A Probabilistic Interpretation for Lazy Nonmonotonic Reasoning

Ken SatohAAAI 1990

Abstract

This seminal 1990 paper by Ken Satoh bridges the gap between symbolic logic and probability theory. It provides a formal proof that "rational" nonmonotonic reasoning—a system characterized by "lazy" belief revision—is mathematically equivalent to a specific type of probabilistic limit. By assigning exponentially higher probabilities to "more normal" states, Satoh demonstrates that logical "laziness" has a rigorous foundation in probability theory.

The Problem: Grounding Nonmonotonic Logic

In classical logic, adding new information never reduces the set of known truths (monotonicity). However, human reasoning is often nonmonotonic: we hold default assumptions (e.g., "birds fly") until we encounter specific counter-evidence (e.g., "Tweety is a penguin").

By the late 1980s, researchers had identified "rational consequence relations" as the gold standard for nonmonotonic reasoning. These relations follow a set of logical rules that describe how a "lazy" reasoner—one who only changes their mind when absolutely necessary—should behave.

The axioms defining a rational consequence relation, including Rational Monotony (7).

While these rules (shown above) were logically intuitive, they lacked a formal probabilistic justification. Satoh’s work aimed to provide the "Rosetta Stone" connecting these symbolic rules to the quantitative world of probability.

The Probabilistic Limit and Ranked Models

Satoh’s core innovation is the use of a parameterized probability function $P_x$. He defines a system where the probability of a state depends on a positive parameter $x$. As $x$ approaches zero, the "most probable" states become infinitely more likely than "less probable" ones.

This mathematical limit maps directly to "ranked models" in logic. In these models, possible worlds are organized into a hierarchy based on their "normality."

A ranked model where states are organized into a hierarchy of normality separated by dashed lines.

As shown in the figure, states like $(P, Q)$ might occupy the most "normal" rank, while others are relegated to lower ranks. In Satoh's framework, the probability of a state in rank $i$ is proportional to $x^i$. As $x \to 0$, the higher-order terms vanish, ensuring that the reasoner always focuses on the most normal (highest-rank) worlds consistent with the evidence.

Key Results: The Equivalence Theorem

The paper’s primary achievement is Theorem 1, which proves that a reasoning system is "rational" if and only if it can be described by this probabilistic limit. This confirms that "lazy" logic is not merely a heuristic but a mathematically sound method for handling high-probability defaults.

Furthermore, Satoh applied this framework to Circumscription, a popular AI technique for minimizing "abnormality." His analysis (Theorem 3) revealed a surprising limitation: while minimizing one or two propositions in parallel remains "rational," minimizing three or more can lead to logical inconsistencies. This suggests that attempting to be too "optimal" across too many variables simultaneously breaks the "lazy" behavior required for rationality.

Conclusion and Future Directions

Satoh’s work provides a concrete formula for assigning probabilities to interpretations in a way that perfectly mimics rational nonmonotonic reasoning. While currently limited to finite propositional languages and "rational" systems, it lays the groundwork for extending probabilistic semantics to more complex frameworks like Default Logic or first-order logic.

Summary updated

BibTeX
@inproceedings{satoh1990probabilistic,
  author = {Ken Satoh},
  title = {{A Probabilistic Interpretation for Lazy Nonmonotonic Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure