弗兰克·阿巴内尔是历史上最臭名昭著的骗子之一，莱昂纳多·迪卡普里奥曾在斯皮尔伯格的电影《逍遥法外》中饰演阿巴内尔。他伪造价值数百万美元的支票，冒充律师和大学讲师的身份，并以泛美航空飞行员的假身份环游世界，这些都发生在他21周岁之前。也许他最令人吃惊的“事迹”，就是在20世纪60年代的亚特兰大成功假扮医生将近一年之久。行医应该需要在医学院学习多年，要有执照、实习期等诸如此类的东西，但阿巴内尔成功避开所有这些细节，而且从未被人发现。
想象一下如何去冒这个险。你偷偷摸摸进入医生不在的办公室，不久后有个病人走进来，并把他所有的症状都告诉了你。现在你得给他诊断，除非你对于药物一窍不通。你只有一柜子的病人资料：他们的症状、诊断结果、接受过的治疗等。你该怎么办？最简单的办法就是找到和现在这个病人症状最相似的病人的资料，然后做相同的诊断。如果你对待病人的态度和阿巴内尔一样有说服力，那么可能会成功。在医学之外，同样的思想也很适用。如果你是一名年轻的总统，面临世界危机，就像肯尼迪当年一样，当时美国的一架间谍机报告，苏联的核导弹被部署在古巴，你很有可能因为经验不足而措手不及。你可以找历史上与当前情况相似的场景，然后尝试从这些场景中吸收经验。参谋长联席会议敦促对古巴进行袭击，但肯尼迪那时刚读过《八月炮火》，这是一本描写第一次世界大战的畅销书，所以他知道那样做很容易会引发全面战争。所以他选择了对古巴进行海上封锁，也许这样做把世界从核战争中拯救出来了。
类比是推动许多历史上最伟大科学进步的动力。当达尔文阅读马尔萨斯的《人口论》时，被经济和自然界中生存竞争的相似性触动，所以有了自然选择理论的诞生。波尔的原子核模型是由将模型看作微型太阳系、将电子看作行星、将原子核看作太阳而产生的。克库勒也是白天做梦梦见蛇吃自己的尾巴才发现苯分子的环状结构的。
类比推理有着突出的知识谱系。亚里士多德在他的相似律中就表达了这一点：如果两个事物相似，其中的一个想法会触发另外一个想法。诸如洛克和休谟之类的经验主义者就追随这个规律。尼采说，真理是一支由暗喻拟人组成的队伍。康德也是其中的信奉者。威廉·詹姆斯认为：“这种意义上的一致性是我们思想的支柱。”一些当时的心理学家甚至认为从整体上看，人类认知是分析必不可少的部分。我们依靠它来找到通往新城市的道路，并理解诸如“领悟”“形象高大”之类的表达。那些十几岁、喜欢说话时在每个句子中加入“像”的人也许喜欢且认为类别是重要的。
考虑到这一点，类比在机器学习中扮演重要角色就不足为奇了。刚开始它进展缓慢，甚至被神经网络夺走了光芒。它的第一个算法的化身出现在一份写于1951年、名不见经传的技术报告中，作者是两位伯克利的统计学家——伊夫琳·菲克斯和乔·霍奇斯。这篇报告几十年之后才发表于主流期刊中。但同时，关于菲克斯和霍奇斯的算法的论文也开始出现，后来逐渐增加，直到它成为计算机科学界中受到研究最多的文章之一。最近邻算法，正如其名，是我们类比学习法之旅的第一站。第二站是支持向量机，这是世纪之交风靡机器学习领域的原理，但最近风头被深度学习掩盖。第三站也是最后一站，是成熟的类比推理法，几十年来是心理学和人工智能的重要组成部分，也是几十年来机器学习领域的背景主题。
5个学派中，类推学派是最不具有凝聚力的一个学派。不像其他学派有很强的身份意识和共同理想，类推学派则更像研究人员松散的集合体，他们的统一依靠的是对于作为学习基础的、相似性判断的信任。一些人，比如支持向量机的支持者甚至可能会反对将自己归入这个范畴。但我认为如果人们能为共同的事业而努力，会受益很多。在机器学习中，相似性是核心思想之一，而类推学派会以各种伪装的方式来保护它。也许在未来10年，机器学习会被深度类比统治，在某种算法中，与最近邻法的高效、支持向量机的数学精密性、类比推理的力量和灵活性结合（瞧，我又泄露了自己的一个秘密研究计划）。
完美另一半
最近邻算法是人类有史以来发明的最简单、最快速的学习算法。实际上，你甚至可以说，这是人类可以发明的最快速的算法。它可以说什么也不做，所以花在运行上的时间为零。再没有比这个更好的了。如果想掌握面部识别技巧，且有大量标有脸部或非脸部标签的图片，你只需让算法待在那儿就好。别担心，高兴起来吧。在不知道的情况下，那些图片已经暗中形成关于“什么是脸”的模型。假设你是脸书，想在照片上自动识别人脸，人们上传这些照片，就是用朋友的名字来标记这些照片的前奏。不用做什么是一件好事，只要脸书用户每天上传超过3亿张照片就可以了。将目前为止我们见过的学习算法（可能要排除朴素贝叶斯法这个例外）应用到这些照片上，可能需要一卡车计算机，而贝叶斯算法的智能程度还不足以用来识别脸部。
当然，这是要付出代价的，这个代价在测试时会出现。名叫简的用户刚上传一张新的照片。这是一张脸吗？最近邻算法的回答是：在脸书所有标记过的照片库中，找到那张和这张最相似的照片（它的“最近邻”）如果那张照片包含一张脸，这张也会有。这足够简单，但理想的情况下，你得在不到一秒的时间内浏览近几十亿张照片。就像一个不想为考试而学习的懒学生，最近邻算法此时猝不及防，不得不断断续续地运行。不像在现实生活中，你的妈妈会跟你说不要把今天可以做的事留到明天，在机器学习中，拖延真的可以带来成功。实际上，学习的整个风格（最近邻算法是其中一种）有时会被人们称为“懒惰学习算法”，在这种情况下，这个术语并没有什么贬义。
懒惰学习算法之所以比它表面看起来更加智能，是因为虽然它的模型是隐性的，但其实它可以很复杂。考虑到极端的情况下，每个等级我们只能有一个例子。例如，我们想知道两个国家的边界在哪里，但我们知道的仅仅是其首都的位置。多数学习算法可能会被难住，但最近邻算法会恰当地猜出，边界会是一条线，位于两个城市的中间位置（见图7–1）。
图7–1
边界上的点距离两个首都的距离都一样，边界线左边的点距离Positiville市较近，因此最近邻算法假定这些点是Posistan国的一部分，反之亦然。如果那条线就是准确的边界，当然是万幸，但作为一种近似法，很有可能这条线什么也不是。当我们知道边界线两边都有很多城市时，事情才真正变得有趣起来（见图7–2）。
图7–2
最近邻算法可以暗中形成一条非常复杂的边界线，虽然它所做的只是记住每个城市的位置，然后将这些点相应地分给每个国家。我们可以将城市的“城域”看作那些最靠近该城市的点，城域之间的界线在图中用虚线来表示。现在Posistan只是它的所有城市城域的集合，和Negaland一样。相反，决策树（举个例子）也许只会形成不是南北向就是东西向的边界，可能更不利于找到真正的边界。因此，虽然决策树算法“愿望更加强烈”，在学习期间很努力地想弄明白边界线的位置，但“懒惰的”最近邻算法实际上最后会胜出。
懒惰学习算法会胜出的原因在于，和构建全局模型（例如，决策树）相比，只要每次弄明白指定的点在哪里会较为简单。想象一下，利用决策树来尝试确定什么是脸。你可以说，脸有两只眼睛、一个鼻子和一张嘴，但什么是眼睛，而你在一张图片中怎样才能找到它呢？如果人的眼睛是闭上的，那又会怎样呢？准确定义一张脸，细到每个像素，这是十分困难的，在表情、姿态、背景、光线条件各异的情况下尤甚。而最近邻算法则走捷径：如果数据库中与简上传的最相似的那张照片是脸部照片，那么简的照片也是。要出现这种情况，数据库就得有一张照片，与新照片足够相似，因此，数据库越大越好。对于一个简单的二维问题，比如猜出两个国家的边界，一个小数据库就足够了。对于一个很难的问题来说，如识别脸部，因为每个像素的颜色都是变化的一个维度，所以需要巨大的数据库。目前我们有这些数据库。但对于渴望学习的算法来说，要从这些数据库中学习东西可能代价很大，因为这种算法要明确划分脸部和非脸部的界线。然而，对于最近邻算法来说，界线隐含在数据点和距离度量中，而唯一要付出的就是查询时间。
构建局部模型而非全局模型的相同想法可以应用于分类之外的用途。通常科学家们利用线性回归来预测连续变量，但大多数现象是非线性的。幸运的是，从局部来看，它们是线性的，因为平滑曲线可以局部近似为直线。因此如果你只用直线来对查询点附近的点，而不是尝试对所有的数据都进行拟合，那么你现在就能拥有一个非常强大的非线性回归算法。懒惰也会有回报。如果肯尼迪需要一套完整的国际关系理论来决定该如何应对苏联在古巴部署的导弹，他可能会遇到麻烦。相反，他从这个危机与第一次世界大战的爆发之间找到相似点，而这个相似点指引他做了正确的决定。
最近邻算法可以用来救命，正如史蒂芬·约翰逊在《幽灵地图》中描述的那样。1854年，伦敦爆发霍乱，城市部分地区8个人中就有1个人死亡。当时的理论认为，霍乱由“不良气体”引起，但该理论并没能阻止霍乱的蔓延，约翰·斯诺（一位质疑该理论的内科医师）则有更好的主意。他在伦敦地图上标出所有霍乱病例的位置，然后划分地图，每个区域都距离公共水泵最近。有了！几乎所有死者都位于某个特定水泵的“城域”中，也就是位于苏活区的布罗德大街上。经推断井里的水被污染了，斯诺说服当地人禁止使用该水泵，流行病就消失了。这段插曲孕育了流行病学，而它还是最近邻算法取得的第一次成功——流行病学正式出现还是在近一个世纪之后。
有了最近邻算法，每个数据点就是自己的微型分类器，为所有获取的查询例子预测级别。最近邻算法就像一群蚂蚁，在这个队伍中每只蚂蚁都做得很少，但把力量聚集在一起，它们就可以移动高山。如果一只蚂蚁的负重过大，它可以和周围的蚂蚁共同承担。本着同样的精神，在k最近邻算法（k–nearest–neighbor algorithm）中，测试的例子的分类方法是找到它的k最近邻，然后让它们进行投票。如果距离上传照片最近的图片是一张脸，但接下来最近的两张却不是，第三张最近邻的照片也还是会认为最新上传的不是脸。最近邻算法容易犯过拟合错误：如果数据点的等级是错误的，它会蔓延到整个城域当中。K最近邻算法更可靠，因为只有在多数k近邻受干扰时才会出错。当然，犯错的代价就是它的图像会更模糊：边界的细节因为投票而变得模糊。K值变大时，方差变小，但偏差变大。
利用多个k最近邻而不仅一个近邻，这不是事情的结局。直观来看，与测试例子最接近的例子应该更重要。这让我们引出加权k最近邻算法。1994年，明尼苏达州立大学和麻省理工学院的研究人员建立了一个推荐系统，其构建基础是他们所谓的“一个看似简单的想法”：过去人们同意的话，将来他们也还会同意。这个想法直接引出协同过滤系统，所有典型的电子商务网站都有这些系统。假设像网飞一样，你建立了电影评分的数据库，用户对他看过的电影都会给出1~5颗星的评分。你想确认用户肯恩是否会喜欢《地心引力》，因此你找到那些以往评分与肯恩的评分最相关的用户。如果他们对《地心引力》评分很高，那么可能肯恩的评分也会很高，你就可以把这部电影推荐给他。但是，如果对于《地心引力》他们有不同的看法，你就需要一个回退点，在这种情况下就要根据用户与肯恩关系的密切程度来进行排名。因此，如果李和肯恩的关系比梅格和肯恩的关系密切，那么相应李的评分也会更有价值。肯恩的预测评价就是与其相关的人的加权平均值，每个人的权值就是他与肯恩关系的系数。
虽然如此，但还是有一个有趣的转变。假设李和肯恩有非常相似的品位，但李比肯恩脾气暴躁。当肯恩给5颗星时，李会给3颗星；当肯恩给3颗星时，李会给1颗星，以此类推。我们想用李的评分来预测肯恩的评分，但如果我们直接预测，会总差2颗星。我们要做的就是，在知道李的评分值的基础上，预测肯恩的排名超过或者低于平均值的量。而现在，既然当李总是比他的平均值高出2颗星时，肯恩也会比他的平均值高出两颗星，我们的预测就会准确。
顺便说一下，你不需要显性评分来进行协同过滤。如果肯恩在网飞上预订了一部电影，意味着他可能会喜欢它。这样“评分”也才有可能被预订或未被预订，而两个用户如果预订了很多一样的电影，那么他们品位就会相似。即便只是暗暗点击某个东西，也会代表你对它感兴趣。最近邻算法和以上提到的都会有效。目前，所有种类的算法都被用于为用户推荐项目，但加权k最近邻算法是第一个受到广泛运用的算法，而且要打败它仍然很困难。
推荐系统，亦如其名，是大业务：亚马逊1/3的业务来自它为用户推荐的商品，网飞3/4的业务也是如此。它与最初的最近邻算法相差很大，因为它的记忆需求，人们觉得它不够实用。回到那时，计算机的存储器是用铁圈做成的，每个比特一个铁圈，甚至储存几千个例子都很费力。时代改变得多快！虽然如此，不必如此智能，以记住所有你见过的例子，然后搜索这些例子，因为多数例子可能并不相关。如果你回头看Posistan和Negaland的地图，你可能会注意到，如果Positiville消失，不会有任何变化。附近城市的城域会扩张至以往被Positiville占用的土地，但因为它们都是Posistan的城市，与Negaland的边界还是会一样。真正重要的是横跨边界、与对方国家的城市相交的城市，其他所有的城市都可以忽略。因此，使最近邻算法更加有效的简单方法，就是删除所有被它们的近邻准确分类的例子。这个技巧加上其他技巧可以使最近邻算法得以应用于一些让人意外的领域，例如，实时操控机器人的手臂。但不用说，它们仍然不是诸如高频交易之类事务的第一选择，因为在这些领域中，计算机会在一秒钟内买卖股票。在它与神经网络的竞争中，因为神经网络可以应用于仅含固定数量的加法、乘法、sigmoids函数的例子中，还可应用于需要为例子的最近邻搜索庞大数据库的算法中，因此神经网络肯定会获胜。
研究人员最初之所以对最近邻算法持怀疑态度，是因为它不确定能否找到两个概念之间的真正边界。但1967年，汤姆·科韦尔和彼得·哈特证明，在给定足够数据的情况下，最近邻算法最糟糕时易于出错的概率也仅仅是最佳可行分类器的两倍。举个例子，如果因为数据中的干扰因素，有至少1%的测试例子不可避免地被错误分类，那么最近邻算法保证误差率最多在2%左右。这是一个重大的启示。直到那时，所有已知的分类器都假定边界会有一种非常明确的形式，直线就是典型例子。这是一把双刃剑：一方面，它使准确性的证明成为可能，正如在感知器的例子中那样；另一方面，这也意味着分类器受到它所能掌握东西的严格限制。最近邻算法是史上第一个能够利用不限数量的数据来掌握任意复杂概念的算法。没人能指望它能找到在超空间中、由数百万个例子形成的边界，但因为科韦尔和哈特的证明，我们知道，它们可能不会错得太离谱。据雷·库兹韦尔的观点，当我们无法理解计算机在做什么时，单一性开始产生。依据该标准，说它已经在筹备当中也不稀奇——1951年就已经开始了，当时菲克斯和霍奇斯发明最近邻算法，这个微小的算法就能做到。
维数灾难
在这个伊甸园中当然也有一条蛇，它被称为“维数灾难”。虽然它对所有学习算法都会有或多或少的影响，但它对最近邻算法的危害尤其大。在低维度条件下（比如二维或者三维），最近邻算法通常能很好地起到作用。随着维数的上升，事情就会很快陷入崩溃状态。当今算法要掌握数千甚至数百万个属性并不稀奇。对于电子商务网站来说，它要掌握你的喜好，那么你每点击一下鼠标就算一种属性。网页上的每个词、图片上的每个像素也是如此。即使只有数十或者数百个属性，最近邻算法也有可能已陷入困境。第一个问题就是多数属性是不相关的：关于肯恩你可能知道100万个事实，但很有可能只有几个事实与他得肺癌的风险有关。虽然知道他是否吸烟对于做出该预测很关键，但是也可能对知道他是否喜欢看《地心引力》用处不大。举个例子，符号学派的方法很擅长处理非相关属性：如果该属性不含任何关于等级的信息，那么它就不包含在决策树或者规则集当中。但让人感到无望的是，最近邻算法会受到非相关属性的迷惑，因为这些属性都能够促成例子之间的相似性。有了足够的相关属性，不相关维度中的偶然相似性会清除重要维度中有意义的相似性，而最近邻算法和随意猜测相比也好不到哪里。
让人感到意外的是，有一个更棘手的问题：拥有更多的属性可能也会有害，即使这些属性是相关的。你可能会想，终归信息越多越好。这不是我们这个时代的口号吗？但随着维数的上升，用于确定概念边界的训练样本的数量也会呈指数上升。如果有20个布尔属性，就会有近100万个可能不一样的例子。如果有21个布尔属性，就会有200万个例子，而边界也会有相应数量的方式来定义这些属性。每个额外的属性都会把学习问题的困难程度加倍，而这也只是有布尔属性的情况。如果属性包含很多信息，添加该属性带来的好处可能会多于损失。如果你有的只是能提供很少信息的属性，比如邮件中的词语或者图片中的像素，那么你可能会遇到麻烦，即使这些属性集中在一起组成的信息足以预测你想要的是什么。
情况会变得更糟糕。最近邻算法的基础是找到相似物体，而在高维度情况下，相似性的概念就会无效。超空间就像过渡区域。在三维空间里的直觉不再适用，怪异离奇的事开始发生。想想一个橘子：一层薄薄的外壳包裹着好吃的果肉。比如橘子90%的半径是果肉，剩下的10%则是果壳，这意味着橘子73%的体积是果肉（0.93）。现在想象一个超级橘子：90%的半径还是果肉，但它在100个维度的空间中。那么果肉的体积已经缩小到超级橘子体积（0.9100）的1/3000。这个超级橘子全都是皮，而并且你绝对无法将其剥开。
另外一个让人不安的例子就发生在我们的老朋友身上——正态分布，又名钟形曲线。正态分布认为，数据本质上就落在一个点上（正态分布的平均值），但其周围也会有模糊的东西（由标准差给出）。对吗？在超空间中不是这样的。在高维度正态分布中，你比较有可能得到远离而不是接近平均值的样本。超空间中的钟形曲线看起来更像甜甜圈，而不像钟。当最近邻算法走进这个颠倒的世界时，它会变得非常困惑。所有的例子看起来都一样，同时因为它们距离彼此太远，无法做出有用的预测。如果你将例子统一地随意分布在高维度的立方体中，大部分例子会更接近立方体的一个面，而不是接近它们的最近邻。在中世纪的地图中，未涉足领域会被标上“龙”、“海蛇”等其他虚构出的生物，或者只标上“此处有怪物”的短语。在超空间中，龙无处不在，你的前门也会有。如果尝试走到你隔壁邻居家，那你永远也到不了那里；你会永远迷失在陌生的陆地上，在这里，所有熟悉的东西都消失不见。
决策树也无法幸免于维数灾难。举个例子，你打算学习的概念是一个球体：球内的点是正的，球外的点是负的。通过放在球体内正合适的最小立方体，决策树可以估算球体的体积。这不是完美的方法，但也不会太差：只有立方体的角才会被误分类。但在高维度空间中，超级立方体几乎所有的体积都会出现在超球面外。对于你准确将其标注为正的例子，你会错误地将许多负的例子分类为正，这会让你的准确率骤然下降。
实际上，没有哪种算法能够幸免于维数灾难。这是机器学习中，继过拟合之后，第二个最糟糕的问题。“维数灾难”这个术语由理查德·贝尔曼在50岁时提出的，他是一位控制论理论家。他观察到，控制算法在三维空间中可以起到很好的作用，但在高维度空间中则变得效率极低。例如，当你想控制机器人手臂中的每个节点或者化工厂的把手时，这种情况就会出现。但在机器学习中，问题不仅仅在于计算成本——随着维数上升，变得越来越困难的是学习本身。
然而，并不是所有东西都丢失了。我们能做的第一件事就是摆脱不相关维度。决策树会自行做好这一点，方法就是计算每种属性的信息增益，然后只使用最能提供信息的属性。对于最近邻算法来说，我们可以完成类似的事情，方法就是首先丢弃所有那些信息增益低于阈值的属性，然后只在简化的空间中测量相似性。这对于一些应用来说足够快、足够好，但不幸的是，这种方法会阻碍许多概念的学习，像XOR逻辑那样：如果当与其他属性结合时，一个属性只描述了有关类别的一些点，而不是关于自己本身，那么它就会被淘汰。一个代价更大但也更智能的选择，就是围绕学习算法来选择属性，并进行爬山算法研究，该研究会不断删除属性，只要不会降低最近邻算法留存数据的准确度。牛顿也进行过许多次的属性选择，当时他确定要预测物体的轨迹，最重要的就是要知道它的质量——不是颜色、气味、年龄，或者无数其他的属性。实际上，方程式最重要的东西，就是未在方程式中出现的所有数量：一旦我们知道这些要点是什么，要弄清楚这些要点如何相互依赖，就变得更加容易了。
要处理弱相关的属性，一个选择就是掌握属性权值。我们不会让所有维度下相似性的重要性相等，而是“缩减”不那么相关的属性。假设训练例子是房间中的点，那么高度尺寸对于我们的目标就没那么重要了。抛弃这一点会将所有例子投到地板上。调低高度尺寸又更像给屋子加了一层更低的天花板。当计算某点到其他点的距离时，该点的高度仍有价值，但没有它的水平位置那么重要。和机器学习中的许多事情一样，我们可以通过梯度下降来掌握属性权值。
一间屋子可能会有很高的天花板，但数据点都会在地板附近，就像一层薄薄的灰尘落在地板上。在这种情况下，我们是幸运的：这个问题看起来似乎和三维有关，其实它更接近二维。不必缩减高度，因为自然已经为我们缩减了。这个非一致性往往能够挽救局面，通过这一点数据在（超）空间中就可以均匀分布了。例子可能会有1000种属性，但实际上，它们都“生存”在维度低很多的空间中。这使最近邻算法有助于识别手写体数字，例如，每个像素都是一个维度，因此会有很多维度，但在所有可能的图片中只有一小部分是数字，所有图片都一起待在超空间小小的舒适角落里。但是，数据“生存”的低维度空间可能会反复无常。例如，如果一间房有家具，灰尘就不会落在地板上，而会落在桌面、椅面、床罩、古董架上。如果我们能弄明白灰尘覆盖地板的大致形状，那么我们需要的就是地板上每个点的坐标。在第八章中，我们会看到机器学习中会有整个分支致力于（可以这么说）在超空间的黑暗中摸索，以找到地板的形状。
空中蛇灾
直到20世纪90年代，应用范围最广的类比学习算法就是最近邻算法，但后来被来自其他学派更引人注目的“表亲”夺去光芒。当时一种新的以相似性为基础的算法横空出世了，横扫之前的所有算法。实际上，你可以说它是自冷战结束以来的另一个“和平红利”。它就是支持向量机（Support vector machines，SVM），是弗拉基米尔·万普尼克（一位苏联频率论研究者）的创意。万普尼克的大半生都在莫斯科的控制科学研究所度过，1990年，随着苏联走向解体，他移居美国，在那里他加入传说中的贝尔实验室。虽然在苏联，万普尼克很多时候都满足于从事理论、纸笔工作，但在贝尔实验室的氛围则不一样。研究人员正在寻找实践结果，而万普尼克最终决定将其想法变成算法。在几年时间内，他和贝尔实验室的同事已经研发出支持向量机。不久之后，支持向量机就变得无所不在，并创下不同的准确度纪录。
表面上看，支持向量机看起来很像加权k最近邻算法：正类别与负类别之间的边界由一组例子、其权值加上相似性测度来确定。测试实例会归入正类别，条件是从平均水平上看，它看起来更像正面例子而不是负面例子。平均数会被加权，而支持向量机只会记住那些用于确定边界的关键例子。如果你回头看Posistan和Negaland的例子，一旦我们丢掉那些不在边界上的城市，剩下的就是这张地图（见图7–3）。
这些例子被称为支持向量，因为它们是“支撑”边界的向量：移动一个向量，边界的一段就会滑向其他不同的地方。你也许还会注意到，边界就是一条锯齿状的线，实例的确切位置会决定突然出现的拐角。真实的概念趋向于拥有更加平缓的边界，这意味着最近邻算法的估算可能不理想。但有了支持向量机，我们就可以掌握平缓的边界，看起来更像图7–4。
图7–3
图7–4
为了学习支持向量机，我们需要选择向量和它们的权值。相似性度量，在支持向量机领地被称为“核心程序”，通常被归为先验性。万普尼克的一个重要观点就是，并不是所有将正面训练例子从负面训练例子分离出来的边界都是平等的。假设Posistan和Negaland发生战争，它们之间隔着无人区，两边都是布雷区。你的任务就是调查无人区，从无人区的这头走到那头，不能踩到任何地雷。幸运的是，你有一张地图，告诉你地雷都埋在哪里。显然，你不会走旧路线：你会假设地雷可能在的位置很宽阔。这就是支持向量机所做的事，实例相当于地雷，要掌握的边界相当于选择的路线。边界距离实例最近的地方就是它的安全边际，支持向量机选择支持向量和权值，这些向量和权值能够产生可能的最大边际。例如，图7–5中的实线边界比虚线要好。
图7–5
虚线边界能够较好地将正面例子和负面例子分离，但很危险的是，它差点接触到A处和B处的地雷。这些例子都是支持向量：删除其中的一个，最大边际边界就会移到不同的地方。通常，边界当然也可能是弯曲的，这使得边界更加难以想象，但我们可以将边界想象成爬向无人区的蛇，边际表示这条蛇可能有多肥。如果很肥的蛇能够一直蜿蜒爬行而不会被地雷炸得粉碎，那么支持向量机就可以很好地将正面例子和负面例子分离。万普尼克表明，在这种情况下，我们可以确信，支持向量机不会过拟合。直观地说，和一条瘦的蛇相比，肥的蛇能够不触雷爬行的方法更少。同样，和低边际的支持向量机相比，高边际的就不太可能因为画了一条过于复杂的边界而过拟合。
事情的第二部分就是支持向量机如何找到最合适的蛇，刚好夹在正面雷区和负面雷区之间。乍一看，通过梯度下降，为每个训练实例掌握权值可能会成功。我们要做的，就是找到能够将边际最大化的权值，而那些最终结果为0权值的例子则被抛弃。不幸的是，这样做只会让权值不受限制地增长，因为从数学的角度讲，权值越大，边际越大。如果距离地雷只有1英尺，然后你将所有东西的尺寸都扩大一倍，包括你自己，你现在距离雷区有2英尺，但这样并不会降低你踩到地雷的可能性。相反，我们得在限制范围内将边际最大化，该范围内，权值智能增长到某个固定值。或者，同样的效果，我们可以在限制范围内将权值最小化，该范围内所有例子都会有一个给定的边际，该边际有可能是1——确切来说是任意的。这就是通常支持向量机做的事情。
约束优化是在将受限函数最大化或者最小化时遇到的问题。宇宙会最大化熵，而熵遵守能量守恒定律。这类问题在商业和技术领域会经常碰到。例如，我们可能会想把工厂生产的小部件数量最大化，这个部件的数量可由机床的数量、小部件的规格等决定。有了支持向量机，约束优化对机器学习来说也会变得重要。无约束优化正在登上顶峰，而这就是梯度下降（或者，在本例子中为上升）要做的事情。约束优化就是当你停在公路上时，尽可能往高处走。如果公路延伸到顶峰，约束及无约束问题的解决方法就会一样。即便如此，更多时候，公路弯弯曲曲围绕着山峰，接着还没到山顶就绕回来了。你知道自己已经到达公路的最高点，因为在不脱离公路的情况下，你已经无法开到更高的地方。换句话说，也就是到达顶点的路线与公路成直角。如果公路和到达顶点的路线形成斜角，那么沿着公路开远些，你总能到达更高点，即使那样做与直线到达峰顶相比，并不会那么快。因此，解决约束优化问题的方法，不是沿着坡面走，而是走与约束面平行的那部分坡面（在该例子中为公路），然后当该部分为零时，停下来。
通常，我们得一次性处理许多个约束条件（在支持向量机的情况下，每个条件对应一个例子）。想象一下，你想尽可能地靠近北极，但你不想离开自己的房间。每间房的四面墙就是一个限制条件，而解决办法就是要跟着指南针直到你碰到一个角落，这个角落是东北部和西北部两面墙的汇合点。我们说这两堵墙是有效约束条件，因为它们阻止你实现最佳效果，也就是北极。如果你的房间有一堵墙的外部直面北部，那么这就是唯一的有效约束条件，而解决方法就在于这堵墙中间的一个点。如果你是圣诞老人，而你的房间已经处在北极上方，而所有的约束条件都无效，那么你就可以在那儿坐等，仔细考虑玩具的最优分配问题（旅行推销员更容易将其与圣诞老人比较）。在支持向量机中，有效约束条件就是支持向量，因为它们的边际已经是经允许达到的最小值，移动边界会违背一个或多个限制条件。所有其他的例子都不相关，而且它们的权值都是零。
在现实中，我们通常会让支持向量机违背一些限制条件，这就意味着将一些例子错误分类，或者利用更少的边际，否则它们就会过拟合。如果在正面区域中间的某个地方有干扰作用的负面例子，那么我们不想让边界在正面区域周围环绕，目的只是为了让例子正确。但支持向量机会因为它弄错的每个例子而受到惩罚，这样就会促使它把错误例子降到最低。支持向量机就像《沙丘》中的沙虫：大而强韧，可以在爬过雷区时幸免于几次但不是很多次爆炸。
四处寻找应用的同时，万普尼克和他的同事很快偶然发现了手写体数字识别，他们在贝尔实验室的联结学派同事就是研究这个方面的专家。让所有人惊讶的是，支持向量机和感知器一样，在其他领域也能很好地工作，感知器多年来已经被精心设计用于数字识别。这为两者持续时间长、波及范围广的竞争奠定了基础。支持向量机可以当作感知器的一个概括版，因为当你利用某个特定的相似性度量时，得到的就是类别之间的超平面边界（向量之间的点积）。但和多层感知器相比，支持向量机有一个重要优势：权值有单个最优条件而不是多个局部最优条件，因此可靠地掌握它们变得简单多了。虽然如此，支持向量机的表现力依旧不比感知器差。支持向量有效地扮演隐藏层的角色，而它们的加权平均值则起到输出层的作用。例如，一台支持向量机可以轻易表示XOR函数，方法就是为4个可能的配置分配一个支持向量，但不较量一下，那些联结主义学者便不会罢休。1995年，拉里·杰克尔（贝尔实验室万普尼克所在部门的主任）和他赌一顿丰盛的大餐——到2000年，神经网络就会和支持向量机一样好理解。他输了，但作为回报，万普尼克打赌——到2005年就没有人会使用神经网络，后来他也输了（唯一吃到免费大餐的是燕乐存，他们的见证人）。另外，随着深度学习的出现，联结学派已经重新占据优势。只要你能掌握它们，含有多层的网络可以比支持向量机用更加简洁的方式来表达许多函数，而支持向量机一直以来只有一层，这一点就使两者大不相同。
支持向量机早期较大的功绩还在于文本分类，后来证明这是一项大实惠，因为网站那时候才人气渐增。当时，朴素贝叶斯是最先进的文本分类器，但当语言中的每个词都代表一个维度时，甚至它也开始过拟合了。它需要的只是一个词，这个词会偶然出现在训练数据中所有与体育相关（举个例子）的页面中，而不是出现在其他页面中，而朴素贝叶斯开始出现幻觉，以为只要包含该词的页面都是体育页面。但多亏了边际最大化，支持向量机即使在很高的维度中也可以抵抗过拟合。
通常，支持向量机选择的支持向量越少，就能更好地进行概括。任何不是支持向量的训练例子可能会被正确分类，条件是它显示为测试实例，因为正面和负面例子之间的边界仍在同样的地方。因此预测支持向量机的误差率，最多就是支持向量的那部分例子。随着维数的上升，这部分也会上升，因此支持向量机无法幸免于维数灾难，但它们最能抵抗这个灾难。
除了实践中的功绩，支持向量机还完全改变了许多机器学习中的传统观点。例如，它揭穿了“模型越简单就越准确”这个谎言，有时候，这个观点会被误以为是奥卡姆剃刀理论。相反，支持向量机可能有无限数量的参数，而且只要它有足够大的边际，就不会过拟合。
然而，支持向量机唯一最让人吃惊的属性就是，无论它形成多么弯曲的边界，那些边界也总是直线（或者一般为超平面）。这并不矛盾，因为直线存在于不同的空间中。假设例子停在（x, y）的平面上，而正面和负面区域之间的边界是抛物线y=x2。没有什么方法能用直线来表示它，但如果我们添加坐标z，意味着现在数据存在于（x, y, z）空间，然后我们设定每个例子的z坐标为它的x坐标的平方，这时边界就是由y=z定义的斜平面。实际上，当数据点上升至三维空间时，有些数据点上升的数量正合适，但比其他数据点上升的要多，而急板（presto）在这个新维度中，正面例子和负面例子可能会被一个平面分开。原来，我们可以把支持向量机利用核心程序、支持向量、权值来做的事情，看作将数据映射到更高维数的空间中，并在那个空间找到最大边际超平面。对于一些核心程序来说，衍生空间有无限的维数，但支持向量机完全不会因此而受到困扰。超空间可能是过渡区域，但支持向量机已经弄明白如何操纵它。
爬上梯子
两个东西如果在一些方面意见一致，那么它们就是相似的。如果它们在一些方面意见一致，可能在其他方面也会意见一致，这就是类比的本质。它还表明了类比推理中的两大子问题：弄明白两个事物的相似度，确定由它们的相似度还能推导出什么。到目前为止，我们已经探索了类比“低功耗”的一端，包含诸如最近邻和支持向量机之类的算法，在这种情况下，这些问题的答案都非常简单。它们的应用最为广泛，但只用一章来介绍类比学习并不完整，因为至少得浏览该领域更为强大的部分。
在任何类比学习算法中，最重要的问题就是如何度量相似性。它可以如数据点之间的欧几里得距离那么简单，也可以和含有多水平子程序的一整套程序那么复杂，而且这些子程序的最终产出是相似度值。不管怎样，相似度函数控制的是学习算法如何从已知例子归纳出新的例子。我们将自己对问题域所了解的东西插入学习算法中，这就变成类推学派对于休谟问题的回答。我们可以将类比学习应用到所有种类的物体中，而不仅仅是属性向量，只要我们有度量它们之间相似度的方法。例如，我们可以通过两个分子之间包含相同子结构的数量，来测量两个分子的相似度。甲烷和甲醇相似，因为它们都有三个碳氢键，而不同点仅在于一个氢原子代替了一个羟基（见图7–6）。
图7–6
然而，这并不意味着它们之间的化学行为是相似的。甲烷是气体，而甲醇是酒精。类比推理的第二部分，就是弄明白在已经发现的相似点的基础上，如何推导出新的东西。这可以很简单，也可以很复杂。在最近邻算法或者支持向量机中，这点包括在最近邻算法或者支持向量类别的基础上，预测新东西的类别。但在案例推理（类比学习的另外一种类型）中，输出的可能是由检索对象组成部分形成的复杂结构。假设你的惠普打印机吐出没用的东西，你会打电话给求助台。他们之前很有可能已经遇到过很多次你这样的问题，所以好办法就是找到那些记录，然后从这些记录中找到可能解决你的问题的方法。这不只是找到与你的问题有许多相似之处的投诉那么简单：例如，和你的打印机一起使用的是Windows系统，还是Mac OS X？这可能会引起系统的不同设置，打印机也会变得相关。一旦你找到最相关的例子，解决你的问题所需步骤的顺序，可能是不同案例中不同步骤的组合，可能还会针对你的问题进一步微调。
求助台是当今案例推理最受欢迎的应用。多数求助台仍采用人力中介，但正畸诊疗软件IPsoft的虚拟求助台员工伊丽莎则与顾客直接对话。伊丽莎配有交互式视频人物角色，迄今已经为2000多万的顾客解决问题，这些问题大部分来自一流的美国公司。“来自机器人王国（Robotistan）的问候，外包最实惠的新选择”是近来外包博客对它的评价。而且，正如外包在不断爬技能这架梯子，类比学习也是如此。第一个以判例为基础、为指定判决辩论的机器人律师已经诞生。这样的系统能够准确预测超过90%经其审核的商业秘密案件。也许在未来的网络法院中，亚马逊云服务上的某处，在开庭期间，机器人律师会推翻机械战警给你的无人驾驶汽车开出的罚单，当你走到沙滩上时，莱布尼茨将所有辩论简化为计算的梦想最终会实现。
可以说，站在技能这架梯子更高处的是音乐创作。大卫·科普是加州大学圣克鲁斯分校的名誉教授，他设计出一种算法，能够通过选择并重组著名作曲家作品中的一些片段，创造出带有这些作曲家风格的新的音乐。我在几年前参加过的一个会议上，他演奏了“莫扎特”的三个片段：一段来自真正的莫扎特，一段出自人类作曲家模仿的莫扎特，一段来自他自己的系统。然后他让听众为真正的莫扎特投票。沃尔夫冈胜出了，但计算机打败了人类模仿者。这是一场人工智能会议，听众们感到非常喜悦。在其他项目中则没有那么开心了，一位听众愤怒地控诉科普，说他毁掉了他的音乐。如果科普是对的，创造性（最深不可测的东西）都可以归结为类比和重组。你可以通过谷歌搜索“david cope mp3”来自行判断。
然而，类比学者最棒的技巧在于跨越问题域来进行学习。人类一直在做这件事情，比如一位高管可以从一家媒体公司跳槽到另一家消费品公司，而不用从零开始，因为许多相同的管理技能仍然适用。华尔街雇用很多物理学家，因为物理和金融问题虽然表面上看区别很大，却往往包含相似的数学结构。然而，假如我们对目前为止见过的学习算法进行训练，让它们预测布朗运动，然后对股市进行预测，那么这些算法将无法达到预期效果。股票价格和悬浮在液体中的粒子的速度只是不同的变量，所以学习算法甚至不知道从何开始。但利用构造映射，类比学者可以完成这件事，这是戴德瑞·根特纳（西北大学的一位心理学家）发明出的算法。结构映射采用两种描述方法，发现了它们某些部分和关系的一致对应关系，然后基于这种对应关系，进一步将一个结构中的属性转移到另一个结构中。例如，如果是太阳系和原子的结构，我们可以将行星映射为电子，将太阳映射为原子核，并和玻尔一样得出结论，认为电子围绕原子核旋转。当然，真理会更加微妙，而往往我们做出类比之后，又得重新定义它们。但能像这样从单个例子中学习，当然是通用学习算法的一个关键属性。当我们与一种新的癌症做斗争时，这样的事一直在发生，因为癌症会不断变异，我们为之前的算法掌握的模型将不再适用。我们也没有时间从大量病人中收集关于新型癌症的数据，也许只有一个病人，而他也需要救治。那么我们最大的希望就是，将新型癌症与已知癌症进行对比，然后努力找到另外一种癌症，它与此种癌症的行为足够相似，那么一些相同的疗法就会起作用。
有类比无法做到的事吗？道格拉斯·霍夫斯泰特认为没有，他是一位认知科学家，还是《哥德尔、艾舍尔、巴赫：集异璧之大成》的作者。霍夫斯泰特看起来有点像格林奇的双胞胎兄弟，可能是世界上最著名的类比学者了。在《表面与本质：类比作为思维的燃料和火焰》一书中，霍夫斯泰特和他的合作者伊曼纽尔·桑德尔激烈地争论，认为所有智能行为都可以归结为类比。我们学习或者发现的每样东西，从日常词语如“妈妈”和“玩耍”的含义，到诸如阿尔伯特·爱因斯坦、埃瓦里斯特·伽罗瓦这些天才惊人的洞察力，这些都是类比应用于实践中的结果。当小蒂姆看到妇女像他妈妈照顾他一样照顾其他孩子时，它概括了“妈妈”的概念来指其他人的妈妈，而不只他的妈妈。这反过来又是一个跳板，用来理解诸如“母舰”和“大自然”等东西。爱因斯坦的“最快乐思想”（该思想还衍生了广义相对论），就是重力与加速度之间的类比：如果你是一台升降机，你无法判断你的重量是因为这个还是那个而产生，因为它们的效果是一样的。我们在类比的广阔海洋里遨游，我们自己会操纵，但无意间也会被操纵。书中的每页都会包含类比（比如本节的标题，或者前一节的标题）。《哥德尔、艾舍尔、巴赫》是哥德尔定理、艾舍尔艺术、巴赫音乐的一个延伸类比。如果终极算法不是类比，那么它肯定就是和类比相似的东西。
起床啦
认知科学见证了符号学派与类推学派之间很长一段时间的争论。符号学派指向他们能够模仿但类推学派无法模仿的东西；接着类推学派弄明白如何做到这一点，然后想出他们能够模仿但符号学派无法模仿的东西，这个循环一直重复下去。基于实例的学习——有时人们这样称呼它，应该更有利于模仿我们如何记住生活中的特定片段；规则是包含抽象概念（如“工作”“爱”）推理的假定选择。但我在读研究生时，觉得这两者真的只是连续区间中的点，而我们应该能够掌握它的所有方面。实际上，规则就是概括的实例，这种情况下我们已经“忘记”一些属性，因为它们并不重要。相反，实例则是非常特殊的规则，每种属性都会有一个条件。在我们的一生中，相似的片段会渐渐被抽象成基于规则的结构，比如“在餐馆吃饭”。你知道去餐馆会涉及从菜单里点菜和给小费，而每次你出去吃饭的时候，都会遵守这些“行为准则”，但你可能不记得自己意识到这些准则时的第一家餐厅。
在博士论文中，我设计了一种算法，以这种方式来将基于实例的学习和基于规则的学习结合起来。一条规则不会只和满足它所有先决条件的实体匹配，与任何其他规则比，它会与其更加相似的实体匹配。在这个意义上讲，它会更接近于满足它的条件。例如，胆固醇浓度为220毫克/分升的人，会比浓度为200毫克/分升的人更加符合以下规则：如果胆固醇浓度超过240毫克/分升，你会有心脏病发作的风险。RISE是我称呼该算法的名字，通过以每个训练实例作为开始来学习，然后渐渐概括每个例子，以吸收最近的例子。最终的结果通常是通则的结合，这些通则会在它们之间和多数例子匹配，越来越多的特殊规则用来将例外规则与那些规则匹配，直到到达特定记忆的“长尾”上。RISE比当时最好的规则和实例学习算法预测得还要准确，而我的实验也表明，准确地说，这是因为它结合了两者的最佳特征。规则可以类推地进行匹配，所以它们不会再那么脆弱。实例可以选择空间中不同区域的不同特点，然后比最近邻算法更能与维数灾难相抗衡，而最近邻算法只能到处选择相同的特征。
RISE是通往终极算法的一个步骤，因为它将符号与类比学习结合起来了。然而这只是小小的一步，因为它不具备这两个范式的全部能力，仍缺少其他三个范式的能力。RISE的规则无法以不同的方式连接起来，每个规则只能直接从其属性中预测例子的类别。另外，这些规则无法一次讨论一个以上的实体；例如，RISE无法表达这样的规则：如果A得了感冒，而B与A有接触，那么B也可能会得感冒。在类比这边，RISE仅仅概括了简单的最近邻算法，它无法利用结构映射或者某个这样的策略来进行跨域学习。在完成博士论文时，我找不到能够为一种算法带来所有5个范式能力的方法，然后我把这个问题丢在一边一段时间。但当我把机器学习应用到诸如口碑营销、数据集成、事例编程、网站个性化等问题中时，我不断发现，每个这样的范式只提供了一部分解决办法。我相信应该有更好的方法。
至此，我们已完成了对5个学派的介绍，同时集中了他们的观点、议定它们的界限、探索了这些碎片如何拼凑在一起。我们现在知道的东西比一开始多得多，但还有一些东西没有找到。在这个谜题的中心有一个很大的漏洞，使人难以看到其模式。问题在于，目前为止，我们见过的所有学习算法，需要一位老师来告诉它们正确答案。它们不会从健康细胞中区分出癌细胞，除非有人将这些细胞标记为“癌细胞”或者“健康细胞”。人类会无师自通，从出生那天开始，就已经这么做了。正如《指环王》中站在魔多大门的弗罗多那样，如果无法在这个障碍附近找到出路，那么我们的长途旅行将毫无意义。有一条路可以穿越壁垒和层层守卫，胜利越来越近。跟我来……