[转]贝叶斯球(Bayes Ball)算法

参考：http://www.cnblogs.com/pangliang/archive/2011/02/27/1966303.html

 

 

用有向图表示的概率模型也叫“贝叶斯网络”. 贝叶斯网络中的两个结点与关于结点(或结点集合)条件独立时我们称“D-separates”与, 写作. D-Separation中的D指Directed. 从图形上看, 结点集合“D-separates”结点与结点是指任意一条从到的路径中都出现了以下两种情形之一:

• 存在样式或, 且;
• 存在样式, 且及其所有后代都不属于.

这几种情形的示意图:
 

第一和第二个图中, , 而; 第三个图中, , 而.

贝叶斯球算法是判断贝叶斯网络中任意一对结点是否条件独立的一种较为直观的算法. 其思想是, 设想在贝叶斯网络中有一个按一定规则运行的球, 在给出已知结点集合的情况下判断球能否由结点出发到达结点(或者反过来, 由到). 如果可以, 那么判断; 反之则有.

每一个结点可以已知(属于)或未知(不属于). 定义几个术语:

• 通过(pass through): 贝叶斯球从当前结点的父结点方向过来时, “通过”指当前结点允许贝叶斯球访问自己的所有子结点; 贝叶斯球从当前结点的子结点方向过来时, “通过”指当前结点允许贝叶斯球访问自己的所有父结点.
• 反弹(bounce back): 贝叶斯球从当前结点的父结点方向过来时, “反弹”指当前结点允许贝叶斯球访问自己的所有父结点; 贝叶斯球从当前结点的子结点方向过来时, “反弹”指当前结点允许贝叶斯球访问自己的所有子结点.
• 截止(block): 当前结点阻止贝叶斯球继续运动.

使用上面的术语, 贝叶斯球运行的规律如下:

• 未知结点总能使贝叶斯球通过, 同时还反弹从其子结点方向来的贝叶斯球.
• 已知结点反弹从其父结点方向来的贝叶斯球, 截止从其子结点方向来的贝叶斯球.

这几条规则如下图所示.
 

图中用双线圈表示已知结点. 反映的规则从左至右依次是:

• 未知结点允许从其父结点方向来的贝叶斯球访问其任意子结点;
• 未知结点允许从其子结点方向来的贝叶斯球访问其任意父结点以及子结点;
• 已知结点允许从其父结点方向来的贝叶斯球访问其任意父结点;
• 已知结点截止从其子结点方向来的贝叶斯球.

还需加上边界条件, 即当前结点是图的边界点时:
 

注意两个反弹的情况, 前者是反弹到所有子结点, 后者是反弹到所有父结点.

下面看几个例子. 示意图中双线圈表示已知结点.

下图中, 设贝叶斯球从图中结点A出发, 右图给出了贝叶斯球的运动轨迹. 从图中看出, 只有左下角的那个结点与结点A条件独立.
 

下图中, 这个图中结点A与B非条件独立. 从A出发时, 尽管从左边的一条路径无法到达B, 但从右边的路径则是可以到达的.
 

下图中, 左图表示, 右图表示. 对于右图的结论也可以这样理解: 因为D的子结点C已知, 所以V形结构EDB中E与B非条件独立, 进而A与B非条件独立.