邏輯推理人工智能演示文稿

邏輯推理人工智能演示文稿第一頁，共九十二頁。優(yōu)選邏輯推理人工智能第二頁，共九十二頁。不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法則及其應(yīng)用第三頁，共九十二頁。不確定性（Uncertainty）定義行動At=航班起飛前t分鐘啟程前往機場；問：At

能不能及時使agent趕上飛機？A180

是一個可靠的行動，如果所選路線上沒有交通事故、沒有交通管制、汽車沒有出故障、沒有沙塵暴，等等，等等。(A1440

或許是個一定不會耽誤飛機的計劃，不過要在機場過夜)邏輯方法使得Agent在得到關(guān)于環(huán)境的足夠多事實時，使得行動計劃得到保證。但是，沒有任何agent能夠獲得關(guān)于其環(huán)境的全部事實。第四頁，共九十二頁。FOL與不確定性FOL能夠處理不確定性嗎？醫(yī)學專家系統(tǒng)：pSymptom(p,Toothache)Disease(p,Cavity)?引起牙痛的原因：牙洞？窮舉牙洞與牙痛有必然聯(lián)系嗎？失敗的原因：懶惰(laziness):failuretoenumerateexceptions,qualifications,etc.無知(ignorance):lackofrelevantfacts,initialconditions,etc.第五頁，共九十二頁。不確定環(huán)境下的決策基本思想：精確度和有效性的折中理性決策的含義既依賴于各種目標的相對重要性，也依賴于這些目標將被實現(xiàn)的可能性（程度）。假設(shè)A180理性決策，這意味著在給定所處的環(huán)境信息下，它是所有可執(zhí)行的規(guī)劃中智能體的性能度量期望達到最大的那個。性能度量：及時趕上飛機、等待時間不長，…第六頁，共九十二頁。不確定環(huán)境下的決策例如：給出行動及其成功的概率如下:

P(A25getsmethereontime|…) =0.04P(A90getsmethereontime|…) =0.70P(A120getsmethereontime|…) =0.95P(A1440getsmethereontime|…) =0.9999該選哪一個行動?例如，取決于成功的幾率以及等待時間的折中。必須考慮效用理論（Utilitytheory）決策論＝概率論＋效用論Decisiontheory=probabilitytheory+utilitytheory第七頁，共九十二頁。不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法則及其應(yīng)用第八頁，共九十二頁。概率理論（Probabilitytheory

）Agent的知識提供的最多是關(guān)于語句的信度（degreeofbelief）。概率論可以處理我們的惰性和無知。概率是宇宙的真實方面：它是物體的行為表現(xiàn)為特定方式的傾向，而不僅僅是對觀察者信心的描述。概率與證據(jù)：在評估語句的概率時，必須指出有關(guān)證據(jù)。Agent獲得新的信息后，其概率評估應(yīng)該更新。先驗概率、后驗概率第九頁，共九十二頁。先驗概率與命題a相關(guān)的無條件概率，在沒有任何其它信息存在的情況下，關(guān)于命題的信度，記為：P（a）。例如，用P（weather）表示天氣的概率：P（weather＝sunny）＝0.7P（weather＝rain）＝0.2P（weather＝cloudy）＝0.08P（weather＝snow）＝0.02先驗概率分布：P（weather）＝<0.7,0.2,0.08,0.02>聯(lián)合概率分布，全聯(lián)合概率分布概率密度函數(shù)第十頁，共九十二頁。后驗（條件）概率得到與命題a相關(guān)的變量的證據(jù)，先驗概率失效，需要以后驗概率替代，記為：P（a|b）例如：P（cavity|toothache）＝0.7乘法規(guī)則：P（ab）＝P（b|a）P（a）第十一頁，共九十二頁。概率公理（Axiomsofprobability）對任意命題A,B:0≤P(A)≤1P(true)=1，P(false)=0P(A

B)=P(A)+P(B)-P(A

B)Kolmogorov公理第十二頁，共九十二頁。不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法則及其應(yīng)用第十三頁，共九十二頁。聯(lián)合概率分布聯(lián)合概率分布（jointprobabilitydistribution）:表中catch是指由于牙醫(yī)的鋼探針不潔而導致的牙齦感染對任何命題φ,其概率是所有原子證據(jù)事件概率的和：P(φ)=Σω:ω╞φP(ω)第十四頁，共九十二頁。聯(lián)合概率分布（枚舉）Startwiththejointprobabilitydistribution:Foranypropositionφ,sumtheatomiceventswhereitistrue:P(φ)=Σω:ω╞φP(ω)P(toothache)=0.108+0.012+0.016+0.064=0.2第十五頁，共九十二頁。Startwiththejointprobabilitydistribution,Canalsocomputeconditionalprobabilities:

P(cavity|toothache) =P(cavity

toothache) P(toothache) = 0.016+0.064 0.108+0.012+0.016+0.064 =0.4聯(lián)合概率分布（枚舉）第十六頁，共九十二頁。歸一化（Normalization）(Denominator)-1

＝normalizationconstantαP(Cavity|toothache)=αP(Cavity,toothache)=α[P(Cavity,toothache,catch)+P(Cavity,toothache,

catch)]=α[<0.108,0.016>+<0.012,0.064>]=α<0.12,0.08>=<0.6,0.4>Generalidea:computedistributiononqueryvariablebyfixingevidencevariablesandsummingoverhiddenvariables.第十七頁，共九十二頁。不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法則及其應(yīng)用第十八頁，共九十二頁。獨立性（Independence）A

與B

獨立，當且僅當

P(A|B)=P(A)orP(B|A)=P(B)orP(A,B)=P(A)P(B)例如：P(Toothache,Catch,Cavity,Weather) =P(Toothache,Catch,Cavity)P(Weather)32entriesreducedto12(weatherhas4possiblevalues);fornindependentbiasedcoins,O(2n)

→O(n)絕對獨立很好但很少見，例如牙科中可能涉及幾百相互關(guān)聯(lián)的變量，這時候如何處理？第十九頁，共九十二頁。條件獨立（Conditionalindependence）已知有一個牙洞，鉆具感染與牙疼的概率相互獨立：鉆具感染與牙痛在給定牙洞的情況下是條件獨立的conditionallyindependent

P(Toothache,Catch|Cavity)=P(Toothache|Cavity)P(Catch|Cavity)第二十頁，共九十二頁。條件獨立推導聯(lián)合分布，將全聯(lián)合分布分解成很多更小的分布:

P(Toothache,Catch,Cavity)

=P(Toothache,Catch|Cavity)P(Cavity)乘法法則 =P(Toothache|Cavity)P(Catch|Cavity)P(Cavity)條件獨立 I.e.,2+2+1=5independentnumbers條件分布將聯(lián)合分布的表示空間由指數(shù)級降到線性。條件概率是處理不確定信息的基礎(chǔ)和最魯棒的形式。第二十一頁，共九十二頁。不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法則及其應(yīng)用第二十二頁，共九十二頁。貝葉斯法則（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.,letMbemeningitis,Sbestiffneck:P(m|s)=P(s|m)P(m)/P(s)=0.8×0.0001/0.1=0.0008第二十三頁，共九十二頁。貝葉斯法則與條件獨立P(Cavity|toothachecatch)=αP(toothachecatch|Cavity)P(Cavity)=αP(toothache|Cavity)P(catch|Cavity)P(Cavity)

Thisisanexampleofana?veBayes

（樸素貝葉斯）model:P(Cause,Effect1,…,Effectn)=P(Cause)iP(Effecti|Cause)Totalnumberofparametersislinearinn第二十四頁，共九十二頁。貝葉斯網(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ò)的由來隨機方法？每個狀態(tài)值取決于前面有限個狀態(tài)，如Markov鏈。在現(xiàn)實生活中，很多事物相互的關(guān)系并不能用一條鏈來串起來；它們之間的關(guān)系可能是交叉的、錯綜復(fù)雜的。如疾病的起因，故障的原因等。第二十九頁，共九十二頁。貝葉斯網(wǎng)絡(luò)的由來全聯(lián)合概率計算復(fù)雜性十分巨大；變量之間的獨立性和條件獨立性能大大減少為了定義全聯(lián)合概率分布所需的概率數(shù)目。需要一種自然、有效的方式來根據(jù)不確定性知識推理——貝葉斯網(wǎng)絡(luò)；第三十頁，共九十二頁。貝葉斯網(wǎng)絡(luò)的定義貝葉斯網(wǎng)絡(luò)(Bayesiannetwork)是一個有向圖，其中每個節(jié)點都標注了定量概率信息：一個隨機變量集合組成網(wǎng)絡(luò)節(jié)點，變量可以是離散的或者連續(xù)的；一個連接節(jié)點對的有向邊或者箭頭的集合，如果存在從節(jié)點X指向節(jié)點Y的有向邊，則稱X是Y的一個父節(jié)點；每個節(jié)點都存在一個條件概率分布P(Xi|Parent(Xi))，量化父節(jié)點對該節(jié)點的影響；圖中不存在有向環(huán)(是有向無環(huán)圖DAG)。

第三十一頁，共九十二頁。簡單例子表示前例中條件獨立的拓撲網(wǎng)絡(luò):WeatherisindependentoftheothervariablesToothacheandCatchareconditionallyindependentgivenCavity第三十二頁，共九十二頁。貝葉斯網(wǎng)絡(luò)的表示

——防盜網(wǎng)BurglaryEarthquakeMaryCallsJohnCallsAlarm0.950.940.290.001

tttfftffP(A)

BE0.900.05

tfP(J)

A0.700.01

tfP(M)

A0.001P(B)0.002P(E)第三十三頁，共九十二頁。條件概率表每個節(jié)點旁的條件概率表(簡稱CPT)中的值對應(yīng)一個條件事件的概率如P(A)=0.94=P(A|Burglary∧Earthquake)；條件事件是父節(jié)點取值的一個可能組合；每行的概率之和應(yīng)為1(表中只給出了為真的情況，為假的概率應(yīng)為1-p)；一個具有k個布爾父節(jié)點的布爾變量的條件概率表中有2k個獨立的可指定的概率(注意概率值是獨立的)；沒有父節(jié)點的節(jié)點的概率只有1行，為先驗概率。

0.700.01

tfP(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ù)個數(shù)隨網(wǎng)絡(luò)中節(jié)點個數(shù)呈線性增長，而聯(lián)合分布的計算呈指數(shù)增長。網(wǎng)絡(luò)中變量間獨立性的指定是實現(xiàn)緊湊表示的關(guān)鍵。獨立性在通過人類專家構(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)事件的完整描述，通過計算全聯(lián)合概率分布求取聯(lián)合分布中的某項是對每個變量賦予一個特定值情況下的合取概率就是條件概率表中適當元素的乘積例子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

第三十八頁，共九十二頁。一種貝葉斯網(wǎng)絡(luò)構(gòu)建方法乘法規(guī)則：P(x1,x2,…xn)=P(xn|xn-1,…,x1,)P(xn-1,…,x1,)鏈式法則(chainrule)：P(Xi|Xi-1,…,X1)=P(Xi|Parent(Xi))Parent(Xi)){Xi-1,…,X1}初始的合取概率化為更小的條件概率和更小的合取式這些條件概率的合取式實際上就是父節(jié)點到子節(jié)點的概率乘積。父子節(jié)點的關(guān)系使得貝葉斯網(wǎng)絡(luò)具有局部結(jié)構(gòu)化的特性，即每個節(jié)點只和數(shù)量有限的其它部分產(chǎn)生直接的相互作用第三十九頁，共九十二頁。貝葉斯網(wǎng)絡(luò)的構(gòu)造

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

第四十一頁，共九十二頁。SupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?Example第四十二頁，共九十二頁。SupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?Example第四十三頁，共九十二頁。SupposewechoosetheorderingM,J,A,B,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)?Example第四十四頁，共九十二頁。SupposewechoosetheorderingM,J,A,B,EP(B|A,J,M)=P(B|A)?Yes(JohnCallsandMaryCallsincreasethechanceofalarm.)P(B|A,J,M)=P(B)?NoP(E|B,A,J,M)=P(E|B)?P(E|B,A,J,M)=P(E|A,B)?Example第四十五頁，共九十二頁。SupposewechoosetheorderingM,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|A))P(E|B,A,J,M)=P(E|A)?NoExample第四十六頁，共九十二頁。Examplecontd.Networkislesscompact:1+2+4+2+4=13numbersneededDecidingconditionalindependenceishardinnoncausaldirections(Causalmodelsandconditionalindependenceseemhardwiredforhumans!)第四十七頁，共九十二頁。條件獨立關(guān)系貝葉斯網(wǎng)絡(luò)中節(jié)點相互獨立(下面兩個定義等價)：(1)給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的；(2)給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點(Markovblanket)，這個節(jié)點對于其它節(jié)點都是條件獨立的。圖示，例子

第四十八頁，共九十二頁。條件獨立關(guān)系圖示

U1UmXZ1jZnjY1YnU1UmXZ1jZnjY1Yn給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的JohnCall給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點，這個節(jié)點對于其它節(jié)點都是條件獨立的。Burglary第四十九頁，共九十二頁。條件分布的有效表達：noisy-OR貝葉斯網(wǎng)絡(luò)中盡管父節(jié)點個數(shù)k很小，但是要完成條件概率表仍需要O(2k)數(shù)據(jù)；如果找到了變量依賴的某種關(guān)系，則可以用O(k)個參數(shù)完成條件概率表—噪聲或(noisy-OR)關(guān)系用于刻畫不確定關(guān)系(邏輯或的推廣)；噪聲或關(guān)系考慮到每個父節(jié)點引起子節(jié)點為真的能力的不確定性:父節(jié)點條件為真但子節(jié)點的結(jié)果未必為真。

第五十頁，共九十二頁。噪聲或關(guān)系（1）例子：發(fā)燒(fever)為真，當且僅當以下三者之一為真：感冒(cold)/流感(flu)/瘧疾(malaria)但是可能病人得了以上疾病卻沒有發(fā)燒癥狀這就是父節(jié)點為真其子節(jié)點未必真的不確定性—即父子關(guān)系被抑制此時可以認為：fever為假當且僅當所有為真的父節(jié)點被抑制，其概率為每個父節(jié)點被抑制的概率的乘積兩條假設(shè)所有原因已經(jīng)列出每個父節(jié)點的抑制獨立于其他父節(jié)點的抑制

第五十一頁，共九十二頁。噪聲或關(guān)系（2）假設(shè)每個單獨抑制的概率如下

P(fever|cold,flu,malaria)=0.6 P(fever|cold,flu,malaria)=0.2 P(fever|cold,flu,malaria)=0.1目的：為建立一個完整的條件概率表，大大減少所需參數(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.988第五十二頁，共九十二頁。噪聲或關(guān)系（3）ColdFluMalariaP(Fever)P(?Fever)

FFF0.01.0

FFT0.91-0.9=0.1

FTF0.81-0.8=0.2

TFF0.41-0.4=0.6

FTT1-0.02=0.980.1*0.2=0.02

TFT1-0.06=0.940.1*0.6=0.06

TTF1-0.12=0.880.2*0.6=0.12

TTT1-0.012=0.9880.1*0.2*0.6=0.012448節(jié)點，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ù)是計算被查詢變量的后驗概率：設(shè)X為待查詢變量，e為觀察到的證據(jù)，E={E1…Em}證據(jù)變量集合，Y={Y1…Yn}非證據(jù)變量集合(也稱隱變量)全部變量集合={X}∪E∪Y推理的任務(wù)是：求后驗概率P(X|e)實際上，根據(jù)邊緣化規(guī)則可得

P(X|e)=P(X,e)=∑yP(X,e,y)

第五十五頁，共九十二頁。查詢實例（1）回答查詢：在貝葉斯網(wǎng)絡(luò)中計算條件概率的乘積并求和。以防盜警報為例，求P(B|J=T,M=F)證據(jù)JohnCalls=True/MaryCalls=False查詢變量Burglary=True隱含變量Earthquake/Alarm用首字母簡化式有：P(b|j,m)=P(b,j,m)=∑E∑AP(b,E,A,j,m)

第五十六頁，共九十二頁。查詢實例（2）進一步代入條件概率：P(b|j,m)=∑E∑AP(b)P(E)P(A|b,e)P(j|A)P(m|A)上式最壞復(fù)雜度O(n2n)，將相對常數(shù)移到求和符號以外：P(b|j,m)=P(b)∑EP(E)∑AP(A|b,E)P(j|A)P(m|A)計算過程(遍歷A=a/a和E=e/e)P(j|a)=0.90 P(m|a)=0.30P(j|a)=0.05 P(m|a)=0.99P(a|b,e)=0.95 P(a|b,e)=0.05P(a|b,e)=0.94 P(a|b,e)=0.06

第五十七頁，共九十二頁。查詢實例（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)*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第五十八頁，共九十二頁。查詢實例（4）相應(yīng)地有：P(b|j,m)=P(b)*0.2568=0.001*0.2568 =*0.0002568類似地有：P(b|j,m)=*P(b)∑EP(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)=<0.0003,0.0499>=<0.006,0.994>只有John打電話而出現(xiàn)盜賊的概率小于1/100★

第五十九頁，共九十二頁。計算P(B|j,m)的枚舉樹第六十頁，共九十二頁。變量消元法（1）在計算中我們發(fā)現(xiàn)P(j|a)*P(m|a)和P(j|a)*P(m|a)重復(fù)計算了兩次，如何消除重復(fù)？只要保留一次計算結(jié)果既可。按照從右到左的次序計算。例子：

第六十一頁，共九十二頁。例子：對M和J，用二元向量表示保存每個給定的a下的概率：A的因子P(a|B,e)是一個2x2x2的矩陣fA(A,B,E).首先對A求和消去，得到一個只有B和E的2x2的矩陣：A上加一橫表示已經(jīng)通過求和消去。使用乘法的過程稱為點積(pointwiseproduct)第六十二頁，共九十二頁。例子：對E求和消去：最后，可以簡單的將B的因子與上述累積矩陣相乘來計算答案：第六十三頁，共九十二頁。點積（pointwiseproduct）第六十四頁，共九十二頁。變量消元法（2）在這樣的計算中只要做：計算兩個因子的點積在因子乘積中對一個變量求和消元在計算中，消除以下無關(guān)節(jié)點：刪除不是查詢變量也非證據(jù)變量的葉節(jié)點刪除所有不是查詢變量，祖先也不是證據(jù)變量的節(jié)點P(JohnCallslBurglary=true).第六十五頁，共九十二頁。精確推理的復(fù)雜度單連通結(jié)構(gòu)—貝葉斯網(wǎng)絡(luò)中任何兩個節(jié)點都至多只有一條無向路徑相連；此時，單連通上的精確推理的時間和空間復(fù)雜度都和網(wǎng)絡(luò)規(guī)模呈線性關(guān)系；而對于多連通結(jié)構(gòu)(見下圖)，最壞情況下變量消元法可能具有指數(shù)級的時空復(fù)雜度—此時貝葉斯網(wǎng)絡(luò)的推理是一個NP問題；所以要尋找多連通網(wǎng)絡(luò)中的近似算法。

第六十六頁，共九十二頁。多連通網(wǎng)絡(luò)

SRP(W)TT.99TF.90FT.90FF.00CP(R)T.80F.20sprinklerRainWetgrassCP(S)T.10F.50P(C)=.5cloudy第六十七頁，共九十二頁。貝葉斯網(wǎng)絡(luò)

1貝葉斯概率基礎(chǔ)

2貝葉斯網(wǎng)絡(luò)的表示

3貝葉斯網(wǎng)絡(luò)中的精確推理

4貝葉斯網(wǎng)絡(luò)的近似推理第六十八頁，共九十二頁。貝葉斯網(wǎng)絡(luò)的近似推理大規(guī)模多連通網(wǎng)絡(luò)的精確推理是不可操作的，所以要考慮近似的推理方法.采用隨機采樣方法，也稱蒙特卡羅算法(MonteCarloalgorithm)：給出近似解答，近似的精度依賴于所生成采樣點的多少。例如：求積分。此處近似的含義：不是通過計算求出網(wǎng)絡(luò)中某個點的條件概率(因為復(fù)雜度高)，而是對該事件進行采樣而獲得概率

第六十九頁，共九十二頁。后驗概率計算的采樣方法有兩類采樣方法直接采樣方法：計算樣本的頻率馬爾科夫鏈采樣方法：根據(jù)馬爾科夫覆蓋中的變量當前值來采樣直接采樣方法依據(jù)已知概率來生成樣本拒絕采樣算法/似然加權(quán)算法馬爾科夫鏈采樣方法證據(jù)變量概率固定條件下隨機生成樣本

第七十頁，共九十二頁。采樣方法的要素任何采樣算法中最基本的要素是根據(jù)已知概率分布生成樣本。例如：一個無偏差的硬幣是一個隨機變量Coin，其可能取值為<正,反>.先驗概率是P(Coin)=<0.5,0.5>.第七十一頁，共九十二頁。直接采樣方法直接采樣方法是按照拓撲結(jié)構(gòu)次序依次對每個變量進行采樣，被采樣變量值的概率分布依賴于父節(jié)點已取得的賦值。具體實現(xiàn)：

第七十二頁，共九十二頁。采樣樣本與概率分布樣本的向量表示{cloudy,sprinkler,rain,wetGrass}F/T或者0/1表示為假或為真/如{T,F,T,T}采樣按照已知概率分布進行，但不是等于這個概率分布值，而是說分布與之相符cloudy={0.5,0.5}/第1次采樣49/51，第2次采樣52/48……如此等等每次采樣應(yīng)該在一定的條件下(這就是條件概率)進行，不滿足條件的樣本不再考慮

第七十三頁，共九十二頁。采樣過程舉例（1）通過例子說明采樣過程/算法均省略(1)因為P(cloudy)=<0.5,0.5>,故cloudy的采樣樣本T/F各占50%，假設(shè)(不妨)返回T(2)P(sprinkler|cloudy=T)=<0.1,0.9>，故sprinkler的采樣樣本T/F各占10%和90%，應(yīng)該返回F（注意：此時采樣樣本均為<TXXX>形式，其中<TTXX>占10%，<TFXX>占90%）(3)P(rain|cloudy=T)=<0.8,0.2>，故rain的采樣樣本T/F各占80%和20%,應(yīng)該返回T/樣本形式類似于(2)

第七十四頁，共九十二頁。采樣過程舉例（2）(4)P(wetGrass|sprinkler=F,rain=T)=<0.9,0.1>，則返回T/采樣樣本形式<TFTT>占90%， <TFTF>占10%實際上如此生成的樣本完全符合先驗概率，即對于上例，{cloudysprinklerrainwetGrass}={TFTT}=0.5*0.9*0.8*0.9=0.324

第七十五頁，共九十二頁。拒絕采樣方法從已知分布的采樣出發(fā)(其計算如上)，通過去掉不滿足證據(jù)條件的樣本來計算(估計)那些未知分布的事件的概率例子：P(Rain|Sprinkler=T)未知其概率

采樣100個樣本：其中73個為<XFXX>，不滿足前提條件余下的27個中8個為rain=T/19個為rain=FP(Rain|Sprinkler=T)=<8,19>=<0.296,0.704>拒絕采樣方法的最大問題就是效率比較低(相當一部分樣本被拒絕了)

第七十六頁，共九十二頁。一致的估計拒絕采樣方法能產(chǎn)生真實概率的一致估計估計的概率在無限多(大量樣本的極限)條件下成為精確值，這樣的估計稱為一致的(consistent)，即

第七十七頁，共九十二頁。似然加權(quán)方法（1）只生成與證據(jù)e一致的事件，避免拒絕采樣的低效率。對證據(jù)節(jié)點的概率進行似然加權(quán)，即按照先驗概率的乘積進行計算/對非證據(jù)節(jié)點進行采樣，采樣樣本服從先驗概率分布例子：求P(rain|sprinkler=T,wetGrass=T)的概率采樣過程如下：(1)權(quán)值w=1.0(2)P(cloudy)=<0.50.5>，據(jù)此采樣，返回T(3)Sprinkler是證據(jù)變量，取值T，則

w←w*P(sprinkler=T|cloudy=T)=1.0*0.1=0.1

第七十八頁，共九十二頁。似然加權(quán)方法（2）(4)P(rain|cloudy=T)=<0.80.2>，據(jù)此進行采樣，假設(shè)=T(5)wetGrass是證據(jù)變量，取值T，則有

w←w*P(wetGrass=T|sprinkler=T,rain=T) =0.1*0.99=0.099此即{cloudysprinklerrainwetGrass}={TTTT}=0.099.解釋：sprinkler=T&wetGrass=T條件下rain=T的概率很低似然加權(quán)方法也得到對于真實概率的一致估計從采樣與加權(quán)的乘積去理解聯(lián)合分布概率的計算，依然是全部條件概率的乘積.

小權(quán)值的樣本占到大多數(shù)第七十九頁，共九十二頁。馬爾科夫鏈采樣（1）直接采樣法按照先驗概率去采樣馬爾科夫鏈采樣對證據(jù)變量以外的變量每次隨機地采樣舉例：考慮求P(rain|sprinkler=T,wetGrass=T)證據(jù)變量固定：sprinkler=T/wetGrass=T隱變量cloudy/rain則隨機采樣：初始值不妨假設(shè)cloudy=T/rain=F初始狀態(tài)=<TTFT>

證據(jù)變量固定下，狀態(tài)空間內(nèi)的隨機走動第八十頁，共九十二頁。馬爾科夫鏈采樣（2）然后反復(fù)按照以下2個步驟采樣(1)當前條件下<XTFT>對cloudy隨機采樣，結(jié)果=<FTFT>(2)當前條件下<FTXT>對rain隨機采樣，結(jié)果=<FTTT>最后得到若干樣本，例如[rain=T]=20/[rain=F]=60，則P(rain|sprinkler=T,wetGrass=T)=<20,60>=<0.250.75>

第八十一頁，共九十二頁。馬爾科夫鏈采樣的合理性（1）馬爾科夫鏈采樣過程最終會進入“動態(tài)平衡”狀態(tài)—被采樣變量服從馬爾科夫覆蓋下的條件概率分布，且“穩(wěn)態(tài)分布”=真實后驗概率P(x|e)我們所需要求解的正是給定證據(jù)變量e下某個變量的概率值P(x|e)證明過程：轉(zhuǎn)移概率—狀態(tài)x到狀態(tài)x’ q(x→x’)時刻t處于狀態(tài)x的概率 t(x)

第八十二頁，共九十二頁。馬爾科夫鏈采樣的合理性（2）下一時刻處于狀態(tài)x’的概率

t+1(x’)=∑xt(x)q(x→x’)穩(wěn)態(tài)分布(stationarydistribution)：當t+1(x’)=t(x’)時，馬爾科夫鏈達到穩(wěn)態(tài)分布，即(省略t) (x’)=∑x(x)q(x→x’) 對于所有x’細致平衡—任意兩個狀態(tài)間沿兩個方向轉(zhuǎn)換概率相等 (x)q(x→x’)=(x’)q(x’→x) 對于所有x,x’簡單公式推導(求和)可證明細致平衡中蘊含著穩(wěn)態(tài)分布

第八十三頁，共九十二頁。幾點總結(jié)貝葉斯網(wǎng)絡(luò)的特點：雙向推理能力（預(yù)測和診斷）快速的調(diào)試和重構(gòu)能力具有較強的概率統(tǒng)計基礎(chǔ)用于人工智能和專家系統(tǒng)的不確定推理（優(yōu)于早期的基于規(guī)則的模式）。這種網(wǎng)絡(luò)支持任何變量子集相對于另一子集的條件概率計算。貝葉斯網(wǎng)絡(luò)是域中變量關(guān)系的直接表示，而不是推理過程。網(wǎng)絡(luò)中的方向表示變量間真正的因果關(guān)系而不是推理過程的信息流向。－－因此在貝葉斯推理過程中，推理過程可以沿任何方向進行（預(yù)測、診斷、解釋）。第八十四頁，共九十二頁。BN定性描述貝葉斯網(wǎng)絡(luò)中每個圓圈表示一個狀態(tài)。狀態(tài)之間的連線表示它們的因果關(guān)系。和馬爾可夫鏈類似，貝葉斯網(wǎng)絡(luò)中的每個狀態(tài)值取決于前面有限個狀態(tài)。不同的是，貝葉斯網(wǎng)絡(luò)比馬爾可夫鏈靈活，它不受馬爾可夫鏈的鏈狀結(jié)構(gòu)的約束，因此可以更準確地描述事件之間的相關(guān)性?？梢灾v，