機率圖模型筆記(8)——Inference Variable Elimination

8.1 Overview-Conditional Probability Queries

8.1.1 Conditional Probability Queries

　　定義如下三個内容:

　　(1)證據： E=e

　　(2)問題：變量集 Y

　　(3)任務：計算P(Y|E=e)

8.1.2 和-積

　　除了問題變量所在的因子，在每個因子上輪流取不同的值并将各個因子做乘積，不同的取值的因子積之和為問題變量的聯合分布 P ，如果不進行歸一化則記為P~。

8.1.3 證據：減少因子

　　對于給定了證據的計算任務 P(Y|E=e) ，其計算方法和8.1.2小結的方法基本類似，不同在于需要在因子中劃去 E=e 以外的分布。

　　需要注意到的是，可以先計算 P(y,e)=∑wP(y,e,w) ，然後利用 P(e)=∑yP(y,e) 來進行計算，并在最後重新進行歸一化。其中 w 是變量中除了y和 e 以外的變量集。

8.1.4 條件機率的算法

　　(1)Push summations into factor product

　　例如變量消除法，它是精确推理的一種，同時也被稱為動态工程。

　　(2)message passing over a graph

　　例如信念傳播，變分近似。

　　(3)Random sampling instantiations

　　例如MCMC以及重要性抽樣。

8.2 Overview-MAP Inference

8.2.1 定義

　　(1)證據：E=e。

　　(2)問題：除 E 以外的其他變量Y。

　　(3)任務：計算 MAP(Y│E=e)=argmaxyP(Y=y|E=e)

　　需要注意的是，可能有多個解存在。

　　應用：資訊編碼，即最有可能傳播的資訊；圖像分割，最有可能的分割情況。

8.2.2 MAP不是邊緣機率的最大值

8.2.3 計算方法

　　其本質上是個優化問題，即：

P(Y│E=e)=P(Y,E=e)P(E=e)∝P(Y,E=e)=1Z∏kφk(Dk)∝∏kφk(Dk)

在上式中， φk(Dk) 是除 E 以外的因子，而因為P(E=e)、 Z 獨立于Y，是以可以省略并寫作正比形式。

8.2.4 算法

　　(1)Push maximization into factor product

　　例如變量消除。

　　(2)Message passing over a graph

　　例如最大乘積信念傳播。

　　(3)Using methods for integer programming

　　(4)對于一些特殊的網絡:graph-cut methods

　　(5)Combinatorial search

8.3 Variable Elimination Algorithm

8.3.1 Elimination in Chains

　　對于一個無向鍊A-B-C-D-E，我們有如下變量消除法則：

P(E)∝∑D∑C∑B∑Aφ(A,B)φ(B,C)φ(C,D)φ(D,E)

=∑D∑C∑Bφ(B,C)φ(C,D)φ(D,E)∑Aφ(A,B)

=∑D∑C∑Bφ(B,C)φ(C,D)φ(D,E)τ1(B)

當需要消除變量B時需包含 φ(B,C) 與 τ1(B) ，并最後定義累加結果為 τ2(C) ，視為與自變量為 C 的函數，依次類推。

8.3.2 Variable Elimination

　　對于有向的貝葉斯網絡來說，每個節點聯合其父節點為一個因子，當對某一變量進行消除時，把與該變量有關的因子放到對應的連加符号右邊，其他的變量與連加符号放到該連加符号左邊。将所需消除的連加符号以及連加符号右邊的式子，寫成以右邊因子中所存在的所有變量為自變量的函數τ。

　　注意，該步驟之後所有因式的轄域中均不存在被消除的變量。

　　馬爾可夫網的變量消除法與上述方法相同。

8.3.3 Variable Elimination with evidence

　　先對于給定的證據變量進行如8.1節所示的因式縮減，然後根據8.3.2的方法進行變量消除。最後歸一化。

8.3.4 總結

　　變量消除算法步驟如下：

　　(1)根據所有的證據進行因式縮減(reduce)

　　(2)對于需要消除的變量 Z ，把所有含有Z的變量放到 Z 的連加右邊，并連同連加符号換成一個因式τ。

　　(3)把得到的 τ 和剩下的因式乘起來。

　　(4)重新歸一化得到分布。

8.4 Complexity Analysis

8.4.1 單次消除乘積次數

　　對于第k次變量消除ψk(Xk)=∑mki=1φi，其進行乘積算法的次數不高于因子的個數 mk 減一乘以最後所得因子的行數 Nk ： (mk−1)Nk 。

　　例如有3個因子，隻需兩次自然連接配接乘積即可得到最後的結果，每次自然連接配接乘積的乘積次數不會高于最後得到的因子的行數。

8.4.2 單次消除加法次數

　　對每個因子做乘積之後需求本次消除的因子的邊緣分布，即把乘積所得分布的行中的相同消除因子的值加起來。由于分布中每行隻會被加一次，是以加法次數不會高于分布中的行數。即 Nk 。

8.4.3 總時間複雜度

　　(1)消除次數 m 必然小于或等于變量個數n；

　　(2)最開始的初始因子數(a)對于貝葉斯網絡來說必然小于變量個數n;(b)對于馬爾可夫網來說可能會大一些，最多的情況是馬爾可夫網是完全圖；

　　(3)每一次變量消除生成1個新因子，并假設因子的最大數量是 m∗ 。

　　(4)令 N=max(Nk)

　　那麼我們有如下結論：

　　(1)乘法操作的次數為： ∑k(mk−1)Nk≤N∑k(mk−1)≤Nm∗

　　(2)加法操作的次數為： ∑kNk=Nm≤Nn

　　我們可以看到，變量消除法的複雜度線性于 N 、n和 m∗ 。但是我們可以看到， Nk=O(drk) ， d 是變量個數，變量k有 rk 種取值。是以其時間複雜度是指數級的。

8.4.4 時間複雜度與選擇消除的變量順序有非常大的關系。

8.5 Graph-Based Perspective

8.5.1 貝葉斯網轉馬爾可夫網： 将有向圖轉化為無向圖後(參見6.5)，每當消除一個變量時，依舊存在的與被消除變量有連接配接的邊之間發生新的邊，因為當新的因子生成的時候它們都是該因子的轄域。

8.5.2 導出圖(Induced Graph)

　　定義 IΦ,α 為給定因子集 Φ 以及消除順序α的導出圖，可以發現，消除順序 α 所新生成的因子的轄域與生成該因子所消除的變量的集合在導出圖中構成了派别(clique)。

8.5.3 導出圖的寬度

　　即該導出圖中最大派别的節點個數減1，對應整個消除變量過程中最大的因子相乘次數(即mk−1)。

8.6 Finding Elimination Orderings

　　由于最優的算法是NP難問題，是以可以采用貪心算法來減少計算量，而一般有如下的損失函數：

　　(1)最小鄰居：其在目前圖中擁有的近鄰的數目。

　　(2)最小權重：其及其近鄰的權重(即可選的值的數目)的乘積，例如有轄域是兩個可取100種值的變量以及五個有2個取值的變量，那麼後者的權重乘積明顯較小。

　　(3)最小填充：由于消除這個頂點而需要新增邊的數目。

　　(4)權重最小填充：由于消除這個丁點而需要新增邊的權重和。

　　值得注意的是，由于導出圖是由多個完全圖拼接而成，即每個點都一定隸屬于一個派别裡，是以其實以上算法的目的都在于找出一個導出圖寬度最小的三角劃分方式。