AMR Parsing via Graph-Sequence Iterative Inference (2020)

Abstract: We propose a new end-to-end model that treats AMR parsing as a series of dual decisions on the input sequence and the incrementally constructed graph. At each time step, our model performs multiple rounds of attention, reasoning, and composition that aim to answer two critical questions: (1) which part of the input sequence to abstract; and (2) where in the output graph to construct the new concept. We show that the answers to these two questions are mutually causalities. We design a model based on iterative inference that helps achieve better answers in both perspectives, leading to greatly improved parsing accuracy. Our experimental results significantly outperform all previously reported Smatch scores by large margins. Remarkably, without the help of any large-scale pre-trained language model (e.g., BERT), our model already surpasses previous state-of-the-art using BERT. With the help of BERT, we can push the state-of-the-art results to 80.2% on LDC2017T10 (AMR 2.0) and 75.4% on LDC2014T12 (AMR 1.0).

## introduction abstract meaning representation (amr) @xcite is a broad-coverage semantic formalism that encodes the meaning of a sentence as a rooted, directed, and labeled graph, where nodes represent concepts and edges represent relations (see an example in figure 1 ). amr parsing is the task of transforming natural language text into amr. one biggest challenge of amr parsing is the lack of explicit alignments between nodes (concepts) in the graph and words in the text. this characteristic not only poses great difficulty in concept ## related work & background on a coarse-grained level, we can categorize existing amr parsing approaches into two main classes: two-stage parsing @xcite @xcite uses a pipeline design for concept identification and relation prediction, where the concept decisions precede all relation decisions; one-stage parsing constructs a parse graph incrementally. for more fine-grained analysis, those one-stage parsing methods can be further categorized into three types: transitionbased parsing @xcite @xcite @xcite @xcite processes a sentence from left-to-right and constructs the graph incrementally by alternately inserting a new node or building a new edge. seq2seq-based parsing @xcite @xcite views parsing as sequence-to-sequence transduction by some linearization of the amr graph. the concept and relation prediction are then treated equally with a shared vocabulary. the third class is graph-based parsing @xcite , where at each time step, a new node along with its connections to existing nodes are jointly decided, either in order @xcite or in parallel @xcite . so far, the recip- the boy must not go the boy must not go obligate-01 boy go-02 -arg2 a r g 0 p o l a r i t y obligate-01 ? go-02 arg2 a r g 0 obligate-01 go-02 ? arg2 p o l a r i t y (a) (b) the current partial (solid) and full (solid + dashed) amr graphs for the sentence "the boy must no go" rocal causation of relation prediction and concept prediction has not been closely-studied and wellutilized. there are also some exceptions staying beyond the above categorization. peng et al. (2015) introduce a synchronous hyperedge replacement grammar solution. pust et al. (2015) regard the task as a machine translation problem, while artzi et al. (2015) adapt combinatory categorical grammar. groschwitz et al. (2018); lindemann et al. (2019) view amr graphs as the structure am algebra. ## motivation our approach is inspired by the deliberation process when a human expert is deducing a semantic graph from a sentence. the output graph starts from an empty graph and spans incrementally in a node-by-node manner. at any time step of this process, we are distilling the information for the next expansion. we call it expansion because the new node, as an abstract concept of some specific text fragments in the input sentence, is derived to complete some missing elements in the current semantic graph. specifically, given the input sentence and the current partially constructed graph, we are answering two critical questions: which part of the input sequence to abstract, and where in the output graph to construct the new concept. for instance, figure 1(a ) and (b) show two possible choices for the next expansion. in figure 1 (a), the word "boy" is abstracted to the concept boy to complement the subject information of the event go-02. on the the boy wants the girl to believe him. attention figure 2 : overview of the dual graph-sequence iterative inference for amr parsing. given the current graph g i and input sequence w . the inference starts with an initial concept decision x 0 and follows the inference chain the details of f and g are shown in red and blue boxes, where nodes in graph and tokens in sequence are selected via attention mechanisms. we believe the mutual causalities, as described above, are useful for action disambiguation and harmonious decision making, which eventually result in more accurate parses. we formulate amr parsing as a series of dual graph-sequence decisions and design an iterative inference approach to tackle each of them. it is sort of analogous to the cognition procedure of a person, who might first notice part of the important information in one side (graph or sequence), then try to confirm her decision at the other side, which could just refute her former hypothesis and propose a new one, and finally converge to a conclusion after multiple rounds of reasoning. ## training & prediction our model is trained with the standard maximum likelihood estimate. the optimization objective is to maximize the sum of the decomposed step-wise log-likelihood, where each is the sum of concept, edge, and edge label probabilities. to facilitate training, we create a reference generation order of nodes by running a breadth-first-traversal over target amr graphs, as it is cognitively appealing (core-semantic-first principle, @xcite and the effectiveness of pre-order traversal is also empirically verified by @xcite in a depth-first setting. for the generation order for sibling nodes, we adopt the uniformly random order and the deterministic order sorted by the relation frequency in a 1 : 1 ratio at first then change to the deterministic order only in the final training steps. we empirically find that the deterministic-afterrandom strategy slightly improves performance. during testing, our model searches for the best output graph through beam search based on the log-likelihood at each spanning step. the time complexity of our model is o(k|v |), where k is the beam size, and |v | is the number of nodes. ablated models as pointed out by @xcite , the precise set of graph re-categorization rules differs among different works, making it difficult to distinguish the performance improvement from model optimization and carefully designed rules. in addition, only recent works @xcite @xcite have started to utilize the large-scale pretrained language model, bert @xcite . therefore, we also include ablated models for addressing two questions: (1) how dependent is our model on performance from handcrafted graph re-categorization rules? (2) how much does bert help? we accordingly implement three ablated models by removing either one of them or removing both. the ablation study not only reveals the individual effect of two model components but also helps facilitate fair comparisons with prior works. ## conclusion we presented the dual graph-sequence iterative inference method for amr parsing. our method constructs an amr graph incrementally in a nodeby-node fashion. each spanning step is explicitly characterized as answering two questions: which parts of the sequence to abstract, and where in the graph to construct. we leverage the mutual causalities between the two and design an iterative inference algorithm. our model significantly advances the state-of-the-art results on two amr corpora. an interesting future work is to make the number of inference steps adaptive to input sentences. also, the idea proposed in this paper may be applied to a broad range of structured prediction tasks (not only restricted to other semantic parsing tasks) where the complex output space can be divided into two interdependent parts with a similar iterative inference process to achieve harmonious predictions and better performance.