# Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning

arXiv: https://arxiv.org/abs/1807.01406 · HTML: https://mlsanity.com/paper/1807.01406/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2018.

## Built on by (most cited first, 15 of 15)

- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units](https://mlsanity.com/paper/2104.02899/) (2021)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [DeepSeer: Interactive RNN Explanation and Debugging via State Abstraction](https://mlsanity.com/paper/2303.01576/) (2023)
- [On the Memory Mechanism of Tensor-Power Recurrent Models](https://mlsanity.com/paper/2103.01521/) (2021)
- [Language Modeling Using Tensor Trains](https://mlsanity.com/paper/2405.04590/) (2024)
- [Implicit N-grams Induced by Recurrence](https://mlsanity.com/paper/2205.02724/) (2022)
- [Extracting Weighted Automata for Approximate Minimization in Language Modelling](https://mlsanity.com/paper/2106.02965/) (2021)
- [Understanding Robust Generalization in Learning Regular Languages](https://mlsanity.com/paper/2202.09717/) (2022)
- [Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network](https://mlsanity.com/paper/2402.02627/) (2024)
- [WFA-IRL: Inverse Reinforcement Learning of Autonomous Behaviors Encoded as Weighted Finite Automata](https://mlsanity.com/paper/2103.05895/) (2021)
- [Are Deep Sequence Classifiers Good at Non-Trivial Generalization?](https://mlsanity.com/paper/2210.13082/) (2022)

## Abstract (arXiv)

In this paper, we unravel a fundamental connection between weighted finite automata~(WFAs) and second-order recurrent neural networks~(2-RNNs): in the case of sequences of discrete symbols, WFAs and 2-RNNs with linear activation functions are expressively equivalent. Motivated by this result, we build upon a recent extension of the spectral learning algorithm to vector-valued WFAs and propose the first provable learning algorithm for linear 2-RNNs defined over sequences of continuous input vectors. This algorithm relies on estimating low rank sub-blocks of the so-called Hankel tensor, from which the parameters of a linear 2-RNN can be provably recovered. The performances of the proposed method are assessed in a simulation study.