人工智能第2章 知识表示

1、敖志刚 编制,第2章 知识表示,第2章 知识表示,21 知识与知识表示的概念 211 知识 212 知识表示 22 状态空间表示法 221 状态空间表示法的基本概念和策略 222 状态空间表示法示例 23 与/或图知识表示 231 与/或图知识表示的概念 232 与/或图表示示例,第2章 知识表示,24 产生式知识表示 241 产生式的结构和组成 242 产生式系统的分类 243 产生式系统的性能及其应用 25 语义网络 251 语义网络的概念 252 语义网络的推理 253 语义网络表示法的特征 26 框架表示法 261 框架表示法的概念与设计 262 框架的基本结构和描述 263 框架系统

2、 264 框架系统的推理和求解过程 264 五种知识表示方法的比较,21 知识与知识表示的概念2.1.1 知识1. 知识的概念,知识是人们对客观事物及其规律的认识，包括对事物的现象、本质、属性、状态、关系、联系和运动等的认识；是解决问题的步骤、操作、规则、过程、技术、技巧、战术、战略、计谋、策略。知识是经过消减、加工、整理、解释、挑选、改造、选择和转换的信息和数据，是由特定领域的事实、信念、描述、关系、启发式和过程组合起来的。,2. 知识的分类,按知识的作用：叙述型知识、过程型知识、控制型知识； 按知识的的性质：对象性知识、事件性知识、性能性知识、元知识； 按知识的作用范围：常识性知识、领域性

3、知识； 按知识的层次：表层知识、深层知识； 按知识的确定性：确定性知识、不确定性知识,3. 知识的属性,可表示性、可利用性、不确定性、矛盾性、相容性、真假性、相对性。,212 知识表示面向人的知识表示的概念,面向人的知识表示可以用是语言、文字、数字、符号、公式、图表、图形、图像等多种形式。这些表示形式是人所能接受、理解和处理的形式。,2. 面向计算机的知识表示的概念,就是要用某种约定的(外部)形式结构来描述知识，通常用知识的规则符号、形式语言和网络图等使知识形式化或模型化 ，而且这种形式结构还要能够转换为机器的内部形式，在计算机中用合适的形式对问题求解过程中所需要的各种知识进行组织、存储、检索

4、、使用、增删、修改、推理和判断；使得计算机能方便地存储、处理和利用。,3. 设计知识表示的基本原则,可实现性、可理解性、表示能力、可维护性、可利用性、自然性、可组织性,4. 知识表示方法的分类,状态空间表示法 基于图的表示法 与/或图表示法 语义网络表示法 谓词逻辑表示法 产生式表示法 特性表示法 框架表示法 知识表示 功能表示法 脚本表示法 过程表示法 多层次信息结构表示法 概念图解表示法 神经网络表示法 意识胞表示法 不精确表示法,状态图,与或图示例,语义网络示例,产生式推理网络示例,22 状态空间表示法2.2.1 状态空间表示法的基本概念,状态：各种相关对象的可能的排列、情况、形势和现状

5、。 表示形式：通常用一组指标、变量或数组来表示。 三个共有特征：就是状态、规则和目标。 问题的三种状态：开始状态、中间状态和目标状态。,知识表示一般步骤:,1 定义一状态空间； 2 确定开始状态； 3 确定目标状态； 4 规定一组规则； 5 将非形式的问题描述转换成形式描述；画出描述问题的状态图； 6 分析问题； 7 选择最佳技术去求解待解问题。,2.2.2 状态空间表示法示例,例2-1 水壶问题 有两个水壶，一个盛满为4公斤水，另一个盛满为3公斤水，水壶上没有任何度量标记。怎样在能装4公斤的水壶里恰好只装2公斤水。,定义操作符,1 (X，YX4) (4，Y) 把4公斤的水壶装满。 2 (X，

6、YY3) (X，3) 把3公斤的水壶装满。 3 (X，YXO)(XD，Y) 从4公斤的水壶倒出一些水。 4 (X，YYO) (X，YD) 从3公斤的水壶倒出一些水。 5 (X，YXO)(O，Y) 把4公斤水壶中的水全部倒掉。 6 (X，YYO)(X，O) 把3公斤水壶中的水全部倒掉。 7 (X，YX+Y4YO)把3公斤水壶中的水往4公斤水壶 (4，Y一 (4一X) 里倒，直到4公斤水壶满。 8 (X，YX+Y3XO) 把4公斤水壶中的水往3公斤水壶 (X一(3一Y)，3) 里倒，直到3公斤水壶满。 9 (X，YX+Y3XO)(O，X+Y) 把4公斤水壶中水全部倒入3公斤水壶。 10(X，YX+

7、Y4YO)(X+Y，O) 把3公斤水壶中水全部倒入4公斤水壶。,例2-2修道士和野人问题,在河的左岸有3个修道士，3个野人和1条船，修道士们想用这条船将所有的人都运过河去，但是受到以下条件的限制： 修道士和野人都会划船，但船一次只能装运两个人； 修道士的人数必须大于野人数； 野人不知道是个骗局。 试问修道士如何用这条船将这些人全部都渡到河的对岸？,表2-2 修道士和野人问题全部状态的合法性,X Y Z 合法性 X Y Z 合法性 X Y Z 合法性 X Y Z 合法性 3 3 1 合法 3 2 1 合法 3 1 1 合法 3 0 1 不可能 2 3 1 不合法 2 2 1 合法 2 1 1 不

8、合法 2 0 1 不合法 1 3 1 不合法 1 2 1 不合法 1 1 1 合法 1 0 1 不合法 0 3 1 合法 0 2 1 合法 0 1 1 合法 0 0 1 不可能 3 3 0 不可能 3 2 0 合法 3 1 0 合法 3 0 0 合法 2 3 0 不合法 2 2 0 合法 2 1 0 不合法 2 0 0 不合法 1 3 0 不合法 1 2 0 不合法 1 1 0 合法 1 0 0 不合法 0 3 0 不可能 0 2 0 合法 0 1 0 合法 0 0 0 合法,定义规则, 将一个修道士从左岸运到右岸； 将一个野人从左岸运到右岸； 将一个修道士和一个野人从左岸运到右岸； 将二个修

9、道士从左岸运到右岸； 将二个野人从左岸运到右岸； 将一个修道士从右岸运到左岸； 将一个野人从右岸运到左岸； 将一个修道士和一个野人从右岸运到左岸； 将二个修道士从右岸运到左岸； 将二个野人从右岸运到左岸；,状态图的概念,修道士和野人问题的状态图,计算机的表达方法,按BASIC语言的写法，就是用赋值语句： 10 LET X = X 2 20 LET Z = 0 30 LET X = X + 1 40 LET Y = Y + 1 50 LET Z = 1,例2-3 梵塔问题：传说印度的主神梵天做了一个梵塔，它是在一块黄铜板上插3根宝面针，其中一根针上从上到下按从小到大的顺序串上了64个金片。梵天要

10、求僧侣们轮流把金片在三根针之间移来移去，规定每次只能移动1片，且不许大片压到小片上。并说如果这64片金片全部移至另一根针上时，世界就会在一声霹雳之中毁灭。,梵塔问题的状态图,二金片问题的一种最佳求解过程,二金片问题的状态空间图,三金片问题的一种最佳求解过程,23 与/或图知识表示,如果一个问题p可以分解为一组子问题P1、P2、P3 ， ，Pn ，并且只有当所有子问题Pi(i=1，2，3 ， ，n)都有解时原问题P才有解，任何一个子问题Pi(i=1，2，3 ， ，n)无解都会导致原问题P无解，则分解所得到的子问题的“与”与原问题P等价。P与P1、P2、P3 ， ， Pn之间的关系就可以用一棵“与

11、树”来表示。,与或图示例,可解节点,在与/或图中，满足以下三个条件之一的节点为可解节点: 任何终止节点都是可解节点。 对“或”节点，当其子节点中至少有一个为可解节点时，则该“或”节点就是可解节点。 对“与”节点，只有当其子节点全部为可解节点时，该“与”节点才是可解节点。,不可解节点,可用类似的方法定义不可解节点: 不为终止节点的端节点是不可解节点。 对“或”节点，若其全部子节点都为不可解节点，则该“或”节点是不可解节点。 对“与”节点，只要其子节点中有一个为不可解节点，则该“与”节点是不可解节点。,与或图表示举例,例2-4 试证明两四边形全等问题T，如图2-9所示，要求用与/或图表示。 证明

12、现假设： T1：证明 ABD ABD； T2：证明 BCD BCD。 T1又可以等价于三个子问题E1、E2、E3的与，其中 E1：AB=AB；E2：AD= AD；E3：BD=BD。 T2也可以等价三个子问题E3、E4、E5的与，其中 E3：BD=BD；E4：BC= BC；E5：CD= CD。,两全等四边形,与/或图表示,示例,例 试求积分 有两种方法解此积分 1因为 ，所以上述积分变为 2上述积分可按下式变换 上述两种方法可用下列与/或图如图2-11来描述,与或图表示,示例,例2-5 分火柴游戏，设堆有7根火柴，由Max（我方）和Min方（对手）两人轮流来分它们，要求每次都要把某堆火柴分成不相

13、等的两部分，最后不能分下去的人为负，对方为胜。如果对方先走，用与/或图知识表示来描述。 如果MIN先走，他有三种选择方法：(6，1)、(5,2)、(4，3)，在MIN的每一种选择下，MAX又有两种走法，整个博弈与/或图如图2-12所示。,与或图表示,24 产生式知识表示,产生式(Production)一词最早是由美国数学家波斯特(EPost)于1943年根据串替换规则提出的一种称为Post机的计算模型。1954年，Markov对Post的产生式系统作了改进，提出了产生式系统的控制策略，根据规则的优先级来确定其执行的顺序。1957年Chomskey利用一系列产生式规则来描述每层文法的语言生成规则

14、。1972年，纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统。目前，产生式表示法已成为人工智能中应用最多的一种知识表示模式。,241 产生式的结构和组成,产生式的一般形式为“前件+后件”。前件就是前提，后件是结论或动作 。 产生式包括各种操作、规则、变换、算子、函数等等 产生式表示法可以很容易地描述事实、规则以及它们的不确定性度量。 规则描述的是事物间的因果关系。其基本形式为:“PQ”或“IF P THEN Q”， 含义是：如果前提P满足，则可推出结论Q或执行Q所规定的操作；,图表示概念,产生式系统示例,例2-6 一个动物识别系统的产生式如下: R1: :若某动物有奶，则它是哺乳

15、动物。 R2: 若某动物有毛发，则它是哺乳动物。 R3: 若某动物吃肉，则它是食肉动物。 R4: 若某动物有爪且有犬齿且眼视前方，则它是食肉动物。 R5: 若某动物是哺乳动物且有蹄，则它是有蹄动物。 R6: 若某动物是有蹄动物且反刍食物，则它是有蹄动物。 R7: 若某动物是哺乳动物且食肉动物且黄褐色且有黑色条纹，则它是老虎。 R8: 若某动物是哺乳动物且食肉动物且黄褐色且有暗斑点，则它是金钱豹。 R9: 若某动物是有蹄动物且有黑色条纹，则它是斑马。 R10: 若某动物是有蹄动物且长腿且长脖子且有暗斑点，则它是长颈鹿。,产生式系统的三个主要部分,产生式系统问题求解的基本过程:,初始化全局数据库,

16、把已知事实送入全局数据库中。 检查规则库是否有末使用的规则，若有执行；否则转。 检查规则库的末使用规则中是否存在有其前提可与全局数据库中已知事实相匹配的规则，若有从中选择一个；否则转。 执行当前选中规则，并对该规则作上标记，把执行该规则后所得到的结论作为新的事实放入全局数据库；如果该规则的结论是一些操作，则执行这些操作。 检查全局数据库中是否包含了该问题的解，若已包含，则说明己求出解，问题求解过程结束；否则转。 当规则库中还有未使用的规则，但均不能与全局数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供,则转,否则，说明该问题无解，终止问题求解过程。 若知识库中不再有

17、末使用规则，也说明该问题无解，终止问题求解过程。,242 产生式系统的分类,1. 从总体控制策略上分类 不可挽回的产生式系统 试探性产生式系统 回溯产生式系统 图搜索产生式系统 2. 按推理方向分类 向前产生式系统 向后产生式系统 双向产生式系统 3. 按规则库的性质及结构分类 可交换的产生式系统 可分解的产生式系统 可恢复的产生式系统,例 四皇后问题。,例2-8设全局数据库的初始状态为C，B，Z，目标状态为M，M， ，M，规则库中有如下重写规则:R1: CD，L R2: CB，M R3: BM，M R4: ZB，B，M,产生式系统的优点：,1模块性 2自然性 3 有效性 4 一致性 5 容易

18、排除故障 6推理方向的可逆性 7控制机构的多样性,产生式系统的缺点 1 效率不高 2 非透明性 3 解释能力 的局限性,产生式系统应用场合:,1知识结构类似于产生式规则的领域并且领域知识是扩散型的，领域内需要有大量的经验知识，不具备精确统一的理论，如临床医学、医疗诊断系统等。 2可以自然地用产生式规则的后件来表达的领域。该领域知识中包含一系列相互独立的动作，如医院的病人监护系统。 3领域知识可方便地从应用中分离出来的领域，如树类型辨识系统，经典分类学等。,产生式系统的改进,1扩大规则集的表达能力。 2提高规则集的检索效率。如“激发树”结构，或增加元规则，即规则的规则，组成多层结构的规则集，指导

19、规则的运用。 3改进控制策略。解决规则匹配的优先次序和冲突裁决问题。 4合理分配知识。为了提高事实库检索与规则集匹配的效率，需要灵活地将知识合理分配在规则集和事实库中。,25 语义网络,语义一般是指语言结构(如词、短语、句子、段落等)及其意义上的联系。 语义网络在形式上是一个有向图，由一组节点和若干条有向弧线构成，节点和弧都可以有标号。节点表示各种事物、对象、概念、情况、性质、状态、事件、行为等；弧表示节点间的语义联系或关系。,语义网络划分为七种类型:,1命题语义网(包括分块联想网络)； 2数据语义网:以数据为中心的语义网络； 3语言语义网:用于自然语言的分析和理解； 4结构语义网:描述客观事

20、物的结构，常见于模式识别和机器学习等领域； 5分类语义网:描述抽象概念及其层次； 6推理语义网:是一种命题网，但它已在某种程度上规范化，更适于推理； 7. 框架语义网：与框架相结合的语义网。,语义网络示例,最常用的基本语义关系有以下几种,1类属关系。 是指具有不同事物间的分类关系、成员关系或实例关系。常用的类属关系有: A-Kind-of（是一种）、A-Member-of（是一员）、Is-a（是一个）。 2 包含关系。是指 “部分与整体”之间的关系。常用的包含关系有:A-part-of（是一部分）。 3 属性关系。是指事物和其属性之间的关系。常用的属性关系有:Have（有）、Can（能、会）、

21、所有者（Owner）。 4 时间关系。时间的先后次序关系，常用的时间关系有Before（在前），After（在后）。,最常用的基本语义关系有以下几种,5. 推论关系。一个概念可由另一个概念推出，如Fetch（推出）。 6. 位置关系。 位置方面的关系。如Located-on（在上）、Located-at（在）、Located-under（在下）、Located-inside（在内）、Located-outside（在外）。 7相近关系。是指形状、内容等方面相似或接近。如Similar-to（相似）、Near-to（接近）。,用 Prolog语句表示,Located-under（“校园”，“钟山

22、”）； Located-inside（“建筑物”，“校园”）； Located-at（“理工大学”，“海福巷”）； Similar-to（“校园”，“公园”）； Fetch（“公园”，“风景美丽”）； A-Member-of（“张三”，“学会”）； A-Kind-of（“图书馆”，“建筑物”）； A-part-of（“阅览室”，“图书馆”）； Is-a（“理工大学”，“单位”）； Is-a（“张三”，“读者”）； Owner（“图书馆”，“理工大学”）； Near-to（“图书馆”，“大礼堂”）； Have（“阅览室”，“读者”）； After（“阅览”，“开放”）； Can（“张三”，“讲英

23、语”）； Can（“阅览室”，“开放”）； Can（“读者”，“阅览”）。,例 试用语义网络描述拱的概念和形状。,252 语义网络的推理,1. 匹配 事物的匹配则为结构上的匹配，包括节点和弧的匹配。用匹配的方法进行推理时，首先构造问题的目标网络块，然后在事实网络中寻找匹配。推理从一条弧连接的两个节点的匹配开始，再匹配与该两个节点相连接的所有其他节点，直到问题得到解答。 假设在知识库中存放着如图2-19所示的语义网络，问图书馆会干什么呢？,2. 继承,所谓继承是指把对事物的描述从抽象节点传递到具体节点。通过继承可以得到所需节点的一些属性值，它通常是沿着Is-a、A-Kind-of等继承弧进行的。

24、继承的一般过程为: 1建立一个节点表，用来存放待求解节点和所有以Is-a、A-Kind-of等继承弧与此节点相连的那些节点。初始情况下，表中只有待求解节点。 2检查表中的第一个节点是否有继承弧。如果有，就把该弧所指的所有节点放入节点表的末尾，记录这些节点的所有属性，并从节点表中删除第一个节点。如果没有，仅从节点表中删除第一个节点。 3重复2，直到节点表为空。此时，记录下来的所有属性都是待求解节点继承来的属性。 例如，在图2-19所示的语义网络中，通过继承关系可以得到：张三不仅会讲英语，而且会阅览；阅览室在校园内，会开放，而且周围风景很美。,253 语义网络表示法的特征,1 知识的深化表达 2

25、联想性 3 自然性 4结构化组织 语义网络的缺点，主要表现为: 其形式过于简单。如果节点间的联系只局限于几种典型的关系，则难以表达较复杂的关系;而增加联系又会大大增加网络的复杂度，相应的知识存储和检索过程就会变得十分复杂。事实上，语义网络的管理和维护也是很复杂的。此外，语义网络本身没有赋予其节点和弧以确切的含义。,26 框架表示法,1. 定义 框架（Frames）是一种描述对象属性的数据结构。人们只要把新的数据加入到该通用数据结构中便可形成一个具体的实体，这样的通用数据结构就称为框架。 实例框架：把具体细节填入后，就得到了该框架的一个具体实例，也被称为实例框架。 框架系统：由一组框架节点及其相

26、互关系组成一个结构化的整体。 框架系统推理：由框架之间的协调来完成。 框架表示方法：是一种层次的、组合式的知识表示方法。,2. 框架的基本结构, | | | ,3. 框架结构的示例,例2-11 一个描述硕士生有关情况的框架 框架名： 姓名：单位（姓，名） 性别：范围（男，女） 默认：男 年龄：单位（岁） 条件：岁17 研究方向：单位（方向名） 导师姓名：单位（姓，名） 参加课题：范围（国家级，省部级，其它） 默认：省部级 学籍： 住址：单位（楼号，房间号） 电话：单位（区号，话机号） 入学时间：单位（年月） 学制：单位（年） 默认：3年,4.实例框架,例2-12 硕士生框架的一个实例框架： 框

27、架名： 姓名：李学表 性别：男 年龄：22 研究方向：人工智能 导师姓名：吴博能 参加课题： 学籍： 住址：6号楼205房间 电话：(025)78787878 入学时间：2008年9月 学制：,5.框架的BNF（巴科斯范式）描述, := := 框架名 := , := 约束, := |(,) := | := | := | := , := := | := | := | := |, := ,6.框架系统的基本结构,7. 学生框架系统的表示,例2-13 学生框架 框架名： 姓名：单位（姓，名） 性别：范围（男，女） 默认：男 年龄：单位（岁） 住址：单位（楼号，房间号） 电话：单位（区号，话机号） 入学时间：单位（年，月） 学制：单位（年）,8. 硕士生框架系统的表示,例2-14 硕士生框架 框架名： 继承： (纵向联系) 学籍： (横向联系) 研究方向：单位（方向名） 导师姓名：单位（姓，名） 参加课题：范围（国家级，省部级，其它） 默认：省部级 学位论文：单位：（论文题目） 默认：题目未定,9