Title: DRAGNN: A TRANSITION-BASED FRAMEWORK FOR DYNAMICALLY CONNECTED NEURAL NETWORKS

Abstract: In this work, we present a compact, modular framework for constructing new recurrent neural architectures. Our basic module is a new generic unit, the Transition Based Recurrent Unit (TBRU). In addition to hidden layer activations, TBRUs have discrete state dynamics that allow network connections to be built dynamically as a function of intermediate activations. By connecting multiple TBRUs, we can extend and combine commonly used architectures such as sequence-tosequence, attention mechanisms, and recursive tree-structured models. A TBRU can also serve as both an encoder for downstream tasks and as a decoder for its own task simultaneously, resulting in more accurate multi-task learning. We call our approach Dynamic Recurrent Acyclic Graphical Neural Networks, or DRAGNN. We show that DRAGNN is significantly more accurate and efficient than seq2seq with attention for syntactic dependency parsing and yields more accurate multi-task learning for extractive summarization tasks.

1. INTRODUCTION:

To apply deep learning models to structured prediction, machine learning practitioners must address two primary issues: (1) how to represent the input, and (2) how to represent the output. The seq2seq encoder/decoder framework (Kalchbrenner & Blunsom, 2013; Cho et al., 2014; Sutskever et al., 2014) proposes solving these generically. In its simplest form, the encoder network produces a fixed-length vector representation of an input, while the decoder network produces a linearization of the target output structure as a sequence of output symbols. Encoder/decoder is state of the art for several key tasks in natural language processing, such as machine translation (Wu et al., 2016) .

However, fixed-size encodings become less competitive when the input structure can be explicitly mapped to the output. In the simple case of predicting tags for individual tokens in a sentence, stateof-the-art taggers learn vector representations for each input token and predict output tags from those (Ling et al., 2015; Huang et al., 2015; Andor et al., 2016) . When the input or output is a syntactic parse tree, networks that explicitly operate over the compositional structure of the network typically outperform generic representations (Dyer et al., 2015; Li et al., 2015; Bowman et al., 2016) . Implictly learned mappings via attention mechanisms can significantly improve the performance of sequence-to-sequence (Bahdanau et al., 2015; Vinyals et al., 2015) , but require runtime that's quadratic in the input size.

In this work, we propose a modular neural architecture that generalizes the encoder/decoder concept to include explicit structure. Our framework can represent sequence-to-sequence learning as well as models with explicit structure like bi-directional tagging models and compositional, tree-structured models. Our core idea is to define any given architecture as a series of modular units, where connections between modules are unfolded dynamically as a function of the intermediate activations produced by the network. These dynamic connections represent the explicit input and output structure produced by the network for a given task.

We build on the idea of transition systems from the parsing literature (Nivre, 2006) , which linearize structured outputs as a sequence of (state, decision) pairs. Transition-based neural networks have recently been applied to a wide variety of NLP problems; Dyer et al. (2015) ; Lample et al. (2016) ; Figure 1 : High level schematic of a Transition-Based Recurrent Unit (TBRU), and common network architectures that can be implemented with multiple TBRUs. The discrete state is used to compute recurrences and fixed input embeddings, which are then fed through a network cell. The network predicts an action which is used to update the discrete state (dashed output) and provides activations that can be consumed through recurrences (solid output). Note that we present a slightly simplified version of Stack-LSTM (Dyer et al., 2015) for clarity. Kiperwasser & Goldberg (2016) ; Zhang et al. (2016) ; Andor et al. (2016) , among others. We generalize these approaches with a new basic module, the Transition-Based Recurrent Unit (TBRU), which produces a vector representation for every transition state in the output linearization (Figure 1 ). These representations also serve as the encoding of the explicit structure defined by the states. For example, a TBRU that attaches two sub-trees while building a syntactic parse tree will also produce the hidden layer activations to serve as an encoding for the newly constructed phrase. Multiple TBRUs can be connected and learned jointly to add explicit structure to multi-task learning setups and share representations between tasks with different input or output spaces (Figure 2 ). This inference procedure will construct an acyclic compute graph representing the network architecture, where recurrent connections are dynamically added as the network unfolds. We therefore call our approach Dynamic Recurrent Acyclic Graphical Neural Networks, or DRAGNN.

Encoder/Decoder (2 TBRU) Bi-LSTM Tagging (3 TBRU) Y1 Y2 Y3 Y4 Y5 Y1 Y2 Y3 Y4 Y5 Stack-LSTM (2 TBRU) Y1 Y2 Y3 Y4 Y5

DRAGNN has several distinct modeling advantages over traditional fixed neural architectures. Unlike generic seq2seq, DRAGNN supports variable sized input representations that may contain explicit structure. Unlike purely sequential RNNs, the dynamic connections in a DRAGNN can span arbitrary distances in the input space. Crucially, inference remains linear in the size of the input, in contrast to quadratic-time attention mechanisms. Dynamic connections thus establish a compromise between pure seq2seq and pure attention architectures by providing a finite set of long-range inputs that 'attend' to relevant portions of the input space. Unlike recursive neural networks (Socher et al., 2010; 2011) DRAGNN can both predict intermediate structures (such as parse trees) and utilize those structures in a single deep model, backpropagating downstream task errors through the intermediate structures. Compared to models such as Stack-LSTM (Dyer et al., 2015) and SPINN Bowman et al. (2016) , TBRUs are a more general formulation that allows incorporating dynamically structured multi-task learning (Zhang & Weiss, 2016) and more varied network architectures.

In sum, DRAGNN is not a particular neural architecture, but rather a formulation for describing neural architectures compactly. The key to this compact description is a new recurrent unit-the TBRU-which allows connections between nodes in an unrolled compute graph to be specified dynamically in a generic fashion. We utilize transition systems to provide succinct, discrete representations via linearizations of both the input and the output for structured prediction. We provide a straightforward way of re-using representations across NLP tasks that operate on different structures.

We demonstrate the effectiveness of DRAGNN on two NLP tasks that benefit from explicit structure: dependency parsing and extractive sentence summarization (Filippova & Altun, 2013) . First, we show how to use TBRUs to incrementally add structure to the input and output of a "vanilla" seq2seq dependency parsing model, dramatically boosting accuracy over seq2seq with no additional computational cost. Second, we demonstrate how the same TBRUs can be used to provide structured intermediate syntactic representations for extractive sentence summarization. This yields better accuracy than is possible with the generic multi-task seq2seq (Dong et al., 2015; Luong et al., 2016) approach. Finally, we show how multiple TBRUs for the same dependency parsing task can be stacked together to produce a single state-of-the-art dependency parsing model. 

2. TRANSITION SYSTEMS:

We use transition systems to map inputs x into a sequence of output symbols, d 1 . . . d n . For the purposes of implementing DRAGNN, transition systems make explicit two desirable properties. First, we stipulate that the output symbols represent modifications of a persistent, discrete state, which makes book-keeping to construct the dynamic recurrent connections easier to express. Second, transition systems make it easy to enforce arbitrary constraints on the output, e.g. the output should produce a valid tree.

Formally, we use the same setup as Andor et al. (2016) , and define a transition system T = {S, A, t} as:

• A set of states S(x).

• A special start state s † ∈ S(x).

• A set of allowed decisions A(s, x) for all s ∈ S.

• A transition function t(s, d, x) returning a new state s for any decision d ∈ A(s, x).

For brevity, we will drop the dependence of x in the functions given above. Throughout this work we will use transition systems in which all complete structures for the same input x have the same number of decisions n(x) (or n for brevity), although this is not necessary.

A complete structure is then a sequence of decision/state pairs (s

1 , d 1 ) . . . (s n , d n ) such that s 1 = s † , d i ∈ A(s i ) for i = 1 . . . n, and s i+1 = t(s i , d i ).

We will now define recurrent network architectures that operate over these linearizations of input and output structure.

3. TRANSITION BASED RECURRENT NETWORKS:

We now formally define how to combine transition systems with recurrent networks into what we call a transition based recurrent unit (TBRU). A TBRU consists of the following:

• A transition system T ,

• An input function m(s) that maps states to fixed-size vector representations, for example, an embedding lookup operation for features from the discrete state: To reproduce the tree, the Shift action should be taken.

m(s) : S → R K LSTM / MLP Cell LSTM / MLP Cell m(si) LSTM / MLP Cell hi s i • • • • • • s 1 s 2 m(s1) m(s2) h1 h2 LSTM / MLP Cell h3 s 3 m(s3) r(si) = {1, 3} d1 argmax d2A(s1) w > d h1 d2 argmax d2A(s2) w > d h2

• A recurrrence function r(s) that maps states to a set of previous time steps: r(s) : S → P{1, . . . , i -1}, where P is the power set. Note that in general |r(s)| is not necessarily fixed and can vary with s. We use r to specify state-dependent recurrent links in the unrolled computation graph.

• A RNN cell that computes a new hidden representation from the fixed and recurrent inputs:

h s ← RNN(m(s), {h i | i ∈ r(s)}).

Example 1. Sequential tagging RNN. Let the input x = {x 1 , . . . , x n } be a sequence of word embeddings, and the output be a sequence of tags d 1 , . . . , d n . Then we can model a simple LSTM tagger as follows:

• T sequentially tags each input token, where s i = {1, . . . , d i-1 }, and A is the set of possible tags. We call this the tagger transition system. • m(s i ) = x i , the word embedding for the next token to be tagged. • r(s i ) = {i -1} to connect the network to the previous state.

• RNN is a single instance of the LSTM cell. 2016) can be defined in our framework as follows:

• T is the arc-standard transition system (Figure 3 ), so the state contains all words and partially built trees on the stack as well as unseen words on the buffer. • m(s i ) is the concatenation of 52 feature embeddings extracted from tokens based on their positions in the stack and the buffer. • r(s i ) = {} is empty, as this is a feed-forward network.

• RNN is a feed-forward multi-layer perceptron (MLP).

Inference with TBRUs. Given the above, inference in the TBRU proceeds as follows:

1. Initialize s 1 = s † . 2. For i = 1, . . . , n:

(a) Update the hidden state:

h i ← RNN(m(s i ), {h j | j ∈ r(s i )}).

(b) Update the transition state:

d i ← argmax d∈A(si) w d h i , s i+1 ← t(s i , d i ).

A schematic overview of a single TBRU is presented in Figure 3 . By adjusting RNN, r, and T , TBRUs can represent a wide variety of neural architectures.

3.1. CONNECTING MULTIPLE TBRUS TO LEARN SHARED REPRESENTATIONS:

While TBRUs are a useful abstraction for describing recurrent models, the primary motivation for this framework is to allow new architectures by combining representations across tasks and compo-sitional structures. We do this by connecting multiple TBRUs with different transition systems via the recurrence function r(s). We formally augment the above definition as follows:

1. We execute a list of T TBRU components, one at a time, so that each TBRU advances a global step counter. Note that for simplicity, we assume an earlier TBRU finishes all of its steps before the next one starts execution. 2. Each transition state from the τ 'th component s τ has access to the terminal states from every prior transition system, and the recurrence function r(s τ ) for any given component can pull hidden activations from every prior one as well.

Example 3. "Input" transducer TBRUs via no-op decisions. We find it useful to define TBRUs even when the transition system decisions don't correspond to any output. These TBRUs, which we call no-op TBRUs, transduce the input according to some linearization. The simplest is the shiftonly transition system, in which the state is just an input pointer s i = {i}, and there is only one transition which advances it: t(s i , •) = {i + 1}. Executing this transition system will produce a hidden representation h i for every input token.

Example 4. Encoder/decoder networks with TBRUs. We can reproduce the encoder/decoder framework for sequence tagging by using two TBRUs: one using the shift-only transition system to encode the input, and the other using the tagger transition system. For input x = {x 1 , . . . , x n }, we connect them as follows:

• For shift-only TBRU: m(s i ) = x i , r(s i ) = {i -1}. • For tagger TBRU: m(s n+i ) = y dn+i-1 , r(s i ) = {n, n + i -1}.

We observe that the tagger TBRU starts at step n after the TBRU finishes, that y j is a fixed embedding vector for the output tag j, and that the tagger TBRU has access to both the final encoding vector h n as well as its own previous time step h n+i-1 .

Example 4. Bi-directional LSTM tagger. With three TBRUs, we can implement a simple bidirectional tagger. The first two run the shift-only transition system, but in opposite directions. The final TBRU runs the tagger transition system and concatenates the two representations:

• Left to right: T = shift-only, m(s i ) = x i , r(s i ) = {i -1}. • Right to left: T = shift-only, m(s n+i ) = x n-i , r(s n+i ) = {n + i -1}. • Tagger: T = tagger, m(s 2n+i ) = {}, r(s 2n+i ) = {i, 2n -i}.

We observe that the network cell in the tagger TBRU takes recurrences only from the bi-directional representations, and so is not recurrent in the traditional sense. See Figure 1 for an unrolled example.

Example 5. Multi-task bi-directional tagging. Here we observe that it's possible to add additional annotation tasks to the bi-directional TBRU stack from Example 4 simply by adding more instances of the tagger TBRUs that produce outputs from different tag sets, e.g. parts-of-speech vs. morphological tags. Most important, however, is that any additional TBRUs have access to all three earlier TBRUs. This means that we can support the "stack-propagation" (Zhang & Weiss, 2016) style of multi-task learning simply by changing r for the last TBRU:

• Traditional multi-task: r(s 3n+i ) = {i, 2n -i} • Stack-prop: r(s 3n+i ) = { i Left-to-right , 2n -i Right-to-left , 2n + i

Tagger TBRU

}:

Remark: the raison d'être of DRAGNN. This example highlights the primary advantage of our formulation: a TBRU can serve as both an encoder for downstream tasks and as a decoder for its own task simultaneously. This idea will prove particularly powerful when we consider syntactic parsing, which involves compositional structure over the input. For example, consider a no-op TBRU that traverses an input sequence x 1 , . . . , x n in the order determined by a binary parse tree: this transducer can implement a recursive tree-structured network in the style of Tai et al. (2015) , which computes representations for sub-phrases in the tree. In contrast, with DRAGNN, we can The first TBRU consumes each input word right-to-left; the second uses the arc-standard transition system. Note that each "Shift" action causes the TBRU1→TBRU2 link to advance. The dynamic recurrent inputs to the given state are highlighted; the stack representations are obtained from the last "Reduce" action to modify each sub-tree.

use the arc-standard parser directly to produce the parse tree as well as encode sub-phrases into representations.

Example 6. Compositional representations from arc-standard dependency parsing. We use the arc-standard transition system (Nivre, 2006) to model dependency trees. The system maintains two data structures as part of the state s: an input pointer and a stack (Figure 3 ). Trees are built bottom up via three possible attachment decisions. Assume that the stack consists of S = {A, B}, with the next token being C. We use S 0 and S 1 to refer to the top two tokens on the stack. Then the decisions are defined as:

• Shift: Push the next token on to the stack: S = {A, B, C}, and advance the input pointer.

• Left arc + label: Add an arc A ← label B, and remove A from the stack: S = {B}.

• Right arc + label: Add an arc A → label B, and remove B from the stack: S = {A}.

For a given parser state s i , we compute two types of recurrences:

• r INPUT (s i ) = {INPUT(s i )}

, where INPUT returns the index of the next input token.

• r STACK (s i ) = {SUBTREE(s i , S 0 ), SUBTREE(s, S 1 )}, where SUBTREE(S,I) is a function returning the index of the last decision that modified the i'th token: SUBTREE(s, i) = argmax j {d j s.t. d j shifts or adds a new child to token i}

We show an example of the links constructed by these recurrences in Figure 4 , and we investigate variants of this model in Section 4. This model is recursively compositional according to the decision taken by the network: when the TBRU at step s i decides to add an arc A → B for state, the activations h i will be used to represent that new subtree in future decisions.1 

Example 7. Extractive summarization pipeline with parse representations. To model extractive summarization, we follow Andor et al. (2016) and use a tagger transition system with two tags: "Keep" and "Drop." However, whereas Andor et al. (2016) use discrete features of the parse tree, we can utilize the SUBTREE recurrence function to pull compositional, phrase-based representations of tokens as constructed by the dependency parser. This model is outlined in Figure 2 . A full specification is given in the Appendix.

3.2. HOW TO TRAIN A DRAGNN:

Given a list of TBRUs, we propose the following learning procedure. We assume training data consists of examples x along with gold decision sequences for one of the TBRUs in the DRAGNN. Note that, at a minimum, we need such data for the final TBRU. Assuming given decisions d 1 . . . d N from prior components 1 . . . T -1, we define a log-likelihood objective to train the T 'th TBRU along its gold decision sequence d N +1 , . . . , d N +n , conditioned on prior decisions:

EQUATION

where θ are the combined parameters across all TBRUs. We observe that this objective is locally normalized (Andor et al., 2016) , since we optimize the probabilities of the individual decisions in the gold sequence.

The remaining question is where do the decisions d 1 . . . d N come from. There are two options here: they can either come as part of the gold annotation (e.g. if we have joint tagging and parsing data), or they will be predicted by unrolling the previous components (e.g. when training stacked extractive summarization model, the parse trees will be predicted by the previously trained parser TBRU).

When training a given TBRU, we unroll an entire input sequence and then use through structure (Goller & Kuchler, 1996) to optimize (1). To train the whole system on a set of C datasets, we use a similar strategy to (Dong et al., 2015; Luong et al., 2016) ; we sample a target task c, 1 ≤ c ≤ C, from a pre-defined ratio, and take a stochastic optimization step on the objective of that task's TBRU. In practice, task sampling is usually preceded by a deterministic number of pretraining steps, allowing, for example, to schedule a certain number of tagger training steps before running any parser training steps.

4. EXPERIMENTS:

In this section, we evaluate three aspects of our approach on two NLP tasks: English dependency parsing and extractive sentence summarization. For English dependency parsing, we primarily use the the Union Treebank setup from Andor et al. (2016) . By evaluating on both news and questions domains, we can separately evaluate how the model handles naturally longer and shorter form text.

On the Union Treebank setup there are 93 possible actions considering all arc-label combinations.

For extractive sentence summarization, we use the dataset of Filippova & Altun (2013) , where a large news collection is used to heuristically generate compression instances. The final corpus contains about 2.3M compression instances, but since we evaluated multiple tasks using this data, we subsampled the training set to be comparably sized to the parsing data (≈60K training sentences). The test set contains 160K examples. We implement our method in TensorFlow, using mini-batches of size 4 and following the averaged momentum training and hyperparameter tuning procedure of Weiss et al. (2015) .

4.1. USING EXPLICIT STRUCTURE IMPROVES ENCODER/DECODER:

We explore the impact of different types of recurrences on dependency parsing in Our final model uses 5 TBRU units. Inspired by Zhang & Weiss (2016) , a left-to-right POS tagging TBRU provides the first layer of representations. Next, we run two shift-only TBRUs, one in each direction, to provide representations to the parsers. Finally, we connect the left-to-right parser to the right-to-left parser using links defined via the SUBTREE function. The result (Table 3 ) is a state-ofthe-art dependency parser, yielding the highest published accuracy for a model trained solely on the Penn Treebank with no additional resources.

5. CONCLUSIONS:

We presented a compact, modular framework for describing recurrent neural architectures. We evaluated our dynamically structured model and found it to be significantly more efficient and accurate than attention mechanisms for dependency parsing and extractive sentence summarization in both single-and multi-task setups. While we focused primarily on syntactic parsing, the framework provides a general means of sharing representations between tasks. There remains low-hanging fruit still to be explored: in particular, our approach can be globally normalized with multiple hypotheses in the intermediate structure. We also plan to push the limits of multi-task learning by combining many different NLP tasks, such as translation, summarization, tagging problems, and reasoning tasks, into a single model.

:

This composition function is similar to that in the constituent parsing SPINN model(Bowman et al.,

2016), but with several key differences. Since we use TBRUs, we compose new representations for "Shift" actions as well as reductions, we take inputs from other recurrent models, and we can utilize subtree representations in downstream tasks.

Figures and Tables:

Figure3: Left: TBRU schematic. Right: Dependency parsing example. For the given gold dependency parse tree and a arc-standard transition state with two sub-trees on the stack is shown. From this state, two possible actions are also shown (Shift and Right arc). To reproduce the tree, the Shift action should be taken.

Parsey McParseface. The open-source syntactic parsing model of Andor et al. (

Figure 4: Detailed schematic for the compositional dependency parser used in our experiments.The first TBRU consumes each input word right-to-left; the second uses the arc-standard transition system. Note that each "Shift" action causes the TBRU1→TBRU2 link to advance. The dynamic recurrent inputs to the given state are highlighted; the stack representations are obtained from the last "Reduce" action to modify each sub-tree.

Dynamic links enable much more accurate, efficient linear-time parsing models on the Treebank Union dev set. We vary the recurrences r to explore utilizing explicit structure in the parsing TBRU. Utilizing the explicit INPUT(s i ) pointer is more effective and more efficient than a quadratic attention mechanism. Incorporating the explicit stack structure via recurrent links further improves performance.

Table content: <table><tr><td>Parsing TBRU recurrence, r(s i ) ⊆ {1, . . . , n + i} Input links Recurrent edges</td><td colspan="2">Parsing Accuracy (%) News Questions</td><td>Runtime</td></tr><tr><td colspan="2">{n} {n} Attention Attention {SUBTREE(s i , S 0 ), SUBTREE(s i , S 1 )} 89.0 {n + i -1} 27.3 {SUBTREE(s i , S 0 ), SUBTREE(s i , S 1 )} 36.0 {n + i -1} 76.1 INPUT(s i ) {n + i -1} 87.1 INPUT(s i ) {SUBTREE(s i , S 0 ), SUBTREE(s i , S 1 )} 90.9</td><td>70.1 75.6 84.8 91.9 89.7 92.1</td><td>O(n) O(n) O(n 2 ) O(n 2 ) O(n) O(n)</td></tr></table>

In this setup, we used relatively small models: single-layer LSTMs with 256 hidden units, taking

Table content: <table><tr><td/><td/><td>Model</td><td/><td/><td colspan="2">Dev UAS LAS</td><td>Test UAS LAS</td></tr><tr><td/><td>POS</td><td>Right-to-left</td><td>Parse</td><td/><td colspan="2">93.08 90.89 92.8</td><td>90.8</td></tr><tr><td>POS</td><td>Right-to-left</td><td>Left-to-right</td><td>Parse</td><td>Rev. Parse</td><td colspan="2">94.01 91.93 93.72 91.83</td></tr><tr><td/><td colspan="3">(Above, but with pretrained word2vec)</td><td/><td colspan="2">94.07 92.06 94.09 92.12</td></tr><tr><td colspan="5">Bi-LSTM, graph-based (Kiperwasser &amp; Goldberg, 2016) Stack LSTM (Dyer et al., 2015) 20 Stack LSTMs (Kuncoro et al., 2016) Globally normalized, transition-based Andor et al. (2016)</td><td>----</td><td>----</td><td>93.10 91.00 93.10 90.90 94.51 92.57 94.61 92.79</td></tr></table>

Deep stacked parsing compared to state-of-the-art on PTB. indicates that additional resources beyond the Penn Treebank are used. Our model is roughly comparable to an ensemble of multiple Stack-LSTM models, and the most accurate without any additional resources.

Table content: <table/>

Peer review (iclr2017):
The paper proposes a new neural architecture, called DRAGNN, for the transition-based framework. A DRAGNN uses TBRUs which are neural units to compute hidden activations for the current state of a transition-based system. The paper proves that DRAGNNs can cover a wide range of transition-based methods in the literature. In addition, one can easily implement multitask learning systems with DRAGNNs. The experimental results shows that using DRAGNNs the authors built (near) state-of-the-art systems for 2 tasks: parsing and summarization. The paper contains two major parts: DRAGNN and demonstrations of its usages. Regarding to the first part, the proposed DRAGNN is a neat tool for building any transition-based systems. However, it is difficult to say whether the DRAGNN is novel. Transition-based framework is already well defined and there*s a huge trend in NLP using neural networks to implement transition-based systems. In my opinion, the difference between the Stack-LSTM (Dyer et al., 2015) and DRAGNN is slight. Of course, the DRAGNN is a powerful architecture but the contribution here should be considered mainly in terms of software engineering. In the second part, the authors used DRAGNN to implement new transition-based systems for different (multi-)tasks. The implementations are neat, confirming that DRAGNN is a powerful architecture, especially for multitask learning. However, we should bear in mind that the solutions employed are already there in the literature, thus making difficult to judge the novelty of this part w.r.t. the theme of the conference.