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:
- 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).
- Cycles: Relations that loop back on themselves.
- Non-projectivity: Crossing semantic relations that cannot be represented in a simple tree.
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.
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