Localized Partial Evaluation of Belief Networks
This addresses the need for faster, approximate inference in applications that do not require exact probabilities for all nodes, though it is incremental as it builds on existing propagation methods.
The paper tackles the problem of inefficient exact evidence propagation in belief networks by introducing the localized partial evaluation (LPE) algorithm, which computes interval bounds on marginal probabilities for a query node by examining only a subset of nodes, resulting in an anytime property that improves solutions with more time.
Most algorithms for propagating evidence through belief networks have been exact and exhaustive: they produce an exact (point-valued) marginal probability for every node in the network. Often, however, an application will not need information about every n ode in the network nor will it need exact probabilities. We present the localized partial evaluation (LPE) propagation algorithm, which computes interval bounds on the marginal probability of a specified query node by examining a subset of the nodes in the entire network. Conceptually, LPE ignores parts of the network that are "too far away" from the queried node to have much impact on its value. LPE has the "anytime" property of being able to produce better solutions (tighter intervals) given more time to consider more of the network.