Evaluating Text Segmentation using Boundary Edit Distance

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1702–1712, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Evaluating Text Segmentation using Boundary Edit Distance Chris Fournier University of Ottawa Ottawa, ON, Canada cfour037@eecs.uottawa.ca Abstract This work proposes a new segmentation evaluation metric, named boundary simi- larity (B), an inter-coder agreement coef- ficient adaptation, and a confusion-matrix for segmentation that are all based upon an adaptation of the boundary edit distance in Fournier and Inkpen (2012). Existing seg- mentation metrics such as Pk, WindowD- iff, and Segmentation Similarity (S) are all able to award partial credit for near misses between boundaries, but are biased towards segmentations containing few or tightly clustered boundaries. Despite S’s improvements, its normalization also pro- duces cosmetically high values that over- estimate agreement & performance, lead- ing this work to propose a solution. 1 Introduction Text segmentation is the task of splitting text into segments by placing boundaries within it. Seg- mentation is performed for a variety of purposes and is often a pre-processing step in a larger task. E.g., text can be topically segmented to aid video and audio retrieval (Franz et al., 2007), question answering (Oh et al., 2007), subjectivity analysis (Stoyanov and Cardie, 2008), and even summa- rization (Haghighi and Vanderwende, 2009). A variety of segmentation granularities, or atomic units, exist, including segmentations at the morpheme (e.g., Sirts and Alum¨ae 2012), word (e.g., Chang et al. 2008), sentence (e.g., Rey- nar and Ratnaparkhi 1997), and paragraph (e.g., Hearst 1997) levels. Between each atomic unit lies the potential to place a boundary. Segmentations can also represent the structure of text as being organized linearly (e.g., Hearst 1997), hierarchi- cally (e.g., Eisenstein 2009), etc. Theoretically, segmentations could also contain varying bound- ary types, e.g., two boundary types could differen- tiate between act and scene breaks in a play. Because of its value to natural language pro- cessing, various text segmentation tasks have been automated such as topical segmentation— for which a variety of automatic segmenters exist (e.g., Hearst 1997, Malioutov and Barzilay 2006, Eisenstein and Barzilay 2008, and Kazantseva and Szpakowicz 2011). This work addresses how to best select an automatic segmenter and which seg- mentation metrics are most appropriate to do so. To select an automatic segmenter for a particu- lar task, a variety of segmentation evaluation met- rics have been proposed, including Pk (Beefer- man and Berger, 1999, pp. 198–200), WindowDiff (WD; Pevzner and Hearst 2002, p. 10), and most recently Segmentation Similarity (S; Fournier and Inkpen 2012, p. 154–156). Each of these met- rics have a variety of flaws: Pk and WindowD- iff both under-penalize errors at the beginning of segmentations (Lamprier et al., 2007) and have a bias towards favouring segmentations with few or tightly-clustered boundaries (Niekrasz and Moore, 2010), while S produces overly optimistic values due to its normalization (shown later). To overcome the flaws of existing text segmen- tation metrics, this work proposes a new series of metrics derived from an adaptation of …

Content truncated to 500 words