Few-Shot Novel Concept Learning for Semantic Parsing

Soham Dan, Osbert Bastani, Dan Roth


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.
Anthology ID:
2021.findings-emnlp.177
Volume:
Findings of the Association for Computational Linguistics: EMNLP 2021
Month:
November
Year:
2021
Address:
Punta Cana, Dominican Republic
Editors:
Marie-Francine Moens, Xuanjing Huang, Lucia Specia, Scott Wen-tau Yih
Venue:
Findings
SIG:
SIGDAT
Publisher:
Association for Computational Linguistics
Note:
Pages:
2064–2075
Language:
URL:
https://aclanthology.org/2021.findings-emnlp.177
DOI:
10.18653/v1/2021.findings-emnlp.177
Bibkey:
Cite (ACL):
Soham Dan, Osbert Bastani, and Dan Roth. 2021. Few-Shot Novel Concept Learning for Semantic Parsing. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 2064–2075, Punta Cana, Dominican Republic. Association for Computational Linguistics.
Cite (Informal):
Few-Shot Novel Concept Learning for Semantic Parsing (Dan et al., Findings 2021)
Copy Citation:
PDF:
https://aclanthology.org/2021.findings-emnlp.177.pdf
Video:
 https://aclanthology.org/2021.findings-emnlp.177.mp4