Abstract
This paper presents a method for learning phonological rules from sample pairs of underlying and surface forms, without negative evidence. The learned rules are represented as finite state transducers that accept underlying forms as input and generate surface forms as output. The algorithm for learning them is an extension of the OSTIA algorithm for learning general subsequential finite state transducers. Although OSTIA is capable of learning arbitrary s.f.s.t's in the limit, large dictionaries of actual English pronunciations did not give enough samples to correctly induce phonological rules. We then augmented OSTIA with two kinds of knowledge specific to natural language phonology, biases from "universal grammar". One bias is that underlying phones are often realized as phonetically similar or identical surface phones. The other biases phonological rules to apply across natural phonological classes. The additions helped in learning more compact, accurate, and general transducers than the unmodified OSTIA algorithm. An implementation of the algorithm successfully learns a number of English postlexical rules.
Introduction
In linguistics, phonological rules describe how sounds change depending on their environment—for instance, why the "t" in butter sounds like a quick "d" (a flap) in American English. While these rules can be represented as Finite State Transducers (FSTs), automatically inducing these FSTs from examples is a significant challenge. Standard induction algorithms like OSTIA (Onward Subsequential Transducer Inference Algorithm) treat symbols as abstract tokens, lacking the "linguistic common sense" inherent in human speech. This paper by Gildea and Jurafsky demonstrates that by incorporating phonological biases—specifically phonetic similarity and natural sound classes—it is possible to transform a general-purpose state machine learner into an efficient tool for mastering complex pronunciation rules.
Methodology: Incorporating Linguistic Biases
The authors extend the vanilla OSTIA algorithm by introducing two major "Universal Grammar" biases to constrain the search space and improve generalization.
1. Alignment Information
Standard OSTIA often delays outputting symbols until the end of a word, leading to non-intuitive state transitions. The authors address this by using a dynamic programming approach to align input and output strings based on 26 phonetic features. This teaches the model that an input phone usually maps to itself or a phonetically similar neighbor, preventing the "hallucination" of random insertions or deletions.
2. Decision Tree Generalization
Rather than treating every transition as a unique event, the algorithm attaches a decision tree to each state. These trees classify incoming sounds based on phonetic features (e.g., "is it a vowel?", "is it stressed?"). By pruning these trees, the algorithm is forced to find the simplest "natural class" that explains the data, such as "all stressed vowels," rather than memorizing individual instances.
Experimental Results
The study utilized a synthetic corpus derived from the CMU Pronunciation Dictionary (99,279 pairs). Models were trained on subsets and evaluated on their ability to induce rules like flapping, t-insertion, and t-deletion.
The improvements were most dramatic in the "flapping" rule. Vanilla OSTIA, even with 50,000 samples, produced a bloated 192-state machine with a 3.14% error rate. In contrast, the augmented OSTIA induced a perfect, minimal 3-state machine using only 6,250 samples, achieving an error rate of just 0.34% (dropping to 0.01% with more data). When learning three rules simultaneously, the augmented version found a clean 5-state machine, whereas vanilla OSTIA exploded into a 329-state model with a 22% error rate.
Discussion and Conclusion
The core insight of this work is that pure mathematical induction is often too flexible for natural language. By constraining the search space with "phonological naturalness," the algorithm becomes both faster and more accurate. The state in an FST effectively represents the history of what has been heard; using decision trees to analyze the next symbol based on that state allows the model to capture context-sensitive rules effectively.
However, limitations remain. The current algorithm handles only obligatory rules and cannot yet model the probabilistic or optional rules common in casual speech. Future work suggests moving toward Probabilistic Finite State Transducers (PFSTs) to better handle the inherent messiness of real-world human language.
Summary updated