本书较全面地介绍了人工智能领域的各种课题,其中包括使用神经网络和遗传算法的感知和适应性、附有本体论的智能agent、自动推理、自然语言分析,以及机器学习的随机途径。论述的许多技术和策略可用于应对现今计算机科学面临的众多挑战。此外,本书进一步由哲学、心理学和神经生理学等角度讨论了人工智能研究工作。
本书可用作大学本科生和研究生教材,还可供从事人工智能研究和应用的专业人员参考。
人工智能
刘凤岐 编著
本书主要内容
本书全面阐述了人工智能的基础理论,内容包括导论、表示与搜索导引、谓词演算、状态空间搜索、启发式搜索、状态空间搜索的控制算法、知识表示、知识系统、不确定推理、基于符号的机器学习、神经网络、学习的遗传与浮现模型、自动推理、自然语言理解等。本书有效结合了求解智能问题的数据结构及实现的算法,把人工智能应用于实际环境中,通过实例和视图,清晰、准确地阐述人工智能领域许多难解的概念,并从社会和哲学、心理学以及神经生理学角度对人工智能进行了独特的讨论。
作者简介
刘凤岐 国防科技大学原计算机系教授,长期从事计算机应用和人工智能的教学和研究工作。自上世纪80年代中期至上世纪末一直带领学生承担国家“863”计划中关于“人工智能程序设计与环境”、“专家系统开发工具”等的研究课题,获省、部级科技进步奖六项。发表论文20余篇,并编著了《逻辑程序设计原理和方法》。1990年获国家“中青年有突出贡献专家”称号,享受政府特殊津贴。
尽管人工智能(AI)与大部分工程学科相同,必须对实际问题提出具体解决方法,在商业世界中证明自己,但我们希望探讨和理解使智力思维与活动成为可能的智能的机理。国学大师辜鸿铭先生(1857—1928)在上世纪之初就指出了“……人与动物的区别何在?就在于智能”[26],对智能给出了界定,但直到电子数字计算机诞生之后才有可能精确探讨智能的属性。若对智能有了深入开发和探讨,将使我们关于世界的知识走向更高水准。我们相信由设计与评价智能人造物能有效研究可能智能的空间。本书将拒绝“智能是人类独有的能力”这一稍显狭隘的观念。
上世纪末期,AI界在“干净派”与“邋遢派”间曾发生过激烈争论,前者强调智能形式理论的详细阐述与分析;后者相信智能本身是某类大构架,可很好地按应用驱动的特定方式逼近。尽管两派间的争论已引申出许多其他争论,包括物理符号系统的支持者与神经网络的研究者,逻辑学家与多半按非逻辑方式发展出的人工生命形式的设计者,专家系统的设计者与基于事例的推理器的研究者,最后是相信AI已达到的人与相信AI绝不会发生的人,但已证明这种两分法过分简单。应该客观地看到,这些争论对AI的发展起到了积极推动作用,促进了AI研究人员对智能属性的深思,扩展了AI的研究范围。
智能用任何单一理论描述都太复杂,研究人员们已构造一理论层次,在多层抽象上表征智能。在该层次的最低层上,神经网络、遗传算法和其他形式的浮现计算使我们能理解适应、感知、体现,以及与物理世界交互的过程,这些必须是任何形式的智力活动的基础。工作在更高层上的逻辑学家们在亚里士多德开创的更强调理性的逻辑推断模式基础上,已探索出演绎、反绎、归纳、真值维护和无数其他推理模式与方式的轮廓。在进一步的更高抽象层上,诊断系统、智能agent和自然语言理解程序的设计者们已逐渐认识到社会进程在建立、传播和延续知识中的作用。
人工智能是一门边缘科学,要涉及哲学、心理学、社会学、神经生理学等领域。可以认为形式主义(或唯理主义)和经验主义支配了AI的先前发展,但近年来的研究已浮现出智能体系的激发兴趣的图像。
在AI事业中,唯理主义和经验主义极端似乎只导致了有限结果,两极端经受了有限的适用性和普遍性。本书将兼顾经验主义的修整(语义网、脚本、包容体系)与唯理主义的清晰、明确的观念(谓词演算、非单调逻辑、自动推理),并且给出基于贝叶斯的另一观点。关系不变性(规律性)的体验制约智能agent的期望,并且学习这些规律性,这本身又有偏向未来的期望。哲学家们有责任评论AI事业认识论的有效性。在本书第15章将讨论唯理主义的设想、经验主义的困境,并且介绍基于贝叶斯的构造主义和谐状态。本书中将涉及当前AI事业中的所有这些层面。
本书的一宗旨是,在AI方法学中高级表示形式体系和搜索技术的中心地位。这恐怕是本书和AI的许多早期工作的最有争议的方面,在浮现计算中的许多研究人员质疑是否符号推理和指称语义在智能中全然有任何作用。虽然表示作为对事物给出名称的思想已受到由神经网络或人工生命的浮现模式提供的隐式表示的挑战,但我们相信理解表示和搜索对任何严肃的人工智能实践者仍是实质的。我们还认为第1章中对AI历史传统和先驱者们的综述是AI教育的关键部分。此外,这些对分析像神经网络的表达能力或穿过遗传算法的适合度情况的候选问题解的进展之类的非符号AI方面是无法估价的工具。在第15章中将给出对现代AI的比较和评论。
本书的另一宗旨是把人工智能安排在实验科学、经验学科范围中。按Newell和Simon图灵奖演说的精神[16],我们引用:
……AI不是对科学传统的某种离奇的偏离,而是关于智能本身的知识,以及理解智能的一般探讨的一部分。此外,我们的AI程序设计工具,与探索式程序设计方法学一起……对探索一环境是理想的。我们的工具为理解与质疑给出了一种手段。我们构造性地达到评价与认识若干现象,即由逐步逼近。
于是我们把每种设计与程序都视为与大自然的一种实验:我们提出一种表示,产生一种搜索算法,并且询问我们对部分智力现象的解释的刻画的适宜性。而自然界对我们的询问给出响应。我们的实验可以解构、修正、扩展,并且再运行。我们的模型可以精炼,我们的理解可以扩展。
下面给出本书各章及附录的内容概要。
第1章由试图按哲学、心理学及其他研究领域理解智能的简史开始。按一种重要意义,AI是一门老科学,其根源至少可追溯到亚里士多德。对该背景的正确评价对理解现代研究致力的问题是实质的。本章还给出AI中某些重要应用领域的综述。本章的目标是为以后的理论和应用提供背景和动机。
第2章中简要介绍作为表示与搜索的AI,试图使读者对AI的该重要研究途径有某些直觉,并且介绍AI研究的初衷。第3章介绍既作为数学系统也作为描述问题实质特征的表示语言的谓词演算。第4章介绍搜索,以及用于实现搜索的算法和数据结构,组织对问题状况的探索。第5章讨论启发式在聚焦和约束基于搜索的问题求解中的实质作用。第6章介绍实现这些搜索算法的若干软件体系,包括黑板和产生式系统。
第7章介绍AI表示模式的发展历史。将由讨论基于联想的网络开始,并且将该模型扩展到包括概念相依理论、框架与脚本。而后深入审查一具体形式体系,即概念图,强调在表示知识中涉及的认识论问题,并且说明在现代表示语言中如何致力于这些问题。在第14章中将重述该形式体系,说明概念图如何用于实现自然语言数据库前端。第7章最后介绍表示的更现代途径,包括面向agent的体系。
第8章介绍基于规则的专家系统,以及基于事例和基于模型的推理,包括NASA空间计划的例子。问题求解的这些途径可描述为第2、3、4、5、6章内容的自然发展:使用对谓词演算表达式的产生式系统与图搜索适当结合。本章将由分析知识密集型问题求解的各途径的力量和弱点结束。
第9章介绍不确定与使用不可靠信息的推理模型。将介绍贝叶斯模型、信念网络、DempsterShafer证据论、因果模型以及不确定情况中推理的肯定因数代数。本章还包含真值维护算法,由最小模型的推理,基于逻辑的反绎,以及贝叶斯信念网络的团树算法。
第10章对基于符号的学习算法给出详细审查,这是引出若干不同问题和求解方法的富有成效的研究领域。这些学习算法按它们的目标、考虑的训练数据、它们的学习策略以及它们使用的知识表示变化。基于符号的学习包括归纳、概念学习、版本空间搜索和ID3。研究了归纳偏向的作用,由数据模式的普遍化,以及在基于解释的学习中有效使用知识由一个实例学习。范畴学习或概念聚类是按无监督的学习介绍。最后介绍增强式学习,或者把来自环境的反馈集成到做新决策的策略中。
第11章介绍神经网络,它常称为学习的亚符号或连接主义模型。在神经网络中信息隐含在对一组连接的处理器的组织和加权中,而学习涉及反复排列与修改全部加权的节点和系统的结构。将介绍若干连接主义体系,包括感知器学习、反向传播和逆传播;将说明Kohonen、Grossberg和Hebb模型;最后介绍结合学习与吸引区模型,包括Hopfield网络的例子。
遗传算法与学习的进化途径在第12章中介绍。按此观点可把学习视为浮现与适应过程。在根据遗传算法求解问题的几个例子之后,将介绍遗传技术在更一般问题求解器中的应用,包括分类器系统和遗传程序设计。而后将由人工生命研究的例子描述基于社会的学习。最后介绍浮现计算专题研究的例子。
定理证明常认为是自动推理,是AI研究的最老领域之一。第13章将讨论该领域中最早的程序,包括逻辑理论家和通用问题求解器。本章的主要焦点是二元归结证明程序,特别是归结反驳。最后,把PROLOG解释器描述为Horn短句与基于归结的推理系统,并且视PROLOG的计算为逻辑程序设计范型的一实例。
第14章介绍自然语言理解。语言理解的传统途径已由第7章介绍的许多语义结构的例子说明,本章将用随机途径补充。这些包括使用Markov模型、相互信息聚类和基于统计的语法分析。最后介绍应用自然语言技术产生数据库查询与原文摘要系统的例子。
第15章致力于智能系统科学的可能性问题,研究对AI的当代挑战,讨论AI的当前限制,以及激发未来的研究课题。
在附录A中介绍随机方法学,这是在不确定情况中推理的重要技术。在附录B中描述机器学习的随机途径。我们由定义隐式Markov模型(HMM)开始,而后介绍几种重要变形,包括自回归和层次HMM。其次介绍动态贝叶斯网络,这是HMM的推广,能跨越时间周期追踪系统。这些技术对模拟复杂环境中的变化是有益的,对诊断和预测推理是需要的。最后在增强式学习中加入概率成分,其中包括描述Markov决策过程和部分可观察Markov决策过程。
请读者不要忽视两附录的内容,随机技术已日益增大了对AI的影响,特别是在诊断和预测推理、自然语言分析、机器人学和机器学习之类的领域中。为支持这些出现的技术,我们较详细地介绍了贝叶斯定理、Markov模型、贝叶斯信念网络以及相关的图模型。我们还介绍了极多使用的概率有限状态机和隐式Markov模型。
我们假定读者们已学习过“离散数学”课程,其中包括谓词演算、集合论、计数和图论。还假定读者有“数据结构”基础,其中包括使用栈、队列和优先排队的树、图和基于递归的搜索。
编写本书的基本参考资料是GFLuger的著作,特别是反映人工智能近期进展的内容。本书中的参考文献并不完善,更详细的参考文献可查阅基本参考资料。由于本书追求的目标是尽量向读者展示人工智能的最新进展,对许多新内容笔者理解得不一定深刻,所以错误之处难免,恳请读者们批评指正。
使用本书
人工智能是一门大前沿科学领域,因此是一门大课程。本书可分为两部分:第一部分,第1~9章,可称为“人工智能导论”;第二部分,第10~15章,可称为“高级人工智能”。
本书应作为计算机专业本科生两学期的教材,共需120学时。学时安排如下。
第1章:10学时。 第2章:2学时。 第3章:4学时。
第4章:6学时。 第5章:6学时。 第6章:4学时。
第7章:8学时。 第8章:8学时。 第9章:8学时。
第10章:10学时。 第11章:8学时。 第12章:8学时。
第13章:8学时。 第14章:10学时。第15章:10学时。
此外,可根据学生的概率论基础情况,在第9章前适当插入附录A,4学时。在第12章之后可补充附录B,6学时,以介绍机器学习的概率途径。若学生缺乏谓词演算、图论和数据结构的基础知识,教师应对第3章、第4章和第5章花费更多时间。
刘凤岐
2011年4月
计算机科学及应用
本书主要内容
本书全面阐述了人工智能的基础理论,内容包括导论、表示与搜索导引、谓词演算、状态空间搜索、启发式搜索、状态空间搜索的控制算法、知识表示、知识系统、不确定推理、基于符号的机器学习、神经网络、学习的遗传与浮现模型、自动推理、自然语言理解等。本书有效结合了求解智能问题的数据结构及实现的算法,把人工智能应用与实际环境中,通过实例和视图,清晰、准确地阐述人工智能领域许多难解的概念,并从社会和哲学、心理学以及神经心理学角度对人工智能进行了独特的讨论。
作者简介
刘凤岐 国防科技大学原计算机系教授,从事计算机应用和人工智能的教学和研究工作。自上世纪80年代中期至上世纪末一直带领学生承担国家“863”高技术规划关于“人工智能程序设计与环境”、“专家系统开发工具”等的研究课题,获省、部级科技进步奖六项。发表论文20余篇,并编著《逻辑程序设计原理和方法》。1990年获国家“中青年有突出贡献专家”称号,享受“政府特殊津贴”。
近20年里,计算机学科有了很大的发展,人们普遍认为,“计算机科学”这个名字已经难以涵盖该学科的内容,因此,改称其为计算学科(Computing Discipline)。在我国本科教育中,1996年以前曾经有计算机软件专业和计算机及应用专业,之后被合并为计算机科学与技术专业。2004年以来,教育部计算机科学与技术专业教学指导分委员会根据我国计算机专业教育和计算学科的现状,为更好地满足社会对计算机专业人才的需求,发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范(试行)》(以下简称《规范》),提出在计算机科学与技术专业名称之下,构建计算机科学、计算机工程、软件工程和信息技术四大专业方向。《规范》中四大专业方向的分类,在于鼓励办学单位根据自己的情况设定不同的培养方案,以培养更具针对性和特色的计算机专业人才。
为配合《规范》的实施,落实中央“提高高等教育质量”的精神,我们规划了“面向计算机科学与技术专业规范系列教材”。本系列教材面向全新的计算学科,针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写,在知识选择、内容组织和教学方法等方面满足《规范》的要求,并与国际接轨。本套教材具有以下几个特点:
(1) 体现《规范》的基本思想,满足其课程要求。为使教材符合我国高等院校的教学实际,编委会根据《规范》的要求规划本套教材,广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。
(2) 围绕“提高教育质量”的宗旨开发教材。为了确保“精品”,本系列教材的出版不走盲目扩大的路子,每本教材的选题都将由编委会集体论证,并由一名编委担任责任编委,最大程度地保证这套教材的编写水准和出版质量。
(3) 教材内容的组织科学、合理,体系得当。本套教材的编写注重研究学科的新发展和新成果,能够根据不同类型人才培养需求,合理地进行内容取舍、组织和叙述,还精心设计了配套的实验体系和练习体系。
(4) 教材风格鲜明。本套教材按4个专业方向统一规划,分批组织,陆续出版。教材的编写体现了现代教育理念,探讨先进的教学方法。
(5) 开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源,为教学实现多方位服务。
我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献,欢迎广大读者广为选用。
“面向计算机科学与技术专业规范系列教材”编委会
出版者的话
序言
前言
第1章导论
11人工智能的定义与基础
111何谓人工智能?
112AI基础简史
113AI与唯理主义和经验主义传统
114形式逻辑的发展
115图灵测试
116智能的生物与社会模型:agent理论
12AI应用领域概述
121博弈
122自动推理与定理证明
123专家系统
124自然语言理解
125模拟人的性能
126规划与机器人
127AI语言和环境
128机器学习
129神经网络与遗传算法
1210AI与哲学
13人工智能概要
练习
第2章表示与搜索导引
21表示系统
22搜索
第3章谓词演算
31命题演算
311语法
312语义
32谓词演算
321语法
322语义
33谓词演算的推断规则
331推断规则
332一致化
34应用:基于逻辑的家庭财务咨询系统
练习
第4章状态空间搜索
41状态空间搜索的结构
411图论
412有限状态机
413问题的状态空间表示
42状态空间搜索策略
421数据驱动和目标驱动的搜索
422广度优先和深度优先搜索
423逐步加深的深度优先搜索
43与/或图和逻辑推理
44应用:家庭财务咨询系统
练习
第5章启发式搜索
51爬山法和动态规划
511爬山法
512动态规划
52最好优先搜索算法
521实现最好优先搜索
522实现启发估价函数
523启发式搜索与专家系统
53可采纳性、单调性及信息度
531可采纳性
532单调性
533A*算法的比较
54搜索博弈图
541极小极大程序
542固定深度的minimax
543αβ剪枝
55计算复杂度问题
练习
第6章状态空间搜索的控制算法
61基于递归的搜索
611递归搜索
612递归搜索示例:模式驱动的推理
62产生式系统
621定义及简史
622产生式系统示例
623搜索的控制
624产生式系统的优点
63问题求解的黑板体系
练习
第7章知识表示
71AI表示研究简史
711含义的联想主义理论
712语义网络的早期工作
713网络关系的标准化
714脚本
715框架
72概念图
721概念图导引
722类型、个体和名称
723类型的层次结构
724概念图的操作
725命题节点
726概念图与逻辑
73替代显式表示
731Brooks的包容体系
732多种表示、本体论与知识服务
74基于agent的分布式问题求解
741面向agent的问题求解:一种定义
742agent范型的示例及其存在问题
练习
第8章知识系统
81专家系统技术概述
811设计基于规则的专家系统
812问题领域的选择与知识工程过程
813概念模型及其在知识获取中的作用
82基于规则的专家系统
821产生式系统与目标驱动的问题求解
822目标驱动的推理的解释与透明性
823产生式系统与数据驱动的推理
824专家系统的启发性与控制
83基于模型、基于事例和混合系统
831基于模型的推理导引
832基于模型的推理:NASA的例子
833基于事例的推理导引
834混合设计
84规划
841STRIPS
842目的反应式规划
843规划:NASA的例子
练习
第9章不确定推理
91基于逻辑的反绎推理
911非单调推理逻辑
912真值维护系统
913基于最小模型的逻辑
914集合覆盖与基于逻辑的反绎
92反绎:替代逻辑
921肯定因数代数
922模糊推理
923Dempster和Shafer的证据论
93不确定性的随机途径
931有向图模型:贝叶斯信念网络
932有向图模型:d分隔
933有向图模型:推理算法
934有向图模型:动态贝叶斯网络
935Markov模型:离散Markov过程
936Markov模型:改型
练习
第10章基于符号的机器学习
101基于符号的学习框架
102版本空间搜索
1021一般化操作与概念空间
1022候选排除算法
1023LEX:归纳搜索启发式
1024候选排除算法的评价
103ID3决策树归纳算法
1031自顶向下归纳决策树
1032信息论的测试选择
1033评价ID3
1034决策树的数据问题
104归纳偏向与学习能力
1041归纳偏向
1042学习能力理论
105知识与学习
1051基于解释的学习
1052类比推理
106无监督的学习
1061发现与无监督的学习
1062概念聚类
1063COBWEB与分类知识的结构
107增强式学习
1071增强式学习的成分
1072示例:井字棋博弈
1073增强式学习的推理算法
练习
第11章神经网络
111神经网络基础
112感知器学习
1121感知器训练算法
1122感知器学习用于分类
1123梯度下降法与δ规则
113反向传播学习
1131反向传播算法
1132例1:NETtalk
1133例2:异或函数
114竞争学习
1141分类的WTA学习算法
1142Kohonen的学习原型网络
1143重复传播网络
115Hebb的叠合学习
1151无监督Hebb学习示例
1152有监督Hebb学习
1153结合存储与线性结合器
116吸引状态网络
1161双向结合存储
1162BAM处理示例
1163自结合存储与Hopfield网络
练习
第12章学习的遗传与浮现模型
121遗传算法
1211遗传算法示例
1212遗传算法的评价
122分类器系统与遗传程序设计
1221分类器系统
1222遗传程序设计
123人工生命和基于社会的学习
1231“生命博弈”
1232进化规划
1233浮现的专题研究
练习
第13章自动推理
131通用问题求解器
132归结定理证明器
1321谓词演算表达式化为短句集合
1322归结证明程序
1323归结策略和简化技术
1324由归结反驳抽取答案
133PROLOG与自动推理
练习
第14章自然语言理解
141理解语言的符号途径
142语法
1421上下文无关文法的规范与分析
143跃迁网分析器与语义
1431跃迁网分析器
1432Chomsky层次与上下文有关文法
1433语义:ATN分析器
1434用ATN组合语法和语义知识
144语言理解的随机工具
1441语法分析的概率途径
1442概率上下文无关分析器
145自然语言的应用
1451故事理解与回答问题
1452数据库前端
1453对Web的信息抽取和摘要系统
练习
第15章结束语:评述与展望
151对AI几种途径的评述
1511智能与物理符号系统假设
1512连接主义计算
1513agent、浮现与智能
1514概率模型和随机技术
152现代认知科学
1521心理学的约束
1522认识论问题
153AI:当前的挑战与未来方向
附录A随机方法导论
附录B随机方法的应用
参考文献