Calculating the optimal step of arc-eager parsing for non-projective trees (2021)

Abstract: It is shown that the optimal next step of an arc-eager parser relative to a non-projective dependency structure can be calculated in cubic time, solving an open problem in parsing theory. Applications are in training of parsers by means of a ‘dynamic oracle’.

## introduction a deterministic transition-based dependency parser is often driven by a classifier that determines the next step, given features extracted from the current configuration @xcite . the classifier may be trained on parser configurations and steps that exactly correspond to 'gold' trees from a treebank. however, better accuracy is generally obtained by also including configurations reached by letting the parser stray from the gold trees, to let the classifier learn how best to recover from any mistakes. this is associated with the term dynamic oracle. if the parser is projective while the gold trees are non-projective moreover, then it is unavoidable that configurations be considered that do not correspond to the gold trees. determining the desired output of the classifier requires calculation of the best next step given an arbitrary configuration and a gold tree. typically, this is the step that allows the most accurate tree to be reached, in terms of the gold tree. 1 for a gold tree that is projective, the optimal step can be determined in linear time for arc-eager parsing @xcite and for shift-reduce parsing @xcite . for a nonprojective gold tree, the optimal step can be determined for several types of non-projective parsers (gómez-rodríguez et al., 2014; gómez-rodríguez and fernández-gonzález, 2015; de lhoneux et al., 2017; fernández-gonzález and gómez-rodríguez, 2018), as well as for shift-reduce parsing (nederhof, 2019). however, for arc-eager parsing, the problem has been unsolved until now. aufrant et al. @xcite propose an approximation of the optimal step, based on the procedure for projective gold trees, and demonstrate the advantages of training a projective parser directly on non-projective trees. the current paper introduces an exact calculation of the optimal step for arc-eager parsing and a nonprojective gold tree, within the same framework as @xcite , which consists of a generic cubic-time tabular dependency parsing algorithm and a fixed context-free grammar that is applied on a string extracted from the current configuration, with edge weights determined by the gold tree. for arc-eager parsing, the context-free grammar is considerably more complex than in the case of shift-reduce parsing. this is a consequence of theoretical properties of arc-eager parsing, which we first need to investigate in detail before we can define 'optimality' of the next step. ## dependency structures let @xmath0, which can be words or punctuation. where we use indices between 1 and n, we also refer to these as tokens, relying on the assumption that given an index i we can retrieve the actual token a i . an additional index 0 represents an imaginary token prepended to the sentence. an unlabeled dependency structure t for w is an unlabeled tree with {0, 1, . . . , n} as the set of nodes, of which 0 is the root. we represent such a tree as a set of edges, each represented as a pair (a, b), where index a is the parent and index b is the child. the descendants of a node are the node itself and the descendants of its children. a dependency structure is projective if the set of de-scendants of each node in the tree can be written as {i, i + 1, . . . , j -1, j} for some i and j (0 ≤ @xmath1. we assume each sentence @xmath2. the score of an arbitrary tree t for the same w is defined as |t ∩ t g |. the accuracy of t is its score divided by n. a dependency parser is usually designed to find a tree that is as accurate as possible, given an input sentence. such a parser can generally be extended in a natural way to find a labeled dependency structure, which is analogously defined as a labeled tree with root 0. an edge label in such a structure is called a dependency relation. this paper focuses on unlabeled dependency parsing. ## transition-based dependency parsing transition-based dependency parsing is commonly formalized in terms of a set of configurations and a finite set of transitions between configurations. for now, a configuration for input sentence @xmath3, β, t ), where α is the stack, β is the remaining input, and t is a subset of (the set of edges of) a dependency structure. we assume αβ is a subsequence of 0 1 • • • n, and β is more specifically a suffix of 1 • • • n. a transition is a partial function, mapping one configuration to another. a step is one application of a transition. a computation is a sequence of steps, starting with the initial configuration (0, 1 • • • n, ∅) and ending in a final configuration (0, ε, t ) where ε denotes the empty string; here t is the resulting tree. a transition may have a precondition, i.e. a condition on the current configuration that must hold for the transition to be applicable. unrestricted preconditions are less than convenient for our purposes, and therefore we opt for a more uniform framework, in which a stack element is a pair (a, a) consisting of a token a and a label a taken from a fixed set. 2 to avoid clutter, we write a a in place of (a, a); this also emphasizes the relation to more traditional formulations of dependency parsing, which are obtained by omitting the superscripts. a first illustration of this is traditional shiftreduce dependency parsing, defined by the transitions in there is a simple one-to-one correspondence between a computation according to taking shift-reduce parsing as starting point, reduce right corresponds roughly to left arc, while the role of reduce left is only partly fulfilled by right arc, which postulates that b is a right child of a, but without removing b as yet, allowing b to take right children, and only later is that b removed by reduce. here shift-reduce parsing would postpone the decision whether that b is the left or the right child of its parent until all descendants of b have been shifted and reduced into it. from the perspective of parsing of artificial languages (sippu and soisalon-soininen, 1990), this is counter-intuitive. the conventional wisdom of deterministic parsing is that one should postpone commitment to occurrences of grammar rules (or here, dependency edges) for as long as possible, until enough information is available to resolve any local ambiguity, assuming left-to-right processing of the input string, and the ability to inspect only the top of the stack and the next k tokens of the remaining input, for a fixed, small number k. two arguments have been given why arc-eager parsing is nonetheless superior for processing nat-shift: (α, bβ, t ) sh (αb l , β, t ) left arc: next we rephrase arc-eager parsing to use labels to express preconditions, to prepare us for section 4. note that a token is transferred from the remaining input to the stack by either shift or right arc. in the former case, it must eventually become a left child of its parent, and in the latter case, it becomes a right child. we use labels l and r for these cases. 4 in a configuration with set t as third element, existence of a stack element a l implies a [(a , a) ∈ t ] and a r implies ∃a [(a , a) ∈ t ]. we thereby obtain the first four transitions in arc-eager parsing in either of the above two formulations cannot work in practice. the problem is illustrated in one possible fix is to add the unshift transition of nivre and fernández-gonzález (2014); see also @xcite . as this causes considerable complications to our framework, we will solve this in another way, reminiscent of honnibal et al. @xcite , which also helps to make a connection with shift-reduce parsing later. our proposed fix is to allow a reduce even if the top of stack has label l, by means of the fifth transition of this formulation at first sight appears to nullify the property that has been argued to give arc-eager an advantage over shift-reduce parsing, namely the early availability of edges connecting a parent and a right child. however, these edges are still identified by investigating which tokens in the stack have label r: their parent is the token immediately left to it in the stack. in other words, a classifier predicting the next step can be made to have access to the exact same feature values as before. this formulation of arc-eager parsing, as do the original formulations (goldberg and nivre, 2012, p. 963), allow the same dependency structure to be obtained in two different ways; cf. ## calculating the optimal step assume there are τ transitions, denoted by 1 , . . . , τ . let represent an application of any of these transitions, and let * denote the reflexive transitive closure of . for a given configuration (α, β, t ) for input sentence w with gold tree t g , there are up to τ steps (α, β, t ) i (α i , β i , t i ), @xmath8, . . . , τ . for each of these, the score is the maximal ρ @xmath9, β i , t i ) * (0 r , , t i ) for some t i ; if i is not applicable on (α, β, t ), or if no final configuration is reachable from (α i , β i , t i ), then we set ρ @xmath10. the task is now to compute that ρ i for each i. this determines which transition to apply next, to eventually obtain the highest-scoring tree, irrespective of any 'incorrect' steps performed in the past, that is, steps that were inconsistent with the gold tree. because |t ∩ t g | is the same for all i, and because the value of |t i ∩ t g | ≤ 1 with (α, β, ∅) i (α i , β i , t i ) is easily determined by a single lookup, the remaining problem is to compute the maximal σ @xmath11, β i , ∅) * (0 r , , t i ). as shown by @xcite , the optimal step can be determined in linear time for (uncorrected) arc-eager parsing, provided the gold tree is projective. the procedure is defined in terms of costs of transitions, rather than in terms of scores. we revisit this in section 5. for normalized arc-eager parsing ( now assume the gold tree may be non-projective. for shift-reduce parsing, nederhof (2019) presents a cubic-time algorithm for calculating σ i , generalizing the procedure of @xcite , which is applicable only on projective trees. the algorithm has a modular design, in terms of a generic tabular dependency parsing algorithm @xcite , plus an explicitly 'split' bilexical context-free grammar (eisner and satta, 1999; eisner, 2000; johnson, 2007) that encodes computations of shift-reduce parsing. a given configuration is translated to an input string, and weights between pairs of input positions are set according to existence of edges between corresponding tokens in the gold tree. exhaustive parsing of the string by the grammar, using an appropriate semiring, yields σ i . here we show that the same framework is applicable on arc-eager parsing. the generic tabular dependency parsing algorithm remains the same, but a new grammar is needed to encode computations of arc-eager parsing. following nederhof (2019), nonterminals are either single symbols or pairs of symbols, and rules are of one of the forms: @xmath12, c), (b, c) → a, (b , ) → a (b, ) or ( , c ) → ( , c) a, where a is a terminal. the last two forms are shorthand for any rules obtained by consistent substitution of the two underscores; which symbols can be meaningfully substituted is clear from context, as exemplified below. we start with the normalized form ( grammar for normalized arceager dependency parsing of a string in {r, ℓ} k-1 {r t , ℓ t , ℓ b , n}n m , representing a stack of length k and a remaining input of length m. a label r in the top of stack is translated to r t , and other occurrences of r are translated to r. a label l in the top of stack is translated to ℓ t , unless the candidate transition is left child, in which case it is translated to ℓ b ; other occurrences of l are translated to ℓ. a label n in the top of stack is translated to n. in the stack with label r, where r t specifically means that the token is on top of the stack. rules (3)-(4) distinguish the two cases @xmath13, l} of reduce left with @xmath14. the rules are best read from right to left, as here for example "if the top of stack has label r or l, and if the token underneath has label r, then the latter keeps its label r and becomes the top of stack". rules (5)-(6) allow for reduce left with a right child that was in the remaining input, or that was the top of stack with label n . in (6), the underscore can be substituted by r or r t . in (3)-(5), the only meaningful substitution is by r. rules (10)-( 18 ) are analogous to ( 1 )-( 9 ). rules ( 20 )-( 21 ) allow any projective parse of the remaining input (as well as of the top of stack if that had label n ), and ( 22 )-(24) handle a token in the remaining input taking a left child in the stack, provided it has label l. in (20)-(24), the only meaningful substitution of the underscore is by n . if a token has already been given label l, then it becoming a right child by (4) or (13) amounts to correcting a mistake made earlier, and may be necessary so the computation does not get stuck (cf. unnormalized arc-eager parsing ( we now also need to observe the chosen policy. with the shift-before-reduce policy, if the candidate transition is reduce, then the first symbol of the remaining input becomes n p (p for 'policy'). there is a notable absence of a rule with right-hand side n p (n, ), which means that this token cannot become a left child without first taking a child from the stack as by ( 39 ) and ( 43 ), because if it were, the policy would be violated: the token should have been shifted, and reduced into its parent on the right, preceding the reduce. there is no restriction on the token becoming a right child, as e.g. ## calculation for projective trees if the gold tree is projective, then the problem becomes much easier. here we assume the formulation of arc-eager parsing as in but discounting a number of these, as follows. first, consider the case of the candidate transition being shift. if @xmath16, the score becomes -∞, as there is no available parent for the shifted token. if @xmath17, we discount a possible gold edge (a k , b p ) if the rightmost descendant of b p is b m , because no projective tree exists in which a k is a left child while its descendants include the end of the input. we further discount a possible gold edge with shift-before-reduce, the string does not contain r p or ℓ p , and the first n is replaced by n p if the candidate transition is reduce. second, if the candidate transition is reduce, we discount up to one gold edge in case of the shiftbefore-reduce policy, as follows, and as illustrated by figure 2 . let r be largest such that, for some @xmath18, there is a gold edge (b p , a r ) where a r has label l, or there is a gold edge (a r , b p ); if no such gold edge exists, let @xmath19. if there is no s (@xmath20, a s ) is not a gold edge, then we discount any gold edge (b q , b 1 ). the rationale is that if b 1 can be given a child from among the tokens in the stack (by a gold edge or otherwise, and without discounting another gold edge elsewhere), then this justifies postponing the shift until after the reduce. if it cannot be, then b 1 becoming a left child violates the shift-before-reduce policy. lastly, if the candidate transition is shift, we discount further gold edges in case of the non-strict reduce-before-right policy, which requires a k-1 to either become a child of some b p or take some b p as child, to justify it not having been reduced into a k-2 before the shift. 7 from among the cases to be distinguished, we choose the one that discounts the fewest edges. first, if the label of a k-1 is l, we can let it become a left child, but should then discount a possible gold edge (a k-2 , a k-1 ). second, if there is a gold edge (a k-1 , b p ), then no edges need be discounted. otherwise, we need to find a child b p of a k-1 , for which there are five options, illustrated in figure 3: (a) the first option is applicable if a k has descendants among the remaining input or has a parent b q (@xmath21. in the former case, choose b p to be the rightmost among the descendants (but let @xmath22, and in the latter case choose @xmath23. in effect we assume non-gold edges (a k-1 , b p ) and (b p , a k ), and consequently we discount any gold edge (b q , b p ) and any gold edge to a k . (b1) if a k has a parent b q in the remaining input, choose b p to be b q . in effect we assume non-gold edge (a k-1 , b q ), and consequently we discount any gold edge (a r , b q ) with @xmath24, b q ), as well as any gold edges (b q , a s ) with @xmath25. (b2) if a k does not have a parent in the remaining input, let b q be the token immediately to the right of the rightmost descendant of a k among the remaining input (but let @xmath26, and let @xmath27. as in (b1), we in effect assume non-gold edge (a k-1 , b q ), and discount any gold edge (a r , b q ) with @xmath28, and discussion is omitted for space reasons. ## empirical results the advantage of 'dynamic oracles' for improving parsing accuracy has been demonstrated before. our experiments have therefore concentrated on two obvious questions, viz. whether the cubic-time calculation is feasible in practice, and whether the higher time costs are rewarded with a more accurate output, relative to a linear-time approximation of the kind discussed in section 5. considered here is unnormalized arc-eager parsing. the classifier, implemented in java and dl4j, uses simple features (gold pos of the three rightmost elements of the stack and three leftmost elements of the remaining input, and leftmost and rightmost dependency relations in the topmost two stack elements). the parser was first trained on configurations corresponding to projectivized gold trees from the german (gsd) corpus of universal dependencies v2.2. the trained parser was then applied on the unprojectivized trees, and the optimal step was calculated for each configuration thus visited. ## conclusions our exact calculation of the optimal step solves an open problem in parsing theory. further research into the application of 'dynamic oracles' is needed to determine whether this can be exploited to improve parsing accuracy.