Hierarchical Topical Segmentation with Affinity Propagation

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 37–47, Dublin, Ireland, August 23-29 2014. Hierarchical Topical Segmentation with Affinity Propagation Anna Kazantseva & Stan Szpakowicz School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Ontario, Canada {ankazant,szpak}@eecs.uottawa.ca Abstract We present a hierarchical topical segmenter for free text. Hierarchical Affinity Propagation for Segmentation (HAPS) is derived from a clustering algorithm Affinity Propagation. Given a doc- ument, HAPS builds a topical tree. The nodes at the top level correspond to the most prominent shifts of topic in the document. Nodes at lower levels correspond to finer topical fluctuations. For each segment in the tree, HAPS identifies a segment centre – a sentence or a paragraph which best describes its contents. We evaluate the segmenter on a subset of a novel manually segmented by several annotators, and on a dataset of Wikipedia articles. The results suggest that hierarchical segmentations produced by HAPS are better than those obtained by iteratively running several one-level segmenters. An additional advantage of HAPS is that it does not require the “gold standard” number of segments in advance. 1 Introduction When an NLP application works with a document, it may benefit from knowing something about this document’s high-level structure. Text summarization (Haghighi and Vanderwende, 2009), question an- swering (Oh et al., 2007) and information retrieval (Ponte and Croft, 1998) are some of the examples of such applications. Topical segmentation is a lightweight form of such structural analysis: given a sequence of sentences or paragraphs, split it into a sequence of topical segments, each characterized by a certain degree of topical unity. This is particularly useful for texts with little structure imposed by the author, such as speech transcripts, meeting notes or literature. The past decade has witnessed significant progress in the area of text segmentation. Most of the topical segmenters (Malioutov and Barzilay, 2006; Eisenstein and Barzilay, 2008; Kazantseva and Szpakowicz, 2011; Misra et al., 2011; Du et al., 2013) can only produce single-level segmentation, a worthy endeavour in and of itself. Yet, to view the structure of a document linearly, as a sequence of segments, is in certain discord with most theories of discourse structure, where it is more customary to consider documents as trees (Mann and Thompson, 1988; Marcu, 2000; Hernault et al., 2010; Feng and Hirst, 2012) or graphs (Wolf and Gibson, 2006). Regardless of the theory, we hypothesize that it may be useful to have an idea about fluctuations of topic in documents beyond the coarsest level. It is the contribution of this work that we develop such a hierarchical segmenter, implement it and do our best to evaluate it. The segmenter described here is HAPS – Hierarchical Affinity Propagation for Segmentation. It is closely based on a graphical model for hierarchical clustering called Hierarchical Affinity Propagation (Givoni et al., 2011). It is a similarity-based segmenter. It takes as input a matrix of similarities between atomic units of text in the sequence to be segmented (sentences or …

Content truncated to 500 words