An Alignment-based Approach to Text Segmentation Similarity Scoring (2022)

Abstract: Text segmentation is a natural language processing task with popular applications, such as topic segmentation, element discourse extraction, and sentence tokenization. Much work has been done to develop accurate segmentation similarity metrics, but even the most advanced metrics used today, B, and WindowDiff, exhibit incorrect behavior due to their evaluation of boundaries in isolation. In this paper, we present a new segment-alignment based approach to segmentation similarity scoring and a new similarity metric A. We show that A does not exhibit the erratic behavior of $ and WindowDiff, quantify the likelihood of B and WindowDiff misbehaving through simulation, and discuss the versatility of alignment-based approaches for segmentation similarity scoring. We make our implementation of A publicly available and encourage the community to explore more sophisticated approaches to text segmentation similarity scoring.

## introduction text segmentation is a natural language processing (nlp) task that consists of dividing a sequence of text elements into segments. let @xmath0, e 2 , e 3 ...e n be a sequence of text elements (e.g. words, sentences, paragraphs, etc...). a segmentation s of t is given by a binary string @xmath1. the ith character of q codifies the presence of a boundary (1) or lack thereof (0) between e i and e i+1 in s. s contains m -1 boundaries and partitions t into m segments 1 . 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), 1 this 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. 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 : h 1 agrees with s in 4 out of 5 positions (one missing boundary), while h 2 agrees with s in only 3 out of 5 positions (one missing and one "extra" boundary). yet it is easy to agree that h 2 is actually closer to s, as it has simply "shifted" the boundary in s one unit to the right. to address this, researchers have proposed a variety of similarity metrics that distinguish "soft" and "hard" errors (shifted versus missing/extra boundaries). however, existing metrics look at boundary errors in isolation; they do not consider the impact that errors have on segments around them. consider how hypothesis segmentations h 3 and h 4 compare to a reference segmentation r in figure 3 . both have a boundary that is shifted one pbp to the right, which results in an"extra" element in the segment to the left of the pbp and a missing element in the segment to the right. however, the resulting segment distortion is not the same. in h 3 , only 1/2 of the elements in the the first segment are correct, while 1/2 of the reference elements are missing from the second segment; in h 4 , the third segment has 4/5 correct elements, and the fourth segment has 1/4 missing elements. it is easy to argue then that h 4 is closer to r than h 3 , but current metrics are unable to distinguish between them. we propose a new similarity metric based on segment alignment, which scores segmentations based on how well their segments match, rather than their boundaries (section 3). we show that our metric aligns more closely with human intuition than existing metrics (section 4) and quantify the errors encountered by those metrics (section 5). code for our new metric and relevant materials are made publicly available at https://github.com/sierra98x/resources . ## existing metrics current segmentation similarity metrics fall into two categories: window-based metrics try to capture errors by sliding a window across the element sequence t and comparing the boundaries in both segmentations; in contrast, edit-based metrics try to find a sequence of boundary edit operations that would make both segmentations equal. ## an alignment-based approach to segmentation similarity scoring in section 1, figure 2, we presented an example that showcased the importance of weighing boundary differences in terms of the impact they have on their corresponding segments. none of the current metrics attempt to do this, and they can not be easily modified to do so. we propose to measure similarity between a pair of segmentations by comparing the segments defined in them. the intuition is straightforward: two segmentations are similar iff the segments defined by them are similar. inspired by alignments from machine translation and string comparison, our approach measures segmentation similarity by finding the maximum likelihood segment alignment and scoring its correctness. the concept of the most likely alignment is based on two key observations. first, it only makes sense to align overlapping segments. second, the overlap between two segments is a good indicator for their "closeness", which tells us if they should be aligned. thus, the maximum likelihood alignment (mla) is one where every segment is aligned to its closest other segment. consider the example alignment in figure 6 : h 2 has fuzzily merged the first two segments in h 1 into a single segment, which results in the third segment from h 1 having a slightly shifted boundary in h 2 . here, it does not make sense to align the third segment in h 1 with the first segment in h 2 ; even if they overlap, the third segment in h 1 overlaps mainly with the second segment in h 2 . the mla can be found greedily in o(m 1 + m 2 ) time, where m 1 and m 2 are the number of segments in h 1 and h 2 , respectively. we only need to find the closest segment for any given segment foot_3 . figure 7 shows pseudocode for generating the mla foot_4 . mla(h1,h2,fn: c): the mla explains the differences between a pair of segmentations in terms of boundaries: in figure 8 , missing/extra boundaries are indicated by the existence of segments with more than one aligned segment. the first segment in h 3 is aligned to two segments in h 4 because h 4 contains an extra boundary; similarly, the third segment in h 4 is aligned to two segments in h 3 because the third segment in h 4 is missing a boundary present in h 3 . furthermore, the existence of pairs of aligned segments with no alignments to any other segments are indicators of matches or transpositions, such as the last segments in h 3 and h 4 . once the mla has been generated, a function should be chosen to map the mla to a similarity score. a simple approach is to assign a weight to every alignment edge, using a function g, and normalize by the number of edges in the mla. this generic similarity score a is defined as: a variety of edge weighting functions can be used: clustering similarity functions such as the rand index, or set similarity metrics such as the overlap coefficient, the sørensen-dice coefficient, or the jaccard index. both symmetric and asymmetric weighting functions can be used, as the edges generated by the mla function are directed; we recommend the jaccard index, since it guarantees a symmetrical segmentation similarity score. further, the jaccard version of a can be easily modified to distinguish between "soft" and "hard" mistakes by penalizing edges with weights under some threshold t. the jaccard index, @xmath2, 1], between two sets s and t is defined as: the mla approach with similarity score function a compares favorably to windowdiff, b, and similar metrics in terms of error analysis, as the mla structure and edge weights provide information about segmentation differences in terms of both boundaries and segments. further, the separation between the mla algorithm and the similarity score function a makes our approach quite versatile, as the mla may instead be scored with a different, task-specific similarity scoring function. consider the reference segmentation r and candidate segmentations h 1 and h 2 in figure 9 : h 1 and h 2 are equidistant to r under a with jaccard (0.58), b, and windowdiff. however, for a task like topic segmentation, h 2 may be preferred, as it contains "meta" topics that consistently match two topics each in r, whereas h 1 contains two correct topics, but one really bad third topic, which is a mixture of four topics in r. conversely, for a task like sentence segmentation, h 1 may be preferred, as it correctly identifies two sentences, where h 2 contains only incorrect sentences. the mla could be used in conjunction with a similarity scoring function that imposes exponentially increasing penalties on segments with many alignments to favor h 2 , while a scoring function that considers only the highest weighted edge for any given segment would favor h 1 . finally, as we will show in the following section, a straightforward implementation of a, using the intersect ratio i as the closeness function and the jaccard index j as the edge weight function, behaves favorably compared to current metrics in a key set of examples. ## similarity metric behavior in this section, we outline three erratic behaviors from b and windowdiff, and compare these metrics against a in a series of example segmentations. ## error quantification we quantify the likelihood of windowdiff and b behaving erroneously through simulation foot_5 . for the three main error types described in section 4, we first instantiate every possible reference segmentation r for sequences of length @xmath3. we then try to find two alternate segmentations h 1 and h 2 that b or windowdiff score as equally similar to r, but in fact are not. finally, for both b and windowdiff, we present the ratio of reference segmentations r of length n for which such errorproducing pairs h 1 and h 2 exist. we also include a in our simulations and verify that it does not behave erroneously in any of the tested scenarios, so it is not included in our discussion. to simplify our analysis, we use the lampriercorrected version of windowdiff @xcite , which pads the beginning and end of the sequence with k -1 elements. the number of errors produced by this version is a lower bound on the number of errors produced by the original win-dowdiff, which penalizes boundary mismatches at the edges less than those at the center. ## limitations while we have seen that a performs favorably when compared to b and windowdiff, further investigation may be warranted on the general mla approach. first, the space of potential alignments for a given pair of segmentations can be quite large, and while a simple greedy intersection ratio approach generates sensible alignments, edge cases may exhibit undesirable behavior. consider figure 16 : h 0 deletes a boundary from r, while h 1 and h 2 transpose it different distances. however, a gives h 2 a worse score than h 0 ; this behavior is explained by the mla between r and h 2 containing a diagonal alignment between the first segment in h 2 and the second segment in r, due to the first segment in r being very small -so small that transposing its boundary by two units is considered worse than deleting it. the intersect ratio closeness function in a uses segment size to distinguish "soft" and "hard" transpositions; as we saw in figure 12 , when the segments are longer, a will match the left and right segments of a twounit transposition with the original segments in r, resulting in a similarity score greater than h 0 . however, specific applications may lean towards favoring "soft" transpositions over deletions regardless of segment size, which would require a) a different segment-to-segment closeness function c, or b) maximizing some global mla function, such as maximum spanning tree. second, in figure 9 , we presented a reference segmentation r and two different candidate segmentations h 1 and h 2 that are scored equally by a, b, and wd. here, the fact that a can not distinguish between them is not due to the mla, as there is only one possible alignment between each candidate and r. thus, it may be of interest to develop more sophisticated mla scoring functions, in order to distinguish between h 1 and h 2 . ## conclusion in this paper, we present a new alignment-based approach to text segmentation similarity scoring and present a new similarity metric a. we show that, unlike a, the most advanced segmentation similarity metrics, b and windowdiff, behave erratically in three key scenarios. we discuss the versatility of alignment-based approaches when paired with different alignment and scoring functions, and show that a, b, and windowdiff exhibit intricate behaviors that should be explored in the future. we make our implementation of a publicly available foot_6 in hope that it encourages the nlp community to explore more sophisticated approaches to text segmentation similarity scoring.