D—separation

D-Separation(D分离)-PRML-8.22-GraphicalModel五18by小军一、引言在贝叶斯网络的学习过程中，经常会遇到（D-Separation）D-分离这个概念，D-分离是寻找网络节点之间的条件独立性的一种方法或者说一种问题的简化处理的技巧。采用D-分离技术，在用贝叶斯网络进行预测，诊断推理等方面，可以提高计算速度，减少计算复杂性。D-Separation是一种用来判断变量是否条件独立的图形化方法。相比于非图形化方法，D-Separation更加直观，且计算简单。对于一个DAG(有向无环图)E，D-Separation方法可以快速的判断出两个节点之间是否是条件独立的。二、三种情况分析首先可以看看以下三种简单情况下条件独立的情况（对应于PRML中8.2.1的Threeexamplegraphs）：ExampleOne：tail-to-tail(节点C连接的是两个箭头的尾部，如图)可知，P(a,b,c)=P(a|c)*P(b|c)*P(c)(1)现在我们求P(a,b)，如果P(a,b)=P(a)*P(b)，则a和b是在c条件下独立分布的。分两种情况进行讨论：（1）C值不作为观察点。令(1)式对c求积分，消去c值，考虑c是离散的情况，可得可以看到，与P(a,b)=P(a)*P(b)不等，所以a和b不是c条件独立的。（2）C值作为观察点(即以C作为条件)。则可以知道C取某个c状态的概率为P(c)，c条件下a和b发生的概率为P(a,b|c)。由下式：可得a和b是c条件下独立的。ExampleTwo：head-to-tail可知，p(a,b,c)=p(a)*p(c|a)*p(b|c)（2）同样分两种情况进行讨论：（1）、c值不作为观察点。对（2）式（考虑c是离散的情况）积分可得：可知，a和b不是c条件独立的。（2）、c值作为观察点。则图模型表示为：c条件下a和b发生的概率为P(a,b|c)。由下式：可知，a和b是c条件下独立的。ExampleThree：head-to-head可知p(a,b,c)=p(a)*p(b)*p(c|a,b)(3)同理，分两种情况讨论：（1）、c值不作为观察点。由于所有p(c|a,b)相加和=1，所以有（3）式消去c，可得p(a,b)=p(a)*p(b)，即a与b是条件独立的。（2）、c值作为观察点。所以有：最后不能因式分解成p(a)*p(b)的形式，所以a与b不是c条件独立的。三、总结对于较为复杂的DAG图，我们可以给出一个普遍意义上的结论，也就是D-Seperation。对于DAG图E，如果A，B，C是三个集合（可以是单独的节点或者是节点的集合），为了判断A和B是否是C条件独立的，我们考虑E中所有A和B之间的无向路径。对于其中的一条路径，如果她满足以下两个条件中的任意一条，则称这条路径是阻塞（block）的：（a）路径中存在某个节点X是head-to-tial或者tail-to-tail节点（Exampleone/two），并且X是包含在C中的；（b）路径中存在某个节点X是head-to-head节点（ExampleThree），并且X或X的儿子都不是包含在C中的；如果A，B间所有的路径都是阻塞的，那么A，B就是关于C条件独立的；否则，A，B不是关于C条件独立的。四、应用例子根据D-Seperation分隔定理，我们可以很容易的判断是否是条件独立的。我们来看一个例子：判断图中a与b是否在c条件下独立？a与b是否在f条件下独立？图中可以看到a到b只有一条路径a-e-f-b。考虑路径上的点e和f：其中e是head-to-head类型的，且e的儿子节点就是c，根据（b），e没有被阻断，而节点f是tail-to-tail类型节点，根据（a），f不在c中，所以a和b不是c条件下独立的。现在如果要判断a和b是否是f下条件独立的。同样的方法，考虑路径a-e-f-b上的所有节点。节点e是head-to-head类型的，e和她的儿子节点c都不在f中，根据(b)可知，所以e是阻断路径的节点。节点f是tail-to-tail节点，且f节点就在f中，根据(a)，可知f节点阻断了路径。结论：a和b是f下条件独立的。D-Seperation还可以用来证明独立同分布和马尔科夫边界等。五、参考资料1、、(--！Thisisanerror!)3、《patternrecognitionandmeachinglearning》-chapter8:GraphicalModel-8.2conditionalindependence