Simple induction of (deterministic) probabilistic finite-state automata for phonotactics by stochastic gradient descent

Huteng Dai, Richard FutrellACL 2021

TL;DR

This paper introduces a general, gradient-descent-based method for learning probabilistic finite-state automata (PFAs) that model phonotactic rules in natural language. They demonstrate that while unrestricted PFAs best predict general linguistic data, specialized PFAs are crucial for capturing complex, long-distance phonotactic constraints.

What Problem Does This Paper Address?

Natural language phonotactics, the rules governing sound sequences in words, are often modeled using formal language theory, specifically regular and subregular languages. While probabilistic finite-state automata (PFAs) are powerful tools for this, efficiently learning these models from data has been a challenge. Existing methods often focus on specific subregular classes, leaving a gap for a general learner that can also be guided towards these restricted classes. This paper aims to bridge this gap by providing a unified, gradient-descent-based approach to induce PFAs, capable of learning both general regular languages and specific subregular constraints relevant to phonotactics.

Methods

The core of the paper is a novel framework for inducing PFAs using stochastic gradient descent. Key aspects include:

  • Differentiable PFA Formulation: They present a formulation of PFAs using right-stochastic matrices for emissions and transitions, making the probability of a sequence a differentiable function of the automaton's parameters. This is crucial for gradient-based optimization.
  • Stochastic Gradient Descent: They employ stochastic gradient descent (SGD) to minimize the negative log-likelihood of training data, effectively maximizing the probability of observed sequences.
  • Softmax for Constraints: To ensure the transition and emission matrices remain right-stochastic (probabilities sum to 1), they use the softmax function on underlying "logits." This allows for gradient updates on real-valued parameters that are then transformed into valid probability distributions.
  • Regularization for Determinism: They introduce a regularization term based on the nondeterminism of the PFA. This allows them to bias the learning process towards more deterministic automata, which are often preferred in linguistic theory.
  • Implementing Subregular Classes: They show how to hard-code constraints to implement specific subregular language classes, such as Strictly k-Local (k-SL) and Strictly k-Piecewise (k-SP) languages, by restricting the structure of the transition matrices.

Datasets

The paper uses two types of datasets:

  • Toy Languages: Synthetically generated data from reference automata for 2-SL and 2-SP languages were used to test the learner's ability to recover known constraints.
  • Real-World Linguistic Data:
    • Navajo: 6,279 phonological words (5,023 for training, 1,256 held-out) and 5,000 generated nonce words (labeled legal/illegal) to test nonlocal constraints.
  • Quechua: 10,804 phonological words (8,643 for training, 2,160 held-out) and 24,352 nonce words (labeled legal/illegal) for testing nonlocal constraints.

Key Insights and Ideas

  • Unrestricted vs. Restricted Learners: The study highlights a fundamental trade-off: unrestricted PFAs are better at predicting general linguistic data (held-out attested forms), but specialized, restricted PFAs (like SP) are essential for capturing specific, often nonlocal, phonotactic constraints.
  • The Power of SP for Nonlocal Constraints: Strictly Piecewise (SP) automata, despite their complexity, are shown to be surprisingly effective at learning long-distance dependencies, a common feature in phonotactics.
  • Overfitting and State Complexity: Automata with more states fit training data better but are more prone to overfitting, meaning they perform poorly on unseen data. This is a classic machine learning challenge.
  • Gradient Descent as a General Tool: The paper demonstrates that a relatively simple gradient-descent approach, without complex heuristics, can effectively learn both general and restricted phonotactic models.

Key Results

  • Toy Languages: The learner successfully recovered reference automata for both 2-SL and 2-SP languages when the appropriate learner class was used. Learners in the "wrong" class failed to capture the constraints.
  • Real-World Data (Attested Forms): Unrestricted PFAs consistently achieved the lowest held-out Negative Log Likelihood (NLL), indicating better prediction of unseen but attested words.
  • Real-World Data (Nonlocal Constraints): For predicting the ill-formedness of artificial nonce words violating nonlocal constraints, the Strictly Piecewise (SP) automaton and the SP+SL product automaton performed best. The unrestricted PFA, despite its capacity, failed to learn these specific nonlocal constraints.
  • Determinism: Induced PFAs naturally tended towards determinism over training time, and explicit regularization accelerated this process with minimal impact on NLL.

Limitations and Future Work

  • Unrestricted PFA's Failure on Nonlocal Constraints: A key limitation is that the unrestricted PFA, while good at general prediction, failed to learn the specific nonlocal constraints tested, even though it theoretically has the capacity. This suggests that the learned structure might prioritize local patterns.
  • Finding a Unified Model: The authors pose the open question of whether a single model could simultaneously excel at learning both local and nonlocal constraints.
  • Future Directions: Future work could explore other restricted language classes, alternative regularization techniques to enforce specific inductive biases, or more sophisticated model architectures that can better balance local and nonlocal pattern learning. The paper also suggests that a regularization term that directly enforces nonlocal interactions might be a fruitful avenue.

Summary updated

BibTeX
@inproceedings{dai2021simple,
  author = {Huteng Dai and Richard Futrell},
  title = {{Simple induction of (deterministic) probabilistic finite-state automata for phonotactics by stochastic gradient descent}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure