文档介绍：流形学习简介
许馨

设是一个低维流形, 是一个光滑嵌入,
其中 D>d . 数据集是随机生成的,且经过 f 映射为观
察空间的数据流形学习就是在给定观察样本
集的条件下重构 f 和.
V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction . Neural Information Processing Systems 15 (NIPS'2002), pp. 705-712, 2003.
流形学习的定义
几种流形学习算法
局部线性嵌入(LLE).
S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, pp. 2323--2326, 2000.
等距映射(Isomap).
. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp. 2319--2323, 2000.
拉普拉斯特征映射(Laplacian Eigenmap).
M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. putation, Vol. 15, Issue 6, pp. 1373 –1396, 2003 .
基于流形学习的方法-LLE(locally linear embedding)*
:对于一组具有嵌套流形的数据集,在嵌套空间与内在低维空间局部邻域间的点的关系应该不变。
即在嵌套空间每个采样点可以用它的近邻点线性表示,在低维空间中保持每个邻域中的权值不变,重构原数据点, 使重构误差最小.
:
1)设D维空间中有N个数据属于同一流形,记做:Xi=〔xi1,xi2,...,xiD〕,i=1~N。假设有足够的数据点,并且认为空间中的每一个数据点可以用它的K个近邻线性表示。求近邻点,一般采用K近邻或者邻域.
2)计算权值Wij,代价函数为:
,(1)
并且权值要满足两个约束条件: <1>每一个数据点Xi都只能由它的邻近点来表示,若Xj不是近邻点,则Wij=0;
<2>权值矩阵的每一行的和为1,即: 。
这样,求最优权值就是对于公式(1)在两个约束条件下求解最小二乘问题。权值体现了数据间内在的几何关系。,
基于流形学习的方法-LLE(locally linear embedding)*
3)保持权值不变,在低维空间d(d<<D)中对原数据点重构。设低维空间的数据点为Yi,可以通过求最小的代价函数

(2)来得到。

公式(2)的最优解需要满足下面的约束条件:
1) ; 2)

条件1消除了Y向量平移不变的影响;条件2避免产生退化解。??
由Rayleittz-Riz定理,低维嵌入是 M 的最小的第 2到第 d+1 个特征向量.
去掉最小特征值0对应的特征向量。
LLE算法示意图
基于流形学习的方法-LLE(locally linear embedding)*
LLE算法的优点
LLE算法可以学习任意维数的低维流形.
LLE算法中的待定参数很少, K 和 d.
LLE算法中每个点的近邻权值在平移, 旋转,伸缩变换下是保持不变的.
LLE算法有解析的整体最优解,不需迭代.
LLE算法归结为稀疏矩阵特征值计算, 计算复杂度相对较小, 容易执行.
基于流形学习的方法-LLE(locally linear embedding)*
LLE算法的缺点
LLE算法要求所学习的流形只能是不闭合的且在局部是线性的.
LLE算法要求样本在流形上是稠密采样的.
LLE算法中的参数 K, d 有过多的选择.
LLE算法对样本中的噪音很敏感.
对于新样本的映射需要重新计算。
R
基于流形学习的方法-LLE(locally linear embedding)*
LLE算法的例子(1)
基于流形学习的方法-LLE(locally linear embedding)*
K选取的原则:
1 近邻点K的值要大于流形的维数d;K>>d会提高算法的鲁棒性;
2 K不能过大,对于高曲率的流形,K过大会导致不能正确表示