流形学习概述

Original: AI学习与实践平台 SIGAI 2019-06-23

广而告之

SIGAI-AI学习交流群的目标是为学习者提供一个AI技术交流与分享的平台。操作指引：关注本微信公众号，回复“芝麻开门”，即可收到入群二维码，扫码即可。

同时在本微信公众号中，回复“SIGAI”+日期，如“SIGAI0515”，即可获取本期文章的全文下载地址（仅供个人学习使用，未经允许，不得用于商业目的）。

数据降维问题

在很多应用中，数据的维数会很高。以图像数据为例，我们要识别32x32的手写数字图像，如果将像素按行或者列拼接起来形成向量，这个向量的维数是1024。高维的数据不仅给机器学习算法带来挑战，而且导致计算量大，此外还会面临维数灾难的问题（这一问题可以直观的理解成特征向量维数越高，机器学习算法的精度反而会降低）。人所能直观看到和理解的空间最多是3维的，为了数据的可视化，我们也需要将数据投影到低维空间中，因此就需要有数据降维这种算法来完成此任务。

例如，下图是将0-9这10个手写数字投影到3维空间中后的结果（来自SIGAI云端实验室）。从图中我们可以清晰的看到这些手写数字在3维空间中的分布，每一个类一般聚集在某一区域内。例如7位于空间的左上角，而6则位于右下角。

在机器学习算法中，数据降维算法是一个大家族，既有有监督学习的版本，也有无监督学习的版本；既有线性的降维算法，也有非线性的降维算法。

最经典的数据降维算法要数PCA（主成分分析），这是一种线性降维算法，而且是无监督的，它通过线性变换将样本投影到低维空间中：

y = Wx

其中，x是输入向量，为n为向量，W是m行n列的投影矩阵，将x左乘它，可以得到一个m维的结果向量y。一般情况下，m远小于n，这样就将一个向量变换成另外一个更低维的向量，从而完成数据降维。PCA的矩阵W是通过样本学习得到的，其依据是最小化重构误差。

PCA是一种线性降维技术，对于非线性数据具有局限性，而在实际应用中很多时候数据是非线性的。此时可以采用非线性降维技术，它们都通过一个非线性的映射函数将输入向量x映射成一个更低维的向量y：

问题的关键是这个非线性映射函数如何得到，一般来说，它要使得数据降维之后保持之前的某些结构信息。非线性降维算法的典型代表有核PCA（KPCA，核主成分分析），神经网络（如自动编码器），流形学习等。在本文中我们重点介绍流形学习算法。

什么是流形？

流形（manifold）是几何中的一个概念，它是高维空间中的几何结构，即空间中的点构成的集合。可以简单的将流形理解成二维空间的曲线，三维空间的曲面在更高维空间的推广。下图是三维空间中的一个流形，这是一个卷曲面：

2维空间中的曲线，3维空间中的曲线可以看做是2维和3维空间中的1维流形，因为曲线是1维的。而3维空间中的曲面可以看做是2维的流形，因为曲面是2维的。n维空间中的m维流形就是具有m维几何形状的一个子集，在这里，m小于n。

在一般的流形学习算法中，我们并没有过多的用到微分几何，拓扑等复杂的数学理论，因此在本文中我们不对流形的数学理论做过多的阐述。

什么是流形学习？

很多应用问题的数据在高维空间中的分布具有某种几何形状，即集中在某个低维的流形附近。对于前面所说的32x32的手写数字图像，数字7的图像在1024维空间中应该聚集在某一个形状的几何体周围（如带状区域，球面），其他的类别也是如此。

流形学习（manifold learning）假设数据在高维空间的分布位于某一更低维的流形上，基于这个假设来进行数据的分析。对于降维，要保证降维之后的数据同样满足与高维空间流形有关的几何约束关系。除此之外，流形学习还可以用实现聚类，分类以及回归算法。

假设有一个N维空间中的流形M，即M为N维欧氏空间的一个真子集：

流形学习降维算法要实现的是如下映射：

其中n<<N。即将N维空间中流形M上的点映射为n维空间中的点。下面介绍几种典型的流形降维算法，包括局部线性映射，拉普拉斯特征映射，局部保持投影，等距映射。

局部线性嵌入

局部线性嵌入[1]（简称LLE）的核心思想是每个样本点都可以由与它相邻的多个点的线性组合（体现了局部线性）来近似重构，这相当于用分段的线性面片近似代替复杂的几何形状，样本投影到低维空间之后要保持这种线性重构关系，即有相同的重构系数。

假设数据集由l个D维向量xi组成，它们分布在D维空间中的一个流形附近。每个数据点和它的邻居位于或者接近于流形的一个局部线性片段（平面，体现了线性，类似于微积分中的以直代曲的思想）上，即可以用邻居点的线性组合来重构，组合系数刻画了局部面片的几何特性：

权重wij为第j个数据点对第i个点的组合权重，这些点的线性组合被用来近似重构数据点i。权重系数通过最小化下面的重构误差确定：

在这里还加上了两个约束条件：每个点只由它的邻居来重构，如果xj不在xi的邻居集合里则权重值为0，这体现了局部性。另外限定权重矩阵的每一行元素之和为1，即：

这是一个带约束的优化问题，求解该问题可以得到权重系数。这一问题和主成分分析要求解的问题类似。可以证明，这个权重值对平移、旋转、缩放等几何变换具有不变性。

假设算法将向量从D维空间的x映射为d维空间的y。每个点在d维空间中的坐标由下面的最优化问题确定：

这里的权重和上一个优化问题的值相同，在前面已经得到。优化的目标是yi，这个优化问题等价于求解稀疏矩阵的特征值问题。得到y之后，即完成了从D维空间到d维空间的非线性降维。下面是整个过程的示意图：

下图为用LLE算法将手写数字图像投影到3维空间后的结果（来自SIGAI云端实验室）：

拉普拉斯特征映射

拉普拉斯特征映射[2]（简称LE）是基于图论的方法。它从样本点构造带权重的图，然后计算图的拉普拉斯矩，对该矩阵进行特征值分解得到投影变换矩阵。

图是离散数学和数据结构中的一个概念。一个图由节点（也称为顶点）和边构成，任意两个节点之间可能都有边进行连接。边可以带有值信息，称为权重，例如两点之间的距离。下图是一个简单的无向图：

上面这个图有5个顶点，5条边，每条边都有权重值，如顶点1和3之间的边的权重为3。图的边可以是有向的，也可以是无向的，前者称为有向图，后者称为无向图。我们可以将地图表示成一个图，每个地点是节点，如果两个地点之间有路连接，则有一条边。如果这条路是单行线，则边是有向的，否则是无向的。

一个图所有节点之间的边的权重构成的矩阵称为邻接矩阵。假设i和j为图的顶点，wij为边(i, j)的权重，由它构成的矩阵W称为邻接矩阵。显然，无向图的邻接矩阵是一个对称矩阵。如果两个顶点之间没有边，则邻接矩阵的元素为0。下面是上图中这个图的邻接矩阵：

节点的度定义为包含一个顶点的边的数量，对于有向图它还分为出度和入度，出度是指从一个顶点射出的边的数量，入度是连入一个节点的边的数量。由于边可以带有权重，因此可以定义带权重的度。定义节点i的带权重的度为与该节点相关的所有边的权重之和：

定义矩阵D为一个对角矩阵，其主对角线元素为每个顶点带权重的度：

其中n为图的顶点数。图的拉普拉斯矩阵定义为：

L = D -W

无向图的拉普拉斯矩阵是对称矩阵，另外可以证明它是半正定矩阵，因此所有特征值为非负实数。降维变换通过对拉普拉斯矩阵进行特征值分解得到。下面给出矩阵半正定的证明。对于任意的非0向量f，有：

因此拉普拉矩阵半正定。下面介绍通过拉普拉斯矩阵进行数据降维的具体做法。

假设有一批样本点x1,...,xk，它们是空间的向量，降维的目标是将它们变换为更低维的空间中的向量y1,...,yk，其中m<<l。在这里假设，其中M为嵌入空间中的一个流形。

算法为样本点构造加权图，图的节点是每一个样本点，边为每个节点与它的邻居节点之间的相似度，每个节点只和它的邻居有连接关系。

算法的第一步是构造图的邻接关系。如果样本点xi和样本点xj的距离很近，则为图的节点i和节点j建立一条边。判断两个样本点是否解接近的方法有两种。第一种是计算二者的欧氏距离，如果距离小于某一值则认为两个样本很接近：

其中是一个人工设定的阈值。第二种方法是使用近邻规则，如果节点i在节点j最近的n个邻居节点的集合中，或者节点j在节点i最近的n个邻居节点的集合中，则认为二者距离很近。

第二步是计算边的权重，在这里也有两种选择。第一种方法为如果节点i和节点j是联通的，则它们之间的边的权重为：

否则wij =0。其中t是一个人工设定的大于0的实数。第二种方式是如果节点i和节点j是联通的则它们之间的边的权重为1，否则为0。

第三步是特征映射。假设构造的图是联通的，即任何两个节点之间都有路径可达，如果不联通，则算法分别作用于每个联通分量上。根据前面构造的图计算它的拉普拉斯矩阵，然后求解如下广义特征值和特征向量问题：

由于是实对称矩阵半正定矩阵，因此特征值非负。假设f0,...,fk-1是这个广义特征值问题的解，它们按照特征值的大小升序排列，即：

去掉值为0的特征值，用剩下部分特征向量为行来构造投影矩阵，将向量投影到以它们为基的空间中。下图是拉普拉斯特征映射对三维数据进行降维的一个例子：

上图中左侧为三维空间中的样本分布，右图为降维后的结果。这种变换起到的效果大致上相当于把三维空间中的曲面拉平之后铺到二维平面上。

局部保持投影

局部保持投影（简称LPP）[3]思路和拉普拉斯特征映射类似，也是一种基于图论的方法。

假设有样本集x1,...,xm，它们是空间中的向量。这里的目标是寻找一个变换矩阵A，将这些样本点映射到更低维的空间，得到向量y1,...,ym，使得yi能够代表xi，其中l<<n：

假设，其中M是空间中的一个流形。

算法的第一步是根据样本构造图，这和拉普拉斯特征映射的做法相同，在这里不再重复介绍。

第二步是特征映射，计算如下广义特征向量问题：

矩阵L和D的定义与计算方式和上一节相同，矩阵X是将样本按列排列形成的。假设上面广义特征向量问题的解为a0,...,al-1，它们对应的特征值满足：

要寻找的降维变换矩阵为：

这样yi是一个l维的向量，A是一个nxl的矩阵。对向量左乘矩阵A的转置即可完成数据的降维。

等距映射

等距映射（Isomap）[4]使用了微分几何中测地线的思想，它希望数据在向低维空间映射之后能够保持流形上的测地线距离。直观来看，就是将数据投影到低维空间之前，保持数据点之间的相对远近关系。

测地线是微分几何中的一个概念，源自于大地测量学，是地球上任意两点之间在球面上的最短路径。在三维空间中两点之间的最短距离是它们之间线段的长度，但如果要沿着地球表面走，最短距离就是测地线的长度，因为我们不能从地球内部穿过去。这里的测地线就是球面上两点之间大圆上劣弧的长度，高中的立体几何中我们就知道了这一结论。坐过长途国际航班的同学可能都知道，我们要从中国去美国，飞机飞的并不是一条直线，而是一条弧线，这大致上就是测地线（事实上不是严格的测地线，因为还要考虑出故障时有备降点等复杂因素）：

等距映射算法计算任意两个样本之间的测地距离，然后根据这个距离构造距离矩阵。最后通过距离矩阵求解优化问题完成数据的降维，降维之后的数据保留了原始数据点之间的距离信息。

在这里测地线距离通过图构造，是图的两个节点之间的最短距离。算法的第一步构造样本集的邻居图，这和前面介绍的两种方法相同。如果两个数据点之间的距离小于指定阈值或者其中一个节点在另外一个节点的邻居集合中，则两个节点是联通的。假设有N个样本，则邻居图有N个节点。邻居图的节点i和j之间边的权重为它们之间的距离wij，距离的计算公式可以有多种选择。

第二步计算图中任意两点之间的最短路径长度，可以通过经典的Dijkstra算法实现。假设最短路径长度为，由它构造如下矩阵：

其元素是所有节点对之间的最短路径长度。算法的第三步根据矩阵DG构造d维投影，这通过求解如下最优化问题实现：

优化的目标是，降维之前任意两点间的最短距离，与降维之后这两点间的最短距离，要尽可能接近。这个问题的解yi即为降维之后的向量。这个目标函数的意义是向量降维之后任意两点之间的距离要尽量的接近在原始空间中这两点之间的最短路径长度，因此可以认为降维尽量保留了数据点之间的测地距离信息。我们可以形象的把这个过程理解成将3D的地球仪投影到2D的平面地图上：

投影之前，美国离中国的距离远，泰国离中国的距离近，投影之后要保持这种距离关系：

实际应用

从2000年之后，在很长一段时间内，流形学习是机器学习领域里的一个研究热点，它在理论上非常优美，也比较完善，但遗憾的是在实际应用中很少被使用。下面我们以它在人脸识别中的应用为例来说明[5]：

与使用PCA和LDA的算法类似，在这里将人脸图像按照像素拼接起来形成一个高维的向量，然后用拉普拉斯特征映射这样的流形降维算法将它们降到低维空间中，然后进行分类。关键的一步是这个降维过程。

参考文献

[1] Roweis, Sam T and Saul, Lawrence K. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500). 2000: 2323-2326.

[2] Belkin, Mikhail and Niyogi, Partha. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 15(6). 2003:1373-1396.

[3] He Xiaofei and Niyogi, Partha. Locality preserving projections. NIPS. 2003:234-241.

[4] Tenenbaum, Joshua B and De Silva, Vin and Langford, John C. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500). 2000: 2319-2323.

[5] He, Xiaofei, et al. Face recognition using Laplacianfaces. Pattern Analysis and Machine Intelligence, IEEE Transactions on 27.3 (2005): 328-340.

▲向上滑动查看更多推荐文章

科普类

【‍获取码】SIGAI0413

机器学习——波澜壮阔四十年

【获取码】SIGAI0620

理解计算：从√2到AlphaGo ——第1季从√2谈起

【获取码】SIGAI0704

理解计算：从√2到AlphaGo ——第2季神经计算的历史背景

【获取码】SIGAI0713

理解计算：从√2到AlphaGo ——第3季神经计算的数学模型

数学类