人工智能及應(yīng)用

1、不確定性推理不確定性推理證據(jù)理論D-S理論理論l證據(jù)理論是由德普斯特證據(jù)理論是由德普斯特(A.P.Dempster)提提出，并由沙佛出，并由沙佛(G.Shfer)進(jìn)一步發(fā)展起來(lái)的進(jìn)一步發(fā)展起來(lái)的一種處理不確定性的理論。也稱為一種處理不確定性的理論。也稱為D-S理理論。論。l其將概率的單點(diǎn)賦值擴(kuò)展為集合賦值，弱其將概率的單點(diǎn)賦值擴(kuò)展為集合賦值，弱化了公理系統(tǒng)。處理由不知道引起的的不化了公理系統(tǒng)。處理由不知道引起的的不確定性。確定性。概率分配函數(shù)概率分配函數(shù)l定義定義4-14-1：設(shè)：設(shè)是樣本集，則由是樣本集，則由的所有子集的所有子集構(gòu)成的集合稱為構(gòu)成的集合稱為的冪集，記為的冪集，記為2。l例：設(shè)

2、例：設(shè)=紅，黃，白紅，黃，白 ，求，求的冪集的冪集2 解：解： 的冪集元素為的冪集元素為 ， 紅紅 ， 黃黃 ， 白白 ， 紅，黃紅，黃 ， 紅，白紅，白 ， 黃，白黃，白 ， 紅，黃，白紅，黃，白 。概率分配函數(shù)概率分配函數(shù)定義定義4-24-2：設(shè)函數(shù)：設(shè)函數(shù)m: 20,10,1，且滿足且滿足 m()=0 A m(Am(A)=1)=1稱稱mm是是2上的概率分配函數(shù)，上的概率分配函數(shù)，m(Am(A) )稱為稱為A A的基的基本概率數(shù)。本概率數(shù)。 概率分配函數(shù)概率分配函數(shù)例：為上一個(gè)例子定義一個(gè)概率分配函數(shù)。例：為上一個(gè)例子定義一個(gè)概率分配函數(shù)。解：解：m(， 紅紅 ， 黃黃 ， 白白 ， 紅，

3、黃紅，黃 ， 紅，白紅，白 ， 黃，白黃，白 ， 紅，黃，白紅，黃，白 ) =0,0.3,0,0.1,0.2,0.2,0,0.2概率分配函數(shù)的兩點(diǎn)說(shuō)明概率分配函數(shù)的兩點(diǎn)說(shuō)明l概率分配函數(shù)將樣本空間中的任意子集映射到概率分配函數(shù)將樣本空間中的任意子集映射到，的一個(gè)數(shù)。，的一個(gè)數(shù)。當(dāng)子集是一個(gè)元素時(shí)，表示對(duì)此元素的精確信任度，當(dāng)子集是一個(gè)元素時(shí)，表示對(duì)此元素的精確信任度，也是對(duì)子集的精確信任度。也是對(duì)子集的精確信任度。當(dāng)子集是多個(gè)元素時(shí)，表示對(duì)子集的精確信任度，當(dāng)子集是多個(gè)元素時(shí)，表示對(duì)子集的精確信任度，但不清楚子集中每個(gè)元素的信任度。但不清楚子集中每個(gè)元素的信任度。當(dāng)子集是樣本空間時(shí)，不知道如何

4、將信任度分配給當(dāng)子集是樣本空間時(shí)，不知道如何將信任度分配給每個(gè)元素。每個(gè)元素。概率分配函數(shù)的兩點(diǎn)說(shuō)明概率分配函數(shù)的兩點(diǎn)說(shuō)明如例中如例中A= 紅紅 ， m( 紅紅 )=0.3表示對(duì)紅的精確信表示對(duì)紅的精確信任度是任度是0.3；A= 紅，黃，白紅，黃，白 ， m( 紅，黃，紅，黃，白白 )= 0.2表示這些信任度不知道如何分配給集合中表示這些信任度不知道如何分配給集合中的元素。的元素。l概率分配函數(shù)不是概率。概率分配函數(shù)不是概率。 不滿足概率的歸一性。不滿足概率的歸一性。信任函數(shù)信任函數(shù)定義定義4-34-3：信任函數(shù)：信任函數(shù)(Belief function)(Belief function) B

5、el:Bel:2 2 0,10,1為對(duì)任給的為對(duì)任給的AA Bel(ABel(A)=)=B Am(Bm(B) ) BelBel函數(shù)又稱為下限函數(shù)，表示對(duì)函數(shù)又稱為下限函數(shù)，表示對(duì)A A的總的信的總的信任度。任度。 信任函數(shù)信任函數(shù)接前例：接前例：Bel()=0 Bel(紅紅)=0.3Bel(紅紅,白白)=Bel(紅紅)+Bel(白白)+Bel(紅紅,白白) =0.3+0.1+0.2=0.6Bel(紅紅,白白,黃黃)=Bel(紅紅)+Bel(白白)+Bel(黃黃)+ Bel(紅紅,白白)+Bel(紅紅,黃黃)+Bel(黃黃,白白) +Bel(紅紅,黃黃,白白) =1信任函數(shù)信任函數(shù)BelBel(

6、 ()=m()=m()=0)=0BelBel( ( )=)=BB m(Bm(B)=1)=1似然函數(shù)似然函數(shù)定義定義4-44-4：似然函數(shù)：似然函數(shù)(Plausibility function)(Plausibility function) Pl(A):Pl(A):2 2 0,1 0,1 對(duì)任給的對(duì)任給的AA Pl(APl(A)=1-Bel(A)=1-Bel(A) 似然函數(shù)又稱為不可駁斥函數(shù)或上限函數(shù)。表似然函數(shù)又稱為不可駁斥函數(shù)或上限函數(shù)。表示對(duì)示對(duì)A A非假的信任度。非假的信任度。 似然函數(shù)似然函數(shù)接前例：接前例：Pl(紅紅)=1-Bel(紅紅)=1-Bel(黃黃,白白) =1-Bel(黃黃

7、)-Bel(白白)-Bel(黃黃,白白) =0.9Pl(黃黃,白白)=1-Bel(黃黃,白白)=1-Bel(紅紅) =0.7似然函數(shù)似然函數(shù)可以證明可以證明 Pl(APl(A)=)=AB m(Bm(B) ) 紅紅B m(Bm(B)=m()=m(紅紅)+m()+m(紅紅, ,白白)+m()+m(紅紅, ,黃黃) ) +m( +m(紅紅, ,白白, ,黃黃)=0.3+0.2+0.2+0.2=0.9)=0.3+0.2+0.2+0.2=0.9 黃黃,白白B m(Bm(B)=m()=m(黃黃)+m()+m(白白)+m()+m(紅紅, ,黃黃) ) +m( +m(白白, ,黃黃) +m() +m(紅紅,

8、,白白)+m()+m(紅紅, ,白白, ,黃黃) ) =0+0.1+0+0.2+0.2+0.2=0.7 =0+0.1+0+0.2+0.2+0.2=0.7似然函數(shù)似然函數(shù)Pl(APl(A)-)-AB m(Bm(B)=1-Bel()=1-Bel(A)-A)-AB m(Bm(B) ) =1-(Bel( =1-(Bel(A)+A)+AB m(Bm(B) ) =1-( =1-(B A m(B)+m(B)+AB m(Bm(B) ) =1- =1-B m(Bm(B) ) =0 =0 Pl(APl(A)=)=AB m(Bm(B) )信任函數(shù)與似然函數(shù)的關(guān)系信任函數(shù)與似然函數(shù)的關(guān)系定理定理4-14-1：信任函數(shù)

9、與似然函數(shù)有如下關(guān)系：對(duì)信任函數(shù)與似然函數(shù)有如下關(guān)系：對(duì)任給的任給的AA 有有 Pl(A)Pl(A)Bel(ABel(A) )證明：證明： Bel(A)+Bel(ABel(A)+Bel(A)=)=B Am(B)+m(B)+C Am(Cm(C) ) B m(Bm(B)=1)=1信任函數(shù)與似然函數(shù)的關(guān)系信任函數(shù)與似然函數(shù)的關(guān)系又又 Pl(A)-Bel(APl(A)-Bel(A)=1-Bel()=1-Bel(A)-Bel(A)A)-Bel(A) =1-( =1-(Bel(A)+Bel(A)Bel(A)+Bel(A) 0 0 Pl(APl(A) ) Bel(ABel(A) )使用信任函數(shù)與似然函數(shù)使用

10、信任函數(shù)與似然函數(shù)lBel(ABel(A) )：表示：表示A A為真的信任度，為信任度為真的信任度，為信任度下限。下限。lPl(APl(A) )：表示：表示A A為非假的信任度，為信任度為非假的信任度，為信任度的上限。的上限。使用信任函數(shù)與似然函數(shù)使用信任函數(shù)與似然函數(shù)l表示事物的不確定性可以由事物的這兩個(gè)函數(shù)表示事物的不確定性可以由事物的這兩個(gè)函數(shù)值來(lái)描述，例如值來(lái)描述，例如紅紅 紅紅：0.3,0.9 表示表示紅紅的精確信任度為的精確信任度為0.3，不可駁斥部分為，不可駁斥部分為0.9，而肯定不是，而肯定不是紅紅的為的為0.1典型值的含義典型值的含義lA0,1A0,1：說(shuō)明對(duì)：說(shuō)明對(duì)A A一

11、無(wú)所知。一無(wú)所知。Bel(ABel(A)=0,Pl(A)=1,)=0,Pl(A)=1,說(shuō)明對(duì)說(shuō)明對(duì)A A沒(méi)有信任，對(duì)沒(méi)有信任，對(duì) A A也沒(méi)有信任。也沒(méi)有信任。lA0,0A0,0：說(shuō)明：說(shuō)明A A為假。為假。 Bel(ABel(A)=0,Pl(A)=0)=0,Pl(A)=0， Bel(ABel(A)=1)=1。lA1,1A1,1：說(shuō)明：說(shuō)明A A為真。為真。概率分配函數(shù)的正交和概率分配函數(shù)的正交和定義定義4-54-5：設(shè)：設(shè)m和和n是兩個(gè)不同的概率分配函數(shù)，是兩個(gè)不同的概率分配函數(shù)，其正交和其正交和mn滿足滿足 mnmn( ()=0)=0 mn(Amn(A)=K)=K-1 -1 X X xyx

12、y= =A Am(xm(x) X ) X n(yn(y) ) 其中其中K=1-K=1-xy=xy=m(xm(x) X ) X n(yn(y) )概率分配函數(shù)的正交和概率分配函數(shù)的正交和設(shè)設(shè)mm1 1,m,m2,2,mmn n是是n n個(gè)不同的概率分配函數(shù)，其正個(gè)不同的概率分配函數(shù)，其正交和交和mm1 1 mm2 2 , , , mmn n滿足滿足 mm1 1 mm2 2 , , , mmn n( ()=0)=0 m m1 1 mm2 2 , , , mmn n(A(A) ) =K =K-1 -1 X X Ai=AAi=A1in mmi i(A(Ai i) ) 其中其中K=K=AiAi1in m

13、mi i(A(Ai i) )概率分配函數(shù)的正交和概率分配函數(shù)的正交和例：設(shè)樣本空間例：設(shè)樣本空間=a,ba,b,從不同的知識(shí)來(lái)源得從不同的知識(shí)來(lái)源得 到的概率分配函數(shù)分別為：到的概率分配函數(shù)分別為： mm1 1( (,a,b,a,ba,b,a,b)=(0,0.4,0.5,0.1)=(0,0.4,0.5,0.1) m m2 2( (,a,b,a,ba,b,a,b)=(0,0.6,0.2,0.2)=(0,0.6,0.2,0.2) 求正交和求正交和mm= =mm1 1 mm2 2 ？概率分配函數(shù)的正交和概率分配函數(shù)的正交和解：先求解：先求K K-1-1K K-1-1=1-=1-xy=xy=mm1 1

14、(x) X m(x) X m2 2(y)(y) =1- m =1- m1 1(a)xm(a)xm2 2(b)-m(b)-m1 1(b)xm(b)xm2 2(a)(a) =1-0.3x0.3-0.5x0.6 =1-0.3x0.3-0.5x0.6 =0.61 =0.61 概率分配函數(shù)的正交和概率分配函數(shù)的正交和 m(m()=0)=0 m(am(a)= )= K K-1 -1 xyxy=a=amm1 1(x) X m(x) X m2 2(y)(y) = K = K-1-1(m(m1 1(a) X m(a) X m2 2(a,b)+(a,b)+ m m1 1(a) X m(a) X m2 2(a)+m

15、(a)+m1 1(a,b) X m(a,b) X m2 2(a)(a) =0.54 =0.54 m(bm(b)=0.43)=0.43 m(a,bm(a,b)=0.03)=0.03D-S理論的推理模型理論的推理模型l如前面介紹，可以使用信任函數(shù)和似然函數(shù)表如前面介紹，可以使用信任函數(shù)和似然函數(shù)表示命題示命題A的信任度下限和上限。我們使用同樣的信任度下限和上限。我們使用同樣的方式表示知識(shí)信任度。的方式表示知識(shí)信任度。l似然函數(shù)和信任函數(shù)的計(jì)算是建立在概率分配似然函數(shù)和信任函數(shù)的計(jì)算是建立在概率分配函數(shù)的基礎(chǔ)之上，概率分配函數(shù)不同，結(jié)論會(huì)函數(shù)的基礎(chǔ)之上，概率分配函數(shù)不同，結(jié)論會(huì)不同。不同。一類特殊的

16、概率分配函數(shù)一類特殊的概率分配函數(shù)l設(shè)設(shè) =s s1 1,s ,s2 2, , ,s sn n,m,m為定義在為定義在2上的概率分上的概率分配函數(shù)，且配函數(shù)，且mm滿足：滿足：1.1.m(sm(si i)0,0,對(duì)任給對(duì)任給s si i 2.2. m(sm(si i)1)13.3.m(m( )=1-)=1- m(sm(si i) )4.4.當(dāng)當(dāng)AA ，且，且A A的元素多于的元素多于1 1個(gè)或沒(méi)有元素，則個(gè)或沒(méi)有元素，則m(Am(A)=0)=0。一類特殊的概率分配函數(shù)一類特殊的概率分配函數(shù)l對(duì)上面的概率分配函數(shù)，可以得到信任函數(shù)對(duì)上面的概率分配函數(shù)，可以得到信任函數(shù)和似然函數(shù)的性質(zhì)：和似然函數(shù)

17、的性質(zhì)：1.1.Bel(ABel(A)= )= siAsiAm(m(s si i) ) 2.2.BelBel( ( )=)=sisim(sm(si i) +m() +m( )=1)=13.3.Pl(APl(A)=1-Bel(A)=1- )=1-Bel(A)=1- siAsiAm(sm(si i) =1- ) =1- sisim(sm(si i)+)+siAsiAm(sm(si i)=m()=m( )+)+Bel(ABel(A) )4.4.Pl(Pl( )=1-Bel()=1-Bel( )=1)=1類概率函數(shù)類概率函數(shù)定義定義4-64-6：設(shè)：設(shè) 為有限域，對(duì)任何命題為有限域，對(duì)任何命題AA 其

18、類其類概率函數(shù)為概率函數(shù)為 f(Af(A)=)=Bel(A)+|ABel(A)+|A|/|/| | |Pl(A)-Bel(APl(A)-Bel(A) )其中其中|A|A|和和| | | |表示表示A A和和 中的元素個(gè)數(shù)。中的元素個(gè)數(shù)。類概率函數(shù)的性質(zhì)類概率函數(shù)的性質(zhì)l si si f( f(s si i)=1)=1證明：證明： f(sf(si i)=)=Bel(sBel(si i)+|s)+|si i|/|/| | |Pl(sPl(si i)-Bel(s)-Bel(si i) =m(s =m(si i)+(1/n)m()+(1/n)m( ) ) si si f(sf(si i)= )= si

19、 si m(sm(si i)+m)+m( ( )=1)=1類概率函數(shù)的性質(zhì)類概率函數(shù)的性質(zhì)l對(duì)任何對(duì)任何AA 有有Bel(A)f(A)Pl(ABel(A)f(A)Pl(A) )證明：證明：Pl(A)-Bel(A)0, |A|/|Pl(A)-Bel(A)0, |A|/| |0|0 Bel(A)f(ABel(A)f(A) ) f(A)Bel(A)+Pl(A)-Bel(Af(A)Bel(A)+Pl(A)-Bel(A) ) = =Pl(APl(A) )類概率函數(shù)的性質(zhì)類概率函數(shù)的性質(zhì)l對(duì)任何對(duì)任何AA 有有f( f( A A)=1-f(A)=1-f(A)證明：證明： f( f(A A)=)=Bel(B

20、el(A)+|A)+|A A|/|/| | |Pl(Pl(A)-Bel(A)-Bel(A A) ) | |A|=|A|=| |-|A|-|A| Pl(Pl(A)-Bel(A)-Bel(A A)=m()=m( ) ) Bel(Bel(A A)=1-Bel(A)-m()=1-Bel(A)-m( ) )類概率函數(shù)的性質(zhì)類概率函數(shù)的性質(zhì) f( f(A A)=1-Bel(A)-m()=1-Bel(A)-m( )+(|)+(| |-|A|)/|-|A|)/| |m(|m( ) ) =1-Bel(A)-m( =1-Bel(A)-m( )+m()+m( )-|A|/|)-|A|/| |m(|m( ) ) =1

21、-(Bel(A)+|A|/| =1-(Bel(A)+|A|/| |( |(Pl(A)-Bel(APl(A)-Bel(A) =1-f(A) =1-f(A)類概率函數(shù)的性質(zhì)類概率函數(shù)的性質(zhì)l根據(jù)前面的性質(zhì)可以很容易得到根據(jù)前面的性質(zhì)可以很容易得到1. f( f()=0)=02. f( f( )=1)=13. 對(duì)任何對(duì)任何AA ,0f(A)1,0f(A)1知識(shí)不確定性的表示知識(shí)不確定性的表示lD-SD-S理論中，不確定性知識(shí)的表示形式為理論中，不確定性知識(shí)的表示形式為 if E then H=if E then H=h h1 1,h,h2 2, , ,h hn n CF=c CF=c1 1,c ,c

22、2 2, , ,c cn n 其中：其中：E E為前提條件，它可以是簡(jiǎn)單條件，也可為前提條件，它可以是簡(jiǎn)單條件，也可以是復(fù)合條件；以是復(fù)合條件；H H是結(jié)論，它用樣本空間的子集表示，是結(jié)論，它用樣本空間的子集表示，h h1 1,h,h2 2, , , ,h hn n是該子集的元素；是該子集的元素；CFCF是可信度因子，用集合的方式表示。是可信度因子，用集合的方式表示。 c c1 1,c ,c2 2, , , ,c cn n用來(lái)表示用來(lái)表示h h1 1,h,h2 2, , ,h hn n的可信度。的可信度。證據(jù)不確定性的表示證據(jù)不確定性的表示l證據(jù)的不確定性由證據(jù)的類概率函數(shù)給出。證據(jù)的不確定性

23、由證據(jù)的類概率函數(shù)給出。 CER(E)=CER(E)=f(Ef(E) )不確定性的更新不確定性的更新l設(shè)有知識(shí)設(shè)有知識(shí) if E then H=if E then H=h h1 1,h,h2 2, , ,h hn n CF=c CF=c1 1,c ,c2 2, , ,c cn n 證據(jù)證據(jù)E E的不確定性為的不確定性為CER(E)CER(E)，確定結(jié)論，確定結(jié)論H H的不的不確定性描述確定性描述CER(H)CER(H)，方法如下：，方法如下：1.1.求求H H的概率分配函數(shù)的概率分配函數(shù)m(hm(h1 1 ,h,h2 2 , , ,h hn n )=(c)=(c1 1XCER(E),cXCER

24、(E),c2 2XCERXCER(E),(E), ,c cn nXCER(EXCER(E) )m(m( )=1-m(h)=1-m(hi i) )不確定性的更新不確定性的更新2.求求Bel(H),Pl(HBel(H),Pl(H) )及及f(Hf(H) Bel(HBel(H)=)=m(m(h hi i) ) Pl(HPl(H)=1-Bel()=1-Bel(H)H) f(Hf(H)=)=Bel(H)+|HBel(H)+|H|/|/| |m(|m( ) )3.3.CER(H)=CER(H)=f(Hf(H) )結(jié)論不確定性的合成結(jié)論不確定性的合成如果有兩條知識(shí)支持同一結(jié)論如果有兩條知識(shí)支持同一結(jié)論 if

25、 Eif E1 1 then H=h then H=h1 1,h,h2 2, , ,h hn n CF=c CF=c1 1,c ,c2 2, , ,c cn n if E if E2 2 then H=h then H=h1 1,h,h2 2, , ,h hn n CF=e CF=e1 1,e,e2 2, , ,e,en n 先求出每條知識(shí)的概率分配函數(shù)先求出每條知識(shí)的概率分配函數(shù)mm1 1 , ,mm2 2, ,然后求然后求出兩個(gè)概率分配函數(shù)的正交和出兩個(gè)概率分配函數(shù)的正交和mm1 1 mm2 2以正交和以正交和作為作為H H的概率分配函數(shù)。的概率分配函數(shù)。示例示例設(shè)有如下規(guī)則設(shè)有如下規(guī)則r

26、1: if Er1: if E1 1 andand E E2 2 then A=athen A=a1 1,a,a2 2 CF=0.3,0.5 CF=0.3,0.5r2: if Er2: if E3 3 and (Eand (E4 4 oror E E5 5) then B=b) then B=b1 1 CF=0.7 CF=0.7r3: if Ar3: if A then H=hthen H=h1 1,h,h2 2,h,h3 3 CF=0.1,0.5,0.3 CF=0.1,0.5,0.3r4: if Br4: if B then H=hthen H=h1 1,h,h2 2,h,h3 3 CF=0

27、.4,0.2,0.1 CF=0.4,0.2,0.1用戶給出用戶給出CER(ECER(E1 1)=0.8, CER(E)=0.8, CER(E2 2)=0.6)=0.6CER(ECER(E3 3)=0.9, CER(E)=0.9, CER(E4 4)=0.5, CER(E)=0.5, CER(E5 5)=0.7)=0.7并假定并假定中有中有1010個(gè)元素，求個(gè)元素，求CER(H)=CER(H)=？示例示例1.求求CER(A)CER(A)CER(ECER(E1 1 andand E E2 2)=minCER(E)=minCER(E1 1),CER(E),CER(E2 2)=0.6)=0.6m(am

28、(a1 1,a,a2 2)=(0.6)=(0.6* *0.3,0.60.3,0.6* *0.5)=(0.18,0.3)0.5)=(0.18,0.3)Bel(ABel(A)=0.18+0.3=0.48)=0.18+0.3=0.48Pl(APl(A)=1-Bel()=1-Bel(A)=1-0=1A)=1-0=1f(Af(A)=)=Bel(A)+|ABel(A)+|A|/|/| | |* *( (Pl(A)-Bel(APl(A)-Bel(A) ) =0.48+2/10 =0.48+2/10* *(1-0.48)=0.584(1-0.48)=0.584CER(A)=CER(A)=f(Af(A)=0.5

29、84)=0.584示例示例2.求求CER(B)CER(B)CER(ECER(E3 3 and(Eand(E4 4 or Eor E5 5)=0.7)=0.7m(bm(b1 1)=(0.7)=(0.7* *0.7)=(0.49)0.7)=(0.49)Bel(BBel(B)=0.49)=0.49Pl(BPl(B)=1-Bel()=1-Bel(B B)=1-0=1)=1-0=1f(Af(A)=)=Bel(A)+|ABel(A)+|A|/|/| | |* *( (Pl(A)-Bel(APl(A)-Bel(A) ) =0.49+1/10 =0.49+1/10* *(1-0.49)=0.541(1-0.4