人工智能时代：破解人机共存密码（套装共10册）

懒惰学习算法会胜出的原因在于，和构建全局模型（例如，决策树）相比，只要每次弄明白指定的点在哪里会较为简单。想象一下，利用决策树来尝试确定什么是脸。你可以说，脸有两只眼睛、一个鼻子和一张嘴，但什么是眼睛，而你在一张图片中怎样才能找到它呢？如果人的眼睛是闭上的，那又会怎样呢？准确定义一张脸，细到每个像素，这是十分困难的，在表情、姿态、背景、光线条件各异的情况下尤甚。而最近邻算法则走捷径：如果数据库中与简上传的最相似的那张照片是脸部照片，那么简的照片也是。要出现这种情况，数据库就得有一张照片，与新照片足够相似，因此，数据库越大越好。对于一个简单的二维问题，比如猜出两个国家的边界，一个小数据库就足够了。对于一个很难的问题来说，如识别脸部，因为每个像素的颜色都是变化的一个维度，所以需要巨大的数据库。目前我们有这些数据库。但对于渴望学习的算法来说，要从这些数据库中学习东西可能代价很大，因为这种算法要明确划分脸部和非脸部的界线。然而，对于最近邻算法来说，界线隐含在数据点和距离度量中，而唯一要付出的就是查询时间。

构建局部模型而非全局模型的相同想法可以应用于分类之外的用途。通常科学家们利用线性回归来预测连续变量，但大多数现象是非线性的。幸运的是，从局部来看，它们是线性的，因为平滑曲线可以局部近似为直线。因此如果你只用直线来对查询点附近的点，而不是尝试对所有的数据都进行拟合，那么你现在就能拥有一个非常强大的非线性回归算法。懒惰也会有回报。如果肯尼迪需要一套完整的国际关系理论来决定该如何应对苏联在古巴部署的导弹，他可能会遇到麻烦。相反，他从这个危机与第一次世界大战的爆发之间找到相似点，而这个相似点指引他做了正确的决定。

最近邻算法可以用来救命，正如史蒂芬·约翰逊在《幽灵地图》中描述的那样。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.9¹⁰⁰）的1/3000。这个超级橘子全都是皮，而并且你绝对无法将其剥开。

另外一个让人不安的例子就发生在我们的老朋友身上——正态分布，又名钟形曲线。正态分布认为，数据本质上就落在一个点上（正态分布的平均值），但其周围也会有模糊的东西（由标准差给出）。对吗？在超空间中不是这样的。在高维度正态分布中，你比较有可能得到远离而不是接近平均值的样本。超空间中的钟形曲线看起来更像甜甜圈，而不像钟。当最近邻算法走进这个颠倒的世界时，它会变得非常困惑。所有的例子看起来都一样，同时因为它们距离彼此太远，无法做出有用的预测。如果你将例子统一地随意分布在高维度的立方体中，大部分例子会更接近立方体的一个面，而不是接近它们的最近邻。在中世纪的地图中，未涉足领域会被标上“龙”、“海蛇”等其他虚构出的生物，或者只标上“此处有怪物”的短语。在超空间中，龙无处不在，你的前门也会有。如果尝试走到你隔壁邻居家，那你永远也到不了那里；你会永远迷失在陌生的陆地上，在这里，所有熟悉的东西都消失不见。

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

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

然而，并不是所有东西都丢失了。我们能做的第一件事就是摆脱不相关维度。决策树会自行做好这一点，方法就是计算每种属性的信息增益，然后只使用最能提供信息的属性。对于最近邻算法来说，我们可以完成类似的事情，方法就是首先丢弃所有那些信息增益低于阈值的属性，然后只在简化的空间中测量相似性。这对于一些应用来说足够快、足够好，但不幸的是，这种方法会阻碍许多概念的学习，像XOR逻辑那样：如果当与其他属性结合时，一个属性只描述了有关类别的一些点，而不是关于自己本身，那么它就会被淘汰。一个代价更大但也更智能的选择，就是围绕学习算法来选择属性，并进行爬山算法研究，该研究会不断删除属性，只要不会降低最近邻算法留存数据的准确度。牛顿也进行过许多次的属性选择，当时他确定要预测物体的轨迹，最重要的就是要知道它的质量——不是颜色、气味、年龄，或者无数其他的属性。实际上，方程式最重要的东西，就是未在方程式中出现的所有数量：一旦我们知道这些要点是什么，要弄清楚这些要点如何相互依赖，就变得更加容易了。

要处理弱相关的属性，一个选择就是掌握属性权值。我们不会让所有维度下相似性的重要性相等，而是“缩减”不那么相关的属性。假设训练例子是房间中的点，那么高度尺寸对于我们的目标就没那么重要了。抛弃这一点会将所有例子投到地板上。调低高度尺寸又更像给屋子加了一层更低的天花板。当计算某点到其他点的距离时，该点的高度仍有价值，但没有它的水平位置那么重要。和机器学习中的许多事情一样，我们可以通过梯度下降来掌握属性权值。

一间屋子可能会有很高的天花板，但数据点都会在地板附近，就像一层薄薄的灰尘落在地板上。在这种情况下，我们是幸运的：这个问题看起来似乎和三维有关，其实它更接近二维。不必缩减高度，因为自然已经为我们缩减了。这个非一致性往往能够挽救局面，通过这一点数据在（超）空间中就可以均匀分布了。例子可能会有1000种属性，但实际上，它们都“生存”在维度低很多的空间中。这使最近邻算法有助于识别手写体数字，例如，每个像素都是一个维度，因此会有很多维度，但在所有可能的图片中只有一小部分是数字，所有图片都一起待在超空间小小的舒适角落里。但是，数据“生存”的低维度空间可能会反复无常。例如，如果一间房有家具，灰尘就不会落在地板上，而会落在桌面、椅面、床罩、古董架上。如果我们能弄明白灰尘覆盖地板的大致形状，那么我们需要的就是地板上每个点的坐标。在第八章中，我们会看到机器学习中会有整个分支致力于（可以这么说）在超空间的黑暗中摸索，以找到地板的形状。

空中蛇灾

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

表面上看，支持向量机看起来很像加权k最近邻算法：正类别与负类别之间的边界由一组例子、其权值加上相似性测度来确定。测试实例会归入正类别，条件是从平均水平上看，它看起来更像正面例子而不是负面例子。平均数会被加权，而支持向量机只会记住那些用于确定边界的关键例子。如果你回头看Posistan和Negaland的例子，一旦我们丢掉那些不在边界上的城市，剩下的就是这张地图（见图7–3）。

这些例子被称为支持向量，因为它们是“支撑”边界的向量：移动一个向量，边界的一段就会滑向其他不同的地方。你也许还会注意到，边界就是一条锯齿状的线，实例的确切位置会决定突然出现的拐角。真实的概念趋向于拥有更加平缓的边界，这意味着最近邻算法的估算可能不理想。但有了支持向量机，我们就可以掌握平缓的边界，看起来更像图7–4。