Sentence Boundary Detection and the Problem with the U.S.

Dan GillickNAACL 2009

TL;DR

This paper presents a state-of-the-art statistical system for Sentence Boundary Detection (SBD), achieving the best reported error rate on the standard Wall Street Journal corpus. The authors highlight the challenges posed by abbreviations like "U.S." and demonstrate that a carefully engineered set of features, combined with a Support Vector Machine, significantly outperforms previous methods.

What Problem Does This Paper Address?

Identifying sentence boundaries is a fundamental step in many Natural Language Processing (NLP) tasks, from language modeling to text summarization. However, the humble period (.) is notoriously ambiguous. It can signal the end of a sentence, but it also appears in abbreviations (e.g., "Mr.", "U.S."), numbers (e.g., "3.14"), and other contexts. Accurately distinguishing sentence-ending periods from these other uses is a non-trivial problem. Even a small error rate can have a cascading negative effect on downstream NLP applications. For instance, a 1% error rate in SBD can lead to a 10% chance of a damaged 10-sentence summary, whereas a 0.25% error rate reduces this to a 2.5% chance.

Methods

The authors propose a fully statistical approach to SBD, moving away from hand-crafted rules and lists of abbreviations. Their system uses a Support Vector Machine (SVM) with a linear kernel. The core of their method lies in a carefully selected set of binary features extracted from the context surrounding a potential sentence boundary (the word before and the word after the period). These features capture various linguistic cues, including:

  • Lexical features: The specific words immediately before and after the period.
  • Capitalization: Whether the word following the period is capitalized (a strong indicator of a new sentence).
  • Token length: The length of the word preceding the period (abbreviations tend to be shorter).
  • Frequency-based features: Log counts of occurrences of the preceding or succeeding word, with or without a period, or with specific capitalization patterns.

They also explore adding features related to abbreviations, but find that simply using a list of abbreviations can sometimes increase errors, suggesting a more nuanced approach is needed.

Datasets

The primary dataset used for training and evaluation is the Wall Street Journal (WSJ) corpus, specifically sections 03-06. This corpus contains approximately 27,000 examples of ambiguous periods. The authors also mention using a large, unlabeled corpus (1 million words) for training and a separate WSJ dataset for testing. They also reference results on the Brown corpus and the Complete Works of Edgar Allen Poe to demonstrate the generalizability of their model.

Key Insights and Ideas

  • The "U.S." problem: Abbreviations like "U.S." are particularly challenging because they appear frequently and their capitalization can be ambiguous (e.g., "U.S. Government" vs. "U.S. Commission"). These types of abbreviations account for a significant portion of the system's errors.
  • Feature engineering is crucial: While a simple SVM is used, the performance gains come from the carefully chosen features. Combining basic lexical and capitalization features significantly reduces errors.
  • Abbreviation lists are a double-edged sword: While intuitively helpful, simply flagging words as abbreviations can be detrimental because some abbreviations do end sentences, while others don't. The system's performance improves when it learns these nuances through features rather than explicit lists.
  • Tokenization matters: Accurate tokenization is highlighted as a critical prerequisite for good SBD performance. Mismatched tokenization between training and testing data can double the error rate.
  • Binary classification is sufficient (for this approach): The authors explore a three-class problem (sentence boundary, abbreviation, abbreviation+sentence boundary) and a structured classification approach but find that a binary classifier with well-chosen features performs best, likely due to the limited number of true "abbreviation+sentence boundary" examples.

Key Results

The paper reports achieving the best known error rate of 0.25% on the standard WSJ test set using a combination of features (features 1+2+3+4+5+6+7+8 in Table 1). This is a significant improvement over previous methods, which reported error rates around 0.9% to 1.65%. The authors' system makes only 67 errors out of 26,977 examples on the WSJ test set.

Limitations and Future Work

  • Abbreviation complexity: The authors acknowledge that abbreviations, especially those related to places (like "U.K.", "N.Y.", "Pa."), are a major source of errors. They suggest that designing features to exploit additional context, potentially involving parsing, might help resolve these complex cases.
  • Language dependence: While their system is provided in English, they note that they have not tested models in other languages.
  • Structured classification: They suggest that future work could explore more structured classification approaches to better handle the three potential classes (sentence boundary, abbreviation, abbreviation+sentence boundary).
  • Availability: The authors have made their implementation, including tokenization, open-source and available to the public.

Summary updated

BibTeX
@inproceedings{gillick2009sentence,
  author = {Dan Gillick},
  title = {{Sentence Boundary Detection and the Problem with the U.S.}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure