Higher-Order Dependency Parsing for Arc-Polynomial Score Functions via Gradient-Based Methods and Genetic Algorithm (2022)

Abstract: We present a novel method for higher-order dependency parsing which takes advantage of the general form of score functions written as arc-polynomials, a general framework which encompasses common higher-order score functions, and includes new ones. This method is based on non-linear optimization techniques, namely coordinate ascent and genetic search where we iteratively update a candidate parse. Updates are formulated as gradient-based operations, and are efficiently computed by auto-differentiation libraries. Experiments show that this method obtains results matching the recent state-of-the-art second order parsers on three standard datasets.

## introduction the goal of modern graph-based dependency parsing is to find the most adequate parse structure for the given input sentence by computing a score for all possible candidate parses, and returning the highest-scoring one. since the number of candidates is exponential in the sentence length, the scoring is performed implicitly: after computing scores for possible parts, the best structure, whose score is the sum of its various parts, is returned by a combinatorial algorithm based on either dynamic programming such as the eisner algorithm @xcite in the projective case, or duality gap such as the chu-liu-edmonds algorithm @xcite in the non-projective case. graph-based models where parts are restricted to single arcs are called first-order models, while models where parts contain k-tuples of arcs are called k th -order models. for instance models with score for sibling and grand-parent relations are 2 nd -order models because parts consist of 2 connected arcs. the connectivity is important since it helps building efficient dynamic programming algorithms in the case of projective arborescences @xcite or efficient approximations in the non-projective case based on lagrangian heuristics @xcite or belief propagation @xcite . the score function of first-order models, being a sum of parts which are simple arcs, is linear in arc variables, while for second-order, being a sum of parts which are pair of arcs, the score function is quadratic in arc variables. more generally k th -order models have a polynomial score function in arc variables, with highest degree equal to k. in this paper we explore the consequences of treating score functions for higher-order dependency parsing as polynomial functions. this framework can recover most previously defined score functions and gives a unified framework for graphbased parsing. moreover, it can express novel functions since in this setting parts are made of possibly disconnected tuples of arcs. we call the results generalized higher-order models, as opposed to previously connected higher-order models. on the other hand, polynomial functions are difficult to manipulate. they are non-convex and so, in addition to already known problems in higherorder parsing such as the computation of the partition function for probabilistic models, maximum a posteriori (map) decoding is itself a challenge. we develop an approximate parsing strategy based on coordinate ascent @xcite , where we iteratively improve a candidate by flipping arcs. we exploit the polynomial nature of the score function to derive an accurate and efficient procedure to select arcs to be flipped. since this method converges to a local minimum, we show how to embed it within a meta-heuristic based on a genetic analogy @xcite to find better optima. we can learn these models via two methods, max-margin or probabilistic estimation. maxmargin is straightforward because it only requires map decoding but is quite fragile since it is sensitive to approximation errors, which are inevitable in our setting. we design a probabilistic loss for our model where we approximate parse scores via a first-order taylor expansion around the map solution. we find that this novel method is efficient and we show empirically that it can outperform previous higher-order models. in summary our contributions are the following: ## related work before the use of powerful neural feature extractors (e.g. bilstm or transformers) dependency parsing with high-order relations was a clear improvement over first-order models. @xcite considered efficient third order models for projective dependency parsing. in order to have efficient dynamic programming algorithms for decoding, only a few limited predefined structures can be included to the model (e.g. dependency, sibling, grandchild, grand-sibling, tri-sibling). 1 higher-order non-projective parsing is np-hard but fast heuristics with good performance have been proposed based on dual decomposition for instance. however, efficient subsystems must be devised to efficiently process complex parts, either based on dynamic programming algorithms such as viterbi @xcite or on integer linear programming @xcite . in practice this restricts parts to connected subgraphs. 2 since the wide adoption of deep feature extractors, the situation is less clear. @xcite consider a second-order model with dependency and adjacent sibling, which can guarantee efficient decoding for projective arborescence with a batchified variant of eisner algorithm @xcite . the results show that adjacent sibling is beneficial for the performance of parser comparing with arc-factored model. @xcite claim that in the non-projective case, second-order features help especially in long sentences. on the other hand, @xcite showed that in general the impact of consecutive sibling features was not substantial, and @xcite showed that the main benefit of these features could be understood as variance reduction, and vanishes when ensembles are used. closely related to our work, wang and tu (2020) consider a second-order model with score for dependencies, siblings and grandchildren where they do not constrain siblings to be adjacent. although exact estimation is intractable in their setting, an approximate estimation of probability of arborescences can be calculated efficiently by a messagepassing algorithm. their experiments seem to confirm that second-order relations are beneficial to the parsing accuracy, even when trained by an approximate estimation of probability, namely mean-field variational inference. instead we approximate the partition function using a first-order taylor approximation around the map solution. partition approximations are usually performed via bethe's free energy, see for instance @xcite . @xcite showed that head selection was a good trade-off during the learning phase, for first-order models. our method applies this principle to the higher-order case, leading to a coordinate ascent method, well known in the optimization literature @xcite . in machine learning and nlp, ascent methods are usually performed in primal-dual algorithms, e.g. @xcite for svms. we use genetic programming to escape local optima when searching for the best parse. although this kind of metaheuristics has been used for other tasks in nlp such as word sense desambiguation @xcite or summarization @xcite , and joint pcfg parsing and tagging @xcite , it is the first time it is applied to dependency parsing to the best of our knowledge. since genetic algorithms can be seen as implementing a markov chain @xcite over candidate solutions, our method resembles markov-chain monte-carlo methods, e.g. gibbs sampling, which have already been investigated in parsing @xcite . our method to choose the best arc to improve the current parse is inspired by a recent method for sampling in discrete distributions @xcite where we replace sampling by map decoding. we rely on properties of polynomials to derive efficient routines for approximate head selection. polynomial factors were discussed for higher-order parsing in @xcite . ## notations we will denote a sentence of n words as @xmath0, x 1 , . . . , x n , where x i is either the dummy root symbol when @xmath1, or the i th word otherwise. for such a sentence x and h, @xmath2, 1, . . . , n}, (h, d) represents a direct arc form head x h to dependent x d . we note y a parse structure, with (h, d) ∈ y if (h, d) is an arc of the parse. for convenience, we will abuse notation and sometimes interpret a parse y either as a vector indexed by arcs or as a matrix: the set of all valid parses for sentence x is noted y x . when x is unambiguous, we simplify y x to y. we note c x as the set of all possible arcs for sentence x, i.e. the arcs of the complete graph over vertices in x, or c when unambiguous. we say that a non-empty set of arcs @xmath3, d 1 ), . . . (h k , d k )} is a factor set if ∀i, h i ̸ = d i and ∀@xmath4, d i ̸ = d j . the first condition asserts that an arc cannot be a self-loop while the second enforces that each word has only one head in a factor set. the two constraints are natural and required for dependency parsing. we note the set of factor sets of cardinal k which can be constructed from arcs in a as f k (a), the set of k th -order factors. in particular, we will just write f k for f k (c). we will abuse notations and write set difference f \{a} with a singleton simply by f \a. given a logic formula f , 1[f ] is the function returning 1 when f is true and 0 otherwise. finally, l hd denotes the label for arc (h, d). ## polynomial score functions for dependency parsing in this work, we consider a generalization of previous score functions for graph-based dependency parsing where we explictly write the score function as a polynomial function where variables represent dependency arcs. with this formulation we can emulate previous score functions, for instance @xcite , but also express new ones. we note that we consider only polynomials where, for each factor, a variable can be used at most once, in other words we deal with polynomials without exponents: in order to reach the k th degree, k different variables must be multiplied. ## learning and decoding we follow @xcite and @xcite , and learn arcs and labels in a multitask fashion with a shared bilstm feature extractor. decoding is a 2-step process, where we first infer a parse structure, and second predict an arc labelling. loss is the sum of label and arc losses: we write (x * , y * , l * ) for the training input sentence and its corresponding parse and labeling. ## experiments we evaluate our parsing method 11 with the score function of @xcite and our extension with third-order factors (3o) with coordinate ascent (ca) and genetic algorithm (ga). we use two kinds of pretrained word vectors: static, such as glove and fasttext @xcite , and dynamic, marked as +bert @xcite . all experiments use higher-order scores. ## conclusion we presented a novel method for higher-order parsing based on coordinate ascent. our method relies on the general form of arc-polynomial score functions. promising arcs are picked by evaluated by gradient computations. this method is agnostic to specific score functions and we showed how we can recover previously defined functions and design new ones. experimentally we showed that, although this method returns local optima, it can obtain state-of-the-art results. further research could investigate whether the difference between the search space during learning and decoding is a cause of performance decrease. in particular the coordinate ascent could be replaced by a structured optimization method such as the frank-wolfe algorithm (see @xcite for a recent variant) to obtain a local optimum in a more restricted search space.