《人工智能·一种现代方法》——Peter Norvig / Stuart Russell

[thzt]

我们将人工智能定义为对从环境中接收感知信息并执行行动的智能体的研究。
每个这样的智能体都实现了一个把感知序列映射到行动的函数。
我们讨论了表达这些函数的各种不同方法，诸如产生式系统，反应式智能体，实时条件规划器，神经元网络，以及决策理论系统等。
我们把学习所扮演的角色解释为把设计者能接触的范围扩展到未知环境中，并且我们说明了这个角色是如何约束智能体设计，形成明确的知识表示和推理的。
我们并不把机器人学和视觉当做各自独立定义的问题对待，而是出现在为实现目标而服务的过程中。

（1）人工智能：围绕智能化智能体的概念，即能够决定要做什么然后执行行动的系统。
（2）问题求解：集中讨论了当需要提前思考若干步骤时决定要做什么的方法。
（3）知识与推理：讨论了关于世界的知识的表示方式，以及如何使用这些知识进行逻辑推理。
（4）规划：继续讨论了如何利用这些推理方法来决策做什么，特别是通过构造规划的方法。
（5）不确定知识与推理：集中讨论了当世界中存在不确定因素时的推理与决策。
（6）学习：描述了为这些决策元件生成所需知识的方法。
（7）通讯，感知与行动：描述了智能化智能体能够感知其环境的方式，以便了解正在进展的各种情况，以及能够将它的规划转换为真实行动的方法。
（8）结论：分析了人工智能的过去与未来，以及人工智能的哲学与伦理含义。

1. 人工智能

绪论

图灵测试是阿兰·图灵提出的，设计的目的是为智能提供一个满足可操作的要求的定义。
他建议预期提出一个长长的而可能有争议的清单来列举智能所需要的能力，不如采用一项基于人类这种无可质疑的智能实体的辨别能力的测试。
如果人类询问者在提出一些书面问题后，无法判断答案是否由人写出，那么计算机就通过了测试。

“思维法则”方法：
19世纪的逻辑学家发展处一种描述世界上的一切事物及其彼此之间关系的精确的命题符号。
与之形成对照，普通的算术符号主要用于描述数与数之间的相等和不相等关系的命题。
到了1965年，原则上，已经有程序可以求解任何用逻辑符号描述的可解问题。（如果问题无解，程序也许永远不会停止求解）
人工智能领域中传统上所谓的逻辑主义，希望通过编制上述程序来创造智能系统。

理性智能体方法：
智能体（agent）就是某种能够行动的东西。
但是人们期待计算机智能体有其它区别于简单”程序“的属性，诸如自主控制的操作，感知环境，持续能力，适应变化，以及有能力承担其它智能体的目标。
理性智能体则要通过自己的行动获得最佳结果，或者在不确定的情况下，获得最佳期望结果。
AI的“思维法则”方法中，强调的是正确的推论。
做出正确推论有时也是理性智能体的部分功能，因为实现理性行动的一个途径就是通过逻辑推理得出指定行动能达成目标的结论，再付诸实施。
另一方面，正确的推论并不是理性的全部内容，因为在许多情况下，没有能证明正确性的事情可做，但是仍然必须有所行动。
还有一些完成理性行动的方式不能说与推理过程有关。

我们需要表示知识并用之进行推理的能力，因为只有这样我们才能在多种不同的环境中制定出好的决策。
我们需要生成可理解的自然语言语句的能力，因为只有这样才能够被复杂的社会接受。
我们需要学习，不只是为了博学，而是因为对世界运转的更好理解使得我们可以找到解决问题的更有效的策略。
我们需要视觉感知，不仅仅因为世界是缤纷多彩的，更是为了对行为的可能后果由更好的了解。

由于上述原因，将AI的研究视为理性智能体的设计过程至少有两个好处。
首先，它比“思维法则”方法更加通用，因为正确的推理只是实现理性的几种可能的机制之一。
其次，它比建立在人类行为或者思维基础上的方法更经得起科学发展的检验，因为理性的标准有着清楚的定义并且是十分普遍的。
另一方面，人类行为可以很好的适应特定环境，并且部分取决于还远远未达到完善程度的复杂而未知的进化过程。

应该牢记的一个重点是：
我们将看到很长一段时间内实现完美的理性（即总能做正确的事情）在复杂的环境下是不可行的，这对计算能力的要求是在是太高了。

人工智能的基础：
（1）哲学：公元前428年——现在
a) 形式化规则能用来抽取合理的结论吗？
b) 精神的意识是如何从物质的大脑产生出来的？
c) 知识从哪里来？
d) 知识是如何导致行动的？
（2）数学：约800年——现在
a) 什么是抽取合理结论的形式化规则？
b) 什么可以被计算？
c) 我们如何用不确定的知识进行推理？
（3）经济学：1776年——现在
a) 我们如何决策以获得最大收益？
b) 我们在他人不合作的情况下如何做到这样？
c) 我们在收益遥遥无期的情况下如何做到这样？
（4）神经科学：1861年——现在
a) 大脑是如何处理信息的？
（5）心理学：1879年——现在
a) 人类和动物如何思考和行动的？
（6）计算机工程：1940年——现在
a) 我们如何才能制造出能干的计算机？
（7）控制论：1948年——现在
a) 人工制品怎样才能在自己的控制下运转？
（8）语言学：1957——现在
a) 语言和思维是怎样联系起来的？

智能化智能体

智能体，可以被视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。
一般而言，智能体在任何时刻的行动选择取决于到那个时刻为止该智能体的整个感知序列。
从数学上看，我们可以用一个把任意给定感知序列映射到智能体的行为的智能体函数来描述智能体的行为。
从智能体内部来看，人造智能体的智能体函数是通过智能体程序实现的。
智能体函数是一个抽象的数学表示，智能体程序是一个具体的实现，该程序在智能体自身的结构上运行。

智能体的概念，只是我们用来分析系统的一个工具，
而不是用来把整个世界划分成智能体和非智能体的绝对特性。

理性智能体，是做事正确的智能体。
当把智能体置于一个环境中后，它将针对收到的感知信息产生行动序列。
该行动序列引起环境历经一个状态序列，如果该状态序列正是想要的，那么这个智能体的性能良好。
性能度量，是智能体成功程度标准的具体化。

理性智能体的定义：
对于每个可能的感知序列，根据已知的感知序列提供的证据和智能体内建的先验知识，
理性智能体应该选择期望能使其性能度量最大化的行动。

我们需要仔细的区别理性和全知的概念。
一个全知的智能体知道它的行动产生的实际结果并且做出相应的动作，但一个全知者在现实中是不可能的。
理性是使期望的性能最大化，而完美是使实际的性能最大化。

扩展一个智能体依赖于设计者的先验知识而不是它自身的感知信息，
我们就说该智能体缺乏自主性。
理性智能体应该是自主的，它应该能够尽可能的学习，以弥补不全面的或者不正确的先验知识。

任务环境，是理性智能体要“解决”的基本“问题”。

AI的任务是设计智能体程序，通过它实现把感知信息映射到行动的智能体函数。
我们假设该程序要在某种具备实际传感器和执行器的计算装置上运行，我们称之为体系结构。
智能体 = 体系结构 + 程序

2. 问题求解

用搜索法对问题求解

本章介绍了在确定的，可观察的，静态的和完全已知的环境下，智能体可以用来选择行动的方法。
在这样的情况下，智能体可以构造行动序列达到目的，这个过程称为搜索。

在智能体可以开始搜索之前，它必须对目标加以形式化并且用目标对问题加以形式化。
一个问题由四个部分组成：初始状态，行动集合，目标测试函数和路径耗散函数。
问题的环境用状态空间表示，一条穿过状态空间从初始状态到达目标状态的路径是一个解。

（1）广度优先搜索
（2）代价一致搜索
（3）深度优先搜索
（4）深度有限搜索
（5）迭代深入搜索
（6）双向搜索

有信息的搜索和探索

本章考察了应用启发式减少搜索耗散，我们考虑了很多实用启发式的算法，
并发现即使用好的启发式，从搜索耗散角度来看，满足最优性也要付出相当的代价。

（1）最佳优先搜索
（2）贪婪最佳优先搜索
（3）A*搜索
（4）爬山法
（5）模拟退火
（6）遗传算法
（7）联机搜索

约束满足问题

约束满足问题（CSP）由变量和变量上的约束组成。
许多重要的现实世界问题都可以描述为CSP问题，CSP的结构可以用约束图表示。

（1）回溯搜索
（2）弧相容算法
（3）割集调整，树分解

对抗搜索

博弈游戏通过下列元素定义：初始状态，每个状态的合法行动，一个终止测试和可用在终止状态上的效用函数。

（1）极小值极大值算法
（2）α-β搜索算法

3. 知识与推理

逻辑智能体

本章说明了如何定义一种逻辑，使得智能体可以对世界进行推理。

智能化智能体需要关于世界的知识以便达到良好的决策。
知识以知识表示语言的语句形式包含在智能体内，这些语句存储在知识库中。
基于知识的智能体是由知识库和推理机制组成的，它的运转方式是把关于世界的语句存储到它的知识库中，
运用推理机制推导出新的语句，并用这些语句来决策采取什么行动。

表示语言，可以通过它的语法和语义来定义，其中语法指定语句的结构，而语义定义了每个语句在每个可能世界或模型中的真值。
语句α蕴含另一语句β，如果β在所有α为真的世界中都为真。
推理是从旧语句中生成新语句的过程。
可靠的推理算法只生成被蕴含的语句，完备的算法生成所有被蕴含的语句。

推理规则是可以用来寻找证明的可靠推理模式，归结规则产生一个用于表示为合取范式的知识库的完备推理算法。
前向链接和反向链接，都是用于以霍恩范式表示的知识库的非常自然的推理算法。

命题逻辑对于智能体内的特定任务是合理有效的，但是无法放大到大小无界的环境，
因为它没有足够的表达能力来准确的处理时间，空间以及对象间关系的普遍模式。

一阶逻辑

本章介绍了一阶逻辑，一种比命题逻辑表达能力更强的表示语言。

知识表示语言应该是陈述性的，可合成的，有表达能力的，上下文无关的以及无歧义的。
逻辑学在它们的本体论预定和知识论约定上存在不同，
命题逻辑只是对事实的存在进行限定，而一阶逻辑对于对象和关系的存在进行限定，因而获得更强的表达能力。

一阶逻辑的一个可能世界或模型是通过对象集，对象之间的关系以及可以应用于对象的函数来定义的。
常量符号命名对象，谓词符号命名关系，而函数符号命名函数。
解释制定了符号到模型的一个映射，复合项把函数符号应用于项，以命名对象。
给定一个解释和模型，就可以判断语句的真值。

一阶逻辑中的推理

本章对一阶逻辑中的逻辑推理以及实现推理的许多算法进行了分析。

（1）合一
（2）分离规则
（3）逻辑程序设计系统
（4）前向链接和反向链接

知识表示

本章通过深入研究如何表示各种知识，已经对如何构造真实的知识库有了一定认识。

大规模知识表示需要通用本体论来组织和结合各种特定领域的知识。
通用本体论需要涵盖各种广泛的知识，并且原则上应该有能力处理任何域。
我们提出了基于类别和事件演算的上位本体论，我们涉及了结构化对象，时间和空间，变化，过程，物质以及信度。
行动，事件和时间能在情景演算或更有表达力的表示方法中表示，这些表示方法使智能体能够根据逻辑推理构建规划。
智能体的精神状态能够用表示信度的字符串来表示。

专用表示系统，例如语义网络和描述逻辑，被设计用来帮助组织类别层次。
继承是推理的一个重要形式，允许对象属性从它们在类别中的隶属关系演绎出来。
在逻辑程序中实现的封闭世界假设，提供了一个避免必须说明大量否定信息的简单方法，它最好被解释为能够被附加信息覆盖的缺省。
非单调逻辑，诸如界限和缺省逻辑，通常想要捕捉到缺省推理，解集程序设计能加速非单调推理。
真值维护系统高效的处理知识更新和修正。

有看似合理的主张宣称，形式化知识表示研究开始于古印度关于印度教圣典的梵语语法的经典理论化，这可以追溯到公元前的第一个千年。
在西方，古希腊数学中术语定义的使用可以被看做最早的例子。
事实上，任何领域的技术术语的发展都可以被视为一种形式的知识表示。

对时间，变化，行动和事件的表示已经在哲学和理论计算机科学，也在人工智能中进行了广泛研究。
最古老的方法是时序逻辑，这是专门的逻辑，在其中每个模型描述一个随着时间变化的完整轨迹，而不是一个静态的关系结构。

4. 规划

规划

提出能达到一定目标的行动序列的任务称为规划。
本章我们在确定性，完全可观察的环境中定义了规划问题。
我们描述了用于规划问题的主要表示方法和一些用来求解它们的算法方法。

规划系统是问题求解算法，它在关于状态和行动的明确命题（或一阶）表示上运转。

（1）偏序规划（POP）算法
（2）规划图
（3）Graphplan算法
（4）Satplan算法

现实世界的规划与行动

本章处理了真实世界的规划和行动的一些复杂因素。

（1）调度算法
（2）分层任务网络（HTN）
（3）条件规划
（4）无传感的或一致性的规划
（5）重新规划，持续规划，多智能体规划

5. 不确定知识与推理

不确定性

本章论证了概率理论是进行不确定性推理的合适方法。
不确定性是因为惰性和无知而出现的，在复杂的，动态的或者难以接近的环境中，不确定性是不可避免的。
概率表达了智能体无法得到语句真值的确定决策的无呢过程度，概率概括了智能体的信心。

（1）先验概率
（2）条件概率
（3）全联合概率分布
（4）贝叶斯法则

概率推理

本章描述了贝叶斯网络，一种已经得到成熟发展的不确定知识表示方法。
贝叶斯网络所扮演的角色大致相当于命题逻辑在确定知识中的角色。
贝叶斯网络是一个节点对应于随机变量的有向无环图，每个节点在给定父节点下都有一个条件概率分布。
贝叶斯网络提供了一种表示域中条件独立关系的简洁方式。

（1）变量消元法
（2）似然加权，马尔可夫链蒙特卡洛方法
（3）关系概率模型（RPM）
（4）真值函数性系统

关于时间的概率推理

本章所强调的主要是关于概率时序过程的表示与推理的一般问题。

（1）隐马尔可夫模型
（2）卡尔曼滤波器
（3）动态贝叶斯网络

语音识别和运动对象跟踪是时序概率模型的两类重要应用。

制定简单决策

本章说明了如何将效用理论与概率结合起来，以使一个智能体能够选择最大化其期望性能的行动。

概率理论描述在证据的基础上，一个智能体应该相信什么。
而效用理论描述一个智能体想要什么。
决策理论则将两者结合起来，以描述一个智能体应该做什么。

我们可以使用决策理论建造一个系统，通过考虑所有可能的行动，选择能导致最佳期望结果的那个行动，从而做出决策。
这样的一个系统被称为理性智能体。

（1）多属性效用理论
（2）决策网络
（3）专家系统

制定复杂决策

本章显示了如何使用关于世界的知识进行决策，即使行动的结果是不确定的以及行动的回报可能直到很多行动完成以后才会兑现。

（1）马尔可夫决策过程（MDP）
（2）价值迭代算法
（3）策略迭代
（4）动态决策网络
（5）博弈论
（6）机制设计

6. 学习

从观察中学习

本章所关注的内容是从实例中归纳学习确定性的函数。

如果从教室那里或者从环境中得到可用的反馈，能够为实例提供正确的值，那么这样的学习问题称为有监督的学习。
这个也被称为归纳学习的任务，要从函数输入和输出的实例中学习一个函数。
学习离散值函数的被称为分类，而学习连续函数的则被称为回归。
归纳学习涉及寻找一个与实例相符合的一致假设。

（1）奥卡姆剃刀原则
（2）决策树
（3）学习曲线
（4）集体学习方法
（5）计算学习理论

学习中的知识

本章研究了各种使用先验知识帮助智能体从新的经验中进行学习的方法。
因为很多先验知识是用关系模型而不是基于属性的模型来表示的，所以我们也讨论了一些允许对关系模型进行学习的系统。

（1）累积学习
（2）基于即使的学习（EBL）
（3）基于相关性的学习（RBL）
（4）基于知识的归纳学习（KBIL）
（5）归纳逻辑程序设计

统计学习方法

统计学习方法的范围包括从简单的平均值计算到构造诸如贝叶斯网络以及神经元网络这样的复杂模型的方法。
它们有许多应用，遍及计算机科学领域，工程领域，神经生物学领域，心理学领域以及物理学领域等等。

（1）贝叶斯学习
（2）最大后验学习方法（MAP）
（3）最大似然学习方法
（4）EM算法
（5）基于实例的模型
（6）神经元网络
（7）感知器
（8）多层前馈神经元网络
（9）反向传播算法

强化学习

本章考察了强化学习问题，只提供感知信息和偶尔获得的回报，一个智能体如何在未知的环境中变得精明能干。
强化学习可以视为整个人工智能问题的缩影，不过在许多简化设置中进行研究，推动了进步。

（1）直接效用估计
（2）自适应动态规划（ADP）
（3）时序差分方法（TD）
（4）策略搜索

7. 通讯，感知与行动

通讯

自然语言理解是人工智能最重要的子领域之一。
它从哲学和语言学，以及逻辑方法，概率知识表示和推理技术中获得启迪。
与人工智能的其它领域不同，自然语言理解需要有关实际人类行为的经验化的研究。

智能体之间为了达到确定的意图而互相发送信号：通知，警告，请求帮助，共享知识或者是做出承诺。
用这样的方式发送信号被称为言语行为。
最终所有的言语行为都是为了使另一个智能体相信某事或去做某事而进行的努力。

语言由约定俗成的，传达含义的符号组成。
在这种意义上，很多动物也是用符号。
不过人类看来是唯一能够使用语法产生多种多样无限量的结构化消息的动物。

形式语言理论以及短语结构语法（特别是上下文无关文法）都是处理自然语言某些方法的有用工具。
上下文无关语言中的语句可以用图分析器在O(n^3)的时间内完成句法分析。
为了处理类似主语与动词一致以及代词格的问题，增强一个语法是很方便的方法。
确定子句语法（DCG）是一种考虑了增强的形式化方法。
通过DCG，句法分析和语义解释（甚至生成）都可以用逻辑推导实现。

语义解释也是可以用增强语法处理的，准逻辑形式能够成为句法树和语义之间一种有用的中间形式。

歧义性，篇章，语法归纳。

概率语言处理

（1）n元的概率语言模型
（2）概率CFG
（3）信息检索系统
（4）信息抽取系统
（5）机器翻译系统

感知

虽然感知看起来对人类来说是一种不费力气的活动，它却需要大量的复杂计算。
视觉的目标是为诸如操纵，导航和物体识别等任务抽取所需的信息。

（1）成像过程
（2）初级视觉处理算法
（3）姿态估计算法

机器人学

机器人学关心的是操纵物理世界的智能化智能体。

机器人装备有传感器来感知它们的环境，以及它们用来对其环境施加物理力的效应器。
机器人感知关心的是根据传感器数据对与决策相关的量进行估计。

（1）卡尔曼滤波器
（2）粒子滤波器
（3）机器人运动规划
（4）单元分解技术
（5）势场技术

8. 结论

哲学基础

“机器能够智能的行动”（或者也许更确切的，其行动看起来如同它们是有智能的），这种断言被哲学家称为弱人工智能（weak AI）假设。
而“能够如此行事的机器确实在思考”（与模拟思考相对）的断言，则被称为强人工智能假设（strong AI）。

图灵拒绝了问题“机器能思考吗？”，而用一个行为测试取而代之。
他预见到了许多对思维机器的可能性的反对意见。
很少有人工智能研究者关注图灵测试，他们更喜欢关注自己的系统在实用任务上的性能，而不是模仿人类的能力。

人工智能：现状与未来

我们只能向前看到很短的距离，但是我们能够看到仍然有很多事情要做。——图灵