Query DAGs: A Practical Paradigm for Implementing Belief-Network
  Inference
  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.
