终极算法【7】——类推学派
类比是推动许多历史上最伟大科学进度的动力。当达尔文阅读马尔萨斯的《人口论》时，被经济和自然界中生存竞争的相似性触动，所以有了自然选择理论的诞生。
类比在机器学习中扮演重要性刚开始进展缓慢，它的第一个算法的化身出现在一份写于1951年的技术报告中，作者是两位伯克利的统计学家——伊夫琳.菲克斯和乔.霍奇斯。最近邻算法是我们类比学习法之旅的第一站，第二站是支持向量机，第三站也是最后一站，是成熟的类比推理法。
类推学派不像其他学派有很强的身份意识和共同理想，类推学派则更像研究人员松散的集合体，他们的统一依靠的是对于作为学习基础的、相似性判断的信任。
最近邻算法是人类有史以来发明的最简单、最快速的学习算法。实际上，甚至可以说，这是人类可以发明的最快速的算法。研究人员最初之所以对最近邻算法持怀疑态度，是因为它不确定能否找到两个概念之间的真正边界。但1967年，汤姆.科韦尔和彼得.哈特证明，在给定足够数据的情况下，最近邻算法最糟糕时易于出错的概率也仅仅是最佳可行分类器的两倍。
在低纬度条件下（比如二维或者三维），最近邻算法通常能够很好地起到作用。随着维度的上升，事情就会很快陷入崩溃状态。举个例子，符号学派的方法很擅长处理非相关属性：如果该属性不含任何关于等级的信息，那么它就不包含在决策树或者规则集当中。但让人感到无望的是，最近邻算法会受到非相关属性的迷惑，因为这些属性都能够促成例子之间的相似性。有了足够的相关属性，不相关维度中的偶然性会清除重要维度中有意义的相似性，而最近邻算法和随意猜测相比也好不到哪里。
最近邻算法的基础是找到相似物体，而在高维度情况下，相似性的概念就会无效。超空间就像过渡区域。在三维空间里的直觉不再适用，怪异离奇的事开始发生。
另一个让人不安的例子发生在正态分布，又名钟形曲线。正态分布认为，数据本质上就落在一个点上（正态分布的平均值），但其周围也会有模糊的东西（由标准差给出）。在超空间中不是这样的，在高纬度正态分布中，你比较有可能得到远离而不是接近平均值的样本。超空间中的钟形曲线看起来更像甜甜圈，而不像钟。当最近邻算法走进这个颠倒的世界时，它会变得非常困惑。所有的例子看起来都一样，同时因为它们距离彼此太远，无法做出有用的预测。
实际上，没有哪种算法能够幸免于维数灾难。这是机器学习中，继过拟合之后，第二个最糟糕的问题。“维数灾难”这个术语由理查德.贝尔曼在50岁时提出的，他是一位控制论理论家。他观察到，控制算法在三维空间中可以起到很好的作用，但在高维度空间中则变得效率极低。在机器学习中，问题不仅仅在于计算成本——随着维度上升，变得越来越困难的是学习本身。
然而，并不是所有东西都丢失了。我们能做的第一件事就是摆脱不相关维度。决策树会自行做好这一点，方法就是计算每种属性的信息增益，然后只使用最能提供信息的属性。对于最近邻算法来说，我们可以完成类似的事情，方法就是首先丢弃所有那些信息增益低于阈值的属性，然后只在简化的空间中测试相似性。
直到20世纪90年代，应用范围最广的类比学习算法就是最近邻算法，但后来被其他学派夺去光芒。当时一种新的以相似性为基础的算法横空出世，它就是支持向量机（SVM），是弗拉基米尔.万普尼克（一位苏联频率论研究者）的创意。
表面上看，支持向量机看起来很像加权k最近邻算法：正类别与负类别之间的边界由一组例子、其权值加上相似性测度来确定。测试实例会归入正类别，条件是从平均水平上看，它看起来更像正面例子而不是负面例子。平均数会被加权，而支持向量机只会记住那些用于确定边界的关键例子。
通常，支持向量机选择的支持向量越少，就能更好地进行概括。任何不是支持向量的训练例子可能会被正确分类，条件是它显示为测试实例，因为正面和负面例子之间的边界仍在同样的地方。除了实践中的功绩，支持向量机还完全改变了许多机器学习中的传统观点。
然而，支持向量机唯一最让人吃惊的属性就是，无论它形成多么弯曲的边界，那些边界也总是直线（或者一般为超平面）。这并不矛盾，因为直线存在于不同的空间中。
两个东西如果在一些方面意见一致，那么它们就是相似的。如果它们在一些方面意见一致，可能在其他方面也会一致，这就是类比的本质。它还表明了类比推理中的两大子问题：弄明白两个事物的相似度，确定由它们的相似度还能推导出什么。
在任何类比学习中，最重要的问题就是如何度量相似性。它可以如数据点之间的欧几里得距离那么简单，也可以和含有多个水平子程序的一整套程序那么复杂，而且这些子程序的最终产出是相似度值。我们可以将类比学习应用到所有种类的物体中，而不仅仅是属性向量，只要我们有度量它们之间相似度的方法。类比推理的第二部分，就是弄明白在已经发现的相似点的基础上，如何推导出新的东西。
认知科学见证了符号学派与类比学派之间很长一段时间的争论。符号学派指向它们能够模仿但类推学派无法模仿的东西；接着类推学派弄明白如何做到这一点，然后想出他们能够模仿但符号学派无法模仿的东西，这个循环一直重复下去。
至此，我们已经完成了对5个学派的介绍，同时集中了他们的观点，议定他们的界限、探索了这些碎片如何拼凑在一起。我们现在知道的东西比一开始多的多，但还有一些东西没有找到。在这个谜题的中心有一个很大的漏洞，使人难以看到其模式。问题在于，目前为止，我们见过的所有学习算法，需要一位老师来告诉它们正确答案。
参考文献：
终极算法. [美] Pedro Domingos 著. 黄芳萍 译