知识表示方法.ppt

第二章知识表示方法,2.1状态空间法2.2问题归约法2.3谓词逻辑法2.4语义网络法2.5其他方法2.6小结,知识的定义,Feigenbaum知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息Bernstein知识是由特定领域的描述、关系和过程组成的Hayes-Roth知识是事实、信念和启发式规则。从知识库的观点看，知识是某领域中所涉及的各有关方面的一种符号表示。,2,知识要素,3,事实,规则,有关问题环境的一些事物的知识，常以“是”的形式出现。,有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果那么”形式出现。,控制,有关问题的求解步骤、技巧性知识，告诉怎么做一件事。,元知识,有关知识的知识，是知识库中的高层知识。包括怎样使用规则，解释规则、校验规则、解释程序结构等知识。,知识的表示,4,知识表示的分类,陈述性知识表示：将知识表示与知识的运用分开处理，在表示知识时，并不涉及如何运用知识的问题，是一种静态的描述方法。过程性知识表示：将知识表示与知识的运用相结合，知识寓于程序中，是一种动态的描述方法。,知识表示的定义,可看成是一组事物的约定，以把人类知识表示成机器能处理的数据结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。,选取知识表示的因素,5,表示知识的范围是否广泛是否适于推理是否适于计算机处理是否有高效的求解算法能否表示不精确知识,能否在同一层次上和不同层次上模块化知识和元知识能否用统一的形式表示是否适合于加入启发信息过程性表示还是说明性表示表示方法是否自然,6,2.1状态空间法（StateSpaceRepresentation）,问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）算符（operator）状态空间方法,7,2.1.1问题状态描述,定义状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。S:所有可能的初始状态集合。F:操作符集合。G:目标状态集合。,2.1状态空间法,8,2.状态空间表示概念详释,例如下棋、迷宫及各种游戏。,MiddleState,GoalState,2.1状态空间法,9,状态空间问题求解,状态空间法:从初始状态开始,每次加一个操作符,递增地建立起操作符的试验序列,直到达到目标状态为止.基本过程:1.为问题选择适当的”状态”及”操作符”的形式化描述方法,定义初始状态集合,目标状态集合及操作符集合;2.将操作符作用在初始状态(新状态)上生成新状态逐步构造状态空间,判断新状态是否为目标状态,如果是转3.否则转2.3.寻找从初始状态到目标状态的一个(最佳)路径。路径边上所使用的操作符序列就是该问题的一个解.,10,例:三数码难题（3puzzleproblem）,初始棋局,目标棋局,2.1状态空间法,11,有向图路径代价图的显示说明图的隐示说明,2.1.2状态图示法,A,B,2.1状态空间法,状态空间图,把初始状态可达到的各状态所组成的空间用有向图表示。用”状态”标识节点,用”操作”标识有向边,有向边方向由被施加操作的对象状态指向操作的结果状态。,12,13,2.1.3状态空间表示举例,产生式系统（productionsystem）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,2.1状态空间法,14,状态空间表示举例,例：猴子和香蕉问题,2.1状态空间法,15,解题过程,用一个四元表列（W，x，Y，z）来表示这个问题状态.,这个问题的操作（算符）如下：2goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）,2.1状态空间法,16,pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）,climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox（W，1，W，z）,2.1状态空间法,17,grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）,该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp,2.1状态空间法,18,2.1状态空间法,19,猴子和香蕉问题自动演示：,2.1状态空间法,状态空间表示举例,传教士和野人问题状态表示：(在河的左岸的传教士人数、野人人数和船的情况)初始状态:（3，3，1）结束状态:（0，0，0中间状态则:（2，2，0）、（3，2，1）、（3，0，0）,20,状态空间表示举例,状态表示：(在河的左岸的传教士人数、野人人数和船的情况)初始状态:（3，3，1）结束状态:（0，0，0中间状态则:（2，2，0）、（3，2，1）每个三元组对应了三维空间上的一个点问题的解，则是一个合法状态的序列：(初始状态，结束状态)中间状态：介于初始状态和结束状态之间除了初始状态外，该序列中任何一个状态，都可以通过一条规则，由与他相邻的前一个状态转换得到,21,22,2.2问题归约法（ProblemReductionRepresentation）,23,问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。,问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2.2问题规约法,24,2.2.1问题归约描述（ProblemReductionDescription）,梵塔难题,2.2问题规约法,25,解题过程（3个圆盘问题）,2.2问题规约法,26,多圆盘梵塔难题演示,2.2问题规约法,27,2.2.2与或图表示,1.与图、或图、与或图,2.2问题规约法,28,2.2问题规约法,29,2.一些关于与或图的术语,2.2问题规约法,30,3.定义,2.2问题规约法,31,不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。与或图构成规则,2.2问题规约法,32,梵塔问题归约图,（322）（333）,2.2问题规约法,33,2.3谓词逻辑法,逻辑语句形式语言,2.3.1谓词演算1.语法和语义基本符号谓词符号、变量符号、函数符号、常量符号、括号和逗号原子公式,34,连词和量词(Connective&Quantifiers)连词与及合取（conjunction)或及析取（disjunction）蕴涵（Implication）非（Not）量词全称量词（UniversalQuantifiers)存在量词(ExistentialQuantifiers),2.3谓词逻辑法,一阶谓词逻辑,一阶谓词逻辑表示法，是一种重要的知识表示方法，它以数理逻辑为基础，是到目前为止能够表达人类思维和推理的一种最精确的形式语言。它的表现方式和人类自然语言非常接近，它能够被计算机作精确推理。,35,一阶谓词逻辑,用谓词公式既可表示事物的状态、属性和概念等事实性的知识，也可表示事物间具有因果关系的规则性知识。,36,用谓词公式表示知识的一般步骤,1.定义谓词及个体，确定每个谓词及个体的确切含义。2.根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。3.根据所要表达的知识的语义，用适当的连接符将各个谓词连接起来形成谓词公式。,37,谓词逻辑表示知识举例1,用谓词逻辑表示下列知识：武汉是一个美丽的城市，但她不是一个沿海城市。1.定义谓词如下：BCity(x)：x是一个美丽的城市HCity(x)：x是一个沿海城市2.将个体代入谓词中，得到：BCity(wuhan),HCity(wuhan)3.根据语义，用逻辑连接符连接BCity(wuhan)HCity(wuhan),38,谓词逻辑表示知识举例2,用谓词逻辑表示下列知识：如果马亮是男孩，张红是女孩，则马亮比张红长得高。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),39,40,2.3.2谓词公式原子公式的的定义：用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。分子谓词公式可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,2.3谓词逻辑法,41,合适公式（WFF，well-formedformulas）合适公式的递归定义合适公式的性质合适公式的真值等价（Equivalence),2.3谓词逻辑法,42,2.3.3置换与合一,置换概念假元推理全称化推理综合推理定义就是在该表达式中用置换项置换变量性质可结合的不可交换的