{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T17:29:42Z","timestamp":1773854982950,"version":"3.50.1"},"reference-count":29,"publisher":"MIT Press","license":[{"start":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T00:00:00Z","timestamp":1662595200000},"content-version":"vor","delay-in-days":250,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,9,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Greedy algorithms for NLP such as transition-based parsing are prone to error propagation. One way to overcome this problem is to allow the algorithm to backtrack and explore an alternative solution in cases where new evidence contradicts the solution explored so far. In order to implement such a behavior, we use reinforcement learning and let the algorithm backtrack in cases where such an action gets a better reward than continuing to explore the current solution. We test this idea on both POS tagging and dependency parsing and show that backtracking is an effective means to fight against error propagation.<\/jats:p>","DOI":"10.1162\/tacl_a_00496","type":"journal-article","created":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T13:57:24Z","timestamp":1662645444000},"page":"888-903","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":5,"title":["Dependency Parsing with Backtracking using Deep Reinforcement Learning"],"prefix":"10.1162","volume":"10","author":[{"given":"Franck","family":"Dary","sequence":"first","affiliation":[{"name":"Aix Marseille Univ, Universit\u00e9 de Toulon, CNRS, LIS, Marseille, France. franck.dary@lis-lab.fr"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxime","family":"Petit","sequence":"additional","affiliation":[{"name":"Aix Marseille Univ, Universit\u00e9 de Toulon, CNRS, LIS, Marseille, France. maxime.petit@lis-lab.fr"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexis","family":"Nasr","sequence":"additional","affiliation":[{"name":"Aix Marseille Univ, Universit\u00e9 de Toulon, CNRS, LIS, Marseille, France. alexis.nasr@lis-lab.fr"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"2022090813571528800_bib1","doi-asserted-by":"publisher","first-page":"1354","DOI":"10.18653\/v1\/D15-1159","article-title":"Improved transition-based parsing and tagging with neural networks","volume-title":"Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing","author":"Alberti","year":"2015"},{"key":"2022090813571528800_bib2","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.18653\/v1\/D17-1130","article-title":"AMR parsing using stack-LSTMs","volume-title":"Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing","author":"Ballesteros","year":"2017"},{"key":"2022090813571528800_bib3","doi-asserted-by":"publisher","first-page":"2005","DOI":"10.18653\/v1\/D16-1211","article-title":"Training with exploration improves a greedy stack LSTM parser","volume-title":"Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing","author":"Ballesteros","year":"2016"},{"key":"2022090813571528800_bib4","first-page":"1455","article-title":"A transition-based system for joint part-of-speech tagging and labeled non-projective dependency parsing","volume-title":"Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning","author":"Bohnet","year":"2012"},{"key":"2022090813571528800_bib5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1162\/tacl_a_00051","article-title":"Enriching word vectors with subword information","volume":"5","author":"Bojanowski","year":"2017","journal-title":"Transactions of the Association for Computational Linguistics"},{"key":"2022090813571528800_bib6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.18653\/v1\/2021.iwpt-1.3","article-title":"The reading machine: A versatile framework for studying incremental parsing strategies","volume-title":"Proceedings of the 17th International Conference on Parsing Technologies (IWPT 2021)","author":"Dary","year":"2021"},{"key":"2022090813571528800_bib7","doi-asserted-by":"publisher","first-page":"334","DOI":"10.3115\/v1\/P15-1033","article-title":"Transition-based dependency parsing with stack long short-term memory","volume-title":"Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)","author":"Dyer","year":"2015"},{"key":"2022090813571528800_bib8","doi-asserted-by":"publisher","first-page":"1440","DOI":"10.1109\/ICCV.2015.169","article-title":"Fast R-CNN","volume-title":"Proceedings of the IEEE International Conference on Computer Vision","author":"Girshick","year":"2015"},{"key":"2022090813571528800_bib9","first-page":"959","article-title":"A dynamic oracle for arc-eager dependency parsing","volume-title":"Proceedings of COLING 2012","author":"Goldberg","year":"2012"},{"key":"2022090813571528800_bib10","first-page":"1077","article-title":"Dynamic programming for linear-time incremental parsing","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics","author":"Huang","year":"2010"},{"key":"2022090813571528800_bib11","first-page":"388","article-title":"Statistical significance tests for machine translation evaluation","volume-title":"Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing","author":"Koehn","year":"2004"},{"key":"2022090813571528800_bib12","doi-asserted-by":"publisher","first-page":"2420","DOI":"10.18653\/v1\/P19-1232","article-title":"Multi-task semantic dependency parsing with policy gradient for learning easy-first strategies","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"Kurita","year":"2019"},{"key":"2022090813571528800_bib13","first-page":"677","article-title":"Tackling error propagation through reinforcement learning: A case of greedy dependency parsing","volume-title":"Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers","author":"Minh","year":"2017"},{"key":"2022090813571528800_bib14","doi-asserted-by":"crossref","first-page":"77","DOI":"10.18653\/v1\/W19-2909","article-title":"D","volume-title":"Proceedings of the Workshop on Cognitive Modeling and Computational Linguistics","author":"Lopopolo","year":"2019"},{"issue":"6","key":"2022090813571528800_bib15","doi-asserted-by":"publisher","first-page":"578","DOI":"10.3758\/BF03203972","article-title":"The span of the effective stimulus during a fixation in reading","volume":"17","author":"McConkie","year":"1975","journal-title":"Perception & Psychophysics"},{"issue":"5","key":"2022090813571528800_bib16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.3758\/BF03335168","article-title":"Asymmetry of the perceptual span in reading","volume":"8","author":"McConkie","year":"1976","journal-title":"Bulletin of the psychonomic society"},{"key":"2022090813571528800_bib17","article-title":"Playing atari with deep reinforcement learning","author":"Mnih","year":"2013","journal-title":"arXiv preprint arXiv:1312.5602"},{"key":"2022090813571528800_bib18","doi-asserted-by":"publisher","first-page":"4586","DOI":"10.18653\/v1\/P19-1451","article-title":"Rewarding Smatch: Transition-based AMR parsing with reinforcement learning","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"Naseem","year":"2019"},{"key":"2022090813571528800_bib19","first-page":"49","article-title":"Memory-based dependency parsing","volume-title":"Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL- 2004) at HLT-NAACL 2004","author":"Nivre","year":"2004"},{"key":"2022090813571528800_bib20","first-page":"96","article-title":"UDAPI: Universal API for universal dependencies","volume-title":"Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017)","author":"Popel","year":"2017"},{"issue":"3","key":"2022090813571528800_bib21","doi-asserted-by":"publisher","first-page":"281","DOI":"10.3758\/BF03200855","article-title":"Regressive eye movements and sentence parsing: On the use of regression-contingent analyses","volume":"22","author":"Rayner","year":"1994","journal-title":"Memory & Cognition"},{"issue":"3\u20134","key":"2022090813571528800_bib22","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1023\/A:1022676722315","article-title":"Q-learning","volume":"8","author":"H. Watkins","year":"1992","journal-title":"Machine learning"},{"key":"2022090813571528800_bib23","unstructured":"Christopher John Cornish Hellaby\n              Watkins\n            \n          . 1989. Learning from Delayed Rewards. Ph.D. thesis, King\u2019s College, Cambridge United Kingdom."},{"key":"2022090813571528800_bib24","first-page":"195","article-title":"Statistical dependency analysis with support vector machines","volume-title":"Proceedings of the Eighth International Conference on Parsing Technologies","author":"Yamada","year":"2003"},{"key":"2022090813571528800_bib25","first-page":"183","article-title":"Approximate dynamic oracle for dependency parsing with reinforcement learning","volume-title":"Proceedings of the Second Workshop on Universal Dependencies (UDW 2018)","author":"Xiang","year":"2018"},{"key":"2022090813571528800_bib26","article-title":"Universal dependencies 2.9","author":"Zeman","year":"2021"},{"key":"2022090813571528800_bib27","doi-asserted-by":"publisher","first-page":"234","DOI":"10.3115\/1697236.1697284","article-title":"Dependency parsing with energy-based reinforcement learning","volume-title":"Proceedings of the 11th International Conference on Parsing Technologies (IWPT\u201909)","author":"Zhang","year":"2009"},{"key":"2022090813571528800_bib28","doi-asserted-by":"publisher","first-page":"562","DOI":"10.3115\/1613715.1613784","article-title":"A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing","volume-title":"Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing","author":"Zhang","year":"2008"},{"key":"2022090813571528800_bib29","first-page":"1391","article-title":"Analyzing the effect of global learning and beam- search on transition-based dependency parsing","volume-title":"Proceedings of COLING 2012: Posters","author":"Zhang","year":"2012"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/tacl\/article-pdf\/doi\/10.1162\/tacl_a_00496\/2042581\/tacl_a_00496.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/tacl\/article-pdf\/doi\/10.1162\/tacl_a_00496\/2042581\/tacl_a_00496.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T13:57:48Z","timestamp":1662645468000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/doi\/10.1162\/tacl_a_00496\/112913\/Dependency-Parsing-with-Backtracking-using-Deep"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":29,"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00496","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022]]},"published":{"date-parts":[[2022]]}}}