工智能及专家系统敖志刚第2章知识表示

第第2章章 知识表示知识表示 敖志刚敖志刚 编制编制 第第2章章 知识表示知识表示 敖志刚敖志刚 编制编制 第第2章章 知识表示知识表示 第2章 知识表示 21 知识与知识表示的概念知识与知识表示的概念 211 知识知识 212 知识表示知识表示 22 状态空间表示法状态空间表示法 221 状态空间表示法的基本概念和策略状态空间表示法的基本概念和策略 222 状态空间表示法示例状态空间表示法示例 23 与与/或图知识表示或图知识表示 231 与与/或图知识表示的概念或图知识表示的概念 232 与与/或图表示示例或图表示示例第第2章章 知识表示知识表示 第2章 知识表示 24 产生式知识表示产生式知识表示 241 产生式的结构和组成产生式的结构和组成 242 产生式系统的分类产生式系统的分类 243 产生式系统的性能及其应用产生式系统的性能及其应用 25 语义网络语义网络 251 语义网络的概念语义网络的概念 252 语义网络的推理语义网络的推理 253 语义网络表示法的特征语义网络表示法的特征 26 框架表示法框架表示法 261 框架表示法的概念与设计框架表示法的概念与设计 262 框架的基本结构和描述框架的基本结构和描述 263 框架系统框架系统 264 框架系统的推理和求解过程框架系统的推理和求解过程 264 五种知识表示方法的比较五种知识表示方法的比较 第第2章章 知识表示知识表示 21 知识与知识表示的概念2.1.1 知识1. 知识的概念知识的概念 知识是人们对客观事物及其是人们对客观事物及其规律的认识，包括，包括对事物的现象、本质、属性、状态、关系、联对事物的现象、本质、属性、状态、关系、联系和运动等的认识；是解决问题的步骤、操作、系和运动等的认识；是解决问题的步骤、操作、规则、过程、技术、技巧、战术、战略、计谋、规则、过程、技术、技巧、战术、战略、计谋、策略。知识是经过消减、加工、整理、解释、策略。知识是经过消减、加工、整理、解释、挑选、改造、选择和转换的信息和数据，是由挑选、改造、选择和转换的信息和数据，是由特定领域的事实、信念、描述、关系、启发式特定领域的事实、信念、描述、关系、启发式和过程组合起来的。和过程组合起来的。第第2章章 知识表示知识表示 2. 知识的分类知识的分类 按知识的作用：叙述型知识、过程型知识、：叙述型知识、过程型知识、控制型知识；控制型知识；按知识的的性质：对象性知识、事件性知识、对象性知识、事件性知识、性能性知识、元知识；性能性知识、元知识； 按知识的作用范围：常识性知识、领域性知常识性知识、领域性知识；识；按知识的层次：表层知识、深层知识；表层知识、深层知识； 按知识的确定性：确定性知识、不确定性知确定性知识、不确定性知识识第第2章章 知识表示知识表示 3. 知识的属性知识的属性 可表示性、可利用性、不确定可表示性、可利用性、不确定性、矛盾性、相容性、真假性、性、矛盾性、相容性、真假性、相对性。相对性。 第第2章章 知识表示知识表示 212 知识表示面向人的面向人的知识表示的概念知识表示的概念 面向人的知识表示可以用是语言、文字、面向人的知识表示可以用是语言、文字、数字、符号、公式、图表、图形、图像等数字、符号、公式、图表、图形、图像等多种形式。这些表示形式是人所能接受、多种形式。这些表示形式是人所能接受、理解和处理的形式。理解和处理的形式。 第第2章章 知识表示知识表示 2. 面向计算机的知识表示的概念面向计算机的知识表示的概念 就是要用某种约定的就是要用某种约定的(外部外部)形式结构来描述形式结构来描述知识，通常用知识，通常用知识的规则符号、形式语言和知识的规则符号、形式语言和网络图等使知识形式化或模型化网络图等使知识形式化或模型化 ，而且这种，而且这种形式结构还要能够转换为机器的内部形式，形式结构还要能够转换为机器的内部形式，在计算机中用合适的形式对问题求解过程中在计算机中用合适的形式对问题求解过程中所需要的各种知识进行组织、存储、检索、所需要的各种知识进行组织、存储、检索、使用、增删、修改、推理和判断；使用、增删、修改、推理和判断；使得计算使得计算机能方便地存储、处理和利用。机能方便地存储、处理和利用。第第2章章 知识表示知识表示 3. 设计知识表示的基本原则设计知识表示的基本原则 可实现性、可理解性、表示能力、可实现性、可理解性、表示能力、可维护性、可利用性、自然性、可可维护性、可利用性、自然性、可组织性组织性第第2章章 知识表示知识表示 4. 知识表示方法的分类知识表示方法的分类 状态空间表示法 基于图的表示法基于图的表示法 与与/或图表示法或图表示法 语义网络表示法语义网络表示法 谓词逻辑表示法谓词逻辑表示法 产生式表示法产生式表示法 特性表示法特性表示法 框架表示法框架表示法知识表示知识表示 功能表示法功能表示法 脚本表示法脚本表示法 过程表示法过程表示法 多层次信息结构表示法多层次信息结构表示法 概念图解表示法概念图解表示法 神经网络表示法神经网络表示法 意识胞表示法意识胞表示法 不精确表示法不精确表示法第第2章章 知识表示知识表示 状态图状态图YXWZSUVT A C D E B节点A是B的前驱弧弧的标记弧T从A指向BB是A的后继第第2章章 知识表示知识表示 与或图示例与或图示例 与节点 或节点dxxxx1122dxxx12dxxx12dxx 11dxxxxxx111212 dxx) 1(xdxdxxx21第第2章章 知识表示知识表示 有关图书馆的一个语义网络 图书馆 建筑物 张三 阅览室 读者 理工大学 单位 大礼堂 校园 钟山 学会 讲英语 公园 开放 阅览 风景美丽 海福巷Owner After Can Near-to Similar-to Can A-Member-of Is-a FetchLocated-underLocated-insideA-Kind-of Is-a A-part-of Have CanLocated-at 语义网络示例语义网络示例 第第2章章 知识表示知识表示 动物识别系统的产生式推理网络R1R2R3R4R5R6R7R8R9R10是食肉类黄褐色有黑条纹有暗斑点 是有蹄类长脖子长腿吃肉 有犬齿有爪眼前视是哺乳类有蹄子反刍食物 产奶有毛虎豹斑马长颈鹿产生式推理网络示例产生式推理网络示例 第第2章章 知识表示知识表示 22 状态空间表示法2.2.1 状态空间表示法的基本概念 状态：各种相关对象的可能的排列、情况、各种相关对象的可能的排列、情况、形势和现状。形势和现状。 表示形式：通常用一组指标、变量或数组通常用一组指标、变量或数组来表示。来表示。 三个共有特征：就是状态、规则和目标。就是状态、规则和目标。 问题的三种状态：开始状态、中间状态和开始状态、中间状态和目标状态。目标状态。第第2章章 知识表示知识表示 知识表示一般步骤知识表示一般步骤: 1 定义一状态空间；定义一状态空间； 2 确定开始状态；确定开始状态； 3 确定目标状态；确定目标状态； 4 规定一组规则；规定一组规则； 5 将非形式的问题描述转换成形将非形式的问题描述转换成形式描述；画出描述问题的状态图；式描述；画出描述问题的状态图； 6 分析问题；分析问题； 7 选择最佳技术去求解待解问题。选择最佳技术去求解待解问题。第第2章章 知识表示知识表示 2.2.2 状态空间表示法示例状态空间表示法示例 例例2-1 水壶问题水壶问题 有两个水壶，一个盛满为有两个水壶，一个盛满为4公斤公斤水，另一个盛满为水，另一个盛满为3公斤水，水壶公斤水，水壶上没有任何度量标记。怎样在能装上没有任何度量标记。怎样在能装4公斤的水壶里恰好只装公斤的水壶里恰好只装2公斤水。公斤水。 第第2章章 知识表示知识表示 定义操作符定义操作符 1 (X，YX4) (4，Y) 把把4公斤的水壶装满。公斤的水壶装满。2 (X，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+Y4YO)(X+Y，O) 把把3公斤水壶中水全部倒入公斤水壶中水全部倒入4公斤水壶。公斤水壶。第第2章章 知识表示知识表示 例例2-2修道士和野人问题修道士和野人问题 在河的左岸有在河的左岸有3个修道士，个修道士，3个野人和个野人和1条船，条船，修道士们想用这条船将所有的人都运过河去，修道士们想用这条船将所有的人都运过河去，但是受到以下条件的限制：但是受到以下条件的限制： 修道士和野人都会划船，但船一次只能装修道士和野人都会划船，但船一次只能装运两个人；运两个人； 修道士的人数必须大于野人数；修道士的人数必须大于野人数； 野人不知道是个骗局。野人不知道是个骗局。 试问修道士如何用这条船将这些人全部都渡试问修道士如何用这条船将这些人全部都渡到河的对岸？到河的对岸？ 第第2章章 知识表示知识表示 表表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 不合法不合法 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 合法合法第第2章章 知识表示知识表示 定义规则定义规则 将一个修道士从左岸运到右岸；将一个修道士从左岸运到右岸； 将一个野人从左岸运到右岸；将一个野人从左岸运到右岸； 将一个修道士和一个野人从左岸运到右岸；将一个修道士和一个野人从左岸运到右岸； 将二个修道士从左岸运到右岸；将二个修道士从左岸运到右岸； 将二个野人从左岸运到右岸；将二个野人从左岸运到右岸； 将一个修道士从右岸运到左岸；将一个修道士从右岸运到左岸； 将一个野人从右岸运到左岸；将一个野人从右岸运到左岸； 将一个修道士和一个野人从右岸运到左岸；将一个修道士和一个野人从右岸运到左岸； 将二个修道士从右岸运到左岸；将二个修道士从右岸运到左岸； 将二个野人从右岸运到左岸；将二个野人从右岸运到左岸；第第2章章 知识表示知识表示 YXWZSUVT A C D E B节点A是B的前驱弧弧的标记弧T从A指向BB是A的后继状态图的概念状态图的概念 第第2章章 知识表示知识表示 331310320220321300311110111011021000010031020221 修道士和野人问题的修道士和野人问题的状态图状态图第第2章章 知识表示知识表示 计算机的表达方法计算机的表达方法 按按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章章 知识表示知识表示 例例2-3 梵塔问题：传说印度的主神梵天做了一个梵梵塔问题：传说印度的主神梵天做了一个梵塔，它是在一块黄铜板上插塔，它是在一块黄铜板上插3根宝面针，其中一根针根宝面针，其中一根针上从上到下按从小到大的顺序串上了上从上到下按从小到大的顺序串上了64个金片。梵个金片。梵天要求僧侣们轮流把金片在三根针之间移来移去，天要求僧侣们轮流把金片在三根针之间移来移去，规定每次只能移动规定每次只能移动1片，且不许大片压到小片上。并片，且不许大片压到小片上。并说如果这说如果这64片金片全部移至另一根针上时，世界就片金片全部移至另一根针上时，世界就会在一声霹雳之中毁灭。会在一声霹雳之中毁灭。 64 1 2 3 1 2 3 1 2 36464第第2章章 知识表示知识表示 梵塔问题的状态图梵塔问题的状态图 113132 22 12 13 33 23 21两片金片的状态图 （111） （311） (211） （321） （231） （221） （331） （121）（131） （223） （332） （123） （323)（232） （132） （133） （313） （212） （122）（333） （222） （233）(213）（113）（112）（312）（322） 三片金片梵塔问题的状态图第第2章章 知识表示知识表示 二金片问题的一种最佳求解过程二金片问题的一种最佳求解过程二金片问题的状态空间图 第第2章章 知识表示知识表示 三金片问题的一种最佳求解过程三金片问题的一种最佳求解过程 1 2 31 2 31 2 3 1 2 31 2 31 2 31 2 31 2 3XYZXYZ第第2章章 知识表示知识表示 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之间的关系就可以用一棵之间的关系就可以用一棵“与树与树”来表示。来表示。第第2章章 知识表示知识表示 与或图示例与或图示例 PP1P2P3P11 P12 P13 P14 P15 P16 P17 P18 图2-9 与/或图 P1 P2 P3 Pn P 图2-7 与树 P1 P2 P3 Pn P 图2-8 或树第第2章章 知识表示知识表示 可解节点可解节点 在与在与/或图中，满足以下三个条件之一或图中，满足以下三个条件之一的节点为可解节点的节点为可解节点: 任何终止节点都是可解节点。任何终止节点都是可解节点。 对对“或或”节点，当其子节点中至少有一节点，当其子节点中至少有一个为可解节点时，则该个为可解节点时，则该“或或”节点就是节点就是可解节点。可解节点。 对对“与与”节点，只有当其子节点全部为节点，只有当其子节点全部为可解节点时，该可解节点时，该“与与”节点才是可解节节点才是可解节点。点。 第第2章章 知识表示知识表示 不可解节点不可解节点 可用类似的方法定义不可解节点可用类似的方法定义不可解节点: 不为终止节点的端节点是不可解节点。不为终止节点的端节点是不可解节点。 对对“或或”节点，若其全部子节点都为节点，若其全部子节点都为不可解节点，则该不可解节点，则该“或或”节点是不可节点是不可解节点。解节点。 对对“与与”节点，只要其子节点中有一节点，只要其子节点中有一个为不可解节点，则该个为不可解节点，则该“与与”节点是节点是不可解节点。不可解节点。第第2章章 知识表示知识表示 与或图表示举例与或图表示举例 例例2-4 试证明两四边形全等问题试证明两四边形全等问题T，如图，如图2-9所示，要所示，要求用与求用与/或图表示。或图表示。 证明证明 现假设：现假设： 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。 第第2章章 知识表示知识表示 两全等四边形两全等四边形 图2-10 两四边形全等问题d2 1 d1 c 2A B C D c d2 1 d1 2A BC D第第2章章 知识表示知识表示 与与/或图表示或图表示 图2-11 证明四边形全等问题的与/或图T14T11T13T12 T T1 T2 E1 E2 E 3T121T122T123T131T132T141T133T142T143T1211T1212T1213第第2章章 知识表示知识表示 示例示例 例例 试求积分试求积分 有两种方法解此积分有两种方法解此积分 1因为因为 ，所以上述积分变为，所以上述积分变为 2上述积分可按下式变换上述积分可按下式变换 上述两种方法可用下列与上述两种方法可用下列与/或图如图或图如图2-11来描述来描述22) 1(12xxxdxxdxdxxxF) 1()(dxxdxxxdxxxdxxxxxxdxxxxxF1112111121112)(222dxxxxxF112)(2第第2章章 知识表示知识表示 与或图表示与或图表示 图2-11 微积分问题的与/或图 与节点 或节点dxxxx1122dxxx12dxxx12dxx 11dxxxxxx111212 dxx) 1(xdxdxxx21第第2章章 知识表示知识表示 示例示例 例例2-5 分火柴游戏，设堆有分火柴游戏，设堆有7根火柴，由根火柴，由Max（我方）和（我方）和Min方（对手）两人轮流来分它方（对手）两人轮流来分它们，要求每次都要把某堆火柴分成不相等的两们，要求每次都要把某堆火柴分成不相等的两部分，最后不能分下去的人为负，对方为胜。部分，最后不能分下去的人为负，对方为胜。如果对方先走，用与如果对方先走，用与/或图知识表示来描述。或图知识表示来描述。 如果如果MIN先走，他有三种选择方法：先走，他有三种选择方法：(6，1)、(5,2)、(4，3)，在，在MIN的每一种选择下，的每一种选择下，MAX又又有两种走法，整个博弈与有两种走法，整个博弈与/或图如图或图如图2-12所示。所示。第第2章章 知识表示知识表示 与或图表示与或图表示 MAX胜MIN胜MIN胜 ( 7 ) (4，3 ) ( 6，1 ) ( 5，2 ) (5，1，1 ) (4，2，1 ) (3，2，2 ) (3，3，1 ) (4,1,1,1 ) (3,2,1,1 ) (2,2,2,1) (3,1,1,1,1 ) (2,2,1,1,1 ) (2,1,1,1,1,1 )MAXMAXMAXMINMINMIN 图2-12 分火柴游戏的与/或图 第第2章章 知识表示知识表示 24 产生式知识表示 产生式产生式(Production)一词最早是由美国数学家波斯一词最早是由美国数学家波斯特特(EPost)于于1943年根据串替换规则提出的一种年根据串替换规则提出的一种称为称为Post机的计算模型。机的计算模型。1954年，年，Markov对对Post的的产生式系统作了改进，提出了产生式系统的控制产生式系统作了改进，提出了产生式系统的控制策略，根据规则的优先级来确定其执行的顺序。策略，根据规则的优先级来确定其执行的顺序。1957年年Chomskey利用一系列产生式规则来描述每利用一系列产生式规则来描述每层文法的语言生成规则。层文法的语言生成规则。1972年，纽厄尔和西蒙年，纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生在研究人类的认知模型中开发了基于规则的产生式系统。目前，产生式表示法已成为人工智能中式系统。目前，产生式表示法已成为人工智能中应用最多的一种知识表示模式。应用最多的一种知识表示模式。第第2章章 知识表示知识表示 241 产生式的结构和组成 产生式的一般形式为产生式的一般形式为“前件前件+后件后件”。前件。前件就是前提，后件是结论或动作就是前提，后件是结论或动作 。 产生式包括各种操作、规则、变换、算子、产生式包括各种操作、规则、变换、算子、函数等等函数等等 产生式表示法可以很容易地描述事实、规产生式表示法可以很容易地描述事实、规则以及它们的不确定性度量。则以及它们的不确定性度量。 规则描述的是事物间的因果关系。其基本规则描述的是事物间的因果关系。其基本形式为形式为:“PQ”或或“IF P THEN Q”， 含义是：含义是：如果前提如果前提P满足，则可推出结论满足，则可推出结论Q或执行或执行Q所规定的操作；所规定的操作； 第第2章章 知识表示知识表示 图表示概念图表示概念 产生式规则R1R2R3 R4 R5 中介事实B、C、 D事实结论A R1 B C D R2 R3 R4 R5 F1 F2 F3 F4 F5 F6 图2-13 产生式推理系统第第2章章 知识表示知识表示 产生式系统示例产生式系统示例例例2-6 一个动物识别系统的产生式如下一个动物识别系统的产生式如下:R1: :若某动物有奶，则它是哺乳动物。若某动物有奶，则它是哺乳动物。R2: 若某动物有毛发，则它是哺乳动物。若某动物有毛发，则它是哺乳动物。R3: 若某动物吃肉，则它是食肉动物。若某动物吃肉，则它是食肉动物。R4: 若某动物有爪且有犬齿且眼视前方，则它是食肉动物。若某动物有爪且有犬齿且眼视前方，则它是食肉动物。R5: 若某动物是哺乳动物且有蹄，则它是有蹄动物。若某动物是哺乳动物且有蹄，则它是有蹄动物。R6: 若某动物是有蹄动物且反刍食物，则它是有蹄动物。若某动物是有蹄动物且反刍食物，则它是有蹄动物。R7: 若某动物是哺乳动物且食肉动物且黄褐色且有黑色条纹，则它是若某动物是哺乳动物且食肉动物且黄褐色且有黑色条纹，则它是老虎。老虎。R8: 若某动物是哺乳动物且食肉动物且黄褐色且有暗斑点，则它是金若某动物是哺乳动物且食肉动物且黄褐色且有暗斑点，则它是金钱豹。钱豹。R9: 若某动物是有蹄动物且有黑色条纹，则它是斑马。若某动物是有蹄动物且有黑色条纹，则它是斑马。R10: 若某动物是有蹄动物且长腿且长脖子且有暗斑点，则它是长颈鹿。若某动物是有蹄动物且长腿且长脖子且有暗斑点，则它是长颈鹿。 第第2章章 知识表示知识表示 图2-14 动物识别系统的产生式推理网络R1R2R3R4R5R6R7R8R9R10是食肉类黄褐色有黑条纹有暗斑点 是有蹄类长脖子长腿吃肉 有犬齿有爪眼前视是哺乳类有蹄子反刍食物 产奶有毛虎豹斑马长颈鹿第第2章章 知识表示知识表示 产生式系统的三个主要部分产生式系统的三个主要部分 控制系统 规则库全局数据库 图2-15 产生式系统的基本结构第第2章章 知识表示知识表示 产生式系统问题求解的基本过程产生式系统问题求解的基本过程: 初始化全局数据库初始化全局数据库,把已知事实送入全局数据库中。把已知事实送入全局数据库中。 检查规则库是否有末使用的规则，若有执行检查规则库是否有末使用的规则，若有执行；否则转；否则转。 检查规则库的末使用规则中是否存在有其前提可与全局数据检查规则库的末使用规则中是否存在有其前提可与全局数据库中已知事实相匹配的规则，若有从中选择一个；否则转库中已知事实相匹配的规则，若有从中选择一个；否则转。 执行当前选中规则，并对该规则作上标记，把执行该规则后执行当前选中规则，并对该规则作上标记，把执行该规则后所得到的结论作为新的事实放入全局数据库；如果该规则的结所得到的结论作为新的事实放入全局数据库；如果该规则的结论是一些操作，则执行这些操作。论是一些操作，则执行这些操作。 检查全局数据库中是否包含了该问题的解，若已包含，则说检查全局数据库中是否包含了该问题的解，若已包含，则说明己求出解，问题求解过程结束；否则转明己求出解，问题求解过程结束；否则转。 当规则库中还有未使用的规则，但均不能与全局数据库中的当规则库中还有未使用的规则，但均不能与全局数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供实，若能提供,则转则转,否则，说明该问题无解，终止问题求解否则，说明该问题无解，终止问题求解过程。过程。 若知识库中不再有末使用规则，也说明该问题无解，终止问若知识库中不再有末使用规则，也说明该问题无解，终止问题求解过程题求解过程。第第2章章 知识表示知识表示 242 产生式系统的分类 1. 1. 从总体控制策略上分类从总体控制策略上分类 不可挽回的产生式系统不可挽回的产生式系统 试探性产生式系统试探性产生式系统 回溯产生式系统回溯产生式系统 图搜索产生式系统图搜索产生式系统2. 2. 按推理方向分类按推理方向分类 向前产生式系统向前产生式系统 向后产生式系统向后产生式系统 双向产生式系统双向产生式系统3. 3. 按规则库的性质及结构分类按规则库的性质及结构分类 可交换的产生式系统可交换的产生式系统 可分解的产生式系统可分解的产生式系统 可恢复的产生式系统可恢复的产生式系统第第2章章 知识表示知识表示 （c）四皇后问题的产生式推理系统R32R11R13R23R24R21R34R42 （ ） A11 A13A11，A23A11，A24A11，A24，A32A13，A21A13，A21，A34A13，A21，A34，A42 1 2 3 41234 i j（a） 44棋盘的四皇后问题 图2-16 四皇后问题求解回溯过程例例 四皇后问题。四皇后问题。 第第2章章 知识表示知识表示 例例2-8 设全局数据库的初始状态为设全局数据库的初始状态为C，B，Z，目标状态，目标状态为为M，M， ，M，规则库中有如下重写规则，规则库中有如下重写规则:R1: CD，L R2: CB，M R3: BM，M R4: ZB，B，M 图2-17 可分解的产生式系统D，LDLBBMMMBMMMR3M，MMMR3M，MMMR3M，MB，MM，MB，B，MCBZR1R2R3R4C，B，Z第第2章章 知识表示知识表示 产生式系统的优点： 1模块性模块性 2自然性自然性 3 有效性有效性 4 一致性一致性 5 容易排除故障容易排除故障 6推理方向的可逆性推理方向的可逆性 7控制机构的多样性控制机构的多样性产生式系统的缺点产生式系统的缺点1 效率不高2 非透明性3 解释能力 的局限性第第2章章 知识表示知识表示 产生式系统应用场合产生式系统应用场合: 1知识结构类似于产生式规则的领域并且领域知知识结构类似于产生式规则的领域并且领域知识是扩散型的，领域内需要有大量的经验知识，识是扩散型的，领域内需要有大量的经验知识，不具备精确统一的理论，如临床医学、医疗诊断不具备精确统一的理论，如临床医学、医疗诊断系统等。系统等。 2可以自然地用产生式规则的后件来表达的领域。可以自然地用产生式规则的后件来表达的领域。该领域知识中包含一系列相互独立的动作，如医该领域知识中包含一系列相互独立的动作，如医院的病人监护系统。院的病人监护系统。 3领域知识可方便地从应用中分离出来的领域，领域知识可方便地从应用中分离出来的领域，如树类型辨识系统，经典分类学等。如树类型辨识系统，经典分类学等。第第2章章 知识表示知识表示 产生式系统的改进 1扩大规则集的表达能力。扩大规则集的表达能力。 2提高规则集的检索效率。如提高规则集的检索效率。如“激发树激发树”结构，或增加元规则，即规则的规则，组结构，或增加元规则，即规则的规则，组成多层结构的规则集，指导规则的运用。成多层结构的规则集，指导规则的运用。 3改进控制策略。解决规则匹配的优先次改进控制策略。解决规则匹配的优先次序和冲突裁决问题。序和冲突裁决问题。 4合理分配知识。为了提高事实库检索与合理分配知识。为了提高事实库检索与规则集匹配的效率，需要灵活地将知识合规则集匹配的效率，需要灵活地将知识合理分配在规则集和事实库中。理分配在规则集和事实库中。第第2章章 知识表示知识表示 25 语义网络 语义一般是指语言结构语义一般是指语言结构(如词、短语、句子、段如词、短语、句子、段落等落等)及其意义上的联系。及其意义上的联系。 语义网络在形式上是一个有向图，由一组节点语义网络在形式上是一个有向图，由一组节点和若干条有向弧线构成，节点和弧都可以有标和若干条有向弧线构成，节点和弧都可以有标号。节点表示各种事物、对象、概念、情况、号。节点表示各种事物、对象、概念、情况、性质、状态、事件、行为等；弧表示节点间的性质、状态、事件、行为等；弧表示节点间的语义联系或关系。语义联系或关系。 ABR图2-18 语义基元的结构第第2章章 知识表示知识表示 语义网络划分为七种类型语义网络划分为七种类型: 1命题语义网命题语义网(包括分块联想网络包括分块联想网络)； 2数据语义网数据语义网:以数据为中心的语义网络；以数据为中心的语义网络； 3语言语义网语言语义网:用于自然语言的分析和理解；用于自然语言的分析和理解； 4结构语义网结构语义网:描述客观事物的结构，常见于描述客观事物的结构，常见于模式识别和机器学习等领域；模式识别和机器学习等领域； 5分类语义网分类语义网:描述抽象概念及其层次；描述抽象概念及其层次； 6推理语义网推理语义网:是一种命题网，但它已在某种是一种命题网，但它已在某种程度上规范化，更适于推理；程度上规范化，更适于推理； 7. 框架语义网：与框架相结合的语义网。框架语义网：与框架相结合的语义网。第第2章章 知识表示知识表示 图2-19 有关图书馆的一个语义网络 图书馆 建筑物 张三 阅览室 读者 理工大学 单位 大礼堂 校园 钟山 学会 讲英语 公园 开放 阅览 风景美丽 海福巷Owner After Can Near-to Similar-to Can A-Member-of Is-a FetchLocated-underLocated-insideA-Kind-of Is-a A-part-of Have CanLocated-at 语义网络示例语义网络示例 第第2章章 知识表示知识表示 最常用的基本语义关系有以下几种最常用的基本语义关系有以下几种 1类属关系。类属关系。 是指具有不同事物间的分类关系、成是指具有不同事物间的分类关系、成员关系或实例关系。常用的类属关系有员关系或实例关系。常用的类属关系有: A-Kind-of（是（是一种）、一种）、A-Member-of（是一员）、（是一员）、Is-a（是一个）。（是一个）。 2 包含关系。是指包含关系。是指 “部分与整体部分与整体”之间的关系。常用之间的关系。常用的包含关系有的包含关系有:A-part-of（是一部分）。（是一部分）。 3 属性关系。属性关系。是指事物和其属性之间的关系。常用的是指事物和其属性之间的关系。常用的属性关系有属性关系有:Have（有）、（有）、Can（能、会）、所有者（能、会）、所有者（Owner）。）。 4 时间关系。时间关系。时间的先后次序关系，常用的时间关系时间的先后次序关系，常用的时间关系有有Before（在前），（在前），After（在后）。（在后）。 第第2章章 知识表示知识表示 最常用的基本语义关系有以下几最常用的基本语义关系有以下几种种 5. 推论关系。一个概念可由另一个概念推出，推论关系。一个概念可由另一个概念推出，如如Fetch（推出）。（推出）。 6. 位置关系。位置关系。 位置方面的关系。如位置方面的关系。如Located-on（在上）、（在上）、Located-at（在）、（在）、Located-under（在下）、（在下）、Located-inside（在内）、（在内）、Located-outside（在外）。（在外）。 7相近关系。相近关系。是指形状、内容等方面相似或是指形状、内容等方面相似或接近。如接近。如Similar-to（相似）、（相似）、Near-to（接（接近）。近）。 第第2章章 知识表示知识表示 用用 Prolog语句表示语句表示Located-under（“校园校园”，“钟山钟山”）；）； 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（“张三张三”，“讲英语讲英语”）；）；Can（“阅览室阅览室”，“开放开放”）；）；Can（“读者读者”，“阅览阅览”）。）。第第2章章 知识表示知识表示 例例 试用语义网络描述拱的概念和形状。试用语义网络描述拱的概念和形状。 的一部分是必须被支撑着柱 2柱 1 顶 （a） 拱是一个简单直柱体 拱顶柱1柱2长方块不能接触（b）拱的语义网络 拱与语义网络第第2章章 知识表示知识表示 252 语义网络的推理 1. 匹配 事物的匹配则为结构上的匹配，包括节点和弧的事物的匹配则为结构上的匹配，包括节点和弧的匹配。用匹配的方法进行推理时，首先构造问题的目匹配。用匹配的方法进行推理时，首先构造问题的目标网络块，然后在事实网络中寻找匹配。推理从一条标网络块，然后在事实网络中寻找匹配。推理从一条弧连接的两个节点的匹配开始，再匹配与该两个节点弧连接的两个节点的匹配开始，再匹配与该两个节点相连接的所有其他节点，直到问题得到解答。相连接的所有其他节点，直到问题得到解答。 假设在知识库中存放着如图假设在知识库中存放着如图2-19所示的语义网络，问所示的语义网络，问图书馆会干什么呢？图书馆会干什么呢？ 图2-20 语义网络片断 图书馆 阅览室 读者 ? Can A-part-of Have第第2章章 知识表示知识表示 2. 继承 所谓继承是指把对事物的描述从抽象节点传递到具体节点。所谓继承是指把对事物的描述从抽象节点传递到具体节点。通过继承可以得到所需节点的一些属性值，它通常是沿着通过继承可以得到所需节点的一些属性值，它通常是沿着Is-a、A-Kind-of等继承弧进行的。继承的一般过程为等继承弧进行的。继承的一般过程为: 1建立一个节点表，用来存放待求解节点和所有以建立一个节点表，用来存放待求解节点和所有以Is-a、A-Kind-of等继承弧与此节点相连的那些节点。初始情况下，表等继承弧与此节点相连的那些节点。初始情况下，表中只有待求解节点。中只有待求解节点。 2检查表中的第一个节点是否有继承弧。如果有，就把该检查表中的第一个节点是否有继承弧。如果有，就把该弧所指的所有节点放入节点表的末尾，记录这些节点的所有弧所指的所有节点放入节点表的末尾，记录这些节点的所有属性，并从节点表中删除第一个节点。如果没有，仅从节点属性，并从节点表中删除第一个节点。如果没有，仅从节点表中删除第一个节点。表中删除第一个节点。 3重复重复2，直到节点表为空。此时，记录下来的所有属性都，直到节点表为空。此时，记录下来的所有属性都是待求解节点继承来的属性。是待求解节点继承来的属性。 例如，在图例如，在图2-19所示的语义网络中，通过继承关系可以得所示的语义网络中，通过继承关系可以得到：张三不仅会讲英语，而且会阅览；阅览室在校园内，会到：张三不仅会讲英语，而且会阅览；阅览室在校园内，会开放，而且周围风景很美。开放，而且周围风景很美。第第2章章 知识表示知识表示 253 语义网络表示法的特征 1 知识的深化表达知识的深化表达 2 联想性联想性 3 自然性自然性 4结构化组织结构化组织 语义网络的缺点，主要表现为语义网络的缺点，主要表现为: 其形式过于简单。如果节点间的联系只局限于几其形式过于简单。如果节点间的联系只局限于几种典型的关系，则难以表达较复杂的关系种典型的关系，则难以表达较复杂的关系;而增加而增加联系又会大大增加网络的复杂度，相应的知识存联系又会大大增加网络的复杂度，相应的知识存储和检索过程就会变得十分复杂。事实上，语义储和检索过程就会变得十分复杂。事实上，语义网络的管理和维护也是很复杂的。网络的管理和维护也是很复杂的。此外，语义网此外，语义网络本身没有赋予其节点和弧以确切的含义。络本身没有赋予其节点和弧以确切的含义。 优点第第2章章 知识表示知识表示 26 框架表示法 1. 定义 框架（框架（Frames）是一种描述对象属性的数据结构。是一种描述对象属性的数据结构。人们只要把新的数据加入到该通用数据结构中便人们只要把新的数据加入到该通用数据结构中便可形成一个具体的实体，这样的通用数据结构就可形成一个具体的实体，这样的通用数据结构就称为框架。称为框架。 实例框架实例框架：把具体细节填入后，就得到了该框架：把具体细节填入后，就得到了该框架的一个具体实例，也被称为实例框架。的一个具体实例，也被称为实例框架。 框架系统：框架系统：由一组框架节点及其相互关系组成一由一组框架节点及其相互关系组成一个结构化的整体。个结构化的整体。 框架系统推理：框架系统推理：由框架之间的协调来完成。由框架之间的协调来完成。 框架表示方法：框架表示方法：是一种层次的、组合式的知识表是一种层次的、组合式的知识表示方法。示方法。第第2章章 知识表示知识表示 2. 框架的基本结构框架的基本结构 | | | 第第2章章 知识表示知识表示 3. 框架结构的示例框架结构的示例 例例2-11 一个描述硕士生有关情况的框架一个描述硕士生有关情况的框架框架名：框架名： 姓名：单位（姓，名）姓名：单位（姓，名） 性别：范围（男，女）性别：范围（男，女） 默认：男默认：男 年龄：单位（岁）年龄：单位（岁） 条件：岁条件：岁17 研究方向：单位（方向名）研究方向：单位（方向名） 导师姓名：单位（姓，名）导师姓名：单位（姓，名） 参加课题：范围（国家级，省部级，其它）参加课题：范围（国家级，省部级，其它） 默认：省部级默认：省部级 学籍：学籍： 住址：单位（楼号，房间号）住址：单位（楼号，房间号） 电话：单位（区号，话机号）电话：单位（区号，话机号） 入学时间：单位（年月）入学时间：单位（年月） 学制：单位（年）学制：单位（年） 默认：默认：3年年第第2章章 知识表示知识表示 4.实例框架实例框架 例例2-12 硕士生框架的一个实例框架：硕士生框架的一个实例框架： 框架名：框架名： 姓名：李学表姓名：李学表 性别：男性别：男 年龄：年龄：22 研究方向：人工智能研究方向：人工智能 导师姓名：吴博能导师姓名：吴博能 参加课题：参加课题： 学籍：学籍： 住址：住址：6号楼号楼205房间房间 电话：电话：(025)78787878 入学时间：入学时间：2008年年9月月 学制：学制： 第第2章章 知识表示知识表示 5.框架的框架的BNF（巴科斯范式）描述（巴科斯范式）描述 := := 框架名框架名 := , := 约束约束, := |(,) := | := | := | := , := := | := | := | := |, := 第第2章章 知识表示知识表示 6.框架系统的基本结构框架系统的基本结构 学生框架本科生框架硕士生框架博士生框架计算机系硕士生信息系硕士生1号硕士生n号硕士生图2-21 框架系统的层次结构第第2章章 知识表示知识表示 7. 学生框架系统的表示学生框架系统的表示 例例2-13 学生框架学生框架 框架名：框架名： 姓名：单位（姓，名）姓名：单位（姓，名） 性别：范围（男，女）性别：范围（男，女） 默认：男默认：男 年龄：单位（岁）年龄：单位（岁） 住址：单位（楼号，房间号）住址：单位（楼号，房间号） 电话：单位（区号，话机号）电话：单位（区号，话机号） 入学时间：单位（年，月）入学时间：单位（年，月） 学制：单位（年）学制：单位（年）第第2章章 知识表示知识表示 8. 硕士生框架系统的表示硕士生框架系统的表示 例例2-14 硕士生框架硕士生框架 框架名：框架名： 继承：继承： (纵向联系纵向联系) 学籍：学籍： (横向联系横向联系) 研究方向：单位（方向名）研究方向：单位（方向名） 导师姓名：单位（姓，名）导师姓名：单位（姓，名） 参加课题：范围（国家级，省部级，其它）参加课题：范围（国家级，省部级，其它） 默认：省部级默认：省部级 学位论文：单位：（论文题目）学位论文：单位：（论文题目） 默认：题目未定默认：题目未定第第2章章 知识表示知识表示 9. 计算机系硕士生框架系统的表示计算机系硕士生框架系统的表示 例例2-15 计算机系硕士生框架计算机系硕士生框架 框架名：框架名： 继承：继承： 专业：范围（计算机应用技术，计算机专业：范围（计算机应用技术，计算机 软件及理论）软件及理论） 默认：计算机应用技术默认：计算机应用技术 使用计算机：单位（计算机的型号）使用计算机：单位（计算机的型号）第第2章章 知识表示知识表示 10.实例框架的例子实例框架的例子 例例2-16 设某个计算机系硕士生的实例框架设某个计算机系硕士生的实例框架 框架名：框架名： 继承：继承： 姓名：杨兵姓名：杨兵 性别：男性别：男 年龄：年龄：23 研究方向：人工智能研究方向：人工智能 第第2章章 知识表示知识表示 11.框架系统中的预定义槽名框架系统中的预定义槽名 常用的预定义槽名有以下几种：常用的预定义槽名有以下几种： is-a槽：类属关系，含义为槽：类属关系，含义为“是一个是一个”。 AKO槽：类属关系，含义为槽：类属关系，含义为 “是一种是一种”。用。用AKO作为下层框作为下层框架的槽名时，其槽值为上层框架的框架名。架的槽名时，其槽值为上层框架的框架名。 Subclass槽：类属关系。当用它作为某下层框架的槽时，表槽：类属关系。当用它作为某下层框架的槽时，表示该下层框架是其上层框架的一个子类。示该下层框架是其上层框架的一个子类。 instance槽：用来建立槽：用来建立“AKO”槽的逆关系。当用它作为某上槽的逆关系。当用它作为某上层框架的槽时，可用来指出它的下一层框架都有哪些层框架的槽时，可用来指出它的下一层框架都有哪些 。 part-of槽：用于指出槽：用于指出“部分部分”与与“全体全体”的关系。的关系。 infer槽：指两框架所描述事物间的逻辑推理关系。槽：指两框架所描述事物间的逻辑推理关系。 possible-reason槽：与槽：与infer槽相反，用来把某结论与原因联槽相反，用来把某结论与原因联系起来。系起来。 similar槽：指出两个框架所描述的事物之间的相似关系。槽：指出两个框架所描述的事物之间的相似关系。 rotation槽：指出两个框架所描述的事物之间的槽：指出两个框架所描述的事物之间的“旋转旋转”关关系。系。第第2章章 知识表示知识表示 12. 框架系统的推理框架系统的推理 框架系统也可实现继承和匹配。框架系统继承，框架系统也可实现继承和匹配。框架系统继承，就是子框架可以拥有其父框架的槽及其槽值。实就是子框架可以拥有其父框架的槽及其槽值。实现继承的操作有匹配、搜索和填槽。匹配就是问现继承的操作有匹配、搜索和填槽。匹配就是问题框架同知识库中的框架的模式匹配。题框架同知识库中的框架的模式匹配。 除此以外，由于框架用于描述具有固定格式的事除此以外，由于框架用于描述具有固定格式的事物、动作和事件，因此可以推论出未被观察到的物、动作和事件，因此可以推论出未被观察到的事实。框架用以下几种途径来帮助实现这一点：事实。框架用以下几种途径来帮助实现这一点： 框架包含它所描述的情况或多方面的信息。框架包含它所描述的情况或多方面的信息。 框架包含物体必须具有的属性。框架包含物体必须具有的属性。 框架描述它们所代表的概念的典型事例。框架描述它们所代表的概念的典型事例。 第第2章章 知识表示知识表示 13. 框架系统问题的求解过程框架系统问题的求解过程 框架系统的问题求解过程按以下步骤进行：框架系统的问题求解过程按以下步骤进行： 把要求解的问题用框架表示出来。把要求解的问题用框架表示出来。 把它与知识库中的已有框架进行匹配，找出一把它与知识库中的已有框架进行匹配，找出一个或多个候选框架，并在这些候选框架引导下进个或多个候选框架，并在这些候选框架引导下进一步获取附加信息，填充尽量多的槽值，以建立一步获取附加信息，填充尽量多的槽值，以建立一个描述当前情况的实例。一个描述当前情况的实例。 (3) 用某种评价方法对候选框架进行评价，以决用某种评价方法对候选框架进行评价，以决定是否接收该框架。定是否接收该框架。第第2章章 知识表示知识表示 14.五种知识表示方法的比较 表示方表示方法法特点特点优缺点优缺点应用场合应用场合状态空状态空间表示间表示法法 以状态和操作为基础，将问题的以状态和操作为基础，将问题的求解定义为从初始状态到目标状求解定义为从初始状态到目标状态的过程。态的过程。 是一类问题的抽象表示，但需要扩展是一类问题的抽象表示，但需要扩展过多的节点；容易产生组合爆炸。过多的节点；容易产生组合爆炸。 适合表达过程适合表达过程性知识。性知识。 与或图与或图表示法表示法 通过一系列的分解变换将原问题通过一系列的分解变换将原问题变为子问题和子子问题的集合。变为子问题和子子问题的集合。 能够较有效的表示问题。但也可能会能够较有效的表示问题。但也可能会扩展大量的节点，存在组合爆炸。扩展大量的节点，存在组合爆炸。 适合表达较复适合表达较复杂的知识。杂的知识。 产生式产生式表示法表示法 利用一系列的规则来表示知识和利用一系列的规则来表示知识和进行推理。进行推理。规则相互独立、模块化；表示方式自规则相互独立、模块化；表示方式自然、直观；推理方便、易排除故障；然、直观；推理方便、易排除故障；控制机制多样。但工作效率较低；解控制机制多样。但工作效率较低；解释能力有限。释能力有限。 适合表达具有适合表达具有某种因果关系某种因果关系的知识。的知识。 语义网语义网络表示络表示法法 是一种用实体及其语义关系来表是一种用实体及其语义关系来表达知识的有向网络图达知识的有向网络图 是一种结构化的知识表示法，具有联是一种结构化的知识表示法，具有联想性、自索引性、自然性，但表达范想性、自索引性、自然性，但表达范围有限，推理规则不十分明了。围有限，推理规则不十分明了。 适合表达事物适合表达事物之间的关系和之间的关系和联系联系 框架表框架表示法示法 由若干个槽和侧面及对应的值来由若干个槽和侧面及对应的值来描述事物各方面的属性和状态。描述事物各方面的属性和状态。 是一种结构化的表示方法，但是难以是一种结构化的表示方法，但是难以清楚地定义知识的模块性。清楚地定义知识的模块性。 适合表达结构适合表达结构性的知识。性的知识。