Linear Text Segmentation using a Dynamic Programming Algorithm

Linear Text Segmentation using a Dynamic Programming Algorithm Athanasios Kehagias Dept. of Math., Phys. and Comp. Sciences Aristotle Univ of Thessaloniki GREECE kehagias@egnatia.ee.auth.gr Fragkou Pavlina , Vassilios Petridis Dept. of Elect. and Computer Eng. Aristotle Univ of Thessaloniki GREECE fragou@egnatia.ee.auth.gr , petridis@eng.auth.gr Abstract In this paper we introduce a dynamic programming algorithm to perform lin- ear text segmentation by global mini- mization of a segmentation cost function which consists of: (a) within-segment word similarity and (b) prior informa- tion about segment length. The eval- uation of the segmentation accuracy of the algorithm on Choi's text collection showed that the algorithm achieves the best segmentation accuracy so far re- ported in the literature. Keywords: Text Segmentation, Docu- ment Retrieval, Information Retrieval, Machine Learning. 1 Introduction Text segmentation is an important problem in in- formation retrieval. Its goal is the division of a text into homogeneous ("lexically coherent") seg- ments, i.e segments exhibiting the following prop- erties: (a) each segment deals with a particular subject and (b) contiguous segments deal with dif- ferent subjects. Those segments can be retrieved from a large database of unformatted (or loosely formatted) text as being relevant to a query. This paper presents a dynamic programming al- gorithm which performs linear segmentation 1 by global minimization of a segmentation cost. The segmentation cost is defined by a function consist- ing of two factors: (a) within-segment word sim- ilarity and (b) prior information about segment length. Our algorithm has the advantage of be- ing able to be applied to either large texts - to seg- ment them into their constituent parts (e.g. to seg- ment an article into sections) - or to a stream of independent, concatenated texts (e.g. to segment a transcript of news into separate stories). For the calculation of the segment homogeneity (or alternatively heterogeneity) of a text, several segmentation algorithms using a variety of crite- ria have been proposed in the literature. Some of those use linguistic criteria such as cue phrases, punctuation marks, prosodic features, reference, syntax and lexical attraction (Beeferman et al., 1997; Hirschberg and Litman, 1993; Passoneau and Litman, 1993). Others, following Halliday and Hasan's theory (Halliday and Hasan, 1976), utilize statistical similarity measures such as word cooccurrence. For example the linear discourse segmentation algorithm proposed by Morris and Hirst (Morris and Hirst, 1991) is based on lexi- cal cohesion relations determined by use of Ro- get's thesaurus (Roget, 1977). In the same direc- tion Kozima's algorithm (Kozima, 1993; Kozima and Furugori, 1993) computes the semantic sim- ilarity between words using a semantic network constructed from a subset of the Longman Dictio- nary of Contemporary English. Local minima of the similarity scores correspond to the positions of topic boundaries in the text. Youmans� (Youmans, 1991) and later l As opposed to hierarchical segmentation (Yaari, 1997)� Hearst (Hearst and Plaunt, 1993; Hearst, 1994) 171 focused on the similarity between adjacent part of texts. They used a sliding window of text and plotted the number of first-used words in the window as a …

Content truncated to 500 words