A Search Algorithm for Inference in Diagnostic Bayesian Networks

摘要

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.