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

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

能不能及時(shí)使agent趕上飛機(jī)？A180

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

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

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

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

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

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

與B

獨(dú)立，當(dāng)且僅當(dāng)

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)絕對(duì)獨(dú)立很好但很少見(jiàn)，例如牙科中可能涉及幾百相互關(guān)聯(lián)的變量，這時(shí)候如何處理？第十九頁(yè)，共九十二頁(yè)。條件獨(dú)立（Conditionalindependence）已知有一個(gè)牙洞，鉆具感染與牙疼的概率相互獨(dú)立：鉆具感染與牙痛在給定牙洞的情況下是條件獨(dú)立的conditionallyindependent

P(Toothache,Catch|Cavity)=P(Toothache|Cavity)P(Catch|Cavity)第二十頁(yè)，共九十二頁(yè)。條件獨(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=5independentnumbers條件分布將聯(lián)合分布的表示空間由指數(shù)級(jí)降到線性。條件概率是處理不確定信息的基礎(chǔ)和最魯棒的形式。第二十一頁(yè)，共九十二頁(yè)。不確定性不確定環(huán)境下的行動(dòng)概率公理使用全概率分布進(jìn)行推理獨(dú)立性貝葉斯法則及其應(yīng)用第二十二頁(yè)，共九十二頁(yè)。貝葉斯法則（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第二十三頁(yè)，共九十二頁(yè)。貝葉斯法則與條件獨(dú)立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第二十四頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)

1貝葉斯網(wǎng)絡(luò)概述

2貝葉斯網(wǎng)絡(luò)的語(yǔ)義

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

4貝葉斯網(wǎng)絡(luò)的近似推理第二十五頁(yè)，共九十二頁(yè)。概率公式條件概率公式乘法公式全概率公式第二十六頁(yè)，共九十二頁(yè)。邊緣化與條件化聯(lián)合概率分布邊緣化（求和消元）P(toothache)=0.108+0.012+0.016+0.064=0.2條件化：第二十七頁(yè)，共九十二頁(yè)。貝葉斯法則由乘法法則P(ab)=P(a|b)P(b)=P(b|a)P(a)

Bayes'rule:

P(a|b)=P(b|a)P(a)/P(b)一般形式：

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

第三十一頁(yè)，共九十二頁(yè)。簡(jiǎn)單例子表示前例中條件獨(dú)立的拓?fù)渚W(wǎng)絡(luò):WeatherisindependentoftheothervariablesToothacheandCatchareconditionallyindependentgivenCavity第三十二頁(yè)，共九十二頁(yè)。貝葉斯網(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)第三十三頁(yè)，共九十二頁(yè)。條件概率表每個(gè)節(jié)點(diǎn)旁的條件概率表(簡(jiǎn)稱CPT)中的值對(duì)應(yīng)一個(gè)條件事件的概率如P(A)=0.94=P(A|Burglary∧Earthquake)；條件事件是父節(jié)點(diǎn)取值的一個(gè)可能組合；每行的概率之和應(yīng)為1(表中只給出了為真的情況，為假的概率應(yīng)為1-p)；一個(gè)具有k個(gè)布爾父節(jié)點(diǎn)的布爾變量的條件概率表中有2k個(gè)獨(dú)立的可指定的概率(注意概率值是獨(dú)立的)；沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)的概率只有1行，為先驗(yàn)概率。

0.700.01

tfP(M)

A第三十四頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)的概率解釋任何完整的概率模型必須具有表示（直接或間接）該領(lǐng)域變量聯(lián)合分布的能力，完全的枚舉需要指數(shù)級(jí)的規(guī)模（相對(duì)于領(lǐng)域變量個(gè)數(shù)）；貝葉斯網(wǎng)絡(luò)提供了這種聯(lián)合概率分布的緊湊表示：分解聯(lián)合分布為幾個(gè)局部分布的乘積：第三十五頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)的概率解釋從公式可以看出，需要的參數(shù)個(gè)數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)呈線性增長(zhǎng)，而聯(lián)合分布的計(jì)算呈指數(shù)增長(zhǎng)。網(wǎng)絡(luò)中變量間獨(dú)立性的指定是實(shí)現(xiàn)緊湊表示的關(guān)鍵。獨(dú)立性在通過(guò)人類專家構(gòu)造貝葉斯網(wǎng)中特別有效。第三十六頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)

1貝葉斯網(wǎng)絡(luò)概述

2貝葉斯網(wǎng)絡(luò)的語(yǔ)義

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

4貝葉斯網(wǎng)絡(luò)的近似推理第三十七頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)的語(yǔ)義貝葉斯網(wǎng)絡(luò)給出了關(guān)于相關(guān)事件的完整描述，通過(guò)計(jì)算全聯(lián)合概率分布求取聯(lián)合分布中的某項(xiàng)是對(duì)每個(gè)變量賦予一個(gè)特定值情況下的合取概率就是條件概率表中適當(dāng)元素的乘積例子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

第三十八頁(yè)，共九十二頁(yè)。一種貝葉斯網(wǎng)絡(luò)構(gòu)建方法乘法規(guī)則：P(x1,x2,…xn)=P(xn|xn-1,…,x1,)P(xn-1,…,x1,)鏈?zhǔn)椒▌t(chainrule)：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)化的特性，即每個(gè)節(jié)點(diǎn)只和數(shù)量有限的其它部分產(chǎn)生直接的相互作用第三十九頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)的構(gòu)造

——防盜網(wǎng)BurglaryEarthquakeMaryCallsJohnCallsAlarmP(m|j,a,b,e)=P(m|a)第四十頁(yè)，共九十二頁(yè)。緊致性與節(jié)點(diǎn)順序貝葉斯網(wǎng)絡(luò)的局部結(jié)構(gòu)化（locallystructed）每個(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個(gè)數(shù)據(jù).比較：n=30,k=5.構(gòu)造貝葉斯網(wǎng)絡(luò)的次序：添加節(jié)點(diǎn)首先從“根本原因”開(kāi)始，然后加入受其直接影響的變量，直到葉節(jié)點(diǎn)(不影響任何其它節(jié)點(diǎn))。

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

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

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

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ú)立的。Burglary第四十九頁(yè)，共九十二頁(yè)。條件分布的有效表達(dá)：noisy-OR貝葉斯網(wǎng)絡(luò)中盡管父節(jié)點(diǎn)個(gè)數(shù)k很小，但是要完成條件概率表仍需要O(2k)數(shù)據(jù)；如果找到了變量依賴的某種關(guān)系，則可以用O(k)個(gè)參數(shù)完成條件概率表—噪聲或(noisy-OR)關(guān)系用于刻畫不確定關(guān)系(邏輯或的推廣)；噪聲或關(guān)系考慮到每個(gè)父節(jié)點(diǎn)引起子節(jié)點(diǎn)為真的能力的不確定性:父節(jié)點(diǎn)條件為真但子節(jié)點(diǎn)的結(jié)果未必為真。

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

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

P(fever|cold,flu,malaria)=0.6 P(fever|cold,flu,malaria)=0.2 P(fever|cold,flu,malaria)=0.1目的：為建立一個(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.988第五十二頁(yè)，共九十二頁(yè)。噪聲或關(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é)點(diǎn)，906邊8254個(gè)數(shù)據(jù)，而不是133,931,430第五十三頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)

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

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

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

4貝葉斯網(wǎng)絡(luò)的近似推理第五十四頁(yè)，共九十二頁(yè)。貝葉斯網(wǎng)絡(luò)中的精確推理基本任務(wù)是計(jì)算被查詢變量的后驗(yàn)概率：設(shè)X為待查詢變量，e為觀察到的證據(jù)，E={E1…Em}證據(jù)變量集合，Y={Y1…Yn}非證據(jù)變量集合(也稱隱變量)全部變量集合={X}∪E∪Y推理的任務(wù)是：求后驗(yàn)概率P(X|e)實(shí)際上，根據(jù)邊緣化規(guī)則可得

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

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

第五十六頁(yè)，共九十二頁(yè)。查詢實(shí)例（2）進(jìn)一步代入條件概率：P(b|j,m)=∑E∑AP(b)P(E)P(A|b,e)P(j|A)P(m|A)上式最壞復(fù)雜度O(n2n)，將相對(duì)常數(shù)移到求和符號(hào)以外：P(b|j,m)=P(b)∑EP(E)∑AP(A|b,E)P(j|A)P(m|A)計(jì)算過(guò)程(遍歷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

第五十七頁(yè)，共九十二頁(yè)。查詢實(shí)例（3）乘積求和過(guò)程：∑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第五十八頁(yè)，共九十二頁(yè)。查詢實(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(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★

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

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

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

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

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

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

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

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

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

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

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

第七十三頁(yè)，共九十二頁(yè)。采樣過(guò)程舉例（1）通過(guò)例子說(shuō)明采樣過(guò)程/算法均省略(1)因?yàn)镻(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（注意：此時(shí)采樣樣本均為<TXXX>形式，其中<TTXX>占10%，<TFXX>占90%）(3)P(rain|cloudy=T)=<0.8,0.2>，故rain的采樣樣本T/F各占80%和20%,應(yīng)該返回T/樣本形式類似于(2)

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

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

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

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

第七十七頁(yè)，共九十二頁(yè)。似然加權(quán)方法（1）只生成與證據(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)的概率采樣過(guò)程如下：(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

第七十八頁(yè)，共九十二頁(yè)。似然加權(quán)方法（2）(4)P(rain|cloudy=T)=<0.80.2>，據(jù)此進(jìn)行采樣，假設(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)方法也得到對(duì)于真實(shí)概率的一致估計(jì)從采樣與加權(quán)的乘積去理解聯(lián)合分布概率的計(jì)算，依然是全部條件概率的乘積.

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

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

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

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

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

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