邏輯推理 _人工智能

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

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

3、A180理性決策，這意味著在給定所處的環(huán)境信息下，它是所有可執(zhí)行的規(guī)劃中智能體的性能度量期望達(dá)到最大的那個。 性能度量：及時趕上飛機(jī)、等待時間不長，,不確定環(huán)境下的決策,例如：給出行動及其成功的概率如下: 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 該選哪一個行動? 例如，取決于成功的幾率以及等待時間的折中。 必須考慮效

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

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

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

7、(),聯(lián)合概率分布（枚舉）,Start with the joint probability distribution: For any proposition , sum the atomic events where it is true: P() = : P() P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2,Start with the joint probability distribution, Can also compute conditional probabilities: P(cavity | toothache) =

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

9、query variable by fixing evidence variables and summing over hidden variables.,不確定性,不確定環(huán)境下的行動 概率公理 使用全概率分布進(jìn)行推理 獨(dú)立性 貝葉斯法則及其應(yīng)用,獨(dú)立性（Independence）,A 與 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(Toothache, Catch, Cavity) P(Weather) 32 entri

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

11、avity),條件獨(dú)立,推導(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 numbers 條件分布將聯(lián)合分布的表示空間由指數(shù)級降到線性。 條件概率是處理不確定信息的基礎(chǔ)和最魯棒的形式。,不確定性,不確定環(huán)境下的行動 概率公理 使用全概率分布進(jìn)行推理 獨(dú)立性 貝葉斯法則及其應(yīng)

12、用,貝葉斯法則（Bayes Rule）,由乘法法則 P(ab) = P(a | b) P(b) = P(b | a) P(a) Bayes rule: P(a | b) = P(b | a) P(a) / P(b) 一般形式： P(Y|X) = P(X|Y) P(Y) / P(X) = P(X|Y) P(Y) 例子：用于從病因（causal）中找到診斷（diagnostic）結(jié)論 : P(Cause|Effect) = P(Effect|Cause) P(Cause) / P(Effect) E.g., let M be meningitis, S be stiff neck: P(m|s)

13、= P(s|m) P(m) / P(s) = 0.8 0.0001 / 0.1 = 0.0008,貝葉斯法則與條件獨(dú)立,P(Cavity | toothache catch) = P(toothache catch | Cavity) P(Cavity) = P(toothache | Cavity) P(catch | Cavity) P(Cavity) This is an example of a nave Bayes （樸素貝葉斯）model: P(Cause,Effect1, ,Effectn) = P(Cause) iP(Effecti|Cause) Total number of

14、 parameters is linear in n,貝葉斯網(wǎng)絡(luò),1 貝葉斯網(wǎng)絡(luò)概述2 貝葉斯網(wǎng)絡(luò)的語義3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理,概率公式,條件概率公式,乘法公式,全概率公式,邊緣化與條件化,聯(lián)合概率分布 邊緣化（求和消元） P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2 條件化：,貝葉斯法則,由乘法法則 P(ab) = P(a | b) P(b) = P(b | a) P(a) Bayes rule: P(a | b) = P(b | a) P(a) / P(b) 一般形式： 更通用版本（條件化）：,貝葉斯網(wǎng)絡(luò)的

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

16、如果存在從節(jié)點(diǎn)X指向節(jié)點(diǎn)Y的有向邊，則稱X是Y的一個父節(jié)點(diǎn)； 每個節(jié)點(diǎn)都存在一個條件概率分布P(Xi|Parent(Xi)，量化父節(jié)點(diǎn)對該節(jié)點(diǎn)的影響； 圖中不存在有向環(huán)(是有向無環(huán)圖DAG)。,簡單例子,表示前例中條件獨(dú)立的拓?fù)渚W(wǎng)絡(luò): Weather is independent of the other variables Toothache and Catch are conditionally independent given Cavity,貝葉斯網(wǎng)絡(luò)的表示 防盜網(wǎng),條件概率表,每個節(jié)點(diǎn)旁的條件概率表(簡稱CPT)中的值對應(yīng)一個條件事件的概率 如P(A)=0.94=P(A|Burgla

17、ryEarthquake)； 條件事件是父節(jié)點(diǎn)取值的一個可能組合； 每行的概率之和應(yīng)為1(表中只給出了為真的情況，為假的概率應(yīng)為1-p)； 一個具有k個布爾父節(jié)點(diǎn)的布爾變量的條件概率表中有2k個獨(dú)立的可指定的概率(注意概率值是獨(dú)立的)； 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)的概率只有1行，為先驗(yàn)概率。,0.70 0.01,t f,P(M),A,貝葉斯網(wǎng)絡(luò)的概率解釋,任何完整的概率模型必須具有表示（直接或間接）該領(lǐng)域變量聯(lián)合分布的能力，完全的枚舉需要指數(shù)級的規(guī)模（相對于領(lǐng)域變量個數(shù)）； 貝葉斯網(wǎng)絡(luò)提供了這種聯(lián)合概率分布的緊湊表示：分解聯(lián)合分布為幾個局部分布的乘積：,貝葉斯網(wǎng)絡(luò)的概率解釋,從公式可以看出，需要的參數(shù)個

18、數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)呈線性增長，而聯(lián)合分布的計(jì)算呈指數(shù)增長。 網(wǎng)絡(luò)中變量間獨(dú)立性的指定是實(shí)現(xiàn)緊湊表示的關(guān)鍵。 獨(dú)立性在通過人類專家構(gòu)造貝葉斯網(wǎng)中特別有效。,貝葉斯網(wǎng)絡(luò),1 貝葉斯網(wǎng)絡(luò)概述2 貝葉斯網(wǎng)絡(luò)的語義3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理,貝葉斯網(wǎng)絡(luò)的語義,貝葉斯網(wǎng)絡(luò)給出了關(guān)于相關(guān)事件的完整描述，通過計(jì)算全聯(lián)合概率分布求取 聯(lián)合分布中的某項(xiàng)是對每個變量賦予一個特定值情況下的合取概率 就是條件概率表中適當(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,一種貝葉斯網(wǎng)絡(luò)

19、構(gòu)建方法,乘法規(guī)則： P(x1,x2, xn)=P(xn|xn-1 ,x1,) P(xn-1 ,x1 ,) 鏈?zhǔn)椒▌t(chain rule)： P(Xi|Xi-1,X1)=P(Xi|Parent(Xi) Parent(Xi) Xi-1,X1 初始的合取概率化為更小的條件概率和更小的合取式 這些條件概率的合取式實(shí)際上就是父節(jié)點(diǎn)到子節(jié)點(diǎn)的概率乘積。 父子節(jié)點(diǎn)的關(guān)系使得貝葉斯網(wǎng)絡(luò)具有局部結(jié)構(gòu)化的特性，即每個節(jié)點(diǎn)只和數(shù)量有限的其它部分產(chǎn)生直接的相互作用,貝葉斯網(wǎng)絡(luò)的構(gòu)造 防盜網(wǎng),Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,P(m | j, a, b, e

20、) =P(m | a),緊致性與節(jié)點(diǎn)順序,貝葉斯網(wǎng)絡(luò)的局部結(jié)構(gòu)化（locally structed） 每個隨機(jī)變量可以至多受到k個其它隨機(jī)變量的影響(k=常數(shù))； 設(shè)網(wǎng)絡(luò)中有n個節(jié)點(diǎn)(隨機(jī)變量)，指定每個條件概率表所需信息量至多為2k個數(shù)據(jù)，則整個網(wǎng)絡(luò)可以用n2k個數(shù)據(jù)完全描述/而全聯(lián)合概率分布需要2n個數(shù)據(jù). 比較：n=30, k=5. 構(gòu)造貝葉斯網(wǎng)絡(luò)的次序：添加節(jié)點(diǎn)首先從“根本原因”開始，然后加入受其直接影響的變量，直到葉節(jié)點(diǎn)(不影響任何其它節(jié)點(diǎn))。,Suppose we choose the ordering M, J, A, B, E P(J | M) = P(J)?,Example,

21、Suppose we choose the ordering M, J, A, B, E P(J | M) = P(J)? No P(A | J, M) = P(A | J)? P(A | J, M) = P(A)?,Example,Suppose we choose the ordering M, J, A, B, E P(J | M) = P(J)? No P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No P(B | A, J, M) = P(B | A)? P(B | A, J, M) = P(B)?,Example,Suppose we ch

22、oose the ordering M, J, A, B, E P(B | A, J, M) = P(B | A)? Yes (JohnCalls and MaryCalls increase the chance of alarm.) P(B | A, J, M) = P(B)? No P(E | B, A ,J, M) = P(E | B)? P(E | B, A, J, M) = P(E | A, B)?,Example,Suppose we choose the ordering M, J, A, B, E P(J | M) = P(J)? No P(A | J, M) = P(A |

23、 J)? P(A | J, M) = P(A)? No P(B | A, J, M) = P(B | A)? Yes P(B | A, J, M) = P(B)? No P(E | B, A, J, M) = P(E | B)? No P(E | B, A, J, M) = P(E | B, A)? Yes (P(E | B, A) P(E | A) P(E | B, A ,J, M) = P(E | A)? No,Example,Example contd.,Network is less compact: 1 + 2 + 4 + 2 + 4 = 13 numbers needed Deci

24、ding conditional independence is hard in noncausal directions (Causal models and conditional independence seem hardwired for humans!),條件獨(dú)立關(guān)系,貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)相互獨(dú)立(下面兩個定義等價)： (1)給定父節(jié)點(diǎn)，一個節(jié)點(diǎn)與它的非后代節(jié)點(diǎn)是條件獨(dú)立的 ； (2)給定一個節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)以及子節(jié)點(diǎn)的父節(jié)點(diǎn)(Markov blanket)，這個節(jié)點(diǎn)對于其它節(jié)點(diǎn)都是條件獨(dú)立的。 圖示，例子,條件獨(dú)立關(guān)系圖示,給定父節(jié)點(diǎn)，一個節(jié)點(diǎn)與 它的非后代節(jié)點(diǎn)是條件獨(dú)立的 Jo

25、hnCall,給定一個節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)以及 子節(jié)點(diǎn)的父節(jié)點(diǎn)，這個節(jié)點(diǎn)對于 其它節(jié)點(diǎn)都是條件獨(dú)立的。Burglary,條件分布的有效表達(dá)：noisy-OR,貝葉斯網(wǎng)絡(luò)中盡管父節(jié)點(diǎn)個數(shù)k很小，但是要完成條件概率表仍需要O(2k)數(shù)據(jù)； 如果找到了變量依賴的某種關(guān)系，則可以用O(k)個參數(shù)完成條件概率表噪聲或(noisy-OR)關(guān)系用于刻畫不確定關(guān)系(邏輯或的推廣)； 噪聲或關(guān)系考慮到每個父節(jié)點(diǎn)引起子節(jié)點(diǎn)為真的能力的不確定性: 父節(jié)點(diǎn)條件為真但子節(jié)點(diǎn)的結(jié)果未必為真。,噪聲或關(guān)系（1）,例子： 發(fā)燒(fever)為真，當(dāng)且僅當(dāng)以下三者之一為真：感冒(cold)/流感(flu)/瘧疾(malaria

26、) 但是可能病人得了以上疾病卻沒有發(fā)燒癥狀 這就是父節(jié)點(diǎn)為真其子節(jié)點(diǎn)未必真的不確定性即父子關(guān)系被抑制 此時可以認(rèn)為：fever為假當(dāng)且僅當(dāng)所有為真的父節(jié)點(diǎn)被抑制，其概率為每個父節(jié)點(diǎn)被抑制的概率的乘積 兩條假設(shè) 所有原因已經(jīng)列出 每個父節(jié)點(diǎn)的抑制獨(dú)立于其他父節(jié)點(diǎn)的抑制,噪聲或關(guān)系（2）,假設(shè)每個單獨(dú)抑制的概率如下 P(fever|cold,flu,malaria)=0.6P(fever|cold,flu,malaria)=0.2P(fever|cold,flu,malaria)=0.1 目的： 為建立一個完整的條件概率表，大大減少所需參數(shù)，如： P(fever|cold,flu,malaria)

27、=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.988,噪聲或關(guān)系（3）,448節(jié)點(diǎn)，906邊 8254個數(shù)據(jù)，而不是133,931,430,貝葉斯網(wǎng)絡(luò),1 貝葉斯概率基礎(chǔ)2 貝葉斯網(wǎng)絡(luò)的表示3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理,貝葉斯網(wǎng)絡(luò)中的精確推理,基本任務(wù)是計(jì)算被查詢變量的后驗(yàn)概率： 設(shè)X為待查詢變量，e為觀察到的證據(jù)，E=E1Em證據(jù)變量集合，Y=Y1Yn非證據(jù)變量集合(也稱隱變量) 全部變量集合=XEY 推理的任務(wù)是：求后驗(yàn)概率P(

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

29、號以外： P(b|j,m)=P(b)EP(E)AP(A|b,E)P(j|A)P(m|A) 計(jì)算過程(遍歷A=a/a和E=e/e) P(j|a)=0.90P(m|a)=0.30 P(j|a)=0.05P(m|a)=0.99 P(a|b,e)=0.95P(a|b,e)=0.05 P(a|b,e)=0.94 P(a|b,e)=0.06,查詢實(shí)例（3）,乘積求和過程： EP(E)AP(A|b,E)P(j|A)P(m|A),=P(e)*AP(A|b,e)P(j|A)P(m|A)+P(e)*AP(A|b,e)P(j|A)P(m|A),=P(e)*P(a|b,e)*P(j|a)*P(m|a)+P(a|b,e

30、)* P(j|a)*P(m|a) +P(e)*P(a|b,e)*P(j|a)* P(m|a)+P(a|b,e)* P(j|a)*P(m|a),=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.99,=0.002*0.2565+0.0025+0.998*0.2538+0.0030 =0.002*0.2590+0.998*0.2568=0.2568,查詢實(shí)例（4）,相應(yīng)地有： P(b|j,m)=P(b)*0.2568=0.001*0.2568=*0.0002568 類似地有： P(b|j,m)=*P(b)EP

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

32、 2 x 2 x 2 的矩陣f A (A, B, E). 首先對A求和消去，得到一個只有B和E的2 x 2 的矩陣： A上加一橫表示已經(jīng)通過求和消去。,使用乘法的過程稱為點(diǎn)積(pointwise product),例子：,對E求和消去： 最后，可以簡單的將B的因子與上述累積矩陣相乘來計(jì)算答案：,點(diǎn)積（pointwise product）,變量消元法（2）,在這樣的計(jì)算中只要做： 計(jì)算兩個因子的點(diǎn)積 在因子乘積中對一個變量求和消元 在計(jì)算中，消除以下無關(guān)節(jié)點(diǎn)： 刪除不是查詢變量也非證據(jù)變量的葉節(jié)點(diǎn) 刪除所有不是查詢變量，祖先也不是證據(jù)變量的節(jié)點(diǎn) P(JohnCalls l Burglary =

33、true).,精確推理的復(fù)雜度,單連通結(jié)構(gòu)貝葉斯網(wǎng)絡(luò)中任何兩個節(jié)點(diǎn)都至多只有一條無向路徑相連； 此時，單連通上的精確推理的時間和空間復(fù)雜度都和網(wǎng)絡(luò)規(guī)模呈線性關(guān)系； 而對于多連通結(jié)構(gòu)(見下圖)，最壞情況下變量消元法可能具有指數(shù)級的時空復(fù)雜度此時貝葉斯網(wǎng)絡(luò)的推理是一個NP問題； 所以要尋找多連通網(wǎng)絡(luò)中的近似算法。,多連通網(wǎng)絡(luò),貝葉斯網(wǎng)絡(luò),1 貝葉斯概率基礎(chǔ)2 貝葉斯網(wǎng)絡(luò)的表示3 貝葉斯網(wǎng)絡(luò)中的精確推理4 貝葉斯網(wǎng)絡(luò)的近似推理,貝葉斯網(wǎng)絡(luò)的近似推理,大規(guī)模多連通網(wǎng)絡(luò)的精確推理是不可操作的，所以要考慮近似的推理方法. 采用隨機(jī)采樣方法，也稱蒙特卡羅算法(Monte Carlo algorithm)：

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

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

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

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

38、稱為一致的(consistent)，即,似然加權(quán)方法（1）,只生成與證據(jù)e一致的事件，避免拒絕采樣的低效率。 對證據(jù)節(jié)點(diǎn)的概率進(jìn)行似然加權(quán)，即按照先驗(yàn)概率的乘積進(jìn)行計(jì)算 / 對非證據(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,似然加權(quán)方法（2）,(4)P(rain|cloudy=T)=，據(jù)此進(jìn)行采樣，假設(shè)=T (

39、5)wetGrass是證據(jù)變量，取值T，則有 ww*P(wetGrass=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的概率很低 似然加權(quán)方法也得到對于真實(shí)概率的一致估計(jì) 從采樣與加權(quán)的乘積去理解聯(lián)合分布概率的計(jì)算，依然是全部條件概率的乘積.,小權(quán)值的樣本占到大多數(shù),馬爾科夫鏈采樣（1）,直接采樣法按照先驗(yàn)概率去采樣 馬爾科夫鏈采樣對證據(jù)變量以外的變量每次隨機(jī)地采樣 舉例：考慮求P(rain |

40、 sprinkler=T,wetGrass=T) 證據(jù)變量固定：sprinkler=T/wetGrass=T 隱變量cloudy/rain則隨機(jī)采樣：初始值不妨假設(shè)cloudy=T/rain=F 初始狀態(tài)=,證據(jù)變量固定下，狀態(tài)空間內(nèi)的隨機(jī)走動,馬爾科夫鏈采樣（2）,然后反復(fù)按照以下2個步驟采樣 (1)當(dāng)前條件下對cloudy隨機(jī)采樣，結(jié)果= (2)當(dāng)前條件下對rain隨機(jī)采樣，結(jié)果= 最后得到若干樣本，例如rain=T=20 / rain=F=60，則P(rain|sprinkler=T,wetGrass=T)= =,馬爾科夫鏈采樣的合理性（1）,馬爾科夫鏈采樣過程最終會進(jìn)入“動態(tài)平衡”狀態(tài)

41、被采樣變量服從馬爾科夫覆蓋下的條件概率分布，且“穩(wěn)態(tài)分布”=真實(shí)后驗(yàn)概率P(x|e) 我們所需要求解的正是給定證據(jù)變量e下某個變量的概率值P(x|e) 證明過程： 轉(zhuǎn)移概率狀態(tài)x到狀態(tài)xq(xx) 時刻t處于狀態(tài)x的概率t(x),馬爾科夫鏈采樣的合理性（2）,下一時刻處于狀態(tài)x的概率 t+1(x)=xt(x)q(xx) 穩(wěn)態(tài)分布(stationary distribution)：當(dāng)t+1(x)=t(x)時，馬爾科夫鏈達(dá)到穩(wěn)態(tài)分布，即(省略t) (x)=x(x)q(xx)對于所有x 細(xì)致平衡任意兩個狀態(tài)間沿兩個方向轉(zhuǎn)換概率相等 (x)q(xx)=(x)q(xx)對于所有x, x 簡單公式推導(dǎo)(求

42、和)可證明細(xì)致平衡中蘊(yùn)含著穩(wěn)態(tài)分布,幾點(diǎn)總結(jié),貝葉斯網(wǎng)絡(luò)的特點(diǎn)： 雙向推理能力（預(yù)測和診斷） 快速的調(diào)試和重構(gòu)能力 具有較強(qiáng)的概率統(tǒng)計(jì)基礎(chǔ) 用于人工智能和專家系統(tǒng)的不確定推理（優(yōu)于早期的基于規(guī)則的模式）。 這種網(wǎng)絡(luò)支持任何變量子集相對于另一子集的條件概率計(jì)算。 貝葉斯網(wǎng)絡(luò)是域中變量關(guān)系的直接表示，而不是推理過程。網(wǎng)絡(luò)中的方向表示變量間真正的因果關(guān)系而不是推理過程的信息流向。 因此在貝葉斯推理過程中，推理過程可以沿任何方向進(jìn)行（預(yù)測、診斷、解釋）。,BN定性描述,貝葉斯網(wǎng)絡(luò)中每個圓圈表示一個狀態(tài)。狀態(tài)之間的連線表示它們的因果關(guān)系。 和馬爾可夫鏈類似，貝葉斯網(wǎng)絡(luò)中的每個狀態(tài)值取決于前面有限個狀態(tài)。

43、不同的是，貝葉斯網(wǎng)絡(luò)比馬爾可夫鏈靈活，它不受馬爾可夫鏈的鏈狀結(jié)構(gòu)的約束，因此可以更準(zhǔn)確地描述事件之間的相關(guān)性。 可以講，馬爾可夫鏈?zhǔn)秦惾~斯網(wǎng)絡(luò)的特例，而貝葉斯網(wǎng)絡(luò)是馬爾可夫鏈的推廣。,發(fā)展歷史（1）,貝葉斯（Reverend Thomas Bayes 1702-1761）學(xué)派奠基性的工作是貝葉斯的論文“關(guān)于幾率性問題求解的評論”。 著名的數(shù)學(xué)家拉普拉斯（Laplace P. S. 1749-1827）用貝葉斯的方法導(dǎo)出了重要的“相繼律”，貝葉斯的方法和理論逐漸被人理解和重視起來。 但由于當(dāng)時貝葉斯方法在理論和實(shí)際應(yīng)用中還存在很多不完善的地方，因而在十九世紀(jì)并未被普遍接受。,發(fā)展歷史（2）,二十世紀(jì)初，意大利的菲納特（B. de Finetti）以及英國的杰弗萊（Jeffreys H.）都對貝葉斯學(xué)派的理論作出重要的貢獻(xiàn)。 第二次世界大戰(zhàn)后，瓦爾德（Wald A.）提出了統(tǒng)計(jì)的決策理論，在這一理論中，貝葉斯解占有重要的地位；信息論的發(fā)展也對貝葉斯學(xué)派做出了新的貢獻(xiàn)。 1958年英國最悠久的統(tǒng)計(jì)雜志Biometrika全文重新刊登了貝葉斯的論文，20世紀(jì)50年代，以羅賓斯（Robb