A Generative Model for Parsing Natural Language to Meaning Representations

Wei Lu, Hwee Tou Ng, Wee Sun Lee, Luke S. ZettlemoyerEMNLP 2008 · OpenReview

Abstract

In this paper, we present an algorithm for learning a generative model of natural language sentences together with their formal meaning representations with hierarchical structures. The model is applied to the task of mapping sentences to hierarchical representations of their underlying meaning. We introduce dynamic programming techniques for efficient training and decoding. In experiments, we demonstrate that the model, when coupled with a discriminative reranking technique, achieves state-of-the-art performance when tested on two publicly available corpora. The generative model degrades robustly when presented with instances that are different from those seen in training. This allows a notable improvement in recall compared to previous models.

Introduction

The goal of semantic parsing is to translate human language into a machine-readable format, such as a Prolog query. Traditionally, researchers have relied on probabilistic grammars—sets of rules defining how words map to meanings and how those meanings combine. However, these systems often suffer from a "grammar bottleneck": if a specific rule or lexical entry was not encountered during training, the parser fails to produce an output, leading to low recall. Furthermore, training is complicated by the fact that word-to-meaning alignments are typically hidden variables that must be inferred.

Methodology

The Hybrid Tree Model

The authors propose a generative model defined over hybrid trees. In these trees, nodes can be either natural language words or meaning representation (MR) tokens. Instead of using an explicit grammar, the model builds trees by recursively creating nodes at each level according to a Markov process. This allows for a more flexible "implicit grammar" that generalizes better to unseen structures.

A hybrid tree structure interleaving natural language words and meaning representation tokens.

Treating words and meaning tokens as part of the same tree structure simplifies the alignment problem, allowing the model to learn the relationship between the two simultaneously. The model "degrades robustly"; if it encounters an unfamiliar sentence structure, it can still attempt a parse based on underlying Markovian probabilities.

Training and Inference

To handle unknown word-to-meaning alignments, the authors use an Expectation-Maximization (EM) approach via the Inside-Outside algorithm. They developed a dynamic programming algorithm that reduces the complexity of this inference to $O(n^3m)$, where $n$ is sentence length and $m$ is the size of the meaning structure. Three model variations were tested: a Unigram model (Model I), a Bigram model (Model II), and an interpolated "Mixgram" model (Model III) to balance precision and recall.

Discriminative Reranking

Because the generative model makes strong independence assumptions, a post-processing step is introduced. An Averaged Perceptron is used to rerank the top-k candidates. This reranker specifically optimizes for F-measure by using a "separating plane" to reject low-confidence predictions.

Feature types used in the discriminative reranking step to improve parse selection.

Evaluation

The model was evaluated on two classic semantic parsing corpora: GEOQUERY (880 U.S. geography questions) and ROBOCUP (300 robot soccer coaching instructions).

The hybrid tree model, combined with reranking (Model III+R), outperformed previous state-of-the-art systems like WASP and KRISP. On GEOQUERY, it achieved an F-score of 85.2 (compared to KRISP's 81.1), with recall jumping to 81.5%, a significant improvement over previous benchmarks. On ROBOCUP, it achieved an F-score of 74.4. Additionally, the model proved language-independent, performing competitively on GEOQUERY subsets in Spanish, Japanese, and Turkish without language-specific tuning.

Conclusion

By moving away from rigid grammars toward a recursive generative process on hybrid trees, this approach achieves significant boosts in recall and robustness. The model's ability to degrade gracefully when encountering unseen structures makes it a powerful tool for real-world semantic parsing. Future work includes extending the model to support more complex representations like lambda-calculus and exploring the inverse task of natural language generation.

Summary updated

Abstract

In this paper, we present an algorithm for learning a generative model of natural language sentences together with their formal meaning representations with hierarchical structures. The model is applied to the task of mapping sentences to hierarchical representations of their underlying meaning. We introduce dynamic programming techniques for efficient training and decoding. In experiments, we demonstrate that the model, when coupled with a discriminative reranking technique, achieves state-of-the-art performance when tested on two publicly available corpora. The generative model degrades robustly when presented with instances that are different from those seen in training. This allows a notable improvement in recall compared to previous models.
BibTeX
@inproceedings{lu2008generative,
  author = {Wei Lu and Hwee Tou Ng and Wee Sun Lee and Luke S. Zettlemoyer},
  title = {{A Generative Model for Parsing Natural Language to Meaning Representations}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://openreview.net/forum?id=HJV9GMf_ZH},
}
Figure