人工智能及专家系统 教学课件 ppt 作者 敖志刚 第2章 知识表示

敖志刚 编制,第2章 知识表示,第2章 知识表示,21 知识与知识表示的概念 211 知识 212 知识表示 22 状态空间表示法 221 状态空间表示法的基本概念和策略 222 状态空间表示法示例 23 与/或图知识表示 231 与/或图知识表示的概念 232 与/或图表示示例,第2章 知识表示,24 产生式知识表示 241 产生式的结构和组成 242 产生式系统的分类 243 产生式系统的性能及其应用 25 语义网络 251 语义网络的概念 252 语义网络的推理 253 语义网络表示法的特征 26 框架表示法 261 框架表示法的概念与设计 262 框架的基本结构和描述 263 框架系统 264 框架系统的推理和求解过程 264 五种知识表示方法的比较,21 知识与知识表示的概念 2.1.1 知识 1. 知识的概念,知识是人们对客观事物及其规律的认识，包括对事物的现象、本质、属性、状态、关系、联系和运动等的认识；是解决问题的步骤、操作、规则、过程、技术、技巧、战术、战略、计谋、策略。知识是经过消减、加工、整理、解释、挑选、改造、选择和转换的信息和数据，是由特定领域的事实、信念、描述、关系、启发式和过程组合起来的。,2. 知识的分类, 按知识的作用：叙述型知识、过程型知识、控制型知识； 按知识的的性质：对象性知识、事件性知识、性能性知识、元知识； 按知识的作用范围：常识性知识、领域性知识； 按知识的层次：表层知识、深层知识； 按知识的确定性：确定性知识、不确定性知识,3. 知识的属性,可表示性、可利用性、不确定性、矛盾性、相容性、真假性、相对性。,212 知识表示 面向人的知识表示的概念,面向人的知识表示可以用是语言、文字、数字、符号、公式、图表、图形、图像等多种形式。这些表示形式是人所能接受、理解和处理的形式。,2. 面向计算机的知识表示的概念,就是要用某种约定的(外部)形式结构来描述知识，通常用知识的规则符号、形式语言和网络图等使知识形式化或模型化 ，而且这种形式结构还要能够转换为机器的内部形式，在计算机中用合适的形式对问题求解过程中所需要的各种知识进行组织、存储、检索、使用、增删、修改、推理和判断；使得计算机能方便地存储、处理和利用。,3. 设计知识表示的基本原则,可实现性、可理解性、表示能力、可维护性、可利用性、自然性、可组织性,4. 知识表示方法的分类,状态空间表示法 基于图的表示法 与/或图表示法 语义网络表示法 谓词逻辑表示法 产生式表示法 特性表示法 框架表示法 知识表示 功能表示法 脚本表示法 过程表示法 多层次信息结构表示法 概念图解表示法 神经网络表示法 意识胞表示法 不精确表示法,状态图,与或图示例,语义网络示例,产生式推理网络示例,22 状态空间表示法 2.2.1 状态空间表示法的基本概念,状态：各种相关对象的可能的排列、情况、形势和现状。 表示形式：通常用一组指标、变量或数组来表示。 三个共有特征：就是状态、规则和目标。 问题的三种状态：开始状态、中间状态和目标状态。,知识表示一般步骤:,1 定义一状态空间； 2 确定开始状态； 3 确定目标状态； 4 规定一组规则； 5 将非形式的问题描述转换成形式描述；画出描述问题的状态图； 6 分析问题； 7 选择最佳技术去求解待解问题。,2.2.2 状态空间表示法示例,例2-1 水壶问题 有两个水壶，一个盛满为4公斤水，另一个盛满为3公斤水，水壶上没有任何度量标记。怎样在能装4公斤的水壶里恰好只装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修道士和野人问题,在河的左岸有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 不合法 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 合法,定义规则, 将一个修道士从左岸运到右岸； 将一个野人从左岸运到右岸； 将一个修道士和一个野人从左岸运到右岸； 将二个修道士从左岸运到右岸； 将二个野人从左岸运到右岸； 将一个修道士从右岸运到左岸； 将一个野人从右岸运到左岸； 将一个修道士和一个野人从右岸运到左岸； 将二个修道士从右岸运到左岸； 将二个野人从右岸运到左岸；,状态图的概念,修道士和野人问题的状态图,计算机的表达方法,按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个金片。梵天要求僧侣们轮流把金片在三根针之间移来移去，规定每次只能移动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之间的关系就可以用一棵“与树”来表示。,与或图示例,可解节点,在与/或图中，满足以下三个条件之一的节点为可解节点: 任何终止节点都是可解节点。 对“或”节点，当其子节点中至少有一个为可解节点时，则该“或”节点就是可解节点。 对“与”节点，只有当其子节点全部为可解节点时，该“与”节点才是可解节点。,不可解节点,可用类似的方法定义不可解节点: 不为终止节点的端节点是不可解节点。 对“或”节点，若其全部子节点都为不可解节点，则该“或”节点是不可解节点。 对“与”节点，只要其子节点中有一个为不可解节点，则该“与”节点是不可解节点。,与或图表示举例,例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。,两全等四边形,与/或图表示,示例,例 试求积分 有两种方法解此积分 1因为 ，所以上述积分变为 2上述积分可按下式变换 上述两种方法可用下列与/或图如图2-11来描述,与或图表示,示例,例2-5 分火柴游戏，设堆有7根火柴，由Max（我方）和Min方（对手）两人轮流来分它们，要求每次都要把某堆火柴分成不相等的两部分，最后不能分下去的人为负，对方为胜。如果对方先走，用与/或图知识表示来描述。 如果MIN先走，他有三种选择方法：(6，1)、(5,2)、(4，3)，在MIN的每一种选择下，MAX又有两种走法，整个博弈与/或图如图2-12所示。,与或图表示,24 产生式知识表示,产生式(Production)一词最早是由美国数学家波斯特(EPost)于1943年根据串替换规则提出的一种称为Post机的计算模型。1954年，Markov对Post的产生式系统作了改进，提出了产生式系统的控制策略，根据规则的优先级来确定其执行的顺序。1957年Chomskey利用一系列产生式规则来描述每层文法的语言生成规则。1972年，纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统。目前，产生式表示法已成为人工智能中应用最多的一种知识表示模式。,241 产生式的结构和组成,产生式的一般形式为“前件+后件”。前件就是前提，后件是结论或动作 。 产生式包括各种操作、规则、变换、算子、函数等等 产生式表示法可以很容易地描述事实、规则以及它们的不确定性度量。 规则描述的是事物间的因果关系。其基本形式为:“PQ”或“IF P THEN Q”， 含义是：如果前提P满足，则可推出结论Q或执行Q所规定的操作；,图表示概念,产生式系统示例,例2-6 一个动物识别系统的产生式如下: R1: :若某动物有奶，则它是哺乳动物。 R2: 若某动物有毛发，则它是哺乳动物。 R3: 若某动物吃肉，则它是食肉动物。 R4: 若某动物有爪且有犬齿且眼视前方，则它是食肉动物。 R5: 若某动物是哺乳动物且有蹄，则它是有蹄动物。 R6: 若某动物是有蹄动物且反刍食物，则它是有蹄动物。 R7: 若某动物是哺乳动物且食肉动物且黄褐色且有黑色条纹，则它是老虎。 R8: 若某动物是哺乳动物且食肉动物且黄褐色且有暗斑点，则它是金钱豹。 R9: 若某动物是有蹄动物且有黑色条纹，则它是斑马。 R10: 若某动物是有蹄动物且长腿且长脖子且有暗斑点，则它是长颈鹿。,产生式系统的三个主要部分,产生式系统问题求解的基本过程:,初始化全局数据库,把已知事实送入全局数据库中。 检查规则库是否有末使用的规则，若有执行；否则转。 检查规则库的末使用规则中是否存在有其前提可与全局数据库中已知事实相匹