A best-first search method for anytime evaluation of belief networks
Nathalie Jitnah, Ann E. Nicholson · 1997
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. node, the P ~ holds its prior probabilities and the Pa is not used. If N is a leaf, the P; ~ is a unit vector and the P, is not used. Otherwise, the P ~ holds the probabilities of the node, averaged over all state combinations of its parents and the P; ~ is a unit vector. Evidence is entered into a node by replacing its P ~ and P ~ vector by one consisting of a 1 for the evidence state and O’s for all other states. Fig. 1 shows an example BN with its CPDs in Fig. 2. The P ~ and P ~ vectors are given for each node, with no evidence. p,(s) ffi (.3 P (B) ffi (.4.5 Px(13) ffi(1 1 BN structure