Generic Oracles for Structured Prediction

What it is about

Local models for structured prediction are trained on gold action sequences only, so they suffer exposure bias and never learn to recover from their own mistakes. Active imitation learning, also called dynamic oracle learning in NLP, lets training explore other outputs, but it needs an oracle that says the best next action for any partial output. The authors show how to build such oracles generically: a candidate output is an automaton over actions, the loss is a minimum-weight problem on a regular language, and the oracle is a shortest-path lookup over the intersection with the gold-annotation automaton. They show that the lookup can be moved mostly into one precomputation, which makes the oracle efficient. The paper is theoretical and gives no experimental scores.

Ideas

• I1. Dynamic oracle for the arc-standard parser in en/src/parse.rs: replace the static oracle with a dynamic one that returns the lowest-loss transition for any partial state (arc-standard, as in Goldberg and Nivre), and measure LAS on the EWT dev set at beam 8 with early update.
• I2. Exploration during training: run the 12-epoch perceptron with rollouts from the model's own transitions, scored by the dynamic oracle, and report dev LAS per epoch against the static baseline; repeat the run twice to check determinism before claiming a gain.
• I3. Tagger oracle in en/src/ptag.rs: with a beam of 2, compute the lowest-loss tag sequence for each prefix and measure UPOS accuracy on the EWT dev set against the current perceptron.

For Mova

The arc-standard oracle and the early update are in en/src/parse.rs, and the beam and tagger are in en/src/ptag.rs. No English chapter is about this method; the closest is 20. Syntax: the Universal Dependencies frame. Measure first: EWT dev LAS with the dynamic oracle against the static one, using the dev set only, since the test set is used once per release.

Cite

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

@inproceedings{teichmann2021generic,
  title = {{Generic Oracles for Structured Prediction}},
  author = {Teichmann, Christoph and Venant, Antoine},
  booktitle = {Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021)},
  year = {2021},
  doi = {10.18653/v1/2021.iwpt-1.1},
  url = {https://doi.org/10.18653/v1/2021.iwpt-1.1}
}

References

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

1. 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
2. Kianté Brantley, Hal Daumé III, and Amr Sharaf. 2020. Active imitation learning with noisy guidance. In 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… find
3. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2093– 2105, Online. Association for Computational Linguistics. find
4. Maximin Coavoux and Shay B. Cohen. 2019. Discontinuous constituency parsing with a stack-free transition system and a dynamic oracle. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and… find
5. 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, Doha, Qatar. Association for Computational… find
6. Maximin Coavoux and Benoı̂t Crabbé. 2016. Neural greedy constituent parsing with dynamic oracles. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 172–182, Berlin, Germany. Association for Computational Linguistics. find
7. Carlos Gómez-Rodrı́guez, Michalina Strzyz, and David Vilares. 2020. A unifying theory of transition-based and sequence labeling parsing. In Proceedings of the 28th International Conference on Computational Linguistics, pages 3776–3793, Barcelona, Spain (Online). International Committee on Computati… find
8. James Cross and Liang Huang. 2016. Span-based constituency parsing with a structure-label system and provably optimal dynamic oracles. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1–11, Austin, Texas. Association for Computational Linguistics. find
9. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA. find
10. E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numer. Math., 1(1):269–271. find
11. Shyh-Shiun Hung, Hen-Hsen Huang, and Hsin-Hsi Chen. 2020. A complete shift-reduce Chinese discourse parser with robust dynamic oracle. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 133–138, Online. Association for Computational Linguistics. find
12. Daniel Fernández-González and Carlos Gómez-Rodrı́guez. 2018a. A dynamic oracle for linear-time 2-planar dependency parsing. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), p… find
13. Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. 2017. Imitation learning: A survey of learning methods. ACM Comput. Surv., 50(2). find
14. Daniel Fernández-González and Carlos Gómez-Rodrı́guez. 2018b. Dynamic oracles for top-down and in-order shift-reduce constituent parsing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1303–1313, Brussels, Belgium. Association for Computational Li… find
15. Alexander Koller and Marco Kuhlmann. 2011. A generalized view on parsing and translation. In Proceedings of the 12th International Conference on Parsing Technologies, pages 2–13, Dublin, Ireland. Association for Computational Linguistics. find
16. Daniel Fried and Dan Klein. 2018. Policy gradient as a proxy for dynamic oracles in constituency parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 469–476, Melbourne, Australia. Association for Computational Linguistic… find
17. Miryam de Lhoneux, Sara Stymne, and Joakim Nivre. 2017. Arc-hybrid non-projective dependency parsing with a static-dynamic oracle. In Proceedings of the 15th International Conference on Parsing Technologies, pages 99–104, Pisa, Italy. Association for Computational Linguistics. find
18. Yoav Goldberg and Joakim Nivre. 2012. A dynamic oracle for arc-eager dependency parsing. In Proceedings of COLING 2012, pages 959–976, Mumbai, India. find
19. The COLING 2012 Organizing Committee. find
20. David Mareček and Zdeněk Žabokrtský. 2011. Gibbs sampling with treeness constraint in unsupervised dependency parsing. In Proceedings of Workshop on Robust Unsupervised and Semisupervised Methods in Natural Language Processing, pages 1–8. find
21. Yoav Goldberg, Francesco Sartorio, and Giorgio Satta. 2014. A tabular method for dynamic oracles in transition-based parsing. Transactions of the Association for Computational Linguistics, 2:119–130. find
22. Mehryar Mohri. 2004. Weighted Finite-State Transducer Algorithms. An Overview, pages 551–563. Springer Berlin Heidelberg, Berlin, Heidelberg. find
23. Mehryar Mohri. 2009. Weighted automata algorithms. In Manfred Droste, Werner Kuich, and Heiko Vogler, editors, Handbook of Weighted Automata, pages 213–254. Springer Berlin Heidelberg, Berlin, Heidelberg. find
24. Mark-Jan Nederhof. 2021. Calculating the optimal step of arc-eager parsing for non-projective trees. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 2273–2283, Online. Association for Computational Linguistics. find
25. M. O. Rabin and D. Scott. 1959. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125. find
26. Stéphane Ross and J. Andrew Bagnell. 2014. Reinforcement and imitation learning via interactive no-regret learning. CoRR, abs/1406.5979. find
27. Stephane Ross, Geoffrey Gordon, and Drew Bagnell. 2011. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research… find
28. Mitchell Stern, Jacob Andreas, and Dan Klein. 2017. A minimal span-based neural constituency parser. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 818–827, Vancouver, Canada. Association for Computational Linguistics. find
29. Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA. find
30. Xiang Yu, Ngoc Thang Vu, and Jonas Kuhn. 2018. Approximate dynamic oracle for dependency parsing with reinforcement learning. In Proceedings of the Second Workshop on Universal Dependencies (UDW 2018), pages 183–191, Brussels, Belgium. Association for Computational Linguistics. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2021-teichmann-generic-oracles-structured-prediction/