跳至內容

馬爾可夫網絡

維基百科,自由的百科全書

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

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