A Generalized Reconstruction Algorithm for Ellipsis Resolution

Shalom Lappin, Hsue-Hueh ShihCOLING 1996

TL;DR

This paper introduces a novel, generalized algorithm for resolving various types of ellipsis in natural language processing. By focusing on syntactic reconstruction and establishing a correspondence between elided and antecedent structures, the algorithm offers a unified computational approach that handles VP ellipsis, pseudo-gapping, stripping, and gapping more comprehensively than previous methods.

What Problem Does This Paper Address?

Natural Language Processing (NLP) systems often struggle with ellipsis, where words or phrases are omitted but understood from context. This omission poses a significant challenge for systems designed to understand text or engage in dialogue because the missing information must be recovered. Traditional approaches to ellipsis resolution often fall into two camps: directly assigning a semantic interpretation or reconstructing the syntactic structure of the antecedent. This paper tackles the limitations of existing syntactic reconstruction methods, which often struggle with the diversity and complexity of ellipsis phenomena, particularly bare ellipsis cases where the elided material doesn't have a direct constituent-for-constituent correspondence in the antecedent.

Methods

The core of the paper is a generalized reconstruction algorithm for ellipsis resolution. The algorithm's central idea is to characterize ellipsis resolution as specifying a (partial) correspondence relation between the unrealized head of an elided clause and its arguments/adjuncts, and the realized head of a non-elided antecedent clause and its arguments/adjuncts.

The algorithm works by:

  1. Identifying an antecedent sentence for the ellipsis fragment.
  2. Taking the head verb of the antecedent as the new interpreted head (A') for the reconstructed clause.
  3. Filling argument slots in A' by first checking for phrases in the ellipsis fragment that match the required type. If no such phrase exists, it uses arguments from the antecedent's head verb.
  4. Constructing a list of adjunct phrases for A', adding adjuncts from the ellipsis fragment and inheriting any adjuncts from the antecedent's head verb that aren't present in the fragment.
  5. Generating a new syntactic structure by combining the filled argument and adjunct lists, reordering them to match the antecedent's structure.

This approach extends and modifies previous reconstruction strategies, notably for VP ellipsis, to encompass a wider range of ellipsis types.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical linguistic examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified Approach to Ellipsis: The algorithm's strength lies in its ability to handle diverse ellipsis types (VP ellipsis, pseudo-gapping, stripping, gapping) under a single, generalized framework, moving beyond type-specific solutions.
  • Syntactic Reconstruction as the Mediator: The paper strongly advocates for syntactic reconstruction as the primary mechanism for ellipsis resolution, arguing that it provides a more robust foundation than direct semantic interpretation for many cases.
  • Handling Bare Ellipsis: A significant contribution is the algorithm's ability to address bare ellipsis, particularly cases where adjuncts in the ellipsis site lack direct counterparts in the antecedent (e.g., example 8). The algorithm accommodates this by allowing adjuncts from the ellipsis site to be added to the reconstructed clause's adjunct list, even if they don't correspond to anything in the antecedent.
  • Importance of Syntactic Structure: The paper highlights that for certain ellipsis phenomena (like contrasting reciprocal pronoun interpretations in example 15), access to the full syntactic structure of the elided clause is crucial, a capability that semantic-only approaches might lack.

Key Results

The paper presents examples of the algorithm's output for VP ellipsis and pseudo-gapping, demonstrating its ability to generate reconstructed syntactic structures. It also illustrates how the algorithm handles bare argument and bare adjunct ellipsis cases (examples 7 and 8), and provides a mechanism for dealing with potentially unbounded adverbial adjuncts in ellipsis sites (example 11). The authors claim their algorithm has wider empirical coverage than other contemporary approaches.

Limitations and Future Work

  • Implementation Status: The algorithm has been partially implemented in Prolog for VP ellipsis and pseudo-gapping, with ongoing re-implementation for a modified HPSG grammar to handle a broader range of ellipsis phenomena.
  • Coverage Gaps: While the algorithm is generalized, the paper acknowledges that some approaches (like higher-order unification) might struggle with certain complex cases, implying that further refinement or integration might be necessary. The paper also notes that the higher-order unification analysis struggles with antecedentless bare adjuncts, a problem the proposed algorithm aims to solve.
  • Future Directions: The authors suggest the algorithm can be integrated into more comprehensive NLP systems for text and dialogue understanding. The ongoing implementation work indicates a clear path for future development and testing.

Summary updated

BibTeX
@inproceedings{lappin1996generalized,
  author = {Shalom Lappin and Hsue-Hueh Shih},
  title = {{A Generalized Reconstruction Algorithm for Ellipsis Resolution}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1996},
}
Figure