Constraint-based Learning of Phonological Processes

Shraddha Barke, Rose Kunkel, Nadia Polikarpova, Eric Meinhardt, Eric Bakovic, Leon BergenEMNLP 2019 · OpenReview

Abstract

Shraddha Barke, Rose Kunkel, Nadia Polikarpova, Eric Meinhardt, Eric Bakovic, Leon Bergen. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).

2019.

Introduction

Phonological processes are the cognitive rules governing how sounds transform based on their phonetic environment. For example, in English, the past-tense suffix /-d/ surfaces as [d] in "begged" but shifts to [t] in "zipped" due to the preceding voiceless consonant. Traditionally, linguists discover these rules by comparing spoken "surface forms" to mental "underlying forms." Automating this discovery is a significant challenge in computational linguistics because underlying forms are latent (not provided in raw data), and the resulting models must be human-readable to be useful for linguistic theory.

Previous automated attempts using program synthesis were often prohibitively slow, requiring nearly an hour to solve a single textbook problem. This paper introduces SYPHON, a system that treats rule discovery as a constraint-based program synthesis problem, achieving state-of-the-art accuracy with a 100x speedup.

Methods: The SYPHON Pipeline

SYPHON navigates an astronomical search space (estimated at $2^{600}$ possible configurations) by decomposing the problem into a manageable three-step pipeline using SMT (Satisfiability Modulo Theories) solvers:

  1. Underlying Form Inference: Using the Z3STR2 string solver, the system generates candidate latent stems and suffixes. It prioritizes candidates with a small edit distance from spoken forms, assuming linguistic simplicity.
  2. Change Inference: The system identifies the specific phonetic transformations (the "what"), such as /z/ becoming [s].
  3. Condition Inference: Using SMT solvers, it identifies the simplest logical context (the "where") that triggers the change.
Overview of the SYPHON pipeline for learning phonological rules from surface forms.

The system utilizes a Bayesian objective function that balances a "simplicity prior" (favoring shorter rules) with a "strong sampling" likelihood, which assumes the data was specifically chosen to illustrate the rule. This allows the solver to avoid overly broad generalizations.

Results and Evaluation

The researchers evaluated SYPHON on 34 curated textbook problems and large-scale lexical databases, including the CMU Pronouncing Dictionary and CELEX-2.

Performance and Speed

SYPHON solved textbook problems in an average of 30 seconds, compared to the previous state-of-the-art baseline of 51 minutes—a speedup of over 100x. On these problems, the system achieved 100% accuracy in recovering correct surface forms. Furthermore, SYPHON demonstrated extreme data efficiency, learning complex rules from as few as 5 to 30 data points, a task currently difficult for deep learning models.

Interpretability

A primary goal of SYPHON is generating rules that match human intuition. The system successfully inferred rules for diverse linguistic phenomena, including Russian final-devoicing, Korean consonant changes, and English flapping.

Inferred phonological rules across various linguistic datasets.

As shown in the table above, the inferred rules are expressed in standard linguistic feature notation, making them immediately interpretable to researchers.

Discussion and Limitations

The success of SYPHON demonstrates that decomposing rule discovery from underlying form inference makes the search space tractable for modern solvers. By encoding linguistic constraints into SMT, the system can exhaustively prove a rule is the simplest possible for a given dataset.

However, SYPHON currently operates under several constraints: it only considers immediate local contexts (trigrams), lacks support for disjunctive ("OR") logic in rule conditions, and assumes rules are independent rather than ordered. Future work will focus on extending the framework to handle long-distance dependencies like vowel harmony and complex rule interactions.

Summary updated

BibTeX
@inproceedings{barke2019constraint,
  author = {Shraddha Barke and Rose Kunkel and Nadia Polikarpova and Eric Meinhardt and Eric Bakovic and Leon Bergen},
  title = {{Constraint-based Learning of Phonological Processes}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=YJPRgT3G93C},
}
Figure