Quantifier Scoping in the SRI Core Language Engine

Douglas B. MoranACL 1988 · DOI

Introduction

Natural language is inherently ambiguous, particularly when it comes to "quantifier scoping." Sentences containing multiple quantifiers—words like every, each, a, or some—often support multiple logical interpretations. For instance, in the sentence "John visited every house on a street," does it mean one specific street where he visited all the houses, or that for every house he visited, it was located on some street? This paper introduces an efficient, rule-based algorithm implemented within the SRI Core Language Engine (CLE) to resolve these ambiguities by generating and ranking the most likely interpretations.

The Scoping Problem

Humans resolve scoping ambiguities using a complex interplay of syntax, logic, and common sense. For computers, however, generating and ranking these possibilities is computationally expensive. The challenge lies in providing a systematic way to produce logical forms in order of preference without exhaustive search or redundant processing. The proposed system addresses this by separating linguistic rules from domain-specific knowledge.

Methodology

The SRI CLE utilizes a two-phase approach to scoping:

  1. Linguistic Phase: This phase uses surface position, syntactic structure, and determiner types to generate a ranked list of possible scopings.
  2. Domain/Discourse Phase: This phase applies world knowledge to penalize logically possible but physically unlikely readings.

The "Qterm" Store

The technical core of the algorithm is the "quantifier store." Unlike previous methods that repeatedly traverse and copy logical trees, this algorithm collects quantifiers into a structured forest of "qtrees." It then "pulls" them out of storage to build the final scoped logical form. This structured approach maintains relative relationships between nested quantifiers and prevents the generation of syntactically impossible logical forms.

Preference Rules

To determine which quantifier takes wide scope, the system employs pairwise comparison rules, such as:

  • The "Each" Rule: "Each" typically takes wide scope over other determiners.
  • Surface Order: A general preference exists to maintain the order in which words appear.
  • Structural Constraints: Quantifiers are generally restricted from being "raised" out of relative clauses or across multiple clause boundaries.

Evaluation and Datasets

The algorithm was evaluated against a curated set of 45 linguistic examples representing various scoping challenges, including nested quantifiers, negation, and prepositional phrases.

Examples of quantifier scoping challenges involving different determiners and sentence structures.

These examples, such as those shown in the figures, test the system's ability to handle variations in determiners (e.g., "every" vs. "each") and structural complexity (e.g., prepositional phrases within noun phrases).

Structural variations in noun phrases and prepositional phrases used to test scoping constraints.

Key Results and Insights

  • Performance: The proposed algorithm is typically an order of magnitude faster than standard predecessors (like the Hobbs and Shieber algorithm) for sentences with four or more quantifiers.
  • Logical Deduplication: The system successfully identifies and discards logically equivalent scopings, ensuring the output is not overwhelmed by redundant interpretations.
  • Ranking Accuracy: The rule-based system correctly predicts human preferences in complex cases, such as the differing scope preferences in "John visited every house on a street" versus "John visited every house on a square."
  • Efficiency through Structure: Treating the quantifier store as a structured collection rather than a flat list ensures that the algorithm maintains the integrity of nested structures.

Conclusion and Future Work

While the linguistic phase of the SRI CLE is highly effective, the integration of real-world domain knowledge to filter scopings remains a primary area for future development. Additionally, the current version does not yet handle mass nouns, collective readings, or complex pronoun-quantifier interactions known as "donkey sentences." Despite these limitations, the system provides a robust and efficient baseline for automated quantifier resolution.

Summary updated

BibTeX
@inproceedings{moran1988quantifier,
  author = {Douglas B. Moran},
  title = {{Quantifier Scoping in the SRI Core Language Engine}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1988},
  doi = {10.3115/982023.982028},
}
Figure