Semantically Sound Inheritance for a Formally Defined Frame Language with Defaults

Robert Nado, Richard FikesAAAI 1987

Abstract

In the mid-1980s, frame-based representation systems were a cornerstone of artificial intelligence, yet they lacked a rigorous logical foundation for handling defaults and exceptions. This paper, presented at AAAI-87, introduces the OPUS system, which replaces ad-hoc "shortest path" heuristics with a formally defined inheritance algorithm. By distinguishing between local and resultant properties and utilizing Truth Maintenance Systems, authors Robert Nado and Richard Fikes provide a semantically sound method for managing complex knowledge hierarchies.

The Problem: Brittle Heuristics in Knowledge Hierarchies

During the 1980s, "frames" were widely used to organize knowledge into hierarchies of classes and members. A significant challenge in these systems was the handling of defaults—properties that are "usually" true but may have exceptions. For example, one might state that "Elephants are typically grey," while "Royal Elephants are typically white."

The industry standard at the time relied on the "shortest path" heuristic, where an object inherited properties from its nearest ancestor in the graph. However, this approach was prone to failure in the presence of redundant links.

The "Clyde" problem: Redundant links in a hierarchy can lead shortest-path heuristics to incorrect conclusions about default properties.

As illustrated in the "Clyde the Elephant" thought experiment (Figure 1), if "Clyde" is a Royal Elephant but also possesses a direct, redundant link to the general "Elephant" class, a shortest-path algorithm might see two paths of equal length. Consequently, it could fail to prioritize the more specific "white" default over the general "grey" one, leading to logical inconsistency.

Methodology: The OPUS Framework

Nado and Fikes sought to replace these heuristics with a formal system that remains consistent even in the face of complex, overlapping inheritance links. Their system, OPUS, extended the formalisms of David Etherington through several key methodological contributions:

  • Formal Distinction of Slots: The system distinguishes between "Own Slots" (properties specific to an entity) and "Prototype Slots" (properties intended for inheritance by class members).
  • Quantified Exceptions: Rather than simply blocking a value, OPUS allows for second-order-like statements. A class can explicitly state that any default value for a specific slot originating from any superclass should be blocked.
  • The "Push" Inheritance Algorithm: Moving away from "pulling" information during queries, the OPUS algorithm "pushes" values down the hierarchy whenever the knowledge base is modified.

Implementation Paths

The authors proposed two distinct ways to implement this logic:

  1. TMS-Based: This version utilizes a Truth Maintenance System (TMS) to manage nonmonotonic justifications. It maintains the belief that "Clyde is white" unless contradictory evidence is introduced, automatically retracting inherited values if the hierarchy changes.
  2. Standalone: For environments without a general TMS, a standalone version manages "local" versus "resultant" sets of values to manually track inheritance.

Key Results and Semantic Soundness

The primary achievement of the OPUS system was the resolution of multiple inheritance conflicts that plagued earlier systems like FRL or NETL. By treating inheritance as a logical inference problem rather than a graph-traversal problem, the authors achieved "semantic soundness."

The OPUS resolution: By tracking local and resultant defaults and exceptions, the system correctly identifies Clyde as white.

As shown in Figure 2, the algorithm tracks "Local Defaults" and "Local Exceptions" at each node to calculate "Resultant" values. In the Clyde example, the exception at the Royal Elephant level correctly blocks the "Grey" default from the Elephant class, ensuring that Clyde's resultant color is "White," regardless of redundant links.

Conclusion and Future Work

The OPUS system was successfully integrated into the Knowledge Engineering Environment (KEE) at IntelliCorp. While the authors acknowledged the computational complexity of managing a full TMS, they demonstrated that a serial algorithm could be efficient enough for practical use.

Future work suggested hybrid approaches: using the faster standalone method for stable, upper regions of a taxonomy and the flexible TMS-based method for more volatile, problem-dependent lower regions. This research remains a foundational step in bridging high-level logical theory with practical software engineering in AI.

Summary updated

BibTeX
@inproceedings{nado1987semantically,
  author = {Robert Nado and Richard Fikes},
  title = {{Semantically Sound Inheritance for a Formally Defined Frame Language with Defaults}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure