流形学习(2)

转载自：http://www.cvchina.info/2010/05/31/manifold-learning-2/#more-1040

dodo：流形学习 (manifold learning)

流形学习是个很广泛的概念。这里我主要谈的是自从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}.

dave

这段话是我在初学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

aa

这个方法不太被人所知，但是我认为这个是流形学习发展中的一个典型的方法（其实其他还有很多人也这莫认为）。就效果来说，这个方法不算好，说它是一个典型的方法，是因为这个方法应用了黎曼几何中一个很直观的性质。这个性质和法坐标(normal coordinate)、指数映射(exponential map)和距离函数(distance function)有关。

如果你了解黎曼几何，你会知道，对于流形上的一条测地线，如果给定初始点和初始点处测地线的切方向，那莫这个测地线就可以被唯一确定。这是因为在这些初始条件下，描述测地线的偏微分方程的解是唯一的。那末流形上的一条测地线就可以和其起点处的切平面上的点建立一个对应关系。我们可以在这个切平面上找到一点，这个点的方向就是这个测地线在起点处的切方向，其长度等于这个测地线上的长。这样的一个对应关系在局部上是一一对应的。那末这个在切平面上的对应点在切平面中就有一个坐标表示，这个表示就叫做测地线上对应点的法坐标表示（有的也叫指数坐标）。那末反过来，我们可以把切平面上的点映射到流形上，这个映射过程就叫做指数映射（Logmap就倒过来）。如果流形上每一个点都可以这样在同一个切平面上表示出来，那末我们就可以得到保持测地线长度的低维表示。如果这样做得到，流形必须可以被单坐标系统所覆盖。

如果给定流形上的采样点，如果要找到法坐标，我们需要知道两个东西，一是测地线距离，二是每个测地线在起点处的切方向。第一个东西好弄，利用Isomap中的方法直接就可以解决，关键是第二个。第二个作者利用了距离函数的梯度，这个梯度和那个切方向是一个等价的关系，一般的黎曼几何书中都有叙述。作者利用一个局部切坐标的二次泰勒展开来近似距离函数，而距离是知道的，就是测地线距离，局部切坐标也知道，那末通过求一个简单的最小二乘问题就可以估计出梯度方向。

如果明白这个方法的几何原理，你再去看那个方法的结果，你就会明白为什莫在距离中心点比较远的点的embedding都可以清楚地看到在一条条线上，效果不太好。

bb

最近这个思想被北大的一个年轻的老师 LIN Tong 发扬光大，就是ECCV‘06上的那篇，还有即将刊登出的TPAMI上的 Riemannian Manifold Learning，实为国内研究学者之荣幸。Lin的方法效果非常好，但是虽然取名叫Riemannian，没有应用到黎曼几何本身的性质，这样使他的方法更容易理解。

Lin也是以一个切空间为基准找法坐标，这个出发点和思想和Brun（S-Logmaps）的是一样的。但是Lin全是在局部上操作的，在得出切空间原点处局部邻域的法坐标以后，Lin采用逐步向外扩展的方法找到其他点的法坐标，在某一点处，保持此点到它邻域点的欧式距离和夹角，然后转化成一个最小二乘问题求出此点的法坐标，这样未知的利用已知的逐步向外扩展。说白了就像缝网一样，从几个临近的已知点开始，逐渐向外扩散的缝。效果好是必然的。

有人做了个好事情，做了个系统，把几个方法的matlab代码放在了一起 http://www.math.umn.edu/~wittman/mani/

以上提到方法论文，都可以用文中给出的关键词借助google.com找到。

3. 基本问题和个人观点

流形学习现在还基本处于理论探讨阶段，在实际中难以施展拳脚，不过在图形学中除外。我就说说几个基本的问题。

a. 谱方法对噪声十分敏感。希望大家自己做做实验体会一下，流形学习中谱方法的脆弱。
b. 采样问题对结果的影响。
c. 收敛性
d. 一个最尴尬的事情莫过于，如果用来做识别，流形学习线性化的方法比原来非线性的方法效果要好得多，如果用原始方法做识别，那个效果叫一个差。也正因为此，使很多人对流形学习产生了怀疑。原因方方面面 : )

e. 把偏微分几何方法引入到流形学习中来是一个很有希望的方向。这样的工作在最近一年已经有出现的迹象。

f. 坦白说，我已不能见庐山真面目了，还是留给大家来说吧

结尾写得有点草率，实在是精疲力尽了，不过还好主体部分写完。

4. 结束语

做学问的人有很多种，有的人学问做得很棒，但是独善其身者居多；有的人还谈不上做学问总想兼济天下。小弟不幸成了后一种人，总觉才学疏浅，力不从心，让各位见笑了。

今天一位朋友（filestorm）给我分享《列子御风》的故事，很受教育。鄙人功力不及二层，心却念是非，口却言利害，实在惭愧。

但又想主动尽自己绵薄之力为“兼济天下”做点事 : )，遂呈拙文于此（包括以前两篇人脸识别的），难免出现偏颇，无论好话坏话，还请各位尽管说来。