第二章-知识表示方法(一)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 知识表示方法（一）,李艳燕,第二章 知识表示方法（一）李艳燕,数据、信息、知识？,2,2,数据、信息、知识的区别,数据：数据是按一定规则排列组合的物理符号，是关于事件的一组离散的客观事实。它是抽象的内容，而且单独看起来，它根本没什么意义。,信息：经过搜集和处理的数据。,知识：知识是信息经过加工整理、解释、挑选和改造而成的。它是经过人为的解读和人的经验充实之后的信息，同时它还极度依赖于该信息所处的背景环境。,3,数据、信息、知识的区别数据：数据是按一定规则排列组合的物理符,知识的特性,知识是人们把实践中获得的信息关联在一起所形成的信息结构。具有以下特性：,相对正确性,：任何知识都是在一定环境和条件下产生的，所以知识的正确性也是在一定的前提下才能正确的。,不确定性,：知识是有关信息关联在一起形成的信息结构，,“,信息,”,与,“,关联,”,是构成知识的两大要素。由于现实世界的复杂性，信息可能是精确的，也可能是不精确的、模糊的；关联可能是确定的，也可能是不确定的。这就使得知识不总是只有真和假两种状态，而是在真和假之间存在有很多状态，即存在,“,真,”,的程度问题。,4,知识的特性知识是人们把实践中获得的信息关联在一起所形成的信息,知识的特性,可表示性,：知识是可以用形式化的东西表示的，比如可用语言、文字、图形、公式等来表示知识，正由于知识的这一特性，才能使我们将知识数据化，才能用计算机来存储知识、传播知识和利用知识。,可利用性,：我们每时每刻都在利用我们所掌握的知识来解决现实世界中的各种问题，如果知识不具有可利用性，我们就不能积累知识，世界就不会前进。,5,知识的特性可表示性：知识是可以用形式化的东西表示的，比如可用,知识的分类,可从不同角度对知识进行分类：,以知识的作用范围划分，可分为,常识性知识,和,领域性知识,以知识的作用及表示来划分，可分为,事实性知识,是指有关领域内的概念、事实、事务的属性、状态及其关系的描述，包括事务的分类、属性、事务间关系、科学事实、客观事实等。,规则性知识,是指有关问题中与事务的行动、动作想联系的因果关系知识，这种知识是动态的、变化的。常以,“,如果,.,则,.,”,的形式出现。,控制性知识,是指有关问题的求解步骤、技巧性知识，告诉该怎样做一件事。也包括当有多个动作同时被激活时应该选择哪个动作来执行的知识。,元知识,是指有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。,6,知识的分类可从不同角度对知识进行分类：6,知识的分类,以知识的确定性来划分，可分为,确定知识,和,不确定知识,。,按照人类的思维及认识方法来分，可分为,逻辑性知识,和,形象性知识,。,7,知识的分类以知识的确定性来划分，可分为确定知识和不确定知识。,知识的表示,知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既要考虑知识的存储又考虑知识的使用。,知识表示实际上就是对人类知识的一种描述，以把人类知识表示成计算机能够处理的数据结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。,8,知识的表示知识表示是研究用机器表示知识的可行性、有效性的一般,知识的表示,知识表示方法可以分为陈述性知识表示和过程性知识表示两大类，但两者界限不明显，难以分开。,陈述性知识,表示主要用来描述事实性知识。这种表示方法告诉人们所描述的客观事物涉及的,“,对象,”,是什么，知识表示就是将对象的有关事实,“,陈述,”,出来，并以数据的形式表示。这类表示法将知识表示与知识运用（推理）分开处理，在表示知识时，并不涉及如何运用知识的问题，是一种静态的描述方法。,9,知识的表示知识表示方法可以分为陈述性知识表示和过程性知识表示,知识的表示,过程性知识,表示主要用于描述规则性知识和控制结构知识。这种表示方法就是告诉人们,“,怎么做,”,，知识表示的形式是一个,“,过程,”,，这一过程就是求解程序。它将知识的表示与运用（推理）相结合，知识就寓于程序之中，是一种动态的描述方法。,10,知识的表示过程性知识表示主要用于描述规则性知识和控制结构知识,知识表示方法的选择,表示能力：能正确、有效地将问题所需要的各类知识都表示出来；,可理解性：所表示的知识易懂、易读；,便于知识的获取和维护；,便于搜索；,便于推理。,11,知识表示方法的选择表示能力：能正确、有效地将问题所需要的各类,知识表示方法,状态空间法,/,产生式表示法,问题归约法,谓词逻辑法,语义网络法,框架表示法,剧本表示,过程表示法,12,知识表示方法状态空间法/产生式表示法12,1.,状态空间表示法,以,“,状态空间,”,的形式对问题进行定义，问题状态空间的构成包括：,（,1,）状态,描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：,Q=(q,0,q,1,.q,n,),其中每个元素,q,i,(i=0,1,2,.,n),为集合的分量，称为状态变量。当给每一个分量以确定的值时，就得到了一个具体的状态。,（,2,）算符,引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。比如走步、过程、规则、数学算子、运算符号或逻辑符号等。例如，在下棋程序中，一个算符就是一个走步。,13,1.状态空间表示法 以“状态空间”的形式对问题进行定义,（,3,）状态空间,由表示一个问题的全部状态及一切可用算符构成的集合称为该问题的状态空间。由三部分构成：问题的所有可能初始状态构成的集合,S,；算符集合,F;,目标状态集合,G,。用一个三元组表示（,S,F,G),。,状态空间的图示形式称为状态空间图。,节点表示状态,有向边（弧）表示算符,（,4,）问题的解,从问题的初始状态集,S,出发，经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列就构成了问题的一个解。,14,（3）状态空间14,用状态空间表示问题的步骤,:,（,1,）定义状态的描述形式,（,2,）表示问题的所有可能状态，并确定问题的初始和目标状态集合描述。,（,3,）定义一组算符，利用这组算符可把问题由一种状态转变为另一种状态。,15,用状态空间表示问题的步骤:15,利用状态空间求解问题的过程,:,不断把算符作用于状态的过程。首先将适用的算符作用于初始状态，以产生新的状态；然后再把一些适用的算符作用于新的状态；这样继续下去，直到产生的状态为目标状态为止。这使，就得到问题的一个解，即使从初始状态到目标状态所用算符构成的序列。,利用状态空间求解问题的过程:,例子：二阶,Hanoi,塔问题,问题简化，只考虑两个盘子的情况。已知三个柱子,1,2,3,和两个盘子,A,B(A,比,B,小,),。最初,A,，,B,依次放在柱子,1,上，最后要移动,A,，,B,到柱子,3,上，要求每次移动一个盘子，只能移动最顶上的盘子，并且任何时候不允许大盘放在小盘上。,17,例子：二阶Hanoi塔问题17,例,18,例18,例,19,例19,例,问题的解：,A(1,2),B(1,3),A(2,3),20,例问题的解：A(1,2),B(1,3),A(2,3)20,*,产生式表示法,用产生式规则表示知识，实质和状态空间法是一致的。可表示事实性知识和规则性知识。,基本形式是：,P Q,或,IF P THEN Q,P,是前提，,Q,是一组结论或操作。,21,*产生式表示法 用产生式规则表示知识，实质和状态空间法是,产生式表示法,确定性规则知识,P Q,或,IF P THEN Q,不确定性规则知识,P Q (,置信度,),或,IF P THEN Q,（置信度）,当已知事实与前提不能精确匹配时，只要按照置信度的要求达到一定的相似度，就认为已知事实与前提条件匹配,22,产生式表示法确定性规则知识22,产生式表示法,确定性事实性知识,三元组,表示,（对象，属性，值）或（关系，对象,1,，对象,2,）,例：老王年龄是,40,岁,（,Wang,Age,40,）,（,Friend,，,Wang,，,Zhang,）,不确定性事实性知识,四元组表示,（对象，属性，值，可信度）或（关系，对象,1,，对象,2,，可信度）,例：（,Wang,Age,40,0.8,）,（,Friend,Wang,Zhang,0.1,）,23,产生式表示法确定性事实性知识（Wang,Age,40）,产生式系统的组成,规则库：描述某领域内知识的产生式集合，包含把问题从初始状态转换成目标状态的变换规则。,综合数据库：事实库，存放输入的事实以及中间和最后结果的工作区,推理机：一个或一组程序，控制和协调规则库与综合数据库的运行，包含了推理方式和控制策略。,24,产生式系统的组成24,产生式系统推理方式,（,1,）正向推理,从已知事实出发，通过规则库得到结论。,推理过程：,1,）规则库中规则与综合数据库中的事实进行匹配，得到匹配的规则集合；,2,）使用冲突解决算法，从匹配规则集合中选择一条规则作为启用规则；,3,）执行启用规则的后件，将后件送入综合数据库或对综合数据库进行必要的修改。,重复这个过程直至达到目标。,数据驱动方式,/,自底向上,25,产生式系统推理方式（1）正向推理数据驱动方式/自底向上25,（,2,）反向推理,从目标（作为假设）出发，反向使用规则，求得已知事实。,推理过程：,1,）规则库中的规则后件与目标事实进行匹配，得到匹配的规则集合；,2,）使用冲突解决算法，从匹配规则集合中选择一条作为启用规则；,3,）将启用规则的前件作为子目标。,重复这个过程直至各子目标均为已知事实,目标驱动方式,/,自顶向下,26,（2）反向推理目标驱动方式/自顶向下26,（,3,）双向推理,推理从上、下两个方向同时进行，直至某个中间界面上两方向结果相符便成功结束。这种推理所形成的推理网络小，从而推理效率更高。,混合型,27,（3）双向推理混合型27,产生式表示法特点,清晰性：形式简单，表示格式固定，规则间相对独立，没有直接关系。易于构建知识库。,模块性：知识库与推理机分离，这样易于修改知识库，无需修改程序。长作为建构专家系统首选的知识表示方法。,自然性：符合人类的思维习惯，直观自然，便于推理。可以表示确定性和不确定性知识。,28,产生式表示法特点清晰性：形式简单，表示格式固定，规则间相对独,2.,问题归约法,问题归约的实质：从目标,(,要解决的问题,),出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合,问题归约表示的组成部分：,一个初始问题描述；,一套把问题变换为子问题的操作符；,一套本原问题描述。,29,2.问题归约法问题归约的实质：从目标(要解决的问题)出发逆,问题归约法,用于表示问题及其求解过程的形式化方法，通常用于表示比较复杂的问题求解。,复杂问题处理,:,问题分解,：将一个复杂问题,P,分解为若干子问题,P,1,P,2,.,P,n,(,每个子问题可以继续分解直到不需要或不能分解为止,),，然后对每个子问题求解，当所有子问题都有解时，原问题,P,才有解。,问题等价变换,：对,P,进行同构或同态的变换，将其变换成若干个较易求解的新问题,P,1,P,2,.,P,n,，只要这些问题中一个有解，则原问题,P,有解。,30,问题归约法用于表示问题及其求解过程的形式化方法，通常用于表示,可以用与,/,或树表示：,与树,或树,31,可以用与/或树表示：与树或树31,与,/,或树,一个问题既要通过分解，也要通过变换才能得到其本原问题，可用与,/,或树表示。根结点表示待求解的原始问题。,32,与/或树32,用与,/,或树表示问题的步骤：,1,）对待求解问题进行分解或等价变换；,2,）如果所得子问题不是本原问题，则继续分解或变换，直到分解或变换成本原问题；,3,）在分解或变化中，分解用,“,与树,”,表示