Elamur Research
☰
home / papers / 2013 / Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers

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

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.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/P13-2109.pdf

Summary

Graph-based non-projective dependency parsing becomes NP-hard once scores go beyond single arcs. Earlier approximate ("turbo") parsers for this setting did not use third-order context and were much slower than projective parsers based on dynamic programming. The authors extend AD3, an alternating-directions dual decomposition method, to third-order models. They split the parsing problem into several components: an arc-factored tree solved with Chu-Liu-Edmonds, grand-sibling and tri-sibling head automata, a Viterbi-decoded head-bigram sequence model, and arbitrary-sibling factors. The quadratic subproblems that AD3 requires are solved by an active set method that only calls each component's ordinary MAP oracle, and it is warm-started from the previous iteration. Candidate heads are pruned beforehand with a first-order model. On English Penn Treebank conversions the parser slightly beats recent projective parsers at similar speed. On 14 CoNLL-2006/2008 datasets it gives the best reported UAS for English, Czech, German and Dutch. This shows that rich higher-order features can be made practical for languages with free word order. The code is released as TurboParser 2.1.

Key points

  • Speed versus accuracy on English (PTB-YM §22, dev):

    • First-order model: 91.38 UAS at 4,063 tokens/sec.
    • Full third-order model: 93.29 UAS at 709 tokens/sec, roughly six times slower.

  • English test set (§23):

    • PTB-YM: 93.07 UAS at 735 tok/s.
    • PTB-S (Stanford basic dependencies): 92.82 UAS at 604 tok/s, compared with 92.7 UAS for Rush and Petrov (2012), whose vine cascade is much faster.

  • Multilingual results: On 14 CoNLL-2006/2008 treebanks the third-order model set new best scores for:

    • Czech: 90.32 vs. 89.46 previously.
    • German: 92.41 vs. 91.89.
    • English: 93.22 vs. 92.68.
    • Dutch: 86.19 vs. 85.81.

    It was competitive on the other languages and ran about 3–4× slower than the vine parser.

  • Algorithm and complexity:

    • AD3 needs O(1/ε) iterations to converge, while subgradient needs O(1/ε²).
    • With K=10 candidate heads per word, each AD3 iteration drops from O(L⁴) to cubic time.

  • Training and decoding setup:

    • Training: 10 epochs of cost-augmented MIRA with ρ=0.05.
    • Pos tags: automatic tags from a jackknifed tagger.
    • Decoding: fractional solutions are rounded to valid trees, but outputs were already integral about 95% of the time.

Interesting ideas

  • Reuse the plain argmax solver for quadratic subproblems. An active set method can solve each component's penalized quadratic problem using only that component's existing MAP routine. This lets any tractable combinatorial solver become a building block in a faster-converging decomposition scheme.
  • Warm-start inner solvers. Reusing the active set from the previous outer iteration is what made the runtimes fast in practice. Carrying state across iterations is a cheap trick worth trying in any nested optimization loop.
  • Choose few large components over many tiny ones. Absorbing grandparent, consecutive-sibling and grand-sibling scores into a single head automaton per head keeps the decomposition compact and agreement faster. This is a useful design principle when building factor-graph models.
  • Prune cheaply before decoding. Limiting candidate heads with a first-order probabilistic model and a relative posterior threshold cuts the asymptotic cost of every subproblem. This filter-then-refine pattern transfers to other structured prediction tasks.
  • Benchmark on projective data too. Evaluating a non-projective parser on projective English allows a direct comparison against exact dynamic-programming parsers. This kind of fair-baseline check is useful whenever an approximate method competes with exact ones in a restricted setting.

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