[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/huang-2012-structured-perceptron-inexact-search/)

[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/) / Structured Perceptron with Inexact Search

# Structured Perceptron with Inexact Search

**Authors:** [Liang Huang](https://md.mova.elamur.ai/free/en/docs/papers/authors/liang-huang/), Suphan Fayong, Yang Guo · **Year:** 2012 · **Venue:** Proceedings of NAACL-HLT 2012 **Link:** [aclanthology.org/N12-1015](https://aclanthology.org/N12-1015/) (ACL Anthology N12-1015) **License of the paper:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) (ACL Anthology, before 2016) — [creativecommons.org/licenses/by-nc-sa/3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/)

[**83** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/huang-2012-structured-perceptron-inexact-search/) of the 140673 papers whose bibliographies we read[Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies](https://aclanthology.org/volumes/N12-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/N12-1015/)
- [PDF](https://aclanthology.org/N12-1015.pdf)

**Authors (3)**

1. Liang Huang
2. Suphan Fayong
3. Yang Guo

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## 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/}
}
```

- [← previous Learning to Solve Arithmetic Word Problems with Verb Categorization](https://md.mova.elamur.ai/free/en/docs/papers/hosseini-2014-learning-solve-arithmetic-word-problems/)
- [next → The Cambridge Grammar of the English Language](https://md.mova.elamur.ai/free/en/docs/papers/huddleston-2002-cambridge-grammar-english-language/)
- [↑ back to papers](https://md.mova.elamur.ai/free/en/docs/papers/)

## 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](https://scholar.google.com/scholar?q=Collins%2C+Michael%2E+2002%2E+Discriminative+training+methods+for+hidden+markov+models%3A+Theory+and+experiments+with+perceptron+algorithms%2E+In+Proceedings+of+EMNLP%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2002-discriminative-training-methods-hidden-markov/)
2. Collins, Michael and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Collins%2C+Michael+and+Brian+Roark%2E+2004%2E+Incremental+parsing+with+the+perceptron+algorithm%2E+In+Proceedings+of+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2004-incremental-parsing-perceptron-algorithm/)
3. Crammer, Koby and Yoram Singer. 2003. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research (JMLR), 3:951–991. [find](https://scholar.google.com/scholar?q=Crammer%2C+Koby+and+Yoram+Singer%2E+2003%2E+Ultraconservative+online+algorithms+for+multiclass+problems%2E+Journal+of+Machine+Learning+Research+%28JMLR%29%2C+3%3A951%E2%80%93991%2E)
4. Daumé, Hal, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. [find](https://scholar.google.com/scholar?q=Daume%CC%81%2C+Hal%2C+John+Langford%2C+and+Daniel+Marcu%2E+2009%2E+Search%2Dbased+structured+prediction%2E)
5. Daumé, Hal and Daniel Marcu. 2005. Learning as search optimization: Approximate large margin methods for structured prediction. In Proceedings of ICML. [find](https://scholar.google.com/scholar?q=Daume%CC%81%2C+Hal+and+Daniel+Marcu%2E+2005%2E+Learning+as+search+optimization%3A+Approximate+large+margin+methods+for+structured+prediction%2E+In+Proceedings+of+ICML%2E)
6. Finley, Thomas and Thorsten Joachims. 2008. Training structural SVMs when exact inference is intractable. In Proceedings of ICML. [find](https://scholar.google.com/scholar?q=Finley%2C+Thomas+and+Thorsten+Joachims%2E+2008%2E+Training+structural+SVMs+when+exact+inference+is+intractable%2E+In+Proceedings+of+ICML%2E)
7. Huang, Liang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of the ACL: HLT, Columbus, OH, June. [find](https://scholar.google.com/scholar?q=Huang%2C+Liang%2E+2008%2E+Forest+reranking%3A+Discriminative+parsing+with+non%2Dlocal+features%2E+In+Proceedings+of+the+ACL%3A+HLT%2C+Columbus%2C+OH%2C+June%2E)
8. Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL 2010. [find](https://scholar.google.com/scholar?q=Huang%2C+Liang+and+Kenji+Sagae%2E+2010%2E+Dynamic+programming+for+linear%2Dtime+incremental+parsing%2E+In+Proceedings+of+ACL+2010%2E)
9. Joachims, T., T. Finley, and Chun-Nam Yu. 2009. Cutting-plane training of structural svms. Machine Learning, 77(1):27–59. [find](https://scholar.google.com/scholar?q=Joachims%2C+T%2E%2C+T%2E+Finley%2C+and+Chun%2DNam+Yu%2E+2009%2E+Cutting%2Dplane+training+of+structural+svms%2E+Machine+Learning%2C+77%281%29%3A27%E2%80%9359%2E)
10. Kulesza, Alex and Fernando Pereira. 2007. Structured learning with approximate inference. In NIPS. [find](https://scholar.google.com/scholar?q=Kulesza%2C+Alex+and+Fernando+Pereira%2E+2007%2E+Structured+learning+with+approximate+inference%2E+In+NIPS%2E)
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](https://scholar.google.com/scholar?q=Lafferty%2C+John%2C+Andrew+McCallum%2C+and+Fernando+Pereira%2E+2001%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In+Proceedings+of+ICML%2E)
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](https://scholar.google.com/scholar?q=Liang%2C+Percy%2C+Alexandre+Bouchard%2DCo%CC%82te%CC%81%2C+Dan+Klein%2C+and+Ben+Taskar%2E+2006%2E+An+end%2Dto%2Dend+discriminative+approach+to+machine+translation%2E+In+Proceedings+of+COLING%2DACL%2C+Sydney%2C+Australia%2C+July%2E)
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](https://scholar.google.com/scholar?q=Marcus%2C+Mitchell+P%2E%2C+Beatrice+Santorini%2C+and+Mary+Ann+Marcinkiewicz%2E+1993%2E+Building+a+large+annotated+corpus+of+English%3A+the+Penn+Treebank%2E+Computational+Linguistics%2C+19%3A313%E2%80%93330%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/bank-1993-marcus-building-large-annotated-corpus-english/)
14. McDonald, Ryan and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL. [find](https://scholar.google.com/scholar?q=McDonald%2C+Ryan+and+Fernando+Pereira%2E+2006%2E+Online+learning+of+approximate+dependency+parsing+algorithms%2E+In+Proceedings+of+EACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/)
15. Ratliff, Nathan, J. Andrew Bagnell, and Martin Zinkevich. 2007. (online) subgradient methods for structured prediction. In Proceedings of AIStats. [find](https://scholar.google.com/scholar?q=Ratliff%2C+Nathan%2C+J%2E+Andrew+Bagnell%2C+and+Martin+Zinkevich%2E+2007%2E+%28online%29+subgradient+methods+for+structured+prediction%2E+In+Proceedings+of+AIStats%2E)
16. Ratnaparkhi, Adwait. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of EMNLP. [find](https://scholar.google.com/scholar?q=Ratnaparkhi%2C+Adwait%2E+1996%2E+A+maximum+entropy+model+for+part%2Dof%2Dspeech+tagging%2E+In+Proceedings+of+EMNLP%2E)
17. Shen, Libin, Giorgio Satta, and Aravind Joshi. 2007. Guided learning for bidirectional sequence classification. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Shen%2C+Libin%2C+Giorgio+Satta%2C+and+Aravind+Joshi%2E+2007%2E+Guided+learning+for+bidirectional+sequence+classification%2E+In+Proceedings+of+ACL%2E)
18. Taskar, Ben, Carlos Guestrin, and Daphne Koller. 2003. Max-margin markov networks. In Proceedings of NIPS. MIT Press. [find](https://scholar.google.com/scholar?q=Taskar%2C+Ben%2C+Carlos+Guestrin%2C+and+Daphne+Koller%2E+2003%2E+Max%2Dmargin+markov+networks%2E+In+Proceedings+of+NIPS%2E+MIT+Press%2E)
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](https://scholar.google.com/scholar?q=Tsochantaridis%2C+I%2E%2C+T%2E+Joachims%2C+T%2E+Hofmann%2C+and+Y%2E+Altun%2E+2005%2E+Large+margin+methods+for+structured+and+interdependent+output+variables%2E+Journal+of+Machine+Learning+Research%2C+6%3A1453%E2%80%931484%2E)
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](https://scholar.google.com/scholar?q=Xu%2C+Yuehua%2C+Alan+Fern%2C+and+Sungwook+Yoon%2E+2009%2E+Learning+linear+ranking+functions+for+beam+search+with+application+to+planning%2E+Journal+of+Machine+Learning+Research+%28JMLR%29%2C+10%3A1349%E2%80%931388%2E)
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](https://scholar.google.com/scholar?q=Zhang%2C+Yue+and+Stephen+Clark%2E+2008%2E+A+tale+of+two+parsers%3A+investigating+and+combining+graph%2Dbased+and+transition%2Dbased+dependency+parsing+using+beam%2Dsearch%2E+In+Proceedings+of+EMNLP%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/zhang-2008-tale-two-parsers-investigating-combining/)