Neural Networks

Linear models in fixed basis functions (Chapters 3 and 4) are easy to fit but cannot adapt their features to the data. A neural network keeps the form "linear combination of basis functions" but lets each basis function be a nonlinear function of a linear combination of the inputs, with adjustable coefficients. This chapter covers how such networks compute (Section 5.1), what error function to minimise and why (5.2), how to compute its gradient in time proportional to the number of weights (backpropagation, 5.3) and its second derivatives (5.4), how to control over-fitting and build in invariances (5.5), how to model multimodal targets (5.6), and how to treat the weights in a Bayesian way (5.7).

TrungTin Nguyen · Following Bishop (2006), Pattern Recognition and Machine Learning, Chapter 5 · Course home · Mathematical toolkit · Python code for the figures

Ch. 1 Introduction Ch. 2 Probability distributions Ch. 3 Linear regression Ch. 4 Linear classification Ch. 5 Neural networks Ch. 6 Kernel methods Ch. 7 Sparse kernel machines Ch. 8 Graphical models Ch. 9 Mixture models and EM Ch. 10 Approximate inference Ch. 11 Sampling methods Ch. 12 Continuous latent variables Ch. 13 Sequential data Ch. 14 Combining models

5.1 Feed-forward network functions

pp. 227–231 The linear models of Chapters 3 and 4 have the form \(y(\mathbf{x},\mathbf{w})\)\({}=f\big(\sum_{j}w_j\phi_j(\mathbf{x})\big)\) (5.1) with fixed basis functions \(\phi_j\), which suffers from the curse of dimensionality when the \(\phi_j\) are chosen without looking at the data. A neural network makes the basis functions adaptive: each one is itself "a nonlinear function of a linear combination of the inputs", and the coefficients of these inner linear combinations are learned together with the outer ones.

Why "two-layer". The count that matters is the number of layers of adaptive weights, so Figure 5.1 is a two-layer network (it is also called a three-layer network, counting layers of units, or a single-hidden-layer network). Both stages resemble the perceptron of Section 4.1.7, which is why the model is also called the multilayer perceptron (MLP), but with smooth instead of step nonlinearities, so \(y_k\) is differentiable in \(\mathbf{w}\), the property on which training rests.

Universal approximation. The book cites a family of theorems (Funahashi 1989; Cybenko 1989; Hornik, Stinchcombe and White 1989; Hornik 1991) saying that two-layer networks with linear outputs can approximate any continuous function on a compact set. The precise statement, and a complete proof in the simplest case that shows where the hidden units come from, are below.

5.1.1 Weight-space symmetries

pp. 231–232 Different weight vectors can define the very same function \(\mathbf{x}\mapsto\mathbf{y}\). This does not matter for prediction, but it matters for the Bayesian model comparison of Section 5.7, where the volume of weight space occupied by a network enters the evidence.

5.2 Network training

pp. 232–241 The simplest recipe for choosing \(\mathbf{w}\) is the curve-fitting one of Section 1.1: minimise the sum of squares \(E(\mathbf{w})\)\({}=\tfrac12\sum_n\|\mathbf{y}(\mathbf{x}_n,\mathbf{w})\)\({}-\mathbf{t}_n\|^2\) (5.11). A probabilistic reading of the network output explains this choice, shows when it is wrong, and tells us which output nonlinearity to pair with which error function.

5.2.1 Parameter optimization

pp. 236–237 Think of \(E(\mathbf{w})\) as a surface over weight space (Figure 5.5). For a small step, \(\delta E\)\({}\simeq\delta\mathbf{w}^\T\nabla E(\mathbf{w})\), so \(\nabla E\) points uphill, and at a minimiser the gradient must vanish, \[ \nabla E(\mathbf{w})=\mathbf{0}, \tag{5.26} \] since otherwise a small step along \(-\nabla E\) would lower the error. Stationary points are minima, maxima or saddle points. By Result 5.2, every local minimum of a two-layer network comes with \(M!\,2^M\) equivalent copies, and there will in general also be inequivalent local minima, so it is useful to compare several (from different random starts, judged on a validation set). There is no closed-form solution of (5.26), so one iterates \[ \mathbf{w}^{(\tau+1)}=\mathbf{w}^{(\tau)}+\Delta\mathbf{w}^{(\tau)}, \tag{5.27} \] with an update \(\Delta\mathbf{w}^{(\tau)}\) that differs from algorithm to algorithm and, in most, uses \(\nabla E\) at the new point.

5.2.2 Local quadratic approximation

pp. 237–239 Expanding about a point \(\widehat{\mathbf{w}}\) to second order, \[ E(\mathbf{w})\simeq E(\widehat{\mathbf{w}})+(\mathbf{w}-\widehat{\mathbf{w}})^\T\mathbf{b}+\tfrac12(\mathbf{w}-\widehat{\mathbf{w}})^\T\mathbf{H}(\mathbf{w}-\widehat{\mathbf{w}}), \tag{5.28} \] where the gradient \(\mathbf{b}\)\({}\equiv\nabla E|_{\mathbf{w}=\widehat{\mathbf{w}}}\) (5.29) and the Hessian \(\mathbf{H}=\nabla\nabla E\) has entries \((\mathbf{H})_{ij}\)\({}=\partial^2E/\partial w_i\partial w_j|_{\mathbf{w}=\widehat{\mathbf{w}}}\) (5.30). The local gradient is then \[ \nabla E\simeq\mathbf{b}+\mathbf{H}(\mathbf{w}-\widehat{\mathbf{w}}). \tag{5.31} \]

5.2.3 Use of gradient information

pp. 239–240

5.2.4 Gradient descent optimization

pp. 240–241 The simplest use of \(\nabla E\) is a step of size \(\eta>0\) (the learning rate) against the gradient, \[ \mathbf{w}^{(\tau+1)}=\mathbf{w}^{(\tau)}-\eta\nabla E(\mathbf{w}^{(\tau)}). \tag{5.41} \] This is a batch method: each step needs the gradient over the whole training set. When the error is a sum over data points, \[ E(\mathbf{w})=\sum_{n=1}^{N}E_n(\mathbf{w}), \tag{5.42} \] the on-line (sequential, stochastic) version updates after each point, \[ \mathbf{w}^{(\tau+1)}=\mathbf{w}^{(\tau)}-\eta\nabla E_n(\mathbf{w}^{(\tau)}), \tag{5.43} \] cycling through the data or sampling with replacement.

Why on-line methods cope with redundancy. Duplicate every data point: the error doubles, \(2E\), and so does the batch gradient (twice the work for the same direction), while a sweep of on-line updates simply sees each point twice at no extra cost per update. A stationary point of \(E\) is generally not stationary for the individual \(E_n\) (their gradients cancel only in the sum), so on-line updates keep moving and can leave a shallow local minimum. Plain steepest descent is nonetheless a poor batch algorithm (Bishop and Nabney, 2008): its behaviour on the elongated bowls of Result 5.5 is analysed in Result 5.13 (it converges only for \(\eta<2/\lambda_{\max}\) and slowly along directions with small \(\lambda_i\)), while conjugate gradients and quasi-Newton methods decrease the error monotonically and are faster. The demo weight decay and early stopping show the effect of the learning dynamics on fit.

5.3 Error backpropagation

pp. 241–249 Gradient-based training needs \(\nabla E\) at every step, so its cost matters. Backpropagation evaluates all the partial derivatives by passing information forwards and then backwards through the network, at a cost comparable to a single forward evaluation. The word is used loosely in the literature (for the MLP itself, or for gradient descent on the sum of squares). Here it names only the first of the two stages of a training step, the evaluation of derivatives; the second stage, using the derivatives to change the weights, can be done by any optimiser of Section 5.2. The same derivative-propagation idea also yields the Jacobian (5.3.4) and the Hessian (5.4).

5.3.1 Evaluation of error-function derivatives

pp. 242–245 For i.i.d. data the error is a sum over patterns, \[ E(\mathbf{w})=\sum_{n=1}^{N}E_n(\mathbf{w}) , \tag{5.44} \] so it is enough to compute \(\nabla E_n\) for one pattern (and sum, (5.57)). As a warm-up, for a single linear layer \(y_k=\sum_iw_{ki}x_i\) (5.45) with \(E_n=\tfrac12\sum_k(y_{nk}-t_{nk})^2\) (5.46), \[ \frac{\partial E_n}{\partial w_{ji}}=(y_{nj}-t_{nj})\,x_{ni}, \tag{5.47} \] an "error signal" at the output end of the link times the variable at its input end. Backpropagation shows that the same local structure persists in any feed-forward network.

5.3.2 A simple example

pp. 245–246 Take the two-layer network of Figure 5.1 with \(\tanh\) hidden units, linear outputs and \(E_n=\tfrac12\sum_k(y_k-t_k)^2\) (5.61). The hidden activation is \[ h(a)=\tanh a=\frac{e^{a}-e^{-a}}{e^{a}+e^{-a}} \tag{5.58, 5.59} \] and its derivative is a function of its value (Erratum: "logistic sigmoid" on p. 245 should read "sigmoidal"), \[ h'(a)=1-h(a)^2. \tag{5.60} \]

For each pattern, forward propagation is \[ a_j=\sum_{i=0}^{D}w^{(1)}_{ji}x_i,\qquad z_j=\tanh(a_j),\qquad y_k=\sum_{j=0}^{M}w^{(2)}_{kj}z_j, \tag{5.62, 5.63, 5.64} \] then the output errors \(\delta_k=y_k-t_k\) (5.65), the hidden errors \[ \delta_j=(1-z_j^2)\sum_{k=1}^{K}w^{(2)}_{kj}\delta_k, \tag{5.66} \] and the derivatives \[ \frac{\partial E_n}{\partial w^{(1)}_{ji}}=\delta_jx_i,\qquad \frac{\partial E_n}{\partial w^{(2)}_{kj}}=\delta_kz_j. \tag{5.67} \] Note that (5.66) is (5.56) with \(h'(a_j)=1-z_j^2\) computed from the stored forward values \(z_j\), at no extra cost.

5.3.3 Efficiency of backpropagation

pp. 246–247 Let \(W\) be the number of weights and biases. Forward propagation costs \(O(W)\): except for very sparse networks \(W\) far exceeds the number of units, so the cost is dominated by the multiply-adds of the sums (5.48), and the evaluation of the activation functions is a small overhead. Backpropagation does the same amount of work in reverse: (5.56) uses each weight once, and (5.53) once more, so the whole gradient costs \(O(W)\), only a small constant factor more than evaluating the error itself.

def grad(w):                       # backpropagation, (5.62)-(5.67), summed over patterns
    for x, t in zip(X, T):
        xe, a, z, ze, y = forward(w, x)          # xe = (1, x), ze = (1, z)
        dk = y - t                                # (5.65)
        dj = (1 - z**2) * (W2[:, 1:].T @ dk)      # (5.66)
        g1 += np.outer(dj, xe); g2 += np.outer(dk, ze)   # (5.67)
num = [(E(w + eps*e) - E(w - eps*e)) / (2*eps) for e in np.eye(W)]   # (5.69)

Modular systems and the Jacobian. Backpropagation applies to any differentiable module, not only to sigmoidal layers. In a system built of modules (Figure 5.8: an adaptive module with parameter \(\mathbf{w}\) feeding other modules that produce \(\mathbf{y}\)), the chain rule gives \(\partial E/\partial\mathbf{w}\)\({}=\sum_{k,j}\frac{\partial E}{\partial y_k}\frac{\partial y_k}{\partial z_j}\frac{\partial z_j}{\partial\mathbf{w}}\) (5.71); the middle factor is the Jacobian of the intermediate module.

5.3.4 The Jacobian matrix

pp. 247–249 The Jacobian of the network map has entries \[ J_{ki}\equiv\frac{\partial y_k}{\partial x_i}, \tag{5.70} \] each evaluated with the other inputs held fixed. It measures how sensitive the outputs are to the inputs; for small known input errors \(\Delta x_i\), \[ \Delta y_k\simeq\sum_i\frac{\partial y_k}{\partial x_i}\Delta x_i, \tag{5.72} \] valid only locally, because the network is nonlinear and \(\mathbf{J}\) must be re-evaluated at each input.

5.4 The Hessian matrix

pp. 249–256 Backpropagation also gives second derivatives \(\partial^2E/\partial w_{ji}\partial w_{lk}\) (5.78); collecting all \(W\) parameters in one vector, these are the entries \(H_{ij}\) of the Hessian. The Hessian is used for: (1) second-order optimisation algorithms; (2) fast re-training after a small change of the data; (3) pruning, where the inverse Hessian ranks weights by their importance; (4) the Laplace approximation of Section 5.7, where \(\mathbf{H}^{-1}\) gives the predictive variance, its eigenvalues give the hyperparameters and its determinant the evidence. A \(W\times W\) matrix has \(W^2\) entries, so no method can do better than \(O(W^2)\) per pattern for the whole matrix; the exact algorithm of Section 5.4.5 attains this.

5.4.1 Diagonal approximation

pp. 250 The inverse of a diagonal matrix is trivial, so a diagonal approximation is cheap to invert. Work pattern by pattern (\(E=\sum_nE_n\)).

Ricotti et al. (1988) keep all terms in (5.80), which makes the diagonal exact but the cost no longer \(O(W)\). In practice the Hessian of a trained network is strongly non-diagonal, so diagonal approximations driven by convenience must be used with care.

5.4.2 Outer product approximation

pp. 251 For regression with a single output and \(E=\tfrac12\sum_n(y_n-t_n)^2\) (5.82) the Hessian is \[ \mathbf{H}=\nabla\nabla E=\sum_{n=1}^{N}\nabla y_n(\nabla y_n)^\T+\sum_{n=1}^{N}(y_n-t_n)\nabla\nabla y_n. \tag{5.83} \] Erratum. The book omits the transpose in the first term. Dropping the second term gives the Levenberg–Marquardt or outer product approximation \[ \mathbf{H}\simeq\sum_{n=1}^{N}\mathbf{b}_n\mathbf{b}_n^\T,\qquad \mathbf{b}_n\equiv\nabla a_n=\nabla y_n . \tag{5.84} \] Erratum. The book writes \(\mathbf{b}_n=\nabla y_n=\nabla a_n\); the order of definition above is the corrected one.

Link to Levenberg–Marquardt. Minimising \(\tfrac12\sum_n(y_n(\mathbf{w})-t_n)^2\) by linearising \(y_n(\mathbf{w}+\Delta)\)\({}\simeq y_n+\mathbf{b}_n^\T\Delta\) gives a linear least-squares problem whose normal equations are \(\mathbf{H}_{\rm GN}\Delta=-\nabla E\) (Gauss–Newton step). Levenberg (1944) and Marquardt (1963) damp it, \((\mathbf{H}_{\rm GN}+\mu\mathbf{I})\Delta\)\({}=-\nabla E\): for \(\mu\to0\) a Gauss–Newton step, for \(\mu\to\infty\) a gradient-descent step of size \(1/\mu\); the damping also repairs the rank deficiency. In the small network of Section 5.3.3 (\(N=6\), \(K=2\), \(W=17\)) the outer-product matrix indeed had rank 12 \(=NK

5.4.3 Inverse Hessian

pp. 252 Write the outer-product approximation as \(\mathbf{H}_N\)\({}=\sum_{n=1}^{N}\mathbf{b}_n\mathbf{b}_n^\T\) (5.86) and add the data points one at a time, \(\mathbf{H}_{L+1}\)\({}=\mathbf{H}_L\)\({}+\mathbf{b}_{L+1}\mathbf{b}_{L+1}^\T\) (5.87).

Quasi-Newton optimisers (BFGS and relatives) build an approximation to \(\mathbf{H}^{-1}\) as a by-product of training (Bishop and Nabney, 2008).

5.4.4 Finite differences

pp. 252–253 Perturbing every pair of weights, \[ \frac{\partial^2E}{\partial w_{ji}\partial w_{lk}}=\frac1{4\epsilon^2}\{E(w_{ji}+\epsilon,w_{lk}+\epsilon)-E(w_{ji}+\epsilon,w_{lk}-\epsilon)-E(w_{ji}-\epsilon,w_{lk}+\epsilon)+E(w_{ji}-\epsilon,w_{lk}-\epsilon)\}+O(\epsilon^2). \tag{5.90} \] Applying central differences to the first derivatives, themselves obtained by backpropagation, is cheaper: \[ \frac{\partial^2E}{\partial w_{ji}\partial w_{lk}}=\frac1{2\epsilon}\Big\{\frac{\partial E}{\partial w_{ji}}(w_{lk}+\epsilon)-\frac{\partial E}{\partial w_{ji}}(w_{lk}-\epsilon)\Big\}+O(\epsilon^2). \tag{5.91} \]

5.4.5 Exact evaluation of the Hessian

pp. 253–254 For a network with two layers of weights the exact Hessian is derived by differentiating the backpropagation formulae. Indices \(i,i'\) denote inputs, \(j,j'\) hidden units, \(k,k'\) outputs, and \[ \delta_k=\frac{\partial E_n}{\partial a_k},\qquad M_{kk'}\equiv\frac{\partial^2E_n}{\partial a_k\partial a_{k'}} . \tag{5.92} \] (For the sum of squares with linear outputs \(M_{kk'}=\delta_{kk'}\), for sigmoid cross-entropy \(M_{kk'}=\delta_{kk'}y_k(1-y_k)\), for softmax cross-entropy \(M_{kk'}=y_k\delta_{kk'}-y_ky_{k'}\).)

5.4.6 Fast multiplication by the Hessian

pp. 254–256 Often one needs \(\mathbf{H}\mathbf{v}\) (or \(\mathbf{v}^\T\mathbf{H}\)), not \(\mathbf{H}\): conjugate-gradient or power iterations, trace estimates, eigenvalues for \(\gamma\) (Section 5.7.2). Forming \(\mathbf{H}\) costs \(O(W^2)\) time and storage, but \(\mathbf{v}^\T\mathbf{H}\) has only \(W\) entries, and can be had in \(O(W)\). Since \(\mathbf{H}\) is symmetric, \[ \mathbf{v}^\T\mathbf{H}=\mathbf{v}^\T\nabla(\nabla E), \tag{5.96} \] i.e. the directional derivative of the gradient. Define the differential operator \(\mathcal{R}\{\cdot\}\equiv\mathbf{v}^\T\nabla\) (Pearlmutter, 1994); it obeys the ordinary rules of calculus (linearity, product rule, chain rule) and \[ \mathcal{R}\{\mathbf{w}\}=\mathbf{v}. \tag{5.97} \]

5.5 Regularization in neural networks

pp. 256–272 The numbers of inputs and outputs are fixed by the data, but the number \(M\) of hidden units is free and controls model complexity. One might hope for an optimal \(M\) balancing under- and over-fitting (Figure 5.9), but the generalisation error is not a smooth function of \(M\), because of local minima: Figure 5.10 shows 30 random starts for each \(M\), and the best validation error happened at \(M=8\). An alternative is to take \(M\) large and add a regulariser, the simplest being weight decay \[ \widetilde{E}(\mathbf{w})=E(\mathbf{w})+\frac\lambda2\mathbf{w}^\T\mathbf{w}, \tag{5.112} \] the negative log of a zero-mean Gaussian prior with precision \(\lambda\) (Chapter 3).

5.5.1 Consistent Gaussian priors

pp. 257–259 Simple weight decay treats all weights alike and is inconsistent with the scaling properties of networks. Take a two-layer network with linear outputs, \[ z_j=h\Big(\sum_iw_{ji}x_i+w_{j0}\Big),\qquad y_k=\sum_jw_{kj}z_j+w_{k0}, \tag{5.113, 5.114} \] and rescale the data linearly, \[ x_i\to\widetilde{x}_i=ax_i+b,\qquad y_k\to\widetilde{y}_k=cy_k+d . \tag{5.115, 5.118} \]

The regulariser (5.121) is the negative log of the (improper) prior \[ p(\mathbf{w}\given\alpha_1,\alpha_2)\propto\exp\Big(-\frac{\alpha_1}2\sum_{w\in\mathcal{W}_1}w^2-\frac{\alpha_2}2\sum_{w\in\mathcal{W}_2}w^2\Big), \tag{5.122} \] improper because the biases are unconstrained, so it cannot be normalised and its evidence would be zero. For Bayesian model comparison one therefore gives the biases their own Gaussian priors (breaking the shift invariance), leaving four hyperparameters \(\alpha_1^w,\alpha_1^b,\alpha_2^w,\alpha_2^b\). More generally, any partition of the weights into groups \(\mathcal{W}_k\) gives \[ p(\mathbf{w})\propto\exp\Big(-\frac12\sum_k\alpha_k\|\mathbf{w}\|_k^2\Big),\qquad \|\mathbf{w}\|_k^2=\sum_{j\in\mathcal{W}_k}w_j^2 . \tag{5.123, 5.124} \] If the groups are the weights leaving each input unit and the \(\alpha_k\) are chosen by maximising the marginal likelihood, this is automatic relevance determination (Section 7.2.2): inputs with large \(\alpha_k\) are switched off.

What the four hyperparameters do (a heuristic derivation). The output is \(f(x)\)\({}=\sum_jw^{(2)}_j\tanh(w^{(1)}_jx+b_j)+b^{(2)}\). (i) With independent zero-mean second-layer weights of precision \(\alpha_2^w\), \(\var f(x)\approx M\,\E[\tanh^2]/\alpha_2^w\): \(\alpha_2^w\) sets the vertical scale, and \(\alpha_2^b\) the range of vertical offsets. (ii) A hidden unit switches near \(x_j=-b_j/w_j\) over a width \(\sim1/|w_j|\); so \(\alpha_1^w\) (the scale of \(w_j\)) sets the horizontal scale of the variations, large precision meaning gentle slopes. (iii) The switch position is the ratio of two independent zero-mean Gaussians, which has a Cauchy distribution with scale \(\sigma_b/\sigma_w=\sqrt{\alpha_1^w/\alpha_1^b}\): a small \(\alpha_1^b\) spreads the switch locations over a wide range of \(x\) (the horizontal range of variation).

5.5.2 Early stopping

pp. 259–262 The error on an independent validation set usually falls and then rises as the network begins to over-fit while the training error keeps decreasing; stopping at the minimum of the validation error (Figure 5.12) gives good generalisation. Qualitatively the number of effective degrees of freedom starts small and grows with training. For a quadratic error this can be made precise.

5.5.3 Invariances

pp. 261–263 In many tasks the prediction should not change under transformations of the input: translation or scale of an object in an image, small non-linear time warping in speech. If enough training examples of the transformations are available, an adaptive model can learn the invariance, but the number of combinations grows exponentially with the number of invariances. Four ways to encourage invariance are listed:

1. Augment the training set with transformed replicas (for on-line training, apply a freshly drawn transformation each time a pattern is presented; for batch training replicate each pattern several times). Easy, can give complex invariances (Figure 5.14) and clearly helps generalisation, but is computationally costly.
2. Add a regulariser that penalises changes of the output under the transformation: tangent propagation (5.5.4). Section 5.5.5 shows it is closely related to approach 1.
3. Invariant features: pre-process to extract features that are invariant; any subsequent classifier inherits the invariance and extrapolates beyond the transformations seen in training, but hand-made invariant features may discard discriminating information.
4. Build the invariance into the network structure, via local receptive fields and weight sharing (convolutional networks, 5.5.6), or into the kernel (Chapters 6 and 7).

5.5.4 Tangent propagation

pp. 263–265 A continuous transformation (translation, rotation, but not reflection) governed by a parameter \(\xi\) moves the input \(\mathbf{x}_n\) along a one-dimensional manifold \(\mathcal{M}\) (Figure 5.15). Let \(\mathbf{s}(\mathbf{x},\xi)\) be the transformed vector, with \(\mathbf{s}(\mathbf{x},0)=\mathbf{x}\). The tangent vector at \(\mathbf{x}_n\) is \[ \bm\tau_n=\frac{\partial\mathbf{s}(\mathbf{x}_n,\xi)}{\partial\xi}\Big|_{\xi=0}. \tag{5.125} \] In practice \(\bm\tau_n\) is approximated by a finite difference, \((\mathbf{s}(\mathbf{x}_n,\xi)-\mathbf{x}_n)/\xi\) for a small \(\xi\) (Figure 5.16).

A related technique, tangent distance, builds the same invariance into distance-based methods such as nearest neighbours (Simard et al., 1993).

5.5.5 Training with transformed data

pp. 265–267 Augmenting the data with transformed copies is closely related to tangent propagation. Consider a single output and the sum of squares in the infinite-data limit, \[ E=\frac12\iint\{y(\mathbf{x})-t\}^2p(t\given\mathbf{x})p(\mathbf{x})\,d\mathbf{x}\,dt , \tag{5.129} \] and an infinite number of copies of each pattern, each transformed with \(\xi\) drawn from \(p(\xi)\): \[ \widetilde E=\frac12\iiint\{y(\mathbf{s}(\mathbf{x},\xi))-t\}^2p(t\given\mathbf{x})p(\mathbf{x})p(\xi)\,d\mathbf{x}\,dt\,d\xi . \tag{5.130} \]

5.5.6 Convolutional networks

pp. 267–269 Instead of learning invariance from examples, convolutional networks (Le Cun et al., 1989; LeCun et al., 1998) build it into the structure, exploiting two facts about images: nearby pixels are more strongly correlated than distant ones, and a feature useful in one region is useful in others. Three mechanisms are used: local receptive fields, weight sharing and subsampling (Figure 5.17).

The final layer is typically fully connected with a softmax output. The whole network is trained by backpropagation with the shared-weight modification of Filling the gap 5.5: derivatives of tied weights are summed. The local receptive fields reduce the number of weights, and weight sharing reduces the number of independent parameters much further. Figure 5.17 of the book is a schematic of a convolutional layer followed by a subsampling layer.

5.5.7 Soft weight sharing

pp. 269–272 Weight sharing in the hard form requires knowing the constraints in advance. In the soft form (Nowlan and Hinton, 1992) the weights are encouraged to form groups with similar values by a mixture-of-Gaussians prior, whose centres, widths and weights are learned together with the network: \[ p(\mathbf{w})=\prod_ip(w_i),\qquad p(w_i)=\sum_{j=1}^{M}\pi_j\N(w_i\given\mu_j,\sigma_j^2), \tag{5.136, 5.137} \] \[ \Omega(\mathbf{w})=-\sum_i\ln\Big(\sum_{j=1}^{M}\pi_j\N(w_i\given\mu_j,\sigma_j^2)\Big),\qquad\widetilde E(\mathbf{w})=E(\mathbf{w})+\lambda\Omega(\mathbf{w}). \tag{5.138, 5.139} \] This is minimised jointly over \(\mathbf{w}\) and \(\{\pi_j,\mu_j,\sigma_j\}\) (a joint optimisation avoids the numerical instability of alternating EM, because the weight distribution keeps moving). Regard \(\pi_j\) as prior probabilities and introduce the posterior probabilities (responsibilities) \[ \gamma_j(w)=\frac{\pi_j\N(w\given\mu_j,\sigma_j^2)}{\sum_k\pi_k\N(w\given\mu_k,\sigma_k^2)} . \tag{5.140} \]

5.6 Mixture density networks

pp. 272–277 Least squares is maximum likelihood under a Gaussian \(p(\mathbf{t}\given\mathbf{x})\), which is a poor assumption for inverse problems. In the two-link robot arm of Figure 5.18 the forward map from joint angles \((\theta_1,\theta_2)\) to the end-effector position is a function, \[ x_1=L_1\cos\theta_1+L_2\cos(\theta_1+\theta_2),\qquad x_2=L_1\sin\theta_1+L_2\sin(\theta_1+\theta_2) \] (Exercise 5.33; origin at the shoulder), but the inverse has two solutions, "elbow up" and "elbow down": reflect the elbow across the line from shoulder to end effector. The same happens whenever a many-to-one forward map is inverted (several diseases, same symptoms).

The toy problem: draw \(x_n\sim U(0,1)\), set \(t_n=x_n+0.3\sin(2\pi x_n)+\) uniform noise on \((-0.1,0.1)\); the inverse problem swaps the roles of \(x\) and \(t\). Figure 5.19 shows that a sum-of-squares network fits the forward data well and the inverse data very badly.

5.7 Bayesian neural networks

pp. 277–284 Regularised maximum likelihood is MAP estimation. A full Bayesian treatment marginalises over the weights, but the nonlinear dependence on \(\mathbf{w}\) makes the posterior non-Gaussian and multimodal, so exact inference is impossible. Variational approximations exist (Hinton and van Camp 1993; Barber and Bishop 1998) but the most complete treatment is based on the Laplace approximation (MacKay 1992a,b), assuming (i) a Gaussian approximation around a mode, and (ii) a posterior so narrow that the network is approximately linear in the weights over its support. Then the results of Chapters 3 and 4 apply.

5.7.1 Posterior parameter distribution

pp. 278–280 For a single target, take \[ p(t\given\mathbf{x},\mathbf{w},\beta)=\N(t\given y(\mathbf{x},\mathbf{w}),\beta^{-1}),\qquad p(\mathbf{w}\given\alpha)=\N(\mathbf{w}\given\mathbf{0},\alpha^{-1}\mathbf{I}), \tag{5.161, 5.162} \] so for data \(\mathcal{D}=\{t_1,\dots,t_N\}\) with inputs \(\mathbf{x}_n\), \(p(\mathcal{D}\given\mathbf{w},\beta)\)\({}=\prod_n\N(t_n\given y(\mathbf{x}_n,\mathbf{w}),\beta^{-1})\) (5.163) and \[ p(\mathbf{w}\given\mathcal{D},\alpha,\beta)\propto p(\mathbf{w}\given\alpha)p(\mathcal{D}\given\mathbf{w},\beta) \tag{5.164} \] which is non-Gaussian because \(y\) is nonlinear in \(\mathbf{w}\). Its logarithm is \[ \ln p(\mathbf{w}\given\mathcal{D})=-\frac\alpha2\mathbf{w}^\T\mathbf{w}-\frac\beta2\sum_{n=1}^{N}\{y(\mathbf{x}_n,\mathbf{w})-t_n\}^2+\const , \tag{5.165} \] a regularised sum of squares, maximised by gradient methods at \(\mathbf{w}_{\rm MAP}\) (with backpropagation). The Laplace approximation needs the curvature of the negative log posterior, \[ \mathbf{A}=-\nabla\nabla\ln p(\mathbf{w}\given\mathcal{D},\alpha,\beta)=\alpha\mathbf{I}+\beta\mathbf{H}, \tag{5.166} \] where \(\mathbf{H}\) is the Hessian of the sum-of-squares error \(\tfrac12\sum_n\{y_n-t_n\}^2\) (Section 5.4), and the Gaussian approximation is \[ q(\mathbf{w}\given\mathcal{D})=\N(\mathbf{w}\given\mathbf{w}_{\rm MAP},\mathbf{A}^{-1}). \tag{5.167} \] The predictive distribution is \(p(t\given\mathbf{x},\mathcal{D})\)\({}=\int p(t\given\mathbf{x},\mathbf{w})q(\mathbf{w}\given\mathcal{D})d\mathbf{w}\) (5.168), still intractable. With a small posterior variance, linearise the network at the mode, \[ y(\mathbf{x},\mathbf{w})\simeq y(\mathbf{x},\mathbf{w}_{\rm MAP})+\mathbf{g}^\T(\mathbf{w}-\mathbf{w}_{\rm MAP}),\qquad \mathbf{g}=\nabla_{\mathbf{w}}y(\mathbf{x},\mathbf{w})\big|_{\mathbf{w}_{\rm MAP}}, \tag{5.169, 5.170} \] so that \(p(t\given\mathbf{x},\mathbf{w},\beta)\)\({}\simeq\N(t\given y(\mathbf{x},\mathbf{w}_{\rm MAP})+\mathbf{g}^\T(\mathbf{w}-\mathbf{w}_{\rm MAP}),\beta^{-1})\) (5.171), a linear-Gaussian model.

5.7.2 Hyperparameter optimization

pp. 280–281 The evidence framework (Section 3.5) with the Laplace approximation gives point estimates of \(\alpha\) and \(\beta\). The evidence is \[ p(\mathcal{D}\given\alpha,\beta)=\int p(\mathcal{D}\given\mathbf{w},\beta)p(\mathbf{w}\given\alpha)d\mathbf{w}. \tag{5.174} \]

5.7.3 Bayesian neural networks for classification

pp. 281–284 For a single logistic output \(y=\sigma(a)\), \(t\in\{0,1\}\) there is no \(\beta\) (labels are assumed correct): \[ \ln p(\mathcal{D}\given\mathbf{w})=\sum_{n=1}^{N}\{t_n\ln y_n+(1-t_n)\ln(1-y_n)\}, \tag{5.181} \] with the same prior (5.162). The MAP weights minimise \(E(\mathbf{w})\)\({}=-\ln p(\mathcal{D}\given\mathbf{w})\)\({}+\tfrac\alpha2\mathbf{w}^\T\mathbf{w}\) (5.182); the Hessian \(\mathbf{H}\) of the negative log likelihood is computed exactly (5.4.5) or by the outer-product approximation (5.85); then \(\mathbf{A}=\alpha\mathbf{I}+\mathbf{H}\) (5.166) and \(q(\mathbf{w}\given\mathcal{D})\) is (5.167) again. Erratum. In (5.181) the sum \(\sum_n\) must be written as \(\sum_{n=1}^N\), and (5.183) has no additive constant.

Exercises

All 41 exercises of Chapter 5 (Bishop, 2006, pp. 284–290), restated in my own words, with complete solutions (hidden). Stars give the book's difficulty and "www" marks the exercises with official solutions. Most are the derivations of the results above; their solutions repeat the essential steps and point to the full treatment. Solution manuals were checked and the steps verified independently (several numerically, as reported above).

1. Exercise 5.1 (★★). A two-layer network has logistic-sigmoid hidden units. Show there is an equivalent network, computing exactly the same function, with \(\tanh\) hidden units, and that the parameters differ by linear transformations. (Erratum: the book's "\(g(\cdot)\)" in the exercise should be \(h(\cdot)\).)

   Solution

   \(\sigma(a)=\tfrac12(1+\tanh(a/2))\) because \(\tanh\tfrac a2=\tfrac{1-e^{-a}}{1+e^{-a}}\). Substituting into \(a_k=\sum_jw^{(2)}_{kj}\sigma(a_j)+w^{(2)}_{k0}\) gives a \(\tanh\) network with \(\widetilde w^{(1)}_{ji}=\tfrac12w^{(1)}_{ji}\), \(\widetilde w^{(2)}_{kj}=\tfrac12w^{(2)}_{kj}\), \(\widetilde w^{(2)}_{k0}\)\({}=w^{(2)}_{k0}+\tfrac12\sum_jw^{(2)}_{kj}\), all linear in the original parameters. Details: Filling the gap 5.2.

2. Exercise 5.2 (★, www). Show that maximising the likelihood under (5.16) for a multi-output network is equivalent to minimising the sum-of-squares error (5.11).

   Solution

   \(-\ln\prod_n\N(\mathbf{t}_n\given\mathbf{y}_n,\beta^{-1}\mathbf{I})\)\({}=\frac\beta2\sum_n\|\mathbf{y}_n\)\({}-\mathbf{t}_n\|^2-\frac{NK}2\ln\beta\)\({}+\frac{NK}2\ln2\pi\). For fixed \(\beta>0\) only the first term depends on \(\mathbf{w}\), and it is \(\beta E(\mathbf{w})\) with \(E\) from (5.11); a positive multiple has the same minimisers. Setting \(\partial/\partial\beta=0\) gives \(1/\beta_{\rm ML}\)\({}=\frac1{NK}\sum_n\|\mathbf{y}_n\)\({}-\mathbf{t}_n\|^2\) (5.17). See Result 5.3.

3. Exercise 5.3 (★★). Targets have Gaussian conditional \(\N(\mathbf{t}\given\mathbf{y}(\mathbf{x},\mathbf{w}),\bm\Sigma)\). Write the error to minimise for known \(\bm\Sigma\); then let \(\bm\Sigma\) be unknown and give its ML solution, noting that the optimisations of \(\mathbf{w}\) and \(\bm\Sigma\) are now coupled.

   Solution

   Known \(\bm\Sigma\): \(E(\mathbf{w})\)\({}=\tfrac12\sum_n(\mathbf{y}_n-\mathbf{t}_n)^\T\bm\Sigma^{-1}(\mathbf{y}_n-\mathbf{t}_n)\). Unknown: \(\bm\Sigma_{\rm ML}\)\({}=\frac1N\sum_n(\mathbf{y}_n-\mathbf{t}_n)(\mathbf{y}_n-\mathbf{t}_n)^\T\) at the current \(\mathbf{w}\), which in turn changes the weighting in \(E\); the profile objective is \(\tfrac N2\ln|\mathbf{S}(\mathbf{w})/N|\). Derivation in Filling the gap 5.3.

4. Exercise 5.4 (★★). Binary targets \(t\in\{0,1\}\), network output \(y=p(t=1\given\mathbf{x})\), and each recorded label is wrong with probability \(\epsilon\). Write the negative log likelihood and verify that (5.21) is recovered for \(\epsilon=0\).

   Solution

   \(E\)\({}=-\sum_n\{t_n\ln[(1-\epsilon)y_n+\epsilon(1-y_n)]\)\({}+(1-t_n)\ln[\epsilon y_n+(1-\epsilon)(1-y_n)]\}\); at \(\epsilon=0\) the arguments are \(y_n\) and \(1-y_n\), which is (5.21). Bounded loss, hence robust: see Filling the gap 5.3.

5. Exercise 5.5 (★, www). Show that maximising the likelihood of a multiclass network with \(y_k=p(t_k=1\given\mathbf{x})\) is equivalent to minimising the cross-entropy (5.24).

   Solution

   With 1-of-\(K\) targets \(p(\mathbf{t}\given\mathbf{x})=\prod_ky_k^{t_k}\); the log likelihood of i.i.d. data is \(\sum_n\sum_kt_{nk}\ln y_k(\mathbf{x}_n,\mathbf{w})\), whose negative is (5.24). Result 5.3(4).

6. Exercise 5.6 (★, www). Show that the derivative of (5.21) with respect to the activation \(a_k\) of a logistic-sigmoid output unit is \(y_k-t_k\), (5.18).

   Solution

   \(\sigma'=\sigma(1-\sigma)\), so \(\partial E_n/\partial a_k\)\({}=-\{t_k/y_k-(1-t_k)/(1-y_k)\}y_k(1-y_k)\)\({}=-t_k(1-y_k)+(1-t_k)y_k\)\({}=y_k-t_k\). Result 5.4.

7. Exercise 5.7 (★). Show the same for the softmax output and the error (5.24).

   Solution

   \(\partial y_k/\partial a_l=y_k(\delta_{kl}-y_l)\), so \(\partial E_n/\partial a_l\)\({}=-\sum_kt_k(\delta_{kl}-y_l)\)\({}=-t_l+y_l\sum_kt_k\)\({}=y_l-t_l\) since \(\sum_kt_k=1\). Result 5.4.

8. Exercise 5.8 (★). Derive the analogue of \(\sigma'=\sigma(1-\sigma)\) for \(\tanh\).

   Solution

   \(\tanh a=N/D\) with \(N=e^a-e^{-a}\), \(D=e^a+e^{-a}\), \(N'=D\), \(D'=N\): \((N/D)'=(D^2-N^2)/D^2=1-\tanh^2a\) since \(D^2-N^2=4\). This is (5.60), derived in Section 5.3.2.

9. Exercise 5.9 (★, www). Derive the error function for a network with output \(-1\le y\le1\) and targets \(t=+1\) for \(\mathcal{C}_1\), \(t=-1\) for \(\mathcal{C}_2\). What is the appropriate output activation?

   Solution

   Put \(p(\mathcal{C}_1\given\mathbf{x})=(1+y)/2\). Then \(E\)\({}=-\sum_n\{\frac{1+t_n}2\ln\frac{1+y_n}2\)\({}+\frac{1-t_n}2\ln\frac{1-y_n}2\}\). The activation is \(y=\tanh(a/2)=2\sigma(a)-1\) (so that \((1+y)/2=\sigma(a)\)); with this choice \(\partial E_n/\partial a=\tfrac12(y_n-t_n)\). Check: \(\partial E_n/\partial y\)\({}=-\frac{1+t}{2(1+y)}+\frac{1-t}{2(1-y)}\); for \(t=1\) this is \(-1/(1+y)\), and \(dy/da=\tfrac12(1-y^2)\), so \(\partial E_n/\partial a\)\({}=-\tfrac12(1-y)\)\({}=\tfrac12(y-1)\)\({}=\tfrac12(y-t)\); \(t=-1\) similarly. Filling the gap 5.3.

10. Exercise 5.10 (★, www). Putting \(\mathbf{v}=\mathbf{u}_i\) in (5.39), show that \(\mathbf{H}\) is positive definite iff all its eigenvalues are positive.

    Solution

    If \(\mathbf{H}\) is positive definite, \(\mathbf{u}_i^\T\mathbf{H}\mathbf{u}_i\)\({}=\lambda_i\|\mathbf{u}_i\|^2\)\({}=\lambda_i>0\). Conversely, if all \(\lambda_i>0\), then for \(\mathbf{v}=\sum c_i\mathbf{u}_i\ne\mathbf{0}\), \(\mathbf{v}^\T\mathbf{H}\mathbf{v}\)\({}=\sum c_i^2\lambda_i>0\). Result 5.5(2).

11. Exercise 5.11 (★★, www). Show that the contours of the quadratic (5.32) are ellipses aligned with the eigenvectors of \(\mathbf{H}\), with lengths inversely proportional to \(\sqrt{\lambda_i}\).

    Solution

    In the coordinates \(\alpha_i\)\({}=\mathbf{u}_i^\T(\mathbf{w}-\mathbf{w}^\star)\), \(E-E^\star=\tfrac12\sum\lambda_i\alpha_i^2=c\) is \(\sum\alpha_i^2/(2c/\lambda_i)=1\), an ellipsoid with semi-axes \(\sqrt{2c/\lambda_i}\propto\lambda_i^{-1/2}\) along \(\mathbf{u}_i\) (Result 5.5(3)).

12. Exercise 5.12 (★★, www). From the Taylor expansion (5.32) about a stationary point, show that the condition for a local minimum is that \(\mathbf{H}\) be positive definite.

    Solution

    Positive definite \(\Rightarrow\) \(E-E^\star\simeq\tfrac12\sum\lambda_i\alpha_i^2>0\) for small \(\boldsymbol\alpha\ne\mathbf{0}\): a strict minimum. A negative eigenvalue \(\lambda_i<0\) makes \(E\) decrease along \(\mathbf{u}_i\), so no minimum. Hence for the quadratic model "minimum iff positive definite" (only the borderline of a zero eigenvalue needs higher-order terms). Result 5.5(4).

13. Exercise 5.13 (★). Show that the quadratic (5.28) has \(W(W+3)/2\) independent elements.

    Solution

    \(\mathbf{b}\): \(W\); symmetric \(\mathbf{H}\): \(W(W+1)/2\). Sum \(=W(W+3)/2\). Filling the gap 5.4.

14. Exercise 5.14 (★). Verify by Taylor expansion that the \(O(\epsilon)\) terms cancel in the central difference (5.69).

    Solution

    \(f(\pm\epsilon)\)\({}=f\pm\epsilon f'\)\({}+\tfrac12\epsilon^2f''\pm\tfrac16\epsilon^3f'''\)\({}+\dots\), so \([f(\epsilon)-f(-\epsilon)]/(2\epsilon)\)\({}=f'+\tfrac16\epsilon^2f'''+O(\epsilon^4)\). The even terms cancel in the difference. Filling the gap 5.6.

15. Exercise 5.15 (★★). Derive a forward-propagation formalism for the Jacobian instead of the backward one.

    Solution

    For input \(i\): set \(\partial x_{i'}/\partial x_i=\delta_{ii'}\); then in forward order \(\partial a_j/\partial x_i\)\({}=\sum_lw_{jl}\partial z_l/\partial x_i\) and \(\partial z_j/\partial x_i\)\({}=h'(a_j)\partial a_j/\partial x_i\); at outputs \(J_{ki}=f'(a_k)\partial a_k/\partial x_i\) (softmax: combine with (5.76)). One sweep per input (\(D\) sweeps), against \(K\) for the backward method. Result 5.7.

16. Exercise 5.16 (★). Extend the outer-product approximation (5.84) to several outputs.

    Solution

    For \(E=\tfrac12\sum_n\sum_k(y_{nk}-t_{nk})^2\), \(\mathbf{H}\)\({}=\sum_n\sum_k\nabla y_{nk}\nabla y_{nk}^\T\)\({}+\sum_n\sum_k(y_{nk}-t_{nk})\nabla\nabla y_{nk}\); dropping the second term, \(\mathbf{H}\)\({}\simeq\sum_n\sum_k\mathbf{b}_{nk}\mathbf{b}_{nk}^\T\), \(\mathbf{b}_{nk}=\nabla y_{nk}\). Result 5.9(2).

17. Exercise 5.17 (★). For the population error \(E\)\({}=\tfrac12\iint\{y(\mathbf{x},\mathbf{w})\)\({}-t\}^2p(\mathbf{x},t)\), use the fact that the minimiser is \(\E[t\given\mathbf{x}]\) to show \(\partial^2E/\partial w_r\partial w_s\)\({}=\int\frac{\partial y}{\partial w_r}\frac{\partial y}{\partial w_s}p(\mathbf{x})d\mathbf{x}\).

    Solution

    Differentiating twice gives \(\iint\frac{\partial y}{\partial w_r}\frac{\partial y}{\partial w_s}p\)\({}+\iint(y-t)\frac{\partial^2y}{\partial w_r\partial w_s}p\). The \(t\)-integral of the second term is \(\int(y-\E[t\given\mathbf{x}])\frac{\partial^2y}{\partial w_r\partial w_s}p(\mathbf{x})d\mathbf{x}\)\({}=0\) when \(y=\E[t\given\mathbf{x}]\). Result 5.9(5).

18. Exercise 5.18 (★). Add skip-layer connections to a two-layer network and write the derivatives with respect to the new parameters.

    Solution

    With \(a_k\)\({}=\sum_jw^{(2)}_{kj}z_j+\sum_iw^{\rm s}_{ki}x_i\): \(\partial E_n/\partial w^{\rm s}_{ki}=\delta_kx_i\) (\(\delta_k=y_k-t_k\) for linear outputs); (5.66), (5.67) unchanged. Filling the gap 5.5.

19. Exercise 5.19 (★, www). Derive (5.85), the outer-product Hessian for a single sigmoid output with cross-entropy.

    Solution

    \(\nabla E_n=(y_n-t_n)\nabla a_n\), \(\nabla\nabla E_n\)\({}=y_n(1-y_n)\nabla a_n\nabla a_n^\T\)\({}+(y_n-t_n)\nabla\nabla a_n\); neglecting the last term gives (5.85). Result 5.9(3).

20. Exercise 5.20 (★). Outer-product Hessian for \(K\) softmax outputs with cross-entropy.

    Solution

    \(\mathbf{H}\)\({}\simeq\sum_n\sum_{k,l}y_{nk}(\delta_{kl}-y_{nl})\mathbf{b}_{nk}\mathbf{b}_{nl}^\T\), \(\mathbf{b}_{nk}=\nabla a_{nk}\): from \(\nabla E_n=\sum_k(y_{nk}-t_{nk})\nabla a_{nk}\) and \(\partial y_k/\partial a_l=y_k(\delta_{kl}-y_l)\). Result 5.9(4).

21. Exercise 5.21 (★★★). Extend (5.86) to \(K>1\) outputs and obtain a form allowing (5.87) to absorb outputs and patterns one at a time, so that (5.89) gives the inverse Hessian sequentially.

    Solution

    \(\mathbf{H}_N\)\({}=\sum_n\sum_k\mathbf{b}_{nk}\mathbf{b}_{nk}^\T\); order the \(NK\) pairs \((n,k)\) and set \(\mathbf{H}_{L+1}\)\({}=\mathbf{H}_L\)\({}+\mathbf{b}_{L+1}\mathbf{b}_{L+1}^\T\) with \(\mathbf{b}_{L+1}\) the \(L+1\)th pair, then apply (5.89) \(NK\) times from \(\mathbf{H}_0^{-1}=\alpha^{-1}\mathbf{I}\). For cross-entropy models factor the output-space matrix (\(y(1-y)\), or \(\diag\mathbf{y}-\mathbf{y}\mathbf{y}^\T\)) into rank-one terms first. Result 5.10.

22. Exercise 5.22 (★★). Derive (5.93)–(5.95) by the chain rule.

    Solution

    Differentiate \(\partial E_n/\partial w^{(2)}_{kj}=\delta_kz_j\) and \(\partial E_n/\partial w^{(1)}_{ji}=\delta_jx_i\) using \(\partial\delta_k/\partial a_{k'}=M_{kk'}\), \(\partial a_{k'}/\partial w^{(2)}_{kj}\)\({}=\delta_{kk'}z_j\), \(\partial a_{j}/\partial w^{(1)}_{j'i'}\)\({}=I_{jj'}x_{i'}\). Full steps and a numerical confirmation: Result 5.11.

23. Exercise 5.23 (★★). Include skip-layer connections in the exact Hessian of Section 5.4.5.

    Solution

    (5.93)–(5.95) are unchanged; new blocks: skip–skip \(x_ix_{i'}M_{kk'}\); skip–second layer \(x_iz_jM_{kk'}\); skip–first layer \(x_ix_{i'}h'(a_j)\sum_{k'}M_{kk'}w^{(2)}_{k'j}\). Result 5.11.

24. Exercise 5.24 (★). Verify that the network (5.113), (5.114) is invariant under (5.115) with the weight changes (5.116), (5.117), and the output change (5.118) is produced by (5.119), (5.120).

    Solution

    \(\sum_i\frac{w_{ji}}a(ax_i+b)+w_{j0}\)\({}-\frac ba\sum_iw_{ji}\)\({}=\sum_iw_{ji}x_i+w_{j0}\), so each hidden activation is unchanged; \(\sum_jcw_{kj}z_j+cw_{k0}+d=cy_k+d\). Result 5.12.

25. Exercise 5.25 (★★★, www). For the quadratic (5.195) and gradient descent from the origin, show \(w^{(\tau)}_j=\{1-(1-\rho\eta_j)^\tau\}w^\star_j\), convergence for \(|1-\rho\eta_j|<1\), the limits (5.199), (5.200), the analogy \(\lambda\leftrightarrow(\rho\tau)^{-1}\), and that the effective number of parameters grows.

    Solution

    \(\nabla E=\mathbf{H}(\mathbf{w}-\mathbf{w}^\star)\) so \(w^{(\tau)}_j-w_j^\star\)\({}=(1-\rho\eta_j)(w^{(\tau-1)}_j-w_j^\star)\) and, from \(w^{(0)}=0\), \(w^{(\tau)}_j=\{1-(1-\rho\eta_j)^\tau\}w_j^\star\). The rest (limits via \((1-\rho\eta)^\tau\simeq e^{-\rho\tau\eta}\); ridge factor \(\eta_j/(\eta_j+\lambda)\); \(\gamma(\tau)=\sum_j\{1-(1-\rho\eta_j)^\tau\}\) increasing) is in Result 5.13.

26. Exercise 5.26 (★★). For tangent propagation with a general feed-forward network, show \(\Omega_n=\tfrac12\sum_k(\mathcal{G}y_k)^2\), derive the forward equations for \(\alpha_j=\mathcal{G}z_j\), \(\beta_j=\mathcal{G}a_j\), the weight derivatives (5.206), and the backpropagation equations for \(\delta_{kr}\) and \(\phi_{kr}\).

    Solution

    \(\mathcal{G}y_k=\sum_iJ_{ki}\tau_i\); \(\alpha_j=h'(a_j)\beta_j\), \(\beta_j=\sum_iw_{ji}\alpha_i\); \(\partial\Omega_n/\partial w_{rs}\)\({}=\sum_k\alpha_k\{\phi_{kr}z_s\)\({}+\delta_{kr}\alpha_s\}\); \(\delta_{kr}=h'(a_r)\sum_lw_{lr}\delta_{kl}\), \(\phi_{kr}\)\({}=h''(a_r)\beta_r\sum_lw_{lr}\delta_{kl}\)\({}+h'(a_r)\sum_lw_{lr}\phi_{kl}\). Derivation: Result 5.14.

27. Exercise 5.27 (★★, www). For additive noise \(\mathbf{x}\to\mathbf{x}+\bm\xi\) (zero mean, unit covariance), follow Section 5.5.5 to obtain the Tikhonov form (5.135).

    Solution

    Expand \(y(\mathbf{x}+\bm\xi)\) to second order, average with \(\E[\bm\xi\bm\xi^\T]=\mathbf{I}\): \(\E\{y(\mathbf{x}+\bm\xi)-t\}^2\)\({}=(y-t)^2+\|\nabla y\|^2+(y-t)\nabla^2y\); integrating over \(t\), the last term carries \(y-\E[t\given\mathbf{x}]=O(\xi^2)\) and is dropped, leaving \(\Omega\)\({}=\tfrac12\int\|\nabla y\|^2p(\mathbf{x})d\mathbf{x}\). Result 5.15.

28. Exercise 5.28 (★, www). How must backpropagation change when several weights are constrained to be equal (convolutional networks)?

    Solution

    The error depends on the shared value \(\omega\), so \(\partial E/\partial\omega\) is the sum of the ordinary derivatives \(\delta_jz_i\) over all links in the tied set; update the single parameter. Filling the gap 5.5.

29. Exercise 5.29 (★, www). Verify (5.141).

    Solution

    \(\partial\Omega/\partial w_i\)\({}=-S_i^{-1}\sum_j\pi_j\partial N_{ij}/\partial w_i\)\({}=\sum_j\gamma_j(w_i)(w_i-\mu_j)/\sigma_j^2\). Result 5.17.

30. Exercise 5.30 (★). Verify (5.142).

    Solution

    \(\partial N_{ij}/\partial\mu_j\)\({}=N_{ij}(w_i-\mu_j)/\sigma_j^2\), so \(\partial\Omega/\partial\mu_j\)\({}=-\sum_i\gamma_j(w_i)(w_i-\mu_j)/\sigma_j^2\)\({}=\sum_i\gamma_j(w_i)(\mu_j-w_i)/\sigma_j^2\). Result 5.17.

31. Exercise 5.31 (★). Verify (5.143).

    Solution

    \(\partial\ln N_{ij}/\partial\sigma_j\)\({}=-1/\sigma_j+(w_i-\mu_j)^2/\sigma_j^3\), hence \(\partial\Omega/\partial\sigma_j\)\({}=\sum_i\gamma_j(w_i)\{1/\sigma_j\)\({}-(w_i-\mu_j)^2/\sigma_j^3\}\). Result 5.17.

32. Exercise 5.32 (★★). Show \(\partial\pi_k/\partial\eta_j\)\({}=\delta_{jk}\pi_j-\pi_j\pi_k\) for the softmax (5.146) and then derive (5.147) using \(\sum_k\gamma_k(w_i)=1\).

    Solution

    Quotient rule for the first part. Then \(\partial\Omega/\partial\eta_j\)\({}=\sum_k(-\sum_i\gamma_k(w_i)/\pi_k)(\delta_{jk}\pi_j-\pi_j\pi_k)\)\({}=-\sum_i\gamma_j(w_i)\)\({}+\pi_j\sum_i\sum_k\gamma_k(w_i)\)\({}=\sum_i\{\pi_j-\gamma_j(w_i)\}\). Result 5.17.

33. Exercise 5.33 (★). Write the forward kinematics of the two-link arm of Figure 5.18 (origin at the attachment point of the lower arm).

    Solution

    \(x_1=L_1\cos\theta_1+L_2\cos(\theta_1+\theta_2)\), \(x_2=L_1\sin\theta_1+L_2\sin(\theta_1+\theta_2)\), where \(\theta_1\) is the angle of the first link from the \(x_1\)-axis and \(\theta_2\) the angle of the second relative to the first. Inverse: with \(r^2=x_1^2+x_2^2\), \(\cos\theta_2=(r^2-L_1^2-L_2^2)/(2L_1L_2)\), giving \(\theta_2=\pm\arccos(\cdot)\) (elbow up and elbow down, two solutions when \(|L_1-L_2|\({}=\operatorname{atan2}(x_2,x_1)\)\({}-\operatorname{atan2}(L_2\sin\theta_2,L_1+L_2\cos\theta_2)\). The two solutions are mirror images across the shoulder–end-effector line, and their average does not reach the target (Filling the gap 5.8).

34. Exercise 5.34 (★, www). Derive (5.155).

    Solution

    With \(\partial\pi_l/\partial a^\pi_k\)\({}=\pi_l(\delta_{lk}-\pi_k)\): \(\partial E_n/\partial a^\pi_k\)\({}=-\sum_l\gamma_l(\delta_{lk}-\pi_k)\)\({}=\pi_k-\gamma_k\). Result 5.18.

35. Exercise 5.35 (★). Derive (5.156).

    Solution

    \(\partial N_k/\partial\mu_{kl}\)\({}=N_k(t_l-\mu_{kl})/\sigma_k^2\); then \(\partial E_n/\partial a^\mu_{kl}\)\({}=\gamma_{nk}(\mu_{kl}-t_{nl})/\sigma_k^2\). Result 5.18.

36. Exercise 5.36 (★). Derive (5.157).

    Solution

    \(\partial N_k/\partial a^\sigma_k\)\({}=N_k(-L+\|\mathbf{t}-\bm\mu_k\|^2/\sigma_k^2)\) because \(\sigma_k=e^{a^\sigma_k}\); hence \(\partial E_n/\partial a^\sigma_k\)\({}=\gamma_{nk}(L-\|\mathbf{t}_n-\bm\mu_k\|^2/\sigma_k^2)\). Result 5.18.

37. Exercise 5.37 (★). Verify (5.158) and (5.160).

    Solution

    Mean: \(\sum_k\pi_k\bm\mu_k\). Variance: split \(\mathbf{t}-\bar{\mathbf{t}}\)\({}=(\mathbf{t}-\bm\mu_k)\)\({}+(\bm\mu_k-\bar{\mathbf{t}})\) inside each component; the cross term has zero mean; \(\E_k\|\mathbf{t}-\bm\mu_k\|^2=L\sigma_k^2\) (\(=\sigma_k^2\) for the book's scalar case). Result 5.19.

38. Exercise 5.38 (★). Using (2.115), derive the predictive distribution (5.172) for the Laplace-approximated Bayesian network.

    Solution

    Marginal of the linear-Gaussian pair (5.167), (5.171): \(\N(t\given y_{\rm MAP},\beta^{-1}+\mathbf{g}^\T\mathbf{A}^{-1}\mathbf{g})\). Result 5.20.

39. Exercise 5.39 (★, www). Use the Laplace result (4.135) to show the evidence is approximated by (5.175).

    Solution

    \(\int e^{-E(\mathbf{w})}d\mathbf{w}\)\({}\simeq e^{-E(\mathbf{w}_{\rm MAP})}(2\pi)^{W/2}|\mathbf{A}|^{-1/2}\), multiplied by the normalisers \((\beta/2\pi)^{N/2}(\alpha/2\pi)^{W/2}\); the \(W\ln2\pi\) terms cancel. Result 5.21.

40. Exercise 5.40 (★, www). Outline the changes to Section 5.7.3 for multiclass networks with softmax outputs.

    Solution

    Likelihood \(\sum_n\sum_kt_{nk}\ln y_{nk}\); same prior; \(\mathbf{H}\) from the softmax cross-entropy (exact with \(M_{kk'}=y_k\delta_{kk'}-y_ky_{k'}\), or the outer-product form of Result 5.9(4)); \(\mathbf{A}=\alpha\mathbf{I}+\mathbf{H}\); evidence (5.183) and \(\alpha\) update (5.178) unchanged in form; predictions by linearising each activation \(a_k\) and integrating the softmax against the resulting Gaussian, approximately. See Result 5.22.

41. Exercise 5.41 (★★). By analogy with Sections 5.7.1 and 5.7.2, derive (5.183) for the network with a sigmoid output and cross-entropy.

    Solution

    Apply Laplace to \(\int e^{-E(\mathbf{w})}d\mathbf{w}\) with the regularised cross-entropy (5.182) and the prior normaliser \((\alpha/2\pi)^{W/2}\): \(\ln p(\mathcal{D}\given\alpha)\)\({}\simeq-E(\mathbf{w}_{\rm MAP})\)\({}-\tfrac12\ln|\mathbf{A}|+\tfrac W2\ln\alpha\), without constant (erratum). Result 5.22.

Demonstrations for this chapter

Each demonstration runs in the browser, with seeded random numbers so that a class sees the same pictures, and links back to these notes. The ▶ Demo boxes above open them already set to the case under discussion.

The Python code that produces every figure of this page is code/ch05_neural_networks.py (see the code index).

References

1. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer, New York. Chapter 5, pp. 225–290 (and the official errata).
2. Bishop, C. M. (1992). Exact calculation of the Hessian matrix for the multilayer perceptron. Neural Computation, 4(4), 494–501. doi:10.1162/neco.1992.4.4.494.
3. Bishop, C. M. (1995). Training with noise is equivalent to Tikhonov regularization. Neural Computation, 7(1), 108–116. doi:10.1162/neco.1995.7.1.108.
4. Bishop, C. M. (1994). Mixture density networks. Technical Report NCRG/94/004, Aston University.
5. Chen, A. M., Lu, H. and Hecht-Nielsen, R. (1993). On the geometry of feedforward neural network error surfaces. Neural Computation, 5(6), 910–927. doi:10.1162/neco.1993.5.6.910.
6. Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4), 303–314. doi:10.1007/BF02551274.
7. Funahashi, K. (1989). On the approximate realization of continuous mappings by neural networks. Neural Networks, 2(3), 183–192. doi:10.1016/0893-6080(89)90003-8.
8. Hassibi, B. and Stork, D. G. (1993). Second order derivatives for network pruning: optimal brain surgeon. In Advances in Neural Information Processing Systems 5, 164–171. Morgan Kaufmann.
9. Hinton, G. E. and van Camp, D. (1993). Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, 5–13. doi:10.1145/168304.168306.
10. Hornik, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2), 251–257. doi:10.1016/0893-6080(91)90009-T.
11. Hornik, K., Stinchcombe, M. and White, H. (1989). Multilayer feedforward networks are universal approximators. Neural Networks, 2(5), 359–366. doi:10.1016/0893-6080(89)90020-8.
12. Kůrková, V. and Kainen, P. C. (1994). Functionally equivalent feedforward neural networks. Neural Computation, 6(3), 543–558. doi:10.1162/neco.1994.6.3.543.
13. Le Cun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W. and Jackel, L. D. (1989). Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4), 541–551. doi:10.1162/neco.1989.1.4.541.
14. LeCun, Y., Bottou, L., Bengio, Y. and Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324. doi:10.1109/5.726791.
15. Leen, T. K. (1995). From data distributions to regularization in invariant learning. Neural Computation, 7(5), 974–981. doi:10.1162/neco.1995.7.5.974.
16. Levenberg, K. (1944). A method for the solution of certain non-linear problems in least squares. Quarterly of Applied Mathematics, 2(2), 164–168. doi:10.1090/qam/10666.
17. MacKay, D. J. C. (1992a). A practical Bayesian framework for backpropagation networks. Neural Computation, 4(3), 448–472. doi:10.1162/neco.1992.4.3.448.
18. MacKay, D. J. C. (1992b). The evidence framework applied to classification networks. Neural Computation, 4(5), 720–736. doi:10.1162/neco.1992.4.5.720.
19. Marquardt, D. W. (1963). An algorithm for least-squares estimation of nonlinear parameters. Journal of the Society for Industrial and Applied Mathematics, 11(2), 431–441. doi:10.1137/0111030.
20. Nowlan, S. J. and Hinton, G. E. (1992). Simplifying neural networks by soft weight-sharing. Neural Computation, 4(4), 473–493. doi:10.1162/neco.1992.4.4.473.
21. Pearlmutter, B. A. (1994). Fast exact multiplication by the Hessian. Neural Computation, 6(1), 147–160. doi:10.1162/neco.1994.6.1.147.
22. Rumelhart, D. E., Hinton, G. E. and Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323, 533–536. doi:10.1038/323533a0.
23. Sietsma, J. and Dow, R. J. F. (1991). Creating artificial neural networks that generalize. Neural Networks, 4(1), 67–79. doi:10.1016/0893-6080(91)90033-2.
24. Simard, P. Y., Steinkraus, D. and Platt, J. C. (2003). Best practices for convolutional neural networks applied to visual document analysis. In Seventh International Conference on Document Analysis and Recognition, 958–963. doi:10.1109/ICDAR.2003.1227801.
25. Simard, P., Victorri, B., LeCun, Y. and Denker, J. (1992). Tangent prop: a formalism for specifying selected invariances in an adaptive network. In Advances in Neural Information Processing Systems 4, 895–903. Morgan Kaufmann.

DOIs were checked against Crossref. The numerical statements made in the text (backpropagation against central differences, the exact Hessian blocks, the \(\mathcal{R}\)-operator product, the sequential inverse Hessian and the transformed-data expansion) come from short Python computations written for these notes.