# Backpropagation Algorithm

### From Ufldl

(Created page with "Suppose we have a fixed training set <math>\{ (x^{(1)}, y^{(1)}), \ldots, (x^{(m)}, y^{(m)}) \}</math> of <math>m</math> training examples. We can train our neural network using ...") |
|||

Line 95: | Line 95: | ||

here is the backpropagation algorithm: | here is the backpropagation algorithm: | ||

- | + | :1. Perform a feedforward pass, computing the activations for layers <math>L_2</math>, <math>L_3</math>, and so on up to the output layer <math>L_{n_l}</math>. | |

- | :1. Perform a feedforward pass, computing the activations for layers <math>L_2</math>, <math>L_3</math>, and | + | |

- | so on up to the output layer <math>L_{n_l}</math>. | + | |

:2. For each output unit <math>i</math> in layer <math>n_l</math> (the output layer), set | :2. For each output unit <math>i</math> in layer <math>n_l</math> (the output layer), set | ||

::<math>\begin{align} | ::<math>\begin{align} | ||

Line 114: | Line 112: | ||

\frac{\partial}{\partial b_{i}^{(l)}} J(W,b; x, y) &= \delta_i^{(l+1)}. | \frac{\partial}{\partial b_{i}^{(l)}} J(W,b; x, y) &= \delta_i^{(l+1)}. | ||

\end{align}</math> | \end{align}</math> | ||

+ | |||

+ | Finally, we can also re-write | ||

+ | the algorithm using matrix-vectorial notation. | ||

+ | We will use "<math>\textstyle \bullet</math>" to denote the element-wise product | ||

+ | operator (denoted ``{\tt .*}'' in Matlab or Octave, and also called the Hadamard product), | ||

+ | so | ||

+ | that if <math>\textstyle a = b \bullet c</math>, then <math>\textstyle a_i = b_ic_i</math>. | ||

+ | Similar to how we extended the definition of <math>\textstyle f(\cdot)</math> to apply element-wise to vectors, we also | ||

+ | do the same for <math>\textstyle f'(\cdot)</math> (so that <math>\textstyle f'([z_1, z_2, z_3]) = | ||

+ | [\frac{\partial}{\partial z_1} f(z_1), | ||

+ | \frac{\partial}{\partial z_2} f(z_2), | ||

+ | \frac{\partial}{\partial z_3} f(z_3)]</math>). | ||

+ | The algorithm can then be written: | ||

+ | |||

+ | : 1. Perform a feedforward pass, computing the activations for layers <math>\textstyle L_2</math>, <math>\textstyle L_3</math>, up to the output layer <math>\textstyle L_{n_l}</math>, using Equations~(\ref{eqn-forwardprop1}-\ref{eqn-forwardprop2}). | ||

+ | : 2. For the output layer (layer <math>\textstyle n_l</math>), set | ||

+ | ::<math>\begin{align} | ||

+ | \delta^{(n_l)} | ||

+ | = - (y - a^{(n_l)}) \bullet f'(z^{(n)}) | ||

+ | \end{align}</math> | ||

+ | : 3. For <math>\textstyle l = n_l-1, n_l-2, n_l-3, \ldots, 2</math> | ||

+ | ::Set | ||

+ | :::<math>\begin{align} | ||

+ | \delta^{(l)} = \left((W^{(l)})^T \delta^{(l+1)}\right) \bullet f'(z^{(l)}) | ||

+ | \end{align}</math> | ||

+ | : 4. Compute the desired partial derivatives: | ||

+ | ::<math>\begin{align} | ||

+ | \nabla_{W^{(l)}} J(W,b;x,y) &= \delta^{(l+1)} (a^{(l)})^T, \\ | ||

+ | \nabla_{b^{(l)}} J(W,b;x,y) &= \delta^{(l+1)}. | ||

+ | \end{align}</math> | ||

+ | |||

+ | <br> | ||

+ | '''Implementation note:''' In steps 2 and 3 above, we need to compute <math>\textstyle f'(z^{(l)}_i)</math> for each value of <math>\textstyle i</math>. | ||

+ | Assuming <math>\textstyle f(z)</math> is the sigmoid activation function, we would already have <math>\textstyle a^{(l)}_i</math> stored away from the | ||

+ | forward pass through the network. Thus, using the expression that we worked out earlier for <math>\textstyle f'(z)</math>, | ||

+ | we can compute this as <math>\textstyle f'(z^{(l)}_i) = a^{(l)}_i (1- a^{(l)}_i)</math>. | ||

+ | <br> | ||

+ | |||

+ | |||

+ | Finally, we are ready to describe the full gradient descent algorithm. In the pseudo-code | ||

+ | below, <math>\textstyle \Delta W^{(l)}</math> is a matrix (of the same dimension as <math>\textstyle W^{(l)}</math>), and | ||

+ | <math>\textstyle \Delta b^{(l)}</math> is a vector (of the same dimension as <math>\textstyle b^{(l)}</math>). Note that in this notation, | ||

+ | ``<math>\textstyle \Delta W^{(l)}</math>'' is a matrix, and in particular it isn't ``<math>\textstyle \Delta</math> times <math>\textstyle W^{(l)}</math>.'' | ||

+ | We implement one iteration of batch gradient descent as follows: | ||

+ | |||

+ | : 1. Set <math>\textstyle \Delta W^{(l)} := 0</math>, <math>\textstyle \Delta b^{(l)} := 0</math> (matrix/vector of zeros) for all <math>\textstyle l</math>. | ||

+ | : 2. For <math>\textstyle i = 1</math> to <math>\textstyle m</math>, | ||

+ | :: 2a. Use backpropagation to compute <math>\textstyle \nabla_{W^{(l)}} J(W,b;x,y)</math> and \\ | ||

+ | <math>\textstyle \nabla_{b^{(l)}} J(W,b;x,y)</math>. | ||

+ | :: 2b. Set <math>\textstyle \Delta W^{(l)} := \Delta W^{(l)} + \nabla_{W^{(l)}} J(W,b;x,y)</math>. | ||

+ | :: 2c. Set <math>\textstyle \Delta b^{(l)} := \Delta b^{(l)} + \nabla_{b^{(l)}} J(W,b;x,y)</math>. | ||

+ | : 3. Update the parameters: | ||

+ | :<math>\begin{align} | ||

+ | W^{(l)} &= W^{(l)} - \alpha \left[ \left(\frac{1}{m} \Delta W^{(l)} \right) + \lambda W^{(l)}\right] \\ | ||

+ | b^{(l)} &= b^{(l)} - \alpha \left[\frac{1}{m} \Delta b^{(l)}\right] | ||

+ | \end{align}</math> | ||

+ | |||

+ | To train our neural network, we can now repeatedly take steps of gradient | ||

+ | descent to reduce our cost function <math>\textstyle J(W,b)</math>. |

## Revision as of 23:26, 26 February 2011

Suppose we have a fixed training
set of *m* training examples.
We can train our neural network using batch gradient descent. In detail, for
a single training example (*x*,*y*), we define the cost function with respect to that
single example to be

This is a (one-half) squared-error cost function.
Given a training set of *m* examples, we then define the overall cost function to be

The first term in the definition of *J*(*W*,*b*) is an average sum-of-squares error term.
The second term is a regularization
term (also called a **weight decay** term) that tends to decrease the magnitude of the weights,
and helps prevent overfitting.

[Note: Usually weight decay is not applied to the bias terms ,
as reflected in our definition for *J*(*W*,*b*). Applying weight decay
to the bias units usually makes only a small different to the final network,
however. If you took CS229, you may also recognize weight decay this as
essentially a variant of the Bayesian regularization method you saw there,
where we placed a Gaussian prior on the parameters and did MAP (instead of
maximum likelihood) estimation.]

The **weight decay parameter** λ controls the relative importance
of the two terms. Note also the slightly overloaded notation: *J*(*W*,*b*;*x*,*y*) is the squared error cost
with respect to a single example; *J*(*W*,*b*) is the overall cost function, which includes the weight decay term.

This cost function above is often used both for classification and for regression problems. For classification,
we let *y* = 0 or 1 represent the two class labels (recall that the sigmoid activation function
outputs values in [0,1]; if we were using a tanh activation function, we would instead use -1 and +1 to denote
the labels). For regression problems, we first scale our outputs to ensure that they lie
in the [0,1] range (or if we were using a tanh activation function, then the [ − 1,1] range).

Our goal is to minimize *J*(*W*,*b*) as a function of *W* and *b*.
To train our neural network, we will initialize each parameter and each to a small random value near
zero (say according to a *N**o**r**m**a**l*(0,ε^{2}) distribution for some small ε, say 0.01),
and then apply an optimization algorithm such as batch gradient descent. Since *J*(*W*,*b*) is a non-convex function,
gradient descent is susceptible to local optima; however, in practice gradient descent
usually works fairly well.
Finally, note that it is important to initialize
the parameters randomly, rather than to all 0's. If all the parameters start off
at identical values, then all the hidden layer units will end up learning the same
function of the input (more formally, will be the same for all values of *i*, so that
for any input *x*).
The random initialization serves the purpose of
**symmetry breaking**.

One iteration of gradient descent updates the parameters *W*,*b* as follows:

where α is the learning rate. The key step is computing the partial derivatives
above.
We will now describe the **backpropagation** algorithm, which gives an
efficient way to compute these partial derivatives.

We will first describe how backpropagation can be used to
compute and
, the
partial derivatives of the cost function *J*(*W*,*b*;*x*,*y*) defined with respect
to a single example (*x*,*y*).
Once we can compute these,
then by referring to Equation~(\ref{eqn-costfunction}), we see that
the derivative of the overall cost function *J*(*W*,*b*) can be computed as

The two lines above differ slightly because weight decay is applied to *W* but not *b*.

The intuition behind the backpropagation algorithm is as follows.
Given a training example (*x*,*y*), we will first run a ``forward pass* to*
compute all the activations throughout the network, including the output value
of the hypothesis *h*_{W,b}(*x*). Then, for each node *i* in layer *l*, we would like
to compute an ``error term* that measures how much that node was*
``responsible* for any errors in our output.*
For an output node, we can directly measure the difference between the
network's activation and the true target value, and use that to define
(where layer *n*_{l} is the output layer). How about hidden
units? For those, we will compute based on a weighted average
of the error terms of the nodes that uses as an input. In detail,
here is the backpropagation algorithm:

- 1. Perform a feedforward pass, computing the activations for layers
*L*_{2},*L*_{3}, and so on up to the output layer . - 2. For each output unit
*i*in layer*n*_{l}(the output layer), set - 3. For
- For each node
*i*in layer*l*, set

- For each node
- 4. Compute the desired partial derivatives, which are given as:

Finally, we can also re-write
the algorithm using matrix-vectorial notation.
We will use "" to denote the element-wise product
operator (denoted ``{\tt .*}* in Matlab or Octave, and also called the Hadamard product),*
so
that if , then .
Similar to how we extended the definition of to apply element-wise to vectors, we also
do the same for (so that ).
The algorithm can then be written:

- 1. Perform a feedforward pass, computing the activations for layers , , up to the output layer , using Equations~(\ref{eqn-forwardprop1}-\ref{eqn-forwardprop2}).
- 2. For the output layer (layer ), set
- 3. For
- Set

- Set
- 4. Compute the desired partial derivatives:

**Implementation note:** In steps 2 and 3 above, we need to compute for each value of .
Assuming is the sigmoid activation function, we would already have stored away from the
forward pass through the network. Thus, using the expression that we worked out earlier for ,
we can compute this as .

Finally, we are ready to describe the full gradient descent algorithm. In the pseudo-code
below, is a matrix (of the same dimension as ), and
is a vector (of the same dimension as ). Note that in this notation,
``* is a matrix, and in particular it isn't `` times .*
We implement one iteration of batch gradient descent as follows:

- 1. Set , (matrix/vector of zeros) for all .
- 2. For to ,
- 2a. Use backpropagation to compute and \\

.

- 2b. Set .
- 2c. Set .

- 3. Update the parameters:

To train our neural network, we can now repeatedly take steps of gradient descent to reduce our cost function .