Dynamic Compositional Neural Networks over Tree Structure

1 Introduction

Learning the distributed representation for long spans of text from its constituents has been a key step for various natural language processing (NLP) tasks, such as text classification [Zhao et al., 2015; Liu et al., 2015], semantic matching [Liu et al., 2016a; 2016b], and machine translation [Cho et al., 2014]. Existing deep learning approaches take a compositional function with different forms to compose word vectors recursively until obtaining a sentential representation. Typically, these compositional functions involve recurrent neural networks [Hochreiter and Schmidhuber, 1997], convolutional neural networks [Kalchbrenner et al., 2014], and treestructured neural networks [Tai et al., 2015; Zhu et al., 2015].

Among these methods, tree-structured neural networks (Tree-NNs) show theirs superior performance in many NLP tasks [Socher et al., 2012]. Following the syntactic tree structure, Tree-NNs assign a fixed-length vector to each word at the leaves of the tree, and combine word and phrase pairs recursively to create intermediate node vectors, eventually obtaining one final vector to represent the whole sentence.

However, these models have a major limitation in their inability to fully capture the richness of compositionality

∗Corresponding author.

[Socher et al., 2013a]. The same parameters are used for all kinds of semantic compositions, even though the compositions have different characteristics in nature. For example, the composition of the adjective and the noun differs significantly from the composition of the verb and the noun. Moreover, many semantic phenomena, such as semantic idiomaticity or transparency, call for more powerful compositional mechanisms [Pylkk¨anen and McElree, 2006]. Therefore, Tree-NNs suffer from the underfitting problem.

To alleviate this problem, some researchers propose to use multiple compositional functions, which are arranged beforehand according to some partition criterion [Socher et al., 2012; 2013a; Dong et al., 2014]. Intuitively, using different parameters for different types of compositions has the potential to greatly reduce underfitting. Socher et al. [2013a] defined different compositional functions in terms of syntactic categories, and a suitable compositional function is selected based on the syntactic categories. Dong et al. [2014] introduced multiple compositional functions and during compositional phase, a proper one is selected based on the input information. Although these models accomplished their mission to a certain extent, they still suffer from the following three challenges. First, the predefined compositional functions cannot cover all the compositional rules; Second, they require more learnable parameters, suffering from the problem of overfitting; Third, it is difficult to determine a universal criterion for semantic composition based solely on syntactic categories.

In this paper, we propose dynamic compositional neural networks over tree structure, in which a meta network is used to generate the context-specific parameters of a dynamic compositional network. Specifically, we construct our models based on two kinds of tree-structured neural networks: recursive neural network (Tree-RecNN) [Socher et al., 2012] and tree-structure long short-term memory neural network (Tree-LSTM) [Tai et al., 2015]. Our work is inspired by recent work on dynamic parameter prediction [De Brabandere et al., 2016; Bertinetto et al., 2016; Ha et al., 2016]. The meta network is used to extract the shared meta-knowledge across different compositional rules and to dynamically generate the context-specific compositional function. Thus, the compositional function of our models varies with positions, contexts and samples. The dynamic compositional network then applies those context-specific parameters to the current input information. Both meta and dynamic networks are differentiable such that the overall networks can be trained in an endto-end fashion. Additional, to reduce the complexity of the whole networks, we define the dynamic weight matrix in a manner simulating low-rank matrix decomposition.

We evaluate our models on two typical tasks: text classification and text semantic matching. The results show that our models are more expressive due to their learning to learn nature, yet without increasing the number of model's parameters. Moreover, we find certain composition operations can be learned implicitly by meta TreeNN, such as the composition of noun phrases and verb phrases.

The contributions of the paper can be summed up as follows.

1. We provide a new perspective on how to compose the individual word of a sentence. Instead of directly using a learnable parameterized compositional function, we introduce a meta neural network, which can generate a compositional network to dynamically compose constituents over tree structure.
2. Experimental results show that the proposed architecture is more expressive due to its learning to learn nature, yet without increasing the number of model's parameters.
3. We present an elaborate qualitative analysis, giving an intuitive understanding on how our model works from semantic and syntactic perspectives.

2 Tree-Structured Neural Network

In this section, we briefly describe the tree-structured neural networks.

The idea of tree-structured neural networks for natural language processing (NLP) is to train a deep learning model with a grammatical tree structure [Pollack, 1990] that can be applied to phrases and sentences. At every node in the tree, the contexts of the left and right children are combined by a compositional function. The parameters of the compositional function are shared across all nodes in the tree. The layer computed at the top node gives a representation for the whole sentence.

2.1 Vanilla Recursive Neural Network

The simplest member of tree-structured NN is the vanilla recursive neural network [Socher et al., 2013a], in which the representation of parent is calculated by weighted linear combination of the child vectors.

Formally, given a binary constituency tree T induced by a sentence, each non-leaf node corresponds to a phrase. We refer to hj ∈ Rd as the hidden state of each node j, and let hlj , hr j denote the left and right child representations respectively.

where W ∈ Rd×2d is a learnable compositional matrix, b is the bias vector.

2.2 Tree LSTM

Tree LSTM [Tai et al., 2015] is a generalization of LSTMs to tree-structured network topologies. In this model, the compositional function is an LSTM unit, and the hidden state hj of each node can be computed as follows: we refer to hj and cj as the hidden state and memory cell of each node j. The transition equations of node j are as follows:

where xj ∈ Rd denotes the input vector and is non-zero if and only if it is a leaf node. The superscript l and r represent the left child and right child respectively. σ represents the logistic sigmoid function and ⊙ denotes element-wise multiplication. W ∈ R5d×3d and b ∈ R5d are learnable parameters.

3 Dynamic Compositional Neural Network

In the above two tree-structured NNs, the compositional function is shared across all nodes in the tree, which results in underfitting since the semantic compositions have great diversities. To address this problem, we propose two dynamic compositional neural networks over tree structure, which dynamically generate different parameters for different types of compositions. Figure 2 shows an illustration of the dynamic compositional neural network, consisting of two components: (1) meta network and (2) basic network with dynamic parameters.

Specifically, we propose two meta networks to generate the context-specific compositional functions for RecNN and TreeLSTM respectively.

3.1 Meta Network for RecNN

For RecNN, we replace the static parameters W and b in Eq.(1) with the dynamic parameters W(zj ) and b(zj ), which are generated by a meta network. The meta network is a smaller RecNN, and the hidden state ˆhj ∈ Rm of node j in meta network is defined as

where Hj = hlj ⊕ hrj ⊕ ˆhlj ⊕ ˆhrj ∈ R2m+2d , Wm ∈ Rm×(2d+2m) and bm ∈ Rm are parameters of meta RecNN; Wz ∈ Rz×m is a scale matrix.

To reduce the number of the parameters, we define the dynamic parameters with a low-rank factorized representation of the weights, analogous to the Singular Value Decomposition. The dynamic parameters W(zj) and b(zj) of the basic RecNN are computed by:

where P ∈ Rd×z , Q ∈ Rz×d , and D(zt) ∈ Rz×z is the diagonal matrix of z.

Thus, our dynamic RecNN needs (6dz +mz) parameters, while the vanilla RecNN has (2d2 + d) parameters. With a small z and m, our dynamic RecNN needs less parameters than the vanilla RecNN. For example, if we set d = 100 and z = m = 20, our model needs 12, 400 parameters while the vanilla model needs 20, 100 parameters.

3.2 Meta Network for TreeLSTM

Likewise, we also use a smaller meta network to generate the static parameters W and b in Eq.(9) with the dynamic parameters W(zj) and b(zj). The meta network is a smaller TreeLSTM, and the hidden state ˆhj ∈ Rm of node j in meta network is defined as

where Hj = hlj ⊕ hrj ⊕ ˆhlj ⊕ ˆhrj ∈ R2m+2d ; Wm ∈ R5m×(3d+2m) and bm ∈ Rm are parameters of meta TreeLSTM; Wz ∈ Rz×m is a scale matrix.

The dynamic parameters W(zj ) and b(zj ) of basic TreeLSTM are computed by:

where for ∗ ∈ {c, o, i, f l , f r },

where P ∈ R5d×z , Q ∈ Rz×3d , B ∈ R5d×z , and D(zt) ∈ Rz×z is the diagonal matrix of z.

With a small z and m, our dynamic TreeLSTM needs a similar amount of parameters compared to the standard TreeLSTM.

4 Application of Dynamic Compositional Neural Networks

In this section, we describe two specific models to show the applications of dynamic compositional neural networks for two typical tasks in NLP.

4.1 Text Classification

The purpose of text classification is that, given a sentence x, the model should predict labels ˆ y from a pre-defined label set Y. From the description in the previous section, we can compute the distributed representation hj of the phrase at node j of a tree:

After this recursive process, the hidden state hR at the root node is used as the sentential representation, which then followed by a softmax classifier to predict the probability distribution over classes.

where ˆy is prediction probabilities, Wt and bt are the parameters of the classifier.

4.2 Text Semantic Matching

Among many natural language processing (NLP) tasks, a common problem is modelling the relevance of a pair of texts. In this section, we show how to effectively use the dynamic compositional neural networks to model the semantic relationship between two sentences.

As shown in Figure 3, given two sentences xa and xb, the representation of each sentence hR can be computed by one basic TreeNN.

where R denotes the root node of a tree. θa and θb are generated by a shared meta TreeNN. Then, the representation of each sentence will be fed into a multi-layer perceptron to obtain a unified representation for the final relationship classification.

The sample-specific but shared meta TreeNN ensures that, on the one hand we can dynamically model the diversity of semantic compositionality, on the other hand we can capture the general rules across different samples.

5 RelatedWork

One thread of related work is the exploration of different kinds of compositional function over tree structures. Socher et al. [2012] proposed the recursive neural network with standard compositional function (RecNN). After that, some extensions are introduced to enhance the expressive power of compositional function, such as MV-RecNN [Socher et al., 2013b], SU-RNN [Socher et al., 2013a], RNTN [Socher et al., 2013b], while these models suffer from the problem of hard-coded compositional operations and overfitting.

Another thread of work is the idea of using one network to direct the learning of another network [De Brabandere et al., 2016]. Naik and Mammone [1992] introduce a meta neural network to provide another network with a step size and a direction vector, which is helpful for parameter optimization. De Brabandere et al. [2016] propose the dynamic filter network to implicitly learn a variety of filtering operations. Bertinetto et al. [2016] introduce a learnet for one-shot learning, which can predict the parameters of a second network given a single exemplar. Ha et al. [2016] propose the model hypernetwork, which uses a small network to generate the weights for a larger network.

Different from these models, we employ the idea of parameter generation to address the limitation of weight-sharing or partially sharing paradigm of tree-based compositional models.

6 Experiment

To make a comprehensive evaluation, we assess our model on five text classification tasks and a semantic matching task.

6.1 Initialization and Hyperparameters

The word embeddings for all of the models are initialized with GloVe vectors [Pennington et al., 2014]. The other parameters are initialized by randomly sampling from uniform distribution in [-0.1, 0.1].

The final hyper-parameters are as follows. The initial learning rate is 0.1. The regularization weight of the parameters is 1E-5 and the others are listed as Table 1.

For all the sentences in the datasets, we parse them with constituency parser [Klein and Manning, 2003] to obtain the trees for our models and some competitor models.

6.2 Text Classification

We evaluate our models on five different datasets. The detailed statistics about the five datasets are listed in Table 2. Each dataset is briefly described as follows.

• SST The movie reviews with two classes (negative, positive) in the Stanford Sentiment Treebank [Socher et al., 2013b].
• MR The movie reviews with two classes [Pang and Lee, 2005].
• QC The TREC questions dataset involves six different question types. [Li and Roth, 2002].
• SUBJ Subjectivity dataset where the goal is to classify each instance (snippet) as being subjective or objective. [Pang and Lee, 2004]
• IE Idiom enhanced sentiment classification. [Williams et al., 2015]. Each sentence contains at least one idiom.

Results As shown in Table 3, DC-TreeLSTM consistently outperforms RecNN, MV-RecNN, RNTN, and TreeLSTM by a large margin while achieving comparable results to the CNN and using much fewer parameters.(The number of parameters in our models is approximately 10K while in CNN the number of parameters is about 400K). Compared with RecNN, DC-RecNN performs better, indicating the effectiveness of the dynamic compositional function. Additionally, both DC-RecNN and DC-TreeLSTM achieve substantial improvement on IE dataset, which covers the richness of compositionality (idiomaticity). We attribute the success on IE to its power in modeling more complicated compositionality.

6.3 Text Semantic Matching

We choose the dataset of Sentences Involving Compositional Knowledge (SICK), which is proposed by Marelli et al. [2014] aiming at evaluation of compositional distributional semantic models. The dataset consists of 9927 sentence pairs in a 4500/500/4927 train/dev/test split, in which each sentence pairs are pre-defined into three labels: "entailment","contradiction" and "neutral".

Results Our results are summarized in Table 4, where the performance of NBOW, LSTM, RecNN, and RNTN are reported by [Bowman et al., 2015; 2014]. For fair comparison, we train our models with the same setting. We can see both DC-RecNN and DC-TreeLSTM outperform competitor models, in which DC-RecNN (DC-TreeLSTM) achieves 3% (2.7%) improvements than RecNN (TreeLSTM). We think this breakthrough is basically attributed to the dynamic compositional mechanism, which enables our models to capture various syntactic patterns (As we will discuss later) therefore can more accurately understand sentences.

6.4 Discussion and Qualitative Analysis

In our models, the latent vector z controls the process of predicting network's parameters and its dimensionality determines the number of model's parameters. Next, we will investigate how the controlling vector z influences the performance of our models.

Impact of the Dimensionality Figure 4 shows the accuracies of DC-RecNN across the different dimensions of [5, 10, . . . , 50] for the controlling vector z on five datasets. We get the following findings:

• For all five datasets, the model can achieve considerable performances even when the size of vector z is reduced to 5. Particularly, for the dataset QC, the model obtains 87.0% accuracy with a pretty small meta Tree-RecNN 1 , suggesting a smaller meta network can be used for generating a more powerful compositional function to effectively model sentence.
• When dealing with the dataset with more labels, larger vector size leads to a better performance. For example, the performance on IE and QC datasets reaches the maximum when the size of z equals 40, while for the other three datasets MR, SST and SUBJ, the model obtains the best performance with the value of 30, 30 and 20 respectively.

Understanding the Neuron's Behaviours As described in previous sections, we know the compositional function is changed cross child nodes over a tree, which is controlled by a latent vector z. To get an intuitive understanding of how the controlling vector z works, we design an experiment to examine the neuron's behaviours of z on each node. More concretely, we refer to zjk as the activation of the k-neuron at node j, where j ∈ {1, . . . ,N} and k ∈ {1, . . . , z}. Then we randomly sample some sentences on the development set from the datasets we used. By visualizing the latent vector zj and analyzing the maximum activation, we can find what kinds of patterns the current neuron focuses on.

Table 5 illustrates multiple interpretable neurons and some representative words or phrases which can activate these neurons. We can observe that:

• For some simple tasks such as text classification, meta network will integrate useful semantic information into the the generation process of compositional function. These semantic bias before composition are taskspecific.

For example, the 21-st neuron is more sensitive to emotional terms, which can be understood as a sentinel, telling the basic neural network that an informative phrase is coming, more attention should be paid in the process of composition. Figure 5-(a) shows a visualization. We can see in this sentence, the neuron has realized that this idiomatic collocation "in stitches" is a key pattern, which is crucial for the final sentiment prediction.

• For more complicated tasks such as semantic matching, a well-grounded understanding of the syntactic structure is crucial. In this context, we find that a

1 With the same parameters, the RecNN obtain 74% accuracy in our implementation

meta network could capture some syntactic information. For example, the 27-th neuron monitors phrases constructed by light-verb. As shown in Figure 5-(b), the verb phrase "taking off" has been attended for forthcoming compositional operation, which is more useful for judging the semantic relation between the sentence pair "An airplane is taking off/A plane is landing".

7 Conclusion

In this work, we introduce a meta neural network, which can generate a compositional network to dynamically compose constituents over tree structure. The parameters of compositional function vary from position to position and from sample to sample, allowing for more sophisticated operations on the input.

To evaluate our models, we choose two typical NLP tasks involving six datasets. The qualitative and quantitative experiment results demonstrate the effectiveness of our models.

Acknowledgments

We would like to thank the anonymous reviewers for their valuable comments and thank Kaiyu Qian, Jiachen Xu, Jifan Chen for useful discussions. This work was partially funded by National Natural Science Foundation of China (No. 61532011 and 61672162), Shanghai Municipal Science and Technology Commission (No. 16JC1420401).