Combine Constituent and Dependency Parsing via Reranking

1 Introduction

Parsing is to infer the grammatical structure of a natural language sentence with respect to a given grammar. For different types of grammar, parsing techniques may vary greatly. Currently, two types of grammar, namely, context-free grammar and dependency grammar, are the most dominant ones in parsing. The availability of large-scale treebanks, in particular, the Penn Treebank (PTB) [Marcus et al., 1993] and Prague Dependency Treebank [Hajic et al., 2001], allows a wide variety of machine learning methods to facilitate both types of parsing.

These two grammars are so closely related to each other that a constituent tree can be converted into a dependency tree using a set of heuristic head rules [Yamada and Matsumoto, 2003]. The word-to-word selectional affinities in a dependency tree can be helpful to syntactic disambiguation for its constituent correspondence. There are successful lexicalized PCFG-based models [Collins, 1997; Charniak, 2000; Bikel, 2004] that include the lexical head of each constituent for the derivation of a constituent tree, at the cost of increasing the complexity of parsing. To reduce such complexity, Klein and Manning [2002] propose a factorization method to split the joint parsing into two generative sub-models. The constituent and dependency structure of a sentence are evaluated independently in order to select the best combination of them.

In this paper, we present an alternative approach to combining constituent and dependency parsing via a factored model for performance enhancement on both sides. Different from the previous works, our approach has the following advantages.

• Both constituent and dependency parsing are formulated under the discriminative framework, which is more capable of incorporating a large variety of features than a generative model. The two types of parsing thus have a better chance to benefit from the complementarity of feature selection.
• Instead of relying on complex joint inference, we opt to rerank the k-best outputs from a constituent parser with a dependency model. This design is highly modularized so that any constituent model (e.g., the Berkeley parser) can be used as long as it outputs k-best constituent trees. The dependency model also has its sub-models that can be switched on or off conveniently. Also, we do not need to retrain the constituent and dependency (sub-) models.
• This approach is computationally efficient, in that it gets around the complexity of joint inference. The efficiency of reranking allows our dependency model to use a rich set of high-order features.

Our experiments show that this approach significantly improves the performance of both sub-models involved. For constituent parsing, our factored parsing model achieves the F1 scores of 91.97% and 85.79% on the WSJ and CTB5.1 datasets, respectively. For dependency parsing, it also obtains the unlabeled attachment score (UAS) of 93.71% and 87.38% on these two datasets. All these results are comparative or even superior to those by the state-of-the-art parsers reported so far.

The remainder of this paper is organized as follows. Section 2 describes the factored parsing model, including its constituent and dependency sub-model. Section 3 presents our reranking method. Experimental results are reported in Section 4, and related works discussed in Section 5. Section 6 concludes our work and looks into some future directions of research.

2 ParsingModel

Figure 1 illustrates a constituent parse tree and its corresponding dependency tree. Combining these two trees will give a lexicalized parse tree as used in a lexicalized constituent parsing model. Let T be a lexicalized parse tree for an input sentence s = w1w2...wn, which can be projected to a constituent tree t and a dependency tree d. Our factored parsing model is formulated under the product-of-experts framework [Hinton, 2002] as

where P(t|s) and P(d|s) are the constituent and the dependency parsing model, respectively, and Z is a normalization factor, a constant for s that does not need to be calculated in our model. Each T = 〈t, d〉 is evaluated with the two submodels, and the best T is two latent structures that receive the highest joint score by both sub-models.

2.1 Constituent Parsing

The constituent parser presented in [Chen and Kit, 2012] and [Chen, 2012] is used in this work. Its training follows the idea of forest re-scoring [Huang, 2008]. However, we enforce a factorization assumption for our constituent model to ensure its tractability. It is that all features are restricted to depend on the structures within a local context for each instance of grammar rule in a parse tree, and the local context consists of only immediate neighbors of the instance.

Following Collins [2002], our model g(t, s) is formulated in the linear form asg(t, s) = θ · Ψ(t, s), (2)

where Ψ(t, s) is a feature vector and θ the vector of associated weights. The factorization assumption induces the decomposition of a feature vector as

where U is the collection of all instances of grammar rule in t, Q(u) a part of t centered around u, and Φ(Q(u), s) the feature vector for Q(u). Following Collins [2002] and Huang [2008], we opt for the averaged perceptron algorithm to estimate θ from a training treebank.

In order to combine this model with a dependency model, the score of the above model needs to be normalized, i.e.,

where T(s) is the collection of all possible constituent trees for s.

Features. Similar to the previous forest re-scoring methods, our approach also adopts a PCFG-based model to generate a score for each instance of grammar rule to describe its likelihood of covering a particular span over an input sentence, and uses it as a basic feature for our constituent model. The unlexicalized PCFG-LA is used to calculate this feature:

where u is an instance of grammar rule A → B C covering word span [i, j) and splitting at k, x, y and z are latent variables in the PCFG-LA, and I(·) and O(·) are the inside and outside probabilities, respectively.

All other features φk(Q(u), s) are binary functions indicating whether a configuration is contained in Q(u) and s. Two types of feature, namely, lexical and structural, are used in the constituent model. Lexical features bind words with the CFG rules that cover them, which can be viewed as a way of lexicalization of the base PCFG-LA. Structural features capture the dependencies between grammar rule instances. The feature templates 1 used in our constituent model are listed in Table 1. Note that the lexical features in this model do not involve any lexical head or bilexical dependency. Such information is utilized in the dependency parsing model.

2.2 Dependency Parsing

In our dependency parsing model, the score of a dependency tree is determined by two factors, namely, the individual edges and the relations between edges in the tree. Accordingly, the model is formulated as

to evaluate the event that d is the dependency tree of s, through its two sub-models: the edge model ge(d, s) to measure the goodness of all dependency edges in d and the edgepair model gr(d, s) to measure the likelihood of two edges to form a relation of certain type.

1 Its source code is released to the public at http://code.google. com/p/gazaparser/.

Like the graph-based method [McDonald et al., 2005a; 2005b], our edge model defines the score of a dependency tree as the sum of scores of all its edges, and the edge-pair model describes the structure of a dependency tree in terms of edge-pair relations. Possible relations between two edges include parent-child, sibling, adjacent, etc. The edge-pair model calculates a score for d by summing up the scores of all types of relations for each edge-pair in d. That is,

where h(e) is the score of an edge e, R the set of relations defined by the model, and hr(ei, ej) the score for the edgepair (ei, ej) in relation r.

The scores h(e) and hr(ei, ej) can be defined in a linear form as in our constituent model and many other dependency parsing models [McDonald et al., 2005a; 2005b; Koo and Collins, 2010]. They can also be calculated using a general-purpose machine learning model, as in the previous work of Jiang and Liu [2010]. In this work, we use the maximum entropy (ME) classifier for this purpose. The score of an edge is computed as

where Φ(e, c) is a feature vector for e being classified as c, and ω its corresponding weight vector. The value of c ∈ {+,-} indicates whether the word pair in e forms a dependency edge.

For the edge-pair model, we adopt two most profitable relations between two edges: parent-child and adjacent. The score of an edge-pair (ei, ej) in a relation is calculated in a similar way as the above, i.e.,

For the sake of combination, this dependency model also needs normalization:

where D(s) is the set of all possible dependency trees for s.

Three ME classifiers, one for edges, and the other two for parent-child and adjacent edge pairs, are trained on three sets of classification instances extracted from a training treebank. A dependency edge e is taken, together with its classification results, as a training instance for the edge classifier. So is an edge-pair (ei, ej) for the edge-pair classifier. For a dependency tree with n words, there are n positive and n(n - 2) negative training instances for the edge classifier, e.g., (ei,+) for 0 ≤ i < n and (ej,-), and there are n - 1 positive and n(n - 1)2 negative training instances for the edge-pair classifier, e.g., (ei, ej , +) for 0 ≤ i ̸= j < n and (ei, ej , -).

The number of negative training instances m is usually set proportional to the positive ones: m = γn, with γ to be tuned using a development set. Our experiments to find the optional γ show that the best performance of our dependency parser is achieved by extracting all positive and negative instances for training the classifiers.

Features. Our dependency model adopts a similar set of features as in McDonald et al. [2005a] and Carreras [2007] that are shown to be effective. Let e be a dependency edge from word wi to wj. Its features include the words and POS tags surrounding the child wj and/or its parent wi, and the distance of the two words di,j = i - j. The feature templates for the edge model are combinations of the basic elements listed in Table 2, where px is the part-of-speech of wx.

Some features are conjoined with the distance feature between the two words in question. This significantly improves the performance of our edge model. Moreover, we opt for a similar set of feature templates for the edge-pair model. Each of its feature instances contains two edges, i.e., grandparent and parent, parent and child. The edge-pair feature are extracted from a dependency tree according to the basic elements in Table 2, where dei,ej represents the relationship of two edges, and 0 and 1 represent the adjacent and parentchild relationship of ei and ej, respectively. The features in the edge-pair model are two times as many as those in the edge model.

3 Reranking

With the factored parsing model, finding the best lexicalized parse tree ̂ T for an input sentence involves a joint inference with the two sub-models, i.e.,

Since both sub-models are very complex, the joint inference is not computationally efficient. Therefore, we opt for a shortcut that uses the dependency model to rerank the k-best outputs from the constituent model. The reranking involves the following steps.

• Generate a list of k-best constituent trees for an input sentence using the constituent model, with a probability P(t|s) assigned to each tree.
• Convert the k-best constituent trees into dependency trees.
• Calculate a probability P(d|s) for each dependency tree using the dependency model.
• Sort the constituent-dependency tree pairs in terms of the product of two probabilities and take the one with the highest product as the final output.

4 Experiments

This section reports on our experiments to examine the effectiveness of the reranking approach, in comparison with the reported performance of other state-of-the-art parsing approaches. Two treebanks, namely, the Wall Street Journal (WSJ) portion of the Penn Treebank and the Chinese Treebank (CTB) 5.1, are used in the experiments. They have been widely used as evaluation data in the field.

For dependency parsing, all constituent trees in the two treebanks are converted to dependency trees using the Penn2Malt 2 conversion program. Each treebank is split into three partitions for training, development and testing, respectively, following its conventional split in most previous works in the field, as in Table 4.

The constituent parsing is evaluated using PARSEVAL, with performance reported in F1 score. The accuracy of dependency parsing is measured by unlabeled attachment score (UAS), i.e., the percentage of tokens with correct heads. All models are evaluated on the same training and test sets.

4.1 Effect of Reranking

The performance of the reranking is highly dependent on the size of the k-best list. A larger k certainly has a higher probability of including the best parsing tree. Our experiments show that the parsing performance increases along with k in general. However, the performance gain starts to decrease when k is over 50, because there are more and more common parts in the constituent trees when k gets larger. The performance reaches its peak around k = 100, which is therefore opted as the setting for our experiments.

The performance of this reranking approach is presented in Table 5 and 6, in comparison with other constituent and dependency parsers well known for their high performance on the WSJ and CTB 5.1 datasets. The performance scores marked with * are obtained from our experiments for comparison. On the WSJ test set, the reranking approach achieves the F1 score 91.97% and the UAS 93.71% for constituent and dependency parsing, respectively. This performance is highly comparable to those of the best systems on these two types of parsing, i.e., the combination model of Fossum and Knight [2009] and the semi-supervised structured conditional model of Suzuki et al. [2009]. Our approach also renews the performance records on the CTB 5.1 test set to the F1 score 85.79% and UAS 87.38%. All these confirm its effectiveness.

2 http://w3.msi.vxu.se/˜nivre/research/Penn2Malt.html.

3 The version released in September, 2009.

4 The option "- Chinese" is not used for parsing Chinese, for it does not give the best parsing performance.

These results show that both types of parsing can be further enhanced by reranking. It is simple in nature and significant in improving parsing performance. Its success seems attributable to the followings.

• The features of long-distance dependency relation are useful to facilitate syntactic disambiguation of constituents, and hence can improve the constituent parsing performance.
• The constituent parser first outputs the k-best candidate constituent trees, filtering out a large number of candidate trees that are difficult for a dependency parser to analyze while keeping the most likely ones for the dependency parser to pick the best. This strategy not only helps improve dependency parsing performance but also gets around the computational complexity of joint decoding.

4.2 Effect of POS Tagging

Apart from the size of k-best candidate trees, another factor of critical impact on parsing performance is the accuracy of POS tagging, which affects the rescoring accuracy of constituent parsing. However, the POS tagging in our datasets is not completely correct, hindering our evaluation from fully and objectively revealing the effectiveness of this reranking. To access this, another experiment approach is conducted on the gold standard POS tags, denoted as g-reranking. A similar experiment is also carried out with Berkeley parser to examine the effect of g-reranking on another constituent parser.

The results of these experiments to compare the effect of the two types of POS tags are presented in Table 7. Using gold standard POS tags, the reranking achieves its highest F1 92.06% and 86.50% for constituent parsing and its highest UAS 94.09% and 89.29% for dependency parsing on the WSJ and CTB5.1 test sets, respectively. Interestingly, a greater improvement of performance is achieved by the reranking with Berkeley parser than with ours, suggesting that the greranking can be similarly significant to others. The greatest improvement is achieved on Chinese dependency parsing, by 2.28% and 2.16%, with Berkeley and our constituent parser, respectively. This result strongly indicates that the accuracy of POS tagging does significantly affect the performance of high-performance parsers. Thus, how to further improve the accuracy of POS tagging pops up again to be a key issue. Since surrounding words provide the most important information about the POS of a word in question, the effect of different features from these words certainly deserves more research effort to explore in order to further enhance POS tagging.

5 RelatedWorks

Our constituent parsing shares a number of key features with the discriminative re-scoring methods [Collins, 2000; Charniak and Johnson, 2005; Huang, 2008]. The factorization assumption ensures the scalability and tractability of our parsing model. This also points to a new direction of parsing methodology in terms of the feature design for re-scoring model. Towards this, we employ more intuitive and rational features than those in the previous related works.

Our dependency parsing model is inspired by the wordpair classification model [Jiang and Liu, 2010] and a similar pairwise classification schemata in Japanese dependency parsing [Uchimoto et al., 1999; Kudo and Matsumoto, 2000]. However, our model includes not only the first-order model used in these previous works, but also a second-order model using the same classification methodology. More importantly, our work focuses on applying the dependency parsing model to rerank constituent parsing, providing dependency relations to complement the localized features used in the constituent model.

Similar to other parser combinations approach, ours also involves two different types of model. The best system [Hall, 2007] in the CoNLL2007 shared task combines six transitionbased parsers. Nivre and McDonald [2008] succeed in improving dependency parsing by integrating graph- and transition-based models in a way to have two complementary models to learn from each other. Farkas et al. [2011] extract utility features from automatic dependency parses of a sentence for a discriminative phrase-structure parser on German, and Green and Zabokrtsky [2012] create a new dependency structure through ensemble learning using a hybrid of the outputs of various parsers. Martins et al. [2008] present an integration method based on stacking. Zhang et al. [2009] propose a linear model-based general framework to combine k-best outputs frommultiple parsers. Compared against these previous methods, our approach is conceptually simpler and, allows in particular, a more straightforward way of modularization in model design.

6 Conclusion and FutureWork

In this paper, we have presented a reranking approach to combine constituent and dependency parsing, which reranks the k-best outputs from a constituent parser using a dependency parsing model. The constituent parsing model follows the basic idea of the forest re-scoring approach and uses two types of localized feature to remedy the inherent defects of a PCFGbased model, achieving a competitive performance at the state-of-the-art level. The dependency parsing model combines three independent classifiers, one on individual edges and two on relations between edges, integrating a wide array of lexical and dependency relation features. Our experiments confirm the validity and effectiveness of this reranking approach, in improving both constituent and dependency parsing on both English and Chinese.

The evaluation results from our experiments suggest that constituent and dependency parsing can complement each other through a straightforward strategy of combination. The latter provides long distance dependencies between lexical items to facilitate syntactic disambiguation of constituents. In return, the former eliminates a lot of spurious ambiguities in dependency parsing by shrinking the whole parse forest to a small candidate list.

Our future work includes examining the effectiveness and efficiency of the reranking in contrast to other combination methods, such as incorporating the dependency parsing model as a feature in the forest re-scoring process of the constituent model. We are also interested in exploring the optimal size of k-best list for the best performance achievable by the reranking.

Acknowledgments

The research described in this paper was partially supported by City University of Hong Kong through the SRG grant 7002796 and by the Research Grants Council (UGC) of Hong Kong SAR, China, through the GRF grant CityU 144410. We would like to thank three anonymous reviewers for their helpful comments and thank Billy Wong for his help.