Unanimous Prediction for 100% Precision with Application to Learning Semantic Mappings

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 952–962, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Unanimous Prediction for 100% Precision with Application to Learning Semantic Mappings Fereshte Khani Stanford University fereshte@cs.stanford.edu Martin Rinard MIT rinard@lcs.mit.edu Percy Liang Stanford University pliang@cs.stanford.edu Abstract Can we train a system that, on any new input, either says “don’t know” or makes a prediction that is guaranteed to be cor- rect? We answer the question in the affir- mative provided our model family is well- specified. Specifically, we introduce the unanimity principle: only predict when all models consistent with the training data predict the same output. We operational- ize this principle for semantic parsing, the task of mapping utterances to logi- cal forms. We develop a simple, efficient method that reasons over the infinite set of all consistent models by only check- ing two of the models. We prove that our method obtains 100% precision even with a modest amount of training data from a possibly adversarial distribution. Empiri- cally, we demonstrate the effectiveness of our approach on the standard GeoQuery dataset. 1 Introduction If a user asks a system “How many painkillers should I take?”, it is better for the system to say “don’t know” rather than making a costly incor- rect prediction. When the system is learned from data, uncertainty pervades, and we must manage this uncertainty properly to achieve our precision requirement. It is particularly challenging since training inputs might not be representative of test inputs due to limited data, covariate shift (Shi- modaira, 2000), or adversarial filtering (Nelson et al., 2009; Mei and Zhu, 2015). In this unforgiving setting, can we still train a system that is guaran- teed to either abstain or to make the correct pre- diction? Our present work is motivated by the goal of input output area of Iowa area(IA) cities in Ohio city(OH) cities in Iowa city(IA) mapping 1 mapping 2 mapping k output 1 area(OH) area(OH) output 2 area(OH) area(OH) output k area(OH) OH training examples input area of Ohio Ohio area output area(Ohio) don’t know testing examples unanimity ... ... Figure 1: Given a set of training examples, we compute C, the set of all mappings consistent with the training examples. On an input x, if all map- pings in C unanimously predict the same output, we return that output; else we return “don’t know”. building reliable question answering systems and natural language interfaces. Our goal is to learn a semantic mapping from examples of utterance- logical form pairs (Figure 1). More generally, we assume the input x is a bag (multiset) of source atoms (e.g., words {area, of, Ohio}), and the out- put y is a bag of target atoms (e.g., predicates {area, OH}). We consider learning mappings M that decompose according to the multiset sum: M(x) = ⊎s∈xM(s) (e.g., M({Ohio}) = {OH}, M({area,of,Ohio}) = {area,OH}). The main challenge is that an individual training example (x, y) does not tell us which source atoms …

Content truncated to 500 words