人工智能第二章

人工智能原理ArtificialIntelligencePrinciple 信息工程学院张永梅 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本 脚本 表示2 9其他方法 第二章知识表示方法 作业 2 1 2 2 2 8 2 9 第二章知识表示方法 实验 实验1 梵塔问题实验 熟悉和掌握问题规约法的原理 实质和规约过程 理解规约图的表示方法 实验2 机器人简单行为实验 掌握谓词逻辑的表达方法 了解机器人 或机械手 的状态 条件 动作或行为等处理流程 实验3 从前有一条河 河的左岸有m个传教士 m个野人和一艘最多可乘n人的小船 约定左岸 右岸和船上或者没有传教士 或者野人数量少于传教士 否则野人会把传教士吃掉 搜索一条可使所有的野人和传教士安全渡到右岸的方案 联系方式 电子邮件 zhangym 联系方式2 1知识表示 KnowledgeRepresentation 概述 按照符号主义的观点 知识是一切智能行为的基础 要使计算机具有智能 首先必须使它拥有知识 知识表示是人工智能研究中最基本的问题之一 在知识处理中总要问到 如何表示知识 知识是用什么来表示的 怎样使机器能懂 能对之进行处理 并能以一种人类能理解的方式将处理结果告诉人们 在AI系统中 给出一个清晰简洁的描述是很困难的 有研究报道认为 严格地说AI对知识表示的认真 系统的研究才刚刚开始 知识的定义 难以给出明确的定义只能从不同侧面加以理解 Feigenbaum 知识是经过消减 塑造 解释和转换的信息 Bernstein 知识是由特定领域的描述 关系和过程成的 Hayes roth 知识是事实 信念和启发式规则 知识库的观点 知识是某领域中所涉及的各有关方面的一种符号表示 知识的类型 按知识的性质概念 命题 公理 定理 规则和方法 按知识的作用域常识性知识 通用通识的知识 人们普遍知道的 适应所有领域的知识 领域性知识 面向某个具体专业领域的知识 例如 专家经验 知识的种类 事实性知识 采用直接表示的形式 如 凡是猴子都有尾巴过程性知识 描述做某件事的过程 如 电视维修法控制性知识 元知识或超知识 是关于如何使用过程性知识的知识 如 推理策略 搜索策略 不确定性的传播策略 按知识的层次表层知识 描述客观事物的现象的知识 例如 感性 事实性知识深层知识 描述客观事物本质 内涵等的知识 例如 理论知识 知识的种类 按知识的等级零级知识 叙述性知识一级知识 过程性知识二级知识 控制性知识 元知识或超知识 按知识的确定性确定性知识 可以说明其真值为真或为假的知识不确定性知识 包括不精确 模糊 不完备知识不精确 知识本身有真假 但由于认识水平限制却不能肯定其真假表示 用可信度 概率等描述 知识的种类 模糊 知识本身的边界就是不清楚的 例如 大 小等表示 用可能性 隶属度来描述不完备 解决问题时不具备解决该问题的全部知识 例如 医生看病 知识的要素 事实 事物的分类 属性 事物间关系 科学事实 客观事实等 最低层的知识 规则 事物的行动 动作和联系的因果关系知识 启发式规则 元知识 当有多个动作同时被激活时 选择哪一个动作来执行的知识 高层知识 知识表示的定义 知识表示研究用机器表示知识的可行性 有效性的一般方法 是一种数据结构与控制结构的统一体 既考虑知识的存储又考虑知识的使用 知识表示可看成是一组描述事物的约定 以把人类知识表示成机器能处理的数据结构 知识表示研究的特点 智能行为特有的灵活性 常识问题 不能概括为一类简洁的理论 是大量小理论的集合 AI的任务受到计算装置的约束 这导致了所采用的 表示 必须同时满足 刻画智能现象 与 计算装置可以接受 这两个有时是矛盾的条件 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本表示2 9其他方法 2 2状态空间法 StateSpaceRepresentation 问题求解技术主要是两个方面 问题的表示求解的方法 状态空间法状态 state 算符 operator 状态空间方法 2 2 1问题状态描述 定义状态 描述某类不同事物间的差别而引入的一组最少变量q0 q1 qn的有序集合 算符 使问题从一种状态变化为另一种状态的手段称为操作符或算符 问题的状态空间 是一个表示该问题全部可能状态及其关系的图 它包含三种说明的集合 即三元状态 S F G 2 2状态空间法 所有可能的问题初始状态集合S 操作符集合F以及目标状态集合G 状态空间表示概念详释 例如下棋 迷宫及各种游戏 MiddleState GoalState 2 2状态空间法 例 三数码难题 3puzzleproblem 初始棋局 目标棋局 2 2状态空间法 2 2状态空间法 实例 十五数码难题 15puzzleproblem 初始状态 目标状态 2 2状态空间法 状态空间法从某个初始状态开始 每次增加一个操作符 递增地建立起操作符的试验序列 直到达到目标状态止 2 2状态空间法 总结完成问题的状态描述要做三件事 1 初始状态的描述 2 操作符集合及其对状态改变的作用 3 目标状态的描述 有向图路径代价图的显示说明图的隐示说明 2 2 2状态图示法 A B 2 2状态空间法 2 2 2状态图示法 2 2状态空间法 图由节点 不一定是有限的节点 的集合构成 一对节点用弧线连接起来 从一个节点指向另一个节点 这种图叫做有向图 directedgraph 某个节点序列 ni1 ni2 nik 当j 2 3 k时 如果对于每一个ni j 1都有一个后继节点nij存在 那么就把这个节点序列叫做从节点ni1至节点nik的长度为k 1的路径 代价 cost 是给各弧线指定数值以表示加在相应算符上的代价 图的显式说明是指各节点及其具有代价的弧线由一张表明确给出 图的隐式说明是指各节点及其具有代价的弧线不能由一张表明确给出 2 2 3状态空间表示举例 产生式系统 productionsystem 一个总数据库 它含有与具体任务有关的信息 随着应用情况的不同 这些数据库可能简单 或许复杂 2 2状态空间法 一套规则 它对数据库进行操作运算 每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作 一个控制策略 它确定应该采用哪一条适用规则 而且当数据库的终止条件满足时 就停止计算 状态空间表示举例 例 猴子和香蕉问题 2 2状态空间法 解题过程 用一个四元表列 W x Y z 来表示这个问题状态 2 2状态空间法 其中 W 猴子的水平位置x 当猴子在箱子顶上时取x 1 否则取x 0Y 箱子的水平位置z 当猴子摘到香蕉时取z 1 否则取z 0 2 2状态空间法 这个问题中的操作 算符 如下 1 goto U 猴子走到水平位置U 表示为goto U W 0 Y z U 0 Y z 即把状态 W 0 Y z 变换为状态 U 0 Y z 2 pushbox V 猴子把箱子推到水平位置V 即有pushbox V W 0 W z V 0 V z 条件 猴子与箱子必须在同一位置上 并且 猴子不是在箱子顶上 2 2状态空间法 3 climbbox猴子爬上箱顶 即有climbbox W 0 W z W 1 W z 条件 猴子和箱子应当在同一位置上 而且猴子不在箱顶上 4 grasp猴子摘到香蕉 即有grasp c 1 c 0 c 1 c 1 条件 猴子和箱子都在位置c上 并且猴子已在箱子顶上 其中 c是香蕉正下方的地板位置 该初始状态变换为目标状态的操作序列为 goto b pushbox c climbbox grasp 状态空间表示举例 例 猴子和香蕉问题 2 2状态空间法 解题过程 用一个四元表列 W x Y z 来表示这个问题状态 2 2状态空间法 其中 W 猴子的水平位置x 当猴子在箱子顶上时取x 1 否则取x 0Y 箱子的水平位置z 当猴子摘到香蕉时取z 1 否则取z 0 猴子与香蕉问题状态空间图 猴子和香蕉问题自动演示 2 2状态空间法 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本表示2 9其他方法 2 3问题归约法 ProblemReductionRepresentation 问题归约表示法的组成部分 一个初始问题描述 一套把问题变换为子问题的操作符 一套本原问题描述 问题归约的实质 从目标 要解决的问题 出发逆向推理 建立子问题以及子问题的子问题 直至最后把初始问题归约为一个平凡的本原问题集合 2 3问题规约法 2 3问题规约法 梵塔问题相传印度教的天神梵天在创造地球这一世界时 建了一座神庙 神庙里竖有三根宝石柱子 柱子由一个铜座支撑 梵天将64个直径大小不一的金盘子 按照从大到小的顺序依次套放在第一根柱子上 形成一座金塔 即所谓的梵塔 又称汉诺塔 天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上 即将整个塔迁移 同时定下3条规则 1 每次只能移动一个盘子 2 盘子只能在三根柱子上来回移动 不能放在他处 3 在移动过程中 三根柱子上的盘子必须始终保持大盘在下 小盘在上 2 3问题规约法 天神说 当这64个盘子全部移到第三根柱子上后 世界末日就要到了 这就是著名的梵塔问题 用计算机求解一个实际问题 首先要从这个实际问题中抽象出一个数学模型 然后设计一个解此数学模型的算法 最后根据算法编写程序 以便调试 编译 连接和运行 从而形成该问题的求解 从实际问题中抽象出一个数学模型的实质 其实就是要用数学的方法抽取其主要的 本质的内容 最终实现对该问题的正确认识 Algorithms Programming 用计算机解决问题的关键任何一项计算 总要事先拟定计算方案和规划计算步骤 为使计算机的计算过程能够解决某一问题 必须为计算机设计执行的解决方案中的每个详细步骤 并且将此过程完整地描述出来 所谓算法是对某个问题求解方案的完整而明确的描述 与算法有关的还有一个大家熟悉的公式 程序 算法十数据结构算法设计和程序设计是不完全相同的 由于数字计算机运算速度很高 是人工手算所不能比拟的 为了充分发挥计算机的这种优点 在用计算机求解问题过程中 应尽量减少人工干预 因此 必须先将所制定的解决方案 告诉 计算机 使计算机按照人们规定的计算顺序去自动执行 用计算机能接受的 语言 来描述解题步骤 即程序设计 它还包含了合适的数据结构 解决计算问题一般步骤 算法设计 算法 为解决某一具体问题制定的 经过严谨定义其运算顺序的一组规则 其中每一个规则都是有效 明确的 且这一顺序将在有限次数下终止 自然语言专用工具流程图 PAD图 N S图算法描述工具Pascal C 算法的描述 PAD图 ProblemAnalysisDiagram 问题分析图 PAD图是日本日立公司提出 是由程序流程图演化来的 用结构化程序设计思想表现程序逻辑结构的图形工具 现在已为ISO认可 PAD图设置了五种基本控制结构的图式 并允许递归使用 2 3 1问题归约描述 ProblemReductionDescription 2 3问题规约法 梵塔难题 a 初始状态 b 目标状态 2 3问题规约法 原始问题归约 简化 为三个子问题 1 移动A B盘至柱子2的双圆盘难题2 移动圆盘C至柱子3的单圆盘问题3 移动A B盘至柱子3的双圆盘难题 2 3问题规约法 归约过程 2 3问题规约法 求解过程 3圆盘难题 2 3问题规约法 2 3问题规约法 这样的问题求解算法可以设计成一个递归结构的算法 如图所示 求解n个圆盘的汉诺塔问题的算法为 1 递归调用n 1个圆盘的汉诺塔问题算法 把上面的n 1个圆盘从A柱移到B柱 2 把最下面的一个圆盘从A柱直接移到C柱 3 递归调用n 1个圆盘的汉诺塔问题算法 把B柱上临时存放的n 1个圆盘移到C柱 2 3问题规约法 2 3问题规约法 2 3问题规约法 2 3问题规约法 梵塔问题是一个典型的只有用递归方法 而不能用其他方法 来解决的问题 递归是计算学科中的一个重要概念 所谓递归 就是将一个较大的问题归约为一个与原问题相同的小问题 根据递归方法 我们可发现将64个盘子的梵塔问题转化为求解63个盘子先移动到第二个柱子上 再将最后一个盘子直接移动到第三个柱子上 最后又一次将63个盘子从第二个柱子移动到第三个柱子上 这样则可以解决64个盘子的梵塔问题 依此类推 63个盘子的梵塔求解问题可以转化为62个盘子的梵塔求解问题 62个盘子的梵塔求解问题又可以转化为61个盘子的梵塔求解问题 直到1个盘子的梵塔求解问题 2 3问题规约法 2 3问题规约法 再由1个盘子的梵塔的求解求出2个盘子的梵塔 直到解出64个盘子的梵塔问题 下面 用C语言对该问题的求解算法进行描述 hanoi intn charleft charmiddle charright if n 1 move 1 one three else hanoi n 1 left right middle move 1 left right hanoi n 1 middle left right 2 3问题规约法 2 3问题规约法 注 n表示n个盘子的梵塔问题 left表示第一个柱子 middle表示第二个柱子 right表示第三个柱子 函数hanoi n 1 left right middle 表示n 1阶梵塔从第一个柱子借助第三个柱子先移到第二个柱子上 函数move 1 left right 表示将第一个柱子上最后一个盘子直接放到第三个柱子上 函数hanoi n 1 middle left right 表示n 1个盘子借助第一个柱子移到第三个柱子上 在以上C语言描述的算法基础上 作适当扩充就可以形成一个完整的程序 经过编译和连接后 计算机就可以执行这个程序 按照递归的方法将问题求解出来 2 3问题规约法 2 3问题规约法 现在的问题目是当n 64时 即有64个盘子时 需要移动多少次盘子 要用多少时间 按照上面的算法 n个盘子的梵塔问题目需要移动的盘子数是n 1个盘子的梵塔问题目需要移动的盘子数的2倍加1 于是 h n 2h n 1 1 2 2h n 2 1 1 22h n 2 2 1 23h n 3 22 2 1 2nh 0 2n 1 22 2 1 2n 1 22 2 1 2n 1 因此 要完成梵塔的搬迁 需要移动盘子的次数为 2n 1 18446744073709551615 2 3问题规约法 2 3问题规约法 如果每秒移动一次 一年有31536000秒 则僧侣们一刻不停地来回搬动 也需要花费5849亿年的时间 假定计算机以每秒1000万个盘子的速度进行搬迁 则需要花费大约58490年的时间 就这个例子 可以了解到理论上可以计算的问题 实际上并不一定能行 这属于算法复杂性方面的研究内容 2 3 2与或图表示 2 3问题规约法 复杂问题很难或没法直接求解 但可以分解成一系列 类型不同 的子问题 而这些子问题又可反复细分成一些更小的子问题 一直到分成一些可普通求解的 相当基本的问题为止 然后由这些分解成的子问题的全部或部分解再导出原问题的解 这种将一个问题分解成若干个子问题 又由子问题的解导出原问题解的方法称为问题化简 问题化简已在工业调度分析 定理证明等方面得到应用 2 3 2与或图表示 与图 或图 与或图 2 3问题规约法 2 3问题规约法 使图中的每个结点含意单一化 2 3问题规约法 父节点 子节点 或节点 与节点 终叶节点 一些关于与或图的术语 2 3问题规约法 定义 可解节点 与或图中一个可解节点的一般定义可以归纳如下 1 终叶节点是可解节点 因为它们与本原问题相关连 2 如果某个非终叶节点含有或后继节点 那么只有当其后继节点至少有一个是可解的时 此非终叶节点才是可解的 3 如果某个非终叶节点含有与后继节点 那么只要当其后继节点全部为可解时 此非终叶节点才是可解的 2 3问题规约法 定义 不可解节点不可解节点的一般定义归纳于下 1 没有后裔的非终叶节点为不可解节点 2 如果某个非终叶节点含有或后继节点 那么只有当其全部后裔为不可解时 此非终叶节点才是不可解的 3 如果某个非终叶节点含有与后继节点 那么只要当其后裔至少有一个为不可解时 此非终叶节点才是不可解的 2 3问题规约法 定义 有解节点 无解节点 终叶节点 2 3问题规约法 对原问题的求解即是对对应的与或图进行搜索 目的在于表明起始节点是有解的 与或图构成规则 每个节点代表一个明显的问题或者问题集合 除了起始节点外 每个节点只有一个父节点 此时 这些图就是与或树 2 3问题规约法 某人一星期天洗一次衣服 所要做的事有 收集脏衣服 洗衣服 把衣服弄干 熨平 叠好并归堆 其中 某些事可采用不同的方法 如洗衣服一项可以是手洗也可以是机器洗 对于这个问题可以构造出下图所示的一棵与 或树 图中手洗的那个结点没有子孙也不是方形结点 它表示此人不采用手洗的方法 当然 洗衣服问题是个非常简单的问题 而实际应用中很多问题远非如此简单 因此使用问题化简就有了现实意义 2 3问题规约法 2 3问题规约法 梵塔问题归约图 与或图 2 3问题规约法 归约过程 2 3问题规约法 求解过程 3圆盘难题 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本表示2 9其他方法 2 4产生式表示法 ProductionSystem 产生式系统1943年 由美国数学家PostPost提出 20世纪60年代 成为认知心理学研究人类心理活动中信息加工过程的基础 专家系统采用产生式系统的结构来建造 采用产生式系统理由 用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象 可以把产生式系统作为人工智能系统的基本结构单元或基本模式看待 到目前为止 产生式系统已发展成为人工智能系统中最典型最普遍的一种结构 2 4产生式表示法 ProductionSystem 又称为产生式规则表示法 它和图灵机有相同的计算能力 目前产生式表示法已成为人工智能中应用最多的一种知识表示方法 产生式知识表示方法 2 4产生式表示法 ProductionSystem 2 4 1产生式的基本形式 产生式通常用于表示具有因果关系的知识 其基本形式是 P Q或IFPTHENQ其中 P是产生式的前提或条件 用于指出该产生式是否是可用的条件 Q是一组结论或动作 用于指出该产生式的前提条件P被满足时 应该得出的结论或应该执行的操作 P和Q都可以是一个或一组数学表达式或自然语言 2 4产生式表示法 ProductionSystem 2 4 2产生式表示知识方法 确定性和不确定性规则知识的产生式表示 确定性规则知识可用前面介绍的产生式的基本形式表示即可 不确定性规则知识用如下形式表示P Q 可信度 或者IFPTHENQ 可信度 其中 P是产生式的前提或条件 用于指出该产生式是否是可用的条件 Q是一组结论或动作 用于指出该产生式的前提条件P被满足时 应该得出的结论或应该执行的操作 2 4产生式表示法 ProductionSystem 2 4 2产生式表示知识方法 产生式规则的例子r6 IF动物有犬齿AND有爪AND眼盯前方THEN该动物是食肉动物其中 r6是该产生式的编号 动物有犬齿AND有爪AND眼盯前方 是产生式的前提P 该动物是食肉动物 是产生式的结论Q 2 4产生式表示法 ProductionSystem 2 4 2产生式表示知识方法 确定性事实性知识一般使用三元组的形式表示如下 对象 属性 值 或 关系 对象1 对象2 不确定性事实性知识一般用四元组的形式表示如下 对象 属性 值 不确定度量值 或 关系 对象1 对象2 不确定度量值 例 老李年龄今年是65岁 Li Age 65 例 老李年龄很可能是40岁 0 8 老李和老张是朋友的可能性不大 0 1 表示为 Li AGE 40 0 8 FRIENDS Li Zhang 0 1 2 4产生式表示法 ProductionSystem 2 4 3产生式系统的组成 产生式系统通常由规则库 数据库和推理机这3个基本部分组成 产生式系统的基本结构 2 4 3产生式系统的组成 产生式系统 用于描述某领域内知识的产生式集合 是某领域知识 规则 的存储器 用来存放输入事实 外部数据库输入的事实以及中间结果和最后结果 由一组程序组成 用来控制协调规则库与数据库的运行 包含了推理方式和控制策略 规则库 数据库 推理机 产生式系统 知识库 推理机知识库 数据库 规则库 2 4 4产生式系统推理方式 产生式系统推理机的推理方式有正向推理 反向推理和双向推理三种 推理过程 从已知事实出发 通过规则求得结论 或称数据驱动方式 也称作自底向上的方式 1 规则集中的规则与数据库中的事实进行匹配 得匹配的规则集合 2 使用冲突解决算法 从匹配规则集合中选择一条规则作为启用规则 3 执行启用规则的后件 将该启用规则的后件送入数据库 重复这个过程直至达到目标 正向推理 2 4 4产生式系统推理方式 反向推理 推理过程 从目标 作为假设 出发 反向使用规则 求得已知事实 这种推理方式也称目标驱动方式 或称自顶向下的方式 1 规则库中的规则后件与目标事实进行匹配 得匹配的规则集合 2 使用冲突解决算法 从匹配规则集合中选择一条规则作为启用规则 3 将启用规则的前件作为子目标 重复这个过程直至各子目标均为已知事实 成功结束 2 4 4产生式系统推理方式 双向推理是一种既自顶向下 又自底向上的推理方式 推理从两个方向同时进行 直至某个中间界面上两方向结果相符便成功结束 这种双向推理较正向或反向推理所形成的推理网络小 从而有更高的推理效率 双向推理 用 If then 的形式表示知识 并模拟人类求解问题的思维过程格式固定 形式单一 规则间相互独立匹配提供的信息只有成功与失败 匹配一般无递归 系统容易建立推理方式单纯 知识库与推理机分离 修改方便 容易理解既可以表示确定性知识 又可以表示不确定知识既利于表示启发性知识 又利于表示过程性知识 2 4 5产生式系统的特点 优点 2 4 5产生式系统的特点 缺点 求解效率低 各规则之间的联系以数据库为媒介 求解过程是一种反复进行的 匹配 冲突消除 执行 的过程不能表示结构性的知识 产生式表示的知识有一定的格式 且规则之间不能直接调用 因此那些具有结构关系或层次关系的知识不易用它表示出来组合爆炸问题 模式匹配最浪费时间 匹配时间与产生式规则数目及工作存储器中元素数目的乘积成正比 产生式规则数目大时 匹配时间可能超过人们的忍耐程度控制饱和问题 很难设计适应各种情况下竞争消除的策略 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本表示2 9其他方法 2 5谓词逻辑法 一阶谓词逻辑表示法 一种重要的知识表示方法 它以数理逻辑为基础 是到目前为止能够表达人类思维和推理的一种最精确的形式语言 它的表现方式和人类自然语言非常接近 它能够被计算机作精确推理 一阶谓词逻辑表示法 2 5谓词逻辑法 一阶谓词逻辑表示法 表示方法 逻辑表示法 一阶谓词逻辑是谓词逻辑中最直观的一种逻辑 它以谓词形式来表示动作的主题 客体 客体可以多个 如 张三与李四打网球 ZhangandLiplaytennis 可写为 play Zhang Li tennis 这里谓词是play 动词主体是Zhang和Li 而客体是tennis 谓词逻辑规范表达式 P x1 x2 x3 这里P是谓词 xi是主体与客体 2 5谓词逻辑法 一阶谓词逻辑表示法 表示方法 逻辑表示法 谓词比命题更加细致地刻画知识 表达能力强如 北京是个城市 City x 把城市这个概念分割出来 把 城市 与 北京 两个概念连接在一起 而且说明 北京 是 城市 的子概念 有层 谓词可以代表变化的情况如 City 北京 真 City 煤球 假在不同的知识之间建立联系 2 5谓词逻辑法 一阶谓词逻辑表示法 表示方法 逻辑表示法 在不同的知识之间建立联系如 Human x Lawed x 人人都受法律管制 x是同一个人 Commit x Punished x x不一定是人 也可以是动物 而 Human x Lawed x commit x Punished x 意为如果由于某个x是人而受法律管制 则这个人犯了罪就一定要受到惩罚 2 5谓词逻辑法 一阶谓词逻辑表示法 表示方法 逻辑表示法 连词和量词 Connective Quantifiers 连词与 合取 conjunction 或 析取 disjunction 蕴涵 Implication 非 Not 量词全称量词 UniversalQuantifiers 存在量词 ExistentialQuantifiers 2 3谓词逻辑法 2 5 1知识的谓词逻辑表示法 用谓词公式既可表示事物的状态 属性和概念等事实性的知识 也可表示事物间具有因果关系的规则性知识 用谓词公式表示知识的一般步骤 2 根据所要表达的事物或概念 为每个谓词中的变元赋以特定的值 1 定义谓词及个体 确定每个谓词及个体的确切含义 3 根据所要表达的知识的语义 用适当的连接符将各个谓词连接起来形成谓词公式 2 5 2谓词逻辑表示知识举例 用谓词逻辑表示下列知识 武汉是一个美丽的城市 但她不是一个沿海城市 如果马亮是男孩 张红是女孩 则马亮比张红长得高 例 第一步 第二步 第三步 定义谓词如下 BCity x x是一个美丽的城市HCity x x是一个沿海城市Boy x x是男孩Girl x x是女孩High x y x比y长得高 根据语义 用逻辑连接符连接BCity wuhan HCity wuhan Boy mal Girl zhangh High mal zhangh 将个体代入谓词中 得到BCity wuhan HCity wuhan Boy mal Girl zhangh High mal zhangh 2 5 3一阶谓词逻辑表示法特点 自然性 谓词是一种接近于自然语言的形式语言 易于理解 精确性 谓词逻辑是二值逻辑 谓词公式的真值只有 真 假 可以表示精确知识 可保证推理得到的结论的精确性 严密性 谓词逻辑具有严格的形式定义及推理规则 容易实现 较易在计算机内部表示 便于对知识的增加 删除和修改 优点 2 5 3一阶谓词逻辑表示法特点 不能表示不确定性的知识 不能表示不精确 模糊性的知识 难以表示启发性知识 局限性 组合爆炸 推理过程中 随着事实和推理规则的增加 加上选择推理规则的盲目性 有可能形成组合爆炸 效率低 推理是基于形式逻辑的 把推理与知识的语义割裂开来 使得推理过程冗长 降低了系统的效率 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本表示2 9其他方法 2 6语义网络法 SemanticNetworkRepresentation 目前 语义网络已经成为人工智能中应用较多的一种知识表示方法 尤其是在自然语言处理方面的应用 语义网络表示法 2 6 1语义网络概念及结构 语义网络 一般由一些最基本的语义单元组成 这些最基本的语义单元被称为语义基元 可用如下三元组来表示为 节点1 弧 节点2 每一个要表达的事实用一个 结点 表示 而事实之间的关系用 弧线 表示 语义基元结构 语义网络结构 2 6 2语义网络基本语义联系 类属关系 类属关系是指具有共同属性的不同事物间的分类关系 成员关系或实例关系 它体现的是 具体与抽象 个体与集体 的层次分类 类属关系实例注 在类属关系中 具体层的结点除了具有抽象层结点的所有属性外 还可以增加一些自己的个性 常用的类属关系有 AKO A Kind of 表示一个事物是另一个事物的一种类型 AMO A Member of 表示一个事物是另一个事物的成员 ISA Is a 表示一个事物是另一个事物的实例 2 6 2语义网络基本语义联系 包含关系也称为聚类关系 是指具有组织或结构特征的 部分与整体 之间的关系 它和类属关系的最主要的区别就是包含关系一般不具备属性的继承性 包含关系 包含关系实例 常用的包含关系的有 Part of 表示一个事物是另一个事物的一部分 或说是部分与整体的关系 用它连接的上下层节点的属性很可能是很不相同的 即Part of联系不具备属性的继承性 2 6 2语义网络基本语义联系 属性关系是指事物和其属性之间的关系 属性关系 例 鸟有翅膀属性关系实例 常用的属性的关系有 Have 表示一个结点具有另一个结点所描述的属性 Can 表示一个结点能做另一个结点的事情 2 6 2语义网络基本语义联系 时间关系是指不同事件在其发生时间方面的先后关系 节点间不具备属性继承性 时间关系 例如 香港回归之后 澳门也回归了 常用的时间关系有 Before 表示一个事件在一个事件之前发生 After 表示一个事件在一个事件之后发生 2 6 2语义网络基本语义联系 位置关系是指不同事物在位置方面的关系 节点间不具备属性继承性 位置关系 常用的位置关系有 Located on 表示一物体在另一物体之上 Located at 表示一物体在某一位置 Located under 表示一物体在另一物体之下 Located inside 表示一物体在另一物体之中 Located outside 表示一物体在另一物体之外 2 6 2语义网络基本语义联系 相近关系是指不同事物在形状 内容等方面相似和接近 相近关系 常用的相近关系有 Similar to 表示一事物与另一事物相似 Near to 表示一事物与另一事物接近 2 6 2语义网络基本语义联系 因果关系是指由于某一事件的发生而导致另一事物的发生 适合表示规则性知识 因果关系 通常用If then联系表示两个节点之间的因果关系 其含义是 如果 那么 2 6 2语义网络基本语义联系 组成关系是一种一对多的联系 用于表示某一事物由其它一些事物构成 通常用Composed of联系表示 组成关系 Composed of联系所连接的节点间不具备属性继承性 2 6 2语义网络基本语义联系 多元逻辑关系例如AC米兰队和国际米兰队在一场足球比赛中的成绩为0 1 逻辑表示法为SCORE AC MILAN INTER MILAN 0 1 可以通过加入附加结点的办法将其改成语义网络表示法 其根本方法是将多元关系表示成二元关系的组合或合取 本例通过加入附加结点G22 多元逻辑关系语义网络实例 从图中可以看出 原来的多元关系都变成了G22结点属性 2 6 2语义网络基本语义联系 例 MichealisanemployeeandJackishisboss SomedayMichealkickedhisboss 语义描述 2 6 2语义网络基本语义联系 用语义网络表示下列命题 1 猪和羊都是动物 2 猪和羊都是哺乳动物 3 野猪是猪 但生长在森林中 4 山羊是羊 头上长着角 5 绵羊是一种羊 它能生产羊毛 例 分析 对象有猪 羊 动物 哺乳动物 野猪 山羊 绵羊 森林 羊毛 角等 语义关系 动物 和 哺乳动物 哺乳动物 和 猪 哺乳动物 和 羊 羊 和 山羊 及 绵羊 野猪 和 猪 之间的关系是 是一种 的关系 可用AKO来表示 山羊 和 头上有角 之间是一种属性关系 可用HAVE来描述 绵羊 和 羊毛 之间是一种属性关系 可用HAVE来描述 野猪 和 森林 之间是位置关系 可用Locate at来表示 2 6 2语义网络基本语义联系 语义网络 AKO AKO HAVE HAVE Locate at 山羊 动物 羊 猪 绵羊 野猪 哺乳动物 头上有角 羊毛 森林 AKO AKO AKO AKO 猪和羊的语义网络 2 6 2语义网络基本语义联系 上面是从关系角度考察语义网络的表达力的 下面从语句角度来考察语义网络 例如 对于如下的语句 或事件 小王送给小李一本书 用语义网络可表示为图1 其中S代表整个语句 这种表示被称为是自然语言语句的深层结构表示 语义网络也能表示用谓词逻辑表示的形式语言语句 例如 x student x read x 三国演义 即 某个学生读过 三国演义 其语义网络表示为图2 2 6 2语义网络基本语义联系 图1语句 事件 的语义网络 小王送给小李一本书 2 6 2语义网络基本语义联系 图2谓词公式的语义网络 谓词逻辑表示的形式语言语句 例如 x student x read x 三国演义 即 某个学生读过 三国演义 2 6 2语义网络基本语义联系 推理方法网络匹配 结构上的匹配 包括结点和弧的匹配 继承推理 利用如 成员联系 因果联系 蕴含联系等具有继承性质的语义联系建立一些并不一定显示存在于网络知识库中的网络结构 语义网络上的推理 网络上的搜索过程 正向 逆向 双向 2 6 2语义网络基本语义联系 继承的一般规则 IFX AKO YandY AKO ZthenX AKO ZIFX ISA YandY AKO ZthenX ISA ZIFX AKO YandY 属性 ZthenX 属性 ZIFX ISA YandY 属性 ZthenX 属性 ZIFX 属性 YandY AKO ZthenX 属性 ZIFX 属性 YandY ISA ZthenX 属性 Z 2 6 2语义网络基本语义联系 类属关系 类属关系是指具有共同属性的不同事物间的分类关系 成员关系或实例关系 它体现的是 具体与抽象 个体与集体 的层次分类 常用的类属关系有 AKO A Kind of 表示一个事物是另一个事物的一种类型 AMO A Member of 表示一个事物是另一个事物的成员 ISA Is a 表示一个事物是另一个事物的实例 2 6 3语义网络的特点 语义网络图的好处是直观 清晰 缺点是表达范围有限 如 一旦有多个结点 而且各结点之间又有联系 则这个网络就很难辨请了 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本表示2 9其他方法 2 7框架表示法 框架表示法是以框架理论为基础发展起来的一种结构化的知识表示 它适用于表达多种类型的知识 框架理论的基本观点是 人脑已存储有大量的典型情景 当面临新的情景时 就从记忆中选择一个称作框架的基本知识结构 其具体内容依新的情景而改变 形成对新情景的认识又记忆于人脑中 框架表示法 2 7 1框架的构成 一般结构 人类对于一件事的了解 表现在对于这件事物的诸方面 即属性的了解 掌握了事物的属性 也就有了关于事物的知识 知识表示是从属性描述开始的 框架 框架是一种描述所论对象 一个事物 一个事件 一个概念 属性的数据结构 框架的结构 一个框架是由若干槽组成 每个槽又可以有若干个侧面 槽用来描述所论对象的某方面的属性 侧面用来描述相应属性的一个方面 槽和侧面所具有的属性值分别称为槽值和侧面值 2 7 1框架的构成 一般结构 框架网络 框架中的槽值或侧面值可以是另一个框架的名字 这就在框架之间建立了联系 构成了框架网络 通过框架网络可以找到另一个框架 继承性是框架表示法的一个重要特征 它不仅可以在两层框架之间实现继承关系 而且可以通过两两的继承关系 从最底层追溯到最高层 使最高层的信息逐层向底层传递 2 7 1框架的构成 一般结构 其一般形式是 框架名槽名1槽值1 侧面名11侧面值111 侧面值112 侧面名12侧面值121 侧面值122 槽名2槽值2 侧面名21侧面值211 侧面值212 侧面名22侧面值221 侧面值222 槽名k槽值k 侧面名k1侧面值k11 侧面值k12 侧面名k2侧面值k21 侧面值k22 即一个框架一般有若干个槽 一个槽有一个槽值或者有若干个侧面 而一个侧面又有若干个侧面值 其中槽值和侧面值可以是数值 字符串 布尔值 也可以是一个动作或过程 甚至还可以是另一个框架的名字 表示对象间关系的常用槽名 用于指出部分和全体的关系 用Part of槽指出的联系所描述的下层框架和上层框架之间不具有继承性 用来表示AKO槽的逆关系 用Instance槽指出的联系都具有继承性 即下层框架可继承上层框架中所描述的属性或值 用于指出对象间抽象概念上的类属关系 直观意义是 是一个 是一种 是一只 等 一般用ISA槽指出的联系都具有继承性 用于具体地指出对象间的类属关系 其直观意义是 是一种 ISA槽 Instance槽 AKO槽 Part of槽 槽名 2 7 1框架的构成 2 7 2框架表示知识举例 教师 的框架 框架名 类属 工作 范围 教学 科研 缺省 教学性别 男 女 学历 中专 大学 类别 例 分析 框架名 教师 含有5个槽 槽名分别为 类属 工作 性别 学历 和 类别 槽名后面是其槽值 槽值 又是一个框架名 范围 缺省 是槽 工作 的两个不同的侧面 其后是侧面值 另外 用括的槽值也是框架名 name 计算机主机super class 计算机sub class 微机 小型机 大型机品牌 联想厂商 北京联想集团公司CPU 品牌 型号 主板 品牌 型号 内存 硬盘 例 frame 计算机主机 2 7 3框架系统的推理 基于框架的推理方法是继承 所谓继承 就是子框架可以拥有其父框架的槽及其槽值 实现继承的操作有匹配 搜索和填槽 匹配就是问题框架同知识库中的框架的模式匹配 所谓问题框架 就是要求解某个问题时 先把问题用一个框架表示出来 然后与知识库中的已有框架进行匹配 如果匹配成功 就可获得有关信息 搜索就是沿着框架间的纵向和横向联系 在框架网络中进行查找 搜索的目的是为了获得有关信息 2 7 4框架表示法的特点 继承性 结构化 自然性 推理灵活多变 A B C D 框架表示法的主要不足之处在于它不善于表达过程性知识 因此它经常与产生式表示法结合起来使用 以取得互补效果 用 If then 的形式表示知识 并模拟人类求解问题的思维过程格式固定 形式单一 规则间相互独立匹配提供的信息只有成功与失败 匹配一般无递归 系统容易建立推理方式单纯 知识库与推理机分离 修改方便 容易理解既可以表示确定性知识 又可以表示不确定知识既利于表示启发性知识 又利于表示过程性知识 2 4 5产生式系统的特点 优点 2 4 5产生式系统的特点 缺点 求解效率低 各规则之间的联系以数据库为媒介 求解过程是一种反复进行的 匹配 冲突消除 执行 的过程不能表示结构性的知识 产生式表示的知识有一定的格式 且规则之间不能直接调用 因此那些具有结构关系或层次关系的知识不易用它表示出来组合爆炸问题 模式匹配最浪费时间 匹配时间与产生式规则数目及工作存储器中元素数目的乘积成正比 产生式规则数目大时 匹配时间可能超过人们的忍耐程度控制饱和问题 很难设计适应各种情况下竞争消除的策略 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本 脚本 表示2 9其他方法 剧本表示法 剧本的知识表示方法与框架类似 由一组槽组成 用来表示特定领域内一些事件的发生序列 剧本方式是采用一个专用的框架 用来表示特定领域的知识 剧本通过一些元语作为槽名来代表要表示的对象的基本行为 有些象电影剧本 开场条件1 病人有病 2 病人的病需要找医生诊治 3 病人有钱 4 病人能够去医院 角色病人 医生 护士 道具医院 挂号室 椅子 桌子 药方 药房 钱 药 场景场景1进入医院 1 病人走进医院 2 病人挂号 3 病人在椅子上坐下等待看病场景2看病 1 病人进入医生的办公室 2 病人向医生介绍病状 3 医生向病人解释病情 4 医生给病人开药方场景3交费 1 病人到交费处 2 病人递交药方 3 病人交钱 4 病人取回药方及收据场景4取药 1 病人到药房 2 病人递交药方 3 病人取药场景5离开 1 病人离开医院 结果1 病人看病了 明白了自己的病是怎么回事 2 病人花了钱 买了药 3 医生付出了劳动 4 医院的药品少了 剧本表示法 推理 剧本表示的知识有强烈的因果结构 系统对事件的处理必须是一个动作完成后才能完成另一个 整个过程的启动取决于开场条件 满足剧本的开场条件 剧本中的事件才有可能发生 而剧本的结果就是动作完成后的系统结果 由于剧本是以非常固定的形式描述的 在预言一些没有直接提到的事件方面特别有用 如已知某一剧本适用于所给定的情形 一旦剧本被起用 则可以应用它按照事件发生的顺序推理 如果事件被强行中断 也就是给定的情节中的某个时间与剧本中的事件不能对应时 则剧本便不能预测被中断以后的事件 如 上例中 如果医生说病人没病 病人就回家了 那么 对于病人所发生的变化 医院的药所发生的变化都不能作出推断 与框架相比 剧本要呆板得多 知识表达的范围也很窄 但对于表达事先构思好的特定知识 如理解故事情节等是非常有效的 第二章知识表示方法 2 1知识表示概述2 2状态空间法2 3问题归约法2 4产生式表示法2 5谓词逻辑法2 6语义网络法2 7框架表示2 8剧本 脚本 表示2 9其他方法 上述的知识表示虽各有特点 而且适用的领域也不同 如 谓词逻辑方法只适用于确定性 陈述性 静态性知识 而对动态的 变化性 模糊性知识则很难表示 产生式规则方法推理方法太单一 如果前提条件太多 或规则条数太多 则推理的速度将慢得惊人 语义网络方法表达的知识面比较窄 框架方法表示的知识横向关系不太明确 纵向从属继承关系很明确 对于复杂的 深层次的知识 就很难用一种知识表示来解决问题 2 9 1混合型知识表示法 根据需要表示的知识的特征来决定用二 三种方式联合表示 2 9 1混合型知识表示法 逻辑与框架 框架里的槽值可以对应于谓词项 语义网络与框架 结点与框架对应 结点的参数就是框架的槽值 产生式与框架 框架的槽值对应于一条产生式规则 与神经网络结合 框架与产生式在产生式系统中 随着产生式规则数量的增加 系统设计者难以理解规则之间的相互作用 因此 需要对规则适当划分 将其组织成易于管理的功能模块 框架系统具有组织成块知识的良好特性 两者的有机结合 有利于系统的开发 调试和管理 2 9 1混合型知识表示法 框架的表示机制可以用作产生式语言和推理机制设计的一个重要构件 框架可以直接用于表示规则 2 9 1混合型知识表示法 需要指出的是 产生式规则也可用框架表示 例如 产生式如果头痛且发烧 则患感冒 用框架表示可为 框架名 前提 条件1 头痛条件2 发烧结论 患感冒 2 9 2面向对象表示法 几年来 在智能系统的设计和构造中 人们开始使用面向对象的的思想 方法和开发技术 并在知识表示 知识库的组成与管理 专家系统设计等方面取得了快速的进展 面向对象表示法 面向对象的基本概念 对象 类 封装 广义地讲 对象 指客观世界中的任何事物 它既可以是一个具体的简单事物 也可以是由多个简单事物组合而成的复杂事物 从问题求解的角度