Computational Methods for Manifold Learning

Computational Methods for Manifold Learning

Manifold learning Xin Yang Data Mining Course 1 Outline Manifold and Manifold Learning

Classical Dimensionality Reduction Semi-Supervised Nonlinear Dimensionality Reduction Experiment Results Conclusions Data Mining Course 2

What is a manifold? Data Mining Course 3 Examples: sphere and torus Data Mining Course

4 Why we need manifold? Data Mining Course 5

Data Mining Course 6 Manifold learning Raw format of natural data is often high dimensional, but in many cases it is the outcome of some process involving only few degrees of

freedom. Data Mining Course 7 Manifold learning Intrinsic Dimensionality Estimation Dimensionality Reduction

Data Mining Course 8 Dimensionality Reduction Classical Method: Linear: MDS & PCA (Hastie 2001) Nonlinear: LLE (Roweis & Saul, 2000) ,

ISOMAP (Tenebaum 2000), LTSA (Zhang & Zha 2004) -- in general, low dimensional coordinates lack physical meaning Data Mining Course 9

Semi-supervised NDR Prior information Can be obtained from experts or by performing experiments Eg: moving object tracking Data Mining Course

10 Semi-supervised NDR Assumption: Assuming the prior information has a physical meaning, then the global low dimensional coordinates bear the same physical meaning.

Data Mining Course 11 Basic LLE Data Mining Course 12

Basic LTSA Characterized the geometry by computing an approximate tangent space Data Mining Course 13

SS-LLE & SS-LTSA Give m the exact mapping data points . Partition Y as Our problem : Data Mining Course

14 SS-LLE & SS-LTSA To solve this minimization problem, partition M as: Then the minimization problem can be written as

Data Mining Course 15 SS-LLE & SS-LTSA Or equivalently Solve it by setting its gradient to be zero, we get:

Data Mining Course 16 Sensitivity Analysis With the increase of prior points, the condition number of the coefficient matrix gets smaller and smaller, the

computed solution gets less sensitive to the noise in and Data Mining Course 17 Sensitivity Analysis

The sensitivity of the solution depends on the condition number of the matrix Data Mining Course 18 Inexact Prior Information

Add a regularization term, weighted with a parameter Data Mining Course 19 Inexact Prior Information Its minimizer can be computed by

solving the following linear system: Data Mining Course 20 Experiment Results incomplete tire --compare with basic LLE and LTSA

--test on different number of prior points Up body tracking --use SSLTSA --test on inexact prior information algorithm Data Mining Course

21 Incomplete Tire Data Mining Course 22 Data Mining Course

23 Relative error with different number of prior points Data Mining Course 24

Up body tracking Data Mining Course 25 Results of SSLTSA

Data Mining Course 26 Results of inexact prior information algorithm Data Mining Course

27 Conclusions Manifold and manifold learning Semi-supervised manifold learning Future work Data Mining Course

28 Data Mining Course 29

Recently Viewed Presentations