人工智能及其应用2(蔡自兴)

1,第二章知识表示方法,2.1状态空间法2.2问题归约法2.3谓词逻辑法2.4语义网络法2.5其他方法2.6小结,2,2.1状态空间法（StateSpaceRepresentation）,问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）:表示问题解法中每一步问题状况的数据结构算符（operator):把问题从一种状态变换为另一种状态的手段状态空间方法:基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的,3,2.1.1问题状态描述,定义状态(State)：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。算符(Operate)：使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间(StateSpace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。,2.1状态空间法,4,状态空间表示概念详释,状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符的实验序列，直到达到目标状态止。例如下棋、迷宫及各种游戏。,MiddleState,GoalState,2.1状态空间法,5,例:三数码难题（3puzzleproblem）,初始棋局,目标棋局,2.1状态空间法,6,有向图一对节点用弧线连接起来，从一个节点指向另一个节点这种图叫做有向图。路径某个节点序列（ni1，ni2，nik）当j=2，3，k时，如果对于每一个ni，j-1都有一个后继节点ni，j存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径代价用c（ni，nj）来表示从节点ni指向节点nj的那段弧线的代价。两点间路径的代价等于连接该路径上各节点的所有弧线代价之和.,2.1.2状态图示法,2.1状态空间法,7,图的显示说明对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价(举例：邻接表，邻接矩阵)图的隐示说明说明节点的无限集合si作为起始节点是已知的。后继节点算符（gamma）也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。（举例：棋局）表示方法的多样性如十五数码难题中规则1：移动数码（15X4条规则）规则2：移动空格（4条规则）,8,产生式系统搜索过程描述,产生式系统（productionsystem）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,2.1状态空间法,9,状态空间表示实例（1）,例：猴子和香蕉问题,2.1状态空间法,10,解题过程,用一个四元表列（W，x，Y，z）来表示这个问题状态.W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0,这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）,2.1状态空间法,11,pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）应当注意的是，要应用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件,climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox（W，1，W，z）提问：应用算符climbbox的先决条件是什么？,2.1状态空间法,12,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状态空间法,13,目标状态,goto（U）,goto（U）,U=b，climbbox,goto（U）,U=b,pushbox（V）,猴子和香蕉问题的状态空间图,goto（U）,U=V,2.1状态空间法,14,猴子和香蕉问题自动演示：,2.1状态空间法,15,状态空间表示实例（2）,推销员旅行问题一个推销员计划出访推销产品。他从一个城市(如A)出发,访问每个城市一次,且最多一次,然后A返回城市A。要求寻找最短路线,如图2.3所示。为了确定这个问题,作如下规定:(1)总数据库是到目前为止所访问过的城市表.初始数据库被描述为表(A)。不允许目录表中任一城市出现多于一次,只有城市A例外,但也只有当所有其他城市均已出现之后,才能再次出现A。(2)规则对应于决策:即下一步走向城市A;下一步走向城市B;下一步走向城市E。一条规则除非能够把某个数据库变为一个合法数据库,否则就不适用于这个数据库。例如,应用下一步走向城市A这条规则就不适用于尚未出现所有其他城市的任一数据库。(3)任一以A为起点和终点,并出现所有其他城市的总数据库,都满足终止条件。可以使用下图的距离图表来计算任一旅程的总距离。提出作为解答的任一旅程,必须是具有最短距离的旅程。,2.1状态空间法,16,2.1状态空间法,17,2.2问题归约法（ProblemReductionRepresentation）问题归约法思想先把问题分解为子问题及子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答,18,问题归约表示的组成部分：（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。,问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2.2问题规约法,19,2.2.1问题归约描述（ProblemReductionDescription）,梵塔难题,2.2问题规约法,思考：用状态空间法有多少个节点？为什么？,20,解题过程,将原始问题归约为一个较简单问题集合将原始梵塔难题归约（简化）为下列子难题移动圆盘A和B至柱子2的双圆盘难题移动圆盘C至柱子3的单圆盘难题移动圆盘A和B至柱子3的双圆盘难题详细过程参看下图,21,解题过程（3个圆盘问题）,2.2问题规约法,22,梵塔问题归约图,2.2问题规约法,23,多圆盘梵塔难题思考？,2.2问题规约法,24,问题归约的描述,问题归约方法应用算符把问题描述转化为子问题描述，可以采用各种数据结构：表列、树、字符串、矢量、数组等；例如梵塔问题的表示：包含两个数列的表列：(113),(333)也可以用状态空间表示法的三元组（S，F，G）表示；其子问题描述规定了最后解答路径将要通过的中间状态；可以把问题归约发看成比状态空间法更通用的问题求解方法；其核心实现是不断简化问题，直至问题成为本原问题（已知问题、易解问题）；,2.2问题规约法,25,2.2.2与或图表示,1.与图、或图、与或图一般，我们用一个似图结构来表示把问题归约为后继问题的替换集合，这一似图结构叫做问题归约图，或叫与或图。如下所示,2.2问题规约法,26,2.2问题规约法,与或图,增加附加节点后的规范化与或图表示：,27,2.一些关于与或图的术语,2.2问题规约法,28,一些关于与或图的术语,父节点、子（后继）节点、弧线起始节点终叶节点：对应于原问题的本原节点或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B，C）和（D，E，F）。各个节点之间用一端小圆弧连接标记。与或图：由与节点及或节点组成的结构图。,2.2问题规约法,29,3.定义,可解节点的一般定义：终叶节点是可解节点(因为它们与本原问题相关连)。：如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。,2.2问题规约法,30,不可解节点的一般定义：没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。,2.2问题规约法,31,如图所示,2.2问题规约法,与或图例子,t,t,t,t,t,t,t,t,t,（a）,（b）,有解节点,无解节点,终叶节点,32,与或图构成规则,（1）与或图中的每个节点代表一个要解决的单一问题或问题集合。起始节点对应于原始问题。（2）对应于本原问题的节点，叫做终叶节点（3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合，只要其中任意一个有解，问题A就可解，所有这些子问题节点称为或节点；（4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点,只有所有子问题都有解，这个子问题的集合才有解，所有这些子问题节点叫做与节点。这些具有共同父节点的与节点用小圆弧连接，以表示与或节点的区别；（5）在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。（即不增加附加节点的情况下）,2.2问题规约法,33,梵塔问题归约图,（322）（333）,2.2问题规约法,数据结构介绍,思考题：四圆盘问题,34,2.3谓词逻辑法(PredicateLogic),逻辑语句：一种形式语言，它能够把逻辑论证符号化，并用于证明定理，求解问题。形式语言：严格地按照相关领域的特定规则，以数学符号（符号串）形式描述该领域有关客体的表达式,2.3.1谓词演算语法与语义基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号谓词演算的解释：谓词符号对应关系，常量符号论域实体，函数符号对应函数；,35,原子公式：由若干谓词符号和项组成的谓词演算。原子公式是谓词演算基本积木块。项包括常量符号、变量符号、函数符号等。定义原子公式为真值或假值就表示了某种语义。无变量的原子公式取值确定，包含变量的原子公式取值不定。例如：INROOM（ROBOT，r1）为真INROOM（ROBOT，r2）为假MARRIEDfather(wang),mother(wang),2.3谓词逻辑法,36,连词和量词(ConnectiveES2=Px,f(A),B;ES3=Pq(z),f(A),B;ES4=Pc,f(A),B;ES1S2=Pz,f(w),B;ES2S1=Pz,f(A),B思考：(1)ES4S1，ES3S2？(2)置换的运算规则？,2.3谓词逻辑法,45,置换的性质可结合律:（LS1）S2=L（S1S2）（S1S2）S3=S1（S2S3）问题：请举例说明？不可交换律:S1S2=S2S1问题：请举例说明？思考：什么置换是谓词逻辑推理所需要的？,2.3谓词逻辑法,/,46,合一（Unification)：合一：寻找项对变量的置换，以使多个表达式一致的操作称为合一。如果一个置换s作用于表达式集Ei的每个元素，则我们用Eis来表示置换例的集。可合一：如果存在置换s使得表达式集Ei置换后有：E1SE2SE3S,则我们称表达式集Ei是可合一的，s称为Ei的合一者。例题：表达式集Px,f(y),B,Px,f(B),B的合一者：sA/x,B/y说明：Px,f(y),BsPx,f(B),BsPA,f(B),B思考：还有其他合一者吗？,2.3谓词逻辑法,47,最通用的合一者：如果对表达式集Ei的任一合一者s，都存在某一s，使得EisEigs，则称g为Ei的最通用合一者。问题：上例题中，最通用的合一者是什么？置换与合一的作用：谓词逻辑推理的基本方法，就是寻找简单有效置换合一，采用消解原理利用消解反演方法求解问题，详见第三章。,2.3谓词逻辑法,48,2.4语义网络法(SemanticNetworkRepresentation),语义网络的结构定义语义网络是知识的一种图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。组成部分词法决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。结构叙述符号排列的约束条件，指定各弧线连接的节点对过程说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。语义确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。,49,语义网络的特点:(1)能把实体的结构、属性与实体间的因果关系显式并简明地表达出来,与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来。这样便以联想方式实现对系统的解释。(2)由于与概念相关的属性和联系被组织在一个相应的节点中,因而使概念易于受访和学习。(3）表现问题更加直观,更易于理解,适于知识工程师与领域专家的沟通。语义网络中的继承方式也符合人类的思维习惯。(4)语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定,因而得到的推理不能保证像谓词逻辑法那样有效。(5）节点间的联系可能是线状、树状或网状的,甚至是递归状的结构,使相应的知识存储和检索可能需要比较复杂的过程。,2.4语义网络法,50,表示一些简单事实，如占有关系和其它情况：以节点表示实体与概念，节点间关系以有向链关联。例：小燕是一只燕子，燕子是一种鸟，鸟有翅膀；巢-1是小燕的巢，巢-1是巢中的一个。问题：上述的语义网络为二元关系，无法表示复杂事实，如：小燕从春天到秋天占有巢1。如果采用谓词逻辑表示为一个四元谓词演算：Owns（XIAOYAN,NET-1,SPRING,FALL）思考：用语义网络如何表示上述四元谓词公式？,2.4语义网络法,2.4.1二元语义网络的表示,SWALLOW,BIRD,XIAOYAN,NEST-1,NEST,ISA,ISA,ISA,OWNS,HAS-PART,WINGS,51,Simmons与Slocum扩展了该基本方法：允许节点既可以表示一个物体或一组物体，也可以表示情况与动作。每一情况节点成为事例框，有一组向外的弧，用以说明与该事例有关的各种变量。,2.4语义网络法,SWALLOW,BIRD,XIAOYAN,NEST-1,NEST,ISA,ISA,ISA,OWNEE,OWN-1,OWNER,SPRING,FALL,SITUATION,TIME,OWNERSHIP,ISA,ISA,ISA,ISA,STARTTIME,ENDTIME,52,选择语义基元：问题：如果语义网络只表示一个特定的物体或概念，那么当有更多不直接相关的同类实体与概念时，需要很多独立的语义网络，使得语义网络图复杂化。Solution：通常需要把有关的一组物体或概念的知识用一个语义网络表示出来，否则会造成网络过多，使问题复杂化。试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识，称为选择语义基元。,2.4语义网络法,RED,MYCAR,COLOR,GREEN,LIHUACAR,COLOR,53,2.4语义网络法,RED,MYCAR,COLOR,GREEN,LIHUACAR,COLOR,CAR,ISA,ISA,概念节点与实例节点,FURNITURE,CHAIR,MYCAR,LEATHER,SEAT,BROWN,PERSON,X,ISA,OWNER,ISA,ISA,ISAPART,COLOR,COVERING,椅子的语义网络,54,2.4.2多元语义网络的表示,谓词逻辑与语义网络等效,容易实现一元关系与二元关系表示。,LIMING,MAN,ISA,ISA（LIMING，MAN）或MAN（LIMING）,（语义网络）,（谓词逻辑）,2.4语义网络法,55,多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。,R(X1，X2，Xn),R12(X1，X2)R13(X1，X3)R1n(X1，Xn).Rn-1n(Xn-1，Xn),可转换为,2.4语义网络法,56,多元语义网络的表示实例1,SCORE(BU,TU,(8589),2.4语义网络法,GAME,G25,BU,85-89,TU,VISITINGTEAM,ISA,HOMETEAM,SCORE,57,三元变为二元组合,2.4语义网络法,例JohngaveMarythebook.,（2）用语义网络法表示时引入附加节点G1：,G1,B23,JOHN,GIVER,OBJECT,MARY,GIVE,ISA,RECIPIENT,BOOK,ISA,多元语义网络的表示实例2,58,2.4.3语义网络的推理过程,语义网络表示知识，没有形式语义，没有统一的语义表示法。为了便于下面的叙述,对所用符号作进一步的规定。区分在链的头部和在链的尾部的节点,把在链的尾部的节点称为值节点。另外,还规定节点的槽相当于链,不过取不同的名字而已。如砖块12(BRICK12)有3个链,构成两个槽。其中一个槽只有一个值,另外一个槽有两个值。颜色槽(COLOR)填入红色(RED)ISA槽填入了砖块(BRICK)和玩具(TOY)。,2.4语义网络法,59,继承推理定义：所谓继承就是对事物的描述从概念节点或类节点传递到实例节点，例如下图。,2.4语义网络法,60,三种继承模式值继承：ISA链与AKO（AKindOf）链，常用知识传递方法；放入值侧面中。“如果需要”（Ifneeded）链：有时对不知道的槽值，可以计算得到，通过此计算程序得到知识的模式称为ifneeded链，如通过体积与密度在需要时可以计算其质量。ifneeded程序放入IFNEEDED侧面中。“缺省”继承：在对事务所作假设无十分把握时，可以加上“可能”字样，这种不肯定的值称为“缺省”值，放入槽的DEFAULT侧面中。,2.4语义网络法,61,匹配推理当解决涉及由几部分组成的事物时,必须制定把值从类部件传递到实例部件的路径，称为匹配推理。例如,由于TOY-HOUSE77是TOY-HOUSE的一个实例,所以它必须有两个部件,一个是砖块,另一个是模块(wedge)。另外,作为玩具房的一个部件的砖块必须支撑模块。在图2.19中,玩具房-77部件以及它们之间的链,都用虚线画的节点和箭头来表示。因为这些知识是通过继承而间接知道的,并不是通过实际的节点和链直接知道的。因此,虚线所表示的节点以及箭头所表示的链是虚节点和虚链。,2.4语义网络法,62,现在来研究图2.20中的结构35(STRUCTURE35)。已知这个结构有两个部件,一个砖块BRICK12和一个楔块WEDGE18。一旦在STRUCTURE35和TOY-HOUSE之间放上ISA链,就知道BRICK12必须支撑WEDGE18。在图2.20中用虚线箭头表示BRICK12和WEDGE18之间的SUPPORT虚链。因为很容易做部件匹配,所以虚线箭头的位置和方向很容易被确定。WEDGE18肯定与作为TOY-HOUSE的一个部件的楔块相匹配,而BRICK12肯定与砖块相匹配。,2.4语义网络法,63,2.5框架（Frame）表示,提问：语义网络中个案知识与通用知识的关系问题？Solution：用通用框架存储类似的个案知识。框架：框架是一种结构化表示法，通常采用语义网络中的节点-槽-值表示结构，以通用数据结构的形式存储以往的经验知识。框架与语义网络的关系：框架可以定义为一组语义网络的节点与槽，这组节点与槽可以描述格式固定的事务、行为和事件；语义网络是节点和弧线的集合，也可以看作框架的集合。思考：框架与语义网络的区别？,64,2.5.1框架的构成,框架通常由描述事务的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面可以拥有若干个值。框架的一般结构：,2.5框架表示法,65,一个简单框架的例子对于复杂的问题，必须同时使用许多框架，构成框架系统，例如：思考：框架与框架的关系？,2.5框架表示法,66,框架的关系：一个框架可以是另一个框架的槽值，并且一个框架结构可以作为几个不同框架的槽值。这样相同的信息不必重复存储，节约空间。,2.5框架表示法,67,框架系统的继承关系与树型结构框架的一个重要属性是继承。为此，框架常表示成一种树型结构，树的每一节点就是一个框架结构，子节点与父节点之间用ISA或AKO槽连接。框架的继承方法：当子节点的某些槽值或侧面没有被直接记录时，可以从其父节点继承这些值。树状框架系统的形式：AKO/ISAVALUEPROPDEFAULTSFIF-NEEDEDCONFLICTADD,2.5框架表示法,68,框架系统的基本推理方法特性继承（ISA/AKO链），例如：燕子鸟部分匹配，例如TOYHOUSE从描述中直接引用，例如：ROOM的例子各槽值的相关信息可以指导进行该槽值的描述，如：图2.22的D面解答子节点与父节点差异的原因，例如：三条腿的椅子思考：框架是一种规定格式描述的事务、行为与事件。那么对于具体的应用，当直接套用框架知识推理不顺利时，框架推理的策略？,2.5.1框架的推理,2.5框架表示法,69,推理框架的选择方法：选择与当前情况对应的框架片断，与其他候选框架相匹配，选择最佳匹配；（知识的合成、交叉）允许部分不相匹配的信息，如漏失某项特性比多了某项特性更合理，比如只有一条腿的人比有三条腿的人更合理；（合理推断）查询框架之间保存有关的连接，指出应用此框架不合理的情况下，可以下一步试探的建议框架；如下图：（启发匹配）沿着框架系统的层次向上搜索，知道找到足够通用、与事实不矛盾的框架，或直接使用，或者建立新的下一层框架。（类型匹配与新类生成）,2.5框架表示法,70,2.6剧本（Script）表示,提问：框架中对事件的描述有什么不足？定义：剧本是框架的特殊形式，它用一组槽值描述事件发生的序列。剧本的构成：（1）开场条件（事件发生的前提条件）（2）角色（有关人物的槽值）（3）道具（有关物体的槽值）（4）场景（事件的顺序，场景可以是其他剧本）（5）结果（事件发生后的结果）,71,剧本的例子(1)开场条件(a)顾客饿了,需要进餐。(b)顾客有足够的钱。(2)角色顾客,服务员,厨师,老板。(3)道具食品,桌子,菜单,钱。(4)场景场景l进入餐厅(a)顾