Inference Algorithms: Relevance reasoning

From DSL

Very often in a decision support system, only a small number of variables need updating, either because they are up to date or because they are of no interest to the user. When the model used by the system is large, the amount of computation to update all variables may be prohibitive, while potentially unnecessary. Reasoning in GeNIe and the underlying SMILE is always preceded by a preprocessing step that explores structural and numerical properties of the model to determine what part of the network is needed to perform computation.

GeNIe keeps track which variables are up to date and which are not and marks them by the node status icon. It also allows the model builder to designate those variables that are of interest to the user as targets. Target nodes (marked by the node status icon) are always guaranteed to be updated by the program during its updating procedure. Other nodes, i.e., nodes that are not designated as targets, may be updated or not, depending on the internals of the algorithm used, but are not guaranteed to be updated. When no nodes are designated as targets, GeNIe assumes that all variables in the model are of interest to the user, i.e., all of them are targets.

Relevance-based algorithms implemented in GeNIe are described in (Druzdzel & Suermondt 1994) and (Lin & Druzdzel 1997, 1998). 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 user and the application programmer.

GeNIe has been written with teaching graphical models in mind. One of the fundamental concepts on which graphical models are built is conditional independence and relevance (Dawid 1979). In order to demonstrate how nodes are relevant to target variables and to evidence variables, GeNIe allows its user in a mode that does not immediately update nodes after the user has entered an observation or made a change in the model. This mode is also useful in case of an editing session. When editing a network, posterior probabilities may be of little interest. When the model is very large, consisting for example of hundreds of variables, this mode improves reaction time.