The Use of a Semantic Network in a Deductive Question-Answering System

James R. McSkimin, Jack Minker

Abstract

This paper presents a methodology for enhancing deductive question-answering (QA) systems by integrating a semantic network into the logical search process. By utilizing set-theoretic constraints and cardinality restrictions, the proposed system prunes search spaces and rejects semantically invalid queries early, addressing the computational explosion common in purely syntactic automated reasoning.

Introduction

In the 1970s, automated reasoning systems primarily relied on the syntactic manipulation of predicate calculus. While logically sound, these systems often lacked real-world context, leading to "blind" searches that explored physically impossible or redundant paths—such as searching for a third senator from a state or attempting to prove a person is their own mother. This paper addresses the search space explosion problem by introducing a semantic layer that understands category relationships and finite domain constraints.

Methods

The system architecture centers on a Semantic Network comprising four components: a Semantic Graph ($G_s$), a Dictionary, a Semantic Form Space, and a specialized Data Base using n-σ notation.

A hierarchical Semantic Graph ($G_s$) defining set-theoretic relationships between categories.

The Semantic Graph (Figure 1) defines relationships such as superset ($⊇$), disjoint ($ϕ$), and overlap ($θ$). The core technical innovation is Semantic Unification. Unlike standard unification, which only checks if symbols match, this algorithm verifies if the categories of variables are compatible based on the Semantic Graph. If a variable substitution violates these constraints—for instance, attempting to unify a 'robot' with a 'human' category—the branch is immediately terminated.

Key Efficiency Mechanisms

  • Hierarchy-Based Inference: Set-membership is handled via the dictionary and graph rather than logical deduction, allowing for "trivial" inferences without expensive resolution steps.
  • Semantic Set Count (SSC): By knowing the exact number of entities in a set (e.g., two senators per state), the system can mark subproblems as "fully solved" and prune remaining search branches once that count is reached.

Results and Evaluation

The approach was evaluated using a hand-crafted political domain dataset involving U.S. Congress members, residency rules, and interest group ratings (e.g., COPE, NSC).

A trace of a proof using semantic unification to prune the search space.

Figure 2 illustrates a typical proof where semantic constraints are applied to a complex query regarding senators from specific states supporting defense interests. The system uses "well-formedness" tests to ensure only valid entities (e.g., congressperson for a REPRESENT predicate) are considered. The "counting restriction" allows the system to stop searching once the known number of senators for Maryland or New York is reached, significantly reducing the Total Search Count (TSC).

Conclusion

By infusing logic with meaning, the authors demonstrate that semantic constraints can drastically optimize deductive search. While the semantic checks introduce some computational overhead, the reduction in the search space for complex queries is substantial. Future work involves scaling these techniques to larger, more diverse databases and refining the conflict detection algorithms to minimize overhead in the MRPPS 3.0 system.

Summary updated

BibTeX
@inproceedings{mcskimin1977use,
  author = {James R. McSkimin and Jack Minker},
  title = {{The Use of a Semantic Network in a Deductive Question-Answering System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure