贝叶斯网最优消元顺序的近似构造算法

Approximation algorithm of variable elimination of Bayesian network

变量消元(VE)法是贝叶斯网推理的一个基本方法,然而不同的消元顺序会导致相差悬殊的计算复杂度,寻找最优消元顺序问题是一个NP难问题,因此在实际应用中多采用近似算法求解。通过对贝叶斯网对应的端正图的分析,综合考虑了消元过程中消去的边和增加的边对剩余图的影响,进而提出了一些降低图的复杂度从而控制消元成本的方法,在此基础上提出了一个最优消元顺序的近似构造算法,最后通过随机仿真实验分析比较了算法的性能。实验结果表明,新算法较最小缺边搜索算法有明显的优势。

Variable Elimination（VE） is a basic reasoning method of Bayesian network;however,different order of elimination will lead to computational complexity of significant differences.It is a NP-hard problem to find the optimal order,so in practical application approximation algorithm is often used.Based on the analysis of the moral graph of Bayesian network,the added edges and the removed edges during elimination were considered,some methods of reducing graph complexity and controlling elimination cost were proposed,and a new algorithm was presented.Finally,the new algorithm was tested by random simulations.The simulation results show that the new algorithm outperforms the minimum deficiency search algorithm.