The Probability of a Possibility: Adding Uncertainty to Default Rules

Craig BoutilierUAI 1993 · OpenReview

TL;DR

This paper introduces a novel framework for combining probabilistic reasoning with default logic and belief revision. It allows for expressing conditional statements like "If A were true, B would be believed to degree p," bridging the gap between qualitative default rules and quantitative probabilistic updates, and offering a unified view of probability and possibility theory.

What Problem Does This Paper Address?

Traditional conditional logics for default reasoning and belief revision, like the AGM theory, handle information in a categorical way: a statement is either believed or not. This works well for strict logical inference but struggles to represent uncertainty in conclusions or the degree to which a default rule might hold. For instance, if an agent learns a new piece of information that contradicts its beliefs, existing methods might force a complete retraction of beliefs. Similarly, while probabilistic methods can handle degrees of belief, they typically break down when dealing with conditions that have zero probability (e.g., updating beliefs based on an event that was considered impossible). This paper addresses the need for a system that can express uncertain default rules and perform belief revisions even when faced with seemingly impossible antecedents, effectively extending conditionalization to handle zero-probability events.

Methods

The authors propose a "counterfactual probability model" (CPM) that builds upon possibility theory. A CPM combines a possibility model (which assigns degrees of possibility to worlds) with a probability distribution over "possible" worlds. This allows for:

  • Counterfactual Probabilities: Defining the probability of a statement B given a statement A, even when the probability of A is zero. This is achieved by considering the most plausible worlds where A holds and assigning relative probability weights to them.
  • Belief Revision: Extending the AGM theory by allowing revised belief sets to incorporate degrees of belief. The revision process is described as "counterfactual conditionalization."
  • Unification: Demonstrating how this framework unifies probability theory and possibility theory. Possibility theory is used to rank worlds and handle qualitative aspects of belief revision (like the "Ramsey test" for conditionals), while probability theory assigns weights to these worlds to capture degrees of belief and uncertainty.
  • Generalized Imaging: Showing that their revision method can be viewed as a form of generalized imaging, a technique for updating beliefs that can handle zero-probability antecedents and offers a more nuanced approach than standard conditionalization.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Qualitative-Quantitative Divide: The core insight is that by combining possibility theory (for qualitative plausibility and ranking) with probability theory (for quantitative degrees of belief), we can create a richer model of reasoning.
  • Handling Zero-Probability Events: The framework provides a principled way to update beliefs based on events that were previously considered impossible, a significant limitation of standard conditionalization.
  • Unified View of Reasoning: The paper suggests that probability and possibility theory, often seen as distinct, can be integrated to provide a more comprehensive account of belief representation and revision.
  • Extending AGM: The proposed model conserves the desirable properties of the AGM theory of belief revision while adding the crucial ability to represent and reason with uncertain conclusions.

Key Results

The paper presents several theoretical results:

  • Theorem 1: A possibility model induces a revision function satisfying the AGM postulates, and vice-versa.
  • Proposition 4: The revised probability function derived from a CPM is a valid probability function, provided the update condition has a non-zero possibility.
  • Theorem 5: The revision process aligns with the truth conditions of the conditional connective (⇒), meaning if A ⇒ B holds, then after revising with A, B will have a probability of 1.
  • Theorem 7: When the update condition A has a non-zero probability, the counterfactual conditionalization reduces to standard conditionalization.
  • Theorem 10: The proposed revision method is equivalent to generalized imaging, offering a unified perspective on belief update mechanisms.

Limitations and Future Work

The authors acknowledge several areas for future work:

  • Deriving New Counterfactual Probabilities: The current model specifies the updated factual probability function but leaves the derivation of new counterfactual probabilities (when the condition has zero probability) underspecified.
  • Iterated Revision: The paper does not fully address how to handle sequences of revisions or how to iterate the process of updating counterfactual probabilities.
  • Practical Constraints: While the framework is theoretically sound, practical applications might require identifying constraints on how probabilities are updated, especially when dealing with unrelated propositions.
  • Application to Diagnosis: The authors mention ongoing work exploring the use of counterfactual probabilities in model-based diagnosis, suggesting this as a promising application area.

Summary updated

Abstract

We present a semantics for adding uncertainty to conditional logics for default reasoning and belief revision. We are able to treat conditional sentences as statements of conditional probability, and express rules for revision such as "If A were believed, then B would be believed to degree p." This method of revision extends conditionalization by allowing meaningful revision by sentences whose probability is zero. This is achieved through the use of counterfactual probabilities. Thus, our system accounts for the best properties of qualitative methods of update (in particular, the AGM theory of revision) and probabilistic methods. We also show how our system can be viewed as a unification of probability theory and possibility theory, highlighting their orthogonality and providing a means for expressing the probability of a possibility. We also demonstrate the connection to Lewis's method of imaging.
BibTeX
@inproceedings{boutilier1993probability,
  author = {Craig Boutilier},
  title = {{The Probability of a Possibility: Adding Uncertainty to Default Rules}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1993},
  url = {https://openreview.net/forum?id=c5b884Idcqr},
}
Figure