Title: TREE2TREE LEARNING WITH MEMORY UNIT

Abstract: Traditional recurrent neural network (RNN) or convolutional neural network (CNN) based sequence-to-sequence model can not handle tree structural data well. To alleviate this problem, in this paper, we propose a tree-to-tree model with specially designed encoder unit and decoder unit, which recursively encodes tree inputs into highly folded tree embeddings and decodes the embeddings into tree outputs. Our model could represent the complex information of a tree while also restore a tree from embeddings. We evaluate our model in random tree recovery task and neural machine translation task. Experiments show that our model outperforms the baseline model.

1. INTRODUCTION:

In the past several years, Sequence-to-Sequence (Seq2Seq) model based on neural networks has made significant progress. It is widely used in various tasks, such as time series analysis (Lipton et al., 2015) , speech recognition (Graves et al., 2013) and machine translation (Bahdanau et al., 2014) . However, such model only captures sequential information while structural information is also of great importance in many tasks. On the one hand, data of many tasks is in hierarchical structure, such as interpersonal relationships in social network. Sequential data may contain latent structural information, on the other hand. For instance, natural language can be parsed into a tree with hierarchical structure, which represents the semantic dependency relationship between words (Chen & Manning, 2014) . Dyer et al. (2016) has shown that introducing structural information into sentence embedding could lead to an improvement to neural machine translation.

General Seq2Seq model can be regarded as a transduction from sequential inputs to sequential outputs, which limits the data structure of applications. But there are a lot of data hierarchical structure that can be represented in tree instead of sequence format. Compared with sequence based model, tree based model is more difficult to construct for the following two reasons: first, the number of child nodes is usually uncertain; second, the structural information of a tree is difficult to represent and restore. Thus, constructing a more informative embedding in tree based model remains a challenging problem. Lots of efforts have been made to tackle this problem. Socher et al. (2011b) designed a recursive tree encoder to encode both content and structure information. Tai et al. (2015) introduced a LSTM tree encoder to calculate an embedding for classification tasks. However, few works are devoted to recovering structural information from a embedding of tree. Socher et al. (2011a) proposed a tree-based model which applied hierarchical perceptron in both encoding and decoding process as a recursive auto-encoder. But its cell cannot handle the long-term dependency.

To address this issue, we propose a novel tree-to-tree model that recursively encodes tree inputs into highly folded tree embeddings and decodes the embeddings into tree outputs. Our model could represent the complex information of a tree while also restore a tree from embeddings. Furthermore, inspired by the architecture of long short-term memory (LSTM) (Hochreiter & Schmidhuber, 1997) , we proposed two memory units for encoder and decoder, respectively. Units of encoder contain an output gate, an input gate and forget gates, and units of decoder have an output gate as well as memory gates. Concretely, during encoding process, information from memory units of child nodes is combined in an organic way with the label of parent node, which is assigned to memory units of parent nodes. After getting the embedding, the decoder transduce it into a tree by splitting information into several parts and passing them to generate child nodes.

Besides, the similarity of two trees is hard to define. To alleviate this issue, we take both content and structure similarity into consideration and design a novel objective function. The content loss reflects whether the corresponding nodes of two trees share the same label, while the structure loss measures the difference of child number for corresponding nodes. The final objective function is the weighted sum of content loss and structure loss.

We design a random tree recovery experiment to evaluate the performance of the tree-to-tree model to represent and restore tree structure data. Experiment result in Section 4 shows, our model can recover nearly 90% of node labels and nearly all structural information, which significantly outperform the previous work. To evaluate our model in real-world problems, we perform experiments in neural machine translation task. Our model shows an improvement on both performance and robustness.

Our main contributions are three-fold:

• We propose a tree-to-tree model with specially designed encoder unit and decoder unit.

• We design a novel objective function with content loss and structure loss for tree.

• Experiments on both tree recovery evaluation and machine translation shows a great improvement.

The complete training and testing code are available at http://www.panda.com

2. RELATED WORK:

Tree-based models are widely used in recent AI research thanks to its ability to restore structure information which has been proved to help raise up performance in practice, like Wang et al. (2011) in image retrieval and Mou et al. (2015) in Heuristic Matching.

Recursive Neural Network(RNN) models are a popular family of tree-based deep learning models especially for NLP research. The main difference among these models lies in how the tree structure is composited, i.e., how to obtain the representation for a phrase or sentence with the representations of words it consists of. The Socher et al. (2011b) propose a basic form of RNN models, which represent phrases and words as vectors. It employ matrices and tensors as operators to perform compositions in a bottom-to-up way and finally reach a sentence embedding vector. Recently, there have been several studies addressing more semantic composition for RNNs. RNTN (Socher et al., 2013b) employs a tensor to model quadratic form interactions rather than basic matrix multiplication. MV-RNN (Socher et al., 2012) assigns each word with a vector and a matrix specifically. Also there have been studies on untied parameter tree composition including Socher et al. (2013a) and Hermann & Blunsom (2013) which utilize different composition functions according to the combined nodes' syntactic tags according to parsing results. Recently an adaptive framework were proposed (Dong et al., 2016) which selects composition function based on only the input vectors' value of their chid nodes.

As a combination of recursive neural network and LSTM, Tree-LSTM was first proposed in Zhu et al. (2015) . It utilizes a memory cell to reflect the history memories of multiple child cells or multiple descendant cells recursively. Following its step, it is applied in NLP tasks and outperform the state-of-art result including language inference in Chen et al. (2017; 2016) , sentiment classification and paraphrase analysis (Tai et al., 2015) . In the above models, the Tree-LSTM structure is applied in the sentence encoding process. For decoding and tree generation process (Zhang et al., 2015) applies top-down Tree-LSTM to generate dependency parse tree.

As the aspect of tree language model, Brychcin (2016) proposes a model that construct a tree structure for different sentences without utilizing syntax information like parsing trees. Bechet et al. (2001) and Richardson et al. (2016) derive a tree language model dependent on dependent parsing trees. As far as we know, we are the first to take consistency parsing information into consideration when constructing a tree-based language model.

3. MODEL:

In this paper, we introduce a novel tree-to-tree architecture, which first encodes the source tree as a context vector by a carefully designed encoder and to decode the vector to a target tree by a decoder. The overall workflow is shown in Table 1 . ) as the state of root node of decoder(l 1 ). For nodes in decoder, we first decide the number of child cells by split units. For example l 1 and l 3 have 3 and 2 child nodes, while other nodes have none. Then nodes split information for their children.

3.1. TREE MEMORY ENCODER(TME):

As intuitively showed in Figure 2 (a), our encoder is improved from Socher et al. (2011a) , which ensures that important information from nodes of lower level can be transmitted to the root node without much decay. In order to reconstruct trees from representation vectors generated by encoder, we designed a novel tree LSTM decoder. At each node of the decoder, information is properly devided into several parts and passed to its child nodes. The structure of Tree2Tree LSTM is shown in Figure 1 .

While Socher et al. (2011a) utilize LSTM encoder to encode trees into a representation vectors containing corresponding node and structure information, we employ a recursive decoder to transform the representation vectors back to trees.

We define tree-encoder as a collection of recursively organized encoder cells. Given the tree structure and the inputs of the leaf nodes, denoted as x 1 , x 2 , • • • , x n each represents an N-dimension vector. Each time a parent vector p is computed from its child nodes c 1 , c 2 , • • • with equation .

p = T M E([c 1 ; c 2 ; • • • ])

Here [c 1 ; c 2 ; • • • ] denotes the concatenation of the children. From bottom to up, all the nodes are computed recursively.

Concretely, our TME unit is shown as follows. While tree-encoder is natural extention of sequence LSTM cell, there is a large difference between tree-decoder and sequence LSTM decoder. Sequence LSTM encoder only only need to recover content information, but tree-decoder should also resolve structure information. That is to say, a tree-decoder cell need to decide what to output, as well as the number child cells. So the structure of tree-decoder is much much complicated that sequence-LSTM cell. The structure of decoder is shown in Figure 2(b) .

i t = σ( n k=1 W (i) (k) h t-1 (k) + u (i) I t + b (i) ) f (p) t = σ( n k=1 W (f )(p) (k) h t-1 (k) + u (f )(p) I t + b (f )(p) ) c t = n k=1 f (k) t c t-1 (k) + i t I t o t = σ(W (o) c t + b (o) ) h t = c t o t (1) c t (i), h t (i), (i = 1, 2, • • • , n) are

nu prob t = sof tmax(W (nu) c c t + W (nu) h h t + b (nu) ) nu t = arg max(nu prob t ) m t (k) = σ(W (m)(k) c c t + W (m)(k) n h t + b (m)(k) ) c t (k) = m t (p) c t n t (k) = σ(W (o) c t (k) + b (o) ) h t (k) = c t (k) o t (k) (2)

where nu t is a gate decide how much child nodes to generate.

m t (i)(i = 1, • • • , nu t ) are memery-keep cells determining how information is splited from c t , n t (i)(i = 1, • • • , nu t )

are output gates of child nodes, and h t (i), (i = 1, • • • , nu t ) are the corresponding outputs. At each step cells decide what to output, how many children to generate and the proportion of remaining information to pass to a specific child node. According to the spilt number nu t determined by our decoding unit at each time, we generate the child nodes c 1 , c 2 , • • • , c nut through the parent node with equation .

[c 1 ; c 2 ; • • • ; c nut ] = T M D(p)

(3)

3.3. OBJECT FUNCTION:

There are two criterion to assess the ability of autoencoder -the correctness of structure and precision of content recovery. So we need to minimize structure loss L 1 and content loss L 2 at the same time. We define L 1 , L 2 as the cross entropy of generating the right number of child nodes and output the right token. We use L = L 1 + λL 2 as our training loss. And we use Adam (Kingma & Ba, 2014) as the optimizer, which is more efficient and convenient to use than SGD.

For the target tree T r and the output tree T o ,

EQUATION

EQUATION

where, 

I(i, T ) = 1,if∃j ∈ T,

4. EXPERIMENT:

To demonstrate the effectiveness of our model, we test our model on two tasks, which includes the tree reconstruction task and machine translation task.

4.1. EXPERIMENT SETUP:



Dataset:

For for tree reconstruction task, we choose the mathematics genealogy dataset1 . Each tree represents a teacher-student relationship of mathematicians. A node indicate a person with its child nodes as the person's direct students. Each node is represented by an integer label. For nodes with more than 2 child nodes, we split the child nodes with each cluster sized 2, and construct corresponding trees.

Finally we got 10000 binary trees. We split all these data into 3 parts, with 9000, 500, 500 each for training/validation/test.

For the machine translation task, our data set consists of 350,000 sentences from United Nations Parallel Corpus (Ziemski et al., 2016) . We choose the first 50,000, 100,000, 340,000 sentence pairs as training set at each time, the validation set and test set both consist of 5,000 sentences. For Chinese corpus, Jieba2 is applied in tokenization. We use Stanford parser (Klein & Manning, 2003; Levy & Manning, 2003) to get parsing tree of each sentence.

Implementation Details:

All our experiments are run on GPUs in tensorflow framework. The autoencoder is trained on our model and the baseline separately with the training set. All parameters in our model are initialized with a uniform distribution within [-0.01, 0.01].

For machine translation tasks, our dictionary consists of all the words occurring in the training set, with each word vector initialized via Glove (Pennington et al., 2014) method in 300 dimensions and set to be joint trained along the model weights.

4.2. EXPERIMENT RESULTS:



Tree Reconstruction:

In this part, we design a self-to-self task to evaluate our model's recovery ability on arbitrary trees. Our model is compared with recursive Auto-Encoder (RAE) (Socher et al., 2011a) .

We evaluate the performance of recovery on label accuracy and structure accuracy. The label accuracy reflects how many nodes are correctly predicted, and the structure accuracy denotes the percentage of trees whose predicted structure is the same as the reference. Our Tree2Tree model reaches 85.9% in labeled accuracy and 100% in structure annuracy, far higher than the baseline which is 73.4% and 79.6%. The exciting result reflects that our tree2tree perfectly maintain almost all of the structured information when it is utilized as an autoencoder. 

Machine Translation:

In this part, we compare our model against the lstm baseline on English to Chinese machine translation task.

Table 1 shows Bleu (Papineni et al., 2002) scores in test set of our model and LSTM of English to Chinese translation task. Here the loss function in our model is defined as the cross entropy between prediction and target. We report results of both our model and LSTM with the same random seed and pick the one with best validation perplexity for final Bleu evaluation. Translation are generated via beam search with beam size 5. We can see that our tree2tree model outperforms the baseline for each data scale, with obvious difference in small dataset. 5w 10w 35w LSTM 0 15.9 28.9 Tree2Tree LSTM 13.4 18.7 29.3 We also test the robustness of our model against the baseline. For each sentence, we replace one word randomly in the original text with a word randomly chosen in the dictionary, and evaluate the difference of the output to test the robustness. We use the reduction proportion of Bleu1 and Bleu2 scores to evaluate the robustness of translation. The result is shown in Table 2 , from which we can see that Tree2Tree LSTM are more stable than LSTM. We will prove this property in theory in Section 5.

5. ANALYSIS:

In this section, we intruduce a Neural Tree Generation Model as a theoretical analysis which provides an explanation for our Tree2Tree in view of probability.

For tree T , we assume that the generation probability of node w i ∈ T satisfies the conditional independent property as follows.

∀node w j = w i , w j ⊥w i |par(w i )

Then, we can get the generation probability of the tree in the Figure 4 (c). P (T ) = P (r 3 |r 1 )P (r 4 |r 1 )P (r 1 |r 0 )P (r 2 |r 0 )P (r 0 ) 

EQUATION

Considering the tree structure as a Bayesian Network and every node as a random vector, we can get the set of Independence assertions of the tree.

EQUATION

Where N onDescendant wi denotes the nodes in the tree that are not descendants of w i .

According to equation 7, we can find that for two nodes with different parent nodes, the probability of two nodes is independent when parent nodes of two nodes are given. Formally, the tree structure can be regarded as a Bayesian Network (Koller & Friedman, 2009) , which leads to the independencies in the tree-structure using D-separation. For instance, Figure 4 (c) provides an intuitive example that (r 3 ⊥ r 2 |r 1 ).

In NLP tasks, the model above can be regarded as a neural tree-structure language model. For a sentence (w 1 , w 2 , • • • , w n ), we define the probability of P (w 1 , w 2 , • • • , w n ) as follows. where par(w i ) denotes the parent node of w i in the parsing tree of the sentence.

EQUATION

Take 'I love pandas' for instance, the parsing tree of the sentence is shown in Figure 4 , the probability of the sentence is computed as follows(by equation 9).

P ( I , love , pandas ) = P ( I |r 1 )P ( love |r 2 )P ( pandas |r 2 )P (r 1 |r 0 )P (r 2 |r 0 )P (r 0 ) (9)

The parsing tree of a sentence is constructed by the grammar of the sentence, which shows the syntactic structure of the sentence. This is consistent with the independency we get from Bayesian Network.

Besides, neural tree-structure language model have an another advantage. LSTM regards a sentence with a length of n as a sequence of n words. We define the path length of a word as the number of units the word goes through before reaching the end node of sentence embedding. For LSTM, the end node is the last word of sentence, and for tree-structured model, the end node is the root node of a tree. The AVE(average path length) of LSTM is O(n), but the AVE of tree LSTM is O(log(n)). So tree LSTM usually has smaller AVE.

6. CONCLUSION AND FUTURE WORK:

In this paper, we introduce a novel Tree2Tree LSTM which contains a tree-structure encoder and a tree-structure decoder. The model can apply to many fancy tasks, such as machine translation, tree-structure generation, etc. Based on our model, some experiments and theroy analysis are done to prove the strength of our model. In the future work, we will try to append tree-based attention to our model to improve the performance of our model.

:

https://genealogy.math.ndsu.nodak.edu/

https://pypi.python.org/pypi/jieba/

Figures and Tables:

process for one of the child units. Ct-1 and ht-1 are cell state and hidden state of parent cell. After passing through memory gate mt(k) for the kth child node, a specific part of information from Ct-1 is transmitted to the k-th child node.

Figure 2: Units of Our Model

Figure 4.2 shows a example of tree reconstruction result. we can observe that our model reconstructs the original tree much better than the baseline in both node level and structure level. Euler Lagrange Poisson Dirichlet Chasles Kronecker Lipschitz Lerch Mertens (a) Origin Genealogy

Figure 4: Parsing Tree of Example Sentence

The Structure of Encoder cell. Ct-1(k) is values of child node's memory units. It is the input. After passing through forget gate f and input gate it, information from Ct-1(k) and It are combined to generate new cell state and hidden state, ct and ht.

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td>ℎ 𝑡 (𝑘)</td></tr><tr><td>𝐶 𝑡-1 (1) 𝐶 𝑡-1 (𝑛) …</td><td>Σ</td><td/><td/><td/><td>𝐶 𝑡</td><td>𝜎 𝑛 𝑡 (𝑘)</td></tr><tr><td/><td>𝒇 𝒕 (𝒌)</td><td>𝒊 𝒕</td><td>𝜎</td><td/><td/><td colspan="2">𝐶 𝑡 (𝑘)</td></tr><tr><td>Σ ℎ 𝑡-1 (𝑘)</td><td>𝜎</td><td>𝜎</td><td>𝑰 𝒕</td><td>𝒐 𝒕</td><td>ℎ 𝑡</td><td/><td>𝜎 𝑚 𝑡 (𝑘)</td></tr><tr><td/><td>𝐼 𝑡</td><td/><td/><td/><td/><td>𝐶 𝑡-1</td><td>ℎ 𝑡-1</td></tr><tr><td colspan="3">(a) (k)</td><td/><td/><td/><td/></tr><tr><td/><td>t</td><td/><td/><td/><td/><td/></tr></table>

, childnum means the label and child number of node i in tree T r . Node i and node j have the same position if and only if the position of the parent and left brother of i, j are same.

Table content: <table><tr><td/><td>the position ofiis same asj,</td></tr><tr><td colspan="2">0,otherwise</td></tr><tr><td>H(i, j) =</td><td>1,if the position ofi, jare same, 0,otherwise</td></tr><tr><td>label Tr(i)</td><td/></tr></table>

Reslut of Translation

Table content: <table><tr><td/><td colspan="2">BLEU1 Reduction(%) BLEU2 Reduction(%)</td></tr><tr><td>LSTM</td><td>23.3</td><td>32.5</td></tr><tr><td>Tree2Tree LSTM</td><td>18.9</td><td>30.9</td></tr></table>

Robustness Analysis

Table content: <table/>

Examples of Robustness Original Text consideration of reports submitted by states parties under article 16 of the convention

Table content: <table><tr><td>financing of the united nations preventive deployment force</td></tr><tr><td>second periodic reports due in 1996</td></tr><tr><td>these figures show that womens participation in politics continues to be limited</td></tr><tr><td>the group of experts had before it the following documents</td></tr><tr><td>Reference</td></tr><tr><td>审议缔约国在盟约第16 条下提交的报告</td></tr><tr><td>联合国预防性部署部队经费的筹措</td></tr><tr><td>应于1996 年提交的第二次报告</td></tr><tr><td>这些数字表明妇女参与政治生活继续受到限制</td></tr><tr><td>专家组收到下列文件</td></tr><tr><td>LSTM</td></tr><tr><td>审议缔约国提交的报告提交的国家间工作组的报告</td></tr><tr><td>联合国预防性部署部队联预部队</td></tr><tr><td>1996 年11 月10 日</td></tr><tr><td>这些数字表明妇女继续在这些部门中占主导地位</td></tr><tr><td>专家组的以下文件是的的的工作</td></tr><tr><td>Tree2Tree LSTM</td></tr><tr><td>审议缔约国在公约第16 条下提交的报告</td></tr><tr><td>联合国预防性部署部队经费的筹措</td></tr><tr><td>应于1996 年第二次定期定期报告</td></tr><tr><td>这些数字表明认为参与妇女人数仍然有限</td></tr><tr><td>专家组有以下文件</td></tr><tr><td>Formally, we can define the generate probability of a tree by equation 6.</td></tr><tr><td>P (tree) =</td></tr><tr><td>winode:wi</td></tr></table>

Peer review (iclr2018):
 Summary: the paper proposes a tree2tree architecture for NLP tasks. Both the encoder and decoder of this architecture make use of memory cells: the encoder looks like a tree-lstm to encode a tree bottom-up, the decoder generates a tree top-down by predicting the number of children first. The objective function is a linear mixture of the cost of generating the tree structure and the target sentence. The proposed architecture outperforms recursive autoencoder on a self-to-self predicting trees, and outperforms an lstm seq2seq on En-Cn translation. Comment: - The idea of tree2tree has been around recently but it is difficult to make it work. I thus appreciate the authors’ effort. However, I wish the authors would have done it more properly. - The computation of the encoder and decoder is not novel. I was wondering how the encoder differs from tree-lstm. The decoder predicts the number of children first, but the authors don’t explain why they do that, nor compare this to existing tree generators. - I don’t understand the objective function (eq 4 and 5). Both Ls are not cross-entropy because label and childnum are not probabilities. I also don’t see why using Adam is more convenient than using SGD. - I think eq 9 is incorrect, because the decoder is not Markovian. To see this we can look at recurrent neural networks for language modeling: generating the current word is conditioning on the whole history (not only the previous word). - I expect the authors would explain more about how difficult the tasks are (eg. some statistics about the datasets), how to choose values for lambda, what the contribution of the new objective is. About writing: - the paper has so many problems with wording, e.g. articles, plurality. - many terms are incorrect, e.g. “dependent parsing tree” (should be “dependency tree”), “consistency parsing” (should be “constituency parsing”) - In 3.1, Socher et al. do not use lstm - I suggest the authors to do some more literature review on tree generation