LLE:Locally Linear Embedding
核心原理#
LLE是一种无监督流形学习算法，核心是保持样本的局部线性关系来实现降维。LLE假设高维数据位于低维流形上，每个样本可由其领域内样本线性重建，降维后需保持这种局部重建关系不变，从而在低维中保留高维数据的集合结构。
算法流程#
1. 近邻搜索：为每个点找k个近邻#
对于每个样本点 $x_i$，找到其K个最近邻 $$\mathcal{N}(i)={j_i,\cdots,j_K}$$
常见做法：（1）欧式距离+KNN；（2）高维数据时用KD-tree/Ball-tree/ANN
2. 计算局部线性重构权重#
对于每个点 $x_i$，用它的邻居线性重构，即
$$x_i\approx \sum_{j\in \mathcal{N}(i)} w_{ij}x_j$$
通过最小化重构误差来求权重：
$$\min_{w_{ij}}\Vert x_i-\sum_{j\in \mathcal{N}(i)}w_{ij}x_j\Vert^2$$
数学上可以进行如下求解：定义领域偏移矩阵
$$Z_{i}=\left[ \begin{aligned} &x_{j_1}-x_i \ &... \ &x_{j_K}-x_i \end{aligned} \right]\in \mathbb{R}^{K\times D}$$
局部协方差矩阵
$$C_i=Z_i Z_i^T\in \mathbb{R}^{K\times K}$$
权重由以下问题给出：
$$\min_{w_i} w_i^T C_i w_i,s.t. 1^T w_i=1$$
闭式解为：
$$w_i=\frac{C_i^{-1}1}{1^T C_i^{-1}1}$$
关于数值稳定性：如果$K>D$，邻居近似共线性，$C_i$可能病态，使用迭代缓解该问题
$$C_i\leftarrow C_i+\epsilon\cdot tr(C_i)I$$
3. 低维嵌入#
有了权重 $w_{ij}$，目标是在低维空间中找到点$y_i\in\mathbb{R}^d,d<<D $，使得同样的重构关系成立
$$y_i\approx \sum_j w_{ij}y_j$$
全局目标函数为：
$$\Phi(Y)=\sum_i\Vert y_i-\sum_j w_{ij}y_j \Vert^2$$
整理成矩阵形式：设$W\in \mathbb{R}^{N\times N}$为稀疏权重矩阵，$M=(I-W)^T(I-W)$，那么有
$$\Phi(Y)=Tr(Y^TMY)$$
可以将上述问题转换为特征值问题
$$Mv=\lambda v$$
其中，
- 最小特征值$\lambda_0=0$，对应平凡解
- 取第2到第$d+1$个最小特征向量拼成低维坐标，即 $$Y=[v_2,\cdots,v_{d+1}]$$
Manifold LLE#
为了解决以下问题：当邻居数$K$偏大，或邻居在局部近似共线/共面，$C_i=Z_i Z_i^T$病态甚至接近奇异，其导致的后果是：（1）权重解不稳定；（2）嵌入维度有效自由度下降。
Manifold LLE认为不是所有邻居方向都可信，只用有效局部维度的方向来重构。具体来说，Manifold LLE对局部协方差矩阵做特征分解，丢弃噪声方向，并在低维子空间中计算重构误差。
对$C_i$做特征分解，即 $$C_i=U\Lambda U^T$$
只保留前$d$个较大的特征值，即保留内在维度： $$C_i^{(d)}=U_d\Lambda_d U_d^T$$
权重计算改为： $$w_i=\underset{1^T w=1}{\arg\min} w^T C_i^{(d)} w$$
Hessian LLE#
为了解决以下问题：标准LLE只看一阶关系，即某个样本点是否能由邻居线性拼出。但在弯曲流形上，一阶线性关系不足以区分两个点是否真正在同一流形上，不同流形可能有相同的一阶近似。
Hessian LLE期望实现等距参数化（isometric embedding），即流形上两点之间的真实距离，在低维坐标里不被拉伸、不被压缩，这一点借用曲率进行判断。算法流程如下：
1. 局部PCA#
对$Z_i$做SVD，即 $$X_i=U_i\Sigma_i V_i^T$$
取前$d$个主方向
$$T_i=V_i^{(1:d)}\in \mathbb{R}^{D\times d}$$
式中，$T_i$是流形在$x_i$处的切空间基，是为局部平直坐标系。
将邻居投影到切空间坐标，即 $$u_{ij}=T_i^T(x_j-x_i)\in\mathbb{R}^d$$
由此获得领域点在流形坐标中的位置。
2. 构造Hessian约束#
记第$k$个嵌入坐标为一个函数 $$f^{(k)}(x_i)=y_i^{(k)}$$
Hessian LLE期望对于每个$f^{(k)}$，在流形方向上，Hessian为0，即等距嵌入。
在d维切空间中，即二阶单项式为$\phi(u)\in \mathbb{R}^m$，式中$m=\frac{d(d+1)}{2}$。对于领域内的所有点，可以构造局部设计矩阵 $\Phi_i\in\mathbb{R}^{K\times m}$。
为了消除不影响Hessian矩阵的常数项与线性项，HLLE对$\Phi_i$做QR/SVD，投影到正交补空间，得到矩阵$H_i$，最终得到算子
$$H_i f_i=Hessian(f)$$
对于每个点$i$，得到约束 $$\Vert H_i f_i \Vert^2\approx 0$$
3. 全局拼接与问题转化#
将所有点的约束相加
$$\sum_i \Vert H_i f_i\Vert^2$$
可写成全局二次型，即
$$\min_f f^T\mathcal{H} f$$
式中，$\mathcal{H}$为稀疏对称矩阵。
可以将上述问题转化为特征值问题，即 $$Hv=\lambda v$$
其中最小特征值对应平凡解，取接下来$d$个最小非0特征向量拼成嵌入坐标。