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

Saujas Vaduguru, Aalok Sathe, Monojit Choudhury, Dipti Sharma

TL;DR

This paper explores learning linguistic rules from very few examples using program synthesis, a technique that generates explicit, human-readable programs. They demonstrate that this approach significantly outperforms neural models on challenging phonology tasks from the Linguistics Olympiad, showcasing its potential for sample-efficient and interpretable rule learning.

What Problem Does This Paper Address?

Modern NLP models, particularly neural networks, have achieved remarkable success in tasks like phonology and morphology. However, this success often comes at the cost of requiring massive datasets – hundreds or thousands of examples per language. Furthermore, the patterns these models learn are typically opaque "black boxes," making it difficult to understand why they make certain predictions. This is in stark contrast to human linguistic learning, where we can often infer rules from just a handful of examples and articulate those rules explicitly. The paper addresses this gap by investigating whether program synthesis, a method for automatically generating programs from examples, can learn interpretable linguistic rules efficiently from minimal data.

Methods

The core of the paper's approach is program synthesis. They frame the problem as learning a program in a domain-specific language (DSL) that transforms input tokens (representing sounds or features) into output tokens. This DSL is designed to capture phonological transformations, allowing for operations like replacing, inserting, or deleting tokens, and crucially, incorporating context through predicates.

Key aspects of their method include:

  • Domain-Specific Language (DSL): The DSL defines a set of predicates (e.g., checking if a token is a specific sound, or if a feature is true) and transformations (e.g., ReplaceBy, Insert, Delete). This allows encoding linguistic knowledge directly into the system.
  • Program Synthesis Algorithm (NDSyn): They use an extension of the NDSyn algorithm, which is designed to learn disjunctions of rules. This algorithm works in multiple passes, allowing it to learn "stateful multi-pass rules" that can build upon previous transformations.
  • FlashMeta: This algorithm is used to generate candidate rules by searching for programs that satisfy input-output examples. It recursively breaks down the problem into smaller sub-problems.
  • Ranking Score: A scoring mechanism is used to prioritize certain rules, allowing for preferences for shorter programs or rules that use more general features.
  • Token-Level Examples: The system operates on token-level examples, where each token is a symbol accompanied by a feature set (key-value pairs).

Datasets

The paper introduces a new benchmark dataset for evaluating their approach.

  • Linguistics Olympiad Problems: They curate a dataset of 34 problems from various Linguistics Olympiads. These problems are specifically chosen because they:
  • Require learning from a minimal number of examples (typically 20-50 forms).
  • Focus on surface word forms rather than requiring deep semantic or syntactic knowledge.
  • Are designed to test generalization abilities.
  • Cover various linguistic phenomena including morphophonology, multilingualism, transliteration, and stress.

The dataset consists of training examples (data) and test examples (assignments).

Key Insights and Ideas

  • Sample Efficiency: Program synthesis can learn complex linguistic rules from a surprisingly small number of examples, a capability that current neural models struggle with.
  • Interpretability: The generated programs are human-readable, providing explicit rules that explain the transformations, unlike opaque neural models.
  • Controllable Generalization: The DSL and ranking scores allow for explicit control over the types of rules learned, enabling a preference for more general rules (e.g., using features) over specific ones.
  • Features Aid Generalization: Incorporating features into the DSL significantly improves the model's ability to generalize, leading to more robust rule learning.
  • Program Length as a Proxy for Overfitting: Shorter programs tend to correlate with better generalization, suggesting that overly complex rule sets can overfit to the training data.

Key Results

The paper reports significant improvements over baseline methods:

  • Overall Performance: Program synthesis models consistently outperform neural models (LSTM, Transformer) and WFST baselines on the Linguistics Olympiad tasks.
  • EXACT Match Accuracy: The "FEATURE" variant of their program synthesis system achieved the highest EXACT match accuracy, indicating it correctly solved the most problems. For instance, on morphophonology problems, the FEATURE system achieved 38.6% EXACT accuracy, compared to 30.1% for NOFEATURE and 37.5% for TOKEN.
  • CHRF Score: The synthesis models also performed well on the CHRF score, which measures token-level accuracy.
  • Specific Problem Types: While program synthesis excelled across most categories, it showed particular strength in morphophonology and multilingual tasks. Transliteration was an exception where baselines performed better, possibly due to issues with pre-processing.

Limitations and Future Work

  • DSL Limitations: The current DSL lacks predicates or transformations to directly reference spans of multiple tokens (e.g., syllables), limiting its ability to model phenomena like reduplication.
  • Word-Level Constraints: The token-level nature of the examples means the system doesn't inherently handle word-level constraints, which can be crucial for tasks like stress assignment.
  • Future Work: The authors suggest extending the DSL to handle more complex features (e.g., semantic categories), incorporating word-level information, and applying the approach to more complex linguistic domains like morphology and syntax. They also highlight the potential of program synthesis for understanding linguistic learning biases.

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 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