A Model and Representation for Type Information and Its Use in Reasoning with Defaults

Lin PadghamAAAI 1988

Abstract

This paper introduces a novel knowledge representation model that partitions "types" into a Type Core (mandatory traits) and a Type Default (typical traits). By mapping these onto a mathematical lattice of feature descriptors, the author provides a consistent method for resolving classic paradoxes in multiple inheritance and default reasoning, moving beyond the limitations of traditional graph-based systems.

Introduction

In the late 1980s, AI researchers faced significant challenges with "inheritance hierarchies"—systems where a sub-type (e.g., "Royal Elephant") inherits properties from a super-type (e.g., "Elephant"). The primary difficulties arose from multiple inheritance and exceptions. For instance, if "Elephants are typically grey" but "Royal Elephants are never grey," and "Clyde is a Royal Elephant," traditional systems often reached contradictory conclusions. These "tangled hierarchies" frequently led to ambiguous situations where AI could not decide on a property, even when the answer was intuitively obvious. Existing systems like NETL or FRL relied on complex path-counting or "shortest-path" heuristics that often failed in edge cases.

The Lattice-Based Model

Lin Padgham proposes moving away from simple directed graphs toward a lattice-based model of feature descriptors. The key innovation is the Core/Default Split:

  • Type Core ($Cr$): Characteristics that are always present (monotonic). If $A$ is a subtype of $B$, $A$'s core must contain all information in $B$'s core.
  • Type Default ($Df$): Characteristics that are typically present (non-monotonic).

In this lattice formalism, higher points represent more information or specialization. The system utilizes an Extension Operation ($\\mathcal{E}$), a "non-monotonic jump" from a type's core to its default, allowed only if the default information does not conflict with existing knowledge. Incompatibility is explicitly modeled as a "join" of two points resulting in an inconsistent state ($K$).

Comparison of traditional inheritance graphs with the proposed lattice-based representation for the Clyde elephant example.

Case Studies and Results

The model was evaluated against canonical problematic networks of the era:

  • The Clyde Example: A redundant inheritance link involving Royal Elephants and African Elephants. The system correctly concludes Clyde is not grey, even with redundant links that confuse "shortest path" algorithms.
  • The Nixon Diamond: A classic conflict where a Quaker (typically a pacifist) is also a Republican (typically not a pacifist).
  • The Nautilus/Cephalopod Problem: A complex hierarchy involving shell-bearing animals.
The Nixon Diamond paradox represented in the lattice model, showing different possible extensions.

The paper demonstrates that the lattice model successfully resolves these dilemmas. By distinguishing between "always" and "usually," the system handles exceptions gracefully. Furthermore, the model naturally implements a Specificity Preference: when faced with conflicting defaults, it prefers the extension from the "most specific" core. This replicates the "inferential distance" heuristic through the inherent structure of the lattice rather than ad-hoc rules.

Discussion and Future Work

The author shows that the lattice model achieves results similar to more complex systems, such as Etherington’s link types, but with a more unified and intuitive representation. However, limitations remain. For instance, individuals can sometimes fall "below the core" (e.g., a three-legged dog). Future work aims to describe reasoning about such "broken" individuals. Additionally, the computational complexity of building and searching a lattice of all possible feature combinations for very large knowledge bases remains a consideration for practical implementation.

Summary updated

BibTeX
@inproceedings{padgham1988model,
  author = {Lin Padgham},
  title = {{A Model and Representation for Type Information and Its Use in Reasoning with Defaults}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure