Max-Margin Incremental CCG Parsing (2020)

Abstract: Incremental syntactic parsing has been an active research area both for cognitive scientists trying to model human sentence processing and for NLP researchers attempting to combine incremental parsing with language modelling for ASR and MT. Most effort has been directed at designing the right transition mechanism, but less has been done to answer the question of what a probabilistic model for those transition parsers should look like. A very incremental transition mechanism of a recently proposed CCG parser when trained in straightforward locally normalised discriminative fashion produces very bad results on English CCGbank. We identify three biases as the causes of this problem: label bias, exposure bias and imbalanced probabilities bias. While known techniques for tackling these biases improve results, they still do not make the parser state of the art. Instead, we tackle all of these three biases at the same time using an improved version of beam search optimisation that minimises all beam search violations instead of minimising only the biggest violation. The new incremental parser gives better results than all previously published incremental CCG parsers, and outperforms even some widely used non-incremental CCG parsers.

## introduction it has been known for a long time that human sentence processing is highly incremental @xcite , with early formation of semantic representations. a parser that is able to form representation early must have some notion of partial structure such as "s missing an object np". also, such parser needs to be able to combine partial structures into bigger partial structures. these two properties are at the core of combinatory categorial grammar (ccg) @xcite . ccg represents partial constituents using complex categories. for example s/np is the category of a transitive sentential prefix such as i like or i think i like requiring an object np on its right. such prefix categories are constructed using combinatory rules such as function composition. in this way we can form (mostly) left-branching derivation trees that can be parsed incrementally even with simple transition mechanisms such as shift-reduce parsers. still, left branching structures are not sufficient to solve all the problems of incremental sentence processing. right adjuncts are particularly problematic. they appear on the right of the head that they modify which means that they need to be predicted, but at the same time they are optional which makes it impossible to predict them with confidence. @xcite tackle this issue by using incremental tree-rotation and revealing operations that allow adjuncts not to be predicted, but still be easy to attach to the head in case they appear. they show great improvement in the incrementality of this approach as measured by connectedness (the average stack size). however, @xcite parser is not fully incremental because its oracle (the function that decides which transition to take in case of non-determinism) foot_0 is a probabilistic model that looks at the whole sentence. it does so using bi-directional elmo embeddings with the addition of bi-directional lstms. the present paper describes a fully incremental version of @xcite parser using an incremental oracle that does not look at the words that are not yet processed. we should note that by a fully incremental parsing model we do not mean a parser that has all the partial trees on the stack fully connected at ev-ery point in time. this is a property of extremely predictive top-down parsers, while the parser that we use is a ccg bottom-up parser. this choice is intentional-even though there is clear evidence that human sentence processing is highly incremental, we argue below that there is no unequivocal evidence that it is more incremental than would be allowed under the strict competence hypothesis (sch) which states that the parser cannot construct any structure that is not licensed by the competence grammar, given ccg's generalized notion of constituency @xcite . most research in incremental parsing has been directed at finding the right parsing algorithm @xcite @xcite or grammar formalism @xcite @xcite @xcite , but not much has been done in addressing the issue of finding the right oracle. early approaches to this problem were lateclosure and minimal-attachment heuristics @xcite which do not appear to be language universal @xcite . @xcite have shown that these heuristics are overruled by human parser if the context gives evidence for a particular interpretation, in itself further evidence for processing incrementality at all levels. it seems natural to model the non-deterministic decision by using a probabilistic model which will condition on words and possibly on the context. oracles of the modern broad coverage incremental parsers are without exception statistical in nature. the most typical statistical oracle is a locally normalised generative model ether in the form of simple pcfg @xcite , feature based @xcite or neural model @xcite . rnng @xcite is the main contemporary representative of this approach. rnng is a top-down parser which in its first version used a non-incremental discriminative locallynormalised model. to make the parser fully incremental @xcite exchanged the discriminative model for a generative one. this was not enough to get a working single-model incremental parser. @xcite added a couple more modifications to the search, namely wordsynchronous beams with a very large number of hypotheses, that gave good results. could we just apply these same techniques to the ccg parser of @xcite and replace non-incremental probabilistic model with an incremental one? the short answer is no. as it will be shown later, a straightforward adaptation of the beam search and switching to a generative model does indeed improve accuracy over the model that does not do that, but not enough to make the incremental parser competitive. we provide an explanation for these results and offer an alternative approach. we identify the problem for building incremental parsing models in terms of three biases: (1) label-bias, (2) exposure-bias and (3) imbalanced probability search bias. these biases are well known from the machine learning literature in structured prediction, but they do not usually have the extreme effect that is seen in the case of incremental parsing. the techniques used in rnng address some of these biases individually but none of the techniques addresses all three together. instead of using a collection of techniques for each bias, we replace them all with a single solution in the form of a global unnormalized model trained with beam-search optimization that minimises all margin violations in the beam simultaneously. this single technique addresses all of the mentioned biases and gives results that outperform all previous incremental parsing models even with a relatively small beam. this is not to say that all unwanted biases are removed-for instance, beam search is still a biased search. however, the biases that remain do not have the drastic effect on performance of the three identified above. ## baseline model the parser of @xcite already offers a fully incremental transition system with a non-incremental probabilistic model that gives state of the art accuracy in recovering predicate-argument dependencies. the parser encodes words using elmo @xcite and bilstm @xcite , sub-trees with tree encoders and the stack with stack-lstm @xcite . this provides the encoding of the whole configuration together with the buffer, because the buffer is implicitly encoded via elmo and bi-lstm, which look at the whole sentence. given the hidden vector representation of the configuration, the parser uses a feed-forward network to determine the probability of the next action. there are three main types of transitions: we refer the reader to @xcite for more detail on the original neural model and transition system, which are not of particular relevance here. what matters is only that (1) the number of tagging actions is much bigger than the number of possible parsing actions and (2) that the buffer is implicitly encoded with elmo and bi-lstm. to make the parsing model fully incremental first we modify elmo embeddings: instead of using full elmo embeddings we use only the forward lstm part of elmo. this decreases performance by only two points on the dev set f1 score from 89.5 to 87.5. finally, we replace bi-lstm with normal lstm @xcite . this causes a significant drop in performance to 60.9. we take the fully incremental model with 60.9 f1 as our baseline, and show how it can be improved, to come as close as possible to the nonincremental version that uses the same embeddings, which has accuracy 87.5 f1, changing only the method of training, keeping the network architecture and embeddings the same. ## eliminating biases some of these biases are well known in the literature of structure prediction and various proposals have been made for reducing their effect. however, most of these techniques usually address only one of the biases, and the combination of these techniques is not always straightforward. as mentioned before, label-bias is caused by model being (i) discriminative, (ii) locally normalised and (iii) having independence assumptions about future input not influencing current actions. we could remove label-bias by removing one of these properties from the model. clearly, we cannot remove property (iii) because we want an incremental model. the simplest solution is to change property (i) and make the model generative. the generative model would give us probability p(x, y) instead of p(y|x). this is done by having an additional action for generation of a word following a shift action. here the model cannot ignore the input because it is forced to generate it. it can also recognise garden-paths: if we are in a state that cannot generate the following word that means we are in a garden-path and will punish all transitions from that state. however, this solution introduces imbalanced probability search bias because we will introduce word-generation actions that have much higher entropy. @xcite advocated dropping the property (ii) by making the model globally normalised. this would allow transitions to have local weights instead of local probabilities. if all transitions from some state are bad, the model is able to give low weight to all of them because weights do not have to sum to one. lafferty et al. (2001) advocated using conditional random fields (crf), which are globally normalised probabilistic models, but margin-based alternatives like max-margin markov networks (m 3 n) @xcite and structured svm @xcite could be used in the same way. these particular solutions are not applicable here because they require (implicitly) enu-merating all possible derivations which is not possible with a model like ours that makes only few independence assumptions. exposure bias happens because model is not exposed to its errors during training time. with dynamic oracle @xcite parser is trained on its own prediced history instead of the gold sequence of actions (static oracle). whenever the model is in some sampled state (which is not necessarily a good state), we train the model to pick the transition that is a beginning of a path that would lead the parser to the ending state with the highest achievable metric score from that state. finding such a transition is not trivial for all systems and all metrics @xcite . to this date there have been no proposals for a dynamic oracle for ccg parsing with f1 metric over ccg dependency structures and it is not even clear if there is a polynomial solution to this problem. 3 therefore this is not an option that we can use. an alternative is to use a reinforcement learning algorithm reinforce @xcite . re-inforce samples derivations for training just like dynamic-oracle, but does not require design of a task-specific oracle extraction algorithm. instead, it implicitly minimises the expected error of the desired metric. 4 @xcite have shown that in some circumstances reinforce can give results almost as good as dynamic oracle, but it requires using additional techniques to compensate for high variance of the training method. the method of applying reinforce to the discriminative parser is straightforward because sampling trees from the discriminative parser is easy. however, that is not the case for the generative model from which we have to sample both trees and sentences at the same time. that is why we will apply reinforce only to the discriminative model. imbalanced probability causes a search bias so the way it was addressed by @xcite is to modify the search itself. @xcite introduced a word synchronous beam search (wordsync) in which all the hypotheses that are competing with each other are guaranteed to have the same number of expensive actions. most of these methods are either not applicable (exact crf, exact m 3 n, dynamic oracle), or they solve only some subset of the previously mentioned biases. however, we can resort to some approximate methods to global models. for instance, instead of enumerating all hypotheses to compute normalization we could use a beam search as an approximation. this was done for crf objective in @xcite and for (single-violation) m 3 n objective in @xcite . they all need to compare in some way the gold hypothesis to the rest of the beam, but the issue arises when the gold hypothesis falls out of the beam. for that situation they use different heuristics. crf approximation of @xcite and @xcite uses early update of @xcite . during training with early update, the beam search is stopped when the gold hypothesis falls out of the beam and the parameter update is performed. in the beam-search optimization (bso) method of @xcite an alternative heuristic is used from @xcite called laso. laso does the update at the same point as early but, unlike early, it continues decoding by removing all elements of the beam except for the gold one. this will potentially result in another update for the same training instance. we have implemented most of these methods in attempt to improve incremental ccg parsing. however, even though many of them gave some improvements over the baseline, none of them was good enough to give a reasonably good parser. to further improve the model we propose two novel approaches: gen-rescaling and bso-*-all where * stands for both early and laso heuristics. ## experiments we have conducted experiments on english ccgbank @xcite . for evaluation we use f1 score over labelled-directed and unlabelled-undirected dependencies. the parser is implemented in scala and uses dynet @xcite for the neural computation. the code is available on github. 5 there are two dependency types often used in ccg parsing research: first one from @xcite which is much closer to the typical ccg notion of dependencies and the second one from @xcite which is more formalism-neutral but less expressive. the only implementation of the second method is the one in c&c parser and is not able to handle all the categories that come from ccgbank. this is the rea-son why most previous work on incremental ccg parsing has used the dependencies of @xcite . in order to be able to compare to them we use the same dependencies. ## other relevant work the incremental ccg parser of ambati (2016) uses the linear model trained with a structured perceptron objective and the early update heuristic. given the simplicity of that model, it performs surprisingly well. the reason is the fact that the structured perceptron addresses all the biases identified in our paper. our work has been an attempt to bring these benefits to more modern neural models. another interesting approach to tackle labelbias while keeping the probabilistic interpretation is the error-states model of @xcite . this model in its original formulation would not be computationally efficient in our setting because there are too many instances of errorstates to be trained on in ccg parsing caused by large number of transitions. possibly some modification based on sampling could remedy this. there has also been some recent work on reducing the imbalanced probability bias. @xcite propose an algorithmic solution for organising beam search into buckets that have the same number of expensive transitions. @xcite propose a sampling based approach with the same motivation of controlling which hypotheses are being compared. of relevance for the ccg incrementality are @xcite and @xcite who claimed that human sentence processing is more incremental than ccg allows under sch for sentences like: the pilot embarrassed mary and put herself in a very awkward situation. here a male gender-biased interpretation of the antecedent "the pilot" conflicts with a feminine bound reflexive "herself". the eye-movements show processing difficulty as soon as "put herself" is read, rather than being delayed until the completion of the vp by the pp. this allows subject binding to be established by vp coordination. @xcite argue that sturt and lombardo's result is explained by the fact that the category for "put" is predictive of a future pp, allowing establishment of binding in advance of parsing without strict incrementality or compromising sch. ## conclusion and future work the methods discussed here have been applied to the task of incremental ccg parsing, but they are not limited to ccg or even to parsing as a task. in principle, they could be applied to any task involving sequential structure prediction. we see this as the most interesting use case not only for the bso-*-all training method but also for having an incremental ccg parser. such parsers can potentially make much more informed decisions about the next word, compared to the models based on mere sequence of words prefix, by including semantic and referential meaning @xcite , as well as syntax.