Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers

What it is about

Non-projective graph parsing with third-order features (grand- and tri-siblings, head bigrams) is NP-hard, so the paper uses AD3, an accelerated dual decomposition algorithm, and extends it with specialised head automata that solve the large subproblems exactly. The result is a parser whose speed is competitive with projective parsers. On the CoNLL-2006 datasets and the non-projective English set, the third-order model gives the best reported UAS for English, Czech, German and Dutch. On English it reaches 93.22 UAS at 785 tokens per second, against 91.21 UAS at 3,127 tokens per second for the first-order model (Table 3). The paper's contribution is the algorithm, and the tables show the cost of each order in tokens per second.

Ideas

• I1. gparse/src/eisner.rs: add a second-order sibling term to the Eisner decoder (projective) and measure LAS on EWT dev against first-order decoding, with tokens per second recorded in the same run.
• I2. For non-projective decoding, compare the approximate hill-climbing step of the McDonald and Pereira card with exact projective decoding on GUM test (test only, NC licence), and count the non-projective gold arcs lost.
• I3. Add a tokens-per-second column to every en parse-eval and gparse run, as this paper does, so that each new feature has a stated cost before anyone argues for it.

For Mova

The ideas touch the decoder gparse/src/eisner.rs and the evaluation output of en parse-eval. The chapters are languages/en/21-clause-structure and languages/en/25-relative-clauses, where non-projective structures occur. Measure first I3, since it costs nothing and makes I1 and any later speed claim comparable.

Cite

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

@inproceedings{martins2013turning,
  title = {{Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers}},
  author = {Martins, André and Almeida, Miguel and Smith, Noah A.},
  booktitle = {Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2013},
  url = {https://aclanthology.org/P13-2109/}
}

References

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

1. S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In International Conference on Natural Language Learning. find our card
2. X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In International Conference on Natural Language Learning. find
3. Y. J. Chu and T. H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. find
4. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585. find
5. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. find
6. J. M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. of International Conference on Computational Linguistics, pages 340–345. find our card
7. H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan. 1986. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2):109–122. find
8. L. Huang and K. Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proc. of Annual Meeting of the Association for Computational Linguistics, pages 1077–1086. find
9. N. Komodakis, N. Paragios, and G. Tziritas. 2007. MRF optimization via dual decomposition: Message-passing revisited. In Proc. of International Conference on Computer Vision. find
10. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of Annual Meeting of the Association for Computational Linguistics, pages 1– 11. find
11. T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In Proc. of Empirical Methods for Natural Language Processing. find
12. S. Kübler, R. McDonald, and J. Nivre. 2009. Dependency parsing. Morgan & Claypool Publishers. find
13. A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. of Annual Meeting of the Association for Computational Linguistics. find
14. A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T. Figueiredo, and P. M. Q. Aguiar. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proc. of Empirical Methods for Natural Language Processing. find
15. A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and M. A. T. Figueiredo. 2011. Dual decomposition with many overlapping components. In Proc. of Empirical Methods for Natural Language Processing. find
16. A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar, N. A. Smith, and E. P. Xing. 2012. Alternating directions dual decomposition. Arxiv preprint arXiv:1212.6550. — [arXiv:1212.6550](https://arxiv.org/abs/1212.6550) find
17. R. T. McDonald and F. C. N. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of Annual Meeting of the European Chapter of the Association for Computational Linguistics. find our card
18. R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proc. of International Conference on Parsing Technologies. find
19. R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of Empirical Methods for Natural Language Processing. find our card
20. R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proc. of International Conference on Natural Language Learning. find
21. J. Nivre, J. Hall, J. Nilsson, G. Eryiǧit, and S. Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Procs. of International Conference on Natural Language Learning. find
22. J. Nocedal and S. J. Wright. 1999. Numerical optimization. Springer-Verlag. find
23. Alexander M Rush and Slav Petrov. 2012. Vine pruning for efficient multi-pass dependency parsing. In Proc. of Conference of the North American Chapter of the Association for Computational Linguistics. find
24. A. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010. On dual decomposition and linear programming relaxations for natural language processing. In Proc. of Empirical Methods for Natural Language Processing. find
25. D. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. of Empirical Methods for Natural Language Processing. find
26. M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez, and J. Nivre. 2008. The CoNLL-2008 shared task on joint parsing of syntactic and semantic dependencies. Proc. of International Conference on Natural Language Learning. find our card
27. R.E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36. find
28. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of International Conference on Parsing Technologies. find our card
29. H. Zhang and R. McDonald. 2012. Generalized higher-order dependency parsing with cube pruning. In Proc. of Empirical Methods in Natural Language Processing. find
30. Y. Zhang and J. Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proc. of the Annual Meeting of the Association for Computational Linguistics. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2013-martins-turning-turbo-fast-third-order/