局部线性嵌入

前言

最近的看的资料主要是关于流形学习的,其应用还是围绕降维。这篇的主要内容是关于LLE算法的。

LLE算法

局部线性嵌入算法(Locally linear embedding)是由Sam T.Roweis和Lawrence K.Saul于2000年发表于《Science》杂志,巧合是的它同Isomap同一时间一起发表。

算法思想

同全局优化的Isomap算法相比,局部线性嵌入是一种局部算法。它的主要思想是利用数据的局部线性来逼近全局线性:即假设任意样本点都可表示为其临近样本点的线性组合,在寻找数据的低维嵌入同时,保持这种邻域线性组合关系不变。

算法步骤

关于算法大致步骤,可以参考资料[1],对于公式的推导可参考资料[2]和[3],比较详细的推导过程可直接参考[3]。
[1] LLE及其改进算法介绍
[2] An Introduction to Locally Linear Embedding
[3] A note on the locally linear embedding algorithm

总结来说,LLE算法可以归结为三步:
(1)寻找每个样本点的$k$个近邻点;
(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵;
(3)由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。
具体的步骤详细描述。

第一步
对于每个样本点$x_i$,根据参数($S$或者$\epsilon$)计算出该样本点的邻域点集合$N_i={ \alpha_{i1},…,\alpha_{ik} }$。这里为了表示方便起见,我采用固定邻域点个数参数$S$。

第二步
这一步的作用是计算出每个样本点的局部线性系数矩阵。
假设样本点$x_i$可被邻域样本点$\alpha_{i1},…,\alpha_{ik}$线性表示,定义目标函数(误差最小化)
\begin{align}
\arg \min_w & \sum_{i=1}^N | x_i-\sum_{j=1}^S w_{ij}\alpha_{ij} |^2 \\
s.t. & \sum_{j=1}^S w_{ij}=1,i=1,…,N
\end{align}

$N$为样本总数,$w_{ij}$为样本点$i$对应的第$j$个系数。
我们观察单个样本点的目标函数
\begin{align}
| x_i-\sum_{j=1}^S w_{ij}\alpha_{ij} |^2 &=| \sum_{j=1}^S (w_{ij}x_i- w_{ij}\alpha_{ij}) |^2 \\
&=| \sum_{j=1}^S w_{ij}(x_i- \alpha_{ij}) |^2 =| Q_i w_i |^2
\end{align}

这里$Q_i=(x_i-\alpha_{i1},…,x_i-\alpha_{iS})$,系数向量$w_i=(w_{i1},…,w_{iS})^T$。
很容易看出这是个优化问题,可以采用拉格朗日乘数法:
\begin{align}
F_i &= | x_i-\sum_{j=1}^S w_{ij}\alpha_{ij} |^2 - \lambda_i(\sum_{j=1}^S w_{ij}-1) \\
&=| Q_i w_i |^2 - \lambda_i 1_{S_i}^T w_i=w_i^T Q_i^T Q_i w_i - \lambda_i 1_{S_i}^T w_i
\end{align}

其中$1_{S_i}$长度为$S$,并且元素全为1的列向量;
接着,用$F_i$对$w_i$求偏导
\begin{align}
\frac{\partial F_i}{\partial w_i} &= Q_i^T Q_i w_i - \lambda_i 1_{S_i} \\
&=C_i w_i-\lambda_i 1_{S_i}=0 \\
\Rightarrow w_i &= \lambda_i C_i^{-1} 1_{S_i}
\end{align}

这里令$C_i=Q_i^T Q_i$。再将$w_i$带入式子$\sum_{j=1}^S w_{ij}=1_{S_i}^T w_i=1$,得到
\begin{align}
& 1_{S_i}^T (\lambda_i C_i^{-1} 1_{S_i})=1 \Rightarrow \lambda_i = (1_{S_i}^T C_i^{-1} 1_{S_i})^{-1}
\end{align}

另外需要声明的有两点。
第一点是我在很多文献中看到以下的的结论,尝试直接推导很是费劲,最终采用了上面矩阵的形式才得以证明。
$$w_{ij}=\frac{\sum_{k=1}^S (C_i^{-1})_{jk}}{\sum_{p=1}^S \sum_{q=1}^S (C_i^{-1})_{pq}}$$

第二点是矩阵$Q_i$不一定可逆,这个时候可以以下方法直接正则化,其中$I_S$是一个大小为$S \times S$的单位矩阵
$$C_i=C_i+rI_S$$

第三步
将所有的样本点映射到低维空间中,并重建高维空间中的线性关系
首先结合前两步中求出的系数$w_{ij}$,可以定义邻接矩阵$U=[u_{ij}]_{N \times N}$,假设样本点$x_i$的邻域样本点集合为$N(i)$,那么
$$
u_{ij}=
\begin{cases}
w_{ij}, &x_j \in N(i) \\
0, &x_j \notin N(i)
\end{cases}
$$

需要注意的是前面求得的系数$w_{ij}$是针对局部的,后面的矩阵$U$是针对全局的。

然后,样本点为$x_i$被映射到$y_i$,对应领域内的点$\alpha_{i1},…,\alpha_{ik}$被映射为$\beta_{i1},…,\beta_{ik}$。依据假设,$y_i$可被$\beta_{i1},…,\beta_{ik}$线性表出。同理可定义目标函数(重建误差最小化)
\begin{align}
\arg \min_Y & \sum_{i=1}^N | y_i-\sum_{j=1}^N u_{ij}y_j |_F^2 \\
s.t. & \sum_{i=1}^S y_i=0 \\
& \frac{1}{N}\sum_{i=1}^N y_i y_i^T=I_d
\end{align}

因为$\sum_{j=1}^N u_{ij}y_j$表示$YU^T$的第$i(<N)$列,故可将目标函数写成矩阵形式
\begin{align}
\sum_{i=1}^N | y_i-\sum_{j=1}^N u_{ij}y_j |_F^2 &=| Y-YU^T |_F^2 \\
&= tr \left((Y-YU^T)(Y-YU^T)^T \right) \\
& =tr \left(Y(I-U^T)(I-U)Y^T \right) \\
& =tr \left(YMY^T \right)
\end{align}

其中$M=(I-U^T)(I-U)$。最终,问题转化为求解矩阵$M$的最小$d+1$个特征向量$u_1,…,u_{d+1}$。舍去最小特征值对应的特征向量(原因未知),则对应的嵌入坐标为$Y=(u_2,…,u_{d+1})^T$。

需要的注意的是,优化需要满足两个条件:即数据中心化和正交化。这两个限制条件的作用在文献[3]中是这样解释的:

The imposing of constraints guarantees the essential uniqueness of the solution.

特别的,对于后一个条件在查到文献[3]中是这样解释的:第二个限制条件确保了重建误差对于不同坐标系的嵌入有同样的度量。虽然我能够理解需要一些限制条件以保证最终的解的唯一性,但是并没有仔细去求证上述两个条件真的能否保证解的唯一性。

对于第三步最终的优化方式依然可以采用拉格朗日乘数法,具体的优化推导在资料[3]中可见,不过我没有再去看,时间限制且到此为止了。

参考资料

[4] 基于全局统计与局部几何性质的数据降维算法研究_王雷