This section is focused on reducing Q-DAGs after they have been generated. The main motivation behind this reduction is twofold: faster evaluation of Q-DAGs and less space to store them. Interestingly enough, we have observed that a few, simple reduction techniques tend in certain cases to subsume optimization techniques that have been influential in practical implementations of belief-network inference. Therefore, reducing Q-DAGs can be very important practically.
This section is structured as follows. First, we start by discussing four simple reduction operations in the form of rewrite rules. We then show examples in which these reductions subsume two key optimization techniques known as network-pruning and computation-caching.