第5章不確定性推理

1、第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)理論證據(jù)理論1第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)理論證據(jù)理論2概述n不精確思維并非專家的習(xí)慣或愛好所至不精確思維并非專家的習(xí)慣或愛好所至, 而而是客觀現(xiàn)實(shí)的要求。是客觀現(xiàn)實(shí)的要求。q很多原因?qū)е峦唤Y(jié)果很多原因?qū)е峦唤Y(jié)果q推理所需的信息不完備推理所需的信息不完備q背景知識(shí)不足背景知識(shí)不足q信息描述模糊信息描述模糊q信息中含有噪聲信息中含有噪聲q規(guī)劃是模糊的規(guī)劃是模糊的q推理

2、能力不足推理能力不足q解題方案不唯一解題方案不唯一 3在人類的知識(shí)和思維行為中, 精確性只是相對(duì)的, 不精確性才是絕對(duì)的。知識(shí)工程需要各種適應(yīng)不同類的不精確性特點(diǎn)的不精確性知識(shí)描述方法和推理方法。幾個(gè)不確定性n證據(jù)的不確定性證據(jù)的不確定性q歧義性；不完全性；不精確性；模糊性；可信性；歧義性；不完全性；不精確性；模糊性；可信性；隨機(jī)性；不一致性隨機(jī)性；不一致性n規(guī)則的不確定性規(guī)則的不確定性q證據(jù)的組合的不確定性證據(jù)的組合的不確定性q規(guī)則自身的不確定性規(guī)則自身的不確定性q規(guī)則結(jié)論的不確定性規(guī)則結(jié)論的不確定性n推理的不確定性推理的不確定性4概述-表示的3方面問(wèn)題n不確定問(wèn)題的數(shù)學(xué)模型表示的不確定問(wèn)題

3、的數(shù)學(xué)模型表示的3方面問(wèn)題方面問(wèn)題q表示問(wèn)題：表示問(wèn)題：n表達(dá)要清楚。表示方法規(guī)則不僅僅是數(shù)表達(dá)要清楚。表示方法規(guī)則不僅僅是數(shù), 還要有語(yǔ)義描述。還要有語(yǔ)義描述。q計(jì)算問(wèn)題：計(jì)算問(wèn)題：n不確定性的傳播和更新。也是獲取新信息的過(guò)程。不確定性的傳播和更新。也是獲取新信息的過(guò)程。5不確定性推理例子例如例如, 對(duì)于如下的推理過(guò)程：對(duì)于如下的推理過(guò)程：nR1：A1 A2B1nR2：A2 A3 B2nR3：B1BnR4：B2B在描述這些規(guī)則時(shí)采用的都是不確定性知識(shí)在描述這些規(guī)則時(shí)采用的都是不確定性知識(shí)表示方式表示方式67推理樹結(jié)果圖 A A1 1A A2 2A A3 3ORORANDANDB B1 1B

4、B2 2B BR R1 1R R2 2R R3 3R R4 4f f1 1f f4 4f f3 3f f2 2概述-表示的3方面問(wèn)題q語(yǔ)義問(wèn)題：將各個(gè)公式解釋清楚語(yǔ)義問(wèn)題：將各個(gè)公式解釋清楚。語(yǔ)義問(wèn)題：如何解釋表示和計(jì)算的含義語(yǔ)義問(wèn)題：如何解釋表示和計(jì)算的含義, 目前多用概率方法。目前多用概率方法。如：如：f(B, A)可理解為當(dāng)前提可理解為當(dāng)前提A為真時(shí)結(jié)論為真時(shí)結(jié)論B為真的一種影響程度為真的一種影響程度, C(A)可理解為可理解為A為真的程度。為真的程度。特別關(guān)心的是特別關(guān)心的是f(B, A)的值：的值：1)A(T) B(T), f(B, A)=?2)A(T) B(F), f(B, A)=

5、?3)B 獨(dú)立于獨(dú)立于A, f(B, A)=?對(duì)對(duì)C(A)關(guān)心的是：關(guān)心的是：1)A為為T, C(A)？2)A為為F, C(A)？ T：True, F：False8概述-分類(1)不確定性推理方法可分為形式化方法和非形式化方不確定性推理方法可分為形式化方法和非形式化方法。法。n形式化方法有形式化方法有邏輯法、新計(jì)算法和新概率法邏輯法、新計(jì)算法和新概率法。邏。邏輯法是非數(shù)值方法輯法是非數(shù)值方法, 采用多值邏輯和非單調(diào)邏輯采用多值邏輯和非單調(diào)邏輯來(lái)處理不確定性。新計(jì)算法認(rèn)為概率法不足以描來(lái)處理不確定性。新計(jì)算法認(rèn)為概率法不足以描述 不 確 定 性述 不 確 定 性 , 從 而 出 現(xiàn) 了 證 據(jù)

6、理 論從 而 出 現(xiàn) 了 證 據(jù) 理 論 ( 也 叫也 叫DempsterShafter, D-S方法方法), 確定性方法確定性方法(CF法法)以及模糊邏輯方法以及模糊邏輯方法。傳統(tǒng)的有基于概率理論。傳統(tǒng)的有基于概率理論的貝葉斯網(wǎng)絡(luò)等。新的貝葉斯網(wǎng)絡(luò)等。新概率法試圖在傳統(tǒng)的概率論概率法試圖在傳統(tǒng)的概率論框架內(nèi)框架內(nèi), 采用新的計(jì)算方法以適應(yīng)不確定性描述。采用新的計(jì)算方法以適應(yīng)不確定性描述。n非形式化方法是指非形式化方法是指啟發(fā)性方法啟發(fā)性方法, 對(duì)不確定性沒(méi)有對(duì)不確定性沒(méi)有給出明確的概念。給出明確的概念。 9概述-分類(2)不確定推理方法：工程方法、控制方法和并行確定不確定推理方法：工程方法、

7、控制方法和并行確定性法。性法。n工程法是將問(wèn)題簡(jiǎn)化為忽略哪些不確定性因素。工程法是將問(wèn)題簡(jiǎn)化為忽略哪些不確定性因素。n控制法是利用控制策略來(lái)消除不確定性的影響控制法是利用控制策略來(lái)消除不確定性的影響, 如啟發(fā)式的搜索方法。如啟發(fā)式的搜索方法。n并行確定性法是把不確定性的推理分解為兩個(gè)相并行確定性法是把不確定性的推理分解為兩個(gè)相對(duì)獨(dú)立的過(guò)程：一個(gè)過(guò)程不計(jì)不確定性采用標(biāo)準(zhǔn)對(duì)獨(dú)立的過(guò)程：一個(gè)過(guò)程不計(jì)不確定性采用標(biāo)準(zhǔn)邏輯進(jìn)行推理；另一過(guò)程是對(duì)第一個(gè)過(guò)程的結(jié)論邏輯進(jìn)行推理；另一過(guò)程是對(duì)第一個(gè)過(guò)程的結(jié)論加以不確定性的度量。前一過(guò)程決定信任什么加以不確定性的度量。前一過(guò)程決定信任什么, 后一過(guò)程決定對(duì)它的信

8、任程度。后一過(guò)程決定對(duì)它的信任程度。 10第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)理論證據(jù)理論11第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)理論證據(jù)理論12概率論基礎(chǔ)n概率論是研究隨機(jī)現(xiàn)象中數(shù)量規(guī)律的科學(xué)。概率論是研究隨機(jī)現(xiàn)象中數(shù)量規(guī)律的科學(xué)。所謂隨機(jī)現(xiàn)象是指在相同的條件下重復(fù)進(jìn)行所謂隨機(jī)現(xiàn)象是指在相同的條件下重復(fù)進(jìn)行某種實(shí)驗(yàn)時(shí)某種實(shí)驗(yàn)時(shí), 所得實(shí)驗(yàn)結(jié)果不一定完全相同所得實(shí)驗(yàn)結(jié)果不一定完全相同且不可預(yù)知的現(xiàn)象。眾所周知的是

9、擲硬幣的且不可預(yù)知的現(xiàn)象。眾所周知的是擲硬幣的實(shí)驗(yàn)。人工智能所討論的不確定性現(xiàn)象實(shí)驗(yàn)。人工智能所討論的不確定性現(xiàn)象, 雖雖然不完全是隨機(jī)的過(guò)程然不完全是隨機(jī)的過(guò)程, 但是實(shí)踐證明但是實(shí)踐證明, 采用采用概率論的思想方法考慮能夠得到較好的結(jié)果。概率論的思想方法考慮能夠得到較好的結(jié)果。在這節(jié)中我們簡(jiǎn)單給出概率論的基本概念和在這節(jié)中我們簡(jiǎn)單給出概率論的基本概念和貝葉斯定理。貝葉斯定理。 13概率論基礎(chǔ)(隨機(jī)事件)n隨機(jī)實(shí)驗(yàn)隨機(jī)實(shí)驗(yàn)：隨機(jī)實(shí)驗(yàn)是一個(gè)可觀察結(jié)果的：隨機(jī)實(shí)驗(yàn)是一個(gè)可觀察結(jié)果的人工或自然的過(guò)程人工或自然的過(guò)程, 其產(chǎn)生的結(jié)果可能不止其產(chǎn)生的結(jié)果可能不止一個(gè)一個(gè), 且不能事先確定會(huì)產(chǎn)生什么結(jié)果

10、。且不能事先確定會(huì)產(chǎn)生什么結(jié)果。 n樣本空間樣本空間：樣本空間是一個(gè)隨機(jī)實(shí)驗(yàn)的全：樣本空間是一個(gè)隨機(jī)實(shí)驗(yàn)的全部可能出現(xiàn)的結(jié)果的集合部可能出現(xiàn)的結(jié)果的集合, 通常記作通常記作, 中中的點(diǎn)的點(diǎn)(即一個(gè)可能出現(xiàn)的實(shí)驗(yàn)結(jié)果即一個(gè)可能出現(xiàn)的實(shí)驗(yàn)結(jié)果)成為樣本成為樣本點(diǎn)點(diǎn), 通常記作通常記作。n隨機(jī)事件隨機(jī)事件：隨機(jī)事件是一個(gè)隨機(jī)實(shí)驗(yàn)的一：隨機(jī)事件是一個(gè)隨機(jī)實(shí)驗(yàn)的一些可能結(jié)果的集合些可能結(jié)果的集合, 是樣本空間的一個(gè)子集。是樣本空間的一個(gè)子集。常用大寫字母常用大寫字母A, B, C, 表示。表示。 14概率論基礎(chǔ)(事件間的關(guān)系與運(yùn)算 )n兩個(gè)事件兩個(gè)事件A與與B可能有以下幾種特殊關(guān)系：可能有以下幾種特殊關(guān)

11、系：q包含包含：若事件：若事件B發(fā)生則事件發(fā)生則事件A也發(fā)生也發(fā)生, 稱稱“A包含包含B”, 或或“B含于含于A”, 記作記作A B或或B A。q等價(jià)等價(jià)：若：若A B且且B A, 即即A與與B同時(shí)發(fā)生或同時(shí)不發(fā)生同時(shí)發(fā)生或同時(shí)不發(fā)生, 則稱則稱A與與B等價(jià)等價(jià), 記作記作A=B。q互斥互斥：若：若A與與B不能同時(shí)發(fā)生不能同時(shí)發(fā)生, 則稱則稱A與與B互斥互斥, 記作記作AB=q對(duì)立對(duì)立：若：若A與與B互斥互斥, 且必有一個(gè)發(fā)生且必有一個(gè)發(fā)生, 則稱則稱A與與B對(duì)立對(duì)立, 記記作或作或, 又稱又稱A為為B的余事件的余事件, 或或B為為A的余事件。的余事件。n任意兩個(gè)事件不一定會(huì)是上述幾種關(guān)系中的

12、一任意兩個(gè)事件不一定會(huì)是上述幾種關(guān)系中的一種。種。 15概率論基礎(chǔ)(事件間的關(guān)系與運(yùn)算 )n設(shè)設(shè)A, B, A1, A2, An為一些事件為一些事件, 它們有下述它們有下述的運(yùn)算：的運(yùn)算：q交交：記：記C=“A與與B同時(shí)發(fā)生同時(shí)發(fā)生”, 稱為事件稱為事件A與與B的交的交, C=|A且且B, 記作或。記作或。 類似地用表示事件類似地用表示事件“n個(gè)事件個(gè)事件A1, A2, An同時(shí)發(fā)生同時(shí)發(fā)生”。q并并：記：記C=“A與與B中至少有一個(gè)發(fā)生中至少有一個(gè)發(fā)生”, 稱為事件稱為事件A與與B的的并并, C=|A或或B, 記作。記作。 類似地用表示事件類似地用表示事件“n個(gè)事件個(gè)事件A1, A2, An

13、中至少有一個(gè)中至少有一個(gè)發(fā)生發(fā)生”。q差差：記：記C=“A發(fā)生而發(fā)生而B不發(fā)生不發(fā)生”, 稱為事件稱為事件A與與B的差的差, C=|A但但B, 記作或。記作或。q求余求余：16AA概率論基礎(chǔ)(運(yùn)算的性質(zhì) )n事件的運(yùn)算有以下幾種性質(zhì)：事件的運(yùn)算有以下幾種性質(zhì)：q交換律：交換律：A B=B A A B=B Aq結(jié)合律：結(jié)合律： (A B) C=A (B C) (A B) C=A (B C)q分配律：分配律： (A B)C=(AC) (BC) (A B) C=(A C) (B C)q摩根律：摩根律： ( Ai)= Ai ( Ai)= Ain事件計(jì)算的優(yōu)先順序?yàn)椋呵笥嗍录?jì)算的優(yōu)先順序?yàn)椋呵笥? 交

14、交, 差和并。差和并。 17概率論基礎(chǔ)(概率定義 )n定義：設(shè)定義：設(shè)為一個(gè)隨機(jī)實(shí)驗(yàn)的樣本空間為一個(gè)隨機(jī)實(shí)驗(yàn)的樣本空間, 對(duì)對(duì)上的任意事件上的任意事件A, 規(guī)定一個(gè)實(shí)數(shù)與之對(duì)應(yīng)規(guī)定一個(gè)實(shí)數(shù)與之對(duì)應(yīng), 記為記為P(A), 滿足以下三條基本性質(zhì)滿足以下三條基本性質(zhì), 稱為事稱為事件件A發(fā)生的概率：發(fā)生的概率：q0 P(A) 1qP( )=1 P( )=0q若二事件若二事件AB互斥互斥, 即即AB= , 則則P(A B)=P(A)+P(B)n以上三條基本規(guī)定是符合常識(shí)的。以上三條基本規(guī)定是符合常識(shí)的。 18, 概率論基礎(chǔ)(概率性質(zhì) )n定義：設(shè)定義：設(shè)An, n=1, 2, 為一組有限或可列為一組有

15、限或可列無(wú)窮多個(gè)事件無(wú)窮多個(gè)事件, 兩兩不相交兩兩不相交, 且且 An=, 則稱事則稱事件族件族An, n=1, 2, 為樣本空間為樣本空間的一個(gè)完的一個(gè)完備事件族備事件族, 又若對(duì)任意事件又若對(duì)任意事件B有有BAn=An或或, n=1, 2, , 則稱則稱An, n=1, 2, 為基本事件為基本事件族。族。n完備事件族與基本事件族有如下的性質(zhì)：完備事件族與基本事件族有如下的性質(zhì)： 定理：若定理：若An, n=1, 2, 為一完備事件族為一完備事件族, 則則 P(An)=1, 且對(duì)于一事件且對(duì)于一事件B有有P(B)= P(AnB)n有若有若An, n=1, 2, 為一基本事件族為一基本事件族,

16、 則則nP(B)= An BP(An)19, 概率論基礎(chǔ)(統(tǒng)計(jì)概率性質(zhì) )n對(duì)任意事件對(duì)任意事件A, 有有0 P(A) 1n必然事件必然事件的概率的概率P() =1, 不可能事件不可能事件的概率的概率P() = 0n對(duì)任意事件對(duì)任意事件A, 有有P( A)=1- P(A)n設(shè)事件設(shè)事件A1, A2, An(kn)是兩兩互不相容的事是兩兩互不相容的事件件, 即有即有, 則則qP( i=1kAi)=P(A1)+P(Ak )n設(shè)設(shè)A, B是兩事件是兩事件, 則則qP(A B)=P(A)+P(B)-P(A B)20, 概率論基礎(chǔ)(條件概率 )n定義：設(shè)定義：設(shè)A, B為事件且為事件且P(A)0, 稱稱

17、 P(B|A)=P(AB)/P(A)n為事件為事件A已發(fā)生的條件下已發(fā)生的條件下, 事件事件B的條件概的條件概率率, P(A)在概率推理中稱為在概率推理中稱為邊緣概率邊緣概率。簡(jiǎn)稱。簡(jiǎn)稱P(B|A)為給定為給定A時(shí)時(shí)B發(fā)生的概率。發(fā)生的概率。nP(AB)稱為稱為A與與B的的聯(lián)合概率聯(lián)合概率。有聯(lián)合概率。有聯(lián)合概率公式：公式：P(AB)=P(B|A)P(A)21概率論基礎(chǔ)(條件概率性質(zhì) )n0 P(B|A) 1 nP( |A)=1, P( |A)=0n若若B1B2= , 則則qP(B1+B2|A)=P(B1|A)+P(B2|A)n乘法公式：乘法公式：P(AB)=P(A)P(B|A)P(A1An)

18、=P(A1)P(A2|A1)P(An|A1An-1)n全概率公式：設(shè)全概率公式：設(shè)A1, A2, An互不相交互不相交, Ai= , 且且P(Ai)0, 則對(duì)于任意事件則對(duì)于任意事件A有有P(A)= P(Ai)P(A|Ai)22概率論基礎(chǔ)(貝葉斯定理 )n設(shè)設(shè)A, B1, B2, , Bn為一些事件為一些事件, P(A)0, B1, B2, , Bn互不相交互不相交, P(Bi)0, i=1, 2, , n, 且且 P(Bi)=1, 則對(duì)于則對(duì)于k=1, 2, , n, n貝葉斯公式容易由條件概率的定義貝葉斯公式容易由條件概率的定義, 乘法公式乘法公式和全概率公式得到。在貝葉斯公式中和全概率公

19、式得到。在貝葉斯公式中, P(Bi), i=1, 2, , n稱為稱為先驗(yàn)概率先驗(yàn)概率, 而而P(Bi|A) i=1, 2, , n稱為稱為后驗(yàn)概率后驗(yàn)概率也是條件概率。也是條件概率。 23() (|)(|)() (|)kkkiiiP B P A BP BAP B P A B).(,005. 0)(,005. 0,.95. 0)(,95. 0)(,:,ACPCPCAPCAPCA試試求求即即的的概概率率為為設(shè)設(shè)被被試試驗(yàn)驗(yàn)的的人人患患有有癌癌癥癥進(jìn)進(jìn)行行普普查查現(xiàn)現(xiàn)在在對(duì)對(duì)自自然然人人群群有有則則有有癌癌癥癥”表表示示事事件件“被被診診斷斷者者患患以以為為陽(yáng)陽(yáng)性性”表表示示事事件件“試試驗(yàn)驗(yàn)反反

20、應(yīng)應(yīng)若若以以驗(yàn)驗(yàn)具具有有如如下下的的效效果果某某種種診診斷斷癌癌癥癥的的試試根根據(jù)據(jù)以以往往的的臨臨床床記記錄錄 解解,95. 0)( CAP因?yàn)橐驗(yàn)?995. 0)(,005. 0)( CPCP,05. 0)(1)( CAPCAP24由由貝葉斯公式得所求概率為貝葉斯公式得所求概率為)()()()()()()(CPCAPCPCAPCPCAPACP .087. 0 即平均即平均1000個(gè)具有陽(yáng)性反應(yīng)的人中大約只有個(gè)具有陽(yáng)性反應(yīng)的人中大約只有87人人患有癌癥患有癌癥.25第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)

21、理論證據(jù)理論26第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)理論證據(jù)理論27貝葉斯網(wǎng)絡(luò)n二十世紀(jì)八十年代貝葉斯網(wǎng)絡(luò)二十世紀(jì)八十年代貝葉斯網(wǎng)絡(luò)(Bayes Network)成功地應(yīng)用于成功地應(yīng)用于專家系統(tǒng)專家系統(tǒng), 成為表示不確定性專家知識(shí)和推理的一種流行的方成為表示不確定性專家知識(shí)和推理的一種流行的方法?；谪惾~斯方法的貝葉斯網(wǎng)絡(luò)是一種適應(yīng)性很廣的手段和法?；谪惾~斯方法的貝葉斯網(wǎng)絡(luò)是一種適應(yīng)性很廣的手段和工具工具, 具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)。在綜合先驗(yàn)信息具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)。在綜合先驗(yàn)信息(領(lǐng)域知識(shí)領(lǐng)域知識(shí)

22、)和數(shù)據(jù)樣本信息的前提下和數(shù)據(jù)樣本信息的前提下, 還可避免只使用先驗(yàn)信息可能帶來(lái)還可避免只使用先驗(yàn)信息可能帶來(lái)的主觀偏見。雖然很多貝葉斯網(wǎng)絡(luò)涉及的學(xué)習(xí)問(wèn)題是的主觀偏見。雖然很多貝葉斯網(wǎng)絡(luò)涉及的學(xué)習(xí)問(wèn)題是NP難解難解的。但是的。但是, 由于已經(jīng)有了一些成熟的近似解法由于已經(jīng)有了一些成熟的近似解法, 加上一些限制后加上一些限制后計(jì)算可大為簡(jiǎn)化計(jì)算可大為簡(jiǎn)化, 很多問(wèn)題可以利用近似解法求解。很多問(wèn)題可以利用近似解法求解。n貝葉斯網(wǎng)絡(luò)方法的不確定性表示基本上是保持了概率的表示方貝葉斯網(wǎng)絡(luò)方法的不確定性表示基本上是保持了概率的表示方式式, 可信度計(jì)算也是概率計(jì)算方法可信度計(jì)算也是概率計(jì)算方法, 只是在實(shí)

23、現(xiàn)時(shí)只是在實(shí)現(xiàn)時(shí), 各具體系統(tǒng)各具體系統(tǒng)根據(jù)應(yīng)用背景的需要采用各種各樣的近似計(jì)算方法。推理過(guò)程根據(jù)應(yīng)用背景的需要采用各種各樣的近似計(jì)算方法。推理過(guò)程稱為概率推理。因此稱為概率推理。因此, 貝葉斯網(wǎng)絡(luò)沒(méi)有其它確定性推理方法擁貝葉斯網(wǎng)絡(luò)沒(méi)有其它確定性推理方法擁有的確定性表示、計(jì)算、語(yǔ)義解釋等問(wèn)題。由于篇幅關(guān)系有的確定性表示、計(jì)算、語(yǔ)義解釋等問(wèn)題。由于篇幅關(guān)系, 本本節(jié)只介紹貝葉斯網(wǎng)絡(luò)的基本概念和簡(jiǎn)單的推理方法。節(jié)只介紹貝葉斯網(wǎng)絡(luò)的基本概念和簡(jiǎn)單的推理方法。28貝葉斯網(wǎng)絡(luò)(事件的獨(dú)立性)n獨(dú)立獨(dú)立：如果：如果X與與Y相互獨(dú)立相互獨(dú)立, 則則 P(X, Y) = P(X)P(Y) P(X|Y) = P

24、(X)n條件獨(dú)立條件獨(dú)立：如果在給定：如果在給定Z的條件下的條件下, X與與Y相互相互獨(dú)立獨(dú)立, 則則 P(X|Y, Z) = P(X|Z)實(shí)際中實(shí)際中, 條件獨(dú)立比完全獨(dú)立更重要條件獨(dú)立比完全獨(dú)立更重要29貝葉斯網(wǎng)絡(luò)(聯(lián)合概率)n如果相互獨(dú)立：如果相互獨(dú)立：qP(X1, X2, , XN) = P(X1) P(X2) P(XN)n條件概率：條件概率：qP(X1, X2, , XN) = P(X1|X2, , XN) P(X2, , XN)n迭代表示：迭代表示：qP(X1, X2, , XN) = P(X1) P(X2| X1) P(X3| X2X1)P(XN|XN-1, , X1)= P(X

25、N) P(XN-1| XN) P(XN-2| XN-1XN)P(X1|X2, , XN)實(shí)際應(yīng)用中就是利用條件獨(dú)立性的性質(zhì)簡(jiǎn)化網(wǎng)實(shí)際應(yīng)用中就是利用條件獨(dú)立性的性質(zhì)簡(jiǎn)化網(wǎng)絡(luò)復(fù)雜性的。絡(luò)復(fù)雜性的。30貝葉斯網(wǎng)絡(luò)(基本概念)貝葉斯網(wǎng)絡(luò)：貝葉斯網(wǎng)絡(luò)：n一系列變量的聯(lián)合概率分布的圖形表示。一系列變量的聯(lián)合概率分布的圖形表示。n一個(gè)表示變量之間的相互依賴關(guān)系的數(shù)一個(gè)表示變量之間的相互依賴關(guān)系的數(shù)據(jù)結(jié)構(gòu)；圖論與概率論的結(jié)合。據(jù)結(jié)構(gòu)；圖論與概率論的結(jié)合。31貝葉斯網(wǎng)絡(luò)(因果關(guān)系網(wǎng)絡(luò))假設(shè)：假設(shè)：n命題命題S(smoker)：該患者是一個(gè)吸煙者：該患者是一個(gè)吸煙者n命題命題C(coal Miner)：該患者是一

26、個(gè)煤礦礦井工人：該患者是一個(gè)煤礦礦井工人n命題命題L(lung Cancer)：他患了肺癌：他患了肺癌n命題命題E(emphysema)：他患了肺氣腫：他患了肺氣腫n由專家給定的假設(shè)可知由專家給定的假設(shè)可知, 命題命題S對(duì)命題對(duì)命題L和命題和命題E有因果影有因果影響響, 而而C對(duì)對(duì)E也有因果影響。命題之間的關(guān)系可以描繪成因也有因果影響。命題之間的關(guān)系可以描繪成因果關(guān)系網(wǎng)。每一個(gè)節(jié)點(diǎn)代表一個(gè)證據(jù)果關(guān)系網(wǎng)。每一個(gè)節(jié)點(diǎn)代表一個(gè)證據(jù), 每一條弧代表一條每一條弧代表一條規(guī)則規(guī)則(假設(shè)假設(shè)), 連接結(jié)點(diǎn)的弧表達(dá)了有規(guī)則給出的連接結(jié)點(diǎn)的弧表達(dá)了有規(guī)則給出的, 節(jié)點(diǎn)間的節(jié)點(diǎn)間的直接因果關(guān)系。其中直接因果關(guān)系。

27、其中, 節(jié)點(diǎn)節(jié)點(diǎn)S, C是節(jié)點(diǎn)是節(jié)點(diǎn)L和和E的父節(jié)點(diǎn)或稱的父節(jié)點(diǎn)或稱雙親節(jié)點(diǎn)雙親節(jié)點(diǎn), 同時(shí)同時(shí), L, E也稱為是也稱為是S和和C的子節(jié)點(diǎn)或稱后代節(jié)的子節(jié)點(diǎn)或稱后代節(jié)點(diǎn)。點(diǎn)。 32貝葉斯網(wǎng)絡(luò)(因果關(guān)系圖例)其中其中, 節(jié)點(diǎn)節(jié)點(diǎn)S, C是節(jié)點(diǎn)是節(jié)點(diǎn)L和和E的的父節(jié)點(diǎn)父節(jié)點(diǎn)或或稱雙親節(jié)點(diǎn)稱雙親節(jié)點(diǎn), 同同時(shí)時(shí), L, E也稱為也稱為是是S和和C的的子節(jié)子節(jié)點(diǎn)點(diǎn)或稱后代節(jié)點(diǎn)?；蚍Q后代節(jié)點(diǎn)。 33SCEL因果關(guān)系圖例 貝葉斯網(wǎng)絡(luò)(貝葉斯網(wǎng)絡(luò))n貝葉斯網(wǎng)就是一個(gè)在弧的連接關(guān)貝葉斯網(wǎng)就是一個(gè)在弧的連接關(guān)系上加入連接強(qiáng)度的因果關(guān)系網(wǎng)系上加入連接強(qiáng)度的因果關(guān)系網(wǎng)絡(luò)絡(luò) 。 34貝葉斯網(wǎng)絡(luò)(圖例) 35BADE

28、FCG貝葉斯網(wǎng)絡(luò)圖例貝葉斯網(wǎng)絡(luò)圖例無(wú)環(huán)圖和指定概率值無(wú)環(huán)圖和指定概率值P(A), P(C), P(B|AC), P(E|B), P(D|B), P(F|E), P(G|DEF) 貝葉斯網(wǎng)絡(luò)(圖例) 非貝葉斯網(wǎng)絡(luò)圖例非貝葉斯網(wǎng)絡(luò)圖例 36BADCEGF貝葉斯網(wǎng)絡(luò)(定義)n兩個(gè)部分兩個(gè)部分q貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖, 這是一個(gè)有向無(wú)環(huán)圖這是一個(gè)有向無(wú)環(huán)圖(DAG: Directed Acyclic Graph), 其中圖中的每個(gè)節(jié)點(diǎn)代其中圖中的每個(gè)節(jié)點(diǎn)代表相應(yīng)的變量。當(dāng)有向弧由節(jié)點(diǎn)表相應(yīng)的變量。當(dāng)有向弧由節(jié)點(diǎn)A指向節(jié)點(diǎn)指向節(jié)點(diǎn)B時(shí)時(shí), 則稱：則稱：A是是B的父節(jié)點(diǎn)；的父節(jié)點(diǎn)；B是是A的子節(jié)

29、點(diǎn)。的子節(jié)點(diǎn)。q節(jié)點(diǎn)和節(jié)點(diǎn)之間的條件概率表節(jié)點(diǎn)和節(jié)點(diǎn)之間的條件概率表(Conditional Probability Table, CPT), 也就是一系列的概率值也就是一系列的概率值, 表示了局部條件概率分布。表示了局部條件概率分布。P(node|parents) 。n目的：由證據(jù)得出原因發(fā)生的概率。目的：由證據(jù)得出原因發(fā)生的概率。 即觀察到即觀察到P(Y), 求求P(X|Y)37貝葉斯網(wǎng)絡(luò)(如何構(gòu)造)n選擇變量選擇變量, 生成節(jié)點(diǎn)生成節(jié)點(diǎn)n 從左至右從左至右(從上到下從上到下), 排列節(jié)點(diǎn)排列節(jié)點(diǎn)n填充網(wǎng)絡(luò)連接弧填充網(wǎng)絡(luò)連接弧, 表示節(jié)點(diǎn)之間的關(guān)系表示節(jié)點(diǎn)之間的關(guān)系n得到條件概率關(guān)系表得到

30、條件概率關(guān)系表?xiàng)l件概率表示的概率網(wǎng)絡(luò)有時(shí)叫條件概率表示的概率網(wǎng)絡(luò)有時(shí)叫“Belief Nets”38貝葉斯網(wǎng)絡(luò)(計(jì)算)n有向非循環(huán)圖是各個(gè)節(jié)點(diǎn)變量關(guān)系傳遞的合理有向非循環(huán)圖是各個(gè)節(jié)點(diǎn)變量關(guān)系傳遞的合理表達(dá)形式。表達(dá)形式。n條件概率的引入使得計(jì)算較之全連接網(wǎng)絡(luò)有了條件概率的引入使得計(jì)算較之全連接網(wǎng)絡(luò)有了大大的簡(jiǎn)化。大大的簡(jiǎn)化。nCPT表相對(duì)比較容易得到。表相對(duì)比較容易得到。 有時(shí)可以用某種概率分布表示有時(shí)可以用某種概率分布表示, 需要做的指示計(jì)算需要做的指示計(jì)算表示的參數(shù)。表示的參數(shù)。39貝葉斯網(wǎng)絡(luò)(計(jì)算續(xù))n簡(jiǎn)單的聯(lián)合概率可以直接從網(wǎng)絡(luò)關(guān)系上得到簡(jiǎn)單的聯(lián)合概率可以直接從網(wǎng)絡(luò)關(guān)系上得到如：如：P

31、(X, Y) = P(X)P(Y|X)又如：又如：P(X, Y, Z) = P(X)P(Y)P(Z|X, Y)40XYP(X)P(Y|X)XZYP(X)P(Z|Y, X)P(Y)貝葉斯網(wǎng)絡(luò)(例)CPT表為：表為：nP(S) = 0.4nP(C) = 0.3nP(E|S, C) = 0.9nP(E|S, C) = 0.3nP(E|S, C) = 0.5 貝葉斯網(wǎng)絡(luò)實(shí)例圖貝葉斯網(wǎng)絡(luò)實(shí)例圖nP(E|S, C) = 0.1 。 41SCELP(S)=0.4P(C)=0.3P(E|S, C)=0.9貝葉斯網(wǎng)絡(luò)(例續(xù))n上圖例中的聯(lián)合概率密度為上圖例中的聯(lián)合概率密度為n由圖可知：由圖可知：E與與L在在S條

32、件下獨(dú)立條件下獨(dú)立, 所以所以P(E|S, C, L) P(E|S, C), L與與C在在S, E條件下獨(dú)立條件下獨(dú)立, 所以所以P(L|S, C)= P(L|S), C與與S在在E條件下獨(dú)立條件下獨(dú)立, 所以所以P(C|S)=P(C) n以上三條等式的正確性以上三條等式的正確性, 可以從貝葉斯網(wǎng)的條件獨(dú)立屬性：每個(gè)變量可以從貝葉斯網(wǎng)的條件獨(dú)立屬性：每個(gè)變量與它在圖中的非繼承節(jié)點(diǎn)在概率上是獨(dú)立的推出。同樣與它在圖中的非繼承節(jié)點(diǎn)在概率上是獨(dú)立的推出。同樣, 從后面給出從后面給出的的D分離的定義的特性中也可以得到相同的結(jié)論。分離的定義的特性中也可以得到相同的結(jié)論。n簡(jiǎn)化后的聯(lián)合概率密度為簡(jiǎn)化后的聯(lián)

33、合概率密度為, 顯然顯然, 簡(jiǎn)化后的公式比原始的數(shù)學(xué)公式更加簡(jiǎn)單明了簡(jiǎn)化后的公式比原始的數(shù)學(xué)公式更加簡(jiǎn)單明了, 計(jì)算復(fù)雜度低很計(jì)算復(fù)雜度低很多。如果原貝葉斯網(wǎng)中的條件獨(dú)立語(yǔ)義數(shù)量較多多。如果原貝葉斯網(wǎng)中的條件獨(dú)立語(yǔ)義數(shù)量較多, 這種減少更加明顯。這種減少更加明顯。42)(*)|(*),|(*),|(),(SPSCPCSLPLCSEPELCSP)(*)(*)|(*),|(),(SPCPSLPCSEPELCSP貝葉斯網(wǎng)絡(luò)(獨(dú)立)n獨(dú)立獨(dú)立qP(X, Y) = P(X)P(Y)qP(X|Y) = P(X)qP(Y|X) = P(Y)n獨(dú)立時(shí)求解獨(dú)立時(shí)求解 q可以直接在網(wǎng)絡(luò)圖上求可以直接在網(wǎng)絡(luò)圖上求4

34、3貝葉斯網(wǎng)絡(luò)(條件獨(dú)立)n對(duì)于對(duì)于X, Y, E: X與與Y在給定在給定E的條件下獨(dú)立的條件下獨(dú)立qP(X|Y, E) = P(X|E)qP(Y|X, E) = P(Y|E)n多個(gè)變量組：多個(gè)變量組：d分離分離(d-separate) qP(X1, X2, , Xn|Y1, Y2, , Ym, E1, E2, , Ep) =P(X1, X2, , Xn|E1, E2, , Ep) q如果一組節(jié)點(diǎn)如果一組節(jié)點(diǎn)X在給定在給定E的條件下的條件下, 從從Xi到到Y(jié)j的每一條通的每一條通路都被即路都被即Ekd分離分離, 則稱則稱X獨(dú)立于另一組節(jié)點(diǎn)獨(dú)立于另一組節(jié)點(diǎn)Y (節(jié)點(diǎn)組節(jié)點(diǎn)組E d分離分離X與與Y)

35、44貝葉斯網(wǎng)絡(luò)(D分離)n圖中有三個(gè)節(jié)點(diǎn)圖中有三個(gè)節(jié)點(diǎn)S, L, EnL(結(jié)果結(jié)果)影響影響S(起因起因), S影響影響E(另一個(gè)結(jié)果另一個(gè)結(jié)果)。n如果給定原因如果給定原因S后后, L并不能告并不能告訴我們有關(guān)訴我們有關(guān)E的更多事情。即的更多事情。即對(duì)于對(duì)于S, L和和E是相對(duì)獨(dú)立的是相對(duì)獨(dú)立的, 那么在計(jì)算那么在計(jì)算S和和L的關(guān)系時(shí)就的關(guān)系時(shí)就不用過(guò)多地考慮不用過(guò)多地考慮E, 將會(huì)大大將會(huì)大大減少計(jì)算復(fù)雜度。減少計(jì)算復(fù)雜度。n稱稱S能能D分離分離L和和E。nD分離是一種尋找條件獨(dú)立的分離是一種尋找條件獨(dú)立的有效方法。有效方法。 45SCELP(S)=0.4P(C)=0.3P(E|S, C)

36、=0.9貝葉斯網(wǎng)絡(luò)( D分離-串行)nLinear 串行連接中串行連接中, 事件事件X通過(guò)事件通過(guò)事件Z影響事件影響事件Y, 反之反之事件事件Y也是通過(guò)事件也是通過(guò)事件Z影響事件影響事件X。但是。但是, 如果如果原因證據(jù)原因證據(jù)Z是給定的是給定的, X并不能給并不能給Y更多的東西更多的東西, 或者說(shuō)或者說(shuō), 從從X那里得到更多的信息。此時(shí)稱那里得到更多的信息。此時(shí)稱, 如如果果Z是已知的是已知的, 那么通道就被阻塞那么通道就被阻塞, X和和Y就是獨(dú)就是獨(dú)立的了。則稱立的了。則稱X和和Y是被是被Z節(jié)點(diǎn)節(jié)點(diǎn)D分離的。分離的。 46XZY貝葉斯網(wǎng)絡(luò)( D分離(分叉連接)Divergingn如果如果,

37、 父節(jié)點(diǎn)父節(jié)點(diǎn)Z是已知是已知的的, 沒(méi)有更多的信息能沒(méi)有更多的信息能夠通過(guò)夠通過(guò)Z影響到所有子影響到所有子節(jié)點(diǎn)。同理節(jié)點(diǎn)。同理, 父節(jié)點(diǎn)父節(jié)點(diǎn)Z是已知時(shí)是已知時(shí), 子節(jié)點(diǎn)子節(jié)點(diǎn)X, , N是相互獨(dú)立的。稱子是相互獨(dú)立的。稱子節(jié)點(diǎn)節(jié)點(diǎn)X, , N是被是被Z節(jié)節(jié)點(diǎn)點(diǎn)D分離的。分離的。 47NYXZ。貝葉斯網(wǎng)絡(luò)( D分離(匯集連接)匯集匯集(Converging)略有不同略有不同n如果不從父節(jié)點(diǎn)得到推斷如果不從父節(jié)點(diǎn)得到推斷, 子節(jié)子節(jié)點(diǎn)點(diǎn)Z就一無(wú)所知就一無(wú)所知, 那么那么, 父節(jié)點(diǎn)是父節(jié)點(diǎn)是相互獨(dú)立的相互獨(dú)立的, 它們之間沒(méi)有相互它們之間沒(méi)有相互影響。影響。n如果如果, 某事件影響了某事件影響了Z

38、, 那么那么, 各各個(gè)父節(jié)點(diǎn)就不是相互獨(dú)立的了。個(gè)父節(jié)點(diǎn)就不是相互獨(dú)立的了。該事件可以直接影響該事件可以直接影響Z, 也可以也可以通過(guò)它的后代節(jié)點(diǎn)影響通過(guò)它的后代節(jié)點(diǎn)影響Z。這種。這種現(xiàn)象稱作條件依存。總之現(xiàn)象稱作條件依存。總之, 如果如果子節(jié)點(diǎn)有了變化子節(jié)點(diǎn)有了變化, 或子節(jié)點(diǎn)的后或子節(jié)點(diǎn)的后代節(jié)點(diǎn)發(fā)生變化代節(jié)點(diǎn)發(fā)生變化, 信息是可以通信息是可以通過(guò)匯集連接傳播的。過(guò)匯集連接傳播的。 48ZNYX。貝葉斯網(wǎng)絡(luò)( D分離(條件依存) 事件事件e直接影響節(jié)點(diǎn)直接影響節(jié)點(diǎn)Z 事件事件e影響節(jié)點(diǎn)影響節(jié)點(diǎn)Z的后代節(jié)點(diǎn)的后代節(jié)點(diǎn) 49ZNYX。eZNYX。LMe貝葉斯網(wǎng)絡(luò)( D分離(定義)n對(duì)于給定的結(jié)

39、點(diǎn)集對(duì)于給定的結(jié)點(diǎn)集 , 如果對(duì)貝葉斯網(wǎng)中的結(jié)點(diǎn)如果對(duì)貝葉斯網(wǎng)中的結(jié)點(diǎn)Vi和和Vj之之間的每個(gè)無(wú)向路徑間的每個(gè)無(wú)向路徑(即不考慮即不考慮DAG圖中弧的方向性的路圖中弧的方向性的路徑徑), 在路徑上都有某個(gè)結(jié)點(diǎn)在路徑上都有某個(gè)結(jié)點(diǎn)Vb, 如果有屬性：如果有屬性：qVb在在 中中, 且路徑上的兩條弧都以且路徑上的兩條弧都以Vb為尾為尾(即弧在即弧在Vb處開始處開始(出發(fā)出發(fā)), 分叉分叉連接連接)qVb在在 中中, 路徑上的一條弧以路徑上的一條弧以Vb為頭為頭, 一條以一條以Vb為尾為尾(串行連接串行連接)qVb和它的任何后繼都不在和它的任何后繼都不在 中中, 路徑上的兩條弧都以路徑上的兩條弧都以

40、Vb為頭為頭(即弧在即弧在Vb處結(jié)束處結(jié)束, 匯集連接匯集連接, 但沒(méi)有后代節(jié)點(diǎn)但沒(méi)有后代節(jié)點(diǎn)) 則稱則稱Vi和和Vj 被被Vb結(jié)點(diǎn)阻塞。結(jié)點(diǎn)阻塞。n如果如果Vi和和Vj被證據(jù)集合被證據(jù)集合 中的任意結(jié)點(diǎn)阻塞中的任意結(jié)點(diǎn)阻塞, 則稱則稱Vi和和Vj是被是被 集合集合D分離分離, 結(jié)點(diǎn)結(jié)點(diǎn)Vi和和Vj條件獨(dú)立于給定的證據(jù)集條件獨(dú)立于給定的證據(jù)集合合 , 可形式化表示為：可形式化表示為：qP(Vi|Vj, )=P(Vi| )qP(Vj|Vi, )=P(Vj| )qI(Vj, Vi| )或或I(Vj, Vi| )50貝葉斯網(wǎng)絡(luò)( D分離(圖示) 51V Vi iVb3VjVb1 V Vb2證據(jù)集給定

41、證據(jù)結(jié)點(diǎn)集，Vi獨(dú)立Vj：Vi到Vj的所有三條路徑都被阻塞a)Vb1是證據(jù)結(jié)點(diǎn)，兩條弧都以Vb1為尾b)Vb2是證據(jù)結(jié)點(diǎn)，一條以Vb2為頭，一條以Vb2為尾c)Vb3及其任何后繼都不在證據(jù)結(jié)點(diǎn)集中，兩條弧都以Vb3為頭貝葉斯網(wǎng)絡(luò)( 定義)n條件獨(dú)立條件獨(dú)立：q如具有以上三個(gè)屬性之一如具有以上三個(gè)屬性之一, 就說(shuō)結(jié)點(diǎn)就說(shuō)結(jié)點(diǎn)Vi和和Vj條件獨(dú)立于條件獨(dú)立于給定的結(jié)點(diǎn)集給定的結(jié)點(diǎn)集 。n阻塞阻塞：q給定證據(jù)集合給定證據(jù)集合 , 當(dāng)上述條件中的任何一個(gè)滿足時(shí)當(dāng)上述條件中的任何一個(gè)滿足時(shí), 就說(shuō)就說(shuō)Vb阻塞相應(yīng)的那條路徑。阻塞相應(yīng)的那條路徑。nD分離分離：q如果如果Vi和和Vj之間所有的路徑被阻塞之間

42、所有的路徑被阻塞, 就叫證據(jù)集合就叫證據(jù)集合 可以可以D分離分離Vi和和Vj52貝葉斯網(wǎng)絡(luò)( D分離(例1) 53ZXYZX、Y獨(dú)立獨(dú)立X、Y條件獨(dú)立條件獨(dú)立YesYesXYZX、Y獨(dú)立獨(dú)立X、Y條件獨(dú)立條件獨(dú)立YesNoXYZX、Y獨(dú)立獨(dú)立X、Y條件獨(dú)立條件獨(dú)立YesNoXYZX、Y獨(dú)立獨(dú)立X、Y條件獨(dú)立條件獨(dú)立NoYesXYX、Y獨(dú)立獨(dú)立X、Y條件獨(dú)立條件獨(dú)立NoNo貝葉斯網(wǎng)絡(luò)( D分離(例2) 54ZXYX草濕草濕Y彩虹彩虹Z下雨下雨P(guān)(X, Y)P(X)P(Y)P(X|Y, Z) = P(X|Z)ZXYX下雨下雨Y灑水灑水Z草濕草濕P(X, Y)= P(X)P(Y)P(X|Y, Z)

43、) P(X|Z)貝葉斯網(wǎng)絡(luò)( D分離(例4)Radio and Ignition, given Battery? YesRadio and Start, given Ignition? YesGas and Radio, given Battery? YesGas and Radio, given Start? NoGas and Battery, given Moves? No 55BatteryRadioIgnitionGasMovesStart貝葉斯網(wǎng)絡(luò)(推理)n建立貝葉斯網(wǎng)絡(luò)的目的建立貝葉斯網(wǎng)絡(luò)的目的q有了網(wǎng)絡(luò)。可以提出問(wèn)題：有了網(wǎng)絡(luò)。可以提出問(wèn)題：nP(問(wèn)題問(wèn)題|證據(jù)證據(jù)), 如：如

44、：P(吸煙吸煙|肺癌肺癌)q進(jìn)行概率推理進(jìn)行概率推理q與謂詞邏輯有相似之處與謂詞邏輯有相似之處 。如：患病。如：患病(吸煙吸煙, 肺癌肺癌)n在某些場(chǎng)合下有有效的推理方法。有一些工具包。在某些場(chǎng)合下有有效的推理方法。有一些工具包。n一般情況下是很困難的一般情況下是很困難的, 原因原因q不是所有的不是所有的CPT表都能夠得到表都能夠得到q網(wǎng)絡(luò)結(jié)構(gòu)大且復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)大且復(fù)雜qNP-hard推理推理n我們要做的是我們要做的是, 將問(wèn)題正確的表示為合理的網(wǎng)絡(luò)形式將問(wèn)題正確的表示為合理的網(wǎng)絡(luò)形式, 選用選用適合的算法。適合的算法。56貝葉斯網(wǎng)絡(luò)(推理續(xù))n貝葉斯網(wǎng)絡(luò)通常使用因果或診斷規(guī)則與推理貝葉斯網(wǎng)絡(luò)通

45、常使用因果或診斷規(guī)則與推理q因果規(guī)則：因果規(guī)則：X Cause Y with some probabilityq診斷診斷規(guī)則：規(guī)則：Y is evidence of X with some probabilityq因果推理：因果推理：Given cause C, determine P(Query|C)q診斷推理：診斷推理：Given evidence E, determine P(Query|E)57貝葉斯網(wǎng)絡(luò)(推理續(xù))n推理需求：推理需求：P(X|Y)q診斷診斷推理是從效果到起因推理是從效果到起因 證據(jù)是一些征兆：證據(jù)是一些征兆：X是起因是起因, Y是征兆是征兆q因果因果推理是從起因到效果

46、推理是從起因到效果 證據(jù)是一些起因：證據(jù)是一些起因： X是征兆是征兆, Y是起因是起因q解釋解釋歷史歷史 X和和Y是起因是起因, Z是兩個(gè)起因的征兆。這時(shí)可以用一是兩個(gè)起因的征兆。這時(shí)可以用一個(gè)起因個(gè)起因Y解釋另一個(gè)起因解釋另一個(gè)起因X。58貝葉斯網(wǎng)絡(luò)(推理例)n下雨、草濕、灑水下雨、草濕、灑水59P(X)P(Y)下雨下雨草濕草濕Query:P(X|Y)P(X)P(Y)草濕草濕下雨下雨Query:P(X|Y)P(X)P(Z|X, Y)下雨下雨草濕草濕Query:P(X|Y, Z) and P(X|Z)P(Y)灑水灑水貝葉斯網(wǎng)絡(luò)(推理例續(xù))n條件：條件：q下雨下雨q草濕草濕q出現(xiàn)蟲子出現(xiàn)蟲子 n

47、 求：求：qP(Raining|Worm Sighting)60P(Y|X)下雨下雨草濕草濕Query:P(X|Z)P(X)出現(xiàn)出現(xiàn)蟲子蟲子P(Z|Y)貝葉斯網(wǎng)絡(luò)(因果推理例)給定患者是一個(gè)吸煙者給定患者是一個(gè)吸煙者(S), 計(jì)算他患肺氣腫計(jì)算他患肺氣腫(E)的概率的概率P(E|S)。S稱作推稱作推理的證據(jù)理的證據(jù), E叫詢問(wèn)結(jié)點(diǎn)。叫詢問(wèn)結(jié)點(diǎn)。 n首先首先, E的另一個(gè)父結(jié)點(diǎn)的另一個(gè)父結(jié)點(diǎn)(C), P(E|S)=P(E, C|S)+P(E, C|S);n右邊的第一項(xiàng)右邊的第一項(xiàng) , P(E, C|S)P(E, C, S)/P(S)P(E|C, S)*P(C, S)/P(S)P(E|C, S)*

48、P(C|S)n同理可得公式的右邊的第二項(xiàng)為：同理可得公式的右邊的第二項(xiàng)為：P(E, C|S) = P(E|C, S)*P(C)。n由此可得：由此可得：nP(E|S) = P(E| C, S)*P(C)+P(E|C, S)*P(C)n如果采用概述中的例題數(shù)據(jù)如果采用概述中的例題數(shù)據(jù), 有有P(C) = 1 - P(C), 則有則有, nP(E|S)0.9*0.3+0.3*(1-0.3)=0.48主要操作：主要操作：n按照給定證據(jù)的按照給定證據(jù)的V和它的所有雙親的聯(lián)合概率和它的所有雙親的聯(lián)合概率, 重新表達(dá)給定證據(jù)的重新表達(dá)給定證據(jù)的詢問(wèn)結(jié)點(diǎn)的所求條件概率。詢問(wèn)結(jié)點(diǎn)的所求條件概率。n直到所有的概率

49、值可從直到所有的概率值可從CPT表中得到表中得到, 推理完成。推理完成。61貝葉斯網(wǎng)絡(luò)(推理自學(xué))Artificial Intelligence: A New Synthesis Nils. J. Nilsson, 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社, 1999Probabilistic Inference in Polytrees (p.332)62第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性方法確定性方法n證據(jù)理論證據(jù)理論63第五章 不確定性推理n概述概述n概率論基礎(chǔ)概率論基礎(chǔ)nBayes網(wǎng)絡(luò)網(wǎng)絡(luò)n主觀主觀Bayes方法方法n確定性

50、方法確定性方法n證據(jù)理論證據(jù)理論64主觀貝葉斯方法(概述)n在在Prospector的探礦系統(tǒng)的研究過(guò)程中提出的探礦系統(tǒng)的研究過(guò)程中提出的。的。 原有貝葉斯公式只考慮原有貝葉斯公式只考慮A出現(xiàn)對(duì)出現(xiàn)對(duì)B的影響的影響, 沒(méi)有考慮沒(méi)有考慮A不出現(xiàn)的影響。不出現(xiàn)的影響。 n貝葉斯規(guī)則：貝葉斯規(guī)則：當(dāng)當(dāng)B為為n個(gè)互不相容事件的集合時(shí)個(gè)互不相容事件的集合時(shí), 貝葉斯公式可寫為：貝葉斯公式可寫為： 65P(A|B)P(B)P(B|A)P(A)n1jjjiii)P(BB|P(A)P(BB|P(AA)|P(Bn 1i跳過(guò)跳過(guò)主觀貝葉斯方法(概述)n思路思路q先定好應(yīng)該怎么辦先定好應(yīng)該怎么辦, 再湊公式。主要是

51、避開再湊公式。主要是避開P(A| B)的計(jì)算。的計(jì)算。 66主觀貝葉斯方法(概述)n規(guī)則的不確定性規(guī)則的不確定性q定義：定義：67(|)(|)(|)( )(|)()P B AP A BPB ALSP BP ABPB表示表示A A為真時(shí)為真時(shí), , 對(duì)對(duì)B B的影響。的影響。( (規(guī)則成立的規(guī)則成立的充分性充分性) )(|)(|)(|)( )(|)()P BAPA BPBALNP BPABPB表示表示A為假時(shí)為假時(shí), , 對(duì)對(duì)B的影響。的影響。( (規(guī)則成立的規(guī)則成立的必要性必要性) ) ( (確定性理論中沒(méi)有考慮這點(diǎn)確定性理論中沒(méi)有考慮這點(diǎn)) )主觀貝葉斯方法(規(guī)則的不確定性)68P(X)-1

52、P(X)O(X) 幾率函數(shù)幾率函數(shù)O(X)|(1)|()|()|()|(ABPABPABPABPABO)(1)()(XOXOXPO(X)O(X)稱為稱為先驗(yàn)幾率先驗(yàn)幾率。表示證據(jù)。表示證據(jù)X X的出現(xiàn)概率和不出現(xiàn)的概率的出現(xiàn)概率和不出現(xiàn)的概率之比之比, , 顯然顯然O(X)O(X)是是P(X)P(X)的增函數(shù)的增函數(shù), , 且有：且有：當(dāng)當(dāng)P(X)P(X)0, 0, 有有O(X)O(X)0 0當(dāng)當(dāng)P(X)P(X)0.5, 0.5, 有有 O(X)O(X)1 1當(dāng)當(dāng)P(X)P(X)1, 1, 有有O(X)O(X)由此可見由此可見, , 幾率函數(shù)實(shí)際上表示了證據(jù)幾率函數(shù)實(shí)際上表示了證據(jù)X X的不確

53、定性。的不確定性。相應(yīng)有相應(yīng)有, , 稱為后驗(yàn)幾率稱為后驗(yàn)幾率 )|(ABO主觀貝葉斯方法(規(guī)則的不確定性)qO(X)的性質(zhì)的性質(zhì)nP(X) = 0時(shí)時(shí), O(X) = 0假假nP(X) = 0.5時(shí)時(shí), O(X) = 1nP(X) = 1時(shí)時(shí), O(X) = 真真qO(X)與與LN, LS的關(guān)系的關(guān)系nO(B|A) = LS O(B)nO(B|A) = LN O(B)69主觀貝葉斯方法(規(guī)則的不確定性)70BA O(B)A)|B O( 1BA O(B)A)|O(B 1BA O(B)A)|O(B 1LS不支持支持沒(méi)影響對(duì)BA O(B)A)|B O( 1BA O(B)A)|O(B 1BA O(B

54、)A)|O(B 1LN不支持支持沒(méi)影響對(duì), , 且必須滿足且必須滿足：主觀貝葉斯方法(規(guī)則的不確定性)qLS, LN0, 不獨(dú)立。不獨(dú)立。qLS, LN不能同時(shí)不能同時(shí) 1或或 1qLS, LN可同時(shí)可同時(shí)171主觀貝葉斯方法(證據(jù)A的不確定性)nP(A)或或O(A)表示證據(jù)表示證據(jù)A的不確定性的不確定性72一般情況），（真當(dāng)，假當(dāng)0, 0)(1)()(AAAPAPAO主觀貝葉斯方法(推理計(jì)算1)nA必出現(xiàn)時(shí)：必出現(xiàn)時(shí)：qO(B|A) = LSO(B)qO(B|A) = LNO(B) 若需要概率時(shí)：若需要概率時(shí)：73)(1)()(AOAOAP主觀貝葉斯方法(推理計(jì)算2)A不確定時(shí)：即不確定時(shí)：

55、即P(A) 1 (1976年的算法年的算法)q向前看一步向前看一步A, A 為與為與A有關(guān)的所有觀察有關(guān)的所有觀察 P(B|A) = P(B|A)P(A| A)+P(B|A)P(A| A) nP(A| A) = 1時(shí)時(shí), 證據(jù)證據(jù)A必然出現(xiàn)必然出現(xiàn)(P95)nP(A| A) = 0時(shí)時(shí), LN代替上式代替上式 的的LS, 公式公式(2)nP(A| A) = P(A) 時(shí)時(shí), (A對(duì)對(duì)A無(wú)影響無(wú)影響), 由上式由上式 P(B| A) = P(B)74) 1 (1)() 1()()|() |(BPLSBPLSABPABP主觀貝葉斯方法(推理計(jì)算2)P(A| A)與與P(B| A)坐標(biāo)系上的三點(diǎn)：坐

56、標(biāo)系上的三點(diǎn)：(P96) 總之是找一些總之是找一些P(A| A)與與P(B| A)的相關(guān)值的相關(guān)值, 兩點(diǎn)也可以做曲線兩點(diǎn)也可以做曲線(或折線、直線或折線、直線)。由差值法從。由差值法從線上得到其它點(diǎn)的結(jié)果線上得到其它點(diǎn)的結(jié)果, 具體過(guò)程可參考教科書具體過(guò)程可參考教科書上例題。上例題。75)()()2(0) 1 (1) |(BPAPAAP公式公式主觀貝葉斯方法(推理計(jì)算2)插值計(jì)算公式插值計(jì)算公式76)/()()()/()(1)()/()()()/(0)/()()/()()/( )/(AAPAPAPAAPAPBPABPBPAPAAPAAPAPABPBPABPABP線性插值圖 770P(A)1P

57、(A|A)P(B|A)P(B|A)P(B)P(B|A)插值點(diǎn)主觀貝葉斯方法(推理計(jì)算3)兩個(gè)證據(jù)時(shí)：兩個(gè)證據(jù)時(shí)：78) |(),|(min) |(2121AAPAAPAAAP) |(),|(max) |(2121AAPAAPAAAP主觀貝葉斯方法(推理計(jì)算2)互相獨(dú)立證據(jù)導(dǎo)出同一假設(shè)互相獨(dú)立證據(jù)導(dǎo)出同一假設(shè)791212( /.)( /)( /)( /) .( )( )( )( )nnO B AAAO B AO B AO B AO BO BO BO B 例題(1)n已知：已知：P(A)=1, P(B1)=0.04, P(B2)=0.02R1:AB1 LS=20 LN=1R2:B1B2 LS=30

58、0 LN=0.001n計(jì)算：計(jì)算：P(B2|A)。分析：當(dāng)使用規(guī)則。分析：當(dāng)使用規(guī)則R2時(shí)時(shí), 證據(jù)證據(jù)B1并不是確定的發(fā)生并不是確定的發(fā)生了了, 即即P(B1)1, 因此要采用插值方法。因此要采用插值方法。n解：先依照解：先依照A必然發(fā)生必然發(fā)生, 由定義和由定義和R1得：得：O(B1) = P(B1)/(1-P(B1) = 0.04/(1-0.04) = 0.0417O(B1|A) = LS*O(B1)=0.83P(B1|A) = O(B1|A )/(1+O(B1|A ) = 0.83/(1+0.83) = 0.454n然后假設(shè)然后假設(shè)P(B1|A)=1, 計(jì)算：計(jì)算： O(B2) = P

59、(B2)/(1-P(B2) = 0.02P(B2|B1) = LS*O(B2)/(1+ LS*O(B2) = 300*0.02/(300*0.02+1)=0.857n最后進(jìn)行插值：最后進(jìn)行插值：P(B1|A) P(B1), P(B2)=0.02, P(B1)=0.04 (已知已知), P(B2|A) = 0.02 + (0.857-0.02)(0.454-0.04)/(1-0.04) = 0.3880例題(2)n已知：證據(jù)已知：證據(jù)A1, A2必然發(fā)生必然發(fā)生, 且且P(B1)0.03 規(guī)則如下：規(guī)則如下：R1：A1B1 LS=20 LN=1; R2：A2B1 LS=300LN=1n求求B1的

60、更新值。的更新值。n解：解：依依R1, P1(B)0.03O(B1)0.03/(1-0.03)=0.030927O(B1|A1)=LSO(B1)=200.030927=0.61855P(B1|A1)= 0.61855/(1+0.61855)=0.382使用規(guī)則使用規(guī)則R1后后, B1的概率從的概率從0.03上升到上升到0.382依依R2：O(B1|A1A2)=300O(B1|A1)=185.565P(B1|A1A2)= 185.565/(1+185.565)=0.99464使用規(guī)則使用規(guī)則R2后后, B1的概率從的概率從0.382上升到上升到0.9946481主觀貝葉斯方法n主觀主觀Bayes