A search algorithm for inference in diagnostic Bayesian networks

作者：Huang Yuxiao; Liu Dayou^*; Zhu Yungang; Jia Haiyang

来源：Journal of Information and Computational Science, 2011, 8(7): 1181-1188.

• Backtracking algorithm
• Combinatorial optimization problems
• Diagnostic Bayesian networks
• Exact inference
• One-factor
• Parameterized
• Search
• Search Algorithms
• Small size

In this article, we propose the concept of Maximum Quadruple-qualified subset (MQQ), which is a parameterized node set in diagnostic Bayesian networks. For certain networks and parameters, MQQ possesses the following features: (i) |MQQ| is large yet eliminating it is feasible; (ii) MQQ is highly relevant to queries; (iii) computation of eliminating MQQ can be shared by one factor with small size. Consequently, the efficiency of exact inference in the networks can be, if not greatly, improved through sharing the computation of eliminating MQQ. Searching for MQQ is a combinatorial optimization problem, and we propose a backtracking algorithm for the problem. We demonstrate empirically the performance of the algorithm on a range of networks.

• 出版日期2011