Mova0.5 pre-release⌕
☰
home / docs / papers / English / Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement

Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement

What it is about

The parser predicts all edges of a graph in parallel, then refines the whole graph in recursive passes. Each pass is conditioned on the graph from the previous pass. An initial parser supplies the first graph, and the paper refines both UDify output and its own graph parser (SynTr). Refinement reduces LAS error relative to earlier models by 5.78%, 9.15% and 23.7% for SynTr on English, Chinese and German, and by 10.64% for refined biaffine output. Three refinement iterations are used. Per-step error reductions on the UD development sets are 13.62%, 17.74% and 0.16% for low-resource treebanks, and 29.38%, 0.81% and 0.41% for high-resource ones. Non-projective trees need more iterations than projective ones.

Ideas

For Mova

The code is en/src/parse.rs, and en/src/ctx.rs already has multi-pass parsing to build on. Use en folds for the decision. The paper's refinement is neural, so the pass must be a deterministic rule-and-count rescoring, and it must not use any large model at test time.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00358 · arXiv 2003.13118

@article{mohammadshahi2021recursive,
  title = {{Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement}},
  author = {Mohammadshahi, Alireza and Henderson, James},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.1162/tacl\_a\_00358},
  eprint = {2003.13118},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1162/tacl_a_00358}
}

References

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

  1. Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pape… find
  2. Giuseppe Attardi and Massimiliano Ciaramita. 2007. Tree revision learning for dependency parsing. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 388–395, Rochester, New York… find
  3. Abhijeet Awasthi, Sunita Sarawagi, Rasna Goyal, Sabyasachi Ghosh, and Vihari Piratla. 2019. Parallel iterative edit models for local sequence transduction. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural… find
  4. Miguel Ballesteros, Yoav Goldberg, Chris Dyer, and Noah A. Smith. 2016. Training with exploration improves a greedy stack LSTM parser. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2005–2010, Austin, Texas. Association for Computational Linguistics.… find
  5. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 957–961, Prague, Czech Republic. Association for Compu… find
  6. Danqi Chen and Christopher Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing(EMNLP), pages 740–750, Doha, Qatar. Association for Computational Linguistics. DOI: https://doi.org/10 .311… find our card
  7. Miryam de Lhoneux, Sara Stymne, and Joakim Nivre. 2017. Old school vs. new school: Comparing transition-based parsers with and without neural network enhancement. In Proceedings of the 15th International Workshop on Treebanks and Linguistic Theories (TLT15), pages 99–110. find
  8. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,… find
  9. Timothy Dozat and Christopher D. Manning. 2016. Deep biaffine attention for neural dependency parsing. find our card
  10. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015. Transition-based dependency parsing with stack long short-term memory. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural… find our card
  11. Huadong Chen, Shujian Huang, David Chiang, and Jiajun Chen. 2017. Improved neural machine translation with a syntax-aware encoder and decoder. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). find
  12. Hao Cheng, Hao Fang, Xiaodong He, Jianfeng Gao, and Li Deng. 2016. Bi-directional attention with agreement for dependency parsing. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2204–2214, Austin, Texas, Association for Computational Linguistics. DOI… find
  13. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the national Bureau of Standards B, 71(4):233–240. DOI: https:// doi.org/10.6028/jres.071B.032 — [doi:10.6028/jres.071b.032](https://doi.org/10.6028/jres.071b.032) find
  14. Zhiyi Chi. 1999. Statistical properties of probabilistic context-free grammars. Computational Linguistics, 25(1):131–160. find
  15. Chu Yoeng-jin and Liu Tseng-hong. 1965 On the shortest arborescence of a directed graph. Science Sinica, 14:1396–1400. find
  16. Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics. DOI: https://doi.org/10 .3115/992628.992688 find our card
  17. James Cross and Liang Huang. 2016. Incremental parsing with minimal features using bidirectional LSTM. In Proceedings of the 54th Annual Meeting of the Association for Com-Daniel Fernández-González and Carlos Gómez-Rodrı́guez. 2019. Left-to-right dependency parsing with pointer networks. In Proce… find
  18. Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 710–716, Minneapolis, Minnesota. Association for Computational Linguistics. find
  19. K. Knight and J. Graehl. 2005. An overview of probabilistic tree transducers for natural language processing. In A. Gelbukh, editor, Computational Linguistics and Intelligent Text Processing. find
  20. CICLing 2005. Lecture Notes in Computer Science, vol 3406, pages 1–24, Springer, Berlin, Heidelberg. DOI: https:// doi.org/10.1007/978-3-540-30586 -6 1 — [doi:10.1007/978-3-540-30586](https://doi.org/10.1007/978-3-540-30586) find
  21. Jan Hajič, Massimiliano Ciaramita, Richard Johansson, Daisuke Kawahara, Maria Antònia Martı́, Lluı́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 dependenc… find our card
  22. Dan Kondratyuk and Milan Straka. 2019. 75 languages, 1 model: Parsing universal dependencies universally. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). DOI: https://doi.… ↗ our card
  23. Keith Hall and Václav Novák. 2005. Corrective modeling for non-projective dependency parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 42–52, Vancouver, British Columbia. Association for Computational Linguistics DOI: https://doi.org/10.3115/1654494 .1654499,… ↗
  24. Terry Koo and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1–11. find
  25. Artur Kulmizev, Miryam de Lhoneux, Johannes Gontrum, Elena Fano, and Joakim Nivre. 2019. Deep contextualized word embeddings in transition-based and graph-based dependency parsing - a tale of two parsers revisited. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processin… find
  26. Felix Hennig and Arne Köhn. 2017. Dependency tree transformation with tree transducers. In Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017), pages 58–66. find our card
  27. Tao Ji, Yuanbin Wu, and Man Lan. 2019. Graph-based dependency parsing with graph neural networks. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2475–2485, Florence, Italy. Association for Computational Linguistics. DOI: https://doi.org/10 .18653/v1… find
  28. Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, and Noah A. Smith. 2016. Distilling an ensemble of greedy dependency parsers into one MST parser. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1744–1753, Austin, Texas. Association fo… find
  29. David R. Karger, Philip N. Klein, and Robert E. Tarjan. 1995. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM (JACM), 42(2):321–328. find
  30. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature represen-Jason Lee, Elman Mansimov, and Kyunghyun Cho. 2018. Deterministic non-autoregressive neural sequence modeling by iterative refinement. In Proceedings of the 2018 Conference o… find
  31. Mumbai, India. The COLING 2012 Organizing Committee. find
  32. Diego Marcheggiani and Ivan Titov. 2017. Encoding sentences with graph convolutional networks for semantic role labeling. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1506–1515, Copenhagen, Denmark. Association for Computational Linguistics. DOI: h… find
  33. Miryam de Lhoneux, Sara Stymne, and Joakim Nivre. 2017. Old school vs. new school: Comparing transition-based parsers with and without neural network enhancement. In Proceedings of the 15th International Workshop on Treebanks and Linguistic Theories (TLT15), pages 99–110. find
  34. Zuchao Li, Hai Zhao, and Kevin Parnow. 2020. Global greedy dependency parsing. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in A… — [doi:10.1609/aaai.v34i05.6348](https://doi.org/10.1609/aaai.v34i05.6348) find
  35. Jared Lichtarge, Christopher Alberti, Shankar Kumar, Noam Shazeer, and Niki Parmar. 2018. Weakly supervised grammatical error correction using iterative decoding. arXiv preprint arXiv:1811.01710. — [arXiv:1811.01710](https://arxiv.org/abs/1811.01710) find
  36. Xuezhe Ma and Eduard Hovy. 2017. Neural probabilistic model for non-projective MST parsing. In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 59–69, Taipei, Taiwan. Asian Federation of Natural Language Processing. find
  37. Xuezhe Ma, Zecong Hu, Jingzhou Liu, Nanyun Peng, Graham Neubig, and Eduard Hovy. 2018. Stack-pointer networks for dependency parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1403–1414, Melbourne, Australia. Association… find
  38. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2): 313–330. DOI: https://doi.org/10 .21236/ADA273556 find our card
  39. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 91–98, Ann Arbor, Michigan. Association for Computational Linguistics. DOI: https:/… find our card
  40. Ryan McDonald and Joakim Nivre. 2011. Analyzing and integrating dependency parsers. Computational Linguistics, 37(1):197–230. DOI: https://doi.org/10.1162/coli a 00039 ↗
  41. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In 11th Conference of the European Chapter of the Association for Computational Linguistics, Trento, Italy. Association for Computational Linguistics. find our card
  42. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523–530, Vancouver, British Columb… find our card
  43. Xuezhe Ma and Hai Zhao. 2012. Fourth-order dependency parsing. In Proceedings of COLING 2012: Posters, pages 785–796, Computational Linguistics. DOI: https:// doi.org/10.18653/v1/N18-1202 find
  44. Alireza Mohammadshahi and James Henderson. 2020. Graph-to-graph transformer for transition-based dependency parsing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings, pages 3278–3289, Online. Association for Computational Linguistics. find our card
  45. Girogion Satta and Eric Brill. 1996. Efficient transformation-based parsing. In 34th Annual Meeting of the Association for Computational Linguistics, pages 255–262, Santa Cruz, California, USA. Association for Computational Linguistics. DOI: https://doi.org /10.3115/981863.981897 ↗
  46. Jens Nilsson and Joakim Nivre. 2008. MaltEval: an evaluation and visualization tool for dependency parsing. In LREC 2008. find
  47. Joakim Nivre, Mitchell Abrams, Željko Agić, Lars Ahrenberg, Lene Antonsen, Katya Aplonova, Maria Jesus Aranzabe, Gashaw Arutie, Masayuki Asahara, Luma Ateyah, Mohammed Attia, Aitziber Atutxa, Liesbeth Augustinus, Elena Badmaeva, Miguel Ballesteros, Esha Banerjee, Sebastian Bank, Verginica Barbu Mi… find
  48. Joakim Nivre and Mario Scholz. 2004. Deterministic dependency parsing of English text. In COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics, pages 64–70, Geneva, Switzerland. COLING DOI: https://doi.org/10 .3115/1220355.1220365 find our card
  49. Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 464–468, New… find
  50. Aaron Smith, Miryam de Lhoneux, Sara Stymne, and Joakim Nivre. 2018. An investigation of the interactions between pre-trained word embeddings, character models and POS tags in dependency parsing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2711–27… find
  51. Milan Straka. 2018. UDPipe 2.0 prototype at CoNLL 2018 UD shared task. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 197–207, Brussels, Belgium. Association for Computational Linguistics. find our card
  52. Roman Novak, Michael Auli, and David Grangier. 2016. Iterative refinement for machine translation. find
  53. Ilan Tchernowitz, Liron Yedidsion, and Roi Reichart. 2016. Effective greedy inference for graph-based non-projective dependency parsing. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 711–720, Austin, Texas. Association for Computational Linguistics.… find
  54. Deric Pang, Lucy H. Lin, and Noah A. Smith. 2019. Improving natural language inference with a pretrained parser. find
  55. Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolog… find
  56. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 195–206. Nancy, France. find our card
  57. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. find
  58. Daniel Zeman, Jan Hajič, Martin Popel, Martin Potthast, Milan Straka, Filip Ginter, Joakim Nivre, and Slav Petrov. 2018. find
  59. CoNLL 2018 shared task: Multilingual parsing from raw text to universal dependencies. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 1–21, Brussels, Belgium. Association for Computational Linguistics. find our card
  60. Wenhui Wang and Baobao Chang. 2016. Graph-based dependency parsing with bidirectional LSTM. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2306–2315, Berlin, Germany. Association for Computational Linguistics. find
  61. Hao Zhang and Ryan McDonald. 2012. Generalized higher-order dependency parsing with cube pruning. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 320–331, Jeju Island, Korea. Association for Computatio… find
  62. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (V… find
  63. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, R’emi Louf, Morgan Funtowicz, and Jamie Brew. 2019. Huggingface’s transformers: State-of-the-art natural language processing. ArXiv, abs/ 1910.03771. DOI: https://doi.org/10 .18653/v1… find
  64. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, and others. 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144. find
  65. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 188–193, Portland, Oregon, USA. Association for Computational Linguistics… find
  66. Yuhao Zhang, Peng Qi, and Christopher D. Manning. 2018. Graph convolution over pruned dependency trees improves relation extraction. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2205–2215, Brussels, Belgium. Association for Computational Lin guisti… find
  67. Xiaoqing Zheng. 2017. Incremental graph-based neural dependency parsing. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1655–1665, Copenhagen, Denmark. Association for Computational Linguistics. PMID: 28199123 find
  68. Nianwen Xue, Fu-Dong Chiou, and Martha Palmer. 2002. Building a large-scale annotated Chinese corpus. In COLING 2002: The 19th International Conference on Computational Linguistics. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2021-mohammadshahi-recursive-non-autoregressive-graph-graph/