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:
- 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.
- Change Inference: The system identifies the specific phonetic transformations (the "what"), such as /z/ becoming [s].
- Condition Inference: Using SMT solvers, it identifies the simplest logical context (the "where") that triggers the change.
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.
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