Query DAGs: A Practical Paradigm for Implementing Belief Network Inference
Adnan Darwiche, Gregory Provan
Abstract:
We describe a new paradigm for implementing inference in belief networks, which relies on compiling a belief network into an arithmetic expression called a Query DAG (QDAG). Each nonleaf node of a QDAG represents a numeric operation, a number, or a symbol for evidence. Each leaf node of a QDAG represents the answer to a network query, that is, the probability of some event of interest. It appears that QDAGs can be generated using any of the algorithms for exact inference in belief networks  we show how they can be generated using clustering and conditioning algorithms. The time and space complexity of a QDAG generation algorithm is no worse than the time complexity of the inference algorithm on which it is based; that of a QDAG online evaluation algorithm is linear in the size of the QDAG, and such inference amounts to a standard evaluation of the arithmetic expression it represents. The main value of QDAGs is in reducing the software and hardware resources required to utilize belief networks in online, realworld applications. The proposed framework also facilitates the development of online inference on different software and hardware platforms, given the simplicity of the QDAG evaluation algorithm. This paper describes this new paradigm for probabilistic inference, explaining how it works, its uses, and outlines some of the research directions that it leads to.
Keywords: Computation under scarce resources, automated construction of decision
models, algor
Pages: 203210
PS Link: http://rpal.rockwell.com/~darwiche/papers/uai96.ps.gz
PDF Link: /papers/96/p203darwiche.pdf
BibTex:
@INPROCEEDINGS{Darwiche96,
AUTHOR = "Adnan Darwiche
and Gregory Provan",
TITLE = "Query DAGs: A Practical Paradigm for Implementing Belief Network Inference",
BOOKTITLE = "Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI96)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1996",
PAGES = "203210"
}

