Few-Shot Novel Concept Learning for Semantic Parsing (2021)

Abstract: Humans are capable of learning novel concepts from very few examples; in contrast, state-of-the-art machine learning algorithms typically need thousands of examples to do so. In this paper, we propose an algorithm for learning novel concepts by representing them as programs over existing concepts. This way the concept learning problem is naturally a program synthesis problem and our algorithm learns from a few examples to synthesize a program representing the novel concept. In addition, we perform a theoretical analysis of our approach for the case where the program defining the novel concept over existing ones is context-free. We show that given a learned grammar-based parser and a novel production rule, we can augment the parser with the production rule in a way that provably generalizes. We evaluate our approach by learning concepts in the semantic parsing domain extended to the few-shot novel concept learning setting, showing that our approach significantly outperforms end-to-end neural semantic parsers.

## introduction a key feature of human intelligence is few-shot learning-namely, their ability to learn novel concepts from as few as one or two examples. in contrast, current deep learning approaches face significant challenges with such tasks. this is a limitation of deep learning across many applications, since in many domains, there are a large number of concepts, and for many, there are only a few examples available for learning. there has been substantial recent interest in studying few-shot learning in the context of semantic parsing @xcite @xcite , which is the task of mapping natural language utterances to an executable meaning representation @xcite . this setting http://cogcomp.org/page/publication_view/952 provides a rich opportunity for concept learning since concepts can naturally be grounded in symbolic representations in the form of programs. as a consequence, there is an opportunity to learn novel, unseen concepts in a compositional way: the novel concept can be represented as a composition of existing concepts, and can then be composed with existing concepts to form more complex ones. while this compositional structure exists in many natural language tasks, it is explicit in semantic parsing. as a concrete example, consider the novel concept 4 times in the utterance run 4 times, where run is an existing concept. the program representing 4 times is the program λx . (repeat 4 x), which is composed with the program run representing run to form the program (repeat 4 run). in this paper, we propose a novel algorithm for learning novel concepts for semantic parsing. at a high level, leveraging the fact that concepts can be represented as programs, our algorithm is based on program synthesis (also known as program induction). in particular, given a set of input-output examples, synthesis algorithms search over the space of possible programs to identify one that is consistent with these examples; they can often find the correct program from very few examples. the key challenge in applying program synthesis to our setting is that the given training examples are for the whole semantic parsing task rather than for the specific sub-program corresponding to the novel concept. in more detail, we consider the problem of learning a semantic parser from denotations alone-i.e., each training example consists of an utterance (the user's input) labeled with the execution of the corresponding program (the user's desired output) rather than the program itself. we assume that the utterance contains a single new natural language concept (e.g., a word or phrase) that we are trying to learn (i.e., synthesize a program representing that word or phrase). to address this issue, our algorithm proceeds as follows: • sketch synthesis: since we already know the remaining concepts in the utterance, we want to avoid synthesizing them as well. to this end, our algorithm first synthesizes a sketch (solar-lezama, 2008), which is an incomplete program where one of its expressions has been left as a hole that remains to be filled in. this hole is supposed to be filled by the novel concept we are trying to synthesize. finally, whenever the novel concept is encountered in future examples, we can substitute it with the synthesized sub-program. next, we perform a theoretical analysis of our approach, which is designed to more generally elucidate why an approach such as ours can enable few-shot learning of novel concepts. in our analysis, we assume that a representation of the novel concept has already been synthesized; instead, our goal is to illustrate why augmenting the existing model with this new concept can generalize well. in particular, the main issue is that the novel concept can result in a shift in the distribution of decisions that must be learned by the model (e.g., application of parsing rules). we focus on the problem of parsing context-free grammars, which is simpler since it is a classification problem instead of a structured prediction problem. then, we show that assuming the learned model is grammar-based (i.e., learn which production rules are in the grammar), then augmenting it with the novel concept (i.e., a novel production rule) can generalize well. finally, we experimentally evaluate our approach on two semantic parsing benchmarks, scan @xcite and geoquery @xcite , extended to our problem of few-shot novel concept learning. we demonstrate that while end-to-end deep learning baselines fail to learn the novel concepts, our approach does so effectively. in summary, our key contributions are: example. consider fig. systematicity in deep learning. prior work has demonstrated that neural networks to not possess systematicity @xcite @xcite , a property where the capacity to learn certain concepts implies the capacity to learn novel, structurally-related concepts. lake and baroni (2018) empirically investigates novel concept learning on the scan dataset. they consider models that have not seen the concept jump during training, but only in isolation, where jump is represented by the program jump, whose denotation is also jump. at test time, the models have to correctly predict the output sequence for jump in various contexts, e.g., jump and look. models are expected to be able to do so since they have seen walk and look and run and look during training, and are expected to extrapolate these examples to jump. they find that several sequence-to-sequence models perform very poorly on this task. however, the kind of concepts they use to assess generalization are very limited. for instance, in scan, the jump primitive is an independent concept with no relation to the existing concepts such as walk, look, run, after, twice, around. in contrast, we consider a more general notion of a novel concept as a program that may be composed of existing concepts, and compare the ability of different models as well as our approach to learn such concepts from few examples. data augmentation. recently, there have been several approaches attempting to improve systematicity of deep neural networks by using data augmentation. one approach, called data recombination @xcite , is to substitute concepts with other words of the same type. however, their approach assumes the type of the concept word is known, whereas we do not make this assumption. furthermore, their approach is restricted to shallow concepts similar to the jump concept in (lake and baroni, 2018), and does not extend to higher-order concepts. another approach is "good enough compositional data augmentation" (andreas, 2020), which uses overlap with other concepts of the same type in the training data to perform data augmentation. in our setting, because we only provide a single teaching example, there is no context overlap with other concepts of the same type in the training data, so their approach is unable to produce any new examples; thus, they perform the same as the end-to-end approach. ## substitution-driven concept learning in this section, we describe our neurosymbolic algorithm for synthesizing programmatic representations of novel concepts from few examples. ## generalization bounds in this section, we prove generalization bounds on our approach adapted to context-free parsing. ## experiments in this section, we provide empirical evidence that our approach can perform few-shot novel concept learning. we use two existing datasets, scan and geoquery, which we have extended to our setting. ## conclusion we have proposed a novel approach for few-shot novel concept learning in semantic parsing. our approach, sdcl, leverages substitutions to infer a sketch of the target program, and then uses program synthesis to infer the sub-program corresponding to the novel concept. thus, sdcl incorporates symbolic techniques that are able to learn from few examples into flexible end-to-end deep learning models. we have provided a theoretical analysis of how sdcl enables few-shot learning. finally, we have empirically demonstrated that sdcl can learn novel concepts from a single example on two semantic parsing benchmarks, which we have extended to the novel concept learning setting.