第三章问题求解技术

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能及其应用,主讲：李敏 教授,智能信息处理与仪器研究室,1,第,3,章 问题求解技术,智能,信息处理,与仪器研究室,学习要求,：,1.,了解命题逻辑与谓词逻辑的区别与联系，掌握谓词公式的概念及可满足性的定义，弄清置换与合一的概念，掌握求取最一般合一置换的方法。,2.,掌握归结原理及归结推理方法。激扬,SKOLEM,标准式和子句集的求取方法，理解谓词公式和子句集在不可满足意义下的一致性，弄懂,HERBRAND,定理，掌握,H,域、原子集、,H,域上的解释的求法，掌握命题逻辑和谓词逻辑中的归结原理。,3.,掌握利用归结原理进行定理证明的方法。,4.,掌握应用归结原理进行问题求解的方法。,5.,掌握归结过程中的控制策略。,2,第,3,章 问题求解技术,智能,信息处理,与仪器研究室,学习要求：,6.,理解不确定推理的基本概念和意义，了解不确定推理方法的种类，充分认识不确定推理中的基本问题，即不确定性的表示问题（包括证据不确定性和知识不确定性的表示）、不确定性的推理计算问题以及不确定性的度量问题。,7.,可信度方法又称确定性方法，是目前常用的不确定推理方法之一。要求充分理解可信度的概念，理解,CF,的含义，掌握利用可信度表示知识（规则）和证据的方法，掌握计算结论可信度的推理计算方法，并熟记各种推理计算公式。,3,第,3,章 问题求解技术,智能,信息处理,与仪器研究室,学习要求：,8.,主观,BAYES,方法是常用的不确定性推理方法之一。要求理解主观,BAYES,方法与基本,BAYES,概率公式之间的关系，了解主观,BAYES,方法的推理网络；掌握主观,BAYES,方法中知识（规则）不确定性和证据不确定性的表示方法，充分理解,(LS,LN),的含义；掌握各种情况下的结论不确定性的推理计算方法，熟记各种情况下的推理计算公式。,9.,证据理论又称,D-S,理论，是常用的第三种不确定性推理计算方法。要求充分了解与前两种不确定性推理方法在证据和结论表示方面的不同；理解概率分配函数、信任函数及似然函数的定义以及它们之间的相互关系；掌握概率分配函数正交和的计算方法；理解定义特定概率分配函数的意义，掌握基于该特定概率分配函数的不确定性推理方法，包括知识（规则）和证据的不确定性表示及结论不确定性的推理计算。,4,命题逻辑,智能,信息处理,与仪器研究室,命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，,特别是定理的自动证明发挥了重要作用。谓词逻辑是在命题逻辑的基础上发展起来的,命题,定义,1,能够分辨真假的语句,称做,命题,。,定义,2,一个语句如果不能再进一步分解成更简单的语句，并且本身是一个,命题，则称此命题为,原子命题,。,原子命题是命题中的最基本的单位，一般用大写字母,P,、,Q,、,R,表示，而命,题的真与假分别用“,T”,与“,F”,表示。,命题一般是一个陈述句，如,太阳从东边升起，雪是白色的,(,是命题,),真漂亮啊！，请站起来！，你到哪里去？（不是命题）,1+1=10 (,条件命题，在二进制情况下,),这盘菜太咸（是命题，但真假不能唯一确定，因人而异）,5,命题公式,智能,信息处理,与仪器研究室,连接词,:,在命题逻辑中用连接词将一些原子命题连接起来形成复合命题。, ：,“,非”或“否定”。,：,析取，表示两个连接的命题具有“或”关系。,：,合取，表示两个连接的命题具有“与”关系。,：,条件或蕴含，,PQ,表示,P,蕴含,Q,即“如果,P,则,Q”,其中，,P,称为条件,的前件，,Q,称为条件的后件。,：,双条件，,PQ,表示“,P,当且仅当,Q”.,表,1,命题逻辑真值表,P Q,P,Q,P,Q,P,Q,P,Q,P,T T,T F,F T,F F,T,T,T,F,T,F,F,F,T,F,T,T,T,F,F,T,F,F,T,T,6,命题公式,智能,信息处理,与仪器研究室,定义,3:,以下面的递归形式给出命题公式的定义：,原子命题是命题公式,A,是命题公式，则,A,也,是命题公式。,若,A,和,B,都是命题公式，则,A,B,AB,AB,A,B,也都是命题公式 。,只有按,得到的公式才是命题公式。,命题公式就是按照上述规则由原子命题、连接词及圆括号所形成的字符串。有时也称,命题演算公式。,连接词的优先级别为：,.,命题逻辑虽然可以用来表示知识，但它有较大的局限性，无法把所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物的共同特征表示出来。,张三是李四的老师，用,P,表示，反映不出关系。,贝多芬是作曲家和柴可夫斯基是作曲家，用命题逻辑表示时，是作曲家的共同特征无法形式化表示出来。,7,谓词逻辑,智能,信息处理,与仪器研究室,谓词与个体,在谓词逻辑中，将原子命题分解为,谓词,与,个体,两部分。,如，李白是诗人，,POET(LIBAI),53, GREATER(5,3),一元谓词：一个谓词与一个个体相关联。,多元谓词：一个谓词与多个个体相关联。,谓诩的一般形式：,P(x1,，,x2,，,，,xn,),其中,P,是谓词，,x1,，,x2,，,，,xn,是个体，谓词通常用大写字母，个体用小写字母表示。,P(x,),是一元谓词，,P(x,y,),是二元谓词，,P(,x1,，,x2,，,，,xn,),是,N,元谓词。,在谓词,P(x1,，,x2,，,，,xn,）,中，若,x,都是个体常量，变元或函数，称,一阶谓词,，如果,x,本身又是一个一阶谓词，则称,二阶谓词,。,8,谓词公式,智能,信息处理,与仪器研究室,连接词,，与命题逻辑中的连接词相同，复合谓词公式的真值表同复合命题逻辑的真值表。,量词,，全称量词（,x,）,它表示“对个体域中的所有（或任一个）个体,x”,存在量词（,x,）,它表示“在个体域中存在个体,x”,(,x)(y,)F(x,y,):,个体域中的任何个体,x,都存在一个个体,y,，,x,与,y,是朋友,(,x)(y)F(x,y,):,个体域中的任何两个个体,x,和,y,，,x,与,y,都是朋友,谓词演算公式,定义,4,谓词演算中，由单个谓词构成的不含任何连接词的公式，称为原子谓词公式,一般地,形如,F(x1,x2,xn,),的谓词公式称为原子谓词公式,或简称为原子,其中,F,为,n,元谓词,而,x1,x2,xn,为个体变元,.,9,谓词公式,智能,信息处理,与仪器研究室,由原子谓词公式、连接词、量词及圆括号所组成的字符串，按照上述规则构成谓词演算公式。,由原子公式的定义出发可定义谓词演算的合式公式如下：,例如：,10,谓词公式的永真性和可满足性,智能,信息处理,与仪器研究室,谓词公式的解释,定义,：设,D,为谓词公式,P,的个体域，若对,P,中的个体常量、函数和谓词按照如下规定赋值：,为每个个体常量指派,D,中的一个元素,;,为每个,n,元函数指派一个从,Dn,到,D,的映射，,其中,Dn,=(x1,x2,xn,)|,x1,x2,xn,D,为每个,n,元谓词指派一个从,Dn,到,F,T,的映射,.,则称这些指派为公式,P,在,D,上的一个解释。,谓词公式的永真性,定义,：如果谓词公式,P,对于个体域,D,上的任何一个解释都取得真值,T,则称,P,在,D,上是永真的，如是,P,在每个非空个体域上均永真，则称,P,永真。,定义：,如果谓词公式,P,对于个体域,D,上的任何一个解释都取得真值,F,则称,P,在,D,上是永假的，如是,P,在每个非空个体域上均永假，则称,P,永假。,谓词公式的永假性又称为不可满足性或不相容性。,11,谓词公式的永真性和可满足性,智能,信息处理,与仪器研究室,谓词公式的可满足性,定义,： 对于谓词公式,P,如果存在至少一个解释，使得公式,P,在此解释下的真值为,T,则称公式,P,是可满足的。,对谓词公式,P,，如果不存在任何解释使得,P,的取值为,T,则称公式,P,是不可满足的。不存在任何解释可使,P,的取值为,T,，即可理解为对于所有的解释都使公式,P,取值为,F(,因为谓词公式要么为,T,，要么为,F),，谓词公式,P,永假与不可满足是等价的。若,P,为永假，则也可称,P,不可满足的。,12,智能,信息处理,与仪器研究室,例,1,13,谓词公式的等价性,智能,信息处理,与仪器研究室,定义：,设,P,与,Q,是两个谓词公式，,D,是它们共同的个体域，若对,D,上的任何一个解释，,P,与,Q,的取值都相同，则公式,P,和,Q,在域,D,上是等价的。如果,D,是任意个体域，则称,P,和,Q,是等价的，记做,P,Q.,常用的等价式,14,谓词公式的永真蕴含,智能,信息处理,与仪器研究室,定义：,对于谓词公式,P,和,Q,如果,PQ,永真，则称,P,永真蕴含,Q,且称,Q,为,P,的逻辑结论，称,P,为,Q,的前提，记作,P,Q.,一些永真蕴含式,15,置换与合一,智能,信息处理,与仪器研究室,要使计算机模拟人类智能，就必须使计算机具有推理的功能，在用各种知识表示法对知识进行表示以后，这些知识就可以输入计算机了。在基于这些知识进行推理时，模式匹配是必须要进行的一项工作。因为只有经过模式匹配，才能从知识库中选出当前适用的知识，才能进行推理。例如，在产生式系统中，为了由已知的初始事实推出相应的结论，就必须从知识库中选出与初始事实相匹配的产生式规则，然后才能运用这些产生式规则进行推理，逐,步推出结论。,基于谓词逻辑的归结推理方法是一种确定性的推理方法，所以它所做的知识模式匹配也是一种确定性的匹配。为了使己知事实与知识库中的知识完全匹配，需要作某种变元置换，这里涉及到置换与合,的有关概念及方法。,16,置换,智能,信息处理,与仪器研究室,17,合一,智能,信息处理,与仪器研究室,18,智能,信息处理,与仪器研究室,例,2,19,智能,信息处理,与仪器研究室,例,2,20,智能,信息处理,与仪器研究室,例,2,21,归结推理方法,智能,信息处理,与仪器研究室,人工智能的目的之一就是使计算机能够模拟人的智能，解决实际中遇到的问题。研究自动定理证明，不仅使许多数学问题可以通过定理证明得以解决，而且可以使得许多如机器人规划等非数学的问题，归结为定理证明问题而得到解决。研究用计算机实现定理证明的机械化，已是人工智能研究的一个重要领域。对于定理证明问题，如果用一阶谓词逻辑表示的话就是要求对前提,P,和结论,Q,证明,P,Q,是永真的。然而，要证明这个谓词公式的永真性必须对所有个体域上的每一个解释进行验证，这是极其困难的。为了化简问题，同数学上常采用的方法一样，可以考虑反证法。即，先否定逻辑结论,Q,，再由否定后的逻辑结论,Q,及前提条件,P,出发推出矛盾，即可证明原问题。换一句话说，为了证明,P,Q,，只要从公式,P,Q,中推出矛盾即可，也就是说，只要证明,P,Q,是不可满足的即可。,22,谓词公式与子句集,智能,信息处理,与仪器研究室,对于定理证明问题，最终可以通过一阶谓词逻辑表示为,P,Q,的不可满足性问题，这里前提条件,P,和结论,Q,又都是以谓词公式表示的。当然，根据谓词公式的定义，,P,Q,也是一个谓词公式。所以，要解决的问题是要证明谓词公式的不可满足性。然而，由于谓词公式的形式干变万化，给谓词演算的研究带来一定的困难。,先介绍两种谓词演算公式的标准型，也就是范式。因而对谓词演算的研究就可以化归为对范式的研究。,23,谓词公式与子句集,智能,信息处理,与仪器研究室,24,谓词公式与子句集,智能,信息处理,与仪器研究室,25,谓词公式与子句集,智能,信息处理,与仪器研究室,26,谓词公式与子句集,智能,信息处理,与仪器研究室,27,智能,信息处理,与仪器研究室,例,3,28,子句与子句集,智能,信息处理,与仪器研究室,Herbrand,理论和,Robinson,的归结原理都是以子句集为背景开展研究的。,29,不可满足意义下的一致性,智能,信息处理,与仪器研究室,公式,G,与其子句集,S,并不等值，但它们在不可满足的意义下是,致的。,定理,设有谓词公式,G,，而其相应的子句集为,S,，则,G,是不可满足的充分必要条件是,S,是不可满足的。,30,Herbrand,理论,智能,信息处理,与仪器研究室,对于一个谓词公式来说，要证明它的不可满足性是困难的。所以，需要考虑它的子句集的不可满足性。然而，对子句集的不可满足性的判定仍然是困难的，因为要判断子句集的不可满足性就要对于句集中的每一个子句逐个进行判定。由于个体变元域,D,的任意性以及解释个数的无限性，这实际上是一项难以完成的工作。能否针对某一个具体的谓词公式，找到一个比较简单的特殊域，只要使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢,?,Herbrand,理论构造了这样的一个域，称为,Herbrand(H,域,),。只要对,H,域上的所有解释进行判定,即可得知谓词公式是否是不可满足的。,31,Herbrand,理论,智能,信息处理,与仪器研究室,32,Herbrand,理论,智能,信息处理,与仪器研究室,33,Herbrand,理论,智能,信息处理,与仪器研究室,34,智能,信息处理,与仪器研究室,例,4,35,智能,信息处理,与仪器研究室,例,5,36,智能,信息处理,与仪器研究室,例,6,37,智能,信息处理,与仪器研究室,例,7,38,智能,信息处理,与仪器研究室,例,8,39,Herbrand,定理,智能,信息处理,与仪器研究室,40,消解原理（归结原理）,智能,信息处理,与仪器研究室,Herbrand,定理只是从理论上给出证明子句集不可满足性的可行性和方法。但要在计算机上实现其证明过程却是非常困难的。,1965,年，,Robinson,提出了归结原理,这是对自动推理的重大突破，使得机器定理证明变为现实。,归结原理又称为消解原理，是,Robinson,提出的证明子句集不可满足性，从而实现了定理证明的一种理论和方法。,子句集中各子句间的关系是合取关系，因此，只要有一个子句是不可满足的，则子句集就是不可满足的。另外，在前面已经指出，空子句是不可满足的，所以只要子句集中包含一个空子句，则此子句集就一定是不可满足的。,Robinson,的归结原理正是基于这一认识提出来的，其基本思想是：检查子句集,S,中是否有空子句，若有，则表明,S,是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集,S,是不可满足的。,41,命题逻辑中的归结原理,智能,信息处理,与仪器研究室,定义,若,P,是原子谓词公式或原子命题，则称,P,与,P,为,互补文字,。,42,命题逻辑中的归结原理,智能,信息处理,与仪器研究室,43,命题逻辑中的归结原理,智能,信息处理,与仪器研究室,44,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,45,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,46,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,47,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：,48,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,49,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,50,一阶谓词逻辑中的归结原理,智能,信息处理,与仪器研究室,在命题逻辑推理中所结出的归结推理过程，在一阶谓词逻辑的,归结推理中仍然适用。,51,利用归结原理进行定理证明,智能,信息处理,与仪器研究室,52,利用归结原理进行定理证明,智能,信息处理,与仪器研究室,应用归结原理进行定理证明的步骤如下：,53,应用归结原理进行问题求解,智能,信息处理,与仪器研究室,54,智能,信息处理,与仪器研究室,例,9,55,智能,信息处理,与仪器研究室,例,10,56,智能,信息处理,与仪器研究室,例,11,57,智能,信息处理,与仪器研究室,例,12,58,智能,信息处理,与仪器研究室,例,13,59,智能,信息处理,与仪器研究室,例,13,60,智能,信息处理,与仪器研究室,例,13,61,智能,信息处理,与仪器研究室,例,14,62,智能,信息处理,与仪器研究室,例,14,63,智能,信息处理,与仪器研究室,例,14,64,智能,信息处理,与仪器研究室,例,15,65,智能,信息处理,与仪器研究室,例,15,66,智能,信息处理,与仪器研究室,例,15,67,智能,信息处理,与仪器研究室,例,15,68,智能,信息处理,与仪器研究室,例,16,69,智能,信息处理,与仪器研究室,例,16,70,智能,信息处理,与仪器研究室,例,16,71,智能,信息处理,与仪器研究室,例,16,72,智能,信息处理,与仪器研究室,例,16,73,智能,信息处理,与仪器研究室,例,16,74,智能,信息处理,与仪器研究室,例,16,75,不确定推理,智能,信息处理,与仪器研究室,基于一阶谓词逻辑的归结推理方法所依据的证据是确定性的即谓词所表示的知识要么为“真”，要么为“假”，其推理过程也是以数理逻辑为基础推理过程是严密的，所推出的结论也是确定的，即结论要么成立，要么不成立。所以，基于一阶谓词逻辑的归结推理方法是一种确定性的推理方法。但是，在日常生活中。人们通常所遇到的情况是信息不够完善、不够精确，即所掌握的知识具有不确定性。人们就是运用这种不确定性的知识进行思维、推理、进而求解问题。所以，为了解决实际问题，必须对不确定知识的表示、推理过程等进行研究。,76,不确定推理的概念,智能,信息处理,与仪器研究室,所谓推理就是从已知事实出发，运用相关的知识,(,或规则,),逐步推出结论或者证明某个假设成立或个成立的思维过程。其中，已知事实和知识,(,规则,),是构成椎理的两个基本要素。巳知事实是推理过程的出发点及推理中使用的知识，将其称为证据，而知识,(,或规则,),则是推理得以向前推进、并逐步达到最终目标的根据。,个人工智能系统由总数据库、知识库和推理机构成。其中，总数数据库就是已知事实的集合，而知识库即是规则库，是一些人们总结的规则的集合，推理机则是由,些推理算法构成，这些算法将依据知识库中的规则和总数据库中的事实进行推理计算。基中，知识库是人工智能系统的核心。由于现实世界中的事物以及事物之间的关系极其复杂，再加上客观上存在的随机性、模糊性以及某些事物或现象暴露的不充分性，从而导致了人们对它们认识的不精确和不完全，具有一定的不确定性。,不确定性推理就是从具有不确定性的证据出发，运用不确定性的知识,(,或规则,),库中的知识，最终推出具有一定程度的不确定性，但却是合理的或近乎合理的结论的思维过程。,77,不确定推理方法的分类,智能,信息处理,与仪器研究室,模型方法,:,模型方法的特点是把不确定的证据和不确定的知识分别与某种度量标准对应起来，并给出更新结论不确定性的合适的算法，从而构成相应的不确定性推理模型。不同的结论不确定性更换算法就对应不同的模型。后面介绍的几种不确定性推理方法都属于模型法。,控制方法,:,控制方法的特点是通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性系统产生的影响，这类方法没有处理不确定性的统一模型，其效果极大地依赖于控制策略，控制策略的选择和研究是这类不确定性推理方法的关键：启发式搜索、相关性制导问题等是目前常见的几种控制制方法。,78,不确定推理方法的分类,智能,信息处理,与仪器研究室,模型方法又分为,数值方法,和,非数值方法,两大类,.,数值方法是对不确定性的一种定量表示和处理方法，目前对它的研究及应用都比较多，形成了多种应用模型。它又可以按其所依据的理论不同分为基于概率的方法和模糊推理方法。基于概率的方法所依据的理论是概率沦，而模糊推理方法所依据的理论则是模糊理论。,非数值方法是指除数值方法外的其他各种处理不确定性的方法，它又包括很多方法。逻辑法就是一种非数值方法，它采用多值逻辑、非单调逻辑来处理不确定性。,79,三种不确定推理方法,智能,信息处理,与仪器研究室,在各类不确定性推理方法中，由于概率论有着完善的理论，同时还为不确定性的合成与传递提供了现成的公式，因而被用来表示和处理知识的不确定性，成为度量不确定性的重要手段。这种纯粹依靠概率模型来表示和处理不确定性的方法称为纯概率方法或概率方法。纯概率方法虽然有严密的理论依据，但它却要求给出事件的先验概率和条件概率，而这些数据又不易获得，因而使其应用受到限制。为此人们经过多年的研究，在概率沦的基础上，发展了一些新的处理不确定性的方法，这些方法包括：,可信度方法,、,主观,BAYES,方法,和,证据理论方法,。,80,可信度方法,智能,信息处理,与仪器研究室,可信度方法是美国斯坦福大学,E.H.Shortliffe,等人在确定性理论,(Theory of confirmation),的基础上，结合概率论等提出的一种不确定性推理方法。,1976,年在专家系统,MYCIN,中首先应用，它是不确定推理方法中应用最早、且简单有效的方法之一。,具有不确定性知识,(,规则,),如何表示,?,不确定性的证据如何表示,?,如何进行推理计算，即如何将证据的不确定性和知识的不确定性传递到结论,?,81,可信度概念,智能,信息处理,与仪器研究室,可信度是人们在实际生活中根据自己的经验或观察对某一事件或现象为真的,相信程度,：例如，孙晓强昨天没来上课，他的理由是因为肚子疼，就此理由而言，只有以下两种可能：一种是孙晓强真的肚子疼了，即理由为真；另一种是孙晓强根本没有肚子疼，只是找个借口不来上课，即理由为假。可信度也可以称做,确定性因子,，在以产生式作为知识表示的专家系统,MYClN,中，用以度量知识和证据的不确定性。显然，可信度具有较大的主观性和经验性，其准确性是难以把握的。但是，对某一具体领域而言由于该领域专家具有丰富的专业知识及实践经验，要给出该领域知识的可信度还是完全有可能的。另外，人工智能所面临的问题，较难用精确的数学模型进行描述，并且先验概率及条件概率的确定也比较困难，因此用可信度来表示知识及证据的不确定性仍不失为一种可行的方法。,82,知识不确定性的表示,智能,信息处理,与仪器研究室,在基于可信度的不确定性推理模型中,知识是以产生式规则的形式表示的，知识的不确定性则是以可信度,CF(H,，,E),表示的。其一般形式为,IF E THEN H (CF(H,，,E),其中：,E,是知识的前提条件，或称为证据。它既可以是一个简单条件，也可以是用,AND,及,OR,把多个简单条件连接起来所构成的复合条件。例如，有,E=E1 AND E2 AND (E3 0R E4),H,是结论，它可以是一个单一的结论，也可以是多个结论。,CF(H,E),是该条知识的可信度,称为可信度因子,(Certainty Factor),或规则强度,.,83,证据不确定性的表示,智能,信息处理,与仪器研究室,单个证据的不确定性获取方法,如果支持结论的证据只有一条，则证据可信度值的确定分两种情况。,第一种情况是，证据为初始证据，其可信度的值一般由提供证据的用户直接指定，指定的方法也是用可信度因子对证据不确定性进行表示，,例如,CF(E),0.8,表示证据,E,的可信度为,0.8,。,第二种情况就是用先前推出的结论作为当前推理的证据，对于这种情况的证据，其可信度的值在推出该结论时通过不确定性传递算法计算得到。证据,E,的可信度,CF(E),也是在,-1,1,上取值。,84,证据不确定性的表示,智能,信息处理,与仪器研究室,组合证据的不确定性的获取方法,如果支持结论的证据有多个，那么这多个证据间的关系有可,能是合取的关系，也可能是析取关系。这多个证据构成一个组合,证据。当证据是多个单一证据的合取时，即,E=E1E2,E3,En,若,El,，,E2,，,E3,，,，,En,各证据的可信度分别为,CF(E1),，,CF(E2),CF(En,),，则,CF(E),minCF(E1),，,CF(E2),.,CF(En,),当证据是多个单一证据的析取时，即,E=E1E2,E3,En,CF(E),minCF(E1),，,CF(E2),.,CF(En,),85,不确定性的推理计算,智能,信息处理,与仪器研究室,不确定性的推理计算是从不确定的初始证据出发，通过运用相关的不确定性知识，最终推出结沦并求出结论的可信度值。,只有单条知识支持结论时，结论可信度的计算方法,如果支持结论的知识只有一条，且已知证据的可信度,CF(E),和规则,(,知识,),IF E THEN H,的可信度,CF(H,E),则结论,H,的可信度计算公式如下：,CF(H),CF(H,，,E) x Max0,，,CF(E),86,不确定性的推理计算,智能,信息处理,与仪器研究室,多条知识支持同一结论时，结论不确定性的合成计算方法,若由多条不同知识推出了相同的结论，但可信度不同，则可用合成算法求出结论的综合可信度。由于对多条知识的综合可通过两两的合成实现，所以下面只考虑两条知识的情况。,设有如下知识：,IF E1 THEN H (CF(H,，,E1),IF E2 THEN H (CF(H,，,E2),则结论,H,的综合可信度可分如下两步算出：,(a),分别计算每,条知识的结论可信度,CF(H),：,CF1(H)=CF(H,E1)x Max0,CF(E1),CF2(H)=CF(H,，,E2)x Max0,CF(E2),b),用下式求出,E1,与,E2,对,H,的综合影响所形成的可,信度,CF1,2(H),：,87,不确定性的推理计算,智能,信息处理,与仪器研究室,这也是著名的专家系统,MYCIN,中所使用的结论不确定性计算公式。,88,不确定性的推理计算,智能,信息处理,与仪器研究室,在已知结论原始可信度的情况下，结论可信度的更新计算方法,在某些情况下，如果已知证据,E,对结论,H,有影响，且知识,IF,E THEN H,的可信度为,CF(H,E),，同时结论,H,原来的可信度为,CF(H),，那么如何求在证据,E,下结论,H,可信度的更新值,CF(H/E),呢,?,即已知规则,IF E THEN H(CF(H,，,E),及,CF(H),，求,CF(H/E),。,这时分三种情况进行讨论,:,89,不确定性的推理计算,智能,信息处理,与仪器研究室,90,不确定性的推理计算,智能,信息处理,与仪器研究室,91,主观,Bayes,方法,智能,信息处理,与仪器研究室,主观,Bayes,方法又称主观概率论，是内,R,0.Duda,等人于,1976,年提出的一种不确定推理模型，它是对概率论中基本,Bayes,公式的改进，是一种基于概率逻辑的方法。该方法在地矿勘探专家系统,PROSPECTOR,中得到了成功的应用。由于主观,Bayes,方法是对概率论中基本,Bayes,公式的改进，所以在介绍主观,Bayes,不确定推理模型之前，先回顾一下概率论中的基本,Bayes,公式。,92,Bayes,公式,智能,信息处理,与仪器研究室,93,Bayes,公式,智能,信息处理,与仪器研究室,94,Bayes,公式,智能,信息处理,与仪器研究室,95,Bayes,公式,智能,信息处理,与仪器研究室,96,智能,信息处理,与仪器研究室,97,智能,信息处理,与仪器研究室,证据理论,证据理论又称,D-S,理论，是由,A.P.Dempster,首先提出，井由,G,Shafer,进一步发展起来的一种处理不确定性的理论。该理论满足比概率论弱的公理能够区分“不确定”与“不知道”的差异，并能处理由“不知道”引起的不确定性，具有较大的灵活性，因而受到人们的重视。,由于涉及到较多数学基础知识，建议同学们课后找相关参考书自学。,98,