1.1 人工智能的诞生及发展
?诞生:1956年美国达特莫斯大学(Dartmouth)召开了一次影响深远的历史性会议,这次会议首次提出了“人工智能”(AI)这一术语,标志着人工智能作为一门新兴学科正式诞生。
?阿伦.图灵(A.Turing 1912~1954) 《计算机与智能》的文章,提出计算机能否思考,图灵测试
?香农(C.Shannon)计算机能够下棋的文章
?麦卡锡(M.MaCarthy)提出“人工智能”这一术语。
图灵测试:
?发展史
–50年代—游戏、博弈
–60年代—搜索方法、一般问题求解?LISP?机器定理证明?知识表示的语义网络模型
–70年代—PROLOG?专家系统?知识工程
–80年代—推理技术、知识获取、自然语言理解、机器视觉?不确定推理、非单调推理、定性推理方法–90年代以来—各种理论的实际应用,机器学习和人工神经网络。
?算术运算阶段?数学运算阶段?逻辑推理阶段?专家系统阶段?模式识别阶段?情感计算阶段?情感理解阶段
1.2 人工智能的定义
?人工智能是指用人工的方法和技术,模仿、延伸和扩展人的智能,实现机器的智能化,人工情感
指用人工的方法和技术,模仿、延伸和扩展人的
情感,使机器具有识别、理解和表达情感的能力。
?是一门知识工程学,以知识为对象,主要研究知识的获取、知识的表示方法和知识的使用(运用知
识进行推理)
?人类智能:人类所具有的智力和行为能力,这种能力是以知识为主的。智力和行为的目的是获取
知识,并运用知识去求解问题。
?人类智能的特点主要体现:
?感知能力
?记忆与思维能力
?归纳与演绎能力
?学习能力
?行为能力。
1.3 人工智能研究的方法及途径
1.3.1 人工智能研究的各种学派及其理论
?符号主义(逻辑主义,计算机学派)
–主张运用计算机科学的方法进行人工智能的研究,通过研究逻辑演绎在计算机上的实现方法、实现人
类智能在计算机上的模拟。
–认为人类智能的基本单元是符号,认知过程就是符号表示下的符号计算,从而思维就是符号计算。–原理:物理符号系统假设和有限合理性原则
?联结主义(仿生学派)
–主张用仿生学的方法进行研究,通过研究人脑的工作模型,搞清楚人类智能的本质。
–认为人类智能的基本单元是神经元,认知过程是由神经元构成的网络的信息传递,这种传递是并行颁
进行的。
–原理:神经网络及神经网络间的连接机制与学习算法。
?行为主义(进化主义)
–主张应用进货论的思想进行人工智能的研究,通过对外界事物的动态感知与交互,使计算机智能模拟
系统逐步进货,提高智能水平。
–认为人工智能起源于控制论,提出智能取决于感知和行动,取决于外界复杂环境的适应,它不需要知
识、不需要表示、不需要推理。智能行为只能在与
现实世界的环境交互作用中表现出来,人工智能也
会像人类智能一样通过逐步进货而实现。
–原理:通过控制论和机器学习算法实现智能系统的逐步进化。
1.3.2 实现人工智能的技术路线
1.专用路线
2.通用路线
3.硬件路线
4.软件路线
1.4 人工智能的研究及应用领域
①问题求解
②机器学习
③专家系统
④模式识别
⑤自动定理证明
⑥自动程序设计
⑦自然语言理解
⑧机器人学
⑨人工神经网络
⑩智能检索
?问题求解:
–研究涉及问题表示空间的研究、搜索策略的研究和归约策略的研究。代表:下棋程序。
?机器学习:
–学习:就是系统在不断重复的工作中对本身能力的增强或改进,使得系统在下一次执行同样任务
或相类似的任务时,会比现在做得更好或效率更
高。即:如果一个系统能够通过执行某种过程而
改进它的性能,这就是学习。
–机器学习则是研究怎样使用计算机模拟或实现人类学习活动的一门科学。同认知科学、逻辑学、
心理学、教育学、哲学有密切联系。
–目标:人类学习过程的认识模型、通用学习算法、构造面向任务的专用学习系统的方法。
?专家系统(Expert System)
–是一个智能的计算机程序,它运用知识和推理步骤来解决只有专家才能解决的复杂问题。即任何
解题能力达到了同领域人类专家水平的计算机
程序都可以称做专家系统。
?模式识别(PatternRecognition)
–模式:原意是提供模仿用的完美无缺的标本。
–模式识别就是识别给定的事物和哪一个标本相同或相类似
?图形和图像识别
?语音识别
?自动定理证明(Automatic Theorem Proving)
–自然演绎法:依据推理规则,从前提和公理中可以推理出许多定理,如果待证的定理恰在其中则
定理得证。
–判定法:对一类问题找出统一的计算机上可实现的算法。吴文俊1977年提出的证明初等几何定
理的算法。
–定理证明器:研究一切可判定问题的证明方法。
1965J.A.Robinson 消解原理Resolution Principle –人机交互进行定理证明:通过人机交互来证明定理。1976 K.Appel证明了四色定理。
?自动程序设计
–程序综合:用于实现自动编程
–程序正确性验证
?自然语言处理(Natural Language Processing)
–主要研究使用计算机理解和生成自然语言的基础理论和基本技术。包括书面语、口语、手写文
字识别。
?机器人(Robot)
–Gaak 2002
?人工神经网络(Artificial Neural Network)
–用大量称为人工神经元的简单处理单元经广泛连接而组成的人工网络,用来模拟人脑神经系统
的结构和功能。
?智能学习
–基于概念的检索
–数据挖掘和自然语言理解
第2章知识表示方法
知识是人类智能的基础。人工智能是一门研究用计算机来模仿和执行人脑的某些智力功能的交叉学科,所以人工智能问题的求解也是以知识为基础的。
知识的获取、知识的表示和运用知识进行推理是人工智能学科要研究的三个主要问题。
2.1概述
2.1.1 知识、信息和数据
数据是记录信息的符号,是信息的载体和表示。信息是对数据的解释,是数据的特定场合下的具体含义。数据和信息是两个不同的概念,相同的数据在不同的环境下表示不同的含义,蕴含有不同的信息。
信息是要以数据的形式来表达和传递的,数据中蕴含着信息,然而,并不是所有的数据中都蕴含着信息,而是只有那些有格式的数据才有意义。对数据中的信息的理解也是主观的、因人而异的,是以增加知识为目的的。
一般把有关信息关联在一起所形成的信息结构称为知识。
综上所述,知识、信息和数据在三个层次的概念。有格式的数据经过处理、解释过程会形成信息,而把有关的信息关联到一起,经过处理过程就形成了知识。知识是用信息表达的,信息则是用数据表达的,这种层次不仅反映了数据、信息和知识的因果产生关系,也反映了他们不同的抽象程度。人类在社会实践过程中,其主要的只能活动就是获取知识,并运用知识解决生活中遇到的各种问题。
知识是人类智能的基础,人工智能问题的求解也是以知识为基础的。知识的获取,知识的表示和运用知识进行推理是人工智能学科要研究的3 个主要问题。
1.知识、信息和数据的关系
2.1.2知识的特性
知识是人们把实践中获取的信息关联在一起所形成的信息结构。具有以下一些特性。
1.相对正确性
任何知识都是在一定环境和条件下产生的,所以知识的正确性也是在一定得前提下才能正确的。
2 不确定性
知识是有关信息关联在一起形成的信息结构,信息与关联是构成知识的两大要素。由于现实世界的复杂性,信息可能是精确地,也可又能是不精确的、模糊的;关联可能是确定的,也可能是不去定的。这就使得知识不起哦那个是只有真和假两种状态,而是在真和假之间存在有很多状态,即存在“真”的程度问题。知识的这一特性称为不确定性。
3.可表示性
知识是可以用形式化得东西表示的,比如可以用语言、文字、图形、公式等来表示知识,正是由于知识的这一特性,才能使我们将知识数据化,才能用计算机来存储知识、传播知识和利用知识。
4.可利用性
我们每时每刻都在利用我们所掌握的知识来解决现实世界种的各种问题,如果知识不具有可利用性,我们就不能积累我们的知识,世界就不会前进。
2.1.3 知识的分类
对知识从不同的角度划分,可得到不同的分类方法。(1)以知识的作用范围划分,可分为常识性知识和领域性知识。
(2)以知识的作用及表示来划分,可分为事实性知识、规则性知识、控制性知识和元知识。
事实性知识是指有关领域内的概念、事实、事物的
属性、状态及其关系的描述,包括事物的分类、属
性、事物间关系、科学事实、客观事实等。
规则性知识是指有关问题中与实务的行动、动作相
联系的因果关系知识,这种知识是动态的、变化的。
常以“如果…,则…”的形式出现。
控制性知识是指有关问题的求解步骤、技巧性知识,
告诉该怎么做一件事。也包括当有多个动作同时被
激活时,应选择哪一个动作来执行的知识。
元知识是指有关知识的知识,是知识库中的高层知
识。包括怎样使用规则、解释规则、校验规则、解
释程序结构等知识。
(3)以知识的去定性来划分,可分为确定知识和不确定知识。
(4)按照人类的思维及认识方法来分,可分为逻辑性知识和形象性知识。
2.1.4 知识的表示
知识表示是研究用机器表示知识的可行性、有效性的一般方法,是一种数据结构与控制结构的统一体,既考虑知识的存储又考虑知识的使用。
知识表示的本质:实际上就是对人类知识的一种描述,以把人类知识表示成计算机能够处理的数据结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。
按照人们从不同角度进行探索以及对问题的不同理解,知识表示方法可分为陈述性知识表示和过程性知识表示两大类。
(1)陈述性知识表示主要用来描述事实性知识。这种表示方法将告诉人们,所描述的客观事物涉及的“对象”是什么,知识表示就是将对象的有关事实“陈述”出来,并以数据的形式表示。这类表示法将知识表示与知识的运用(推理)分开处理,在表示知识时,并不涉及如何运用知识的问题,是一种静态的描述方法。
(2)过程性知识表示:主要用来描述规则性知识和控制结构知识。这种表示方法就是告诉人们“怎么做”,知识表示的形式是一个“过程”,这一“过程”就是求解程序。他将知识的表示与运用(推理)相结合,知识就寓于程序之中,是一种动态的描述方法。
2.2一阶谓词逻辑表示法
1.一阶谓词逻辑表示法:是一种重要的知识表示方法,它以数理逻辑为基础,是到目前为止能够表达人类思维活动规律的一种最精确的形式语言。
2.谓词公式:是用谓词连接符号将一些谓词连接起来所形成的公式。
知识数据
信息
2.3产生式表示法
1.知识的表示方法:
(1)确定性规则知识的产生式表示:确定性规则知识的产生式形式为:
P→Q 或者
IF P THEN Q
其中P是产生式前提,用于指出该产生式是否可用的条件;Q是一组结论或操作,用于指出前提P所指示的条件被满足时,应该得出的结论或应该执行的操作。
(2)不确定性规则知识的产生式表示:不确定性规则知识的产生式形式为:P→Q(置信度) 或者
IF P THEN Q (置信度)
2.产生式的组成
规则库、综合数据库和控制系统(推理机)。
前二者构成产生式系统的问题表示(描述)后者则控制应用规则推出解答的全过程。
(1)规则库
规则库(知识库)
描述应用领域的常识和启发式知识,产生式规则的集合,产生式系统的知识库。
a)产生式规则—表示事物间的启发式关联,”条件-动
作型规则”
b)是一个以"如果满足这个条件,就应当采取某些操
作"形式表示的语句
c)产生式一般形式:P?Q 或IF P then Q
P:产生式的IF(如果)被称为条件、前项或产生式的左边。它说明应用这条规则必须满足的条件;
Q:THEN(那么)部分被称为操作、结果、后项或产生式的
推理机
综合数据库
规则库
右边。
在产生式系统的执行过程中,如果某条规则的条件满足了,那么,这条规则就可以被应用;也就是说,系统的控制部分可以执行规则的操作部分。
产生式的两边可用谓词逻辑、符号和语言的形式,或用很复杂的过程语句来表示。这取决于所采用数据结构的类型。
(2)综合数据库
a)存放当前已知的知识信息数据,包括推理过程中形
成的中间结论知识。
b)用于存储有关问题的状态、性质等事实的叙述型知
识。
c)其数据由控制器用来激活相应的规则
d)数据可常量、多元数组、谓词、表结构等,基本含
义为事实或断言。
(3)规则解释(控制器)
根据有关问题的控制型知识,选择控制策略,将规则与事实进行匹配,控制并利用知识进行推理,求解问题。匹配器:判断规则条件是否成立
冲突解决器:选择可调用的规则
解释器:执行规则的动作,适时终止系统运行。
(1)匹配
在这一步,把当前数据库与规则的条件部分相匹配。
如果两者完全匹配,则把这条规则称为触发规则。当按规则的操作部分去执行时,称这条规则为启用规则。被触发的规则不一定总是启用规则,因为可能同时有几条规则的条件部分被满足,这就要在解决冲突步骤中来解决这个问题。在复杂的情况下,在数据库和规则的条件部分之间可能要进行近似匹配。
(2).冲突解决
当有一条以上规则的条件部分和当前数据库相匹配时,就需要决定首先使用哪一条规则,这称为冲突解决。策略:
First,Best,All
(a) 专一性排序(b) 规则排序(c) 数据排序
(d) 规模排序(e) 就近排序(f) 上下文限制
(3).操作
操作就是执行规则的操作部分,经过操作以后,当前数据库将被修改。然后,其他的规则有可能被使用。3.产生式系统的推理方式
(1)正向推理
(2)反向推理
(3)双向推理
2.4语义网络表示法语义网络:是通过概念及其语义关系来表示知识的一种网络图,它是一个带标注的有向图。其中有向图的各节点用来表示各种概念、事物、属性、情况、动作、状态等,节点上的标注用来区分各节点所表示的不同对象,每个节点可以带有若干个属性,以表征其所代表的对象的特性,弧是有方向,有标注的,方向用来体现节点间的主次关系,而其上的标注则表示被连接的两个节点间的某种语义联系或语义关系。
一个最简单的语义网络可由如下的一个三元组表示:(节点1,弧,节点2)
2.5框架表示法
1.框架理论的基本观点:是“人脑中以存储有大量事物的典型情景,也就是人们对这些事物的一种认识,这些典型情景是以一个称为框架的基本知识结构存储在记忆中的,当人面临新的情景时就从记忆中选择(粗匹配)一个合适的框架,这个框架是以前记忆的一个知识框架而其具体内容要依新的情景而改变,通过对这个框架的细节加工、修改和补充,形成对新的事物情景的认识,而这种认识的新框架又可记忆于人脑之中,以丰富人的知识。”
2.一个框架可由框架名、槽侧面和值4部分组成。
2.6状态空间表示法
1.状态空间搜索的研究焦点在于:设计高效的搜索算法,以降低搜索代价并解决组合爆炸问题。
2.传教士与野人渡河问题
问题:
3(N)个传教士与3(N)个野人渡河,有一条船,每次至多可供2(K)人乘渡。任何时刻,要求河的两岸及船上的野人数目总是不超过传教士的数目(允许在某一岸只有野人而没有传教士)
问题描述:
S g
搜索空间示意
问题全状态空间
搜索空间
解路径
状态三元组(传教士数目m ,野人数目c ,船的状况b) 初始状态:(3,3,1) 结束状态:(0,0,0) 中间状态:(2,2,0),(3,2,1),(3,0,0)…… 限制条件:m+c<=2, m>=c 问题求解任务: (3,3,1) (0,0,0) 状态空间可能状态数:4*4*2=32个 合法状态:20个(如(1,0,1),(1,2,1)) 非法状态:如(0,0,1),(0,3,0) 可达的合法状态:16个 操作算子:L(m,c),R(m,c) ● 指示从左岸到右岸的划船操作和从右岸到左岸的划船操作 ● m 和c 的可能组合有5个:10,20,11,01,02 ● 共有10个操作算子 八数码游戏 状态数:9! ( = 362,880 ) 1.状态空间及其搜索的表示(1) 状态空间以SP 指示,为一个二元组 ● SP =(S,O) ? S:在问题求解过程中所有可达的合法状态构成的集合 ? O:操作算子的集合,操作算子的执行导致状态的变迁 可描述为一有向图: ● 节点指示状态, ● 节点间的有向弧表示状态变迁, ● 弧上的标签指示导致状态变迁的操作算子。 状态空间的搜索以SE 指示,表示为1个五元组: ● SE=(S,O,E,I,G) ? E -搜索引擎 ? I -问题的初始状态 ? G -问题的目标状态 2.一般图搜索策略(1) (1)搜索术语 ● 一般图搜索:是在状态空间中搜索从初始状态到目标状态解答路径的过程。 ● 节点深度:根节点深度为0,其他节点为dn=dn-1+1 ● 路径:从节点ni 到nk 的路径由相邻节点间的弧线构成的折线,通常要求路径是无环的 ● 节点扩展: ● 路径代价: ? 路径本身代价 ? 路径搜索代价
搜索过程要点
① 从初始或目的状态出发,并将它作为当前状态 ② 扫描操作算子集,将适用于当前状态的一些操作算子作用在其上而得到新的状态,并建立指向父结点
的指针
③ 检查所生成的新状态是否满足结束状态,如果满足,
则得解,并可沿着有关指针带着向到达开始状态,
给出一解答路径;否则将这新状态作为当前状态,返回第2步再进行搜索。 搜索策略的主要任务: 确定如何选取操作算子的方式!
搜索的本质: 状态空间中,问题的求解就是搜索,搜索某个状态空间以求得操作算子序列的一个解答的过程,它也就对
应于使一个隐式图的足够大的一部分变为显式并包含目的结点的过程。 搜索的基本问题:
① 搜索过程是否一定能找到一个解
② 搜索过程是否能终止运行或者是否会陷入一个死循环 ③ 当搜索过程找到解时,找到的是否是最佳解 ④ 搜索过程的时间与空间复杂性如何
4.搜索策略 盲目搜索 ● 指在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随机调用操作算子)进行的搜索,能快速地运用一个操作算子。 ● 特点:由于没有可参考的信息,只要能匹配的操作算子都需运用,这会搜索出更多的状态,生成较大状态空间显示图。 启发式搜索 ● 是考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选取较合适的操作算
(331(310)
(320)
(321)
(300)
(311)
(221)
(020)
(031)
(010)
(011)
(111)
(000
11
02
01
01
10
02
01
20
11
20
01
02
01
02
11
10
渡河问题的状态空间图
5
7 4 6 1 3 8 2 5
6 7 4 8 3 2 1
子,尽量减少不必要的搜索,以求尽快地到达结
束状态,提高搜索效率。
特点:如具有较多甚至较完整的启发信息,虽然只须运用少量操作算子,只生成较小的状态空间
显示图,能将搜索引向一个解答,但每使用一个
操作算子便湎须做更多的计算与判
盲目搜索-广度优先搜索看图(a)
盲目搜索-深度优先搜索看图(b)
图(a)
图(b)
启发式图搜索策略
启发式知识的指导作用:
① 选择下一个要被扩展的节点,排序待施展节点是常
用的方法
② 扩展一个节点时,公仅有选择地生成部分有用的节
点,而非所有可能的子节点
③ 修剪掉某些估计不可能导致成功的子节点
评价函数:计算每个节点的得分,以便用于排列
它们在扩展节点表中的位置 f(n)=g(n)+h(n)
? n —搜索图中的某个当前被扩展的节点 ? f(n)—从初始状态节点s ,经由节点n 到达目标状
态节点ng,估计的最小路径代价
? g(n)—从s 到n ,估计的最小路径代价
? h(n)—从n 到ng ,估计的最小路径代价(启发式
函数)
? 算法的可采纳性
● 在搜索图存在从初始状态节点到目标状态节点
解答路径的情况下,若一个搜索法总能找到最短的解答路径,则称该算法具有可采纳性。 ? 回溯策略 ? 爬山法
八数码问题启发式搜索方法1
八数码问题启发式搜索方法2
2.6与或树表示法
1.问题的分解与等价变换
问题的分解是指把一个复杂的问题P 分解为若干个子问题P 1,P 2,……Pn(每个子问题又可以继续分解为若干个更为简单的字问题,直到不需要再分解或不能再分解为止)。然后对每个子问题求解,并且只有当所有子问题Pi(i=1,2,……,n)都有解时,原问题P 才有解,它的解就是所有子问题的”与”;任何一个子问题Pi 无解都会导致原问题P 无解,即分解所得到的子问题的“与”和原问题P 等价。
问题的等价变换是指对一个复杂问题P 进行同构或同态的等价变换,将其变换为若干个较为容易求解的新问题P 1,P 2,……Pn ,只要这些新问题Pi 中有一个解,则原问题P 就有解。只有当变换得到的所有问题Pi(i=1,2,……,n)都无解时,原问题P 才无解。也就是说,等价变换所得到的新问题的“或”与原问题等价。
问题归约:是人们求解问题常用的策略,就是把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。
问题归约可以递归地进行,直到把问题变换为本原问题的集合。
本原问题:就是不可或不需再通过变换化简的“原子”问题,它的解可以直接得到或通过一个“黑箱”操作得到。 例:问题归约 h(n)=错误位置的个数
103724685?? ? ? ???
130724685??
? ? ???123704685??
? ? ???013724685??
? ? ???123784605?? ? ? ???123074685?? ? ? ???123740685?? ? ? ???023174685?? ? ? ???
123674085??
? ? ???
123784065?? ? ? ???123784650?? ? ? ???
123084765?? ? ? ???
023184765??
? ? ???123804765??
? ? ???
5 6 4 6 4 4 5 5
4 3
5 2 0 3 h(n)=错误位置离其正确位置需要走行步数的和 103724685??
? ? ???
130724685??
? ? ???123704685??
? ? ???013724685??
? ? ???123784605?? ? ? ???123074685?? ? ? ???
123740685?? ? ? ???
123784065?? ? ? ???123784650?? ? ? ???
123084765?? ? ? ???
023184765??
? ? ???123804765??
? ? ???
6 8 6 8 4 6 4 6 2 0 4 6 ()()
342
3
4
2
2
2
2
2
2
2
(sin /(1))sin (/1))(1cos )cos (11/(1))cos cos cos (1/(1))x x x dx xdx x x dx
x d x x x dx
d x xd x x dx dx x dx ++=++=--+-++=-++-++?????????
问题归约的与或树表示
把一个复杂的问题归约为一组本原问题时,其归约过程可以用一个与/或树表示。
1.与树
当把一个复杂问题分解为若干个子问题时,用一个“与树”这种分解。例如,设问题P可以分解为3个子问题P1,P2,P3,即对它的求解相当于对这3个新问题的同时求解,则P和着3个新问题之间的关系可
以用图2.1表示所示的一个“与树”来表示。在这个“与树”中,用相应的节点表示P,P1,P2,P3,并用三条有向边分别将p和P1,P2,P3连接起来,它表示P1,P2,P3是p的三个子问题。图中连接三条有向边的小弧线表示P1,P2,P3之间是“与”的关系,它们是对节点p的分解,p为“与”节点。
2.或树
当把一个复杂问题变换为若干个与之等价的新问题时,可用一个“或树”来表示这种变换。例如,设问题p可以变换三个新问题P1,P2,P3中的任何一个,即它与这三个新问题中的任何一个等价,则p与它们之间的关系可用图2.2所示的一个“或树”来表示。在这个“或”树中,用相应的节点表示P1,P2,P3;并用三条有向边分别将p 和P1,P2,P3连接起来,它表示P1,P2,P3是与p等价的三个新问题。图中的有向边不用小弧线连接,它表示P1,P2,P3之间是“或”的关系,即节点p为“或”节点。3.与/或树
如果一个问题既需要通过分解,又需要通过变换才能得到其本原问题,则其求解过程可用一个”与/或树”来表示。与/或树的例子如图2.3所示。事实上,大多数实际问题都需要用与/或树来表示,即在解决大多数问题时,队员问题的分解与变换是相结合的。在与/或树中,其根本节点对应着待求解的原始问题。
4.端节点与终止接点
在与/或树中,没有子节点的节点称为端节点;本原问题所对应的节点称为终止节点。可见,终止节点一定是端节点,但端节点却不一定是终止节点。
5.可解节点与不可解节点
在与/或树中,满足以下三个条件之一的节点为可解节点:(1)该节点是一个终止节点
(2)该节点是一个“或”节点,且其子节点中至少有一个为可解节点。
(3)该节点是一个”与”节点,且其子节点全部为可解节点。
同样,满足下列条件之一的节点为不可解节点:
(1)该节点是一个端节点,但却不是终止节点。(2)该节点是一个“或”节点,但其子节点中没有一个是可解节点。
(3)该节点是“与”节点,且其子节点中至少有一个为不可解节点。
6.解树
解树是一个由可解节点构成,并且可由这些可解节点推出初始节点(它对应着原始问题)也为可解节点的子树。
P11
P1
P
P2P3
图2.3
P12P13
P31P32
P1P
P2P3
图2.1
P1
P
P2P3
图2.2
在解树中一定包含初始节点。例如,在图2.4所给出的与/或树中,用粗线表示的子树就是它的一个解树。该图中的节点p为原始问题节点,标有t的节点是终止节点。由可解节点的定义,可以容易推知原始问题P为可解节点。
图2.4
7.用与/或树表示问题的步骤
用与或树表示法表示问题的步骤如下:
(1)对所要求解的问题进行分解或等价变换。
(2)若所得的子问题不是本原问题,则继续分解或变换,直到分解或变换为本原问题。
(3)在分解或变换中,若是不等价的分解,则用“与树”表示,若是等价变换,则用“或树”表示。
8.与/或树表示举例
例2.1 三阶Hanoi塔问题。设有A、B、C三个盘子(A 比B小,B比C小)及三根柱子,三个盘子自上而下从小到大的顺序穿在1号柱子上,要求把它们全部移到3号柱子上,而且每次只能移动一个盘子,任何时刻都不能把大的盘子压在小盘子上,如图2.5所示,
图2.5
解:第一步,设用三元组
(i,j,k)
表示问题在任一时刻的状态,用“→”表示状态的转换。在上述三元组中,i代表盘子C所在的柱子号,j代表盘子B所在的柱子号,k代表盘子A所在的柱
子号。则原问题可表示为
(1,1,1)→(3,3,3)
第二部,利用归约方法,原问题可分解为以下三个子问题:
(1)把盘子A和B移到2号柱子上的双盘子问题。即(1,1,1)→(1,2,2)
(2)把盘子C移到3号柱子上的单盘子移动问题。即(1,2,2)→(3,2,2)
(3)把盘子A和B移到3号柱子上的双盘子问题。即(3,2,2)→(3,3,3)
其中,子问题(1)和(3)都是一个二阶Hanoi塔问题,它们还可以再继续进行分解;子问题(2)是本原问题,它已不需要再分解。
(1,1,1)→(1,2,2)又可分解为(1,1,1)→(1,1,3)、(1,1,3)→(1,2,3)和(1,2,3)→(1,2,2)三个本原问题;(3,2,2)→(3,3,3)又可分解为(3,2,2)→(3,2,1)、(3,2,1)→(3,3,1)和(3,3,1)→(3,3,3)三个本原问题。
第三步:根据分解与变换情况画出与/或树.如图2.6
所示。
图2.6三阶Hanoi塔的与/或树
在图2.6所示的与/或树中,有7个终止节点,它们分别对应着7个本原问题。如果把这些本原问题从左到右排列起来,即得到了原始问题的解:
(1,1,1)→(1,1,3)(1,2,2)、(1,1,3)→(1,2,3)、(1,2,3)→(1,2,2)、(1,2,2)→(3,2,2)(3,2,2)→(3,2,1)、(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)
第三章确定性推理(复习的课件内容)
?按照推理过程所用知识的确定性,推理可分为确定性推理和不确定性推理
?推理是指从已知事实出发,运用已掌握的知识,推导出其中蕴含的事实性结论或归纳出某些新
的结论的过程。
?人工智能系统的构成:
–推理机---一些程序来完成的;
–综合数据库---存放有用于推理的事
实或证据;
–知识库---存放有用于推理所必须的
知识。
?按照推理的逻辑基础分类可分为演绎推理、归纳推理和默认推理
?按照对推理方向的控制,推理可分为正向推理、反向推理、混合推理及双向推理四种情况?谓词
?表示知识
?将谓词公式化为子句集
?归结反演
(以下是老师课上说的内容。)
3.1 推理概述
1. 所谓推理,是指从已知事实出发,运用已掌握的知识,推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。
2. 推理的方法及其分类
2.1 按照推理的逻辑基础分类
可分为演绎推理(从一般→个别的推理)、归纳推理(从个别→一般的推理)和默认推理(又称缺省推理,是在知识不完全的情况下假设某些条件已经具备所进行的推理)。
2.2 按所用知识的确定性分类
按推理时所用知识的确定性来划分,推理可分为确定性推理、不确定性推理。
3. 推理的控制策略
控制策略包括推理方向、搜索策略、冲突消解策略等;而推理方法则是指在推理控制策略确定之后,在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法。
推理方向用来确定推理的驱动方式,即是数据(证据)驱动或是目标驱动。
4. 推理的冲突消解策略
推理过程中的冲突消解策略,就是确定如何从多条匹配规则中选出一条规则作为启用规则,将它用于当前的推理。
目前已有的多种冲突消解策略的基本思想都是对匹配的知识或规则进行排序,以决定匹配规则的优先级别,优先级高的规则将作为启用规则。
常用排序方法有如下几种:
(1)按就近原则排序
(2)按知识特殊性排序
(3)按上下文限制排序
(4)按知识的新鲜性排序
(5)按知识的差异性排序
(6)按领域问题的特点排序
(7)按规则的次序排序
(8)按前提条件的规模排序
3.2 命题逻辑1. 能够分辨真假的语句称作命题。
2. 命题公式(要求会应用)
2.1. 连接词
~:称为“非”或“否定”。
∨:称为“析取”。
∧:称为“合取”。
→:称为“条件”或者“蕴含”。
?:称为“双条件”。P ? Q表示“P当且仅当Q”。
2.2 以下面的递归形式给出命题公式的定义:
?(1)原子命题是命题公式。
?(2)A是命题公式,则~A也是命题公
式。
?(3)若A和B都是命题公式,则A∧B、
A∨B、
A→B、A?B也是命题公式
?(4)只有按(1)—(3)所得的公式才
是命题公式。
3.3 谓词逻辑
一个谓词可以与一个个体相关联,此种谓词称作一元谓词,它刻画了个体的性质。(poet(LiBai))
一个谓词也可以与多个个体相关联,此种谓词称为多元谓词,它刻画了个体间的“关系”。(teacher(A,B))
谓词的一般形式:
P(x1,x2,…,xn )
其中P是谓词,而x1,x2,…,xn是个体。谓词通常用大写字母表示,个体通常用小写字母表示。
项:在谓词中,个体可以是常量,也可以是变量,还可以是一个函数。
谓词的元数:谓词中包含的个体数目称为谓词的元数,例如P(x)是一元谓词,P(x,y)是二元谓词,而P(x1,x2,…,xn )则是n元谓词。
谓词的阶数:在谓词P(x1,x2,…,xn )中,若xi(i=1,2,…,n)都是个体常量、变元或函数,则称它为一阶谓词。如果某个xi本身又是一个一阶谓词,则称它为二阶谓词,依次类推。
谓词和函数的区别:谓词具有逻辑值“真”或“假”,而函数则是某个个体到另一个个体(按数学上的概念是自变量到因变量)之间的映射。
◆谓词公式表达?
1. 连接词
~,∨,∧,→,?
2. 量词
为刻画谓词与个体间的关系,引入了两个量词:全称量词(?x),和存在量词(?x)。
3. 谓词演算公式 量词否定律
量词分配律
4.量词 命题:不包含变量的谓词公式和逻辑语句。命题演算是谓词演算的子集 全称量词:对于某个论域的所有个体,都有P(x)值为T 存在量词:对于某个论域中至少存在一个个体,其P(x)值为T 约束变量(变元):出现在量词符号中的变量 自由变量:不受量词约束的变量 例:
◆谓词演算的合式公式
可按下述规则得到谓词演算的合式公式: (1) 原子谓词公式是合式公式。
(2) 若A 是合式公式,则~A 也是合式公式。 (3)若A 和B 都是合式公式,则A ∧B 、A ∨B 、A →B 、A ?B 也都是合式公式。 (4)若A 是合式公式,x 是任一个体变元,则(?x)A 和(?x)A 也都是合式公式。 (5)只有按(1)—(4)所得的公式才是合式公式。 谓词逻辑合式公式例: ①马科斯是男人 ②马科斯是庞贝人
③所有的庞贝人都是罗马人 ④恺撒是一个统治者
⑤所有罗马人或忠于恺撒或仇恨他 ⑥每个人忠于某个人
⑦人们只想暗杀他们不忠于的统治者 ⑧马科斯试图谋杀恺撒
◆归结原理的完备性
对于一阶谓词逻辑,从不可满足的意义上说,归结原理是完备的。即若子句集是不可满足的,则必存在一个从该子句集到空子句的归结推理过程;反之,若从子句集到空子句存在一个归结推理过程,则该子句集必是不可满足的。 ◆利用归结原理进行定理证明 应用归结原理进行定理证明的步骤如下: 设要被证明的定理可用谓词公式表示为如下的形
式:A1∧A2∧…∧An →B (1)首先否定结论B ,并将否定后的公式~B 与前提公式集组成如下形式的谓词公式: G= A1∧A2∧…∧An
∧~B
(2) 求谓词公式G 的子句集S 。
(3) 应用归结原理,证明子句集S 的不可满足性,从而证明谓词公式G 的不可满足性。这就说明对结论B 的否定是错误的,推断出定理的成立。 (1)()(2)()(3)()()()(4)()(5)()()(,)(,)(6)(,)
(7)[()()sin (,)(,man Marcus Pompeian Marcus x Pompeian x Roman x ruler Caesar x Roman x loyalto x Caesar hate x Caesar x yloyalto x y x y person x ruler y tryassa ate x y loyalto x ????∨????∧∧??)(8)sin (,)y tryassa ate Marcus Caesar )()(x A x x xA ?????)()(x A x x xA ?????)
()())()((x xB x xA x B x A x ?∧??∧?)()())()((x xB x xA x B x A x ?∨??∨?12()()()()()n
P a P a P x P x a ?∧∧?∧ 12()()()()()n P a P a P x P x a ?∨∨?∨
例已知:
A: (?x)((? y)(P(x,y)∧Q(y))→(? y)(R(y)∧T(x,y)))
B: ~(? x)R(x)→(? x)(? y)(P(x,y)→~Q(y))
求证:B是A的逻辑结论。
证明首先将A和~B化为子句集
(1)~P(x,y)∨~Q(y) ∨R(f(x))
(2)~P(x,y)∨~Q(y) ∨T(x,f(x)) //(1)(2)为
A
(3)~R(z)
(4)P(a,b)
(5)Q(b) //(3)(4)(5)为B
下面进行归结:
(6)~P(x,y)∨~Q(y) (1)与(3)归结,σ={f(x)/z} (7)~Q(b) (4)与(6)归结,σ={a/x,b/y} (8)NIL(空子句)(5)与(7)归结
所以B是A的逻辑结论。
◆应用归结原理进行问题求解
下面是利用归结原理求取问题答案的步骤:
(1)把已知前提条件用谓词公式表示出来,并化成相应的子句集,设该子句集的名字为S1。
(2)把待求解的问题也用谓词公式表示出来,然后将其否定,并与一谓词ANSWER构成析取式。谓词ANSWER 是一个专为求解问题而设置的谓词,其变量必须与问题公式的变量完全一致。
(3)把问题公式与谓词ANSWER构成的析取式化为子句集,并把该子句集与S1合并构成子句集S。
(4)对子句集S应用谓词归结原理进行归结,在归结的过程中,通过合一置换,改变ANSWER中的变元。(5)如果得到归结式ANSWER ,则问题的答案即在ANSWER谓词中。
例任何兄弟都有同一个父亲,John和Peter是兄弟,且John的父亲是David,问Peter的父亲是谁?
解第一步:将已知条件用谓词公式表示出来,并化成子句集,那么要先定义谓词。
(1)定义谓词:
设Father(x,y)表示x是y的父亲。
Brother(x,y)表示x和y是兄弟。
(2)将已知事实用谓词公式表示出来。
F1 :任何兄弟都有同一个父亲。
(x)(y)(z)(Brother(x,y)∧Father(z,x)→Father(z,y))
F2:John和Peter是兄弟。Brother(John,Peter)
F3:John的父亲是David。Father(David, John) (4)将它们化成子句集得:
S1={~Brother(x,y)∨~Father(z,x)∨Father(z,y), Brother(John,Peter), Father(David,John)}
第二步:把问题用谓词公式表示出来,并将其否定与谓词ANSWER作析取。
设Peter的父亲是u,则有:Father(u,Peter)。
将其否定与ANSWER作析取,得:
G:~Father(u,Peter)∨ANSWER(u)
第三步:将上述公式G化为子句集S2,并将S1和S2合并到S。
S2 ={~Father(u,Peter)∨ANSWER(u)}
S= S1∪S2
将S中各子句列出如下:
(1)~Brother(x,y)∨~Father(z,x)∨Father(z,y)。
(2)Brother(John,Peter)。
(3)Father(David,John)。
(4)~Father(u,Peter)∨ANSWER(u)。
第四步:应用归结原理进行归结
(5) ~Brother(John,y)∨Father(David,y) (1)与(3)归结σ={David/z,John/x}
(6)~Brother(John,Peter)∨ANSWER(David) (4)与(5)归结σ={David/u,Peter/y}
(7)ANSWER(David) (2)与(6)归结
第五步:得到了归结式ANSWER(David),答案即在其中,所以u=David。即Peter的父亲是David。
◆归结过程的控制策略(?)
1.引入控制策略的原因
对子句集S进行归结时,首先要从子句集中找出可进行归结的一对子句进行归结。
第四章
推理:从已知事实出发,运用相关的知识(或规则)逐步推出结论或者证明某个假设成立或不成立的思维过程.其中已知事实和知识(夫则)是构成推理的两个基本要素.
不确定性推理:就是从具有不确定性的证据出发,运用不确定性的知识或规则库中的知识,最终推出具有一定程度的不确定性,但却是合理的或近乎合理的结论的思维过程。
不确定性推理的两个分类:模型方法;控制方法.
新的处理不确定推理方法:1.可信度方法2.主观Bayes方法3.证据理论方法.
不确定推理中的基本问题:1.不确定性的表示,不确定性主要包括两个方面:证据的不确定性和知识的不确定性.2.推理计算,不确定推理过程主要包括不确定性的传递计算算法、组合证据不确定性算法和结论不确定性的更新或合成算法.需要解决以下问题:①不确定性传递问题②证据
不确定性的合成问题③结论不确定性的合成问题.3.不确定性的量度.
可信度的概念:就是人们在实际生活中根据自已的经验或观察对某一事件或现象为真的相信程度.
CF(H,E):是知识的可信度,称为可信度因子(Certainty Factor)或规则强度.在专家系统MYCIN中,CF(H,E)被定义为:CF(H,E)=MB(H,E)-MD(H,E),其中,MB(Measure Belief)称为信任增长度.
单个证据的不确定性获取方法:如果支持结论的证据只有一条,则证据可信度值的确定分以下两种情况. ①证据为初始证据,其可信度的值一般由提供证据的用户直接指定,指定的方法也是用可信度因子对证据不确定性进行表示.
②用先前推出的结论作为当前推理的证据,对于这种情况的证据,其可信度的值在推出该结论时通过不确定性传递算法计算得到.证据E的可信度CF(E)也是在[-1,1]上取值. 组合证据的不确定性的获取方法:如果支持结论的证据有多个,那么这多个证据间的关系有可能是合取关系,也可能是析取关系.这多个证据构成一个组合证据.1.当证据是多个单一证据的合取时,即E=E1∧E2∧E3∧…∧E n.2.若E1,E2,E3,…,E n各证据的可信度分别为CF(E1),CF(E2),CF(E3),…,CF(E n),则CF(E)=min{CF(E1),CF(E2),CF(E3),…,CF(E n)}.2.当证据是多个单一证据的析取时,即E=E1VE2VE3V…VE n.若E1,E2,E3,…,E n各证据的可信度分别为CF(E1),CF(E2),CF(E3),…,CF(E n), 则CF(E)=max{CF(E1),CF(E2),CF(E3),…,CF(E n)}.
第五章
搜索的概念:解决的问题是如何寻找可利用的知识,即如何确定推理路线,才能使在付出尽量少的代价的前提下把问题圆满解决。根据问题的实际情况,按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的推理路线的过程,就称为搜索。所以搜索包含两层含义,一层含义是要找到从初始事实到问题最终答案的一条推现路线,另一层含义是找到的这条路线足时间和空间复杂度最小的求解路线。
搜索的种类:搜索分为盲目搜索和启发式搜索两种。盲目搜索又称无信息搜索,在搜索过程中,只按预先规定的搜索控制策略进行搜索,而没有任何中间信息来改变这些控制策略。启发式搜索又称有信息搜索,它是指在搜索求解过程中,根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向,使搜索朝着最有希望的方向前进,加速问题的求解,并找到最优解。搜索求解问题的基本思想:首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态,选择一适当的算符作用于当前状态,生成一组后继状态(或称后继节点),然后检查这组后继状态中有没有目标状态。如果有,则说明搜索成功,从初始状态到目标状态的一系列算符即是问题的解:若没有,则按照某种控制策略从已生成的状态中再选—个状态作为当前状态,重复上述过程,直到目标状态出现或不再有可供操作的状态及算符时为止。
宽度优先搜索: 宽度优先搜索又称为广度优先搜索,是一种盲目搜索策略。其基本思想是,从初始节点开始,逐层对节点进行依次扩展,并考察它是否为目标节点,在对下层节点进行扩展(或搜索)之前,必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面.
有界深度优先搜索:为了避免搜索过程沿着无穷的路径搜索下去,往往对一个节点扩展的最大深进行限制.
搜索树中节点深度的概念:1.搜索树中初始节点(即根节点)的深度为0;2.任何其它节点的深度等于其父节点的深度加上1.
启发式搜索:利用问题自身特性信息来提高搜索效率的搜索策略,称为启发式搜索或有信息搜索.
最佳优先搜索:又称为有序搜索或择优搜索.
局部最佳优先搜索:其思想是:当对某一个节点扩展之后,对它的每一个后继节点计算估价函数肋的值,并在这些后继节点的范围内,选择一个f(x)的值最小的节点,作为下一个要考察的节点。由于它每次只在后继节点的范围内选择下一个要考察的节点,范围比较小,所以称为局部最佳优先搜索或局部择优搜索。
全局最佳优先搜索: 全局最佳优先搜索也是一个有信息的启发式搜索,它的思想类似于宽度优先搜索所不同的是,在确定下一个扩展节点时,以与问题特性密切相关的估价函数f(x)作为标准,不过这种方法是在OPEN表中的全部节点中选择一个估价函数f(x)最小的节点,作为下一个被考察的节点.正因为选择的范围是OPEN表中的全部节点,所以称它称为全局最佳优先搜索或全局择优搜索.
第六章
机器学习:计算机自动获取知识,它是知识工程的3个分支(获取知识、表示知识、使用知识)之一。
学习的概念:学习是一个有特定目的的知识获取过程,其内在行为是获取知识、积累经验、发现规律,其外在
表现是使系统性能得到改进、系统实现自我完善、自适应环境。
机器学习概念:机器学习是研究如何使用计算机来模拟人类学习活动的一门学科。更严格地说就是研究计算机获取新知识和新技能、识别现有知识、不断改善性能、实现自我完善的方法。
机器学习研究的目标:机器学习研究的目标有3个:1.人类学习过程的认知模型。这一方身是对人类学习机理的研究。种研究不仅对人类的教育,而且对开发机器学习系统都有重要的意义;2.通用学习法。这个方身是对人类学习过程的研究,探索各种可能的学习方法,建立起独立于具体应用领域的通用学习算法;3.构造面向任务的专用学习系统(工程目标)。这一方身是要解决专门的实际问题,并开发完成这些专门任务的学习系统。
机器学习的发展史:分为4个阶段。其研究内容分别为:神经元模型和决策理论;符号概念获取;知识增强和论域专用学习;连接学习。
机器学习的主要策略及研究现状:
1、机械学习。机械学习又称记忆学习,是最简单的学习策略。这种学习策略不需要任何推理过程。外面输入知识的表示方式与系统内部表示方式完全一致,不需要任何处理和变换。
2、传授学习。传授学习又称指导式学习或指点学习在使用传授学习系统时,外界输入知识的表达方式与系统内部表达方式不完全一致,系统在接受外部知识时,需要一点推理、翻译和转化工作。
3、演绎学习。在演绎学习中,学习系统由给定的知识进行演绎的保真推理,并存储有用的结论。这种策略近几年才作为一种独立的学习策略。演绎学习包括知识改造、知识编译、产生宏操作、保持等价的操作和其他保真变换。
4、归纳学习。归纳学习是应用归纳推理进行学习的一类学习方法。按其有无教师指导,可以分为实例学习及观察与发现学习。
1)实例学习:实例学习义称为概念获取,它是通过
向学习者提供某一概念的一组正例和反例,使学习
者从这些正反例中归纳推理出概念的一股描述,这
个描述应能解释所有给定的正例并排除所有给定的
反例。这些正反例是由信息源提供的:信息源可能
是已经知道概念的教师、-也可能是学习者本身,还
可能是学习者以外的外部环境。
2)观察与发现学习。观察与发现学习又称为描述的
—般化。这类学习没有教师的指导,它要产生对所
有或大多数观察到的规律和规则的解释。这类学习
包括概念聚类、构造分类、曲线拟合(使方程符合数据)、发现并解释观察到的定律并形成理论。
5、类比学习。类比学习就是在遇到新的问题时,可以学习以前解决过的类似问题的解决办法,来解决当前的问题。
环境:环境就是指系统外部信息的来源,它可以是系统的工作对象,也可以是包括工作对象和外界条件。环境就是为学习系统提供获取知识所需的相关对象的素材或信息,如何构造高质量、高水平的信息,将对学习系统获取知识的能力有很大影响。
信息的质量:指对事物表述的正确性、选择的适当性和组织的合理性。
学习环节:学习环节通过对环境的搜索获得外部信息,并将这些信息与执行环节所反馈回的信息进行比较。学习环节就要从这些差距中获取相关对象的知识,并将这些知识存入知识库中。
知识库:知识库用于存放由学习环节所学到的知识。选择知识表示方法要考虑的准则:表达能力的强弱;推理难度的大小;修改的难易;是否便于扩充。
执行环节:执行环节是整个学习系统的核心。执行环节用于处理系统面临的现实问题,即应用知识库中所学到的知识求解问题,并对执行的效果进行评估,将评价的结果反馈回学习环节,以便系统进一步的学习。
第八章专家系统
8.1.2 专家系统的定义
专家系统是一种具有大量专门知识与经验的智能程序系统,它能运用某个领域一个或多个专家多年积累的经验和专门知识,模拟领域专家求解问题时的思维过程,以解决该领域中的各种复杂问题。也就是说,专家系统具有三个方面的含义:
它是一种具有智能的程序系统。能运用专家知识和经验进行推理的启发式程序系统。
它必须包含有大量专家水平的领域知识,并能在运行过程中不断地对这些知识进行更新。
它能应用人工智能技术模拟人类专家求解问题的推理过程,解决那些本来应该由领域专家才能解决的复杂问题。
8.1.3 专家系统的种类
对专家系统的类型划分可以有多种不同的方法。不同的分类方法所得到的分类结果也不同。
1. 按专家系统特性和处理问题的类型分类
(1)解释型:通过对已知信息和数据进行分析和推理,从而确定它们的含义,给出相应解释的一类专家系统。(2)诊断型:根据输入系统的有关被诊断对象的信息,
来推断出相应对象存在的故障和产生故障的原因,并进一步给出排除故障方法的一类专家系统。
(3)设计型:根据用户输入的设计要求数据,求解出满足设计要求的目标配置方案的一种专家系统。
(4)预测型:通过对过去知识以及当前的事实与数据进行分析,推断未来情况的一类专家系统。
(5)规划型:根据给定的规划目标数据,制定出某个能够达到目的的动作规划或行动步骤的一类专家系统。(6)监视型:这是一类用于对被检控对象进行实时地、不断地观察,并能观察到情况及时做出适当反应的专家系统。
(7)控制型:用来对一个受控对象或客体的行为进行适当的调节与管理,以使其满足预期要求的一类专家系统。(8)调试型:对失灵的对象制定出排除故障的规划并实施排除的一类专家系统。
(9)教学型:是一类可根据学生学习的特点,制定适当的教学计划和教学方法,以对学生进行教学和辅导的专家系统。
(10)修理型:对发生故障的系统或设备进行处理,使其恢复正常工作的一类专家系统。
除了以上这10种类型的专家系统外,决策型和管理型的专家系统也是近年来颇受人们重视的两类专家系统。
8.2 专家系统的基本结构
1 数据库及其管理系统
数据库又称综合数据库,用来存储有关领域问题的初始事实、问题描述以及系统推理过程中得到的种种中间状态或结果等,系统的目标结果也存于其中。
2 知识库及其管理系统
知识库是专家系统的知识存储器,用来存放被求解问题的相关领域内的原理性知识或一些相关的事实以及专家的经验性知识。原理性或事实性知识是一种广泛公认的知识,即书本知识和常识,而专家的经验知识则是长期的实践结晶。
3 知识获取机构
知识获取机构是专家系统中的一个重要部分,它负责系统的知识获取,由一组程序组成。其基本任务是从知识工程师那里获得知识或人训练数据
中自动获取知识,并把得到的知识送入知识库中,并确保知识的一致性及完整性。
4 推理机
推理机是专家系统在解决问题时的思维推理核心,它是一组程序,用以模拟领域专家思维过程,以使整个专家系统能够以逻辑方式进行问题求解。
5 解释器
解释器是人与机接口相连的部件,它负责对专家系统的行为进行解释,并通过人机接口界面提供给用户。
6 人—机接口
人-机接口是专家系统的另一个关键组成部分,它是专家系统与外界进行通讯与交互的桥梁,由一组程序与相应的硬件组成。
8.3知识获取的任务
利用某种手段从知识源中获取专家系统实现问题求解所需的专门知识,并以某种形式在计算机中存储,满足领域问题求解的需求。一般包括知识抽取、表示、输入和检测等几项工作。
8.4.2 专家系统建造步骤
图8.2专家系统的建造步骤
下面对图8.2所描述的专家系统开发的各个阶段分别进行讨论。
1)、应用领域选择与可行性分析
这一阶段主要工作包括以下几个方面:(1)问题调研;(2)应用领域选择与可行性分析
需求分析
原型设计与开发
原型系统评价
最终系统设计
最终系统实现
系统测试与评价
系统维护
可行性分析;(3)确定最终开发专家系统的应用领域及要解决的问题。
2)、需求分析
需求分析就是系统建造人员对用户的需求进行详尽的调查和仔细的分析,它是建立专家系统的第一步,需求分析的好坏直接影响着系统开发的成败。其内容包括:目标与任务描述、数据与知识描述、功能描述、性能描述、质量保证、时间与进度要求等。
3)、原型设计与开发
在建造系统原型时,要注意这样一些问题:(1)只追求系统主要功能的实现,暂不考虑系统的处理效率和次要功能;(2)知识库中的知识数量不能太多,但对解决该类型问题所需的知识类型应该齐全;(3)对系统的实现方法与知识库的构建方法、推理方法等都应有多种备选方案,以供专家、系统开发者和用户比较,以便在开发最终系统时选用最好的方法。
4)、原型评价
由用户、领域专家、知识工程师和系统编程人员共同对系统的主要功能、知识推理功能等需求规格说明书中的主要指标进行测试及评价,对其不足进行反馈,以便进行修改。
5)、最终系统设计
该阶段的主要任务包括:问题的详细定义;确定项目规划;对系统各个方面进行设计,如基本知识描述、系统体系结构、工具选择、知识表示方式、推理方式、对话模型等;制定测试规划;制定产品规划;提出实施规划等。本阶段的最终结果使系统设计说明书。
6)、最终系统实现
本阶段依据最终系统设计说明书对专家系统进行编程实现。选择适当的语言环境和软件开发工具,完成的主要工作包括:原型系统修改;系统实现;系统集成与验证。
7)、系统测试与评价
最终系统完成后,还需对其进行必要的测试与评估,并根据测试与评估结果对系统进行必要的修改,以达到需求分析书中所确立的性能与功能指标。
8)、系统维护与完善
在这一阶段中,系统人员要倾听用户的反映,对系统中的一些不足进行不断的完善。主要的工作是:不断增加系统功能;不断修改系统,尤其是扩充知识库,使其更完备;不断扩大系统应用领域,增强系统的问题求解能力;修改系统,使其能够适应外部环境的变化。
1. 专家系统的评价方法
以下两种方法是在评价专家系统时常用的方法。(1)“逸事”评价法。利用一些典型例子来对系统的性能进行说明,向人们证明系统在这些典型例子所具有的条件下工作性能良好。对于这些例子以外的其他情况,系统能否很好的工作并不知道。
(2)实验的方法。利用实验来评价专家系统在处理存储于数据库中的各种问题实例时,所表现出的性能。这种方法看起来似乎比逸事方法优越,但在系统实现上难度较大,在获取数据库中哪些有代表性的实例时,也常常会遇到困难。
8.6 专家系统开发工具
常用的专家系统开发工具和环境可分为4种主要类型:语言型开发工具、骨架型开发工具、通用型开发工具、开发环境与辅助型开发工具。
8.6.1 语言型开发工具
程序设计语言是开发专家系统的最常用和最基本的工具,包括通用程序设计语言和人工智能语言。用于专家系统开发的通用程序设计语言的主要代表有C、C++、PASCAL、ADA等;人工智能语言的主要代表有SMALLTALK、LISP和PROLOG。SMALLTALK是面向对象型的语言,LISP为函数型语言,而PROLOG则是逻辑型语言。
其优点是程序设计具有针对性,程序质量较高。缺点是编程工作量大,逻辑设计比较繁琐,难度大,开发周期长。
8.6.2 骨架型开发工具
也称为专家系统外壳或框架型开发工具,是由一些已经成熟的具体专家系统演变来的。其演变方法是:抽去这些专家系统中的具体知识,保留它们的体系结构和功能,再把领域专用的界面改为通用界面,这样就可得到相应的专家系统外壳或框架。
比较有代表性的专家系统骨架型开发工具主要有EMYCIN、KAS及EXPERT等。
有关这些开发工具的详细介绍请参见教材。
8.6.3 通用型开发工具
该类型开发工具是不依赖于任何已有专家系统,不针对任何具体领域,完全重新设计的一类专家系统开发工具。与骨架系统相比,它具有更大的灵活性和通用性,并且对数据及知识的存取和查询提供了更多的控制手段。这类型工具的典型代表是OPS系列通用开发工具。OPS是美国卡内基-梅隆大学(CMU)的J. McDermott, A. Newell等人,于1975年利用LISP语言研制开发的一个基于规则的通用型专家系统开发工具。自问世以来,已有OPS1、OPS2、OPS3、OPS4、OPS5、OPS5+、OPS5e、OPS7及OPS83等多种版本相继诞生。这些版本之间的差
异较大,其中最有代表性的版本是OPS5。
8.6.4 开发环境与辅助型开发工具
开发环境是指帮助专家系统建造者进行程序设计的系统环境,它常被作为建造专家系统的知识工程语言的一部分。早期的开发环境又称支撑环境,规模较小,功能也比较少,通常由辅助调试工具、知识库编辑器、输入/输出处理工具及解释工具4个典型部分组成。作为专家系统建造工具的一部分,帮助建造者更好地使用专家系统建造工具。辅助型专家系统开发工具则是由一些程序模块组成,用来帮助专家系统建造者开发应用系统。AGE、TEIRESIAS、ROUGET、TIMM、EXPERTEASE、SEEK、MORE、ETS等都是辅助型工具程序的典型。其中AGE是辅助进行系统结构设计的典型程序,TEIRESIAS是辅助进行知识获取的典型程序。