馬爾可夫網絡

馬爾可夫網絡，（馬爾可夫隨機場、無向圖模型）是關於一組有馬爾可夫性質隨機變量 $X$ 的全聯合概率分佈模型。

馬爾可夫網絡類似貝葉斯網絡用於表示依賴關係。但是，一方面它可以表示貝葉斯網絡無法表示的一些依賴關係，如循環依賴；另一方面，它不能表示貝葉斯網絡能夠表示的某些關係，如推導關係。馬爾可夫網絡的原型是易辛模型，最初是用來說明該模型的基本假設^[1]。

形式化定義[編輯]

形式上，一個馬爾可夫網絡包括：

一個無向圖G = (V,E)，每個頂點v ∈V表示一個在集合 $X$ 的隨機變量，每條邊{u,v} ∈ E表示隨機變量u和v之間的一種依賴關係。
一個函數集合 $f_{k}$ （也稱為因子或者團因子有時也稱為特徵），每一個 $f_{k}$ 的定義域是圖G的團或子團k. 每一個 $f_{k}$ 是從可能的特定聯合的指派（到元素k）到非負實數的映射。

聯合分佈函數[編輯]

聯合分佈（吉布斯測度）用馬爾可夫網絡可以表示為：

P(X=x)={\frac {1}{Z}}\prod _{k}f_{k}(x_{\{k\}})

其中 $x=x_{\{1\}}x_{\{2\}}x_{\{3\}}\cdots$ 是向量， $x_{\{k\}}=x_{\{k,1\}}x_{\{k,2\}}\cdots x_{\{k,|c_{k}|\}}$ 是隨機變量 $x$ 在第k個團的狀態（ $|c_{k}|$ 是在第k個團中包含的節點數。），乘積包括了圖中的所有團。注意馬爾可夫性質在團內的節點存在，在團之間是不存在依賴關係的。這裏， $Z$ 是配分函數，有

Z=\sum _{x\in {\mathcal {X}}}\prod _{k}f_{k}(x_{\{k\}})

.

實際上，馬爾可夫網聯絡經常表示為對數線性模型。通過引入特徵函數 $\phi _{k}$ ，得到

f_{k}=\exp \left(w_{k}^{\top }\phi _{k}(x_{\{k\}})\right)

和

P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }\phi _{k}(x_{\{k\}})\right)

以及劃分函數

Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }\phi _{k}(x_{\{k\}})\right)

。

其中， $w_{k}$ 是權重， $\phi _{k}$ 是勢函數，映射團 $k$ 到實數。這些函數有時亦稱為吉布斯勢；術語勢源於物理，通常從字面上理解為在臨近位置產生的勢能。

對數線性模型是對勢能的一種便捷的解釋方式。一個這樣的模型可以簡約的表示很多分佈，特別是在領域很大的時候。另一方面，負的似然函數是凸函數也帶來便利。但是即便對數線性的馬爾可夫網絡似然函數是凸函數，計算似然函數的梯度仍舊需要模型推理，而這樣的推理通常是難以計算的。

馬爾可夫性質[編輯]

馬爾可夫網絡有這樣的馬爾可夫性質：圖的頂點u在狀態 $x_{u}$ 的概率只依賴頂點u的最近臨節點，並且頂點u對圖中的其他任何節點是條件獨立的。該性質表示為

P(X_{u}=x_{u}|X_{v},v\neq u)=P(X_{u}=x_{u}|X_{v},v\in N_{u})

頂點u的最近臨節點集合 $N_{u}$ 也稱為頂點u的馬爾可夫鏈。

推理[編輯]

在貝葉斯網絡中，計算節點 $V'=\{v_{1},...,v_{i}\}$ 集合對給出的另外節點 $W'=\{w_{1},...,w_{j}\}$ 集合的條件分佈可以通過的所有可能的 $u\notin V',W'$ 指派值求和，這是精確推理。精確推理是NP-hard問題，一般相信不存在快速計算方法。近似推理技術如馬爾科夫蒙特卡洛和置信度傳播通常更加可行。一些馬爾可夫隨機場的子類，如樹，有多項式時間複雜度的推理算法，發現這樣的子類也是活躍的研究課題。也有一些馬爾可夫隨機場的子類允許有效最大後驗概率估計，或者最可能的指派值；應用的例子包括關聯網絡。