流形学习和拉普拉斯特征映射
本人开始书写这个系列的缘起在于目前图神经网络似乎热了起来，个人也比较看好对图神经网络的研究，因为深度学习的大热多半是深度卷积神经神经网络的成功带来的，深度卷积神经网络在视觉应用方面的成功，很多就在于卷积神经网络的局部连接先验和图像这一数据结构的特点相得益彰。而现实中的大多数数据，如基因、作者研究的交通网络、甚至语言中的词语、生理信号等等数据，都可以用图数据结构进行建模。因此我们有理由相信深度图神经网络的发展很有可能会在这些数据的相关应用中带来突破性进展。作者几年的阅读和研究，也做了一些和图学习相关的研究，写写博文，也算给对自己这方面的知识做做总结。
第一篇就来写写本人对流形学习的理解好了，流形学习（Manifold Learning）有着一个很好听的中文名字，流形出自文天祥的诗《正气歌》“天地有正气，杂然赋流形。”。不管它的名词多么诗情画意，流形学习可以仅仅理解为利用高维数据的几何性质来做如下的工作[1]：
1.聚类：将点根据相似性聚成多个类。给定{X1,…,Xn}，构建一个函数f : X to {1,…,k}。两个在流形上相近的点应该属于同一类。
2.降维：将点映射到一个更低维的空间，且保存其几何结构。给定R^D上的{X1,…,Xn} ，构建一个函数f : R^D to R^d，d<D。映射过程中需要保存点在流形上的距离。
3.半监督，监督学习：给定有标注和无标注的点，构建一个标注函数。给定{(X1,Y1),…,(Xn,Yn)}，构建 f : X to Y。流形上相近的点应该有相同的标注。
总结来说，如图1所示，就是对于高维流形（图）上的点{X1,…,Xn}，通过f将其映射到另一个空间后，应该尽量保持各点在流形上的距离。拉普拉斯特征映射方法[2]是其中最为经典的方法之一，其在一定程度上保持了流形的局部信息。假设点{X1,…,Xn}位于如图2左侧所示的流形之上，{X1,…,Xn}构成了一个图G=(V,E)，{X1,…,Xn}是图G上的节点，假设流形结构我们是已知的，因此图上各节点之间的距离也是已知的，{X1,…,Xn}各节点对之间的距离w_ij (i=1...n, j=1...n)构成了相似矩阵W in R^nxn（图2右侧）。
图1 流形学习的本质，从左侧空间映射到右侧空间，仍然保持各点之间在原流形上的空间关系
图2.一个图的相似矩阵
这时，我们在进行学习时（聚类、降维等等）需要将{X1,…,Xn}映射到(y1,...,yn)。如前所述，我们希望(y1,...,yn)之间的距离和{X1,…,Xn}之间的距离相似，即|yi - yj|和w_ij尽量正相关，这可以通过最小化以下损失函数获得：
其中对角矩阵D_ii = \sum_j W_ij, L = D - W。矩阵L被称作图拉普拉斯。通过最小化y^T L y，我们可以尽量保持流形上的点{X1,…,Xn}映射到(y1,...,yn)之后，(y1,...,yn)仍然保持了{X1,…,Xn}之间的空间关系。以上的求解是假设(y1,...,yn)为一维，即某条直线上的点，加入(y1,...,yn)为多维的向量，拉普拉斯特征映射的损失函数为：
L也可被视为流形上Laplace-Beltrami算子的离散近似。假设映射为f，损失函数的连续形式为：
对于损失函数的连续形式，可以这样来理解：我们希望映射f尽量保持流形上各点的空间关系，那么当流形上的数据分布较为密集时，我们希望映射后的数据分布也较为平滑，即梯度较小。而拉普拉斯特征映射正是其离散形式。
总结来看，流形学习的本质即是在映射过程中尽量保持数据所在流形上的先验属性，后面准备写的流形上的非负矩阵分解、图神经网络等究其本质都是一种映射，这些方法都可以说是在映射过程中利用已知目标图数据的原有性质来做文章
To be continued
[1] Manifold Learning: The Theory Behind It, https://towardsdatascience.com/manifold-learning-the-theory-behind-it-c34299748fec
[2] Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps for dimensionality reduction and data representation." Neural computation 15, no. 6 (2003): 1373-1396.
网友评论