Sample-efficient Linguistic Generalizations through Program Synthesis: Experiments with Phonology Problems (2021)

Abstract: Neural models excel at extracting statistical patterns from large amounts of data, but struggle to learn patterns or reason about language from only a few examples. In this paper, we ask: Can we learn explicit rules that generalize well from only a few examples? We explore this question using program synthesis. We develop a synthesis model to learn phonology rules as programs in a domain-specific language. We test the ability of our models to generalize from few training examples using our new dataset of problems from the Linguistics Olympiad, a challenging set of tasks that require strong linguistic reasoning ability. In addition to being highly sample-efficient, our approach generates human-readable programs, and allows control over the generalizability of the learnt programs.

## introduction in the last few years, the application of deep neural models has allowed rapid progress in nlp. tasks in phonology and morphology have been no exception to this, with neural encoder-decoder models achieving strong results in recent shared tasks in phonology @xcite and morphology @xcite . however, the neural models that perform well on these tasks make use of hundreds, if not thousands of training examples for each language. additionally, the patterns that neural models identify are not interpretable. in this paper, we explore the problem of learning interpretable phonological and morphological rules from only a small number of examples, a task that humans are able to perform. consider the example of verb forms in the language mandar presented in program synthesis @xcite is a method that can be used to learn programs that map an input to an output in a domain-specific language (dsl). it has been shown to be a highly sampleefficient technique to learn interpretable rules by specifying the assumptions of the task in the dsl @xcite . this raises the questions (i) can program synthesis be used to learn linguistic rules from only a few examples? (ii) if so, what kind of rules can be learnt? (iii) what kind of operations need to explicitly be defined in the dsl to allow it to model linguistic rules? (iv) what knowledge must be im-plicitly provided with these operations to allow the model to choose rules that generalize well? in this work, we use program synthesis to learn phonological rules for solving linguistics olympiad problems, where only the minimal number of examples necessary to generalize are given @xcite . we present a program synthesis model and a dsl for learning phonological rules, and curate a set of linguistics olympiad problems for evaluation. we perform experiments and comparisons to baselines, and find that program synthesis does significantly better than our baseline approaches. we also present some observations about the ability of our system to find rules that generalize well, and discuss examples of where it fails. ## program synthesis program synthesis is "the task of automatically finding programs from the underlying programming language that satisfy (user) intent expressed in some form of constraints" @xcite . this method allows us to specify domain-specific assumptions as a language, and use generic synthesis approches like flashmeta @xcite to synthesize programs. the ability to explicitly encode domain-specific assumptions gives program synthesis broad applicability to various tasks. in this paper, we explore applying it to the task of learning phonological rules. whereas previous work on rule-learning has focused on learning rules of a specific type @xcite , the dsl in program synthesis allows learning rules of different types, and in different rule formalisms. in this work, we explore learning rules similar to rewrite rules @xcite ) that are used extensively to describe phonology. sequences of rules are learnt using a noisy disjunctive synthesis algorithm ndsyn @xcite extended to learn stateful multi-pass rules @xcite . ## dataset to test the ability of our program synthesis system to learn linguistic rules from only a few examples, we require a task with a small number of training examples, and a number of test examples which measure how well the model generalises to unseen data. additionally, to ensure a fair evaluation, the test examples should be chosen such that the samples in the training data provide sufficient evidence to correctly solve the test examples. to this end, we use problems from the linguistics olympiad. the linguistics olympiad is an umbrella term describing contests for high school students across the globe. students are tasked with solving linguistics problems-a genre of composition that presents linguistic facts and phenomena in enigmatic form @xcite . these problems typically have 2 parts: the data and the assignments. the data consists of examples where the solver is presented with the application rules to some linguistic forms (words, phrases, sentences) and the forms derived by applying the rules to these forms. the data typically consists of 20-50 forms, the minimal number of examples required to infer the correct rules is presented @xcite . the assignments provide other linguistic forms, and the solver is tasked with applying the rules inferred from the data to these forms. the forms in the assignments are carefully selected by the istoken (w ," a " , -1) istoken (w ," b " ,0) istoken (w ," c " ,1) ## analysis we examine two aspects of the program synthesis models we propose. the first is the way it uses the explicit knowledge in the dsl and implicit knowledge provided as the ranking score to generalize. we then consider specific examples of problems, and show examples of where our models succeed and fail in learning different types of patterns. ## conclusion in this paper, we explore the problem of learning linguistic rules from only a few training examples. we approach this using program synthesis, and demonstrate that it is a powerful and flexible technique for learning phonology rules in olympiad problems. these problems are designed to be challenging tasks that require learning rules from a minimal number of examples. these problems also allow us to specifically test for generalization. we compare our approach to various baselines, and find that it is capable of learning phonological rules that generalize much better than existing approaches. we show that using the dsl, we can explicitly control the structure of rules, and using the ranking score, we can provide the model with implicit preferences for certain kinds of rules. having demonstrated the potential of program synthesis as a learning technique that can work with very little data and provide human-readable models, we hope to apply it to learning more complex types of lingusitic rules in the future. in addition to being a way to learn rules from data, the ability to explicity control the generalization behaviour of the model allows for the use of program synthesis to understand the kinds of learning biases and operations that are required to model various linguistic processes. we leave this exploration to future work. research in phonetics, phonology, and morphology, pages 1-39, online. association for computational linguistics. elysia warner. 2019. tarangan. in samuel ahmed, bozhidar bozhanov, ivan derzhanski (technical editor), hugh dobbs, dmitry gerasimov, shinjini ghosh, ksenia gilyarova, stanislav gurevich, gabrijela hladnik, boris iomdin, bruno l'astorina, tae hun lee (editor-in chief), tom mccoy, andré nikulin, miina norvik, tung-le pan, aleksejs peguševs, alexander piperski, maria rubinstein, daniel rucki, artūrs semen ¸uks, nathan somers, milena veneva, and elysia warner, editors, international linguistics olympiad 2019. international linguistics olympiad. shijie wu. 2020. neural transducer. https://github. com/shijie-wu/neural-transducer/ .