Reward Augmented Maximum Likelihood for Neural Structured Prediction

Introduction

Structured output prediction is ubiquitous in machine learning. Recent advances in natural language processing, machine translation, and speech recognition hinge on the development of better discriminative models for structured outputs and sequences. The foundations of learning structured output models were established by the seminal work on conditional random fields (CRFs) and variants , and structured large margin methods , which demonstrate how generalization performance can be significantly improved when one considers the joint effects of the predictions across multiple output components. These models have evolved into their deep neural counterparts through the use of recurrent neural networks (RNN) with LSTM and GRU cells and attention mechanisms .

A key problem in structured output prediction has always been to enable direct optimization of the task reward (loss) used for test evaluation. For example, in machine translation one seeks better BLEU scores, and in speech recognition better word error rates. Not surprisingly, almost all task reward metrics are not differentiable, hence hard to optimize. Neural sequence models (e.g. ) optimize conditional log-likelihood, i.e. the conditional log-probability of the ground truth outputs given corresponding inputs. These models do not explicitly consider the task reward during training, hoping that conditional log-likelihood serves as a good surrogate for the task reward. Such methods make no distinction between alternative incorrect outputs: log-probability is only measured on the ground truth input-output pairs, and all alternative outputs are equally penalized through normalization, whether near or far from the ground truth target. We believe one can improve upon maximum likelihood (ML) sequence models if the difference in the rewards of alternative outputs is taken into account.

Standard ML training, despite its limitations, has enabled the training of deep RNN models, leading to revolutionary advances in machine translation and speech recognition . A key property of ML training for locally normalized RNN models is that the objective function factorizes into individual loss terms, which could be efficiently optimized using stochastic gradient descend (SGD). This training procedure does not require any form of inference or sampling from the model during training, leading to computational efficiency and ease to implementation. By contrast, almost all alternative formulations for training structure prediction models require some form of inference or sampling from the model at training time which slows down training, especially for deep RNNs (e.g. see large margin, search-based , and expected risk optimization methods).

Our work is inspired by the use of reinforcement learning (RL) algorithms, such as policy gradient , to optimize expected task reward . Even though expected task reward seems like a natural objective, direct policy optimization faces significant challenges: unlike ML, a stochastic gradient given a mini-batch of training examples is extremely noisy and has a high variance; gradients need to be estimated via sampling from the model, which is a non-stationary distribution; the reward is often sparse in a high-dimensional output space, which makes it difficult to find any high value predictions, preventing learning from getting off the ground; and, finally, maximizing reward does not explicitly consider the supervised labels, which seems inefficient. In fact, all previous attempts at direct policy optimization for structured output prediction have started by bootstrapping from a previously trained ML solution , using several heuristics and tricks to make learning stable.

This paper presents a new approach to task reward optimization that combines the computational efficiency and simplicity of ML with the conceptual advantages of expected reward maximization. Our algorithm called reward augmented maximum likelihood (RAML) simply adds a sampling step on top of the typical likelihood objective. Instead of optimizing conditional log-likelihood on training input-output pairs, given each training input, we first sample an output proportionally to its exponentiated scaled reward. Then, we optimize log-likelihood on such auxiliary output samples given corresponding inputs. When the reward for an output is defined as its similarity to a ground truth output, then the output sampling distribution is peaked at the ground truth output, and its concentration is controlled by a temperature hyper-parameter.

Our theoretical analysis shows that the RAML and regularized expected reward objectives optimize a KL divergence between the exponentiated reward and model distributions, but in opposite directions. Further, we show that at non-zero temperatures, the gap between the two criteria can be expressed by a difference of variances measured on interpolating distributions. This observation reveals how entropy regularized expected reward can be estimated by sampling from exponentiated scaled rewards, rather than sampling from the model distribution.

Remarkably, we find that the RAML approach achieves significantly improved results over state of the art maximum likelihood RNNs. We show consistent improvement on both speech recognition (TIMIT dataset) and machine translation (WMT’14 dataset), where output sequences are sampled according to their edit distance to the ground truth outputs. Surprisingly, we find that the best performance is achieved with output sampling distributions that shift a lot of the weight away from the ground truth outputs. In fact, in our experiments, the training algorithm rarely sees the original unperturbed outputs. Our results give further evidence that models trained with imperfect outputs and their reward values can improve upon models that are only exposed to a single ground truth output per input .

Reward augmented maximum likelihood

Given a dataset of input-output pairs, $\mathcal{D}\equiv\{(\boldsymbol{\mathbf{x}}^{(i)},\boldsymbol{\mathbf{y}}^{*(i)})\}_{i=1}^{N}$, structured output models learn a parametric score function ${p}_{\theta}({\mathbf{y}}\mid\boldsymbol{\mathbf{x}})$, which scores different output hypotheses, ${\mathbf{y}}\in\mathcal{Y}$. We assume that the set of possible output, $\mathcal{Y}$ is finite, e.g. English sentences up to a maximum length. In a probabilistic model, the score function is normalized, while in a large-margin model the score may not be normalized. In either case, once the score function is learned, given an input $\boldsymbol{\mathbf{x}}$, the model predicts an output $\widehat{\boldsymbol{\mathbf{y}}}$ achieving maximal score,

If this optimization is intractable, approximate inference (e.g. beam search) is used. We use a reward function $r(\boldsymbol{\mathbf{y}},{\mathbf{y}}^{*})$ to evaluate different proposed outputs against ground-truth outputs. Given a test dataset $\mathcal{D}^{\prime}$, one computes $\sum_{(\boldsymbol{\mathbf{x}},{\mathbf{y}}^{*})\in\mathcal{D}^{\prime}}r(\widehat{\boldsymbol{\mathbf{y}}}(\boldsymbol{\mathbf{x}}),{\mathbf{y}}^{*})$ as a measure of empirical reward. Since models with larger empirical reward are preferred, ideally one hopes to maximize empirical reward during training.

However, since empirical reward is not amenable to numerical optimization, one often considers optimizing alternative differentiable objectives. The maximum likelihood (ML) framework tries to minimize negative log-likelihood of the parameters given the data,

Minimizing this objective increases the conditional probability of the target outputs, $\log{p}_{\theta}({\mathbf{y}}^{*}\mid\boldsymbol{\mathbf{x}})$, while decreasing the conditional probability of alternative incorrect outputs. According to this objective, all negative outputs are equally wrong, and none is preferred over the others.

By contrast, reinforcement learning (RL) advocates optimizing expected reward (with a maximum entropy regularizer ), which is formulated as minimization of the following objective,

Let us define a distribution in the output space, termed the exponentiated payoff distribution, that is central in linking ML and RL objectives:

Returning to the log-likelihood objective, one can verify that (2) is equivalent to a KL divergence in the opposite direction between a delta distribution $\delta({\mathbf{y}}\mid{\mathbf{y}}^{*})$ and the model distribution ${p}_{\theta}({\mathbf{y}}\mid\boldsymbol{\mathbf{x}})$,

We propose a method called reward-augmented maximum likelihood (RAML), which generalizes ML by allowing a non-zero temperature parameter in the exponentiated payoff distribution, while still optimizing the KL divergence in the ML direction. The RAML objective function takes the form,

which can be re-expressed in terms of a KL divergence as follows,

2 Sampling from the exponentiated payoff distribution

To compute the gradient of the model using the RAML approach, one needs to sample auxiliary outputs from the exponentiated payoff distribution, $q({\mathbf{y}}\mid{\mathbf{y}}^{*};\tau)$. This sampling is the price that we have to pay to learn with rewards. One should contrast this with loss-augmented inference in structured large margin methods, and sampling from the model in RL. We believe sampling outputs proportional to exponentiated rewards is more efficient and effective in many cases.

Experiments in this paper use reward values defined by either negative Hamming distance or negative edit distance. We sample from $q({\mathbf{y}}\mid{\mathbf{y}}^{*};\tau)$ by stratified sampling, where we first select a particular distance, and then sample an output with that distance value. Here we focus on edit distance sampling, as Hamming distance sampling is a simpler special case. Given a sentence ${\mathbf{y}}^{*}$ of length $m$, we count the number of sentences within an edit distance $e$, where $e\in\{0,\ldots,2m\}$. Then, we reweight the counts by $\exp\{-e/\tau\}$ and normalize. Let $c(e,m)$ denote the number of sentences at an edit distance $e$ from a sentence of length $m$. First, note that a deletion can be thought as a substitution with a nil token. This works out nicely because given a vocabulary of length $v$, for each insertion we have $v$ options, and for each substitution we have $v-1$ options, but including the nil token, there are $v$ options for substitutions too. When $e=1$, there are $m$ possible substitutions and $m+1$ insertions. Hence, in total there are $(2m+1)v$ sentences at an edit distance of $1$. Note, that exact computation of $c(e,m)$ is difficult if we consider all edge cases, for example when there are repetitive words in ${\mathbf{y}}^{*}$, but ignoring such edge cases we can come up with approximate counts that are reliable for sampling. When $e>1$, we estimate $c(e,m)$ by

where $s$ enumerates over the number of substitutions. Once $s$ tokens are substituted, then those $s$ positions lose their significance, and the insertions before and after such tokens could be merged. Hence, given $s$ substitutions, there are really $m-s$ reference positions for $e-s$ possible insertions. Finally, one can sample according to BLEU score or other sequence metrics by importance sampling where the proposal distribution could be edit distance sampling above.

RAML analysis

the difference between the strictly convex potential at $p$ and its first order Taylor approximation expanded about $q$. Clearly this definition is not symmetric between $p$ and $q$. By the strict convexity of $F$ it follows that $D_{F}\left(p~{}\|~{}q\right)\geq 0$ with $D_{F}\left(p~{}\|~{}q\right)=0$ if and only if $p=q$. To characterize the difference between opposite Bregman divergences, we provide a simple result that relates the two directions under suitable conditions. Let $H_{F}$ denote the Hessian of $F$.

for some $a=(1-\alpha)p+\alpha q$, ($0\leq\alpha\leq{\textstyle\frac{1}{2}}$), $b=(1-\beta)q+\beta p$, ($0\leq\beta\leq{\textstyle\frac{1}{2}}$). (see Appendix A)

The KL divergence between $p$ and $q$ in two directions can be expressed as,

for some $a=(1-\alpha){s}+\alpha r$, ($0\leq\alpha\leq{\textstyle\frac{1}{2}}$), $b=(1-\beta)r+\beta{s}$, ($0\leq\beta\leq{\textstyle\frac{1}{2}}$). (see Appendix A)

where ${s}(\boldsymbol{\mathbf{y}})$ denotes $\tau$-scaled logits predicted by the model such that ${p}_{\theta}({\mathbf{y}}\mid\boldsymbol{\mathbf{x}})=f^{*}({s}(\boldsymbol{\mathbf{y}})/\tau)$, and $r(\boldsymbol{\mathbf{y}})=r({\mathbf{y}},{\mathbf{y}}^{*})$. The gap between regularized expected reward (5) and $\tau$-scaled RAML criterion (8) is simply a difference of two variances, whose magnitude decreases with increasing regularization. Proposition 2 also shows an opportunity for learning algorithms: if $\tau$ is chosen so that $q=f^{*}(r/\tau)$, then $f^{*}(a/\tau)$ and $f^{*}(b/\tau)$ have lower variance than ${p}$ (which can always be achieved for sufficiently small $\tau$ provided ${p}$ is not deterministic), then the expected regularized reward under ${p}$, and its gradient for training, can be exactly estimated, in principle, by including the extra variance terms and sampling from more focused distributions than ${p}$. Although we have not yet incorporated approximations to the additional variance terms into RAML, this is an interesting research direction.

Related Work

The literature on structure output prediction is vast, falling into three broad categories: (a) supervised learning approaches that ignore task reward and use supervision; (b) reinforcement learning approaches that use only task reward and ignore supervision; and (c) hybrid approaches that attempt to exploit both supervision and task reward. This paper clearly falls in category (c).

Work in category (a) includes classical conditional random fields and conditional log-likelihood training of RNNs . It also includes the approaches that attempt to perturb the training inputs and supervised training structures to improves the robustness (and hopefully the generalization) of the conditional models (e.g. see ). These approaches offer improvements to standard maximum likelihood estimation, but they are fundamentally limited by not incorporating a task reward. The DAGGER method also focuses on using supervision only, but can be extended to use a task loss; even then, the DAGGER assumes that an expert is available to label every alternative sequence, which does not fit the usual structured prediction scenario.

By contrast, work in category (b) includes reinforcement learning approaches that only consider task reward and do not use any other supervision. Beyond the traditional reinforcement learning approaches, such as policy gradient , and actor-critic , Q-learning , this category includes SEARN . There is some relationship to the work presented here and work on relative entropy policy search , and policy optimization via expectation maximization and KL-divergence , however none of these bridge the gap between the two directions of the KL-divergence, nor do they consider any supervision data as we do here.

There is also a substantial body of related work in category (c), which considers how to exploit supervision information while training with a task reward metric. A canonical example is large margin structured prediction , which explicitly uses supervision and considers an upper bound surrogate for task loss. This approach requires loss augmented inference that cannot be efficiently achieved for general task losses. We are not aware of successful large-margin methods for neural sequence prediction, but a related approach by for neural machine translation builds on SEARN . Some form of inference during training is still needed, and the characteristics of the objective are not well studied. We also mentioned the work on maximizing task reward by bootstrapping from a maximum likelihood policy , but such an approach only makes limited use of supervision. Some work in robotics has considered exploiting supervision as a means to provide indirect sampling guidance to improve policy search methods that maximize task reward , but these approaches do not make use of maximum likelihood training. An interesting work is which explicitly incorporates supervision in the policy evaluation phase of a policy iteration procedure that otherwise seeks to maximize task reward. However, this approach only considers a greedy policy form that does not lend itself to being represented as a deep RNN, and has not been applied to structured output prediction. Most relevant are ideas for improving approximate maximum likelihood training for intractable models by passing the gradient calculation through an approximate inference procedure . These works, however, are specialized to particular approximate inference procedures, and, by directly targeting expected reward, are subject to the variance problems that motivated this work.

One advantage of the RAML framework is its computational efficiency at training time. By contrast, RL and scheduled sampling require sampling from the model, which can slow down the gradient computation by $2\times$. Structural SVM requires loss-augmented inference which is often more expensive than sampling from the model. Our framework only requires sampling from a fixed exponentated payoff distribution, which can be thought as a form of input pre-processing. This pre-processing can be parallelized by model training by having a thread handling loading the data and augmentation.

Recently, we were informed of the unpublished work of Volkovs et al. that also proposes an objective like RAML, albeit with a different derivation. No theoretical relation was established to entropy regularized RL, nor was the method applied to neural nets for sequences, but large gains were reported over several baselines applying the technique to ranking problems with CRFs.

Experiments

We compare our approach, reward augmented maximum likelihood (RAML), with standard maximum likelihood (ML) training on sequence prediction tasks using state-of-the-art attention-based recurrent neural networks . Our experiments demonstrate that the RAML approach considerably outperforms ML baseline on both speech recognition and machine translation tasks.

For experiments on speech recognition, we use the TIMIT dataset; a standard benchmark for clean phone recognition. This dataset consists of recordings from different speakers reading ten phonetically rich sentences covering major dialects of American English. We use the standard train / dev / test splits suggested by the Kaldi toolkit .

As the sequence prediction model, we use an attention-based encoder-decoder recurrent model of with three $256$-dimensional LSTM layers for encoding and one $256$-dimensional LSTM layer for decoding. We do not modify the neural network architecture or its gradient computation in any way, but we only change the output targets fed into the network for gradient computation and SGD update. The input to the network is a standard sequence of $123$-dimensional log-mel filter response statistics. Given each input, we generate new outputs around ground truth targets by sampling according to the exponentiated payoff distribution. We use negative edit distance as the measure of reward. Our output augmentation process allows insertions, deletions, and substitutions.

An important hyper-parameter in our framework is the temperature parameter, $\tau$, controlling the degree of output augmentation. We investigate the impact of this hyper-parameter and report results for $\tau$ selected from a candidate set of $\tau\in\{0.6,\,0.65,\,0.7,\,0.75,\,0.8,\,0.85,\,0.9,\,0.95,\,1.0\}$. At a temperature of $\tau=0$, outputs are not augmented at all, but as $\tau$ increases, more augmentation is generated. Figure 1 depicts the fraction of different numbers of edits applied to a sequence of length $20$ for different values of $\tau$. These edits typically include very small number of deletions, and roughly equal number of insertions and substitutions. For insertions and substitutions we uniformly sample elements from a vocabulary of $61$ phones. According to Figure 1, at $\tau=0.6$, more than $60\%$ of the outputs remain intact, while at $\tau=0.9$, almost all target outputs are being augmented with $5$ to $9$ edits being sampled with a probability larger than $0.1$. We note that the augmentation becomes more severe as the outputs get longer.

The phone error rates (PER) on both dev and test sets for different values of $\tau$ and the ML baseline are reported in Table 1. Each model is trained and tested $4$ times, using different random seeds. In Table 1, we report average PER across the runs, and in parenthesis the difference of average error to minimum and maximum error. We observe that a temperature of $\tau=0.9$ provides the best results, outperforming the ML baseline by $2.9\%$ PER on the dev set and $2.3\%$ PER on the test set. The results consistently improve when the temperature increases from $0.6$ to $0.9$, and they get worse beyond $\tau=0.9$. It is surprising to us that not only the model trains with such a large amount of augmentation at $\tau=0.9$, but also it significantly improves upon the baseline. Finally, we note that previous work suggests several refinements to improve sequence to sequence models on TIMIT by adding noise to the weights and using more focused forward-moving attention mechanism. While these refinements are interesting and they could be combined with the RAML framework, in this work, we do not implement such refinements, and focus specifically on a fair comparison between the ML baseline and the RAML method.

2 Machine translation

We evaluate the effectiveness of the proposed approach on WMT’14 English to French machine translation benchmark. Translation quality is assessed using tokenized BLEU score, to be consistent with previous work on neural machine translation . Models are trained on the full $36$M sentence pairs from WMT’14 training set, and evaluated on $3003$ sentence pairs from newstest-2014 test set. To keep the sampling process efficient and simple on such a large corpus, we augment the output sentences only based on Hamming distance (i.e. edit distance without insertion or deletion). For each sentece we sample a single output at each step. One can consider insertions and deletions or sampling according to exponentiated sentence BLEU scores, but we leave that to future work.

As the conditional sequence prediction model, we use an attention-based encoder-decoder recurrent neural network similar to , but we use multi-layer encoder and decoder networks consisting of three layers of $1024$ LSTM cells. As suggested by , for computing the softmax attention vectors, we use a feedforward neural network with $1024$ hidden units, which operates on the last encoder and the first decoder layers. In all of the experiments, we keep the network architecture and the hyper-parameters fixed. All of the models achieve their peak performance after about $4$ epochs of training, once we anneal the learning rates. To reduce the noise in the BLEU score evaluation, we report both peak BLEU score and BLEU score averaged among about $70$ evaluations of the model while doing the fifth epoch of training. We perform beam search decoding with a beam size of $8$.

Table 2 summarizes our experimental results on WMT’14. We note that our ML translation baseline is quite strong, if not the best among neural machine translation models , achieving very competitive performance for a single model. Even given such a strong baseline, the RAML approach consistently improves the results. Our best model with a temperature $\tau=0.85$ improves average BLEU by $0.4$, and best BLEU by $0.35$ points, which is a considerable improvement. Again we observe that as we increase the amount of augmentation from $\tau=0.75$ to $\tau=0.85$ the results consistently get better, and then they start to get worse with more augmentation.

Details. We train the models using asynchronous SGD with $12$ replicas without momentum. We use mini-batches of size $128$. We initially use a learning rate of $0.5$, which we then exponentially decay to $0.05$ after $800K$ steps. We keep evaluating the models between $1.1$ and $1.3$ million steps and report average and peak BLEU scores in Table 2. We use a vocabulary $200K$ words for the source language and $80K$ for the target language. We only consider training sentences that are up to $80$ tokens. We replace rare words with several UNK tokens based on their first and last characters. At inference time, we replace UNK tokens in the output sentences by copying source words according to largest attention activations as suggested by .

Conclusion

We present a learning algorithm for structured output prediction that generalizes maximum likelihood training by enabling direct optimization of a task reward metric. Our method is computationally efficient and simple to implement. It only requires augmentation of the output targets used within a log-likelihood objective. We show how using augmented outputs sampled according to edit distance improves a maximum likelihood baseline by a considerable margin, on both machine translation and speech recognition tasks. We believe this framework is applicable to a wide range of probabilistic models with arbitrary reward functions. In the future, we intend to explore the applicability of this framework to other probabilistic models on tasks with more complicated evaluation metrics.

Acknowledgment

We thank Dan Abolafia, Sergey Levine, Cinjon Resnick, Yujia Li, Ben Poole, and the Google Brain team for insightful comments and discussions.

References

Appendix A Proofs

for some $a=(1-\alpha)p+\alpha q$, ($0\leq\alpha\leq{\textstyle\frac{1}{2}}$), $b=(1-\beta)q+\beta p$, ($0\leq\beta\leq{\textstyle\frac{1}{2}}$).

Let $f(p)$ denote $\nabla F(p)$ and consider the midpoint ${\textstyle\frac{q+p}{2}}$. One can express $F({\textstyle\frac{q+p}{2}})$ by two Taylor expansions around $p$ and $q$. By Taylor’s theorem there is an $a=(1-\alpha)p+\alpha q$ for $0\leq\alpha\leq{\textstyle\frac{1}{2}}$ and $b=\beta p+(1-\beta)q$ for $0\leq\beta\leq{\textstyle\frac{1}{2}}$ such that

where ${s}\!=\!f({p})$ and $r\!=\!f(q)$. These relations also hold if we instead chose ${s}\!\in\!\mathcal{F}^{*}$ and $r\!\in\!\mathcal{F}^{*}$ in the range space, and used ${p}\!=\!f^{*}({s})$ and $q\!=\!f^{*}(r)$. In general (24) and (25) are not equal.

The KL divergence between $p$ and $q$ in two directions can be expressed as,

for some $a=(1-\alpha){s}+\alpha r$, ($0\leq\alpha\leq{\textstyle\frac{1}{2}}$), $b=(1-\beta)r+\beta{s}$, ($0\leq\beta\leq{\textstyle\frac{1}{2}}$).

for some $a=(1-\alpha){s}+\alpha r$, ($0\leq\alpha\leq{\textstyle\frac{1}{2}}$), $b=(1-\beta)r+\beta{s}$, ($0\leq\beta\leq{\textstyle\frac{1}{2}}$). Note that by the specific form (29) we also have

Therefore, by combining (33) and (34) with (30) we obtain

Equality (27) then follows by applying (26) to (35).

Next, to prove the inequality in (28), let $\delta={s}-r$ and observe that

since $\|f^{*}_{\tau}(a)-f^{*}_{\tau}(b)\|_{\infty}\leq 2$ and $\|f^{*}_{\tau}(b)\|_{2}^{2}\leq\|f^{*}_{\tau}(b)\|_{1}^{2}\leq 1$. The result follows by applying (26) to (39). ∎