终极算法 第七章 类推学派:像什么就是什么

终极算法 第七章 摘要

弗兰克·阿巴内尔是历史上最臭名昭著的骗子之一,莱昂纳多·迪卡普里奥曾在斯皮尔伯格的电影《逍遥法外》中饰演阿巴内尔。他伪造价值数百万美元的支票,冒充律师和大学讲师的身份,并以泛美航空飞行员的假身份环游世界,这些都发生在他21周岁之前。也许他最令人吃惊的“事迹”,就是在20世纪60年代的亚特兰大成功假扮医生将近一年之久。行医应该需要在医学院学习多年,要有执照、实习期等诸如此类的东西,但阿巴内尔成功避开所有这些细节,而且从未被人发现。

类比是推动许多历史上最伟大科学进步的动力。当达尔文阅读马尔萨斯的《人口论》时,被经济和自然界中生存竞争的相似性触动,所以有了自然选择理论的诞生。波尔的原子核模型是由将模型看作微型太阳系、将电子看作行星、将原子核看作太阳而产生的。克库勒也是白天做梦梦见蛇吃自己的尾巴才发现苯分子的环状结构的。最近邻算法,正如其名,是我们类比学习法之旅的第一站。第二站是支持向量机,这是世纪之交风靡机器学习领域的原理,但最近风头被深度学习掩盖。第三站也是最后一站,是成熟的类比推理法,几十年来是心理学和人工智能的重要组成部分,也是几十年来机器学习领域的背景主题。

在机器学习中,相似性是核心思想之一,而类推学派会以各种伪装的方式来保护它。也许在未来10年,机器学习会被深度类比统治,在某种算法中,与最近邻法的高效、支持向量机的数学精密性、类比推理的力量和灵活性结合。

完美另一半

最近邻算法是人类有史以来发明的最简单、最快速的学习算法。实际上,你甚至可以说,这是人类可以发明的最快速的算法。它可以说什么也不做,所以花在运行上的时间为零。再没有比这个更好的了。

研究人员最初之所以对最近邻算法持怀疑态度,是因为它不确定能否找到两个概念之间的真正边界。但1967年,汤姆·科韦尔和彼得·哈特证明,在给定足够数据的情况下,最近邻算法最糟糕时易于出错的概率也仅仅是最佳可行分类器的两倍。举个例子,如果因为数据中的干扰因素,有至少1%的测试例子不可避免地被错误分类,那么最近邻算法保证误差率最多在2%左右。这是一个重大的启示。

维数灾难

符号学派的方法很擅长处理非相关属性:如果该属性不含任何关于等级的信息,那么它就不包含在决策树或者规则集当中。但让人感到无望的是,最近邻算法会受到非相关属性的迷惑,因为这些属性都能够促成例子之间的相似性。有了足够的相关属性,不相关维度中的偶然相似性会清除重要维度中有意义的相似性,而最近邻算法和随意猜测相比也好不到哪里。

决策树也无法幸免于维数灾难。举个例子,你打算学习的概念是一个球体:球内的点是正的,球外的点是负的。通过放在球体内正合适的最小立方体,决策树可以估算球体的体积。这不是完美的方法,但也不会太差:只有立方体的角才会被误分类。但在高维度空间中,超级立方体几乎所有的体积都会出现在超球面外。对于你准确将其标注为正的例子,你会错误地将许多负的例子分类为正,这会让你的准确率骤然下降。

实际上,没有哪种算法能够幸免于维数灾难。这是机器学习中,继过拟合之后,第二个最糟糕的问题。“维数灾难”这个术语由理查德·贝尔曼在50岁时提出的,他是一位控制论理论家。他观察到,控制算法在三维空间中可以起到很好的作用,但在高维度空间中则变得效率极低。例如,当你想控制机器人手臂中的每个节点或者化工厂的把手时,这种情况就会出现。但在机器学习中,问题不仅仅在于计算成本——随着维数上升,变得越来越困难的是学习本身。

空中蛇灾

直到20世纪90年代,应用范围最广的类比学习算法就是最近邻算法,但后来被来自其他学派更引人注目的“表亲”夺去光芒。当时一种新的以相似性为基础的算法横空出世了,横扫之前的所有算法。实际上,你可以说它是自冷战结束以来的另一个“和平红利”。它就是支持向量机(Support vector machines,SVM),是弗拉基米尔·万普尼克(一位苏联频率论研究 者)的创意。万普尼克的大半生都在莫斯科的控制科学研究所度过,1990年,随着苏联走向 解体,他移居美国,在那里他加入传说中的贝尔实验室。虽然在苏联,万普尼克很多时候都 满足于从事理论、纸笔工作,但在贝尔实验室的氛围则不一样。研究人员正在寻找实践结 果,而万普尼克最终决定将其想法变成算法。在几年时间内,他和贝尔实验室的同事已经研 发出支持向量机。不久之后,支持向量机就变得无所不在,并创下不同的准确度纪录。

在现实中,我们通常会让支持向量机违背一些限制条件,这就意味着将一些例子错误分类,或者利用更少的边际,否则它们就会过拟合。如果在正面区域中间的某个地方有干扰作用的负面例子,那么我们不想让边界在正面区域周围环绕,目的只是为了让例子正确。支持向量机早期较大的功绩还在于文本分类,后来证明这是一项大实惠,因为网站那时候才人气渐增。当时,朴素贝叶斯是最先进的文本分类器,但当语言中的每个词都代表一个维度时,甚至它也开始过拟合了。它需要的只是一个词,这个词会偶然出现在训练数据中所有与体育相关(举个例子)的页面中,而不是出现在其他页面中,而朴素贝叶斯开始出现幻觉,以为只要包含该词的页面都是体育页面。但多亏了边际最大化,支持向量机即使在很高的维度中也可以抵抗过拟合。

除了实践中的功绩,支持向量机还完全改变了许多机器学习中的传统观点。例如,它揭穿了“模型越简单就越准确”这个谎言,有时候,这个观点会被误以为是奥卡姆剃刀理论。相 反,支持向量机可能有无限数量的参数,而且只要它有足够大的边际,就不会过拟合。

爬上梯子

在任何类比学习算法中,最重要的问题就是如何度量相似性。它可以如数据点之间的欧几里得距离那么简单,也可以和含有多水平子程序的一整套程序那么复杂,而且这些子程序的最终产出是相似度值。不管怎样,相似度函数控制的是学习算法如何从已知例子归纳出新的例子。我们将自己对问题域所了解的东西插入学习算法中,这就变成类推学派对于休谟问题的回答。

起床啦

认知科学见证了符号学派与类推学派之间很长一段时间的争论。符号学派指向他们能够模仿但类推学派无法模仿的东西;接着类推学派弄明白如何做到这一点,然后想出他们能够模仿但符号学派无法模仿的东西,这个循环一直重复下去。

至此,我们已完成了对5个学派的介绍,同时集中了他们的观点、议定它们的界限、探索了这些碎片如何拼凑在一起。我们现在知道的东西比一开始多得多,但还有一些东西没有找到。在这个谜题的中心有一个很大的漏洞,使人难以看到其模式。问题在于,目前为止,我们见过的所有学习算法,需要一位老师来告诉它们正确答案。

注:摘自原书中文版(百度云下载PDF) 第七章