【机器学习基础】第四十二课:[降维与度量学习]流形学习

流形学习,等度量映射(Isomap),局部线性嵌入(LLE)

Posted by x-jeff on January 19, 2023

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.流形学习

流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间,换言之,它在局部具有欧氏空间的性质,能用欧氏距离来进行距离计算。这给降维方法带来了很大的启发:若低维流形嵌入到高维空间中,则数据样本在高维空间的分布虽然看上去非常复杂,但在局部上仍具有欧氏空间的性质,因此,可以容易地在局部建立降维映射关系,然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时,能对数据进行可视化展示,因此流形学习也可被用于可视化。本节介绍两种著名的流形学习方法。

2.等度量映射

等度量映射(Isometric Mapping,简称Isomap)的基本出发点,是认为低维流形嵌入到高维空间之后,直接在高维空间中计算直线距离具有误导性,因为高维空间中的直线距离在低维嵌入流形上是不可达的。如图10.7(a)所示,低维嵌入流形上两点间的距离是“测地线”(geodesic)距离:想象一只虫子从一点爬到另一点,如果它不能脱离曲面行走,那么图10.7(a)中的红色曲线是距离最短的路径,即S曲面上的测地线,测地线距离是两点之间的本真距离。显然,直接在高维空间中计算直线距离是不恰当的。

那么,如何计算测地线距离呢?这时我们可利用流形在局部上与欧氏空间同胚这个性质,对每个点基于欧氏距离找出其近邻点,然后就能建立一个近邻连接图,图中近邻点之间存在连接,而非近邻点之间不存在连接,于是,计算两点之间测地线距离的问题,就转变为计算近邻连接图上两点之间的最短路径问题。从图10.7(b)可看出,基于近邻距离逼近能获得低维流形上测地线距离很好的近似。

在近邻连接图上计算两点间的最短路径,可采用著名的Dijkstra算法或Floyd算法,在得到任意两点的距离之后,就可通过MDS方法来获得样本点在低维空间中的坐标。图10.8给出了Isomap算法描述。

需注意的是,Isomap仅是得到了训练样本在低维空间的坐标,对于新样本,如何将其映射到低维空间呢?这个问题的常用解决方案,是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出,训练一个回归学习器来对新样本的低维空间坐标进行预测。这显然仅是一个权宜之计,但目前似乎并没有更好的办法。

对近邻图的构建通常有两种做法,一种是指定近邻点个数,例如欧氏距离最近的$k$个点为近邻点,这样得到的近邻图称为$k$近邻图;另一种是指定距离阈值$\epsilon$,距离小于$\epsilon$的点被认为是近邻点,这样得到的近邻图称为$\epsilon$近邻图。两种方式均有不足,例如若近邻范围指定得较大,则距离很远的点可能被误认为近邻,这样就出现“短路”问题;近邻范围指定得较小,则图中有些区域可能与其他区域不存在连接,这样就出现“断路”问题,短路与断路都会给后续的最短路径计算造成误导。

3.局部线性嵌入

与Isomap试图保持近邻样本之间的距离不同,局部线性嵌入(Locally Linear Embedding,简称LLE)试图保持邻域内样本之间的线性关系。如图10.9所示,假定样本点$\mathbf{x}_i$的坐标能通过它的邻域样本$\mathbf{x}_j,\mathbf{x}_k,\mathbf{x}_l$的坐标通过线性组合而重构出来,即

\[\mathbf{x}_i=w_{ij}\mathbf{x}_j+w_{ik}\mathbf{x}_k+w_{il}\mathbf{x}_l \tag{10.26}\]

LLE希望式(10.26)的关系在低维空间中得以保持。

LLE先为每个样本$\mathbf{x}_i$找到其近邻下标集合$Q_i$,然后计算出基于$Q_i$中的样本点对$\mathbf{x}_i$进行线性重构的系数$\mathbf{w}_i$:

\[\begin{align*} &\min \limits_{\mathbf{w}_1,\mathbf{w}_2,...,\mathbf{w}_m} \sum^m_{i=1} \left|\left| \mathbf{x}_i - \sum_{j\in Q_i} w_{ij} \mathbf{x}_j \right|\right| _2 ^2 \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} \quad \quad s.t.& \sum_{j\in Q_i} w_{ij}=1 \\ \end{array} \end{align*} \tag{10.27}\]

其中$\mathbf{x}_i$和$\mathbf{x}_j$均为已知,令$C_{jk}=(\mathbf{x}_i-\mathbf{x}_j)^T(\mathbf{x}_i-\mathbf{x}_k)$,$w_{ij}$有闭式解

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

LLE在低维空间中保持$\mathbf{w}_i$不变,于是$\mathbf{x}_i$对应的低维空间坐标$\mathbf{z}_i$可通过下式求解:

\[\min \limits_{\mathbf{z}_1,\mathbf{z}_2,...,\mathbf{z}_m} \sum^m_{i=1} \left|\left| \mathbf{z}_i - \sum_{j\in Q_i} w_{ij} \mathbf{z}_j \right|\right| _2 ^2 \tag{10.29}\]

式(10.27)与(10.29)的优化目标同形,唯一的区别是式(10.27)中需确定的是$\mathbf{w}_i$,而式(10.29)中需确定的是$\mathbf{x}_i$对应的低维空间坐标$\mathbf{z}_i$。

令$\mathbf{Z}=(\mathbf{z}_1,\mathbf{z}_2,…,\mathbf{z}_m)\in \mathbb{R}^{d’ \times m}$,$(\mathbf{W})_{ij}=w_{ij}$,

\[\mathbf{M}=(\mathbf{I}-\mathbf{W})^T(\mathbf{I}-\mathbf{W}) \tag{10.30}\]

则式(10.29)可重写为

\[\begin{align*} &\min \limits_{\mathbf{Z}} \text{tr}(\mathbf{ZMZ^T}) \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.& \mathbf{ZZ}^T=\mathbf{I} \\ \end{array} \end{align*} \tag{10.31}\]

式(10.31)可通过特征值分解求解:$\mathbf{M}$最小的$d’$个特征值对应的特征向量组成的矩阵即为$\mathbf{Z}^T$。

此处和后续推导不太一样,详见第3.2部分。

LLE的算法描述如图10.10所示。算法第4行显示出:对于不在样本$\mathbf{x}_i$邻域区域的样本$\mathbf{x}_j$,无论其如何变化都对$\mathbf{x}_i$和$\mathbf{z}_i$没有任何影响;这种将变动限制在局部的思想在许多地方都有用。

3.1.式(10.28)的推导

若令

\[\mathbf{x}_i \in \mathbb{R}^{d \times 1}\] \[Q_i=\{q_i^1, q_i^2,...,q_i^n \}\]

则式(10.27)的目标函数可以进行如下恒等变形:

\[\begin{align} \sum^m_{i=1} \left|\left| \mathbf{x}_i - \sum_{j\in Q_i} w_{ij} \mathbf{x}_j \right|\right| _2 ^2 &= \sum^m_{i=1} \left|\left| \sum_{j\in Q_i} w_{ij} \mathbf{x}_i - \sum_{j\in Q_i} w_{ij} \mathbf{x}_j \right|\right| _2 ^2 \\&= \sum^m_{i=1} \left|\left| \sum_{j\in Q_i} w_{ij} (\mathbf{x}_i - \mathbf{x}_j )\right|\right| _2 ^2 \\&= \sum^m_{i=1} \parallel \mathbf{X}_i \mathbf{w}_i \parallel _2^2 \\&= \sum_{i=1}^m \mathbf{w}_i^T \mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i \end{align}\]

其中,

\[\mathbf{w}_i = \begin{bmatrix} w_{iq_i^1} \\ w_{iq_i^2} \\ \vdots \\ w_{iq_i^n} \end{bmatrix} \in \mathbb{R}^{n\times 1}\] \[\mathbf{X}_i = \begin{bmatrix} \mathbf{x}_i - \mathbf{x}_{q_i^1} & \mathbf{x}_i - \mathbf{x}_{q_i^2} & \cdots & \mathbf{x}_i - \mathbf{x}_{q_i^n} \\ \end{bmatrix} \in \mathbb{R}^{d\times n}\]

同理,式(10.27)的约束条件也可以进行如下恒等变形:

\[\sum_{j\in Q_i} w_{ij}=\mathbf{w}_i^T \mathbf{I} = 1\]

其中,

\[\mathbf{I} = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ \end{bmatrix} \in \mathbb{R}^{n\times 1}\]

所以,式(10.27)可以重写为:

\[\begin{align*} &\min \limits_{\mathbf{w}_1,\mathbf{w}_2,...,\mathbf{w}_m} \sum^m_{i=1} \mathbf{w}_i^T \mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} \quad \quad s.t.& \mathbf{w}_i^T \mathbf{I} = 1 \\ \end{array} \end{align*}\]

显然,此问题为带约束的优化问题,因此可以考虑使用拉格朗日乘子法来进行求解。由拉格朗日乘子法可得此优化问题的拉格朗日函数为:

\[L(\mathbf{w}_1,\mathbf{w}_2,...,\mathbf{w}_m,\lambda)=\sum_{i=1}^m \mathbf{w}_i^T \mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i + \lambda (\mathbf{w}_i^T \mathbf{I} - 1)\]

对拉格朗日函数关于$\mathbf{w}_i$求偏导并令其等于0可得:

\[\begin{align} \frac{\partial L(\mathbf{w}_1,\mathbf{w}_2,...,\mathbf{w}_m,\lambda)}{\partial \mathbf{w}_i} &= \frac{\partial [ \sum_{i=1}^m \mathbf{w}_i^T \mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i + \lambda (\mathbf{w}_i^T \mathbf{I} - 1) ]}{ \partial \mathbf{w}_i} \\&=\frac{\partial [ \mathbf{w}_i^T \mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i + \lambda (\mathbf{w}_i^T \mathbf{I} - 1) ]}{ \partial \mathbf{w}_i} \\&= 0 \end{align}\]

又由矩阵微分公式

\[\frac{\partial \mathbf{x}^T \mathbf{Bx}}{\partial \mathbf{x}}=(\mathbf{B}+\mathbf{B}^T)\mathbf{x}\] \[\frac{\partial \mathbf{x}^T \mathbf{a}}{\partial \mathbf{x}}=\mathbf{a}\]

可得

\[\frac{\partial [ \mathbf{w}_i^T \mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i + \lambda (\mathbf{w}_i^T \mathbf{I} - 1) ]}{ \partial \mathbf{w}_i} = 2\mathbf{X}_i^T\mathbf{X}_i\mathbf{w}_i+\lambda \mathbf{I}=0\] \[\mathbf{X}_i^T \mathbf{X}_i \mathbf{w}_i=-\frac{1}{2}\lambda \mathbf{I}\]

若$\mathbf{X}_i^T \mathbf{X}_i$可逆,则

\[\mathbf{w}_i=-\frac{1}{2}\lambda (\mathbf{X}_i^T \mathbf{X}_i)^{-1} \mathbf{I}\]

又因为$\mathbf{w}_i^T \mathbf{I}= \mathbf{I}^T \mathbf{w}_i = 1$,则上式两边同时左乘$\mathbf{I}^T$可得

\[\mathbf{I}^T \mathbf{w}_i=-\frac{1}{2}\lambda \mathbf{I}^T (\mathbf{X}_i^T \mathbf{X}_i)^{-1} \mathbf{I} = 1\] \[-\frac{1}{2} \lambda = \frac{1}{\mathbf{I}^T (\mathbf{X}_i^T \mathbf{X}_i)^{-1} \mathbf{I}}\]

将其代回$\mathbf{w}_i=-\frac{1}{2}\lambda (\mathbf{X}_i^T \mathbf{X}_i)^{-1} \mathbf{I}$即可解得

\[\mathbf{w}_i = \frac{(\mathbf{X}_i^T \mathbf{X}_i)^{-1} \mathbf{I}}{\mathbf{I}^T (\mathbf{X}_i^T \mathbf{X}_i)^{-1} \mathbf{I}}\]

若令矩阵$(\mathbf{X}_i^T \mathbf{X}_i)^{-1}$第$j$行第$k$列的元素为$C_{jk}^{-1}$,则

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

此即为公式(10.28)。显然,若$\mathbf{X}_i^T \mathbf{X}_i$可逆,此优化问题即为凸优化问题,且此时用拉格朗日乘子法求得的$\mathbf{w}_i$为全局最优解。

3.2.式(10.31)的推导

\[\begin{align} \min \limits_{\mathbf{Z}} \sum_{i=1}^m \parallel \mathbf{z}_i - \sum_{j \in Q_i} w_{ij} \mathbf{z}_j \parallel _2^2 &= \sum_{i=1}^m \parallel \mathbf{ZI}_i-\mathbf{ZW}_i \parallel_2^2 \\&= \sum_{i=1}^m \parallel \mathbf{Z} (\mathbf{I}_i-\mathbf{W}_i) \parallel_2^2 \\&= \sum_{i=1}^m (\mathbf{Z} (\mathbf{I}_i-\mathbf{W}_i))^T \mathbf{Z} (\mathbf{I}_i-\mathbf{W}_i) \\&= \sum_{i=1}^m (\mathbf{I}_i-\mathbf{W}_i)^T \mathbf{Z}^T \mathbf{Z} (\mathbf{I}_i-\mathbf{W}_i) \\&= \text{tr} ( (\mathbf{I}-\mathbf{W})^T \mathbf{Z}^T \mathbf{Z} (\mathbf{I}-\mathbf{W}) ) \\&= \text{tr} ( \mathbf{Z} (\mathbf{I}-\mathbf{W})(\mathbf{I}-\mathbf{W})^T \mathbf{Z}^T ) \\&= \text{tr} (\mathbf{ZMZ}^T) \\ \end{align}\]

其中,

\[\mathbf{Z} = \begin{bmatrix} \mathbf{z}_1 & \mathbf{z}_2 & \cdots & \mathbf{z}_m \end{bmatrix} = \begin{bmatrix} z_{11} & z_{12} & \cdots & z_{1m} \\ z_{21} & z_{22} & \cdots & z_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ z_{d'1} & z_{d'2} & \cdots & z_{d'm} \end{bmatrix} \in \mathbb{R}^{d'\times m}\]

每一列为一个样本,一共有$m$个样本。此外还有,

\[\mathbf{I}= \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ \end{bmatrix} \in \mathbb{R}^{m\times m}, \mathbf{I}_i \in \mathbb{R}^{m\times 1}\] \[\mathbf{W}=\begin{bmatrix} w_{11} & w_{21} & \cdots & w_{m1} \\ w_{12} & w_{22} & \cdots & w_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ w_{m1} & w_{2m} & \cdots & w_{mm} \\ \end{bmatrix} \in \mathbb{R}^{m\times m}, \mathbf{W}_i \in \mathbb{R}^{m \times 1}\]

$\mathbf{W}$其实是个稀疏矩阵。举个例子,假设$\mathbf{z}_1=w_{12}\mathbf{z}_2+w_{13}\mathbf{z}_3+w_{14}\mathbf{z}_4$,那么其对应的:

\[\mathbf{W}_1 = \begin{bmatrix} 0 \\ w_{12} \\ w_{13} \\ w_{14} \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} \in \mathbb{R}^{m\times 1}\]

关于矩阵的迹,有:

\[\text{tr} (AA^T) = \text{tr} (A^TA)\]

根据推导,

\[\mathbf{M}=(\mathbf{I}-\mathbf{W})(\mathbf{I}-\mathbf{W})^T\]

个人理解:式(10.30)应该以此处的为准,原书应该是写错了。

约束条件$\mathbf{Z} \mathbf{Z}^T=\mathbf{I}$是为了得到标准化(标准正交空间)的低维数据(此处的$\mathbf{I}$应该是$d’ \times d’$的单位矩阵)。

拉格朗日乘子法求$\mathbf{Z}$:

\[L(\mathbf{Z},\lambda)=\mathbf{ZMZ}^T + \lambda (\mathbf{Z}\mathbf{Z}^T - \mathbf{I})\] \[\frac{\partial L(\mathbf{Z},\lambda)}{\partial \mathbf{Z}}=2 \mathbf{MZ}^T+2\lambda \mathbf{Z}^T=0\]

从而得到,

\[\mathbf{MZ}^T=-\lambda \mathbf{Z}^T = \lambda' \mathbf{Z}^T\]

因此,$\mathbf{Z}^T$是矩阵$M$的特征向量组成的矩阵。把$\mathbf{MZ}^T=-\lambda \mathbf{Z}^T $代入:

\[\begin{align} L(\mathbf{Z},\lambda) &= \mathbf{ZMZ}^T + \lambda (\mathbf{Z}\mathbf{Z}^T - \mathbf{I}) \\&= -\lambda \mathbf{I} \\&= \lambda' \mathbf{I} \end{align}\]

若要求$L(\mathbf{Z},\lambda)$最小,则$\lambda ^{‘}$最小,即取$\mathbf{M}$的最小特征值。

4.参考资料

  1. 南瓜书PumpkinBook
  2. LLE(局部线性嵌入)课件