[Next] [Up] [Previous]
Next: Optimization in Belief-Network Inference Up: Reducing Query DAGs Previous: Network Pruning

Computation Caching

Figure: A simple belief network for demonstrating the relationship between Q-DAG reduction and computation caching. The light-shaded node, tex2html_wrap1014, is a query node, and the dark-shaded node, tex2html_wrap1015, is an evidence node.  

Caching computations is another influential technique for optimizing inference in belief networks. To consider an example, suppose that we are applying the polytree algorithm to compute tex2html_wrap1668 in the network of Figure 11. Given evidence, say tex2html_wrap1669, the algorithm will compute tex2html_wrap1670 by passing the messages shown in Figure 12. If the evidence changes to tex2html_wrap1671, however, an algorithm employing caching will not recompute the message tex2html_wrap1672 (which represents the causal support from tex2html_wrap1256 to tex2html_wrap1015 [PearlPearl1988]) since the value of this message does not depend on the evidence on tex2html_wrap1015.[+] This kind of optimization is typically implemented by caching the values of messages and by keeping track of which messages are affected by what evidence.

Figure 12: Message passing when C is queried and B is observed.

Now, consider the Q-DAG corresponding to this problem which is shown in Figure 13(a). The nodes enclosed in dotted lines correspond to the message from tex2html_wrap1256 to tex2html_wrap1015.[+] These nodes do not have evidence-specific nodes in their ancestor set and, therefore, can never change values due to evidence changes. In fact, numeric reduction will replace each one of these nodes and its ancestors with a single node as shown in Figure 13(b).

In general, if numeric reduction is applied to a Q-DAG, one is guaranteed the following: (a) if a Q-DAG node represents a message that does not depend on evidence, that node will not be re-evaluated given evidence changes; and (b) numeric reduction will guarantee this under any Q-DAG evaluation method since it will replace the node and its ancestor set with a single root node.[+]

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

[Next] [Up] [Previous]
Next: Optimization in Belief-Network Inference Up: Reducing Query DAGs Previous: Network Pruning