Non-Programmers Can Label Programs Indirectly via Active Examples: A Case Study with Text-to- SQL (2023)

Abstract: Can non-programmers annotate natural language utterances with complex programs that represent their meaning? We introduce APEL, a framework in which non-programmers select among candidate programs generated by a seed semantic parser (e.g., Codex). Since they cannot understand the candidate programs, we ask them to select indirectly by examining the programs’ input-ouput examples. For each utterance, APEL actively searches for a simple input on which the candidate programs tend to produce different outputs. It then asks the non-programmers only to choose the appropriate output, thus allowing us to infer which program is correct and could be used to fine-tune the parser. As a first case study, we recruited human non-programmers to use APEL to re-annotate SPIDER, a text-to-SQL dataset. Our approach achieved the same annotation accuracy as the original expert annotators (75%) and exposed many subtle errors in the original annotations.

## introduction semantic parsing often aims to map a natural language utterance to a program, which can be executed on an input @xcite . for example, for the utterance "how old is the youngest person," we can map to the sql program select min(age) from people, execute it on an input database, and return the output answer. language models like codex often achieve substantial few-shot performance @xcite . however, user-facing applications often involve novel phrases or domain-specific values unseen during pre-training or generic instruction-tuning, so the model still needs more labels for training. since hiring programming experts to label training data is costly, can we ask non-programmers to label them? we introduce apel, a framework that indirectly labels programs with non-programmer responses on carefully constructed input-output examples. apel must be seeded with a moderately good semantic parser: we use codex for this in our experiments, prompting it with a few demonstrations that we solicited from expert programmers. we now want to label additional training data. to construct the correct program for a new utterance, apel uses the seed parser to generate a list of candidate programs with prior probabilities (figure 1 top), and then asks non-programmer annotators to indicate which candidate is correct. however, we cannot ask the annotators to select the correct program directly, since even expert programmers might find this challenging (figure 2 ). instead, apel obtains information indirectly by asking questions about how the program should be-@xmath0 figure 2 : apel needs to obtain information about whether s 1 or s 2 is correct; it is hard even for experts to directly select the correct one by eyeballing. the error of s 1 is subtle: it finds the first names of the students who have dogs and the first names of the students who have cats, and intersects these two sets of first names. apel can reveal this error by asking about a tiny student database i in which alice jones owns a dog while alice smith owns a cat. as no student named alice owns both, the annotator will select an output o that does not include alice, implying that s 1 is incorrect. to reduce annotators' workload, we propose an algorithm to search for a program input that maximizes the expected information gain of the annotator's answer ( §3), subject to the constraint that the input is simple enough for the annotator to reason about the correct output easily (figure 3 ). since our method resembles the programming by example (pbe) framework @xcite and learns an underlying program by actively choosing which examples should be labeled, we call our framework apel-active programming by examples using a prior derived from a natural language utterance. ## optimizing the input database we attempt to maximize the expected information gain ig over all databases that conform to the given schema c and have at most r total records, where @xmath1. formally, we search for when multiple databases have the same ig, we break ties by favoring the smallest database. since t and p are fixed during the optimization process, we will write ig(i) instead of ig p t-1 (i t ) for short. our method can be summarized as "fuzz-thendrop." fuzzing @xcite ) is an established practice in software testing, where an algorithm generates a large number of random program inputs to search for an input that satisfies a property or reveals a bug. in our case, we want to search for an input database that maximizes the information gain. therefore, we first perform fuzzing by randomly generating a large number of large databases as in zhong et al. (2020)-see appendix c for further details-and keep the database i 0 that maximizes the expected information gain ig(i 0 ). we then drop records from i 0 to satisfy the simplicity criterion for l iterations. for each iteration ℓ of dropping records, we randomly drop 5% of the records from i ℓ to obtain i ℓ+1 . if this results in a less informative database, i.e., ig(i ℓ+1 ) < ig(i ℓ ), we are willing to retry up to 20 times in hopes of randomly finding an i ℓ+1 that is at least as informative as i ℓ ; if we fail in all 20 tries, we keep the best of the 20 despite the decrease in ig. of the databases smaller than r that we encountered during the l iterations, let î be the one with the highest ig: since our procedure is randomized, we repeat it 3 times, and let i * be the î with the largest ig( î), breaking ties as before in favor of smaller î. finally, we simplify i * by dropping tables and columns that were not mentioned by any sql candidates in p. our procedure of dropping records from a large informative database is heavily inspired by @xcite , which, given a database i such that s 1 (i) ̸ = s 2 (i), provably finds the smallest subset of records in i such that programs s 1 and s 2 return different outputs. however, their algorithm works only for a restricted family of sql programs and cannot be adapted to optimize information gain. our procedure does not provide any provable optimality guarantee, but is more flexible and practical. in practice, simply applying the above procedure can generate unnatural databases and lead to vacuous sql execution, confusing the annotators. in appendix c, we illustrate several typical confusions (figure 6 ) and explain how we fix them. ## experimental setup we describe the dataset used to benchmark apel ( §4.1), how we obtained the prior over sql candidates ( §4.2), and our evaluation metrics ( §4.4). ## automated simulation evaluation with 3 rounds of interactions, apel accuracy (91%) substantially improves on the codex accuracy (72%), validating the effectiveness of our framework; we achieved this by interacting with our oracle annotator for 1.8 rounds on average. compared to origdb (86%), which uses the sample databases from the original spider dataset to interact for 1 round, apel's database generation method leads to higher accuracy since it allows multiple rounds and optimizes for information gain. furthermore, averaged across all utterances, the databases generated by apel contained altogether 10 records across all rounds-whereas the origdb databases contained on average 33,295 records and would be impractical to present to human annotators. these results highlight the need for the databases to be both simple and informative. 2 appendix h provides further information on the database sizes, the number of interaction rounds, and the robustness of our database generation method under different hyper-parameter choices. ## human evaluation we evaluate the effectiveness of apel with real human annotators. we built an interface designed to be user-friendly ( §6.1) and used it ourselves to establish gold annotations for 240 utterances ( §6.2). we then recruited 11 non-programmer subjects to annotate the same utterances ( §6.3), aggregated their responses by learning a model of annotator behavior ( §6.4), and benchmarked their performance with the newly established gold standard ( §6.5). we analyze errors by spider expert annotators in §6.6, qualitative feedback from our subjects in §6.7, and errors made by our subjects in appendix f. ## conclusion we proposed apel, enabling non-programmers to indirectly label sql programs via input-output examples. with advances in semantic parsing and pbe, future work could potentially extend apel to other applications. we hope non-programmers can label more complex programs in the future, hence decreasing the costs of supervising increasingly capable ai systems that can take complicated actions by generating and executing code.