DEPARTMENT OF COMPUTER SCIENCE
MONASH UNIVERSITY

Clayton, Victoria 3168 Australia


TECHNICAL REPORT 97/309


Weight-directed search for anytime evaluation of belief networks

N Jitnah and A E Nicholson

ABSTRACT

We present a new framework for implementing evaluation of belief networks (BNs), which consists of two steps: (1) transforming a belief network into a graph structure called a BNgraph (2) performing anytime inference by searching the graph. Once the BNgraph has been constructed, whenever new evidence is incorporated, the posterior probabilities of query nodes are re-calculated, using a variation of the polytree message-passing algorithm. The BNgraph framework is geared towards anytime evaluation. Evaluation is a graph search problem and we investigate different search strategies. We show how it is possible to increase the rate of convergence of the anytime result, by using a best-first graph search method based on arc weights.