Backpropagation

This article is about the computer algorithm. For the biological process, see Neural backpropagation.

Backpropagation can also refer to the way the result of a playout is propagated up the search tree in Monte Carlo tree search

Machine learning and data mining

Problems Classification Clustering Regression Anomaly detection Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles (Bagging, Boosting, Random forest) k-NN Linear regression Naive Bayes Neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH Hierarchical k-means Expectation-maximization (EM) DBSCAN OPTICS Mean-shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA t-SNE
Structured prediction Graphical models (Bayes net, CRF, HMM)
Anomaly detection k-NN Local outlier factor
Neural nets Autoencoder Deep learning Multilayer perceptron RNN Restricted Boltzmann machine SOM Convolutional neural network
Reinforcement Learning Q-Learning SARSA Temporal Difference (TD)
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine learning venues NIPS ICML IJMLC ML JMLR ArXiv:cs.LG
Machine learning portal

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. It calculates the gradient of a loss function with respect to all the weights in the network, so that 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; nonetheless, 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 (or "nodes") 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 classification task, where the input is an image of an animal, and the correct output would be the name of the animal.

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.^[1]

The algorithm

Let $N$ be a neural network with $e$ connections.

Below, $x,x_{1},x_{2},\dots$ will denote vectors in $\mathbb {R} ^{m}$ , $y,y',y_{1},y_{2},\dots$ vectors in $\mathbb {R} ^{n}$ , and $w,w_{0},w_{1},\ldots$ vectors in $\mathbb {R} ^{e}$ . These are called inputs, outputs and weights respectively. The neural network corresponds to a function $y=f_{N}(w,x)$ which, given a weight $w$ , maps an input $x$ to an output $y$ . (See neural network for details.)

We select an error function $E(y,y')$ measuring the difference between two outputs. The standard choice is $E(y,y')={\tfrac {1}{2}}|y-y'|^{2}$ , the square of the Euclidean distance between the vectors $y$ and $y'$ . The factor of ${\tfrac {1}{2}}$ conveniently cancels the exponent when the error function is subsequently differentiated.

The backpropagation algorithm takes as input a sequence of training examples $(x_{1},y_{1}),\dots ,(x_{p},y_{p})$ and produces a sequence of weights $w_{0},w_{1},\dots ,w_{p}$ starting from some initial weight $w_{0}$ , usually chosen at random. These weights are computed in turn: we compute $w_{i}$ using only $(x_{i},y_{i},w_{i-1})$ for $i=1,\dots ,p$ . The output of the backpropagation algorithm is then $w_p$ , giving us a new function $x\mapsto f_{N}(w_{p},x)$ . The computation is the same in each step, so we describe only the case $i=1$ .

Now we describe how to find $w_{1}$ from $(x_{1},y_{1},w_{0})$ . This is done by considering a variable weight $w$ and applying gradient descent to the function $w\mapsto E(f_{N}(w,x_{1}),y_{1})$ to find a local minimum, starting at $w=w_{0}$ . We then let $w_{1}$ be the minimizing weight found by gradient descent.

The algorithm in code

When we want to code the algorithm above in a computer, we need explicit formulas for the gradient of the function $w\mapsto E(f_{N}(w,x),y)$ from above. We do that in this section, for the special choice $E(y,y')=|y-y'|^{2}$ .

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 (the difference between the targeted and actual output values) 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 (percentage) from the gradient of the weight.

This ratio (percentage) influences the speed and quality of learning; it is called the learning rate. The greater the ratio, the faster the neuron trains, but 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.

Code

The following is a stochastic gradient descent algorithm for training a three-layer network (only one hidden layer):

  initialize network weights (often small random values)
  do
     forEach training example named ex
        prediction = neural-net-output(network, ex)  // forward pass
        actual = teacher-output(ex)
        compute error (prediction - actual) at the output units
        compute  $\Delta w_h$  for all weights from hidden layer to output layer  // backward pass
        compute  $\Delta w_i$  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

The lines labeled "backward pass" can be implemented using the backpropagation algorithm, which calculates the gradient of the error of the network regarding the network's modifiable weights.^[2] 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, but backpropagation properties can be used with any gradient-based optimizer, such as L-BFGS or truncated Newton.

Backpropagation networks are necessarily multilayer perceptrons (usually with one input, multiple 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 rectifier, 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^{[note 1]} that is the weighted sum of its input.

A simple neural network with two input units and one output unit

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 ( $x_{1}$ , $x_{2}$ , $t$ ) where $x_{1}$ and $x_{2}$ are the inputs to the network and $t$ is the correct output (the output the network should eventually produce given the identical inputs). The network given $x_{1}$ and $x_{2}$ will compute an output $y$ which very likely differs from $t$ (since the weights are initially random). A common method for measuring the discrepancy between the expected output $t$ and the actual output $y$ is using the squared error measure:

E=(t-y)^2 \,

where $E$ is the discrepancy or error.

As an example, consider the network on a single training case: $(1, 1, 0)$ , thus the input $x_{1}$ and $x_{2}$ are 1 and 1 respectively and the correct output, $t$ is 0. Now if the actual output $y$ is plotted on the x-axis against the error $E$ on the $y$ -axis, the result is a parabola. The minimum of the parabola corresponds to the output $y$ which minimizes the error $E$ . For a single training case, the minimum also touches the $x$ -axis, which means the error will be zero and the network can produce an output $y$ that exactly matches the expected output $t$ . 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.

Error surface of a linear neuron for a single training case.

However, the output of a neuron depends on the weighted sum of all its inputs:

y=x_1w_1 + x_2w_2

where $w_{1}$ and $w_{2}$ 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 (If a neuron has $k$ weights, then the dimension of the error surface would be $k+1$ , thus a $k+1$ dimensional equivalent of the 2D parabola).

Error surface of a linear neuron with two input weights

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 (since a multi-layered linear network is equivalent to a single-layer network). The method used in backpropagation is gradient descent.

An analogy for understanding gradient descent

Further information: Gradient descent

The basic intuition behind gradient descent can be illustrated by a hypothetical scenario. A person is stuck in the mountains and is trying to get down (i.e. trying to find the minima). 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 steepest descent (i.e. downhill). If he was trying to find the top of the mountain (i.e. the maxima), then he would proceed in the direction steepest ascent (i.e. uphill). 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 taken down the mountain represents the sequence of parameter settings that the algorithm will explore. The steepness of the hill represents the slope of the error surface at that point. The instrument used to measure steepness is differentiation (the slope of the error surface can be calculated by taking the derivative of the squared error function at that point). The direction he chooses to travel in aligns with the gradient of the error surface at that point. The amount of time he travels before taking another measurement 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,^{[note 2]} the squared error function is:

E = \tfrac{1}{2}(t - y)^2

where

E

is the squared error,

t

is the target output for a training sample, and

y

is the actual output of the output neuron.

The factor of $\textstyle {\frac {1}{2}}$ 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 $j$ , its output $o_{j}$ is defined as

o_{j} = \varphi(\mbox{net}_{j}) = \varphi\left(\sum_{k=1}^{n}w_{kj}o_k\right)

The input $\mbox{net}_{j}$ to a neuron is the weighted sum of outputs $o_k$ of previous neurons. If the neuron is in the first layer after the input layer, the $o_k$ of the input layer are simply the inputs $x_{k}$ to the network. The number of input units to the neuron is $n$ . The variable $w_{ij}$ denotes the weight between neurons $i$ and $j$ .

The activation function $\varphi$ is in general non-linear and differentiable. A commonly used activation function is the logistic function:

\varphi(z) = \frac{1}{1+e^{-z}}

which has a nice derivative of:

{\frac {d\varphi }{dz}}(z)=\varphi (z)(1-\varphi (z))

Finding the derivative of the error

Calculating the partial derivative of the error with respect to a weight $w_{ij}$ is done using the chain rule twice:

\frac{\partial E}{\partial w_{ij}} = \frac{\partial E}{\partial o_j} \frac{\partial o_j}{\partial\mathrm{net_j}} \frac{\partial \mathrm{net_j}}{\partial w_{ij}}

In the last factor of the right-hand side of the above, only one term in the sum $\mathrm{net_j}$ depends on $w_{ij}$ , so that

\frac{\partial \mathrm{net_j}}{\partial w_{ij}} = \frac{\partial}{\partial w_{ij}}\left(\sum_{k=1}^{n}w_{kj}o_k\right) = o_i

If the neuron is in the first layer after the input layer, $o_i$ is just $x_{i}$ .

The derivative of the output of neuron $j$ with respect to its input is simply the partial derivative of the activation function (assuming here that the logistic function is used):

\frac{\partial o_j}{\partial\mathrm{net_j}} = \frac {\partial}{\partial \mathrm{net_j}}\varphi(\mathrm{net_j}) = \varphi(\mathrm{net_j})(1-\varphi(\mathrm{net_j}))

This is the reason why backpropagation requires the activation function to be differentiable.

The first factor is straightforward to evaluate if the neuron is in the output layer, because then $o_j = y$ and

\frac{\partial E}{\partial o_j} = \frac{\partial E}{\partial y} = \frac{\partial}{\partial y} \frac{1}{2}(t - y)^2 = y - t

However, if $j$ is in an arbitrary inner layer of the network, finding the derivative $E$ with respect to $o_j$ is less obvious.

Considering $E$ as a function of the inputs of all neurons $L = {u, v, \dots, w}$ receiving input from neuron $j$ ,

\frac{\partial E(o_j)}{\partial o_j} = \frac{\partial E(\mathrm{net}_u, \mathrm{net}_v, \dots, \mathrm{net}_w)}{\partial o_j}

and taking the total derivative with respect to $o_j$ , a recursive expression for the derivative is obtained:

\frac{\partial E}{\partial o_j} = \sum_{l \in L} \left(\frac{\partial E}{\partial \mathrm{net}_l}\frac{\partial \mathrm{net}_l}{\partial o_j}\right) = \sum_{l \in L} \left(\frac{\partial E}{\partial o_{l}}\frac{\partial o_{l}}{\partial \mathrm{net}_l}w_{jl}\right)

Therefore, the derivative with respect to $o_j$ can be calculated if all the derivatives with respect to the outputs $o_l$ of the next layer – the one closer to the output neuron – are known.

Putting it all together:

\dfrac{\partial E}{\partial w_{ij}} = \delta_{j} o_{i}

with

\delta _{j}={\frac {\partial E}{\partial o_{j}}}{\frac {\partial o_{j}}{\partial \mathrm {net_{j}} }}={\begin{cases}(o_{j}-t_{j})o_{j}(1-o_{j})&{\mbox{if }}j{\mbox{ is an output neuron,}}\\(\sum _{l\in L}\delta _{l}w_{jl})o_{j}(1-o_{j})&{\mbox{if }}j{\mbox{ is an inner neuron.}}\end{cases}}

To update the weight $w_{ij}$ using gradient descent, one must choose a learning rate, $\alpha$ . 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 $-1$ :

\Delta w_{ij}=-\alpha {\frac {\partial E}{\partial w_{ij}}}={\begin{cases}-\alpha o_{i}(o_{j}-t_{j})o_{j}(1-o_{j})&{\mbox{if }}j{\mbox{ is an output neuron,}}\\-\alpha o_{i}(\sum _{l\in L}\delta _{l}w_{jl})o_{j}(1-o_{j})&{\mbox{if }}j{\mbox{ is an inner neuron.}}\end{cases}}

The $\textstyle -1$ 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 two modes of learning to choose from: stochastic and batch. In stochastic learning, each propagation is followed immediately by a weight update. In batch learning many propagations occur before updating the weights, accumulating errors over the samples within a batch. Stochastic learning introduces "noise" into the gradient descent process, using the local gradient calculated from one data point; this reduces the chance of the network getting stuck in a local minima. Yet batch learning typically yields a faster, more stable descent to a local minima, since each update is performed in the direction of the average error of the batch samples. In modern applications a common compromise choice is to use "mini-batches", meaning batch learning but with a batch of small size and with stochastically selected samples.

Training data collection

Online learning is used for dynamic environments that provide a continuous stream of new training data patterns. Offline learning makes use of a training set of static patterns.

Limitations

Gradient descent can find the local minimum instead of the global minimum

Gradient descent with backpropagation is not guaranteed to find the global minimum of the error function, but only a local minimum; also, it has trouble crossing plateaux in the error function landscape. This issue, caused by the non-convexity of error functions in neural networks, was long thought to be a major drawback, but in a 2015 review article, Yann LeCun et al. argue that in many practical problems, it is not.^[3]
Backpropagation learning does not require normalization of input vectors; however, normalization could improve performance.^[4]

History

Notes

↑ One may notice that multi-layer neural networks use non-linear activation functions, so an example with linear neurons seems obscure. However, even though the error surface of multi-layer networks are much more complicated, locally they can be approximated by a paraboloid. Therefore, linear neurons are used for simplicity and easier understanding.
↑ There can be multiple output neurons, in which case the error is the squared norm of the difference vector.

References

1 2 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.
↑ Paul J. Werbos (1994). The Roots of Backpropagation. From Ordered Derivatives to Neural Networks and Political Forecasting. New York, NY: John Wiley & Sons, Inc.
↑ LeCun, Yann; Bengio, Yoshua; Hinton, Geoffrey (2015). "Deep learning". Nature. 521: 436–444. doi:10.1038/nature14539.
↑ ISBN 1-931841-08-X,
↑ Stuart Dreyfus (1990). Artificial Neural Networks, Back Propagation and the Kelley-Bryson Gradient Procedure. J. Guidance, Control and Dynamics, 1990.
↑ Eiji Mizutani, Stuart Dreyfus, Kenichi Nishio (2000). On derivation of MLP backpropagation from the Kelley-Bryson optimal-control gradient formula and its application. Proceedings of the IEEE International Joint Conference on Neural Networks (IJCNN 2000), Como Italy, July 2000. Online
1 2 3 Jürgen Schmidhuber (2015). Deep learning in neural networks: An overview. Neural Networks 61 (2015): 85-117. ArXiv
1 2 3 Jürgen Schmidhuber (2015). Deep Learning. Scholarpedia, 10(11):32832. Section on Backpropagation
↑ Henry J. Kelley (1960). Gradient theory of optimal flight paths. Ars Journal, 30(10), 947-954. Online
↑ Arthur E. Bryson (1961, April). A gradient method for optimizing multi-stage allocation processes. In Proceedings of the Harvard Univ. Symposium on digital computers and their applications.
↑ Stuart Dreyfus (1962). The numerical solution of variational problems. Journal of Mathematical Analysis and Applications, 5(1), 30-45. Online
↑ Bryson, A.E.; W.F. Denham; S.E. Dreyfus. Optimal programming problems with inequality constraints. I: Necessary conditions for extremal solutions. AIAA J. 1, 11 (1963) 2544-2550
↑ Stuart Russell; Peter Norvig. Artificial Intelligence A Modern Approach. p. 578. The most popular method for learning in multilayer networks is called Back-propagation.
↑ Arthur Earl Bryson; Yu-Chi Ho (1969). Applied optimal control: optimization, estimation, and control. Blaisdell Publishing Company or Xerox College Publishing. p. 481.
↑ Seppo Linnainmaa (1970). The representation of the cumulative rounding error of an algorithm as a Taylor expansion of the local rounding errors. Master's Thesis (in Finnish), Univ. Helsinki, 6-7.
↑ Seppo Linnainmaa (1976). Taylor expansion of the accumulated rounding error. BIT Numerical Mathematics, 16(2), 146-160.
↑ Griewank, Andreas (2012). Who Invented the Reverse Mode of Differentiation?. Optimization Stories, Documenta Matematica, Extra Volume ISMP (2012), 389-400.
↑ Griewank, Andreas and Walther, A.. Principles and Techniques of Algorithmic Differentiation, Second Edition. SIAM, 2008.
↑ Stuart Dreyfus (1973). The computational solution of optimal control problems with time lag. IEEE Transactions on Automatic Control, 18(4):383–385.
↑ Paul Werbos (1974). Beyond regression: New tools for prediction and analysis in the behavioral sciences. PhD thesis, Harvard University.
↑ Paul Werbos (1982). Applications of advances in nonlinear sensitivity analysis. In System modeling and optimization (pp. 762-770). Springer Berlin Heidelberg. Online
↑ Alpaydın, Ethem (2010). Introduction to machine learning (2nd ed.). Cambridge, Mass.: MIT Press. p. 250. ISBN 978-0-262-01243-0.
↑ Eric A. Wan (1993). Time series prediction by using a connectionist network with internal delay lines. In SANTA FE INSTITUTE STUDIES IN THE SCIENCES OF COMPLEXITY-PROCEEDINGS (Vol. 15, pp. 195-195). Addison-Wesley Publishing Co.

External links

A Gentle Introduction to Backpropagation - An intuitive tutorial by Shashi Sathyanarayana The article contains pseudocode ("Training Wheels for Training Neural Networks") for implementing the algorithm.
Neural Network Back-Propagation for Programmers (a tutorial)
Backpropagation for mathematicians
Chapter 7 The backpropagation algorithm of Neural Networks - A Systematic Introduction by Raúl Rojas (ISBN 978-3540605058)
Quick explanation of the backpropagation algorithm
Graphical explanation of the backpropagation algorithm
Concise explanation of the backpropagation algorithm using math notation by Anand Venkataraman
Visualization of a learning process using backpropagation algorithm
Backpropagation neural network tutorial at the Wikiversity

This article is issued from Wikipedia - version of the 11/28/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.