Grammar Approximation by Representative Sublanguage: A New Model for Language Learning

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 832–839, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Grammar Approximation by Representative Sublanguage: A New Model for Language Learning Smaranda Muresan Institute for Advanced Computer Studies University of Maryland College Park, MD 20742, USA smara@umiacs.umd.edu Owen Rambow Center for Computational Learning Systems Columbia University New York, NY 10027, USA rambow@cs.columbia.edu Abstract We propose a new language learning model that learns a syntactic-semantic grammar from a small number of natural language strings annotated with their semantics, along with basic assumptions about natural lan- guage syntax. We show that the search space for grammar induction is a complete gram- mar lattice, which guarantees the uniqueness of the learned grammar. 1 Introduction There is considerable interest in learning computa- tional grammars.1 While much attention has focused on learning syntactic grammars either in a super- vised or unsupervised manner, recently there is a growing interest toward learning grammars/parsers that capture semantics as well (Bos et al., 2004; Zettlemoyer and Collins, 2005; Ge and Mooney, 2005). Learning both syntax and semantics is arguably more difficult than learning syntax alone. In for- mal grammar learning theory it has been shown that learning from “good examples,” or representative examples, is more powerful than learning from all the examples (Freivalds et al., 1993). Haghighi and Klein (2006) show that using a handful of “proto- 1This research was supported by the National Science Foun- dation under Digital Library Initiative Phase II Grant Number IIS-98-17434 (Judith Klavans and Kathleen McKeown, PIs). We would like to thank Judith Klavans for her contributions over the course of this research, Kathy McKeown for her in- put, and several anonymous reviewers for very useful feedback on earlier drafts of this paper. types” significantly improves over a fully unsuper- vised PCFG induction model (their prototypes were formed by sequences of POS tags; for example, pro- totypical NPs were DT NN, JJ NN). In this paper, we present a new grammar formal- ism and a new learning method which together ad- dress the problem of learning a syntactic-semantic grammar in the presence of a representative sample of strings annotated with their semantics, along with minimal assumptions about syntax (such as syntac- tic categories). The semantic representation is an ontology-based semantic representation. The anno- tation of the representative examples does not in- clude the entire derivation, unlike most of the ex- isting syntactic treebanks. The aim of the paper is to present the formal aspects of our grammar induction model. In Section 2, we present a new grammar formal- ism, called Lexicalized Well-Founded Grammars, a type of constraint-based grammars that combine syntax and semantics. We then turn to the two main results of this paper. In Section 3 we show that our grammars can always be learned from a set of positive representative examples (with no negative examples), and the search space for grammar in- duction is a complete grammar lattice, which guar- antees the uniqueness of the learned grammar. In …

Content truncated to 500 words