HYBRID ALGORITHMS FOR APPROXIMATE BELIEF UPDATING IN BAYES NETS

Belief updating in Bayes nets, a well-known computationally hard probl em, has recently been approximated by several deterministic algorithms and by various randomized approximation algorithms Deterministic algo rithms usually provide probability bounds, but have an exponential run time. Some randomized schemes have a polynomial runtime, but provide o nly probability estimates. Randomized algorithms that accumulate high- probability partial instantiations, resulting in probability bounds, a re presented. Some of these algorithms are also sampling algorithms. S pecifically, a variant of backward sampling, used both as a sampling a lgorithm and as a randomized enumeration algorithm, is introduced and evaluated An implicit assumption made in prior work, for both sampling and accumulation algorithms, that query nodes must be instantiated in all the samples, is relaxed Genetic algorithms can be used as an alte rnate search component for high-probability instantiations; several me thods of applying them to belief updating are presented. (C) 1997 Else vier Science Inc.