人工智能ArtificialIntellig

1、人工智能Artificial Intelligence,不確定性推理 Uncertainty Reasoning,本章主要內(nèi)容,基本概念 主觀Bayes方法 確定性方法 證據(jù)理論 模糊推理,基本概念(1/3,什么是不確定性推理? 不確定性推理是建立在非經(jīng)典邏輯上的一種推理,是對不確定性知識的運用與處理 是從不確定性的初始證據(jù)出發(fā),通過運用不確定性的知識,最終推出具有一定程度的不確定性但卻合理或者近乎合理的結(jié)論的思維過程 為什么要研究不確定性推理? 日常生活中含有大量的不確定的信息 ES系統(tǒng)中大量的領(lǐng)域知識和專家經(jīng)驗，不可避免的包含各種不確定性,基本概念(2/3,不確定性推理的基本問題: 表示問

2、題:即采用什么方法描述不確定性.一般有數(shù)值表示和非數(shù)值的語義表示方法. 計算問題:主要指不確定性的傳播和更新,也即獲得新信息的過程.主要包括: 已知C(A), AB f(B,A),如何計算C(B) 已知C1(A),又得到C2(A),如何確定C(A) 如何由C(A1),C(A2)計算C(A1A2), C(A1A2) 語義問題: 指的是上述表示和計算的含義是什么,如何進(jìn)行解釋,基本概念(3/3,不確定推理方法的分類 形式化方法:在推理一級擴(kuò)展確定性方法. 邏輯方法:是非數(shù)值方法,采用多值邏輯、非單調(diào)邏輯來處理不確定性 新計算方法:認(rèn)為概率方法不足以描述不確定性,出現(xiàn)了確定性理論,確定性因子,模糊邏

3、輯方法等 新概率方法:在傳統(tǒng)的概率框架內(nèi),采用新的計算工具以確定不確定性描述 非形式化方法:在控制一級上處理不確定性 如制導(dǎo)回溯、啟發(fā)式搜索等等,本章主要內(nèi)容,基本概念 主觀Bayes方法 可信度方法 證據(jù)理論 模糊推理,主觀Bayes方法,1976年提出的，應(yīng)用于地礦勘探專家系統(tǒng)Prospector中 不確定推理系統(tǒng)包括： 不確定性的表示： 規(guī)則/知識 事實/證據(jù) 不確定性的計算 組合證據(jù)的不確定算法 不確定性的傳遞算法 結(jié)論的不確定算法,規(guī)則不確定的表示（1/2,if E then (LS， LN) H (P(H) (1)E是規(guī)則的前提條件，H是結(jié)論，P(H)是H的先驗概率，是指在沒有任何

4、證據(jù)的情況下結(jié)論H為真的概率。 (2)LS是充分性度量：表示E對H的支持程度，取值范圍0,+),其定義為： P(E/H) LS=- P(E/H,規(guī)則不確定的表示（2/2,3)LN是必要性度量：表示E對H的支持程度，取值范圍0,+),其定義為： P(E/H) 1-P(E/H) LN=-=- P(E/H) 1-P(E/H,證據(jù)不確定的表示,對于初始證據(jù)E，由用戶根據(jù)觀察S給出P(E/S). 引入可信度函數(shù)C(E/S): (1)C(E/S)=-5, 表示在S下，E肯定不存在P(E/S)=0 (2)C(E/S)=0, 表示在S與E無關(guān)， P(E/S)=P(E) (3)C(E/S)=5, 表示在S下，E

5、肯定存在，P(E/S)=1 (4)C(E/S)為其他值的時候， P(E/S)可以通過線性插值得到,組合證據(jù)不確定的表示,1)E=E1 E2 En 如果已知P(E1/S), P(En/S), 則： P(En/S)=minP(E1/S), P(En/S) (2)E=E1 E2 En 如果已知P(E1/S), P(En/S), 則： P(En/S)=maxP(E1/S), P(En/S) (3)對于“非”： P(E/S)=1 - P(E/S,不確定性的傳遞算法,主觀Bayes方法推理的任務(wù)就是根據(jù)證據(jù)E的概率P(E)和LS，LN的值，把H的先驗概率P(H)更新為P(H/E)或P(H/E)。 分下面三

6、種情況討論： 證據(jù)肯定存在 證據(jù)肯定不存在 證據(jù)不確定,證據(jù)肯定存在（1/2,證據(jù)肯定存在時：P(E)=P(E/S)=1 P(H/E)=P(H) P(E/H)/P(E) P(H/E)=P(H) P(E/H)/P(E) P(H/E) P(H) P(E/H) - = - - P(H/E) P(H) P(E/H) 引入幾率函數(shù)O(x)定義為： O(x)=P(x)/(1-P(x), P(x)=O(x)/(1+O(x,證據(jù)肯定存在（2/2,O(H/E)=LS O(H) P(H/E)=LS P(H)/(LS-1) P(H) +1) LS的意義： (1)LS1時, O(H/E) O(H), P(H/E)P(

7、H)，說明E的存在將增強H為真的概率。E的存在對H為真是充分的，所以稱LS為充分性度量 (2) LS=1時, O(H/E)=O(H) (3) LS1時, O(H/E) O(H),E導(dǎo)致H為真的可能性下降 (4) LS=0時, O(H/E)=0,E的存在將使H為假,證據(jù)肯定不存在（1/2,證據(jù)肯定不存在時：P(E)=P(E/S)=0，P(E)=1 P(H/E)=P(H) P(E/H)/P(E) P(H/E)=P(H) P(E/H)/P(E) P(H/E) P(H) P(E/H) - = - - P(H/E) P(H) P(E/H) O(H/E)=LN O(H) P(H/E)=LN P(H)/(L

8、N-1) P(H) +1,證據(jù)肯定不存在（2/2,LN的意義： (1)LN1時, O(H/E) O(H), P(H/E)P(H)，說明E的不存在將增強H為真的概率。 (2) LN=1時, O(H/E)=O(H) (3) LN1時, O(H/E) O(H),E的不存在導(dǎo)致H為真的可能性下降，即E的不存在將反對H為真，說明E對H為真的必要性 (4) LN=0時, O(H/E)=0,E的不存在將使H為假。這里也可以看出E對H為真的必要性，所以也稱LN為必要性度量,不確定性的傳遞算法,從上面討論知： (1)若E越是支持H為真時，則應(yīng)使LS越大 (2)若E對H越是必要時，則應(yīng)使LN越小 LS、LN的取值

9、情況：LS 0, LN 0 只能出現(xiàn)： 但不能出現(xiàn)： LS1 LS1, LN1 LS1, LN1 LS1, LN1 LS=LN=1,例一,設(shè)有如下知識： r1: if E1 then (10,1) H1 (0.03) r2: if E2 then (20,1) H2 (0.05) r3: if E3 then (1,0.002) H3 (0.3) 求：當(dāng)證據(jù)存在及不存在時，P(Hi/Ei)及 P(Hi/Ei) 的值各是多少,證據(jù)不確定（1/2,證據(jù)不定時：0P(E/S)1,后驗概率為： P(H/S)=P(H/E) P(E/S)+P(H/E) P(E/S) 分四種情況討論如下： (1)P(E/S

10、)=1 則有P(E/S)=0,證據(jù)肯定存在 (2)P(E/S)=0 則有P(E/S)=1,證據(jù)肯定不存在 (3)P(E/S)=P(E),說明E和S無關(guān) P(H/S)=P(H,證據(jù)不確定（2/2,4)當(dāng)P(E/S)為其他值的時候，通過分段插值計算P(H/S)的值,0,P(E/S,1,P(E,P(H/E,P(H,P(H/E,P(H/S,例二,當(dāng)證據(jù) E必然發(fā)生，H1的先驗概率0.03, H2的先驗概率0.01, 且有規(guī)則: r1: if E then (20,1) H1 r2: if H1 then (300, 0.0001) H2 求：P(H2|E,結(jié)論不確定性的合成,若有n條知識都支持相同的結(jié)

11、論，而且每條知識的前提所對應(yīng)的證據(jù)Ei(i=1,n)都有相應(yīng)的觀察Si與之對應(yīng)，此時只要先對每條知識分別求出O(H/ Si)然后就可用下式求出結(jié)論不確定性的合成： O(H/ S1, ,Sn)= O(H/ S1) O(H/Sn) - - O(H) O(H) O(H,例三,當(dāng)證據(jù)E1、E2、E3、E4必然發(fā)生后， H 的先驗概率為0.03,且有規(guī)則則: r1: if E1 then (20,1) H r2: if E2 then (300,1) H 求：結(jié)論H的概率變化化,本章主要內(nèi)容,基本概念 主觀Bayes方法 可信度方法 證據(jù)理論 模糊推理,可信度方法模型,主要包括： 知識的不確定性表示 證

12、據(jù)的不確定性表示 組合證據(jù)的不確定性表示 不確定性的傳遞算法 結(jié)論不確定性的合成算法,知識的不確定性表示,產(chǎn)生式規(guī)則： If E Then H (CF(H, E) CF(H,E)是該條知識的可信度，稱為可信度因子或規(guī)則強度，表示當(dāng)前提條件E所對應(yīng)的證據(jù)為真時，它對結(jié)論H為真的支持程度。 CF是根據(jù)經(jīng)驗對一個事物或現(xiàn)象為真的可信程度的度量 CF(H,E)取值為：-1,1,知識的不確定性表示(續(xù),CF定義： CF(H,E)=MB(H,E)-MD(H,E) MB:信任增長度，它表示因與前提條件E匹配的證據(jù)的出現(xiàn)，使結(jié)論H為真的信任增長度 MD：不信任增長度，它表示因與前提條件E匹配的證據(jù)的出現(xiàn)，對結(jié)

13、論H的不信任增長度,知識的不確定性表示(續(xù),MB的定義：由條件概率和先驗概率定義 1 若P（H）=1 MB(H,E)= maxP(H|E), P(H) P(H) - 否則 1-P(H) MD的定義： 1 若P（H）=0 MD(H,E)= min P(H|E), P(H) P(H) - 否則 -P(H,知識的不確定性表示(續(xù),MB(H,E)和MD(H,E)是互斥的：即一個證據(jù)不能既增加對H的信任度，又不能同時增加對H的不信任度 當(dāng)MB(H,E) 0 , MD(H,E)=0 當(dāng)MD(H,E) 0, MB(H,E)=0,知識的不確定性表示(續(xù),CF(H,E)的直觀意義： (1)CF(H,E)0,則P

14、(H|E)P(H):E的出現(xiàn)增加了H為真的概率，增加了H為真的可信度 (2)CF(H,E)0,則P(H|E)P(H):E的出現(xiàn)減少了H為真的概率，增加了H為假的可信度 (3)CF(H,E)=0,則P(H|E)=P(H):表示H與E獨立，即E的出現(xiàn)對H沒有影響 CF(H,E)幾個特殊的值： (1)前提真，則結(jié)論必真，即P(H|E)=1,有CF(H,E)=1 (2)前提真，而結(jié)論必假，即P(H|E)=0,有CF(H,E)=-1 (3)前提與結(jié)論無關(guān)，即P(H|E)=P(H), 有CF(H,B)=0,證據(jù)的不確定性表示,證據(jù)的不確定性也用CF來表示 CF值的來源分兩種情況： 初始證據(jù)：由提供證據(jù)的用

15、戶給出 以前的結(jié)論作為新證據(jù)：由傳遞算法推出 證據(jù)的CF取值范圍：-1，1 E肯定為真時：CF(E)=1 E肯定為假時：CF(E)= - 1 對E一無所知時：CF(E)=0 CF(E)0表示E以CF(E)為真 CF(E)0表示E以CF(E)為假,組合證據(jù)不確定性算法,1)E=E1 E2 En 如果已知CF(E1), CF(En), 則： CF(E)=minCF(E1), CF(En) (2)E=E1 E2 En 如果已知CF(E1), CF(En), 則： CF(E)=maxCF(E1), CF(En,不確定性的傳遞算法,已知：CF(E) E H CF(H,E) 則規(guī)定：CF(H)=CF(H,

16、E) max0, CF(E) 規(guī)定：CF(E)= -CF(E) 當(dāng)證據(jù)為假時：CF(H)=0，即該模型沒有考慮證據(jù)為假時對H所產(chǎn)生的影響 當(dāng)證據(jù)為真時，CF(H,E)實際上就是結(jié)論H的可信度CF(H,結(jié)論不確定性合成算法,r1: if E1 then H (CF(H,E1) r2: if E2 then H (CF(H,E2) 求合成的CF(H) (1)首先對每條知識求出CF(H)，即： CF1(H)=CF(H,E1) max0, CF(E1) CF2(H)=CF(H,E2) max0, CF(E2) (2)規(guī)定： CF1(H)+CF2(H)-CF1(H) CF2(H) CF1(H)=0, C

17、F2(H)=0 CF(H)= CF1(H)+CF2(H)+CF1(H) CF2(H) CF1(H)0, CF2(H)0 CF1(H) +CF2(H) 其他,可信度模型- 例一,r1: A1 B1 CF(B1, A1)=0.8 r2: A2 B1 CF(B1, A2)=0.5 r3: B1 A3 B2 CF(B2, B1 A3)=0.8 初始證據(jù) A1 ，A2 ，A3 的CF值均設(shè)為1，而初始未知證據(jù) B1 ，B2 的CF值為0，即對 B1 ，B2 是一無所知的。 求：CF(B1 ) ,CF(B2)的更新值,可信度模型- 例二,r1: A1 B1 CF(B1, A1)=0.8 r2: A2 B1

18、 CF(B1, A2)=0.6 初始證據(jù) A1 ，A2 的CF值均設(shè)為0.5，而初始未知證據(jù) B1 的CF值為0.1。 求：CF(B1 ) 的更新值,本章主要內(nèi)容,基本概念 主觀Bayes方法 確定性方法 證據(jù)理論 模糊推理,證據(jù)理論,主要內(nèi)容： 概率分配函數(shù) 信任函數(shù) 似然函數(shù) 證據(jù)的不確定性度量 規(guī)則的不確定性度量 推理計算,概率分配函數(shù),定義：U為樣本空間，設(shè)函數(shù)M：2U0, 1，且滿足： M() =0 AUM(A)=1 則稱M為2U上的概率分配函數(shù)，M(A)稱為A的基本概率數(shù) (1)M(A)的作用是把U的任意一個子集A都映射為0,1上的一個數(shù)M(A)。它表示證據(jù)對U的子集A成立的一種信

19、任度量，是對U的子集的信任分配。 (2)概率分配函數(shù)不是概率,證據(jù)理論,例： U=紅，黃，藍(lán) 假設(shè)： M(紅)=0.3, M(黃)=0, M(藍(lán))=0.1, M(紅,黃)=0.2, M(紅,藍(lán))=0.2, M(黃,藍(lán))=0.1, M(紅,黃,藍(lán))=0.1, M()=0,信任函數(shù),定義：命題的信任函數(shù)Bel: 2U0, 1，且 Bel(A) = BAM(B) 對所有的AU (1)命題A的信任函數(shù)的值，是A的所有子集的基本概率分配函數(shù)值的和，用來表示對A的總的信任 (2) Bel函數(shù)又稱為下限函數(shù) (3) Bel() = M() =0 Bel(U) = BUM(B) = 1,似然函數(shù),定義：似然函

20、數(shù)Pl: 2U0, 1，且 Pl(A) =1- Bel(A) 對所有的AU (1) Bel(A)表示對A為真的信任度，則 Bel(A)表示對A為真，即A為假的信任度，所以 Pl(A)表示A非假的信任度，它又稱為上限函數(shù)。 (2) Pl(A) =1- Bel(A) = ABM(B) (3) 0 Bel(A) Pl(A) 1 (4) Pl(A) - Bel(A):表示既不信任A，也不信任A的一種度量，可表示對不知道的度量,證據(jù)的不確定性度量,1)以區(qū)間(Bel(A), Pl(A)作為證據(jù)A的不確定性度量：表示了對A信任程度的上限和下限。 A(0,0): 表示A為假 A(0,1): 表示對A一無所知

21、 A(1,1): 表示A為真 (2)以函數(shù)： f1(A)=Bel(A)+(|A| |U|) (Pl(A)-Bel(A) 表示證據(jù)A的不確定性度量。 f1()=0， f1(U)=1 0 f1(A) 1 AU,規(guī)則的不確定性度量,設(shè)U=u1, un,A和B為U的子集，如： A=a1, am, B=b1, bk 規(guī)則表示如下： A B=b1, bk c1, ck (1)B是結(jié)論，用樣本空間的子集表示，b1, bk是該子集中的元素 (2) c1, ck表示規(guī)則的不確定性度量 ，ci表示bi的可信度 (3) ci0， ni=1ci1,推理計算,f1(A1A2) = minf1(A1), f1(A2) f

22、1(A1A2) = maxf1(A1), f1(A2) 已知f1(A) A B =b1, bk c1, ck， 求 f1(B) (1)求出B的概率分配函數(shù) M(B)=M(b1, bk)=f1(A) c1, f1(A) ck M(U)=1 - ki=1 f1(A) ci,推理計算(續(xù),如果有兩條知識支持同一條結(jié)論： A1 B =b1, bk c1, ck， A2 B =b1, bk c1, ck， 則首先分別對每一條知識求出概率分配函數(shù)： M1(b1, bk) M2(b1, bk) 然后由：M=M1M2 求出結(jié)論B的概率分配函數(shù)M,推理計算(續(xù),概率分配函數(shù)的合成定義： 設(shè)M1和M2是兩個概率分

23、配函數(shù)，則合成M=M1M2定義為： M() =0 M(A) =K XY=A M1(X) M2(Y) 其中x,y是U的子集，并且： K-1=1- XY= M1(X) M2(Y) = XY M1(X) M2(Y,推理計算(續(xù),概率分配函數(shù)的合成示例： 例一：設(shè)U=黑，白，且 M1(黑,白,黑,白,)=(0.3, 0.5, 0.2, 0) M2(黑,白,黑,白,)=(0.6, 0.3, 0.1, 0) 例二：設(shè)U=a,b,c,d M1(b,c,d,U)=(0.7, 0.3) M2(a,b,U)=(0.6, 0.4,推理計算(續(xù),2)求出Bel(B) ,Pl(B),f1(B) Bel(B) = ABM

24、(A) Pl(B) =1- Bel(B) f1(B)=Bel(B)+(|B| |U|) (Pl(B)-Bel(B,證據(jù)理論示例,例一： 已知 f1(A1)=0.8, f1(A2)=0.6, |U|=20 A1A2B=b1,b2 (c1,c2)=(0.3,0.5) 求：f1(B) 例二： 已知 f1(A1)=0.53, f1(A2)=0.52, |U|=20 A1B=b1,b2 ,b3 (c1,c2 ,c3)=(0.1,0.5,0,3) A2B=b1,b2 ,b3 (c1,c2 ,c3)=(0.4,0.2,0,1) 求：f1(B,本章主要內(nèi)容,基本概念 主觀Bayes方法 確定性方法 證據(jù)理論

25、模糊推理,模糊推理,處理隨機性的理論基礎(chǔ)是概率論 處理模糊性的基礎(chǔ)是模糊集合論 本節(jié)主要內(nèi)容： 模糊集合與操作 語言變量 模糊推理,模糊集合與操作（1,經(jīng)典集合是清晰的，即： 一個元素x是否屬于某一個集合A是明確的，要么x屬于A，要么x不屬于A，兩者必居其一，而且只能居其一。 C(x)為特征函數(shù),模糊集合與操作（2,例子: Rule: If the temperature is higher than 80F, it is hot; otherwise, it is not hot. Cases: Temperature = 100F Hot Temperature = 80.1F Hot T

26、emperature = 79.9F Not hot Temperature = 50F Not hot 情緒邏輯的不足 The membership function of crisp logic fails to distinguish between members of the same set,模糊集合與操作（3,Conception of Fuzzy Logic Many decision-making and problem-solving tasks are too complex to be defined precisely however, people succeed

27、by using imprecise knowledge Fuzzy logic resembles human reasoning in its use of approximate information and uncertainty to generate decisions,模糊集合與操作（4,Natural Language,Consider: Joe is tall - what is tall? Joe is very tall - what does this differ from tall? Natural language (like most other activi

28、ties in life and indeed the universe) is not easily translated into the absolute terms of 0 and 1,模糊集合與操作（5,Fuzzy logic is a superset of boolean logic It was created by Dr. Lotfi Zadeh in 1960s for the purpose of modeling the uncertainty inherent in natural language In fuzzy logic, it is possible to

29、 have partial truth values. And is an approach to uncertainty that combines real values 01 and logic operations Fuzzy logic is based on the ideas of fuzzy set theory and fuzzy set membership often found in natural (e.g., spoken) language,模糊集合與操作（6,模糊集合：把傳統(tǒng)集合論中由特征函數(shù)決定的絕對隸屬關(guān)系模糊化，把集合（0，1）擴(kuò)散到區(qū)間0，1，以表示元素

30、x隸屬于子集A的模糊程度,模糊集合與操作（7,Fuzzy Set deals with degrees of membership and degrees of truth, it is a set with fuzzy boundaries. In classical set theory; fA(x):X 0,1, where fA(x) = In fuzzy sets; A(x):X 0,1, where A(x) = 1, if x is totally in A; A(x) = 0, if x is not in A; 0 A(x) 1, if x is partly in A,1,

31、 if xA 0, if xA,模糊集合與操作（8,Classical tall men example,模糊集合與操作（9,Crisp and fuzzy sets of tall men,模糊集合與操作（10,Example: “Young” Example: Ann is 28, 0.8 in set “Young” Bob is 35, 0.1 in set “Young” Charlie is 23, 1.0 in set “Young” Unlike statistics and probabilities, the degree is not describing probabi

32、lities that the item is in the set, but instead describes to what extent the item is the set,模糊集合與操作（11,Membership function of fuzzy logic,Age,25,40,55,Young,Old,1,Middle,0.5,DOM Degree of Membership,Fuzzy values,Fuzzy values have associated degrees of membership in the set,0,模糊集合與操作（12,模糊集的邏輯運算 E.g

33、. A = 1.0, 0.20, 0.75 B = 0.2, 0.45, 0.50 A B = MAX(1.0, 0.2), MAX(0.20, 0.45), MAX(0.75, 0.50) = 1.0, 0.45, 0.75,模糊集合與操作（13,模糊集的邏輯運算 E.g. A B = MIN(1.0, 0.2), MIN(0.20, 0.45), MIN(0.75, 0.50) = 0.2, 0.20, 0.50,模糊集合與操作（14,模糊集的邏輯運算 Example. Ac = 1 1.0, 1 0.2, 1 0.75 = 0.0, 0.8, 0.25,語言變量(1,模糊集合的一種應(yīng)用是

34、計算語言學(xué)，目的是對自然語言的語句進(jìn)行計算，就象對邏輯語句進(jìn)行運算一樣。 語言變量可以看作是用某種自然語言和人工語言的詞語或句子來表示變量的值和描述變量間的內(nèi)在聯(lián)系的一種系統(tǒng)化的方法 模糊集合和語言變量可用于量化自然語言的含義，因而可用來處理具有指定值的語言變量。 Fuzzy logic=computing with words,語言變量（2,模糊邏輯的核心概念是語言變量。 模糊邏輯的基本思想是將常規(guī)數(shù)值變量模糊化，使變量成為以定性術(shù)語（也稱語言值）為值域的語言變量,模糊推理（1,A fuzzy rule can be defined as a conditional statement as

35、 below. IF x is A THEN y is B Differences between classical and fuzzy rules. IF height is 1.80 THEN select_for_team In fuzzy rules; IF height is tall THEN select_for_team,模糊推理（2,A fuzzy rule can have multiple antecedents. IF height is tall AND age is small THEN select_for_team Or, another example IF

36、 service is excellent OR food is delicious THEN tip is generous,模糊推理（3,模糊推理過程,Crisp Input,Fuzzy Input,Fuzzy Output,Crisp Output,Fuzzification,Rule Evaluation,Defuzzification,Input Membership Functions,Rules / Inferences,Output Membership Functions,模糊推理（4,常用的隸屬函數(shù),模糊推理（5,模糊化:模糊化借助于輸入模糊集合的隸屬函數(shù)轉(zhuǎn)變輸入值為隸屬度，即模糊化是根據(jù)模糊集合轉(zhuǎn)變輸入值為隸屬度值的過程。 模糊估值:由于模糊控制規(guī)則的部分匹配特性和規(guī)則的前提條件相重疊的事實，通常在一個時刻可能有多于一條的模糊規(guī)則被激活