A Transition-Based Algorithm for Unrestricted AMR Parsing

David Vilares, Carlos Gómez-Rodríguez

Abstract

Abstract Meaning Representation (AMR) captures the semantic structure of sentences as rooted, labeled graphs. Traditional parsers often struggle with the non-linear nature of these graphs, requiring specialized heuristics to handle reentrancy and cycles. This paper presents AMR-COVINGTON, a transition-based parser that adapts the Covington algorithm to handle unrestricted graph structures natively. By removing tree-based constraints, the model achieves state-of-the-art performance in reentrancy detection while maintaining competitive overall Smatch scores.

Introduction: The Complexity of Semantic Graphs

In Natural Language Processing, AMR serves as a blueprint for a sentence's meaning. Unlike standard syntax trees, AMR representations are graphs that allow for:

  1. Reentrancy: A single concept participating in multiple semantic roles (e.g., in "The boy wants to go," the "boy" is both the wanter and the goer).
  2. Cycles: Relations that loop back on themselves.
  3. Non-projectivity: Crossing semantic relations that cannot be represented in a simple tree.
An example of an AMR graph showing reentrancy and semantic labeling.

Most transition-based parsers, originally designed for dependency trees, require "hacks" like SWAP operations or post-processing to handle these properties. AMR-COVINGTON addresses this by utilizing an algorithm designed to be unrestricted from the outset.

Methodology: The AMR-COVINGTON Parser

The core of the system is an adaptation of the Covington algorithm (2001). While originally intended for dependency parsing, Covington is unique because it systematically compares every new word against all previously processed words.

Removing Constraints

The researchers found that by simply removing acyclicity and single-head constraints, the Covington algorithm becomes a natural fit for AMR graphs. The parser manages state using a buffer ($\beta$) for incoming words and two lists ($\lambda_1, \lambda_2$) to track processed concepts.

Transition System

The parser introduces specific transitions to bridge the gap between words and semantic concepts:

  • CONFIRM: Converts a word into a concept node.
  • BREAKDOWN: Decomposes a single word into multiple concepts (e.g., "father" mapping to both a relational role and the concept of a father).
  • REDUCE: Removes functional words, such as prepositions, that do not have their own node in the graph.

The system is driven by three feed-forward neural networks that serve as an "oracle," predicting the next transition, the appropriate relation label, and the concept to be generated.

Experimental Results

The model was evaluated on the LDC2015E86 corpus, a standard benchmark containing nearly 20,000 annotated graphs.

Performance comparison across various metrics, highlighting the model's strength in reentrancy detection.

As shown in the results table, AMR-COVINGTON achieved a 64% Smatch score, placing it at the state-of-the-art for transition-based parsers. Notably, it significantly outperformed previous models in reentrancy detection, scoring 44 compared to the previous best of 41. This improvement stems from the algorithm's systematic look-back mechanism, which ensures that all potential parents for a node are considered. The neural transition classifier itself reached an accuracy of approximately 86%.

Discussion and Conclusion

While highly effective, the AMR-COVINGTON approach involves a trade-off in computational complexity. The systematic comparison of nodes results in a worst-case runtime of $O(n^2)$, which is slower than the linear $O(n)$ time of tree-constrained parsers. Additionally, the BREAKDOWN transition proved difficult for the neural oracle to master, with a recall of only 50%.

Despite these challenges, the simplicity of the unrestricted approach demonstrates that complex graph structures can be handled natively without the need for specialized "hacks," providing a robust foundation for future semantic parsing research.

Summary updated

Abstract

Non-projective parsing can be useful to handle cycles and reentrancy in AMR graphs. We explore this idea and introduce a greedy left-to-right non-projective transition-based parser. At each parsing configuration, an oracle decides whether to create a concept or whether to connect a pair of existing concepts. The algorithm handles reentrancy and arbitrary cycles natively, i.e. within the transition system itself. The model is evaluated on the LDC2015E86 corpus, obtaining results close to the state of the art, including a Smatch of 64%, and showing good behavior on reentrant edges.
BibTeX
@inproceedings{vilares2018transition,
  author = {David Vilares and Carlos Gómez-Rodríguez},
  title = {{A Transition-Based Algorithm for Unrestricted AMR Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2018},
  doi = {10.18653/v1/n18-2023},
}
Figure