Discovering Non-monotonic Autoregressive Orderings with Variational Inference
Authors: Xuanlin Li
Brandon Trabucco
Dong Huk Park
Michael Luo
Sheng Shen
Trevor Darrell
Yang Gao
Venue: ICLR 2021 Poster (2021)
Keywords: variational inference
unsupervised learning
computer vision
natural language processing
optimization
reinforcement learning

Abstract: The predominant approach for language modeling is to encode a sequence of tokens from left to right, but this eliminates a source of information: the order by which the sequence was naturally generated. One strategy to recover this information is to decode both the content and ordering of tokens. Some prior work supervises content and ordering with hand-designed loss functions to encourage specific orders or bootstraps from a predefined ordering. These approaches require domain-specific insight. Other prior work searches over valid insertion operations that lead to ground truth sequences during training, which has high time complexity and cannot be efficiently parallelized. We address these limitations with an unsupervised learner that can be trained in a fully-parallelizable manner to discover high-quality autoregressive orders in a data driven way without a domain-specific prior. The learner is a neural network that performs variational inference with the autoregressive ordering as a latent variable. Since the corresponding variational lower bound is not differentiable, we develop a practical algorithm for end-to-end optimization using policy gradients. Strong empirical results with our solution on sequence modeling tasks suggest that our algorithm is capable of discovering various autoregressive orders for different sequences that are competitive with or even better than fixed orders.

Published as a conference paper at ICLR 2021
DISCOVERING NON-MONOTONIC AUTOREGRESSIVE ORDERINGS WITH VARIATIONAL INFERENCE
Xuanlin Li; Brandon Trabuceo; Dong Huk Park, Michael Luo University of California, Berkeley
(xuanlinli17, btrabucco, dong. huk, park,,ark mi cichl 1uo jbrr
Sheng Shen, Trevor Darrell, Yang Gao
University of California, Berkeley; Tsinghua University {sheng.s, 3, trevordarrell (eaeeeeeeeeeeeeeeeeeee @ebereeeey edu, ey200738gmail.com
ABSTRACT
The predominant approach for language modeling is to encode a sequence of to- kens from left to right, but this eliminates source of information: the order by which the sequence was naturally generated. One strategy to recover this infor- mation is decode both the content and ordering of tokens. Some prior work supervises content and ordering with hand-designed loss functions to encourage specific orders bootstraps from a predefined ordering. These approaches require domain-specine insight. Other prior work searches over valid insertion operations that lead to ground truth sequences during training, which has high time complex- ity and cannot be efficiently parallelized. We address these limitations with an un- supervised learner that can be trained in a milly-parallelizatie manner to discover high-quality autoregressive orders in a data driven way without a Nomain-specifh prior. The learner a neural network that performs variational inference with the autoregressive ordering as a latent variable. Since the corresponding variational lower bound is not differentiable, we develop a practical algorithm for end-to-end optimization using policy gradients. Strong empirical results with our solution on sequence modeling tasks suggest that our algorithm capable of discovering various autoregressive orders for different sequences that competitive with even better than fixed orders.
INTRODUCTION
Autoregressive models have a rich history. Early papers that studied autoregressive models, such as (Uria et al., 2016) and (Germain al., 2015), showed an interest in designing algorithms that did not require gold-standas autoregressive order to be known upfront by researchers. However, these papers were overshadowed by developments in natural language processing that demonstrated the power of the left-to-right autoregressive order (Cho et al., 2014; Sutskever et al., 2014a). Since then, the left-to-right autoregressive order has been essential for application domains such as image captioning (Vinyals et al.. 2015b; Xu et al., 2015), machine translation (Luong et al., 2015; Bahdanau et al., 2015) and distant fields like image synthesis (van den Oord et al., 2016). However, interest in non left-to-right autoregressive orders is resurfacing (Welleck et al., 2019h; Stern et al., 2019), and evidence (Vinyals et al., 2016; Gü et al., 2018; Alvarez-Melis & Jaakkola, 2017) suggests adaptive orders may produce more accurate autoregressive models. These positive results make designing algorithms that can leverage adaptive orders an important research domain.
Inferring autoregressive orderings in a data-driven manner is challenging. Modern benchmarks for machine translation (Stahlberg. 2019) and other tasks (Oda et al., 2015) are not labelled with gold-standard orders, and left-to-right seems be the default. This could be explained if domain- independent methodology for identifying high-quality orders is an open question. Certain ap- proaches (Stern et al., 2019; Welleck al., 2019b; Ruis al., 2020) use hand-designed loss fune- as balanced binary trees. These loss functions incorporate
tions to promote a genre of
Authors contrihuted equally.

---

Published as a conference paper at ICLR 2021
certain domain- aasammiiissssmtiin:::: for example, they assume the balanced binary tree order will not dis- rupt learning. Learning disruption is an important consideration, because prior work shows that poor orders may prohibitively slow learning (Chen al., 2018). Future approaches to inferring autoregressive orders should withhold domain knowledge, to promote their generalization.
To our best knowledge, we propose the first conaain-nndependett unsupervised learner that discovers high-quality autoregressive orders through aully-aaallelizable end-to-end training without domain- specific tuning. We provide three main contributions that stabilize this learner. First, we propose an encoder architecture that conditions on training examples to output autoregressive orders using techniques combinatorical optimization. Second, we propose Variational Order Inference that learns an approximate posterior over autoregressive orders. Finally, we develop practical algorithm for solving the resulting non-differentiable ELBO end-to-end with policy gradients.
Empirical results with our solution on image captioning, code generation, text summarization, and machine translation tasks suggest that with similar hyperparameters, our algorithm capable of recovering autoregressive orders that are even better than fixed orders. Case studies suggest that our learned orders depend adaptively on content, and resemble a type of best-first generation order, which first decodes focal objects and names. Our experimental framework is available at this link.
RELATED WORKS
Autoregressive Models Autoregressive models decompose the generation of a high dimensional probability distribution by generating one dimension at time, with a predefined order. Combined with high capacity neural networks, this approach to modeling complex distributions has been very successful (Sutskever et al., 201 I; Mikolov et al., 2012). Recent works have achieved great im- provements with autoregressive models in many applications, including language modeling (Rad- ford et al., 2018; 2019; Brown et al., 2020), machine translation (Sutskever al., 2014b) and image captioning (Karpathy & Fei-Fei, 2015). Most previous works on autoregressive models use a fixed ordering pre-defined by the designer with left-to-right emerging as the primary choice. In contrast, our method is capable of learning arbitrary orderings conditioned on data and is more flexible.
Non-Monotonie Autoregressive Orderings Ford et al. (2018b) shows that sub-optimal ordering can severely limit the viability of a language model and propose to first generate partially filled sentence template and then fill in missing tokens. Previous works have also studied bidirectional decoding (Sun et al., 2017; Zhou et al., 2019; Mehri & Sigal, 2018) 8) and syntax trees based decoding (Yamada & Knight, 2001; Charniak et al., 2003; Dyer et al., 2016; Aharoni Goldberg, 2017; Wang et al., 2018) in the natural language setting. However, all of the works mentioned above do not learn the orderings and instead opt to use heuristics to define them. Chan et al. (2019) performs language modeling according to a known prior, such as balanced binary tree, and does not allow arbitrary sequence generation orders. Welleck et al. (2019a) proposes to use a tree-based recursive generation method to learn arbitrary generation orders. However, their performance lags behind that of left-to- right. Gu et al. (2019a) proposes Transformer-InDIGGO to allow non-monotonic sequence generation by first pretraining with pre-defined orderings, such left-to-right, then fine-tuning use Searched Adaptive Order (SAO) to find alternative orderings. They report that without pretraining, the learned orders degenerate. In addition, they perform beam search when decoding each token during training, which cannot be efficiently parallelized at the sequence length dimension. Emelianenko et al. (2019) proposes an alternative to SAO, but suffers from similar poor time complexity. In contrast, our method learns high-quality autoregressive orderings directly from data under silly--arallelizable end-to-end training.
Variational Methods Our method optimizes the evidence lower bound, or ELBO in short. ELBO a quantity that is widely used as an optimization proxy in the machine learning literature, where the exact quantity is hard to compute optimize. Variational methods have achieved great success in machine learning, such as VAË (Kingma & Welling, 2013) and 3-VAE (Higgins et al., 2017).
Combinatorial Optimization Recent works have studied gradient-based optimization in the com- binatorial space of permutations (Mena et al., 2018; Grover et al., 2019; Linderman et al., 2018). These works have been applied in tasks such as number sorting, jigsaw puzzle solving, and neural signal identification in worms. To our best knowledge, we are the first to build on these techniques to automatically discover autoregressive orderings in vision and language datasets.
2

---

Published as a conference paper at ICLR 2021
3 PRELIMINARIES
The goal of autoregressive sequence modelling is to model an ordered sequence of target values y (y), 1/2 ... 3n) y4 E R. possibly conditioned on an ordered sequence of source values x = (II, 221,,2...., Fm) æ; E IR, where (x, y) is sampled from the dataset D.
Inspired by Vinyals et al. (2015a) and Gu al. (2019a), formulate the generation process of y as a 2n step process, where at time step 2/ - we generate a value, and at timestep 2/. we select a not-yet-chosen position in 21 ........................ .n) insert the value. Thus, we introduce the latent sequence variable z = (21, 22 ................................ zn)) z E Sn, where Sn is the set of one-dimensional permutations of (1, ]. and 2 defined as the absolute position of the value generated time step
in the naturally ordered Then ply, z/x) denotes the probability of generating in the ordering of given the source sequence x. We can thus factorize ply, z/x) using the chain rule:
ply, x|xx = p(u=, (x)pp(x))(((/)/)) x) II p(ue, lees Mecis x)p(=sl Xx 1=2
For example, p(y1, 2/ defined as the probability of generating 1/2 in the first step, then inserting y2 into absolute position 2, then generating y1. and finally inserting 1/1 into absolute position 1.
2,
1/x) p(y2 xx) (=) 192, x)p((1 (21, y2, x)p (p(22] 22/22 21, 12.32.2 x) is
Note that in practice, the length of y is usually varied. Therefore, we do not first create fixed-length sequence of blanks and then replace the blanks with actual values. Instead, dynamically insert new value at position relative to the previous values. One common approach to predict such relative position is Pointer Network (Vinyals al., 2015a). In other words, at timestep at position ry relative to the previous generated values. Here, for any E Sn, r= (r1, (f1,T2,-- .2,..... (n) constructed such that there bijection between S, and the set of all constructed r. Due such bijection, we can use z and r interchangeaaly. We will use throughout the paper.
insert the value
4 VARIATIONAL ORDER INFERENCE (VOI)
Policy Gradient
log Pol y. x)
log pol Ye 3 an
Autoregressive Decoder
log po
V. m on 30
Ye
log q12 y.x)
z
Permute
Permutation Generator
X
Y2
322
Yz.
Figure 1: Computational Graph for Variational Order Inference
Starting from just the original data y in natural order, we can use variational inference create an objective (2) that allows us to recover latent order z, parametrized by two neural networks and Φb The encoder network e samples autoregressive orders given the ground truth data, which the decoder network 0 uses to recover y. More specifically, & is a non-autoreeressive network (permutation generator in Fig. 1) that takes in the source sequence x and the entire ground truth target sequence y and outputs latent order z in a single forward pass. 0 is an autoregressive network (autoregressive decoder in Fig. 1) that takes in and predicts both the target sequence y and the ordering through the factorization in Equation (1), We name this process Variational Order Inference (VOI).
py z|x)
D [log ps [x)] = B(x,y)=D log En-gg(zly.x))
(z x)
2 (x [Ea (a z 2|x)] + Hag (-ly,))
Here, H.g is the entropy term. During training, we train & and 0 jointly to maximize the ELBO in (2). During testing, we only keep the decoder 0.
3

---

Published as a conference paper at ICLR 2021
To optimize the decoder network 0 in (2), for each y, we first sample K latents 21, Z2..... ZK from x-). We then update using the Monte-Carbe gradient estimate
EynD K E Tologpoly.z.
Algorithm Variational Order Inference
1: Given: encoder network & with learning rate ag. decoder network 0 with learning rate cag. entropy coefficient B. batch of training data (X, Y) {(xx sampled from dataset D
2: Set gradient accumulators Je = 0, go = 0
3: for (x.y) (X, Y do
In practice, this is done through parallel tensor operations
4: X= -=)
5: Sample K doubly stochastic matrices B1, B2..... BR E Baxn from G.S.(X,))
6: Obtain Pt, Ps,..., .a....,PK Px E Pnxn from B1, B BR using Hungarian Algorithm
7:
Obtain latents Z1. Z2: 2K = Slaniy) (P1), F (P2), honty) (Pk)
8:
9e = Ge + N Li Ve logpe Pa (y: 211x)
9:
Calculate log q6
Zi
y x
(X, P.) log log(perm(es)) (exp (X)))
~ P.)
log (perm (xx)
10:
Calculate b(y,x)
R
Σ
i=1 log
11: 9s 9d N- Ei=1 V
log 20 22 (logpoly 2/(x) b(y, + + VoHa
12: end for
13: Φ = Ø a+
8 Oke go
Optimizing the encoder network is tricky. Since is a discrete latent variable, the gradient from log py z) does not flow through z. Thus, we formulate (2) in a reinforcement learning setting with a one-step Markov Decision Process (S, A, R). Under our setting, the state space S D: for each state (x,y) E D, the action space A(x,y) = Stengihly) with entropy term Hys (-ly,)); x); the reward function R(xx,y) y), E Slengthyy) = log (y, x/x). We can then set the optimization objective (Ø)) to be (2). In practice, we find that adding an entropy coefficient 3 and gradually annealing speed up the convergence of decoder while still obtaining good autoregressive orders.
To compute V ((). we derive the policy gradient with baseline formulation (Sutton et al., 2000):
VoL(Ø) E(xyy)< [E [V log go (zly, (log (y, z|x) b(y, x))] 3V H..
(3)
where b(y.x) x) is the baseline function independent of action z. The reason we use a state-dependent baseline b(y, x) instead of global baseline b that the the length of y can have wide range, caus-
ing significant reward scale difference. In particular, we set b(y, x) = Exzqs [log po (y: x/]x)]. If we
sample K 2 2 latents for each y, then we can use its Monte- Carlo estimate 1 K Σ log 2/(x).
Since we policy gradient to optimize 6, we still need closed form for the distribution x).. Before we proceed, we define Paxn as the set of n X n permutation matrices, where exactly one entry in each row and column is and all other entries are O; Baxn the set of doubly stochastic matrices, i.e. non-negative matrices whose sum of entries in each row and in each column equals 1; [R as the set of neg-negative X matrices. Note that we have the relationship Puxn C Baxn C B
To obtain qos (zlyy ()), we first write z in two-dimensional form. For each z E Sn, let (z E PaxX be constructed such that fn (Z); = one_hot(2;). where fz); is the i-th row of fn fz(z). Thus fn is a natural bijection from S, to Pnxxn. and we can rewrite qø as a distribution over Pnxn such that go (s (2) x) = qo (x)y,x).
Next, we need to model the distribution of qa(-ly, x). Inspired by (Mena et al., 2018), we model Is (-lly x) as Guubbe--atthing distribution G.M.(X) over PaxXs where X o(y, x) E Raxx the output of Φb Then for P E Pax.s
qo (s x) Go(Sn
qo x
exp (X,
xTace(X"P) P) is the Frobenius inner product of X and P. To obtain sam- ples in Puxn from the Gumbel-Matching distribution, (Mena et al., 2018) relaxes Paxn to Baxn by defining the Gunbel-Sinkhom distribution (.).(X.T) T over Baxns and proves that
where (X, P)F
4

---

Published as a conference paper at ICLR 2021
G.S.(X, 7) converges almost surely to G.M.(X) from (.M.(X), we first sample from G.S.(X, then apply Hungarian algorithm (Munkres, 1957) to obtain P E G.M.(X). Further details presented in Appendix A.
0+. Therefore, approximately sample
The Gumbel-Matching distribution allows us to obtain the numerator for the closed form of xx( (z( x), which equals exp (X, P)r- However, the denominator is in- tractable to compute and equals PPP.... exp (X, P) Upon further examination, we can express it perm(exp(X)) the matrix permanent of xxp(), and approximate it using perm g (exp(X (X), its Bethe permanent. We present details about matrix permanent and Bethe permanent along with the proof that the denominator of g x) equals perm(exp(XX) in Appendix B.
After we approximate qo. we can now optimize & using the policy gradient in (3), We present diagram of our architecture in Figure 1, and pseudocode of our algorithm in Algorithm 1. Note that even though latent space S, is very large and contains n! permutations, in practice, (y z (x) 2 po(y, z|x) Vz Sn, then po (y; z|x) tends to increase the edit distance between z and z decreases. Therefore, @ does not need to search over the entire latent to obtain good permutations, making variational inference over S, feasible.
5 EXPERIMENTS
Encoder and Decoder Architecture. We present encoder and decoder architectures for Variational Order Inference on conditional sequence generation tasks, which we focus in this work. Note that Algorithm is also applicable to unconditional sequence generation domains, such as image generation, through different encoder and decoder architectures. We leave this for future work.
For decoder 0, we use the Transformer-InDIGO (Gu et al., 2019a) architecture, which builds on Transformer with relative position representations (Shaw et al., 2018) to allow sequence generation through insertion operations. Note that "encoder" and "decoder" in this section refer to the two networks á and 0 in Algorithm I, respectively, instead of Transformer's encoder and decoder. Also, we obtain orderings through the output of encoder instead of through Searched Adaptive Order (SAO). To our best effort, we were unable to obtain the official implementation of Transformer- InDIGO, so we reimplemented the algorithm based on the paper's descriptions.
As a side note, rather than generating y autoregressively in 2n steps as done in Transformer-InDIGG. it is possible to use non-autoregressive decoder instead and improve the decoding speed. There have recently been many works on non- non-autoregressive conditional sequence generation (Gu et al., 2018; 2019b; Ma et al., 2019; Bao et al., 2019). To train a non -utoeetooeeeesiivve decoder Transformer, we can incorporate the ordering information generated by our encoder network into the decoder Transformer's 's encoder latent output. We leave this for future work.
For encoder ø, we adopt the Transformer (Vaswani et al., 2017) architecture. Note that our encoder generates latents based on the entire ground truth target sequence y. Therefore, does not need to mask out subsequent positions during attention. We also experiment with different position embed- ding schemes (see Section 7) and find that Transformer-XL's (Dai al., 2019) relative positional encoding performs the best, so we replace the sinusoid encoding in the original Transformer.
Tasks. We evaluate our approach on challenging sequence generation tasks: natural language to code generation (NL2Code) (Ling et al., 2016), image captioning, text summarization, and machine translation. For NL2CCde, we use Django (Oda et al., 2015). For image captioning, we use COCO 2017 (Lin et al., 2015). For text summarization, we use English Gigaword (Graff et al., 2003; Rush et al., 2015). For machine translation, we use WMT16 Nomanian-Engllis (Ro-En).
Baselines. We compare our approach with several pre-defined fixed orders: Left-to-Right (L22R (Wu et al., 2018), Common-First (Common) (Ford et al., 2018a), Rare-First (Rare) (Ford et al., 2018a), and Random-Ordering (Random). Here, Common-First order is defined generating words with ordering determined by their relative frequency from high to low; Rare-First order is defined as the reverse of Common-Firg order; and Random-Ordering Ordering is defined training with randomly sampled order for each sample at each time step.
Preprocessing. For Django, we adopt the same preprocessing steps described in (Gu et al., 2019a), and we use all unique words as the vocabulary. For MS-COCO, we find that the baseline in Gu et al. (2019a) is much lower than commonly used in the vision and language community. There-
5

---

Published as a conference paper at ICLR 2021
fore, instead of using Resnet-18, we use the pretrained Faster-RCNN checkpoint using ResNet-50 FPN backbone provided by Torch Vision to extract 512-dimensional feature vectors for each object detection. To make our model spatially-awann for every detection before feeding into our Transformers' encoder. For Gigaword and WMT, we learn 32k byte-pair encoding (BPE, Sennrich al. (2016)) tokenized data.
also concatenate the bounding box coordinates
Runtime Improvement
Runtime Insprovement
Runtime Improvementt
Tiue Per Step (Secoonds)
Speedup Foctor
Search Time
500
Training Method
Sequemes Langth (Thkeess)
Sequence Length (Tooomns)
Figure 2: Runtime performance improvement. We compare the runtime performance of VOI
(K = 4) with SAO on single Tesla P100 GPU, in terms of time per training iteration and ordering search time. VOI outputs latent orderings in single forward pass, and we observe a significant runtime improvement over SAO that searches orderings sequentially. The speedup factor linearly increases with respect to the sequence length.
MS-COCO
Django
Gigaword R-1 R-2 R-L BLEU
WMTI6 Ro-En Metcor TER
Order
BLEU
Meteor R-L CIDEr BLEU Accuracy
InDIGO SAO
29.3
24.9
54.5
92.9
42.6
32.9
32.5
53.0
49.0
Ours - Random
28.9
24.2
55.2
92.8
21.6
26.9
30.1
11.6
27.6
Ours L2R
30.5
25.3
54.5
95.6
40.5
33.7
35.6
17.2
33.2
32.7
54.4
50.2
Ours Common
28.0
24.8
55.5
90.3
37.1
29.8
33.9
15.0
31.1
27.4
50.1
53.9
Ours Rare
28.1
24.5
52.9
91.4
31.1
27.9
34.1
15.2
31.3
26.0
48.5
55.1
Ours VOI
31.0
25.7
56.0
100.6
44.6
34.3
36.6
17.6
34.0
32.9
54.6
49.3
Table I: Results of MS-COCO, Django, Gigaword, and WMT with fixed orders (L2R, Random, Common, Rare) as baseline. Here, R-1, R-1,R- R-2, and R-L indicate ROUGE-L, ROUGE-2, ROUGE-I,ROUGE,, and ROUGE- L. respectively. For TER, lower is better; for all other metries, higher is better. "_" not reported.
Training. For decoder, set dmwodel 512, daidden 2048, 6 layers for both Transformer's encoder and decoder, and 8 attention heads. This is the same model configuration as Transformer- Base (Vaswani al., 2017) and as described in Gu et al. (2019a). Our encoder also uses the same configuration. For our model trained with Variational Order Inference, we sample K = 4 latents for each training sample. An ablation on the choices of K is presented in Section For WMT, many previous works on nonsequential orderings (Stern et al., 2019) and nonautoregressive sequence generation (Gu et al., 2019b) have found sequence-level knowledge distillation (Kim & Rush, 2016) helpful. Therefore, we first train the L2R model on the original WMT corpus, then create new training corpus using beam search. We find that this improves the BLEU of VOI model by about 2. Even though the training set changed, the orderings learned by VOI are very similar to the ones trained on the original corpus. More detailed training processes are described in Appendix C.
During training, decoder can predict all tokens with their positions given by the latent ordering in one single forward pass. If we let N denote the batch size, 7 denote the length of each target sequence, and d denote the size of hidden vector, then one single forward pass of our model has computation complexity OdNKdl2) while Transformer-InDIGG trained with SAO has complexity O(Nd(3). Since K < I in general, our algorithm has better theoretical computational complexity during training. During evaluation, we only keep the decoder to iteratively generate the next position and token, which is as efficient as any standard fixed-orde autoregressive models.
encoder outputs the latent ordering through one single forward pass, and our
For InDGOO-SA, we report the results on COCO and Django trained using our own implementation. We did not attempt SAO on Gigaword or WMT due to the large dataset sizes, which can take 100 days to train. For WMT, we report the SAO result as in the original paper, and we follow their evaluation scheme (results are case-sensitive). The BLEU scores obtained through SacreBI EEU. Evaluation scripts are open-sourced.

---

Published as a conference paper at ICLR 2021
We also empirically compare VOI's runtime with that of SAO and fixed-order baselines (e.g. L2R). We implement SAO as described in Gu et al. (2019a). We test the runtime on a single GPU in order to accurately measure the number of ops required. For training speed per iteration, we use batch size of 8. For ordering search time, we use a batch size of to avoid padding tokens in the input for accurate measure. We observe that VOI is significantly faster than SAO, which searches orderings sequentially. In practice, as we distribute VOI across more GPUs, the K factor in the runtime is elfectively divided by the number of GPUs used (if we ignore the parallelization overhead), so we can achieve further speedups.
Results. We compare VOI against predefined orderings along with Transformer-IDDIG. trained with SAO in Table 1. The metrics we used include BLEU-4 (Papineni et al., 2002), Meteor (Denkowski & Lavie, 2014), Rouge (Lin, 2004), CIDEr (Vedantam et al., 2015), and TER (Snover et al., 2006). The "accuracy" reported for Django is defined as the percentage of perfect matches in code generation. Our results illustrate consistently better performance across fixed orderings. Most notably, CIDEr for MS-COCO, BLEU for Django, and Rouge-1 for Gigaword reveal the largest improvements in performance.
ORDER ANALYSIS
In this section, we analyze the generation orders learned by Variational Order Inference macro level by comparing the similarity of our learned orders with predefined orders defined in Section 5, and micro level, by inspecting when the model generates certain types of tokens.
Order Rank Correlation
Normalized Levenshtein Distance
1.0
Order
L2R
Metric
Common
Hare
Model
Bsseline-L2R
Sequence Length
Sequercee Langth
Figure 3: Global statistics for learned orders. We compare metrics as a function of the sequence length of generated captions the COCO 2017 validation set. On the left, we compare orders learned with Variational Order Inference to set of predefined orders (solid lines) using Order Rank Correlation. As reference, we provide the Order Rank Correlation between L2R and the same set of predefined orders (dashed lines). In the right plot, with identical setup. we measure Normalized Levenshtein Distance. We observe that Variational Order Inference favors left-to-right decoding above the other predefined orders-this corresponds to the blue lines. However, with max Order Rank Correlation of 0.6, appears left-to-right is not a perfect explanation. The comparably high Order Rank Correlation of 0.3 with rare-tokens-fiig first order suggests complex strategy.
6.1 UNDERSTANDING THE MODEL GLOBALLY
We find that prior work (Gu et al., 2019a; Welleck al., 2019a; Gu et al., 2018) tends to study autoregressive orders by evaluating performance on validation sets, and by visualizing the model's generation steps. We provide similar visualizations in Appendix F.3. However, this does not merit a quantitative understanding of the strategy that was learned. We address this limitation by introducing methodology to quantitatively study decoding strategies learned by non-monotonic autoregressive models. We introduce Normalized Levenshtein Distance and Order Rank Correlation, to measure similarity between decoding strategies. Given two generation orders w, z E S, of the same se- quence y, where is the length of y. we define the Normalized Levenshtein Distance.
DNLD (w, z) = lev (w, v2) /n
(5)
lev (w,z) z) + min {lev (WI.,)) z). lev (w, 21:) ,lev (Wi:; Z1:)
(6)
The function lev (w,2) 2) is the Levenshtein distance, and 21: removes the first element of z. This metric has the property that a distance of 0 implies that two orders w and z are the same, while a distance of 1 implies that the same tokens appear in distant locations in w and z. Our second metric Order Rank Correlation, is the Spearman's 's rank correlation coefficient between w and z.
DoRc (w,z) z) 1- 6 Ei= (w: 2:) (nr3 n)
7

---

Published as a conference paper at ICLR 2021
A correlation of 1 implies that and the same; correlation of -1 implies that and reversed; and a correlation of O implies that w and z are not correlated. Figure 3, we apply these metrics to analyze our models learnt through Variational Order Inference
Normalized Generation Index Of Tokens
1.0
Normalized Location
0.8
Model
0.4
Baseline L2R
0.2
<U0V NOUN
N.M
ADV
VERB
ADJ
PRT
ADP
CONJ
PRON
DET
Part Of Speech
Figure 4: Local statistics for learned orders. In this figure, evaluate the normalized generation indices for different parts of speech in model-predicted captions on the COCO 2017 validation set. The normalized generation index defined the absolute generation index particular token, divided by the final length of predicted sequence. The parts of speech (details in Appendix E) are sorted in ascending order of their average normalized location. We observe that modifier tokens, such "the", tend to be decoded last, while descriptive tokens, such as nouns and verbs, tend to be decoded first.
Discussion. The experiment in Figure 3 confirms model's behavior is not well explained by predefined orders. Interestingly, as the generated sequences increase length, the Normalized Lev- enshtein Distance decreases, reaching a final value of 0.57, indicating that approximately half of the tokens are already arranged according to a left-to-right generation order. However, the Order Rank Correlation barely increases, we can infer that while individual tokens are close to their left-to-right generation index, their relative ordering is not preserved. Our hypothesis is that certain phrases are generated from left-to-right, but their arrangement follows best-first strategy.
6.2 UNDERSTANDING THE MODEL LOCALLY
To complement the study of our model at global level, we perform similar study the micro token level. Our hope that a per-token metric can help us understand if and when our Variational Order Inference is adaptively choosing between left-to-right and rare-first order. We also hope to evaluate our hypothesis that Variational Order Inference is following a best-first strategy.
Discussion. The experiment in Figure 4 demonstrates that Variational Order Inference prefers decoding descriptive tokens first-such as nouns, numerals, adverbs, verbs, and adjectives. addi- tion, the unknown part of speech is typically decoded first, and find this typically corresponds to special tokens such as proper names. Our model appears to capture the salient content first, which is illustrated by nouns ranking second in the generation order statistics. For image captioning, nouns typically correspond to focal objects, which suggests our model has an object-detection phase. Evi- dence of this phase supports our previous hypothesis that best-first strategy is learned.
6.3 UNDERSTANDING THE MODEL VIA PERTURBATIONS
In this section, we study the question: to what extent is the generation order learned by Vari- ational Order Inference dependent on the con- tent the conditioning variable x? This ques- tion is important because simply knowing that our model has learned a best-first does not il- luminate whether that strategy depends only the target tokens being generated, or if also depends on the content of x. An adaptive gen- eration order should depend on both.
Geneerlis Order Seretivity
Image
31
Fasture Gamuar
Discussion. In this experiment, we first obtain a sequence y generated by our VOI given the source image x. We then freeze y, which allows the model infer generation order for y when
8

---

Published as a conference paper at ICLR 2021
different features of x are removed. Figure 6.3 shows that for a particular case, removing single region-feature (feature number O, which corresponds to the bus) from x changes the -reee-preddicted generation order by much as 0.7 Normalized Levenshtein Distance. These results confirm that our model appears to learn an adaptive strategy, which depends on both the tokens y being generated and the content of the conditioning variable x, which is an image in this experiment.
ABLATION STUDIES
In Section 5, introduced the specific encoder and decoder architectures we use for conditional sequence generation tasks, In this section, we present ablation stud- ies to support the architecture design of our encoder and modeling l with Gumbel- Matching distribution.
Table 2: Normalized Levenshtein Distance between the ordering learnt by the encoder and the ground truth ordering, under different positional encodings (enc) and modeling distributions of dø (distrib).
Enc Distrib
Gumbel- Gumbel-Matching Plackett-Luce
Sinusoid
0.40
0.62
Sinusoid Pos Attn
0.42
0.58
We consider 4 different positional encod- ing schemes for the encoder Transformer 6z: the sinusoid encoding in the original Trans-
Relative
0.38
0.53
XL-Reelttiee
0.25
0.57
former (Vaswani et al., 2017), the sinusoid encoding with positional attention module (Gu et al., 2018), the relative positional encoding in Shaw et al. (2018), and the relative positional encoding proposed in Transformer- X (Dai et al., 2019). Besides modeling (- X. y) as Gunbel-Matching distribution and using Bethe permanent approximate its denominator, we also consider modeling using Plackett-Luce distribution (Plackett, 1975; Luce, 1959) and sample using techniques recently proposed in Grover et al. (2019). Plackett-Luce distribution has tractable density, the exact is efficiently without using approximation techniques.
can compute
To analyze the encoder's ability to learn autoregressive orderings, we first train a decoder with Common-First order on one batch of MS-COCO until it perfectly generates each sentence. We then fix the decoder and initialize an encoder. We train the encoder for 15k gradient steps using the procedure in Algorithm I to recover the ground truth Common-Fing order, and we report the final Normalized Levenshtein Distanee against the ground truth Table 2. We observe that modeling ts with Gumbel-Matching distribution significantly outperforms modeling with Plackett- Luce, despite the former requiring denominator approximation. We also observe that under Gumbel Muubel-Matching modeling distribution, the relative position encoding in Transformer-XL significantly outperforms other encoding schemes. Thus we combine these two techniques in our architecture design.
In addition, analyze how the choice of K. the number of latents per training sample, affects model performance. We use the same setting as above and apply Transformer-X relative position encod- ing, and report the results in Table 3. We observe that the encoder more accurately fits to the ground truth order as K increases, until value of around 10. Since very large K can slow the model down while only bringing marginal improvement, a choice of K from 4 to 10 is sufficient.
Normalized Levenshtein Dis- tance between the encoder ordering and the ground truth with respect to the choice of K.
Table 3:
K 2 3
10 20
DNED 0.31 0.28 0.25 0.21 0.21
8 CONCLUSION
We propose, to our best knowledge, the first unsupervised learner that learns high-quality autore- gressive orders through pallleaarallllizable end-to-end training without domain-specific tuning. We propose a procedure named Variational Order Inference that uses the Variational Lower Bound with the space of autoregressive orderings as latent. Building on techniques in combinatorical optimiza- tion, we develop practical policy gradient algorithm to optimize the encoder of the variational objective, and we propose an encoder architecture that conditions on training examples to output autoregressive orders. Empirical results demonstrate that our model is capable of discovering au- toregressive orders that are competitive with or even better than fixed and predefined orders. In addition, the global and local analysis of the orderings learned through Variational Order Inference suggest that they resemble a type of best-first generation order, characterized by prioritizing the generation of descriptive tokens and deprioritizing the generation of modifier tokens.

---

Published as a conference paper at ICLR 2021
REFERENCES
Roce Aharoni and Yoav Goldberg. Towards string-to toetreet--reeeeeeee tree neural machine translation. arXiv preprint
1741:.7700.44433 2017.
David Alvarez-Melis and Tommi S. Jaakkola. Tree-structured decoding with doubly-recurrent neural networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: /ttp://ppppee wpwp//veeeeeeeeeeeeeeeeeee.eeewe net/
Nima Anari and Alireza Rezaei. A tight analysis of bethe approximation for permanent. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1434-1445, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Con- ference Track Proceedings, 2015. URL http: / aaaaaaiiivo.... org/ abs / 1009944900000 0473.
Yu Bao, Hao Zhou, Jiangtao Feng, Mingxuan Wang. Shujian Huang, Jiajun Chen, and Lei LI. Non- autoregressive transformer by position learning. 2019.
Tom B Brown, Benjamin Mann. Nick Ryder, Melamie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. /4 165, 2020.
William Chan, Nikita Kitaev, Kelvin Guu, Mitchell Stern, and Jakob Uszkoreit. Kermit: Generative intertionbbase modeling for sequences, 2019.
Eugene Charniak, Kevin Knight, and Kenji Yamada. Syntax-based language models for statistical machine translation. In Proceedings of MT Summit IX, pp. 40-46. Citeseer, 2003.
Xi Chen, Nikhil Mishra, Mostafa Rohaninejad, and Pieter Abbeel. Pixelsnail: An improved au- toregressive generative model. In Jemnifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 863- 871. PMLR, 2018. URL http: / http:/ppoceeeegggeeeeeeee mlr. pwwss/v80 chccchhennhh html.
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Alessandro Moschitti, Bo Pang, and Walter Daelemans (eds.), Proceedings of the 2014 Conference Empirical Methods in Natural Language Pro- cessing. EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special doi: 10.3115/v1/d14-1177, URL
Interest Group of the ACL, pp. 1724 1734. ACL, 2014.
https: //doi .org/1........ 101/111.1151 1...3115vvl/oo
Zihang Dai, Zhilin Yang. Yiming Yang. Jaime Carbonell, Quoe Le, and Ruslan Salakhutdinov. Tra Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting the
the Association for Computational Linguisties. pp. 2978 2988, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v 1/t19////991111111 1285. URL https:/ / www. . acl web. org/ /etthontooooooo wwwphhoooyyy/oo
ogy/o1l///////o /P//// 90128515555
Michael Denkowski and Alon Lavie. Meteor universal: Language specific translation evaluation for any target language. In Proceedings of the EACL 2014 Workshop on Statistical Machine Translation, 2014.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A Smith. Recurrent neural network grammars. arXiv preprint vrXiv:1602.00776, 2016.
Dmitrii Emelianenko, Elena Voita, and Pavel Serdyukov. Sequence modeling with un- constrained generation order. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' d'Alhee- Emily B. Fox, and Roman Garnet (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neural In- formation Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancou- ver, BC, Canada, pp. 7698-7709, 2019. URL http:/ /tto://papzaa nips cc/paper/ 8986 8986- 126-ssquence-model tanccnn ion.
10

---

Published as a conference paper at ICLR 2021
N. Ford, Daniel Duckworth, Mohammad Norouzi, and G. Dahl. The importance of generation order in language modeling. ArXiv, abs/1808. 01111808.09900 2018a.
Nicolas Ford, Daniel Duckworth, Mohammad Norouzi, and George Dahl. The importance of generation order in language modeling. arXiv preprint arXiv: teXivv:8088.01 878.009900, 2018b.
Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. Made: Masked autoencoder for distribution estimation. volume 37 of Proceedings of Machine Learning Research, pp. 881-889, Lille, France, 07-09 Jul 2015. PMLR. URL http: http:://proceee http///oooeiicceooooooooooooo.ce www..ng.........ee.eeemmm p.p..///////////
ml
germain15 html.
David Graff, Junbo Kong, Ke Chen, and Kazuaki Maeda. English gigaword, 2003.
Aditya Grover, E. Wang, Aaron Zweig, and S. Ermon. Stochastic optimization of sorting networks via continuous relaxations. ArXiv, abs/1903.08850, 2019.
Jetic Gü, Hassan S. Shavarani, and Anoop Sarkar. Top-down tree structured decoding with syntactic connections for neural machine translation and parsing. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 401-413, Brussels, Belgium, October- November 2018. Association for Computational Linguistics. doi: 1118653//1/DD55 1-37780077 URL https: www wwwwwblwwbb........... orq/ hetpg//nnhoogyy// /
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O. K. Li, and Richard Socher. Non- autoregressive neural machine translation. In 5th International Conference on Learning Rep- resentations, 2018.
Jiatao Gu, Qi Liu, and Kyunghyun Cho. Insertion-based decoding with automatically inferred gen- eration order. Transactions of the Association for Computational Linguistics, 7:661-676, 2019a.
Jiatao Gu. Changhan Wang, and Junbo Zhao Levenshtein transformer. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 11181-11191, Curran Asso- wttpeeeeeiinn...eeiiieeeeeeeeeee neurips...... wtt..cc/pppppeee pttp://sccccppppp////////////// wttpp//pppp/////ieeeeeeeeee ciates, Inc., 2019b. URL 755-59944777789966666666 Paweed666-PPap.pppdppp Paper.pdf. 6758982068 www.e225500ooooooooceooooooaoeaa 7b2 000488900666666
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: http//ppeevvvveeeeeeeeeeeeeeeeee wtt.:/eettoddddaaeeeeeaaa
Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descrip- tions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 3128-3137,201 2015.
Yoon Kim and Alexander M. Rush. Sequence-level knowledge distillation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1317-1327, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/
URL httph:://// /tops::/wwww
www. acl web. argg/anthlogyyyooooooo /D1 (-16-/11111111 1139.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //aaxiiv.rr/////e/..a.......aeae
1412. 6980.
Diederik P Kingma and Max Welling, arXiv: 2013.
Auto-encoding variational bayes.
arXiv preprint
Chin-Yew Lin. ROUGE: A package for automatic evaluation of summaries. In Text Summarization Branches Out, pp. 74-81, Barcelona, Spain, July 2004. Association for Computational Linguis- tics. URL https: www. acl web. org/ http://nnhooolgy/ooe

---

Published as a conference paper at ICLR 2021
Tsung- Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, and Piotr Dollár. Microsoft coco: Common objects in context, 2015.
Scott Linderman, Gonzalo Mena, Hal Cooper, Liam Paninski, and John Cunningham. Reparame- terizing the birkhoff polytope for variational permutation inference. volume 84 of Proceedings of Machine Learning Research, pp. 1618 1627, Blancc, Blanca, Lanzarote, Canary Islands, 09-1 Apr mir. wwwss/ https////////////eeeeeeeee linderman 8a html.
2018. PMLR. URL http: huttt::/ppee http:p::/ppcceeedneeeooo
W. Ling, P. Blunsom, Edward Grefenstette, K. Hermann, Tomás Kociský, Fumin Wang, and A. Se- nior. Latent predictor networks for code generation. ArXiv, abs/1603.06744, 2016.
R. Duncan Luce. Individual Choice Behavior: A Theoretical analysis. Wiley, New York, NY, USA, 1959.
Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches attention- based neural machine translation. In Lluís Märquez, Chris Callison-Buree Burch, Jian Su, Daniele Pighin, and Yuval Marton (eds.). Proceedings of the 2015 Conference on Empirical Methods Natu- ral Language Processing, EMNLP 2015, Lisbon, Portugal, September 17-21, 2015, pp. 1412- 1421. The Association for Computational Linguisties, 2015. doi: 10.18653/v1/d15-1111 URL https: / /wi. www.ioorg11... 111111...13//// 3vvl/ a11-1166.
Xuezhe Ma, Chunting Zhou, Xian Li, Graham Neubig, and Eduard Hovy. FlowSeq: Non- autoregressive conditional sequence generation with generative flow. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th In- ternational Joint Conference on Natural Language Processing TEMNLP-IJCNLA pp. 4282- 4292, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/v1/D11-144 URL https:: www. ac web. weeeb.org//ate has//anhhooggyy//ba
Shikib Mehri and Leonid Sigal. Middle-out decoding. In Advances in Neural Information Process- ing Systems, pp. 5518-5529, 2018.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with sinhho- networks. International Conference on Learning Representations, 2018. URL htnttps://openreevisee net htt.://eeettforrrt////eee forum? 1d=Byt3oJ-OR,
Gonzalo Mena, Erdem Varol, Amin Nejatbakhsh, Eviatar Yemini, and Liam Paninski. Sinkhorn permutation variational marginal inference. volume 118 of Proceedings of Machine Learning Research, pp. 1-9. PMLR, 08 Dec 2020. htt.tttpp/ppoocee ngg mlr. press/v118/ mer.22aa. html.
Tomáš Mikolov al. Statistical language models based on neural networks. Presentation at Google, Mountain View, 2nd April, 80:26, 2012.
James R. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32-38, 38, March 1957.
Yusuke Oda, Hiroyuki Fudaba, Graham Neubig, Hideaki Hata, Sakriani Sakti, Tomoki Toda, and Satoshi Nakamura. Learning to generate pseudo-code from source code using statistical machine translation. In Proceedings of the 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), ASE '15, pp. 574-584, Lincoln, Nebraska, USA, November 2015. IEEE Computer Society. ISBN 978- 1-5090-0025-8, doi: 10.1109/ASE.0015.36. URL https: //doi. /0lrg/10... 1109/11000001 / ASE 2015.36.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic
evaluation of machine translation. In Proceedings the 40th Annual Meeting of the Associa- tion for Computational Linguistics, pp. 311-318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 10.3115/10730331077133. URL https: // aclweb org/
1040.
Robin L Plackett. The analysis of permutations. pp. 193-202, 1975.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training, 2018
12

---

Published as a conference paper at ICLR 2021
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 1(8):9, 2019.
Laura Ruis, Mitchell Stern, Julia Proskurnia, and William Chan. Insertion-deletion transformer. CoRR, abs/2001 1.55000000, 2020. URL https: /wtp/vaaavvvvaaa//aaa/ee.eaaaa http://b/22000500//1
Alexander M. Rush, Sumit Chopra, and Jason Weston. A neural attention model for abstractive sentence summarization. Proceedings of the 2015 Conference on Empirical Methods Natural
Language Processing, 2015. doi: (0.18653//1/d11--0444 URL http://tttst doi. org/o1
18653/v1/D15 1044.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 1.118633/11/P1-1166 URL https: /www. ac web. org/ ses/anthhlogyyP110 1162.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Pupers), pp. 464-468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 11111163/11N/11-//1 2074. URL https:://// / www aclweb. org/
Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastie ma- trices. Ann. Math. Stutist., 35(2):876-879, 06 1964. doi: (//114//mm//17777033))) URL
https:://oi.... wwwddo..org.oo worg/ 00.//1..11111 aomo /
Matthew Snover, Bonnie Dorr, Richard Schwartz, Linnea Micciulla, and John Makhoul. A study of translation edit rate with targeted human annotation. In In Proceedings of Association for Machine Translation the Americas, pp. 223-231, 2006.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. 15(1):1929-1955 January 2014. ISSN 1532-4435.
Felix Stahlberg. Neural machine translation: A review. ArXiv, 1b2/191..00047 2019.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible sequence generation via insertion operations. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICMI, 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5976-5985. PMLR, 2019. URL http::/ppocceedinnnee wwt.smmr...pprr. press//99// stern19 9a. html.
Qing Sun, Stefan Lee, and Dhruv Batra. Bidirectional beam search: forward-backward inference in neural sequence models for fill-n-thhebllnnk image captioning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6961-6969, 2017.
Ilya Sutskever, James Martens, and Geoffrey E Hinton. Generating text with recurrent neural net- works. In ICML, 2011.
Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence to sequence learning with neural networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: An- nual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Mon- treal, Quebec, Canada, pp. 3104-3112, 2014a. URL http: http::///ppppeaaeeee nips cc/ cttccc//pppp/ cc/paper///pcppccc 5346 wee---seuueeeeeeeeeeeeeeeeeeeeee to to-tso--eseeeeeeee -
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104-3112 2014b.
13

---

Published as a conference paper at ICLR 2021
Richard S Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. A. Solla,
T. K. Leen, and K. Müller (eds.). Advances in Neural Information Processing Systems
12, pp. 1057-1063. MIT Press, 2000. URL http:/ /ttp::/ppperrsee nips. cc wttp:pec//ppp///eeeeeeeeeeee.eet pdf.
for- peappplicyygraaaeeee-eeeeeeeeeee hoaere/e-oorrrttfffeeeeeeeeeeeea wtw.rnnggttttfffiiioooooooo.oo funct -ow.
Benigno Uria, Mare-Alexandre Côté, Karol Gregor, lain Murray, and Hugo Larochelle. Neu- ral autoregressive distribution estimation. J. Mach. Learn. Res., 17:205:1 2016. URL http:// pttp://rr/pppeee//////1/-2222220
Aäron van den Oord, Nal Kalchbrenner, Lasse Espeholt, Koray Kavukcuoglu, Oriol Vinyals, and Alex Graves. Conditional image generation with pixelenn decoders. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg. Isabelle Guyon, and Ro- man Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 4790-4798, 2016. URL http:/ http://papers papprsp.ersssse//// nips. ccs.cc/ppaa 6527- 1027-conditionale iimae-ma-e-ee- generation with-pixelcne decoders,,
paper/ ctpppc/ppperr//////ppppppppp.pep
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neu- ral Information Processing Systems 30, pp. 5998-6008. Curran Associates, Inc., 2017. URL i--alllll alll -you- pdd.
http:/ pett::/paapers httpppapppppppeee/eeeeeeeeeeee.p .atrrs.iipss. nips. cc/ sec//appr/// /71 811 -
Ramakrishna Vedantam, C. Lawrence Zitnick, and Devi Parikh. Cider: Consensus-based image description evaluation. In CVPR, pp. 4566-457, IEEE Computer Society, 2015. ISBN 978-
1-4673-6964-0. URL http:/ /tt:///bll /bblp.bpp... uni toii-rre ceii-trreer.. de/ dbb cttp//////////////11111 html [een1##edattammPP1.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Sys- tems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2692-2700, 2015a. URL www.nnteereeee.......... Stt
http:/ fttt:://paaeree wwwppaappppepaa/ ps ce/ wwwpppappp6....
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA. USA. June 7-12, 2015, pp. 3156-3164. IEEE Computer Society, 2015b. doi: 10. 1109/CVPR.20115.298833. URL https: / / doii org/10. 1109/CVPR. 2015. 7298935.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representa- tions, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Truck Proceedings, 2016.
URL http: / /aaaaiiiii..////////.aaa//aaaavv org/ abs/ 1tt.:111111101 06391.
P. O. Vontobel. The bethe permanent of a non-negative matrix. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 341-346, 2010.
Xinyi Wang. Hieu Pham, Pengcheng Yin, and Graham Neubig. A tree-based decoder for neural machine translation. arXiv preprint arXiv:I808 09374, 2018.
Sean Welleck, Kianté Brantley, Hal Daumé III, and Kyunghyun Cho. Non-monotonic sequential text generation. arXiv preprint arxiv /etp/9922200. 0922, 2019a.
Sean Welleck, Kianté Brantley, Hal Daumé III, and Kyunghyun Cho. Non-monotonic sequential text generation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Cali- fornia, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6716-6726, PMLR, 2019b. URL
ngs ml wtw.s//svv v97 / wel leck1 9a html.
14

---

Published as a conference paper at ICLR 2021
Lijun Wu, Xu Tan, Di He, Fei Tian, Tao Qin, Jianhuang Lai, and Tie- Yan Liu. Beyond error propagation in neural machine translation: Characteristics language also matter. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 3602-3611, Brussels, Belgium, October-November 2018. Association for Computational Linguistics. doi: wwtpw/..g/athooooggggoo////////e httpthhhloy///1-111/ N0.18653/11/118-1330 URL hwwpt:ttp//ccc /wwww acl web orgg hts./anhoollggg.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhutdinov, Richard S. Zemel, and Yoshua Bengio, Show, attend and tell: Neural image caption generation with visual attention. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, vol- ume of JMLR Workshop and Conference Proceedings, pp. 2048-2057. JMLR.org, 2015. URL http: http::/proceeeeeee pptpe/dccceeeeeeeooooeoe .mlr, ppwss/v37 htcp//////xucllcc html.
Kenji Yamada and Kevin Knight. A syntax-based statistical translation model. In Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics, pp- 523-530, 2001.
Long Zhou, Jiajun Zhang, and Chengqing Zong. Synchronous bidirectional neural machine transla- tion. Transactions of the Association for Computational Linguistics, 7:91-105, 2019.
15

---

Published as a conference paper at ICLR 2021
APPENDIX
A GUMBEL-MATCHING DISTRIBUTION AND ITS SAMPLING
In Section 4, We model the distribution of (- Gumbel-Matching distribution (.M.(X)
over PaXn. where X = <(y,x) E æaxx is the latent output.
To obtain samples in PAXn from the Gumbel-Matching distribution, Mena et al. (2018) relaxes Puxn to BRxn by defining the Gumbel-Sinkhorn distribution G.S.(X,)) T > over Baxn- Here reproduce the following definitions and theorems with similar notations from Sinkhorn (1964)
and Mena et al. (2018):
Definition A.1. Let X Raxn and A Baxwn The Sinkhorn Operator defined as
Tx(A) 0 (A1,,1))
(8)
To(A) = A (1
(9)
T(A) (T(((A))
(10)
S(X) = lim T (exxp(XX)
(11)
2-000
Here, Ø is the element-wise division between two matrices, and T, and Te row and column normalizations a non-negative matrix, respectively. Therefore, iteratively applying T is equivalent to iteratively normalizing non-negative matrix by column and row.
Theorem A.2. (Sinkhorn, 1964) The range of S is Baxn-
Theorem A.3. (Mena et al., 2018) Let E Baxn; > The Gumbel-Sinkhorn distribution G.S.(X,r) r) is defined as follows:
X =( T
(12)
where is a matrix of i...d. standard Gumbel noise. Moreover, G.S.(X,T) converges almost surely to G.M.(X) as - 0
To approximately sample from GXM. we first sample from G.S.(X,7). Even though theoreti- cally, T needs to be applied infinite number of times to obtain matrix in Bnxn. Mena et al. (2018) reports that 20 iterations of T enough in practice. We find that in our experiments, 20 iterations are not enough to obtain a matrix in Baxn= but 100 200 iterations are enough. After we obtain the matrix in Baxn. we apply Hungarian algorithm (Munkres, 1957) to obtain P G.M.(().
Finally, we need to calculate the entropy term Hgg in Lg in Equation 3. This can be approximated using the technique Appendix B.3 of Mena al. (2018).
B MATRIX PERMANENT AND ITS APPROXIMATION WITH BETHE PERMANENT
In this section, we present details about matrix permanent and bethe permanent, which we use as an approximation the denominator of x)),
Definition B.I. Let A E B.xnn The permanent of A is defined as follows:
perm(A]
Σ
II
A
(13)
oES, i=1
Theorem B.2. The denominator of go( (-lly, equals perm(exp(X))
16

---

Published as a conference paper at ICLR 2021
Proof.
Σ PEPaXE
ex, P\r
(X, = Σ expl Xio()))
dESn
Σ
II
(exp(X))
rE i=1 = perm permmexp((X) exp(X))
Definition B.3. (Vontobel, 2010; Anari & Rezaci, 2019) Let A E 1 The bethe permanent of is defined as follows:
perm B (A) exp
max
E(ns
log Aig - Ti.j log 7..j + (1 Ho) (1 Ri))))
(14)
BEB.XM km
1.
Theorem B.4. (Anari & Rezaei, 2019) Let A E R Then, v2 "eer((A) I (erm = (erm(A).
The y in Definition B.3 can be calculated using the message passing algorithm in Lemma 29 of Vontobel (2010). An efficient implementation has recently been introduced in Appendix C of Mena et al. (2020). Therefore, we can use perm & (exp (X)) to approximate the denominator of ( x), and we can then use policy gradient compute V (ob in Equation (3).
C DETAILED TRAINING PROCESS AND HYPERPARAMETER SETTINGS
For all experiments, we apply dropout = 0.1 (Srivastava et al., 2014) and label smoothing 0.1. We apply Adam Optimizer (Kingma Ba, 2015) with 33 0.99, 32 0.999 for MS-COCO, and 81 = 0.99, A2 0.98 for all other tasks. For baseline experiments, we use a batch size of 64 for Django and MS-COCO, and 128 for Gigaword and WMT. We decrease the learning rate linearly from le-4 to zero. We train the baseline until the performance plateaus.
For our VOI model, we train on Django for a total of 350 epochs (120k gradient steps), MS-COCO for 20 epochs (350k gradient steps), Gigaword for 16 epochs (1M gradient steps), and WMT16 Ro- En for 120 epochs (1.3M gradient steps). We use a batch size of 36 for MS-COCO and Django, 50 for Gigaword, and 54 for WMT. We sample K
latents per training sample for the first three datasets, and K = 3 for WMT. Due to constraints in computational resource, we were unable to scale WMT larger batch size and larger K. We also did not experiment with larger batch size for COCO, Django, and Gigaword. We leave the investigations of larger batch sizes and larger K for future work.
We set the initial decoder learning rate to be 5e-5 and the encoder learning rate to be 5e-6. We train the VOI encoder and decoder with shared embedding for about the first 15-20% of steps (i.e. 4 epochs for COCO, 50 epochs for Django, 3 epochs for Gigaword, and 20 epochs for WMT). We then separate the embeddings for the rest of the training steps. When the embedding shared, we set the entropy coefficient = 0.3 for all tasks.
After we separate the embeddings, for MS-COCO, we anneal with log-linear schedule from 0.3 to 0.03. We decrease the learning rate to (3e-5, 3--6) for the decoder and the encoder respectively after epoch 13, when the encoder starts to sample very similar permutations for a single training data. We observe that training either VOI or the fixed ordering models for too long leads to overfitting. Finetuning VOI with the encoder fixed does not help and causes the performance to slightly drop.
For Django, set the learning rates to be (3e-5, 3c-6). We log-anneal 3 to 0.03 for the first 90% of steps and then anneal 3 to 0.003 for the rest of the steps. We find that the latter allows the encoder to commit to single ordering sequences of longer length and slightly improves performance. We finally fix the encoder and finetune the decoder for 50 epochs with a larger batch size 64 and learning rate linearly annealing zero. This finetuning step improves the BLEU score by about 0.6.
For Gigaword and WMT, we add a cosine alignment loss between the decoder and the encoder's embedding matrices to the loss of the encoder. We the cosine alignment loss coefficient to be
17

---

Published as a conference paper at ICLR 2021
Loss
Less
Paener
Peadara
Layer
Grudirts dig
Pormusation
Autreggent
Self
Crees
[erarh a baer SWin
[ COENTD a Bite Ehvinn
Figure 5:
This figure demonstrates our algorithm for an image captioning task. The model on the left is the Permutation Transformer, which maps training examples to permutation matrices. The model on the right is an autoregressive model that learns to predict tokens and positions.
100.0 for Gigaword and 10.0 for WMT. Intuitively, since the Gigaword and WMT vocabularies are much larger than those of MS-COCO and Django, and they contain many rare words, this loss allows the encoder leverage the semantic information recently-leamm from the decoder better discover autoregressive orderings.
For Gigaword, we anneal 3 log-linearly from 0.3 to 0.03 in epochs (500k gradient steps). We then fix the encoder and fine-tune the decoder with batch size of 128 for epochs with learning rate linearly decreasing from 7e-5 to We observe that, compared to COCO and Django, this finetuning step significantly improves VOI's performance and raises the ROUGE score by around 1.5 to 2.0.
For WMT, we anneal / linellly from 0.3 to 7e-4 80 epochs (900k gradient steps). We decrease the learning rates from (5e-5, 5e-6) to (3e-5, 36-6) at epoch 40 when the encoder starts sampling very similar permutations. We then fix the encoder and finetune the decoder with a batch size of 128 for 20 epochs with learning rate linearly decreasing from 3e-5 to O. We observe that this finetuning step also significantly benefits VOI's performance and improves the BLEU score by around 1.5 points.
Due resource constraints, did not fully, and we leave the discovery of better training schemes for future work.
hyperparameters and training schedules very care-
D EXAMPLE ARCHITECTURE FOR CONDITIONAL SEQUENCE GENERATION
In Section 5, we introduced the specific encoder and decoder architectures used for the conditional sequence generation tasks in our paper. To further illustrate the architecture of Variational Order Inference, we present diagram the architecture instantiated for COCO 2017.
E PARTS OF SPEECH MAPPINGS
The parts of speech used in Order Analysis section correspond the NLTK Universal Tagset. In the below table, we provide mappings for the tag identifiers used in our main paper. More in- formation about the specific NLTK tags can be found at the following url: http: www..llk.. org org/book// ch05 html.
F VISUALIZATIONS OF SEQUENCE GENERATION
F.1 COCO
We visualize the generation order inferred by Variational Order Inference for COCO. Sequences are generated using beam search over both tokens and their insertion positions, using a beam size of 3. Bounding boxes that correspond to region-features calculated using bottom-up attention superimposed on the image, with an opacity value proportional to the magnitude of their softmax attention value in the final cross-attention layer in the language model.
18

---

Published as a conference paper at ICLR 2021
Tag
Meaning
English Examples
ADJ
adjective
new, good, high, special, big, local on, of, at, with, by, into, under really, already, still, early, now and, or, but, if, while, although the, some, most, every, no, which year, home, costs, time, Africa twenty-four, fourth, 1991, 14:24 at, on, out, over per, that, up, with he, their, her, its, my, us is, say, told, given, playing, would :
ADP
adposition
ADV
adverb
CONJ
conjunction
DET
determiner, article
NOUN
noun
NUM
numeral
PRT
particle
PRON
pronoun
VERB
verb
punctuation marks other
X
ersatz, esprit, dunno, gr8, univeristy
Table 4: NLTK Universal Tagset.
Image 000000036539
people
people
snow
two people
snow
people standing
two people standing in snow
two people standing in snow
people
standing standing in snow snowboards
snow snowboards
two people
two
people
standing
in the snow on snowboards
Figure 6: Generation order inferred by Variational Order Inference. Without supervision over its generation order, nor domain-specifie initialization, a prior aid learning, the model learns adaptive strategy that prioritizes object names in this case, people and snow.
Decoded Text
woman
Image 000000000785
riding
riding skis
woman riding skis down
woman riding skis down snow
woman riding skis down snow
slope
woman riding skis down show
covered
slope
woman
riding
skis down
snow
covered
slope
Figure 7: Generation order inferred by Ours-VOr VOI for image from the COCO 2017 validation set with the image identifier 000000000785.
19

---

Published as a conference paper at ICLR 2021
Decoded Text
Image 000000000802
kitchen
kitchen
cabinets
kitchen
cabinets
a kitchen
with
cabinets
kitchen with
cabinets
kitchen with
cabinets
appliances
kitchen with cabinets and appliances
kitchen with
cabinets and white
appliances
kitchen with
white
cabinets and
white appliances
Figure 8: Generation order inferred by Ours-VOI for an image from the COCO 2017 validation set with the image identifier 000000000802.
Decoded Text
person
person
ledge
Image ID: 000000001268
person
ladge
person
standing
ladge
person
standing
on
ledge
person
standing
ledge
person
standing
ledge
water
person
standing
ledge near
person
standing
ledge
person
standing
ledge
Figure 9: Generation order inferred by Ours-VOI for an image from the COCO 2017 validation set with the image identifier 000000001268.
20

---

Published as a conference paper at ICLR 2021
Decoded Text
Image ID: 000000001296
woman
woman
phone
woman
phone
woman
holding
phone
woman holding
cell phono
woman holding
cell phone
woman holding
cell phone
hand
woman holding
phone
holding
holding
Figure 10: Generation order inferred by VOrs-VOI for an image from the COCO 2017 validation with the image identifier 000000001296.
Decoded Text
desktop
desktop
laptop
Image ID: 000000001503
desktop
laptop
desktop
computer
laptop
desktop
computer
with
laptop
desktop
computer
with
laptop
desktop
computer
with
laptop
desk
desktop
computer
laptop
desktop
computer
laptop
desktop
computer
laptop
Figure 11: Generation order inferred by Ours-VOI for an image from the COCO 2017 validation with the image identifier 000000001503.
21

---

Published as a conference paper at ICLR 2021
Decoded Text
bedroom bad
Image ID: 000000001993
bedroom bed
bedroom with bed
bedroom with bed
bedroom with bed table
bedroom with bed and table
bedroom with
table
bedroom
with bed and table
Figure 12: Generation order inferred by Ours-VOI for an image from the COCO 2017 validation set with the image identifier 000000001993.
Decoded Text
young
Image ID: 000000000785
young
young
person riding
young
riding skis
young
person riding skis on
young person riding skis
young
person riding
snowy
young
person
riding
skis
snowy
slope
Figure 13: Generation order inferred by Ours-L.2R for an image from the COCO 2017 validation with the image identifier 000000000785.
22

---

Published as a conference paper at ICLR 2021
Decoded Text
Image 000000000802
kitchen
kitchen with
a kitchen with white
kitchen with white appliances
kitchen with white appliances and
kitchen with white appliances and wood
kitchen with white appliances and wood
cabinets
kitchen with
white
appliances and wood cabinets
Figure 14: Generation order inferred by Ours-L2R for an image from the COCO 2017 validation with the image identifier 000000000802.
Decoded Text
couple
Image ID: 000000001268
couple of
couple of people
couple of people that couple of people that are couple of people that are sitting couple people
sitting
couple people that sitting
couple
people
sitting
Figure 15: Generation order inferred by Ours-I.2R for an image from the COCO 2017 validation with the image identifier 000000001268.
23

---

Published as a conference paper at ICLR 2021
Decoded Text
Image ID: 000000001296
woman in
woman In crowd
crowd Is
woman In crowd Is using
crowd is using her
woman crowd Is using her cell
woman crowd is using her cell phone
woman crowd is using her cell
phone
Figure 16: Generation order inferred by Ours-L2R for an image from the COCO 2017 validation with the image identifier 000000001296.
Decoded Text
desktop
Image ID: 000000001503
desktop
computer
a desktop
computer
sitting
a desktop
computer
sitting on
desktop
sitting on top computer
desktop
computer
sitting on top of sitting top sitting top
desktop
computer
desktop
computer
desktop
computer
sitting
top
Figure 17: Generation order inferred by Ours-I.2R for an image from the COCO 2017 validation with the image identifier 000000001503.
24

---

Published as a conference paper at ICLR 2021
Decoded Text
bed
Image ID: 000000001993
bed and
a bed and
bed and table
bed and table
bed and table
bed and table room
bed and table room
Figure 18: Generation order inferred by Ours-L2R for an image from the COCO 2017 validation with the image identifier 000000001993.
Decoded Text
Image ID: 000000000785
on the
in the
person in
person some in the
person
snow
person
some
skis In the snow
Figure 19: Generation order inferred by Ours-Common for an image from the COCO 2017 valida- tion set with the image identifier 000000000785.
25

---

Published as a conference paper at ICLR 2021
Decoded Text
Image 000000000802
with
with
and
with
a kitchen with
and
kitchen with
and
kitchen area with refrigerator and
kitchen with stove refrigerator and
kitchen area
with
stove
refrigerator
and
dishwasher
Figure 20: Generation order inferred by Ours-Common for an image from the COCO 2017 valida- tion set with the image identifier 000000000802.
Decoded Text
Image ID: 000000001268
of on
of
of
sitting on
of of people sitting people sitting on top of people sitting on of
group of people sitting on top pier
Figure 21: Generation order inferred by Ours-Common for an image from the COCO 2017 valida- tion set with the image identifier 000000001268.
26

---

Published as a conference paper at ICLR 2021
Decoded Text
Image ID: 000000001296
woman
holding
B
holding
while
holding
woman
holding cell phone while on
woman
holding
cell phone while talking
on
woman
holding
cell
phone
while
talking
on
crowd
Figure 22: Generation order inferred by Ours-Common for an image from the COCO 2017 valida- tion set with the image identifier 000000001296.
Decoded Text
Image ID: 000000001503
on
sitting of
sitting on top of sitting of wooden sitting on top wooden
computer
computer
sitting on of wooden dask
computer
monitor
sitting on top wooden desk
Figure 23: Generation order inferred by Ours-Common for an image from the COCO 2017 valida- tion set with the image identifier 000000001503.
27

---

Published as a conference paper at ICLR 2021
Decoded Text
Image ID: 000000001993
In
in to
sitting in
sitting in next to sitting in room next to bed sitting in room next to
bed sitting in room next to window
Figure 24: Generation order inferred by Ours-Common for an image from the COCO 2017 valida- tion set with the image identifier 000000001993.
Decoded Text
slope
skis
slope
Image ID: 000000000785
skis
covered
slope
skis
snow covered
slope
riding skis
snow covered
slope
riding skis down snow
covered slope
man riding skis down snow
covered slope
man riding
slope
riding
slope
riding
slope
Figure 25: Generation order inferred by Ours-Rare for an image from the COCO 2017 validation set with the image identifier 000000000785.
28

---

kitchen with stove and refrigerator Published as a conference paper at ICLR 2021
Decoded Text
Image 000000000802
stove
refrigerator
kitchen
refrigerator
kitchen stove and refrigerator
kitchen with and refrigerator refrigerator
kitchen with stove and
kitchen with stove and refrigerator
kitchen with stove and refrigerator
Figure 26: Generation order inferred by Burs-Rare for an image from the COCO 2017 validation set with the image identifier 000000000802.
Decoded Text
dock
dock looking
dock looking
waber
Image ID: 000000001268
dock looking
water
woman dock looking at water
sitting dock looking at water
woman sitting dock looking at the water woman sitting dock looking at the water woman sitting on dock looking at the water
woman sitting dock looking at the water
woman sitting on dock looking at the water
Figure 27: Generation order inferred by Ours-Rare for an image from the COCO 2017 validation set with the image identifier 000000001268.
29

---

Published as a conference paper at ICLR 2021
Decoded Text
Image ID: 000000001296
talking
talking
call
talking
call phone
talking
her
cell phone
talking
her cell phone
woman talking her cell phone
the woman talking her cell phone
the woman talking her cell phone
the woman talking
her call phone
Figure 28: Generation order inferred by Ours-Rare for an image from the COCO 2017 validation set with the image identifier 000000001296.
Decoded Text
mouse
keyboard
Image ID: 000000001503
desk
keyboard
mouse
laptop desk
keyboard
laptop desk keyboard and mouse
laptop desk with
keyboard and
laptop on desk with keyboard and mouse
laptop desk with keyboard and mouse
laptop on desk with keyboard and mouse
laptop dask with keyboard and mouse
laptop on desk with keyboard and mouse
Figure 29: Generation order inferred by Ours-Rare for an image from the COCO 2017 validation set with the image identifier 000000001503.
30

---

Published as a conference paper at ICLR 2021
Decoded Text
chairs
tables
Image ID: 000000001993
room
bed chairs
tables
room bed chairs tables
room with bed chairs and tables
room
with
bed
chairs
and
tables
tables
Figure 30: Generation order inferred by Ours-Rare for an image from the COCO 2017 validation set with the image identifier 000000001993.
F.2 DIANGO
We visualize the latent generation order inferred by Variational Order Inference for Django. Se- quences are generated using a beam search over both the tokens and their insertion positions, using beam size of 3. Text which the model is conditioned is provided the left for each example.
Conditioned Text
Decoded Text
AttributeError
AttributeError
AttributeError
name
AttributeError
"SSTR:O''
raise an AttributeError with an argument
string STR:O_,, formated with s self-name self, name )
AttributeError
'STRRO"'
%
name
AttributeError
'STTR:""'
AttributeError
'STR::
% self
name
AttributeError
SSTR:
self
raise
AttributeError
STR:O
% self
name
Figure 31: Generation order inferred by Ours-VOI for pseudocode sample from the Django natu- ral language to code test set with the sample id 154.
F.3 GIGAWORD
We visualize the latent generation order inferred by Variational Order Inference for Gigaword. Se- quences generated using beam search both the tokens and their insertion positions, using a beam size of 3. Text on which the model is conditioned is provided on the left for each example.
31

---

Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
enumerate
enumerate
1, arg enumerate
arg In enumerate arg in enumerate arg in enumerate arg enumerate args
for every and in enumerated iterable
:pass
:pass
ipass
arg
args
:pass
args
:pass
Figure 32: Generation order inferred by Ours-VOI for pseudocode sample from the Django natu- ral language code with the sample id 431.
Conditioned Text
Decoded Text
raise
raise AttributeError
raise
AttributeError
raise AttributeError
STRR:
raise AttributeError with argument string STRRO,,,, formated with self.name self. name
raise AttributeError
'STTR:
raise AttributeError
'SSTR:O''
self
raise AttributeError
'SSTR:
% self
raise AttributeError
STR:O
raise
AttributaError
STTR:
% self
name
Figure 33: Generation order inferred by Ours-I.2R for pseudocode sample from the Django natu- ral language code with the sample id 154.
32

---

for 1, arg In Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
for
for
for
for i, arg
for every and in enumerated iterable
for arg in enumerate
for i, arg in enumerate for arg enumerate args
args
arg
args
:pass
Figure 34: Generation order inferred by Ours-L2R for pseudocode sample from the Django natu- ral language code with the sample id 431.
Conditioned Text
Decoded Text
self
self
self
raise AttributeError with argument
('STR:O
self
string STRRO,,,, formated with self.name
self. name
('_STR:0_"
self
STSTO
STR:O_
raise
STR:O
name
raise
STR:O
name
self
class
raise AttributeError
STR:O
name
self
class
Figure 35: Generation order inferred by Ours-Common for pseudocode sample from the Django natural language to code test set with the sample id 154.
33

---

arg args Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
()
) :pass
for for every and in enumerated iterable for in
) :pass
:pass
for in args
:pass
for args
:pass
:pass
arg args
:pass
Figure 36: Generation order inferred by Ours-Common for pseudocode sample from the Django
natural language to code test set with the sample id 431.
Conditioned Text
Decoded Text
AttributeErrar
raise
AttributeError
raise
AttributeErrer
raise
AttributeError
name
raise AttributeError with argument
string STRRO,,,, formated with self.name
raise
AttributeError
SSTR:
self. name
raise
AttributeError
'STR:0_"
name
raise
AttributeError
('STR:
name
raise
AttributeError
|TTR::
raise
self
AttributoError
STR:O
name
Figure 37: Generation order inferred by Ours-Rare for pseudocode sample from the Django natural language to code test set with the sample id 154.
34

---

Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
enumerate
enumerate
arg enumerate
arg enumerate args
In arg enumerate args
for every and in enumerated iterable
for arg enumerate args
for arg enumerate args :pass
for arg enumerate args :pass
arg enumerate args :pass
, arg enumerate args :pass
Figure 38: Generation order inferred by Ours-Rare for pseudocode sample from the Django natural language to code test set with the sample id 431.
Conditioned Text
Decoded Text
antigua
antigua
antigua
prime minister antigua and bar@@
bud@@ baldwin left here monday for hong kong winding his four visit aaang
antigua
hong
kong
antigua
leaves
antigua
leaves
shanghal
hong
antigua
pm
shanghai
hong
kong
Figure 39: Generation order inferred by Ours-VOT for a text sample from the Gigaword text sum- marization set with the sample id 15.
35

---

Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
lankan
lankan
trawlers
the sri lankan has taken into
custody two indian fishing trawlers which poaching sni sapos; northwestern
arrested Indian fishermen board local newspaper reported wednesday.
lankan
Indian
trawlers
lankan
Indian
trawlers
lankan
two
Indian
trawlers
navy
indian
trawlers
Figure 40: Generation order inferred by Ours-VOI for a text sample from the Gigaword text sum-
marization set with the sample id 33.
Conditioned Text
Decoded Text
antigua
antigua
antigua
leaves
prime minister antigua and bar@@
bud@@ baldwin left here monday for hong kong winding his four visit aaang
antigua
leaves shanghai
antigua
leaves shanghal for
antigua
leaves shanghal for
hong
antigua
pm
shanghai
hong
kong
Figure 41: Generation order inferred by Ours-I.2R for text sample from the Gigaword text sum- marization set with the sample id 15.
36

---

Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
sri
sri
lankan
sri
lankan
navy
the sri lankan has taken into
custody two indian fishing trawlers which poaching sni sapos; northwestern
lankan
arrests
arrested Indian fishermen board local reported wednesday.
lankan
navy
nevy
lankan navy
arrests Indian
sri lankan navy
arrests
* Indian
fishermen
Figure 42: Generation order inferred by Ours-L2R for text sample from the Gigaword text sum- marization set with the sample id 33.
Conditioned Text
Decoded Text
antigua
antigua
pm
prime minister antigua and bar@@
antigua
ends
bud@@ baldwin left here monday for hong kong winding his four visit shanghal.
antigua
ends visit
antigua
pm
antigua
pm ends
visit to shanghal
Figure 43: Generation order inferred by Ours-Common for text sample from the Gigaword text summarization with the sample id 15.
37

---

Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
sri
sri
lankan
sri
lankan
navy
the sri lankan has taken into
custody two indian fishing trawlers which poaching sri sapos; northwestern
lankan
arrests
arrested Indian fishermen board local reported wednesday.
lankan
navy
nevy
lankan navy arrests
Indian
sri lankan navy arrests
* # Indian
fishermen
Figure 44: Generation order inferred by Ours-Common for text sample from the Gigaword text summarization with the sample id 33.
Conditioned Text
Decoded Text
antigua
antigua
ends
antigua
ends
visit
prime minister antigua and bar@@
bud@@ baldwin left here monday for hong kong winding his four visit Maang
antigua
ends
prime
visit
antigua
ends
minister visit
antigua
ends
prime
minister visit
china
antigua
prime
ministar
visit
china
Figure 45: Generation order inferred by Ours-Rare for text sample from the Gigaword text sum- marization set with the sample id 15.
38

---

Published as a conference paper at ICLR 2021
Conditioned Text
Decoded Text
fishermen
arrests
fishermen
lankan
arrests
fishermen
the lankan has taken Into
custody two indian fishing trawlers which poaching sri lanka &apos; northwestern coast arrested indian fishermen board local reported wednesday.
lankan
arrests
fishermen
lankan
navy arrests
fishermen
navy
indian
lankan navy arrests Indian
fishermen
sri lankan navy arrests
Indian
fishermen
Figure 46: Generation order inferred by Ours-Rare for text sample from the Gigaword text sum- marization test set with the sample id 33.
39


Reviews:
[{"review_id": "yMUyFJg8Wwy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "- Summary\nThis paper aims to decode both content and ordering of language models and proposes Variational Order Inference (VOI). The authors introduce a latent sequence variable z = (z_1, .. ,z_n) in which z_t is defined as the absolute position of the value generated. The authors model the posterior distribution of z as a Gumbel-Matching distribution which is relaxed as a Gumbel-Sinkorn distribution. To training the encoder and decoder networks, the ELBO is maximized using the policy gradient with baseline. The experimental results on Django and MS-COCO 2017 dataset show the proposed VOI outperforms the Transformer-InDIGO, as well as suggests that learned orders depend on content and best-first generation order.\n\n\n- Strong points\n\t1. The research on non-autoregressive orders to generate language is interesting, and the proposed method using Gumbel-Sinkorn distribution is mathematically well sound and novel.\n\t2. The proposed method outperforms the previous Transformer-InDIGO and other baselines (Random, L2R, Common, Rare). This paper analyzed the learned orders globally and locally, and conducted ablation studies.\n\t3. The paper is well-written and the authors also provide source codes for reproducibility.\n\n- Weak points\n\t1. The results are not compared with other SOTA auto-regressive algorithms.\n\n- Questions\n\t- How do you think about transferring knowledge from auto-regressively trained such as GPT-2 to such non-autoregressive models? Using the pertained model for the encoder and decoder would improve the results? Have you tried this strategy?", "extra_scores": {}, "extra_text": {}}, {"review_id": "WUbsJYBCKBh", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 paper proposes to model the generation order as latent variables for sequence generation tasks, by optimizing the ELBO involving a proposed process of Variational Order Inference (VOI). To alleviate the difficulty of optimizing discrete latent variables, the authors propose to cast it as a one-step Markov Decision problem and optimize it using the policy gradient. The authors also introduce the recent developed Gumbel-matching techniques to derive the close-form of the posterior distribution.\n\nPros:\n1. Overall, I think the research problem, i.e., explicit modeling the generation order,  in this work is interesting and worthy of discovering\n2. Casting the optimization of discrete latent variables as a one-step MDP is interesting\n3. Experiments show that the induced \"best-first\" order outperforms fixed orders, which verifies the motivation of the paper`\n4. Extensive and inspiring analysis \n\nCons:\n1. Explicit modeling the generation order is not a very novel idea that there have been many works on this topic. \n2. For checking the generalization of the method and better comparison w/ InDIGO (though InDIGO also conducted on MSCOCO, Django and the current comparison is sufficiently fair), I would like to increase my rating if seeing more experiments on large scale machine translation benchmarks as those in InDIGO. This would also further support your claim of a general-purpose approach w/ little domain knowledge (if any).\n\n-------\nMinors:\n- figure 1: could consider adding x, which would better match the descriptions of the paper (modeling p(y|x) instead of p(y))\n\nMissing references: \n\n[1] Chan, W., Kitaev, N., Guu, K., Stern, M. and Uszkoreit, J., 2019. KERMIT: Generative insertion-based modeling for sequences. arXiv preprint arXiv:1906.01604.\n\n[2] Gu, J., Wang, C. and Zhao, J., 2019. Levenshtein transformer. In Advances in Neural Information Processing Systems (pp. 11181-11191).\n\n[3] Bao, Y., Zhou, H., Feng, J., Wang, M., Huang, S., Chen, J. and Li, L., 2019. Non-autoregressive transformer by position learning. arXiv preprint arXiv:1911.10677.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SkUEed-plB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 authors  propose the first domain-independent unsupervised learner that discovers high-quality autoregressive orders through fully-parallelizable end-to-end training without domain specific tuning.  Inspired by the variational auto-encoder, they propose an\nencoder architecture to infer autoregressive orders. To solve  the non-differentiable ELBO ( discrete latent variables), they further construct a  practical algorithm with the help of policy gradients. The experiment results, such as the  global and local statistics for learned orders, are convincing.\n\nSome problems.\n1: The authors should clearly define the two similarity metrics between autoregressive orders in the appendix.\n2: Please check up the X_axis in the Fig 3.\n3: It would be better if the authors provide more results in the appendix,  such as the ablation studies about the 'K' and visualizations of sequences generated by the baselines.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OXn2q76q7nJ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 paper designed a new generative model by capturing the auto-regressive order as latent variables for sequence generation task. Based on combinatorical optimization techniques, the authors derived an policy gradient algorithm to optimize the variational lower bound. Empirical results on image caption and code generation showed that this method is superior than both fixed-order generation and previous adaptive-order method transformer-InDIGO. The authors further analyzed the learned orders on global and local level on COCO2017 dataset, demonstrating that the arrangement tend to follows the best-first strategy.\n\n\nConcerns:\n1. effect of sample size K: In section 5 training part, the paper claimed \"For our model trained with Variational Order Inference , we sample K = 4 latents for each\ntraining sample.\". The sample size K is used to approximate the gradient in variational order inference and it also affects the training efficiency i.e. $O(NKdl^2)$. It's not clear how the author choose the appropriate sample size K. Some analysis or experiemnt reults on the sensitivity of sample size K will help clarify this concern.\n\n\n2. experiments on nmt & running time: The papers didn't report any results on machine translation, an important task on conditional sequence generation. Since previous work(e.g. transformer-InDIGO) demonstrated superior results on several translation datasets, it's recommended that the authors also showed results on these datasets. Also one strength of the approach is its potential of fully parallelizing. A running time comparison will provide more convincing evidence to this claim.\n\n\n3. figure: Figure 1. in section 4 showed the structure of variational order inference. Considering the paper is mainly focused on conditional generation, an conditional generation version will be better by incorporating x sequence into the figure.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with a particular model structure selection problem: inferring the order of a given sequence of latent variables. This problem is closely related to the matching problem that involves discrete optimization. The authors propose to cast the problem into a one-step Markov Decision problem and optimize it using the policy gradient.  The proposal here is using Variational Order Inference (VOI) using and using a Gumbel-Sinkhorn distribution to construct a proposal over approximate permutations. The approach is mathematically sound and novel.

Empirical results on image caption and code generation show promising results: method outperforms the previous Transformer-InDIGO and other baselines (Random, L2R, Common, Rare). This paper further analyzes the learned orders globally and locally, and conducts ablations.

The reviewers were overall very enthusiastic. 

Decision: Accept (Poster)