mlsanityData to 7 Oct 2026

Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning

arXiv 1807.01406 ↗First posted 4 Jul 2018cs.LG cs.FL stat.MLcited by 15

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 7; 2022: 3; 2023: 1; 2024: 3; 2025: 1.

15 papers.

Sort:

By area:

  1. 2021Thinking Like Transformerscited by 182
  2. 2024On the Tractability of SHAP Explanations under Markovian Distributionscited by 10
  3. 2021Formal Language Theory Meets Modern NLPcited by 9
  4. 2021Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Unitscited by 8
  5. 2025SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelismcited by 8
  6. 2021Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanationscited by 7
  7. 2023DeepSeer: Interactive RNN Explanation and Debugging via State Abstractioncited by 6
  8. 2021On the Memory Mechanism of Tensor-Power Recurrent Modelscited by 5
  9. 2022Implicit N-grams Induced by Recurrencecited by 4
  10. 2021Extracting Weighted Automata for Approximate Minimization in Language Modellingcited by 3
  11. 2022Understanding Robust Generalization in Learning Regular Languagescited by 3
  12. 2024Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Networkcited by 3
3 more
  1. 2024Language Modeling Using Tensor Trainscited by 3
  2. 2021WFA-IRL: Inverse Reinforcement Learning of Autonomous Behaviors Encoded as Weighted Finite Automatacited by 0
  3. 2022Are Deep Sequence Classifiers Good at Non-Trivial Generalization?cited by 0