轉自http://cid-2d7821b3af3c6073.spaces.live.com/blog/cns!2D7821B3AF3C6073!155.entry

概率圖模型之有向圖與無向圖

圖模型用圖結構描述隨機變量之間的依賴關系,結點表示隨機變量,邊表示隨機變量之間的依賴關系,可以是有向圖和無向圖。

一 無向圖模型

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

1 無向圖模型的表示

給定包含n個隨機變量的問題域clip_image002,則定義在問題域U上的無向圖模型包括拓撲結構和參數兩部分:

Ø 拓撲結構S:節點表示隨機變量,兩節點之間的連線表示它們之間具有直接的相互影響。

Ø 參數Θ:無向圖模型參數是對節點之間相互影響的定量描述。它是拓撲結構S中每個極大完全子圖所對應的勢函數的集合。其中,極大完全子圖(clique)是指不包含于其它完全子圖的完全子圖(完全子圖中任何兩節點是直接相連的),勢函數clip_image004則反映了極大完全子圖clip_image006的每種可能狀態的能量。

2 無向圖模型的聯合概率分解

利用無向圖模型可將圖的聯合概率分解為一系列因子式。給定無向圖模型拓撲結構S和參數Θ之后,問題域U上的聯合概率密度函數可寫為:

clip_image008

其中N為無向圖中極大完全子圖的數目。

3 例子:

clip_image010

clip_image012

clip_image014

二 有向圖模型

clip_image016

1 一個簡單的例子

clip_image018

2 一般情況

clip_image020考慮任意聯合分布 ,通過連續使用乘法規則



clip_image022

利用局部馬爾可夫性簡化簡化:在給定其所有父親節點的情況下,隨機變量X與其非后繼條件獨立。

clip_image024

其中pai是Xi的父節點集合。

三 有向圖模型與無向圖模型的對比:

1 共同之處

將復雜的聯合分布分解為多個因子的乘積

2 不同之處

有向圖模型因子是概率分布、無需全局歸一

無向圖模型因子是勢函數,需要全局歸一

3 優缺點

無向圖模型中勢函數設計不受概率分布約束,

設計靈活,但全局歸一代價高

有向圖模型無需全局歸一、訓練相對高效