Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking
What it is about
A discriminative reranker needs a good list of candidate parses for each sentence. The authors produce 50-best lists with a coarse-to-fine generative parser: a coarse pass prunes the chart, and a finer pass scores the surviving parses, which gives lists of much higher quality than the usual n-best output. A MaxEnt reranker then chooses one parse from the 50-best list with features of whole trees, which dynamic programming could not handle. The oracle F-score of the 50-best list is 96.8, while the reranker reaches 91.0 against 89.7 for the base parser on the Penn Treebank, a 13% reduction in F-score error. The gain comes from features that are arbitrary functions of the whole tree.
Ideas
- I1. Reranker over the beam in
en/src/parse.rs: keep the final beam of 8 transition sequences per sentence, add a second averaged perceptron that scores whole-tree features (for example, the number of conj children and the length of the longest dependency), and measure EWT dev LAS against the 1-best beam output. - I2. Oracle gap from
en beam-curve: report the oracle LAS of the beam against the 1-best LAS at beam sizes 1, 2, 4, 8 and 16 on EWT dev; a large gap, as the paper shows for 50-best, says a reranker has room to help. - I3. Coarse-to-fine decoding: use the greedy
enmodel (LAS 79.0) as the coarse pass that prunes candidate arcs, then run the beam-8 model on the surviving arcs, and measure LAS and running time on EWT dev, checking that results are identical across two runs.
For Mova
The beam and the candidate list are in en/src/parse.rs, the curve tool is en beam-curve, and the GPU counterpart would be the Eisner decoder in gparse/src/eisner.rs. The chapter that the ideas touch is 20. Syntax: the Universal Dependencies frame. Measure first: the oracle LAS of the beam-8 output on EWT dev, since it sets the ceiling for any reranker.
Cite
@inproceedings{charniak2005coarse,
title = {{Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking}},
author = {Charniak, Eugene and Johnson, Mark},
booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
year = {2005},
doi = {10.3115/1219840.1219862},
url = {https://doi.org/10.3115/1219840.1219862}
}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. find
- Daniel M. Bikel. 2004. Intricacies of collins parsing model. Computational Linguistics, 30(4). find
- Rens Bod. 2003. An efficient implementation of an new dop model. In Proceedings of the European Chapter of the Association for Computational Linguists. find
- 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. find
- 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. find our card
- 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. find
- 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. find our card
- Jason Eisner and Giorgio Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proceedings of the 37th Annual find
This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-charniak-coarse-fine-n-best-parsing/