Minimum Cut Model for Spoken Lecture Segmentation

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 25–32, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Minimum Cut Model for Spoken Lecture Segmentation Igor Malioutov and Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {igorm,regina}@csail.mit.edu Abstract We consider the task of unsupervised lec- ture segmentation. We formalize segmen- tation as a graph-partitioning task that op- timizes the normalized cut criterion. Our approach moves beyond localized com- parisons and takes into account long- range cohesion dependencies. Our results demonstrate that global analysis improves the segmentation accuracy and is robust in the presence of speech recognition errors. 1 Introduction The development of computational models of text structure is a central concern in natural language processing. Text segmentation is an important in- stance of such work. The task is to partition a text into a linear sequence of topically coherent segments and thereby induce a content structure of the text. The applications of the derived rep- resentation are broad, encompassing information retrieval, question-answering and summarization. Not surprisingly, text segmentation has been ex- tensively investigated over the last decade. Fol- lowing the first unsupervised segmentation ap- proach by Hearst (1994), most algorithms assume that variations in lexical distribution indicate topic changes. When documents exhibit sharp varia- tions in lexical distribution, these algorithms are likely to detect segment boundaries accurately. For example, most algorithms achieve high per- formance on synthetic collections, generated by concatenation of random text blocks (Choi, 2000). The difficulty arises, however, when transitions between topics are smooth and distributional vari- ations are subtle. This is evident in the perfor- mance of existing unsupervised algorithms on less structured datasets, such as spoken meeting tran- scripts (Galley et al., 2003). Therefore, a more refined analysis of lexical distribution is needed. Our work addresses this challenge by casting text segmentation in a graph-theoretic framework. We abstract a text into a weighted undirected graph, where the nodes of the graph correspond to sentences and edge weights represent the pair- wise sentence similarity. In this framework, text segmentation corresponds to a graph partitioning that optimizes the normalized-cut criterion (Shi and Malik, 2000). This criterion measures both the similarity within each partition and the dissimilar- ity across different partitions. Thus, our approach moves beyond localized comparisons and takes into account long-range changes in lexical distri- bution. Our key hypothesis is that global analysis yields more accurate segmentation results than lo- cal models. We tested our algorithm on a corpus of spo- ken lectures. Segmentation in this domain is chal- lenging in several respects. Being less structured than written text, lecture material exhibits digres- sions, disfluencies, and other artifacts of sponta- neous communication. In addition, the output of speech recognizers is fraught with high word er- ror rates due to specialized technical vocabulary and lack of in-domain spoken data for training. Finally, pedagogical considerations call for fluent transitions between different topics in a lecture, further complicating the segmentation task. Our experimental results confirm our hypothe- …

Content truncated to 500 words