Personal

Silja Renooij

http://www.dramaqueendom.com/summary.jpg

Links

Qualitative Probabilistic Networks

This page gives an overview of research on the subject of QPNs. QPN is short for `Qualitative Probabilistic Network', and has nothing to do with `Queueing Petri Nets', `Quiz and Poll Networks', or anything else that uses this abbreviation.

Qualitative probabilistic networks can be seen as qualitative abstractions of probabilistic, or Bayesian (belief), networks: a directed acyclic graph is used to model probabilistic (in)dependence, but instead of providing conditional probabilities to encode a joint probability distribution, only constraints on conditional probability distributions are required.

Qualitative probabilistic networks were first introduced by Mike Wellman as qualitative abstractions of Influence Diagrams in Fundamental Concepts of Qualitative Probabilistic Networks.

Qualitative relationships

Initially, Wellman introduced QPNs that could model two types of monotone probabilistic relationship based on stochastic dominance properties of conditional probability distributions: A probabilistic relationship has associated a sign that indicates a property of the modelled constraint. This sign can be a `+', a `-', a `0' or a `?'.

Max Henrion and Marek Druzdzel introduced an additional type of qualitative relationship:

Wellman and Henrion studied the relation between the two types of synergy and the relation between product synergy and a special kind of intercausal reasoning: explaining away. Details can be found in:
  1. M. Henrion, M.J. Druzdzel (1991). Qualitative propagation and scenario-based approaches to  explanation in probabilistic reasoning. Uncertainty in Artificial Intelligence, 6. Elsevier Science Publishers, North-Holland, pp. 17-32.
  2. M.J. Druzdzel, M. Henrion (1993). Intercausal reasoning with uninstantiated ancestor nodes. Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, San Francisco, pp. 317-325.
  3. M.P. Wellman, M. Henrion (1991). Qualitative intercausal relations, or explaining ``explaining away''. Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, pp. 535-546.
  4. M.P. Wellman , M. Henrion (1993). Explaining ``explaining away''. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, pp. 287-291.
Generalising the approach provided by QPNs to abstractions of other uncertainty handling formalisms, Simon Parsons introduced Qualitative Certainty Networks (QCNs). Compared to a 'regular' QPN, QCNs define two other types of probabilistic relations: More details on QCNs can be found in
  1. S. Parsons (1995). Refining reasoning in qualitative probabilistic networks. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, San Francisco, pp. 427-434.
  2. S. Parsons (2001). Qualitative Methods for Reasoning under Uncertainty. MIT Press, Cambridge, Massachusetts.

Qualitative inference

Wellman introduced an inference algorithm for probabilistic inference in qpns that is based on: For details see:
  1. M.P. Wellman (1990). Fundamental concepts of qualitative probabilistic networks. Artificial Intelligence, vol. 40, pp. 257-303.
  2. M.P. Wellman (1990). Graphical inference in qualitative probabilistic networks. Networks, vol. 20, pp. 687-701.
Druzdzel and Henrion introduced a different algorithm for inference in QPNS. Instead of reducing the graph, their algorithm is based on passing messages containing signs through the graph. First they introduced a sign-propagation algorithm for singly connected digraphs; this was later extended to multiply connected digraphs. For details see:
  1. M. Henrion, M.J. Druzdzel (1991). Qualitative propagation and scenario-based approaches to explanation in probabilistic reasoning. Uncertainty in Artificial Intelligence, 6. Elsevier Science Publishers, North-Holland, pp. 17-32.
  2. M.J. Druzdzel, M. Henrion (1993). Efficient reasoning in qualitative probabilistic networks. Proceedings of the Eleventh National Conference on Artificial Intelligence. AAAI Press, Menlo Park, pp. 548-553.
  3. M.J. Druzdzel (1993). Probabilistic Reasoning in Decision Support Systems: From Computation to Common Sense. PhD Thesis, Department of Engineering and Public Policy, Carnegie Mellon University, Pittsburgh, PA.
The sign-propagation algorithm was designed to handle a single observation at a time. Different methods exist to determine the joint effect of a set of observations. For details see:
  1. M.J. Druzdzel (1993). Probabilistic Reasoning in Decision Support Systems: From Computation to Common Sense. PhD Thesis, Department of Engineering and Public Policy, Carnegie Mellon University, Pittsburgh, PA.
  2. S. Renooij, L.C. van der Gaag, S. Parsons (2002). Propagation of multiple observations in QPNs revisited. Proceedings of the Fifteenth European Conference on Artificial Intelligence, IOS Press, Amsterdam, pp. 665-669.
In multiply connected digraphs, qualitative inference can easily lead to ambiguous results due to the presence of trade-offs in the network. Druzdzel and Henrion have identified different sources of ambiguity; Renooij et. al provide an algorithm for identifying trade-offs in networks along with the information necessary to resolve them. For details see:
  1. M.J. Druzdzel, M. Henrion (1993). Belief propagation in qualitative probabilistic networks. In: N. Piera Carrete, M.G.  Singh (Editors). Qualitative Reasoning and Decision Technologies. CIMNE, Barcelona, pp. 451-460.
  2. S. Renooij, L.C. van der Gaag, S. Parsons, S. Green (2000). Pivotal pruning of trade-offs in QPNs.  Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers, San Francisco, pp. 515-522.
  3. S. Renooij (2001). Qualitative Approaches to Quantifying Probabilistic Networks. Ph.D. Thesis, Institute for Information and Computing Sciences, Utrecht University, The Netherlands.

Enhancements of qualitative probabilistic networks

Context (in)dependence

Qualitative influences can only be represented with an unambiguous sign, if they are monotonic, that is, if the sign is independent of the values of other variables in the network than the two between which the influence exists. The sign can then be thought of as being context independent. Renooij and Van der Gaag have shown that non-monotonic influences can sometimes be reduced to monotonic ones, using the additive synergy. With Bolt, they introduced influences capturing the prior effect of a generally non-monotonic influence. More in general, information about signs in different contexts is captured by using context-specific signs. For details see:
  1. S. Renooij, L.C. van der Gaag (1998). Decision making in qualitative influence diagrams.  Proceedings of the Eleventh International FLAIRS Conference, AAAI Press, Menlo Park, California, pp. 410-414.
  2. S. Renooij, L.C. van der Gaag (2000). Exploiting non-monotonic influences in qualitative belief networks. Proceedings of the Eighth International Conference on Information Processing and Management of Uncertainty, Madrid, pp. 1285-1290.
  3. J.H. Bolt, S. Renooij, L.C. van der Gaag (2003). Upgrading Ambiguous Signs in QPNs. Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers, San Francisco, pp. 73-80.
  4. S. Renooij, L.C. van der Gaag, S. Parsons (2002). Context-specific sign-propagation in qualitative probabilistic networks. Artificial Intelligence, vol. 140, pp. 207-230.

A notion of strength

When trade-offs are modelled in a qualitative network, inference will give ambiguous and thus uninformative results. To overcome this problem, at least ot some extent, different approaches for introducing a notion of strength into QPNs have been proposed, based on either absolute or relative (orders of) magnitudes. For details see:
  1. S. Parsons (1995). Refining reasoning in qualitative probabilistic networks. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, San Francisco, pp. 427-434.
  2. S. Renooij, L.C. van der Gaag (1999). Enhancing QPNs for trade-off resolution. Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers, San Francisco, California, pp. 559-566.
  3. S. Renooij, S. Parsons, P. Pardieck (2003). Using Kappas as Indicators of Strength in Qualitative Probabilistic Networks.Proceedings of the Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Lecture Notes in Artificial Intelligence, ©Springer Verlag, pp. 87-99.

Applications for qualitative probabilistic networks

Probability elicitation

In constructing probabilistic networks, especially when doing this by hand, knowledge acquisition can be facilitated by taking advantage of easily acquired qualitative information and by not requiring exact values. Qualitative probabilistic relations can therefore be elicited prior to or as part of the probability elicitation process. The qualitative relations can be used either as constraints on the probability distributions to be assessed, or for studying the reasoning behaviour of the quantitative network under construction. See e.g.
  1. M.J. Druzdzel, L.C. van der Gaag (1995). Elicitation of probabilities for belief networks: combining qualitative and quantitative information. Proceedingsof the Eleventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers, San Francisco, pp. 141-148.
  2. S. Renooij (2001). Qualitative Approaches to Quantifying Probabilistic Networks. Ph.D. Thesis, Institute for Information and Computing Sciences, Utrecht University, The Netherlands.
  3. S. Renooij, L.C. van der Gaag (2002). From qualitative to quantitative probabilistic networks. Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers, San Francisco, pp. 422 - 429.
To facilitate probability elicitation, often the interactions between variables are assumed to correspond to a noisy-or. Different authors have discussed the relationship between the noisy-or and the different qualitative relations; some also discuss Occam's razor. See e.g.
  1. M.P. Wellman (1990). Fundamental concepts of qualitative probabilistic networks. Artificial Intelligence, vol. 40, pp. 257-303.
  2. M.J. Druzdzel, M. Henrion (1993). Efficient reasoning in qualitative probabilistic networks. Proceedings of the Eleventh National Conference on Artificial Intelligence. AAAI Press, Menlo Park, pp. 548-553.
  3. M.J. Druzdzel, M. Henrion (1993). Belief propagation in qualitative probabilistic networks. In: N. Piera Carrete, M.G. Singh (Editors). Qualitative Reasoning and Decision Technologies. CIMNE, Barcelona, pp. 451-460.
  4. M.P. Wellman , M. Henrion (1993). Explaining ``explaining away''. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, pp. 287-291.
  5. J.Mark. Agosta (1991) Conditional inter-causally independent node distributions, a property of noisy-or models. Proceedings of the Seventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, San Francisco, pp. 9-16.

Explanation

Druzdzel used QPNs to generate verbal explanantions of probabilistic reasoning. See
  1. M. Henrion, M.J. Druzdzel (1991). Qualitative propagation and scenario-based approaches to explanation in probabilistic reasoning. Uncertainty in Artificial Intelligence, 6. Elsevier Science Publishers, North-Holland, pp. 17-32.
  2. M.J. Druzdzel (1993). Probabilistic Reasoning in Decision Support Systems: From Computation to Common Sense. PhD Thesis, Department of Engineering and Public Policy, Carnegie Mellon University, Pittsburgh, PA.

Qualitative decision making and planning

As first introduced by Wellman, QPNs were intended to support qualitative decision making by means of the additive synergy. See e.g.
  1. M.P. Wellman (1990). Fundamental concepts of qualitative probabilistic networks. Artificial Intelligence, vol. 40, pp. 257-303.
  2. S. Renooij, L.C. van der Gaag (1998). Decision making in qualitative influence diagrams. Proceedings of the Eleventh International FLAIRS Conference, AAAI Press, Menlo Park, California, pp. 410-414.

Argumentation

Parsons studied the relation between QPNs and systems for argumentation. Prakken and Renooij use a QPN to construct legal arguments. See
  1. Simon Parsons, Shaw Greene: Argumentation and Qualitative Decision Making. ESCQARU 1999: 328-340
  2. H. Prakken, S. Renooij (2001). Reconstructing causal reasoning about evidence: A case study.   Legal Knowledge and Information Systems. JURIX 2001:The Fourteenth Annual Conference, IOS Press, Amsterdam, pp. 131-142.