流行-Manifold学习理解与应用

流行-Manifold【1】

　　流形，也就是 Manifold 。

1. 比较好的形象理解

　　流形学习的观点是认为，我们所能观察到的数据实际上是由一个低维流形映射到高维空间上的，即这些数据所在的空间是“嵌入在高维空间的低维流形。”。由于数据内部特征的限制，一些高维中的数据会产生维度上的冗余，实际上只需要比较低的维度就能唯一地表示。

　　举个例子，比如说我们在平面上有个圆，如何表示这个圆呢？如果我们把圆放在一个平面直角坐标系中，那一个圆实际上就是由一堆二维点构成的。

　　比如一个单位圆：（1,0）是一个在圆上的点，（0,1）也是一个在圆上的点，但（0.0）和（2,3）等等很多点是不在这个圆上的。显然如果用二维坐标来表示，我们没有办法让这个二维坐标系的所有点都是这个圆上的点。也就是说，用二维坐标来表示这个圆其实是有冗余的。我们希望，如果能建立某一种描述方法，让这个描述方法所确定的所有点的集合都能在圆上，甚至能连续不间断地表示圆上的点，那就好了！有没有这种方法呢？对于圆来说，当然有！那就是用极坐标。在极坐标的表示方法下，圆心在原点的圆，只需要一个参数就能确定：半径。当你连续改变半径的大小，就能产生连续不断的“能被转换成二维坐标表示”的圆。所以说，实际上二维空间中的圆就是一个一维流形。　　

　　与之相似的，三维空间中一个球面，用x, y, z三个坐标轴确定时会产生冗余（很多在三维空间中的数据点并不在球面上）。但其实只需要用两个坐标就可以确定了，比如经度和维度。只要给定任何合法的经度和维度，我们就都能保证这个点肯定在球面上！球面是一个很典型的流形的例子，而地球就是一个很典型的“球面”啦（姑且当作球面好啦）。

　　有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”，不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像，所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。直观上来讲，一个流形好比是一个 d 维的空间，在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是，流形并不是一个“形状”，而是一个“空间”，如果你觉得“扭曲的空间”难以想象，那么请再回忆一块布的例子（一块二维的布，再三维空间进行扭曲，则说“三维空间扭曲的布是一个二维的流行”，即"二维流形"嵌入了“三维空间”）。如果我没弄错的话，广义相对论似乎就是把我们的时空当作一个四维流（空间三维加上时间一维）形来研究的，引力就是这个流形扭曲的结果。当然，这些都是直观上的概念，其实流形并不需要依靠嵌入在一个“外围空间”而存在，稍微正式一点来说，一个 d 维的流形就是一个在任意点出局部同胚于（简单地说，就是正逆映射都是光滑的一一映射）欧氏空间 $\textcal{R}^d$ 。

2. 流形学习的作用

　　那么，流形学习有什么用呢？我现在能想到的主要有两个方面。

　　先说第一个方面。高维空间有冗余，低维空间没冗余。也就是说，流形可以作为一种数据降维的方式。传统很多降维算法都是用欧氏距离作为评价两个点之间的距离函数的。但是仔细想想这种欧氏距离直觉上并不靠谱。“我们只是看到了三维数据，就要用三维坐标系内的尺度去对事物进行评价？”总觉得有些怪怪的。

　　举个例子，从北京到上海有多远？你可以找一个地球仪，然后用一把能弯曲的软软的尺子，经过地球仪表面然后测量一下这两个点的距离。但是如果我用一个直直的线，将地球仪从北京到上海洞穿，测量出一个更短的距离，你一定会觉得我疯了。显然对于“从北京到上海的距离”这件事，我们关注的是把三维地球展开成二维平面，然后测量的地表上的距离，而不是三维空间中球面上两个点的空间直线距离（相信没有人从北京到上海会挖一条直通上海的地道的！将这个问题推广一些，假如说决策部门打算把一些离得比较近的城市聚成一堆，然后组建个大城市。这时候“远近”这个概念显然是指地表上的距离，因为说空间直线距离并没有什么意义。

　　而对于降维算法来说，如果使用传统的欧氏距离来作为距离尺度，显然会抛弃“数据的内部特征”。如果测量球面两点距离采用空间欧氏距离，那就会忽略掉“这是个球面”这个信息。

　　那么，除了地球这种简单的例子，实际应用中的数据，怎么知道它是不是一个流形呢？于是不妨又回归直观的感觉。再从球面说起，如果我们事先不知道球面的存在，那么球面上的点，其实就是三维欧氏空间上的点，可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是，它们允许出现的位置受到了一定的限制，具体到球面，可以可以看一下它的参数方程

可以看到，这些三维的坐标实际上是由两个变量 $\theta$ 和 $\varphi$ 生成的，也可以说成是它的自由度是二，也正好对应了它是一个二维的流形。有了这样的感觉之后，再来看流形学习里经常用到的人脸的例子，就很自然了。

3. 流行学习的应用　　

　　下图是 Isomap 论文里的一个结果：

　　这里的图片来自同一张人脸（好吧，其实是人脸模型），每张图片是 64×64 的灰度图，如果把位图按照列（或行）拼起来，就可以得到一个 4096 维的向量，这样一来，每一张图片就可以看成是 4096 维欧氏空间中的一个点。很显然，并不是 4096 维空间中任意一个点都可以对应于一张人脸图片的，这就类似于球面的情形，我们可以假定所有可以是人脸的 4096 维向量实际上分布在一个 d 维 (d < 4096) 的子空间中。而特定到 Isomap 的人脸这个例子，实际上我们知道所有的 698 张图片是拍自同一个人脸（模型），不过是在不同的 pose 和光照下拍摄的，如果把 pose （上下和左右）当作两个自由度，而光照当作一个自由度，那么这些图片实际只有三个自由度，换句话说，存在一个类似于球面一样的参数方程（当然，解析式是没法写出来的），给定一组参数（也就是上下、左右的 pose 和光照这三个值），就可以生成出对应的 4096 维的坐标来。换句话说，这是一个嵌入在 4096 维欧氏空间中的一个 3 维流形。实际上，上面的那张图就是 Isomap 将这个数据集从 4096 维映射到 3 维空间中，并显示了其中 2 维的结果，图中的小点就是每个人脸在这个二维空间中对应的坐标位置，其中一些标红圈的点被选出来，并在旁边画上了该点对应的原始图片，可以很直观地看出这两个维度正好对应了 pose 的两个自由度平滑变化的结果。就我目前所知，把流形引入到机器学习领域来主要有两种用途：一是将原来在欧氏空间中适用的算法加以改造，使得它工作在流形上，直接或间接地对流形的结构和性质加以利用；二是直接分析流形的结构，并试图将其映射到一个欧氏空间中，再在得到的结果上运用以前适用于欧氏空间的算法来进行学习。这里 Isomap 正巧是一个非常典型的例子，因为它实际上是通过“改造一种原本适用于欧氏空间的算法”，达到了“将流形映射到一个欧氏空间”的目的。 :) Isomap 所改造的这个方法叫做 Multidimensional Scaling (MDS) ，MDS 是一种降维方法，它的目的就是使得降维之后的点两两之间的距离尽量不变（也就是和在原是空间中对应的两个点之间的距离要差不多）。只是 MDS 是针对欧氏空间设计的，对于距离的计算也是使用欧氏距离来完成的。如果数据分布在一个流形上的话，欧氏距离就不适用了。

　　让我们再回到地球——这个在三维空间中的二维流形，假设我们要在三维空间中计算北极点和南极点的距离，这很容易，就是两点相连的线段的长度，可是，如果要在这个流形上算距离就不能这样子算了，我们总不能从北极打个洞钻到南极去吧？要沿着地球表面走才行，当然，如果我随便沿着什么路线走一遍，然后数出总共走了多少步作为距离，这是不成的，因为这样一来如果我沿着不同的路线走，岂不是会得到不同的距离值？总而言之，我们现在需要一个新的定义在地球表面（流形）上的距离度量，理论上来说，任意满足测度的 4 个条件的函数都可以被定义为距离，不过，为了和欧氏空间对应起来，这里选择一个直线距离的推广定义。

　　还记得初中学的“两点之间，线段最短”吗？现在，我们反过来说，把线段的概念推广一下，变成“两点之间最短的曲线是线段”，于是流形上的距离定义也就等同于欧氏空间了：流形上两个点之间的距离就是连接两个点的“线段”的长度。虽然只是置换了一个概念，但是现在两者统一起来了，不过，在流形上的线段大概就不一定是“直”的了（于是直线也变成不一定是“直”的了），通常又称作是“测地线”。对于球面这个简单的流形来说，任意一条线段必定是在一个“大圆”上的，于是球面上的直线其实都是一些大圆，也造成了球面这个流形上没有平行线等一系列尴尬的局面（任意两条直线均相交），如果你看过一些数学科普八卦类的书，应该会回忆起不少东西啦！

　　回到 Isomap ，它主要做了一件事情，就是把 MDS 中原始空间中距离的计算从欧氏距离换为了流形上的测地距离。当然，如果流形的结构事先不知道的话，这个距离是没法算的，于是 Isomap 通过将数据点连接起来构成一个邻接 Graph 来离散地近似原来的流形，而测地距离也相应地通过 Graph 上的最短路径来近似了。如下图所示：

　　这个东西叫做 Swiss Roll ，姑且把它看作一块卷起来的布好了。图中两个标黑圈的点，如果通过外围欧氏空间中的欧氏距离来计算的话，会是挨得很近的点，可是在流形上它们实际上是距离很远的点：红色的线是 Isomap 求出来的流形上的距离。可以想像，如果是原始的 MDS 的话，降维之后肯定会是很暴力地直接把它投影到二维空间中，完全无视流形结构，而 Isomap 则可以成功地将流形“展开”之后再做投影。

　　除了 Isomap 之外，Manifold Embedding 的算法还有很多很多，包括 Locally Linear Embedding 、Laplacian Eigenmaps 、Hessian Eigenmaps 、Local Tangent Space Alignment、Semidefinite Embedding (Maximum Variance Unfolding) 等等等等。哪个好哪个坏也不好说，它们都各有特点，而且也各自有不少变种。网上有一个 Matlab 的 demo ，给出了几种流行的 manifold embedding 算法在一些 synthetic manifold 上的结果和对比，可以有一个直观的认识。

　　另一方面是改造现有算法使其适合流形结构甚至专门针对流形的特点来设计新的算法，比较典型的是 graph regularized semi-supervised learning 。简单地说，在 supervised learning 中，我们只能利用有 label 的数据，而（通常都会有很多的）没有 label 的数据则白白浪费掉。在流形假设下，虽然这些数据没有 label ，但是仍然是可以有助于 Learn 出流形的结构的，而学出了流形结构之后实际上我们就是对原来的问题又多了一些认识，于是理所当然地期望能得到更好的结果喽。

　　当然，所有的这些都是基于同一个假设，那就是数据是分布在一个流形上的（部分算法可能会有稍微宽松一些的假设），然而 real world 的数据，究竟哪些是分别在流形上的呢？这个却是很难说。不过，除了典型的 face 和 hand written digit 之外，大家也有把基于流形的算法直接用在诸如 text 看起来好像也流形没有什么关系的数据上，效果似乎也还不错。

　　话说回来，虽然和实际应用结合起来是非常重要的一个问题，但是也并不是决定性的，特别是对于搞理论方面的人来我想，对于他们来说，其实也像是在做应用啦，不过是把数学里的东西应用到机器学习所研究的问题里来，而且其中关系错综复杂，图论、代数、拓扑、几何……仿佛是十八路诸侯齐聚一堂，所以让我总觉得要再花 500 年来恶补数学才行呀！

　　不过我表示可以理解其中存在的潜在的 happy 之处，就好比你玩游戏，先玩了《天地劫：神魔至尊传》，然后再玩《天地劫序章：幽城幻剑录》的时候，会发现里面的人物、剧情逐渐地联系起来，也许甚至只是在一个地方出现过的一个完全不起眼的配角，当你再在另一地方突然看到他是，一系列的线索瞬间被联系起来，全局的画面渐渐浮现，那种 happy 的感觉，大概就是所谓的“拨云见日”了吧！