Formalizing Semantic Parsing with Tree Transducers

Formalizing Semantic Parsing with Tree Transducers Bevan Keeley Jones & Mark Johnson Department of Computing Macquarie University Sydney, NSW 2109, Australia Bevan.Jones@students.mq.edu.au Mark.Johnson@mq.edu.au Sharon Goldwater School of Informatics University of Edinburgh Edinburgh, EH8 9AB, UK sgwater@inf.ed.ac.uk Abstract This paper introduces tree transducers as a unifying theory for semantic parsing models based on tree transformations. Many exist- ing models use tree transformations, but im- plement specialized training and smoothing methods, which makes it difficult to mod- ify or extend the models. By connecting to the rich literature on tree automata, we show how semantic parsing models can be de- veloped using completely general estimation methods. We demonstrate the approach by reframing and extending one state-of-the-art model as a tree automaton. Using a variant of the inside-outside algorithm with variational Bayesian estimation, our generative model achieves higher raw accuracy than existing generative and discriminative approaches on a standard data set. 1 Introduction Automatically interpreting language is an important challenge for computational linguistics. Semantic parsing addresses the specific task of learning to map natural language sentences to formal represen- tations of their meaning, a problem that arises in de- veloping natural language interfaces, for example. Given a set of (sentence, meaning representation) pairs like the example below, we want to to learn a map that generalizes to previously unseen sentences. 1. Sentence: what is the capital of texas ? Meaning: answer(capital 1(stateid(texas))) Researchers have formalized the learning prob- lem in various ways, with approaches including string classifiers (Kate and Mooney, 2006), syn- chronous grammar (Wong and Mooney, 2006), combinatory categorial grammar (Zettlemoyer and Collins, 2005; Kwiatkowski et al., 2010), and PCFG-based approaches (Lu et al., 2008; Borschinger et al., 2011). Each approach has re- quired its own custom algorithms, which has made model development and innovation slow. Never- theless, there are many similarities between the approaches, which all exploit parallels between the structure of the meaning representation and that of the natural language. The meaning representation, as a context-free formal language, has an obvious tree structure. Trees are also widely used to describe natural language structure. Consequently, the semantic parsing problem can be generally defined as learning a mapping between trees, one of which may be latent. This mapping can be expressed as a tree transducer, a formalism from automata theory that maps input trees to output trees or strings. Tree transducers have well understood properties and algorithms, and a rich literature, making them a particularly appealing model class. Although some previous approaches strongly re- semble tree transducers, to our knowledge, we are the first to explicitly formulate the problem in this way. We argue that connecting semantic parsing to the tree automata literature will free researchers from devising custom solutions and allow them to focus on studying and improving their models and developing more general learning algorithms. To demonstrate the effectiveness of the approach, we choose one state-of-the-art model, the hybrid tree (Lu et al., 2008), translate it into the tree transducer Bevan Jones, Mark Johnson and Sharon Goldwater. 2011. Formalizing Semantic …

Content truncated to 500 words