馬爾可夫網絡

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

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

形式化定義

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

• 一個無向圖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問題，一般相信不存在快速計算方法。近似推理技術如馬爾科夫蒙特卡洛和置信度傳播通常更加可行。一些馬爾可夫隨機場的子類，如樹，有多項式時間複雜度的推理算法，發現這樣的子類也是活躍的研究課題。也有一些馬爾可夫隨機場的子類允許有效最大後驗概率估計，或者最可能的指派值；應用的例子包括關聯網絡。

條件隨機場

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

參見

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