The Costs of Inheritance in Semantic Networks

Rob’t F. SimmonsCOLING 1984

TL;DR

This paper explores the computational cost of using inheritance in semantic networks for question answering. The authors propose a "relaxed unification" approach that efficiently matches question terms with knowledge base entries by leveraging taxonomic and partitive relationships, significantly reducing processing time.

What Problem Does This Paper Address?

Answering natural language questions often requires understanding relationships between concepts, such as synonyms, instances, and hyponyms. Semantic networks are a common way to represent this knowledge, with inheritance (specifically, taxonomic and partitive relations) being a crucial mechanism for inferring new information. However, the authors observed that directly applying inheritance logic in a naive way led to prohibitively high computational costs, making real-time question answering impractical. They aimed to find a way to effectively use inheritance for question answering without incurring excessive computational expense.

Methods

The core of the paper introduces a "relaxed unification" algorithm for matching question triples (SRq) with candidate answer triples (SRc) from a knowledge base. Unlike standard unification, which requires exact matches, relaxed unification allows for matches based on taxonomic and partitive relationships. This is achieved by introducing "abstractive closure" (using SUP and INST arcs) and "complex product closure" (using arcs like OF, HAS, LOC, AND, OR) to find related concepts. The authors also define CLOSAB (Abstractive Closure) and CLOSCP* (Complex Product Closure) procedures to handle these relationships. The process involves first attempting direct matches, then using abstractive closure, and finally complex product closure if direct matches fail.

Datasets

The primary "dataset" used in this study is a portion of the AI Handbook, specifically 170 semantic relations (SRs) represented by 733 binary relations. This text was manually organized into a knowledge base with taxonomic and partitive relations. The authors also mention studies on a story about a rocket's flight and a general English dictionary as contexts for their work.

Key Insights and Ideas

  • Inheritance is powerful but costly: While inheritance in semantic networks is essential for rich understanding, a direct, unoptimized implementation can be computationally prohibitive for real-time applications.
  • Relaxed unification is key: By allowing matches based on related concepts (synonyms, instances, hyponyms) rather than exact matches, the system can find answers more efficiently.
  • Closure operations are the engine: Abstractive and complex product closures provide the mechanisms to explore these related concepts, effectively expanding the search space without brute-force enumeration.
  • Short inference paths are dominant: Empirically, most answers are found through short inference paths, suggesting that limiting the depth of these closures is a practical optimization.
  • Semantic relations as inference rules: The paper suggests that semantic relations can be viewed as inference rules, enabling the system to act as a theorem prover for loosely ordered logic.

Key Results

The initial experiments with a naive inheritance approach were very slow, with some questions taking up to a minute of CPU time. By implementing the relaxed unification procedure and optimizing the process, the authors reduced the computation time to the range of 1/2 to 15 seconds per question on a DEC 2060 in uncompiled ELISP. They estimate that even with a complex question composed of multiple subquestions, a complete search might involve examining around a thousand candidates, which is still accomplished within a few seconds.

Limitations and Future Work

The authors acknowledge that the experiment was primarily concerned with the simple levels of inference involved in taxonomic structures. They note that the complex product closure arcs often lead to probable inferences rather than certain ones, and the probability of finding an answer decreases rapidly with longer inference paths. Future work could explore the cost-effectiveness of using more complex inference rules with relaxed unification and investigate theoretically less appealing compilation methods. The paper also suggests that this approach is applicable to any use of an English dictionary encoded in semantic networks.

Summary updated

BibTeX
@inproceedings{simmons1984costs,
  author = {Rob’t F. Simmons},
  title = {{The Costs of Inheritance in Semantic Networks}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}

Loading related content...

Figure