3. Back-propagation and Learning

Chapter 3
Back-propagation and Learning

This lecture covers the technology at the heart of deep learning: back-propagation. We begin with a brief review of supervised machine learning and optimization by gradient descent. Then by considering deep learning models as computation graphs, or equivalently function compositions, we show how gradients can be automatically computed. We cover some practical considerations and conclude with an example of putting it all together to learn a simple multi-class classifier.

Recall that in supervised learning we are given a parametrized model \(y = f(x; \theta)\) and a set of training examples \(\cD = \{(x^{(i)}, y^{(i)})\}_{i=1}^{N}\). Our goal is to find the parameters \(\theta\) so that \(f(x^{(i)}; \theta)\) is a good predictor of \(y^{(i)}\) for all \(i=1, \ldots, N\). We do this by defining a regularized loss function \(L\) that measures how well the model fits the training data. The loss function usually decomposed over the training data plus a prior on the parameters,

\begin{align} L(\theta) &\triangleq \sum_{i=1}^{N} \ell\!\left(f(x^{(i)}; \theta), y^{(i)}\right) + R(\theta) \tag{73}\end{align}

We then optimize the loss function with respect to the parameters to find the best model

\begin{align} \theta^\star &= \argmin_{\theta} L(\theta) \tag{74}\end{align}

The simplest algorithm for doing this is gradient descent, which iteratively updates \(\theta\) as

\begin{align} \theta \leftarrow \theta - \eta \nabla_{\!\theta} L \tag{75}\end{align}

where \(\eta\) is a step size, either fixed or chosen via some step size schedule.

The most basic model we can think of in deep learning is the multi-layer perceptron (MLP), which is a composition of affine transformations with elementwise non-linear transforms. Concretely, let \(x \in \reals^{p_0}\) be the input data, \(z_j \in \reals^{p_j}\) be the hidden layer features, and \(y \in \reals^{p_n}\) be the output. Each layer computes its output as

\begin{align} z_j &= f_j(z_{j-1}) = \sigma_j(A_j z_{j-1} + b_j) \tag{76}\end{align}

where \(A_j \in \reals^{p_{j} \times p_{j-1}}\) and \(b_j \in \reals^{p_j}\) are parameters, and \(\sigma_j\) is a non-linear activation function. To simplify this expression so that it applies to all layers in the network, we have defined \(x \triangleq z_0\) and \(y \triangleq z_n\). Hence, the multi-layer perceptron defines the composition

\begin{align} y &= (f_n \circ \cdots \circ f_2 \circ f_1)(x) \tag{77}\\ &= \sigma_n(A_n \sigma_{n-1}( \cdots \sigma_1(A_1 x + b_1)) + b_n) \tag{78}\end{align}

The idea of composing affine functions and non-linear activations in multi-layer perceptrons can be generalised in the sense that the function \(f(\cdot; \theta)\) can be an arbitrarily composition of simple differentiable parametrized sub-functions, and where the parameters of these functions are optimised end-to-end. The composed function can be represented by a computation graph as illustrated in Figure 20, where the sub-functions are depicted as nodes in the graph. This type of representation is very popular for describing deep learning architectures where nodes can denote anything from a very simple arithmetic operation to very complicated algorithmic procedures and data transformations.

To compute the output of the function, we sort the nodes in topological order and evaluate each sub-function in turn,

\begin{align} z_1 &= f_1(x; \theta_1) \notag \\ z_2 &= f_2(z_1; \theta_2) \notag \\ &\hphantom{=} \vdots \tag{79}\\ z_7 &= f_7(z_6; \theta_7) \notag \\ y &= f_8(z_4, z_7; \theta_8) \notag \end{align}
Example of a deep learning model as an end-to-end computation graph. This graph implements the composed function where each ’s parameters have been omitted for
Figure 20: Example of a deep learning model as an end-to-end computation graph. This graph implements the composed function \(y = f_8(f_4(f_3(f_2(f_1(x)))), f_7(f_6(f_5(f_1(x)))))\) where each \(f_i\)’s parameters have been omitted for brevity. Note here that \(f_8\) takes three arguments: one the output from \(f_4\), another the output from \(f_7\), and the last parameters \(\theta_8\).

To compute the derivative of a loss function at the output of the graph, with respect to any parameter or input of the graph, we simply apply the chain rule of differentiation by following the arrows backwards through the graph. This is known as back propagation. Two examples are shown in Figure 21 for computing the derivative of the loss \(L\) with respect to parameter \(\theta_7\) and parameter \(\theta_1\), respectively. Here writing out the chain rule we have

\begin{align} \frac{\partial L}{\partial \theta_7} = \frac{\partial L}{\partial y} \frac{\partial y}{\partial z_7} \frac{\partial z_7}{\partial \theta_7} \qquad\text{and}\qquad \frac{\partial L}{\partial \theta_1} &= \frac{\partial L}{\partial y} \left( \frac{\partial y}{\partial z_4} \frac{\partial z_4}{\partial z_3} \frac{\partial z_3}{\partial z_2} \frac{\partial z_2}{\partial z_1} + \frac{\partial y}{\partial z_7} \frac{\partial z_7}{\partial z_6} \frac{\partial z_6}{\partial z_5} \frac{\partial z_5}{\partial z_1} \right) \frac{\partial z_1}{\partial \theta_1} \label{eqn:dl_grad_example} \tag{80}\end{align}

where, for the latter derivative \(\frac{\partial L}{\partial \theta_1}\), the first term in the summation is from the top branch and second term in the summation is from the bottom branch of the graph.

Back-propagation of gradients through the computation graph. See text for details
Figure 21: Back-propagation of gradients through the computation graph. See text for details.