机器学习笔记之概率图模型——马尔可夫随机场
引言回顾:贝叶斯网络与条件独立性马尔可夫随机场与条件独立性全局马尔可夫性(Global Markov Property)局部马尔可夫性(Local Markov Property)成对马尔可夫性(Pairwise Markov Property)马尔可夫随机场的因子分解概念介绍:团、势函数关于马尔可夫随机场因子分解的证明马尔可夫毯引言
前面部分介绍了贝叶斯网络的结构表示以及贝叶斯网络相关的概率图模型。本节将介绍马尔可夫随机场(Markov Random Field)的结构表示(Representation)。
回顾:贝叶斯网络与条件独立性
基于贝叶斯网络(有向图),样本集合X\mathcal XX各维度信息的联合概率分布表示如下:
P(X)=(x1,⋯,xp)=∏i=1pP(xi∣xpa(i))\mathcal P(\mathcal X) = \mathcal (x_1,\cdots,x_p) = \prod _{i=1}^p \mathcal P(x_i \mid x_{pa(i)})P(X)=(x1,⋯,xp)=i=1∏pP(xi∣xpa(i))
其中xpa(i)x_{pa(i)}xpa(i)表示结点xix_ixi的父结点。基于该式,贝叶斯网络中包含三种变量之间的典型依赖关系:
详见‘贝叶斯网络的结构表示’一节
传送门
同父结构(Common Parent)顺序结构V\mathcal VV型结构(V-Structure)
实际上,可以通过使用有向分离(D\mathcal DD划分,D-Separation)更泛化地判断有向图中变量间的条件独立性。
详见‘贝叶斯网络之有向分离(D划分)’一节。
传送门
马尔可夫随机场与条件独立性
全局马尔可夫性(Global Markov Property)
马尔可夫随机场是一种无向图表示方法,相比于贝叶斯网络(有向图),由于没有箭头指向,因此无向图中变量之间的依赖关系使用一种方式即可表示:
对应数学符号表示如下:
i2⊥i3∣i1i_2 \perp i_3 \mid i_1i2⊥i3∣i1
在马尔可夫随机场中,变量之间条件独立性的判别同样可以使用类似D\mathcal DD划分的方式进行描述。不同于贝叶斯网络的D\mathcal DD划分,马尔可夫随机场中的“D\mathcal DD划分”被缩略为一条规则:
场景构建:
假设lal_ala是变量集合xAx_{\mathcal A}xA中的一个变量;lcl_clc是变量集合xCx_{\mathcal C}xC中的一个变量;变量lal_ala和lcl_clc之间存在一条路径,并且路径上至少存在一个非la,lcl_a,l_cla,lc变量构成的结点,并定义其为lb1,lb2,⋯l_{b_1},l_{b_2},\cdotslb1,lb2,⋯
如果变量lal_ala与变量lcl_clc之间相互独立,必然需要lb1,lb2,⋯l_{b_1},l_{b_2},\cdotslb1,lb2,⋯中至少存在一点位于变量集合xBx_{\mathcal B}xB中。如果存在结点lbkl_{b_k}lbk满足如下条件:
lbk∈{lb1,lb2,⋯}l_{b_k} \in \{l_{b_1},l_{b_2},\cdots\}lbk∈{lb1,lb2,⋯}lbk∈xBl_{b_k} \in x_{\mathcal B}lbk∈xB
此时,给定变量集合xBx_{\mathcal B}xB的结点信息,则有:
la⊥lc∣lbkl_a \perp l_c \mid l_{b_k}la⊥lc∣lbk
图像表示如下:
这种规则在无向图中也被称为全局马尔可夫性(Global Markov Property):给定两个变量子集的分离集,则两个变量子集相互独立。
也就是说,xAx_{\mathcal A}xA集合中的任意点与xCx_{\mathcal C}xC中的任意点之间如果存在路径,并且所有路径均满足上述情况,则xA⊥xC∣xBx_{\mathcal A}\perp x_{\mathcal C} \mid x_{\mathcal B}xA⊥xC∣xB。对应图像表示如下:
观察上图,任意一个由xAx_{\mathcal A}xA发射到xCx_{\mathcal C}xC的路径,均经过xBx_{\mathcal B}xB中的结点。
对应‘贝叶斯网络’,这里是‘马尔可夫随机场’对全局马尔可夫性的使用。
局部马尔可夫性(Local Markov Property)
示例:一个马尔可夫随机场表示如下:
观察i1i_1i1结点,与其直接相连的变量有三个,分别是i2,i3,i4i_2,i_3,i_4i2,i3,i4。如果给定i2,i3,i4i_2,i_3,i_4i2,i3,i4条件下,变量i1i_1i1将条件独立于i5,i6i_5,i_6i5,i6。
称变量i2,i3,i4i_2,i_3,i_4i2,i3,i4是变量i1i_1i1的邻接变量。局部马尔可夫性的具体概念如下:给定某变量的邻接变量,则该变量条件独立于图中除该变量及邻接变量的其他所有变量:
令V\mathcal VV表示图的结点集;令n(v)n(v)n(v)表示结点vvv的邻接结点构成的集合;
局部马尔可夫性的数学符号表达如下:
v⊥{V−v−n(v)}∣n(v)v \perp \{\mathcal V - v - n(v)\} \mid n(v)v⊥{V−v−n(v)}∣n(v)
上述示例的局部马尔可夫性表达为:
i1⊥{i5,i6}∣{i2,i3,i4}i_1 \perp \{i_5,i_6\} \mid \{i_2,i_3,i_4\}i1⊥{i5,i6}∣{i2,i3,i4}
成对马尔可夫性(Pairwise Markov Property)
依然使用上述马尔可夫随机场为例,其中结点i1,i6i_1,i_6i1,i6是两个非邻接变量。如果给定除去i1,i6i_1,i_6i1,i6之外的其他变量结点,则变量i1,i6i_1,i_6i1,i6之间条件独立:
成对马尔可夫性的具体概念如下:给定图中除两个非邻接变量的其他所有变量,这两个非邻接变量条件独立:
令图中结点集为V\mathcal VV,边集为E\mathcal EE;x−i−jx_{-i-j}x−i−j表示图中除去xi,xjx_i,x_jxi,xj的其他所有结点;<xi,xj><x_i,x_j><xi,xj>表示结点xi,xjx_i,x_jxi,xj之间的边;
局部马尔可夫性的数学符号表示如下:
xi⊥xj∣x−i−jbased<xi,xj>∉Ex_i \perp x_j \mid x_{-i-j} \quad based <x_i,x_j> \notin \mathcal Exi⊥xj∣x−i−jbased<xi,xj>∈/E
综上,马尔可夫随机场的条件独立性体现为三个方面:全局、局部、成对马尔可夫性。并且这三种性质相互等价。
马尔可夫随机场的因子分解
回顾贝叶斯网络的因子分解:
由于是有向边,可以通过拓扑排序的方式直接找到结点之间的关联关系:
i0,i2i_0,i_2i0,i2的入度为零,因此在表示条件概率时,只能在’|'的后面。如:
P(i1∣i0),P(i3∣i2)\mathcal P(i_1 \mid i_0),\mathcal P(i_3 \mid i_2)P(i1∣i0),P(i3∣i2)同理,所有结点基于出度与入度的关系,对应表示为P(\mathcal P(P(入度∣\mid∣出度))):
P(i3∣i1,i2),P(i4∣i3)\mathcal P(i_3 \mid i_1,i_2),\mathcal P(i_4 \mid i_3)P(i3∣i1,i2),P(i4∣i3)因此,上述贝叶斯网络中结点的联合概率分布表示如下:
P(i0,i1,i2,i3,i4)=∏i=1pP(ik∣ipa(k))=P(i1∣i0)⋅P(i3∣i1,i2)⋅P(i4∣i3)\begin{aligned} \mathcal P(i_0,i_1,i_2,i_3,i_4) & = \prod_{i=1}^p \mathcal P(i_k \mid i_{pa(k)})\\ & = \mathcal P(i_1 \mid i_0) \cdot \mathcal P(i_3 \mid i_1,i_2) \cdot \mathcal P(i_4 \mid i_3) \end{aligned}P(i0,i1,i2,i3,i4)=i=1∏pP(ik∣ipa(k))=P(i1∣i0)⋅P(i3∣i1,i2)⋅P(i4∣i3)
由于马尔可夫随机场对应概率图是无向图,结点之间的边只能表示结点之间存在相关性,而不能表示结点之间显式的因果关系。
如何使用因子分解表示马尔可夫随机场的条件独立性?
概念介绍:团、势函数
团本身是关于结点的集合,其定义表示如下:对于图中结点的一个子集,若该子集内部任意两结点之间都有边连接,则称该结点子集是一个团(Clique)。
已知一个马尔可夫随机场表示如下:
根据团的定义,上述示例中可以找到如下几种团:
{i0,i1},{i1,i2,i3},{i1,i2},{i2,i3},{i1,i3},{i3,i4}\{i_0,i_1\},\{i_1,i_2,i_3\},\{i_1,i_2\},\{i_2,i_3\},\{i_1,i_3\},\{i_3,i_4\}{i0,i1},{i1,i2,i3},{i1,i2},{i2,i3},{i1,i3},{i3,i4}
而极大团(Maximal Clique)表示:在一个团中加入任意一个结点后都不再形成团,称该团为极大团。
如上述团{i0,i1}\{i_0,i_1\}{i0,i1},如果加入i2i_2i2,由于i0,i2i_0,i_2i0,i2之间没有边,因此无法构成团。因此{i0,i1}\{i_0,i_1\}{i0,i1}是极大团;
同理,{i1,i2,i3},{i3,i4}\{i_1,i_2,i_3\},\{i_3,i_4\}{i1,i2,i3},{i3,i4}都是极大团。
使用团表示马尔可夫随机场中结点的联合概率分布:
场景构建:
假设数据集合X\mathcal XX共包含ppp个特征/变量:
X=(x1,x2,⋯,xp)T\mathcal X = \left(x_1,x_2,\cdots,x_p\right)^TX=(x1,x2,⋯,xp)T这ppp个特征所构成的马尔可夫随机场中,将结点划分成若干个团。假设划分出团的数量为K\mathcal KK,将划分出的团进行如下表示:
xC1,xC2,⋯,xCKx_{\mathcal C_1},x_{\mathcal C_2},\cdots,x_{\mathcal C_{\mathcal K}}xC1,xC2,⋯,xCK
将联合概率分布P(X)\mathcal P(\mathcal X)P(X)表示如下:
P(X)=1Z∏i=1Kψ(xCi)\mathcal P(\mathcal X) = \frac{1}{\mathcal Z} \prod_{i=1}^{\mathcal K} \psi(x_{\mathcal C_i})P(X)=Z1i=1∏Kψ(xCi)
称ψ(xCi)(i=1,2,⋯,K)\psi(x_{\mathcal C_i})(i=1,2,\cdots,\mathcal K)ψ(xCi)(i=1,2,⋯,K)为团xCix_{\mathcal C_i}xCi的势函数(Potential Functions),也称因子(Factor),它是一个非负实函数;它用来定义团xCix_{\mathcal C_i}xCi的概率分布函数。Z\mathcal ZZ被称为规范化因子,具体表示如下:
注意,这里的
xxx是指变量维度 ->
(x1,⋯,xp)(x_1,\cdots,x_p)(x1,⋯,xp)
Z=∑x∏i=1Kψ(xCi)=∑x1,⋯,xp∏i=1Kψ(xCi)\begin{aligned} \mathcal Z & = \sum_{x} \prod_{i=1}^{\mathcal K} \psi(x_{\mathcal C_i}) \\ & = \sum_{x_1,\cdots,x_p}\prod_{i=1}^{\mathcal K} \psi(x_{\mathcal C_i}) \end{aligned}Z=x∑i=1∏Kψ(xCi)=x1,⋯,xp∑i=1∏Kψ(xCi)
规范化因子的作用即确保P(X)\mathcal P(\mathcal X)P(X)是正确的概率结果。
关于马尔可夫随机场因子分解的证明
这里介绍西瓜书中的证明过程。
既然通过势函数ψ(xCi)(i=1,2,⋯,K)\psi(x_{\mathcal C_i})(i=1,2,\cdots,\mathcal K)ψ(xCi)(i=1,2,⋯,K)将联合概率分布P(X)\mathcal P(\mathcal X)P(X)分解称如下形式:
P(X)=1Z∏i=1Kψ(xCi)\mathcal P(\mathcal X) = \frac{1}{\mathcal Z} \prod_{i=1}^{\mathcal K}\psi(x_{\mathcal C_i})P(X)=Z1i=1∏Kψ(xCi)
基于该公式,我们需要证明:xCi(i=1,2,⋯,K)x_{\mathcal C_i}(i=1,2,\cdots,\mathcal K)xCi(i=1,2,⋯,K)的条件独立性。
基于全局马尔可夫性,马尔可夫随机场的结点结构是单一的,假设三个团xC1,xC2,xC3x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3}xC1,xC2,xC3结构表示如下:
只需要证明:给定团xC2x_{\mathcal C_2}xC2的条件下,团xC1x_{\mathcal C_1}xC1和团xC3x_{\mathcal C_3}xC3条件独立即可。即:
P(xC1,xC3∣xC2)=P(xC1∣xC2)⋅P(xC3∣xC2)\mathcal P(x_{\mathcal C_1},x_{\mathcal C_3} \mid x_{\mathcal C_2}) = \mathcal P(x_{\mathcal C_1} \mid x_{\mathcal C_2}) \cdot \mathcal P(x_{\mathcal C_3} \mid x_{\mathcal C_2})P(xC1,xC3∣xC2)=P(xC1∣xC2)⋅P(xC3∣xC2)
等式左侧:
利用条件概率公式和概率的加法公式(积分运算),将P(xC1,xC3∣xC2)\mathcal P(x_{\mathcal C_1},x_{\mathcal C_3}\mid x_{\mathcal C_2})P(xC1,xC3∣xC2)表示为如下形式:
P(xC1,xC3∣xC2)=P(xC1,xC2,xC3)P(xC2)=P(xC1,xC2,xC3)∑xC1,xC3P(xC1,xC2,xC3)\begin{aligned} \mathcal P(x_{\mathcal C_1},x_{\mathcal C_3}\mid x_{\mathcal C_2}) & = \frac{\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3})}{\mathcal P(x_{\mathcal C_2})} \\ & = \frac{\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3})}{\sum_{x_{\mathcal C_1},x_{\mathcal C_3}}\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3})} \end{aligned}P(xC1,xC3∣xC2)=P(xC2)P(xC1,xC2,xC3)=∑xC1,xC3P(xC1,xC2,xC3)P(xC1,xC2,xC3)观察上图,可以将上述三个团看成三个结点,上图中的三个结点构成了两个更大的团:{xC1,xC2},{xC2,xC3}\{x_{\mathcal C_1},x_{\mathcal C_2}\},\{x_{\mathcal C_2},x_{\mathcal C_3}\}{xC1,xC2},{xC2,xC3}。并分别定义对应的势函数为ψC1C2(xC1,xC2),ψC2C3(xC2,xC3)\psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}),\psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})ψC1C2(xC1,xC2),ψC2C3(xC2,xC3)。利用势函数将联合概率分布进行展开:
规范化因子
Z\mathcal ZZ消掉了。
P(xC1,xC2,xC3)=1Z∏i=1Kψ(xCi)=1Z⋅ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)P(xC1,xC3∣xC2)=1Z⋅ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)∑xC1,xC31Z⋅ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)=ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)∑xC1,xC3ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)\begin{aligned} \mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3}) & = \frac{1}{\mathcal Z} \prod_{i=1}^{\mathcal K}\psi(x_{\mathcal C_i})\\ & = \frac{1}{\mathcal Z} \cdot \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3}) \\ \mathcal P(x_{\mathcal C_1},x_{\mathcal C_3}\mid x_{\mathcal C_2}) & = \frac{\frac{1}{\mathcal Z} \cdot \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})} {\sum_{x_{\mathcal C_1},x_{\mathcal C_3}} \frac{1}{\mathcal Z}\cdot \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})} \\ & = \frac{\psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})} {\sum_{x_{\mathcal C_1},x_{\mathcal C_3}} \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})} \end{aligned}P(xC1,xC2,xC3)P(xC1,xC3∣xC2)=Z1i=1∏Kψ(xCi)=Z1⋅ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)=∑xC1,xC3Z1⋅ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)Z1⋅ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)=∑xC1,xC3ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)又因为团xC1x_{\mathcal C_1}xC1和团xC3x_{\mathcal C_3}xC3之间的结点不相交。因此,分母可表示为如下形式:
∑xC1,xC3ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)=∑xC1ψC1C2(xC1,xC2)⋅∑xC3ψC2C3(xC2,xC3)\sum_{x_{\mathcal C_1},x_{\mathcal C_3}} \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3}) = \sum_{x_{\mathcal C_1}} \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \sum_{x_{\mathcal C_3}} \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3}) xC1,xC3∑ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)=xC1∑ψC1C2(xC1,xC2)⋅xC3∑ψC2C3(xC2,xC3)最终,P(xC1,xC3∣xC2)\mathcal P(x_{\mathcal C_1},x_{\mathcal C_3}\mid x_{\mathcal C_2})P(xC1,xC3∣xC2)可表示为如下形式:
P(xC1,xC3∣xC2)=ψC1C2(xC1,xC2)∑xC1ψC1C2(xC1,xC2)⋅ψC2C3(xC2,xC3)∑xC3ψC2C3(xC2,xC3)\mathcal P(x_{\mathcal C_1},x_{\mathcal C_3}\mid x_{\mathcal C_2}) = \frac{\psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2})}{\sum_{x_{\mathcal C_1}} \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2})} \cdot \frac{\psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})}{\sum_{x_{\mathcal C_3}} \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})}P(xC1,xC3∣xC2)=∑xC1ψC1C2(xC1,xC2)ψC1C2(xC1,xC2)⋅∑xC3ψC2C3(xC2,xC3)ψC2C3(xC2,xC3)
等式右侧:首先观察P(xC1∣xC2)\mathcal P(x_{\mathcal C_1} \mid x_{\mathcal C_2})P(xC1∣xC2)。和等式左侧展开方式相似,但需要对分子、分母均执行积分运算:
P(xC1∣xC2)=P(xC1,xC2)P(xC2)=∑xC3P(xC1,xC2,xC3)∑xC1,xC3P(xC1,xC2,xC3)\begin{aligned} \mathcal P(x_{\mathcal C_1} \mid x_{\mathcal C_2}) & = \frac{\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2})}{\mathcal P(x_{\mathcal C_2})} \\ & = \frac{\sum_{x_{\mathcal C_3}}\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3})}{\sum_{x_{\mathcal C_1},x_{\mathcal C_3}}\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3})} \end{aligned}P(xC1∣xC2)=P(xC2)P(xC1,xC2)=∑xC1,xC3P(xC1,xC2,xC3)∑xC3P(xC1,xC2,xC3)
使用势函数对联合概率分布P(xC1,xC2,xC3)\mathcal P(x_{\mathcal C_1},x_{\mathcal C_2},x_{\mathcal C_3})P(xC1,xC2,xC3)进行展开:
Z,∑xC3ψC1C3(xC1,xC3)\mathcal Z,\sum_{x_{\mathcal C_3}} \psi_{\mathcal C_1\mathcal C_3}(x_{\mathcal C_1},x_{\mathcal C_3})Z,∑xC3ψC1C3(xC1,xC3)被消掉。
P(xC1∣xC2)=1ZψC1C2(xC1,xC2)⋅∑xC3ψC1C3(xC1,xC3)1Z∑xC1ψC1C2(xC1,xC2)⋅∑xC3ψC1C3(xC1,xC3)=ψC1C2(xC1,xC2)∑xC1ψC1C2(xC1,xC2)\begin{aligned} \mathcal P(x_{\mathcal C_1} \mid x_{\mathcal C_2}) & = \frac{\frac{1}{\mathcal Z}\psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \sum_{x_{\mathcal C_3}}\psi_{\mathcal C_1\mathcal C_3}(x_{\mathcal C_1},x_{\mathcal C_3})}{\frac{1}{\mathcal Z}\sum_{x_{\mathcal C_1}} \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2}) \cdot \sum_{x_{\mathcal C_3}} \psi_{\mathcal C_1\mathcal C_3}(x_{\mathcal C_1},x_{\mathcal C_3})} \\ & = \frac{\psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2})}{\sum_{x_{\mathcal C_1}} \psi_{\mathcal C_1\mathcal C_2}(x_{\mathcal C_1},x_{\mathcal C_2})} \end{aligned}P(xC1∣xC2)=Z1∑xC1ψC1C2(xC1,xC2)⋅∑xC3ψC1C3(xC1,xC3)Z1ψC1C2(xC1,xC2)⋅∑xC3ψC1C3(xC1,xC3)=∑xC1ψC1C2(xC1,xC2)ψC1C2(xC1,xC2)
同理,P(xC3∣xC2)\mathcal P(x_{\mathcal C_3} \mid x_{\mathcal C_2})P(xC3∣xC2)和P(xC1∣xC2)\mathcal P(x_{\mathcal C_1} \mid x_{\mathcal C_2})P(xC1∣xC2)存在相同的展开方式,对应结果表示如下:
P(xC3∣xC2)=ψC2C3(xC2,xC3)∑xC3ψC2C3(xC2,xC3)\mathcal P(x_{\mathcal C_3} \mid x_{\mathcal C_2}) = \frac{\psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})}{\sum_{x_{\mathcal C_3}} \psi_{\mathcal C_2\mathcal C_3}(x_{\mathcal C_2},x_{\mathcal C_3})}P(xC3∣xC2)=∑xC3ψC2C3(xC2,xC3)ψC2C3(xC2,xC3)
至此,等式左侧 = 等式右侧,证毕。
至此,可证明势函数对联合概率分布的表达可以表示团之间的条件独立性。
势函数的本质 -> 在介绍完‘玻尔兹曼机’时再回顾介绍。
马尔可夫毯
马尔可夫毯(Markov Blanket)是一个由结点组成的集合。在马尔可夫随机场中表示为:某变量的所有邻接变量组成的集合。
马尔可夫毯的性质在局部马尔可夫性中得到了描述:如果给定某变量的马尔可夫毯,无向图中除去该变量及对应马尔可夫毯之外的所有变量与该变量条件独立。
马尔可夫毯的这种性质,可以将其视为一种屏障:只要该屏障被给定,意味着马尔可夫毯所包围的结点与马尔可夫毯外的其他结点相互独立。
但实际上,马尔可夫毯并不是马尔可夫随机场中特有的描述,在贝叶斯网络中,同样存在马尔可夫毯。
以某贝叶斯网络的结点xix_ixi为例,假设该贝叶斯网络中一共包含ppp个结点(对应数据集合X\mathcal XX的ppp个特征变量),结点xix_ixi的条件概率表示如下:
这里为了简化起见,使用
x−ix_{-i}x−i替代。即除去
xix_ixi的其他结点。
P(xi∣x1,⋯,xi−1,xi+1,⋯,xp)=P(xi∣x−i)\mathcal P(x_i \mid x_1,\cdots,x_{i-1},x_{i+1},\cdots,x_p) = \mathcal P(x_i \mid x_{-i})P(xi∣x1,⋯,xi−1,xi+1,⋯,xp)=P(xi∣x−i)
我们将其展开:
xix_ixi设为‘离散型随机变量’,因此,它的积分形式是
∑xi\sum_{x_i}∑xi
P(xi∣x−i)=P(xi,x−i)P(x−i)=P(X)∑xiP(X)\begin{aligned} \mathcal P(x_i \mid x_{-i}) & = \frac{\mathcal P(x_i,x_{-i})}{\mathcal P(x_{-i})} \\ & = \frac{\mathcal P(\mathcal X)}{\sum_{x_i} \mathcal P(\mathcal X)} \end{aligned}P(xi∣x−i)=P(x−i)P(xi,x−i)=∑xiP(X)P(X)
将贝叶斯网络因子分解公式代入上式:
P(xi∣x−i)=∏j=1pP(xj∣xpa(j))∑xi∏j=1pP(xj∣xpa(j))\begin{aligned} \mathcal P(x_i \mid x_{-i}) & = \frac{\prod_{j=1}^p \mathcal P(x_j \mid x_{pa(j)})}{\sum_{x_i} \prod_{j=1}^p \mathcal P(x_j \mid x_{pa(j)})} \end{aligned}P(xi∣x−i)=∑xi∏j=1pP(xj∣xpa(j))∏j=1pP(xj∣xpa(j))
观察分母,它的积分只限制xix_ixi相关的结点,与xix_ixi无关的结点都可视作常数,并与分子中的xix_ixi无关结果消掉:
假设与xix_ixi相关的结点集合为Δ\DeltaΔ,则有:
P(xi∣x−i)=∏j∉ΔP(xj∣xpa(j))⋅∏j∈ΔP(xj∣xpa(j))∏j∉ΔP(xj∣xpa(j))⋅∑xi∏j∈ΔP(xj∣xpa(j))=∏j∈ΔP(xj∣xpa(j))∑xi∏j∈ΔP(xj∣xpa(j))\begin{aligned} \mathcal P(x_i \mid x_{-i}) & = \frac{\prod_{j \notin \Delta} \mathcal P(x_j \mid x_{pa(j)}) \cdot \prod_{j \in \Delta} \mathcal P(x_j \mid x_{pa(j)})}{\prod_{j \notin \Delta} \mathcal P(x_j \mid x_{pa(j)}) \cdot \sum_{x_i} \prod_{j \in \Delta} \mathcal P(x_j \mid x_{pa(j)})} \\ & = \frac{\prod_{j \in \Delta} \mathcal P(x_j \mid x_{pa(j)})}{\sum_{x_i} \prod_{j \in \Delta} \mathcal P(x_j \mid x_{pa(j)})} \end{aligned}P(xi∣x−i)=∏j∈/ΔP(xj∣xpa(j))⋅∑xi∏j∈ΔP(xj∣xpa(j))∏j∈/ΔP(xj∣xpa(j))⋅∏j∈ΔP(xj∣xpa(j))=∑xi∏j∈ΔP(xj∣xpa(j))∏j∈ΔP(xj∣xpa(j))
至此,在求解xix_ixi变量的条件概率时,将范围从特征集合中的所有结点缩小到与xix_ixi相关的若干结点。
我们要判定哪些结点是否与xix_ixi存在关联?
xix_ixi作为子节点,存在结点作为父结点指向xix_ixi;
P(xj=xi∣xpa(j))\mathcal P(x_j = x_i \mid x_{pa(j)})P(xj=xi∣xpa(j))xix_ixi作为父结点,存在结点使得xix_ixi作为父结点指向该节点;
P(xj∣xpa(j)=xi)\mathcal P(x_j \mid x_{pa(j)} = x_i)P(xj∣xpa(j)=xi)贝叶斯网络的V\mathcal VV型结构中,xix_ixi的子结点给定的条件下,xix_ixi结点与另外的父结点xkx_kxk之间存在关联关系;
P(xj∣xpa(j)=xi,xk)\mathcal P(x_j \mid x_{pa(j)} = x_i,x_k)P(xj∣xpa(j)=xi,xk)
至此,贝叶斯网络中,某结点xix_ixi的马尔可夫毯表示如下:
该图只是一个子图,延伸的部分略。
通过观察发现,贝叶斯网络的马尔可夫毯和马尔可夫随机场的存在一定区别:i5,i6i_5,i_6i5,i6和i1i_1i1之间没有边相连接。
但如果将上述图像转化为道德图,观察转化结果:
观察发现,转换成道德图中,i0,i2,i3,i4,i5,i6i_0,i_2,i_3,i_4,i_5,i_6i0,i2,i3,i4,i5,i6都与i1i_1i1组成了临接变量关系。
下一节将介绍推断(Inference)。
相关参考:
机器学习-周志华著
机器学习-概率图模型3-贝叶斯网络-Representation-D-Separation
机器学习-概率图模型5-马尔可夫随机场-Representation-条件独立性