Similar to journal version.

Current approaches to semantic parsing, the task of converting text to a formal meaning representation, rely on annotated training data mapping sentences to logi- cal forms. Providing this supervision is a major bottleneck in scaling semantic parsers. This paper presents a new learn- ing paradigm aimed at alleviating the su- pervision burden. We develop two novel learning algorithms capable of predicting complex structures which only rely on a binary feedback signal based on the con- text of an external world. In addition we reformulate the semantic parsing problem to reduce the dependency of the model on syntactic patterns, thus allowing our parser to scale better using less supervision. Our results surprisingly show that without us- ing any annotated meaning representations learning with a weak feedback signal is ca- pable of producing a parser that is compet- itive with fully supervised parsers.

We consider the problem of learning to parse sentences to lambda-calculus representations of their underlying semantics and present an algorithm that learns a weighted combinatory categorial grammar (CCG). A key idea is to introduce non-standard CCG combinators that relax certain parts of the grammar—for example allowing flexible word order, or insertion of lexical items— with learned costs. We also present a new, online algorithm for inducing a weighted CCG. Results for the approach on ATIS data show 86 % F-measure in recovering fully correct semantic analyses and 95.9% F-measure by a partial-match criterion, a more than 5 % improvement over the 90.3% partial-match figure reported by He and Young (2006).

(*) Solving the same problem as ZC05 paper on atis and geo. Geo, jobs, restaurant are artificially generated, atis is natural! New CCG combinators and new online algorithm more flexible with realistic language. atis exact 1-pass p=.9061 r=.8192 f=.8605 atis exact 2-pass p=.8575 r=.8460 f=.8516 atis partial 1-pass p=.9676 r=.8689 f=.9156 atis partial 2-pass p=.9511 r=.9671 f=.9590 (He and Young 2006 atis partial f=90.3%) geo880 1-pass p=.9549 r=.8320 f=.8893 geo880 2-pass p=.9163 r=.8607 f=.8876 (ZC05 p=.9625 r=.7929 f=.8695) Still uses GENLEX with two additional rules. Still uses initial lexicon with nouns and wh-words! CCG additions include: 1. function application with reverse word order. 2. function composition with reverse word order. (do we even need the syntactic cats with slashes?) 3. additional type raising and crossed-comp rules that need more careful reading. Two important differences from learning algorithm of ZC05: 1. online updates instead of batch. 2. perceptron updates instead of SGD on NLL. Learning algorithm: 1. skip example if parsed correctly with current lex. 2. introduce all genlex and find maxscore parse with correct semantics. 3. add the new entries in maxparse to lex and try parsing again. 4. do a perceptron update.

(***) Zettlemoyer and Collins 2005: map sentences to typed lambda expressions: which rivers run through states that border the state with the capital austin (lambda $0:e (and:<t*,t> (river:<r,t> $0) (exists:<<e,t>,t> (lambda $1:e (and:<t*,t> (state:<s,t> $1) (next_to:<lo,<lo,t>> $1 (the:<<e,t>,e> (lambda $2:e (and:<t*,t> (state:<s,t> $2) (capital2:<s,<c,t>> $2 austin_tx:c))))) (loc:<lo,<lo,t>> $0 $1)))))) In addition to the training set of pairs like above they have two additional sources of information given by hand: a. GENLEX rules: to generate candidates for the lexicon, they produce a cross product of (all substrings of the sentence) x (all categories that can be produced from the lambda expression). The second part is done using 10 heuristic rules that convert parts of the lambda expression to possible categories e.g. N:(lambda (x) (major x)). b. Initial lexicon: this includes two types of manually added entries: domain specific, database derived entities such as (Utah => NP:utah) and domain independent entries such as “what” => (S/(S\NP))/N:(lambda f (lambda g (lamba x (and (f x) (g x)))). Both these look like cheating. How sensitive are the results to these manual inputs? What kinds of words are actually learnt at the end? Is it possible to learn entries like “what” at all? Why do we need syntactic categories, can’t we just have lambda expressions? Should look at how future work handled these. Geo880 p=.9625 r=.7929 f=.8695 (TM01 p=.8992 r=.7940) Jobs640 p=.9736 r=.7929 f=.8740 (TM01 p=.9325 r=.7984)