summaries: This work presented an improvement of grid search algorithm for certain hyperparameters in deep neural nets training. These hyperparameters, such as learning rate and drop out, have "temperature" like meaning to control the noise injected in the training. With this analogy, the author proposed to use the idea of parallel tempering in statistical physics to allow exchange these hyperparameters during the training. Their empirical results showed this improves standard grid search.

summaries: The paper proposes a new paradigm to perform hyperparameter search by proposing a way to jointly optimize over the hyperparameter space and the parameter space as opposed to the traditional way to performing these in separation (with the hyperparameter search invoking the parameter optimization) The paper’s main claim is that this allows the seach to follow non-local paths in the joint space. The main methodology proposed in the paper is inspired by the idea of parallel tempering from physics. The paper proposes to view parameter learning under a certain hyperparameter as running a langevin chain at a particular temperature. This is motivated by considering common hyperparameters as batch size, dropout rate or learning rate as inducing a specific level of noise to the training process, the variance of which is analogous to the inverse temperature in Langevin diffusion.

abstractText: Hyperparameter optimization is both a practical issue and an interesting theoretical problem in training of deep architectures. Despite many recent advances the most commonly used methods almost universally involve training multiple and decoupled copies of the model, in effect sampling the hyperparameter space. We show that at a negligible additional computational cost, results can be improved by sampling nonlocal paths instead of points in hyperparameter space. To this end we interpret hyperparameters as controlling the level of correlated noise in training, which can be mapped to an effective temperature. The usually independent instances of the model are coupled and allowed to exchange their hyperparameters throughout the training using the well established parallel tempering technique of statistical physics. Each simulation corresponds then to a unique path, or history, in the joint hyperparameter/model-parameter space. We provide empirical tests of our method, in particular for dropout and learning rate optimization. We observed faster training and improved resistance to overfitting and showed a systematic decrease in the absolute validation error, improving over benchmark results.

title: The effects of adding noise during backpropagation training on a generalization performance

venue: Neural computation,

authors:
James S. Bergstra
Rémi Bardenet
Yoshua Bengio
Balázs Kégl

title: Algorithms for hyperparameter optimization

venue: Advances in Neural Information Processing Systems

title: Training with noise is equivalent to tikhonov regularization

venue: Neural Computation,

authors:
Anna Choromanska
MIkael Henaff
Michael Mathieu
Gerard Ben Arous
Yann LeCun

title: The Loss Surfaces of Multilayer Networks

venue: Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics,

authors:
Gregory Cohen
Saeed Afshar
Jonathan Tapson
André van Schaik

title: Emnist: an extension of mnist to handwritten letters

venue: arXiv preprint arXiv:1702.05373,

authors:
Guillaume Desjardins
Aaron Courville
Yoshua Bengio
Pascal Vincent
Olivier Delalleau

title: Tempered markov chain monte carlo for training of restricted boltzmann machines

venue: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,

authors:
David J. Earl
Michael W. Deem

title: Parallel tempering: Theory, applications, and new perspectives

venue: Phys. Chem. Chem. Phys.,

authors:
Hiroaki Fukunishi
Osamu Watanabe
Shoji Takada

title: On the hamiltonian replica exchange method for efficient sampling of biomolecular systems: Application to protein structure prediction

venue: The Journal of Chemical Physics,

authors:
Geoffrey E. Hinton
Drew van Camp

title: Keeping the neural networks simple by minimizing the description length of the weights

venue: In Proceedings of the Sixth Annual Conference on Computational Learning Theory,

authors:
Geoffrey E. Hinton
Nitish Srivastava
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Improving neural networks by preventing co-adaptation of feature detectors

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Simplifying neural nets by discovering flat minima

authors:
Max Jaderberg
Valentin Dalibard
Simon Osindero
Wojciech M. Czarnecki
Jeff Donahue
Ali Razavi
Oriol Vinyals
Tim Green
Iain Dunning
Karen Simonyan
Chrisantha Fernando
Koray Kavukcuoglu

title: Population based training of neural networks

authors:
Helmut G Katzgraber
Simon Trebst
David A Huse
Matthias Troyer

title: Feedback-optimized parallel tempering monte carlo

venue: Journal of Statistical Mechanics: Theory and Experiment,

authors:
S. Kirkpatrick
C.D. Gelatt
M.P. Vecchi

title: Optimization by simulated annealing

venue: doi: 10.1126/science.220.4598.671. URL https: //science.sciencemag.org/content/220/4598/671

authors:
Alex Krizhevsky
Geoffrey Hinton

authors:
Arvind Neelakantan
Luke Vilnis
Quoc V. Le
Ilya Sutskever
Lukasz Kaiser
Karol Kurach
James Martens

title: Adding Gradient Noise Improves Learning for Very Deep Networks

venue: arXiv e-prints, art

authors:
Shibani Santurkar
Dimitris Tsipras
Andrew Ilyas
Aleksander Madry

title: How does batch normalization help optimization

authors:
H.S. Seung
H. Sompolinsky
N. Tishby

title: Statistical mechanics of learning from examples

venue: Phys. Rev. A,

authors:
Jocelyn Sietsma
Robert J.F. Dow

title: Creating artificial neural networks that generalize

venue: Neural Networks,

authors:
Jasper Snoek
Hugo Larochelle
Ryan P. Adams

title: Practical bayesian optimization of machine learning algorithms

venue: In Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 2,

authors:
Yuji Sugita
Akio Kitao
Yuko Okamoto

title: Multidimensional replica-exchange method for freeenergy calculations

authors:
Robert H. Swendsen
Jian-Sheng Wang

title: Replica monte carlo simulation of spin-glasses

venue: Phys. Rev. Lett.,

authors:
Simon Trebst
Matthias Troyer
Ulrich H.E. Hansmann

title: Optimized parallel tempering simulations of proteins

authors:
Qiliang Yan
Juan J. de Pablo

title: Hyper-parallel tempering monte carlo: Application to the lennardjones fluid and the restricted primitive model

authors:
Yao Zhang
Andrew M. Saxe
Madhu S. Advani
Alpha A. Lee

title: Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning

venue: Molecular Physics,

title: In the current implementation we used a fixed acceptance parameter to focus the discussion on the main idea of replica exchange of hyperparameters. Table 4: Comparison study of dependance of average acceptance rate across all the replicas on difference values of constant C. C

heading: 1 INTRODUCTION

text:
The remarkable improvement in performance of machine learning models has been paid for with an increased model complexity. Part of this complexity is directly related to architectural choices, such as model topology and depth or increased overall number of parameters (weights), but an increasingly important aspect, from both theoretical and practical standpoint, is the growth of the number of hyperparameters. Though the classification may seem fluid, with structural features such as the number of layers being treated as a hyperparameters as well, the difference is laid bare by the distinct nature of training, which involves a double loop of optimizations. The inner loop finds the best model weights – with hyperparameters held fixed to some arbitrary values – using the performance on the training dataset, while the outer loop is responsible for finding the optimal value of hyperparameters to ensure a robust performance on new data, i.e. generalization. A separate dataset is used for this key task. Hyperparameters thus optimized may include structural features, regularization constants, and even dynamical characteristics of the training algorithm.
The practical importance of hyperparameters cannot be underestimated: the very same architecture may deliver state-of-the-art or mediocre results, depending on the choices made. Simultaneously as the number of hyperparameters grows, the search space becomes high-dimensional and thus necessitates proper hyperparameter optimization (HO) procedures, which go beyond rule-of-thumb choices. This is additionally complicated by the fact that computational resources and time are usually limited. A number of HO approaches have been developed (Bergstra et al., 2011); the simplest ones involve grid- or random searches, but their main weakness is poor scaling and failure to reuse information obtained from previous parameter choices. A broad family of methods addressing the latter issue arise in the Bayesian framework: here the the assignment of new hyperparameter values to be evaluated is informed by the performance of the model with the previous assignments (Snoek et al., 2012). The high computational cost of evaluation inspires additional strategies, for instance bandit methods, to leverage cheaper but cruder results obtained with partial datasets. All of the above HO strategies, however, share a key characteristic: optimization of hyperparameters is decoupled from that of the weights, and the procedures amount to a more or less clever sampling of the points in hyperparameter space, using the validation dataset only. A family of genetic HO algorithms overcome this issue by optimization in both weights and hyperparameter space, however, in
this case, in a greedy way (see for example Jaderberg et al. (2017)). They cannot be thus guaranteed to explore space in an unbiased way, and the results may explicitly depend on initial conditions .
Here, we propose a radically different strategy: that of coupling the usually independent copies of the model at different hyperparameter values during the training. The instances of the model are allowed to exchange their hyperparametes as the optimization of the weights on the training dataset progresses, in effect tracing out a highly nonlocal trajectory in the product of hyperparameter and weight spaces. The final trained model cannot thus be thought of as being characterized by a particular point value of the hyperparameters, but rather by a path or history. The exchange procedure is based on the physical technique of parallel tempering (Swendsen & Wang, 1986), which itself depends on a mapping of the hyperparameter values to an effective “temperature” of the model. We demonstrate empirically, that this HO approach – which leverages also the training dataset – has a number of desirable properties: it results in models more resilient to overfitting, achieving smaller overall errors, and achieving them faster. The method is naturally parallelizable and the computational cost overhead over usual grid searches is negligible.
The goal of this work is then twofold: first, to provide (or, in some instances, recapitulate) a unifying and intuitive physical perspective on various types of hyperparameters, which can be interpreted as setting the level of “noise” during the training of the model. This, in turn, defines an effective parameter - similar in spirit to temperature - controlling the smoothness of the generalization function. Second, and much more important in applications, is to show that this perspective allows to move beyond the usual paradigm of two decoupled weight/hyperparameter optimizations in a well-motivated and controlled fashion, and ultimately to train more robust models.
This paper is organized as follows: in section 2 we review the interpretation of hyperparameters as controls of noise, and the mapping to an effective ”temperature”. In section 3 we introduce the main concepts of our path-based model optimization. In section 4 we show numerical tests of the approach on neural nets trained on EMNIST and CIFAR-10 datasets. The discussed examples of hyperparameters include the learning rate and drop-out rate, among others. Finally, in section 5 we discuss the implications, as well as potential generalizations of the method.

heading: 2 HYPERPARAMETERS AS CONTROLS OF SMOOTHNESS OF POTENTIAL LANDSCAPE

text:
Training of modern machine learning models, in particular of deep neural networks (DNNs), is a complex non-convex optimisation problem of minimizing the total objective function (otherwise called loss or energy):
L(x,W) = 1 N N∑ i=1 li(xi,W), (1)
where li(xi,W) captures deviations of the predictions of the model, parametrized by weights W, for the i-th data point xi in the training set of total size N . The standard choice of the optimisation method for this problem remains the Stochastic Gradient Descent (SGD) algorithm
Wt+1 = Wt − γ |NB | ∑ i∈NB ∇Wli(xi,Wt) (2)
with a step size γ and the gradient computed only on a batch NB of the training set.
It is well established, that various forms of direct noise injection, whether to the inputs, weights or gradients, aid generalization performance (Sietsma & Dow, 1991; Neelakantan et al., 2015). From the theory point of view it has been shown that the effect of such methods is analogous – though not identical – to introducing particular types of regularization (Bishop, 1995; An, 1996) smoothing the cost function. Furthermore, an often invoked intuition is that noise allows the algorithm to escape narrow minima of the cost function defined by the training data, thereby preventing overfitting. This is also true for non-white noise introduced “indirectly”, such as the one generated by the minibatches in Eq.2. Aided by the results suggesting poor generalization for “deep” (Choromanska et al., 2015), and, conversely, good generalization for “flat” minima of the loss function (Hinton & van Camp, 1993; Hochreiter & Schmidhuber, 1995), it was postulated in Zhang et al. (2018) that strong performance of SGD is, in fact, due to the correlated nature of the induced batch noise.
In what follows, we will greatly benefit from an intuitive – if not always rigorous – picture relating various kinds of noise to an effective parameter controlling smoothness of the potential landscape, similar in spirit to temperature. Common hyperparameters, such as the learning rate, dropout or batch size, can be treated on the same footing, as we now demonstrate.
Let us begin with the prototypical case of added Langevin noise, for which the temperature analogy is exact (Seung et al., 1992): the gradients are corrupted by white noise ξ with a variance 〈ξi(t)ξj(t′)〉 = 2Tδijδtt′ . The naive GD can then be viewed as a diffusion process of particle in a complex potential landscape, with the weight updates a discretized version of the continuum equation:
∂W
∂t = −∇WL+ ξ(t). (3)
At long-times Eq. 3 converges to a Gibbs probability distribution, from which weights W can be directly sampled:
P (W) = 1
Z exp (−βL (W)) . (4)
The inverse temperature β = 1/T is not arbitrary, but rather is defined by the variance of the noise ξ. Furthermore, the multiplicative prefactor β in Eq. 4 controls the overall scale of variation of the potential landscape. Strong noise, corresponding to large variance, and therefore high temperature T, results in small β which “flattens” the landscape of L (W). Conversely, weak noise results in large β, amplifying potential differences. This is the central idea behind changing temperature in the familiar simulated annealing method (Kirkpatrick et al., 1983). An alternative way of phrasing the above is that the increased variance of the noise does not allow the finer details the potential landscape to be explored by the dynamics, effectively smoothing it. The crucial observation is that the latter perspective extends also to cases where the noise is not white. Though, strictly speaking, the variance of the noise is not the temperature anymore, it still performs an analogous function: it effectively controls the roughness/smoothness of the landscape. An immediate consequence is that higher variance facilitates diffusion of the model in such high-dimensional space, and improves ergodicity (see Fig. 1).
As an illustration, we now consider common examples of hyperparameters from this perspective, and examine their influence on diffusion curves. For the learning rate γ, its magnitude is directly related to the size of the time step in the discretization of the Langevin equation, and by dimensional analysis it is analogous to increasing the noise variance (thus temperature) by a factor of γ. In the case of SGD dynamics Eq. 2 the noise variance can be computed explicitly (Zhang et al., 2018). Even though the noise is highly correlated, i.e. not thermal, the variance scales overall as inverse batch size: |Nb|−1, and thus smaller batch size smoothens the potential. Similarly, dropout regularization has the effect of increasing the variance of neural outputs at training by a factor of inverse dropout retention rate p−1 (Hinton et al., 2012), therefore amplifying noise and improving diffusion, as seen in Fig. 1. The case of L2 regularization is different: an increased L2 naturally diminishes the magnitude of the potential landscape variations, and so the initial diffusion is faster (see Fig. 1), however at later times the diffusion is effectively suppressed; the plateau value reached is, naturally, the lower the stronger the L2 regularization. Since, therefore, the models do not diffuse at different rates, L2 does not satisfy the basic requirements of our procedure, and we do not expect systematic improvements for this hyperparameter. On the other hand, for parameters relating to direct noise injection (for instance to gradients or weights), the relationship of large magnitude to
high “temperature” is natural, as described above, and their smoothing effect has been noted in the literature An (1996).
Since generically there are many hyperparameters, and results or intuitions such as above may not be readily available, it is imperative to be able to systematically identify whether they are related to landscape smoothness. This is, fortunately, possible. The functional significance of the notion of smoothness lies precisely in determining the diffusion properties of the random walk, therefore it is natural to test for smoothing properties by performing a diffusion experiment. To wit, sensitivity of the weight diffusion curves – obtained from SGD training runs – to the value of hyperparameter in question implies relation to smoothness. To exemplify this we consider Batch Normalization (BN). By studying Lipschitz properties Santurkar et al. (2018) ultimately confirmed it is related to effective landscape smoothing. Alternatively,
comparing training with and without BN, it can be immediately shown to improve weight diffusion (see Fig.2).
Training the model with different hyperparameters can thus be intuitively thought of as minimizing the objective at different intensities of noise, or, equivalently, in effective landscapes of varying degree of smoothness. We will now use this insight to construct a new nonlocal hyperparameter optimization procedure.

heading: 3 REPLICA EXCHANGE OF HYPERPARAMETERS

text:
Algorithm 1 Training with replica exchange INPUT: Number of replicas M , Inverse ”temperature” (hyperparameters) β = (β1, β2, . . . , βM )
Number of steps for initialization ∆Ni Number of SGD steps between exchanges ∆Ne Exchange normalization parameter C Number of steps T
OUTPUT: Weight configurations W = (W1,W2, . . . ,WM) of the replicas, 1: Initialization: ∀k ∈M , initialize weights Wk for each replica and set t = 0. 2: ∀k ∈M , perform SGD for ∆Ni steps. Update t← t+ 1 at each step. 3: Repeat: 4: ∀k ∈M , perform SGD for ∆Ne steps to update Wk. Set t← t+ 1 at each step. 5: Let Lt = (L (Wt1) ,L (Wt2) , ...,L (Wtk) be validation losses at time t. 6: Randomly select a pair (m,n) of replicas with adjacent temperatures. 7: if ∆ = C (βm − βn) [L (Wm)− L (Wn)] ≤ 0 then 8: swap βm and βn 9: else 10: swap βm and βn with probability exp (−∆). 11: Finish if t > T .
The core of our approach is to endow the model with the ability to change hyperparameters during training, and hence to optimize the model over a subset of paths in the combined weight and hyperparameter space, as opposed to being confined to hyperplanes determined by a fixed value of the hyperparameter. In the previous section we have noted that varying typical hyperparameters defines a family of optimization problems of monotonically changing smoothness of the effective landscape, and thus of ergodicity properties and complexity. This family is labelled by an effective “temperature” determined by the variance of the noise induced in the training by particular hyperparameter choices.
Inspired by similar problems in statistical physics we use the parallel tempering (replica exchange) method (Swendsen & Wang, 1986). In this procedure, multiple Markov Chain Monte-Carlo
(MCMC) simulations, or replicas, are run in parallel at different temperatures, which define the levels of uncertainty in the objective function, i.e. the energy. The temperatures are arranged in ascending manner forming a ladder on which the states of the replicas are swapped between neighboring values with Metropolis-Hastings acceptance criteria, ensuring that the whole setup satisfies detailed balance not only for each chain individually, but also between the chains (see discussion below). The lower temperature chains’ ergodicity is thus radically improved by the possibility of temporarily performing MC moves at higher temperatures, where the landscape looks flatter. Note that this results in a non-greedy and highly nonlocal exploration. Indeed, parallel tempering is efficient in systems with broken ergodicity – the usual case for complex energy landscapes, where configuration space can effectively become partitioned into separate regions with low probability for inter-region transitions (for a concise review see Earl & Deem (2005)). Applications beyond the original spin-glass simulations include protein folding (Fukunishi et al., 2002) and, in machine learning, training of Boltzmann machines (Desjardins et al., 2010).
In our algorithm, the MCMC chains for individual replicas are replaced with multiple instances of the standard SGD dynamics distinguished by hyperparameter values, which is a more efficient way to approach Langevin-like equation 3 for systems with large number of long-range correlated parameters. We assume, using the noise analogy discussed in the previous section, that the weight configurations W of the replicas follow a Gibbs distribution Pm(W) characterized by the effective inverse ”temperature” βm, determined by the value of the hyperparameter:
Pm(W) = 1
Zm exp (−βmL (W)) , (5)
with Zm the partition function. The total system distribution is then a product over the M replicas:
Pfull = M∏ i Pi(Wi) (6)
The transition probability P (W, βm;W′, βn) of swapping configurations W′ and W between two replicas m and n should satisfy the detailed balance condition in the full system, which implies:
P (W, βm;W′, βn) P (W′, βn;W, βm) = exp (−∆) , (7)
where we used Gibbsianity and where: ∆ = (βm − βn) [L (W′)− L (W)] (8)
Note that the global detailed balance condition guarantees that in the long-time limit the joint probability distribution Eq. 6 will be sampled faithfully. In particular, no dependence on initial state of the weights will survive. Following the standard Metropolis-Hastings scheme, the exchange occurs with analytically computable acceptance probability:
P (W, βm;W′, βn) = 1 for ∆ ≤ 0, (9) = exp (−∆) for ∆ > 0.
The resulting Algorithm 1 is described in the table above. It accepts M replicas of the system, a vector β of inverse temperatures, number of initialization and SGD steps between exchanges. Each one of the M realisations of the system is first run for ∆Ne steps, until they achieve their relative equilibrium. Subsequently, exchanges are proposed every ∆Ne steps. The constant C introduced in the acceptance ratio is responsible for normalization of the exponential argument and may be required when the values of hyper-parameter are very low, or too high (see below).
An important practical issue is the selection of replica temperatures and spacing, so that exchange proposals are accepted with a high probability. The theoretical answer depends on the properties of the energy landscape and fluctuations in the system; the basic idea is to ensure that energy histograms for neighbouring replicas have sufficiently large overlap. To this end, a common choice for temperature ladder is a geometric progression. In what follows, for simplicity, we use an equal spacing between replicas and instead scale β with a tunable parameter C to control the exchange rate, which requires calibration. For such tuning, running of preliminary realisations of the system prior to a parallel tempering optimisation may be needed to approximate energy histograms. Here we run short training without exchanges to tune the acceptance ratio constant C, or to fine-tune the temperatures selection. It is also worth noting that the acceptance ratio relates to the number of trainable parameters in the model. Increase in the number of parameters allows for more accessible states in parameter space, and induces smaller acceptance ratio.
Fully Connected 10 softmax
Another input argument is the swap step; here an important observation is that when parallel tempering is used for MCMC sampling purposes, it is necessary to satisfy the detailed balance condition. For too small a step the system may not equilibrate sufficiently fast, and hence will not obey the Markov property.

heading: 4 EMPIRICAL RESULTS

text:
To validate the proposed approach we conducted a series of experiments: first, using small LeNet-like models, we investigated the effects of various types of hyperparameter-induced “noise” on weight diffusion and tested the associated idea of hyperparameter replica exchange. We then moved to deep ResNet architectures He et al. (2016) to verify applicability of our parallel-tempering-based algorithm to large scale models.
The expriments were performed on EMNIST-letters (Cohen et al. (2017)) and CIFAR-10 (Krizhevsky & Hinton (2009)) datasets. EMNIST-letters consists of 124800 training images and 20800 testing images of shape 28 × 28 pixels with 26 classes. CIFAR-10 has 50000 training images and 10000 testing images with 10 classes. Each image has shape 32 × 32 pixels and 3 channels. The validation splits for both datasets were generated by random sampling of a training dataset taking 10% out. All models were trained with a mini-batch size of 128.
The LeNet-like models are summarized in tables 1 and 2. For EMNIST we apply zero-padding to 32 × 32 pixels before the inputs are fed to the network. Each average pooling layer is multiplied by a learnable coefficient and added bias (one per feature map). The neurons between the average pooling layer and convolutional layer are fully connected (every feature map from average pooling
is connected to every convolutional feature map), as opposed to the original LeNet architecture from LeCun et al. (1998). In the output layer each neuron outputs the square of the Euclidean distance between its input vector and its weight vector. Afterwards we apply normalized exponential function (RBF activation). For CIFAR-10 we used Max Pooling instead of Average Pooling and softmax activation on the output. Every simulation starts with a learning rate of 0.1. The learning rate for EMNIST is annealed after 62K steps, and for CIFAR-10 after 25K steps. When considering dropout as the hyperparameter being varied, the exchanges are introduced after 25K and 10K steps for EMNIST and CIFAR-10, respectively. For the simulation where the learning rate itself is being varied, each replica is annealed to a different value of the learning rate, and exchanges start being proposed right after annealing.
The results for LeNet-like models are presented in Fig. 3. Replicas differing by a “temperature” defined by Dropout and learning rate are generated, and the model performance (in terms of classification error) of the best independent replica, corresponding to a fixed hyperparameter value, is compared against a parallel tempering solution, where replica swaps are introduced. In all of the cases, for both datasets, the best parallel tempered path achieves a significantly lower error rate. We have also observed increased resilience to overfitting in our small-scale simulations, though this aspect requires more careful study. It is worth noting, that for the EMNIST task an error rate comparable to the best untempered results is achieved in a much smaller number of training epochs. Overall, the training is at least as fast as for the independent simulations.
In order to showcase the flexibility of the algorithm, and its potential for generating additional improvements for already efficient and optimized models, we benchmark the approach on the residual architectures for CIFAR-10, where we follow He et al. (2016). Specifically, images are normalized by subtracting per-pixel mean and augmented via a number of transformations: the image is left-right-flipped with probability 0.5 and 4 pixels are zero-padded on each side, with a following random 32 × 32 crop. We use weight decay of 0.0001 and momentum of 0.9. We apply Batch Normalization, as in the original paper, and compare exchangeable learning rate to a fixed one after the initial learning rate annealing. The training begins with learning rate 0.1, annealed only once at step 32K; the total amount of training steps is 64K, as in He et al. (2016).
In Fig. 4 test error curves for ResNet20 and ResNet44 are presented, along with a visualisation of hyperparameter exchanges between replicas in a representative simulation. Introduction of the exchanges consistently reduces the overall minimal testing error for both architectures. With eight replicas we obtain an improvement of 1.04% for ResNet20 and 1.66% for ResNet44 (see table 3 for mean and standard deviation values). We expect larger improvements for larger number of replicas. Note that the hyperparameter value corresponding to the the best individually trained model (found by grid-search), is included in the parameter ladder for the PT simulation together with a small number of “suboptimal” values. The PT solution improves on all of them, by leveraging the replicas to explore the parameter space in a nonlocal fashion. This is seen in the non-trivial trajectories in hyperparameter space taken by all replicas as the training of their weights proceeds, in particular the trajectory of the ultimately best one.

heading: 5 CONCLUSIONS AND DISCUSSION

text:
We introduced a new training approach to improve model optimization, by coupling previously independent grid search simulations at different hyperparameter values using the replica exchange technique. The method, which can be thought of as optimizing the model over non-monotonic and nonlocal paths in the joint hyperparameter/weight space, is very general: it can be applied to any hyperparameter which admits interpretation as a temperature-like quantity, in the very weak sense of facilitating weight diffusion during training. This diffusion test is, in fact, a simple experiment which can be performed at little cost to establish, whether any given parameter is related to landscape smoothness. We show that this is the case for Dropout, learning rate, but also Batch Normalization. The method is easily parallelizable, and similar in cost to standard grid search.
Experiments performed on LeNet (with CIFAR and EMNIST datasets) and ResNet (with CIFAR) architectures, showed consistently lower test error. In particular, we obtain improvement over the benchmark results for ResNet20 and ResNet44 on the CIFAR dataset.
A number of further improvements are possible. Practically, the most important concerns the automation of hyperparameter range selection, and the subsequent replica temperature ladder choice to optimize acceptances, which can potentially also reduce the test error. Conceptually, the idea can also be generalized to the case of multiple parameters controlling the smoothness of the energy landscape, which are not necessarily temperature-like Fukunishi et al. (2002). In this setup, multidimensional exchanges between replicas with different values of distinct hyperparameters are permitted, using the hyper-parallel tempering method Yan & de Pablo (1999); Sugita et al. (2000), allowing for more complex paths. These topics are the subject of an ongoing work.

heading: A APPENDIX

text:
In Fig. 5 the dynamics of the training algorithm across multiple replicas is shown. We emphasize that the dynamics for any fixed value of a hyperparameter is performed using standard SGD dynamics, and not Monte Carlo. Moreover, SGD can be replaced by e.g. Adam optimization, as MC exchanges are only performed between replicas, within which dynamics can be arbitrary.
For conceptual simplicity we have assumed a single parameter C controlling the acceptance ratio of swap moves between all the replicas in our proof-of-principle implementation. The performance of the algorithm is sensitive to the value of C. In the table 4 we provide a comparison of average acceptance rates for different values of C. In fact, for optimal performance acceptances between each pair of neighbouring replicas should be adjusted, to allow for an efficient exploration of the landscape at all scales. It may seem that this requires excessive tuning, in effect introducing additional hyperparameters, but this is not the case. The tuning of acceptances, or equivalently the distribution of hyperparameters for the replicas, can be performed automatically in an adaptive procedure Katzgraber et al. (2006); Trebst et al. (2006). In the current implementation we used a fixed acceptance parameter to focus the discussion on the main idea of replica exchange of hyperparameters.

title: TRAINING DEEP NEURAL NETWORKS BY OPTIMIZING OVER NONLOCAL PATHS IN HYPERPARAMETER SPACE


summaries: In the context of neural machine translation, limitations of some reinforcement learning methods, in particular REINFORCE and contrastive minimum risk training (MRT), are analyzed. The authors argue that MRT doesn't optimize the expected reward. Moreover, they show that using REINFORCE, with either realistic or dummy constant rewards, may lead to a peakier distribution. Similar BLEU scores are obtained with either type of rewards, which is an interesting and perplexing result (in my opinion). For both REINFORCE and MRT, the paper shows that unless the gold token was already amongst the most probable after pre-training, it takes many samples for it to become the most likely output, which limits the usefulness of on-policy RL approaches.

summaries: This paper first theoretically demonstrates that a commonly used reinforcement learning method for neural sequence-to-sequence models (e.g. in NMT), contrastive minimum risk training (CMRT), is not guaranteed to converge to local (let alone global) optima of the reward function. The paper then empirically demonstrates that the REINFORCE algorithm, while not subject to the same theoretical flaws as CMRT, in practice fails to improve NMT models unless the baseline model is already "nearly correct" (i.e. the correct tokens were already within the few most probable tokens before the fine-tuning steps with REINFORCE). In fact, some of the performance gains of using REINFORCE/CMRT can be attributed to making the model's output probability distribution more peaked, and not necessarily from making the target tokens more probable as commonly assumed.

abstractText: Reinforcement learning (RL) is frequently used to increase performance in text generation tasks, including machine translation (MT), notably through the use of Minimum Risk Training (MRT) and Generative Adversarial Networks (GAN). However, little is known about what and how these methods learn in the context of MT. We prove that one of the most common RL methods for MT does not optimize the expected reward, as well as show that other methods take an infeasibly long time to converge. In fact, our results suggest that RL practices in MT are likely to improve performance only where the pre-trained parameters are already close to yielding the correct translation. Our findings further suggest that observed gains may be due to effects unrelated to the training signal, concretely, changes in the shape of the distribution curve.

authors:
Marcin Andrychowicz
Filip Wolski
Alex Ray
Jonas Schneider
Rachel Fong
Peter Welinder
Bob McGrew
Josh Tobin
OpenAI Pieter Abbeel
Wojciech Zaremba

title: Hindsight experience replay

venue: In Advances in Neural Information Processing Systems,

authors:
Shiqi Shen Ayana
Zhiyuan Liu
Maosong Sun

title: Neural headline generation with minimum risk training

venue: arXiv preprint arXiv:1604.01904,

authors:
Ondrej Bojar
Rajen Chatterjee
Christian Federmann
Barry Haddow
Matthias Huck
Chris Hokamp
Philipp Koehn
Varvara Logacheva
Christof Monz
Matteo Negri
Matt Post
Carolina Scarton
Lucia Specia
Marco Turchi

title: Findings of the 2015 workshop on statistical machine translation

authors:
Massimo Caccia
Lucas Caccia
William Fedus
Hugo Larochelle
Joelle Pineau
Laurent Charlin

title: Language gans falling short

venue: arXiv preprint arXiv:1811.02549,

authors:
Thomas Degris
Martha White
Richard S Sutton

title: Off-policy actor-critic

venue: arXiv preprint arXiv:1205.4839,

authors:
Sergey Edunov
Myle Ott
Michael Auli
David Grangier
Marc’Aurelio Ranzato

title: Classical structured prediction losses for sequence to sequence learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)

venue: Association for Computational Linguistics,

authors:
Benjamin Eysenbach
Abhishek Gupta
Julian Ibarz
Sergey Levine

title: Diversity is all you need: Learning skills without a reward function

venue: In International Conference on Learning Representations,

authors:
Lior Fox
Leshem Choshen
Yonatan Loewenstein

title: Dora the explorer: Directed outreaching reinforcement action-selection

authors:
Dibya Ghosh
Avi Singh
Aravind Rajeswaran
Vikash Kumar
Sergey Levine

title: Divide-andconquer reinforcement learning

authors:
Lisa Anne Hendricks
Zeynep Akata
Marcus Rohrbach
Jeff Donahue
Bernt Schiele
Trevor Darrell

title: Generating visual explanations

venue: In ECCV,

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Philipp Koehn
Hieu Hoang
Alexandra Birch
Chris Callison-Burch
Marcello Federico
Nicola Bertoldi
Brooke Cowan
Wade Shen
Christine Moran
Richard Zens
Chris Dyer
Ondrej Bojar
Alexandra Constantin
Evan Herbst. Moses

title: Open source toolkit for statistical machine translation

venue: In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions,

authors:
Jiwei Li
Will Monroe
Tianlin Shi
Sébastien Jean
Alan Ritter
Dan Jurafsky

title: Adversarial learning for neural dialogue generation

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Siqi Liu
Zhenhai Zhu
Ning Ye
Sergio Guadarrama
Kevin Murphy

title: Optimization of image description metrics using policy gradient methods

authors:
Peter Makarov
Simon Clematide

title: Neural transition-based string transduction for limitedresource setting in morphology

venue: In COLING,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

venue: In International conference on machine learning,

title: Lexicons and minimum risk training for neural machine translation: Naist-cmu at wat2016

venue: In WAT@COLING,

authors:
Graham Neubig
Matthias Sperber
Xinyi Wang
Matthieu Felix
Austin Matthews
Sarguna Padmanabhan
Ye Qi
Devendra Singh Sachan
Philip Arthur
Pierre Godard
John Hewitt
Rachid Riad
Liming Wang

title: Xnmt: The extensible neural machine translation toolkit

venue: AMTA,

title: Minimum error rate training in statistical machine translation

venue: In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume

authors:
Kishore Papineni
Salim Roukos
Todd Ward
Wei-Jing Zhu

title: Bleu: a method for automatic evaluation of machine translation

venue: In Proceedings of the 40th annual meeting on association for computational linguistics,

authors:
Matthias Plappert
Rein Houthooft
Prafulla Dhariwal
Szymon Sidor
Richard Y Chen
Xi Chen
Tamim Asfour
Pieter Abbeel
Marcin Andrychowicz

title: Parameter space noise for exploration

authors:
O. Press
A. Bar
B. Bogin
J. Berant
L. Wolf

title: Language generation with recurrent generative adversarial networks without pre-training

venue: In Fist Workshop on Learning to Generate Natural Language@ICML,

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

venue: arXiv preprint arXiv:1511.06732,

authors:
Steven J Rennie
Etienne Marcheret
Youssef Mroueh
Jerret Ross
Vaibhava Goel

title: Self-critical sequence training for image captioning

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Keisuke Sakaguchi
Matt Post
Benjamin Van Durme

title: Grammatical error correction with neural reinforcement learning

venue: arXiv preprint arXiv:1707.00299,

authors:
Philip Schulz
Wilker Aziz
Trevor Cohn

title: A stochastic decoder for neural machine translation

venue: In ACL,

authors:
Rico Sennrich
Barry Haddow
Alexandra Birch

title: Neural machine translation of rare words with subword units

authors:
Rico Sennrich
Orhan Firat
Kyunghyun Cho
Alexandra Birch
Barry Haddow
Julian Hitschler
Marcin Junczys-Dowmunt
Samuel Läubli
Antonio Valerio Miceli Barone
Jozef Mokry
Maria

title: Nadejde. Nematus: a toolkit for neural machine translation

authors:
Shiqi Shen
Yong Cheng
Zhongjun He
Wei He
Hua Wu
Maosong Sun
Yang Liu

title: Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1683–1692

authors:
Shiqi Shen
Yang Liu
Maosong Sun

title: Optimizing non-decomposable evaluation metrics for neural machine translation

venue: Journal of Computer Science and Technology,

authors:
Rakshith Shetty
Marcus Rohrbach
Lisa Anne Hendricks
Mario Fritz
Bernt Schiele

title: Speaking the same language: Matching machine to human captions by adversarial training

venue: IEEE International Conference on Computer Vision (ICCV),

authors:
David Silver
Guy Lever
Nicolas Heess
Thomas Degris
Daan Wierstra
Martin Riedmiller

title: Deterministic policy gradient algorithms

venue: In ICML,

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
G. Tevet
G. Habib
V. Shwartz
J. Berant

title: Evaluating text GANs as language models

venue: arXiv preprint arXiv:1810.12686,

authors:
Tijmen Tieleman
Geoffrey Hinton

title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
John Wieting
Taylor Berg-Kirkpatrick
Kevin Gimpel
Graham Neubig

title: Beyond BLEU: Training neural machine translation with semantic similarity. In The 57th Annual Meeting of the Association for Computational Linguistics (ACL), Florence, Italy, July 2019

venue: URL https: //arxiv.org/abs/1909.06694

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine learning,

authors:
Lijun Wu
Yingce Xia
Li Zhao
Fei Tian
Tao Qin
Jianhuang Lai
Tie-Yan Liu

title: Adversarial neural machine translation

venue: arXiv preprint arXiv:1704.06933,

authors:
Lijun Wu
Fei Tian
Tao Qin
Jianhuang Lai
Tie-Yan Liu

title: A study of reinforcement learning for neural machine translation

authors:
Zhen Yang
Wei Chen
Feng Wang
Bo Xu

title: Improving neural machine translation with conditional sequence generative adversarial nets. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pp. 1346–1355

authors:
Lantao Yu
Weinan Zhang
Jun Wang
Yong Yu

title: Seqgan: Sequence generative adversarial nets with policy gradient

venue: In AAAI,

authors:
Jiac heng Zhang
Yanzhuo Ding
Shiqi Shen
Yong Cheng
Maosong Sun
Huanbo Luan
Yang Liu

title: Thumt: An open source toolkit for neural machine translation

venue: arXiv preprint arXiv:1706.06415,

authors:
Yizhe Zhang
Zhe Gan
Lawrence Carin

title: Generating text via adversarial training

venue: In NIPS workshop on Adversarial Training,

heading: 1 INTRODUCTION

text:
Reinforcement learning (RL) is an appealing path for advancement in Machine Translation (MT), as it allows training systems to optimize non-differentiable score functions, common in MT evaluation, as well as tackling the “exposure bias” (Ranzato et al., 2015) in standard training, namely that the model is not exposed during training to incorrectly generated tokens, and is thus unlikely to recover from generating such tokens at test time. These motivations have led to much interest in RL for text generation in general and MT in particular (see §2). Various policy gradient methods have been used, notably REINFORCE (Williams, 1992) and variants thereof (e.g., Ranzato et al., 2015; Edunov et al., 2018) and Minimum Risk Training (MRT; e.g., Och, 2003; Shen et al., 2016). Another popular use of RL is for training GANs (Yang et al., 2018; Tevet et al., 2018). Nevertheless, despite increasing interest and strong results, little is known about what accounts for these performance gains, and the training dynamics involved.
We present the following contributions. First, our theoretical analysis shows that commonly used approximation methods are theoretically ill-founded, and may converge to parameter values that do not minimize the risk, nor are local minima thereof (§2.2).
Second, using both naturalistic experiments and carefully constructed simulations, we show that performance gains observed in the literature likely stem not from making target tokens the most probable, but from unrelated effects, such as increasing the peakiness of the output distribution (i.e., the probability mass of the most probable tokens). We do so by comparing a setting where the reward is informative, vs. one where it is constant. In §4 we discuss this peakiness effect (PKE).
Third, we show that promoting the target token to be the mode is likely to take a prohibitively long time. The only case we find, where improvements are likely, is where the target token is among the first 2-3 most probable tokens according to the pretrained model. These findings suggest that REINFORCE (§5) and CMRT (§6) are likely to improve over the pre-trained model only under the best possible conditions, i.e., where the pre-trained model is “nearly” correct.
We conclude by discussing other RL practices in MT which should be avoided for practical and theoretical reasons, and briefly discuss alternative RL approaches that will allow RL to tackle a larger class of errors in pre-trained models (§7).

heading: 2 RL IN MACHINE TRANSLATION

text:
An MT system generates tokens y = (y1, ..., yn) from a vocabulary V one token at a time. The probability of generating yi given preceding tokens y<i is given by Pθ(·|x, y<i), where x is the source sentence and θ are the model parameters. For each generated token yi, we denote with r(yi; y<i, x, y
(ref)) the score, or reward, for generating yi given y<i, x, and the reference sentence y(ref). For brevity, we omit parameters where they are fixed within context. For simplicity, we assume r does not depend on following tokens y>i.
We also assume there is exactly one valid target token, as de facto, training is done against a single reference (Schulz et al., 2018). In practice, either a token-level reward is approximated using MonteCarlo methods (e.g., Yang et al., 2018), or a sentence-level (sparse) reward is given at the end of the episode (sentence). The latter is equivalent to a uniform token-level reward.
r is often the negative log-likelihood, or a standard MT metric, e.g., BLEU (Papineni et al., 2002). RL’s goal is to maximize the expected episode reward (denoted with R); i.e., to find
θ∗ = arg max θ R(θ) = arg max θ Ey∼Pθ [r(y)] (1)

heading: 2.1 REINFORCE

text:
For a given source sentence, and past predictions y<i, REINFORCE (Williams, 1992) samples k tokens (k is a hyperparameter) S = ( y(1), ..., y(k) ) from Pθ and updates θ according to this rule:
∆θ ∝ 1 k k∑ i=1 r(yi)∇ log(Pθ(yi)) (2)
The right-hand side of equation 2 is an unbiased estimator of the gradient of the objective function, i.e., E [∆θ] ∝ ∇θR (θ). Therefore, REINFORCE is performing a form of stochastic gradient ascent on R, and has similar formal guarantees. From here follows that if R is constant with respect to θ, then the expected ∆θ prescribed by REINFORCE is zero. We note that r may be shifted by a constant term (called a “baseline”), without affecting the optimal value for θ.
REINFORCE is used in MT, text generation, and image-to-text tasks (Liu et al., 2016; Wu et al., 2018; Rennie et al., 2017; Shetty et al., 2017; Hendricks et al., 2016) – in isolation, or as a part of training (Ranzato et al., 2015). Lately, an especially prominent use for REINFORCE is adversarial training with discrete data, where another network predicts the reward (GAN). For some recent work on RL for NMT, see (Zhang et al., 2016; Li et al., 2017; Wu et al., 2017; Yu et al., 2017; Yang et al., 2018).

heading: 2.2 MINIMUM RISK TRAINING

text:
The term Minimum Risk Training (MRT) is used ambiguously in MT to refer either to the application of REINFORCE to minimizing the risk (equivalently, to maximizing the expected reward, the negative loss), or more commonly to a somewhat different estimation method, which we term Contrastive MRT (CMRT) and turn now to analyzing. CMRT was proposed by Och (2003), adapted to NMT by Shen et al. (2016), and often used since (Ayana et al., 2016; Neubig, 2016; Shen et al., 2017; Edunov et al., 2018; Makarov & Clematide, 2018; Neubig et al., 2018).
The method works as follows: at each iteration, sample k tokens S = {y1, . . . , yk} from Pθ, and update θ according to the gradient of
R̃(θ, S) = k∑ i=1 Qθ,S(yi)r(yi) = Ey∼Q [ r(y) ] where
Qθ,S(yi) = P (yi) α∑ yj∈S P (yj) α
Commonly (but not universally), deduplication is performed, so R̃ sums over a set of unique values (Sennrich et al., 2017). This changes little in our empirical results and theoretical analysis.
Despite the resemblance in definitions ofR (equation 1) and R̃ (indeed, R̃ is sometimes presented as an approximation of R), they differ in two important aspects. First, Q’s support is S, so increasing
Q(yi) for some yi necessarily comes at the expense of Q(y) for some y ∈ S. In contrast, increasing P (yi), as in REINFORCE, may come at the expense of P (y) for any y ∈ V . Second, α is a smoothness parameter: the closer α is to 0, the closer Q is to be uniform.
We show in Appendix A.1 that despite its name, CMRT does not optimize R, nor does it optimize E[R̃]. That is, it may well converge to values that are not local maxima of R, making it theoretically ill-founded.1 However, given CMRT popularity, the strong results it yielded and the absence of theory for explaining it, we discuss it here. Given a sample S, the gradient of R̃ is given by
∇R̃ = α k∑ i=1 ( Q(yi) · r(yi) · ∇ logP (yi) ) − EQ[r]∇ logZ(S) (3)
where Z(S) = ∑ i P (yi) α. See Appendix A.2.
Comparing Equations 2 and 3, the differences between REINFORCE and CMRT are reflected again. First, ∇R̃ has an additional term, proportional to ∇ logZ(S), which yields the contrastive effect. This contrast may improve the rate of convergence since it counters the decrease of probability mass for non-sampled tokens.
Second, given S, the relative weighting of the gradients∇ logP (yi) is proportional to r(yi)Q(yi), or equivalently to r(yi)P (yi)α. CMRT with deduplication sums over distinct values in S (equation 3), while REINFORCE sums over all values. This means that the relative weight of the unique value yi is r(yi)|{yi∈S}|k in REINFORCE. For α = 1 the expected value of these relative weights is the same, and so for α < 1 (as is commonly used), more weight is given to improbable tokens, which could also have a positive effect on the convergence rate.2 However, if α is too close to 0, ∇R̃ vanishes, as it is not affected by θ. This tradeoff explains the importance of tuning α reported in the literature. In §6 we present simulations with CMRT, showing very similar trends as presented by REINFORCE.

heading: 3 MOTIVATING DISCUSSION

text:
Implementing a stochastic gradient ascent, REINFORCE is guaranteed to converge to a stationary point of R under broad conditions. However, not much is known about its convergence rate under the prevailing conditions in NMT.
We begin with a qualitative, motivating analysis of these questions. As work on language generation empirically showed, RNNs quickly learn to output very peaky distributions (Press et al., 2017). This tendency is advantageous for generating fluent sentences with high probability, but may also entail slower convergence rates when using RL to fine-tune the model, because RL methods used in text generation sample from the (pretrained) policy distribution, which means they mostly sample what the pretrained model deems to be likely. Since the pretrained model (or policy) is peaky, exploration of other potentially more rewarding tokens will be limited, hampering convergence.
Intuitively, REINFORCE increases the probabilities of successful (positively rewarding) observations, weighing updates by how rewarding they were. When sampling a handful of tokens in each context (source sentence x and generated prefix y<i), and where the number of epochs is not large, it is unlikely that more than a few unique tokens will be sampled from Pθ(·|x, y<i). (In practice, k is typically between 1 and 20, and the number of epochs between 1 and 100.) It is thus unlikely that anything but the initially most probable candidates will be observed. Consequently, REINFORCE initially raises their probabilities, even if more rewarding tokens can be found down the list.
We thus hypothesize the peakiness of the distribution, i.e., the probability mass allocated to the most probable tokens, will increase, at least in the first phase. We call this the peakiness-effect (PKE), and show it occurs both in simulations (§4.1) and in full-scale NMT experiments (§4.2).
With more iterations, the most-rewarding tokens will be eventually sampled, and gradually gain probability mass. This discussion suggests that training will be extremely sample-inefficient. We assess the rate of convergence empirically in §5, finding this to be indeed the case.
1Sakaguchi et al. (2017) discuss the relation between CMRT and REINFORCE, claiming that CMRT is a variant . Appendix A.1 shows that CMRT does not in fact optimize the same objective.
2Not performing deduplication (e.g. in THUMT (Zhang et al., 2017)) results in assigning higher relative weight to high-probability tokens, which may have an adverse effect on convergence rate.

heading: 4 THE PEAKINESS EFFECT

text:
We turn to demonstrate that the initially most probable tokens will initially gain probability mass, even if they are not the most rewarding, yielding a PKE.
Caccia et al. (2018) recently observed in the context of language modeling using GANs that performance gains similar to those GAN yield can be achieved by decreasing the temperature for the prediction softmax (i.e., making it peakier). However, they proposed no causes for this effect. Our findings propose an underlying mechanism leading to this trend. We return to this point in §7. Furthermore, given their findings, it is reasonable to assume that our results are relevant for RL use in other generation tasks, whose output space too is discrete, high-dimensional and concentrated.

heading: 4.1 CONTROLLED SIMULATIONS

text:
We experiment with a 1-layer softmax model, that predicts a single token i ∈ V with probability eθi∑ j e θj
. θ = {θj}j∈V are the model’s parameters. This model simulates the top of any MT decoder that ends with a softmax layer, as essentially all NMT decoders do. To make experiments realistic, we use similar parameters as those reported in the influential Transformer NMT system (Vaswani et al., 2017). Specifically, the size of V (distinct BPE tokens) is 30,715, and the initial values for θ were sampled from 1,000 sets of logits taken from decoding the standard newstest2013 development set, using a pretrained Transformer model. The model was pretrained on WMT2015 training data (Bojar et al., 2015). Hyperparameters are reported in Appendix A.3. We define one of the tokens in V to be the target token and denote it with ybest. We assign deterministic token reward, this makes learning easier than when relying on approximations and our predictions optimistic. We experiment with two reward functions:
1. Simulated Reward: r(y) = 2 for y = ybest, r(y) = 1 if y is one of the 10 initially highest scoring tokens, and r(y) = 0 otherwise. This simulates a condition where the pretrained model is of decent but sub-optimal quality. r here is at the scale of popular rewards used in MT, such as GAN-based rewards or BLEU (which are between 0 and 1). 2. Constant Reward: r is constantly equal to 1, for all tokens. This setting is aimed to confirm that PKE is not a result of the signal carried by the reward.
Experiments with the first setting were run 100 times, each time for 50K steps, updating θ after each step. With the second setting, it is sufficient to take a single step at a time, as the expected update after each step is zero, and so any PKE seen in a single step is only accentuated in the next. It is, therefore, more telling to run more repetitions rather than more steps per initialization. We, therefore, sample 10,000 pretrained distributions, and perform a single REINFORCE step.
As RL training lasts about 30 epochs before stopping, samples about 100K tokens per epoch, and as the network already predicts ybest in about two thirds of the contexts,3 we estimate the number of steps used in practice to be in the order of magnitude of 1M. For visual clarity, we present figures for 50K-100K steps. However, full experiments (with 1M steps) exhibit similar trends: where REINFORCE was not close to converging after 50K steps, the same was true after 1M steps.
We evaluate the peakiness of a distribution in terms of the probability of the most probable token (the mode), the total probability of the ten most probable tokens, and the entropy of the distribution (lower entropy indicates more peakiness).
3Based on our NMT experiments, which we assume to be representative of the error rate of other systems.
Results. The distributions become peakier in terms of all three measures: on average, the mode’s probability and the 10 most probable tokens increases, and the entropy decreases. Figure 1a presents the histogram of the update size, the difference in the probability of the 10 most probable tokens in the Constant Reward setting, after a single step. Figure 1b depicts similar statistics for the mode. The average entropy in the pretrained model is 2.9 is reduced to 2.85 after one REINFORCE step.
Simulated Reward setting shows similar trends. For example, entropy decreases from 3 to about 0.001 in 100K steps. This extreme decrease suggests it is effectively a deterministic policy. PKE is achieved in a few hundred steps, usually before other effects become prominent (see Figure 2), and is stronger than for Constant Reward.
4.2 NMT EXPERIMENTS
We turn to analyzing a real-world application of REINFORCE to NMT. Important differences between this and the previous simulations are: (1) it is rare in NMT for REINFORCE to sample from the same conditional distribution more than a handful of times, given the number of source sentences x and sentence prefixes y<i (contexts); and (2) in NMT Pθ(·|x, y<i) shares parameters between contexts, which means that updating Pθ for one context may influence Pθ for another.
We follow the same pretraining as in §4.1. We then follow Yang et al. (2018) in defining the reward function based on the expected BLEU score. Expected BLEU is computed by sampling suffixes for the sentence, and averaging the BLEU score of the sampled sentences against the reference.
We use early stopping with a patience of 10 epochs, where each epoch consists of 5,000 sentences sampled from the WMT2015 (Bojar et al., 2015) German-English training data. We use k = 1. We retuned the learning-rate, and positive baseline settings against the development set. Other hyper-parameters were an exact replication of the experiments reported in (Yang et al., 2018).
Results. Results indicate an increase in the peakiness of the conditional distributions. Our results are based on a sample of 1,000 contexts from the pretrained model, and another (independent) sample from the reinforced model.
The modes of the conditional distributions tend to increase. Figure 3 presents the distribution of the modes’ probability in the reinforced conditional distributions compared with the pretrained model, showing a shift of probability mass towards higher probabilities for the mode, following RL. Another indication of the increased peakiness is the decrease in the average entropy of Pθ, which was reduced from 3.45 in the pretrained model to an average of 2.82 following RL. This more modest reduction in entropy (compared to §4.1) might also suggest that the procedure did not converge to the optimal
value for θ, as then we would have expected the entropy to substantially drop if not to 0 (overfit), then to the average entropy of valid next tokens (given the source and a prefix of the sentence).

heading: 5 PERFORMANCE FOLLOWING REINFORCE

text: We now turn to assessing under what conditions it is likely that REINFORCE will lead to an improvement in the performance of an NMT system. As in the previous section, we use both controlled simulations and NMT experiments.

heading: 5.1 CONTROLLED SIMULATIONS

text:
We use the same model and experimental setup described in Section 4.1, this time only exploring the Simulated Reward setting, as a Constant Reward is not expected to converge to any meaningful θ. Results are averaged over 100 conditional distributions sampled from the pretrained model.
Caution should be exercised when determining the learning rate (LR). Common LRs used in the NMT literature are of the scale of 10−4. However, in our simulations, no LR smaller than 0.1 yielded any improvement in R. We thus set the LR to be 0.1. We note that in our simulations, a higher learning rate means faster convergence as our reward is noise-free: it is always highest for the best option. In practice, increasing the learning rate may deteriorate results, as it may cause the system to overfit to the sampled instances. Indeed, when increasing the learning rate in our NMT experiments (see below) by an order of magnitude, early stopping caused the RL procedure to stop without any parameter updates.
Figure 2 shows the change in Pθ over the first 50K REINFORCE steps (probabilities are averaged over 100 repetitions), for a case where ybest was initially the second, third and fourth most probable. Although these are the easiest settings, and despite the high learning rate, it fails to make ybest the mode of the distribution within 100K
steps, unless ybest was initially the second most probable. In cases where ybest is initially of a lower rank than four, it is hard to see any increase in its probability, even after 1M steps.

heading: 5.2 NMT EXPERIMENTS

text:
We trained an NMT system, using the same procedure as in Section 4.2, and report BLEU scores over the news2014 test set. After training with an expected BLEU reward, we indeed see a minor improvement which is consistent between trials and pretrained models. While the pretrain BLEU score is 30.31, the reinforced one is 30.73.
Analyzing what words were influenced by the RL procedure, we begin by computing the cumulative probability of the target token ybest to be ranked lower than a given rank according to the pretrained model. Results (Figure 4) show that in about half of the cases, ybest is not among the top three choices of the pretrained model, and we thus expect it not to gain substantial probability following REINFORCE, according to our simulations.
We next turn to compare the ranks the reinforced model assigns to the target tokens, and their ranks according to the pretrained model. Figure 6 presents the difference in the probability that ybest is ranked at a given rank following RL and the probability it is ranked there initially. Results indicate that indeed more target tokens are ranked first, and less second, but little consistent shift of probability mass occurs otherwise across the ten first ranks. It is possible that RL has managed to push ybest in some cases between very low ranks (<1,000) to medium-low ranks (between 10 and 1,000). However, token probabilities in these ranks are so low that it is unlikely to affect the system outputs in any way. This fits well with the results of our simulations that predicted that only the initially top-ranked tokens are likely to change.
In an attempt to explain the improved BLEU score following RL with PKE, we repeat the NMT experiment this time using a constant reward of 1. Our results present a nearly identical improvement in BLEU, achieving 30.72, and a similar pattern in the change of the target tokens’ ranks (see Ap-
Figure 5: The probability of different tokens following CMRT, in the controlled simulations in the Simulated Reward setting. The left/right figures correspond to simulations where the target token (ybest) was initially the second/third most probable token. The green line corresponds to the target token, yellow lines to medium-reward tokens and red lines to tokens with r(y) = 0.
pendix 8). Therefore, there is room to suspect that even in cases where RL yields an improvement in BLEU, it may partially result from reward-independent factors, such as PKE.4

heading: 6 EXPERIMENTS WITH CONTRASTIVE MRT

text:
In §2.2 we showed that CMRT does not, in fact, maximizeR, and so does not enjoy the same theoretical guarantees as REINFORCE and similar policy gradient methods. However, being the RL procedure of choice in much recent work we repeat the simulations described in §4 and §5, assessing CMRT’s performance in these conditions. We experiment with α = 0.005 and k = 20, common settings in the literature, and average over 100 trials.
Figure 5 shows how the distribution Pθ changes over the course of 50K update steps to θ, where ybest is taken to be the second and third initially most probable token (Simulated Reward setting). Results are similar in trends to those obtained with REINFORCE: MRT succeeds in pushing ybest to be the highest ranked token if it was initially second, but struggles where it was initially ranked third or below. We only observe a small PKE in MRT. This is probably due to the contrastive effect, which means that tokens that were not sampled do not lose probability mass.
All graphs we present here allow sampling the same token more than once in each batch (i.e., S is a sample with replacements). Simulations with deduplication show similar results.

heading: 7 DISCUSSION

text:
In this paper, we showed that the type of distributions used in NMT entail that promoting the target token to be the mode is likely to take a prohibitively long times for existing RL practices, except under the best conditions (where the pretrained model is “nearly” correct). This leads us to conclude that observed improvements from using RL for NMT are likely due either to fine-tuning the most probable tokens in the pretrained model (an effect which may be more easily achieved using reranking methods, and uses but little of the power of RL methods), or to effects unrelated to the signal carried by the reward, such as PKE. Another contribution of this paper is in showing that CMRT does not optimize the expected reward and is thus theoretically unmotivated.
A number of reasons lead us to believe that in our NMT experiments, improvements are not due to the reward function, but to artefacts such as PKE. First, reducing a constant baseline from r, so as to make the expected reward zero, disallows learning. This is surprising, as REINFORCE, generally and in our simulations, converges faster where the reward is centered around zero, and so the fact that this procedure here disallows learning hints that other factors are in play. As PKE can be observed even where the reward is constant (if the expected reward is positive; see §4.1), this suggests PKE
4We tried several other reward functions as well, all of which got BLEU scores of 30.73–30.84. This improvement is very stable across metrics, trials and pretrained models.
may play a role here. Second, we observe more peakiness in the reinforced model and in such cases, we expect improvements in BLEU (Caccia et al., 2018). Third, we achieve similar results with a constant reward in our NMT experiments (§5.2). Fourth, our controlled simulations show that asymptotic convergence is not reached in any but the easiest conditions (§5.1).
Our analysis further suggests that gradient clipping, sometimes used in NMT (Zhang et al., 2016; Wieting et al., 2019), is expected to hinder convergence further. It should be avoided when using REINFORCE as it violates REINFORCE’s assumptions.
The per-token sampling as done in our experiments is more exploratory than beam search (Wu et al., 2018), reducing PKE. Furthermore, the latter does not sample from the behavior policy, but does not properly account for being off-policy in the parameter updates.
Adding the reference to the sample S, which some implementations allow (Sennrich et al., 2017) may help reduce the problems of never sampling the target tokens. However, as Edunov et al. (2018) point out, this practice may lower results, as it may destabilize training by leading the model to improve over outputs it cannot generalize over, as they are very different from anything the model assigns a high probability to, at the cost of other outputs.

heading: 8 CONCLUSION

text:
The standard MT scenario poses several uncommon challenges for RL. First, the action space in MT problems is a high-dimensional discrete space (generally in the size of the vocabulary of the target language or the product thereof for sentences). This contrasts with the more common scenario studied by contemporary RL methods, which focuses mostly on much smaller discrete action spaces (e.g., video games (Mnih et al., 2015; 2016)), or continuous action spaces of relatively low dimensions (e.g., simulation of robotic control tasks (Lillicrap et al., 2015)). Second, reward for MT is naturally very sparse – almost all possible sentences are “wrong” (hence, not rewarding) in a given context. Finally, it is common in MT to use RL for tuning a pretrained model. Using a pretrained model ameliorates the last problem. But then, these pretrained models are in general quite peaky, and because training is done on-policy – that is, actions are being sampled from the same model being optimized – exploration is inherently limited.
Here we argued that, taken together, these challenges result in significant weaknesses for current RL practices for NMT, that may ultimately prevent them from being truly useful. At least some of these challenges have been widely studied in the RL literature, with numerous techniques developed to address them, but were not yet adopted in NLP. We turn to discuss some of them.
Off-policy methods, in which observations are sampled from a different policy than the one being currently optimized, are prominent in RL (Watkins & Dayan, 1992; Sutton & Barto, 1998), and were also studied in the context of policy gradient methods (Degris et al., 2012; Silver et al., 2014). In principle, such methods allow learning from a more “exploratory” policy. Moreover, a key motivation for using α in CMRT is smoothing; off-policy sampling allows smoothing while keeping convergence guarantees.
In its basic form, exploration in REINFORCE relies on stochasticity in the action-selection (in MT, this is due to sampling). More sophisticated exploration methods have been extensively studied, for example using measures for the exploratory usefulness of states or actions (Fox et al., 2018), or relying on parameter-space noise rather than action-space noise (Plappert et al., 2017).
For MT, an additional challenge is that even effective exploration (sampling diverse sets of observations), may not be enough, since the state-action space is too large to be effectively covered, with almost all sentences being not rewarding. Recently, diversity-based and multi-goal methods for RL were proposed to tackle similar challenges (Andrychowicz et al., 2017; Ghosh et al., 2018; Eysenbach et al., 2019). We believe the adoption of such methods is a promising path forward for the application of RL in NLP.

heading: 9 ACKNOWLEDGMENTS

text: This work was supported by the Israel Science Foundation (grant no. 929/17) and by the HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office.

heading: A APPENDIX

text:
A.1 CONTRASTIVE MRT DOES NOT MAXIMIZE THE EXPECTED REWARD
We hereby detail a simple example where following the Contrastive MRT method (see §2.2) does not converge to the parameter value that maximizes R.
Let θ be a real number in [0, 0.5], and let Pθ be a family of distributions over three values a, b, c such that:
P θ (x) =  θ x = a 2θ2 x = b
1− θ − 2θ2 x = c
Let r(a) = 1, r(b) = 0, r(c) = 0.5. The expected reward as a function of θ is:
R(θ) = θ + 0.5(1− θ − 2θ2)
R(θ) is uniquely maximized by θ∗ = 0.25.
Table 1 details the possible samples of size k = 2, their probabilities, the corresponding R̃ and its gradient. Standard numerical methods show that E[∇R̃] over possible samples S is positive for θ ∈ (0, γ) and negative for θ ∈ (γ, 0.5], where γ ≈ 0.295. This means that for any initialization of θ ∈ (0, 0.5], Contrastive MRT will converge to γ if the learning rate is sufficiently small. For θ = 0, R̃ ≡ 0.5, and there will be no gradient updates, so the method will converge to θ = 0. Neither of these values maximizes R(θ).
We note that by using some g (θ) the γ could be arbitrarily far from θ∗. g could also map to (−inf, inf) more often used in neural networks parameters.
We further note that resorting to maximizing E[R̃] instead, does not maximize R(θ) either. Indeed, plotting E[R̃] as a function of θ for this example, yields a maximum at θ ≈ 0.32.
A.2 DERIVING THE GRADIENT OF R̃
Given S, recall the definition of R̃:
R̃(θ, S) = k∑ i=1 Qθ,S(yi)r(yi)
Taking the deriviative w.r.t. θ:
k∑ i=1 r(yi) ∇P (y) · αP (y)α−1 · Z(S)−∇Z(S) · P (y)α Z(S)2 =
k∑ i=1 r(yi) (α∇P (yi) P (yi) Q(yi)− ∇Z(S) Z(S) Q(yi) ) = k∑ i=1 r(yi)Q(yi) ( α∇ logP (yi)−∇ logZ(S) ) =
α k∑ i=1 ( r(yi)Q(yi)∇ log P (yi) ) − EQ[r]∇ logZ(S)
A.3 NMT IMPLEMENTATION DETAILS
True casing and tokenization were used (Koehn et al., 2007), including escaping html symbols and "-" that represents a compound was changed into a separate token of =. Some preprocessing used before us converted the latter to ##AT##-##AT## but standard tokenizers in use process that into 11 different tokens, which over-represents the significance of that character when BLEU is calculated. BPE (Sennrich et al., 2016) extracted 30,715 tokens. For the MT experiments we used 6 layers in the encoder and the decoder. The size of the embeddings was 512. Gradient clipping was used with size of 5 for pre-training (see Discussion on why not to use it in training). We did not use attention dropout, but 0.1 residual dropout rate was used. In pretraining and training sentences of more than 50 tokens were discarded. Pretraining and training were considered finished when BLEU did not increase in the development set for 10 consecutive evaluations, and evaluation was done every 1,000 and 5,000 for batches of size 100 and 256 for pretraining and training respectively. Learning rate used for rmsprop (Tieleman & Hinton, 2012) was 0.01 in pretraining and for adam (Kingma & Ba, 2015) with decay was 0.005 for training. 4,000 learning rate warm up steps were used. Pretraining took about 7 days with 4 GPUs, afterwards, training took roughly the same time. Monte Carlo used 20 sentence rolls per word.
A.4 DETAILED RESULTS FOR CONSTANT REWARD SETTING
We present graphs for the constant reward setting in Figures 8 and 7. Trends are similar to the ones obtained for the Simulated Reward setting.

title: ING FOR NEURAL MACHINE TRANSLATION