关键词: 贝叶斯网, 变量消元, 近似算法, 端正图, 团

Abstract: 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.

Key words: Bayesian network, Variable Elimination (VE), approximately algorithms, moral graph, clique