A Skeptic's Menagerie: Conflictors, Preemptors, Reinstaters, and Zombies in Nonrnonotonic Inheritance

TL;DR

This paper delves into the nuances of nonmonotonic inheritance reasoning, specifically focusing on how different systems handle "defeaters" – arguments that challenge other arguments. The authors introduce a taxonomy of these interactions, highlighting how subtle definitional differences can lead to vastly different conclusions and computational behaviors, particularly in skeptical reasoning systems.

What Problem Does This Paper Address?

Inheritance systems, which model how properties are passed down through hierarchies (e.g., "birds fly," "penguins are birds," therefore "penguins fly"), often need to handle exceptions. Nonmonotonic inheritance allows for these exceptions, meaning a general rule can be overridden by a more specific one. The challenge arises when multiple, conflicting exceptions or rules exist, leading to situations where an argument might be "defeated" – its conclusion is challenged. This paper tackles the complex problem of how different nonmonotonic inheritance reasoners, particularly "skeptical" ones (which only accept conclusions that are undeniably true), deal with these defeats. They explore various types of "defeat" and "defeater-defeats," aiming to clarify the subtle distinctions between different reasoning systems and their computational implications.

Methods

The paper introduces a formal framework for analyzing nonmonotonic inheritance. Key methods include:

  • Defining types of defeat: The authors formally define "preemptors" (arguments that override others due to specificity) and "conflictors" (arguments that directly contradict each other without a clear specificity relation).
  • Introducing "situators": These are paths within the network that establish the "betweenness" required for preemption to hold.
  • Classifying "defeater-defeaters": This is a crucial contribution. They categorize how defeated arguments can themselves be "undefeated" or how defeats can be overcome. This includes concepts like "reinstatement" (where a defeated argument is brought back) and "zombies" (conflicted paths that can still defeat other paths).
  • Analyzing skeptical vs. credulous reasoning: The paper contrasts "skeptical" reasoners (which aim for a single, certain conclusion) with "credulous" reasoners (which may produce multiple possible conclusions).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses illustrative examples (like the Nixon diamond and animal hierarchies) rather than empirical evaluation on datasets.

Key Insights and Ideas

  • The "Skeptic's Menagerie": The paper argues that subtle differences in defining defeat mechanisms (preemption, conflict, situators) create a rich "menagerie" of reasoning behaviors. Even within skeptical systems, these differences matter significantly.
  • The Problem of Reinstatement: The authors strongly argue against "reinstatement," where a defeated argument is brought back. They contend that this can lead to semantically undesirable conclusions, allowing arguments to go through even when their underlying reasons are undercut by more specific information.
  • Defeater-Defeaters Matter: The interaction between defeaters is critical. The paper identifies five types of "defeater-defeaters" (e.g., preemptor-preemptor, conflictor-conflictor) and discusses their impact on conclusions.
  • "Zombies" and Ideal Skepticism: The concept of "zombies" (conflicted paths that can still defeat others) is introduced as a way to handle certain skeptical reasoning scenarios, particularly when dealing with the intersection of all possible credulous extensions. However, they note that purely path-based formalisms struggle to capture this "ideal" skepticism.
  • Trade-offs in Algorithm Design: There's a fundamental trade-off between the "correctness" (semantic desirability) of inheritance definitions and the efficiency of algorithms that implement them. Marker propagation algorithms, for instance, often implicitly rely on reinstatement for efficiency, which the authors deem problematic.

Key Results

  • Formal Definitions: The paper provides precise definitions for concepts like situators, preemptors, conflictors, and defeaters, offering a common language for discussing these issues.
  • Classification of Defeats: A taxonomy of defeat interactions is presented, clarifying how different systems might handle complex scenarios.
  • Argument Against Reinstatement: The authors provide strong arguments for why reinstatement is semantically undesirable in inheritance reasoning.
  • Implications for Algorithms: The work highlights limitations of simple marker propagation algorithms in achieving robust skeptical reasoning without reinstatement.

Limitations and Future Work

  • Computational Efficiency of Non-Reinstating Skepticism: A key open question is whether preemption without reinstatement can be computed efficiently without enumerating all possible situator paths. The authors suggest that simple marker propagation might not be sufficient.
  • Mixed Nets: While the paper touches on mixed nets (combining strict and defeasible links), further exploration of their implications, particularly regarding situators being strict paths, is suggested.
  • "Ideal" Skepticism: Capturing the intersection of all credulous extensions (ideal skepticism) is noted as a challenge for purely path-based formalisms, hinting at the need for alternative approaches.
  • Empirical Evaluation: The paper is primarily theoretical. Future work could involve empirical evaluations of different reasoning systems on real-world or benchmark inheritance networks.

Summary updated

BibTeX
@inproceedings{1991skeptic,
  title = {{A Skeptic's Menagerie: Conflictors, Preemptors, Reinstaters, and Zombies in Nonrnonotonic Inheritance}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure