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

前，信用卡是否完好。

我们可以像学习这条规则那样来同时学习多套规则，利用我们之前见过的算法来学习合取概念。我们学习每个规则之后，会排除该规则包含的正面例子，因此下一个规则会尽可能多地包含剩下的正面例子，以此类推，直到所有的例子都被包含在内。这是一个“分而治之”的例子，也是科学家的战术手册中最古老的策略。为了找到单个规则，我们也可以对算法进行改良，方法就是保留某数n的假设，不止一个数，然后在每个步骤中将这些数以所有可能的方法延伸开来，最后保留n的最佳结果。

通过该方法发现规则的创意来自理夏德·米哈尔斯基（RyszardMichalski），他是波兰的一位计算机科学家。米哈尔斯基的故乡——卡尔鲁兹之前曾属于波兰、俄罗斯、德国以及乌克兰，这让米哈尔斯基比多数人更能理解合取概念。1970年移民美国之后，他和汤姆·米切尔、杰米·卡博内尔一起创立了机器学习的符号学派。他个性傲慢，如果你在一场机器学习会议中做报告，那么很有可能他会举手指出你只是重新发现了他之前的旧观点。

零售商喜欢一套套的规则，因为他们要决定该囤什么货。通常，他们会用比“分而治之”更为彻底的方法，也就是寻找所有能够准确预测每个购买项的规则。沃尔玛在该领域属先驱，他们早期的发现之一就是，如果你买了纸尿片，那么很有可能会买啤酒。为什么？对此进行解释的说法之一就是，妈妈让爸爸去超市买纸尿片，出于情感补偿，爸爸买了一箱啤酒。知道这一点，超市现在会把啤酒放在纸尿片旁边，这样啤酒就会卖得更好。不找规律，这样的事就不会在沃尔玛发生。“啤酒和纸尿片”的规则已经在数据挖掘领域取得传奇式的地位（虽然会有人说，所谓的传奇和城市多样化有关）。不管怎样，这和米哈尔斯基想象的数字电路设计问题还差得很远。20世纪60年代，他开始考虑规则归纳问题。如果你发明了新的学习算法，你甚至无法想象这个算法能应用的所有地方。

我第一次直接体验规则学习，是在申请信用卡的时候。那时我刚来到美国，开始接受研究生教育，银行给我寄了一封信，说“很遗憾，您居住在该地址的时间还不足够长，所以无历史信用记录，你的申请被拒绝了”。就在那时，我知道在机器学习领域有待研究的东西还很多。

在无知与幻觉之间

规则集在很大程度上比合取概念要有力得多。实际上，规则的力量如此之大，大到你可以用规则来代表任何概念，要找到原因则很难。如果你给我某个概念的完整例子，我只能将每个例子变成一个规则。这个规则规定了每个例子的所有属性，而这些规则的集合就是该概念的定义。回到之前关于约会的例子，其中的一个规则是：现在是周末晚上，天气暖和，没有好看的电视节目，你提议去泡吧，她会说“没问题”。表3–1只包含了几个例子，但其实它有16种（2×2×2×2）可能，每个可能都会有“约”或者“不约”的结果，将每个正面例子以这样的方法变成规则，我们就成功了。

规则集的力量是一把双刃剑。从正面看，你知道自己总能找到和数据完美匹配的规则。但你还没来得及开始觉得走运，就意识到自己很有可能会找到一个毫无意义的规则。记住“天下没有免费的午餐”：没有知识，你就无法进行学习。假设某概念能通过规则集来定义，相当于什么也没有假设。

无用规则集的一个例子就是，只包含了你看到的正面例子，除此之外，没有其他的例子。这个规则集看起来100%准确，但那只是假象：它会预测每个新例子都是负面例子，然后把每个正面例子弄错。如果正面例子总体上比负面例子多，这种做法的效果会比抛硬币更糟糕。想象一下，邮件过滤器仅因为某封邮件和之前垃圾邮件一模一样就将其过滤，这样会有什么后果？对分类好的数据进行学习很容易，这样的数据看起来也很棒，但还不如没有垃圾邮件过滤器。很遗憾，我们“分而治之”的算法有可能就像那样对规则集进行简单的学习。

在《博闻强识的富内斯》的故事中，豪尔赫·路易斯·博尔赫斯讲述了和一位拥有完美记忆力的少年相遇的故事。拥有完美记忆力看起来非常幸运，但其实这是一个可怕的诅咒。富内斯能记住过去任意时刻天空中云朵的形状，但他没有办法理解，下午15:14看到的狗的侧面和下午15:15看到的狗的正面，都是同一条狗。每次他在镜子中看到自己的脸，都会感到惊讶不已。富内斯无法进行概括：对他来说，两个事物，只有每个细节看起来都一致，才能说它们是一样的。自由的规则算法和富内斯一样，发挥不了作用。学习就意味着将细节遗忘，只记住重要部分。计算机就是最大的白痴专家：它们可以毫无差错地将所有东西记住，但那不是我们想让它们做的。

问题不限于记忆大量例子。每当算法在数据中找到现实世界中不存在的模型时，我们说它与数据过于拟合。过拟合问题是机器学习中的中心问题。在所有主题中，关于过拟合问题的论文最多。每个强大的学习算法，无论是符号学算法、联结学算法，或者其他别的学习算法，都不得不担忧幻觉模式这个问题。避免幻觉模式唯一安全的方法，就是严格限制算法学习的内容，例如要求学习内容是一个简短的合取概念。很遗憾，这种做法就像把孩子和洗澡水一起倒掉一样，会让学习算法无法看到多数真实的模型，这些模型在数据中是可见的。因此，好的学习算法永远在无知与幻觉的夹缝中行走。

人类对过拟合也没有免疫。你甚至可以说，过拟合是我们的万恶之源。想想一个白人小女孩，在商场看到拉美裔婴儿时脱口而出“看，妈妈，那是小女佣”（真实例子）。小女孩并非生来就是偏执狂。那是因为在她短暂的人生阅历里，她对见过的仅仅几个拉美裔女佣进行了笼统的概括。这个世界有许多从事其他职业的拉美裔，但她还没有见过他们。我们的信仰建立在自己的经历之上，这会让我们对世界的理解不完整，而且也容易过早得出错误的结论。即便你很聪明，学识渊博，也无法免受过拟合的影响。亚里士多德说要使一个物体不断运动，需要对其施加一个力，就犯了过拟合的错误。伽利略的天才之处在于，无须到外太空亲眼见证，他凭直觉就知道，不受外力影响的物体会一直保持运动。

但学习算法特别容易过拟合，因为它们拥有从数据中发现模型、近乎无限制的能力。人类发现一个模型所用的时间，计算机可以找到数百万个。在机器学习中，计算机最大的优势（处理大量数据以及不知疲倦不断重复同样步骤的能力）也是它的劣质所在。如果你做的研究够多，然后能有所发现，也很不错。《圣经密码》（1998年的畅销书）声称如果你以固定间距跳过某些字母，然后把点中的字母拼起来，就会发现《圣经》对未来的预言。遗憾的是，保证你能从任何足够长的文本中找到“预言”，有很多方法。怀疑论者会说，他们在《白鲸记》和最高法院的裁决中找到了预言，除此之外，还提到罗斯威尔，以及《圣经·创世纪》中的不明飞行物。约翰·冯·诺依曼（计算机科学的奠基之父之一）曾说过一句众所周知的话：“用4个参数，我能拟合一头大象；用5个参数，我可以让它的鼻子扭动起来。”当今我们通常会学习拥有数百万参数的模型，这些参数足以让世界上的每头大象都扭动鼻子。甚至曾有人说过，数据挖掘意味着“折磨数据，直到数据妥协”。

过拟合问题因为嘈杂的声音被严重夸大。在机器学习中，这些噪声仅仅意味着数据中的误差，或者你无法预测的偶然事件。比如你的朋友在电视不好看的时候，真的想去泡吧，但你记错第三次约会的情况，并写着那天晚上的电视好看。如果你现在努力找出一套规则，为那天晚上破个例，这样你可能最终会得到一个糟糕的答案，比忽略那个晚上得出的结果还糟。或者比如你的朋友前一晚刚出去喝醉了，所以今晚想休息，但如果是平时，她会答应出去约会。除非你知道她宿醉了，为了得出本例子的正确结果而掌握一套规则，其实会适得其反：你最好将第三次约会情况“错误分类”，以得出否定回答。这种情况更糟：误差或偶然事件会让你无法找出整套规律。仔细看，你会发现第二次约会和第三次约会其实难以区别：它们都有相同的属性。如果你的朋友答应第二次邀请，而拒绝第三次邀请，那么就没有什么规则能让这两次预测都准确。

当你有过多假设，而没有足够的数据将这些假设区分开来时，过拟合问题就发生了。坏消息是，即便对最简单的合取概念算法来说，假设的数量也会随着属性的增多而呈指数级增长。指数级增长是一件恐怖的事。大肠杆菌每15分钟就能大致分裂成两个细菌，只要有足够的营养，它可以在大约一天时间内，生长出大量细菌，和地球一样大。当算法需要做的事情和输入的数据一样呈指数级增长时，计算机科学家就将这个现象称为组合爆炸，然后会四处奔走寻求保护。在机器学习中，一个概念可能实例的数量，是其属性数量的指数函数：如果属性是布尔值，每种新的属性可能会是实例数量的两倍，方法就是引用之前的每个实例，然后为了那个新属性，对该实例以“是”或“非”来进行扩展。反过来，可能概念的数量是可能实例数量的指数函数：既然每个概念都把实例分成正面或者负面，加入一个实例，可能的概念就会翻倍。因此，概念的数量就是属性数量的指数函数的一个指数函数！换句话说，机器学习就是组合爆炸的组合爆炸。也许我们该放弃，不要把时间浪费在这样没有希望的问题上。

幸运的是，在学习过程中，会发生一些事，把其中一个指数消除，只剩下一个“普通的”单一指数难解型问题。假设你有一个袋子，装满概念的定义，每个定义写在一张纸上，你随机取出纸片，然后看看这个概念和数据的匹配程度。和连续抛1000次硬币都是正面朝上的概率相比，一个不恰当的定义更没有可能让你的数据中所有1000个例子都准确无误。“一把椅子有四条腿，而且是红色的，或者有椅面但没有椅腿”可能会和某些例子匹配，但并不是和你看到的所有椅子都匹配，也可能会和其他一些事物相匹配，但并不是和所有其他事物都匹配。因此，如果一个随机定义准确匹配了1000个例子，那么这个概念不太有可能是错误的定义，或者至少它和正确的定义非常接近。而且如果一个定义和100万个例子相匹配，那么实际上它就是正确的定义。其他的定义怎么能使那么多例子准确无误？

当然，真正的学习算法不会只是从袋子里随机去除一个定义。这个算法会尝试所有定义，而且这些定义也不是随机选择的。算法尝试的定义越多，越有可能偶然得到能够和所有例子匹配的定义。如果你每组抛1000次硬币，然后重复100万组，实际上至少会有一组出现1000次硬币都是正面朝上的情况，而100万也仅仅是假设的一个小数目。例如，如果例子只有13个属性，那大概就是可能的合取概念的数目（注意你不需要明确地尝试一个又一个概念，如果你找到的最好的那个概念利用了合取概念学习算法，并且和所有的例子匹配，效果也是一样的）。

总结：学习就是你拥有的数据的数量和你所做假设数量之间的较量。更多的数据会呈指数级地减少能够成立的假设数量，但如果一开始就做很多假设，最后你可能还会留下一些无法成立的假设。一般来说，如果学习算法只做了一个指数数量的假设（例如，所有可能的合取概念），那么该数据的指数报酬会将其取消，你毫无影响，只要你有许多例子，且属性不太多。另外，如果算法做了一个双指数的假设（例如，所有可能的规则集），那么数据只会取消其中的一个指数，而且你仍会处于麻烦之中。你甚至可以提前弄明白自己需要多少例子，这是为了保证算法选择的假设和准确的那个非常接近，只要它对所有数据都拟合。换句话说，是为了假设能够尽可能准确。哈佛大学的莱斯利·瓦利安特获得了图灵奖（计算机科学领域的诺贝尔奖），因为他发明了这种分析方法，他在自己的书中将这种方法取名为“可能近似正确”（probably approximately correct），非常恰当。

你能信任的准确度

在实践中，瓦利安特式的分析方法往往非常被动，而且需要的数据比你拥有的还要多。那么你怎么决定，是否要相信学习算法告诉你的东西呢？这个很简单：在利用学习算法过去看不到的数据对其进行证实之前，你不要相信任何东西。如果学习算法假设的模型对新数据来说也适用，你就可以很有信心地说那些模型是正确的，否则你知道学习算法过拟合了。这仅仅是应用于机器学习中的科学方法：对一个新理论来说，这不足以用来解释过去的证据，因为捏造一个能做到这些的理论非常容易。理论还必须做出新的预测，而且只有这些预测经过实验验证后，你才接受它们（即使那样，也只是暂时的，因为未来的证据会对其进行证伪）。

爱因斯坦的广义相对论也只是在亚瑟·爱丁顿对其证实之后才广泛被人们接受。爱丁顿以经验为主，证实广义相对论的预测是对的，预测表明太阳使来自遥远星球的光线变弯了。但是你也不必等待新数据的到来，以决定能否信任学习算法。你可以利用自己拥有的数据，将其分成一个训练集和一个测试集，然后前者交给学习算法，把后者隐藏起来不让学习算法发现，用来验证其准确度。留存数据的准确度就是机器学习中的“黄金标准”。你可以写一篇关于你发明的伟大的新型学习算法的文章，但如果你的算法的留存数据不如之前的算法的留存数据准确，那么这篇文章也没有什么出版价值。

此前不可见数据的准确度测试确实是一个相当严格的考验，实际上，科学的很多方面都因此没有经得住考验。这并不意味着科学就没有用了，因为科学不仅仅是用来预测的，还能用来解释和理解。但是最后，你的模型如果无法对新的数据做出准确预测，就无法保证自己真的理解或者解释了隐藏在背后的现象。对于机器学习来说，对不可见数据的测试是必不可少的，因为这是判断学习算法是否过拟合的唯一方法。

即使测试集准确度也会出问题。据说，在早期军事应用中，一种简单的学习算法探测到坦克的训练集和测试集的准确度都为100%，两个集都由100张图片组成。惊讶？还是怀疑？结果是这样的——所有有坦克的图片都比没有坦克的图片亮，所以学习算法就都挑了较亮的图片。目前我们有更大的数据集，但并不意味数据收集的质量会更好，所以得当心。在机器学习从新生领域成长为成熟领域的过程中，务实的经验评价会起到重要的作用。追溯至20世纪80年代，每个学派的研究人员很多时候都相信自己华而不实的理论，假装自己的研究范式从根本上说是更好的，所以与其他学派的交流也很少。雷·穆尼、裘德·沙弗里克等符号学者开始系统地对不同算法的相同数据集进行比较，令人惊讶的是，真正的赢家还没有出现。如今竞争在继续，但“异花授粉”的情况也很多。利用加州大学欧文分校的机器学习小组维护的普通实验框架和大型数据集存储库，我们会取得重大进步。而且正如我们看到的，创造通用学习算法的最大希望在于综合不同研究范式的观点。

当然，知道你何时过拟合这一点还不足够，我们需要第一时间避免过拟合。这就意味着不再对数据进行完全拟合，即便我们能做到。有一个方法就是运用统计显著性检验来确保我们看到的模型真实可靠。例如，拥有300个正面例子、100个反面例子的规则，和拥有3个正面例子、1个负面例子的规则一样，它们训练数据的准确率都达到75%，但第一个规则几乎可以肯定比抛硬币好用，而第二个则不然，因为抛4次硬币，可以很容易得出3次正面朝上。在构建规则时，如果某一时刻无法找到能提高该规则准确度的条件，那么我们只能停下，即便它还包括一些负面例子。这样做会降低规则的训练集准确度，也可能让它变成一个更能准确概括的规则，这是我们关心的。

虽然如此，我们还没有大功告成。如果我尝试了一条规则，400个例子中的准确率是75%，可能会相信这个规则。但如果我尝试了100万条规则，其中最佳的规则中，400个例子中的准确率是75%，可能就不会相信这个规则，因为这很有可能是偶然发生的。这也是你在挑共同基金时遇到的问题。Clairvoyant基金连续10年获得高于市场平均水平的收益。哇！这个基金的经理一定是个天才，不是吗？如果你有1000种基金可以选择，很有可能你选的那个会比Clairvoyant基金的收益还要高，即使那些基金都由玩飞镖的猴子秘密经营。科学文献也被这个问题困扰着。显著性检验是决定一项研究结果是否值得出版的“黄金标准”，但如果几个组找一个结果，而只有一个组找到了，那么很有可能它并没有找到。虽然你阅读他们看起来很可靠的文章，但是绝不会猜到那样的结果。有一个解决方法：出版有肯定结果的文章，同时发表有否定结果的文章，那样你就会知道所有尝试失败的例子，但这种做法没有流行起来。在机器学习中，我们可以把自己尝试了多少条规则记录下来，然后相应地调整显著性检验，不过那样做，这些检验可能会把可靠的规则连同不可靠的一起丢弃。更好的方法就是认识到有些错误的假设会不可避免成立，但要控制它们的数量，方法就是否定低显著性的假设，然后对剩下的假设做进一步的数据检测。

另外一个流行的方法就是选择更加简单的假设。“分而治之”算法会含蓄地选择更简单的规则，因为它在一出现只有正面例子的情况时，就会停止添加条件；在一出现包含所有正面例子的情况时，就会停止添加规则。但为了和过拟合做斗争，我们要对更简单的规则有更强的偏好，这样就能在所有负面例子被包含之前，就停止添加条件。例如，我们可以稍微降低规则的准确度，来缩短规则的长度，然后把这种做法当作一个测评指标。

对较简单假设的偏好就是众人皆知的奥卡姆剃刀原理（Ocam’srazor），但在机器学习背景下，这有点误导性。“如无必要，勿增实体”，因为剃刀常常会被替换，仅意味着挑选能够拟合数据的最简原理。奥卡姆可能对这样的想法感到迷惑，也就是我们会偏向那些不那么能完整解释论据的理论，因为这个理论的概括性更好。简单的理论更受欢迎，因为它们对于我们来说，花费的认知成本更低；对于我们的算法来说，花费的计算成本更低，这不是因为我们想让这些理论更准确。相反，即使是我们最复杂的模型，也往往是在事实过分简化之后得到的。甚至在那些能够完美拟合数据的理论中，我们由“天下没有免费的午餐”这个定理，知道没有什么能够保证最简单的理论最擅长概括，而实际上，有些最佳的学习算法，比如推进和支持向量机，能了解那些看起来过于复杂的模型（在第七章和第九章中我们会了解它们为什么有这样的功能）。

如果你的学习算法检测集准确度不尽如人意，你就得诊断问题在哪里。是因为无知，还是因为幻想？在机器学习中，这些的专业叫法为“偏差”和“方差”。某座钟如果总是慢一个小时，那么它的偏差会很高，但方差会很低。但如果这座钟走得时快时慢，最后平均下来准点了，那么它的方差会很高，但偏差会很低。假设你和一些朋友在酒吧喝酒、玩飞镖。他们不知道你已经练了多年飞镖，所以非常熟练。你的所有飞镖都打到靶心，你的偏差和方差都很低，效果图3–1c所示。