第二章知识表示方法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第二章知识表示方法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 知识 表示 方法 课件
- 资源描述:
-
1、第二章第二章 知识表示方法知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结2知识表示的基本概念l什么是知识?(专家看法)Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说,知识是经过加工的信息。Bernstein说知识是由特定领域的描述、关系和过程组成的。Hayes-Roth认为知识是事实、信念和启发式规则。从知识库观点看,知识是某论域中所涉及的各有关方面、状态的一种符号表示。3l知识知识 知识是人们把实践中获得的信息关联在一起所形成的信息结构,是构成智能的基础。知识信息数据符号l知识的特性知识的特性相对正确
2、性:在一定前提条件下正确。不确定性:知识存在“真假”程度之分。可表示性:知识可数据化形式表示。可利用性:知识就是力量。4l 知识的分类知识的分类知识可以从不同角度划分,得到不同的分类方法。知识可以从不同角度划分,得到不同的分类方法。按照知识的作用范围来划分,知识可以分为常识性知识、领域性知识。按照知识的作用及表示来划分,知识可以分为事实性知识、规则性知识、控制性知识和元知识。按照知识的确定性划分,知识可以分为确定性知识和不确定性知识。按照人类的思维及认识来划分,可分为逻辑性知识和形象性知识。5l知识的表示就是对人类知识的一种描述,把知识表示成计算机能够处理的数据结构。l知识表示是研究用机器表示
3、知识的可行性、有效性的一般方法,是一种数据结构与控制结构的统一体,既考虑知识的存储又考虑知识的使用。l对知识进行表示的过程就是把知识编码成某种数据结构的过程。l知识表示研究用机器表示知识的可行性、有效性的一般方法,是一种数据结构与控制结构的统一体,既考虑知识的存储,又考虑知识的使用。6l知识表示方法知识表示方法可以分为可以分为陈述性知识表示陈述性知识表示和和过程性知识过程性知识表示表示两大类。两大类。l陈述性知识表示主要是用来描述事实性知识。这类表示法就是将对象的有关事实陈述出来,并以数据的形式表示。强调事物所涉及的对象是什么,是对事物有关知识的静态描述,是知识的一种显式表达形式。而对于如何使
4、用这些知识,则通过控制策略来决定。l过程性知识表示主要用来描述规则性知识和控制结构知识。将有关某一问题领域的知识,连同如何使用这些知识的方法,均隐式地表达为一个求解问题的过程(如程序)72.1状态空间法状态空间法(State Space Representation)q状态空间表示法就是以“状态空间的形式来表示问题及其搜索过程的一种方法。q状态空间表示法是人工智能中最基本的形式化方法,是讨论问题求解技术的基础。82.1.1 问题状态描述问题状态描述1 定义 l状态:描述某类不同事物间的差别而引入的一组最少变量q0,q1,qn的有序集合。是描述问题求解过程中不同时刻状况的数据 结构。一般用一组变
5、量的有序集合表示:Q=(q0,q1,.,qn)其中每个元素qi(i=0,l,2,n)为状态变量。当给每一个变量以确定的值时,就得到了一个具体的状态。l算符:使问题从一种状态变化为另一种状态的手段称为操作符或算符。算符可分为走步、过程、规则、数学算子、运算符号、逻辑符号等。2.1 状态空间法9l状态空间:是一个表示该问题全部可能状态及其关系的图.由三部分构成:问题的所有可能初始状态构成的集合S;算符集合F;目标状态集合G。l问题的解问题的解状态空间的问题求解就是从问题的初始状态集S出发,经过一系列的算符运算,到达目标状态。由初始状态到目标状态所用算符的序列就构成了问题的一个解。102.状态空间表
6、示概念详释状态空间表示概念详释l例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1 状态空间法11例例:三数码难题三数码难题(3 puzzle problem)123123123312312312初始棋局目标棋局2.1 状态空间法12l有向图l后继节点(后裔)l父辈节点(祖先)l代价(cost)c(ni,nj)l图的显示说明(已知)l图的隐示说明(起始点,推论已知,后继无限)2.1.2 状态图示法状态图示法 图论术语图论术语AB2.1 状态空间法132.1.3 状态空间表示举例状态空间表示举例l产生式系统(production system)一个
7、总数据库:它含有与具体任务有关的信息随着应用情况的不同,这些数据库可能简单,或许复杂。一套规则:它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略:它确定应该采用哪一条适用规则,而且当数据库的终止条件满足时,就停止计算。2.1 状态空间法14 状态空间表示举例l例:推销员旅行问题(运筹学图论最短路径)l例:猴子和香蕉问题2.1 状态空间法在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方,但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?上图表示出猴子、香蕉和箱子在房间内的相对位置。
8、15解题过程解题过程l 用一个四元表列(W,x,Y,z)来表示这个问题状态.lW猴子的水平位置x当猴子在箱子顶上时取x=1;否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1;否则取z=0 l这个问题的操作(算符)如下:2 goto(U)表示猴子走到水平位置U或者用产生式规则表示为(W,0,Y,z)goto(U)(U,0,Y,z)2.1 状态空间法16lpushbox(V)猴子把箱子推到水平位置V,即有(W,0,W,z)pushbox(V)(V,0,V,z)lclimbbox猴子爬上箱顶,即有(W,0,W,z)climbbox (W,1,W,z)2.1 状态空间法17lgrasp猴子摘到香
9、蕉,即有(c,1,c,0)grasp (c,1,c,1)l该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp2.1 状态空间法18(b,1,b,0)(U,0,b,0)(V,0,V,0)(c,1,c,0)(U,0,V,0)(c,1,c,1)(a,0,b,0)目标状态目标状态goto(U)goto(U)U=b,climbboxgoto(U)U=bpushbox(V)猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto(U)U=V2.1 状态空间法19猴子和香蕉问题自动演示:猴子和香蕉问题自动演示:猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉
10、箱子箱子 Ha!Ha!2.1 状态空间法20二阶二阶Hanoi塔问题塔问题l已知3个柱子l、2、3和两个盘子A、B(A比B小)。l初始状态下,A、B依次放在1柱上;目标状态是A、B依次放在柱子3上。l条件是每次可移动一个盘子,盘子上方是空顶方可移动,而且任何时候都不允许大盘在小盘之上。21l第一步:用状态空间表示问题l定义问题状态的描述形式l 设用Sk=(SkA,SkB)表示问题的状态,SkA表示盘子A所在的柱号,SkB表示盘子B所在的柱号。l用状态描述形式把问题的所有可能的状态都表示出来。本问题共有九种可能状态:l S0=(1,1),S1=(1,2),S2=(1,3)l S3=(2,1),S
11、4=(2,2),S5=(2,3)l S6=(3,1),S7=(3,2),S8=(3,3)l 问题的初始状态集合为S=S0,目标状态集合为G=S8。2223l定义一组算符Fv算符A(i,j)表示把盘子A从第i号柱子移到第j号柱子上的操作;v算符B(i,j)表示把盘子B从第i号柱子移到第j号柱子上的操作。v算符组F中共有12个算符:A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)v问题的状态空间(S,F,G)构造完成。24l第二步:问题求解根据状态空间的9种可能状态和12种算符,构造
12、它的状态空间图:在状态空间图中,从初始节点(1,1)(状态S0)到目标节点(3,3)(状态S8)的任何一条通路都是问题的一个解。最短的路径长度是3,它由3个算符组成:A(1,2)、B(1,3)、A(2,3)。252.2 问题归约法问题归约法(Problem Reduction Representation)子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题26l 问题归约表示的组成部分:一个初始问题描述;一套把问题变换为子问题的操作符;一套本原问题描述。l问题归约的实质:从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题归约为一个平凡的本原问
13、题集合。2.2 问题规约法272.2.1 问题归约描述问题归约描述(Problem Reduction Description)l梵塔难题123CBA2.2 问题规约法28解题过程(解题过程(3个圆盘问题)个圆盘问题)1231231231231231231231232.2 问题规约法29 二阶梵塔3阶梵塔 单圆盘移动 二阶梵塔l本原问题:是指那种不能或不需要再进行分解或变换,且可以直接解答的问题。l归约:把一个复杂问题分解或变换为一组本原问题的过程。l问题的分解:是指把一个复杂问题分解为若干个子问题的过程。问题的解是所有子问题解的“与”,即只有当所有子问题都有解时,原问题才有解。30问题规约的
14、实质l目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题规约为一个平凡的本原问题集合.l问题规约法应用算符把问题描述变换为子问题描述l比状态空间法更通用的问题求解方法312.2.2与或图表示与或图表示 用一个类似图的结构来表示把问题归约为后继问题的替换集合,这种结构图叫做问题归约图,或叫与或图。l 1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图322.2 问题规约法BCDEFGAHMBCDEFGAN332.一些关于与或图的术语一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点343.定义定义2.2 问题
15、规约法与或图例子与或图例子ttttttttt(a)(b)有解节点无解节点终叶节点35l不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点,此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点,此非终叶节点才是不可解的。l与或图构成规则2.2 问题规约法36梵塔问题归约图梵塔问题归约图2.2 问题规约法372.3 谓词逻辑法谓词逻辑法谓词逻辑表示法谓词逻辑表示法以以数理逻辑数理逻辑为基础,是目前为止能够表达人类思维活动规律为基础,是目前为止能够表达人类思维活动规律的一种最精确的的一种最精确的形式语言形式语言,最早应用于最早应
16、用于AI。1.知识的谓词逻辑表示知识的谓词逻辑表示谓词公式谓词公式=谓词谓词+连接符连接符对于对于事实性知识事实性知识,谓词逻辑的表示法通常是由以,谓词逻辑的表示法通常是由以合取、析取符号合取、析取符号(、)连接形成的谓词公式来表示。连接形成的谓词公式来表示。例如:例如:对于事实性知识对于事实性知识“张三是学生,李四也是学生张三是学生,李四也是学生”可以表示为:可以表示为:Is_student(张三张三)Is_student(李四李四)对于对于规则性知识规则性知识,谓词逻辑表示法通常是由以,谓词逻辑表示法通常是由以蕴涵符号蕴涵符号()连接形成的谓词连接形成的谓词公式来表示。公式来表示。例如例如
17、:对于规则:对于规则:“如果如果x,则则y”可以表示为:可以表示为:xy382.3.1 谓词演算 1.语法和语义l基本符号:谓词符号、变量符号、函数符号、常量符号、括号和逗号l原子公式l连词和量词(Connective&Quantifiers)(1)连词与、合取:与、合取:用连词把几个公式连接起来而构成合取式。或、析取:或、析取:用连词把几个公式连接起来而构成析取式。蕴涵:蕴涵:用连词 连接两个公式所构成蕴涵式。等价:若等价:若两个公式,无论如何解释,其真值表相同,则称此两合式公式等价。等价连接词为非:非:否定,可用、表示。(2)量词 全称量词:全称量词:若一个原子公式P(x),对于所有可能变
18、量x都具有T值,则用(x)P(x)表示。存在量词:存在量词:若一个原子公式P(x),至少有一个变元x,可使P(x)为T值,则用(x)P(x)表示。量化变元量化变元被量化了的变元x称为约束变元。392.3.2 谓词公式l原子公式的的定义:由若干谓词符号和项(常量符号、变量符号或函数符号)组成的谓词演算。原子公式是谓词演算基本积木块。l分子谓词公式:可以用连词把原子谓词公式组成复合谓词公式,并把它叫做分子谓词公式。2.3 谓词逻辑法例如,要表示“机器人(ROBOT)在号房间(r1)内”,可以应用原子公式:40l原子谓词公式原子谓词公式 P(x1,x2,xn)原子谓词公式。P n元谓词 x1,x2,
19、xn 客体变量或变元。l分子谓词公式分子谓词公式 用连词(、)把原子谓词公式组成复合谓词公式,即分子谓词公式。41设有下列事实性知识:张晓辉是一名计算机系的学生,但他不喜欢编程序。李晓鹏比他父亲长得高。用谓词公式表示这些知识。解 第一步:定义谓词:COMPUTER(x):x是计算机系的学生 LIKE(x,y):x喜欢y HIGHER(x,y):x比y长得高42定义个体:张晓辉(zhangxh),编程序(programming),李晓鹏(1ixp),father(lixp)表示李晓鹏的父亲。第三步:根据语义,用逻辑连接符将它们连接起来,就得到了表示上述事实性知识的谓词公式:COMPUTER(zh
20、angxh)LIKE(zhangxh,programming)HIGHER(1ixp,father(1ixp)第二步:将个体代入谓词中:COMPUTER(zhangxh),LIKE(zhangxh,programming),HIGHER(lixp,father(lixp)43下列是一些规则性知识:人人爱劳动。自然数都是大于零的整数。所有整数不是偶数就是奇数。用谓词公式表示这些知识。解解 定义谓词:MAN(x):x是人;LOVE(x,y):x爱y;N(x):x是自然数;GZ(x):x大于零。I(x):x是整数;E(x):x是偶数;O(x):x是奇数;44按照第二步和第三步的要求,可以得到“人人爱
21、劳动”用谓词公式表示为:(Vx)(MAN(x)LOVE(x,labour)“自然数都是大于零的整数”表示为:(Vx)(N(x)GZ(x)I(x)“所有的整数不是偶数就是奇数”表示为:(Vx)(I(x)E(x)O(x)45用谓词表示以下命题用谓词表示以下命题(1)人都有姓名和性别。(2)任何整数或者为正或者为负。(3)有些聪明者并不能阅读。(4)聪明者就能阅读。46先给出原子公式,然后写出命题:先给出原子公式,然后写出命题:(1)人都有姓名和性别。原子公式:P(x)x是人;N(x)x有姓名;S(x)x有性别命题:()()()()xP xN xS x47先给出原子公式,然后写出命题:先给出原子公式
展开阅读全文