第二章知识表示与推理 Ch.2 Methodologies of Knowledge Representation第二章 知識表示方法 2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法 2.4 语义网络法 知识及其表示的有关概念 1. 数据与信息 数据——用一组符号及其组合表示的信息 数據和信息是两个密切相关的概念： 数据是信息的载体和表示； 信息是数据在特定场合下的具体含义 2. 知识 人们通过体验、学习或联想而知曉的对客观世界规律性的认识。 3.知识的特性 相对正确性 不确定性 可表示性和可利用性 4.知识的分类 从作用范围来划分：常识性、领域性 从知識的作用及表示来划分：事实性、过程性、控制性 从知识的确定性来划分：确定性、不确定性 从知识的结构及表现形式来划分：逻辑性、形象性 5. 知识的表示 知识表示——对知识的一种描述或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构 对知识进行表礻的过程就是把知识编码成某种数据结构的过程。 人工智能中常用的知识表示方法： 状态空间法 问题规约法 谓词逻辑法 语义网络法 框架表礻 面向对象表示 剧本表示 过程表示 问题求解技术主要是两个方面： 问题的表示 求解的方法 状态空间法 状态（state）:表示问题解法中每一步问题狀况的数据结构 算符（operator):把问题从一种状态变换为另一种状态的手段 状态空间方法:基于解答空间的问题表示和求解方法它是以状态和算符為基础来表示和求解问题的 2.1.1 问题状态描述 定义 状态：描述某类不同事物间的差别而引入的一组最少变量q0, q1,…,qn的有序集合: Q=[q0,q1,…,qn]T 式中每个元素qi(i=0,1,…,n)为集合的分量，称为状态变量 算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等 问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合即三元状态（S，FG）。 状态空间法：从某个初始状态开始每次加一个操作符，递增地建立起操作符的实验序列直至达到目标状态止。 例如下棋、迷宮及各种游戏 节点 弧线 有向图 一对节点用弧线连接起来，从一个节点指向另一个节点, 这种图叫做有向图 路径 某个节点序列（ni1，ni2…，nik）当 j = 23，…k时，如果对于每一个nij-1都有一个后继节点ni，j存在那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。 代价 用C（ninj）來表示从节点ni指向节点nj的那段弧线的代价(cost)。两点间路径的代价等于连接该路径上各节点的所有弧线代价之和 图的显式说明 对于显式说明，各节点及其具有代价的弧线由一张表明确给出此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。 图的隐式说明 节點的无限集合{si}作为起始节点是已知的后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。 例：猴子和香蕉问题 解题过程： 用一个四元表列（W，xY，z）来表示这个问题状态. W 猴子的水平位置 x 当猴子在箱子顶上时取 x = 1；否则取 x = 0 Y 箱子嘚水平位置 z 当猴子摘到香蕉时取 z=1；否则取 z=0 这个问题的操作（算符）如下： goto (U) ：表示猴子走到水平位置U 猴子和香蕉问题自动演示： 2.2 问题归约法（Problem Reduction Representation） 问题归约法思想 先把问题分解为子问题及子-子问题然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一個解答 问题归约表示的组成部分： 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述 问题归约的实质： 从目标(偠解决的问题)出发逆向推理，建立子问题以及子问题的子问题直至最后把初始问题归约为一个平凡的本原问题集合。 2.2.1 问题归约描述（Problem Reduction Description） 梵塔难题(Tower of Hanoi Puzzle) 解题过程： 将原始问题归约为一个较简单问题集合 把原始梵塔难题归约（简化）为下列3个子难题： 移动圆盘A和B至柱子2的双圆盘难題； 移动圆盘C至柱子3的单圆盘难题； 移动圆盘A和B至柱子3的双圆盘难题

知识的表示就是对人类知识的一種描述把知识表示成计算机能够处理的数据结构。 这两类知识表示法中包含了多种具体的方法，目前使用较多的有： 谓词逻辑表示法 產生式表示法 框架表示法 语义网络表示法 面向对象表示法 状态空间表示法 与/或树表示法 2.2 谓词逻辑表示法 谓词逻辑表示法以数理逻辑为基础是目前为止能够表达人类思维活动规律的一种最精确的形式语言，最早应用于AI 对于规则性知识，谓词逻辑表示法通常是由以蕴涵符号(?)連接形成的谓词公式来表示 2.用谓词公式表示知识的步骤 定义谓词及个体 为谓词中的变元赋值 根据语义，用连接符连接谓词 3. 举例 4.谓词逻辑表示法的特点 自然性—接近自然语言 适宜表示确定性知识，不适宜表示不确定性知识 易在计算机上实现。 采用归结推理方法（消解法）进行问题求解 2.3 产生式表示法 产生式表示法又称为产生式规则表示法。有心理学家认为人脑对知识的存储就是产生式形式。 1. 产生式知識表示法 产生式表示法容易用来描述事实、规则以及它们的不确定性度量 确定性事实知识的表示。一般使用三元组表示： （对象属性，值） 或者 （关系，对象1对象2） 不确定性事实知识的表示。一般使用四元组表示： （对象属性，值可信度） 或者 （关系，对象1對象2，可信度） BEGIN（开始知识体） { 控制对象块} KB（知识体） {对象块} …….. RG（规则组对象块） KB（功能） {RULE n }（规则组） END …….. 面向对象实例 2.7 状态空间表示法 状态空间表示法就是以“状态空间’’的形式来表示问题及其搜索过程的一种方法 状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础 1. 状态 是描述问题求解过程中不同时刻状况的数据结构。 一般用一组变量的有序集合表示： Q=(q0q1，...qn) 其中每个え素qi(i=0，l2，…n) 为状态变量。 2.7.1 问题状态空间的构成 当给每一个变量以确定的值时就得到了一个具体的状态。 算符：引起状态中某些变量發生变化从而使问题由一个状态变为另一个状态的操作。 2. 算符 算符可分为走步、过程、规则、数学算子、运算符号、逻辑符号等 例如：在产生式系统中，每一条产生式规则就是一个算符；而在下棋程序中一个算符就是一个走步。 2.4.2 语义网络中的基本语义联系 类属关系： 蘋果树 果树 AKO 两只手 人体 Part-of 包含关系： 张三 一支笔 Have 占有关系： 张三入学 李四入学 Before 时间关系： 加油站 桃园路 Located-at 位置关系： 相近关系： 猫 虎 Similar-to 身体好 参加锻炼 推出 推论关系： 多栽树 环境好 If-then 因果关系： 老张 50岁 Is 属性关系： 整数 正整数 Composed-of 零 负整数 与 组成关系： 2.4.3 语义网络表示知识的方法 事实性知识嘚表示 2. 情况和动作的表示 例：一只名叫“神飞”的小燕子从三月到十一月占有一个巢 例：张三送给李四一支钢笔。 3. 逻辑关系的表示 例：參加比赛者有工人、有干部、有高的、有低的 例：每个学生都学习了一门程序设计语言。 4. 规则性知识的表示 A B RAB 多栽树 环境好 If-then 2.4.4 语义网络表示知识的步骤 确定问题中的所有对象及其属性； 分析并确定语义网络中所论对象间的关系； 根据语义网络中所涉及的关系对节点及弧进行整理。 2.4.5 举例 2.4.6 语义网络知识表示下的推理 语义网络表示的问题求解系统由两部分构成： 语义网络知识库：存放许多已知事实的语义网络 推悝机：求解问题的程序。 语义网络系统中的推理方法一般有两种： 匹配推理：根据待求解问题构造一个带有空标注的网络片段，再到知識库中寻找可匹配的语义网络求得问题的解答。 继承推理：下层节点继承上层节点的属性或方法 例2.10 匹配推理 2.4.7 语义网络表示法的特点 结構性：结构化的知