Global vs. Local
?
?
?
然而 Isomap 的全局方法有一个很大的问题就是要考虑任意两点之间的关系，这个数量将随着数据点数量的增多而爆炸性增长，从而使得计算难以负荷。
另一方面，随着互联网的发展，我们所面临的数据规模正变得越来越大，例如图中所示的 twitter 社交网络于2008年的一个子集所构成的一个图，包含大约2万 个节点、25万条边。Twitter 现在的用户数量已经超过一 亿，并且还在飞速增长。诸 如此类的巨型结构使用全局 方法进行分析正在变得越来 越不切实际。
因此，以 LLE 为开端的局部分 析方法的变种和相关的理论基 础研究逐渐受到更多的关注。。
谱图理论
?
?
图上的拉普拉斯算子：拉普拉斯矩阵
??=?????，??是对角线元素为度数的对角阵，??是权重矩阵
1 2 3 4 5 6 1 2 3 2?10?13?10?1200?1?1?10000
4 5 6 0?10
0?10?1003?1?1?130?101
谱图理论
??
拉普拉斯矩阵特征向量组成了一组正交向量基，大量应用于学习问题 “非洲”的特征向量
谱图理论
?
图上的拉普拉斯算子收敛到流形上的拉普拉斯算子
???
M. Belkin, P. Niyogi, Towards a theoretical foundations for Laplacian based manifold methods, COLT 2005.
M. Hein, et al., From graphs to manifolds – weak and strong pointwise consistency of graph Laplacian, COLT 2005.
A. Singer, From graph to manifold Laplacian: the convergence rate, Applied and Computational Harmonic Analysis, 2006
?
拉普拉斯矩阵的特征向量收敛到流形上拉普拉斯的特征函数
??
U. von Luxburg, et al., Consistency of spectral clustering, Max Planck Institute technique report, 2004
M. Belkin, P. Niyogi, Convergence of Laplacian eigenmaps, NIPS 2006.
LE
?
希望保持流形的近邻关系: 将原始空间中相近的点映射成目标空间中相近的点 目标函数：Ey=???????????????
=1，去除任意的缩放
转化成一个特征向量问题：????=????
LE的求特征向量问题对应于连续的时候求拉普拉斯特征函数问题
2
?
??
?约束条件：????
??
流形学习(浙大)
