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.
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.