Hammersley-Clifford定理證明

Proof of Hammersley-Clifford Theorem

[TOC]

? 最近看語義分割論文DeepLab，有使用全連接CRF恢復(fù)局部的細(xì)節(jié)信息，提升分割精度。又回去復(fù)習(xí)了下CRF，仍然有一個(gè)問題很困擾: "根據(jù)Hammersley Clifford定理，一個(gè)無向圖模型的概率可以表示為定義在圖上所有最大團(tuán)上的勢函數(shù)的乘積"；為什么可以這么定義，也就是Hammersley Clifford定理證明過程，書中并沒有沒有給出；網(wǎng)上看到也有一些童鞋有同樣的困惑，本文翻譯并備注了證明過程，希望對大家有所幫助。

原文地址: Proof of Hammersley-Clifford Theorem

本文下載地址：Hammersley-Clifford定理證明

依賴知識(shí)

a): 熟悉概率論的基礎(chǔ)知識(shí)

b):了解概率圖模型;熟悉MRF,最大團(tuán)相關(guān)知識(shí)

定義1

? 一個(gè)無向圖模型G稱之為馬爾科夫隨機(jī)場(MRF),如果兩個(gè)頂點(diǎn)被觀測頂點(diǎn)分割情況下條件獨(dú)立。也就是說對圖中任意頂點(diǎn)X_i ，以下條件屬性成立
P(X_i|X_{G\backslash i}) = P(X_i|X_{N_i}) \tag 1
? X_{G \backslash i} 代表除了X_i 之外的所有頂點(diǎn)，X_{N_i} 代表i的所有鄰居頂點(diǎn)-即所有與X_i 相連的頂點(diǎn)。

定義2

? 在無向圖模型G上的一個(gè)概率分布P(X) 稱之為吉布斯分布，如果它能夠因子分解為定義在團(tuán)(clique)上的正函數(shù)的乘積，這些團(tuán)覆蓋了G的所有頂點(diǎn)和邊。即
P(X) = \frac 1 Z \prod_{c \in C_G} \phi_c(X_c) \tag 2
? C_G 是G上所有(最大)團(tuán)的集合，Z=\sum_x \prod_{c \in C_G} \phi_c(X_c) 是歸一化常量。

?

證明過程

? Hammersley Clifford告訴我們這兩個(gè)定義是等價(jià)的，下面將證明這個(gè)定理。

反向證明(吉布斯分布=>MRF)

? 設(shè)D_i = N_i \bigcup \{X_i\} 是包含X_i 鄰居頂點(diǎn)和X_i 本身的集合。從等式(1)的右邊開始
P(X_i|X_{N_i}) = \frac {P(X_i,X_{N_i})} {P(X_{N_i})} \tag 3

\ \ \ \ \ \ \ =\frac {\sum_{G \backslash D_i} \prod_{c \in C_G} \phi_c(X_c)} {\sum_{x_i} \sum_{G \backslash D_i} \prod_{c \in C_G} \phi_c(X_c)} \tag 4

? 基于是否包含X_i 將最大團(tuán)C_G 分為兩組：

C_i = {c \in C_G: X_i \in c} 和 R_i = {c \in C_G: X_i \notin c} ；現(xiàn)在可以將等式(4)分為C_i 和 R_i 上的乘積。
P(X_i|X_{N_i}) =\frac {\sum_{G \backslash D_i} \prod_{c \in C_i} \phi_c(X_c) \prod_{c \in R_i} \phi_c(X_c)} {\sum_{x_i} \sum_{G \backslash D_i} \prod_{c \in C_i} \phi_c(X_c) \prod_{c \in R_i} \phi_c(X_c)} \tag 5

= \frac {\prod_{c \in C_i} \phi_c(X_c) \sum_{G \backslash D_i} \prod_{c \in R_i} \phi_c(X_c)} {\sum_{x_i} \prod_{c \in C_i} \phi_c(X_c) \sum_{G \backslash D_i} \prod_{c \in R_i} \phi_c(X_c)} \tag 5

? 在G \backslash D_i 上的求和可以移到C_i 乘積的后面，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=C_i" alt="C_i"> 團(tuán)中所有的頂點(diǎn)一定都來自D_i; 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=C_i" alt="C_i"> 只包含X_i 和與X_i 相鄰的頂點(diǎn)，由D_i 的定義可知；因而 C_i 乘積對于在G \backslash D_i 上的求和相當(dāng)于常數(shù)項(xiàng)，故可以把C_i 乘積拿到G \backslash D_i 上的求和的外面。

? 同樣注意到因子\sum_{G \backslash D_i} \prod_{c \in R_i} \phi_c(X_c) 沒有包含X_i ,并且可以從分母移除，因?yàn)榉肿右舶怂?。因此有?br> P(X_i|X_{N_i}) = \frac {\prod_{c \in C_i} \phi_c(X_c)} {\sum_{x_i} \prod_{c \in C_i} \phi_c(X_c)} \tag 7

\ \ \ \ \ \ \ \ \ \ =\frac {\prod_{c \in C_i} \phi_c(X_c)} {\sum_{x_i} \prod_{c \in C_i} \phi_c(X_c)} * \frac {\prod_{c \in R_i} \phi_c(X_c)} {\prod_{c \in R_i} \phi_c(X_c)} \tag 8

\ \ \ \ \ \ \ \ \ \ =\frac {\prod_{c \in C_G} \phi_c(X_c)} {\sum_{x_i} \prod_{c \in C_G} \phi_c(X_c)} \tag 9

= \frac {P(X)} {P(X_{G \backslash \{i\}})} \tag {10}

= P(X_i|X_{G \backslash \{i\}}) \tag {11}

? 消除了G \backslash D_i 上的求和項(xiàng)后，在公式(8)的分子分母乘上一個(gè)相同的因子，再次引入勢函數(shù)；最終公式(11)與公式(1)的左邊相等，證明了反向等價(jià)。

正向證明(MRF=>吉布斯分布)

? 對于任意s \subset G,定義一個(gè)如下的候選勢函數(shù):

f_s(X_s=x_s) = \prod_{z \subset s} P(X_z=x_z,X_{G \backslash z} =0)^{-1^{|s|-|z|}} \tag {12}

  1. 等式右邊的乘積是在s的所有子集上進(jìn)行的。
  2. 對于s任意子集z, P(X_z=x_z,X_{G \backslash z} =0) 表示屬于z的頂點(diǎn)(隨機(jī)變量取值)與s一致，圖中其它頂點(diǎn)給默認(rèn)值(記做"0")。
  3. 當(dāng)s集合與z集合頂點(diǎn)個(gè)數(shù)不同時(shí)指數(shù)為1，否則為0; |s| 表示集合s中元素(頂點(diǎn))個(gè)數(shù)。
  4. 很顯然f是正函數(shù)，概率都是非負(fù)的。
  5. 只需要需要證明如下兩點(diǎn),即可說明無向圖模型的概率P(X) 可以表示為圖上所有團(tuán)的勢函數(shù)乘積。
  1. \prod_{s \subset G} f_s(X_s) = P(X) \ \ \ (a)
  2. f_s(X_s) =1 如果s 不是一個(gè)團(tuán)

證明第一點(diǎn)

? 為證明第一點(diǎn)，先來展示一個(gè)恒等式:
0 = (1 - 1)^K = C_0^K - C_1^K + C_2^K + ... ... + (-1)^KC_K^K \tag {13}

a. C_N^K 表示從K個(gè)元素中選取N個(gè)元素的所有組合情況

b. 現(xiàn)在證明\prod_{s \subset G} f_s(X_s) 中所有的因子都可以互相抵消，除了P(X) ；

c. 對于任意子集z \in G ,及z 相關(guān)的因子\Delta = P(X_z, X_{G \backslash z = 0}) ；它在s不包含z的情況下沒有出現(xiàn)(此時(shí)z不會(huì)是s的子集)；

d. 它在s=z 情況下出現(xiàn)一次(z=s是s的子集)，因而\Delta ^{-1^0} = \Delta

f. 它在s包含z以及另外一個(gè)元素的情況下出現(xiàn)C_1^{|G|-|z|} 次；因?yàn)閟的選擇有C_1^{|G|-|z|} 種，并且滿足|s|-|z|=1 ,因此這時(shí)\Delta ^{-1^1} = \Delta ^{-1} 。

g. 它在s包含z以及另外兩個(gè)個(gè)元素的情況下出現(xiàn)C_2^{|G|-|z|} 次；因?yàn)閟的選擇有C_2^{|G|-|z|} 種，并且滿足|s|-|z|=2 ,因此這時(shí)\Delta ^{-1^2} = \Delta

h. 依次類推... ... ；最終第一點(diǎn)的等式(a)左邊, z相關(guān)因子\Delta 所有乘積就是：
\Delta * \Delta^{-1(C_1^{|G|-|z|})} * \Delta^{-1^2(C_2^{|G|-|z|})} * ... * * \Delta^{-1^{|G|-|z|}(C_{|G|-|z|}^{|G|-|z|})}

= \Delta ^{(1- C_1^{|G|-|z|} + C_2^{|G|-|z|} + (-1)^{|G|-|z|}(C_{|G|-|z|}^{|G|-|z|})) }

? 令K=|G|-|z| , 根據(jù)公式(13)可以看出所有的因子互相抵消\Delta ^0= 1 ；除了一種情況z=G 。因而有
\prod_{s \subset G} f_s(X_s) =\Delta_{\{z=G\}} =P(X_G, X_{G \backslash G = 0}) =P(X_G) = P(X)
i. 第一點(diǎn)證明完畢。

證明第二點(diǎn)

? 為證明第二點(diǎn)，需要使用馬爾科夫?qū)傩?，如果s不是一個(gè)團(tuán)，那么一定有兩個(gè)屬于s的頂點(diǎn)a、b，它們之間沒有邊連接，我們按照如下方式重寫f_s(X_s)

? f_s(X_s=x_s)
= \prod_{z \subset s} P(X_z=x_z,X_{G \backslash z} =0)^{-1^{|s|-|z|}} \tag {14}

= \prod_{w \subset s \backslash \{a,b\}} \left[ \frac {P(X_w,X_{G \backslash w}=0) P(X_{w \bigcup \{a,b\}},X_{G \backslash w \bigcup \{a,b\}}=0)} {P(X_{w \bigcup \{a\}},X_{G \backslash w \bigcup \{a\}}=0) P(X_{w \bigcup \{b\}},X_{G \backslash w \bigcup \{b\}}=0) } \right]^{-1^*} \tag {15}

? 公式(15)將z \subset s 分為4中情況：z=w, z=w \bigcup \{a\},z=w \bigcup \{b\} 和 z = w \bigcup \{a,b\} ,并顯示的寫出了這些因子。注意公式(15)中的位置是對的哦。接下來將證明他們互相抵消。因此指數(shù)是多少不重要了，這里用-1^* 表示。

根據(jù)貝葉斯規(guī)則有：

\frac {P(X_w,X_{G \backslash w}=0)} {P(X_{w \bigcup \{a\}},X_{G \backslash w \bigcup \{a\}}=0)}

=\frac {P(X_a=0|X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0) P(X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0)} {P(X_a|X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0) P(X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0)} \tag {16}

=\frac {P(X_a=0|X_b,X_w,X_{G \backslash w \bigcup \{a,b\}}=0) P(X_b,X_w,X_{G \backslash w \bigcup \{a,b\}}=0)} {P(X_a|X_b,X_w,X_{G \backslash w \bigcup \{a,b\}}=0) P(X_b,X_w,X_{G \backslash w \bigcup \{a,b\}}=0)} \tag {17}

=\frac {P(X_{w \bigcup \{b\}},X_{G \backslash w \bigcup \{b\}}=0)} {P(X_{w \bigcup \{a,b\}},X_{G \backslash w \bigcup \{a,b\}}=0)} \tag {18}

a) 公式(16)依據(jù)概率分解P(a,b)=P(a|b)*P(b) ; 首先僅僅看因子部分P(X_w,X_{G \backslash w}=0) \\= P(X_a=0,X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0) \\=P(X_a=0|X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0) P(X_b=0,X_w,X_{G \backslash w \bigcup \{a,b\}}=0)

b) 同理分母部分一樣的分解

c) 公式(16)的左邊部分，由于X_a 和X_b 在給定圖剩余部分是條件獨(dú)立的，因此可以將X_b=0 替換為X_b ;分子分母都替換了。

d) 公式(16)的右邊部分，分子分母是一樣的,可以約掉，實(shí)際上是先約掉，然后在同時(shí)乘一個(gè)相同的因子；得到公式(17),自然而然概率連乘得到公式(18)

e) 將公式(18)結(jié)果帶入公式(15); 可知公式(15) 恒等于1. 第二點(diǎn)證明完畢。

疑問點(diǎn)

  1. 本文的證明，只能說明無向圖模型的概率可以分解為G上所有團(tuán)的勢函數(shù)乘積；并不能說明是所有的最大團(tuán)的勢函數(shù)乘積。 哪位網(wǎng)友知道，麻煩給我回復(fù)，非常感謝！
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 因受今年2號(hào)臺(tái)風(fēng)“苗柏”外圍環(huán)流影響，小漠陣風(fēng)達(dá)11級(jí)；并出現(xiàn)特大暴雨，致使水庫水源變濁，飲用水安全受到威...
    小漠宣傳閱讀 2,915評(píng)論 31贊 1
  • 愛上寫字？這是多么好笑的事情。曾幾何時(shí)，所有的好心情都會(huì)被寫一篇文字這樣的任務(wù)而打破?？涩F(xiàn)在，竟然愛上了寫字，哪怕...
    擰巴人生閱讀 190評(píng)論 0贊 1
  • 當(dāng)然每條路，沒有好壞，對錯(cuò)，也沒有優(yōu)劣之分。選擇哪條路，日后在老去的路上不后悔就好。努力的意義，或許日后能讓自己及...
    林琳success閱讀 378評(píng)論 2贊 2
  • 王者榮耀
    死若隱活若現(xiàn)閱讀 142評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容