【教学课件】第二章知识表示.ppt

第二章 知识表示,知识与知识表示的概念 一阶谓词逻辑表示法 产生式表示法 语义网络表示法 框架表示法 过程表示法,按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首先必须使它拥有知识。,知识与知识表示的概念,知识的概念知识表示的概念,2.1.1 知识的概念,知识的一般概念：知识是人们在改造客观世界的实践中积累起来的认识和经验 认识：包括对事物现象、本质、属性、状态、关系、联系和运动等的认识 经验：包括解决问题的微观方法：如步骤、操作、规则、过程、技巧等 宏观方法：如战略、战术、计谋、策略等知识的有代表性的定义：（1）Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换了的信息（2）Bernstein：知识由特定领域的描述、关系和过程组成（3）Heyes-Roth：知识=事实+信念+启发式知识、信息、数据及其关系 数据是信息的载体，本身无确切含义，其关联构成信息 信息是数据的关联，赋予数据特定的含义，仅可理解为描述性知识 知识可以是对信息的关联，也可以是对已有知识的再认识 常用的关联方式：if then,什么是知识？,按知识的性质：概念、命题、公理、定理、规则和方法按知识的作用域：常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的知识。领域性知识：面向某个具体专业领域的知识。例如：专家经验。按知识的作用效果：事实性知识：用于描述事物的概念、定义、属性等；或用于描述问题的状态、环境、条件等。过程性知识：用于问题求解过程的操作、演算和行为的知识；用来指出如何使用那些与问题有关的事实性知识的知识；表示方式：产生式、谓词、语义网络等。控制性知识：(元知识或超知识)是关于如何使用过程性知识的知识；例如：推理策略、搜索策略、不确定性的传播策略。,2.1.1 知识的概念,知识的类型,按知识的层次 表层知识：描述客观事物的现象的知识。例如：感性、事实性知识 深层知识：描述客观事物本质、内涵等的知识。例如：理论知识按知识的确定性 确定性知识：可以说明其真值为真或为假的知识 不确定性知识：包括不精确、模糊、不完备知识 不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假 表示：用可信度、概率等描述 模糊：知识本身的边界就是不清楚的。例如：大，小等 表示：用可能性、隶属度来描述 不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病按知识的等级 零级知识：叙述性知识 一级知识：过程性知识 二级知识：控制性知识（元知识或超知识）,2.1.1 知识的概念,知识表示的要求表示能力：能否正确、有效地表示问题。包括：表范围的广泛性 领域知识表示的高效性 对非确定性知识表示的支持程度 可利用性：可利用这些知识进行有效推理。包括：对推理的适应性：推理是根据已知事实利用知识导出结果的过程 对高效算法的支持程度：知识表示要有较高的处理效率可实现性：要便于计算机直接对其进行处理 可组织性：可以按某种方式把知识组织成某种知识结构可维护性：便于对知识的增、删、改等操作自然性：符合人们的日常习惯可理解性：知识应易读、易懂、易获取等,2.1.1 知识的概念,知识表示的含义及要求,知识表示的观点 陈述性观点：知识的存储与知识的使用相分离 优点：灵活、简洁，演绎过程完整、确定，知识维护方便 缺点：推理效率低、推理过程不透明 过程性观点：知识寓于使用知识的过程中 优点：推理效率高、过程清晰 缺点：灵活性差、知识维护不便知识表示的方法 逻辑表示法：一阶谓词逻辑 产生式表示法：产生式规则 结构表示法：语义网络，框架 过程表示法：,2.1.2 知识表示的概念,知识表示的观点及方法,知识表示技术综述,逻辑表示模式,语义网络,过程表示和产生式系统,产生式系统(PS)表示法评述表,框架,一阶谓词逻辑表示法,逻辑是最早也是最广泛用于知识表示的模式 知识的逻辑表达通常是指用一阶谓词逻辑来描述人工智能的问题求解知识,命题演算,谓词演算,用一阶谓词描述人的婚姻年龄关系 个体：SUE，BOB，TWENTY，THIRTY 谓词：married(X,Y)X和Y结婚 aged(X,Z)X的年龄为Z male(X)X是男性其中：X，Y，Z是个体变元，它们的个体域是SUE，BOB，TWENTY，THIRTY；可以表示成一组合式谓词公式的合取形式：married(SUE,BOB)aged(SUE,TWENTY)aged(BOB,THIRTY)male(BOB)谓词演算使用两个量词:一个是全称量词：，彐,例1:There is playing card that is red and is a jack,彐X playing-card(X)jack(X)is-red(X),例2:每个人(X)有一个父亲(Y)“,X彐Yperson(X)hasfather(X,Y),谓词演算,设在一房间里，c处有一个机器人，a和b处各有一张桌子，分别称为a桌和桌和b桌，a桌上有一盒子，如图所示要求机器人从c处出发把盒子从a桌上拿到b桌上，然后再回到c处请用谓词逻辑来描述机器人的行动过程。,1.机器人移盒子,逻辑表示在AI中的应用,定义谓词 状态 操作 状态 TABLE(x):x是桌子 EMPTY(y):y手中是空的 AT(y,z):y在在z的附近 HOLDS(y,w):y拿着w ON(w,x):w在x桌面上,机器人移盒子,问题的初始状态：AT(robot,c)EMPTY(robot)ON(box,a)TABLE(a)TABLE(b)问题的目标状态：AT(robot,c)EMPTY(robot)ON(box,b)TABLE(a)TABLE(b),机器人移盒子,逻辑表示在AI中的应用,所求的问题的解是机器人的操作序列 定义谓词来表示机器人的操作动作：GOTO(x,y):从x处走到y处 Pickup(x):在x处拿起盒子 Setdown(x):在x处放下盒子,机器人移盒子,逻辑表示在AI中的应用,GOTO(x,y):从x处走到y处条件：AT(robot,x)状态变化：删除表：AT(robot,x)添加表：添加表：AT(robot,y)Pickup(x):在x处拿起盒子条件:ON(box,x),TABLE(x),AT(robotx),EMPTY(robot)状态变化：删除表：EMPTY(robot),ON(box,x)添加表：HOLDS(robot,box)Setdown(x)：在x处放下盒子 条件：AT(robot,x),TABLE(x),HOLDS(robot,box)状态变化：删除表：HOLDS(robot,box)添加表：EMPTY(robot),ON(box,x),机器人移盒子,逻辑表示在AI中的应用,机器人移盒子,史密斯家族聚会问题,考虑一个假想的家庭聚会，史密斯家族几十年来第一次聚到一起。他们发现某些共同的习惯和兴趣，能使两对或更多的夫妇一起度过一个令人愉快的假期。夫妇们的兴趣和习惯种类是：（1）饮食爱好和习惯（2）娱乐偏好（3）度假偏好（4）早上起床时间,逻辑表示在AI中的应用,定义谓词sameinterest(X,Y)表示两对夫妇对四类谓词(diet,entertainment,location,rise-time)均有共同兴趣,其中X,Y分别表示两个不同夫妇对中丈夫的名字。彐X1 X2 Y1 Y2 D1 D2 E1 E2 L1 L2 R1 R2 sameinterest(X1,Y1)(married(X1,X2)married(Y1,Y2)(X1=Y1)(diet(X1,D1)diet(Y1,D2)(D1=D2)(entertainment(X1,E1)entertainment(Y1,E2)(E1=E2)(location(X1,L1)location(Y1,L2)(L1=L2)(rise-time(X1,R1)rise-time(Y1,R2)(R1=R2),史密斯家族聚会问题,逻辑表示在AI中的应用,修道士和野人问题(The Missionaries and Cannibals Problem),定义谓词:(X,Y,S)表示状态S下 XY(X,Y,S)表示状态S下 XYX,Y的个体域是0,1,2,3 然后定义安全性谓词 safety(Z,X,Y,S):safety(Z,X,Y,S)(X,0,S)(X,Y,S)(X=0),在河的左岸有三个野人,三个修道士和一条船，修道士们想用这条船把所有的人运到河对岸,但受以下条件的约束:1.修道士和野人都会划船修，但船每次至多可载两个人;2.在河的任一岸如果野人数目超过修道士数目,修道士就会被野人吃掉；假设野人会服从任何一次过河安排，请规划一个确保修道士安全过河的计划.,逻辑表示在AI中的应用,谓词 across：在保证渡河前后的安全性的前提下的一种过河方案:S=across(D,X,X1,Y,Y1,S)(D=+)safety(L,X-X1,Y-Y1,S)safety(R,3-X+X1,3-Y+Y1,S)(boat(L,S)boat(R,S)(D=-)safety(R,X-X1,Y-Y1,S)safety(L,3-X+X1,3-Y+Y1,S)(boat(R,S)boat(L,S)(2,X1+Y1,S),修道士和野人问题(The Missionaries and Cannibals Problem),逻辑表示在AI中的应用,描述状态的谓词：,a,b,c,猴子摘香蕉问题,逻辑表示在AI中的应用,AT(x,y)：x在y处ONBOX：猴子在箱子上 HB：猴子得到香蕉,个体域：x：monkey,box,banana Y：a,b,c,问题的初始状态 AT(monkey,a)AT(box,b)ONBOX，HB 问题的目标状态 AT(monkey,c)，AT(box,c)ONBOX，HB,a,b,c,猴子摘香蕉问题,逻辑表示在AI中的应用,猴子摘香蕉问题,逻辑表示在AI中的应用,描述操作的谓词 Goto(u,v)：猴子从u处走到v处 Pushbox(v,w)：猴子推着箱子从v处移到w处 Climbbox：猴子爬上箱子 Grasp：猴子摘取香蕉 各操作的条件和动作 Goto(u,v)条件：ONBOX，AT(monkey,u)，动作：删除表：AT(monkey,u)添加表：AT(monkey,v)Pushbox(v,w)条件：ONBOX，AT(monkey,v)，AT(box,v)动作：删除表：AT(monkey,v)，AT(box,v)添加表：AT(monkey,w)，AT(box,w),a,b,c,Climbbox 条件：ONBOX，AT(monkey,w)，AT(box,w)动作：删除表：ONBOX 添加表：ONBOX Grasp 条件：ONBOX，AT(box,c)动作：删除表：HB 添加表：HB,猴子摘香蕉问题,逻辑表示在AI中的应用,a,b,c,谓词逻辑表示的特征,主要优点 自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解 明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解 精确：谓词逻辑的真值只有“真”与“假”，其表示、推理都是精确的 灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节 模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行,主要缺点 知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识 知识库管理困难：缺乏知识的组织原则，知识库管理比较困难 存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸 系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率,谓词逻辑表示的特征,产生式表示法,产生式是目前人工智能中使用最多的一种知识表示方法,2.3.1 产生式表示的基本方法 事实的表示 规则的表示2.3.2 产生式系统的基本结构2.3.3 产生式系统的基本过程2.3.4 产生式系统的控制策略2.3.5 产生式系统的类型 2.3.6 产生式系统的特性,2.3.1 产生式表示的基本方法,事实的定义 事实：断言一个语言变量的值或断言多个语言变量之间关系的陈述句 语言变量的值或语言变量之间的关系可以是数字、词等 例如：“雪是白的”，其中“雪”是语言变量，“白的”是语言变量的值“王峰热爱祖国”，其中，“王峰”和“祖国”是两个语言变量,“热爱”是语言变量之间的关系事实的表示 确定性知识：事实可用如下三元组表示：（对象，属性，值）或（关系，对象1，对象2）非确定性知识：事实可用如下四元组表示：（对象，属性，值，可信度因子）“可信度因子”是指该事实为真的相信程度。可用0,1之间的一个实数来表示。,事实的表示,规则的作用：描述事物之间的因果关系。规则的产生式表示形式常称为产生式规则，简称为产生式或规则。产生式的基本形式：PQ 或者 IF P THEN Q产生式的含义：如果前提P满足，则可推出结论Q或执行Q所规定的操作,2.3.1 产生式表示的基本方法,产生式规则的例子：r6:IF 动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是食肉动物,规则的表示,综合数据库DB(Data Base)存放求解问题的各种当前信息,2.3.1 产生式表示的基本方法,控制系统(Control system)控制系统的主要作用 亦称推理机，用于控制整个产生式系统的运行，决定问题求解过程的推理线路,规则库RB(Rule Base)也称知识库KB(Knowledge Base),用于存放与求解问题有关的所有规则的集合 作用：是产生式系统问题求解的基础 要求：知识的完整性、一致性、准确性、灵活性和知识组织的合理性,控制系统的主要任务选择匹配：按一定策略从规则库种选择规则与综合数据库中的已知事实进行匹配。匹配是指把所选规则的前提与综合数据库中的已知事实进行比较，若事实库中存的事实与所选规则前提一致，则称匹配成功，该规则为可用；否则，称匹配失败，该规则不可用。冲突消解：对匹配成功的规则，按照某种策略从中选出一条规则执行。执行操作：对所执行的规则，若其后件为一个或多个结论，则把这些结论加入综合数据库；若其后件为一个或多个操作时，执行这些操作。终止推理：检查综合数据库中是否包含有目标，若有，则停止推理。路径解释：在问题求解过程中，记住应用过的规则序列，以便最终能够给出问题的解的路径。,2.3.1 产生式表示的基本方法,2.3.1 产生式表示的基本结构,包含以下规则:R1:如果引擎不能转动(1),且电瓶内有电(2)，则让用户检查启动器。R2:如果没有火花，则让用户检查电极尖端。R3:如果引擎能转动(1)但车子不能启动(2)，则让用户检查火花塞。R4:如果引擎不能转动，则让用户检查电瓶。R5:如果电瓶没电，则让用户给电瓶充电(1),且退出(2)。Rn 数据库中含有一个简单事实:引擎不能转动,设有一个汽车故障检测系统:,动物识别系统：该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物。其规则库包含如下15条规则：r1 IF 该动物有毛发 THEN 该动物是哺乳动物 r2 IF 该动物有奶 THEN 该动物是哺乳动物r3 IF 该动物有羽毛 THEN 该动物是鸟r4 IF 该动物会飞 AND 会下蛋 THEN 该动物是鸟r5 IF 该动物吃肉 THEN 该动物是食肉动物r6 IF 该动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是食肉动物r7 IF 该动物是哺乳动物 AND 有蹄 THEN 该动物是有蹄类动物r8 IF 该动物是哺乳动物 AND 是嚼反刍动物 THEN 该动物是有蹄类动物r9 IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有暗斑点 THEN 该动物是金钱豹,r10 IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有黑色条纹 THEN 该动物是虎r11 IF 该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 该动物是长颈鹿r12 IF 动物是有蹄类动物 AND 身上有黑色条纹 THEN 该动物是斑马r13 IF 该动物是鸟 AND 有长脖子 AND 有长腿 AND 不会飞 AND 有黑白二色 THEN 该动物是鸵鸟r14 IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅r15 IF 该动物是鸟 AND 善飞 THEN 该动物是信天翁,动物识别系统：,初始综合数据库包含的事实有：动物有暗斑点，有长脖子，有长腿，有奶，有蹄,动物识别系统：,图中最上层的结点称为“假设”或“结论”中间结点称为“中间假设”；终结点称为“证据”或“事实”；每个“结论”都是本问题的一个目标，所有“假设”构成了本问题的目标集合,长颈鹿,斑马,长脖子,长腿,暗斑点,有蹄类,黑条纹,有蹄,哺乳动物,嚼反刍动物,有毛,r2,r7,r8,r11,r12,有奶,r1,2.3.1 产生式表示的基本结构,系统的推理过程(1)先从规则库中取出第一条规则r1，检查其前提是否可与综合数据库中的已知事实相匹配。r1的前提是“有毛发”，但事实库中无此事实，故匹配失败。然后取r2，该前提可与已知事实“有奶”相匹配，r2被执行，并将其结论“该动物是哺乳动物”作为新的事实加入到综合数据库中。此时，综合数据库的内容变为：动物有暗斑，有长脖子，有长腿，有奶，有蹄，是哺乳动物(2)再从规则库中取r3，r4，r5，r6进行匹配，均失败。接着取r7，该前提与已知事实“是哺乳动物”相匹配，r7被执行，并将其结论“该动物是有蹄类动物”作为新的事实加入到综合数据库中。此时，综合数据库的内容变为：动物有暗斑，有长脖子，有长腿，有奶，有蹄，是哺乳动物，是有蹄类动物(3)此后，r8，r9，r10均匹配失败。接着取r11，该前提“该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑”与已知事实相匹配，r11被执行，并推出“该动物是长颈鹿”。由于“长颈鹿”已是目标集合中的一个结论，即已推出最终结果，故问题求解过程结束。说明：上述规则仅是一种直接表示方式，用三元组表示r15如下：r15：IF（动物，类别，鸟）AND（动物，本领，善飞）THEN（动物，名称，信天翁）,产生式表示的基本结构,起源和功用 POST(1943年）提出，在 ES 领域中得到了广泛的应用。例如：DENDRAL 化学质谱仪分析系统 MYCIN 医疗诊断专家系统 HEARSAY 语音识别系统,问题求解中的搜索策略,冲突消解策略(1)随机选择(2)在相继阶段中选不同的规则(3)选择第一条可用规则(4)给每条规则赋予一权值，并用权值来决定选择哪条规则。,回溯,深度优先/广度优先/启发式搜索(1)深度优先搜索 generate 和 validate 都可划归为深度优先搜索。(2)广度优先搜索,问题求解中的搜索策略,R1(7)R2(10)3 1 R2 R3(5)R1 R4(20)6 9 4 2 R3 R4 R2 R3 R4 8 7 13 10 5 R4 R4 R4 11 14 12 图 启发式搜索,(3)启发式搜索 假设各规则给定权重如下:R1:7;R2:10;R3:5;R4:20那么,启发式数据驱动方法扩展顺序,如图:,2.3.3 产生式系统的基本过程,(1)初始化综合数据库，即把欲解决问题的已知事实送入综合数据库中；(2)检查规则库中是否有未使用过的规则，若无转(7)；(3)检查规则库的未使用规则中是否有其前提可与综合数据库中已知事实相匹配的规则，若有，形成当前可用规则集；否则转(6)；(4)按照冲突消解策略，从当前可用规则集中选择一个规则执行，并对该规则作上标记。把执行该规则后所得到的结论作为新的事实放入综合数据库；如果该规则的结论是一些操作，则执行这些操作；(5)检查综合数据库中是否包含了该问题的解，若已包含，说明解已求出，问题求解过程结束；否则，转(2)；(6)当规则库中还有未使用规则，但均不能与综合数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供，则转(2)；否则，执行下一步；(7)若知识库中不再有未使用规则，也说明该问题无解，终止问题求解过程。说明：从第(3)步到第(5)步的循环过程实际上就是一个搜索过程,2.3.4 产生式系统的控制策略,总体上可分为以下两种方式：1.不可撤回方式 它即根据当前已知的局部知识选取一条规则作用于当前综合数据库，接着再根据新状态继续选取规则，如此进行下去，不考虑撤回用过的规则。不理想规则的应用会降低效率，但不影响可解性。优点是控制过程简单，缺点是当问题有多个解时不一定能找到最优解2.试探性方式 又可分为以两种下方式：回溯方式：是一种碰壁回头的方式。即在问题求解过程中，允许先试一试某条规则，如果以后发现这条规则不合适，则允许退回去，再另选一条规则来试。需要解决的主要问题：一是如何确定回溯条件，二是如何减少回溯次数 是一种完备而有效的策略，它容易实现且占内存容量较小。图搜索方式：图搜索方式是一种用图或树把全部求解过程记录下来的方式。由于它记录了已试过的所有路径，因此便于从中选取最优路径。主要区别 回溯方式抹去了所有引起失败的试探路径，而图搜索方式则记住了已试过的所有路径。,正向推理产生式系统：也称数据驱动方式，它是从初始状态出发，朝着目标状态前进，正向使用规则的一种推理方法。正向使用规则，是指以问题的初始状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的前提时，该规则才被使用。优点：简单明了，且能求出所有解 缺点：执行效率较低，原因是使用规则具有一定的盲目性。逆向推理产生式系统 也称目标驱动方式，它是从目标（作为假设）状态出发，朝着初始状态前进，反向使用规则的一种推理方法。所谓逆向使用规则，是指以问题的目标状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的后件时，该规则才被使用。优点：不使用与问题无关的规则。因此，对那些目标明确的问题，使用反向推理方式是一种最佳选择。双向推理产生式系统 双向推理是把正向推理和反向推理结合起来使用的一种推理方式 它需要把问题的初始状态和目标状态合并到一起构成综合数据库,2.3.4 产生式系统的控制策略,问题求解的方法,1.数据驱动方法,procedure generate;begin identify the set S of applicable rules;while S is non-empty do begin select a rule R from S;apply R;if the problem is solved by the application of R then indicate SUCCESS else callgeneraterecursively remove R from S and undo the effect of applying R endend;,假设有包含以下四条规则的产生式系统:R1:如果X能被12整除则X能被6整除;R2:如果X能被20整除则X能被10整除;R3:如果X能被6整除则X能被2整除;R4:如果X能被10整除则X能被5整除;,初始数据库:N能被12整除,N能被20整除,目标是判断N是否能被5整除。,问题求解的方法,R1 R2 R2 R3 R1 R4 S6 R3 R4 R2 R3 R4 R4 S2 R4 R4 S5 S1 S3 S4 图 数据驱动方法的搜索树,执行generate过程:,R1:如果X能被12整除则X能被6整除;R2:如果X能被20整除则X能被10整除;R3:如果X能被6整除则X能被2整除;R4:如果X能被10整除则X能被5整除;,N能被12整除,N能被20整除,(1)S=R1,R2(2)S=R2,R3(3)S=R3,R4(4)S=R4,跟踪求解过程得到使用规则的第一路径是:R1,R2,R3,R4,问题求解的方法,第二路径是:R1,R2,R4 第三路径是:R1,R2,R3,R4 第四路径是:R2,R1,R3,R4 第五路径是:R2,R1,R4 第六路径是:R2,R4,R1 R2 R2 R3 R1 R4 S6 R3 R4 R2 R3 R4 R4 S2 R4 R4 S5 S1 S3 S4 图 数据驱动方法的搜索树,执行generate过程:,R1:如果X能被12整除则X能被6整除;R2:如果X能被20整除则X能被10整除;R3:如果X能被6整除则X能被2整除;R4:如果X能被10整除则X能被5整除;,N能被12整除,N能被20整除,问题求解的方法,2.目标驱动方法,function validate(X:expression):boolean;var result:boolean:begin result:=false;scan the rule base to identify the set of applicable rules S which have X on the right-hand side;if S is empty then ask the user for some rules to add to S;While(result=false)and(S is non-empty)do begin select and remove a rule R from S;C:=the condition part of R;if C is true in the database then result:=true else if C is false in the database then do nothing else if validate(C)is true then result:=true end;validate:=resultend;,问题求解的方法,R1:如果X能被12整除则X能被6整除;R2:如果X能被20整除则X能被10整除;R3:如果X能被6整除则X能被2整除;R4:如果X能被10整除则X能被5整除;,N能被12整除,N能被20整除,Validate(N能被5整除),S=R4,Validate(N能被10整除),S=R2,N能被20整除,问题求解的方法,在很多应用中，条件部分是复合表达式，如：如果C1且C2且C3，则Validate必须修改以适应这种规则，修改的方法如下：,（1）将“if C is false in the database”改为：“if(C1 is false)or(C2 is false)or(C3 is false)”（2）将“if Validate(C)is true”改为：“if(Validate(C1)is true)and(Validate(C2)is true)or(Validate(C3)is true)”,问题求解的方法,3.混合方法,procedure mixed-method;begin repeat let user enter data into the database;call proceduregenerateto generate new facts which are added to the database;callselect-hypothesisto select a goal statement E;callvalidate(E);until the problem is solvedend;,设综合数据库的初始状态为C，B，Z，目标状态为 M，M，M，规则库中有如下规则：r1：CD，L r2：CB，M r3：BM，M r4：ZB，B，M 解决该问题时，可先把初始综合数据库分为三个子库，然后对这三个子库分别应用规则库中的相应规则进行求解。,例：,C,B,Z,C,B,Z,D,L,B,M,M,M,B,B,M,D,L,B,M,M,M,B,M,B,M,M,M,M,M,M,M,M,M,M,M,M,r1,r2,r3,r4,r3,r3,r3,2.3.5 产生式系统的类型,可恢复的产生式系统 是指那种采用回溯控制方式的产生式系统 其求解问题的方法是：当执行某条规则后，如果发现所得到的新的综合数据库不可能求出问题的解，就立即撤消由该规则所产生的结果，使综合数据库恢复到先前的状态，然后再另选别的规则继续求解。它既可以向综合数据库中添加新的内容，又可以从综合数据库中删除或修改老的内容。这种求解问题的方法，更符合人们的一般习惯。,2.3.6 产生式系统的特点,主要优点：自然性：采用“如果，则”的形式，人类的判断性知识基本一致。模块性：规则是规则库中最基本的知识单元，各规则之间只能通过综合数据库发生联系，而不能相互调用，从而增加了规则的模块性。有效性：产生式知识表示法既可以表示确定性知识，又可以表示不确定性知识，既有利于表示启发性知识，又有利于表示过程性知识。一致性：规则库中的所有规则都具有相同的格式，并且综合数据库可被所有规则访问，因此规则库中的规则可以统一处理。,主要缺点：效率较低：各规则之间的联系必须以综合数据库为媒介。并且，其求解过程是一种反复进行的“匹配冲突消解执行”过程。这样的执行方式将导致执行的低效率。不便于表示结构性知识：由于产生式表示中的知识具有一致格式，且规则之间不能相互调用，因此那种具有结构关系或层次关系的知识则很难以自然的方式来表示。,2.3.6 产生式系统的特点,第2章 知识表示,2.1 知识表示与知识表示的概念2.2 一阶谓词逻辑表示法2.3 产生式表示法2.4 语义网络表示法2.5 框架表示法2.6 过程表示法,2.4 语义网络表示法,2.4.1 语义网络的基本概念2.4.2 事务和概念的语义网络表示2.4.3 情况和动作的语义网络表示2.4.4 逻辑关系的语义网络表示2.4.5 语义网络的求解过程2.4.6 语义网络表示法的特征,语义网络是奎廉()1968年在研究人类联想记忆时提出的一种心理学模型，认为记忆是由概念间的联系实现的。随后，奎廉又把它用作知识表示。1972年，西蒙在他的自然语言理解系统中也采用了语义网络表示法。1975年，亨德里克()又对全称量词的表示提出了语义网络分区技术。,什么是语义网络,语义网络是1968年Quillian提出来的，目的是用来描述人对事物的认识，对人脑的功能的模拟。语义网络是一个有向图，其中结点表示个体，而弧表示二个体间的二元关系，弧上标记关系模型名称，单一个体就由一结点表示。,2.4.1 语义网络的基本概念,什么是语义网络 结点：实体，表示各种事物、概念、情况、属性、状态、事件、动作等；弧：语义关系，表示它所连结的两个实体之间的语义联系，它必须带有标识。语义基元 语义网络中最基本的语义单元称为语义基元，可用三元组表示为：（结点1，弧，结点2）基本网元 指一个语义基元对应的有向图,2.4.1 语义网络的基本概念,例如：若有语义基元（A,R,B），其中，A、B分别表示两个结点，R表示A与B之间的某种语义联系，则它所对应的基本网元如下图所示：,A,B,R,2.4.1 语义网络的基本概念,语义网络的简单例子：例2.7 用于一网络表示“鸵鸟是一种鸟”事实的表示：例：“雪的颜色是白的”规则的表示：例：规则R的含义是“如果 A 则 B”,鸵鸟,鸟,是一种,雪,白,颜色,A,B,R,2.4.1 语义网络的基本概念,实例关系：ISA 体现的是“具体与抽象”的概念，含义为“是一个”，表示一个事物是另一个事物的一个实例。例分类关系：AKO 亦称泛化关系，体现的是“子类与超类”的概念，含义为“是一种”，表示一个事物是另一个事物的一种类型。例成员关系：A-Member-of 体现的是“个体与集体”的关系，含义为“是一员”，表示一个事物是另一个事物的一个成员。例,鸟,动物,AKO,张强,共青团员,A-Member-of,人,李刚,ISA,2.4.1 语义网络的基本概念,属性关系：指事物和其属性之间的关系。常用的属性关系有：Have：含义为“有”，表示一个结点具有另一个结点所描述的属性 Can：含义为“能”、“会”，表示一个结点能做另一个结点的事情,2.4.1 语义网络的基本概念,Age:含义为“年龄”，表示一个结点是另一个结点在年龄方面的属性,Part-of：含义为“是一部分”，表示一个事物是另一个事物的一部分。,大脑,人体,Part-of,2.4.1 语义网络的基本概念,例如，“大脑是人体的一部分”,时间关系 指不同事件在其发生时间方面的先后次序关系。常用的时间关系有：Before：含义为“在前”，表示一个事件在另一个事件之前发生 After:含义为“在后”，表示一个事件在另一个事件之后发生,2.4.1 语义网络的基本概念,位置关系 指不同事物在位置方面的关系。常用的位置关系有：Located-on：含义为“在上”，表示某一物体在另一物体之上 Located-at：含义为“在”，表示某一物体所在的位置 Located-under：含义为“在下”，表示某一物体在另一物体之下 Located-inside：含义为“在内”，表示某一物体在另一物体之内；Located-outside：含义为“在外”，表示某一物体在另一物体之外。,书,2.4.1 语义网络的基本概念,相近关系 指不同事物在形状、内容等方面相似或接近。常用的相近关系有：Similar-to：含义为“相似”，表示某一事物与另一事物相似 Near-to：含义为“接近”，表示某一事物与另一事物接近,2.4.1 语义网络的基本概念,用语义网络表示：动物能运动、会吃。鸟是一种动物，鸟有翅膀、会飞。鱼是一种动物，鱼生活在水中、会游泳。,employees person John event1#1 managers manager of tom,isa,isa,object,punching,agent,如：John是雇员，老板是Tom，而John打了 Tom，其语义网络表示：,从属关系,子集合关系：isa,事件,例：machine#12在其构造中使用20次零件#1的事件：,例：Tom的高度是1.7米并且还在增高,用语义网络表示：王强是某公司的经理；理想公司在中关村；王强28岁。,语义网络表示法,主要优点：结构性 把事物的属性以及事物间的各种语义联系显式地表示出来，是一种结构化的知识表示方法。在这种方法中，下层结点可以继承、新增、变异上层结点的属性。联想性 本来是作为人类联想记忆模型提出来的，它着重强调事物间的语义联系，体现了人类的联想思维过程。自索引性 把各接点之间的联系以明确、简洁的方式表示出来，通过与某一结点连结的弧可以很容易的找出与该结点有关的信息，而不必查找整个知识库。这种自索引能力有效的避免搜索时所遇到的组合爆炸问题。自然性 这种带有标识的有向图，可比较直观地把知识表示出来，符合人们表达事物间关系的习惯，并且与自然语言语义网络之间的转换也比较容易实现。,主要缺点：非严格性 没有象谓词那样严格的形式表示体系，一个给定语义网络的含义完全依赖于处理程序对它所进行的解释，通过语义网络所实现的推理不能保证其正确性。复杂性 语义网络表示知识的手段是多种多样的，这虽然对其表示带来了灵活性，但同时也由于表示形式的不一致，使得它的处理增加了复杂性。,语义网络表示法,第2章 知识表示,2.1 知识表示与知识表示的概念2.2 一阶谓词逻辑表示法2.3 产生式表示法2.4 语义网络表示法2.5 框架表示法2.6 过程表示法,2.5 框架表示法,框架表示法是在框架理论的基础上发展起来的一种结构化知识表示方法。框架是一种知识表示模式,1975年由M.Minsky最早作为视觉感知、自然语言对话和其他复杂行为的基础提出的。,框架的基本概念,1.框架的基本结构一类实体的框架提供了一种结构,在这种结构中填入有关新情况的数据时,可以根据以往经验获得的概念对这些数据进行分析和解释。另外,这种框架结构也提供了在一个具体上下文中对特定实体进行预见驱动的处理方式,在这个上下文环境下根据这种结构可以寻找那些预见的信息。存放可预见信息的位置称为槽(slots)。一个框架由若干个槽组成