Weakly Supervised Semantic Parsing with Execution-based Spurious Program Filtering (2023)

Abstract: The problem of spurious programs is a longstanding challenge when training a semantic parser from weak supervision. To eliminate such programs that have wrong semantics but correct denotation, existing methods focus on exploiting similarities between examples based on domain-specific knowledge. In this paper, we propose a domain-agnostic filtering mechanism based on program execution results. Specifically, for each program obtained through the search process, we first construct a representation that captures the program’s semantics as execution results under various inputs. Then, we run a majority vote on these representations to identify and filter out programs with significantly different semantics from the other programs. In particular, our method is orthogonal to the program search process so that it can easily augment any of the existing weakly supervised semantic parsing frameworks. Empirical evaluations on the Natural Language Visual Reasoning and WikiTableQuestions demonstrate that applying our method to the existing semantic parsers induces significantly improved performances.

## introduction semantic parsing is the task of mapping natural language utterances into machine-executable meaning representations, often referred to as programs. most deep learning-based semantic parsing studies take the supervised learning approach requiring utterance-program paired dataset. however, annotating such pairs demands expensive expert annotations. instead, weakly-supervised semantic parsing, i.e. learning from denotation, has drawn much attention @xcite @xcite . in this setup, a semantic parser is trained with cheaper denotation (execu-tion result of the program) rather than the program itself. prior works on weakly supervised semantic parsing attack the spuriousness problem by introducing some domain-specific knowledge, such as abstracted utterance-program pairs @xcite or utterance groups @xcite . unlike these works, we propose a domain-agnostic filtering mechanism based on a majority vote over program execution results to alleviate the spuriousness issue. our intuition is that programs whose execution results largely deviate from those of other programs in the pool are likely to be spurious, thus filtering them out would improve the training of weakly supervised semantic parsers. to effectively quantify the degree of deviation, we propose a novel representation scheme of programs based on the execution results. here, the entries of a representation vector are the program's execution results on worlds retrieved from other training examples. to exclude spurious programs, we run a majority vote on these representations to construct a "centroid representation" and filter out the programs whose representation is dissimilar to it. our method can be applied to any weakly supervised semantic parser with minimal modification, as long as it involves a program search step in the training process. we evaluate our filtering mechanism on two challenging datasets with distinct characteristics: natural language visual reasoning (nlvr) @xcite and wikitablequestions (wtq) @xcite . when added on the base models @xcite , our filtering mechanism shows significant improvement over the baselines without using additional domain-specific knowledge. finally, we quantitatively analyze the effectiveness of our approach in detecting spurious programs and conduct an error analysis on a failure case. ## background in this section, we formalize weakly supervised semantic parsing problems and introduce two datasets: nlvr and wtq. ## execution-based filtering to eliminate spurious programs, we devise a novel execution-based filtering mechanism. intuitively, among consistent programs, the spurious ones are likely to semantically deviate. however, measuring or defining semantic distance is challenging. thus, we instead loosely capture the semantics of programs by executing them against reasonably selected worlds. then, we filter out the programs whose execution results deviate most from others by performing a majority vote. formal setups consider an example with utterance x, world w, and denotation y. 2 the programs figure 2 : illustration of our program representation scheme and filtering based on majority vote. retrieved worlds (w j 's) partition the programs into several groups by their execution results and are represented as lines in the figure. 4 by running majority vote based on the execution results, programs in the gray regions may be filtered. ## collecting execution results in the previous section, the program representation is defined by the program's execution results on multiple worlds. now we describe methods to select the worlds and obtain programs' execution results on those worlds. we discuss two separate approaches for nlvr and wtq, considering their vastly different world configurations. ## experiments to validate the efficacy of our filtering method, we conduct experiments on nlvr and wtq datasets. first, for each dataset, we characterize existing parsers we use and explain where our method is applied. after explaining our filtering implementation on each of these datasets, we present our experimental results and ablation studies. ## analysis setup in this section, we quantitatively analyze the effectiveness of our approach in filtering out spurious programs. to assess its effectiveness in distinguishing between spurious and correct programs, we randomly select 30 examples from the nlvr training set and manually label the programs obtained through the last program search step. next, we evaluate the performance of spurious program detection, by classifying all programs with scores lower than the threshold τ as spurious. ## conclusion we proposed a domain-agnostic approach to filter out spurious programs in weakly supervised semantic parsing based on execution results and majority vote. our assumption was spurious programs are outliers in terms of meaning; thus, we introduced a representation scheme that captures the semantics of programs. based on these representations, we ran the majority vote to identify and exclude spurious programs from the pool. our approach showed significant improvements over base models on nlvr and wtq test set performance, also reporting a new state-of-the-art on nlvr with less domain-specific knowledge than the previous best model.