知识表示方法ppt课件.pptVIP

ArtificialIntelligence AI Email 第二章 知识表示方法 预备知识 人类的智能活动过程主要是一个获得并运用知识的过程按照符号主义的观点 知识是一切智能行为的基础 要使计算机具有智能 首先必须使它拥有知识首先需要明确一下几个问题什么是知识知识的划分人工智能系统中的知识什么是知识表示 知识表示方法 知识的概念 知识的一般概念 知识是人们在改造客观世界的实践中积累起来的认识和经验认识 包括对事物现象 本质 属性 状态 联系等的认识经验 包括解决问题的微观方法和宏观方法微观方法 如步骤 操作 规则 过程 技巧等宏观方法 如战略 战术 计谋 策略等eg if大雁向南飞 then冬天就要来临了 这样一条知识就是人们经过长期的观察 将 大雁向南飞 与 冬天来临 这两条信息关联在一起 雪是白色的 反映雪与颜色的一种关系 知识的概念 知识 信息 数据及其关系数据 是信息的载体 本身无确切含义 如 水的温度是100 木头的长度是2米 大楼的高度是100层 信息 是数据的关联 赋予数据特定的含义 仅可理解为描述性知识 数据是没有联系的 孤立的 只有当数据用来描述一个客观事物和客观事物的关系 形成有逻辑的数据流 他们才能被称为信息 知识 可以是对信息的关联 也可以是对已有知识的再认识 如 西安7月1日气温为30度 12月1日气温为3度 当对这类信息进行归纳和对比就会发现西安每年7月气温比较高 12月气温比较低 于是有价值的信息沉淀并结构化后就形成了知识 知识的划分 知识的划分按知识的性质 概念 命题 公理 定理 规则和方法按知识的作用域 常识性知识 领域性知识按知识的等级 零级知识 事实性知识 用于描述事物的概念 定义 属性等 或用于描述问题的状态 环境 条件等 一级知识 过程性知识 用于问题求解过程的操作 演算和行为的知识 表示方式 产生式 谓词 语义网络等 二级知识 控制性知识 元知识或超知识 是关于如何使用过程性知识的知识 例如 推理策略 搜索策略 不确定性的传播策略 知识的划分 按知识的层次 表层知识 描述客观事物的现象的知识 例如 感性 事实性知识深层知识 描述客观事物本质 内涵等的知识 例如 理论知识按知识的确定性 确定性知识 可以说明其真值为真或为假的知识不确定性知识 包括不精确 模糊 不完备知识不精确 知识本身有真假 但由于认识水平限制却不能肯定知识的真假 表示 用可信度 概率等描述模糊 知识本身的边界就是不清楚的 例如 大 小等 表示 用可能性 隶属度来描述不完备 解决问题时不具备解决该问题的全部知识 例如 医生看病 知识的划分 按人类的思维及认识方法 逻辑性知识 是反映人类逻辑思维过程的知识 一般具有因果关系或难以精确描述的特点 是人类的经验性知识和直观感觉 如 人的为人处事的经验与风格形象性知识 通过事物的形象建立起来的知识 如 什么是人 按知识的获取方式 显性知识 指可通过文字 语言 图形 声音等形式编码记录和传播的知识 如 教材 音视频光盘 隐性知识 指人们长期实践中积累获得的知识 不易用显性知识表达的知识 如 每个人都有不同的审美观 人工智能系统中的知识 一个智能程序高水平的运行需要有关的事实知识 规则知识 控制知识和元知识 事实知识 是有关问题环境的一些事物的知识 常以 是 的形式出现 如事物的分类 属性 事物间关系 科学事实 客观事实等事实是静态的为人们共享的可公开获得的公认的知识 在知识库中属低层的知识 如 雪是白色的 鸟有翅膀 张三李四是好朋友 这辆车是张三的 规则知识 是有关问题中与事物的行动 动作相联系的因果关系知识 是动态的 常以 如果 那么 形式出现 人工智能系统中的知识 控制知识 是有关问题的求解步骤 技巧的知识 告诉人们怎么做一件事 也包括当有多个动作同时被激活时应选哪一个动作来执行的知识 控制知识常与程序结合在一起出现 如一个问题求解的算法可以看做是一种知识表示 元知识 是有关知识的知识 是知识库中的高层知识 包括怎样使用规则 解释规则 校验规则 解释程序结构等知识 元知识与控制知识是有重迭的 对一个大的程序来说 以元知识或说元规则形式体现控制知识更为方便 因为元知识存于知识库中 而控制知识常与程序结合在一起出现 从而不容易修改 知识表示 知识表示 是研究用机器表示知识的可行性 有效性的一般方法 是一种数据结构与控制结构的统一体 既考虑知识的存储又考虑知识的使用 知识表示的要求 表示能力 能否正确 有效地表示问题 包括 表示范围的广泛性 领域知识表示的高效性 对非确定性知识表示的支持程度 可利用性 可利用这些知识进行有效推理 包括 对推理的适应性 对高效算法的支持程度 可实现性 要便于计算机直接对其进行处理可组织性 可以按某种方式把知识组织成某种知识结构可维护性 便于对知识的增 删 改等操作自然性 符合人们的日常习惯可理解性 知识应易读 易懂 易获取等 内容提要 第二章 知识表示方法 1 状态空间法 2 问题归约法 3 谓词逻辑法 4 语义网络法 5 其他方法 内容提要 第二章 知识表示方法 1 状态空间法 2 问题归约法 3 谓词逻辑法 4 语义网络法 5 其他方法 状态空间法 人工智能虽然有多个研究领域 而且每个研究领域又各有自己的规律和特点 都可抽象为一个 问题求解 的过程 问题求解过程实际上是一个搜索过程 问题求解技术主要是两个方面 问题的表示求解的方法状态空间法 StateSpaceRepresentation 状态空间法就是用来表示问题及其搜索过程的一种方法 它是人工智能中最基本的形式化方法 用 状态 state 和 算符 operator 来表示问题 状态空间法 状态空间法的三要素 1 状态 state 描述某类不同事物间的差别而引入的一组最少变量q0 q1 qn的有序集合 是表示问题解法中每一步问题状况的数据结构 有序集合中每个元素qi i 0 1 n 为集合的分量 称为状态变量 给定每个分量的一组值就得到一个具体的状态 2 算符 operator 使问题从一种状态变化为另一种状态的手段称为操作符或算符 3 状态空间方法 是一个表示该问题全部可能状态及其关系的图 它包含三种说明的集合 即三元状态 S F G S 所有可能的问题初始状态集合 F 操作符集合 G 目标状态集合 状态空间法 状态空间法举例 下棋 迷宫及各种游戏 十五数码难题 15puzzle 由15个编有1至15并放在4 4方格棋盘上的可走动的棋子组成 初始棋局 目标棋局 十五数码难题 初始状态 目标状态 如何把初试棋局变成目标棋局 首先把适用的算符用于初始状态 以产生新的状态 再把另一些适用算符用于这些新的状态 这样继续下去 直至产生目标状态为止 状态空间法 状态图示法 状态空间的图示形式称为状态空间图 状态图中有几个术语 节点 Node 图形上的汇合点 用来表示状态 事件和时间关系的汇合 弧线 Arc 节点间的连接线 表示算符 有向图 DirectedGraph 一对节点用弧线连接起来 从一个节点指向另一个节点 后继节点 Descendantnode 与父辈节点 Parentnode 如果某条弧线从节点ni指向节点nj 那么节点nj就叫做节点ni的后继节点或后裔 而节点ni叫做节点nj的父辈节点或祖先 状态空间法 状态图示法 状态空间的图示形式称为状态空间图 状态图中有几个术语 路径 Path 某个节点序列 ni1 ni2 nik 当j 2 3 k时 如果对于每一个ni j 1都有一个后继节点nij存在 那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径 代价 Cost 用c ni nj 来表示从节点ni指向节点nj的那段弧线的代价 两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和 图的显示说明 隐示说明 指各节点及其具有代价的弧线可以 不可以由一张表明确给出 显然 显示说明对于大型的图是不切实际的 而对于具有无限节点集合的图则是不可能的 状态空间法 问题的表示对求解工作有很大影响 人们希望有较小的状态空间表示 例如 对于十五数码问题 可以规定15 4 60条规则 即 上移棋子1 下移棋子1 左移棋子1 右移棋子1 如果用 上下左右移动空格 则只需4条规则 所以 移动空格是一种较好的表示 状态空间法 状态空间法举例 猴子和香蕉问题 在一个房间内有一只猴子 一个箱子和一束香蕉 香蕉挂在天花板下方 但猴子的高度不足以碰到它 那么这只猴子怎样才能摘到香蕉呢 猴子和香蕉问题 解题过程用一个四元表列 W x Y z 来表示这个问题状态W 猴子的水平位置 x 当猴子在箱子顶上时取1 否则取0 Y 箱子的水平位置 z 当猴子摘到香蕉时取1 否则取0 初始状态为 a 0 b 0 目标状态为 c 1 c 1 这个问题的操作 算符 如下 goto U 表示猴子走到水平位置Upushbox V 猴子把箱子推到水平位置Vclimbbox猴子爬上箱顶grasp猴子摘到香蕉 猴子和香蕉问题 解题过程该初始状态变换为目标状态的操作序列为 Step1 goto b Step2 pushbox c Step3 climbboxStep4 grasp 猴子和香蕉问题 状态空间图 内容提要 第二章 知识表示方法 1 状态空间法 2 问题归约法 3 谓词逻辑法 4 语义网络法 5 其他方法 问题归约法 问题归约 ProblemReduction 是另外一种基于状态空间的问题描述与求解方法已知问题的描述 通过一系列变换把此问题变为一个子问题集合这些子问题的解可以直接得到 本原问题 从而解决了初始问题 问题归约法 问题归约法的组成部分一个初始问题描述 一套把问题变换为子问题的操作符 一套本原问题描述 本原问题 不能再分解或变换且直接可解的子问题 问题归约的实质 从目标 要解决的问题 出发逆向推理 建立子问题以及子问题的子问题 直到最后把初始问题归约为一个本原问题集合 问题归约法 问题归约法举例 汉诺塔问题 Hanoi 从1移到3每次移动一个盘子大盘在下小盘在上 初始状态 111 目标状态 333 汉诺塔问题 原始问题可以归约为下列3个子问题 子问题1 移动圆盘A和B至柱子2 借助柱子3 子问题2 移动圆盘C至柱子3 子问题3 把圆盘A和B移至柱子3 借助柱子1 汉诺塔问题 归约过程 3个圆盘 汉诺塔问题 汉诺塔问题归约图 本原问题 本原问题 与或图 问题归约法 与或图表示 用一个类似于图的结构来表示把问题归约为后继问题的替换集合 与图 把一个复杂问题分解为若干个较为简单的子问题 形成 与 树 或图 利用同构或同态的等价变换 把原问题变换为若干个较为容易求解的新问题 形成 或 树 问题归约法 与或图表示 子问题替代集合结构图 与或图 问题归约法 一些关于与或图的术语 起始节点对应于原始问题描述 终叶节点对应于本原问题 问题归约法 与或图的构成规则1 与或图中的每个节点代表一个要解决的单一问题或问题集合 图中所含起始节点对应于原始问题A 2 对应于本原问题的节点称为终叶节点 它没有后继节点 3 对于把算符应用于问题A的每种可能情况 都把问题变换为一个子问题集合 有向弧线自A指向后继节点表示所求得的子问题集合 问题归约法 与或图的构成规则4 一般对于代表两个或两个以上子问题集合的每个节点 有向弧线从此节点指向次子问题集合中的各个节点 由于只有当集合中所有项都有解时 这个子问题的集合才能获得解答 所以这些子问题节点叫做与节点 5 特殊情况下 当只有一个算符可应用于问题A 而且这个算符产生具有一个以上子问题的某个集合时 由上述规则3 和规则4 所产生的图可以得到简化 简化 问题归约法 与或图的搜索 目的在于表明起始节点是有解的 可解节点终叶节点是可解节点 对应于本原问题 如果某个非终叶节点含有或后继节点 那么只要当其后继节点至少有一个是可解的时 此非终叶节点才是可解的 如果某个非终叶节点含有与后继节点 那么只有当其后继节点全部为可解时 此非终叶节点才是可解的 问题归约法 不可解节点没有后裔的非终叶节点为不可解节点 如果某个非终叶节点含有或后继节点 那么只有当其全部后裔为不可解时 此非终叶节点才是不可解的 如果