Entailment in Probability of Thresholded Generalizations

Donald BamberUAI 1996

TL;DR

This paper introduces "entailment in probability," a new nonmonotonic logic for reasoning with "thresholded generalizations" (e.g., "nearly everything with property A also has property B"). It provides a formal definition and a decision procedure, showing that this new logic is probabilistically trustworthy and closely related to existing systems like System-Z+.

What Problem Does This Paper Address?

Human reasoning often involves generalizations that aren't absolute. For instance, we know "birds can fly," but we also know there are exceptions (penguins, ostriches). This paper tackles how to formally reason with such "thresholded generalizations," where we acknowledge exceptions but assert that they are rare. Specifically, it addresses the challenge of defining a logical entailment relation that captures this probabilistic nature of generalizations. Traditional logic requires conclusions to be true in all cases where premises are true, which is too strict for everyday reasoning. The paper aims to define a "nonmonotonic" entailment relation – one where adding new premises can invalidate existing conclusions – that is "probabilistically trustworthy," meaning conclusions are highly likely to be true if the premises are.

Methods

The paper proposes a novel nonmonotonic entailment relation called "entailment in probability." This is built upon a formal framework for "thresholded generalizations," which are statements of the form "nearly everything with property $\alpha$ also has property $\beta$" qualified by an exception rate threshold.

Key methodological steps include:

  • Formalizing Thresholded Generalizations: Defining a syntax and semantics where generalizations are associated with a probability threshold for exceptions.
  • Two-Level Probability Structure: Introducing a model where at the lower level, a probability function assigns probabilities to properties, and at the upper level, a probability distribution over these models represents uncertainty about the true model.
  • Entailment with Certainty (Monotonic): As a stepping stone, defining a monotonic entailment relation that requires conclusions to hold in all models satisfying the premises. This is related to Adams' logic of conditionals.
  • Entailment in Probability (Nonmonotonic): Defining the core nonmonotonic entailment relation. This is achieved by requiring that nearly every model satisfying the premises also satisfies the conclusion. This is formalized using concepts like "probability order" and "stochastic analogs" of the monotonic definitions.
  • Depth Entailment: Introducing an alternative, "depth entailment" based on exception depths, which is shown to be equivalent to entailment in probability. This provides a practical decision procedure.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Probabilistically Trustworthy Conclusions: The central idea is that nonmonotonic entailment should guarantee that if the premises are true, the conclusion is improbable to be false. This is a crucial relaxation of classical logic's certainty requirement.
  • Two-Level Probability: The formalization using a probability distribution over models is a powerful way to capture uncertainty about the underlying probability space itself, which is essential for reasoning with generalizations.
  • Equivalence of Depth and Probability Entailment: The demonstration that "depth entailment" (based on exception depths) is equivalent to "entailment in probability" is a significant result. It provides a concrete, algorithmic way to test for probabilistic entailment, which is otherwise abstract.
  • Connection to System-Z+: The paper establishes a strong link between its proposed entailment relation and Goldszmidt and Pearl's System-Z+, showing that System-Z+'s conclusions are also probabilistically trustworthy and that the paper's framework offers a more robust justification for it.

Key Results

  • Formal Definition of Entailment in Probability: A precise definition (Definition 15) is provided for nonmonotonic entailment based on thresholded generalizations.
  • Decision Procedure: Theorem 27 shows that entailment in probability is equivalent to "depth entailment," for which a decision procedure is outlined (Section 6.2). This means we can algorithmically determine if a set of generalizations entails another.
  • Probabilistic Trustworthiness Guaranteed: The proposed entailment relation ensures that conclusions are probabilistically trustworthy.
  • Relationship to System-Z+: The paper demonstrates that its entailment in probability is closely related to System-Z+, providing a probabilistic justification for System-Z+'s reasoning.

Limitations and Future Work

  • Unknown Parameters ($\psi$, $\delta$): The definitions of thresholded generalizations and entailment involve parameters ($\psi$, $\delta$) that are assumed to be positive and small, respectively, but their exact values are unknown. The definitions are designed to be robust to these unknown values, often by considering asymptotic behavior as $\delta$ approaches zero. However, the practical implications of specific choices of $\psi$ and $\delta$ are not deeply explored.
  • Language Independence: While Theorem 27 suggests entailment is language independent, the paper doesn't delve into the implications of this for different logical languages or the complexity of inference in larger languages.
  • Computational Complexity: While a decision procedure is presented, the paper does not analyze the computational complexity of this procedure.
  • Future Work: The paper suggests that the framework provides a more sound footing for System-Z+ and its conclusions. Further exploration of the properties of inference, complexity, and practical applications of this entailment relation would be valuable. The paper also notes that its definition of entailment in probability is a stochastic analog of entailment with certainty, hinting at potential extensions or comparisons with other probabilistic logics.

Summary updated

BibTeX
@inproceedings{bamber1996entailment,
  author = {Donald Bamber},
  title = {{Entailment in Probability of Thresholded Generalizations}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure