Discriminative Reranking for Natural Language Parsing

Summary

The work splits parsing into two stages. A base probabilistic parser proposes a short list of candidate trees for each sentence together with their probabilities, and a second, discriminatively trained model reorders the list. Because the second model only scores complete candidates, it can use arbitrary, overlapping features of whole trees without changing the generative model or its decision sequence. Collins trains the reranker with a boosting-style method that minimises an exponential ranking loss and effectively selects useful features one at a time. On the Wall Street Journal treebank, reranking clearly improves over the base parser (the 2005 journal version reports F-measure rising from 88.2% to 89.75%). The approach generalises to any NLP task that can be cast as choosing among candidates.

How Mova uses it

• math/src/steps.rs ("top-K reranking") — the arithmetic word-problem solver's beam-search perceptron produces the top-K distinct final expression trees (Model::topk, candidates with tree, score, value and actions), and a separate judge reranks them.
• math/src/bin/mathsolve.rs (--rerank K) — the judge is trained on candidates produced by models that did not see the corresponding fold (4 folds), so it does not learn to over-trust the base model's training-set answers.
• The judge later became the place where extra evidence is plugged in as features (world-model answer, ensemble votes, shapes), as in the original two-stage design.

Effectiveness in Mova

Measured on SVAMP (architecture notes, table of ideas from papers): reranking with a judge over top-K raised accuracy from 47,7% to 54,3% — one of the confirmed gains.

👨‍🔬💥

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/0891201053630273

@article{collins2005discriminative,
  title = {{Discriminative Reranking for Natural Language Parsing}},
  author = {Collins, Michael and Koo, Terry},
  journal = {Computational Linguistics},
  year = {2005},
  doi = {10.1162/0891201053630273},
  url = {https://doi.org/10.1162/0891201053630273}
}

References

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

1. Abney, Steven. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23(4):597–618. j¼2 ! find
2. P n i M i , j ð ā aÞdg k ðx i , j Þ j¼2 e P n i M ð ā aÞ 1 þ j¼2 e i , j þ P n i M i , j ð ā aÞ 1 þ j¼2 e n i X n i X q i , j e dg k ðx i , j Þ A q i , j þ ðB:5Þ j¼2 j¼2 n i X X q i , j e dg k ðx i , j Þ q i , j þ ðB:6Þ i j¼2 W þ 1 log k  2 W k Altun, Yasemin, Thomas Hofmann, and Mark John… find
3. Altun, Yasemin, Mark Johnson, and Thomas Hofmann. 2003. Loss functions and optimization methods for discriminative learning of label sequences. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP 2003), Sapporo, Japan. find
4. Berger, Adam L., Stephen A. Della Pietra, and Vincent J. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71. find
5. Black, Ezra, Frederick Jelinek, John Lafferty, David Magerman, Robert Mercer, and Salim Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. In Proceedings of the Fifth DARPA Speech and Natural Language Workshop, Harriman, NY. find
6. Charniak, Eugene. 1997. Statistical parsing with a context-free grammar and word statistics. Proceedings of the 14th National Conference on Artificial Intelligence, Menlo Park, CA. AAAI Press/MIT Press. find
7. Charniak, Eugene. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL-2000, Seattle. find
8. Chen, Stanley F., and Ronald Rosenfeld. 1999. A gaussian prior for smoothing maximum entropy models. Technical Report CMU-CS-99-108, Computer Science Department, Carnegie Mellon University. find
9. Collins, Michael. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and Eighth Conference of the European Chapter of the Association for Computational Linguistics, pages 16–23, Madrid. find
10. Collins, Michael. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia. find
11. Collins, Michael. 2000. Discriminative reranking for natural language parsing. In Proceedings of the 17th International Conference on Machine Learning (ICML 2000), Stanford, CA. Morgan Kaufmann, San Francisco. find
12. Collins, Michael. 2002a. Ranking algorithms for named-entity extraction: Boosting and the voted perceptron. In ACL 2002: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, Philadelphia. find
13. Collins, Michael. 2002b. Discriminative training methods for hidden Markov models: Theory and experiments with the perceptron algorithm. In Proceedings of EMNLP 2002, Philadelphia. find
14. Collins, Michael. 2004. Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. In Harry Bunt, John Carroll, and Giorgio Satta, editors, New Developments in Parsing Technology. Kluwer. find
15. Collins, Michael and Nigel Duffy. 2001. Convolution kernels for natural language. find
16. In Advances in Neural Information Processing Systems (NIPS 14), Vancouver. find
17. Collins, Michael, and Nigel Duffy. 2002. New ranking algorithms for parsing and tagging: Kernels over discrete structures, and the voted perceptron. In ACL 2002: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, Philadelphia. find
18. Collins, Michael, Robert E. Schapire, and Yoram Singer. 2002. Logistic regression, AdaBoost and Bregman distances. Machine Learning, 48(1/2/3):253–285. find
19. Della Pietra, Stephen, Vincent Della Pietra, and John Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393. find
20. Duffy, Nigel and David Helmbold. 1999. Potential boosters? In Advances in Neural Information Processing Systems (NIPS 12), Denver. find
21. Freund, Yoav, Raj Iyer, Robert E. Schapire, and Yoram Singer. 1998. An efficient boosting algorithm for combining preferences. In Machine Learning: Proceedings of the 15th International Conference, Madison, WI. find
22. Freund, Yoav and Robert E. Schapire. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139. find
23. Freund, Yoav and Robert E. Schapire. 1999. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296. find
24. Friedman, Jerome H., Trevor Hastie, and Robert Tibshirani. 2000. Additive logistic regression: A statistical view of boosting. Annals of Statistics, 38(2):337–374. find
25. Henderson, James. 2003. Inducing history representations for broad coverage statistical parsing. In Proceedings of the Joint Meeting of the North American Chapter of the Association for Computational Linguistics and the Human Language Technology Conference (HLT-NAACL 2003), pages 103–110, Edmonton,… find
26. Hoffgen, Klauss U., Kevin S. van Horn, and Hans U. Simon. 1995. Robust trainability of single neurons. Journal of Computer and System Sciences, 50:114–125. find
27. Johnson, Mark, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic ‘‘unification-based’’ grammars. In Proceedings of ACL 1999, College Park, MD. find
28. Joshi, Aravind K., Leon S. Levy, and Masako Takahashi. 1975. Tree adjunct grammars. Journal of Computer and System Science 10, no. 1:136–163. find
29. Koller, Daphne, and Mehran Sahami. 1996. Toward optimal feature selection. In Proceedings of the 13th International Conference on Machine Learning (ICML), pages 284–292, Bari, Italy, July. find
30. Lafferty, John. 1999. Additive models, boosting, and inference for generalized divergences. In Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT’99), Santa Cruz, CA. find
31. Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML 2001, Williamstown, MA. find
32. Lebanon, Guy and John Lafferty. 2001. Boosting and maximum likelihood for exponential models. In Advances in Neural Information Processing Systems (NIPS 14), Vancouver. find
33. Malouf, Robert. 2002. A comparison of algorithms for maximum entropy parameter estimation. In Proceedings of the Sixth Conference on Natural Language Learning (CoNNL-2002), Taipei, Taiwan. find
34. Marcus, Mitchell, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
35. Mason, Llew, Peter L. Bartlett, and Jonathan Baxter. 1999. Direct optimization of margins improves generalization in combined classifiers. In Advances in Neural Information Processing Systems (NIPS 12), Denver. find
36. McCallum, Andrew. 2003. Efficiently inducing features of conditional random fields. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI 2003), Acapulco. find
37. Och, Franz Josef, and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In ACL 2002: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 295–302, Philadelphia. find
38. Papineni, Kishore A., Salim Roukos, and R. T. Ward. 1997. Feature-based language understanding. In Proceedings of EuroSpeech’97, vol. 3, pages 1435–1438, Rhodes, Greece. find
39. Papineni, Kishore A., Salim Roukos, and R. T. Ward. 1998. Maximum likelihood and discriminative training of direct translation models. In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 1, pages 189–192, Seattle. find
40. Pearl, Judea. 1988. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, CA. find
41. Ratnaparkhi, Adwait. 1997. A linear observed time statistical parser based on maximum entropy models. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, Brown University, Providence, RI. find
42. Ratnaparkhi, Adwait. 1998. Maximum Entropy Models for Natural Language Ambiguity Resolution. Ph.D. thesis, University of Pennsylvania, Philadelphia. find
43. Ratnaparkhi, Adwait, Salim Roukos, and R. T. Ward. 1994. A maximum entropy model for parsing. In Proceedings of the International Conference on Spoken Language Processing, pages 803–806, Yokohama, Japan. find
44. Riezler, Stefan, Tracy H. King, Ronald M. Kaplan, Richard Crouch, John T. Maxwell III, and Mark Johnson. 2002. Parsing the Wall Street Journal using a lexical-functional grammar and discriminative estimation techniques. In ACL 2002: Proceedings of the 40th Annual Meeting of the Association for Compu… find
45. Riezler, Stefan and Alexander Vasserman. 2004. Incremental feature selection and l 1 regularization for relaxed maximum-entropy modeling. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP’04), Barcelona, Spain. find
46. Rosenfeld, Ronald. 1997. A whole sentence maximum entropy language model. In Proceedings of the IEEE Workshop on Speech Recognition and Understanding, Santa Barbara, CA, December. find
47. Schapire, Robert E., Yoav Freund, Peter Bartlett, and W. S. Lee. 1998. Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics, 26(5):1651–1686. find
48. Schapire, Robert E. and Yoram Singer. 1999. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336. find
49. Schapire, Robert E. and Yoram Singer. 2000. BoosTexter: A boosting-based system for text categorization. Machine Learning, 39(2/3):135–168. find
50. Sha, Fei and Fernando Pereira. 2003. Shallow parsing with conditional random fields. In Proceedings of HLT-NAACL 2003, Edmonton, Alberta, Canada. find
51. Shen, Libin, Anoop Sarkar, and Aravind K. Joshi. 2003. Using LTAG based features in parse reranking. In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing (EMNLP 2003), Sapporo, Japan. find
52. Valiant, Leslie G. 1984. A theory of the learnable. Communications of the ACM, 27(11):1134–1142. find
53. Walker, Marilyn, Owen Rambow, and Monica Rogati. 2001. SPoT: A trainable sentence planner. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL 2001), Pittsburgh. find
54. Zhou, Yaqian, Fuliang Weng, Lide Wu, and Hauke Schmidt. 2003. A fast algorithm for feature selection in conditional maximum entropy modeling. In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing (EMNLP 2003), Sapporo, Japan. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/collins-2000-discriminative-reranking-natural-language-parsing/