Manifold Learning Kai Yang sadoii@163.com 1.12.2015.

Presentation on theme: "Manifold Learning Kai Yang sadoii@163.com 1.12.2015."— Presentation transcript:

1 Manifold Learning Kai Yang

2 Machine Learning Problem
(Training Data) f C罗 1.欧式空间 2.我们是否还需要去关注，当数据不处于欧式空间的时候，如何解决？ We always think X and Y are in Euclidean space f:X→Y Manifold learning

3 Outline What’s manifold and manifold learning?
What’s classical methods and its application? Summary and thought. Manifold learning

4 What’s manifold and manifold learning?
Background Motivation Manifold learning

5 Background Manifold Manifold = Many + Fold 流形学习——北大数学系江泽涵教授
2.流形是一个空间，而不是一个形状——流形空间。 3.形象表示流形，不从数学上说明。 Manifold learning

6 Background Manifold learning Dimensionality reduction
The geometry and topology of data manifold Study on machine learning problem under manifold assumption Dimensionality reduction Manifold learning

7 Motivation Data:Euclidean space Traditional dimensionality reduction
Principal Component Analysis(PCA) Linear Discriminant Analysis(LDA) PCA 降维的意义： 1.原始采样空间冗余信息过多 2.数据可视化，特征提取 Data:Euclidean space LDA Manifold learning

8 Motivation Traditional method in manifold PCA Not Work!
Manifold learning

9 Manifold learning Manifold Dimensionality Reduction
It’s an dimensionality reduction method based on manifold space Manifold Dimensionality Reduction Manifold learning

10 Manifold learning Low-dimensional embedding / coordinate space
dimensionality reduction Maintain a certain geometric properties (principle) High-dimensional data / observation space Low-dimensional embedding / coordinate space [王瑞平,流形学习专题介绍] Manifold learning

11 Outline What’s classical methods and its application? 等距离映射 局部线性嵌入
(Isometric MaPPing,ISOMAP) 局部线性嵌入 (Locally Linear Embedding,LLE) Manifold learning

12 The manifold ways of perception[H. Sebastian Seung, Daniel D
The manifold ways of perception[H. Sebastian Seung, Daniel D. Lee,2000,science] 这篇文章的重要在于，告诉人们所认知的世界，是流形的。 而机器学习是让机器模拟人的行为，因此让机器去研究流形的流形学习就有了现实意义。 Professor of Computer Science and the Princeton Neuroscience Institute Professor in School of Engineering and Applied Science at the University of Pennsylvania Manifold learning

13 Isometric Feature Mapping
J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp , 2000. Cited Views: 7424 Manifold learning

14 Isometric Feature Mapping
geodesic distance Embedding space of dimensionality reduction Euclidean distance vs. geodesic distance Shortest path approximate geodesic distance 我们研究的是流形空间，而非欧式空间。那么我们需要找到一种，在流形空间中表示距离的量。 欧式空间的距离，两个点的坐标差。那么在流形空间，应该如何鉴定两个点的距离呢？——测底距离。 测底距离：1.形成紧邻图。2.相邻点用欧氏距离表示测底距离，不相邻点用最短路径表示测底距离。 Manifold learning

15 Isometric Feature Mapping
The basic idea After the reduction, the distance between any two points in low-dimensional space should be same with distance in the original high-dimensional space xi xj gij yi yj dij Mapping gij dij Manifold learning

16 Isometric Feature Mapping
证明在欧式空间相似性较小，但流形空间相似性大的数据，降维之后仍能保持原有的相似性。 16 Manifold learning

17 Locally linear Embedding
Cited Views: 7660 Locally linear Embedding S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, pp , 2000. Cited Views: 7660 Manifold learning

18 Locally linear Embedding
The basic idea Sampling data with low-dimensional manifold is linear approximately a Euclidean space locally Data samples on manifold Manifold learning

19 Locally linear Embedding
Manifold learning

20 Locally linear Embedding
Manifold learning

21 Application Data visualization Information retrieval Image process
Pattern recognition …… Manifold learning

22 Outline Summary and Thoughts. Compare ISOMAP and LLE Conclusion
Resources and Reference Manifold learning

23 ISOMAP vs LLE Similar They all can keep the geometrical properties of manifold for the same purpose. Manifold learning

24 ISOMAP vs LLE Different
Isomap wants to maintain the geodesic distance between any two points while LLE hope to maintain local linear relationship 从保持几何的角度来看，Isomap保持了更多的信息量 LLE算法希望样本集均匀稠密采样于低维流形，因此，对于受噪声污染、样本密度稀疏或相互关联较弱的数据集，在从高维观测 空间到低维嵌入空间的映射过程中，可能会将相互关联较弱的远点映射到局部近邻点的位置，从而破坏了低维嵌入结果。 Manifold learning

25 ISOMAP vs LLE Different Isomap:global LLE:local Too Hard Better
从复杂度角度来看 Isomap:考虑任意两点之间的关系，这个数量将随着数据点数量的增多而爆炸性增长，从而使得计算难以负荷。 以 LLE 为开端的局部分 析方法的变种和相关的理论基 础研究逐渐受到更多的关注。 Too Hard Better Isomap:global LLE:local Manifold learning

26 Conclusion Advantage Disadvantages
Based on the geometry structure of the manifold, can keep the original information Disadvantages The assumption of manifold structure Neighborhood parameter k 非线性：基于流形内在几何结构，体现现实数据的本质 对观察数据存在流形结构的假设 需要调节较多的算法参数，如k-NN的邻域参数k Manifold learning

27 Resources Isomap LLE Mani fold Learning Matlab Demo
LLE Mani fold Learning Matlab Demo Comparison of Manifold Learning methods manifold/plot_compare_methods.html Manifold learning

28 Reference Xiaofei He ：manifold learning Homepage: Joshua B. Tenenbaum, Vin de Silva, John C. Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction Sam T. Roweis and Lawrence K. Saul. Nonlinear Dimensionality Reduction by Locally Linear Embedding Chunguang LI. Manifold Learning and its Application in Pattern Recognition Yingke Lei. The study of Manifold Learning Algorithms and Their Applications Ruiping Wang. Manifold Learning presentations Manifold learning

29 Question and Answer? 2011年11月1日

30 Thanks! Manifold learning