Efficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections

Zakaria Mhammedi; Andrew Hellicar; Ashfaqur Rahman; James Bailey

Source-linked AI summary

Efficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections

Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, James Bailey

arXiv:1612.00188v5Dec 1, 2016cs.LG

TL;DR

RNNs face exploding or vanishing gradients when learning long-term dependencies, while unitary approaches can limit expressiveness or scale poorly. The paper replaces complex unitary constraints with an efficient Householder-based orthogonal parametrisation, whose gradient-step complexity matches that of a simple RNN and preserves comparable benefits.

Problem
RNNs struggle with long-term dependencies because transition-matrix norms can cause exploding or vanishing gradients, while unitary methods may limit expressiveness or scale poorly.
Method
The paper parametrises orthogonal RNN transition matrices with Householder reflections and develops an efficient algorithm for their back-propagated gradients.
Results
The proposed gradient algorithm has worst-case time complexity of the same order as a simple RNN for one gradient step.
Takeaways & Limitations
Orthogonal constraints implemented through this parametrisation provide a computationally efficient alternative to unitary constraints while preventing exploding gradients.
Takeaways & Limitations
Storing Householder matrices across all time steps requires mnT values, which may be impractical when m is much greater than 1.

Abstract

from arXiv · show

The problem of learning long-term dependencies in sequences using Recurrent Neural Networks (RNNs) is still a major challenge. Recent methods have been suggested to solve this problem by constraining the transition matrix to be unitary during training which ensures that its norm is equal to one and prevents exploding gradients. These methods either have limited expressiveness or scale poorly with the size of the network when compared with the simple RNN case, especially when using stochastic gradient descent with a small mini-batch size. Our contributions are as follows; we first show that constraining the transition matrix to be unitary is a special case of an orthogonal constraint. Then we present a new parametrisation of the transition matrix which allows efficient training of an RNN while ensuring that the matrix is always orthogonal. Our results show that the orthogonal constraint on the transition matrix applied through our parametrisation gives similar benefits to the unitary constraint, without the time complexity limitations.

1. Introduction

RNNs struggle to learn long-term dependencies because transition-matrix norms can produce exploding or vanishing gradients. This work connects unitary constraints to orthogonal constraints and introduces an efficient Householder-based parametrisation.

1. Introduction: Transition-matrix spectral norms above one can cause exploding gradients, while norms below one make information vanish and hinder long-term dependency learning.These effects make training simple RNNs challenging.
1. Introduction: Unitary transition matrices avoid exploding gradients by maintaining norm one, but existing approaches can have limited expressiveness or poor scaling.The paper motivates an orthogonal alternative to address these limitations.
1. Introduction: Unitary constraints are shown to correspond to a subset of orthogonal constraints in an RNN with twice the hidden size.This equivalence motivates working with real orthogonal matrices rather than complex unitary matrices.
1. Introduction: Householder matrices provide a simple parametrisation of orthogonal RNN transition matrices, with back-propagated gradients derived for the new parameters.The parametrisation is also applicable to other deep architectures.
1. Introduction: The proposed gradient algorithm has worst-case time complexity of the same order as a simple RNN for one gradient step.This targets efficient training under stochastic gradient descent.

2. Related Work

Prior approaches preserve norm structure through initialization, unitary parametrisations, manifold optimisation, or soft orthogonal constraints. Their trade-offs include incomplete expressiveness, complex arithmetic, and O(n^3) costs, motivating the proposed approach.

2. Related Work: Orthogonal or identity initialization can improve performance, but training can later destroy the initial transition-matrix structure.The transition matrix may again develop a spectral norm different from one.
2. Related Work: The original unitary RNN uses 7n parameters and computes matrix-vector products in O(n log n), but cannot span the full unitary group when hidden size exceeds 7.This restriction may limit model expressiveness.
2. Related Work: Lie-algebra parametrisation spans the whole unitary group, but computing its matrix exponential costs O(n^3).Its full expressiveness therefore comes with cubic computational cost.
2. Related Work: Cayley-transform optimisation spans all unitary matrices but also requires matrix inverses and matrix-matrix products with O(n^3) complexity.This can be problematic for large networks trained with small mini-batches.
2. Related Work: Most reviewed orthogonality-enforcing methods require at least O(n^3) time, whereas the proposed method is included as a lower-cost alternative.The paper compares these costs for one stochastic gradient step.

3. Complex unitary versus orthogonal

A complex unitary RNN can be represented by a real orthogonal RNN with twice the hidden size. This establishes the mathematical basis for focusing on orthogonal transition-matrix parametrisations.

3. Complex unitary versus orthogonal: A unitary transition matrix W in C^n×n has an equivalent orthogonal representation Ŵ in R^2n×2n.The real representation uses a block-matrix structure.
3. Complex unitary versus orthogonal: The complex hidden state and transition matrix are represented using real and imaginary components in a doubled-dimensional real space.The resulting variables satisfy ĥ(t) ∈ R^2n and Ŵ ∈ R^2n×2n.
3. Complex unitary versus orthogonal: When the activation acts separately on real and imaginary parts, the unitary-RNN update has a direct real-space representation.An equivalent real representation remains possible for activations that do not separate these parts.
3. Complex unitary versus orthogonal: The equivalent real-space activation can couple hidden units rather than applying independently to each hidden unit.This follows from the transformed activation construction.
3. Complex unitary versus orthogonal: Unitary conditions on the complex matrix imply that the real block representation is orthogonal, so orthogonal matrices provide the paper’s focus.The paper therefore treats complex unitary transitions as a special orthogonal case.

4. Parametrisation of the transition matrix

The transition matrix is parametrised as a product of Householder-based mappings, providing a smooth and flexible route to orthogonal matrices with efficient gradient computation.

Householder parametrisation: The proposed parametrisation represents the transition matrix using m reflection vectors and products of Householder matrices.The construction uses mappings H_k and vectors u_i ∈ R^i, assembled through the matrix U.
Expressiveness: When m = n, the parametrisation can span the entire set O(n) of n×n orthogonal matrices.Theorem 1 states that O(n) is included in the image of M_1.
Design properties: The parametrisation is smooth apart from a zero-measure subset and allows a speed–expressiveness trade-off through the number of reflection vectors.Increasing the number of reflection vectors improves flexibility while affecting computational cost.
Orthogonality conditions: For m < n, W is always orthogonal for nonzero reflection vectors, while m = n additionally requires u1 ∈ {−1, 1}.The unrestricted m = n case uses the special H1 mapping to retain orthogonality.
Gradient computation: The algorithm derives back-propagated gradients through a compact WY representation and computes local forward and backward propagations.Algorithm 1 computes C(t), ∂L/∂U(t), and ∂L/∂h(t−1) from U and the hidden state.
Complexity: When m ≈ n, global forward and backward propagation require approximately 3n^2T and 5n^2T flops, about twice the sRNN cost.The comparison is for hidden-to-hidden computations with one input sequence of length T and n ≫ 1.
Complexity: Storing Householder matrices across all time steps requires mnT values, compared with nT for storing only hidden states.Local regeneration during back-propagation avoids this storage but has global BP complexity (11n − 3m + 5)mT.

5. Experiments

Across five long-term-dependency tasks, the oRNN was evaluated against simple RNNs, LSTMs, and unitary or orthogonal RNNs. Results show strong performance on sequence generation, addition, MNIST, and character prediction, but weaker copying performance with some activations.

5.1. Sequence generation: The orthogonal parametrisation outperformed the sRNN and performed on average better than the LSTM on sequence generation.
5.2. Addition Task: The oRNN beat the baseline MSE in fewer than 5000 iterations for both addition-task lags and across two random initialisation seeds.
5.3. Pixel MNIST: On MNIST, the best oRNN performed better than three of four compared unitary or orthogonal RNNs despite having fewer parameters.
5.4. Penn Tree Bank: On Penn Tree Bank, oRNN and LSTM performed similarly for one-step prediction, while LSTM performed better for five-step prediction.
5.5. Copying task: On the copy task, oRNN with leaky_ReLU failed to reproduce uRNN performance, while OPLU achieved comparable performance.

6. Discussion

The paper uses Householder reflections to enforce an orthogonal recurrent transition matrix efficiently. This prevents exploding gradients, supports broader orthogonality beyond unitary constraints, and is especially advantageous for near-singleton mini-batches, while further comparison of unitary and orthogonal constraints remains needed.

6. Discussion: Householder reflections provide an easy, computationally efficient parametrisation that enforces orthogonality in the recurrent transition matrix.The same parametrisation can also enforce orthogonality between hidden layers in other deep architectures.
6. Discussion: Orthogonal transition matrices prevent exploding gradients during training, while the parametrisation also permits a soft orthogonal constraint.The paper describes softening the constraint by allowing u1 to vary continuously between -1 and 1.
6. Discussion: The method is particularly advantageous for stochastic gradient descent when the mini-batch size is close to 1.Other orthogonality-enforcing methods have time complexity O(BTn^2+n^3), becoming O(BTn^2) when BT ≫ n.
6. Discussion: Further experiments are needed to clarify the performance difference between unitary and orthogonal constraints.

A. Proofs

The proofs establish that products of Householder matrices can represent orthogonal matrices and connect this construction to QR decomposition. They also provide supporting arguments for the complex-valued corollary and gradient identities.

A. Proofs: QR decomposition constructs an orthogonal factor as a product of Householder matrices, yielding M1(u1, . . . , un) = Hn(un) . . . H1(u1) = ˜Q.The resulting upper-triangular factor has positive diagonal elements.
A. Proofs: Algorithm 2 applies Householder transformations iteratively to obtain Q and an upper-triangular R from a full-rank matrix A.It initializes Q as the identity and updates Q and R through successive transformations.
A. Proofs: The gradient proofs use infinitesimal perturbations, trace identities, and a matrix-differentiation lemma to derive derivatives through the parametrisation.The proof also establishes the complex-valued construction used in the corollary.

B. Algorithm Explanation

The algorithm explanation derives the forward and backward computations for the Householder parametrisation through triangular systems. It links these solves to the recurrent updates and implementation steps.

B. Algorithm Explanation: The implementation relies on matrix expressions involving T, its diagonal structure, the Kronecker delta, and the all-ones matrix.
B. Algorithm Explanation: The forward and backward computations require solving the triangular systems T˜h = U′h and T′˜C = U′∂L/∂C.These systems provide the intermediate quantities needed for the gradient calculations.
B. Algorithm Explanation: The forward solve is expanded row by row, with zero structure in the factors simplifying the resulting expressions.Equations (20) and (21) explain lines 8 and 9 of Algorithm 1.
B. Algorithm Explanation: The computed intermediate quantity yields H∗,1 = C(t) when h = h(t−1), explaining the corresponding recurrent update.The backward derivation similarly identifies expressions that explain lines 12–18 of Algorithm 1.

C. Time complexity

The section reports flop counts for operations in the algorithm’s local backward and forward propagation steps. These counts are summarized in Table 5 under the stated definition of U.

C. Time complexity: Table 5 reports the flop count for different operations in the algorithm’s local backward and forward propagation steps.
C. Time complexity: The reported operation counts concern both local backward propagation and local forward propagation.

D. Matlab implementation of Algorithm 1

The Matlab implementation provides code for one-step forward and backward propagation in the orthogonal RNN algorithm, computing the transition matrix and required gradients.

D. Matlab implementation of Algorithm 1: The Matlab listing initializes reflection-vector and hidden-state arrays before executing the forward-propagation loop.U contains reflection vectors, h is the hidden state at time-step t−1, and BPg is the loss gradient with respect to C=Wh.
D. Matlab implementation of Algorithm 1: The implementation computes C(t), ∂L/∂h(t−1), and ∂L/∂U(t) during one-step forward and backward propagation.The code stores ∂L/∂h(t−1) in g and ∂L/∂U(t) in G.
D. Matlab implementation of Algorithm 1: Forward propagation takes (U, h(t−1)) as inputs, while backward propagation takes (U, C(t), ∂L/∂C(t)).In the Matlab code, ∂L/∂C(t) is represented by BPg.