当前位置:   article > 正文

机器学习笔记之概率图模型(五)马尔可夫随机场的结构表示_马尔科夫随机场

马尔科夫随机场

引言

前面部分介绍了贝叶斯网络的结构表示以及贝叶斯网络相关的概率图模型。本节将介绍马尔可夫随机场(Markov Random Field)的 结构表示(Representation)。

回顾:贝叶斯网络与条件独立性

基于贝叶斯网络(有向图),样本集合 X \mathcal X X各维度信息的联合概率分布 表示如下:
P ( X ) = ( x 1 , ⋯   , x p ) = ∏ i = 1 p P ( x i ∣ x p a ( 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=1pP(xixpa(i))
其中 x p a ( i ) x_{pa(i)} xpa(i)表示结点 x i x_i xi父结点。基于该式,贝叶斯网络中包含 三种变量之间的典型依赖关系
详见‘贝叶斯网络的结构表示’一节传送门

  • 同父结构(Common Parent)
  • 顺序结构
  • V \mathcal V V型结构(V-Structure)

实际上,可以通过使用有向分离( D \mathcal D D划分,D-Separation)更泛化地判断有向图中变量间的条件独立性
详见‘贝叶斯网络之有向分离(D划分)’一节。传送门

马尔可夫随机场与条件独立性

全局马尔可夫性(Global Markov Property)

马尔可夫随机场是一种无向图表示方法,相比于贝叶斯网络(有向图),由于没有箭头指向,因此无向图中变量之间的依赖关系 使用一种方式即可表示:
无向图-变量之间的依赖关系
对应数学符号表示如下:
i 2 ⊥ i 3 ∣ i 1 i_2 \perp i_3 \mid i_1 i2i3i1

马尔可夫随机场中,变量之间条件独立性的判别 同样可以使用 类似 D \mathcal D D划分的方式 进行描述。不同于贝叶斯网络的 D \mathcal D D划分马尔可夫随机场中的“ D \mathcal D D划分”被缩略为一条规则

场景构建

  • 假设 l a l_a la变量集合 x A x_{\mathcal A} xA中的一个变量
  • l c l_c lc变量集合 x C x_{\mathcal C} xC中的一个变量
  • 变量 l a l_a la l c l_c lc之间存在一条路径,并且路径上至少存在一个非 l a , l c l_a,l_c la,lc变量构成的结点,并定义其为 l b 1 , l b 2 , ⋯ l_{b_1},l_{b_2},\cdots lb1,lb2,

如果变量 l a l_a la变量 l c l_c lc之间相互独立,必然需要 l b 1 , l b 2 , ⋯ l_{b_1},l_{b_2},\cdots lb1,lb2,至少存在一点位于变量集合 x B x_{\mathcal B} xB。如果存在结点 l b k l_{b_k} lbk满足如下条件

  • l b k ∈ { l b 1 , l b 2 , ⋯   } l_{b_k} \in \{l_{b_1},l_{b_2},\cdots\} lbk{ lb1,lb2,}
  • l b k ∈ x B l_{b_k} \in x_{\mathcal B} lbkxB

此时,给定变量集合 x B x_{\mathcal B} xB的结点信息,则有:
l a ⊥ l c ∣ l b k l_a \perp l_c \mid l_{b_k} lalclbk
图像表示如下:
无向图的D划分规则
这种规则在无向图中也被称为全局马尔可夫性(Global Markov Property):给定两个变量子集的分离集,则两个变量子集相互独立
也就是说, x A x_{\mathcal A} xA集合中的任意点 x C x_{\mathcal C} xC中的任意点之间如果存在路径,并且所有路径均满足上述情况,则 x A ⊥ x C ∣ x B x_{\mathcal A}\perp x_{\mathcal C} \mid x_{\mathcal B} xAxCxB。对应图像表示如下
结点集A和C被结点集B分离
观察上图,任意一个由 x A x_{\mathcal A} xA发射到 x C x_{\mathcal C} xC的路径,均经过 x B x_{\mathcal B} xB中的结点
对应‘贝叶斯网络’,这里是‘马尔可夫随机场’对全局马尔可夫性的使用。

局部马尔可夫性(Local Markov Property)

示例:一个马尔可夫随机场表示如下:
马尔可夫随机场示例

观察 i 1 i_1 i1结点,与其直接相连变量有三个,分别是 i 2 , i 3 , i 4 i_2,i_3,i_4 i2,i3,i4。如果 给定 i 2 , i 3 , i 4 i_2,i_3,i_4 i2,i3,i4条件下,变量 i 1 i_1 i1将条件独立于 i 5 , i 6 i_5,i_6 i5,i6

变量 i 2 , i 3 , i 4 i_2,i_3,i_4 i2,i3,i4变量 i 1 i_1 i1邻接变量局部马尔可夫性的具体概念如下:给定某变量的邻接变量,则该变量条件独立于图中除该变量及邻接变量的其他所有变量

  • V \mathcal V V表示图的结点集
  • n ( v ) n(v) n(v)表示结点 v v v邻接结点构成的集合

局部马尔可夫性的数学符号表达如下:
v ⊥ { V − v − n ( v ) } ∣ n ( v ) v \perp \{\mathcal V - v - n(v)\} \mid n(v) v{ Vvn(v)}n(v)
上述示例的局部马尔可夫性表达为:
i 1 ⊥ { i 5 , i 6 } ∣ { i 2 , i 3 , i 4 } i_1 \perp \{i_5,i_6\} \mid \{i_2,i_3,i_4\} i1{ i5,i6}{ i2,i3,i4}

成对马尔可夫性(Pairwise Markov Property)

依然使用上述马尔可夫随机场为例,其中结点 i 1 , i 6 i_1,i_6 i1,i6是两个非邻接变量。如果 给定除去 i 1 , i 6 i_1,i_6 i1,i6之外的其他变量结点,则变量 i 1 , i 6 i_1,i_6 i1,i6之间条件独立
马尔可夫随机场-成对马尔可夫性示例
成对马尔可夫性的具体概念如下:给定图中除两个非邻接变量的其他所有变量,这两个非邻接变量条件独立

  • 令图中结点集 V \mathcal V V边集 E \mathcal E E;
  • x − i − j x_{-i-j} xij表示图中除去 x i , x j x_i,x_j xi,xj的其他所有结点
  • < x i , x j > <x_i,x_j> <xi,xj>表示结点 x i , x j x_i,x_j xi,xj之间的边

局部马尔可夫性的数学符号表示如下:
x i ⊥ x j ∣ x − i − j b a s e d < x i , x j > ∉ E x_i \perp x_j \mid x_{-i-j} \quad based <x_i,x_j> \notin \mathcal E xixjxijbased<xi,xj>/E

综上,马尔可夫随机场的条件独立性体现为三个方面全局、局部、成对马尔可夫性。并且这三种性质相互等价

马尔可夫随机场的因子分解

回顾贝叶斯网络的因子分解:
贝叶斯网络-因子分解示例
由于是有向边,可以通过拓扑排序的方式直接找到结点之间的关联关系

  • i 0 , i 2 i_0,i_2 i0,i2入度为零,因此在表示条件概率时,只能在’|'的后面。如:
    P ( i 1 ∣ i 0 ) , P ( i 3 ∣ i 2 ) \mathcal P(i_1 \mid i_0),\mathcal P(i_3 \mid i_2) P(i1i0),P(i3i2)
  • 同理,所有结点基于出度与入度的关系,对应表示为 P ( \mathcal P( P(入度 ∣ \mid 出度 ) ) )
    P ( i 3 ∣ i 1 , i 2 ) , P ( i 4 ∣ i 3 ) \mathcal P(i_3 \mid i_1,i_2),\mathcal P(i_4 \mid i_3) P(i3i1,i2),P(i4i3)
  • 因此,上述贝叶斯网络中结点的联合概率分布表示如下:
    P ( i 0 , i 1 , i 2 , i 3 , i 4 ) = ∏ i = 1 p P ( i k ∣ i p a ( k ) ) = P ( i 1 ∣ i 0 ) ⋅ P ( i 3 ∣ i 1 , i 2 ) ⋅ P ( i 4 ∣ i 3 ) P(i0,i1,i2,i3,i4)=pi=1P(ikipa(k))=P(i1i0)P(i3i1,i2)P(i4i3) P(i0,i1,i2,i3,i4)=i=1pP(ikipa(k))=P(i1i0)P(i3i1,i2)P(i4i3)

由于马尔可夫随机场对应概率图是无向图,结点之间的边只能表示结点之间存在相关性,而不能表示结点之间显式的因果关系

如何使用因子分解表示马尔可夫随机场的条件独立性

概念介绍:团、势函数

本身是关于结点的集合,其定义表示如下:对于图中结点的一个子集,若该子集内部任意两结点之间都有边连接,则称该结点子集是一个团(Clique)。
已知一个马尔可夫随机场表示如下:
马尔可夫随机场示例-团
根据团的定义,上述示例中可以找到如下几种团:
{ 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 } \{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\} { i

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/1019988
推荐阅读
相关标签
  

闽ICP备14008679号