Nonlinear Weighted Finite Automata

Tianyu Li, Guillaume Rabusseau, Doina PrecupAISTATS 2018 · OpenReview

Abstract: Weighted finite automata (WFA) can expressively model functions defined over strings but are inherently linear models. Given the recent successes of non-linear models in machine learning, it is natural to extend this framework. This paper introduces Nonlinear Weighted Finite Automata (NL-WFA), a model that bridges the gap between classical formal language theory and modern deep learning. By replacing the linear components of traditional automata with neural networks, the authors create a model that captures complex, non-linear patterns in sequence data using significantly fewer states and less training data than its linear predecessors.

Introduction

Weighted Finite Automata (WFA) are a staple in sequence modeling, used for applications ranging from speech recognition to bioinformatics. They are prized for being succinct and mathematically well-understood. However, WFA are inherently linear: their computations are restricted to a series of matrix multiplications.

In the current era of machine learning, nonlinearity is essential for capturing the complex structures of real-world data. While Recurrent Neural Networks (RNNs) provide this nonlinearity, they are often viewed as "black boxes" difficult to reconcile with formal language theory. This research asks: Can we inject the power of neural networks into the WFA framework without losing the structural benefits of automata?

Methods

The authors base their approach on the spectral learning algorithm, a classic two-step method for training linear WFA:

  1. Factorization: Decomposing a "Hankel matrix" (prefixes vs. suffixes) to find a low-dimensional vector representation for every prefix.
  2. Regression: Finding transition matrices that map the representation of a prefix $u$ to the representation of $u\sigma$.

The NL-WFA Innovation: Instead of using linear algebra (like SVD), the authors employ neural networks:

  • Nonlinear Factorization: An auto-encoder compresses the rows of the Hankel matrix into a latent state, allowing the model to disentangle complex data structures.
  • Nonlinear Regression: Standard transition matrices are replaced with feed-forward neural networks. Each symbol in the alphabet is assigned a small network to compute internal state evolution.
Architectures for Nonlinear Factorization and Transition Networks

Crucially, unlike RNNs, this model does not rely on Backpropagation Through Time (BPTT). Instead, it follows the two-stage spectral logic, which can be more computationally efficient and provides a distinct inductive bias.

Results and Key Insights

The model was evaluated on synthetic data (Probabilistic Dyck Language) and real-world data (Penn Treebank character-level English verbs).

State Efficiency

A key finding is that nonlinearity allows for much smaller models. A linear WFA might require a massive number of states to approximate a function that an NL-WFA can represent with just a few states and a couple of nonlinear layers.

Pautomac Score vs. Number of States on the Dyck language task

Performance Benchmarks

  • Synthetic Data: On the Dyck language, NL-WFA achieved significantly lower Word Error Rates (WER) and better Pautomac scores than linear WFA, especially when the number of states was small (e.g., under 10 states).
  • Sample Complexity: NL-WFA converged to better performance with much less training data than the linear version.
  • Real-World Data: On the Penn Treebank task, the NL-WFA outperformed HMMs, linear WFA, and even LSTMs on the Pautomac score across all sample sizes. While LSTMs eventually matched prediction accuracy (WER) as data increased, NL-WFA remained superior in the "small data" regime.

Conclusion

NL-WFA demonstrates that the "spectral" view of learning is a natural fit for training neural architectures on sequences. By performing a nonlinear version of the "kernel trick," the model maps data into a high-dimensional feature space where transitions become much more expressive. Future work will focus on refining hyperparameter tuning, establishing theoretical consistency guarantees, and scaling the model to massive corpora.

Summary updated

Abstract

Weighted finite automata (WFA) can expressively model functions defined over strings but are inherently linear models.Given the recent successes of non-linear models in machine learning, it is natu...
BibTeX
@inproceedings{li2018nonlinear,
  author = {Tianyu Li and Guillaume Rabusseau and Doina Precup},
  title = {{Nonlinear Weighted Finite Automata}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=4jhWwAMVydm},
}
Figure