智能控制-第二章知识表示方法.ppt

第二章 知识表示方法,2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结,中南大学 智能系统与智能软件研究所,数据与信息 数据用一组符号及其组合表示的信息 数据和信息是两个密切相关的概念：数据是信息的载体和表示；信息是数据在特定场合下的具体含义。数据和信息又是两个不同的概念：知识 人们通过体验、学习或联想而知晓的对客观世界规律性的认识。,知识及其表示的有关概念：,中南大学 智能系统与智能软件研究所,3.知识的特性,相对正确性不确定性可表示性和可利用性,4.知识的分类,从作用范围来划分：常识性、领域性从知识的作用及表示来划分：事实性、过程性、控制性从知识的确定性来划分：确定性、不确定性从知识的结构及表现形式来划分：逻辑性、形象性,中南大学 智能系统与智能软件研究所,知识表示对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。在选择知识的表示方法时，可从以下几个方面进行考虑：（1）充分表示领域知识；（2）有利于对知识的利用；（3）便于对知识的组织、维护与管理；（4）便于理解和实现。,5.知识的表示,中南大学 智能系统与智能软件研究所,2.1 状态空间法（State Space Representation）,问题求解技术主要包括两个方面：问题的表示求解的方法状态空间法状态（state）:表示问题解法中每一步问题状况的数据结构算符（operator):把问题从一种状态变换为另一种状态的手段状态空间方法:基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的,中南大学 智能系统与智能软件研究所,问题状态描述,定义状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合:,2.1 状态空间法,算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。,问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。,中南大学 智能系统与智能软件研究所,2.状态空间表示概念详释,状态空间法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的实验序列，直至达到目标状态止。例如下棋、迷宫及各种游戏。,2.1 状态空间法,中南大学 智能系统与智能软件研究所,例:三数码难题（3 puzzle problem）,初始棋局,目标棋局,2.1 状态空间法,中南大学 智能系统与智能软件研究所,有向图 一对节点用弧线连接起来，从一个节点指向另一个节点,这种图叫做有向图。路径 某个节点序列（ni1，ni2，nik）当 j=2，3，k时，如果对于每一个ni，j-1都有一个后继节点ni，j存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价 用C（ni，nj）来表示从节点ni指向节点nj的那段弧线的代价(cost)。两点间路径的代价等于连接该路径上各节点的所有弧线代价之和。,2.1.2 状态图示法,2.1 状态空间法,中南大学 智能系统与智能软件研究所,图的隐式说明 节点的无限集合si作为起始节点是已知的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。,图的显式说明 对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。,中南大学 智能系统与智能软件研究所,2.1.3 状态空间表示举例,产生式系统（production system）一个总数据库（Global Database)：它含有与具体任务有关的信息。随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,2.1 状态空间法,中南大学 智能系统与智能软件研究所,状态空间表示举例,例：猴子和香蕉问题,2.1 状态空间法,中南大学 智能系统与智能软件研究所,解题过程：,用一个四元表列（W，x，Y，z）来表示这个问题状态.W 猴子的水平位置x 当猴子在箱子顶上时取 x=1；否则取 x=0 Y 箱子的水平位置z 当猴子摘到香蕉时取 z=1；否则取 z=0,这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置U，或者用产生式规则表示为：（W，0，Y，z）goto（U）（U，0，Y，z）,2.1 状态空间法,中南大学 智能系统与智能软件研究所,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 状态空间法,应当注意的是，要应用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。,应用算符climbbox的先决条件是什么？,中南大学 智能系统与智能软件研究所,grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）,令初始状态为(a，0，b，0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图，如下图所示。从图不难看出，把该初始状态变换为目标状态的操作序列为：goto(b),pushbox(c),climbbox,grasp,2.1 状态空间法,中南大学 智能系统与智能软件研究所,(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，climbbox,goto（U）,U=b,pushbox（V）,猴子与香蕉问题的状态空间图,goto（U）,U=V,初始状态,grasp,V=c,climbbox,2.1 状态空间法,中南大学 智能系统与智能软件研究所,猴子和香蕉问题自动演示：,2.1 状态空间法,中南大学 智能系统与智能软件研究所,2.2 问题归约法（Problem Reduction Representation）问题归约法思想 先把问题分解为子问题及子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答,中南大学 智能系统与智能软件研究所,问题归约表示的组成部分：一个初始问题描述；一套把初始问题变换为子问题的操作符；一套本原问题描述。,问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2.2 问题归约法,中南大学 智能系统与智能软件研究所,2.2.1 问题归约描述（Problem Reduction Description）,梵塔难题(Tower of Hanoi Puzzle),2.2 问题归约法,中南大学 智能系统与智能软件研究所,3圆盘梵塔难题：,2.2 问题归约法,中南大学 智能系统与智能软件研究所,解题过程：,把原始梵塔难题归约（简化）为下列3个子难题：移动圆盘A和B至柱子2的双圆盘难题；移动圆盘C至柱子3的单圆盘难题；移动圆盘A和B至柱子3的双圆盘难题。,中南大学 智能系统与智能软件研究所,解题过程（3圆盘难题）,2.2 问题归约法,中南大学 智能系统与智能软件研究所,梵塔难题归约图（与或图）,2.2 问题归约法,中南大学 智能系统与智能软件研究所,多圆盘梵塔难题演示,2.2 问题归约法,中南大学 智能系统与智能软件研究所,2.2.2 与或图表示,1.与图、或图、与或图 一般，用一个似图结构来表示把问题归约为后继问题的替换集合，这一似图结构叫做问题归约图，或叫与或图。如下所示,2.2 问题归约法,中南大学 智能系统与智能软件研究所,与或图,2.2 问题归约法,中南大学 智能系统与智能软件研究所,2.一些关于与或图的术语,2.2 问题归约法,中南大学 智能系统与智能软件研究所,一些关于与或图的术语,父节点、子（后继）节点、弧线起始节点：对应于原始问题描述的节点终叶节点：对应于本原问题的节点或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B，C）和（D，E，F）。各个节点之间用一段小圆弧连接标记。与或图：由与节点及或节点组成的结构图。,2.2 问题归约法,中南大学 智能系统与智能软件研究所,3.定义可解节点的一般定义,终叶节点是可解节点(因为它们与本原问题相关联)。如果某个非终叶节点含有或后继节点，那么只要有一个后继节点是可解的时，此非终叶节点就是可解的。如果某个非终叶节点含有与后继节点，那么只有其全部后继节点为可解时，此非终叶节点才是可解的。,2.2 问题归约法,中南大学 智能系统与智能软件研究所,没有后裔的非终叶节点为不可解节点。如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。如果某个非终叶节点含有与后继节点，那么只要当其后裔有一个为不可解时，此非终叶节点就是不可解的。,不可解节点的一般定义,2.2 问题归约法,中南大学 智能系统与智能软件研究所,如图所示,2.2 问题归约法,中南大学 智能系统与智能软件研究所,与或图构成规则,（1）与或图中的每个节点代表一个要解决的单一问题或问题集合。起始节点对应于原始问题。（2）对应于本原问题的节点，叫做终叶节点。（3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合，这些子问题节点叫做或节点。（4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点,这些子问题节点叫做与节点。,2.2 问题归约法,中南大学 智能系统与智能软件研究所,2.3 谓词逻辑法,逻辑语句：一种形式语言，它能够把逻辑论证符号化，并用于证明定理，求解问题。形式语言：严格地按照相关领域的特定规则，以数学符号（符号串）形式描述该领域有关客体的表达式。,2.3.1 谓词演算 1.语法和语义基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号,MARRIED(father(LI),mother(LI),中南大学 智能系统与智能软件研究所,原子公式：由若干谓词符号和项组成的谓词演算。原子公式是谓词演算的基本积木块。,如:INROOM(ROBOT,r1)（机器人在1号房间内）,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,2.连词和量词(Connective&Quantifiers)连词(,=,)与及合取（conjunction)：用连词把几个公式连接起来而构成的公式。合取项是合取式的每个组成部分。,例：LIKE(I，MUSIC)LIKE(I，PAINTING)（我喜爱音乐和绘画。）,LIVES(L1，HOUSE-1)COLOR(HOUSE-1，YELLOW)（李住在一幢黄色的房子。）,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,例：PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL)（李力打篮球或踢足球。）,或及析取（disjunction）：用连词把几个公式连接起来而构成的公式。析取项是析取式的每个组成部分,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,蕴涵（Implication）：“=”表示“如果那么”（IFTHEN）关系，其所构成的公式叫做蕴涵。蕴涵的左式叫做前件,后式叫做后件。例：RUNS(LIUHUA,FASTEST)=WINS(LIUHUA,CHAMPION),非（Not）：表示否定，、均可表示,用来否定一个公式的真值。例：INROOM(ROBOT,r2),2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,以上讲的是命题演算(谓词演算的一个子集)，但它缺乏用有效的方法来表达多个命题的能力，如：,“所有机器人都是灰色的”可以表示为：(x)ROBOT(x)=COLOR(x,GRAY)但命题演算就无法表示，所以需要使公式中的命题带有变量。,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,量词 全称量词（Universal Quantifier）：若一个原子公式P（x），对于所有可能变量 x都具有T值，则用（x）P（x）表示,存在量词（Existential Quantifier）,若一个原子公式P（x），至少有一个变元x，可使P（x）为T值，则用（x）P（x）表示。,例：(x)INROOM(x,r1)（1号房间内有个物体）,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,2.3.2 谓词公式原子公式的的定义用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。分子谓词公式可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,合适公式（WFF，well-formed formulas）在谓词演算中，合适公式的递归定义如下：(1)原子谓词公式是合适公式。,(4)若A是合适公式，x为A中的自由变元，则(x)A和(x)A都是合适公式。,(2)若A为合适公式，则A也是一个合适公式。,(5)只有按上述规则(1)至(4)求得的那些公式，才是合适公式。,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,合适公式的性质合适公式的真值,等价（Equivalence)如果两个合适公式，无论如何解释，其真值表都是相同的，那么我们就称此两合适公式是等价的。,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,(1)否定之否定(P)等价于P(2)PQ等价于P=Q(3)狄摩根定律(PQ)等价于PQ(PQ)等价于PQ(4)分配律P(QR)等价于(PQ)(PR)P(QR)等价于(PQ)(PR),(5)交换律PQ等价于QPPQ等价于QP(6)结合律(PQ)R等价于P(QR)(PQ)R等价于P(QR)(7)逆否律P=Q等价于Q=P,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,(8)(x)P(x)等价于(x)P(x)(x)P(x)等价于(x)P(x)(9)(x)P(x)Q(x)等价于(x)P(x)(x)Q(x)(x)P(x)Q(x)等价于(x)P(x)(x)Q(x)(10)(x)P(x)等价于(y)P(y)(x)P(x)等价于(y)P(y),2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,2.3.3 置换与合一,置换概念假元推理,W1,产生W2,（x）W1（x）W2（x）,产生W2（A）,W（x）,全称化推理,综合推理,W1W2,（x）,W（A）,W1（A）,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,置换的定义：就是在表达式中用置换项置换变量。如果用E表示表达式，s为一置换，则置换后的表达式记为Es。性质可结合律（Ls1）s2=L（s1s2）（s1s2）s3=s1（s2s3）不可交换律 s1s2 s2s1,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,例如：表达式Px,f(y),B的4个置换为,s2=A/y 则 Px,f(y),Bs2=Px,f(A),B,s1=z/x,w/y 则 Px,f(y),Bs1=Pz,f(w),B,s3=(q(z)/x,A/y)则 Px,f(y),Bs3=Pq(z),f(A),B,s4=(c/x,A/y)则 Px,f(y),Bs3=Pc,f(A),B,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,合一（Unification)合一：寻找项对变量的置换，以使两表达式一致。,可合一：如果一个置换s作用于表达式集E i的每个元素，则我们用E i s来表示置换例的集。并称表达式集E i是可合一的，如果存在一个置换s使得：E 1 s=E 2 s=E 3 s=s称为E i的合一者。,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,单一形式,所以s=A/x,B/y是Px,f(y),B,Px,f(B),B的合一者,而s=B/y是Px,f(y),B,Px,f(B),B最简单的合一者,令置换 s=A/x,B/y,则,Px,f(y),B s=PA,f(B),B,Px,f(B),Bs=PA,f(B),B,例如：对于表达式集Px,f(y),B,Px,f(B),B,2.3 谓词逻辑法,中南大学 智能系统与智能软件研究所,2.4 语义网络法（Semantic Network Representation）,语义网络的结构 定义 语义网络是知识的一种图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。,组成部分词法 决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。结构 叙述符号排列的约束条件，指定各弧线连接的节点对。过程 说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。语义 确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。,中南大学 智能系统与智能软件研究所,表示简单事实和占有关系,2.4 语义网络法,2.4.1 二元语义网络的表示,例.所有的燕子(SWALLOW)都是鸟(BIRD),SWALLOW,BIRD,ISA,我们希望表示“小燕子（XIAOYAN）是一只燕子”,XIAOYAN,ISA,WNGS,HAS-PART,我们希望表示“鸟有翅膀”,NEST1,NEST,ISA,OWNS,我们希望表示“小燕子有一个巢(nest)”,中南大学 智能系统与智能软件研究所,表示简单事实和占有关系,2.4 语义网络法,2.4.1 二元语义网络的表示,SWALLOW,BIRD,ISA,XIAOYAN,ISA,NEST1,NEST,ISA,OWNEE,我们希望 把“小燕从春天到秋天占有一个巢”的信息加到网络中去。,OWN-1,SPRING,TIME,STARTTIME,ISA,FALL,ENDTIME,ISA,OWNERSHIP,ISA,ISA,SITUATION,OWNER,中南大学 智能系统与智能软件研究所,选择语义基元问题 就是试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。,2.4 语义网络法,2.4.1 二元语义网络的表示,“我的汽车是棕黄色的”表示为：,TAN,COLOR,MY CAR,CAR,GREEN,COLOR,LIHUAS CAR,ISA,ISA,“李华的汽车是棕绿色的”表示为：,中南大学 智能系统与智能软件研究所,2.4.2 多元语义网络的表示,LIMING,MAN,ISA,ISA（LIMING，MAN）或 MAN（LIMING）,（语义网络）,（谓词逻辑）,2.4 语义网络法,李明是一个人：,说明：语义网络可以毫无困难地表示二元关系,表示二元关系,中南大学 智能系统与智能软件研究所,把多元关系转化为一组二元关系的组合，或二元关系的合取。,R(X1，X2，Xn),R12(X1，X2)R13(X1，X3)R1n(X1，Xn).Rn-1 n(Xn-1，Xn),可转换为,2.4 语义网络法,表示多元语义,2.4.2 多元语义网络的表示,中南大学 智能系统与智能软件研究所,例如，要表达北京大学(BEIJING University,简称BU)和清华大学(TSINGHUA University,简称TU)两校篮球队在北大进行的一场比赛的比分是85比89。,2.4.2 多元语义网络的表示,谓词逻辑：,语义网络：,SCORE(BU，TU，(85-89),G25,85-89,TU,VISTINGTEAM,SCORE,BU,GAME,ISA,HOMETEAM,在语义网络中进行上述转换需要引入附加节点,2.4 语义网络法,中南大学 智能系统与智能软件研究所,2.4.3 语义网络的推理过程,语义网络中的推理过程主要有两种，一种是继承，另一种是匹配。,1.继承,继承就是把对事物的描述从概念节点或类节点传递到实例节点。,这种推理过程，类似于人的思维过程。一旦知道了某种事物的身份以后，可以联想起很多关于这件事物的一般描述。例如，通常认为鲸鱼很大，鸟比较小，城堡很古老，运动员很健壮等。,2.4 语义网络法,中南大学 智能系统与智能软件研究所,有3种继承过程：值继承“如果需要”继承“默认”继承,2.匹配,（1）虚节点和虚链（图2.19),（2）部件匹配(图2.20),当解决涉及由几部分组成的事物时，继承过程将如何进行？,2.4 语义网络法,中南大学 智能系统与智能软件研究所,2.5 其他知识表示方法（Others),框架（Frame）表示 框架是一种数据结构，在这个结构中，新的资料可以从过去的经验中得到的概念来分析和解释。框架是一种结构化知识表示法，通常采用语义网络中的节点-槽-值表示结构。这组节点和槽可以描述格式固定的事物、行动和事件。,中南大学 智能系统与智能软件研究所,框架的构成框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。这些内容可以根据具体问题的具体需要来取舍，一个框架的一般结构如下：,2.5 其他知识表示方法,中南大学 智能系统与智能软件研究所,例如，一个人可以用其职业、身高和体重等项描述，因而可以用这些项目组成框架的槽。当描述一个具体的人时，再用这些项目的具体值填入到相应的槽中。下表给出了描述John的框架。,2.5 其他知识表示方法,中南大学 智能系统与智能软件研究所,剧本（Script）表示 剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列。,一个剧本一般由以下各部分组成：(1)开场条件给出在剧本中描述的事件发生的前提条件。(2)角色用来表示在剧本所描述的事件中可能出现的有关 人物的一些槽。(3)道具这是用来表示在剧本所描述的事件中可能出现的 有关物体的一些槽。(4)场景描述事件发生的真实顺序，可以由多个场景组成，每个场景又可以是其它的剧本。(5)结果给出在剧本所描述的事件发生以后通常所产生的 结果。,2.5 其他知识表示方法,中南大学 智能系统与智能软件研究所,过程（Procedure）表示,过程式表示不象陈述式表示那样具有固定的形式，如何描述知识完全取决于具体的问题。,过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。,2.5 其他知识表示方法,中南大学 智能系统与智能软件研究所,2.6 小结（Summary）,本章所讨论的知识表示问题是人工智能研究的核心问题之一。,对于同一问题可以有许多不同的表示方法。不过对于特定问题有的表示方法比较有效，有的表示方法可能不太适用，或者不是好的表示方法。,在表示和求解比较复杂的问题时，采用单一的知识表示方法是远远不够的。往往必须采用多种方法进行混合的知识表示。,中南大学 智能系统与智能软件研究所,方法,初始问题,算符,目标,结果,状态 空间法,问题归约法,谓词逻辑法,语义网络法,状态,结点,合适公式,结点,算符,弧,子句集,置换合一,消解反演,链,目标状态,结点,根结点,目标网络,解答路径（path）,解答树（tree）,nil,语义网络,四种知识表示方法间的关系,