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.
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.
I 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.
Comments
The 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.
The 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.
It 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.
It 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.
It is unclear to me how positives and negatives are sampled for training in Phase 2, and also whether that impacts training.
The experimental results should include some measure of variance based on different train and/or test splits.
It 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.
Typos, etc.
The references are not consistently formatted.