Text Segmentation Using Exponential Models

Text Segmentation Using Exponential Models* Doug Beeferman Adam Berger John Lafferty School of Computer Science Carnegie Mellon University Abstract This paper introduces a new statistical ap- proach to partitioning text automatically into coherent segments. Our approach en- lists both short-range and long-range lan- guage models to help it sniff out likely sites of topic changes in text. To aid its search, the system consults a set of simple lexical hints it has learned to associate with the presence of boundaries through inspection of a large corpus of annotated data. We also propose a new probabilistically mo- tivated error metric for use by the natu- ral language processing and information re- trieval communities, intended to supersede precision and recall for appraising segmen- tation algorithms. Qualitative assessment of our algorithm as well as evaluation using this new metric demonstrate the effective- ness of our approach in two very different domains, Wall Street Journal articles and the TDT Corpus, a collection of newswire articles and broadcast news transcripts. 1 Introduction The task we address in this paper might seem on the face of it rather elementary: identify where one re- gion of text ends and another begins. This work was motivated by the observations that such a seemingly simple problem can actually prove quite difficult to automate, and that a tool for partitioning a stream of undifferentiated text (or multimedia) into coher- ent regions would be of great benefit to a number of existing applications. The task itself is ill-defined: what exactly is meant by a "region" of text? We confront this issue by *Research supported in part by NSF grant IRI- 9314969, DARPA AASERT award DAAH04-95-1-0475, and the ATR Interpreting Telecommunications Research Laboratories. adopting an empirical definition of segment. At our disposal is a collection of online data (38 million words of Wall Street Journal archives and another 150 million words from selected news broadcasts) annotated with the boundaries between regions-- articles or news reports, respectively. Given this in- put, the task of constructing a segmenter may be cast as a problem in machine learning: glean from the data a set of hints about where boundaries occur, and use these hints to inform a decision on where to place breaks in unsegmented data. A general-purpose tool for partitioning expository text or multimedia data into coherent regions would have a number of immediate practical uses. In fact, this research was inspired by a problem in informa- tion retrieval: given a large unpartitioned collection of expository text and a user's query, return a collec- tion of coherent segments matching the query. Lack- ing a segmenting tool, an II:t application may be able to locate positions in its database which are strong matches with the user's query, but be unable to de- termine how much of the surrounding data to pro- vide to the user. This can manifest itself in quite unfortunate ways. For example, a video-on-demand application (such as the one described in (Christel et al., 1995)) responding to a query about a recent …

Content truncated to 500 words