Neural String Edit Distance (2022)

Abstract: We propose the neural string edit distance model for string-pair matching and string transduction based on learnable string edit distance. We modify the original expectation-maximization learned edit distance algorithm into a differentiable loss function, allowing us to integrate it into a neural network providing a contextual representation of the input. We evaluate on cognate detection, transliteration, and grapheme-to-phoneme conversion, and show that we can trade off between performance and interpretability in a single framework. Using contextual representations, which are difficult to interpret, we match the performance of state-of-the-art string-pair matching models. Using static embeddings and a slightly different loss function, we force interpretability, at the expense of an accuracy drop.

## introduction state-of-the-art models for string-pair classification and string transduction employ powerful neural architectures that lack interpretability. for example, bert @xcite compares all input symbols with each other via 96 attention heads, whose functions are difficult to interpret. moreover, attention itself can be hard to interpret (jain and wallace, 2019; @xcite . in many tasks, such as in transliteration, a relation between two strings can be interpreted more simply as edit operations @xcite . the edit operations define the alignment between the strings and provide an interpretation of how one string is transcribed into another. learnable edit distance @xcite allows learning the weights of edit operations from data using the expectation-maximization (em) algorithm. unlike post-hoc analysis of black-box models, which depends on human qualitative judgment @xcite @xcite , the restricted set of edit operations allows direct figure 1 : an example of applying the dynamic programming algorithm used to compute the edit probability score. it gradually fills the table of probabilities that prefixes of the word "equal" transcribe into prefixes of phoneme sequence "iy k w ah l". the probability (gray circles) depends on the probabilities of the prefixes and probabilities of plausible edit operations: insert (blue arrows), substitute (green arrows) and delete (red arrows). we reformulate the em training used to train learnable edit distance as a differentiable loss function that can be used in a neural network. we propose two variants of models based on neural string edit distance: a bidirectional model for string-pair matching and a conditional model for string transduction. we evaluate on cognate detection, transliteration, and grapheme-to-phoneme (g2p) conver-sion. the model jointly learns to perform the task and to generate a latent sequence of edit operations explaining the output. our approach can flexibly trade off performance and intepretability by using input representations with various degrees of contextualization and outperforms methods that offer a similar degree of interpretability @xcite . ## learnable edit distance edit distance @xcite formalizes transcription of a string @xmath0, . . . , s n ) of n symbols from alphabet s into a string @xmath1, . . . , t m ) of m symbols from alphabet t as a sequence of operations: delete, insert and substitute, which have different costs. ristad and yianilos (1998) reformulated operations as random events drawn from a distribution of all possible operations: deleting any @xmath2, inserting any @xmath3, and substituting any pair of symbols from s × t . the probability p(s, t) = α n,m of t being edited from s can be expressed recursively: this can be computed using the dynamic programming algorithm of @xcite , which also computes values of α i,j for all prefixes s :i and t :j . the operation probabilities only depend on the individual pairs of symbols at positions i, j, so the same dynamic programming algorithm is used for computing the suffix-pair transcription probabilities β i,j (the backward probabilities). with a training corpus of pairs of matching strings, the operation probabilities can be estimated using the em algorithm. in the expectation step, expected counts of all edit operations are estimated for the current parameters using the training data. each pair of symbols s i and t j contribute to the expected counts of the operations: ## neural string edit distance model in our model, we replace the discrete table of operation probabilities with a probability estimation based on a continuous representation of the input, which brings in the challenge of changing the em training into a differentiable loss function that can be back-propagated into the representation. computation of the transcription probability is shown in figure 1 . we use the same dynamic programming algorithm (equation 1 and algorithm 2 in appendix a) that gradually fills a table of probabilities row by row. the input symbols are represented by learned, possibly contextual embeddings (yellow and blue boxes in figure 1 ) which are used to compute a representation of symbol pairs with a small feed-forward network. the symbol pair representation is used to estimate the probabilities of insert, delete and substitute operations (blue, red and green arrows in figure 1 ). formally, we embed the source sequence s of length n into a matrix h @xmath4. we represent the symbol-pair contexts as a function of the respective symbol representations (small gray rectangles in figure 1 ) as a function of repspective symbol representation c i,@xmath5, h t j ) depending on the task. the logits (i.e., the probability scores before normalization) for the edit operations are obtained by concatenation of the following vectors (corresponds to red, green and blue arrows in figure 1 ): the probabilities p i,j del , p i,j ins and p i,j subs are obtained by taking the respective values from the distribution corresponding to the logits. foot_0 note that p i,j only depends on (possibly contextual) input embeddings h s i , h s i-1 , h t j , and h t j-1 , but not on the derivation of prefix t :j from s :i . ## experiments we evaluate the string-pair matching model on cognate detection, and the string transduction model on arabic-to-english transliteration and english grapheme-to-phoneme conversion. in all tasks, we study four ways of representing the input symbols with different degrees of contextualization. the interpretable context-free (unigram) encoder uses symbol embeddings summed with learned position embeddings. we use a 1-d convolutional neural network (cnn) for locally contexualized representation where hidden states correspond to consecutive input n-grams. we use bidirectional recurrent networks (rnns) and transformers @xcite for fully contextualized input representations. architectural details and hyperparameters are listed in appendix c. all hyperparameters are set manually based on preliminary experiments. further hyperparameter tuning can likely lead to better accuracy of both baselines and our model. however, preliminary experiments showed that increasing the model size only has a small effect on model accuracy. we run every experiment 5 times and report the mean performance and the standard deviation to control for training stability. the source code for the experiments is available at https://github.com/jlibovicky/ neural-string-edit-distance . cognate detection. cognate detection is the task of detecting if words in different languages have the same origin. we experiment with austro-asiatic languages @xcite and indo-european languages @xcite normalized into the international phonetic alphabet as provided by @xcite . 2 for indo-european languages, we have 9,855 words (after excluding singleton-class words) from 43 languages forming 2,158 cognate classes. for austro-asiatic languages, the dataset contains 11,828 words of 59 languages, forming only 98 cognate classes without singletons. we generate classification pairs from these datasets by randomly sampling 10 negative examples for each true cognate pair. we use 20k pairs for validation and testing, leaving 1.5m training examples for indo-european and 80m for austro-asiatic languages. many cognate detection methods are unsupervised and are evaluated by comparison of a clustering from the method with true cognate classes. we train a supervised classifier, so we use f 1 -score on our splits of the dataset. because the input and the output are from the same alphabet, we share the parameters of the encoders of the source and target sequences. as a baseline we use the original statistical learn-able edit distance @xcite . the well-performing black-box model used as another baseline for comparison with our model is a transformer processing a concatenation of the two input strings. similar to bert @xcite , we use the representation of the first technical symbol as an input to a linear classifier. we also compare our results with the stance model @xcite , a neural model utilizing optimaltransport-based alignment over input text representation which makes similar claims about interpretability as we do. similar to our model, we experiment with various degrees of representation contextualization. transliteration and g2p conversion. for string transduction, we test our model on two tasks: arabic-to-english transliteration @xcite foot_2 and english g2p conversion using the cmudict dataset @xcite foot_3 . the arabic-to-english transliteration dataset consists of 12,877 pairs for training, 1,431 for validation, and 1,590 for testing. the source-side alphabet uses 47 different symbols; the target side uses 39. the cmudict dataset contains 108,952 training, 5,447 validation, and 12,855 test examples, 10,999 unique. the dataset uses 27 different graphemes and 39 phonemes. we evaluate the output strings using character error rate (cer): the standard edit distance between the generated hypotheses and the ground truth string divided by the ground-truth string length; and word error rate (wer): the proportion of words that were transcribed incorrectly. the cmudict dataset contains multiple transcriptions unlike the string-matching task, the future target symbols are unknown. therefore, when using the contextual representations, we encode the target string using a single-direction rnn and using a masked transformer, respectively. to evaluate our model under low-resource conditions, we conduct two sets of additional experiments with the transliteration of arabic. we compare our unigram and rnn-based models with the rnn-based s2s model trained on smaller subsets of training data (6k, 3k, 1.5k, 750, 360, 180, and 60 training examples) and different embedding and hidden state size (8, 16, . . . , 512). for the g2p task, where the source and target symbols can be approximately aligned, we further quantitatively assess the model's interpretability by measuring how well it captures alignment between the source and target string. we consider the substitutions in the viterbi decoding to be aligned symbols. we compare this alignment with statistical word alignment and report the f 1 score. we obtain the source-target strings alignment using efmaral @xcite , a state-ofthe-art word aligner, by running the aligner on the entire cmudict dataset. we use grow-diagonal for alignment symmetrization. the baseline models are rnn-based @xcite and transformer-based @xcite 2 . the interpretability loss only has a negligible (although mostly slightly negative) influence on the accuracy, within the variance of training runs. the ablation study on loss functions ( the transliteration of arabic appears to be a simpler problem than g2p conversion. the performance matches s2s, has fast training times, and there is a smaller gap between the error rates of the context-free and contextualized models. the training time of our transduction models is 2-3× higher than with the baseline s2s models because the baseline models use builtin pytorch functions, whereas our model is implemented using loops using torchscript 5 (15% faster than plain python). the performance under low data conditions and with small model capacity is in figure 3 . models that use static symbol embeddings as the input perform worse than the black-box s2s models in both tasks. local contextualization with cnn improves the performance over static symbol embeddings. using the fully contextualized input representation narrows the performance gap between s2s models and neural string edit distance models at the expense of decreased interpretability because all input states can, in theory, contain information about the entire input sequence. the ability to preserve source-target alignment is highest when the input is represented by embeddings only. rnn models not only have the best accuracy, but also 5 https://pytorch.org/docs/stable/jit.html capture quite well the source-target alignment. we hypothesize that rnns work well because of their inductive bias towards sequence processing, which might be hard to learn from position embeddings given the task dataset sizes. including the interpretability loss usually slightly improves the accuracy and improves the alignment between the source and target strings. it manifests both qualitatively ( compared to s2s models, beam search decoding leads to much higher accuracy gains, with beam search 5 reaching around 2× error reduction compared to greedy decoding. for all input representations except the static embeddings, length normalization does not improve decoding. unlike machine translation models, accuracy doesn't degrade with increasing beam size. see figure 4 in appendix. the ablation study on loss functions ( ## related work weighted finite-state transducers. @xcite use a weighted-finite state transducer (wfst) with neural scoring function to model sequence transduction. as in our model, they back-propagate the error via a dynamic program. our model is stronger because, in the wfst, the output symbol generation only depends on the contextualized source symbol embedding, disregarding the string generated so far. @xcite extend the model by including contextualized target string representation and edit operation history. this makes their model more powerful than ours, but the loss function cannot be exactly computed by dynamic programming and graphemes phonemes edit operations neural sequence matching. several neural sequence-matching methods utilize a scoring function similar to symbol-pair representation. @xcite propose integrating alignment between two sequences into a loss function that eventually leads to finding alignment between the sequences. the stance model @xcite , which we compare results with, first computes the alignment as an optimal transfer problem between the source and target representation. in the second step, they assign a score using a convolutional neural network applied to a soft-alignment matrix. we showed that our model reaches better accuracy with the same input representation. similar to our model, these approaches provide interpretability via alignment. they allow many-to-many alignments, but cannot enforce a monotonic sequence of operations unlike wfsts and our model. learnable edit distance. @xcite used trainable edit distance in combination with crfs for string matching. recently, riley and gildea (2020) integrated the statistical learnable edit distance within a pipeline for unsupervised bilingual lexicon induction. as far as we know, our work is the first using neural networks directly in dynamic programming for edit distance. edit distance in deep learning. lasertagger @xcite and editnts @xcite formulate sequence generation as tagging of the source text with edit operations. they use standard edit distance to pre-process the data (so, unlike our model cannot work with different alphabets) and then learn to predict the edit operations. levenshtein transformer @xcite is a partially non-autoregressive s2s model generating the output iteratively via insert and delete operations. it delivers a good trade-off of decoding speed and translation quality, but is not interpretable. ## conclusions we introduced neural string edit distance, a neural model of string transduction based on string edit distance. our novel formulation of neural string edit distance critically depends on a differentiable loss. when used with context-free representations, it offers a direct interpretability via insert, delete and substitute operations, unlike widely used s2s models. using input representations with differing amounts of contextualization, we can trade off interpretability for better performance. our experimental results on cognate detection, arabic-to-english transliteration and grapheme-to-phoneme conversion show that with contextualized input representations, the proposed model is able to match the performance of standard black-box models. we hope that our approach will help motivate more work on this type of interpretable model and that our framework will be useful in such future work. kaisheng yao and geoffrey zweig. 2015. sequenceto-sequence neural net models for grapheme-tophoneme conversion. in interspeech 2015, 16th annual conference of the international speech communication association, dresden, germany, september 6-10, 2015, pages 3330-3334. isca. sevinj yolchuyeva, géza németh, and bálint gyires-tóth. 2019. transformer based grapheme-tophoneme conversion. in interspeech 2019, 20th annual conference of the international speech communication association, graz, austria, 15-19 september 2019, pages 2095-2099. isca. lei yu, jan buys, and phil blunsom. 2016. online segment to segment neural transduction. in proceedings of the 2016 conference on empirical methods in natural language processing, pages 1307-1316, austin, texas. association for computational linguistics.