Decoding As Dynamic Programming For Recurrent Autoregressive Models
Authors: Najam Zaidi
Trevor Cohn
Gholamreza Haffari
Venue:  (2020)
Keywords: Decoding

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) inference is found exactly using dynamic programming. The MAP inference 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 unidirectional decoding baselines.

Published as a conference paper at ICLR 2020
DECODING AS DYNAMIC PROGRAMMING FOR RECUR- RENT AUTOREGRESSIVE MODELS
Najam Zaidi
Trevor Cohn
Faculty of Information Technology Monash University, Australia syed. zai faidi1 @monash.eeemmmm edu
School of Computing and Information Systems University of Mclbourne, Australia
t. cohn @ un i me b. edu. au
Gholamreza Haffari
Faculty of Information Technology Monash University, Australia gholamreza haffariimomaaa edu
ABSTRACT
Decoding in autoregressive models (ARMs) consists of searching for high scor- ing output sequence under the trained model. Standard decoding methods, based unidirectional greedy algorithm propagation and myopic decisions which do not account for future steps in the generation process. In this paper we present novel decoding approach based the method auxiliary coordinates (Carreira-Perpinat 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 factor graph approximation of the ARM, whose maximum posteriori (MAP) solution is found exactly using dynamic programming. The MAP solution 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.
beam search, are suboptimal due to error
Wang (014) to address
INTRODUCTION
Neural autoregressive models (ARMs) have shown remarkable performance on various natural lan- guage processing tasks such 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 an end-to-end manner by optimizing the training objective to learn model param- eters. 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 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 's recurrent neural networks (RNNs) (Elman 1990). conditional text generation models with RNN-based decoder (Sutskever et al. 2014), and transformers (Vaswani 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 don-decomposable long-range inter- dependencies among the output variables, i.c. an output token directly depends on all of the previ- ously generated tokens. Standard uni-directional decoding algorithms, e.g. greedy and beam search,

---

Published as a conference paper at ICLR 2020
Mi+
0h+2
W
M++2
W
M++2
h,
he4
he43
he43
(a)
(b)
(c)
Figure 1: A typical RNN with unbounded Markov order is shown in (a). The factor graphs of our zero-order and first-order Markov approximations are illustrated in (b) and (c), respectively. The blue and red factors correspond to likelihood terms and the constraint violations, respectively, from equations K for order k = O, and (4), for
are ineffective in producing high-scoring output sequences, as errors in the decoding history can ad- versely 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 globally optimal complete sequence (Bahdanau et al. 2014 Sutskever et al.) 2014 Mikolov 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-Perrinan & 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 [ We then alternate the output variables and the state variables. The state variables updated to respect the state dynamics of the underlying ARM and the currently fixed output tokens. The output variables updated by dynamic programming exactly optimise 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.
between optimizing
To validate approach, text infilling task, which consists of filling missing parts of a sentence a paragraph (Hor- vat & Byrne, 2014; Tromble & Eisner 2009 Schmaltz et al., 2016). Text infilling chal- lenging as it requires the global structure of the
evaluate the
Context: a package sports charnels
package that indurinz all the movec gharnes the basts charnels also
Greedy:
pockage that package movis with the chaindl.
sentence to fill blank properly. As shown in the figure right, both greedy and beam search fail to fill the blanks correctly. We conduct ex- periments 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
Boam: Do you have a package of that packags 2 movie of with the baskk charne
well as TIGS (Liu et al. 2019), recently introduced strong inference method for this task. TIGS decodes by iteratively optimizing the output variables in continuous relaxation of the discrete output space, and then projecting back the fractional solu- tion 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.
2 RELATED WORK
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
2

---

Published as a conference paper at ICLR 2020
rounding, similar rounding the fractional solution of linear program relaxation of an integer linear program. Performing the best projection, 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 similar to that SPENs and DVNs in that it iteratively optimises and refines the predicted output. However, the output variables always stay in the discrete space in 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 those which may not strictly satisfy the constraints imposed by the dynamics of the underlying ARMs. Cho (2016) proposed to inject ran- dom noise to the hidden states of 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-Perpinar & 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 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 globally optimize the training objective, given careful design of the architecture.
3 OUR DECODING FRAMEWORK
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 recurrent neural network model for text generation. The prob- ability of generating a sequence ...... Yn under the RNN decomposed as
Ply,,.., yn) II P(uly=s),
(1)
where +() = softmax Wh; + b). and the state dynamics h, (h:-1199--1) Decoding then refers to the following optimization problem,
arg max log P(yi,.., yn) Σ log P( yi....
The above optimization problem is computationally hard as it decomposes to conditional probabili- ties with unbounded length for the conditioning contexts, i.c. 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 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 gf
Σ log ((vlg.
(3)
s.t.
g: f(g.-1. Vi E n.....].
Notice the appearance of the new explicit variables g in this optimisation formulation of the decod- ing problem, which mirror the role of h in the underlying RNN. Eliminating the g variables would make this optimisation problem exactly equivalent the original decoding problem in eqn (2) The
3

---

Published as a conference paper at ICLR 2020
serve continuous auxiliary coordinates, following the MAC technique Caareira-Perpinan & Wang 2014).
The objective function in eqn links the state variable gi token variable ys 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 the previous tokens. Interestingly, order decomposition by linking the state variable gi-k from & steps in the past to the generation of the current token yi. This due 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 generated tokens between that time step and the current time step y Hence, our htth order decoding optimisation problem written follows:
generalise to a k
arg min yi -88"
Σ log Pf (g:
(4)
s.t.
gi = f(gi-1:31-1)
Vi [2.
where ((x) (g Y denotes l 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 y For example with
The variables ga and y: for indices i < O are assigned null values, i.c., O, or sentence start sentinel. Assuming the constraints are satisfied, this constrained optimisation problem is equivalent to the decoding problem in eqn ( Otherwise, when the constraints are not met, the htth order objective results in a more accurate approximation to the original decoding problem compared to the first-order formulation in eqn (3. As is made larger, the reliance on g is reduced, as f()) uses the RNN's 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 higher order, is a higher complexity of inference, which we discuss in Section 4.
2, (( (g:-2
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]
4 OPTIMISATION ALGORITHMS
We now turn to solving the constrained optimisation problem in eqn (4). Using the quadratic- penttty (QP) method (Nocedal & Wright 2006), we turn it to an unconstrained optimisation problem,
min C(g vT. Bf
Σ log Pfy:lf( (g (g-+x())) + Allg: - f(g.-1.((1)
(5)
This suggests a two-step block coordinate descent algorithm alternate between (i) optimizing y's while g's s are fixed, and (ii) optimizing g's while y's '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 Mon-Markovian decoding objective to the hounded-Marken constrained optimisation problem in eqn (4), so 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 g; is conditionally generated based on the previous hidden state according multivariate Gaussian distribution with the mean vector g and the diagonal covariance matrix whose diagonal elements are μ 1r_
Assuming g's are fixed, the discrete output variables y's can be updated to exactly solve eqn (5) using variant of the Viterbi algorithm (Viterbil 1967). Let P Pg.., (lyf=)) == softmax(W W fTh) [g. (g + b) be the conditional probability of the next token given the previous k tokens and gi-A- Consider dynamic programming table T E RD
Updating the Output Variables
4

---

Published as a conference paper at ICLR 2020
The table is filled from left to right, and at each time i, the element corresponding to the DP state yi-k+1 E e is computed as,
Tlyl- t min Tly o o Y'EY
1] log P (ve o y + pllg: - -f 1
where y' o yf denotes the concatenation of the token y' to the beginning of the sequence of tokens y - 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[)}k+1) where n is the length of the sequence, l is the Markov order, and [ is the size of the vocabulary.
Updating the State Variables Next, we turn to optimizing the penalized decoding objective (eqn [) with respect to the continuous auxiliary variables, g. assuming fixed outputs, y. For particu- lar 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 transi- tion 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(gī' yi 14). This means, there is no need for backpropagation through the time (BPTT), as opposed 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 likeliilddood 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.
DECODING IN AN ENSEMBLE
In this section, we extend our MAC-based decoding approach 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 as- signment 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 product of experts (Hinton) 1999.. Unidirectional decoding algorithms cannot decode under such ensembles.
Let us consider the decoding problem in ensemble of left-to-right and right-to-left RNNs,
Σ log (x)ly))) + log P()ly>
arg max .n.
where each RNN has its own parameters. We then reformulate this optimisation problem, using auxiliary variables g, and g! for the L2R and R2L RNNs, as follows,
Σ log ((yilf (g-+x++)) + log " (tt)))
arg yf-g""
min """"""""""""
(+t))
(6)
s.t.
g: = 7 (g::-1, 11-1
Vi E [2,.., m]
g = (g/41: 1--1
Vi E [1,..,n-11]
e = elvil
Vi E [1..,]]
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 y: and v/ produced by the L2R and R2L models, respectively (denoted e(y)). This provides denser signal, e.g. from synonyms or words with related syntactic categories, in order to couple the two optimisation problems, compared to sparse signal from constraints using identity of the tokens.
5

---

Published as a conference paper at ICLR 2020
Contect: Look, flis one matches our roem nesperstre Targel: Moreover, It's easy to clean, right? ? You are reall lazy.
placing his shoolieer Target: manning ng gun frm hercopper
Context: Good evering. 38" Are you Mr. 3m Stewart from the States
looks another directon. sightly behind Torget: poth from motel office loads directy up house
Target: Ahn yes that's right..
you soday you needing transfar?
Context: as the detective descenos: someone reaches imo his pockec and pulss out a pack of qum. Target: he holds out to someene
Target: I'm going to need Deposi Centiization to handle the affairs related home.
(a)
(b)
Figure 2: Some test examples from (a) Daily Dialogue and (b) SWAG datasets.
To solve the above optimisation problem, we use of the quadratic penalty method, similar to the previous section, i.c.
min 88 BP'TT'''''''
Σ
log P (y:
B (gi - log P P(xi 81+ 1)
+ullg: - -
|elys] - -[vil12.
This suggests an optimisation algorithm which alternates between (i) updating {y",g") } in the first phase while the other variables are fixed, and (ii) updating g'') in the second phase while the other variables are fixed. The updates for each of these phases is done using iterative algorithm, similar those presented section [ for updating the output and state variables. The only modifi- cation in the objective function of each phase (compared to the previous section) is the inclusion of the token embedding constraints ||e[y]] e[vi]l?, which can be casily accounted for in the dynamic programming algorithm when updating the output variables.
6 EXPERIMENTS
The Text Infilling Task. Text infilling consists of predicting missing parts of a sentence or 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 [001] 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 2019), which also limits the vocabulary, but places no restriction on the number and position of the blanks, and thus is more similar situations encountered in real life applications.
follow setup similar to (Liu et al,,
More formally let B be a mask, comprising set of indices where blanks appear in the sentence. Let y be target sentence where tokens at the positions of the sentence in B have been masked. For example if B = {i, i + 1} then y is (V1,. sentence B the aim to fill in the blanks they appear in sentence. This requires considering global structure of the sentence along with the conditioning context.
1/+22 JBn Given the context x and masked
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 template (denoted as Daily) which 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
Training.
We trained both left-to-right (L2R) ) and right-to-left (R2L) ) models, where R2L models trained by reversing the target side sentence. All models are trained with word embedding

---

Published as a conference paper at ICLR 2020
Dialogue
SWAG
Decoding Method
BLEU
PPLX
BLEU
PPLX
Greedy
71.2
5.88
71.6
5.64
L2R
Beam
71.3
5.84
71.8
5.58
TIGS
73.0
4.31
74.0
3.49
Ours
79.3
3.49
83.9
2.31
Greedy
70.2
6.96
63.9
7.07
R2L
Beam
70.4
6.90
64.1
6.97
TIGS
71.8
4.87
66.5
4.68
Ours
77.9
3.80
78.7
3.04
Both
Ours
80.2
79.3
L.2R component
3.30
3.39
R2L component
3.73
4.15
Table I: BLEU score and perplexity of various models on the two datasets with 50% masking rate.
The results of our decoding approach is based on the 1st order approximation.
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 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 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 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 OpenNMT 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 optimis- ers. 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 step in the direc- tion 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 jts 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 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, 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.
6.1 RESULTS
The results reported in Table Following Liu et al. (2019). we build test set of 5000 sentences for each dataset. We use 50% masking rate and randomly place the blanks for each sentence. We perform experiments left-to-right (L22), right-to-left (R2L), and ensemble of the two.

---

Published as a conference paper at ICLR 2020
Generally, L2R models outperform R2L models. This may be due to sentences being generated inherently in 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 better BLEU score. The benchmark TIGS method (Liu et al. 2019) outpeforms both the greedy algorithm and beam search. However, 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.
decoding method
Given that context from both directions helps in better decoding when working with unidirectional models, we perform experiments on an ensemble of 1.2R and R2L. models. Notably, the unidirec- tional 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.
6.2 ANALYSIS
Varying the Masking Rate. Increasing the masking rate makes 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 able to achieve better results even with high masking rates.
Mask Rate
25%
50%
75%
BLEU
PPLX
BLEU
PPLX
BLEU
PPLX
Greedy
85,4
4.43
71.2
5.88
60.4
4.25
Beam
85.4
4.43
71.3
5,84
62.0
4.03
TIGS
88.0
3.47
73.0
4.31
62.5
3.53
Ours (1st order)
90.9
2.80
79.3
3.49
64.3
2.47
Table 2: Performance with varying masking rates for the different decoding methods.
Varying the Markov Order. Our penalized de- coding objective is composed of the negative log-
likelihood term and the penalty (see eqn 5). As the al- gorithm proceeds, both of these terms decrease, show- ing consistency in the auxiliary variables. We hy- pothesise 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 penal- ized decoding objective in k-th order Markov approxi- mations for (0, 1, 1,2) The results based on 100 examples the test set for the Daily Dialogue dataset, with random masking using 50% masking rate. Ob- serve that the penalized decoding objective tends to decrease less for the 2nd order method compared to the others. Table 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, report results based on two different methods for updating the state variables our method, i.c. gradient- and forced decoding. As expected, gradient- based updates produced more accurate results compared to forced decoding, but the cost of a longer run-time.
6x
tenttret aapenee capertu
4x
3x 30
2x
Figure 3: The figure shows the penalised decoding objective for zero, first and sec- ond order Markov models
Figure 4 shows the iterative improvement of an example test sentence in each iteration of our decod- ing methods with varying Markov order. Each method is given the same initial solution produced by the beam search. The zero-order method converges to bad solution in the first iteration and gets
8

---

Published as a conference paper at ICLR 2020
Gradient Based
Forced Decoding
BLEU
PPLX
Time
BLEU
PPLX
Time
Oforder
77.4
6.55
297s
75.4
6.86
65s
1-order
84.2
3.42
348s
82.6
3.75
938
2-order
85.5
2.33
893s
83.4
3.34
711s
Table The results of varying Markov order and state variable update method. Time is reported for processing 100 sentences.
stuck there in future iterations. The first-order method arrives further improved solution while the second order method can find the best solution among all.
Content: Oh, I'd much prefer to go car, then we don't need to get to the station with our lusgage and You
Gold:
found
Epoch
Zero Order
First Order
Second Order
Fve to drive.
My train I'm supposed to of that
found
relaxing
found the train
And got drive...
My late
And live got to drive. set's
But pot crive
[see not fond
of that I'm found it
more relaxing
fond of that. found it more relaxing tö
that found more relaxing take
have the and
Hit down
train
And (ieegel gol drive... My Can lateli
And to drive Let's sels I'm hal
and pot to drive ssee fond of
of that Im found it
more relaxing
Tond that, found more relasing
that found it prettty more relaxing to
the and
take the
the
And Divegol pol drive... of that
late
And
drive.. Let's
Bol But Bol drivee.. Isee
fond
Pri found It more relaxing
much of that. Iound it more rolaxing BB
that found mudi more rolaxing Kel
have the and
pet train
train
And Ivve to drive. My can I'm late
And luv get drive. Let'ssee ''m not
but (Ve not to crive.. Isee I'm not fond
tht I'm found it more relaxing
much of that. Ifound it more relaxing t6
that. Ioound much more relaxing to pet
the and
train
train
5 And I've got drive. My can I'm late
And live got to drive. Let'ssee I'm not
but (ve pot to crive. [ses not
of that I'm found it more relaxing
much of that. found it more relaxing 1ö
that |I found it much more relaxing to ii the
the and
train
Figure 4: Improvement of the sentence different iterations
CONCLUSION
This work presented method for improving decoding in discrete autoregressive models using dynamic programming. The core idea is to introduce auxiliary variables to decouple the non- Markovian aspects of the model, permitting the next model approximation, and the process iterates. Our results show that our decoding frame- work 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 open text generation problems. Improving the complexity of decoding is an important direction for future research, is applying the method to other autoregressive models, such as the Transformer, which includes self attention, as well as other structured prediction problems.
approximate solution. This solution is used create
ACKNOWLEDGMENTS
This work was supported by the Australian Research Council (DP160102686) and Multi-modal Australian ScienceS Imaging and Visualisation Environment (MASSIVE) www.massive.oog .org..u)) through computational infrastructure. The authors are grateful to the anonymous reviewers for their insightful comments and corrections.
REFERENCES
Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. Bottom-up and top-down attention for image captioning and visual question answer- ing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6077-6086, 2018
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv preprint AX0iv:409.047. 2014.

---

Published as a conference paper at ICLR 2020
David Belanger and Andrew McCallum. Structured prediction energy networks. In International Conference on Machine Learning, pp. 983-992, 2016.
Miguel Carreira-Perpinal and Weiran Wang. Distributed optimization of deeply nested systems. In Artificial Intelligence and Statistics (AISTATS), pp. 10-19, 2014.
Kyunghyun Cho. Noisy parallel approximate decoding for conditional recurrent language model. arXiv preprint arXiv: 1605003353, 2016.
Jeffrey L. Elman. Finding structure in time. COGNITIVE SCIENCE, 14(2):179 211, 1990.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. arXiv preprint arXiv: 04833, 2018.
William Fedus, lan Goodfellow, and Andrew M Dai. Maskgan: better text generation via filling in the_. arXiv preprint 18X100/0 2018.
Steven Y Feng, Aaron W Li, and Jesse Hoey. Keep calm and switch on! preserving sentiment and fluency in semantic text exchange. arXiv preprint arXiv: N0Kiv:9999.000800 2019.
Michael Gygli, Mohammad Norouzi, and Anelia Angelova. Deep value networks learn to evaluate and iteratively refine structured outputs. In Proceedings of the 33rd International Conference on International Conference Machine Learning (ICML), 2017.
Geoffrey E. Hinton. Products of experts. In Ninth International Conference on Artificial Neural Networks, volume 1, pp. 1-6, 1999.
Ari Holtzman, Jan Buys, Maxwell Forbes, Antoine Bosselut, David Golub, and Yejin Choi. Learning to write with cooperative discriminators. arXiv preprint 1rX.v:1805.0608, 2018.
Matic Horvat and William Byme. A graph-based approach to string regeneration. In Proceedings of the Student Research Workshop at the 14th Conference of the European Chapter of the Association for Computational Linguistics, pp. 85-95, 2014.
Daphne Ippolito, David Grangier, Chris Callison-Buree and Douglas Eck. Unsupervised hierarchi- cal story infilling. In Proceedings of the First Workshop on Narrative Understanding, pp. 37-43, 2019.
Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander Rush. OpenNMT: Open- source toolkit for neural machine translation. In Proceedings of ACL 2017, System Demonstra- tions, pp. 67-72, Vancouver, Canada, July 2017. Association for Computational Linguistics. URL https: www wwwwwb.wwwb........ www.wrg//goooo.....oo.......go.. httpo/////..ooooggg///---------0
Yanran Li, Hui Su, Xiaoyu Shen, Wenjie Li, Ziqiang Cao, and Shuzi Niu. Dailydialog: A manually labelled multi-turn dialogue dataset. arXiv preprint arXiv:1710.03995 2017.
Dayiheng Liu, Jie Fu, Pengfei Liu, and Jiancheng Lv. Tigs: An inference algorithm for text infilling with gradient search. arXiv preprint 19Xiv:1905.10700 2019.
Tomáx Mikolov, Martin Karafiát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association, 2010.
Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer, New York, NY, USA. second edition, 2006.
Allen Schmaltz, Alexander M Rush, and Stuart M Shieber. Word ordering without syntax. arXiv preprint 1rXiv:1604.0888 086633, 2016.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances neural information processing systems, pp. 3104-3112 3112, 2014.
Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, and Tom Goldstein. Training neural networks without gradients: scalable admm approach. In International conference on machine learning, pp. 2722-2731, 2016.
10

---

Published as a conference paper at ICLR 2020
Roy Tromble and Jason Eisner. Learning linear ordering problems for better translation. In Pro- ceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2-Volume 2, pp. 1007-1016, 2009.
Lifu Tu and Kevin Gimpel. Learning approximate inference networks for structured prediction. In International Conference on Learning Representations (ICLR), 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, pp. 5998-6008, 2017.
A. Viterbi. Error bounds for convolutional codes and asymptotically optimum decoding algo- rithm. IEEE Transactions on Information Theory, 13(2):260-269) April 1967. doi: 10.1109/TIT. 1967.1054010.
Xiaojun Wan, Fuli Luo, Xue Sun, Songfang Huang, and Jin-ge Yao. Cross-language document summarization via extraction and ranking of multiple summaries. Knowledge and Information Systems, 58(2):811 1991114999200 2019.
Junxiang Wang, Fuxun Yu, Xiang Chen, and Liang Zhao. Admm for efficient deep learning with global convergence. 2019.
Rowan Zellers, Yonatan Bisk, Roy Schwartz, and Yejin Choi. Swag: A large-scale adversarial dataset for grounded commonsense inference. arXiv preprint arXiv: 1rXiv:/888.05326 2018.
Wanrong Zhu, Zhiting Hu, and Eric Xing. Text infilling, arXiv preprint
2019.
Geoffrey Zweig and Christopher IC Burges. The microsoft research sentence completion challenge. Microsoft Research, Redmond, WA, USA, Tech. Rep. MSR-TR 10R--TR-0011-12, 2011.


Reviews:
[{"review_id": "rJgHLapy9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work introduces a new algorithm to improve decoding in discrete autoregressive models (ARMs). Because exact decoding of ARMs is computationally difficult, the contribution of this paper is to introduce a new approximate solution. The authors show experimentally that this new framework is very effective and outperforms multiple baselines such as greedy and bean search and another text filing algorithm called TIGC on a text-filling benchmark. This work is not in my domain of expertise so I am not able to have a very accurate evaluation. However, based on the references cited in this paper, there are other approximate solution for ARMs and I believe the authors need to use those as baselines to show that the proposed approximate solution is useful.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJlQ7OR3FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nOverall, the proposed method can be very useful in RNN decoding and structure prediction. The idea, however, is quite straightforward to people who are familiar with probabilistic graphic models and inference. I am surprised (if the authors' claim is correct) the RNN community still relies on greedy/beam search for decoding. In graphical model language, the hidden states (h_i or g_i in the paper) are typically viewed as continuous latent random variables. The function f that links consecutive hidden states are factors or potential functions. For inference/prediction, you can jointly optimize the hidden states and discrete outputs, where the alternative updates are a natural choice. Similar ideas were used long time ago when (hierarhical) conditional random fields were popular. Honestly, I don't see anything new here.  Here are a few comments:\n\n1. Don't say ARMs are non-Markov model and/or with unbounded Markov order. This is very misleading and over bragging. RNNs are just a nonlinear version of HMM/hidden Kalman filter. The only difference is that the states are continuous (Kalman filter uses continuous states as well), and the state transition kernel is nonlinear, constructed in a very black-box way. People like to make some analogy with brains --- unfortunately, these explanations are at most an analogy.  Given hidden states, RNNs are just first order Markov-chains, nothing special. If you integrate out hidden states, of course, every output is dependent on all the previous outputs. But the same argument applies to all the hidden markov models/dynamic systems. This is not something unique to RNNs, and shouldn't be hyped everywhere.\n\n2. Is there a way to show the standard deviations/error bars in the test results, say, Table 1 & 2 and the figure? One single number is usually not representative for the performance, unless you have a large test set. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BygmgjVnYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I think this is a good study, unless I miss something. It proposes a new solution to one of the fundamental problems in the field, which significantly improves previous solutions in terms of accuracy. I will recommend it for acceptance unless I miss something. (I’m not an expert in the field and the problem seems to be so fundamental, making me cautious about judging the novelty of the proposed solution.)\n\nThere seems to be some unclarity about the optimization algorithm. In short, I suspect that the proposed optimization has some difficulty with its convergence. \n-\tIn Sec.4, the authors suggest “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”. They further suggest `a variant of the Viterbi algorithm’ for (i) and gradient-based algorithms for (ii). These seem to make sense to me so far. \n-\tThen, in Sec.6, they state that “We use the Nesterov optimizer with a learning rate of 0.1. All \\mu’s are initialised with 0.5 and are multiplied by 1.2 after 5 epochs”. I think this needs some explanation. \n-\tFor instance, what is the thought behind the choice of the optimizer? Why was Nesterov’s acceleration necessary instead of plain GD? Is it essential to use the scheduled adjustment of \\mu?\n-\tIt states “All \\mu’s” but there seems only a single \\mu in Eq.(5). Am I missing something?\n-\t Some explanation on what “Nesterov optimizer” and \\mu would also be necessary for a wide range of readers. \n-\tThere is a statement on the initialization of the optimization in p.7: “h corresponding to the beam search solution to initialize the g variables”. How sensitive is the optimization to the initial values? For instance, will the results change if g’s are initialized by the solution of the greedy method. \n-\tThere is a plot without a figure caption in p.8, which shows how the objective cost decreases with parameter updates. Why are their values at ‘epoch’=0 lower than those at the subsequent epochs? Does this mean the initial values give more optimal parameters?\n\nAdditional comments:\n-\tIt would be more friendly to the readers to show the definition of the notations like y^n_1. \n-\tThere is a statement like “Decoding was run for 10 epochs.” I suppose epochs here mean iteration count of the alternated parameter updates in the proposed algorithm. Why do the authors call it `epoch’? \n-\tNo figure caption for the plot in p.8. It also uses `epochs’ for the horizontal axis title. No axis title for the vertical axis. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an approximate inference approach for decoding in autoregressive models, based on the method of auxiliary coordinates,  which uses iterative factor graph approximations of the model.  The approach leads to nice improvements in performance on a text infilling task.  The reviewers were generally positive about this paper, though there was a concern that more baselines are needed and discussion was very limited following the author responses.  I tend to agree with the authors that their results are convincing on the infilling task.  The impact of the paper is a bit limited by the lack of experiments on more standard decoding tasks, which, as the authors point out, would be challenging as their approach is computationally demanding.  Overall I believe this would be an interesting contribution to the ICLR community.
Decision: Accept (Poster)