Proof of Hammersley-Clifford Theorem
Proof of Hammersley-Clifford Theorem
依赖知识
定义1
定义2
证明过程
反向证明(吉布斯分布=>MRF)
正向证明(MRF=>吉布斯分布)
证明第一点
证明第二点
疑问点
最近看语义分割论文DeepLab，有使用全连接CRF恢复局部的细节信息，提升分割精度。又回去复习了下CRF，仍然有一个问题很困扰: “根据Hammersley Clifford定理，一个无向图模型的概率可以表示为定义在图上所有最大团上的势函数的乘积”；为什么可以这么定义，也就是Hammersley Clifford定理证明过程，书中并没有没有给出；网上看到也有一些童鞋有同样的困惑，本文翻译并备注了证明过程，希望对大家有所帮助。
原文地址: Proof of Hammersley-Clifford Theorem
本文下载地址：Hammersley-Clifford定理证明
依赖知识
a): 熟悉概率论的基础知识
b):了解概率图模型;熟悉MRF,最大团相关知识
定义1
一个无向图模型G称之为马尔科夫随机场(MRF),如果两个顶点被观测顶点分割情况下条件独立。也就是说对图中任意顶点XiXi ，以下条件属性成立
P(Xi|XG∖i)=P(Xi|XNi)(1)
(1)P(Xi|XG∖i)=P(Xi|XNi)
XG∖iXG∖i 代表除了XiXi 之外的所有顶点，XNiXNi 代表ii的所有邻居顶点-即所有与XiXi 相连的顶点。
定义2
在无向图模型G上的一个概率分布P(X)P(X) 称之为吉布斯分布，如果它能够因子分解为定义在团(clique)上的正函数的乘积，这些团覆盖了G的所有顶点和边。即
P(X)=1Z∏c∈CGϕc(Xc)(2)
(2)P(X)=1Z∏c∈CGϕc(Xc)
CGCG 是G上所有(最大)团的集合，Z=∑x∏c∈CGϕc(Xc)Z=∑x∏c∈CGϕc(Xc) 是归一化常量。
证明过程
Hammersley Clifford告诉我们这两个定义是等价的，下面将证明这个定理。
反向证明(吉布斯分布=>MRF)
设Di=Ni⋃{Xi}Di=Ni⋃{Xi} 是包含XiXi 邻居顶点和XiXi 本身的集合。从等式(1)的右边开始
P(Xi|XNi)=P(Xi,XNi)P(XNi)(3)
(3)P(Xi|XNi)=P(Xi,XNi)P(XNi)
=∑G∖Di∏c∈CGϕc(Xc)∑xi∑G∖Di∏c∈CGϕc(Xc)(4)
(4) =∑G∖Di∏c∈CGϕc(Xc)∑xi∑G∖Di∏c∈CGϕc(Xc)
基于是否包含XiXi 将最大团CGCG 分为两组：
Ci=c∈CG:Xi∈cCi=c∈CG:Xi∈c 和 Ri=c∈CG:Xi∉cRi=c∈CG:Xi∉c ；现在可以将等式(4)分为CiCi 和 RiRi 上的乘积。
P(Xi|XNi)=∑G∖Di∏c∈Ciϕc(Xc)∏c∈Riϕc(Xc)∑xi∑G∖Di∏c∈Ciϕc(Xc)∏c∈Riϕc(Xc)(5)
(5)P(Xi|XNi)=∑G∖Di∏c∈Ciϕc(Xc)∏c∈Riϕc(Xc)∑xi∑G∖Di∏c∈Ciϕc(Xc)∏c∈Riϕc(Xc)
=∏c∈Ciϕc(Xc)∑G∖Di∏c∈Riϕc(Xc)∑xi∏c∈Ciϕc(Xc)∑G∖Di∏c∈Riϕc(Xc)(5)
(5)=∏c∈Ciϕc(Xc)∑G∖Di∏c∈Riϕc(Xc)∑xi∏c∈Ciϕc(Xc)∑G∖Di∏c∈Riϕc(Xc)
在G∖DiG∖Di 上的求和可以移到CiCi 乘积的后面，因为CiCi 团中所有的顶点一定都来自DiDi; 因为CiCi 只包含XiXi 和与XiXi 相邻的顶点，由DiDi 的定义可知；因而 CiCi 乘积对于在G∖DiG∖Di 上的求和相当于常数项，故可以把CiCi 乘积拿到G∖DiG∖Di 上的求和的外面。
同样注意到因子∑G∖Di∏c∈Riϕc(Xc)∑G∖Di∏c∈Riϕc(Xc) 没有包含XiXi ,并且可以从分母移除，因为分子也包含了它。因此有：
P(Xi|XNi)=∏c∈Ciϕc(Xc)∑xi∏c∈Ciϕc(Xc)(7)
(7)P(Xi|XNi)=∏c∈Ciϕc(Xc)∑xi∏c∈Ciϕc(Xc)
=∏c∈Ciϕc(Xc)∑xi∏c∈Ciϕc(Xc)∗∏c∈Riϕc(Xc)∏c∈Riϕc(Xc)(8)
(8) =∏c∈Ciϕc(Xc)∑xi∏c∈Ciϕc(Xc)∗∏c∈Riϕc(Xc)∏c∈Riϕc(Xc)
=∏c∈CGϕc(Xc)∑xi∏c∈CGϕc(Xc)(9)
(9) =∏c∈CGϕc(Xc)∑xi∏c∈CGϕc(Xc)
=P(X)P(XG∖{i})(10)
(10)=P(X)P(XG∖{i})
=P(Xi|XG∖{i})(11)
(11)=P(Xi|XG∖{i})
消除了G∖DiG∖Di 上的求和项后，在公式(8)的分子分母乘上一个相同的因子，再次引入势函数；最终公式(11)与公式(1)的左边相等，证明了反向等价。
正向证明(MRF=>吉布斯分布)
对于任意s⊂Gs⊂G,定义一个如下的候选势函数:
fs(Xs=xs)=∏z⊂sP(Xz=xz,XG∖z=0)−1|s|−|z|(12)
(12)fs(Xs=xs)=∏z⊂sP(Xz=xz,XG∖z=0)−1|s|−|z|
等式右边的乘积是在s的所有子集上进行的。
对于s任意子集z, P(Xz=xz,XG∖z=0)P(Xz=xz,XG∖z=0) 表示属于z的顶点(随机变量取值)与s一致，图中其它顶点给默认值(记做”0”)。
当s集合与z集合顶点个数不同时指数为1，否则为0; |s||s| 表示集合s中元素(顶点)个数。
很显然f是正函数，概率都是非负的。
只需要需要证明如下两点,即可说明无向图模型的概率P(X)P(X) 可以表示为图上所有团的势函数乘积。
a). ∏s⊂Gfs(Xs)=P(X) (a)∏s⊂Gfs(Xs)=P(X) (a)
b). fs(Xs)=1fs(Xs)=1 如果ss 不是一个团
证明第一点
为证明第一点，先来展示一个恒等式:
0=(1−1)K=CK0−CK1+CK2+......+(−1)KCKK(13)
(13)0=(1−1)K=C0K−C1K+C2K+......+(−1)KCKK
a. CKNCNK 表示从K个元素中选取N个元素的所有组合情况
b. 现在证明∏s⊂Gfs(Xs)∏s⊂Gfs(Xs) 中所有的因子都可以互相抵消，除了P(X)P(X) ；
c. 对于任意子集z∈Gz∈G ,及zz 相关的因子Δ=P(Xz,XG∖z=0)Δ=P(Xz,XG∖z=0) ；它在s不包含z的情况下没有出现(此时z不会是s的子集)；
d. 它在s=zs=z 情况下出现一次(z=s是s的子集)，因而Δ−10=ΔΔ−10=Δ
f. 它在s包含z以及另外一个元素的情况下出现C|G|−|z|1C1|G|−|z| 次；因为s的选择有C|G|−|z|1C1|G|−|z| 种，并且满足|s|−|z|=1|s|−|z|=1 ,因此这时Δ−11=Δ−1Δ−11=Δ−1 。
g. 它在s包含z以及另外两个个元素的情况下出现C|G|−|z|2C2|G|−|z| 次；因为s的选择有C|G|−|z|2C2|G|−|z| 种，并且满足|s|−|z|=2|s|−|z|=2 ,因此这时Δ−12=ΔΔ−12=Δ
h. 依次类推… … ；最终第一点的等式(a)左边, z相关因子ΔΔ 所有乘积就是：
Δ∗Δ−1(C|G|−|z|1)∗Δ−12(C|G|−|z|2)∗...∗∗Δ−1|G|−|z|(C|G|−|z||G|−|z|)
Δ∗Δ−1(C1|G|−|z|)∗Δ−12(C2|G|−|z|)∗...∗∗Δ−1|G|−|z|(C|G|−|z||G|−|z|)
=Δ(1−C|G|−|z|1+C|G|−|z|2+(−1)|G|−|z|(C|G|−|z||G|−|z|))
=Δ(1−C1|G|−|z|+C2|G|−|z|+(−1)|G|−|z|(C|G|−|z||G|−|z|))
令K=|G|−|z|K=|G|−|z| , 根据公式(13)可以看出所有的因子互相抵消Δ0=1Δ0=1 ；除了一种情况z=Gz=G 。因而有
∏s⊂Gfs(Xs)=Δ{z=G}=P(XG,XG∖G=0)=P(XG)=P(X)
∏s⊂Gfs(Xs)=Δ{z=G}=P(XG,XG∖G=0)=P(XG)=P(X)
i. 第一点证明完毕。
证明第二点
为证明第二点，需要使用马尔科夫属性，如果s不是一个团，那么一定有两个属于s的顶点a、b，它们之间没有边连接，我们按照如下方式重写fs(Xs)fs(Xs)
fs(Xs=xs)fs(Xs=xs)
=∏z⊂sP(Xz=xz,XG∖z=0)−1|s|−|z|(14)
(14)=∏z⊂sP(Xz=xz,XG∖z=0)−1|s|−|z|
=∏w⊂s∖{a,b}[P(Xw,XG∖w=0)P(Xw⋃{a,b},XG∖w⋃{a,b}=0)P(Xw⋃{a},XG∖w⋃{a}=0)P(Xw⋃{b},XG∖w⋃{b}=0)]−1∗(15)
(15)=∏w⊂s∖{a,b}[P(Xw,XG∖w=0)P(Xw⋃{a,b},XG∖w⋃{a,b}=0)P(Xw⋃{a},XG∖w⋃{a}=0)P(Xw⋃{b},XG∖w⋃{b}=0)]−1∗
公式(15)将z⊂sz⊂s 分为4中情况：z=w,z=w⋃{a},z=w⋃{b}和z=w⋃{a,b}z=w,z=w⋃{a},z=w⋃{b}和z=w⋃{a,b} ,并显示的写出了这些因子。注意公式(15)中的位置是对的哦。接下来将证明他们互相抵消。因此指数是多少不重要了，这里用−1∗−1∗ 表示。
根据贝叶斯规则有：
P(Xw,XG∖w=0)P(Xw⋃{a},XG∖w⋃{a}=0)
P(Xw,XG∖w=0)P(Xw⋃{a},XG∖w⋃{a}=0)
=P(Xa=0|Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xa|Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xb=0,Xw,XG∖w⋃{a,b}=0)(16)
(16)=P(Xa=0|Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xa|Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xb=0,Xw,XG∖w⋃{a,b}=0)
=P(Xa=0|Xb,Xw,XG∖w⋃{a,b}=0)P(Xb,Xw,XG∖w⋃{a,b}=0)P(Xa|Xb,Xw,XG∖w⋃{a,b}=0)P(Xb,Xw,XG∖w⋃{a,b}=0)(17)
(17)=P(Xa=0|Xb,Xw,XG∖w⋃{a,b}=0)P(Xb,Xw,XG∖w⋃{a,b}=0)P(Xa|Xb,Xw,XG∖w⋃{a,b}=0)P(Xb,Xw,XG∖w⋃{a,b}=0)
=P(Xw⋃{b},XG∖w⋃{b}=0)P(Xw⋃{a,b},XG∖w⋃{a,b}=0)(18)
(18)=P(Xw⋃{b},XG∖w⋃{b}=0)P(Xw⋃{a,b},XG∖w⋃{a,b}=0)
a) 公式(16)依据概率分解P(a,b)=P(a|b)∗P(b)P(a,b)=P(a|b)∗P(b) ; 首先仅仅看因子部分P(Xw,XG∖w=0)=P(Xa=0,Xb=0,Xw,XG∖w⋃{a,b}=0)=P(Xa=0|Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xw,XG∖w=0)=P(Xa=0,Xb=0,Xw,XG∖w⋃{a,b}=0)=P(Xa=0|Xb=0,Xw,XG∖w⋃{a,b}=0)P(Xb=0,Xw,XG∖w⋃{a,b}=0)
b) 同理分母部分一样的分解
c) 公式(16)的左边部分，由于XaXa 和XbXb 在给定图剩余部分是条件独立的，因此可以将Xb=0Xb=0 替换为XbXb ;分子分母都替换了。
d) 公式(16)的右边部分，分子分母是一样的,可以约掉，实际上是先约掉，然后在同时乘一个相同的因子；得到公式(17),自然而然概率连乘得到公式(18)
e) 将公式(18)结果带入公式(15); 可知公式(15) 恒等于1. 第二点证明完毕。
疑问点
本文的证明，只能说明无向图模型的概率可以分解为G上所有团的势函数乘积；并不能说明是所有的最大团的势函数乘积。 哪位网友知道，麻烦给我回复，非常感谢！
---------------------
作者：csuyzt
来源：CSDN
原文：https://blog.csdn.net/csuyzt/article/details/81709439
版权声明：本文为博主原创文章，转载请附上博文链接！