《人工智能蔡自兴第二章知识表示方法》由会员分享,可在线阅读,更多相关《人工智能蔡自兴第二章知识表示方法(39页珍藏版)》请在金锄头文库上搜索。
1、第二章 知识表示方法,2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法 2.4 语义网络法 2.5 其他方法 2.6 小结,2,2.1状态空间法 (State Space Representation),问题求解技术主要是两个方面: 问题的表示 求解的方法 状态空间法 状态(state) 算符(operator) 状态空间方法,3,2.1.1 问题状态描述,定义 状态:描述某类不同事物间的差别而引入的一组最少变量q0,q1,qn的有序集合。 算符:使问题从一种状态变化为另一种状态的手段称为操作符或算符。 问题的状态空间:是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,
2、即三元状态(S,F,G)。,2.1 状态空间法,4,2. 状态空间表示概念详释,例如下棋、迷宫及各种游戏。,Middle State,Goal State,2.1 状态空间法,5,例:三数码难题 (3 puzzle problem),初始棋局,目标棋局,2.1 状态空间法,6,有向图 路径 代价 图的显示说明 图的隐示说明,2.1.2 状态图示法,A,B,2.1 状态空间法,7,2.1.3 状态空间表示举例,产生式系统(production system) 一个总数据库:它含有与具体任务有关的信息随着应用情况的不同,这些数据库可能简单,或许复杂。 一套规则:它对数据库进行操作运算。每条规则由左
3、部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。 一个控制策略:它确定应该采用哪一条适用规则,而且当数据库的终止条件满足时,就停止计算。,2.1 状态空间法,8,状态空间表示举例,例:猴子和香蕉问题,2.1 状态空间法,9,解题过程,用一个四元表列(W,x,Y,z)来表示这个问题状态.,这个问题的操作(算符)如下: 2 goto(U)表示猴子走到水平位置U 或者用产生式规则表示为 (W,0,Y,z) goto(U) (U,0,Y,z),2.1 状态空间法,10,pushbox(V)猴子把箱子推到水平位置V,即有 (W,0,W,z) pushbox(V) (V,0,V,z),cl
4、imbbox猴子爬上箱顶,即有 (W,0,W,z) climbbox (W,1,W,z),2.1 状态空间法,11,grasp猴子摘到香蕉,即有 (c,1,c,0) grasp (c,1,c,1),该初始状态变换为目标状态的操作序列为 goto(b),pushbox(c),climbbox,grasp,2.1 状态空间法,12,2.1 状态空间法,13,猴子和香蕉问题自动演示:,2.1 状态空间法,14,2.2 问题归约法 (Problem Reduction Representation),15,问题归约表示的组成部分: 一个初始问题描述; 一套把问题变换为子问题的操作符; 一套本原问题描述
5、。,问题归约的实质: 从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题归约为一个平凡的本原问题集合。,2.2 问题规约法,16,2.2.1 问题归约描述 (Problem Reduction Description),梵塔难题,2.2 问题规约法,17,解题过程(3个圆盘问题),2.2 问题规约法,18,多圆盘梵塔难题演示,2.2 问题规约法,19,2.2.2与或图表示,1.与图、或图、与或图,2.2 问题规约法,20,2.2 问题规约法,21,2.一些关于与或图的术语,2.2 问题规约法,22,3.定义,2.2 问题规约法,23,不可解节点的一般定义 没有
6、后裔的非终叶节点为不可解节点。 全部后裔为不可解的非终叶节点且含有或后继节点,此非终叶节点才是不可解的。 后裔至少有一个为不可解的非终叶节点且含有与后继节点,此非终叶节点才是不可解的。 与或图构成规则,2.2 问题规约法,24,梵塔问题归约图,(322) (333),2.2 问题规约法,25,2.3 谓词逻辑法,逻辑语句 形式语言,2.3.1 谓词演算 1. 语法和语义 基本符号 谓词符号、变量符号、函数符号、 常量符号、括号和逗号 原子公式,26,连词和量词(Connective &Quantifiers) 连词 与及合取(conjunction) 或及析取(disjunction) 蕴涵(
7、Implication) 非(Not) 量词 全称量词(Universal Quantifiers) 存在量词 (Existential Quantifiers),2.3 谓词逻辑法,27,2.3.2 谓词公式 原子公式的的定义: 用P(x1,x2,xn)表示一个n元谓词公式,其中P为n元谓词,x1,x2,,xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式,或原子谓词公式。 分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式,并把它叫做分子谓词公式。,2.3 谓词逻辑法,28,合适公式(WFF,well-formed formulas) 合适公式的递归定义 合适公式
8、的性质 合适公式的真值 等价(Equivalence),2.3 谓词逻辑法,29,2.3.3 置换与合一,置换 概念 假元推理 全称化推理 综合推理 定义 就是在该表达式中用置换项置换变量 性质 可结合的 不可交换的,2.3 谓词逻辑法,30,合一(Unification) 合一:寻找项对变量的置换,以使两表达式一致。 可合一:如果一个置换s作用于表达式集Ei的每个元素,则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。,2.3 谓词逻辑法,31,2.4 语义网络法 (Semantic Network Representation),语义网络的结构 定义 组成部分 词法 结构 过
9、程 语义,32,表示占有关系和其它情况 例: 小燕是一只燕子,燕子是鸟;巢-1是小燕的巢,巢-1是巢中的一个。,选择语义基元 试图用一组基元来表示知识,以便简化表示,并可用简单的知识来表示更复杂的知识。,2.4 语义网络法,2.4. 1 二元语义网络的表示,33,2.4.2 多元语义网络的表示,谓词逻辑与语义网络等效,2.4 语义网络法,34,多元语义网络表示的实质 把多元关系转化为一组二元关系的组合,或二元关系的合取。,2.4 语义网络法,35,2.4.3 连接词和量化的表示,合取 三元变为二元组合 析取 加注析取界限,并标记DIS,以免引起混淆。 否定 两种表示方式:或标注NEG界限。,2
10、.4 语义网络法,36,蕴涵 在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。 量化 存在量化ISA链 全称量化分割法,2.4 语义网络法,37,2.5其他方法(Others),框架(Frame)表示 框架是一种结构化表示法,通常采用语义网络中的节点-槽-值表示结构。 剧本(Script)表示 剧本是框架的一种特殊形式,它用一组槽来描述某些事件的发生序列。 过程(Procedure)表示 过程式表示就是将有关某一问题领域的知识,连同如何使用这些知识的方法,均隐式地表达为一个求解问题的过程。,38,2.6 小结(Summary),本章所讨论的知识表示问题是人工智能研究的核心问题之一。知识表示方法很多,本章介绍了其中的7种,有图示法和公式法,陈述式表示和过程式表示等。,39,