馬爾可夫網絡

馬爾可夫網絡,(馬爾可夫隨機場無向圖模型)是關於一組有馬爾可夫性質隨機變量的全聯合概率分布模型。

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

形式化定義

形式上,一個馬爾可夫網絡包括:

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

聯合分布函數

聯合分布(吉布斯測度)用馬爾可夫網絡可以表示為:

 

其中 是向量, 是隨機變量 在第k個團的狀態( 是在第k個團中包含的節點數。),乘積包括了圖中的所有團。注意馬爾可夫性質在團內的節點存在,在團之間是不存在依賴關係的。這裡, 配分函數,有

 .

實際上,馬爾可夫網聯絡經常表示為對數線性模型。通過引入特徵函數 ,得到

 

 

以及劃分函數

 

其中, 是權重, 是勢函數,映射團 到實數。這些函數有時亦稱為吉布斯勢;術語源於物理,通常從字面上理解為在臨近位置產生的勢能

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

馬爾可夫性質

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

 

頂點u的最近臨節點集合 也稱為頂點u馬爾可夫鏈

推理

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

條件隨機場

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

參見

參考

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