本书是一本经典的人工智能教材,全面阐述了人工智能的基础理论,有效结合了求解智能问题的数据结构以及实现的算法,把人工智能的应用程序应用于实际环境中,并从社会和哲学、心理学以及神经生理学角度对人工智能进行了独特的讨论。新版中增加了对“基于随机方法的机器学习”的介绍,并提出了一些新的主题,如涌现计算、本体论、随机分割算法等。
人工智能 复杂问题求解的结构和策略(原书第6版)
Artificial Intelligence
Structures and Strategies for Complex Problem Solving
Sixth Edition
(美) George F. Luger新墨西哥大学 著 郭茂祖 刘 扬 玄 萍 王春宇 等译
“在人工智能领域里,学生经常遇到许多很难的概念;本书通过精选的实例与简单明了的视图,清晰而准确地阐述这些概念。”
—— Joseph,圣迭哥州立大学
“本书是人工智能课程的完美补充。它既给读者以历史的观点,又给出所有技术的实用指南。这是一本必须要推荐的人工智能的图书。”
—— Pascal Rebreyend,瑞典达拉那大学
“该书的写作风格和全面的论述使它成为人工智能领域很有价值的文献。”
—— Malachy Eaton,利默里克大学
本书是一本经典的人工智能教材,全面阐述了人工智能的基础理论,有效结合了求解智能问题的数据结构以及实现的算法,把人工智能的应用程序应用于实际环境中,并从社会和哲学、心理学以及神经生理学角度对人工智能进行了全面的讨论。
本版新增内容
新增一章,介绍用于机器学习的随机方法,包括一阶贝叶斯网络、各种隐马尔可夫模型、马尔可夫随机场推理和循环信念传播。
介绍针对期望最大化学习以及利用马尔可夫链蒙特卡罗抽样的结构化学习的参数选择,强化学习中马尔可夫决策过程的利用。
介绍智能体技术和本体的使用。
介绍自然语言处理的动态规划(Earley语法分析)以及Viterbi等其他概率语法分析技术。
书中的许多算法采用Prolog、LISP和Java语言来构建。
作者简介
George F. Luger
1973年在宾夕法尼亚大学获得博士学位,并在之后的5年间在爱丁堡大学人工智能系进行博士后研究,现在是新墨西哥大学计算机科学研究、语言学及心理学教授。
我们通过做来学习我们必须做的……
——亚里士多德《伦理学》(Ethics)
欢迎阅读第6版
我很高兴被邀请写作这本《人工智能》教材的第6版。这是对20多年来前几个版本的褒奖,说明我们获取AI的方法得到了大家的高度评价。同样令人兴奋的是,随着人工智能领域的新的发展,我们能够在每个新版本中介绍这些新发展和新技术。我们感谢许多读者、同事和学生督促我们及时地更新相关主题。
前几版中的许多章节现在仍然具有很好的适用性,包括对逻辑、搜索算法、知识表示、产生式系统、机器学习以及用LISP、Prolog和本版中的Java开发的程序设计技术的介绍。这些仍然是人工智能的中心问题,也是这个新版本的重点。
这本书仍然是容易理解的。我们介绍了关键的表示技术,包括逻辑、语义和连接主义网络、图模型等。我们首先用伪代码的形式清楚地描述了搜索算法,然后在补充材料中介绍了许多用Prolog、LISP和/或Java实现的搜索算法。希望有学习主动性的学生能够掌握我们这些核心实现并把它们扩展到新的应用领域。
第6版中增加了新的一章(第13章)来介绍基于随机方法的机器学习。随机技术对人工智能的影响日益增大,尤其是在诊断推理、预测推理、自然语言理解、机器人学和机器学习这些领域。为了支持这些新兴的技术,我们扩充了对贝叶斯定理、马尔可夫模型、贝叶斯网络以及相关图模型的介绍。另外,还扩充讨论了概率有限状态自动机、隐马尔可夫模型、基于Earley解析器和Viterbi算法实现的动态规划。其他一些主题(如涌现计算、本体论、随机分割算法)在前几版中写得有些仓促,现在已成为比较重要的主题,值得更加全面地讨论。第6版中所做的修改反映出了新出现的人工智能问题,同时也是人工智能领域具有持久活力的证明。
随着AI研究课题的不断扩大,我们得到了很多人(包括出版商、编辑、朋友、同事,尤其是广大读者)的支持,他们使我们的工作具有长久而又有意义的生命力。能得到这样的机会,我们仍然很兴奋:因为很少有人会鼓励科学家从他们自己较窄的研究兴趣出发写出宏篇巨著。我们对出版商和读者为我们提供这样的机会表示感谢。我们也很受鼓舞,因为本书前几版已经用于全世界许多人工智能领域,而且被翻译成了许多不同语言(包括德语、波兰语、葡萄牙语、俄语以及中文简体和繁体)。
虽然人工智能和大多数工程学科一样,必须通过为实际问题提供解决方案来证明自己对商业领域的价值,但是我们与许多同事和学生却以相同的原因进入AI领域:我们想要理解和探索能够进行智能思考和动作的头脑的工作机制。我们避免使用“智能是人类的特有能力”这样粗浅的说法,而是相信我们能够通过设计和评估人工智能产物来有效地研究可能的智能空间。尽管我们的经历使我们没有理由改变初衷,但是我们的工作在广度、复杂度和创新性方面又上了一个新的台阶。在前面版本的前言中,我们概括了三点主张,我们相信坚持这三点主张可以使我们的方法在人工智能教学过程中取得卓越的成效。在这一版的前言中,自然要回到这些主题看看它们是如何随着领域发展而延续的。
第一点主张是通过详细讨论人工智能的理论基础来统一不同的分支。在我们首次采纳这点主张时,主要问题似乎是协调两种研究者,一种着重于对人工智能进行详细描述和形式化理论分析(整洁派),另一种相信智能本身是某种豪华的工具并且能够用应用驱动的特定方法获得(杂乱派)。事实证明,这种二分法过于简单。
在当代的AI中,整洁派和杂乱派之间的争论,已经引起了物理符号系统支持者和神经网络研究者、逻辑学家和非逻辑方式进化人工生命形式的设计者、专家系统建造者和基于案例的推理者以及相信已经获得人工智能的人和认为人工智能永远无法获得的人之间的许多争论。AI是一门前沿科学,在这里,离经叛道者、探索者、极端预言家和其他梦想家被形式主义和经验主义慢慢驯服。我们最初的这种印象现在让位于一个不同的比喻:在一个巨大、无秩序但大体上和平的城市里,有秩序的中产阶级邻居从不同的、混乱的、狂放不羁的地区来此谋生。在我们致力于写作本书不同版本的几年中,一幅关于智能结构的引人注目的图画开始从城市的结构、艺术和工业中显现出来。
智能太复杂了,无法用任何单一的理论来描述;研究者正在构建一个从多个抽象层次上刻画智能的理论层次结构。在这个结构的底层,神经网络、遗传算法和其他形式的涌现计算使我们能理解所有形式的智能行为之下必然隐含的适应、感知、表现和与物质世界交互的过程。通过某些仍然是部分理解的归结,这个由盲目原始的参与者构成的混乱群体引出了逻辑推理的更冷静模式。在这个更高的层次上,逻辑学家在亚里士多德贡献的基础上,描绘演绎、反绎、归纳、真值维护和推理的无数其他方式和方法。在更高层抽象上,专家系统、智能主体和自然语言理解程序的设计者渐渐认识到社会过程在产生、传播和维持知识方面所起的作用。
从这一点来看,在AI事业中,理性主义和经验主义两种极端都只能得到一些片面的结论,两种极端的适用性和普遍性都受到限制。作者采取了另一种态度,即认为经验主义者的条件作用(语义网、脚本、包容结构)和理性主义者清晰明确的观点(谓词演算、非单调逻辑、自动推理)构成了第三个观点——贝叶斯定理。关联不变性的经验以智能的多个智能主体的期望为条件,学习这些不变性反过来可以使将来的期望发生偏离。作为哲学家,我们有责任分析人工智能事业在认识论上的合法性。为完成这一任务,我们在第16章讨论了理性主义工程、经验主义难题,并提出了一个基于贝叶斯的构造论者的一致观点。在第6版中,我们触及了呈现这个AI事业的所有层次。
我们在前面版本中提出的第二点主张是在AI方法学中高级表示形式和搜索技术占有中心位置。这可能是前面版本及AI许多早期工作中最有争议的方面,许多涌现计算的研究者质疑符号推理和指称语义在思考中是否有作用。虽然为事物给定名字的表示法思想受到了神经网络或人工生命的涌现模式提供的隐含表示法的挑战,但我们相信对于任何严谨的人工智能研究者,理解表示法和搜索仍然是基本的。同时,我们认为第1章对历史传统和先驱的回顾是人工智能教育不可或缺的部分。而且,高级表示形式和搜索技术也是分析非符号人工智能的多个方面(如分析神经网络的表达能力或者通过遗传算法的适应度范围计算候选问题解的进展)的无价工具。第16章中对现代AI的不同方法进行了比较和评论。
我们在前面版本中提出的第三点主张是将人工智能放到经验科学的上下文中。引用以前版本中Newell and Simon(1976)的图灵奖演讲:
……AI不是对科学传统的某种奇怪的偏离,而……是对关于智能知识的寻求和对智能本身的理解的一部分。另外,AI程序设计工具和研究程序设计的方法学……对探究外界环境都是完美的。我们的工具提供了一种理解和质疑的方法。我们通过逐步近似来察觉和了解自然现象。
这样,将每个设计和程序都看成是对自然的一个试验:我们提出一个表示,生成一个搜索算法,并质疑这样的描述是否能够适当地说明部分智能现象。自然世界给我们的疑问一个回答。我们的实验可能会被拆解、修订、扩充,然后再次运行。模型可能被改进,同时我们的理解范围也进一步扩大了。
第6版的新内容
第6版最主要的修改是扩充了获取人工智能的随机方法。为此,我们修改了93节,并且加入了第13章来介绍基于概率的机器学习。我们更加全面地介绍了随机的人工智能工具及其在学习和自然语言中的应用。
我们从集合论和计数的基础知识开始,逐步引出概率、随机变量和独立性等概念。接着,以一种症状和一种疾病为例,介绍并使用了贝叶斯定理,然后将其推广到最通用的形式。我们分析研究了应用贝叶斯定理的假设,介绍了argmax和简单贝叶斯方法。我们介绍了随机推理的一些例子,包括语言现象分析和Viterbi算法。我们还介绍了条件独立性的思想,随后在第9章引出了关于贝叶斯信念网络(BBN)的介绍。
第13章介绍了隐马尔可夫模型(HMM),并通过几个例子说明了其使用方法。我们也介绍了HMM的几种变形,包括自回归和层次化的隐马尔可夫模型,还介绍了动态贝叶斯网络(DBN),并举例说明了它们的使用方法。我们讨论了参数和结构学习,介绍了期望最大化方法并举例说明了它们在松散信念传播中的使用。最后,我们在扩展早期的强化学习表示的基础上,介绍了马尔可夫决策过程(MDP)以及部分可观测的马尔可夫决策过程(POMDP)。
我们扩充了一些实例,这些例子用来解释概率有限状态自动机和概率接受器以及动态规划的使用,尤其是解释如何使用随机测量的动态规划算法(Viterbi算法)。我们添加了一个随机英语语法分析器(以爱丁堡大学Mark Steedman的工作为基础)以及Earley解析器中动态规划的使用。
我们做的一个主要决定是从本书中删除介绍Prolog和LISP的章节,部分原因是它们太庞大了。我们也收集了一些用Java实现的人工智能算法。当增加新的一章(第13章)来介绍基于随机方法的机器学习时,我们觉得这本书太厚、太笨重了。这样,第6版比第5版少了150多页(指的是英文原版书),以Prolog、LISP和Java语言实现的AI算法以补充材料的形式发行。在人工智能的研究刚开始时,我们总是认为这样的方法对于理解AI算法的优势(和局限性)是非常有益的——那就是要实现这些算法!我们鼓励这一代的读者切实这样去做:浏览这些补充材料,实现我们提出的这些算法并进行实验。
最后,我们按照惯例更新了参考文献限于篇幅,“参考文献”以PDF形式放在本书的网站(http://wwwhzbookcom)上,有需要的读者可下载使用。——编辑注
和一些材料。在修订后的第16章中,我们又回来讨论智能本性的更深入问题和产生智能机器的可能性。
第6版的内容
第1章简单介绍人工智能。我们从哲学、心理学和其他研究领域中试图了解头脑和智能的历史。从重要意义上讲,AI是一门古老的科学,至少可以追溯到亚里士多德。对这些背景的了解是理解现代研究中主要问题的基本条件。我们还介绍了AI中一些重要应用领域的概要情况。第1章的目的是为后面的理论和应用提供背景知识和动机。
第2、3、4、5、6章(第二部分)介绍AI问题求解的研究工具。第2章介绍描述问题本质特征的谓词演算,谓词演算既是一种数学系统,也是一种表示语言。第3章介绍搜索以及用来实现搜索的算法和数据结构,搜索技术用来组织问题情景的探测。第4章讨论启发式在聚焦和约束基于搜索的问题求解中所起的基本作用。第5章介绍随机方法,这是一种在不确定情况下推理的重要技术。第6章介绍构建这些搜索算法所需的软件体系结构,包括黑板和产生式系统。
第7、8、9章构成本书的第三部分:人工智能、知识密集型问题求解、变化和模糊情况下推理的表示法。第7章介绍AI表示法的发展历程。我们从对基于关联的网络的讨论开始,扩展这个模型以包含概念依赖理论、框架和脚本。然后介绍一种特别的形式方法——概念图的深入检验,强调知识表示中包含的认识论问题,并且说明这些问题是如何在现代表示语言中表示的。在第14章扩展了这个形式方法,说明了如何用概念图来实现自然语言数据库前端。第7章的最后介绍更多的现代表示方法,包括Copycat结构和面向主体的结构。
第8章介绍基于规则的专家系统以及基于案例和基于模型的推理系统,包括来自NASA空间计划的例子。这些问题求解方法是作为第二部分内容的自然延伸来进行介绍的:用谓词演算表达式的产生式系统来协调一个图搜索。这一章最后分析每种知识密集型问题求解方法的优势和不足。
第9章介绍用不确定信息和不可靠信息进行推理的模型。我们讨论用于不确定情况推理的贝叶斯模型、信念网络、Dempster-Shafer、因果模型以及Stanford确信度代数。第9章还包括真值维护算法、最小模型推理、基于逻辑的反绎以及贝叶斯信念网络的团树算法。
第四部分包括第10章到第13章,提供机器学习中问题的扩充说明。在第10章,我们对基于符号的学习算法进行了详细的介绍,这是一个硕果累累的研究领域,产生了大量的问题和解决方法。这些学习算法在其目标、训练数据、学习策略和使用的知识表示法上各不相同。基于符号的学习包括归纳、概念学习、变形空间搜索和ID3。归纳偏置的作用也要考虑,即从数据模式中泛化,同时还要考虑在基于解释的学习中有效利用从单个示例中学习到的知识。分类学习(或者说概念聚类)与无监督学习一起介绍。这一章最后介绍强化学习,即把来自环境的反馈结合到决策策略中的能力。
第11章介绍了神经网络,这类网络经常称为学习的子符号或连接模型。在神经网络中,信息隐含在一个连接的处理机集合的组织和权重中,学习包括结点权重和系统结构的重新排列和修改。我们介绍了许多连接结构,包括感知机学习、反传和逆传。我们展示了Kohonen、Grossberg和Hebbian模型。我们介绍了联想学习和吸引子模型,包括Hopfield网络的例子。
第12章介绍学习的遗传算法和进化方法。从这个观点来看,学习可以看成是一个涌现和适应过程。在介绍了几个基于遗传算法的问题求解实例后,我们介绍遗传技术在更通用的问题求解器中的应用,这其中包括分类器系统和遗传程序设计。然后结合人工生命研究中的例子描述基于社会的学习。我们用圣达菲研究所(Santa Fe Institute)关于涌现计算研究的一个例子结束本章。
第13章介绍机器学习的随机方法。首先定义隐马尔可夫模型,然后介绍几个重要的变形,包括自回归和层次化的隐马尔可夫模型。我们接下来介绍动态贝叶斯网络(是HMM的一个推广),它也能够通过时间周期跟踪系统。对于在诊断和预测推理中模拟复杂环境的改变,这些技术是非常有用的。最后,我们为第10章介绍的强化学习增加了一个概率部分,介绍了马尔可夫决策过程(MDP)和部分可观测的马尔可夫决策过程(POMDP)。
第五部分包括第14章和第15章,介绍自动推理和自然语言理解。定理证明(常常称为自动推理)是AI研究最早的领域之一。在第14章,我们讨论这一领域中最早的程序,包括逻辑理论家和通用问题求解器。本章的焦点是二元归结证明过程,特别是归结反驳,还介绍了使用超归结和参数调制的高级推理。最后,我们把Prolog解释器描述为一个基于Horn子句和归结的推理系统,并将Prolog计算看成是逻辑程序设计范例的一个实例。
第15章介绍自然语言理解。我们在第7章中已经介绍过传统的自然语言理解方法,就是用许多语法结构进行例示。这里我们又补充了随机方法,包括马尔可夫模型、图解析(Earley算法)、交互信息聚类和基于统计的解析。本章的最后是几个例子,包括将这些自然语言理解技术应用于数据库查询系统(一个文本摘要系统)以及使用机器学习方法去泛化从万维网获得的结果。
最后,第16章是本书的后记。其中提到了智能系统科学的可能性问题,考虑了现在AI面临的挑战,讨论了目前AI的限制,并设计了AI激动人心的未来。
使用本书
人工智能是一个很大的领域,因此这是一本很厚的书。尽管学习本书时可能会需要超过一个学期才能覆盖里面所有的内容,但是我们对本书进行了仔细设计,使得大家可以采取不同的路径来学习其中的内容。通过选择内容的子集,我们既可以将这本教材用于一个学期的课程,也可以用于整个学年(两个学期)的课程。
我们假设绝大多数学生已经学习了离散数学的入门课程,包括谓词演算、集合论、计数和图论。如果学生没有学过这些课程,那么教师应该花更多的时间讲解本书开始部分(21节、31节和51节)的那些概念。我们还假设学生已经学习了数据结构课程,包括树、图、递归搜索,会使用堆栈、队列和优先级队列。如果学生没有学过这些课程,那么多花些时间在第3、4、6章的开始部分。
在一个学期的课程中,我们会很快扫过本书的前两部分。有了这个准备,学生就能够看懂第三部分的内容。接着考虑补充材料中的Prolog、LISP或者Java代码,要求学生实现第二部分中的主要表示和搜索技术。也可以选择在课程中早点介绍一门语言(如Prolog),来检验遇到的数据结构和搜索技术。我们觉得语言部分介绍的元解释器对于构建基于规则的和其他知识密集型问题的求解器很有帮助。Prolog、LISP和Java都是构建自然语言理解和学习系统的极好工具,这些结构在第二部分和第三部分加以介绍,在补充材料中有相关例子。
在两个学期的课程中,可以覆盖第四部分和第五部分中的所有应用领域,特别是机器学习的几章,要进行较为详细的讲解。我们也期望学生做一个更详细的程序设计项目。我们认为这对于学生在第二学期复习AI文献中的许多基本资源非常重要。让学生知道我们处于AI事业发展中的什么位置、我们如何到达这里并且让学生对人工智能未来的进展有一个认识都是至关重要的,为此我们使用互联网上的资料或者选择一个读物合集,比如《Computation and Intelligence》 (Luger 1995)。
本书中的算法采用类Pascal的伪代码进行描述。符号中使用了Pascal的控制结构及英语描述的检查和操作。我们在Pascal控制结构中加入了两个有用的结构。第一个是修改过的case语句,它使每一个分支都可以用一个任意的布尔检检来标记,而不是像在标准Pascal中只能将一个变量的值与不变的case标记相比较。case依次测试这些条件,直到一个为真,然后执行相关的动作;所有其他动作被忽略。熟悉LISP的人会注意到这和LISP的cond语句有同样的语义。
另一个增加的有用结构是return语句,它可以有一个参数,可以出现在过程或函数中的任何位置。当遇到return时,会使程序立即退出该函数,将其参数作为结果返回。除此之外,我们都使用Pascal的结构,再加上英语描述,这可以使算法清晰易读。
可以获得的补充材料
第6版附带了由我的研究生维护的网站。这个网站由新墨西哥大学的两个研究生Alejandro CdeBaca和Cheng Liu建立。网站的内容包括大多数章节后面建议的补充材料、一些示例问题及其解决方法以及对学生项目的许多建议。除了补充材料中的Prolog、LISP和Java程序外,网站上还有许多用Java和C++写的AI算法。欢迎同学们使用这些材料,并添加自己的评论、代码和批评。网站地址是wwwcsunmedu/~luger/ai-final/。
我的Email地址是luger@csunmedu,欢迎各位读者来信交流心得体会。
致谢
虽然我是第6版的署名作者,但本书一直是我在新墨西哥大学做计算机科学、心理学和语言学教授时努力的成果,其中也离不开我的同事们、研究生和朋友们的贡献。第6版同时也是许多读者通过Email给我评价、更正和建议的成果。本书将继续这种方法,反映“团体”的成果。因此,介绍内容时,我将继续使用“我们”、“我们的”这些人称代词。
我要感谢Bill Stubblefield,他是本书前3版的合著者,对本书有20多年的贡献,更重要的是我们的友谊。我也要感谢许多帮助完成第6版和以前版本的审稿人,包括Dennis Bahler、Leonardo Bottaci、Skona Brittain、Philip Chan、Peter Collingwood、Mehdi Dastani、John Donald、Sarah Douglas、Christophe GiraudCarrier、Andrew Kosoresow、Terran Lane、 Chris Malcolm、Ray Mooney、Marek Perkowski、Barak Pearmutter、Dan Pless、Bruce Porter、Stuart Shapiro、Julian Richardson、Jude Shavlik、John Sheppard、Carl Stern、Leon van der Torre、Marco Valtorta和Bob Veroff。我们还要感谢读者通过Email给我们寄来无数建议和评价。最后,感谢Chris Malcolm、Brendan McGonnigle和Akasha Tang审定第16章。
我们新墨西哥大学的同事中,感谢Dan Pless、Nikita Sakhanenko、Roshan Rammohan和Chayan Chakrabarti在扩充第5、9和13章的材料中起到了主要作用,感谢Joseph Lewis对第9章和第16章的贡献,感谢Carl Stern帮助扩充第11章连接学习,感谢Bob Veroff审定第14章中自动推理部分的材料,感谢Jared Saia、Stan Lee和Paul dePalma帮助完成第15章自然语言理解的随机方法。
我们要感谢Academic Press允许重印第11章中的许多材料,这些材料最早出版于《Cognitive Science:The Science of Intelligent Systems》(Luger 1994)。最后,我们感谢20多年来新墨西哥大学使用本书的学生,他们拓宽了我们的视野,帮助改掉了书中许多印刷错误和失误。
我们感谢BenjaminCummings、AddisonWesleyLongman和Pearson Education的许多朋友,他们对我们完成第6版的写作工作给予了很多支持和鼓励。特别是Alan Apt帮助我们完成第1版,Lisa Moller和Mary Tudor帮助我们完成第2版,Victoria Henderson、Louise Wilson和Karen Mosman帮助我们完成第3版,Keith Mansfield、Karen Sutherland和Anita Atkinson帮助我们完成第4版, Keith Mansfield、Owen Knight、Anita Atkinson和Mary Lince帮助我们完成第5版,以及Simon Plumtree、Matt Goldstein、Joe Vetere和Sarah Milmore帮助我们完成第6版。AddisonWesley美国公司的Katherine Haratunian在分发教师指导手册和PowerPoint演示材料工作上起了巨大的作用(这些是由AddisonWesley Pearson维护的,只能通过读者当地的销售代表得到)。感谢新墨西哥大学的Linda Cicarella帮助我们准备了许多图表。
我们感谢Thomas Barrow,一位国际知名的艺术家、新墨西哥大学艺术教授(退休),他绘制了书中的插图。
人工智能是一门激动人心的、回报丰厚的学科,祝你在认识到其力量和挑战的同时享受学习的快乐。
George Luger
2008年1月1日
Albuquerque
计算机科学及应用
“在该领域里学生经常遇到许多很难的概念;通过深刻的实例与简单明了的视图,该书中清晰而准确地阐述这些概念。”
——Joseph,圣迭哥州立大学
“本书是人工智能课程的完美补充。它既给读者以历史的观点,又给出所有技术的实用指南。这是一本必须要推荐的人工智能的图书。”
——Pascal Rebreyend,瑞典达拉那大学
“该书的写作风格和全面的论述使它成为人工智能领域很有价值的文献。”
——Malachy Eaton,利默里克大学
本书是一本经典的人工智能教材,全面阐述了人工智能的基础理论,有效结合了求解智能问题的数据结构以及实现的算法,把人工智能的应用程序应用于实际环境中,并从社会和哲学、心理学以及神经生理学角度对人工智能进行了独特的讨论。
本版新增内容
? ?新增一章,介绍用于机器学习的随机方法,包括一阶贝叶斯网络、各种隐马尔可夫模型、马尔可夫随机场推理和循环信念传播。
? ?介绍针对期望最大化学习以及利用马尔可夫链蒙特卡罗抽样的结构化学习的参数选择,强化学习中马尔可夫决策过程的利用。
? ?介绍智能体技术和本体的使用。
? ?介绍自然语言处理的动态规划(Earley语法分析)以及Viterbi等其他概率语法分析技术。
? ?书中的许多算法采用Prolog、LISP和Java语言来构建。
(美) George F. Luger 著:George F. Luger 1973年在宾夕法尼亚大学获得博士学位,并在之后的5年间在爱丁堡大学人工智能系进行博士后研究,现在是新墨西哥大学计算机科学研究、语言学及心理学教授。
郭茂祖 刘扬 玄萍 王春宇 等译:暂无简介
人工智能(AI)最开始的动机是想创造一种机器,它不仅能够思考,而且还有可能和人类交流,这是计算的最高级目标。在过去的许多年里,人工智能的研究者们在探索智能机制的同时,还使人工智能在实际领域取得了更广泛的应用。我们可以使用不同的人工智能策略解决很多在实际应用计算机技术时出现的复杂问题。众所周知,智能本身是非常复杂的,难以用单一的理论来描述。因此,产生了一系列的理论从不同的抽象层次刻画这个主题。在最低层次,神经网络、遗传算法以及其他形式的理论可以辅助理解适应性原理、感知机制以及与物理世界的交互机制。在更加抽象的层次,专家系统的设计、智能主体、随机模型以及自然语言理解程序反映了知识在智能中的角色和创建、传递、保持的社会过程。更深一层,逻辑学家提出了演绎、反绎、归纳、真值维护以及其他的推理模型和方式。
在第6版中,George F Luger阐述了复杂问题求解结构和策略的所有这些层次的理论,同时,他还指出了智能研究本身的令人兴奋之处,演示了怎样使用不同的软件工具和技术去解决计算机科学家面临的复杂问题。
这本畅销教材的主要特点是:
彻底和全面阐述人工智能的基础理论。
有效结合了求解智能问题的数据结构以及实现的算法。
用LISP、Prolog或Java语言编写实例程序。
把人工智能的应用程序应用于实际环境中。
从社会和哲学角度出发对人工智能进行全面的讨论。
与第5版相比,第6版主要扩充了获取人工智能的随机方法的相关材料,包括:
修改93节、加入第13章来介绍基于概率的机器学习。
扩充了关于有限状态自动机和概率接受器以及动态规划的使用,尤其是使用随机测量的动态规划算法(Viterbi算法)的例子。
此外,第6版除了介绍Prolog和LISP,还收集了一些用Java实现的人工智能算法。
本书共16章。第1章(第一部分)简单介绍人工智能;第2、3、4、5、6章(第二部分)介绍AI问题求解的研究工具;第7、8、9章(第三部分)介绍人工智能和知识密集型问题求解以及变化和模糊情况下推理的表示法;第10、11、12、13章(第四部分)提供机器学习中问题的扩充说明;第14、15章构成本书的第五部分,第14章讨论这一领域中最早的程序,第15章介绍自然语言理解;第16章(第六部分)作为本书的结束语。
本书适合作为高等院校计算机、自动化、电子等专业本科生及研究生的人工智能教材。同时,本书也是人工智能领域的研究者或那些想了解和应用当前人工智能技术的工作人员的一本宝贵的参考资料。
本书第6版的翻译工作由郭茂祖主持,郭茂祖审校了全部译稿,玄萍负责校对。其中,郭茂祖翻译了第1、2、3、4、5章,刘扬翻译了第7、8、9、10章,玄萍翻译了第11、12、13、14章,王春宇翻译了第6、15、16章。在本书的翻译过程中,李建伏、邓超、邹权、于建涛、王峻、李艳娟、吴伟宁、徐磊、艾淼、邢志安给予了很多帮助,对他们表示由衷的感谢。另外,本书的翻译参考了第5版的中文版,在此一并表示感谢。
出版者的话
译者序
前言
第一部分人工智能的历史渊源及研究范围
第1章人工智能的历史及应用
11从伊甸园到第一台电子计算机:对智能、知识和人类技能的态度
111人工智能基础的简要历史
112理性主义和经验主义学派对人工智能的影响
113形式逻辑的发展
114图灵测试
115智能的生物和社会模型:主体理论
12人工智能应用领域概述
121博弈
122自动推理和定理证明
123专家系统
124自然语言理解和语义学
125对人类表现建模
126规划和机器人学
127人工智能的语言和环境
128机器学习
129其他表示:神经网络和遗传算法
1210AI和哲学
13人工智能小结
14结语和参考文献
15习题
第二部分作为表示和搜索的人工智能
第2章谓词演算
20简介
21命题演算(选读)
211符号和语句
212命题演算的语义
22谓词演算
221谓词的语法和语句
222谓词演算的语义
223语义含义的积木世界例子
23使用推理规则产生谓词演算表达式
231推理规则
232合一算法
233合一的例子
24应用:一个基于逻辑的财务顾问
25结语和参考文献
26习题
第3章状态空间搜索的结构和策略
30简介
31状态空间搜索的结构
311图论(选读)
312有限状态自动机(选读)
313问题的状态空间表示
32用于状态空间搜索的策略
321数据驱动搜索和目标驱动搜索
322图搜索的实现
323深度优先搜索和宽度优先搜索
324迭代加深的深度优先搜索
33利用状态空间来表示命题演算和谓词演算的推理
331逻辑系统的状态空间描述
332与或图
333进一步的例子和应用
34结语和参考文献
35习题
第4章启发式搜索
40简介
41爬山法和动态规划法
411爬山
412动态规划
42最佳优先搜索算法
421实现最佳优先搜索
422实现启发评估函数
423启发式搜索和专家系统
43可采纳性、单调性和信息度
431可采纳性度量
432单调性
433信息度更高的启发是更好的启发
44在博弈中使用启发
441在可穷举搜索图上的极小极大过程
442固定层深的极小极大过程
443αβ过程
45复杂度问题
46结语和参考文献
47习题
第5章随机方法
50简介
51计数基础(选读)
511加法和乘法规则
512排列与组合
52概率论基础
521样本空间、概率和独立性
522概率推理:一个道路/交通例子
523随机变量
524条件概率
53贝叶斯定理
54随机方法学的应用
541“tomato”是如何发音的
542道路/交通例子的扩展
55结语和参考文献
56习题
第6章为状态空间搜索建立控制算法
60简介
61基于递归的搜索(选读)
611递归
612一个递归搜索的例子:模式驱动推理
62产生式系统
621定义和历史
622产生式系统的例子
623产生式系统中的搜索控制
624AI产生式系统的优点
63用于问题求解的黑板结构
64结语和参考文献
65习题
第三部分捕获智能:AI中的挑战
第7章知识表示
70知识表示问题
71AI表示模式的简要历史
711语义关联理论
712语义网的早期研究
713网络关系的标准化
714脚本
715框架
72概念图:网络语言
721概念图简介
722类型、个体和名字
723类型层次
724泛化和特化
725命题结点
726概念图和逻辑
73其他表示方法和本体
731Brooks的包容结构
732Copycat结构
733多种表示、本体和知识服务
74基于主体的和分布式的问题求解方法
741基于主体的定义
742基于主体的应用
75结语和参考文献
76习题
第8章求解问题的强方法
80简介
81专家系统技术概览
811基于规则的专家系统设计
812问题选择和知识工程的步骤
813概念模型及其在知识获取中的作用
82基于规则的专家系统
821产生式系统和目标驱动问题求解
822目标驱动推理中的解释和透明性
823利用产生式系统进行数据驱动推理
824专家系统的启发和控制
83基于模型系统、基于案例系统和混合系统
831基于模型推理简介
832基于模型推理:来自NASA的例子
833基于案例推理介绍
834混合设计:强方法系统的优势和不足
84规划
841规划简介:机器人学
842使用规划宏:STRIPS
843teleoreactive规划
844规划:来自NASA的例子
85结语和参考文献
86习题
第9章不确定条件下的推理
90简介
91基于逻辑的反绎推理
911非单调推理逻辑
912真值维护系统
913基于最小模型的逻辑
914集合覆盖和基于逻辑的反绎
92反绎:逻辑之外的办法
921Stanford确信度代数
922模糊集推理
923DempsterShafer证据理论
93处理不确定性的随机方法
931有向图模型:贝叶斯信念网络
932有向图模型:d-可分
933有向图模型:一个推理算法
934有向图模型:动态贝叶斯网络
935马尔可夫模型:离散马尔可夫过程
936马尔可夫模型:变形
937BBN概率建模的一阶替代方案
94结语和参考文献
95习题
第四部分机器学习
第10章基于符号的机器学习
100简介
101基于符号学习的框架
102变形空间搜索
1021泛化操作符和概念空间
1022候选解排除算法
1023LEX:启发式归纳搜索
1024评估候选解排除算法
103ID3决策树归纳算法
1031自顶向下决策树归纳
1032测试选择的信息论方法
1033评价ID3
1034决策树数据问题:打包、推进
104归纳偏置和学习能力
1041归纳偏置
1042可学习性理论
105知识和学习
1051MetaDENDRAL
1052基于解释的学习
1053EBL和知识层学习
1054类比推理
106无监督学习
1061发现和无监督学习
1062概念聚类
1063COBWEB和分类知识的结构
107强化学习
1071强化学习的组成部分
1072一个例子:九宫游戏
1073强化学习的推理算法和应用
108结语和参考文献
109习题
第11章机器学习:连接机制
110简介
111连接网络的基础
112感知机学习
1121感知机训练算法
1122例子:用感知机网络进行分类
1123通用delta规则
113反传学习
1131反传算法的起源
1132反传算法实例1:NETtalk
1133反传算法实例2:异或
114竞争学习
1141对于分类的“胜者全拿”学习
1142学习原型的Kohonen网络
1143outstar网络和逆传
1144支持向量机
115Hebbian一致性学习
1151概述
1152无监督Hebbian学习的例子
1153有监督Hebbian学习
1154联想记忆和线性联想器
116吸引子网络或“记忆”
1161概述
1162双向联想记忆
1163BAM处理的例子
1164自相关记忆和Hopfield网络
117结语和参考文献
118习题
第12章机器学习:遗传性和涌现性
120社会性和涌现性的学习模型
121遗传算法
1211两个例子:CNF可满足性问题和巡回推销员问题
1212遗传算法的评估
122分类器系统和遗传程序设计
1221分类器系统
1222用遗传算子进行程序设计
123人工生命和基于社会的学习
1231生命游戏
1232进化规划
1233涌现的实例研究
124结语和参考文献
125习题
第13章机器学习:概率理论
130学习中的随机模型和动态模型
131隐马尔可夫模型(HMM)
1311隐马尔可夫模型的介绍和定义
1312隐马尔可夫模型的重要变形
1313使用HMM和Viterbi解码音素串
132动态贝叶斯网络和学习
1321动态贝叶斯网络
1322学习贝叶斯网络
1323期望最大化:一个例子
133强化学习的随机扩展
1331马尔可夫决策过程
1332部分可观测的马尔可夫决策过程
1333马尔可夫决策过程实现的例子
134结语和参考文献
135习题
第五部分人工智能问题求解的高级课题
第14章自动推理
140定理证明中的弱方法
141通用问题求解器和差别表
142归结定理证明
1421概述
1422为归结反驳生成子句形式
1423二元归结证明过程
1424归结策略和简化技术
1425从归结反驳中抽取解答
143Prolog和自动推理
1431概述
1432逻辑程序设计和Prolog
144自动推理进一步的问题
1441弱方法求解的统一表示法
1442可选推理规则
1443归结反驳支持下的问答机制
1444搜索策略及其使用
145结语和参考文献
146习题
第15章自然语言理解
150自然语言理解问题
151解构语言:分析
152语法
1521使用上下文无关文法说明和解析
1522Earley解析器:动态规划二次访问
153转移网络解析器及语义学
1531转移网络解析器
1532乔姆斯基层次和上下文相关文法
1533ATN解析器的语义
1534结合句法和语义知识的ATN
154语言理解的随机工具
1541概述:语言分析中的统计技术
1542马尔可夫模型方法
1543决策树方法
1544解析的概率方法
1545概率上下文无关解析器
155自然语言应用
1551故事理解和问题解答
1552数据库前端
1553Web信息抽取和摘要系统
1554用学习算法来泛化抽取的信息
156结语和参考文献
157习题
第六部分后记
第16章人工智能是经验式的学科
160简介
161人工智能:修订的定义
1611人工智能和物理符号系统假设
1612连接或者“神经”计算
1613主体、涌现和智能
1614概率模型和随机技术
162智能系统科学
1621心理学约束
1622认识论问题
163人工智能:当前的挑战和未来的方向
164结语和参考文献