智能控制第二章知识表示方法ppt课件

《智能控制第二章知识表示方法ppt课件》由会员分享，可在线阅读，更多相关《智能控制第二章知识表示方法ppt课件（66页珍藏版）》请在装配图网上搜索。

1、第二章 知识表示方法2.1 形状空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结数据与信息 数据用一组符号及其组合表示的信息 数据和信息是两个亲密相关的概念：数据是信息的载体和表示；信息是数据在特定场所下的详细含义。数据和信息又是两个不同的概念：知识 人们经过体验、学习或联想而知晓的对客观世界规律性的认识。知识及其表示的有关概念：3.知识的特性v相对正确性v不确定性v可表示性和可利用性4.知识的分类v从作用范围来划分：常识性、领域性v从知识的作用及表示来划分：现实性、过程性、控制性v从知识确实定性来划分：确定性、不确定性v从知识的构造及表现方式来划分：逻

2、辑性、笼统性v知识表示对知识的一种描画，或者说是一组商定，一种计算机可以接受的用于描画知识的数据构造。v对知识进展表示的过程就是把知识编码成某种数据构造的过程。v在选择知识的表示方法时，可从以下几个方面进展思索：v 1充分表示领域知识；v 2有利于对知识的利用；v 3便于对知识的组织、维护与管理；v 4便于了解和实现。5.知识的表示2.1 形状空间法State Space Representationv 问题求解技术主要包括两个方面：问题求解技术主要包括两个方面：v 问题的表示问题的表示v 求解的方法求解的方法v 形状空间法形状空间法v 形状形状state:表示问题解法中每一步问题情况的表示问

3、题解法中每一步问题情况的数据构造数据构造v 算符算符operator):把问题从一种形状变换为另一种把问题从一种形状变换为另一种形状的手段形状的手段v 形状空间方法形状空间方法:基于解答空间的问题表示和求解方基于解答空间的问题表示和求解方法，它是以形状和算符为根底来表示和求解问题的法，它是以形状和算符为根底来表示和求解问题的2.1.1 问题形状描画v定义v形状：描画某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合:2.1 形状空间法01,TnQq qqv算符：使问题从一种形状变化为另一种形状的手段称为操作符或算符。v问题的形状空间：是一个表示该问题全部能够形状及其关系的图，它

4、包含三种阐明的集合，即三元形状S，F，G。2.形状空间表示概念详释v形状空间法：从某个初始形状开场，每次加一个操作符，递增地建立起操作符的实验序列，直至到达目的形状止。v例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1 形状空间法例:三数码难题3 puzzle problem123123123312312312初始棋局目的棋局2.1 形状空间法v有向图v 一对节点用弧线衔接起来，从一个节点指向另一个节点,这种图叫做有向图。v途径 v 某个节点序列ni1，ni2，nik当 j=2，3，k时，假设对于每一个ni，j-1都有一个后继节点ni，j存在，

5、那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的途径。v代价 v 用Cni，nj来表示从节点ni指向节点nj的那段弧线的代价(cost)。两点间途径的代价等于衔接该途径上各节点的一切弧线代价之和。2.1.2 形状图示法AB2.1 形状空间法图的隐式阐明 节点的无限集合si作为起始节点是知的。后继节点算符也是知的，它能作用于任一节点以产生该节点的全部后继节点和各衔接弧线的代价。图的显式阐明 对于显式阐明，各节点及其具有代价的弧线由一张阐明确给出。此表能够列出该图中的每一节点、它的后继节点以及衔接弧线的代价。2.1.3 形状空间表示举例v产生式系统production systemv一

6、个总数据库Global Database)：它含有与详细义务有关的信息。随着运用情况的不同，这些数据库能够简单，或许复杂。v一套规那么：它对数据库进展操作运算。每条规那么由左右两部分组成，左部鉴别规那么的适用性或先决条件，右部描画规那么运用时所完成的动作。v一个控制战略：它确定应该采用哪一条适用规那么，而且当数据库的终止条件满足时，就停顿计算。2.1 形状空间法 形状空间表示举例例：猴子和香蕉问题2.1 形状空间法解题过程：v 用一个四元表列W，x，Y，z来表示这个问题形状.v W 猴子的程度位置vx 当猴子在箱子顶上时取 x=1；否那么取 x=0v Y 箱子的程度位置vz 当猴子摘到香蕉时取

7、 z=1；否那么取 z=0v这个问题的操作算符如下：v gotoU表示猴子走到程度位置U，或者用产生式规那么表示为：vW，0，Y，z gotoU U，0，Y，z2.1 形状空间法vpushboxV猴子把箱子推到程度位置V，即有vW，0，W，z pushboxV V，0，V，zv vclimbbox猴子爬上箱顶，即有vW，0，W，z climbbox W，1，W，zv 2.1 形状空间法该当留意的是，要运用算符pushboxV，就要求产生式规那么的左边，猴子与箱子必需在同一位置上，并且，猴子不是箱子顶上。这种强加于操作的适用性条件，叫做产生式规那么的先决条件。运用算符climbbox的先决条件是

8、什么？v grasp猴子摘到香蕉，即有vc，1，c，0 grasp c，1，c，1v 令初始形状为(a，0，b，0)。这时，goto(U)是独一适用的操作，并导致下一形状(U，0，b,0)。如今有3个适用的操作，即goto(U)，pushbox(V)和climbbox(假设U=b)。把一切适用的操作继续运用于每个形状，我们就可以得到形状空间图，如以下图所示。从图不难看出，把该初始形状变换为目的形状的操作序列为：goto(b),pushbox(c),climbbox,grasp2.1 形状空间法(b，1，b，0)U，0，b，0V，0，V，0c，1，c，0U，0，V，0c，1，c，1a，0，b，0

9、目的形状目的形状gotoUgotoUU=b，climbboxgotoUU=bpushboxV猴子与香蕉问题的形状空间图猴子与香蕉问题的形状空间图gotoUU=V初始形状初始形状graspV=c,climbbox2.1 形状空间法猴子和香蕉问题自动演示：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 形状空间法2.2 问题归约法Problem Reduction Representation问题归约法思想 先把问题分解为子问题及子-子问题，然后处理较小的问题。对该问题的某个详细子集的解答就意味着对原始问题的一个解答 子问题子问题 1 子问题子问题 n原始问题原始问题子问题

10、集子问题集本本原原问问题题v 问题归约表示的组成部分：v一个初始问题描画；v一套把初始问题变换为子问题的操作符；v一套本原问题描画。v问题归约的本质：v 从目的(要处理的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题归约法2.2.1 问题归约描画 Problem Reduction Descriptionv梵塔难题(Tower of Hanoi Puzzle)1 2 364 disks Moving times:64 disks 264-1 2641019.27 If one person move 1 disk in one s

11、econd,then to finish this problem needs more than 3000 billion years.(30000多亿年2.2 问题归约法123CBA初始配置初始配置123CBA目的配置目的配置3 3圆盘梵塔难题：圆盘梵塔难题：2.2 问题归约法解题过程：v把原始梵塔难题归约简化为以下3个子难题：v挪动圆盘A和B至柱子2的双圆盘难题；v挪动圆盘C至柱子3的单圆盘难题；v挪动圆盘A和B至柱子3的双圆盘难题。1 2 3ABC1 2 3ABC3223331221 2 3ABC1 2 3ABC3221 2 3ABC1 2 3ABC111122解题过程3圆盘难题123

12、1231231231231231231232.2 问题归约法梵塔难题归约图与或图113 123 111 113 123 122 111 333 122 322 111 122 322 333 321 331 322 321 331 333 Fig 2.8 AND/OR graph for the 3-disk THP(b)(a)(c)2.2 问题归约法多圆盘梵塔难题演示2.2 问题归约法2.2.2 与或图表示1.与图、或图、与或图 普通，用一个似图构造来表示把问题归约为后继问题的交换集合，这一似图构造叫做问题归约图，或叫与或图。如下所示ABCD与图ABC或图2.2 问题归约法BCDEFHAHM

13、BCDEFGAN与或图与或图2.2 问题归约法2.一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点2.2 问题归约法一些关于与或图的术语v父节点、子后继节点、弧线v起始节点：对应于原始问题描画的节点v终叶节点：对应于本原问题的节点v或节点：只需处理某个问题就可处理其父辈问题的节点集合，如M，N，H。v与节点：只需处理一切子问题，才干处理其父辈问题的节点集合，如B，C和D，E，F。各个节点之间用一段小圆弧衔接标志。v与或图：由与节点及或节点组成的构造图。2.2 问题归约法3.定义可解节点的普通定义 终叶节点是可解节点(由于它们与本原问题相关联)。假设某个非终叶节点含有

14、或后继节点，那么只需有一个后继节点是可解的时，此非终叶节点就是可解的。假设某个非终叶节点含有与后继节点，那么只需其全部后继节点为可解时，此非终叶节点才是可解的。2.2 问题归约法v没有后裔的非终叶节点为不可解节点。v假设某个非终叶节点含有或后继节点，那么只需当其全部后裔为不可解时，此非终叶节点才是不可解的。v假设某个非终叶节点含有与后继节点，那么只需当其后裔有一个为不可解时，此非终叶节点就是不可解的。不可解节点的普通定义2.2 问题归约法如下图与或图例子与或图例子tttttttttab有解节点有解节点无解节点无解节点终叶节点终叶节点2.2 问题归约法与或图构成规那么v1与或图中的每个节点代表一

15、个要处理的单一问题或问题集合。起始节点对应于原始问题。v2对应于本原问题的节点，叫做终叶节点。v3对于把算符运用于问题A的每种能够情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合，这些子问题节点叫做或节点。v4普通对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点,这些子问题节点叫做与节点。2.2 问题归约法2.3 谓词逻辑法v逻辑语句：一种方式言语，它可以把逻辑论证符号化，并用于证明定理，求解问题。v方式言语：严厉地按照相关领域的特定规那么，以数学符号符号串方式描画该领域有关客体的表达式。2.3.1 谓词演算 1.语法

16、和语义根本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号MARRIED(father(LI),mother(LI)谓词符号函数符号常量符号 原子公式：由假设干谓词符号和项组成的谓词演算。原子公式是谓词演算的根本积木块。如如:INROOM(ROBOT,r1)机器人在机器人在1号房间内号房间内 2.3 谓词逻辑法2.连词和量词(Connective&Quantifiers)连词(,=,)与及合取conjunction)：用连词把几个公式衔接起来而构成的公式。合取项是合取式的每个组成部分。例：LIKE(I，MUSIC)LIKE(I，PAINTING)我喜欢音乐和绘画。LIVES(L1，HO

17、USE-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：表示否认，、均可表示,用来否认一个公式的

18、真值。例：INROOM(ROBOT,r2)2.3 谓词逻辑法以上讲的是命题演算(谓词演算的一个子集)，但它缺乏用有效的方法来表达多个命题的才干，如：“一切机器人都是灰色的可以表示为：一切机器人都是灰色的可以表示为：(x)ROBOT(x)=COLOR(x,GRAY)x)ROBOT(x)=COLOR(x,GRAY)但命题演算就无法表示，所以需求使公但命题演算就无法表示，所以需求使公式中的命题带有变量。式中的命题带有变量。2.3 谓词逻辑法v量词v 全称量词Universal Quantifier：假设一个原子公式Px，对于一切能够变量 x都具有T值，那么用 xPx表示约束变元约束变元全称量词作用域

19、全称量词作用域存在量词Existential Quantifier 假设一个原子公式假设一个原子公式Px，至少有一个变元，至少有一个变元x，可使，可使P x为为T值，那么用值，那么用 xPx表示。表示。全称量词约束变元约束变元存在量词作用域存在量词作用域存在量词 例：(x)INROOM(x,r1)1号房间内有个物体2.3 谓词逻辑法2.3.2 谓词公式原子公式的的定义用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。分子谓词公式可以用连词把原子谓词公式组成复合谓词公式，并把它叫

20、做分子谓词公式。2.3 谓词逻辑法v适宜公式适宜公式WFF，well-formed formulasv在谓词演算中，适宜公式的递归定义如下：在谓词演算中，适宜公式的递归定义如下：v(1)原子谓词公式是适宜公式。原子谓词公式是适宜公式。(4)假设A是适宜公式，x为A中的自在变元，那么(x)A和(x)A都是适宜公式。(2)假设A为适宜公式，那么A也是一个适宜公式。(3)假设A和B都是适宜公式，那么(AB)，(AB)，(A=B)和(A B)也都是适宜公式。(5)只需按上述规那么(1)至(4)求得的那些公式，才是适宜公式。2.3 谓词逻辑法v适宜公式的性质v适宜公式的真值T F T F F F表表2-

21、1 真值表真值表P Q PQ P Q PQ PT T T T T FF T T F T TF F F F T Tv等价Equivalence)v 假设两个适宜公式，无论如何解释，其真值表都是一样的，那么我们就称此两适宜公式是等价的。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)

22、(PQ)R等价于等价于P(QR)(7)逆否律逆否律P=Q等价于等价于Q=P2.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 置换与合一v置换v概念v假元推理W1产生产生W2 xW1x W2x产生产生W2AWx恣意变量恣意变量约束变元约束变元v全称化推理v综合推理W1W2x WAW1A2.3 谓词逻辑法v置换的定义：就是在表达式中用置

23、换项置换变量。假设用E表示表达式，s为一置换，那么置换后的表达式记为Es。v 性质v可结合律Ls1s2=Ls1s2v s1s2s3=s1s2s3v不可交换律 s1s2 s2s12.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 谓词逻辑法v合一Unification)v合一：寻觅项对变

24、量的置换，以使两表达式一致。v可合一：假设一个置换s作用于表达式集E i的每个元素，那么我们用E i s来表示置换例的集。并称表达式集E i是可合一的，假设存在一个置换s使得：v E 1 s=E 2 s=E 3 s=vs称为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

25、,f(B),B2.3 谓词逻辑法2.4 语义网络法Semantic Network Representationv语义网络的构造v 定义v 语义网络是知识的一种图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。v 组成部分v词法 决议表示词汇表中允许有哪些符号，它涉及各个节点和弧线。v构造 表达符号陈列的约束条件，指定各弧线衔接的节点对。v过程 阐明访问过程，这些过程能用来建立和修正描画，以及回答相关问题。v语义 确定与描画相关的(联想)意义的方法即确定有关节点的陈列及其占有物和对应弧线。v表示简单现实和占有关系2.4 语义网络法2.4.1 二元语义

26、网络的表示例例.一切的燕子一切的燕子(SWALLOW)都是鸟都是鸟(BIRD)SWALLOWBIRDISA我们希望表示我们希望表示“小燕子小燕子XIAOYAN是一只燕子是一只燕子XIAOYANISAWNGSHAS-PART我们希望表示我们希望表示“鸟有翅膀鸟有翅膀NEST1NESTISAOWNS我们希望表示我们希望表示“小燕子有一个巢小燕子有一个巢(nest)v表示简单现实和占有关系2.4 语义网络法2.4.1 二元语义网络的表示SWALLOWBIRDISAXIAOYANISANEST1NESTISAOWNEE我们希望我们希望 把把“小燕从春天到秋天占有一个巢的信息加小燕从春天到秋天占有一个巢

27、的信息加到网络中去。到网络中去。OWN-1SPRINGTIMESTARTTIMEISAFALLENDTIMEISAOWNERSHIPISAISASITUATIONOWNERv选择语义基元问题v 就是试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。2.4 语义网络法2.4.1 二元语义网络的表示“我的汽车是棕黄色的表示为：我的汽车是棕黄色的表示为：TANCOLORMY CARCARGREENCOLORLIHUAS CARISAISA“李华的汽车是棕绿色的表示李华的汽车是棕绿色的表示为：为：2.4.2 多元语义网络的表示LIMINGMANISAISALIMING，MAN

28、或或 MANLIMING语义网络语义网络谓词逻辑谓词逻辑2.4 语义网络法李明是一个人：李明是一个人：阐明：语义网络可以毫无困难地表示二元关系阐明：语义网络可以毫无困难地表示二元关系表示二元关系表示二元关系 把多元关系转化为一组二元关系的组合，或二元关系的合取。R(X1R(X1，X2X2，Xn)Xn)R12(X1R12(X1，X2)R13(X1X2)R13(X1，X3)R1n(X1X3)R1n(X1，Xn)Xn).Rn-1 n(Xn-1 Rn-1 n(Xn-1，Xn)Xn)可转换为可转换为2.4 语义网络法表示多元语义表示多元语义2.4.2 多元语义网络的表示例如，要表达北京大学(Univer

29、sity,简称BU)和清华大学(TSINGHUA University,简称TU)两校篮球队在北大进展的一场竞赛的比分是85比89。2.4.2 多元语义网络的表示谓词逻辑：谓词逻辑：语义网络：语义网络：SCORE(BU，TU，(85-89)G2585-89TUVISTINGTEAMSCOREBUGAMEISAHOMETEAM在语义网络中进展上述转换需求引入附加节点在语义网络中进展上述转换需求引入附加节点2.4 语义网络法2.4.3 语义网络的推理过程 语义网络中的推理过程主要有两种，一种是承继，另一种是匹配。1.1.承继承继 承继就是把对事物的描画从概念节点或类节点传送到实例节点。这种推理过程

30、，类似于人的思想过程。一旦知道了某种事物的身份以后，可以联想起很多关于这件事物的普通描画。例如，通常以为鲸鱼很大，鸟比较小，城堡很古老，运发动很强壮等。2.4 语义网络法有3种承继过程：值承继 “假设需求承继 “默许承继2.2.匹配匹配 1虚节点和虚链 图2.19)2部件匹配(图2.20)当处理涉及由几部分组成的事物时，承继过程将如何进展？2.4 语义网络法2.5 其他知识表示方法Others)框架Frame表示 框架是一种数据构造，在这个构造中，新的资料可以从过去的阅历中得到的概念来分析和解释。框架是一种构造化知识表示法，通常采用语义网络中的节点-槽-值表示构造。这组节点和槽可以描画格式固定

31、的事物、行动和事件。框架的构成框架的构成框架通常由描画事物的各个方面的槽组成，框架通常由描画事物的各个方面的槽组成，每个槽可以拥有假设干个侧面，而每个侧面又可每个槽可以拥有假设干个侧面，而每个侧面又可以拥有假设干个值。这些内容可以根据详细问题以拥有假设干个值。这些内容可以根据详细问题的详细需求来取舍，一个框架的普通构造如下：的详细需求来取舍，一个框架的普通构造如下：111 121 211 n11 nm12.5 其他知识表示方法例如，一个人可以用其职业、身高和体重等项描画，因此可以用这些工程组成框架的槽。当描画一个详细的人时，再用这些工程的详细值填入到相应的槽中。下表给出了描画John的框架。2

32、.5 其他知识表示方法剧本Script表示 剧本是框架的一种特殊方式，它用一组槽来描画某些事件的发生序列。一个剧本普通由以下各部分组成：一个剧本普通由以下各部分组成：(1)开场条件给出在剧本中描画的事件发生的前提条件。开场条件给出在剧本中描画的事件发生的前提条件。(2)角色用来表示在剧本所描画的事件中能够出现的有关角色用来表示在剧本所描画的事件中能够出现的有关 人物的一些槽。人物的一些槽。(3)道具这是用来表示在剧本所描画的事件中能够出现的道具这是用来表示在剧本所描画的事件中能够出现的 有关物体的一些槽。有关物体的一些槽。(4)场景描画事件发生的真实顺序，可以由多个场景组成，场景描画事件发生的

33、真实顺序，可以由多个场景组成，每个场景又可以是其它的剧本。每个场景又可以是其它的剧本。(5)结果给出在剧本所描画的事件发生以后通常所产生的结果给出在剧本所描画的事件发生以后通常所产生的 结果。结果。2.5 其他知识表示方法过程Procedure表示 过程式表示不象陈说式表示那样具有固定的方式，如何描画知识完全取决于详细的问题。过程式表示就是将有关某一问题领域的知识，连同如何运用这些知识的方法，均隐式地表达为一个求解问题的过程。2.5 其他知识表示方法2.6 小结Summaryv本章所讨论的知识表示问题是人工智能研讨的中心问题之一。v对于同一问题可以有许多不同的表示方法。不过对于特定问题有的表示方法比较有效，有的表示方法能够不太适用，或者不是好的表示方法。v在表示和求解比较复杂的问题时，采用单一的知识表示方法是远远不够的。往往必需采用多种方法进展混合的知识表示。方法 初始问题算符目的结果 形状 空间法 问题归约法 谓词逻辑法 语义网络法形状形状结点结点适宜公式适宜公式结点结点算符算符弧弧 子句集子句集置换合一置换合一消解反演消解反演链链目的形状目的形状结点结点根结点根结点目的网络目的网络解答途径解答途径path 解答树解答树treenil语义网络语义网络 四种知识表示方法间的关系四种知识表示方法间的关系