人工智能chapter8uncertainty.ppt

1、第八章 不確定知識與推理,概述 非精確性推理 不確定性人工智能的數學基礎 貝葉斯網絡,8.1 概述,知識的不確定性,隨機性 模糊性 自然語言中的不確定性 常識知識的不確定性 知識的其他不確定性,隨機性 以牛頓理論為代表的確定性科學，創(chuàng)造了給世界以精確描繪的方法，將整個宇宙看作是鐘表式的動力學系統(tǒng)，處于確定、和諧、有序的運動之中。 客觀世界上隨機的，映射到人腦的客觀世界，即主觀世界也應該是隨機的。因此，人類在認知過程中表現出的智能和知識，不可避免地伴隨有隨機性。 隨機性無處不在，隨機性使得世界更為復雜，也更為豐富多彩。,8.1 概述,模糊性 直到20世紀，人們才認識到，模糊性并不是壞事。它能夠用

2、較少的代價，傳遞足夠的信息，并能對復雜事物做出高效率的判斷和處理。 模糊性的客觀性 哲學家羅素早在1923年一篇題為Vagueness的論文中明確指出：“認為模糊知識必定是靠不住的，這種看法是大錯特錯的”。 隨著科學技術的發(fā)展，科學家們已經認識到：硬要把模糊事物人為地精確化，不僅會以方法的復雜性為代價，而且會降低結果的意義性。,8.1 概述,自然語言中的不確定性 語言帶有不確定性是很自然的，是人類思維的本質特征之一。 計算機自然語言理解、機器翻譯等研究，從20世紀40年代興起至今已經有60多年的歷史， 人們寄希望于表示概念的語言值的不確定性研究取得突破,8.1 概述,常識知識的不確定性 在人工

3、智能界，常識知識的表示、處理和驗證是非常困難的。 常識知識的相對性 目前，人工智能界有這樣的共識：有無常識是人和機器的根本區(qū)別之一。,8.1 概述,知識的其他不確定性 知識的不完備性 知識的 不協調性 知識的非恒常性,8.1 概述,不確定性知識的表示、處理和模擬，尋找并且形式化地表示不確定性知識中的規(guī)律性，讓機器模擬人類知識客觀世界和人類自身的認知過程，使機器具有不確定性智能，成為人工智能學家的重要任務。,8.1 概述,8.2 非精確性推理,非精確性推理方法研究產生的原因大致如下： 很多原因導致同一結果推理所需的信息不完備背景知識不足信息描述模糊信息中含有噪聲劃分是模糊的推理能力不足解題方案不

4、唯一,ES是通過大量專家知識來取得高水平的問題求解能力。由于專家知識是不確定的，因此ES要達到高性能,必須解決好不確定性問題。 傳統(tǒng)的概率統(tǒng)計方法受限制 放棄傳統(tǒng)程序求解的邏輯完備性,8.2 非精確性推理,Shortliffe等人1975年結合MYCIN系統(tǒng)的建立提出了確定性理論。 DURA等人1976在PROSPECTOR的基礎上給出了概率法。 Dempster Shafter同年提出證據理論。 Zadeh兩年后提出了可能性理論，1983年提出了模糊邏輯。,8.2 非精確性推理,非確定性推理的研究和發(fā)展,MYCIN系統(tǒng)是第一個采用了不確定推理邏輯的專家系統(tǒng)，在20世紀70年代非常有名。 這個

5、系統(tǒng)提出該確定性方法時遵循了下面的原則：（1） 不采用嚴格的統(tǒng)計理論。使用的是一種接近統(tǒng)計理論的近似方法。（2） 用專家的經驗估計代替統(tǒng)計數據（3） 盡量減少需要專家提供的經驗數據，盡量使少量數據包含多種信息。（4） 新方法應適用于證據為增量式地增加的情況。（5） 專家數據的輕微擾動不影響最終的推理結論。,確定性理論,MYCIN 概述,用 戶,解釋模塊,咨詢模塊,知識獲取模塊,感染病專家與知識工程師,知識庫,動態(tài)數據庫 (推理記錄),患者數據庫 (原始數據庫),MYCIN系統(tǒng)結構圖,MYCIN推理策略,采用反向推理和深度優(yōu)先搜索。 診斷治療過程如下 ： (1)確定患者有無細菌性感染。 (2)確

6、定可能引起感染的有機體。 (3)確定對其有抑制作用的藥物。 (4)選擇對治療最合適的藥物。 這四個步驟由目標規(guī)則 來執(zhí)行。,MYCIN知識表示,如：RULE 037 PREMISE: ($AND (NOTKNOWN CONTXT IDENT) (SAME CONTXT GRAM GRAMNEG) (SAME CONTXT MORPH ROD) (SAME CONTXT AIR AEROBIC) ACTION: (CONCLUDE CONTXT CLASS ENTEROBACTERIACEAE TALLY 0.8),可信度是指人們根據以往經驗對某個事物或現象為真的程度的一個判斷，或者說是人們對某

7、個事物或現象為真的相信程度。,可信度的概念,可信度具有一定的主觀性，較難把握。但對某一特定領域，讓該領域專家給出可信度還是可行的。,8.3.2 CF模型,表示形式： 在C-F模型中，知識是用產生式規(guī)則表示的，其一般形式為： IF E THEN H (CF(H, E) 其中，E是知識的前提條件；H是知識的結論；CF(H, E)是知識的可信度。,1. 知識不確定性的表示:,例子： IF 發(fā)燒 AND 流鼻涕 THEN 感冒 (0.8),說明：當某人確實有“發(fā)燒”及“流鼻涕”癥狀時，則有80%的把握是患了感冒。,說明： (1) E可以是單一條件，也可以是復合條件。例如： E=(E1 OR E2) A

8、ND E3 AND E4 (2) H可以是單一結論，也可以是多個結論 (3) CF是知識的靜態(tài)強度，CF(H, E)的取值為-1, 1，表示當E為真時，證據對H的支持程度，其值越大，支持程度越大。 (4) CF(H, E)可以理解為規(guī)則的可信度,可信度的定義 在CF模型中，把CF(H, E)定義為 CF(H, E)=MB(H, E)-MD(H, E),2.可信度的定義與性質,MB: 信任增長度，MB(H, E)定義為:,MD:不信任增長度，MB(H, E)定義為:,MB和MD的關系:,當MB(H, E)0時: P(H|E)P(H) E的出現增加了H的概率 當MD(H, E)0時： P(H|E)

9、P(H) E的出現降低了H的概率,CF(H, E)=MB(H, E)-MD(H, E),可信度的性質: 互斥性 對同一證據，它不可能既增加對H的信任程度，又同時增加對H的不信任程度，這說明MB與MD是互斥的。即有如下互斥性： 當MB(H, E)0時，MD(H, E)=0 當MD(H, E)0時，MB(H, E)=0,值域,典型值 (1) 當CF(H,E)=1時，有P(H/E)=1，它說明由于E所對應證據的出現使H為真。此時，MB(H, E)=1，MD(H, E)=0。 (2) 當CF(H,E)= -1時，有P(H/E)=0，說明由于E所對應證據的出現使H為假。此時，MB(H, E)=0，MD(

10、H,E)=1。 (3)當CF(H,E)= 0時，有MB(H, E)=0、MD(H, E)=0。前者說明E所對應證據的出現不證實H；后者說明E所對應證據的出現不否認H。 (4) 對H的信任增長度等于對非H的不信任增長度,對H的信任增長度等于對非H的不信任增長度 對H的可信度與非H的可信度之和等于0 可信度不是概率 概率滿足：P(H)+P(H)=1 和 0P(H),P(H) 1 但可信度不滿足。,(5)對同一前提E，若支持若干個不同的結論Hi(i=1,2,n)，則：,若：專家給出的知識有如下情況 CF(H1, E)=0.7, CF(H2, E)=0.4,非法，應進行調整或規(guī)范化,證據（E）不確定性

11、的表示： 證據的不確定性也是用可信度來表示的，其取值范圍也為-1,1 若E為初始證據，其值由用戶給出。 若E為中間結論，其值可通過計算得到。 不確定性的含義： 對E，其可信度CF(E)的含義如下： CF(E)=1，證據E肯定它為真 CF(E)=-1，證據E肯定它為假 CF(E)=0，對證據E一無所知 0CF(E)1，證據E以CF(E)程度為真 -1CF(E)0，證據E以CF(E)程度為假,3. 證據不確定性的表示,4. 否定證據不確定性的計算 CF(E)=- CF(E) 5. 組合證據不確定性的計算 “合取”與“析取”兩種基本情況。,析取: 當組合證據是多個單一證據的析取時 即E=E1 OR

12、E2 OR OR En時，若已知CF(E1)，CF(E2)，CF(En)，則 CF(E)=maxCF(E1), CF(E2), ,CF(En),合取: 當組合證據是多個單一證據的組合時 即 E=E1 AND E2 AND AND En時，若已知CF(E1)，CF(E2)，CF(En)，則 CF(E)=minCF(E1), CF(E2), ,CF(En),CF模型中的不確定性推理實際上是從不確定的初始證據出發(fā)，不斷運用相關的不確性知識，逐步推出最終結論和該結論可信度的過程。 每一次運用不確定性知識，都需要由證據的不確定性和知識的不確定性去計算結論的不確定性。,6. 不確定性推理,不確定性的更新公

13、式: CF(H)=CF(H, E)max0, CF(E),若CF(E)0: 若CF(E)=1:,CF(H)=0 即該模型沒考慮E為假對H的影響。,CF(H)=CF(H,E) 即規(guī)則強度CF(H,E)實際上是在E為真時，H的可信度,當有多條知識支持同一個結論，且這些知識的前提相互獨立，結論的可信度又不相同時，可利用不確定性的合成算法求出結論的綜合可信度。 設有知識：IF E1 THEN H (CF(H, E1) IF E2 THEN H (CF(H, E2) 則結論H 的綜合可信度可分以下兩步計算： (1) 分別對每條知識求出其CF(H)。即 CF1(H)=CF(H, E1) max0, CF(

14、E1) CF2(H)=CF(H, E2) max0, CF(E2) (2) 用如下公式求E1與E2對H的綜合可信度,7. 結論不確定性的合成,設有如下一組知識： r1：IF E1 THEN H (0.9) r2：IF E2 THEN H (0.6) r3：IF E3 THEN H (-0.5) r4：IF E4 AND ( E5 OR E6) THEN E1 (0.8) 已知：CF(E2)=0.8，CF(E3)=0.6，CF(E4)=0.5，CF(E5)=0.6, CF(E6)=0.8 求：CF(H)=? 解：由r4得到： CF(E1)=0.8max0, CF(E4 AND (E5 OR E6

15、) = 0.8max0, minCF(E4), CF(E5 OR E6) =0.8max0, minCF(E4), maxCF(E5), CF(E6) =0.8max0, minCF(E4), max0.6, 0.8 =0.8max0, min0.5, 0.8 =0.8max0, 0.5 = 0.4,例子,由r1得到：CF1(H)=CF(H, E1)max0, CF(E1) =0.9max0, 0.4 = 0.36 由r2得到：CF2(H)=CF(H, E2)max0, CF(E2) =0.6max0, 0.8 = 0.48 由r3得到：CF3(H)=CF(H, E3)max0, CF(E3)

16、 =-0.5max0, 0.6 = -0.3 根據結論不精確性的合成算法，CF1(H)和CF2(H)同號，有： CF12(H)和CF3(H)異號，有： 即綜合可信度為CF(H)=0.53,不精確推理過程可以總結如下： 每條規(guī)則RULE和每項事實FACT各自都有一個確定的可信度(數值在-1,1閉區(qū)間內)，給了事實FACT的可信度F，按照規(guī)則RULE的可信度R，即可以如下地自下而上(從樹葉到樹根，前一層的C是后一層的F)計算出各層推斷出結論CONCLUSION 的可信度 CF(自下而上算)：,MYCIN 不精確推理,“與”節(jié)點處的結論可信度C=(推斷規(guī)則的可信度 R)(輸入分支中的 min可信度

17、F或C) “或”節(jié)點處的結論可信度C=(規(guī)則可信度R1)與(輸入分支1的可信度C1)之乘積C1R1+(規(guī)則可信度R2)與 (輸入分支2的可信度C2)之乘積C2R2-(C1R1)(C2R2)。 在推理過程中，一般還規(guī)定有一個統(tǒng)一的閾值，比方MYCIN系統(tǒng)是0.2；凡遇可信度閾值時，即置成0.0，表示談不上可信不可信。所以在推理鏈上，凡遇C0.2者，置成C=0。,C1=min0.8=C20.8=0.24,R9=1.0,C7,C6,C3,C4,C5,C2,R8=0.5,R5=0.75,R10=1.0,R6=1.0,R7=0.5,R4=0.8,F5=0.9,R3=0.9,R1=0.8,R2=0.75,

18、F6=1.0,F8=0.5,F1=0.8,F7=0.5,F4=0.9,F3=0.9,F2=0.4,例：,其中:C2=0.40.75=0.3, C3=0.90.8=0.72 C4=1.00.75+0.751.0- 1.00.750.71.0 =0.93, C5=0.80.5=0.4, C6=min0.5= 0.40.5=0.20, C7=0.51.0+0.51.0- 0.51.01.00.5=0.75. 推理鏈上的可信度計算過程,8.3.不確定性人工智能的數學基礎,人工智能是在數學的基礎上發(fā)展起來的 為了解決人工智能中的各種不確定性問題，同樣需要數學的支持,概率理論 模糊集理論 核函數和主曲線

19、粗糙集理論,* * *,8.3.1 概率理論,概率理論是處理隨機性最好的數學工具,17世紀人們對賭博中隨機現象的研究,20世紀概率論的公理化體系,數理統(tǒng)計、隨機過程的研究,奠基人：Jacob Bernoulli P.S.Laplace, J.W.Lindeberg P.L.Chebyshev,A.A.Markov,A.N.Kolmogorov,K.Pearson:生物統(tǒng)計進行研究 R.Fisher:模型的參數估計方法以及試驗設計方法 R.Brown:布朗運動，隨機過程 A.K.Erlang:Poisson 過程,由概率論、數理統(tǒng)計和隨機過程構成的概率理論，為研究隨機性奠定了數學基礎，也為研究不

20、確定性提供了工具。,8.3.1.1 貝葉斯定理,隨機事件的關系及邏輯運算 集合表示隨機事件 事件A不出現： 事件A包含于時間B： 事件A，B至少出現一個： 事件A，B同時出現：,事件間的運算滿足交換律、結合律、分配律、對偶律,確定事件A的概率P（A）通常有三種計算方法： 古典概率：P（A）=k/m（其中，k為A中所包含的基本事件數，n為基本事件的總數）。 頻率法： P（A）=m/n（其中，n為重復實驗次數，n為事件A出現的次數）。 主觀確定法：P（A）=專家主觀賦值（通常用于不宜大量重復的隨機現象）,條件概率及貝葉斯定理,定義1：隨機 事件的獨立性：設（ ，F，P）是一概率空間，A，B是F中的

21、任意兩個隨機事件，如果 P（AB）=P（A）P（B），則稱A、B是相互獨立的。,一個事件的發(fā)生對另一事件的發(fā)生沒有任何影響，事件才具有獨立性,定義2：設（ ，F，P）是一概率空間，A，B是F中的任意兩個隨機事件，假設P（B）0, 稱 為事件B出現條件下，事件A發(fā)生的條件概率 。,條件概率及貝葉斯定理,條件概率的意義在于：如果在隨機試驗中，已經觀察到了事件B的發(fā)生，那么可以利用事件B發(fā)生的概率，去認識事件A的不確定性。,貝葉斯定理（Bayes） 設事件A1，A2 ，A3 ，An中任意兩個事件都不相交，則對任何事件B有下式成立： 該定理就叫Bayes定理，上式稱為Bayes公式。,條件概率及貝葉斯

22、定理,貝葉斯定理,設Ai是導致事件B發(fā)生的所有可能原因，已知他們的概率為P（Ai）,這些概率被稱為先驗概率; 設Ai在隨機試驗中不能或者沒有被直接觀察到，只能觀察到與之聯系的B的發(fā)生; 在此條件下，對事件Ai出現的可能性作出判斷，即求出關于B的條件概率P（Ai|B），又稱為Ai的后驗概率。,例如：用B代表發(fā)燒，A代表感冒: P（A|B） - P（B|A）,貝葉斯公式給出用先驗概率P（B|A），求后驗概率 P（A|B）的方法,例子：,已知：s表示病人脖子強直； m表示病人患有腦膜炎 p（s|m）=0.5; p(m)=1/50000; p(s)=1/20,p(m|s)=?,p(m|s)=p(s|m

23、)p(m)/p(s)=0.0002,8.3.2 粗糙集理論（Rough Set）,1965年，L. A. Zadeh提出Fuzzy Sets 的概念，試圖通過這一理論解決G.frege的含糊概念。 FS方法：利用隸屬函數描述邊界上的不確定對象。,1982年，波蘭華沙理工大學 Z.Pawlak 教授針對G. frege的邊界線區(qū)域思想提出了Rough Sets理論。 RS方法：把無法確認的個體都歸屬于邊界區(qū)域，把邊界區(qū)域定義為上近似集和下近似集的差集。,Rough set theory is still another approach to vagueness. Similarly to fu

24、zzy set theory it is not an alternative to classical set theory but it is embedded in it. Rough set theory can be viewed as a specific implementation of Freges idea of vagueness, i.e., imprecision in this approach is expressed by a boundary region of a set, and not by a partial membership, like in f

25、uzzy set theory. Rough set concept can be defined by approximations.,1982 Z. Pawlak 波蘭,1 問題,醫(yī)生,癥狀 頭痛？ 肌肉痛？ 體溫？,患??？ 流感？,條件屬性,決策屬性,條件屬性,決策屬性,是,不可分辨關系,RS理論是基于不可分辨關系的（等價關系）。,1 問題,醫(yī)生,癥狀 頭痛？ 肌肉痛？ 體溫？,患??？ 流感？,表達條件屬性等價類和決策屬性等價類的關系（其中存在vague）,在條件屬性下的等價類,在決策屬性下的等價類,b1=p1,p2,p3 b2=p5 b3=p4,p6 b4=p7,X=p1,p4,p5

26、Y=p2,p3,p6,p7,條件屬性下,決策屬性下,決策屬性,是,X=p1,p4,p5,上近似 b1Ub2Ub3,下近似 b1,邊界域 b2Ub3,直觀理解:,對于上近似集外的元素,一定不屬于X,對于邊界域內的元素,可能屬于X,也可能不屬于X,對于下近似內的元素,一定屬于X,Rough Set 的能力,屬性約簡,屬性的重要度,規(guī)則生成,8.4 貝葉斯網絡,根據概率理論的法則建立網絡模型，對不確定性進行推理。 貝葉斯網絡是一系列變量的聯合概率分布的圖形表示。,8.4 .1 貝葉斯網絡的表示,包含兩個部分： 貝葉斯網絡結構圖：有向無環(huán)圖（DAG），其中圖中的每個節(jié)點代表相應的變量，節(jié)點之間的連接關

27、系代表了貝葉斯網絡的條件獨立語義。 節(jié)點和節(jié)點之間的條件概率表（CPT）：一系列的概率值。,命題S(moker)：吸煙者命題C(oal Miner)：煤礦礦井工人命題L(ung Cancer)：他患了肺癌命題E(mphysema)：他患了肺氣腫,貝葉斯網有時也叫因果網，因為可以將連接結點的弧認為是表達了直接的因果關系。,如果一個貝葉斯網絡提供了足夠的條件概率值，足以計算任何給定的聯合概率，我們就稱，它是可計算的，即可推理的。 貝葉斯網的兩個要素：其一為貝葉斯網的結構，也就是各節(jié)點的繼承關系，其二就是條件概率表CPT。若一個貝葉斯網可計算，則這兩個條件缺一不可。,貝葉斯網絡,例：,給定了他們是否

28、給你打電話的證據，估計有人入室行竊的概率,7.4.2 貝葉斯網絡的語義,貝葉斯網絡能表示任意概率分布的同時，它們?yōu)檫@些能用簡單結構表示的分布提供了可計算優(yōu)勢。 假設對于頂點xi，其雙親節(jié)點集為Pai，每個變量xi的條件概率P(xi|Pai)。 則頂點集合X=x1,x2,xn的聯合概率分布可如下計算：,貝葉斯網絡的聯合概率分布,Burglary,Earthquake,P(B),0.001,JohnCalls,Alarm,P(E),0.002,MaryCalls,B E P(A),t t .95,t f .90,f t .30,f f .001,A P(J),t .90,f .05,A P(M),

29、t .70,f .01,計算報警器響了，但既沒有盜賊闖入，也沒有發(fā)生地震，同時John和Mary都給你打電話的概率,P(j m a b e) =P(j|a)P(m|a)P(a|b e) P(b)P(e) =0.90*0.70*0.001*0.999*0.998=0.00062,貝葉斯網絡的聯合概率分布,該等式暗示了早先給定的圖結構有條件獨立語義。 它說明貝葉斯網絡所表示的聯合分布作為一些單獨的局部交互作用模型的結果具有因式分解的表示形式。,7.4.3貝葉斯網的推理模式,因果推理（由上向下推理） 診斷推理 辯解,在確定某個已觀察事件也就是一組證據變量值的某個賦值后，任何概率推理系統(tǒng)的基本任務都是

30、要計算一組查詢變量的后驗概率。,因果推理（由上向下推理）,7.4.3貝葉斯網絡的推理模式,給定患者是一個吸煙者（S），計算他患肺氣腫（E）的概率P(E|S)。,S：推理的證據，E：詢問結點。,P(E|S)=P(E,C|S)+P(E,C|S);/全概率公式 =P(E|C,S)*P(C|S)+P(E|C,S)*P(C|S); /貝葉斯公式 在圖中，C和S并沒有雙親關系，符合條件獨立條件：P(C|S)=P(C), P(C|S) = P(C),由此可得：P(E|S) = P(E|S,C)*P(C)+P(E|C,S)*P(C),P(E,C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)(貝葉斯定理)P(E|C,S)*P(C|S)(反