Dependency Graph Parsing as Sequence Labeling (2024)

Abstract: Various linearizations have been proposed to cast syntactic dependency parsing as sequence labeling. However, these approaches do not support more complex graph-based representations, such as semantic dependencies or enhanced universal dependencies, as they cannot handle reentrancy or cycles. By extending them, we define a range of unbounded and bounded linearizations that can be used to cast graph parsing as a tagging task, enlarging the toolbox of problems that can be solved under this paradigm. Experimental results on semantic dependency and enhanced UD parsing show that with a good choice of encoding, sequence-labeling semantic dependency parsers combine high efficiency with accuracies close to the state of the art, in spite of their simplicity.

## introduction in recent years, a new family of approaches has emerged for dependency parsing that treats the problem as a sequence labeling task @xcite . this has advantages in terms of simplicity, flexibility and speed, as parsing can be performed with generic sequence labeling software and easily combined with other tasks that operate within the same framework. for this, one needs an encoding that can represent parse trees as a sequence composed of one discrete label per word, so that a sequence labeling component can be trained and output trees can then be decoded from the sequences. in the last few years, a wide range of such encodings with different strengths and weaknesses have been proposed for dependency parsing @xcite @xcite @xcite . however, these encodings are designed for dependency trees, where each word is restricted to have exactly one parent and cycles are forbidden. the more complex family of structured prediction problems where the output is a graph of dependen-cies between words, including tasks like semantic dependency parsing @xcite , enhanced universal dependencies parsing @xcite or even structured sentiment analysis @xcite ; has not been integrated into the sequence labeling framework so far due to a lack of encodings that can support reentrancy, disconnected nodes and cycles. 1 we bridge this gap by defining sequence labeling encodings for these problems that are framed as predicting directed graphs between words -which, following some previous literature @xcite -we group under the umbrella term of dependency graph parsing. by taking dependency tree encodings as a starting point and extending them to support graphs, we define a wide range of both unbounded and bounded encodings to cast dependency graph parsing problems as sequence labeling. to test the performance of the encodings, we experiment on two dependency graph parsing tasks, representative of different kinds of linguistically-relevant structures: semantic dependency parsing (where the output are dags, directed acyclic graphs) and enhanced ud parsing (where graphs have cycles). the source code is available at github.com/anaezquerro/separ. ## background sequence-labeling approaches that partially perform syntactic parsing have long been known, in the form of supertagging @xcite . still, the goal of supertagging is to cut the search space of the parsing process, not to fully replace it: the generated labels (supertags) are not enough to encode a whole parse tree, and a parsing algorithm is still needed to fill the missing information. the first attempt at addressing the full task of natural language parsing as sequence labeling was by @xcite , who introduced a linearization for dependency parsing where the label of each word encoded the pos tag of its head and its relative position among words with the same pos tag. however, machine learning algorithms of the time struggled to predict such labels, leaving the practical results far behind the state of the art. it was with the development of deep learning and its use in nlp architectures that parsing as sequence labeling became practically viable. this was shown by @xcite for constituent parsing and by @xcite for dependency parsing. for the purposes of this paper, we will leave work on constituent parsing linearizations @xcite aside and outline the encodings that cast dependency parsing as sequence labeling, since they have a more direct relation to our target problem of dependency graph parsing and will be the inspiration of our proposed encodings. common notation let v be a vocabulary of possible tokens. we will denote a sentence of length n by @xmath0, w 2 , . . . , w n ] ∈ v n . let s n be the set of possible parses (dependency trees or dependency graphs) for sentences of length n. then, a sequence labeling encoding for parsing is an injective function e : s @xmath1; where l is a set of labels that is defined depending on the encoding. thus, a sequence labeling encoding is used to represent a parse for a sentence of length n, @xmath2, w 2 , . . . , w n ], as a sequence of n labels (one per word), @xmath3, l 2 , . . . , l n ] ∈ l n . since e is injective, one can recover a parse in s n from its associated label sequence in l n via the inverse function, e -1 : {e(s) | @xmath4. this enables parsing as sequence labeling: if we train a tagger to predict a function f θ : v @xmath5, and θ are the model parameters) that associates each word w with the encoding of its parse, we can obtain the parse for a sentence w as e -1 (f θ (w)). a theoretical limitation is that no known encodings are bijective, so e -1 is not defined on all possible sequences of labels (l n ), but just on those that correspond to encodings of valid trees. we call the set of such sequences, γ @xmath6, the set of well-formed label sequences for length n. since f θ is an approximation by a sequence labeling classifier, it is possible that it outputs ill-formed label sequences. however, this is workable in practice, since there are simple heuristics to fix ill-formed sequences converting them to well-formed ones (i.e., mapping from l n to γ n ). we now define concepts related to kplanarity @xcite to later define the coverage of various encodings. two arcs in a dependency tree or graph are said to cross if their arrows cross when drawn above the words. thus, two arcs (w i , w j ) and (w k , w l ) such that min(i, j) < min(k, l) cross iff min(k, l) < max(i, j) < max(k, l). a tree or graph is noncrossing, or 1-planar, if it contains no crossing arcs. we also introduce the term relaxed 1-planar for a tree or graph with no pair of crossing arcs pointing in the same direction (i.e., only opposite crossing arcs are allowed). finally, a tree or graph is (relaxed) k-planar for some @xmath7. dependency parsing encodings a sequence labeling encoding for dependency parsing is a sequence labeling encoding where the set of parses of interest, s n , is t n , the set of dependency trees for sentences of length n. in all dependency parsing encodings defined so far in the literature, each label l i assigned to a word w i is of the form (d i , x i ), where d i represents the label of the dependency going to w i , and it is x i that varies between encodings and encodes the unlabeled dependency tree. thus, we will focus on x i and ignore dependency labels from now on. ## unbounded graph encodings contrary to dependency trees, dependency graphs in general allow reentrancy (two or more incoming arcs to the same node) and cycles. let g n be the set of dependency graphs for sentences of length n. a sequence labeling encoding for dependency graph parsing is one where s @xmath8. we next present our unbounded encodings. as in dependency parsing encodings, we assume that each label l i is of the form (d i , x i ), but in this case d i is a tuple composed of the labels of the dependencies going to w i , sorted by head position. as before, we focus on the encoding-dependent component x i , and ignore dependency labels from now on. ## bounded graph encodings we now define two bounded encodings for graph parsing, based on the 4-and 7-bit encodings by @xcite . ## model architecture let w be our input sentence. the model produces a sequence of vectors @xmath9, w 2 , . . . , w n ] us-ing a generic encoder e θ . this encoder can range from lookup tables mapping words to static embeddings foot_5 to encoders that deeply contextualize words. we then use a generic decoder, d ϕ , to make output predictions at the word level. the decoder could also vary widely, from simple feedforward networks to more sophisticated architectures. let @xmath10, . . . x n ] = d ϕ (w) be the output representations for each word. we use these outputs to predict each component x i from the label l @xmath11, x i ). the sequence (x 1 , ..., x n ) is fed to the corresponding encoding-specific decoding algorithm to recover the set of predicted arcs ê. then, to predict the label representing the relationship between the pair of nodes of a predicted arc (w h , w i ) ∈ ê, we concatenate their representations [(w h |w i ) : (w h , w i ) ∈ ê] and use them to feed another generic decoder d φ that predicts the dependency type (an element of d i ) associated with them. ## experiments for evaluation, we use two kinds of dependency graph structures with different properties: semantic dependency parsing, and enhanced ud parsing. datasets for semantic dependency parsing, we will use the following datasets and formalisms from the semeval 2018 task 18 @xcite : (i) the english dataset annotated with delph-in mrs-derived bi-lexical dependencies @xcite (ii), the english and chinese datasets with enju predicate-argument structures @xcite , and (iii) the english and czech datasets with prague semantic dependencies @xcite . they are all collections of sentences annotated as graphs, where some tokens do not contribute to the graph, some might have just one parent, and others multiple parents. these representations are dags, excluding the study of relevant phenomena involving cycles. to study cycles, we rely on enhanced universal dependencies, particularly on the version released together with the iwpt 2021 shared task @xcite . we evaluated five languages: arabic, finnish, french, slovak, and tamil, joining the different treebanks of the same language to build a larger annotated corpus. in appendix a.2, we provide additional information and statistics for both dag and iwpt treebanks. metrics we use the sdp evaluation toolkit 6 (oepen et al., 2015). we report both unlabeled and labeled f1 score (lf, uf) w.r.t. the predicted dependencies, i.e. triplets of the form (predicate, role, argument). 7 results with further metrics, including exact match, are in the appendix. models' setup for the encoders of our taggers, we use a few representatives. we focus on experiments using two transformer-based encoders: (1) xlm-roberta @xcite , as a single multilingual pre-trained encoder for non-english experiments, and (2) xlnet @xcite for english experiments. in addition, we experimented with bilstms for comparison in terms of speedaccuracy trade-off. the decoder is a 1-layered feedforward network followed by a softmax. we did a minor hyperparameter search to tune the optimizer and batch size to our resources. 8 for comparison, we include an external model (biaf), a biaffine semantic dependency parser (dozat and manning, 2018) -from supar foot_9 -using the same encoders as for our experiments. ## conclusion for the first time, we have framed dependency graph parsing tasks, like semantic dependency or eud parsing, as sequence labeling tasks. we have proposed a wide variety of bounded and unbounded encodings that -with the right representationcan be learned by standard encoders. among unbounded encodings, positional strategies performed poorly, but bracketing-based encoders obtained robust performance, excelling especially in dense 10 our decoding process is parallel for positional encodings, since each label xi can be independently processed to create a subset of predicted arcs, thus optimizing the inference time. datasets. on the other hand, the more compact bounded encodings, with a fixed number of bits per label, obtained the best results in sparser datasets. overall, results are comparable or even outperform a strong biaffine baseline. thus, dependency graph parsing can effectively be solved as sequence labeling, as both bounded and unbounded encodings are learnable using standard bidirectional encoders and simple feed-forward decoders.