笑对人生，傲立寰宇

有好些时间没有更新blog，因为这段时间有很多别的事情：所做的research最近在进行implementation，观看奥运，接待朋友，搬家 。。。。。。现在生活开始转回学期的状态了。

这一年来在Csail一直使用Linux工作站，它的性能非常出色。前两天工作到晚上的时候，有点疲惫，想干点别的——终于发现这台机子的系统缺了一点东西——没有游戏。于是，自己动手，丰衣足食，用MATLAB写了一个扫雷，呵呵。我不是艺术青年，也就谈不上有多少美工设计了，不过玩起来的感觉，和在windows下的扫雷也没有太大差别。

程序放到Matlab Exchange上面了，有兴趣就去瞧瞧吧，呵呵

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=21211&objectType=file

后来才发现，KDE下面还是有扫雷的，叫KMines。不过，还是自己写的东西比较亲切了。

现在越来越多的科学计算以外的东西开始在matlab下面被实现了——虽然不如在windows下面的counterpart pp，不过功能都挺齐全。Emacs的Fans们可以一天到晚只用Emacs一个程序不出来完成几乎全部的工作和娱乐。matlab离这种“操作系统化”的境界也不远了。

matlab自己的浏览器，你可以试试： web('www.google.com');  还有自己的ftp，文件下载命令urlread，音乐播放命令play，和电影播放命令movie。（在低版本matlab，上面的部分命令可能还没提供）

像email, painter这样的功能虽然暂时还没有内建，不过，实现起来也不是特别困难了。也许在不远的将来，我们真的可以长时间在matlab下面完成各种工作不用出来。

----------------------------------------------------------------------------------------------------

既然说到这里，就继续说点MATLAB的GUI编程吧。以前，在香港的时候，当算法要移植到系统的时候，都是用C#来完成外围的UI。现在，已经长时间在Linux下面工作了。坦白的说，可以选择的UI结构其实是更多了，主要有GTK, Qt，还有Java里面的Swing, Swt。但是，它们现在还处在战国时代，百家争鸣，却没有主流。现在自己写一些UI也主要是为了自己方便，也就不想折腾太多架构了，还是回到Matlab去吧。

比起其它高级语言下面的常用UI体系，Matlab的UI还是比较“土”的——但是，非常实用。它提供了一种普通语言一般没有内建的控件：axes，你可以直接在里面绘制各种图表。另外一个优势，就是和matlab代码的无缝套接，原来写好的算法，不需要任何移植或者重新封装，就能在这个UI上面直接调用。虽然长得很朴素，但是，对于科学方面的应用，它的开发效率无疑是最高的。

它提供了两种编写GUI应用程序的方式：使用Guide（一个类似于窗口设计器的东西，能直接往里面拉控件和调节参数)，或者是直接手工写代码。我个人比较偏向于使用后者，一来自己写的东西代码比较简洁，二来自己能够自由选择合适的程序结构（取决于应用的逻辑），而不受限于自动生成的程序结构。

但是，写matlab对GUI应用有一个根本性的缺陷，那就是这种语言的核心不支持多线程编程（它的新版支持多核运算，但是和multithread不是一个概念），任何长时间的程序一旦跑起来，就会把其它东西的运行block掉。因此，它适合用于单步运算时间不太长的交互式算法，而长时间运行的陈程序，比如大规模的training，一般情况还是不要用UI来控制了。

这篇blog和学术没有关系。前面连篇累牍的东西，我想很多朋友也看得挺累的了，这次就先歇一歇吧，讲点学术以外的生活。

严格来说，我们现在正在放暑假，不过，说实话，除了不上课外，和平时也没什么区别。入夏以来，这里的气温一天高比一天——今天的最高温度已经突破95华氏度了。住的地方没有空调，这对于我这个长期生活在南方，对空调有严重依赖的人来说，确实是一个很有挑战性的体验。

因为不用上课了，生活也开始丰富了一些。

暂停了一年多（hmm... 不知道这还叫不叫“暂停”）的羽毛球运动恢复起来了。看来，美国人确实对badminton不太感冒，MIT的体育馆虽然只有四五个场子，我们平常去打的时候，经常都有空场，在里面打球的很多是中国同学（当然也包括港澳台同胞了，呵呵）。也有一些老外在里面打球，水平还是很不错的。

我的水平也和在HK的时候差不多——难得的是，大家都在附近的区间，最近几次连续很多场双打，都是(16:14)这样的比分（2006年以前的比赛规则）。打得多了，有点瘾子，心血来潮之下进了一把新拍子。其实，以咱现在的能力，用好拍子也不见得能发挥多少优越性，只是小小的心理满足罢了。

另外一项活动，就是风帆了——这就是学校在河边的好处。我原来正好却一个partner去学sailing，xiaoqian转来MIT之后，正好和他一起去学习这个玩意。上过两次课后，我们现在已经可以在查尔斯河驾驶小帆船了。有风的时候，乘帆游河确实是一种惬意的生活——不过，“乘风破浪会有时，直挂云帆济沧海”的豪情，在这小河上就万难体验了。

因为上船前物品都要寄存，所以，现在还没有我在船上的照片。就先贴几张别人拍的charles river上MIT的风帆遨游的情景吧。

前面几篇谈了一些对数学的粗浅看法。其实，如果对某门数学有兴趣，最好的方法就是走进那个世界去学习和体验。

这里说说几本我看过后觉得不错的数学教科书。

1. 线性代数 (Linear Algebra)：

我想国内的大学生都会学过这门课程，但是，未必每一位老师都能贯彻它的精要。这门学科对于Learning是必备的基础，对它的透彻掌握是必不可少的。我在科大一年级的时候就学习了这门课，后来到了香港后，又重新把线性代数读了一遍，所读的是

Introduction to Linear Algebra (3rd Ed.)  by Gilbert Strang.

这本书是MIT的线性代数课使用的教材，也是被很多其它大学选用的经典教材。它的难度适中，讲解清晰，重要的是对许多核心的概念讨论得比较透彻。我个人觉得，学习线性代数，最重要的不是去熟练矩阵运算和解方程的方法——这些在实际工作中MATLAB可以代劳，关键的是要深入理解几个基础而又重要的概念：子空间(Subspace)，正交(Orthogonality)，特征值和特征向量(Eigenvalues and eigenvectors)，和线性变换(Linear transform)。从我的角度看来，一本线代教科书的质量，就在于它能否给这些根本概念以足够的重视，能否把它们的联系讲清楚。Strang的这本书在这方面是做得很好的。

而且，这本书有个得天独厚的优势。书的作者长期在MIT讲授线性代数课(18.06)，课程的video在MIT的Open courseware网站上有提供。有时间的朋友可以一边看着名师授课的录像，一边对照课本学习或者复习。

http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/CourseHome/index.htm

2. 概率和统计 (Probability and Statistics):

概率论和统计的入门教科书很多，我目前也没有特别的推荐。我在这里想介绍的是一本关于多元统计的基础教科书：

Applied Multivariate Statistical Analysis (5th Ed.)  by Richard A. Johnson and Dean W. Wichern

这本书是我在刚接触向量统计的时候用于学习的，我在香港时做研究的基础就是从此打下了。实验室的一些同学也借用这本书学习向量统计。这本书没有特别追求数学上的深度，而是以通俗易懂的方式讲述主要的基本概念，读起来很舒服，内容也很实用。对于Linear regression, factor analysis, principal component analysis (PCA), and canonical component analysis (CCA)这些Learning中的基本方法也展开了初步的论述。

之后就可以进一步深入学习贝叶斯统计和Graphical models。一本理想的书是

Introduction to Graphical Models (draft version).  by M. Jordan and C. Bishop.

我不知道这本书是不是已经出版了（不要和Learning in Graphical Models混淆，那是个论文集，不适合初学）。这本书从基本的贝叶斯统计模型出发一直深入到复杂的统计网络的估计和推断，深入浅出，statistical learning的许多重要方面都在此书有清楚论述和详细讲解。MIT内部可以access，至于外面，好像也是有电子版的。

3. 分析 (Analysis)：

我想大家基本都在大学就学过微积分或者数学分析，深度和广度则随各个学校而异了。这个领域是很多学科的基础，值得推荐的教科书莫过于

Principles of Mathematical Analysis, by Walter Rudin

有点老，但是绝对经典，深入透彻。缺点就是比较艰深——这是Rudin的书的一贯风格，适合于有一定基础后回头去看。

在分析这个方向，接下来就是泛函分析(Functional Analysis)。

Introductory Functional Analysis with Applications, by Erwin Kreyszig.

适合作为泛函的基础教材，容易切入而不失全面。我特别喜欢它对于谱论和算子理论的特别关注，这对于做learning的研究是特别重要的。Rudin也有一本关于functional analysis的书，那本书在数学上可能更为深刻，但是不易于上手，所讲内容和learning的切合度不如此书。

在分析这个方向，还有一个重要的学科是测度理论(Measure theory)，但是我看过的书里面目前还没有感觉有特别值得介绍的。

4. 拓扑 (Topology)：

在我读过的基本拓扑书各有特色，但是综合而言，我最推崇：

Topology (2nd Ed.)  by James Munkres

这本书是Munkres教授长期执教MIT拓扑课的心血所凝。对于一般拓扑学(General topology)有全面介绍，而对于代数拓扑(Algebraic topology)也有适度的探讨。此书不需要特别的数学知识就可以开始学习，由浅入深，从最基本的集合论概念（很多书不屑讲这个）到Nagata-Smirnov Theorem和Tychonoff theorem等较深的定理（很多书避开了这个）都覆盖了。讲述方式思想性很强，对于很多定理，除了给出证明过程和引导你思考其背后的原理脉络，很多令人赞叹的亮点——我常读得忘却饥饿，不愿释手。很多习题很有水平。

5. 流形理论 (Manifold theory)：

对于拓扑和分析有一定把握时，方可开始学习流形理论，否则所学只能流于浮浅。我所使用的书是

Introduction to Smooth Manifolds.  by John M. Lee

虽然书名有introduction这个单词，但是实际上此书涉入很深，除了讲授了基本的manifold, tangent space, bundle, sub-manifold等，还探讨了诸如纲理论(Category theory)，德拉姆上同调(De Rham cohomology)和积分流形等一些比较高级的专题。对于李群和李代数也有相当多的讨论。行文通俗而又不失严谨，不过对某些记号方式需要熟悉一下。

虽然李群论是建基于平滑流形的概念之上，不过，也可能从矩阵出发直接学习李群和李代数——这种方法对于急需使用李群论解决问题的朋友可能更加实用。而且，对于一个问题从不同角度看待也利于加深理解。下面一本书就是这个方向的典范：

Lie Groups, Lie Algebras, and Representations: An Elementary Introduction.  by Brian C. Hall

此书从开始即从矩阵切入，从代数而非几何角度引入矩阵李群的概念。并通过定义运算的方式建立exponential mapping，并就此引入李代数。这种方式比起传统的通过“左不变向量场(Left-invariant vector field)“的方式定义李代数更容易为人所接受，也更容易揭示李代数的意义。最后，也有专门的论述把这种新的定义方式和传统方式联系起来。

————————————————————————————

无论是研究Vision, Learning还是其它别的学科，数学终究是根基所在。学好数学是做好研究的基石。学好数学的关键归根结底是自己的努力，但是选择一本好的书还是大有益处的。不同的人有不同的知识背景，思维习惯和研究方向，因此书的选择也因人而异，只求适合自己，不必强求一致。上面的书仅仅是从我个人角度的出发介绍的，我的阅读经历实在非常有限，很可能还有比它们更好的书（不妨也告知我一声，先说声谢谢了）。

Learning是一个融会多种数学于一体的领域。说起与此有关的数学学科，我们可能会迅速联想到线性代数以及建立在向量空间基础上的统计模型——事实上，主流的论文中确实在很大程度上基于它们。

R^n (n-维实向量空间) 是我们在paper中见到最多的空间，它确实非常重要和实用，但是，仅仅依靠它来描述我们的世界并不足够。事实上，数学家们给我们提供了丰富得多的工具。

“空间”(space)，这是一个很有意思的名词，几乎出现在所有的数学分支的基础定义之中。归纳起来，所谓空间就是指一个集合以及在上面定义的某种数学结构。关于这个数学结构的定义或者公理，就成为这个数学分支的基础，一切由此而展开。

还是从我们最熟悉的空间——R^n 说起吧。大家平常使用这个空间的时候，除了线性运算，其实还用到了别的数学结构，包括度量结构和内积结构。

• 第一，它是一个拓扑空间(Topological space)。而且从拓扑学的角度看，具有非常优良的性质：Normal (implying Hausdorff and Regular), Locally Compact, Paracompact, with Countable basis, Simply connected (implying connected and path connected), Metrizable. 
• 第二，它是一个度量空间(Metric space)。我们可以计算上面任意两点的距离。
• 第三，它是一个有限维向量空间(Finite dimensional space)。因此，我们可以对里面的元素进行代数运算（加法和数乘），我们还可以赋予它一组有限的基，从而可以用有限维坐标表达每个元素。
• 第四，基于度量结构和线性运算结构，可以建立起分析(Analysis)体系。我们可以对连续函数进行微分，积分，建立和求解微分方程，以及进行傅立叶变换和小波分析。
• 第五，它是一个希尔伯特空间（也就是完备的内积空间）(Hilbert space, Complete inner product space)。它有一套很方便计算的内积(inner product)结构——这个空间的度量结构其实就是从其内积结构诱导出来。更重要的，它是完备的(Complete)——代表任何一个柯西序列(Cauchy sequence)都有极限——很多人有意无意中其实用到了这个特性，不过习惯性地认为是理所当然了。
• 第六，它上面的线性映射构成的算子空间仍旧是有限维的——一个非常重要的好处就是，所有的线性映射都可以用矩阵唯一表示。特别的，因为它是有限维完备空间，它的泛函空间和它本身是同构的，也是R^n。因而，它们的谱结构，也就可以通过矩阵的特征值和特征向量获得。
• 第七，它是一个测度空间——可以计算子集的大小（面积/体积）。正因为此，我们才可能在上面建立概率分布(distribution)——这是我们接触的绝大多数连续统计模型的基础。

我们可以看到，这是一个非常完美的空间，为我们的应用在数学上提供了一切的方便，在上面，我们可以理所当然地认为它具有我们希望的各种良好性质，而无须特别的证明；我们可以直接使用它的各种运算结构，而不需要从头建立；而且很多本来不一样的概念在这里变成等价的了，我们因此不再需要辨明它们的区别。

以此为界，Learning的主要工作分成两个大的范畴：

1. 建立一种表达形式，让它处于上面讨论的R^n空间里面。
2. 获得了有限维向量表达后，建立各种代数算法或者统计模型进行分析和处理。

这里只讨论第一个范畴。先看看，目前用得比较广泛的一些方法：

1. 直接基于原始数据建立表达。我们关心的最终目标是一个个现实世界中的对象：一幅图片，一段语音，一篇文章，一条交易记录，等等。这些东西大部分本身没有附着一个数值向量的。为了构造一个向量表达，我们可以把传感器中记录的数值，或者别的什么方式收集的数值数据按照一定的顺序罗列出来，就形成一个向量了。如果有n个数字，就认为它们在R^n里面。

   不过，这在数学上有一点小问题，在大部分情况下，根据数据产生的物理原理，这些向量的值域并不能充满整个空间。比如图像的像素值一般是正值，而且在一个有界闭集之中。这带来的问题是，对它们进行线性运算很可能得到的结果会溢出正常的范围——在大部分paper中，可能只是采用某些heuristics的手段进行简单处理，或者根本不管，很少见到在数学上对此进行深入探讨的——不过如果能解决实际问题，这也是无可厚非的，毕竟不是所有的工作都需要像纯数学那样追求严谨。

2. 量化(quantization)。这是在处理连续信号时被广泛采用的方式。只是习以为常，一般不提名字而已。比如一个空间信号（Vision中的image）或者时间信号，它们的domain中的值是不可数无限大的(uncountably infinite)，不要说表示为有限维向量，即使表达为无限序列也是不可能的。在这种情况下，一般在有限域内，按照一定顺序每隔一定距离取一个点来代表其周围的点，从而形成有限维的表达。这就是信号在时域或空域的量化。

   这样做不可避免要丢失信息。但是，由于小邻域内信号的高度相关，信息丢失的程度往往并不显著。而且，从理论上说，这相当于在频域中的低通过率。对于有限能量的连续信号，不可能在无限高的频域中依然保持足够的强度，只要采样密度足够，丢失的东西可以任意的少。

   除了表示信号，对于几何形体的表达也经常使用量化，比如表示curve和surface。

3. 找出有限个数充分表达一个对象也许不是最困难的。不过,在其上面建立数学结构却未必了。一般来说，我们要对其进行处理，首先需要一个拓扑结构用以描述空间上的点是如何联系在一起。直接建立拓扑结构在数学上往往非常困难，也未必实用。因此，绝大部分工作采取的方式是首先建立度量结构。一个度量空间，其度量会自然地诱导出一个拓扑结构——不过，很多情况下我们似乎会无视它的存在。

   最简单的情况，就是使用原始向量表达的欧氏距离(Euclidean distance)作为metric。不过，由于原始表达数值的不同特性，这种方式效果一般不是特别好，未必能有效表达实际对象的相似性（或者不相似性）。因此，很多工作会有再此基础上进行度量的二次建立。方式是多种多样的，一种是寻求一个映射，把原空间的元素变换到一个新的空间，在那里欧氏距离变得更加合适。这个映射发挥的作用包括对信息进行筛选，整合，对某些部分进行加强或者抑制。这就是大部分关于feature selection，feature extraction，或者subspace learning的文章所要做的。另外一种方式，就是直接调节距离的计算方式（有些文章称之为metric learning）。

   这两种方式未必是不同的。如果映射是单射，那么它相当于在原空间建立了一个不同的度量。反过来，通过改变距离计算方式建立的度量在特定的条件下对应于某种映射。

4. 大家可能注意到，上面提到的度量建立方法，比如欧氏距离，它需要对元素进行代数运算。对于普通的向量空间，线性运算是天然赋予的，我们无须专门建立，所以可以直接进行度量的构造——这也是大部分工作的基础。可是，有些事物其原始表达不是一个n-tuple，它可能是一个set，一个graph，或者别的什么特别的object。怎么建立代数运算呢？

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

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

5. 回到我们的正题，除了直接建立运算定义，另外一种方式就是嵌入(embedding)到某个向量空间，从而继承其运算结构为我所用。当然这种嵌入也不是乱来，它需要保持原来这些对象的某种关系。最常见的就是保距嵌入(isometric embedding)，我们首先建立度量结构（绕过向量表达，直接对两个对象的距离通过某种方法进行计算），然后把这个空间嵌入到目标空间，通常是有限维向量空间，要求保持度量不变。

   “嵌入”是一种在数学上应用广泛的手段，其主要目标就是通过嵌入到一个属性良好，结构丰富的空间，从而利用其某种结构或者运算体系。在拓扑学中，嵌入到metric space是对某个拓扑空间建立度量的重要手段。而在这里，我们是已有度量的情况下，通过嵌入获取线性运算的结构。除此以来，还有一种就是前些年比较热的manifold embedding，这个是通过保持局部结构的嵌入，获取全局结构，后面还会提到。

6. 接下来的一个重要的代数结构，就是内积(inner product)结构。内积结构一旦建立，会直接诱导出一种性质良好的度量，就是范数(norm)，并且进而诱导出拓扑结构。一般来说，内积需要建立在线性空间的基础上，否则连一个二元运算是否是内积都无法验证。不过，kernel理论指出，对于一个空间，只要定义一个正定核(positive kernel)——一个符合正定条件的二元运算，就必然存在一个希尔伯特空间，其内积运算等效于核运算。这个结论的重要意义在于，我们可以绕开线性空间，通过首先定义kernel的方式，诱导出一个线性空间(叫做再生核希尔伯特空间 Reproducing Kernel Hilbert Space)，从而我们就自然获得我们所需要的度量结构和线性运算结构。这是kernel theory的基础。

   在很多教科书中，以二次核为例子，把二维空间变成三维，然后告诉大家kernel用于升维。对于这种说法，我一直认为在一定程度上是误导的。事实上，kernel的最首要意义是内积的建立（或者改造），从而诱导出更利于表达的度量和运算结构。对于一个问题而言，选择一个切合问题的kernel比起关注“升维”来得更为重要。

   kernel被视为非线性化的重要手段，用于处理非高斯的数据分布。这是有道理的。通过nonlinear kernel改造的内积空间，其结构和原空间的结构确实不是线性关联，从这个意义上说，它实施了非线性化。不过，我们还应该明白，它的最终目标还是要回到线性空间，新的内积空间仍旧是一个线性空间，它一旦建立，其后的运算都是线性的，因此，kernel的使用就是为了寻求一个新的线性空间，使得线性运算更加合理——非线性化的改造最终仍旧是要为线性运算服务。

   值得一提的是，kernelization本质上说还是一种嵌入过程：对于一个空间先建立内积结构，并且以保持内积结构不变的方式嵌入到一个高维的线性空间，从而继承其线性运算体系。

7. 上面说到的都是从全局的方式建立代数结构的过程，但是那必须以某种全局结构为基础（无论预先定义的是运算，度量还是内积，都必须适用于全空间。）但是，全局结构未必存在或者适合，而局部结构往往简单方便得多。这里就形成一种策略，以局部而达全局——这就是流形(manifold)的思想，而其则根源于拓扑学。

   从拓扑学的角度说，流形就是一个非常优良的拓扑空间：符合Hausdorff分离公理（任何不同的两点都可以通过不相交的邻域分离），符合第二可数公理（具有可数的拓扑基），并且更重要的是，局部同胚于R^n。因此，一个正则(Regular)流形基本就具有了各种最良好的拓扑特性。而局部同胚于R^n，代表了它至少在局部上可以继承R^n的各种结构，比如线性运算和内积，从而建立分析体系。事实上，拓扑流形继承这些结构后形成的体系，正是现代流形理论研究的重点。继承了分析体系的流形，就形成了微分流形(Differential manifold)，这是现代微分几何的核心。而微分流形各点上的切空间(Tangent Space)，则获得了线性运算的体系。而进一步继承了局部内积结构的流形，则形成黎曼流形(Riemann manifold)，而流形的全局度量体系——测地距离(geodesics)正是通过对局部度量的延伸来获得。进一步的，当流行本身的拓扑结构和切空间上的线性结构发生关系——也就获得一簇拓扑关联的线性空间——向量丛(Vector bundle)。

   虽然manifold theory作为现代几何学的核心，是一个博大精深的领域，但是它在learning中的应用则显得非常狭窄。事实上，对于manifold，很多做learning的朋友首先反应的是ISOMAP, LLE, eigenmap之类的算法。这些都属于embedding。当然，这确实是流形理论的一个重要方面。严格来说，这要求是从原空间到其映像的微分同胚映射，因此，嵌入后的空间在局部上具有相同的分析结构，同时也获得了各种好处——全局的线性运算和度量。不过，这个概念在learning的应用中被相当程度的放宽了——微分同胚并不能被完全保证，而整个分析结构也不能被完全保持。大家更关注的是保持局部结构中的某个方面——不过这在实际应用中的折衷方案也是可以理解的。事实表明，当原空间中的数据足够密集的情况下，这些算法工作良好。

   Learning中流形应用的真正问题在于它被过滥地运用于稀疏空间(Sparse space)，事实上在高维空间中撒进去几千乃至几十万点，即使最相邻的几点也难称为局部了，局部的范围和全局的范围其实已经没有了根本差别，连局部的概念都立不住脚的时候，后面基于其展开的一切工作也都没有太大的意义。事实上，稀疏空间有其本身的规律和法则，通过局部形成全局的流形思想从本质上是不适合于此的。虽然，流形是一种非常美的理论，但是再漂亮的理论也需要用得其所——它应该用于解决具有密集数据分布的低维空间。至于，一些paper所报告的在高维空间（比如人脸）运用流形方法获得性能提升，其实未必是因为“流形”本身所起的作用，而很可能是其它方面的因素。

8. 流形在实际应用中起重要作用的还有两个方面：一个是研究几何形体的性质（我们暂且不谈这个），还有就是它和代数结构的结合形成的李群(Lie group)和李代数(Lie algebra)。 当我们研究的对象是变换本身的时候，它们构成的空间是有其特殊性的，比如所有子空间投影形成了Grassmann流形，所有的可逆线性算子，或者仿射算子，也形成各自的流形。对他们的最重要操作是变换的结合，而不是加法数乘，因此，它们上面定义的更合适的代数结构应该是群和不是线性空间。而群和微分流形的结合体——李群则成为它们最合适的描述体系——而其切空间则构成了一种加强的线性空间：李代数，用于描述其局部变化特性。

   李代数和李群的关系是非常漂亮的。它把变换的微变化转换成了线性空间的代数运算，使得移植传统的基于线性空间的模型和算法到李空间变得可能。而且李代数中的矩阵比起变换本身的矩阵甚至更能反映变换的特性。几何变换的李代数矩阵的谱结构就能非常方便地用于分析变换的几何特性。

   最后，回头总结一下关于嵌入这个应用广泛的策略，在learning中的isometry, kernel和manifold embedding都属于此范畴，它们分别通过保持原空间的度量结构，内积结构和局部结构来获得到目标（通常是向量空间）的嵌入，从而获得全局的坐标表达，线性运算和度量，进而能被各种线性算法和模型所应用。

   在获得这一系列好处的同时，也有值得我们注意的地方。首先，嵌入只是一种数学手段，并不能取代对问题本身的研究和分析。一种不恰当的原始结构或者嵌入策略，很多时候甚至适得其反——比如稀疏空间的流形嵌入，或者选取不恰当的kernel。另外，嵌入适合于分析，而未必适合于重建或者合成。这是因为嵌入是一个单射(injection)，目标空间不是每一个点都和原空间能有效对应的。嵌入之后的运算往往就打破了原空间施加的限制。比如两个元素即使都是从原空间映射过来，它们的和却未必有原像，这时就不能直接地回到原空间了。当然可以考虑在原空间找一个点它的映射与之最近，不过这在实际中的有效性是值得商榷的。

和Learning有关的数学世界是非常广博的，我随着学习和研究的深入，越来越发现在一些我平常不注意的数学分支中有着适合于问题的结构和方法。比如，广群(groupoid)和广代数(algebroid)能克服李群和李代数在表示连续变换过程中的一些困难——这些困难困扰了我很长时间。解决问题和建立数学模型是相辅相成的，一方面，一个清晰的问题将使我们有明确的目标去寻求合适的数学结构，另一方面，对数学结构的深入理解对于指导问题的解决也是有重要作用的。对于解决一个问题来说，数学工具的选择最重要的是适合，而不是高深，但是如果在现有数学方法陷入困难的时候，寻求更高级别的数学的帮助，往往能柳暗花明。数学家长时间的努力解决的很多问题，并不都是理论游戏，他们的解决方案中很多时候蕴含着我们需要的东西，而且可能导致对更多问题的解决——但是我们需要时间去学习和发现它们。

近日来，抽空再读了一遍点集拓扑(Point Set Topology)，这是我第三次重新学习这个理论了。我看电视剧和小说，极少能有兴致看第二遍，但是，对于数学，每看一次都有新的启发和收获。

代数，分析，和拓扑，被称为是现代数学的三大柱石。最初读拓扑，是在两三年前，由于学习流形理论的需要。可是，随着知识的积累，发现它是很多理论的根基。可以说，没有拓扑，就没有现代意义的分析与几何。我们在各种数学分支中接触到的最基本的概念，比如，极限，连续，距离（度量），边界，路径，在现代数学中，都源于拓扑。

拓扑学是一门非常奇妙的学科，它把最直观的现象和最抽象的概念联系在一起了。拓扑描述的是普遍使用的概念（比如开集，闭集，连续），我们对这些概念习以为常，理所当然地使用着，可是，真要定义它，则需要对它们本质的最深刻的洞察。数学家们经过长时间的努力，得到了这些概念的现代定义。这里面很多第一眼看上去，会感觉惊奇——怎么会定义成这个样子。

首先是开集。在学习初等数学时，我们都学习开区间 (a, b)。可是，这只是在一条线上的，怎么推广到二维空间，或者更高维空间，或者别的形体上呢？最直观的想法，就是“一个不包含边界的集合”。可是，问题来了，给一个集合，何谓“边界”？在拓扑学里面，开集(Open Set)是最根本的概念，它是定义在集合运算的基础上的。它要求开集符合这样的条件：开集的任意并集和有限交集仍为开集。

我最初的时候，对于这样的定义方式，确实百思不解。不过，读下去，看了和做了很多证明后，发现，这样的定义一个很重要的意义在于：它保证了开集中每个点都有一个邻域包含在这个集合内——所有点都和外界（补集）保持距离。这样的理解应该比使用集合运算的定义有更明晰的几何意义。但是，直观的东西不容易直接形成严谨的定义，使用集合运算则更为严格。而集合运算定义中，任意并集的封闭性是对这个几何特点的内在保证。

另外一个例子就是“连续函数”(Continuous Function)。在学微积分时，一个耳熟能详的定义是“对任意的epsilon > 0，存在delta > 0，使得 。。。。”，背后最直观的意思就是“足够近的点保证映射到任意小的范围内”。可是，epsilon, delta都依赖于实空间，不在实空间的映射又怎么办呢？拓扑的定义是“如果一个映射的值域中任何开集的原像都是开集，那么它连续。”这里就没有epsilon什么事了。

这里的关键在于，在拓扑学中，开集的最重要意义就是要传递“邻域”的意思——开集本身就是所含点的邻域。这样连续定义成这样就顺理成章了。稍微把说法调节一下，上面的定义就变成了“对于f(x)的任意领域U，都有x的一个邻域V，使得V里面的点都映射到U中。”

这里面，我们可以感受到为什么开集在拓扑学中有根本性的意义。既然开集传达“邻域”的意思，那么，它最重要的作用就是要表达哪些点靠得比较近。给出一个拓扑结构，就是要指出哪些是开集，从而指出哪些点靠得比较近，这样就形成了一个聚集结构——这就是拓扑。

可是这也可以通过距离来描述，为什么要用开集呢，反而不直观了。某种意义上说，拓扑是“定性”的，距离度量是“定量”的。随着连续变形，距离会不断变化，但是靠近的点还是靠近，因此本身固有的拓扑特性不会改变。拓扑学研究的就是这种本质特性——连续变化中的不变性。

在拓扑的基本概念中，最令人费解的，莫过于“紧性”(Compactness)。它描述一个空间或者一个集合“紧不紧”。正式的定义是“如果一个集合的任意开覆盖都有有限子覆盖，那么它是紧的”。乍一看，实在有点莫名其妙。它究竟想描述一个什么东西呢？和“紧”这个形容词又怎么扯上关系呢？

一个直观一点的理解，几个集合是“紧”的，就是说，无限个点撒进去，不可能充分散开。无论邻域多么小，必然有一些邻域里面有无限个点。上面关于compactness的这个定义的玄机就在有限和无限的转换中。一个紧的集合，被无限多的小邻域覆盖着，但是，总能找到其中的有限个就能盖全。那么，后果是什么呢？无限个点撒进去，总有一个邻域包着无数个点。邻域们再怎么小都是这样——这就保证了无限序列中存在极限点。

Compact这个概念虽然有点不那么直观，可是在分析中有着无比重要的作用。因为它关系到极限的存在性——这是数学分析的基础。了解泛函分析的朋友都知道，序列是否收敛，很多时候就看它了。微积分中，一个重要的定理——有界数列必然包含收敛子列，就是根源于此。

在学习拓扑，或者其它现代数学理论之前，我们的数学一直都在有限维欧氏空间之中，那是一个完美的世界，具有一切良好的属性，Hausdorff, Locally compact, Simply connected，Completed，还有一套线性代数结构，还有良好定义的度量，范数，与内积。可是，随着研究的加深，终究还是要走出这个圈子。这个时候，本来理所当然的东西，变得不那么必然了。

• 两个点必然能分开？你要证明空间是Hausdorff的。
• 有界数列必然存在极限点？这只在locally compact的空间如此。
• 一个连续体内任意两点必然有路径连接？这可未必。

一切看上去有悖常理，而又确实存在。从线性代数到一般的群，从有限维到无限维，从度量空间到拓扑空间，整个认识都需要重新清理。而且，这些绝非仅是数学家的概念游戏，因为我们的世界不是有限维向量能充分表达的。当我们研究一些不是向量能表达的东西的时候，度量，代数，以及分析的概念，都要重新建立，而起点就在拓扑。

关于MATLAB的效率问题，很多文章，包括我之前写的一些，主要集中在使用向量化以及相关的问题上。但是，最近我在实验时对代码进行profile的过程中，发现在新版本的MATLAB下，for-loop已经得到了极大优化，而效率的瓶颈更多是在函数调用和索引访问的过程中。

由于MATLAB特有的解释过程，不同方式的函数调用和元素索引，其效率差别巨大。不恰当的使用方式可能在本来不起眼的地方带来严重的开销，甚至可能使你的代码的运行时间增加上千倍（这就不是多买几台服务器或者增加计算节点能解决的了，呵呵）。

下面通过一些简单例子说明问题。（实验选在装有Windows Vista的一台普通的台式机(Core2 Duo 2.33GHz + 4GB Ram)进行，相比于计算集群, 这可能和大部分朋友的环境更相似一些。实验过程是对某一个过程实施多次的整体进行计时，然后得到每次过程的平均时间，以减少计时误差带来的影响。多次实验，在均值附近正负20%的范围内的置信度高于95%。为了避免算上首次运行时花在预编译上的时间，在开始计时前都进行充分的“热身”运行。）

函数调用的效率

一个非常简单的例子，把向量中每个元素加1。（当然这个例子根本不需要调函数，但是，用它主要是为了减少函数执行本身的时间，突出函数解析和调用的过程。）

作为baseline，先看看最直接的实现

% input u: u is a 1000000 x 1 vector
v = u + 1; 

这个过程平均需要0.00105 sec。

n = numel(u);
% v = zeros(n, 1) has been pre-allocated.
for i = 1 : n
    v(i) = u(i) + 1;
end

所需的平均时间大概是0.00110 sec。从统计意义上说，和vectorization已经没有显著差别。无论是for-loop或者vectorization，每秒平均进行约10亿次“索引-读取-加法-写入”的过程，计算资源应该得到了比较充分的利用。

要是这个过程使用了函数调用呢？MATLAB里面支持很多种函数调用方式，主要的有m-function, function handle, anonymous function, inline, 和feval，而feval的主参数可以是字符串名字，function handle, anonymous function或者inline。

用m-function，就是专门定义一个函数

function y = fm(x)
    y = x + 1;

for i = 1 : n
    v(i) = fm(u(i));
end

function handle就是用@来把一个function赋到一个变量上，类似于C/C++的函数指针，或者C#里面的delegate的作用

fh = @fm;
for i = 1 : n
    v(i) = fh(u(i));
end

anonymous function是一种便捷的语法来构造简单的函数，类似于LISP, Python的lambda表达式

fa = @(x) x + 1;
for i = 1 : n
    v(i) = fa(u(i));
end

inline function是一种传统的通过表达式字符串构造函数的过程

fi = inline('x + 1', 'x');
for i = 1 : n
    v(i) = fi(u(i));
end

feval的好处在于可以以字符串方式指定名字来调用函数，当然它也可以接受别的参数。

v(i) = feval('fm', u(i));
v(i) = feval(fh, u(i));
v(i) = feval(fa, u(i)); 

从这里面，我们可以看到几个有意思的现象：

• 首先，调用自定义函数的开销远远高于一个简单的计算过程。直接写 u(i) = v(i) + 1 只需要  0.0011 秒左右，而写u(i) = fm(v(i)) 则需要0.385秒，时间多了几百倍，而它们干的是同一件事情。这说明了，函数调用的开销远远大于for-loop自己的开销和简单计算过程——在不同情况可能有点差别，一般而言，一次普通的函数调用花费的时间相当于进行了几百次到一两千次双精度浮点加法。
• 使用function handle和anonymous function的开销比使用普通的m-函数要高一些。这可能是由于涉及到句柄解析的时间，而普通的函数在第一次运行前已经在内存中进行预编译。
• inline function的运行时间则令人难以接受了，竟然需要一百多秒（是普通函数调用的四百多倍，是直接计算的十几万倍）。这是因为matlab是在每次运行时临时对字符串表达式（或者它的某种不太高效的内部表达）进行parse。
• feval(fh, u(i))和fh(u(i))，feval(fa, u(i))和fa(u(i))的运行时间很接近，表明feval在接受句柄为主参数时本身开销很小。但是，surprising的是

  for i = 1 : n
      v(i) = feval(@fm, u(i));
  end
  比起
  fh = @fm;
  for i = 1 : n
      v(i) = feval(fh, u(i));
  end
  慢了4.5倍 (前者0.618秒，后者2.788秒)。
  

  for i = 1 : n
      v(i) = feval(@(x) x + 1, u(i));
  end
  比起
  fa = @(x) x + 1;
  for i = 1 : n
      v(i) = feval(fa, u(i));
  end
  竟然慢了53倍(前者0.652秒，后者34.689秒）。
  

  由于在MATLAB的内部实现中，function handle的解析是在赋值过程中进行的，所以预先用一个变量把句柄接下，其效果就是预先完成了句柄解析，而如果直接把@fm或者@(x) x + 1写在参数列上，虽然写法简洁一些，但是解析过程是把参数被赋值到所调函数的局部变量时才进行，每调用一次解析一次，造成了巨大的开销。

• feval使用字符串作为函数名字时，所耗时间比传入句柄大，因为这涉及到对函数进行搜索的时间（当然这个搜索是在一个索引好的cache里面进行（除了第一次），而不是在所有path指定的路径中搜索。）

在2007年以后，MATLAB推出了arrayfun函数，上面的for-loop可以写为

v = arrayfun(fh, u)

元素和域的访问

除了函数调用，数据的访问方式对于效率也有很大影响。MATLAB主要支持下面一些形式的访问：

• array-index  A(i): 
• cell-index:  C{i}; 
• struct field:  S.fieldname
• struct field (dynamic):  S.('fieldname')

这里主要探索单个元素或者域的访问（当然，MATLAB也支持对于子数组的非常灵活整体索引）。

对于一百万次访问的平均时间

我们可以看到MATLAB对于单个数组元素或者静态的struct field的访问，可以达到不错的速度，在主流台式机约每秒2亿次（连同for-loop的开销）。而cell array的访问则明显缓慢，约每秒400万次（慢了50倍）。MATLAB还支持灵活的使用字符串来指定要访问域的语法（动态名字），但是，是以巨大的开销为代价的，比起静态的访问慢了200倍以上。

关于Object-oriented Programming

MATLAB在新的版本中（尤其是2008版），对于面向对象的编程提供了强大的支持。在2008a中，它对于OO的支持已经不亚于python等的高级脚本语言。但是，我在实验中看到，虽然在语法上提供了全面的支持，但是matlab里面面向对象的效率很低，开销巨大。这里仅举几个例子。

• object中的property的访问速度是3500万次，比struct field慢了6-8倍。MATLAB提供了一种叫做dependent property的属性，非常灵活，但是，效率更低，平均每秒访问速度竟然低至2.6万次（这种速度基本甚至难以用于中小规模的应用中）。
• object中method调用的效率也明显低于普通函数的调用，对于instance method，每百万次调用，平均需时5.8秒，而对于static method，每百万次调用需时25.8秒。这相当于每次调用都需要临时解析的速度，而matlab的类方法解析的效率目前还明显偏低。
• MATLAB中可以通过改写subsref和subsasgn的方法，对于对象的索引和域的访问进行非常灵活的改造，可以通过它创建类似于数组的对象。但是，一个符合要求的subsref的行为比较复杂。在一个提供了subsref的对象中，大部分行为都需要subsref进行调度，而默认的较优的调度方式将被掩盖。在一个提供了subsref的类中（使用一种最快捷的实现），object property的平均访问速度竟然降到1万5千次每秒。

建议

根据上面的分析，对于撰写高效MATLAB代码，我有下面一些建议：

1. 虽然for-loop的速度有了很大改善，vectorization（向量化）仍旧是改善效率的重要途径，尤其是在能把运算改写成矩阵乘法的情况下，改善尤为显著。
2. 在不少情况下，for-loop本身已经不构成太大问题，尤其是当循环体本身需要较多的计算的时候。这个时候，改善概率的关键在于改善循环体本身而不是去掉for-loop。
3. MATLAB的函数调用过程（非built-in function）有显著开销，因此，在效率要求较高的代码中，应该尽可能采用扁平的调用结构，也就是在保持代码清晰和可维护的情况下，尽量直接写表达式和利用built-in function，避免不必要的自定义函数调用过程。在次数很多的循环体内（包括在cellfun, arrayfun等实际上蕴含循环的函数）形成长调用链，会带来很大的开销。
4. 在调用函数时，首选built-in function，然后是普通的m-file函数，然后才是function handle或者anonymous function。在使用function handle或者anonymous function作为参数传递时，如果该函数被调用多次，最好先用一个变量接住，再传入该变量。这样，可以有效避免重复的解析过程。
5. 在可能的情况下，使用numeric array或者struct array，它们的效率大幅度高于cell array（几十倍甚至更多）。对于struct，尽可能使用普通的域（字段，field）访问方式，在非效率关键，执行次数较少，而灵活性要求较高的代码中，可以考虑使用动态名称的域访问。
6. 虽然object-oriented从软件工程的角度更为优胜，而且object的使用很多时候很方便，但是MATLAB目前对于OO的实现效率很低，在效率关键的代码中应该慎用objects。
7. 如果需要设计类，应该尽可能采用普通的property，而避免灵活但是效率很低的dependent property。如非确实必要，避免重载subsref和subsasgn函数，因为这会全面接管对于object的接口调用，往往会带来非常巨大的开销（成千上万倍的减慢），甚至使得本来几乎不是问题的代码成为性能瓶颈。

考试周结束后，在MIT的第一学年落下帷幕了，接下来将是长达3个多月的长假。很多同学外出旅游，或者回家度假。而我将留在校园，继续我的research。

经过了一个学年的努力，最重要的目标终于达成了：通过TQE。

在MIT的研究生在学位答辩之前需要经过两次qualify，分别叫TQE(Technical Qualification Exam)和RQE(Research Qualification Exam)，它们分别和课程与研究相关。每个系对于qualify有不同的policy，而对于Computer Science的学生来说，TQE并不是一次专门的考试，而是要求修四门主课，必须达到3A1B以上，才算通过TQE。为了保证足够的广度，系里把所开的全部主课分成三大领域（System, Theory, Artificial Intelligence)，它们各自又分为三个子领域（共9个）。学生可以自由选四门主课列入自己的TQE Plan，但是这四门课程要求属于四个不同子领域，并且必须覆盖三大领域。

在这个学年里，我修的四门课，分别是

• Machine Learning (AI)
• Advanced Algorithms (Theory)
• Advanced Computer Networks (System)
• Natural Language Processing (AI,  本来是想选Advanced Computer Vision的，无奈Freeman教授这个学期取消了这门课程，只得换一门了）

在昨天，成绩全部出来了，以4A通过了这些课程，终于长舒了一口气，这意味着TQE的圆满完成，在接下来的日子可以专心做research了。

坦率地说，MIT CS的课程并不是特别艰深，只要认真去学，在这里的中国学生拿A并不是很难的事情。但是，很多课程确实很重，需要付出大量的时间和精力。为了这些课程，我也放弃了这一学年的主要学术会议了。

MIT的课程在国际上享有盛誉，因为大部分课程是通过OCW(http://ocw.mit.edu)向全世界公开的，可能不少朋友都曾经接触过。不过，在网上看公开的课程资料，和真正参与到这些课程中，感觉还是不一样的。就我个人感觉来说，这里很多课程的课程质量确实是一流的。其实从高中开始，我就有逃课的习惯，直到后来在科大读本科，以及在香港中文大学读硕士的时候，都大量缺课（这不见得是好事，不要随意模仿，呵呵~~~）。主要原因是感觉老师上课的节奏和我的思维节奏不是特别吻合——我更喜欢到图书馆自己看书。在MIT，老师从不点名，但是，我却极少缺课（除了临时的情况，缺过几堂）——老师所讲的课还是有很大的吸引力的。而且每堂课容量很大，我很少觉得老师讲得太慢了，甚至有些地方还未必能当时跟上，需要课后仔细回味。

我所上的这些课程都没有教科书，Lecture Notes都是授课老师（也可能包括他们的学生）自己编写，Problem Set也是老师自己设计。上课的教授都是在学术研究中非常有成就的学者，他们中很多都在顶尖学术会议和期刊上发表了大量paper。上课的内容也贴近学术研究的前沿。其中Advanced Computer Networks这门课，每堂课程的内容几乎都是近年发表的两三篇SIGCOMM的paper（这些paper有一半是MIT发表的）。有一些老教授上课时喜欢说类似这样的话：“今天讲的这个理论是我的某某学生提出的，当年他也和你们一样修我这门课”。

老师们在讲述一个理论，一个方法的时候，很鼓励学生去发现它们的问题和局限。在很多作业和考试题中，都有要求评论某个方法的缺点的题目。比较有意思的是Natural Language Processing的课，这门课每隔两三周，会布置一篇文章回去阅读（通常是发表在Science等顶尖刊物的经典paper），然后要求写一份评论，既要求写正面的，也要求写反面的。为了完成这种任务，我们回去只能把这篇文章反来复去看很多遍去分析其中潜藏的谬误，比如某个理论可能暗含了一些假设，一个表面完美的实验可能隐藏了不公平的因素。然后，大家会带着这些思考到课堂上讨论。

这些锻炼的影响是潜移默化的。上个月审了一些ECCV paper，我发现这种影响被带到了审稿过程中去了。以前审稿会或多或少使用诸如“方法不新”，“实验不充分”这类放之四海皆准，却没什么信息量的理由来批判一些文章。而这次，这类理由一条都没有用，而是逐条抽出文章中的谬误加以剖析批评。这样的评论更为深刻有力，不过，这些paper的处境可能也堪忧了。。。

CS大部分课程都有一个大的course project，而且占评分比重很大（一般在40% - 50%）。所有的project都是非命题的，从选择topic，survey，理论，实验，到最后的paper(report)都是学生自主完成。在topic选择完成后，一般需要先提交一份proposal，老师会给与指导意见。对于每个project，我还是尽己所能做到最好，平均在每个project上投入的时间和精力，绝不亚于一篇CVPR/ICCV。 这些project最后都得到了不错的评价，至于老师们对于project的实际要求有多高，这个我就说不准了。

这一年的压力是很大的，因为，这几门课的成败关系到能否顺利拿到PhD。不过，上课的过程非常有收获，也得到了很大的锻炼。除了上课，还投入相当多的时间学习数学（主要涉及泛函分析，优化理论，现代统计学，测度理论，平滑流行理论，李群论等，有一些是复习巩固，一些是新学），让自己的基础更加扎实。Research的过程拖得比较慢，但也有了一些重要的进展。

在香港的时候发了一些paper，觉得自己走在了领域的前端。而这一年让我重新变成一个学生：我还有很多东西不懂，需要继续学习。

这篇文章谈到的话题——编辑器，和学术没有直接联系，可是却影响着我们每天的工作效率。我们平常使用电脑的过程中，至少有三类软件是必不可少的：操作系统，网络浏览器，以及编辑器。

网上的很多技术论坛充斥的着这样的争论：Windows vs. Linux，或者IE vs. Firefox。可是，这些争论虽然炽热，但其历史久远的程度却无法和下面的这个争辩相提并论：Vi/Vim vs. Emacs。熟悉Unix/Linux的朋友都知道它们的鼎鼎大名，这两款编辑器都诞生于1976年，其作者也分别是计算机界举足轻重的人物，Bill Joy (Sun的共同创始人和首席科学家），和Richard Stallman (GNU的创立者和自由软件的教父)。这两种编辑器代表了不同的设计哲学，自其诞生起，关于它们孰优孰劣的争论便无日无之，伴随着它们的成长，直到现在。在Wiki上有专门一个词条，叫做"Editor War"，它描述了这场延续了超过30年依然没有尽头的“战争”。

在这篇文章中，我无意介入这场争论，而是以一个使用者的角度，回顾在我成长的不同阶段所观察到的各种编辑器的变迁。

遥远的Dos时代：WPS & CCED & Turbo IDE

在1994年的时候，我刚上初中，家里给我买了第一台电脑——那是一台486，使用MS-Dos 6.22 + Windows 3.1。虽然，Windows在那时已经初具规模，但是由于历史的原因，当时Dos下的软件远比Windows下面的丰富，因此大部分工作还是在Dos完成。

当时在国内，大家流行的是学习中文打字——尤其是五笔字型，由于相比于当时智能化程度还很低的拼音具有无可比拟的录入速度，广受青睐。国外的编辑器对于中文一般支持不好，而且不符合中国人的使用方式，使用的人不多。当时主流的文字处理方式是用WPS处理一般的文章，用CCED编撰表格。国内很多文章都是用20行20列的原稿纸撰写——一个方格一个字。这种排版方式只有WPS独家支持，而用Word实现非常困难而且使用不便。

一点题外话，这两款软件的作者，求伯君和朱崇君，是国内早期程序员的杰出代表。当时有一篇广为流传的报道——求伯君卖屋做软件，它让求伯君以及他创立的金山公司成为国产软件事业旗帜。除了WPS，新一代的电脑用户更加熟悉的金山词霸也是金山的作品。平心而论，WPS还是一款非常优秀的软件，也符合国内大部分用户的需要的。由于和微软商业竞争上的失策以及盗版的侵蚀，WPS跌下王座，辉煌不再，令人惋惜。

而程序的撰写，主要使用每种语言自己的IDE，比如Quick Basic, Turbo Pascal, Turbo C/C++，都有自己专用的集成编辑环境。这些软件一张1.44M的软盘就能装下，虽然功能远不如现在用DVD才能装下的Visual Studio，不过其设计确实非常经典，使用也很方便。

在那个时候Turbo Pascal/C的出品人Borland公司是程序设计领域的领袖。可是到了Windows时代，除了Delphi的短暂风行，已经根本无力和Visual Studio抗衡，在一系列战略失误之后，最近把它的程序设计软件事业（旗下的CodeGear公司），以两千多万美元的低价贱卖给一个别的公司。（两千多万美元，对于一般人来说听着很多，但是相比现在的IT业动辄十亿百亿的交易来说，这实在是惨淡得令人伤心。）除了Borland高层在战略上的把握连连失误之外，Borland的顶尖人才大量流失也是其失败的重要原因，连Turbo Pascal和Delphi的首席架构师，也在1996年被微软挖走，为微软开发了一种非常优秀的语言C#。

Windows时代：Microsoft独领风骚

在90年代中期开始，Word开始大量进入国内用户的视野，并且逐步取代了WPS，占据了文字处理的垄断地位。我最早使用Word，是在Word 5.0/6.0版的时候，当时相应的Office版本是4.3。到了Windows 95之后，办公套件的版本开始改用年代表示，到现在已经更新了多个版本：Office 95, 97, 2000, 2003, 2007。

Word 6.0给我的最印象深刻的体验就是所见即所得(WYSIWYG)——字体段落风格直接就显示在工作区里，虽然现在看来这是理所当然，这在当时可是个新概念，WPS等当时还是主流的软件都还不能实现这点，主要还是依靠特殊控制符来表达排版。当时，Office对我有着非常大的吸引力，包括Word/Excel/PowerPoint/Access，每个新版本出来都要详细学习一番。我家里的书柜中还摆放了不少这些软件的教程——不过已经很久没看了，它们是那个时代的印记。

不过，Word功能再强大，也是不能拿来写程序的。在Windows时代的程序开发，经历了短暂的战国时代后，由Microsoft的Visual Studio一统天下。在Windows刚出来的时候，那是一团混乱。习惯了Dos编程的程序员们完全不知道怎么在Windows下面写程序。仓卒之间，开发商就把Dos下的那些开发软件改改拿去出Windows下面的版本：比如Borland C++ 4.0/5.0和Microsoft C 7.0。由于这些东西本身不是为windows写的，用它们开发windows程序困难很多，而且很不稳定。混乱期结束后，真正的windows开发工具出来了，最著名的是Borland Delphi/C++ Builder和Microsoft Visual Studio(包括被广为使用的VC6和VB6)。

Borland和Microsoft的产品一度势均力敌，相持不下。随着它的一些顶尖设计师，包括Anders Hejlsberg被挖到微软，Visual Studio有了长足进步，对于Borland的产品有着越来越明显的优势。Microsoft依赖其强势的市场地位，开始推广.Net，并且推出了C#——这是Anders Hejlsberg领导下的一款力作，在很多方面都是非常优秀的。这时候Borland开始手足无措，左右摇摆，一时要搞Borland.Net来迎合新的趋势，却无法抗衡微软的先天优势，一时又要搞Kylix支持跨平台开发，却发现Linux市场太小无法养活自己，而且那里是开源的天下，商业软件不是那么受欢迎，Mac更是Apple的封闭王国，水泼不进。在进退失据之中逐步失去市场。

在很长一段时间，从高中开始，直到到去MIT之前，我一直是用Visual Studio作为自己的主要开发工具，经历了它从第一代版本VS97, VS6.0, VS.Net 2002, VS.Net 2003直到VS.Net 2005。功能强大而又体贴，是一款值得信赖的软件。我个人不是热别喜欢VS 6.0（虽然到了今天，它依然有大量的人在使用），主要是它对于ISO C++的标准支持得不是特别好，对于很多高级的模板用法编译上存在问题。但是，到了VS2003/2005，这些问题不复存在了。而对于C#的喜爱，也加深了我对于Visual Studio.Net的依赖。

专业领域：向文本回归

Windows是视觉的盛宴，所有的软件都热衷于“所见即所得”的方式——也给用户种下了“所见即所得”是理所当然的印象。在这种方式下，编辑成为了输入文字，以及通过大量的鼠标操作(interaction)来选择和调节样式的工作。Interactive的工作方式，简单，直观，对于普通用户来说确实是最好的。但是对于一些专业要求比较高的工作未必尽然。

从计算机科学的角度看来，它最大的问题在于内容和排版样式紧密耦合。这使得贯彻排版的一致性变得非常困难，基本需要每篇文章逐句逐段的调节。当需要更换排版方式的时候，整个耗时费力的排版过程需要重新进行。Word的样式表在部分解决了这个问题，但是，大量的细调依旧不可避免。

在很多专门领域，要求同一内容方便施加不同的排版方式（学术会议稿件），或者要求排版方式一致地贯彻在大量的文件之中（比如系统性的产生大批帮助文件）。这就需要内容和排版分离来大幅度提高效率——因为它要求内容和排版分离的编辑方式，而不是“所见即所得”的耦合方式。

首先是Latex。这是学术论文撰写的重要方式。它是以纯文本形式编写，以特殊指令，比如\section, \table, \equation等等来标示不同的内容，并通过style file来贯彻最后的排版样式。相比于Word，Latex产生的学术文档一般具有更高的排版质量。公式输入也更为方便（在熟练掌握主要的数学符号输入的情况下）。不过，坦白地说，虽然相比于Word，Latex对于内容和样式有更大程度的的分离，但是，样式还是在一定程度上耦合在所编辑的文本中，比如figure的位置和大小调节，以及\textbf, \emph这些直接写在文中而非style file中的指令。

Latex这样的编译式文字处理形式（以文本编辑源文件，并通过编译生成排版后的结果），还有着另外一个优点，便于自动产生。对于有大量图表的文章，我常用的一种方式就是写一个脚本把实验结果直接生成Latex图表，从而节省手工录入的过程，既提高了效率，又减少了错误。

真正的和排版无关的表达形式是XML，它单纯地放置内容，并且通过XSL(XML Stylesheet Language)来描述内容的表现方式。这种方式被大量运用于自动化的网页和文档的生成过程。我曾经在MATLAB Exchange发表过的一些Toolbox，后来就采用了这种方式大批生成帮助页。

http://web.mit.edu/dhlin/www/softwares/dmtoolbox_doc/helps/mdoc.dmtoolbox.mdir.xml

http://web.mit.edu/dhlin/www/softwares/sltoolbox_doc/helps/mdoc.sltoolbox.mdir.xml

大家可以到上面这个网址看看效果（index页面有时传输略缓慢）。主要是，撰写一些脚本从matlab源码的头注释中自动提取帮助内容，产生XML文件，并且通过XSL来定义表现形式。

文本如何产生呢？一种就是上述的用程序批量生成，还有很多还是要文本编辑器来编辑。在Windows里面，文本编辑基本上是百花齐放的局面。没有一种编辑器占垄断地位，我个人用得比较多的是UltraEdit，有时也用EditPlus和NotePad++。一般来说，一些专门格式的文件都用专门的编辑器编写，比如Latex，常用WinEdt或者LatexEditor；XML则用XML Spy，HTML主要用Visual Studio或者DreamWeaver。

在MIT的工作：文本编辑的世界

到了MIT——这是自由软件的大本营，工作方式进一步受到身边环境的同化，全面向Linux转移，这一年里Linux基本就是我的工作环境。（不要误解，这里从来不强迫大家使用什么操作系统，很多人还是坚持用windows的，呵呵，不过如果在公开邮件中宣传Windows可能会惹来Richard Stallman的责难）

在这里，我用Latex写作业，报告和paper，用Latex-Beamer来编写presentation（不再用ppt了），也和使用多年的Visual Studio说再见了。现在，软件的编译构建通过自行撰写MakeFile来完成。这是一种全新的体验——就是你能在这个过程中全面了解和控制每个过程运作的细节——这一切都是自己编写指令完成，而不再是隐藏在按钮后面的神秘过程。你可以非常自由而灵活地把握和定制流程的走向。

看上去有点麻烦，不过磨刀不误砍柴功，通过一个设计良好的脚本（这在一开始可能需要花点时间），可以把大量过程自动化（而使用传统工作方式，可能需要很多次操作），从而很大程度上提高工作效率，而且能很好保证过程的一致性和正确性。

这一次，都只是围绕着一个核心——编辑文本（无论是Latex source, Makefile, Bash script还是Program source code都是以文本形式存在的）。和Windows一样，Linux也有着无数的编辑器，但是有两种是长期占据优势地位的，就是文章一开始提到的Vi/Vim和Emacs。

在Windows里面，编辑器是普通的工具，在Linux里面，在相当程度上，这两种编辑器各自代表着一种文化潮流，其地位不是Windows那些编辑器可以相提并论的。Emacs诞生于MIT，Vi/Vim起源于Berkeley，在我身边的人中使用Emacs的占多数。这是一种强大得令人难以置信的编辑系统。它的使用说明长达561页，这仅仅是使用说明。还有一本长达300多页的说明，告诉你怎么用Emacs LISP来配置这个编辑器。

Emacs被很多人认为就是一个完备的“操作系统”。在这个编辑器里面，你除了编写各种格式的文件之外，可以构建和运行程序，收发邮件，以文本方式浏览网页（它以一种很聪明的方式把网页的内容以比较友好的文本方式呈现给你），还可以玩游戏，和煮咖啡（这个功能对于我来说暂时属于传说）。在某些自由软件社区，Emacs是一种信仰和生活方式，通过经过精心配置的Emacs，你基本上可以不离开它完成几乎全部工作（Hmm, 拿它来打3D游戏似乎还不现实，但是俄罗斯方块之类的是绰绰有余了，呵呵）。

我对于Emacs还没有那么忠诚，不过它在过去的这个学年确实是我的主要编辑工具，我用它完成了我全部的course project——它被用来撰写C/C++, Python, Java, 和Latex。但是，MATLAB还是用matlab自带的editor来写——值得一提的是MATLAB的editor有一种Emacs模式。

Emacs其实是一个非常灵活的软件，对非常核心的部件都可以全面定制，而远不仅仅是key mapping, color scheme等表面的东西。对它的配置，使用一种专门为它设计的语言，叫做Emacs LISP，这是一种基于LISP的专用语言。但学习起来，可能不那么容易。Emacs的配置过程颇为繁琐，它主要通过.emacs文件配置，大家可以在网上看看那些被分享的.emacs配置文件，基本都在数百行以上。也就是说，在让你的Emacs编辑器完全符合你的心意之前，需要编写一个几百行的配置脚本。当然，你用默认的配置也可以，不过在某些格式的文件的编写中没有那么好使。我在第一次使用前，花了整整三天才把它配得比较顺手了。当然了，第一次配好后，把.emacs存下来，以后就省心了——即使重装系统，把那个.emacs拷贝过来就行。

Emacs给人的感觉是有点过于重量级了，即使在一台配备Quadcore(3G Xeon x 4) + 8G Ram的工作站上，打开大部分插件时，还是有时感到一点delay。不要小看这一点delay，在代码编辑的过程中，在效率上会带来不可忽略的开销，（想想击键时需要等待0.2秒的感觉)。后来，始终觉得Emacs不太适合进行轻量级的编辑，于是转向Vim。

Vim也是一种非常优秀和强大的编辑器，编辑效率比Emacs更高。Emacs通过Ctrl, Alt, Shift这些辅助组合键来触发各种功能。而Vim则采用模式方式，它有多种mode。在Insert mode里面，就像普通编辑器那样，比如输入dd，就是敲进去两个字符dd；而在normal mode里面，dd就是删除当前行。它在编辑命令上下了很多的功夫，编辑功能特别强大。比如单是删除就有非常多的方式，dw 删除一个单词，d3w 删除三个单词，d4j 删除接下来三行，d5k 删除前面五行， dG 删除到文章末尾，d$删除到行尾，dft删除到下一个出现的字母t，d'a删除到下个书签为a的地方。。。。。。还有其它非常多样的编辑方式。这使得很多以前需要敲很多键才能完成的功能，在几个键内迅速实现。不过Vim的学习曲线比较陡峭，上手比较难，需要反复大量联系才能熟练，很多人看着几个模式来回切换就晕，更不用说用说那些千变万化的命令组合。不过经过一段时间的坚持练习，后面的编辑速度可以成倍提高，非一般编辑器能比。

相比于Emacs, Vim相对较轻（虽然也在变得臃肿之中），而且很多必要的部件本身就配置得不错，人工配置的工作量比较少。它也有一门专门的语言来配置，叫做Vim Script，新版的Vim也可以用python来配置了。对于我自己使用感觉来说，它的Line Number Display和Omni Completion是相比于Emacs更出色的亮点，而且编辑上感觉不到延时，也不需要老是把手指伸到Ctrl, Alt这种地方去了。

文本编辑是计算机一个很基础的用处，以至于我们常常忽略它。不过，当你深入到它的世界，却可以发现它独特的魅力。

随着最后一个project的完成，第一学年结束了。

这不是一个值得庆祝的时刻——当数万无价的生命无可挽回，当无数的同胞仍在失去亲人的痛苦之中，举国同哀的时候。

对于中华民族来说，2008年是不平凡的一年，我们共同经历了最严峻的挑战。在过去的半年里，我从未如此强烈地感觉到自己对于这片养育了自己的土地的血浓于水的情感。即使到了期末最紧张的时候，依然长时间地看着一篇篇或令人沉重，或令人感动的报道而不能自拔。

身在他乡，方知故乡情重。

虽然无法提供更多的帮助，在这里的大家还是尽了努力，向灾区的人民表达了自己的心意——虽处万里之遥，我们感同身受。

此时此刻，最想要表达的，就是对遇难同胞最深的哀悼。

愿，逝者安息，生者平安。

MATLAB是一门在数值运算方面非常高效的语言，对于提高MATLAB的效率，有一些大家熟知的方法，比如避免使用for循环，向量化，使用C-mex写核心，等等。这些原则大体是没错的，但是教条地运用有时反而会降低效率。

根据问题的规模，适当选择向量化的策略

向量化的基本思想是以空间换时间，通过把要处理的对象转化成一个矩阵，集中处理。这比起非向量化的处理方式往往需要消耗更多的内存。在内存紧张的时候，内存分配的开销可能是很大的。

比如，给定一个列向量v1，和一个行向量v2, 计算矩阵M，使得M(i, j) = v1(i) + v2(j)。一种常用的向量化实现：

m = length(v1); 
n = length(v2);
M = repmat(v1, [1, n]) + repmat(v2, [m, 1]);

这个过程中，除了M以外，还要创建两个大小为m x n的临时矩阵。repmat创建临时矩阵有一定的overhead，主要花费在元素索引上。由于元素加法的向量化收益本身并不显著，扣除repmat的额外开销后，得益就更小了。另外，当这些矩阵很大，接近物理内存容纳能力的时候，必然导致和虚拟内存进行频繁的交换，耗费大量的IO时间，向量化可能得不偿失。这种情况下，下面这种向量化程度略低的方式可能是更好的选择：

M = zeros(m, n);
if m < n
    for i = 1 : m
        M(i, :) = v1(i) + v2;
    end
else
    for i = 1 : n
        M(:, i) = v1 + v2(i);
    end
end

这个例子是要说明在设计向量化的时候，要对其它潜在的影响因素也进行考虑，权衡得失。对于这个例子本身，在2007版以后的matlab，有一个通用的简洁的写法。

M = bsxfun(@plus, v1, v2);

MATLAB内部对于bsxfun有很专业的优化，这个写法在时间和空间上都比较节省。

对一组d x d矩阵求逆，假设这些矩阵放在大小为d x d x n的数组里。在一般条件下，多个矩阵求逆没有特别的向量化方法，通常就是逐个求

n = size(A, 3);
B = zeros(size(A));
for i = 1 : n
    B(:, :, i) = inv(A(:, :, i));
end

不过，当d很小而n很大的时候，比如对大量2x2矩阵求逆（这在设计几何的问题中很常见），那么直接利用2x2矩阵的求逆共识，进行向量化了：

a = reshape(A(1, 1, :), [1, n]);
b = reshape(A(1, 2, :), [1, n]);
c = reshape(A(2, 1, :), [1, n]);
d = reshape(A(2, 2, :), [1, n]);

g = 1 ./ (a .* d - b .* c);
r11 = d .* g;
r12 = -b .* g;
r21 = -c .* g;
r22 = a .* g;

B = reshape([r11; r21; r12; r22], [2, 2, n]); 

在正式的代码中，还需要处理可能为奇异(a*d-b*c=0)的情况。

某些非数值计算问题的向量化

有些问题，表面上不像是数值计算，但是通过适当的转化，也可以通过向量化解决。

非等量复制: 比如有一组数[10, 20, 30], 各自要复制成[3, 2, 5]份，最终产生出 [10 10 10 20 20 30 30 30 30 30]。这个问题，虽然简单，但是因为不是那么“整齐”，因此向量化不是特别直接。下面给出一种思路：

首先产生出起始位置标志向量[1 0 0 1 0 1 0 0 0 0]，然后通过cumsum，产生出[1 1 1 2 2 3 3 3 3 3]，最后以此为索引，可以得到结果。

% vs: the values to be copied
% ns: the numbers of copies 

vs = vs(ns > 0);
ns = ns(ns > 0);

sp = [1, cumsum(ns(1:end-1)) + 1];
result = vs(cumsum(sp));

对于图像处理或者二维信号问题，善用filter。

比如，要对每个像素，基于其局部邻域进行一些计算。即使整个计算本身不是线性的，但是只要能分解成线性局部运算的组合，就可以利用filter。

比如，对于图像I, 产生V，使得V(i, j)是像素I(i, j)周围w x w邻域的像素的方差。

I = im2double(I);
h = ones(w, w) / (w * w);
M = imfilter(I, h, 'symmetric');
M2 = imfilter(I.^2, h, 'symmetric');
V = M2 - M.^2;

题目中所说到的四个词语，都是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的工作。许多有重要贡献的工作，往往未必有很炫的方法和模型，但是，其对于问题本身的深入发掘和洞察却令我惭愧。

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

最近做course project的时候，我发现所写的程序中有几个地方特别能反映MATLAB与别的高级语言很不一样的风格。

例1：一批user去访问文件，比如u1访问了f11, f12, ..., u2访问了f21, f22, ...，每个用户访问的文件数目可能不等，要求输出一个表M, M(i, j)是用户 i 和 j 都访问过的文件的个数。

先用高级语言给出一个比较直接的解决吧，下面是python的代码。（其实C++/C#/Java的也类似，不过python的代码比较简洁）

首先，建立一个访问字典（或者叫map)，记录每个文件都被哪些人访问过。

# input is a map named ufiles, 
# ufiles[u] is a set of files accessed by u

acc_dict = {}
for u in users:
    for f in ufiles[u]:
        if f in acc_dict:
            acc_dict[f].add(u)  # add u to an existing set
        else:
            acc_dict[f] = set([u])  # initialize the set

然后，基于这个字典进行计数。对每一个文件，给每一对访问过它的用户的相应计数加1

# initialize the table
M = {}
for u1 in users:
    for u2 in users:
        M[(u1, u2)] = 0

# do counting
for f in acc_dict:
    uset = acc_dict[f]
    for u1 in uset:
        for u2 in uset:
            M[(u1, u2)] += 1

这样就基本完成计数了。

MATLAB没有像python那样丰富的数据结构，比如set(集合)和dict(映射表，字典)。但是，在这个表面上需要依靠经典数据结构完成的问题，我们可以用MATLAB给出一个更加高效简洁的解决方法

给出代码之前，先做点数学分析。令F是一个矩阵，F(u, f) = 1代表u访问过这个文件，否则F(u, f) = 0。那么M其实就可以写成：

M(u1, u2) = sum_f F(u1, f) F(u2, f) --- 很容易看出，这就是u1, u2都访问过的文件的数目。

M = F * F'

下面的代码就很顺理成章了

% Input: ufiles is a cell array of indices of files accessed by each user
% ufiles(i) is a row vector of the indices accessed by user i

% construct F 
n = length(ufiles)
% to produce usrs like {[1 1 1 1 ...], [2 2 2 ...], ...}
usrs = arrayfun(@(i) i * ones(1, length(ufiles{i})), 1:n, ...
                'UniformOutput', false)

I = [usrs{:}]  % concatenate the indices into one long vector
J = [ufiles{:}]
F = sparse(I, J, 1);

% compute M 
M = F * F'

注意这里用sparse matrix, 那么运算复杂度会显著降低，并且只依赖于实际访问的数量。实际性能上，通过MATLAB的稀疏矩阵乘法比自己用高级语言实现更快。

熟悉kernel的朋友可能已经看出来，MATLAB的做法其实是用file access indicator vector作为每个user的feature，构造出来的M则是相应的Gram matrix。不过，如果没有这方面的思维习惯的话，未必能很快就把一个统计文件访问量的问题联想到矩阵乘法或者内积计算。

例2：给出一组数字，算出每个不同数字出现的次数。

python的实现

counts = {}
for v in values:
    if v in counts:
        counts[v] += 1
    else:
        counts[v] = 1

Matlab的实现

svalues = sort(values);
dp = find(diff(svalues));
sp = [1, dp+1];
ep = [dp, length(svalues)];
U = svalues(sp);   % U is the set of distinct values
C = ep - sp + 1;   % C is the corresponding counts of these values

一般情况下，两种实现的时间复杂度都是O(n log(n))。不过，它们体现了不太一样的思维方式。高级语言倾向于通过数据结构加速每个元素的处理，而MATLAB没有复杂的数据结构，它注重于以整体方式进行操作。

这几个星期一直忙着作业和考试，这里有些天没有更新了。刚过了mid-term，回到这里和朋友们说说话。

今年3月，Mathworks推出了MATLAB一个重要的新版本，MATLAB 2008a，也叫做MATLAB 7.6。在这个版本里，MATLAB解决了几个长期以来固有的弊端，而且加入了一些重要的能力。这次的更新是非常aggressive的，可能代表了MATLAB的一种历史性的转型。

1. 完全实现面向对象编程。其实，在MATLAB的早期版本里面，也有class的概念，不过大家如果使用过的话，可能知道那是一种不太好的设计。功能不强，过程繁琐，而且，很多很tricky的地方，尤其是重载numel, subsref这类函数的时候。而新的设计抛开了历史包袱，现在写出来的类和在python里面写的长得差不多，舒服多了。这套设计，吸取（或者“抄袭”）了Python和C#的优点，除了支持封装(encapsulation)，继承(inheritance)，和多态(polymorphism)这些基本特性以外，还支持了一些新兴的特性，包括属性(property)，事件(event)，和静态方法(static method)。
2. 支持Handle类型——用另外一种说法，就是支持函数调用传引用。以前matlab传递参数只有一种方法，copy on write。就是说，当你传一个东西进去，如果它要发生改变，那么，这个东西会整个copy一份，然后修改会在副本上生效。这使得实现动态数据结构变得非常困难。比如一个列表，如果每添加一个元素，都要拷贝整个列表一次，将是什么效果呢？因此，传统上matlab擅长于以矩阵为基础的算法，但是对于以经典动态数据结构为基础的算法，比如动态列表，哈希表，搜索树，图等，就力不从心了。这个新版本终于引入了对引用的支持，这将使MATLAB实现经典数据结构和算法变得前所未有的轻松。现在，数值和统计算法与经典算法越来越多地合流，很多应用都需要同时使用两方面的算法，MATLAB的这个变化正好适应了这种需求。
3. 引入了名空间的管理。以前，MATLAB所有的函数都在同一个global的名空间下面。比如两个工具包里面出现了同名函数，解决起来很麻烦。比如现在有两个算法叫LDA，一个是Latent Dirichlet Allocation，一个是Linear Discriminant Analysis，在一个应用中需要同时用到两个算法，而写这两个算法的人各自把它们命名为lda.m，那么问题就出来了。一种naive的方法是改名字，不过会直接破坏掉那些toolbox里面对那个函数的依赖。而这个版本，它借鉴其它高级语言的经验，终于引入了namespace，给这个问题一个很好的解决。

从这些特点看来，MATLAB这个版本的重要改变，就是全面吸收其它高级语言的特性，从一个数值运算语言开始迈向一个以数值计算为强项的通用语言，以应对复杂或者更大规模应用的需要。

一直以来，由于matlab缺乏处理高级数据结构和建立复杂应用的能力，它有一个有力的竞争者numpy，这是python里面进行矩阵和数值运算的包，它建基于python这种著名的通用语言，并且提供matlab矩阵的部分能力。这次MATLAB的全面升级，对于numpy无疑提出了严峻的挑战。

除了程序设计结构方面的变化，MATLAB 2008在多个方面也有重要进步。

1. 它的优化工具箱(optimization toolbox)首次引进了interior point algorithm。interior point algorithm在convex optimization中占有重要地位，并且性能优越。MATLAB optimization toolbox一直以为因为使用老式算法，性能太差，而饱受诟病。这次终于引入interior point，希望它的优化性能能得到显著改善。
2. 重写核心JIT引擎（运行时编译，可以显著提高运行效率），并且采用了最新的BLAS/Lapack核心，运算速度会有相当程度的提高。另外，还大幅度提高了对sparse matrix的计算速度。
3. 它的统计工具箱增强了对很多著名的统计算法的有力支持，比如HMM, GMM，还有NMF（Nonnegative Matrix Factorization)，并且开始引入对蒙特卡罗采样的支持。

MATLAB 2008刚刚发行，现在学校内部还没开始支持。不过，这个版本确实非常值得期待。

这两周经历了这个学期第一个忙碌的高峰。

这里的课业本来就很繁重，而且，很多时候并不均衡。最近，两门课程“不约而同”地把整个学期30%以上的作业量集中到了两个星期——我不记得这两周除了完成各种接续不断的assignment，还做过什么。

学计算机的人都知道循环语句，可是，如果这些人做TA，并且在布置作业的时候使用for循环，那是什么一种情况呢？最近一次作业的一道大题，竟然使用三重循环来布置，实在令人佩服。题目大概是长成这个样子：

1. (a).  (a.1) xxxx, (a.2), xxxx, .... (a.n) xxxx, (a.(n+1)) change some condition, please repeat from (a.1) to (a.n) ...... (b) ..... (c) ..... (d) ........ (e) with a new setting, please repeat (a) to (d) ..... 2 ..... 3 ..... 4 ...... 5 in a new method, please repeat 1 to 4.

除了两门课的作业和实验，还需要完成Network的research proposal。这里的课程project都有一个特点，全部都是不命题的。学生需要自己完成，从survey, proposal, formulation, experiment, 到最后的report的全过程。Network这门课的老师特别强调，project必须探索这个领域的研究前沿，最后的report必须写成可以发表的paper的形式，中间有一次中期检查，最后还有一次答辩。他不只一次的告诉我们，每年都有相当数量的project paper成功发表到top conference上——这应该是他对我们的一种期待——这对于这门课的学生，尤其是不在这个领域的，确实是极具挑战性的。

CS的决策人确实是用心良苦——要求每个学生修的课必须覆盖3大领域(system, theory, AI)，而在大部分的课程中，教授都要求学生完成一个从选题到最后报告的完整的课题研究过程。虽然非常辛苦，但是，学生确实可以获得在计算机科学的各大领域开展研究的经验。另外一方面，几年前CS把所属的全部实验室合并成CSAIL——常年有800人工作的超大型实验室，鼓励各个研究小组相互交流。强制性的跨领域修课政策加上大实验室制，使得CSAIL内部的交叉研究特别活跃。很多研究课题都是“杂交”的。每个老师管着不同领域的课题，每个学生参与不同小组的meeting，已经司空见惯。在某些具体的领域，CSAIL的研究未必是最好的，但是，这里确实是世界上交叉学科发展最为蓬勃的地方。

今天作业的一部分，是以Science的reviewer的身份去review一篇文章，并攥写review报告。

这篇文章是已经在1996年发表于Science上，标题非常有趣：

Statistical Learning by 8-Month-Old Infants

大家可以非常容易在google上找到这篇文章的全文。

文章指出一个一个很值得思考的心理学实验结果：一个很小的婴儿，只需要听上两分钟的连续语音，就能形成对以后听到的连续语音进行有效分词的能力。

这篇文章阐述的是在语言学习方面的结果，而事实上，在所有智能领域，我们都可以看到类似的观察。比如在Vision，人们都没有经过系统的可控的物体识别训练，但是却非常容易获得在复杂的世界上对对象进行迅速的分割，识别，以及获取其它方面信息的能力，而目前computer vision的能力在最简单的可控实验中依旧举步维艰。

人类只需要很少的训练的情况下能够迅速获得非常灵活有效的“模型”去应对充满变化和干扰的实际输入，而计算机学习算法通过在大量样本训练，也很难接近哪怕是婴儿的水平呢？ 人类的学习机制和目前人工智能研究所采用的方式究竟有什么不同？

现在统计学习领域百花齐放，但是，大部分的方法，无论formulation有多大的数学上的差别，基本上都是让一个具有某种结构的model按照某种准则去"fit"训练数据，通常还加上某种复杂性的约束。不过，很难想像人类是使用类似的方法从现实中学习的。我们每天感受到的是一个不断变化，各种要素充分融合的世界，没有分离的“训练数据”去学。我们的大脑能够理解非常复杂的东西，但是我们所接触的“训练集”按照经典统计学系理论的观点是无法支持这种复杂性的。虽然，我们经常会犯被观察所误导的错误，但是，相比于机器学习算法，我们overfitting的机会和程度远小得多。

我相信，我们的学习过程远比目前所有的机器学习算法聪明得多，绝不仅仅是observed->fitting这样的统计形式。AI的主要领域的研究现在过分依赖于统计建模，可是统计有它固有的瓶颈。早在Vapnik他们建立统计学习基础的时代，已经明确告诉了大家，统计学习受到复杂性的根本制约。因此，统计学习本身并没有足够能力到达人工智能的目标。相对于人类真正的智能来说，统计所能产生的智能只能认为是一种非常初级的形式。

从rule-based的专家系统到神经网络，再到统计学习，AI几十年内经历了几次大规模方法论更新的浪潮，但是是不是离真正的智能越来越近了呢？我们究竟是不是走在一个正确的方向上？

CVPR 2008的审稿期刚刚结束了。今年，我对于所审的paper，采取了更加宽容的态度。

Vision依旧很热闹，但是，我感觉这个领域在喧嚣的背后似乎有点疲态了。年复一年，每年成百上千的paper仍旧是在那几个旧的舞台上唱着老调子。比如object recognition，无数打着"novel framework"旗号的车子，仍旧挤在local feature extractor + classifier (SVM/AdaBoost ...)的独木桥上，难道，这是唯一的方法么？

在没有看到有人开辟新的道路的时候，我更欣赏那些专注解决于一个具体的小问题，并且提出了有见地的方法的文章。对于那种表面华美的，而内里却仅仅是把A feature换成B feature，C model换成D model的，我一般评价很低。

这里的一位教授在谈到写paper的时候，提到了一种很多人都会犯的毛病。还是用object recognition的工作为例子，为了完成实验，你必须做大量的工作，把整个framework搭建起来，从data到feature到classifier，要写很多很多的code，花很多很多的时间去debug。为了对得起这些付出，很多人想把这些努力都写到paper上去，因此形成了很多并不新颖的工作每年都在投。而事实上，这些工作并不完全是没有新的东西，但是，那一点新的东西，在整个framework式的表述中被喧宾夺主了。

要写一篇有吸引力的文章，必须有取舍的决断。有些为了完成实验必须做的工作，你即使在上面付出了半年时间，但是如果缺乏真正的学术价值，在paper中应该尽量简省，把大部分的篇幅着力于那些真正的有意义的地方（哪怕那个地方其实你只花了3个小时想出来）。评paper不是评劳模（当然有些reviewer可能有这种倾向），不能把工作量的因素拿来布局paper的篇幅，不能把对某些工作“舍不得”的情绪带到paper的presentation当中。

CVPR审稿落幕了，我们的reading group又开始了。这个学期，John决定让大家自己轮流选paper，lead每个星期的reading。他说，除非有充分的理由，不要选近五年的文章。他上学期其实就是这样的风格，选的很多都是五六十年代的文章——信息论和统计学习的奠基者们那种seminal的经典著述。这些paper让我感慨前辈们的工作是多么有生命力，今天无数的主流算法仍旧发源于40年前的某篇文章，而且事实上没有走远多少。科技日新月异，其核心学理的进化则缓慢得多，艰难得多。

在paper里面通过比较几个近期工作来claim自己的东西是新的很容易，但是，要让一个工作放在这个学科的整个发展历史中去考量却依然有价值，则是非常艰难。这个学期，我开始要参加Alan的meeting, 他是MIT另外一个大实验室LIDS的director。有一次和Alan meeting的时候，大家提到一些最新发表的算法，他说，这些东西has been done 40 years ago。他人很nice，但是一项工作要得到他的认同很难。那次，我在他面前present了40分钟我的新工作，很多的东西都被他认为是在数学领域已经解决的（虽然vision里面没有出现这样的publication），不过庆幸的是，还是有一个point，被他指出I have never seen people working on this。后来两个星期，我在这个point上投入了很多时间去思考，发现这确实是一个很有价值的问题。

我在这里所接触的教授都很nice，平常对学生的工作也不干涉太多，但是对于一项工作的评价非常挑剔。John告诉我，要解决最困难的问题，容易解决的问题让别人做去。这半年来，脱离了CVPR的指挥棒，在沿着自己的道路一点一点的缓慢前进着，但是走的很踏实。刚来的时候，对MIT的氛围有点不太习惯，好像CVPR也好，NIPS也好，都没什么要紧的。现在才慢慢觉得，只有从conference的指挥棒中走出来，才能脱离浮躁，实实在在的进行有意义的探索。

两个星期后，将轮到我挑选reading group上讨论的paper。这么长时间大家都讨论的是信息论和统计方面的文章，我说，我要变一下，找vision的paper，John答应了，不过条件是paper必须是经得住考验的真正的好paper。我现在不知道哪篇能达到这个要求。

开学第一周，下岗了很长时间的闹钟又开始工作了。在上课和作业中，生活又恢复了忙碌。

这个学期选的一门Natural Language Processing，上课的风格还是让我觉得颇有创意。这门课每隔两周都要学生完成一篇类似GRE Issue这样的作文，就某个看上去有点深度的问题进行辩论。

在第一堂课，就布置了这样的讨论题：

比较统计模型和语法模型在自然语言建模中的优劣。

其实原题给出的是两个虚拟的Google员工的辩论，要求对其发表评论，上面这句话只是一个简要的归纳。题目中有一个很有意思的类比：

牛顿基于开普勒的天文观测数据归纳出万有引力定律。假设我们有充分多的天文数据，是不是可以直接Learn出一个统计模型，并且用它来predict行星在任何时间的运行位置和速度呢。

事实上，离开自然语言这样一个context，更广义上说，这里做的是让经验模型PK核心定律。

这里继续引申，可以到达一个听起来有点离经叛道的思考，前辈们在过去几百年间通过艰辛的努力和积累，建立起了以物理定律为基础的科学，

那么物理定律，能不能通过统计方法学出来呢？或者说，牛顿能不能被统计算法所取代呢。

我不是“统计万能”的支持者，但是，我相信，对这些问题的思考，有助于于理解统计方法的本质能力——它究竟能做什么，不能做什么。在过去的十几年里，统计学习在AI的众多领域里占据了主导地位。AI在继专家系统和神经网络之后，迎来了“统计时代”。但是，统计是不是就是建立真正意义的人工智能的钥匙呢？在享受统计方法给我们带来的一切好处的同时，也许，我们也许还需要一种批判的眼光去审视当今科学研究中的统计潮流。

上一次去纽约，已经是一年半前的事情了——参加2006年的CVPR。

昨天，我再次来到了纽约——因为要给Dylan当搬运工，同时也看看远道而来的小呆了，呵呵。

纽约是在很多人心中国际大都会的象征。但是，无论从哪个角度说，它都不属于那种人见人爱的城市。不同于东方的几个明星城市像香港和新加坡，纽约给我的第一印象就是既破又脏。

作为游客，我在纽约的主要交通工具是地铁——这里的地铁是世界上最古老的地铁之一，不过，也是我见过的最破烂的地铁。黑森森的地铁站里面站着，目无表情的人，从楼梯，站台，乃至铁轨上面到处都是垃圾和烟头——散发着令人不太愉悦的味道。很多地铁站内没有线路牌，地铁里面很多时候也是不报站的。不过，只要留心观察，要是有足够的素材让你判断火车到了哪个站了——虽然不是特别清晰显眼。

曼哈顿的主要区域都可以用“坐标”定位，主要的街和大道排成规则的纵横网格，都是用数字编号，使得在这个大城市里面找地方变得非常方便。曼哈顿岛上有大片的鳞次栉比的高楼群（从总数上超过香港的中环很多）。在美国的很多城市（包括Boston, San Diego乃至Houston）晚上都是颇为安静的，街上的商店很早就关门了。而纽约和这个国家的其它城市不同，到了晚上12点，主要的街道上依旧车水马龙，热闹非凡——就像香港的弥敦道。

三教九流的人共融在这个城市里。在这里，你经常可以看到豪华的加长林肯招摇过市，也可以看到在街边的衣衫褴褛的乞丐。在高耸入云的摩天大厦的下面就是遍地烟头的街道和破败不堪的地铁站。

纽约，不是一个花园城市，但却是一个充满魅力的城市——它的魅力源于它海纳百川的胸襟——藏龙卧虎和又藏污纳垢——鲜明的反差渗透在这个城市的每一个角落，构成了纽约最独特的性格。

新学期开始啦——寒假后，又要开始面对繁忙的课程了。

开学第一天，就和mentor meeting了——他非常满意，算是给这个学期开了个好头。这个学期的任务还是很重的，选了两门课

Computer Networks：选这门课，是因为系里要求学生在qualify前选择的课程必须横跨三个领域，在System领域，我们大家合计选这门了——因为考试的比重比较少。不过，这门课是research-oriented的，课程project要求很高。

The best projects are sure to be publishable (as they have in past years) in top ACM or IEEE conferences in the area, such as SIGCOMM, INFOCOM, or MOBICOM, or appear as articles in journals like SIGCOMM's Computer Communications Review (CCR). I have a strong feeling that you will far surpass my already high expectations with wonderful work that will further the state-of-the-art in network research.

看来有得忙活了。如果上三个月课作出来的project就能发到mobicom/sigcomm，我估计得考虑转行做网络了，哈哈。历史上是有这号牛人的，敬仰一把。

还有一门Natural Language and Computer Representation of Knowledges。这门本不是我要选的，只因为Computer Vision课被Freeman取消了，起码今年没有。不得不在AI领域另选一门。不过看了一些syllabus，内容还是很interesting的。

开拓视野，博纳众长，说不定对自己的research还有所启发。

最后，祝愿大家新春快乐！

随手翻开这期TechTalk, 在头版的大标题computer vision的字样赫然入目。第一次在TechTalk看到自己领域的文章，自然很感兴趣。

先介绍一下，TechTalk是MIT内部一份免费派发的报纸，每周一期，主要报道学校的各种科学研究的进展。一直以来，占据这份报纸头版的主要是生命科学，能源科学，或者新材料。

这篇文章的标题是 Computer vision may not be as good as thought

文章的作者来自 McGovern Institute of Brain Research @ MIT。

文章主要是针对近期在Object recognition所取得的“进展”而发的。它开篇就旗帜鲜明地提出：

The apparent success of object recognition may be misleading because the tests being used are inadvertently stacked in favor of computers.

在MIT McGovern Institute和Harvard Rowland Institute的一项联合研究中，他们认为，被广泛用于评价object recognition性能的Caltech 101 database并不能有效反映出算法在真实条件下的能力。文章指出，object recognition的核心困难源于一个物体在形成图像过程中，由于方向，位置，光照，外界环境等等的要素影响而发生的各种变化。而以Caltech 101为代表的主流测试库，在获取过程中实际上是隐含了有利于计算机辨别的因素，而不能真实反映客观世界的复杂变化，并且掩盖了实际问题的复杂性。

The ease with which we recognize visual objects belies the computational difficulty of this feat.

在他们的实验中，他们做了一个非常naive的算法作为baseline，该算法仅仅用到了一些非常初级的信息，而且没有进行特别处理和分析。他们原以为这个算法会fail，但是他们惊奇地发现，这个naive算法在Caltech 101上表现出色(surprisingly well)，其性能甚至超过了5个最新提出的state-of-the-art的算法。

从这样的实验结果中，他们对主流的算法评价体系提出了质疑

We suspected that the supposedly natural images in current computer vision tests do not really engage the central problem of variability.

为了验证他们的想法，他们设计了这样的实验，只使用飞机和车两类物体，但是，尽可能引入各种真实变化的条件。他们发现，那些在Caltech 101上面分多类分得很好的算法，在这里分两类都分得一蹋糊涂。这个团对得到这样的结论：

The model did well on the Caltech101 image set not because it is a good model but because the so-called 'natural' images in the test set fail to adequately capture real world variability.

他们提出，computer vision的研究人员应该抛弃现有的不科学的评价体系。

作为脑科学系的研究人员，他们研究object recognition的方法，主要是探索our brain's own solution，并且尽可能地去模仿它。他们认为，这是一个正确的方向。

小时候，老师就告诉我们，读书讲究先由薄而厚，再由厚而薄。前者是吸收和积累，后者是融会和消化。

这些年，读了不少关于统计学习的东西，很多东西都记不清楚了。从我自己的角度看来（可能是很肤浅的），学概率和统计，关键是记住三个概念：测度(measure)，期望(expectation)，和独立性(independence)。

测度是现代概率理论的基石。在经典的概率论里面——比如我们在本科学的那些——大多是通过举例子和文字说明的方式告诉你概率是什么，这容易明白，不过缺乏严密的公理化根基。现代概率论整个建立在测度理论的基础上，概率的定义非常简单，不过也很抽象——所谓“概率”，就是归一化的测度。没有测度，就没有整个概率论的大厦，所以它很重要——不过，它在实用中直接用上的机会不大，所以不是这篇文章的主体。关于独立性，以及它的一个孪生的名词：Markov，也扮演着非常重要的角色，它是Graphical models的基础。有兴趣的可以去读M. I. Jordan的书。

而在统计学习的实际应用中，就是你平时写code，用得最多的就是期望，或者一个通俗点的版本——平均值。其实这两者不太一样，期望是从model出发演绎的，平均值通常是指从data出发归纳的。不过它们的关系确实非常密切。

统计学习在很多情况下，就是求平均值

我们平常说去Learn一个model——其实，在很多情况下，这就是干一件听上去很简单的事情，求平均值。我们知道，我们所接触的大部分重要的概率分布，都属于exponential family，比如Gauss, Binomial, Multinomial, Dirichlet, Poisson, Exponential, Gamma等等分布都属于这个家族。它的一个重要特点就是——得期望者得天下。就是说，知道了某些统计量的期望，就知道了整个model，至于model的参数，或者就是期望本身（比如Gauss)，或者不难从期望中得到。可以证明，对于这些model，对它们的最大似然估计(Maximum Likelihood estimation)，就是从data中算出某些统计量的平均值作为model的期望。

在Bayes学习中，我们还考虑先验分布(prior)。在这里，model的估计还是求平均值。所谓prior是怎么来的？就是以前曾经观察过的data那里总结得到的，然后以prior的形式影响当前的model估计。一般而言，使用exponential family，我们通常会使用conjugate prior，这种prior，基本就是沿着刚才说的，假想我们已经看过一些data的思路得到的，它的形式和data mean几乎如出一辙。而带了prior的估计，还是在求平均值，不过这里的平均值就是（假想）以前观察过的数据和当前的数据合在一起求平均。

对于更加复杂的Graphical model，每个节点的estimate和update，很多时候，其实是做了这样的事情——把其它节点传来的平均值和这个节点接触的数据的平均值混合进行新的平均。从最简单的Gauss, 到更加复杂的Gaussian Mixture Model, Latent Dirichlet Allocation, Markov Random Field, Generalized Kalman Filtering概莫能外——大家可以仔细看看它们的每一个update公式，看看哪个不是在求平均值。

怎样求平均值

平均值是很重要的。不过怎么求呢？这似乎是小学初中就解决了的问题。不过，求平均值的世界其实是如此博大精深。如果说它是少林武学，我现在这点水平，也就够在嵩山下扫扫地罢了。很多在世界上赫赫有名的数学家，穷毕生心血，方能一窥堂奥。

虽然，只有扫地的水平，不过起码也看过大师们练武。这门学问主要有两个方面：得到data求平均值，得到model求期望。

先说说求data的平均值。这太简单了，有什么好说的。不就是加法和乘法么，小学学过算术的人都会算，即使没学过，拿个计算器也照样算。在通常的实数空间内，确实很简单；不过对于一般的求平均值的情况，就非常非常困难了。一般来说，求平均值有两个流派，一种是基于线性代数(linear algebra)，另外一种是基于度量空间(metric space)。前面一种大家很熟悉：

m = (x1 + x2 + ... + xn) * (1/n)。

这是我们读了这么多年书最常见的平均值。不过，这样定义太局限了，它要求这些东西能做加法和数乘——我不得不说，这个要求实在太高，只有线性空间（这种空间是数学里面的贵族，它们什么好处都全了）能够满足——对于数学领域更广大的人民群众（各种更一般的数学结构，比如群，拓扑流形），加法和数乘简直是一种奢侈得不切实际的活动。

其实平均值是一个非常广泛的概念，不仅仅存在于线性空间中，还为广大人民群众服务。对于某个度量空间，它的一般性定义是这么给出的

使得 d(m, x1) + d(m, x2) + ... + d(m, xn) 最小的那个m

也就是说，求平均值是一个优化问题。关于这个问题，在不同的空间中有不同的答案：在最高级的希尔伯特空间中（定义了内积的完备线性空间），m就是上面给出的基于线性代数的形式。所以说，基于线性代数的定义仅仅是基于度量空间的定义的一个特例。不过由于这个特例被广泛使用，所以大家一说平均值就想起它，而不是一般形式。在推广一些的巴拿赫空间中（定义了范数的完备线性空间），上述的问题是一个凸优化问题，因为范数必然是凸函数。它具有唯一的最优解。

最困难的是在非线性空间中。一个典型的例子是黎曼流形（注意，这里我们只讨论黎曼流形，对于更为一般的拓扑流形或者微分流形，因为不具有度量结构，所以不能定义均值。）在黎曼流形上，两点间的距离是通过测地距离给出的。在黎曼流形上，通过测地距离定义的平均值，叫做黎曼中心。一部分朋友对于这几个术语可能不太熟悉，还是举个形象点的例子。比如，在地球上给出几个地点，你要在地面上找一个“平均地点”，使得它到那几个地点的“地面距离”的平方和最小。如果，用传统的算术方法拿这些地点的三维坐标来算，你估计得在那钻个油井了。对于“球面平均”问题（专门一点的说法叫做特殊正交群SO(3)的黎曼中心，恩，这个名词我也有点晕），到了在本世纪，在数学里依旧可以发paper，目前还没有一般情况下的解析解。

别的领域我不懂，不过“球面平均”在vision里面价值是很大的，它是对三维旋转变换建立统计模型的基础——我们再一次看到了求平均值对于统计的重要意义。球面平均求的是“平均”的旋转，如果对于一般的仿射变换(Affiine transform)，“平均”的变换又怎么求呢？这是个open problem，留待大家思考。

怎样求期望

说完从data求平均值，再说说从model得到期望(expectation)——这们学问就更博大了。虽然，期望的定义很简单——求和或者积分就行了。不过，它的实际计算，对于很多实际模型是intractable的。

概率论最早源于掷色子，我们的前辈数学家们为了破解求复杂模型求期望的问题，提出的方法就是掷色子。在学术上，美其名曰“蒙特卡罗方法”(Monte Carlo)。原理很简单，不断地掷色子来大量采样，然后从采来的样本求平均值来逼近模型的期望。

掷色子是世界上最有学问的之一，正因为如此，我们对于“赌神”，“赌王”之类的人物崇拜犹如滔滔江水，因为它们掷色子掷得好。无数的统计学家把毕生经历奉献给掷色子（采样）事业，并且做出伟大成就。关于采样的专著和文献，汗牛充栋。

掷色子就这么难么？是的。据估算，即使对于一个复杂度不高的model，要得到一个可以接受的估计，所需的样本量往往大得惊人，而且指数增长。如果不掌握要领，你即使掷到宇宙末日，估计离一个靠谱的估计还远着呢。采样技术名目繁多，最流行的莫过于重要性采样(importance sampling)和马尔科夫链蒙特卡罗过程(MCMC)。具体就不多说了。

我们的生活从来不缺乏距离的概念，无论是时间的还是空间的，可以测量的还是不可以测量的。自我们来到这个世界，就会用我们还很幼小的眼睛测量着自己和身边的人的距离，然后跟着距离自己最近的人学叫“妈妈”；长大了，我们学会了用“距离产生美”这种不知道属于公理还是定理的命题，提醒自己不要和心仪的mm走得太近；而垂垂老矣的人们则开始计算自己到生命终点的距离，盘算着什么时候该立遗嘱了。

什么叫距离呢？随便翻开一本数学教科书，你会发现，这些书会在这个或者那个角落告诉你，所谓距离，就是一个符合对称性和三角不等式的非负二元函数。为什么要符合对称性和三角不等式呢——大部分的书会告诉你，这是规定——不符合的就不是距离。少部分负责任一些的书会告诉你，不符合这些条件的“距离”会多麻烦。于是你接受了。

当你放下书本，回到我们多姿多彩的生活中的时候，这个呆板的定义似乎不能有效地解决你生活中的问题。你去hiking的时候，入口处告诉你，从山下到山上的距离是多少多少里路，按说上山和下山的距离是一样的，可是当你攀到山顶又走回来的时候，心里可能犯嘀咕，怎么感觉距离不一样呢？伟大的数学家们是不会错的。这是相对论！——那些费了半天劲才把洛仑兹变换搞明白的人们，生怕错过了这个机会就没有机会显示自己深厚的物理底蕴了。不过，我只是相信一点，根据目前人类的进化水平，即使把世界短跑冠军的运动速度和地球公转自转速度加起来再乘以10，离光速还远着呢。

再说一个例子，不知道男同胞们是不是发现，当你想去接近你的梦中情人的时候，距离似乎遥不可及——走出太阳系似乎都没有那么远，反过来，当她想接近你的时候，这个距离比任何预先给定的正实数都小——我有点怀疑，牛顿或者莱布尼茨当年是不是有过类似体验，才总结出了微机分——这告诉我们为什么微机分不是女生提出的。

为了能让距离去解释上面说到的现象，我们有必要把它的概念推广一下，把对称性去掉——很多情况下，我们甚至把三角不等式也去掉。一个著名的例子，就是Kullback-Leibler divergence——用来描述两个分布的“距离”。大家注意了，这里定义这个的人很聪明，为了不和数学家作对，他选择叫做divergence，而不是distance。不过，很多信息论和统计学的书都犹抱琵琶半遮面地告诉我们，其实可以把它YY成为某种距离。伴随着对称性的丧失，距离的方向性出现了。就是说从a到b的距离，和从b到a的距离是不一样的——恩，这种推广看起来很适合用来计算你和你心仪的人的距离，或者山顶和山脚的距离。

小学老师告诉我们怎么去量度两个点之间的距离，就是拿一把尺子。可是，很多时候，你没有机会使用直尺的。你所能做的就是从这点走到那点，看看费了多少劲——这就是我们大多数人在生活经验中的距离。黎曼老先生，作为理论联系实际的代表，第一次从在数学上总结了这种生活上的距离——geodesic distance，中文叫做测地距离。它是怎么算距离的呢？就是从起点出发，一步步走向目标，然后把每一步费了多少劲加起来。至于，每一步费了多少劲怎么算，大家都可以有不同的算法——但是，这些都叫Riemann Metric。 为了大家计算距离时的身体健康，鼓励大家节省能源，规定，只有按照最省事的方法到达目标，这样算出来的才叫距离。 不过，在很多实际应用中，大家只能找到比较省事的方法，未必是“最省的”，也睁一只眼闭一只眼，把算出来的东西追加“距离”的光荣称号。

打破对称性的千年枷锁，扔掉直尺这种陈腐工具，人们获得了空前的思想解放。男生和女生们开始附庸风雅地用曾经只存在于象牙塔的概念——距离——去评价自己和她或者他的关系。如何评价，见仁见智——在我看来，很多人的metric里面不外乎写了多少情书，给电信公司贡献了多少短信费，qq/msn在线了多少时间，又或者吃了多少顿麦当劳。。。。。。在这个定义的基础上，“距离产生美”——这个挂在多少人口头的箴言横空出世了。根据距离就是费了多少劲的意思，这句话告诉我们，只有费了很多功夫，死了无数脑细胞，才能得到，或者还得不到的才是美的；信手而获，不需要追求的，就谈不上美了。从这个意义上说，这句话和高中的学到的“劳动产生价值”的道理是一样的，只不过，“劳动产生价值”是物质层次的——太俗了，“距离产生美”是精神层次的，档次和格调显然不一样。