Parse Tree Fragmentation of Ungrammatical Sentences

Homa B. Hashemi, Rebecca HwaIJCAI 2016

Abstract

Statistical parsers trained on well-formed text often "hallucinate" complete syntactic structures when encountering ungrammatical input, such as text from language learners or machine translation systems. This paper introduces parse tree fragmentation, a framework designed to identify and extract only the coherent, reliable sub-structures of a parse. By isolating these fragments, we provide a more accurate syntactic representation for downstream tasks. Our evaluation on fluency judgment tasks demonstrates that simple features derived from these fragments significantly improve performance, achieving high accuracy in both English-as-a-Second Language (ESL) and Machine Translation (MT) domains.

Introduction: The Problem of "Over-Helpful" Parsers

Most state-of-the-art syntactic parsers are optimized for "clean" data, such as the Wall Street Journal corpus. When presented with ungrammatical input (e.g., "The members of the vote opposes any him"), these parsers are designed to produce a single, globally connected tree. To satisfy formal grammatical constraints, the parser often forces awkward or incorrect relationships, spreading the "damage" of a local error across the entire syntactic structure.

Comparison between a standard Stanford parse tree (a) and the proposed coherent fragments (b) for an ungrammatical sentence.

Rather than discarding these low-confidence parses or attempting pre-emptive correction, this research proposes a middle ground: identifying which parts of the parse tree are structurally sound (the "fragments") and discarding the edges that represent grammatical errors or parser confusion.

Methodology

The authors propose two primary methods for "cutting" a full parse tree into its constituent fragments:

1. Classification-based Parse Tree Fragmentation (CLF)

This approach treats fragmentation as a binary classification problem. For every edge in a parse tree, a Gradient Boosting Classifier determines whether to "keep" or "cut" it. The model leverages features such as node labels, tree depth, word N-grams from the English Gigaword corpus, and the frequency of the underlying grammar rule in the Penn Treebank.

2. Treebank-Based Fragmentation (TBF)

A deterministic "back-off" approach, TBF evaluates the commonality of specific grammar rules (e.g., $NP \rightarrow DT\ NN$) within a standard treebank. If a rule is rare or unusual, the system breaks the tree at that node to isolate the potentially problematic structure.

Conceptual illustration of the tree fragmentation process where unreliable edges are removed to form coherent sub-structures.

To train these models, "Gold Standard" fragments were created by aligning ungrammatical sentences with human-corrected paraphrases using tree-edit distance to pinpoint structural divergences.

Datasets and Evaluation

The study utilizes two domains of noisy text:

  • English-as-a-Second Language (ESL): The First Certificate in English (FCE) dataset, containing student writings and teacher corrections.
  • Machine Translation (MT): The LIG corpus, consisting of French-to-English translations and human-edited post-editions.
  • Background Corpus: The Agence France Press (AFE) section of the English Gigaword for N-gram statistics.

Key Results and Insights

The fragmentation process itself serves as a powerful signal for sentence quality. A sentence resulting in many small fragments is likely highly ungrammatical, whereas a few large chunks indicate higher fluency.

  • Performance: The combination of fragmentation features and Language Modeling (CLF + LM) achieved the highest accuracy on fluency judgment tasks: 82.2% on ESL data and 74.7% on MT data.
  • Feature Efficiency: Remarkably, just four simple features derived from fragments (number of fragments, average size, minimum size, and maximum size) outperformed complex feature sets containing over 60,000 variables.
  • Correlation: In regression tasks predicting the exact number of errors, fragmentation features showed a significantly stronger correlation ($r = 0.462$ for ESL) with human judgments than sentence length or standard language models alone.

Conclusion and Future Work

While the current fragmentation process is "post-hoc"---relying on an initial parse from the Stanford Parser---it successfully mitigates the impact of parser "hallucination." Future work aims to develop specialized fragmentation parsers that perform this task in a single step. Additionally, these fragments hold promise for Information Extraction (IE) tasks, where ignoring "broken" syntactic components could prevent the extraction of erroneous facts.

Summary updated

BibTeX
@inproceedings{hashemi2016parse,
  author = {Homa B. Hashemi and Rebecca Hwa},
  title = {{Parse Tree Fragmentation of Ungrammatical Sentences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}

Loading related content...

Figure