ch4-不确定性推理

1、不确定性推理 1不确定因素模糊性随机性不可靠不知道 2不确定性推理定义从具有不确定性的证据出发，运用不确定性的知识或规则库中的知识，最终推出具有一定程度的不确定性，但却合理的或近乎合理的结论的思维过程。3不确定性推理方法的分类模型方法：把不确定性证据和知识与某种度量标准对应起来，给出更新结论不确定性的合适算法，构成不确定性推理模型。数值方法：定量表示和处理不确定性。以模糊集理论为基础的方法按这种方法，把所有条件中最小的可信度作为总条件的可信度。这种方法类似于当把几根绳子连接起来使用时，总的绳子强度与强度最差的绳子的相同。以概率为基础的方法这种方法同样赋予每个证据以可信度。但当把单独条件的可信度

2、结合起来求取总的可信度时，它取决于各可信度的乘积。非数值方法：逻辑法，多值逻辑和非单调逻辑4不确定性推理方法的分类控制方法：通过领域中引起不确定性的某些特征及控制策略，限制或减少不确定性系统产生的影响，没有统一模型，效果依赖于控制策略。启发式搜索相关性制导回溯5不确定性推理中的基本问题不确定性的表示证据知识不确定性的度量不确定性的推理计算不确定性的传递问题证据不确定性的合成问题：证据间的合成（与/或）结论不确定性的合成问题：两个规则的合成6常用的不确定性推理方法 主观贝叶斯(Bayes)可信度(确定性) 证据理论(DS)模糊逻辑推理 可能性理论缺省推理 非单调推理系统 7概率推理方法主观Bay

3、es方法 R.O.Duda、P.E.Hart等人1976年在Bayes公式的基础上经适当改进提出了主观Bayes方法;最早用于处理不确定性推理的方法之一;已在地矿勘探专家系统PROSPECTOR中得到了成功的应用。 8概率推理方法主观Bayes方法 Bayes公式 若有诸事件A1,A2,，An，彼此独立，且B为事件A1A2An的子事件，P(Ai)0(i=1,2,n)，P(B)0，那么Bayes公式可表示为：式中， 为先验概率； 为后验概率。Bayes公式就是从先验概率推导出后验概率的公式。9概率推理方法主观Bayes方法 为阐明主观Bayes方法，先引入几个概念：引入两个数值(LS，LN)来作

4、度量LS 表现规则成立的充分性LN 表现规则成立的必要性这种表示既考虑了 A 的出现对 B 的支持，又考虑了 A 的不出现对 B 的影响。10对规则的主观Bayes方法 对规则的不确定性度量:直接使用Bayes 公式来做度量时，在计算P(B|A)时需要已知P(A|B)，为避开这个困难，提出了主观Bayes 方法。对规则AB的不确定性f(B,A)以(LS，LN)来描述。其中 11对规则的主观Bayes方法先建立几率函数， 定义为表示的是证据X的出现概率与不出现概率之比，显然随P(X)的加大O(X)也加大，而且当P(x)=0时，有 O(x) 0 当P(x)=1时，有 O(x) 于是，取值于0,1的

5、P(x)被放大为O(x)，取值为0, 。12对规则的主观Bayes方法不难验证O(B|A)=LSO(B)O(B|A)=LNO(B)由于 两者相比得 这就是O(B|A)=LSO(B)同样，也可得O(B|A)=LNO(B)13对规则的主观Bayes方法由这两个公式可看出，LS表示A真时，对B为真的影响程度，表示规则AB成立充分性。LN表示A假时，对B为真的影响程度，表示规则AB成立的必要性。14对规则的主观Bayes方法几个特殊值15对规则的主观Bayes方法由LS，LN 的定义知，LS，LN均 0,而且LS，LN不是独立取值的，只能出现LS1，LN1或LS1 或LSLN1。但不能出现两者同时1或

6、同时1。在实际系统中，LS，LN的值是由专家凭经验给出的，而不是依LS，LN的定义来计算的。16对证据的主观Bayes方法证据的不确定性度量 就以O(A)或P(A)表示证据A的不确定性，转换公式是17主观Bayes方法推理计算 （1） 当A确定必出现时，可直接使用O(B|A)LSO(B)O(B|A)=LNO(B)以求得使用规则AB后，O(B)的更新值O(B/A),O(B/A)。若需要以概率表示，再由计算出P(B|A),P(B|A)。 18主观Bayes方法推理计算 （2）当A是不确定的，即P(A)1时，需作如下考虑。设A代表与A有关的所有观察，对规则AB来说 Duda 1976年给出公式：P(

7、B|A)=P(B|A)P(A|A)+P(B|A)P(A|A)问题是当P(B|A)，AB (LS，LN)以及P(B)已知时，如何更新P(B)或说寻求P(B|A) 。当P(A|A)1时，证据A必然出现有下式成立：19主观Bayes方法推理计算 证明：20主观Bayes方法推理计算 当P(A|A)=0时，证据A必然不出现经同样的推导得：21主观Bayes方法推理计算 当P(A|A)=P(A)时，也即观察A对A无影响。有P(B|A)=P(B|A)P(A)+P(B|A)P(A) =P(BA)+P(BA) =P(B)这样已可确定P(A|A)为0、P(A)、1时相应的P(B|A)的值，便可得线性插值图。 2

8、2主观Bayes方法推理计算 线性插值图23主观Bayes方法推理计算 P(A|A)的其它取值下的P(B|A)，可通过线性插值图求得。（3）P(A1A2|A)=minP(A1|A),P(A2|A) P(A1A2|A)=maxP(A1|A),P(A2|A)（4）若A1B, A2B而A1，A2相互独立，对 A1，A2的有关观察分别为A1，A2便有:24主观Bayes方法推理计算 4.举例1当证据A1 ， A2 ， A3 ， A4必然发生后，看B的概率变化。已知B的先验概率为0.03，而规则R1： A1 B LS=20 LN=1R2： A2 B LS=300 LN=1R3： A3B LS=75 LN

9、=1R4： A4 B LS=4 LN=1下面进行计算。25主观Bayes方法推理计算 （1）依P(B)0.03便得:（2）依R1，有O(B| A1)=LS O(B) =20(0.030927)=0.6185使用规则R1后，B1的概率从0.03上升到0.38226主观Bayes方法推理计算 （3）依R2有O(B| A1 A2 )=300 O(B| A1 )=185.565由于 A2发生，使B的概率由0.328增到0.99464，对A3 ， A4 的发生可同样计算。27主观Bayes方法推理计算 举例2当证据A必然发生，已知B1的先验证概率为0.03，而规则R1：A B1 LS=20 LN=1R2

10、：B1B2 LS=300 LN=0.0001又知P(B2)的先验概率为0.01时，如何计算P(B2 |A)？问题是当使用R2时，B1不是必然发生了，也是不确定的，这时需使用插值方法。28主观Bayes方法推理计算 （1） 依A必发生，由R1得P(B1 |A)=0.382（2）但是使用规则R2时，B1并非确定地发生，因此要用插值法。 设P(B1 |A)1，这时依B1)29主观Bayes方法推理计算 （3） 再设P(B1|A)P(B1)0.03，即A对B1无影响，P（B2）0.01，根据这两个值可进行插值计算，求得:见图30主观Bayes方法推理计算 P(B2 |A)=0.305131主观Baye

11、s方法推理计算 总结主观Bayes方法优点：直观，明了。问题：要求Bj个事件相互独立（无关），实际上是不可能的。P(A/Bi)和P(Bi)难以计算。实际应用中，为了避开这一点采用LS, LN的专家给定值。32可信度方法确定性方法可信度的不确定性表示一般通过对事实赋于一个介于0和1之间的系数来表示事实的不确定性。1代表完全确定0代表完全不确定。系数被称为可信度也有一些专家系统，如MYCIN和EXPERT等，取可信度的范围为-1到+1。 33可信度方法确定性方法证据的不确定性处理：当规则具有一个以上的条件时，需要根据各条件的可信度来求得总条件部分的可信度。以概率为基础的方法这种方法同样赋予每个证据

12、以可信度。但当把单独条件的可信度结合起来求取总的可信度时，它取决于各可信度的乘积。 34可信度方法确定性方法知识的不确定性表示也叫规则的不确定性它表示当规则的条件被完全满足时，产生某种结论的不确定程度。它也是以赋予规则在0和1之间的系数的方法来表示的。例：有以下规则：如果启动器发生刺耳的噪声那么这个启动器坏的可能性是0.8。该规则表示，如果“启动器发生刺耳的噪声”这事实完全肯定的可信度为1.0，那么得出“这个启动器坏”的结论的可信度为0.8。35可信度方法确定性方法知识的不确定性处理如果规则的条件部分不完全确定，即可信度不为1时，求知识的可信度方法有两种：(1)取结论可信度为条件可信度系数的乘

13、积。(2)按照某种概率论的解释，我们假设规则的条件部分的可信度Cin和其结论部分的可信度Cout存在某种关系，这种关系可用来代表规则的不确定性。36可信度方法确定性方法 以产生式作为知识表示方法的专家系统MYCIN中，第一次使用了不确定性推理方法，给出了以确定性因子或称可信度作为不确定性的度量。这种推理方法必须解决几个方面的核心问题规则和证据的不确定性度量问题不确定性的传播与更新问题。37可信度方法规则的表示 以产生式作为知识表示，给出了以确定性因子或称可信度作为不确定性的度量。有规则A B，其可信度CF(B, A)定义如下：38可信度方法规则的表示CF(B,A)表示的意义：证据为真是相对于P

14、(B) = 1 - P(B)来说，A对B为真的支持程度，即A发生更支持B发生，此时 CF(B,A) 0。相对于P(B)来说，A对B为真的不支持程度。即A发生不支持B发生，此时 CF(B,A) 0。它总是满足条件-1 CF(B,A) 1。39可信度方法规则的表示CF(B, A)的特殊值：CF(B, A) = 1， 前提真，结论必真CF(B, A) = -1， 前提真，结论必假CF(B, A) = 0 ， 前提真假与结论无关实际应用中CF(B, A)的值由专家确定，并不是由P(B|A), P(B)计算得到的。注意：CF(B,A)表示的是增量P（B|A）P（B）对1P（B）或P（B）的比值，而不是绝

15、对量的比值。40可信度方法证据的表示证据A的可信度用CF( A)来表示，为了计算方便，规定：-1 CF( A) 1可信度CF( A)的如下特殊值的含义：CF( A) = 1， 前提肯定真CF(A) = -1， 前提肯定假CF(A) = 0， 对前提一无所知CF( A) 0， 表示A以CF( A)程度为真CF( A) 0， 表示A以CF( A)程度为假实际使用时，初始证据的CF值有专家根据经验提供，其它证据的CF通过规则进行推理计算得到。41可信度方法不确定性的传播与更新1）“与”的计算： A1 A2 BCF(A1 A2 ) = min CF(A1), CF(A2) 2）“或”的计算：A1 A2

16、 BCF(A1 A2 ) = max CF(A1), CF(A2) 3）“非”的计算：CF(A ) = CF(A) 4）由A， A B，求 CF(B)：CF(B) = max(0，CF(A)CF(B,A)42可信度方法不确定性的传播与更新5）合成，由两条规则求出再合并：由规则A1B可求得CF1（B），同时又有规则A2B，可求得CF2（B）。如何根据这两条规则的产生的结果，计算其合成后的可信度CF（B）？先有：CF1(B)= max(0，CF(A1)CF(B,A1)CF2(B)= max(0，CF(A2)CF(B,A2)43可信度方法不确定性的传播与更新CF1(B)和CF2(B)是同时发生的，即

17、可以是分别从两条完全独立的途径得到的知识。44可信度方法不确定性的传播与更新6）CF(B)的更新计算：已知证据A 的可信度CF（A），结论B的原有可信度CF（B），求A通过规则AB，作用到B后，B的可信度的更新值CF（B|A）。由于，证据A不是必然发生的，是具有一定可信度的，所以必须对可信度的情况进行讨论。45可信度方法不确定性的传播与更新当CF（A）=1时，即A必然发生时：46可信度方法不确定性的传播与更新当0CF（A）1时，即A可能发生时：由于A是否发生是不确定的，因此CF（B|A）一定比A必然发生时要小。此时取CF（A）* CF（B，A）代替上式中的规则可信度CF（B，A）即可。即更新后

18、的可信度公式为：47可信度方法不确定性的传播与更新当CF（A）0时，即A不可能发生时规则AB不使用，即认为不可能发生的事件（A为假的事件）对结果B没有影响。48可信度方法例题已知 R1：A1B1 CF（B1，A1）0.8 R2：A2B1 CF（B1，A2）0.5 R3：B1A3B2 CF（B2，B1A3）0.8 CF（A1）CF（A2）CF（A3）1； CF（B1）= CF（B2）=0计算更新 CF（B1）、CF（B2）49可信度方法例题解：依规则R1CF（B1|A1）CF（B1）CF（B1，A1）（1CF（B1）0.8即更新后CF（B1）0.8依规则R2CF（B1|A2）CF（B1）CF（B

19、1，A2）（1CF（B1）0.9更新后CF（B1）0.950可信度方法例题依R3，先计算CF（B1A3）min（CF（A3），CF（B1）0.9由于CF（B1A3）1，CF（B2| B1A3）= CF（B2）+ CF（B1A3）CF(B2，B1A3)（1-CF（B2）=0+0.90.8(1-0)=0.72答：更新后的可信度分别是：CF（B1）0.9，CF（B2）0.7232.swf51证据理论（D-S Theory） 证据理论由Dempster首先提出，并由他的学生Shafer发展起来，也称D-S理论。在专家系统的不精确推理中已得到广泛的应用, 也用在模式识别系统中。证据理论中引入了信任函数，

20、它满足概率论弱公理。在概率论中，当先验概率很难获得，但又要被迫给出时，用证据理论能区分不确定性和不知道的差别。所以它比概率论更合适于专家系统推理方法。当概率值已知时，证据理论就成了概率论。因此，概率论是证据理论的一个特例，有时也称证据理论为广义概率论。52证据理论（D-S Theory） 证据用集合来表示：如U中的每个元素代表一种疾病。讨论一组疾病A发生的可能性时，A就变成了单元的集合。U内元素间是互斥的，但Ai中元素间不是互斥的。针对医疗诊断问题， U就是所有可能疾病（假设）的集合，诊断的结果必是U中确定的元素构成的。A表示某一种（单元素）或某几种疾病。医生为了诊断所进行的各种检查就称作证据

21、，有的证据支持的不只是一种疾病而是多种疾病，即构成U的一子集A。 53证据理论（D-S Theory） 证据理论定义了多个函数值来描述证据及规则的不确定性概率分配函数M信任函数Bel似然函数Pl54证据理论：概率分配函数概率分配函数的作用是把D上的任意一个子集A( 2D)都映射为0,1上的一个数m(A) 。当A对应一个命题时, m(A) 就是对应命题不确定性的度量.概率分配函数定义：设D为样本空间，领域内的命题都用D的子集表示，如果定义函数m (x)为集合2D到区间0,1的一个映射函数，即设m (x)为集合2D0,1的一个映射，且满足如下条件：m() = 0 空的为零m(A) = 1 全空间的

22、和为1（ AD）称m (x)为2D上的概率分配函数.m(A)为命题A的基本概率数。m是在D的幂集2D 上定义的，取值范围是0,1。55证据理论：概率分配函数概率分配函数设m (x)为集合2D0,1的一个映射，且满足：m() = 0 空的为零m(A) = 1 全空间的和为1（ A2D ）m (x)为2D上的概率分配函数.m(A)为命题A的基本概率数m是在D的幂集2D 上定义的，取值范围是0,1。基本概率函数的物理意义是：若A属于D，且不等于D，表示对A的精确信任度若A等于D，表示这个数不知如何分配.56证据理论：信任函数信任函数是对命题A的不确定性进行度量。信任函数的定义设D为样本空间， 2D为

23、D的所有子集表示的命题之集合， A是2D中的一个命题。如果定义函数Bel(A)为将集合2D映射到区间0,1上的函数，且满足：对所有的 A 2D 称Bel(A)为信任函数或称下限函数。57证据理论：信任函数信任函数信任函数Bel：2D 0,1A的信任函数为：包含于A中的所有集合的概率分配函数值之和。根据定义有：Bel() m() = 0Bel(D)m(B) = 1（B属于D）信任函数Bel类似于概率密度函数，表示A中所有子集的基本概率分配数值的和。表示对A为真的信任程度。58证据理论：似然函数似然函数定义：设有函数Pl(A)为将集合2D映射到区间0,1上的函数，即似然函数Pl：2D 0,1且满足

24、：对所有的 A 2D 则称Pl(A)为似然函数。意义：A的似然函数为Pl(A)：表示对A为非假的信任度程度。即对A不为假的信任程度。59证据理论：似然函数对A不为假的信任程度应该大于对A为真的信任程度，即Bel(A) Pl(A) 根据定义有：0 Bel(A) Pl(A) 1，可见Bel是Pl的一部分。称Bel(A)和Pl(A)是A的下限不确定性值和上限不确定性值。因此可用区间（Bel(A)，Pl(A)）来表示A的不确定性度量。60证据理论：类概率函数f1用类概率函数f1(A)来衡量A的不确定性，其定义如下：f1(A)= Bel(A) + |A|/|D|(Pl(A) - Bel(A)其中|A|、

25、|D|为集合内元素的个数。有下列式子成立：f1()0f1(D)10f1(A)1，对A属于D61证据理论：似然函数设函数f(Bel(A), Pl(A)，下列特殊值的含义f(1, 1) 表示A为真f(0, 0) 表示A为假f(0, 1) 表示对A一无所知f(1, 0) 不可能成立62证据理论：规则的不确定性度量设子集合A, B，其中 A = a1, a2, , al, B = b1, b2, , bk用相应的向量 (c1, c2, , ck) 描述规则A B的不确定性度量，其中ci0, 1ik, 且cj1 1jk。63证据理论：推理计算1）“与”的计算： f1 (A1A2) = min f1 (A

26、1), f1 (A2)2）“或”的计算f1 (A1A2) = max f1 (A1), f1 (A2)3）“非”的计算f1(A ) = f1 (A )4）由f1 (A)， A B， (c1, c2, , ck)。求f1 (B)m(b1, b2, ,bk) =(f1 (A)c1, f1 (A)c2, , f1 (A)ck)m (D) = 1-f1 (A)ci, i = 1, , k64证据理论：推理计算5）证据的组合，m1, m2在D上的合成对于同样的证据，由于来源不同，分别得到二个概率分配函数m1, m2。定义： m1, m2的正交和为 m = m1m2规定：m() = 0; m(A) = K

27、-1 m1(X)m2(Y), 当XY = A其中:若K 0, K = 1 - m1(X)m2(Y), 当XY = 或 K = m1(X)m2(Y), 当XY 若K = 0,认为m1, m2矛盾。没有联合基本概率分配函数。常数K是根据m1m2需对2D的所有元素的基本概率分配之和为1来确定的。65证据理论：推理计算例题已知：f1(A1) = 0.40 ,f1(A2)=0.50,|D| = 20. A1B=b1,b2,b3，(c1,c2,c3)=(0.1,0.2,0.3) A2B=b1,b2,b3，(c1,c2,c3)=(0.5,0.2,0.1)求：f1(B)解：（1） 先求：m1(b1,b2,b3)=(0.4*0.1,0.4*0.2,0.4*0.3) =(0.04,0.08,0.12);m1(U)=1- m1(b1)+m1(b2)+m1(b3)=0.76;66证据理论：推理计算例题m2(b1,b2,b3)=(0.5*0.5,0.5*0.2,0.5*0.1) =(0.