Criteria to evaluate approximate belief network representations in expert systems

摘要

The representation of uncertainty, and reasoning in the presence of uncertainty, 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. Unfortunately, belief propagation techniques for general network structures are computationally intense. In this paper, we present belief network representations 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 representation. A criterion is required to measure the closeness of the approximate to the actual. We examine desirable features of measures that compare approximate representations to the actual one. We identify two well-known measures, called the logarithm rule and the quadratic rule, as having special properties for evaluating approximations. We present a new result that shows the equivalence of using the logarithm rule to that of finding the maximum likelihood estimator. Next, we discuss the modeling implications of using the logarithm rule and the quadratic rule in terms of the nature of solutions that are obtained, and the computational effort required to obtain such solutions. Finally, we 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 probability distributions and cost functions. Our results suggest that the logarithm rule is very appropriate for evaluating approximate representations.