馬爾可夫網絡

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

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

形式化定義

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

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

聯合分佈函數

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

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

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

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

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

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

和

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

以及劃分函數

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

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

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

馬爾可夫性質

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

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

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

推理

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

條件隨機場

一個馬爾可夫網絡的重要變體是條件隨機場，每個隨機變量可以條件依賴於一組全局的觀察${\displaystyle o}$。這個模型中，每個函數${\displaystyle \phi _{k}}$是從指派值到團k和從觀察${\displaystyle o}$到非負實數的映射。這樣的馬爾可夫網絡更適於不對觀察建立分佈模型的區分性模型，不是生成性模型。

參見

• 圖模式
• 馬爾可夫鏈
• 馬爾可夫邏輯網絡

參考

1. Ross Kindermann and J. Laurie Snell, 馬爾可夫隨機場及其應用 （頁面存檔備份，存於互聯網檔案館）（1980）美國數學協會, ISBN 0-8218-5001-6