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

Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 1158–1171 November 20–23, 2022. ©2022 Association for Computational Linguistics 1158 Higher-Order Dependency Parsing for Arc-Polynomial Score Functions via Gradient-Based Methods and Genetic Algorithm Xudong Zhang, Joseph Le Roux, Thierry Charnois Laboratoire d’Informatique de Paris Nord, Universit´e Sorbonne Paris Nord – CNRS UMR 7030, F-93430, Villetaneuse, France {xudong.zhang,leroux,thierry.charnois}@lipn.fr 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 func- tions, 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 op- erations, 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. 1 Introduction The goal of modern graph-based dependency pars- ing 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 candi- dates is exponential in the sentence length, the scor- ing 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 (Eisner, 1997) in the projective case, or duality gap such as the Chu-Liu-Edmonds algorithm (McDonald et al., 2005) in the non-projective case. Graph-based models where parts are restricted to single arcs are called first-order models, while mod- els where parts contain k-tuples of arcs are called kth-order models. For instance models with score for sibling and grand-parent relations are 2nd-order models because parts consist of 2 connected arcs. The connectivity is important since it helps build- ing efficient dynamic programming algorithms in the case of projective arborescences (Koo and Collins, 2010) or efficient approximations in the non-projective case based on lagrangian heuris- tics (Koo et al., 2010; Martins et al., 2013) or belief propagation (Smith and Eisner, 2008). 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 kth-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 depen- dency parsing as polynomial functions. This frame- work can recover most previously defined score functions and gives a unified framework for graph- based parsing. Moreover, it can express novel func- tions since in this setting parts are made of possibly disconnected tuples of arcs. We call the results generalized higher-order models, as …

Content truncated to 500 words