MIT大牛LinDahua博文转载

1、MIT大牛Lin Dahua博文精选 转载林达华的博文，值得花点时间来读，这里精选几篇。April 10 How to get asolution?我们所做的topic，一般有几个阶段：Analysis：分析问题，找到问题的关键Modeling/Formulation：对问题进行数学抽象，建立模型，或者formulate目标函数Solving：设计出求解的算法Experiments：实验最近的工作都集中在Solving这部分，就说说这个吧。求解的方法求解问题有很多不同的方法，就我知道的来说，大概有这么几个大家族。Heuristics。就是根据对问题的观察而设计的一些简单的方法，不一定遵循什么规

2、范，或者有什么深刻的数学根据。这类方法往往比较简单易懂，intuition比较明显，很多时候performance也挺不错的，不见得比高深的方法差，因而在实际工程中很受欢迎，几乎应用在全部的学科。不过，好像很多朋友对这类方法颇为不屑，认为没有技术含量，或者叫做没有理论深度。确实，有相当部分的Heuristics纯粹粗制滥造，投机取巧。不过，还有很多Heuristics虽然简单，但是切中问题要害，在长期的复杂的实际应用中经受住了考验。这些方法，表面看来可能只是再简单不过的几条四则运算公式，说不上多少理论，但是并不代表它没有深刻的理论基础。一个典型的例子是Google PageRank中使用的传导

3、公式(简单版本)，道理和公式都很简单，可是，做过类似工作的朋友可能都知道，它和代数图论以及马尔可夫随机过程有着很深的联系。又比如，Fourier Transform在刚出来的时候，仅仅是工程师的一些heuristics，后来关于它的理论已经成为了泛函分析的一个核心组成部分，也是信号处理的理论基础之一。真正好的heuristics，它的好处肯定不是瞎懵出来，而是有内在原因的。对它们的原理的探索，不断带动理论方面的发展，甚至创造了新的理论方向。说到这里，有人可能会argue，这是理论家们在故弄玄虚混饭吃。Hmm，这种说法我不能认同，但是，确实存在把工程方法胡乱进行理论化的事实。什么才叫有价值的理论

4、化，而不是故弄玄虚，确实值得思考，这里先不展开了。Analytical Solution。当你把问题formulate出来后，有些情况是直接可以从问题推导出解析解的。这种情况通常存在于objective function是Linear或者Quadratic的情况。大家都很喜欢这种情况的出现，理论漂亮，实现简洁。但是，据我的观察，很多情况下，这种elegance是通过减化模型换取的。把cost写成quadratic term，把distribution假设为Gauss，很多时候都能得到这样的结果。我不反对进行简化，也欣赏漂亮的analytical solution，如果它把问题解决得很好。但是，

5、这里面有个问题，很多能获得简单解析解的问题已经被做过了，剩下的很多难点，未必是一个简化模型能有效解决的。简化是一种很好的方法，但是，使用起来，尤其是在实际中的应用必须慎重，要清楚了解它们可能带来的问题。比如说，很多模型喜欢使用差的平方来衡量误差大小。但是，这很早就被指出是unrobust的，一个很大的deviation会dominate整个optimization，使得solution严重偏离方向。如果这种robustness在带解决的问题中是一个必须考虑的要素，那么用平方误差就要仔细考虑了。Numerical Optimization。如果formulation没有解析解，那么自然的想法就是

6、使用数值方法求解。目前大家常用的是基于Gradient/Hessian之类的local optimization的方法，有时会加上random initialization。如果objective function是convex的，那么这种方法保证收敛到global optimal，这是大家很希望的。convex problem无论在formulation还是在solution的阶段，都是很有学问的。很多问题可以formulate成convex的，但是未必都那么直接，这需要有这方面的基础。Solving一个convex problem有现成的方法，但是，如果能对问题的结构有insightful

7、的观察，可能能利用问题本身的特点大幅度降低求解的复杂度-这往往比直接把问题扔进solver里面等答案更有意义。除了convex optimization，还有一种数值方法应用非常广泛，叫做coordinate ascend或者alternate optimization。大概的思路是，几个有关的变量，轮流选择某个去优化，暂时固定其它的。在Machine Learning里面非常重要的Expectation-Maximization(EM算法)就属于这个大家族。另外，很多复杂的graphical model采用的variational inference也是属于此类。使用这类方法，有两个问题：一

8、个是如果几个variable之间相互影响，变一个，其他跟着变的话，那么直接使用这种方法可能是错误的，并不能保证收敛。另外一个问题是，如果problem不是convex的话，可能没有任何保证你得到的solution和global solution有联系。很可能，你得到的解和真正的全局最优解相差十万八千里。这个没有什么通用有效的途径来解决。不过，针对具体问题的结构特点，在求解过程中施加一定的引导是有可能的。Dynamic Programming。这个方法更多见于经典计算机算法中，不过现在越来越多在Vision和Learning见到它的影子。主要思路是把大问题分解为小问题，总结小问题的solutio

9、n为大问题的solution。至于如何设计分解和综合的过程，依赖于对问题的观察和分析，并无通用的法则可循。用DP解决问题的洞察力需要逐步的积累。不少经典算法就源自于DP，比如shotest path。一个可能有用的观察是，如果问题或者模型呈现链状，树状，或者有向无环图结构的，可能很有希望能通过DP高效解决。Local Exchange。很多建立在图上的问题，都可以通过某种局部交换来达到全局的平衡。像Belief propagation,Junction tree等等在graphical model的重要inference方法，还有tranduction model，都用到了类似的策略。这在实践

10、中被证明为非常有效。但是，并不是随便设计的局部交换过程都是收敛的。这里面需要关注两个问题：(1)交换过程是不是能保证某些重要的invariance不被破坏；(2)交换过程中，是不是有一个objective，比如距离全局平衡的deviation，它在每一步都保持单调。有很多交换过程，在有向无环图中保证收敛，但是，在带环图中由于信息的重复传递可能引起不稳定，或者不能收敛到正确的解。Monte Carlo Sampling。蒙特卡罗采样的原理非常简单，就是用样本平均，来逼近期望(这个可能需要用intractable的积分完成，没法直接算)。求平均很简单，关键在于采样过程。我们求解问题，通常是在后验分

11、布中采样，这种分布在大部分问题中，不要说直接采样了，可能连解析形式都没法给出。如果采样问题有效解决了，基本上我们研究的大部分问题其实都可以通过采样完成。由于直接采样往往非常困难，于是就产生了其它的方法，间接做这个事情。一种想法就是，既然p(x)不好直接采，我找一个比较容易采样的q(x)来逼近p(x)，然后给从q(x)采出的每个样本加一个weight，p(x)/q(x)。这在理论上被严格证明是对的-这种方法叫做Importance Sampling。这里的问题在于，如果q(x)和p(x)不太接近，那么采样效率非常低下，如果在一个高维空间，可能采1000年都达不到要求。可是，要得到一个approx

12、imate很好的q(x)本身不比直接从p(x)采样来得容易。还有一种聪明一点的方法，叫sequential importance sampling。在这里面q(x)，不是一蹴而就建立起来的，而是每个样本先采一部分，然后根据那部分，确定下一部分的proposal distribution，继续采，也就是说q(x)和样本都是dynamically built up。这个方法在vision里面一个非常著名的应用是用于tracking，相应发展出来的方法论叫做particle filtering。另外一大类重要的采样方法，叫Markov Chain Monte Carlo(MCMC)。这个的想法是，设

13、计一个马尔科夫链，让它的平衡分布恰好是p(x)，那么等它平衡时开始采。以前我们做随机过程作业是已知一个markov chain，求equilibrium distribution，设计MCMC就是反过来了。最重要的MCMC方法莫过于Metropolis-Hastings Algorithm和Gibbs Sampling，前者常被用于设计在solution space的随机游走(Random walk)，后者则是conditional sampling的基础方法。可是Markov过程怎么转移呢。最简单的Random Walk结合acceptance rate之后理论上是对的。可是，让sample

14、r随便乱走，猴年马月才能把solution space走一遍阿。于是，有人提出结合一个solution space的局部信息来引导它往有用的方向走。一个重要的方法叫做Hybric Monte Carlo(HMC)，想法就是把它模拟成一个物理场，把要sample的分布视为波尔兹曼分布后获得物理场的势能，通过哈密顿动力学模型(其实就是牛顿力学的推广)来驱动sampler。可是，如果问题更为复杂呢，比如整个solution space有几个井，sample掉到某一个井可能出不来了。为了解决这个问题，一种重要的方法叫Tempering，就是开始给分子充分加热，让它获得足够的动能能在各个井之间来回跳，然

15、后逐步冷却，从而能捕捉到多个势井。Monte Carlo方法较早的时候主要用于统计物理，目前已经广泛应用于计算机，生物，化学，地质学，经济学，社会学等等的研究。这是目前所知道的用于求解复杂的真实模型的最有效的方法。它的核心，就是猜-你直接解不出来，只好猜了，呵呵。但是，怎样才能猜得准，则是大有学问-几十年来各个领域关于Monte Carlo研究的工作汗牛充栋，有很多进展，但是还有很长的路要走。和这里很多留学生一样，我一向潜心于自己的学习和研究。可是最近，我们的世界并不宁静，我认识的不只一个在美国的朋友受到了不太友好的挑衅-在不知不觉中，我们可能已经身处反分裂和支持奥运的前线。我看到包括MIT

16、CSSA在内的很多学生团体开始组织起来支持自己的祖国。我没有具体帮上什么，但是，我对所有在用自己的行动捍卫国家荣誉的同胞怀有最深的敬意。我也希望，我的努力，能让外国的朋友明白中国人是值得尊敬的。June 22拓扑：游走于直观与抽象之间近日来，抽空再读了一遍点集拓扑(Point Set Topology)，这是我第三次重新学习这个理论了。我看电视剧和小说，极少能有兴致看第二遍，但是，对于数学，每看一次都有新的启发和收获。代数，分析，和拓扑，被称为是现代数学的三大柱石。最初读拓扑，是在两三年前，由于学习流形理论的需要。可是，随着知识的积累，发现它是很多理论的根基。可以说，没有拓扑，就没有现代意义的

17、分析与几何。我们在各种数学分支中接触到的最基本的概念，比如，极限，连续，距离(度量)，边界，路径，在现代数学中，都源于拓扑。拓扑学是一门非常奇妙的学科，它把最直观的现象和最抽象的概念联系在一起了。拓扑描述的是普遍使用的概念(比如开集，闭集，连续)，我们对这些概念习以为常，理所当然地使用着，可是，真要定义它，则需要对它们本质的最深刻的洞察。数学家们经过长时间的努力，得到了这些概念的现代定义。这里面很多第一眼看上去，会感觉惊奇-怎么会定义成这个样子。首先是开集。在学习初等数学时，我们都学习开区间(a,b)。可是，这只是在一条线上的，怎么推广到二维空间，或者更高维空间，或者别的形体上呢?最直观的想法

18、，就是一个不包含边界的集合。可是，问题来了，给一个集合，何谓边界?在拓扑学里面，开集(Open Set)是最根本的概念，它是定义在集合运算的基础上的。它要求开集符合这样的条件：开集的任意并集和有限交集仍为开集。我最初的时候，对于这样的定义方式，确实百思不解。不过，读下去，看了和做了很多证明后，发现，这样的定义一个很重要的意义在于：它保证了开集中每个点都有一个邻域包含在这个集合内-所有点都和外界(补集)保持距离。这样的理解应该比使用集合运算的定义有更明晰的几何意义。但是，直观的东西不容易直接形成严谨的定义，使用集合运算则更为严格。而集合运算定义中，任意并集的封闭性是对这个几何特点的内在保证。另外

19、一个例子就是连续函数(Continuous Function)。在学微积分时，一个耳熟能详的定义是对任意的epsilon 0，存在delta 0，使得。，背后最直观的意思就是足够近的点保证映射到任意小的范围内。可是，epsilon,delta都依赖于实空间，不在实空间的映射又怎么办呢?拓扑的定义是如果一个映射的值域中任何开集的原像都是开集，那么它连续。这里就没有epsilon什么事了。这里的关键在于，在拓扑学中，开集的最重要意义就是要传递邻域的意思-开集本身就是所含点的邻域。这样连续定义成这样就顺理成章了。稍微把说法调节一下，上面的定义就变成了对于f(x)的任意领域U，都有x的一个邻域V，使得

20、V里面的点都映射到U中。这里面，我们可以感受到为什么开集在拓扑学中有根本性的意义。既然开集传达邻域的意思，那么，它最重要的作用就是要表达哪些点靠得比较近。给出一个拓扑结构，就是要指出哪些是开集，从而指出哪些点靠得比较近，这样就形成了一个聚集结构-这就是拓扑。可是这也可以通过距离来描述，为什么要用开集呢，反而不直观了。某种意义上说，拓扑是定性的，距离度量是定量的。随着连续变形，距离会不断变化，但是靠近的点还是靠近，因此本身固有的拓扑特性不会改变。拓扑学研究的就是这种本质特性-连续变化中的不变性。在拓扑的基本概念中，最令人费解的，莫过于紧性(Compactness)。它描述一个空间或者一个集合紧不

21、紧。正式的定义是如果一个集合的任意开覆盖都有有限子覆盖，那么它是紧的。乍一看，实在有点莫名其妙。它究竟想描述一个什么东西呢?和紧这个形容词又怎么扯上关系呢?一个直观一点的理解，几个集合是紧的，就是说，无限个点撒进去，不可能充分散开。无论邻域多么小，必然有一些邻域里面有无限个点。上面关于compactness的这个定义的玄机就在有限和无限的转换中。一个紧的集合，被无限多的小邻域覆盖着，但是，总能找到其中的有限个就能盖全。那么，后果是什么呢?无限个点撒进去，总有一个邻域包着无数个点。邻域们再怎么小都是这样-这就保证了无限序列中存在极限点。Compact这个概念虽然有点不那么直观，可是在分析中有着无

22、比重要的作用。因为它关系到极限的存在性-这是数学分析的基础。了解泛函分析的朋友都知道，序列是否收敛，很多时候就看它了。微积分中，一个重要的定理-有界数列必然包含收敛子列，就是根源于此。在学习拓扑，或者其它现代数学理论之前，我们的数学一直都在有限维欧氏空间之中，那是一个完美的世界，具有一切良好的属性，Hausdorff,Locally compact,Simply connected，Completed，还有一套线性代数结构，还有良好定义的度量，范数，与内积。可是，随着研究的加深，终究还是要走出这个圈子。这个时候，本来理所当然的东西，变得不那么必然了。两个点必然能分开?你要证明空间是Hausdo

23、rff的。有界数列必然存在极限点?这只在locally compact的空间如此。一个连续体内任意两点必然有路径连接?这可未必。一切看上去有悖常理，而又确实存在。从线性代数到一般的群，从有限维到无限维，从度量空间到拓扑空间，整个认识都需要重新清理。而且，这些绝非仅是数学家的概念游戏，因为我们的世界不是有限维向量能充分表达的。当我们研究一些不是向量能表达的东西的时候，度量，代数，以及分析的概念，都要重新建立，而起点就在拓扑。April 19图谱马尔可夫过程聚类结构题目中所说到的四个词语，都是Machine Learning以及相关领域中热门的研究课题。表面看属于不同的topic，实际上则是看待同

24、一个问题的不同角度。不少文章论述了它们之间的一些联系，让大家看到了这个世界的奇妙。从图说起这里面，最简单的一个概念就是图(Graph)，它用于表示事物之间的相互联系。每个图有一批节点(Node)，每个节点表示一个对象，通过一些边(Edge)把这些点连在一起，表示它们之间的关系。就这么一个简单的概念，它对学术发展的意义可以说是无可估量的。几乎所有领域研究的东西，都是存在相互联系的，通过图，这些联系都具有了一个统一，灵活，而又强大的数学抽象。因此，很多领域的学者都对图有着深入探讨，而且某个领域关于图的研究成果，可以被其它领域借鉴。矩阵表示：让代数进入图的世界在数学上，一种被普遍使用的表达就是邻接矩

25、阵(Adjacency Matrix)。一个有N个节点的图，可以用一个N xN的矩阵G表示，G(i,j)用一个值表示第i个节点和第j个节点的联系，通常来说这个值越大它们关系越密切，这个值为0表示它们不存在直接联系。这个表达，很直接，但是非常重要，因为它把数学上两个非常根本的概念联系在一起：图(Graph)和矩阵(Matrix)。矩阵是代数学中最重要的概念，给了图一个矩阵表达，就建立了用代数方法研究图的途径。数学家们几十年前开始就看到了这一点，并且开创了数学上一个重要的分支-代数图论(Algebraic Graph Theory)。代数图论通过图的矩阵表达来研究图。熟悉线性代数的朋友知道，代数中

26、一个很重要的概念叫做谱(Spectrum)。一个矩阵的很多特性和它的谱结构-就是它的特征值和特征向量是密切相关的。因此，当我们获得一个图的矩阵表达之后，就可以通过研究这个矩阵的谱结构来研究图的特性。通常，我们会分析一个图的邻接矩阵(Adjacency Matrix)或者拉普拉斯矩阵(Laplace Matrix)的谱-这里多说一句，这两种矩阵的谱结构刚好是对称的。谱：分而治之的代数谱，这个词汇似乎在不少地方出现过，比如我们可能更多听说的频谱，光谱，等等。究竟什么叫谱呢?它的概念其实并不神秘，简单地说，谱这个概念来自分而治之的策略。一个复杂的东西不好直接研究，就把它分解成简单的分量。如果我们把一

27、个东西看成是一些分量叠加而成，那么这些分量以及它们各自所占的比例，就叫这个东西的谱。所谓频谱，就是把一个信号分解成多个频率单一的分量。矩阵的谱，就是它的特征值和特征向量，普通的线性代数课本会告诉你定义：如果A v=c v，那么c就是A的特征值，v就叫特征向量。这仅仅是数学家发明的一种数学游戏么?-也许有些人刚学这个的时候，并一定能深入理解这么个公式代表什么。其实，这里的谱，还是代表了一种分量结构，它为使用分而治之策略来研究矩阵的作用打开了一个重要途径。这里我们可以把矩阵理解为一个操作(operator)，它的作用就是把一个向量变成另外一个向量：y=A x。对于某些向量，矩阵对它的作用很简单，A

28、 v=cv，相当于就把这个向量v拉长了c倍。我们把这种和矩阵A能如此密切配合的向量v1,v2,.叫做特征向量，这个倍数c1,c2,.叫特征值。那么来了一个新的向量x的时候，我们就可以把x分解为这些向量的组合，x=a1 v1+a2 v2+.，那么A对x的作用就可以分解了：A x=A(a1 v1+a2 v2+.)=a1 c1 v1+a2 c2 v2.所以，矩阵的谱就是用于分解一个矩阵的作用的。这里再稍微延伸一点。一个向量可以看成一个关于整数的函数，就是输入i，它返回v(i)。它可以延伸为一个连续函数(一个长度无限不可数的向量，呵呵)，相应的矩阵A变成一个二元连续函数(面积无限大的矩阵)。这时候矩阵

29、乘法中的求和变成了积分。同样的，A的作用可以理解为把一个连续函数映射为另外一个连续函数，这时候A不叫矩阵，通常被称为算子。对于算子，上面的谱分析方法同样适用(从有限到无限，在数学上还需要处理一下，不多说了)-这个就是泛函分析中的一个重要部分-谱论(Spectral Theory)。马尔可夫过程-从时间的角度理解图回到图这个题目，那么图的谱是干什么的呢?按照上面的理解，似乎是拿来分解一个图的。这里谱的作用还是分治，但是，不是直观的理解为把图的大卸八块，而是把要把在图上运行的过程分解成简单的过程的叠加。如果一个图上每个节点都有一个值，那么在图上运行的过程就是对这些值进行更新的过程。一个简单，大家经

30、常使用的过程，就是马尔可夫过程(Markov Process)。学过随机过程的朋友都了解马尔可夫过程。概念很简单-将来只由现在决定，和过去无关。考虑一个图，图上每个点有一个值，会被不断更新。每个点通过一些边连接到其它一些点上，对于每个点，这些边的值都是正的，和为1。在图上每次更新一个点的值，就是对和它相连接的点的值加权平均。如果图是联通并且非周期(数学上叫各态历经性,ergodicity)，那么这个过程最后会收敛到一个唯一稳定的状态(平衡状态)。图上的马尔可夫更新过程，对于很多学科有着非常重要的意义。这种数学抽象，可以用在什么地方呢?(1)Google对搜索结果的评估(PageRank)原理上

31、依赖于这个核心过程，(2)统计中一种广泛运用的采样过程MCMC，其核心就是上述的转移过程，(3)物理上广泛存在的扩散过程(比如热扩散，流体扩散)和上面的过程有很重要的类比，(4)网络中的信息的某些归纳与交换过程和上述过程相同(比如Random Gossiping)，还有很多。非常多的实际过程通过某种程度的简化和近似，都可以归结为上述过程。因此，对上面这个核心过程的研究，对于很多现象的理解有重要的意义。各个领域的科学家从本领域的角度出发研究这个过程，得出了很多实质上一致的结论，并且很多都落在了图的谱结构的这个关键点上。图和谱在此联姻根据上面的定义，我们看到邻接矩阵A其实就是这个马尔可夫过程的转移

32、概率矩阵。我们把各个节点的值放在一起可以得到一个向量v，那么我们就可以获得对这个过程的代数表示，v(t+1)=A v(t)。稳定的时候，v=A v。我们可以看到稳定状态就是A的一个特征向量，特征值就是1。这里谱的概念进来了。我们把A的特征向量都列出来v1,v2,.，它们有A vi=ci vi。vi其实就是一种很特殊，但是很简单的状态，对它每进行一轮更新，所有节点的值就变成原来的ci倍。如果0 ci 1，那么，相当于所有节点的值呈现指数衰减，直到大家都趋近于0。一般情况下，我们开始于一个任意一个状态u，它的更新过程就没那么简单了。我们用谱的方法来分析，把u分解成u=v1+c2 v2+c3 v3+

33、.(在数学上可以严格证明，对于上述的转移概率矩阵，最大的特征值就是1，这里对应于平衡状态v1，其它的特征状态v2,v3,.,对应于特征值1 c2 c3.-1)。那么，我们可以看到，当更新进行了t步之后，状态变成u(t)=v1+c2t v2+c3t v3+.，我们看到，除了代表平衡状态的分量保持不变外，其它分量随着t增长而指数衰减，最后，其它整个趋近于平衡状态。从上面的分析看到，这个过程的收敛速度，其实是和衰减得最慢的那个非平衡分量是密切相关的，它的衰减速度取决于第二大特征值c2，c2的大小越接近于1，收敛越慢，越接近于0，收敛越快。这里，我们看到了谱的意义。第一，它帮助把一个图上运行的马尔可夫

34、过程分解为多个简单的字过程的叠加，这里面包含一个平衡过程和多个指数衰减的非平衡过程。第二，它指出平衡状态是对应于最大特征值1的分量，而收敛速度主要取决于第二大特征值。我们这里知道了第二大特征值c2对于描述这个过程是个至关重要的量，究竟是越大越好，还是越小越好呢?这要看具体解决的问题。如果你要设计一个采样过程或者更新过程，那么就要追求一个小的c2，它一方面提高过程的效率，另外一方面，使得图的结构改变的时候，能及时收敛，从而保证过程的稳定。而对于网络而言，小的c2有利于信息的迅速扩散和传播。聚类结构-从空间的角度理解图c2的大小往往取决于图上的聚类结构。如果图上的点分成几组，各自聚成一团，缺乏组与

35、组之间的联系，那么这种结构是很不利于扩散的。在某些情况下，甚至需要O(exp(N)的时间才能收敛。这也符合我们的直观想象，好比两个大水缸，它们中间的只有一根很细的水管相连，那么就需要好长时间才能达到平衡。有兴趣的朋友可以就这个水缸问题推导一下，这个水缸系统的第二大特征值和水管流量与水缸的容积的比例直接相关，随比例增大而下降。对于这个现象进行推广，数学上有一个重要的模型叫导率模型(Conductance)。具体的公式不说了，大体思想是，节点集之间的导通量和节点集大小的平均比例和第二大特征值之间存在一个单调的上下界关系。导率描述的是图上的节点连接的空间结合，这个模型把第二特征值c2和图的空间聚集结

36、构联系在一起了。图上的聚类结构越明显，c2越大；反过来说，c2越大，聚类的结构越明显，(c2=1)时，整个图就断裂成非连通的两块或者多块了。从这个意义上说，c2越大，越容易对这个图上的点进行聚类。机器学习中一个重要课题叫做聚类，近十年来，基于代数图论发展出来的一种新的聚类方法，就是利用了第二大特征值对应的谱结构，这种聚类方法叫做谱聚类(Spectral Clustering)。它在Computer Vision里面对应于一种著名的图像分割方法，叫做Normalized Cut。很多工作在使用这种方法。其实这种方法的成功，取决于c2的大小，也就是说取决于我们如何构造出一个利于聚类的图，另外c2的

37、值本身也可以作为衡量聚类质量，或者可聚类性的标志。遗憾的是，在paper里面，使用此方法者众，深入探讨此方法的内在特点者少。归纳起来图是表达事物关系和传递扩散过程的重要数学抽象图的矩阵表达提供了使用代数方法研究图的途径谱，作为一种重要的代数方法，其意义在于对复杂对象和过程进行分解图上的马尔可夫更新过程是很多实际过程的一个重要抽象图的谱结构的重要意义在于通过它对马尔可夫更新过程进行分解分析图的第一特征值对应于马尔可夫过程的平衡状态，第二特征值刻画了这个过程的收敛速度(采样的效率，扩散和传播速度，网络的稳定程度)。图的第二特征分量与节点的聚类结构密切相关。可以通过谱结构来分析图的聚类结构。马尔可夫

38、过程代表了一种时间结构，聚类结构代表了一种空间结构，谱把它们联系在一起了，在数学刻画了这种时与空的深刻关系。July 09 Learning中的代数结构的建立Learning是一个融会多种数学于一体的领域。说起与此有关的数学学科，我们可能会迅速联想到线性代数以及建立在向量空间基础上的统计模型-事实上，主流的论文中确实在很大程度上基于它们。Rn(n-维实向量空间)是我们在paper中见到最多的空间，它确实非常重要和实用，但是，仅仅依靠它来描述我们的世界并不足够。事实上，数学家们给我们提供了丰富得多的工具。空间(space)，这是一个很有意思的名词，几乎出现在所有的数学分支的基础定义之中。归纳起来

39、，所谓空间就是指一个集合以及在上面定义的某种数学结构。关于这个数学结构的定义或者公理，就成为这个数学分支的基础，一切由此而展开。还是从我们最熟悉的空间-Rn说起吧。大家平常使用这个空间的时候，除了线性运算，其实还用到了别的数学结构，包括度量结构和内积结构。第一，它是一个拓扑空间(Topological space)。而且从拓扑学的角度看，具有非常优良的性质：Normal(implying Hausdorff and Regular),Locally Compact,Paracompact,with Countable basis,Simply connected(implying connec

40、ted and path connected),Metrizable.第二，它是一个度量空间(Metric space)。我们可以计算上面任意两点的距离。第三，它是一个有限维向量空间(Finite dimensional space)。因此，我们可以对里面的元素进行代数运算(加法和数乘)，我们还可以赋予它一组有限的基，从而可以用有限维坐标表达每个元素。第四，基于度量结构和线性运算结构，可以建立起分析(Analysis)体系。我们可以对连续函数进行微分，积分，建立和求解微分方程，以及进行傅立叶变换和小波分析。第五，它是一个希尔伯特空间(也就是完备的内积空间)(Hilbert space,Comp

41、lete inner product space)。它有一套很方便计算的内积(inner product)结构-这个空间的度量结构其实就是从其内积结构诱导出来。更重要的，它是完备的(Complete)-代表任何一个柯西序列(Cauchy sequence)都有极限-很多人有意无意中其实用到了这个特性，不过习惯性地认为是理所当然了。第六，它上面的线性映射构成的算子空间仍旧是有限维的-一个非常重要的好处就是，所有的线性映射都可以用矩阵唯一表示。特别的，因为它是有限维完备空间，它的泛函空间和它本身是同构的，也是Rn。因而，它们的谱结构，也就可以通过矩阵的特征值和特征向量获得。第七，它是一个测度空间-

42、可以计算子集的大小(面积/体积)。正因为此，我们才可能在上面建立概率分布(distribution)-这是我们接触的绝大多数连续统计模型的基础。我们可以看到，这是一个非常完美的空间，为我们的应用在数学上提供了一切的方便，在上面，我们可以理所当然地认为它具有我们希望的各种良好性质，而无须特别的证明；我们可以直接使用它的各种运算结构，而不需要从头建立；而且很多本来不一样的概念在这里变成等价的了，我们因此不再需要辨明它们的区别。以此为界，Learning的主要工作分成两个大的范畴：建立一种表达形式，让它处于上面讨论的Rn空间里面。获得了有限维向量表达后，建立各种代数算法或者统计模型进行分析和处理。这

43、里只讨论第一个范畴。先看看，目前用得比较广泛的一些方法：直接基于原始数据建立表达。我们关心的最终目标是一个个现实世界中的对象：一幅图片，一段语音，一篇文章，一条交易记录，等等。这些东西大部分本身没有附着一个数值向量的。为了构造一个向量表达，我们可以把传感器中记录的数值，或者别的什么方式收集的数值数据按照一定的顺序罗列出来，就形成一个向量了。如果有n个数字，就认为它们在Rn里面。不过，这在数学上有一点小问题，在大部分情况下，根据数据产生的物理原理，这些向量的值域并不能充满整个空间。比如图像的像素值一般是正值，而且在一个有界闭集之中。这带来的问题是，对它们进行线性运算很可能得到的结果会溢出正常的范

44、围-在大部分paper中，可能只是采用某些heuristics的手段进行简单处理，或者根本不管，很少见到在数学上对此进行深入探讨的-不过如果能解决实际问题，这也是无可厚非的，毕竟不是所有的工作都需要像纯数学那样追求严谨。量化(quantization)。这是在处理连续信号时被广泛采用的方式。只是习以为常，一般不提名字而已。比如一个空间信号(Vision中的image)或者时间信号，它们的domain中的值是不可数无限大的(uncountably infinite)，不要说表示为有限维向量，即使表达为无限序列也是不可能的。在这种情况下，一般在有限域内，按照一定顺序每隔一定距离取一个点来代表其周围

45、的点，从而形成有限维的表达。这就是信号在时域或空域的量化。这样做不可避免要丢失信息。但是，由于小邻域内信号的高度相关，信息丢失的程度往往并不显著。而且，从理论上说，这相当于在频域中的低通过率。对于有限能量的连续信号，不可能在无限高的频域中依然保持足够的强度，只要采样密度足够，丢失的东西可以任意的少。除了表示信号，对于几何形体的表达也经常使用量化，比如表示curve和surface。找出有限个数充分表达一个对象也许不是最困难的。不过,在其上面建立数学结构却未必了。一般来说，我们要对其进行处理，首先需要一个拓扑结构用以描述空间上的点是如何联系在一起。直接建立拓扑结构在数学上往往非常困难，也未必实用

46、。因此，绝大部分工作采取的方式是首先建立度量结构。一个度量空间，其度量会自然地诱导出一个拓扑结构-不过，很多情况下我们似乎会无视它的存在。最简单的情况，就是使用原始向量表达的欧氏距离(Euclidean distance)作为metric。不过，由于原始表达数值的不同特性，这种方式效果一般不是特别好，未必能有效表达实际对象的相似性(或者不相似性)。因此，很多工作会有再此基础上进行度量的二次建立。方式是多种多样的，一种是寻求一个映射，把原空间的元素变换到一个新的空间，在那里欧氏距离变得更加合适。这个映射发挥的作用包括对信息进行筛选，整合，对某些部分进行加强或者抑制。这就是大部分关于feature

47、 selection，feature extraction，或者subspace learning的文章所要做的。另外一种方式，就是直接调节距离的计算方式(有些文章称之为metric learning)。这两种方式未必是不同的。如果映射是单射，那么它相当于在原空间建立了一个不同的度量。反过来，通过改变距离计算方式建立的度量在特定的条件下对应于某种映射。大家可能注意到，上面提到的度量建立方法，比如欧氏距离，它需要对元素进行代数运算。对于普通的向量空间，线性运算是天然赋予的，我们无须专门建立，所以可以直接进行度量的构造-这也是大部分工作的基础。可是，有些事物其原始表达不是一个n-tuple，它可能

48、是一个set，一个graph，或者别的什么特别的object。怎么建立代数运算呢?一种方法是直接建立。就是给这些东西定义自己的加法和数乘。这往往不是那么直接(能很容易建立的线性运算结构早已经被建立好并广泛应用了)，可能需要涉及很深的数学知识，并且要有对问题本身的深入了解和数学上的洞察力。不过，一个新的代数结构一旦建立起来，其它的数学结构，包括拓扑，度量，分析，以及内积结构也随之能被自然地诱导出来，我们也就具有了对这个对象空间进行各种数学运算和操作的基础。加法和数乘看上去简单，但是如果我们对于本来不知道如何进行加法和数乘的空间建立了这两样东西，其理论上的贡献是非常大的。(一个小问题：大家常用各种

49、graphical model，但是，每次这些model都是分别formulate，然后推导出estimation和evaluation的步骤方法。是否可能对the space of graphical model或者它的某个特定子集建立某种代数结构呢?(不一定是线性空间，比如群，环，广群，etc)从而使得它们在代数意义上统一起来，而相应的estimation或者evaluation也可以用过代数运算derive。这不是我的研究范围，也超出了我目前的能力和知识水平，只是我相信它在理论上的重要意义，留作一个远景的问题。事实上，数学中确实有一个分支叫做Algebraic statistics可能在

50、探讨类似的问题，不过我现在对此了解非常有限。)回到我们的正题，除了直接建立运算定义，另外一种方式就是嵌入(embedding)到某个向量空间，从而继承其运算结构为我所用。当然这种嵌入也不是乱来，它需要保持原来这些对象的某种关系。最常见的就是保距嵌入(isometric embedding)，我们首先建立度量结构(绕过向量表达，直接对两个对象的距离通过某种方法进行计算)，然后把这个空间嵌入到目标空间，通常是有限维向量空间，要求保持度量不变。嵌入是一种在数学上应用广泛的手段，其主要目标就是通过嵌入到一个属性良好，结构丰富的空间，从而利用其某种结构或者运算体系。在拓扑学中，嵌入到metric spa

51、ce是对某个拓扑空间建立度量的重要手段。而在这里，我们是已有度量的情况下，通过嵌入获取线性运算的结构。除此以来，还有一种就是前些年比较热的manifold embedding，这个是通过保持局部结构的嵌入，获取全局结构，后面还会提到。接下来的一个重要的代数结构，就是内积(inner product)结构。内积结构一旦建立，会直接诱导出一种性质良好的度量，就是范数(norm)，并且进而诱导出拓扑结构。一般来说，内积需要建立在线性空间的基础上，否则连一个二元运算是否是内积都无法验证。不过，kernel理论指出，对于一个空间，只要定义一个正定核(positive kernel)-一个符合正定条件的二

52、元运算，就必然存在一个希尔伯特空间，其内积运算等效于核运算。这个结论的重要意义在于，我们可以绕开线性空间，通过首先定义kernel的方式，诱导出一个线性空间(叫做再生核希尔伯特空间Reproducing Kernel Hilbert Space)，从而我们就自然获得我们所需要的度量结构和线性运算结构。这是kernel theory的基础。在很多教科书中，以二次核为例子，把二维空间变成三维，然后告诉大家kernel用于升维。对于这种说法，我一直认为在一定程度上是误导的。事实上，kernel的最首要意义是内积的建立(或者改造)，从而诱导出更利于表达的度量和运算结构。对于一个问题而言，选择一个切合问

53、题的kernel比起关注升维来得更为重要。kernel被视为非线性化的重要手段，用于处理非高斯的数据分布。这是有道理的。通过nonlinear kernel改造的内积空间，其结构和原空间的结构确实不是线性关联，从这个意义上说，它实施了非线性化。不过，我们还应该明白，它的最终目标还是要回到线性空间，新的内积空间仍旧是一个线性空间，它一旦建立，其后的运算都是线性的，因此，kernel的使用就是为了寻求一个新的线性空间，使得线性运算更加合理-非线性化的改造最终仍旧是要为线性运算服务。值得一提的是，kernelization本质上说还是一种嵌入过程：对于一个空间先建立内积结构，并且以保持内积结构不变的

54、方式嵌入到一个高维的线性空间，从而继承其线性运算体系。上面说到的都是从全局的方式建立代数结构的过程，但是那必须以某种全局结构为基础(无论预先定义的是运算，度量还是内积，都必须适用于全空间。)但是，全局结构未必存在或者适合，而局部结构往往简单方便得多。这里就形成一种策略，以局部而达全局-这就是流形(manifold)的思想，而其则根源于拓扑学。从拓扑学的角度说，流形就是一个非常优良的拓扑空间：符合Hausdorff分离公理(任何不同的两点都可以通过不相交的邻域分离)，符合第二可数公理(具有可数的拓扑基)，并且更重要的是，局部同胚于Rn。因此，一个正则(Regular)流形基本就具有了各种最良好的

55、拓扑特性。而局部同胚于Rn，代表了它至少在局部上可以继承Rn的各种结构，比如线性运算和内积，从而建立分析体系。事实上，拓扑流形继承这些结构后形成的体系，正是现代流形理论研究的重点。继承了分析体系的流形，就形成了微分流形(Differential manifold)，这是现代微分几何的核心。而微分流形各点上的切空间(Tangent Space)，则获得了线性运算的体系。而进一步继承了局部内积结构的流形，则形成黎曼流形(Riemann manifold)，而流形的全局度量体系-测地距离(geodesics)正是通过对局部度量的延伸来获得。进一步的，当流行本身的拓扑结构和切空间上的线性结构发生关系-

56、也就获得一簇拓扑关联的线性空间-向量丛(Vector bundle)。虽然manifold theory作为现代几何学的核心，是一个博大精深的领域，但是它在learning中的应用则显得非常狭窄。事实上，对于manifold，很多做learning的朋友首先反应的是ISOMAP,LLE,eigenmap之类的算法。这些都属于embedding。当然，这确实是流形理论的一个重要方面。严格来说，这要求是从原空间到其映像的微分同胚映射，因此，嵌入后的空间在局部上具有相同的分析结构，同时也获得了各种好处-全局的线性运算和度量。不过，这个概念在learning的应用中被相当程度的放宽了-微分同胚并不能被

57、完全保证，而整个分析结构也不能被完全保持。大家更关注的是保持局部结构中的某个方面-不过这在实际应用中的折衷方案也是可以理解的。事实表明，当原空间中的数据足够密集的情况下，这些算法工作良好。Learning中流形应用的真正问题在于它被过滥地运用于稀疏空间(Sparse space)，事实上在高维空间中撒进去几千乃至几十万点，即使最相邻的几点也难称为局部了，局部的范围和全局的范围其实已经没有了根本差别，连局部的概念都立不住脚的时候，后面基于其展开的一切工作也都没有太大的意义。事实上，稀疏空间有其本身的规律和法则，通过局部形成全局的流形思想从本质上是不适合于此的。虽然，流形是一种非常美的理论，但是再

58、漂亮的理论也需要用得其所-它应该用于解决具有密集数据分布的低维空间。至于，一些paper所报告的在高维空间(比如人脸)运用流形方法获得性能提升，其实未必是因为流形本身所起的作用，而很可能是其它方面的因素。流形在实际应用中起重要作用的还有两个方面：一个是研究几何形体的性质(我们暂且不谈这个)，还有就是它和代数结构的结合形成的李群(Lie group)和李代数(Lie algebra)。当我们研究的对象是变换本身的时候，它们构成的空间是有其特殊性的，比如所有子空间投影形成了Grassmann流形，所有的可逆线性算子，或者仿射算子，也形成各自的流形。对他们的最重要操作是变换的结合，而不是加法数乘，因

59、此，它们上面定义的更合适的代数结构应该是群和不是线性空间。而群和微分流形的结合体-李群则成为它们最合适的描述体系-而其切空间则构成了一种加强的线性空间：李代数，用于描述其局部变化特性。李代数和李群的关系是非常漂亮的。它把变换的微变化转换成了线性空间的代数运算，使得移植传统的基于线性空间的模型和算法到李空间变得可能。而且李代数中的矩阵比起变换本身的矩阵甚至更能反映变换的特性。几何变换的李代数矩阵的谱结构就能非常方便地用于分析变换的几何特性。最后，回头总结一下关于嵌入这个应用广泛的策略，在learning中的isometry,kernel和manifold embedding都属于此范畴，它们分别通过保持原空间的度量结构，内积结构和局部结构来获得到目标(通常是向量空间)的嵌入，从而获得全局的坐标表达，线性运算和度量，进而能被各种线性算法和模型所应用。在获得这一系列好处的同时，也有值得我们注意的地方。首先，嵌入只是一种数学手段，并不能取代对问题本身的研究和分析。一种不恰当的原始结构或者嵌入策略，很多时候甚至适得其反