Non-Monotonic Sequential Text Generation

Introduction

Most sequence-generation models, from n-grams (Bahl et al., 1983) to neural language models (Bengio et al., 2003) generate sequences in a purely left-to-right, monotonic order. This raises the question of whether alternative, non-monotonic orders are worth considering (Ford et al., 2018), especially given the success of “easy first” techniques in natural language tagging (Tsuruoka & Tsujii, 2005), parsing (Goldberg & Elhadad, 2010), and coreference (Stoyanov & Eisner, 2012), which allow a model to effectively learn their own ordering. In investigating this question, we are solely interested in considering non-monotonic generation that does not rely on external supervision, such as parse trees (Eriguchi et al., 2017; Aharoni & Goldberg, 2017).

In this paper, we propose a framework for training sequential text generation models which learn a generation order without having to specifying an order in advance (§ 2). An example generation from our model is shown in Figure 1. We frame the learning problem as an imitation learning problem, in which we aim to learn a generation policy that mimics the actions of an oracle generation policy (§ 3). Because the tree structure is unknown, the oracle policy cannot know the exact correct actions to take; to remedy this we propose a method called annealed coaching which can yield a policy with learned generation orders, by gradually moving from imitating a maximum entropy oracle to reinforcing the policy’s own preferences. Experimental results demonstrate that using the proposed framework, it is possible to learn policies which generate text without pre-specifying a generation order, achieving easy first-style behavior. The policies achieve performance metrics that are competitive with or superior to conventional left-to-right generation in language modeling, word reordering, and machine translation (§ 5).Code and trained models available at https://github.com/wellecks/nonmonotonic_text.

Non-Monotonic Sequence Generation

Unlike conventional approaches with a fixed generation order, often left-to-right (or right-to-left), our goal is to build a sequence generator that generates these tokens in an order automatically determined by the sequence generator, without any extra annotation nor supervision of what might be a good order. We propose a method which does so by generating a word at an arbitrary position, then recursively generating words to its left and words to its right, yielding a binary tree like that shown in Figure 1.

Learning for Non-Monotonic Generation

Learning in our non-monotonic sequence generation model (§ 2) amounts to inferring a policy $\pi$ from data. We first consider the unconditional generation problem (akin to language modeling) in which the data consists simply of sequences $Y$ to be generated. Subsequently (§ 4.1) we consider the conditional case in which we wish to learn a mapping from inputs $X$ to output sequences $Y$.

This learning problem is challenging because the sequences $Y$ alone only tell us what the final output sequences of words should be, but not what tree(s) should be used to get there. In left-to-right generation, the observed sequence $Y$ fully determines the sequence of actions to take. In our case, however, the tree structure is effectively a latent variable, which will be determined by the policy itself. This prevents us from using conventional supervised learning for training the parameterized policy. On the other hand, at training time, we do know which words should eventually appear, and their order; this substantially constrains the search space that needs to be explored, suggesting learning-to-search (Daumé et al., 2009) and imitation learning (Ross et al., 2011; Ross & Bagnell, 2014) as a learning strategy.One could consider applying reinforcement learning to this problem. This would ignore the fact that at training time we know which words will appear, reducing the size of the feasible search space from $O(|V|^{T})$ to $O(|X|^{T})$, a huge savings. Furthermore, even with a fixed generation order, RL has proven to be difficult without partially relying on supervised learning (Ranzato et al., 2015; Bahdanau et al., 2015b, 2016).

The key idea in our imitation learning framework is that at the first step, an oracle policy’s action is to produce any word $w$ that appears anywhere in $Y$. Once picked, in a quicksort-esque manner, all words to the left of $w$ in $Y$ are generated recursively on the left (following the same procedure), and all words to the right of $w$ in $Y$ are generated recursively on the right. (See Figure 2 for an example.) Because the oracle is non-deterministic (many “correct” actions are available at any given time), we inform this oracle policy with the current learned policy, encouraging it to favor actions that are preferred by the current policy, inspired by work in direct loss minimization (Hazan et al., 2010) and related techniques (Chiang, 2012; He et al., 2012).

In learning-to-search-style algorithms, we aim to learn a policy $\pi$ that mimics an oracle (or “reference”) policy $\pi^{*}$. To do so, we define a roll-in policy ${\pi^{\text{in}}}$ and roll-out policy ${\pi^{\text{out}}}$. We then repeatedly draw states $s$ according to the state distribution induced by ${\pi^{\text{in}}}$, and compute cost-to-go under ${\pi^{\text{out}}}$, for all possible actions $a$ at that state. The learned policy $\pi$ is then trained to choose actions to minimize this cost-to-go estimate.

Formally, denote the uniform distribution over $\{1,\dots,T\}$ as $U[T]$ and denote by $d_{\pi}^{t}$ the distribution of states induced by running $\pi$ for $t$-many steps. Denote by $\mathcal{C}(\pi;{\pi^{\text{out}}},s)$ a scalar cost measuring the loss incurred by $\pi$ against the cost-to-go estimates under ${\pi^{\text{out}}}$ (for instance, $\mathcal{C}$ may measure the squared error between the vector $\pi(\cdot|s)$ and the cost-to-go estimates). Then, the quantity being optimized is:

Here, ${\pi^{\text{in}}}$ and ${\pi^{\text{out}}}$ can use information not available at test-time (e.g., the ground-truth $Y$). Learning consists of finding a policy which only has access to states $s_{t}$ but performs as well or better than $\pi^{*}$. By varying the choice of ${\pi^{\text{in}}}$, ${\pi^{\text{out}}}$, and $\mathcal{C}$, one obtains different variants of learning-to-search algorithms, such as DAgger (Ross et al., 2011), AggreVaTe (Ross & Bagnell, 2014) or LOLS (Chang et al., 2015).

In the remainder of this section, we describe the cost function we use, a set of oracle policies and a set of roll-in policies, both of which are specifically designed for the proposed problem of non-monotonic sequential generation of a sequence. These sets of policies are empirically evaluated later in the experiments (§ 5).

2 Cost Measurement

There are many ways to measure the prediction cost $\mathcal{C}(\pi;{\pi^{\text{out}}},s)$; arguably the most common is squared error between cost-predictions by $\pi$ and observed costs obtained by ${\pi^{\text{out}}}$ at the state $s$. However, recent work has found that, especially when dealing with recurrent neural network policies (which we will use; see § 4), using a cost function more analogous to a cross-entropy loss can be preferred (Leblond et al., 2018; Cheng et al., 2018; Welleck et al., 2018). In particular, we use a KL-divergence type loss, measuring the difference between the action distribution produced by $\pi$ and the action distribution preferred by ${\pi^{\text{out}}}$.

Our approach estimates the loss in Eq. (1) by first sampling one training sequence, running the roll-in policy for $t$ steps, and computing the KL divergence (2) at that state using $\pi^{*}$ as $\pi^{\text{out}}$. Learning corresponds to minimizing this KL divergence iteratively with respect to the parameters of $\pi$.

3 Roll-In Policies

The roll-in policy determines the state distribution over which the learned policy $\pi$ is to be trained. In most formal analyses, the roll-in policy is a stochastic mixture of the learned policy $\pi$ and the oracle policy $\pi^{*}$, ensuring that $\pi$ is eventually trained on its own state distribution (Daumé et al., 2009; Ross et al., 2011; Ross & Bagnell, 2014; Chang et al., 2015). Despite this, experimentally, it has often been found that simply using the oracle’s state distribution is optimal (Ranzato et al., 2015; Leblond et al., 2018). This is likely because the noise incurred early on in learning by using $\pi$’s state distribution is not overcome by the benefit of matching state distributions, especially when the the policy class is sufficiently high capacity so as to be nearly realizable on the training data (Leblond et al., 2018). In preliminary experiments, we observed the same is true in our setting: simply rolling in according to the oracle policy (§ 3.4) yielded the best results experimentally. Therefore, despite the fact that this can lead to inconsistency in the learned model (Chang et al., 2015), all experiments are with oracle roll-ins.

4 Oracle Policies

In this section we formalize the oracle policies that we consider. To simplify the discussion (we assume that the roll-in distribution is the oracle), we only need to define an oracle policy that takes actions on states it, itself, visits. All the oracles we consider have access to the ground truth output $Y$, and the current state $s$. We interpret the state $s$ as a partial binary tree and a “current node” in that binary tree where the next prediction will go. It is easiest to consider the behavior of the oracle as a top-down, level-order traversal of the tree, where in each state it maintains a sequence of “possible tokens” at that state. An oracle policy $\pi^{*}(\cdot|s_{t})$ is defined with respect to $Y_{t}$, a consecutive subsequence of $Y$. At $s_{0}=\langle\rangle$, $\pi^{*}$ uses the full $Y_{0}=Y$. This is subdivided as the tree is descended. At each state $s_{t}$, $Y_{t}$ contains “valid actions”; labeling the current node with any token from $Y_{t}$ keeps the generation leading to $Y$. For instance, in Figure 2, after sampling b for the root, the valid actions $(a,b,c,d)$ are split into $(a)$ for the left child and $(c,d)$ for the right child.

Given the consecutive subsequence $Y_{t}=(w^{\prime}_{1},\ldots,w^{\prime}_{N^{\prime}})$, an oracle policy is defined as:

where the $p_{a}$s are arbitrary such that $\sum_{a\in Y}p_{a}=1$. An oracle policy places positive probability only on valid actions, and forces an $\langle\text{end}\rangle$ output if there are no more words to produce. This is guaranteed to always generate $Y$, regardless of how the random coin flips come up.

When an action $a$ is chosen, at $s_{t}$, this “splits” the sub-sequence $Y_{t}=(w^{\prime}_{1},\dots,w^{\prime}_{N^{\prime}})$ into left and right sub-sequences, $\overleftarrow{Y}_{t}=(w^{\prime}_{1},\ldots,w^{\prime}_{i-1})$ and $\overrightarrow{Y}_{t}=(w^{\prime}_{i+1},\ldots,w_{N})$, where $i$ is the index of $a$ in $Y_{t}$. (This split may not be unique due to duplicated words in $Y_{t}$, in which case we choose a valid split arbitrarily.) These are “passed” to the left and right child nodes, respectively.

There are many possible oracle policies, and each of them is characterized by how $p_{a}$ in Eq. (3) is defined. Specifically, we propose three variants.

Motivated by Welleck et al. (2018) who applied learning-to-search to the problem of multiset prediction, we design a uniform oracle $\pi^{*}_{\text{uniform}}$. This oracle treats all possible generation orders that lead to the target sequence $Y$ as equally likely, without preferring any specific set of orders. Formally, $\pi^{*}_{\text{uniform}}$ gives uniform probabilities $p_{a}=1/n$ for all words in $Y_{t}$ where $n$ is the number of unique words in $Y_{t}$. (Daumé (2009) used a similar oracle for unsupervised structured prediction, which has a similar non-deterministic oracle complication.)

Coaching Oracle.

An issue with the uniform oracle is that it does not prefer any specific set of generation orders, making it difficult for a parameterized policy to imitate. This gap has been noticed as a factor behind the difficulty in learning-to-search by He et al. (2012), who propose the idea of coaching. In coaching, the oracle takes into account the preference of a parameterized policy in order to facilitate its learning. Motivated by this, we design a coaching oracle as the product of the uniform oracle and current policy $\pi$:

This coaching oracle ensures that no invalid action is assigned any probability, while preferring actions that are preferred by the current parameterized policy, reinforcing the selection by the current policy if it is valid.

Annealed Coaching Oracle.

The multiplicative nature of the coaching oracle gives rise to an issue, especially in the early stage of learning, as it does not encourage learning to explore a diverse set of generation orders. We thus design a mixture of the uniform and coaching policies, which we refer to as an annealed coaching oracle:

We anneal $\beta$ from $1$ to over learning, on a linear schedule.

Deterministic Left-to-Right Oracle.

In addition to the proposed oracle policies above, we also experiment with a deterministic oracle that corresponds to generating the target sequence from left to right: $\pi^{*}_{\text{left-right}}$ always selects the first un-produced word as the correct action, with probability $1$. When both roll-in and oracle policies are set to the left-to-right oracle $\pi^{*}_{\text{left-right}}$, the proposed approach recovers to maximum likelihood learning of an autoregressive sequence model, which is de facto standard in neural sequence modeling. In other words, supervised learning of an autoregressive sequence model is a special case of the proposed approach.

Neural Net Policy Structure

The first policy we consider is implemented as a recurrent network with long short-term memory (LSTM) units (Hochreiter & Schmidhuber, 1997) by considering the partial binary tree as a flat sequence of nodes in a level-order traversal $(a_{1},\ldots,a_{t})$. The recurrent network encodes the sequence into a vector $h_{t}$ and computes a categorical distribution over the action set:

where $u_{a}$ and $b_{a}$ are weights and bias associated with $a$.

This LSTM structure relies entirely on the linearization of a partial binary tree, and minimally takes advantage of the actual tree structure or the surface order. It may be possible to exploit the tree structure more thoroughly using a recurrent architecture that is designed to encode a tree (Zhang et al., 2015; Alvarez-Melis & Jaakkola, 2017; Dyer et al., 2015; Bowman et al., 2016), which we leave for future investigation. We did experiment with additionally conditioning $\pi$’s action distribution on the parent of the current node in the tree, but preliminary experiments did not show gains.

Transformer Policy.

We additionally implement a policy using a Transformer (Vaswani et al., 2017). The level-order sequence $a_{1},...,a_{t}$ is again summarized by a vector $h_{t}$, here computed using a multi-head attention mechanism. As in the LSTM policy, the vector $h_{t}$ is used to compute a categorical distribution over the action set (6).

Auxiliary ⟨end⟩delimited-⟨⟩end\langle\text{end}\rangle Prediction.

We also consider separating the action prediction into token ($a_{i}\in\mathcal{V}$) prediction and $\langle\text{end}\rangle$ prediction. The policy under this view consists of a categorical distribution over tokens (6) as well as an $\langle\text{end}\rangle$ predictor which parameterizes a Bernoulli distribution, $\pi_{\text{end}}(\langle\text{end}\rangle|s_{t})\propto\sigma(u_{e}^{\top}h_{t}+b_{e}),$ where $\pi_{\text{end}}(\langle\text{end}\rangle=1|s_{t})$ means $a_{t}$ is $\langle\text{end}\rangle$, and $a_{t}$ is determined by $\pi$ according to (6) otherwise. At test time, we threshold the predicted $\langle\text{end}\rangle$ probability at a threshold $\tau$. In our experiments, we only use this approach with the Transformer policy (§ 5.4).

1 Conditional Sentence Generation

An advantage of using a neural network to implement the proposed policy is that it can be easily conditioned on an extra context. It allows us to build a conditional non-monotonic sequence generator that can for instance be used for machine translation, image caption generation, speech recognition and generally multimedia description generation (Cho et al., 2015). To do so, we assume that a conditioning input (e.g. an image or sentence) $X$ can be represented as a set of $d_{\text{enc}}$-dimensional context vectors, obtained with a learned encoder function $f^{\text{enc}}(X)$ whose parameters are learned jointly with the policy’s.

Experimental Results

In this section we experiment with our non-monotone sequence generation model across four tasks. The first two are unconditional generation tasks: language modeling (§ 5.1) and out-of-order sentence completion (§ 5.2). Our analysis in these tasks is primarily qualitative: we seek to understand what the non-monotone policy is learning and how it compares to a left-to-right model. The second two tasks are conditional generation tasks, which generate output sequences based on some given input sequence: word reordering (§ 5.3) and machine translation (§ 5.4).

We begin by considering generating samples from our model, trained as a language model. Our goal in this section is to qualitatively understand what our model has learned. It would be natural also to evaluate our model according to a score like perplexity. Unfortunately, unlike conventional autoregressive language models, it is intractable to compute the probability of a given sequence in the non-monotonic generation setting, as it requires us to marginalize out all possible binary trees that lead to the sequence.

We use a dataset derived from the Persona-Chat (Zhang et al., 2018) dialogue dataset, which consists of multi-turn dialogues between two agents. Our dataset here consists of all unique persona sentences and utterances in Persona-Chat. We derive the examples from the same train, validation, and test splits as Persona-Chat, resulting in 133,176 train, 16,181 validation, and 15,608 test examples. Sentences are tokenized by splitting on spaces and punctuation. The training set has a vocabulary size of 20,090 and an average of 12.0 tokens per example.

Model.

We use a uni-directional LSTM that has 2 layers of 1024 LSTM units. See Appendix A.2 for more details.

Basic Statistics.

We draw 10,000 samples from each trained policy (by varying the oracle) and analyze the results using the following metrics: percentage of novel sentences, percentage of unique, average number of tokens, average span sizeThe average span is the average number of children for non-leaf nodes excluding the special token $\langle\text{end}\rangle$, ranging from $1.0$ (chain, as induced by the left-right oracle) to $2.0$ (full binary tree). and Bleu (Table 1). We use Bleu to quantify the sample quality by computing the Bleu score of the samples using the validation set as reference, following Yu et al. (2016) and Zhu et al. (2018). In Appendix Table 6 we report additional scores. We see that the non-monotonically trained policies generate many more novel sentences, and build trees that are bushy (span $\sim 1.3$), but not complete binary trees. The policy trained with the annealed oracle is most similar to the validation data according to Bleu.

Content Analysis.

We investigate the content of the models in Table 2, which shows samples from policies trained with different oracles. Each of the displayed samples are not a part of the training set. We provide additional samples organized by length in Appendix Tables 8 and 9, and samples showing the underlying trees that generated them in Appendix Figures 5-7. We additionally examined word frequencies and part-of-speech tag frequencies, finding that the samples from each policy typically follow the validation set’s word and tag frequencies.

Generation Order.

We analyze the generation order of our various models by inspecting the part-of-speech (POS) tags each model tends to put at different tree depths (i.e. number of edges from node to root). Figure 3 shows POS counts by tree depth, normalized by the sum of counts at each depth (we only show the four most frequent POS categories). We also show POS counts for the validation set’s dependency trees, obtained with an off-the-shelf parser. Not surprisingly, policies trained with the uniform oracle tend to generate words with a variety of POS tags at each level. Policies trained with the annealed oracle on the other hand, learned to frequently generate punctuation at the root node, often either the sentence-final period or a comma, in an “easy first” style, since most sentences contain a period. Furthermore, we see that the policy trained with the annealed oracle tends to generate a pronoun before a noun or a verb (tree depth 1), which is a pattern that policies trained with the left-right oracle also learn. Nouns typically appear in the middle of the policy trained with the annealed oracle’s trees. Aside from verbs, the annealed policy’s trees, which place punctuation and pronouns near the root and nouns deeper, follow a similar structure as the dependency trees.

2 Sentence Completion

A major weakness of the conventional autoregressive model, especially with unbounded context, is that it cannot be easily used to fill in missing parts of a sentence except at the end. This is especially true when the number of tokens per missing segment is not given in advance. Achieving this requires significant changes to both model architecture, learning and inference (Berglund et al., 2015).

Our proposed approach, on the other hand, can naturally fill in missing segments in a sentence. Using models trained as language models from the previous section (§ 5.1), we can achieve this by initializing a binary tree with observed tokens in a way that they respect their relative positions. For instance, the first example shown in Table 3 can be seen as the template “ favorite food ! ” with variable-length missing segments. Generally, an initial tree with nodes $(w_{i},\ldots,w_{k})$ ensures that each $w_{j}$ appears in the completed sentence, and that $w_{i}$ appears at some position to the left of $w_{j}$ in the completed sentence when $w_{i}$ is a left-descendant of $w_{j}$ (analogously for right-descendants).

To quantify the completion quality, we first create a collection of initial trees by randomly sampling three words $(w_{i},w_{j},w_{k})$ from each sentence $Y=(w_{1},\ldots,w_{T})$ from the Persona-Chat validation set of § 5.1. We then sample one completion for each initial tree and measure the Bleu of each sample using the validation set as reference as in § 5.1. According to Bleu, the policy trained with the annealed oracle sampled completions that were more similar to the validation data (Bleu 44.7) than completions from the policies trained with the uniform (Bleu 38.9) or left-to-right (Bleu 14.3) oracles.

In Table 3, we present some sample completions using the policy trained with the uniform oracle. The completions illustrate a property of the proposed non-monotonic generation that is not available in left-to-right generation.

3 Word Reordering

We first evaluate the proposed models for conditional generation on the Word Reordering task, also known as Bag Translation (Brown et al., 1990) or Linearization (Schmaltz et al., 2016). In this task, a sentence $Y=(w_{1},...,w_{N})$ is given as an unordered collection $X=\{w_{1},...,w_{N}\}$, and the task is to reconstruct $Y$ from $X$. We assemble a dataset of $(X,Y)$ pairs using sentences $Y$ from the Persona-Chat sentence dataset of § 5.1. In our approach, we do not explicitly force the policies trained with our non-monotonic oracles to produce a permutation of the input and instead let them learn this automatically.

For encoding each unordered input $x=\{w_{1},...,w_{N}\}$, we use a simple bag-of-words encoder: $f^{\text{enc}}(\{w_{1},...,w_{N}\})=\frac{1}{T}\sum_{i=1}^{N}\text{emb}(w_{i})$. We implement $\text{emb}(w_{i})$ using an embedding layer followed by a linear transformation. The embedding layer is initialized with GloVe (Pennington et al., 2014) vectors and updated during training. As the policy (decoder) we use a flat LSTM with 2 layers of 1024 LSTM units. The decoder hidden state is initialized with a linear transformation of $f^{\text{enc}}(\{w_{1},...,w_{T}\})$.

Results.

Table 4 shows Bleu, F1 score, and exact match for policies trained with each oracle. The uniform and annealed policies outperform the left-right policy in F1 score (0.96 and 0.95 vs. 0.903). The policy trained using the annealed oracle also matches the left-right policy’s performance in terms of Bleu score (46.0 vs. 46.3) and exact match (0.212 vs. 0.208). The model trained with the uniform policy does not fare as well on Bleu or exact match. See Appendix Figure 6 for example predictions.

Easy-First Analysis.

Figure 4 shows the entropy of each model as a function of depth in the tree (normalized to fall in $$). The left-right-trained policy has high entropy on the first word and then drops dramatically as additional conditioning from prior context kicks in. The uniform-trained policy exhibits similar behavior. The annealed-trained policy, however, makes its highest confidence (“easiest”) predictions at the beginning (consistent with Figure 3) and defers harder decisions until later.

4 Machine Translation

We evaluate the proposed models on IWSLT’16 German $\rightarrow{}$ English (196k pairs) translation task. The data sets consist of TED talks. We use TED tst2013 as a validation dataset and tst-2014 as test.

Model & Training.

We use a Transformer policy, following the architecture of (Vaswani et al., 2017). We use auxiliary $\langle\text{end}\rangle$ prediction by introducing an additional output head, after observing a low brevity penalty in preliminary experiments. For the $\langle\text{end}\rangle$ prediction threshold $\tau$ we use $0.5$, and also report a variant (+$\langle\text{end}\rangle$ tuning) in which $\tau$ is tuned based on validation Bleu ($\tau=0.67)$. Finally, we report a variant which embeds each token by additionally encoding its path from the root (+tree-encoding) based on (Shiv & Quirk, 2019). See Appendix A.3 for additional details and results with a Bi-LSTM encoder-decoder architecture.

Results.

Results on validation and test data are in Table 7 according to four (very) different evaluation measures: Bleu, Meteor (Lavie & Agarwal, 2007), YiSi (Lo, 2018), and Ribes (Isozaki et al., 2010). First focusing on the non-monotonic models, we see that the annealed policy outperforms the uniform policy on all metrics, with tree-encoding yielding further gains. Adding $\langle\text{end}\rangle$ tuning to the tree-encoding model decreases the Ribes score but improves the other metrics, notably increasing the Bleu brevity penalty.

Compared to the best non-monotonic model, the left-to-right model has superior performance according to Bleu. As previously observed (Callison-Burch et al., 2006; Wilks, 2008), Bleu tends to strongly prefer models with left-to-right language models because it focuses on getting a large number of $4$-grams correct. The other three measures of translation quality are significantly less sensitive to exact word order and focus more on whether the “semantics” is preserved (for varying definitions of “semantics”). For those, we see that the best annealed model is more competitive, typically within one percentage point of left-to-right.

Related Work

Arguably one of the most successful approaches for generating discrete sequences, or sentences, is neural autoregressive modeling (Sutskever et al., 2011; Tomas, 2012). It has become de facto standard in machine translation (Cho et al., 2014a; Sutskever et al., 2014) and is widely studied for dialogue response generation (Vinyals & Le, 2015) as well as speech recognition (Chorowski et al., 2015). On the other hand, recent works have shown that it is possible to generate a sequence of discrete tokens in parallel by capturing strong dependencies among the tokens in a non-autoregressive way (Gu et al., 2017; Lee et al., 2018; Oord et al., 2017). Stern et al. (2018) and Wang et al. (2018) proposed to mix in these two paradigms and build a semi-autoregressive sequence generator, while largely sticking to left-to-right generation. Our proposal radically departs from these conventional approaches by building an algorithm that automatically captures a distinct generation order.

In (neural) language modeling, there is a long tradition of modeling the probability of a sequence as a tree or directed graph. For example, Emami & Jelinek (2005) proposed to factorize the probability over a sentence following its syntactic structure and train a neural network to model conditional distributions, which was followed more recently by Zhang et al. (2015) and by Dyer et al. (2016). This approach was applied to neural machine translation by Eriguchi et al. (2017) and Aharoni & Goldberg (2017). In all cases, these approaches require the availability of the ground-truth parse of a sentence or access to an external parser during training or inference time. This is unlike the proposed approach which does not require any such extra annotation or tool and learns to sequentially generate a sequence in an automatically determined non-monotonic order.

Conclusion, Limitations & Future Work

We described an approach to generating text in non-monotonic orders that fall out naturally as the result of learning. We explored several different oracle models for imitation, and found that an annealed “coaching” oracle performed best, and learned a “best-first” strategy for language modeling, where it appears to significantly outperform alternatives. On a word re-ordering task, we found that this approach essentially ties left-to-right decoding, a rather promising finding given the decades of work on left-to-right models. In a machine translation setting, we found that the model learns to translate in a way that tends to preserve meaning but not n-grams.

There are several potentially interesting avenues for future work. One is to solve the “learning to stop” problem directly, rather than through an after-the-fact tuning step. Another is to better understand how to construct an oracle that generalizes well after mistakes have been made, in order to train off of the gold path(s).

Moreover, the proposed formulation of sequence generation by tree generation is limited to binary trees. It is possible to extend the proposed approach to $n$-ary trees by designing a policy to output up to $n+1$ decisions at each node, leading to up to $n$ child nodes. This would bring a set of generation orders, that could be captured by the proposed approach, which includes all projective dependency parses. A new oracle must be designed for $n$-ary trees, and we leave this as a follow-up work.

Finally, although the proposed approach indeed learns to sequentially generate a sequence in a non-monotonic order, it cannot consider all possible orders. It is due to the constraint that there cannot be any crossing of two edges when the nodes are arranged on a line following the inorder traversal, which we refer to as projective generation. Extending the proposed approach to non-projective generation, which we leave as future work, would expand the number of generation orders considered during learning.

Acknowledgements

We thank support by eBay, TenCent and NVIDIA. This work was partly supported by Samsung Advanced Institute of Technology (Next Generation Deep Learning: from pattern recognition to AI), Samsung Electronics (Improving Deep Learning using Latent Structure), Sloan Foundation Research Fellowship, NSF Louis Stokes Alliances for Minority Participation Bridge to Doctorate (#1612736) and ACM SIGHPC/Intel Computational and Data Science Fellowship, and STCSM 17JC1404100/1.

References

Appendix

Appendix A Additional Experiment Details and Results

The decoder is a 2-layer LSTM with 1024 hidden units, dropout of 0.0, based on a preliminary grid search of $n_{\text{layers}}\in\{1,2\},n_{\text{hidden}}\in\{512,1024,2048\},{\text{dropout}}\in\{0.0,0.2,0.5\}$. Word embeddings are initialized with GloVe vectors and updated during training. All presented Word Reordering results use greedy decoding.

Training

Oracle

For $\pi_{\text{annealed}}^{*}$, $\beta$ is linearly annealed from 1.0 to 0.0 at a rate of 0.05 each epoch, after a burn-in period of 20 epochs in which $\beta$ is not decreased. We use greedy decoding when $\pi_{\text{coaching}}^{*}$ is selected at a roll-in step; we did not observe significant performance variations with stochastically sampling from $\pi_{\text{coaching}}^{*}$. These settings are based on a grid search of $\beta_{\text{rate}}\in\{0.01,0.05\},\beta_{\text{burn-in}}\in\{0,20\},\text{coaching-rollin}\in\{\text{greedy},\text{stochastic}\}$ using the model selected in the Model section above.

Example Predictions

Figure 8 shows example predictions from the validation set, including the generation order and underlying tree.

A.2 Unconditional Generation

We use the same settings as the Word Reordering experiments, except we always use stochastic sampling from $\pi_{\text{coaching}}^{*}$ during roll-in. For evaluation we select the model state at the end of training.

Samples in Tables 8-9 are organized as ‘short’ ($\leq$ 5th percentile), ‘average-length’ (45-55th percentile), and ‘multi-sentence’ ($\geq$ 3 punctuation tokens). Each image in Figures 5, 6, and 7 shows a sampled sentence, its underlying tree, and its generation order.

Additional BLEU Scores

Since absolute BLEU scores can vary by using a softmax temperature (Caccia et al., 2018) or top-k sampler, we report additional scores for $k\in\{10,100,1000\}$ and BLEU-$\{2,3,4\}$ in Table 6. Generally the policy trained with the annealed oracle achieves the highest metrics.

A.3 Machine Translation

We use the default Moses tokenizer script (Koehn et al., 2007) and segment each word into a subword using BPE (Sennrich et al., 2015) creating 40k tokens for both source and target. Similar to (Bahdanau et al., 2015a), during training we filter sentence pairs that exceed 50 words.

Transformer Policy

The Transformer policy uses 4 layers, 4 attention heads, hidden dimension 256, feed-forward dimension 1024, and is trained with batch-size 32 and a learning rate $1\text{e}^{-5}$. For this model and experiment, we define an epoch as 1,000 model updates. The learning rate is divided by a factor of 1.1 every 100 epochs. For $\pi_{\text{annealed}}^{*}$, $\beta$ is linearly annealed from 1.0 to 0.0 at a rate of 0.01 each epoch, after a burn-in period of 100 epochs. We compute metrics after each validation epoch, and following training we select the model with the highest validation Bleu.

Loss with Auxiliary ⟨end⟩delimited-⟨⟩end\langle\text{end}\rangle Predictor

A binary cross-entropy loss is used for the $\langle\text{end}\rangle$ predictor for all time-steps, so that the total loss is $\mathcal{L}_{\text{bce}}(\pi^{*},\pi_{\text{end}})+\mathcal{L}_{\text{KL}}(\pi^{*},\pi)$ where $\mathcal{L}_{\text{KL}}$ is the loss from Section 3.2. For time-steps in which $\langle\text{end}\rangle$ is sampled, $\mathcal{L}_{\text{KL}}$ is masked, since the policy’s token distribution is not used when $a_{t}$ is $\langle\text{end}\rangle$. $\mathcal{L}_{\text{KL}}$ is averaged over time by summing the loss from unmasked time-steps, then dividing by the number of unmasked time-steps.

Tree Position Encodings

We use an additional tree position encoding, based on (Shiv & Quirk, 2019), which may make it easier for the policy to identify and exploit structural relationships in the partially decoded tree. Each node is encoded using its path from the root, namely a sequence of left or right steps from parent to child. Each step is represented as a 2-dimensional binary vector ($$for the root,$$ for left and $$for right), so that the path is a vector$e(a_{i})\in\{0,1\}^{2*\text{max-depth}}$after zero-padding. Finally,$e(a_{i})$is multiplied element-wise by a geometric series of a learned parameter$p$, that is,$e(a_{i})\cdot\left[1,p,p,p^{2},p^{3},...\right]$. We only use this approach with the Transformer policy.

Additional LSTM Policy

Results are shown in Table 7. We use a bi-directional LSTM encoder-decoder architecture that has a single layer of size 512, with global concat attention (Luong et al., 2015). The learning rate is initialized to 0.001 and multiplied by a factor of 0.5 on a fixed interval.