目錄
-
-
- Variable Elimination(VE) 消元法
-
- VE in complex graphs
- Exact Inference: Clique Tree
-
- Cluster graph and clique tree
- Message passing: Sum Product
- Clique Tree Calibration
- Message passing: Belief Update
- Constructing clique tree
-
Variable Elimination(VE) 消元法
線性鍊上的消元：
按照 A、B、C、D 的順序依次消去
VE in complex graphs
induced graph in VE
step 1: Moralizing for BN （即在 v-structure 的兩個父親節點連邊）
step 2: Triangulation （即在消元過程中做三角化操作）
最後出來會是 chordal，即是一個弦圖，圖中隻有三角，沒有四邊形
如果每次 inference 的時候都要周遊整個圖，那就太蠢了，這裡可以采用動态規劃的算法，消元時候的中間結果是可以拿來重用的。
提前計算好定義在每個 clique 上的 marginal distribution，在做 inference 時候也能快很多。
Exact Inference: Clique Tree
Cluster graph and clique tree
clique tree 是定義在弦圖上的，根據 clique 生成的樹狀結構。
clique tree 有兩個非常重要的性質：
- tree and family preserving: 原來的 induced graph 轉化為 clique tree 後具有樹狀結構，而且和原來的結構是可以互相轉換的。clique tree 的每一個節點是代表一個 clique，邊上是兩個 clique 間重疊的部分。
- running intersection property：是指變量 X 存在一條連續的樹的子路徑上。如 G 出現在了 Clique2和 clique4中，那麼中間的 clique3和 clique5
機率圖學習——Inference as Optimization: Cluster Graph & Belief Propagation 聚類圖，置信傳播 每個 clique 都是有他們對應的 local CPD 機率圖學習——Inference as Optimization: Cluster Graph & Belief Propagation 聚類圖，置信傳播 機率圖學習——Inference as Optimization: Cluster Graph & Belief Propagation 聚類圖，置信傳播
Message passing: Sum Product
順序1：
順序2：
Clique Tree Calibration
calibration（校準）：使得兩個相鄰 clique 之間傳送的消息相等。