Geometric Methods and Manifold Learning

(1)

s lid e C o lo r,

Geometric Methods and Manifold Learning

Mikhail Belkin, Ohio State University,

prepared jointly with Partha Niyogi

(2)

High Dimensional Data

When can we avoid the curse of dimensionality?

Smoothness

rate ≈ (1/n)

^s^d

splines,kernel methods, L

2

regularization...

Sparsity

wavelets, L

1

regularization, LASSO, compressed sensing..

Geometry

graphs, simplicial complexes, laplacians, diffusions

(3)

Geometry and Data: The Central Dogma

Distribution of natural data is non-uniform and

concentrates around low-dimensional structures.

The shape (geometry) of the distribution can be

exploited for efficient learning.

(4)

Manifold Learning

Learning when data _{∼ M ⊂} _R ^N Clustering: _{M → {} 1, . . . , k }

connected components, min cut

Classification: _{M → {−} _1, ₊₁ _}

P on M × {−1, +1}

Dimensionality Reduction: f : M → R ⁿ n << N

M unknown: what can you learn about _M from data?

e.g. dimensionality, connected components holes, handles, homology

curvature, geodesics

(5)

Formal Justification

Speech

speech ∈ l

2

generated by vocal tract Jansen and Niyogi (2005)

Vision

group actions on object leading to different images Donoho and Grimes (2004)

Robotics

configuration spaces in joint movements

Graphics

Manifold + Noise may be generic model in high dimensions.

(6)

Take Home Message

Geometrically motivated approach to learning

nonlinear, nonparametric, high dimensions

Emphasize the role of the Laplacian and Heat Kernel

Semi-supervised regression and classification Clustering and Homology

Randomized Algorithms and Numerical Analysis

(7)

Principal Components Analysis

Given x 1 , . . . , x _n ∈ R ^D

Find y 1 , . . . , y _n ∈ R such that

y _i = w · x _i

and

max w Variance ( { y _i } ) = X

i

y _i ² = w ^T X

i

x _i x ^T _i

! w

X

(8)

Manifold Model

Suppose data does not lie on a linear subspace.

Yet data has inherently one degree of freedom.

(9)

An Acoustic Example

u(t) s(t)

l

(10)

An Acoustic Example

u(t) s(t)

l

One Dimensional Air Flow

(i)

^∂V_∂x

= −

_ρc^A₂ ^∂P_∂t

(ii)

^∂P_∂x

= −

_A^ρ ^∂V_∂t

V (x, t) = volume velocity

P (x, t) = pressure

(11)

Solutions

0.65 0.7

0.75 0.8

0.85 0.9

0.95 1

0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1

beta−1 beta−3

beta−7

u(t) = P

_∞

n=1

α

_n

sin(nω

0

t) ∈ l

2

s(t) = P

_∞

n=1

β

_n

sin(nω

0

t) ∈ l

2

(12)

Acoustic Phonetics

A

l

l ₂

1 A ₂

1 Vocal Tract modeled as a sequence of tubes.

(e.g. Stevens, 1998)

(13)

Vision Example

f : R ² → [0, 1]

F = { f | f (x, y) = v(x − t, y − r ) }

(14)

Robotics

g : S ² × S ² × S ² → R ³

h (θ 1 , φ 1 ), (θ 2 , φ 2 ), (θ 3 , φ 3 ) i → (x, y, z )

(15)

Manifold Learning

Learning when data _{∼ M ⊂} _R ^N Clustering: _{M → {} 1, . . . , k }

connected components, min cut

Classification/Regression: _{M → {−} _1, ₊₁ _} or _{M →} _R

P on M × {−1, +1} or P on M × R

Dimensionality Reduction: f : M → R ⁿ n << N

M unknown: what can you learn about _M from data?

e.g. dimensionality, connected components holes, handles, homology

curvature, geodesics

(16)

Differential Geometry

All you wanted to know about

differential geometry but were

afraid to ask, in 10 easy slides!

(17)

Embedded manifolds

M ^k ⊂ R ^N

Locally (not globally) looks like Euclidean space.

0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000

1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111

S ² ⊂ R ³

(18)

Tangent space

000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000

111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111

T _p M ^k ⊂ R ^N

k -dimensional affine subspace of _R ^N .

(19)

Tangent vectors and curves

0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000

1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111

(20)

Tangent vectors and curves

0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000

1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111

v

φ (t)

φ(t) : R → M ^k

dφ(t) d t

0 = V

Tangent vectors <———> curves.

(21)

Tangent vectors as derivatives

0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000

1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111

v

φ (t)

f : M ^k → R

(22)

Tangent vectors as derivatives

0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000

1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111

v

φ (t)

f : M ^k → R

φ(t) : R → M ^k

f (φ(t)) : R → R

df

dv = d f (φ(t)) d t

0 Tangent vectors <———> Directional derivatives.

(23)

Riemannian geometry

Norms and angles in tangent space.

000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000

111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111

w

v

h v, w i k v k , k w k

(24)

Length of curves and geodesics

000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000

111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111

φ(t) : [0, 1] → M ^k

l(φ) =

Z ¹

0 dφ dt

dt

Can measure length using norm in tangent space.

Geodesic — shortest curve between two points.

(25)

Gradient

000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000

111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111

v

φ (t)

f : M ^k → R

h∇ f, v i ≡ df dv

Tangent vectors <———> Directional derivatives.

(26)

Exponential map

000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000

111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111

(t) r

φ p

w v

q

exp _p : T _p M ^k → M ^k exp _p (v) = r exp _p (w) = q

Geodesic φ(t)

φ(0) = p, φ( k v k ) = q dφ(t) dt

0 = v

(27)

Laplace-Beltrami operator

000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000 000000000000000000000000000000000000000

111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111 111111111111111111111111111111111111111

x

2

p x

1

f : M ^k → R

exp _p : T _p M ^k → M ^k

∆ _M f (p) ≡ X

i

∂ ² f (exp _p (x))

∂x ² _i

Orthonormal coordinate system.

(28)

Intrinsic Curvature

cannot flatten —— can flatten

nonzero curvature —— zero curvature

No accurate map of Earth exists – Gauss’s theorem.

(29)

Dimensionality Reduction

Given x 1 , . . . , x _n ∈ M ⊂ R ^N ,

Find y 1 , . . . , y _n ∈ R ^d where d << N

ISOMAP (Tenenbaum, et al, 00) LLE (Roweis, Saul, 00)

Laplacian Eigenmaps (Belkin, Niyogi, 01)

Local Tangent Space Alignment (Zhang, Zha, 02) Hessian Eigenmaps (Donoho, Grimes, 02)

Diffusion Maps (Coifman, Lafon, et al, 04)

Related: Kernel PCA (Schoelkopf, et al, 98)

(30)

Algorithmic framework

(31)

Algorithmic framework

(32)

Algorithmic framework

Neighborhood graph common to all methods.

(33)

Isomap

1. Construct Neighborhood Graph.

2. Find shortest path (geodesic) distances.

D _ij is n × n

3. Embed using Multidimensional Scaling.

(34)

Multidimensional Scaling

Idea: Distances _→ Inner products _→ Embedding 1. Inner product from distances:

h x , x i − 2 h x , y i + h y , y i = k x − y k ²

A _ii + A _jj − 2A _ij = D _ij

Answer:

A = − 1

2 HDH where H = I − 1

n 11 ^T

In general only an approximation.

(35)

Multidimensional Scaling

2. Embedding from inner products (same as PCA!).

Consider a positive definite matrix A . Then A _ij corresponds to inner products.

A =

X n

i =1

λ _i φ _i φ ^T _i

Then for any x ∈ {1, . . . , n}

ψ(x) = p

λ 1 φ _i (x), . . . , p

λ _k φ _k (x)

∈ R ^k

(36)

Isomap

From Tenenbaum, et al. 00

(37)

Unfolding flat manifolds

Isomap:

“unfolds” a flat manifold isometric to a convex domain in _R ⁿ .

Hessian Eigenmaps:

“unfolds” and flat manifold isometric to an arbitrary domain in _R ⁿ .

LTSA can also find an unfolding.

(38)

Locally Linear Embedding

1. Construct Neighborhood Graph.

2. Let x 1 , . . . , x _n be neighbors of x . Project x to the span of

x 1 , . . . , x _n .

3. Find barycentric coordinates of x ¯ .

x

3

x

1

2

x

¯

x = w 1 x 1 + w 2 x 2 + w 3 x 3

w 1 + w 2 + w 3 = 1

Weights w 1 , w 2 , w 3 chosen,

so that x ¯ is the center of mass.

(39)

Locally Linear Embedding

4. Construct sparse matrix W . i th row is barycentric coordinates of x ¯ _i in the basis of its nearest neighbors.

5. Use lowest eigenvectors of (I − W ) ^t (I − W ) to embed.

(40)

Laplacian and LLE

O x

x

1

2

x

3

X w

_i

x

_i

= 0

X w

_i

= 1

Hessian H . Taylor expansion :

f (x

_i

) = f (0) + x

^t_i

∇f + 1

_i

f (0) − X

i

w

_i

x

^t_i

∇f − 1 2

X

i

x

^t_i

Hx

_i

=

= − 1 2

X

i

x

^t_i

Hx

_i

≈ −trH = ∆f

(41)

Laplacian Eigenmaps

Step 1

[

Constructing the Graph

]

e

_ij

= 1 ⇔ x

_i

“close to” x

_j

1. ǫ-neighborhoods. [

^parameter

ǫ ∈ R ] Nodes i and j are connected by an edge if

|| x

_i

− x

_j

||

²

< ǫ

2. n nearest neighbors. [

parameter

n ∈ N ] Nodes i and j are connected by an edge if i is among

n nearest neighbors of j or j is among n nearest neighbors of i.

(42)

Laplacian Eigenmaps

Step 2

. [

Choosing the weights

].

1. Heat kernel. [

parameter

t ∈ R ]. If nodes i and j are connected, put

W

_ij

= e

⁻

||xi−xj||2 t

2. Simple-minded. [

No parameters

]. W

_ij

= 1 if and only if vertices i and j are connected by an

edge.

(43)

Laplacian Eigenmaps

Step 3.

[

Eigenmaps

] Compute eigenvalues and eigenvectors for the generalized eigenvector problem:

Lf = λDf

D is diagonal matrix where

D

_ii

= X

j

W

_ij

L = D − W

Let f

0

, . . . , f

_k−₁

be eigenvectors.

Leave out the eigenvector f

₀

and use the next m lowest eigenvectors for embedding in an

(44)

Diffusion Distance

Heat diffusion operator H ^t .

δ _x and δ _y initial heat distributions.

Diffusion distance between x and y :

k H ^t δ _x − H ^t δ _y k L

²

Difference between heat distributions after time t .

(45)

Diffusion Maps

Embed using weighted eigenfunctions of the Laplacian:

x → (e ^−λ

¹

^t f 1 (x), e ^−λ

²

^t f 2 (x), . . .)

Diffusion distance is (approximated by) the distance between the embedded points.

Closely related to random walks on graphs.

(46)

Justification

Find y 1 , . . . , y _n ∈ R

min X

i,j

(y _i − y _j ) ² W _ij

Tries to preserve locality

(47)

A Fundamental Identity

But

1 2

X

]

X

i,j

||Y

_i

− Y

_j

||

²

W

_ij

= trace(Y

^T

LY )

subject to Y

^T

Y = I .

Use eigenvectors of L to embed.

(49)

PCA versus Laplacian Eigenmaps

0 20 40

0

10

20

30

40

nz = 75 −5 0 5

x 10⁻³

−8

−6

−4

−2 0 2 4 6 8x 10⁻³

−2 0 2

−4

−2 0 2 4

(50)

On the Manifold

smooth map f : M → R Z

M k∇ ^M f k ² ≈ X

i∼j

W _ij (f _i − f _j ) ²

Recall standard gradient in _R ^k of f (z 1 , . . . , z _k )

∇f =



 



∂f

∂z₁

∂f

∂z₂

·

∂f

∂z_k



 



(51)

Curves on Manifolds

Consider a curve on M

c(t) ∈ M t ∈ (−1, 1) p = c(0); q = c(τ )

f (c(t)) : (−1, 1) → R

| f (0) − f (τ ) | > d _G (p, q) k∇ ^M f (p) k

(52)

Stokes Theorem

A Basic Fact

Z

M k∇ ^M f k ² = Z

f · ∆ _M f

This is like

X

i,j

W _ij (f _i − f _j ) ² = f ^T Lf

where

∆ _M f is the manifold Laplacian

(53)

Manifold Laplacian

Recall ordinary Laplacian in _R ^k This maps

f (x 1 , . . . , x _k ) → −

X k

i =1

∂ ² f

∂x ² _i

!

Manifold Laplacian is the same on the tangent space.

(54)

Properties of Laplacian

Eigensystem

∆ _M f = λ _i φ _i

λ _i ≥ 0 and λ _i → ∞

{ φ _i } form an orthonormal basis for L ² ( M )

Z

k∇ ^M φ _i k ² = λ _i

(55)

The Circle: An Example

φ

− d ² u

dt ² = λu where u(0) = u(2π)

Eigenvalues are

λ _n = n ²

Eigenfunctions are

sin(nt), cos(nt)

(56)

From graphs to manifolds

f : M → R x ∈ M x 1 , . . . , x _n ∈ M

Graph Laplacian:

L ^t _n (f )(x) = f (x) X

j

e ⁻

kx−xjk2

t

− X

j

f (x _j )e ⁻

kx−xjk2 t

Theorem [pointwise convergence] t _n = n ⁻

^k⁺²⁺¹ ^α

n→∞ lim

(4πt _n ) ⁻

^k⁺²²

n L ^t _n

ⁿ

f (x) = ∆ _M f (x)

(57)

From graphs to manifolds

Theorem [convergence of eigenfunctions]

t→ 0 lim ,n→∞ Eig [L ^t _n

ⁿ

] → Eig [∆ _M ]

Belkin Niyogi 06

(58)

Estimating Dimension from Laplacian

λ 1 ≤ λ 2 . . . ≤ λ _j ≤ . . .

Then

A + 2

d log(j ) ≤ log(λ _j ) ≤ B + 2

d log(j + 1)

Example: on S ¹

λ _j = j ² = ⇒ log(λ _j ) = 2

1 log(j )

(Li and Yau; Weyl’s asymptotics)

(59)

Visualization

Data representation, dimensionality reduction, visualization

Visualizing spaces of digits.

Partiview, Ndaona, Surendran 04

(60)

Motion estimation

Markerless motion estimation: inferring joint angles.

Corazza, Andriacchi, Stanford Biomotion Lab, 05, Partiview, Surendran

Isometrically invariant representation. [link]

Eigenfunctions of the Laplacian are invariant under

isometries.

(61)

Graphics, etc

Laplacian from meshes/non-probabilistic point clouds.

Belkin, Sun, Wang 08, 09

(62)

Recall

Heat equation in _R ⁿ :

u(x, t) – heat distribution at time t .

u(x, 0) = f (x) – initial distribution. x ∈ R ⁿ , t ∈ R .

∆ _R

ⁿ

u(x, t) = du

dt (x, t)

Solution – convolution with the heat kernel:

u(x, t) = (4πt) ⁻

ⁿ²

Z

R

ⁿ

f (y)e ⁻

^kx−yk

2 4t

dy

(63)

Proof idea (pointwise convergence)

Functional approximation:

Taking limit as t → 0 and writing the derivative:

∆ _R

ⁿ

f (x) = d dt

(4πt) ⁻

ⁿ²

Z

R

ⁿ

f (y)e ⁻

^kx−yk

2 4t

dy

0

(64)

Proof idea (pointwise convergence)

Functional approximation:

Taking limit as t → 0 and writing the derivative:

(65)

Proof idea (pointwise convergence)

Functional approximation:

dy

Empirical approximation:

Integral can be estimated from empirical data.

∆ _R

ⁿ

f (x) ≈ − 1

t (4πt) ⁻

ⁿ²

f (x) − X

f (x _i )e ⁻

^kx−^xi^k

2 4t

!

(66)

Some difficulties

Some difficulties arise for manifolds:

Do not know distances.

Do not know the heat kernel.

||x−y||

x

y

M

dist (x,y)

_M

(67)

Some difficulties

Some difficulties arise for manifolds:

Do not know distances.

Do not know the heat kernel.

||x−y||

x

y

M

dist (x,y)

_M

Careful analysis needed.

(68)

The Heat Kernel

H _t (x, y) = P

i e ^−λ

ⁱ

^t φ _i (x)φ _i (y)

in _R ^d , closed form expression

H _t (x, y) = 1

(4πt) ^d/ ² e ⁻

^kx−yk

2 4t

Goodness of approximation depends on the gap

H _t (x, y) − 1

(4πt) ^d/ ² e ⁻

^kx−yk

2 4t

H _t is a Mercer kernel intrinsically defined on manifold.

(69)

Three Remarks on Noise

1. Arbitrary probability distribution on the manifold:

convergence to weighted Laplacian.

2. Noise off the manifold:

µ = µ _M

^d

+ µ _R

^N

Then

t→ lim 0 L ^t f (x) = ∆f (x)

3. Noise off the manifold:

z = x + η ( ∼ N (0, σ ² I ))

We have

(70)

NLDR: some references

A global geometric framework for nonlinear dimensionality reduction.

J.B. Tenenbaum, V. de Silva and J. C. Langford, 00.

Nonlinear Dimensionality Reduction by Locally Linear Embedding.

L. K. Saul and S. T. Roweis. 00

Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.

M.Belkin, P.Niyogi, 01.

Hessian Eigenmaps: new locally linear embedding techniques for high-dimensional data. D. L.

Donoho and C. Grimes, 02.

Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment.

Zhenyue Zhang and Hongyuan Zha. 02.

Charting a manifold. Matthew Brand, 03

Diffusion Maps. R. Coifman and S. Lafon. 04.

Many more: http://www.cse.msu.edu/∼lawhiu/manifold/

(71)

Unlabeled data

Reasons to use unlabeled data in inference:

Pragmatic:

Unlabeled data is everywhere. Need a way to use it.

Philosophical:

The brain uses unlabeled data.

(72)

Geometry of classification

How does shape of the data affect classification?

Manifold assumption.

Cluster assumption.

Reflect our understanding of structure of natural data.

(73)

Intuition

(74)

Intuition

8 15 30 50

Number of Labeled Points

Error rate, %

k−NN

Geodesic k−NN

(81)

Cluster assumption

(82)

Cluster assumption

00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000 00000000000000000000000000

11111111111111111111111111

(83)

Unlabeled data

Geometry is important.

(84)

Unlabeled data

Geometry is important.

Unlabeled data to estimate geometry.

(85)

Manifold assumption

Manifold/geometric assumption:

functions of interest are smooth with respect to the

underlying geometry.

(86)

Manifold assumption

Manifold/geometric assumption:

functions of interest are smooth with respect to the underlying geometry.

Probabilistic setting:

Map X → Y . Probability distribution P on X × Y .

Regression/(two class)classification: X → R .

(87)

Manifold assumption

Manifold/geometric assumption:

functions of interest are smooth with respect to the underlying geometry.

Probabilistic setting:

Map X → Y . Probability distribution P on X × Y . Regression/(two class)classification: X → R .

Probabilistic version:

conditional distributions P (y | x) are smooth with respect to

the marginal P (x) .

(88)

What is smooth?

Function f : X → R . Penalty at x ∈ X :

1 δ ^k ⁺²

Z

small _δ

(f (x) − f (x + δ)) ² p(x)d δ ≈ k∇ f k ² p(x)

Total penalty – Laplace operator:

Z

X k∇ f k ² p(x) = h f, ∆ _p f i _X

(89)

What is smooth?

Function f : X → R . Penalty at x ∈ X :

1 δ ^k ⁺²

Z

small _δ

(f (x) − f (x + δ)) ² p(x)d δ ≈ k∇ f k ² p(x)

Total penalty – Laplace operator:

Z

X k∇ f k ² p(x) = h f, ∆ _p f i _X

Two-class classification – conditional P (1 | x) .

= 1

= 1

(92)

Regularization

Estimate f : R ^N → R

Data: ( x 1 , y 1 ), . . . , ( x _l , y _l )

Regularized least squares (hinge loss for SVM):

f ^∗ = argmin

f ∈H

1 l

X (f ( x _i ) − y _i ) ² + λ k f k ² _K

fit to data + smoothness penalty

k f k ^K incorporates our smoothness assumptions.

Choice of _{k k} _K is important.

(93)

Algorithm: RLS/SVM

Solve : f ^∗ = argmin

f ∈H

1 l

X (f ( x _i ) − y _i ) ² + λ k f k ² K

k f k ^K is a Reproducing Kernel Hilbert Space norm with kernel K ( x , y ) .

Can solve explicitly (via Representer theorem):

f ^∗ ( · ) =

X l

i =1

α _i K ( x _i , · )

[α 1 , . . . , α _l ] ^t = ( K + λI ) ⁻ ¹ [y 1 , . . . , y _l ] ^t

( ) = ( )

(94)

Manifold regularization

Estimate f : R ^N → R

Labeled data: ( x 1 , y 1 ), . . . , ( x _l , y _l )

Unlabeled data: x _l ₊₁ , . . . , x _l ₊ _u f ^∗ = argmin

f ∈H

1 l

X (f ( x _i ) − y _i ) ² + λ _A k f k ² K + λ _I k f k ² I

fit to data + extrinsic smoothness + intrinsic smoothness

Empirical estimate:

k f k ² _I = 1

(l + u) ² [f ( x 1 ), . . . , f ( x _l ₊ _u )] L [f ( x 1 ), . . . , f ( x _l ₊ _u )] ^t

(95)

Laplacian RLS/SVM

Representer theorem (discrete case):

f ^∗ ( · ) =

l + u

X

i =1

α _i K ( x _i , · )

Explicit solution for quadratic loss:

¯

α = (J K + λ _A lI + λ _I l

(u + l) ² LK ) ⁻ ¹ [y 1 , . . . , y _l , 0, . . . , 0] ^t

( K ) _ij = K ( x _i , x _j ), J = diag (1, . . . , 1

| {z } , 0, . . . , 0

| {z } )

(96)

Experimental results: USPS

10 20 30 40

LapSVM Std Dev TSVM

LapSVM SVM

LapSVM RLS

LapRLS

(97)

Experimental comparisons

Dataset → g50c Coil20 Uspst mac-win WebKB WebKB WebKB

Algorithm ↓ (link) (page) (page+link)

SVM (full labels) 3.82 0.0 3.35 2.32 6.3 6.5 1.0

SVM (l labels) 8.32 24.64 23.18 18.87 25.6 22.2 15.6

Graph-Reg 17.30 6.20 21.30 11.71 22.0 10.7 6.6

TSVM 6.87 26.26 26.46 7.44

14.5 8.6

7.8 Graph-density 8.32 6.43 16.92 10.48 - - -

∇ TSVM 5.80 17.56 17.61 5.71 - - -

LDS 5.62 4.86 15.79

5.13

- - -

LapSVM

5.44 3.66 12.67

10.41 18.1 10.5

6.4

(98)

−0.46

−0.26

0.46 0.46 0.26

L =



 



2 −1 −1 0 0 0

−1 2 −1 0 0 0

−1 −1 3 −1 0 0

0 0 −1 3 −1 −1

0 0 0 −1 2 −1

0 0 0 −1 −1 2



 



Unnormalized clustering:

L e ₁ = λ 1 e ₁ e ₁ = [ − 0.46, − 0.46, − 0.26, 0.26, 0.46, 0.46]

Normalized clustering:

Le ₁ = λ 1 De ₁ e ₁ = [ − 0.31, − 0.31, − 0.18, 0.18, 0.31, 0.31]

(103)

Graph Clustering: Mincut

Mincut: minimize the number (total weight) of edges cut).

argmin

S

X

i∈S, j ∈V −S

w _ij

(104)

Graph Laplacian

f

f f

1

f

f f

2

3 4

5

6

L =



 



2 −1 −1 0 0 0

−1 2 −1 0 0 0

−1 −1 3 −1 0 0

0 0 −1 3 −1 −1

0 0 0 −1 2 −1

0 0 0 −1 −1 2



 



Basic fact:

X

i∼j

(f _i − f _j ) ² w _ij = 1

2 f ^t L f

(105)

Graph Laplacian

f

f f

1

f

f f

2

3 4

5

6

L =



 



2 −1 −1 0 0 0

−1 2 −1 0 0 0

−1 −1 3 −1 0 0

0 0 −1 3 −1 −1

0 0 0 −1 2 −1

0 0 0 −1 −1 2



 



argmin

S

X

i∈S, j ∈V −S

w _ij = argmin

f

i

∈{− 1 , 1 }

X

i∼j

(f _i − f _j ) ² = 1

8 argmin

f

i

∈{− 1 , 1 }

f ^t L f

Relaxation gives eigenvectors.

(106)

Geometric Methods and Manifold Learning

s lid e C o lo r,