Approximate Dynamic Oracle for Dependency Parsing with Reinforcement Learning

What it is about

A dynamic oracle tells a transition parser which action is best from a state the parser itself got into by mistake, so that training covers its own errors. For transition systems where the exact dynamic oracle is hard to derive, the authors train an approximate one (ADO) with deep Q-learning. The oracle sees the gold tree as positions of gold heads in the stack and buffer, and learns action costs from a reward that counts the gold arcs an action makes unreachable. Over 55 big CoNLL 2017 treebanks, the ADO raises average LAS over the static oracle by 0.33 (arc-standard), 0.33 (Attardi), 0.51 (swap) and 0.21 (arc-hybrid) points, and it helps on 35 to 41 treebanks per system. Its actions differ from the exact dynamic oracle in 0.53% of states.

Ideas

• I1. en/src/parse.rs: add a dynamic oracle for arc-standard that charges each action by the number of gold arcs it makes unreachable, and train with it; measure cv LAS on the train folds against the static oracle, two runs each.
• I2. en/src/parse.rs: learn the oracle costs with a small linear model over gold-head positions instead of deep Q-learning (CPU only, no foreign weights), and measure how often its action differs from the exact arc-standard dynamic oracle on EWT train states.
• I3. The paper's largest gains are on small treebanks, so measure static against dynamic-oracle LAS on cross-validation of the ATIS train split (lowercase queries, LAS 63.0 on test now).

For Mova

The problem is error propagation in the en parser's greedy arc-standard decoding, which the paper describes in its introduction, so the chapter is 20-syntax-overview. The code is en/src/parse.rs, which has a static oracle today. Measure first: the error rate from erroneous starting states (their oracle recovery test) on EWT train, which shows how much error propagation there is before any training change.

Topics: Dependency parsing · Treebanks

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/w18-6021

@inproceedings{yu2018approximate,
  title = {{Approximate Dynamic Oracle for Dependency Parsing with Reinforcement Learning}},
  author = {Yu, Xiang and Vu, Ngoc Thang and Kuhn, Jonas},
  booktitle = {Proceedings of the Second Workshop on Universal Dependencies (UDW 2018)},
  year = {2018},
  doi = {10.18653/v1/w18-6021},
  url = {https://doi.org/10.18653/v1/w18-6021}
}

References

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

1. Marco Kuhlmann and Joakim Nivre. 2006. Mildly non-projective dependency structures. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 507–514. find
2. Oron Anschel, Nir Baram, and Nahum Shimkin. 2016. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning. arXiv preprint arXiv:1611.01929. — [arXiv:1611.01929](https://arxiv.org/abs/1611.01929) find
3. Minh Le and Antske Fokkens. 2017. Tackling error propagation through reinforcement learning: A case of greedy dependency parsing. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, volume 1, pages 677–687. find
4. Giuseppe Attardi. 2006. Experiments with a multilan-guage non-projective dependency parser. In Proceedings of the Tenth Conference on Computational Natural Language Learning, pages 166–170. Association for Computational Linguistics. find
5. Francis Maes, Ludovic Denoyer, and Patrick Galli-nari. 2009. Structured prediction with reinforcement learning. Machine learning, 77(2-3):271. find
6. Michael A Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th annual ACM southeast conference, pages 95–102. Citeseer. find
7. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. find
8. Hal Daumé, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. Machine learning, 75(3):297–325. find
9. Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux, Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji, Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Pau… find
10. Sergey Edunov, Myle Ott, Michael Auli, David Grangier, and Marc’Aurelio Ranzato. 2017. Classical structured prediction losses for sequence to sequence learning. arXiv preprint arXiv:1711.04956. find
11. Yoav Goldberg and Joakim Nivre. 2012. A dynamic oracle for arc-eager dependency parsing. Proceedings of COLING 2012, pages 959–976. find
12. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the Association of Computational Linguistics, 1:403–414. find
13. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together, pages 50–57. Association for Computational Linguistics. find our card
14. Carlos Gómez-Rodrı́guez and Daniel Fernández-González. 2015. An efficient dynamic oracle for unrestricted non-projective 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
15. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. find our card
16. Joakim Nivre. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1-Volume 1, pages 351–359. Association for Comput… find
17. Carlos Gómez-Rodrı́guez, Francesco Sartorio, and Giorgio Satta. 2014. A polynomial-time dynamic oracle for non-projective dependency parsing. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 917–927. find
18. Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. 2015. Prioritized experience replay. arXiv preprint arXiv:1511.05952. find
19. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional lstm feature representations. Transactions of the Association for Computational Linguistics, 4:313–327. find our card
20. Milan Straka, Jan Hajic, and Jana Straková. 2016. Udpipe: Trainable pipeline for processing conll-u files performing tokenization, morphological analysis, pos tagging and parsing. In LREC. find our card
21. Marco Kuhlmann, Carlos Gómez-Rodrı́guez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 673–682. Association for… find
22. Milan Straka, Jan Hajic, Jana Straková, and Jan Hajic jr. 2015. Parsing universal dependency treebanks using neural networks and search-based oracle. In International Workshop on Treebanks and Linguistic Theories (TLT14), pages 208–220. find
23. Richard S Sutton and Andrew G Barto. 1998. Reinforcement learning: An introduction, volume 1. MIT press Cambridge. find
24. Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Has-selt, Marc Lanctot, and Nando Freitas. 2016. Dueling network architectures for deep reinforcement learning. In International Conference on Machine Learning, pages 1995–2003. find
25. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, volume 3, pages 195–206. Nancy, France. find our card
26. Xiang Yu and Ngoc Thang Vu. 2017. Character composition model with convolutional neural networks for dependency parsing on morphologically rich languages. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), volume 2, pages 672–678. find
27. Daniel Zeman, Martin Popel, Milan Straka, Jan Hajic, Joakim Nivre, Filip Ginter, Juhani Luotolahti, Sampo Pyysalo, Slav Petrov, Martin Potthast, Francis Tyers, Elena Badmaeva, Memduh Gokirmak, Anna Nedoluzhko, Silvie Cinkova, Jan Hajic jr., Jaroslava Hlavacova, Václava Kettnerová, Zdenka Uresova,… find
28. Conll 2017 shared task: Multilingual parsing from raw text to universal dependencies. In Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 1–19, Vancouver, Canada. Association for Computational Linguistics. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2018-yu-approximate-dynamic-oracle-dependency-parsing/