We propose SEARNN, a novel training algorithm for recurrent neural networks (RNNs) inspired by the "learning to search" (L2S) approach to structured prediction. RNNs have been widely successful in structured prediction applications such as machine translation or parsing, and are commonly trained using maximum likelihood estimation (MLE). Unfortunately, this training loss is not always an appropriate surrogate for the test error: by only maximizing the ground truth probability, it fails to exploit the wealth of information offered by structured losses. Further, it introduces discrepancies between training and predicting (such as exposure bias) that may hurt test performance. Instead, SEARNN leverages test-alike search space exploration to introduce global-local losses that are closer to the test error. We first demonstrate improved performance over MLE on two different tasks: OCR and spelling correction. Then, we propose a subsampling strategy to enable SEARNN to scale to large vocabulary sizes. This allows us to validate the benefits of our approach on a machine translation task. Recurrent neural networks (RNNs) have been quite successful in structured prediction applications such as machine translation BID27 , parsing BID1 or caption generation . These models use the same repeated cell (or unit) to output a sequence of tokens one by one. As each prediction takes into account all previous predictions, this cell learns to output the next token conditioned on the previous ones. The standard training loss for RNNs is derived from maximum likelihood estimation (MLE): we consider that the cell outputs a probability distribution at each step in the sequence, and we seek to maximize the probability of the ground truth.Unfortunately, this training loss is not a particularly close surrogate to the various test errors we want to minimize. A striking example of discrepancy is that the MLE loss is close to 0/1: it makes no distinction between candidates that are close or far away from the ground truth (with respect to the structured test error), thus failing to exploit valuable information. Another example of train/test discrepancy is called exposure or exploration bias BID22 : in traditional MLE training the cell learns the conditional probability of the next token, based on the previous ground truth tokens -this is often referred to as teacher forcing. However, at test time the model does not have access to the ground truth, and thus feeds its own previous predictions to its next cell for prediction instead.Improving RNN training thus appears as a relevant endeavor, which has received much attention recently. In particular, ideas coming from reinforcement learning (RL), such as the REINFORCE and ACTOR-CRITIC algorithms BID22 BID0 , have been adapted to derive training losses that are more closely related to the test error that we actually want to minimize.In order to address the issues of MLE training, we propose instead to use ideas from the structured prediction field, in particular from the "learning to search" (L2S) approach introduced by BID8 and later refined by BID24 and BID5 among others.Contributions. In Section 2, we review the limitations of MLE training for RNNs in details. We also clarify some related claims made in the recent literature. In Section 3, we make explicit the strong links between RNNs and the L2S approach. In Section 4, we present SEARNN, a novel training algorithm for RNNs, using ideas from L2S to derive a global-local loss that is much closer to the test error than MLE. We demonstrate that this novel approach leads to significant improvements on two difficult structured prediction tasks, including a spelling correction problem recently introduced in BID0 . As this algorithm is quite costly, we investigate scaling solutions in Section 5. We explore a subsampling strategy that allows us to considerably reduce training times, while maintaining improved performance compared to MLE. We apply this new algorithm to machine translation and report significant improvements in Section 6. Finally, we contrast our novel approach to the related L2S and RL-inspired methods in Section 7. We now contrast SEARNN to several related algorithms, including traditional L2S approaches (which are not adapted to RNN training), and RNN training methods inspired by L2S and RL.Traditional L2S approaches. Although SEARNN is heavily inspired by SEARN, it is actually closer to LOLS BID5 , another L2S algorithm. As LOLS, SEARNN is a meta-algorithm where roll-in/roll-out strategies are customizable (we explored most combinations in our experiments). Our findings are in agreement with those of BID5 : we advocate using the same combination, that is, a learned roll-in and a mixed roll-out. The one exception to this rule of thumb is when the associated reduced problem is too hard (as seems to be the case for machine translation), in which case we recommend switching to a reference roll-in.Moreover, as noted in Section 4, SEARNN adapts the optimization process of LOLS (the one difference being that our method is stochastic rather than online): each intermediate dataset is only used for a single gradient step. This means the policy interpolation is of a different nature than in SEARN where intermediate datasets are optimized for fully and the resulting policy is mixed with the previous one.However, despite the similarities we have just underlined, SEARNN presents significant differences from these traditional L2S algorithms. First off, and most importantly, SEARNN is a full integration of the L2S ideas to RNN training, whereas previous methods cannot be used for this purpose directly. Second, in order to achieve this adaptation we had to modify several design choices, including:• the intermediate dataset construction, which significantly differs from traditional L2S; 3• the careful choice of a classifier (those used in the L2S literature do not fit RNNs well);• the design of tailored surrogate loss functions that leverage cost information while being easy to optimize in RNNs.L2S-inspired approaches. Several other papers have tried using L2S-like ideas for better RNN training, starting with which introduces "scheduled sampling" to avoid the exposure bias problem. The idea is to start with teacher forcing and to gradually use more and more model predictions instead of ground truth tokens during training. This is akin to a mixed roll-in -an idea which also appears in BID8 ).Wiseman & Rush (2016, BSO) adapt one of the early variants of the L2S framework: the "Learning A Search Optimization" approach of Daumé & Marcu (2005, LASO) to train RNNs. However LASO is quite different from the more modern SEARN family of algorithms that we focus on: it does not include either local classifiers or roll-outs, and has much weaker theoretical guarantees. Additionally , BSO's training loss is defined by violations in the beam-search procedure, yielding a very different algorithm from SEARNN. Furthermore , BSO requires being able to compute a meaningful loss on partial sequences, and thus does not handle general structured losses unlike SEARNN. Finally, its ad hoc surrogate objective provides very sparse sequence-level training signal, as mentioned by their authors, thus requiring warm-start. BID1 use a loss that is similar to LL for parsing, a specific task where cost-to-go are essentially free. This property is also a requirement for BID26 , in which new gradient procedures are introduced to incorporate neural classifiers in the AGGREVATE BID24 variant of L2S. 4 In contrast, SEARNN can be used on tasks without a free cost-to-go oracle.RL-inspired approaches. In structured prediction tasks, we have access to ground truth trajectories, i.e. a lot more information than in traditional RL. One major direction of research has been to adapt RL techniques to leverage this additional information. The main idea is to try to optimize the expectation of the test error directly (under the stochastic policy parameterized by the RNN): DISPLAYFORM0 Since we are taking an expectation over all possible structured outputs, the only term that depends on the parameters is the probability term (the tokens in the error term are fixed). This allows this loss function to support non-differentiable test errors, which is a key advantage. Of course, actually computing the expectation over an exponential number of possibilities is computationally intractable.To circumvent this issue, BID25 subsample trajectories according to the learned policy, while BID22 ; BID23 use the REINFORCE algorithm, which essentially approximates the expectation with a single trajectory sample. BID0 adapt the ACTOR-CRITIC algorithm, where a second critic network is trained to approximate the expectation.While all these approaches report significant improvement on various tasks, one trait they share is that they only work when initialized from a good pre-trained model. This phenomenon is often explained by the sparsity of the information contained in "sequence-level" losses. Indeed, in the case of REINFORCE, no distinction is made between the tokens that form a sequence: depending on whether the sampled trajectory is above a global baseline, all tokens are pushed up or down by the gradient update. This means good tokens are sometimes penalized and bad tokens rewarded.In contrast, SEARNN uses "global-local" losses, with a local loss attached to each step, which contains global information since the costs are computed on full sequences. To do so, we have to "sample" more trajectories through our roll-in/roll-outs. As a result, SEARNN does not require warm-starting to achieve good experimental performance. This distinction is quite relevant, because warm-starting means initializing in a specific region of parameter space which may be hard to escape. Exploration is less constrained when starting from scratch, leading to potentially larger gains over MLE.RL-based methods often involve optimizing additional models (baselines for REINFORCE and the critic for ACTOR-CRITIC), introducing more complexity (e.g. target networks). SEARNN does not.Finally, while maximizing the expected reward allows the RL approaches to use gradient descent even when the test error is not differentiable, it introduces another discrepancy between training and testing. Indeed, at test time, one does not decode by sampling from the stochastic policy. Instead, one selects the "best" sequence (according to a search algorithm , e.g. greedy or beam search). SEARNN avoids this averse effect by computing costs using deterministic roll-outs -the same decoding technique as the one used at test time -so that its loss is even closer to the test loss. The associated price is that we approximate the gradient by fixing the costs, although they do depend on the parameters.RAML BID19 ) is another RL-inspired approach. Though quite different from the previous papers we have cited, it is also related to SEARNN. Here, in order to mitigate the 0/1 aspect of MLE training, the authors introduce noise in the target outputs at each iteration. The amount of random noise is determined according to the associated reward (target outputs with a lot of noise obtain lower rewards and are thus less sampled). This idea is linked to the label smoothing technique BID28 , where the target distribution at each step is the addition of a Dirac (the usual MLE target) and a uniform distribution. In this sense, when using the KL loss SEARNN can be viewed as doing learned label smoothing , where we compute the target distribution from the intermediate costs rather than arbitrarily adding the uniform distribution.Conclusion and future work. We have described SEARNN, a novel algorithm that uses core ideas from the learning to search framework in order to alleviate the known limitations of MLE training for RNNs. By leveraging structured cost information obtained through strategic exploration, we define global-local losses. These losses provide a global feedback related to the structured task at hand, distributed locally within the cells of the RNN. This alternative procedure allows us to train RNNs from scratch and to outperform MLE on three challenging structured prediction tasks. Finally we have proposed efficient scaling techniques that allow us to apply SEARNN on structured tasks for which the output vocabulary is very large, such as neural machine translation.The L2S literature provides several promising directions for further research. Adapting "bandit" L2S alternatives BID5 would allow us to apply SEARNN to tasks where only a single trajectory may be observed at any given point (so trying every possible token is not possible). Focused costing BID12 ) -a mixed roll-out policy where a fixed number of learned steps are taken before resorting to the reference policy -could help us lift the quadratic dependency of SEARNN on the sequence length. Finally, targeted sampling BID12 ) -a smart sampling strategy that prioritizes cells where the model is uncertain of what to do -could enable more efficient exploration for large-scale tasks.Let us consider the case where we perform the roll-in up until the t th cell. In order to be able to perform roll-outs from that t th cell, a hidden state is needed. If we used a reference policy roll-in, this state is obtained by running the RNN until the t th cell by using the teacher forcing strategy, i.e. by conditioning the outputs on the ground truth. Finally, SEARNN also needs to know what the predictions for the full sequence were in order to compute the costs . When the reference roll-in is used, we obtain the predictions up until the t th cell by simply copying the ground truth. Hence, we discard the outputs of the RNN that are before the t th cell.
We introduce SeaRNN, a novel algorithm for RNN training, inspired by the learning to search approach to structured prediction, in order to avoid the limitations of MLE training.
{"src": "scitldr-AIC_train", "paper_id": "HkUR_y-RZ"}