Source-linked AI summary
Unitary Evolution Recurrent Neural Networks
Martin Arjovsky, Amar Shah, Yoshua Bengio
TL;DR
RNNs are difficult to optimize over long-term dependencies because gradients can vanish or explode, motivating a recurrent architecture with unitary hidden-to-hidden weights. The paper parameterizes these matrices efficiently through structured compositions in the complex domain and reports state-of-the-art performance on hard long-term reasoning tasks.
Problem
RNN training is hindered by vanishing and exploding gradients when learning long-term dependencies, while direct unitary-matrix optimization is not straightforward and projection can cost O(n3).
Method
The paper constructs expressive unitary recurrent matrices by composing structured unitary building blocks and uses complex-valued hidden states with the modReLU nonlinearity.
Results
The proposed uRNN achieves state-of-the-art performance on hard long-term reasoning and memory tasks, including 91.4% accuracy on permuted MNIST versus 88% for LSTM.
Takeaways & Limitations
Unitary evolution is presented as a way to mitigate vanishing and exploding gradients while enabling efficient matrix computation and parameter optimization.
Takeaways & Limitations
A diagonal unitary parameterization has poor representation capacity, while richer parameterizations require more computation and memory; storing all hidden states also remains potentially prohibitive.
Abstract
from arXiv · showhide
Recurrent neural networks (RNNs) are notoriously difficult to train. When the eigenvalues of the hidden to hidden weight matrix deviate from absolute value 1, optimization becomes difficult due to the well studied issue of vanishing and exploding gradients, especially when trying to learn long-term dependencies. To circumvent this problem, we propose a new architecture that learns a unitary weight matrix, with eigenvalues of absolute value exactly 1. The challenge we address is that of parametrizing unitary matrices in a way that does not require expensive computations (such as eigendecomposition) after each weight update. We construct an expressive unitary weight matrix by composing several structured matrices that act as building blocks with parameters to be learned. Optimization with this parameterization becomes feasible only when considering hidden states in the complex domain. We demonstrate the potential of this architecture by achieving state of the art results in several hard tasks involving very long-term dependencies.
1. Introduction
The paper frames long-term dependency learning as a gradient-stability problem and proposes efficient orthogonal/unitary recurrent matrices, with complex-valued representations enabling the parameterization. The resulting architecture is reported to outperform LSTMs and prior orthogonal-initialization approaches on long-term dependency tasks.
- Motivation: Vanishing gradients erase credit-assignment signals from the distant past, while exploding gradients make gradient-based optimization unstable.These problems arise when training deep or recurrent dynamical systems.
- Related work: LSTM and GRU gating, self-loops, and orthogonal weight matrices are presented as heuristics for reducing long-term dependency difficulties.
- Contribution: The paper analyzes propagated gradients for orthogonal recurrent matrices and discusses moving to the complex domain to alleviate real-valued parameterization difficulties.
- Contribution: The proposed expressive unitary matrices use compositions of simple unitary matrices requiring at most O(n log n) computation and O(n) memory for state dimension n.General matrices require O(n2) computation and memory.
- Evaluation: Complex-valued matrices and parameters are implemented and optimized with real numbers, and experiments report generally better performance than LSTMs and prior orthogonal-initialization methods.The model is evaluated for learning long-term dependencies with relatively few parameters.
2. Orthogonal Weights and Bounding the Long-Term Gradient
This section bounds long-term gradients by combining the chain rule with operator-norm inequalities and norm-preserving orthogonal weights. With ReLU nonlinearities, the analysis yields a depth-independent bound that avoids exploding gradients, although other derivative regimes can still produce vanishing or uninformative bounds.
- Orthogonal weights: Orthogonal matrices preserve vector norms under repeated multiplication, supporting norm-based control of recurrent gradient propagation.
- Gradient analysis: The gradient between hidden layers is analyzed by applying the chain rule, with Dk+1 defined as the Jacobian of the pointwise nonlinearity.
- Gradient analysis: Operator norms provide the inequalities needed to bound products of weight and nonlinearity Jacobian matrices.
- Gradient regimes: If the activation derivative can exceed 1, the resulting bound cannot effectively control deep-network gradients and exploding gradients may occur.
- ReLU result: With ReLU nonlinearities, the analysis gives a bound that holds for arbitrary depth and makes gradient clipping unnecessary.
- Novelty: The authors describe this analysis as the first mathematical proof that a neural-network architecture avoids exploding gradients.
3. Unitary Evolution RNNs
The paper constructs expressive unitary recurrent matrices by composing simple structured unitary building blocks, avoiding the cost and representational limitations of naive parameterizations. This enables recurrent models with norm-preserving hidden states and computational costs that scale nearly linearly with hidden dimension.
- Motivation: Unitary matrices preserve eigenvalue magnitudes at 1, but direct optimization is difficult because gradient updates can leave the unitary set and projection may cost O(n3).The paper motivates a parameterization that maintains unitarity without repeated eigendecomposition.
- Parameterization: A unitary matrix can be constructed as a product of simple parametric unitary matrices, because products of unitary matrices remain unitary.The proposed strategy composes structured building blocks rather than directly learning an unconstrained matrix.
- Parameterization: The building blocks include diagonal phase matrices, complex reflection matrices, Fourier transforms, inverse Fourier transforms, and permutations.Diagonal and reflection matrices support O(n) storage and matrix-vector computation, while Fourier transforms use O(n log n) multiplication.
- Efficiency: The composed construction uses O(n log n) computation and O(n) memory, compared with O(n2) computation and memory for general matrices.Its parameter, memory, and computational costs increase almost linearly with hidden-layer size.
- Unitary Evolution RNNs: The resulting unitary evolution RNN uses a unitary hidden-to-hidden matrix, preserving hidden-state norms while providing a large memory for long-term dependencies.The paper defines any RNN with a unitary hidden-to-hidden matrix as a uRNN and selects a particular composition after experimenting with several structures.
4. Architecture details
The architecture represents complex recurrent states and parameters using real-valued operations, uses modReLU to alter magnitudes while preserving phase, and maps complex hidden states to real outputs. Norm-preserving operations also make performance relatively insensitive to parameter initialization.
- Complex-valued implementation: Complex numbers are implemented through their real and imaginary parts, allowing matrix-vector products and differentiable functions to use real-valued operations.This representation is compatible with deep-learning frameworks such as Theano.
- Input to hidden: The uRNN uses fixed input-to-hidden and hidden-to-hidden matrices across time, with a complex input matrix and a learned complex initial hidden state.The hidden state dimension is denoted nh, and the input-to-hidden matrix has shape C^nh×nin.
- Nonlinearity: Separate ReLUs on real and imaginary parts performed poorly, so the model uses modReLU, which affects only the absolute value of each complex hidden state.The paper speculates that preserving phase may help store information across many time steps, and reports that experiments supported this claim.
- Hidden to output: A real output matrix maps complex hidden states to real outputs for prediction and loss calculation.The output matrix has shape R^no×2nh, and the real output can be passed to a softmax for classification.
- Initialization: Norm-preserving operations make performance relatively insensitive to initialization, while zero biases make the network initially linear with unitary weights.The initialization scheme samples input and output matrices using Glorot initialization and samples diagonal phases uniformly over the complex unit circle.
5. Experiments
Across long-term dependency benchmarks, the uRNN generally outperformed or matched LSTMs while avoiding baseline-level failure, especially on copying memory and permuted MNIST. Exploratory analyses associate this behavior with slower gradient decay and less hidden-state saturation.
- Copying memory problem: The uRNN consistently achieved perfect performance on the copying-memory task, including time lags up to 500 steps, without getting stuck at the memoryless baseline.The LSTM and tanh RNN remained near the memoryless strategy except in the simplest case, whereas the uRNN solved the tested lengths in relatively few iterations.
- Adding problem: The uRNN and LSTM convincingly beat the adding-problem baseline through T = 400, while the tanh RNN and IRNN failed to beat it at any tested length.At T = 750, the uRNN achieved lower test error than the LSTM, although its curve was noisier.
- Pixel-by-pixel MNIST: 91.4% accuracy on permuted MNIST exceeded the LSTM’s 88% and the IRNN’s close to 82%, despite the uRNN using less than a quarter of the LSTM’s parameters.On unpermuted MNIST, the LSTM instead achieved 98.2% versus 95.1% for the uRNN.
- Pixel-by-pixel MNIST: The uRNN converged in less than 20 thousand iterations on permuted MNIST, while the LSTM required 5 to 10 times as many iterations.The figure’s comparison also reports that the uRNN converged in a fraction of the iterations required by the LSTM.
- Exploratory experiments: Initially, the uRNN propagated gradients without the exponential decay observed in the other models, and after 100 iterations it retained the least decay.Its hidden-state norms also remained more consistent over time than the LSTM’s, whose states became nearly unchanged after several steps.
- Exploratory experiments: On a T = 1000 forward pass, uRNN hidden-state norms grew steadily, whereas LSTM norms grew rapidly and then stayed constant after about 500 steps.The authors interpret the LSTM behavior as suggesting saturation in incorporating new information; at T = 750, its output correlated with the first target sample at ρ = 0.991.
6. Discussion
The discussion identifies further opportunities for reducing recurrent-network memory use and enlarging hidden layers. It also reports that uRNNs achieve state-of-the-art performance and better gradient propagation on long sequences than several compared architectures.
- Unitary weights could eliminate hidden-state storage during backpropagation if paired with an invertible nonlinearity.The inverse is the conjugate transpose, enabling hidden states to be recomputed in the backward pass.
- This approach could reduce memory usage by an order of T, the number of time steps.
- The authors suggest that lower memory use could make immensely large hidden layers possible, potentially enabling vast memory representations.
- uRNNs demonstrate state-of-the-art performance on hard problems requiring long-term reasoning and memory.
- uRNNs are reported to pass gradient information through long sequences more effectively and suffer less hidden-state saturation than LSTMs, typical RNNs, and IRNNs.