[Next] [Up] [Previous]
Next: Computation Caching Up: Reducing Query DAGs Previous: Reductions

## Network Pruning

Figure: A simple belief network before pruning (a) and after pruning (b). The light-shaded node, , is a query node, and the dark-shaded node, , is an evidence node.

Pruning is the process of deleting irrelevant parts of a belief network before invoking inference. Consider the network in Figure 9(a) for an example, where is an evidence variable and is a query variable. One can prune node from the network, leading to the network in Figure 9(b). Any query of the form has the same value with respect to either network. It should be clear that working with the smaller network is preferred. In general, pruning can lead to dramatic savings since it can reduce a multiply-connected network to a singly-connected one.

Figure: A Q-DAG (a) and its reduction (b).

If we generate a Q-DAG for the network in Figure 9(a) using the polytree algorithm, we obtain the one in Figure 10(a). This Q-DAG corresponds to the following expression,

If we generate a Q-DAG for the network in Figure 9(b), however, we obtain the one in Figure 10(b) which corresponds to the following expression,

As expected, this Q-DAG is smaller than the Q-DAG in Figure 10(a), and contains a subset of the nodes in Figure 10(a).

The key observation, however, is that the optimized Q-DAG in Figure 10(b) can be obtained from the unoptimized one in Figure 10(a) using Q-DAG reduction. In particular, the nodes enclosed in dotted lines can be collapsed using numeric reduction into a single node with value 1. Identity elimination can then remove the resulting node, leading to the optimized Q-DAG in Figure 10(b).

The more general observation, however, is that prunable nodes contribute identity elements when computing answers to queries. These contributions appear as Q-DAG nodes that evaluate to identity elements under all instantiations of evidence. Such nodes can be easily detected and collapsed into these identity elements using numeric reduction. Identity elimination can then remove them from the Q-DAG, leading to the same effect as network pruning.[+] Whether Q-DAG reduction can replace all possible pruning operations is an open question that is outside the scope of this paper.

[Next] [Up] [Previous]
Next: Computation Caching Up: Reducing Query DAGs Previous: Reductions

Darwiche&Provan