Principle-Based Interpretation of Natural Language Quantifiers

Samuel S. EpsteinAAAI 1988

Author: Samuel S. Epstein (1988)

Abstract

This paper presents QSB (Quantifier Scopes and Bindings), a computational system designed to resolve quantifier scope ambiguities and pronoun references using Government-Binding (GB) theory. While GB theory was historically viewed as computationally prohibitive due to the combinatorial explosion of potential Logical Forms (LFs), this work demonstrates that by treating linguistic principles as efficient filters and employing specific optimization strategies—such as quasi-partitioning and minimal construction—complex natural language structures can be interpreted with high efficiency. The system achieves several orders of magnitude in speedup, proving that elegant linguistic principles can be implemented in practical natural language processing systems.

Introduction

In natural language, quantifiers such as "every," "some," and "many" present a significant challenge for computational understanding. Their meaning often depends on their "scope" relative to other quantifiers and the pronouns that refer back to them. For example, in the sentence, "Every professor expects several students to read many books," the interpretation changes depending on how the quantifiers are nested.

When pronouns are introduced—particularly in complex cases like "donkey sentences" (e.g., "Every man that owns a donkey beats it")—the number of possible interpretations grows exponentially. While Government-Binding (GB) theory provides a sophisticated framework for explaining these phenomena, it was long considered "hopeless" for computational implementation. A naive "generate-and-test" model would need to evaluate tens of thousands of potential LFs for a single sentence. Epstein’s QSB system challenges this assumption by providing a principled, high-performance implementation.

The QSB System Architecture

The QSB system is structured into three primary modules: a Parser, a Scope Module, and a Binding Module. The core innovation lies in the latter two, which implement GB theory without falling into combinatorial traps.

Linguistic Principles as Constraints

The system utilizes Quantifier Raising (QR) to derive Logical Forms from surface structures. This process is governed by four key principles that restrict where a quantifier can "land" in the structure:

  1. Phrasal-node-adjunction: Restricts determiners to moving only to specific phrasal nodes.
  2. Non-theta-adjunction: Prevents determiners from moving into "argument" positions, such as direct objects.
  3. Opacity: Ensures determiners remain within their local clauses (opaque domains).
  4. Minimal Binding Requirement (MBR): Imposes constraints on how landing sites can overlap or interleave.

Computational Optimization Strategies

To transform these theoretical principles into an efficient system, Epstein employs six specific programming strategies designed to prune the search space as early as possible:

  • Easier-Earlier & Maximal Filtering: By running the least computationally expensive and most restrictive filters first, the system discards invalid representations before they consume significant resources.
  • Wholesale Filtering: Rather than checking individual representations, the system applies filters to entire classes of structures simultaneously.
  • Schematic Representation & Minimal Construction: The system uses abstract "shortcuts" to represent possibilities, avoiding the overhead of building full, complex data structures for every potential interpretation.
  • Quasi-partitioning: This is the system's most impactful optimization. It breaks long sentences into overlapping segments, allowing the system to solve smaller sub-problems. This prevents the $n!$ complexity inherent in large sentences by recognizing that quantifier scope relationships rarely cross certain structural boundaries, such as coordination.

Evaluation and Results

Because the paper predates modern benchmarks like GLUE, the system was evaluated using a "significant fragment of English"—a set of hand-crafted, linguistically complex sentences involving coordination, relativization, and donkey pronoun binding.

The performance gains were substantial:

  • Search Space Reduction: For a sentence containing five quantifiers, the Minimal Construction strategy reduced the number of candidate Logical Forms from 50,830 to just 64.
  • Processing Speed: A complex sentence that required 50 seconds to process using standard methods was resolved in 0.45 seconds using quasi-partitioning.
  • Stress Testing: The system successfully processed a massive sentence containing nine quantifiers—representing 362,880 ($9!$) theoretical orderings—in just 0.16 seconds on a Symbolics 3645 Lisp machine.

Conclusion and Future Directions

Epstein’s work demonstrates that the perceived computational cost of principle-based linguistics is often a matter of implementation strategy rather than inherent theoretical flaws. By ordering constraints effectively and using divide-and-conquer techniques like quasi-partitioning, QSB achieves real-time performance on highly complex inputs.

However, the author identifies several areas for further development. The system does not yet handle "branching quantifiers" (where quantifiers are independent of one another), and the target language—an enriched predicate logic—could be further refined to capture more nuanced natural language meanings. Future iterations of the work aim to integrate a fully principle-based parser to replace the recursive descent model used in the prototype.

Summary updated

BibTeX
@inproceedings{epstein1988principle,
  author = {Samuel S. Epstein},
  title = {{Principle-Based Interpretation of Natural Language Quantifiers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure