Created by potrace 1.13, written by Peter Selinger 2001-2015

流形学习

等度量映射(Isomap)

下图一个类似瑞士卷样的点集,想象一个虫子从瑞士卷的一个点走到另一个点,可能需要围绕瑞士卷走很长的距离(图中实线).但是如果用欧式距离测量两点间却会很短(图中虚线).想像一下,如果使用MDS或是PCA进行线性降维,肯定会破坏数据的流形结构.

image

为了在降维后保留原数据的流形结构,Isomap算法不是计算的直线距离,而是计算路径,但是为了防止图中的情况发生,Isomap算法先计算距离较近的两点之间的距离,并且将距离较远的两点距离设置为无穷大.然后再根据得到的距离使用最小路径算法,如著名的Dijkstra算法或Floyd算法,得到最短的路径,这样的话得到的距离就与图中实线接近.

最后再使用MDS进行降维.这样降维会按照密集分布的流形结构展开.

步骤1:计算数据两两间的距离.将临近点的距离设置为欧式距离;将其他点的距离设置为无穷大.
步骤2:根据步骤1得到的距离,使用最短距离算法更新距离.
步骤3:使用MDS算法进行降维.

局部线性嵌入(LLE)

LLE首先假设数据在较小的局部是线性的，在降维后尽量保证局部的线性关系.

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

x_1 = w_{12}x_2 + w_{13}x_3 +w_{14}x_4

其中， w_{12} ， w_{13} ， w_{14} 为权重系数。在我们通过LLE降维后，我们希望也尽量保持同样的线性关系，即

x_1' \approx w_{12}x_2' + w_{13}x_3' +w_{14}x_4'

也就是说，投影前后线性关系的权重系数w12，w13，w14是尽量不变或者最小改变的。

从上面可以看出，线性关系只在样本的附近起作用，离样本远的样本对局部的线性关系没有影响，因此降维的复杂度降低了很多。

image

image

对于LLE算法，我们首先要确定邻域大小的选择，即我们需要多少个邻域样本来线性表示某个样本。它主要利用数据的局部线性来逼近全局线性。所以 LLE 的第一步就是寻找每个样本点的 K 个近邻点；直观地，对于每个样本点 X_i ，根据参数 K 计算出该样本点的领域点集 \left\{ Z _ { i 1 } , \dots , Z _ { i K } \right\} .

找到 X_i 和这k个最近邻之间的线性关系，也就是要找到线性关系的权重系数。这显然是一个回归问题:

\begin{array} { c } { \arg \min _ { W } \sum _ { i = 1 } ^ { N } \left\| X _ { i } - \sum _ { j = 1 } ^ { K } W _ { i j } Z _ { i j } \right\| ^ { 2 } } \\ { \text { s.t. } \sum _ { j = 1 } ^ { K } W _ { i j } = 1 , i = 1 , \dots , N } \end{array}

N 为样本个数， W_{ij} 为样本点 i 对应的第 j 个重构系数。
观察单个样本点的目标函数。

\begin{aligned} \varepsilon & = \left\| X _ { i } - \sum _ { j = 1 } ^ { K } W _ { i j } Z _ { i j } \right\| ^ { 2 } = \left\| \sum _ { j = 1 } ^ { K } \left( W _ { i j } X _ { i } - W _ { i j } Z _ { i j } \right) \right\| ^ { 2 } \\ & = \left\| \sum _ { j = 1 } ^ { K } W _ { i j } \left( X _ { i } - Z _ { i j } \right) \right\| ^ { 2 } = \left\| Q _ { i } W _ { i } \right\| ^ { 2 } \end{aligned}

式子中 Q _ { i } = \left[ X _ { i } - Z _ { i 1 } , X _ { i } - Z _ { i 2 } , \cdots , X _ { i } - Z _ { i K } \right] ，重构系数向量 W _ { i } = \left[ W _ { i 1 } , W _ { i 2 } , \cdots , W _ { i K } \right] 。为使 \varepsilon 最小，可以用拉格朗日乘数法求解 W_i 的值。

\begin{aligned} \mathcal { L } _ { i } & = \left\| X _ { i } - \sum _ { j = 1 } ^ { K } W _ { i j } Z _ { i j } \right\| ^ { 2 } - \lambda _ { i } \left( \sum _ { j } ^ { K } W _ { i j } - 1 \right) \\ & = \left\| Q _ { i } W _ { i } \right\| ^ { 2 } - \lambda _ { i } I ^ { T } W _ { i } \\ & = W _ { i } ^ { T } Q _ { i } ^ { T } Q _ { i } W _ { i } - \lambda _ { i } I ^ { T } W _ { i } \end{aligned}

其中 1 = [ 1,1 , \cdots , 1 ] ，长度为 K。
将 \mathcal { L } _ { i } 对 W_i 求偏导。

\frac { \partial \mathcal { L } _ { i } } { \partial W _ { i } } = Q _ { i } ^ { T } Q _ { i } W _ { i } - \lambda _ { i } 1 = C _ { i } W _ { i } - \lambda _ { i } 1 = 0

推出

W _ { i } = \lambda _ { i } C _ { i } ^ { - 1 } 1

式子中 C _ { i } = Q _ { i } ^ { T } Q _ { i } ,另外有 \sum _ { j = 1 } ^ { K } W _ { i j } = 1 ^ { T } W _ { i } = 1 ,则

1 ^ { T } \lambda _ { i } C _ { i } ^ { - 1 } 1 = 1 \Rightarrow \lambda _ { i } = \left( 1 ^ { T } C _ { i } ^ { - 1 } 1 \right) ^ { - 1 }

最终

\begin{aligned} W _ { i } & = \lambda _ { i } C _ { i } ^ { - 1 } 1 = \left( 1 ^ { T } C _ { i } ^ { - 1 } 1 \right) ^ { - 1 } C _ { i } ^ { - 1 } 1 \\ & = \frac { C _ { i } ^ { - 1 } 1 } { 1 ^ { T } C _ { i } ^ { - 1 } 1 } \end{aligned}

上式中 K > D 时 C_i 不一定可逆，可以通过加入 C 的迹的小倍数来规范化。

C _ { i } = C _ { i } + r I

现在我们得到了高维的权重系数，那么我们希望这些权重系数对应的线性关系在降维后的低维一样得到保持。假设我们的n维样本集 \{X_1,X_2,...,X_N\} 在低维的d维度对应投影为 \{Y_1,Y_2,...,Y_m\} , 则我们希望保持线性关系，也就是希望对应的均方差损失函数最小，即最小化损失函数 J(Y) 如下：

\begin{array} { c } { \arg \min _ { Y } \sum _ { i } \left\| Y _ { i } - \sum _ { j } W _ { i j } Y _ { j } \right\| ^ { 2 } } \\ { \text { s.t. } \sum _ { i = 1 } ^ { N } Y _ { i } = 0 } \\ { N ^ { - 1 } \sum _ { i = 1 } ^ { N } Y _ { i } Y _ { i } ^ { T } = I _ { d } } \end{array}

式子中 Y = \left[ Y _ { 1 } , Y _ { 2 } , \cdots , Y _ { N } \right] 是 d × N 矩阵。d 是 Y 的维数。
首先解释加入约束条件

\left\{ \begin{array} { l } { \sum _ { i = 1 } ^ { N } Y _ { i } = 0 } \\ { N ^ { - 1 } \sum _ { i = 1 } ^ { N } Y _ { i } Y _ { i } ^ { T } = I _ { d } } \end{array} \right.

加入这两个约束条件是在不影响损失函数求解的前提下使方程易于求解,保证解得唯一性.实质上第一个约束是所有点的均值。第二个约束是解的协方差。所有点的均值为 0，协方差为单位阵I。这就使得解空间分布唯一。
将目标函数转换为矩阵表示

\begin{array} { c } { \arg \min _ { Y } \left\| Y - Y W ^ { T } \right\| ^ { 2 } } \\ { \text { s.t. } Y 1 _ { N } = 0 } \\ { N ^ { - 1 } Y Y ^ { T } = I _ { d } } \end{array}

同样应用拉格朗日数乘法对上述最优化问题求解。

\mathcal { L } = \sum _ { i } \left\| Y _ { i } - \sum _ { j } W _ { i j } Y _ { j } \right\| ^ { 2 } - \sum _ { \alpha , \beta = 1 } ^ { d } \lambda _ { \alpha \beta } \left[ \frac { 1 } { N } \sum _ { i = 1 } ^ { N } y _ { \alpha i } y _ { \beta i } - \delta _ { \alpha \beta } \right] - \sum _ { \alpha = 1 } ^ { d } \kappa _ { \alpha } \sum _ { i = 1 } ^ { N } y _ { \alpha i }

其中， \lambda _ { \alpha \beta } , \kappa _ { \alpha } 是拉格朗日乘子；并且 \lambda _ { \alpha \beta } = \lambda _ { \beta \alpha } ，如果 \alpha = \beta 时 \delta _ { \alpha \beta } = 1 ，否则 \delta _ { \alpha \beta } = 0 。
为了将上式用矩阵表示，使 \Lambda = \left[ \lambda _ { \alpha \beta } \right] _ { 1 \leq \alpha , \beta \leq d } \in \mathbb { R } ^ { d \times d } 且 \kappa = \left[ \kappa _ { 1 } , \kappa _ { 2 } , \cdots , \kappa _ { d } \right] 。

\mathcal { L } = \left\| Y - Y W ^ { T } \right\| ^ { 2 } - \Lambda \left[ \frac { 1 } { N } Y Y ^ { T } - I _ { d } \right] - I _ { N } ^ { T } Y \kappa

对 Y 求偏导并令为 0，得到

\frac { \partial \mathcal { L } } { \partial Y } = Y \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) - N ^ { - 1 } \Lambda Y - \kappa I _ { N } ^ { T } = 0

由于 \left( I _ { N } - W \right) 1 _ { N } = 0 和 Y 1 _ { N } = 0 ,故 κ = 0，将 κ = 0 带入得到

Y \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) = N ^ { - 1 } \Lambda Y

将上式左右转置，

\left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) Y ^ { T } = N ^ { - 1 } Y ^ { T } \Lambda

上式中 \Lambda 和 Y 均为未知变量，但是 \Lambda 是对称阵，一定能够找到正交阵 U 使得 \Lambda 对角化 \hat { Y } = U ^ { T } Y 。

\left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) \left( Y ^ { T } U \right) = N ^ { - 1 } \left( Y ^ { T } U \right) D \Longleftrightarrow \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) \hat { Y } ^ { T } = N ^ { - 1 } \hat { Y } ^ { T } D

值得一提的是，当令 \hat { Y } = U ^ { T } Y 时，

\begin{array} { c } { \arg \min _ { Y } \left\| \hat { Y } - \hat { Y } W ^ { T } \right\| ^ { 2 } } \\ { s.t. \hat{Y} 1 _ { N } = 0 } \\ { N ^ { - 1 } \hat { Y } \hat { Y } ^ { T } = I _ { d } } \end{array}

依然成立。
因为 N ^ { - 1 } \hat { Y } \hat { Y } ^ { T } = I _ { d } ，故组成 \hat { Y } 矩阵的列向量模长为 N ^ { 1 / 2 } 。所以 N ^ { - 1 / 2 } \hat { Y } 才是 \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) 的特征向量。

到这里就可以得到求解 \Phi ( Y ) 最小值对应的 Y 为： \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) 的最小 d 个特征值对应特征向量再乘上常数 N ^ { 1 / 2 } 。

事实上，因为 \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) 是半正定矩阵，它的特征值 \lambda i 一定非负，由 W 1 _ { N } = I _ { N } 可知， \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) 的最小特征值为 0，对应的特征向量为 1_N 。按照上面陈述， N ^ { 1 / 2 } 1 _ { N } 是 Y 的一个向量。但是它不满足 \hat { Y } _ { 1 _ { N } } = 0 ，所以应该舍去最小的特征值。
所以，求解 \Phi ( Y ) 最小值对应的 Y 为： \left( I _ { N } - W ^ { T } \right) \left( I _ { N } - W \right) 的最小 d + 1 个特征值对应特征向量再乘上常数 N ^ { 1 / 2 } ，舍掉最小的特征值对应的特征向量。

另一个方面，由矩阵范数与迹的关系 \| A \| _ { F } = \sqrt { \operatorname { tr } \left( A ^ { T } A \right) } = \sqrt { \operatorname { tr } \left( A A ^ { T } \right) }

\begin{aligned} \sum _ { i } \left\| Y _ { i } - \sum _ { j } W _ { i j } Y _ { j } \right\| ^ { 2 } & = \left\| Y - Y W ^ { T } \right\| ^ { 2 } = \operatorname { tr } \left( \left( Y - Y W ^ { T } \right) \left( Y - Y W ^ { T } \right) ^ { T } \right) \\ & = \operatorname { tr } \left( Y \left( I - W ^ { T } \right) ( I - W ) Y ^ { T } \right) \end{aligned}

从这个公式可知 \Phi ( Y ) 最小值为 \left( I - W ^ { T } \right) ( I - W ) 对应的特征值之和，由于 \left( I - W ^ { T } \right) ( I - W ) 的最小特征值为 0，所以前 d + 1 个特征值之和与除去 0 特征值的前 d 个特征值之和相同。而且 0 特征应的特征向量为常数向量 1。与上面表述印证。

参考:
周志华<机器学习>
https://www.cnblogs.com/pinard/p/6266408.html
https://github.com/ArrowLuo/LLE_Algorithm
https://github.com/ArrowLuo/LLE_Algorithm/blob/master/%E5%B1%80%E9%83%A8%E7%BA%BF%E6%80%A7%E5%B5%8C%E5%85%A5%EF%BC%88Locally%20linear%20embedding%EF%BC%89.pdf

posted @ 2018-10-05 10:25:45
评论加载中...
发表评论