搜索
第二节知识表示方法•内容提要：•状态空间法•问题归约法•谓词逻辑法•语义网络法•其他方法前言•在学习本章内容之前，我们先了解一下有关知识及其表示的概念。人类的智能活动过程主要是一个获得并运用知识的过程，知识是智能的基础。为了使计算机具有智能，就必须使它具有知识。那什么是知识呢？知识一般概念•知识是人们在改造客观世界的实践中积累起来的认识和经验•认识：包括对事物现象、本质、属性、状态、关系、联系和运动等的认识•经验：包括解决问题的微观方法：如步骤、操作、规则、过程、技巧等•宏观方法：如战略、战术、计谋、策略等•知识的有代表性的定义•（1）Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换了的信息•（2）Bernstein：知识由特定领域的描述、关系和过程组成•（3）Heyes-Roth：知识=事实+信念+启发式•知识、信息、数据及其关系•数据是信息的载体，本身无确切含义，其关联构成信息•信息是数据的关联，赋予数据特定的含义，仅可理解为描述性知识•知识可以是对信息的关联，也可以是对已有知识的再认识•常用的关联方式：if……then……什么是知识?•一般来说，我们把有关信息关联在一起所形成的信息结构称为知识。知识表示就是对知识的一种描述，一种计算机可以接受的用于描述知识的数据结构。知识反映了客观世界中事物之间的关系。例如，雪是白色的、鸟有翅膀等都是知识知识的要素•知识的要素是指构成知识的必需元素。在这里，我们关心的是一个人工智能系统所处理的知识的组成成分。一般而言，人工智能系统的知识包含事实、规则、控制和元知识。知识的要素•事实：事物的分类、属性、事物间关系、科学事实、客观事实等.是有关问题环境的一些事物的知识，常以“┅是┅”形式出现，也是最低层的知识。例如：雪是白色的，人有四肢。•规则：事物的行动、动作和联系的因果关系知识。这种知识是动态的，常以“如果┅那么┅”形式出现。例如启发式规则，如果下雨，则出门带伞。知识的要素•控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。是有关问题的求解步骤、规划、求解策略等技巧性知识.•元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。是有关知识的知识，是知识库中的高层知识。元知识与控制知识有时有重叠.知识的分类根据知识表达的内容，将其简单地分为如下几类：事实性知识知识的一般直接表示，如果事实性知识是批量的、有规律的，则往往以表格、图册，甚至数据库等形式出现。这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物都是胎生繁殖后代等。过程性知识表述做某件事的过程。标准程序库也是常见的过程性知识，而且是系列化、配套的。如电视机维修法，怎样烹制法国大餐等。行为性知识不直接给出事实本身，只给出它在某方面的行为。行为性知识经常表示为某种数学模型，从某种意义上讲，行为性知识描述的是事物的内涵，而不是外延。如微分方程知识的分类实例性知识只给出一些实例。知识藏在实例中。感兴趣的不是实例本身，而是隐藏在大量实例中的规律性知识。类比性知识既不给出外延，也不给出内涵，只给出它与其它事物的某些相似之处。类比性知识一般不能完整地刻画事物，但它可以启发人们在不同的领域中做到知识的相似性共享。如比喻，心如刀绞，谜语等元知识有关知识的知识。最重要的元知识是如何使用知识的知识。例如，一个好的专家系统应该知道自己能回答什么问题，不能回答什么问题，这就是关于自己知识的知识。元知识是用于如何从知识库中找到想要的知识。•按知识的性质•概念、命题、公理、定理、规则和方法•按知识的作用域•常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的知识。•领域性知识：面向某个具体专业领域的知识。例如：专家经验。•按知识的层次•表层知识：描述客观事物的现象的知识。例如：感性、事实性知识•深层知识：描述客观事物本质、内涵等的知识。例如：理论知识•按知识的确定性•确定性知识：可以说明其真值为真或为假的知识•不确定性知识：包括不精确、模糊、不完备知识•不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假•表示：用可信度、概率等描述•模糊：知识本身的边界就是不清楚的。例如：大，小等•表示：用可能性、隶属度来描述•不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病•每种以知识和符号操作为基础的智能系统，其问题求解方法都需要某种对解答的搜索。•在搜索过程开始之前，必须先用某种方法或某几种方法的混和来表示问题。•问题求解技术主要涉及两个方面：问题的表示求解的方法•知识表示方式是学习人工智能的中心内容之一。知识表示知识表示的概念•什么是知识表示•是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。•知识表示的要求•表示能力：能否正确、有效地表示问题。包括：•表示范围的广泛性•领域知识表示的高效性•对非确定性知识表示的支持程度•可利用性：可利用这些知识进行有效推理。包括：•对推理的适应性：推理是根据已知事实利用知识导出结果的过程•对高效算法的支持程度：知识表示要有较高的处理效率•可实现性：要便于计算机直接对其进行处理•可组织性：可以按某种方式把知识组织成某种知识结构•可维护性：便于对知识的增、删、改等操作•自然性：符合人们的日常习惯•可理解性：知识应易读、易懂、易获取等知识表示的一般方法•状态空间法•问题归约法•谓词逻辑法•语义网络•另外还有框架表示以及剧本表示,过程表示,这里不在一一详述.•在表示和求解比较复杂的问题时,采用单一的表示方法是不够的,往往采用多种方法的混合表示.目前这仍是人工智能专家感兴趣的研究方向.状态空间法问题求解(problemsolving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中.运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。状态空间法•问题求解技术主要涉及两个方面：问题的表示求解的方法•状态空间法状态（State）算符（Operator)状态空间方法（MethodonStateSpace)状态•状态（state）：描述某类不同事物间的差别而引入的一组最少变量q0q1，…，qn的有序集合.矢量形式：矢量形式：Q=[q0,q1,…qn]T式中每个元素qi为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=[q０k,,q1k,…,qnk]•算符（operator）：把问题从一种状态变换为另一种状态的手段.•算符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。算符•状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。•它包含三种说明的集合,即三元状态（S，F，G）•S—初始状态集合；•F—操作符集合；•G—目标状态集合。•对一个问题的状态描述，必须确定3件事：•(1)该状态描述方式，特别是初始状态描述；•(2)操作符集合及其对状态描述的作用；•(3)目标状态描述的特性状态空间表示•典型的例子:•下棋、迷宫及各种游戏。三数码难题•问题描述:•三数码难题:有3个编有1-3并放在2X2方格棋盘上可走动的棋子组成.棋盘上总有一个空格,以便让空格周围的棋子走进来.直至从初始状态到达目标状态.三数码难题八数码难题初始棋局目标棋局表示•制定操作算符集：•*直观方法——为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需32个操作算子。•*简易方法——仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。•*空格移动的唯一约束是不能移出棋盘。•根据问题状态、操作算符和目标条件选择各种表示，是高效率求解必须的。在问题求解过程中，会不断取得经验，获得一些简化的表示。从初始棋局开始，试探由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。八数码难题部分状态图十五数码难题(思考)119415131275861321014123456789101112131415初始状态目标状态状态空间的图示形式称为状态空间图。•有向图(directedgraph)•图:由节点（不一定是有限的节点）的集合构成。•有向图:是指图中的一对节点用弧线连接起来，从一个节点指向另一个节点。•路径•某个节点序列（ni1,ni2,,…,nik）当j=2,3,…k时，如果对于每一个nij-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点，ni1至至节点nik的长度为k的路径。状态图示法•寻找从一种状态变换为另一种状态的某个算符序列问题就等价于寻求图的某一路径的问题.•代价:加在各弧线的指定数值，以表示加在相应算符上的代价。•两个节点间路径的代价等于连接该路径上各节点的所有弧线的代价之和.•图的显示说明:指各节点及其具有代价的弧线可以由一张表明确给出,(可以列出每一个节点,其后继节点以及连接弧线上的代价)•图的隐示说明指各节点及其具有代价的弧线不可以由一张表明确给出.(起始节点后继节点算符已知,把后继算符应用于各节点，以扩展节点）状态图示法状态空间表示举例问题描述在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?•用一个四元表列（W，x，Y，z）来表示问题状态.•其中：W-猴子的水平位置；x－当猴子在箱子顶上时取x=1；否则取x=0；Y－箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。解题过程操作（算符）：•该初始状态变换为目标状态的操作序列为：•{goto(b),pushbox(c),climbbox,grasp}U=b=c状态空间表示举例•产生式系统（ProductionSystem）•一个总数据库(globaldatabase)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。•一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样。•一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。产生式系统•例:推销员旅行问题•从城市A出发,访问每个城市一次且仅一次,返回城市A.•总数库:到目前为止访问过的城市表.•规则:从一个城市达到另一个城市,规则的要求是必须是合法的数据库.(任一城市出现不能多余一次,只到所有城市出现后,才能出现A)•任一个以A为起点的和终点的总数据库都满足终止条件.•这种图搜索控制策略将在第三章讨论.推销员旅行问题•例2.1推销员旅行问题（旅行商问题）•一个推销员计划出访推销产品。他从一个城市（如A）出发，访问每个城市一次，且最多一次，然后返回城市A。要求寻找最短路线。推销员旅行问题•状态描述：目前为止访问过的城市列表（A…）•初始状态：（A）•目标状态：（A……A）39推销员旅行问题图2.4推销员旅行问题状态空间图•算符：下一步走向的城市(a)(b)(c)(d)(e)•约束：每个城市只能走过一次，A除外作业•（p54）2-3利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。问题归