Optimal Transport-based Alignment of Learned Character Representations for String Similarity

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5907–5917 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 5907 Optimal Transport-based Alignment of Learned Character Representations for String Similarity Derek Tam1, Nicholas Monath1, Ari Kobren1, Aaron Traylor2, Rajarshi Das1, Andrew McCallum1 1College of Information and Computer Sciences, University of Massachusetts Amherst 2Department of Computer Science, Brown University {dptam,nmonath,akobren,rajarshi,mccallum}@cs.umass.edu aaron_traylor@brown.edu Abstract String similarity models are vital for record linkage, entity resolution, and search. In this work, we present STANCE–a learned model for computing the similarity of two strings. Our approach encodes the characters of each string, aligns the encodings using Sinkhorn It- eration (alignment is posed as an instance of optimal transport) and scores the alignment with a convolutional neural network. We eval- uate STANCE’s ability to detect whether two strings can refer to the same entity–a task we term alias detection. We construct five new alias detection datasets (and make them pub- licly available). We show that STANCE (or one of its variants) outperforms both state-of- the-art and classic, parameter-free similarity models on four of the five datasets. We also demonstrate STANCE’s ability to improve downstream tasks by applying it to an instance of cross-document coreference and show that it leads to a 2.8 point improvement in B3 F1 over the previous state-of-the-art approach. 1 Introduction String similarity models are crucial in record link- age, data integration, search and entity resolu- tion systems, in which they are used to deter- mine whether two strings refer to the same en- tity (Bilenko and Mooney, 2003; McCallum et al., 2005; Li et al., 2015). In the context of these systems, measuring string similarity is compli- cated by a variety of factors including: the use of nicknames (e.g., Bill Clinton instead of William Clinton), token permutations (e.g., US Navy and Naval Forces of the US) and noise, among others. Many state-of-the-art sys- tems employ either classic similarity models, such as Levenshtein, longest common subsequence, and Jaro-Winkler, or learned models for string similar- ity (Levin et al., 2012; Li et al., 2015; Ventura et al., 2015; Kim et al., 2016a; Gan et al., 2017). While classic and learned approaches can be ef- fective, they both have a number of shortcomings. First, the classic approaches have few parameters making them inflexible and unlikely to succeed across languages or across domains with unique characteristics (e.g. company names, music album titles, etc.) (Needleman and Wunsch, 1970; Smith and Waterman, 1981; Winkler, 1999; Gionis et al., 1999; Bergroth et al., 2000; Cohen et al., 2003). Classic models also assume that each edit has equal cost, which is unrealistic. For example, consider the names Chun How and Chun Hao–which can refer to the same entity–and the names John A. Smith and John B. Smith, which can- not. Even though the first pair differ by 2 edits and the second pair by 1, transforming ow to ao in the first pair should cost less than transforming A to B in the …

Content truncated to 500 words