西瓜书：LLE推导

所谓LLE（局部线性嵌入）即”Locally Linear Embedding”的降维算法，在处理所谓流形降维的时候，效果比PCA要好很多。
首先，所谓流形，我们脑海里最直观的印象就是Swiss roll,在吃它的时候喜欢把它整个摊开成一张饼再吃，其实这个过程就实现了对瑞士卷的降维操作，即从三维降到了两维。降维前，我们看到相邻的卷层之间看着距离很近，但其实摊开成饼状后才发现其实距离很远，所以如果不进行降维操作，而是直接根据近邻原则去判断相似性其实是不准确的。

LLE的降维实现过程，直观的可视化效果如下图1所示：

一、LLE原理

LLE的原理其实是这样的：

所谓局部线性，即认为在整个数据集的某个小范围内，数据是线性的，就比如虽然地球是圆的，但我们还是可以认为我们的篮球场是个平面；而这个“小范围”，最直接的办法就是k-近邻原则。这个“近邻”的判断也可以是不同的依据：比如欧氏距离，测地距离等。

既然是线性，则对每个数据点 (D维数据，即D1的列向量)，可以用其近邻数据点的线性组合来表示(见上图2)，即:

上式中，wi 是 k1的列向量，wji 是 wi 的第 j 行, xji 是 xi 的第 j 个近邻点(1<=j<=k)，即


特别注意：此处xi中的维度为D，切不可把 xji 视为x i中的第j个元素,只是这里的表示刚好凑巧相同。

通过使下述Loss-function最小化：

求解上式可得到权重系数

其中 w (维度为kXN）对应于 N 个数据点，即 N 列
接下来是LLE中又一个假设：即认为将原始数据从D维降到d维后，
其依旧可以表示为其k近邻的线性组合，且组合系数不变，即 仍然是wi ,再一次通过最小化loss function:

最终得到降维后位于低维空间的的数据:

二、算法推导

step 1：
运用k近邻算法得到每个数据 xi 的 k 近邻点：

step 2: 求解权重系数矩阵
即求解如下有约束优化问题：

在推导之前，我们首先统一下数据的矩阵表达形式
输入和权重分别为：


则可逐步推导出权重系数矩阵的表达式：

将 Si 看做局部协方差矩阵, 即:


运用拉格朗日乘子法：

求导可得：


其中 1k 为 k1的元素全1的列向量，就上述表达式而言，局部协方差矩阵Si 是个k k 的矩阵，其分母实质是矩阵Si 逆矩阵的所有元素之和，而其分子是Si 的逆矩阵对行求和后得到的列向量。

step 3: 映射到低维空间
即求解下述有约束优化问题：


输出结果即低维空间向量组成的矩阵Y：

首先，用一个 NN 的稀疏矩阵(sparse matrix) W来表示w:
对 i 的近邻点 j ：
否则 :
因此：
其中，
其中，Wi是方阵 W(NN)的第i列 ， Ii是单位矩阵 I(N*N)的第i列，yi 对应矩阵Y第 i 列，所以 :

由矩阵相关知识可知：对矩阵 A = [a1, a2, …, aN] ，有

由于Y(Ii-Wi)对应的是矩阵的一列,好比上述中 ai,所以对于整个矩阵而言Y(I-W)类比上述矩阵A，所以：


再一次使用拉格朗日乘子法：



可见Y其实是M的特征向量构成的矩阵，为了将数据降到 d 维，我们只需取M的最小的 d 个非零特征值对应的特征向量，而一般第一个最小的特征值接近0，我们将其舍弃，最终按从小到大取前 [2, d+1] 个特征值对应的特征向量。