[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/narrative-2005-charniak-coarse-fine-n-best-parsing/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [English](https://md.mova.elamur.ai/free/en/docs/papers/en/) / Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking

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

**Authors:** [Eugene Charniak](https://md.mova.elamur.ai/free/en/docs/papers/authors/eugene-charniak/), [Mark Johnson](https://md.mova.elamur.ai/free/en/docs/papers/authors/mark-johnson/) · **Year:** 2005 · **Venue:** Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05) **Link:** [aclanthology.org/P05-1022](https://aclanthology.org/P05-1022/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**872** citations](https://openalex.org/works?filter=cites:W2125712079) openalex-snapshot · 2026-10-14[**440** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/narrative-2005-charniak-coarse-fine-n-best-parsing/) of the 140673 papers whose bibliographies we read[Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)](https://aclanthology.org/volumes/P05-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/P05-1022/)
- [PDF](https://aclanthology.org/P05-1022.pdf)
- [DOI 10.3115/1219840.1219862](https://doi.org/10.3115/1219840.1219862)
- [OpenAlex](https://openalex.org/W2125712079)

**Authors (2)**

1. [Eugene Charniak](https://openalex.org/A5005380528) [Semantic Scholar](https://www.semanticscholar.org/author/1749837) · h 56 · 12874 citations · 218 works
2. [Mark Johnson](https://openalex.org/A5034461489) [ORCID](https://orcid.org/0000-0003-4809-8441) · [Semantic Scholar](https://www.semanticscholar.org/author/145177220) · h 60 · 25884 citations · 354 works

Citations and author metrics from openalex-snapshot (2026-10-14); authors with the same name are not always told apart.

## 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 `en` model (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](https://md.mova.elamur.ai/free/en/docs/languages/en/20-syntax-overview/). Measure first: the oracle LAS of the beam-8 output on EWT dev, since it sets the ceiling for any reranker.

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.3115/1219840.1219862](https://doi.org/10.3115/1219840.1219862)

```
@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}
}
```

- [← previous Pragmatic information extraction from subject ellipsis in informal English](https://md.mova.elamur.ai/free/en/docs/papers/nariyama-2006-pragmatic-information-extraction-subject-ellipsis/)
- [next → Non-Projective Dependency Parsing using Spanning Tree Algorithms](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/)
- [↑ back to English](https://md.mova.elamur.ai/free/en/docs/papers/en/)

## References

8 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. 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](https://scholar.google.com/scholar?q=Steve+Benson%2C+Lois+Curfman+McInnes%2C+Jorge+J%2E+Mor%2C+and+Jason+Sarich%2E+2004%2E+Tao+users+manual%2E+Technical+Report+ANL%2FMCS%2DTM%2D242%2DRevision+1%2E6%2C+Argonne+National+Laboratory%2E)
2. Daniel M. Bikel. 2004. Intricacies of collins parsing model. Computational Linguistics, 30(4). [find](https://scholar.google.com/scholar?q=Daniel+M%2E+Bikel%2E+2004%2E+Intricacies+of+collins+parsing+model%2E+Computational+Linguistics%2C+30%284%29%2E)
3. Rens Bod. 2003. An efficient implementation of an new dop model. In Proceedings of the European Chapter of the Association for Computational Linguists. [find](https://scholar.google.com/scholar?q=Rens+Bod%2E+2003%2E+An+efficient+implementation+of+an+new+dop+model%2E+In+Proceedings+of+the+European+Chapter+of+the+Association+for+Computational+Linguists%2E)
4. 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](https://scholar.google.com/scholar?q=Eugene+Charniak%2E+2000%2E+A+maximum%2Dentropy%2Dinspired+parser%2E+In+The+Proceedings+of+the+North+American+Chapter+of+the+Association+for+Computational+Linguistics%2C+pages+132%E2%80%93139%2E)
5. 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](https://scholar.google.com/scholar?q=Michael+Collins+and+Terry+Koo%2E+in+submission%2E+Discriminative+reranking+for+natural+language+parsing%2E+Technical+report%2C+Computer+Science+and+Artificial+Intelligence+Laboratory%2C+Massachusetts+Institute+) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2000-discriminative-reranking-natural-language-parsing/)
6. 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](https://scholar.google.com/scholar?q=Michael+Collins%2E+1997%2E+Three+generative%2C+lexicalised+models+for+statistical+parsing%2E+In+The+Proceedings+of+the+35th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+San+Francisco%2E+Morg)
7. 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](https://scholar.google.com/scholar?q=Michael+Collins%2E+2000%2E+Discriminative+reranking+for+natural+language+parsing%2E+In+Machine+Learning%3A+Proceedings+of+the+Seventeenth+International+Conference+%28ICML+2000%29%2C+pages+175%E2%80%93182%2C+Stanford%2C+Califor) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2000-discriminative-reranking-natural-language-parsing/)
8. Jason Eisner and Giorgio Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proceedings of the 37th Annual [find](https://scholar.google.com/scholar?q=Jason+Eisner+and+Giorgio+Satta%2E+1999%2E+Efficient+parsing+for+bilexical+context%2Dfree+grammars+and+head+automaton+grammars%2E+In+Proceedings+of+the+37th+Annual)