第07章不确定推理

1不确定推理2一、不确定推理概述（1）由于事物以及事物之间关系的复杂性导致相当一部分证据和知识的不确定性、模糊性。人工智能系统的智能主要反映在求解不确定性问题的能力上。3一、不确定推理概述（2）精确推理归结推理tableau推理以数理逻辑为基础,所处理的事实与结论之间存在着确定的因果关系;事实是确定的,得出的结论也是确定的;逻辑推理是一种运用确定知识进行的精确推理。不精确推理人工智能和专家系统的核心问题;是建立在非经典逻辑上的一种推理，是基于不确定性知识上的推理；从不确定的初始事实（证据）出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性却是合理或近乎合理的结论的思维过程。4一、不确定推理概述（3）精确推理从已知事实出发，运用相关的知识（或规则）逐步推出结论或者证明某个假设成立或不成立的思维过程。证据：已知事实根据：知识或规则5二、不确定推理方法的分类•模型方法：把不确定的证据和不确定的知识分别与某种度量标准对应起来，并给出更新结论不确定性的合适的算法，从而构成相应的不确定性推理模型。•控制方法：通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性系统产生的影响。如：启发式搜索、相关性制导回溯。数值方法：是对不确定性的一种定量表示和处理方法。基于概率的方法模糊推理方法非数值方法：如逻辑方法，它采用多值逻辑、非单调逻辑来处理不确定性。6三、不确定推理中的基本问题不确定性表示不确定性的匹配算法不确定性的更新算法73.1不确定性的表示（1）在不精确推理中，不确定性：证据的不确定性知识的不确定性证据初始事实：医疗诊断中的症状、化验结果等数据，多来源与观察，具有不确定性。推理过程中产生的中间结果：事实不确定，推理使用的知识不确定。证据不确定性表现在：歧义性、不完全性、不精确性、模糊性、可信性和随机性知识就是知识库中的知识，是进行推理的基础；在产生式系统中知识就是产生式规则；在不精确推理系统中，知识通常带有不确定性。83.1不确定性的表示（2）规则：IFETHENHE:规则的前提即证据；H:规则的结论，也可以是其它规则的证据。EHC（E）C（H）CF（H,E）C(E)：表示证据E为真的程度；CF(H,E)：规则强度，可以是该规则在应用中成功的概率，也可以是该条规则的可信度或其它；C(H)：规则(知识)的结论H的可信度，通过不确定性的更新算法来计算。93.1不确定性的表示（3）不确定性的量度和数值的取值范围•量度要能充分表达相应的知识和证据的不确定性程度。•量度范围的指定应便于领域专家及用户对不确定性的估计。•量度要便于对不确定性的更新计算，而且对结论的不确定性量度不能超出量度规定的范围。•量度的确定应当是直观的，同时应有相应的理论依据。103.2不确定性的匹配算法（1）•匹配算法：设计一个算法用来计算匹配双方相似的程度。•阈值：指定一个相似的限度，用来衡量匹配双方相似的程度是否落在指定的限度内。113.3不确定性的更新算法（1）•不确定推理的根本目的根据用户提供的初始证据，通过运用不确定知识，最终推出不确定结论，并推出结论为确定性的程度。(1)不确定性传递问题：C(H)=g1[C(E),CF(H,E)](2)证据不确定性的合成问题：C(E1∧E2)=g2[C(E1),C(E2)]C(E1∨E2)=g3[C(E1),C(E2)](3)结论不确定性的合成问题：C(H)=g4[C1(H),C2(H)]12四、可信度方法美国斯坦福大学E.H.Shortliffe等人在确定性理论（TheoryofConfirmation）的基础上，结合概率论等提出的一种不确定性推理方法。1976年在专家系统MYCIN中首先应用。134.1基于可信度的不确定性的表示可信度：根据经验或观察对一个事件或现象为真的程度。在MYCIN系统中，不确定性用可信度表示，知识用产生式规则表示，每一条规则都有一个可信度；每个证据也具有一个可信度。1、知识的不确定性表示知识规则的一般形式为：IFETHENH(CF(H,E))CF(H,E)表示规则的可信度，称为可信度因子或规则强度。CF(H,E)在[-1,1]上取值，它表示在已知证据E的情况下对假设H为真的支持程度。CF(H,E)0：表示证据的存在增加结论为真的程度，CF(H,E)的值越大结论H越真；CF(H,E)=1：表示证据的存在结论为真；CF(H,E)0：表示证据的存在增加结论为假的程度，CF(H,E)的值越小结论H越假；CF(H,E)=-1：表示证据的存在结论为假；CF(H,E)=0：表示证据E和结论H没有关系；144.1基于可信度的不确定性的表示2.证据不确定性的表示证据E的不确定性用证据的可信度CF（E）表示。原始证据的可信度由用户在系统运行时提供，中间结果的可信度由不确定性推理算法得到。CF(E)的取值范围与CF(H,E)相同，即[-1,1]。当证据以某种程度为真时，CF(E)0；当证据肯定为真时，CF(E)=1;当证据以某种程度为假时，CF(E)0,当证据肯定为假时，CF(E)=-1；当证据一无所知时，CF(E)=0。154.2可信度方法推理的基本算法1.组合证据的不确定性算法证据的合取。当组合证据是多个单一证据的合取时，即E=E1ANDE2AND…ANDEn若已知CF(E1),CF(E2),…,CF(En),则CF(E)=min{CF(E1),CF(E2),…,CF(En)}证据的析取。当组合证据是多个单一证据的析取时，即E=E1ORE2OR…OREn若已知CF(E1),CF(E2),…,CF(En),则CF(E)=max{CF(E1),CF(E2),…,CF(En)}164.2可信度方法推理的基本算法2.不确定性的传递算法所谓不确定性传递算法就是根据证据和规则的可信度求结论的可信度。已知规则IFETHENH(CF(H,E))并已知证据E的可信度CF（E），则CF(H)=CF(H,E)*max{0,CF(E)}若CF(E)0，即证据以某种程度为真，则CF(H)=CF(H,E)*CF(E)。当CF(E)0,即证据以某种程度为假，规则不能使用，则CF（H）=0。174.2可信度方法推理的基本算法3.多个独立证据推出同一假设的合成算法设有如下两条规则：IFE1THENH(CF(H,E1))IFE2THENH(CF(H,E2))则结论H的综合可信度可按如下步骤求得：（1）先分别求出CF1(H)=CF(H,E1)*max{0,CF(E1)}CF2(H)=CF(H,E2)*max{0,CF(E2)}（2）用下述公式求出E1和E2对H的综合影响所形成的可信度CF1,2(H)。CF1(H)+CF2(H)-CF1(H)*CF2(H)CF1(H)≥0,CF2(H)≥0CF1(H)+CF2(H)+CF1(H)*CF2(H)CF1(H)0,CF2(H)0CF1(H)+CF2(H)1－min{|CF1(H)|,|CF2(H)|}CF1,2(H)=CF1(H)与CF2(H)异号183.多个独立证据推出同一假设的合成算法例：设有如下规则：R1：IFE1THENH(0.8)R2：IFE2THENH(0.6)R3：IFE3THENH(-0.5)R4：IFE4ANDE5ORE6THENE1(0.7)R5：IFE7ANDE8THENE3(0.9)在系统运行中已从用户处得CF(E2)=0.8,CF(E4)=0.5,CF(E5)=0.6,CF(E6)=0.7,CF(E7)=0.6,CF(E8)=0.9，求H的综合可信度CF(H)。4.2可信度方法推理的基本算法推理过程解：由上述规则形成的推理网络图：HR1R2R3E1E2E3E4E5E6E8E7ANDORANDR4R5(1)求证据E4、E5、E6逻辑组合的可信度CF(E4AND(E5ORE6))=min{CF(E4),max{CF(E5),CF(E6)}}=min{0.5,max{0.6,0.7}}=0.5(2)根据规则R4求CF（E1）CF（E1)=0.7*max{0,CF(E4AND(E5ORE6))}=0.7*0.5=0.35(3)求证据E7、E8逻辑组合的可信度CF(E7ANDE8)=min{CF(E7),CF(E8)}=min{0.6,0.9}=0.6(4)根据规则R5求CF（E3）CF（E3）=0.9*max{0,CF(E7ANDE8)}=0.9*0.6=0.54(5)根据规则R1求CF1（H）CF1(H)=0.8*max{0,CF(E1)}=0.8*0.35=0.28(6)根据规则R2求CF2（H）CF2(H)=0.6*max{0,CF(E2)}=0.6*0.8=0.48(7)根据规则R2求CF3（H）CF3(H)=-0.5*max{0,CF(E3)}=-0.5*max{0,0.54}=-0.27(8)组合由独立证据导出的假设H的可信度CF1(H)、CF2(H)和CF3(H)，得到H的综合可信度。CF1,2(H)=CF1(H)+CF2(H)-CF1(H)*CF2(H)=0.28+0.48-0.28*0.48=0.63CF1,2(H)+CF3(H)0.63-0.271－min{|CF1,2(H)|,|CF3(H)|}1-0.27=0.49CF1,2,3(H)==194.2可信度方法推理的基本算法可信度方法小结计算简单只适用于特定的情况和范围改进的可信度方法－带有阈值限度的不确定性推理20五、概率方法不确定性与概率有许多内在的联系。因此，很早以来，研究人员就将概率理论引入人工智能中，用做一种不确定性的处理工具。215.1概率论基础（1）1.事件的概率在随机现象中，表示事件发生可能性大小的数称为事件的概率。设有A表示一个事件，则它的概率记做P(A)。概率的性质：对于任意事件A，有0P(A)1;必然事件D的概率P(D)=1，不可能事件Ø概率P(Ø)=0设事件A1,A2,…,Ak是两两互不相容的事件，即有Ai∩Aj=Ø(i≠j),则P(Ai)=P(A1)+P(A2)+…+P(Ak);对任一事件A，有P(A)=1-P(A);若A,B是两个事件，则P(A∪B)=P(A)+P(B)-P(A∩B);若A,B是两个事件，且AB，则P(A-B)=P(A)-P(B)。225.1概率论基础（2）2.条件概率在设A和B是某个随机实验中的两个事件，如果在事件B发生的条件下考虑事件A发生的概率，则称它为事件A的条件概率。记作P(A|B)。若P(B)0，则P(A∩B)P(B)P(A|B)=235.1概率论基础（3）3.全概率公式与Bayes公式定理：设事件A1,A2,…,An满足两两互不相容，即当i≠j时，有Ai∩Aj=Ø；P(Ai)0全概率公式24六、主观Bayes方法R.O.Duda和P.E.Hart等人于1976年在Bayes公式的基础上经适当改进，提出了主观Bayes方法，建立了相应的不精确推理模型，并在矿藏勘探专家系统PROSPECTOR中得到了成功的应用。256.1不确定性的表示(1)1、知识的不确定性表示在主观Bayes方法中，规则表示为：IFETHEN(LS,LN)H(P(H))其中：LS:充分性量度；LN:必要性量度，这两个数值由领域专家给出。主观Bayes方法的不精确推理过程:根据前提E的概率P(E),利用规则的LS和LN,把结论H的先验概率P(H)更新为后验概率P(H|E)的过程。EHP(E)P(H)LS,LN规则名(1)几率函数几率函数O(odds)等价于概率函数P，定义为：PO1–P1+O先验几率：P(H)P(H)1–P(H)P(H)后验几率：P(H|E)P(H|E)1–P(H|E)P(H|E)O=P=O(H)==O(H|E)==266.1不确定性的表示(2)(2)充分性度量LS与必要性度量LN由Bayes公式知:P(E|H)*P(H)P(E)P(E|H)*P(H)P(E)(1)/(2)，可得P(H|E)P(H)*P(E|H)P(H|E)P(H)*P(E|H)P(H|E)=P(H|E)=(1)(2)=(3)P(E|