基于代数决策图的贝叶斯网络参数简化技术  

Bayesian Network Parameter Reduction Technique Based on Algebraic Decision Diagrams

作　　者：王瑶[1] 孙秦[1] 

机构地区：[1]西北工业大学航空学院,西安710072

出　　处：《工程数学学报》2016年第3期259-269,共11页Chinese Journal of Engineering Mathematics

基　　金：工信部十二五质量与可靠性技术基础项目(2052013B003)~~

摘　　要：贝叶斯网络是一种进行不确定性知识表达和推理的有效工具,推理算法是贝叶斯网络研究的主要内容之一.目前,贝叶斯网络推理算法采用条件概率表(CPT)来存储贝叶斯网络中各节点的条件概率分布(CPD).CPT中的概率参数随父节点数目的增加呈指数增长,使得网络中概率参数急剧增加,降低了网络推理效率.为提高网络推理效率,本文提出采用代数逻辑图(ADD)取代CPT存储网络中各节点CPD的方法.结合有序二分决策图理论,分析并验证了ADD通过捕捉贝叶斯网络中父子节点之间的环境独立性来减少网络中的概率参数的原理,进而推导出了CPT到等价ADD转化的算法.最后,通过实例验证了ADD存储方式的有效性.结果表明,对于具有环境独立特性的贝叶斯网络,相对于CPT的存储方式,等价ADD存储方式可有效减少网络中的概率参数,为贝叶斯网络推理效率的提高提供一种有效手段.Bayesian network is an effective tool for uncertainty knowledge presentation and inference. Bayesian network inference algorithm is one of the main fields in Bayesian network research. Currently, in almost every inference algorithm, the conditional probability distribution（CPD） of each node in a Bayesian network is represented in the form of conditional probability table（CPT）. However, there is an exponential increase in the number of probability parameters of each CPT as the number of father nodes grows, which will cause an upsurge in the number of parameters in a Bayesian network and finally reduce the inference efficiency. To improve the inference efficiency of Bayesian network, the algebraic decision diagram（ADD） is proposed to represent the CPD of each node in a Bayesian network. Furthermore, by using the theory of ordered binary decision diagram, we analyze and verify the principle that ADD reduces the parameters of a Bayesian network by characterizing the context-specific independence among the parent-child nodes of the net. In addition, the algorithm for converting a CPT into its equivalent ADD is deduced. Eventually, the efficiency of ADD in parameter storage is validated by an example. It shows that for any Bayesian network with the context-specific independence,the parameters of the net can be reduced in the form of the equivalent ADD compared to the form of CPT, which provides a powerful tool for improving the inference efficiency of Bayesian network.

关 键 词：贝叶斯网络 代数决策图 条件概率表 环境独立 

分 类 号：O233[理学—运筹学与控制论] O211.9[理学—数学]