Tractable Theories of Multiple Defeasible Inheritance in Ordinary Nonmonotonic Logics

Brian A. HaughAAAI 1988

Introduction

In the field of artificial intelligence, the 1980s were marked by a concerted effort to formalize "common sense" reasoning. A central challenge was nonmonotonic reasoning—the ability of a system to revise its conclusions in the light of new, potentially conflicting information. Brian A. Haugh’s 1988 paper, presented at AAAI, addresses critical shortcomings in earlier formalizations of inheritance hierarchies with exceptions, specifically those proposed by John McCarthy. By distinguishing between explicit knowledge and derived conclusions, Haugh developed a family of logical theories that are both more intuitive and computationally tractable.

The Problem: Flaws in Early Formalizations

John McCarthy’s early attempts to use circumscription for handling defeasible rules—rules that can be overridden—suffered from several technical "bugs." Haugh identifies four primary issues:

  1. Rigidity: Systems could not easily handle exceptions to class membership (e.g., representing that a robotic penguin isn't a biological bird).
  2. Unintended Models: Logics would often "hallucinate" gratuitous links between objects to mathematically minimize abnormalities.
  3. Excessive Closed-World Assumptions: The assumption that unknown abnormalities do not exist was often too strong for real-world applications.
  4. The Nixon Diamond: Conflicting defaults led to counter-intuitive results in complex, multi-link versions of these conflicts.
The classic Nixon Diamond illustrates a conflict of properties where an individual (Nixon) belongs to two classes (Quaker and Republican) with opposing default traits (Pacifist vs. Non-Pacifist).

Methodology and Innovations

Haugh’s approach introduces several key innovations to resolve these issues. He distinguishes between isa-x (explicit network links provided as input) and isa (derived relations concluded by the system). Instead of minimizing the total number of "abnormal" objects, Haugh proposes minimizing the explicit links required to explain the network. This prevents the system from inventing "gratuitous" connections to satisfy logical constraints.

Furthermore, the paper axiomatizes four specific types of abnormalities:

  • Direct Abnormalities: Where a direct link (e.g., Penguin -> Not-Fly) overrides a longer path (e.g., Penguin -> Bird -> Fly).
  • Inherited Abnormalities: Exceptions that propagate down the hierarchy.
  • Conflicting Paths: Scenarios like the Nixon Diamond where multiple paths lead to contradictory conclusions.

To address the "Closed-World" problem, Haugh suggests using "starred" predicates for proven truths and "unstarred" predicates for general possibilities, allowing for an "Open-World" interpretation where the system can remain agnostic when information is insufficient.

The Penguin/Bird/Flyer hierarchy is a standard benchmark for defeasible inheritance, demonstrating how specific class knowledge (Penguin) overrides general defaults (Bird).

Evaluation and Results

The theory was evaluated against standard logical benchmarks, including the classic Nixon Diamond, extended multi-link diamonds, and simple class cancellation hierarchies. Haugh’s formulation proved superior in handling "Extended Nixon Diamonds," correctly identifying that only the final links in conflicting paths should be treated as suspect, thereby preserving intermediate conclusions.

The paper also formalizes two levels of "skeptical" reasoning: ambiguity-blocking, which halts inference at the point of conflict, and ambiguity-propagating, which treats the result as uncertain and allows that uncertainty to flow further up the hierarchy.

Conclusion

Haugh’s work represents a significant advancement in making nonmonotonic reasoning computationally feasible. By avoiding unnecessary abnormalities and focusing on the minimization of explicit knowledge, these theories can be efficiently implemented using Truth Maintenance Systems (TMS). While future work remains in areas like auto-epistemic logic and more robust ambiguity propagation, this paper provides a solid foundation for tractable, common-sense AI.

Summary updated

BibTeX
@inproceedings{haugh1988tractable,
  author = {Brian A. Haugh},
  title = {{Tractable Theories of Multiple Defeasible Inheritance in Ordinary Nonmonotonic Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure