A Differentiable Relaxation of Graph Segmentation and Alignment for AMR Parsing (2021)

Abstract: Abstract Meaning Representations (AMR) are a broad-coverage semantic formalism which represents sentence meaning as a directed acyclic graph. To train most AMR parsers, one needs to segment the graph into subgraphs and align each such subgraph to a word in a sentence; this is normally done at preprocessing, relying on hand-crafted rules. In contrast, we treat both alignment and segmentation as latent variables in our model and induce them as part of end-to-end training. As marginalizing over the structured latent variables is infeasible, we use the variational autoencoding framework. To ensure end-to-end differentiable optimization, we introduce a differentiable relaxation of the segmentation and alignment problems. We observe that inducing segmentation yields substantial gains over using a ‘greedy’ segmentation heuristic. The performance of our method also approaches that of a model that relies on the segmentation rules of Lyu and Titov (2018), which were hand-crafted to handle individual AMR constructions.

## introduction abstract meaning representation (amr; @xcite ) is a broad-coverage semantic formalism which represents sentence meaning as rooted labeled directed acyclic graphs. the representations have been exploited in a wide range of tasks, including text summarization @xcite @xcite , machine translation @xcite , paraphrase detection @xcite and question answering @xcite . an amr graph can be regarded as consisting of multiple concept subgraphs, which can be individually aligned to sentence tokens @xcite . in figure 1 and tokens. for example, '(o / opine-01: arg1 (t / thing))' refers to a combination of the predicate 'opine-01' and a filler of its semantic role arg1. intuitively, this subgraph needs to be aligned to the token 'opinion'. similarly, '(b / boy)' should be aligned to the token 'boy'. given such an alignment and segmentation, it is straightforward to construct a simple parser: parsing can be framed as tagging input tokens with subgraphs (including empty subgraphs), followed by predicting relations between the subgraphs. the key obstacle to training such an amr parser is that the segmentation and alignment between amr subgraphs and words are latent, i.e. not annotated in the data. most previous work adopts a pipeline approach to handling this obstacle. they rely on a prelearned aligner (e.g., @xcite ) to produce the alignment, and apply a rule system to segment the amr subgraph @xcite @xcite @xcite @xcite . while @xcite jointly optimize the parser and the alignment model, the rules handling specific constructions still needed to be crafted to segment the graph. the segmentation rules are relatively complex -e.g., the rules of @xcite targeted 40 different amr subgraph typesand language-dependent. amr has never been intended to be used as an interlingua @xcite and amr banks for individual languages substantially diverge from english amr. for example, spanish amr represents pronouns and ellipsis differently from the english one @xcite . as new amr sembanks in languages other than english are being developed @xcite , domain-specific amr extensions get developed @xcite , and extra constructions are getting introduced to amrs @xcite , eliminating the need for rules while learning graph segmentation from scratch is becoming an important problem to solve. we propose to optimize a graph-based parser that treats the alignment and graph segmentation as latent variables. the graph-based parser consists of two parts: concept identification and relation identification. the concept identification model generates the amr nodes, and the relation identification component decides on the labeled edges. during training, both components rely on latent alignment and segmentation, which are being induced simultaneously. importantly, at test time, the parser simply tags the input with the subgraphs and predicts the relations, so there is no test-time overhead from using the latent-structure apparatus. an extra benefit of this approach, in contrast to encoder-decoder amr models @xcite @xcite ) is its transparency, as one can readily see which input token triggers each subgraph. 1 to develop our parser, we frame the alignment and segmentation problems as choosing a generation order of concept nodes, as we explain in section 2.2. as marginalization over the latent generation orders is infeasible, we adopt the variational auto-encoder (vae) framework @xcite . intuitively, a trainable neural module (an encoder in the vae) is used to sample a plausible generation order (i.e., a segmentation plus an alignment), which is then used to train the parser (a decoder in the vae). as one cannot 'differentiate through' a sample of discrete variables to train the encoder, we introduce a differentiable relaxation which makes our objective end-to-end differentiable. we experiment on the amr 2.0 and 3.0 datasets. we compare to a greedy segmentation heuristic, inspired by @xcite , that produces a seg-mentation deterministically and provides a strong baseline to our segmentation induction method. we also use a version of our model with segmentation induction replaced by a hand-crafted rule-based segmentation system from previous work; foot_1 it can be thought of as an upper bound on how well induction can work. on amr 2.0 (ldc2016e25), we found that our vae system obtained a competitive smatch score of 76.1, reducing the gap between using the segmentation heristic (75.2) and the rules exploiting the prior knowledge about amr (76.8). on amr 3.0 (ldc2020t02), the vae system gets even closer to the rule-based system (75.5 vs 75.7), possibly because the rules were designed for amr 2.0. our main contributions are: our method makes very few assumptions about the nature of the graphs, so it may be effective in other tasks that can be framed as graph prediction (e.g., executable semantic parsing, liang 2016, or scene graph prediction, @xcite . ## estimating latent generation order we show how to estimate the latent generation order jointly with the parser, as also illustrated in figure 5 . ## parsing while we relied on the latent variable machinery to train the parser, we do not use it at test time. in fact, the encoder q φ (o|g, x) is discarded after training. at test time, the first step is to predict sets of concept nodes for every token using the concept identification model p θ (v|x, o) (as shown in figure 4 ). note that the token-specific autoregressive models can be run in parallel across tokens. the second step is predicting relations between all the nodes, relying on the relation identification model p θ (e|x, o, v). ## experiments we experiment on ldc2016e25 (amr2.0) and ldc2020t02 (amr3.0). the evaluation is based on smatch @xcite , and the evaluation tool of @xcite . we compare our generation-order induction framework to pre-set segmentations, i.e., producing the segmentation on a preprocessing step. we vary the segmentation methods while keeping the rest of the model identical to our full model (i.e., the same autoregressive model and the learned alignment). we provide ablation studies for our induction framework. we further provide visualization of the induced generation order, along with extra details, in appendix. ## related work a wide range of approaches for amr parsing have been explored, including graph-based models @xcite @xcite , transitionbased models @xcite , grammar-based models @xcite @xcite and neural autoregressive models @xcite @xcite @xcite . the majority of strong parsers rely on explicit graph segmentation in training. typically, the segmentation is dealt with hand-crafted rules, with rule templates developed by studying training set statistics and ensuring the necessary level of coverage. alternatively, @xcite ; @xcite ; lindemann et al. (2020); peng et al. (2015) using existing grammar formalisms to segment the amr graphs. astudillo et al. (2020); lee et al. (2020) -while not not relying on graph recategorization rules -use a rule system to 'pack' and 'unpack' nodes. in recent work, strong results more generally, outside of amr parsing, differentiable relaxations of latent structure representations have received attention in nlp @xcite , including previous applications of the perturb-and-map framework @xcite . from a more general goal perspective -inducing a segmentation of a linguistic structure -our work is related to tree-substitution grammar induction @xcite , the dop paradigm @xcite and unsupervised semantic parsing @xcite , though the methods used in that previous work are very different from ours. ## conclusions to eliminate hand-crafted segmentation systems used in previous amr parsers, we cast the alignment and segmentation as generation-order induction. we propose to treat this generation order as a latent variable in a vae framework. our method outperforms a simple segmentation heuristic and approaches the performance of a method using rules designed to handle specific amr constructions. importantly, while the latent variable modeling machinery is used in training, the parser is very simple at test time. it tags the input words with amr concept nodes with autoregressive models and then predicts relations between the nodes independently from each other. vanilla sequence-to-sequence models are known to struggle with out-of-distribution generalization @xcite , and, in the future work, it would be interesting to see if this holds for amr and if such more constrained and structured methods as ours can better deal with this more challenging but realistic setting.