**Adnan Darwiche
Department of Mathematics
American University of Beirut
PO Box 11 - 236, Beirut, Lebanon
darwiche@aub.edu.lb **

**Gregory Provan
Rockwell Science Center
1049 Camino Dos Rios
Thousand Oaks, CA 91360
provan@risc.rockwell.com **

We describe a new paradigm for implementing inference in belief networks,
which consists of two steps:
(1) compiling a belief network into an arithmetic expression called
a Query DAG (Q-DAG);
and (2) answering queries using a simple evaluation algorithm.
Each node of a Q-DAG represents a numeric
operation, a number, or a symbol for evidence. Each leaf node of a Q-DAG
represents the answer to a network query, that is, the probability of some event
of interest. It appears that Q-DAGs can be generated using any of the
standard 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
Q-DAG *generation* algorithm is no worse than the time complexity of the
inference algorithm on which it is based. The complexity of a Q-DAG *
evaluation* algorithm is linear in the size of the Q-DAG, and such
inference amounts to a standard evaluation of the arithmetic expression it
represents. The intended value of Q-DAGs
is in reducing the software and hardware resources required to utilize belief
networks in on-line, real-world applications. The proposed framework also
facilitates the development of on-line inference on different software
and hardware platforms due to the simplicity of the Q-DAG evaluation algorithm.
Interestingly enough, Q-DAGs were found to serve other purposes: simple
techniques for reducing Q-DAGs tend to subsume relatively complex
optimization techniques for belief-network inference, such as
network-pruning and computation-caching.

- Introduction
- Query DAGs
- Generating Query DAGs
- Reducing Query DAGs
- A Diagnosis Example
- Concluding Remarks
- Proof of Theorem
- References
- About this document ...

Darwiche&Provan