你是理性主义者还是经验主义者？
理性主义者认为，感官会欺骗人，而逻辑推理是通往知识的唯一可靠的道路。经验主义者认为所有推理都是不可靠的，知识必须来源于观察及实验。法国人是理性主义者，盎格鲁–撒克逊人（法国人就这样称呼他们）是经验主义者。评论员、律师、数学家是理性主义者，记者、医生、科学家是经验主义者。《女作家与谋杀案》是关于犯罪的电视剧，属于理性主义，《犯罪现场调查》则属于经验主义。在计算机科学领域，理论家和知识工程师属于理性主义者，黑客和计算机学习者属于经验主义者。
理性主义者喜欢在迈出第一步前，就提前规划好一切。经验主义者喜欢尝试新事物，然后看看结果会怎样。我不知道理性主义和经验主义是否都有专门的基因，但我看了看自己的计算机科学家同事，经过反复观察，发现理性主义者和经验主义者的个性特点几乎一样：有些人以理性主义为核心，而且绝不会改变；其他人则是彻底的经验主义者，未来也不会改变。这两方可以彼此进行对话，而且有时候还可以利用彼此的定论，但他们对彼此了解仅限这么多。实际上，每方都会认为对方做什么并不重要，而且也没什么意思。
自从智人的黎明到来，理性主义和经验主义也许就已经出现。在去狩猎之前，原始人鲍勃会花很长时间坐在洞里，思考要去哪里打猎。同时，穴居女人爱丽丝正在外面系统地调查领土。这两种方法我们都还在使用，保守地说这两种方法没有哪个更好。你也许会认为，机器学习就是经验主义最终胜利的产物，但我们很快会看到，真理总是比我们想的更加微妙。
理性主义与经验主义是哲学家最热衷讨论的问题。柏拉图是早期的理性主义者，而亚里士多德是早期的经验主义者。关于这个问题的辩论，真正开始于启蒙运动时期，每方有三位伟大的思想家：笛卡儿、斯宾诺莎、莱布尼茨是理性主义的代表，洛克、贝克莱、休谟则是经验主义的代表。因为相信自己的推理能力，理性主义者编造出宇宙理论（委婉地说），这经不住时间的考验，但他们也创造了基本的数学知识，比如微积分和解析几何。经验主义总体来说更为实际，而且它们随处可见，从科学方法到美国宪法都有它们的身影。
大卫·休谟是最伟大的经验主义者，以及有史以来最伟大、以英语为母语的哲学家。诸如亚当·斯密、查尔斯·达尔文之类的思想家都深受其影响。你也可以说他是符号学派的守护神。他1711年生于苏格兰，大半辈子都生活在18世纪的爱丁堡（一个思想活跃的繁荣城市）。他虽然性情温和，却是一个严格的怀疑论者，花了大半辈子来解开他那个时代的难题。为了得出符合逻辑的论断，休谟借用了洛克开创的经验主义思想，并提出一个问题，这个问题在所有领域的知识中就像一把达摩克利斯之剑，从最琐碎的领域到最先进的领域，都是一个时刻存在的问题：在概括我们见过的东西以及没见过的东西时，怎样才能做到合理？从某种意义上说，每种学习算法都在尝试回答这个问题。
休谟的问题也正是我们开启寻找终极算法之旅的开始。首先，我们会通过日常生活中的例子来解释这个问题，并通过现在人人皆知的“天下没有免费的午餐”这个定理来体现这个问题。然后我们会看到符号学者对休谟的回答。这把我们引向机器学习中最重要的问题：不真实存在的过拟合或幻觉模式。我们会看到符号学者如何解决它。机器学习本质上是一种炼金术，在魔法石的辅助下把数据变成知识。对于符号学者来说，魔法石就是知识。在接下来的4章中，我们还会研究其他学派的“炼金术”。
约不约
你有一个很喜欢的朋友，想找她出来约会。如果遭到拒绝，你会很难过，但是如果你想知道她会不会答应，也只能去问她。现在是周五傍晚，你拿着手机坐在那里考虑要不要给她打电话。你记得上次你问过她，但她拒绝了。但是为什么上次的前两次你约她，她都答应了，而这两次的前一次她却拒绝了？可能有时候只是她不想出门？也可能她喜欢泡吧而不喜欢吃饭？为了理出头绪，你先放下了手机，写下了前几次的情况（见表3–1）。
表3–1 约会记录
那么答案是什么？答应还是不答应？有没有什么模型可以区分肯定和否定？更重要的是，这个模型会如何决定今天的情况？
很明显，没有哪个因素可以单独准确预测出答案：有的周末她喜欢出去约会，而有的周末她却不想出去；有时她喜欢去泡吧，而有时她又不喜欢……把所有因素综合起来会怎样？可能周末她喜欢去泡吧？并不是，第四次约会就排除了这种情况，或者可能她只喜欢天气暖和的周末晚上出去约会？是的！这个说法符合之前的情况！看了看外面寒冷的天气，好像今晚不合适。可是等一下！电视不好看的晚上她会不会想去泡吧？好像这也符合前几次的情况，也就是说今天可以约会！快，快点打给她，不然就迟了。再等等。你怎么知道这是对的模型？你已经找到两种情况和之前的情况相符，但这两次的预测都是否定。细想一下，如果她只想天气好的时候去泡吧，那怎么办？或者她只是在没什么电视好看时的周末才会出去？或者……
这时，你灰心地把画好的表揉成一团，丢到垃圾桶里。没有办法知道她会不会答应！你能做什么？休谟的灵魂伤心地在你的肩膀上点头。你没有任何依据选择这个而不是另外一个。对于“她会说什么”这个问题，回答“是”或“否”的可能性都一样。时钟嘀嗒作响，最后你准备抛硬币来决定。
你不是唯一身处窘境的人——我们都是。我们才开始寻找终极算法之旅，似乎就已经遇到无法克服的困难了。有没有什么办法可以从过去的经历中掌握规律，然后信心满满地运用到未来的事情中？如果没有，那么机器学习不就是一个没有希望的事业了吗？就此而言，所有学科甚至所有人类的知识，不就随时可能会被推翻吗？
这种情况不是大数据能解决的问题。你可以像卡萨诺瓦那样放荡，有无数个可以约会数几千次的女人，但你的主数据库还是不知道这次这个女人会说什么。即使今天和前几次她答应约会的情况一样（都是周末、一样的约会方式、一样的天气、一样的电视节目），这也并不意味着这次她会答应你出去约会。正如你所知道的那样，她的回答由一些你不知道或者无法知道的原因决定。也或者她的回答没有什么别的原因，只是随口回答，而你也只是白费力气地从之前的情况中找规律。
自休谟提出归纳问题，哲学家就已经对此进行辩论，但还没有人能给出一个满意的答案。伯特兰·罗素喜欢用“归纳主义者火鸡”这个故事来阐述这个问题。故事的主人公是一只火鸡，它来到农场的第一个早晨，主人在早上9点喂它们，但作为实实在在的归纳法优越论者，它不想过早下结论：主人每天都9点喂它们。首先它在不同情况下观察了很多天，收集了许多观察数据。主人连续多天都是9点喂它们，最终它得出结论，认为主人每天早上9点喂火鸡，那么主人一直会在早上9点给它喂食。接下来是平安夜那天的早晨，主人没有喂它，因为它被宰了。
如果休谟问题仅仅是一个我们可以忽略的哲学小难题，就太好了，但事实并非如此。例如，谷歌的业务就是在你往搜索框输入一些关键字时，猜测你在寻找哪些网页。过去搜索查询的人所输入关键字的大量记录，以及他们点击的、相应查询结果页面的链接，都是谷歌的重要资产。如果某个人输入一组关键字，而这些关键字却不在记录里面，你该怎么办？即便关键字在记录中，你怎么能肯定当前用户想要的搜索结果和之前的一样？
如果我们只是假设未来和昨天一样，那么会怎样呢？这当然是一个有风险的假设（这对归纳主义者火鸡就不会奏效）。另外，没有这样的假设，所有知识将不复存在，生活也是如此。虽然有很多不确定性，但我们还是宁可活下来。遗憾的是，虽然有那样的假设，但我们还是尚未走出困境。这个假设还得应付这些“微不足道的”例子：如果我是一名医生，患者B和患者A有一模一样的症状，我假设两人的诊断结果都一样。但如果患者B的症状和其他人都不一样，我就仍然不知道如何做诊断。这属于机器学习问题：将某结果推广到我们没有见过的事件中。
也许这也不是什么大问题？有了足够的数据，大多数事件不就变得“微不足道”了吗？不是的。我们在前面的章节中了解到，为什么记忆不能当作通用学习算法，我们现在可以用更量化的方式来解释这个问题。假设你现在有一个数据库，含有1万亿条记录，每条记录有1000个布尔字段（也就是说，每个字段回答一个是或否的问题）。这个数据库真的好大。你认为有多少种可能的事件？往下读之前好好猜一猜。每个问题可能的答案有两个，两个问题就是2乘以2（是—是、是—否、否—是、否—否），三个问题就是2的三次方（2×2×2=23），如果是1000个问题，就是2的1000次方（21000）。你的数据库中1万亿条记录，可能性就是分子是1、分母是无限大的数乘以1%，然后再乘以21000，“分子是1、分母是无限大的数”指的是“小数点前是0，小数点后是286个0，后面跟着1的小数”。结果就是：无论有多少数据——多少兆、多少千兆、多少千兆兆、多少泽或多少尧字节，你基本上什么也看不到。你要决定的新事件已经存在于数据库中，而数据库非常大，这件事发生的概率低到可以忽略，所以如果不进行一般化，对你就不会有任何帮助。
如果这些听起来有点抽象，那么假设你是一个邮件服务提供商，要将每封收到的邮件进行分类，分为垃圾邮件或非垃圾邮件。你也许有一个包含1万亿封过去邮件的数据库，而且每封邮件都已经被分为垃圾邮件或非垃圾邮件，但那样做并不会让你省事，因为每封新邮件和之前邮件一模一样的概率几乎是0。你没有选择，只能以大概的概率来区分垃圾邮件和非垃圾邮件，而根据休谟的观点，这根本做不到。
“天下没有免费的午餐”定理
休谟提出爆炸性问题之后的250年，大卫·沃尔珀特（David Wolpert）赋予了这个问题优雅的数学形式。沃尔珀特原来是一名物理学家，后来成为机器学习者。他的研究结果被人们称为“天下没有免费的午餐”定理，规定“怎样才算是好的学习算法”。这个规定要求很低：没有哪个学习算法可以比得上随意猜测。好吧，那我们就不用找终极算法，可以回家了：终极算法只是用抛硬币来做决定的算法。说真的，如果没有哪个学习算法可以比抛硬币更管用，那会怎样？而且如果真的是那样，为什么这个世界——从垃圾邮件过滤（随时都在进行）到自动驾驶汽车——到处都是非常成功的学习算法呢？
“天下没有免费的午餐”这个定理和帕斯卡尔赌注失败的原因非常相似。帕斯卡尔的《思想录》于1669年出版，他在书中提到我们应该相信基督教中的神，因为如果神存在，他就会给我们永生，而如果他不存在，我们的损失也很小。这在当时是非常复杂的论点，但正如狄德罗指出的那样，伊玛目也可以同样的理由让人们来相信真主安拉的存在。如果你选错了要信的神，代价就是永世在地狱。总而言之，在考虑各种各样可能相信的神时，选择特定的神来信仰，还不如选择其他的神。因为，有说“这样做”的神，也会有说“不，那样做”的神。你也许应该把神忘了，好好享受没有宗教限制的生活。
用“学习算法”来代替“神”，用“准确的预测”来代替“永生”，你就遵守“天下没有免费的午餐”这个定理了。选择你最喜欢的学习算法（在本书中你会看到很多算法）。如果存在学习算法比随机猜测好用的领域，我（一个喜欢唱反调的人）会构建一个学习算法没有随机猜测好用的领域。我要做的就是把所有“未知”例子的标签翻过来。因为“经过观察”的标签表明，你的学习算法绝无可能区分世界和反物质世界。在这两个世界中的平均表现，学习算法和随机猜测一样好用。因此，在所有可能的世界中，把每个世界与其反物质世界配对，你的学习算法的作用就和抛硬币的作用一样。
虽然如此，别马上就对机器学习或终极算法失望。我们不关心所有可能存在的世界，而只关心我们生存的这个世界。如果我们对这个世界有所了解，然后把了解的知识输入我们的学习算法，那么现在和随机猜测相比，学习算法就可以发挥优势了。休谟可能会回应说，知识本身必须由归纳得来，因此知识也是有问题的。没错，虽然知识是通过进化编入我们的大脑的，但我们不得不冒这个险。我们也可以这样问，有没有小部分毋庸置疑、非常基础的宝贵知识，让我们可以在其基础上进行所有归纳（有点像笛卡儿的“我思故我在”，虽然很难明白，如何将这句话输入学习算法中）。我觉得回答是肯定的，在第九章，我们就会知道那些宝贵的知识是什么。
同时，“天下没有免费的午餐”这个实际的结论表明，不靠知识进行学习，这样的事不存在。只有数字也不够。从零开始只会让你一无所获。机器学习就像知识泵，我们可以用它来从数据中提取大量的知识，但首先我们得先对泵进行预设。
数学家认为机器学习这个问题是一个不适定问题（ill–posed problem）：这个问题没有唯一解。下面是一个简单的不适定问题：哪两个数相加的得数是1000？假设这两个数都是正数，答案就有500种……1和999，2和998等等。解决不适定问题的唯一办法就是引入附加假设。如果我告诉你，第二个数是第一个数的三倍，那么答案就是250和750。
汤姆·米切尔（Tom Mitchell）是典型的符号学者，称机器学习体现“无偏见学习的无用性”。在日常生活中，“偏见”是一个贬义词：预设观念不太好。但在机器学习中，预设观念是必不可少的；没有这些观念，你就无法进行学习。实际上，预设观念对人类认知来说，也是必不可少的，这些观念是“直线布入”人脑的。对于它们，我们也觉得是理所当然的。超出那些观念的偏见才值得质疑。
亚里士多德曾经说过，在知识领域，没有什么东西不是首先凭借感觉来形成的。莱布尼茨又加了一句，“除了知识本身”。人类的大脑不是一张白纸，因为它不是一块石板。石板是被动的，你可以在上面写东西，但大脑可以主动处理它接收到的东西。记忆就是大脑用来写东西的石板，而且记忆不是一开始就是空白的。另一方面，计算机在你给它编程之前，就是一张白纸；在用计算机做事之前，这个积极的过程需写入记忆。我们的目标是找到最简单的、我们能编写的程序，这样写好的程序就可以无限制地通过阅读数据来自行编程，直到该程序掌握所有能掌握的知识。
机器学习不可避免地含有投机的因素。在《警探哈里》（第一集）中，克林特·伊斯特伍德追逐一名银行抢劫犯，同时不断向他开枪。最后，抢劫犯躺在一把装有子弹的枪旁边，不确定要不要把它拿起来。哈里开了6枪还是只开了5枪？哈里同情地说（可以这么说）：“你得问自己一个问题：‘我足够走运吗？’你真的走运吗，小子？”这也是机器学习算法每天运作时必须问自己的问题：“今天我幸运吗？”就像进化的过程一样，机器学习不是时时刻刻都知道自己是否可以准确无误地运行。实际上，误差是常有的事，并不意外。但没关系，因为我们放弃误差的部分，主要靠没有误差的部分，而计算结果才是最重要的。我们一旦掌握新的知识，基于前面的步骤，就可以得出更多的知识。唯一的问题就是，从哪里开始。
对知识泵进行预设
在《自然哲学的数学原理》一书及三大运动定律中，牛顿阐述了推理的四条法则。虽然这些法则没有那些物理定律那么著名，但可以说很重要。其中第三条是关键法则，我们可以这样表述：
我们见过的所有真实的东西，在宇宙中也是真实的。
可以毫不夸张地说，这句听起来无伤大雅的话就是牛顿革命以及现代科学的核心。开普勒定律适用于6个实体：那个年代太阳系中已知的6颗行星。牛顿定律适用于宇宙中的每一个微粒。这两个定律之间的共性如此之大，让人感到吃惊，而这也是牛顿法则的直接结果。这个法则本身就是拥有非凡动力的知识泵。没有这个法则，也就没有什么自然法则，有的也只是永远无法完整的、小规律的集合体。
牛顿法则是机器学习的第一个不成文规则。我们归纳自己能力范围内、应用最广泛的规则，只有在数据的迫使下，才缩小规则的应用范围。乍一看，这看起来可能过于自信甚至近乎荒谬，但这种做法已经为科学服务了300余年。当然也可以想象出一个变化无常的宇宙，在那里牛顿法则不起作用，但那并不是我们的宇宙。
然而，牛顿法则仅仅是第一步。还得弄明白我们见到的哪些是真实的——如何从原始数据中找出规律。标准的解决方法就是假设我们知道真理的形式，而算法的任务就是把这个形式具体化。例如，在之前提到的约会问题中，你可以假设你朋友的回复由单个因素来决定。在这种情况下，算法就只包括看看每个已知的因素（时间、约会方式、天气、晚间电视节目），确定该因素是否每次都能准确预测她的回答。可问题就在于，每个因素都无法预测她的回答！你打赌了，然后输了。所以你把假设放宽了一点。如果你朋友的回答是由两个因素一起决定的呢？总共四个因素，每个因素有两种可能的值，那么总共有24种可能（总共有6对因素组合，即12乘以因素的两种可能）。数字太多，我们遇到尴尬：两个因素的四种组合准确预测了结果！接下来怎么办？如果你觉得运气还行，可以选其中的一种，然后祈祷最好的结果。但更明智的选择是采取民主的做法：对每个选项进行选择，然后选最后赢的预测。
如果所有两个因素组合的预测都失败了，你可以尝试任意个数因素的组合，机器学习者和心理学家称之为“合取概念”（conjunctive concept）。字典对词的定义就属于合取概念：椅子是有靠背、若干条腿的坐具。把任意一个描述去掉，就不再是椅子。托尔斯泰在写《安娜·卡列尼娜》的开篇时，出现在他脑海里的就是合取概念：“所有幸福的家庭都是相似的，每个不幸的家庭各有各的不幸。”对于个人来说，也是这样的。为了感到幸福，你需要健康、爱、朋友、钱、你喜欢的工作等。把这些东西的任意一个拿走，痛苦也会随之而来。
在机器学习中，概念性的例子成为正面例子，而与概念例子相反的则是负面例子。如果你在尝试通过图片来认出猫，那么猫的图片就是正面例子，而狗的图片则是负面例子。如果你对世界文学中描述的家庭进行汇总，并编成数据库，那么卡列尼娜一家就是幸福家庭的负面例子，而且正面例子寥寥无几。
首先做有条件的假设，如果这样无法解释数据，再放松假设的条件，这就是典型的机器学习。这个过程通常由算法自行进行，不需要你的帮助。首先，算法会尝试所有单一因素，然后尝试所有两个因素的组合，之后就是所有三个因素的组合等。但现在我们遇到一个问题：合取概念太多，没有足够的时间对其逐个尝试。
约会的例子有点欺骗性，因为它太小（4个变量，4个例子）。但假设你提供在线约会服务，你就需要知道要对哪些人进行配对。如果你的每个会员都填写了一份问卷，问卷包含50个“是或否”的问题，这样就有100种特点，这100种特点涵盖了每对可能配对成功的情侣的特点，每对情侣中的一方都有50个特点。这些情侣出去约会之后，会汇报结果，在此基础上，你能找到“佳偶”这个定义的合取概念吗？总共有3100种可能的定义（每个问题有三种选择，分别为“是”、“否”、“与该品质无关”）。即使由世界上最快速的计算机来做这项工作，这些情侣也会老得去世了（你的公司也破产了）。等你计算出来，除非你走运，可以找出很短的一条关于“佳偶”的定义。规则太多，而时间太少，我们得做点更精明的事。
这里有一种方法：暂且假设每个配对都合适，然后排除所有不含有某品质的搭配，对每种品质重复同样的做法，然后选择那个排除了最多不当搭配和最少适当搭配的选项。现在你的定义看起来就像“只有他开朗，这对才合适”。现在反过来试着把其他品质加进去，然后选择那个排除了剩下最多的不当搭配和剩下最少的适当搭配的选项。现在的定义可能是“只有他和她都开朗，这对才合适”。然后试着往那两个特点里加入第三个品质，以此类推。一旦排除了所有不合适的搭配，你就成功了：就有了这个概念的定义，这个概念排除了所有的正面例子和所有的负面例子。例如，“每对中的两个人都开朗，这对才合适，他爱狗，而她不爱猫”。现在你可以丢掉所有数据，然后只把这个定义留下，因为这个定义概括了所有和你的目标相关的东西。这个算法保证能在合理的时间内完成运算，而这也是我们在本书中见过的第一个真实的学习算法。
如何征服世界
虽然合取概念的用途有很多，但并不能让你走很远。正如鲁德亚德·吉卜林说的那样，问题在于“编部落歌谣的方法有很多种，而每种方法都是正确的”。真正的概念是分离的。椅子可能有四条腿或三条腿，而有些则一条也没有。你可以以无数种方法来赢一盘棋。包含“伟哥”这个词的邮件有可能是垃圾邮件，但包含“免费”一词的邮件也有可能是垃圾邮件。此外，所有规则都会有例外。所有的鸟都会飞，除了企鹅、鸵鸟、食火鸡或者几维鸟（或断了翅膀的鸟，或被锁在笼子里的鸟）。
我们要做的就是学习经过一系列规则定义的概念，而不仅仅是单个规则，例如：
如果你喜欢《星球大战》第四至六部，那么你会喜欢《阿凡达》。
如果你喜欢《星际迷航：下一代》以及《泰坦尼克号》，那么你会喜欢《阿凡达》。
如果你参加塞拉俱乐部，并阅读科幻书籍，那么你会喜欢《阿凡达》。
或者：
如果你的信用卡昨天在中国、加拿大以及尼日利亚被刷，那么它被盗了。
如果某工作日晚上11点，你的信用卡被刷，那么它被盗了。
如果你的信用卡被用来购买一美元的汽油，那么它被盗了。
如果你对最后一条规则有疑问，解释如下：过去信用卡窃贼通常会用偷到的卡购买一美元的汽油，来看看在数据挖掘器识破其阴谋前，信用卡是否完好。
我们可以像学习这条规则那样来同时学习多套规则，利用我们之前见过的算法来学习合取概念。我们学习每个规则之后，会排除该规则包含的正面例子，因此下一个规则会尽可能多地包含剩下的正面例子，以此类推，直到所有的例子都被包含在内。这是一个“分而治之”的例子，也是科学家的战术手册中最古老的策略。为了找到单个规则，我们也可以对算法进行改良，方法就是保留某数n的假设，不止一个数，然后在每个步骤中将这些数以所有可能的方法延伸开来，最后保留n的最佳结果。
通过该方法发现规则的创意来自理夏德·米哈尔斯基（Ryszard Michalski），他是波兰的一位计算机科学家。米哈尔斯基的故乡——卡尔鲁兹之前曾属于波兰、俄罗斯、德国以及乌克兰，这让米哈尔斯基比多数人更能理解合取概念。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’s razor），但在机器学习背景下，这有点误导性。“如无必要，勿增实体”，因为剃刀常常会被替换，仅意味着挑选能够拟合数据的最简原理。奥卡姆可能对这样的想法感到迷惑，也就是我们会偏向那些不那么能完整解释论据的理论，因为这个理论的概括性更好。简单的理论更受欢迎，因为它们对于我们来说，花费的认知成本更低；对于我们的算法来说，花费的计算成本更低，这不是因为我们想让这些理论更准确。相反，即使是我们最复杂的模型，也往往是在事实过分简化之后得到的。甚至在那些能够完美拟合数据的理论中，我们由“天下没有免费的午餐”这个定理，知道没有什么能够保证最简单的理论最擅长概括，而实际上，有些最佳的学习算法，比如推进和支持向量机，能了解那些看起来过于复杂的模型（在第七章和第九章中我们会了解它们为什么有这样的功能）。
如果你的学习算法检测集准确度不尽如人意，你就得诊断问题在哪里。是因为无知，还是因为幻想？在机器学习中，这些的专业叫法为“偏差”和“方差”。某座钟如果总是慢一个小时，那么它的偏差会很高，但方差会很低。但如果这座钟走得时快时慢，最后平均下来准点了，那么它的方差会很高，但偏差会很低。假设你和一些朋友在酒吧喝酒、玩飞镖。他们不知道你已经练了多年飞镖，所以非常熟练。你的所有飞镖都打到靶心，你的偏差和方差都很低，效果图3–1c所示。
图3–1
你的朋友本也玩得很好，但他喝得有点多。他的镖射完了，他大声说，平均下来是他射中了靶心（也许他本该是一位统计学家）。这是低偏差、高方差的例子，如图3–1d所示。本的女朋友艾希莉射得很稳，但射的时候过于偏向右上角。她的方差低，但偏差高（见图3–1a）。科迪，从外地来，从来没有玩过飞镖，射的镖都位于中心上方，偏离中心，他的偏差和方差都高（见图3–1b）。
你可以估算一种学习算法的偏差和方差，方法就是在掌握训练集的随机变量之后，对算法的预测进行对比。如果算法一直出错，那么问题就出在偏差上，而你需要一个更为灵活的学习算法（或者只和原来的不一样即可）。如果出现的错误无模式可循，问题就出在方差上，而你要么尝试一种不那么灵活的学习算法，要么获取更多的数据。大多数学习算法都有一个“把手”，通过旋转“把手”，你可以调节这些算法的灵活度，例如，显著性检验的界限值，或者对于模型规模的惩罚方式。扭动“把手”是你尝试的第一个方法。
归纳是逆向的演绎
更深层的问题是，多数学习算法开始时掌握的东西很少，即使转再多“把手”，也没法让这些算法到达终点。没有成年人大脑中所储存知识的指导，这些算法很容易误入歧途。虽然多数学习算法会误入歧途，但只是假设你明白真理的形式（例如，那是一小组规则），还不足以达到令人震惊的程度。严格的经验主义者会说，开始时知之甚少，这是所有新生儿都有的特点，因为这个特点深深存在于其大脑结构中，而孩子确实会比成人更容易犯过拟合的错误，但我们想学得比孩子快（18年是很长的一段时间，而且还没把大学教育时间计算在内）。主算法应该能以大量的知识作为启动（无论这些知识由人类来提供，还是之前已经掌握），然后在对数据做出新概括时，用到这些知识。这就是科学家做的工作，这相当于从零开始做。“分而治之”原则的归纳算法做不到这一点，但还有别的掌握规则的方法能做到。
问题的关键在于认识到，归纳仅仅是逆向演绎，就和减法是加法的逆运算，或者积分是微分的逆运算一样。这个观点由威廉姆·斯坦利·杰文斯于19世纪末首次提出。史蒂夫·马格尔顿和雷·邦坦（一个英国—澳大利亚研究组）在此基础上于1988年设计出第一个实用算法。在数学这个学科中，通过已知条件进行运算，得出其逆向结果的方法已经有一段传奇的历史。把这种方法运用到加法当中就有了整数，因为如果没有负数，加法就不可逆了（3-4=-1）。同样，将其用到乘法中就有了有理数，而将其运用到平方运算中就有了复数。让我们来看看能否将这种方法运用到演绎中。演绎推理的一个典型例子就是：
苏格拉底是人类。
所有人类都会死。
所以……
第一个句子是关于苏格拉底的事实，第二个是关于人类的一般规则。接下来的推理是怎样的？苏格拉底当然也会死，这是将一般规则用到苏格拉底身上得出的。相反，我们在归纳推理中会以最初事实和衍生事实作为开始，然后找一个规则，让我们由前者推出后者：
苏格拉底是人类。
……
所以苏格拉底也会死。
有这样一个规则：如果苏格拉底是人类，那么他就会死。这句话完成了推理，但并不是很有用，因为这是专门针对苏格拉底的规则。但现在我们应用牛顿定律，然后将该定律推广到所有实体当中：如果某实体是人类，那么它就会死。或者更简洁些：所有人类都会死。当然，仅通过苏格拉底就归纳出该规则过于草率，但对于其他人类，我们知道相似的事实：
柏拉图是人类，他会死。
亚里士多德是人类，他会死。
以此类推……
对于每个事实，我们构建这样的规则，让我们由第一个事实推出第二个事实，然后通过牛顿定律将其推广。当同一条通用规则一次又一次被归纳出来时，我们有信心说那条规则说的是真的。
到目前为止，我们还没有做任何“分而治之”算法无法做到的事。可是，如果我们不知道苏格拉底、柏拉图、亚里士多德是人类，只知道他们是哲学家，那会怎样？我们仍会得出结论，说他们也会死，因为之前我们就归纳过或者别人告诉过我们，所有人都会死。这也是一种有效推广（至少在我们解决人工智能问题，而机器人开始从事哲学研究之前是），而且这也在我们的推理中“填补了漏洞”：
苏格拉底是哲学家。
所有哲学家都是人。
所有人都会死。
所以苏格拉底会死。
我们也可以单纯从其他规则中归纳另一些规则。如果我们知道所有哲学家都是人，而且会死，我们就可以归纳出所有人都会死（我们不会归纳出所有会死的都是人类，因为我们知道其他会死的动物，例如猫和狗。另一方面，科学家、艺术家等也是人类，也会死，因此这条规则得到加强）。通常，我们以越多的规则和事实作为开头，也就有越多的机会运用“逆向演绎”归纳新的规则。我们归纳的规则越多，我们能归纳的规则也就越多。这是知识创造的良性循环，只受过拟合风险和计算成本的限制。可是在这里，我们也有初始知识的协助：如果我们有很多小的而不是大的漏洞要修补，归纳的步骤就不会有那么大的风险，所以过拟合的可能性也会降低（例如，给定相同数量的例子，“所有哲学家都是人类”这个归纳，就比“所有人都会死”这个归纳风险要小）。
逆运算往往比较困难，因为逆运算的结果不止一个。例如，一个整数有两个平方根：一个正数，一个负数［22=（–2）2=4］。最为人所知的是，对一个函数的导数积分，只会将函数恢复为一个常数。函数的导数告诉我们该函数在每个点上下浮动的幅度。把所有幅度值加起来会重新得到函数，除非我们不知道它从哪里开始变化。我们可以在不改变导数的情况下，上下“滑动”积分过的函数。为了简便，我们可以假设附加常量为0，来“取缔”函数。逆向演绎存在类似的问题，而牛顿定律就是一个解决方法。例如，我们由“所有希腊的哲学家都是人类”和“所有希腊哲学家都会死”可以归纳出“所有人类都会死”，或只能归纳出“所有希腊人都会死”。可是为什么仅满足于最保守的归纳？其实我们可以认为所有人都会死，直到遇到例外（据雷·库兹韦尔说，这个意外很快就会出现）。
同时，逆向演绎的另外一个重要的应用，就是预测新研制的药物是否有不良的副作用。动物测试及临床试验的失败，成为研制新药物需要花费多年、数十亿美元的主要原因。通过归纳已知有毒分子的结构，我们可以得出规律，迅速清除明显的有毒化合物，大大提高剩余化合物的临床试验成功率。
掌握治愈癌症的方法
更广泛地说，逆向演绎是在生物学中发现新知识的重要方法，这也是治愈癌症要迈出的第一步。根据中心法则的观点，在活细胞中进行的任何活动都最终由细胞的基因控制，通过发起蛋白质的合成来完成。一个细胞就像一台微型计算机，而DNA就是计算机运行的程序：改变DNA，皮肤细胞就会变成神经元细胞，或者小鼠细胞会变成人类细胞。在计算机的程序中，所有的故障都是由程序员引起的。但在细胞中，故障可自行产生，比如当辐射或者细胞复制误差将某基因变成另外一个基因时，当基因偶然被复制两次时……很多时候，变异会导致细胞悄无声息地死去，但有时候细胞开始生长，然后不可控制地分裂，这样癌细胞就产生了。
治愈癌症意味着在不破坏完好细胞的情况下，阻止受损细胞的繁殖。这就需要知道完好细胞和受损细胞的区别在哪里，特别是它们染色体组的区别在哪里，因为其他所有的一切都依此进行。幸运的是，基因测序变得越来越普遍、越来越实惠。利用基因测序，我们可以预测哪种药对哪种癌基因起作用。这和传统的化学疗法不一样，化学疗法对所有细胞的影响都一样。掌握哪种药物对哪种变异有效，这需要关于患者的数据库、他们的癌基因、服用过的药物以及药效。最简单的规则对基因与药物之间一对一的对应关系进行编码，例如，如果出现BCR–ABL基因，那么服用格列卫这种药物（BCR–ABL引发一种白血病，而格列卫在10个患者中能治愈9个患者）。一旦癌基因排序和治疗结果核对达到标准管理，更多这样的规则会被发现。
然而，这仅仅是一个开始。大多数癌症都会涉及各种混合的变异，或者只有靠某些药物才能治愈，而这些药物尚未被研发出来。下一步就是以更为复杂的条件来掌握规则，这涉及癌基因组、患者的基因组、病史、药物的已知副作用等。但最终我们需要的，就是完整细胞运转的模型，这让我们在计算机上对特殊病人变异的影响、不同药物组合的效果进行模仿，无论是真实存在的，还是猜想出来的，都进行模仿。我们构建此类模型的主要信息，主要源于DNA测序仪、基因表达微阵列以及生物学文献。将这些结合起来，人们就会看到逆向演绎的作用。
亚当（我们在第一章中提到过的机器人科学家）就是一个例子。亚当的目标是弄明白酵母粉如何起作用。机器人以酵母遗传学、新陈代谢的基本知识，以及一批酵母细胞的基因表达数据作为开端，运用逆向演绎来假设哪种基因会通过哪种蛋白质来表达，然后设计微阵列实验来对其进行检测，接着修正假设，最后重复以上步骤。是否每个基因都会表达出来，这取决于其他基因，以及所处的环境条件，由此产生的网络交互可表达为一个规则集，例如：
如果温度高，那么基因A就会表达出来。
如果基因A表达出来，而基因B没表达出来，则基因C表达出来。
如果基因C表达出来，那么基因D不会表达出来。
如果我们知道的是第一条和第三条规则，不知道第二条，但我们有微阵列数据，数据显示在高温条件下，基因B和基因D无法表达，那么我们就可以通过逆向演绎来归纳出第二条规则。一旦我们有了这条规则，而且也许利用微阵列实验证实了这条规则，那么我们就能用它作为进一步归纳推理的基础。同理，我们也可以将化学反应的顺序拼凑起来，因为蛋白质就是按照这些顺序发挥作用的。
即便如此，仅仅知道哪些基因调节哪些基因，以及蛋白质如何组织化学反应中的细胞网络还不够。我们还需要知道，每种分子产生的量有多少。DNA微阵列和其他实验能够提供这种数量方面的信息，但逆向演绎，以其“非有即无”的逻辑特点，并不是很擅长处理这方面的事情。因此我们要用到联结学派的方法，这会在下一章谈到。
20问游戏
逆向演绎的另外一个局限性就在于，它涉及很密集的计算，因此很难扩展到海量数据集中。因为这些原因，符号学家选择的算法是决策树归纳。决策树可以当作此类问题的答案：如果有多个概念的规则对应一个实例，那怎么办？那么我们怎么知道实例对应哪个概念呢？如果看到一个部分封闭的物体，它有一个平面、四条腿，那么我们怎么知道它是一张桌子，还是一把椅子呢？有一个方法，就是对规则进行排序，例如以准确率递减的顺序来排列，然后选择符合描述的第一条规则。另一个方法，就是让规则自己选择。决策树通常会保证，每个实例会准确对应一条规则。也就是说，在一次及以上的属性测试中，如果每对规则存在区别，这样的规则集将被组织成一棵决策树。例如，看看以下这些规则：
如果你支持削减税收，反对堕胎，那么你属于共和党。
如果你反对削减税收，那么你属于民主党。
如果你支持削减税收，提倡堕胎合法，反对枪械管制，那么你属于独立人士。
如果你支持削减税收，提倡堕胎合法，支持枪械管制，那么你属于民主党。
这些可以组成一些决策树，如图3–2所示。
图3–2
决策树的原理就像玩一个有实例的20问游戏。从“根部”开始，每个节点都会问每个属性的值，然后根据答案，我们沿着这个或另外一个分支继续下去。当到达“树叶”部分时，我们读取预测的概念。从“根部”到“树叶”的每条路线都对应一个规则。这让人想起那些烦人的电话语音提示菜单，如果你拨打客户服务电话，就得通过这些菜单，这些菜单与决策树相似并非偶然——电话语音提示菜单就是一棵决策树。电话线另一头的计算机在和你玩20问游戏，目的是弄明白你想要做什么，每个选项就是一个问题。
根据以上决策树，你要么是共和党人，要么是民主党人，要么是独立人士。你无法选择其中的两种或三种，或者一个都不选。拥有这个属性的概念组被称为类集，而预测类集的算法称为分类器。单个概念隐含两类定义：概念本身及其反面（例如，垃圾邮件和非垃圾邮件）。分类器是机器学习最为普遍的方式。
利用“分而治之”算法的一个变体，我们就可以掌握决策树了。首先，我们选一个属性，在决策树的“根部”进行测试。然后我们关注每个分支上的例子，为那些例子选择下一个测试（例如，我们看看支持削减税收的人是否反对堕胎或者支持堕胎合法）。我们在归纳推理出的每个新节点上重复这个步骤，一直到分支上的所有例子都有同一个类别，此时我们就可以用该类别来命名该分支了。
有一个突出的问题，那就是如何挑选最佳属性以便在节点处进行测试。准确度（准确预测例子的数量）并不能起到很好的作用，因为我们不是在尝试预测某个特殊类别，而是在尝试慢慢分离每个类别，直到每个分支都变得“纯粹”。这使人想起信息论中熵的概念。一组对象的熵，就是用来衡量混乱度的单位。如果150人的组里面有50个共和党人、50个民主党人、50个独立人士，那么这个组的政治熵会达到最大。另一方面，如果这个组全部是共和党人，那么熵就变成零（这就是党派联合的目的）。所以为了学习一棵好的决策树的优点，我们在每个节点选择这样的属性：在其所有分支中，产生的熵在平均值上属性最低，取决于每个分支上有多少例子。
和规则学习一样，我们不想归纳出一棵树，可以准确地预测所有训练例子的类别，因为这样的树很有可能会过拟合。和之前一样，为了防止这样的事情发生，我们可以利用显著性检验或针对树的大小设立惩罚制度。
如果属性离散，属性的每个值都有一个分支，这没关系，但如果是数值属性该怎么办？如果连续变量的每个值都有一个分支，决策树将变得无限宽。一个简单的方法就是通过熵来选择几个临界值，然后使这些临界值起作用。例如，患者的体温是高于还是低于100华氏度？这个体温数和其他症状一起，也许是所有医生都要知道的，通过体温可以断定患者是否感染疾病。
决策树可应用在许多不同的领域。在机器学习领域，决策树源于心理学方面的知识。厄尔·亨特及其同事于20世纪60年代利用了决策树，目的是为了模拟人类如何掌握新的概念。另外，亨特其中的一个研究生罗斯·昆兰后来尝试把决策树用于象棋中。他最初的目的是为了从棋盘占位预测王车大战骑士的后果。据调查，决策树已经由一开始这些微不足道的用途，发展成为机器学习算法中应用最为广泛的方法。要知道原因并不困难：决策树易于理解，可以快速掌握，而且通常无须太多调整就可以做到准确无误。昆兰是符号学派中最卓越的研究者。作为一个沉稳、务实的澳大利亚人，因为对决策树年复一年不断地改进，并写了和决策树有关、逻辑清晰的论文，使决策树成为分类活动中的“黄金标准”。
无论你想预测什么，人们利用决策树来预测的可能性会很大。微软的Kinect利用决策树，通过其深度相机的输出信息，可以弄明白你身体的各个部位在哪里，然后利用这些部位的动作来控制Xbox游戏机。在2002年的一场正面交锋中，决策树准确预测了3/4的最高法院裁决，而一个专家小组的准确率却不到60%。数千个决策树使用者不可能会出错，你仔细想想，然后画一棵树来预测朋友的答复（如果你想约她出去的话）。如图3–3所示。
图3–3
根据这棵树的结果，今晚她会答应你出去约会。深呼吸，拿起手机，拨通她的电话吧。
符号学派
符号学派的核心理念就是，所有和智力相关的工作都可以归结为对符号的操纵。数学家在解方程时，会移动符号，然后根据预先定义的规则，用其他符号来代替这些符号。逻辑学家进行推论时也是同样的道理。根据这个假设，智力是独立于基质的。符号处理是通过写在黑板上进行的，还是通过打开或关闭晶体管、放电神经元，或者玩玩积木就能完成的，这些都不重要。如果你能利用万能图灵机的力量来进行设置，那么就能做任何事情。软件可以和硬件清晰地分离。如果你关注的重点是想弄明白机器是怎样学习的，你（谢天谢地）不用担心后者无法在亚马逊的云服务上购买个人计算机或者自行车。
符号学机器学习者和许多其他计算机科学家、心理学家、哲学家一样，都相信符号操纵的力量。心理学家大卫·马尔称，每个信息处理系统应该经过三个不同水平的研究：该系统解决所解决问题的基本属性，用来解决问题的算法和表示方法，以及这些算法和表示方法如何实现。例如，加法可以由一组公理来定义，和加法如何进行无关；数字可以以不同方式进行表达（例如，罗马数字和阿拉伯数字），还可以用不同算法进行相加；而这些运算可以通过算盘、袖珍计算器，或者效率更低的方式——你的大脑来进行。根据马尔的水平理论，学习是我们能够研究的认知能力的典型例子，而且对我们来说受益匪浅。
符号主义机器学习是人工智能知识工程学派的一个分支。20世纪70年代，所谓的基于知识的系统取得卓越成绩，而到了80年代，它们迅速传播，后来却消失了。它们消失的主要原因是人人逃避的知识习得瓶颈：从专家身上提取知识，然后将其编码成为规则，这样做难度太大、太费力、易出故障，会引起很多问题。让计算机自行学习，比如通过查看过往患者症状及其相应疗效的数据库，就可以进行疾病诊断，比无数次地找医生要容易很多。突然之间，诸如理夏德·米哈尔斯基、汤姆·米切尔、罗斯·昆兰之类的先驱人物，他们的工作有了新的联系，而这个领域自此没有停止发展过（另外一个重要的问题就是基于知识的系统在处理不确定性时会有问题，在第六章会深入探讨这个问题）。
因为其起源和指导原则，符号学派和其他学派相比，和人工智能的其他方面关系更为密切。如果计算机科学是一块大陆，符号主义机器学习和知识工程学会有很长的交界线。知识通过两个方向进行交易——手动输入的知识，供学习算法使用；还有归纳得出的知识，用来加入知识库中，但最终理性主义者和经验主义者的断层线会刚好落在这条界线上，想越过这条界线则不容易。
符号主义是通往终极算法的最短路程。它不要求我们弄明白进化论和大脑的工作原理，而且也避免了贝叶斯主义的数学复杂性。规则集合决策树易于理解，所以我们知道学习算法要做什么。这样它可以轻易算出自己做对或做错什么，找出故障，得出准确结果。
尽管决策树很受欢迎，但逆向演绎是寻找主算法更好的出发点。因为逆向演绎具备这样的关键属性：可以轻易地将知识并入主算法中，而且我们知道休谟问题使这一点变得很有必要。另外，规则集和决策树相比，表达多数概念的方式要简洁很多。把一棵决策树转变成一个规则集很容易：每条从“根部”到“叶子”的路线是一条规则，而且路线不会崩溃。另外，最坏的情况是，把一个规则集转化成一棵决策树，需要把每条规则变成一棵迷你决策树，然后用规则2决策树的副本来代替规则1决策树的每片叶子，用规则3决策树的副本来代替规则2决策树每个副本的每片叶子，以此类推，这样会引起大范围崩溃。
逆向演绎就像一个超级科学家，系统查看论据，思考可行的归纳法，整理最有利的证据，然后将这些和其他论据一起，进一步提出假设——所有过程都基于计算机的速度。逆向演绎简洁而美观，至少符合符号学者的品位。此外，逆向演绎也有一些严重的缺点。可行的归纳法数量广泛，除非我们和最初知识保持亲密关系，否则很容易在空间中迷失。逆向演绎容易被噪声迷惑：我们怎样才能知道，哪些演绎步骤被漏掉了，如果前提或者结论本身就已出错？最严重的是，真正的概念很少能通过一个规则集来定义。它们不是黑，也不是白，比如垃圾邮件和非垃圾邮件之间有一片很大的灰色区域。要获取真正的概念，就得权衡并收集有弱点的论据，直到出现清晰的定义。疾病的诊断，涉及把重点放在一些症状上面，然后放弃那些不完整的论据。还没有人能只学习一个规则组，就能通过观看图片的像素来认出一只猫，而且可能以后也没人能做到。
联结学派对符号学派尤其不满。根据他们的观点，你能通过逻辑规则来定义的概念仅仅是冰山一角，其实表面之下还有很多东西是形式推理无法看到的。而同样的道理，我们脑子里所想的东西也是潜意识的。你不能仅靠构造一个空洞的机械化科学家，就想让他把所有有意义的事情完成，你首先得给他点什么东西，例如一个真正的大脑，能和真实的感觉相连，在真实世界中成长，甚至可能要常常绊他的脚。你怎样才能构造这样的大脑呢？通过逆向分析。如果想对一辆车进行逆向分析，你就应看看发动机盖下面。如果想对大脑进行逆向分析，你就要看看脑壳里面。