D分离是什么

FanlyQA2020-10-25 10:22:48阅读(...)

D分离是一种用来判断变量是否条件独立的图形化方法。相比于非图形化方法,D-Separation更加直观,且计算简单。对于一个DAG(有向无环图)E,D-Separation方法可以快速的判断出两个节点之间是否是条件独立的。

D 分离(D-Separation)是一种用来判断变量是否条件独立的图形化方法。相比于非图形化方法,D-Separation 更加直观,且计算简单。对于一个 DAG(有向无环图)E,D-Separation 方法可以快速的判断出两个节点之间是否是条件独立的。

D分离是什么

基本概念

在贝叶斯网络的学习过程中,经常会遇到 D 分离(D-Separation)这个概念,D 分离是寻找网络节点之间的条件独立性的一种方法或者说一种问题的简化处理的技巧。采用 D 分离技术,在用贝叶斯网络进行预测,诊断推理等方面,可以提高计算速度,减少计算复杂性。

原理

对于给定的结点集ε,如果对贝叶斯网中的结点 Vi 和 Vj 之间的每个无向路径,在路径上有某个结点 Vb,如果有属性:

(1)Vb 在ε中,且路径上的两条弧都以 Vb 为头(即弧在 Vb 处开始(出发));

(2)Vb 在ε中,路径上的一条弧以 Vb 为头,一条以 Vb 为尾 ;

(3)Vb 和它的任何后继都不在ε中,路径上的两条弧都以 Vb 为头(即弧在 Vb 处结束);

则称 Vi 和 Vj 被 Vb 结点阻塞。

如果 Vi 和 Vj 被证据集合ε中的任意结点阻塞,则称 Vi 和 Vj 是被ε集合 D 分离,结点 Vi 和 Vj 条件独立于给定的证据集合ε,即 P(Vi|Vj,ε) =P(Vi|ε)和 P(Vj|Vi,ε) =P(Vj|ε),表示为:I(Vi,Vj|ε) 或 I(Vj,Vi|ε) 。

无向路径:DAG 图是有向图,所以其中的路径也应该是有向路径,这里所指的无向路径是不考虑 DAG 图中的方向性时的路径。

条件独立:如具有以上三个属性之一,就说结点 Vi 和 Vj 条件独立于给定的结点集ε。

阻塞:给定证据集合ε,当上述条件中的任何一个满足时,就说 Vb 阻塞相应的那条路径。

D 分离:如果 Vi 和 Vj 之间所有的路径被阻塞,就叫证据集合ε可以 D 分离 Vi 和 Vj。D 分离的实质就是寻找贝叶斯网中的条件独立语义,以简化推理计算。

三种情况独立分析

情况一

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 条件下独立的。

情况二

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 条件下独立的。

情况三

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 条件独立的。

基于 D-Seperation 的独立分析

D-Separation 是一种用来判断变量是否条件独立的图形化方法。相比于非图形化方法,D-Separation 更加直观,且计算简单。对于一个 DAG(有向无环图)E,D-Separation 方法可以快速的判断出两个节点之间是否是条件独立的。

对于较为复杂的 DAG 图,我们可以给出一个普遍意义上的结论,也就是 D-Seperation。对于 DAG 图 E,如果 A,B,C 是三个集合(可以是单独的节点或者是节点的集合),为了判断 A 和 B 是否是 C 条件独立的,我们考虑 E 中所有 A 和 B 之间的无向路径。对于其中的一条路径,如果她满足以下两个条件中的任意一条,则称这条路径是阻塞(block)的:

(1)路径中存在某个节点 X 是 head-to-tial 或者 tail-to-tail 节点(情况一和情况二),并且 X 是包含在 C 中的;

(2)路径中存在某个节点 X 是 head-to-head 节点(情况三),并且 X 或 X 的儿子是不包含在 C 中的;

如果 A,B 间所有的路径都是阻塞的,那么 A,B 就是关于 C 条件独立的;否则,A,B 不是关于 C 条件独立的。

实例

据 D-Seperation 分隔定理,我们可以很容易的判断是否是条件独立的。

判断图中 a,b 是否是 c 条件独立的:

上图中 a 到 b 只有一条路径 a->e->f->b。考虑路径上的点 e 和 f,e 是 head-to-head 类型的,且 e 的儿子节点就是 c,根据(b),e 不是阻断的。所以 a 和 b 不是 c 条件下独立的。

如果要判断 a 和 b 是否是 f 下条件独立的。同样的方法,考虑路径 a->e->f->b 上的所有节点。节点 e 是 head-to-head 类型的,e 和她的儿子节点 c 都不在 f 中,所以 e 不是阻断路径的节点。节点 f 是 tail-to-tail 节点,且 f 就在 f 节点中,所以 f 节点阻断了路径。结论:a 和 b 是 f 下条件独立的。

D-Seperation 还可以用来证明独立同分布和马尔科夫边界等。

收藏0个人收藏
走进科技生活方式

评论交流

泪雪默认头像请「登录」后参与评论
  1. 加载中..