Abstract
Federico Fancellu, Sorcha Gilroy, Adam Lopez, Mirella Lapata. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).
2019.
Semantic parsing—the task of mapping natural language sentences to formal meaning representations—is a cornerstone of computational linguistics. This paper introduces RNN DAG Grammars, a neural parsing model designed to ensure that generated semantic graphs are always structurally valid. By predicting grammar rules instead of raw strings, the model achieves state-of-the-art results on multilingual datasets while virtually eliminating the "broken" outputs common in standard sequence models.
The Structural Challenge in Semantic Parsing
In semantic parsing, the goal is to map a natural language sentence (e.g., "Every ship in the dock needs a big anchor") into a formal representation, often a Directed Acyclic Graph (DAG). These graphs capture the entities and the complex relationships between them.
Traditionally, researchers "linearize" these graphs into strings of text to use standard sequence-to-sequence (seq2seq) models. However, seq2seq models lack an inherent understanding of graph geometry. They frequently produce "ill-formed" outputs—such as unbalanced brackets or undefined variables—which are useless for downstream reasoning tasks. The authors sought a model that combines the training ease of sequence models with the structural rigor of formal grammars.
RNN DAG Grammars: A Graph-Aware Approach
The authors propose a model that predicts a sequence of grammar productions rather than characters or words. This approach uses a "restricted DAG grammar" to define valid graph constructions, making it mathematically impossible to generate a structurally unsound graph.
Model Architecture
The system employs an encoder-decoder architecture:
- Encoder: A Bidirectional LSTM processes the input sentence, incorporating word embeddings, POS tags, and dependency labels to capture rich contextual information.
- Decoder (Stack-LSTM): The decoder maintains a stack of partial graph fragments and selects from three primary actions at each step:
GEN-FRAG(creates new nodes/edges),GEN-LABEL(assigns semantic labels), andREDUCE(combines fragments).
A copy mechanism is also integrated, allowing the model to "point" back to the input sentence to handle named entities or rare words by copying lemmas directly into the graph.
Experimental Evaluation
The model was evaluated using the Parallel Meaning Bank (PMB), a multilingual corpus covering English, German, Italian, and Dutch. The researchers converted Discourse Representation Structures (DRS) from the PMB into DAGs for training and testing. They utilized both "Gold" (expert-verified) and "Silver" (automatically labeled) data.
Key Results
- Structural Reliability: While standard seq2seq models produced ill-formed graphs in 4% to 20% of cases, the RNN DAG Grammar reduced this error rate to just 0.4%.
- Performance: The model achieved an F1 score of 73.55 on the English gold test set, significantly outperforming seq2seq baselines.
- Multilingual Success: The paper provides the first reported results for semantic graph parsing in German, Italian, and Dutch within this framework, demonstrating the model's ability to handle language-agnostic meaning representations.
Conclusion
By using a formal grammar as a "safety rail," the RNN DAG Grammar ensures that neural models remain grounded in structural logic. While highly effective, the model showed some sensitivity to noise in "silver" data, where disconnected graphs can violate grammar assumptions. Future work may explore different generation orders and the application of this method to other formalisms like Abstract Meaning Representation (AMR).
Summary updated