--- title: "Online Learning of Approximate Dependency Parsing Algorithms — McDonald 2006" description: "The maximum spanning tree framework scores a tree as a sum of arc scores, which cannot see neighbouring decisions. 25 references, cited by 268 papers here." authors: ["Ryan McDonald", "Fernando Pereira"] year: 2006 venue: "11th Conference of the European Chapter of the Association for Computational Linguistics" source: "https://aclanthology.org/E06-1011/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/mcdonald-2006-online-learning-approximate-dependency-parsing/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mcdonald-2006-online-learning-approximate-dependency-parsing/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Online Learning of Approximate Dependency Parsing Algorithms # Online Learning of Approximate Dependency Parsing Algorithms **Authors:** [Ryan McDonald](https://md.research.elamur.ai/free/en/authors/ryan-mcdonald/) and [Fernando Pereira](https://md.research.elamur.ai/free/en/authors/fernando-pereira/) · **Year:** 2006 · **Venue:** 11th Conference of the European Chapter of the Association for Computational Linguistics **Link:** [aclanthology.org/E06-1011](https://aclanthology.org/E06-1011/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only [**461** citations](https://openalex.org/works?filter=cites:W194033037) OpenAlex, 2026-10-14 · [**268** citations in our library](https://md.research.elamur.ai/free/en/papers/mcdonald-2006-online-learning-approximate-dependency-parsing/cited-by/) of the 140,884 papers whose bibliographies we read · [11th Conference of the European Chapter of the Association for Computational Linguistics](https://aclanthology.org/volumes/E06-1/) · [licence](https://creativecommons.org/licenses/by-nc-sa/3.0/) - [Publisher's page](https://aclanthology.org/E06-1011/) - [PDF](https://aclanthology.org/E06-1011.pdf) - [OpenAlex](https://openalex.org/W194033037) **Authors (2)** 1. [Ryan McDonald](https://openalex.org/A5022489655) [Semantic Scholar](https://www.semanticscholar.org/author/143957226) · h 48 · 16,067 citations · 113 works 2. [Fernando Pereira](https://openalex.org/A5103620421) [Semantic Scholar](https://www.semanticscholar.org/author/145366908) · h 32 · 21,783 citations · 69 works Citations and author metrics: OpenAlex, 2026-10-14; authors with the same name are not always told apart. ## What it is about The maximum spanning tree framework scores a tree as a sum of arc scores, which cannot see neighbouring decisions. The paper adds second-order factors (sibling and grandparent pairs) to projective parsing, using an extension of Eisner's algorithm that stays cubic, and gives an approximate non-projective second-order parser: it starts from the projective solution and greedily rearranges arcs under the tree constraint. It also allows words with several heads, which Danish needs. Training is online large-margin (MIRA-style), which the authors show is robust to approximate inference. On Czech, per-word accuracy rises from 83.0 with the first-order projective parser to 85.2 with the second-order non-projective one; on Danish the F-measure reaches 84.4 and 85.6 with multiple parents. The authors report the best accuracy known to them for both languages at the time. ## Ideas - I2. gparse: after projective decoding, apply the paper's greedy arc rearrangement to sentences with crossing arcs, and measure LAS on GUM test (test only, NC licence) and on the non-projective EWT sentences. ## For Mova - I1. gparse/src/eisner.rs: add a second-order sibling term to the projective decoder and measure LAS on EWT dev against first-order decoding, recording tokens per second. - I3. en/src/parse.rs: replace the averaged perceptron update with a margin-based update whose step size scales with the number of wrong arcs, as in this paper, and measure LAS on EWT dev, twice, for determinism. The ideas touch the decoder `gparse/src/eisner.rs`, the approximate step that would sit after it, and the update rule in `en/src/parse.rs`. The chapters are `languages/en/21-clause-structure` and `languages/en/25-relative-clauses`, where crossing arcs appear. Measure first I3, a change to the update rule on the existing parser with no new data, and then I1 for the decoder. ## Institutions [🎓**University of Pennsylvania** Philadelphia · United States 143 works · 56,645 citations](https://md.research.elamur.ai/free/en/universities/university-of-pennsylvania/) Topics[Dependency parsing](https://md.research.elamur.ai/free/en/topics/dependency-parsing/) ## Cite Cite as Ryan McDonald and Fernando Pereira. 2006. Online Learning of Approximate Dependency Parsing Algorithms. 11th Conference of the European Chapter of the Association for Computational Linguistics. The paper itself, not this card. BibTeX from the library's record of the work. ```bibtex @inproceedings{mcdonald2006online, title = {{Online Learning of Approximate Dependency Parsing Algorithms}}, author = {Ryan McDonald and Fernando Pereira}, booktitle = {11th Conference of the European Chapter of the Association for Computational Linguistics}, year = {2006}, url = {https://aclanthology.org/E06-1011/} } ``` - [← previous Effective Self-Training for Parsing](https://md.research.elamur.ai/free/en/papers/mcclosky-2006-effective-self-training-parsing/) - [next → The stages of event extraction](https://md.research.elamur.ai/free/en/papers/ahn-2006-stages-event-extraction/) - [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/) ## References 25 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. E. Charniak. 2000. A maximum-entropy-inspired parser. In Proc. NAACL. [our card](https://md.research.elamur.ai/free/en/papers/charniak-2000-maximum-entropy-inspired-parser/) 2. D.M. Chickering, D. Geiger, and D. Heckerman. 1994. Learning bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research. [find](https://scholar.google.com/scholar?q=D%2EM%2E+Chickering%2C+D%2E+Geiger%2C+and+D%2E+Heckerman%2E+1994%2E+Learning+bayesian+networks%3A+The+combination+of+knowledge+and+statistical+data%2E+Technical+Report+MSR%2DTR%2D94%2D09%2C+Microsoft+Research%2E) 3. Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. [find](https://scholar.google.com/scholar?q=Y%2EJ%2E+Chu+and+T%2EH%2E+Liu%2E+1965%2E+On+the+shortest+arborescence+of+a+directed+graph%2E+Science+Sinica%2C+14%3A1396%E2%80%93+1400%2E) 4. M. Collins and B. Roark. 2004. Incremental parsing with the perceptron algorithm. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/collins-2004-incremental-parsing-perceptron-algorithm/) 5. M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann. 1999. A statistical parser for Czech. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/collins-1999-statistical-parser-czech/) 6. M. Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. [our card](https://md.research.elamur.ai/free/en/papers/collins-2002-discriminative-training-methods-hidden-markov/) 7. K. Crammer and Y. Singer. 2003. Ultraconservative online algorithms for multiclass problems. JMLR. [find](https://scholar.google.com/scholar?q=K%2E+Crammer+and+Y%2E+Singer%2E+2003%2E+Ultraconservative+online+algorithms+for+multiclass+problems%2E+JMLR%2E) 8. H. Daum´e and D. Marcu. 2005. Learning as search optimization: Approximate large margin methods for structured prediction. In Proc. ICML. [find](https://scholar.google.com/scholar?q=H%2E+Daum%C2%B4e+and+D%2E+Marcu%2E+2005%2E+Learning+as+search+optimization%3A+Approximate+large+margin+methods+for+structured+prediction%2E+In+Proc%2E+ICML%2E) 9. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. [find](https://scholar.google.com/scholar?q=J%2E+Edmonds%2E+1967%2E+Optimum+branchings%2E+Journal+of+Research+of+the+National+Bureau+of+Standards%2C+71B%3A233%E2%80%93240%2E) 10. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COL-ING. [our card](https://md.research.elamur.ai/free/en/papers/eisner-1996-three-new-probabilistic-models-dependency/) 11. J. Hajič, E. Hajicova, P. Pajas, J. Panevova, P. Sgall, and B. Vidova Hladka. 2001. The Prague Dependency Treebank 1.0 CDROM. Linguistics Data Consortium Cat. No. LDC2001T10. [find](https://scholar.google.com/scholar?q=J%2E+Hajic%CC%8C%2C+E%2E+Hajicova%2C+P%2E+Pajas%2C+J%2E+Panevova%2C+P%2E+Sgall%2C+and+B%2E+Vidova+Hladka%2E+2001%2E+The+Prague+Dependency+Treebank+1%2E0+CDROM%2E+Linguistics+Data+Consortium+Cat%2E+No%2E+LDC2001T10%2E) 12. K. Hall and V. N´ov´ak. 2005. Corrective modeling for non-projective dependency parsing. In Proc. IWPT. [find](https://scholar.google.com/scholar?q=K%2E+Hall+and+V%2E+N%C2%B4ov%C2%B4ak%2E+2005%2E+Corrective+modeling+for+non%2Dprojective+dependency+parsing%2E+In+Proc%2E+IWPT%2E) 13. R. Hudson. 1984. Word Grammar. Blackwell. [find](https://scholar.google.com/scholar?q=R%2E+Hudson%2E+1984%2E+Word+Grammar%2E+Blackwell%2E) 14. M. T. Kromann. 2001. Optimaility parsing and local cost functions in discontinuous grammars. In Proc. FG-MOL. [find](https://scholar.google.com/scholar?q=M%2E+T%2E+Kromann%2E+2001%2E+Optimaility+parsing+and+local+cost+functions+in+discontinuous+grammars%2E+In+Proc%2E+FG%2DMOL%2E) 15. M. T. Kromann. 2003. The danish dependency treebank and the dtag treebank tool. In Proc. TLT. [find](https://scholar.google.com/scholar?q=M%2E+T%2E+Kromann%2E+2003%2E+The+danish+dependency+treebank+and+the+dtag+treebank+tool%2E+In+Proc%2E+TLT%2E) 16. R. McDonald, K. Crammer, and F. Pereira. 2005a. Flexible text segmentation with structured multilabel classifi cation. In Proc. HLT-EMNLP. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2C+K%2E+Crammer%2C+and+F%2E+Pereira%2E+2005a%2E+Flexible+text+segmentation+with+structured+multilabel+classifi+cation%2E+In+Proc%2E+HLT%2DEMNLP%2E) 17. R. McDonald, K. Crammer, and F. Pereira. 2005b. Online large-margin training of dependency parsers. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-online-large-margin-training-dependency/) 18. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005c. Non-projective dependency parsing using spanning tree algorithms. In Proc. HLT-EMNLP. [our card](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-non-projective-dependency-parsing-spanning/) 19. I.A. Meĺčuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. [find](https://scholar.google.com/scholar?q=I%2EA%2E+Mel%CC%81c%CC%8Cuk%2E+1988%2E+Dependency+Syntax%3A+Theory+and+Practice%2E+State+University+of+New+York+Press%2E) 20. R. Moore. 2005. A discriminative framework for bilingual word alignment. In Proc. HLT-EMNLP. [find](https://scholar.google.com/scholar?q=R%2E+Moore%2E+2005%2E+A+discriminative+framework+for+bilingual+word+alignment%2E+In+Proc%2E+HLT%2DEMNLP%2E) 21. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/) 22. A. Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. EMNLP. [our card](https://md.research.elamur.ai/free/en/papers/ratnaparkhi-1996-maximum-entropy-model-part-speech/) 23. B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proc. EMNLP. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+D%2E+Klein%2C+M%2E+Collins%2C+D%2E+Koller%2C+and+C%2E+Manning%2E+2004%2E+Max%2Dmargin+parsing%2E+In+Proc%2E+EMNLP%2E) 24. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. IWPT. [our card](https://md.research.elamur.ai/free/en/papers/yamada-2003-statistical-dependency-analysis-support-vector/) 25. A 2nd-Order Non-projective MST Parsing is NP-hard [find](https://scholar.google.com/scholar?q=A+2nd%2DOrder+Non%2Dprojective+MST+Parsing+is+NP%2Dhard)