[Next] [Up] [Previous]

Reductions

 
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:

1. Identity elimination: eliminates a numeric node if it is an identity element of its child operation node.
2. Numeric reduction: replaces an operation node with a numeric node if all its parents are numeric nodes.
3. Associative merging: eliminates an operation node using operation associativity.
4. Commutative merging: eliminates an operation node using operation commutativity.

These rules can be applied successively and in different order until no more applications are possible.

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.

[Next] [Up] [Previous]