Probabilistic, Structure-Aware Algorithms for Improved Variety, Accuracy, and Coverage of AMR Alignments (2021)

Abstract: We present algorithms for aligning components of Abstract Meaning Representation (AMR) graphs to spans in English sentences. We leverage unsupervised learning in combination with heuristics, taking the best of both worlds from previous AMR aligners. Our unsupervised models, however, are more sensitive to graph substructures, without requiring a separate syntactic parse. Our approach covers a wider variety of AMR substructures than previously considered, achieves higher coverage of nodes and edges, and does so with higher accuracy. We will release our LEAMR datasets and aligner for use in research on AMR parsing, generation, and evaluation.

## introduction research with the abstract meaning representation (amr; banarescu et al., 2013), a broadcoverage semantic annotation framework in which sentences are paired with directed acyclic graphs, must contend with the lack of gold-standard alignments between words and semantic units in the english data. a variety of rule-based and statistical algorithms have sought to fill this void, with improvements in alignment accuracy often translating into improvements in amr parsing accuracy (pourdamghani et al., 2014; naseem et al., 2019; liu et al., 2018). yet current alignment algorithms still suffer from limited coverage and less-than-ideal accuracy, constraining the design and accuracy of parsing algorithms. where parsers use latent alignments (e.g., lyu and titov, 2018; cai and lam, 2020), explicit alignments can still facilitate evaluation and error analysis. moreover, amr-to-text generation research and applications using amr stand to benefit from accurate, human-interpretable alignments. we present linguistically enriched amr (leamr) alignment, which achieves full graph cov-erage via four distinct types of aligned structures: subgraphs, relations, reentrancies, and duplicate subgraphs arising from ellipsis. this formulation lends itself to unsupervised learning of alignment models. advantages of our algorithm and released alignments include: (1) much improved coverage over previous datasets, (2) increased variety of the substructures aligned, including alignments for all relations, and alignments for diagnosing reentrancies, (3) alignments are made between spans and connected substructures of an amr, (4) broader identification of spans including named entities and verbal and prepositional multiword expressions. contributions are as follows: ## related work the main difficulty presented by amr alignment is that it is a many-to-many mapping problem, with gold alignments often mapping multiple tokens to multiple nodes while preserving amr structure. previous systems use various strategies for aligning. they also have differing approaches to what types of substructures of amr are aligned-whether they are nodes, subgraphs, or relations-and what they are aligned to-whether individual tokens, token spans, or syntactic parses. two main alignment strategies remain dominant, though they may be combined or extended in various ways: rule-based strategies as in flanigan et al. (2014), flanigan et al. (2016), liu et al. (2018), and szubert et al. (2018), and statistical strategies using expectation-maximization as in pourdamghani et al. (2014). jamr. the jamr system (flanigan et al., 2014, 2016) aligns token spans to subgraphs using iterative application of an ordered list of 14 rules which include exact and fuzzy matching. jamr alignments form a connected subgraph of the amr by the nature of the rules being applied. a disadvantage of jamr is that it lacks a method for resolving ambiguities, such as repeated tokens, or of learning novel alignment patterns. isi. the isi system (pourdamghani et al., 2014) produces alignments between tokens and nodes and between tokens and relations via an expectation-maximization (em) algorithm in the style of ibm model 2 (brown et al., 1988). first, the amr is linearized; then em is applied using a symmetrized scoring function of the form p(a | t) + p(t | a), where a is any node or edge in the linearized amr and t is any token in the sentence. graph connectedness is not enforced for the elements aligning to a given token. compared to jamr, isi produces more novel alignment patterns, but also struggles with rare strings such as dates and names, where a rule-based approach is more appropriate. extensions and combinations. tamr (tuned abstract meaning representation; liu et al., 2018) uses the jamr alignment rules, along with two others, to produce a set of candidate alignments for the sentence. then, the alignments are "tuned" with a parser oracle to select the candidates that correspond to the oracle parse that is most similar to the gold amr. some amr parsers (naseem et al., 2019; fernandez astudillo et al., 2020) ## an all-inclusive formulation of amr alignment aligning amrs to english sentences is a vexing problem not only because the english training data lacks gold alignments, but also because amrsunlike many semantic representations-are not designed with a derivational process of form-function subunits in mind. rather, each amr graph represents the full-sentence meaning, and amr anno- figure 1 : amr and alignments for the sentence "most of the students want to visit new york when they graduate." alignments are differentiated by colors: blue (subgraphs), green (duplicate subgraphs), and orange (relations). relations that also participate in reentrancy alignments are bolded. we advocate here for a definition of alignment that is principled-achieving full coverage of the graph structure-while being framework-neutral and easy-to-understand, by aligning graph substructures to shallow token spans on the form side, rather than using syntactic parses. we do use structural considerations to constrain alignments on the meaning side, but by using spans on the form side, we ensure the definition of the alignment search space is not at the mercy of error-prone parsers. definitions. given a tokenized sentence w and its corresponding amr graph g, a complete alignment assumes a segmentation of w into spans s, each containing one or more contiguous tokens; and puts each of the nodes and edges of g in correspondence with some span in s. a span may be aligned to one or more parts of the amr, or else is null-aligned. individual alignments for a sentence are grouped into four layers: subgraph alignments, duplicate subgraph alignments, relation alignments, and reentrancy alignments. these are given for an example in figure 1 . all alignments are between a single span and a substructure of the amr. a span may be aligned in multiple layers which are designed to capture different information. within the subgraph layer, alignments are mutually exclusive with respect to both spans and amr components. the same holds true within the relation layer. every node will be aligned exactly once between the subgraph and duplicate subgraph layers. every edge will be aligned exactly once between the subgraph and relation layers, and may additionally have a secondary alignment in the reentrancy layer. ## released data we release a dataset foot_1 of the four alignment layers reflecting correpondences between english text and various linguistic phenomena in gold amr graphs-subgraphs, relations (including argument structures), reentrancies (including coreference, control, etc.), and duplicate subgraphs. automatic alignments cover the ≈60,000 sentences of the ldc2020t02 dataset (knight et al., 2020) and ≈1,500 sentences of the little prince. we manually created gold alignments for evaluating our automatic aligner, split into a development set (150 sentences) and a test set (200 sen- type triggered by example coref a pronoun (including possessive or reflexive) (anaphora) i love my house repetition a repeated name or non-pronominal phrase (non-anaphoric coreference) the u.s. promotes american goods coordination coordination of two or more phrases sharing an argument they cheered and celebrated control control verbs, control nouns, or control adjectives i was afraid to speak up adjunct control control within an adjunct phrase i left to buy some milk; mary cooked while listening to music unmarked adjunct control control within an adjunct phrase with only a bare verb and no subordinating conjunction mary did her homework listening to music comparative control a comparative construction be as objective as possible pragmatic reentrancies that must be resolved using context john met up with a friend ## leamr aligner we formulate statistical models for the alignment layers described above-subgraphs, duplicate subgraphs, relations, and reentrancies-and use the expectation-maximization (em) algorithm to estimate probability distributions without supervision, with a decoding procedure that constrains aligned units to obey structural requirements. in line with flanigan et al. (2014, 2016), we use rulebased preprocessing to align some substructures using string-matching, morphological features, etc. before delving into the models and algorithm, we motivate two important characteristics: structure-preserving. constraints on legal candidates during alignment ensure that at any point only connected substructures may be aligned to a span. thus, while our aligner is probabilistic like the isi aligner, it has the advantage of preserving the amr graph structure. projection distance. the scores calculated for an alignment take into account a distance metric designed to encourage locality-tokens that are close together in a sentence are aligned to subtructures that are close together in the amr graph. we define the projection distance dist(n1,n2) between two neighboring nodes n1 and n2 to be the signed distance in the corresponding sentence between the span aligned to n1 and the span aligned to n2. this motivates the model to prefer alignments whose spans are close together when aligning nodes which are close together-particularly useful when a word occurs twice with identical subgraphs. thus, our aligner relies on more information from the amr graph structure than other aligners (note that the isi system linearizes the graph). further details are given in §5.2. ## experimental setup sentences are preprocessed with the stanza library (qi et al., 2020) to obtain lemmas, part-of-speech tags, and named entities. we identify token spans using a combination of named entities and a fixed list of multiword expressions (details are given in appendix b). coreference information, which is used to identify legal candidates in the reentrancy alignment phase, is obtained using neural-coref. @xcite lemmas are used in each alignment phase to normalize representation of spans, while parts of speech and coreference are used to restrict legal candidates in the relation and reentrancy alignment phases. we tune hyperparameters, including penalties for duplicate alignments and our factorized backoff probability, on the development set. ## results for nodes (or edges) and tokens respectively. this partial credit is calculated for each gold alignment and the closest matching predicted alignment with nodes (or edges) n 1 and n 2 and tokens t 1 and t 2 . coverage is the percentage of relevant amr components that are aligned. our aligner shows improvements over previous aligners in terms of coverage and accuracy even when using a partial credit metric for evaluation. we demonstrate greater coverage, including coverage of phenomena not aligned by previous systems. ## conclusions we demonstrate structure-aware amr aligners that combine the best parts of rule-based and statistical methods for amr alignment. we improve on previous systems in terms of accuracy and particularly in terms of alignment coverage and variety of amr components to be aligned.