《人工智能课件之知识表示方法33592.pptx》由会员分享，可在线阅读，更多相关《人工智能课件之知识表示方法33592.pptx（228页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二节 知识表示方法 内容提要：状态空间法 问题归约法 谓词逻辑法 语义网络法 其他方法前言 在学习本章内容之前，我们先了解一下有关知识及其表示的概念。人类的智能活动过程主要是一个获得并运用知识的过程，知识是智能的基础。为了使计算机具有智能，就必须使它具有知识。那什么是知识呢？知识一般概念 知识是人们在改造客观世界的实践中积累起来的认识和经验 认识：包括对事物现象、本质、属性、状态、关系、联系和运动等的认识 经验：包括解决问题的微观方法：如步骤、操作、规则、过程、技巧等 宏观方法：如战略、战术、计谋、策略等 知识的有代表性的定义（1）Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换
2、了的信息（2）Bernstein：知识由特定领域的描述、关系和过程组成（3）Heyes-Roth：知识=事实+信念+启发式 知识、信息、数据及其关系 数据是信息的载体，本身无确切含义，其关联构成信息 信息是数据的关联，赋予数据特定的含义，仅可理解为描述性知识 知识可以是对信息的关联，也可以是对已有知识的再认识 常用的关联方式：if then 什么是知识?一般来说，我们把一般来说，我们把有关信息关联在一起所形成有关信息关联在一起所形成的信息结构称为知识。知识表示就是对知识的的信息结构称为知识。知识表示就是对知识的一种描述，一种计算机可以接受的用于描述知一种描述，一种计算机可以接受的用于描述知识的
3、数据结构识的数据结构。知识反映了客观世界中事物之知识反映了客观世界中事物之间的关系。间的关系。例如，例如，雪是白色的、鸟有翅膀等都是知识知识的要素 知识的要素是指构成知识的必需元素。在这里，我们关心的是一个人工智能系统所处理的知识的组成成分。一般而言，人工智能系统的知识包含事实、规则、控制和元知识。知识的要素 事实：事物的分类、属性、事物间关系、科学事实、客观事实等.是有关问题环境的一些事物的知识，常以“是”形式出现，也是最低层的知识。例如：雪是白色的，人有四肢。规则：事物的行动、动作和联系的因果关系知识。这种知识是动态的，常以“如果那么”形式出现。例如启发式规则，如果下雨，则出门带伞。知识的
4、要素 控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。是有关问题的求解步骤、规划、求解策略等技巧性知识.元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。是有关知识的知识，是知识库中的高层知识。元知识与控制知识有时有重叠.知识的分类根据知识表达的内容，将其简单地分为如下几类：事实性知识知识的一般直接表示，如果事实性知识是批量的、有规律的，则往往以表格、图册，甚至数据库等形式出现。这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物都是胎生繁殖后代等。过程性知识表述做某件事的过程。标准程序库也是常见的过程性知识，而且是系列化、配套的。如电视机维修法，怎样烹制法国大餐
5、等。行为性知识不直接给出事实本身，只给出它在某方面的行为。行为性知识经常表示为某种数学模型，从某种意义上讲，行为性知识描述的是事物的内涵，而不是外延。如微分方程知识的分类实例性知识只给出一些实例。知识藏在实例中。感兴趣的不是实例本身，而是隐藏在大量实例中的规律性知识。类比性知识既不给出外延，也不给出内涵，只给出它与其它事物的某些相似之处。类比性知识一般不能完整地刻画事物，但它可以启发人们在不同的领域中做到知识的相似性共享。如比喻，心如刀绞，谜语等元知识有关知识的知识。最重要的元知识是如何使用知识的知识。例如，一个好的专家系统应该知道自己能回答什么问题，不能回答什么问题，这就是关于自己知识的知识
6、。元知识是用于如何从知识库中找到想要的知识。按知识的性质 概念、命题、公理、定理、规则和方法 按知识的作用域 常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的知识。领域性知识：面向某个具体专业领域的知识。例如：专家经验。按知识的层次 表层知识：描述客观事物的现象的知识。例如：感性、事实性知识 深层知识：描述客观事物本质、内涵等的知识。例如：理论知识 按知识的确定性 确定性知识：可以说明其真值为真或为假的知识 不确定性知识：包括不精确、模糊、不完备知识 不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假 表示：用可信度、概率等描述 模糊：知识本身的边界就是不清楚的。例如：大，小
7、等 表示：用可能性、隶属度来描述 不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病 每种以知识和符号操作为基础的智能系统，其问题求解方法都需要某种对解答的搜索。在搜索过程开始之前，必须先用某种方法或某几种方法的混和来表示问题。问题求解技术主要涉及两个方面：问题的表示 求解的方法 知识表示方式是学习人工智能的中心内容之一。知识表示知识表示的概念 什么是知识表示 是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。知识表示的要求 表示能力：能否正确、有效地表示问题。包括：表示范围的广泛性 领域知识表示的高效性 对非确定性知识表示的支持程度 可利用性：可利
8、用这些知识进行有效推理。包括：对推理的适应性：推理是根据已知事实利用知识导出结果的过程 对高效算法的支持程度：知识表示要有较高的处理效率 可实现性：要便于计算机直接对其进行处理 可组织性：可以按某种方式把知识组织成某种知识结构 可维护性：便于对知识的增、删、改等操作 自然性：符合人们的日常习惯 可理解性：知识应易读、易懂、易获取等 知识表示的一般方法 状态空间法 问题归约法 谓词逻辑法 语义网络 另外还有框架表示以及剧本表示,过程表示,这里不在一一详述.在表示和求解比较复杂的问题时,采用单一的表示方法是不够的,往往采用多种方法的混合表示.目前这仍是人工智能专家感兴趣的研究方向.状态空间法问题求
9、解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中.运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。状态空间法 问题求解技术主要涉及两个方面：问题的表示 求解的方法 状态空间法 状态（State）算符（Operator)状态空间方法（Method on State Space)状态 状态（state）：描
10、述某类不同事物间的差别而引入的一组最少变量 q0 q1，qn的有序集合.矢量形式：矢量形式：Q=q0,q1,qnT 式中每个元素qi为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如 Qk=qk,q1k,qnk 算符（operator）：把问题从一种状态变换为另一种状态的手段.算符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。算符 状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。它包含三种说明的集合,即三元状态（S，F，G）S 初始状态集合；F 操作符集合；G 目标状态集合。对一个问题的状态描述，必须确定3件事：(1)该状
11、态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性状态空间表示 典型的例子:下棋、迷宫及各种游戏。三数码难题 问题描述:三数码难题:有3个编有1-3并放在2X2方格棋盘上可走动的棋子组成.棋盘上总有一个空格,以便让空格周围的棋子走进来.直至从初始状态到达目标状态.三数码难题八数码难题 初始棋局 目标棋局表示 制定操作算符集：*直观方法为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需32个操作算子。*简易方法仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。*空格移动的唯一约束是不能移出棋盘。根据问题状态、操作算符和目标条件选择各种
12、表示，是高效率求解必须的。在问题求解过程中，会不断取得经验，获得一些简化的表示。从初始棋局开始，试探由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。八数码难题部分状态图十五数码难题(思考)初始状态目标状态状态空间的图示形式称为状态空间图。有向图(directed graph)图:由节点（不一定
13、是有限的节点）的集合构成。有向图:是指图中的一对节点用弧线连接起来，从一个 节点指向另一个节点。路径 某个节点序列（ni1,ni2,nik）当j=2,3,k时，如果 对于每一个nij-1都有一个后继节点nij存在，那么就把这 个节点序列叫做从节点，ni1至至节点nik的长度为k的路 径。状态图示法 寻找从一种状态变换为另一种状态的某个算符序列问题就等价于寻求图的某一路径的问题.代价:加在各弧线的指定数值，以表示加在相应算符上的代价。两个节点间路径的代价等于连接该路径上各节点的所有弧线的代价之和.图的显示说明:指各节点及其具有代价的弧线可以由一张表明确给出,(可以列出每一个节点,其后继节点以及连
14、接弧线上的代价)图的隐示说明 指各节点及其具有代价的弧线不可以由一张表明确给出.(起始节点后继节点算符已知,把后继算符应用于各节点，以扩展节点）状态图示法状态空间表示举例问题描述在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?用一个四元表列（W，x，Y，z）来表示问题状态.其中：W-猴子的水平位置；x当猴子在箱子顶上时取x=1；否则取x=0；Y箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。解题过程操作（算符）：该初始状态变换为目标状态的操作序列为：goto(b),pushbox
15、(c),climbbox,grasp U=b=c状态空间表示举例 产生式系统（ProductionSystem）一个总数据库(global database)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。产生式系统 例:推销员旅行问题
16、从城市A出发,访问每个城市一次且仅一次,返回城市A.总数库:到目前为止访问过的城市表.规则:从一个城市达到另一个城市,规则的要求是必须是合法的数据库.(任一城市出现不能多余一次,只到所有城市出现后,才能出现A)任一个以A为起点的和终点的总数据库都满足终止条件.这种图搜索控制策略将在第三章讨论.推销员旅行问题 例2.1 推销员旅行问题（旅行商问题）一个推销员计划出访推销产品。他从一个城市（如A）出发，访问每个城市一次，且最多一次，然后返回城市A。要求寻找最短路线。推销员旅行问题 状态描述：目前为止访问过的城市列表（A）初始状态：（A）目标状态：（AA）39推销员旅行问题 图2.4 推销员旅行问题
17、状态空间图 算符：下一步走向的城市(a)(b)(c)(d)(e)约束：每个城市只能走过一次，A除外作业（p54）2-3 利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。问题归约法 已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的
18、实质。问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。问题规约法图解梵塔难题 有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。梵塔难题(a)初始状态(b)目标状态分析 原始问题归约（简化）为三个子问题1、移动A，B盘至柱子2的双圆盘难题2、移动
19、圆盘C至柱子3的单圆盘问题3、移动A，B盘至柱子3的双圆盘难题分析 可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题（111）(122)，(122)(322)以及(322)(333)规定了最后解答路径将要通过的脚踏石状态(122)和(322)。具体解题过程与或图 一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。与或图表示例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示(左图)同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示(右图)与或图表示与或图的一
20、些术语 如果某条弧线从节点a指向节点b，那么节点a叫做节点b的父辈节点；节点b叫做节点a的后继节点或后裔；或节点，只要解决某个问题就可解决其父辈问题的节点集合；与节点，只有解决所有子问题，才能解决其父辈问题的节点集合；弧线，是父辈节点指向子节点的圆弧连线；终叶节点，是对应于原问题的本原节点.举例58与或图构成规则(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A 指向后继节点表示所求得的子问题集合。(4)一般对于代
21、表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子 问题的集合才能获得解答，所以这些子问题节点叫做与节点。(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去。59 59 59 59作业 P54 2-5 试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。谓词逻辑法知识补充-命题逻辑 命题逻辑 逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位
22、。数理逻辑中最基本、最简单的部分。命题逻辑 什么是命题？命题是陈述客观外界发生事情的陈述句。命题是或为真或为假的陈述句。特征：陈述句 真假必居其一,且只居其一.命题逻辑 例1 下列句子是命题吗？8小于10.8大于10.任一个5的偶数可表示成两个素数的和.答：是命题逻辑 例2 下列句子是命题吗？8大于10吗?请勿吸烟.X大于Y.我正在撒谎.悖论 答：不是命题逻辑 命题的抽象 以p、q、r等表示命题。以1表示真，0表示假。则命题就抽象为：取值为0或1的p等符号。若p取值1，则表示p为真命题；若p取值0，则表示p为假命题；命题逻辑“复杂命题”例3:由简单命题能构造更加复杂命题(1)期中考试,张三没有
23、考及格.(2)期中考试,张三和李四都考及格了.(3)期中考试,张三和李四中有人考90分.(4)如果张三能考90分,那么李四也能考90分.(5)张三能考90分当且仅当李四也能考90分.命题逻辑 联结词和复合命题 上述诸如“没有”、“如果 那么”等连词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题称为简单命题。复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。命题逻辑 否定联结词 定义1：设p为一个命题,复合命题“非p”称为p的否定式，记为p，“”称为否定联结词.“p”为真当且仅当p为假。例3中,若p代表“期中
24、考试张三考及格了”，则(1)“期中考试,张三没有考及格.”可表示为p.命题逻辑 合取联结词 定义2 设p、q为两个命题，复合命题“p而且q”称为p、q的合取式，记为p q，“”称作合取联结词。p q真当且仅当p与q同时真.例3的(2)“期中考试,张三和李四都考及格了.”可记为p q,其中p代表“张三考及格”,q代表“李四考及格”.命题逻辑 析取联结词 定义3设p、q为两个命题，复合命题“p或者q”称为p、q的析取式，记为p q，“”称作析取联结词。p q为真当且仅当p与q中至少有一个为真.例3的(3)“期中考试,张三和李四中有人考90分.”可记为p q,其中p代表“张三考90分”,q代表“李四
25、考90分”。命题逻辑“相容或”与“相异或”日常语言中“或”有两种标准用法,例如:(1)张三或者李四考了90分.(2)第一节课上数学课或者上英语课.差异在于：当构成它们的简单命题都真时，前者为真，后者却为假。前者称为“相容或”，后者称为“相异或”。前者(“相容或”)可表示为p q，后者却不能。注意：不能见了或就表示为p q。命题逻辑 蕴涵联结词 定义4设p、q为命题,复合命题“如果p,则q”称为p对q的蕴涵式，记作pq,其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“”称为蕴涵联结词。“p q”假当且仅当p真而q假.pq这样的真值规定有其合理性，也有人为因素。在自然语言中，”如果.“与”“那
26、末.”之间常常是有因果联系的否则就没有意义，但对命题P-Q来说，只要P,Q能够分别确定真值，P-Q即成为命题。此外，自然语言中对“如果.，则.”这样的语句，当前提为假时，结论不管真假，整个 语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T.如果雪是黑的，那末太阳从西方出在自然语言中，”如果.“与”“那末.”之间常常是有因果联系的否则就没有意义，但对命题P-Q来说，只要P,Q能够分别确定真值，P-Q即成为命题。此外，自然语言中对“如果.，则.”这样的语句，当前提为假时，结论不管真假，整个 语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前
27、提为F时，条件命题的真值都取为T.如果雪是黑的，那么太阳从西方出命题逻辑 等价联结词 定义5设p、q为命题,复合命题“p当且仅当q”称作p、q的等价式,记作pq,“”称作等价联结词。pq真当且仅当p、q同时为真或同时为假.命题逻辑 注意 上述五个联结词来源于日常使用的相应词汇,但并不完全一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解,而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“”。有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间的真假值的关系,而不讨论命题的内容.命题逻辑 命题符号化 例4 将下列命
28、题符号化:(1)铁和氧化合,但铁和氮不化合.(2)如果我下班早,就去商店看看,除非我很累.(3)李四是计算机系的学生,他住在312室或313室.命题逻辑 解（1）铁和氧化合,但铁和氮不化合.p(q)，其中:p代表“铁和氧化合”，q代表“铁和氮化合”。（2）如果我下班早,就去商店看看,除非我很累.(P)q)r，其中:p代表“我很累”,q代表“我下班早”,r代表“我去商店看看”命题逻辑（3）李四是计算机系的学生,他住在312室或313室.p(q r)(q r)，其中：p代表“李四是计算机系学生”,q代表“李四住312室”,r代表“李四住313室”.还可表示为：p(q(r)(q)r)命题逻辑命题公式及其解释原子公式：单个命题变元、单个命题常元称为原子公式。命题公式：由如下规则生成的公式称为命题公式：1.单个原子公式是命题公式。2.若A,B是命题公式，则A,A B,A B,A B,A B是公式。3.所有命题公式都是有限次应用1、2得到的符号串。