貝葉斯網(wǎng)絡初步(更新版)
【正文】 t f f A P(J) t f A P(M) t f P(B) P(E) 貝葉斯網(wǎng)絡的語義 ?貝葉斯網(wǎng)絡的兩種含義 ?對聯(lián)合概率分布的表示 — 構造網(wǎng)絡 ?對條件依賴性語句集合的編碼 — 設計推理過程 ?貝葉斯網(wǎng)絡的語義 P(x1,..., xn) = P(x1|parent(x1)) ... P(xn|parent(xn)) 貝葉斯網(wǎng)絡的語義公式計算示例： ?試計算：報警器響了，但既沒有盜賊闖入，也沒有發(fā)生地震，同時 John和 Mary都給你打電話的概率。 Example: TreeStructured Bayesian Network D A B C F E G p(a, b, c, d, e, f, g) is modeled as p(a|b)p(c|b)p(f|e)p(g|e)p(b|d)p(e|d)p(d) Example D A B c F E g Say we want to pute p(a | c, g) Example D A B c F E g Direct calculation: p(a|c,g) = Sbdef p(a,b,d,e,f | c,g) Complexity of the sum is O(m4) Example D A B c F E g Reordering: Sd p(a|b) Sd p(b|d,c) Se p(d|e) Sf p(e,f |g) Example D A B c F E g Reordering: Sb p(a|b) Sd p(b|d,c) Se p(d|e) Sf p(e,f |g) p(e|g) Example D A B c F E g Reordering: Sb p(a|b) Sd p(b|d,c) Se p(d|e) p(e|g) p(d|g) Example D A B c F E g Reordering: Sb p(a|b) Sd p(b|d,c) p(d|g) p(b|c,g) Example D A B c F E g Reordering: Sb p(a|b) p(b|c,g) p(a|c,g) Complexity is O(m), pared to O(m4) （ 2）變量消元算法 ? 消除重復計算，提高枚舉算法的效率 ? 保存中間結果，以備多次使用 ? 從右到左（在樹結構中為自底向上）的次序計算 BN的計算公式 ? 算法過程：參見 《 人工智能：一種現(xiàn)代方法 》中的第 14章 （ 3） Clustering算法（ Joint Tree算法） ? 單獨節(jié)點聯(lián)合起來形成 Cluster節(jié)點，使得 BN結構成為一棵 多樹 （ Polytree） ? 多樹 —— 單連通網(wǎng)絡 ，即任何兩節(jié)點間至多只有一條路徑相連 ? 概率推理包含命題邏輯推理作為其特殊情況，故 BN的推理是一個 NP問題 ? 在多連通的 BN結構中，及時每個節(jié)點的父節(jié)點個數(shù)有固定的界限，在最壞的情況下，變量消元算法仍可能具有指數(shù)級時間和空間復雜度 多連通網(wǎng)絡及其 CPT： Cloudy Rain Wet Grass Sprinkler S R P(W) t t t f f t f f C P(S) t f P(C) C P(R) t f 等價的聯(lián)合樹及其 CPT： Cloudy Spr+Rain Wet Grass S + R P(W) t t t f f t f f P(C) 貝葉斯網(wǎng)絡的近似推理 ?大規(guī)模多連通 BN的精確推理是不可操作的， 必須通過近似推理來解決。故新的當前狀態(tài)為： [C=false, S=true, R=true, W=true] 【 注 】 ： 上述過程中所訪問的每一個狀態(tài)都是一個樣本 ，能對查詢變量 Rain的估計有貢
教學課件相關推薦
鄂ICP備17016276號-1