AI第3章--不确定性推理2ppt课件

1、人工智能人工智能主讲教师：主讲教师：李李 娜娜 娜娜 Instructor: Li Nana : 第五章 不确定性推理n概述n可信度方法 (确定性方法)n主观Bayes方法n证据理论第五章 不确定性推理n概述n确定性方法(可信度方法)n主观Bayes方法n证据理论概述-不确定推理的概念n推理：从已知事实出发，运用相关知识推理：从已知事实出发，运用相关知识( (或规则或规则) )逐步逐步推出结论或者证明某个假设成立或不成立的思维过程。推出结论或者证明某个假设成立或不成立的思维过程。已知事实是推理过程的出发点即推理中使用的知识，已知事实是推理过程的出发点即推

2、理中使用的知识， 我们把它称为证据。我们把它称为证据。n不确定推理：从具有不确定性的证据出发，运用不确不确定推理：从具有不确定性的证据出发，运用不确定性的知识定性的知识( (或规则或规则) )，最终推出具有一定程度的不确，最终推出具有一定程度的不确定性，但却是合理的或近乎合理的结论的思维过程。定性，但却是合理的或近乎合理的结论的思维过程。概述-不确定性的主要表现n1、证据的不确定性n观察度量的不确定性n证据表示的不确定性n多个不确定证据合成时表现出来的不确定性n2、规则的不确定性n3、结论的不确定性E1HE2H概述不确定推理中的基本问题n不确定性的表示不确定性的表示n单个证据的不确定性表示单个

3、证据的不确定性表示n 证据的来源：证据的来源：n (1) (1)初始证据初始证据: :通过观察而得到的，由于观察本身通过观察而得到的，由于观察本身的不精确性，因此所得的初始证据具有不确定性；的不精确性，因此所得的初始证据具有不确定性；n (2) (2)间接证据间接证据: :在推理过程中利用前面推理出的结在推理过程中利用前面推理出的结论作为当前新的推理证据。论作为当前新的推理证据。n 证据不确定性的表示通常为一个数值，用以表证据不确定性的表示通常为一个数值，用以表示相应证据的不确定性程度。示相应证据的不确定性程度。n (1) (1)对于由观察得到的证据，其值一般由用户或对于由观察得到的证据，其值

4、一般由用户或专家给出专家给出; ;n (2) (2)对于用前面推理所得结论作为当前推理的证对于用前面推理所得结论作为当前推理的证据，其值则是由推理中的不确定性传递算法计算得到。据，其值则是由推理中的不确定性传递算法计算得到。n组合证据的不确定性表示组合证据的不确定性表示n 证据不止一个，而是几个，这几个证据间可能是证据不止一个，而是几个，这几个证据间可能是andand或或oror的关系，假设的关系，假设C(E1)C(E1)表示证据表示证据E1E1的不确定性程的不确定性程度，度， C(E2) C(E2)表示证据表示证据E2E2的不确定性程度，如何由的不确定性程度，如何由C(E1)C(E1)和和C

5、(E2)C(E2)来计算来计算C(E1E2)C(E1E2)和和C(E1E2)C(E1E2)概述不确定推理中的基本问题规则的不确定性表示规则的不确定性表示 规则不确定性要由领域专家给出，以一个数值表示，该数规则不确定性要由领域专家给出，以一个数值表示，该数值表示了相应知识的不确定性程度。值表示了相应知识的不确定性程度。推理计算推理计算结论的不确定性表示结论的不确定性表示不确定性传递问题：不确定性传递问题： 已知证据已知证据E E的不确定性度量为的不确定性度量为C(E)C(E)，而规则，而规则E HE H的不确定的不确定性度量为性度量为CF(H,E)CF(H,E)，那么如何计算结论，那么如何计算结

6、论H H的不确定性程度的不确定性程度C(H)C(H)，即，即如何将证据如何将证据E E的不确定和规则的不确定和规则E HE H的不确定性传递到结论的不确定性传递到结论H H上。上。结论不确定性的合成问题：结论不确定性的合成问题： 如果有两个证据分别由两条规则支持结论，如何根据这两如果有两个证据分别由两条规则支持结论，如何根据这两个证据和两条规则的不确定性确定结论的不确定性。即已知个证据和两条规则的不确定性确定结论的不确定性。即已知 E1 H C(E1),CF(H,E1) E1 H C(E1),CF(H,E1) E2 H C(E2),CF(H,E2) E2 H C(E2),CF(H,E2) 如何

7、计算如何计算C(H)C(H)概述-分类1）不确定性推理方法控制方法模型方法数值方法非数值方法基于概率的方法模糊推理方法可信度方法主观Bayes方法证据理论方法第五章 不确定性推理n概述n可信度方法(确定性方法)n主观Bayes方法n证据理论可信度方法确定性方法）nMYCIN系统研制过程中产生的不确定推理方法,第一个采用了不确定推理逻辑，70年代很有名。它是不确定推理方法中应用最早、且简单有效的方法之一。可信度方法n可信度：人们在实际生活中根据自己的经验或观察对可信度：人们在实际生活中根据自己的经验或观察对某一事件或现象为真的相信程度某一事件或现象为真的相信程度, ,也称为确定度因子。也称为确定

8、度因子。n可信度具有较大的主观性和经验性。但是，对某一具可信度具有较大的主观性和经验性。但是，对某一具体领域而言，由于该领域专家具有丰富的专业知识及体领域而言，由于该领域专家具有丰富的专业知识及实践经验，要给出该领域知识的可信度还是完全有可实践经验，要给出该领域知识的可信度还是完全有可能的。能的。n可信度(确定性)方法n证据前提的不确定性表示n规则的不确定性表示n推理计算-结论的不确定性表示确定性(可信度)方法证据的不确定性度量n单个证据的不确定性获取方法：两种n初始证据：由提供证据的用户直接指定，用可信度因子对证据的不确定性进行表示。如证据E的可信度表示为CF(E)。n 如对它的所有观测都能

9、肯定为真，则使CF(E)=1；如能肯定为假，则使CF(E)=-1；若它以某种程度为真，则使其取小于1的正值，即0 CF(E)1;若它以某种程度为假，则使其取大于-1的负值，即-1 CF(E)0，并且这种支持的力度越大，就使CF(H, E)的值越大，相反，如果证据E的出现，使结论H为假的可信度增加，则使CF(H, E)0，并且这种支持的力度越大，就使CF(H, E)的值越小；若证据的出现与否和H无关，则使CF(H, E)=0。nP(H|E)=1nP(H|E)=0nP(H|E)=P(H)P(H)E)|P(H , P(H)P(H)-E)|P(HP(H)E)|P(H , P(H)1P(H)-E)|P(

10、HE) CF(H,当当n规则n规则的不确定性表示n证据前提的不确定性表示n推理计算结论的不确定性表示 确定性方法规则 (推理计算 1）n从不确定的初始证据出发，通过运用相关的不确定知识，最终推出结论并求出结论的可信度值。n最简单的情形：只有单条规则-不确定性传递问题n例如 由E， E H，求 H。已知证据E的可信度CF(E )和规则CF(H, E )的可信度，则结论H的可信度计算公式为：n CF(H) =max0,CF(E )CF(H, E )n (CF(E )0 时CF(H) =0,说明在该模型中没有考虑证据为假时对结论H的影响。)规则 (推理计算 2）n多条知识支持同一结论时-结论不确定性

11、的合成问题n设有如下知识：if E1 then H； if E2 then H；n1)利用上式分别计算每一条知识的结论可信度CF(H)n CF1(H) =max0,CF(E1 )CF(H,E1 )n CF2(H) =max0,CF(E2)CF(H,E2 )n2)用下式合成CF1(H) 、CF(H) ，求可信度 CF12(H) n符号不同与当当 当(H)CF(H)CF |(H)CF| , |(H)CFmin|-1(H)CF(H)CF0(H)CF0(H)CF (H)CF (H)CF(H)CF(H)CF0(H)CF0(H)CF (H)CF (H)CF-(H)CF(H)CF(H)CF212121212

12、12121212112，例题例题n知：R1：A1B1CFB1，A1）0.8n R2：A2B1 CFB1，A2）0.5n R3：B1A3B2CFB2，B1A3）0.8nCFA1）CFA2）CFA3）1；而对B1和B2一无所知；n计算 CFB2）n本题可图示为A1A2B1A3B2B1An解：依规则R1，nCF1B1）n CFB1，A1）max0, CFA1）0.8，n依规则R2：n CF2B1）n CFB1，A2）max0, CFA2）0.5，n利用合成算法计算B的综合可信度：nCF1( B1)CF1( B1) CF( B) CF1( B1)CF( B)0.9 n依R3，先计算

13、nCFB1A3）n minCFA3），CFB1）0.9n CFB2）= n C F ( B 2 ， B 1 A 3 ) m a x 0 , C F B 1 A 3 ） =0.90.8=0.72n答：CFB1）0.9，CFB2）0.72A1A2B1A3B2B1An例 设有一组知识:n解：规则 (推理计算 3）n已知结论原始可信度的情况下，结论可信度的更新计算方法。n即已知规则E H 的可信度为CF(E,H )，证据E的可信度为CF(E)，同时已知结论H原来的可信度为CF(H)，如何求在证据E下结论 H可信度的更新值CF(H/E) ：规则 (推理计算 4）nCF(E) =0，n

14、 规则E H不可使用，即此计算不必进行。n0 CF(E) 0，使用公式n 由规则r1得到X的可信度更新值为：n CF(X/A)n =CF0(X)+ CF(A) CF(X,A)- CF0(X) CF(A) CF(X,A)n =0.1+0.5X0.8- 0.1X0.5X0.8=0.46n 由规则r2得到X的可信度更新值为：n CF(X/A,B)n =CF(X/A)+ CF(B) CF(X,B)- CF(X/A) CF(B) CF(X,B)n =0.622n 由规则r3得到X的可信度更新值为：n CF(X/A,B,C)n =CF(X/A,B)+ CF(C) CF(X,C)- CF(X/A,B) CF

15、(C) CF(X,C)n =0.698nCF(X/A,B,C)即是X的可信度更新值。ABCX(0.1)DXDY(0.2)0.80.6 0.40.3主观贝叶斯方法(概述）贝叶斯公式：设事件H1, Hn是彼此独立、互不相容的事件，则有：在贝叶斯公式中，P(Hi), i=1, 2, , n称为先验概率，而P(Hi|E) i=1, 2, , n称为后验概率. P(E)H)P(H)|P(EE)|P(HE)|P(Hin 1in1jjjii)P(HH|P(E)P(HH|P(En例:n一个病人发热(E)，问他患感冒(Hi) 的概率是多少？即求E)|P(HiE)|P(Hi感冒时发感冒时发热的概率热的概率患者感患

16、者感冒的概冒的概率率发热发热的概的概率率n1jjjii)P(HH|P(E)P(HH|P(E)()P(HH|P(EiiEP主观贝叶斯方法(概述）n直接根据贝叶斯公式进行推理计算简单明了，但是它要求结论Hi相互独立，实际上难以保证。而且P(E| Hi)的计算通常比较困难。所以在求解不确定性推理问题时，还不能直接使用贝叶斯公式，而是使用对其经过改进的主观贝叶斯公式。n1976年提出的，在地矿勘探系统中得到成功的应用。是对概率中基本贝叶斯公式的改进。n主观贝叶斯方法n证据前提的不确定性表示n规则的不确定性表示n推理计算-结论的不确定性表示主观贝叶斯方法主观贝叶斯方法(概述）n证据的不确定性表示n 单个

17、证据：在主观贝叶斯方法中，证据的不确定性用概率表示。例如，对于初始证据E，其先验概率为P(E)。n 组合证据n当证据是多个单一证据的合取时，即E= E1 and E2andandEnn 若各证据的可信度分别为P(E1), P(En), 则P(E ) = min P(E1), P(En)n当证据是多个单一证据的析取时，即E= E1orE2 ororEnn 若各证据的可信度分别为P(E1), P(En),则P(E ) = max P(E1), P(En)n当证据是某一证据的非时，即E= A；n 则P(E ) =1-P(A )n主观贝叶斯方法n证据前提的不确定性表示n规则的不确定性表示n推理计算-结

18、论的不确定性表示主观贝叶斯方法主观贝叶斯方法(概述）n规则的不确定性表示n 在主观贝叶斯方法，规则的不确定性是以一个数值对(LS,LN)来进行描述的。nIF E THEN (LS,LN) H (P(H)n取值范围n取值范围n它们的具体取值由领域专家根据实际经验给出。nH)|P(EH)|P(ELS规则的充分性度量规则的充分性度量: :表示表示E E为真时，对为真时，对H H的影响。的影响。H)|EP(H)|EP(LN 规则的必要性度量规则的必要性度量: :表示表示E E为假时，对为假时，对H H的影响。的影响。H为真时E出现的概率除以H为假时E出现的概率H为真时E不出现的概率除以H为假时E不出现

19、的概率n主观贝叶斯方法n证据前提的不确定性表示n规则的不确定性表示n推理计算-结论的不确定性表示主观贝叶斯方法主观贝叶斯方法n推理计算推理计算不确定性的传递：不确定性的传递：n 1 1已知规则已知规则EHEH的的(LS,LN)(LS,LN)和和P(H)P(H)、 P(E) P(E)，如何，如何计算计算P(H/E)P(H/E)或或P(H/P(H/E)E)n n n 这里存在三种情况：证据这里存在三种情况：证据E E肯定存在、肯定不存肯定存在、肯定不存在或以某种程度存在。在或以某种程度存在。n n )/()/()(,),(EHPorEHPHPLNLSEPn(1)证据E肯定存在，即P(E)=1时：n

20、 n n 由基本贝叶斯公式，可得：n 两式相除得：)()()/()/()/()/(HPHPHEPHEPEHPEHP)/(EHP)/(EHP)()/(HPHEP)()/(HPHEP)(1)(HPHPLS)()()|(EPHPHEP)()()|(EPHPHEP)/()(,EHPHPLNLS主观贝叶斯方法(概述）n几率函数O(X)n n 数学证明，O(x)与P(x)有相同的单调性P(X)-1P(X)X)P(P(X)O(X)(1)()(XOXOXP)(1)()/()/(HPHPLSEHPEHP)()/(HOLSEHO)/(EHPE肯定出现的情况下，肯定出现的情况下，H的先验几率更新为的先验几率更新为后

21、验几率的公式后验几率的公式E肯定出现的情况下，肯定出现的情况下，H的先验概率更新为的先验概率更新为后验概率的公式后验概率的公式1)() 1()(HPLSHPLSn讨论LS对后验概率的影响n(1)LS1n O(H/E)O(H)，即n P(H/E)P(H)n(2) LS=1n O(H/E)=O(H)n(3)0LS1n O(H/E)1，且越大越好。)()/(HOLSEHOE的存在，使的存在，使H为真的概为真的概率增加，且率增加，且LS越大，越大，P(H/E)越大，表明越大，表明E对对H为真的支持越强。为真的支持越强。E与与H无关。无关。E的出现使的出现使H为为真的可能性下降。真的可能性下降。E的出现

22、使的出现使H为为假。假。n(2)证据E肯定不存在，即P(E)=0时：n n P(E)=1，由贝叶斯公式，可得：n 两式相除得：)()()/()/()/()/(HPHPHEPHEPEHPEHP)/(EHP)/(EHP)()/(HPHEP)()/(HPHEP)(1)(HPHPLN)()()|(EPHPHEP)()()|(EPHPHEP)/()(,EHPHPLNLS主观贝叶斯方法(概述）n n )()()/()/(HPHPLNEHPEHP)()/(HOLNEHO)/(EHPE肯定不出现的情况肯定不出现的情况下，下，H的先验几率更的先验几率更新为后验几率的公式新为后验几率的公式E肯定不出现的情况肯定不

23、出现的情况下，下，H的先验概率更的先验概率更新为后验概率的公式新为后验概率的公式1)() 1()(HPLNHPLNn讨论LN对后验概率的影响n(1)LN1n O(H/E)O(H)，即n P(H/E)P(H)n(2)LN=1n O(H/E)=O(H)n(3)0LN1n O(H/E)1|A|1或或|A|=0|A|=0，则，则M(A)=0M(A)=0n例例1)(1niisMniisM1)(证据理论 (Evident Theory)概述证据的不确定性表示规则的不确定性推理计算证据理论 (证据的不确定性)n对于不确定性证据E，其不确定性用信任函数f(E)表示n 1)当E是初始的简单证据时，其信任度f(E

24、)由用户给出；n 2)当E是前面推理所得结论，又要作为当前推理的证据时，其信任度f(E)由推理计算得到；n 3当证据E由多个证据组合而成时，其信任度f(E)由下列方法求取。如果E= E1 and E2 andand En，则f(E)= min f(E1), f(E2), f(En)；如果E= E1 or E2 oror En，则f(E)= max f(E1), f(E2 ), f(En)证据理论概述证据的不确定性规则的不确定性推理计算证据理论 (规则的不确定性)n不确定性知识用如下形式的规则表示n IF E THEN H=h1,hn CF=c1,cnn n CF是该条知识的可信度因子，用集合形

25、式表示，其中ci用来表示指出由E得到hi的可信度， ci与hi对应。证据理论概述证据的不确定性规则的不确定性推理计算证据理论 (推理计算)n推理计算模型：n已知IF E THEN H=h1,hn CF=c1,cn，E的信任度为f(E)，|H| |U|.求结论H的信任度f(H)n第一步：求出H的特定概率分配函数, 对于上述知识，H的概率分配函数n m(h1)=f(E)c1n m(h2)=f(E)c2n n m(hn)=f(E)cnn m(U)=1- f(E)c1-f(E)c2-f(E)cnn第二步：求出H的信任函数Bel(H)和似然函数PI(H)n第三步：求结论H的信任度f(H)n )()(|)

26、()(HBelHPIUHHBelHf例题nM(D)=1-0.18-0.3=0.52ABM(A)Pl(B)=M(b1)+M(b2)+M(D)=1作业 n设有以下规则：证据理论 (推理计算)n如果两条知识支持同一结论H，即n IF E1 THEN H=h1,hn CF=c1,cn，n IF E2 THEN H=h1,hn CF=c1,cn，nm1, m2在U上的合成-概率分配函数的合成运算 n定义：m = m1 m2 n规定：m() = 0 ，n m(A) = n其中 K11n且 K1 0。n若K1 0，认为m1，m2矛盾，没有联合基本概率分配函数 。AYX21)Y(m)X(mKYX21YX21)

27、Y(m)X(m)Y(m)X(mn推理计算模型：n如果两条知识支持同一结论H，即n IF E1 THEN H=h1,hn CF=c1,cn，n IF E2 THEN H=h1,hn CF=c1,cn，n第一步：分别对每一条知识求出概率分配函数, n m1(h1,hn)和m2(h1,hn)n然后再用公式m=m1 m2 求m1和m2的正交和，即可得到结论H的概n率分配函数m.n第二步：求出H的信任函数Bel(H)和似然函数PI(H)n第三步：求结论H的信任度f(H)n 例题n知：f1(A1) = 0.40 ,f1(A2)=0.50,|U| = 20.nA1B=b1,b2,b3，(c1,c2,c3)=

28、(0.1,0.2,0.3)nA2B=b1,b2,b3，(c1,c2,c3)=(0.5,0.2,0.1)n求：f1(B)n解：（先求：m1(b1,b2,b3)n=(0.4*0.1,0.4*0.2,0.4*0.3)=(0.04,0.08,0.12);nm1(U)n =1- m1(b1)+m1(b2)+m1(b3)=0.76;nm2(b1,b2,b3)n=(0.5*0.5,0.5*0.2,0.5*0.1)=(0.25,0.10,0.05);nm2(U)n=1- m2(b1)+m2(b2)+m2(b3)=0.70;例题n求m =m1 m2n 1/Kn =m1(b1)*m2(b1)+ m1(b1)*m2

29、(U)+ m1(b2)*m2(b2)+ m1(b2)*m2(U)+ m1(b3)*m2(b3)+ m1(b3)*m2(U)+ m1(U)*m2(b1)+ m1(U)*m2(b2)+ m1(U)*m2(b3)+ m1(U)*m2(U)n=0.01+0.028+0.008+0.056+0.06+0.084+0.19+0.076+0.038+0.532n=1/1.082n有： m(b1)n =K*(m1(b1)*m2(b1)+m1(b1)*m2(U)+m1(U)*m2(b1) =1.082*(0.01+0.028+0.19)=0.247n m(b2)n =K*(m1(b2)*m2(b2)+m1(b2

30、)*m2(U)+m1(U)*m2(b2)n =1.082*(0.008+0.056+0.076)=0.151nm(b3)n =K*(m1(b3)*m2(b3)+m1(b3)*m2(U)+m1(U)*m2(b3)n =1.082*(0.06+0.084+0.038)=0.nm(U)n =1- m(b1)+ m(b2)+ m(b3)=0.464例题n最后：BelB）n m(b1)+ m(b2)+ m(b3)0.536nP1(B)1-Bel(B)n由于基本概率分配函数只定义在B集合和全集U之上，所以其它集合的分配函数值为0，即Bel(B)=0n所以，可得n P1(B)1-Bel(B)=1n f (B)n =Bel(B)+(P1(B)-Bel(B)*|B|/|U|n =0.536+(1-0.536)*3/20=0.606第五章 不确定性推理nThe End主观贝叶斯方法n推理计算推理计算 ：n 4 4较复杂的情形较复杂的情形n E E的不确定性由观察的不确定性由观察