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:
- Factorization: Decomposing a "Hankel matrix" (prefixes vs. suffixes) to find a low-dimensional vector representation for every prefix.
- 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.
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.
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