LLE

1. LLE 是什么

Locally linear embedding（LLE）[1] 是一种非线性降维算法，它能够使降维后的数据较好地保持原有 流形结构 。LLE可以说是流形学习方法最经典的工作之一。很多后续的流形学习、降维方法都与LLE有密切联系

一个形象的流形降维过程如下图。我们有一块卷起来的布，我们希望将其展开到一个二维平面，我们希望展开后的布能够在局部保持布结构的特征，其实也就是将其展开的过程，就想两个人将其拉开一样

2. LLE 的主要思想

LLE首先假设数据在较小的局部是线性的，也就是说，某一个数据可以由它邻域中的几个样本来线性表示。

• 比如我们有一个样本 $x_1$,我们在它的原始高维邻域里用 K-近邻思想 找到和它最近的三个样本 $x_2$, $x_3$, $x_4$. 然后我们假设 $x_1$ 可以由 $x_2$, $x_3$, $x_4$ 线性表示，即：

  

  • 其中，$w_{12}$，$w_{13}$，$w_{14}$ 为权重系数。
    

• 在我们通过LLE降维后，我们希望 $x_1$ 在低维空间对应的投影 $x_1^{\prime }$ 和 $x_2$, $x_3$, $x_4$ 对应的投影 $x_2^{\prime }$, $x_3^{\prime }$, $x_4^{\prime }$ 也尽量保持同样的线性关系，即：
  

• 也就是说，投影前后线性关系的权重系数 $w_{12}$，$w_{13}$，$w_{14}$ 是尽量不变或者最小改变的。

• 从上面可以看出，线性关系只在样本的附近起作用，离样本远的样本对局部的线性关系没有影响，因此降维的复杂度降低了很多。这句话的意思是： 如果表示原来高维空间中的点（假设高维空间中一共有 $D$ 个点），他们和每一个其他的点之间（其他 $D-1$ 个点）都存在 $w_{ij}$ 的表示关系，通过 LLE 降维的方法之后，使每个点只与周围的最近的 $k$ 个点之间存在线性表示关系，只能被周围的 $k$ 个点通过 $w_{ij}$ 来表示，这样的话，相当于计算量和维度都减少了很多。

3. LLE 算法推导过程

3.1 如何找到 k 个近邻

假设空间中一共有 $D$ 个点，现有一个点 $x_i$，对于整个空间中其他所有的点（$D-1$个）都进行距离运算；这里使用的距离是欧氏距离。然后，我们将这 $D-1$ 个点与 $x_i$ 距离最小的 $k$ 个点选出来，这就是 $k$ 近邻的思想

3.2 找 $x_i$ 与这 k 个近邻的线性关系

在前面我们说到了，我们如何将原来的高维数据降维到低维空间？或者说，“维度” 这个概念，指的到底是什么？

维度在这里就是由 $w_{ij}$ 的权重矩阵决定的，如果什么处理也不做，这个时候，一个 $x_i$ 就和整个空间中所有的点有关，要通过其他的每一个点来决定这个 $x_i$ 但是，假设我们只用最近的 $k$ 个点，就相当于我们只计算 $k$ 个 $w_{ij}$，然后利用求得的权重矩阵来对新的维度的数据进行生成，由于权重矩阵减小了，所以新的数据的维度也减小了。

---

现在来实际的推导步骤：

• 假设我们有 $m$ 个 $n$ 维样本 X = { x 1 , x 2 , . . . , x m } X=\{x_1,x_2,...,x_m\} X={x1​,x2​,...,xm​}（每个样本都有 $n$ 行），代表了整个高维空间中所有的样本点。
• 我们要找到 $x_i$ 与 $k$ 个近邻之间的线性关系，这显然是个回归问题，所以我们用回归问题常用的 均方误差 来作为损失函数 ：
  
  • 其中，$Q(i)$ 表示i的 $k$ 个近邻样本集合
  • 一般我们也会对权重系数 $w_{ij}$ 做归一化的限制，即权重系数需要满足所有系数相加为$1$ ：
    
  • 根据上面说的，我们只用最近 $k$ 个点来描述 $x_i$，即：所有不属于 $Q(i)$ 的点的 $w_{ij}=0$

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

3.3 $x_i$ 与 k 个近邻点的线性关系求解过程

首先对于 3.2 中第一个公式进行求解：

• 首先矩阵化并解析第一个公式：
  • $(1)$
    
  • $(2)$ 中：
    
    • 注意，这里的 $(x_i-x_j)$ 表示的是最后的矩阵
    • $W_i=(w_{i1},w_{i2},...w_{ik}{)}^T$，维度是 $k\times 1$。
  • $(3)$ 中:
    
    • $(x_i-x_j)W_i$ 看作 $A$ 矩阵的整体
    • 对一个矩阵求范数，其本质是求这个矩阵特征值的最大值，$||A|{|}_2=\sqrt{{\lambda }_{max}(A^{T}A)}\to ||A|{|}_2^2={\lambda }_{max}(A^{T}A)$
    • 因此整个公式就变成了对图中紫色波浪线的公式进行特征值分解然后求特征值的最大值；下面引入如何对一个矩阵进行特征值分解

这里打个断点 $\ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast$。

3.3.1 奇异值分解

3.3.1.1 特征值分解 （EVD）

在理角奇异值分解之前，需要先回顾一下特征值分解，如果矩阵 $A$ 是一个 $m\times m$ 的实对称矩阵（即 $A=A^T$），那么它可以根据 $A{q}_i={\lambda }_i{q}_i$, $q_i^T{q}_j=0(i\ne j)$ 被分解成如下的形式：

• 其中 $Q$ 为标准正交阵，即有 $Q{Q}^T=I$，
• $\Sigma$ 为对角矩阵，且上面的矩阵的维度均为 $m\times m$。
• ${\lambda }_i$ 称为特征值，
• $q_i$ 是 $Q$（特征矩阵）中的列向量，称为特征向量。
• $I$ 在这里表示单位阵，有时候也用 $E$ 表示单位阵

上面的特征值分解，对矩阵有着较高的要求，它需要被分解的矩阵 $A$ 为实对称矩阵，但是现实中，我们所遇到的问题一般不是实对称矩阵。那么当我们碰到一般性的矩阵，即有一个$m\times n$ 的矩阵 $A$ ，它是否能被分解成上面的形式呢？当然是可以的，这就是我们下面要讨论的内容。

3.3.1.2 奇异值分解（SVD）

有一个 $m\times n$ 的实数矩阵 $A$ ，我们想要把它分解成如下的形式:

• 其中 $U$ 和 $V$ 均为单位正交阵，即有$U{U}^T=I$和 $V{V}^T=I$，
• $U$ 称为左奇异矩阵，$V$ 称为右奇异矩阵，
• $\Sigma$ 仅在主对角线上有值，我们称它为奇异值，其它元素均为0。
• 上面矩阵的维度分别为 $U\in R^{m\times m}$, $\Sigma \in R^{m\times n}$, $V\in R^{n\times n}$。
• 一般 $\Sigma$ 有如下形式：
  

奇异值分解的各个矩阵形式如下：

• 对于奇异值分解，我们可以利用上面的图形象表示，图中方块的颜色表示值的大小，颜色越浅，值越大。对于奇异值矩阵 $\Sigma$，只有其主对角线有奇异值，其余均为 $0$。

---

正常求上面的$U,V,\Sigma$ 不便于求，我们可以利用如下性质

• PS: 需要指出的是，这里 $\Sigma {\Sigma }^T$与 ${\Sigma }^T\Sigma$ 在矩阵的角度上来讲，它们是不相等的，因为它们的维数不同 $\Sigma {\Sigma }^T\in R^{m\times m}$，而${\Sigma }^T\Sigma \in R^{n\times n}$ ，但是它们在主对角线的奇异值是相等的，即有
  
  因为主对角线上的值的个数永远都是 $m$ 和 $n$ 中较小的一个（奇异值矩阵非对称）

• 由于 $A{A}^T$和 $A^{T}A$ 也是对称矩阵（性质：一个矩阵乘以他的转置矩阵，得到的矩阵是对称矩阵），那么可以利用式（1-1）做特征值分解。

• 利用式（2-2）对 $A$ 做特征值分解，得到的特征矩阵即为 $U$；利用式（2-3）对 $A$ 特征值分解，得到的特征矩阵即为 $V$ ；对 $\Sigma {\Sigma }^T$或 ${\Sigma }^T\Sigma$ 中的特征值开方，可以得到所有的奇异值。

让我们回到 3.3 开头的第 $(4)$ 步 $\ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast \ast$

• 令$Z_i=(x_i-x_j)(x_i-x_j{)}^T,j\in Q(i)$ 进一步简化上述公式:
  
• 对于我们最早提出的权重的约束公式也进行矩阵化：
  
  • 其中 $W_i^T=w_{i1},w_{i2},...w_{ik}$，维度是 $1\times k$；$1_k$ 是维度为 $k\times 1$ 的全 $1$ 矩阵 $[1,1,1,...1{]}^T$（k个1）

---

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

• 对 $W_i$ 求导并且令其值为 $0$ 可得到下面公式：
  
• 即：
  
  • 其中 ${\lambda }^{\prime }=-\frac{1}{2\lambda }$为一个常数。利用 $W_i^T{1}_k=1$,对 $W_i$ 归一化，那么最终我们的权重系数 $W_i$ 为：
    

3.4 根据求得的先行参数 $W$ 求解低维点集 Y = { y 1 , y 2 , . . . , y m } Y=\{y_1,y_2,...,y_m\} Y={y1​,y2​,...,ym​}

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

• 可以看到这个式子和我们在高维的损失函数几乎相同，唯一的区别是高维的式子中，高维数据已知，目标是求最小值对应的权重系数W,而我们在低维是权重系数 $W$ 已知，求对应的低维数据。

• 注意，这里的 $W$ 已经是 $m\times m$ 维度，之前的 $W_i$ 是 $k\times 1$ 维度，对整个 $m$ 数据集求和之后：${\sum }_{i=1}^m$变成了 $k\times m$ ，即：对于整个数据集 X = { x 1 , x 2 , . . . , x m } X=\{x_1,x_2,...,x_m\} X={x1​,x2​,...,xm​}上的所有 $m$ 个点，每个点都有 $k$ 个近邻，和每个近邻之间都有 $1$ 个参数，所以参数的维度总共为 $W$ ：$k\times m$；又因为，在整个数据集上其实每两个点之间都有参数，但是我们 $k\times m$ 个参数只能表示每个点与近邻之间的关系，我们进一步扩展将参数的数量增加，使得每两个点之间都有参数，只不过，除了这 $k\times m$ 个参数之外，其他的参数都为 $0$，代表非近邻点与 $x_i$ 没有关系，通过这种操作，我们将整个参数的数量扩展到 $m\times m$ 维，其中有效的参数个数只有 $k\times m$ 个，其余的都是 $0$。

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

  • ${\sum }_{i=1}^m{y}_i=0$ 将矩阵进行中心化
  • $\frac{1}{m}{\sum }_{i=1}^m{y}_i{y}_i^T=I$ （单位协方差）

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

• 现在已经知道 $W$ 维度为 $m\times m$
• 现在的目的是通过 $W$ 来求算经过降维之后的点的集合 Y = { y 1 , y 2 , . . y m } Y=\{y_1,y_2,..y_m\} Y={y1​,y2​,..ym​}
• $Y$ 中所有的点维度是 $d$, $d<n$
• 因为前面对 $X$ 求权重矩阵 $W$ 的时候我们一共涉及了三个量 $w_{ij}$, $W_i$ 和 $W$，这里我们再回顾一下：
  • $w_{ij}$ 是点 $x_i$ 周围的 k个近邻分别到 $x_i$ 的权重，
  • $W_i$ 是对于一个 $x_i$ 周围 k个近邻的参数的矩阵，维度为：$k\times 1$；
  • $W$ 是对于整个 $X$ 集合所有 $m$ 个点的 k 近邻的参数的综合矩阵，维度为：$k\times m$；
  • 而后我们为了将这个权重矩阵 $W$ 的参数扩展成 $m\times m$ 维，我们就设定 $k\times m$ 个数据意外的那些权重都为 $0$
  • 所以最后 $W$ 的维度是 $m\times m$ 但是里面的每一个列向量只有 $k$ 个值不为 $0$
• 我们现在拿着 $W$ 来对 $J(y)$ 进行操作来得到我们想要求的 Y = { y 1 , y 2 , . . y m } Y=\{y_1,y_2,..y_m\} Y={y1​,y2​,..ym​}

这个时候可能有一个问题：为什么在下图第一个公式中求和的范围是 $i=1\to k$，求解 $Y$ 的时候，第二个式子的部分的求和范围就变成 $i=1\to m$ 了

• 其实这个问题也容易理解，我们在第一次求解的时候关注的是周围 $k$ 个近邻，而后我们将整个 $W$ 扩展到除了 $k$ 近邻以外的点，也就是整个数据集 $m$ 个点，但是这个时候仍然只有 $k$ 个参数值是有效的，因为就像我们上面说的，其他的点在与当前点 $y_i$ 做矩阵运算的时候乘到的参数 $w_{ij}$ 都是 $0$，所以并不冲突。

---

【现在开始正式推导 $J(Y)$】的求解过程

• $tr$ 是迹函数，对一个矩阵进行 $l2$ 范数运算可以与迹函数之间进行转化
• $W$ 维度是：$m\times m$；$W_i$ 维度是：$m\times 1$
• $I$ 的维度是： $m\times m$；$I_i$ 的维度是： $m\times 1$
• $Y$ 的维度：$d\times m$
• 约束函数矩阵化为：$Y{Y}^T$=$mI$
• 所以总的 优化目标函数为：
  

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

为什么 $M$ 的最小特征值为 $0$ 呢？

这是因为 $W^{T}e=e$, 得到 $|W^T-I|e=0$,由于 $e\ne 0$ ,所以只有 $W^T-I=0$, 即 $(I-W{)}^T=0$ ,两边同时左乘 $I-W$，即可得到$(I-W)(I-W{)}^{T}e=0e$,即 $M$ 的最小特征值为 $0$.

---