邏輯推理 _人工智能

1、不確定性不確定性l不確定環(huán)境下的行動(dòng)l概率公理l使用全概率分布進(jìn)行推理l獨(dú)立性l貝葉斯法則及其應(yīng)用不確定性（不確定性（Uncertainty）l定義行動(dòng) At = 航班起飛前 t 分鐘啟程前往機(jī)場(chǎng)；l問： At 能不能及時(shí)使agent趕上飛機(jī)？A180 是一個(gè)可靠的行動(dòng)，如果所選路線上沒有交通事故、沒有交通管制、汽車沒有出故障、沒有沙塵暴，等等，等等。(A1440 或許是個(gè)一定不會(huì)耽誤飛機(jī)的計(jì)劃，不過要在機(jī)場(chǎng)過夜)l邏輯方法使得Agent在得到關(guān)于環(huán)境的足夠多事實(shí)時(shí)，使得行動(dòng)計(jì)劃得到保證。l但是，沒有任何agent能夠獲得關(guān)于其環(huán)境的全部事實(shí)。FOL與不確定性與不確定性lFOL能夠處理不確定性

2、嗎？l醫(yī)學(xué)專家系統(tǒng)：p Symptom(p,Toothache) Disease(p,Cavity) ?引起牙痛的原因：牙洞？ 窮舉牙洞與牙痛有必然聯(lián)系嗎？l失敗的原因：懶惰(laziness): failure to enumerate exceptions, qualifications, etc.無(wú)知(ignorance): lack of relevant facts, initial conditions, etc.不確定環(huán)境下的決策不確定環(huán)境下的決策l基本思想：精確度和有效性的折中l(wèi)理性決策的含義既依賴于各種目標(biāo)的相對(duì)重要性，也依賴于這些目標(biāo)將被實(shí)現(xiàn)的可能性（程度）。l假設(shè)A180

3、理性決策，這意味著在給定所處的環(huán)境信息下，它是所有可執(zhí)行的規(guī)劃中智能體的性能度量期望達(dá)到最大的那個(gè)。l性能度量：及時(shí)趕上飛機(jī)、等待時(shí)間不長(zhǎng)，不確定環(huán)境下的決策不確定環(huán)境下的決策l例如：給出行動(dòng)及其成功的概率如下: P(A25 gets me there on time | ) = 0.04 P(A90 gets me there on time | ) = 0.70 P(A120 gets me there on time | ) = 0.95 P(A1440 gets me there on time | ) = 0.9999 l該選哪一個(gè)行動(dòng)?例如，取決于成功的幾率以及等待時(shí)間的折中。必須

4、考慮效用理論（Utility theory）決策論概率論效用論Decision theory = probability theory + utility theory不確定性不確定性l不確定環(huán)境下的行動(dòng)l概率公理l使用全概率分布進(jìn)行推理l獨(dú)立性l貝葉斯法則及其應(yīng)用概率理論（概率理論（ Probability theory ）lAgent的知識(shí)提供的最多是關(guān)于語(yǔ)句的信度（degree of belief）。l概率論可以處理我們的惰性和無(wú)知。l概率是宇宙的真實(shí)方面：它是物體的行為表現(xiàn)為特定方式的傾向，而不僅僅是對(duì)觀察者信心的描述。l概率與證據(jù)：在評(píng)估語(yǔ)句的概率時(shí)，必須指出有關(guān)證據(jù)。Agent獲得

5、新的信息后，其概率評(píng)估應(yīng)該更新。先驗(yàn)概率、后驗(yàn)概率先驗(yàn)概率先驗(yàn)概率l與命題a相關(guān)的無(wú)條件概率，在沒有任何其它信息存在的情況下，關(guān)于命題的信度，記為：P（a）。l例如，用P（weather）表示天氣的概率：P（weather sunny）0.7P（weather rain）0.2P（weather cloudy）0.08P（weather snow）0.02l先驗(yàn)概率分布：P（weather ）l聯(lián)合概率分布，全聯(lián)合概率分布l概率密度函數(shù)后驗(yàn)（條件）概率后驗(yàn)（條件）概率l得到與命題a相關(guān)的變量的證據(jù)，先驗(yàn)概率失效，需要以后驗(yàn)概率替代，記為：P（a|b）l例如：P（cavity | toothac

6、he）0.7l乘法規(guī)則：P（a b） P（b | a） P（a）概率公理（概率公理（Axioms of probability）l對(duì)任意命題 A, B:0 P(A) 1P(true) = 1 ， P(false) = 0P(A B) = P(A) + P(B) - P(A B)Kolmogorov公理不確定性不確定性l不確定環(huán)境下的行動(dòng)l概率公理l使用全概率分布進(jìn)行推理l獨(dú)立性l貝葉斯法則及其應(yīng)用聯(lián)合概率分布聯(lián)合概率分布l聯(lián)合概率分布（joint probability distribution）:表中catch是指由于牙醫(yī)的鋼探針不潔而導(dǎo)致的牙齦感染l對(duì)任何命題 , 其概率是所有原子證據(jù)事件

7、概率的和： lP() = : P()聯(lián)合概率分布（枚舉）聯(lián)合概率分布（枚舉）lStart with the joint probability distribution:lFor any proposition , sum the atomic events where it is true: P() = : P()P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2lStart with the joint probability distribution,lCan also compute conditional probabilities:

8、P(cavity | toothache) = P(cavity toothache)P(toothache)= 0.016+0.064 0.108 + 0.012 + 0.016 + 0.064= 0.4聯(lián)合概率分布（枚舉）聯(lián)合概率分布（枚舉）歸一化（歸一化（Normalization）l(Denominator)-1 normalization constant lP(Cavity | toothache) = P(Cavity,toothache) = P(Cavity,toothache,catch) + P(Cavity,toothache, catch)= + = = lGener

9、al idea: compute distribution on query variable by fixing evidence variables and summing over hidden variables.不確定性不確定性l不確定環(huán)境下的行動(dòng)l概率公理l使用全概率分布進(jìn)行推理l獨(dú)立性l貝葉斯法則及其應(yīng)用獨(dú)立性（獨(dú)立性（Independence）lA 與 B 獨(dú)立，當(dāng)且僅當(dāng)P(A|B) = P(A) or P(B|A) = P(B) or P(A, B) = P(A) P(B)例如：例如：P(Toothache, Catch, Cavity, Weather)= P(Tootha

10、che, Catch, Cavity) P(Weather)l32 entries reduced to 12 (weather has 4 possible values); for n independent biased coins, O(2n) O(n)l絕對(duì)獨(dú)立很好但很少見，例如牙科中可能涉及幾百相互關(guān)聯(lián)的變量，這時(shí)候如何處理？條件獨(dú)立（條件獨(dú)立（Conditional independence）l已知有一個(gè)牙洞，鉆具感染與牙疼的概率相互獨(dú)立：l鉆具感染與牙痛在給定牙洞的情況下是條件獨(dú)立的lconditionally independent P(Toothache, Catch |

11、Cavity) = P(Toothache | Cavity) P(Catch | Cavity)條件獨(dú)立條件獨(dú)立l推導(dǎo)聯(lián)合分布，將全聯(lián)合分布分解成很多更小的分布:P(Toothache, Catch, Cavity)= P(Toothache, Catch | Cavity) P(Cavity) 乘法法則= P(Toothache | Cavity) P(Catch | Cavity) P(Cavity) 條件獨(dú)立I.e., 2 + 2 + 1 = 5 independent numbersl條件分布將聯(lián)合分布的表示空間由指數(shù)級(jí)降到線性。l條件概率是處理不確定信息的基礎(chǔ)和最魯棒的形式。不確定

12、性不確定性l不確定環(huán)境下的行動(dòng)l概率公理l使用全概率分布進(jìn)行推理l獨(dú)立性l貝葉斯法則及其應(yīng)用貝葉斯法則（貝葉斯法則（Bayes Rule）l由乘法法則 P(ab) = P(a | b) P(b) = P(b | a) P(a) Bayes rule: P(a | b) = P(b | a) P(a) / P(b)l一般形式： P(Y|X) = P(X|Y) P(Y) / P(X) = P(X|Y) P(Y)l例子：用于從病因（causal）中找到診斷（diagnostic）結(jié)論 :P(Cause|Effect) = P(Effect|Cause) P(Cause) / P(Effect)E.g

13、., let M be meningitis, S be stiff neck:P(m|s) = P(s|m) P(m) / P(s) = 0.8 0.0001 / 0.1 = 0.0008貝葉斯法則與條件獨(dú)立貝葉斯法則與條件獨(dú)立P(Cavity | toothache catch) = P(toothache catch | Cavity) P(Cavity) = P(toothache | Cavity) P(catch | Cavity) P(Cavity) lThis is an example of a nave Bayes （樸素貝葉斯）model:P(Cause,Effect1,

14、 ,Effectn) = P(Cause) iP(Effecti|Cause)lTotal number of parameters is linear in n貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò) 1 貝葉斯網(wǎng)絡(luò)概述2 貝葉斯網(wǎng)絡(luò)的語(yǔ)義3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理概率公式概率公式()(|)( )P XYP X YP Y()()(|)P XYP X P YX11( )() (|)() (|)nnP YP X P Y XP XP Y X條件概率公式乘法公式全概率公式邊緣化與條件化邊緣化與條件化l聯(lián)合概率分布l邊緣化（求和消元）lP(toothache) = 0.108 + 0.012 +

15、0.016 + 0.064 = 0.2l條件化：( )( , )zP YP Y z( )(| ) ( )zP YP Yz P z貝葉斯法則貝葉斯法則l由乘法法則 P(ab) = P(a | b) P(b) = P(b | a) P(a) Bayes rule: P(a | b) = P(b | a) P(a) / P(b)l一般形式： l更通用版本（條件化）：(|, )(| )(|, )(| )P XY e P YeP YX eP Xe(|)( )(|)(|)( )()P XY P YP YXP XY P YP X1()( ) (|)niiiP XP Y P X Y貝葉斯網(wǎng)絡(luò)的由來l隨機(jī)方法？

16、每個(gè)狀態(tài)值取決于前面有限個(gè)狀態(tài) ，如Markov鏈。l在現(xiàn)實(shí)生活中，很多事物相互的關(guān)系并不能用一條鏈來串起來；它們之間的關(guān)系可能是交叉的、錯(cuò)綜復(fù)雜的。如疾病的起因，故障的原因等。貝葉斯網(wǎng)絡(luò)的由來l全聯(lián)合概率計(jì)算復(fù)雜性十分巨大；l變量之間的獨(dú)立性和條件獨(dú)立性能大大減少為了定義全聯(lián)合概率分布所需的概率數(shù)目。l需要一種自然、有效的方式來根據(jù)不確定性知識(shí)推理貝葉斯網(wǎng)絡(luò)；貝葉斯網(wǎng)絡(luò)的定義l貝葉斯網(wǎng)絡(luò)(Bayesian network)是一個(gè)有向圖，其中每個(gè)節(jié)點(diǎn)都標(biāo)注了定量概率信息：n 一個(gè)隨機(jī)變量集合組成網(wǎng)絡(luò)節(jié)點(diǎn)，變量可以是離散的或者連續(xù)的；n 一個(gè)連接節(jié)點(diǎn)對(duì)的有向邊或者箭頭的集合，如果存在從節(jié)點(diǎn)X指向

17、節(jié)點(diǎn)Y的有向邊，則稱X是Y的一個(gè)父節(jié)點(diǎn)；n 每個(gè)節(jié)點(diǎn)都存在一個(gè)條件概率分布P(Xi|Parent(Xi)，量化父節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的影響；n 圖中不存在有向環(huán)(是有向無(wú)環(huán)圖DAG)。 簡(jiǎn)單例子簡(jiǎn)單例子l表示前例中條件獨(dú)立的拓?fù)渚W(wǎng)絡(luò):lWeather is independent of the other variableslToothache and Catch are conditionally independent given Cavity 防盜網(wǎng)BurglaryEarthquakeMaryCallsJohnCallsAlarm0.950.940.290.001 t t t f f t f f

18、P(A) B E0.900.05 t fP(J) A0.700.01 t fP(M) A0.001P(B) 0.002P(E) l每個(gè)節(jié)點(diǎn)旁的條件概率表(簡(jiǎn)稱CPTCPT)中的值對(duì)應(yīng)一個(gè)條件事件的概率如P(A)=0.94=P(A|BurglaryEarthquake)；條件事件是父節(jié)點(diǎn)取值的一個(gè)可能組合；每行的概率之和應(yīng)為1(表中只給出了為真的情況，為假的概率應(yīng)為1-p)；一個(gè)具有k個(gè)布爾父節(jié)點(diǎn)的布爾變量的條件概率表中有2k個(gè)獨(dú)立的可指定的概率(注意概率值是獨(dú)立的)；沒有父節(jié)點(diǎn)的節(jié)點(diǎn)的概率只有1行，為先驗(yàn)概率。 0.700.01 t fP(M) A貝葉斯網(wǎng)絡(luò)的概率解釋貝葉斯網(wǎng)絡(luò)的概率解釋l任何

19、完整的概率模型必須具有表示（直接或間接）該領(lǐng)域變量聯(lián)合分布的能力，完全的枚舉需要指數(shù)級(jí)的規(guī)模（相對(duì)于領(lǐng)域變量個(gè)數(shù)）；l貝葉斯網(wǎng)絡(luò)提供了這種聯(lián)合概率分布的緊湊表示：分解聯(lián)合分布為幾個(gè)局部分布的乘積：iiinpaxPxxxP)|(),(21貝葉斯網(wǎng)絡(luò)的概率解釋貝葉斯網(wǎng)絡(luò)的概率解釋l從公式可以看出，需要的參數(shù)個(gè)數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)呈線性增長(zhǎng)，而聯(lián)合分布的計(jì)算呈指數(shù)增長(zhǎng)。l網(wǎng)絡(luò)中變量間獨(dú)立性的指定是實(shí)現(xiàn)緊湊表示的關(guān)鍵。l獨(dú)立性在通過人類專家構(gòu)造貝葉斯網(wǎng)中特別有效。貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò) 1 貝葉斯網(wǎng)絡(luò)概述2 貝葉斯網(wǎng)絡(luò)的語(yǔ)義3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理l貝葉斯網(wǎng)絡(luò)給出了關(guān)于相關(guān)事件的

20、完整描述，通過計(jì)算全聯(lián)合概率分布求取聯(lián)合分布中的某項(xiàng)是對(duì)每個(gè)變量賦予一個(gè)特定值情況下的合取概率就是條件概率表中適當(dāng)元素的乘積例子 P(jmabe)=P(j|a)P(m|a)P(a|be)P(b)P(e)=0.90*0.70*0.001*0.999*0.998=0.00062 niiinnXparentxPxnxPxXxXP111)(|(),.1(),.,(l乘法規(guī)則：P(x1,x2, xn)=P(xn|xn-1 ,x1,) P(xn-1 ,x1 ,) l鏈?zhǔn)椒▌t(chain rule)：P(Xi|Xi-1,X1)=P(Xi|Parent(Xi)Parent(Xi) Xi-1,X1l初始的合取概

21、率化為更小的條件概率和更小的合取式 l這些條件概率的合取式實(shí)際上就是父節(jié)點(diǎn)到子節(jié)點(diǎn)的概率乘積。l父子節(jié)點(diǎn)的關(guān)系使得貝葉斯網(wǎng)絡(luò)具有局部結(jié)構(gòu)化的特性，即每個(gè)節(jié)點(diǎn)只和數(shù)量有限的其它部分產(chǎn)生直接的相互作用 防盜網(wǎng)BurglaryEarthquakeMaryCallsJohnCallsAlarmP(m | j, a, b, e) =P(m | a)l貝葉斯網(wǎng)絡(luò)的局部結(jié)構(gòu)化（locally structed）每個(gè)隨機(jī)變量可以至多受到k個(gè)其它隨機(jī)變量的影響(k=常數(shù))；設(shè)網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)(隨機(jī)變量)，指定每個(gè)條件概率表所需信息量至多為2k個(gè)數(shù)據(jù)，則整個(gè)網(wǎng)絡(luò)可以用n2k個(gè)數(shù)據(jù)完全描述/而全聯(lián)合概率分布需要2n

22、個(gè)數(shù)據(jù).比較：n=30, k=5.l構(gòu)造貝葉斯網(wǎng)絡(luò)的次序：添加節(jié)點(diǎn)首先從“根本原因”開始，然后加入受其直接影響的變量，直到葉節(jié)點(diǎn)(不影響任何其它節(jié)點(diǎn))。 lSuppose we choose the ordering M, J, A, B, EP(J | M) = P(J)?ExamplelSuppose we choose the ordering M, J, A, B, EP(J | M) = P(J)?NoP(A | J, M) = P(A | J)? P(A | J, M) = P(A)?ExamplelSuppose we choose the ordering M, J, A, B

23、, EP(J | M) = P(J)?NoP(A | J, M) = P(A | J)? P(A | J, M) = P(A)? NoP(B | A, J, M) = P(B | A)? P(B | A, J, M) = P(B)?ExamplelSuppose we choose the ordering M, J, A, B, EP(B | A, J, M) = P(B | A)? Yes (JohnCalls and MaryCalls increase the chance of alarm.)P(B | A, J, M) = P(B)? NoP(E | B, A ,J, M) = P

24、(E | B)?P(E | B, A, J, M) = P(E | A, B)?ExamplelSuppose we choose the ordering M, J, A, B, EP(J | M) = P(J)?No P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? NoP(B | A, J, M) = P(B | A)? YesP(B | A, J, M) = P(B)? NoP(E | B, A, J, M) = P(E | B)? NoP(E | B, A, J, M) = P(E | B, A)? Yes (P(E | B, A) P(E |

25、A)P(E | B, A ,J, M) = P(E | A)? NoExampleExample contd.lNetwork is less compact: 1 + 2 + 4 + 2 + 4 = 13 numbers neededlDeciding conditional independence is hard in noncausal directions(Causal models and conditional independence seem hardwired for humans!)l貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)相互獨(dú)立(下面兩個(gè)定義等價(jià))：(1)給定父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)與它的非后代節(jié)點(diǎn)

26、是條件獨(dú)立的 ；(2)給定一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)以及子節(jié)點(diǎn)的父節(jié)點(diǎn)(Markov blanket)，這個(gè)節(jié)點(diǎn)對(duì)于其它節(jié)點(diǎn)都是條件獨(dú)立的。圖示，例子 U1UmXZ1jZnjY1YnU1UmXZ1jZnjY1Yn給定父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)與它的非后代節(jié)點(diǎn)是條件獨(dú)立的JohnCall給定一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)以及子節(jié)點(diǎn)的父節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)對(duì)于其它節(jié)點(diǎn)都是條件獨(dú)立的。Burglarynoisy-ORl貝葉斯網(wǎng)絡(luò)中盡管父節(jié)點(diǎn)個(gè)數(shù)k很小，但是要完成條件概率表仍需要O(2k)數(shù)據(jù)；l如果找到了變量依賴的某種關(guān)系，則可以用O(k)個(gè)參數(shù)完成條件概率表噪聲或(noisy-OR)關(guān)系用于刻畫不確定關(guān)系(邏輯或的推廣)

27、；l噪聲或關(guān)系考慮到每個(gè)父節(jié)點(diǎn)引起子節(jié)點(diǎn)為真的能力的不確定性: 父節(jié)點(diǎn)條件為真但子節(jié)點(diǎn)的結(jié)果未必為真。 l例子：發(fā)燒(fever)為真，當(dāng)且僅當(dāng)以下三者之一為真：感冒(cold)/流感(flu)/瘧疾(malaria)但是可能病人得了以上疾病卻沒有發(fā)燒癥狀這就是父節(jié)點(diǎn)為真其子節(jié)點(diǎn)未必真的不確定性即父子關(guān)系被抑制此時(shí)可以認(rèn)為：fever為假當(dāng)且僅當(dāng)所有為真的父節(jié)點(diǎn)被抑制，其概率為每個(gè)父節(jié)點(diǎn)被抑制的概率的乘積l兩條假設(shè)所有原因已經(jīng)列出每個(gè)父節(jié)點(diǎn)的抑制獨(dú)立于其他父節(jié)點(diǎn)的抑制 l假設(shè)每個(gè)單獨(dú)抑制的概率如下 P(fever|cold,flu,malaria)=0.6P(fever|cold,flu,ma

28、laria)=0.2P(fever|cold,flu,malaria)=0.1l目的：為建立一個(gè)完整的條件概率表，大大減少所需參數(shù)，如：P(fever|cold,flu,malaria)=0.2*0.1=0.02 P(fever|cold,flu,malaria)=0.6*0.2*0.1=0.012 P(fever|cold,flu,malaria)=1-0.012=0.988Cold Flu MalariaP(Fever)P(Fever) F F F0.01.0 F F T0.91-0.9=0.1 F T F0.81-0.8=0.2 T F F0.41-0.4=0.6 F T T1-0.02

29、=0.980.1*0.2=0.02 T F T1-0.06=0.940.1*0.6=0.06 T T F1-0.12=0.880.2*0.6=0.12 T T T1-0.012=0.9880.1*0.2*0.6=0.012448節(jié)點(diǎn)，906邊8254個(gè)數(shù)據(jù)，而不是133,931,430貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò) 1 貝葉斯概率基礎(chǔ)2 貝葉斯網(wǎng)絡(luò)的表示3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理l基本任務(wù)是計(jì)算被查詢變量的后驗(yàn)概率：設(shè)X為待查詢變量，e為觀察到的證據(jù)，E=E1Em證據(jù)變量集合，Y=Y1Yn非證據(jù)變量集合(也稱隱變量)全部變量集合=XEY推理的任務(wù)是：求后驗(yàn)概率P(X|e)實(shí)際上，

30、根據(jù)邊緣化規(guī)則可得 P(X|e)=P(X,e)=yP(X,e,y) l回答查詢：在貝葉斯網(wǎng)絡(luò)中計(jì)算條件概率的乘積并求和。l以防盜警報(bào)為例，求P(B|J=T,M=F)證據(jù)JohnCalls=True/MaryCalls=False查詢變量Burglary=True隱含變量Earthquake/Alarml用首字母簡(jiǎn)化式有：P(b|j,m)=P(b,j,m) =EAP(b,E,A,j,m) l進(jìn)一步代入條件概率：P(b|j,m)=EAP(b)P(E)P(A|b,e)P(j|A)P(m|A)l上式最壞復(fù)雜度O(n2n) ，將相對(duì)常數(shù)移到求和符號(hào)以外：P(b|j,m)=P(b)EP(E)AP(A|b,

31、E)P(j|A)P(m|A)l計(jì)算過程(遍歷A=a/a和E=e/e)P(j|a)=0.90P(m|a)=0.30P(j|a)=0.05P(m|a)=0.99P(a|b,e)=0.95P(a|b,e)=0.05P(a|b,e)=0.94 P(a|b,e)=0.06 l乘積求和過程：EP(E)AP(A|b,E)P(j|A)P(m|A) q=P(e)*AP(A|b,e)P(j|A)P(m|A)+P(e)*AP(A|b,e)P(j|A)P(m|A)q=P(e)*P(a|b,e)*P(j|a)*P(m|a)+P(a|b,e)* P(j|a)*P(m|a)+P(e)*P(a|b,e)*P(j|a)* P(

32、m|a)+P(a|b,e)* P(j|a)*P(m|a)q=0.002*0.95*0.90*0.30+0.05*0.05*0.99+0.998*0.94*0.90*0.30+0.06*0.05*0.99q=0.002*0.2565+0.0025+0.998*0.2538+0.0030 q=0.002*0.2590+0.998*0.2568=0.2568l相應(yīng)地有：P ( b | j , m ) = P ( b ) * 0 . 2 5 6 8 = 0 . 0 0 1 * 0 . 2 5 6 8=*0.0002568l類似地有：P(b|j,m)=*P(b)EP(E)AP(A|b,E)P(j|A)P

33、(m|A)=*P(b)*0.002*(0.0783+0.0351) +0.998*(0.0003+0.0495)=*0.999*0.0499 =*0.0499l歸一化以后有：P(B|j,m)=只有John打電話而出現(xiàn)盜賊的概率小于1/100 計(jì)算P(B |j,m)的枚舉樹的枚舉樹l在計(jì)算中我們發(fā)現(xiàn)P(j|a)*P(m|a)和P(j|a)*P(m|a)重復(fù)計(jì)算了兩次，如何消除重復(fù)？只要保留一次計(jì)算結(jié)果既可。按照從右到左的次序計(jì)算。例子： 例子： 對(duì)M和J，用二元向量表示保存每個(gè)給定的a下的概率： A的因子P( a | B, e)是一個(gè) 2 x 2 x 2 的矩陣f A (A, B, E). 首先

34、對(duì)A求和消去，得到一個(gè)只有B和E的2 x 2 的矩陣： A上加一橫表示已經(jīng)通過求和消去。使用乘法的過程稱為點(diǎn)積(pointwise product)例子： 對(duì)E求和消去： 最后，可以簡(jiǎn)單的將B的因子與上述累積矩陣相乘來計(jì)算答案：點(diǎn)積（點(diǎn)積（pointwise product）l在這樣的計(jì)算中只要做：計(jì)算兩個(gè)因子的點(diǎn)積在因子乘積中對(duì)一個(gè)變量求和消元l在計(jì)算中，消除以下無(wú)關(guān)節(jié)點(diǎn)：刪除不是查詢變量也非證據(jù)變量的葉節(jié)點(diǎn)刪除所有不是查詢變量，祖先也不是證據(jù)變量的節(jié)點(diǎn)P(JohnCalls l Burglary = true).l單連通結(jié)構(gòu)貝葉斯網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)都至多只有一條無(wú)向路徑相連；l此時(shí)，單連通

35、上的精確推理的時(shí)間和空間復(fù)雜度都和網(wǎng)絡(luò)規(guī)模呈線性關(guān)系；l而對(duì)于多連通結(jié)構(gòu)(見下圖)，最壞情況下變量消元法可能具有指數(shù)級(jí)的時(shí)空復(fù)雜度此時(shí)貝葉斯網(wǎng)絡(luò)的推理是一個(gè)NP問題；l所以要尋找多連通網(wǎng)絡(luò)中的近似算法。 S R P(W)T T .99T F .90F T .90F F .00C P(R)T .80F .20sprinklerRainWet grassC P(S)T .10F .50P(C)=.5cloudy貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò) 1 貝葉斯概率基礎(chǔ)2 貝葉斯網(wǎng)絡(luò)的表示3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理l大規(guī)模多連通網(wǎng)絡(luò)的精確推理是不可操作的，所以要考慮近似的推理方法.l采用隨機(jī)采

36、樣方法，也稱蒙特卡羅算法(Monte Carlo algorithm)：給出近似解答，近似的精度依賴于所生成采樣點(diǎn)的多少。例如：求積分。l此處近似的含義：不是通過計(jì)算求出網(wǎng)絡(luò)中某個(gè)點(diǎn)的條件概率(因?yàn)閺?fù)雜度高)，而是對(duì)該事件進(jìn)行采樣而獲得概率 l有兩類采樣方法直接采樣方法：計(jì)算樣本的頻率馬爾科夫鏈采樣方法：根據(jù)馬爾科夫覆蓋中的變量當(dāng)前值來采樣直接采樣方法l依據(jù)已知概率來生成樣本l拒絕采樣算法 / 似然加權(quán)算法馬爾科夫鏈采樣方法l證據(jù)變量概率固定條件下隨機(jī)生成樣本 l任何采樣算法中最基本的要素是根據(jù)已知概率分布生成樣本。l例如：一個(gè)無(wú)偏差的硬幣是一個(gè)隨機(jī)變量Coin，其可能取值為.先驗(yàn)概率是P(C

37、oin)=.l直接采樣方法是按照拓?fù)浣Y(jié)構(gòu)次序依次對(duì)每個(gè)變量進(jìn)行采樣，被采樣變量值的概率分布依賴于父節(jié)點(diǎn)已取得的賦值。l具體實(shí)現(xiàn)： l樣本的向量表示cloudy, sprinkler, rain, wetGrass F/T或者0/1表示為假或?yàn)檎?/ 如T, F, T, Tl采樣按照已知概率分布進(jìn)行，但不是等于這個(gè)概率分布值，而是說分布與之相符cloudy=0.5,0.5 / 第1次采樣49/51，第2次采樣52/48如此等等l每次采樣應(yīng)該在一定的條件下(這就是條件概率)進(jìn)行，不滿足條件的樣本不再考慮 l通過例子說明采樣過程 / 算法均省略(1)因?yàn)镻(cloudy)=, 故cloudy的采樣樣

38、本T/F各占50%，假設(shè)(不妨)返回T(2)P(sprinkler|cloudy=T)=，故sprinkler的采樣樣本T/F各占10%和90%，應(yīng)該返回F（注意：此時(shí)采樣樣本均為形式，其中占10%，占90%）(3)P(rain|cloudy=T)=，故rain的采樣樣本T/F各占80%和20%, 應(yīng)該返回T / 樣本形式類似于(2) (4)P(wetGrass|sprinkler=F, rain=T)=，則返回T / 采樣樣本形式占90%，占10%l實(shí)際上如此生成的樣本完全符合先驗(yàn)概率，即l對(duì)于上例，cloudy sprinkler rain wetGrass =T F T T=0.5*0.

39、9*0.8*0.9=0.324 niiinnpsxParentxPxxPxxS111)(|().().(l從已知分布的采樣出發(fā)(其計(jì)算如上)，通過去掉不滿足證據(jù)條件的樣本來計(jì)算(估計(jì))那些未知分布的事件的概率例子：P(Rain|Sprinkler=T)未知其概率 采樣100個(gè)樣本：l其中73個(gè)為，不滿足前提條件l余下的27個(gè)中8個(gè)為rain=T / 19個(gè)為rain=FlP(Rain|Sprinkler=T)=l拒絕采樣方法的最大問題就是效率比較低(相當(dāng)一部分樣本被拒絕了) l拒絕采樣方法能產(chǎn)生真實(shí)概率的一致估計(jì)l估計(jì)的概率在無(wú)限多(大量樣本的極限)條件下成為精確值，這樣的估計(jì)稱為一致的(co

40、nsistent)，即 l只生成與證據(jù)e一致的事件，避免拒絕采樣的低效率。對(duì)證據(jù)節(jié)點(diǎn)的概率進(jìn)行似然加權(quán)，即按照先驗(yàn)概率的乘積進(jìn)行計(jì)算 / 對(duì)非證據(jù)節(jié)點(diǎn)進(jìn)行采樣，采樣樣本服從先驗(yàn)概率分布例子：求P(rain| sprinkler=T, wetGrass=T)的概率采樣過程如下：(1)權(quán)值w=1.0(2)P(cloudy)=，據(jù)此采樣，返回T(3)Sprinkler是證據(jù)變量，取值T，則ww*P(sprinkler=T|cloudy=T)=1.0*0.1=0.1 (4)P(rain|cloudy=T)=，據(jù)此進(jìn)行采樣，假設(shè)=T(5)wetGrass是證據(jù)變量，取值T，則有ww*P(wetGrass

41、=T|sprinkler=T,rain=T)=0.1*0.99=0.099此即cloudy sprinkler rain wetGrass=T T T T =0.099 .解釋：sprinkler=T & wetGrass=T條件下rain=T的概率很低l似然加權(quán)方法也得到對(duì)于真實(shí)概率的一致估計(jì)l從采樣與加權(quán)的乘積去理解聯(lián)合分布概率的計(jì)算，依然是全部條件概率的乘積. 小權(quán)值的樣本占到大多數(shù)l直接采樣法按照先驗(yàn)概率去采樣l馬爾科夫鏈采樣對(duì)證據(jù)變量以外的變量每次隨機(jī)地采樣舉例：考慮求P(rain | sprinkler=T,wetGrass=T)證據(jù)變量固定：sprinkler=T/wet

42、Grass=T隱變量cloudy/rain則隨機(jī)采樣：初始值不妨假設(shè)cloudy=T/rain=F初始狀態(tài)= 證據(jù)變量固定下，狀態(tài)空間內(nèi)的隨機(jī)走動(dòng)然后反復(fù)按照以下2個(gè)步驟采樣(1)當(dāng)前條件下對(duì)cloudy隨機(jī)采樣，結(jié)果=(2)當(dāng)前條件下對(duì)rain隨機(jī)采樣，結(jié)果=最后得到若干樣本，例如rain=T=20 / rain=F=60，則P(rain|sprinkler=T,wetGrass=T)= = l馬爾科夫鏈采樣過程最終會(huì)進(jìn)入“動(dòng)態(tài)平衡”狀態(tài)被采樣變量服從馬爾科夫覆蓋下的條件概率分布，且“穩(wěn)態(tài)分布”=真實(shí)后驗(yàn)概率P(x|e)l我們所需要求解的正是給定證據(jù)變量e下某個(gè)變量的概率值P(x|e)l證明

43、過程：轉(zhuǎn)移概率狀態(tài)x到狀態(tài)x q(xx)時(shí)刻t處于狀態(tài)x的概率t(x) 下一時(shí)刻處于狀態(tài)x的概率 t+1(x)=xt(x)q(xx)穩(wěn)態(tài)分布(stationary distribution)：當(dāng)t+1(x)=t(x)時(shí)，馬爾科夫鏈達(dá)到穩(wěn)態(tài)分布，即(省略t) (x)=x(x)q(xx)對(duì)于所有x細(xì)致平衡任意兩個(gè)狀態(tài)間沿兩個(gè)方向轉(zhuǎn)換概率相等 (x)q(xx)=(x)q(xx)對(duì)于所有x, x簡(jiǎn)單公式推導(dǎo)(求和)可證明細(xì)致平衡中蘊(yùn)含著穩(wěn)態(tài)分布 幾點(diǎn)總結(jié)幾點(diǎn)總結(jié)l貝葉斯網(wǎng)絡(luò)的特點(diǎn)：雙向推理能力（預(yù)測(cè)和診斷）快速的調(diào)試和重構(gòu)能力具有較強(qiáng)的概率統(tǒng)計(jì)基礎(chǔ)用于人工智能和專家系統(tǒng)的不確定推理（優(yōu)于早期的基于規(guī)則

44、的模式）。l這種網(wǎng)絡(luò)支持任何變量子集相對(duì)于另一子集的條件概率計(jì)算。l貝葉斯網(wǎng)絡(luò)是域中變量關(guān)系的直接表示，而不是推理過程。網(wǎng)絡(luò)中的方向表示變量間真正的因果關(guān)系而不是推理過程的信息流向。 因此在貝葉斯推理過程中，推理過程可以沿任何方向進(jìn)行（預(yù)測(cè)、診斷、解釋）。BN定性描述定性描述l貝葉斯網(wǎng)絡(luò)中每個(gè)圓圈表示一個(gè)狀態(tài)。狀態(tài)之間的連線表示它們的因果關(guān)系。l和馬爾可夫鏈類似，貝葉斯網(wǎng)絡(luò)中的每個(gè)狀態(tài)值取決于前面有限個(gè)狀態(tài)。不同的是，貝葉斯網(wǎng)絡(luò)比馬爾可夫鏈靈活，它不受馬爾可夫鏈的鏈狀結(jié)構(gòu)的約束，因此可以更準(zhǔn)確地描述事件之間的相關(guān)性。l可以講，馬爾可夫鏈?zhǔn)秦惾~斯網(wǎng)絡(luò)的特例，而貝葉斯網(wǎng)絡(luò)是馬爾可夫鏈的推廣。 發(fā)展

45、歷史（發(fā)展歷史（1）l貝葉斯（Reverend Thomas Bayes 1702-1761）學(xué)派奠基性的工作是貝葉斯的論文“關(guān)于幾率性問題求解的評(píng)論”。l著名的數(shù)學(xué)家拉普拉斯（Laplace P. S. 1749-1827）用貝葉斯的方法導(dǎo)出了重要的“相繼律”，貝葉斯的方法和理論逐漸被人理解和重視起來。l但由于當(dāng)時(shí)貝葉斯方法在理論和實(shí)際應(yīng)用中還存在很多不完善的地方，因而在十九世紀(jì)并未被普遍接受。發(fā)展歷史（發(fā)展歷史（2）l二十世紀(jì)初，意大利的菲納特（B. de Finetti）以及英國(guó)的杰弗萊（Jeffreys H.）都對(duì)貝葉斯學(xué)派的理論作出重要的貢獻(xiàn)。l第二次世界大戰(zhàn)后，瓦爾德（Wald A.）提出了統(tǒng)計(jì)的決策理論，在這一理論中，貝葉斯解占有重要的地位；信息論的發(fā)展也對(duì)貝葉斯學(xué)派做出了新的貢獻(xiàn)。l1958年英國(guó)最悠久的統(tǒng)計(jì)雜志Biometrika全文重新刊登了貝葉斯的論