A Generative Model for Parsing Natural Language to Meaning Representations

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 783–792, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics A Generative Model for Parsing Natural Language to Meaning Representations Wei Lu1, Hwee Tou Ng1,2, Wee Sun Lee1,2 1Singapore-MIT Alliance 2Department of Computer Science National University of Singapore luwei@nus.edu.sg {nght,leews}@comp.nus.edu.sg Luke S. Zettlemoyer CSAIL Massachusetts Institute of Technology lsz@csail.mit.edu Abstract In this paper, we present an algorithm for learning a generative model of natural lan- guage sentences together with their for- mal meaning representations with hierarchi- cal structures. The model is applied to the task of mapping sentences to hierarchical rep- resentations of their underlying meaning. We introduce dynamic programming techniques for efficient training and decoding. In exper- iments, we demonstrate that the model, when coupled with a discriminative reranking tech- nique, achieves state-of-the-art performance when tested on two publicly available cor- pora. The generative model degrades robustly when presented with instances that are differ- ent from those seen in training. This allows a notable improvement in recall compared to previous models. 1 Introduction To enable computers to understand natural human language is one of the classic goals of research in natural language processing. Recently, researchers have developed techniques for learning to map sen- tences to hierarchical representations of their under- lying meaning (Wong and Mooney, 2006; Kate and Mooney, 2006). One common approach is to learn some form of probabilistic grammar which includes a list of lexi- cal items that models the meanings of input words and also includes rules for combining lexical mean- ings to analyze complete sentences. This approach performs well but is constrained by the use of a sin- gle, learned grammar that contains a fixed set of lexical entries and productions. In practice, such a grammar may lack the rules required to correctly parse some of the new test examples. In this paper, we develop an alternative approach that learns a model which does not make use of an explicit grammar but, instead, models the cor- respondence between sentences and their meanings with a generative process. This model is defined over hybrid trees whose nodes include both natu- ral language words and meaning representation to- kens. Inspired by the work of Collins (2003), the generative model builds trees by recursively creating nodes at each level according to a Markov process. This implicit grammar representation leads to flexi- ble learned models that generalize well. In practice, we observe that it can correctly parse a wider range of test examples than previous approaches. The generative model is learned from data that consists of sentences paired with their meaning rep- resentations. However, there is no explicit labeling of the correspondence between words and meaning tokens that is necessary for building the hybrid trees. This creates a challenging, hidden-variable learning problem that we address with the use of an inside- outside algorithm. Specifically, we develop a dy- namic programming parsing algorithm that leads to O(n3m) time complexity for inference, where n is the sentence length and m …

Content truncated to 500 words