知识表示方法PPT课件

1,第二章知识表示方法,2.1状态空间法2.2问题归约法2.3谓词逻辑法2.4语义网络法2.5其他方法2.6小结,2,知识表示的基本概念,什么是知识？（专家看法）Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息。Bernstein说知识是由特定领域的描述、关系和过程组成的。Hayes-Roth认为知识是事实、信念和启发式规则。从知识库观点看，知识是某论域中所涉及的各有关方面、状态的一种符号表示。,3,知识知识是人们把实践中获得的信息关联在一起所形成的信息结构，是构成智能的基础。知识信息数据符号知识的特性相对正确性：在一定前提条件下正确。不确定性：知识存在“真假”程度之分。可表示性：知识可数据化形式表示。可利用性：知识就是力量。,4,知识的分类知识可以从不同角度划分，得到不同的分类方法。按照知识的作用范围来划分，知识可以分为常识性知识、领域性知识。按照知识的作用及表示来划分，知识可以分为事实性知识、规则性知识、控制性知识和元知识。按照知识的确定性划分，知识可以分为确定性知识和不确定性知识。按照人类的思维及认识来划分，可分为逻辑性知识和形象性知识。,5,知识的表示就是对人类知识的一种描述，把知识表示成计算机能够处理的数据结构。知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。对知识进行表示的过程就是把知识编码成某种数据结构的过程。知识表示研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储，又考虑知识的使用。,6,知识表示方法可以分为陈述性知识表示和过程性知识表示两大类。陈述性知识表示主要是用来描述事实性知识。这类表示法就是将对象的有关事实陈述出来，并以数据的形式表示。强调事物所涉及的对象是什么，是对事物有关知识的静态描述，是知识的一种显式表达形式。而对于如何使用这些知识，则通过控制策略来决定。过程性知识表示主要用来描述规则性知识和控制结构知识。将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程（如程序）,7,2.1状态空间法（StateSpaceRepresentation）,状态空间表示法就是以“状态空间的形式来表示问题及其搜索过程的一种方法。状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础。,8,2.1.1问题状态描述,1定义状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。是描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：Q=(q0，q1，.，qn)其中每个元素qi(i=0，l，2，n)为状态变量。当给每一个变量以确定的值时，就得到了一个具体的状态。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。算符可分为走步、过程、规则、数学算子、运算符号、逻辑符号等。,2.1状态空间法,9,状态空间：是一个表示该问题全部可能状态及其关系的图.由三部分构成：问题的所有可能初始状态构成的集合S；算符集合F；目标状态集合G。问题的解状态空间的问题求解就是从问题的初始状态集S出发，经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列就构成了问题的一个解。,10,2.状态空间表示概念详释,例如下棋、迷宫及各种游戏。,MiddleState,GoalState,2.1状态空间法,11,例:三数码难题（3puzzleproblem）,初始棋局,目标棋局,2.1状态空间法,12,有向图后继节点（后裔）父辈节点（祖先）代价（cost）c(ni，nj)图的显示说明（已知）图的隐示说明（起始点，推论已知，后继无限）,2.1.2状态图示法图论术语,A,B,2.1状态空间法,13,2.1.3状态空间表示举例,产生式系统（productionsystem）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,2.1状态空间法,14,状态空间表示举例,例：推销员旅行问题（运筹学图论最短路径）例：猴子和香蕉问题,2.1状态空间法,在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?上图表示出猴子、香蕉和箱子在房间内的相对位置。,15,解题过程,用一个四元表列（W，x，Y，z）来表示这个问题状态.W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0,这个问题的操作（算符）如下：2goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）,2.1状态空间法,16,pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）,climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox（W，1，W，z）,2.1状态空间法,17,grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）,该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp,2.1状态空间法,18,2.1状态空间法,19,猴子和香蕉问题自动演示：,2.1状态空间法,20,二阶Hanoi塔问题,已知3个柱子l、2、3和两个盘子A、B(A比B小)。初始状态下，A、B依次放在1柱上；目标状态是A、B依次放在柱子3上。条件是每次可移动一个盘子，盘子上方是空顶方可移动，而且任何时候都不允许大盘在小盘之上。,21,第一步：用状态空间表示问题定义问题状态的描述形式设用Sk=(SkA，SkB)表示问题的状态，SkA表示盘子A所在的柱号，SkB表示盘子B所在的柱号。用状态描述形式把问题的所有可能的状态都表示出来。本问题共有九种可能状态:S0=(1，1)，S1=(1，2)，S2=(1，3)S3=(2，1)，S4=(2，2)，S5=(2，3)S6=(3，1)，S7=(3，2)，S8=(3，3)问题的初始状态集合为S=S0，目标状态集合为G=S8。,22,23,定义一组算符F,算符A(i，j)表示把盘子A从第i号柱子移到第j号柱子上的操作；,算符B(i，j)表示把盘子B从第i号柱子移到第j号柱子上的操作。,算符组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),问题的状态空间(S，F，G)构造完成。,24,第二步：问题求解根据状态空间的9种可能状态和12种算符，构造它的状态空间图：,在状态空间图中，从初始节点(1，1)(状态S0)到目标节点(3，3)(状态S8)的任何一条通路都是问题的一个解。最短的路径长度是3，它由3个算符组成：A(1，2)、B(1，3)、A(2，3)。,25,2.2问题归约法（ProblemReductionRepresentation）,26,问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。,问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2.2问题规约法,27,2.2.1问题归约描述（ProblemReductionDescription）,梵塔难题,2.2问题规约法,28,解题过程（3个圆盘问题）,2.2问题规约法,29,本原问题：是指那种不能或不需要再进行分解或变换，且可以直接解答的问题。归约：把一个复杂问题分解或变换为一组本原问题的过程。问题的分解：是指把一个复杂问题分解为若干个子问题的过程。问题的解是所有子问题解的“与”，即只有当所有子问题都有解时，原问题才有解。,30,问题规约的实质目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题规约为一个平凡的本原问题集合.问题规约法应用算符把问题描述变换为子问题描述比状态空间法更通用的问题求解方法,31,2.2.2与或图表示,用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。1.与图、或图、与或图,2.2问题规约法,32,2.2问题规约法,33,2.一些关于与或图的术语,2.2问题规约法,34,3.定义,2.2问题规约法,35,不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。与或图构成规则,2.2问题规约法,36,梵塔问题归约图,2.2问题规约法,37,2.3谓词逻辑法,谓词逻辑表示法以数理逻辑为基础，是目前为止能够表达人类思维活动规律的一种最精确的形式语言，最早应用于AI。1.知识的谓词逻辑表示谓词公式=谓词+连接符对于事实性知识，谓词逻辑的表示法通常是由以合取、析取符号（、）连接形成的谓词公式来表示。例如：对于事实性知识“张三是学生，李四也是学生”可以表示为：Is_student(张三)Is_student(李四)对于规则性知识，谓词逻辑表示法通常是由以蕴涵符号()连接形成的谓词公式来表示。例如：对于规则：“如果x,则y”可以表示为：xy,38,2.3.1谓词演算1.语法和语义基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号原子公式连词和量词(Connective&Quantifiers)（1）连词与、合取：用连词把几个公式连接起来而构成合取式。或、析取：用连词把几个公式连接起来而构成析取式。蕴涵：用连词连接两个公式所构成蕴涵式。等价：若两个公式，无论如何解释，其真值表相同，则称此两合式公式等价。等价连接词为非：否定，可用、表示。(2)量词全称量词：若一个原子公式P(x)，对于所有可能变量x都具有T值，则用(x)P(x)表示。存在量词：若一个原子公式P(x)，至少有一个变元x，可使P(x)为T值，则用(x)P(x)表示。量化变元被量化了的变元x称为约束变元。,39,2.3.2谓词公式原子公式的的定义：由若干谓词符号和项（常量符号、变量符号或函数符号）组成的谓词演算。原子公式是谓词演算基本积木块。分子谓词公式：可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,2.3谓词逻辑法,例如，要表示“机器人(ROBOT)在号房间(r1)内”，可以应用原子公式：,40,原子谓词公式P(x1,x2,xn)原子谓词公式。Pn元谓词x1,x2,xn客体变量或变元。分子谓词公式用连词（、）把原子谓词公式组成复合谓词公式，即分子谓词公式。,41,设有下列事实性知识：张晓辉是一名计算机系的学生，但他不喜欢编程序。李晓鹏比他父亲长得高。用谓词公式表示这些知识。,解第一步：定义谓词：COMPUTER(x)：x是计算机系的学生LIKE(x，y)：x喜欢yHIGHER(x，y)：x比y长得高,42,定义个体：张晓辉(zhangxh)，编程序(programming)，李晓鹏(1ixp)，father(lixp)表示李晓鹏的父亲。,第三步：根据语义，用逻辑连接符将它们连接起来，就得到了表示上述事实性知识的谓词公式：COMPUTER(zhangxh)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,按照第二步和第三步的要求，可以得到“人人爱劳动”用谓词公式表示为：(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有性别命题：,47,先给出原子公式，然后写出命题：,(2)任何整数或者为正或者为负。原子公式：I（x）x是整数；P（x）x是正数；N（x）x是负数命题：,48,先给出原子公式，然后写出命题：,(3)有些聪明者并不能阅读。原子公式：R(x)x能阅读；I(x)x是聪明的；命题：,49,先给出原子公式，然后写出命题：,(4)聪明者就能阅读。原子公式：R(x)x能阅读；I(x)x是聪明的；命题：或：,50,合式公式定义：原子谓词公式是合式公式。若A为合式公式，则A也是一个合式公式。若A和B都是合式公式，则(AB),(AB),(AB),(AB)都是合式公式。若A是合式公式，x为A中的自由变元，则(x)A，(x)A是合式公式。只有按上述规则求得的那些公式才是合式公式。,51,合式公式中连词和量词的优先顺序如右所示，同级者从左至右作用，可用括号改变作用次序。,52,2.合式公式的性质,53,常用等价关系,54,常用等价关系,55,2.3.3置换与合一,谓词逻辑中的两个重要推理规则：假元推理全称化推理,56,2.3谓词逻辑法2.3.3置换与合一,例：综合应用假元推理和全称化推理，有：,57,2.3.3置换与合一,上例中使用了置换A/x。置换定义：一个置换s是形如t1/x1,t2/x2,tn/xn的有限集合，其中t1,t2,tn是项（变量、常量或函数），x1,x2,xn是互不相同的变量，ti/xi表示用ti置换（替换）xi。对谓词表达式E实施s置换的结果表示为Es。没有元素的置换称为空置换，记为。,58,置换举例,设有表达式Px,f(y),B，对于置换：s1=z/x,w/ys2=A/y分别有：Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),B,59,2.3.3置换与合一,合一定义：对于谓词表达式集Ei，若存在一个置换s，可使E1s=E2s=,=Ens，则称s为Ei的合一者，称Ei为可合一的。最一般合一者：如果s是Ei的任一合一者，又存在某个s，使得Eis=Eigs成立，则称g为Ei的最一般合一者。,60,合一者、最一般合一者举例,设有表达式集Ei=Px,f(y),B，Px,f(B),B，该表达式集的合一者：s1=B/y，s2=w/x,B/ys1=B/y是该表达式集的最一般合一者。（为什么？）,61,合一者、最一般合一者举例,因为对于Ei的任一个合一者s，均存在一个合一者s,使得Eis=Eigs成立。存在一个合一者s=w/x,使得Eis2=Eis1s成立；存在一个合一者s=，使得Eis1=Eis1s成立。,62,例将教材上的梵塔难题（由A、B、C三个盘简化为只有A、B两个盘）用谓词逻辑法表示。,L（x,y）表示盘B在柱x，盘A在柱y；E（x,y）表示x等于y则上述问题的谓词逻辑法表示为：表示事实型知识，即初始时盘B和盘A均在柱1；,63,例将教材上的梵塔难题（由A、B、C三个盘简化为只有A、B两个盘）用谓词逻辑法表示。,表示规则型知识。表示事实型知识，即通过推理达到的事实：盘B和盘A均在柱3,64,例将教材上的梵塔难题（由A、B、C三个盘简化为只有A、B两个盘）用谓词逻辑法表示。,在上述基础上，应用置换和推理即可表达解决问题的知识如下：,65,例将教材上的梵塔难题（由A、B、C三个盘简化为只有A、B两个盘）用谓词逻辑法表示。,在上述基础上，应用置换和推理即可表达解决问题的知识如下：,66,例将教材上的梵塔难题（由A、B、C三个盘简化为只有A、B两个盘）用谓词逻辑法表示。,在上述基础上，应用置换和推理即可表达解决问题的知识如下：,67,语义网络是1968年J.R.Quillian在研究人类联想记忆时提出的心理学模型，认为记忆是由概念间的联系实现的。随后在自然语言理解系统中用做知识表示，在ES中语义网络首先由PROSPECTOR实现。目前，语义网络已成为AI中应用较多的一种知识表示方法。,2.4语义网络表示法,68,谓词逻辑与语义网络等效,2.4语义网络法,69,多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。,2.4语义网络法,70,语义网络是通过概念及其语义关系来表示知识的一种网络图，它是一个带标注的有向图，由节点和弧构成。,2.4.1语义网络的概念及其结构,节点：表示不同对象（概念、事物、属性、情况、动作、状态等）；可以带有表征对象特性的若干属性。,弧：是有方向、有标注的。方向体现节点间的主次关系，标注表示节点间的语义关系。,71,其中：A和B分别代表节点，R表示A和B之间的某种语义联系。,一个最简单的语义网络可由一个三元组表示：(节点1，弧，节点2)它可用有向图表示，称做基本网元。,72,当把多个基本网元用相应的语义联系关联在一起时，就可得到一个语义网络。,在语义网络中，节点还可以是一个语义子网络，所以，语义网络实质上可以是一种多层次的嵌套结构。,73,2.4.2语义网络中的基本语义联系,74,75,2.4.3语义网络表示知识的方法,事实性知识的表示,76,2.情况和动作的表示,例：一只名叫“神飞”的小燕子从三月到十一月占有一个巢。,77,例：张三送给李四一支钢笔。,78,3.逻辑关系的表示,例：参加比赛者有工人、有干部、有高的、有低的。,79,例：每个学生都学习了一门程序设计语言。,80,4.规则性知识的表示,81,2.4.4语义网络表示知识的步骤,确定问题中的所有对象及其属性；分析并确定语义网络中所论对象间的关系；根据语义网络中所涉及的关系，对节点及弧进行整理。,82,2.4.5举例,83,84,85,2.4.6语义网络知识表示下的推理,语义网络表示的问题求解系统由两部分构成：语义网络知识库：存放许多已知事实的语义网络。推理机：求解问题的程序。,语义网络系统中的推理方法一般有两种：匹配推理：根据待求解问题，构造一个带有空标注的网络片段，再到知识库中寻找可匹配的语义网络，求得问题的解答。继承推理：下层节点继承上层节点的属性或方法。,86,例2.10匹配推理,87,2.4.7语义网络表示法的特点,结构性：结构化的知识表示方法。能将事物间的语义联系显式地表示出来；下层概念节点可以继承、补充、变异上层概念的属性，实现信息的共享。自然性：带有标识的有向图，自然语言转换容易。联想性：联想记忆模型。非严格性：没有公认的形式表示体系。,88,2.5框架表示法,框架表示法由M.Minsky1975年提出，它针对人们在理解事物情景时的心理学模型，论述了人们理解问题的一种思想方法。,框架表示法最早用作视觉感知、自然语言对话等问题的知识表示,目前已作为一种通用数据结构来表示知识对象。,89,框架理论认为，人脑中存储有大量事物的典型情景，这是人们对现实世界中各种事物的认识，这些典型情景都是以一种类似于框架的基本知识结构存储在记忆中的。当面临一种新事物情景时，就从记忆中找出一个合适的框架并根据实际情况对其细节加以修改、补充，从而形成对当前事物情景的认识。,2.5.1框架理论,90,当一个人将要走进一个教室之前，他就可以想像这个教室一定有四面墙，有门、窗、天花板和地板，还有黑板、讲台、课桌、坐凳等，尽管他对这个教室的具体细节如教室的大小、门窗的个数等还不清楚，但对教室的基本结构是可以预见的。,例如：,他之所以能够做到这一点，是由于在以前的认识活动中已在其头脑中建立起了有关“教室”这一概念的基本框架。这一基本框架不仅指出了相应事物的名称(教室)，而且还指出了事物各有关方面的属性(墙、门、窗等)，通过对该框架的查找就很容易得到有关教室的特征。,在他进入教室之后，经观察得到了教室的大小、门窗的个数等细节，把这些数据填人到教室框架中，就得到教室框架的一个具体实例，这是他关于这个教室的视觉印象，称为实例框架。,91,2.5.2框架的定义及组成,1.框架的定义框架是用于描述静态对象的通用数据结构，该对象用“对象属性属性值”表示。,框架由若干个槽（Slot）组成，槽用于描述对象的属性。,槽又可由槽值或若干个侧面组成，侧面用于描述相应属性的一个方面。,侧面可由一个或多个侧面值组成。,92,（数据库表字段）|,2.框架的组成,93,框架名：主机品牌：联想1+1生产厂商：北京联想集团公司CPU：品牌：Intel型号：奔腾933主板：品牌：QDI型号：ATXVA5内存：品牌：现代型号：SDRAM容量：128MB硬盘：品牌：Seagate型号：ST320423A容量：20GB,例：“计算机主机”框架,94,2.5.3用框架表示知识的步骤,分析对象及其