CRITERIA TO EVALUATE APPROXIMATE BELIEF NETWORK REPRESENTATIONS IN EXPERT-SYSTEMS

The representation of uncertainty, and reasoning in the presence of un certainty, has become an important area of research in expert systems. Belief networks have been found to provide an effective framework for the representation of uncertainty using probability calculus. Unfortu nately, belief propagation techniques for general network structures a re computationally intense. In this paper, we present belief network r epresentations that approximate the underlying dependency structure in a problem domain in order to allow efficient propagation of beliefs. An important issue then is one of obtaining the 'best' approximate rep resentation. A criterion is required to measure the closeness of the a pproximate to the actual. We examine desirable features of measures th at compare approximate representations to the actual one. We identify two well-known measures, called the logarithm rule and the quadratic r ule, as having special properties for evaluating approximations. We pr esent a new result that shows the equivalence of using the logarithm r ule to that of finding the maximum likelihood estimator. Next, we disc uss the modeling implications of using the logarithm rule and the quad ratic rule in terms of the nature of solutions that are obtained, and the computational effort required to obtain such solutions. Finally, w e use a decision theoretic approach to compare such solutions using a common frame of reference. A simple decision problem is modelled as a belief network, and the comparison is performed over a wide range of p robability distributions and cost functions. Our results suggest that the logarithm rule is very appropriate for evaluating approximate repr esentations.