人工智能及其应用_知识表示113

第二章知识表示本章主要讨论知识表示问题，介绍7种知识表示方法：状态空间法、问题归约法、谓词演算法、语义网络法、框架表示、本体技术、过程表示。掌握状态空间法、问题归约法、谓词演算法、语义网络法的要点及其之间的关系，了解框架表示、本体技术、过程表示。知识表示的基本概念知识表示：研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。人工智能系统所关心的知识事实有关问题环境的一些事物的知识，常以“…是…”的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等。如雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的。规则有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果…那么…”形式出现。控制有关问题的求解步骤、技巧性知识，告诉怎么做一件事。元知识有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。2.1状态空间法问题求解问题求解(problemsolving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。状态空间法：基于解答空间的问题表示和求解方法，它是以状态和算符(operator)为基础来表示和求解问题的。2.1状态空间法1.问题求解技术两个主要的方面(1)问题的表示：如果描述方法不对，对问题求解会带来很大的困难；(2)求解的方法：采用试探搜索方法。2.状态空间法三要点(1)状态（state）(2)算符（operator）(3)状态空间方法2.1状态空间法2.1.1问题状态描述1.定义状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0,q1,…,qn]T式中每个元素qi(i=0,1,,n)为集合的分量,称为状态变量,给定每个分量的一组值就得到一个具体的状态,如Qk=[q0k,q1k,…,qnk]T式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(statespace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。可把状态空间记为三元状态(S，F，G)。2.1状态空间法2.状态空间表示详释让我们先用数码难题(puzzleproblem)来说明状态空间表示的概念。由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，…等等。2.1状态空间法2.状态空间表示详释状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符的试验序列，直到达到目标状态为止。寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及此后检验这些新的状态描述，看是否达到了该目标状态。对于最优化问题找到任一目标状态是不够的，必须按某个准则实现最优化路径。P26完成目标状态的三件事：１状态描述方式，特别是初始状态描述；２操作符集合及其对状态描述的作用；３目标状态的特性。2.1状态空间法2.1.2状态图示法为了对状态空间图有更深入的了解，这里介绍一下图论中的几个术语和图的正式表示法。1.图论中的几个术语节点(node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合；弧线(arc)：节点间的连接线；有向图(directedgraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点(descendantnode)与父辈节点(parentnode)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。2.1状态空间法2.1.2状态图示法1.图论中的几个术语路径：某个节点序列(ni1,ni2,…,nik)当j=2，3，…，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价：用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。显式表示：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。隐式表示：节点的无限集合{si}作为起始节点是已知的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。2.1状态空间法2.1.2状态图示法2.图的显式和隐式表示一个图可由显式说明也可由隐式说明。显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。此外，引入后继节点算符的概念是方便的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价把后继算符应用于{si}的成员和它们的后继节点以及这些后继节点的后继节点，如此无限制地进行下去，最后使得由Γ和{si}所规定的隐式图变为显示图。问题的表示对求解工作量有很大的影响。人们显然希望有较小的状态空间表示。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。2.1状态空间法2.1.2状态图示法根据问题状态、操作符和目标条件选择各种表示，是高效率问题求解必须的。各种问题都可以用状态空间加以表示，并用状态空间搜索法来求解。2.1状态空间法2.1.2状态图示法1.产生式系统（ProductionSystem）·一个总数据库(globaldatabase)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。·一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。用规则来改变数据库就象用算符来改变状态一样。·一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。推销员旅行问题总数据库：到目前为止所访问的城市；规则对应于决策：即下一步走向城市Ａ，下一步走向城市Ｂ，…，下一步走向城市Ｅ，一条规则必须能把某个数据库变为一个合法数据库，否则不适应这个数据库；任一以Ａ为起点和终点，并出现所有其它城市的总数据库，都满足终止条件．2.1状态空间法2.1.2状态图示法2.状态空间表示举例例2猴子和香蕉问题(monkeyandbananaproblem)在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?图2.4表示出猴子、香蕉和箱子在房间内的相对位置。猴子和香蕉...用一个四元表列(W,X,Y,Z)来表示这个问题的状态，其中W－猴子的水平位置X－当猴子在箱子顶上时取X=1；否则取X=0Y－箱子的水平位置Z－当猴子摘到香蕉时取Z=1；否则取Z=0图2.4猴子和香蕉问题2.1状态空间法2.1.2状态图示法这个问题中的操作(算符)如下：(1)goto(U)猴子走到水平位置U，或者用产生式规则表示为：(W，0，Y，z)(U，0，Y，z)(2.3)即应用操作goto(U)，能把状态(W，0，Y，z)变换为状态(U，0，Y，z)。(2)pushbox(V)猴子把箱子推到水平位置V，即有(W，0，W，z)(V，0，V，z)(2.4)应当注意的是，要应用算符pushbox(V)，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。2.1状态空间法2.1.2状态图示法这个问题中的操作(算符)如下：(3)climbbox猴子爬上箱顶，即有(W，0，W，z)(W，1，W，z)(2.5)在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上。(4)grasp猴子摘到香蕉，即有(c,1,c,0)(c,1,c,1)(2.6)其中，c是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上。2.1状态空间法对于规则(2)，只有当算符pushbox(V)的先决条件，即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时，算符pushbox(V)才是适用的。这一操作算符的作用是猴子把箱子推到位置V。在这一表示中，目标状态的集合可由任何最后元素为1的表列来描述。令初始状态为(a,0,b,0)这时，goto(U)是唯一适用的操作，并导致下一状态(U,0,b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。猴子和香蕉问题的状态空间图2.2问题归约法2.2.1问题归约描述先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2问题归约法2.2.1问题归约描述１梵塔难题有3个柱子(1，2和3)和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图2.6所示。2.2问题归约法解题过程：将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B最好不要移至柱子3，否则就不能把圆盘C移至柱子3。因此，首先应该把圆盘A和B移到柱子2上。然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。将原始难题归约（简化）为下列子难题：移动圆盘A和B至柱子2的双圆盘难题，如图(a)所示。2.2问题归约法图2.7梵塔问题解答(a)图2.8梵塔问题解答(b)图2.9梵塔问题解答(c)2.2问题归约法梵塔问题归约图：子问题2可作为本原问题考虑，因为它的解只包含一步移动。应用一系列相似的推理，子问题1和子问题3也可被归约为本原问题，如图2.10所示。这种图式结构，叫做与或图(AND/ORgraph)。它能有效地说明如何由问题归约法求得问题的解答。梵塔问题归约图2.2问题归约法2.2.1问题归约描述２问题归约描述问题归约方法应用算符把问题描述变换为子问题描述，问题描述可以用多种数据结构形式，包括表列、树、字符串、矢量、数组等。梵塔问题采用包含两个数列的表列来描述,[(113),（333)]表示把配置（113）变换为配置（333）。用状态空间表示的三元组合（S，F，