人工智能原理第7章不精确推理.ppt

,*,人工智能原理,第,7,章 不精确推理,1,本章内容,7.1,不精确推理的必要性,7.2,贝叶斯概率推理,7.3,贝叶斯网络,7.4,可信度方法*,7.5,模糊推理,参考书目,第,7,章 不精确推理,2,7.1,不精确推理的必要性,不精确推理的原因,/,方法,第,7,章 不精确推理,3,为什么要不精确推理,做不精确推理的原因有多种：,推理所需的信息不完备：,竞争双方不知道对方信息,背景知识不足：,疑难病症的机理,多种原因导致同一结果：,疾病的诊断,信息描述模糊：,目击者对嫌疑犯的描述,信息中含有噪声：,做假帐，虚假统计报表，采集数据当中的噪声（雷达、声纳,/,化验）等,第,7,章 不精确推理,4,不精确推理的原因,规则是模糊的：,定性描述，如“如果刑事犯罪猖獗，就应加大打击力度”等,推理能力不足：,天气预报的计算,解决方案不唯一：,多个方案如何选优的问题,两种不确定性,环境的不确定性,智能体几乎从来无法了解关于其环境的全部事实,反映环境的知识的不确定性,过于复杂而无组织,知识粥,(knowledge soup),第,7,章 不精确推理,5,不精确推理,现实不确定性需要不精确推理，将数值计算引入推理过程,继续使用逻辑联结词,真假值概率化，以表示某种可靠程度,在推理的前提和结论之间建立概率公式（解释）,前提称为证据，结论称为假设,应用：专家系统中的推理网络,(PROSPECTOR,系统,/MYCIN,系统,),第,7,章 不精确推理,8,贝叶斯网络,(Bayesian network),智能体使用概率对行动结果,(,用事件之间的联系表示,),进行预测，进而选择期望效用最高的行动,贝叶斯网络,(,也叫贝叶斯信念网,),是一个节点标注了定量概率信息的有向图，反映了一个事件对于另一个事件的影响程度,/,表示了变量之间的依赖关系和概率信息,贝叶斯网络是事件之间联系的全面而形象的表示,第,7,章 不精确推理,9,知识粥,(Knowledge Soup),现实世界的复杂性和不确定性反映在智能体内部,异质的、不固定的、经常不一致的知识,称为知识粥,“,粥体,”,包含小块,(small chunk),对应于规则、框架等，大块,(large chunk),对应于整个理论,这些“块”的内部是一致的，“块”之间可以是不一致的,从整体来说，知识往往具有这样的特性,模糊、不确定、随机、无知,第,7,章 不精确推理,10,7.2,Bayes,概率推理,7.2.1,有关概念和公式,7.2.2,几率和似然比,7.2.3,似然比应用,第,7,章 不精确推理,11,主观,Bayes,主义,主观,Bayes,主义：,将概率推理与归纳逻辑的解释联系起来，现实世界的一些因果关系可以形成一种信念，它并非在所有场合下都正确，可称为部分信念,/,表示这种信念的最好方法是概率方法，对概率的解释有若干种，其中,Bayes,创立了主观解释，也称为主观,Bayes,主义,其要点是：概率是个人的一种合理置信度，每个人的估计,(,概率,),虽然各不相同，但应该满足概率的基本规律和其他某些客观规律，因而是合理的,第,7,章 不精确推理,12,7.2.1,有关概念和公式,在,Bayes,概率推理中，推理规则表示为,if E(,前提,/,证据,),then H(,结论,/,假设,)(,LS,LN),规则强度用,LS/LN,表示,(,也称为似然比,)/,其不精确推理过程是：根据证据,E,的概率,P(E),，利用规则的,LS,和,LN,，把结论的先验概率,P(H),更新为后验概率,P(H|E),，因而也称为概率传播,第,7,章 不精确推理,13,Bayes,条件概率,Bayes,条件概率：令假设,H,的先验概率为,P(H),，,P(H),是指定的,/,证据,E,为真时,H,的条件概率为,P(H|E),，,P(H|E),的一部分是指定的，一部分是根据,P(H),和指定的,P(H|E),计算出来的，这部分计算出的概率称为后验概率,条件概率,P(H|E),可看作以一定概率成立的,EH,的推理规则,第,7,章 不精确推理,14,概率公理,Bayes,概率服从如下公理,(Kolmogorov,公理,),：,(1)0P(H)1,(2)P(H=T)=1/P(H=F)=0,(3)P(HG)=P(H)+P(G),P(H,G,)/,当,H,和,G,互斥有,P(HG)=P(H)+P(G),特别有,P(H)+P(H)=1/,一般地有,P(H,i,|E)=1,即证据,E,下,H,i,的全体构成了一切可能的假设，其中任意,H,i,和,H,j,(ij),互斥,这样的概率公理是不能违反的,(p364,论证,),第,7,章 不精确推理,15,条件概率公式,条件概率公式,P(H&G)=P(H|G)P(G)=P(G|H)P(H),该公式指明了,H,和,G,两个假设之间存在着相关性,如果,H,和,G,相互独立，则,P(H|G)=P(H),P(G|H)=P(G),P(H&G)=P(H)P(G),第,7,章 不精确推理,16,全概率公式,全概率公式：一个假设的先验概率可以表示为两个假设的概率，其中后面一个假设遍历各种可能性且各个可能性之间是独立的，则有,P(H)=,i,P(H&Gi)=,i,P(H|Gi)P(Gi),其解释为：假设,H,的概率等于从各种证据提供的信息所推出的条件概率之和,/,证据满足独立性和完全性,这个公式也称为全联合分布,第,7,章 不精确推理,17,边缘化,上述全概率公式从另一个角度可以视为通用化边缘规则：,P(Y)=,z,P(Y,z)=,z,P(Y|z)P(z),将随机变量的某个变量的分布抽取出来，求和从而得到该变量的无条件概率,(,或称为边缘概率,)/,其过程称为边缘化或求和消元,(summing out),用于从多个变量的全概率分布中求取某个变量的概率，进行推理,第,7,章 不精确推理,18,归一化,在一定条件下某个随机变量的绝对概率值可以根据概率公理来归一化,一种结果作为分子，同条件各种结果之和作为分母,通常，同条件下结果只有,2,个,a/,a,，故有,p(a|*)+p(a|*)=1(*,为某种条件,),引入归一化常数,=1/p(a)+p(,a),第,7,章 不精确推理,19,逆概率公式,逆概率公式,从条件概率公式可得,如果有多个假设,H,1,H,n,，则上式化为,第,7,章 不精确推理,20,逆概率公式的例子,逆概率公式不仅是条件概率公式的一个简单变形，实际上很有用处,如果某个条件概率不便计算，则可以先计算其逆概率，而后算出所要的条件概率,例子：,求,P(,肺炎,|,咳嗽,),可能比较困难，但统计,P(,咳嗽,|,肺炎,),可能比较容易,(,因为要上医院,)/,假设,P(,肺炎,)=1/10000,，而,P(,咳嗽,)=1/10,，,90%,的肺炎患者都咳嗽，则,P(,肺炎,|,咳嗽,)=,第,7,章 不精确推理,21,修正因子,(1),可以将前面的逆概率公式写成,这说明先验概率,P(H),可以通过方括号部分,(,作为修正因子,),修正为后验概率,P(H|E)(,证据,E,为真时,H,的后验概率,),在上面的例子中，医生认为一个人得肺炎的可能性为万分之一，一旦发现患者咳嗽，就将调整为万分之九,第,7,章 不精确推理,22,修正因子,(2),将,E,看作证据，先验概率,P(E),越小，且,H,为真时,E,的条件概率,P(E|H),越大，则修正因子所起作用越大,在上例中，如果,P(,咳嗽,)=0.0001/P(,咳嗽,|,肺炎,)=0.9999/,P(,肺炎,),不变,则,P(,肺炎,|,咳嗽,)=0.9999,，远远超过原来的万分之九,第,7,章 不精确推理,23,后验概率递推公式,当有,n,个互相独立的证据，则有公式,上式,可以写成递推公式形式：,上式说明：随着新证据的不断获得，从证据少时的后验概率推出证据多时的后验概率，且每一步都是把上一步的后验概率视为新证据到来时的先验概率,第,7,章 不精确推理,24,6.2.2,几率和似然比,引入相对量度,定义,几率：,称为,H,的几率或先验几率，取值范围,0,),由此反过来有,定义,条件几率：,第,7,章 不精确推理,25,后验几率和先验几率的关系,例子,：,O(,晴天,|,冬天早晨有雾,)=4.2,，如果冬天早晨有雾，则该天为晴天的可能性是非晴天可能性的,4.2,倍,由几率定义、条件几率定义和条件概率公式可以推得后验几率和先验几率的关系：,第,7,章 不精确推理,26,似然比,定义,似然比：,LS=P(E|H)/P(E|H),LN=P(E|H)/P(E|H),则可得下述关系：,O(H|E)=LS*O(H),O(H|E)=LN*O(H),有多个证据独立时，其公式是,第,7,章 不精确推理,27,似然比约束,对,LS,和,LN,的约束,对于,LS,和,LN,有如下约束要求：二者都是非负的，并且满足,第,7,章 不精确推理,28,6.2.3,似然比应用,似然比,(,规则强度,)LS,和,LN,的应用,当,P(E)=1,时，利用,LS,将先验几率,O(H),更新为后验几率,O(H|E)/,当,P(E)=1,时，利用,LN,来更新几率,在专家系统,PROSPECTOR(,一个用于探矿的,ES),中同时应用了,LS,和,LN,，分别表示正面证据和反面证据的支持，称为充分因子和必要因子，并将,LS,、,LN,附着在每条规则之上,第,7,章 不精确推理,29,LS,和,LN,的作用,当,LS,很大，说明证据成立时假设成立的可能性很大，否则,LS1,说明,E,排斥,H,；,LN,很小，说明证据不成立时假设不成立的可能性很大,LS,和,LN,之值接近,1,时说明证据成立或不成立对于结论是否成立影响不大,一般情况下，,LS,和,LN,不是根据定义计算出来的，而是给定的,第,7,章 不精确推理,30,应用举例,(1),例子：评职称的概率,设某副教授,X,要评正教授，现有,4,个指标，却有,8,人参与竞争,/,投票前夕，,X,作了如下预测：如果不考虑评委因素，则成功概率,=1/2,，此相当于先验几率,O(H)=1,；如果考虑评委因素，则情况如下：,校评委共,15,人，其中,5,人来自其他竞争者所在系，,4,人与,X,素有微隙，尤其是其中,2,人兼具来自其他竞争者所在系，对,X,的成功构成了极大威胁，但聊以自慰的是评委中有,5,位老朋友，估计会投,X,的票,第,7,章 不精确推理,31,应用举例,(2),为此，,X,定义了如下的似然比：,LS(,评委,Y1,出席,|X,评上,)=1/2 Y1,来自其他竞争者所在系，同时令,LN=2(LS*LN=1),LS(,评委,Y2,出席,|X,评上,)=1/4Y2,与,X,素有微隙，同时令,LN=4,LS(,评委,Y3,出席,|X,评上,)=1/8Y3,来自其他竞争者所在系兼与,X,素有微隙，同时令,LN=8,LS(,评委,Y4,出席,|X,评上,)=4Y4,是,X,的老朋友，同时令,LN=1/4,LS(,评委,Y5,出席,|X,评上,)=1Y5,不属于以上情况，,LN=1,第,7,章 不精确推理,32,应用举例,(3),若,15,人全体出席，且假定各条件互相独立，则按公式,(6.11),，,X,评上的后验概率是：,O(X,评上,|15,人出席,)=,根据几率和概率之间的关系，换为概率,P=O/(1+O)=1/9,，,X,评上的希望不大,第,7,章 不精确推理,33,应用举例,(4),但是，当又有消息说，一位来自其他竞争者所在系兼与,X,素有微隙的评委,A,不能出席，而代之以一位态度中立的评委,/,此时，,X,又作了一番推测：,LS(A,出席,|X,评上,)=LN(A,出席,|X,评上,)=8,LS(,中立评委,|X,评上,)=1,则在原结果的基础上乘上上述因子，使得后验几率,=1,，即后验概率,=1/2,，,X,评上的前景大大改观,第,7,章 不精确推理,34,7.3,贝叶斯网络,7.3.1,贝叶斯网络的表示,7.3.2,贝叶斯网络中的精确推理,7.3.3,贝叶斯网络的近似推理,第,7,章 不精确推理,35,贝叶斯网络定义,贝叶斯网络,(Bayesian network),是一个有向图，其中每个节点都标注了定量概率信息,(1),一个随机变量集合组成网络节点，变量可以是离散的或者连续的,(2),一个连接节点对的有向边或者箭头的集合，如果存在从节点,X,指向节点,Y,的有向边，则称,X,是,Y,的一个父节点,(3),每个节点都存在一个条件概率分布,P(Xi|Parent(Xi),，量化父节点对该节点的影响,(4),图中不存在有向环,(,是有向无环图,DAG),第,7,章 不精确推理,36,6.3.1,贝叶斯网络的表示,从一个例子,(,防盗网,),开始,第,7,章 不精确推理,Burglary,Earthquake,Alarm,JohnCall,MaryCall,P(B),.001,P(E),.002,B E P(A),T T .95,T F .94,F T .29,F F .001,A P(J),T .90,F .05,A P(M),T .70,F .01,37,条件概率表,每个节点旁的条件概率表,(,简称,CPT),中的值对应一个条件事件的概率,如,P(A)=0.94=P(A|Burglary,Earthquake,),条件事件是父节点取值的一个可能组合,每行的概率之和应改为,1(,表中只给出了为真的情况，为假的概率应为,1-p),一个具有,k,个布尔父节点的布尔变量的条件概率表中有,2,k,个独立的可指定的概率,(,注意概率值是独立的,),没有父节点的节点的概率只有,1,行,/,为先验概率,第,7,章 不精确推理,38,全联合概率分布,贝叶斯网络给出了关于相关事件的完整描述，通过计算全联合概率分布求取,联合分布中的某项是对每个变量赋予一个特定值情况下的合取概率,就是条件概率表中适当元素的乘积,例子,P(j,ma,b,e,)=P(j|a)P(m|a)P(a|,b,e,)P(,b,)P(,e,)=0.90*0.70*0.001*0.999*0.998=0.00062,第,7,章 不精确推理,39,链式法则,初始的合取概率化为更小的条件概率和更小的合取式,/,这些条件概率的合取式实际上就是父节点到子节点的概率乘积,P(X,i,|X,i-1,X,1,)=P(X,i,|Parent(X,i,),如果父节点包含于条件,X,i-1,X,1,之中,此为链式法则,父子节点的关系使得贝叶斯网络具有局部结构化的特性，即每个节点只和数量有限的其它部分产生直接的相互作用,第,7,章 不精确推理,40,局部结构化与节点顺序,由于贝叶斯网络的局部结构化，每个随机变量可以至多受到至多,k,个其它随即变量的影响,(k=,常数,),设网络中有,n,个节点,(,随机变量,),，指定每个条件概率表所需信息量至多为,2,k,个数据，则整个网络可以用,n2,k,个数据完全描述,/,而全联合概率分布需要,2,n,个数据,构造贝叶斯网络的次序：添加节点首先从“根本原因,”,开始，然后加入受其直接影响的变量，直到叶节点,(,不影响任何其它节点,),第,7,章 不精确推理,41,条件独立关系,贝叶斯网络中节点相互独立,(,下面两个定义等价,),：,(1),给定父节点，一个节点与它的非后代节点是条件独立的,(2),给定一个节点的父节点、子节点以及子节点的父节点,(Markov blanket),，这个节点对于其它节点都是条件独立的,图示,第,7,章 不精确推理,42,条件独立关系图示,第,7,章 不精确推理,U1,Um,X,Z1j,Znj,Y1,Yn,U1,Um,X,Z1j,Znj,Y1,Yn,43,噪声或关系,(1),贝叶斯网络中尽管父节点个数,k,很小，但是要完成条件概率表仍需要,O(2,k,),数据,如果找到了变量依赖的“噪声”逻辑关系，则可以用,O(k),个参数完成条件概率表,噪声或,(noisy-OR),关系用于刻画不确定关系，使逻辑或的推广,噪声或关系考虑到每个父节点引起子节点为真的能力的不确定性,第,7,章 不精确推理,44,噪声或关系,(2),这种不确定性用一个例子表示：,发烧,(fever),为真，当且仅当以下三者之一为真,感冒,(cold)/,流感,(flu)/,疟疾,(malaria),但是可能病人得了以上疾病却没有发烧症状，这就是父节点为真其子节点未必真的不确定性,即父子关系被抑制,此时可以认为：,fever,为假当且仅当所有为真的,父节点被抑制，其概率为每个父节点被抑制的概率的乘积,第,7,章 不精确推理,45,噪声或关系,(3),假设每个单独抑制的概率如下,P(,fever,|cold,flu,malaria,)=0.6P(,fever,|,cold,flu,malaria,)=0.2P(,fever,|,cold,flu,malaria,)=0.1,则可以建立一个完整的条件概率表,/,大大减少了所需参数，成为一种有效表示,如,P(,fever,|,cold,flu,malaria,)=0.2*0.1=0.02P(,fever,|cold,flu,malaria,)=0.6*0.2*0.1=0.012 P(,fever,|cold,flu,malaria,)=1-0.012=0.988,第,7,章 不精确推理,46,6.3.2,贝叶斯网络中的精确推理,概率推理系统中的基本任务是计算被查询变量的后验概率,设,X,为待查询变量,/e,为观察到的证据,/E=E1Em,证据变量集合,/Y=Y1Yn,非证据变量集合,(,也称隐变量,),全部变量集合,=X,E,Y,推理的任务是：求,后验概率,P(X|e),实际上，根据边缘化规则可得,P(X|e)=,P(X,e)=,y,P,(,X,e,y,),第,7,章 不精确推理,47,查询实例,(1),上式表明：在贝叶斯网络中计算条件概率的乘积并求和，以便回答查询,以防盗警报为例，求,P(B|JohnCalls=T,M=F),证据,JohnCalls=True/MaryCalls=False,查询变量,Burglary=True,隐含变量,Earthquake/Alarm,用首字母简化式有：,P(b|j,m,)=,P(b,j,m,)=,E,A,P(b,E,A,j,m),第,7,章 不精确推理,48,查询实例,(2),进一步代入条件概率：,P(b|j,m),=,E,A,P(b)P(E)P(A|b,e)P(j|A)P(,m|A,),上式最坏复杂度仍然是,O(n2,n,),对所有变量求和,改进,将相对常数移到求和符号以外,P(b|j,m),=,P(b),E,P(E),A,P(A|b,E)P(j|A)P(,m|A,),计算过程,(,遍历,A=a/,a,和,E=e/,e),P(j|a)=0.90P(,m|a,)=0.30,P(j|,a,)=0.05P(,m,|,a,)=0.99,P(a|b,e)=0.95P(,a|b,e)=0.05,P(,a|b,e,)=0.94P(,a|b,e,)=0.06,第,7,章 不精确推理,49,查询实例,(3),乘积求和过程,E,P(E),A,P(A|b,E)P(j|A)P(,m|A,)=P(e)*,A,P(A|b,e)P(j|A)P(,m|A,)+P(,e,)*,A,P(A|b,e)P(j|A)P(,m|A,)=P(e)*P(a|b,e)*P(j|a)*P(,m|a,)+P(,a|b,e)*P(j|,a)*P(,m|a,)+P(,e,)*P(a|b,e)*P(j|a)*P(,m|a,)+P(,a|b,e)*P(j|,a)*P(,m|a,)=0.002*0.95*0.90*0.30+0.05*0.05*0.99+0.998*0.94*0.90*0.30+0.06*0.05*0.99=0.002*0.2565+0.0025+0.998*0.2538+0.0030=0.002*0.2590+0.998*0.2568=0.2568,第,7,章 不精确推理,50,查询实例,(4),相应地有,P(b|j,m),=,P(b)*,0.2568=,0.001*0.2568=,*0.0002568,类似地有,P(,b|j,m),=,*P(,b,),E,P(E),A,P(A|,b,E)P(j|A)P(,m|A,)=,*P(,b,)*0.002*(0.0783+0.0351)+0.998*(0.0003+0.0495)=,*0.999*0.0499=,*0.0499,归一化以后有,P(B|j,m,)=,=,只有,John,打电话而出现盗贼的概率小于,1/100,第,7,章 不精确推理,51,变量消元法,(1),在计算中我们发现,P(j|a)*P(,m|a,),和,P(j|,a)*P(,m|a,),重复计算了两次，如何消除重复？只要保留一次计算结果既可,(,动态规划,),通过点积,(pointwise product),求和的方法消去隐含变量,二元向量,f,M,(A)=P(m|a)P(m|,a),T,消去,A,：,f,AJM,(B,E)=,f,A,(a,B,E)*,f,J,(a)*,f,M,(a)=,f,A,(a,B,E)*,f,J,(a)*,f,M,(a)+,f,A,(,a,B,E)*,f,J,(,a)*,f,M,(,a),第,7,章 不精确推理,52,变量消元法,(2),在这样的计算中只要做：,计算两个因子的点积,在因子乘积中对一个变量求和消元,由此消除了重复计算,在计算中，消除以下无关节点：,删除不是查询变量也非证据变量的叶节点,删除所有不是查询变量祖先也不是证据变量祖先的节点,第,7,章 不精确推理,53,精确推理的复杂度,单连通结构,贝叶斯网络中任何两个节点都至多只有一条无向路径相连,此时，单连通上的精确推理的时间和空间复杂度都和网络规模呈线性关系,而对于多连通结构,(,见下图,),，最坏情况下变量消元法可能具有指数级的时空复杂度,此时贝叶斯网络的推理是一个,NP,问题,所以要寻找多连通网络中的近似算法,第,7,章 不精确推理,54,多连通网络,第,7,章 不精确推理,S R P(W),T T .99,T F .90,F T .90,F F .00,C P(R),T .80,F .20,sprinkler,Rain,Wet grass,C P(S),T .10,F .50,P(C)=.5,cloudy,55,6.3.3,贝叶斯网络的近似推理,大规模多连通网络的精确推理是不可操作的，所以要考虑近似的推理方法,采用随机采样方法，也称蒙特卡罗算法,(Monte Carlo algorithm),：给出问题的近似解答，近似的精度依赖于所生成采样点的多少,此处近似的含义,不是通过计算求出网络中某个点的条件概率,(,因为复杂度高,),，而是对该事件进行采样而获得概率,第,7,章 不精确推理,56,后验概率计算的采样方法,有两类采样方法：,直接采样方法,计算样本的频率,马尔科夫链采样方法,根据马尔科夫覆盖中的变量当前值来采样,直接采样方法,依据已知概率来生成样本,拒绝采样算法,/,似然加权算法,马尔科夫链采样方法,证据变量概率固定条件下随机生成样本,第,7,章 不精确推理,57,直接采样方法,直接采样方法是按照拓扑结构次序依次对每个变量进行采样，被采样变量值的概率分布依赖于父节点已取得的赋值,具体实现：,拒绝采样算法,首先按照先验概率分布采样，然后排除所有与证据不匹配的样本，最后计算样本频率,似然加权,证据变量的值用权值,(,条件概率,),来表示，只对非证据变量进行采样,第,7,章 不精确推理,58,采样样本与概率分布,样本的向量表示,cloudy,sprinkler,rain,wetGrass,F/T,或者,0/,1,表示为假或为真,/,如,T,F,T,T,采样按照已知概率分布进行，但不是等于这个概率分布值，而是说分布与之相符,cloudy=0.5,0.5/,第,1,次采样,49/51,，第,2,次采样,52/48,如此等等,每次采样应该在一定的条件下,(,这就是条件概率,),进行，不满足条件的样本不再考虑,第,7,章 不精确推理,59,采样过程举例,(1),通过例子说明采样过程,/,算法均省略,(1),因为,P(cloudy)=,故,cloudy,的采样样本,T/F,各占,50%,，假设,(,不妨,),返回,T,(2)P(sprinkler|cloudy=T)=,，故,sprinkler,的采样样本,T/F,各占,10%,和,90%,，应该返回,F,注意：此时采样样本均为,形式，其中,占,10%,，,占,90%,(3)P(rain|cloudy=T)=,，故,rain,的采样样本,T/F,各占,80%,和,20%,应该返回,T/,样本形式类似于,(2),第,7,章 不精确推理,60,采样过程举例,(2),(4)P(wetGrass|sprinkler=F,rain=T)=,，则返回,T/,采样样本形式,占,90%,，,占,10%,实际上如此生成的样本完全符合先验概率，即,对于上例，,cloudy sprinkler rain wetGrass=T F T T=0.5*0.9*0.8*0.9=0.324,第,7,章 不精确推理,61,拒绝采样方法,从已知分布的采样出发,(,其计算如上,),，通过去掉不满足证据条件的样本来计算,(,估计,),那些未知分布的事件的概率,例子：,P(Rain|Sprinkler=T),未知其概率,/,采样,100,个样本,其中,73,个为,，不满足前提条件,余下的,27,个中,8,个为,rain=T/19,个为,rain=F,P(Rain|Sprinkler=T)=,=,拒绝采样方法的最大问题就是效率比较低,第,7,章 不精确推理,62,一致的估计,拒绝采样方法能产生真实概率的一致估计,估计的概率在无限多,(,大量样本的极限,),条件下成为精确值，这样的估计称为一致的,(consistent),，即,P(x,1,x,m,)=N,PS,(x,1,x,m,)/N,第,7,章 不精确推理,63,似然加权方法,(1),对证据节点的概率进行似然加权，即按照先验概率的乘积进行计算,/,对非证据节点进行采样，采样样本服从先验概率分布,例子：求,P(rain|sprinkler=T,wetGrass=T),的概率,采样过程如下：,(1),权值,w=1.0,(2),P(cloudy)=,，据此采样，返回,T,(3)Sprinkler,是证据变量，取值,T,，则,ww*P(sprinkler=T|cloudy=T)=1.0*0.1=0.1,第,7,章 不精确推理,64,似然加权方法,(2),(4)P(rain|cloudy=T)=,，据此进行采样，假设,=T,(5)wetGrass,是证据变量，取值,T,，则有,ww*P(wetGrass=T|sprinkler=T,rain=T)=0.1*0.99=0.099,此即,cloudy sprinkler rain wetGrass=T T T T=0.099/,解释：,sprinkler=T&wetGrass=T,条件下,rain=T,的概率很低,似然加权方法也得到对于真实概率的一致估计,/,从采样与加权的乘积去理解联合分布概率的计算，依然是全部条件概率的乘积,第,7,章 不精确推理,65,马尔科夫链采样,(1),直接采样法按照先验概率去采样,马尔科夫链采样对证据变量以外的变量每次随机地采样,举例：考虑求,P(rain|sprinkler=T,wetGrass=T),证据变量固定,sprinkler=T/wetGrass=T,隐变量,cloudy/rain,则随机采样,初始值不妨假设,cloudy=T/rain=F,初始状态,=,第,7,章 不精确推理,66,马尔科夫链采样,(2),然后反复按照以下,2,个步骤采样,(1),当前条件下,对,cloudy,随机采样，结果,=,(2),当前条件下,对,rain,随机采样，结果,=,最后得到若干样本，例如,rain=T=20/rain=F=60,，则,P(rain|sprinkler=T,wetGrass=T)=,=(?),第,7,章 不精确推理,67,马尔科夫链采样的合理性,(1),马尔科夫链,采样过程最终会进入“动态平衡,”,状态,被采样变量服从马尔科夫覆盖下的条件概率分布，且“稳态分布”,=,真实后验概率,P(x|e),我们所需要求解的正是给定证据变量,e,下某个变量的概率值,P(x|e),证明过程：,转移概率,状态,x,到状态,xq(x,x),时刻,t,处于状态,x,的概率,t,(x),第,7,章 不精确推理,68,马尔科夫链采样的合理性,(2),下一时刻处于状态,x,的概率,t+1,(x)=,x,t,(x),q(x,x),稳态分布,(stationary distribution),当,t+1,(x)=,t,(x),时，马尔科夫链达到稳态分布，即,(,省略,t),(x)=,x,(x),q(x,x),对于所有,x,细致平衡,任意两个状态间沿两个方向转换概率相等,(x),q(x,x)=,(x),q(x,x),对于所有,x,x,简单公式推导,(,求和,),可证明细,致平衡中蕴含着稳态分布,第,7,章 不精确推理,69,马尔科夫链采样的合理性,(3),前述马尔科夫链采样过程称为,Gibbs,采样器，其转移概率写为：,q(x,x)=q(x,i,x,i,),(x,i,x,i,)=P(x,i,|x,i,e),由此证明满足细致平衡,(p398),，也就是稳态分布,而,P(x,i,|x,i,e),正是所求的贝叶斯网络中条件概率,最终每个时刻的状态概率值都相同,第,7,章 不精确推理,70,7.4,可信度方法*,7.4.1,可信度定义与性质,7.4.2,证据不确定下,CF,的计算,7.4.3,可信度推理例子,第,7,章 不精确推理,71,6.4,可信度方法,可信度方法的原则,Mycin,系统设计时考虑了如下一些原则：,(1),用接近统计理论的近似方法；,(2),用专家经验估计代替统计数据；,(3),尽量减少经验估计；,(4),适用于证据增量式增加的情况；,(5),数据的轻微扰动不影响最终的推理结论,证据理论是其基础,(Dempster-Shafer),第,7,章 不精确推理,72,确认理论为基础,以确认理论为基础，和概率理论的区别：,设,E,为证据，,H,为假设，则概率论公式为,P(H|E)+P(H|E)=1,CF(certainty factor),表示确认理论下的定量可信度，则有公式,CF(H|E)+CF(H|E)=0,含义：,E,肯定了,H(=1),就同时否定了,H(=,-,1),第,7,章 不精确推理,73,肯定和否定的程度,用两个量来表示在给定证据下，对某个假设的肯定和否定的程度,表示：,MB(measure belief)/MD(disbelief),含义：,MB(H|E)=a,证据,E,的出现使假设,H,的可信度增加了数量,a/MD(H|E)=b,证据,E,的出现使假设,H,的不可信度增加了数量,b,显然,a/b,不能同时大于,0,CF(H|E)=MB(H|E),-,MD(H|E),第,7,章 不精确推理,74,6.4.1,可信度定义与性质,MB,和,MD,的解释：其值应该由专家给出,/,但为了提供某种理论依据，给出其概率解释，,一般不直接用于构造知识库,第,7,章 不精确推理,75,有关性质,(1),MB,和,MD,的性质,(1),由定义，当,p(H)=1,时,MB(H|E)=p(H|E)=1 MD(H|E)=p(H|E)=0,(2),由定义，当,p(H)=1,时,MB(H|E)=p(H|E)=0 MD(H|E)=p(H|E)=1,(3),恒有,0MB(H|E),，,MD(H|E)1,(4),互斥性：当,MB(H|E)0,时,MD(H|E)=0,当,MD(H|E)0,时,MB(H|E)=0,即恒有,MB(H|E)*MD(H|E)=0,(5),若,MB(H|E)=1,时则对任何,E,有,MD(H|E)=0,；反之，若,MD(H|E)=1,时则对任何,E,有,MB(H|E)=0,第,7,章 不精确推理,76,有关性质,(2),复合证据的处理,(1)MB(H|E1&E2)=MB(H|E1)+MB(H|E2),-,MB(H|E1)*MB(H|E2),MD(H|E1&E2)=MD(H|E1)+MD(H|E2),-,MD(H|E1)*MD(H|E2),多于,2,个证据的，可以进一步组合,(E1&E2)&E3.,(2)MB(H|E1&E2)=MB(H|E1)MD(H|E1&E2)=MD(H|E1),其中,E2,为未知真假的证据,第,7,章 不精确推理,77,CF,定义与性质,可信度因子,CF(H|E)=MB(H|E),-,MD(H|E),根据,MB/MD,的互斥性知，,CF,只取,MB,或,MD,之一值,性质：,(1)-1CF(H|E)1,(2)CF(H|E)+CF(H|E)=0,(3),令,E+=E1&En,为所有支持,H,的证据总和(即,MB(H|Ei)0)/E,-,=E,1,&E,m,为所有不支持,H,的证据总和,(,即,MD(H|E,j,)0),CF(H|E+&E,-,)=MB(H|E+),-,MD(H|E,-,),第,7,章 不精确推理,78,CF,性质,当多个证据导出同一假设时，先求出各自,MB/MD,然后利用复合证据处理公式得出总的,MB/MD,，再得到,CF,(4),若,H1,Hk,是,k,个互相独立的假设，,E,为对其有利的证据，则,第,7,章 不精确推理,79,6.4.2,证据不确定下的,CF,计算,不确定证据下,CF,的计算,证据,E,本身不确定，其可信度用,CF(E),或,CF(E|S),表示，,S,是证据,E,的观察,/,有性质如下：,(1),当证据,E,以某种程度为真时，,0CF(E)1,以某种程度为假时，,-,1CF(E)0,(2),证据,E,肯定真时,CF(E)=1,证据肯定假时,CF(E)=,-,1,对证据一无所知时,CF(E)=0,第,7,章 不精确推理,80,证据的,CF,计算,(1),CF,对复合证据的处理：同,MB/MD,的定义,(1)CF(H|E1&E2)=CF(H|E1)+CF(H|E2),CF(H|E1)*CF(H|E2),(2)CF(H|E1&E2)=CF(H|E1),其中,E2,为未知真假的证据,证据的合取与析取,(1)E=E1 and and En,CF(E1and and En)=minCF(E1),CF(En),(2)E=E1 or or En,CF(E1 or or En)=maxCF(E1),CF(En),第,7,章 不精确推理,81,证据的,CF,计算,(2),由证据与规则的可信度求假设的可信度,CF(H|S)=CF(H|E),max0,CF(E)(CF(E)0,时,则不能应用,),MB(H|S)=MB(H|E),max0,CF(E),MD(H|S)=MD(H|E),max0,CF(E),第,7,章 不精确推理,82,可信度阈值,可信度阈值的设定,为了使专家数据的轻微扰动不影响推理结论，,Mycin,系统,设置了最低阈值,0.2,，即只有,CF0.2,的证据才对信念函数,MB/MD,起作用,由此补充对假设可信度的计算,(1)MB(H|E)=0,如果,MD(H|E)=1,或,CF(E)0.2,(2)MD(H|E)=0,如果,MB(H|E)=1,或,CF(E)0.2,(3)MB/MD/CF(H|S)=MB/MD/CF(H|E)*CF(E),如果,CF(E)0.2,否则为0,第,7,章 不精确推理,83,6.4.3,可信度推理例子,推理规则形式,:=,设有推理网络如下图所示，其推理规则为,(1)ABH,0.7(2)CH,0.5,(3)(DE)F(GI)H,0.9(4)JH,0.3,每个证据的可信度标在叶子节点的下面，节点分叉带弧者为与节点,第,7,章 不精确推理,84,推理网络,第,7,章 不精确推理