题目中所说到的四个词语，都是Machine Learning以及相关领域中热门的研究课题。表面看属于不同的topic，实际上则是看待同一个问题的不同角度。不少文章论述了它们之间的一些联系，让大家看到了这个世界的奇妙。

从图说起

这里面，最简单的一个概念就是“图”(Graph)，它用于表示事物之间的相互联系。每个图有一批节点(Node)，每个节点表示一个对象，通过一些边(Edge)把这些点连在一起，表示它们之间的关系。就这么一个简单的概念，它对学术发展的意义可以说是无可估量的。几乎所有领域研究的东西，都是存在相互联系的，通过图，这些联系都具有了一个统一，灵活，而又强大的数学抽象。因此，很多领域的学者都对图有着深入探讨，而且某个领域关于图的研究成果，可以被其它领域借鉴。

矩阵表示：让代数进入图的世界

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

代数图论通过图的矩阵表达来研究图。熟悉线性代数的朋友知道，代数中一个很重要的概念叫做“谱”(Spectrum)。一个矩阵的很多特性和它的谱结构——就是它的特征值和特征向量是密切相关的。因此，当我们获得一个图的矩阵表达之后，就可以通过研究这个矩阵的谱结构来研究图的特性。通常，我们会分析一个图的邻接矩阵(Adjacency Matrix)或者拉普拉斯矩阵(Laplace Matrix)的谱——这里多说一句，这两种矩阵的谱结构刚好是对称的。

谱：“分而治之”的代数

谱，这个词汇似乎在不少地方出现过，比如我们可能更多听说的频谱，光谱，等等。究竟什么叫“谱”呢？它的概念其实并不神秘，简单地说，谱这个概念来自“分而治之”的策略。一个复杂的东西不好直接研究，就把它分解成简单的分量。如果我们把一个东西看成是一些分量叠加而成，那么这些分量以及它们各自所占的比例，就叫这个东西的谱。所谓频谱，就是把一个信号分解成多个频率单一的分量。

矩阵的谱，就是它的特征值和特征向量，普通的线性代数课本会告诉你定义：如果A v = c v，那么c 就是A的特征值，v就叫特征向量。这仅仅是数学家发明的一种数学游戏么？——也许有些人刚学这个的时候，并一定能深入理解这么个公式代表什么。其实，这里的谱，还是代表了一种分量结构，它为使用“分而治之”策略来研究矩阵的作用打开了一个重要途径。这里我们可以把矩阵理解为一个操作(operator)，它的作用就是把一个向量变成另外一个向量：y = A x。对于某些向量，矩阵对它的作用很简单，A 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 变成一个二元连续函数（面积无限大的矩阵）。这时候矩阵乘法中的求和变成了积分。同样的，A的作用可以理解为把一个连续函数映射为另外一个连续函数，这时候A不叫矩阵，通常被称为算子。对于算子，上面的谱分析方法同样适用（从有限到无限，在数学上还需要处理一下，不多说了）——这个就是泛函分析中的一个重要部分——谱论（Spectral Theory）。

马尔可夫过程——从时间的角度理解图

回到“图”这个题目，那么图的谱是干什么的呢？按照上面的理解，似乎是拿来分解一个图的。这里谱的作用还是分治，但是，不是直观的理解为把图的大卸八块，而是把要把在图上运行的过程分解成简单的过程的叠加。如果一个图上每个节点都有一个值，那么在图上运行的过程就是对这些值进行更新的过程。一个简单，大家经常使用的过程，就是马尔可夫过程(Markov Process)。

学过随机过程的朋友都了解马尔可夫过程。概念很简单——“将来只由现在决定，和过去无关”。考虑一个图，图上每个点有一个值，会被不断更新。每个点通过一些边连接到其它一些点上，对于每个点，这些边的值都是正的，和为1。在图上每次更新一个点的值，就是对和它相连接的点的值加权平均。如果图是联通并且非周期（数学上叫各态历经性, ergodicity)，那么这个过程最后会收敛到一个唯一稳定的状态（平衡状态)。

图上的马尔可夫更新过程，对于很多学科有着非常重要的意义。这种数学抽象，可以用在什么地方呢？(1) Google对搜索结果的评估(PageRank)原理上依赖于这个核心过程，(2) 统计中一种广泛运用的采样过程MCMC，其核心就是上述的转移过程，(3) 物理上广泛存在的扩散过程（比如热扩散，流体扩散）和上面的过程有很重要的类比，(4) 网络中的信息的某些归纳与交换过程和上述过程相同 (比如Random Gossiping)，还有很多。非常多的实际过程通过某种程度的简化和近似，都可以归结为上述过程。因此，对上面这个核心过程的研究，对于很多现象的理解有重要的意义。各个领域的科学家从本领域的角度出发研究这个过程，得出了很多实质上一致的结论，并且很多都落在了图的谱结构的这个关键点上。

图和谱在此联姻

根据上面的定义，我们看到邻接矩阵A其实就是这个马尔可夫过程的转移概率矩阵。我们把各个节点的值放在一起可以得到一个向量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 + ... （在数学上可以严格证明，对于上述的转移概率矩阵，最大的特征值就是1，这里对应于平衡状态v1，其它的特征状态v2, v3, ..., 对应于特征值1 > c2 > c3 > ... > -1)。那么，我们可以看到，当更新进行了t 步之后，状态变成 u(t) = v1 + c2^t v2 + c3^t v3 + ...，我们看到，除了代表平衡状态的分量保持不变外，其它分量随着t 增长而指数衰减，最后，其它整个趋近于平衡状态。

从上面的分析看到，这个过程的收敛速度，其实是和衰减得最慢的那个非平衡分量是密切相关的，它的衰减速度取决于第二大特征值c2，c2的大小越接近于1，收敛越慢，越接近于0，收敛越快。这里，我们看到了谱的意义。第一，它帮助把一个图上运行的马尔可夫过程分解为多个简单的字过程的叠加，这里面包含一个平衡过程和多个指数衰减的非平衡过程。第二，它指出平衡状态是对应于最大特征值1的分量，而收敛速度主要取决于第二大特征值。

我们这里知道了第二大特征值c2对于描述这个过程是个至关重要的量，究竟是越大越好，还是越小越好呢？这要看具体解决的问题。如果你要设计一个采样过程或者更新过程，那么就要追求一个小的c2，它一方面提高过程的效率，另外一方面，使得图的结构改变的时候，能及时收敛，从而保证过程的稳定。而对于网络而言，小的c2有利于信息的迅速扩散和传播。

聚类结构——从空间的角度理解图

c2的大小往往取决于图上的聚类结构。如果图上的点分成几组，各自聚成一团，缺乏组与组之间的联系，那么这种结构是很不利于扩散的。在某些情况下，甚至需要O(exp(N))的时间才能收敛。这也符合我们的直观想象，好比两个大水缸，它们中间的只有一根很细的水管相连，那么就需要好长时间才能达到平衡。有兴趣的朋友可以就这个水缸问题推导一下，这个水缸系统的第二大特征值和水管流量与水缸的容积的比例直接相关，随比例增大而下降。

对于这个现象进行推广，数学上有一个重要的模型叫导率模型(Conductance)。具体的公式不说了，大体思想是，节点集之间的导通量和节点集大小的平均比例和第二大特征值之间存在一个单调的上下界关系。导率描述的是图上的节点连接的空间结合，这个模型把第二特征值c2和图的空间聚集结构联系在一起了。

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

归纳起来

• 图是表达事物关系和传递扩散过程的重要数学抽象
• 图的矩阵表达提供了使用代数方法研究图的途径
• 谱，作为一种重要的代数方法，其意义在于对复杂对象和过程进行分解
• 图上的马尔可夫更新过程是很多实际过程的一个重要抽象
• 图的谱结构的重要意义在于通过它对马尔可夫更新过程进行分解分析
• 图的第一特征值对应于马尔可夫过程的平衡状态，第二特征值刻画了这个过程的收敛速度（采样的效率，扩散和传播速度，网络的稳定程度）。
• 图的第二特征分量与节点的聚类结构密切相关。可以通过谱结构来分析图的聚类结构。

马尔可夫过程代表了一种时间结构，聚类结构代表了一种空间结构，“谱”把它们联系在一起了，在数学刻画了这种时与空的深刻关系。

留学大半年，经历着不一样的生活，品尝着不一样的滋味，发现自己还有太多的东西需要学习。

对自己，要学会省思；

对朋友，要学会尊重；

对生活，要学会坚强；

对学问，要学会谦恭。

我们所做的topic，一般有几个阶段：

• Analysis: 分析问题，找到问题的关键
• Modeling / Formulation:  对问题进行数学抽象，建立模型，或者formulate目标函数
• Solving: 设计出求解的算法
• Experiments: 实验

最近的工作都集中在Solving这部分，就说说这个吧。

求解的方法

求解问题有很多不同的方法，就我知道的来说，大概有这么几个大家族。

1. Heuristics。就是根据对问题的观察而设计的一些简单的方法，不一定遵循什么规范，或者有什么深刻的数学根据。这类方法往往比较简单易懂，intuition比较明显，很多时候performance也挺不错的，不见得比高深的方法差，因而在实际工程中很受欢迎，几乎应用在全部的学科。不过，好像很多朋友对这类方法颇为不屑，认为“没有技术含量”，或者叫做“没有理论深度”。

   确实，有相当部分的Heuristics纯粹粗制滥造，投机取巧。不过，还有很多Heuristics虽然简单，但是切中问题要害，在长期的复杂的实际应用中经受住了考验。这些方法，表面看来可能只是再简单不过的几条四则运算公式，说不上多少理论，但是并不代表它没有深刻的理论基础。一个典型的例子是Google PageRank中使用的传导公式（简单版本），道理和公式都很简单，可是，做过类似工作的朋友可能都知道，它和代数图论以及马尔可夫随机过程有着很深的联系。 又比如，Fourier Transform在刚出来的时候，仅仅是工程师的一些heuristics，后来关于它的理论已经成为了泛函分析的一个核心组成部分，也是信号处理的理论基础之一。

   真正好的heuristics，它的好处肯定不是瞎懵出来，而是有内在原因的。对它们的原理的探索，不断带动理论方面的发展，甚至创造了新的理论方向。说到这里，有人可能会argue，这是“理论家们在故弄玄虚混饭吃”。Hmm，这种说法我不能认同，但是，确实存在“把工程方法胡乱进行理论化”的事实。什么才叫有价值的理论化，而不是故弄玄虚，确实值得思考，这里先不展开了。

2. Analytical Solution。当你把问题formulate出来后，有些情况是直接可以从问题推导出解析解的。这种情况通常存在于objective function是Linear或者Quadratic的情况。大家都很喜欢这种情况的出现，理论漂亮，实现简洁。但是，据我的观察，很多情况下，这种elegance是通过减化模型换取的。把cost写成quadratic term，把distribution假设为Gauss，很多时候都能得到这样的结果。

   我不反对进行简化，也欣赏漂亮的analytical solution，如果它把问题解决得很好。但是，这里面有个问题，很多能获得简单解析解的问题已经被做过了，剩下的很多难点，未必是一个简化模型能有效解决的。简化是一种很好的方法，但是，使用起来，尤其是在实际中的应用必须慎重，要清楚了解它们可能带来的问题。

   比如说，很多模型喜欢使用差的平方来衡量误差大小。但是，这很早就被指出是unrobust的，一个很大的deviation会dominate整个optimization，使得solution严重偏离方向。如果这种robustness在带解决的问题中是一个必须考虑的要素，那么用平方误差就要仔细考虑了。

3. Numerical Optimization。如果formulation没有解析解，那么自然的想法就是使用数值方法求解。目前大家常用的是基于Gradient/Hessian之类的local optimization的方法，有时会加上random initialization。如果objective function是convex的，那么这种方法保证收敛到global optimal，这是大家很希望的。convex problem无论在formulation还是在solution的阶段，都是很有学问的。很多问题可以formulate成convex的，但是未必都那么直接，这需要有这方面的基础。Solving一个convex problem有现成的方法，但是，如果能对问题的结构有insightful的观察，可能能利用问题本身的特点大幅度降低求解的复杂度——这往往比直接把问题扔进solver里面等答案更有意义。

   除了convex optimization，还有一种数值方法应用非常广泛，叫做coordinate ascend或者alternate optimization。大概的思路是，几个有关的变量，轮流选择某个去优化，暂时固定其它的。在Machine Learning里面非常重要的Expectation-Maximization (EM算法)就属于这个大家族。另外，很多复杂的graphical model采用的variational inference也是属于此类。使用这类方法，有两个问题：一个是如果几个variable之间相互影响，变一个，其他跟着变的话，那么直接使用这种方法可能是错误的，并不能保证收敛。另外一个问题是，如果problem不是convex的话，可能没有任何保证你得到的solution和global solution有联系。很可能，你得到的解和真正的全局最优解相差十万八千里。这个没有什么通用有效的途径来解决。不过，针对具体问题的结构特点，在求解过程中施加一定的引导是有可能的。

4. Dynamic Programming。这个方法更多见于经典计算机算法中，不过现在越来越多在Vision和Learning见到它的影子。主要思路是把大问题分解为小问题，总结小问题的solution为大问题的solution。至于如何设计分解和综合的过程，依赖于对问题的观察和分析，并无通用的法则可循。用DP解决问题的洞察力需要逐步的积累。不少经典算法就源自于DP，比如shotest path。一个可能有用的观察是，如果问题或者模型呈现链状，树状，或者有向无环图结构的，可能很有希望能通过DP高效解决。

5. Local Exchange。很多建立在图上的问题，都可以通过某种局部交换来达到全局的平衡。像Belief propagation, Junction tree等等在graphical model的重要inference方法，还有tranduction model，都用到了类似的策略。这在实践中被证明为非常有效。但是，并不是随便设计的局部交换过程都是收敛的。这里面需要关注两个问题：(1)交换过程是不是能保证某些重要的invariance不被破坏；(2)交换过程中，是不是有一个objective，比如距离全局平衡的deviation，它在每一步都保持单调。有很多交换过程，在有向无环图中保证收敛，但是，在带环图中由于信息的重复传递可能引起不稳定，或者不能收敛到正确的解。

6. Monte Carlo Sampling。蒙特卡罗采样的原理非常简单，就是用样本平均，来逼近期望（这个可能需要用intractable的积分完成，没法直接算）。求平均很简单，关键在于采样过程。我们求解问题，通常是在后验分布中采样，这种分布在大部分问题中，不要说直接采样了，可能连解析形式都没法给出。如果采样问题有效解决了，基本上我们研究的大部分问题其实都可以通过采样完成。

   由于直接采样往往非常困难，于是就产生了其它的方法，间接做这个事情。一种想法就是，既然p(x)不好直接采，我找一个比较容易采样的q(x)来逼近p(x)，然后给从q(x)采出的每个样本加一个weight，p(x) / q(x)。这在理论上被严格证明是对的——这种方法叫做Importance Sampling。这里的问题在于，如果q(x)和p(x)不太接近，那么采样效率非常低下，如果在一个高维空间，可能采1000年都达不到要求。可是，要得到一个approximate很好的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)。这个的想法是，设计一个马尔科夫链，让它的平衡分布恰好是p(x)，那么等它平衡时开始采。以前我们做随机过程作业是已知一个markov chain，求equilibrium distribution，设计MCMC就是反过来了。最重要的MCMC方法莫过于Metropolis-Hastings Algorithm和Gibbs Sampling，前者常被用于设计在solution space的随机游走(Random walk)，后者则是conditional sampling的基础方法。

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

   Monte Carlo方法较早的时候主要用于统计物理，目前已经广泛应用于计算机，生物，化学，地质学，经济学，社会学等等的研究。这是目前所知道的用于求解复杂的真实模型的最有效的方法。它的核心，就是猜——你直接解不出来，只好猜了，呵呵。但是，怎样才能猜得准，则是大有学问——几十年来各个领域关于Monte Carlo研究的工作汗牛充栋，有很多进展，但是还有很长的路要走。

和这里很多留学生一样，我一向潜心于自己的学习和研究。可是最近，我们的世界并不宁静，我认识的不只一个在美国的朋友受到了不太友好的挑衅——在不知不觉中，我们可能已经身处反分裂和支持奥运的前线。我看到包括MIT CSSA在内的很多学生团体开始组织起来支持自己的祖国。我没有具体帮上什么，但是，我对所有在用自己的行动捍卫国家荣誉的同胞怀有最深的敬意。我也希望，我的努力，能让外国的朋友明白中国人是值得尊敬的。

很多做research的朋友喜欢top-down approach，包括我自己。就是说，在开始一个topic的时候，在第一时间就设定了大体的formulation，model又或者methodology。至于选择哪种设定，往往取决于研究者本身的偏好，知识背景，或者对问题的第一反应。

接下来的事情就顺理成章了，推导数学模型和相关公式以及算法步骤，然后设计程序进行实验。当然少不了再拉上几个相关工作，比较一番。如果自己的设计很幸运地有明显的improvement，于是非常满意，开始写paper（在不少情况下，paper的理论部分甚至提前写好了）。可是，如果不work呢？ 通常大家会采取下面一些方法中的一种或者几种：

• 观察实验结果，猜想几个不work的原因，然后回头局部调整模型和算法；
• 换一下数据集，看看能不能work
• 祭起“终极法宝”——调参数，人工修改或者写脚本遍历，直到找到一组work的参数为止。不过，那些作为“绿叶”用的参照算法，通常是没有这种待遇了。

无论如何，你总算把实验搞定了。但是，为什么work呢？除了几条曲线，你总得找一些“让人信服”的理由。在我所在的领域，有一些理由几乎是万能的，因而普遍出现在paper里面：

• 以前的算法，不考虑某某因素，而这个因素是很重要的，我的算法考虑了，所以效果更好
• 以前的算法，把某些因素分开考虑，但是它们实际上是相关联了，我的算法把它们结合在一起，体现了这种关联关系，所以更好
• 以前的算法是线性的，但是这个问题本身明显是非线性的，我这里用了非线性的方法，所以更符合实际。为了进一步解释清楚，还画出一些二维或者三维的toy samples，显示出线性和非线性有“多么巨大的差别”
• 以前的方法用的是参数化模型（比如高斯分布），而现实世界明显不是这样子，我这里采用非参数化模型，能更准确地逼近实际分布
• 主流方法大都采用某某算法完成某个步骤，或者某某特征来描述某个方面，其实这个算法或者特征在这里不太适合，我换了一个更适合的或者更“先进”的。

还有很多，不一而足。总体来说，就是增加了某方面的复杂性，推广了模型，或者把某些部分变得更加时髦，数学更深。正因为多了东西可以调节，只要花上足够时间去设定参数，还是有很大机会能找到一组能得到improvement的参数的。可是，这种improvement是不是真正有意义呢？是不是足够significant，以至于所增加的复杂性是值得的呢？

我们的世界总是无限复杂的，和无数的因素相关，这些因素又总是有某种联系。我们的前辈们留给我们的最好的方法，就是从问题中分离出最关键的要素，和最重要的关系，而非不断地增加价值不大的因素，建立意义不大的联系。

我并不是一个完全拒绝复杂，但是我个人觉得对复杂性的增长应该慎重。每增加一个要素，都应该是基于对问题的深入分析，而不是先入为主的设想和冠冕堂皇的理由。这不完全是知识能力的问题，更多的是一种治学态度——是不是愿意安心下来对问题本身进行深入细致的解剖，找出问题本身的关键所在，而不是脱离问题预先构想某种“漂亮”模型或者“巧妙”方法，并且通过上面所述的种种方法推销出去。

研究是一种创新的过程，广拓思路是必须的。但是真正有价值的novelty应该是建立在对问题本身的深入理解，确实发现了别人忽略的关键因素，或者主流算法的真正不足，并且创造性地提出解决方法。这需要持之以恒的努力。真正经得起考验的学术价值，源于解决还没有被解决的问题，而不是使用了某种所谓别人没用过的“新颖”方法来解决本来已经解决的问题，又或者给模型加入某个要素来取得非实质性的性能改进。

上面所说的这些问题，几乎都发生在我的身上。而汤老师的很多建议，其实正是指出了这些问题，却没有被我认真思考，反而总是以为只要理论做得高深，模型设计得精巧，就是好的工作。来了MIT之后，更多地阅读一些有历史价值的文章（现在看CVPR反而比较少了），接触一些更加solid的工作。许多有重要贡献的工作，往往未必有很炫的方法和模型，但是，其对于问题本身的深入发掘和洞察却令我惭愧。

要做真正的学问，首先要戒除浮躁。