Segmentation Similarity and Agreement

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 152–161, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Segmentation Similarity and Agreement Chris Fournier University of Ottawa Ottawa, ON, Canada cfour037@eecs.uottawa.ca Diana Inkpen University of Ottawa Ottawa, ON, Canada diana@eecs.uottawa.ca Abstract We propose a new segmentation evaluation metric, called segmentation similarity (S), that quantifies the similarity between two segmen- tations as the proportion of boundaries that are not transformed when comparing them us- ing edit distance, essentially using edit dis- tance as a penalty function and scaling penal- ties by segmentation size. We propose several adapted inter-annotator agreement coefficients which use S that are suitable for segmenta- tion. We show that S is configurable enough to suit a wide variety of segmentation evalua- tions, and is an improvement upon the state of the art. We also propose using inter-annotator agreement coefficients to evaluate automatic segmenters in terms of human performance. 1 Introduction Segmentation is the task of splitting up an item, such as a document, into a sequence of segments by plac- ing boundaries within. The purpose of segmenting can vary greatly, but one common objective is to denote shifts in the topic of a text, where multiple boundary types can also be present (e.g., major ver- sus minor topic shifts). Human-competitive auto- matic segmentation methods can help a wide range of computational linguistic tasks which depend upon the identification of segment boundaries in text. To evaluate automatic segmentation methods, a method of comparing an automatic segmenter’s per- formance against the segmentations produced by hu- man judges (coders) is required. Current meth- ods of performing this comparison designate only one coder’s segmentation as a reference to com- pare against. A single “true” reference segmentation from a coder should not be trusted, given that inter- annotator agreement is often reported to be rather poor (Hearst, 1997, p. 54). Additionally, to en- sure that an automatic segmenter does not over-fit to the preference and bias of one particular coder, an automatic segmenter should be compared directly against multiple coders. The state of the art segmentation evaluation met- rics (Pk and WindowDiff) slide a window across a designated reference and hypothesis segmentation, and count the number of windows where the number of boundaries differ. Window-based methods suffer from a variety of problems, including: i) unequal penalization of error types; ii) an arbitrarily defined window size parameter (whose choice greatly af- fects outcomes); iii) lack of clear intuition; iv) in- applicability to multiply-coded corpora; and v) re- liance upon a “true” reference segmentation. In this paper, we propose a new method of comparing two segmentations, called segmentation similarity 1 (S), that: i) equally penalizes all er- ror types (unless explicitly configured otherwise); ii) appropriately responds to scenarios tested; iii) de- fines no arbitrary parameters; iv) is intuitive; and v) is adapted for use in a variety of popular inter- annotator agreement coefficients to handle multiply- coded corpora; and vi) does not rely upon a …

Content truncated to 500 words