终极算法 [美] 佩德罗·多明戈斯 中信出版集团

　　序

　　你也许不知道，但机器学习就在你身边。当你把查询信息输入搜索引擎时，它确定该向你显示哪些搜索结果（包括显示哪些广告）。当你打开邮箱时，大部分垃圾邮件你无法看到，因为计算机已经把这些垃圾邮件过滤了。登录亚马逊网站购买一本书，或登录网飞（Netflix）公司网站观看视频，机器学习系统会推荐一些你可能喜欢的产品。脸书（Facebook）利用机器学习决定该向你展示哪些更新，推特（Twitter）也同样会决定显示哪些文章。你使用计算机的任何时候，都有可能涉及机器学习。

　　传统上认为，让计算机完成某件事情的唯一方法（从把两个数相加到驾驶飞机），就是非常详细地记录某个算法并解释其如何运行。但机器学习算法就不一样：通过从数据中推断，它们自己会弄明白做事方法。掌握的数据越多，它们的工作就越顺利。现在我们不用给计算机编程，它们自己给自己编程。

　　机器学习不仅存在于网络空间，它还存在于你每天的生活中：从你醒来到入睡，每时每刻无所不在。

　　早上7 点你的收音机闹钟响起，播放的是你之前从未听过的歌曲，但你的确很喜欢这首歌。Pandora 电台（可免费根据你的喜好播放歌曲）的优势在于，根据你听的音乐，电台掌握了你的品位，就像你自己的radio jock 账号一样。这些歌曲本身可能借助机器学习来播放。接下来你吃早餐，阅读早报。早报在几个小时前印好，利用学习算法，印刷过程经过仔细调整，以免报纸出现折痕。你房间的温度刚刚好，电费明显少了很多，因为你安装了Nest智能温控器。

　　你开车去上班，车持续调整燃油喷射和排气再循环，以达到最佳的油耗。你利用一个交通预报系统（Inrix）来缩短高峰时段上下班的时间，这当然能减缓你的压力。上班时，机器学习帮你克服信息超载。你利用数据立方体来汇总大量数据，从每个角度观察该立方体，获取最有用的信息。你要决定是采用布局方案A，还是采用布局方案B，以便为网站带来更多的业务。网络学习系统会尝试两种布局方案，并给予反馈。你得对潜在供应商的网站进行调查，但网站的语言是外语。没关系，谷歌会自动为你翻译。E–mail 会自动分类并归入相应的文件夹，只把最重要的信息留在邮箱里，非常方便。文字处理软件帮你查找语法和拼写错误。你为即将到来的行程查找到一个航班，但决定推迟购买机票，因为必应旅行（Bing Travel）预测票价很快会下降。也许你没有意识到以上这些，要不是机器学习帮助你，你可能要马不停蹄地亲自做很多事情。

　　你在休息时间查看自己的共同基金，大部分基金利用学习算法来选股，其中的某些基金完全由学习系统运作。午餐时间到了，你走在大街上，想找个吃饭的地方，这时候用手机上的Yelp点评应用程序来帮助你。你的手机充满了学习算法，它们努力工作，改正拼写错误、理解口头指令、减少传输误差、识别条形码，还有其他很多事情。手机甚至可以预测你接下来会做什么，然后依此给出建议。例如，当你吃完午餐后，它会小心翼翼地提示你，下午和外地来访者的会面要推迟，因为她的航班延误了。

　　下班时夜幕已降临，你走向自己的车，机器学习会保证你的安全，监测停车场监控摄像头的录像，如果探测到可疑人的行动，它会提示不在场的安保人员。在回家路上，你在超市门口停车，走向超市货物通道，通道借助学习算法进行布置：该摆放哪些货物，通道末尾该展示哪些产品，洋葱番茄辣酱是否该放在调味酱区域，或是放在墨西哥玉米片旁边。你用信用卡付款。学习算法会向你发送信用卡支付提示，并在得到你的确认后完成支付。另外一个算法持续寻找可疑交易，如果它觉得你的卡号被盗，则会提示你。还有一种算法尝试评估你对这张卡的满意度，如果你是理想的客户但对服务不太满意，银行会在你决定换卡之前，为你提供更贴心的服务。

　　你回到家，走到信箱旁，发现有朋友的一封来信，这是通过能阅读手写地址的学习算法派送的。当然也会有垃圾来信，由另外的学习算法进行选择。你停留了一会儿，呼吸夜晚清新凉爽的空气。你所在城市的犯罪率明显下降了，因为警察开始使用统计算法来预测哪里的犯罪率最高，并在那里集中巡警力量。你和家人共享晚餐。市长出现在新闻里，你为他投票，因为选举那天，学习算法确定你为“关键未投票选民”之后，他亲自给你打了电话。吃完晚餐，你观看球赛，两支球队都借助统计学习来挑选队员。你也可能和孩子们在Xbox 上玩游戏，Kinecta学习算法确定你在哪里、在做什么。你在睡前吃药，医生通过学习算法的辅助来设定和检测吃药的最佳时间。医生也可能利用机器学习来帮你诊断疾病，例如，分析X射线结果并弄明白一系列非正常症状。

　　机器学习参与了你人生的每个阶段。如果你为了参加SAT大学入学考试（美国学术能力评估测试）而在网上学习，某学习算法会给你的练习短文打分。如果你申请商学院，且最近要参加GMAT（经企管理研究生入学考试），其中的一个文章打分工具就是一个学习系统。可能当你求职时，某学习算法会从虚拟文件中挑选出你的简历，并告诉未来的雇主：这位是很不错的人选，看看吧。最近公司给你加薪可能还多亏另外的学习算法。如果想买套房子，Zillow.com网站会估算你看中的每套房的价值，接着房子就有了着落。之后申请住房贷款，某学习算法会研究你的申请，并建议是否可以通过申请。最重要的是，如果你使用在线约会服务，机器学习甚至可能帮你找到人生挚爱。

　　社会在不断变化，学习算法也是如此。机器学习正在重塑科学、技术、商业、政治以及战争。卫星、DNA（脱氧核糖核酸）测序仪以及粒子加速器以前所未有的精细程度探索自然，同时，学习算法将庞大的数据转变成新的科学知识。企业从未像现在这样了解自己的用户。在美国大选中，拥有最佳选举模型的候选人奥巴马最终战胜了对手罗姆尼，获得了竞选胜利。无人驾驶汽车、轮船、飞机分别在陆地、海面、空中进行生产前测试。没有人把你的喜好编入亚马逊的推荐系统，学习算法通过汇总你过去的购买经历就能确定你的喜好。谷歌的无人驾驶汽车通过自学，懂得如何在公路上平稳行驶，没有哪个工程师会编写算法，一步一步指导它该怎么走、如何从A地到达B地——这也没必要，因为配有学习算法的汽车能通过观察司机的操作来掌握开车技能。

　　机器学习是“太阳底下的新鲜事”：一种能够构建自我的技术。从远古祖先学会打磨石头开始，人类就一直在设计工具，无论这些工具是手工完成的，还是大批量生产的。学习算法本身也属于工具，可以用它们来设计其他工具。“计算机毫无用处，”毕加索说，“它们只能给你提供答案。”计算机并没有创造性，它们只能做你让它们做的事。如果你告诉它们要做的事涉及创造力，那么就要用到机器学习。学习算法就像技艺精湛的工匠，它生产的每个产品都不一样，而且专门根据顾客的需要精细定制。但是不像把石头变成砖、把金子变成珠宝，学习算法是把数据变成算法。它们掌握的数据越多，算法也就越精准。

　　现代人希望让世界来适应自己，而不是改变自己来适应世界。机器学习是100 万年传奇中最新的篇章：有了它，不费吹灰之力，世界就能感知你想要的东西，并依此做出改变。就像身处魔法林，在你通过时，周围的环境（今天虚拟，明天现实）会进行自我重组。你在树木和灌木中选出的路线会变成一条路，迷路的地方还会出现指路标志。

　　这些看似有魔力的技术十分有用，因为机器学习的核心就是预测：预测我们想要什么，预测我们行为的结果，预测如何能实现我们的目标，预测世界将如何改变。从前，我们依赖巫医和占卜师进行预测，但他们太不可靠；科学的预测就更值得信赖，但也仅限于我们能系统观察和易于模仿的事物，大数据和机器学习却大大超出这个范围。我们可通过独立的思维来预测一些常见的事情，包括接球和与人对话，但有些事情，即便我们很努力，也无法预测。可预测与难以预测之间的巨大鸿沟，可以交给机器学习来填补。

　　矛盾的是，尽管学习算法在自然和人类行为领域开辟了新天地，但它们仍笼罩在神秘之中。媒体每天都报道涉及机器学习的新闻：苹果公司发布Siri 个人助理，IBMa沃森（IBM的超级计算机）在《危险边缘》游戏中战胜了人类，塔吉特（Target）能在未成年妈妈的父母发现之前通知她怀孕，美国国家安全局在寻找信息连接点……在这些新闻事件中，学习算法如何起作用仍不得而知。计算机“吞入”数以万亿的字节，并神奇地产生新的观点，关于大数据的书籍甚至也避谈“这个过程到底发生了什么”。我们一般认为学习算法就是找到两个事件之间的联结点，例如，用谷歌搜索“感冒药”和患感冒之间的联系。然而，寻找联结点与机器学习的关系就像是砖与房子的关系，房子是由砖组成的，但一堆砖头肯定不能称之为“房子”。

　　当一项新技术同机器学习一样流行且具有革命性时，不弄明白其中的奥妙实在太可惜。模棱两可会导致误差和滥用。亚马逊的算法能断定当今世界人们在读什么书，这一点比谁都强。美国国家安全局的算法能断定你是否为潜在恐怖分子。气候模型可以判定大气中二氧化碳的安全水平。选股模型比我们当中的多数人更能推动经济发展。你无法控制自己理解不了的东西，这也是追求幸福的公民、专家或普通人需要了解机器学习的原因。

　　本书的第一个目标就是揭示机器学习的秘密。只有工程师和机修工有必要知道汽车发动机如何运作，但每位司机都必须明白转动方向盘会改变汽车的方向、踩刹车会让车停下。当今极少有人知道学习算法对应的原理是什么，更不用说如何使用学习算法。心理学家丹·诺曼（Don Norman）创造了“概念模型”（conceptual model）这个新词，代指为了有效利用某项技术而需粗略掌握的知识。本书就将介绍机器学习的概念模型。

　　并不是所有算法的工作原理都相同，这些差异会产生不同的结果，比如亚马逊和网飞的推荐系统。假设这两个系统试着根据“你喜欢的东西”来对你进行引导，亚马逊很有可能会把你带到你之前常浏览的书籍类别，网飞则可能会把你带到你不熟悉且似乎有点奇怪的区域，并引导你爱上那里。在本书当中，我们会看到诸如亚马逊、网飞之类的公司使用的各式各样的算法。与亚马逊相比，网飞公司的算法对你的爱好理解得更深（尽管还是很有限），然而具有讽刺意味的是，这并非意味着亚马逊也应该利用这个算法。网飞的商业模式是依靠晦涩的电影、电视节目的长尾效应来推动需求，这些电影和节目的成本很低。它一般不推荐大片，因为你的会员订阅费可能有限。亚马逊则没有这样的问题：尽管擅长利用长尾效应，但它同样乐意把更昂贵的热销商品卖给你，这也会简化其物流工作。对于那些奇怪的产品，如果是订阅会员可免费享用的，我们可能会乐意去尝试，而如果需要另外掏钱，我们去选择它们的可能性就小得多。

　　每年都会出现上百种新的算法，但它们都是基于几个相似的基本思路。为了明白机器学习如何改变世界，你有必要理解这些思路。本书就将对此进行介绍。学习算法并不是那么深奥难懂，除了运用在计算机上，对于我们来说很重要的问题都可以通过学习算法找到答案，比如：我们如何学习？有没有更好的方法？我们能预测什么？我们能信任所学的知识吗？对这些问题，机器学习的各个学派有不同的答案。

　　机器学习主要有5 个学派，我们会对每个学派分别介绍：符号学派将学习看作逆向演绎，并从哲学、心理学、逻辑学中寻求洞见；联结学派对大脑进行逆向分析，灵感来源于神经科学和物理学；进化学派在计算机上模拟进化，并利用遗传学和进化生物学知识；贝叶斯学派认为学习是一种概率推理形式，理论根基在于统计学；类推学派通过对相似性判断的外推来进行学习，并受心理学和数学最优化的影响。在构建机器学习的目标推动下，我们将回顾过去100 年的思想史，并以新的观点来看待这段历史。

　　机器学习的5 个学派都有自己的主算法，利用这种万能学习算法，原则上，你可以通过任何领域的数据来挖掘知识：符号学派的主算法是逆向演绎，联结学派的主算法是反向传播，进化学派的主算法是遗传编程，贝叶斯学派的主算法是贝叶斯推理，类推学派的主算法是支持向量机。在实践中，这些算法可能在有些工作中可用，而在其他工作中不可用。我们真正想要寻找的是能够综合这5 种算法的终极算法。虽然有些人认为这难以实现，但对机器学习领域的人来说，这个梦想赋予我们力量，促使我们夜以继日地工作。

　　如果存在终极算法，那么它可以通过数据学得包括过去的、现在的以及未来的所有知识。创造终极算法将是科学历史上最伟大的进步之一。它可以加速各类知识的进步，并以我们现在甚至无法想象的方式改变世界。终极算法与机器学习的关系就像标准模型和粒子物理学或中心法则与分子生物学的关系：该统一原理能理解人类当今知道的一切，并为未来数十年或者数百年的进步奠定基础。今天我们面临许多难题，比如制造家用机器人和治愈癌症，终极算法就是解决这些难题的关键。

　　以癌症为例。治愈癌症十分困难，因为它往往是一种综合疾病。肿瘤可由各种原因诱发，且在转移时会发生突变。杀死肿瘤细胞最可靠的方法是对其基因进行排序，弄明白哪些药物可以抵抗癌细胞（这种方法不会对人造成伤害，患者必须提供基因和用药史），甚至为你专门研制一种新药。没有哪个医生能够掌握该过程所需的所有知识。对于机器学习来说，这却是再合适不过的任务。实际上，与亚马逊和网飞每天所做的搜索工作相比，它的工作是为你找到正确的疗法，而不是合适的书籍或者电影，而且它的工作更为复杂，也更具挑战。遗憾的是，虽然当今的学习算法能以超出人类水平的精确度来诊断疾病，但治愈癌症仍远远超出它们的理解范围。如果我们可以找到终极算法，这将不再是难题。

　　因此，本书的第二个目标就是帮你创造终极算法。你可能会认为这需要高深的数学运算和严谨的理论方面的工作，正相反，它需要暂时放下数学奥秘，来观看各种学习行为包罗万象的模型。对外行人来说，他们就像从远方赶到终极算法这片森林，从某些角度看，他们比专家更适合创造终极算法，因为专家对某些学科已经过于投入。一旦我们有了概念性的解决方法，就能补充数学上的细节，但这不是本书的目标和重点。我们之所以谈论每个学派，是为了收集它们的观点，并找到其适用之处。请记住，没有哪个盲人能了解整头大象。我们会尤其关注哪个学派能对治疗癌症做出贡献，也关注该学派的缺失。然后，我们会将所有观点集中，一步步地变成解决方案——这个解决方案可能还不是终极算法，但已是我们能找到的最接近终极算法的方案。希望它能解放你的大脑，让你大胆想象。当你阅读本书时，如果觉得某些章节读起来困难，可以随意略读甚至跳过它们。本书的概要才是重中之重，当明白所有学派的观点之后，如果你重读那些困难的章节，收获可能会比之前更多。

　　我研究机器学习已经有20 余年了。我对机器学习的兴趣因一本书而起，大四时我在书店看到这本书名很奇怪的书——《人工智能》（Artificial Intelligence）。那本书只有一个章节是关于机器学习的，但读那个章节时，我立即确定，学习是实现人工智能的关键，而且当时技术水平如此原始，我也许能做点什么。所以我搁置了读MBA（工商管理硕士）的计划，到加利福尼亚欧文分校攻读博士。机器学习当时是一个小众且鲜为人知的领域，研究人员寥寥无几，但加利福尼亚大学却拥有一个巨大的研究团队。一些同学中途放弃了，因为他们看不到机器学习的未来，而我坚持了下来。对我来说，没有什么能比教计算机学习更有吸引力的了：如果我们做到这一点，其他问题就会迎刃而解。5 年后我毕业了，那时数据挖掘技术十分流行，我开始写这本书。我的博士论文结合了符号学派和类推学派的观点。过去10 年，我一直在整合符号学派和贝叶斯学派的观点，最近又在尝试整合它们与联结学派的观点。是时候进行下一步研究，并尝试综合这5 个范式了。

　　写这本书时，我的脑海里浮现出各式各样但又有相似之处的读者。

　　围绕大数据以及机器学习的讨论充满争议，如果你对此感到好奇，且怀疑有比论文上看到的更为深层次的东西，那么这本书就是你进行革命的指南。

　　如果你的主要兴趣是机器学习的商业用途，那么本书至少能通过6 种方法帮助你：成为分析学中更精明的消费者；充分利用你的数据专家；减少许多数据挖掘项目的隐患；看看如果不买手写编码软件，你能让什么进行自动操作；降低信息系统的僵硬度；期待正朝你走来的新技术。我见过太多浪费大量时间和金钱去解决难题的人，他们使用了错误的学习算法，或者误解了学习算法的含义。要避免这些惨败，实际上，你只需要阅读这本书。

　　如果你是普通人或者决策者，关注由大数据和机器学习引发的社会和政治问题，那么本书将为你提供该技术的入门知识：什么是机器学习，机器学习能干什么、不能干什么。本书没有让你觉得乏味的复杂细节。从隐私问题到未来的工作，以及机器人化引起战争的道德观，我们会看到真正的问题所在，以及如何正确思考。

　　如果你是科学家或者工程师，那么机器学习肯定是你不想错过的有力武器。在大数据时代（即便是中型数据时代），陈旧的、靠得住的统计工具并不会让你走得更远。你需要的是机器学习的非线性技术来精确模仿多种现象，它会带来全新的、科学的世界观。今天，“范式转移”被人们用得过于随意，但我可以毫不夸张地说，本书要讲的内容就是和“范式转移”相关。

　　如果你是机器学习专家，那么你可能对本书的大部分内容已经相当熟悉，但你仍会发现其中有许多新颖的看法、经典的观点，以及有用的例子和类比。很大程度上，我希望本书能提出与机器学习相关的、新的看法，甚至能让你开始思考新的方向。我们身边到处是容易达成的目标，我们理应追寻这种目标，但我们也不应忽略不远处就有更大的目标（关于这一点，我希望你们能原谅我诗意地用“终极算法”来指通用型学习算法）。

　　如果你是学生，无论你多大，是考虑该选什么专业的高中生，还是决定该研究什么领域的本科生，或者是考虑转行、经验丰富的专家，我希望本书能让你对这个令人着迷的领域感兴趣。当今世界极度缺乏机器学习专家，如果你决定加入这一行列，你不仅能得到令人激动的时刻和丰厚的物质回报，还有服务社会的大好机会。如果你已经在研究并学习主算法，我希望本书能帮你了解它的历史。如果你在旅途中偶然发现本书，也值得你用心阅读。

　　最后要强调一点，如果你渴望奇迹，那么机器学习对你来说就是一场精神盛宴。我诚挚地邀请你一同前往。

　　佩德罗·多明戈斯（Pedro Domingos），美国华盛顿大学计算机科学教授，加州大学欧文分校信息与计算机科学博士，在机器学习与数据挖掘方面著有200多部专业著作和数百篇论文。国际机器学习学会联合创始人，《机器学习》杂志编委会成员，JAIR前副主编。美国人工智能协会院士（AAAI Fellow，国际人工智能界的*高荣誉），荣获SIGKDD创新大奖（数据科学领域的*高奖项）、斯隆奖（Sloan Fellowship）、美国国家科学基金会成就奖（NSF CAREER Award）、富布赖特奖学金、IBM学院奖以及多个顶ji论文奖项。

推荐序

序

第一章 机器学习革命

学习算法入门

为何商业拥护机器学习

给科学方法增压

10 亿个比尔·克林顿

学习算法与国家安全

我们将走向何方

第二章 终极算法

来自神经科学的论证

来自进化论的论证

来自物理学的论证

来自统计学的论证

来自计算机科学的论证

机器学习算法与知识工程师

天鹅咬了机器人

终极算法是狐狸，还是刺猬

我们正面临什么危机

新的万有理论

未达标准的终极算法候选项

机器学习的五大学派

第三章 符号学派：休谟的归纳问题

约不约

“天下没有免费的午餐”定理

对知识泵进行预设

如何征服世界

在无知与幻觉之间

你能信任的准确度

归纳是逆向的演绎

掌握治愈癌症的方法

20 问游戏

符号学派

第四章 联结学派：大脑如何学习

感知器的兴盛与衰亡

物理学家用玻璃制作大脑

世界上最重要的曲线

攀登超空间里的高峰

感知器的复仇

一个完整的细胞模型

大脑的更深处

第五章 进化学派：自然的学习算法

达尔文的算法

探索：利用困境

程序的适者生存法则

性有何用

先天与后天

谁学得最快，谁就会赢

第六章 贝叶斯学派：在贝叶斯教堂里

统治世界的定理

所有模型都是错的，但有些却有用

从《尤金·奥涅金》到Siri

所有东西都有关联，但不是直接关联

推理问题

掌握贝叶斯学派的方法

马尔可夫权衡证据

逻辑与概率：一对不幸的组合

第七章 类推学派：像什么就是什么

完美另一半

维数灾难

空中蛇灾

爬上梯子

起床啦

第八章 无师自通

物以类聚，人以群分

发现数据的形状

拥护享乐主义的机器人

熟能生巧

学会关联

第九章 解开迷惑

万里挑一

终极算法之城

马尔科夫逻辑网络

从休谟到你的家用机器人

行星尺度机器学习

医生马上来看你

第十章 建立在机器学习之上的世界

性、谎言和机器学习

数码镜子

充满模型的社会

分享与否？方式、地点如何？

神经网络抢了我的工作

战争不属于人类

谷歌＋终极算法=天网？

进化的第二部分

后 记

致 谢

延伸阅读

　　购物网站用算法来为你推荐商品，点评网站用算法来帮你选择餐馆，GPS系统用算法来帮你选择*佳路线，公司用算法来选择求职者……

　　当机器最终学会如何学习时，将会发生什么？

　　不同于传统算法，现在悄然主导我们生活的是“能够学习的机器”，它们通过学习我们琐碎的数据，来执行任务；它们甚至在我们还没提出要求，就能完成我们想做的事。

　　什么是终ji算法？

　　机器学习五大学派，每个学派都有自己的主算法，能帮助人们解决