第五講 不確定與非單調(diào)推理2

1、第五章 不確定與非單調(diào)推理5.1 基本概念5.2 概率方法5.3 主觀Bayes方法5.4 可信度方法5.5 證據(jù)理論5.6 模糊理論5.7 基于框架表示的不確定性推理5.8 基于語義網(wǎng)絡(luò)表示的不確定性推理5.9 非單調(diào)推理5.6 模糊推理5.6.1 模糊命題含有模糊概念、模糊數(shù)據(jù)的語句稱為模糊命題。它的一般表示形式為：xis A 或者 x is A (CF)其中，A是模糊概念或者模糊數(shù)，用相應(yīng)的模糊集及隸屬函數(shù)刻畫； x是論域上的變量，用以代表所論述對象的屬性； CF是該模糊命題的可信度，它既可以是一個(gè)確定的數(shù)，也可以是一個(gè)模糊數(shù)或者模糊語言值。模糊語言值是指表示大小、長短、多少等程度的一些

2、詞匯。如：極大、很大、相當(dāng)大、比較大。模糊語言值同樣可用模糊集描述。5.6.2 模糊知識的表示（1）模糊產(chǎn)生式規(guī)則的一般形式是：IFETHENH(CF,)其中，E是用模糊命題表示的模糊條件；H是用模糊命題表示的模糊結(jié)論；CF是知識的可信度因子，它既可以是一個(gè)確定的數(shù)，也可以是一個(gè)模糊數(shù)或模糊語言值。是匹配度的閾值，用以指出知識被運(yùn)用的條件。例如：IFx is A THEN y is B (CF,)（2）推理中所用的證據(jù)也用模糊命題表示，一般形式為xisA或者xisA(CF)（3）模糊推理要解決的問題：證據(jù)與知識的條件是否匹配：如果匹配，如何利用知識及證據(jù)推出結(jié)論。5.6.3 模糊匹配與沖突消解

3、在模糊推理中，知識的前提條件中的A與證據(jù)中的A不一定完全相同，因此首先必須考慮匹配問題。例如：IF x is 小THENy is 大(0.6) x is 較小兩個(gè)模糊集或模糊概念的相似程度稱為匹配度。常用的計(jì)算匹配度的方法主要有貼近度、語義距離及相似度等。1. 貼近度設(shè)A與B分別是論域U=u1,u2,un上的兩個(gè)模糊集，則它們的貼近度定義為：(A,B)= AB+(1-A B) /2其中( )( )( )( )AiBiAiBiUUA BuuABuu 2. 語義距離(1)海明距離(2)歐幾里得距離(3)明可夫斯基距離(4)切比雪夫距離匹配度為：1-d(A,B)11( , )|( )( )|1( ,

4、 )|( )( )|nAiBiibABad A Buund A Buuduba211( , )( )( )nAiBiid A Buun111( , )|( )( )| ,1qnqAiBiid A Buuqn1( , )max|( )( )|AiBii nd A Buu 3. 相似度(1) 最大最小法(2) 算術(shù)平均法(3) 幾何平均最小法11min( ),( )( , )max( ),( )nAiBiinAiBiiuur A Buu11min( ),( )( , )1( )( )2nAiBiinAiBiiuur A Buu11min( ),( )( , )( )( )nAiBiinAiBiiu

5、ur A Buu(4) 相關(guān)系數(shù)法(5) 指數(shù)法1221111( ) ( )( , )( ) ( ) 11( ),( )nAiABiBinnAiABiBiinnAAiBBiiiuur A Buuuunn1|()()|( , )nAiBiiuur A Be匹配度舉例設(shè)U=a,b,c,dA=0.3/a+0.4/b+0.6/c+0.8/dA=0.2/a+0.5/b+0.6/c+0.7/d貼近度：AB=(0.30.2)(0.40.5)(0.60.6)(0.80.7)=0.7A B=(0.30.2)(0.40.5)(0.60.6)(0.80.7)=0.3(A,B)=1/2AB+(1-A B)=1/20.

6、7+(1-0.3)=0.7海明距離：d(A,B)=1/4(|0.3-0.2|+|0.4-0.5|+|0.6-0.6|+|0.8-0.7|)=0.075(A,B)=1-d(A,B)=1-0.075=0.925相似度：最大最小法：r(A,B)=(0.30.2)+(0.40.5)+(0.60.6)+(0.80.7)/(0.30.2)+(0.40.5)+(0.60.6)+(0.80.7)=1.9/2.2=0.86(1) 分別計(jì)算出每一個(gè)子條件與其證據(jù)的匹配度例如對復(fù)合條件E=x1 is A1 AND x2 is A2 AND x3 is A3及相應(yīng)證據(jù)E:x1 is A1 , x2 is A2 , x

7、3 is A3分別算出Ai與Ai的匹配度match(Ai,Ai),i=1,2,3。(2) 求出整個(gè)前提條件與證據(jù)的總匹配度。目前常用的方法有“取極小”和“相乘”等。match(E,E)=minmatch(A1,A1),match(A2,A2), match(A3,A3)match(E,E)=match(A1,A1)match(A2,A2)match(A3,A3)(3) 檢查總匹配度是否滿足閾值條件，如果滿足就可以匹配，否則為不可匹配。復(fù)合條件的模糊匹配模糊推理中的沖突消解1. 按匹配度大小排序2. 按加權(quán)平均值排序例如，設(shè)U=u1,u2,u3,u4,u5,A=0.9/u1+0.6/u2+0.4

8、/u3B=0.6/u2+0.8/u3+0.5/u4C=0.5/u3+0.8/u4+1/u5D=0.8/u1+0.5/u2+0.1/u3并設(shè)有如下模糊知識：R1:IFx is A THEN y is H1R2:IFx is B THEN y is H2R3:IFx is C THEN y is H3用戶提供的初始證據(jù)為：E: x is Dmatch(A,D)=D(u1)/A(u1)+D(u2)/A(u2)+D(u3)/A(u3)=0.8/0.9+0.5/0.6+0.1/0.4同理可得：match(B,D)=0.8/0+0.5/0.6+0.1/0.8match(C,D)=0.8/0+0.5/0+0

9、.1/0.5以上D與A、B、C的匹配度用模糊集形式表示。下面求匹配度的加權(quán)平均值：AV(match(A,D)=(0.80.9+0.50.6+0.10.4)/(0.9+0.6+0.4)=0.56同理可得：AV(match(B,D)=0.27AV(match(C,D)=0.1于是得到： AV(match(A,D)AV(match(B,D)AV(match(C,D)所以R1是當(dāng)前首先被選用的知識。3. 按廣義順序關(guān)系排序由上例可得：match(A,D)=D(u1)/A(u1)+D(u2)/A(u2)+D(u3)/A(u3)=0.8/0.9+0.5/0.6+0.1/0.4match(B,D)=0.8/

10、0+0.5/0.6+0.1/0.8match(C,D)=0.8/0+0.5/0+0.1/0.5下面以match(A,D)與match(B,D)為例說明廣義順序排序的方法：首先用match(B,D)的每一項(xiàng)分別與match(A,D)的每一項(xiàng)進(jìn)行比較。比較時(shí)D(ui)與D(uj)中取其小者， A(ui)與B(uj)按如下規(guī)則取值：若A(ui)B(uj)則取“1”；若A(ui)0 ，則就認(rèn)為match(A,D)優(yōu)于match(B,D) ，記為match(A,D) match(B,D) 。按這種方法，對match(A,D)與match(B,D)可以得到：0.8/1+0.5/1+0.1/1+0.5/1+

11、0.5/1+0.1/0+0.1/1+0.1/0+0.1/0=0.8/1+0.1/0由于1=0.80=0.1，所以得到：match(A,D) match(B,D)同理可得：match(A,D) match(C,D)match(B,D) match(C,D)最后得到：match(A,D) match(B,D)match(C,D) 由此可知R1應(yīng)該是首先被選用的知識。5.6.4 模糊推理的基本模式1. 模糊假言推理知識：IF x is A THEN y is B證據(jù)：x is A-結(jié)論：y is B對于復(fù)合條件有：知識：IF x1 is A1 AND x2 is A2 ANDAND xn is An

12、 THEN y is B證據(jù)： x1 is A1 ， x2 is A2 ， ， xn is An-結(jié)論：y is B2. 模糊拒取式推理知識：IF x is A THEN y is B證據(jù)：y is B-結(jié)論：x is A知識：IF x is A THEN y is B證據(jù)：y is not B-結(jié)論：x is not A5.6.5 簡單模糊推理知識中只含有簡單條件，且不帶可信度因子的模糊推理稱為簡單模糊推理。合成推理規(guī)則：對于知識IF x is A THEN y is B首先構(gòu)造出A與B之間的模糊關(guān)系R，然后通過R與證據(jù)的合成求出結(jié)論。 如果已知證據(jù)是x is A且A與A可以模糊匹配，則通過

13、下述合成運(yùn)算求取B：B=A R 如果已知證據(jù)是y is B且B與B可以模糊匹配，則通過下述合成運(yùn)算求出A：A=R B構(gòu)造模糊關(guān)系R的方法1. 扎德方法扎德提出了兩種方法：一種稱為條件命題的極大極小規(guī)則；另一種稱為條件命題的算術(shù)規(guī)則，由它們獲得的模糊關(guān)系分別記為Rm和Ra。設(shè)AF(U),BF(V)，其表示分別為且用，分別表示模糊集的笛卡兒乘積、并、交、補(bǔ)及有界和運(yùn)算，則扎德把Rm和Ra分別定義為：( )/,( )/ABUVAuuBuu()()( )( )(1( )/( , )()()1(1( )( )/( , )mABAU VaABU VRA BA Vuvuu vRA VUBuvu v IF x

14、 is A THEN y is B對于模糊假言推理，若已知證據(jù)為x is A則：Bm=A RmBa=A Ra對于模糊拒取式推理，若已知證據(jù)為y is B則：Am=Rm BAa=Ra B扎德法推理舉例(1)例5.8 設(shè)U=V=1,2,3,4,5, A=1/1+0.5/2, B=0.4/3+0.6/4+1/5并設(shè)模糊知識及模糊證據(jù)分別為： IF x is A THEN y is B x is A其中，A的模糊集為：A=1/1+0.4/2+0.2/3則由模糊知識可分別得到Rm與Ra：000.40.61000.40.610.50.50.50.50.50.50.50.911,11111111111111

15、1111111111111111maRR扎德法推理舉例(2)Bm=A Rm =1,0.4,0.2,0,0=0.4,0.4,0.4,0.6,1Ba=A Ra=0.4,0.4,0.4,0.6,1若已知證據(jù)為:y is B,且B=0.2/1+0.4/2+0.6/3+0.5/4+0.3/5,則：Am=Rm B Aa=Ra B=0.5,0.6,0.6,0.6,0.6000.40.610.50.50.50.50.51111111111111110.2000.40.610.40.50.50.50.50.50.60.5,0.5,0.6,0.6,0.6111110.5111110.3111112. Mamdan

16、i方法 IF x is A THEN y is B對于模糊假言推理，Bc= A Rc對于模糊拒取式推理，Ac=Rc B( )( )/( , )cABU VRA Buvu v3. Mizumoto方法米祖莫托等人根據(jù)多值邏輯中計(jì)算T(AB)的定義，提出了一組構(gòu)造模糊關(guān)系的方法，分別記為Rs,Rg,Rsg,Rgs,Rgg,Rss等等。其定義分別為：( )( )/( , )1,( )( )( )( )0,( )( )( )( )/( , )1,( )( )( )( )( ),( )( )sABsU VsABABsABgABgU VgABABgBABRA VUBuvu vuvuvuvRA VUBuvu

17、 vuvuvvuv 設(shè)U=V=1,2,3,4,5, A=1/1+0.5/2, B=0.4/3+0.6/4+1/5 模糊知識： IF x is A THEN y is B 模糊證據(jù)： x is A 其中，A的模糊集為：A=1/1+0.4/2+0.2/3Bs=A Rs=0.2,0.2,0.2,0.4,1Bg=A Rg=0.2,0.2,0.4,0.6,100001000.40.6100011000.411,111111111111111111111111111111sgRR各種模糊關(guān)系的性能分析(1)比較模糊關(guān)系性能所依據(jù)的基本原則：原則1：知識：IF x is A THEN y is B證據(jù)：x

18、is A-結(jié)論：y is B原則2：知識：IF x is A THEN y is B證據(jù)：x is very A-結(jié)論：y is very By is B各種模糊關(guān)系的性能分析(2)原則3：知識：IF x is A THEN y is B證據(jù)：x is more or less A-結(jié)論：y is more or less By is B原則4：知識：IF x is A THEN y is B證據(jù)：x is not A-結(jié)論：y is unknowny is not B以上原則是針對模糊假言推理的。各種模糊關(guān)系的性能分析(3)原則5：知識：IF x is A THEN y is B證據(jù)：y i

19、s not B-結(jié)論：x is not A原則6：知識：IF x is A THEN y is B證據(jù)：y is not very B-結(jié)論：x is not very A各種模糊關(guān)系的性能分析(4)原則7：知識：IF x is A THEN y is B證據(jù)：y is not more or less B-結(jié)論： x is not more or less A原則8：知識：IF x is A THEN y is B證據(jù)： y is B-結(jié)論： x is unknownx is A模糊關(guān)系評測實(shí)例設(shè)U=V=1,2,3,4,5,6,7,8,9,10A=1/1+0.8/2+0.6/3+0.4/4+

20、0.2/5 （?。〣=0.2/4+0.4/5+0.6/6+0.8/7+1/8+1/9+1/10 （大）0000.20.40.60.81110.20.20.20.20.40.60.80.80.80.80.40.40.40.40.40.60.60.60.60.60.60.60.60.60.60.60.60.60.60.60.80.80.80.80.80.80.80.80.80.811111111111111111111111111111111111111111111111111mR0000.20.40.60.81110000.20.40.60.80.80.80.80000.20.40.60.60.

21、60.60.60000.20.40.40.40.40.40.40000.20.20.20.20.20.20.200000000000000000000000000000000000000000000000000cR000000011100000010000000010.2000000010.40.200000010.60.40.20001110.80.60.40.20001110.80.60.40.20001110.80.60.40.20001110.80.60.40.20001110.80.60.40.2000sgR00000001110000001000000001000000001000

22、00000100000011100000001110000000111000000011100000001110000000ssR根據(jù)基本概念擴(kuò)充法，由A可得：very A=1,0.64,0.36,0.16,0.04,0,0,0,0,0more or less A=1,0.89,0.77,0.63,0.45,0,0,0,0,0not A=0,0.2,0.4,0.6,0.8,1,1,1,1,1not very A=0,0.36,0.64,0.84,0.96,1,1,1,1,1not more or less A=0,0.11,0.23,0.37,0.55,1,1,1,1,12( )/AUuu0.

23、5( )/AUuu1( )/AUuu21( )/AUuu0.51( )/AUuu由B可得：very B=0,0,0,0.04,0.16,0.36,0.64,1,1,1more or less B=0,0,0,0.45,0.63,0.77,0.89,1,1,1not B=1,1,1,0.8,0.6,0.4,0.2,0,0,0not very B=1,1,1,0.96,0.84,0.64,0.36,0,0,0not more or less B=1,1,1,0.55,0.37,0.23,0.11,0,0,02( )/BVvv0.5( )/BVvv1( )/BVvv21( )/BVvv0.51( )

24、/BVvv各種模糊關(guān)系符合推理原則情況一覽表原則ABRm Ra Rc Rs Rg Rsg Rgg Rgs Rss Rb R R R* R# R1234AVery AVery Amore or less AMore or less ANot ANot ABVery BBMore or less BBUnknownNot B v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v 5678Not ANot very ANot more or less AUnknownANot BNot very BNot more

25、 or less BBB v v v v v v v v v v v v v v v v v v v v v 5.6.6 模糊三段論推理R1: IF x is A THEN y is BR2: IF y is B THEN z is C-R3: IF x is A THEN z is C其中A、B、C分別是論域U、V、W上的模糊集。如果R3可由R1及 R2推導(dǎo)出來，則稱模糊三段論成立。設(shè)R(A,B),R(B,C)與R(A,C)分別是根據(jù)上述模糊知識得到的模糊關(guān)系，它們分別定義在UV,VW,UW上，如果R(A,B) R(B,C)=R(A,C)則R3就能夠從R1和R2推導(dǎo)出來，此時(shí)稱模糊三段論成立

26、。滿足模糊三段論的模糊關(guān)系在前面討論的15種模糊關(guān)系中，有一些能滿足模糊三段論，有一些不能滿足。設(shè)U=V=W=1,2,3,4,5A=1/1+0.6/2+0.2/3B=0.3/3+0.7/4+1/5C=0.09/3+0.49/4+1/5對Rm由R1，R2，R3分別得到：000.3 0.71111110.4 0.4 0.4 0.6 0.611111( , ),( , )0.8 0.8 0.8 0.8 0.80.70.70.70.70.7111110.30.30.30.49 0.711111000.09 0.491mmRA BR B C000 .0 90 .4 910 .40 .40 .40 .4

27、90 .6(,)0 .80 .80 .80 .80 .811111111110 .30 .30 .30 .4 910 .40 .40 .40 .4 90 .6(,)(,)0 .80 .80 .80 .80 .81111111111mmmRA CRABRBC w顯然，Rm(A,B)Rm(B,C)Rm(A,C)。這說明Rm不滿足模糊三段論。000.30.7111111000.31111111( , ),( ,)00111000.091111111000.090.49111111000.090.491ggRA BRB C000.090.491000.090.491000.090.491000.090

28、.491( ,),( , )( ,)000.0911000.091111111111111111111111gggRA CRA BRB C顯然，Rg(A,B)Rg(B,C)=Rg(A,C)這說明Rg滿足模糊三段論。各種模糊關(guān)系滿足模糊三段論情況表中，“v”表示滿足，“”表示不滿足。模糊關(guān)系Rm Ra Rc Rs Rg Rsg Rgg Rgs Rss Rb R R R* R# R模糊三段論 v v v v v v v v5.6.7 多維模糊推理多維模糊推理是指知識的前提條件是復(fù)合條件的一類推理。其一般模式為：知識：IF x1 is A1 AND x2 is A2 ANDAND xn is An

29、THEN y is B證據(jù)： x1 is A1 x2 is A2 xn is An-結(jié)論：y is B其中，Ai，AiF(Ui);B,BF(V);Ui及V是論域，i=1,2,n。對于多維模糊推理，目前主要有三種處理方法。1. 扎德方法 (Ui=U)該方法的基本思想是：(1)求出A1,A2,An的交集，并記為A。(2)求出A與B之間的模糊關(guān)系R(A,B)，也可記為R(A1,A2,An,B)。(3)求出證據(jù)中A1,A2,An的交集，并記為A。(4)由A與R(A,B)的合成求出B。（該方法要求Ai定義在相同的論域）多維模糊推理舉例例5.9 設(shè)U=V=W=1,2,3,4,5A1=1,0.6,0,0,0

30、, A2=0,1,0.5,0,0, B=0,0,1,0.8,0A1=0.8,0.5,0,0,0, A2=0,0.9,0.5,0,0由此可得:A1A2=0,0.6,0,0,0， A1A2=0,0.5,0,0,0Ba=(A1A2)Ra(A1,A2,B)=0.4,0.4,0.5,0.5,0.412111 110.40.41 10.4(, )111 11111 11111 11aRA A B 2. 祖卡莫托(Tsukamoto)方法知識：IF x1 is A1 AND x2 is A2 ANDAND xn is An THEN y is B證據(jù)： x1 is A1 x2 is A2 xn is An-

31、結(jié)論：y is B（1）首先構(gòu)造各個(gè)子條件與結(jié)論之間的模糊關(guān)系R(Ai,B),i=1,2,n（2）根據(jù)復(fù)合條件中的每一個(gè)子條件求出相應(yīng)的Bi：Bi=AiR(Ai,B),i=1,2,n（3） 對各Bi取交集，從而得到B： B=B1B2Bn3. 蘇更諾(Sugeno)方法該方法通過遞推計(jì)算求出B，具體為：B1=A1 R(A1,B)B2=A2 R(A2,B1)B=Bn=An R(An,Bn-1)11110010000110(,),(,)0,0,0.8,0.5,0111111111111111sssRA BBARA B2122211111100000(,),(,)0,0,0.5,0.5,0001101

32、111111111ssssssRA BBBARA B5.6.8 多重模糊推理所謂多重模糊推理，一般是指知識具有如下表示形式的一種推理：IF x is A1THENy is B1ELSEIF x is A2THENy is B2ELSEIF x is AnTHENy is Bn其中，AiF(U),BiF(V),i=1,2,n。這里只討論它的一種簡單形式：IF x is A THENy is BELSEy is C其中AF(U),B,CF(V)。知識：IF x is A THEN y is B ELSEy is C證據(jù) x is A -結(jié)論：y is D其中A, AF(U); B,C,DF(V)。

33、推理方法：通過A、B、C構(gòu)造UV上的一個(gè)模糊關(guān)系R，然后，通過A與R的合成得到結(jié)論D，即D=A R多重模糊推理中的模糊關(guān)系()()( )( )(1( )( )/( , )()()11( )( )( )( )/( , )mABACU VaABACU VRABACuvuvu vRAVUBAVUCuvuvu v 5.6.9 帶有可信度因子的模糊推理知識：IF x is A THEN y is BCF1證據(jù)： x is A CF2-結(jié)論： y is B CF結(jié)論可信度的計(jì)算：CF=match(A,A)CF1CF2CF=match(A,A)minCF1,CF2CF=match(A,A)max0,CF1+

34、CF2-1CF=minmatch(A,A),CF1,CF2模糊數(shù)取極小的運(yùn)算規(guī)則(min)類似于與模糊數(shù)的四則運(yùn)算。組合證據(jù)知識：IF x1 is A1 AND x2 is A2 ANDAND xn is An THEN y is B CF0證據(jù)： x1 is A1 CF1 x2 is A2 CF2 xn is An CFn-結(jié)論： y is B CF組合證據(jù)的匹配度：match(E,E)=minmatch(A1,A1),match(A2,A2), match(A3,A3)match(E,E)=match(A1,A1)match(A2,A2)match(A3,A3)組合證據(jù)的可信度：CF1 =CF1CF2CFnCF1 =CF1CF2CFn結(jié)論的可信度： CF=match(E,E)CF0CF1結(jié)論不確定性的合成結(jié)論不確定性的合成：假設(shè)根據(jù)兩組證據(jù)及相關(guān)知識分別分別推出了如下兩個(gè)結(jié)論：y is B1 CF1y is B2 CF2則可用如下方法得到它們的合成結(jié)論和可信度因子：B=B1B2CF=CF1+CF2-CF1CF2使用這種方法時(shí)，一般要求兩個(gè)推理序列是相互獨(dú)立的。其它不確定性推理方法5.7 基于框架表示的不確定性推理5.8 基于語義網(wǎng)絡(luò)表示的不確定性推理5.9 非單調(diào)推理5.9.1 非單調(diào)推理的概念單調(diào)推理：S1：已有的知識集 S2：增加新知識后的知識集采用經(jīng)典邏輯的演