Generic Oracles for Structured Prediction (2021)

Abstract: When learned without exploration, local models for structured prediction tasks are subject to exposure bias and cannot be trained without detailed guidance. Active Imitation Learning (AIL), also known in NLP as Dynamic Oracle Learning, is a general technique for working around these issues by allowing the exploration of different outputs at training time. AIL requires oracle feedback: an oracle is any algorithm which can, given a partial candidate solution and gold annotation, find the correct (minimum loss) next output to produce. This paper describes a general finite state technique for deriving oracles. The technique describe is also efficient and will greatly expand the tasks for which AIL can be used.

## introduction structured prediction tasks, e.g., pos tagging, machine translation or syntactic parsing, are central to nlp and are commonly solved with machine learning based models. there are two main ways of approaching these problems: in one, a model scores fragments of possible outputs and an efficient decoding algorithm finds the highest scoring solution, e.g., using conditional random fields and the forward-backward algorithm. in the second approach a model produces an output through a sequence of decisions, each extending a partial output produced by the previous steps, e.g., picking one word after the other in a sequence to sequence translation system or repeatedly splitting a sentence into constituents. modern neural models use complex hidden states to express the interdependence between outputs, making efficient decoding difficult and the latter approach ever more important. when training models to make sequential decisions it is necessary to provide guidance on which actions to take to achieve minimum loss against a gold output. sometimes there is a clear sequence of correct actions, e.g., when learning to translate or tag, there is the option of simply training the model to follow the gold annotation, which corresponds 1-1 to possible model outputs. ## formal background before we describe our approach, we will recap some of the theory of ail and finite state machines. through a detailed discussion of both topics in a shared vocabulary, the connection will become clearer. we use the task of mapping sentences to parse trees as our running example. ## finite state automata oracles we now provide generic dynamic oracles, prove the soundness of our constructions and provide complexity upper-bounds. we will encode all the possible action sequences for a given imitation learning problem as an automaton and then retrieve the next transition in a minimum loss complete solution for a given prefix. the key question is how to derive an automaton of losses from a problem instance without having to explicitly go through all possible action sequences. in order to do this, we need three requirements guaranteeing applicability of finite-state techniques. first, we must be able to build a decomposition automaton inverting the interpretation function, and its language must not be empty. second, we must be able to approximate the loss function with a transducer working over action sequences. third, there must be an automaton recognizing the set of admissible candidate output action sequences for the considered input. these requirements are formally captured by the following definitions. definition 7. x, g, • has a decomposable gold annotation if the set g -1 = {α ∈ o * | α = g} is both regular and non-empty. an automaton recognising this set is called a decomposition automaton. in our constituency parsing example, the decomposition automaton for a tree is simply the automaton that accepts the bracketing for the tree, e.g., the one recognizing "s( john vp( hit np( the ball ) ) )" for the tree in fig. 1 . the automaton recognizing this sequence would have positions in the gold output as states and would have transitions such as 1, john, 2 or 2, v p (, 3 with weight 0. for machine translation the decomposition automaton may recognize any of a number of possible gold translations. note that our notion of "decomposable" is unrelated to the notion of "arc-decomposable" used in previous research on oracles for dependency parsing. our notions of decomposability is concerned with decomposing every possible way of arriving at the gold output into a sequence of actions, while arc-decomposability tells us about the interaction between added edges during dependency parsing. definition 8. we say that l is decomposable if there exists a transducer t such that for any instance x, g, • ∈ p and sequences α, α , β ∈ o * , if l( α , β ) < l( α , β ), then there exists β ∈ o * such that β = β and t (α , β ) < t (α, β). definition 8 relates the transducer and loss function with an inequality, not an equality. this provides more flexibility: we do not require that the loss function be directly computed by a transducer. if we did, then that would rule out very common losses such as f-score. rather, we allow transducers which conserve the right minima (see lemma 3 below). variations of the levenshtein edit-distance between the output and gold-sequence are expressible as a (single state) transducer, and provides a generic loss function in practical cases. consider our example of constituency parsing: the f-score is the harmonic mean of two measures that require division by the total count of constituents present in a prediction and is hard to express as a transducer. however, as shown by @xcite , for purposes of an oracle, the number of incorrectly inserted and missing brackets (which corresponds to the edit distance between input and output for our setting) fits definition 8 and can thus replace a loss based on the f-score. an incorrectly inserted bracket will always reduce precision without changing recall and vice versa for dropping a bracket. for our example problem the transducer would have have transitions 0, x, x, 0 with weight 0, which map every symbol to itself, transitions 0, x(, , 0, 0, , x(, 0 and 0, y (, x(, 0 which allow us to delete, insert, or relable any opening brackets x(, y ( with weight 1, as well as transitions 0, x), , 0 and 0, , x), 0 with weight 0. foot_3 the next lemma states that for any set of action sequences, the input action sequence assigned minimum weight by some decomposition transducer is indeed a minimum loss action sequence out of that set. lemma 3. let l be decomposable, x, g, • ∈ p , and t be as described in definition 8. for any subset d ⊆ o * , if α ∈ arg min α∈d min β, β =g t (α, β), then α ∈ arg min α∈d l( α , g) proof. let α ∈ arg min α∈d min β, β =g t (α, β) and β ∈ arg min β =g t (α, β). if there existed α ∈ d such that l( α , g) < l( α , g), it would follow from definition 8 that ∃β , β = β = g and t (α , β ) < t ( α, β), which contradicts the definition of α. hence α ∈ arg min α∈d l(α, β). finally, we need to add the regularity of the possible action sequences: definition 9. we say that x has regular constraints iff τ x is regular. for our context free parsing example, all the possible parses for a sentence can be expressed in a finite state automaton by virtue of the fact that any finite language is regular. we obtain an automaton of size o(n 2 ) for an input of length n, when we construct states that encode how many brackets are open and which word was last produced. we would have a state (3, c, t), which would be reached after producing, e.g., ((a(bc for the input sentence abcd. t and f would be use to indicate whether we can still produce closing brackets before outputting the next word, to prevent outputs like @xcite . we would allow, e.g., a transition of the form (3, c, t), ), (2, c, t). note that we only need to maintain numbers up to the length of the inputs sentence, since no more can be used in a permissible parse for the input. our construction for the action sequence automaton allows for unary bracketings, but since they do not occur in the gold output and would always incur additional loss, this will not constitute a difficulty. from here on, we assume x, g, • to be an instance with both decomposable gold annotation and regular constraints, and l to be a decomposable loss function. we now proceed to a first oracle construction which follows naturally from these assumptions and some of the properties of finite state machines listed in section 2. let α ∈ o * represent a sequence of k actions that the model has already taken. we can find an optimal action for the next step: consider an arbitrary candidate action @xmath0, among the possible choices for o, is part of the minimum loss completion of α into an admissible action sequence. letting (for any action sequence γ) cont γ = {γ ∈ τ x | γ ≥ γ} denote the set of admissible continuations of γ, we can formally rephrase our objective as choosing an action o minimizing the quantity min α ∈contα•o l( α , g). to ease notational clutter, let us define l(α ) = min β ∈ g -1 t (α , β ). observe that lemma 3 ensures that we solve the oracle task if we find õ ∈ arg min @xmath1. for if we find such õ, letting α ∈ arg min α ∈contα•o l(α ), we have α ∈ arg min α ∈contα l(α ) (easily checked from the definition of õ). then, from lemma 3 follows that α ∈ arg min α ∈contα l( α , g), which (since α ∈ cont α•õ ) finally shows that õ is one of the optimal choices for continuing α, i.e. õ ∈ arg min @xmath2, g). how can we compute this quantity? we first build an automaton a α•o which recognizes the set α • o • o * . this is easily done as depicted below, with the following graphical conventions: states are circled, the start state (0) is marked with a left-dangling incoming arrow, arrows between states represented transitions, annotated with their label(s) and weight (a set of labels like o is a factored representation of one transition for each @xmath3, all with the same indicated weight), and final weights are given by the downwards outgoing arrows. in our example setting, this would be an automaton that accepts the brackets and word tokens produced so far, followed by all possible words and brackets and which assigns weight 0 to each of those transitions. let c x be an automaton recognizing the set τ x of admissible actions for x (c x exists since x has regular constraints). in our example this would be an automaton that accepts all the valid bracketings of the input. note that this can be represented as a finite state automaton, due to the limit on open brackets we stipulated. observe that c x ∩ a α•o (as provided by lemma 1) recognizes cont α•o . let now t be the transducer provided by definition 8, and d g be a decomposition automaton for g. consider the transducer by two successive applications of lemma 1), and let q 0 be its initial state. with a little work (we skip the details here, due to space limitations), one can show that if β / ∈ g -1 or α / ∈ cont α•o then t α•o (α , β ) = +∞, and that otherwise t α•o (α , β ) = t (α , β ). this guarantees: equation ( 1 ) and preceding observations establish the soundness of the following oracle computation: find and output the action o minimizing v tα•o (q 0 ). in terms of our example, this would mean taking the automaton that expresses all possible continuations of a partial parse and intersecting it with the automaton of all possible bracketings of the input. then we apply a transducer that encodes the edit distance to the gold bracketing and extract the shortest path from the resulting automaton we now briefly discuss the complexity of a single call to this oracle, and of a sequence of prediction, at each timestep of an input's processing. recall that @xmath4. let m t , m g and m x denote the number of states of t , d g and c x resepectively, and e t , e g , e x their respective number of finite-weight transitions. we consider the size of the alphabet o constant and exclude it from the underlying variables of all the asymptotic bounds reported. by lemma 1, computing and is asymptotically the dominant term. iterating (a constant number of times) over @xmath5 if a machine learning system builds and outputs a (complete) sequence of n actions in processing (entirely) a given input x, and needs to call the oracle at each timestep @xmath6, n] (i.e., there is a call on each prefix of length k of the complete action sequence), the overall cost of oracle calls in the processing of x will then be o(n 3 (m g m t m x e g e t e x )). if no negative weights are involved, this can be lowered to this is extremely suboptimal, because the algorithm discussed above is only superficially dynamic: at every timestep, an independent computation arises with redundant work all the way up to the prefix α of previous actions disregarding the result of previous timesteps' computations. in fact, shortest path computations can be performed in advance. to this aim, we can work with @xmath7, a transducer that combines the automaton of all possible input sequences with the decompositions of the gold output. this transducer is only dependent on the problem and the loss function, hence only needs to be computed once, at the time the corpus is created. we can use the following observation: when we start producing the output sequence, the best action is the first action of the best path from t 's start state q 0 . after outputting an action a, we can obtain a set c of states in t that are reachable by reading a from q 0 . the best next action must then be the first action of some path from some state @xmath8, which is determined according to the cost of reaching q through a plus the weight of the best path from q . this updating can be carried forward during the whole decoding process. this frees us from having to repeat a lot of computation, as we will see that we only need to compute the best paths in t once. to formalize this: let @xmath9, q, o, o, δ, ρ , then let pre α (q ) = min β∈o * δ * (q 0 , α, β, q ), the minimum weight of a path reaching q from the start state with α. using eq. ( 2 ), we have finally, since by construction t (α , β ) = +∞ entails β = g, it is sufficient to find to solve the oracle problem for prefix α. our second construction thus proceeds as follows: second oracle computation for α. when constructing the problem, compute v t for each instance. during iteration, to obtain the optimal next action @xmath10, choose the minimum of pre α•o (q ) + v t (q ). what we gain from this obviously depends on the cost of computing pre α (q ) for every state q . the key insight is that pre α•o can be computed inductively from pre α : obverse that in the second equality above, the quantity min q min p δ(q , o, p, q ) + δ * (q , , β , q ) depends only on t , the states q and q , and not on the prefix α. we thus refer to this quantity as c(q , q ). since it does not depend on α, it can be precomputed once for every pair q , q , and reused through every iteration. the cost of this precomputation is asymptotically bounded by o(|q| 3 ): the lion's share is computing a table for the (lhs) epsilon closure δ * (q , , β , q ), for all pairs q , q . this is an instance of an all-pair shortest-path problem and solved with the floyd-warshall algorithm @xcite . this is also akin to considering t has an automaton rather than a transducer, using only the 'input' side (lhs) of transitions, and eliminating transitions. note in passing, that computing pre is a similar problem and therefore done with the same asymptotic bound. because pre α•o can be computed inductively, it is possible to update it as the dagger algorithm is going through a problem instance computing first pre , and then updating by taking a minimum over all possible transitions for the next action produced. the induction step then computes pre α•o (q ) from the different pre α (q ) and c(q , q ) in o(|q| 2 ) (since for each entry q we need to range over all q ). this could be reduced to constant time by looking just at the inputs of t and making the induced automaton deterministic @xcite , however, that would come at the cost of a worst-case exponentially larger precomputation. we now turn to the complexity analysis of the refined oracle construction. computing v t is the only precomputation that we have not yet addressed, and can be achieved in time o(|q||δ|) before any dagger iterations. we can bound this with o(|q| 3 ) as well. oracle calls will receive a (possibly empty) prefix of the form α. to compute the oracle we have to compute pre α•o from pre α , which will cost o(|q| 2 ) for a nondeterministic automaton, and then compute the minimum in equation (3). hence, over a sequence of n actions with oracle calls in one entire pass over input x in dagger, the total cost of oracle calls will be bounded by o(|q| 3 + n|q| 2 ), or with the same notations as before o((m x m g m t ) 3 + n(m x m g m t ) 2 ). holding other parameters fixed, our second construction is much more efficient with respect to n, the length of the input. we can therefore conclude that our second construction is much more efficient during the actual dagger training steps, with most of the computation moved into preprocessing, which is only needed once during the lifetime of a corpus. applied to our context free parsing example, our analysis bounds an oracle call (and update of pre) with o(n 6 ). the precomputation is bounded by o(n 9 ), and the total of oracle calls in building a complete output is bounded with o(n foot_4 ). however, we used here a generic bound that will hold for all instances of our method. no assumption were made on the nature of the automata involved 7 , and specific instances will allow more efficient implementation of automata-theoretic operations, with no change to the general framework. we leave discussion of the automata theoretic properties that enable more efficient oracles for future work. ## related work our dynamic oracle construction is general and only takes limited bookkeeping as seen in the previous section. however, this computation can still be costly and one topic in existing imitation learning is avoiding oracles computations where possible. a recent approach uses statistical techniques for the so called task of apple tasting to learn when it is necessary to call to an expensive oracle and when it is possible to instead use a cheap heuristic @xcite . we could implement trans-ducer application and other computations on the finite state automata in a lazy manner and avoid oracle computations in order to save on computations for the automata and for tracking shortest paths. other work uses reinforcement learning in order to derive approximate oracles @xcite . by using reinforcement learning to replace many of the oracle evaluation, it would also be possible to save on automaton construction. the finite state approach we have sketched can give us an optimal action to take next. while this is sufficient to implement active imitation learning with a technique like dagger, in some settings it can be beneficial to use not just information on what the best next action is, but rather to obtain the minimum loss for every available action in a given state @xcite and to then train a loss aware classifier. as we are already computing these quantities, our algorithms would also suitable for this setting. related dynamic oracles there are a number of previously published oracles that are related to our setting, even if they proceed slightly differently. they are particularly used for dependency or constituency parsing. note that our approach for constructing an automaton expressing the loss for all possible continuations could be applied to setting where the output is produced in a fashion other than left to right. assume, e.g., that we use an algorithm which produces parse trees by "splitting" a sentence into sub-sequences repeatedly as in @xcite . let the output generated to far be s(np(the old baker)vp(uses a sharp knife)). we would then simply construct an automaton equivalent to the regular expression through application of the loss transducer approximating the loss for all possible action sequences, we could retrieve the minimum loss continuation. we leave work on whether this construction allows for more efficient look-up to future work. a predecessor of the work by @xcite is the paper by @xcite which discusses a shift-reduce system for constituency parsing and gives a constant time dynamic oracle for this system. it would be possible to express their setting, as well as those of @xcite , @xcite and the discourse parsing focused on of hung et al. (2020) in our framework. dynamic oracles have also been developed for different formalizations of the dependency parsing problem @xcite for shift reduce parsing. for the projective setting, one could generalize these oracles by translating dependency tree to constituency trees @xcite or tag sequences @xcite . oracles for non-projective dependency and constituency parsing @xcite @xcite @xcite can in certain cases be computed in polynomial time, but would be harder to express in this framework without necessitating extremely large automata as it would be difficult to encode the different admissible sets of actions. our idea of using interpretations of action sequences is inspired by interpreted regular tree grammars (irtgs) @xcite . our approach works in terms of automata over string sequences and irtgs are based on automata over trees. in future work we will use irtgs to extend our approach to additional domains. ## conclusion this paper gives a generic approach for deriving dynamic oracles for nlp. the oracles make it possible to implement error aware learning and learning in ambiguous environments for a wide range of nlp problems, including most problems that can be approached with sequence to sequence models. there is no need to derive new oracles for every new loss or set of output actions, instead automata can be derived once and reused if only part of a problem changes. we also showed how to substantially improve the efficiency of oracle lookup, by moving most computational cost into a one time pre-computation.