人工智能及其应用蔡自兴第四版课件.ppt

1、2第二章 知识表示方法w 2.1 状态空间法w 2.2 问题归约法w 2.3 谓词逻辑法w 2.4 语义网络法w 2.5 其他方法w 2.6 小结32.1状态空间法（State Space Representation）w 问题求解技术主要是两个方面：问题求解技术主要是两个方面：问题的表示问题的表示求解的方法求解的方法w 状态空间法状态空间法状态状态（state）:表示问题解法中每一步问题状况的表示问题解法中每一步问题状况的数据结构数据结构算符算符（operator):把问题从一种状态变换为另一种把问题从一种状态变换为另一种状态的状态的手段手段状态空间方法状态空间方法:基于解答空间的问题表示和

2、求解方基于解答空间的问题表示和求解方法，它是以法，它是以状态和算符状态和算符为基础来表示和求解问题为基础来表示和求解问题的的42.1.1 问题状态描述w 定义状态(State)：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。算符(Operate)：使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间(State Space)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1 状态空间法5状态空间表示概念详释w 状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符的实验序列，直到达到目标状

3、态止。w 例如下棋、迷宫及各种游戏。Original StateMiddleStateGoalState2.1 状态空间法6例:三数码难题（3 puzzle problem）123123123312312312初始棋局目标棋局2.1 状态空间法7w 有向图 一对节点用弧线连接起来，从一个节点指向另一个节点这种图叫做有向图。w 路径 某个节点序列（ni1，ni2，nik）当 j=2，3，k时，如果对于每一个ni，j-1都有一个后继节点ni，j存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径w 代价 用c（ni，nj）来表示从节点ni指向节点nj的那段弧线的代价。两点间路径的

4、代价等于连接该路径上各节点的所有弧线代价之和.2.1.2 状态图示法2.1 状态空间法AB8w 图的显示说明 对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价(举例：举例：邻接表，邻接矩阵)w 图的隐示说明 说明节点的无限集合si作为起始节点是已知的。后继节点算符（gamma）也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。（举例：举例：棋局）w 表示方法的多样性 如十五数码难题中规则1：移动数码（15X4条规则）规则2：移动空格（4条规则）9产生式系统搜索过程描述w 产生式系统（productio

5、n system）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性适用性或先决条件以及右部描述规则应用时所完成的动作动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法10 状态空间表示实例（状态空间表示实例（1 1）w 例：猴子和香蕉问题2.1 状态空间法11解题过程w 用一个四元表列（W，x，Y，z）来表示这个问题状态.W 猴子的水平位置x 当猴子在箱子顶上时取 x=1；否则取 x=0w Y 箱子的水平位置z 当猴子摘到香蕉时取

6、 z=1；否则取 z=0w 这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1 状态空间法12w pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）应当注意的是，要应用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件w climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox （W，1，W，z）提问：应用算符climbbox的先决条

7、件是什么？2.1 状态空间法13w grasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）令初始状态为令初始状态为(a(a，0 0，b b，0)0)。这时，。这时，goto(Ugoto(U)是唯是唯一适用的操作，并导致下一状态一适用的操作，并导致下一状态(U(U，0 0，b,0)b,0)。现在。现在有有3 3个适用的操作，即个适用的操作，即goto(U)goto(U)，pushbox(V)pushbox(V)和和climbboxclimbbox(若若U=b)U=b)。把所有适用的操作继续应用于每。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图，如下图所示。个

8、状态，我们就能够得到状态空间图，如下图所示。从图不难看出，把该从图不难看出，把该初始状态变换为目标状态的操初始状态变换为目标状态的操作序列作序列为为 goto(b),push box(c),climbbox,grasp2.1 状态空间法14(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，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法15猴子和香蕉问题自动演示：猴子猴子

9、香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 状态空间法16状态空间表示实例（状态空间表示实例（2 2）w 推销员旅行问题一个推销员计划出访推销产品。他从一个城市(如 A)出发,访问每个城市一次,且最多一次,然后 A返回城市 A。要求寻找最短路线,如图 2.3 所示。为了确定这个问题,作如下规定:(1)总数据库是到目前为止所访问过的城市表.初始数据库被描述为表(A)。不允许目录表中任一城市出现多于一次,只有城市 A 例外,但也只有当所有其他城市均已出现之后,才能 再次出现 A。(2)规则对应于决策:即下一步走向城市 A;下一步走向城市 B;下一步走向城市E。一条规则除非能够把

10、某个数据库变为一个合法数据库,否则就不适用于这个数据 库。例如,应用 下一步走向城市 A 这条规则就不适用于尚未出现所有其他城市的任一 数据库。(3)任一以 A 为起点和终点,并出现所有其他城市的总数据库,都满足终止条件。可以使用下图的距离图表来计算任一旅程的总距离。提出作为解答的任一旅程,必须是具有最短距离的旅程。2.1 状态空间法17ABDE(ACDEBA)推销员旅行问题状态空间图(A)起始节点2.1 状态空间法182.2 问题归约法（Problem Reduction Representation）问题归约法思想 先把问题分解为子问题及子-子问题，然后解决较小的问题。对该问题的某个具体子

11、集的解答就意味着对原始问题的一个解答子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题19w 问题归约表示的组成部分：（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。w 问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法202.2.1 问题归约描述（Problem Reduction Description）w 梵塔难题123CBA2.2 问题规约法思考：用状态空间法有多少个节点？为什么？21解题过程w 将原始问题归约为一个较简单问题集合w

12、将原始梵塔难题归约（简化）为下列子难题移动圆盘移动圆盘A A和和B B至柱子至柱子2 2的双圆盘难题的双圆盘难题移动圆盘移动圆盘C C至柱子至柱子3 3的单圆盘难题的单圆盘难题移动圆盘移动圆盘A A和和B B至柱子至柱子3 3的双圆盘难题的双圆盘难题w 详细过程参看下图详细过程参看下图22解题过程（3个圆盘问题）1231231231231231231232.2 问题规约法12323梵塔问题归约图2.2 问题规约法24多圆盘梵塔难题思考？2.2 问题规约法25问题归约的描述w 问题归约方法应用算符把问题描述转化为子问题描述，可以采用各种数据结构：表列、树、字符串、矢量、数组等；例如梵塔问题的表示

13、：包含两个数列的表列：(113),(333)w 也可以用状态空间表示法的三元组（S，F，G）表示；其子问题描述规定了最后解答路径将要通过的中间状态；w 可以把问题归约发看成比状态空间法更通用的问题求解方法；其核心实现是不断简化问题，直至问题成为本原问题（已知问题、易解问题）；2.2 问题规约法262.2.2与或图表示w 1.与图、或图、与或图 一般，我们用一个似图结构来表示把问题归约为后继问题的替换集合，这一似图结构叫做问题归约图，或叫与或图。如下所示2.2 问题规约法ABCD与图ABC或图272.2 问题规约法BCDEFGAHMBCDEFGAN与或图与或图增加附加节点后的规范化与或图表示：2

14、82.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点29一些关于与或图的术语w 父节点、子（后继）节点、弧线w 起始节点w 终叶节点：对应于原问题的本原节点w 或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。w 与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B，C）和（D，E，F）。各个节点之间用一端小圆弧连接标记。w 与或图：由与节点及或节点组成的结构图。2.2 问题规约法303.定义可解节点的一般定义：终叶节点是可解节点(因为它们与本原问题相关连)。：如果某个非终叶节点含有或后继节点，那么只要当其后继节

15、点至少有一个是可解的时，此非终叶节点才是可解的。如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。2.2 问题规约法31不可解节点的一般定义：w 没有后裔的非终叶节点为不可解节点。w 全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。w 后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。2.2 问题规约法32如图所示2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点33与或图构成规则w（1）与或图中的每个节点代表一个要解决的单一问题或问题集合。起始节点对应于原始

16、问题。w（2）对应于本原问题的节点，叫做终叶节点w（3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合，只要其中任意一个有解，问题A就可解，所有这些子问题节点称为或节点；w（4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点,只有所有子问题都有解，这个子问题的集合才有解，所有这些子问题节点叫做与节点。这些具有共同父节点的与节点用小圆弧连接，以表示与或节点的区别；w（5）在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4

17、所产生的图可以得到简化。（即不增加附加节点的情况下）2.2 问题规约法34梵塔问题归约图（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）2.2 问题规约法数据结构介绍数据结构介绍思考题：四圆盘问题思考题：四圆盘问题352.3 谓词逻辑法(Predicate Logic)w 逻辑语句：一种形式语言，它能够把逻辑论证符号化，并用于证明定理，求解问题。w 形式语言：严格地按照相关领域的特定规则，以数学符号（符号串）形式描述该领域有关客体的表达式2.3

18、.1 谓词演算w 语法与语义基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号谓词演算的解释：谓词符号对应关系，常量符号论域实体，函数符号对应函数；36原子公式：由若干谓词符号和项组成的谓词演算。原子公式是谓词演算基本积木块。项包括常量符号、变量符号、函数符号等。定义原子公式为真值或假值就表示了某种语义语义。无变量的原子公式取值确定，包含变量的原子公式取值不定。例如：INROOM（ROBOT，r1）为真 INROOM（ROBOT，r2）为假 MARRIEDfather(wang),mother(wang)2.3 谓词逻辑法37w 连词和量词(Connective&Quantifier

19、s)连词 与、合取（conjunction)：用连词把几个公式连接起来而构成的公式。合取项是合取式的每个组成部分。例：LIKE(I，MUSIC)LIKE(I，PAINTING)（我喜爱音乐和绘画。）或、析取（disjunction）：用连词把几个公式连接起来而构成的公式。析取项是析取式的每个组成部分例：PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL)（李力打篮球或踢足球。）蕴涵（Implication）:“=”表示“如果那么”（IFTHEN）关系，其所构成的公式叫做蕴涵。非（Not）表示否定，、均可表示2.3 谓词逻辑法38w 量词 全称量词（Univers

20、al Quantifier）：若一个原子公式P（x），对于所有可能变量 x都具有T值，则用 （x）P（x）表示例如:所有的机器人都是灰色的（x）ROBOT(x)=COLOR(x,GRAY)约束变元约束变元全程量词作用域全程量词作用域存在量词（Existential Quantifier）若一个原子公式P（x），至少有一个变元x，可使P （x）为T值，则用（x）P（x）表示。例：(x)INROOM(x,r1)（1号房间内有个物体）392.3.2 谓词公式原子公式的的定义：用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn

21、)叫做谓词演算的原子公式原子公式，或原子谓词公式原子谓词公式。分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式分子谓词公式。2.3 谓词逻辑法40w 合式公式（WFF，well-formed formulas）合式公式的递归定义(1)原子谓词公式是合式公式。(2)若A为合适公式，则A也是一个合式公式。(3)若A和B都是合式公式，则(AB)，(AB)，(AB)和(AB)也都是合式公式。(4)若A是合式公式，x为A中的自由变元，则(x)A和(x)A都是合式公式。(5)只有按上述规则(1)至(4)求得的那些公式，才是合式公式。例题：试把下列命题表示为谓词公式：任何整数，

22、或者为整数或者为负数。2.3 谓词逻辑法41w 合式公式的性质合式公式的真值等价（Equivalence)如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是等价的。T F T F F F表表2-1 真值表真值表P Q PQ P Q PQ PT T T T T FF T T F T TF F F F T T2.3 谓词逻辑法42等价关系w(1 否定之否定(P)等价于 Pw(2)P Q 等价于 P=Qw(3)狄摩根定律(P Q)等价于 P Q(P Q)等价于 P Qw(4 分配律P(Q R)等价于(P Q)(P R)P (Q R)等价于(P Q)(P R)w(5)交换律

23、P Q 等价于 Q PP Q 等价于 Q P 2.3 谓词逻辑法43w 6)结合律(P Q)R 等价于 P(Q R)(P Q)R 等价于 P (Q R)w(7)逆否律P=Q 等价于 Q=Pw(8)(x)P(x)等价于(x)P(x)(x)P(x)等价于(x)P(x)w(9)(x)P(x)Q(x)等价于(x)P(x)(x)Q(x)(x)P(x)Q(x)等价于(x)P(x)(x)Q(x)w(10 (x)P(x 等价于(y)P(y)(x)P(x)等价于(y)P(y)442.3.3 置换与合一w 谓词逻辑的推理谓词逻辑的推理将推理规则应用于一定的合式公式（集），以产将推理规则应用于一定的合式公式（集），

24、以产生新的合式公式。生新的合式公式。假元推理假元推理 全称化推理全称化推理 综合推理综合推理 思考：推理规则中存在项的变换与同一问题，思考：推理规则中存在项的变换与同一问题，如何实施？如何实施？2.3 谓词逻辑法W1W1W2 W2（x）W（x）W（A）任意变量任意变量约束变元约束变元(x)W1(x)W2(x)W1（A）W2（A）45w 置换置换(Substitution)：在表达式中用置换项置换变量，例如用项（在表达式中用置换项置换变量，例如用项（A）替换函数表达式中的变量（替换函数表达式中的变量（x）。一个表达式）。一个表达式E（Expression）用一个置换）用一个置换S（Substit

25、ution）而）而得到的表达式的置换，记为得到的表达式的置换，记为ES。w 例题：表达式例题：表达式E：Px,f(y),B；置换：；置换：s1=z/x,w/y,s2=A/y,s3=q(z)/x,A/y,s4=c/x,A/ySolution:ES1=Pz,f(w),B;ES2=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 谓词逻辑法46w 置换的性质置换的性质 可结合律可结合律:（LS1）S2 =L（S1S2）（

26、S1S2）S3=S1（S2S3）问题：请举例说明？问题：请举例说明？不可交换律不可交换律:S1S2=S2S1问题：请举例说明？问题：请举例说明？思考：什么置换是谓词逻辑推理所需要的？思考：什么置换是谓词逻辑推理所需要的？2.3 谓词逻辑法/47w 合一合一（Unification)：合一：合一：寻找项对变量的置换，以使多个表达式一寻找项对变量的置换，以使多个表达式一致的操作称为致的操作称为合一合一。如果一个置换。如果一个置换s作用于表达式作用于表达式集集Ei的每个元素，则我们用的每个元素，则我们用Ei s来表示置换例来表示置换例的集。的集。可合一：可合一：如果存在置换如果存在置换s使得表达式集

27、使得表达式集Ei置换后置换后有：有：E1S E2S E3S,则我们称表达式集则我们称表达式集Ei是是可合一的可合一的，s 称为称为Ei 的的合一者合一者。w 例题：例题：表达式集表达式集 Px,f(y),B,Px,f(B),B 的合一者：的合一者：s A/x,B/y 说明：说明：Px,f(y),Bs Px,f(B),Bs PA,f(B),B思考：还有其他合一者吗？思考：还有其他合一者吗？2.3 谓词逻辑法48w 最通用的合一者：最通用的合一者：如果对表达式集如果对表达式集Ei的任的任一合一者一合一者s，都存在某一，都存在某一s，使得，使得Eis Eigs，则称，则称g为为Ei的最通用合一者。的

28、最通用合一者。w 问题：上例题中，最通用的合一者是什么？问题：上例题中，最通用的合一者是什么？w 置换与合一的作用：谓词逻辑推理的基本方置换与合一的作用：谓词逻辑推理的基本方法，就是寻找简单有效置换合一，采用消解法，就是寻找简单有效置换合一，采用消解原理利用消解反演方法求解问题，详见第三原理利用消解反演方法求解问题，详见第三章。章。2.3 谓词逻辑法492.4 语义网络法 (Semantic Network Representation)语义网络的结构 定义 语义网络是知识的一种图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。组成部分 词法 决定表

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

30、的继承方式也符合人类的思维习惯。(4)语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定,因而得到的推理不能保证像谓词逻辑法那样有效。(5）节点间的联系可能是线状、树状或网状的,甚至是递归状的结构,使相应的知识存储和检索可能需要比较复杂的过程。2.4 语义网络法51w 表示一些简单事实，如占有关系和其它情况：以节点表示实体与概念，节点间关系以有向链关联。例：小燕是一只燕子，燕子是一种鸟，鸟有翅膀；巢-1是小燕的巢，巢-1是巢中的一个。问题：上述的语义网络为二元关系，无法表示复杂事实，如：小燕从春天到秋天占有巢1。如果采用谓词逻辑表示为一个四元谓词演算：Owns（XIAOYAN,NET

31、-1,SPRING,FALL）思考：用语义网络如何表示上述四元谓词公式思考：用语义网络如何表示上述四元谓词公式？2.4 语义网络法2.4.1 二元语义网络的表示SWALLOWBIRDXIAOYANNEST-1NESTISAISAISAOWNSHAS-PARTWINGS52Simmons与Slocum扩展了该基本方法：允许节点既可以表示一个物体或一组物体，也可以表示情况与动作。每一情况节点成为事例框，有一组向外的弧，用以说明与该事例有关的各种变量。2.4 语义网络法SWALLOWBIRDXIAOYANNEST-1NESTISAISAISAOWNEEOWN-1OWNERSPRINGFALLSITU

32、ATIONTIMEOWNERSHIPISAISAISAISASTARTTIMEENDTIME53w 选择语义基元：问题：如果语义网络只表示一个特定的物体或概念，那么当有更多不直接相关的同类实体与概念时，需要很多独立的语义网络，使得语义网络图复杂化。Solution：通常需要把有关的一组物体或概念的知识用一个语义网络表示出来，否则会造成网络过多，使问题复杂化。试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识，称为选择语义基元。2.4 语义网络法REDMYCARCOLORGREENLIHUACARCOLOR542.4 语义网络法REDMYCARCOLORGREENLIHU

33、ACARCOLORCARISAISA概念节点与实例节点FURNITURECHAIRMYCARLEATHERSEATBROWNPERSONXISAOWNERISAISAISA PARTCOLORCOVERING椅子的语义网络552.4.2 多元语义网络的表示w 谓词逻辑与语义网络等效,容易实现一元关系与二元关系表示。LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（语义网络）（语义网络）（谓词逻辑）（谓词逻辑）2.4 语义网络法56w 多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。R(XR(X1 1，X X2 2，X Xn n)R

34、 R1212(X(X1 1，X X2 2)R)R1313(X(X1 1，X X3 3)R R1n1n(X(X1 1，X Xn n).R Rn-1 nn-1 n(X(Xn-1n-1，X Xn n)可转换为可转换为2.4 语义网络法57多元语义网络的表示实例1w SCORE(BU,TU,(8589)2.4 语义网络法GAMEG25BU85-89TUVISITING TEAMISAHOME TEAMSCORE58w 三元变为二元组合2.4 语义网络法例例 John gave Mary the book.（1）谓词逻辑法）谓词逻辑法：GAVE（JOHN，MARY，BOOK）3项项（2）用用语义网络法语

35、义网络法表示时引入附加节点表示时引入附加节点G1：G1B23JOHNGIVEROBJECTMARYGIVEISARECIPIENTBOOKISA多元语义网络的表示实例2592.4.3 语义网络的推理过程w 语义网络表示知识，没有形式语义，没有统一的语义表示法。w 为了便于下面的叙述,对所用符号作进一步的规定。区分在链的头部和在链的尾部的节点,把在链的尾部的节点称为值节点。另外,还规定节点的槽相当于链,不过取不同的名字而已。如砖块12(BRICK12)有3个链,构成两个槽。其中一个槽只有一个值,另外一个槽有两个值。颜色槽(COLOR)填入红色(RED)ISA槽填入了砖块(BRICK)和玩具(TO

36、Y)。2.4 语义网络法60w 继承推理定义：所谓继承就是对事物的描述从概念节点或类节点传递到实例节点，例如下图。2.4 语义网络法61w 三种继承模式值继承：ISA链与 AKO（A Kind Of）链，常用知识传递方法；放入值侧面中。“如果需要”（Ifneeded）链：有时对不知道的槽值，可以计算得到，通过此计算程序得到知识的模式称为ifneeded链，如通过体积与密度在需要时可以计算其质量。ifneeded程序放入IFNEEDED侧面中。“缺省”继承：在对事务所作假设无十分把握时，可以加上“可能”字样，这种不肯定的值称为“缺省”值，放入槽的DEFAULT侧面中。2.4 语义网络法62w 匹

37、配推理当解决涉及由几部分组成的事物时,必须制定把值从类部件传递到实例部件的路径，称为匹配推理。例如,由于 TOY-HOUSE77 是 TOY-HOUSE 的一个实例,所以它必须有两个部件,一个是砖块,另一个是模块(wedge)。另外,作为玩具房的一个部件的砖块必须 支撑模块。在图 2.19 中,玩具房-77 部件以及它们之间的链,都用虚线画的节点和箭头 来表示。因为这些知识是通过继承而间接知道的,并不是通过实际的节点和链直接知道 的。因此,虚线所表示的节点以及箭头所表示的链是虚节点和虚链。2.4 语义网络法63现在来研究图 2.20中的结构 35(STRUCTURE35)。已知这个结构有两个部

38、件,一 个砖块BRICK12和一个楔块WEDGE18。一旦在STRUCTURE35和TOY-HOUSE之间放上ISA链,就知道BRICK12必须支撑WEDGE18。在图2.20中用虚线箭头表示BRICK12和WEDGE18 之间的SUPPORT虚链。因为很容易做部件匹配,所以虚线箭头的位置和方向很容易被确定。WEDGE18肯定与作为TOY-HOUSE的一个部件的楔块相匹配,而 BRICK12 肯定与砖块相匹配。2.4 语义网络法642.5 框架（框架（Frame）表示）表示w 提问：提问：语义网络中个案知识与通用知识的关系问题？语义网络中个案知识与通用知识的关系问题？Solution：用通用框

39、架存储类似的个案知识。用通用框架存储类似的个案知识。w 框架框架：框架是一种结构化表示法，通常采用语义网框架是一种结构化表示法，通常采用语义网络中的节点络中的节点-槽槽-值表示结构，以通用数据结构的形式值表示结构，以通用数据结构的形式存储以往的经验知识。存储以往的经验知识。w 框架与语义网络的关系：框架与语义网络的关系：框架可以定义为一组语义网络的节点与槽，这组节点与槽框架可以定义为一组语义网络的节点与槽，这组节点与槽可以描述格式固定的事务、行为和事件；可以描述格式固定的事务、行为和事件；语义网络是节点和弧线的集合，也可以看作框架的集合。语义网络是节点和弧线的集合，也可以看作框架的集合。思考：

40、框架与语义网络的区别？思考：框架与语义网络的区别？652.5.1 框架的构成框架的构成w 框架通常由描述事务的各个方面的槽组成，每个槽可以拥有若框架通常由描述事务的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面可以拥有若干个值。干个侧面，而每个侧面可以拥有若干个值。w 框架的一般结构：框架的一般结构：2.5 2.5 框架表示法框架表示法66w 一个简单框架的例子一个简单框架的例子w 对于复杂的问题，必须同时使用许多框架，构成框架对于复杂的问题，必须同时使用许多框架，构成框架系统，例如：系统，例如：w 思考：框架与框架的关系？思考：框架与框架的关系？2.5 2.5 框架表示法框架表示法6

41、7w 框架的关系：框架的关系：一个框架可以是另一个框架的槽值，并且一个一个框架可以是另一个框架的槽值，并且一个框架结构可以作为几个不同框架的槽值。这样相同的信息不必框架结构可以作为几个不同框架的槽值。这样相同的信息不必重复存储，节约空间。重复存储，节约空间。2.5 2.5 框架表示法框架表示法68w 框架系统的继承关系与树型结构框架系统的继承关系与树型结构框架的一个重要属性是继承。为此，框架常表示成一种树型框架的一个重要属性是继承。为此，框架常表示成一种树型结构，树的每一节点就是一个框架结构，子节点与父节点之结构，树的每一节点就是一个框架结构，子节点与父节点之间用间用ISA或或AKO槽连接。槽

42、连接。框架的继承方法：当子节点的某些槽值或侧面没有被直接记框架的继承方法：当子节点的某些槽值或侧面没有被直接记录时，可以从其父节点继承这些值。录时，可以从其父节点继承这些值。w 树状框架系统的形式：树状框架系统的形式：AKO/ISA VALUE PROP DEFAULT SF IF-NEEDED CONFLICT ADD2.5 2.5 框架表示法框架表示法69w 框架系统的基本推理方法框架系统的基本推理方法特性继承（特性继承（ISA/AKO链），例如：燕子链），例如：燕子鸟鸟部分匹配，例如部分匹配，例如TOYHOUSE从描述中直接引用，例如：从描述中直接引用，例如：ROOM的例子的例子各槽值的

43、相关信息可以指导进行该槽值的描述，如：图各槽值的相关信息可以指导进行该槽值的描述，如：图2.22的的D面面解答子节点与父节点差异的原因，例如：三条腿的椅子解答子节点与父节点差异的原因，例如：三条腿的椅子w 思考：框架是一种规定格式描述的事务、行为与事件。那么对思考：框架是一种规定格式描述的事务、行为与事件。那么对于具体的应用，当直接套用框架知识推理不顺利时，框架推理于具体的应用，当直接套用框架知识推理不顺利时，框架推理的策略？的策略？2.5.1 框架的推理框架的推理2.5 2.5 框架表示法框架表示法70w 推理框架的选择方法：推理框架的选择方法：选择与当前情况对应的框架片断，与其他候选框架相

44、匹配，选择最选择与当前情况对应的框架片断，与其他候选框架相匹配，选择最佳匹配；（佳匹配；（知识的合成、交叉知识的合成、交叉）允许部分不相匹配的信息，如漏失某项特性比多了某项特性更合理，允许部分不相匹配的信息，如漏失某项特性比多了某项特性更合理，比如只有一条腿的人比有三条腿的人更合理；（比如只有一条腿的人比有三条腿的人更合理；（合理推断合理推断）查询框架之间保存有关的连接，指出应用此框架不合理的情况下，查询框架之间保存有关的连接，指出应用此框架不合理的情况下，可以下一步试探的建议框架；如下图：可以下一步试探的建议框架；如下图：（启发匹配启发匹配）沿着框架系统的层次向上搜索，知道找到足够通用、与事

45、实不矛盾沿着框架系统的层次向上搜索，知道找到足够通用、与事实不矛盾的框架，或直接使用，或者建立新的下一层框架。（的框架，或直接使用，或者建立新的下一层框架。（类型匹配与新类型匹配与新类生成类生成）2.5 2.5 框架表示法框架表示法712.6 剧本（剧本（Script）表示）表示w 提问：框架中对事件的描述有什么不足？w 定义：剧本是框架的特殊形式，它用一组槽值描述事件发生的序列。w 剧本的构成：（1）开场条件 （事件发生的前提条件）（2）角色 （有关人物的槽值）（3）道具 （有关物体的槽值）（4）场景 （事件的顺序，场景可以是其他剧本）（5）结果 （事件发生后的结果）72w 剧本的例子剧本的

46、例子(1)开场条件开场条件(a)顾客饿了顾客饿了,需要进餐。需要进餐。(b)顾客有足够的钱。顾客有足够的钱。(2)角色角色顾客顾客,服务员服务员,厨师厨师,老板。老板。(3)道具道具食品食品,桌子桌子,菜单菜单,钱。钱。(4)场景场景 场景场景 l 进入餐厅进入餐厅 (a)顾客走入餐厅顾客走入餐厅(b)寻找桌子寻找桌子(c)在桌子旁坐下。在桌子旁坐下。场景场景 2 点菜点菜 (a)服务员给顾客菜单服务员给顾客菜单(b)顾客点菜顾客点菜(c)顾客把菜单还顾客把菜单还给服务员给服务员(d)顾客等待服务员送菜。顾客等待服务员送菜。场景场景 3 等待等待 (a)服务员把顾客所点的菜告诉厨师服务员把顾客

47、所点的菜告诉厨师 (b)厨师做菜。厨师做菜。场景场景 4 吃菜吃菜 (a)厨师把做好的莱给服务员厨师把做好的莱给服务员(b)服务员给顾客送菜服务员给顾客送菜(c)顾客吃菜。顾客吃菜。场景场景 5 离开离开 (a)服务员拿来账单服务员拿来账单(b)顾客付钱给服务员顾客付钱给服务员(c)(c)顾客顾客离开餐厅。离开餐厅。(5)结果结果(a)顾客吃了饭顾客吃了饭,不饿了。不饿了。(b)顾客花了钱。顾客花了钱。(c)老板挣了钱。老板挣了钱。(d)(d)餐厅食品少了。餐厅食品少了。2.6 2.6 剧本表示法剧本表示法73w 剧本推理的方法：剧本推理的方法：剧本中所有描述的事件形成巨大的因果链；剧本中所有

48、描述的事件形成巨大的因果链；剧本中对应于当前情形，其事件一般包括两种处理方式：剧本中对应于当前情形，其事件一般包括两种处理方式：对于不是事件核心部分的剧本，设置指针指向即可，当它成为对于不是事件核心部分的剧本，设置指针指向即可，当它成为核心事件再启用；核心事件再启用；对于事件核心部分的剧本，使用人物、事件、条件等填充槽值，对于事件核心部分的剧本，使用人物、事件、条件等填充槽值，启用其场景序列；启用其场景序列；推理方法：推理方法：剧本启动后，即可按其场景序列推断其过程；剧本启动后，即可按其场景序列推断其过程；运用剧本可以预测未提及的事件；运用剧本可以预测未提及的事件；如过非核心事件的剧本部分启动

49、，场景序列可能改变；如过非核心事件的剧本部分启动，场景序列可能改变；w 思考：剧本与框架系统在知识描述方面的不同的特点？思考：剧本与框架系统在知识描述方面的不同的特点？2.6 2.6 剧本表示法剧本表示法742.7 过程（过程（Procedure）表示）表示w 思考：语义网络、框架、剧本表示法的共同特征？思考：语义网络、框架、剧本表示法的共同特征？知识的静态描述，显示表达，知识的静态描述，显示表达，推理的控制策略，推理效率推理的控制策略，推理效率w 知识的过程表示方法知识的过程表示方法将有关某一问题的领域知识，连同如何应用这些知识，都隐将有关某一问题的领域知识，连同如何应用这些知识，都隐式地表

50、达为一个求解过程。式地表达为一个求解过程。求解效率高求解效率高表示知识的适用范围窄表示知识的适用范围窄扩充新知识难扩充新知识难75w 过程知识表示的例子八数码问题的状态的描述与目标状态2.7 2.7 过程表示法过程表示法76求解方法的图示77782.6 2.6 小结（小结（Summary）w 本章所讨论的本章所讨论的知识表示问题知识表示问题是人工智能研究的核心问是人工智能研究的核心问题之一。题之一。知识表示方法很多，本章介绍了其中的知识表示方法很多，本章介绍了其中的7 7种，种，有有图示法图示法和和公式法公式法，陈述式表示陈述式表示和和过程式表示过程式表示等。等。w 对于同一问题可以有许多不同