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

Saujas Vaduguru, Aalok Sathe, Monojit Choudhury, Dipti Misra Sharma

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

Deep learning has revolutionized Natural Language Processing, but it faces a significant "data hunger" problem. Modern neural models typically require hundreds or thousands of examples to learn phonological or morphological patterns, such as converting a singular noun into a plural. Furthermore, these models are often "black boxes," providing little insight into the reasoning behind their predictions.

In contrast, humans can often deduce the rules of a foreign language from just a few instances. This cognitive ability is the foundation of the Linguistics Olympiad, where students solve puzzles in unfamiliar languages. This research investigates whether we can build a system that reasons like a linguist by moving away from statistical pattern matching toward program synthesis—finding explicit, interpretable rules that generalize from minimal data.

Methods: Synthesis as Rule Discovery

The authors treat linguistic rule-learning as a program synthesis task. Instead of training a neural network, the system searches for a program in a Domain-Specific Language (DSL) that maps input strings to output strings.

The program synthesis pipeline, showing the transition from word-level examples to token-level alignments, candidate generation, and final rule selection.

Key components of the methodology include:

  • The DSL: A declarative language designed to represent "rewrite rules" (e.g., "replace 'd' with 's' if it's followed by an 'i'"). It includes predicates to check context and transformations to modify tokens.
  • NDSyn Algorithm: An extension of the FlashMeta framework that decomposes the search for a complex program into smaller, manageable sub-problems.
  • Multi-pass Synthesis: The system can apply rules in sequence, allowing it to handle complex, multi-step linguistic changes.
  • Ranking Score: To choose between multiple programs that fit the data, the system uses a ranking score that favors shorter, more general programs over long, overly specific ones—a computational implementation of Occam's Razor.

Datasets

The researchers curated a new dataset of 34 linguistics problems sourced from various Linguistics Olympiads. These problems cover four main categories: Morphophonology (sound changes during word formation), Multilingual mapping, Transliteration, and Stress identification. The dataset is exceptionally small by AI standards, averaging just 43 training words per problem, making it a rigorous test of "few-shot" learning.

Key Insights and Results

The program synthesis approach significantly outperformed traditional neural models and Weighted Finite State Transducers (WFSTs). The best synthesis variant (TOKEN) achieved 32.7% overall exact match accuracy, compared to just 8.2% for an LSTM and 5.4% for a Transformer. In the morphophonology category, the synthesis model reached 38.6% accuracy.

Correlation between the number of rules per program and exact match accuracy across different model variants. Shorter programs generally correlate with higher accuracy.

Several key findings emerged from the analysis:

  • Domain Knowledge as a Constraint: Defining a DSL "bakes in" the basic structure of phonology, narrowing the search space compared to neural networks that must learn basic concepts from scratch.
  • Features Aid Generalization: When the model has access to linguistic features (e.g., "is this a vowel?"), it learns more robust rules. Instead of a rule for a specific letter, it might learn a rule for all "voiceless sounds."
  • The "Shortness" Bias: The study confirms that "correct" linguistic programs tend to be shorter. As shown in the experimental results, very long, complex programs were usually a sign of overfitting—memorizing training data rather than learning the underlying rule.

Limitations and Future Work

While successful, the system has clear boundaries. It operates primarily at the token level and struggles with "global" rules, such as stress patterns that depend on the structure of an entire word. It also failed on "reduplication" (repeating parts of a word) because the current DSL lacks the ability to reference variable-length spans of text. Future work could explore learning linguistic features automatically rather than relying on manual engineering.

Summary updated

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.
BibTeX
@inproceedings{vaduguru2021sample,
  author = {Saujas Vaduguru and Aalok Sathe and Monojit Choudhury and Dipti Misra Sharma},
  title = {{Sample-efficient Linguistic Generalizations through Program Synthesis: Experiments with Phonology Problems}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure