A Best-First Search Method for Anytime Evaluation of Belief Networks

Nathalie Jitnah and Ann E. Nicholson

We present a method for incremental evaluation of a Belief Network (BN). Evaluation is initially performed on a restricted number of nodes in the immediate vicinity of the query nodes. The BN is then traversed radially out from each query node and estimates for the belief of the query node are computed iteratively. This incremental evaluation results in a form of anytime algorithm. A best-first graph traversal strategy requires an assessment of the relative importance of various nodes in terms of contributing the most towards a query node. At each step, we must visit in priority the most significant nodes while making a trade-off with computation cost. We use the concept of arc weights in a BN to determine to what extent a node influences the query node. We also incorporate a measure of the computation cost of visiting a node, in terms of the state space sizes of the node and of its parents.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.