Linear Text Segmentation Using Affinity Propagation

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 284–293, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Linear Text Segmentation Using Affinity Propagation Anna Kazantseva School of Electrical Engineering and Computer Science, University of Ottawa ankazant@site.uottawa.ca Stan Szpakowicz School of Electrical Engineering and Computer Science, University of Ottawa & Institute of Computer Science, Polish Academy of Sciences szpak@site.uottawa.ca Abstract This paper presents a new algorithm for lin- ear text segmentation. It is an adaptation of Affinity Propagation, a state-of-the-art clus- tering algorithm in the framework of factor graphs. Affinity Propagation for Segmenta- tion, or APS, receives a set of pairwise simi- larities between data points and produces seg- ment boundaries and segment centres – data points which best describe all other data points within the segment. APS iteratively passes messages in a cyclic factor graph, until conver- gence. Each iteration works with information on all available similarities, resulting in high- quality results. APS scales linearly for realistic segmentation tasks. We derive the algorithm from the original Affinity Propagation formu- lation, and evaluate its performance on topi- cal text segmentation in comparison with two state-of-the art segmenters. The results sug- gest that APS performs on par with or outper- forms these two very competitive baselines. 1 Introduction In complex narratives, it is typical for the topic to shift continually. Some shifts are gradual, others – more abrupt. Topical text segmentation identifies the more noticeable topic shifts. A topical segmenter’s output is a very simple picture of the document’s structure. Segmentation is a useful intermediate step in such applications as subjectivity analysis (Stoy- anov and Cardie, 2008), automatic summarization (Haghighi and Vanderwende, 2009), question an- swering (Oh, Myaeng, and Jang, 2007) and others. That is why improved quality of text segmentation can benefit other language-processing tasks. We present Affinity Propagation for Segmenta- tion (APS), an adaptation of a state-of-the-art clus- tering algorithm, Affinity Propagation (Frey and Dueck, 2007; Givoni and Frey, 2009).1 The origi- nal AP algorithm considerably improved exemplar- based clustering both in terms of speed and the qual- ity of solutions. That is why we chose to adapt it to segmentation. At its core, APS is suitable for seg- menting any sequences of data, but we present it in the context of segmenting documents. APS takes as input a matrix of pairwise similarities between sen- tences and, for each sentence, a preference value which indicates an a priori belief in how likely a sentence is to be chosen as a segment centre. APS outputs segment assignments and segment cen- tres – data points which best explain all other points in a segment. The algorithm attempts to maximize net similarity – the sum of similarities between all data points and their respective segment centres. APS operates by iteratively passing messages in a factor graph (Kschischang, Frey, and Loeliger, 2001) until a good set of segments emerges. Each iteration considers all similarities – takes into ac- count all available information. An iteration in- cludes …

Content truncated to 500 words