Incremental Parsing with the Perceptron Algorithm

Summary

The paper asks whether an unnormalised discriminative model can work well together with heuristic search in parsing. Instead of reranking candidates from another parser, the authors train the parameters of an incremental left-to-right parser directly with a perceptron variant, using the same beam search during training and decoding. The key device is early update: as soon as the correct partial analysis falls out of the beam, decoding stops and the weights are updated against the best item at that point, so the model is not penalised for errors that search alone would cause later. Features are borrowed from Roark's generative incremental parser, which makes the two approaches directly comparable, and some training refinements and punctuation features are added. On the Penn Treebank the perceptron alone matches the generative model, and a hybrid that adds the generative model's log-probability as a feature improves F-measure further. The approach offers a simple way to add arbitrary features to a parser without exhaustive candidate enumeration or expensive dynamic programming.

How Mova uses it

• math/src/steps.rs: word problems are solved as a transition system — the model walks through the numbers in text order and at each step chooses SHIFT (take the number), SKIP (ignore it) or REDUCE (combine the top two with an operation and direction), mirroring Mova's arc-standard dependency parser; an exact arithmetic core computes each subproblem.
• Training is a structured perceptron with a beam and early update exactly in the sense of this paper: the gold action sequence comes from the gold expression tree, and when the gold prefix leaves the beam the update is made at that step against the best state there. Parameters are averaged.
• Features come from the UD parse of the problem (units, verbs, subjects, cue words, question words) rather than lexical bags.

Effectiveness in Mova

Early update is the default training scheme of the solver and is not ablated on its own. The alternative max-violation update (Huang, Fayong, Guo 2012; MATH_MAXVIOL=1) was measured against it: SVAMP 57.3% → 56.0%, i.e. worse, so early update was kept.

👨‍🔬💥

More ideas (a second reading)

• I1. en/src/parse.rs: add a count-based score as one extra feature in the perceptron. Use the log relative frequency of the arc label given the head and dependent tags, estimated on the training part only. Weight it on a held-out part of the training data, never on test. Measure LAS on EWT test with and without it, with en folds.
• I2. Ablation of the punctuation features: the paper shows that punctuation features close the gap to the generative model. Add punctuation-context features (the token before and after the candidate arc, when it is punctuation) to en parse-eval and report LAS on EWT test with and without them.
• I3. en/src/ptag.rs: the tagger is already an averaged perceptron with beam 8. Test whether a count-based tag prior (the en/src/tag.rs TnT prior) added as one feature changes tag accuracy on EWT test, as the hybrid does for parsing.

Cite

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

@inproceedings{collins2004incremental,
  title = {{Incremental Parsing with the Perceptron Algorithm}},
  author = {Collins, Michael and Roark, Brian},
  booktitle = {Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)},
  year = {2004},
  doi = {10.3115/1218955.1218970},
  url = {https://doi.org/10.3115/1218955.1218970}
}

References

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

1. Steven Abney. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23(4):597–617. find
2. Michael Collins and Nigel Duffy. 2002. New ranking algorithms for parsing and tagging: Kernels over discrete structures and the voted perceptron. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 263–270. find
3. Michael Collins. 2000. Discriminative reranking for natural language parsing. In The Proceedings of the 17th International Conference on Machine Learning. find our card
4. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1–8. find our card
5. Michael Collins. 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
6. Fabrizio Costa, Vincenzo Lombardo, Paolo Frasconi, and Giovanni Soda. 2001. Wide coverage incremental parsing by learning attachment preferences. In Conference of the Italian Association for Artificial Intelligence (AIIA), pages 297–307. find
7. Stephen Della Pietra, Vincent Della Pietra, and John Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:380–393. find
8. Yoav Freund and Robert Schapire. 1999. Large margin classification using the perceptron algorithm. Machine Learning, 3(37):277–296. find
9. Yoav Freund, Raj Iyer, Robert Schapire, and Yoram Singer. 1998. An efficient boosting algorithm for combining preferences. In Proc. of the 15th Intl. Conference on Machine Learning. find
10. Stuart Geman and Mark Johnson. 2002. Dynamic programming for parsing and estimation of stochastic unification-based grammars. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 279–286. find
11. Mark Johnson and Brian Roark. 2000. Compact non-left-recursive grammars using the selective left-corner transform and factoring. In Proceedings of the 18th International Conference on Computational Linguistics (COLING), pages 355–361. find
12. Mark Johnson, Stuart Geman, Steven Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic “unification-based” grammars. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pages 535–541. find
13. Mark Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):617–636. find
14. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18th International Conference on Machine Learning, pages 282–289. find
15. Adwait Ratnaparkhi, Salim Roukos, and R. Todd Ward. 1994. A maximum entropy model for parsing. In Proceedings of the International Conference on Spoken Language Processing (ICSLP), pages 803–806. find
16. Adwait Ratnaparkhi. 1999. Learning to parse natural language with maximum entropy models. Machine Learning, 34:151–175. find
17. Stefan Riezler, Tracy 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 Proceedings of the 40th Annual Meeting of the Association for Computational Lingu… find
18. Brian Roark, Murat Saraclar, and Michael Collins. 2004. Corrective language modeling for large vocabulary ASR with the perceptron algorithm. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pages 749–752. find
19. Brian Roark. 2001a. Probabilistic top-down parsing and language modeling. Computational Linguistics, 27(2):249–276. find
20. Brian Roark. 2001b. Robust Probabilistic Predictive Syntactic Processing. Ph.D. thesis, Brown University. http://arXiv.org/abs/cs/0105019. — [arXiv:cs/0105019](https://arxiv.org/abs/cs/0105019) ↗
21. Brian Roark. 2004. Robust garden path parsing. Natural Language Engineering, 10(1):1–24. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/collins-2004-incremental-parsing-perceptron-algorithm/