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:
- Rigidity: Systems could not easily handle exceptions to class membership (e.g., representing that a robotic penguin isn't a biological bird).
- Unintended Models: Logics would often "hallucinate" gratuitous links between objects to mathematically minimize abnormalities.
- Excessive Closed-World Assumptions: The assumption that unknown abnormalities do not exist was often too strong for real-world applications.
- The Nixon Diamond: Conflicting defaults led to counter-intuitive results in complex, multi-link versions of these conflicts.
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.
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