人工智能2(北邮ppt课件).ppt

《人工智能2(北邮ppt课件).ppt》由会员分享，可在线阅读，更多相关《人工智能2(北邮ppt课件).ppt（104页珍藏版）》请在三一办公上搜索。

1、1,第二章 知识表示方法,状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法,2,2.1 状态空间法,问题状态描述状态图示法状态空间表示举例,3,2.1.1 问题状态描述,1、状态（State）的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下：Q=q0,q1,qnT (2.1)式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。 给定每个分量的一组值就得到一个具体的状态，如Qk=qk,q1k,，qnkT (2.2),4,算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步

2、、过程、规则、数学算子、运算符号或逻辑符号等。,5,问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。,6,2、状态空间的表示法对一个问题的状态描述，必须确定3件事：(1) 该状态描述方式，特别是初始状态描述；(2) 操作符集合及其对状态描述的作用；(3) 目标状态描述的特性。,7,八数码问题的状态空间S状态集。八数码的所有的摆法(9!)G指定的某个或某些八数码摆放状态。操作算子数码的移动。4(方向) 8(数码)32个将空格向上移U

3、p将空格向左移Left将空格向下移Down将空格向右移 Right,8,2.1 状态空间法,问题状态描述状态图示法状态空间表示举例,9,2.1.2 状态图示法,图的基本概念图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图(directed graph)。某个节点序列(ni1,ni2,nik)当j=2，3，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(cost) 是给各弧线指定数值以表示加在相应算符上的代价。,10,图的显式说明 是指各节点及其具有代价

4、的弧线由一张表明确给出。图的隐式说明 是指各节点及其具有代价的弧线不能由一张表明确给出。,11,1 4 37 65 8 2,1 37 4 65 8 2,1 4 3 7 65 8 2,1 4 37 8 65 2,1 4 37 65 8 2,1 37 4 65 8 2,1 37 4 65 8 2,1 4 37 65 8 2,4 35 7 6 8 2,1 4 37 8 6 5 2,1 4 37 8 65 2,1 47 6 35 8 2,1 4 37 6 25 8,Up,Left,Down,Right,Up,Down,Down,Up,Right,Left,Left,Right,12,2.1 状态空间法

5、,问题状态描述状态图示法状态空间表示举例,13,2.1.3 状态空间表示举例,1、产生式系统一个产生式系统由下列3部分组成：一个总数据库(global database)，它含有与具体任务有关的信息。一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,14,2、状态空间表示举例,猴子与香蕉的问题,a,c,b,15,状态空间表示 设系统的状态用四元数组描述：S=(w, x, y, z) 其中w:猴子所处水平位置 x:

6、箱子所在水平位置 y:猴子是否在箱子上(y=1,在; y=0，不在) z:猴子是否能拿到香蕉(z=1,拿到; z=0,没有拿到),16,可能出现的状态如下：S0=(a,b,0,0)S1=(b,b,0,0)S2=(c,c,0,0)S3=(c,c,1,0)S4=(c,c,1,1)其中S0为初始状态， S4为目标状态。,17,算符 F=(f1, f2, f3 , f4 )其中 f1 (u) 为猴子走到u处。(w, x, 0, z) (u, x, 0, z) f2 (u) 为猴子走到v处。(x, x, 0, 0 ) (v, v, 0, 0) f3 为猴子爬上台子。 (x, x, 0, z ) (x,

7、x,1, z) f4 为猴子拿到香蕉。 (c, c, 1, 0) (c, c,1, 1 ),18,求解过程,19,旅行商问题（travelling salesman problem,TSP问题）,销售员到几个城市去推销商品，城市之间的距离是已知的，他现在从某一个城市出发，经过每个城市一次，最后又回到出发的城市。要求归划好一条最短路线。,7,7,10,10,10,13,6,5,6,A,B,E,D,C,20,第二章 知识表示方法,状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法,21,2.2 问题归约法,问题归约描述与或图表示,22,2.2.1 问题归约描述,1、问题归约法的

8、概念已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。,23,2、问题归约法的组成部分 （1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。,24,3、示例：梵塔难题问题 有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要

9、求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。,25,1,3,2,C,1,2,3,A,B,A,B,C,26,归约过程：（1）移动圆盘A和B至柱子2的双圆盘难题；（2）移动圆盘C至柱子3的单圆盘难题；（3）移动圆盘A和B至柱子3的双圆盘难题。,27,1,3,2,C,1,2,3,A,B,A,B,C,28,1,2,3,A,B,C,1,2,3,A,B,C,29,1,2,3,A,B,C,1,2,3,A,B,C,30,4、归约描述问题归约方法是应用算符来把问题描述变换为子问题描述。可以用状态空间表示的三元组合(S、F、G)来规定与

10、描述问题；对于梵塔问题，子问题（111）(122)，(122)(322)以及(322)(333)规定了最后解答路径将要通过的脚踏石状态(122)和(322)。问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。,31,(1,1,1)(3,3,3),(1,1,1)(1,2,2),(1,2,2)(3,2,2),(3,2,2)(3,3,3),(1,1,1)(1,1,3),(1,2,3)(1,2,2),(1,1,3)(1,2,3),(3,2,2)(3,3,3),(3,2,2)(3,2,1),(3,3,1)(3,3,3),32,2.2 问题归约法,问题归

11、约描述与或图表示,33,2.2.2 与或图表示,1、与或图的概念用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。,34,35,2、与或图的有关术语父节点 是一个初始问题或是可分解为子问题的问题节点；子节点 是一个初始问题或是子问题分解的子问题节点；或节点 只要解决某个问题就可解决其父辈问题的节点集合；与节点 只有解决所有子问题，才能解决其父辈问题的节点集合；弧线 是父辈节点指向子节点的圆弧连线；终叶节点 是对应于原问

12、题的本原节点。,36,3、与或图的有关定义可解节点 与或图中一个可解节点的一般定义可以归纳如下：(1) 终叶节点是可解节点(因为它们与本原问题相关连)。(2) 如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。(3) 如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。,37,不可解节点 不可解节点的一般定义归纳于下：(1) 没有后裔的非终叶节点为不可解节点。(2) 如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。(3) 如果某个非终叶节点含有与后继节点，那么只

13、要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。,38,4、与或图构图规则 代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2) 对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。(4) 一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。(5) 在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。,39,第二章 知识

14、表示方法,状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法,40,2.3 谓词逻辑法,谓词演算谓词公式置换与合一,41,2.3.1 谓词演算,1、语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值T(真)；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假)。,42,2、连词和量词连词有(与)、(或)，全称量词(x)，存在量词(x)。原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂

15、的合适公式。,43,3、几个有关定义用连词把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。用连词把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。用连词连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。如果前项和后项都是合适公式，那么蕴涵也是合适公式。,44,前面具有符号的公式叫做否定。一个合适公式的否定也是合适公式。量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约

16、束变量，否则就叫它为自由变量。在合适公式中，感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。,45,2.3 谓词逻辑法,谓词演算谓词公式置换与合一,46,2.3.2 谓词公式,1、谓词合适公式的定义在谓词演算中合适公式的递归定义如下：(1) 原子谓词公式是合适公式。(2) 若A为合适公式，则A也是一个合适公式。(3) 若A和B都是合适公式，则(AB)，(AB)，(A=B)和(AB)也都是合适公式。(4) 若A是合适公式，x为A中的自由变元，则(x)A和(x)A都是合适公式。(5) 只有按上述规则(1)至(4)求得的那些公式，才是合适公式。,47,2、合式公式的性质(1) 否定之否定

17、(P)等价于P(2) PQ等价于PQ(3) 狄摩根定律(PQ)等价于PQ(PQ)等价于PQ(4) 分配律P(QR)等价于(PQ)(PR)P(QR)等价于(PQ)(PR),48,(5) 交换律PQ等价于QPPQ等价于QP(6) 结合律(PQ)R等价于P(QR)(PQ)R等价于P(QR)(7) 逆否律PQ等价于QP,49,此外，还可建立下列等价关系：(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)等价于(

18、 y)P(y)( x)P(x)等价于( y)P(y),50,2.3 谓词逻辑法,谓词演算谓词公式置换与合一,51,2.3.3 置换与合一,1、置换假元推理，就是由合适公式W1和W1W2产生合适公式W2的运算。全称化推理，是由合适公式(x)W(x)产生合适公式W(A)，其中A为任意常量符号。一个表达式的置换就是在该表达式中用置换项置换变量。一般说来，置换是可结合的，但置换是不可交换的。,52,2、合一寻找项对变量的置换，以使两表达式一致，叫做合一(unification)。如果一个置换s作用于表达式集Ei的每个元素，则用Eis来表示置换例的集。称表达式集Ei是可合一的。如果存在一个置换s使得：E

19、1s=E2s=E3s=那么称此s为Ei的合一者，因为s的作用是使集合Ei成为单一形式。,53,举例：表达式Px,f(y),B的一个置换为s1=z/x,w/y， 则：Px,f(y),Bs1=Pz,f(w),B,54,2.4 语义网络法,二元语义网络的表示多元语义网络的表示连词和量化的表示语义网络的推理过程,55,2.4.1 二元语义网络的表示,、语义网络的基本概念 语义网络是知识的一种结构化图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。,56,语义网络表示由下列4个相关部分组成： (1) 词法部分 决定表示词汇表中允许有哪些符号，它涉及各个节点和弧

20、线。(2) 结构部分 叙述符号排列的约束条件，指定各弧线连接的节点对。(3) 过程部分 说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。(4) 语义部分 确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。,57,语义网络具有下列特点：(1) 能把实体的结构、属性与实体间的因果关系显式地和简明地表达出来，与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来。(2) 由于与概念相关的属性和联系被组织在一个相应的节点中，因而使概念易于受访和学习。(3) 表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。(4) 语义网络结构的语义解释依赖于该结构

21、的推理过程而没有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有效。(5) 节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程。,58,2、二元语义网络的表示 用两个节点和一条弧线可以表示一个简单的事实，对于表示占有关系的语义网络，是通过允许节点既可以表示一个物体或一组物体，也可以表示情况和动作。每一情况节点可以有一组向外的弧(事例弧)，称为事例框，用以说明与该事例有关的各种变量。,60,举例：用二元语义网络表示：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。,62,分清概念节点与实例节点 在选择节点时，首先要弄清节点是

22、用于表示基本的物体或概念的，或是用于多种目的的。否则，如果语义网络只被用来表示一个特定的物体或概念，那么当有更多的实例时就需要更多的语义网络。,64,选择语义基元 试图用一组基元来表示知识。这些基元描述基本知识，并以图解表示的形式相互联系。用这种方式，可以用简单的知识来表示更复杂的知识。,66,2.4 语义网络法,二元语义网络的表示多元语义网络的表示连词和量化的表示语义网络的推理过程,67,2.4.2 多元语义网络的表示,语义网络是一种网络结构。节点之间以链相连。从本质上讲，接点之间的连接是二元关系。语义网络从本质上来说，只能表示二元关系，如果所要表示的事实是多元关系，则把这个多元关系转化成一

23、组二元关系的组合，或二元关系的合取。具体来说，多元关系R(X1，X2，Xn)总可以转换成R1 (X11，X12)R2 (X21，X22)Rn (Xn1,Xn2)。要在语义网络中进行这种转换需要引入附加节点。,68,69,2.4 语义网络法,二元语义网络的表示多元语义网络的表示连词和量化的表示语义网络的推理过程,70,2.4.3 连词和量化的表示,可以用语义网络表示谓词逻辑法中的各种连词及量化。1.合取 多元关系可以被转换成一组二元关系的合取，从而可以用语义网络的形式表示出来。2.析取 在语义网络中，为与合取关系相区别，在析取关系的连接上加注析取界限，并标记DIS。,71,3.否定 采用ISA和

24、PART OF关系或标注NEG界限来表示否定。4.蕴涵 在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。5.量化 存在量化在语义网络中可直接用ISA链来表示。而全称量化就要用分割方法来表示。,72,2.4 语义网络法,二元语义网络的表示多元语义网络的表示连词和量化的表示语义网络的推理过程,73,2.4.4 语义网络的推理过程,74,1.继承,75,值继承如果需要继承缺省继承,76,2.匹配,77,2.5 其他方法,框架表示法剧本表示法过程表示法,78,2.5.1 框架,1、框架的构成框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。一个框

25、架的一般结构如下： 框架名槽1侧面11值111侧面12值121槽2侧面21值211 槽n侧面n1值n11侧面nm值nm1,79,较简单的情景是用框架来表示诸如人和房子等事物。例如，一个人可以用其职业、身高和体重等项描述，因而可以用这些项目组成框架的槽。当描述一个具体的人时，再用这些项目的具体值填入到相应的槽中。,80,简单框架示例,81,框架是一种通用的知识表达形式，对于如何运用框架系统还没有一种统一的形式，常常由各种问题的不同需要来决定。,82,2、框架的推理如前所述，框架是一种复杂结构的语义网络。因此语义网络推理中的匹配和特性继承在框架系统中也可以实行。除此以外，由于框架用于描述具有固定格

26、式的事物、动作和事件，因此可以在新的情况下，推论出未被观察到的事实。,83,框架用以下几种途径来帮助实现这一点：(1) 框架包含它所描述的情况或物体的多方面的信息。(2) 框架包含物体必须具有的属性。在填充框架的各个槽时，要用到这些属性。(3) 框架描述它们所代表的概念的典型事例。,84,用一个框架来具体体现一个特定情况的过程，经常不是很顺利的。但当这个过程碰到障碍时，经常不必放弃原来的努力去从头开始，而是有很多办法可想的：(1) 选择和当前情况相对应的当前的框架片断，并把这个框架片断和候补框架相匹配。选择最佳匹配。(2) 尽管当前的框架和要描述的情况之间有不相匹配的地方，但是仍然可以继续应用

27、这个框架。(3) 查询框架之间专门保存的链，以提出应朝哪个方向进行试探的建议。(4) 沿着框架系统排列的层次结构向上移动(即从狗框架哺乳动物框架动物框架)，直到找到一个足够通用，并不与已有事实矛盾的框架。,85,2.5 其他方法,框架表示法剧本表示法过程表示法,86,2.5.2 剧本,剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列，就像剧本中的事件序列一样，故称为“剧本”或脚本。,87,一个剧本一般由以下各部分组成：(1) 开场条件 给出在剧本中描述的事件发生的前提条件。(2) 角色 用来表示在剧本所描述的事件中可能出现的有关人物的一些槽。(3) 道具 这是用来表示在剧本所描述的

28、事件中可能出现的有关物体的一些槽。(4) 场景 描述事件发生的真实顺序，可以由多个场景组成，每个场景又可以是其它的剧本。(5) 结果 给出在剧本所描述的事件发生以后通常所产生的结果。,88,例子：以餐厅剧本为例说明剧本各个部分的组成。,91,根据剧本的重要性，可以有二种准备剧本的方法。(1) 对于不属于事件核心部分的剧本，只需设置指向该剧本的指针即可，以便当它成为核心时启用。(2) 对于符合事件核心部分的剧本，则应使用在当前事件中涉及到的具体对象和人物去填写剧本的槽。剧本的前提、道具、角色和事件等常能起到启用剧本的指示器的作用。,92,一旦剧本被启用，则可以应用它来进行推理。其中最重要的是运用

29、剧本可以预测没有明显提及的事件的发生。剧本结构，比起框架这样的一些通用结构来，要呆板得多，知识表达的范围也很窄，因此不适用于表达各种知识，但对于表达预先构思好的特定知识，如理解故事情节等，是非常有效的。,93,2.5 其他方法,框架表示法剧本表示法过程表示法,94,2.5.3 过程,语义网络、框架和剧本等知识表示方法，均是对知识和事实的一种静止的表达方法，是知识的一种显式表达形式。而对于如何使用这些知识，则通过控制策略来决定。,95,和知识的陈述式表示相对应的是知识的过程式表示。所谓过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。它所给出的

30、是事物的一些客观规律，表达的是如何求解问题。知识的描述形式就是程序，所有信息均隐含在程序之中。从程序求解问题的效率上来说，过程式表达要比陈述式表达高得多。但因其知识均隐含在程序中，因而难于添加新知识和扩充功能，适用范围较窄。,96,2.6 小 结,知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，结构化方法，陈述式表示和过程式表示等。,97,状态空间法是一种基于解答空间的问题表示和求解方法，它是以状态和操作符为基础的。在利用状态空间图表示时，从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，

31、因而只适用于表示比较简单的问题。,98,问题归约法从目标(要解决的问题)出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本原问题集合。这些本原问题的解可以直接得到从而解决了初始问题，用与或图来有效地说明问题归约法的求解途径。问题归约法能够比状态空间法更有效地表示问题。状态空间法是问题归约法的一种特例。在问题归约法的与或图中，包含有与节点和或节点，而在状态空间法中只含有或节点。,99,谓词逻辑法采用谓词合适公式和一阶谓词演算把要解决的问题变为一个有待证明的问题，然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也

32、是正确的。谓词逻辑是一种形式语言，能够把数学中的逻辑论证符号化。谓词逻辑法常与其它表示方法混合使用，灵活方便，可以表示比较复杂的问题。,100,语义网络是一种结构化表示方法，它由节点和弧线或链线组成。节点用于表示物体、概念和状态，弧线用于表示节点间的关系。语义网络的解答是一个经过推理和匹配而得到的具有明确结果的新的语义网络。语义网络可用于表示多元关系，扩展后可以表示更复杂的问题。,101,框架是一种结构化表示方法。框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。大多数实用系统必须同时使用许多框架，并可把它们联成一个框架系统。框架表示已获广泛应用，然而并非所

33、有问题都可以用框架表示。,102,剧本是框架的一种特殊形式，它使用一组槽来描述事件的发生序列。剧本表示特别适用于描述顺序性动作或事件，但使用不如框架灵活，因此应用范围也不如框架那么广泛。,103,过程是一种知识的过程式表示，它将某一有关问题领域知识同这些使用方法一起，隐式地表示为一个问题求解过程。过程表示用程序来描述问题，具有很高的问题求解效率。由于知识隐含在程序中难以操作，所以适用范围较窄。,104,在表示和求解比较复杂的问题时，采用单一的知识表示方法是远远不够的。往往必须采用多种方法混合表示。例如，综合采用框架、语义网络、谓词逻辑的过程表示方法(两种以上)，可使所研究的问题获得更有效的解决。此外，在选择知识表示方法时，还要考虑所使用的程序设计语言所提供的功能和特点，以便能够更好地描述这些表示方法。,