An Alignment-based Approach to Text Segmentation Similarity Scoring

Proceedings of the 26th Conference on Computational Natural Language Learning (CoNLL), pages 374 - 383 December 7-8, 2022 ©2022 Association for Computational Linguistics An Alignment-based Approach to Text Segmentation Similarity Scoring Gerardo Ocampo Diaz and Jessica Ouyang Department of Computer Science University of Texas at Dallas Richardson, TX 75083 {godiaz,jessica.ouyang}@utdallas.edu Abstract Text segmentation is a natural language pro- cessing task with popular applications, such as topic segmentation, element discourse extrac- tion, and sentence tokenization. Much work has been done to develop accurate segmenta- tion similarity metrics, but even the most ad- vanced metrics used today, B, and WindowDiff, exhibit incorrect behavior due to their evalua- tion of boundaries in isolation. In this paper, we present a new segment-alignment based ap- proach to segmentation similarity scoring and a new similarity metric A. We show that A does not exhibit the erratic behavior of B and WindowDiff, quantify the likelihood of B and WindowDiff misbehaving through simulation, and discuss the versatility of alignment-based approaches for segmentation similarity scor- ing. We make our implementation of A pub- licly available and encourage the community to explore more sophisticated approaches to text segmentation similarity scoring. 1 Introduction Text segmentation is a natural language processing (NLP) task that consists of dividing a sequence of text elements into segments. Let T = e1, e2, e3...en be a sequence of text el- ements (e.g. words, sentences, paragraphs, etc...). A segmentation S of T is given by a binary string Q = [0|1]n−1 that encodes boundaries between the elements of T. The ith character of Q codi- fies the presence of a boundary (1) or lack thereof (0) between ei and ei+1 in S. S contains m − 1 boundaries and partitions T into m segments1. Measuring similarity between segmentations is not simple. The most straightforward approach is to frame a segmentation as a series of decisions made at every potential boundary position (PBP), 1This definition corresponds to single-type segmentation. A multi-type version also exists where different boundary types are considered, enabling the encoding of different types of segments and even hierarchical relations between them. S Dogs are cute Very fast cars 0 0 1 0 0 Figure 1: Example segmentation with Q = 00100. which exist between every pair of elements in T, and to calculate the average PBP agreement, but this does not match human intuition well. Consider how S in Figure 1 compares with h1 and h2 in Figure 2: h1 agrees with S in 4 out of 5 positions (one missing boundary), while h2 agrees with S in only 3 out of 5 positions (one missing and one “extra" boundary). Yet it is easy to agree that h2 is actually closer to S, as it has simply “shifted" the boundary in S one unit to the right. h1 Dogs are cute Very fast cars h2 Dogs are cute Very fast cars Figure 2: Alternate segmentations to S from Figure 1. To address this, researchers have proposed a vari- ety of similarity metrics that distinguish “soft" …

Content truncated to 500 words