Backpropagation, an abbreviation for "backward propagation of errors", is a common method
of training artificial neural networks used in conjunction with an optimization method
such as gradient descent.
The method calculates the gradient of a loss function with respects to all the weights
in the network.
The gradient is fed to the optimization method which in turn uses it to update the weights,
in an attempt to minimize the loss function.
Backpropagation requires a known, desired output for each input value in order to calculate
the loss function gradient.
It is therefore usually considered to be a supervised learning method, although it is
also used in some unsupervised networks such as autoencoders.
It is a generalization of the delta rule to multi-layered feedforward networks, made possible
by using the chain rule to iteratively compute gradients for each layer.
Backpropagation requires that the activation function used by the artificial neurons be
differentiable.
Motivation The goal of any supervised learning algorithm
is to find a function that best maps a set of inputs to its correct output.
An example would be a simple classification task, where the input is an image of an animal,
and the correct output would be the name of the animal.
Some input and output patterns can be easily learned by single-layer neural networks.
However, these single-layer perceptrons cannot learn some relatively simple patterns, such
as those that are not linearly separable.
For example, a human may classify an image of an animal by recognizing certain features
such as the number of limbs, the texture of the skin, the size of the animal, and the
list goes on.
A single-layer neural network however, must learn a function that outputs a label solely
using the intensity of the pixels in the image.
There is no way for it to learn any abstract features of the input since it is limited
to having only one layer.
A multi-layered network overcomes this limitation as it can create internal representations
and learn different features in each layer.
The first layer may be responsible for learning the orientations of lines using the inputs
from the individual pixels in the image.
The second layer may combine the features learned in the first layer and learn to identify
simple shapes such as circles.
Each higher layer learns more and more abstract features such as those mentioned above that
can be used to classify the image.
Each layer finds patterns in the layer below it and it is this ability to create internal
representations that are independent of outside input that gives multi-layered networks their
power.
The goal and motivation for developing the backpropagation algorithm was to find a way
to train a multi-layered neural network such that it can learn the appropriate internal
representations to allow it to learn any arbitrary mapping of input to output.
Summary The backpropagation learning algorithm can
be divided into two phases: propagation and weight update.
Phase 1: Propagation Each propagation involves the following steps:
Forward propagation of a training pattern's input through the neural network in order
to generate the propagation's output activations.
Backward propagation of the propagation's output activations through the neural network
using the training pattern target in order to generate the deltas of all output and hidden
neurons.
Phase 2: Weight update For each weight-synapse follow the following
steps: Multiply its output delta and input activation
to get the gradient of the weight.
Subtract a ratio of the gradient from the weight.
This ratio influences the speed and quality of learning; it is called the learning rate.
The greater the ratio, the faster the neuron trains; the lower the ratio, the more accurate
the training is.
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 phase 1 and 2 until the performance of the network is satisfactory.
Algorithm Algorithm for a 3-layer network:
initialize network weights do
forEach training example ex prediction = neural-net-output(network, ex)
forward pass actual = teacher-output(ex)
compute error at the output units compute for all weights from hidden layer
to output layer backward pass compute for all weights from input layer to
hidden layer backward pass continued update network weights input layer not modified
by error estimate until all examples classified correctly or
another stopping criterion satisfied return the network
As the algorithm's name implies, the errors propagate backwards from the output nodes
to the input nodes.
Technically speaking, backpropagation calculates the gradient of the error of the network regarding
the network's modifiable weights.
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.
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.
Intuition Learning as an optimization problem
Before showing the mathematical derivation of the backpropagation algorithm, it helps
to develop some intuitions about the relationship between the actual output of a neuron and
the correct output for a particular training case.
Consider a simple neural network with two input units, one output unit and no hidden
units.
Each neuron uses a linear output that is the weighted sum of its input.
Initially, before training, the weights will be set randomly.
Then the neuron learns from training examples, which in this case consists of a set of tuples
where and are the inputs to the network and is the correct output.
The network given and will compute an output which very likely differs from . A common
method for measuring the discrepancy between the expected output and the actual output
is using the squared error measure: ,
where is the discrepancy or error.
As an example, consider the network on a single training case: , thus the input and are 1
and 1 respectively and the correct output, is 0.
Now if the actual output is plotted on the x-axis against the error on the -axis, the
result is a parabola.
The minimum of the parabola corresponds to the output which minimizes the error . For
a single training case, the minimum also touches the -axis, which means the error will be zero
and the network can produce an output that exactly matches the expected output . Therefore,
the problem of mapping inputs to outputs can be reduced to an optimization problem of finding
a function that will produce the minimal error.
However, the output of a neuron depends on the weighted sum of all its inputs:
, where and are the weights on the connection
from the input units to the output unit.
Therefore, the error also depends on the incoming weights to the neuron, which is ultimately
what needs to be changed in the network to enable learning.
If each weight is plotted on a separate horizontal axis and the error on the vertical axis, the
result is a parabolic bowl.
The backpropagation algorithm aims to find the set of weights that minimizes the error.
There are several methods for finding the minima of a parabola or any function in any
dimension.
One way is analytically by solving systems of equations, however this relies on the network
being a linear system, and the goal is to be able to also train multi-layer, non-linear
networks.
The method used in backpropagation is gradient descent.
An analogy for understanding gradient descent
The basic intuition behind gradient descent can be illustrated by a hypothetical scenario.
A person is stuck in the mountains is trying to get down.
There is heavy fog such that visibility is extremely low.
Therefore, the path down the mountain is not visible, so he must use local information
to find the minima.
He can use the method of gradient descent, which involves looking at the steepness of
the hill at his current position, then proceeding in the direction with the most negative steepness.
If he was trying to find the top of the mountain, then he would proceed in the direction with
most positive steepness.
Using this method, he would eventually find his way down the mountain.
However, assume also that the steepness of the hill is not immediately obvious with simple
observation, but rather it requires a sophisticated instrument to measure, which the person happens
to have at the moment.
It takes quite some time to measure the steepness of the hill with the instrument, thus he should
minimize his use of the instrument if he wanted to get down the mountain before sunset.
The difficulty then is choosing the frequency at which he should measure the steepness of
the hill so not to go off track.
In this analogy, the person represents the backpropagation algorithm, and the path down
the mountain represents the set of weights that will minimize the error.
The steepness of the hill represents the slope of the error surface at that point.
The direction he must travel in corresponds to the gradient of the error surface at that
point.
The instrument used to measure steepness is differentiation.
The distance he travels in between measurements is the learning rate of the algorithm.
See the limitation section for a discussion of the limitations of this type of "hill climbing"
algorithm.
Derivation Since backpropagation uses the gradient descent
method, one needs to calculate the derivative of the squared error function with respect
to the weights of the network.
Assuming one output neuron, the squared error function is:
, where
is the squared error, is the target output for a training sample,
and is the actual output of the output neuron.
The factor of is included to cancel the exponent when differentiating.
Later, the expression will be multiplied with an arbitrary learning rate, so that it doesn't
matter if a constant coefficient is introduced now.
For each neuron , its output is defined as .
The input to a neuron is the weighted sum of outputs of previous neurons.
If the neuron is in the first layer after the input layer, the of the input layer are
simply the inputs to the network.
The number of input units to the neuron is . The variable denotes the weight between
neurons and . The activation function is in general non-linear
and differentiable.
A commonly used activation function is the logistic function:
which has a nice derivative of:
Finding the derivative of the error Calculating the partial derivative of the
error with respect to a weight is done using the chain rule:
In the last term of the right-hand side, only one term in the sum depends on , so that
. The derivative of the output of neuron with
respect to its input is simply the partial derivative of the activation function:
This is the reason why backpropagation requires the activation function to be differentiable.
The first term is straightforward to evaluate if the neuron is in the output layer, because
then and
However, if is in an arbitrary inner layer of the network, finding the derivative with
respect to is less obvious.
Considering as a function of the inputs of all neurons receiving input from neuron ,
and taking the total derivative with respect to , a recursive expression for the derivative
is obtained:
Therefore, the derivative with respect to can be calculated if all the derivatives with
respect to the outputs of the next layer – the one closer to the output neuron – are known.
Putting it all together:
with
To update the weight using gradient descent, one must choose a learning rate, . The change
in weight, which is added to the old weight, is equal to the product of the learning rate
and the gradient, multiplied by :
The is required in order to update in the direction of a minimum, not a maximum, of
the error function.
For a single-layer network, this expression becomes the Delta Rule.
To better understand how backpropagation works, here is an example to illustrate it: The Back
Propagation Algorithm, page 20.
Modes of learning There are three modes of learning to choose
from: on-line, batch and stochastic.
In on-line and stochastic learning, each propagation is followed immediately by a weight update.
In batch learning, many propagations occur before updating the weights.
On-line learning is used for dynamic environments that provide a continuous stream of new patterns.
Stochastic learning and batch learning both make use of a training set of static patterns.
Stochastic goes through the data set in a random order in order to reduce its chances
of getting stuck in local minima.
Stochastic learning is also much faster than batch learning since weights are updated immediately
after each propagation.
Yet batch learning will yield a much more stable descent to a local minimum since each
update is performed based on all patterns.
Limitations The result may converge to a local minimum.
The "hill climbing" strategy of gradient descent is guaranteed to work if there is only one
minimum.
However, often the error surface has many local minima and maxima.
If the starting point of the gradient descent happens to be somewhere between a local maximum
and local minimum, then going down the direction with the most negative gradient will lead
to the local minimum.
The convergence obtained from backpropagation learning is very slow.
The convergence in backpropagation learning is not guaranteed.
Backpropagation learning does not require normalization of input vectors; however, normalization
could improve performance.
History
Vapnik cites 2544-2550) as the first publication of the backpropagation algorithm in his book
"Support Vector Machines.".
Arthur E. Bryson and Yu-Chi Ho described it as a multi-stage dynamic system optimization
method in 1969.
It wasn't until 1974 and later, when applied in the context of neural networks and through
the work of Paul Werbos, David E. Rumelhart, Geoffrey E. Hinton and Ronald J. Williams,
that it gained recognition, and it led to a “renaissance” in the field of artificial
neural network research.
During the 2000s it fell out of favour but has returned again in the 2010s, now able
to train much larger networks using huge modern computing power such as GPUs.
For example, in 2013 top speech recognisers now use backpropagation-trained neural networks.
Notes
See also Artificial neural network
Biological neural network Catastrophic interference
Ensemble learning AdaBoost
Overfitting References
External links A Gentle Introduction to Backpropagation - An
intuitive tutorial by Shashi Sathyanarayana The article contains pseudocode for implementing
the algorithm.
Neural Network Back-Propagation for Programmers Backpropagation for mathematicians
Chapter 7 The backpropagation algorithm of Neural Networks - A Systematic Introduction
by Raúl Rojas Implementation of BackPropagation in C++
Implementation of BackPropagation in C# Implementation of BackPropagation in Java
Another 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 by Anand Venkataraman
Backpropagation neural network tutorial at the Wikiversity