天天看點

PGM——從有向圖到無向圖的轉化(moralization)

在解決實際問題的過程中我們經常需要将有向圖(directed graph)轉化成一個與之對應的無向圖(undirected graph),但是相同結構的有向圖和無向圖能夠表達的變量間的獨立性是不同的,如何将一個有向圖轉化成一個無向圖,這個無向圖最大化的表達了原來的資訊,又盡量少地丢失有向圖裡包含的條件獨立性呢? 首先從一個straightforward的例子說起:

PGM——從有向圖到無向圖的轉化(moralization)

有向圖(a)的聯合分布是一系列條件機率因子的乘積:

PGM——從有向圖到無向圖的轉化(moralization)

轉化成無向圖如(b)所示,很簡單,這個無向圖中的maximal cliques就是一對相鄰的節點,是以聯合分布機率的形式就是:

PGM——從有向圖到無向圖的轉化(moralization)

其實就是把第一個節點的邊緣機率

PGM——從有向圖到無向圖的轉化(moralization)

吸收進第一個potential function,以此類推:

PGM——從有向圖到無向圖的轉化(moralization)

注意:這裡這裡partition function Z=1.

這種轉換如何推廣至其它圖結構? 這樣我們就可以把任意一個基于特定的有向圖的因式分解的分布函數轉換成一個基于無向圖的因式分解了。

首先,保證條件分布裡的任何一個變量都至少是無向圖中一個clique裡的一員。 對于無向圖中隻有一個父節點的點可以直接将有向的連接配接線改成無向連接配接線。 但是對于在有向圖中有一個以上父節點的node,就不可以再這樣做了。 下圖是一個有三個父節點的有向圖:

PGM——從有向圖到無向圖的轉化(moralization)

其聯合分布:

PGM——從有向圖到無向圖的轉化(moralization)

把邊緣機率吸收進

PGM——從有向圖到無向圖的轉化(moralization)

所在的clique potential裡,是以他們就同屬于一個clique,需要在任意兩個父節點之間添加連接配接線。 這種在父節點之間添加連接配接線的過程叫做moralization。 得到的無向圖就叫moral graph (值得注意,在這個例子裡,和無向圖相比,the moral graph是全連接配接的(fully connected)是以展現出沒有條件獨立的特性。其實在無向圖轉化成有向圖的方法中,moral graph可以最大化地保留原有向圖中的條件獨立性。 如果我們将有向圖轉化成無向圖時,簡單地将任意兩個節點連接配接起來,形成一個全連接配接的無向圖,但是這樣就舍棄了所有條件獨立特性。但moralization的過程可以通過添加最少的連接配接線在無向圖中保留最多個數的獨立特性。)

上面這個圖所對應的無向圖如下:

PGM——從有向圖到無向圖的轉化(moralization)

總結:将有向圖轉化成無向圖的一般步驟,首先,在有向圖的每個節點的兩個父節點之間添加無向的連接配接線,然後把原來的連接配接線去掉箭頭,就可以得到moral graph了。 然後我們要把無向圖裡所有的clique potential初始化為1.