图论在贝叶斯网条件独立性中的应用
摘要：贝叶斯网络是将概率论和图论进行有机结合，是一种概率图形模型。该文通过实例和图形，利用图论中的d-分离表示贝叶斯网节点间的通路，使用贝叶斯球算法，分析通路是否阻塞或激活，能够较好判定贝叶斯网中节点间的条件独立性。
关键词：贝叶斯网；图论；通路；条件独立性；贝叶斯球算法
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）33-7568-03
1 贝叶斯网的概念
1.1 贝叶斯网的定义
贝叶斯网络是一种概率网络，它是基于概率推理的图形化网络，它包含两方面的内容，即用BN=（（DAG，CPD）来表示，分别指有向无环图和条件概率表。
1）有向无环图DAG=（V，E）是一个网络结构。其中，V={xl，x2，…，xn}是DAG中结点的集合，每一结点xi为V表示域中的一个随机变量，每个变量都具有限且互斥的状态集合，变量可以是连续变量，也可以是不连续变量，变量的状态以是两个或两个以上，取值可以是确定型，也可以是不确定型的。E是结点间有向边（弧）的集合，边表示变量之间的直接依赖关系。对于任意的两个节点[Xi，Xj]的有向边表示[Xi]对[Xj]有直接的因果影响，表示为弧[Xi→Xj]，并称节点[Xi]是节点[Xj]的父亲节点（parent），而节点[Xj]是节点[Xi]的子节点（child）。
2） CPD表示为条件概率分布（即BN的参数集合），属于贝叶斯网的定量部分。条件概率表（Conditional Probability Table，CPT）反映了变量之间关联性的局部概率分布情况，可以用P（Xi/Pa（Xi）来描述，表示给定了父亲节点的状态情况下，当前节点所有取值的条件概率分布表。
贝叶斯网络提供了对域的一个完整描述。有了节点及其对应的有向边、条件概率表，贝叶斯网络就可以表达网络中所有节点（变量）的联合概率，并可以根据先验概率信息或某些节点的取值来计算其它任意节点的概率信息。其中，联合概率可由下式求得：
下面给出一个典型的贝叶斯网，如图1。
1.2 贝叶斯网的条件独立性
[X，Y]和[Z]为贝叶斯网[N]中三个不相交的节点集，给定[Z]时，[X]通往[Y]的所有通路都被堵塞，即[Z]d-分隔[X，Y]，则称[X]和[Y]在给定[Z]时条件独立，记为[X⊥Y|Z]，且有
[p（X，Y|Z）=p（X|Z）p（Y|Z）]，或[p（X|Y，Z）=p（X|Z）]。
2 图论的定义
1736年，一篇著名的论文《依据几何位置的解题方法》发表，这是研究图论（Graph theory）的第一篇文章，该文的作者欧拉因此被尊称为图论和拓扑之父。图论严格来讲是组合数学的一个重要分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法，交叉应用了拓扑学、群论、数论等学科，其应用十分广泛，如在物理学、化学、运筹学、计算机科学、控制论、社会科学等领域。
本文中应用d-分离来判定贝叶斯网中节点的条件独立性，d-分离是图论的概念。
3 d-分离判定节点间的条件独立性
3.1 节点相连的基本情况
贝叶斯网通路是指开始于节点X而结束于节点Y的一个节点序列，节点序列中的相邻节点均有边相连，且节点各异。由于贝叶斯网通路中边的方向变化，产生有顺连节点、分连节点和汇连节点，其结构如下图2所示。
设X，Y，Z是图G=（V，E）中三个不同的节点，如果满足[X→Z∈G]和[Y←Z∈G]，且[X∙∙∙Y∉G]，称三元组（X，Y，Z）是G的顺连结构，节点Z称为顺连节点；如果满足[X←Z∈G]和[Y←Z∈G]，且[X∙∙∙Y∉G]，称三元组（X，Y，Z）是G的分连结构，节点Z称为分连节点；如果满足[X→Z∈G]和[Y→Z∈G]，且[X∙∙∙Y∉G]，称三元组（X，Y，Z）是G的汇连结构，节点Z称为汇连节点。
3.2 条件独立性判断
如果Z d-分离X和Y，那么X和Y在给定Z时条件独立。然而Z d-分离X和Y是指，贝叶斯网中的节点X和节点Y之间的所有通路都被节点集Z所阻塞。如果满足如下条件，节点X和节点Y之间的通路[α]被Z所阻塞：
1）[α]有一个在Z中的顺连节点或分连节点；
2）[α]有一个汇连接点，并且该节点和它的后代节点都不在Z中。
如图3所示的贝叶斯网，设X={A}， Y={G}， Z={D}，X和Y之间的每一条通路[α]是阻塞还是激活，下面我们进行分析。
设X={F}， Y={G}， Z={C}， X和Y之间的通路[α]：
3.3 贝叶斯球算法
Shachter为了判定d-分离提出了贝叶斯球算法，其基本思想为：在贝叶斯网中给定节点集K信息的情况下，贝叶斯球沿着从节点集J到贝叶斯网中其他节点的有效通道运动，从而确定与节点集J的d-分离节点集，即判断贝叶斯网中两节点是否条件独立。具体实现有如下两种方法：
1）首先定义3个术语：什么是“通过”？从当前结点的父结点方向传来的贝叶斯球，当前结点允许贝叶斯球访问自己的所有子结点； 从当前结点的子结点方向传来的贝叶斯球，当前结点允许贝叶斯球访问自己的所有父结点，以上两种情况就指“通过”。
什么是“反弹”？从当前结点的父结点方向传来的贝叶斯球，当前结点允许贝叶斯球访问自己的所有父结点；从当前结点的子结点方向传来的贝叶斯球，当前结点允许贝叶斯球访问自己的所有子结点，以上两种情况就指“反弹”。
什么是“截止”？截止就是指当前结点阻止贝叶斯球继续向任何方向运动。
用术语表达贝叶斯球运行的规律如下：
未知结点总能使贝叶斯球通过，同时还反弹从其子结点方向来的贝叶斯球。
已知结点反弹从其父结点方向来的贝叶斯球，截止从其子结点方向来的贝叶斯球。
如图4所示的贝叶斯网，设X={A}，Z={D，F}，贝叶斯球从节点A开始运动，根据以上的算法运动规律，贝叶斯球无法到达节点G，也就是节点A到节点G的通路被阻塞，所以节点A在给定信息Z情况下与节点G条件独立。
2）节点集J中的任何节点[xi]，假定[xi]的贝叶斯网球总是从子节点处传来，根据与其相连的边的方向及相连节点的类型，将贝叶斯球从贝叶斯网中其他节点发送，并对节点做相应标记符号。如果一个节点[xi]把贝叶斯球传给它的子节点，则为节点[xi]标记为“bottom”；如果把贝叶斯球传给它的父节点，标记为“top”；不管贝叶斯球是传给子节点还是父节点，节点[xi]同时标记已访问“visited”。直到算法结束，J的d-分离的节点集就是所有没有被标记为“bottom”的节点集。
4 总结
贝叶斯网络是将概率论和图论进行有机结合，是一种概率图形模型。d-分离是在给定信息时表示节点间的条件独立，是图论的范畴，而条件独立属于概率论的范畴，利用d-分离能够较好较快判定贝叶斯网中节点间的条件独立性，确定贝叶斯网中节点间的关系。
参考文献：
[1] 刘惟一，李维华，岳昆.智能数据分析[M].北京：科学出版社，2007.
[2] 张连文，郭海鹏.贝叶斯网引论[M].科学出版社，2006.
[3] 冀俊忠，刘椿年，沙志强.贝叶斯网模型的学习、推理和应用[J].计算机工程与应用， 2003，39（5）：23-27.
[4] 燕子宗，张宝琪.图论及其应用[J].重庆科技学院学报，2007（6）.