Belief propagation in Qualitative Probabilistic Networks

Authors:

Marek J. Druzdzel
Carnegie Mellon University
Department of Engineering and Public Policy
(currently with:
University of Pittsburgh
Department of Information Science
and Intelligent Systems Program
e-mail: marek@sis.pitt.edu)

Max Henrion
Rockwell International Science Center
Palo Alto Laboratory
e-mail: henrion@sumex-aim.stanford.edu
(currently with:
Lumina Decision Systems)

Abstract:

Qualitative probabilistic networks (QPNs) (Wellman 1990) are an abstraction of influence diagrams and Bayesian belief networks replacing numerical relations by qualitative influences and synergies. To reason in a QPN is to find the effect of decision or new evidence on a variable of interest in terms of the sign of the change in belief (increase or decrease). We review our work on qualitative belief propagation, a computationally efficient reasoning scheme based on local sign propagation in QPNs. Qualitative belief propagation, unlike the existing graph-reduction algorithm, preserves the network structure and determines the effect of evidence on all nodes in the network. We show how this supports meta-level reasoning about the model and automatic generation of intuitive explanations of probabilistic reasoning.