Dependency Parsing with Backtracking using Deep Reinforcement Learning (2022)

Abstract: 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.

## introduction transition-based parsing has become a major approach in dependency parsing, since the work of @xcite and @xcite , 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 local score, typically computed by a classifier. the action selected is greedily applied to the current 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 incorrect 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 transitionbased 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 backtracking 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 try backtracking actions and the training algorithm responds to this choice by granting it a reward. if the backtracking action is the adequate move to make in the current configuration, it will receive a positive reward and the parser will learn in which situation backtrack is adequate. the work presented here is part of a more ambitious project which aims at modeling eye movements during human reading. more precisely, we are interested to predict regressive saccades: eye movements that bring the gaze back to a previous location in the sentence. there is much debate in the psycholinguistic literature concerning the reasons of such eye movements @xcite . our position with respect to this debate is the one advocated by @xcite , for whom part of these saccades are linguistically motivated and happen in situations where the reader's incremental comprehension of the sentence is misguided by an ambiguous sentence start, until reaching a novel word which integration will prove incompatible with the current understanding and will trigger a regressive saccade, as in garden path sentences. our long-term project is to model regressive saccades with backtracking actions. although this work enters in this long-term project, the focus of this article is on the nlp aspects of this program and we propose a way to implement backtracking in the framework of transition-based parsing. we will just mention some preliminary studies on garden path sentences in the conclusion. in order to move in the direction of a more cognitively plausible model, we add two constraints to our model. the first one concerns the text window around the current word that the parser takes into account when predicting an action. this window can be seen as an approximation of the sliding window introduced by @xcite to model the perceptual span of a human reader. 1 transition-based parsers usually allow taking into account the right context of the current word. the words in the right context constitute a rich source of information and yield better predictions of the next action to perform. in our model, the parser does not have access to this right context, simulating the fact that a human reader has only a limited access to the right context (few characters to the right of the fixation point @xcite ). it is only after backtracking that a right context is available for it has been uncovered before backtrack took place. the second constraint is incrementality. when performing several tasks, such as pos tagging and parsing, as will be done in the tagparser described in section 3, these tasks are organized in an incremental fashion. at each step, a word is read, pos tagged, and integrated in the syntactic structurea more cognitively plausible behavior than a sequential approach where the whole sentence is first pos tagged then parsed. the structure of the paper is the following: in section 2, we compare our work to other approaches in transition-based parsing which aim at proposing solutions to the two problems mentioned above. in section 3, we describe the model that we use to predict the linguistic annotation and 1 it is actually a rough approximation of the sliding window because it defines a span over words and not characters. ## related work several ways to overcome the two limits of transition-based parsing mentioned in the introduction, namely, training the parser with only correct examples and exploring only a single hypothesis at inference time, have been explored in the literature. ## backtracking reading machines our model is an extension of the reading machine, a general model for nlp proposed in @xcite that generalizes transition-based parsing to other nlp tasks. a reading machine is a finite automaton whose states correspond to linguistic levels. there can be, for example, one state for pos tagging, one state for lemmatization, one state for syntactic parsing, and so on. when the machine is in a given state, an action is predicted, which generally writes on an output tape a label corresponding to the prediction just made. 2 there are usually as many output tapes as there are levels of linguistic predictions and at least one input tape that usually contains the words of the sentence to process. 3 predictions are realized by classifiers that take as input the configuration of the machine and compute a probability distribution over the possible actions. configurations are complex objects that describe the aspects of the machine that are useful in order to predict the next action to perform. among the important elements of a configuration for the rest of the paper, we can cite the current state of the machine, the word index (noted as wi) that is the position of the word currently processed, and the history, a list of all actions performed so far. the text is read word by word, a window of an arbitrary size centered on wi defines the part of the text that can be used to make predictions on the current word. figure 1 shows the architecture of three simple machines. the two machines in the top part of the figure realize a single task. the machine on the left part realizes pos tagging. it is made of a single state and has a series of transitions that loop on the state. the machine has one input tape from which words are read and one output tape, on which predicted pos are written. each transition is labeled with a tagging action of the form pos(p) that simply writes the pos tag p on the pos output tape at the word index position. the machine on the right implements an arceager transition-based parser that produces unlabeled dependency trees. it has the same simple structure than the tagging machine. its transitions are labeled with the four standard arc-eager actions of unlabeled transition-based parsing: left, reduce, shift, and right. the machine has two input tapes, one for words and one for pos tags, and one output tape on which it writes the index of the governor of the current word when left or right actions are predicted. the machine on the bottom part of the figure, which we call a tagparser, realizes the two tasks simultaneously in an incremental fashion. when in state pos, the machine tags the current word then control jumps to the parser in order to attach the current word to the syntactic structure built so far or to store it in a stack. once this is done, control returns to state pos to tag the next word. the reason why the transitions labeled right and shift lead to state pos is that these two actions increase the word index wi and initiate the processing of a new word. the machine has one input tape for words and two output tapes, one for pos tags and one for the governor position. we augment the machines described above in order to allow them to undo some preceding actions. this ability relies on three elements: (a) the definition of a new action, called back, that undoes a certain number of actions; (b) the history of the actions performed so far in order to decide which actions to undo; and (c) the definition of undoing an action. undoing an action amounts to recovering the configuration that existed before the action was performed. this is quite straightforward for tagging and parsing actions. 4 three backtracking machines, based on the machines of figure 1 , are shown in figure 2 . they all have an extra state, named back, and two extra transitions. when in state back, the machine predicts one of the two actions back or ¬back. when action ¬back is selected, control jumps either to state pos or syn, depending on the machine, and the machine behaves like the simple machines of figure 1 . action ¬back does not modify the configuration of the machine. this is not the only possible architecture for backtracking machines, this point will be briefly addressed in the conclusion. if action back is selected, the last actions of the history are undone until a ¬back action is reached. this definition of action back allows undoing all actions that are related to the previous word. after back has been applied, the configuration of the machine is almost the same as the configuration it was in before processing the current word. there is, however, a major difference: it now has access to the following word. otherwise, the machine would deterministically predict the action it has predicted before. one can notice that the transition labeled back in the machine loops on a single state, this feature allows the machine to perform several successive back actions. figure 3 shows how the tagparsing machine of figure 2 would ideally process the sentence the old man the boat, a classical garden path sentence for which, two words (old and man) should be re-analyzed after the noun phrase the boat has been read. the figure describes the machine configuration each time it is in state back. three tapes are represented: the input tape that contains tokens, figure 3 : processing the garden path sentence the old man the boat with a bactracking tagparser. after reading the second determiner, the machine backtracks in order to reanalyze words old and man. the pos tape, and the parsing tape that contains the index of the governor of the current word. the figure also represents, at the bottom, the ba array, which is described below, as well as the sequence of actions predicted since the last visit to state back. the current word appears in boldface. the figure shows two successive occurrences of a back action, after the second determiner is read, leading to the re-analysis of the word old that was tagged adj and the word man that was tagged noun. a backtracking machine as the one described above can run into infinite loops: nothing prevents it to repeat endlessly the same sequence of actions. one can hope that, during training, such behavior leads to poor performance and is ruled out. but there is no guarantee that this will be the case. furthermore, we would like to prevent the machine for exploring, at inference time, the whole (or a large part of the) configuration space. in order to do so, we introduce a constraint on the number of times a back action is taken when parsing a sentence. a simple way to introduce such a constraint is to limit to a given constant k the number of authorized back actions per word. this feature is implemented by introducing an array ba of size n, where n is the number of words of the sentence to process. array ba is initialized with zeros, and every time a back action is predicted in position i, the value of ba[wi] is incremented. when the machine is in state back and ba[wi] is equal to k, performing a back action is not permitted. a ¬back action is forced, bypassing the classifier that decides whether to backtrack or not. the introduction of array ba and the parameter k defines an upper bound on the size of the action sequence for a sentence of length n. this upper bound is equal to 3nk + 2n for the tagger, 4nk + 3n for the parser, and 5nk + 4n for the tagparser. 5 as one can notice, linearity is preserved. in our experiments, we chose @xmath0. ## training reading machines, as introduced by @xcite , are trained in a supervised learning fashion. given data annotated at several linguistic levels, an oracle function decomposes it into a sequence of configurations and actions (c 0 , a 0 , c 1 , a 1 , . . . , c n , a n ). this sequence of configurations and actions constitute the training data of the classifiers of the machine to train: pairs (c i , a i ) are presented iteratively to the classifier during the training stage. a backtracking reading machine cannot be trained this way since there are no occurrences of back actions in the data. in order to learn useful occurrences of such actions, the training process should have the ability to generate some back actions and be able to measure if this action was beneficial. in order to implement such a behavior, we use reinforcement learning (rl). we cast our problem as a markov decision process (mdp). in an mdp, an agent (the parser) is in configuration c t at time t. it selects an action a t from an action set (made of the tagging actions, the parsing actions and the back and ¬back actions) and performs it. we note c the set of all configurations and a the set of actions. the environment (the annotated data) responds to action a t by giving a reward r @xmath1, a t ) and by producing the succeeding configuration c t+1 = δ(c t , a t ). in our case, configuration c t+1 is deterministically determined by the structure of the machine. the reward function gives high 5 see appendix a for details. given an mdp that indicates the reward associated to applying action a in configuration c, the goal is to learn a function q * (c, a) that maximizes the total amount of reward (also called discounted return) that can be expected after action a has been applied. once this function (or an approximation of it) is computed, one can use it to select which action to choose when in configuration c, by simply picking the action that maximizes function q * . such behavior is called an optimal policy in the rl literature. function q * is the solution to the bellman optimality equation. foot_4 it has been proven @xcite that such iterative algorithm converges towards the q * function. in order to store the values of q, the algorithm uses a large table that has an entry for every (configuration, action) pair. in our case, there are far too many configurations to allocate such a table. instead we use a simple form of deep q learning @xcite and approximate function q using a multilayer perceptron c q . c q takes as input a configuration c and outputs a vector whose dimension is the number of different actions in the action set. the component of the vector corresponding to action a is the approximation of q(c, a) computed by c q . it is noted c q (c, a). during training, every time an action a is performed by the parser in configuration c, the parameters of c q are updated using gradient descent of the loss function. the loss function should be defined in a way to minimize the difference between the actual value c q (c, a) and its updated value c q (c, a). this difference is computed with the smooth l1 loss @xcite : reward functions in rl, the training process is guided by the reward r(c, a) granted by the environment when action a is performed in configuration c. defining a reward function for tagging action and parsing action is quite straightforward. in the case of tagging, the reward should be high when the tag chosen for the current word is correct and low when it is not. a simple reward function is one that associates, for example, value 0 in the first case and -1 in the second. more elaborate reward functions could be defined that penalize more some confusions (e.g., tagging a verb as a preposition). in the case of parsing, a straightforward reward function will give a reward of zero for a correct action and a negative reward for an incorrect one. we use a slightly more complex function inspired by the dynamic oracle of @xcite . this function, in the case of an incorrect action a, counts the number of dependencies of the correct analysis that cannot anymore be predicted due to a. the reward for a is the opposite of this number. actions that cannot be executed, such as popping an empty stack, are granted a reward of -1.5. defining the reward function for back actions is more challenging. when a back action is performed, a certain number of actions a i . . . a i+k are undone. each of these actions was granted a reward r i . . . r i+k . let's call @xmath2. the larger e is, the more errors have been made. let's call ϕ(e) the function that computes the reward for executing a back action, given e. formally, we want ϕ to respect the following principles: ## experiments three machines were used in our experiments: a tagger, a parser and a tagparser, based on the architectures of figure 2 . each of the three machines has been trained in three different learning regimes: supervised learning (sl) using a dynamic oracle, reinforcement learning without back actions (rl), and reinforcement learning with back actions (rlb). ## conclusions we have proposed, in this article, an extension to transition-based parsing that consists of allowing the parser to undo the last actions performed in order to explore alternative hypotheses. we have shown that this kind of model can be effectively trained using deep reinforcement learning. this work will be extended in several ways. the first concerns the disappointing results of the tagparser. as already mentioned in section 4, many studies have shown that there is usually an advantage to jointly predict several types of linguistic annotations over predicted them separately. we did not observe this phenomenon in our backtracking tagparser. the problem could come from the structure of the backtracking machines. the structures used, illustrated in figure 2 , are just one possible architecture, others are possible, as for example dedicating different back states for the parser and the tagger. the second direction concerns the integration of other nlp tasks in a single machine. @xcite showed that reading machines can take as input raw text and realize word segmentation, pos tagging, lemmatization, parsing, and sentence segmentation. we would like to train such a complex machine with reinforcement learning and backtracking to study whether the machine can backtrack across several linguistic levels. a third direction concerns the processing of garden path sentences. such sentences offer examples in which we expect a backtracking machine to backtrack. we have built a corpus of 54 garden path sentences in french, using four different syntactic patterns of different complexity level and organized the sentences in minimal pairs and have tested our machine on it. the results are mixed; in some cases, the machine behaves as expected, in other cases it does not. a detailed analysis showed that the machine usually backtracks on garden path sentences but has a tendency of not reanalyzing the sentence as was expected. the problem seems to be of a lexical nature. some words that should be attributed new pos tags in the reanalysis phase resist this reanalysis. this is probably due to their lexical representation. more work is needed to understand this phenomenon and find ways to overcome it. the last direction is linked to the long-term project of predicting regressive saccades. the general idea is to compare back movements predicted by our model and actual eye movement data and study whether these movements are correlated.