A Probabilistic Forest-to-String Model for Language Generation from Typed Lambda Calculus Expressions

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1611–1622, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics A Probabilistic Forest-to-String Model for Language Generation from Typed Lambda Calculus Expressions Wei Lu and Hwee Tou Ng Department of Computer Science School of Computing National University of Singapore {luwei,nght}@comp.nus.edu.sg Abstract This paper describes a novel probabilistic ap- proach for generating natural language sen- tences from their underlying semantics in the form of typed lambda calculus. The approach is built on top of a novel reduction-based weighted synchronous context free grammar formalism, which facilitates the transforma- tion process from typed lambda calculus into natural language sentences. Sentences can then be generated based on such grammar rules with a log-linear model. To acquire such grammar rules automatically in an unsuper- vised manner, we also propose a novel ap- proach with a generative model, which maps from sub-expressions of logical forms to word sequences in natural language sentences. Ex- periments on benchmark datasets for both En- glish and Chinese generation tasks yield sig- nificant improvements over results obtained by two state-of-the-art machine translation models, in terms of both automatic metrics and human evaluation. 1 Introduction This work focuses on the task of generating natu- ral language sentences from their underlying mean- ing representations in the form of formal logical ex- pressions (typed lambda calculus). Many early ap- proaches to generation from logical forms make use of rule-based methods (Wang, 1980; Shieber et al., 1990), which concern surface realization (ordering and inflecting of words) but largely ignore lexical ac- quisition. Recent approaches start to employ corpus- based probabilistic methods, but many of them as- sume the underlying meaning representations are of specific forms such as variable-free tree-structured representations (Wong and Mooney, 2007a; Lu et al., 2009) or database entries (Angeli et al., 2010). While these algorithms usually work well on spe- cific semantic formalisms, it is unclear how well they could be applied to a different semantic formal- ism. In this work, we propose a general probabilis- tic model that performs generation from underlying formal semantics in the form of typed lambda calcu- lus expressions (we refer to them as λ-expressions throughout this paper), where both lexical acquisi- tion and surface realization are integrated in a single framework. One natural proposal is to adopt a state-of-the-art statistical machine translation approach. However, unlike text to text translation, which has been ex- tensively studied in the machine translation commu- nity, translating from logical forms into text presents additional challenges. Specifically, logical forms such as λ-expressions may have complex internal structures and variable dependencies across sub- expressions. Problems arise when performing auto- matic acquisition of a translation lexicon, as well as performing lexical selection and surface realization during generation. In this work, we tackle these challenges by mak- ing the following contributions: • A novel forest-to-string generation algorithm: Inspired by the work of Chiang (2007), we in- troduce a novel reduction-based weighted bi- nary synchronous context-free grammar for- malism for generation …

Content truncated to 500 words