Self-Adaptive Hierarchical Sentence Model

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, average-pooling or max-pooling) over their word-vectors. The word-vectors, 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 non-linear 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 fixed-length 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.

Background

In the cBoW sentence model, the representation $\bar{h}$ for $\mathbf{x}_{1: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 $\mathbf{h}_{1:T}^{0}$, the hidden layer vector $h_{t}$ at time step $t$ is computed from a non-linear transformation of the current input vector $h_{t}^{0}$ and the hidden vector at the previous time step $h_{t-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(\cdot)$ be the component-wise non-linear transformation function. The dynamics of recurrent neural networks can be described by the following equations:

The sentence representation $\bar{h}$ is then the hidden vector obtained at the last time step, $h_{T}$, which summarizes all the past words. The composition dynamics in recurrent neural networks can be described by a chain as in Fig. 2(a).

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(W_{L}h_{l}+W_{R}h_{r}+b)$, where $h$ is the hidden representation for a parent node in the parsing tree and $h_{l}$, $h_{r}$ are the hidden representations for the left and right child of the parent node, respectively. $W_{L}$, $W_{R}$ 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. 2(b).

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.

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.

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., $\text{scope}(h^{1}_{j})=\{x_{j}\},\forall j\in 1:T$ and for any $t\geq 2$, define $\text{scope}(h^{t}_{j})=\text{scope}(h^{t-1}_{j})\cup\text{scope}(h^{t-1}_{j+1})$. Then the $t$th 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 $h^{t}_{j}$ is $\{\mathbf{x}_{j:j+t-1}\}$. Intuitively, for the sub-pyramid rooted at $h^{t}_{j}$, we can interpret $h^{t}_{j}$ as a top level summarization of the phrase $\mathbf{x}_{j:j+t-1}$ in the original sentence. For example, $h^{3}_{4}$ in Fig. 3 can be viewed as a summarization of the phrase on the mat.

In general, units at the $t$th 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.

2 Local Composition and Level Pooling

The recursive local composition in the pyramid works in the following way

Technically, when computing $h_{j}^{t}$, $\omega_{l},\omega_{c}$ and $\omega_{r}$ are parametrized functions of $h_{j}^{t-1}$ and $h_{j+1}^{t-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.

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 $t$th level, $t\in 1:T$, of the pyramid to obtain a summarization of all consecutive phrases of length $t$ in the original sentence, denoted by $\bar{h}^{t}$ (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 $\bar{h}^{1}$ corresponds to the representation returned by applying cBoW to the whole sentence. $[(\bar{h}^{1})^{T},\cdots,(\bar{h}^{T})^{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 Gating Network

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(\cdot)$ is the classifier and $w(\cdot)$ corresponds to the gating network in Fig. 1.

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 $\mathcal{L}(\cdot)$ be our scalar objective function. The goal is to derive the partial derivative of $\mathcal{L}$ with respect to the model parameters in AdaSent, i.e., two recurrent matrices, $W_{L}$, $W_{R}$ and two local composition matrices $G_{L},G_{R}$ (and their corresponding bias vectors):

The same analysis can be applied to compute $\frac{\partial\mathcal{L}}{\partial G_{L}}$ and $\frac{\partial\mathcal{L}}{\partial G_{R}}$. Taking into account the DAG structure of AdaSent, we can compute $\frac{\partial\mathcal{L}}{\partial h^{t}_{j}}$ recursively in the following way:

Now consider the left and right local BP formulations:

where $I$ is the identity matrix and $\text{diag}(f^{\prime})$ is a diagonal matrix spanned by the vector $f^{\prime}$, which is the derivative of $f(\cdot)$ 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 $\omega_{l}$, $\omega_{r}$ and $\omega_{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.

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.

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

MR. Movie reviews Pang and Lee (2005)https://www.cs.cornell.edu/people/pabo/movie-review-data/ data set where each instance is a sentence. The objective is to classify each review by its overall sentiment polarity, either positive or negative.

CR. Annotated customer reviews of 14 products obtained from Amazon Hu and Liu (2004)http://www.cs.uic.edu/$\sim$liub/FBS/sentiment-analysis.html. The task is to classify each customer review into positive and negative categories.

SUBJ. Subjectivity data set where the goal is to classify each instance (snippet) as being subjective or objective Pang and Lee (2004).

MPQA. Phrase level opinion polarity detection subtask of the MPQA data set Wiebe et al. (2005)http://mpqa.cs.pitt.edu/.

TREC. Question data set, in which the goal is to classify an instance (question) into 6 different types Li and Roth (2002)http://cogcomp.cs.illinois.edu/Data/QA/QC/.

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

NB-SVM and MNB. Naive Bayes SVM and Multinomial Naive Bayes with uni and bigram features Wang and Manning (2012).

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.

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.

P.V.. Paragraph Vector Le and Mikolov (2014) is an unsupervised model to learn distributed representations of words and paragraphs. We use the public implementation of P.V.https://github.com/mesnilgr/iclr15 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.

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.

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 $W_{L}$ and $W_{R}$ $\gg 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 $\mathcal{L}(\cdot,\cdot)$ be our objective function to minimize. For example, when $\mathcal{L}$ is the negative log-likelihood in the classification setting, our optimization can be formulated as

where $\mathbf{x}_{i}$ is the training sequence and $y_{i}$ is the label. The value of the regularization coefficient $\lambda$ is problem dependent. In our experiments, typical values of $\lambda$ range from $0.01$ to $5\times 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.

2.2 Implementation Details

Throughout our experiments, we use a 50-dimensional word embedding trained using word2vec Mikolov et al. (2013) on the Wikipedia corpus ($\sim$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.

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-of-the-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 400KThe state-of-the-art accuracy on TREC is 95.0 achieved by Silva et al. (2011) using SVM with 60 hand-coded features.. 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..

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(\mathcal{H}_{\mathbf{x}}=t|\mathbf{x}_{1:T}),\forall t$ and the second row shows the probability $\Pr(y=1|\mathcal{H}_{\mathbf{x}}=t),\forall 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.

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.

References