Neural Embeddings for Nearest Neighbor Search Under Edit Distance
Authors: Xiyuan Zhang
Yang Yuan
Piotr Indyk
Venue:  (2020)
Keywords: Embedding
Edit Distance
Nearest Neighbor Search
Learning-Augmented Algorithm

Abstract: The edit distance between two sequences is an important metric with many applications. The drawback, however, is the high computational cost of many basic problems involving this notion, such as the nearest neighbor search. A natural approach to overcoming this issue is to embed the sequences into a vector space such that the geometric distance in the target space approximates the edit distance in the original space. However, the known edit distance embedding algorithms, such as Chakraborty et al.(2016), construct embeddings that are data-independent, i.e., do not exploit any structure of embedded sets of strings. In this paper we propose an alternative approach, which learns the embedding function according to the data distribution. Our experiments show that the new algorithm has much better empirical performance than prior data-independent methods. 

Under review as a conference paper at ICLR 2020
NEURAL EMBEDDINGS FOR NEAREST NEIGHBOR SEARCH UNDER EDIT DISTANCE
A Anonymous authors Paper under double-blind review
A ABSTRACT
The edit distance between two sequences is an important metric with many applications. The drawback, however, is the high computational cost of many basic problems involving this notion, such as the nearest neighbor search. A natural approach to overcoming this issue is to embed the se- quences into a vector space such that the geometric distance in the tar- get space approximates the edit distance in the original space. However, the known edit distance embedding algorithms, such as Chakraborty el al.) (2016), construct embeddings that are data-independent, i.e., not ex- ploit any structure of embedded sets of strings. In this paper we propose an alternative approach, which learns the embedding function according to the data distribution. Our experiments show that the new algorithm has much better empirical performance than prior lata-independen methods.
INTRODUCTION
The edit distance is popular metric for computing the dissimilarity between two strings. Given strings and the edit distance dr(x,)) y) between them is equal to the minimum number of character insertions, deletions and substitutions needed to transform æ into y. The metric and its many variants have been defined and studied since the 1960s (Levenshtein 1966 Wagner and Fischer 1974). It has found many applications in computational biology (to measure the similarity between DNA/RNA sequences), natural language processing, information theory and other fields.
From the algorithmic perspective, the main drawback of edit distance is its computational complexity. The best known algorithm for computing the distance between two strings of length n takes time that is roughly quadratic in (Masek and Paterson 1980); there is also evidence that this runtime is essentially optimal (Backurs and Indyk 2015) Furthermore, many applications require finding the closest string in large collection of (say) N strings. Thus, even if we could estimate the edit distance in time O(n), computing the distances to all strings in the collection would take O(Nn) time, which is infeasible for large data sets.
A natural approach to resolving both issues relies on low-distortion embeddings. The idea. is to construct mapping that maps strings into d-dimensional space Rd, such that the edit distance dæ(2; (2, y) is approximated by the distance [[[(x) f(y))l between the images of the strings, up to some factor D called distortion. If the mapping f can be evaluated elficiently, this immediately implies an efficient way to compute the edit distance. Further- more, embedding strings into space equipped with norm || makes it possible to use nearest neighbor search algorithms designed for that norm. For many normed spaces, e.g. Minkowski norms Ad many efficient. approximate nearest neighbor search algorithms are available. This dual goal has motivated long line of rescarch focused on designing efficient. low-distortion embeddings of variants of edit distance into normed spaces (Muthukrishnan
and Sahinalp 2000; [Commode et al.] 2001
Ostrovsky and Rabani 2005) [atu et al. 20066] Chakraborty et al. 2016). The method given in
Jowhari 2012: Andoni and Onak 2012
the last paper (Chakraborty et al. 2016) was shown to yield good results in practice, in the
context of large scale similarity joins, 1.e., identifying all pairs of similar sequences (Zhang
and Zhang 2017)

---

Under review as a conference paper at ICLR 2020
Positive
CCTGCCGATGAGCATTTTTGGO
MXXAOOOOOODO CCCTGCCGATTAAGEATTTTTCCG
Embedding Space
Anchor
Negative
TATICCATATTOCCTCTAGGAA
Triplet loss for embedding DNA sequence imputs. Given anchor point A, a positive point P that is close to A in terms of edit distance, and negative point N that is not close to A. We hope our embedding function f satisfies f(A) is closer to f(P) than f(N) in lp-
Figure I:
A weakness of the aforementioned algorithms is that they are data-independent,, ie., they do not exploit any structure of embedded sets of strings. In contrast, over the last decade, a large body of research on "learning to hash" showed that data- data-dependent methods often yield (binary) embeddings with a significantly lower distortion than their inntedindeeendent counterparts (Wang et 2018). Such methods, however, are lypically tailored to obtaining binary representations of vectors that already live in geometric (typically Hilbert) space. It is thus natural to investigate whether similar benefits of data- data-dependent methods can be obtained for edit distance embeddings as well.
In this paper investigate whether the "learning to hash" approach can yield lower dis- tortion embeddings than those obtained using data-independent methods. Since our goal is to obtain distance-preserving mappings of sequences, as a model implementing those mappings. Specifically, we leverage a two-layer GRU net- work, depicted in Figure 2 and described in more details in Section The network inputs a sequence of characters (e-g., A, G, or C for DNA sequences), and outputs a vector of symbols, such that the distance between the vectors approximates the edit distance between the original sequences.
Recurrent Neural Networks
The standard loss function for optimizing the network is the triplet loss (see Figure D which has two problems in our scenario. The first problem is distance scaling: triplet loss only controls the relative distance ordering among data points after embedding, rather than the absolute embedding distance between any two data points. This prevents us from getting accurate edit distance estimation from the embedding. To alleviate this issue, we designed warm-start phase (Phase 1) before optimizing triplet loss (Phase 2), which initializes the embedding so that the discrepancy between the original edit distance and the embedding distance is minimized. The second problem is worst case performance of our model. Due to the nature of learning, the network we learned fits the training data better, and may not do well on unseen hard examples. To alleviate this issue, we append back up phase (Phase 3), which deals with hard cases.
We emphasize that all the three phases are optimizing the same network. We run Adam algorithm for each phase until convergence, and then use its final state as the initial state for the next phase. Although in principle one may use a single phase with combination of different loss functions to train our model, this requires additional hyperparameter adjust- ment for the combining ratios. Our current three phase training does not need additional hyperparameters, and therefore can casily fit different scenarios.
The Phase 3 design is non-trivial. Our starting observation is that Recurrent Neu- ral Networks that we employ are not "compatible" with the data-indepnndent mappings of Chakraborty et al. (2016) (which we call CGK from now on). This is because CGK can generate different number of copics for every input character, which is a discrete decision that hard to be learned by neural networks. We show, however, that this "extra power" of the algorithm is not necessary. In particular, we introduce a "truncated" version of the CGK algorithm (referred to as CGK'), that outputs only 1 or 2 symbols per round. We then show that CGK' has the same guarantees as the original CGK algorithm. Based on this observation, we design our Phase to be an optimized version of CGK*. Specifically, since each round there will be either or symbols in CGK', can directly compare the
2

---

Under review as a conference paper at ICLR 2020
two cases and use the difference approximation to the gradients to train our model. Em- pirically, Phase does not affect the recall on ordinary datasets much, but greatly improves performance hard instances.
To evaluate the embeddings, we employ them for nearest neighbor search in a collection of sequences, and compare their performance to CGK. As in Zhang and Zhang (2017) we use three data sets: Gen50ks (containing soquenees from the human genome project), UniRef (protein sequence dataset from the UniProt project) and Tree (containing textual information from Medline, an online medical information database). After learning the embeddings, we generate a set of queries, and for each query we identify sequences the data set (called condidates) that are closest to the query in the embedded space. We then measure "top-K recall", i.e., the fraction of the actual top K nearest neighbors (computed using the exact edit distance) returned as one of the C candidates. Our results demonstrate that, over a wide range of parameters higher recalls than the algorithm of CGK, often by factor of 3 more. Similarly, our method often obtains identical recall to that of CGK while using an order magnitude fewer candidates. This means that in a typical ncarest ncighbor search "filtering" pipcline, where the candidates are quickly identified in the embedded space and then the exact edit distance is computed between the candidates and queries to identify the final answers, our method reduces the number of exact edit, distance computations by up to one order of magnitude. Moreover, our learned embedding also has much more organized structure than CGK, as shown in Appendix A.4
and C, our learned embedding consistently achieves
2
RELATED WORK
2.1 EDrr DISTANCE COMPUTING
Exact and approximate algorithms for edit distance computation have been broadly studied, see Navarro (2001) for overview. For exact algorithms, Wagner and Fischer (1974) gave J-time algorithm using dynamic programming. This was later improved to O( ( log n)
by Masek and Paterson (1880). Faster approximation algorithms were studied as well, see
e.g., Landau et al. (1988 F Batu et al. (2003); Bar- Yossef et al. (2004); Batu et al. (2006); Andoni et al. (2010); ; Andoni and Onak (2012). The current state of the art consists of
near-linear algorithm of Andoni et al. (2010) guarantecing (log n) aap-aappoxiitatin (with a trade-off between the running time and the exponent c), and a constant factor approximation
2 algorithm of Chakraborty et al. (2018). To the best of our knowledge, noither algorithm has been implemented.
2.2 EDIT DISTANCE EMBEDDING
As mentioned in the introduction, there has been a long line of rescarch focused on designing embeddings of various variants of the edit distance into geometric space. For the edit distance as defined in the introduction, the best known algorithu is due to Ostrovsky and Rabani (2005), who designed an embedding into the Hamming space with distortion 20(Vlog n log log This algorithm was quite complex, and to the best of our knowledge has never been implemented. Recently, Chakraborty et al. (2016) gave a substantially different embedding with distortion O(k) where & is the edit distance between the original strings. The empirical evaluation of the algorithm, given in Zhang and Zhang (2017), demonstrated that the embedding yields good results in practice, and that the empirical distortion of this embedding typically much lower than the worst case bound. ZZhang and Zhang (2019) also proposed a novel string partition based algorithm for edit similarity join, without generating embeddings. GGomez-Bigorda et al.] (2017) presented a novel approach for word embedding in Levenshtein space to improve downstream handwritten word spotting. Their method is similar to our Phase 1, but our model deals with longer sequences instead of words, and also adopts triplet loss training to capture sequence similarity (Phase 2) and CGK based algorithm to learn sequence alignment (Phase 3).
2.3 SIMILARITY CAPTURING
Neural models are powerful to learn embeddings that capture latent similarity. For example, word2vec (Mikolov et al. 2013 learns semantic and syntactic similarity of word from its
3

---

Under review as a conference paper at ICLR 2020
f(z)
[
A
B
C
D
1
Linear Layer
GRU
GRU
GRU
+
GRU
GRU
GRU T
GRU
GRU
0
Figure 2: Our embodding model leveraging two-layer GRU.
linguistic context. The idea has been extended to learn sentence or document similarity Le and Mikolov 2014), biological sequence similarity (Asgari and Mofrad 2015 Ng 2017
The aforementioned methods characterize input representations based their context. A different approach aims to learn a distance metric, see Kulis (2013) for an overview. Among them, triplet network (Weinberger and Saul 2009; Hoffer and Ailon 2015 Schroff et al. 2015) uses triplet loss to learn similarity over triplets. Part of our model gets inspiration Trom triplet network.
3 PRELIMINARIES
We D to denote the alphabet, i.e., the set of symbols used in the strings. For any two strings 2, E D we use dg(x,y) y) to denote the edit distance between x and y, ie., the minimum number of symbol insertions, deletions
substitutions nceded to transform x into We define the distance metric d(x, y) = || - yll.- the strings have different lengths, pad the shorter string to make their lengths equal. In the binary case, d(x, y) corresponds to the Hamming distance between x and
The CGK algorithm is described below. Tts input consists of string x of length (to be embedded), and sequence of 6n random bits r, which are interpreted as a sequence of 3n random hash functions hi. fign {0,1} + {0. produces sequence fax obtained by replicating cach symbol in x at least once (the actual number is random variable depending on and r).
Algorithm CGK Embodding Function f
Input: x E {0. 1)", and a random string r E {0, 13
Output: f(z r) E (0, 1] 3m
Interpret r as the description of hi,..., han Initialization:
{0, + (0,
1, (0, (0,....0))) ,0) {0, 1
for j = 1,2, ... 3n do a, = Iji
i= i hy (x:);
end for Set f(x a.
LEARNING-BASED EMBEDDING METHOD
Recurrent Neural Network (RNN) models proved effective for sequence embedding tasks like language modeling (Mikolov et al. 2011). image captioning (Mao et al. 2015), protein sequence embedding (Bepler and Berger 2019), etc. Long Short Term Memory (LSTM)
(Hochreiter and Schmidhuber 1997) and Gated Recurrent Unit (GRU) (Cho et al. 2014
utilize gates to overcome the long-term dependency problem and often yield improved em- pirical results. Our learning based embedding model leverages two-layer GRU depicted in Figure The input is a sequence n characters onc-hot encoding, x = {x1, We feed the input sequence into two-layer GRU and linear layer to get the embedding sequence y = fxx). Here 6, represents the dropout rate in GRU. We use Adam optimizer and 4:1 train:validation split for cross-validation to tune the hyper-parameters.

---

Under review as a conference paper at ICLR 2020
Phase 1
Phase 2
Phase
Embed
> (x))
p
Embed
f2(p)
fs(x) [A
B C ...]
Idg - d]
Embed
+ f2(a)
triplet
Add minor?
loss
y
Embed
+ (1(
Embed
- f2(n)
f2(2)) [AA B CC
Figure 3: Our three phase training method: Phase as warm start; Phase 2 learns similarity; Phase for hard case. Embed refers embedding model depicted in Figure 2
h1 = GRU 11-1)
(1)
h2 ? Oh, 12
(2)
y1 Wh? +b
(3)
{yl 122 v
(4)
4.1 PHASE 1: ABSOLUTE Loss AS WARM START
We use Phase 1 tune the embedding such that the absolute difference between the edit distance and the embedding distance is small. In every iteration, we take a pair of input strings v and y, and pass it through two embedding networks denoted as fi, which share weights. The loss is defined as:
L = -dE(EE (z))
(5)
4.2 PHASE 2: TRIPLET Loss FOR SIMILARITY CAPTURING
Phase initializes the network with weights computed in Phase It leverages triplet loss (Weinberger and Saul 2009) to capture the dependencies between string similarities. In each iteration we randomly choose an original string as the anchor and define positive and negative strings with respect to their edit distances from the anchor. More specifically, We randomly sample the positive pairs from top-5 edit distance and sample negative pairs as the top-30 distance in the embedded space, which is fairly standard approach for triplet loss (Weinberger and Saul 2009; Sablayrolles et al. 2019). The anchor, the positive and the negafive string form a triplet. The triplets passed through three networks, denoted by f2, which share common weights. For an anchor a, positive string p and a negative string n, we formulate the triplet loss as:
(00x(0)d(((((o)) -((a)/)))))d((()..)))) f2()) + margin)
Further, we set margin to be dæ n) d)(a,p). Intuitively, we hope that the difference between the hamming distance between the positive and the negative pairs is larger than that of the edit distance, namely (2())) ((I2(a),{2(()) 2 dg(a,n) dd((..). See Figure for illustration.
4.3 PHASE 3: INSERTION LOss FOR HARD CASES
Phase 3 initialized using weights computed in Phase 2. During each iteration pair of input strings is passed through two embedding networks denoted as Ja, which share weights. Let x and y represent the original input strings and fa(x) and fs(y) denote their embeddings. Denote the CGK' (a variant of CGK, see Algorithm 3 in the appendix) with random initialization as g. and we apply it on fa(x), fa(y) and get fz(x) = g ((fax))), fv()) (x)) f'S is our final embedding function, which is essentially concatenation of an embodding network f and the CGK' algorithm g.
Optimization in Phase 3 has two different losses: the absolute loss and the insertion loss. The absolute loss (Lg) ensures that the distance of the final embedding close to the edit distance of x and y- The insertion loss is defined follows. For each character in fa(x),
5

---

Under review as a conference paper at ICLR 2020
compare the two cases that with without duplication of e to optimize the hash functions and the threshold. See Appendix A.1 for more details.
Lg = (d v) d (()
(7)
As we mentioned before, we use CGK' instead of CGK because restricts the number of replications of each symbol to be at most 2, therefore approximation to the gradient, and then optimize the paramcters in CGK'. In what follows we show that this modification does not affect the worst-case guarantees of the method (i.e., CGK' with random initialization). See Appendix A.2 for the proof.
compare the two cases to get
Theorem 1. The mapping f 10, x {0,1)am 7 {0, 1 computed by Algorithm salisfies the following properlies:
(1) Given {0,1)An An and (() (0, 1)2n the input, can always decode T.
2m
(2) For every 2, y E {0, dg(a, v) z d(f (z.
(3) There ezists a constant cu such that for every positive constant c 2 cu and every x, E {0, 1)"h ((flzrr,,f S dg(x, v)² with probability at least 1/2.
EXPERIMENTS
5.1 DATASETS
We evaluate our neural embedding with three datasets as in Zhang and Zhang (017)) J. Specifically, we use Gen50ks: a genetic sequence datasstt from the human genome project; UniRef: UniRef90 protein sequence dataset from the UniProt project: and Tree: a refer- ence dataset from Medline (an online modical information database). See Table | for their properties. Furthermore, following Zhang and Zhang (2117) we truncate some input strings to avoid dealing with very long outlier strings. For Gen50ks dataset, the string lengths sharply concentrate around 5000, we set the truncation length to be 5000 and threshold- ing affects the distances only minimally. For UniRef and Trec dataset, string lengths vary drastically. In order to avoid biasing the original data distribution, 11000 and 2500) so that only small (roportion(11662 and 0.97%) of the strings exceed the threshold. For Gen50ks, UniRef and Tree dataset, train our model with 1000, 2000, 2000 strings (including base and query) respectively, which means that we train with less than 2% data points in the whole dataset.
set rather large
Table Statistical analysis of three datasets.
Datasct
Gen50ks
UniRef
Tree
Alphabel Size
4
25
37
Dataset Size
50000
400000
233435
Avg Len.
5000
445
1217
Max Len.
5152
35213
3947
Min Len.
4829
200
80
5.2 NEAREST NEIGHBOR SEARCH
5.2.1 EXACT NEAREST NEIGHBOR SEARCH
We evaluate our model in the context of nearest neighbour search. We randomly select 100 queries and use the remainder the dataset as the base set. Our goal to find strings in the base set most similar to the query strings. To this end use linear scan to identify the C' sequences in the data set (called candidates) that are closest to the query in the embedded space. We compare embeddings generated by our neural model, CGK and its close variant CGK', as well as the identity embedding (which is optimal no insertions or deletions are needed). Since CGK and its variants are randomized, we measure the average of five independent runs.
For all three datasets we observe that our neural model offers significant performance gains compared to the other embedding methods.

---

Under review as a conference paper at ICLR 2020
12 PH007TE
280
(a) top-1
(b) top-10
(c) top-100
Figure 4: Gen50ks: top K recalls for algorithm (Neural) as a function of the number of candidates.
CGK, CGK' and identity,
Dbc Beito
G
1900 Mi0 DEM (NRC
U1000 20000
20300 SWie 2000 Delw soow 19000) 31300 Do0m
2508 sa0e 2980 19000 SoM 15000 (1M0
(a) top-1
(b) top-10
(c) top-100
Figure 5: Uniref: top K recalls for our algorithm (Neural) vs. CGK, CGK' and identity, as
function of the number of candidates.
Snard
2906
3000
1908
(a) top-1
(b) top-10
(c) top- 100
Figure 6: Trec: top K recalls for algorithm (Neural) vs. CGK, CGK and identity, as function the number of candidates.
5.2.2 LSH-BASED APPROXIMATE NEAREST NEIGHBOR SEARCH
In the previous section used linear to find C nearest neighbors in the embedded space. Although this task can be often accomplished efficiently (e.g., using GPUs), in many scenarios more efficient approximate nearest neighbor search algorithms need to be employed. In this section we investigate one such instantiation employing Locality-Senan Sensitive Hashing (LSH). We note that the same framework was used in Zhang and Zhang 2017 to evaluate CGK.
We the cross-poly posys-po LSH family under the Euclidean distance with multi-prole LSH (Andoni et al. [2015). For genetic dataset Gen50ks, we build 50 hash tables and 10-bit hash functions( We vary the number of hash bits and find 10-bit hash functions give the best performance). We test with five randomly selected 100 queries and record the mean and standard deviation as in Table 2
Table 2: Top-1 Recall for Gen50ks using LSH
Number of Probes
100
200
400
1600
3200
Neural
50.2+2.7
63.6
74.0
84.2
93.0
98.6+ 99.8 0..4
CGK
18.0+2.9
23.612.8
34.4+2.0
47.6+3.7
68.615.2
88.813.4
98.2+1.3
CGK' 11.0+2,6
16.812.2
26.013.0
43.0
65.8144
83.613.4
98.010.6
Identity
4.6:t0.4
9.8+1.6
19.2+1.7
33.2+4.0
56.8+33.7
83.4+2.6
97.440.8

---

Under review as a conference paper at ICLR 2020
Table 3: Recall for Gen50ks, edit distance join threshold K
50
Number of Probes
50
100
200
400
800
1600
3200
Neural
91.6
96.4
98.3
99.5
100.0
100.0
100.0
CGK
79.6
83.9
86.6
90.6
94.5
97.6
99.7
CGK'
65.0
69.5
74.4
80.3
88.0
94.8
99.0
Identity
7.9
12.9
22.0
38.6
60.2
81.5
95.7
Table 4: Recall for Gen50ks, edit distance join threshold K = 100
Number of Probes
50
100
200
400
800
1600
3200
Neural
82.5
91.0
96.4
99.0
99.8
99.9
100.0
CGK
61.9
66.9
72.9
79.8
88.1
95.0
99.2
CGK'
42.6
48.5
55.5
65.3
78.6
91.8
98.8
Identity
6.3
11.1
20.6
36.7
59.5
82.8
96.6
Table 5:
Ablation Study: Top-1 Recall for Gen50ks
Candidate Num
10
50
80
100
200
500
800
1000
2000
5000
26.4
40.6
48.2
51.8
53.0
59.8
67.8
71.0
74.2
79.4
86.2
Neural Phase 2+3
+3.44
+4499
+4.1
+3.4
+3.5
+3.4
+3.7
+3.1
+3.3
+3.7
+1.
7.6
14.8
19.4
22.0
24.4
28.2
34.4
40.0
42.8
51.8
63.6
Neural Phase 1+3
+0.4
+1.1
+1.0
+2.9
+3.0
#1.1
+1.9
+3.8
+3.4
=4.0
#4.4
36.6
49.8
60.6
63.2
65.0
70.2
77.4
81.2
82.4
88.8
94.2
Neural Phase 1+2
+1.3
#3.1
+1.9
11.7
+1.8
22.7
22.8
11.8
118
22.4
11.4
36.2
53.4
60.8
62.8
64.0
66.8
71.8
75.2
76.4
81.8
87.0
Neural Phase 1+2+3
#1.8
13.8
33.7
12.9
13.0
12.9
11.7
12.1
12.6
1.3
11.5
5.3 STRING SIMILARITY JOIN
Zhang and Zhang 2017 adopts the vanilla bit-sampling LSH for hamming distance, which docs not suit our embedding the neural embedded strings are continuous values instoad of discrete characters. So for our string similarity join experiments, we continue use the cross-polytope LSH family under the Euclidean distance with multi-probe LSH.
The LSH table parameters are the same with the approximate nearest. neighbor setting. We run PassJoin [Li et al. 2011 to evaluate our join results.
5.4 ABLATION STUDY
We further do ablation study to evaluate the function of three phases in our model. We notice performance drop by removing Phase 1 Phase 2. We explain this Phase provides good initialization which makes similarity learning easier while Phase 2 learns string similarity. Removing phase 3 generally does not lower the performance of top-1 recall much. This might be that these datasets do not contain many hard instances coexisting small shift and small substitution). Phase does show its effectiveness our synthetic hard case dataset, see Appendix A.3 We further show the standard deviation by testing with five different query sets, each of which contains randomly selected strings.
6 CONCLUSION
In this paper, we introduce the idea of using neural embedding for computing nearest neigh- bor search under edit distance. Our method has three phases, i.c., the warm-start phase for generating an initial network with the correct scale, the triplet loss phase for learning relative distance among data points, and the back up phase for dealing with hard cases. Our last phase is non-trivial, because we designed a truncated version CGK algorithm (akm performance guarantee. Our phase directly opti-
CGK') and proved that it has worst mizes CGK' and easily solves hard cases. Overall, our method gives much better empirical results than the existing met hods for nearest neighbor search.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I. P.P. and Schmidt, L. (2015). Practical and optimal LSH for angular distance. In NIPS, pages 1225 1233.
Andoni, A., Krauthgamer, R., and Onak, (2010). Polylogarithmic approximation for edit. distance and the asymmetric query complexity. In FOCS, pages 377-386. IEEE Computer Society,
Andoni, A. and Onak, K. (2012). Approximating edit distance in near-linear time. SIAM J. Comput., 41(6):1633- 1648.
Asgari, E. and Mofrad, M. R. K. (2015). Protvec: continuous distributed representation of biological sequences. CoRR, abs/1503.000 1ess1500.0514..
Backurs, A. and Indyk, P. (2015). Edit distance cannot be computed in strongly sub- quadratic time (unless SETH is false). In STOC, pages 51-58. ACM.
Bar- Yossef Z., Jayram, T. S., Krauthgamer, R., and Kumar, R. (2004). Approximating edit distance efficiently. FOCS, pages 550-559. IEEE Computer Society.
Batu, T., Ergün, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., and Sami, R. (2003). sublinear algorithm for weakly approximating edit distance. In STOC, pages 316-324. ACM.
Batu, T., Ergün, F., and Sahinalp, S. C. (2006). Oblivious string embeddings and edit distance approximations. In SODA, pages 792-801. ACM Press.
Bepler, T. and Berger, B. (2019). Learning protein sequence embeddings using information from structure.
Chakraborty, D., Das, D., Goldenberg, E., Koucky, M., and Saks, M. E. (2018). Approxi- mating edit distance within constant factor in truly sub-quadratic time. In FOCS, pages 979-988 990. IEFE Computer Society.
Chakraborty, D., Goldenberg, E., and Koucký, M. (2016). Streaming algorithuns for embed- ding and computing edit distance in the low distance regime. Tn STOC, pages 712-722 -2-... ACM.
Cho, K., van Merrienboer, B., Gülçehre, Ç., Bahdanau, D., Bougares, F., Schwenk, H., and Bengio, Y. (2014). Learning phrase representations using RNN mcoder-decode for statistical machine translation. In EMNLP, pages 1724-1734 1734. ACL.
Cormode, G., Muthukrishnan, S., and Sahinalp, S. C. (2001). Permutation editing and matching via embeddings. In ICALP, volume 2076 of Lecture Notes in Computer Science, pages 481-492. Springer.
Comez-Bigordee L., Rusiñol, M., and Karatzas, D. (2017). LSDE: levenshtein space deep embedding for query-by by-string word spotting. In ICDAR, pages 499-504. IEEE.
Hochreiter, S. and Schmidhuber, J. (1997). Long short-term memory. Neural Computation, 9(8):1733-1780.
Hoffer, E. and Ailon, N. (2015). Deep metric lcarning using triplet network. In SIMBAD, volume 9370 of Lecture Notes in Computer Science, pages 84-92. Springer.
Jowhari, H. (2012). Efficient communication protocols for deciding edit distance. In ESA, volume 7501 of Lecture Notes in Computer Science, pages 648-658 Springer.
Kulis, B. (2013). Metric learning: A survey. Foundations and Trends in Machine Learning, 5(4):287-364.
Landau, G. M., Myers, E. W., and Schmidt, J. P.. (1998). Incremental string comparison. STAM J. Comput., 27(2):557-558

---

Under review as a conference paper at ICLR 2020
Le, Q. V. and Mikolov, Т. (2014). Distributed representations of sentences and documents. In JCML, volume 32 of JMLR Workshop and Conference Proceedings, pages 1188-1196. JMLR.org.
Levenshtein, V. (1966). Binary codes capable of correcting deletions, insertions, and reversals. In Soviel physics doklady, volume 10, pages 707 710.
Levin, D. A. and Peres, Y. (2017). Markow chains and mixing times, volume 107. American Mathematical Soc.
Li, G., Deng, D., Wang, J., and Feng, J. (2011). PASS-JOIN: partition-based method for similarity joins. PVLDB, 5(3):253 264.
Mao, J., Xu, W., Yang, Y., Wang, J., and Yuille, A. L. (2015). Deep captioning with multimodal recurrent neural networks (m-rnn). In ICLR.
Masek, W. J. and Paterson, M. (1980). A faster algorithm computing string edit distances. J. Compul. Sysl. Sci., 20(1):18 31.
Mikolov, T., Kombrink, S., Burget, L., Cernocký, J., and Khudanpur, S. (2011). Extensions of recurrent neural network language model. In ICASSP, pages 5528-5531 IEEE.
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. (2013). Distributed representations of words and phrases and their compositionality. In NIPS, pages 3111 3119.
Muthukrishnan, S. and Sahinalp, C. (2000). Approximate nearest neighbors and sequence comparison with block operations. In STOC, pages 416-424. ACM.
Navarro, G. (2001). A guided tour to approximate string matching. ACM Comput. Sure., 33(1):31-88.
Ng, P. (2017). dna2vec: Consistent. vector representations of variable-length k-mers. CoRR, abs/1 Abs/1700.06279.
Ostrovsky, and Rabani, Y. (2005). Low distortion embeddings for edit distance. In STOC, pages 218-224. ACM.
Sablayrolles, A., Douze, M., Schmid, C., and Jégou, H. (2019). Spreading vectors for similarity search. ICLR (Poster). OpenReview.net
Schroff, F., Kalenichenko, D., and Philbin, J. (2015). Facenet: unified embedding for face recognition and clustering. Tn CVPR, pages 815-823. IEEE Computer Society.
van der Maaten, and Hinton, G. (2008). Visualizing data using t-SNE. Journal of Machine Learning Reseorch, 9:2579- 2605.
Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. J. ACM, 21(1):168 173.
Wang, J., Zhang, T., Song. J., Sebe, N., and Shen, H. T. (2018). A survey on learning to hash. IEEE Trans. Pattern Anal. Mach. Intell., 40(4):769-790.
Weinberger, K. Q and Saul, L. K. (2009). Distance metric learning for large margin nearest neighbor classification. J. Mach. Learn. Res., 10:207-244
Zhang, H. and Zhang, Q. (2017). Embedjoin: Efficient edit similarity joins via embeddings. In KDD, pages 585 594. ACM.
Zhang, H. and Zhang, Q. (2019). Minjoin: Efficient edit similarity joins via local hash minima. In KDD, pages 1093- 0093-1103. ACM.
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 CGK' ALGORITHM AND PHASE 3
In Algorithm we present the truncated version of CGK that we use in the paper. Com- pared with Algorithm 1 the main difference is in CGK' every character will be duplicated for at most twice (with probability 0.5). Our Phase an optimized version of CGK!. We use Algorithm 3 in Phase 3. The main difference between Algorithm and 3 is that we are using a threshold variable thres in the if-statement, to decide whether to duplicate the character or not. Moreover, the if-condition is evaluated based on the inner product between hash function hy and a one hot vector 24. Hence, Algorithm version of Algorithm 2
3 is just a more general
Then how do we optimize the parameters in Algorithm 3 E.g. thres and h)? Since Algo- rithm 3 involves discrete decisions with if-statements, manually define the gradients in Algorithm 4 by comparing the case whether the character is duplicated or not and calculate how it affects the loss.
Algorithm CGK' Embedding Function f
Input: x E {0, 1)a, and random string r E {0, 13 Output: fzz r) E {0, 1
Interpret r as the description of h1, ... .,., : {0,1} + 1}. Initialization: j -= 1, a (0.... 0) E {0. 1)2n
for i = 1,2, 1,2,...,.. do
if (x;) then
0j Ti
j= 1;
else
0j+1 = 0j = F4;
j=
end if end for Set f(x,r) = a.
Algorithm Learning- Buclingg-uugn Augmented Embedding Function f'
Input: x where x; one-hot vector, is 2n matrix interpretod as hy,..., h2ns
Ihres E R after optimization
Output: (x(x), set. Duplicate which records the duplicated bits f'(x)
Initialization: j= 1, = 02x2n, Duplicale = 0
for 1,2,...,77 , do
if h, 22 < thres then
=x;
j=j+1 11;
else
0j+1 Aj = Fi;
Duplicate + Duplicate Uf}
j=j +
end if end for
Set f'(x) a.
A.2 PROOF OF THE MAIN THEOREM
For simplicity, denote the two embedded strings f(xrr),((, f" Below always use i to denote the index for the input strings, and use to denote the index for the embedded strings. We idx(æ,)) to denote the corresponding index i for producing the
11

---

Under review as a conference paper at ICLR 2020
Algorithm 4 Optimization Scheme for h and thres in Algorithm 3
Input: v. (x),, H interpreted as hi,... Bann thres, set Duplicate in Algorithm 3 learning parameters e,
Output: H and Uhres after optimization
Initialization j =1
== (dx((")) dg(a,
for i = 1,2,..- do
g(x) = (xx if E Duplicate then
Remove g(z)5+1 from g(z);
L' =
dz(r,))):
if L,' < then
thres thres +
h, = h1 -1 Izi
end if
j j= j= 2:
clsc
Duplicate g(t) in g(z); L' dn (g(x), ('()) y)(
if L' < L then thres thres E;
hj = hj +1- Fz;
end if
j j= 1;
end if
end for
j-th index of output f(r Define A, & idx(x,;) idx(y. the input index difference between æ and y at embedding index j.
In Algorithm [ given the imput and index i, may append the output. We call the first copy the major copy, and the second copy the minor copy. The major copy always exists in the output, but the minor copy exists with probability 1/2, depending on the hash function ltj. For any index j, if ff and f are both major copies or both minor copies, we say j is aligned. Otherwise, j is not aligned. Initially, ff and If are major copies, therefore index aligned. See figure 7 for illustration.
two copies of x; into
We scan f and fa from left to right, and for every index j such that j+1 is not aligned but j is aligned, we find the next aligned index j', and group all the indices j ",,..""''' j'' as a sub-index string for the aligned index j. For the corner case that j' does not exist, we pick j' as the minimum final j value for computing fe and f (So starting from j', f or f will be padded with zeros).
Now we focus on the aligned indices. For an aligned index j without a sub- index string, we know index j ++1 1 is also aligned, otherwise j + 1 will be inside the sub-index string for index j. In this case, we can show Aj+1 - A, = by discussing whether index j + has major or minor copics.
On the other hand, consider an aligned index j with a sub-index string. In this case, we know both ff and rý are major copies. Without loss of generality, we may assume lf+1 is major copy and f/ is a minor copy (the other case is symmetric). We have the following lemma for few facts related to the sub-index string.
Lemma 2. Denote the next aligned index by j' >
jj +j+1. 1. Assume the sub-indes string has Given T such that T/2 E Z+, we have
length A j - j
(1) 17. and 13. are major copies,
(2) & < T holds with probability 1 - 2-T
12

---

Under review as a conference paper at ICLR 2020
]
Y
j
A Major
A
B
B
C
C
D
E $
E
A
B
B
C
C
D
E
F
A Minor
$
2
$
2
2
+
$ Aligned
B
B
C
C
D
D
E
E
B
B
C
C
D
E
E
F
2 Not Aligned
Figure 7: Two possible cases of the sub-index string
(3) Conditioned on S T,
{
1, w.p. 2/3 0, w.p. 1/3
Proof. Since j' is the first aligned index after j, we know that for any < < < < 3o is not aligned, therefore one of fj. and f% major and the other one minor. By Algorithm ? for the string with the minor copy, with probability 1, the next copy on jo + 1 is a major copy; and for the string with the major copy, the next copy on j. + 1 is major copy or minor copy with equal probability. However, both copies on Jo + is major, we know jo + 1 is aligned, and thus j' = jo 1. In other words, this case only happens for the index Jo = j" - 1, and for other indices, the two strings are not aligned, and have major copies in turn. That already proves (1).
Since the two strings have major copics in turn, and only major copics will increment the value of jd)( we know
1, t is odd
D D
0, otherwise
See Figure 7 for the two possible cases. Moreover, every step from j+ to j' holds with probability 1/2, so the probability that the sub-index string has length is 2-t. By summing over the probabilities of t. from 1 to T, we proved (2). Finally, (3) holds by comparing the probabilities of < T being odd and being even, which is exactly 2
Remark 1. Based on Lemma 2)), if there are sub- aubiindex strings, and for given T (to be determined later), the probability that all sub-inder strings are within length T is bounded by - 1. 2-T using union bound. Below we discuss the case conditioned on this event.
Lemma 33 states that if an aligned index has a sub-index string, and f is major copy, then A will be incremented by with probability 2/3, and stay unchanged with probability 1/3. Since ff are major copies, we know that this case happens with probability 1/4. The symmetric case where f minor copy and f5t1 is a major copy also happens with probability 1/4.
Combine the two possible cases for aligned index j (with or without sub-index string), and assuming the next aligned major index j'. If f and f/ are minor copies, or are the same, we have A A, = by simple case analysis. Ötherwise, we have:
1, w.p. 1/6
Ay A
w.p. 2/3
1, w.p. 1/6
This is because for the two aligned major copics at index j, with probability 1/2, the next index j ++ is still aligned, and as a result A does not change. With probability 1/2, there exists a sub-index string for index j, but conditioned on this, the probability that A, does not change is 1/3. So the total probability for being unchanged is 1 1/2+1/6 = 2/3. The other two cases symmetric, each has probability (1 2/3)/2 1/6. This defines random walk process for Aj and the remaining analysis similar to the analysis in Chakraborty et. al. (2016).
13

---

Under review as a conference paper at ICLR 2020
Assume that (z, y) = k. Let = 22(0) 2z11)
2x(h y be scries of strings such that
dg(x dg(x(1-1), 2 1. Let & be the first index which x(1-1) and x(1) differ. For simplicity we assume that i < ... < ik (and we will later show this is without loss of generality).
Let dj be the difference between deleted and inserted bits between æ and y before the index j. Therefore, dg = O, and
dj-1;
idx(x, E (1,,... ixx
dj-1 1,
idx(x,)) i,, idxx(x 1) + it, x(0) is obtained by deletion
dj
(9)
dj-1 + 1,
idx(x,;) it, idx(xx 1) o it, (1)) is obtained by insertion otherwise
d--1
d denotes the required length of "shift" between f* and fa. In other words, for j such that idx(x;;) E (ir, and idx(æ,,) idx(v.j) = = dj, know fj = -f Moreover, for any j' 2 j such that jdx(x,j')) E [idx(x, 4++1); we know that f3 = -. holds as well, because the same hash function will be applied to both strings after idx(x,j).
By modeling Aj and dj as chasing game between a cat and dog with kennel, the following lemma was proved in Chakraborty et al. (2016).
Lemma (Lemma in Chakraborty al. (016))) IJ dr(r(,))) v) = k, then
Pr(li 13 + fy.j is an aligned major index H 1 2 (l,,k) k)
Where 1),,1) denotes the probability that the random walk process defined by the origin, reaches the point at time t for the first time.
starting at
As discussed in Chakraborty al. (2016), the assumption that i., is are strictly mono- tone is without loss of generality, because it suffices to modify the updating rule of d, in (9) such that d, and dj-1 can be differed by more than unit. Once dy is properly defined, Lemma still applies.
The sum El qtt, k) in Lemma is casy to bound:
Lemma 4. For any k, E N, with probability more than - - il holds that
gtt
12k
t=
In particular, 7776k2 2
Proof. Below is well known fact about random walks that can be found e.g. (Theorem 2.17 in Levin and Peres (2017) For any k E N, it holds that:
12k VI
rt, 2
where r(t, k) denotes the probability a simple random walk starting at the origin reaches point lo for the first time in steps. Let be the number of non-lazy steps during t-step random walk defined in By applying Chernoff Bounds, for any < we have:
P(m (1 11-
Therefore, with probability more than 1 Et performing more than (1 - f-stess simple random walk. Setting 8 = 1 gives the result in Lemma 4.
Now ready to prove Theorem
14

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 1 (1) is trivially true, because we simulate Algorithm 2 using the random string r to decide for each index of f whether it a major copy or not.
To see (2) is true, need to do case analysis. We scan for and fu from left to right, and skip all indices that are the same. For the first different index j, there are three cases:
1. j is aligned major, and j + 1 is aligned minor.
2. j is aligned major, and j + is also aligned major.
3. j is aligned major, and j + 1 is not aligned.
For the first two cases, it suffices to replace the bit at idx(x., of x; and we can keep scanning starting from the next aligned major. For the third case, we can do induction on the length t of the sub-index string for j, to show that it suffices to make at most edits if there are different bits from j to j + t. Without loss of generality, we assume that the index j + 1 of Ie is a major copy while j + 1 of fu is minor copy.
If f = 1, which means j + 2 is aligned major. In this case, if bits at index j + 1 of f and fu are matched, it suffices edit the bit at index j. Otherwise, it suffices to delete idx(x,5) of 2, and replace the bit at idx(x, + 1) of æ to match y.
If t 2, which mcans j + is aligned major, and the index j of f is major copy. In this case, we check whether the bits at j + 2 for f², f are the same.
If yes, it means, idx(y, j 2) of y and idx(x, + 2) of are the same. In this case, it suffices to replace idx(x, of to match y.
If no, it suffices to replace both idx(x, j), idx(ar, + 1) of x to match
If 1 2, we also check whether the bits al j + for f=, g are the same.
If yes, it means, idx(y,j + t) of y and idx(x, j + of x are the same. Then we may reduce the analysis to the ( 4-2 2 case. By induction, we know that from j to j + - 2, we can make the proper edit to match x and y. If no, it mcans idx(u.j + t) of y and idx(x. j + t) of x are different. We make one edit on idx(x,)+6) to match idx(y.5+b) +t) t) of y, and then reduce the analysis to the t - 2 case.
Notice that in the above two sub-cases, we did not analyze the case index j ++t- 1. This is because this index is not aligned, and the minor copy is included in the analysis of index j to j +t 2, while the major copy is included in the analysis of index +
The above analysis shows that sulfices to make at most (( edits to match x and until one of f or fe starts to pad veros. Since there are at most d(f", deletions or insertions on z, and originally z and have the same length, we know that there are at most d(f*, padded zeros. Combine the two cases together, we have dg(f" f9)/2 s d(f",f") f").
f), there are at most I aligned major indices that satisfies f # f3. Notice that, if for any indicos, if ff f/, it does not affect d Hence below we consider other cases when fj # fl:
(3) Apply Lemma 3 know that with probability (1 (1- (1- +)) (1 1 /
If j an aligned minor, we know that j-1 is aligned major such that ff + f3, and also j + an aligned major index. Thus the number of such indices at most
If j is not aligned, we know that j belongs to a sub-index string for an aligned major index j' < j. Notice that f f f", otherwise j' won't have sub-index string. We bound the number of such indices below.
15

---

Under review as a conference paper at ICLR 2020
To recap, need to bound the expected sum of lengths of sub-index strings that start from an aligned major index j such that fj * f/ Since the number such strings and the expected length of each string at most. 2, follows that the expected sum of lengths at most 21. We can thus use Markov inequality to show that this quantity is at most 20l with probability at least 9/10.
We note that in Lemma B we did not consider the comparison between f and f when one of them has padded zeros. However, it is easy to see that in this case every edit operation can only incur one unit of cost in d(f" f which is not the worst case.
Therefore, with probability at least (1 e #) (1 1 0.1, the hamming distance at most 20l. Let
ck
we know the probability is at least
20
(1 (1- (1 12k
6
7
0.1
ek² T80
12v 120
(1
0.1
Vc
12v 120
2(
350 (1
0.1
Ve
The last inequality holds because 1, otherwise the hamming distance is Therefore
it suffices pick co 50000, and the expression above is larger than 0.5. Notice that we did not carefully tune the constants here.
(a) Neural
(b) CGK
Figure 8: t-SNE visualization of neural embedding and CGK embedding. The purple point with orange arrow represents the query string, and the red points represent top-10 10 edit distance nearest neighbors of the query strings, and the blue points represent the others.
A.3 SYNTHETIC DATA SET
Although Phase 1+2 has good performance for most data sets, we can easily construct synthetic data sets for which it will fail. For example, given string x, applying 1-bit shift to the right gives rise to a large hamming distance but the edit distance is only two. If this 1-bit shift cocxists with a 3-bit substitution (so that the hamming distance and edit distance are both equal three), it would be quite "hard" for Phase 1+2 to find nearest neighbors under edit distance. However, adding Phase easily solves the problem, and gives improved accuracy the challenging hard cases.
16

---

Under review as a conference paper at ICLR 2020
Table Top-1 Recall for the Synthetic Dataset. Candidate number one.
Model
Top-1 1 (ecall(%)
Phase 1+2+3
64.3
Phase 1+22
40.9
CGK CGK' Identity
60.1
58.0
40.6
We have generated synthetic data set illustrate the algorithm effectiveness. First we have chosen some prefix strings from the Gen50ks dataset the query set. Then, for each query, we generate its small shifts (one or two) and small substitution strings (three or four), which are used the base set. For each query we want to find the closest edit distance string in the base set. The performance of all studied algorithms on this data set are shown in Table 6 It can be scen that adding Phase improves the performance of our method.
A.4 VISUALIZATION
We visualize the embedding results for both CGK and our model using t-SNE (van der Maaten and Hinton 2008). For CGK embedding, the points distribute over the 2D space randomly no matter what hyper-parameters are used. For neural embedding, on the other hand, points are well clustered. Figure X shows 2D t-SNE projections with perplexity and learning rate 10.
17


Reviews:
[{"review_id": "rJggF6khFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper proposes a scheme to learn representations for sequences\nusing neural networks such that the Hamming distance in the embedded\nspace is close to the edit distance in the original representation of\nthe sequences. This is achieved through a 3-phase algorithm which are\nclearly motivated and technically sound. The empirical results clearly\ndemonstrate the gains from the representation learning on multiple\ndata sets and scenarios. \n\nGiven the clarity, technical soundness and the improved empirical\nperformance, I am leaning towards an accept. However, there are a\ncouple of open questions that, if addressed, would help me better\nunderstand the contributions:\n\n- The main concern is the need for the separated out phases instead\n  of directly minimizing some combinations of these different\n  terms. Is there any inherent reason why the loss function cannot be\n  combined to just train a single neural network in an end-to-end\n  manner instead of this phase-wise manner. The presence of these\n  distinct phases require the reader to figure out when to switch\n  phases, and how dependent the downstream performance is to the\n  phase change decision. \n- As expected, there is a cost to Phase 3. The text is Sec. 5.4 does\n  not appear to match up with the Table 5. The table indicates that\n  removing phase 3 actually improves performance in all but the top-10\n  and top-200 case. The text says something different. Please clarify.\n- Moreover, if there is a cost to Phase 3, can this be properly\n  explained? If there is a cost to it, could there be a way to decide\n  if/when we require the phase 3?\n\n\nMinor:\n\n- It would also be important to understand the effect of the network\n  architecture on the downstream performance. Why is a 2 layer GRU\n  necessary and/or sufficient? Some intuition regarding this would be\n  very useful and can indicate the ease of applicability of the\n  proposed scheme across different data sets.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SJgPAR6hYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose an approach for learning embeddings for strings using a three-phase approach. Each phase uses a different neural network to learn embeddings for strings such that the distance between strings in embedding space approximates the edit distance between the strings. A modest set of empirical results suggests that the proposed approach outperforms hand-crafted embeddings.\n\nI found the presentation in this paper very disjointed and difficult to follow. While I believe (my interpretation of) the basic idea of this paper is interesting, I believe the current presentation significantly hinders readers from following the authors’ intentions.\n\nComments\n\nThe description of how the network structure and weights are “initialized” across the different phases is not clear. Different notation (f_1, f_2, f_3) is used for each network, but in reality, this is just the same network. However, the writing makes this very difficult to notice.\n\nThe authors introduce the CGK and CGK’ embedding algorithms, and then proceed to prove various properties about them. However, it is not clear to me how these theoretical properties are used by the neural network. From what I can tell, CGK’ is an alternative to CGK which reduces the output size relative to CGK (from 3n to at most 2n) while still ensuring exact reconstruction of the input. (I did not verify the proof in detail.) The authors then claim that this is helpful in the current context because it ensures the network parameters can be easily optimized. It is not clear to me what this means. (I guess that somehow using “CGK’ distance” makes training the model easier than using “CGK distance”.) Additionally, the experiments do not verify this claim empirically. So it is unclear whether using “CGK’ distance” helps in the context of learning embeddings.\n\nIt is really unclear to me whether the neural network outputs a continuous or a binary vector. In particular, Equations 5 - 8 all suggest that Hamming loss is defined on the outputs of the various neural networks (f_1, f_2, and f_3). The paper also refers to bits in the output of f_3. Later on, though, the paper mentions that the neural embedded strings are continuous vectors. While this could just be typos or inconsistent notation, considering that other parts of the paper do rely on binary representations, this makes the presentation very confusing.\n\nIt is unclear to me whether the can be (approximately) reconstructed from the embeddings. It seems that Theorem 1 suggests that the binary outputs of CGK’ can be decoded, but I cannot tell whether that extends to the embeddings.\n\nIt is unclear to me how positives and negatives are sampled for training in Phase 2, and also whether that impacts training.\n\nThe experimental results should include some measure of variance based on different train and/or test splits.\n\nIt seems as though the three phases could be rolled into a single multi-task learning problem in which the network is trained during a single phase.\n\nTypos, etc.\n\nThe references are not consistently formatted.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJljrxLpKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose a three phase learning schedule to find embedding vectors for sequences. The goal is to have the euclidean distance of embedding vectors mimic the edit distance of input sequences. Given such embedding one can perform faster approximate nearest neighbor search in compare to calculating pairwise edit distances.\nThey use a RNN to output a real value per sequence step. At first they pretrain with the absolute difference of euclidean distance and edit distance. Then they fine tune with a triplet loss, such that the difference in euclidean distances be larger than the difference in edit distances. Finally they modify the embeddings with a stochastic, differentiable algorithm such that they can get guarantees for generalization.\n\nUnfortunately, the manuscript is not well written. There is a high chance of misunderstandings. What I gather from the experiment section is that their model is trained on the whole corpus. During training repeatedly trains with absolute loss on pairwise edit distances. During inference random 100 of those same sequences that has been trained on are selected to compare with the rest. If this is true, I fail to grasp the point of this paper. Since during training you have effectively calculated all the pairwise edit distances. There is no generalization happening. This paper has effectively memorized the edit distances of some sequences. \n\nIt seems that only phase 3 (cgk') is designed to have any accuracy on unseen sequences, and experiments show that it underperforms the original cgk.\n\nIf this is not true and indeed they are training for example on one half of the corpus and the 100 query + base are unseen during training I am willing to increase my score. Given the added clarification in the paper.\n\nAgain assuming that this is not just memorization:\n\nWhy eq 5 (regression loss) is the absolute value? It means that you will never get closer than lr/2 to the optimal point, where as with a least squares loss your gradients get smaller when you get closer.\n\nHow are the negative sample, positive samples selected for an anchor? Are they just two random points, is there any importance sampling happening?\n\nWhy during phase 2, the phase 1 loss is stopped? There is no intuition, justification in the paper. Why the loss is not eq 5 + eq 6 during the whole training?\n\nHow are you optimizing? SGD I assume? How are you selecting hyper-parameters, such as learning rate? Is there any validation set?\n\nIs there a typo in eq 7? The text says \"we calculate the absolute loss as in Phase 1 to optimize our embedding network f3\" but eq 7 is on f'(3). Are you backpropagating through algorithm 3 toward embeddings or just toward thres as in algorithm 4?\n\nCurrently, given the poor quality of the write up, the merit of the idea and the experiments is not clear.\n\nRelated work: LSDE: Levenshtein Space Deep Embedding for Query-by-string Word Spotting", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an approach to improving the calculation of embeddings for nearest-neighbor search with respect to edit distance.

Reading the reviews, it seems that the paper is greatly improved over its previous version, but still has significant clarity issues. Given that these issues remain even after one major revision, I would suggest that the paper not be accepted for this ICLR, but that the authors carefully revise the paper for clarity and submit to a following submission opportunity. It may help to share the paper with others who are not familiar with the research until they can read it once and understand the method well.

I have quoted Reviewer 3 below in the author discussion, where there are some additional clarity issues that may help being resolved:

----------

Some specifics are clear now with their new edition. 
* The [relationship between] cgk' & cgk not as clear as it could be. For example the algorithms are designed for bits. So one should assume that they are applying it on the bits of the characters. But this should be clarified in the manuscript.
* Also still backpropagating through f' is not clear to me.
* And in the text for inference they still say: "We randomly select 100 queries and use the remainder of the dataset as the base set" which should be "the remainder excluding the training set" or "including?".
Decision: Reject