Dependency Parsing with Backtracking using Deep Reinforcement Learning

Dependency Parsing with Backtracking using Deep Reinforcement Learning Franck Dary, Maxime Petit, Alexis Nasr Aix Marseille Univ, Universit´e de Toulon, CNRS, LIS, Marseille, France {franck.dary,maxime.petit,alexis.nasr}@lis-lab.fr Abstract Greedy algorithms for NLP such as transition- based parsing are prone to error propagation. One way to overcome this problem is to al- low the algorithm to backtrack and explore an alternative solution in cases where new evi- dence 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. 1 Introduction Transition-based parsing has become a major ap- proach in dependency parsing, since the work of Yamada and Matsumoto (2003) and Nivre et al. (2004), for it combines linear time complexity and high linguistic performances. The algorithm follows a local and greedy approach to parsing that consists of selecting at every step of the parsing process the action that maximizes a lo- cal score, typically computed by a classifier. The action selected is greedily applied to the cur- rent configuration of the parser and yields a new configuration. At training time, an oracle function transforms the correct syntactic tree of a sentence into a sequence of correct (configuration, action) pairs. These pairs are used to train the classifier of the parser. The configurations that do not pertain to the set of correct configurations are never seen during training. At inference time, if the parser predicts and executes an incorrect action, it produces an in- correct configuration, with respect to the sentence being parsed, which might have never been seen during training, yielding a poor prediction of the next action to perform. Additionally, the parser follows a single hypothesis by greedily selecting the best scoring action. The solution built by the parser can be sub-optimal for there is no guarantee that the sum of the scores of the actions selected maximizes the global score. These are well-known problems of transition- based parsing and several solutions have been proposed in the literature to overcome them, they will be briefly discussed in Section 2. The solution we propose in this article consists of allowing the parser to backtrack. At every step of the parsing process, the parser has the opportunity to undo its n previous actions to explore alternative solutions. The decision to backtrack or not is taken each time a new word is considered, before trying to process it, by giving the current configuration to a binary classifier, that will assign a score to the back- tracking action. Traditional supervised learning is not suited to learn such a score, since the training data contains no occurrences of backtrack actions. In order to learn in which situation a backtrack action is worthy, we use reinforcement learning. During training, the parser has the opportunity to …

Content truncated to 500 words