D eezy M atch: A Flexible Deep Learning Approach to Fuzzy String Matching (2020)

Abstract: We present DeezyMatch, a free, open-source software library written in Python for fuzzy string matching and candidate ranking. Its pair classifier supports various deep neural network architectures for training new classifiers and for fine-tuning a pretrained model, which paves the way for transfer learning in fuzzy string matching. This approach is especially useful where only limited training examples are available. The learned DeezyMatch models can be used to generate rich vector representations from string inputs. The candidate ranker component in DeezyMatch uses these vector representations to find, for a given query, the best matching candidates in a knowledge base. It uses an adaptive searching algorithm applicable to large knowledge bases and query sets. We describe DeezyMatch’s functionality, design and implementation, accompanied by a use case in toponym matching and candidate ranking in realistic noisy datasets.

## introduction string matching is an integral component of many natural language processing (nlp) pipelines. one such application is in entity linking (el), the task of mapping a mention (i.e., a string) to its corresponding entry in a knowledge base (kb). most el systems currently rely on a lookup table @xcite @xcite foot_0 or shallow string similarity approaches (e.g., based on n-gram overlaps as in @xcite ; @xcite , or super-string matching, as in @xcite ) to narrow the entries of a kb down to a set of potential candidates the mention may refer to (i.e., aliases). while these choices allow fast run-time, they generally rely on the assumption that all surface forms of each entity are present as aliases in the kb. the performances of these systems degrade when dealing with domain-specific vocabulary @xcite , local variations @xcite , historical materials @xcite and, in general, challenges that emerge when performing el on non-standard documents. 2 this subtask of el, often referred to as candidate ranking (and selection), is mostly ignored when designing downstream systems, even though its significant impact on downstream nlp pipelines has been shown previously @xcite . in this paper, we present deezymatch, a new deep learning approach that strives to address advanced string matching and candidate ranking in a more comprehensive and integrated manner than existing tools. deezymatch is a free, open-source community software written in python. it uses py-torch @xcite to implement various state-of-the-art neural network architectures, and it has been tested on both cpu and gpu. one of the main features of deezymatch is its modular design and flexibility. we describe deezymatch's functionalities, design choices and technical implementation. we compare its performance in relation to other approaches on several realistic string matching scenarios, covering different languages, alphabets, and domains, and we evaluate the quality of the candidate ranker in a real-case setting. thanks to its easy-to-use interface, deezymatch can be seamlessly integrated into existing el systems. this allows deezymatch to be adopted outof these parameters can be frozen, that is, they will not be changed during fine-tuning. various hyperparameters including the architecture of the neural network and tokenization can be changed by the user (see text). in candidate ranker, for each query and candidate pair, learned vector representations are first generated using a deezymatch model. these vectors are then used to rank candidates according to different metrics (e.g., l 2 -norm distance, cosine similarity and prediction scores). the steps of candidate ranker are depicted by dashed lines in the figure . side the nlp community, especially in digital humanities, where it could play a major role in addressing known issues concerning the el systems and their adaptability to the non-standard nature of the datasets typically used in this field @xcite . deezymatch is released under mit license. it is available via pypi, foot_2 and its source codes are on github. 4 we provide extensive documentation, including examples in jupyter notebooks, to enable the smooth adoption of all its components. ## description of the system fig. 1 shows the two main components of deezy-match: pair classifier and candidate ranker. together they allow the training or fine-tuning of a query-candidate classifier and finding best matching candidates to a query from a kb. ## comparison with existing systems the majority of readily available el tools rely on a lookup table or on shallow string similarity approaches to select an initial set of candidates, followed by a disambiguation step. tagme! (ferragina and scaiella, 2010), for instance, a well established el baseline, performs candidate selection through perfect matches between mentions and a list of alias surface forms derived from wikipedia, as also discussed by @xcite . alternatives to perfect matches involve the adoption of edit-distance techniques, such as levensthein distance (see, for example, its adoption in @xcite ). while there are many implementations of such approaches readily available, these methods suffer from poor scalability (i.e., time complexity, as we discuss in our experiments in section 3.1.1). due to this, some el pipelines (e.g., @xcite ) have incorporated such techniques only when no exact matching entry can be retrieved. more recently, researchers have developed deep learning solutions for candidate selection. @xcite framed it as a distance learning task with a noise detector in their el system, in which the linkage between mentions that are not necessarily in the kb is learned from lists of positive candidates (the top matching candidates) and negative candidates (randomly sampled from the kb). @xcite have recently presented stance, a model for computing the similarity of two strings by encoding the characters of each of them, aligning the encodings using sinkhorn iteration, and scoring the alignment with a convolutional neural network. the associated repository foot_4 offers codes for reproducing the experiments in the paper. unfortunately, their implementation is not directly comparable with deezymatch, as it was not designed to be integrated directly into an el pipeline. the work closest to ours, which has directly inspired our initial development, is by @xcite . the authors presented a recurrent neural network architecture to encode pairs of toponyms followed by a multi-layer perceptron to determine if they are matching. the authors accompanied their work with a repository to reproduce the results presented in the paper. 6 however, the user has little control over the model architecture, including its hyperparameters and processing steps. moreover, the authors do not offer a method for either loading a trained model and applying it to new data or for candidate ranking. building upon this previous work, we present an easy to use library that (a) relies on deep neural networks for fuzzy string matching and candidate ranking beyond surface similarities; (b) is significantly faster than edit-distance approaches; and (c) can be seamlessly integrated into existing el pipelines with a single python command. ## conclusions we presented deezymatch, a new user-friendly python library for fuzzy string matching and candidate ranking, based on deep neural network architectures. deezymatch can be seamlessly integrated into existing el pipelines. its flexibility allows the user to easily fine-tune a pretrained model or to adapt the model architecture to the specificity of a real-case scenario. we compared its design, implementation and functionalities with other approaches. in the future, we plan to support self-attention and state-of-the-art pretrained character-based models, integrate learning to rank functionalities in the candidate selection process and to release a zoo of models trained on large datasets which can be fine-tuned further in other downstream nlp tasks. deezymatch was designed with flexibility in mind, and we encourage the community to further extend its implementation for addressing other related tasks, such as record linkage, transliteration and data integration. @xcite . additionally, due to this, we skip toponyms if no correct match has been found by all the tested methods. 11 here, we do not take into account the time spent on training the model and generating the candidate vectors, as this is done offline only once and can be reused for all following candidate ranking tasks that use the same model and gazetteer. training a model on a dataset with ≈670k pairs (including preprocessing) takes 28m on gpu and 54m on cpu, while generating and combining candidate vectors takes 39m on gpu and 204m on cpu.