# Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2020.

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

- [MLRegTest: A Benchmark for the Machine Learning of Regular Languages](https://mlsanity.com/paper/2304.07687/) (2023)
- [Simulating Weighted Automata over Sequences and Trees with Transformers](https://mlsanity.com/paper/2403.09728/) (2024)
- [A Tensor Decomposition Perspective on Second-order RNNs](https://mlsanity.com/paper/2406.05045/) (2024)
- [Warm Starting State-Space Models with Automata Learning](https://mlsanity.com/paper/2603.05694/) (2026)
- [Sequential Density Estimation via Nonlinear Continuous Weighted Finite Automata](https://mlsanity.com/paper/2206.03923/) (2022)
- [Prompting Robot Teams with Natural Language](https://mlsanity.com/paper/2509.24575/) (2025)
- [On the Role of Depth in the Expressivity of RNNs](https://mlsanity.com/paper/2604.02201/) (2026)

## Abstract (arXiv)

In this paper, we present connections between three models used in different research fields: weighted finite automata~(WFA) from formal languages and linguistics, recurrent neural networks used in machine learning, and tensor networks which encompasses a set of optimization techniques for high-order tensors used in quantum physics and numerical analysis. We first present an intrinsic relation between WFA and the tensor train decomposition, a particular form of tensor network. This relation allows us to exhibit a novel low rank structure of the Hankel matrix of a function computed by a WFA and to design an efficient spectral learning algorithm leveraging this structure to scale the algorithm up to very large Hankel matrices.We then unravel a fundamental connection between WFA and second-orderrecurrent neural networks~(2-RNN): in the case of sequences of discrete symbols, WFA and 2-RNN with linear activationfunctions are expressively equivalent. Leveraging this equivalence result combined with the classical spectral learning algorithm for weighted automata, we introduce the first provable learning algorithm for linear 2-RNN defined over sequences of continuous input vectors.This algorithm relies on estimating low rank sub-blocks of the Hankel tensor, from which the parameters of a linear 2-RNN can be provably recovered. The performances of the proposed learning algorithm are assessed in a simulation study on both synthetic and real-world data.