Negative Reasoning Using Inheritance

Lin PadghamIJCAI 1989

TL;DR

While most AI inheritance systems focus on what an object is, Lin Padgham’s 1989 paper introduces a formal framework for deducing what an object is not. By using a lattice-based model that distinguishes between "core" and "default" characteristics, the paper provides a way to draw both strict and default negative conclusions—a critical capability for high-stakes domains like medical diagnosis.

What Problem Does This Paper Address?

Inheritance reasoning is a classic AI problem: if we know a "Bird" typically "Flies," and "Tweety" is a "Bird," we infer Tweety flies. However, most research in the 80s (Etherington, Touretzky, etc.) focused almost exclusively on collecting positive information.

The gap Padgham identifies is that in many real-world scenarios, negative information is just as vital. In medicine, ruling out a disease is as important as confirming one. In pharmacology, knowing that a drug is incompatible with a patient's condition is a life-or-death requirement. Standard models struggled to deduce these "not-a" relationships unless they were explicitly stated. Padgham seeks to move beyond explicit "not" links to a system where negative conclusions can be logically deduced or assumed by default.

Methods

The paper builds on a lattice-based model of descriptors. Instead of simple nodes in a graph, types are defined by sets of characteristics.

  1. Core vs. Default ($X_c$ vs. $X_d$): Every type has a "core" (characteristics strictly necessary to be that type) and a "default" (characteristics a typical member has). For example, a "Dog" core might include "canine DNA," while the default includes "four legs." This allows the system to recognize a three-legged dog as still being a dog.
  2. The Lattice Structure: Types are ordered by "more information" ($\sqsupseteq$). If $A \sqsupseteq B$, then $A$ is a subtype of $B$.
  3. Incompatibility ($\mathcal{I}$): A formal relation defining when two characteristics cannot coexist (e.g., "weight 5kg" and "weight 10kg").
  4. The $N$ Operator (Negative Default Assumption): This is the paper's primary innovation. Just as we have a positive default (if it's an $A$, assume it's a typical $A$), the $N$ operator allows for a negative default: if an object doesn't fit the description of a typical $X$, we can assume it is not an $X$.
  5. Strict vs. Default Negative Reasoning:
    • Strict: If $X$ is incompatible with $Y$, and $Z$ is a subtype of $Y$, then $X$ is strictly not a $Z$.
  6. Default: Using the $N$ operator to jump to negative conclusions when information is missing but suggestive.

Datasets

As a theoretical paper in knowledge representation, it does not use large-scale empirical datasets. Instead, it validates the logic using:

  • The Medical Drug Example: A knowledge base of drugs (diuretics, beta-blockers, etc.) and their effects on blood glucose.
  • The "Royal Elephant" Problem: A classic "toy problem" in inheritance literature used to demonstrate how the model handles specific exceptions (e.g., elephants are usually grey, but Royal Elephants are not).

Key Insights and Ideas

  • Symmetry of Reasoning: The author argues that negative default reasoning is the exact functional mirror of positive default reasoning. If we are comfortable assuming "birds fly" by default, we should be equally comfortable assuming "this non-flying thing is not a typical bird."
  • The Power of Contraposition: By using a lattice of characteristics, the system can "reason backwards" along inheritance links. If a drug must be a "blood glucose lowerer" and we know our patient cannot have their glucose lowered, we can strictly deduce that the patient cannot take that drug.
  • Handling Exceptions Gracefully: The core/default split solves the "three-legged dog" problem. It allows individuals to be members of a class even if they deviate from the default, without breaking the inheritance logic for the rest of the class.

Key Results

  • Formalization of $NOT(A)$: The paper provides a mathematical definition for the "complement" of a type based on the union of all types incompatible with it.
  • Proof of Correctness: Padgham provides proofs showing that strict negative reasoning is logically required if one accepts the basic tenets of the lattice model.
  • Conflict Resolution: The paper suggests a "Preference for Specificity." When positive and negative conclusions conflict, the system should prefer the one derived from the most specific information. However, the author notes an intuition that positive defaults should generally override negative defaults unless the negative information is more specific.

Limitations and Future Work

  • Complexity of Interactions: The model assumes that incompatibility is a simple relationship between two characteristics. It does not yet handle "complex interactions" where three or more items together create an incompatibility that none do individually.
  • Priority of Defaults: The author admits that more work is needed to determine exactly how to prioritize negative default conclusions against positive ones in complex, messy graphs.
  • Implementation Scale: While the logic is sound for the provided examples, the paper does not explore the computational complexity of maintaining these lattices in massive, real-time databases.

Reference: Padgham, L. (1989). Negative Reasoning Using Inheritance. Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89).

Summary updated

BibTeX
@inproceedings{padgham1989negative,
  author = {Lin Padgham},
  title = {{Negative Reasoning Using Inheritance}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure