Reward Augmented Maximum Likelihood for Neural Structured Prediction
A key problem in structured output prediction is direct optimization of the task reward function that matters for test evaluation. This paper presents a simple and computationally efficient approach to incorporate task reward into a maximum likelihood framework. By establishing a link between the log-likelihood and expected reward objectives, we show that an optimal regularized expected reward is achieved when the conditional distribution of the outputs given the inputs is proportional to their exponentiated scaled rewards. Accordingly, we present a framework to smooth the predictive probability of the outputs using their corresponding rewards. We optimize the conditional log-probability of augmented outputs that are sampled proportionally to their exponentiated scaled rewards. Experiments on neural sequence to sequence models for speech recognition and machine translation show notable improvements over a maximum likelihood baseline by using reward augmented maximum likelihood (RML), where the rewards are defined as the negative edit distance between the outputs and the ground truth labels.
The submitted paper presents an alternative to expected reward optimization (eq. 3) for neural structured prediction. The new objective (eq. 8) requires to work with a normalized reward score that defines a proper probability distribution. Sampling from this stationary distribution has the great advantage of reduced variance (which is furthered by annealing with a temperature hyperparameter). The paper is evaluated on two sequence-to-sequence learning tasks, with promising results.  
The paper addresses an important problem in optimizing expected reward for structured prediction, namely the high variance of estimation procedures that have to sample from a non-stationary model distribution. In the natural language community, especially in statistical machine translation, "expected reward optimization" is known under the name of "minimum risk optimization" or "maximum expected BLEU" training, and has been successfully applied for linear discriminative models (Och: Minimum error rate training in statistical machine translation, ACL 2003; Li & Eisner: First- and second-order expectation semirings with applications to minimum-risk training on translation forests, EMNLP 2009; He & Deng: Maximum expected BLEU training of phrase and lexicon translation models; inter alia) and non-linear neural models (Shen et al.: Minimum risk training for neural machine translation, ACL 2016). It is also known in vision as "expected loss optimization" (Yuille & He: Probabilistic models of vision and max-margin methods. Frontiers of Electrical and Electronic Engineering. 2012). In all these approaches, instead of sampling, expected reward is calculated exactly on n-best lists of outputs or via dynamic programming over the output graph. These approaches should be mentioned, especially the application to neural MT by Shen et al. 2016, and it should be explained why a direct calculation of expected reward over n-best lists or translation graphs is not an option in your approach. Additionally, since these approaches are well-known in machine translation, they should be considered as baseline in your experimental comparison.  The issue of sampling becomes important if reward feedback on output is only available for a single sampled output. This is the case in Ranzato et al.'s reinforcement learning approach or in bandit structure prediction approaches (Sokolov et al.: Stochastic Structured Prediction under Bandit Feedback. http://arxiv.org/abs/1606.00739). The first approach solves the variance problem by initializing the model with a word-level model trained in batch-mode. The second approach explores different objectives among which a cross-entropy objective is used which is identical to (7) (or (8) without the maximum entropy regularizer). Since the approach of Solokov et al. works in a bandit setting, normalizing reward in order to sample from it is not possible. Thus one drawback of the presented work is that is applicable only in cases where rewards are available to all output structures, otherwise the normalization constant cannot be calculated properly. Speaking of which, what are the guarantees on the quality of approximating the normalization constant based on samples? Firstly, a normalization constant is not an expectation that can be easily be approximated by sampling. Secondly, an approximate per-sentence BLEU score needs to be used in the practical application to machine translation. What is it in your experiment?  Concerning the analysis given in the paper, it is nice to see how objective (8) and (3) differ. However, a simple application of Jensen's inequality (mentioned in Sokolov et al. 2016) shows that (8) is a convex upper bound on (3):  Let q and p be defined as in Section 3, then E_q[ -log p] >= -log E_p[q].  It is not entirely clear what the lengthy derivation given in the presented paper adds to this. Furthermore, for unbounded SMT metrics such as Translation Error Rate (Snover et al.: A Study of Translation Error Rate with Targeted Human Annotation, AMTA 2006) the term ||s-r|| can be very large. Thus r and s need to be specified more clearly in the submitted paper.  What is also not mentioned in the presented paper is the aspect of convexity which could give rise to faster convergence, which is again not mentioned or measured in the presented paper. Since variance reduction is claimed as a key contribution, the relation of variance reduction to convergence speed might be worth exploring.  Lastly, the experiments presented in the paper seem to show promising improvements, however, many details are missing: What was the per-sentence BLEU approximation used as reward signal? Why did you not optimize the temperature constant on a heldout set - the presented evaluation basically selects the temperature constant on the test set. Are the result differences statistically significant?  Finally, possible citations for using annealing schedules and sampling in expected loss training for structured prediction are:  Smith & Eisner: Minimum risk annealing for training log-linear models. ACL 2006. Arun et al.: A unified approach to minimum risk training and decoding. WMT 2010.