共计 7810 个字符，预计需要花费 20 分钟才能阅读完成。
假如数据是平均采样于一个高维欧氏空间中的低维流形，流形学习就是从高维采样数据中复原低维流形构造，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。它是从观测到的景象中去寻找事物的实质，找到产生数据的外在法则。流形学习办法是模式识别中的根本办法，分为线性流形学习算法和非线性流形学习算法，线性办法就是传统的办法如主成分剖析（PCA）和线性判别分析（LDA），非线行流形学习算法包含等距映射（Isomap），拉普拉斯特色映射（LE）等
流形学习是个很宽泛的概念。这里我次要谈的是自从 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_1x_2,… ,x_ {k-1} x_ {k} . Extract the component of the operator that delivers the projection on x_1^2,…,x_k^2, x_1x_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 采纳逐渐向外扩大的办法找到其余点的法坐标，在某一点处，放弃此点到它邻域点的欧式间隔和夹角，而后转化成一个最小二乘问题求出此点的法坐标，这样未知的利用已知的逐渐向外扩大。说白了就像缝网一样，从几个邻近的已知点开始，逐步向外扩散的缝。成果好是必然的。
以上提到办法论文，都能够用文中给出的关键词借助 google.com 找到。
3. 根本问题和个人观点
流形学习当初还根本处于实践探讨阶段，在理论中难以施展拳脚，不过在图形学中除外。我就说说几个根本的问题。
a. 谱办法对噪声非常敏感。心愿大家本人做做试验领会一下，流形学习中谱办法的软弱。
b. 采样问题对后果的影响。
c. 收敛性
d. 一个最难堪的事件莫过于，如果用来做辨认，流形学习线性化的办法比原来非线性的办法成果要好得多，如果用原始办法做辨认，那个成果叫一个差。也正因为此，使很多人对流形学习产生了狐疑。起因方方面面 : )
e. 把偏微分几何办法引入到流形学习中来是一个很有心愿的方向。这样的工作在最近一年曾经有呈现的迹象。
f. 坦白说，我已不能见庐山真面目了，还是留给大家来说吧
结尾写得有点粗率，切实是精疲力尽了，不过还好主体局部写完。
