知识表示方法PPT.ppt

第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结 CSUCSUCSUCSUCSUCSUCSUCSUCSU知识的定义 Feigenbaum知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息Bernstein知识是由特定领域的描述、关系和过程组成的 Hayes-Roth知识是事实、信念和启发式规则。从知识库的观点看，知识是某领域中所涉及的各有关方面的一种符号表示。2CSUCSUCSUCSUCSUCSUCSUCSUCSU知识要素3 事实事实 规则规则有关问题环境的一些事物的知识，常以有关问题环境的一些事物的知识，常以“是是”的形式出的形式出现。现。有关问题中与事物的行动、动作相联系的因果关系知识，有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以是动态的，常以“如果如果那么那么”形式出现。形式出现。控制控制有关问题的求解步骤、技巧性知识，告诉怎么做一件事。有关问题的求解步骤、技巧性知识，告诉怎么做一件事。元知识元知识有关知识的知识，是知识库中的高层知识。包括怎样使用有关知识的知识，是知识库中的高层知识。包括怎样使用规则，解释规则、校验规则、解释程序结构等知识。规则，解释规则、校验规则、解释程序结构等知识。CSUCSUCSUCSUCSUCSUCSUCSUCSU知识的表示4知识表示的分类知识表示的分类陈述性知识表示：将知识表示与知识的运用分开处理，在陈述性知识表示：将知识表示与知识的运用分开处理，在表示知识时，并不涉及如何运用知识的问题，是一种静态的表示知识时，并不涉及如何运用知识的问题，是一种静态的描述方法。描述方法。过程性知识表示：将知识表示与知识的运用相结合，知识过程性知识表示：将知识表示与知识的运用相结合，知识寓于程序中，是一种动态的描述方法。寓于程序中，是一种动态的描述方法。知识表示的定义知识表示的定义可看成是一组事物的约定，以把人类知识表示成机器能处理可看成是一组事物的约定，以把人类知识表示成机器能处理的数据结构。对知识进行表示的过程就是把知识编码成某种的数据结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。数据结构的过程。CSUCSUCSUCSUCSUCSUCSUCSUCSU选取知识表示的因素5l表示知识的范围是否广表示知识的范围是否广泛泛l是否适于推理是否适于推理l是否适于计算机处理是否适于计算机处理l是否有高效的求解算法是否有高效的求解算法l能否表示不精确知识能否表示不精确知识l能否在同一层次上和不同层能否在同一层次上和不同层次上模块化次上模块化l知识和元知识能否用统一的知识和元知识能否用统一的形式表示形式表示l是否适合于加入启发信息是否适合于加入启发信息l过程性表示还是说明性表示过程性表示还是说明性表示l表示方法是否自然表示方法是否自然CSUCSUCSUCSUCSUCSUCSUCSUCSU62.1状态空间法（State Space Representation）v问题求解技术主要是两个方面：v问题的表示v求解的方法v状态空间法v状态（state）v算符（operator）v状态空间方法CSUCSUCSUCSUCSUCSUCSUCSUCSU72.1.1 问题状态描述v定义v状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。v算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。v问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。vS:所有可能的初始状态集合。F:操作符集合。G:目标状态集合。2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU82.状态空间表示概念详释v例如下棋、迷宫及各种游戏。OriginalState2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU9状态空间问题求解状态空间法状态空间法:从初始状态开始从初始状态开始,每次加一个操作符每次加一个操作符,递增地建立起操递增地建立起操作符的试验序列作符的试验序列,直到达到目标状态为止直到达到目标状态为止.基本过程基本过程:1.1.为问题选择适当的为问题选择适当的”状态状态”及及”操作符操作符”的形式化描述方的形式化描述方法法,定义初始状态集合定义初始状态集合,目标状态集合及操作符集合目标状态集合及操作符集合;2.2.将操作符作用在初始状态将操作符作用在初始状态(新状态新状态)上生成新状态逐步构造上生成新状态逐步构造状态空间状态空间,判断新状态是否为目标状态判断新状态是否为目标状态,如果是转如果是转3.3.否则否则转转2.2.3.3.寻找从初始状态到目标状态的一个寻找从初始状态到目标状态的一个(最佳最佳)路径。路径边上路径。路径边上所使用的操作符序列就是该问题的一个解所使用的操作符序列就是该问题的一个解.CSUCSUCSUCSUCSUCSUCSUCSUCSU10例:三数码难题（3 puzzle problem）初始棋局目标棋局2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU11v有向图v路径v代价v图的显示说明v图的隐示说明2.1.2 状态图示法AB2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU状态空间图状态空间图 把初始状态可达到的各状态所组成的空间用有向图把初始状态可达到的各状态所组成的空间用有向图表示。用表示。用”状态状态”标识节点标识节点,用用”操作操作”标识有向边标识有向边,有向边方向由被施加操作的有向边方向由被施加操作的对象状态指向操作的结果状态。对象状态指向操作的结果状态。12CSUCSUCSUCSUCSUCSUCSUCSUCSU132.1.3 状态空间表示举例v产生式系统（production system）v一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。v一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。v一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU14 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU15解题过程v 用一个四元表列（W，x，Y，z）来表示这个问题状态.v这个问题的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU16vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）vclimbbox猴子爬上箱顶，即有（W，0，W，z）climbbox （W，1，W，z）2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU17vgrasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）v该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU18目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU19猴子和香蕉问题自动演示：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU状态空间表示举例v传教士和野人问题v状态表示：(在河的左岸的传教士人数、野人人数和船的情况)v初始状态:（3，3，1）v结束状态:（0，0，0v中间状态则:（2，2，0）、（3，2，1）、（3，0，0）20CSUCSUCSUCSUCSUCSUCSUCSUCSU状态空间表示举例v状态表示：(在河的左岸的传教士人数、野人人数和船的情况)v初始状态:（3，3，1）v结束状态:（0，0，0v中间状态则:（2，2，0）、（3，2，1）v每个三元组对应了三维空间上的一个点v问题的解，则是一个合法状态的序列：(初始状态，结束状态)v中间状态：介于初始状态和结束状态之间v除了初始状态外，该序列中任何一个状态，都可以通过一条规则，由与他相邻的前一个状态转换得到21CSUCSUCSUCSUCSUCSUCSUCSUCSU222.2 问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题CSUCSUCSUCSUCSUCSUCSUCSUCSU23v 问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：v从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU242.2.1 问题归约描述（Problem Reduction Description）v梵塔难题123CBA2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU25解题过程（3个圆盘问题）1231231231231231231231232.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU26多圆盘梵塔难题演示2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU272.2.2与或图表示v1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图CSUCSUCSUCSUCSUCSUCSUCSUCSU282.2 问题规约法BCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSU292.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点CSUCSUCSUCSUCSUCSUCSUCSUCSU303.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点CSUCSUCSUCSUCSUCSUCSUCSUCSU31v不可解节点的一般定义v没有后裔的非终叶节点为不可解节点。v全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。v后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。v与或图构成规则2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU32梵塔问题归约图（113113）（123123）（111111）（113113）（123123）（122122）（111111）（333333）（122122）（322322）（111111）（122122）（322322）（333333）（321321）（331331）（322322）（321321）（331331）（333333）2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU332.3 谓词逻辑法v逻辑语句v形式语言2.3.1 谓词演算v 1.语法和语义v基本符号v谓词符号、变量符号、函数符号、常量符号、括号和逗号v原子公式CSUCSUCSUCSUCSUCSUCSUCSUCSU34v连词和量词(Connective&Quantifiers)v连词v与及合取（conjunction)v或及析取（disjunction）v蕴涵（Implication）v非（Not）v量词v全称量词（Universal Quantifiers)v存在量词(Existential Quantifiers)2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU一阶谓词逻辑v一阶谓词逻辑表示法，是一阶谓词逻辑表示法，是一种重要的知识表示一种重要的知识表示方法，它以数理逻辑为基础，是到目前为止能方法，它以数理逻辑为基础，是到目前为止能够表达人类思维和推理的一种最精确的形式语够表达人类思维和推理的一种最精确的形式语言。它的表现方式和人类自然语言非常接近，言。它的表现方式和人类自然语言非常接近，它能够被计算机作精确推理。它能够被计算机作精确推理。35CSUCSUCSUCSUCSUCSUCSUCSUCSU一阶谓词逻辑v用谓词公式既可表示事物的状态、属性和概念等事实性的知识，也可表示事物间具有因果关系的规则性知识。36CSUCSUCSUCSUCSUCSUCSUCSUCSU用谓词公式表示知识的一般步骤用谓词公式表示知识的一般步骤1.定义谓词及个体，确定每个谓词及个体的确切定义谓词及个体，确定每个谓词及个体的确切含义。含义。2.根据所要表达的事物或概念，为每个谓词中的根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。变元赋以特定的值。3.根据所要表达的知识的语义，用适当的连接符根据所要表达的知识的语义，用适当的连接符将各个谓词连接起来形成谓词公式。将各个谓词连接起来形成谓词公式。37CSUCSUCSUCSUCSUCSUCSUCSUCSU谓词逻辑表示知识举例1v用谓词逻辑表示下列知识：v武汉是一个美丽的城市，但她不是一个沿海城市。1.定义谓词如下：BCity(x)：x是一个美丽的城市 HCity(x)：x是一个沿海城市2.将个体代入谓词中，得到：BCity(wuhan),HCity(wuhan)3.根据语义，用逻辑连接符连接vBCity(wuhan)HCity(wuhan)38CSUCSUCSUCSUCSUCSUCSUCSUCSU谓词逻辑表示知识举例2v用谓词逻辑表示下列知识：v如果马亮是男孩，张红是女孩，则马亮比张红长得高。1.定义谓词如下：Boy(x):x是男孩 Girl(x):x是女孩 High(x,y):x比y长得高2.将个体代入谓词中，得到:Boy(mal),Girl(zhangh),High(mal,zhangh)3.根据语义，用逻辑连接符连接(Boy(mal)Girl(zhangh)High(mal,zhangh)39CSUCSUCSUCSUCSUCSUCSUCSUCSU402.3.2 谓词公式v原子公式的的定义：v用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。v分子谓词公式v可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU41v合适公式（WFF，well-formed formulas）v合适公式的递归定义v合适公式的性质v合适公式的真值v等价（Equivalence)2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU422.3.3 置换与合一v置换v概念v假元推理v全称化推理v综合推理v定义v就是在该表达式中用置换项置换变量v性质v可结合的v不可交换的2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU43v合一（Unification)v合一：寻找项对变量的置换，以使两表达式一致。v可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU442.6 小结（Summary）v本章所讨论的知识表示问题是人工智能研究的核心问题之一。知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，陈述式表示和过程式表示等。CSUCSUCSUCSUCSUCSUCSUCSUCSU45方法 初始问题算符目标结果 状态 空间法 归约法 谓词逻辑法 语义网络法状态状态结点结点合适公式合适公式结点结点算符算符弧弧 子句集子句集（set of clause）置换合一置换合一消解反演消解反演链链目标状态目标状态结点结点根结点根结点目标网络目标网络解答路径解答路径 （path）解答树解答树 （tree）nil语义网络语义网络知识表示方法间的关系知识表示方法间的关系