Referential Determinism and Computational Efficiency: Posting Constraints from Deep Structure

Gavan Duffy, John C. MalleryAAAI 1984

Introduction

In the mid-1980s, the field of computational linguistics saw a shift away from "deep structures"—the underlying grammatical representations of sentences—in favor of surface-level analysis. However, in their 1984 AAAI paper, Duffy and Mallery argue that this trend overlooks a critical factor: computational efficiency. They propose that deep structure is not merely a linguistic abstraction but a necessary mechanism for resolving references deterministically, thereby avoiding the costly backtracking that plagues many natural language processing (NLP) systems.

The Challenge of Reference Resolution

The core task of an NLP system is to map linguistic tokens (such as "the police" or "it") to specific entities within an internal model of the world, typically represented as a semantic network. This process, known as reference resolution, is inherently difficult due to the variability of natural language.

Surface-interpretive approaches, which analyze only the final form of a sentence, struggle with syntactic variations. For instance, "The police wanted Elmer" and "Elmer was wanted by the police" convey the same meaning but have different surface structures. Without a canonical internal representation, an AI must account for these variations every time it accesses its memory. This often results in "non-determinism," where the system makes a tentative reference, encounters a contradiction later in the sentence, and must "backtrack" to re-evaluate. This process is computationally expensive and hinders real-time processing.

The Referential Determinism Hypothesis

To address these inefficiencies, Duffy and Mallery introduce the Referential Determinism Hypothesis. This principle suggests that syntactic analysis should be designed to maximize the certainty of the reference resolution process. By prioritizing analyses that lead to deterministic mapping, the system can avoid the trial-and-error approach of traditional parsers.

The authors implement this via a framework consisting of the Relatus parser and the Gnoscere knowledge base. The system operates through a method called Constraint Posting. Rather than committing to a specific reference immediately, the system "posts" a set of requirements (constraints) as it processes the sentence. It adopts a "wait and see" strategy, gathering enough information to ensure a certain match before finalizing the reference.

Methodology: Two-Phase Recursive Mapping

The transition from raw text to a semantic network occurs in two distinct phases:

  1. Syntax to Constraints: The Relatus parser traverses a deep-structure parse tree to generate a "constraint tree." This step standardizes grammatical relationships, ensuring that different syntactic forms of the same idea result in the same set of constraints.
  2. Constraints to Semantic Network: The system then traverses the constraint tree to locate existing objects in the Gnoscere knowledge base that satisfy all requirements. If no such object exists, a new one is created.

This process relies on canonicalization. By converting sentences into a standardized "deep" form, the system ensures that the internal representation remains consistent regardless of whether the input was in the active or passive voice.

Insights on Efficiency and Parsimony

A common critique of Transformational Grammar (the foundation of deep structure) is that it is too complex for efficient AI. Duffy and Mallery refute this, arguing that deep structure acts as a "cache" for positional and relational information. By "unpacking" the sentence structure once into a canonical form, the system avoids having to re-process syntactic variety during subsequent reasoning or inference tasks.

Furthermore, the authors distinguish between immediate reference (mapping tokens to known entities) and deliberative reference (handling complex ambiguities or contradictions). They argue that immediate reference must be deterministic to provide a stable foundation for the more complex, deliberative reasoning tasks that follow.

Conclusion

The approach demonstrated by Duffy and Mallery shows that "immediate reference" can be handled without false starts or the need to retract premature references. By using deep structure to post constraints, the system guarantees that the semantic network remains syntactically canonical, making future operations—such as learning or logical inference—significantly faster.

While the paper focuses primarily on internal, immediate reference and acknowledges the limitations regarding "external" world mapping and the complexity of deliberative reference, it provides a robust argument for the computational utility of deep linguistic structures. The success of the method ultimately depends on the accuracy of the parser, but it offers a clear path toward more tractable and efficient AI systems.

Summary updated

BibTeX
@inproceedings{duffy1984referential,
  author = {Gavan Duffy and John C. Mallery},
  title = {{Referential Determinism and Computational Efficiency: Posting Constraints from Deep Structure}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure