Flexible Text Segmentation with Structured Multilabel Classification

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 987–994, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Flexible Text Segmentation with Structured Multilabel Classification Ryan McDonald Koby Crammer Fernando Pereira Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 {ryantm,crammer,pereira}@cis.upenn.edu Abstract Many language processing tasks can be re- duced 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 segmenta- tion based on ideas from multilabel clas- sification. Using this model, we can natu- rally represent segmentation problems in- volving overlapping and non-contiguous segments. We evaluate the model on en- tity extraction and noun-phrase chunking and show that it is more accurate for over- lapping and non-contiguous segments, but it still performs well on simpler data sets for which sequential tagging has been the best method. 1 Introduction Text segmentation is a basic task in language pro- cessing, with applications such as tokenization, sen- tence splitting, named-entity extraction, and chunk- ing. Many parsers, translation systems, and extrac- tion systems rely on such segmentations to accu- rately process the data. Depending on the applica- tion, segments may be tokens, phrases, or sentences. However, in this paper we primarily focus on seg- menting sentences into tokens. The most common approach to text segmenta- tion is to use finite-state sequence tagging mod- els, in which each atomic text element (character or token) is labeled with a tag representing its role in a segmentation. Models of that form include hidden Markov models (Rabiner, 1989; Bikel et al., 1999) as well as discriminative tagging mod- els based on maximum entropy classification (Rat- naparkhi, 1996; McCallum et al., 2000), conditional random fields (Lafferty et al., 2001; Sha and Pereira, 2003), and large-margin techniques (Kudo and Mat- sumoto, 2001; Taskar et al., 2003). Tagging mod- els are the best previous methods for text segmen- tation. However, their purely sequential form limits their ability to naturally handle overlapping or non- contiguous segments. We present here an alternative view of segmenta- tion as structured multilabel classification. In this view, a segmentation of a text is a set of segments, each of which is defined by the set of text positions that belong to the segment. Thus, a particular seg- ment may not be a set of consecutive positions in the text, and segments may overlap. Given a text x = x1 · · · xn, the set of possible segments, which corresponds to the set of possible classification la- bels, is seg(x) = {O, I}n; for y ∈ seg(x), yi = I iff xi belongs to the segment. Then, our segmen- tation task is to determine which labels are correct segments in a given text. We have thus a structured multilabel classification problem: each instance, a text, may have multiple structured labels, represent- ing each of its segments. These labels are structured in that they do not come from a predefined …

Content truncated to 500 words