概率圖模型（1）：表示

作者：心有寶寶人自圓
聲明：歡迎轉(zhuǎn)載本文中的圖片或文字玷过，請說明出處

寫在前面

最近讀到的文章需要深入的了解概率圖模型（Probability Graph Model）才能搞清楚使用深度學(xué)習(xí)方法建模的原理龄广，所以整理一下概率圖模型的相關(guān)內(nèi)容來加深理解（果然再消化一遍就會(huì)有新的收獲??）

我寫的這篇學(xué)習(xí)筆記沒有使用非常標(biāo)準(zhǔn)的術(shù)語，我認(rèn)為重要的是理解有關(guān)的概念

這篇文章主要介紹概率圖模型的表示鞭盟，包括有向圖（貝葉斯網(wǎng)）和無向圖（馬爾可夫網(wǎng)个从、馬爾可夫隨機(jī)場）

0.Background

0.1 概率

對于n維離散隨機(jī)變量 $\boldsymbol x=(x_1,x_2,...,x_n)$ 侣监，其中 $x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(m)})',i=1,2,....,n$

為了對該隨機(jī)變量 $\boldsymbol x$ 建模鸭轮，我們需要兩種最基本的概率

$\begin{cases}邊緣概率P(x_i)=\sum_{k_1=1}^m...\sum_{k_{n-1}=1}^m P(x_1^{(k1)},x2^{(k2)},...,x_i,...,x_n^{k_{n-1}})\\條件概率P(x_j|x_i)=\frac{P(x_i,x_j)}{P(x_i)}\end{cases}$

可以通過邊緣概率和條件概率推導(dǎo)出：

$鏈?zhǔn)椒▌t：P(x_1,x_2,...,x_n)=\prod_{i=1}^n(x_i|x_1,..,x_{i-1})$

$貝葉斯法則：P(x_2|x_1)=\frac{P(x_1,x_2)}{P(x_1)}=\frac{P(x_1,x_2)}{\int P(x_1,x_2)dx_2}=\frac{P(x_2)P(x_1|x_2)}{\int P(x_2)P(x_1|x_2)dx_2}$

不難發(fā)現(xiàn)若要為 $P(\boldsymbol x)=P(x_1,x_2,...,x_n)$ 建模，計(jì)算量是隨維度指數(shù)增長的橄霉，計(jì)算十分復(fù)雜

因此為了簡化計(jì)算窃爷，提出了一些簡化的條件：

獨(dú)立性假設(shè)： $P(x_1,...,x_n)=\prod_{i=1}^nP(x_i),x_i\bot x_j$ ，如樸素貝葉斯姓蜂，但條件過強(qiáng)
馬爾可夫假設(shè)： $x_j\bot x_{i+1}|x_{i-k+1},i<j$ 意味著當(dāng)前隨機(jī)變量只與前k個(gè)隨機(jī)變量有關(guān)按厘，如一階馬爾可夫過程 $P(x_1,...,x_n)=P(x_1)\prod_{i=2}^nP(x_i|x_{i-1}),其中x_j\bot x_{i+1}|x_i,i<j$ ，雖然條件有些放松但仍過強(qiáng)
條件獨(dú)立性假設(shè)： $(\boldsymbol x_A\bot \boldsymbol x_B)| \boldsymbol x_C钱慢，其中\(zhòng)boldsymbol x_A逮京，\boldsymbol x_B，\boldsymbol x_C是不相交的集合$

連續(xù)隨機(jī)變量也有類似的情況束莫，出于簡單只考慮離散隨機(jī)變量

0.2 圖

0.2.1 表示

$\begin{cases}一般是離散隨機(jī)變量\begin{cases}有向圖 Bayesian Network\\無向圖 Markov Network\end{cases}\\服從高斯分布的連續(xù)變量\begin{cases}有向圖 Gauss B N\\無向圖 Gauss M N\end{cases}\end{cases}$

0.2.2 推斷

$\begin{cases}精確推斷：直接根據(jù)圖計(jì)算概率分布\\近似推斷\begin{cases}確定性近似推斷（變分推斷）\\隨機(jī)近似：蒙特卡洛采樣（MCMC）\end{cases}\end{cases}$

0.2.3 學(xué)習(xí)

$\begin{cases}參數(shù)學(xué)習(xí)\begin{cases}完備數(shù)據(jù)：即無隱變量的數(shù)據(jù)懒棉，有向圖和無向圖有各自的算法\\隱變量：EM算法\end{cases}\\結(jié)構(gòu)學(xué)習(xí)：學(xué)習(xí)適合數(shù)據(jù)的圖模型和參數(shù)\end{cases}$

1. 有向圖 Bayesian Network

1.1 表示

前提條件：隨機(jī)變量 $x_1,x_2,...,x_n$ 之間存在條件獨(dú)立性

構(gòu)建有向圖：對隨機(jī)變量 $x_1,...,x_n$ 拓?fù)渑判?/p>

因子分解：根據(jù)有向圖直接得出模型 $P(x_1,x_2,...,x_n)=\prod_{i=1}^n P(x_i|\boldsymbol x_{Pa_=(i)})，其中\(zhòng)boldsymbol x_{Pa(i)}是x_i的父結(jié)點(diǎn)的集合$

例子：有向圖的局部結(jié)構(gòu)：貝葉斯網(wǎng)絡(luò)本身就蘊(yùn)含了條件獨(dú)立的性質(zhì)

有向圖的局部結(jié)構(gòu)

1.2 D劃分 D-Separation

作用：基于有向圖檢測隨機(jī)變量之間的獨(dú)立的圖形化方法

條件獨(dú)立性： $(\boldsymbol x_A\bot \boldsymbol x_B)| \boldsymbol x_C览绿，其中\(zhòng)boldsymbol x_A漓藕，\boldsymbol x_B，\boldsymbol x_C是不相交的集合$

Tail-to-Tail型： $a\in \boldsymbol x_C,b\in \boldsymbol x_A (或\boldsymbol x_B),c\in \boldsymbol x_B (或\boldsymbol x_A)$ 挟裂，即路徑都通過 $\boldsymbol x_C$ 才滿足條件獨(dú)立
Head-to-Tail型： $b\in \boldsymbol x_C,a\in \boldsymbol x_A (或x_B),c\in \boldsymbol x_B (或\boldsymbol x_A)$$a\in \boldsymbol x_C,b\in \boldsymbol x_A (或\boldsymbol x_B),c\in \boldsymbol x_B (或\boldsymbol x_A)$ ，即路徑都通過 $\boldsymbol x_C$ 才滿足條件獨(dú)立
Head-to-Head型： $a\in \boldsymbol x_A (或\boldsymbol x_B),b\in \boldsymbol x_B (或\boldsymbol x_A),c和c的子孫(如d)必須在\boldsymbol x_A\and \boldsymbol x_B\and \boldsymbol x_C的補(bǔ)集中$ 揍诽，即路徑都不能通過 $\boldsymbol x_C$ 和c的子孫才滿足條件獨(dú)立

換句話說就是路徑阻塞時(shí)才（條件）獨(dú)立诀蓉，若連通則不獨(dú)立

1.3 條件獨(dú)立性

全局馬爾可夫性：有向圖的D劃分體現(xiàn)出有向圖的全局馬爾可夫性（在整個(gè)有向圖成立）
局部馬爾可夫性：設(shè)a是我們關(guān)注的結(jié)點(diǎn) $a\bot (\{祖先結(jié)點(diǎn)集合\}-父結(jié)點(diǎn))\or非子孫結(jié)點(diǎn)|父結(jié)點(diǎn)$

現(xiàn)在考慮 $P(x_k|\boldsymbol x_{-k})=P(x_k|x_1,..,x_{k-1},x_{k+1},..,x_n)$

$P(x_k|\boldsymbol x_{-k})=\frac{P(x_k,\boldsymbol x_{-k})}{P(\boldsymbol x_{-k})}=\frac{P(\boldsymbol x)}{\int_{x_k}P(\boldsymbol x)dx_k}=\frac{\prod_{i=1}^nP(x_i|\boldsymbol x_{Pa(i)})}{\int_{x_k}\prod_{i=1}^nP(x_i|\boldsymbol x_{Pa(i)})dx_k}$

在使用 $\Delta$ 代表 $\prod_{i=1}^nP(x_i|x_{\boldsymbol Pa(i)})$ 中與 $x_k$ 有關(guān)的項(xiàng)， $\Delta=P(x_k|\boldsymbol x_{Pa(k)})\cdot\prod_{s\in \boldsymbol x_{Child(k)}}P(x_s|x_k,\boldsymbol x_{Pa(s)}-x_k)$

在有向圖中暑脆，與 $x_k$ 相關(guān)的結(jié)點(diǎn)和邊成了馬爾可夫毯（即與 $x_k$ 相鄰接的所有結(jié)點(diǎn)）

由于連乘渠啤，分母中積分（或者說 $\sum$ ）中的與 $x_k$ 無關(guān)的項(xiàng)可提到積分號外與分子約分

最后得到 $P(x_k|\boldsymbol x_{-k})=\frac{\Delta}{\int_{x_k}\Delta dx_k}$

2. 無向圖 Markov Network

2.1 條件獨(dú)立性

我認(rèn)為這部分可描述為Markov Network（又稱Markov Random Field）的定義

條件獨(dú)立性： $(\boldsymbol x_A\bot \boldsymbol x_B)| \boldsymbol x_C，其中\(zhòng)boldsymbol x_A添吗，\boldsymbol x_B沥曹，\boldsymbol x_C是不相交的集合$

由于無向圖中無方向，所以就沒有3種局部結(jié)構(gòu)的區(qū)分，因此條件獨(dú)立性會(huì)很簡單妓美，相反因子分解則很復(fù)雜

全局馬爾可夫性： $a (\in \boldsymbol x_A)僵腺，b(\in \boldsymbol x_B)$ 之間的每一條路徑中至少一個(gè)結(jié)點(diǎn)c在 $\boldsymbol x_C$ 集合中，此時(shí)觀測c組成的集合 $\boldsymbol c$ 壶栋，路徑會(huì)被阻斷辰如，此時(shí)有 $(a\bot b)|\boldsymbol c$ （換句話說，只要觀測一個(gè)節(jié)結(jié)點(diǎn)通過該節(jié)結(jié)點(diǎn)這一條路徑就被阻斷了贵试，然而兩個(gè)結(jié)點(diǎn)仍可以通過其它路徑連通）
局部馬爾可夫性：設(shè)a是我們關(guān)注的結(jié)點(diǎn)琉兜，則 $a\bot\{全集-a-\boldsymbol x_{a的鄰接結(jié)點(diǎn)}\}|\boldsymbol x_{a的鄰接結(jié)點(diǎn)}$ 。（換句話說毙玻，阻斷了a的全部路徑豌蟋，a就和其余的結(jié)點(diǎn)獨(dú)立了）
成對馬爾可夫性： $x_i\bot x_j|\boldsymbol x_{-i-j}(i\ne j,且i,j不鄰接)$ 。（這個(gè)性質(zhì)是局部馬爾可夫性的推論桑滩，任意兩個(gè)不鄰接的結(jié)點(diǎn)在其余結(jié)點(diǎn)給定的條件下是條件獨(dú)立的）

這三個(gè)條件獨(dú)立性是相互等價(jià)的梧疲，可以相互推出

2.1 表示

無向圖在構(gòu)建聯(lián)合概率分布（因子分解）時(shí)比有向圖復(fù)雜很多，并且難以表達(dá)

為了解決這一問題施符，先給出圖中的一些定義：

團(tuán)：一個(gè)關(guān)于結(jié)點(diǎn)的集合往声，集合內(nèi)的任何兩個(gè)結(jié)點(diǎn)之間有邊連接（鄰接）
最大團(tuán)：團(tuán)中無法再填加任何一個(gè)結(jié)點(diǎn)形成一個(gè)更大的團(tuán)

所以我們要把因子分解定義在團(tuán)之上：

? $P(x)=\frac 1 Z\prod_{c\in \boldsymbol C}\Psi_c(\boldsymbol x_c),其中Z是歸一化因子,\boldsymbol C是團(tuán)的集合,x_c是團(tuán)中隨機(jī)變量集合,\Psi_c(x_c)是勢函數(shù)必須為正$

? $Z=\sum_xF(x)=\sum_{x_1}...\sum_{x_n}F(\boldsymbol x),其中F(\boldsymbol x)=\prod_{c\in \boldsymbol C}\Psi_c(\boldsymbol x_c)$ （類似于使聯(lián)合分布表內(nèi)各種聯(lián)合概率之和為1/計(jì)算類似于softmax的歸一化過程）

由于團(tuán)的同樣個(gè)數(shù)過多，因此在再把因子分解定義在最大團(tuán)之上

? $P(x)=\frac 1 {Z^*}\prod_{c\in \boldsymbol C^*}\Psi_c(\boldsymbol x_c),其中Z^*是歸一化因子戳吝，\boldsymbol C^*是最大團(tuán)的集合$

2.2.1 Hammersley-Clifford定理

Hammersley-Clifford定理保證基于最大團(tuán)的因子分解與無向圖的條件獨(dú)立性等價(jià)（2.1節(jié)）

換句話說根據(jù)Hammersley Clifford定理浩销，一個(gè)無向圖模型的概率可以表示為定義在圖上所有最大團(tuán)上的勢函數(shù)的乘積（證明Hammersley-Clifford定理）

有興趣可以看一下??就是證明： $馬爾可夫隨機(jī)場（馬爾可夫網(wǎng)）\Leftrightarrow吉布斯分布$

參考上述博文給出定理的證明并將一些問題進(jìn)行解釋：

必要性： $因子分解\Rightarrow條件獨(dú)立$ 等價(jià)于 ${吉布斯分布\Rightarrow馬爾可夫隨機(jī)場}$

證明目標(biāo)：

? 馬爾可夫網(wǎng)絡(luò)（馬爾科夫隨機(jī)場(MRF)）的條件獨(dú)立性是等價(jià)的，我們選擇局部馬爾可夫性作為目標(biāo)：

? 設(shè) $\boldsymbol G$ 是結(jié)點(diǎn)的全集（所有隨機(jī)變量）听哭，

? $x_i$ 是我們關(guān)注的結(jié)點(diǎn)（隨機(jī)變量）慢洋，

? $\boldsymbol N_i$ 是 $x_i$ 鄰接的結(jié)點(diǎn)（隨機(jī)變量），

（注：集合的加減法表示加入或去除元素陆盘，可以集合與集合運(yùn)算或集合與元素運(yùn)算,普筹，代替交集并集啥的 ）

? $P(x_i|\boldsymbol G-x_i)=P(x_i|\boldsymbol N_i)$

證明過程：

設(shè) $\boldsymbol D_i=\boldsymbol N_i+x_i$ 表示 $x_i$ 于其鄰接的結(jié)點(diǎn)組成的集合,

$\boldsymbol C$ 表示最大團(tuán)的集合

? $P(x_i|\boldsymbol N_i)=\frac{P(x_i,\boldsymbol N_i)}{P(\boldsymbol N_i)}=\frac{P(\boldsymbol D_i)}{P(\boldsymbol N_i)}$

這里的 $P(\boldsymbol N_i),P(\boldsymbol D_i)$ ，就很像邊緣概率分布（但還保留了一部分隨機(jī)變量而非僅一個(gè)）

? $P(\boldsymbol N_i)=\begin{cases}\int_{\boldsymbol N_i}P(\boldsymbol x)\cdot d\boldsymbol N_i,連續(xù)變量\\\sum_{\boldsymbol N_i}P(\boldsymbol x),離散變量\end{cases}$

（注：這里的積分號和累加號是很多個(gè)目標(biāo)集合內(nèi)結(jié)點(diǎn)（隨機(jī)變量）的累加）

根據(jù)上述因子分解的表示

? $P(x_i|\boldsymbol N_i)=\frac{\sum_{\boldsymbol G-D_i}\frac{1}{Z}\prod_{c\in\boldsymbol C}\Psi_c(x_c)}{\sum_{\boldsymbol G-N_i}\frac{1}{Z}\prod_{c\in\boldsymbol C}\Psi_c(x_c)}=\frac{\sum_{\boldsymbol G-D_i}\prod_{c\in\boldsymbol C}\Psi_c(x_c)}{\sum_{x_i}\sum_{\boldsymbol G-D_i}\prod_{c\in\boldsymbol C}\Psi_c(x_c)}$

設(shè) $\boldsymbol C_i$ 為 $\boldsymbol C$ 中包含 $x_i$ 的最大團(tuán)隘马， $\boldsymbol R_i$ 為 $\boldsymbol C$ 中不包含 $x_i$ 的最大團(tuán)太防， $\boldsymbol C=\boldsymbol C_i+R_i$

不難發(fā)現(xiàn)：由于最大團(tuán)的定義， $\boldsymbol C_i$ 中的最大團(tuán)必須是 $\boldsymbol N_i$ 的子集

? $P(x_i|\boldsymbol N_i)=\frac{\sum_{\boldsymbol G-D_i}\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)\prod_{c\in\boldsymbol R_i}\Psi_c(x_c)}{\sum_{x_i}\sum_{\boldsymbol G-D_i}\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)\prod_{c\in\boldsymbol R_i}\Psi_c(x_c)}=\frac{\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)\sum_{\boldsymbol G-D_i}\prod_{c\in\boldsymbol R_i}\Psi_c(x_c)}{\sum_{x_i}\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)\sum_{\boldsymbol G-D_i}\prod_{c\in\boldsymbol R_i}\Psi_c(x_c)}$

其中 $\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)$ 可以提到求和（積分）號之外酸员，就是因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cboldsymbol%20x_c" alt="\boldsymbol x_c" mathimg="1">是 $\boldsymbol N_i$ 的子集（與 $\boldsymbol G-D_i$ 交集為空）

? $P(x_i|\boldsymbol N_i)=\frac{\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)}{\sum_{x_i}\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)}=\frac{\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)}{\sum_{x_i}\prod_{c\in\boldsymbol C_i}\Psi_c(x_c)}\cdot\frac{\prod_{c\in\boldsymbol R_i}\Psi_c(x_c)}{\prod_{c\in\boldsymbol R_i}\Psi_c(x_c)}\\=\frac{\prod_{c\in \boldsymbol C}\Psi_c(x_c)}{\sum_{x_i}\prod_{c\in \boldsymbol C}\Psi_c(x_c)}=\frac{P(\boldsymbol x)}{P(\boldsymbol G-x_i)}\\=P(x_i|\boldsymbol G-x_i)$

充分性： $條件獨(dú)立\Rightarrow因子分解$ 等價(jià)于 $馬爾可夫隨機(jī)場\Rightarrow吉布斯分布$

證明目標(biāo)：無向圖模型的聯(lián)合概率 $P(\boldsymbol x)$ 可以表示為圖上所有團(tuán)的勢函數(shù)乘積（或者說聯(lián)合概率能分解為定義在團(tuán)上的乘積蜒车，且團(tuán)覆蓋了無向圖的所有頂點(diǎn)和邊）

證明過程：

先假設(shè)如下勢函數(shù)：對任意 $\boldsymbol s\subseteq \boldsymbol G$ ，有勢函數(shù)

? $f_s(x_s)=\prod_{\boldsymbol z \subseteq \boldsymbol s}P(\boldsymbol x_z,x_\boldsymbol {G-z}=0)^{-1^{|s|-|z|}}$

? $\boldsymbol s$ 是 $\boldsymbol G$ 的任意子集幔嗦， $\boldsymbol z$ 是 $\boldsymbol s$ 的任意子集

? $P(\boldsymbol x_z,\boldsymbol {G-z}=0)$ 表示將處 $\boldsymbol z$ 包含的結(jié)點(diǎn)外分配默認(rèn)值酿愧，記作0

? $|s|,|z|$ 分別標(biāo)識 $\boldsymbol s,\boldsymbol z$ 集合中的結(jié)點(diǎn)個(gè)數(shù)

? 很顯然該勢函數(shù)是非負(fù)的（概率非負(fù)）

只需證明如下2點(diǎn)，即可說明MRF的聯(lián)合概率 $P(\boldsymbol x)$ 可表示為圖上所有團(tuán)的勢函數(shù)乘積

? （1） $\prod_{\boldsymbol{s\subseteq G}}f_s(\boldsymbol x_s)=P(x)$

? （2）若 $\boldsymbol s$ 不是一個(gè)團(tuán)邀泉，則 $f_s(\boldsymbol x_s)=1$

證（1）：

? 對任意子集 $\boldsymbol z \subset \boldsymbol G$ （注意此處不再僅僅限定 $\boldsymbol z \subseteq \boldsymbol s$ 嬉挡，且 $\boldsymbol z\ne\boldsymbol G$ ）設(shè)與 $\boldsymbol z$ 相關(guān)的因子為 $\Delta=P(\boldsymbol x_z,x_{\boldsymbol G-z}=0)$

? a) $|s|=|z|$ 的情況出現(xiàn)了一次钝鸽，此時(shí) $\Delta^{-1^0}=\Delta$

? b) $|\boldsymbol s|-|\boldsymbol z|=1$ 的情況出現(xiàn)了 $C_{\boldsymbol|G|-\boldsymbol|z|}^1$ 次（組合數(shù)），此時(shí) $\Delta^{-1^1}=\Delta^{-1}$

? c) $|\boldsymbol s|-|\boldsymbol z|=2$ 的情況出現(xiàn)了 $C_{\boldsymbol|G|-\boldsymbol|z|}^2$ 次庞钢，此時(shí) $\Delta^{-1^2}=\Delta$

? ...

? n) $|\boldsymbol s|-|\boldsymbol z|=|\boldsymbol G|-|\boldsymbol z|$ 的情況出現(xiàn)了 $C_{\boldsymbol|G|-\boldsymbol|z|}^{|\boldsymbol G|-|\boldsymbol z|}$ 次（這是 $\boldsymbol s$ 的最大情況拔恰，即等于 $\boldsymbol G$ ），此時(shí) $\Delta^{-1^{|\boldsymbol G|-|\boldsymbol z|}}$

? 依此類推焊夸，所有與 $\boldsymbol z$ 相關(guān)的 $\Delta$ 連乘（記作 $\Delta_{\boldsymbol z\subset \boldsymbol G}$ ）為：

? $\Delta\cdot(\Delta^{-1})^{C_{\boldsymbol|G|-\boldsymbol|z|}^1}\cdot(\Delta)^{C_{\boldsymbol|G|-\boldsymbol|z|}^2}\cdot\cdot\cdot\cdot(\Delta^{-1^{|\boldsymbol G|-|\boldsymbol z|}})^{C_{\boldsymbol|G|-\boldsymbol|z|}^{|\boldsymbol G|-|\boldsymbol z|}}\\=\Delta^{(1-C_{\boldsymbol|G|-\boldsymbol|z|}^1+C_{\boldsymbol|G|-\boldsymbol|z|}^2+...+(-1)^{|G|-|z|}C_{\boldsymbol|G|-\boldsymbol|z|}^{\boldsymbol|G|-\boldsymbol|z|})}$

? 又有 $0=(1-1)^k=C_k^0-C_k^1+C_k^2+...+(-1)^kC_k^k\\=1-C_{\boldsymbol|G|-\boldsymbol|z|}^1+C_{\boldsymbol|G|-\boldsymbol|z|}^2+...+(-1)^{|G|-|z|}C_{\boldsymbol|G|-\boldsymbol|z|}^{\boldsymbol|G|-\boldsymbol|z|}$

? 故當(dāng) $|\boldsymbol G|\ne|\boldsymbol z|$ 時(shí) $\Delta_{\boldsymbol z\subset \boldsymbol G}=\Delta^0=1$ 仁连，此時(shí)不為1的僅剩 $|\boldsymbol G|=|\boldsymbol z|$ 的情況（記作 $\Delta_{\boldsymbol z= \boldsymbol G}$ ）

? $\prod_{\boldsymbol{s\subseteq G}}f_s(\boldsymbol x_s)=\Delta_{\boldsymbol z\subset \boldsymbol G}\cdot\Delta_{\boldsymbol z=\boldsymbol G}=\Delta_{\boldsymbol z=\boldsymbol G}\\=P(\boldsymbol x_G,\boldsymbol x_{G-G})=P(x)$

? 證（2）：

? 該證明需要用到無向圖的馬爾可夫性。若 $\boldsymbol s$ 不是一個(gè)團(tuán)阱穗，那么必存在兩個(gè)結(jié)點(diǎn) $a,b$ 沒有邊連接饭冬，故

? $f_s(x_s)=\prod_{\boldsymbol z \subseteq \boldsymbol s}P(\boldsymbol x_z,x_\boldsymbol {G-z}=0)^{-1^{|s|-|z|}}\\=\prod_{w\subseteq s-\{a,b\}}[\frac{P(\boldsymbol x_w,\boldsymbol x_{G-w}=0)\cdot P(\boldsymbol x_{w+\{a,b\}},\boldsymbol x_{G-w-\{a,b\}})}{P(\boldsymbol x_{w+a}.\boldsymbol x_{G-w-a}=0)\cdot P(\boldsymbol x_{w+b}.\boldsymbol x_{G-w-b}=0)}]^{-1^*}$

? 不難發(fā)現(xiàn)這種拆分方法將 $\boldsymbol z= \boldsymbol w,\boldsymbol z=\boldsymbol w+\{a,b\},\boldsymbol z=\boldsymbol w+a,\boldsymbol z=\boldsymbol w+b$ 分開來考慮（ $\boldsymbol w$ 可以為空集），而由于接下來的證明與指數(shù) $-1^*$ 無關(guān)揪阶，我們就不用在意其具體表示了

? 關(guān)于拆分后的形式： $P(\boldsymbol x_{w+\{a,b\}},\boldsymbol x_{G-w-\{a+b\}})$ 項(xiàng)之所以在分子昌抠，是因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=-1%5E%7B%7Cs%7C-%7Cw%7C%7D%3D-1%5E%7B%7Cs%7C-%7Cw%7C%2B2%7D" alt="-1^{|s|-|w|}=-1^{|s|-|w|+2}" mathimg="1">，故該項(xiàng)在分子上鲁僚，同理 $P(\boldsymbol x_{w+\{a\}},\boldsymbol x_{G-w-\{a\}})$ 和 $P(\boldsymbol x_{w+\{b\}},\boldsymbol x_{G-w-\{b\}})$ 項(xiàng)由于 $-(-1^{|s|-|w|})=-1^{|s|-|w|+1}$ 而為原始項(xiàng)的倒數(shù)而在分母上炊苫，所有這是正確的表達(dá)式

? 根據(jù)條件概率公式有：

? $\frac{P(\boldsymbol x_w,\boldsymbol x_{G-w}=0)}{P(\boldsymbol x_{w+a},\boldsymbol x_{G-w-a}=0)}=\frac{P(x_a=0|x_b=0,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})\cdot P(x_b=0,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}{P(x_a|x_b=0,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})\cdot P(x_b=0,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}=\frac{P(x_a=0|x_b=0,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}{P(x_a|x_b=0,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}$

? 由于 $x_a和x_b$ 在給定其他結(jié)點(diǎn)的條件下是條件獨(dú)立的（成對馬爾可夫性），故上式右邊等價(jià)于

? $\frac{P(\boldsymbol x_w,\boldsymbol x_{G-w}=0)}{P(\boldsymbol x_{w+a},\boldsymbol x_{G-w-a}=0)}=\frac{P(x_a=0|x_b,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}{P(x_a|x_b,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}=\frac{P(x_a=0|x_b,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}{P(x_a|x_b,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})}\cdot P(x_b,\boldsymbol x_w,\boldsymbol x_{G-w-\{a,b\}})\\=\frac{P(\boldsymbol x_{w+b},\boldsymbol x_{G-w-b})}{P(\boldsymbol x_{w+\{a,b\}},\boldsymbol x_{G-w-\{a,b\}})}$

? 將其代入上面的式子會(huì)發(fā)現(xiàn):

? $\frac{P(\boldsymbol x_w,\boldsymbol x_{G-w}=0)\cdot P(\boldsymbol x_{w+\{a,b\}},\boldsymbol x_{G-w-\{a,b\}})}{P(\boldsymbol x_{w+a}.\boldsymbol x_{G-w-a}=0)\cdot P(\boldsymbol x_{w+b}.\boldsymbol x_{G-w-b}=0)}\equiv1$

? 即可完成證明

? 由于最大團(tuán)的勢函數(shù)可有團(tuán)的勢函數(shù)表示冰沙，故在最大團(tuán)上該結(jié)論也成立

2.2.2 勢函數(shù)與吉布斯分布

為保證勢函數(shù)為正侨艾，一般使用 $\Psi_c(\boldsymbol x_c)=e^{-E(\boldsymbol x_c)},E(x)稱為能量函數(shù)$

這樣構(gòu)成的聯(lián)合概率 $P(\boldsymbol x)$ 是吉布斯分布（Gibbs Distribution）

? $P(x)=\frac 1 {Z^*} \prod_{c\in \boldsymbol C^*}\Psi_c(\boldsymbol x_c)\\=\frac 1 {Z^*} \prod_{c\in \boldsymbol C^*}exp\{-E(\boldsymbol x_c)\}\\=\frac 1 {Z^*}exp\{\sum_{c\in \boldsymbol C^*}-E(\boldsymbol x_c)\}$

不難發(fā)現(xiàn)：Gibbs Distribution就是一種指數(shù)族分布，這又和最大熵產(chǎn)生了聯(lián)系

結(jié)論：馬爾可夫隨機(jī)場（馬爾可夫網(wǎng)）等價(jià)于吉布斯分布（都在Hammersley-Clifford定理的證明中有體現(xiàn)）

Reference

[1] 【機(jī)器學(xué)習(xí)】【白板推導(dǎo)系列】

[2] Hammersley-Clifford定理證明

轉(zhuǎn)載請說明出處拓挥。