Incremental Parsing with Minimal Features Using Bi-Directional LSTM

Introduction

Recently, neural network-based parsers have become popular, with the promise of reducing the burden of manual feature engineering. For example, ?) and subsequent work replace the huge amount of manual feature combinations in non-neural network efforts [Nivre et al. (2006, Zhang and Nivre (2011] by vector embeddings of the atomic features. However, this approach has two related limitations. First, it still depends on a large number of carefully designed atomic features. For example, ?) and subsequent work such as ?) use 48 atomic features from ?), including select third-order dependencies. More importantly, this approach inevitably leaves out some nonlocal information which could be useful. In particular, though such a model can exploit similarities between words and other embedded categories, and learn interactions among those atomic features, it cannot exploit any other details of the text.

We aim to reduce the need for manual induction of atomic features to the bare minimum, by using bi-directional recurrent neural networks to automatically learn context-sensitive representations for each word in the sentence. This approach allows the model to learn arbitrary patterns from the entire sentence, effectively extending the generalization power of embedding individual words to longer sequences. Since such a feature representation is less dependent on earlier parser decisions, it is also more resilient to local mistakes.

With just three positional features we can build a greedy shift-reduce dependency parser that is on par with the most accurate parser in the published literature for English Treebank. This effort is similar in motivation to the stack-LSTM of ?), but uses a much simpler architecture.

We also extend this model to predict phrase-structure trees with a novel shift-promote-adjoin system tailored to greedy constituency parsing, and with just two more positional features (defining tree span) and nonterminal label embeddings we achieve the most accurate greedy constituency parser for both English and Chinese.

LSTM Position Features

The central idea behind this approach is exploiting the power of recurrent neural networks to let the model decide what apsects of sentence context are important to making parsing decisions, rather than relying on fallible linguistic information (which moreover requires leaving out information which could be useful). In particular, we model an input sentence using Long Short-Term Memory networks (LSTM), which have made a recent resurgence after being initially formulated by ?).

The input at each time step is simply a vector representing the word, in this case an embedding for the word form and one for the part-of-speech tag. These embeddings are learned from random initialization together with other network parameters in this work. In our initial experiments, we used one LSTM layer in each direction (forward and backward), and then concatenate the output at each time step to represent that sentence position: that word in the entire context of the sentence. This network is illustrated in Figure 1.

It is also common to stack multiple such LSTM layers, where the output of the forward and backward networks at one layer are concatenated to form the input to the next. We found that parsing performance could be improved by using two bi-directional LSTM layers in this manner, and concatenating the output of both layers as the positional feature representation, which becomes the input to the fully-connected layer. This architecture is shown in Figure 2.

Intuitively, this represents the sentence position by the word in the context of the sentence up to that point and the sentence after that point in the first layer, as well as modeling the “higher-order” interactions between parts of the sentence in the second layer. In Section 5 we report results using only one LSTM layer (“Bi-LSTM”) as well as with two layers where output from each layer is used as part of the positional feature (“2-Layer Bi-LSTM”).

Shift-Reduce Dependency Parsing

We use the arc-standard system for dependency parsing (see Figure 4). By exploiting the LSTM architecture to encode context, we found that we were able to achieve competitive results using only three sentence-position features to model parser state: the head word of each of the top two trees on the stack ($s_{0}$ and $s_{1}$), and the next word on the queue ($q_{0}$); see Table 1.

The usefulness of the head words on the stack is clear enough, since those are the two words that are linked by a dependency when taking a reduce action. The next incoming word on the queue is also important because the top tree on the stack should not be reduced if it still has children which have not yet been shifted. That feature thus allows the model to learn to delay a right-reduce until the top tree on the stack is fully formed, shifting instead.

The structure of our network model after computing positional features is fairly straightforward and similar to previous neural-network parsing approaches such as ?) and ?). It consists of a multilayer perceptron using a single ReLU hidden layer followed by a linear classifier over the action space, with the training objective being negative log softmax.

We found that performance could be improved, however, by factoring out the decision over structural actions (i.e., shift, left-reduce, or right-reduce) and the decision of which arc label to assign upon a reduce. We therefore use separate classifiers for those decisions, each with its own fully-connected hidden and output layers but sharing the underlying recurrent architecture. This structure was used for the results reported in Section 5, and it is referred to as “Hierarchical Actions” when compared against a single action classifier in Table 3.

Shift-Promote-Adjoin Constituency Parsing

To further demonstrate the advantage of our idea of minimal features with bidirectional sentence representations, we extend our work from dependency parsing to constituency parsing. However, the latter is significantly more challenging than the former under the shift-reduce paradigm because:

we also need to predict the nonterminal labels

the tree is not binarized (with many unary rules and more than binary branching rules)

While most previous work binarizes the constituency tree in a preprocessing step [Zhu et al. (2013, Wang and Xue (2014, Mi and Huang (2015], we propose a novel “Shift-Promote-Adjoin” paradigm which does not require any binariziation or transformation of constituency trees (see Figure 5). Note in particular that, in our case only the Promote action produces a new tree node (with a non-terminal label), while the Adjoin action is the linguistically-motivated “sister-adjunction” operation, i.e., attachment [Chiang (2000, Henderson (2003]. By comparison, in previous work, both Unary-X and Reduce-L/R-X actions produce new labeled nodes (some of which are auxiliary nodes due to binarization). Thus our paradigm has two advantages:

it dramatically reduces the number of possible actions, from $3X+1$ or more in previous work to $3+X$, where $X$ is the number of nonterminal labels, which we argue would simplify learning;

it does not require binarization [Zhu et al. (2013, Wang and Xue (2014] or compression of unary chains [Mi and Huang (2015]

There is, however, a more closely-related “shift-project-attach” paradigm by ?). For the example in Figure 5 he would use the following actions:

shift(I), project(NP), project(S), shift(like), project(VP), shift(sports), project(NP), attach, attach.

The differences are twofold: first, our Promote action is head-driven, which means we only promote the head child (e.g., VP to S) whereas his Project action promotes the first child (e.g., NP to S); and secondly, as a result, his Attach action is always right-attach whereas our Adjoin action could be either left or right. The advantage of our method is its close resemblance to shift-reduce dependency parsing, which means that our constituency parser is jointly performing both tasks and can produce both kinds of trees. This also means that we use head rules to determine the correct order of gold actions.

We found that in this setting, we did need slightly more input features. As mentioned, node labels are necessary to distinguish whether a tree has been sufficiently promoted, and are helpful in any case. We used 8 labels: the current and immediate predecessor label of each of the top two stacks on the tree, as well as the label of the left- and rightmost adjoined child for each tree. We also found it helped to add positional features for the leftmost word in the span for each of those trees, bringing the total number of positional features to five. See Table 1 for details.

Experimental Results

We report both dependency and constituency parsing results on both English and Chinese.

All experiments were conducted with minimal hyperparameter tuning. The settings used for the reported results are summarized in Table 6. Networks parameters were updated using gradient backpropagation, including backpropagation through time for the recurrent components, using ADADELTA for learning rate scheduling [Zeiler (2012]. We also applied dropout [Hinton et al. (2012] (with $p=0.5$) to the output of each LSTM layer (separately for each connection in the case of the two-layer network).

We tested both types of parser on the Penn Treebank (PTB) and Penn Chinese Treebank (CTB-5), with the standard splits for each of training, development, and test sets. Automatically predicted part of speech tags with 10-way jackknifing were used as inputs for all tasks except for Chinese dependency parsing, where we used gold tags, following the traditions in literature.

Table 2 shows results for English Penn Treebank using Stanford dependencies. Despite the minimally designed feature representation, relatively few training iterations, and lack of pre-computed embeddings, the parser performed on par with state-of-the-art incremental dependency parsers, and slightly outperformed the state-of-the-art greedy parser.

The ablation experiments shown in the Table 3 indicate that both forward and backward contexts for each word are very important to obtain strong results. Using only word forms and no part-of-speech input similarly degraded performance.

Figure 6 compares our parser with that of ?) in terms of arc recall for various arc lengths. While the two parsers perform similarly on short arcs, ours significantly outpeforms theirs on longer arcs, and more interestingly our accuracy does not degrade much after length 6. This confirms the benefit of having a global sentence repesentation in our model.

Table 4 summarizes the Chinese dependency parsing results. Again, our work is competitive with the state-of-the-art greedy parsers.

2 Constituency Parsing: English & Chinese

Table 5 compares our constituency parsing results with state-of-the-art incremental parsers. Although our work are definitely less accurate than those beam-search parsers, we achieve the highest accuracy among greedy parsers, for both English and Chinese. The greedy accuracies for ?) are from Haitao Mi, and greedy results for ?) come from duplicating experiments with code provided by those authors., The parser of ?) does not use an explicit transition system, but is similar in spirit since generating a right bracket can be viewed as a reduce action.

Related Work

Because recurrent networks are such a natural fit for modeling languages (given the sequential nature of the latter), bi-directional LSTM networks are becoming increasingly common in all sorts of linguistic tasks, for example event detection in ?). In fact, we discovered after submission that ?) have concurrently developed an extremely similar approach to our dependency parser. Instead of extending it to constituency parsing, they also apply the same idea to graph-based dependency parsing.

Conclusions

We have presented a simple bi-directional LSTM sentence representation model for minimal features in both incremental dependency and incremental constituency parsing, the latter using a novel shift-promote-adjoin algorithm. Experiments show that our method are competitive with the state-of-the-art greedy parsers on both parsing tasks and on both English and Chinese.

Acknowledgments

We thank the anonymous reviewers for comments. We also thank Taro Watanabe, Muhua Zhu, and Yue Zhang for sharing their code, Haitao Mi for producing greedy results from his parser, and Ashish Vaswani and Yoav Goldberg for discussions. The authors were supported in part by DARPA FA8750-13-2-0041 (DEFT), NSF IIS-1449278, and a Google Faculty Research Award.

References