Papperoni

1992

Gradient-Based Learning Algorithms for Recurrent Networks and Their Computational Complexity

Ronald J. Williams, David Zipser

Open PDF Google Scholar

citations

Cite Score

36

AI summary

This paper presents a comprehensive analysis of gradient-based learning algorithms for recurrent neural networks, categorizing them by exactness and operational mode, and provides detailed computational complexity analyses for various architectures and tasks, including the impact of teacher forcing.

Main Contributions

Categorization and analysis of gradient-based learning algorithms for recurrent networks based on exactness and operational mode (continual vs. epochwise).
Detailed computational complexity analysis (space and time) for various algorithms, including Backpropagation Through Time (BPTT), Real-Time Recurrent Learning (RTRL), and a hybrid FP/BPTT algorithm.
Introduction and analysis of approximation strategies like Truncated BPTT and Subgrouping in RTRL to reduce computational requirements.
Discussion of teacher forcing as a technique to stabilize learning and its implications for optimizing different error measures in continually operating networks.
Exploration of architecture-specific approaches, particularly two-stage architectures with hidden-to-hidden, output-to-hidden, and output-to-output feedback only.

Abstract

In this chapter we describe and analyze several gradient-based algorithms for supervised learning in recurrent networks, focusing on discrete-time, feedforward networks having connections that generally include a delay of one time step. We categorize algorithms based on whether they compute the exact gradient or an approximation, and whether they are suitable for continually operating networks or only for epochwise tasks. We analyze the computational complexity of these algorithms in terms of both space and time requirements for general cases and worst-case scenarios. Specific architectures with simplified delay structures and the role of 'teacher forcing' in learning dynamics are also discussed.

Citation Graph

Loading graph...

References [44]

Sort:

Filter:

[1]Learning Internal Representations by Error Propagation

D. E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams - 1986

46 papers in library cite

I expected very little of this, but was so good in explaining concepts! Very good read. It gets a bit boring when it starts explaining things by the end of the chapter, but good nonetheless.

[2]Generalization of Back-Propagation to Recurrent Neural Networks

Fernando J. Pineda - 1987

5 papers in library cite

Too abstract and mathy. Exactly the kind of paper I don't like. It would be waaaay better if it had some images or some concrete concepts to ground this. Also, I was out of patience for this type of stuff when I read this.

[3]Generalization of Backpropagation With Application to a Recurrent Gas Market Model

Paul J. Werbos - 1988

11 papers in library cite

The first two sections are amazing. Very nice concepts, well explained. From section 3 on it gets more abstract and too formalized, and it's mostly for Hopfield recurrent nets (so not very relevant now). Section 4 is just the application to the gas market, which I don't care for at all.

[4]A Learning algorithm for Continually Running Fully Recurrent Neural Networks

R. Williams, David Zipser - 1989

8 papers in library cite

Quick read and very simple concept. I wish they explained things using a more visual approach instead of maths, but it's ok to follow nonetheless.

[5]Learning Phonetic Features Using Connectionist Networks: An Experiment in Speech Recognition

R. Watrous, Lokendra Shastri - 1987

4 papers in library cite

Really nothing interesting to see here. Maybe the only merit is early usage of backprop.

[6]Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences

P. Werbos - 1974

14 papers in library cite

Werbos PhD Thesis, introduced backprop

[7]Complexity of Exact Gradient Computation Algorithms for Recurrent Neural Networks

Ronald J. Williams - 1989

6 papers in library cite

[8]A Learning Rule for Asynchronous Perceptrons With Feedback in a Combinatorial Environment

L. B. Almeida - 1987

5 papers in library cite

[9]An Efficient Gradient-Based Algorithm for on-Line Training of Recurrent Network Trajectories

Ronald J. Williams, J. Peng - 1990

5 papers in library cite

[10]Learning State Space Trajectories in Recurrent Neural Networks

B. A. Pearlmutter - 1989

5 papers in library cite

[11]A Fixed Size Storage O(n³) Time Complexity Learning algorithm for Fully Recurrent Continually Running Networks

Jürgen Schmidhuber - 1992

4 papers in library cite

[12]Adaptive Signal Processing

B. Widrow, S. D. Stearns - 1985

4 papers in library cite

[13]Applied Optimal Control

J. A. E. Bryson, Y. C. Ho - 1969

4 papers in library cite

[14]Dynamics and Architecture for Neural Computation

Fernando J. Pineda - 1988

4 papers in library cite

[15]Finite-State Automata and Simple Recurrent Networks

A. Cleeremans, D. S. Schreiber, J. L. Mcclelland - 1989

4 papers in library cite

[16]Learning Sequential Structures With the Real-Time Recurrent Learning Algorithm

A. W. Smith, David Zipser - 1989

4 papers in library cite

[17]A First Look at Phonetic Discrimination Using a Connectionist Architecture With Recurrent Links

G. Kuhn - 1987

3 papers in library cite

[18]A Focused Back-Propagation Algorithm for Temporal Pattern Recognition

M. C. Mozer - 1989

3 papers in library cite

[19]Adaptive Neural Oscillator Using Continuous-Time Back-Propagation Learning

K. Doya, S. Yoshizawa - 1989

3 papers in library cite

[20]At Tractor Dynamics and Parallelism in a Connectionist Sequential Machine

Michael I. Jordan - 1986

3 papers in library cite

[21]Adaptive State Representation and Estimation Using Recurrent Connectionist Networks

R. Williams - 1990

2 papers in library cite

[22]Learning to Represent State

J. Bachrach - 1988

2 papers in library cite

[23]Optimization of Time-Varying Systems

L. E. J. Mcbride, K. S. Narendra - 1965

2 papers in library cite

[24]The 'Moving Targets' Training algorithm

R. Rohwer - 1990

2 papers in library cite

[25]A Bifurcation Theory Approach to Vector Field Programming for Periodic Attractors

B. Baird - 1989

1 paper in library cites

[26]A Learning algorithm for Analog, Fully Recurrent Neural Networks

M. Gherrity - 1989

1 paper in library cites

[27]A Learning algorithm to Teach Spatiotemporal Patterns to Recurrent Neural Networks

M. Sato - 1990

1 paper in library cites

[28]A Learning Neural-Network Model of the Oculomotor Integrator

D. Arnold, D. A. Robinson - 1989

1 paper in library cites

[29]A Real Time Learning algorithm for Recurrent Analog Neural Networks

M. Sato - 1990

1 paper in library cites

[30]A Subgrouping Strategy That Reduces Complexity and Speeds Up Learning in Recurrent Networks

David Zipser - 1989

1 paper in library cites

[31]A Theoretical Framework for Back-Propagation (Technical Report CRG-TR-88-6)

Yann Lecun - 1988

1 paper in library cites

[32]Experimental Analysis of the Real-Time Recurrent Learning Algorithm

Ronald J. Williams, David Zipser - 1989

1 paper in library cites

[33]Finding Structure in Time (CRL Technical Report 8801)

Jeffrey L. Elman - 1988

1 paper in library cites

[34]Identification and Control of Dynamic Systems Using Neural Networks

K. S. Narendra, K. Parthasarathy - 1990

1 paper in library cites

[35]Learning in Recurrent Finite Difference Networks

F. S. Tsung - 1990

1 paper in library cites

[36]Neural Network Analysis of Distributed Representations of Dynamical Sensory-Motor Transformations in the Leech

S. Lockery, Y. Fang, T. Sejnowski - 1990

1 paper in library cites

[37]Neural Network Models of Velocity Storage in the Horizontal Vestibulo-Ocular Reflex

T. J. Anastasio - 1991

1 paper in library cites

[38]Phoneme Recognition Using Time-Delay Neural Networks (Technical Report TR-I-0006)

A. Waibel, T. Hanazawa, Geoffrey Hinton, K. Shikano, K. Lang - 1987

1 paper in library cites

[39]Recurrent Backpropagation and the Dynamical Approach to Adaptive Neural Computation

Fernando J. Pineda - 1989

1 paper in library cites

[40]Some Experiments on Learning Stable Network Oscillations

F. S. Tsung, G. W. Cottrell, A. Selverston - 1990

1 paper in library cites

[41]Stable Adaptive Systems

K. S. Narendra, A. M. Annaswamy - 1989

1 paper in library cites

[42]Steepest Descent Algorithms for Neural Network Controllers and Filters

S. W. Piche - 1994

1 paper in library cites

[43]The Utility Driven Dynamic Error Propagation Network (Technical Report CUED/F-INFENG/TR.1)

A. J. Robinson, F. Fallside - 1987

1 paper in library cites

[44]Training Recurrent Networks

R. Rohwer, S. Renals - 1989

1 paper in library cites

Cited by

8

papers in your library

Cites

6

papers in your library

Read

on February 8, 2026

Oof, this was a hard read. I had to force myself to finish. I think this is too theoretical and deals with RNNs that are not really used nowadays. I skimmed through the second half.

Tags

Paper Aliases

No aliases