OPTIMAL COMPLETION DISTILLATION FOR SEQUENCE LEARNING
We present Optimal Completion Distillation (OCD), a training procedure for optimizing sequence to sequence models based on edit distance. OCD is efficient, has no hyper-parameters of its own, and does not require pretraining or joint optimization with conditional log-likelihood. Given a partial sequence generated by the model, we first identify the set of optimal suffixes that minimize the total edit distance, using an efficient dynamic programming algorithm. Then, for each position of the generated sequence, we define a target distribution that puts an equal probability on the first token of each optimal suffix. OCD achieves the state-of-theart performance on end-to-end speech recognition, on both Wall Street Journal and Librispeech datasets, achieving 9.3% and 4.5% word error rates, respectively.
The authors propose an alternative approach to training seq2seq models, which addresses concerns about exposure bias and about the typical MLE objective being different from the final evaluation metric. In particular, the authors propose to use a dynamic program to compute the optimal continuations of predicted prefixes (during training) in terms of edit distance to the true output, and then use a per-token cross entropy loss, with a target distribution that is uniform over all optimal next-tokens. The authors conduct a number of experiments, and show that this scheme allows them to attain state-of-the-art performance on end-to-end speech recognition, and that they can moreover do this without needing to pretrain the model with the MLE objective.
This is a very nice paper; it is generally well written, it gets excellent results, and it contains a comprehensive set of experiments and analysis. It is also quite exciting to see an approach to alleviating exposure bias that does not require pretraining with MLE. Accordingly, my suggestions mainly relate to the presentation and related work:
 - It seems a bit strange to argue that the proposed approach doesn't increase the time complexity over MLE. While technically true (as the authors note) if the vocabulary is bigger than the sequence lengths, the difference in (on policy) training time will presumably be felt when dealing with very long sequences, or with cases where the number of labels per time-step is small, like in character-level generation or in seq2seq style sequence labeling.
 - I think it's difficult to argue that the proposed approach isn't essentially a modification of imitation learning/learning-to-search algorithms like, say, AggreVaTe or LOLS (Chang et al., ICML 2015). As far as I can tell, the only differences are that cross entropy is used rather than a cost-sensitive classifier, and, perhaps, that the training is done in minibatches (with no aggregation).
 
 - Relatedly, while it is interesting that the loss uses all the optimal completion tokens, it should be noted that there is much work in transition-based parsing that adopts a learning-to-search approach and uses losses that incorporate multiple optimal next-predictions as given by a "dynamic oracle"; see Goldberg and Nivre (COLING, 2012) and others.  
 - I think it's also worth noting that training approaches like MIXER and others can target arbitrary rewards (and not just those where we can efficiently compute optimal next-steps), and so the proposed approach is a compelling competitor to MIXER-like approaches on problems such as machine translation or image captioning only to the extent that training with edit-distance is useful for such problems. Do you have a sense of whether training with edit-distance does indeed improve performance on such tasks?
Pros:
- well written and interesting
- good experiments, results, and analysis
Cons:
 - perhaps slightly more similar to previous work than is argued
Update after author response: thanks for your response; I think the revised paper largely addresses my comments and those of the other reviewers, and I continue to hope it is accepted. Here are two small notes on the related work section of the revised paper:
- In distinguishing OCD from DAgger, you note that the optimal policy is computed rather than provided at training time. In fact, structured prediction applications of SEARN (Daume III et al., 2009, which should also be cited) and DAgger often have this flavor too, such as when using them for sequence labeling (where optimal continuations are calculated based on Hamming distance).
- Please include a reference to Goldberg and Nivre's (2012) dynamic oracle work.