条件随机场与概率无向图因子分解参数化形式（一）

前言

学习条件随机场时，对于条件随机场的参数化形式很难理解，从联合概率分布的分解角度出发也很难证明出来，回顾一下前提条件，发现问题的关键在于Hammersley Clifford定理，所以从相关内容出发证明。

后面证明我还是理解错了，问题的关键不在于Hammersley Clifford定理，而在于条件概率的计算。

参考：

• CSDN：Hammersley-Clifford定理证明
• SPITZER：MARKOV RANDOM FIELDS AND GIBBS ENSEMBLES
• Hammersley,Clifford：markov fields on finite graphs and lattices
• 编程学习网：【机器学习】 概率无向图模型
• CSDN：深度学习笔记之受限玻尔兹曼机(一)玻尔兹曼分布介绍
• CSDN：Hammersley-Clifford定理证明

条件随机场中条件概率定义

条件随机场中的条件概率分布的定义是简单明了的。
$$P(y_i|x,y_1,\cdots ,y_{i-1},y_{i+1},\cdots ,y_n)=P(y_i|x,y_{i-1},y_{i+1})$$

这个证明是简单的，因为满足马尔可夫性，同时根据条件概率分布的运算规则有：
P ( y 1 , ⋯   , y i − 2 , y i , y i + 2 , ⋯   , y n ∣ x , y i − 1 , y i + 1 ) = P ( y i ∣ x , y 1 , ⋯   , y i − 1 , y i + 1 , ⋯   , y n ) ∗ P ( y 1 , ⋯   , y i − 2 , y i + 2 , ⋯   , y n ∣ x , y i − 1 , y i + 1 ) = P ( y i ∣ x , y i − 1 , y i + 1 ) ∗ P ( y 1 , ⋯   , y i − 2 , y i + 2 , ⋯   , y n ∣ x , y i − 1 , y i + 1 )

==​P(y1​,⋯,yi−2​,yi​,yi+2​,⋯,yn​∣x,yi−1​,yi+1​)P(yi​∣x,y1​,⋯,yi−1​,yi+1​,⋯,yn​)∗P(y1​,⋯,yi−2​,yi+2​,⋯,yn​∣x,yi−1​,yi+1​)P(yi​∣x,yi−1​,yi+1​)∗P(y1​,⋯,yi−2​,yi+2​,⋯,yn​∣x,yi−1​,yi+1​)​

然而问题的关键在于，怎么由这些条件概率分布表示联合概率分布。

后来我才明白，这个定义远远不够，甚至说还很弱小，要想用条件概率分布表示联合概率分布，需要深挖，没有耐心的可以直接看后面条件概率计算总结。

参考：

• Helge Langseth(Norwegian University of Science and Technology)：The Hammersley-Clifford Theorem and its Impact on Modern Statistics
• David Pollard(YALE)：Hammersley-Clifford theorem for Markov random fields
• WIKIPEDIA：Hammersley–Clifford theorem

Hammersley–Clifford 定理证明

证明这个定理分为两个部分，第一部分是证明任何一个Gibbs概率密度都满足马尔可夫性，另一部分是满足马尔可夫性的正概率密度一定是Gibbs概率密度。

Gibbs random field(GBF)一定满足马尔可夫性质。证明如下：

上面的图形用Gibbs随机场来表似联合概率分布就是：$P(A,B,C,D,E,F)\propto f_1(A,B,D)f_2(A,C,D)f_3(C,D,F)f_4(C,E,F)$

然后我们假设其中$C,D$是固定的，那么这个联合概率分布就是：$P(A,B,c,d,E,F)\propto f_1(A,B,d)f_2(A,c,d)f_3(c,d,F)f_4(c,E,F)$
条件概率分布为：$P(A,B,E,F|c,d)=\frac{P(A,B,c,d,E,F)}{P(c,d)}\propto f_1(A,B,d)f_2(A,c,d)f_3(c,d,F)f_4(c,E,F)=g_1(A,B)g_2(E,F)$
即：$P(A,B,E,F|c,d)\propto g_1(A,B)g_2(E,F)$
独立性满足。

每个满足局部马尔可夫性质的正概率分布也是Gibbs随机场。这个证明我还没看明白，改天再写。

峰回路转

就在此时，我灵光一闪，又找到了来时的路。我们从简单的角度出发，也就是从条件概率分布乘积形成联合概率分布的角度来看。
P ( A , B , C , D , E , F ) = P ( A ) ∗ P ( B ∣ A ) ∗ P ( D ∣ A , B ) ∗ P ( C ∣ A , B , D ) ∗ P ( F ∣ A , B , C , D ) ∗ P ( E ∣ A , B , C , D , F ) = P ( A ) ∗ P ( B ∣ A ) ∗ P ( D ∣ A , B ) ∗ P ( C ∣ A , D ) ∗ P ( F ∣ C , D ) ∗ P ( E ∣ C , F ) = P ( A , B , D ) ∗ P ( C ∣ A , D ) ∗ P ( F ∣ C , D ) ∗ P ( E ∣ C , F ) = f 1 ( A , B , D ) ∗ f 2 ( A , C , D ) ∗ f 3 ( F , C , D ) ∗ f 4 ( E , C , F )

P(A,B,C,D,E,F)====​P(A)∗P(B∣A)∗P(D∣A,B)∗P(C∣A,B,D)∗P(F∣A,B,C,D)∗P(E∣A,B,C,D,F)P(A)∗P(B∣A)∗P(D∣A,B)∗P(C∣A,D)∗P(F∣C,D)∗P(E∣C,F)P(A,B,D)∗P(C∣A,D)∗P(F∣C,D)∗P(E∣C,F)f1​(A,B,D)∗f2​(A,C,D)∗f3​(F,C,D)∗f4​(E,C,F)​

刚好是上面的图形中的四个$\text{最大团(maximal clique)}$的函数的乘积形式，为了确保里面的$f_1,f_2,f_3,f_4$都是正的概率密度函数，需要找一个一定为正的函数来替代他们，可以用指数函数，当然应该也可以用其他的为正的比如$x^2+1$，反正最后都是通过归一化使之成为一个合格的概率密度。
上面表达式中一些特殊的代换也需要解释一下，这与上面的条件概率分布的等式有关，严格来说，条件概率的等式应该是这个样子：
$$P(y_i|x,y_{i-1},y_{i+1})=P(y_i|x,y_{i-1},y_{i+1},y\ne y_i,\forall y)$$

也就是只要条件里面有相邻的点，其他的都可以被化简。
如果相邻的点没有全部在内呢？
P ( y i ∣ x , y i − 1 , y i − 2 ) ∗ P ( y i − 2 ∣ x , y i − 1 ) = P ( y i , y i − 2 ∣ x , y i − 1 ) P ( y i ∣ x , y i − 1 ) ∗ P ( y i − 2 ∣ x , y i − 1 ) =

P(yi​∣x,yi−1​,yi−2​)∗P(yi−2​∣x,yi−1​)=P(yi​∣x,yi−1​)∗P(yi−2​∣x,yi−1​)=​P(yi​,yi−2​∣x,yi−1​)​

所以就算条件里面没有包含所有的相邻点，依旧是可以直接化简为条件中有的相邻的点。说着有点绕，就是条件里面有相邻点，就可以直接消去不相邻的点。不管是不是全部相邻点都在。就是这一点导致我始终无法理解$\text{条件随机场（CRF）}$的表达式，到了这一步，就可以回答我们之前提出的问题-由条件概率分布表示联合概率分布。归根到底还是条件概率用的不熟，所以特意整理一下。

条件概率运算总结

条件概率从定义上来说运算就是贝耶斯公式，而从马尔可夫性这个特殊的语义环境下，条件概率还有不同的计算公式。因此下文分为基本计算和马尔可夫性计算两个方面介绍：

基本的条件概率公式

P ( A ∣ B ) = P ( A , B ) P ( B ) P ( C ∣ A , B ) ∗ P ( B ∣ A ) = P ( B , C ∣ A )

P(A∣B)=P(C∣A,B)∗P(B∣A)=​P(B)P(A,B)​P(B,C∣A)​

满足马尔可夫性的条件概率的公式

为了简单起见，我们研究有五个顶点构成的概率图模型，假设图如下所示：

我们分析每个顶点所对应的条件概率情况。

---

首先从$A$点开始。我们要分析$A$点所对应的所有条件概率，首先分析包含相邻点$B$的：
$$P(A|B)=P(A|B,C)=P(A|B,D)=P(A|B,E)=P(A|B,C,D)=P(A|B,C,E)=P(A|B,D,E)=P(A|B,C,D,E)$$

A点的条件概率一共有$B,C,D,E,BC,BD,BE,CD,CE,DE,BCD,BCE,BDE,CDE,BCDE$，一共有$C_4^1+C_4^2+C_4^3+C_4^4=4+6+4+1=15$个，我们上面只列出了含有相邻点$B$的$8$个，还有$7$个没有分析。不包含相邻点的条件概率稍后分析，先分析条件中包含相邻点的。

怎么证明呢？对于上述表达式中除了第一项$P(A|B)$外，其他各项我们都可以用类似的表达式证明：
$$P(A|B,\ast )=\frac{P(A,\ast |B)}{P(\ast |B)}=\frac{P(A|B)\times P(\ast |B)}{P(\ast |B)}$$

最后一个等式是由马尔可夫性得来的，马尔可夫性说明了他们之间是独立的。$A$和$\ast$被$B$分割了，所以他们之间的关系是条件独立的，也就有：
$$P(A,\ast |B)=P(A|B)\times P(\ast |B)$$

因此有$P(A|B,\ast )=P(A|B)$。

对于剩余的7个条件概率分布$P(A|C),P(A|D),P(A|E),P(A|C,D),P(A|C,E),P(A|D,E),P(A|C,D,E)$，就无法化简。因为无法从马尔可夫性中推断关系，从贝耶斯条件出发也无法对条件概率分布进行化简，所以无法化简。

---

对于顶点B来说，剩余的每个点都是它的相邻的点，但是相邻的点中有相互连接的，也有相互不连接的，用来分析马尔可夫条件下的条件概率分布最好不过了。不过图中没有它不连接的，所以依旧无法化简，换句话说，任何点集构成的条件都是B点的相邻点集，所以无法化简。不信我们验证一下：
$$P(B|C,A)=\frac{P(A,B|C)}{P(A|C)}$$

由于$A,B$并不是由$C$进行分割的，所以上面的条件概率无法判断出$A,B$是否独立，也就无法拆分为两项的乘积，所以无法化简。换句话说，$A,C$都是相邻点，所以无法进行删减。也就是对于条件中的相邻点一个也不能删。

---

对顶点$C$来说，$C$同样应该有$15$个条件概率，我们先对其中包含有相邻点的那些条件概率进行分析。相邻点包括$B,D,E$，我们分别讨论条件包含一个相邻，两个相邻，三个相邻这三种情况：

一个相邻：
$$P(C|B,A)=\frac{P(A,C|B)}{P(A|B)}=\frac{P(A|B)P(C|B)}{P(A|B)}=P(C|B)$$

上式是因为$A,C$被$B$分割了，所以根据马尔可夫性，上面的条件概率可被拆分。

两个相邻的：
$$P(C|B,D,A)=\frac{P(A,C|B,D)}{P(A|B,D)}=\frac{P(A|B,D)P(C|B,D)}{P(A|B,D)}$$

通过这个表达式我们发现，在化简条件概率表达式时，我们只需要考虑表达式中包含的那些元素之间的关系就可以。比如说上面的只有$A,B,C,D$，所以我们只用考虑$A,B,C,D$之间的网图就行了。

在这种情况下，符合马尔可夫性，$A,C$被$B,D$隔开。

不同相邻的点集：
然后我们分析一下不同相邻点集条件下的概率，$P(C|B)=\frac{P(B,C)}{P(B)}$与$P(C|D)=\frac{P(C,D)}{P(D)}$，无法根据马尔可夫性或贝耶斯公式进行化简。也就说明不足以说明他们相等。换句话说：包含不同相邻点集的条件概率是不等的。

三个相邻的：
$$P(C|B,D,E,A)=\frac{P(A,C|B,D,E)}{P(A|B,D,E)}=\frac{P(A|B,D,E)\ast P(C|B,D,E)}{P(A|B,D,E)}=P(C|B,D,E)$$

上述倒数第二个式子同样也是利用了马尔可夫性，$B,D,E$分割了$A,C$，所以可以拆分。

综上所述：
条件中有相邻点集的可以约分到只剩相邻的那些点，其余的不能约分。

应用

我们现在用上述条件概率的计算公式来证明一下本文的主题，怎么用条件概率分布求联合概率分布。
P ( A , B , C , D , E ) = P ( A ) ∗ P ( B ∣ A ) ∗ P ( C ∣ A , B ) ∗ P ( D ∣ A , B , C ) ∗ P ( E ∣ A , B , C , D ) = P ( A ) ∗ P ( B ∣ A ) ∗ P ( C ∣ B ) ∗ P ( D ∣ B , C ) ∗ P ( E ∣ B , C , D ) = P ( A , B ) ∗ P ( C ∣ B ) ∗ P ( D ∣ B , C ) ∗ P ( E ∣ B , C , D ) = P ( A , B ) ∗ P ( C , D , E ∣ B )

P(A,B,C,D,E)====​P(A)∗P(B∣A)∗P(C∣A,B)∗P(D∣A,B,C)∗P(E∣A,B,C,D)P(A)∗P(B∣A)∗P(C∣B)∗P(D∣B,C)∗P(E∣B,C,D)P(A,B)∗P(C∣B)∗P(D∣B,C)∗P(E∣B,C,D)P(A,B)∗P(C,D,E∣B)​

我们回顾一下上面的最大团。

最大团有：$(A,B),(B,C,D,E)$
刚好是两部分，并且每一部分的参数恰好对应，$f_1(A,B)\propto P(A,B),f_2(B,C,D,E)\propto P(C,D,E|B)$。
然后为了确保$f_1,f_2$是正的，我们取为
$$\begin{gathered} P(A,B)=\exp (f_1(A,B)) \\ P(C,D,E|B)=\exp (f_2(B,C,D,E)) \end{gathered}$$
然后带入上面计算联合概率分布的公式有：
$$P(A,B,C,D,E)=\exp (f_1(A,B))\ast \exp (f_2(B,C,D,E))=\exp (f_1(A,B)+f_2(B,C,D,E))$$