人工智能 状态空间法 第二章主讲课件.ppt

《人工智能 状态空间法 第二章主讲课件.ppt》由会员分享，可在线阅读，更多相关《人工智能 状态空间法 第二章主讲课件.ppt（76页珍藏版）》请在三一办公上搜索。

1、人工智能,Artificial Intelligence,主讲人：,XXX,目 录,状态空间法,语义网络表示,谓词逻辑表示,问题归约法,第2 章 知识表示方法,（一）,目 录,框架表示,小结,过程表示,本体技术,第2 章 知识表示方法,（二）,2.1状态空间法（State Space Representation）,问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）算符（operator）状态空间方法,2.1.1 问题状态描述,基本概念状态(state)它是为描述某类不同事物间的差别而引入的一组最少变q0,q1,qn的有序集合,其矢量形式如下: Q=q0,q1,qnT

2、(2.1) 式中每个元素qi(i=0,1,n)为集合的分量,称为状态变量。给定每个分量的一组值就得到一个具体的状态,如 Qk=qk ,q1k,qnkT(2.2)操作符(operator) 称使问题从一种状态变化到另一种状态的手段为操作符或算符。问题的状态空间： 是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。,2.1 状态空间法,2. 状态空间表示概念详释,例如下棋、迷宫及各种游戏。,MiddleState,GoalState,2.1 状态空间法,例:三数码难题（3 puzzle problem）,初始棋局,目标棋局,2.1 状态空间法,1.图的基本概

3、念图是一个包含节点(不一定是有限的节点)和节点间弧线的集合。若图中每条弧线均标有方向,则称这种图为有向图(directed graph)。2.代价(cost)是给各弧线指定数值以表示加在相应操作符上的代价。3.图的显式说明是指各节点及其具有代价的弧线由一张表明确给出。4.图的隐式说明:是指各节点及其具有代价的弧线不能由一张表明确给出。,2.1 状态空间法,2.1.2 状态图示法,有向图代价图的显示说明图的隐示说明,2.1.2 状态图示法,A,B,2.1 状态空间法,2.1.3状态空间表示举例,例：猴子和香蕉问题,2.1 状态空间法,猴子和香蕉问题自动演示：,2.1 状态空间法,解题过程,用一个

4、四元表列（W，x，Y，z）来表示这个问题状态.,这个问题的操作（算符）如下：2 goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z） goto（U） （U，0，Y，z）,2.1 状态空间法,2.1.3状态空间表示举例,ushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbox（V） （V，0，V，z）,climbbox猴子爬上箱顶，即有（W，0，W，z） climbbox （W，1，W，z）,2.1 状态空间法,2.1.3状态空间表示举例,grasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1）,该初始状态变换为目标状态的操

5、作序列为goto(b),pushbox(c),climbbox,grasp,2.1 状态空间法,2.1.3状态空间表示举例,目标状态,猴子和香蕉问题的状态空间图,2.1 状态空间法,2.1.3状态空间表示举例,2.2问题规约法表示,2.2.1问题归约描述1.问题归约法的概念问题归约是将初始问题变为一个本原问题集合。2.问题归约法的组成部分(1)一个初始问题描述;(2)一套把问题变换为子问题的操作符;(3)一套本原问题描述。,2.2问题规约表示,2.2 问题规约法,2.2 问题规约法,问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平

6、凡的本原问题集合。,2.2问题规约表示,梵塔难题,解题过程（3个圆盘问题）,2.2 问题规约法,梵塔问题归约图：子问题2可作为本原问题考虑，因为它的解只包含一步移动。 应用一系列相似的推理，子问题1和子问题3也可被归约为本原问题，如下图所示。 这种图式结构，叫做与或图(AND/OR graph)。它能有效地说明如何由问题归约法求得问题的解答。,图 梵塔问题归约图,2.2.2与或图表示,1.与图、或图、与或图,2.2 问题规约法,2.2 问题规约法,2.一些关于与或图的术语,2.2 问题规约法,终叶节点：对应于原问题的本原节点。或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H

7、）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧连接标记。,一些关于与或图的术语： 父节点、子（后继）节点、弧线、起始节点。,3.定义,不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。与或图构成规则,2.2 问题规约法,2.2 问题规约法,3.定义图解,3.与或图构图规则 (1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中起始节点对应原始问题。 (2) 对应于本

8、原问题的节点,叫做终叶节点。 (3)有向弧线自A指向后继节点,表示所求得的子问题集合。 (4) 一般对于代表两个或两个以上子问题集合的每个节点,有向弧线从此节点指向集合中的各个节点。 (5) 在特殊情况下,当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的某个集合时,由上述规则(3)和规则(4)所产生的图可以得到简化。,2.3谓词逻辑表示,2.3.1谓词演算1.语法和语义谓词逻辑的基本组成部分是谓词、变量、函数和常量,并用圆括弧、方括弧、花括弧和逗号隔开。 例如，要表示“机器人(ROBOT)在号房间(r1)内”，如下图所示，可以应用原子公式:2.连词和量词连词有(与)、(或),

9、全称量词(),存在量词()。,3.几个有关定义 1.用连词把几个公式连接起来而构成的公式叫做合取,而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。 例：LIKE(I，MUSIC)LIKE(I，PAINTING)(我喜爱音乐和绘画。),2.用连词把几个公式连接起来所构成的公式叫做析取,而此析取式的每一组成部分叫做析取项。一些合适公式所构成的任一析取也是一个合适公式。 例：PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL)(李力打篮球或踢足球。),2.3 谓词逻辑法,3.用连词=连接两个公式所构成的公式叫做蕴涵。称蕴涵的左式为前项

10、,右式为后项。如果前项和后项都是合适公式,那么蕴涵也是合适公式 “=”表示“如果-那么”的语句。 IF = THEN 前项 后项 (左式) (右式)例：RUNS(LIUHUA，FASTEST)TWINS(LIUHUA，CHAMPION) (如果刘华跑得最快，那么他取得冠军),2.3 谓词逻辑法,前面具有符号的公式叫做否定。一个合适公式的否定也是合适公式。 例：INROOM(ROBOT，r2)(机器人不在2号房间内。)如果一个合适公式中某个变量是经过量化的,则称这个变量为约束变量,否则为自由变量。称所有变量都是受约束的合适公式为句子。,2.3 谓词逻辑法,2.3 谓词逻辑法,2.3.2 谓词公式

11、原子公式的的定义：用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。分子谓词公式可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,合适公式（WFF，well-formed formulas）合适公式的递归定义合适公式的性质合适公式的真值等价（Equivalence),2.3 谓词逻辑法,合适公式(WFF ,well-formed formulas)的递归定义：(1) 原子谓词公式是合适公式。(2) 若A为合适公式，则A也是一个合适公式。(3) 若A和B都是合适

12、公式， 则(AB),(AB),(ATB), (AB)也都是合适公式。(4) 若A是合适公式，x为A中的自由变元， 则( x) A ,(Ex) A都是合适公式。(5) 只有按上述规则(1)至(4)求得的那些公式，才是合适公式。,2.3 谓词逻辑法,例题：对于所有的x，如果x是整数，则x或为正的或者为负的。“( x) (I(x)=(P(x) N(x) ) I(x)表示x是整数，P(x)表示x是正数，N(x)表示x是负数。,2.3 谓词逻辑法,2.合适公式的性质,(1) 否定之否定,(2) PQ,(3) 狄摩根定理,(4) 分配律,(5) 交换律,(6) 结合律,(7) 逆否律,在一个量化的表达式中

13、的约束变量是一类虚元,它可以用任何一个不在表达式中出现过的其它变量符号来代替。举例如下：,2.3 谓词逻辑法,2.3.3 置换与合一,置换概念假元推理全称化推理综合推理定义就是在该表达式中用置换项置换变量性质可结合的不可交换的,2.3 谓词逻辑法,置换：用项(A)替换函数表达式中的变量(x)，记为ES，即表示一个表达式E (Expression)，用一个置换S (Substitution)而得到的表达式的置换。 例1表达式P x, f(y) ,B的4个置换为 ：,s1=z/x, w/y,s2=A/y,s3=q(z)/x , A/y,s4=c/x , A/y,我们用Es来表示一个表达式E用置换s

14、所得到的表达式的置换。于是，我们可得到Px,f(y),B的4个置换的例，如下：,Px,f(y),Bs1=Pz, f(w), B,Px,f(y),Bs2=Px, f(A), B,Px,f(y),Bs3=Pq(z), f(A) ,B,Px,f(y),Bs4=Pc,f(A),B2),2.3 谓词逻辑法,合一（Unification)合一：寻找项对变量的置换，以使两表达式一致。可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。,2.3 谓词逻辑法,2.4 语义网络表示 （Semantic Network Representation）,

15、语义网络的结构定义组成部分词法结构过程语义,词法部分决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。 结构部分叙述符号排列的约束条件，指定各弧线连接的节点对。 过程部分说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。 语义部分确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。,2.4 语义网络法,用两个节点和一条弧线可以表示一个简单的事实,对于表示占有关系的语义网络,是通过允许节点既可以表示一个物体或一组物体,也可以表示情况和动作。每一情况节点可以有一组向外的弧(事例弧),称为事例框,用以说明与该事例有关的各种变量。在选择节点时,首先要弄清节点是用

16、于表示基本的物体或概念的,或是用于多种目的的。否则,如果语义网络只被用来表示一个特定的物体或概念,那么当有更多的实例时就需要更多的语义网络。 选择语义基元就是试图用一组基元来表示知识。这些基元描述基本知识,并以图解表示的形式相互联系。,2.4 语义网络法,2.4. 1 二元语义网络的表示,2.表示占有关系和其它情况例： 小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。,2.4 语义网络法,1.表示简单的事实 例1. 所有的燕子都是鸟,二元语义网络的表示,3.选择语义基元试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。,例3.我椅子的颜色是咖啡色的；椅

17、子包套是皮革；椅子是一种家具；椅子是座位的一部分；椅子的所有者是X；X是个人，如下图所示：,2.4 语义网络法,图 椅子的语义网络,2.4 语义网络法,2.4.2 多元语义网络的表示,谓词逻辑与语义网络等效,2.4 语义网络法,2.4.2多元语义网络的表示 语义网络是一种网络结构。节点之间以链相连。从本质上讲,接点之间的连接是二元关系。语义网络从本质上来说,只能表示二元关系,如果所要表示的事实是多元关系,则把这个多元关系转化成一组二元关系的组合,或二元关系的合取。,2.4 语义网络法,例如，要表达北京大学(BEIJING University,简称BU)和清华大学(TSINGHUA Unive

18、rsity,简称TU)两校篮球队在北大进行的一场比赛的比分是85比89。,若用谓词逻辑可表示为SCORE(BU，TU，(85-89)。这个表示式中包含3项，而语义网络从本质上来说，只能表示二元关系。解决这个矛盾的一种方法是把这个多元关系转化成一组二元关系的组合，或二元关系的合取。 对于上述球赛，我们可以建立一个G25节点来表示这场特定的球赛。然后，把有关球赛的信息和这场球赛联系起来。这样的过程如图所示。,图 多元关系的语义网络表示,2.4 语义网络法,具体来说，多元关系R(X1，X2，Xn)总可以转换成R1(X11X12)R2(X21，X22)Rn(Xn1,Xn2) 例如，三根线a，b，c组成

19、一个三角形。这可表示成TRIANGLE(a，b，c)。这个三元关系可转换成一组二元关系的合取，即CAT (a, b) CAT (b, c) CAT (c, a),多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。,2.4 语义网络法,2.4.3 语义网络推理过程,在语义网络知识表达方法中，没有形式语义，也就是说，和谓词逻辑不同，对所给定的表达结构表示什么语义没有统一的表示法。赋予网络结构的含义完全决定于管理这个网络的过程的特性。已经设计了很多种以网络为基础的系统，它们各自采用完全不同的推理过程。为了便于以下的叙述，我们对所用符号作进一步的规定。我们区分在链头部和在链尾

20、部的节点，把在链尾部的节点称为值节点。另外，我们还规定节点的槽相当于链，不过取不同的名字而已。,2.4 语义网络法,图 2.15 语义网络的槽与数值,2.4 语义网络法,在图 2-15中砖块12（BRICK12）有3个链，构成两个槽。其中一个槽只有一个值，另外一个槽有两个值。我们说颜色槽（COLOR）填入红色（RED），ISA 槽填入了砖块（BRICK）和玩具（TOY）。,语义网络中的推理过程主要有两种：一种是继承，另一种是匹配。,2.4 语义网络法,这种推理过程，类似于人的思维过程。一旦知道了某种事物的身份以后，可以联想起很多关于这件事物的一般描述。例如，我们通常认为鲸鱼很大，鸟比较小，城堡

21、很古老，运动员很健壮。这就像我们用每种事物的典型情况来描述各种事物鲸鱼、鸟、城堡和运动员那样。一共有3种继承过程：值继承、“如果需要”继承和“默认”继承。 （1）值继承：除了ISA链以外，另外还有一种AKO（是某种）链也可被用于语义网络中的描述或特性的继承。AKO是A-KIND-OF的缩写。总之，ISA和AKO链直接地 表示类的成员关系 以及子类和类之间的关系，提供了一种把知识从某一层传递到另一层的途径。,1.继承,2.4 语义网络法,在语义网络系统中,问题求解推理的匹配实现过程为：（1） 根据待求解问题的要求构造一个网络片断，其中有些节点或弧的标识是空的,反映求解的问题。（2） 此网络片断到

22、知识库中去寻找可匹配的网络，以找出所需要的信息。当然，这种匹配一般不完全的，具有不确定性，因此需要解决不确定匹配的问题。（3） 当问题的 语义网络片断与知识库中的 某些语义网络片断匹配进，则与询问处匹配的事实就是问题的解。,2.匹配,2.4 语义网络法,目 录,框架表示,小结,过程表示,本体技术,第2 章 知识表示方法,（二）,2.5 框架表示,框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。这些内容可以根据具体问题的具体需要来取舍，一个框架的一般结构如下： ,1.一个框架系统的例子,图中所示的就是表示立方体的一个视图的框架。图中，最高层的框架用i

23、sa槽说明它是一个立方体，并由region槽指示出它所拥有的3个可见面A、B、E。而A、B、E又分别用3个框架来具体描述。用must be槽指示出它们必须是一个平行四边形。,一个立体视图的框架表示,2.5 框架表示,为了能从各个不同的角度来描述物体，可以对不同角度的视图分别建立框架，然后再把它们联系起来组成一个框架系统 。图中所示的就是从3个不同的角度来研究一个立方体的例子 。为了简便起见，图中略去了一些细节，在表示立方体表面的槽中，用实线与可见面连接，用虚线与不可见面连接。,立方体框架系统,2.5 框架表示,二、框架的推理,如前所述，框架是一种复杂结构的语义网络。因此语义网络推理中的匹配和特

24、性继承在框架系统中也可以实行。除此以外，由于框架用于描述具有固定格式的事物、动作和事件，因此可以在新的情况下，推论出未被观察到的事实。框架用以下几种途径来帮助实现这一点：（1）框架包含它所描述的情况或物体的 多方面的信息。这些信息可以被引用，就像已经直接观察到这些信息一样。例如，当一个程序访问一个ROOM框架时，不论是否有证据说明屋子里有门，都可以推论出，在屋子里至少有一个门。之所以能这样做，是因为 ROOM 框架中包含对屋子的描述，其中包括在屋子里必须有门的事实。,2.5 框架表示,（2）框架包含物体必须 具有的属性。在填充框架的各个槽时，要用到这些属性。建立对某一情况的描述要求先建立对此情

25、况的各个方面的描述。与描述这个情况的框架中的各个槽有关的信息可用来指导如何建立这些方面的描述。（3）框架 描述它们所代表的概念的典型事例。如果某一情况在很多方面和一个框架相匹配，只有少部分相互之间存在不同之处。这些不同之处很可能对应于当前情况的 重要方面，也许应该 对这些不同之处作出解答。因此，如果一个椅子被认为应有4条腿，而某一椅子只有3条腿，那么或许这把椅子需要修理。,二、框架的推理,2.5 框架表示,2.5 框架表示,图 相似网络,2.6 本体技术,1.本体组成 知识工程领悟中，本体是一个工程上的人工产物，是用于描述某种确定现实情况的特定术语集，加上一组关于术语内涵意义的显式假定集合构成

26、,一句话讲：一个完整的本体应由概念、关系、函数、公理、和实例五类基本元素构成。,2.6 本体技术,2.本体分类,（1）知识表示本体（2）通用常识本体（3）领域本体（4）语言学本体（5）任务本体,2.6 本体技术,3.本体建模：,（1）建立本体模型的过程可分为：非形式化阶段 和形式化阶段。,2.6 本体技术,（2）本体建模过程（甘唐五阶段法） 1.数据收集和分析； 2.建立一个字典； 3.对字典进行求精，建立内容更丰富的表； 4.用RDFS语言描述上述各表； 5.定义关系的代数属性，定义知识的推理规则。,2.7 过程式表示,过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐

27、式地表达为一个求解问题的过程。,过程式不像陈述式那样具有固定的形式，如何描述知识完全取决于具体的问题。下面以八数码问题为例，给出一种求解该问题的过程式描述。,我们用一个的方格阵来表示该问题的一个状态，为叙述上的方便，我们用ai来标记这个方格，如图2-7-1（a）所示。问题的目标状态设定为图2-7-1（b）。当任意给定一初始状态后，求解该问题的过程如下：,图 2-7-1 状态的描述及其目标状态,2.7 过程式表示,（1）首先移动棋牌，使得棋子1和空格均不在位置c上。（2）依次移动棋牌 ，使得空格位置沿图2-8-2（a）所示的箭头方向移动，直到棋子1位于a为止。（3）依次移动将牌 ，使得空格位置沿

28、图2-8-2（b）所示的箭头方向移动，直到数码2位于b为止。若这时刚好数码3在位置c，则转 （6）。 （4） 依次移动将牌，使得空格位置沿书上所示的箭头方向移动，直到数码3位于e为止。这时空格刚好在位置d。,经过以上4步，得到的状态如图 2-7-3（a）所示。其中“”表示除空格以外的任何将牌。,2.7 过程式表示,图2-8-2 空格移动方向示意图,2.7 过程式表示,（5） 依次移动将牌，使得空格位置沿图2-8-2（d）所示的箭头方向移动，直到空格又回到了d为止。此时状态如图2-8-3（b）所示。（6） 依次移动将牌，使得空格位置沿图2-8-2（e）所示的箭头方向移动，直到数码4在位置f为止。

29、若这时刚好数码5在位置i则转（9）。（7） 依次移动将牌，使得空格位置沿图2-8-2（f）所示的箭头方向移动，直到数码5位于e为止。这时空格刚好在位置d。（8） 依次移动将牌，使得空格位置沿图2-8-2（g）所示的箭头方向移动，直到空格又回到位置d为止。 （9） 依次移动将牌，使得空格位置沿图2-8-2（h）所示的箭头方向移动，直到数码6在位置h为止，若这时数码7、8分别在位置g和d，则问题得解，否则，说明由所给初始状态达不到所要求的目标状态。,2.7 过程式表示,图 八数码问题示例,给出应用以上过程求解一个具体的八数码问题的例子，其中(1)(9)9个状态分别对应了以上过程的(1)(9)9个步

30、骤结束时所达到的状态 ：,2.7 过程式表示,2.8 小结,状态空间法是一种基于解答空间的问题表示和求解方法。从某个初始状态开始,每次加一个操作符,递增地建立起操作符的试验序列,直到达到目标状态为止。 问题归约法从目标(要解决的问题)出发,逆向推理,通过一系列变换把初始问题变换为子问题集合和子子问题集合,直至最后归约为一个平凡的本原问题集合。用与或图来有效地说明问题归约法的求解途径 谓词逻辑法采用谓词合适公式和一阶谓词演算把要解决的问题变为一个有待证明的问题,然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的,从而证明这个新语句也是正确的。,表2.8.1 知识表示法的比较,2.

31、8 小结,语义网络是一种结构化表示方法,它由节点和弧线或链线组成。节点用于表示物体.概念和状态,弧线用于表示节点间的关系。语义网络的解答是一个经过推理和匹配而得到的具有明确结果的新的语义网络。语义网络可用于表示多元关系,扩展后可以表示更复杂的问题。 框架是一种结构化 表示方法。框架通常由 指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。大多数实用系统必须同时使用许多框架，并可把它们联成一个框架系统。 过程是一种知识的过程式表示，它将某一有关问题领域知识同这些使用方法一起，隐式地表示为一个问题求解过程。过程表示用程序来描述问题，具有很高的问题求解效率。由于知识隐含在程序中难以操作，因此适用范围较窄。,谢谢观看,XIEXIEDAJIAGUANKAN,