Deciding Consistency of Databases Containing Defeasible and Strict Information

Moisés Goldszmidt, Judea PearlUAI 1989

TL;DR

This paper introduces a formal framework for determining consistency in knowledge bases that mix "typical" (defeasible) rules with absolute (strict) rules. It proposes a probabilistic approach to define consistency and entailment, allowing for a clear distinction between exceptions and outright contradictions, and offers an efficient procedure for checking consistency.

What Problem Does This Paper Address?

In artificial intelligence and logic, representing knowledge often involves dealing with rules that are not always true. For example, "birds fly" is a general rule, but penguins are an exception. Traditional logic struggles with these exceptions, leading to the development of non-monotonic reasoning. This paper tackles a specific challenge within non-monotonic reasoning: how to formally define and detect inconsistencies when a knowledge base contains both "defeasible" statements (like "typically, penguins are birds") and "strict" statements (like "all birds fly"). The authors argue that existing formalisms don't adequately distinguish between a knowledge base that simply describes exceptions and one that is fundamentally contradictory, leading to intuitive problems. For instance, a knowledge base stating "all birds fly" and "typically, penguins don't fly" feels inherently wrong, not just a description of an exceptional class.

Methods

The core of the paper's methodology lies in a probabilistic interpretation of logical statements.

  • Probabilistic Consistency: They define consistency not as the possibility of a single truth assignment satisfying all statements, but as the existence of a probability distribution where defeasible statements can have arbitrarily high probability (approaching certainty) and strict statements have probability exactly 1. This allows for "near misses" for defeasible rules.
  • Probabilistic Entailment: A conclusion is considered "p-entailed" if it can be assigned arbitrarily high probability in all probability distributions that satisfy the knowledge base.
  • Tolerance and Confirmation: To operationalize consistency, they introduce "tolerance" (a statement is tolerated if it can be verified without falsifying any other statement) and "confirmation" (a set of statements is confirmable if its non-empty subsets are tolerated).
  • Decision Procedure: They derive a theorem that links p-consistency to the confirmability of all non-empty subsets. This leads to an effective, albeit potentially computationally intensive, procedure for testing consistency and identifying inconsistent subsets.

Datasets

Not discussed in the paper. The paper focuses on formalizing consistency and entailment for abstract knowledge bases, using illustrative examples rather than specific datasets.

Key Insights and Ideas

  • Distinguishing Contradictions from Exceptions: The probabilistic framework elegantly separates knowledge bases that describe exceptions (e.g., "penguins don't fly" is an exception to "birds fly") from those that are fundamentally contradictory (e.g., "all birds fly" and "typically, penguins don't fly" when penguins are known to be birds). The former can be made consistent with high probabilities, while the latter cannot.
  • The Importance of "Proper" Probability Distributions: Requiring probability distributions to be "proper" (i.e., not assigning zero probability to antecedents of conditional statements) is crucial. This ensures that statements about non-empty classes are meaningful and prevents trivial consistency.
  • Consistency as Confirmability of Subsets: The key theoretical result is that a knowledge base is consistent if and only if every non-empty subset of its statements is "confirmable." This provides a concrete, albeit potentially complex, criterion for checking consistency.
  • Strict vs. Defeasible Entailment: The paper distinguishes between "p-entailment" (high probability) and "strict p-entailment" (certainty), highlighting that strict rules cannot be derived from defeasible ones alone.

Key Results

  • A formal definition of probabilistic consistency for knowledge bases with defeasible and strict sentences.
  • A characterization of consistency based on the "confirmability" of all non-empty subsets of sentences.
  • An effective, two-phase procedure for testing consistency and identifying inconsistent subsets.
  • The worst-case complexity for testing consistency is bounded by O[PS × (|D| + |S|)], where PS is the complexity of propositional satisfiability for the material counterparts of the sentences, |D| is the number of defeasible sentences, and |S| is the number of strict sentences.
  • For Horn clauses, consistency testing can be done in polynomial time.

Limitations and Future Work

  • Computational Complexity: While an effective procedure is provided, its worst-case complexity can be high, especially if the underlying propositional satisfiability problem is hard. The authors note that for Horn clauses, this complexity becomes polynomial.
  • Chaining and Contraposition: The authors acknowledge that their definition of p-entailment is conservative and does not readily support chaining of defeasible rules or contraposition, which are desirable properties in some reasoning systems.
  • Future Work: The paper suggests several avenues for future research, including developing a graphical decision criterion for consistency in mixed inheritance networks and exploring more powerful notions of entailment.

Summary updated

BibTeX
@inproceedings{goldszmidt1989deciding,
  author = {Moisés Goldszmidt and Judea Pearl},
  title = {{Deciding Consistency of Databases Containing Defeasible and Strict Information}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1989},
}
Figure