Grammar-Constrained Neural Semantic Parsing with LR Parsers

Artur Baranowski, Nico HochgeschwenderACL 2021

TL;DR

This paper introduces a novel method for neural semantic parsing that leverages LR parsers to enforce grammatical constraints during the generation of logical forms. By integrating a standard LR parser into an encoder-decoder framework, the approach ensures syntactically valid outputs without modifying the neural network architecture, leading to improved performance on semantic parsing tasks.

What Problem Does This Paper Address?

Semantic parsing aims to translate natural language utterances into structured meaning representations, often in the form of logical forms like SQL queries or programming code. Many of these logical forms can be described by context-free grammars. A key challenge is ensuring that the generated logical forms are syntactically correct according to these grammars. Traditional approaches often involve complex modifications to neural network architectures or predict full derivation trees, which can be computationally expensive and intrusive. This paper addresses the need for a more efficient and less intrusive way to enforce grammatical constraints in modern neural semantic parsers, specifically targeting logical forms that can be described by deterministic context-free grammars.

Methods

The core contribution of this paper is the integration of an LR parser into a standard encoder-decoder neural network architecture for semantic parsing. Instead of modifying the neural network itself, the LR parser acts as a constraint during the decoding process.

Here's how it works:

  • Encoder-Decoder Framework: The paper uses a standard recurrent encoder-decoder (SEQ2SEQ) model, similar to those used in neural machine translation. The encoder processes the natural language input, and the decoder generates the target logical form token by token.
  • LR Parser Integration: The LR parser is used to guide the decoder's output. At each decoding step, the decoder queries the current state of the LR parser to determine the set of syntactically valid next tokens. The decoder then generates a probability distribution over these valid tokens, and the parser consumes the chosen token to update its state.
  • Bottom-Up Constraint Enforcement: Unlike many previous grammar-guided decoding methods that work top-down by predicting derivation trees, this approach enforces constraints in a bottom-up fashion by directly generating lexical tokens (the leaves of the syntax tree). This is conceptually simpler and avoids the need to generate full parse trees.
  • Inference-Time Constraint: The grammatical constraints are enforced only during inference, meaning the neural network itself doesn't need to explicitly learn the grammar. This reduces computational overhead and makes the approach more adaptable to existing SEQ2SEQ frameworks.
  • Handling Non-Determinism: When there's more than one possible next token according to the LR parser, the decoder is invoked to choose among them. If there's only one valid option, the decoder is bypassed, further streamlining the process.

Datasets

The paper evaluates its approach on two standard semantic parsing datasets:

  • GEOQUERY: A dataset for text-to-SQL queries.
  • ATIS: A dataset for natural language understanding in the air travel domain.

The authors use the same training, validation, and test splits as a previous work (Finegan-Dollak et al., 2018) to ensure comparability. They note that these datasets feature complex queries with low levels of redundancy, which they hypothesize will highlight the benefits of grammar-constrained decoding.

Key Insights and Ideas

  • Simplicity and Efficiency: The most significant insight is that enforcing grammatical constraints can be achieved effectively and efficiently by integrating an external LR parser with a standard encoder-decoder model, rather than by fundamentally altering the neural architecture.
  • Offloading Syntactic Learning: By using an LR parser, the neural network is relieved of the burden of learning the target language's syntax. This can be particularly beneficial for ensuring balanced expressions and preventing syntax errors, especially over long sequences.
  • Bottom-Up Advantage: Directly generating lexical tokens and using a bottom-up parser is a more direct and potentially less error-prone approach than generating full derivation trees.
  • Attention vs. Grammar: The results suggest that while attention mechanisms help with long-range dependencies, explicit grammatical constraints (via LR parsing) are crucial for resolving complex syntactic structures and achieving higher accuracy, especially in "oracle" trials where entity anonymization simplifies the task.

Key Results

The paper presents preliminary evaluation results on GEOQUERY and ATIS datasets, comparing their grammar-constrained approach (Ours) against a recurrent SEQ2SEQ baseline and an attentional SEQ2SEQ model from Finegan-Dollak et al. (2018).

  • GEOQUERY:
    • Standard Trials: Ours achieved 34% exact match accuracy, compared to 27% for the baseline without attention.
  • Oracle Trials: Ours achieved 63% exact match accuracy, significantly outperforming the baseline's 49%. With attention, Ours reached 69%, while the baseline with attention reached 73%.
  • ATIS:
    • Standard Trials: Ours achieved 9% exact match accuracy, compared to 8% for the baseline without attention.
  • Oracle Trials: Ours achieved 48% exact match accuracy, significantly outperforming the baseline's 14%. With attention, Ours reached 55%, while the baseline with attention reached 57%.

The results show that enforcing grammatical constraints with LR parsers leads to improved performance, particularly in oracle trials where the task is simplified by entity anonymization. The authors note that the greatest improvements are seen in oracle trials without an attention layer, suggesting that the grammar constraint is the primary driver of accuracy in these scenarios.

Limitations and Future Work

  • Deterministic Context-Free Grammars: The current approach is limited to deterministic context-free grammars. The authors acknowledge that generalizing to more complex, non-deterministic grammars (using GLR parsers) might incur additional computational costs proportional to the grammar's non-determinism.
  • Training Mismatch: A mismatch exists between training (where the decoder might generate syntactically invalid sequences) and inference (where constraints are enforced). The paper addresses this by filtering target sequences during training, but it's a point of consideration.
  • Future Work: The authors plan to:
  • Expand trials to include other logical forms beyond SQL.
  • Generalize the approach to context-free grammars using GLR parsers.
  • Enforce grammatical constraints at training time, not just inference time.

Summary updated

BibTeX
@inproceedings{baranowski2021grammar,
  author = {Artur Baranowski and Nico Hochgeschwender},
  title = {{Grammar-Constrained Neural Semantic Parsing with LR Parsers}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure