Elamur Research⌕
☰
home / papers / 2008 / Integrating Graph-Based and Transition-Based Dependency Parsers

Integrating Graph-Based and Transition-Based Dependency Parsers

Summary

The paper tackles a known tension in data-driven dependency parsing. Graph-based parsers rely on global training and exact search but can only use features over one or two arcs. Transition-based parsers make greedy, locally trained decisions but can condition on everything built so far. Earlier error analysis showed the two families fail in different, complementary places. The authors therefore combine them at training time rather than only at parsing time. One parser, the guide, produces a full parse, and features describing that parse are added to the feature vector of the other parser, the base, which then learns when to rely on them (a form of classifier stacking). They apply this in both directions using MSTParser and MaltParser on the CoNLL-X shared task data sets. Both guided parsers consistently beat their unguided versions, giving a significant gain over the previous state of the art. MST guided by Malt benefits most. The approach matters because it only requires defining new features, yet it exploits complementary model biases in a principled way.

Key points

  • The two systems are MSTParser and MaltParser:
    • MSTParser (McDonald et al., 2006) scores pairs of arcs, uses near-exhaustive unlabeled search plus a separate arc labeler, and is trained online with MIRA.
    • MaltParser (Nivre et al., 2006) uses the linear-time Nivre (2003) transition system with SVM-learned transition scores.
  • The earlier error analysis behind the method (McDonald and Nivre, 2007) found clear differences:
    • Malt is weaker on long arcs and arcs near the root, but stronger on short, deeply embedded arcs.
    • Malt is better on noun and pronoun dependents.
    • MST is better on verbs, adjectives, adverbs, adpositions and conjunctions.
  • The guide features (Table 1) are simple questions about the guide parse:
    • For MST_Malt: whether an arc (i, j), with or without a given label, is present in Malt's output, and which label Malt gives to a node.
    • For Malt_MST: whether MST links the top of the stack and the front of the buffer, plus MST's head direction and labels for those tokens.
  • Evaluation is on the CoNLL-X shared task data sets. Both guided models improve, and MST_Malt ends up significantly more accurate than Malt_MST.
  • Related combinations each reported about 1.7 points on the Penn Treebank:
    • Sagae and Lavie (2006): parse-time voting with four parsers.
    • McDonald (2006): MSTParser using features from the Collins and Charniak parsers.

Interesting ideas

  • I1. Combine at learning time, not just by voting. Feeding one model's single best output to another as extra features lets the second model learn context-dependent trust in the first. Only two systems are needed, unlike voting ensembles that require at least three.
  • I2. Pick partners by their error profiles. The pairing was motivated by complementary error distributions, not chosen ad hoc. Running an error breakdown by arc length, depth and POS before building an ensemble is a reusable recipe for any pair of structured predictors.
  • I3. Global inference spreads local gains. The base model benefits more from guidance when its inference is global, because fixing one decision type helps others, while greedy decoders lose part of the gain to error propagation. This is useful when deciding which model in a pipeline should receive the auxiliary signals.
  • I4. The learner affects how much guide features are used. With a batch, regularized learner such as an SVM, guide features may get small weights if the original features already separate the training data. An online learner such as MIRA tends to latch onto them early and weight them heavily. Inspecting learned weights is a cheap way to check whether stacked features are actually used.
  • I5. Stacking is a cheap alternative to re-ranking. Only the guide's top parse is consumed, and the base model is not forced to follow it. This keeps the cost far below n-best re-ranking, which matters for low-resource or production settings.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Dependency parsing

Cited by

127 papers of our library cite it (of the 140884 whose bibliographies we read); 10 of them have a page here, 117 not yet.

Cite

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

@inproceedings{nivre2008integrating,
  title = {{Integrating Graph-Based and Transition-Based Dependency Parsers}},
  author = {Nivre, Joakim and McDonald, Ryan},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  url = {https://aclanthology.org/P08-1108/}
}

References

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

  1. Giuseppe Attardi. 2006. Experiments with a multilanguage non-projective dependency parser. In Proceedings of CoNLL, pages 166–170. find our card
  2. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of CoNLL, pages 149–164. find our card
  3. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL, pages 132–139. find our card
  4. Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  5. Michael Collins. 2000. Discriminative reranking for natural language parsing. In Proceedings of ICML, pages 175–182. find our card
  6. Yuan Ding and Martha Palmer. 2004. Synchronous dependency insertion grammars: A grammar formalism for syntax based statistical MT. In Proceedings of the Workshop on Recent Advances in Dependency Grammar, pages 90–97. find
  7. Xiangyu Duan, Jun Zhao, and Bo Xu. 2007. Probabilistic parsing action models for multi-lingual dependency parsing. In Proceedings of EMNLP-CoNLL, pages 940–946. find
  8. Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING, pages 340–345. find our card
  9. Radu Florian, Hany Hassan, Abraham Ittycheriah, Hongyan Jing, Nanda Kambhatla, Xiaoqiang Luo, Nicolas Nicolov, and Salim Roukos. 2004. A statistical model for multilingual entity detection and tracking. In Proceedings of NAACL/HLT. find
  10. Johan Hall, Jens Nilsson, Joakim Nivre, Gülsen Eryiğit, Beáta Megyesi, Mattias Nilsson, and Markus Saers. 2007. Single malt or blended? A study in multilingual parser optimization. In Proceedings of EMNLP-CoNLL. find
  11. Keith Hall. 2007. K-best spanning tree parsing. In Proceedings of ACL, pages 392–399. find
  12. Kristy Hollingshead and Brian Roark. 2007. Pipeline iteration. In Proceedings of ACL, pages 952–959. find
  13. Richard Johansson and Pierre Nugues. 2007. Incremental dependency parsing using online learning. In Proceedings of EMNLP-CoNLL, pages 1134–1138. find
  14. Ryan McDonald and Joakim Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In Proceedings of EMNLP-CoNLL, pages 122– 131. find our card
  15. Ryan McDonald and Giorgio Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of IWPT, pages 122–131. find
  16. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91–98. find our card
  17. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of HLT/EMNLP, pages 523–530. find our card
  18. Ryan McDonald, Kevin Lerman, and Fernando Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proceedings of CoNLL, pages 216–220. find our card
  19. Ryan McDonald. 2006. Discriminative Learning and Spanning Tree Algorithms for Dependency Parsing. Ph.D. thesis, University of Pennsylvania. find
  20. Tetsuji Nakagawa. 2007. Multilingual dependency parsing using global features. In Proceedings of EMNLP-CoNLL, pages 952–956. find
  21. Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of CoNLL, pages 49–56. find our card
  22. Joakim Nivre, Johan Hall, Jens Nilsson, Gülsen Eryiğit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225. find our card
  23. Joakim Nivre, Johan Hall, Sandra Kübler, Ryan McDonald, Jens Nilsson, Sebastian Riedel, and Deniz Yuret. 2007. find
  24. The CoNLL 2007 shared task on dependency parsing. In Proceedings of EMNLP-CoNLL, pages 915–932. find our card
  25. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of IWPT, pages 149–160. find our card
  26. Kenji Sagae and Alon Lavie. 2006. Parser combination by reparsing. In Proceedings of NAACL: Short Papers, pages 129–132. find our card
  27. Anoop Sarkar. 2001. Applying co-training methods to statistical parsing. In Proceedings of NAACL, pages 175–182. find
  28. Rion Snow, Dan Jurafsky, and Andrew Y. Ng. 2005. Learning syntactic patterns for automatic hypernym discovery. In Proceedings of NIPS. find
  29. Mark Steedman, Rebecca Hwa, Miles Osborne, and Anoop Sarkar. 2003. Corrected co-training for statistical parsers. In Proceedings of ICML, pages 95–102. find
  30. Ben Taskar, Simon Lacoste-Julien, and Dan Klein. 2005. A discriminative matching approach to word alignment. In Proceedings of HLT/EMNLP, pages 73–80. find our card
  31. Ivan Titov and James Henderson. 2007a. Fast and robust multilingual dependency parsing with a generative latent variable model. In Proceedings of EMNLP-CoNLL, pages 947–951. find
  32. Ivan Titov and James Henderson. 2007b. A latent variable model for generative dependency parsing. In Proceedings of IWPT, pages 144–155. find
  33. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, pages 195–206. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nivre-2008-integrating-graph-based-transition-based/