Abstract
In the early development of Knowledge Representation, inheritance hierarchies were a primary method for encoding common-sense knowledge. However, early systems relied on a "shortest-path" heuristic that frequently led to logical inconsistencies. This paper by David Touretzky (1984) identifies the fundamental flaws of path-based inheritance and introduces inferential distance, a topological ordering that ensures more specific information correctly overrides general defaults.
Introduction
Representing knowledge through hierarchies—such as "Birds fly" and "Ostriches are birds"—is intuitive but computationally challenging when exceptions are introduced. Early AI systems like NETL and FRL used the "shortest-path" algorithm: to determine if an entity possessed a property, the system traversed the graph to find the nearest ancestor defining that property. Touretzky demonstrates that this numerical approach is logically unsound, particularly when dealing with redundant information or multiple inheritance.
The Failure of Shortest-Path Heuristics
Touretzky identifies two primary failure modes in traditional inheritance systems: the redundancy problem and the ambiguity problem.
The Redundancy Problem
Redundancy occurs when a fact is explicitly stated that was already implied by the hierarchy. For example, if we know "Clyde is a Circus Elephant" and "Circus Elephants are Royal Elephants," we already know "Clyde is a Royal Elephant." If we then explicitly add the link "Clyde is an Elephant," we create a shortcut.
In a shortest-path system, this shortcut can be disastrous. If "Elephants are gray" but "Royal Elephants are not gray," the system might follow the shorter path from Clyde to Elephant and conclude he is gray, ignoring the more specific (and correct) information that he is a Royal Elephant.
Ambiguity and Multiple Inheritance
Multiple inheritance allows an entity to belong to multiple classes, which may have conflicting defaults. The classic example is the "Nixon Diamond."
In this scenario, Richard Nixon is both a Quaker and a Republican. Quakers are typically pacifists, while Republicans are typically pro-defense (not pacifists). A shortest-path reasoner might arbitrarily choose one conclusion based on the number of links, failing to recognize that the situation is inherently ambiguous.
Proposed Solution: Inferential Distance
To resolve these issues, Touretzky proposes Inferential Distance Ordering. The core principle is that specificity should be determined by the topology of the graph rather than the number of links.
The Topological Rule
Class $A$ is considered "nearer" to an object than class $B$ if there exists an inheritance path from $A$ to $B$. This relationship establishes $A$ as a subclass of $B$. By using this partial ordering, the system ensures that information from a subclass always overrides information from a superclass, regardless of how many "shortcuts" exist in the graph.
Integration with Default Logic
The paper bridges the gap between semantic networks and formal logic by mapping inheritance networks onto Raymond Reiter’s Default Logic. Touretzky shows that inferential distance acts as a filter for proof sequences. This allows developers to use "normal" defaults (e.g., "Birds fly") without needing to explicitly list every exception (e.g., "Birds fly unless they are ostriches or penguins"), as the hierarchy handles exceptions implicitly.
Key Results and Implications
Touretzky’s formalization of inheritance networks led to several significant conclusions:
- Constructible Extensions: He proved that every acyclic inheritance network has at least one consistent set of beliefs, known as a constructible extension.
- Stability and Ambiguity: The paper identifies specific subgraph structures that lead to instability or ambiguity, allowing for better network design.
- Conditioning: Touretzky demonstrated that any complex network can be "conditioned"—its topology adjusted—so that even a simple, fast shortest-path reasoner can produce correct results.
Conclusion
"Implicit Ordering of Defaults in Inheritance Systems" shifted the focus of Knowledge Representation from numerical heuristics to topological analysis. By introducing inferential distance, Touretzky provided a robust framework for handling exceptions and ambiguity, ensuring that AI systems could reason more accurately about complex, real-world taxonomies. While modern systems have evolved, the principle that specificity is topological remains a cornerstone of logical reasoning in AI.
Summary updated