Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.
They 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.

Unfortunately, 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. 

It seems that only phase 3 (cgk') is designed to have any accuracy on unseen sequences, and experiments show that it underperforms the original cgk.

If 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.

Again assuming that this is not just memorization:

Why 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.

How are the negative sample, positive samples selected for an anchor? Are they just two random points, is there any importance sampling happening?

Why 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?

How are you optimizing? SGD I assume? How are you selecting hyper-parameters, such as learning rate? Is there any validation set?

Is 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?

Currently, given the poor quality of the write up, the merit of the idea and the experiments is not clear.

Related work: LSDE: Levenshtein Space Deep Embedding for Query-by-string Word Spotting
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 
The paper proposes a scheme to learn representations for sequences
using neural networks such that the Hamming distance in the embedded
space is close to the edit distance in the original representation of
the sequences. This is achieved through a 3-phase algorithm which are
clearly motivated and technically sound. The empirical results clearly
demonstrate the gains from the representation learning on multiple
data sets and scenarios. 

Given the clarity, technical soundness and the improved empirical
performance, I am leaning towards an accept. However, there are a
couple of open questions that, if addressed, would help me better
understand the contributions:

- The main concern is the need for the separated out phases instead
  of directly minimizing some combinations of these different
  terms. Is there any inherent reason why the loss function cannot be
  combined to just train a single neural network in an end-to-end
  manner instead of this phase-wise manner. The presence of these
  distinct phases require the reader to figure out when to switch
  phases, and how dependent the downstream performance is to the
  phase change decision. 
- As expected, there is a cost to Phase 3. The text is Sec. 5.4 does
  not appear to match up with the Table 5. The table indicates that
  removing phase 3 actually improves performance in all but the top-10
  and top-200 case. The text says something different. Please clarify.
- Moreover, if there is a cost to Phase 3, can this be properly
  explained? If there is a cost to it, could there be a way to decide
  if/when we require the phase 3?


Minor:

- It would also be important to understand the effect of the network
  architecture on the downstream performance. Why is a 2 layer GRU
  necessary and/or sufficient? Some intuition regarding this would be
  very useful and can indicate the ease of applicability of the
  proposed scheme across different data sets.

review_title: Official Blind Review #1

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