Ideal Reformulation of Belief Networks
John Breese and Eric Horvitz
Click here to access postscript file.
Click here to access pdf file.
The intelligent reformulation or restructuring of a belief network
can greatly increasethe efficiency of inference. However, time
expended for reformulation is not available for performing inference.
Thus, under time pressure, there is a tradeoff between the time
dedicated to reformulating the network and the time applied to the
implementation of a solution. We investigate this partition of
resources into time applied to reformulation and time used for
inference. We shall describe first general principles for computing the
ideal partition of resources under uncertainty. These principles have
applicability to a wide variety of problems that can be divided into
interdependent phases of problem solving. After, we shall present
results of our empirical study of the problem of determining the
ideal amount of time to devote to searching for clusters in belief
networks. In this work, we acquired and made use of probability
distributions that characterize (1) the performance of alternative
heuristic searchmethods for reformulating a network instance into a
set of cliques, and (2) the time for executing inference procedures on
various belief networks. Given a preference model describing the value
of a solution as a function of the delay required for its computation,
the system selects an ideal time to devote toreformulation.
In: Proceedings of Sixth Conference on Uncertainty in Artificial
Intelligence, Cambridge, MA, Association for Uncertainty in
Artificial Intelligence, Mountain View, CA. July 1990. pp 64-72.
Keywords: Decision-theoretic control, Bayesian networks, bounded optimal systems, bounded optimality, decision-theoretic control of computation, metareasoning, rationality under bounded resources, probabilistic inference.