第1讲知识表示

1、Artificial Intelligence人工智能人工智能第一讲 知识表示2第1讲 知识表示o 知识与知识表示的概念知识与知识表示的概念o 状态空间表示法状态空间表示法o 问题归约及与或图表示法问题归约及与或图表示法o 谓词逻辑表示法谓词逻辑表示法o 产生式表示法产生式表示法o 语义网络表示法语义网络表示法32.1.1 知识的概念知识的概念o 知识：在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。o 知识：把有关信息关联在一起所形成的信息结构。o 知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。信息关联形式：信息关联形式：

2、“如果如果，则，则” 如果大雁向南飞，则冬天就要来临了如果大雁向南飞，则冬天就要来临了例：例：雪是白色的。雪是白色的。 事实事实如果头疼且流鼻涕，则有可能患了感冒。如果头疼且流鼻涕，则有可能患了感冒。规则规则4o 相对正确性相对正确性 任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的。2.1.2 知识的特征1+1=2（十进制）（十进制）1+1=10（二进制）（二进制）知 识 状 态 ：知 识 状 态 ： “ 真真 ” ，“假假”，“中间状态中间状态” 不确定性不确定性 随机性 模糊性 经验性 不完全性52.1.2 知识的特征3. 可表示性与可利用性可表示性与可利用性 知识的

3、可表示性：知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。 知识的可利用性：知识可以被利用。62.1.3 知识的分类知识的分类o 按知识的作用范围分类n 常识性知识：通用性知识。：通用性知识。n 领域性知识：专业性知识。：专业性知识。o 按知识的作用及表示n 事实性知识：有关概念、事实、事物的属性及状：有关概念、事实、事物的属性及状态等。态等。n 过程性知识：有关系统状态变化、问题求解过程：有关系统状态变化、问题求解过程的操作、演算和行动的知识。的操作、演算和行动的知识。n 控制性知识（深层知识或元知识）：关于如何运（深层知识或元知识）：关于如何运用已有的知识进行问题求解的知识。

4、用已有的知识进行问题求解的知识。醋是酸的。醋是酸的。北京是中国的首都。北京是中国的首都。一年有一年有12个月。个月。例：例：从北京到上海是乘飞机还是火车的问题表示如下：从北京到上海是乘飞机还是火车的问题表示如下： 事实性知识事实性知识：北京、上海、飞机、时间、费用：北京、上海、飞机、时间、费用过程性知识过程性知识：乘飞机、坐火车：乘飞机、坐火车控制性知识控制性知识：乘飞机较快、较贵；坐火车较慢、较便宜：乘飞机较快、较贵；坐火车较慢、较便宜72.1.3 知识的分类知识的分类o 按知识的结构及表现形式按知识的结构及表现形式n 逻辑性知识：反映人类逻辑思维过程的知识。逻辑性知识：反映人类逻辑思维过程

5、的知识。n 形象性知识：通过事物的形象建立起来的知识。形象性知识：通过事物的形象建立起来的知识。o 按知识的确定性按知识的确定性n 确定性知识：可指出其真值为确定性知识：可指出其真值为“真真“或或”假假“的的知识，是精确性的知识。知识，是精确性的知识。n 不确定性知识：具有不精确、不完全及模糊性等不确定性知识：具有不精确、不完全及模糊性等特性的知识。特性的知识。82.1.4 知识的表示知识的表示o 知识表示（知识表示（Knowledge Representation）:将人类将人类知识形式化或者模型化。知识形式化或者模型化。o 知识表示是对知识的一种描述，或者说是一组约定，知识表示是对知识的一

6、种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。一种计算机可以接受的用于描述知识的数据结构。9第第2章章 知识表示知识表示o 知识与知识表示的概念知识与知识表示的概念o 状态空间表示法状态空间表示法o 问题归约及与或图表示法问题归约及与或图表示法o 谓词逻辑表示法谓词逻辑表示法o 产生式表示法产生式表示法o 语义网络表示法语义网络表示法2.2 状态空间表示法状态空间表示法o 问题求解技术主要是两个方面问题求解技术主要是两个方面：n问题的表示问题的表示：同一问题有多种不同的表示：同一问题有多种不同的表示n求解的方法求解的方法* *1 1：许多问题求解方法采用试探搜索方法许多

7、问题求解方法采用试探搜索方法o 状态空间法状态空间法：基于解答空间的问题表示和求解方法* *2 2n状态（状态（statestate）n算符（算符（operatoroperator）n状态空间状态空间10112.2 状态空间表示法状态空间表示法定义 :o 状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下： 式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。122.2 状态空间表示法状态空间表示法132.2 状态空间表示法状态空间表示法o 给定每个变量的一组值就得到一个具体的状态，如 Qk=q0k，q1k，. ，qnkT 它

8、只是问题所有可能状态的罗列，还必须描述这些状态之间的可能变化。o 所谓操作，或称为算子是引起状态中的某分量发生改变，从而使问题由一个具体状态A变化为另一具体状态B的作用。142.2 状态空间表示法状态空间表示法o 算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。o 要完成某个问题的状态描述问题的状态描述，必须确定三件事：n 1.该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述；n 2.操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；n 3.目标状态描述的特性。目标状态描述的特性。o

9、问题的状态空间(state space)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S(初始状态S0S)、操作符集合F以及目标状态集合G(GS)。可把状态空间记为三元状态(S，F，G)。o 状态空间可用有向图来表示152.2 状态空间表示法状态空间表示法162.2 状态空间表示法状态空间表示法o 状态空间的一个解 使一个有限的操作算子序列，它使初始状态转化为目标状态：S0-f1-S1-f2-.fk-G 17N个传教士，N个野人，一条船，可同时乘坐k个人乘渡。传教士为安全起见，应如何规定摆渡方案，使得任何时刻，当传教士与野人在同一地点(河两岸以及

10、船上)时，野人数目总是不超过传教士的数目。传教士与野人均可摆渡。例：传教士与野人问题（例：传教士与野人问题（M-CM-C问题）：问题）：以以N=3(N=3(传教士或野人数传教士或野人数) )，k=2(k=2(每条船的载人数每条船的载人数) )为例求解。为例求解。求解过程如下求解过程如下：1. 1.状态描述状态描述用用(m, c, b)表示表示左岸左岸传教士人数传教士人数m、野人人数、野人人数c和船的状态和船的状态b（b=0无船，无船，b=1有船）：有船）：0m, c3, b 0, 1。2.2.操作描述操作描述 (1) IF (m, c, 1) THEN (m-1, c, 0) (2) IF (

11、m, c, 0) THEN (m+1, c, 1) (3) IF (m, c, 1) THEN (m, c-1, 0) (4) IF (m, c, 0) THEN (m, c+1, 1) (5) IF (m, c, 1) THEN (m-1, c-1, 0) (6) IF (m, c, 0) THEN (m+1,c+1,1) (7) IF (m, c, 1) THEN (m-2, c, 0) (8) IF (m, c, 0) THEN (m+2, c, 1) (9) IF (m, c, 1) THEN (m, c-2, 0) (10)IF (m, c, 0) THEN (m, c+2, 1)3

12、.3.初始状态初始状态 ： ( (3,3,13,3,1) )4.4.结束状态：结束状态： （0,0,00,0,0）19第第2章章 知识表示知识表示o 知识与知识表示的概念知识与知识表示的概念o 状态空间表示法状态空间表示法o 问题归约及与或图表示法问题归约及与或图表示法o 谓词逻辑表示法谓词逻辑表示法o 产生式表示法产生式表示法o 语义网络表示法语义网络表示法202.3.1 2.3.1 问问题归约法题归约法 o 问题归约(problem reduction)是另一种问题描述与求解方法。n 先把问题分解为子问题和子先把问题分解为子问题和子-子问题，然后解决较小的问子问题，然后解决较小的问题。题。

13、n 对该问题的某个具体子集的解答就意味着对原始问题的对该问题的某个具体子集的解答就意味着对原始问题的一个解答。一个解答。21 问题归约描述问题归约描述o 问题归约表示的组成部分：n 一个初始问题描述；一个初始问题描述；n 一套把问题变换为子问题的操作符；一套把问题变换为子问题的操作符；n 一套本原问题描述。一套本原问题描述。o 其中的每一个问题是不证明的，自然成立的，如公理、已知其中的每一个问题是不证明的，自然成立的，如公理、已知的实事等（本原问题集）的实事等（本原问题集）o 问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本

14、原问题集合。22梵塔难题梵塔难题 有3个柱子(1，2和3)和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。23梵塔难题梵塔难题 解题过程：将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。只有在移开圆盘A和B之后，才能移动圆盘C；而

15、且圆盘A和B最好不要移至柱子3就不能把圆盘C移至柱子3。因此，首先应该把圆盘A和B移到柱子2上。然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。将原始难题归约（简化）为下列子难题：移动圆盘A和B至柱子2的双圆盘难题，如图(a)所示。24梵塔难题梵塔难题o 把原始难题归约（简化）为以下三个子难题： n 移动圆盘移动圆盘A和和B至柱子至柱子2的双圆盘难题；如图的双圆盘难题；如图(a)所示所示n 移动圆盘移动圆盘C至柱子至柱子3的单圆盘难题的单圆盘难题 ；如图；如图(b)所示所示n 移动圆盘移动圆盘A和和B至柱子至柱子3双圆盘难题；如图双圆盘难题；如图(c)所示所示2

16、5梵塔难题梵塔难题图 2.7 梵塔问题解答(a)图 2.8 梵塔问题解答(b)图 2.9 梵塔问题解答(c)26梵塔难题梵塔难题o梵塔问题归约图：子问题2可作为本原问题考虑，因为它的解只包含一步移动。应用一系列相似的推理，子问题1和子问题3也可被归约为本原问题，如图2.10所示。这种图式结构，叫做与或图(AND/OR graph)。它能有效地说明如何由问题归约法求得问题的解答。 图 2.10 梵塔问题归约图27问题归约法问题归约法o 把一个问题描述变换为一个归约或后继问题描述的集合，这是由问题归约算符进行的。变换所得所有后继问题的解就意味着父辈问题的一个解。o 所有问题归约的目的是最终产生具有

17、明显解答的本原问题。这些问题可能是能够由状态空间搜索中走动一步来解决的问题，或者可能是别的具有已知解答的更复杂的问题。282. 2. 与或图表示与或图表示 o一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。如下图所示:图 2.13 子问题集合图 2.14 与或图29o 一些关于与或图的术语：n 父节点父节点、子（后继）节点子（后继）节点、弧线弧线、起始节点起始节点。n 终叶节点终叶节点：对应于原问题的本原节点。：对应于原问题的本原节点。n 或节点或节点：只要解决某个问题就可解决其父辈问题的节点：只要解决某个问题就可解决其父辈问题的节点集

18、合，如（集合，如（M，N，H）。）。n 与节点与节点：只有解决所有子问题，才能解决其父辈问题的：只有解决所有子问题，才能解决其父辈问题的节点集合，如（节点集合，如（B,C)和（和（D,E,F）各个结点之间用一端小）各个结点之间用一端小圆弧连接标记。圆弧连接标记。 o 与或图：由与节点及或节点组成的结构图。30o 可解节点的一般定义n (1) 终叶节点是可解节点终叶节点是可解节点(因为它们与本原问题相关连因为它们与本原问题相关连)。n (2) 如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只要当其，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可后继节点至少有

19、一个是可解的时，此非终叶节点才是可解的。解的。n (3) 如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只要当其，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。后继节点全部为可解时，此非终叶节点才是可解的。31o 不可解节点的一般定义:n (1) 没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。n (2) 如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只有当其，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。全部后裔为不可解时，此非终叶节点才是不可解的。n (3) 如果某个非终叶节点含有如果某个非终叶节点

20、含有与后继节点与后继节点，那么只要当其，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解后裔至少有一个为不可解时，此非终叶节点才是不可解的。的。32图图2.15 2.15 中，终叶节点用字母中，终叶节点用字母t t表示，有解节点用小原点表示，而解图用粗线分支表示。表示，有解节点用小原点表示，而解图用粗线分支表示。 图 2.15 与或图例子33与或图构成规则与或图构成规则 (1) 与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2) 对应于本原问题的节点，叫做终叶节点，它没有后裔。(3) 对于把算符应用于问题A的每种可能情况，都把问题变换为一个

21、子问题集合；有向弧线自A 指向后继节点表示所求得的子问题集合。(4) 一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。(5) 在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。 因此，代表子问题集合的中间或节点可以被略去，如右图所示。图 2.16 与或树34第第2章章 知识表示知识表示o 知识与知识表示的概念知识与知识表示的概念o 状态空间表示法状态空间表示法o 问题归约

22、及与或图表示法问题归约及与或图表示法o 谓词逻辑表示法谓词逻辑表示法o 产生式表示法产生式表示法o 语义网络表示法语义网络表示法352.2 谓词逻辑表示法谓词逻辑表示法362.2.1 命题命题太阳从西太阳从西边出来。边出来。372.2.2 谓词谓词382.2.2 谓词谓词392.2.3 402.2.3 谓词公式412.2.3 谓词公式422.2.3 谓词公式432.2.3 谓词公式442.2.3 谓词公式452.2.3 谓词公式462.2.4 谓词公式的性质472.2.4 谓词公式的性质482.2.4 谓词公式的性质49502.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法512.2.5 谓

23、词逻辑知识表示方法谓词逻辑知识表示方法52 例例2 有下列知识：有下列知识： 刘欢比他父亲出名。刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程序。高扬是计算机系的一名学生，但他不喜欢编程序。人人爱劳动。人人爱劳动。 为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词：Bigger(x,y): x 比比 y 出名。出名。Computer(x): x 是计算机系的学生。是计算机系的学生。Like(x,y): x 喜欢喜欢 y 。Love(x,y): x 热爱热爱 y。Man(x): x 是人。是人。然后用谓词公式把上述知识表示为：然后用谓词公式把

24、上述知识表示为：Bigger（Liuhong , father(Liuhong)Computer(Gaoyang) Like(Gaoyang , programing) ( x) (Man(x) Love(x, labour)2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法53例例3 3 设有下列知识设有下列知识自然数都是大于零的整数所有整数不是偶数就是奇数偶数除以2是整数首先定义谓词如下：首先定义谓词如下：n(x):x是自然数I(x):x是整数E(x):x是偶数O(x):x是奇数GZ(x):x大于零另外用函数另外用函数S(x)S(x)表示表示x x除以除以2.2.此时，上述知识可用谓词公

25、式分别表示为：此时，上述知识可用谓词公式分别表示为：(x)（n(x)GZ(x)I(x)）(x) (I(x)E(x) O(x)(x) (E(x)I(s(x)2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法54例例. . 设在房内设在房内c c处有一机器人，在处有一机器人，在a a及及b b处各有一张桌子，处各有一张桌子，a a桌上有一个盒子，为了桌上有一个盒子，为了让机器人从让机器人从c c处出发把盒子从处出发把盒子从a a处拿到处拿到b b处的桌上，然后再回到处的桌上，然后再回到c c处，需要制定处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。相应的行动规划。下面用一阶

26、谓词逻辑描述机器人的行动过程。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。cab设相关谓词的定义如下：设相关谓词的定义如下： table(x):xtable(x):x是桌子是桌子 empty(y):yempty(y):y手中是空的手中是空的 at(yat(y，z)z)：y y在在z z的附近的附近 holds(y,w):yholds(y,w):y拿着拿着w w on(w,x):w on(w,x):w在在x x的上面的上面 其中，其中，x x的个体域是的个体域是a,b; a,b; y y的个体域是的个体域是robot; robot; z z的个体域是的个体域是a,b,c;a,b,

27、c; w w的个体域是的个体域是boxbox2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法55问题的初始状态是：问题的初始状态是：at(robot,c)empty(robot)on(box,a)table(a)table(b)问题的目标状态是：问题的目标状态是：at(robot,c) empty(robot)on(box,b)table(a)table(b)机器人的目标是把问题的初始状态转化为目标状态，其间它必须完成一机器人的目标是把问题的初始状态转化为目标状态，其间它必须完成一系列的操作。系列的操作。cab2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法56操作一般可以分为操作一般

28、可以分为条件条件和和动作动作两部分。两部分。 条件可以很容易的用谓词公式表示， 动作可以通过动作前后的状态变化表示出来，即只要指出动作后应从动作前的状态中删去和增加什么谓词就描述了相应的动作。机器人为了把盒子从机器人为了把盒子从a处拿到处拿到b处，应执行如下三个操作：处，应执行如下三个操作：goto(x,y):从x处走到y处；pick_up(x):在x处拿起盒子；set_done(x):在x处放下盒子。这三个操作分别用条件和动作表示如下：这三个操作分别用条件和动作表示如下：1. Goto(x,y) 条件：at(robot,x) 动作 删除：at(robot,x)增加：at(robot,y)2.

29、 Pick_up(x) 条件：on(box,x)table(x) empty(robot) at(robot,x) 动作 删除：empty(robot)on(box,x)增加: holds(robot,box)2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法573. Set_down(x) 条件：at(robot,x)table(x)holds(robot,box)动作 删除：holds(robot,box)增加：empty(robot)on(box,x)操作步骤：操作步骤：机器人在执行每一个操作前，总要先检查当前状态是否可使所要求的条件得到满足。若能满足，就执行相应的操作，否则就检查下一

30、个操作所要求的条件。所谓检查当前状态是否满足所要求的条件，其实是一个定理证明的过程，即证明当前状态是否蕴含操作所要求的条件，若蕴含表示当前所要求的条件得到了满足。机器人行动规划问题的求解过程如下：(其中，在检查条件的满足性时要进行变量的代换。)2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法58At(robot,c)Empty(robot)状态状态1(初始状态初始状态)On(box,a) 用用c代换代换xTable(a) 用用a代换代换yTable(b) goto(x,y)At(robot,a)Empty(robot)状态状态2On(box,a) 用用a代换代换xTable(a)Table

31、(b) pick-up(x)At(robot,a)Hold(robot,box)状态状态3Table(a) 用用a代换代换xTable(b) 用用b代换代换y goto(x,y) At(robot,b)Hold(robot,box)状态状态4Table(a) 用用b代换代换xTable(b) setdown(x) At(robot,b)empty(robot) 状态状态5on(box,b) 用用b代换代换xTable(a) 用用c代换代换yTable(b) goto(x,y)At(robot,c)empty(robot) 状态状态6on(box,b) (目标状态目标状态)Table(a) Ta

32、ble(b)cab2.2.5 谓词逻辑知识表示方法谓词逻辑知识表示方法592.2.6 谓词逻辑知识表示方法的特点谓词逻辑知识表示方法的特点60第2章 知识表示o 知识与知识表示的概念知识与知识表示的概念o 状态空间表示法状态空间表示法o 问题归约及与或图表示法问题归约及与或图表示法o 谓词逻辑表示法谓词逻辑表示法o 产生式表示法产生式表示法o 语义网络表示法语义网络表示法612.3 产生式产生式622.3.1 产生式产生式632.3.1 产生式产生式642.3.1 产生式产生式652.3.1 产生式产生式662.3.1 产生式产生式672.3.2 产生式系统产生式系统682.3.2 产生式系统

33、产生式系统692.3.2 产生式系统产生式系统702.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统712.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统722.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统732.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统742.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统752.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统76演绎型演绎型(正向正向)产生式系统产生式系统猎豹猎豹深褐色毛发深褐色毛发有花斑点有花斑点食肉动物食肉动物食肉食肉哺乳动

34、物哺乳动物外形特征外形特征有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼R3R2R1深褐色毛发深褐色毛发有花斑点有花斑点有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼推理方向：推理方向： 事实事实 结论结论77正向推理的产生式系统正向推理的产生式系统算法中的符号：算法中的符号： DB: 存放事实和中间结果的事实库事实库； KB: 存放知识的规则库规则库； RS: 当前所有触发规则触发规则构成的冲突集合冲突集合。 78正向推理的产生式系统正向推理的产生式系统初始事实放入事实库 DBDBDB DB 中有目标？KB中有适用适用规则？匹配，将所有触发规则放入冲突集RSRS RS 为

35、空？成功，退出成功，退出失败，退出失败，退出用户要补充新事实？ 新事实加入事实库 DBDB是否是是否是否否79正向推理的产生式系统正向推理的产生式系统按规定的冲突解决策略从 RS 中选择一条规则执行。执行结果加入事实库 DBAB80逆向推理的产生式系统逆向推理的产生式系统o 特点特点 - 目标驱动：目标驱动：n 从假设的待证目标出发，逆向地运用规则，求证所有支持目标所需的条件是否成立。n 被逆向使用的规则称为B规则。 例：例： 假设待证目标：假设待证目标： G G ； 事实证据库：事实证据库： 规则集：规则集： R1: R1: ifif B B and C and C thenthen G G

36、, , R2: R2: ifif D D thenthen B B, , 推理后事实证据库：推理后事实证据库： B B,C ,C ； C,C,D D ；81逆向推理的产生式系统实例（逆向推理的产生式系统实例（1）o 动物识别产生式系统动物识别产生式系统: G = “ A是猎豹？是猎豹？”n 已有知识（规则库）：R1： IF X 是食肉动物 X 毛发是深褐色 X 有花斑点 THEN X 是猎豹。R2： IF ( X 是哺乳动物 ) ( X 食肉 ) ( X 有尖利的牙齿 X 有爪子 X 有前视眼 ) THEN X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物u 已知事实（事实库

37、）：已知事实（事实库）： A A有毛发；有毛发； A A有尖利的牙齿；有尖利的牙齿； A A有爪子；有爪子； A A有前视眼；有前视眼； A A毛发是深褐色；毛发是深褐色； A A有花斑点；有花斑点； 82推理方向：推理方向： 目标目标 事实事实逆向推理的产生式系统实例（逆向推理的产生式系统实例（2）猎豹猎豹有花斑点有花斑点食肉动物食肉动物食肉食肉哺乳动物哺乳动物外形特征外形特征有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼R3R2R1深褐色毛发深褐色毛发深褐色毛发深褐色毛发有花斑点有花斑点有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼83逆向推理的产生式系统逆向推理的产生

38、式系统算法中的符号：算法中的符号： DB: 存放最终事实和中间证据的事实证据库事实证据库； KB: 存放知识的规则库规则库； RS: 当前所有触发规则触发规则构成的冲突集合冲突集合。 84逆向推理的产生式系统逆向推理的产生式系统假设待证目标DBDB有支持目标的事实KB中有支持目标的规则匹配，将所有触发规则放入冲突集RSRS目标成立，退出目标成立，退出事实支持假设目标，事实送 DBDB 用户补充新事实？ 询问用户是否是否是否AB 目标不成立目标不成立, ,退出退出 RS 为空？是否85A选择规则的一个前提条件作为新的待证目标。B从 RS 中选择一条触发规则逆向推理的产生式系统逆向推理的产生式系统

39、86正（逆）向产生式系统的比较正（逆）向产生式系统的比较特点特点正向推理正向推理逆向推理逆向推理推理驱动方式推理驱动方式数据驱动目标驱动优点优点算法简单，易于实现搜索目的性强，推理效率高 缺点缺点1、搜索目的性弱，可能求解出多个无关的结论；2、 匹配时，要遍历整个规则库，推理效率低。1、确定目标的时候，具有盲目性，可能产生假目标2、当规则的后件是操作而非断言时，即反应型系统，不宜使用此法 用途用途主要用于已知初始数据，不知目标的推理；或是解解空间空间大的一类推理。主要用于结论单一或已知目标求证的一类推理。应用应用监控、预测、规划、设计等选择、分类、故障诊断等872.3.4 产生式表示的特点产生

40、式表示的特点88第第2章章 知识表示知识表示o 知识与知识表示的概念知识与知识表示的概念o 状态空间表示法状态空间表示法o 问题归约及与或图表示法问题归约及与或图表示法o 谓词逻辑表示法谓词逻辑表示法o 产生式表示法产生式表示法o 语义网络表示法语义网络表示法891. 概述概述 语义网络语义网络1968年由年由J.R.Quillian提出，开始是作为人类联想记忆的一个显提出，开始是作为人类联想记忆的一个显式心理学模型提出，随后在式心理学模型提出，随后在AI中用于自然语言理解，表示命题信息（具有中用于自然语言理解，表示命题信息（具有逻辑真的事实）。目前语义网络已广泛应用于人工智能的许多领域，是一

41、逻辑真的事实）。目前语义网络已广泛应用于人工智能的许多领域，是一种表达能力强而且灵活的知识表达方式。种表达能力强而且灵活的知识表达方式。 语义网络是通过概念及其语义关系来表示知识的一种网络图语义网络是通过概念及其语义关系来表示知识的一种网络图 ； 从图论的观点看，他们就是一个从图论的观点看，他们就是一个“带标识的有向图带标识的有向图” ； 语义网络由节点和节点间的弧组成；语义网络由节点和节点间的弧组成； 节点表示各种事物，概念，情况，属性，动作，状况等；节点表示各种事物，概念，情况，属性，动作，状况等； 弧表示各种语义联系，指明他所连接的节点间的各种语义联系弧表示各种语义联系，指明他所连接的节

42、点间的各种语义联系； 节点和弧都必须带有标识，以便区分各种不同对象以及对象间的各种不同语义联系；节点和弧都必须带有标识，以便区分各种不同对象以及对象间的各种不同语义联系； 每个节点可以带有若干属性，一般用框架或元组表示；每个节点可以带有若干属性，一般用框架或元组表示； 节点还可以是一个语义子网络，形成一个多层次的嵌套结构。节点还可以是一个语义子网络，形成一个多层次的嵌套结构。 知识的语义网络表示方法知识的语义网络表示方法90 一个最简单的语义网络是如下一个三元组：一个最简单的语义网络是如下一个三元组： （节点（节点1，弧，节点，弧，节点2） 它可用图表示，称为一个基本网元。它可用图表示，称为一

43、个基本网元。 其中，其中，A,BA,B分别代表两个节点；分别代表两个节点；R RABAB表示表示A A与与B B之间的语某种语义联系。之间的语某种语义联系。 例如：例如： 其中，在猎狗与狗之间的语义关系其中，在猎狗与狗之间的语义关系”是一种是一种”具体的指出了猎狗与狗的语义关系，具体的指出了猎狗与狗的语义关系，即猎狗是狗的一种，两者之间存在类属关系。即猎狗是狗的一种，两者之间存在类属关系。 这里，弧线的方向是有意义的，需要根据事务间的关系确定。例如在表示类属关系这里，弧线的方向是有意义的，需要根据事务间的关系确定。例如在表示类属关系时，箭头所指的节点代表上层概念，而箭尾的节点代表下层概念。时，

44、箭头所指的节点代表上层概念，而箭尾的节点代表下层概念。ABRAB猎狗猎狗狗狗是一种是一种91o常用的语义联系常用的语义联系 语义联系反映了节点间的语义关系。下面列出一些常用的语义联系，用作参考：语义联系反映了节点间的语义关系。下面列出一些常用的语义联系，用作参考：1 1A-Member-ofA-Member-of联系联系它表示个体与集体之间的关系，它们之间有属性继承权和属性更改权。它表示个体与集体之间的关系，它们之间有属性继承权和属性更改权。 例如：张三是工会会员。例如：张三是工会会员。张三张三工会工会A-Member-ofA-Member-of2 2Composed Composed ofo

45、f联系联系 它表示构成联系，是一种一对多的联系，被它连接的节点不具有属性继它表示构成联系，是一种一对多的联系，被它连接的节点不具有属性继承性。承性。 例如：整数由正整数、负整数及零组成。例如：整数由正整数、负整数及零组成。整数整数与与正整数正整数零零负整数负整数ComposedComposedofof923.have 3.have 联系联系 它表示属性或事物的占有关系。它表示属性或事物的占有关系。鸟鸟翅膀翅膀havehave4.Before, after, at 4.Before, after, at 联系联系 它们是用来表示事件之间的时间先后关系，其中它们是用来表示事件之间的时间先后关系，其

46、中,before,before表示一个事件在表示一个事件在 另一个事件之前发生，另一个事件之前发生，afterafter表示一个事件在另一个事件之后发生，表示一个事件在另一个事件之后发生， atat表示某一事件发生的时间表示某一事件发生的时间唐朝唐朝宋朝宋朝beforebefore5.located-on 5.located-on 联系联系 这些联系用来表示事物间的位置关系。这些联系用来表示事物间的位置关系。6.similar-to6.similar-to，near-to near-to 联系联系 这些语义联系用来表示事物间的相似和接近的联系。这些语义联系用来表示事物间的相似和接近的联系。书书

47、桌子桌子located-onlocated-on猫猫虎虎similar-tosimilar-to此外，此外，ISA、AKO、Infer灯也可用作语义网络。灯也可用作语义网络。93当把多个基本网元用相应语义联系关联在一起时，就可得到一个语义网络。当把多个基本网元用相应语义联系关联在一起时，就可得到一个语义网络。例如：由三个基本网元，经合并后可得到一个语义网络。例如：由三个基本网元，经合并后可得到一个语义网络。 A B B C A CRABRBCRAC A B CRABRBCRAC := | Merge (，） := := （，） := : ） := | ） 其中，其中，Merge()是一个合并过

48、程，它把括弧中的所有基本网元关联在一起，即把相是一个合并过程，它把括弧中的所有基本网元关联在一起，即把相 同的节点合并为一个，从而构成一个语义网络。同的节点合并为一个，从而构成一个语义网络。942. 知识的语义网络表示知识的语义网络表示 语义网络可以表示事实性的知识，也可以表示有关事实性知识之间的复杂联系。语义网络可以表示事实性的知识，也可以表示有关事实性知识之间的复杂联系。 (1) 用语义网络表示事实用语义网络表示事实 ：表示节点：表示节点 ：表示狐：表示狐 ：该节点描述对象的属性：该节点描述对象的属性 该语义网络表示了猎狗是一种狗，且进一步指出狗是一种动物，并且分该语义网络表示了猎狗是一种

49、狗，且进一步指出狗是一种动物，并且分别指出他们所具有的属性。（做这些只要在图中增加一个节点和一条弧，并别指出他们所具有的属性。（做这些只要在图中增加一个节点和一条弧，并对每个节点附上相应的属性就可以了。）对每个节点附上相应的属性就可以了。） 语义网络具有属性继承的特性，即下层概念可以继承上层概念的属性，这语义网络具有属性继承的特性，即下层概念可以继承上层概念的属性，这样就可以在下层概念中只列出它独有的属性。样就可以在下层概念中只列出它独有的属性。 另外下层概念还可以对其上层概念的属性作进一步的细化，补充，变异，另外下层概念还可以对其上层概念的属性作进一步的细化，补充，变异，使之能更准确的反映下

50、层概念的特征。使之能更准确的反映下层概念的特征。 猎狗猎狗 狗狗 动物动物吃肉吃肉 身上有毛身上有毛 有生命有生命能狩猎能狩猎 有尾巴有尾巴 能运动能运动跑得快跑得快 会会吃吃95 在一些稍复杂的事实性知识中，经常会用到像在一些稍复杂的事实性知识中，经常会用到像“并且并且“及及“或者或者“这样的连接词。这样的连接词。（用谓词公式表示时，可用合取符号和析取符号把他们表示出来），语义网络可以通过（用谓词公式表示时，可用合取符号和析取符号把他们表示出来），语义网络可以通过增设增设合取节点合取节点及及析取节点析取节点来表示。来表示。例如：与会者有男，有女，有年老的，例如：与会者有男，有女，有年老的，

51、有年青的。有年青的。 其语义网络为：其语义网络为： （其中，（其中，A,B,C,DA,B,C,D分别分别 代表四种不同情况的代表四种不同情况的 与会者）与会者） 人人 与会者与会者 A B C D 与与或或或或 男男 女女 年老年老 年轻年轻状态状态状态状态状态状态状态状态部分部分部分部分部分部分部分部分是是96 上述例子中的节点都是用来表示一个事物或是一个具体概念的，其实，节点还可上述例子中的节点都是用来表示一个事物或是一个具体概念的，其实，节点还可以表示某一情况，某一事件或者某个动作。此时，节点可以有一组向外的弧，用以表示某一情况，某一事件或者某个动作。此时，节点可以有一组向外的弧，用于指

52、出不同的情况，例如当用节点表示某一动作时，向外的弧可用来指出动作的于指出不同的情况，例如当用节点表示某一动作时，向外的弧可用来指出动作的主体及客体。主体及客体。 例例1 1： 有如下事实：有如下事实： 张山给肖红一本书张山给肖红一本书 ( (可把张山给肖红一本书作为一个事件，并在语义网络中增设一个可把张山给肖红一本书作为一个事件，并在语义网络中增设一个“事件事件”节点节点) )一本书一本书 给予事件给予事件 张山张山 肖红肖红 给给客体客体2 2客体客体1 1动作动作主体主体97小信使小信使鸽子鸽子鸟鸟占有占有窝窝鸟窝鸟窝春天春天时间时间秋天秋天情况情况是一只是一只占有者占有者是一种是一种是一

53、种是一种占有物占有物开始于开始于结束于结束于是是是是 其中，其中，“占有占有” 为一个动作节点，通过它，不仅可以描述占有为一个动作节点，通过它，不仅可以描述占有“窝窝”，还可描述占有，还可描述占有“窝窝”的时间。的时间。例例2：有下述事实：有下述事实： “小信使小信使”这只鸽子从春天到秋天占有一个窝。这只鸽子从春天到秋天占有一个窝。98 (2) 用语义网络表示有关事实间的关系用语义网络表示有关事实间的关系 语义网络可以描述事物间多种复杂的语义关系，下面是常用的几种：语义网络可以描述事物间多种复杂的语义关系，下面是常用的几种： 指事物间的类属关系。如指事物间的类属关系。如“是一种是一种”等。等。

54、动物动物 鱼鱼 八哥八哥 鸵鸟鸵鸟鲨鱼鲨鱼草鱼草鱼鸟鸟 会学人语会学人语 善鸣善鸣 不会飞不会飞 善奔走善奔走 有牙有牙 吃肉吃肉是一种是一种是一种是一种是一种是一种是一种是一种是一种是一种是一种是一种吃吃生活在水中生活在水中会游泳会游泳能运动能运动会吃会吃会飞会飞有羽毛有羽毛 下层概念节点除了可继承，细化，补充上层概念节点的属性外，还出现了下层概念节点除了可继承，细化，补充上层概念节点的属性外，还出现了变异变异的情况：的情况：鸟是鸵鸟的上层概念节点，其属性是有羽毛，会飞，但鸵鸟只是继承了有羽毛这一属性，把鸟是鸵鸟的上层概念节点，其属性是有羽毛，会飞，但鸵鸟只是继承了有羽毛这一属性，把鸟的会飞

55、鸟的会飞变异变异为不会飞，善奔走。为不会飞，善奔走。 99如果下层概念是其上层概念的一方面或者一个部分，则称它们如果下层概念是其上层概念的一方面或者一个部分，则称它们 是聚集关系。是聚集关系。教学教学教师教师课程课程学生学生部分部分部分部分部分部分如果一个概念可由另一个概念推出，则称它们之间存在推论关系。如果一个概念可由另一个概念推出，则称它们之间存在推论关系。需进食需进食饥饿饥饿推出推出思远公司思远公司朱雀大街朱雀大街位于位于100在语义网络中，一条弧只能从一个节点指向另一个节点，适合在语义网络中，一条弧只能从一个节点指向另一个节点，适合 于表示一个二元关系。但在许多情况下需要用一种关系把几

56、个于表示一个二元关系。但在许多情况下需要用一种关系把几个 事物联系起来。例如对于如下事实：事物联系起来。例如对于如下事实： 郑州位于西安和北京之间。郑州位于西安和北京之间。 为了在语义网络中描述多元关系，可以用节点来表示关系。为了在语义网络中描述多元关系，可以用节点来表示关系。位置关系位置关系郑州郑州北京北京西安西安居居中中边界边界_1边界边界_2101(3) 用语义网络表示比较复杂的知识用语义网络表示比较复杂的知识 设有如下两个事实：张三的自行车是飞鸽牌，黑色，设有如下两个事实：张三的自行车是飞鸽牌，黑色，2828型型 李四的自行车是金狮牌，红色，李四的自行车是金狮牌，红色，2626型型 将

57、其用语义网络描述出来。将其用语义网络描述出来。 分析分析 如写成两个网络，很容易，但对知识的利用带来不便，如写成两个网络，很容易，但对知识的利用带来不便， 如何写成一个呢？如何写成一个呢？ 分析事实发现，它们都是关于自行车的，因此只要把自行车作为分析事实发现，它们都是关于自行车的，因此只要把自行车作为 一个通用概念用一个节点表示，而把张三李四的自行车作为他们一个通用概念用一个节点表示，而把张三李四的自行车作为他们 的实例。这样，就很容易用一个语义网络把它们表示出来，当要的实例。这样，就很容易用一个语义网络把它们表示出来，当要 寻找有关自行车的信息时，只要首先找到自行车这个节点就可以寻找有关自行车的信息时，只要首先找到自行车这个节点就可以 了。了。10228型型飞鸽飞鸽自行车自行车1黑色黑色自行车自行车交通工具交通工具自行车自行车2红色红色26型型金狮金狮张三张三李四李四人人是是是是所有者所有者所有者所有者车型车型车型车型车名车名车名车名颜色颜色颜色颜色是一种是一种是是是是103 用语义网络表示较复杂的知识时，往往牵涉到对量