Title: Neural Tree Transducers for Tree to Tree Learning

Abstract: We introduce a novel approach to tree-to-tree learning, the neural tree transducer (NTT), a top-down depth first context-sensitive tree decoder, which is paired with recursive neural encoders. Our method works purely on tree-to-tree manipulations rather than sequence-to-tree or tree-to-sequence and is able to encode and decode multiple depth trees. We compare our method to sequence-to-sequence models applied to serializations of the trees and show that our method outperforms previous methods for tree-to-tree transduction.

1. Introduction:

The sequence-to-sequence (Seq2Seq) model has led to a revolution in generative models for neural encoding and decoding (Sutskever et al., 2014) . Seq2Seq allowed for the encoding or compression of the initial input stream and a generative transformation sequence. From another point of view, Seq2Seq implicitly incorporate tree structure, whereas our method explicitly operates on trees. This is specifically important for tree transduction. We present a tree-to-tree (Tree2Tree) model for neural tree transduction which "translates" one tree into another. Intuitively, Seq2Seq can be thought of as equivalent to Seq2Tree, followed by Tree2Tree, and finally Tree2Seq. While these can be mathematically equivalent, for neural networks the structure can radically change what the model is able to learn.

Tree2Tree operates on trees as tree transducer. Tree transduction and tree rule extraction have been extensively studied outside of deep learning; for a review see Comon et al. (2007) . Unlike classical transduction methods, neural Tree2Tree models have no explicit rule extraction. Tree2Tree extends neural implementation of tree structured transduction from the seminal work of Frasconi et al. (1998) . We effectively learn the transduction rules instead of learning the weights on hand coded transduction rules. Tree transduction is an important problem for many tasks including neural syntactic machine translation (Cowan, 2008; Razmara, 2011; Wang et al., 2007) , mapping sentences to functional programs (Alvarez-Melis & Jaakkola, 2017) , and specialized program translation (Alur & D'Antoni, 2012) .

Within natural language processing, Seq2Seq has been used for many applications including machine translation (Sutskever et al., 2014; Bahdanau et al., 2014; Vinyals et al., 2015b) , caption generation (Vinyals et al., 2015b) , abstractive summarization (Rush et al., 2015) , dialog generation (Vinyals & Le, 2015) . One of the main advantages of Seq2Seq other existing generative models like hidden Markov models is its ability to "remember" longer term information using long-short term memory (LSTM), or more recently gated recurrent units (GRUs). These nonlinear recurrent models have an explicit memory retention which allows for the information in the encoded sentence to persist over the generated sequence (Lin & Tegmark, 2016) , furthermore, LSTM has been shown to capture context sensitive languages (Gers & Schmidhuber, 2001) and RNNs in general are Turing complete (Siegelmann & Sontag, 1995) . Furthermore, Seq2Seq has been shown to learn grammar (Vinyals et al., 2015a) as well as tree structure (Bowman et al., 2015) , and with explicit supervision syntax dependencies (Linzen et al., 2016) . Nonetheless, the original Seq2Seq model from Sutskever et al. (2014) reversed the input sequence in order to increase performance, showing that memory retention of distant information remained a problem. Attentional mechanisms (Bahdanau et al., 2014; Luong et al., 2015) were introduced to assist the decoder to reference distant entries in the input sequence. There has been further use of memory storage additions (Sukhbaatar et al., 2015) to retain more relevant history.

Both sequence-to-tree (Aharoni & Goldberg, 2017; Zhang et al., 2015; Dong & Lapata, 2016) and tree-to-sequence (Eriguchi et al., 2016a) have been explored. However, tree-to-tree encoding and decoding has been largely ignored. This, in spite of the fact that tree transduction and tree grammars have a long tradition (Engelfriet, 1975; Graehl & Knight, 2004; Cowan, 2008) . Syntax based (treeto-tree) machine translation models produced state-of-the-art results for many years (Cowan, 2008; Razmara, 2011) .

Unlike other work that focuses on extending sequence-to-sequence to trees, our work frames the tree-to-tree problem in the context of tree transduction. We draw from a large body of previous work in this field and thus, explicitly examine this problem from the perspective of production rules and tree edit distance (Tai, 1979) .

The major contribution of this paper is to introduce a neural tree transducer containing a new decoder mechanism specialized to tree-to-tree decoding and to show that this tree-to-tree model achieves better performance than standard Seq2Seq models on a clean set of transduction tasks.

2 Tree-to-Tree Model Our neural tree transducer uses an encoded representation of the input tree S together with the generative decoder model described below to predict the output tree T . The tree T is conditional on S such that the conditional probability, P(T | S ) = p∈Path(T ) P(x p | x 1 , . . . , x p-1 , enc(S )) where Path(T ) is the sequence of integers indexing the tree traversal, and x p is the random variable representing the label of the node at the p-th step of the traversal. Thus P(x p ) is the probability distribution over the labels at the p-th node. The encoder function, enc(S ), generates a k-dimensional encoding of a source tree, enc : S → R k . In general, the encoder does not need to be a tree encoder. However, concretely, we used a TreeLSTM for encoding the input tree S .

The decoder for our tree-to-tree transducer can be viewed as a context sensitive grammar. For this reason in sections 2.1.2 and 2.1.3 we introduce the formal notation of the probablistic context free grammar (PCFG) which is the theoretical grounding of our model and relates back to previous literature on tree transduction. However, the reader may skip these sections as the neural tree decoder is specified in section 2.1.4.

2.1. Neural Tree Decoder:

Unlike in sequence learning, which is simply left-to-right or vice versa, tree-based encoding and decoding requires us to select a tree traversal path. Thus, in order to properly define the probability structure over the tree we specify the one-to-one serialization of the binary tree to a sequence. We first start by defining a probabilistic model over trees, which is dependent on the tree traversal (or serialization). Next, we relate the tree decoding to production rules, first using the probabilistic context free grammar, and then we develop the our decoder model which is a probabilistic context sensitive model specification of our neural decoder. Figure 1 shows a tree encoding for (a + b) * c. An example explicit serialization of the tree is " node {*} child{ node {+} child{ node {a}} child{ node {b}} } child{ node {c}} ; ." While this is a general notation, we can further simplify to serializing the tree as { * { + { a } { b } } { c } } where a subtree is decorated by { }. This tree representation is from a depth first (or left most) derivation. This is also otherwise known as a prefix notation. (One can rewrite the infix notation (a + b) * c into prefix notation * + a b c.) However, in general if an interior node can have only a left or a right child we need minimally use } to decorate the sequence, so * + a } b } } c } } would be a minimal representation.

We require our serial representations to be one-to-one with trees. Thus, a probability distribution over such sequences uniquely corresponds to a probability distribution over trees. There are several ways of serializing trees, which lead to different probability distributions over the resulting strings. Thus, a simple representation for probability over trees requires a good choice for serialization and then a restriction over the probability distribution of these strings.

The derivation path Path(T ) is the traversal sequence of the tree. The function Path(•) takes a tree as its argument and outputs a sequence which corresponds to the derivation path. Focusing on the depth first derivation, we can see that the probability of the probability distribution over the p-th output of x p is conditional on the previous output, so we can write the probability of the next observation b as

P(x 4 = b | x 1 = * , x 2 = +, x 3 = a).

Thus, we can generalize to P(x p | x 1 , . . . , x p-1 ). And thus, we can say that the probability of the tree T , P(T ), is the serialization sequence

P(T ) = p∈Path(T ) P(x p | x 1 , . . . , x p-1 ) ≡ Path(T ) p=1 P p-1 (x p ).

Mapping from one tree to another constitutes a grammar and to understand how our neural tree transducer works we review for context sensitive and context free grammar transduction works. In order to serialize the tree, a set of production rules is required. Thus, in the following sections we describe a formal model of serialization using production rules, starting with the simplest model, context free production rules. We then generalize these context free grammars to make them context sensitive by taking into account the left sibling subtree when producing the right sibling.

2.1.1. Tree Production Rules:

It is convenient to represent trees as a set of production rules. In particular we can write giving a tree which corresponds to figure 1. Production rules are, in general, not adequate for doing serialization since they may be ambiguous; there may be more than one tree corresponding to a resulting sequence. However, production rules are a good language to describe simple probabilistic models for trees. So we need to relate a serialization to production rules. We will first do this for probabilistic context free grammars and then extend to context sensitive ones.

S → O | v | , O → OO | vO | Ov | vv. In

A first step in making this connection between production rules and trees is to define a function U : sequences → symbols. When given a partial sequence of a tree, U returns the symbol for the parent of the next symbol to be generated. Next we define a function V : (Σ ∪ O) → R k to access a probability vector given a symbol. This allows us to get at the idea of a production function by making claims like, P(x p = x|x 1 , . . . , x p-1 ) = P(x p = x|U(x 1 , . . . , x p-1 )) = g(x|u) = g 2 (x|V(u)) where u = U(x 1 , . . . , x p-1 ). U then gives us access to the same information as the rule that was used to land us at this point in the tree.

2.1.2. Probabilistic Context Free Grammar:

Although the above grammar is not, in general, context free, we can make is so by simplifying the assumptions about the production rules. This naturally will limit the conditional probability of a next observation conditional on the probability of the production rule. In a probabilistic context free grammar (PCFG), all production rules are independent. In other words P(x p = x | x 1 , . . . , x p-1 ) = P(x p = x | U(x 1 , . . . , x p-1 ) = y) = P(y → x). In order to make our grammar context-free, we split and restrict the production rule

O → OO | vO | Ov | v into two productions of O ---→ le f t O | v, O ---→ right O | v.

There are other representations for context-free grammars, which are equivalent, but for our purposes this is the most relevant. For example, + → ab becomes + ---→ 

P(x 4 = b | x 1 , x 2 , x 3 ) = P(x 4 = b | U(x 1 , x 2 , x 3 )) = P(x 4 = b | +) = P(+ ---→ right b).

The generalization of this model of the probability of a tree is

P(T ) = p∈Path(T ) P(x p | x 1 , . . . , x p-1 ) = p∈Path(T ) P(x p | U(x 1 , . . . , x p-1 ) = y) = p∈Path(T ) P(y → x p ).

2.1.3. Probabilistic Context Sensitive Model:

We do not, in fact, want to have the production rules be context free, so we will split the production rules O → OO | vO | Ov | vv, in order not to assume independence on the paths, aside from the parent. Given left-most derivations, the production rules can be modified into O ---→

le f t v | O and O conditioned on left ------------------→ right OO | vO | Ov | vv.

The left dependency is an assumption of our model; however, our decoder can be easily extensible to other context sensitive assumptions.

For representation purposes, we need to define functions for the derivation path, as well as the left subtree. We define the function f , which takes an index p ∈ Path(T ) and returns the index of the parent node. Then we can define the derivation path to x p as the sequence {x 1 , . . . , x f ( f (p)) , x f (p) } ≡ P p . Furthermore, we can define a function LS which extracts the left subtree sequence for an entry x p , so LS p = {x j s.t. f (p) < j < p}.

Having defined the required functions we, can now write down our context sensitive model as P(x p | x 1 , . . . , x p-1 ) = P(x p | {P p } ∪ {LS p }). Relative to a PCFG, where we have P(x p | x f (p) ), the context sensitive model relies on the derivation path as well as the left subtree.

Now we define two functions G : P p → R k and some H : LS p → R k . Under our model

P(x p = x|x 1 , . . . , x p-1 ) = P(x p | {P p } ∪ {LS p }) = P(x p = x | G(P p ), H(LS p )) = g(x|h P , h LS ).

Having fully specified the general context sensitive model, we now define the specification of the decoder for our neural tree transducer (NTT).

2.1.4. Neural Model Specification:

We use can use any recurrent neural network model for representing the information passed down from the root to the p-th node G, and for the encoding of the left subtree, H we can use any recursive neural network model.

The recurrent neural network, G, and the recursive neural network, H, could be specified as

h P = tanh(V P h f (p) + U P x f (p) + b P ) h LS = tanh(V LS l h C l (( f (p)+1)) + V LS r h C r (( f (p)+1)) + U LS x f (p)+1 + b LS ),

where C l and C r are functions which return the left and right direct children respectively, and x f (p)+1 is the left sibling of x p . As previously defined LS p extracts the left subtree sequence for an entry x p . If x p is a left child or the root then h LS = 0. The matrices V P , U P , V LS l , V LS r , U LS are estimated, and differ from the functions U and V.

In this paper, an LSTM and a binary TreeLSTM were used for G and H, respectively.

Finally, we can write g(x|h P , h LS ) = so f tmax(W P h P + W LS h LS + b). As a direct result,

P(x p = x i |x 1 , . . . , x p-1 ) = P(x p = x i | G(P p ), H(LS p )) = g(x i | h P , h LS ) |V| j=1 g(x j | h P , h LS )

, where x i and x j represent symbols in the vocabulary, and |V| is the number of symbols in the vocabulary. Figure 2 shows a concrete example of the decoder.

( a + b ) * c h 1 h 2 h 3 x 3 = a x 2 = + h 4 x 4 = b x 1 = * h 5 x 5 = c H(LS 5 ) encode

Figure 2 : This is an explicit example of the neural tree transducer model (NTT) binary tree for ( a + b ) * c. x p are the random variables, and h p are the hidden states. p corresponds to the derivation number, so x 2 is the second generated random variable, who's realization is the symbol +. The set LS 5 = {x 2 , x 3 , x 4 }, and P 5 = {x 1 } The hidden state h 5 is a function of the encoded left subtree h LS 5 = H(LS 5 )) h 2 and the parent hidden state, h P = h 1 . The reader should note that the predicted Pr(x 2 | x 1 ) = g(x 2 = + | h 2 ), while Pr(x 5 | x 1 , x 2 , x 3 , x 4 ) = g(x 5 = c | h 2 , h LS 5 ), so the difference in the prediction of x 2 and x 5 is due to the dependence on the left sibling subtree. Finally, h 1 = enc(S ) where S is the source tree to be transduced.

An important assumption of the model is that left derivations depend only on their parents, whereas right derivations are sensitive to the left sibling subtree. Allowing the left derivations to be dependant on their right subtree would create a cyclical dependency. Therefore, we make the implicit assumption that the parent hidden state captures sufficient information. In contrast, a breadth first approach can be bidirectionally dependent; however, the independence assumption is made with the children at subsequent depths. Although in this paper we focus on binary trees, we can generalize to N-ary trees by adding a symbol to our vocabulary which does not allow another right sibling.

3. Related Work:

There are three main related neural methods: Seq2Seq, Seq2Tree and Tree2Seq. To our knowledge there are no explicit Tree2Tree neural models to compare against. As discussed below, Tree2Tree is a transduction problem with is often done implicitly by these methods by using serialized versions of trees. By focusing purely on the tree transduction problem, we obtain both higher accuracy due to better localization and insight into the models. Seq2Seq is a baseline as Seq2Seq can be decomposed into Seq2Tree, Tree2Tree, and Tree2Seq. Thus Seq2Seq models should in theory be able to capture tree transduction.

3.1. Sequence-to-Sequence:

The first neural sequence-to-tree method treated grammar as a foreign language (Vinyals et al., 2015a) . However, similar to our baseline, their tree output is a serialization of a tree rather than a tree structure. This is an important distinction from a true Seq2Tree in that the hidden state vector in the decoder must treat the serialization as a stack. In our results, one can see that which serialization one uses matters. Seq2Seq has a disadvantage in that the trees generated may not be well formed. We find this is actually a problem in practice, not just in theory. Dyer et al. (2016) introduced the stack-based RNNG model, which uses a stack structure to create well formed trees. However, this model is still fundamentally a Seq2Seq approach with the stack function serving as a similar form of compression. Similarly, Grefenstette et al. (2015) show that the augmentation of Seq2Seq with memory was required for higher transduction accuracy.

3.2. Tree-to-Sequence:

Tree-to-Sequence learning can be thought of as a tree serialization task (Eriguchi et al., 2016b; a) . However, the tree representation is also useful for localizing information. Furthermore, as (Socher et al., 2011) showed, tree-to-value clearly captures sentiment. The idea that locality is more accurately captured in trees seems natural and could plausibly replace the (somewhat ad hoc) input reversal in Seq2Seq. Chen et al. (2017) showed improvements in machine translation by incorporating a tree encoder; however, their decoder remains sequence based.

3.3. Sequence-to-Tree:

Sequence-to-Tree transformation is a more well-studied problem, since it includes parsing and neural parsing has achieved state-of-the-art results (Aharoni & Goldberg, 2017) and hence garnered much attention. There are two main differences between these methods and our approach, 1) other decoders are breadth based, and 2) many sequence-to-tree problems, particularly dependency parsing, are fundamentally not tree-to-tree.

Recently, several neural tree decoders have been proposed. The models most similar to our approach are the SEQ2TREE (Dong & Lapata, 2016) , top-down tree LSTMs (Zhang et al., 2015) , and the double recurrent neural networks (Alvarez-Melis & Jaakkola, 2017) . All of their neural decoders, while somewhat similar to our approach, differ in important ways from our decoder. Most importantly, all of these methods use top down breadth first search, whereas our model is depth first.

Dong & Lapata (2016) used stack based production rules using a hierarchical decoder; however, SEQ2TREE does not explicitly do context sensitive production. Top-down tree LSTMs (Zhang et al., 2015) have four independent LSTMs for decoding, which require expensive explicit tree serialization and thus more parameters than we use. While doubly recurrent NNs (Alvarez-Melis & Jaakkola, 2017) do not suffer from the issue of multiple independent LSTMs, it does require explicit differentiation predictions of both terminal nodes and subsequently node labels.

Direct comparison of our tree-to-tree method on the problems addressed in these seq-to-tree papers is not possible. Dependency parsing, as done in (Zhang et al., 2015) is inherently sequence-to-tree, and does not map cleanly onto any tree-to-tree problem. Mapping sentences to functional programs, as done in (Alvarez-Melis & Jaakkola, 2017; Dong & Lapata, 2016 ) could be made into a tree-to-tree problem by parsing the sentences into trees, but their approach uses explicitly constructed n-ary trees where each level is restricted to a given label type.

Our depth first search allows us, at the cost of maintaining a stack, to avoid the problem of the separation of the point at which the label and the child node is predicted, which drove the need for double recurrence in the prior work.

4. Experiments:

We evaluated the different methods using tree edit distance (TED) (Tai, 1979; Bille, 2005) between the predicted tree and the actual tree. TED is the number of insertions, deletions, and modifications to make the two trees equivalent, while aligning the trees. In order to assess the tree-to-tree transduction rules which the models could learn, we chose four standard tree tasks 1) tree copy, 2) tree reordering, 3) node relabeling, and 4) node and subtree deletion. Our experiments are similar to those of Grefenstette et al. (2015) ; however, we explicitly isolate complex tree reordering, subtree deletion, and context sensitive relabeling. Tree Copy and Simple Node Relabeling While tree copying seems to be trivial, it shows that both Seq2Seq and Tree2Tree can perform copies. The NTT does not reverse order, but instead encodes the tree bottom up and left to right. One interesting observation is that Tree2Tree training required more training examples.

For tree copying, we simply validated that all of the models could copy a tree. For simple relabeling, we used context free relabeling rules to change from one vocabulary to another, so 1 → a. (See Figure 3 .)

Complex Node Relabeling For complex relabeling, or context sensitive relabeling, we took a tree with arbitrary labels and transformed it into a tree where the labels are reordered. We tried two subtasks, the first where the left sibling was required to be smaller than the right sibling. The second, more complex, task required the right sibling to be less than the left subtree. This causes the tree to be ordered.

Tree Reordering For tree reordering, we generated examples by taking mathematical expressions in reverse polish (or prefix notation) and transforming them infix notation. This process is a non-trivial tree reordering. However, there is no node relabeling, so it isolates the reordering capability of the NTT model. As expected, this is where the most benefit of the NTT model was found.

Subtree deletion For our final experiment, we focused on deletion rules. Here we created transduction rules to delete a subtree and replace it with a new symbol.

4.1. Settings:

Throughout our experiments we chose a maximum tree depth of 6 and vocabulary size of 256.

For our baseline Seq2Seq model, we used a two layer LSTM with 256 dimensions for both the hidden units and the memory cell with a bidirectional encoder and we also used the same formulation for the Seq2Seq with attention. Our Neural Tree Transducer (NTT) used a binary TreeLSTM for the encoder with a 256 dimensional hidden state space. The left subtree encoder was also a binary TreeLSTM, but with only one layer and the parent derivation was a LSTM with one hidden layer with 256 hidden units.

We used teacher forcing and curriculum learning. For all models we used the AdamOptimizer with an initial learning rate of 0.001, a dropout ratio of 0.2 and gradient clipping at 5.0. The models were trained until the development accuracy no longer improved.

4.2. Results:

Results are shown in Table 1 , and discussed below. For the task of simple relabeling, both Seq2Seq-Attn and NTT models perform nearly perfectly, which shows (not surprisingly) that the simple relabeling is not difficult. The Seq2Seq model without attention uniformly performs worse; the attention mechanism greatly aids relabeling. However, for complex relabeling the NTT performs much better than the Seq2Seq attention model. This is to be expected, as context sensitive relabeling relies heavily on the left subtree. Furthermore, the Seq2Seq model performs only sightly above the no edit case where the prediction is the original tree. In comparing the reordering, the NTT also greatly outperforms the baselines. Again, this is expected as the localization of a reordering is much easier in the NTT model. Finally, for deletion the NTT does not largely outperform Seq2Seq with attention model. The deletion is localized to a subsequence of the serialization. As a result, the attention model seems to be able to accurately "forget", while for the NTT model this is a equivalent to a relabeling task. 1 : Tree edit distance for the tree tasks of tree copying (Copy), subtree reordering (Reordering), node relabeling (Relabeling) and node and subtree deletion (Deletion). The models are sequence-tosequence (Sutskever et al., 2014) (Seq2Seq) , sequence-to-sequence with attention (Bahdanau et al., 2014 ) (Seq2Seq-Attn), and our neural tree transducer method (NTT).

Task:



5. Conclusion and Future Work:

We introduced a neural tree transduction (NTT) model which learns Tree2Tree transformations and presented a novel and intuitive context sensitive depth first decoder based on context sensitive grammars. Our NTT model was evaluated over several standard tree tasks and showed superior performance relative to Seq2Seq models. For tree transduction tasks such as syntactic machine translation, tree code based optimization, and text simplification, tree-to-tree is an essential component which is not easily captured by Seq2Seq models.

Unlike top down breadth first decoders, our NTT method naturally lends itself to streaming decoding (Alur & D'Antoni, 2012) . Streaming decoding would allow for arbitrary depth decoding and a parallel encoding/decoding scheme. Another immediate improvement to our model would be to incorporate tree attention as in the work of Munkhdalai & Yu (2016) , which have applied attention to tree alignment. Finally, we intend to apply our method to syntactic machine translation (translating from a dependency parse in one language to the parse in another language), text simplification, and program optimization.

:



Figures and Tables:

Figure 1: Example binary tree for ( a + b ) * c.

this notation, S is the root node of the tree, O is the set of non-terminals, and v are terminal symbols Σ and . For clarity, in our example we define the non-terminals O ∈ {+, * } and the terminals v ∈ {a, b, c, }. The observation is generated by the sequence of left most production rules S → * by S → O , * → +c by O → Ov , and +c → abc by O → vv

Going back to the example of the probability of the next observation b as,

Figure3: a) Simple relabeling example where 1 → a, 2 → b, and so on. b) subtree reordering where nodes labeled 4 and 5 swap. c) full reordering of subtree where left and right subtrees of the root node swap, and d) subtree deletion where the subtree of node 2 is replaced be the node labelled 6. The dotted arrows represent conditional dependence.

Peer review (iclr2018):
 The paper introduces a neural tree decoder architecture for binary trees that conditions the next node prediction on representations of its ascendants (encoded with an LSTM recurrent net) and left sibling subtree (encoded with a binary LSTM recursive net) for right sibling nodes. To perform tree to tree transduction the input tree is encoded as a vector with a Tree LSTM; correspondences between input and output subtrees are not modelled directly (using e.g. attention) as is done in traditional tree transducers. While the term context-sensitive should be used with caution, I do accept the claim here, although the notation used does not make the exposition clear. Experimental results show that the architecture performs better at synthetic tree transduction tasks (relabeling, reordering, deletion) than sequence-to-sequence baselines. While neural approches to tree-to-tree transduction is an understudied problem, the contributions of this paper are very narrow and it is not shown that the proposed approach will generalize to more expressive models or real-world applications of tree-to-tree transduction. Existing neural tree decoders, such as Dong and Lapata or Alvarex-Melis and Jaakkola, could be combined with tree LSTM encoders without any technical innovations and could possibly do as well as the proposed model for the transduction tasks tested - no experiments are performed with existing tree-based decoder architectures. Specific comments per section: 1. Unclear what is meant be "equivalent" in first paragraph. 2. The model does not assign an explicit probability to the tree structure - rather it seems to rely on the distinction between terminal and non-terimal symbols and the restriction to binary trees to know when closing brackets are implied - this is not made clear, and a general model should not have this restriction, as there are many cases where we want to generate non-binary trees. The production rule notation used is incorrect and confusing, mixing sets with non-terminals and terminal symbols: A better notation for the rules in 2.1.1 would be something like S -> P | v | .epsilon; P -> Q R | Q u | u Q | u w, where P, Q, R .in O and u, w .in v. 2.1.2. Splitting production rules as ->_left, ->_right is not standard notation. Rather introduce intermediate non-terminals in the grammar: O -> O_L O_R; O_L -> a | Q, O_R -> b | Q. 2.1.3 The context-sensitively here arise when conditioning on the entire left sibling subtree (not just the top non-terimal). The rules should have a format such as O -> O_L O_R; O_L -> a | Q; .alpha O_R -> .alpha a | .alpha Q, where .alpha is an entire subtree rooted at O_L. 2.1.4 Should be g(x|.) = exp( ), the softmax function includes the normalization which is done in the equation below. 3. Note that is is possible to restrict the decoder to produce tree structures while keeping a sequential neural architecture. For some tasks sequential decoders do actually produce mostly well-formed trees, given enough training data. RNNG encodes completed subtrees recursively, and the stack LSTM encodes the entire partially-produced tree, so it does produce and condition on trees not just sequences. The model in this paper is not more expressive than RNNG, it just encodes somewhat different structural biases, which might or might not be suited for real tasks. 4. In the examples given, the same set of symbols are used as both terminals and non-terminals. How is the tree structure then predicted by the decoder? Details about the training setup are missing: How is the training data generated, what is the size of the trees during training (compared to testing)? 4.2 The steep drop in performance between depth 5 and 6 indicates that model is very sensitive to its memorization capacity and might not be generalizing over the given training data. For real tree-to-tree applications involving these operations, there is good reason to believe that some kind of attention mechanism will be needed over the input tree during decoding. Reference should generally be to published proceedings rather than to arxiv where available - e.g. Aharoni and Goldberg, Dong and Lapata, Erguchi et al, Rush et al. For Graehl and Knight there is a published journal paper in Computational Linguistics.