Self-Adaptive Hierarchical Sentence Model

1 Introduction

The goal of sentence modeling is to represent the meaning of a sentence so that it can be used as input for other tasks. Previously, this task was often cast as semantic parsing, which aims to find a logical form that can describe the sentence. With recent advances in distributed representations and deep neural networks, it is now common practice to find a vectorial representation of sentences, which turns out to be quite effective for tasks of classification [Kim, 2014], machine translation [Cho et al., 2014; Bahdanau et al., 2015], and semantic matching [Hu et al., 2014].

Perhaps the simplest method in this direction is the continuous Bag-of-Words (cBoW), where the representations of sentences are obtained by global pooling (e.g, averagepooling or max-pooling) over their word-vectors. The wordvectors, also known as word-embedding, can be determined in either supervised or unsupervised fashion. cBoW, although effective at capturing the topics of sentences, does not consider the sequential nature of words, and therefore has difficulty capturing the structure of sentences. There has been a surge of sentence models with the order of words incorporated, mostly based on neural networks of various forms, including recursive neural networks [Socher et al., 2010; 2012; 2013], recurrent neural network [Irsoy and Cardie, 2014; Lai et al., 2015], and convolution neural network [Kalchbrenner et al., 2014; Kim, 2014]. These works apply levels of nonlinear transformations to model interactions between words and the structure of these interactions can also be learned on the fly through gated networks [Cho et al., 2014]. However these models output a fixed length continuous vector that does not retain intermediate information obtained during the composition process, which may be valuable depending on the task at hand.

In this paper, we propose a self-adaptive hierarchical sentence model (AdaSent). Instead of maintaining a fixedlength continuous vectorial representation, our model forms a multi-scale hierarchical representation. AdaSent is inspired from the gated recursive convolutional neural network (grConv) [Cho et al., 2014] in the sense that the information flow forms a pyramid with a directed acyclic graph structure where local words are gradually composed to form intermediate representations of phrases. Unlike cBoW, recurrent and recursive neural networks with fixed structures, the gated nature of AdaSent allows the information flow to vary with each task (i.e., no need for a pre-defined parse tree). Unlike grConv, which outputs a fixed-length representation of the sentence at the top of the pyramid, AdaSent uses the intermediate representations at each level of the pyramid to form a multiscale summarization. A convex combination of the representations at each level is used to adaptively give more weight to some levels depending on the sentence and the task. Fig. 1 illustrates the architecture of AdaSent and compares it to cBoW, recurrent neural networks and recursive neural networks.

Our contributions can be summarized as follows. First, we propose a novel architecture for short sequence modeling which explores a new direction to use a hierarchical multiscale representation rather than a flat, fixed-length representation. Second, we qualitatively show that our model is able to automatically learn the representation which is suitable for the task at hand through proper training. Third, we conduct extensive empirical studies on 5 benchmark data sets to quantitatively show the superiority of our model over previous approaches.

2 Background

Let x1:T denote the input sequence with length T . Each token xt ∈ x1:T is a V dimensional one-hot binary vector to encode the ith word, where V is the size of the vocabulary. We use U ∈ Rd×V to denote the word embedding matrix, in which the jth column is the d-dimensional distributed representation of the jth word in the vocabulary. Hence the word vectors for the sequence x1:T is obtained by h01:T = Ux1:T .

In the cBoW sentence model, the representation ¯h for x1:T is obtained by global pooling, either average pooling (Eq. 1) or max pooling (Eq. 2), over all the word vectors:

It is clear that cBoW is insensitive to the ordering of words and also the length of a sentence, hence it is likely for two different sentences with different semantic meanings to be embedded into the same vector representation.

Recurrent neural networks [Elman, 1990] are a class of neural networks where recurrent connections between input units and hidden units are formed through time. The sequential nature of recurrent neural networks makes them applicable to various sequential generation tasks, e.g., language modeling [Mikolov et al., 2010] and machine translation [Bahdanau et al., 2015; Cho et al., 2014].

Given a sequence of word vectors h01:T , the hidden layer vector ht at time step t is computed from a non-linear transformation of the current input vector h0t and the hidden vector at the previous time step ht-1. Let W be the input-hidden connection matrix, H be the recurrent hidden-hidden connection matrix and b be the bias vector. Let f(·) be the component-wise non-linear transformation function. The dynamics of recurrent neural networks can be described by the following equations:

The sentence representation ¯h is then the hidden vector obtained at the last time step, hT , which summarizes all the past words. The composition dynamics in recurrent neural networks can be described by a chain as in Fig. 2a.

• (a) Composition process in a recurrent neural network.

Figure 2: Composition dynamics in recurrent and recursive neural networks. The one-hot binary encoding of word sequences is first multiplied by the word embedding matrix U to obtain the word vectors before entering the network.

Recursive neural networks build on the idea of composing along a pre-defined binary parsing tree. The leaves of the parsing tree correspond to words, which are initialized by their word vectors. Non-linear transformations are recursively applied bottom-up to generate the hidden representation of a parent node given the hidden representations of its two children. The composition dynamics in a recursive neural network can be described as h = f(WLhl +WRhr + b), where h is the hidden representation for a parent node in the parsing tree and hl, hr are the hidden representations for the left and right child of the parent node, respectively. WL, WR are left and right recursive connection matrices. Like in recurrent neural networks, all the parameters in recursive neural networks are shared globally. The representation for the whole sentence is then the hidden vector obtained at the root of the binary parsing tree. An example is shown in Fig. 2b.

Although the composition process is nonlinear in recursive neural network, it is pre-defined by a given binary parsing tree. Gated recursive convolutional neural network (grConv) [Cho et al., 2014] extends recursive neural network through a gating mechanism to allow it to learn the structure of recursive composition on the fly. If we consider the composition structure in a recurrent neural network as a linear chain and the composition structure in a recursive neural network as a binary tree, then the composition structure in a grConv can be described as a pyramid, where word representations are locally combined until we reach the top of the pyramid, which gives us the global representation of a whole sentence. We refer interested readers to [Cho et al., 2014] for more details about grConv.

3 Self-Adaptive Hierarchical Sentence Model

AdaSent is inspired and built based on grConv. AdaSent differs from grConv and other neural sentence models that try to obtain a fixed-length vector representation by forming a hierarchy of abstractions of the input sentence and by feeding the hierarchy as a multi-scale summarization into the following classifier, combined with a gating network to decide the weight of each level in the final consensus, as illustrated in Fig. 1.

3.1 Structure

The structure of AdaSent is a directed acyclic graph as shown in Fig. 3. For an input sequence of length T, AdaSent is a pyramid of T levels. Let the bottom level be the first level and the top level be the T th level. Define the scope of each unit in the first layer to be the corresponding word, i.e., scope(h1j ) = {xj}, ∀j ∈ 1 : T and for any t ≥ 2, define scope(htj ) = scope(ht-1 j ) ∪ scope(ht-1 j+1 ). Then the tth level in AdaSent contains a layer of T -t+1 units where each unit has a scope of size t. More specifically, the scope of htj is {xj:j+t-1}. Intuitively, for the sub-pyramid rooted at htj , we can interpret htj as a top level summarization of the phrase xj:j+t-1 in the original sentence. For example, h34 in Fig. 3 can be viewed as a summarization of the phrase on the mat.

the the

Figure 3: Composition dynamics in AdaSent. The jth unit on the tth level is an intermediate hidden representation of the phrase xj:j+t-1 in the original sentence. All the units on the tth level are then pooled to obtain the tth level representation in the hierarchy H.

In general, units at the tth level are intermediate hidden representations of all the consecutive phrases of length t in the original sentence (see the scopes of units at the 3rd level in Fig. 3 for an example). There are two extreme cases in AdaSent: the first level contains word vectors and the top level is a global summarization of the whole sentence.

Before the pre-trained word vectors enter into the first level of the pyramid, we apply a linear transformation to map word vectors from Rd to RD with D ≥ d. That way we can allow phrases and sentences to be in a space of higher dimension than words for their richer structures. More specifically, the hidden representation h11:T at the first level of the pyramid is

where U ′ ∈ RD×d is the linear transformation matrix in AdaSent and U ∈ Rd×V is the word-embedding matrix trained with a large unlabeled corpus. Equivalently, one can view ˜ U ≜ U ′U ∈ RD×V as a new word-embedding matrix tailored for AdaSent. This factorization of the wordembedding matrix also helps to reduce the effective number of parameters in our model when d ≪ D.

3.2 Local Composition and Level Pooling

The recursive local composition in the pyramid works in the following wayhtj = ωlht-1 j +ωrht-1 j+1 + ωc ˜htj (5)

where j ranges from 1 to T - t + 1 and t ranges from 2 to T. WL,WR ∈ RD×D are the hidden-hidden combination matrices, dubbed recurrent matrices, and bW ∈ RD is a bias vector. ωl, ωr and ωc are the gating coefficients which satisfy ωl, ωr, ωc ≥ 0 and ωl + ωr + ωc = 1. Eq. 6 provides a way to compose the hidden representation of a phrase of length t from the hidden representation of its left t - 1 prefix and its right t - 1 suffix. The composition in Eq. 6 includes a non-linear transformation, which allows a flexible hidden representation to be formed. The fundamental assumption behind the structure of AdaSent is then encoded in Eq. 5: the semantic meaning of a phrase of length t is a convex combination of the semantic meanings of its t - 1 prefix, t - 1 suffix and the composition of these two. For example, we expect the meaning of the phrase the cat to be expressed by the word cat since the is only a definite article, which does not have a direct meaning. On the other hand, we also hope the meaning of the phrase not happy to consider both the functionality of not and also the meaning of happy. We design the local composition in AdaSent to make it flexible enough to catch the above variations in language while letting the gating mechanism (the way to obtain ωl, ωr and ωc) adaptively decide the most appropriate composition from the current context.

Technically, when computing htj , ωl, ωc and ωr are parametrized functions of ht-1 j and ht-1 j+1 such that they can decide whether to compose these two children by a non-linear transformation or simply to forward the children's representations for future composition. For the purpose of illustration, we use the softmax function to implement the gating mechanism during the local composition in Eq. 7. But note that we are not limited to a specific choice of gating mechanism. One can adopt more complex systems, e.g., MLP, to implement the local gating mechanism as long as the output of the system is a multinomial distribution over 3 categories.

GL, GR ∈ R3×D and bG ∈ R3 are shared globally inside the pyramid. The softmax function over a vector is defined as:

Local compositions are recursively applied until we reach the top of the pyramid.

It is worth noting that the recursive local composition in AdaSent implicitly forms a weighted model average such that each unit at layer t corresponds to a convex combination of all possible sub-structures along which the composition process is applied over the phrase of length t. This implicit weighted model averaging makes AdaSent more robust to local noises and deteriorations than recurrent nets and recursive nets where the composition structure is unique and rigid. Fig. 4 shows an example when t = 3.

Once the pyramid has been built, we apply a pooling operation, either average pooling or max pooling, to the tth level, t ∈ 1 : T, of the pyramid to obtain a summarization of all consecutive phrases of length t in the original sentence, denoted by ¯ht (see an example illustrated in Fig. 3 for the global level pooling applied to the 3rd level in the pyramid). It is straightforward to verify that ¯h1 corresponds to the representation returned by applying cBoW to the whole sentence. [(¯h1 )T , · · · , (¯hT )T ]T then forms the hierarchy in which lower level summarization in the hierarchy pays more attention to local words or short phrases while higher level summarization focuses more on the global interaction of different parts in the sentence.

3.3 Gating Network

Suppose we are interested in a classification problem, one can easily extend our approach to other problems of interests. Let g(·) be a discriminative classifier that takes ¯ht ∈ RD as input and outputs the probabilities for different classes. Let w(·) be a gating network that takes ¯ht ∈ RD , t = 1, . . . , T as input and outputs a belief score 0 ≤ γt ≤ 1. Intuitively, the belief score γt depicts how confident the tth level summarization in the hierarchy is suitable to be used as a proper representation of the current input instance for the task at hand. We require γt ≥ 0, ∀t and ∑Tt=1 γt = 1.

Let C denote the categorical random variable corresponding to the class label. The consensus of the whole system is reached by taking a mixture of decisions made by levels of summarizations from the hierarchy:

where each g(·) is the classifier and w(·) corresponds to the gating network in Fig. 1.

3.4 Back Propagation through Structure

We use back propagation through structure (BPTS) [Goller and Kuchler, 1996] to compute the partial derivatives of the objective function with respect to the model parameters. Let L(·) be our scalar objective function. The goal is to derive the partial derivative of L with respect to the model parameters in AdaSent, i.e., two recurrent matrices, WL, WR and two local composition matrices GL,GR (and their corresponding bias vectors):

The same analysis can be applied to compute ∂L ∂GL and ∂L ∂GR . Taking into account the DAG structure of AdaSent, we can compute ∂L ∂htj recursively in the following way:

Now consider the left and right local BP formulations:

where I is the identity matrix and diag(f ′ ) is a diagonal matrix spanned by the vector f ′ , which is the derivative of f(·) with respect to its input. The identity matrix in Eq. 12 and Eq. 13 plays the same role as the linear unit recurrent connection in the memory block of LSTM [Hochreiter and Schmidhuber, 1997] to allow the constant error carousel to effectively prevent the gradient vanishing problem that commonly exists in recurrent neural nets and recursive neural nets. Also, the local composition weights ωl, ωr and ωc in Eq. 12 and Eq. 13 have the same effect as the forgetting gate in LSTM [Gers et al., 2000] by allowing more flexible credit assignments during the back propagation process.

4 Experiments

In this section, we study the empirical performance of AdaSent on 5 benchmark data sets for sentence and short phrase classification and then compare it to other competitor models. We also visualize the representation of the input sequence learned by AdaSent by projecting it in a 2 dimensional space using PCA to qualitatively study why AdaSent works for short sequence modeling.

4.1 Experimental Setting

Statistics about the data sets used in this paper are listed in Table 1. We describe each data set in detail below:

1. MR. Movie reviews [Pang and Lee, 2005] 1 data set where each instance is a sentence. The objective is to classify each review by its overall sentiment polarity, either positive or negative.
2. CR. Annotated customer reviews of 14 products obtained from Amazon [Hu and Liu, 2004] 2 . The task is to classify each customer review into positive and negative categories.
3. SUBJ. Subjectivity data set where the goal is to classify each instance (snippet) as being subjective or objective [Pang and Lee, 2004].
4. MPQA. Phrase level opinion polarity detection subtask of the MPQA data set [Wiebe et al., 2005] 3 .
5. TREC. Question data set, in which the goal is to classify an instance (question) into 6 different types [Li and Roth, 2002] 4 .

We compare AdaSent with different methods listed below on the five data sets.

1. NB-SVM and MNB. Naive Bayes SVM and Multinomial Naive Bayes with uni and bigram features [Wang and Manning, 2012].
2. RAE and MV-RecNN. Recursive autoencoder [Socher et al., 2011] and Matrix-vector recursive neural network [Socher et al., 2012]. In these two models, words are gradually composed into phrases and sentence along a binary parse tree.
3. CNN [Kim, 2014] and DCNN [Kalchbrenner et al., 2014]. Convolutional neural network for sentence modeling. In DCNN, the author applies dynamic k-max pooling over time to generalize the original max pooling in traditional CNN.
4. P.V.. Paragraph Vector [Le and Mikolov, 2014] is an unsupervised model to learn distributed representations of words and paragraphs. We use the public implemen-

1 https://www.cs.cornell.edu/people/pabo/movie-review-data/

2 http://www.cs.uic.edu/∼liub/FBS/sentiment-analysis.html

3 http://mpqa.cs.pitt.edu/

4 http://cogcomp.cs.illinois.edu/Data/QA/QC/

• tation of P.V. 5 and use logistic regression on top of the pre-trained paragraph vectors for prediction.
• cBoW. Continuous Bag-of-Words model. As discussed above, we use average pooling or max pooling as the global pooling mechanism to compose a phrase/sentence vector from a set of word vectors.
• RNN, BRNN. Recurrent neural networks and bidirectional recurrent neural networks [Schuster and Paliwal, 1997]. For bidirectional recurrent neural networks, the reader is referred to [Lai et al., 2015] for more details.
• GrConv. Gated recursive convolutional neural network [Cho et al., 2014] shares the pyramid structure with AdaSent and uses the top node in the pyramid as a fixed length vector representation of the whole sentence.

4.2 Training

The difficulty of training recurrent neural networks is largely due to the notorious gradient exploding and gradient vanishing problem [Bengio et al., 1994; Pascanu et al., 2013]. As analyzed and discussed before, the DAG structure combined with the local gating composition mechanism of AdaSent naturally help to avoid the gradient vanishing problem. However, the gradient exploding problem still exists as we observe in our experiments. In this section, we discuss our implementation details to mitigate the gradient exploding problem and we give some practical tricks to improve the performance in the experiments.

Regularization of Recurrent Matrix

The root of the gradient exploding problem in recurrent neural networks and other related models lies in the large spectral norm of the recurrent matrix as shown in Eq. 12 and Eq. 13. Suppose the spectral norm of WL and WR ≫ 1, then the recursive application of Eq. 12 and Eq. 13 in the back propagation process will cause the norm of the gradient vector to explode. To alleviate this problem, we propose to penalize the Frobenius norm of the recurrent matrix, which acts as a surrogate (upper bound) of the corresponding spectral norm, since 1) it is computationally expensive to compute the exact value of spectral norm and 2) it is hard to establish a direct connection between the spectral norm and the model parameters to incorporate it into our objective function. Let L(·, ·) be our objective function to minimize. For example, when L is the negative log-likelihood in the classification setting, our optimization can be formulated as

where xi is the training sequence and yi is the label. The value of the regularization coefficient λ is problem dependent. In our experiments, typical values of λ range from 0.01 to 5 × 10-5 . For all our experiments, we use minibatch AdaGrad [Duchi et al., 2011] with the norm-clipping technique [Pascanu et al., 2013] to optimize the objective function in Eq. 14.

5 https://github.com/mesnilgr/iclr15

Implementation Details

Throughout our experiments, we use a 50-dimensional word embedding trained using word2vec [Mikolov et al., 2013] on the Wikipedia corpus (∼1B words). The vocabulary size is about 300,000. For all the tasks, we fine-tune the word embeddings during training to improve the performance [Collobert et al., 2011]. We use the hyperbolic tangent function as the activation function in the composition process as the rectified linear units [Nair and Hinton, 2010] are more prone to the gradient exploding problem in recurrent neural networks and its related variants. We use an MLP to implement the classifier on top of the hierarchy and use a softmax function to implement the gating network. We also tried using MLP to implement the gating network, but this does not improve the performance significantly.

4.3 Experiment Results

The classification accuracy of AdaSent compared with other models is shown in Table 2. AdaSent consistently outperforms P.V., cBoW, RNN, BRNN and GrConv by a large margin while achieving comparable results to the state-ofthe-art and using much fewer parameters: the number of parameters in our models range from 10K to 100K while in CNN the number of parameters is about 400K 6 . AdaSent outperforms all the other models on the MPQA data set, which consists of short phrases (the average length of each instance in MPQA is 3). We attribute the success of AdaSent on MPQA to its power in modeling short phrases since long range dependencies are hard to detect and represent.

Compared with BRNN, the level-wise global pooling in AdaSent helps to explicitly model phrases of different lengths while in BRNN the summarization process is more sensitive to a small range of nearby words. Hence, AdaSent consistently outperforms BRNN on all data sets. Also, AdaSent significantly outperforms GrConv on all the data sets, which indicates that the variable length multi-scale representation is key to its success. As a comparison, GrConv does not perform well because it fails to keep the intermediate representations. More results on using GrConv as a fixed-length sequence encoder for machine translation and related tasks can be found in [Cho et al., 2014]. cBoW is quite effective on some tasks (e.g., SUBJ). We think this is due to the language regularities encoded in the word vectors and also the characteristics of the data itself. It is surprising that P.V. performs worse than other methods on the MPQA data set. This may be due to the fact that the average length of instances in MPQA is small, which limits the number of context windows when training P.V..

6 The state-of-the-art accuracy on TREC is 95.0 achieved by [Silva et al., 2011] using SVM with 60 hand-coded features.

We also report model variance of P.V., cBoW, RNN, BRNN, GrConv and AdaSent in Table 3 by running each of the models on every data set 10 times using different settings of hyper-parameters and random initializations. We report the mean classification accuracy and also the standard deviation of the 10 runs on each of the data set. Again, AdaSent consistently outperforms all the other competitor models on all the data sets.

To study how the multi-scale hierarchy is combined by AdaSent in the final consensus, for each data set, we sample two sentences with a pre-specified length and compute their corresponding belief scores. We visualize the belief scores of 10 sentences by a matrix shown in Fig. 5. As illustrated in Fig. 5, the distribution of belief scores varies among different input sentences and also different data sets. The gating network is trained to adaptively select the most appropriate representation in the hierarchy by giving it the largest belief score. We also give a concrete example from MR to show both the predictions computed from each level and their corresponding belief scores given by the gating network in Fig. 6. The first row in Fig. 6 shows the belief scores Pr(Hx = t|x1:T ), ∀t and the second row shows the probability Pr(y = 1|Hx = t), ∀t predicted from each level in the hierarchy. In this example, although the classifier predicts incorrectly for higher level representations, the gating network assigns the first level with the largest belief score, leading to a correct final consensus. The flexibility of multiscale representation combined with a gating network allows AdaSent to generalize GrConv in the sense that GrConv corresponds to the case where the belief score at the root node is 1.0.

To show that AdaSent is able to automatically learn the appropriate representation for the task at hand, we visualize the first two principal components (obtained by PCA) of the vector with the largest weight in the hierarchicy for each sentence in the dataset. Fig. 7 shows the projected features from AdaSent (left column) and cBoW (right column) for SUBJ (1st row), MPQA (2nd row) and TREC (3rd row). During training, the model implicitly learns a data representation that enables better prediction. This property of AdaSent is very interesting since we do not explicitly add any separation constraint into our objective function to achieve this.

5 Conclusion

In this paper, we propose AdaSent as a new hierarchical sequence modeling approach. AdaSent explores a new direction to represent a sequence by a multi-scale hierarchy instead of a flat, fixed-length, continuous vector representation. The analysis and the empirical results demonstrate the effectiveness and robustness of AdaSent in short sequence modeling. Qualitative results show that AdaSent can learn to represent input sequences depending on the task at hand.

Acknowledgments

This work was done when the first and third authors were respectively an intern and a visiting scholar at Noah's Ark Lab, Huawei Technology, Hong Kong. Han Zhao thanks Tao Cai and Baotian Hu at Noah's Ark Lab for their technical support and helpful discussions. This work is supported in part by China National 973 project 2014CB340301.