Figure: The four main methods for Q-DAG reduction.
The goal of Q-DAG reduction is to reduce the size of a Q-DAG while
maintaining the arithmetic expression it represents.
In describing the equivalence of arithmetic expressions,
we define the notion of Q-DAG equivalence:
Figure [*] shows four basic reduction operations that we have experimented with:
We have proven that these operations are sound in [Darwiche ProvanDarwiche \ Provan1995]. Based on an analysis of network structure and preliminary empirical results, we have observed that many factors govern the effectives of these operations. The degree to which reduction operations, numeric reduction in particular, can reduce the size of the Q-DAG depends on the topology of the given belief network and the set of evidence and query variables. For example, if all root nodes are evidence variables of the belief network, and if all leaf nodes are query variables, then numeric reduction will lead to little Q-DAG reduction.
We now focus on numeric reduction, showing how it sometimes subsumes two optimization techniques that have been influential in belief network algorithms. For both optimizations, we show examples where an unoptimized algorithm that employs numeric reduction yields the same Q-DAG as an optimized algorithm. The major implication is that optimizations can be done uniformly at the Q-DAG level, freeing the underlying belief network algorithms from such implementational complications.
The following examples assume that we are applying the polytree algorithm to singly-connected networks.