Backpropagation

Backpropagation is a common method of teaching artificial neural networks how to perform a given task. Arthur E. Bryson and Yu-Chi Ho described it as a multi-stage dynamic system optimization method in 1969.^[1][2] It wasn't until 1974 and later, when applied in the context of neural networks and through the work of Paul Werbos,^[3] David E. Rumelhart, Geoffrey E. Hinton and Ronald J. Williams,^[4][5] that it gained recognition, and it led to a “renaissance” in the field of artificial neural network research.

It is a supervised learning method, and is a generalization of the delta rule. It requires a teacher that knows, or can calculate, the desired output for any input in the training set. It is most useful for feed-forward networks (networks that have no feedback, or simply, that have no connections that loop). The term is an abbreviation for "backward propagation of errors". Backpropagation requires that the activation function used by the artificial neurons (or "nodes") be differentiable.

Contents 1 Summary 1.1 Phase 1: Propagation 1.2 Phase 2: Weight update 2 Modes of learning 3 Algorithm 4 Multithreaded backpropagation 5 Limitations 6 References 7 External links

Summary

For better understanding, the backpropagation learning algorithm can be divided into two phases: propagation and weight update.

Phase 1: Propagation

Each propagation involves the following steps:

1. Forward propagation of a training pattern's input through the neural network in order to generate the propagation's output activations.
2. Backward propagation of the propagation's output activations through the neural network using the training pattern's target in order to generate the deltas of all output and hidden neurons.

Phase 2: Weight update

For each weight-synapse:

1. Multiply its output delta and input activation to get the gradient of the weight.
2. Bring the weight in the opposite direction of the gradient by subtracting a ratio of it from the weight.

This ratio influences the speed and quality of learning; it is called the learning rate. The sign of the gradient of a weight indicates where the error is increasing, this is why the weight must be updated in the opposite direction.

Repeat the phase 1 and 2 until the performance of the network is good enough.

Modes of learning

There are two modes of learning to choose from: One is on-line learning and the other is batch learning. In on-line learning, each propagation is followed immediately by a weight update. In batch learning, many propagations occur before weight updating occurs. Batch learning requires more memory capacity, but on-line learning requires more updates.

Algorithm

Actual algorithm for a 3-layer network (only one hidden layer):

  Initialize the weights in the network (often randomly)
  Do
         For each example e in the training set
              O = neural-net-output(network, e) ; forward pass
              T = teacher output for e
              Calculate error (T - O) at the output units
              Compute delta_wh for all weights from hidden layer to output layer ; backward pass
              Compute delta_wi for all weights from input layer to hidden layer ; backward pass continued
              Update the weights in the network
  Until all examples classified correctly or stopping criterion satisfied
  Return the network

As the algorithm's name implies, the errors propagate backwards from the output nodes to the inner nodes. Technically speaking, backpropagation calculates the gradient of the error of the network regarding the network's modifiable weights.^[6] This gradient is almost always used in a simple stochastic gradient descent algorithm to find weights that minimize the error. Often the term "backpropagation" is used in a more general sense, to refer to the entire procedure encompassing both the calculation of the gradient and its use in stochastic gradient descent. Backpropagation usually allows quick convergence on satisfactory local minima for error in the kind of networks to which it is suited.

Backpropagation networks are necessarily multilayer perceptrons (usually with one input, one hidden, and one output layer). In order for the hidden layer to serve any useful function, multilayer networks must have non-linear activation functions for the multiple layers: a multilayer network using only linear activation functions is equivalent to some single layer, linear network. Non-linear activation functions that are commonly used include the logistic function, the softmax function, and the gaussian function.

The backpropagation algorithm for calculating a gradient has been rediscovered a number of times, and is a special case of a more general technique called automatic differentiation in the reverse accumulation mode.

It is also closely related to the Gauss–Newton algorithm, and is also part of continuing research in neural backpropagation.

Multithreaded backpropagation

Backpropagation is an iterative process that can often take a great deal of time to complete. When multicore computers are used multithreaded techniques can greatly decrease the amount of time that backpropagation takes to converge. If batching is being used, it is relatively simple to adapt the backpropagation algorithm to operate in a multithreaded manner.

The training data is broken up into equally large batches for each of the threads. Each thread executes the forward and backward propagations. The weight and threshold deltas are summed for each of the threads. At the end of each iteration all threads must pause briefly for the weight and threshold deltas to be summed and applied to the neural network. This process continues for each iteration. This multithreaded approach to backpropagation is used by the Encog Neural Network Framework.^[7]

Limitations

• The convergence obtained from backpropagation learning is very slow.
• The convergence in backpropagation learning is not guaranteed.
• The result may generally converge to any local minimum on the error surface, since stochastic gradient descent exists on a surface which is not flat.
• Backpropagation learning requires input scaling or normalization. Inputs are usually scaled into the range of +0.1f to +0.9f for best performance.

References

1. ^ Stuart Russell and Peter Norvig. Artificial Intelligence A Modern Approach. p. 578. "The most popular method for learning in multilayer networks is called Back-propagation. It was first invented in 1969 by Bryson and Ho, but was largely ignored until the mid-1980s." 
2. ^ Arthur Earl Bryson, Yu-Chi Ho (1969). Applied optimal control: optimization, estimation, and control. Blaisdell Publishing Company or Xerox College Publishing. pp. 481. 
3. ^ Paul J. Werbos. Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences. PhD thesis, Harvard University, 1974
4. ^ Alpaydın, Ethem (2010). Introduction to machine learning (2nd ed. ed.). Cambridge, Mass.: MIT Press. p. 250. ISBN 978-0-262-01243-0. "...and hence the name backpropagation was coined (Rumelhart, Hinton, and Williams 1986a)." 
5. ^ Rumelhart, David E.; Hinton, Geoffrey E., Williams, Ronald J. (8 October 1986). "Learning representations by back-propagating errors". Nature 323 (6088): 533–536. doi:10.1038/323533a0. 
6. ^ Paul J. Werbos (1994). The Roots of Backpropagation. From Ordered Derivatives to Neural Networks and Political Forecasting. New York, NY: John Wiley & Sons, Inc.
7. ^ J. Heaton http://www.heatonresearch.com/encog/mprop/compare.html Applying Multithreading to Resilient Propagation and Backpropagation

External links

• Backpropagation for mathematicians
• Chapter 7 The backpropagation algorithm of Neural Networks - A Systematic Introduction by Raúl Rojas (ISBN 978-3540605058)
• NeuronDotNet - A modular implementation of artificial neural networks in C# along with sample applications
• Implementation of BackPropagation in C++
• Implementation of BackPropagation in C#
• Implementation of BackPropagation in Java
• Implementation of BackPropagation in Ruby
• Implementation of BackPropagation in Python
• Implementation of BackPropagation in PHP
• Quick explanation of the backpropagation algorithm
• Graphical explanation of the backpropagation algorithm
• Concise explanation of the backpropagation algorithm using math notation
• Backpropagation neural network tutorial at the Wikiversity