Research map / Architectures and efficiency / RNNs and normalization
On the Expressivity of Recurrent Neural Cascades
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterises the regular languages recognised by recurrent neural cascades (RNCs) with sign or tanh activations, showing positive-weight RNCs capture exactly the star-free regular languages via a semigroup/group-based framework.
Problem
Whether the cascade (acyclic) architecture of recurrent neural networks limits expressivity, and what exact class of regular languages RNCs with sign and tanh activations can capture.
Approach
Analyse RNC expressivity by which semigroups and groups a single neuron can implement, using a continuous notion of homomorphism between dynamical systems and algebraic automata theory (Krohn-Rhodes decomposition): positive-weight sign/tanh neurons implement flip-flop monoids, so cascades capture exactly star-free languages, while groups require non-monotone or second-order neurons.
Key results
- RNCs with sign or tanh activations and positive recurrent weights capture exactly the star-free regular languages.
- Monotone bounded activations (sign, tanh with non-negative weights) cannot implement group operations, so a single tanh neuron and cascades of them cannot capture non-star-free languages.
- Allowing negative recurrent weights or second-order tanh neurons extends expressivity beyond star-free languages (e.g., implementing the cyclic group of order two, parity).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sign or tanh activation with non-negative recurrent weights in a cascade | Recurrent Neural Cascades · Regular languages | expressivity | No clear effect |
| Allow negative recurrent weights | Sign- or tanh-activation RNCs · Regular languages | expressivity | Helped |
| Use second-order sign or tanh neurons to implement the cyclic group of order two | Recurrent Neural Cascades · Regular languages | expressivity | Helped |
| Allow arbitrary cyclic dependencies among recurrent neurons | RNNs with sign or tanh activation · Regular languages | expressivity | Helped |
Surprising findings
- Acyclicity (cascade architecture) does not limit expressivity within the star-free class, contrary to the suggestion that cyclic dependencies are needed.
Limitations
- Results are theoretical and stated for regular functions under idealised continuous neurons.
- Group operations (beyond C2 and simple groups) are not shown to be implementable by standard sign/tanh neurons.
Experimental setup
Baselines: tanh RNN expressivity results (prior work on RNCs)
Builds on: Krohn-Rhodes decomposition theorem Letichevsky decomposition theorem recurrent cascade correlation
Closest papers by meaning
- RNNs of RNNs: Recursive Construction of Stable Assemblies of Recurrent Neural Networks (NeurIPS 2022 · similarity 0.88)
- Efficient recurrent architectures through activity sparsity and sparse back-propagation through time (ICLR 2023 · similarity 0.87)
- Dynamical Isometry and a Mean Field Theory of RNNs: Gating Enables Signal Propagation in Recurrent Neural Networks (ICML 2018 · similarity 0.86)
- Framing RNN as a kernel method: A neural ODE approach (NeurIPS 2021 · similarity 0.86)
- State-Regularized Recurrent Neural Networks (ICML 2019 · similarity 0.86)
- Recurrent neural networks: vanishing and exploding gradients are not the end of the story (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.