Evaluating Centering for Sentence Ordering in Two New Domains

Nikiforos KaramanisNAACL 2006

TL;DR

This paper investigates the effectiveness of Centering Theory, a linguistic framework for modeling text coherence, in automatically ordering sentences. By applying Centering-based metrics to new datasets, the authors find that a simple metric focusing on avoiding "NOCB" (No Common Ground) transitions is surprisingly robust, outperforming more complex Centering-derived metrics across multiple domains. This suggests that basic referential coherence might be a stronger predictor of good sentence order than previously assumed.

What Problem Does This Paper Address?

Producing coherent and readable text is a fundamental challenge in natural language generation. Simply having the right information isn't enough; the order in which sentences are presented significantly impacts comprehension. Arbitrarily reordering sentences from an understandable text often results in nonsensical output, highlighting the importance of sentence ordering. A key aspect of text coherence is "entity coherence," which concerns how noun phrase (NP) referents link sentences together. Centering Theory has been a prominent computational linguistics framework for modeling this entity coherence for decades. However, empirical evaluations of Centering-based metrics for sentence ordering have often been limited to specific domains or small datasets. This paper aims to bridge this gap by evaluating Centering-based metrics on new, larger datasets and in multiple domains, providing a more comprehensive empirical assessment.

Methods

The core of this paper is the empirical evaluation of Centering-based metrics for sentence ordering. The authors adopt a methodology introduced by Karamanis et al. (2004), which treats the naturally occurring sentence order in a text as the "gold standard" (GSO). Metrics are then penalized based on how often they produce orderings that are equally or better than the GSO. To make this evaluation practical, instead of exhaustively enumerating all possible sentence orderings (which grows factorially), the authors employ methods that allow for sampling a large number of alternative orderings.

The paper focuses on four specific Centering-based metrics:

  • M.NOCB: A baseline metric that prioritizes orderings with the fewest "NOCB" (No Common Ground) transitions, where a NOCB occurs when two consecutive sentences share no common referent.
  • M.CHEAP: Selects orderings with the fewest violations of "CHEAPNESS" (a concept related to referent salience and grammatical role).
  • M.KP: A combined metric that sums up violations of CHEAPNESS, COHERENCE, and SALIENCE.
  • M.BFP: Utilizes transition preferences from Brennan et al. (1987).

The authors also describe the data transformation process, which involves creating "CF lists" (Centering Focus lists) for each sentence, representing the grammatical roles of referents. These CF lists are then used to compute the Centering concepts and evaluate the metrics.

Datasets

The paper evaluates the Centering-based metrics using data from two sources:

  • NEWS corpus: A collection of 200 articles from the North American News Corpus.
  • ACCS corpus: A collection of 200 accident narratives from the National Transportation Safety Board database.

These datasets were previously used by Barzilay and Lapata (2005) and Barzilay and Lee (2004) for evaluating other coherence models. The authors note that their approach treats all texts in these corpora as testing data, as the Centering-based metrics are deployable on unseen texts without training. They also reference the GNOME corpus (used by Karamanis et al. (2004)) for comparison.

Key Insights and Ideas

  • Simplicity Trumps Complexity: The most striking finding is that the baseline M.NOCB metric, which simply penalizes transitions where no referent is carried over between sentences, performs remarkably well. This suggests that basic referential continuity is a highly significant factor in sentence ordering, potentially more so than more intricate Centering concepts like CHEAPNESS, COHERENCE, or SALIENCE.
  • Robustness Across Domains: The M.NOCB metric's strong performance is consistent across the NEWS and ACCS corpora, indicating its generalizability beyond a single domain. This robustness is a key contribution, as previous evaluations were often domain-specific.
  • Practicality vs. Theoretical Completeness: While M.NOCB is the most effective metric in terms of accurately identifying the gold standard ordering, its "classification rate" (the proportion of alternative orderings that are considered more coherent) is still relatively high. This means that even M.NOCB would require exploring a significant number of alternatives to reliably find the best ordering, suggesting that purely Centering-based approaches might not be sufficient for practical, fully automated sentence ordering systems without further enhancements.

Key Results

The experimental results, presented in Tables 2 and 3, show that M.NOCB consistently outperforms M.CHEAP, M.KP, and M.BFP in terms of identifying the gold standard sentence order. For instance, in the NEWS corpus (200 texts), M.NOCB has a lower classification rate than M.CHEAP for 155 texts, M.KP for 131 texts, and M.BFP for 121 texts. Similar patterns are observed in the ACCS corpus. The p-values from the sign tests indicate that these differences are statistically significant. The authors also note that the results are strikingly similar to those reported for the GNOME corpus, despite the smaller size of the GNOME sample.

Limitations and Future Work

The authors acknowledge a significant limitation: the "classification rate" of M.NOCB, while better than its competitors, is still high (e.g., 30.90% in NEWS, 15.51% in ACCS). This means that on average, M.NOCB would still need to consider a substantial fraction of alternative orderings to find the best one, making it impractical for direct use in an ordering algorithm without further improvements.

For future work, the authors propose:

  • Directly evaluating other methods (like Barzilay and Lapata's) using their experimental setup and a larger number of alternative orderings.
  • Supplementing M.NOCB with additional features of coherence to improve its performance.

Summary updated

BibTeX
@inproceedings{karamanis2006evaluating,
  author = {Nikiforos Karamanis},
  title = {{Evaluating Centering for Sentence Ordering in Two New Domains}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
}
Figure