知识表示和处理方法

1、第3讲 知识表示和处理方法2010年10月8日1知识回顾问题的状态和状态空间盲目的搜索方法启发式搜索方法图搜索策略博弈(一). 如何定义状态空间及其搜索(二). 问题的特征分析2知识回顾问题的状态和状态空间盲目的搜索方法启发式搜索方法图搜索策略博弈(一).宽度优先搜索(二).深度优先搜索(三).分支有界搜索(四).迭代加深搜索3知识回顾问题的状态和状态空间盲目的搜索方法启发式搜索方法图搜索策略博弈(一).启发式信息的表示(二).几种最基本的搜索策略4知识回顾问题的状态和状态空间盲目的搜索方法启发式搜索方法图搜索策略博弈(一).一个通用的图搜索算法(二). A算法和A*算法5知识回顾问题的状态和

2、状态空间盲目的搜索方法启发式搜索方法图搜索策略博弈(一).极大极小(MAXMIN)过程(二). -过程6主要内容概述一阶谓词逻辑表示法产生式表示法语义网络表示法框架表示法过程式知识表示认识rolog语言7概述 “知识就是力量”这句名言在人工智能领域中能够得到很好的体现。 人工智能的求解是以知识为基础的，所以知识表示是人工智能研究的重要课题。 人工智能问题的求解是以知识为基础的。如何将已获得的有关知识以计算机内部代码形式加以合理地描述、存储，以使有效地利用这些知识便是知识表示。知识表示方法的提出，常模仿人脑的知识存储结构，心理学家对知识表示方法的研究做出了重要的贡献。 8概述一、知识和知识表示的

3、含义1、知识 读书破万卷，下笔如有神。 杜 甫 知识就是力量。 培 根 书是人类进步的阶梯。 高尔基 人的知识愈广，人的本身也愈臻完善。 高尔基 9概述一、知识和知识表示的含义1、知识 知识是经过裁剪、塑造、解释、选择和转换了的信息。 -费根鲍姆 知识是由特定领域的描述、关系和过程组成。 -伯恩斯坦 知识=事实+信念+启发式。 -海叶斯-罗斯 1994年图灵将的获得者。 他的重大贡献在于：通过实验和研究，证明了实现智能行为的主要手段在于知识，在多数实际情况下是特定领域的知识。10概述一、知识和知识表示的含义2、知识表示 人类拥有的知识如何才能被计算机系统所接受并用于实际问题的求解呢？ 怎样以合

4、适的方式将面向人的知识转化为计算机系统所能接受的形式呢？ 知识表示是将知识符号化，并输入计算机的过程和方法。 11概述一、知识和知识表示的含义2、知识表示 知识表示包含两层含义： (1) 用给定的结构，按一定的原则、组织方式表示知识。 (2) 解释所表示知识的含义。12概述一、知识和知识表示的含义2、知识表示 知识表示的目的： 不仅要解决知识在计算机中的存储问题，而且要使这种表示知识的方法能够方便地运用知识和管理知识。13概述一、知识和知识表示的含义2、知识表示 在AI中知识表示方法的目的：利用知识来帮助选择或限制程序的搜索范围。利用知识来帮助程序识别、判断、规划和学习。 14概述一、知识和知

5、识表示的含义3、智能系统中的知识 要使计算机系统具有智能，一般来说至少应该使系统拥有以下4方面的知识：对象(Object)和物体。AI中的知识表示应该能表示各种知识对象以及对象的类型、性质等。事件(Event)。AI中的知识表示应该能表示事件的时序、因果关系等。15概述一、知识和知识表示的含义3、智能系统中的知识行为(Performance)。是关于如何做的知识，如：如何写文章，如何编程等。元知识(Metaknowledge)。是关于知识的知识，即怎样知道什么是知识，以及如何运用知识。 16概述二、AI中知识表示方法分类1、过程式知识表示 过程性知识一般是表示如何做的知识，是有关系统变化、问题

6、求解过程的操作、演算和行为的知识。这种知识是隐含在程序之中的，机器是无法从程序的编码中抽取出来的。 17概述二、AI中知识表示方法分类1、过程式知识表示 过程式知识表示描述过程性知识，即描述表示控制规则和控制结构的知识，给出一些客观规律，告诉怎么做。过程性知识一般可用算法予以描述，用一段计算机程序来实现，如矩阵求逆程序，程序中描述了矩阵的逆和求解方法的知识。18概述二、AI中知识表示方法分类2、陈述式知识表示 陈述式知识描述系统的状态、环境和条件，以及问题的概念、定义和事实。19概述三、AI对知识表示方法的要求 首先，一种好的知识表示方法要求有较强的表达能力和足够的精细程度，考察三个方面： 1

7、、表示能力。要求能够正确、有效地将问题求解所需要的各类知识都表示出来。 2、可理解性。所表示的知识应易懂、易读、易于表示。 3、自然性。即表示方法要自然，要尽量实用于不同的环境和不同的用途，易于检查、修改和维护。 20概述三、AI对知识表示方法的要求 然后，从知识的利用上考察三个方面： 1、便于获取和表示新知识，并以合适方式与已有知识相连接。 2、便于搜索，在求解问题时，能够较快地在知识库中找出有关知识。 3、便于推理，要能够从已有知识中推出需要的答案或结论。 21概述四、知识表示要注意的问题 对人类而言，知识表示最主要的手段是自然语言。 要将知识植入到计算机中去，涉及到知识在计算机中的表示。

8、 知识在计算机中表示出来以后，还涉及到是否能够还原的问题，即是否“失真”的问题。 22概述四、知识表示要注意的问题 在建立知识表示是应注意以下问题： (1) 知识的范围和基本知识的确定。 (2) 决定哪些知识应该清楚地表达出来，哪些可以隐含。 (3) 知识库的模块化和可理解些性，知识的检索效率。 (4) 排除自然语言的二义性。 (5) 加入必要的常识知识。 23一阶谓词逻辑表示方法24作业1.什么是知识？有哪几种分类。（P58)2.试用一阶谓词逻辑表示法描述下述推理：（P58) 凡是清洁的东西就有人喜欢； 人们都不喜欢苍蝇； 所以苍蝇不清洁。25知识回顾知识概述一阶谓词逻辑表示法26主要内容产

9、生式表示法语义网络表示法框架表示法27产生式表示法美国数学家Post，1943年提出了一种计算形式体系里所使用的术语。主要是使用类似文法的规则，对符号串做替换运算。这就是最早的一个产生式系统。到了60年代，产生式系统成为认知心理学研究人类心理活动中信息加工过程的基础，由此心理学家认为，人脑对知识的存储就是产生式形式。因此，用它来建立人类认知模型。到目前为止，产生式系统已发展成为人工智能系统中最典型最普遍的一种结构。产生式表示方法是专家系统的第一选择的知识表达方式。28一、 产生式可以表示的知识种类及其基本形式表示（一）、可表示知识的种类 产生式表示方法容易描述事实，规则以及它们的不确定性度量。

10、产生式表示法29（二）、产生式的基本形式 PQ 或 IF P THEN Q 产生式表示法30（三）、产生式与谓词逻辑中蕴涵式的区别1、产生式可以表示精确与不精确知识，蕴涵式只能表示精确知识；2、产生式没有真值，蕴涵式有真值。产生式表示法31二、 知识的表示方法事实可看成是断言一个语言变量的值或是多个语言变量间的关系的陈述句，语言变量的值或语言变量间的关系可以是一个词，不一定是数字。如雪是白色的，其中雪是语言变量，其值是白色的。约翰喜欢玛丽，其中约翰、玛丽是两个语言变量，两者的关系值是喜欢。产生式表示法32二、 知识的表示方法一般使用三个元组（对象，属性，值）或（关系，对象1，对象2）来表示事实

11、，其中对象就是语言变量，若考虑不确定性就成四元组表示了。这种表示的机器内部实现就是一个表。如事实：老李年龄是35岁，便写成（Lee，Age，35）而老李、老张是朋友，可写成（Friend，Lee，Chang ）产生式表示法33三、 产生式的组成多数较为简单的专家系统都是以产生式表示知识的，相应的系统称作产生式系统。 产生式系统由个部分组成，即总数据库（或全局数据库）、产生式规则和控制策略。各部分间的关系如图所示。 产生式表示法34三、 产生式的组成（一）综合数据库 它是产生式系统所用的主要数据结构。它主要表示问题的状态，即初始状态、目标状态和中间状态，以及状态之间的关系等。它不是固定不变的，在

12、求解过程中，它的内容将越来越多，状态之间的关系也越来越复杂。 经常用来表示数据库的数据结构有串、集合、数组、树、表、记录、队列等。 产生式表示法35（二）产生式规则 是对数据库进行操作的一系列规则。规则的一般形式是： IF条件THEN操作 即满足应用的先决条件后，就对数据库实行后面的操作。产生式表示法36（三）控制策略 它规定了操作的顺序，即在什么条件下用什么规则进行操作，什么条件下停止运行，即它规定了问题求解的搜索策略和路线。一般，控制策略可分为两大类： 不可撤回方式(Irrevocable) 试探法(Tentative) a)回溯法(Backtracking) b)图搜索法(Graph-s

13、earch)产生式表示法37四、产生式系统的推理方法 产生式表示法38产生式表示法五、产生式系统的选择与匹配 从选择规则到执行操作分3步： 匹配、冲突解决和操作。 39产生式表示法五、产生式系统的选择与匹配（一）匹配。在这一步 ，把当前数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。 40产生式表示法（二）冲突解决。当有一条以上规则的条件部分 和当

14、前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。举例如下：设有以下两条规则，规则R1：IFfourth dawnshort yardagethen punt规则R2：IF fouth dawnshort yardagewithin 30 yards(from the goal line)then field goal41产生式表示法 这是两条关于美式足球的规则。 R1规则规定进攻一方如果在前三次进攻中前进的距离少于10码（short yardage)，那么在第四次进攻（fourth dawn）时，可以踢悬空球（punt） 。 R2规则规定，如果进攻这一方，在前三次进攻中，前进的

15、距离少于10码 ，而进攻的位置又在离对方球门线30码距离之内，那么就可以射门（field goal）。 42产生式表示法 如果当前数据库包含事实 “fourth dawn” 和 “short yardage”以及 “within 30 yards”，则上述两条规则都被触发， 这就需要用冲突解决来决定首先使用哪一条规则 。有很多种冲突解决策略，其中一种策略是先使用规则R2， 因为R2的条件部分包括了更多的限制，因此规定了一个更为特殊的情况。 这是一种按专一性来编排顺序的策略，称为专一性排序。还有不少其他的冲突解决策略， 如规则排序、数据排序、规模排序和就近排序等。 43产生式表示法 （a） 专一

16、性排序。如果某一规则条件部分规定 的情况，比另一规则条件部分规定的情况更有针对性，则这条规则有较高的优先级。 （b） 规则排序。如果规则编排的顺序 就表示了启用的优先级，则称之为规则排序。 （c） 数据排序。 把规则条件部分 的所有条件 按优先级次序编排起来，运行时首先使用在条件部分包含较高优先级数据的规则。44产生式表示法 （d） 规模排序。按规则的条件部分的 规模排列优先级，优先使用被满足的条件较多的规则。（e） 就近排序。把最近使用的规则放在 最优先的位置。这和人类的行为有相似之处。 如果某一规则经常被使用，则人们倾向于更多地使用这条规则。（f） 上下文限制。把产生式规则 按它们所描述的

17、上下文分组，也就是说按上下文对规则分组。在某种上下文条件下， 只能从与其相对应的那组规则中选择可应用的规则。45产生式表示法（三）操作。操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用。 46六、 产生式表示的特点产生式表示格式固定，形式单一，规则（知识单位）间相互较为独立，没有直接关系，使知识库的建立较为容易，处理较为简单的问题是可取的。 另外推理方式单纯，也没有复杂计算。特别是知识库与推理机是分离的，这种结构给知识库的修改带来方便，无需修改程序，对系统的推理路径也容易作出解释。 基于这些说明，产生式表示知识常作为建造专家系统的第一选择的知识表示方法

18、。 产生式表示法47语义网络表示法框架表示法48过程式知识表示语义网络、框架、剧本等知识表示方法，是对知识和事实的一种静止的表达方法，称为陈述性知识表达，是知识的一种显式表达方式。对于如何使用这些知识，则是通过控制策略来决定。过程表示法的本质是用程序的形式对知识进行表示，表示法中已经将那些用于求解问题的控制性策略融入到知识表示中，所有信息都隐含在程序中。49过程式知识表示过程表示法可有多种实现形式，过程规则式表示法是比较典型的一种，它主要包括四个部分：激发条件：在问题求解过程中，启动该知识所应满足的条件，或者说调用一个知识库中的程序所应具备的条件或提供哪些参数。演绎操作：一个过程中将一次被执行的动作。它由一系列的子目标构成。每个子目标就类似程序中的一条语句，在应用推理求解问题时，一旦某个过程的激发条件被满足，该过程被启动，其中的每个操作将被依次执行。状态转换：过程被执行中，用来完成对综合数据库的增、删、改操作。返回：过程规则的最后一个语句是返回语句，用以将控制权返回到调用该过程规则的上一级过程规则那儿去。50过程式知识表示假设有这样一条表示父子关系的知识：“如果x与y是兄弟，且z是x的父亲，则z也是y的父亲”，用过程规则表示法可表示如下：BR(Father ?z ?y)GOAL(Brother x y)GOAL(Fat