Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking

Proceedings of the 43rd Annual Meeting of the ACL, pages 173–180, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Coarse-to-fine n-best parsing and MaxEnt discriminative reranking Eugene Charniak and Mark Johnson Brown Laboratory for Linguistic Information Processing (BLLIP) Brown University Providence, RI 02912 {mj|ec}@cs.brown.edu Abstract Discriminative reranking is one method for constructing high-performance statis- tical parsers (Collins, 2000). A discrim- inative reranker requires a source of can- didate parses for each sentence. This pa- per describes a simple yet novel method for constructing sets of 50-best parses based on a coarse-to-fine generative parser (Charniak, 2000). This method gener- ates 50-best lists that are of substantially higher quality than previously obtainable. We used these parses as the input to a MaxEnt reranker (Johnson et al., 1999; Riezler et al., 2002) that selects the best parse from the set of parses for each sen- tence, obtaining an f-score of 91.0% on sentences of length 100 or less. 1 Introduction We describe a reranking parser which uses a reg- ularized MaxEnt reranker to select the best parse from the 50-best parses returned by a generative parsing model. The 50-best parser is a probabilistic parser that on its own produces high quality parses; the maximum probability parse trees (according to the parser’s model) have an f-score of 0.897 on section 23 of the Penn Treebank (Charniak, 2000), which is still state-of-the-art. However, the 50 best (i.e., the 50 highest probability) parses of a sentence often contain considerably better parses (in terms of f-score); this paper describes a 50-best parsing al- gorithm with an oracle f-score of 96.8 on the same data. The reranker attempts to select the best parse for a sentence from the 50-best list of possible parses for the sentence. Because the reranker only has to consider a relatively small number of parses per sentences, it is not necessary to use dynamic pro- gramming, which permits the features to be essen- tially arbitrary functions of the parse trees. While our reranker does not achieve anything like the ora- cle f-score, the parses it selects do have an f-score of 91.0, which is considerably better than the maxi- mum probability parses of the n-best parser. In more detail, for each string s the n-best parsing algorithm described in section 2 returns the n high- est probability parses Y(s) = {y1(s), . . . , yn(s)} together with the probability p(y) of each parse y ac- cording to the parser’s probability model. The num- ber n of parses was set to 50 for the experiments described here, but some simple sentences actually received fewer than 50 parses (so n is actually a function of s). Each yield or terminal string in the training, development and test data sets is mapped to such an n-best list of parse/probability pairs; the cross-validation scheme described in Collins (2000) was used to avoid training the n-best parser on the sentence it was being used to parse. A feature extractor, described in section 3, is a vector of …

Content truncated to 500 words