[原创]贝叶斯网推理的实现

一．利用贝叶斯网进行预测的有效性

贝叶斯网可以根据所给出的历史数据构造出贝叶斯网模型并计算相应的参数后，就可以利用贝叶斯网来对未知事件进行预测，这其实就是在模拟人类的经验形成过程。其最大的优势就是可计算性，而且这种可计算性来自于数据本事，并不需要向模糊处理那样提前给定先验知识，这就最适合计算机进行处理。

人类是从日常的生活、工作中对各种反复出现的状况进行归纳、总结来形成经验，然后当类似的情况再次出现时人类就可以利用已有的经验进行处理。贝叶斯网则是从大量的历史数据中发现数据间的因果依赖关系从而拟合出一个和给出的数据最为匹配的因果结构，然后根据这个因果结构计算各变量的条件概率。这样当再次给出部分数据时就可以利用这个贝叶斯模型利用贝叶斯公式来计算其它尚未给出的变量各种取值的概率，这就形成了对其它变量的预测。

贝叶斯网预测的有效性来自于现实世界中各种事物之间的相互依赖以及人类所关注的事物的变化、生长都在人类所能体验到的时空尺度上具有相关性、类似性、重复性等特点。贝叶斯网其实就是对人类经验的模拟，所以贝叶斯网所模拟的事物的状态必须是重复出现的而且彼此之间有各种各样的联系的。贝叶斯网的基础来自贝叶斯公式，所以其预测的结果是条件概率的，也就是说在当前给定的条件下，某事物各种状态出现的概率各自是多少。当然这也是我们通常做预测时的状况，类似于我们通常所说的：在目前这种情况下，我认为成功的可能性在50%左右。

贝叶斯网的用途很广泛，只要是有大量的历史数据同时又有着相当不确定性的地方都可以使用到贝叶斯网来做预测。比如风险评估、客户偏好等等，尤其是在那些积累了大量数据但还没有形成比较明确知识的领域，更适合处于巨变的环境中而又缺少知识积累的中国企业。

二．推理思路

贝叶斯网是一个有向网络，每个节点的函数表其实就是该变量以及其所有父亲变量的联合概率分布，因此一个变量可以利用其父亲节点和贝叶斯全概率公式消去。所以贝叶斯网的推理过程就是计算某个未知变量概率的过程，其实也就是一个消元的过程，是将除了待求变量和已知取值变量之外的其它变量一一消去的过程。

就推理思路来说很简单，麻烦的是如何实现，因为消元计算是合并老的函数表，是一个连乘然后累加的结果，在变量数量较多的情况下会产生数量巨大的中间函数（笔者在某次跟踪过程中发现中断推理时的中间函数的数量竟然有4000多个，当时就断了单步跟踪查看的念头），用单个函数来计算则既难于理解又难于处理预设值变量、待求变量等。最后笔者采取了将函数编为一个类，计算新函数时会产生的中间函数归整为一个函数队列也编为一个类。函数类用于所有的实际计算、预设值的处理、结果查询等等；函数队列类则主要用于收集消元过程中产生的中间函数，统一为它们赋值、设定预设值等，唯一实际执行的工作就是完成所有中间函数在当前取值条件下的连乘。

三．推理过程

推理过程包括如下几个部分：

1 初始化

a 构造一个初始的中间函数队列，将本次推理所涉及到的所有节点相对应的函数放入其中；

b 对初始的函数队列设置已知变量的预设值；

c 构造一个待消元变量序列，该序列不包括已知的预设值变量和待求变量；

2 如果待消元变量序列中还有待消元变量则重复执行消元

a 构造一个新的函数队列，将原有的函数队列中的和待消元变量相关的函数全部移入新的函数队列；

b 构造一个新的函数，该函数为新的函数队列的计算结果；

c 对新的函数队列中所涉及到的所有变量依次赋值，即从(0,0,…,0)一直赋值到(m,n,…,z)（其中m,n,….,z等是各个变量的最大取值分类号），对每次赋值计算新函数队列的连乘值，将该连乘值按待消元变量的取值进行累加后所得的值就是新函数在当前赋值条件下的函数值；

d 将计算完毕的新函数加入到原有的函数队列中；

3 将目前的函数队列中的所有函数合并为一个函数并进行归一化处理，最后所得到的函数就是在当前已知条件下待求变量的概率分布。

需要注意的是求出的概率分布有可能是NaN（double类型下的不是数字）。这不是计算出现了问题，而是说依据本模型所依赖的数据在现实情况下不应该出现当前的已知变量取值组合，也就是说某个已知变量的取值赋予了错误的取值。从语义上讲，就是根据前面几个已知变量的赋值，该变量的取值已经是固定的了（也就是在前面几个已知变量的取值条件下某个值的取值概率为100%，其它值的取值概率为0），但给变量设定了其它不应该会出现的取值情况。

四．推理过程的优化

前面介绍的推理过程是通用过程，但在变量很多时，已知变量很少而且和待求变量的逻辑关系简单，和其它变量没什么关系，而通用过程会把所有变量都考虑进行一一消去，计算量很大但又没什么必要，而且还会造成计算误差，影响到预测精度。鉴于此种情况，需要考虑对通用过程进行优化。

优化包括两个方面，一个是消元顺序，一个是消元规模。

消元顺序的优化是因为每次消元都是将和待消变量有关系的所有变量的函数表全部进行一次连乘累加计算，如果和待消变量有关系的变量很多则计算量极其巨大，所以消元顺序的优化就是每次挑选一个影响最小的变量消去。

消元规模是对当前所应用的贝叶斯网结构的考察，一定要牢记贝叶斯网表示了量化的因果逻辑关系。而因果关系是单向依赖关系，即A->B，是A的取值决定了B的取值而不是相反。所以在进行推理时其实只要考虑已知变量和待求变量的所有祖先变量就可以了，其它变量的存在既不会影响待求的概率分布反而会在连乘中产生误差影响预测精度。

将这两个问题组合在一起考虑就是利用图计算在每次预测开始时先将所有的已知变量和待求变量及其祖先一起根据当前贝叶斯网结构生成一个无向结构图(anGraph)，待消元变量就是anGraph中除已知变量和待求变量之外的节点（已知变量和待求变量的所有祖先）。只针对anGraph所涉及的变量进行消元计算就实现了消元规模的优化，按最小缺边数依次从anGraph中删除节点就实现了消元顺序的优化。

五．推理效能

贝叶斯网推理的计算量虽然巨大，但包括数据准备在内依然是在秒级（一般都小于1s，如果是连续推理，由于贝叶斯网结构已经读取速度更快），基本可以支持操作级的决策支持应用。对于利用anGraph进行优化的效果并不明显，应该是目前所用的贝叶斯网结构变量还不是很多，结构还不是非常复杂，而anGraph本身的生成、缺边计算、删除节点、构造新边等维护性工作的开销相对来说就比较大了以至于部分抵消了优化效果，但对预测精度的提高是肯定的。

参考书目：

1 贝叶斯网引论，科学出版社，张连文/郭海鹏著
2 复杂决策任务的建模与求解方法，科学出版社，杨善林/胡小建著