An Imitation Game for Learning Semantic Parsers from User Interaction (2020)

Abstract: Despite the widely successful applications, bootstrapping and fine-tuning semantic parsers are still a tedious process with challenges such as costly data annotation and privacy risks. In this paper, we suggest an alternative, human-in-the-loop methodology for learning semantic parsers directly from users. A semantic parser should be introspective of its uncertainties and prompt for user demonstrations when uncertain. In doing so it also gets to imitate the user behavior and continue improving itself autonomously with the hope that eventually it may become as good as the user in interpreting their questions. To combat the sparsity of demonstrations, we propose a novel annotation-efficient imitation learning algorithm, which iteratively collects new datasets by mixing demonstrated states and confident predictions and retrains the semantic parser in a Dataset Aggregation fashion (Ross et al., 2011). We provide a theoretical analysis of its cost bound and also empirically demonstrate its promising performance on the text-to-SQL problem. Code will be available at https://github.com/sunlab-osu/MISP .

## introduction semantic parsing has found tremendous applications in building natural language interfaces that allow users to query data and invoke services without programming @xcite @xcite @xcite . the life cycle of a semantic parser typically consists of two stages: (1) bootstrapping, where we keep collecting labeled data via trained annotators and/or crowdsourcing for model training until it reaches commercialgrade performance (e.g., 95% accuracy on a surrogate test set), and (2) fine-tuning, where we deploy the system, analyze the usage, and collect and 1 code will be available at https://github.com/ sunlab-osu/misp . does the system need to consider any conditions about the table attribute "school/club team"? what condition does "jalen rose" imply? thank you! query result: 1. executed sql query: 25 aleksandar radojević serbia barton cc (ks) center 5 jalen rose united states michigan guard-forward ... ... ... ... ... how many schools or teams had jalen rose? user interaction feedback collection no. player nationality school/club team position select count(school/club team) where school/club team ... @xmath0 select count(school/club team) where player ... ## related work interactive semantic parsing. our work extends the recent idea of leveraging system-user interaction to improve semantic parsing on the fly @xcite @xcite @xcite @xcite @xcite . @xcite built a neural model to identify and correct error spans in generated queries via dialogues. @xcite formalized a model-based intelligent agent misp, which enables user interaction via a policy probability-based uncertainty estimator, a grammar-based natural language generator, and a multi-choice question-answer interaction design. more recently, @xcite crowdsourced a dataset for fixing incorrect sql queries using free-form natural language feedback. semantic @xcite constructed a contextual semantic parsing dataset where agents could trigger conversations to handle exceptions such as ambigu-ous or incomplete user commands. in this work, we seek to continually improve semantic parsers from such user interaction, a topic that is not carefully studied by the aforementioned work. interactive learning from feedback. learning interactively from user feedback has been studied in many nlp tasks @xcite @xcite @xcite @xcite . most relevant to us, @xcite constructed a self-feeding chatbot that improves itself from user satisfied responses and their feedback on unsatisfied ones. in the field of semantic parsing, clarke et al. (2010); artzi and zettlemoyer (2013); iyer et al. (2017 ) learned semantic parsers from binary user feedback on whether executing the generated query yields correct results. however, often times (especially in information-seeking scenarios) it may not be very practical to expect end users able to validate the denotation correctness (e.g., consider validating an execution result "103" for the question "how many students have a gpa higher than 3.5" from a massive table). active learning is also leveraged to save human annotations @xcite . our work is complementary to this line of research as we focus on learning interactively from end users (not "teachers"). ## preliminaries formally, we assume the semantic parsing model generates a semantic parse by executing a sequence of actions a t (parsing decisions) at each time step t. in practice, the definition of an action depends on the specific semantic parsing model, as we will illustrate shortly. a state s t is then defined as a tuple of (q, a 1:t-1 ), where q is the initial natural language question and a 1:t-1 = (a 1 , ..., a t-1 ) is the current partial parse. in particular, the initial state s 1 = (q, φ) contains only the question. denote a semantic parser as π, which is a policy function (sutton and barto, 2018) that takes a state s t as input and outputs a probability distribution over the action space. the semantic parsing process can be formulated as sampling a trajectory τ by alternately observing a state and sampling an action from the policy, i.e., τ = (s 1 , a 1 ∼ π(s 1 ), ..., s t , a t ∼ π(s t )), assuming a trajectory length t . the probability of the generated semantic parse becomes: p π(a 1:t |s 1 ) = t @xmath1. an interactive semantic parser typically follows the aforementioned definition and requests the user's validation of a specific action a t . based on the feedback, a correct action a * t can be inferred to replace the original a t . the parsing process continues with a * t afterwards. in this work, we adopt misp @xcite as the back-end interactive semantic parsing framework, given that it is a principled framework for this purpose and can generalize to various kinds of semantic parsers and logical forms. however, we note that our proposed algorithm is not limited to misp; it instead depicts a general algorithm for learning semantic parsers from user interaction. we illustrate the application of misp to a sketch-based parser, sqlova @xcite , as follows. more details and another example of how it applies to a non-sketch-based parser editsql @xcite can be found in appendix b.1. example. consider the sqlova parser, which generates a query by filling "slots" in a predefined sql sketch "select agg scol where wcol op val". to complete the sql query in figure 1 , it first takes three steps: @xmath2, @xmath3. misp detects that a 3 is uncertain because its probability is lower than a pre-specified threshold. it validates a 3 with the user and corrects it with @xmath4 ## learning semantic parsers from user interaction in this section, we present neil, an annotation-efficient imitation learning algorithm that trains a parser from user interaction, without requiring a large amount of user feedback (or "annotations"). this property is particularly important for end userfacing systems in practical use. note that while we apply neil to semantic parsing in this work, in principle it can also be applied to other structured prediction tasks (e.g., machine translation). ## theoretical analysis while neil enjoys the benefit of learning from a small amount of user feedback, one crucial question is whether it can still achieve the same level of performance as the traditional supervised approach (which trains a policy on full expert annotations, if one could afford that and manage the privacy risk). in this section, we prove that the performance gap between the two approaches is mainly determined by the learning policy's probability of trusting a confident action that turns out to be wrong, which can be controlled in practice. our analysis follows prior work @xcite to assume a unified trajectory length t and an infinite number of training samples in each iteration (i.e., @xmath5, such that the state space can be full explored by the learning policy. an analysis under the "finite sample" case can be found in appendix a.5. ## experiments in this section, we conduct experiments to demonstrate the annotation efficiency of our neil algo-rithm and that it can train semantic parsers for high performance when the parsers are reasonably initialized, which verifies our theoretical analysis. ## conclusion and future work our work shows the possibility of continually learning semantic parsers from fine-grained end user interaction. as a pilot study, we experiment systems with simulated user interaction. one important future work is thus to conduct large-scale user studies and train parsers from real user interaction. this is not trivial and has to account for uncertainties such as noisy user feedback. we also plan to derive a more realistic formulation of user/expert annotation costs by analyzing real user statistics (e.g., average time spent on each question). in experiments, we observe that neural semantic parsers tend to be overconfident and training them with more data does not mitigate this issue. in the future, we will look into more accurate confidence measure via neural network calibration @xcite or using machine learning components (e.g., answer triggering @xcite or a reinforced active selector @xcite ). finally, we believe our algorithm can be applied to save annotation effort for other nlp tasks, especially the low-resource ones @xcite .