LLE算法推导

对于LLE算法，我们首先要确定邻域大小的选择，即我们需要多少个邻域样本来线性表示某个样本。假设这个值为k。我们可以通过和KNN一样的思想通过距离度量比如欧式距离来选择某样本的k个最近邻。

在寻找到某个样本的xix_ixi的k个最近邻之后我们就需要xix_ixi找到和这k个最近邻之间的线性关系，也就是要找到线性关系的权重系数。找线性关系，这显然是一个回归问题。假设我们有m个n维样本{x1,x2,...,xm}\{x_1,x_2,...,x_m\}{x1,x2,...,xm},我们可以用均方差作为回归问题的损失函数：即：

J(w)=∑i=1m∣∣xi−∑j∈Q(i)wijxj∣∣22J(w) = \sum\limits_{i=1}^{m}||x_i-\sum\limits_{j \in Q(i)}w_{ij}x_j||_2^2J(w)=i=1∑m∣∣xi−j∈Q(i)∑wijxj∣∣22

其中，Q(i)Q(i)Q(i)表示iii的k个近邻样本集合。一般我们也会对权重系数wij做归一化的限制，即权重系数需要满足

∑j∈Q(i)wij=1\sum\limits_{j \in Q(i)}w_{ij} = 1j∈Q(i)∑wij=1

也就是我们需要通过上面两个式子求出我们的权重系数。一般我们可以通过矩阵和拉格朗日子乘法来求解这个最优化问题。

对于第一个式子，我们先将其矩阵化：

J(W)=∑i=1m∣∣xi−∑j∈Q(i)wijxj∣∣22=∑i=1m∣∣∑j∈Q(i)wijxi−∑j∈Q(i)wijxj∣∣22=∑i=1m∣∣∑j∈Q(i)wij(xi−xj)∣∣22=∑i=1mWiTPiTPiWi\begin{align} J(W) & = \sum\limits_{i=1}^{m}||x_i-\sum\limits_{j \in Q(i)}w_{ij}x_j||_2^2 \\& = \sum\limits_{i=1}^{m}||\sum\limits_{j \in Q(i)}w_{ij}x_i-\sum\limits_{j \in Q(i)}w_{ij}x_j||_2^2 \\& = \sum\limits_{i=1}^{m}||\sum\limits_{j \in Q(i)}w_{ij}(x_i-x_j)||_2^2 \\& = \sum\limits_{i=1}^{m} W_i^TP_{i}^TP_iW_i \end{align} J(W)=i=1∑m∣∣xi−j∈Q(i)∑wijxj∣∣22=i=1∑m∣∣j∈Q(i)∑wijxi−j∈Q(i)∑wijxj∣∣22=i=1∑m∣∣j∈Q(i)∑wij(xi−xj)∣∣22=i=1∑mWiTPiTPiWi

其中Wi=(wi1,wi2,...wik)TW_i =(w_{i1}, w_{i2},...w_{ik})^TWi=(wi1,wi2,...wik)T，矩阵Pi=[xi−xj],j∈Q(i)P_i=[x_i-x_j], j \in Q(i)Pi=[xi−xj],j∈Q(i)。

令矩阵Zi=PiTPiZ_i=P_{i}^TP_iZi=PiTPi，则第一个式子进一步简化为J(W)=∑i=1mWiTZiWiJ(W) = \sum\limits_{i=1}^{m} W_i^TZ_iW_iJ(W)=i=1∑mWiTZiWi。对于第二个式子，我们可以矩阵化为：

∑j∈Q(i)wij=WiT1k=1\sum\limits_{j \in Q(i)}w_{ij} = W_i^T1_k = 1j∈Q(i)∑wij=WiT1k=1

其中1k1_k1k为k维全1向量。

现在我们将矩阵化的两个式子用拉格朗日子乘法合为一个优化目标：

L(W)=∑i=1mWiTZiWi+λ(WiT1k−1)L(W) = \sum\limits_{i=1}^{m} W_i^TZ_iW_i + \lambda(W_i^T1_k - 1) L(W)=i=1∑mWiTZiWi+λ(WiT1k−1)

对WWW求导并令其值为0，我们得到:

2ZiWi+λ1k=02Z_iW_i + \lambda1_k = 02ZiWi+λ1k=0

即

Wi=λ′Zi−11kW_i = \lambda'Z_i^{-1}1_kWi=λ′Zi−11k

其中λ′=−12λλ'=−\frac{1}{2}λλ′=−21λ为一个常数。利用WiT1k=1W_{i}^T1_k=1WiT1k=1,对WiW_iWi归一化，那么最终我们的权重系数WiW_iWi为：

Wi=Zi−11k1kTZi−11kW_i = \frac{Z_i^{-1}1_k}{1_k^TZ_i^{-1}1_k} Wi=1kTZi−11kZi−11k

现在我们得到了高维的权重系数，那么我们希望这些权重系数对应的线性关系在降维后的低维一样得到保持。假设我们的n维样本集{x1,x2,...,xm}\{x_1,x_2,...,x_m\}{x1,x2,...,xm}在低维的d维度对应投影为{y1,y2,...,ym}\{y_1,y_2,...,y_m\}{y1,y2,...,ym}，则我们希望保持线性关系，也就是希望对应的均方差损失函数最小，即最小化损失函数J(Y)J(Y)J(Y)如下：

J(Y)=∑i=1m∣∣yi−∑j=1kwijyj∣∣22J(Y) = \sum\limits_{i=1}^{m}||y_i-\sum\limits_{j=1}^{k}w_{ij}y_j||_2^2 J(Y)=i=1∑m∣∣yi−j=1∑kwijyj∣∣22

对于不在样本xix_ixi邻域内的样本xjx_jxj，我们令对应的wij=0w_{ij}=0wij=0，这样可以把www扩展到整个数据集的维度。则有

J(Y)=∑i=1m∣∣yi−∑j=1mwijyj∣∣22J(Y) = \sum\limits_{i=1}^{m}||y_i-\sum\limits_{j=1}^{m}w_{ij}y_j||_2^2 J(Y)=i=1∑m∣∣yi−j=1∑mwijyj∣∣22

可以看到这个式子和我们在高维的损失函数几乎相同，唯一的区别是高维的式子中，高维数据已知，目标是求最小值对应的权重系数WWW,而我们在低维是权重系数WWW已知，求对应的低维数据。注意这里WWW的维数为m×mm \times mm×m，其中对应的列为权重，列和为1。

为了得到标准化的低维数据，一般我们也会加入约束条件如下：

∑i=1myi=0;1m∑i=1myiyiT=I\sum\limits_{i=1}^{m}y_i =0;\;\; \frac{1}{m}\sum\limits_{i=1}^{m}y_iy_i^T = Ii=1∑myi=0;m1i=1∑myiyiT=I

首先我们将目标损失函数矩阵化：

J(Y)=∑i=1m∣∣yi−∑j=1mwijyj∣∣22=∑i=1m∣∣YIi−YWi∣∣22=tr(Y(I−W)(I−W)TYT)\begin{align} J(Y) & = \sum\limits_{i=1}^{m}||y_i-\sum\limits_{j=1}^{m}w_{ij}y_j||_2^2 \\& = \sum\limits_{i=1}^{m}||YI_i-YW_i||_2^2 \\& = tr(Y(I-W)(I-W)^TY^T) \end{align} J(Y)=i=1∑m∣∣yi−j=1∑mwijyj∣∣22=i=1∑m∣∣YIi−YWi∣∣22=tr(Y(I−W)(I−W)TYT)

其中Y=[y1,y2,...,ym]Y=[y_1,y_2,...,y_m]Y=[y1,y2,...,ym]，(6)式到(7)式利用的迹的性质

tr(AB)=tr(BA)tr(AB) =tr(BA)tr(AB)=tr(BA)

余下内容可见局部线性嵌入(LLE)原理总结