2005 CoarseToFineNBestParsing

From GM-RKB
Jump to navigation Jump to search

Subject Headings: k-Best Parsing Algorithm.

Notes

Cited By

Quotes

Abstract

Discriminative reranking is one method for constructing high-performance statistical parsers (Collins, 2000). A discriminative reranker requires a source of candidate parses for each sentence. This paper describes a simple yetnovel method for constructing sets of 50-best parses based on a coarse-to-fine generative parser (Charniak, 2000). This method generates 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 sentence, obtaining an f-score of 91.0% on sentences of length 100 or less.

Conclusion

This paper has described a dynamic programming n-best parsing algorithm that utilizes a heuristic coarse-to-fine refinement of parses. Because the coarse-to-fine approach prunes the set of possible parse edges beforehand, a simple approach which enumerates the n-best analyses of each parse edge is not only practical but quite efficient. We use the 50-best parses produced by this algorithm as input to a MaxEnt discriminative reranker. The reranker selects the best parse from this set of parses using a wide variety of features. The system we described here has an f-score of 0.91 when trained and tested using the standard PARSEVAL framework.

This result is only slightly higher than the highest reported result for this test-set, Bod’s (.907) (Bod, 2003). More to the point, however, is that the system we describe is reasonably efficient so it can be used for the kind of routine parsing currently being handled by the Charniak or Collins parsers. A 91.0 f-score represents a 13% reduction in f-measure error over the best of these parsers. (This probably underestimates the actual improvement. There are no currently accepted figures for inter-annotater agreement on Penn WSJ, but it is no doubt well short of 100%. If we take 97% as a reasonable estimate of the the upper bound on tree-bank accuracy, we are instead talking about an 18% error reduction.)

Both the 50-best parser, and the reranking parser can be found at ftp://ftp.cs.brown.edu/pub/nlparser/, named parser and reranker respectively.

References

  • Steve Benson, Lois Curfman McInnes, Jorge J. Mor, and Jason Sarich. (2004). Tao users manual. Technical Report ANL/MCS-TM-242-Revision 1.6, Argonne National Laboratory.
  • Daniel M. Bikel. (2004). Intricacies of collins parsing model. Computational Linguistics, 30(4).
  • Rens Bod. (2003). An efficient implementation of an new dop model. In: Proceedings of the European Chapter of the Association for Computational Linguists.
  • Eugene Charniak. (2000). A maximum-entropy-inspired parser. In The Proceedings of the North American Chapter of the Association for Computational Linguistics, pages 132–139.
  • Michael Collins and Terry Koo. in submission. Discriminative reranking for natural language parsing. Technical report, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.
  • Michael Collins. (1997). Three generative, lexicalised models for statistical parsing. In The Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics, San Francisco. Morgan Kaufmann.
  • Michael Collins. (2000). Discriminative reranking for natural language parsing. In Machine Learning: Proceedings of the Seventeenth International Conference (ICML 2000), pages 175–182, Stanford, California.
  • Jason Eisner and Giorgio Satta. (1999). Efficient parsing for bilexical context-free grammars and head automaton grammars. In: Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pages 457–464.
  • Joseph Emonds. 1976. A Transformational Approach to English Syntax: Root, Structure-Preserving and Local Transformations. Academic Press, New York, NY.
  • Joshua Goodman. (1997). Global thresholding and multiple-pass parsing. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP 1997).
  • Jane Grimshaw. (1997). Projection, heads, and optimality. Linguistic Inquiry, 28(3):373–422.
  • Liang Huang and David Chang. (2005). Better k-best parsing. Technical Report MS-CIS-05-08, Department of Computer Science, University of Pennsylvania.
  • Victor M. Jimenez and Andres Marzal. (2000). Computation of the n best parse trees for weighted and stochastic context-free grammars. In: Proceedings of the Joint IAPR International Workshops on Advances in Pattern Recognition. Springer LNCS 1876.
  • Mark Johnson, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. (1999). Estimators for stochastic “unification-based” grammars. In The Proceedings of the 37th Annual Conference of the Association for Computational Linguistics, pages 535–541, San Francisco. Morgan Kaufmann.
  • Dan Klein and Christopher D. Manning. (2003). Accurate unlexicalized parsing. In: Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics.
  • Robert Malouf. (2002). A comparison of algorithms for maximum entropy parameter estimation. In: Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002), pages 49–55.
  • Stefan Riezler, Tracy H. King, Ronald M. Kaplan, Richard Crouch, John T. III Maxwell, and Mark Johnson. (2002). Parsing the wall street journal using a lexical-functional grammar and discriminative estimation techniques. In: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 271–278. Morgan Kaufmann.
  • Brian Roark. (2001). Probabilistic top-down parsing and language modeling. Computational Linguistics, 27(2):249–276.
  • R. Schwartz and Y.L. Chow. (1990). The n-best algorithm: An efficient and exact procedure for finding the n most likely sentence hypotheses. In: Proceedings of the IEEE International Conference on Acoustic, Speech, and Signal, Processing, pages 81–84.

,

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2005 CoarseToFineNBestParsingEugene Charniak
Mark Johnson		Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Rerankinghttp://aclweb.org/anthology-new/P/P05/P05-1022.pdf10.3115/1219840.1219862
Retrieved from "http://www.gabormelli.com/RKB/index.php?title=2005_CoarseToFineNBestParsing&oldid=618574"