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 arithmeticexpression called a Query DAG (Q-DAG); and (2) answering queries using a simpleevaluation algorithm. Each node of a Q-DAG represents a numeric operation, anumber, or a symbol for evidence. Each leaf node of a Q-DAG represents theanswer 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 algorithmsfor exact inference in belief networks (we show how they can be generated usingclustering and conditioning algorithms). The time and space complexity of aQ-DAG generation algorithm is no worse than the time complexity of theinference algorithm on which it is based. The complexity of a Q-DAG evaluationalgorithm is linear in the size of the Q-DAG, and such inference amounts to astandard evaluation of the arithmetic expression it represents. The intendedvalue of Q-DAGs is in reducing the software and hardware resources required toutilize belief networks in on-line, real-world applications. The proposedframework also facilitates the development of on-line inference on differentsoftware and hardware platforms due to the simplicity of the Q-DAG evaluationalgorithm. Interestingly enough, Q-DAGs were found to serve other purposes:simple techniques for reducing Q-DAGs tend to subsume relatively complexoptimization techniques for belief-network inference, such as network-pruningand computation-caching.