流形学习方法概述

用户7506105

发布于 2021-09-27 10:51:06

1.2K0

发布于 2021-09-27 10:51:06

文章被收录于专栏：碎片学习录

一般来讲，流形学习在目前来说的用途上可以作为数据降维、迁移学习等过程的一种比较好的方法，它借鉴了拓扑流形的概念，同时也是在机器学习/深度学习领域是较火且实用的一种数据预处理思想。

众所周知，如果是面对数据降维问题，肯定能第一反应出主成分分析(PCA), 而主成分分析一般是无监督的，且思想是通过一系列线性变换将高维空间的样本映射到低维上的，即

X' = Wx

其中W为线性变换矩阵，是通过样本数据学习到的，而这最重要的是PCA一般只是在线性降维场景较为多用，在非线性数据样本时具有很大的局限性。针对非线性样本，如果需要降维，则需要学习到一个非线性映射函数，即

X' = \Phi(x)

目前来说，这样的非线性映射函数可以由核PCA(类比带有核函数的支持向量机)、神经网络(黑箱技术)、和流形学习等，所以这也是流形学习思想应用的场景，接下来详述。

所谓流形，其实是高维空间中的几何结构，即空间中的点构成的集合，所以二维空间的流形是曲线，三维空间的流形是曲面(直线、平面是特殊的曲线和曲面)

在一般的流形学习算法中，并没有过多的用到微分几何，拓扑、微分流形等复杂的数学理论，因为很少涉及到空间动态变化情况(据称微分流形是数学系最难的课...)

将手写数字图片维度降至三维

(图片来源于网络)

那流形学习的具体思想是什么呢？

首先一个空间流形它在某个点的局部是可度量的，可以计算欧式距离的，即流形的局部空间和欧式空间同胚(同胚是拓扑学概念，可以理解为同构，即两个空间存在同构映射关系)。如果有一个很低维度的流形嵌入到高维流形中(嵌入可以举例为在三维空间中的曲线或散点，分布的复杂性肯定比曲面复杂)，但是这些嵌入到高维流形中的局部部分都是可以度量的(比如散点间距离，异面直线距离等)，因此如果能容易地在局部建立降维映射关系，然后推广到全局则是高维流形的一种思考方法。一般来说我们在实际场景的数据样本的维度是高维的，且分布比较复杂，但是局部是具有欧式空间性质的，所以降维场景可以采用流形学习的思想

同胚

接下来解释几种典型的流形学习方法

多维缩放算法MDS

要求在原始空间中样本之间的距离(可以看成是样本特征向量之间的欧式距离)在低维空间中得到保持

数学原理

假设N个样本在原始n维空间中的距离矩阵为D，D为对称矩阵

D = \begin{bmatrix} d_{11}& d_{12} & ... & d_{1N} \\ d_{21} & d_{22} & ... & d_{2N}\\ & ... & ... & ...\\ d_{N1} & d_{N2} & ... & d_{NN} \end{bmatrix}

其中

d_{ij} = ||\vec{x_i} - \vec{x_j}||

假设需要将该n维空间的样本X(维度为N*n)降维至n'空间的样本Z(维度为N*n')，且欧式距离需保持不变，所求的是样本Z，但是不知道n‘。

令矩阵B=

ZZ^T

,则B为

N*N

的矩阵,对应元素

b_{ij} = \vec{z_i}\cdot \vec{z_j}

(内积)，接下来就是比较繁多的数学推导了

因为距离需保持不变，则

d_{ij}^2 = ||\vec{x_i} - \vec{x_j}||^2 = ||\vec{z_i} - \vec{z_j}||^2

= ||\vec{z_i}||^2 + ||\vec{z_j}||^2 - 2\vec{z_i}^T \vec{z_j} = b_{ii} + b_{jj} - 2b_{ij}

由于降维前样本需要标准化中心化，所以这里的变换后的Z也是去除量纲的，即

\sum_{i=1}^N \vec{z_i} = \vec{0}

所以矩阵B的每行之和均为0，每列之和也都为0(提了相同的公因式后剩下的就是求和为0)。

所以有

\sum_{i=1}^N d_{ij}^2 = \sum_{i=1}^N b_{ii} + Nb_{jj} = tr(B) + Nb_{jj}

\sum_{j=1}^N d_{ij}^2 = \sum_{i=1}^N b_{jj} + Nb_{ii} = tr(B) + Nb_{ii}

\sum_{i=1}^N \sum_{j=1}^N d_{ij}^2 = \sum_{i=1}^N (tr(B) + Nb_{ii}) = 2Ntr(B)

tr(B)为矩阵B的迹，即对角线元素之和

综合上面的式子，代入

d_{ij}^2 = b_{ii} + b_{jj} - 2b_{ij}

可以得到

b_{ij} = \frac{\frac{\sum_{i=1}^N d_{ij}^2 + \sum_{j=1}^N d_{ij}^2}{N} - \frac{\sum_{i=1}^N \sum_{j=1}^N d_{ij}^2}{N^2} - d_{ij}^2}{2}

所以这样就求出来了内积矩阵B，但是如何求得矩阵Z呢，且注意B=

ZZ^T

,有什么想法吗？

很明显这个在线性代数或高等代数中是常见的题型(矩阵的合同分解)，即和单位矩阵合同，步骤是先算出B的特征值构造成对角矩阵后，计算每个特征值的特征向量，再做施密特正交等，最后单位化，最终就可计算出Z，

Z = V_{\lambda}\Lambda_{\lambda}^{1/2}

(V为对应

\lambda

的特征向量矩阵，

\Lambda

为特征值构成的对角矩阵，1/2次幂是对角元素开平方), Z的维度n'为B的非零特征根的个数,但在现实中为了有效降维，往往只需要降维后的矩阵与原始空间的距离尽可能相等而非严格相等，所以一般取前

n^*

个最大的特征值构成对角矩阵，其对应的特征向量构建成特征向量矩阵,即

Z = \hat{V}\hat{\Lambda}^{1/2}

算法过程

标准化原始样本数据集X(均值一定需要为0)
计算在原始n为空间的距离矩阵D
根据上面推导式算出矩阵B
对B进行合同分解，算出矩阵Z，Z即为高维空间的低维流形表现形式

多维缩放的中心思想是保证了缩放后的样本欧式距离尽可能不变

等度量映射Isomap

高维流形计算距离具有误导性，比如在三维球面，计算南极到赤道、中国上海到美国洛杉矶的距离是圆弧而不是直线距离(欧式距离)，所以高维流形中的直线距离在低维嵌入流形中是不可达的

等度量映射相较于多维缩放，其实本质就是距离矩阵D的计算方式的不同，多维缩放中的D就是纯粹的欧式距离，而这里等度量映射采用的即是图论中的测地线距离。

测地线距离

测地线距离可以看成是KNN和图论最短路径算法的结合，它首先基于的是高维流形在局部上和欧式空间是同胚的，然后对于高维流形中的每个散点基于欧式距离找出它在低维流形中的K个近邻点，然后不属于这K个近邻点集中的点就不和该散点存在连接(即距离为无穷)，如此一来对每个散点求K个近邻就可以构建出一个近邻连接图，之后利用图论或数据结构中的Dijkstra或Floyd算法计算任意两点的最短路径即为距离矩阵D的元素，这个路径长度称为点与点之间的测地线距离。

步骤

标准化原始数据集X
根据超参数近邻个数k构建近邻连接图或近邻连接矩阵
利用最短路径算法求得矩阵D
然后采用上式局部缩放的MDS算法算出低维矩阵Z

这两种算法都是需要已知了样本集不再改变的情况下的降维，如果后续有新样本进入预测推理且需要降维至n’维度时，则会比较麻烦，因为新样本改变了标准化后的分布，一种较为简单的方案就是已知的高维数据集X作为输入，然后通过这两种算法压缩后的低维数据集Z作为输出，构建多元回归或神经网络学习，然后新样本代入训练好的回归器得到新维度坐标，这也是目前来说最好的办法

局部线性嵌入算法LLE

与等度量映射Isomap保持距离不变不同，局部线性嵌入则是试图保持邻域样本之间的线性关系(在二维空间是保持共线性、三维空间是保持共面性)，假设样本点

\vec{x_i}

可以由它的邻域样本

\vec{x_j}

、

\vec{x_k}

、

\vec{x_l}

线性表示，即

\vec{x_i} = w_{ij}\vec{x_j} + w_{ik}\vec{x_k} + w_{il}\vec{x_l}

,局部线性嵌入则是希望这种线性表达式能在低维流形中保持不变

推导

首先基于每个样本

\vec{x_i}

找到近邻点下标集合

Q_i

(找近邻的方法可以参考KNN或等度量映射Isomap),然后求出样本

\vec{x_i}

与下标集合

Q_i

中元素之间的线性关系，具体过程类似最小二乘法求线性回归。

先定义重构误差,且让它最小化

Y = \min\limits_{\vec{w}} err = \sum_{i=1}^N ||\vec{x_i} - \sum_{j\in Q_i} w_{ij}\vec{x_j}||_2^2

因为样本是标准化后，所以权重向量

\vec{w}

有一个约束

\sum_{j\in Q_i} w_{ij} = 1,i=1,2,...,N

这个最优化问题可以用拉格朗日乘数法求偏导求解，其结果也可以类比最小二乘法，结果为

w_{ij} = \frac{\sum_{k\in Q_i} C_{jk}^{-1}}{\sum{l,s \in Q_i} C_{ls}^{-1}}

其中

C_{jk} = (\vec{x_i} - \vec{x_j})^T \vec{x_i} - \vec{x_k}

重点来了，这里就是需要保证

w_{ij}

在低维空间中不变，所以在低维空间中的最小化目标函数变为

Y' = \min\limits_{\vec{z_i}} err' = \sum_{i=1}^N ||\vec{z_i} - \sum_{j\in Q_i} w_{ij}\vec{z_j}||_2^2

仔细观察该式，写成矩阵式则有

Y' = \min\limits_{Z} tr(Z^T (I-W)^T(I-W) Z)

这里比较巧妙,利用了矩阵的二次型的知识

同样的这里的约束条件为

Z^T Z = I_{n'\times n'}

对于降维这里是固定权重向量

\vec{w}

而自变量是低维流形Z，所以一般都是谁未知谁做优化问题的自变量

这里的求解可以用到线性代数或高等代数的结论

设二次型

f(x_1,x_2,...,x_n) = f(X)= X^TAX

,在约束条件

X^TX

下的极大值为A的最大特征值，极小值为A的最小特征值，假设

\lambda_1

为A的最小特征值，

\lambda_n

为A的最大特征值，且利用X=PY将f(X)化为标准型f(Y) =

\lambda_1 y_1^2 + ... + \lambda_n y_n^2

,故

\lambda_1 <=\lambda_1(y_1^2 +... + y_n^2) <= \lambda_1 y_1^2 + ... + \lambda_n y_n^2 = X^TAX <= \lambda_n(y_1^2 +... + y_n^2) =\lambda_n

,所以有

\lambda_1 X^TX <=X^TAX <= \lambda_n X^TX

，由于

X^TX=1

，所以结论得证

所以这里就选用矩阵

(I-W)^T(I-W)

的最小n'个特征值对应的特征向量组成的矩阵即为降维后的矩阵Z

步骤

标准化原始数据集X
根据策略选取最近的k个元素的近邻集
根据公式计算权重向量

\vec{w}

构建矩阵

(I-W)^T(I-W)

对该矩阵进行特征值求解，n'个最小的特征值对应的特征向量即为低维流形Z

总结

流形学习还有其他的方法，比如拉普拉斯特征映射等，究其方法还是需要保证从高维到低维的某一个特征的值不变，然后不断优化求解，最终得到的低维流形即为所求，该方法没有像PCA那样需要建立线性关系，而只是基于某一个局部的度量进行的降维可以很好地解决非线性数据集的降维问题。另外在推导过程中可以发现，线性代数是多么地卓尔不群，所以基础真的很重要！！

其次，流形学习其实是对噪音数据非常敏感的，所以在数据集采样获取过程中也必须尽量保证对邻域的样本密集采样，否则一些线性关系或距离的鲁棒性都不高，如果出现了不同邻域的噪音数据，这个数据就极有可能是邻域间的边界，会导致实际降维效果往往没有预期的好，所以在进行流形降维前需要进行一定的异常缺失值的预处理过程，才能更大程度上取得更好的降维效果

参考资料

《机器学习》周志华老师著

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-09-15，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法