Non-monotonicity in probabilistic reasoning

Benjamin N. GrosofUAI 1986

TL;DR

This paper explores how to formalize non-monotonic reasoning within probabilistic frameworks, moving beyond traditional logic. It proposes a method called Specificity-Prioritized Maximization of Conditional Independence (SPMCI) to handle situations where new information can invalidate previous conclusions, akin to "default inheritance" in categorical reasoning. This work is crucial for building more robust and human-like AI systems that can reason with uncertainty and adapt to new evidence.

What Problem Does This Paper Address?

Probabilistic reasoning is often described as "non-monotonic," meaning that adding new information can sometimes lead to revising or retracting previously drawn conclusions. This is a fundamental aspect of human reasoning, where we often make assumptions or "defaults" that are subject to revision when more specific or contradictory evidence emerges. However, formalizing this non-monotonicity within probabilistic logic has been challenging. Traditional probabilistic logic, while powerful, is inherently monotonic, meaning conclusions are always preserved when new information is added. This paper aims to bridge this gap by developing a formal framework for non-monotonic probabilistic reasoning that captures common patterns like "default inheritance" and "specificity."

Methods

The authors propose two main approaches to non-monotonic probabilistic reasoning:

  • Maximization of Conditional Independence (MCI): This approach focuses on maximizing conditional independence statements, which represent assumptions about how variables relate to each other given certain conditions. MCI aims to infer these independence statements in a non-monotonic way, allowing them to be overridden by more specific information.
  • Specificity-Prioritized Maximization of Conditional Independence (SPMCI): This is a refinement of MCI that explicitly handles situations where multiple default assumptions might conflict. SPMCI prioritizes conclusions based on the specificity of the information they are based on. For example, if we have a general rule about "Neptune cars" and a more specific rule about "Neptune Triton cars," SPMCI would favor the conclusion derived from the Triton rule if it conflicts with the general Neptune rule.

To formalize these ideas, the authors leverage Pointwise Circumscription, a variant of circumscription logic designed for non-monotonic reasoning. This allows them to express minimality conditions on "abnormality" predicates, effectively prioritizing certain conclusions or assumptions over others. They also discuss Maximum Entropy (ME) as another approach to non-monotonic reasoning, noting its relationship and differences with SPMCI.

Datasets

Not discussed in the paper. The paper focuses on formalizing reasoning principles rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Probabilistic reasoning can be non-monotonic: The paper establishes that the notion of non-monotonicity, well-understood in categorical logic, can be meaningfully applied to probabilistic reasoning.
  • "Default Inheritance" in probabilities: A key insight is that common probabilistic reasoning patterns, like assuming a general probability applies to a specific case when no contrary information exists, can be formalized. This is analogous to "default inheritance" in categorical reasoning (e.g., "birds fly" is a default, but "ostriches" are an exception).
  • Specificity is key to resolving conflicts: When multiple probabilistic defaults conflict, the paper argues that prioritizing conclusions based on the specificity of the conditioning information is a natural and effective strategy.
  • Pointwise Circumscription as a formalization tool: This logical formalism proves to be a powerful tool for expressing and implementing the proposed non-monotonic probabilistic reasoning principles, particularly for handling priorities.
  • MCI as maximizing irrelevance: The paper suggests that MCI can be viewed as a way to maximize irrelevance, which aligns with principles of simplicity and efficiency in reasoning.

Key Results

The paper doesn't present quantitative results in terms of accuracy or performance metrics on specific tasks. Instead, its key results are:

  • A formal framework for non-monotonic probabilistic reasoning: The paper provides a theoretical foundation for reasoning with probabilistic defaults and exceptions.
  • The SPMCI principle: This principle offers a concrete method for handling conflicting probabilistic defaults by prioritizing more specific information.
  • Formalization of SPMCI using Pointwise Circumscription: This demonstrates how existing non-monotonic logic tools can be adapted for probabilistic contexts.
  • Identification of "default inheritance" and "default irrelevance" as key types of non-monotonic probabilistic reasoning.

Limitations and Future Work

  • Computational Efficiency: The authors acknowledge that making non-monotonic probabilistic reasoning efficient is a significant open challenge. Current ME algorithms, for instance, can be computationally expensive.
  • Specifying MCI/SPMCI: An open question is which conditional independence statements to maximize and what priorities to assign. The paper suggests that indiscriminate MCI is undesirable and prioritization is often needed.
  • Relationship with Maximum Entropy: The exact relationship between ME and SPMCI, particularly how ME produces MCI and whether it's compatible with specificity prioritization, is an area of ongoing investigation.
  • Bayesian and Decision Theory Foundations: The paper mentions investigating the basis in Bayesian statistical estimation and decision theory for the "default inheritance" principle.
  • Formalization of intended models: The authors are still investigating whether their proposed circumscriptive formalization of (SP)MCI truly captures its intended models.
  • Practical application: While the paper lays theoretical groundwork, applying these methods efficiently in goal-directed computations remains a challenge.

Summary updated

BibTeX
@inproceedings{grosof1986non,
  author = {Benjamin N. Grosof},
  title = {{Non-monotonicity in probabilistic reasoning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1986},
}
Figure