Getting More from Segmentation Evaluation

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 362–366, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Getting More from Segmentation Evaluation Martin Scaiano University of Ottawa Ottawa, ON, K1N 6N5, Canada mscai056@uottawa.ca Diana Inkpen University of Ottawa Ottawa, ON, K1N 6N5, Canada diana@eecs.uottawa.com Abstract We introduce a new segmentation evaluation measure, WinPR, which resolves some of the limitations of WindowDiff. WinPR distin- guishes between false positive and false nega- tive errors; produces more intuitive measures, such as precision, recall, and F-measure; is in- sensitive to window size, which allows us to customize near miss sensitivity; and is based on counting errors not windows, but still pro- vides partial reward for near misses. 1 Introduction WindowDiff (Pevzner and Hearst, 2002) has be- come the most frequently used measure to evalu- ate segmentation. Segmentation is the task of di- viding a stream of data (text or other media) into coherent units. These units may be motivated top- ically (Malioutov and Barzilay, 2006), structurally (Stokes, 2003) (Malioutov et al., 2007) (Jancsary et al., 2008), or visually (Chen et al., 2008), depending on the domain and task. Segmentation evaluation is difficult because exact comparison of boundaries is too strict; a partial reward is required for close boundaries. 2 WindowDiff “The WindowDiff metric is a variant of the Pk mea- sure, which penalizes false positives and near misses equally.” (Malioutov et al., 2007). WindowDiff uses a sliding window over the segmentation; each win- dow is evaluated as correct or incorrect. WindowD- iff is effectively 1 − accuracy for all windows, but accuracy is sensitive to the balance of positive and negative data being evaluated. The positive and negative balance is determined by the window size. Small windows produce more negatives, thus WindowDiff recommends using a window size (k) of half the average segment length. This produces an almost equal number of positive windows (con- taining boundaries) and negative windows (without boundaries). Equation 1 represents the window size (k), where N is the total number of sentences (or content units). Equation 2 is WindowDiff’s traditional definition, where R is the number of reference boundaries in the window from i to i+k, and C is the number of computed boundaries in the same window. The comparison (> 0) is sometimes forgotten, which produces strange values not bound between 0 and 1; thus we prefer equation 3 to represent WindowDiff, as it emphasizes the comparison. k = N 2 * number of segments (1) WindowDiff = 1 N − k N−k � i=0 (|Ri,i+k − Ci,i+k| > 0)(2) WindowDiff = 1 N − k N−k � i=0 (Ri,i+k ̸= Ci,i+k) (3) Figure 1 illustrates WindowDiff’s sliding win- dow evaluation. Each rectangle represents a sen- tence, while the shade indicates to which segment it truly belongs (reference segmentation). The ver- tical line represents a computed boundary. This ex- ample contains a near miss (misaligned boundary). In this example, we are using a window size of 5. The …

Content truncated to 500 words