《人工智能基础》

第 1 章是全书的概述：人工智能是什么、怎样一路走来、有哪几个学派、用在哪里、现阶段还做不到什么。本章梳理的推理期、知识期、学习期，也就是全书推理、知识、学习三部分的由来（前言）。

把“人工智能”拆开看（第 1 章）：“人工”指人造的、对自然事物的模拟；“智能”是人类和某些高等生物神经系统特有的能力。人类智能包括四个方面：感知和理解环境，思维、推理和决策，学习，适应环境以及行动。学术界至今没有统一的定义。1956 年达特茅斯会议的说法是：让机器的行为看起来就像人表现出来的智能行为一样。后来模拟的对象扩展到其他生物，实现方式也不必照搬人类，作者因此给出一个较宽的定义：

本书给出的人工智能定义如下：人工智能是基于人们对智能机制的理解，使机器模拟、延伸或替代人类智能或其他生物智能的理论、方法、技术及应用的一门系统学科。

第 1 章 1.1.1 节，p.2

近期目标和长期目标（第 1 章）：近期目标是造出有特定功能的智能工具，例如无人驾驶、机器翻译、人脸识别；追求的是系统行为和人的行为相似，不追求内部机制一致。长期目标是揭示智能的机理，造出完全自主的智能“伙伴”。自主性指机器在没有直接外部干预时独立行动、在最少的人类监督下做决定的能力，通常用来表征机器的智能水平。作者说，长期目标为近期目标指明方向，近期目标为长期目标打下理论和技术基础。

弱、强、超人工智能（第 1 章）：按发展程度分三级。弱人工智能（artificial narrow intelligence，ANI）也叫专用人工智能，只擅长单方面的工作；强人工智能（artificial general intelligence，AGI）一般叫通用人工智能，在各方面都和人类智能相当；超人工智能（artificial super intelligence，ASI）则全面超越人类智能。作者说，目前所有人工智能系统都属于弱人工智能，垃圾邮件分类、百度翻译、能战胜围棋世界冠军的 AlphaGo 都是；不过随着生成式人工智能和大语言模型的快速发展，强人工智能“已初露萌芽”。对超级智能的种种设想，作者提醒“极具争议性”，未必符合未来的发展，只有一定借鉴意义。

三起两落的发展史

四个词（第 1 章）：一般认为 1956 年以前是孕育期。此后按研究热点的变换（书中依据周志华 2016 年的分法），人工智能经历了三个时期：20 世纪 50 年代到 60 年代中后期是推理期，主流技术是基于符号表示的搜索和演绎推理；60 年代后期到 80 年代中期是知识期，主流技术是知识工程和专家系统；80 年代后期至今是学习期，主流技术是统计学习和基于人工神经网络的连接主义学习。作者把这段历史概括为四个词：“源远流长”“分进合击”（各学派独立探索）、“跌宕起伏”（三起两落）、“殊途同归”。

孕育期（第 1 章）：数理逻辑、控制论、信息论等理论的创立和电子计算机的发明，为人工智能准备了基础。书里的年表从亚里士多德（Aristotle）的三段论讲起，经过1936 年图灵（Turing）提出的图灵机、1943 年第一个神经元数学模型麦卡洛克-皮茨模型（McCulloch-Pitts，MP），到 1950 年图灵提出图灵测试。图灵测试给出了一个检验机器是否有智能的可操作标准，作者称之为“人工智能哲学方面的第一个提案”。

推理期（第 1 章）：当时人们以为，只要让机器会逻辑推理，机器就有了智能。代表工作是 Simon 和 Newell 的自动定理证明程序逻辑理论家（logic theorist）和后来的通用问题求解器（general problem solver，GPS）。1956 年夏天，McCarthy、Minsky、Shannon 等人发起的达特茅斯研讨会提出了“artificial intelligence”一词，标志人工智能成为独立学科，这一年被称为人工智能元年。随后迎来第一个高潮：1957 年 Rosenblatt 提出感知器，开启有监督学习的先河；1958 年王浩用 3～5 分钟证明了《数学原理》中命题演算的全部 220 条定理；同年 McCarthy 发明了最早的人工智能语言 LISP（list processor，表处理语言）。一些学者以为通用人工智能二十年内就会出现。

接着很快跌入低谷：机器翻译错误百出；复杂问题求解遇到组合爆炸；感知器解决不了异或这类线性不可分问题。作者分析原因：问题太复杂；在缺少问题知识的情况下追求通用方法；理论匮乏是关键。承诺落空后很多项目中断，甚至有人认为不必保留独立的人工智能学科。

知识期（第 1 章）：以 Feigenbaum 为代表的学者认为，要让机器有智能，就必须让机器拥有知识。1968 年，第一个推断化学分子结构的专家系统 DENDRAL 研制成功，研究者转向解决狭窄专业领域的典型问题。作者说，专家系统让人工智能从理论研究转向实际应用，使人们认识到“知识是智能的基础”；不确定性知识的表示与推理也取得突破，建立了主观贝叶斯方法、可信度方法、证据理论等。1981 年，日本启动为期 10 年的第五代计算机项目。神经网络也在这时复兴：1982 年 Hopfield 提出反馈神经网络，1986 年 Rumelhart 等提出多层前馈网络的误差反向传播（back propagation，BP）算法。但人类知识量巨大，把知识总结出来教给计算机相当困难，专家系统卡在知识获取的瓶颈上，还有领域狭窄、缺乏常识、维护成本高等问题；第五代计算机的推理速度还不如通用计算机，以失败告终。

学习期（第 1 章）：

无论是推理期还是知识期，机器都是按照人类设定的规则和总结的知识运行，无法超越其创造者，并且人力成本非常高。

第 1 章 1.2.4 节，p.6

数据快速积累、算力大幅提升之后，人们希望机器通过分析数据自动学习。1984 年 Valiant 提出概率近似正确理论（probably approximately correct，PAC），为统计学习奠定理论基础；90 年代中期，以支持向量机和核方法为代表的统计学习占据主流；2006 年，深度学习概念被提出。2012 年，Hinton 和两名研究生设计的卷积神经网络 AlexNet 在 ImageNet 图像分类比赛（ILSVRC）中夺冠；书中图 1.2 显示，此后冠军的识别错误率逐年下降，2015 年降到 3.6%，低于人类的 5.1%。2022 年 11 月 30 日 OpenAI 推出 ChatGPT，引发了人们对生成式人工智能的广泛关注。

三大学派

符号主义（第 1 章）：符号主义（symbolicism）又叫逻辑主义、心理学派，认为智能的基本元素是符号，智能行为是符号运算的结果。它的基本假设是物理符号系统假设（书中引 Newell 等 1976 年的工作）：一个完善的符号系统有输入、输出、存储、复制符号，建立符号结构，实现条件性迁移这 6 种功能；能表现智能的系统必定能执行这 6 种功能，反过来也成立。由此推出：人和计算机都是物理符号系统，可以用计算机模拟人的智能活动。作者认为，感性知识和某些常识很难用符号精确描述，所以这个假设“有很大的局限性，是不完全成立的”。

符号主义解题分三步：把现实问题抽象成符号（一般靠人工），用算法做推理演算求解，再回到现实世界执行、检验效果。优点是可解释、易理解；缺点是符号化要靠人工并会丢失信息，知识难在任务间复用，知识一多容易互相矛盾，不适合数据含噪声、模型不明确的图像识别等场景。它的最新发展是知识图谱。

连接主义（第 1 章）：连接主义（connectionism）又叫仿生学派、生理学派，认为智能的基本元素是神经元，智能产生于大量神经元的并行分布式连接，代表研究是人工神经网络。数据充足时，它能从数据中发现隐含的规律，抗噪能力好；深度学习大大提高了图像识别和语音识别的效果，使它成为热点。缺点是人脑机理尚未明确，只能局部模拟；需要大量训练数据，在开放动态环境下效果不理想；在输入和输出之间建立了一个“无法解释的黑箱”，不适合解决逻辑推理问题。

行为主义（第 1 章）：行为主义（actionism）又叫进化主义、控制论学派，认为智能取决于感知和行动。它把能与环境进行感知与行动交互的个体抽象为 Agent（书中不译），用个体是否有合理行动来衡量智能。这一派的出发点是：认知能力很弱的生物，没有世界模型、没有语法语义规则，也能在复杂的真实世界里活得很好，靠的是反射能力而不是知识推理。Brooks 认为让机器像人一样思维太难，不如先做出像样的机器昆虫，再慢慢进化出机器人。他在麻省理工学院人工智能实验室做的六足机器昆虫由 150 个传感器和 23 个执行器组成，能像蝗虫一样行走；它不会推理和规划，应对复杂环境的能力却大大超过同时代的机器人。作者说，行为主义关注智能的外在表现，降低了对智能的要求；它的最新发展是强化学习，即 Agent 在与环境交互中根据奖励或惩罚不断学习行动策略。

由分立到融合（第 1 章）：作者说，21 世纪初开始，三大学派由分立逐步走向融合。把神经网络的“黑箱学习”与先验知识、符号推理和统计学习结合，是为了实现可解释、可推理、可操控的“白箱学习”；把连接主义和行为主义结合，就有了深度强化学习。知识问答系统既用符号主义的知识存储和查询，也用连接主义做语音识别和语言理解；自动驾驶要综合三派的方法。

人工智能的进步正是不同研究学派发展、碰撞与融合的结果。

第 1 章 1.6 节，p.18

用在哪里，擅长什么，还差什么

应用领域（第 1 章）：应用分两大类：一类是智能信息处理，解决海量信息的筛选、分类、挖掘、检索等问题；一类是实现智能行为，即 Agent 的感知、判断、决策和控制。书中列举的典型领域有：

• 机器视觉：让计算机采集、处理和理解视觉信息，已是落地最广的人工智能技术之一。
• 自然语言处理：从基于规则、统计学习走到深度学习；2018 年以来“预训练+微调”成为新范式。
• 智能规划与决策：推理出实现目标的动作序列、选择方案，是无人机、无人车等自主系统的核心技术。
• 机器人：从“示教-再现”的程序控制机器人，到配有少量传感器的自适应机器人，再到能感知、学习、决策的智能机器人；自动驾驶按国际汽车工程师协会（SAE）的标准分为 0—5 共 6 级。
• 计算机博弈：被看作验证机器智能的“试金石”。1997 年“深蓝”靠强大算力加搜索和剪枝战胜国际象棋世界冠军 Kasparov；这种方法对围棋无效，AlphaGo 结合深度学习和强化学习战胜了李世石、柯洁，AlphaGo Zero 只靠自我博弈学习。
• 专家系统：用大量专门知识和经验模拟人类专家的决策，解决没有算法解的复杂问题。

硬计算与软计算（第 1 章）：传统方法用经典数学和统计工具求精确解，称为硬计算。语音识别、天气预报这类问题影响因素多、数据有噪声、知识不完全，很难求出精确解，而且追求最优解未必有意义。人工智能利用常识、领域知识和搜索策略，给出近似、不精确但成本低的解，通常是次优解或可行解。

近似、不精确的高效软计算方法正在以“大概率会足够好”的低成本解决方案补充或取代“最好的”硬计算解决方案。

第 1 章 1.5.1 节，p.16

从计算复杂度看，人工智能擅长 NP（non-deterministic polynomial）完全问题和 NP 难问题。P 问题（polynomial problem）是在多项式时间内就能算出来的问题，即所需时间随问题规模按多项式增长，比如排序；NP 完全问题是最难的一类 NP 问题，目前没有多项式时间的有效算法，比如旅行商问题（traveling salesman problem，TSP），暴力搜索要花指数级甚至阶乘级的时间。对这类问题，人工智能的代表技术是启发式算法，如启发式搜索、智能优化算法：能以可接受的代价给出较优解，但不能保证全局最优，表现取决于具体问题和设计者的经验。

现阶段的局限（第 1 章）：莫拉维克悖论（Moravec's paradox）说，对计算机而言，人类独有的逻辑和思考能力只需要很少的计算量，无意识的技能和感知能力却需要极大的计算量。Moravec 说过，让计算机像成人一样下棋相对容易，让它有一岁小孩的感知和行动能力却相当困难。作者比较说，人能处理不确定、偏主观的问题，能随时改变目标；人工智能需要明确的目标和可观测的环境，很难创造从未有过的东西。作者归纳了人工智能做好一项典型任务的五个条件：

• 有丰富的知识指导推理，或有丰富的数据帮助挖掘规律；
• 环境可观测；
• 环境确定，能准确预测操作的后果；
• 环境静态，或者变化规律已知；
• 任务目标明确。

国际象棋、围棋、图像识别、语音识别都满足这五条；有一条或几条不满足，就比较困难。自动驾驶要兼顾安全、快速、舒适，难以定出量化目标，天气和突发路况又让环境不确定、动态、规律未知，所以完全自主驾驶还非常困难。此外，以深度学习为核心的系统存在鲁棒性差（环境稍有变化就容易出错）、可解释性差、要求大样本等问题，限制了它在关键领域的应用。本章小结里作者的结论是：

目前，人工智能还是一种实现特定功能的智能工具，在短期内不可能全面超越人类智能。

第 1 章 1.6 节，p.19

第 2—5 章是全书的推理部分，依次讲状态空间搜索、人工智能博弈、智能优化算法和经典逻辑推理（前言）。第 2 章打头。作者说，人工智能面对的大多是无法用经典数学方法求解的复杂问题，很难掌握全部信息，也没有现成的算法，只能依靠经验和已有知识一步步摸索：

根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小(或较小)的推理路线，使问题得以解决的过程称为搜索。

第 2 章，p.21

有些问题理论上有算法，但复杂度太高，受时间和空间限制无法实用，也要靠搜索。本章的办法是：用状态空间法表示问题，用图搜索算法求解。

把问题画成一张图

状态与操作算子（第 2 章）：状态（state）描述求解过程中某一时刻的状况，只保留对求解有用的信息；操作算子（operator）也叫状态转换规则，是把问题从一个状态变到另一个状态的手段。所有状态和它们之间的转换关系构成状态空间（state space）。一个状态空间由五样东西确定：状态集合、算子集合、初始状态、目标状态、路径代价（没有明确给出时，每步代价算 1）。画成图时，节点是状态，边是算子，边上的权是转换的代价，问题的解就是从初始节点到目标节点的一条路径。作者说，把问题抽象成状态空间图是知识表示，在图里找路径是推理，推理的前提是正确确定状态和转换规则。

硬币和开机（第 2 章）：3 枚硬币全部正面朝上，每次翻 2 枚，能不能全部翻成反面？3 枚硬币共有 8 种状态，只有恰好 2 枚正反不同的状态之间能互相转换；画出图来，初始状态和目标状态不连通，所以做不到。换成 4 枚、每次翻 3 枚，就有解。另一个例子是负载均衡开机：4 台设备分两路供电，要逐台开机，两路负载之差不能超过 500W；16 种开关组合里有 7 种违反限制，只剩 9 个有效节点，求解就是找一条从全关到全开的路径。魔方、汉诺塔、旅行商问题，以及路径规划、集成电路布局、定理证明、机器人行动规划，都可以这样描述。

先构图，还是边走边构图（第 2 章）：先生成全部节点和边、再从中找路的，叫显式图。现实问题往往做不到：三阶魔方约有 4.33×10¹⁹ 个状态，围棋最多有 3 的 361 次方个状态，比宇宙中已知的原子数还多。可人走迷宫并不需要完整的地图，从起点出发，边探索边发现新的房间就行。用状态描述和转换规则的知识来定义的图叫隐式图，计算机里只需存这些知识。

显式图搜索是先构图再寻路，而隐式图搜索是边构图边寻路。

第 2 章 2.1.2 节，p.24

通用图搜索框架

从走迷宫说起（第 2 章）：作者用一个人走迷宫的过程来抽象。站在起点 S，查看 S 通向哪些房间，叫扩展 S，发现的房间是 S 的子节点。已经扩展过、不必再探索的房间称为 Closed 房间；已经发现但还没探索的称为 Open 房间。每一步只能从 Open 房间里挑一个去扩展，扩展完它就变成 Closed，新发现的房间成为 Open，如此循环，直到找到目标。据此设两张表：Closed 表存已扩展的节点，Open 表存待扩展的节点。流程是：

• 第一步，把初始节点放进 Open 表；
• 第二步，如果 Open 表空了，说明无解，失败退出；
• 第三步，从 Open 表选一个节点 n，移进 Closed 表；
• 第四步，如果 n 是目标，成功退出；
• 第五步，找出 n 的全部子节点放进 Open 表，回到第二步。

成功的条件是“正在扩展的节点为目标节点”。状态空间图就这样随探索逐步展开，算法设计得当的话，只需探明一小部分。要给出解路径，就在扩展时为每个子节点记下父节点：每个节点只有一个父节点，找到目标后逐级回溯父节点，就得到倒过来的解路径。

选哪个节点来扩展（第 2 章）：

采用何种选点策略对于图搜索算法的性能有决定性影响，根据不同的选点策略，通用图搜索框架可衍生出不同的图搜索算法。

第 2 章 2.1.2 节，p.27

求解中与问题相关、能用来简化搜索的信息叫启发信息（heuristic information）。不用启发信息、只按发现次序之类选点的，是盲目搜索，也叫无信息搜索；先评估 Open 表中每个节点离目标有多近、挑最有希望的扩展，是启发式搜索。

同一个节点被发现两次（第 2 章）：图里有环路，或两点之间有多条路，新扩展出的子节点可能已经在 Open 表或 Closed 表里。两个节点状态相同、来路不同，严格说是两个节点，但从它们出发往后找的情况完全一样，只需保留一个。保留哪个，看历史已用代价 g(n)，即从初始节点到 n 已发现路径的最小代价。规则是：新节点不比旧节点好（g 大于或等于旧的），就舍弃新节点；新节点更好，就删掉旧节点、把新节点放进 Open 表，不管旧节点原来在哪张表。作者解释：如果旧节点已在 Closed 表，它的子节点的父指针和代价都是按旧节点算的，要逐个找出来更新很难；把新节点放回 Open 表、让它重新扩展，后继节点会被重新发现，父指针和代价也就自动更新了。何况新节点并没有被扩展过，不该留在 Closed 表。作者认为，这比有的资料分 Open、Closed 两种情况来讲更清晰。

节点和规则怎么写进程序（第 2 章）：节点至少要记三项：state（状态）、father（父节点）、g（历史已用代价）。设计 state 有三个要点：可行性，能区分不同的节点，这是基本要求；简洁性，变量尽量少；易用性，便于做扩展运算。转换规则至少包含两样：应用条件（应用前的状态）和应用结果（应用后的状态）。以八数码为例：3×3 的棋盘上有 8 个数字棋子和 1 个空位，空位旁的棋子可以移进空位。用 3×3 数组表示状态就能区分棋局，但每用一次规则都要先查空位在哪里，不够易用；把空位坐标一起放进状态，规则就好写了。作者借此说明，数据结构和扩展过程要一起设计。

盲目搜索

宽度优先与深度优先（第 2 章）：宽度优先搜索（breadth first search，BFS）每次选最先进入 Open 表的节点，Open 表像一个排队的队列，离起点近的先扩展。问题有解且搜索树宽度有限时，它一定能找到解；每步代价相同的问题，找到的一定是最优解；缺点是效率低，有时等同于穷举。深度优先搜索（depth first search，DFS）每次选最后进入 Open 表的节点，Open 表像一摞盘子（堆栈），先往深处钻。它有时更省时间和空间，但搜索树无限深时可能停不下来，也不保证找到最优解。改进办法有两个：有界深度优先搜索给深度设一个上限 l，到了就退回上一层，可目标有多深事先不知道，l 小了找不到解，大了费时间；迭代加深搜索让 l 从小到大逐次试，结合了两者的优点，既保证找到解，又兼顾效率。

代价优先搜索（第 2 章）：每步代价不同时，用代价优先搜索（uniform cost search，UCS，也叫一致代价搜索），每次选 g 最小的节点扩展。书中例 2.5 从城市 A 到城市 E：先扩展 A，发现 C（代价 6）和 B（代价 7）；扩展 C，发现 D（13）和 E（23）；扩展 B，又发现 D，这次代价 12 更小，替换原来的 D；扩展 D，发现代价 18 的 E，替换代价 23 的 E；最后扩展 E，成功。解路径是 A→B→D→E，代价 18，是最优的。如果一发现 E 就停下，得到的会是代价 23 的 A→C→E。

之所以要在扩展节点时再检查其是否为目标节点，是为了保证找到最优解；如果发现目标节点即终止，那么无法保证找到最优解。

第 2 章 2.2.3 节，p.37

代价优先搜索仍算盲目搜索，因为它只看已经花了多少，不估计到目标还要花多少；有解时保证最优，但不一定快。书中用四项标准比较这几种算法：时间复杂度（扩展的节点总数）、空间复杂度（最多要存的节点数）、完备性（有解就一定能找到）、最优性（找到代价最小的解）。宽度优先、迭代加深、代价优先都是完备的，深度优先不完备，有界深度优先在深度上限不小于目标深度时才完备；代价优先总能找到最优解，宽度优先和迭代加深要在每步代价相同时才最优。

启发式搜索

在启发式搜索算法中，通常既要考虑节点的历史已用代价，又要考虑节点接近目标节点的程度，从而兼顾最优性和搜索效率。

第 2 章 2.3 节，p.38

A 算法：f(n)=g(n)+h(n)（第 2 章）：A 算法给 Open 表中每个节点 n 打一个分 f(n)=g(n)+h(n)，按分数从小到大选点。g(n) 是从起点到 n 已经花的代价；h(n) 叫启发函数，是对从 n 到目标还要花多少代价的估计，由设计者根据问题特点和经验给定。作者说，考虑 g 是为了找到最优解，考虑 h 是为了挑更接近目标的节点、缩小搜索范围；g 占比越大越可能找到最优解，但越慢；h 占比越大越快，但 h 估计不准时会扰乱搜索。h 恒为 0 时，A 算法就是代价优先搜索；g 恒为 0 时，变成贪婪搜索，可能很快，但不保证最优。例 2.6 用两个启发函数：h₁ 估得合理，找到代价 13 的最优路径；h₂ 与实际代价相差大，找到的是代价 15 的路径，不是最优。

可纳的启发函数（第 2 章）：如果对所有节点，h(n) 都不超过从 n 到目标的实际最小代价 h*(n)，即从不高估，就说这个启发函数满足可纳性（admissibility）；采用可纳启发函数的 A 算法就是 A* 算法。定理 2.1 证明：在有限图上，如果每条边的代价都大于某个正数、问题有解，A* 一定终止在一条最小代价的解路径上。证明的要点是：算法结束前，Open 表里总有一个位于最优路径上的节点，它的分数不超过最优路径的代价；而非最优路径上的目标节点，分数一定大于最优代价，所以总排在那个节点后面，不会先被选中。也就是说，非最优的目标节点可能先被发现，但不会先被扩展，这正是把成功条件设在扩展时的原因。代价优先搜索就是 h 恒为 0 的 A*，所以它也一定能找到最优解。

怎样设计启发函数（第 2 章）：作者提出两个要求：尽量准确地反映实际代价；满足可纳性。对应两条思路：先找一个尽量准的估计，再证明它可纳；或者放松原问题的限制条件，比如减少对操作的限制，用放松后问题的代价当估计。迷宫里代价是路径长度，可以用到目标的直线距离（欧氏距离），两点之间直线最短，所以不会高估；也可以用横、纵坐标差的绝对值之和（曼哈顿距离），因为相邻房间之间只有水平或垂直的路。八数码里很难直接估出步数，就用放松的办法：假设棋子可以不受阻挡地自由移动，每个棋子的归位步数就是它到目标位置的曼哈顿距离，加起来作为估计；再放松一步，只数有几个棋子没归位，因为每个没归位的棋子至少要动一步。两个估计都可纳。

更具信息（第 2 章）：在可纳的前提下，h 越大越好，也就是越接近真实代价越好。两个可纳的启发函数，如果对所有节点都有 h₁(n) ≤ h₂(n)，就说 h₂ 比 h₁ 更具信息。定理 2.2 证明：用 h₂ 的 A* 扩展过的节点，用 h₁ 的 A* 也一定扩展过，即 h₂ 扩展的节点不会更多。八数码里，曼哈顿距离之和比未归位棋子数更具信息，书中的例子分别扩展了 6 个和 7 个节点。

单调性（第 2 章）：A* 有时会把同一个节点扩展两次：第一次是从非最优的方向发现它的，后来从更好的方向又发现了它。如果对任意节点和它的子节点，父节点的估计值都不超过子节点的估计值加上这一步的代价（三角不等式的形式），就说启发函数满足单调性。定理 2.3 证明：这时 A* 每扩展一个节点，就已经找到了到达它的最优路径，因此不会重复扩展节点。书中迷宫和八数码的四个启发函数都满足单调性。以曼哈顿距离之和为例，走一步棋，被移动棋子的曼哈顿距离最多增减 1，所以估计值的变化不超过这一步的代价 1。

特点与改进（第 2 章）：作者总结，A* 在移动机器人和车辆自动导航中应用广泛，适合环境不变、有先验知识的路径搜索；估计越接近实际，搜索越快；有解时一定找到最优解。缺点是 h 估计得过低时，要存的节点多，速度难以满足实时要求。研究者从内存消耗、实时性、动态环境适应性、移动目标追踪、路径质量等方面做了改进，例如：

• 动态 A*（D*，Stentz 1994 年提出）：机器人在动态环境中相邻两次搜索的路径很相似，重用已搜索的信息比完全重算更快，适合周围环境未知或动态变化的场合；
• 任意时间 D*（anytime D*，AD*）：在 D* 的基础上考虑时间约束，能在有限时间内重新规划次优路径；
• 任意时间修复 A*（anytime repairing A*，ARA*）：先快速给出一条次优路径，再在时间允许的范围内不断优化，时间足够时可以得到最优路径；
• 增量式搜索，如 Tree-AA*：重用之前所有 A* 搜索的结果，应对目标节点动态变化的情况。

本章小结（第 2 章）：作者在小结里强调，通用图搜索框架是本章所有算法的基础，核心是 Open 表、Closed 表两张表和不断从 Open 表选点扩展的循环；选点策略不好，“可能变成穷举法”，要遍历整个状态空间图才能找到解。宽度优先、深度优先、代价优先属于盲目搜索；启发式搜索在代价估计较准确时效率更高，启发函数的作用体现在可纳性、更具信息、单调性三个方面。本章的算法主要适用于已知的静态环境；针对未知或动态的环境，研究者发展了一系列改进方法。

第 2 章是一个行动者在不变的环境里找路；第 3 章换成两方或几方对弈，每一方都挑对自己最有利、对对方最不利的走法（第 3 章）。

博弈提供了一个可构造的任务领域，在这个领域中具有明确的胜利和失败。博弈问题复杂性高，而且无法用传统的计算方法来求解，因此成为人工智能研究的重要问题之一。

第 3 章，p.58

博弈的五个要素（第 3 章）：作者把博弈定义为两个以上的参与者按预定规则和各自策略行动、从中取得收益的过程。一个完整的博弈问题有五个要素：

• 参与者：独立决策、独立承担后果的个人或组织；
• 信息：参与者掌握的、对决策有帮助的情报；
• 策略：根据已知信息采取的行动方案，比如石头剪刀布的策略集合是{出石头，出剪刀，出布}；
• 次序：谁先谁后；
• 收益：各方决策后的得失，可以是得分、收入，也可以是情绪价值，常写成收益矩阵，即列出各种策略组合结果的表。

博弈怎么分类（第 3 章）：

• 按出招顺序：静态博弈又叫同时博弈，各方同时出手，如囚徒困境（两名嫌疑犯分开审问，各自决定认不认罪）；动态博弈又叫序贯博弈，有先有后，后手知道先手选了什么，如五子棋。
• 按信息：完全信息指了解别人的特征、策略和收益；完美信息指知道博弈已经发生的全部过程。扑克、桥牌、麻将信息完全但不完美，因为有些信息是各方私有的。随机博弈里还有一个叫“自然”的参与者，比如掷骰子。
• 按收益：零和博弈指各方收益加起来为零，如田忌赛马；非零和博弈如囚徒困境。
• 按人数：双人博弈最常见；多人博弈更复杂，参与者之间可能结盟，联盟还可能破裂或重组。

作者判断：在国际象棋、围棋等完美信息博弈中，算法已胜过人类；在西洋双陆棋等部分随机博弈中，可与人类媲美；在桥牌、麻将等不完美信息的多人博弈中，还不及人类（第 3 章）。

对抗搜索和经典搜索的区别（第 3 章）：求解这类博弈的一类重要方法叫对抗搜索（adversarial search），即在竞争环境里最大化己方收益、最小化对方收益。作者把它和第 2 章的经典搜索列表对比：

• 经典搜索只有一个行动者（书里叫 Agent），环境不变且已知，起点和目标确定后搜一次，就能得到从起点到目标的一整条最优路径；
• 对抗搜索有多个行动者，必须考虑对方怎么走。它得到的是当前局面下的一个最好走步，每进入一个新局面都要重新搜索；又因为有时间限制，通常只能找到近似解。

完美信息博弈：极小极大搜索与剪枝

博弈树（第 3 章）：双人零和完美信息博弈包括井字棋、象棋、围棋、五子棋等：双方轮流走，都了解局面和历史，得失之和为零。以井字棋为例，先手叫 MAX，后手叫 MIN，轮到谁走的局面就叫谁的节点。把所有可能的走法一层层展开，就得到一棵博弈树。站在 MAX 的立场，自己的几种走法里选一个就行，是“或”的关系；对方的每一种走法都必须应对，是“与”的关系。

作者说，不能像第 2 章那样先搜出一条通往胜局的路径再照着走，因为棋往哪里走是双方共同决定的，目标又完全对立。复杂的棋连完整的博弈树都建不出来，只能每次搜一小部分，为当前局面挑一个较好的走步（第 3 章）。

极小极大搜索（第 3 章）：极小极大搜索（minimax search）是博弈树搜索的基本算法。不管搜多深，一次搜索只决定己方这一步，对方走完后要在新局面下重新搜索。算法仿照人下棋的三步：看看有哪些走法，比一比哪个对自己有利，选最有利的。关键在第二步，要靠评估函数打分。

• 静态评估函数只看当前局面，比如棋子的多少、轻重和位置，和设计者的经验关系很大。约定对 MAX 有利时取正值，越大越有利；对 MAX 不利时取负值；势均力敌时为零。
• 静态评估不考虑后面的变化，用在中间局面上可能把人带偏。书中例子：只看静态值，S 下面的 A 是 10、B 是 3，似乎该选 A；可往下看一步，A 之后 MIN 能把局面压到 −6，B 之后最差也有 1，其实该选 B。
• 所以要往前看几步，并假定双方都理性：MAX 总挑评估值最大的走法，MIN 总挑最小的。

做法分三步：以当前局面为根，生成规定深度的博弈树，给最底层的局面打静态分；自下而上倒推，MAX 节点取子节点中的最大值，MIN 节点取最小值；最后选出使评估值最大的那一步。取极大和取极小交替进行，所以叫“极小极大”（第 3 章）。

极小极大搜索算法假定在对方选择最优走步的前提下，最小化己方损失，是一种较保守的方法。

第 3 章 3.2.2 节，p.69

它的问题是节点数随深度按指数增长：每个局面平均有 b 种走法、搜 d 层，大约要看 b 的 d 次方个节点，所以搜不深，棋力受限（第 3 章）。

α-β 剪枝（第 3 章）：作者打比方：初学者只能预判一两个回合，高手能看十几个回合，因为高手经验多，根本不考虑胜算小的走法；只看必要的分支，同样的工夫就能看得更深。α-β 剪枝（alpha-beta pruning）借鉴的就是这一点。

剪枝的基本思想是：一边生成博弈树，一边估计各节点的倒推值，根据已知节点的倒推值范围，及时停止扩展已无必要再扩展的分支。

第 3 章 3.2.3 节，p.69

α 和 β 是两个界限。一个 MAX 节点已算出某个子节点是 −3，它最后的值就不会低于 −3，这个下界叫 α；一个 MIN 节点已经有个子节点是 −7，它的值就不会高于 −7，这个上界叫 β。如果某个 MIN 节点的 β 已经不高于上面某个 MAX 节点的 α，再往下搜也改变不了选择，就停下，这叫 α 剪枝；反过来，MAX 节点的 α 已经不低于上面某个 MIN 节点的 β，也停下，这叫 β 剪枝。剪枝必须用深度优先搜索，边生成边剪（第 3 章）。

书中一个例子里，要访问的节点从 39 个减到 23 个。剪枝选出的走步和不剪枝的极小极大搜索完全一样，只是更快。效果很看搜索顺序：总是先搜到最有利的走法，同样的计算量大约能多看一倍的深度；反过来就一次也剪不了。1997 年，超级计算机“深蓝”战胜国际象棋世界冠军卡斯帕罗夫，用的就是 α-β 剪枝（第 3 章）。

蒙特卡罗树搜索与 AlphaGo

用随机模拟估计好坏（第 3 章）：蒙特卡罗树搜索（Monte Carlo tree search，MCTS）把树搜索和蒙特卡罗算法结合起来，在搜索空间巨大时非常有效。蒙特卡罗算法的意思是：反复随机抽样，用出现的频率去估计概率。用在棋上，就是从某个局面开始随机把棋下完，下很多盘，赢的比例会越来越接近这个局面真实的好坏。它在有限时间里求近似最优解，让更有希望的分支得到更多搜索机会（第 3 章）。

每一轮迭代分四步：

• 选择：从根节点往下，挑最值得看的节点；
• 扩展：给选中的节点随机添一个子节点；
• 模拟：从新节点出发随机走到终局，这段过程不记进搜索树；
• 回溯：把输赢结果沿路传回根节点，更新路上每个节点赢了几次、访问了几次的记录。

时间或算力用完后，通常选访问次数最多的那一步，因为越好的走法被模拟得越多（第 3 章）。

选择时用的打分公式叫置信区间上界（upper confidence bound，UCB），由两项相加：一项是这个节点在模拟中的胜率，代表利用（exploitation）；另一项随访问次数增多而变小，让很少被看过的节点也有机会，代表探索（exploration）。系数 c 调节两项的比重（第 3 章）。

围棋为什么难（第 3 章）：围棋每步平均约有 250 种走法，一盘约 150 步，博弈树远大于五子棋和国际象棋；而且没法像象棋那样按棋子的轻重和多少判断形势，静态评估函数很难设计。研究人员因此提出了 MCTS（第 3 章）。

AlphaGo 的四个部件（第 3 章）：

• 策略网络：给定棋局，预测下一步各种走法的获胜概率；
• 快速走步：策略网络的简化版，速度快约 1000 倍；
• 价值网络：给定棋局，估计黑棋或白棋获胜的概率，相当于静态评估函数；
• 蒙特卡罗树搜索：把前三者组合成完整的系统。

策略网络舍去胜率低的走法，减少搜索的宽度；价值网络让一些分支不必走到底，减少搜索的深度。作者的说法是，策略网络对每一步的选择做取舍，“是一个偏微观的评估”；价值网络判断整盘棋的获胜概率，“是一个偏宏观的评估”（第 3 章）。

MCTS 的长处和短处（第 3 章）：作者认为，它适合分支多、极小极大搜索算不动的问题；每次模拟只扩展一个子节点，一次模拟的耗时与树深成正比，不是按指数增长；它不依赖领域知识，给出规则就能工作，稍作调整就能换一种棋，比如 AlphaZero 不只会下围棋，也能下国际象棋。短处是：树太大时关键节点访问不够；随机性可能让它错过关键的一步；要模拟很多次才收敛，围棋程序要百万次博弈才能达到专业棋手的水平（第 3 章）。

不完美信息博弈：纳什均衡与遗憾最小化

更接近现实，也更难（第 3 章）：作者指出，经济运行、产业布局、网络空间安全等现实决策，大多要在没有掌握全部情况时做出，属于不完美信息博弈，例如猜拳、德州扑克、麻将和拍卖。

在博弈树规模相近的情况下，求解不完美信息博弈问题比求解完美信息博弈问题要困难得多。

第 3 章 3.3 节，p.78

纳什均衡（第 3 章）：只能在猜测的基础上决策时，要求的就不是最优策略，而是各方都能接受的均衡。纳什均衡（Nash equilibrium）以美国数学家纳什（Nash）命名，指多人非合作博弈中，只要别人不改策略，谁也不会单独改策略的状态。纳什（1950）证明：每个参与者只有有限种策略、并允许以一定概率随机选择策略（混合策略）时，纳什均衡一定存在。

书中用囚徒困境说明：A、B 两人都沉默（不认罪），各判 1 年，对双方最好。可不管 B 怎么选，A 认罪都更划算：B 沉默时，A 认罪就被释放，不认罪判 1 年；B 认罪时，A 认罪判 5 年，不认罪判 10 年，B 也一样。所以双双认罪才是稳定的局面，也就是纳什均衡，双双沉默不是，这就是“困境”名称的由来（第 3 章）。

作者说纳什均衡不容易找：对方会不断调整；策略空间大时计算非常复杂（第 3 章）。

遗憾配比（第 3 章）：遗憾最小化算法根据以往对局中的遗憾程度来选策略，用来快速找到近似的纳什均衡。最基本的是 Hart 等（2000）提出的遗憾配比算法，灵感来自人的遗憾（regret）：出石头输给了布，就会后悔没出剪刀。做法是：

• 每轮算一算，换成某个策略能比实际多得多少，逐轮累加；
• 只保留正值，叫正遗憾（positive regrets），负的记为零；
• 下一轮按各策略正遗憾的大小，按比例随机出招；全都为零就完全随机。

书中的石头剪刀布例子：赢得 1 分，输得 −1 分，平局 0 分。第一轮对方出布、己方出石头，没出剪刀的遗憾是 2，没出布的遗憾是 1，所以下一轮出石头、剪刀、布的概率分别是 0、2/3、1/3。随机出招也让对手猜不到自己的打法。如果所有玩家都理性，遗憾配比最终收敛到纳什均衡（第 3 章）。

虚拟遗憾最小化（第 3 章）：遗憾配比适合猜拳这类同时出手的博弈；Zinkevich 等（2007）提出的虚拟遗憾最小化算法把它推广到纸牌这类有先有后的序贯博弈。牌局要画成博弈树，算遗憾时还要按到达各个决策点的概率加权。作者认为它是遗憾最小化算法里最成功、应用最广的：从随机策略开始，每次优化一个参与者的策略，反复迭代，在双人零和博弈中收敛到纳什均衡。

因此，可以认为，人工智能扑克并不是利用对方的弱点取胜，而是找出对方无法取胜的策略。

第 3 章 3.3.2 节，p.82

书中的例子是卡内基梅隆大学开发的德州扑克系统 Libratus：2017 年 1 月，它与 4 名人类顶级选手对战并获胜，这是人工智能第一次在一对一无限注德州扑克中战胜人类顶级选手。后来扩展成的多人系统 Pluribus，2019 年在六人无限注德州扑克的较简单场景下击败了人类专业选手（第 3 章）。

随机博弈

加入骰子（第 3 章）：随机博弈引入随机因素，反映现实的不可预测。典型的例子是西洋双陆棋，每次移动前先掷两个骰子，按点数走。走棋的一方不知道对方会掷出几点，所以要在博弈树里加上代表掷骰子结果的机会节点（CHANCE）。两个骰子共有 21 种不同结果（第 3 章）。

求解用期望极小极大搜索：MAX 节点取最大值，MIN 节点取最小值，机会节点按概率取加权平均。这时评估函数光保证好坏的排序对还不够，数值必须与获胜概率成正比，否则机会节点算出的平均值会误导选择。掷骰子让每层的分支又多了 21 倍，所以实际只能搜得很浅，通常只有 3 层（第 3 章）。

本章小结（第 3 章）：作者归纳，大多数博弈都能用博弈树表示，主要挑战是怎样高效地搜索博弈树。不完美信息博弈还必须考虑对方隐藏的信息，所以更难。作者说，遗憾值还原了日常生活中遗憾的含义：把实际用的策略换成新策略，新策略多产生的那部分收益就是遗憾值；所有动作的遗憾值都足够小时，就可以认为接近纳什均衡（第 3 章）。

第 4 章仍属全书的推理部分。它要解决的是优化问题：通过改变输入，让一个或多个目标函数达到最大或最小。所有可能的输入构成搜索空间，使目标函数最优的那个输入就是最优解。和第 2 章找路不同，这类问题通常不关心怎么走到目标，只关心能不能得到最优解或较好的解，所以也叫局部搜索问题（第 4 章）。

作者说，简单的优化问题可以用数学方法直接求解；特别复杂的问题只能用启发式算法找局部最优解，智能优化算法就是其中一类，灵感来自人类智能、生物群体的社会性和自然现象。组合优化指从大量排列组合里挑出最好的一种。

作为一类随机搜索算法，尽管智能优化算法在理论上不如传统优化算法完善，往往不能保证解的最优性，但是在实际应用中表现出运行速度快、适合并行处理、通用性强等特点，可以为组合优化等 NP 问题提供有效的解决方案。

第 4 章，p.89

本章讲遗传算法、蚁群优化算法、粒子群优化算法和模拟退火算法，每种都拿旅行商问题做例子（第 4 章）。

旅行商问题（第 4 章）：推销员从一个城市出发，走遍 n 个城市、每个城市只经过一次，再回到起点，求最短的路线。它是典型的 NP 难组合优化问题（规模一大就很难在合理时间里求出精确解），有多个局部最优解。车辆路由、集成电路布局、机器人导航等都是它的推广。书中的中国旅行商问题（China traveling salesman problem，C-TSP）要求在中国 34 个省会级城市之间找最短路线（第 4 章）。

遗传算法

模仿生物进化（第 4 章）：进化算法（evolutionary algorithms，EA）把适者生存的进化规律变成算法。和第 2 章的搜索不同，它不从一个起点出发，而是从一组解出发，改进成另一组更好的解。2006 年，美国国家航空航天局的空间技术-5（space technology-5，ST-5）航天器搭载的天线，形状就是由进化算法设计的（第 4 章）。

遗传算法是进化算法中影响最普遍的一种，最早由 Holland（1975）提出。术语都借自生物学：一组可行解叫种群，每个解是一个个体，解的编码叫染色体，编码的每个分量叫基因，评估函数的值叫适应度。每一代通过选择、交叉、变异产生新一代种群，若干代后，种群的适应度在理想情况下会接近最优（第 4 章）。

一步步怎么做（第 4 章）：

• 编码：把解变成染色体。最常用的是二进制编码，把解写成一串 0 和 1，方便交叉和变异，但高维问题里位串很长、效率低；另有实数编码和整数编码。
• 定适应度函数：按目标函数给个体打分。它必须是正值，不需要求导，也不要求函数连续。
• 生成初始种群：种群太小容易陷入局部最优，太大则计算量高，一般取 10—200 个。
• 选择：轮盘赌选择法让被选中的概率与适应度成正比；锦标赛选择法随机抽几个个体，留下最好的；精英选拔法把最好的个体直接复制到下一代，收敛快，但可能过早收敛。
• 交叉：两个父代按交叉概率交换一部分基因。作者说，正如基因重组在生物进化中起核心作用，交叉在遗传算法中也起核心作用。方式有单点交叉、多点交叉、统一交叉，以及为排列类问题设计、能把先后顺序传给子代的戴维斯顺序交叉。
• 变异：按变异概率随机改动个别基因，比如翻转一位、交换两个基因、把一段打乱或倒过来。它一是在最优解附近做小范围搜索，二是维持种群多样、防止过早收敛。
• 终止：最优个体够好，或适应度不再上升，或达到预设代数就停。

作者强调，保持种群的多样性对遗传算法的成功至关重要。一个适应度高的个体在种群中占了绝对多数，叫过早收敛，这时要缩小它的适应度、降低竞争力；到后期，平均适应度已接近最好的适应度，很难再改善，叫停滞现象，这时要调整适应度的比例，提升一部分个体的竞争力（第 4 章）。

用遗传算法解旅行商问题（第 4 章）：给每个城市编号（1 北京、2 上海、3 广州……），一条路线就是一串不重复的编号；适应度取路线总长度的倒数，路线越短分越高。交叉用戴维斯顺序交叉；变异不能只改一位，那样会让某个城市走两次、某个城市漏掉，所以要随机交换两个城市的位置。书中的运行结果显示，到第 786 代，路线已远好于初始路线；算法有随机性，每次结果不完全相同（第 4 章）。

长处和不足（第 4 章）：作者称遗传算法是最受欢迎的受生物启发的智能优化算法之一：同时评估一群解，不易陷入局部最优，便于并行；只用适应度，不求导，适用面广；适合搜索空间巨大、参数众多的问题。不足是参数缺少通用的设置方法，计算量大，结果有随机性、不保证最优。它的经典应用是函数优化，在车间调度、装箱、任务分配等组合优化难题上也非常有效（第 4 章）。

蚁群优化算法

蚂蚁怎么找到最短路（第 4 章）：群体智能（swarm intelligence）指由简单个体组成的群体，在与环境和彼此的交互中表现出的智能行为。蚂蚁在走过的路上释放信息素，信息素会逐渐挥发，后来的蚂蚁按浓度选路。路越短，单位时间内走过的次数越多，留下的信息素越多，被选中的可能越大，形成正反馈，最后蚂蚁都聚到最短的路上。蚁群优化（ant colony optimization，ACO）算法模拟的就是这种集体寻径行为：每只蚂蚁走过的路线代表一个可行解，找到的最短路线就是最优解（第 4 章）。

作者认为，蚂蚁的智能来自简单规则带来的多样性和正反馈：多样性让蚂蚁不会走进死胡同、陷入无限循环；正反馈把有用的信息保存下来，强化学习效果。

二者的巧妙结合使智能行为涌现，如果多样性过剩，正反馈不足，将导致过多的随机运动，难以到达稳定状态；如果多样性不够，正反馈过强，将导致行为僵化，当环境变化时，蚁群不能进行相应调整。

第 4 章 4.2.1 节，p.100

算法怎么跑（第 4 章）：先给各条路设定初始信息素浓度；所有蚂蚁从起点出发，每只按信息素浓度以一定概率选下一站，直到都到达目标；然后记下当前最好的解，全局更新信息素，分两步：先挥发，旧的信息素逐渐消逝；再增强，每只蚂蚁按自己解的质量留下相应的信息素。达到最大迭代次数或结果稳定就停（第 4 章）。

用在旅行商问题上，最早的是蚂蚁系统（ant system，AS）。人工蚂蚁有三条规则：走过的路释放信息素；按路的长短和信息素浓度以一定概率选下一个城市；去过的城市不再去（用禁忌表记下），保证路线有效。选路时，信息素越浓、两城距离越近，被选中的概率越大。信息素怎么留有三种算法：蚁周算法等蚂蚁走完一整圈，按总路程留，总路程越短留得越多；蚁量算法每走一段，按这一段的长短留；蚁密算法每走一段留固定的量。蚁周算法用了全局信息，效果最好，通常作为基本模型（第 4 章）。后来的最大最小蚁群系统（max-min ant colony system）给每条路的信息素设上下限：下限让蚂蚁仍有机会探索别的路，上限保证经验仍有引导作用（第 4 章）。

长处、短处和用途（第 4 章）：作者列出的优点是：正反馈让搜索不断逼近最优；个体通过改变环境、感知环境来间接通信；分布式并行，效率高；不容易陷入局部最优；不易受个别个体的影响。缺点是搜索时间长，容易停滞，即搜到一定程度后所有个体的解完全一样，无法再探索新路。改进办法有调整信息素、让侦察蚁和搜索蚁分工、加入扰动等。蚁群优化尤其擅长离散的组合优化，典型应用有网络路由优化、飞行器航迹规划和电力系统优化（第 4 章）。

粒子群优化算法

向鸟群学习（第 4 章）：鸟群为什么能保持几乎相同的速度飞行而不乱？Reynolds（1987）提出一个模型：每只鸟只守三条规矩，不和邻近个体相撞，和邻近个体速度一致，飞向鸟群中心。受此启发，Kennedy 等（1995）提出了粒子群优化（particle swarm optimization，PSO）算法。

做法是把每只鸟抽象成一个没有质量和体积的粒子，它的位置代表一个候选解；鸟群在天空找食物，就是粒子在搜索空间里找最优解。每个粒子记住两个位置：自己找到过的最好位置（pbest），和整个群体找到过的最好位置（gbest）。每一步，粒子的新速度由三部分相加：

• 惯性：按原来的方向接着飞；
• 认知项：被拉回自己到过的最好位置，代表自身记忆的影响；
• 社会项：被吸引到群体的最好位置，代表群体信息的影响。

后两项各乘一个随机数，增加随机性。新位置等于旧位置加上新速度（第 4 章）。

参数的经验值：粒子一般取 20—40 个；惯性的权重大利于全局搜索，小利于局部细找；速度要设上下限，太快会飞过最优解，太慢则收敛太慢（第 4 章）。作者指出，和其他群体智能算法一样，PSO 的种群多样性和收敛速度之间存在矛盾，各种改进都是为了在加强局部搜索的同时保持多样性，防止收敛太快而早熟（第 4 章）。

和遗传算法比（第 4 章）：两者都从一组随机初始解出发迭代搜索。不同之处，作者列了三条，第一条是：

遗传算法强调适者生存，不好的个体在竞争中被淘汰，而粒子群优化算法强调协同合作，不好的个体通过学习向好的方向转变。

第 4 章 4.3.3 节，p.107

另外两条是：遗传算法里最好的个体靠多产生后代来传播基因，PSO 里最好的个体靠吸引别的个体靠近来施加影响；遗传算法的选择只和上一代有关，PSO 还用到历史信息，即 pbest 和 gbest（第 4 章）。

作者认为 PSO 易于实现、要调的参数少、鲁棒性好、收敛较快；缺点是精度较低、容易发散，加速度系数、最大速度等设得不好会错过最优解，数学理论基础也不够牢。它已用于图像处理、神经网络训练、电力系统设计等（第 4 章）。

模拟退火算法

从冶金得来的灵感（第 4 章）：退火是冶金学术语，指把材料加热，再按特定速率冷却。加热后原子离开原位随机移动，慢慢冷却时能量逐渐降低，最后有序地凝固，很可能停在比原先更低的内能位置。Metropolis 等（1953）提出了模拟退火（simulated annealing，SA）的最初思想，Kirkpatrick 等（1983）把它成功引入组合优化。对应关系是：目标函数相当于能量，候选解相当于物体的状态，控制参数相当于温度，最优解相当于能量最低的状态（第 4 章）。

为什么要接受更差的解（第 4 章）：拿爬山法对照。爬山法从一个随机起点出发，每次走到邻近解里最好的那个（书中为便于比较改成求最小值），简单、收敛快，但到了一个局部的低谷就停住，因为往哪个方向挪一点都不会更好。

不同于爬山法，模拟退火算法的解不要求迭代更新后的解一定比之前的解更好，它引入了一个接受概率。

第 4 章 4.4.1 节，p.109

这条规则叫 Metropolis 准则：新解更好就接受；更差的也以一定概率接受，变差得越多、温度越低，接受的可能越小。这样，温度高时能翻过小山丘、跳出局部最优，温度降下来后就逐渐稳定在全局最优附近（第 4 章）。

初始温度要足够高，越高越可能得到高质量的解，但也越耗时；最简单的降温办法是每次乘一个 0.8—0.99 之间的系数；终止温度接近 0（第 4 章）。解旅行商问题时，新路线由邻域操作产生：把两个城市之间的一段路线倒过来，把一个城市挪到另一个城市后面，或者把两个城市对调（第 4 章）。

作者认为，模拟退火是通用的随机搜索算法，能以一定概率跳出局部最优、最终趋于全局最优，结果不依赖初始值，能为 NP 复杂度的优化问题提供近似解法；代价是要求较高的初温、较慢的降温、较低的终温和每个温度下足够多的采样，收敛过程较长。它用于集成电路设计、神经网络训练、图像恢复和各种组合优化问题（第 4 章）。

本章小结（第 4 章）：作者归纳，传统优化方法一般是确定性算法，碰上高维、多模态等复杂问题时，速度和收敛性难以满足要求。这一章的问题往往与路径无关，只需存储当前状态，对它做评估和修改。四种算法的共同点是都能跳出局部最优，占内存少，速度较快，能在有限时间内、在很大的或连续的状态空间里找到最优或近似最优解。

全局搜索用于快速定位最优解的范围，而局部开发用于锁定最优解存在的区域并进一步寻找最优解，只有两部分达到一个良好的平衡状态才能有较好的求解效果。

第 4 章 4.5 节，p.112

四种算法的区别在于来源不同、平衡全局探索和局部开发的办法不同，比如模拟退火主要调一个超参数，蚁群优化要同时调好几个参数。作者还列了近年提出的新算法，如人工蜂群、蝙蝠、布谷鸟搜索、麻雀搜索等，认为这一领域正处于快速发展期，在工程领域前景广阔（第 4 章）。

这一章在哪里（第 5 章）：本章是推理部分的最后一章。作者说，从人工智能学科诞生起，逻辑推理就是研究重点之一：用逻辑方法对符号及其关系做演算，是符号主义学派的重要研究内容，“逻辑理论家”被认为是有史以来开发的第一个人工智能程序。经典逻辑又叫二值逻辑，包括命题逻辑和谓词逻辑，任何公式的真值只能是真或假，适合解决能用经典逻辑语言描述的确定性推理问题，特点是精确、严密。全章以自动定理证明为主线。

为什么要形式化（第 5 章）：自然语言有歧义、有冗余，还在不断演变，意思常常要靠上下文，计算机难以直接存储和处理。经典逻辑推理先把知识写成命题公式或谓词公式这样的符号，再研究通用的推理规则。以三段论为例：大前提“所有人都会死”，小前提“苏格拉底是人”，结论“苏格拉底会死”。抽象成任意 x 有属性 y、A 是 x、所以 A 有属性 y 这样的形式以后，x 换成动物、A 换成牛顿，推理照样成立。作者据此说，逻辑推理有通用性（只看形式，不管内容），也有严密性（只要形式化正确，结论就一定成立）。

形式化的好处在于：具体的问题一旦形式化为符号，在推理求解过程中就不用再关心各符号的具体含义，可以利用与问题无关的通用方法来演绎推理，如三段论。

第 5 章 5.1.1 节，p.115

自动定理证明（第 5 章）：自动定理证明就是把人证明定理的过程，变成计算机上自动进行的符号演算。有观点认为，符号主义学派的思想源头就是它；它还能用于医疗诊断、信息检索、规划制定和问题求解。证明定理，就是证明由前提推出结论永远成立。直接证很难，通常用反证法。书里列了几个节点：1930 年 Herbrand 提出 Herbrand 定理，打下理论基础；1965 年 Robinson 提出归结推理，自动定理证明进入应用阶段；1976 年四色定理（四种颜色足以给地图上色，且相邻区域颜色不同）成为第一个主要借助计算机证明的定理；1977 年吴文俊院士提出几何定理机器证明的“吴方法”。作者认为，人工智能至今还不能自己提出并证明全新的定理，但辅助人证明定理已经非常有效，既能加快证明，也能帮人发现新定理。

命题逻辑：从蕴含式到归结

命题和联结词（第 5 章）：命题（proposition，能判断真假的陈述句）只能取真或假；疑问句、祈使句、感叹句和悖论都不是命题，例如“人工智能会超过人类智能吗？”就不是。命题逻辑（propositional logic）研究命题之间的关系。不能再拆的命题叫原子命题（atomic proposition），用大写字母表示；把原子命题连起来的符号叫联结词（logical connective），共五种：析取（disjunction，“或”）、合取（conjunction，“与”）、蕴含（implication，即如果前者成立、那么后者成立，前面的叫前件，后面的叫后件）、双向蕴含（bidirectional implication，“当且仅当”）、非（negation，否定）。比如“无侦-7 和翼龙-10 都是高空侦察无人机”，就是两个原子命题的合取。

蕴含式的特别之处（第 5 章）：蕴含式只在前件为真、后件为假时才为假；前件为假时，不管后件真假，整个式子都为真。前后件之间也可以毫无关系，“如果 GPS 信号丢失，那么电池状态良好”也能写成蕴含式，这和日常说的条件句不一样。两个公式在所有取值下真假都相同，才算等价。逐一列真值表来证明等价太烦琐，书里给出一组常用的等价式（否定之否定、德·摩根律、交换律、分配律、结合律、逆否律等）供变形使用。作者特别强调蕴含等价式：P 蕴含 Q，等价于非 P 或 Q。这说明蕴含式和析取式本质上相同，可以互换。例如“只要进入密闭环境，就会迷路”为真，就意味着讨论范围内的机器人“要么处于未进入密闭环境，要么处于迷路状态”。

自然演绎推理和它的难处（第 5 章）：自然演绎推理模仿人的推理，从已知为真的事实出发，直接用推理规则推出结论。最基本的两条：假言推理，已知“若供电电压过高，则控制电路损坏”和“供电电压过高”，推出“控制电路损坏”；链式推理（又叫假言三段论），再加上“若控制电路损坏，则机器人失去控制”，推出“若供电电压过高，则机器人失去控制”。机器做这件事，核心是判断某个事实是否符合某条定理的条件。形式简单时容易匹配，复杂时就难了。例 5.2 的定理是：无人机载荷重且油箱容量小，续航能力一定不好。已知某型无人机载荷重，续航却好。人一想就知道它油箱不小，可这个事实和定理的条件在形式上对不上，机器推不下去。同一条定理能改写出 6 种等价的蕴含式，用蕴含式推理，就得把这些形式全部给出，否则可能因为形式不符而卡住。

改写成析取式：归结推理（第 5 章）：把这 6 种形式都按蕴含等价式改写成析取式，结果完全相同：载荷不重，或油箱容量不小，或续航不好。假言推理和链式推理改写以后，也变成同一条规则，这就是归结推理（又叫消解推理）。几个概念：文字（literal）是原子命题或它的否定；子句（clause）是一个文字，或几个文字的析取；一对互为否定的文字叫互补文字，含互补文字的两个子句叫亲本子句。归结就是：两个亲本子句消去一对互补文字，把剩下的部分用“或”连起来，作为结论。作者说，这种方法规则简单、便于编程，使逻辑推理演算达到了可实用的程度，被认为是自动推理特别是自动定理证明领域的里程碑式成果。

使用时有几条规矩：归结前要把事实和定理都化成子句的集合，子句内部是析取，子句之间是合取，所有子句合起来叫合取范式（conjunctive normal form）；每次只能消去一对互补文字；如果两个子句各只剩一个文字且正好互补，比如 P 和非 P，归结结果为“空”，记作 nil 或□。空意味着参与归结的子句互相矛盾，这是用归结证明定理的关键。命题公式化成子句集分四步：消去蕴含符号；否定深入，让“非”只作用在单个原子命题上；转成子句的合取；写成子句集。

用归结证明定理（第 5 章）：一条定理可以写成：条件 1 且……且条件 n，那么结论。要证明它永远为真，等价于证明所有条件成立而结论不成立永远为假。所以做法分三步：把结论的否定和所有条件合在一起；化成子句集；反复归结，直到得出空。书里说，归结推理是完备的：只要子句集确实不可满足，就一定存在一条归结到空的路径。

假设结论不成立，然后通过推理发现其与已知条件之间存在矛盾，从而证明原结论成立，这正是反证法的思想。

第 5 章 5.2.3 节，p.123

例 5.4 是移动机器人自检：驱动系统的状态能直接感知，传动系统的好坏不能。已知定理是驱动系统和传动系统都正常，机器人就向前移动；事实是驱动系统正常，机器人却没动；要证传动系统不正常。把事实、定理和结论的否定（传动系统正常）合起来，化成四个子句，依次归结得到空，结论得证。这样用树形画出的归结过程，叫归结反驳树。

命题逻辑的局限（第 5 章）：

命题逻辑的推理过程精确，易于理解。但是，命题逻辑以语句为单位进行演算，表达能力非常有限。命题逻辑甚至不能证明三段论的合法性。

第 5 章 5.2.3 节，p.124

原因是，“所有的人都是要死的”“苏格拉底是人”“苏格拉底是要死的”在命题逻辑里只是三个互不相干的命题。命题逻辑也看不到句子内部：“无侦-7 是无人机”和“翼龙-10 是无人机”表达不出共同的属性；“坦克在运输车的后面”和“运输车在坦克的后面”表达不出同一种关系。要把命题拆成对象和属性（或关系），就需要谓词逻辑。

谓词逻辑：置换、合一与标准化

谓词公式（第 5 章）：谓词逻辑（predicate logic）用谓词等符号描述对象之间的关系。谓词公式由四部分组成：个体词，指具体的事物或抽象的概念，包括常量（如小王）、变量（如 x、y、z）和函数（如“小王的父亲”）；谓词，描述对象的状态、性质和对象之间的关系，如某物在另一物后面；量词，全称量词表示所有、任意，存在量词表示存在、有些；再加上联结词。谓词把对象映射为真或假，函数则把对象映射为另一个对象。本章只讨论一阶谓词：谓词只描述个体，量词只约束变量。把自然语言写成谓词公式时，全称量词下一般用蕴含，如“任意整数都是有理数”写成：对所有 x，x 是整数则 x 是有理数；存在量词下一般用合取，如“某些机器人是有轮子的”写成：存在 x，x 是机器人且 x 有轮子。

置换与合一（第 5 章）：“所有人都会死”化成子句是：x 不是人，或 x 会死。它和“苏格拉底是人”形式上不完全互补，不能直接归结。用苏格拉底替换 x 以后，两者成了亲本子句，归结出“苏格拉底会死”。这种用项（常量、变量或函数）替换变量的操作叫置换（substitution）。规矩是：只有变量能被置换；同一变量要整体替换；不能用含 x 的函数去替换 x；置换的先后不能随意交换。能让几个公式变得一模一样的置换叫合一元（unifier）。合一元往往不止一个，其中只做最必要替换的那个叫最一般合一元（the most general unifier, MGU），其他合一元都可以由它再叠加一层置换得到。归结时必须用它，因为变量一旦换成常量就不能再换。

如果在归结时引入了非必要的置换，将一些变量过早地转换为确定的个体，无法再置换为其他变量或常量等，就可能导致归结失败。

第 5 章 5.3.2 节，p.129

八步标准化（第 5 章）：命题公式化成子句集只要 4 步，谓词公式因为有变量和量词，要 8 步：消去蕴含；否定深入（括号外的否定会改变括号内的量词）；变量标准化，让每个量词约束的变量各有自己的名字；消去存在量词，不在任何全称量词辖域内的，直接换成一个新常量，在全称量词辖域内的，换成以那些全称变量为参数的新函数，叫斯科伦函数（Skolem function），比如对每个 x 都存在一个 y，就把 y 写成 x 的函数；消去全称量词（剩下的变量都受全称量词约束，直接去掉）；转成合取范式；写成子句集；最后给变量改名，使每个变量只出现在一个子句里。

谓词归结证明（第 5 章）：宏观上和命题归结完全一样，也是结论取否定、化成子句集、归结到空；区别在于每次归结前，要先找最一般合一元，使两个子句成为亲本子句。例 5.8 是机器人找箱子：已知 27 号房间的所有箱子都比 29 号房间的小，箱子 A 在 27 号或 29 号房间，箱子 B 在 27 号房间且不比 A 小，求证 A 在 27 号房间。假设 A 不在 27 号，就推出 A 在 29 号；再经过置换，推出 B 比 A 小，与已知矛盾，归结出空。

作者指出，事先不知道哪一对子句能最快归结出空，只能逐对比较，能归结的都归结，既费时间又占存储，效率低。于是有了归结策略。一类是删除策略，删掉永真式等无用子句，缩小范围；另一类是限制策略，限制哪些子句可以参与归结，减少盲目性，例如支持集策略（每次归结至少有一个子句来自结论的否定，或由它推出）、线性输入策略（每次有一个子句来自原始子句集）、祖先过滤。支持集策略和祖先过滤是完备的，线性输入策略不能保证归结出空。

从证明到求解（第 5 章）：很多时候没有现成的结论要证，而是要回答结论是什么。办法是构造一个带未知数的结论，把问题求解变成定理证明。例 5.9 问箱子 A 在哪个房间：构造“存在房间 u 满足 A 在 u 中”的结论，把它的否定（对任何房间 u，A 都不在 u 中）加进子句集归结。归结过程中用 27 替换了 u 才得到空，答案就是 27 号房间。实际应用中，常给含 u 的子句再加一个 Answer(u)，用“或”连上，归结的终点就不是空，而是 Answer(27)，答案可以直接读出。作者提醒，问题求解本质上仍是定理证明，构造的结论在形式上必须正确，否则得不到正确答案。

作者的小结（第 5 章）：命题逻辑可以看作谓词逻辑的特例（也叫零阶谓词），两者的推理方法基本一致；归结证明的原理是反证法；谓词归结的难处在于处理变量和量词，置换只能替代变量，归结必须用最一般合一元。作者认为谓词逻辑有四个优点：自然，接近自然语言；精确，真值只有真和假，适合确定性知识；严密，能保证知识库里新旧知识逻辑一致、推理结果正确；容易实现，便于转成计算机内部形式，也便于增删修改。局限同样明显：不能表示不确定性知识；不便加入启发性知识和元知识（关于如何运用知识的知识）；推理效率低，事实一多、规则盲目使用，就可能组合爆炸。

谓词逻辑利用谓词公式描述对象的性质、状况和关系，是人工智能领域中使用最早的知识表示方法，也是研究得最深入、理解最全面的一种知识表示方法。

第 5 章 5.4 节，p.135

谓词逻辑用在自动问答（QA3 系统）、机器人行动规划（STRIPS 系统）、问题求解（PS 系统）等系统中，也擅长硬件和软件的合成与验证这类能严格定义概念的场景（第 5 章）。

这一章在哪里（第 6 章）：第 6、7 章是全书的知识部分，本章讲确定性知识，第 7 章讲不确定性知识（前言）。作者说，获取、表示和处理知识的能力，是人类智能区别于其他生物智能的重要特征；知识表示与推理是人工智能知识期的代表性成果。前面的状态空间搜索和谓词逻辑推理属于推理期，靠较少的知识和较复杂的搜索得出结论。本章讲四种方法：产生式、语义网络、框架和知识图谱。

本章所讨论的知识表示与推理则是在大规模的知识库基础上，通过相对简单的推理方法和较少的推理步骤得到结论，适合于解决严重依赖知识的领域问题。

第 6 章，p.139

知识、知识表示和推理

数据、信息、知识（第 6 章）：书里用自动驾驶举例。“交通指示灯”“绿灯”是数据，即对事物的符号记录；“交通指示灯显示为绿灯”“车辆通行”是信息，即在某个语境中有含义的数据；“交通指示灯显示为绿灯，车辆可以通行”是知识，它在两条信息之间建立了联系。数据是信息的基础，信息是知识的前提。知识有三种分法：

• 按作用：事实性知识（factual knowledge，描述概念、属性、状态、关系，如“汽车有发动机”）；过程性知识（procedural knowledge，规则、定律、经验，如遇到雨雪天气车辆要慢行）；控制性知识（control knowledge，又叫元知识，讲怎样运用知识去求解）。
• 按确定程度：确定性知识（certain knowledge，真假能明确判断）和不确定性知识（uncertain knowledge，如明天降雨概率 70%）。
• 按能否形式化：显性知识（explicit knowledge，能用形式化语言写出来，本章知识库里的都是）和隐性知识（tacit knowledge，如图像分类神经网络里存的知识）。

作者还说，知识有主观性，也只有相对正确性，比如经典力学在宏观适用、在微观不适用。

知识表示（第 6 章）：知识表示就是把人类知识符号化、输入计算机，用约定的形式结构描述知识，并能转成机器内部的形式。书里概括了 8 种典型方法：状态空间、谓词逻辑、产生式、语义网络、框架、面向对象、基于可扩展标记语言（extensible markup language, XML）的方法，以及本体（在人工智能里指“共享概念模型的明确形式化规范说明”，用来统一领域概念、实现知识共享）。作者认为，现有方法各有局限，实际知识库往往同时用好几种。能体现知识间内在联系、有层次的，叫结构化表示（语义网络、框架）；否则是非结构化表示（状态空间、谓词逻辑、产生式）。

推理的分类（第 6 章）：推理是从已知判断推出新判断的过程，要解决两件事：推理方法和推理控制策略。书里从六个角度给推理方法分类，要点如下：

• 演绎推理（deductive reasoning）由一般到具体，前提为真、形式有效，结论就一定为真；归纳推理（inductive reasoning）从足够多的实例归纳出一般结论，比如见过的车都有轮子，就认为车有轮子，可磁悬浮列车就没有轮子；缺省推理（default reasoning）在知识不完全时先默认某些条件成立，发现默认错了，就撤销它和由它推出的所有结论。
• 单调推理（monotonic reasoning）中，新知识不会推翻已有结论，经典逻辑的演绎就是这样；非单调推理（non-monotonic reasoning）可能要否定已有结论，归纳和缺省推理都属于这一类。作者说，非单调推理是人们常用的一种思维方式。
• 还可以分为确定性与不确定性推理、启发式与非启发式推理，以及基于知识的推理、统计推理和直觉推理。直觉推理凭常识，比如行人看到汽车驶来立刻躲开；作者说，在机器上实现它还非常困难。

推理方向（第 6 章）：正向推理从已知事实出发，不断推出新事实，直到得到解，缺点是盲目，会推出很多无关的结论。反向推理先假设一个目标，再找支持它的证据，目的性强，便于向用户解释，缺点是初始目标选得盲目。双向推理两头同时进行，在中途“碰头”就结束；难处是两边的比重和碰头时机不好把握。

匹配与冲突消解（第 6 章）：推理时要拿已知事实和知识逐一比较，叫匹配。一条都匹配不上，说明缺知识或问题超出了范围；匹配上多条，就是发生了冲突，要按某种策略挑一条，叫冲突消解（conflict resolution）。书里的例子：规则一是车到十字路口遇红灯就停车等待；规则二是车到十字路口遇红灯、靠右行驶且前面没车，就可以右转。如果定下条件越多越优先，推理机就用规则二。常用策略都是给知识排序，如条件更具体的优先、与最新事实匹配的优先、匹配度高的优先。

产生式

规则和系统（第 6 章）：作者说，产生式是应用最广泛的知识表示方法，是专家系统首选的表示方法，例如测定分子结构的 DENDRAL、估计矿藏的 PROSPECTOR，以及 MYCIN。产生式表示两类知识：事实，用三元组写成（对象，属性，值），如这条路线长 40 公里；规则，写成 IF P THEN Q，如“IF 汽车超速 THEN 立即减速”。作者认为蕴含式只是产生式规则的特例：蕴含式只能表示精确的知识，产生式规则还能表示操作、变换，也能表示不确定性知识。

产生式系统（production system）由三部分组成：全局数据库，存放已知事实、中间结论和待证结论，内容不断变化；产生式规则集，即领域知识的集合；控制系统，即推理机，负责挑规则去匹配、做冲突消解、执行规则、判断何时结束。它可以正向、反向或双向推理；预测、监视、控制问题适合正向，诊断问题适合反向。书里自动驾驶右转的例子有 5 条规则：已知红灯、路口没有其他车辆、有行人在人行横道上，正向推理匹配到红灯且有行人则不可右转那一条，结论是不能右转。

和图搜索的关系（第 6 章）：初始事实对应初始节点，待证结论对应目标节点，规则对应状态转换规则，全局数据库对应 Open/Closed 表，控制策略对应搜索策略。

可以认为，问题求解是目的，图搜索是方法，产生式系统是形式。

第 6 章 6.2.3 节，p.151

作者认为，产生式适合表示彼此关系不密切、没有层次结构的知识，以及经验性、不确定性的知识。优点是规则各自独立，易于建库和修改，推理直观，便于解释；缺点也来自独立：体现不了知识间的联系，规模大了难保一致；每一步都要匹配，规则多时效率低。

语义网络与框架

语义网络（第 6 章）：语义网络（semantic network）由 Quillian 在 1968 年研究人类联想记忆时提出。它是带标识的有向图：节点表示实体、概念或状态，带标识的弧表示关系，基本单元是三元组（节点 1，弧，节点 2）。常见关系有实例关系 ISA（Is-A，如 R1 是一辆自动驾驶汽车）、分类关系 AKO（A-Kind-Of，如自动驾驶汽车是一种轮式移动机器人）、组装关系、属性关系，以及集合与成员关系 AMO（A-Member-Of）。多元关系要拆成几个二元关系，必要时加中间节点。

推理有两种。一是继承（inheritance）：沿 ISA、AKO 等弧把上层的描述传给下层，包括值继承（value inheritance，轮式移动机器人的移动机构是轮子，自动驾驶汽车和 R1 也是）、“如果-需要”继承（if-needed inheritance，需要时调用程序计算）、默认继承（default inheritance，不与事实冲突就沿用默认值）。作者说，继承推理是非单调的，下层的特殊信息可以抵消上层的一般信息，叫继承抵消。例 6.4：办公机器的电源是墙上插座，但机器人例外，用电池；扫地机器人 R2D2 继承离它最近的父节点，电源是电池。二是匹配（matching）：把问题写成含未知部分的网络片段，到知识库里找能对上的部分，比如问摄像头的特点，就得到“成本低、采集信息丰富”。作者说，匹配为搜索引擎知识问答系统设计提供了基础。语义网络的优点是结构性、联想性、自然性；缺点是不够严格（节点和弧的含义由用户自定，推理正确性无法保证），还可能组合爆炸。

框架（第 6 章）：框架（frame）理论由 Minsky 在 1974 年提出，基于心理学研究：人的记忆里存有大量典型场景，遇到新情况，就挑一个场景的结构来套，再补充、修改细节。比如已有轿车的框架，看到加长型轿车就套用它，再加一个“车身长度”属性。框架由框架名和若干槽组成，槽描述某一方面的属性，槽下可以再分侧面，槽值也可以是另一个框架的名字。框架按抽象程度分层：书里的<教师>框架有超类、工作、性别、学历等槽，工作的范围是教学、科研，缺省为教学；<大学教师>是它的子框架；<教师-1>是<大学教师>的实例，填上了李明、副教授等具体信息。推理靠匹配和填槽：要找男性、40 岁以下、副教授、身体健康、会英语的教师，就把条件写成问题框架逐槽比对，匹配到<教师-1>，填上姓名李明；填槽可以继承上位框架的槽值，也可以调用槽上附带的程序（if-needed、if-added 等）。

框架与语义网络没有本质的区别，可以认为框架是一种具有复杂结构的语义网络。

第 6 章 6.4.2 节，p.159

作者说，框架为后来的人工智能框架语言奠定了基础，也为面向对象语言提供了思路，被认为是面向对象系统的前身。缺点是没有完整的理论体系，槽和侧面缺乏清晰的语义，多重继承会带来歧义，不同框架系统难以对齐。

知识图谱

为什么出现（第 6 章）：作者说，知识表示的最新发展是知识图谱。20 世纪 70～80 年代的知识工程和专家系统，在规则明确、边界清晰、应用封闭的场景里取得了成功，但严重依赖专家，适应不了大数据时代开放应用和规模化的需求。知识图谱靠数据驱动或众包，大规模自动获取知识，解决了知识获取的瓶颈。

知识图谱作为一种大规模语义知识库，可由知识规模上的量变带来知识效用的质变。

第 6 章 6.5 节，p.161

是什么（第 6 章）：知识图谱用图描述对象及其关系，本质上是大规模的语义网络，只是规模更大、构建方式更多样。它用资源描述框架（resource description framework, RDF，由万维网联盟 World Wide Web Consortium, W3C 制定的标准数据模型）表示知识，每条知识是一个三元组（triples）：主语、谓词、宾语，如（Beijing，capital_of，China）表示北京是中国的首都。知识图谱的概念由谷歌在 2012 年提出，目的是增强信息检索；谷歌强调“things，not strings”，意思是搜索引擎从匹配字符串变成搜索事物。书中举例：传统搜索“自动驾驶汽车是机器人吗？”只能得到相关新闻，加入知识图谱后直接给出答案“是”。

分类与构建（第 6 章）：按覆盖范围，分通用知识图谱（general-purpose knowledge graph, GKG，重广度，如 DBpedia）和领域知识图谱（domain-specific knowledge graph, DKG，靠行业数据构建，质量要求更高）；按知识类型，分常识知识图谱（commonsense knowledge graph, CKG，如 WordNet）和百科知识图谱（encyclopedia knowledge graph, EKG，重事实）。构建方式有自顶向下（先定本体和数据模式，再填实体，早期多用）和自底向上（先从开放数据抽取实体，再建关系，现在大多如此）。流程分三步：

• 知识抽取：从结构化、半结构化、非结构化数据里抽取实体、关系、属性。难点在非结构化数据，要用自然语言处理做实体命名识别、关系抽取、实体统一和指代消解。
• 知识表示：主要用 RDF 三元组，并可推理补全，比如由 R1 是自动驾驶汽车、自动驾驶汽车是一种轮式移动机器人，推出 R1 是轮式移动机器人；也可以把实体和关系表示成向量，按相似度预测新的三元组。
• 知识融合：整合不同来源的知识，剔除冗余和错误，并持续更新。

书里用北京冬奥会 5G 无人车火炬接力的一段文字演示全过程：识别出时间、地点、系统等实体；从“依托”“部署”“完成”等词判断实体间的关系；把“5G”和“第五代移动通信技术”统一起来；判断“这”指的是“无人车火炬接力”。

特点和难处（第 6 章）：和传统语义网络最明显的区别是规模：书中的图示标出，传统专家系统时代的知识规模不超过百万级，现代商用知识图谱已达百亿至千亿级。此外还有语义丰富、质量精良、结构对机器友好。作者说，优点与缺点相伴而生：为了让更多知识入库，只能放宽质量要求，采取“经济、务实”的做法，允许模式不完善甚至缺失；封闭世界假设（closed world assumption，库里没有的事实就当作不成立）不再成立，比如历史人物缺了父母的信息，但他一定有父母；还有知识不完全的困境，这是语义搜索、智能问答等系统的首要难题。本体是概念框架，知识图谱则是它的实例化。

应用（第 6 章）：作者说，知识图谱已经成为互联网中知识驱动的智能应用的基础设施。四类应用：语义搜索，最典型，按实体和关系检索，直接给出结构化的结果；智能问答，先把提问变成查询，再到三元组里检索、匹配、推理；智能分析与决策支持；以及金融、医疗、电商等垂直行业。作者也说，语言歧义、复杂推理等问题还没有好办法，高质量通用知识图谱的构建还有很长的路要走。

作者的小结（第 6 章）：

在人工智能中，知识和推理是不可分割的，不同的知识表示方法通常对应不同的知识推理方法。

第 6 章 6.6 节，p.172

作者认为，知识表示多种多样，缺乏统一的框架；以知识图谱为代表的大规模自动化知识表示，使知识工程进入了大数据知识工程的阶段。但隐性知识和过程性知识难以表示，很多知识库缺乏学习能力，短期内还无法完整地建立开放领域的知识库，尤其很难完全表示常识知识。

本章讲不确定性知识的表示与推理，主要介绍基于概率和基于模糊的两类方法（第 7 章）。作者在章首说，客观事物的出现有随机性，人的认识也不完全、不精确，很多概念本身就是模糊的。

在此情况下，若仍用经典逻辑进行精确处理，则必须要人为地在本来没有明确界限的事物间划定界限，从而舍弃事物固有的随机性或模糊性，与真实情况不符。

第 7 章，p.174

不确定性从哪里来，推理要多做什么

三种来源（第 7 章）：不确定性，是指对一个说法是否为真不能完全肯定，只能估计它为真的可能性。来源有三种：

• 随机性：条件不充分，条件和结果之间没有必然的因果关系，用概率描述。事情本身含义清楚，只是发不发生说不准。
• 模糊性：类别划不清，比如年轻与年老、高与低，用隶属度（属于某一类的程度，0 到 1 之间）描述。书中用一张图对比：随机性下对象要么在集合里、要么不在；模糊性下对象可以一部分在集合里。
• 不完全性：信息不全，比如破案时警方掌握的罪犯信息往往不完整。相关理论有粗糙集理论，它把知识看作给对象分类的能力，知识不全时，用肯定属于某类、可能属于某类的两个集合把这一类夹在中间；还有邓聚龙提出的灰色系统理论（书中称灰度理论），研究在少量、不完全的信息下怎样做决策。

比确定性推理多出的三个问题（第 7 章）：不确定性推理是从不确定的证据出发，用不确定的知识，推出带一定不确定性、但合理或近乎合理的结论。它要多解决三件事：

• 怎么表示和度量：知识的不确定程度一般由领域专家给一个数，证据要用同一套表示法。比如专家系统 MYCIN 用可信度，取值 –1 到 1，越接近 1 越接近真。
• 怎样才算匹配：规则前提和手头证据的不确定程度不一定相同，常用办法是算出两者的相似程度，再定一个限度（阈值），在限度内就算匹配上。
• 怎么算结论：几个条件用“且”“或”连起来时，要算这组证据的整体程度，常用最大最小方法（“且”取小、“或”取大）、概率方法（只能在事件完全独立时用）、有界方法；多步推理时，每一步的结论连同它的不确定性当成新证据，初始证据的不确定性就一步步传到最终结论；几条知识推出同一结论时，还要合成。

方法怎么分（第 7 章）：分模型方法和控制方法。模型方法给证据和知识定一套度量，再给出更新结论的算法；控制方法没有统一模型，靠控制策略减少不确定性的影响。本章只讲模型方法里的数值方法，分概率推理及其扩展、模糊推理两大类。

概率推理及其扩展

从概率出发（第 7 章）：概率论理论完备，又现成提供了合成与传递的公式，所以最早被用来处理不确定性。完全用概率模型的叫纯概率方法，贝叶斯网络是代表，理论严密，但要事先给出先验概率和条件概率，数据不好获取，于是又发展出主观贝叶斯方法、可信度方法和证据理论。

贝叶斯网络（第 7 章）：贝叶斯公式解决的是由结果反推原因：原因看不见，只看到结果发生了，问每种原因的可能性。原因本来的可能性叫先验概率，看到结果后修正过的叫后验概率。贝叶斯网络把一组变量画成有向无环图（directed acyclic graph，DAG，沿着箭头走永远回不到出发点），节点是变量，箭头表示因果依赖，每个节点附一张条件概率表（CPT），记下它在父节点各种取值下的概率。关键性质是：父节点定下来，一个节点就和其他非直接先导节点无关。n 个变量的联合分布原本要 2ⁿ–1 个概率值，找出这类条件独立关系，只需根节点的先验概率和各节点对父节点的条件概率，计算大大减少。三种典型连接：串行（A→B→C），B 已知时 A 和 C 互不影响；分叉（一因多果），原因已知时几个结果互相独立；汇集（多因一果），结果不知道时几个原因互相独立，结果一旦知道，原因之间就有了关联。

可以认为，贝叶斯网络是一个表示条件独立关系的图模型，利用其属性能够获得概率分布的定性结构，从而进行高效的推理和决策。

第 7 章 7.2.1 节，p.182

汽车异常检测（第 7 章）：网络里发动机异常会引起温度高和异响，轮胎破损也会引起异响。推理有三种模式：

• 因果推理（自顶向下）：从原因推结果。已知发动机异常，把另一个原因（轮胎破损与否）分两种情况展开，查表相加，得出汽车异响的概率 0.48。
• 诊断推理（自底向上）：从结果推原因，用贝叶斯公式转成因果推理。已知没有异响，得出轮胎没有破损的概率 0.849。
• 辩解：如果同时知道发动机没有异常，没有异响就有了解释，对轮胎的判断也随之改变。

作者认为，贝叶斯网络推理理论基础强，证据之间、假设之间都独立时计算量小；但各假设的概率之和必须为 1，加一个新假设就得全部重定，证据之间有依赖时不能直接用，先验概率和条件概率在实际中也很难得到（第 7 章）。

主观贝叶斯方法（第 7 章）：很多事件发生得少，没法统计，只能请专家凭经验估计，叫主观概率。这个方法由 Duda 等提出，在地矿勘探专家系统 PROSPECTOR 中成功应用。每条规则带两个专家给的数：LS 衡量证据出现对结论的支持程度，LN 衡量证据对结论的必要程度。计算时把概率换成几率（odds function，概率除以不发生的概率）：证据出现，结论的几率乘以 LS；证据没出现，乘以 LN。等于 1 表示没有影响。书中例子：先验概率 0.03、LS 为 10 的规则，证据出现后概率约为 0.24，是原来的 8 倍；先验概率 0.3、LN 为 0.002 的规则，证据不出现，可能性削弱为原来的 1/350。证据本身也不确定时，按把握程度插值。作者评价它理论基础较坚实，专家给值省去大量统计，是“实用且灵活”的方法；缺点是专家还得给出先验概率，比较难，对独立性的要求也限制了应用（第 7 章）。

可信度方法（第 7 章）：由 Shortliffe 等提出，最早用在 MYCIN 上。可信度因子（certainty factor，CF）是凭经验对一件事为真的相信程度，取值 –1 到 1。书中的规则例子是阴天且湿度大则下雨，强度 0.8，意思是有八成把握要下雨。

但人工智能面向的多是结构不良的复杂问题，难以给出精确的数学解析模型，先验概率及条件概率的确定又比较困难，因而用可信度来表示知识及证据的不确定性仍不失为一种可行的方法。

第 7 章 7.2.3 节，p.190

计算分三步：组合证据时，“且”取最小、“或”取最大；传递时，结论的可信度＝规则强度×证据的可信度，证据偏向假就记为 0；两条规则推出同一结论时两两合成，两个都是正值就取两者之和减两者乘积。例如阴天推下雨的规则强度 0.7，阴天的可信度 0.5，得下雨 0.35；另一条规则得 0.2，合成为 0.48。作者认为它简单直观，适合 MYCIN 这类推理链短、精度要求不高的系统；缺点是会累积误差，逻辑上等价的一条规则和几条规则可能算出不同结果，合成顺序不同结果也可能不同，推理链长时误差很大（第 7 章）。

证据理论（第 7 章）：也叫 D-S（Dempster-Shafer）理论（theory of evidence）。Dempster 从 1967 年起发表一系列论文，他的学生 Shafer 在 1976 年引入信任函数。它把给单个结果赋值扩展为给一组结果赋值，可看作一种广义概率论。三个基本量：

• 概率分配函数：把总量 1 分给各个子集。它不等于概率，各单个结果分到的数加起来不一定是 1。
• 信任函数（belief function）：一个命题所有子集分到的数之和，是对它为真的信任，算下限。
• 似然函数（plausibility function）：所有与它相交的子集分到的数之和，是对它不假的信任，算上限。两者之差是不确定的部分；书中图示对 A 为真的信任度 0.25、为假 0.15，不确定度 0.6。

两个来源的证据用 Dempster 合成规则（Dempster's combinational rule）合并：两边的数两两相乘，按交集归到对应子集，再除以所有交集非空的乘积之和 K。K 越接近 0，冲突越大；K 为 0 时完全冲突，无法合成。书中的 Zadeh 悖论：一个证人说凶手是 Peter 的可能性 0.99、Paul 0.01，另一个说 Mary 0.99、Paul 0.01，合成后却认定 Paul 是凶手，有违常识。作者认为它不必事先给先验概率，比主观贝叶斯方法灵活，又能综合不同专家和数据源，广泛用于信息融合、情报分析、智能决策等；局限是处理不了严重冲突的证据，子集元素越多信任度越大，对分配函数敏感（第 7 章）。

模糊推理

模糊集合（第 7 章）：Zadeh 在 1965 年提出模糊集合，用来处理大与小、快与慢这类边界不清的概念。讨论的全体对象叫论域，所有元素的隶属度合起来叫隶属函数，一般凭经验或统计确定，也可由专家给出，不同的人可能定得不同。书中例子：三辆车分别跑 85、120、50 公里/小时，假设最高 150，用车速除以 150 表示“速度快”的程度，约为 0.57、0.8、0.33；也可以换更精细的定法。运算都是逐个元素对隶属度操作：交集取小，并集取大，补集用 1 减。

模糊关系（第 7 章）：模糊关系（fuzzy relation）描述两类对象之间的关联程度，用 0 到 1 的矩阵表示，比如车速和发动机油温只有一定程度的关联。两个模糊集合叉积成关系矩阵时，每格取两个隶属度中较小的；矩阵之间常用最大-最小合成：对应元素先两两取小，再取最大。

模糊推理与模糊控制（第 7 章）：应用最广的是基于模糊规则的推理。模糊规则是把专家或操作者的经验用语言写成的定性规则，表示时给属性值配一个隶属度，如（汽车，速度，（快，0.9）），0.9 代替了“较”字。一条规则可以写成一个模糊关系矩阵，输入一个与规则前提相近的模糊向量，与矩阵合成就得到结论；多条规则的总关系是各矩阵的并集。模糊控制的流程是：模糊化（把状态量换成隶属度形式）→用规则推出模糊输出→清晰化（换成精确控制量）→作用于系统，再反馈回来。清晰化有三种办法：最大隶属度法取隶属度最大的元素，简单但丢了其他信息；加权平均法以隶属度为权重求平均，工业控制里用得较广；中位数法取把隶属度总和分成相等两半的元素。作者比较说，中位数法利用的信息多但计算复杂，动态性能好于加权平均法、静态性能略逊，这两种一般都优于最大隶属度法（第 7 章）。

汽车定速巡航（第 7 章）：书中的经验规则是车速低于设定值就开大油门、差得越多开得越大，高于设定值就关小。把车速偏差和油门变化各分成负大到正大五档（negative big，NB 到 positive big，PB），写五条同档对应的规则，每条叉积成矩阵、取并得总关系；运行时把实际偏差与总关系合成，再清晰化成具体控制量。

模糊控制不需要被控对象的精确数学模型，根据人对被控对象的控制经验来设计控制器，鲁棒性强，适合于解决过程控制中的非线性、强耦合时变、滞后等问题。

第 7 章 7.3.2 节，p.214

作者也指出缺点：简单的模糊处理可能降低控制精度；设计缺乏系统性；规则式的写法不便于学习和调整参数（第 7 章）。

本章小结（第 7 章）：作者归纳，不确定性主要来自随机性、模糊和不完全，要用不同方法处理。基于贝叶斯网络的概率推理发展最早、最成熟，但要大量有统计规律的数据，所以有了主观贝叶斯、可信度等放松条件、简化计算的方法。模糊集合用隶属度刻画“亦此亦彼的程度”，作者认为这相对于概率论“非此即彼的假设”是认识上的一大进步，但隶属度常带主观性。

尽管本章讨论的技术大多数是从实践中总结出来的工程性方法，对不确定性的处理往往不够严格，使用上也有很多局限性，但是它们能解决一些实际问题，其结果能够给出令人满意的解释，符合人类认识世界的直觉。

第 7 章 7.4 节，p.215

作者最后提到延伸方向：要捕捉因果关系，有 Pearl 的因果网络；要处理随时间变化的证据，有隐马尔可夫链和动态贝叶斯网络；要联系随机性和模糊性，有李德毅的云模型（第 7 章）。

第 8—10 章是全书的“学习”部分，分别讲从数据、网络结构和环境交互中学习的方法；第 8 章讲从数据中学习（前言）。作者在章首说，学习是人类智能的主要标志，也被认为是让机器获得智能的根本途径；机器学习是数据驱动模型的典型代表，和前几章基于规则、知识驱动的方法明显不同（第 8 章）。

机器学习不依赖知识库和预先给定规则，能够从数据或环境交互中自动分析获取知识，并利用知识对未知数据进行预测。

第 8 章，p.218

基本概念

从写规则到学规则（第 8 章）：全章用一个例子贯穿：预测路上一辆车要变道还是直行。按规则做，可以规定转向灯开了就是要变道；可有的车不打灯，只减速、调车头，规则就得改，再考虑驾驶习惯和路况，还得改。问题越复杂，人工定规则越难。机器学习的做法是从真实行驶数据里记录车速、转角、转向灯和后来的结果，让算法自己归纳出判断规则，数据变了还能自动调整。

常用术语（第 8 章）：每条记录叫样本，速度、转角这些叫特征，“变道”“直行”这类结果叫标签。模型是从历史数据里学出来的输入到输出的映射。参数分两种：超参数在学习前由人设定，通常不到 10 个；模型内部参数由训练确定，神经网络的连接权值可达上亿个。模型用在新样本上的能力叫泛化能力。没学好训练数据的一般规律，叫欠拟合（under-fitting）；在训练集上表现过好、到新数据上反而变差，叫过拟合（over-fitting）。作者认为过拟合是机器学习的关键障碍，无法彻底避免，只能缓解。

四种学习方式（第 8 章）：按训练样本提供的信息和反馈分四类。有监督学习（supervised learning）的样本都有标签，书中说“导师就是标签”；无监督学习（unsupervised learning）没有标签，只看样本的分布和结构；半监督学习（semi-supervised learning）用少量有标签、大量无标签的样本；强化学习（reinforcement learning）没有训练样本，只有环境给的奖惩反馈。

三要素（第 8 章）：建一个机器学习算法，就是确定三件事。

• 模型：先凭经验划定候选函数的范围，叫假设空间（hypothesis space），学习就是在里面找最合适的那个。线性模型简单，但只能表达特征间的线性关系；处理非线性问题，可以先对特征做非线性变换、用核方法，或直接用 k 近邻、决策树、神经网络这类非线性模型。参数化模型（parametric model）的函数形式固定，简单好解释、需要的数据少；非参数化模型（non-parametric model）的参数随数据增多，更灵活，但要更多数据、易过拟合、难解释。
• 学习准则：损失函数（loss function）衡量单个样本错了多少；全部训练样本的平均损失叫经验风险（empirical risk），只求它最小，样本少或有噪声时容易过拟合；再加一项代表模型复杂度的正则化项，就是结构风险（structural risk），能选出复杂度合适的模型。
• 优化算法：简单问题可以直接求导数为零的点，多数问题只能迭代求近似解。最常用梯度下降法：每次沿函数值下降最快的方向走一小步，步长叫学习率。函数有多个局部极小时可能陷进去，可用多个起点、模拟退火、遗传算法等办法跳出，作者提醒这些大多缺乏理论保证。

几条理论（第 8 章）：概率近似正确（PAC）理论说，从有限样本不能指望学到完全正确的模型，只能要求以较大概率学到误差足够小的模型。由此推出：候选模型越多越复杂，需要的样本越多，这就是深度神经网络要大数据的原因；样本不够时，太复杂的模型还不如简单模型。特征连续时，用 VC 维（Vapnik-Chervonenkis dimension）衡量模型能力。奥卡姆剃刀（Occam's razor）主张选与训练数据相符的最简单模型。没有免费午餐定理（no free lunch theorem）说，不存在对所有问题都有效的算法，所以作者主张脱离实际问题谈算法优劣没有意义，“不存在放之四海而皆准的算法”。

长处和局限（第 8 章）：作者认为机器学习擅长三类问题：没有现成规则的（人脸识别、语音识别）、规则一直在变的（信用卡欺诈检测）、数据本身在变的（购物趋势预测）。AlphaGo 靠定规则成不了高手，靠学习数以百万计的棋局战胜了人类冠军。局限有四条：效果严重依赖数据，数据有偏见就学偏，没数据则“巧妇难为无米之炊”；性能依赖模型选择；只能做事先指定的任务；只靠统计难以发现复杂关联。书中用简化的录取数据说明辛普森悖论（Simpson's paradox）：两个学院分别看都是男生录取率高，合起来却是女生高，原因是女生多报了容易录取的学院。

有监督学习

回归和分类（第 8 章）：有监督学习的典型问题有两类。回归预测连续值，如由行驶里程预测耗油量；分类预测离散类别，如由速度和转角判断直行还是变道。回归要找贴近所有样本的拟合曲线或曲面，分类要找把各类分开的决策边界。两者也相通：先用回归算出属于某类的概率，再和阈值比较，就成了分类，逻辑回归（logistic regression）就是这样。

一般流程（第 8 章）：五步，回归和分类一样。

• 数据准备：去重、编码、补缺失值、处理异常值；标准化消除量纲影响，常用的是缩放到 0—1 之间，或变成均值 0、标准差 1；样本多时常按 50%、25%、25% 分训练、验证、测试集。
• 特征提取：选出有用特征，或投影到新的特征空间；深度学习模型自带这一步。
• 选模型、训练：从简单到复杂多试几种。
• 评估：留出法用独立的验证集；k 折交叉验证（cross validation）把数据分成 k 份，轮流留一份验证，k 常取 10；样本少时用留一法或自助法。选定模型后，用测试集以外的全部数据重新训练。作者强调，得到最终模型前不能以任何方式使用测试集，否则测试结果就不再无偏。
• 封装应用：供其他程序调用，有新数据就持续优化。

一般认为，数据和特征往往决定了模型性能的上限，而模型选择与参数优化只是在不断地逼近这个上限。

第 8 章 8.2.1 节，p.235

回归方法（第 8 章）：线性回归用最小二乘法，让预测误差的平方和最小。耗油量例子拟合出一条直线，估计驶往 450km 外要耗油 32.4L；只看里程不够准，还要加入车况、路况，就成了多元线性回归。变量间不是线性关系时用多项式回归，阶数决定复杂度：例 8.3 用带噪声的正弦数据演示，阶数 0、1 欠拟合，3 合适，9 连噪声也拟合进去，过拟合。岭回归（ridge regression）和套索回归（lasso regression）在目标函数里加正则化项，既缓解特征强相关带来的不稳定，又防过拟合；套索回归能让一部分系数变成 0，相当于自动挑特征，适合特征多、有用特征少的问题。回归效果常用均方误差、平均绝对误差、决定系数等指标评估；例 8.4 中二次多项式模型在训练集和验证集上误差都比直线小，所以更好。

四种分类方法（第 8 章）：

• 线性判别分析（linear discriminant analysis，LDA）：Fisher 最早提出。把样本投影到一条直线上，让同类的投影尽量挤在一起、不同类尽量分开，新样本投影后看离哪类中心近。它也可用于有监督的降维。
• 支持向量机（support vector machine，SVM）：能分开两类样本的分界线有无数条，选两边留空最宽（间隔最大）的那条，作者说间隔越大，抗噪声能力越强，泛化越好。最终只由离分界线最近的少数样本决定，这些样本叫支持向量。允许少量样本越界的叫软间隔（soft margin），越界的惩罚轻重由一个超参数调节。线性分不开时，用核函数（kernel function）把样本隐式映射到高维空间再分，高斯核最常用。作者评价：理论扎实、适合小样本、泛化好；但不适合大规模数据，经典形式只能二分类，对核函数和超参数敏感。
• k 近邻（k-nearest neighborhood，KNN）：不训练，来一个新样本就找最近的 k 个训练样本投票。k 小易过拟合，k 大易欠拟合，常用交叉验证选；例 8.8 用留一法比较后选 k=5。简单易用，但数据多时计算量大，也不适合图像、语音这类高维数据。
• 决策树（decision tree）：从根节点起逐个特征提问，一路走到叶节点得出类别。建树时每步选让子集最“纯”的特征：ID3 用信息增益（information gain），C4.5 改用增益率（gain ratio）并能处理连续特征，CART（classification and regression tree）用基尼指数（Gini index）、只建二叉树，还能做回归。树太深容易过拟合，要剪枝：预剪枝在生长中提前停下，后剪枝先长全再剪。决策树好理解，不需要标准化，但训练数据稍变，树形可能大变，可用随机森林等组合多棵树来缓解。

作者说，分类器的好坏和数据特点有关，没有通用的方法：特征里混有文字型数据时，SVM、逻辑回归不适用，决策树更合适；特征相互独立时适合线性或基于距离的方法，相关时适合决策树或神经网络（第 8 章）。

分类怎么评估（第 8 章）：把预测和真实情况列成表，得到四个数：真正例、假正例、假反例、真反例。准确率是全部预测里对的比例，但各类样本数相差很大时会失真；敏感性（sensitivity，又叫召回率 recall）是真正例里被找出来的比例；特异性（specificity）是真反例里被判对的比例；精度（precision）是判为正例的里真正是正例的比例。例 8.10 预测 40 个样本，敏感性 80%、特异性 90%、精度 88.9%、准确率 85%。分类器输出概率时，阈值调低能找出更多正例，也会误判更多反例；把各个阈值下的结果画成 ROC（receiver operating characteristic）曲线，曲线下面积 AUC（area under ROC curve）越大越好。

无监督学习

聚类（第 8 章）：无监督学习以聚类为主，就是在不知道类别时，把特征相似的样本归成一组，每组叫一个簇（cluster），组内尽量像、组间尽量不像；每个簇代表什么，由使用者命名。例如按颜色和纹理把道路图像分成天空、道路、行人，按购物行为分客户群。聚类的根本问题是怎么衡量相似：常用欧氏距离、曼哈顿距离等闵可夫斯基距离（Minkowski distance），考虑特征相关性的马哈拉诺比斯距离（Mahalanobis distance），看方向的夹角余弦，看变化趋势的相关系数。

六类算法（第 8 章）：

• 划分法：代表是 k 均值，先定 k 个中心，每个样本归给最近的中心，再用各组均值更新中心，反复到不变。简单快速，但要事先定 k，受初始中心和异常点影响，只适合球形的簇。k 可用手肘法定：增加 k 时组内距离平方和先猛降后趋缓，拐点就是合适的 k。
• 层次法：常用自底向上合并（agglomerative），每个样本先自成一簇，反复合并最近的两簇，得到一棵聚类树；不用事先定簇数，但计算量大，合并后不能撤销。
• 密度法：代表是 DBSCAN，从样本密集处向外扩展成簇，能找出任意形状的簇和异常点，但不适合疏密差别大的数据。
• 网格法：把空间划成小格子再按密度聚类，速度快，代表是 CLIQUE。
• 模型法：如高斯混合模型（Gaussian mixture model，GMM），假定数据由几个高斯分布叠加而成。
• 模糊法：如模糊 C-均值，一个样本可以按不同隶属度同时属于几个簇。

作者说，聚类是机器学习里新算法最多、发展最快的领域，因为它没有客观评估标准，也就没有通用算法（第 8 章）。评估只能用有效性指标：内部指标看簇内紧不紧、簇间远不远，如轮廓系数（silhouette coefficient）；外部指标拿聚类结果和已知的参考类别比对，如纯度（purity）。

半监督学习

思路（第 8 章）：现实中有标签的样本少、无标签的多，比如网页，愿意花时间标注的用户很少。半监督学习把两者一起用。

半监督学习的基本前提是：假设无标签样本所揭示的数据分布信息与类别标注是有联系的，即相似的样本拥有相似的输出。

第 8 章 8.4.1 节，p.296

五种方法（第 8 章）：

• 生成式方法：假定所有数据来自同一个概率模型，如半监督高斯混合模型，用最大期望（expectation-maximization，EM）算法反复估计参数。简单，但假设不对时，无标签样本反而添乱。
• 半监督支持向量机（S3VM）：找既能分开有标签样本、又穿过数据稀疏区域的分界面。直推式支持向量机（TSVM）先给无标签样本打临时标签，再逐步调整。
• 半监督聚类：利用两个样本必须同簇或不能同簇这类约束，或少量带标签样本来辅助聚类。
• 基于分歧的方法：经典是协同训练，两个分类器各从一个角度看数据，各自把最有把握的无标签样本标好交给对方学习。
• 基于图的方法：样本是节点，越相似连得越紧；有标签的节点像已经染了色，学习就是颜色在图上扩散的过程。

作者指出半监督学习还有四个问题：理论分析不深；选算法缺乏依据，选错了可能比单纯有监督或无监督还差；优化难，不易得全局最优；半监督回归研究还少（第 8 章）。

强化学习

基本思想（第 8 章）：强化学习的概念来自行为心理学，智能体（Agent）在与环境的交互中试错，目标是让累积奖励最大。以围棋为例：专家也很难给出每一步的“正确”落子，但终局输赢很容易得到，可以从结果倒推每一步的好坏。它的特点是没有标签、奖励常常延迟、每个动作都影响下一状态，还要在探索新招和利用已知好招之间权衡。基本要素有 Agent、动作、环境、状态、奖励和策略（书中举的投递无人机，状态是位置、速度、姿态，动作是升降、转弯，投递成功得分）。多数问题可以写成马尔可夫决策过程（Markov decision process，MDP）：下一状态和奖励只取决于当前状态和动作。

奖励和价值（第 8 章）：累积奖励是把未来各步奖励打折后相加，折扣越小，Agent 越“目光短浅”；越接近 1，越“富有远见”。价值是对未来累积奖励的估计，作者说确定价值的评估方法是设计强化学习算法的核心。探索与利用常用 ε-贪婪（ε-greedy）策略：大多数时候选当前最好的动作，偶尔随机试一下，试的概率随训练逐渐减小。

之所以选择能带来最大价值而不是最大奖励的动作，是因为这些动作从长远来看将带来最大的累积奖励。

第 8 章 8.5.1 节，p.306

算法的分法（第 8 章）：基于模型的算法先学会环境怎么变，可以在脑中模拟，效率高，但模拟和真实有差距；无模型的算法直接从交互中学，适用面广但要大量采样，多数算法属于这类。基于价值的算法学每个动作值多少，选最值钱的；基于策略的算法直接输出各动作的概率，适合连续动作；演员-评论员（actor-critic）把两者结合。用来探索的策略和最终要学的策略是同一个的叫同策略（on-policy），不是同一个的叫异策略（off-policy）。

Q 学习、Sarsa 和 DQN（第 8 章）：Q 学习把每个状态下每个动作的价值记在一张表里，每走一步，用得到的奖励加上下一状态的最高价值来修正表中的值，交互足够多后照表选动作就是最优策略。例 8.16 在 2×3 的网格里找目标，多轮后 Q 表收敛，从起点出发的最优路线有三条，不唯一。Sarsa 用下一步实际要执行的动作来修正，属于同策略。在“悬崖行走”问题里，Q 学习贴着悬崖走最短路，偶尔试探就会掉下去；Sarsa 学会远离悬崖，路长但安全。Sarsa(λ) 拿到奖励后不只修正上一步，还按远近修正之前走过的各步。状态太多或连续时表格装不下，就用深度神经网络来估计价值，这是深度强化学习。DeepMind 的深度 Q 网络（DQN）用两个办法让训练稳定：另设一个更新较慢的目标网络；把经历先存起来再随机抽取来学，即经验回放（experience replay）。DQN 在雅达利 2600 游戏中达到与人类玩家相当的水平。

应用和难处（第 8 章）：作者认为，凡是能写成序列决策、给出状态动作和奖励的问题，通常都能用强化学习，它因此被认为是迈向通用人工智能的关键途径。书中举了机器人控制、游戏、推荐、调度等例子，如 2020 年 DeepMind 的系统在全部 57 款雅达利 2600 游戏中都超过人类玩家。难处有四：奖励难设计，奖励稀疏时难收敛，可用奖励塑造（reward shaping）等办法；需要的数据太多，有的领域不允许在真实环境试错；训练不稳定；泛化差，围棋 Agent 若总和低水平棋手下，遇到高手就一筹莫展。作者的结论是，简单套用经典算法往往不现实，相对于较成熟的有监督学习，强化学习的研究还处于相对初级的阶段（第 8 章）。

本章小结

作者的归纳（第 8 章）：机器学习是从已知预测未知的过程，适合数据多、有模式、但规则复杂或无法直接定义的问题。它也有易受干扰、数据偏见、过拟合等问题，缺乏常识，复杂模型学到的东西人不易看懂。选算法要看数据规模、数据分布、能否拿到标签、能否得到环境反馈。最成熟的是有监督学习，近年人们更关注无监督学习和强化学习，也在研究只用少量样本甚至不用训练样本的学习方法。

在机器学习系统的构建和应用过程中，从数据预处理到模型选择和评估再到结果解释，仍然需要人类专家的指导。

第 8 章 8.6 节，p.321

本章讲从网络结构中学习（前言）。作者说，人工神经网络是机器学习的一个分支，因为重要，单独成章；它克服了符号主义方法处理感知和非结构化数据的缺陷，深度神经网络还能自动提取文本、图像的特征（第 9 章）。

从神经元到网络

生物神经元（第 9 章）：神经元由细胞体、树突、轴突和突触组成。树突接收信号，细胞体把它们累加，超过阈值就兴奋，经轴突传给下一个神经元；突触的连接强度会随刺激改变。人脑约有 1.4×10¹¹ 个神经元，每个与 10³～10⁵ 个神经元相连。书里举幼儿认识火的例子：看到火、感到热、被烫后缩手，相关的几类神经元之间一步步建立起联系。

这里与火相关的信息分布式地存储在神经元之间的连接上，而不是保存在神经元的内部。

第 9 章 9.1.1 节，p.327

人工神经元（第 9 章）：作者说，一个人工神经网络由神经元特性、网络拓扑结构、学习规则三个要素决定，学习规则是研究的核心问题。最早、影响最大的是 MP 模型：各输入乘上权值后相加，减去阈值，再送进激活函数；加权和够大输出 1（兴奋），否则输出 0（抑制）。它的权值固定，不会学习。神经元的区别主要在激活函数：阈值型最像生物神经元，但不连续、不能求导；sigmoid 函数（sigmoid，一条 S 形曲线）输出连续地落在 0 和 1 之间，浅层网络多用；线性整流函数（rectified linear unit, ReLU）输入小于 0 时输出 0，大于 0 时原样输出，深度网络用得最多；softmax 函数（softmax）把一组数变成加起来为 1 的概率，常放在分类网络的最后。

网络结构与学习规则（第 9 章）：前馈网络一层接一层往前传，没有回路，整个网络相当于一个函数，适合函数逼近和预测；反馈网络把输出送回输入，像人的短期记忆，适合时间序列分析和联想记忆，但要考虑稳定性。Hebb 学习规则（Hebb）来自条件反射：两个相连的神经元同时兴奋，连接就加强，否则减弱；作者认为几乎所有学习规则都可看作它的变形。Delta 学习规则（Delta）用于有监督学习：以实际输出和期望输出的误差为目标，沿误差下降最快的方向一点点调权值（梯度下降），所以要求激活函数能求导。

几种经典的浅层网络

浅层网络指没有隐层（输入层和输出层之间的中间层），或只有一两个隐层的网络（第 9 章）。

感知器（第 9 章）：最早的人工神经网络，比 MP 模型多了一样：权值能学。单层感知器遇到分错的样本就修正权值；只要两类样本能用一条直线（高维时是超平面）分开，有限步内一定学成。书中用它学会了“与”门。但“异或”（两个输入相同输出 0，不同输出 1）找不到一条直线分开，单层感知器做不到；加一个隐层，把点映射到新的空间，就变得可分了。作者评价感知器泛化能力不强，实践中已很少用，但为支持向量机和多层网络打下了基础。

BP 网络（第 9 章）：多层网络的难处是不知道隐层该输出什么，没法直接按误差调。BP 算法（误差反向传播）让两个方向的计算交替进行：正向把输入一层层算到输出；反向用输出层的误差估计前一层的误差，一层层往前推，据此调整各层权值。每个节点对误差的敏感程度（书里叫灵敏度）由后一层的灵敏度和连接权值算出，从后往前递推，省去大量重复计算。书中的无人平台案例，用单隐层 BP 网络根据雷达测到的速度和截面积给无人机分类。

通用近似定理（universal approximation theorem）说明，只要隐层神经元足够多，单隐层前馈网络就能以任意精度逼近有界闭区域上的连续函数。作者说 BP 网络非线性映射能力强、容错、能自学习；但可能陷入局部最优，超参数多，效果依赖样本，初始权值随机，结果不可重现。还有梯度消失问题（vanishing gradient problem）：sigmoid 的导数最大只有 0.25，层数一多，连乘后梯度越来越小，靠前的层几乎学不动。书中说这也是 BP 网络最多只设两个隐层的原因。

Hopfield 网络（第 9 章）：一种反馈网络，权值按规则事先算好，输出不断送回输入，稳定的网络最后停在某个状态。书中用能量函数（李雅普诺夫函数，Lyapunov）解释：权值对称、没有自反馈时，每次状态变化能量只降不升，最后停在一个极小值。把要记住的模式设计成这些极小值，网络就成了联想存储器；把优化问题的目标函数写成能量函数，网络收敛的过程就是寻优，得到局部最优解。

自组织特征映射网络（第 9 章）：Kohonen 提出，模仿大脑皮层的侧抑制（一个神经元兴奋后抑制周围的神经元），不要标签。输出层神经元排成平面，样本进来，最像样本的神经元获胜，它和邻居一起向样本靠拢，邻居范围逐渐缩小。训练完，相似的输入落在相邻的位置。书里用 13 种动物的大小、腿数、毛和羽毛、会不会飞等特征训练，结果鸟类聚在一起，虎、狼、狗聚在一起，马和牛靠在一起。

深度学习的思路与得失

特征提取是瓶颈（第 9 章）：作者认为，传统机器学习靠领域知识人工提取特征，面对图像、语言这类数据非常困难。办法是把网络分成更多层，以原始数据为输入，逐层自动提取特征。但 BP 算法直接用于深层网络有四个问题：梯度消失，易陷入局部最优，参数多易过拟合，用不上无标签数据。2006 年 Hinton 等在《科学》上发表论文，提出深度学习的基本思想：把低层特征组合成更抽象的高层特征。训练难题有两条解法：用无监督的逐层预训练给参数一个好的初值；或用卷积、循环这类特殊结构减少参数。

为什么要深（第 9 章）：一个隐层理论上就够，作者引伊恩·古德费洛等的说法：单隐层的学习始终在同一个特征空间里进行，缺少特征变换。深而窄的网络能逐层变换特征；单隐层要达到同样效果，神经元往往要指数级增长。比如 ln(cos(exp(sin³x)))，深度网络可以拆成五步，一层做一步。深度学习因此是端到端学习（end-to-end learning），不分模块和阶段，直接优化最终目标。

通过网络权值调整，学习从原始数据到期望输出的映射，实现特征和分类器联合优化，中间过程不需要人为干预，使得机器学习向全自动数据分析前进了一大步。

第 9 章 9.3.1 节，p.369

模型、训练与优势（第 9 章）：作者的选型建议是：图像分类用卷积神经网络；语音、文本等序列用循环神经网络、长短期记忆网络或 Transformer；自编码器用于降维和特征提取。早年的逐层训练（layer-wise training）先用无标签数据一层层预训练，再用有标签数据微调，作者说它起了历史性的作用；现在常用预训练-微调：先在大数据集上训练基础模型，再拿到具体任务上微调，本质是一种迁移学习。作者说深度网络提取特征的方式和人的视觉相似：Hubel 等在猫的实验中发现初级视觉皮层神经元对移动的边缘敏感，视觉信号逐级向上，层次越高特征越抽象。深度学习还离不开大数据：数据少时它和传统方法差不多甚至更差，数据越多优势越大。

局限（第 9 章）：作者列了五条：网络结构难设计，调参靠经验，结果常无法复现；依赖大数据和高性能计算，能耗高；可解释性差，内部特征是连续数值，不对应人能看懂的符号，所以在运输、医疗、法律、金融等高风险领域受限；训练是非凸优化，理论分析难；容易被欺骗，在熊猫图片上叠加精心设计的细微噪声，人看还是熊猫，模型却很有把握地认成长臂猿，这叫对抗样本（adversarial example）。训练数据里的偏见也很难发现。

虽然深度学习取得了很大的进展，但是相比人脑的学习和推理能力还相差甚远。深度学习善于类比推理，但在需要逻辑推理时往往无能为力。

第 9 章 9.3.1 节，p.375

作者还提醒，深度学习擅长图像、语音这类数值建模任务，在一些数据分析竞赛中不如随机森林等传统算法，“根据没有免费午餐定理，没有任何一个算法在所有任务上都优于其他算法。”（第 9 章）

卷积、循环与生成对抗网络

卷积神经网络（第 9 章）：卷积神经网络（convolutional neural network, CNN）是第一种被成功训练的深度网络。核心是卷积层：拿一个小的权值矩阵在图像上从左上滑到右下，每到一处和那一小块像素对应相乘再求和，得到一张新图。这个小矩阵叫卷积核（convolution kernel），新图叫特征图（feature map）。每个输出只看一小块，这一小块叫局部感受野（local receptive field）；各处用同一个卷积核，叫权值共享（weight sharing）。所以 1000×1000 的图像用 10×10 的卷积核，整层只要 101 个参数。一层通常有多个卷积核，各提取边缘、颜色、纹理等一种特征，层数越多特征越抽象。

卷积只做线性运算，非线性靠激活函数。早期的 LeNet-5 用 sigmoid，有梯度消失问题；ReLU 在输入大于 0 时梯度恒为 1，在很大程度上解决了它，缺点是神经元可能“坏死”，输入总为负就再不会被激活。池化层（pooling layer）把特征图缩小：最大池化取一小块里的最大值，作者说它“突出重点，提取更显著的特征”。作者打比方：看完美景闭上眼，记不清细节，却记得看到了什么。最后全连接层把局部特征整合成全局特征（人脸识别还要看眼、鼻、口的相对位置），输出层用 softmax 给出各类概率。

2012 年的 AlexNet 让卷积网络成为图像分类的核心算法；此后 VGG 用小卷积核加深网络，GoogLeNet 并排放几种卷积来加宽网络，深度残差网络（deep residual network, ResNet）加跨层连接，把输入直接加到卷积输出上，解决了层数加深后学习效率低的问题。作者坦言，需要几层、每层几个卷积核，“暂时还没有理论支撑”，多凭经验试。防过拟合的办法有数据增强（data augmentation，旋转、翻转、裁剪图片来扩充样本）、正则化（惩罚过大的权值）、随机失活（Dropout，训练时随机让一部分神经元不工作，相当于集成许多子网络）、分批归一化（batch normalization，把每层输入重新标准化）和早停（early stopping，验证集错误率不再下降就停）。

它成功的关键在于采用局部连接和权值共享的方式，减少了参数量，使得网络易于优化，同时降低了过拟合的风险。

第 9 章 9.3.2 节，p.395

循环神经网络（第 9 章）：循环神经网络（recurrent neural network, RNN）有短期记忆，隐层既接收当前输入，也接收自己上一时刻的输出，适合语音、文字这类序列。比如标词性，知道“发动”是动词，后面的“汽车”多半是名词。双向循环网络同时看前后文：“我要去____汽车，我的车坏了”，看到后半句才知道该填维修。训练用时序反向传播（back propagation through time, BPTT），误差沿时间往回传，每传一步乘一个系数，传得越远，梯度按指数变大（梯度爆炸）或变小（梯度消失），远处的影响就难以捕捉。梯度爆炸可以设阈值截断；梯度消失最常用的解法是长短期记忆网络（long short-term memory, LSTM），用输入门、遗忘门、输出门控制忘掉什么、加入什么。循环网络的缺点是不适合并行计算。

生成对抗网络（第 9 章）：生成对抗网络（generative adversarial network, GAN）的灵感来自零和博弈。生成器（generator）从随机噪声造假样本，判别器（discriminator）分辨真假，双方轮流改进，直到判别器对真假样本的判断都是 0.5，即生成的分布和真实分布一样。作者认为它能拟合非常复杂的分布，但训练困难：两方难同时收敛，难判断何时停止，会出现模式崩溃（如手写数字生成器只会写某几个数字），还有生成器梯度消失。作者打比方说，认出齐白石的画比临摹容易，判别器很快学成，生成器就得不到有用的梯度。GAN 主要用于图像生成和编辑，用在文本上难得多。

深度学习大模型

什么是大模型（第 9 章）：作者把大模型定义为具有大规模参数和复杂计算结构的神经网络模型，通常有亿级以上参数，目的是从海量数据中学习内在模式和世界知识；并说它“很可能像个人计算机时代的操作系统一样”，成为人工智能的关键基础设施。它从“标注数据监督学习”的专用模型，到“无标注数据预训练+标注数据微调”，再到大规模预训练加指令微调和人类对齐，经历了从小模型到大模型、从专用到通用。规模定律（scaling laws）是说，性能随参数量、数据量、计算量的指数增长而平稳提升，作者说这种提升通常明显高于改进架构和算法的收益。有些能力要等规模过了某个阈值才突然出现，这叫涌现能力。

注意力与 Transformer（第 9 章）：卷积网络受感受野限制，难处理长距离依赖；循环网络每一步要等上一步，难以并行。2017 年 Vaswani 等提出的 Transformer 用注意力机制对全局建模，解决了这两点。注意力把权重集中到与任务相关的部分：每个输入算出查询（要找什么）、键（可供匹配的上下文）、值（内容本身）三个向量，用查询和各个键的相似度作权重，对值加权求和；在句子内部这样做叫自注意力。模型本身不知道词的先后，要另加位置编码。编码器把输入序列变成向量表示，解码器再把它变成输出序列，比编码器多一个编码器-解码器注意力（encoder-decoder attention）读取输入，并用掩码挡住还没生成的词元（token，分词后的基本单位）。

几种典型架构（第 9 章）：BERT 只用编码器，双向看整句，预训练时遮住一些词元让模型猜（掩码语言建模，masked language model, MLM），擅长理解类任务。GPT 只用解码器，从左到右预测下一个词元，擅长生成；书中说其原理是“将广泛的世界知识压缩到仅包含解码器的 Transformer 模型中”，后来这条路线成了主流。ViT（vision Transformer）把图像切成小块，每块当作一个词元送进 Transformer。CLIP 用文本-图像对做对比学习（contrastive learning），让配对的文字和图像在表示空间里靠近，用时拿“A photo of a dog.”这类提示和图片比相似度就能分类。扩散模型（diffusion model）先把图像一步步加噪声，再学会一步步去噪还原。

怎样造一个大模型（第 9 章）：数据要先过滤低质量内容、去重、删除隐私信息，作者说高质量数据能大大降低所需的数据量。书中介绍的语言大模型构建分四个阶段：预训练，用海量网页、书籍、代码得到基础模型；指令微调（instruction tuning），用少量高质量的指令和期望回答教它听指令；奖励建模，训练一个判断回答好坏的奖励模型；强化学习，按奖励模型的打分继续调整。后几步就是基于人类反馈的强化学习（reinforcement learning from human feedback, RLHF），目的是和人的偏好对齐。使用时还可借助思维链（chain-of-thoughts, CoT）等提示技术，或接上计算器、搜索引擎。多模态大模型多以语言大模型为中心，因为文本表达效率高，语言大模型又含丰富的世界知识。

风险与挑战（第 9 章）：作者指出，大模型仍有较严重的幻觉问题，会生成事实错误、似是而非的文本；训练数据可能带入有害内容，模型会被提示注入欺骗，敏感数据可能被编码进参数。他还列了四点局限：涌现缺乏理论解释；预训练太贵，难做可重复实验；Transformer 训练成本高、推理慢；能力越强，越难与人类价值观对齐。

尽管语言大模型的基本思想比较容易理解，但要形式化解释为什么通过简单的语言建模目标(预测下一个词元)训练得到的大模型能够解决各种复杂任务，仍然具有很大的挑战。

第 9 章 9.4.4 节，p.434

作者的总评是，大模型“引发了机器学习范式的一系列重要革新，为通用人工智能发展提供了一种新的途径”（第 9 章）。

本章小结（第 9 章）：作者归纳，人工神经网络把知识存在单元之间的连接上，学习就是调整连接权值，适合有大量数据、却无法用规则或公式写清的问题；主要缺点是“黑箱”性质，说不出预测的依据，结构复杂时容易过拟合。深度学习还有训练成本高、调参技巧如同“炼丹术”、难以融入先验知识等问题，改进方向有正则化、随机失活等训练技巧，Hinton 不依赖误差反向传播的前向-前向算法，以及可解释性研究。

本章讲从与环境的交互中学习（前言）。章首说，Agent 是行为主义学派最重要的概念之一，也是它区别于其他学派的一个重要依据（第 10 章）。

Agent 是什么（第 10 章）：Agent 一词源于拉丁语 agere，意思是“去做”。国内把它译作主体、智能体、智能代理等，没有统一译法。作者说，这个概念本身不限定是否智能，译成“智能体”容易让人误以为它一定有智能，所以本书沿用英文。书里采用人工智能领域普遍接受的定义（引斯图尔特·罗素等）：Agent 是能够通过传感器（sensor）感知环境、并通过执行器（actuator）对环境产生影响的任何事物。下棋程序是软件 Agent，扫地机器人是硬件 Agent；也可以把人看作 Agent，眼睛、鼻子是传感器，手、脚是执行器。计算机领域的开创性定义（Wooldridge 等，1995）则说，Agent 是部署在一定环境里、为实现设计目标能自主行动的计算机系统，强调它的行动（一定程度上）独立、有目的。

这个概念最初由 Minsky（1986）提出，指在社会中通过协商求解问题的个体。学者们对定义有争议，只普遍认为自主性是核心（第 10 章）。

Agent 概念具有很强的包容性，它将所有能够对环境进行感知和施加影响的个体包容到一个统一的概念框架下进行研究。

第 10 章，p.439

Agent 函数和 Agent 程序（第 10 章）：从感知到行动的中间那段，可以用两种方式说。Agent 函数是抽象的数学描述，输入全部感知历史（感知序列），输出动作；Agent 程序是它的具体实现，只输入当前的感知信息，要用历史就得自己存。程序要在物理平台上跑，所以 Agent 的体系结构可以看作“物理平台+Agent 程序”。书里用吸尘器世界来说明：只有 A、B 两个房间，吸尘器能感知自己在哪个房间、房间干净（Clean）还是有灰尘（Dirty），能做的动作是向左（Left）、向右（Right）、吸尘（Suck）、什么也不做（Noop）。最简单的 Agent 函数是：有灰尘就吸，否则去另一个房间。

理性 Agent（第 10 章）：怎么判断 Agent 是否智能，书里用理性 Agent 来回答。作者说，人工智能里的“理性”是技术术语，可以看作对智能的一种具体描述，和日常说的“不要感情用事”不是一回事。

理性 Agent 是对于每个可能的感知序列，在给定感知信息和先验知识的基础上，选择能使其性能度量的期望最大化的行动的 Agent。

第 10 章 10.1.3 节，p.441

性能度量由设计者或用户的需求来定，比如吸尘器单位时间清掉多少灰尘。理性 Agent 只管把它做到最大，不管它合不合理：也可以设计一个尽量把地面弄脏的理性 Agent。理性不等于全知，不要求“上帝视角”；也不等于完美，它追求的是期望最大，单次结果说不准。书里的例子：吸尘器看到 A 房间干净，去 B 房间看看，刚到就被掉下来的吊灯砸扁了，但不能说它的行动不理性。

理性 Agent 基于本身的经验和知识努力去做到最好，但是并不保证能够成功。

第 10 章 10.1.3 节，p.442

所以 Agent 常要先收集信息、在未知环境里探索和学习，再决策。作者说，过度依赖设计者给的先验知识就是缺乏自主性；理性 Agent 应该能靠学习弥补不完整的信息或不正确的先验知识（第 10 章）。

为什么要研究 Agent（第 10 章）：作者给了四条理由。一是 Agent 原意是代理，符合让机器替代或辅助人类部分智力活动的初衷，如工业机器人、股票交易代理、电话语音助手。二是它只看智能的外在表现，实现手段可以是符号主义的推理，也可以是连接主义的神经网络，摆脱了仿生学的局限：

Agent 强调智能的外在表现，只要 Agent 的行动决策能够实现某种性能度量期望最大化，就可以认为该 Agent 的行动是理性的，也就是具有智能。

第 10 章 10.1.4 节，p.442

三是它给人工智能各领域提供了统一框架：单个 Agent 有感知智能（如机器视觉、语音识别）、认知智能（如知识表示、机器学习、智能规划）、行动智能（如智能控制）；多个 Agent 之间的合作、竞争、对抗对应群体智能和对抗博弈；Agent 和人的共生合作对应人机协同。四是它关注整体、强调交互、蕴含学习与进化。作者说，人类不可能替 Agent 设计好所有行动模式，只有赋予它学习与进化能力，才能打破人为预设的能力界限，适应开放环境（第 10 章）。

先把任务环境说清楚

PEAS（第 10 章）：作者说，设计理性 Agent 的第一步是描述任务环境，相当于把“问题”说清楚。描述用四个要素，合称 PEAS（performance, environment, actuator, sensor）：性能、环境、执行器、传感器。以出租车自动驾驶为例：性能是安全、快、准确到达、盈利、合法、舒适；环境是街道、交通、行人、乘客、天气；执行器是方向盘、油门、刹车、喇叭、车灯和对乘客的屏幕；传感器是摄像头、雷达、GPS 接收器、各种仪表和接收乘客指令的触摸屏、麦克风。作者说，PEAS 没有标准答案，它不给设计方案，但给出需求说明；城市里的出租车和高速公路上的货车，设计就差得很远（第 10 章）。

任务环境的七个维度（第 10 章）：

• 完全可观测与部分可观测：每一刻能否看到环境全貌。下棋能；只看得到本房间的吸尘器不能。
• 确定的与随机的：下一状态是否完全由当前状态和动作决定。吸尘器环境里垃圾随机出现，是随机的。
• 片段式与延续式：前后决策是否互不相关。图像分类是片段式，路径规划是延续式。
• 静态的与动态的：Agent 思考时环境会不会变。下围棋是静态的；网购时商品可能被别人买走，是动态的。
• 离散的与连续的：围棋是离散的，出租车的速度、方向盘角度是连续的。
• 单 Agent 与多 Agent：要不要考虑别的 Agent。主动避让的其他车辆算 Agent，建筑和树木算环境。
• 已知的与未知的：是否掌握环境的变化规律。魔方是已知的，到了没有地图的新城市的出租车面对的是未知环境。

作者说明，这种划分只是为了便于研究（第 10 章）。

五种 Agent 程序

由简到繁（第 10 章）：

• 简单反射 Agent：只看当前感知，按“条件-动作”规则表行事。吸尘器版本是：有灰尘就吸，否则在 A 就向右、在 B 就向左。程序简洁、速度快，但通常要求环境完全可观测，在部分可观测的环境里常陷入无限循环，智能有限。出租车用前面有障碍物就转方向盘这条规则，可能来回反复地转。
• 基于模型的反射 Agent：根据感知历史维持内部状态，记住现在看不到的那部分环境。为此要装进两类知识：环境自己会怎样变，自己的动作会怎样影响环境。吸尘器能估计各房间现在脏没脏，不再来回乱跑；出租车看到“前方正在施工”，经过施工→车道减少→堵车→追尾→危险一串推理，得出“松油门”。
• 基于目标的 Agent：再加上目标，比如出租车要去的地方，选能达成目标的动作，状态空间搜索就属于这一类。它要规划或搜索，效率较低，但更灵活：换个目标就能生成新的动作序列，反射 Agent 换目标往往要改掉大部分规则。
• 基于效用的 Agent：能到达的路线有好几条，有的更快、更安全或更便宜。能否到达只分满意和不满意，效用函数能给出具体分数。它选期望效用最大的动作，即把一个动作各种可能结果的效用按概率加权平均；多个目标冲突时，还能在其间折中。
• 学习 Agent：性能部件负责决定动作（可以是前面任何一种）；评估部件按性能度量给反馈；学习部件据此修改性能部件；问题产生器提出探索性动作，比如对新车做刹车实验，学某速度下踩多大力、刹车距离多长。强化学习 Agent 就是一种学习 Agent，靠试错和奖励让累积奖励最大。

作者在小结里打了个比方：五种 Agent 依次是“头脑简单”“瞻前顾后”“目标明确”“权衡利弊”和“三省吾身”的 Agent（第 10 章）。

多 Agent 系统

为什么要多个 Agent（第 10 章）：单个 Agent 能力有限，难以求解分布式、异构的复杂问题；就像人离不开社会，常要部署多个 Agent 共同行动，这就是多 Agent 系统（multi-agent system, MAS）。例如交通系统把每个摄像头当作一个 Agent，协调监控来扩大覆盖。

MAS 通常并不能简单看作其所有 Agent 的总和，因为这些 Agent 的行动常常会互相影响。

第 10 章 10.4.1 节，p.451

书中的例子：每辆自动驾驶出租车都只顾自己最快到达，很快就会出事故或堵车，所以要把 Agent 组织起来。书里只讲合作的情形，要素是组织、通信和协作（第 10 章）。

组织结构（第 10 章）：完全集中式由一个总控 Agent 统领，命令快、开销小，但总控一坏全盘失败，适合小规模、静态、已知的环境；完全分布式里各 Agent 平等、点对点通信，容错和扩展性好，但协调复杂；分层结构排成树，信息上传、控制下达；合弄（holon）既是独立个体又是协作整体，好比细胞和器官，一个 Agent 可以属于多个合弄；联盟是一组 Agent 为提高效用临时结合、目标达成就解散，书中案例是把每个路口当作 Agent 控制绿灯时长、随车流重组联盟（Srinivasan 等，2010）；涌现式则没有集中控制，集体行动从局部交互中自然产生。实际系统可以综合使用。

通信（第 10 章）：作者说多余的通信会增加成本、让系统不稳定。两种主要方式：局部通信，Agent 按约定格式直接互发消息；黑板通信，大家在一块公共的“黑板”上看问题和别人的结果，再写上自己的结果，彼此不直接通信。黑板结构也是一种重要的专家系统结构。

协作就是解约束满足问题（第 10 章）：作者说，Agent 的协作在数学上可以归结为约束满足问题（constraint satisfaction problem, CSP）：一组变量、各自的可选值、变量间的约束，要找一组满足全部约束的取值。书中的例子：三台监测设备覆盖区两两重叠，只有三种频率可用，重叠的不能同频，这等于给三个点涂三种颜色、相连的点不同色。在 MAS 里，变量和约束一开始就分散在各 Agent 手里，没有谁掌握全局，这叫分布式约束满足问题。

最早的分布式算法是异步回溯（asynchronous backtracking）。各 Agent 有事先定好的优先级，用 agent_view 记下别人当前的取值；用 ok? 消息把自己的取值告诉优先级更低的邻居，和高优先级的值冲突就换值；换不出来，就用 nogood 消息要求高优先级的 Agent 换。书里用四皇后问题演示，四个 Agent 各管一行，几轮换值和逐级回报冲突后，各行皇后依次落在第 2、4、1、3 列（第 10 章）。

特点与局限（第 10 章）：MAS 已用于飞行器编队、传感器网络、多机器人合作控制、交通控制等。它的特征是：每个 Agent 都没有完整信息和解决全部问题的能力，没有全局控制，信息分散，计算异步。优势是自主、并行、易扩展。作者也说这项技术尚未成熟：组成越复杂越难集成，大型系统通信复杂、协作困难；分布式算法还要解决减少通信、动态增减 Agent、兼顾隐私和效率等问题。小结里作者归纳：设计 Agent 的第一步总是尽可能完整地描述任务环境；求解分布式约束满足问题，就是为多个 Agent 找到满足彼此约束的一致行动组合（第 10 章）。

这是全书最后一章，分析人工智能面临的风险与挑战（前言）。章首说，人工智能提高了生产力和生活水平，也带来改变就业结构、冲击法律与伦理、侵犯个人隐私、挑战国际关系准则等新问题，要兼顾创新发展与安全可控，需要技术和制度两方面的保障（第 11 章）。

趋势

四个特点（第 11 章）：一是创新步伐加快，机器学习、计算机视觉、自然语言处理、内容生成都有明显进步；二是基础设施扩容，芯片、5G、数据中心加快建设，开源平台让训练成本大降，创新不再是少数人的专属；三是和产业结合更紧，人工智能被看作推动第四次工业革命的通用技术，既让传统产业升级为“智能+”产业，又催生智能机器人、智能运载工具等新兴产业；四是改变人机关系，作者说人工智能“就像空气一样须臾不可离”。

这一波会不会退潮（第 11 章）：人工智能经历了两次低谷、三次浪潮，推理期和知识期的高峰都有人预言“人类要被机器毁灭了！”。作者说前两次的共同点是：以研究人员的探索为主，企业参与少，落地有限；技术上符号主义占主导，难以处理现实中大量的不确定性，神经网络所需的数据和算力也不成熟。这一次，海量数据提供了“燃料”，机器学习在视觉、语音、语言等领域接连突破，企业成了主要推动者；深度学习用端到端的方式自动提取特征，符号主义则以知识图谱的形式延续，成为新一代搜索引擎的核心技术。

作者用技术成熟度曲线来看：新技术成熟前大多要经过萌芽、期望膨胀、幻灭低谷、爬坡，最后才成熟。以前遇冷，是因为技术创造不了较大的经济价值；这一次的价值在于和各行业结合、提质增效。

只要智能化的需求旺盛，学术界不像前两次那样盲目乐观，人工智能将保持其繁荣、稳定发展的趋势，而不会马上进入寒冬。

第 11 章 11.1.2 节，p.467

作者也指出局限：深度学习缺乏理论支撑，结构设计和训练主要靠经验；无监督学习、小样本学习、可解释性和通用人工智能还有待算法思想上的突破（第 11 章）。

五个发展方向

作者说，眼下的突破主要靠专用系统做“大数据、小任务”，未来方向是通用人工智能；为此要克服现有方法只适用于封闭静态环境和固定任务、鲁棒性差、解释性弱的缺陷（第 11 章）。

鲁棒方法（第 11 章）：鲁棒性指系统受到各种不确定因素干扰时仍能保持功能稳定的能力。现有方法默认数据分布、类别、属性、目标都不变，现实中这些都会变，一变原模型就可能表现很差，而且没有理论保证会差到什么程度。作者提出两条路：用符号学习从数据中学到形式化的知识，便于理解和推广；用深度神经网络做多任务学习。

可解释性（第 11 章）：深度学习的模型被看作黑盒子，说不清决策依据和是否可靠，阻碍了它在医学、金融等领域的应用。书里把可解释性方法分三类：建模之前的（如数据可视化）、本身可解释的（如基于规则的方法）、建模之后用来解释的（如敏感性分析）。

自主学习与持续学习（第 11 章）：书中引徐宗本的观点，下一代人工智能以适应环境为特征。较现实的中间目标是机器学习自动化，做到数据自生成、模型自构建、任务自切换等。自动机器学习（automated machine learning, AutoML）就是把整个流程自动化，在特征工程、模型构建、超参数调优上代替繁琐重复的人工。持续学习指学新任务时不忘旧知识；现有系统容易出现灾难性遗忘，适应了新任务，旧任务上的表现大幅下降。作者建议借鉴海马体和新皮层在记忆上的互补作用，在稳定和可塑之间取得平衡。

类脑智能与混合增强智能（第 11 章）：类脑智能受脑神经和认知机制启发，主要在功能层面借鉴人脑的计算方式，有望解决样本效率低、耗能高、缺乏逻辑推理等问题。混合增强智能承认机器无法完全取代人，把人的作用引入系统，研究人在回路、脑机接口、人机共驾等。

即使未来人工智能技术有了更大的进步，人机协同也将是必要的工作模式。

第 11 章 11.1.3 节，p.470

知识驱动与数据驱动结合（第 11 章）：书中引张钹等的观点，新一代人工智能要发挥知识、数据、算法、算力四个要素的作用。知识驱动可解释，但太依赖专家；数据驱动能从数据中找规律，但难解释、算法脆弱。他们提出在介于符号和向量之间的半语义空间里统一处理知识和数据，例如贝叶斯深度学习。

风险

四类安全风险（第 11 章）：

• 设计风险：设计者的价值观会嵌进系统；如何让人工智能追求与人类价值观相符的目标（价值对齐），还没有成熟方案。
• 算法风险：算法自己调参数和规则，形成“黑箱”，让传统监管失效；对抗攻击就是利用算法缺陷；还可能悄悄侵害消费者，比如大数据杀熟。
• 数据安全风险：隐私泄露和数据归属问题，用户数据可能在不知情时被拿去训练。
• 技术滥用风险：用于诈骗、黑客工具、批量制造虚假信息，深度伪造的假视频泛滥。

社会伦理挑战（第 11 章）：一是法律。一般认为人工智能只是工具，不是法律主体，所以《自然》等杂志不接受它做论文署名作者；但它会越来越多以“类人主体”的形式出现，算法歧视、自动驾驶事故该谁负责，已成为现实问题。二是社会治理。接触和使用人工智能的机会与能力不均，形成“数字鸿沟”，会扩大贫富差距；书中说预计约 80% 的工作会不同程度地受到影响，可能出现结构性失业（第 11 章）。

超人工智能（第 11 章）：作者说，现有人工智能只是完成特定任务的机器，可能威胁人类的是未来也许出现的强人工智能或超人工智能。书中引迈克斯·泰格马克整理的调查，多数人认为超人工智能几十年后出现；以雷·库兹韦尔（Kurzweil）为代表的学者预测，超人工智能 2045 年左右实现。对它是好是坏有三派：卢德主义者认为一定是坏事，坚决反对研发；数字乌托邦主义者（如谷歌创始人 Page）认为结果一定是好的；人工智能有益运动的支持者（如 Musk、Gates、Hawking）认为好坏取决于人类自己的选择。

作者的判断是：今天担心没有意识的人工智能统治人类，如同“杞人忧天”；但人工智能进入自动驾驶、无人战机、远程手术等高风险领域后，在自我进化中存在脱离控制的风险。短期威胁是自动驾驶安全、致命性自主武器和隐私泄露；长期威胁是能力全面超过人类的人工智能失控，无法保证它的利益和人类一致（第 11 章）。

应对

各国的举措（第 11 章）：书中说全球至少 60 个国家制定了治理政策。联合国教科文组织 2021 年发布《人工智能伦理问题建议书》；2023 年首届全球人工智能安全峰会上签署了《布莱奇利宣言》；欧盟实行分类监管的《人工智能法案》2024 年 8 月 1 日生效；美国监管要求较少，主要强调安全原则。中国 2019 年提出和谐友好、公平公正、包容共享、尊重隐私、安全可控、共担责任、开放协作、敏捷治理八项治理原则，2021 年发布《新一代人工智能伦理规范》，2023 年 8 月 15 日起实施《生成式人工智能服务管理暂行办法》。

从四方面确保安全有序（第 11 章）：

• 确立价值原则：人本、公正、责任。公正是不能片面遵循“资本逻辑”与“技术逻辑”，要让每个人都有平等使用的机会；责任是明确各环节各方的责任，建立事故问责机制。
• 建立伦理规范：给设计者、开发者、使用者定行为守则，把共识规范嵌入算法，避免“算法歧视”与“算法欺诈”。
• 研究安全技术：隐私加密、可信计算、伦理设计、安全评估，提升深度学习的可信性和可解释性。
• 健全制度保障：完善行业法规，推动《个人信息保护法》《数据安全法》实施，加强行业自律和国际合作。

人工智能是为增进人类的福祉和利益而创造出来的，人本原则是人工智能研发、应用的最高价值原则。

第 11 章 11.2.3 节，p.476

小结（第 11 章）：作者说，人工智能是人类创造的智能工具，能代替或辅助人完成重复性的脑力劳动，让人有更多时间从事创造性工作；以通用人工智能为导向、用人类知识指导数据驱动的算法，是重要的发展方向。书中引方滨兴的观点：人们总是先享用新技术的红利，之后才注意到它的安全问题。作者认为，要一方面提高可解释性、发展安全测试技术，一方面健全法律法规；人工智能也可能打开“潘多拉魔盒”。

人工智能作为一项新技术，既能赋能安全，又会伴生安全问题。

第 11 章 11.3 节，p.477

面对未知，我们应该心怀敬畏，审慎地对待人工智能的技术进步和应用推广，评估可能产生的颠覆性影响，预防和管控潜在的风险，让人工智能造福人类。

第 11 章 11.3 节，p.477