Year: 2020

Abstract:
Decoding in autoregressive models (ARMs) consists of searching for a high scoring output sequence under the trained model. Standard decoding methods, based on unidirectional greedy algorithm or beam search, are suboptimal due to error propagation and myopic decisions which do not account for future steps in the generation process. In this paper we present a novel decoding approach based on the method of auxiliary coordinates (Carreira-Perpinan & Wang, 2014) to address the aforementioned shortcomings. Our method introduces discrete variables for output tokens, and auxiliary continuous variables representing the states of the underlying ARM. The auxiliary variables lead to a factor graph approximation of the ARM, whose maximum a posteriori (MAP) solution is found exactly using dynamic programming. The MAP solution is then used to recreate an improved factor graph approximation of the ARM via updated auxiliary variables. We then extend our approach to decode in an ensemble of ARMs, possibly with different generation orders, which is out of reach for the standard unidirectional decoding algorithms. Experiments on the text infilling task over SWAG and Daily Dialogue datasets show that our decoding method is superior to strong competing decoding methods.

heading: 1 INTRODUCTION
text: Neural autoregressive models (ARMs) have shown remarkable performance on various natural language processing tasks such as question answering, machine translation, summarization and reading comprehension (Anderson et al., 2018; Bahdanau et al., 2014; Wan et al., 2019). These models are usually trained in an end-to-end manner by optimizing the training objective to learn model parameters. Once the model has been trained, the output is generated by searching for a high scoring sequence given the context and the trained model. This is referred to as the decoding problem.
ARMs create a sequence by repeatedly generating the next symbol conditioned on all previous symbols generated. Symbols play dual duty: first they are generated, and next they are incorporated into the conditioning of subsequent decisions. As subsequent decisions can be arbitrarily distant in the sequence, these generation models are non-Markovian, i.e. they do not have a bounded Markov order. As prominent examples, ARMs include Elman’s recurrent neural networks (RNNs) (Elman, 1990), conditional text generation models with RNN-based decoder (Sutskever et al., 2014), and transformers (Vaswani et al., 2017).
Exact decoding in ARMs is computationally hard, as the output search space is exponentially large and does not lend itself to efficient algorithms. This is due to non-decomposable long-range interdependencies among the output variables, i.e. an output token directly depends on all of the previously generated tokens. Standard uni-directional decoding algorithms, e.g. greedy and beam search,
are ineffective in producing high-scoring output sequences, as errors in the decoding history can adversely affect the future. These algorithms make local decisions to extend an incomplete sequence (hypothesis) by selecting the token with the maximum likelihood at each time step, hoping to get a globally optimal complete sequence (Bahdanau et al., 2014; Sutskever et al., 2014; Mikolov et al., 2010).
In this paper, we present a novel decoding method, based on the method of auxiliary coordinate (MAC), which has been mainly investigated for training deep neural networks (Carreira-Perpinan & Wang, 2014). Our approach introduces discrete variables for output tokens, and auxiliary continuous variables representing the states of the underlying ARM. The auxiliary variables lead to a factor graph approximation of the ARM with a bounded Markov order (see Figure 1). We then alternate between optimizing over the output variables and the state variables. The state variables are updated to respect the state dynamics of the underlying ARM and the currently fixed output tokens. The output variables are updated by dynamic programming to exactly optimise a global scoring function, decomposed over local factors determined by the currently fixed state variables. We then extend our MAC-based decoding approach to decode under product of ARM experts (Hinton, 1999), i.e. an ensemble of ARMs combined additively in log-space, with each using a different generation order.
To validate our approach, we evaluate on the text infilling task, which consists of filling missing parts of a sentence or a paragraph (Horvat & Byrne, 2014; Tromble & Eisner, 2009; Schmaltz et al., 2016). Text infilling is challenging as it requires the global structure of the sentence to fill a blank properly. As shown in the figure to right, both greedy and beam search fail to fill the blanks correctly. We conduct experiments on two datasets: SWAG (Zellers et al., 2018) and Daily dialogue (Li et al., 2017) with various mask rates. We show that our decoding approach achieve remarkable improvements against the greedy and beam search algorithms as well as TIGS (Liu et al., 2019), a recently introduced strong inference method for this task. TIGS decodes by iteratively optimizing the output variables in a continuous relaxation of the discrete output space, and then projecting back the fractional solution to the discrete space. In contrast, the outputs in our approach stay in the discrete space, and we iteratively optimize over both the outputs and the continuous state variables.

heading: 2 RELATED WORK
text: Inference in Relaxed Output Spaces. One approach to inference in deep neural networks is to relax the discrete output space to a continuous space, and then use gradient descent optimisation over the relaxed output variables, including structured prediction energy networks (SPENs) (Belanger & McCallum, 2016) and deep value networks (DVNs) (Gygli et al., 2017). The gradient descent optimisation for inference in SPENs is replaced by an inference network in Tu & Gimpel (2018), in order to speed up the prediction process. In all of these works, the relaxed output should be projected back to the discrete space at the end of the inference in the relaxed space. This is usually done by
rounding, similar to rounding the fractional solution of a linear program relaxation of an integer linear program. Performing the best projection, in terms of the loss function of interest, is usually a hard problem in itself; therefore, the quality of the solution is often degraded in the projection step.
Our inference approach is similar to that of SPENs and DVNs in that it iteratively optimises and refines the predicted output. However, the output variables always stay in the discrete space in our approach, so we do not need a projection step of the inference process for rounding. Our approach, instead, relaxes the space of continuous state variables to those which may not strictly satisfy the constraints imposed by the dynamics of the underlying ARMs. Cho (2016) proposed to inject random noise to the hidden states of a conditional recurrent neural language model during greedy or beam search, and execute multiple parallel decoding runs. Our approach, instead, makes structured changes to the state variables in the direction of optimising the decoding objective.
Method of Auxiliary Coordinates. Carreira-Perpinan & Wang (2014) introduced the method of auxiliary variables (MAC) to train a neural network. Their idea was to break the interdependence in layers of the neural network by introducing additional variables per data point and per hidden unit. This resulted in smaller problems that could be solved easily given a careful design of the architecture. Taylor et al. (2016) extends MAC by introducing different auxiliary variables for the linear operations and non-operations in a neural network. This results in three sets of variables involving two auxiliary variables and the weights, which is then optrimized by alternating direction method of multipliers (ADMM). Similarly, (Wang et al., 2019) introduces new variables and train the neural network using ADMM to globally optimize the training objective, given a careful design of the architecture.

heading: 3 OUR DECODING FRAMEWORK
text: Notations. We denote scalars, vectors and matrices using lower-case, bold lower-case and bold upper-case letters, e.g. y, y and Y. Individual elements of y are denoted as yi.
Problem Formulation. Consider a recurrent neural network model for text generation. The probability of generating a sequence y1, .., yn under the RNN is decomposed as
P (y1, .., yn) = n∏ i=1 P (yi|y<i) , (1)
where P (.|y<i) := softmax(Whi + b), and the state dynamics is hi = f (hi−1, yi−1). Decoding then refers to the following optimization problem,
arg max y1,..,yn logP (y1, .., yn) = n∑ i=1 logP (yi|y<i) (2)
The above optimization problem is computationally hard as it decomposes to conditional probabilities with unbounded length for the conditioning contexts, i.e. a non-Markovian model.
Method of Auxiliary Coordinate (MAC). Our goal is to decompose the optimisation problem in eqn (2) into smaller optimisation problems, which can be solved jointly and coupled via the state variables. This would make decoding more resilient compared t uni-directional decoding, where early errors can adversely affect the future.
Let us start by considering the following decomposition of the decoding problem,
arg min yn1 ,g n 1 − ∑ i logP (yi|gi)
s.t. gi = f (gi−1, yi−1) ∀i ∈ [2, .., n] .
(3)
Notice the appearance of the new explicit variables g in this optimisation formulation of the decoding problem, which mirror the role of h in the underlying RNN. Eliminating the g variables would make this optimisation problem exactly equivalent to the original decoding problem in eqn (2). The
g serve as continuous auxiliary coordinates, following the MAC technique (Carreira-Perpinan & Wang, 2014).
The objective function in eqn (3) links the state variable gi to token variable yi generated at the time step i. This is a zero-order decomposition of the log-likelihood function in eqn (2), as the terms in the objective do not condition on the previous tokens. Interestingly, we can generalise to a kth order decomposition by linking the state variable gi−k from k steps in the past to the generation of the current token yi. This is due to the fact that the current hidden state, responsible for generating the current token in RNNs, is a deterministic function of the past hidden state gi−k and all of the k generated tokens between that time step and the current time step yi−1i−k. Hence, our k
th order decoding optimisation problem is written as follows:
arg min yn1 ,g n 1 − ∑ i logP (yi|f (k)(gi−k,yi−1i−k))
s.t. gi = f (gi−1, yi−1) ∀i ∈ [2, .., n] ,
(4)
where f (k)(gi−k,yi−1i−k) denotes k repeated applications of the RNN’s state transition function f (.) to compute the current hidden state from the past state gi−k and the tokens observed since then yi−1i−k. For example with k = 2, f (2)(gi−2,y i−1 i−2) = f (Wf (Wgi−2,yi−2),yi−1). The variables gi and yi for indices i ≤ 0 are assigned null values, i.e., 0, or a sentence start sentinel. Assuming the constraints are satisfied, this constrained optimisation problem is equivalent to the decoding problem in eqn (2). Otherwise, when the constraints are not met, the kth order objective results in a more accurate approximation to the original decoding problem compared to the first-order formulation in eqn (3). As k is made larger, the reliance on g is reduced, as f (k) uses the RNN’s state transition function directly. This will be important in early stages of optimisation, where g does not accurately reflect the RNN state dynamic. The cost of using a higher order, is a higher complexity of inference, which we discuss in Section 4.
In summary, our decoding approach results in a constrained optimisation problem, incorporating two types of factors corresponding to the likelihood terms in the objective function and the constraint violations, respectively, which are denoted by blue and red, in the factor graph of Figure 1.

heading: 4 OPTIMISATION ALGORITHMS
text: We now turn to solving the constrained optimisation problem in eqn (4). Using the quadratic-penalty (QP) method (Nocedal & Wright, 2006), we turn it to an unconstrained optimisation problem,
min gn1 ,y n 1 L(gn1 ,yn1 , µ) := ∑ i − logP (yi|f (k)(gi−k,yi−1i−k)) + µ||gi − f (gi−1, yi−1)|| 2 2. (5)
This suggests a two-step block coordinate descent algorithm to alternate between (i) optimizing y’s while g’s are fixed, and (ii) optimizing g’s while y’s are fixed. Other methods for constrained optimization can be used, e.g. the augmented Lagrangian, rather than the quadratic-penalty method (Nocedal & Wright, 2006; Taylor et al., 2016; Wang et al., 2019). However, the focus of our work is to investigate the effectiveness of decomposing the non-Markovian decoding objective to the bounded-Markov constrained optimisation problem in eqn (4), so we leave it to the future work to investigate the effect of different optimisation strategies.
It is worth noting that the above optimisation problem can be also interpreted as inference objective in an stochastic RNN, where the next hidden state gi is conditionally generated based on the previous hidden state according to a multivariate Gaussian distribution with the mean vector gi−1 and the diagonal covariance matrix whose diagonal elements are µ−1.
Updating the Output Variables Assuming g’s are fixed, the discrete output variables y’s can be updated to exactly solve eqn (5) using a variant of the Viterbi algorithm (Viterbi, 1967). Let Pgi−k(.|y i−1 i−k) := softmax(W · f (k)(gi−k,y i−1 i−k) + b) be the conditional probability of the next token given the previous k tokens and gi−k. Consider a dynamic programming table T ∈ R|Y k|×n.
The table is filled from left to right, and at each time i, the element corresponding to the DP state yii−k+1 ∈ Yk is computed as,
T [yii−k+1, i]← min y′∈Y T [y′ ◦ yi−1i−k+1, i− 1]− logPgi−k(yi|y ′ ◦ yi−1i−k+1) + µ||gi − f (gi−1, yi−1)|| 2 2
where y′ ◦ yi−1i−k+1 denotes the concatenation of the token y′ to the beginning of the sequence of tokens yi−1i−k+1, which results in a sequence of tokens of length k. Once the DP table is built, the optimal sequence can be read off by traversing the table from the end towards the beginning. The time complexity of the DP is O(n|Y|k+1) where n is the length of the sequence, k is the Markov order, and |Y| is the size of the vocabulary.
Updating the State Variables Next, we turn to optimizing the penalized decoding objective (eqn 5) with respect to the continuous auxiliary variables, g, assuming fixed outputs, y. For particular combinations of state transition and the likelihood functions, the optimal state values may have gradient-free closed form solution. However, we assume the general case, where the state transition and likelihood functions are given typical nonlinear functions. In the absence of closed-form solution, the simplest method is to use gradient-based optimization algorithms. Interestingly, the computational graph corresponding to the penalized decoding objective considers the state variables of all positions as the input when computing the output L(gn1 ,yn1 , µ). This means, there is no need for backpropagation through the time (BPTT), as opposed to the underlying RNN, to compute the gradient as the contribution of all positions is taken into account in parallel.
We also propose an approximation method to simplify the g update, by ignoring the log-likelihood term in the objective, which we denote by forced decoding. In this case, the penalty term can be optimized exactly, and reduced to zero by computing g’s according to the RNN state transition function f (.) from-left-to-right while the output variables are fixed. This update does not involve computing the gradients, and only involves a forward pass through the RNN.

heading: 5 DECODING IN AN ENSEMBLE
text: In this section, we extend our MAC-based decoding approach to decode under an ensemble of ARMs, each using a different generation order. For example, consider two RNN-based language models, left-to-right (L2R) and right-to-left (R2L), where each of which gives a score to an assignment of words to the blank positions in the text infilling task. We are then interested to find an assignment of words which has the maximum sum of the scores under these two models. As both models are in the exponential family, this corresponds to a product of experts (Hinton, 1999). Unidirectional decoding algorithms cannot decode under such ensembles.
Let us consider the decoding problem in an ensemble of left-to-right and right-to-left RNNs,
arg max y1,..,yn ∑ i log −→ P (yi|y<i) + log ←− P (yi|y>i)
where each RNN has its own parameters. We then reformulate this optimisation problem, using auxiliary variables gi and g′i for the L2R and R2L RNNs, as follows,
arg min yn1 ,g n 1 ,y ′n 1 ,g ′n 1 − ∑ i log −→ P (yi| −−→ f (k)(gi−k,y i−1 i−k)) + log ←− P (y′i| ←−− f (k)(g′i+k,y ′i+1 i+k))
s.t. gi = −→ f (gi−1, yi−1) ∀i ∈ [2, .., n] g′i = ←− f (g′i+1, yi+1) ∀i ∈ [1, .., n− 1] e[yi] = e[y ′ i] ∀i ∈ [1, .., n]
(6)
where the constraints in eqn (6) couple the two optimisation problems corresponding to the L2R and R2L RNNs. Note that we have enforced the equality between the embeddings of the words yi and y′i produced by the L2R and R2L models, respectively (denoted e[y]). This provides a denser signal, e.g. from synonyms or words with related syntactic categories, in order to couple the two optimisation problems, compared to a sparse signal from constraints using identity of the tokens.
To solve the above optimisation problem, we use of the quadratic penalty method, similar to the previous section, i.e.,
min gn1 ,y n 1 ,g ′n 1 ,y ′n 1 ∑ i − log −→ P (yi| −−→ f (k)(gi−k,y i−1 i−k))− log ←− P (y′i| ←−− f (k)(g′i+k,y ′i+1 i+k))
+µ||gi − −→ f (gi−1, yi−1)||22 + µ′||g′i − ←− f (g′i+1, y ′ i+1)||22 + µ′′||e[yi]− e[y′i]||2 .
This suggests an optimisation algorithm which alternates between (i) updating {yn1 ,gn1 } in the first phase while the other variables are fixed, and (ii) updating {y′n1 ,g′ n 1} in the second phase while the other variables are fixed. The updates for each of these phases is done using an iterative algorithm, similar to those presented in section 4, for updating the output and state variables. The only modification in the objective function of each phase (compared to the previous section) is the inclusion of the token embedding constraints ||e[yi]− e[y′i]||2, which can be easily accounted for in the dynamic programming algorithm when updating the output variables.

heading: 6 EXPERIMENTS
text: The Text Infilling Task. Text infilling consists of predicting missing parts of a sentence or a paragraph. The task is encountered in everyday applications of restoring historical or damaged documents (Zhu et al., 2019), writing articles or contracts with templates (Ippolito et al., 2019) and text editing (Feng et al., 2019). Although important, text infilling is less explored and has been studied under simplified and restricted settings (Fedus et al., 2018; Zweig & Burges, 2011; Holtzman et al., 2018; Fan et al., 2018). For example, Horvat & Byrne (2014) restricted the vocabulary to the set of gold standard words blanked in the sentence. Here we follow a setup similar to (Liu et al., 2019), which also limits the vocabulary, but places no restriction on the number and position of the blanks, and thus is more similar to situations encountered in real life applications.
More formally let B be a mask, comprising set of indices where blanks appear in the sentence. Let yB be a target sentence where tokens at the positions of the sentence in B have been masked. For example if B = {i, i+ 1} then yB is {y1, ...yi−1, , , yi+2, ..yn}. Given the context x and masked sentence yB , the aim is to fill in the blanks as they appear in sentence. This requires considering global structure of the sentence along with the conditioning context.
Datasets. We evaluate our proposed approach on two text infilling tasks over two widely used publicly available corpora. The first task is conversation reply with a template (denoted as Daily) which is conducted on the DailyDialog dataset (Li et al., 2017). Similar to Liu et al. (2019) we convert the multi-turn dialogues into single-turn dialogues , resulting in 82,372 conversation pairs. The query sentence is used as input to the encoder x where as the reply is the output y from the decoder. The second task is captions from movies along with an ending (denoted as SWAG) which is conducted on the SWAG dataset (Zellers et al., 2018). We only consider the correct endings to build the target side. This gives us 73,000 pairs of sentences. The input to the encoder is the caption x whereas the decoder has to produce the ending y conditioned on x. Some examples of these datasets are shown in Figure 2.
Training. We trained both left-to-right (L2R ) and right-to-left (R2L ) models, where R2L models are trained by reversing the target side sentence. All models are trained with a word embedding
size and hidden dimension size of 512. We use ADAM optimiser to train the models with an initial learning rate of 0.001. Since the source and target sides are in the same language, we shared the word embeddings between the encoder and decoder. The models were trained for 10 epochs.
Baselines. Our baselines include: greedy decoding, beam search, and a strong recently proposed inference algorithm for the text infilling task TIGS (Liu et al., 2019). TIGS decodes by iterating through the following steps: (i) relaxing the space of output variables from discrete to continuous and optimise over the continuous output variables using gradient based optimization, and (ii) projecting back the solution from the continuous space to discrete. In contrast, the outputs in our approach stay in the discrete space, and we optimize over both discrete and the continuous state variables, as part of an iterative coordinate descent procedure. Our methods and the baslines are implemented on top of OpenNMT1 (Klein et al., 2017).
Decoding Parameters We use the Nesterov optimiser with a learning rate of 0.1. We experiment with Adam and simple SGD and find empirically that Nesterov works better than the other optimisers. Nesterov is a momentum based optimiser that stabilize the update directions and seems to better escape from poor local optima during the decoding iterations. Rather than taking a step in the direction of updated accumulated gradient, Nesterov optimiser first moves in the direction of previously accumulated gradient. It calculates the new gradient and then makes a correction. This prevents the optimiser from going too fast and results in increased responsiveness, which significantly improves the performance.
All µ’s for the penalty terms corresponding to different constraints, are initialised with 0.5 and are multiplied by 1.2 after 5 iterations, and decoding was run for 10 iterations, chosen as the first order method had reliably converged in terms of objective value and the output string.
We use the RNN states h corresponding to the beam search solution to initialize the g variables in our decoding method. We experiment with initialising the hidden states with random values, or using the values corresponding to the greedy solution. We find that using beam search for initialisation gives better results. Compared to beam search, random initialisation requires an average of 12x more iterations, and would occasionally suffer from non-convergence, where the solution oscillates. We find negligible difference between the number of iterations needed for convergence between the beam and greedy search initialised hidden states.

heading: 6.1 RESULTS
text: The results are reported in Table 1. Following Liu et al. (2019), we build a test set of 5000 sentences for each dataset. We use a 50% masking rate and randomly place the blanks for each sentence. We perform experiments on left-to-right (L2R), right-to-left (R2L), and an ensemble of the two.
1https://github.com/Najamxaidi/Decoding-as-a-dynamic-program-for-recurrent-autoregressive-models.git
Generally, L2R models outperform R2L models. This may be due to sentences being generated inherently in a left to right manner. Hence modelling the writing process with a right to left model may make it difficult to learn useful patterns. The trend across all the models and both datasets is that a decrease in perplexity leads to a better BLEU score. The benchmark TIGS method (Liu et al., 2019) outperforms both the greedy algorithm and beam search. However, our decoding method outperforms TIGS and other baselines significantly. Compared to the greedy algorithm and beam search, our method and TIGS leverage information from both future and the past. Compared to TIGS, our method operates by keeping the output variables in the discrete space, whereas in TIGS the output variables are relaxed to the continuous space and projected back to the discrete space.
Given that context from both directions helps in better decoding when working with unidirectional models, we perform experiments on an ensemble of L2R and R2L models. Notably, the unidirectional greedy algorithm and beam search cannot operate on the ensemble. Our method, instead, can decode with the ensemble, which further improves the BLEU score for the Dialogue task.

heading: 6.2 ANALYSIS
text: Varying the Masking Rate. Increasing the masking rate makes it difficult for all the models to correctly fill in the blanks. We experiment on the dialogue dataset by randomly masking the test set with the rates 25%, 50%, and 75%. Results are reported in Table 2. As the masking rate increases, BLEU score decreases, whereas perplexity increases. Compared to the other techniques, our method is able to achieve better results even with high masking rates.
Varying the Markov Order. Our penalized decoding objective is composed of the negative loglikelihood term and the penalty (see eqn 5). As the algorithm proceeds, both of these terms decrease, showing consistency in the auxiliary variables. We hypothesise that, although higher order Markov models produce more accurate approximations to the original decoding problem, they result in harder optimization problems. The following figure (right) plots the penalized decoding objective in k-th order Markov approximations for k ∈ {0, 1, 2}. The results are based on 100 examples in the test set for the Daily Dialogue dataset, with random masking using 50% masking rate. Observe that the penalized decoding objective tends to decrease less for the 2nd order method compared to the others. Table 3 reports the perplexity, BLEU score, and decoding time for these different Markov approx-
imations. The results confirm the increase in the BLEU score and decrease in the perplexity, as the Markov order increases. Furthermore, it shows the trade-off in the solution quality vs. decoding time for these different approximations. In Table 3, we report results based on two different methods for updating the state variables in our method, i.e. gradient-based and forced decoding. As expected, gradient-based updates produced more accurate results compared to forced decoding, but at the cost of a longer run-time.
Figure 4 shows the iterative improvement of an example test sentence in each iteration of our decoding methods with varying Markov order. Each method is given the same initial solution produced by the beam search. The zero-order method converges to a bad solution in the first iteration and gets
stuck there in future iterations. The first-order method arrives to a further improved solution while the second order method can find the best solution among all.

heading: 7 CONCLUSION
text: This work presented a method for improving decoding in discrete autoregressive models using dynamic programming. The core idea is to introduce auxiliary variables to decouple the nonMarkovian aspects of the model, permitting an approximate solution. This solution is used to create the next model approximation, and the process iterates. Our results show that our decoding framework is effective, leading to substantial improvements over greedy and beam search baselines. Our approach does have limitations, most notably the computational complexity which is polynomial in the vocabulary size, thus limiting its application to open text generation problems. Improving the complexity of decoding is an important direction for future research, as is applying the method to other autoregressive models, such as the Transformer, which includes self attention, as well as other structured prediction problems.

heading: ACKNOWLEDGMENTS
text: This work was supported by the Australian Research Council (DP160102686) and Multi-modal Australian ScienceS Imaging and Visualisation Environment (MASSIVE) (www.massive.org.au) through computational infrastructure. The authors are grateful to the anonymous reviewers for their insightful comments and corrections.

Review summaries:
The paper proposes a decoding algorithm for auto-regressive models (ARMs) to improve the decoding accuracy. The key idea is to introduce auxiliary continuous states variables, and alternatively optimize the discrete output variables (i.e., the tokens) and the continuous states. Given the hidden states, the decoding can be efficiently done by veterbi-like algorithms. Then the constraint of the auxiliary variables can be imposed by penalty based continuous based optimization. The paper also extends the idea to the ensemble of ARMs.  On two NLP tasks, the paper shows improvement upon the existing greedy or beach search based approaches.