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

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

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

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

5、肯定存在，P(E/S)=1 (4)C(E/S)為其他值的時候， P(E/S)可以通過線性插值得到,組合證據不確定的表示,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方法推理的任務就是根據證據E的概率P(E)和LS，LN的值，把H的先驗概率P(H)更新為P(H/E)或P(H/E)。 分下面三

6、種情況討論： 證據肯定存在 證據肯定不存在 證據不確定,證據肯定存在（1/2,證據肯定存在時：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) 引入幾率函數O(x)定義為： O(x)=P(x)/(1-P(x), P(x)=O(x)/(1+O(x,證據肯定存在（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導致H為真的可能性下降 (4) LS=0時, O(H/E)=0,E的存在將使H為假,證據肯定不存在（1/2,證據肯定不存在時：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,證據肯定不存在（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的不存在導致H為真的可能性下降，即E的不存在將反對H為真，說明E對H為真的必要性 (4) LN=0時, O(H/E)=0,E的不存在將使H為假。這里也可以看出E對H為真的必要性，所以也稱LN為必要性度量,不確定性的傳遞算法,從上面討論知： (1)若E越是支持H為真時，則應使LS越大 (2)若E對H越是必要時，則應使LN越小 LS、LN的取值

9、情況：LS 0, LN 0 只能出現： 但不能出現： LS1 LS1, LN1 LS1, LN1 LS1, LN1 LS=LN=1,例一,設有如下知識： 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) 求：當證據存在及不存在時，P(Hi/Ei)及 P(Hi/Ei) 的值各是多少,證據不確定（1/2,證據不定時：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,證據肯定存在 (2)P(E/S)=0 則有P(E/S)=1,證據肯定不存在 (3)P(E/S)=P(E),說明E和S無關 P(H/S)=P(H,證據不確定（2/2,4)當P(E/S)為其他值的時候，通過分段插值計算P(H/S)的值,0,P(E/S,1,P(E,P(H/E,P(H,P(H/E,P(H/S,例二,當證據 E必然發生，H1的先驗概率0.03, H2的先驗概率0.01, 且有規則: r1: if E then (20,1) H1 r2: if H1 then (300, 0.0001) H2 求：P(H2|E,結論不確定性的合成,若有n條知識都支持相同的結

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

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

13、論H的不信任增長度,知識的不確定性表示(續,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,知識的不確定性表示(續,MB(H,E)和MD(H,E)是互斥的：即一個證據不能既增加對H的信任度，又不能同時增加對H的不信任度 當MB(H,E) 0 , MD(H,E)=0 當MD(H,E) 0, MB(H,E)=0,知識的不確定性表示(續,CF(H,E)的直觀意義： (1)CF(H,E)0,則P

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

15、戶給出 以前的結論作為新證據：由傳遞算法推出 證據的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)為假,組合證據不確定性算法,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) 則規定：CF(H)=CF(H,

16、E) max0, CF(E) 規定：CF(E)= -CF(E) 當證據為假時：CF(H)=0，即該模型沒有考慮證據為假時對H所產生的影響 當證據為真時，CF(H,E)實際上就是結論H的可信度CF(H,結論不確定性合成算法,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)規定： 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 初始證據 A1 ，A2 ，A3 的CF值均設為1，而初始未知證據 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 初始證據 A1 ，A2 的CF值均設為0.5，而初始未知證據 B1 的CF值為0.1。 求：CF(B1 ) 的更新值,本章主要內容,基本概念 主觀Bayes方法 確定性方法 證據理論 模糊推理,證據理論,主要內容： 概率分配函數 信任函數 似然函數 證據的不確定性度量 規則的不確定性度量 推理計算,概率分配函數,定義：U為樣本空間，設函數M：2U0, 1，且滿足： M() =0 AUM(A)=1 則稱M為2U上的概率分配函數，M(A)稱為A的基本概率數 (1)M(A)的作用是把U的任意一個子集A都映射為0,1上的一個數M(A)。它表示證據對U的子集A成立的一種信

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

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

21、 A(1,1): 表示A為真 (2)以函數： f1(A)=Bel(A)+(|A| |U|) (Pl(A)-Bel(A) 表示證據A的不確定性度量。 f1()=0， f1(U)=1 0 f1(A) 1 AU,規則的不確定性度量,設U=u1, un,A和B為U的子集，如： A=a1, am, B=b1, bk 規則表示如下： A B=b1, bk c1, ck (1)B是結論，用樣本空間的子集表示，b1, bk是該子集中的元素 (2) c1, ck表示規則的不確定性度量 ，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的概率分配函數 M(B)=M(b1, bk)=f1(A) c1, f1(A) ck M(U)=1 - ki=1 f1(A) ci,推理計算(續,如果有兩條知識支持同一條結論： A1 B =b1, bk c1, ck， A2 B =b1, bk c1, ck， 則首先分別對每一條知識求出概率分配函數： M1(b1, bk) M2(b1, bk) 然后由：M=M1M2 求出結論B的概率分配函數M,推理計算(續,概率分配函數的合成定義： 設M1和M2是兩個概率分

23、配函數，則合成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,推理計算(續,概率分配函數的合成示例： 例一：設U=黑，白，且 M1(黑,白,黑,白,)=(0.3, 0.5, 0.2, 0) M2(黑,白,黑,白,)=(0.6, 0.3, 0.1, 0) 例二：設U=a,b,c,d M1(b,c,d,U)=(0.7, 0.3) M2(a,b,U)=(0.6, 0.4,推理計算(續,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,證據理論示例,例一： 已知 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,本章主要內容,基本概念 主觀Bayes方法 確定性方法 證據理論

25、模糊推理,模糊推理,處理隨機性的理論基礎是概率論 處理模糊性的基礎是模糊集合論 本節主要內容： 模糊集合與操作 語言變量 模糊推理,模糊集合與操作（1,經典集合是清晰的，即： 一個元素x是否屬于某一個集合A是明確的，要么x屬于A，要么x不屬于A，兩者必居其一，而且只能居其一。 C(x)為特征函數,模糊集合與操作（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,模糊集合：把傳統集合論中由特征函數決定的絕對隸屬關系模糊化，把集合（0，1）擴散到區間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,模糊集合的一種應用是

34、計算語言學，目的是對自然語言的語句進行計算，就象對邏輯語句進行運算一樣。 語言變量可以看作是用某種自然語言和人工語言的詞語或句子來表示變量的值和描述變量間的內在聯系的一種系統化的方法 模糊集合和語言變量可用于量化自然語言的含義，因而可用來處理具有指定值的語言變量。 Fuzzy logic=computing with words,語言變量（2,模糊邏輯的核心概念是語言變量。 模糊邏輯的基本思想是將常規數值變量模糊化，使變量成為以定性術語（也稱語言值）為值域的語言變量,模糊推理（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,常用的隸屬函數,模糊推理（5,模糊化:模糊化借助于輸入模糊集合的隸屬函數轉變輸入值為隸屬度，即模糊化是根據模糊集合轉變輸入值為隸屬度值的過程。 模糊估值:由于模糊控制規則的部分匹配特性和規則的前提條件相重疊的事實，通常在一個時刻可能有多于一條的模糊規則被激活