有关流形学习论文
流形学习
流形学习是个很广泛的概念。这里我主要谈的是自从2000年以后形成的流形学习概念和其主要代表方法。自从2000年以后，流形学习被认为属于非线性降维的一个分支。众所周知，引导这一领域迅速发展的是2000年Science杂志上的两篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形学习的基本概念
那流形学习是什莫呢？为了好懂，我尽可能应用少的数学概念来解释这个东西。所谓流形（manifold）就是一般的几何对象的总称。比如人，有中国人、美国人等等；流形就包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习把一组在高维空间中的数据在低维空间中重新表示。和以往方法不同的是，在流形学习中有一个假设，就是所处理的数据采样于一个潜在的流形上，或是说对于这组数据存在一个潜在的流形。 对于不同的方法，对于流形性质的要求各不相同，这也就产生了在流形假设下的各种不同性质的假设，比如在Laplacian
Eigenmaps中要假设这个流形是紧致黎曼流形等。对于描述流形上的点，我们要用坐标，而流形上本身是没有坐标的，所以为了表示流形上的点，必须把流形放入外围空间（ambient space）中，那末流形上的点就可以用外围空间的坐标来表示。比如R^3中的球面是个2维的曲面，因为球面上只有两个自由度，但是球面上的点一般是用外围R^3空间中的坐标表示的，所以我们看到的R^3中球面上的点有3个数来表示的。当然球面还有柱坐标球坐标等表示。对于R^3中的球面来说，那末流形学习可以粗略的概括为给出R^3中的表示，在保持球面上点某些几何性质的条件下，找出找到一组对应的内蕴坐标（intrinsic coordinate）表示，显然这个表示应该是两维的，因为球面的维数是两维的。这个过程也叫参数化（parameterization）。直观上来说，就是把这个球面尽量好的展开在通过原点的平面上。在PAMI中，这样的低维表示也叫内蕴特征（intrinsic feature）。一般外围空间的维数也叫观察维数，其表示也叫自然坐标（外围空间是欧式空间）表示,在统计中一般叫observation。
了解了流形学习的这个基础，那末流形学习中的一些是非也就很自然了，这个下面穿插来说。由此，如果你想学好流形学习里的方法，你至少要了解一些微分流形和黎曼几何的基本知识。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap开创了一个数据处理的新战场。在没有具体说Isomap之前，有必要先说说MDS（Multidimensional Scaling）这个方法。我们国内的很多人知道PCA，却很多人不知道MDS。PCA和MDS是相互对偶的两个方法。MDS就是理论上保持欧式距离的一个经典方法，MDS最早主要用于做数据的可视化。由于MDS得到的低维表示中心在原点，所以又可以说保持内积。也就是说，用低维空间中的内积近似高维空间中的距离。经典的MDS方法，高维空间中的距离一般用欧式距离。
Isomap就是借窝生蛋。他的理论框架就是MDS，但是放在流形的理论框架内，原始的距离换成了流形上的测地线（geodesic）距离。其它一模一样。所谓的测地线，就是流形上加速度为零的曲线，等同于欧式空间中的直线。我们经常听到说测地线是流形上两点之间距离最短的线。其实这末说是不严谨的。流形上两点之间距离最短的线是测地线，但是反过来不一定对。另外，如果任意两个点之间都存在一个测地线，那末这个流形必须是连通的邻域都是凸的。Isomap就是把任意两点的测地线距离（准确地说是最短距离）作为流形的几何描述，用MDS理论框架
理论上保持这个点与点之间的最短距离。在Isomap中，测地线距离就是用两点之间图上的最短距离来近似的，这方面的算法是一般计算机系中用的图论中的经典算法。
如果你曾细致地看过Isomap主页上的matlab代码，你就会发现那个代码的实现复杂度远超与实际论文中叙述的算法。在那个代码中，除了论文中写出的算法外，还包括了 outlier detection和embedding scaling。这两样东西，保证了运行他们的程序得到了结果一般来说相对比较理想。但是，这在他们的算法中并没有叙述。如果你直接按照他论文中的方法来实现，你可以体会一下这个结果和他们结果的差距。从此我们也可以看出，那几个作者做学问的严谨态度，这是值得我们好好学习的。
另外比较有趣的是，Tenenbaum根本不是做与数据处理有关算法的人，他是做计算认知科学（computational cognition science）的。在做这个方法的时候，他还在stanford，02年就去了
MIT开创一派，成了CoCoSci 的掌门人，他的组成长十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT带的学生就从来再也没有做过类似的工作。其原因我今年夏天有所耳闻。他在今年参加 UCLA Alan Yuille 组织的一个summer school上说，（不是原文，是大意）我们经常忘了做研究的原始出发点是什莫。他做Isomap就是为了找一个好的visual perception的方法，他还坚持了他的方向和信仰，computational cognition，他没有随波逐流。而由他引导起来的 manifold learning 却快速的发展成了一个新的方向。
这是一个值得我们好好思考的问题。我们做一个东西，选择一个研究方向究竟是为了什莫。你考虑过吗？
（当然，此问题也在问我自己）
b) LLE (Locally linear Embedding)
LLE在作者写出的表达式看,是个具有十分对称美的方法. 这种看上去的对称对于启发人很重要。LLE的思想就是，一个流形在很小的局部邻域上可以近似看成欧式的，就是局部线性的。那末，在小的局部邻域上，一个点就可以用它周围的点在最小二乘意义下最优的线性表示。LLE把这个线性拟合的系数当成这个流形局部几何性质的刻画。那末一个好的低维表示，就应该也具有同样的局部几何，所以利用同样的线性表示的表达式，最终写成一个二次型的形式，十分自然优美。
注意在LLE出现的两个加和优化的线性表达，第一个是求每一点的线性表示系数的。虽然原始公式中是写在一起的，但是求解时，是对每一个点分别来求得。第二个表示式，是已知所有点的线性表示系数，来求低维表示（或嵌入embedding）的，他是一个整体求解的过程。这两个表达式的转化正好中间转了个弯，使一些人困惑了，特别后面一个公式写成一个二次型的过程并不是那末直观，很多人往往在此卡住，而阻碍了全面的理解。我推荐大家去精读 Saul 在
JMLR上的那篇LLE的长文。那篇文章无论在方法表达还是英文书写，我认为都是精品，值得好好玩味学习。
另外值得强调的是，对于每一点处拟合得到的系数归一化的操作特别重要，如果没有这一步，这个算法就没有效果。但是在原始论文中，他们是为了保持数据在平行移动下embedding不变。 LLE的matlab代码写得简洁明了，是一个样板。
在此有必要提提Lawrence Saul这个人。在Isomap和LLE的作者们中，Saul算是唯一一个以流形学习（并不限于）为研究对象开创学派的人。Saul早年主要做参数模型有关的算法。自从LLE以后，坐阵UPen创造了一个个佳绩。主要成就在于他的两个出色学生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多奖，在此不多说，可以到他主页上去看。Weinberger把学习核矩阵引入到流形学习中来。他的这个方法在流形学习中影响到不是很显著，却是在 convex optimization 中人人得知。Fei Sha不用多说了，machine learning中一个闪亮的新星，中国留学生之骄傲。现在他们一个在Yahoo,一个在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要说哪一个方法被做的全面，那莫非LE莫属。如果只说LE这个方法本身，是不新的，许多年前在做mesh相关的领域就开始这莫用。但是放在黎曼几何的框架内，给出完整的几何分析的，应该是Belkin和Niyogi（LE作者）的功劳。
LE的基本思想就是用一个无向有权图来描述一个流形，然后通过用图的嵌入（graph
embedding）来找低维表示。说白了，就是保持图的局部邻接关系的情况把这个图从高维空间中重新画在一个低维空间中（graph drawing）。
在至今为止的流行学习的典型方法中，LE是速度最快、效果相对来说不怎莫样的。但是LE有一个其他方法没有的特点，就是如果出现outlier情况下，它的鲁棒性（robustness）特别好。 后来Belkin和Niyogi又分析了LE的收敛性。大家不要忽视这个问题，很重要。鼓励有兴趣数学功底不错的人好好看看这篇文章。
d) Hessian Eigenmaps
如果你对黎曼几何不懂，基本上看不懂这个方法。又加作者表达的抽象，所以绝大多数人对这个方法了解不透彻。在此我就根据我自己的理解说说这个方法。
这个方法有两个重点：（1）如果一个流形是局部等距（isometric）欧式空间中一个开子集的，那末它的Hessian矩阵具有d+1维的零空间。（2）在每一点处，Hessian系数的估计。
首先作者是通过考察局部Hessian的二次型来得出结论的，如果一个流形局部等距于欧式空间中的一个开子集，那末由这个流形patch 到开子集到的映射函数是一个线性函数，线性函数的二次混合导数为零，所以局部上由Hessian系数构成的二次型也为零，这样把每一点都考虑到，过渡到全局的Hessian矩阵就有d+1维的零空间，其中一维是常函数构成的，也就是1向量。其它的d维子空间构成等距坐标。这就是理论基础的大意，当然作者在介绍的时候，为了保持理论严谨，作了一个由切坐标到等距坐标的过渡。
另外一个就是局部上Hessian系数的估计问题。我在此引用一段话：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
这段话是我在初学HE时候，写信问Dave Donoho，他给我的回信。希望大家领会。如果你了解了上述基本含义，再去细看两遍原始论文，也许会有更深的理解。由于HE牵扯到二阶导数的估计，所以对噪声很敏感。另外，HE的原始代码中在计算局部切坐标的时候，用的是奇异值分解(SVD)，所以如果想用他们的原始代码跑一下例如图像之类的真实数据，就特别的慢。其实把他们的代码改一下就可以了，利用一般PCA的快速计算方法，计算小尺寸矩阵的特征向量即可。还有，在原始代码中，他把Hessian系数归一化了，这也就是为什莫他们叫这个方法为 Hessian LLE 的原因之一。
Dave Dohono是学术界公认的大牛，在流形学习这一块，是他带着他的一个学生做的，Carrie Grimes。现在这个女性研究员在Google做 project leader，学术界女生同学的楷模 : )
e) LTSA (Local tangent space alignment)
很荣幸，这个是国内学者（浙江大学数学系的老师ZHANG Zhenyue）为第一作者做的一个在流行学习中最出色的方法。由于这个方法是由纯数学做数值分析出身的老师所做，所以原始论文看起来公式一大堆，好像很难似的。其实这个方法非常直观简单。
象 Hessian Eigenmaps 一样，流形的局部几何表达先用切坐标，也就是PCA的主子空间中的坐标。那末对于流形一点处的切空间，它是线性子空间，所以可以和欧式空间中的一个开子集建立同构关系，最简单的就是线性变换。在微分流形中，就叫做切映射 (tangential map)，是个很自然很基础的概念。把切坐标求出来，建立出切映射，剩下的就是数值计算了。最终这个算法划归为一个很简单的跌代加和形式。如果你已经明白了MDS，那末你就很容易明白，这个算法本质上就是MDS的从局部到整体的组合。
这里主要想重点强调一下，那个论文中使用的一个从局部几何到整体性质过渡的alignment技术。在spectral method（特征分解的）中，这个alignment方法特别有用。只要在数据的局部邻域上你的方法可以写成一个二次项的形式，就可以用。
其实LTSA最早的版本是在02年的DOCIS上。这个alignment方法在02年底Brand的 charting a manifold 中也出现，隐含在Hessian Eigenmaps中。在HE中，作者在从局部的Hessian矩阵过渡到全局的Hessian矩阵时，用了两层加号，其中就隐含了这个 alignment方法。后来国内一个叫 ZHAO Deli 的学生用这个方法重新写了LLE，发在Pattern Recognition上，一个短文。可以预见的是，这个方法还会被发扬光大。
ZHA Hongyuan 后来专门作了一篇文章来分析 alignment matrix 的谱性质，有兴趣地可以找来看看。
f) MVU (Maximum variance unfolding)
这个方法刚发出来以后，名字叫做Semi-definite Embedding (SDE)。构建一个局部的稀疏欧式距离矩阵以后，作者通过一定约束条件（主要是保持距离）来学习到一个核矩阵，对这个核矩阵做PCA就得到保持距离的 embedding，就这莫简单。但是就是这个方法得了多少奖，自己可以去找找看。个人观点认为，这个方法之所以被如此受人赏识，无论在vision还是在learning，除了给流形学习这一领域带来了一个新的解决问题的工具之外，还有两个重点，一是核方法（kernel），二是半正定规划（semi-definite programming），这两股风无论在哪个方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
这个方法不太被人所知，但是我认为这个是流形学习发展中的一个典型的方法（其实其他还有很多人也这莫认为）。就效果来说，这个方法不算好，说它是一个典型的方法，是因为这个方法应用了黎曼几何中一个很直观的性质。这个性质和法坐标(normal coordinate)、指数映射(exponential map)和距离函数(distance function)有关。
如果你了解黎曼几何，你会知道，对于流形上的一条测地线，如果给定初始点和初始点处测地线的切方向，那莫这个测地线就可以被唯一确定。这是因为在这些初始条件下，描述测地线的偏微分方程的解是唯一的。那末流形上的一条测地线就可以和其起点处的切平面上的点建立一个对应关系。我们可以在这个切平面上找到一点，这个点的方向就是这个测地线在起点处的切方向，其长度等于这个测地线上的长。这样的一个对应关系在局部上是一一对应的。那末这个在切平面上的对应点在切平面中就有一个坐标表示，这个表示就叫做测地线上对应点的法坐标表示（有的也叫指数坐标）。那末反过来，我们可以把切平面上的点映射到流形上，这个映射过程就叫做指数映射（Logmap就倒过来）。如果流形上每一个点都可以这样在同一个切平面上表示出来，那末我们就可以得到保持测地线长度的低维表示。如果这样做得到，流形必须可以被单坐标系统所覆盖。
如果给定流形上的采样点，如果要找到法坐标，我们需要知道两个东西，一是测地线距离，二是每个测地线在起点处的切方向。第一个东西好弄，利用Isomap中的方法直接就可以解决，关键是第二个。第二个作者利用了距离函数的梯度，这个梯度和那个切方向是一个等价的关系，一般的黎曼几何书中都有叙述。作者利用一个局部切坐标的二次泰勒展开来近似距离函数，而距离是知道的，就是测地线距离，局部切坐标也知道，那末通过求一个简单的最小二乘问题就可以估计出梯度方向。
如果明白这个方法的几何原理，你再去看那个方法的结果，你就会明白为什莫在距离中心点比较远的点的embedding都可以清楚地看到在一条条线上，效果不太好。
最近这个思想被北大的一个年轻的老师 LIN Tong 发扬光大，就是ECCV‘06上的那篇，还有即将刊登出的TPAMI上的 Riemannian Manifold Learning，实为国内研究学者之荣幸。Lin的方法效果非常好，但是虽然取名叫Riemannian，没有应用到黎曼几何本身的性质，这样使他的方法更容易理解。
Lin也是以一个切空间为基准找法坐标，这个出发点和思想和Brun（S-Logmaps）的是一样的。但是Lin全是在局部上操作的，在得出切空间原点处局部邻域的法坐标以后，Lin采用逐步向外扩展的方法找到其他点的法坐标，在某一点处，保持此点到它邻域点的欧式距离和夹角，然后转化成一个最小二乘问题求出此点的法坐标，这样未知的利用已知的逐步向外扩展。说白了就像缝网一样，从几个临近的已知点开始，逐渐向外扩散的缝。效果好是必然的。
浅谈流形学习
bypluskid, on 2010-05-29, in Machine Learning76 comments
总觉得即使是“浅谈”两个字，还是让这个标
题有些过大了，更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了，想起来要扯一下这个话题，也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉，不过如果并不是想要进行严格的理论推导的话，也可以从许多直观的例子得到一些感性的认识，正好我也就借这个机会来简单地谈一下这个话题吧，或者说至少是我到目前为止对这它的认识。 这两个词，在谈 Manifold 之前，不妨先说说 Learning ，也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科，因为每当它的一个子领域发展得像模像样之后，就立马自立门户，从此和 AI “再无瓜葛”了，而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪，比如说数学，分门别类总算是够多了吧？可以不管怎么分，大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢？我觉得这里有很大一部分
是它自身定位的问题。
反正现在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
说 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是这相当于一个 tautology ，因为到底什么又是the intelligence of machines呢？一开始的时候，大牛们都野心勃勃，而且好像也是信心满满，就好像曾经广泛认为“牛顿定理揭示了宇宙真理，科学剩下的事情只要按照公式来做计算就可以了”一样，大家可能觉得，不出几十年，人类就可以不用思考，交给 AI 来做了。不过我这里并不想再多说诸如什么是“思考”，什么是“智能”之类的以及随之而来的“图灵测试”之类的话题。我想说的是，到头来，AI 到底是什么，这还是一个问题，或者说，AI 在一开始定了一个过高的目标，几十年后，发现情况并不像当年那么乐观，却又有些下不了台了。
这个时候，AI 的一些旁枝或者子领域果断放下面子，丢掉了那个近乎玄幻的目标，逐渐发展成为“正常”的学科，所以也就不再好称为 AI 了。或者说现在的 AI 有两个意思，一个广义的 AI ，包括了所有相关的以及派生的领域，另一个则是狭义的或者经典的 AI ，专门指那些仍然在执着地追求着真正的“智能”的部分，或者说得不好听一点，就
是剩下的部分。
Machine Learning 作为离家出走的典型，虽然名字里带了 Learning 一个词，让人乍一看觉得和 Intelligence 相比不过是换了个说法而已，然而事实上这里的 Learning 的意义要朴素得多。我们来看一看 Machine Learning 的典型的流程就知道了，其实有时候觉得和应用数学或者更通俗的数学建模有些类似，通常我们会有需要分析或者处理的数据，根据一些经验和一些假设，我们可以构建一个模型，这个模型会有一些参数（即使是非参数化方法，也是可以类似地看待的），根据数据来求解模型参数的过程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞机器学习的人，通常把它叫做 Learning （或者，换一个角度，叫 Training）——因为根据数据归纳出一个有用的模型，这和我们人类“学习”的过程还是挺类似的吧。不过，如果抛开无聊的抠字眼游戏的话，我们可以看到，Machine Learning 已经抛弃了“智能”的高帽子，它的目的就是要解决具
体的问题——而并不关心是否是通过一种“智能”的方式类解决的。
说到这里，其实我们构造模型就类似于写一个类，数据就是构造函数的参数，Learning 就是构造函数运行的过程，成功构造一个对象之后，我们就完成了学习。一些 Machine Learning 的问题到这一步就结束了，另一些情况还会使用得到的模型（对象）对后来的数据进行一些处理，通常会是Inferencing。到这个时候，又有些像统计里的东西了，所谓“统计推断”嘛。其实原本统计和机器学习研究的不少问题就是交叉在一起的，不过两派人从不同的角度来看待同样的问题。而且，也确实有 Statistical Learning 这么一个说法存在的，可以把他看成是 Machine Learning 的一个子领域（或者是一个分子或
者甚至就是 Machine Learning 本身）。
到这里，如果你还没有因为不断地抠字眼而烦躁的话，
我已经忍无可忍了。所以，我就假定你已经了解了什么叫 Learning ，或者是已经恶心到懒得去了解了。于是我们转入下一个话题：流形，也就是 Manifold 。不知道你有没有为我在本文开头放上的那个地球的图片感到困惑？这是因为球面是一个很典型的流
形的例子，而地球就是一个很典型的“球面”啦（姑且当作球面好啦）。
有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”，不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像，所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布，可以把它看成一个二维平面，这是一个
二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不
扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况）。
所以，直观上来讲，一个流形好比是一个 d 维的空间，在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是，流形并不是一个“形状”，而是一个“空间”，如果你觉得“扭曲的空间”难以想象，那么请再回忆之前一块布的例子。如果我没弄错的话，广义相对论似乎就是把我们的时空当作一个四维流（空间三维加上时间一维）形来研究的，引力就是这个流形扭曲的结果。当然，这些都是直观上的概念，其实流形并不需要依靠嵌入在一个“外围空间”而存在，稍微正式一点来说，一个 d 维的流形就是一个在任意点出局部同胚于（简单地说，就是正逆映射都是光滑的一一映射）欧氏空间。
实际上，正是这种局部与欧氏空间的同
胚给我们带来了很多好处，这使得我们在日常生活中许许多多的几何问题都可以使用简单的欧氏几何来解决，因为和地球的尺度比起来，我们的日常生活就算是一个很小的局部啦——我突然想起《七龙珠》里的那个界王住的那种私人小星球，走几步就要绕一圈的感觉，看来界王不仅要体力好（那上面重力似乎是地球的十倍），而且脑力也要好，
初中学的必须是黎曼几何了！
那么，除了地球这种简单的例子，实际应用中的数据，怎么知道它是不是一个流形呢？于是不妨又回归直观的感觉。再从球面说起，如果我们事先不知道球面的存在，那么球面上的点，其实就是三维欧氏空间上的点，可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是，它们允许出现的位置受到了一定的限制，具体到球面，可以
可以看一下它的参数方程：
可以看到，这些三维的坐标实际上是由两个变量和生成的，也可以说成是它的自由度是二，也正好对应了它是一个二维的流形。有了这样的感觉之后，再来看流形学习里经
常用到的人脸的例子，就很自然了。下图是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 上的最短路径来近似了。
流形学习
流形学习是个很广泛的概念。这里我主要谈的是自从2000年以后形成的流形学习概念和其主要代表方法。自从2000年以后，流形学习被认为属于非线性降维的一个分支。众所周知，引导这一领域迅速发展的是2000年Science杂志上的两篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形学习的基本概念
那流形学习是什莫呢？为了好懂，我尽可能应用少的数学概念来解释这个东西。所谓流形（manifold）就是一般的几何对象的总称。比如人，有中国人、美国人等等；流形就包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习把一组在高维空间中的数据在低维空间中重新表示。和以往方法不同的是，在流形学习中有一个假设，就是所处理的数据采样于一个潜在的流形上，或是说对于这组数据存在一个潜在的流形。 对于不同的方法，对于流形性质的要求各不相同，这也就产生了在流形假设下的各种不同性质的假设，比如在Laplacian
Eigenmaps中要假设这个流形是紧致黎曼流形等。对于描述流形上的点，我们要用坐标，而流形上本身是没有坐标的，所以为了表示流形上的点，必须把流形放入外围空间（ambient space）中，那末流形上的点就可以用外围空间的坐标来表示。比如R^3中的球面是个2维的曲面，因为球面上只有两个自由度，但是球面上的点一般是用外围R^3空间中的坐标表示的，所以我们看到的R^3中球面上的点有3个数来表示的。当然球面还有柱坐标球坐标等表示。对于R^3中的球面来说，那末流形学习可以粗略的概括为给出R^3中的表示，在保持球面上点某些几何性质的条件下，找出找到一组对应的内蕴坐标（intrinsic coordinate）表示，显然这个表示应该是两维的，因为球面的维数是两维的。这个过程也叫参数化（parameterization）。直观上来说，就是把这个球面尽量好的展开在通过原点的平面上。在PAMI中，这样的低维表示也叫内蕴特征（intrinsic feature）。一般外围空间的维数也叫观察维数，其表示也叫自然坐标（外围空间是欧式空间）表示,在统计中一般叫observation。
了解了流形学习的这个基础，那末流形学习中的一些是非也就很自然了，这个下面穿插来说。由此，如果你想学好流形学习里的方法，你至少要了解一些微分流形和黎曼几何的基本知识。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap开创了一个数据处理的新战场。在没有具体说Isomap之前，有必要先说说MDS（Multidimensional Scaling）这个方法。我们国内的很多人知道PCA，却很多人不知道MDS。PCA和MDS是相互对偶的两个方法。MDS就是理论上保持欧式距离的一个经典方法，MDS最早主要用于做数据的可视化。由于MDS得到的低维表示中心在原点，所以又可以说保持内积。也就是说，用低维空间中的内积近似高维空间中的距离。经典的MDS方法，高维空间中的距离一般用欧式距离。
Isomap就是借窝生蛋。他的理论框架就是MDS，但是放在流形的理论框架内，原始的距离换成了流形上的测地线（geodesic）距离。其它一模一样。所谓的测地线，就是流形上加速度为零的曲线，等同于欧式空间中的直线。我们经常听到说测地线是流形上两点之间距离最短的线。其实这末说是不严谨的。流形上两点之间距离最短的线是测地线，但是反过来不一定对。另外，如果任意两个点之间都存在一个测地线，那末这个流形必须是连通的邻域都是凸的。Isomap就是把任意两点的测地线距离（准确地说是最短距离）作为流形的几何描述，用MDS理论框架
理论上保持这个点与点之间的最短距离。在Isomap中，测地线距离就是用两点之间图上的最短距离来近似的，这方面的算法是一般计算机系中用的图论中的经典算法。
如果你曾细致地看过Isomap主页上的matlab代码，你就会发现那个代码的实现复杂度远超与实际论文中叙述的算法。在那个代码中，除了论文中写出的算法外，还包括了 outlier detection和embedding scaling。这两样东西，保证了运行他们的程序得到了结果一般来说相对比较理想。但是，这在他们的算法中并没有叙述。如果你直接按照他论文中的方法来实现，你可以体会一下这个结果和他们结果的差距。从此我们也可以看出，那几个作者做学问的严谨态度，这是值得我们好好学习的。
另外比较有趣的是，Tenenbaum根本不是做与数据处理有关算法的人，他是做计算认知科学（computational cognition science）的。在做这个方法的时候，他还在stanford，02年就去了
MIT开创一派，成了CoCoSci 的掌门人，他的组成长十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT带的学生就从来再也没有做过类似的工作。其原因我今年夏天有所耳闻。他在今年参加 UCLA Alan Yuille 组织的一个summer school上说，（不是原文，是大意）我们经常忘了做研究的原始出发点是什莫。他做Isomap就是为了找一个好的visual perception的方法，他还坚持了他的方向和信仰，computational cognition，他没有随波逐流。而由他引导起来的 manifold learning 却快速的发展成了一个新的方向。
这是一个值得我们好好思考的问题。我们做一个东西，选择一个研究方向究竟是为了什莫。你考虑过吗？
（当然，此问题也在问我自己）
b) LLE (Locally linear Embedding)
LLE在作者写出的表达式看,是个具有十分对称美的方法. 这种看上去的对称对于启发人很重要。LLE的思想就是，一个流形在很小的局部邻域上可以近似看成欧式的，就是局部线性的。那末，在小的局部邻域上，一个点就可以用它周围的点在最小二乘意义下最优的线性表示。LLE把这个线性拟合的系数当成这个流形局部几何性质的刻画。那末一个好的低维表示，就应该也具有同样的局部几何，所以利用同样的线性表示的表达式，最终写成一个二次型的形式，十分自然优美。
注意在LLE出现的两个加和优化的线性表达，第一个是求每一点的线性表示系数的。虽然原始公式中是写在一起的，但是求解时，是对每一个点分别来求得。第二个表示式，是已知所有点的线性表示系数，来求低维表示（或嵌入embedding）的，他是一个整体求解的过程。这两个表达式的转化正好中间转了个弯，使一些人困惑了，特别后面一个公式写成一个二次型的过程并不是那末直观，很多人往往在此卡住，而阻碍了全面的理解。我推荐大家去精读 Saul 在
JMLR上的那篇LLE的长文。那篇文章无论在方法表达还是英文书写，我认为都是精品，值得好好玩味学习。
另外值得强调的是，对于每一点处拟合得到的系数归一化的操作特别重要，如果没有这一步，这个算法就没有效果。但是在原始论文中，他们是为了保持数据在平行移动下embedding不变。 LLE的matlab代码写得简洁明了，是一个样板。
在此有必要提提Lawrence Saul这个人。在Isomap和LLE的作者们中，Saul算是唯一一个以流形学习（并不限于）为研究对象开创学派的人。Saul早年主要做参数模型有关的算法。自从LLE以后，坐阵UPen创造了一个个佳绩。主要成就在于他的两个出色学生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多奖，在此不多说，可以到他主页上去看。Weinberger把学习核矩阵引入到流形学习中来。他的这个方法在流形学习中影响到不是很显著，却是在 convex optimization 中人人得知。Fei Sha不用多说了，machine learning中一个闪亮的新星，中国留学生之骄傲。现在他们一个在Yahoo,一个在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要说哪一个方法被做的全面，那莫非LE莫属。如果只说LE这个方法本身，是不新的，许多年前在做mesh相关的领域就开始这莫用。但是放在黎曼几何的框架内，给出完整的几何分析的，应该是Belkin和Niyogi（LE作者）的功劳。
LE的基本思想就是用一个无向有权图来描述一个流形，然后通过用图的嵌入（graph
embedding）来找低维表示。说白了，就是保持图的局部邻接关系的情况把这个图从高维空间中重新画在一个低维空间中（graph drawing）。
在至今为止的流行学习的典型方法中，LE是速度最快、效果相对来说不怎莫样的。但是LE有一个其他方法没有的特点，就是如果出现outlier情况下，它的鲁棒性（robustness）特别好。 后来Belkin和Niyogi又分析了LE的收敛性。大家不要忽视这个问题，很重要。鼓励有兴趣数学功底不错的人好好看看这篇文章。
d) Hessian Eigenmaps
如果你对黎曼几何不懂，基本上看不懂这个方法。又加作者表达的抽象，所以绝大多数人对这个方法了解不透彻。在此我就根据我自己的理解说说这个方法。
这个方法有两个重点：（1）如果一个流形是局部等距（isometric）欧式空间中一个开子集的，那末它的Hessian矩阵具有d+1维的零空间。（2）在每一点处，Hessian系数的估计。
首先作者是通过考察局部Hessian的二次型来得出结论的，如果一个流形局部等距于欧式空间中的一个开子集，那末由这个流形patch 到开子集到的映射函数是一个线性函数，线性函数的二次混合导数为零，所以局部上由Hessian系数构成的二次型也为零，这样把每一点都考虑到，过渡到全局的Hessian矩阵就有d+1维的零空间，其中一维是常函数构成的，也就是1向量。其它的d维子空间构成等距坐标。这就是理论基础的大意，当然作者在介绍的时候，为了保持理论严谨，作了一个由切坐标到等距坐标的过渡。
另外一个就是局部上Hessian系数的估计问题。我在此引用一段话：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
这段话是我在初学HE时候，写信问Dave Donoho，他给我的回信。希望大家领会。如果你了解了上述基本含义，再去细看两遍原始论文，也许会有更深的理解。由于HE牵扯到二阶导数的估计，所以对噪声很敏感。另外，HE的原始代码中在计算局部切坐标的时候，用的是奇异值分解(SVD)，所以如果想用他们的原始代码跑一下例如图像之类的真实数据，就特别的慢。其实把他们的代码改一下就可以了，利用一般PCA的快速计算方法，计算小尺寸矩阵的特征向量即可。还有，在原始代码中，他把Hessian系数归一化了，这也就是为什莫他们叫这个方法为 Hessian LLE 的原因之一。
Dave Dohono是学术界公认的大牛，在流形学习这一块，是他带着他的一个学生做的，Carrie Grimes。现在这个女性研究员在Google做 project leader，学术界女生同学的楷模 : )
e) LTSA (Local tangent space alignment)
很荣幸，这个是国内学者（浙江大学数学系的老师ZHANG Zhenyue）为第一作者做的一个在流行学习中最出色的方法。由于这个方法是由纯数学做数值分析出身的老师所做，所以原始论文看起来公式一大堆，好像很难似的。其实这个方法非常直观简单。
象 Hessian Eigenmaps 一样，流形的局部几何表达先用切坐标，也就是PCA的主子空间中的坐标。那末对于流形一点处的切空间，它是线性子空间，所以可以和欧式空间中的一个开子集建立同构关系，最简单的就是线性变换。在微分流形中，就叫做切映射 (tangential map)，是个很自然很基础的概念。把切坐标求出来，建立出切映射，剩下的就是数值计算了。最终这个算法划归为一个很简单的跌代加和形式。如果你已经明白了MDS，那末你就很容易明白，这个算法本质上就是MDS的从局部到整体的组合。
这里主要想重点强调一下，那个论文中使用的一个从局部几何到整体性质过渡的alignment技术。在spectral method（特征分解的）中，这个alignment方法特别有用。只要在数据的局部邻域上你的方法可以写成一个二次项的形式，就可以用。
其实LTSA最早的版本是在02年的DOCIS上。这个alignment方法在02年底Brand的 charting a manifold 中也出现，隐含在Hessian Eigenmaps中。在HE中，作者在从局部的Hessian矩阵过渡到全局的Hessian矩阵时，用了两层加号，其中就隐含了这个 alignment方法。后来国内一个叫 ZHAO Deli 的学生用这个方法重新写了LLE，发在Pattern Recognition上，一个短文。可以预见的是，这个方法还会被发扬光大。
ZHA Hongyuan 后来专门作了一篇文章来分析 alignment matrix 的谱性质，有兴趣地可以找来看看。
f) MVU (Maximum variance unfolding)
这个方法刚发出来以后，名字叫做Semi-definite Embedding (SDE)。构建一个局部的稀疏欧式距离矩阵以后，作者通过一定约束条件（主要是保持距离）来学习到一个核矩阵，对这个核矩阵做PCA就得到保持距离的 embedding，就这莫简单。但是就是这个方法得了多少奖，自己可以去找找看。个人观点认为，这个方法之所以被如此受人赏识，无论在vision还是在learning，除了给流形学习这一领域带来了一个新的解决问题的工具之外，还有两个重点，一是核方法（kernel），二是半正定规划（semi-definite programming），这两股风无论在哪个方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
这个方法不太被人所知，但是我认为这个是流形学习发展中的一个典型的方法（其实其他还有很多人也这莫认为）。就效果来说，这个方法不算好，说它是一个典型的方法，是因为这个方法应用了黎曼几何中一个很直观的性质。这个性质和法坐标(normal coordinate)、指数映射(exponential map)和距离函数(distance function)有关。
如果你了解黎曼几何，你会知道，对于流形上的一条测地线，如果给定初始点和初始点处测地线的切方向，那莫这个测地线就可以被唯一确定。这是因为在这些初始条件下，描述测地线的偏微分方程的解是唯一的。那末流形上的一条测地线就可以和其起点处的切平面上的点建立一个对应关系。我们可以在这个切平面上找到一点，这个点的方向就是这个测地线在起点处的切方向，其长度等于这个测地线上的长。这样的一个对应关系在局部上是一一对应的。那末这个在切平面上的对应点在切平面中就有一个坐标表示，这个表示就叫做测地线上对应点的法坐标表示（有的也叫指数坐标）。那末反过来，我们可以把切平面上的点映射到流形上，这个映射过程就叫做指数映射（Logmap就倒过来）。如果流形上每一个点都可以这样在同一个切平面上表示出来，那末我们就可以得到保持测地线长度的低维表示。如果这样做得到，流形必须可以被单坐标系统所覆盖。
如果给定流形上的采样点，如果要找到法坐标，我们需要知道两个东西，一是测地线距离，二是每个测地线在起点处的切方向。第一个东西好弄，利用Isomap中的方法直接就可以解决，关键是第二个。第二个作者利用了距离函数的梯度，这个梯度和那个切方向是一个等价的关系，一般的黎曼几何书中都有叙述。作者利用一个局部切坐标的二次泰勒展开来近似距离函数，而距离是知道的，就是测地线距离，局部切坐标也知道，那末通过求一个简单的最小二乘问题就可以估计出梯度方向。
如果明白这个方法的几何原理，你再去看那个方法的结果，你就会明白为什莫在距离中心点比较远的点的embedding都可以清楚地看到在一条条线上，效果不太好。
最近这个思想被北大的一个年轻的老师 LIN Tong 发扬光大，就是ECCV‘06上的那篇，还有即将刊登出的TPAMI上的 Riemannian Manifold Learning，实为国内研究学者之荣幸。Lin的方法效果非常好，但是虽然取名叫Riemannian，没有应用到黎曼几何本身的性质，这样使他的方法更容易理解。
Lin也是以一个切空间为基准找法坐标，这个出发点和思想和Brun（S-Logmaps）的是一样的。但是Lin全是在局部上操作的，在得出切空间原点处局部邻域的法坐标以后，Lin采用逐步向外扩展的方法找到其他点的法坐标，在某一点处，保持此点到它邻域点的欧式距离和夹角，然后转化成一个最小二乘问题求出此点的法坐标，这样未知的利用已知的逐步向外扩展。说白了就像缝网一样，从几个临近的已知点开始，逐渐向外扩散的缝。效果好是必然的。
浅谈流形学习
bypluskid, on 2010-05-29, in Machine Learning76 comments
总觉得即使是“浅谈”两个字，还是让这个标
题有些过大了，更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了，想起来要扯一下这个话题，也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉，不过如果并不是想要进行严格的理论推导的话，也可以从许多直观的例子得到一些感性的认识，正好我也就借这个机会来简单地谈一下这个话题吧，或者说至少是我到目前为止对这它的认识。 这两个词，在谈 Manifold 之前，不妨先说说 Learning ，也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科，因为每当它的一个子领域发展得像模像样之后，就立马自立门户，从此和 AI “再无瓜葛”了，而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪，比如说数学，分门别类总算是够多了吧？可以不管怎么分，大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢？我觉得这里有很大一部分
是它自身定位的问题。
反正现在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
说 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是这相当于一个 tautology ，因为到底什么又是the intelligence of machines呢？一开始的时候，大牛们都野心勃勃，而且好像也是信心满满，就好像曾经广泛认为“牛顿定理揭示了宇宙真理，科学剩下的事情只要按照公式来做计算就可以了”一样，大家可能觉得，不出几十年，人类就可以不用思考，交给 AI 来做了。不过我这里并不想再多说诸如什么是“思考”，什么是“智能”之类的以及随之而来的“图灵测试”之类的话题。我想说的是，到头来，AI 到底是什么，这还是一个问题，或者说，AI 在一开始定了一个过高的目标，几十年后，发现情况并不像当年那么乐观，却又有些下不了台了。
这个时候，AI 的一些旁枝或者子领域果断放下面子，丢掉了那个近乎玄幻的目标，逐渐发展成为“正常”的学科，所以也就不再好称为 AI 了。或者说现在的 AI 有两个意思，一个广义的 AI ，包括了所有相关的以及派生的领域，另一个则是狭义的或者经典的 AI ，专门指那些仍然在执着地追求着真正的“智能”的部分，或者说得不好听一点，就
是剩下的部分。
Machine Learning 作为离家出走的典型，虽然名字里带了 Learning 一个词，让人乍一看觉得和 Intelligence 相比不过是换了个说法而已，然而事实上这里的 Learning 的意义要朴素得多。我们来看一看 Machine Learning 的典型的流程就知道了，其实有时候觉得和应用数学或者更通俗的数学建模有些类似，通常我们会有需要分析或者处理的数据，根据一些经验和一些假设，我们可以构建一个模型，这个模型会有一些参数（即使是非参数化方法，也是可以类似地看待的），根据数据来求解模型参数的过程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞机器学习的人，通常把它叫做 Learning （或者，换一个角度，叫 Training）——因为根据数据归纳出一个有用的模型，这和我们人类“学习”的过程还是挺类似的吧。不过，如果抛开无聊的抠字眼游戏的话，我们可以看到，Machine Learning 已经抛弃了“智能”的高帽子，它的目的就是要解决具
体的问题——而并不关心是否是通过一种“智能”的方式类解决的。
说到这里，其实我们构造模型就类似于写一个类，数据就是构造函数的参数，Learning 就是构造函数运行的过程，成功构造一个对象之后，我们就完成了学习。一些 Machine Learning 的问题到这一步就结束了，另一些情况还会使用得到的模型（对象）对后来的数据进行一些处理，通常会是Inferencing。到这个时候，又有些像统计里的东西了，所谓“统计推断”嘛。其实原本统计和机器学习研究的不少问题就是交叉在一起的，不过两派人从不同的角度来看待同样的问题。而且，也确实有 Statistical Learning 这么一个说法存在的，可以把他看成是 Machine Learning 的一个子领域（或者是一个分子或
者甚至就是 Machine Learning 本身）。
到这里，如果你还没有因为不断地抠字眼而烦躁的话，
我已经忍无可忍了。所以，我就假定你已经了解了什么叫 Learning ，或者是已经恶心到懒得去了解了。于是我们转入下一个话题：流形，也就是 Manifold 。不知道你有没有为我在本文开头放上的那个地球的图片感到困惑？这是因为球面是一个很典型的流
形的例子，而地球就是一个很典型的“球面”啦（姑且当作球面好啦）。
有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”，不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像，所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布，可以把它看成一个二维平面，这是一个
二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不
扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况）。
所以，直观上来讲，一个流形好比是一个 d 维的空间，在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是，流形并不是一个“形状”，而是一个“空间”，如果你觉得“扭曲的空间”难以想象，那么请再回忆之前一块布的例子。如果我没弄错的话，广义相对论似乎就是把我们的时空当作一个四维流（空间三维加上时间一维）形来研究的，引力就是这个流形扭曲的结果。当然，这些都是直观上的概念，其实流形并不需要依靠嵌入在一个“外围空间”而存在，稍微正式一点来说，一个 d 维的流形就是一个在任意点出局部同胚于（简单地说，就是正逆映射都是光滑的一一映射）欧氏空间。
实际上，正是这种局部与欧氏空间的同
胚给我们带来了很多好处，这使得我们在日常生活中许许多多的几何问题都可以使用简单的欧氏几何来解决，因为和地球的尺度比起来，我们的日常生活就算是一个很小的局部啦——我突然想起《七龙珠》里的那个界王住的那种私人小星球，走几步就要绕一圈的感觉，看来界王不仅要体力好（那上面重力似乎是地球的十倍），而且脑力也要好，
初中学的必须是黎曼几何了！
那么，除了地球这种简单的例子，实际应用中的数据，怎么知道它是不是一个流形呢？于是不妨又回归直观的感觉。再从球面说起，如果我们事先不知道球面的存在，那么球面上的点，其实就是三维欧氏空间上的点，可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是，它们允许出现的位置受到了一定的限制，具体到球面，可以
可以看一下它的参数方程：
可以看到，这些三维的坐标实际上是由两个变量和生成的，也可以说成是它的自由度是二，也正好对应了它是一个二维的流形。有了这样的感觉之后，再来看流形学习里经
常用到的人脸的例子，就很自然了。下图是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 上的最短路径来近似了。
流形学习
流形学习是个很广泛的概念。这里我主要谈的是自从2000年以后形成的流形学习概念和其主要代表方法。自从2000年以后，流形学习被认为属于非线性降维的一个分支。众所周知，引导这一领域迅速发展的是2000年Science杂志上的两篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形学习的基本概念
那流形学习是什莫呢？为了好懂，我尽可能应用少的数学概念来解释这个东西。所谓流形（manifold）就是一般的几何对象的总称。比如人，有中国人、美国人等等；流形就包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习把一组在高维空间中的数据在低维空间中重新表示。和以往方法不同的是，在流形学习中有一个假设，就是所处理的数据采样于一个潜在的流形上，或是说对于这组数据存在一个潜在的流形。 对于不同的方法，对于流形性质的要求各不相同，这也就产生了在流形假设下的各种不同性质的假设，比如在Laplacian
Eigenmaps中要假设这个流形是紧致黎曼流形等。对于描述流形上的点，我们要用坐标，而流形上本身是没有坐标的，所以为了表示流形上的点，必须把流形放入外围空间（ambient space）中，那末流形上的点就可以用外围空间的坐标来表示。比如R^3中的球面是个2维的曲面，因为球面上只有两个自由度，但是球面上的点一般是用外围R^3空间中的坐标表示的，所以我们看到的R^3中球面上的点有3个数来表示的。当然球面还有柱坐标球坐标等表示。对于R^3中的球面来说，那末流形学习可以粗略的概括为给出R^3中的表示，在保持球面上点某些几何性质的条件下，找出找到一组对应的内蕴坐标（intrinsic coordinate）表示，显然这个表示应该是两维的，因为球面的维数是两维的。这个过程也叫参数化（parameterization）。直观上来说，就是把这个球面尽量好的展开在通过原点的平面上。在PAMI中，这样的低维表示也叫内蕴特征（intrinsic feature）。一般外围空间的维数也叫观察维数，其表示也叫自然坐标（外围空间是欧式空间）表示,在统计中一般叫observation。
了解了流形学习的这个基础，那末流形学习中的一些是非也就很自然了，这个下面穿插来说。由此，如果你想学好流形学习里的方法，你至少要了解一些微分流形和黎曼几何的基本知识。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap开创了一个数据处理的新战场。在没有具体说Isomap之前，有必要先说说MDS（Multidimensional Scaling）这个方法。我们国内的很多人知道PCA，却很多人不知道MDS。PCA和MDS是相互对偶的两个方法。MDS就是理论上保持欧式距离的一个经典方法，MDS最早主要用于做数据的可视化。由于MDS得到的低维表示中心在原点，所以又可以说保持内积。也就是说，用低维空间中的内积近似高维空间中的距离。经典的MDS方法，高维空间中的距离一般用欧式距离。
Isomap就是借窝生蛋。他的理论框架就是MDS，但是放在流形的理论框架内，原始的距离换成了流形上的测地线（geodesic）距离。其它一模一样。所谓的测地线，就是流形上加速度为零的曲线，等同于欧式空间中的直线。我们经常听到说测地线是流形上两点之间距离最短的线。其实这末说是不严谨的。流形上两点之间距离最短的线是测地线，但是反过来不一定对。另外，如果任意两个点之间都存在一个测地线，那末这个流形必须是连通的邻域都是凸的。Isomap就是把任意两点的测地线距离（准确地说是最短距离）作为流形的几何描述，用MDS理论框架
理论上保持这个点与点之间的最短距离。在Isomap中，测地线距离就是用两点之间图上的最短距离来近似的，这方面的算法是一般计算机系中用的图论中的经典算法。
如果你曾细致地看过Isomap主页上的matlab代码，你就会发现那个代码的实现复杂度远超与实际论文中叙述的算法。在那个代码中，除了论文中写出的算法外，还包括了 outlier detection和embedding scaling。这两样东西，保证了运行他们的程序得到了结果一般来说相对比较理想。但是，这在他们的算法中并没有叙述。如果你直接按照他论文中的方法来实现，你可以体会一下这个结果和他们结果的差距。从此我们也可以看出，那几个作者做学问的严谨态度，这是值得我们好好学习的。
另外比较有趣的是，Tenenbaum根本不是做与数据处理有关算法的人，他是做计算认知科学（computational cognition science）的。在做这个方法的时候，他还在stanford，02年就去了
MIT开创一派，成了CoCoSci 的掌门人，他的组成长十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT带的学生就从来再也没有做过类似的工作。其原因我今年夏天有所耳闻。他在今年参加 UCLA Alan Yuille 组织的一个summer school上说，（不是原文，是大意）我们经常忘了做研究的原始出发点是什莫。他做Isomap就是为了找一个好的visual perception的方法，他还坚持了他的方向和信仰，computational cognition，他没有随波逐流。而由他引导起来的 manifold learning 却快速的发展成了一个新的方向。
这是一个值得我们好好思考的问题。我们做一个东西，选择一个研究方向究竟是为了什莫。你考虑过吗？
（当然，此问题也在问我自己）
b) LLE (Locally linear Embedding)
LLE在作者写出的表达式看,是个具有十分对称美的方法. 这种看上去的对称对于启发人很重要。LLE的思想就是，一个流形在很小的局部邻域上可以近似看成欧式的，就是局部线性的。那末，在小的局部邻域上，一个点就可以用它周围的点在最小二乘意义下最优的线性表示。LLE把这个线性拟合的系数当成这个流形局部几何性质的刻画。那末一个好的低维表示，就应该也具有同样的局部几何，所以利用同样的线性表示的表达式，最终写成一个二次型的形式，十分自然优美。
注意在LLE出现的两个加和优化的线性表达，第一个是求每一点的线性表示系数的。虽然原始公式中是写在一起的，但是求解时，是对每一个点分别来求得。第二个表示式，是已知所有点的线性表示系数，来求低维表示（或嵌入embedding）的，他是一个整体求解的过程。这两个表达式的转化正好中间转了个弯，使一些人困惑了，特别后面一个公式写成一个二次型的过程并不是那末直观，很多人往往在此卡住，而阻碍了全面的理解。我推荐大家去精读 Saul 在
JMLR上的那篇LLE的长文。那篇文章无论在方法表达还是英文书写，我认为都是精品，值得好好玩味学习。
另外值得强调的是，对于每一点处拟合得到的系数归一化的操作特别重要，如果没有这一步，这个算法就没有效果。但是在原始论文中，他们是为了保持数据在平行移动下embedding不变。 LLE的matlab代码写得简洁明了，是一个样板。
在此有必要提提Lawrence Saul这个人。在Isomap和LLE的作者们中，Saul算是唯一一个以流形学习（并不限于）为研究对象开创学派的人。Saul早年主要做参数模型有关的算法。自从LLE以后，坐阵UPen创造了一个个佳绩。主要成就在于他的两个出色学生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多奖，在此不多说，可以到他主页上去看。Weinberger把学习核矩阵引入到流形学习中来。他的这个方法在流形学习中影响到不是很显著，却是在 convex optimization 中人人得知。Fei Sha不用多说了，machine learning中一个闪亮的新星，中国留学生之骄傲。现在他们一个在Yahoo,一个在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要说哪一个方法被做的全面，那莫非LE莫属。如果只说LE这个方法本身，是不新的，许多年前在做mesh相关的领域就开始这莫用。但是放在黎曼几何的框架内，给出完整的几何分析的，应该是Belkin和Niyogi（LE作者）的功劳。
LE的基本思想就是用一个无向有权图来描述一个流形，然后通过用图的嵌入（graph
embedding）来找低维表示。说白了，就是保持图的局部邻接关系的情况把这个图从高维空间中重新画在一个低维空间中（graph drawing）。
在至今为止的流行学习的典型方法中，LE是速度最快、效果相对来说不怎莫样的。但是LE有一个其他方法没有的特点，就是如果出现outlier情况下，它的鲁棒性（robustness）特别好。 后来Belkin和Niyogi又分析了LE的收敛性。大家不要忽视这个问题，很重要。鼓励有兴趣数学功底不错的人好好看看这篇文章。
d) Hessian Eigenmaps
如果你对黎曼几何不懂，基本上看不懂这个方法。又加作者表达的抽象，所以绝大多数人对这个方法了解不透彻。在此我就根据我自己的理解说说这个方法。
这个方法有两个重点：（1）如果一个流形是局部等距（isometric）欧式空间中一个开子集的，那末它的Hessian矩阵具有d+1维的零空间。（2）在每一点处，Hessian系数的估计。
首先作者是通过考察局部Hessian的二次型来得出结论的，如果一个流形局部等距于欧式空间中的一个开子集，那末由这个流形patch 到开子集到的映射函数是一个线性函数，线性函数的二次混合导数为零，所以局部上由Hessian系数构成的二次型也为零，这样把每一点都考虑到，过渡到全局的Hessian矩阵就有d+1维的零空间，其中一维是常函数构成的，也就是1向量。其它的d维子空间构成等距坐标。这就是理论基础的大意，当然作者在介绍的时候，为了保持理论严谨，作了一个由切坐标到等距坐标的过渡。
另外一个就是局部上Hessian系数的估计问题。我在此引用一段话：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
这段话是我在初学HE时候，写信问Dave Donoho，他给我的回信。希望大家领会。如果你了解了上述基本含义，再去细看两遍原始论文，也许会有更深的理解。由于HE牵扯到二阶导数的估计，所以对噪声很敏感。另外，HE的原始代码中在计算局部切坐标的时候，用的是奇异值分解(SVD)，所以如果想用他们的原始代码跑一下例如图像之类的真实数据，就特别的慢。其实把他们的代码改一下就可以了，利用一般PCA的快速计算方法，计算小尺寸矩阵的特征向量即可。还有，在原始代码中，他把Hessian系数归一化了，这也就是为什莫他们叫这个方法为 Hessian LLE 的原因之一。
Dave Dohono是学术界公认的大牛，在流形学习这一块，是他带着他的一个学生做的，Carrie Grimes。现在这个女性研究员在Google做 project leader，学术界女生同学的楷模 : )
e) LTSA (Local tangent space alignment)
很荣幸，这个是国内学者（浙江大学数学系的老师ZHANG Zhenyue）为第一作者做的一个在流行学习中最出色的方法。由于这个方法是由纯数学做数值分析出身的老师所做，所以原始论文看起来公式一大堆，好像很难似的。其实这个方法非常直观简单。
象 Hessian Eigenmaps 一样，流形的局部几何表达先用切坐标，也就是PCA的主子空间中的坐标。那末对于流形一点处的切空间，它是线性子空间，所以可以和欧式空间中的一个开子集建立同构关系，最简单的就是线性变换。在微分流形中，就叫做切映射 (tangential map)，是个很自然很基础的概念。把切坐标求出来，建立出切映射，剩下的就是数值计算了。最终这个算法划归为一个很简单的跌代加和形式。如果你已经明白了MDS，那末你就很容易明白，这个算法本质上就是MDS的从局部到整体的组合。
这里主要想重点强调一下，那个论文中使用的一个从局部几何到整体性质过渡的alignment技术。在spectral method（特征分解的）中，这个alignment方法特别有用。只要在数据的局部邻域上你的方法可以写成一个二次项的形式，就可以用。
其实LTSA最早的版本是在02年的DOCIS上。这个alignment方法在02年底Brand的 charting a manifold 中也出现，隐含在Hessian Eigenmaps中。在HE中，作者在从局部的Hessian矩阵过渡到全局的Hessian矩阵时，用了两层加号，其中就隐含了这个 alignment方法。后来国内一个叫 ZHAO Deli 的学生用这个方法重新写了LLE，发在Pattern Recognition上，一个短文。可以预见的是，这个方法还会被发扬光大。
ZHA Hongyuan 后来专门作了一篇文章来分析 alignment matrix 的谱性质，有兴趣地可以找来看看。
f) MVU (Maximum variance unfolding)
这个方法刚发出来以后，名字叫做Semi-definite Embedding (SDE)。构建一个局部的稀疏欧式距离矩阵以后，作者通过一定约束条件（主要是保持距离）来学习到一个核矩阵，对这个核矩阵做PCA就得到保持距离的 embedding，就这莫简单。但是就是这个方法得了多少奖，自己可以去找找看。个人观点认为，这个方法之所以被如此受人赏识，无论在vision还是在learning，除了给流形学习这一领域带来了一个新的解决问题的工具之外，还有两个重点，一是核方法（kernel），二是半正定规划（semi-definite programming），这两股风无论在哪个方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
这个方法不太被人所知，但是我认为这个是流形学习发展中的一个典型的方法（其实其他还有很多人也这莫认为）。就效果来说，这个方法不算好，说它是一个典型的方法，是因为这个方法应用了黎曼几何中一个很直观的性质。这个性质和法坐标(normal coordinate)、指数映射(exponential map)和距离函数(distance function)有关。
如果你了解黎曼几何，你会知道，对于流形上的一条测地线，如果给定初始点和初始点处测地线的切方向，那莫这个测地线就可以被唯一确定。这是因为在这些初始条件下，描述测地线的偏微分方程的解是唯一的。那末流形上的一条测地线就可以和其起点处的切平面上的点建立一个对应关系。我们可以在这个切平面上找到一点，这个点的方向就是这个测地线在起点处的切方向，其长度等于这个测地线上的长。这样的一个对应关系在局部上是一一对应的。那末这个在切平面上的对应点在切平面中就有一个坐标表示，这个表示就叫做测地线上对应点的法坐标表示（有的也叫指数坐标）。那末反过来，我们可以把切平面上的点映射到流形上，这个映射过程就叫做指数映射（Logmap就倒过来）。如果流形上每一个点都可以这样在同一个切平面上表示出来，那末我们就可以得到保持测地线长度的低维表示。如果这样做得到，流形必须可以被单坐标系统所覆盖。
如果给定流形上的采样点，如果要找到法坐标，我们需要知道两个东西，一是测地线距离，二是每个测地线在起点处的切方向。第一个东西好弄，利用Isomap中的方法直接就可以解决，关键是第二个。第二个作者利用了距离函数的梯度，这个梯度和那个切方向是一个等价的关系，一般的黎曼几何书中都有叙述。作者利用一个局部切坐标的二次泰勒展开来近似距离函数，而距离是知道的，就是测地线距离，局部切坐标也知道，那末通过求一个简单的最小二乘问题就可以估计出梯度方向。
如果明白这个方法的几何原理，你再去看那个方法的结果，你就会明白为什莫在距离中心点比较远的点的embedding都可以清楚地看到在一条条线上，效果不太好。
最近这个思想被北大的一个年轻的老师 LIN Tong 发扬光大，就是ECCV‘06上的那篇，还有即将刊登出的TPAMI上的 Riemannian Manifold Learning，实为国内研究学者之荣幸。Lin的方法效果非常好，但是虽然取名叫Riemannian，没有应用到黎曼几何本身的性质，这样使他的方法更容易理解。
Lin也是以一个切空间为基准找法坐标，这个出发点和思想和Brun（S-Logmaps）的是一样的。但是Lin全是在局部上操作的，在得出切空间原点处局部邻域的法坐标以后，Lin采用逐步向外扩展的方法找到其他点的法坐标，在某一点处，保持此点到它邻域点的欧式距离和夹角，然后转化成一个最小二乘问题求出此点的法坐标，这样未知的利用已知的逐步向外扩展。说白了就像缝网一样，从几个临近的已知点开始，逐渐向外扩散的缝。效果好是必然的。
浅谈流形学习
bypluskid, on 2010-05-29, in Machine Learning76 comments
总觉得即使是“浅谈”两个字，还是让这个标
题有些过大了，更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了，想起来要扯一下这个话题，也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉，不过如果并不是想要进行严格的理论推导的话，也可以从许多直观的例子得到一些感性的认识，正好我也就借这个机会来简单地谈一下这个话题吧，或者说至少是我到目前为止对这它的认识。 这两个词，在谈 Manifold 之前，不妨先说说 Learning ，也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科，因为每当它的一个子领域发展得像模像样之后，就立马自立门户，从此和 AI “再无瓜葛”了，而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪，比如说数学，分门别类总算是够多了吧？可以不管怎么分，大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢？我觉得这里有很大一部分
是它自身定位的问题。
反正现在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
说 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是这相当于一个 tautology ，因为到底什么又是the intelligence of machines呢？一开始的时候，大牛们都野心勃勃，而且好像也是信心满满，就好像曾经广泛认为“牛顿定理揭示了宇宙真理，科学剩下的事情只要按照公式来做计算就可以了”一样，大家可能觉得，不出几十年，人类就可以不用思考，交给 AI 来做了。不过我这里并不想再多说诸如什么是“思考”，什么是“智能”之类的以及随之而来的“图灵测试”之类的话题。我想说的是，到头来，AI 到底是什么，这还是一个问题，或者说，AI 在一开始定了一个过高的目标，几十年后，发现情况并不像当年那么乐观，却又有些下不了台了。
这个时候，AI 的一些旁枝或者子领域果断放下面子，丢掉了那个近乎玄幻的目标，逐渐发展成为“正常”的学科，所以也就不再好称为 AI 了。或者说现在的 AI 有两个意思，一个广义的 AI ，包括了所有相关的以及派生的领域，另一个则是狭义的或者经典的 AI ，专门指那些仍然在执着地追求着真正的“智能”的部分，或者说得不好听一点，就
是剩下的部分。
Machine Learning 作为离家出走的典型，虽然名字里带了 Learning 一个词，让人乍一看觉得和 Intelligence 相比不过是换了个说法而已，然而事实上这里的 Learning 的意义要朴素得多。我们来看一看 Machine Learning 的典型的流程就知道了，其实有时候觉得和应用数学或者更通俗的数学建模有些类似，通常我们会有需要分析或者处理的数据，根据一些经验和一些假设，我们可以构建一个模型，这个模型会有一些参数（即使是非参数化方法，也是可以类似地看待的），根据数据来求解模型参数的过程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞机器学习的人，通常把它叫做 Learning （或者，换一个角度，叫 Training）——因为根据数据归纳出一个有用的模型，这和我们人类“学习”的过程还是挺类似的吧。不过，如果抛开无聊的抠字眼游戏的话，我们可以看到，Machine Learning 已经抛弃了“智能”的高帽子，它的目的就是要解决具
体的问题——而并不关心是否是通过一种“智能”的方式类解决的。
说到这里，其实我们构造模型就类似于写一个类，数据就是构造函数的参数，Learning 就是构造函数运行的过程，成功构造一个对象之后，我们就完成了学习。一些 Machine Learning 的问题到这一步就结束了，另一些情况还会使用得到的模型（对象）对后来的数据进行一些处理，通常会是Inferencing。到这个时候，又有些像统计里的东西了，所谓“统计推断”嘛。其实原本统计和机器学习研究的不少问题就是交叉在一起的，不过两派人从不同的角度来看待同样的问题。而且，也确实有 Statistical Learning 这么一个说法存在的，可以把他看成是 Machine Learning 的一个子领域（或者是一个分子或
者甚至就是 Machine Learning 本身）。
到这里，如果你还没有因为不断地抠字眼而烦躁的话，
我已经忍无可忍了。所以，我就假定你已经了解了什么叫 Learning ，或者是已经恶心到懒得去了解了。于是我们转入下一个话题：流形，也就是 Manifold 。不知道你有没有为我在本文开头放上的那个地球的图片感到困惑？这是因为球面是一个很典型的流
形的例子，而地球就是一个很典型的“球面”啦（姑且当作球面好啦）。
有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”，不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像，所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布，可以把它看成一个二维平面，这是一个
二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不
扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况）。
所以，直观上来讲，一个流形好比是一个 d 维的空间，在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是，流形并不是一个“形状”，而是一个“空间”，如果你觉得“扭曲的空间”难以想象，那么请再回忆之前一块布的例子。如果我没弄错的话，广义相对论似乎就是把我们的时空当作一个四维流（空间三维加上时间一维）形来研究的，引力就是这个流形扭曲的结果。当然，这些都是直观上的概念，其实流形并不需要依靠嵌入在一个“外围空间”而存在，稍微正式一点来说，一个 d 维的流形就是一个在任意点出局部同胚于（简单地说，就是正逆映射都是光滑的一一映射）欧氏空间。
实际上，正是这种局部与欧氏空间的同
胚给我们带来了很多好处，这使得我们在日常生活中许许多多的几何问题都可以使用简单的欧氏几何来解决，因为和地球的尺度比起来，我们的日常生活就算是一个很小的局部啦——我突然想起《七龙珠》里的那个界王住的那种私人小星球，走几步就要绕一圈的感觉，看来界王不仅要体力好（那上面重力似乎是地球的十倍），而且脑力也要好，
初中学的必须是黎曼几何了！
那么，除了地球这种简单的例子，实际应用中的数据，怎么知道它是不是一个流形呢？于是不妨又回归直观的感觉。再从球面说起，如果我们事先不知道球面的存在，那么球面上的点，其实就是三维欧氏空间上的点，可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是，它们允许出现的位置受到了一定的限制，具体到球面，可以
可以看一下它的参数方程：
可以看到，这些三维的坐标实际上是由两个变量和生成的，也可以说成是它的自由度是二，也正好对应了它是一个二维的流形。有了这样的感觉之后，再来看流形学习里经
常用到的人脸的例子，就很自然了。下图是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 上的最短路径来近似了。
流形学习
流形学习是个很广泛的概念。这里我主要谈的是自从2000年以后形成的流形学习概念和其主要代表方法。自从2000年以后，流形学习被认为属于非线性降维的一个分支。众所周知，引导这一领域迅速发展的是2000年Science杂志上的两篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形学习的基本概念
那流形学习是什莫呢？为了好懂，我尽可能应用少的数学概念来解释这个东西。所谓流形（manifold）就是一般的几何对象的总称。比如人，有中国人、美国人等等；流形就包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习把一组在高维空间中的数据在低维空间中重新表示。和以往方法不同的是，在流形学习中有一个假设，就是所处理的数据采样于一个潜在的流形上，或是说对于这组数据存在一个潜在的流形。 对于不同的方法，对于流形性质的要求各不相同，这也就产生了在流形假设下的各种不同性质的假设，比如在Laplacian
Eigenmaps中要假设这个流形是紧致黎曼流形等。对于描述流形上的点，我们要用坐标，而流形上本身是没有坐标的，所以为了表示流形上的点，必须把流形放入外围空间（ambient space）中，那末流形上的点就可以用外围空间的坐标来表示。比如R^3中的球面是个2维的曲面，因为球面上只有两个自由度，但是球面上的点一般是用外围R^3空间中的坐标表示的，所以我们看到的R^3中球面上的点有3个数来表示的。当然球面还有柱坐标球坐标等表示。对于R^3中的球面来说，那末流形学习可以粗略的概括为给出R^3中的表示，在保持球面上点某些几何性质的条件下，找出找到一组对应的内蕴坐标（intrinsic coordinate）表示，显然这个表示应该是两维的，因为球面的维数是两维的。这个过程也叫参数化（parameterization）。直观上来说，就是把这个球面尽量好的展开在通过原点的平面上。在PAMI中，这样的低维表示也叫内蕴特征（intrinsic feature）。一般外围空间的维数也叫观察维数，其表示也叫自然坐标（外围空间是欧式空间）表示,在统计中一般叫observation。
了解了流形学习的这个基础，那末流形学习中的一些是非也就很自然了，这个下面穿插来说。由此，如果你想学好流形学习里的方法，你至少要了解一些微分流形和黎曼几何的基本知识。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap开创了一个数据处理的新战场。在没有具体说Isomap之前，有必要先说说MDS（Multidimensional Scaling）这个方法。我们国内的很多人知道PCA，却很多人不知道MDS。PCA和MDS是相互对偶的两个方法。MDS就是理论上保持欧式距离的一个经典方法，MDS最早主要用于做数据的可视化。由于MDS得到的低维表示中心在原点，所以又可以说保持内积。也就是说，用低维空间中的内积近似高维空间中的距离。经典的MDS方法，高维空间中的距离一般用欧式距离。
Isomap就是借窝生蛋。他的理论框架就是MDS，但是放在流形的理论框架内，原始的距离换成了流形上的测地线（geodesic）距离。其它一模一样。所谓的测地线，就是流形上加速度为零的曲线，等同于欧式空间中的直线。我们经常听到说测地线是流形上两点之间距离最短的线。其实这末说是不严谨的。流形上两点之间距离最短的线是测地线，但是反过来不一定对。另外，如果任意两个点之间都存在一个测地线，那末这个流形必须是连通的邻域都是凸的。Isomap就是把任意两点的测地线距离（准确地说是最短距离）作为流形的几何描述，用MDS理论框架
理论上保持这个点与点之间的最短距离。在Isomap中，测地线距离就是用两点之间图上的最短距离来近似的，这方面的算法是一般计算机系中用的图论中的经典算法。
如果你曾细致地看过Isomap主页上的matlab代码，你就会发现那个代码的实现复杂度远超与实际论文中叙述的算法。在那个代码中，除了论文中写出的算法外，还包括了 outlier detection和embedding scaling。这两样东西，保证了运行他们的程序得到了结果一般来说相对比较理想。但是，这在他们的算法中并没有叙述。如果你直接按照他论文中的方法来实现，你可以体会一下这个结果和他们结果的差距。从此我们也可以看出，那几个作者做学问的严谨态度，这是值得我们好好学习的。
另外比较有趣的是，Tenenbaum根本不是做与数据处理有关算法的人，他是做计算认知科学（computational cognition science）的。在做这个方法的时候，他还在stanford，02年就去了
MIT开创一派，成了CoCoSci 的掌门人，他的组成长十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT带的学生就从来再也没有做过类似的工作。其原因我今年夏天有所耳闻。他在今年参加 UCLA Alan Yuille 组织的一个summer school上说，（不是原文，是大意）我们经常忘了做研究的原始出发点是什莫。他做Isomap就是为了找一个好的visual perception的方法，他还坚持了他的方向和信仰，computational cognition，他没有随波逐流。而由他引导起来的 manifold learning 却快速的发展成了一个新的方向。
这是一个值得我们好好思考的问题。我们做一个东西，选择一个研究方向究竟是为了什莫。你考虑过吗？
（当然，此问题也在问我自己）
b) LLE (Locally linear Embedding)
LLE在作者写出的表达式看,是个具有十分对称美的方法. 这种看上去的对称对于启发人很重要。LLE的思想就是，一个流形在很小的局部邻域上可以近似看成欧式的，就是局部线性的。那末，在小的局部邻域上，一个点就可以用它周围的点在最小二乘意义下最优的线性表示。LLE把这个线性拟合的系数当成这个流形局部几何性质的刻画。那末一个好的低维表示，就应该也具有同样的局部几何，所以利用同样的线性表示的表达式，最终写成一个二次型的形式，十分自然优美。
注意在LLE出现的两个加和优化的线性表达，第一个是求每一点的线性表示系数的。虽然原始公式中是写在一起的，但是求解时，是对每一个点分别来求得。第二个表示式，是已知所有点的线性表示系数，来求低维表示（或嵌入embedding）的，他是一个整体求解的过程。这两个表达式的转化正好中间转了个弯，使一些人困惑了，特别后面一个公式写成一个二次型的过程并不是那末直观，很多人往往在此卡住，而阻碍了全面的理解。我推荐大家去精读 Saul 在
JMLR上的那篇LLE的长文。那篇文章无论在方法表达还是英文书写，我认为都是精品，值得好好玩味学习。
另外值得强调的是，对于每一点处拟合得到的系数归一化的操作特别重要，如果没有这一步，这个算法就没有效果。但是在原始论文中，他们是为了保持数据在平行移动下embedding不变。 LLE的matlab代码写得简洁明了，是一个样板。
在此有必要提提Lawrence Saul这个人。在Isomap和LLE的作者们中，Saul算是唯一一个以流形学习（并不限于）为研究对象开创学派的人。Saul早年主要做参数模型有关的算法。自从LLE以后，坐阵UPen创造了一个个佳绩。主要成就在于他的两个出色学生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多奖，在此不多说，可以到他主页上去看。Weinberger把学习核矩阵引入到流形学习中来。他的这个方法在流形学习中影响到不是很显著，却是在 convex optimization 中人人得知。Fei Sha不用多说了，machine learning中一个闪亮的新星，中国留学生之骄傲。现在他们一个在Yahoo,一个在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要说哪一个方法被做的全面，那莫非LE莫属。如果只说LE这个方法本身，是不新的，许多年前在做mesh相关的领域就开始这莫用。但是放在黎曼几何的框架内，给出完整的几何分析的，应该是Belkin和Niyogi（LE作者）的功劳。
LE的基本思想就是用一个无向有权图来描述一个流形，然后通过用图的嵌入（graph
embedding）来找低维表示。说白了，就是保持图的局部邻接关系的情况把这个图从高维空间中重新画在一个低维空间中（graph drawing）。
在至今为止的流行学习的典型方法中，LE是速度最快、效果相对来说不怎莫样的。但是LE有一个其他方法没有的特点，就是如果出现outlier情况下，它的鲁棒性（robustness）特别好。 后来Belkin和Niyogi又分析了LE的收敛性。大家不要忽视这个问题，很重要。鼓励有兴趣数学功底不错的人好好看看这篇文章。
d) Hessian Eigenmaps
如果你对黎曼几何不懂，基本上看不懂这个方法。又加作者表达的抽象，所以绝大多数人对这个方法了解不透彻。在此我就根据我自己的理解说说这个方法。
这个方法有两个重点：（1）如果一个流形是局部等距（isometric）欧式空间中一个开子集的，那末它的Hessian矩阵具有d+1维的零空间。（2）在每一点处，Hessian系数的估计。
首先作者是通过考察局部Hessian的二次型来得出结论的，如果一个流形局部等距于欧式空间中的一个开子集，那末由这个流形patch 到开子集到的映射函数是一个线性函数，线性函数的二次混合导数为零，所以局部上由Hessian系数构成的二次型也为零，这样把每一点都考虑到，过渡到全局的Hessian矩阵就有d+1维的零空间，其中一维是常函数构成的，也就是1向量。其它的d维子空间构成等距坐标。这就是理论基础的大意，当然作者在介绍的时候，为了保持理论严谨，作了一个由切坐标到等距坐标的过渡。
另外一个就是局部上Hessian系数的估计问题。我在此引用一段话：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
这段话是我在初学HE时候，写信问Dave Donoho，他给我的回信。希望大家领会。如果你了解了上述基本含义，再去细看两遍原始论文，也许会有更深的理解。由于HE牵扯到二阶导数的估计，所以对噪声很敏感。另外，HE的原始代码中在计算局部切坐标的时候，用的是奇异值分解(SVD)，所以如果想用他们的原始代码跑一下例如图像之类的真实数据，就特别的慢。其实把他们的代码改一下就可以了，利用一般PCA的快速计算方法，计算小尺寸矩阵的特征向量即可。还有，在原始代码中，他把Hessian系数归一化了，这也就是为什莫他们叫这个方法为 Hessian LLE 的原因之一。
Dave Dohono是学术界公认的大牛，在流形学习这一块，是他带着他的一个学生做的，Carrie Grimes。现在这个女性研究员在Google做 project leader，学术界女生同学的楷模 : )
e) LTSA (Local tangent space alignment)
很荣幸，这个是国内学者（浙江大学数学系的老师ZHANG Zhenyue）为第一作者做的一个在流行学习中最出色的方法。由于这个方法是由纯数学做数值分析出身的老师所做，所以原始论文看起来公式一大堆，好像很难似的。其实这个方法非常直观简单。
象 Hessian Eigenmaps 一样，流形的局部几何表达先用切坐标，也就是PCA的主子空间中的坐标。那末对于流形一点处的切空间，它是线性子空间，所以可以和欧式空间中的一个开子集建立同构关系，最简单的就是线性变换。在微分流形中，就叫做切映射 (tangential map)，是个很自然很基础的概念。把切坐标求出来，建立出切映射，剩下的就是数值计算了。最终这个算法划归为一个很简单的跌代加和形式。如果你已经明白了MDS，那末你就很容易明白，这个算法本质上就是MDS的从局部到整体的组合。
这里主要想重点强调一下，那个论文中使用的一个从局部几何到整体性质过渡的alignment技术。在spectral method（特征分解的）中，这个alignment方法特别有用。只要在数据的局部邻域上你的方法可以写成一个二次项的形式，就可以用。
其实LTSA最早的版本是在02年的DOCIS上。这个alignment方法在02年底Brand的 charting a manifold 中也出现，隐含在Hessian Eigenmaps中。在HE中，作者在从局部的Hessian矩阵过渡到全局的Hessian矩阵时，用了两层加号，其中就隐含了这个 alignment方法。后来国内一个叫 ZHAO Deli 的学生用这个方法重新写了LLE，发在Pattern Recognition上，一个短文。可以预见的是，这个方法还会被发扬光大。
ZHA Hongyuan 后来专门作了一篇文章来分析 alignment matrix 的谱性质，有兴趣地可以找来看看。
f) MVU (Maximum variance unfolding)
这个方法刚发出来以后，名字叫做Semi-definite Embedding (SDE)。构建一个局部的稀疏欧式距离矩阵以后，作者通过一定约束条件（主要是保持距离）来学习到一个核矩阵，对这个核矩阵做PCA就得到保持距离的 embedding，就这莫简单。但是就是这个方法得了多少奖，自己可以去找找看。个人观点认为，这个方法之所以被如此受人赏识，无论在vision还是在learning，除了给流形学习这一领域带来了一个新的解决问题的工具之外，还有两个重点，一是核方法（kernel），二是半正定规划（semi-definite programming），这两股风无论在哪个方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
这个方法不太被人所知，但是我认为这个是流形学习发展中的一个典型的方法（其实其他还有很多人也这莫认为）。就效果来说，这个方法不算好，说它是一个典型的方法，是因为这个方法应用了黎曼几何中一个很直观的性质。这个性质和法坐标(normal coordinate)、指数映射(exponential map)和距离函数(distance function)有关。
如果你了解黎曼几何，你会知道，对于流形上的一条测地线，如果给定初始点和初始点处测地线的切方向，那莫这个测地线就可以被唯一确定。这是因为在这些初始条件下，描述测地线的偏微分方程的解是唯一的。那末流形上的一条测地线就可以和其起点处的切平面上的点建立一个对应关系。我们可以在这个切平面上找到一点，这个点的方向就是这个测地线在起点处的切方向，其长度等于这个测地线上的长。这样的一个对应关系在局部上是一一对应的。那末这个在切平面上的对应点在切平面中就有一个坐标表示，这个表示就叫做测地线上对应点的法坐标表示（有的也叫指数坐标）。那末反过来，我们可以把切平面上的点映射到流形上，这个映射过程就叫做指数映射（Logmap就倒过来）。如果流形上每一个点都可以这样在同一个切平面上表示出来，那末我们就可以得到保持测地线长度的低维表示。如果这样做得到，流形必须可以被单坐标系统所覆盖。
如果给定流形上的采样点，如果要找到法坐标，我们需要知道两个东西，一是测地线距离，二是每个测地线在起点处的切方向。第一个东西好弄，利用Isomap中的方法直接就可以解决，关键是第二个。第二个作者利用了距离函数的梯度，这个梯度和那个切方向是一个等价的关系，一般的黎曼几何书中都有叙述。作者利用一个局部切坐标的二次泰勒展开来近似距离函数，而距离是知道的，就是测地线距离，局部切坐标也知道，那末通过求一个简单的最小二乘问题就可以估计出梯度方向。
如果明白这个方法的几何原理，你再去看那个方法的结果，你就会明白为什莫在距离中心点比较远的点的embedding都可以清楚地看到在一条条线上，效果不太好。
最近这个思想被北大的一个年轻的老师 LIN Tong 发扬光大，就是ECCV‘06上的那篇，还有即将刊登出的TPAMI上的 Riemannian Manifold Learning，实为国内研究学者之荣幸。Lin的方法效果非常好，但是虽然取名叫Riemannian，没有应用到黎曼几何本身的性质，这样使他的方法更容易理解。
Lin也是以一个切空间为基准找法坐标，这个出发点和思想和Brun（S-Logmaps）的是一样的。但是Lin全是在局部上操作的，在得出切空间原点处局部邻域的法坐标以后，Lin采用逐步向外扩展的方法找到其他点的法坐标，在某一点处，保持此点到它邻域点的欧式距离和夹角，然后转化成一个最小二乘问题求出此点的法坐标，这样未知的利用已知的逐步向外扩展。说白了就像缝网一样，从几个临近的已知点开始，逐渐向外扩散的缝。效果好是必然的。
浅谈流形学习
bypluskid, on 2010-05-29, in Machine Learning76 comments
总觉得即使是“浅谈”两个字，还是让这个标
题有些过大了，更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了，想起来要扯一下这个话题，也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉，不过如果并不是想要进行严格的理论推导的话，也可以从许多直观的例子得到一些感性的认识，正好我也就借这个机会来简单地谈一下这个话题吧，或者说至少是我到目前为止对这它的认识。 这两个词，在谈 Manifold 之前，不妨先说说 Learning ，也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科，因为每当它的一个子领域发展得像模像样之后，就立马自立门户，从此和 AI “再无瓜葛”了，而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪，比如说数学，分门别类总算是够多了吧？可以不管怎么分，大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢？我觉得这里有很大一部分
是它自身定位的问题。
反正现在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
说 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是这相当于一个 tautology ，因为到底什么又是the intelligence of machines呢？一开始的时候，大牛们都野心勃勃，而且好像也是信心满满，就好像曾经广泛认为“牛顿定理揭示了宇宙真理，科学剩下的事情只要按照公式来做计算就可以了”一样，大家可能觉得，不出几十年，人类就可以不用思考，交给 AI 来做了。不过我这里并不想再多说诸如什么是“思考”，什么是“智能”之类的以及随之而来的“图灵测试”之类的话题。我想说的是，到头来，AI 到底是什么，这还是一个问题，或者说，AI 在一开始定了一个过高的目标，几十年后，发现情况并不像当年那么乐观，却又有些下不了台了。
这个时候，AI 的一些旁枝或者子领域果断放下面子，丢掉了那个近乎玄幻的目标，逐渐发展成为“正常”的学科，所以也就不再好称为 AI 了。或者说现在的 AI 有两个意思，一个广义的 AI ，包括了所有相关的以及派生的领域，另一个则是狭义的或者经典的 AI ，专门指那些仍然在执着地追求着真正的“智能”的部分，或者说得不好听一点，就
是剩下的部分。
Machine Learning 作为离家出走的典型，虽然名字里带了 Learning 一个词，让人乍一看觉得和 Intelligence 相比不过是换了个说法而已，然而事实上这里的 Learning 的意义要朴素得多。我们来看一看 Machine Learning 的典型的流程就知道了，其实有时候觉得和应用数学或者更通俗的数学建模有些类似，通常我们会有需要分析或者处理的数据，根据一些经验和一些假设，我们可以构建一个模型，这个模型会有一些参数（即使是非参数化方法，也是可以类似地看待的），根据数据来求解模型参数的过程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞机器学习的人，通常把它叫做 Learning （或者，换一个角度，叫 Training）——因为根据数据归纳出一个有用的模型，这和我们人类“学习”的过程还是挺类似的吧。不过，如果抛开无聊的抠字眼游戏的话，我们可以看到，Machine Learning 已经抛弃了“智能”的高帽子，它的目的就是要解决具
体的问题——而并不关心是否是通过一种“智能”的方式类解决的。
说到这里，其实我们构造模型就类似于写一个类，数据就是构造函数的参数，Learning 就是构造函数运行的过程，成功构造一个对象之后，我们就完成了学习。一些 Machine Learning 的问题到这一步就结束了，另一些情况还会使用得到的模型（对象）对后来的数据进行一些处理，通常会是Inferencing。到这个时候，又有些像统计里的东西了，所谓“统计推断”嘛。其实原本统计和机器学习研究的不少问题就是交叉在一起的，不过两派人从不同的角度来看待同样的问题。而且，也确实有 Statistical Learning 这么一个说法存在的，可以把他看成是 Machine Learning 的一个子领域（或者是一个分子或
者甚至就是 Machine Learning 本身）。
到这里，如果你还没有因为不断地抠字眼而烦躁的话，
我已经忍无可忍了。所以，我就假定你已经了解了什么叫 Learning ，或者是已经恶心到懒得去了解了。于是我们转入下一个话题：流形，也就是 Manifold 。不知道你有没有为我在本文开头放上的那个地球的图片感到困惑？这是因为球面是一个很典型的流
形的例子，而地球就是一个很典型的“球面”啦（姑且当作球面好啦）。
有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”，不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像，所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布，可以把它看成一个二维平面，这是一个
二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不
扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况）。
所以，直观上来讲，一个流形好比是一个 d 维的空间，在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是，流形并不是一个“形状”，而是一个“空间”，如果你觉得“扭曲的空间”难以想象，那么请再回忆之前一块布的例子。如果我没弄错的话，广义相对论似乎就是把我们的时空当作一个四维流（空间三维加上时间一维）形来研究的，引力就是这个流形扭曲的结果。当然，这些都是直观上的概念，其实流形并不需要依靠嵌入在一个“外围空间”而存在，稍微正式一点来说，一个 d 维的流形就是一个在任意点出局部同胚于（简单地说，就是正逆映射都是光滑的一一映射）欧氏空间。
实际上，正是这种局部与欧氏空间的同
胚给我们带来了很多好处，这使得我们在日常生活中许许多多的几何问题都可以使用简单的欧氏几何来解决，因为和地球的尺度比起来，我们的日常生活就算是一个很小的局部啦——我突然想起《七龙珠》里的那个界王住的那种私人小星球，走几步就要绕一圈的感觉，看来界王不仅要体力好（那上面重力似乎是地球的十倍），而且脑力也要好，
初中学的必须是黎曼几何了！
那么，除了地球这种简单的例子，实际应用中的数据，怎么知道它是不是一个流形呢？于是不妨又回归直观的感觉。再从球面说起，如果我们事先不知道球面的存在，那么球面上的点，其实就是三维欧氏空间上的点，可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是，它们允许出现的位置受到了一定的限制，具体到球面，可以
可以看一下它的参数方程：
可以看到，这些三维的坐标实际上是由两个变量和生成的，也可以说成是它的自由度是二，也正好对应了它是一个二维的流形。有了这样的感觉之后，再来看流形学习里经
常用到的人脸的例子，就很自然了。下图是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 上的最短路径来近似了。
本文标签：