本书主要阐述人工智能问题求解方法的一般性原理和基本思想。主要内容有:一般的搜索问题包括盲目搜索和启发式搜索等;与或图搜索,包括AO算法和博亦树搜索等;谓词逻辑以及基于归结的定理证明方法;知识表示,包括产生式方法、语义网络、框架等;不确定性推理方法,包括贝叶斯方法、证据理论和确定性方法等;机器学习,包括实例学习、解释学习、决策树学习和神经网络等;高级搜索,包括局部搜索方法、模拟退火方法和遗传算法等。
本书可作为计算机专业的本科生或者研究生学习人工智能基础课程的教材或参考书。
人工智能自从1956年问世以来,已经经历了近50年的风风雨雨,其发展并非一帆风顺,历经几次大起大落。也正是在这样的起落中,人工智能这门学科得以逐步发展壮大起来。
实际上,从古代开始,人类就一直幻想着制造出具有智能的机器。很多古代的传说,无不体现了这样的思想。但是,只有在计算机出现以后,借助于计算机这种工具,人工智能才有可能从幻想走向现实。
究竟什么是人工智能?人工智能是否能够实现?一直是人们争议的问题。由于对智能本身研究得不够充分,人们往往将智能神秘化。当IBM的“深蓝”第一次战胜国际象棋世界冠军卡斯帕罗夫的时候,先是惊叹人工智能的发展,继而,当对“深蓝”的原理有所了解之后,又有很多人提出这样的疑问:这就是智能吗?人类下棋可不是这样的。
机器智能是对人类智能的一种模仿,是功能上的模仿,而不是机理上的模仿。由于对人类智能的了解还远远不够,因此,从机理上模仿人类的智能,至少在近期内是不可能实现的,而且即使实现也不一定就是成功的。当年莱特兄弟成功地制造了飞机,正是因为他们没有模仿鸟的飞行,他们制造的飞机不是像鸟那样依靠翅膀的煽动而飞行,才取得了成功。可以想象,如果当时人们制造的是翅膀可以煽动的飞机的话,也许到现在飞机也不能成为一种常用的交通工具。因此,在研究人工智能的过程中,不必追求其机理是否与人类一致,所追求的应该是人工智能的功能。
通俗地讲,人工智能就是一些方法,依靠这些方法,计算机可以比较好地求解问题,能够帮助人类做许多以前需要人类的智能才能完成的工作。
人工智能发展至今,已经形成了一整套的理论和方法,这些理论和方法已经在专家系统、自然语言处理、模式识别、人机交互、智能信息处理、信息检索、图像处理、数据挖掘和机器人技术等各个人工智能的应用领域发挥着巨大的作用。
目前,人工智能仍处于发展时期,很多问题解决得还不够好,甚至不能求解;很多问题的求解还需要一定的条件。人工智能毕竟是依靠机器实现的。与人类相比,机器相对呆板、不够灵活。因此,人工智能应该是一个人机协调的系统。为了机器处理的方便,人类应该做一些让步,为机器提供一定的条件,以便机器发挥其优势。就像火车一样,火车拉得多,跑得快,但火车离不开铁路,一旦离开了铁路,火车将一事无成。修建铁路就是人类对火车的让步。人工智能的应用,也许同样需要人类修建一条能让人工智能在其上面“跑”的“铁路”。
人工智能是多学科的交叉学科,涉及的内容广泛,而且一直在不断地发展,随时都在产生新的方法和理论。本书作为人工智能入门性的教材,主要介绍人工智能研究中最基本的、最经典的理论和方法,为计算机科学和技术人员以及其他学科领域中对人工智能感兴趣的科技工作者和学生提供最基本的人工智能技术和有关问题的入门知识。
前言人工智能全书共8章,第1至第7章每一章介绍人工智能的一种方法。
第0章绪论,首先介绍什么是人工智能,并阐述了图灵测试和中文屋子问题。这些问题的阐述将有助于理解什么是人工智能问题。然后介绍人工智能的研究目标、发展历史,以及人工智能所涉及的研究课题。这将有助于理解哪些问题属于人工智能领域。
第1章介绍搜索问题。搜索被认为是人工智能,尤其是传统的人工智能的两大支柱之一,很多人工智能问题的求解,最终都可以归结为搜索问题,或者与搜索问题有联系。本章主要介绍盲目搜索算法和启发式搜索算法,给出算法的描述和应用举例。
第2章介绍与或图的搜索问题,给出与或图的启发式搜索算法——AO*搜索算法和博弈树搜索算法——α|β剪支算法。α|β剪支算法是求解博弈问题最主要的算法。
第3章介绍一阶谓词逻辑及归结原理。一阶谓词逻辑是知识表示的方法之一,具有很好的数学基础。本章从命题逻辑入手,着重讨论逻辑运算在人工智能推理方法中的意义、谓词逻辑表示方法、归结原理推理方法及其理论基础。
第4章介绍知识表示方法。知识表示是支撑人工智能的两大支柱之一。人工智能问题的求解离不开知识,首先遇到的就是知识表示问题。本章主要介绍人工智能中最常用的产生式、语义网络和框架等知识表示方法及基于这些知识表示方法的推理方法。
第5章介绍不确定性推理方法。现实世界的问题,往往包含大量模糊性、随机性、不可靠性或不知道等不确定性因素,因此不确定性也是人工智能问题的主要特征之一。本章主要介绍人工智能中用于求解不确定性问题的推理方法,包括贝叶斯网络、主观贝叶斯方法、确定性方法和证据理论等。
第6章介绍机器学习方法。学习是人类最重要的能力,通过学习,人们可以解决过去不能解决的问题。因此机器学习在人工智能中起着举足轻重的作用。本章主要介绍机器学习的基本思想和基于实例的学习、基于解释的学习、决策树学习、人工神经网络学习等具体的机器学习方法。
第7章介绍高级搜索方法。高级搜索是近年发展起来的搜索方法,其特点是通过引入随机因素,把寻求最优解降低为求解满意解,从而达到降低算法复杂度的目的。本章主要介绍局部搜索方法、模拟退火算法和遗传算法。
学习人工智能,掌握方法固然重要,但更重要的是应用这些方法解决实际问题。这就涉及编程实现问题。与一般的程序设计相比,人工智能程序设计具有其特殊性。本书并不涉及人工智能程序设计问题,但并不是说这部分内容不重要。在学习本书的同时,一定要边学习边编程实现,通过程序的实现,进一步理解算法,了解算法是如何解决实际问题的。这一点在人工智能学习中是至关重要的。
本书每一章后面都附有习题,有些习题比较简单,有些习题是探讨性的,并没有“标准答案”。解答习题对于学习者来说,同样是重要的环节。
本书在写作过程中,参考了大量的国内外文献资料,在此一并表示感谢。
对于本书中出现的缺点和错误,欢迎读者给予批评指正。
第0章绪论10.1什么是人工智能1
0.2图灵测试2
0.3中文屋子问题4
0.4人工智能的研究目标5
0.5人工智能发展简史6
0.6人工智能研究的课题9第1章搜索问题141.1回溯策略15
1.2图搜索策略21
1.3无信息图搜索过程23
1.4启发式图搜索过程25
1.5搜索算法讨论50
习题55第2章与或图搜索问题572.1与或图的搜索57
2.2与或图的启发式搜索算法AO*60
2.3博弈树的搜索64
习题75第3章谓词逻辑与归结原理773.1命题逻辑77
3.1.1命题77
3.1.2命题公式78
3.1.3命题逻辑的意义82
3.1.4命题逻辑的推理规则83
3.1.5命题逻辑的归结方法85
3.2谓词逻辑基础88
3.2.1谓词基本概念88
3.2.2一阶谓词逻辑90
3.2.3谓词演算与推理93
3.2.4谓词知识表示95
目录人工智能3.3谓词逻辑归结原理98
3.3.1归结原理概述98
3.3.2Skolem 标准型99
3.3.3子句集101
3.3.4置换与合一103
3.3.5归结式106
3.3.6归结过程107
3.3.7归结过程控制策略109
3.4Herbrand定理113
3.4.1概述113
3.4.2H域114
3.4.3H解释117
3.4.4语义树与Herbrand定理118
3.4.5Herbrand定理120
3.4.6Herbrand定理与归结法的完备性121
习题122第4章知识表示1254.1概述125
4.1.1知识126
4.1.2知识表示128
4.1.3知识表示观130
4.2产生式表示131
4.2.1事实与规则的表示131
4.2.2产生式系统的结构133
4.2.3产生式系统的推理134
4.2.4产生式表示的特点138
4.3语义网络表示139
4.3.1语义网络的结构139
4.3.2基本的语义关系140
4.3.3语义网络的推理144
4.3.4语义网络表示法的特点147
4.4框架表示148
4.4.1框架结构148
4.4.2框架表示下的推理151
4.4.3框架表示法的特点152
4.5其他表示方法153
4.5.1脚本知识表示方法153
4.5.2过程性知识表示法155
4.5.3直接性知识表示方法156
习题157第5章不确定性推理方法1595.1概述159
5.1.1不确定性159
5.1.2不确定性推理的基本问题161
5.1.3不确定性推理方法的分类163
5.2概率论基础163
5.2.1随机事件164
5.2.2事件的概率166
5.2.3贝叶斯定理169
5.2.4信任几率170
5.3贝叶斯网络171
5.3.1贝叶斯网络基本概念171
5.3.2贝叶斯网络的推理模式178
5.4主观贝叶斯方法181
5.4.1规则的不确定性181
5.4.2证据的不确定性184
5.4.3推理计算185
5.5确定性方法189
5.5.1规则的不确定性度量191
5.5.2证据的不确定性度量192
5.5.3不确定性的传播与更新193
5.5.4问题195
5.6证据理论(D\|S theory)196
5.6.1基本概念196
5.6.2证据的不确定性198
5.6.3规则的不确定性200
5.6.4推理计算200
习题202第6章机器学习2056.1概述205
6.1.1机器学习的基本概念206
6.1.2机器学习研究的意义207
6.1.3机器学习发展历史209
6.1.4机器学习分类210
6.2机器学习的基本系统结构214
6.2.1环境215
6.2.2知识库215
6.2.3学习环节216
6.2.4执行环节216
6.3实例学习216
6.3.1实例学习的基本概念217
6.3.2实例学习方法的分类223
6.3.3变型空间法225
6.4解释学习230
6.4.1解释学习的基本概念230
6.4.2解释学习方法233
6.5决策树学习237
6.5.1概述237
6.5.2ID3算法241
6.6神经网络学习245
6.6.1神经网络基础245
6.6.2前馈型人工神经网络253
6.6.3自组织竞争人工神经网络260
6.6.4人工神经网络的应用264
习题268第7章高级搜索2707.1基本概念270
7.1.1组合优化问题270
7.1.2邻域272
7.2局部搜索算法274
7.3模拟退火算法280
7.3.1固体退火过程280
7.3.2模拟退火算法284
7.3.3参数的确定288
7.3.4应用举例——旅行商问题296
7.4遗传算法300
7.4.1生物进化与遗传算法300
7.4.2遗传算法的实现问题308
习题322参考文献323