Efficient reasoning 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
email: henrion@camis.stanford.edu
(currently with:
Lumina Decision Systems)

Abstract:

Qualitative Probabilistic Networks (QPNs) are an abstraction of Bayesian belief networks replacing numerical relations by qualitative influences and synergies (Wellman 1990). To reason in a QPN is to find the effect of new evidence on each node in terms of the sign of the change in belief (increase or decrease). We introduce a polynomial time algorithm for reasoning in QPNs, based on local sign propagation. It extends our previous scheme from singly connected to general multiply connected networks. Unlike existing graph-reduction algorithms, it preserves the network structure and determines the effect of evidence on all nodes in the network. This aids meta-level reasoning about the model and automatic generation of intuitive explanations of probabilistic reasoning.