Question

1. 流形学习manifold learning是一类借鉴了拓扑流形概念的降维方法。

2. 流形是在局部和欧氏空间同胚的空间，它在局部具有欧氏空间的性质，能用欧氏距离进行距离计算。

   如果低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看起来非常复杂，但是在局部上仍然具有欧氏空间的性质。

3. 当维数被降低至二维或者三维时，能对数据进行可视化展示，因此流形学习也可用于可视化。

4. 流形学习若想取得很好的效果，则必须对邻域保持样本密采样，但这恰恰是高维情形下面临的重大障碍。因此流形学习方法在实践中的降维性能往往没有预期的好。

5. 流形学习对于噪音数据非常敏感。噪音数据可能出现在两个区域连接处：

   • 如果没有出现噪音，这两个区域是断路的。
   • 如果出现噪音，这两个区域是短路的。

4.1 多维缩放

4.1.1 多维缩放原理

1. 多维缩放Multiple Dimensional Scaling:MDS要求原始空间中样本之间的距离在低维空间中得到保持。

2. 假设 $ MathJax-Element-657 $ 个样本在原始空间中的距离矩阵为 $ MathJax-Element-268 $ :

   $ \mathbf D=\begin{bmatrix} d_{1,1}&d_{1,2}&\cdots&d_{1,N}\\ d_{2,1}&d_{2,2}&\cdots&d_{2,N}\\ \vdots&\vdots&\ddots&\vdots\\ d_{N,1}&d_{N,2}&\cdots&d_{N,N}\\ \end{bmatrix} $

   其中 $ MathJax-Element-269 $ 为样本 $ MathJax-Element-917 $ 到样本 $ MathJax-Element-856 $ 的距离。

   假设原始样本是在 $ MathJax-Element-897 $ 维空间，目标是获取样本在 $ MathJax-Element-387 $ 维空间且欧氏距离保持不变，其中满足 $ MathJax-Element-274 $ 。

   假设样本集在原空间的表示为 $ MathJax-Element-275 $ ，样本集在降维后空间的表示为 $ MathJax-Element-276 $ 。

   $ \mathbf X= \begin{bmatrix} \mathbf{\vec x}_1^T\\ \mathbf{\vec x}_2^T\\ \vdots\\ \mathbf{\vec x}_N^T\end{bmatrix} =\begin{bmatrix} x_{1,1}&x_{1,2}&\cdots&x_{1,n}\\ x_{2,1}&x_{2,2}&\cdots&x_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{N,1}&x_{N,2}&\cdots&x_{N,n}\\ \end{bmatrix}\\ \mathbf Z= \begin{bmatrix} \mathbf{\vec z}_1^T\\ \mathbf{\vec z}_2^T\\ \vdots\\ \mathbf{\vec z}_N^T\end{bmatrix} =\begin{bmatrix} z_{1,1}&z_{1,2}&\cdots&z_{1,n^\prime}\\ z_{2,1}&z_{2,2}&\cdots&z_{2,n^\prime}\\ \vdots&\vdots&\ddots&\vdots\\ z_{N,1}&z_{N,2}&\cdots&z_{N,n^\prime}\\ \end{bmatrix} $

   所求的正是 $ MathJax-Element-388 $ 矩阵，同时也不知道 $ MathJax-Element-387 $ 。

   很明显：并不是所有的低维空间都满足线性映射之后，样本点之间的欧氏距离保持不变。

3. 令 $ MathJax-Element-279 $ ，即 ：

   $ \mathbf B=\begin{bmatrix} b_{1,1}&b_{1,2}&\cdots&b_{1,N}\\ b_{2,1}&b_{2,2}&\cdots&b_{2,N}\\ \vdots&\vdots&\ddots&\vdots\\ b_{N,1}&b_{N,2}&\cdots&b_{N,N}\\ \end{bmatrix} $

   其中 $ MathJax-Element-280 $ 为降维后样本的内积。

   则根据降维前后样本的欧氏距离保持不变有：

   $ d_{ij}^{2}=||\mathbf{\vec z}_i-\mathbf{\vec z}_j||^{2}=||\mathbf{\vec z}_i||^{2}+||\mathbf{\vec z}_j||^{2}-2\mathbf{\vec z}_i^{T}\mathbf{\vec z}_j =b_{i,i}+b_{j,j}-2b_{i,j} $

   假设降维后的样本集 $ MathJax-Element-388 $ 被中心化，即 $ MathJax-Element-282 $ ，则矩阵 $ MathJax-Element-311 $ 的每行之和均为零，每列之和均为零。即：

   $ \sum_{i=1}^{N}b_{i,j}=0,j=1,2,\cdots,N\\ \sum_{j=1}^{N}b_{i,j}=0,i=1,2,\cdots,N $

   于是有：

   $ \sum_{i=1}^{N}d_{ij}^{2}=\sum_{i=1}^{N}b_{i,i}+Nb_{j,j}=tr(\mathbf B)+Nb_{j,j}\\ \sum_{j=1}^{N}d_{ij}^{2}=\sum_{j=1}^{N}b_{j,j}+Nb_{i,i}=tr(\mathbf B)+Nb_{i,i}\\ \sum_{i=1}^{N}\sum_{j=1}^{N}d_{ij}^{2}=\sum_{i=1}^{N}\left(tr(\mathbf B)+Nb_{i,i}\right)=2N tr(\mathbf B) $

   令：

   $ d_{i,\cdot}^{2}=\frac 1N \sum_{j=1}^{N}d_{ij}^{2}=\frac{tr(\mathbf B)}{N}+b_{i,i}\\ d_{j,\cdot}^{2}=\frac 1N \sum_{i=1}^{N}d_{ij}^{2}=\frac{tr(\mathbf B)}{N}+b_{j,j}\\ d_{\cdot,\cdot}^{2}=\frac {1}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}d_{ij}^{2}=\frac{2tr(\mathbf B)}{N} $

   代入 $ MathJax-Element-284 $ ，有：

   $ b_{i,j}=\frac{b_{i,i}+b_{j,j}-d_{ij}^{2}}{2} =\frac{d_{i,\cdot}^{2}+d_{j,\cdot}^{2}-d_{\cdot,\cdot}^{2}-d_{ij}^{2}}{2} $

   右式根据 $ MathJax-Element-285 $ 给出了 $ MathJax-Element-286 $ ，因此可以根据原始空间中的距离矩阵 $ MathJax-Element-287 $ 求出在降维后空间的内积矩阵 $ MathJax-Element-311 $ 。

   现在的问题是已知内积矩阵 $ MathJax-Element-289 $ ，如何求得矩阵 $ MathJax-Element-388 $ 。

4. 对矩阵 $ MathJax-Element-311 $ 做特征值分解，设 $ MathJax-Element-292 $ ，其中

   $ \Lambda=\begin{bmatrix}\lambda_1&0&0&\cdots&0\\ 0&\lambda_2&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\lambda_N \end {bmatrix} $

   为特征值构成的对角矩阵， $ MathJax-Element-293 $ ， $ MathJax-Element-294 $ 为特征向量矩阵。

   假定特征值中有 $ MathJax-Element-295 $ 个非零特征值，它们构成对角矩阵 $ MathJax-Element-296 $ 。令 $ MathJax-Element-297 $ 为对应的特征向量矩阵，则 $ MathJax-Element-298 $ 。

   此时有 $ MathJax-Element-299 $ ， $ MathJax-Element-300 $ 。

5. 在现实应用中为了有效降维，往往仅需要降维后的距离与原始空间中的距离尽可能相等，而不必严格相等。

   此时可以取 $ MathJax-Element-301 $ 个最大特征值构成对角矩阵 $ MathJax-Element-302 $ 。令 $ MathJax-Element-314 $ 表示对应的特征向量矩阵，则 $ MathJax-Element-315 $ 。

4.1.2 多维缩放算法

1. 多维缩放MDS算法：
   

   • 输入：

     • 距离矩阵 $ MathJax-Element-324 $ 。
     • 低维空间维数 $ MathJax-Element-387 $ 。

   • 输出：样本集在低维空间中的矩阵 $ MathJax-Element-388 $ 。

   • 算法步骤：

     • 根据下列式子计算 $ MathJax-Element-308 $ ：

       $ d_{i,\cdot}^{2}=\frac 1N \sum_{j=1}^{N}d_{ij}^{2},\quad d_{j,\cdot}^{2}=\frac 1N \sum_{i=1}^{N}d_{ij}^{2},\quad d_{\cdot,\cdot}^{2}=\frac {1}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}d_{ij}^{2} $

     • 根据下式计算矩阵 $ MathJax-Element-311 $ ： $ MathJax-Element-310 $ 。

     • 对矩阵 $ MathJax-Element-311 $ 进行特征值分解。

     • 取 $ MathJax-Element-312 $ 为 $ MathJax-Element-387 $ 个最大特征值所构成的对角矩阵， $ MathJax-Element-314 $ 表示对应的特征向量矩阵， 计算： $ MathJax-Element-315 $ 。

4.2 等度量映射

4.2.1 算法

1. 等度量映射 Isometric Mapping:Isomap的基本观点是：低维流形嵌入到高维空间后，直接在高维空间中计算直线距离具有误导性。因为在高维空间中的直线距离在低维嵌入流形上是不可达的。

2. 低维嵌入流形上，两点之间的距离是“测地线”geodesic距离。

   • 计算测地线距离的方法是：利用流形在局部上与欧氏空间同胚这个性质，对每个点基于欧氏距离找出它在低维流形上的近邻点， 然后就能建立一个近邻连接图。

     • 图中近邻点之间存在链接。
     • 图中非近邻点之间不存在链接。

   • 于是计算两点之间测地线距离的问题转变为计算近邻连接图上两点之间的最短路径问题（可以通过著名的Dijkstra算法或者Floyd算法）。

   • 在得到任意两点的距离之后，就可以通过MDS算法来获得样本点在低维空间中的坐标。

3. Isomap算法：
   

   • 输入：

     • 样本集 $ MathJax-Element-371 $
     • 近邻参数 $ MathJax-Element-395 $ 。
     • 低维空间维数 $ MathJax-Element-387 $ 。

   • 输出：样本集在低维空间中的矩阵 $ MathJax-Element-388 $ 。

   • 算法步骤：

     • 对每个样本点 $ MathJax-Element-917 $ ，计算它的 $ MathJax-Element-395 $ 近邻。同时将 $ MathJax-Element-917 $ 与 它的 $ MathJax-Element-395 $ 近邻的距离设置为欧氏距离，与其他点的距离设置为无穷大。
     • 调用最短路径算法计算任意两个样本点之间的距离，获得距离矩阵 $ MathJax-Element-324 $ 。
     • 调用多维缩放MDS算法，获得样本集在低维空间中的矩阵 $ MathJax-Element-388 $ 。

4.2.2 性质

1. Isomap算法有个很大的问题：对于新样本，如何将其映射到低维空间？

   常用的方法是：

   • 将训练样本的高维空间坐标作为输入，低维空间坐标作为输出，训练一个回归学习器。
   • 用这个回归学习器来对新样本的低维空间进行预测。

   这仅仅是一个权宜之计，但是目前并没有更好的办法。如果将新样本添加到样本集中，重新调用Isomap算法，则会得到一个新的低维空间。

   • 一方面计算量太大（每个新样本都要调用一次Isomap算法）。
   • 另一方面每次降维后的空间都在变化，不利于降维后的训练过程。

2. 对于近邻图的构建有两种常用方案：
   

   • 一种方法是指定近邻点个数，比如指定距离最近的 $ MathJax-Element-395 $ 个点为近邻点 。这样得到的近邻图称作 $ MathJax-Element-395 $ 近邻图。
   • 另一种方法是指定距离阈值 $ MathJax-Element-866 $ ，距离小于 $ MathJax-Element-866 $ 的点被认为是近邻点。这样得到的近邻图称作 $ MathJax-Element-866 $ 近邻图。

   这两种方案都有不足：
   

   • 如果近邻范围过大，则距离很远的点也被误认作近邻，这就是“短路”问题。
   • 如果近邻范围过小，则图中有些区域可能与其他区域不存在连接，这就是“断路”问题 。 短路问题和断路问题都会给后续的最短路径计算造成误导。

4.3 局部线性嵌入 LLE

1. 与Isomap试图保持邻域内样本之间的距离不同，局部线性嵌入Locally Linear Embedding:LLE试图保持邻域内样本之间的线性关系。

   这种线性保持在二维空间中就是保持共线性，三维空间中就是保持共面性。

2. 假定样本点 $ MathJax-Element-917 $ 的坐标能够通过它的邻域样本 $ MathJax-Element-332 $ 进行线性组合而重构出来，即： $ MathJax-Element-333 $ 。LLE算法希望这种关系在低维空间中得到保持。

4.3.1 重构系数求解

1. LLE首先为每个样本 $ MathJax-Element-917 $ 找到其近邻点下标集合 $ MathJax-Element-378 $ ， 然后计算基于 $ MathJax-Element-378 $ 中的样本点对 $ MathJax-Element-917 $ 进行线性重构的系数 $ MathJax-Element-770 $ 。

   定义样本集重构误差为（ $ MathJax-Element-383 $ 为 $ MathJax-Element-770 $ 的分量）：

   $ err=\sum_{i=1}^{N}||\mathbf{\vec x}_i-\sum_{j \in \mathbb Q_i}w_{i,j}\mathbf{\vec x}_j ||_2^{2} $

   目标是样本集重构误差最小，即：

   $ \min_{\mathbf{\vec w}_1,\mathbf{\vec w}_2,\cdots,\mathbf{\vec w}_N}\sum_{i=1}^{N}||\mathbf{\vec x}_i-\sum_{j \in \mathbb Q_i}w_{i,j}\mathbf{\vec x}_j ||_2^{2} $

2. 这样的解有无数个，对权重增加约束，进行归一化处理。即：

   $ \sum_{j \in \mathbb Q_i}w_{i,j}=1,i=1,2,\cdots,N $

   现在就是求解最优化问题：

   $ \min_{\mathbf{\vec w}_1,\mathbf{\vec w}_2,\cdots,\mathbf{\vec w}_N}\sum_{i=1}^{N}||\mathbf{\vec x}_i-\sum_{j \in \mathbb Q_i}w_{i,j}\mathbf{\vec x}_j ||_2^{2}\\ s.t.\quad \sum_{j \in \mathbb Q_i}w_{i,j}=1,i=1,2,\cdots,N $

   该最优化问题有解析解。令 $ MathJax-Element-341 $ ，则可以解出：

   $ w_{i,j}=\frac{\sum_{k\in \mathbb Q_i}C_{j,k}^{-1}}{\sum_{l,s\in \mathbb Q_i}C_{l,s}^{-1}} ,j \in \mathbb Q_i $

   其中：

   • $ MathJax-Element-342 $ 刻画了 $ MathJax-Element-343 $ 到 $ MathJax-Element-917 $ 的差向量，与 $ MathJax-Element-856 $ 到 $ MathJax-Element-917 $ 的差向量的内积。
   • $ MathJax-Element-383 $ 刻画了这些内积中，与 $ MathJax-Element-856 $ 相关的内积的比例。

   

4.3.2 低维空间保持

1. 求出了线性重构的系数 $ MathJax-Element-770 $ 之后， LLE在低维空间中保持 $ MathJax-Element-770 $ 不变。

   设 $ MathJax-Element-917 $ 对应的低维坐标 $ MathJax-Element-937 $ ，已知线性重构的系数 $ MathJax-Element-770 $ ，定义样本集在低维空间中重构误差为：

   $ err^{\prime}=\sum_{i=1}^{N}||\mathbf{\vec z}_i-\sum_{j \in \mathbb Q_i}w_{i,j}\mathbf{\vec z}_j ||_2^{2} $

   现在的问题是要求出 $ MathJax-Element-937 $ ，从而使得上式最小。即求解：

   $ \min_{\mathbf{\vec z}_1,\mathbf{\vec z}_2,\cdots,\mathbf{\vec z}_N} \sum_{i=1}^{N}||\mathbf{\vec z}_i-\sum_{j \in \mathbb Q_i}w_{i,j}\mathbf{\vec z}_j ||_2^{2} $

2. 令 $ MathJax-Element-355 $ ，其中 $ MathJax-Element-387 $ 为低维空间的维数（ $ MathJax-Element-897 $ 为原始样本所在的高维空间的维数）。令

   $ \mathbf W=\begin{bmatrix} w_{1,1}&w_{1,2}&\cdots&w_{1,N}\\ w_{2,1}&w_{2,2}&\cdots&w_{2,N}\\ \vdots&\vdots&\ddots&\vdots\\ w_{N,1}&w_{N,2}&\cdots&w_{N,N} \end{bmatrix} $

   定义 $ MathJax-Element-385 $ ，于是最优化问题可重写为： $ MathJax-Element-359 $ 。

   该最优化问题有无数个解。添加约束 $ MathJax-Element-360 $ ，于是最优化问题为：

   $ \min_{\mathbf Z}tr(\mathbf Z^T \mathbf M \mathbf Z) \\ s.t.\quad \mathbf Z^{T}\mathbf Z=\mathbf I_{n^\prime\times n^\prime} $

   该最优化问题可以通过特征值分解求解：选取 $ MathJax-Element-412 $ 最小的 $ MathJax-Element-387 $ 个特征值对应的特征向量组成的矩阵即为 $ MathJax-Element-388 $ 。

3. LLE 中出现了两个重构误差。

   • 第一个重构误差：为了在原始空间中求解线性重构的系数 $ MathJax-Element-770 $ 。目标是：基于 $ MathJax-Element-378 $ 中的样本点对 $ MathJax-Element-917 $ 进行线性重构，使得重构误差最小。
   • 第二个重构误差：为了求解样本集在低维空间中的表示 $ MathJax-Element-388 $ 。目标是：基于线性重构的系数 $ MathJax-Element-770 $ ，将 $ MathJax-Element-378 $ 中的样本点对 $ MathJax-Element-937 $ 进行线性重构，使得重构误差最小。

4.3.2 LLE 算法

1. LLE算法：
   

   • 输入：

     • 样本集 $ MathJax-Element-371 $ 。
     • 近邻参数 $ MathJax-Element-395 $ 。
     • 低维空间维数 $ MathJax-Element-387 $ 。

   • 输出：样本集在低维空间中的矩阵 $ MathJax-Element-388 $ 。

   • 算法步骤：

     • 对于样本集中的每个点 $ MathJax-Element-375 $ ，执行下列操作：

       • 确定 $ MathJax-Element-917 $ 的 $ MathJax-Element-395 $ 近邻，获得其近邻下标集合 $ MathJax-Element-378 $ 。

       • 对于 $ MathJax-Element-379 $ ， 根据下式计算 $ MathJax-Element-383 $ ：

         $ w_{i,j}=\frac{\sum_{k\in Q_i}C_{j,k}^{-1}}{\sum_{l,s\in \mathbb Q_i}C_{l,s}^{-1}}\\C_{j,k}=(\mathbf{\vec x}_i-\mathbf{\vec x}_j)^{T}(\mathbf{\vec x}_i-\mathbf{\vec x}_k) $

       • 对于 $ MathJax-Element-381 $ ， $ MathJax-Element-382 $

     • 根据 $ MathJax-Element-383 $ 构建矩阵 $ MathJax-Element-775 $ 。

     • 计算 $ MathJax-Element-385 $ 。

     • 对 $ MathJax-Element-412 $ 进行特征值分解，取其最小的 $ MathJax-Element-387 $ 个特征值对应的特征向量，即得到样本集在低维空间中的矩阵 $ MathJax-Element-388 $ 。