Elamur Research⌕
☰
home / papers / 2012 / A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing

A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing

Summary

Most dependency parsers rely on a separate part-of-speech tagger, so tagging mistakes flow into the parser and cannot be corrected later. Bohnet and Nivre propose a single transition-based model that predicts POS tags and labeled dependency trees together, including non-projective structures. They extend the SWAP-based transition system of Nivre (2009): the SHIFT action now also assigns a tag to the word it moves onto the stack. Decoding uses beam search, and training uses a structured perceptron with passive-aggressive updates. Two pruning steps keep the larger search space manageable. Only a few high-scoring tag candidates from a preprocessing tagger are allowed, and arc labels never seen in training for a given head/dependent tag pair are excluded. Experiments on Chinese, Czech, English and German show that the joint model beats a pipeline on both tagging and parsing accuracy, reaching state-of-the-art results for all four languages. The authors describe it as the first joint system to produce labeled dependencies and the first joint system to reach top accuracy on non-projective parsing.

Key points

  • The transition set has four actions: LEFT-ARC_d, RIGHT-ARC_d, SHIFT_p and SWAP. Every word must pass through a SHIFT_p, so every node in the output receives a tag. Soundness and completeness carry over directly from Nivre (2009).
  • SHIFT_p is permitted only for the k best tags from a preprocessing tagger whose score is within α of the 1-best tag. Arc labels not observed in training for the predicted tag combination are filtered out. Both restrictions give a significant speed-up.
  • The beam is controlled by two pruning parameters, b1 and b2. A hypothesis's score is the sum of the scores of its configuration–transition pairs.
  • In the English error analysis, the joint model makes fewer tagging errors on ambiguous verb forms (VBN vs. VBD, VBZ vs. NN). It also improves singular nouns and adverbs, with adverbs less often mistaken for IN.
  • The joint model raises F-scores on the central grammatical relations:
    • subjects: German rises from 91.3 to 92.1, English from 95.6 to 96.1;
    • objects: German rises from 86.9 to 87.9, English from 90.2 to 91.9.

Interesting ideas

  • I1. Tag through the SHIFT action. Attaching the tag choice to the action that consumes a word is a cheap way to add tagging to any shift-reduce parser. The same idea could extend to other word-level decisions, such as morphological features, which the authors list as future work.
  • I2. Use the pipeline tagger as a candidate generator. The joint model chooses among a small k-best set from the tagger, using a score margin α, instead of searching all tags. This keeps most of the speed of a pipeline while letting syntax override doubtful tags, and the trick suits any joint model with large label sets.
  • I3. Constrain arc labels with training-data statistics. Disallowing arc labels never seen for a given head/dependent tag pair is a simple, data-driven pruning rule. It would be useful for morphologically rich languages like Ukrainian, where tag inventories are large.
  • I4. Measure tagging gains by grammatical category. Category-level confusion matrices show that the joint model's tagging gains concentrate on syntactically central categories such as verbs. Those gains then appear as better subject and object attachment. Evaluating per category and per function, not just overall accuracy, shows where the joint modeling actually helps.
  • I5. Support non-projectivity without hurting simpler languages. The SWAP-based system handles non-projective trees, which matters for Czech and German. It did not hurt accuracy on Chinese and English, whose benchmark sets contain only projective trees. One general-purpose transition system can therefore serve typologically diverse languages, a useful property for multilingual work.

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 · Part-of-speech tagging

Cited by

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

Cite

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

@inproceedings{bohnet2012transition,
  title = {{A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing}},
  author = {Bohnet, Bernd and Nivre, Joakim},
  booktitle = {Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning},
  year = {2012},
  url = {https://aclanthology.org/D12-1133/}
}

References

51 references, 22 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. Burton H. Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13:422–426. find
  3. Bernd Bohnet and Jonas Kuhn. 2012. The best of both worlds – a graph-based completion model for transition-based parsers. In Proceedings of EACL, pages 77–87. find
  4. Bernd Bohnet. 2010. Top accuracy and fast dependency parsing is not a contradiction. In Proceedings of COLING, pages 89–97. find our card
  5. Bernd Bohnet. 2011. Comparing advanced graph-based and transition-based dependency parsers. In Proceedings of the International Conference on Dependency Linguistics (Depling), pages 282–289. find
  6. Xavier Carreras, Michael Collins, and Terry Koo. 2008. Tag, dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proceedings of CoNL-L, pages 9–16. find
  7. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 957–961. find our card
  8. Eugene Charniak and Mark Johnson. 2005. Coarse-to-fine n-best parsing and MaxEnt discriminative reranking. In Proceedings of ACL, pages 173–180. find our card
  9. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL, pages 132–139. find our card
  10. Shay B. Cohen and Noah A. Smith. 2007. Joint morphological and syntactic disambiguation. In Proceedings of EMNLP-CoNLL, pages 208–217. find
  11. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 112–119. find our card
  12. Michael Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of ACL-EACL, pages 16–23. find our card
  13. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP, pages 1–8. find our card
  14. Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585. find
  15. Andrea Gesmundo, James Henderson, Paola Merlo, and Ivan Titov. 2009. A latent variable model of synchronous syntactic-semantic parsing for multiple languages. In Proceedings of the 2009 CoNLL Shared Task, pages 37–42. find
  16. Yoav Goldberg and Reut Tsarfaty. 2008. A single generative model for joint morphological segmentation and syntactic parsing. In Proceedings of ACL, pages 371– 379. find
  17. Jan Hajič, Massimiliano Ciaramita, Richard Johansson, Daisuke Kawahara, Maria Antònia Martı́, L-luı́s Màrquez, Adam Meyers, Joakim Nivre, Sebastian Padó, Jan Štěpánek, Pavel Straňák, Mihai Surdeanu, Nianwen Xue, and Yi Zhang. 2009. The conll-2009 shared task: Syntactic and semantic dependen… find our card
  18. Jun Hatori, Takuya Matsuzaki, Yusuke Miyao, and Jun’ichi Tsujii. 2011. Incremental joint pos tagging and dependency parsing in chinese. In Proceedings of IJCNLP, pages 1216–1224. find
  19. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL, pages 1077–1086. find
  20. Richard Johansson and Pierre Nugues. 2006. Investigating multilingual dependency parsing. In Proceedings of CoNLL, pages 206–210. find
  21. Terry Koo and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of ACL, pages 1–11. find
  22. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proceedings of ACL, pages 595–603. find our card
  23. Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In Proceedings of EMNLP, pages 1288–1298. find
  24. Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency Parsing. Morgan and Claypool. find
  25. John Lee, Jason Naradowsky, and David A. Smith. 2011. A discriminative model for joint morphological disambiguation and dependency parsing. In Proceedings of ACL, pages 885–894. find
  26. Zhenghua Li, Min Zhang, Wanxiang Che, Ting Liu, Wenliang Chen, and Haizhou Li. 2011. Joint models for chinese POS tagging and dependency parsing. In Proceedings of EMNLP, pages 1180–1191. find
  27. Andre Martins, Noah Smith, and Eric Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proceedings of ACL-IJCNLP, pages 342–350. find
  28. Andre Martins, Noah Smith, Eric Xing, Pedro Aguiar, and Mario Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proceedings of EMNLP, pages 34–44. find our card
  29. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL, pages 81–88. find our card
  30. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91–98. find our card
  31. Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of CoNLL, pages 49–56. find our card
  32. Joakim Nivre. 2006. Inductive Dependency Parsing. Springer. find
  33. Joakim Nivre. 2007. Incremental non-projective dependency parsing. In Proceedings of NAACL HLT, pages 396–403. find
  34. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553. find our card
  35. Joakim Nivre. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of ACL-IJCNLP, pages 351–359. find our card
  36. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of NAACL HLT, pages 404–411. find our card
  37. Slav Petrov, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proceedings of COL-ING/ACL, pages 433–440. find our card
  38. Sebastian Riedel and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proceedings of EMNLP, pages 129– 137. find
  39. Helmut Schmid and Florian Laws. 2008. Estimation of conditional probabilities with decision trees and an application to fine-grained POS tagging. In Proceedings of COLING, pages 777–784. find
  40. Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, Alex Strehl, and S V N Vishwanathan. 2009. Hash Kernels for Structured Data. In Journal of Machine Learning. find
  41. David Smith and Jason Eisner. 2008. Dependency parsing by belief propagation. In Proceedings of EMNLP, pages 145–156. find
  42. Anders Søgaard. 2011. Semi-supervised condensed nearest neighbor for part-of-speech tagging. In Proceedings of ACL, pages 48–52. find
  43. Jun Suzuki, Hideki Isozaki, Xavier Carreras, and Michael Collins. 2009. An empirical study of semi-supervised structured conditional models for dependency parsing. In Proceedings of EMNLP, pages 551–560. find
  44. Ivan Titov and James Henderson. 2007. A latent variable model for generative dependency parsing. In Proceedings of IWPT, pages 144–155. find
  45. Ivan Titov, James Henderson, Paola Merlo, and Gabriele Musillo. 2009. Online graph planarization for synchronous parsing of semantic and syntactic dependencies. In Proceedings of IJCAI. find
  46. Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proceedings of NAACL, pages 252–259. find our card
  47. Reut Tsarfaty. 2006. Integrated morphological and syntactic disambiguation for modern hebrew. In Proceedings of the COLING/ACL 2006 Student Research Workshop, pages 49–54. find our card
  48. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, pages 195–206. find our card
  49. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proceedings of EMNLP, pages 562–571. find our card
  50. Yue Zhang and Stephen Clark. 2011. Syntactic processing using the generalized perceptron and beam search. Computational Linguistics, 37:105–151. find
  51. Yue Zhang and Joakim Nivre. 2011. Transition-based parsing with rich non-local features. In Proceedings of ACL. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bohnet-2012-transition-based-system-joint-part/