A Randomized Approximation Algorithm of Logic Sampling

PIBNET is hard for NP, by reduction from 3-satisfiability in the propositional calculus [3]. That classification has focused research on approximate methods, special-case techniques, heuristics, and analyses of average-case behavior. There now exists a number of algorithms for exact probabilistic inference in belief networks: the message-passing algorithm of Pearl [ 12], the triangulation method of Lauritzen and Spiegelhalter [10], and others. Previous approximation algorithms include the Markov-simulation scheme of Pearl [13, 14], Henrion's logic sampling [7], and the randomized approximation scheme (ras), known as BN-RAS, which we have previously demonstrated [1]. Heckerman has proposed a special-case algorithm for certain kinds of two-level belief networks [6]. Each algorithm has computational properties that render it attractive for inference on certain kinds of networks. The NPhard classification suggests, however, that no algorithm can provide a definitive efficient solution for all inference problems.