Dependency parsing with structure preserving embeddings (2021)

Abstract: Modern neural approaches to dependency parsing are trained to predict a tree structure by jointly learning a contextual representation for tokens in a sentence, as well as a head–dependent scoring function. Whereas this strategy results in high performance, it is difficult to interpret these representations in relation to the geometry of the underlying tree structure. Our work seeks instead to learn interpretable representations by training a parser to explicitly preserve structural properties of a tree. We do so by casting dependency parsing as a tree embedding problem where we incorporate geometric properties of dependency trees in the form of training losses within a graph-based parser. We provide a thorough evaluation of these geometric losses, showing that a majority of them yield strong tree distance preservation as well as parsing performance on par with a competitive graph-based parser (Qi et al., 2018). Finally, we show where parsing errors lie in terms of tree relationship in order to guide future work.

## introduction dependency grammars are syntactic formalisms that represent the syntactic structure of a sentence as asymmetric binary grammatical relations among words @xcite @xcite . an example dependency structure is given in figure 1 . formally, a dependency structure is defined as a directed graph where words are vertices and relations are labelled directed edges (the arcs) between a child (the dependent) and its parent (the head). in practice, dependency structures considered for syntactic analysis are trees. dependency trees have long been used to improve the performance of many nlp applications, including machine translation @xcite @xcite , relation extraction @xcite @xcite , and semantic role labeling @xcite @xcite . in order to assign the correct dependency tree to a sentence, dependency parsers are trained to correctly identify head-dependent relations between pairs of words. modern neural approaches do so by jointly learning contextual feature representations for the tokens in a sentence, as well as a parsing decision function. this is the case for recent graphbased parsers @xcite @xcite where an encoder feature extractor is complemented by a score function predicting the likelihood of a word to be the head of another. however, whereas this joint learning strategy results in stateof-the-art performance, the representations learned by these parsers are opaque. as a first step towards learning interpretable parser representations, here we take a different approach: in addition to learning-to-parse, we seek to learn representations from which tree distances between words in dependency trees can be recovered. this stems from one simple observation: previous approaches do not take into account the geometry of the tree they try to model. that is, parsers are unaware of the structural properties of the tree (e.g., distance between nodes, depth from root), and as such are not trained to explicitly preserve these properties. in this respect, our approach is aligned with recent work looking at these geometric properties in the context of probing the bert @xcite embedding space for syntactic structure @xcite . in particular, @xcite manning (2019 have shown that it is possible to recover approximate syntactic trees from bert embeddings by a linear transformation trained to minimize the difference between predicted and ground-truth tree distances. given these results we then ask: is it possible to extend this idea to directly train treeaware dependency parsers? we argue that using the geometric tree structure to embed the dependency trees enhances the interpretability of the learned representations in this paper, we show that this is indeed possible by casting dependency parsing as a tree embedding problem. specifically, we view a dependency tree as a finite metric space, and compute head-dependent scores for all word pairs within a sentence as follows: given a sentence @xmath0, . . . , w ns ), where w 0 is a special root token, we compute a geometric tree embedding φ : {w 0 , . . . , w ns } → r m that maps tokens w i to m-dimensional vectors. geometric properties of an ideal isometric tree embedding are used to define the functional form of head-dependent (edge) scores ψ(w i , w j ). concretely, our approach predict dependency trees only from pairwise embedded node distances, which completely specify the score function. we consider this as a step in the direction of interpretable end-to-end dependency parsing. we start with a straight-forward application of @xcite and consider a mean absolute error (mae) loss that encourages the embedding φ to approximate an isometric embedding of the ground-truth tree t s into (r m , d r ). in this paper, we use the squared euclidean distance semi-metric (d 2 2 ) as in @xcite and also consider the distance obtained from the ℓ 1 -norm (d 1 ) foot_0 . we show formally that any isometric d 2 2 embedding can be simply rotated to form an isometric d 1 embedding. we learn the tree embedding φ and the edge score function ψ through end-to-end training, by incorporating geometric properties of dependency trees (in terms of distance and depth) in the form of geometric losses within a graph-based parser. as our base parser, we use a simplified version of the biaffine parser of @xcite . this setup allows us to directly compare the performance of our losses and score functions to the biaffine score function used in several state-of-the-art graph parsers. we propose three additional losses for training a dependency parser expressed explicitly through tree distances: a maximum likelihood estimation function, a margin-based loss function, and one based on cross-entropy. finally, we explore whether adding a soft global constraint on the isometry of the learned trees helps with parsing performance; to this end, we combine our novel loss functions with the mae loss. we evaluate our approach on 16 languages from different families. we complement unlabeled accuracy of head-dependent attachement scores (uas) with a spearman's ρ correlation between predicted and true distances (dspr) to directly assess geometric properties of the output trees. we also provide labeled attachment scores (las) for completeness. through extensive experimentation, we make the following observations: our results in the direction of accurate dependency parser that closely preserve tree distances are encouraging. ## background: metric tree embeddings a tree @xmath1, e) along with the distance d t (u, v) is a finite metric space, foot_1 where d t (u, v) is the length of the shortest path between any u, @xmath2. in this paper we consider tree embeddings, φ : @xmath3, which map nodes @xmath4. that is, for all pairs u, @xmath5, the tree distance d t (u, v) is roughly the corresponding distance d r (φ(u), φ(v)) in the embedding space r m , where we select the metric or semi-metric d r (x, y) in r m . in this section, we discuss the choice of d r and illustrate distortion free (i.e., isometric) embeddings φ : @xmath6. these distortion free embeddings motivate the formulation of losses that we use for training suitable embeddings, as discussed in § 3. to choose the distance measure d r in the embedding space, we note that for a sufficiently large dimension m: i) any tree can be embedded isometrically into ℓ 1 ; ii) any metric space (including trees) can be embedded into ℓ ∞ ; and iii) for ℓ p spaces, with 1 < @xmath7, trees can only be embedded with distortion @xcite . the power transform of the euclidean distance d 2 (x, y) c , with @xmath8, allows for isometric embedding of trees @xcite . however, the squared euclidean distance d 2 (x, y) 2 does not satisfy the triangle inequality foot_2 and therefore is only a semi-metric. nevertheless, both (r m , d 1 ) and (r m , d 2 2 ) are natural choices for embedding spaces for trees and, in this paper, we restrict our attention to these. we follow @xcite to explicitly construct squared euclidean embeddings. specifically, all distortion free embeddings into (r m , d 2 2 ) can be simply expressed in terms of the edge displacement vectors {z i } |e| @xmath9, where z @xmath10.e., z := φ(c) -φ(p), where c, @xmath11. for an isometric embedding, it turns out we require these z i 's to be orthonormal, that is theorem 2.1. pythagorean embeddings. given a rooted tree (v, e, r), where @xmath12, then for any @xmath13: @xmath14, for some matrix @xmath15.e., eqn. (1) is satisfied). see appendix b-d for an example that demonstrates this construction along with proofs. the edge-on-path indicator vectors b(r, v) provide some additional intuition about these squared euclidean embeddings. specifically, for v, @xmath16 here (5) follows from ( 1 ), ( 3 ) and ( 4 ). therefore g is an isometric ℓ 1 embedding which expresses tree distance in terms of the ℓ 1 norm of the difference between two path vectors b. one interesting consequence of theorem 2.1, along with eqn.'s (4) and ( 6 ), is: corollary 2.1. ℓ 1 embeddings. given any isometric embedding φ : @xmath17, the embedding g(v) = z t φ(v) is an isometric embedding of the same tree here z is as described in (3). that is, any distance preserving tree embedding using the squared euclidean norm can simply be rotated to an isometric ℓ 1 tree embedding. 4 note the converse of cor. 2.1 is not true. for example, three equally spaced points on a line form an ℓ 1 embedding that cannot be linearly transformed to a d 2 2 embedding. indeed, it is shown in @xcite ) that a finite metric tree can be embedded into (r m , d 1 ) if and only if it has at most 2m leaves. thus, for a fixed dimensional embedding space r m , the metric d 1 allows for more trees to be isometrically embedded than d 2 2 . in this paper we use an embedding dimension m that is larger than the number of edges and thus isometric tree embeddings are feasible using both d 2 2 and d 1 . the learning problem considered in this paper is, given a sentence s, we seek to embed each of the sentence's tokens into (r m , d r ) such that the embedded tree is nearly isometric to the dependency parse tree for s. here we evaluate using both d 1 and d 2 2 for d r . ## geometric losses for tree embeddings given a sentence @xmath18, . . . , w ns ), where w 0 is a special root token inserted at the beginning of every sentence, dependency parsing seeks to recover the correct dependency tree t @xmath19, e s ). for simplicity, we label the tree nodes in v s with the tokens themselves, so v @xmath20, . . . , w ns }. a geometric tree embedding maps tokens w i within a sentence s to embedded points v @xmath21, s) ∈ r m (for brevity, we drop the dependence on the whole sentence s and simply write φ(w i )). in § 2, we describe the exact geometry of the isometric embeddings using the d 2 2 semi-metric. for d 1 isometric embeddings we show one sub-class are simply rotations of isometric d 2 2 embeddings, but there are other forms. this section examines the use of auxiliary losses on the embedding φ that encourage approximately isometric embeddings. we expect an approximation of this geometry holds in d 2 2 when the losses are sufficiently small. since we do not have a similar proof of necessity as in appendix d for d 1 embeddings, the local geometry is more open. given such an embedding, we then follow firstorder graph-based dependency parsers @xcite which compute a pairwise score ψ(v i , v j ) that indicates how likely it is for w j to be the head of w i . these scores provide edge weights on a fully connected embedded graph on φ(v s ) × φ(v s ). having trained a network to compute suitable embeddings v @xmath22, v j ), parsing then amounts to finding the maximum spanning tree in this weighted graph that is rooted at v 0 ; a detailed description of the parser architecture is provided in § 4. given this general approach, a natural choice for an auxiliary loss on φ is to consider the mean absolute error (mae) in the distances between the embeddings of any two nodes: we next consider the edge scoring function ψ, whose role is to assign costs to proposed headdependent pairs (w i , w j ). we denote this groundtruth head-dependent relation by (w i , w j ) (which is true when w j is the head of w i in t ) and note it can be defined only in terms of the distance d t (w i , w j ) and depth difference ∆ s (w i , w j ) = d t (w 0 , w i ) -d t (w 0 , w j ) as follows: each node w i then has a unique head w j defined by (8), except for the root w 0 which has none. given the embedding φ is providing a near-isometric tree, we define an edge scoring function in the embedding space, namely ψ(v i , v j ), by rewriting (8) in the following probabilistic form: a natural loss on both the embedding φ : @xmath23, v j ) is the maximum likelihood loss as an alternative to the mle loss we consider a margin based approach where the task is to minimize ℓ φ ij for the true head j, subject to ℓ φ @xmath24, . . . , n}\{i, j}, where α > 0 is a margin. 5 we explore such a margin-based approach using the soft triplet loss @xcite as a third alternative for the head-dependent loss we consider the cross-entropy between the probability distribution p φ (w j |w i ) and the corresponding distribution p t (w i |w j ) formed by using an isometric embedding φ t in eqns. (9 -13). note that for an isometric embedding φ t we have d r (v i , v j ) = d t (w i , w j ), and this can be used to simplify the resulting expression. specifically, we find p t (w j |w i ) depends only on the true tree distance d t and not on the details of φ t . the crossentropy loss is then in summary, we investigate the choice between several different head-dependent losses (i.e., eqn.'s ( 14 ), (15), or (16), and optionally combine each of these with the explicit global mae loss (7). ## conclusions in this work, we propose to use the geometry of (dependency) tree structures to construct a neural dependency parser that improves the interpretability of the learned representations without compromising parsing performance. we propose several geometric loss functions, and show that for a majority of them, our simple network learns distancepreserving embeddings through end-to-end training. in doing so, we also compare squared euclidean distance (d 2 2 ) with the distance obtained from ℓ 1 -norm (d 1 ), as the (semi-)metric in the embedding space r m , and provide empirical evidence for using the proper d 1 metric. we compare our results with a competitive and widely-used graphparser proposed by @xcite on 16 languages from different families, and show overall parser performances that are on par with it. our experiments also suggest a new way of looking at the sources of parsing errors in terms of tree distances, and show that the majority of errors are local (e.g., sisters or grandparents). for future work, we suggest looking at potential ways to correct such high-frequency head prediction errors, defined by their relationship within a tree. another interesting direction that's worth exploring is to use the continuous tree distances predicted by our methods as features for downstream tasks instead of the discrete tree structures produced by conventional parsers. as recent work has been exploring, this differentiable representation of tree structure is potentially useful within the iterative-refinement framework @xcite , or as additional tree-specific positional features in a transformer @xcite .