邏輯推理 _人工智能_課件

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

2、ptom(p,Toothache) Disease(p,Cavity) ?引起牙痛的原因：牙洞？ 窮舉牙洞與牙痛有必然聯(lián)系嗎？失敗的原因：懶惰(laziness): failure to enumerate exceptions, qualifications, etc.無知(ignorance): lack of relevant facts, initial conditions, etc.不確定環(huán)境下的決策根本思想：精確度和有效性的折中理性決策的含義既依賴于各種目標的相對重要性，也依賴于這些目標將被實現(xiàn)的可能性程度。假設A180理性決策，這意味著在給定所處的環(huán)境信息下，它是所有可執(zhí)行的規(guī)

3、劃中智能體的性能度量期望到達最大的那個。性能度量：及時趕上飛機、等待時間不長，不確定環(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 該選哪一個行動?例如，取決于成功的幾率以及等待時間的折中。必須考慮效用理論Utility theory決策論概率論效用論Decision theo

4、ry = probability theory + utility theory先驗概率與命題a相關的無條件概率，在沒有任何其它信息存在的情況下，關于命題的信度，記為：Pa。例如，用Pweather表示天氣的概率：Pweather sunny0.7Pweather rain0.2Pweather cloudy0.08Pweather snow0.02先驗概率分布：Pweather 聯(lián)合概率分布，全聯(lián)合概率分布概率密度函數(shù)后驗條件概率得到與命題a相關的變量的證據(jù)，先驗概率失效，需要以后驗概率替代，記為：Pa|b例如：Pcavity | toothache0.7乘法規(guī)那么：Pa b Pb | a

5、Pa概率公理Axioms of probability對任意命題 A, B:0 P(A) 1P(true) = 1 ， P(false) = 0P(A B) = P(A) + P(B) - P(A B)Kolmogorov公理不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法那么及其應用聯(lián)合概率分布聯(lián)合概率分布joint probability distribution:表中catch是指由于牙醫(yī)的鋼探針不潔而導致的牙齦感染對任何命題 , 其概率是所有原子證據(jù)事件概率的和： P() = : P()聯(lián)合概率分布枚舉Start with the joint probabilit

6、y 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.2Start with the joint probability distribution,Can also compute conditional probabilities:P(cavity | toothache) = P(cavity toothache)P(toothache)= 0.016+0.064 0.10

7、8 + 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 query variable by fixing evidence variables and summing over

8、hidden variables.不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法那么及其應用獨立性IndependenceA 與 B 獨立，當且僅當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 entries reduced to 12 (weather has 4 possible values); for n independent biased

9、 coins, O(2n) O(n)絕對獨立很好但很少見，例如牙科中可能涉及幾百相互關聯(lián)的變量，這時候如何處理？條件獨立Conditional independence有一個牙洞，鉆具感染與牙疼的概率相互獨立：鉆具感染與牙痛在給定牙洞的情況下是條件獨立的conditionally independent P(Toothache, Catch | Cavity) = P(Toothache | Cavity) P(Catch | Cavity)條件獨立推導聯(lián)合分布，將全聯(lián)合分布分解成很多更小的分布:P(Toothache, Catch, Cavity)= P(Toothache, Catch |

10、 Cavity) P(Cavity) 乘法法那么= P(Toothache | Cavity) P(Catch | Cavity) P(Cavity) 條件獨立I.e., 2 + 2 + 1 = 5 independent numbers條件分布將聯(lián)合分布的表示空間由指數(shù)級降到線性。條件概率是處理不確定信息的根底和最魯棒的形式。不確定性不確定環(huán)境下的行動概率公理使用全概率分布進行推理獨立性貝葉斯法那么及其應用貝葉斯法那么Bayes Rule由乘法法那么 P(ab) = P(a | b) P(b) = P(b | a) P(a) Bayes rule: P(a | b) = P(b | a) P

11、(a) / P(b)一般形式： P(Y|X) = P(X|Y) P(Y) / P(X) = P(X|Y) P(Y)例子：用于從病因causal中找到診斷diagnostic結論 :P(Cause|Effect) = P(Effect|Cause) P(Cause) / P(Effect)E.g., 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貝葉斯法那么與條件獨立P(Cavity | toothache catch) = P(toothache catch

12、 | 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 parameters is linear in n貝葉斯網(wǎng)絡 1 貝葉斯網(wǎng)絡概述2 貝葉斯網(wǎng)絡的語義3 貝葉斯網(wǎng)絡中的精確推理4 貝葉斯網(wǎng)絡的近似推理概率公式條件概率公式乘法公式全概率公式邊緣化與條件化聯(lián)合概率分布邊緣化

13、求和消元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)絡的由來隨機方法？每個狀態(tài)值取決于前面有限個狀態(tài) ，如Markov鏈。在現(xiàn)實生活中，很多事物相互的關系并不能用一條鏈來串起來；它們之間的關系可能是交叉的、錯綜復雜的。如疾病的起因，故障的原因等。貝葉斯網(wǎng)絡的由來全聯(lián)合概率計算復雜性十分巨大；變量之間的獨立性和

14、條件獨立性能大大減少為了定義全聯(lián)合概率分布所需的概率數(shù)目。需要一種自然、有效的方式來根據(jù)不確定性知識推理貝葉斯網(wǎng)絡；貝葉斯網(wǎng)絡的定義貝葉斯網(wǎng)絡(Bayesian network)是一個有向圖，其中每個節(jié)點都標注了定量概率信息： 一個隨機變量集合組成網(wǎng)絡節(jié)點，變量可以是離散的或者連續(xù)的； 一個連接節(jié)點對的有向邊或者箭頭的集合，如果存在從節(jié)點X指向節(jié)點Y的有向邊，那么稱X是Y的一個父節(jié)點； 每個節(jié)點都存在一個條件概率分布P(Xi|Parent(Xi)，量化父節(jié)點對該節(jié)點的影響； 圖中不存在有向環(huán)(是有向無環(huán)圖DAG)。 簡單例子表示前例中條件獨立的拓撲網(wǎng)絡:Weather is independe

15、nt of the other variablesToothache and Catch are conditionally independent given Cavity貝葉斯網(wǎng)絡的表示 防盜網(wǎng)BurglaryEarthquakeMaryCallsJohnCallsAlarm0.950.940.290.001 t t t f f t f fP(A) B E0.900.05 t fP(J) A0.700.01 t fP(M) A0.001P(B) 0.002P(E) 條件概率表每個節(jié)點旁的條件概率表(簡稱CPT)中的值對應一個條件事件的概率如P(A)=0.94=P(A|BurglaryEar

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

17、的計算呈指數(shù)增長。網(wǎng)絡中變量間獨立性的指定是實現(xiàn)緊湊表示的關鍵。獨立性在通過人類專家構造貝葉斯網(wǎng)中特別有效。貝葉斯網(wǎng)絡 1 貝葉斯網(wǎng)絡概述2 貝葉斯網(wǎng)絡的語義3 貝葉斯網(wǎng)絡中的精確推理4 貝葉斯網(wǎng)絡的近似推理貝葉斯網(wǎng)絡的語義貝葉斯網(wǎng)絡給出了關于相關事件的完整描述，通過計算全聯(lián)合概率分布求取聯(lián)合分布中的某項是對每個變量賦予一個特定值情況下的合取概率就是條件概率表中適當元素的乘積例子 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)絡構建方法乘法規(guī)那么：P(x1,x2, xn)=P(xn|

18、xn-1 ,x1,) P(xn-1 ,x1 ,) 鏈式法那么(chain rule)：P(Xi|Xi-1,X1)=P(Xi|Parent(Xi)Parent(Xi) Xi-1,X1初始的合取概率化為更小的條件概率和更小的合取式 這些條件概率的合取式實際上就是父節(jié)點到子節(jié)點的概率乘積。父子節(jié)點的關系使得貝葉斯網(wǎng)絡具有局部結構化的特性，即每個節(jié)點只和數(shù)量有限的其它局部產(chǎn)生直接的相互作用貝葉斯網(wǎng)絡的構造 防盜網(wǎng)BurglaryEarthquakeMaryCallsJohnCallsAlarmP(m | j, a, b, e) =P(m | a)緊致性與節(jié)點順序貝葉斯網(wǎng)絡的局部結構化locally s

19、tructed每個隨機變量可以至多受到k個其它隨機變量的影響(k=常數(shù))；設網(wǎng)絡中有n個節(jié)點(隨機變量)，指定每個條件概率表所需信息量至多為2k個數(shù)據(jù)，那么整個網(wǎng)絡可以用n2k個數(shù)據(jù)完全描述/而全聯(lián)合概率分布需要2n個數(shù)據(jù).比較：n=30, k=5.構造貝葉斯網(wǎng)絡的次序：添加節(jié)點首先從“根本原因開始，然后參加受其直接影響的變量，直到葉節(jié)點(不影響任何其它節(jié)點)。 Suppose we choose the ordering M, J, A, B, EP(J | M) = P(J)?ExampleSuppose we choose the ordering M, J, A, B, EP(J |

20、M) = P(J)?NoP(A | J, M) = P(A | J)? P(A | J, M) = P(A)?ExampleSuppose 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)? NoP(B | A, J, M) = P(B | A)? P(B | A, J, M) = P(B)?ExampleSuppose we choose the ordering M, J, A, B, EP(B | A, J, M) = P(B | A)? Yes

21、 (JohnCalls and MaryCalls increase the chance of alarm.)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)?ExampleSuppose 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,

22、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)? NoExampleExample contd.Network is less compact: 1 + 2 + 4 + 2 + 4 = 13 numbers neededDeciding conditional independence is hard in noncausal directions(Causal models an

23、d conditional independence seem hardwired for humans!)條件獨立關系貝葉斯網(wǎng)絡中節(jié)點相互獨立(下面兩個定義等價)：(1)給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的 ；(2)給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點(Markov blanket)，這個節(jié)點對于其它節(jié)點都是條件獨立的。圖示，例子 條件獨立關系圖示 U1UmXZ1jZnjY1YnU1UmXZ1jZnjY1Yn給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的JohnCall給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點，這個節(jié)點對于其它節(jié)點都是條件獨立的。Burglary

24、條件分布的有效表達：noisy-OR貝葉斯網(wǎng)絡中盡管父節(jié)點個數(shù)k很小，但是要完成條件概率表仍需要O(2k)數(shù)據(jù)；如果找到了變量依賴的某種關系，那么可以用O(k)個參數(shù)完成條件概率表噪聲或(noisy-OR)關系用于刻畫不確定關系(邏輯或的推廣)；噪聲或關系考慮到每個父節(jié)點引起子節(jié)點為真的能力的不確定性: 父節(jié)點條件為真但子節(jié)點的結果未必為真。 噪聲或關系1例子：發(fā)燒(fever)為真，當且僅當以下三者之一為真：感冒(cold)/流感(flu)/瘧疾(malaria)但是可能病人得了以上疾病卻沒有發(fā)燒病癥這就是父節(jié)點為真其子節(jié)點未必真的不確定性即父子關系被抑制此時可以認為：fever為假當且僅當

25、所有為真的父節(jié)點被抑制，其概率為每個父節(jié)點被抑制的概率的乘積兩條假設所有原因已經(jīng)列出每個父節(jié)點的抑制獨立于其他父節(jié)點的抑制 噪聲或關系2假設每個單獨抑制的概率如下 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)=0.2*0.1=0.02 P(fever|cold,flu,malaria)=0.6*0.2*0.1=0.012 P(fever|cold,flu,mal

26、aria)=1-0.012=0.988噪聲或關系3Cold 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=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é)點，906邊8254個數(shù)據(jù)，而不是133,931,430貝葉斯網(wǎng)絡 1 貝葉斯概率根底2 貝葉斯網(wǎng)絡

27、的表示3 貝葉斯網(wǎng)絡中的精確推理4 貝葉斯網(wǎng)絡的近似推理貝葉斯網(wǎng)絡中的精確推理根本任務是計算被查詢變量的后驗概率：設X為待查詢變量，e為觀察到的證據(jù)，E=E1Em證據(jù)變量集合，Y=Y1Yn非證據(jù)變量集合(也稱隱變量)全部變量集合=XEY推理的任務是：求后驗概率P(X|e)實際上，根據(jù)邊緣化規(guī)那么可得 P(X|e)=P(X,e)=yP(X,e,y) 查詢實例1答復查詢：在貝葉斯網(wǎng)絡中計算條件概率的乘積并求和。以防盜警報為例，求P(B|J=T,M=F)證據(jù)JohnCalls=True/MaryCalls=False查詢變量Burglary=True隱含變量Earthquake/Alarm用首字母簡

28、化式有：P(b|j,m)=P(b,j,m) =EAP(b,E,A,j,m) 查詢實例2進一步代入條件概率：P(b|j,m)=EAP(b)P(E)P(A|b,e)P(j|A)P(m|A)上式最壞復雜度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.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 查詢實例3乘積求和過程：EP(E)AP(A|b

29、,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.259

30、0+0.998*0.2568=0.2568查詢實例4相應地有：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)=只有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)重復計算了兩次，如何

31、消除重復？只要保存一次計算結果既可。按照從右到左的次序計算。例子： 例子：對M和J，用二元向量表示保存每個給定的a下的概率：A的因子P( a | B, e)是一個 2 x 2 x 2 的矩陣f A (A, B, E).首先對A求和消去，得到一個只有B和E的2 x 2 的矩陣：A上加一橫表示已經(jīng)通過求和消去。使用乘法的過程稱為點積(pointwise product)例子：對E求和消去：最后，可以簡單的將B的因子與上述累積矩陣相乘來計算答案：點積pointwise product變量消元法2在這樣的計算中只要做：計算兩個因子的點積在因子乘積中對一個變量求和消元在計算中，消除以下無關節(jié)點：刪除不是

32、查詢變量也非證據(jù)變量的葉節(jié)點刪除所有不是查詢變量，祖先也不是證據(jù)變量的節(jié)點P(JohnCalls l Burglary = true).精確推理的復雜度單連通結構貝葉斯網(wǎng)絡中任何兩個節(jié)點都至多只有一條無向路徑相連；此時，單連通上的精確推理的時間和空間復雜度都和網(wǎng)絡規(guī)模呈線性關系；而對于多連通結構(見以下圖)，最壞情況下變量消元法可能具有指數(shù)級的時空復雜度此時貝葉斯網(wǎng)絡的推理是一個NP問題；所以要尋找多連通網(wǎng)絡中的近似算法。 多連通網(wǎng)絡 S R P(W)T T .99T F .90F T .90F F .00C P(R)T .80F .20sprinklerRainWet grassC P(S)

33、T .10F .50P(C)=.5cloudy貝葉斯網(wǎng)絡 1 貝葉斯概率根底2 貝葉斯網(wǎng)絡的表示3 貝葉斯網(wǎng)絡中的精確推理4 貝葉斯網(wǎng)絡的近似推理貝葉斯網(wǎng)絡的近似推理大規(guī)模多連通網(wǎng)絡的精確推理是不可操作的，所以要考慮近似的推理方法.采用隨機采樣方法，也稱蒙特卡羅算法(Monte Carlo algorithm)：給出近似解答，近似的精度依賴于所生成采樣點的多少。例如：求積分。此處近似的含義：不是通過計算求出網(wǎng)絡中某個點的條件概率(因為復雜度高)，而是對該事件進行采樣而獲得概率 后驗概率計算的采樣方法有兩類采樣方法直接采樣方法：計算樣本的頻率馬爾科夫鏈采樣方法：根據(jù)馬爾科夫覆蓋中的變量當前值來采

34、樣直接采樣方法依據(jù)概率來生成樣本拒絕采樣算法 / 似然加權算法馬爾科夫鏈采樣方法證據(jù)變量概率固定條件下隨機生成樣本 采樣方法的要素任何采樣算法中最根本的要素是根據(jù)概率分布生成樣本。例如：一個無偏差的硬幣是一個隨機變量Coin，其可能取值為.先驗概率是P(Coin)=.直接采樣方法直接采樣方法是按照拓撲結構次序依次對每個變量進行采樣，被采樣變量值的概率分布依賴于父節(jié)點已取得的賦值。具體實現(xiàn)： 采樣樣本與概率分布樣本的向量表示cloudy, sprinkler, rain, wetGrass F/T或者0/1表示為假或為真 / 如T, F, T, T采樣按照概率分布進行，但不是等于這個概率分布值，

35、而是說分布與之相符cloudy=0.5,0.5 / 第1次采樣49/51，第2次采樣52/48如此等等每次采樣應該在一定的條件下(這就是條件概率)進行，不滿足條件的樣本不再考慮 采樣過程舉例1通過例子說明采樣過程 / 算法均省略(1)因為P(cloudy)=, 故cloudy的采樣樣本T/F各占50%，假設(不妨)返回T(2)P(sprinkler|cloudy=T)=，故sprinkler的采樣樣本T/F各占10%和90%，應該返回F注意：此時采樣樣本均為形式，其中占10%，占90%(3)P(rain|cloudy=T)=，故rain的采樣樣本T/F各占80%和20%, 應該返回T / 樣本

36、形式類似于(2) 采樣過程舉例2(4)P(wetGrass|sprinkler=F, rain=T)=，那么返回T / 采樣樣本形式占90%，占10%實際上如此生成的樣本完全符合先驗概率，即對于上例，cloudy sprinkler rain wetGrass =T F T T=0.5*0.9*0.8*0.9=0.324 拒絕采樣方法從分布的采樣出發(fā)(其計算如上)，通過去掉不滿足證據(jù)條件的樣本來計算(估計)那些未知分布的事件的概率例子：P(Rain|Sprinkler=T)未知其概率 采樣100個樣本：其中73個為，不滿足前提條件余下的27個中8個為rain=T / 19個為rain=FP(R

37、ain|Sprinkler=T)=拒絕采樣方法的最大問題就是效率比較低(相當一局部樣本被拒絕了) 一致的估計拒絕采樣方法能產(chǎn)生真實概率的一致估計估計的概率在無限多(大量樣本的極限)條件下成為精確值，這樣的估計稱為一致的(consistent)，即 似然加權方法1只生成與證據(jù)e一致的事件，防止拒絕采樣的低效率。對證據(jù)節(jié)點的概率進行似然加權，即按照先驗概率的乘積進行計算 / 對非證據(jù)節(jié)點進行采樣，采樣樣本服從先驗概率分布例子：求P(rain| sprinkler=T, wetGrass=T)的概率采樣過程如下：(1)權值w=1.0(2)P(cloudy)=，據(jù)此采樣，返回T(3)Sprinkler

38、是證據(jù)變量，取值T，那么ww*P(sprinkler=T|cloudy=T)=1.0*0.1=0.1 似然加權方法2(4)P(rain|cloudy=T)=，據(jù)此進行采樣，假設=T(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的概率很低似然加權方法也得到對于真實概率的一致估計從采樣與加權的乘積去理解聯(lián)合分布概率的計算，依然是全

39、部條件概率的乘積. 小權值的樣本占到大多數(shù)馬爾科夫鏈采樣1直接采樣法按照先驗概率去采樣馬爾科夫鏈采樣對證據(jù)變量以外的變量每次隨機地采樣舉例：考慮求P(rain | sprinkler=T,wetGrass=T)證據(jù)變量固定：sprinkler=T/wetGrass=T隱變量cloudy/rain那么隨機采樣：初始值不妨假設cloudy=T/rain=F初始狀態(tài)= 證據(jù)變量固定下，狀態(tài)空間內的隨機走動馬爾科夫鏈采樣2然后反復按照以下2個步驟采樣(1)當前條件下對cloudy隨機采樣，結果=(2)當前條件下對rain隨機采樣，結果=最后得到假設干樣本，例如rain=T=20 / rain=F=60

40、，那么P(rain|sprinkler=T,wetGrass=T)= = 馬爾科夫鏈采樣的合理性1馬爾科夫鏈采樣過程最終會進入“動態(tài)平衡狀態(tài)被采樣變量服從馬爾科夫覆蓋下的條件概率分布，且“穩(wěn)態(tài)分布=真實后驗概率P(x|e)我們所需要求解的正是給定證據(jù)變量e下某個變量的概率值P(x|e)證明過程：轉移概率狀態(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)：當t+1(x)=t(x)時，馬爾科夫鏈到達穩(wěn)態(tài)分布，即(省略t) (x)=x(x)q(xx)對于

41、所有x細致平衡任意兩個狀態(tài)間沿兩個方向轉換概率相等 (x)q(xx)=(x)q(xx)對于所有x, x簡單公式推導(求和)可證明細致平衡中蘊含著穩(wěn)態(tài)分布 幾點總結貝葉斯網(wǎng)絡的特點：雙向推理能力預測和診斷快速的調試和重構能力具有較強的概率統(tǒng)計根底用于人工智能和專家系統(tǒng)的不確定推理優(yōu)于早期的基于規(guī)那么的模式。這種網(wǎng)絡支持任何變量子集相對于另一子集的條件概率計算。貝葉斯網(wǎng)絡是域中變量關系的直接表示，而不是推理過程。網(wǎng)絡中的方向表示變量間真正的因果關系而不是推理過程的信息流向。 因此在貝葉斯推理過程中，推理過程可以沿任何方向進行預測、診斷、解釋。BN定性描述貝葉斯網(wǎng)絡中每個圓圈表示一個狀態(tài)。狀態(tài)之間的

42、連線表示它們的因果關系。和馬爾可夫鏈類似，貝葉斯網(wǎng)絡中的每個狀態(tài)值取決于前面有限個狀態(tài)。不同的是，貝葉斯網(wǎng)絡比馬爾可夫鏈靈活，它不受馬爾可夫鏈的鏈狀結構的約束，因此可以更準確地描述事件之間的相關性。可以講，馬爾可夫鏈是貝葉斯網(wǎng)絡的特例，而貝葉斯網(wǎng)絡是馬爾可夫鏈的推廣。 開展歷史1貝葉斯Reverend Thomas Bayes 1702-1761學派奠基性的工作是貝葉斯的論文“關于幾率性問題求解的評論。著名的數(shù)學家拉普拉斯Laplace P. S. 1749-1827用貝葉斯的方法導出了重要的“相繼律，貝葉斯的方法和理論逐漸被人理解和重視起來。但由于當時貝葉斯方法在理論和實際應用中還存在很多不完善的地方，因而在十九世紀并未被普遍接受。開展歷史2二十世紀初，意大利的菲納特B. de Finetti以及英國的杰弗萊Jeffreys H.都對貝葉斯學派的理論作出重要的奉獻。第二次世界大戰(zhàn)后，瓦爾德Wald A.提出了統(tǒng)計的決策理論，在這一理論中，貝葉斯解占有重要的地位；信息論的開展也對貝葉斯學派做出了新的奉獻。1958年英國最悠久的統(tǒng)計雜志Biometrika全文重新刊登了貝葉斯的論文，20世紀50年代，以羅賓斯Rob