An in-depth look at E uclidean disk embeddings for structure preserving parsing (2021)

Abstract: Preserving the structural properties of trees or graphs when embedding them into a metric space allows for a high degree of interpretability, and has been shown beneficial for downstream tasks (e.g., hypernym detection, natural language inference, multimodal retrieval). However, whereas the majority of prior work looks at using structure-preserving embeddings when encoding a structure given as input, e.g., WordNet (Fellbaum, 1998), there is little exploration on how to use such embeddings when predicting one. We address this gap for two structure generation tasks, namely dependency and semantic parsing. We test the applicability of disk embeddings (Suzuki et al., 2019) that has been proposed for embedding Directed Acyclic Graphs (DAGs) but has not been tested on tasks that generate such structures. Our experimental results show that for both tasks the original disk embedding formulation leads to much worse performance when compared to non-structure-preserving baselines. We propose enhancements to this formulation and show that they almost close the performance gap for dependency parsing. However, the gap still remains notable for semantic parsing due to the complexity of meaning representation graphs, suggesting a challenge for generating interpretable semantic parse representations.

## introduction numerous studies in nlp have focused on embedding linguistic elements into metric spaces, where instances are represented as vectors whose geometric distance reflects the semantic similarity among instances @xcite @xcite . more recently, some have gone beyond embedding words and sequences, and explored the encoding of a hierarchy (e.g., wordnet, @xcite through modelling its partial order structure @xcite @xcite . consequently, given the size and depth of such structures, attention has shifted to geometric spaces (mostly hyperbolic) that could better represent order and containment relations @xcite @xcite . methods to embed elements of hierarchies are structure-preserving, and therefore interpretable, in that the relative position in the embedding space reflects the relation in the original hierarchy (e.g., parent-child relation). most of these methods have been shown to be beneficial not only on tasks pertinent to the encoded hierarchy itself (e.g., hyponymy relations), but on downstream tasks including multimodal retrieval @xcite and video understanding @xcite . however, whereas there is a plethora of studies looking at preserving structure while encoding an hierarchy given as input, there is little to no exploration on how to do this while predicting one. in this work, we start one such exploration with the quintessential structure generation task in nlp: parsing. given an input sentence, e.g., 'anna asked mary to stop', parsing is the task of transducing a natural language string into a structured linguistic representation (e.g., the amr graph in fig. 1(a) ) that encodes either syntactic or semantic properties of the string. recent neural network based approaches have achieved state-of-the-art performance while being able to generalize both across frameworks, as well as across trees and graphs @xcite @xcite @xcite . however, not much can be said about the representations these parsers learn since the parsers are not explicitly trained to preserve any of the geometric properties of their output structure, and as such are not interpretable. we believe that moving to interpretable, structured representations would allow for a better diagnostic of what is learnt by a parser, while at the same time laying the foundations to connect 'deep' natural language understanding to other tasks, especially in the multimodal domain. how can we build such interpretable representations? does interpretability impact performance? @xcite have attempted to answer these questions in the context of parsing into dependency trees by means of a structure-preserving loss that forces embedding distances to be isometric to tree distances. whereas kádár et al. show that a structure-preserving embedding leads to comparable performance with blackbox methods, their method does not generalize to graphs. this is of particular relevance to semantic parses that are often dags, and where it is unclear how to isometrically embed multiple paths between a pair of nodes. to this end, we turn to a method that allows us to model transitive asymmetrical relations expressible as a dag: disk embeddings @xcite . disk embeddings represent dags as a series of concentric disks, each defined by a center vector and a radius (as the ones in fig 1(b )), and have been shown to outperform other methods when encoding hypernym relations in the wordnet hierarchy. however, it is not clear whether such a method transfers well to more complex architectures where embeddings are contextualized given an input sentence, and structure prediction often interacts with predicting other elements of the tree or graph (node label, edge label, etc.). in summary, our work makes the following contributions: disk embedding losses for tree and graph generation in parsing: we found the disk embedding loss formulation of @xcite to be sub-optimal w.r.t. parsing performance. we found that simply adding a positive margin already provides a large boost in performance, but the best performance is obtained when an auxiliary loss that considers local neighbourhood relations is added, as well as when parent-child relations are oversampled. interpretability in parsing (though at the cost of performance): through a comparison with noninterpretable approaches, we found that whereas for dependency trees the price to pay in terms of performance for interpretability is small, for semantic graphs the gap is higher, highlighting where future work should focus its efforts. importantly, we found that most semantic parsing errors are local and specific to the parser we use, where the lack of explicit alignment between words and graph nodes poses a challenge for disk embeddings, especially in the case of named entity substructures. ## disk embeddings: background as discussed above, disk embeddings @xcite provide an interpretable model for transitive asymmetrical relations (i.e., partially ordered sets or posets), such as those represented by a dag. they are a general framework that allows to embed posets in a (quasi-)metric space. let's define (x, d) as a quasi-metric space with distance d and a closed disk d(x, r) = {@xmath0, x) ≤ r}, where x is the center and r the radius. we can express the containment relationship for two disks foot_0 as given a set of such disks, the ordering provided by this subset relationship provides a poset. foot_1 disk embeddings seek to maintain order isomorphism between the posets of a graph g (x g , g ) and their disk embedding representation (x φ , φ ). such an isomorphism exists if there is a bijective in our case the bijective function f is modelled via a neural network architecture introduced in § 3. to achieve isomorphism, we make use of the protrusion ℓ ij of disk x @xmath1, r j ) with respect to disk x @xmath2, r i ) as the degree of containment: it follows from eq. ( 1 ) that ℓ @xmath3. moreover, the protrusion ℓ ij provides a continuous measure of the degree of containment. specifically it equals the maximum signed distance of points in disk d(c j , r j ) from the boundary of disk d(c i , r i ). here ℓ @xmath4, r j ) is entirely contained inside d(c i , r i ) (and, indeed, with a margin equal to recovering dags from disk embeddings. we wish to be able to represent a dag with a disk embedding and also be able to recover the edges of that dag from its disk embedding. however, recovering the edges of the original dag is not always possible. to see this, suppose we have a disk embedding formed by a 1-1 mapping of the nodes of a dag to disks. 3 moreover, suppose the mapping is an order isomorphism, so the partial ordering is preserved. it is natural to consider an edge from disk x i to disk x j if and only if x j ⊂ x i and there is no other intervening node (i.e., there is no x k such that x j ⊂ x k ⊂ x i ). this process recovers a dag with the same partial ordering as the original dag, but it may be missing edges. this issue occurs, for example, for the disk embedding shown in fig. 1b , which represents the same partial ordering as the dag in fig. 1a . however, in decoding this disk embedding, we would not decode the edge from 'ask' to 'person', since 'stop' is an intervening node. we remedy this problem by adding as many dummy nodes as necessary to the original dag (as illustrated in fig. 1c and fig. 1d ). specifically, for any edge (n i , n j ) in the original dag that can be removed without changing the partial ordering, we create a new dummy node m ij , and replace that edge by the two edges (n i , m ij ) and (m ij , n j ). every edge in the modified graph is then required to reproduce the implied partial ordering, and this modified dag is therefore recoverable from an order isomorphism. ## disk embedding: model the disk embedding module takes as input the hidden representations of a sentence encoder (lstm or transformer); we discuss how these representations are obtained in the context of dependency and semantic parsing in § 4.1 and 4.2 respectively. this input undergoes a linear transformation followed by a leakyrelu activation to obtain x g , that is then used to learn disk embeddings. to learn the centers c and the radii r of the disks, we pass x g through a n-layer mlp (where @xmath5: centers and radii c and r are used to compute the protrusion values ℓ ij as in eq. 2. we then use the ℓ ij values in a contrastive loss with a margin α as follows: given that we have access to both positive and negative instances (node pairs in an ancestordescendant relationship vs. all the rest), we can also formulate a maximum likelhood estimation (mle) binary cross-entropy loss, where we directly maximize the probability of a pair of nodes i and j to be either in an ancestor-descendant relationship or not. ## parsing systems our baseline dependency and semantic parsing both determine edge presence between nodes using the biaffine formulation of @xcite (see eq. 7-9), which predicts the most likely parent for each node, along with the grammatical relation between each pair of head and dependent, conditioned on an encoded hidden representation. we replace this with the disk embedding module described in § 3, leaving all other modules unchanged. ## data and settings we use the english-ewt section of universal dependencies (ud; @xcite for dependency parsing, and the amr2.0 dataset @xcite for semantic parsing. ablations. for both tasks, we perform an ablation study on the development data to understand the impact of the choice of the loss function, sampling method, distance function and related settings (see in eq. 3a-3b, centers and radii are computed separately, whereas in the original implementation of suzuki et al. they are learnt jointly as a single vector in which the radius is the last dimension. to understand whether capturing the interaction between centers and radii helps with learning better disk embeddings, we create a (+shared) alternative where we jointly learn the centres and radii as in the original implementation. finally, we build on the intuition of centers and radii informing each other, and propose an additional option on top of shared, (+iter2 and +iter3), where we train an mlp to take c, r and x (n-1) g as input and iteratively refine the centers and radii k times (where @xmath6,3}). all the settings described assume that we include all negative instances (node pairs that are not in an ancestor-descendant relation) as part of the loss computation; however this might lead to a class imbalance problem as there are many more negatives than there are positive instances (∼ 10:1 ratio). we therefore experiment with different sampling methods, including removing descendant-ancestor negatives altogether. we found that only one sampling method lead to performance improvement, i.e., oversampling of parent-child nodes (+sampling). in practice, we multiply the loss of every parent-child pair by a factor (here 2) in order to penalize errors coming from such pairs. we further test the joint impact of this sampling approach together with the auxiliary structure loss (+both). eq. 4 uses a constant margin α for negative samples. however, one can formulate a tailored lower bound on the margin, σ ij , that depends on the relationship between node i and j. we formally prove the existence of such a lower bound in appendix b, and provide an algorithm to identify it (algorithm 1). in practice, however, the use of this tailored margin did not result in a performance improvement for either the dependency or the semantic parsing. for completeness, we include the results in appendix c, for all combinations, we compare two distance functions: ℓ 2 and ℓ 1 norms. we include a list of hyperparameter values in appendix a. ## evaluation for both dependency and semantic parsing tasks, we compare our model output (a tree or a graph) to a reference parse. for dependency parsing, we report accuracy, calculated using two standard measures: unlabelled attachment score (uas), that is the percentage of tokens that are assigned the correct head; and labelled attachment score (las) that is the percentage of tokens that are assigned the correct head and the correct grammatical relation. we use uas for model selection. for semantic parsing, we use mtool foot_7 to report a set of fine-grained f1 scores that reflect the performance of each classifier in the perin parser. edge (presence), (node) label, top (node) reflect the losses introduced in § 4.2; prop(erty prediction) represents a dedicated score on how well we predict named entity subgraphs (the properties), as well as how well we connect them to the rest of the graph. 9 finally, all is a weighted average of these f1 scores. 10 all results are reported as an average of 3 runs, along with standard deviations. ## results the disk embedding loss formulation of @xcite performs considerably worse than all other settings. results in the structure auxiliary loss helps with performance, often in conjunction with oversampling parent-child pairs. results in to have interpretability one has to pay a price in performance. ## analysis do errors correlate with the (graph) distance and the relation between nodes? now that we have access to interpetable representations, we can inspect which relations in a parse tree/graph are challenging to embed correctly. we begin by defining two types of errors w.r.t. the protrusion ℓ ij for a predicted edge (i, j): one where ℓ @xmath7. we use 0 instead of α as the cutoff point because, although not below the desired margin, the sigmoid in eq. 5 will still correctly predict the disk for i containing that of j. we plot these errors against the graph distance between all node pairs, foot_10 and report the % of errors over the total number of node pairs for different values of graph distance. fig. 2 (a) shows that there is an inverse correlation between errors and distance, with parent-child (distance of 1) and grandparentgrandchild relations (distance of 2) displaying the highest numbers of incorrect protrusions; this is particularly striking in the case of semantic parsing and we elaborate more on this when discussing the role of edge permutations below. however, we can see that a large number of incorrect protrusions fall in (-α, 0), especially in the case of dependency parsing, for which the sigmoid will still predict a correct containment. what makes semantic parsing harder? we start answering this question by looking at the results on the dev set where properties (prop) are the ones whose performance is impacted the most. we referred to this in § 4.2 as the edge permutation problem for nodes in named entity substructures which pose a challenge in the absence of explicit alignment information; we hypothesize this might cause a drop in performance and if so, we expect performance to drop more when there are more permutations. fig. 3 shows that there is indeed an effect of the number of permutations on performance, with the baseline system performing better on instances with a large number of permutations. interestingly, in the absence of permutations, our parser performs comparably to the baseline system. edge permutations could also be the main reason behind the large % of local errors in fig. 2(a) . to confirm this, we take a closer look at the breakdown of % protrusion errors for parent-child pairs according to whether both, either or neither node is subjected to permutation. fig. 2(b) shows that when both or either node is permuted, the containment relationship is usually incorrectly predicted. note, however, that whereas the number of these incorrect predictions are large, the overall performance is not overly affected, because when matching a predicted and a gold graph, we look at the node label and not at the node id. using the example in fig. 1(b) , from a matching perspective, we would obtain the same graph swapping the parent node 'name' of 'anna' with the one of 'mary'. we also analyze the difference in performance between trees and graphs, as well as the effect of the number of nodes on performance; due to space limitations we include these results in appendix d.1. in appendix d.3, we discuss whether the size of the parses warrants moving to the hyperbolic space. ## conclusions and future work we have explored disk embeddings as a means to obtain interpretable representations when training a parser that preduces a tree/graph. we showed that previously proposed disk embedding formulations are sub-optimal for the task of parsing, and accordingnly explored alternatives that improve parsing performance. nonetheless, our results suggest that we still need to pay a cost in performance to attain interpretability; this cost is small when parsing into trees, but notable for graphs. we also speculate that this cost might be due to properties of the parser we use, especially in cases where the absence of an alignment between words in a sentence and nodes in a graph allows for many permutations. our work can be considered as a first attempt to bring parsing and 'deep' natural language understanding into the realm of interpretability and representation learning, so that trees and graphs could be used in downstream tasks (e.g., image retrieval), similarly to how word embeddings have been used.