Tackling Error Propagation through Reinforcement Learning: A Case of Greedy Dependency Parsing

Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 677–687, Valencia, Spain, April 3-7, 2017. c⃝2017 Association for Computational Linguistics Tackling Error Propagation through Reinforcement Learning: A Case of Greedy Dependency Parsing Minh Lê CLTL Vrije Universiteit Amsterdam Amsterdam, The Netherlands m.n.le@vu.nl Antske Fokkens CLTL Vrije Universiteit Amsterdam Amsterdam, The Netherlands antske.fokkens@vu.nl Abstract Error propagation is a common problem in NLP. Reinforcement learning explores erroneous states during training and can therefore be more robust when mistakes are made early in a process. In this paper, we apply reinforcement learning to greedy dependency parsing which is known to suffer from error propagation. Reinforce- ment learning improves accuracy of both labeled and unlabeled dependencies of the Stanford Neural Dependency Parser, a high performance greedy parser, while maintaining its efficiency. We investigate the portion of errors which are the result of error propagation and confirm that rein- forcement learning reduces the occurrence of error propagation. 1 Introduction Error propagation is a common problem for many NLP tasks (Song et al., 2012; Quirk and Corston- Oliver, 2006; Han et al., 2013; Gildea and Palmer, 2002; Yang and Cardie, 2013). It can occur when NLP tools applied early on in a pipeline make mistakes that have negative impact on higher-level tasks further down the pipeline. It can also occur within the application of a specific task, when se- quential decisions are taken and errors made early in the process affect decisions made later on. When reinforcement learning is applied, a sys- tem actively tries out different sequences of ac- tions. Most of these sequences will contain some errors. We hypothesize that a system trained in this manner will be more robust and less susceptible to error propagation. We test our hypothesis by applying reinforce- ment learning to greedy transition-based parsers (Yamada and Matsumoto, 2003; Nivre, 2004), which have been popular because of superior effi- ciency and accuracy nearing state-of-the-art. They are also known to suffer from error propagation. Because they work by carrying out a sequence of actions without reconsideration, an erroneous ac- tion can exert a negative effect on all subsequent decisions. By rendering correct parses unreach- able or promoting incorrect features, the first error induces the second error and so on. McDonald and Nivre (2007) argue that the observed negative correlation between parsing accuracy and sentence length indicates error propagation is at work. We compare reinforcement learning to super- vised learning on Chen and Manning (2014)’s parser. This high performance parser is available as open source. It does not make use of alterna- tive strategies for tackling error propagation and thus provides a clean experimental setup to test our hypothesis. Reinforcement learning increased both unlabeled and labeled accuracy on the Penn TreeBank and German part of SPMRL (Seddah et al., 2014). This outcome shows that reinforce- ment learning has a positive effect, but does not yet prove that this is indeed the result of reduced er- ror propagation. We therefore designed an …

Content truncated to 500 words