D-Separation(D-分离)

  |   0 评论   |   269 浏览

D-Separation是一种用来判断变量是否条件独立的图形化方法。换言之,对于一个DAG(有向无环图)E,D-Separation方法可以快速的判断出两个节点之间是否是条件独立的。

1.1 形式1:head-to-head

贝叶斯网络的第一种结构形式如下图所示:

4d8c2e145ea34af29f72950db7b74bd0-image.png

所以有:P(a,b,c) = P(a)*P(b)*P(c|a,b)成立,化简后可得:

4788bcaa2fa4429886f4df74f80671b2-image.png

即在c未知的条件下,a、b被阻断(blocked),是独立的,称之为head-to-head条件独立,对应本节中最开始那张图中的“x1、x2独立”。

1.2 形式2:tail-to-tail

贝叶斯网络的第二种结构形式如下图所示

4b66bd2b75d64e15bc680ace3375deed-image.png

考虑c未知,跟c已知这两种情况:

  1. 在c未知的时候,有:P(a,b,c)=P(c)*P(a|c)*P(b|c),此时,没法得出P(a,b) = P(a)P(b),即c未知时,a、b不独立。
  2. 在c已知的时候,有:P(a,b|c)=P(a,b,c)/P(c),然后将P(a,b,c)=P(c)*P(a|c)*P(b|c)带入式子中,得到:P(a,b|c)=P(a,b,c)/P(c) = P(c)*P(a|c)*P(b|c) / P(c) = P(a|c)*P(b|c),即c已知时,a、b独立。

所以,在c给定的条件下,a,b被阻断(blocked),是独立的,称之为tail-to-tail条件独立,对应本节中最开始那张图中的“x6和x7在x4给定的条件下独立”。

b96f64fbcee046cb8e8551285f5f284e-image.png

1.3 形式3:head-to-tail

贝叶斯网络的第三种结构形式如下图所示:

09c9c54f39004683b7a4e50716329af3-image.png

还是分c未知跟c已知这两种情况:

  1. c未知时,有:P(a,b,c)=P(a)*P(c|a)*P(b|c),但无法推出P(a,b) = P(a)P(b),即c未知时,a、b不独立。
  2. c已知时,有:P(a,b|c)=P(a,b,c)/P(c),且根据P(a,c) = P(a)*P(c|a) = P(c)*P(a|c),可化简得到:

b9381a30e7924d36b3d14f8e79671274-image.png

所以,在c给定的条件下,a,b被阻断(blocked),是独立的,称之为head-to-tail条件独立。

358e47e4465544f2921c8bbdd2fcb2d2-image.png

插一句:这个head-to-tail其实就是一个链式网络,如下图所示:
b097ff2dc92c4cdea720e7fbd4db9b99-image.png

根据之前对head-to-tail的讲解,我们已经知道,在xi给定的条件下,xi+1的分布和x1,x2…xi-1条件独立。意味着啥呢?意味着:xi+1的分布状态只和xi有关,和其他变量条件独立。通俗点说,当前状态只跟上一状态有关,跟上上或上上之前的状态无关。这种顺次演变的随机过程,就叫做马尔科夫链(Markov chain)。且有:

cd999ebe6de54f79b4dd326e5a0dec24-image.png

接着,将上述结点推广到结点集,则是:对于任意的结点集A,B,C,考察所有通过A中任意结点到B中任意结点的路径,若要求A,B条件独立,则需要所有的路径都被阻断(blocked),即满足下列两个前提之一:

  1. A和B的“head-to-tail型”和“tail-to-tail型”路径都通过C;
  2. A和B的“head-to-head型”路径不通过C以及C的子孙;

最后,举例说明上述D-Separation的3种情况(即贝叶斯网络的3种结构形式),则是如下图所示:

上图中左边部分是head-to-tail,给定 T 时,A 和 X 独立;右边部分的右上角是tail-to-tail,给定S时,L和B独立;右边部分的右下角是head-to-head,未给定D时,L和B独立。



参考文章

评论

发表评论

validate