pr_lzh7_人工智能课件3_推理.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,章 高级知识推理,高级知识推理,经典逻辑,确定性推理 单调性推理,归约推理 肖解演绎推理 规则演绎推理,非经典逻辑,不确定性推理 非单调性推理,时序推理 概率推理,经典逻辑与非经典逻辑的不同,经典 非经典,推理方法 演绎逻辑 归纳逻辑,辖域取值 二值 多值 模糊,运算法则 有些不成立,逻辑算符 逻辑算符 引入模态算符,单调性 单调 非单调,单调推理和非单调推理,单调推理,基于谓词逻辑的推理系统是单调的,系统中已知为真的命题随着推理的进行而增加,结论越来越多,非单调推理,推理系统的定理集合不随推理过程的进行而单调增大,新推理出的定理可能修正以至否定原有的一些定理,使得原来能够解释的一些现象变得不可解释,.,非单调推理,非单调推理用来处理那些不适合用谓词逻辑表示的知识。,它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。,缺省推理,在没有证据能够证明某命题不成立时,就承认该命题成立,.,不具备命题的全部知识,也能够进行合理的推理并给出正确的结论,定义,如果,X,不知道，那么得结论,Y,。,如果,X,不能被证明，那么得结论,Y,。,如果,X,不能在某个给定的时间内被证明，那么得结论,Y,。,不确定性推理,精确推理的局限性,推理,依据已知事实（证据）、相关知识（规则）,证明某个假设成立,or,不成立,精确推理及其不足,将原本为不确定性的关系,“,硬性,”,转化为精确关系,将原本不存在明确界限的事物,“,人为,”,划定界限,歪曲了现实情况的本来面目,舍弃了事物的某些重要属性,失去了真实性,不确定性推理的定义及意义,1.,定义,也称,“,不精确性推理,”,从不确定性的初始证据（即已知事实）出发,运用不确定性的知识（或规则）,推出具有一定程度的不确定性但却是合理或近乎合理的结论,2.,意义,使计算机对人类思维的模拟更接近于人类的真实思维过程,不确定性推理的定义及意义,不确定性推理中的基本问题,不确定性的表示与度量,不确定性匹配,不确定性的传递算法,不确定性的合成,不确定性的表示与度量,1.,不确定性的表示,选择不确定性表示方法时应考虑的因素,充分考虑领域问题的特征,恰当地描述具体问题的不确定性,满足问题求解的实际需求,便于推理过程中对不确定性的推算,不确定性的表示与度量（续,1,）,2.,不确定性的度量,针对不同的领域问题采用不同的度量方法,用不同的数值刻画不同的不确定性程度,事先规定不确定性程度的取值范围,3.,常用的度量方法,测度理论（基于概率统计的度量方法）,Shannon,信息熵,其它度量方法,不确定性的表示与度量（续,2,）,在选择不确定性度量方法时应考虑的因素：,充分表达相应知识及证据不确定性的程度,度量范围便于领域专家及用户估计不确定性,便于计算过程中的不确定性传递，结论的不确定性度量不超出规定的范围,度量的确定应直观，且有相应的理论依据,不确定性匹配,解决不确定性匹配的常用方法,设计一个,匹配算法,用以计算相似度,指定一个相似度的,“,限定,”,（即,阈值,）,证据不确定性的组合,单一证据,&,组合证据,单一证据,：前提条件仅为一个简单条件,组合证据,：一个复合条件对应于一组证据,前提条件用,AND,（与）或,OR,（或）把多个简单条件连接起来构成复合条件,不确定性的传递,包含两个子问题,在,每一步推理,中，如何把证据及知识的不确定性传递给结论,在,多步推理,中，如何把初始证据的不确定性传递给最终结论,结论不确定性的合成,用不同知识进行推理得到相同的结论,相同结论的不确定性程度却不相同,需要用合适的算法对它们进行合成,不确定性推理方法的分类,不确定性推理的两条研究路线,模型方法,在推理一级上扩展确定性推理,不确定证据和知识与某种度量标准对应,给出更新结论不确定性的算法,构成相应的不确定性推理模型,控制方法,在控制策略一级上处理不确定性,无统一的不确定性处理模型，其效果依赖于控制策略,不确定性推理方法的分类,不确定性推理,模型,方法,控制,方法,数值,方法,非数值,方法,概率统,计方法,模糊推,理方法,粗糙集,方法,绝对概率方法,贝叶斯方法,证据理论方法,HMM,方法,发生率计算,相关性制导回溯、机缘控制、启发式搜索等,可信度方法,关于不确定性推理方法的说明,数值方法,对不确定性的一种定量表示和处理方法,其研究及应用较多，已形成多种应用模型,非数值方法,除数值方法外的其它处理不确定性的模型方法,典型代表：,“,发生率计算方法,”,，它采用集合来描述和处理不确定性，且满足概率推理的性质,关于不确定性推理方法的说明（续,1,）,概率统计方法,有完整、严密的数学理论,为不确定性的合成与传递提供了现成的数学公式,最早、最广泛地用于不确定性知识的表示与处理,已成为不确定性推理的重要手段,证据理论方法,1967,年,Dempster,首次提出，,1976,年,Shafer,完善,可表示并处理,“,不知道,”,等不确定性信息,关于不确定性推理方法的说明（续,2,）,模糊推理方法,可表示并处理由模糊性引起的不确定性,已广泛应用于不确定性推理,粗糙集理论方法,1981,年,Z.Pawlak,首次提出,一种新的可表示并处理,“,含糊,”,等不确定性的数学方法,可用于不确定性推理、数据挖掘等领域,概率推理,概率论是研究随机现象中数量规律的科学。,所谓随机现象是指在相同的条件下重复进行某种实验时，所得实验结果不一定完全相同且不可预知的现象,掷硬币实验,人工智能所讨论的不确定性现象，虽然不完全是随机的过程，但是实践证明，采用概率论的思想方法考虑能够得到较好的结果。,概率论基础,（,概率定义,）,定义：,设,为一个随机实验的样本空间，对,上的任意事件,A,，规定一个实数与之对应，记为,P(A),，满足以下三条基本性质，称为事件,A,发生的概率：,若二事件,A,、,B,互斥，即，则,以上三条基本规定是符合常识的。,概率论基础,（条件,概率,）,定义,：设,A,，,B,为事件且,P(A)0,，称,P(B|A),为事件,A,已发生的条件下，事件,B,的,条件概率,，,P(A),在概率推理中称为,边缘概率,。,简称,P(B|A),为给定,A,时,B,发生的概率。,P(AB),称为,A,与,B,的联合概率。有联合概率公式：,概率论基础,（条件,概率性质,）,，,乘法公式,：,全概率公式：设,A,1,，,A,2,，,A,n,互不相交，且 ，,则对于任意事件,A,有,概率论基础,（,贝叶斯定理,）,设,A,，,B,1,，,B,2,，,，,B,n,为一些事件，,P(A)0,，,B,1,，,B,2,，,，,B,n,互不相交，,P(B,i,)0,i=1,2,n,，且 ，则对于,k=1,2,n,，,贝叶斯公式容易由条件概率的定义，乘法公式和全概率公式得到。在贝叶斯公式中，,P(B,i,),i=1,2,n,称为,先验概率,，而,P(B,i,|A)i=1,2,n,称为,后验概率,也是,条件概率,。,独立性,和是独立的,在给定时，和是条件独立的,概率推理,设,H,1,H,2,H,3,为三个结论,E,是支持这些结论的证据,且已知,:,P(H,1,)=0.3,P(H,2,)=0.4,P(H,3,)=0.5,P(E|H,1,)=0.5,P(E|H,2,)=0.3,P(E|H,3,)=0.4,求,:P(H,1,|E),P(H,2,|E),P(H,3,|E),解,:,贝叶斯网络,二十世纪八十年代贝叶斯网络（,Bayes Network,）成功地应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。,基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具，具有坚实的数学理论基础。,在综合先验信息（领域知识）和数据样本信息的前提下，还可避免只使用先验信息可能带来的主观偏见。,虽然很多贝叶斯网络涉及的学习问题是,NP,难解的。但是，由于已经有了一些成熟的近似解法，加上一些限制后计算可大为简化，很多问题可以利用近似解法求解。,贝叶斯网络,贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方式，可信度计算也是概率计算方法，只是在实现时，各具体系统根据应用背景的需要采用各种各样的近似计算方法。,推理过程称为概率推理。,贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。,贝叶斯网络的由来,全联合概率计算复杂性十分巨大,朴素贝叶斯太过简单,现实需要一种自然、有效的方式来捕捉和推理,不确定性知识,变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目,贝叶斯网络,（,基本概念,）,贝叶斯网络：,一系列变量的联合概率分布的图形表示。,一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。,贝叶斯网络的定义,是一个有向无环图,(DAG),随机变量集组成网络节点，变量可离散或连续,连接节点对的有向边组成边集合,每节点,X,i,都有一个条件概率分布表：,P(X,i,|Parents(X,i,),，,量化其父节点对该节点的影响,独立和条件独立,Weather,Cavity,Catch,Toothache,Weather,和其它,3,个变量相互独立,贝叶斯网络示例,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,B E,P(A),t t,t f,f t,f f,0.95,0.94,0.29,0.001,A,P(J),t,f,0.90,0.05,A,P(M),t,f,0.70,0.01,P(B),0.001,P(E),0.002,贝叶斯网络的语义,贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络,。,贝叶斯网络的语义,P(x,1,.,x,n,)=P(x,1,|parent(x,1,).P(x,n,|parent(x,n,),贝叶斯网络的语义公式计算示例：,试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时,John,和,Mary,都给你打电话的概率。,解：,P(J,M,A,B,E)=P(J|A)P(M|A)P(A|B,E)P(B)P(E),=0.9x0.7x0.001x0.999x0.998=0.00062,=0.062%,贝叶斯网络的推理,计算,贝叶斯网络中的条件独立关系,：,给定父节点，一个节点与它的,非后代节点,是条件独立的,给定一个节点的父节点、子节点以及子节点的父节点,马尔可夫覆盖,(Markov blanket),，这个节点和网络中,的所有其它节点是条件独立的,主观,Bayes,方法,用产生式规则表示知识,:,IF E THEN(LS,LN)H,式中,(LS,LN),表示知识的静态强度,LS:,充分性因子,LN:,必要性因子,充分性度量,它表示,E,对,H,的支持程度，取值于,0,由专家给出。,必要性度量,它表示,E,对,的支持程度，即,E,对,H,为真的必要性程度，取值范围为,0,+,，也是由专家凭经验给出。,主观,Bayes,方法,几率函数,表示,x,的出现概率与不出现概率之比,当,P(x)=0,时，有,O(,x,),0,当,P(x)=1,时，有,O(,x,),把取值为,0,1,的,P(X),放大为取值,0,+,的,O(X).,知识不确定性的表示,由,Bayes,公式，,由以上两式可得，,即有，,同理可得,:,以上两式是修改的,Bayes,公式,当,E,为真时,利用,LS,将,H,的先验几率,O(H),更新为后验几率,O(H|E),当,E,为假时,利用,LN,将,H,的先验几率,O(H),更新为后验几率,O(H|E),知识不确定性的表示,LS,时,O(H|E),P(H|E)1,E,的存在导致,H,为真,.,因此称,E,对,H,是充分的,LS,为充分性因子,LN,0,时,O(H|E)0,P(H|E)0,E,的不存在导致,H,为假,.,因此称,E,对,H,是必要的,LN,为必要性因子,证据的不确定性描述,根据观察,S,直接求出,P(E|S),非常困难，引进了可信度,C(E|S),，用户可根据实际情况在,-5,5,中选取一个整数作为初始证据的可信度。,可信度,C(E|S),与概率,P(E|S),的对应关系可用下式表示：,C(E|S)=-5,，表示在观察,S,下证据,E,肯定不存在，即,P(E|S)=0,；,C(E|S)=0,，表示在观察,S,与证据,E,无关，即,P(E|S)=P(E),；,C(E|S)=5,，表示在观察,S,下证据,E,肯定存在，即,P(E|S)=1,。这样，用户只要对证据,E,给出在观察,S,下的可信度,C(E|S),，系统即可求出相应的,P(E|S),。,组合证据的不确定性描述,对于组合证据,E,E,1,AND E,2,AND AND E,n,则,P(E|S),minP(E,1,|S),P(E,2,|S),P(E,n,|S),对于组合证据,E,E,1,OR E,2,OR OR E,n,则,P(E|S),maxP(E,1,|S),P(E,2,|S),P(E,n,|S),基于主观,Bayes,方法的不确定性推理,在主观,Bayes,方法中，知识是用产生式规则表示的，具体形式为：,IF E THEN(LS,LN)H(P(H),LS,LN,是充分性和必要性度量，,P(H),是专家给出的先验概率。,推理就由,P(H),，,P(E),，,LS,和,LN,求出,的过程。,证据,E,确定必出现,P(E)=P(E/S)=1,，由,Bayes,公式，,由以上两式可得，,即有，,若需要以概率的形式表示，再由公式,计算出,这就是把先验概率,P,(,H,),更新为后验概率,P(H|E),的计算公式。,证据,E,确定必不出现,P(E)=P(E|S)=0,所以,从而,这就是把先验概率,P(H),更新为后验概率,的计算公式。,证据,E,不确定,不能用上面的公式计算后验概率，可用,Duda,于,1976,年给出的公式 来计算出后验概率。这分为以下情况：,证据肯定存在,证据肯定不存在,与无关,当,P,（,E|S,）为其它值时,证据,E,不确定,(,续,),当,故,这就是证据肯定存在的情况。,当,故有,这就是证据肯定不存在的情况。,证据,E,不确定,(,续,),当,P(E|S)=P(E),时，与无关，利用全概率公式有,当,P(E|S),为其它值时，通过分段线性插值的方法，就可以得到计算,P(H|S),的公式，,即,该公式称为,EH,公式。,P(E),(E|S)1,对于初始证据，由于其不确定性是用可信度,C(E|S),给出，此时只要把,P(E|S),与,C(E|S),的对应关系转换公式代入,EH,公式，就可以得到用可信度,C(E|S),计算,P(H|S),的公式：,该公式称为,CP,公式。这样，当用初始证据进行推理时，根据用户告知的,C(E|S),通过运用,CP,公式就可以求出,P(H|S).,当用推理过程中得到的中间结论作为证据进行推理时，通过运用,EH,公式就可求出,P(H|S).,结论不确定性的合成算法,若有,n,条规则都支持相同的结论，而且每条规则的前提条件所对应的证据,i,（,i=1,2,n,）都有相应的观察,S,i,与之对应，此时只要先对每条规则分别求出,H,的后验几率,O(H|S,i,),然后按下列公式求出所有观察下,H,的后验几率,.,证据理论,Dempster-Shafer,理论,诞生,：,源于,20,世纪,60,年代美国哈佛大学数学家,A.P.Dempster,在,利用上、下限概率来解决多值映射问题,方面的研究工作。自,1967,年起连续发表了一系列论文，标志着证据理论的正式诞生。,形成,：,Dempster,的学生,G.Shafer,对证据理论做了进一步的发展，引入,信任函数,概念，形成了一套基于,“,证据,”,和,“,组合,”,来处理不确定性推理问题的数学方法，并于,1976,年出版了,证据的数学理论,(,A Mathematical Theory of Evidence,),，这标志着证据理论正式成为一种处理不确定性问题的完整理论。,证据理论的核心、优点及适用领域,核心,：,Dempster,合成规则,，这是,Dempster,在研究统计问题时首先提出的，随后,Shafer,把它推广到更为一般的情形。,优点,：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上,Dempster,合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在,专家系统、信息融合,等领域中得到了广泛应用。,适用领域,：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。,证据理论的局限性,要求,证据必须是独立的,，而这有时不易满足,证据合成规则没有非常坚固的理论支持，其,合理性和有效性还存在较大的争议,计算上存在着潜在的,指数爆炸问题,证据理论的主要特点,满足比,Bayes,概率理论更弱的条件，即,不必满足概率可加性,。,具有,直接表达,“,不确定,”,和,“,不知道,”,的能力。,证据理论不但允许人们将信度赋予假设空间的单个元素，而且还能赋予它的子集，这,很象人类在各级抽象层次上的证据收集过程,。,其他推理方法,非单调推理,时序推理,缺省推理,模糊逻辑,