GRE 和机器学习

其实是在之前复习 GRE 的时候突然想到的一些好玩的事情，只是一直没有时间写出来，今天圣诞节，决定抽空把它写了。先祝大家圣诞快乐！

但凡是考过 GRE 的同学都知道，复习过程是很痛苦的。不过现在是信息时代，找资料确实很方便，除了各种复习材料之外，网上也不乏各种复习方法总结建议之类的，其中甚至还有帮你把每天的复习细节都具体安排好了的。当然其中也有许多很好的建议和经验，但是无论如何还是自己才知道什么方法适合自己啊。所以闲暇的时候我自己也在想，这个过程究竟是怎么一回事，后来越来越觉得和机器学习其实有相当多的地方。

最典型的就是类比反义了，GRE 里的类比就是给一个词对，让你分析出这两个词之间的关系，然后类比这个关系，在 5 个选项里找出同样关系的词对；反义则要简单得多，就是给一个词，找到它的反义词。其实是很简单的问题，我曾经尝试了一下，如果看着翻译过来的中文做题的话，错误率可以很小，所以最大的瓶颈其实就在词汇量了，词汇也应该是 GRE 笔试复习过程中最大的坎。一般复习方法分为两种，一种是被红宝书，或者其他各种“宝书”，甚至还有看字典的，另外一种则是突击看诸如“猴哥类反”之类的往年题目的正确答案列表，以及最近几年的机经之类的。

这两种方法就正好和机器学习里的两种方法对应起来了——“Generative Model”（生成模型）和“Discrimative Model”（判别模型）。背红宝的方法，可以看作是生成模型，它学习的结果是知道每个词的意思，这样一来，就可以以不变应万变了，因为词的意思一旦知道之后，各种问题都会变得很容易，比如类比反义，虽然也会有个别歧义的情况，但是大部分时候，一旦你知道了单词的意思，要选正确答案就变得非常容易了。在机器学习里生成模型的一个典型例子就是进行概率密度估计，也就是说，我要从所给定的数据中学习出什么规律来的话，就先去估计出生成这个数据的本征概率模型，一旦这个模型知道了，其他的问题就都迎刃而解了。比如，对于分类，其实只要比较两个类别生成该数据的模型，选择概率最大的一个即可，而回归问题则可以通过对条件概率求期望而得到。所以，生成模型，一旦成功估计出了正确（或者接近正确）的模型，将会非常强大。然而，在实际中，除非数据非常稠密，资源非常丰富（某些模型需要占用相当多的计算和存储资源），经常会得不到满意的结果。

另一方面，判别模型就不像生成模型那样野心勃勃了，要做分类就做分类，它只关心怎么把手头这个分类问题做好，而完全无视你的数据是如何生成的，以及模型是否能够处理其他更多的问题。例如，对于二分类问题，生成模型可能要去估计两个概率模型的期望和协方差矩阵等一大堆参数（例如，如果 $n$ 是数据维度的话，参数个数通常是在 $O(n^2)$ 这个数量级的，如果是非参数方法，则更多了），而生成模型只要估计出一个分隔超平面就可以了（通常参数就在 $O(n)$ 这个数量级） 。所以，就和背“猴哥类反”之类的资料一样，如果我的目的单纯就是为了做类反，那么我就没有必要费力去背红宝那样把每个单词的各个意思搞清楚——特别是在时间和精力不允许将红宝背熟的情况下。也就是说，如果当前的条件限制比较大（例如数据不充足），强行进行生成模型的估计，可能会得到一个比较差的模型，往往就不如专用的鉴别模型。例如对于那些单词，我只要知道它经常和哪些词搭配出现组成类比反义，就足以应付类反题了。

当然，鉴别模型的缺点就是局限性，针对这个问题学习出来的模型，基本没法用来处理其他的问题。这在机器学习中通常不是太大的问题，不过对于我们日常学习来说，就是一个需要权衡的问题了。至少我是不希望费那么多力背单词的结果只是为了做那么几道类反，之后就毫无用处了。总之，这是一个和资源和目的都有关系的权衡问题。

除了权衡之外，学习方法的选取还有其他问题需要考虑，这实际上不止限于 GRE 的复习了，关于我们教育中的学习问题，怎么样的学习方法才是行之有效的，我猜这个是不是“教育学”所研究的一个重要部分。当然，研究人的学习问题要困难许多，因为但凡和人打交道，都会有许多的不确定因素，然而在机器学习中则没有这些问题——当然，这个问题仍然是非常困难的。具体来说，在机器学习中，有一个子领域叫做 Learning Theory （学习理论），就专门研究这些问题，有一个很牛会议叫做 Conference on Learning Theory (COLT) ，顾名思义啦。简单地来说，给定一个学习算法，它到底是不是合理，这个问题是需要证明的。

比如，上太傻或者 GTer 或者甚至校内上，都可以看到一大堆经验贴、总结贴、建议贴、方法贴之类的，甚至很多还互相矛盾，那么应该相信哪个呢？通常比较可信的可能是某个比较“权威”的人发的帖子，比如版主之类的，不过，人们大概会更在意另一类帖子，比如“GRE 780+800+5.5 猛男复习经验分享”这样子，也就是已经有成功案例的。当然，最靠谱的还是你自己用一套方法复习，然后考了超高的分数，也许自己也已经按捺不住想要去发帖给大家分享经验了。然而，这样子真的靠谱吗？我想，但凡写过 GRE 的 Arguments 的都知道，以偏概全是很严重的错误，特别是在例子只有一个这种极端的情况。当然，并不是说，有人这样子复习，然后考了高分，我反而要说这样的复习方法是错误的；只是说，仅从一个人考了高分这件事情，并不能证明这样的方法是很好的。

不过，其实这样的经验方法或者启发式方法，我们时常用到，特别是在做 Engineering 等方面来说，通常灵感和经验比严格的证明重要得多——或者说，管用得多。比如在调试程序的时候，我们有时候会“随意地”（当然，并不是那么随意，这可能是凭一种经验或者第六感，总之是处于无法具体描述的原因）改变一些代码，而且不少时候都能“奇迹般地”解决问题。再比如，我写了一个程序，在各种不同的输入下，运行了很多次都是对的，那它就一定正确了吗？当然不一定，不过基本上也不会有人想要去从数学上来证明一段代码的正确性（虽然似乎确实有这样的研究工作）。不过，太过极端地依赖于经验或者启发式，也是会出现问题的。

最典型的例子就是传统的 AI ，人们根据自己的经验、理解以及对生物大脑模型的认识，设计出一些“理所当然”的算法和模型，得到了一些初步的令人鼓舞的结果，然而后来的发展并没有如预期的那么顺利，到现在传统 AI 的没落应该也不是什么有争议的事情了。而机器学习呢，其实一开始也面临同样的问题，当然后来学习理论得到了应有的重视。简单来说，对于一个学习算法，你需要说明它为什么有道理，或者说，为什么能学习。

事实上，有很多方法通常是非常理所当然的，比如概率模型估计中的最大似然的方法，简单地说，最大似然就是在给定一定数量的采样数据的情况下，估计出一个使得生成这些采样数据的概率（称作“似然 (Likelihood)”）最大的那个模型。一方面，这个感觉上很合理，如果我这些采样数据是从这个模型生成出来的，那当然它们的概率会比较大，因为如果概率比较小的话，就不容易背生成出来以及被观测到了；另一方面，在实际应用中效果也挺好。然而，最大似然的方法有没有问题呢？有，比如，用最大似然的方法来估计高斯混合模型(Gaussian Mixture Model)，其最优解会是及其病态的情况——其中一个 Gaussian Model 会变成期望是某一个数据点，而方差是零的情况，这个时候整个数据集的似然会变到无穷大，然而这显然不是我们所期望的结果。

总之，证明算法的正确性是一个非常重要的问题。实际上，早期的机器学习研究中，已经有这样的工作，很多模型，都被证明具有渐进收敛性，简单地来说，可以证明，通过这些算法估计出来的模型，当数据采样点趋向于无穷多的时候，能够渐进地收敛到真实的模型。一个简单的例子就是“最近邻分类器”，它的学习方式就是简单地把所有训练数据和相应的标签全部记住，而分类的时候就直接指定为离待分类数据最近的那个训练数据点的标签。当训练数据点趋向于无穷的时候，不严格一点，我们可以看成待分类数据最近的那个点可能就是它本身了——也就是说其实训练数据集已经包含了所有可能的点，也包含了这个待分类的数据点，因此它的真实标签我们其实已经知道了（如果还有噪音的话，那就再求一个期望吧），所以也就能得到正确的结果了。

这样的学习理论当然比没有理论是一大进步，然而，对于数据趋向于无穷多的时候的结论，是否一定能得到在数据点有限或者甚至很少的时候也有很好的效果呢？似乎不一定，然而人们似乎也不太 care 这些，而是激动地去发展各种算法，并把实践中碰到的问题归为特例采用一些特殊的手段来处理。在科学发展史上似乎总是有这样的例子，人们以为发现了真理，“剩下的就只剩下计算了”。不过也总是会有清醒的人。比如 Vapnik 大仙，我记得以前在 blog 里贴过他的照片的：

(ps: 有谁看得懂那句“All your Bayes are belong to us”的典故吗？ 😀 )总之 Vapnik 认识到我们应该去研究在有限样本或者甚至小样本的情况下的学习问题，特别是相关的学习理论。简单来说，仅仅依靠“在样本趋向于无穷”的时候的收敛性并不能保证学习算法的优良性，我们需要的学习算法是要能够通过有限的数据得到足够合理的结果，使其具有良好的“泛化能力”，或者更通俗地来说，“归纳能力”。也就是说，学习算法要能够从有限的样本总归纳出模式和规律，这个归纳的过程使得学习的结果能够应用到未知的数据上也能得到好的结果。

在这个意义下，最近邻分类器实在不是一个很好的算法（我们现在都知道它在数据量很小的时候会严重过拟合），它的做法就是简单的“死记硬背”，而几乎没有任何“归纳”可言。这样一来，两种观点其实可以有趣地和我们生活中关于“天才”的两种观点对应起来。比如在传统的学习理论框架下，我们古时候（当然现在也仍然存在一些这样的看法）对于天才的标准——比如，“倒背如流”，甚至“过目不忘”——就是完全符合原来的渐进理论的很优良的“学习机器”。因为如果能过目不忘了，那么在数据样本趋向于无穷多的时候，也就是当他把全宇宙所有的知识都背下来之后，那肯定是全能的了。然而这只是一个极限情况，极限情况下的完美，能否得出在正常的有限的情况下也表现良好呢？这个恐怕不行了——一个人如果只有记忆能力而没有归纳推广能力的话，很难说他能学到什么知识啊。这也正是现代的比较合理的对于天才的观点了——天才应该是指那些能够深刻洞察问题本质，抓住其规律的人。

总之扯回学习理论，Vapnik 大仙研究的问题，正是在有限的样本下训练出来的模型，是否具有优良的泛化能力，换句话说，在有限的数据下训练出来的模型，是否能够在那些没有接触过的数据上也能表现良好。事实上，一开始他的工作并没有得到太多人的重视，直到他根据自己的理论设计出了一个算法——支持向量机 (Support Vector Machine) ，并取得了优良的学习性能（到今天 SVM 甚至已经被泛滥地应用与工程领域啦），人们才开始重视这方面的研究，才发现那些之前碰到的问题以及为此而设计的特殊的一些解决办法，都可以在这个理论框架下得到统一的解释。

到这里已经扯得够远了，也不打算再讲介绍 Vapnik 老爷爷的理论具体是什么概念，实际上我现在也讲不动，目前自己的功底太有限了，光写这么一篇水文已经写得很吃力了。也许等到将来认识再深刻一些了，可以再讲一些更有趣的东西。 🙂 迫不及待的同学可以自己去看 Vapnik 老爷爷的书 Statistical Learning Theory 和 The Nature of Statistical Learning Theory ，中文译本叫做《统计学习理论》和《统计学习理论的本质》。粗略地讲，后一本可以看成是前一本的几乎删掉了所有证明细节的精简版。