第5章不确定与非单调推理

第５章不确定与非单调推理不精确推理的主要理论基础是概率论。但是由于显示世界中存在的种种原因，使得获取大容量的样本成为困难，从而使得传统的概率论方法受到限制.为此,专家系统的建造者们提出了许多改进的理论模型和经验公式处理不确定性.其中有代表性的有以下五种方法:第５章不确定与非单调推理MYCIN的不精确推理模型C-F模型、主观Bayes方法、模糊集理论、证据理论、发生率计算。当然，不精确推理一直是专家系统中的一个重要课题，各种各样的方法正在创建之中。MYCIN的不精确推理MYCIN是一个比较著名的计算机医疗专家系统。它的功能是帮助内科医生诊断细菌感染病并为患者选择合适的治疗方案。它的不精确推理模型是由Shortliffe等人提出的。Ｃ－Ｆ模型一、MYCIN的推理控制在MYCIN中为每一个断言A指定一个确定性度量CF(A)，若知道A为真，则CF(A)=1；若知道A为假，则CF(A)=-1；若对A一无所知，则CF(A)=0。MYCIN的知识是由规则表示的，它的一般形式是：IFE1ANDE2ANDANDEnTHENH(x)其中Ei(i=1,2,,n)是证据,H可以是一个或多个结论.规则的意思是:当证据E1到En都确实存在时,结论H以x的可信度成立。x是可信度因子Ｃ－Ｆ模型（CF：CertaityFactor），由领域专家给出。x的值在[-1,1]范围内，x0表示证据存在，增加结论为真的可信度，x越大结论越真，x=1表示证据存在，结论为真；相反，x0表示证据存在增加结论为假的可信度，x越小结论越假；x=-1表示证据存在，结论为假；当x=0时，表示证据和结论没有关系。Ｃ－Ｆ模型在MYCIN中，它的规则通过反向推理策略被连成推理回路。由于规则的前提断言A有CF(A)，而此规则又有可信度因子x，现在要问在这种情况下，规则的结论H的可信度应怎样计算呢？MYCIN的不精确推理解决方案如下：Ｃ－Ｆ模型MYCIN的不精确推理算法在MYCIN中首先引入了信任增长度MB（MeasureBelief）和不信任增长度MD（MeasureDisbelief）两个概念。MB[H,E](0)表示因证据E的出现而增加对假设H为真的信任增长度，即MB[H,E]0表示因证据E的出现而增加对假设H为真的信任增长度，即P(HE)P(H).Ｃ－Ｆ模型MD[H,E](0)表示因证据E的出现而增加对假设H为假的不信任增长度，即P(HE)P(H).因为同一个证据E不可能既增加对H的信任增长度又增加对H的不信任增长度.即不可能因证据E的出现，既使MB[H,E]0又使MD[H,E]0，也就是P(HE)P(H)P(HE)P(h)，同时成立是不可能的，即应有互斥律。Ｃ－Ｆ模型当MB[H,E]0时，MD[H,E]=0；当MD[H,E]0时，MB[H,E]=0。MB和MD的概率意义是：假定P(h)表示h的先验概率，P(HE)表示当E为真时，H的条件概率，如果P(HE)大于P(H)，意思是说，在E存在的条件下，对H的信任增加，为此，MB定义为：Ｃ－Ｆ模型1若P(H)=1MB[H,E]=max{P(HE),P(H)}-P(H)否则1-P(h)同理，如果P(HE)小于P(H)，说明在E存在的条件下对H的不信任增加。MD定义为：Ｃ－Ｆ模型１若P(h)=0MD(h,e)=min{P(he),P(h)}-P(h)否则-P(h)然而在MYCIN中主要用的是另一个概念—可信度CF，它把MB和MD组合到一起，CF的定义如下：CF[h,e]=MB[h,e]-MD[h,e]Ｃ－Ｆ模型根据CF的定义和MB与MD满足互斥律的性质以及若P(he)=P(h)表示e与h独立等性质，CF公式可为：MB[h,e]-0=P(he)-P(h)若P(he)P(h)CF[h,e]=1-P(h)0若P(he)=P(h)0-MD[h,e]=P(he)-P(h)若P(he)P(h)P(h)Ｃ－Ｆ模型公式中P(H)是个常量，因此，上式是一个P(HE)的分段线性函数。该公式的直观解释是：CF0,说明E的出现增加H为真的概率,即P(HE)P(H)，也就是说E的出现增加了H为真的可信度,CF越大,E的出现增加H为真的可信度越大,CF=1,导出P(HE)=1,即E的出现使H为真；Ｃ－Ｆ模型CF0，说明E的出现减少H为真的概率,即P(HE)P(H),也就是说E的出现增加了H为假的可信度，CF越小，E的出现增加H为假的可信度越大，CF=-1，导出P(HE)=0，即E的出现使H为假；CF=0时，导出P(HE)=P(H)，即E与H独立，或者说E的出现对H没有影响。根据上述原则，当有规则IFETHENH，我们就能够根据E的出现是增加H为真还是为假的可信度及E对H的影响程度给出CF[H,E]的值。从MB，MD和CF的定义还可以看出以下特征：Ｃ－Ｆ模型（1）变程：0≤MB[H,E]≤10≤MD[H,E]≤1-1≤CF[H,E]≤1Ｃ－Ｆ模型（2）证实的情况：-1若P(he)=0CF[h,e]=0若P(he)=P(h)1若P(he)=1Ｃ－Ｆ模型（3）不证实的情况：MB[H,E]=0这时E的存在证实不了H，即这时或是E与H独立或是E否认H；MD[H,E]=0,这时E的存在不否认H，即这时或是E与H独立或是E证实H；CF[H,E]=0这时E与H独立Ｃ－Ｆ模型（4）对于同一证据E，若有若干个互斥的假设结论Hi(i=1,2,…,n),则可以证明：in=CF[Hi,E]≤1且上式中等式成立，当且仅当n=1与P(H1E)=1。这一条在建立专家系统时经常用得到。比如，专家给出的规则出现下面的情况：CF[H1,E]=0.7,CF[H2,E]=0.4其中H1和H2互斥。因为0.7+0.4=1.11非法，就应该调整或规范化。Ｃ－Ｆ模型（5）从定义可以看出，可信度CF与概率P有一定的对应关系，但又有区别。这可以从下式看出，对于概率恒有：P(HE)+P(HE)=1而CF[H,E]+CF[H,E]=0这就是说，对H的可信度与对H的可信度之和是0而不是1,可见可信度不是概率.Ｃ－Ｆ模型从前面的叙述中我们看到CF的定义中用到了先验概率P(H)和条件概率P(HE),事实上这些数据很难得到。在实际应用中，规则的可信度是由领域专家给定，其基本原则是：若证据E出现增加假设H为真的可信度，则给出的CF[H,E]0,反之，CF[H,E]0；若证据的出现不影响假设H的可信度，则给出的CF[H,E]=0。Ｃ－Ｆ模型CF的另一个作用是求某断言A(包括证据和假设)的可信度，用CF(A)表示某断言A为真的可信度。推理的任务就是求出CF(A)。若A是原始证据，则由用户观察主观给出，若A是某规则的结论，则根据前提E的可信度CF(E)及规则的可信度CF[A,E]按一定算法得出。由于前提可以是单个条件也可以是多个条件的逻辑组合，所以分下述两方面介绍。Ｃ－Ｆ模型(1)证据是单个条件当规则IFETHENH(x)被使用时，又分E是肯定存在和E以CF[E]存在两种情况。其中x等于CF[H,E]。若E肯定存在，即CF[E]=1，那麽结论H以x的可信度为真，即CF[H]=CF[H,E]；Ｃ－Ｆ模型若E不是肯定存在。这是因为在客观世界中，对证据的观察也不是很准确的，另一方面，证据E可能是另一条规则的结论，这时也常常是不确定的。在这种情况下，结论H的可信度CF[H]不仅取决规则的可信度CF[H,E]的值，也取决于证据E的可信度CF[E]。计算公式如下：CF[H]=CF[H,E].max{0,CF[E]}(1)Ｃ－Ｆ模型公式中取0和CF[E]的最大值的意义是：若CF[E]小于0（即前提为假）说明这条规则不能应用，或者说求出的CF[H]应等于0。否则，结论H的可信度等于规则的可信度乘以证据的可信度。Ｃ－Ｆ模型(2)证据是多个条件的逻辑组合A)证据是AND连接若IFE1ANDE2ANDANDEnTHENH(x),则CF[E]=CF[E1ANDE2ANDANDEn]=min{CF[E1],CF[E2],,CF[En]}(2)Ｃ－Ｆ模型B)证据是OR连接E=E1ORE2OROREnCF[E]=CF[E1ORE2OROREn]max{CF[E1],CF[E2],,CF[En]}(3)Ｃ－Ｆ模型C）两条规则具有相同的结论如果有规则：IFE1THENH(CF[H,E1])IFE2THENH(CF[H,E2])首先利用公式（1）分别求出CF1[H]=CF[H,E1].max{0,CF[E1]}CF2[H]=CF[H,E2].max{0,CF[E2]}Ｃ－Ｆ模型然后用公式CF1[H]+CF2[H]-CF1[H].CF2[H]若CF1[H]&CF2[H]≥0CF12[H]=CF1[H]+CF2[H]+CF1[H].CF2[H](4)若CF1[H]0,CF2[H]0CF1[H]+CF2[H]1-min{∣CF1[H]∣,∣CF2[H]∣}若CF1[H]与若CF2[H](异号)Ｃ－Ｆ模型一个计算实例例如有如下一批规则r1IFE1THENH（0.9）r2IFE2THENH（0.7）r3IFE3THENH（-0.8）r4IFE4ANDE5THENE1（0.7）r5IFE5AND(E7ORE8)THENE2（1.0）Ｃ－Ｆ模型在系统运行过程中从用户处得CF[E3]=0.3;CF[E4]=0.9;CF[E5]=0.6;CF[E6]=0.7;CF[E7]=-0.3CF[E8]=0.8,试求CF[H]即H的可信度。依题意可得如下的推理网络：Ｃ－Ｆ模型HE1E2E3E4E5E6ORE7E8Ｃ－Ｆ模型解：首先求出CF[E1]，CF[E2]和CF[E3]，然后再求CF[H]。CF[E1]=0.7*max{0,CF[E4ANDE5]}=0.7*max{0,min{CF[E4],[E5]}}=0.7*max{0,min{0.9,0.6}}=0.7*max{0,0.6}=0.7*0.6=0.42Ｃ－Ｆ模型CF[E2]=1*max{0,CF[E6AND(E7ORE8)]}=1*max{0,min{CF[E6],CF(E7ORE8)}}=1*max{0,min{CF[E6],max{CF[E7],CF[E8]}}}=1*max{0,min{CF[E6],max{-0.3,0.8}}}=1*max{0,min{0.7,0.8}}=1*max{0,0.7}=1*0.7=0.7Ｃ－Ｆ模型CF[E3]=0.3已知CF1[H]=0.9*max{0,CF[E1]}=0.9*max{0,0.42}=0.38CF2[H]=0.7*0.7=0.49CF3[H]=-0.8*0.3=-0.24CF12[H]=CF1[H]+CF2[H]-CF1[[H].CF2[H]=0.38+0.49-0.38*0.49=0.6838(用公式（4）的等式1)Ｃ－Ｆ模型CF123[H]=(0.6838-0.24)/1.24=0.3579(用公式（4）的等式3)即最后H的可信度是0.3579Ｃ－Ｆ模型例：已知规则R1、R2的可信度：R1：A→X，CF(X,A)=0.8R2:B→X，CF(X,B)=0.6证据可信度CF(A)=CF(B)=0.5求结论X的可信度CF(X)?解：本题是多条规则支持同一个结论的情况，首先计算Ｃ－Ｆ模型CF1(A,X)=0.5*0.8=0.4CF2(B,X)=0.5*0.6=0.3由于CF1和CF2都大于0所以CF12=CF1+CF2-CF1CF2=0.4+0.3-0.4*0.3=0.58