Application Programmers Manual: Relevance Reasoning

Reasoning in graphical models in SMILE can be preceded by a preprocessing step that explores structural and numerical properties of the model to determine which parts of the network are needed to perform computation.

Relevance reasoning reduces the size and the connectivity of a network by pruning nodes that are computationally irrelevant to the nodes of interest in the network. Therefore, it can help in reducing the complexity of inference in a network. Sometimes, users may not be interested in every node in the network. Those nodes of interest are called target nodes. Relevance reasoning is used to obtain the smallest sub-network which contains all the necessary information to compute the values of the target nodes. For example, if the goal is to compute the posterior distribution of a node, then nodes that have up to date distributions do not need to be included in computation. Similarly, if the user has selected a subset of nodes to be the target nodes, nodes that are neither target nor evidence do not need to be included in reasoning. Relevance algorithms are very fast and usually lead to substantial savings in computation. We call this preprocessing step collectively relevance reasoning. Relevance reasoning is transparent to the application programmer.

This sub-network will then be updated and the values for the target nodes will be calculated. To set a node to be target, the SetTarget() network method should be used. To clear or ask the target status of a node UnSetTarget() or IsTarget() methods should used. It is important to note that if no nodes are marked as targets in a given network, the library will assume that all the nodes are of interest to the user (i.e., all of them are target nodes).

Relevance reasoning comprises several steps:

• Evidence propagation

Under some circumstances, evidence nodes can imply the values of their neighboring nodes (their parents or their children). Evidence propagation, instantiates nodes in the network if their values are directly implied by current evidence.

• Evidence absorption

Relevance reasoning absorbs instantiated nodes into the probability distribution of their children, and removes arcs between them.

• Barren node removal

A node is barren if it is neither an evidence nor a target node and it has no descendants or all of its descendants are barren. A probabilistically independent node is d-separated from the target nodes given evidence nodes. That is, the value of this node has no impact on the values of target nodes. Removing both barren nodes and probabilistically independent nodes will not change the values of target nodes.

• Nuisance node removal

A nuisance node is a node that is computationally related to target nodes given evidence nodes, but is not part of any evidence trail (or d-connecting path) from any evidence node to any target node. Relevance reasoning recursively removes those nuisance nodes with only one child and no parents by marginalizing them to their children.

Relevance reasoning can be activated/deactivated by using two of the network methods: ActivateRelevance() and DeactivateRelevance().

For more information on the implementation of relevance reasoning and its performance consult (Lin & Druzdzel 1997) and (Druzdzel & Suermondt 1994).