Structured Perceptron with Inexact Search

Summary

The convergence guarantee of the structured perceptron assumes exact search for the best structure, yet practical systems such as incremental parsers and translation decoders use beam search. The authors show that convergence still holds with inexact search as long as every weight update fixes a "violation", i.e. a case where the model scores a wrong partial structure at least as high as the correct one. They formalise this as the violation-fixing perceptron and prove the same mistake bound as for the classic algorithm. The framework explains why standard full-sequence updates with beam search can fail, and shows that Collins and Roark's early update and LaSO are special cases, giving early update its first theoretical justification. They also propose new update strategies; the best, max-violation, updates at the prefix where the gap between the best wrong hypothesis and the gold prefix is largest, and on POS tagging and incremental parsing it matches or beats early update while training about three times faster.

How Mova uses it

• math/src/steps.rs (Model::run) — the arithmetic word-problem solver builds expression trees with a beam-search perceptron trained with early update by default.
• Max-violation is implemented as an option (MATH_MAXVIOL=1): the gold action prefix is scored alongside the beam, and the update happens at the step where "best beam state minus gold prefix" is largest, instead of the first step where gold falls out of the beam.

Effectiveness in Mova

Measured on SVAMP (architecture notes, table of ideas from papers): max-violation lowered accuracy from 57,3% to 56,0%, so it stays off by default and early update remains the training regime.

👨‍🔬💥

More ideas (a second reading)

• I1. en/src/parse.rs training loop: the parser uses beam 8 with early update. Add max-violation as an update option, and measure LAS on EWT test and the number of iterations to the held-out peak. Two identical runs before any claim; the choice is made on the two-fold check.
• I2. Invalid-update counter: count the updates where the gold prefix has already fallen out of the beam, per epoch, in the en parse-eval training log. The paper finds that invalid updates predict bad learning, and in parsing they stay near 50% at the standard update.
• I3. en/src/ptag.rs: test beam sizes 1, 2, 4 and 8 with early and max-violation updates. The paper's tagging result suggests that a small beam with the max-violation update matches a larger beam with early update, which would cut tagger training time.

Cite

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

@inproceedings{huang2012structured,
  title = {{Structured Perceptron with Inexact Search}},
  author = {Huang, Liang and Fayong, Suphan and Guo, Yang},
  booktitle = {Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2012},
  url = {https://aclanthology.org/N12-1015/}
}

References

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

1. Collins, Michael. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP. find our card
2. Collins, Michael and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL. find our card
3. Crammer, Koby and Yoram Singer. 2003. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research (JMLR), 3:951–991. find
4. Daumé, Hal, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. find
5. Daumé, Hal and Daniel Marcu. 2005. Learning as search optimization: Approximate large margin methods for structured prediction. In Proceedings of ICML. find
6. Finley, Thomas and Thorsten Joachims. 2008. Training structural SVMs when exact inference is intractable. In Proceedings of ICML. find
7. Huang, Liang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of the ACL: HLT, Columbus, OH, June. find
8. Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL 2010. find
9. Joachims, T., T. Finley, and Chun-Nam Yu. 2009. Cutting-plane training of structural svms. Machine Learning, 77(1):27–59. find
10. Kulesza, Alex and Fernando Pereira. 2007. Structured learning with approximate inference. In NIPS. find
11. Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML. find
12. Liang, Percy, Alexandre Bouchard-Côté, Dan Klein, and Ben Taskar. 2006. An end-to-end discriminative approach to machine translation. In Proceedings of COLING-ACL, Sydney, Australia, July. find
13. Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: the Penn Treebank. Computational Linguistics, 19:313–330. find our card
14. McDonald, Ryan and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL. find our card
15. Ratliff, Nathan, J. Andrew Bagnell, and Martin Zinkevich. 2007. (online) subgradient methods for structured prediction. In Proceedings of AIStats. find
16. Ratnaparkhi, Adwait. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of EMNLP. find
17. Shen, Libin, Giorgio Satta, and Aravind Joshi. 2007. Guided learning for bidirectional sequence classification. In Proceedings of ACL. find
18. Taskar, Ben, Carlos Guestrin, and Daphne Koller. 2003. Max-margin markov networks. In Proceedings of NIPS. MIT Press. find
19. Tsochantaridis, I., T. Joachims, T. Hofmann, and Y. Altun. 2005. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6:1453–1484. find
20. Xu, Yuehua, Alan Fern, and Sungwook Yoon. 2009. Learning linear ranking functions for beam search with application to planning. Journal of Machine Learning Research (JMLR), 10:1349–1388. find
21. Zhang, Yue and Stephen Clark. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search. In Proceedings of EMNLP. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/huang-2012-structured-perceptron-inexact-search/