Flexible Text Segmentation with Structured Multilabel Classification

Ryan T. McDonald, Koby Crammer, Fernando PereiraEMNLP 2005 · OpenReview

Abstract

Many language processing tasks can be reduced to breaking the text into segments with prescribed properties. Such tasks include sentence splitting, tokenization, named-entity extraction, and chunking. We present a new model of text segmentation based on ideas from multilabel classification. Using this model, we can naturally represent segmentation problems involving overlapping and non-contiguous segments. We evaluate the model on entity extraction and noun-phrase chunking and show that it is more accurate for overlapping and non-contiguous segments, but it still performs well on simpler data sets for which sequential tagging has been the best method.

The Bottleneck of Sequential Tagging

Most Natural Language Processing (NLP) tasks, such as Named Entity Recognition (NER) or noun-phrase chunking, have traditionally relied on sequential tagging. The industry standard uses the BIO (Beginning, Inside, Outside) scheme, where every word in a sentence is assigned exactly one tag.

However, this approach creates a fundamental bottleneck: it assumes segments are contiguous and non-overlapping. Real-world data is often messier. For example, in the phrase "Bill and Hilary Clinton," a standard tagger struggles to extract both "Bill Clinton" and "Hilary Clinton" because they overlap at the word "Clinton." Similarly, in technical domains like chemistry, entity names are frequently non-contiguous, interrupted by other words. This paper proposes a "structured multilabel classification" framework to overcome these constraints.

Methods: Segmentation as Multilabel Classification

Instead of asking "What is the tag for this word?", the authors reframe segmentation as a classification problem: "Is this specific set of word positions a valid segment?" By treating segments as independent entities rather than parts of a single sequence, the model can naturally identify overlapping and fragmented structures.

Key Innovations

  1. Segment-Based Scoring: The model uses a linear function to score potential segments defined as sets of indices (not necessarily adjacent).
  2. $k$-best Inference: To handle the exponential number of possible segments, a dynamic programming algorithm (similar to Viterbi) finds the $k$ highest-scoring segments.
  3. Learning with Margins: The authors adapted online learning algorithms to ensure "correct" segments are separated from "incorrect" ones by a specific mathematical margin.
  4. The "Skip" Feature: To model non-contiguous segments, features were introduced to explicitly bridge gaps between words (e.g., connecting "Bill" to "Clinton" while skipping "and Hilary").

Experimental Results

The model was evaluated on standard benchmarks (CoNLL 2000 and 2003) and a "stress test" using the PennBioIE dataset. The latter contains chemical substance names from MEDLINE abstracts, where approximately 6% of entities are overlapping or non-contiguous.

Performance on Chemical Substance Extraction (PennBioIE).

As shown in the results for chemical substance extraction, the multilabel approach achieved a significant performance boost, resulting in up to a 26% reduction in error compared to standard sequential models. On "cleaner" datasets like CoNLL, the model remained highly competitive with state-of-the-art Conditional Random Fields (CRFs), proving that the added flexibility does not degrade performance on traditional tasks.

Precision, Recall, and Thresholding

A key insight from the study is the model's conservative nature. It tends to exhibit very high precision but lower recall. Because the learning algorithm scores segments as invalid if they contain even minor negative evidence, the segments it does select are highly likely to be correct.

Precision, Recall, and F-measure vs. Threshold across different tasks.

By adjusting a "separation threshold," users can tune the model to be either more "cautious" (higher precision) or "brave" (higher recall). This flexibility allows the model to be tailored to specific application needs, such as high-stakes medical data extraction where precision is paramount.

Conclusion

Structured multilabel classification provides a robust alternative to sequential tagging for complex text segmentation. While the inference algorithm's $O(n^3)$ complexity is higher than traditional methods, the ability to handle overlapping and non-contiguous entities offers a major advantage for technical and messy real-world datasets. Future work will focus on automating threshold tuning and applying the framework to broader tasks like simultaneous sentence interpretation.

Summary updated

Abstract

Many language processing tasks can be reduced to breaking the text into segments with prescribed properties. Such tasks include sentence splitting, tokenization, named-entity extraction, and chunking. We present a new model of text segmentation based on ideas from multilabel classification. Using this model, we can naturally represent segmentation problems involving overlapping and non-contiguous segments. We evaluate the model on entity extraction and noun-phrase chunking and show that it is more accurate for overlapping and non-contiguous segments, but it still performs well on simpler data sets for which sequential tagging has been the best method.
BibTeX
@inproceedings{mcdonald2005flexible,
  author = {Ryan T. McDonald and Koby Crammer and Fernando Pereira},
  title = {{Flexible Text Segmentation with Structured Multilabel Classification}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  url = {https://openreview.net/forum?id=ByNEafZuZB},
}
Figure