Abstract
Semantic parses are directed acyclic graphs (DAGs), so semantic parsing should be modeled as graph prediction. But predicting graphs presents difficult technical challenges, so it is simpler and more common to predict the linearized graphs found in semantic parsing datasets using well-understood sequence models. The cost of this simplicity is that the predicted strings may not be well-formed graphs. We present recurrent neural network DAG grammars, a graph-aware sequence model that ensures only well-formed graphs while sidestepping many difficulties in graph prediction. We test our model on the Parallel Meaning Bank—a multilingual semantic graphbank. Our approach yields competitive results in English and establishes the first results for German, Italian and Dutch.
Introduction: The Graph Prediction Challenge
In semantic parsing, the goal is to translate natural language into machine-readable meaning representations. Formalisms like Abstract Meaning Representation (AMR) or Discourse Representation Theory (DRT) are naturally structured as Directed Acyclic Graphs (DAGs).
Traditionally, researchers have bypassed the complexities of direct graph prediction by flattening these structures into strings (linearization) and applying standard sequence-to-sequence (seq2seq) models. However, these models are "graph-blind"; they often produce outputs with structural errors, such as mismatched brackets or unbound variables, which fail to form valid graphs. Conversely, dedicated graph prediction models often require complex latent variables to manage the multiple valid orderings of a single graph. This paper introduces Recurrent Neural Network DAG Grammars (RNN-DAGGs) to achieve the simplicity of sequence prediction while guaranteeing structural validity.
Methodology: Graph-Aware String Rewriting
The core innovation of RNN-DAGGs is the use of a restricted DAG grammar to guide a neural sequence model. This approach ensures that every generated output is a mathematically well-formed graph by construction.
1. Restricted DAG Grammar
The authors adapt a grammar capable of decomposing a DAG into a unique sequence of production rules. This grammar serves as a structural blueprint, defining the valid transitions at each step of the generation process.
2. Neural Realizer
The model employs an encoder-decoder architecture inspired by Recurrent Neural Network Grammars (RNNGs):
- Encoder: A bidirectional LSTM processes the input sentence to capture contextual information.
- Decoder: A stack-LSTM tracks the partial graph structure. It selects from three primary actions:
GEN-FRAG(generates graph structure),GEN-LABEL(fills in specific concepts using a copy mechanism), andREDUCE(completes a branch and integrates it into the parent structure).
Evaluation and Key Results
The model was evaluated using the Parallel Meaning Bank (PMB), a multilingual semantic graphbank covering English, German, Italian, and Dutch.
Structural Integrity and Accuracy
On English "Gold" data, the RNN-DAGG significantly improved structural reliability. The percentage of ill-formed graphs dropped from 4.12% in a standard seq2seq baseline to just 0.40%. Furthermore, the model achieved an F1 score of 73.55, outperforming previous state-of-the-art systems.
Multilingual Success
The paper establishes the first published results for German, Italian, and Dutch DRS parsing. By utilizing a copy mechanism to select words from the input sentence, the model demonstrates strong cross-lingual portability. In "cross-silver" settings (training on English and testing on other languages), the model maintained high performance, such as an F1 score of 71.12 for Italian, suggesting that the underlying semantic DAG structure is largely language-agnostic.
Conclusion
RNN-DAGGs provide a robust middle ground between simple sequence models and complex graph predictors. By embedding grammatical constraints directly into the decoding process, the model eliminates the need for post-processing "fixer" scripts and ensures that semantic parses are always well-formed. Future work aims to extend this formalism to other graph-based representations like AMR and Minimal Recursion Semantics (MRS).
Summary updated