Source-linked AI summary
Architectural Complexity Measures of Recurrent Neural Networks
Saizheng Zhang, Yuhuai Wu, Tong Che, Zhouhan Lin, Roland Memisevic, Ruslan Salakhutdinov, Yoshua Bengio
TL;DR
RNN connecting architectures lack a general formalization and quantitative measures of architectural complexity. The paper introduces a graph-theoretic framework and three measures—recurrent depth, feedforward depth, and recurrent skip coefficient—and proves their existence and computability. Experiments report benefits from increasing recurrent and feedforward depth in some settings, while larger recurrent skip coefficients can improve long-term dependency performance.
Problem
Previous work lacked a general definition and quantitative measurements for the connecting architectures and depth of RNNs.
Method
The paper formulates RNN connecting architectures as graphs and defines recurrent depth, feedforward depth, and recurrent skip coefficient from graph-theoretic properties.
Results
The experiments find that increasing recurrent and feedforward depth can improve performance in some settings, while increasing recurrent skip coefficient can largely improve long-term dependency performance.
Takeaways & Limitations
The measures and results provide guidance for designing recurrent architectures for particular learning tasks.
Takeaways & Limitations
The complexity analysis assumes homogeneous, unidirectional RNNs; bidirectional models are treated as unidirectional components.
Abstract
from arXiv · showhide
In this paper, we systematically analyze the connecting architectures of recurrent neural networks (RNNs). Our main contribution is twofold: first, we present a rigorous graph-theoretic framework describing the connecting architectures of RNNs in general. Second, we propose three architecture complexity measures of RNNs: (a) the recurrent depth, which captures the RNN's over-time nonlinear complexity, (b) the feedforward depth, which captures the local input-output nonlinearity (similar to the "depth" in feedforward neural networks (FNNs)), and (c) the recurrent skip coefficient which captures how rapidly the information propagates over time. We rigorously prove each measure's existence and computability. Our experimental results show that RNNs might benefit from larger recurrent depth and feedforward depth. We further demonstrate that increasing recurrent skip coefficient offers performance boosts on long term dependency problems.
1 Introduction
The paper addresses the underformalized connecting architectures of RNNs by introducing a general graph-based formulation and quantitative measures of their complexity. It defines recurrent depth, feedforward depth, and recurrent skip coefficient, then evaluates architectures with varying depths and skip coefficients.
- RNN research has focused on optimization, gradient instability, and transition units, while connecting architectures received less systematic attention.
- Previous work explored stacked RNNs, skip connections, and multiple notions of depth without rigorously formalizing depth or its implications.
- The paper represents general RNN connecting architectures with a well-defined graph framework and analyzes transformations along recurrent and feedforward directions.
- Recurrent depth, feedforward depth, and recurrent skip coefficient quantify over-time complexity, local input-output complexity, and information propagation across time.The skip coefficient is connected to long-term dependency problems and vanishing or exploding gradients.
- Experiments evaluate models with different recurrent depths, feedforward depths, and recurrent skip coefficients on sequential modeling tasks.
2 General Formulations of RNN Connecting Architectures
The paper models RNN connecting architectures as finite weighted directed multigraphs and unfolds them across time into infinite directed acyclic graphs. This representation links graph edges, time delays, transition functions, and information flow in a unified framework.
- An RNN cyclic graph is a finite weighted directed multigraph whose nodes represent input, hidden, or output units and whose edge weights encode time-related offsets.Its defining conditions enforce periodic unfolding, at least one directed cycle, and no zero-weight closed walk.
- Unfolding replicates cyclic-graph nodes across time and creates edges whose temporal differences equal the corresponding cyclic edge weights.
- The unfolding of any RNN cyclic graph is a directed acyclic graph.
- The cyclic and unfolded graph representations correspond one-to-one, with cyclic edge weights determining how edges travel through time.For example, a weight of 1 advances an edge by one time step, while a loop with weight 2 advances it by two.
- The framework supports periodic RNNs with period number m, including ordinary architectures with m = 1 and structures such as hierarchical or clockwork RNNs with m > 1.
- Each node applies a transition function to the outputs of its incoming nodes, allowing vanilla RNNs, LSTMs, and GRUs to fit the same connecting-architecture framework.
- An RNN is specified by its cyclic graph, unfolded graph, and node transition functions; homogeneous RNNs share one transition-function form across hidden nodes.
3 Measures of Architectural Complexity
The paper measures RNN architectural complexity through recurrent depth, feedforward depth, and recurrent skip coefficient. These measures separately characterize long-run transformations, local input-output transformations, and the rate of information propagation across time.
- The analysis assumes homogeneous, unidirectional RNNs, treating bidirectional models as separate unidirectional components.
- 3.1 Recurrent Depth: Recurrent depth measures the asymptotic average maximum number of nonlinear transformations per time step along recurrent paths.It is defined from the growth rate of the longest path length over increasing time intervals and is computable under a mild assumption.
- 3.1 Recurrent Depth: For simple and stacked RNNs, recurrent depth equals 1, indicating that their nonlinearities increase at the same rate over time despite different layer counts.
- 3.3 Feedforward Depth: Feedforward depth captures the short-run maximum input-to-output transformations that recurrent depth does not characterize well.
- 3.3 Feedforward Depth: The bound D*i(n) ≤ n · dr + df shows that feedforward depth dominates for small n, whereas recurrent depth determines the growth for large n.
- 3.5 Recurrent Skip Coefficient: The recurrent skip coefficient is the reciprocal of the shortest-path growth rate and increases when fewer transformations are required per time step.Larger values permit information to skip across multiple time steps and are intended to alleviate long-term dependency problems.
4 Experiments and Results
The experiments test whether recurrent and feedforward depth improve performance and whether larger recurrent skip coefficients help on long-term dependency tasks. Results favor moderate depth increases and larger skip coefficients, although effects depend on task and architecture.
- Tasks and Training Settings: The experiments evaluate depth and recurrent skip coefficients across language modeling, adding, copying memory, sequential MNIST, and permuted MNIST.The study includes tanh RNNs and LSTMs, with task-specific settings and approximately parameter-matched comparisons.
- Recurrent Depth is Non-trivial: The td architecture outperforms sh, st, and bu across the evaluated tanh RNN and LSTM settings.On PennTreebank, td tanh RNN reaches test BPC 1.49; on text8, td LSTM-large reaches BPC 1.49.
- Comparing Depths: On text8, the best test BPC occurs with df = 3 and dr = 2, while excessive depth can hurt performance.Increasing dr or df helps at moderate values, but dr = 3 or df = 4 can reduce performance, potentially because of optimization issues.
- Recurrent Skip Coefficients: Increasing the recurrent skip coefficient improves long-term dependency performance on the adding and copying memory problems.For adding, s = 30 succeeds at T = 750 and T = 1000; for copying memory, s = 40 lowers CE from 0.2409 to 0.0975 at T = 200.
- Recurrent Skip Coefficients: Larger recurrent skip coefficients substantially improve sequential MNIST performance, including for tanh RNNs and LSTMs.The study reports that s > 1 improves tanh RNNs, while LSTM gains depend on the dataset and saturate differently for MNIST and pMNIST.
- Recurrent Skip Coefficients vs. Skip Connections: Among architectures with skip connections, larger recurrent skip coefficients produce better sequential MNIST and pMNIST performance.With the same skip length k, model (3) outperforms model (2) despite differing only in skip-connection direction.
5 Conclusion
The paper introduces a graph-based framework and three measures of RNN architectural complexity: recurrent depth, feedforward depth, and recurrent skip coefficient.
- The framework formalizes RNN connecting architectures through graph representations for architectural complexity analysis.
- Recurrent depth and feedforward depth capture short-term and over-time nonlinear properties of RNNs.
- The recurrent skip coefficient captures long-term information propagation and can improve performance on long-term dependency tasks.
- Increasing recurrent depth and feedforward depth might improve performance, although increasing feedforward depth might not help long-term dependency tasks.
- The measures and empirical findings provide guidance for designing recurrent architectures for particular learning tasks.
A Proofs
The proofs establish structural properties of the graph-based complexity measures, including existence, periodicity, path decompositions, and bounds relating path lengths to recurrent and feedforward depths.
- The quantities d_i and s_i are periodic with period m across time indices.
- The recurrent-depth proof bounds long paths using directed-cycle lengths and their summed recurrent skip coefficients.The argument considers repeated traversal of cycles and derives corresponding asymptotic bounds.
- Walks in the cyclic graph are decomposed into a path and directed cycles by iteratively removing cycles.The decomposition preserves the walk’s directed-edge sequence through the path and cycle components.
- The feedforward-depth supremum exists and is finite under the stated graph construction.The proof defines a periodic per-time quantity and establishes a finite upper bound.
- For all time steps and integer horizons, the path-length quantity is bounded by n · d_r + d_f.
B.1 RNNs with tanh
The tanh-RNN formulation computes each node from incoming node outputs by applying affine transformations, summing them, and passing the result through tanh.
- Each tanh-RNN node applies the tanh transition function to summed affine transformations of all incoming nodes.The bias term is omitted in the described computation.
- The node output is represented as a vector h_v computed from its incoming-node inputs.
- The bottom-up architecture is used as a concrete example of the node-computation formulation.
B.3 Recurrent Depth is Non-trivial
Figure 4 compares validation curves for four connecting architectures on text8 using tanhRNN-small and LSTM-small models.
- The figure compares sh, st, bu, and td connecting architectures on the text8 dataset.
- The left panel reports tanhRNN-small results, while the right panel reports LSTM-small results.
B.4 Full Comparisons on Depths
The experiments compare nine architectures across feedforward depths 2–4 and recurrent depths 1–3. On sequential MNIST, increasing feedforward depth leaves performance roughly unchanged, while increasing recurrent depth may reduce performance.
- Text8: Nine architectures vary feedforward depth df = 2, 3, 4 and recurrent depth dr = 1, 2, 3 on the text8 dataset.Figure 5 presents validation curves, grouping comparisons by fixed feedforward or recurrent depth.
- Sequential MNIST: Nine architectures with df = 2, 3, 4 and dr = 1, 2, 3 are evaluated on sequential MNIST with roughly 8K parameters.The first architecture, with dr = 1 and df = 2, uses hidden size 90.
- Sequential MNIST: Increasing feedforward depth leaves model performance roughly unchanged on sequential MNIST.Figure 6 fixes recurrent depth and compares curves for df = 2, 3, 4.
- Sequential MNIST: Increasing recurrent depth may decrease performance on long-term dependency tasks.The authors suggest larger recurrent depth may amplify gradient vanishing or exploding problems.
B.5 Recurrent Skip Coefficients
The experiments show that sequential MNIST requires a larger recurrent skip coefficient than pMNIST for good performance. The proposed explanation concerns consecutive zero-valued subsequences in sequential MNIST and their effect on gradient flow.
- Dataset comparison: Good performance on MNIST requires a larger recurrent skip coefficient s than on pMNIST.The authors attribute this difference to the structure of the input sequences.
- Sequential MNIST: Sequential MNIST contains consecutive zero-valued subsequences lasting 10 to 20 steps, where input-output gradient flow may vanish.A sufficiently large s can cover these subsequences, after which the model starts to perform better.
- pMNIST: Permutation blends zeros and ones into more uniform pMNIST sequences, which may make training easier despite the randomized order.The authors propose this as an explanation for the reduced impact of long zero sequences.
B.6 Recurrent Skip Coefficients vs. Skip Connections
The comparison examines skip-coefficient architectures on MNIST and pMNIST. One architecture initially performs worse but later surpasses another, consistent with stronger long-run skipping effects.
- Training curves: Architecture (3) is usually worse than (2) early in training but surpasses (2) midway through training.The authors relate the early advantage of (2) to easier information transfer through its skip connections.
- Training curves: Architecture (3) may gain an advantage only after multiple k time steps because its recurrent skip connections exert a stronger long-term skipping effect.Architecture (2) has shorter paths and therefore easier initial gradient flow.
- Experimental setup: Test curves compare architectures (1), (2), (3), and (4) with tanh, with recurrent skip coefficients shown in the legends.Figure 8 reports these comparisons on MNIST and pMNIST.