A Skeptical Theory of Inheritance in Nonmonotonic Semantic Networks

John F. Horty, Richmond H. Thomason, David S. TouretzkyAAAI 1987

Introduction

In the late 1980s, AI research faced a significant hurdle in knowledge representation: how should machines inherit properties in complex taxonomies with exceptions? For instance, if "Birds fly" but "Penguins are birds that don't fly," how does a system conclude whether a specific penguin flies? This seminal 1987 paper by Horty, Thomason, and Touretzky introduced a "skeptical" approach to resolve such ambiguities in acyclic semantic networks.

The Problem: Multiple Inheritance and Ambiguity

The core challenge lies in multiple inheritance, famously exemplified by the "Nixon Diamond." In this scenario, an individual belongs to two categories with conflicting properties.

The Nixon Diamond (Γ₃), illustrating conflicting inheritance paths where a skeptical reasoner would remain undecided.

Previous "credulous" models would generate multiple "extensions"—competing sets of conclusions. In the Nixon Diamond, one extension would conclude Nixon is a pacifist, while another would conclude he is not. This leads to an exponential explosion of possibilities in large networks and forces the system to make arbitrary choices. The authors proposed a skeptical alternative: when faced with unresolvable, conflicting arguments of equal strength, the reasoner refuses to draw a conclusion, ensuring a unique and stable set of inferences.

Methodology: Argument Construction

The authors shifted from a traditional top-down "property flow" metaphor to a bottom-up "argument construction" approach. This allows the system to evaluate the strength of competing paths based on their structure.

Key Technical Components

  • Forward Chaining: Reasoning paths are built from the individual upward (e.g., Tweety → Canary → Bird → Flying Thing).
  • Preemption: This formalizes the intuition that specific information should override general information. If a path through a specific category (e.g., Penguin) conflicts with a path through a general category (e.g., Bird), the specific path "preempts" the general one.
  • Skeptical Neutralization: If two compound arguments conflict and neither is more specific (preempted), the skeptical reasoner "neutralizes" both, refusing to support either conclusion.
Examples of direct conflict (left) and preemption (right) in inheritance networks.

Key Insights and Results

The skeptical approach offers several advantages over its credulous predecessors:

  • Unambiguous Inference: The paper provides a formal definition that yields exactly one set of supported assertions for any acyclic semantic net, avoiding the instability of multiple extensions.
  • Computational Efficiency: By using a topological sort to order path processing, the authors developed an algorithm that avoids the exponential complexity often associated with nonmonotonic reasoning.
  • Inconsistency Tolerance: Explicit contradictions in a database are reported but do not "poison" the rest of the network, maintaining local logical integrity.

Limitations and Future Work

The theory is strictly limited to acyclic networks. In networks with cycles (e.g., A is a B, B is a C, C is an A), the inductive definition of "path degree" breaks down. Furthermore, the logic is restricted to simple positive and negative links, lacking the expressiveness of full first-order logic. The authors suggest that while skepticism is a stable design choice, future work should bridge the gap between skeptical and credulous reasoning styles.

Summary updated

BibTeX
@inproceedings{horty1987skeptical,
  author = {John F. Horty and Richmond H. Thomason and David S. Touretzky},
  title = {{A Skeptical Theory of Inheritance in Nonmonotonic Semantic Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure