Solutions to exercises from chapter 1 of Neural networks and deep learning¶
Thanks to Michael Nielsen for generously making this great book available for free.
Ex1: Sigmoid neurons simulating perceptrons, part I¶
Exercise: Suppose we take all the weights and biases in a network of perceptrons, and multiply them by a positive constant, $c>0$ . Show that the behaviour of the network doesn't change.
The key insight is that if this modification doesn't change the output of an individual perceptron, then it won't change the output of the network. More specifically, if scaling all weights and biases by a constant doesn't change the output of a perceptron, then all perceptrons in the input layer will produce the same output, and all perceptrons in the next layer will receive the same input — and scaling this input won't change their output, so the perceptrons in the next layer will receive the same input, produce the same output... and so on until we arrive at the output layer producing the same final outputs as before we introduced the scaling term.
If we write a function to calculate the weighted input for a perceptron, everything becomes intuitively obvious:
# Take in weights and biases (w1, w2, b), input values (x1, x2) and a scaling term (c).
# Return the weighted input for a perceptron, with weights and biases scaled by c.
def z(w1, w2, b, x1, x2, c = 1):
return (w1*c)*x1 + (w2*c)*x2 + (b*c)
We easily see that the scaling term $c$ can't change the sign of the result if $c > 0$, because:
$$ (w_1 c) x_1 + (w_2 c) x_2 + (b c) = c(w_1 x_1 + w_2 x_2 + b) $$
Which is readily observed by running the function on a few exemplary scenarios:
scaling_term = 2
unscaled = z(6, 3, -4, 1, 0)
scaled = z(6, 3, -4, 1, 0, scaling_term)
print(f"unscaled: {unscaled}, scaled: {scaled}")
unscaled: 2, scaled: 4
unscaled = z(6, 3, -4, 0, 1)
scaled = z(6, 3, -4, 0, 1, scaling_term)
print(f"unscaled: {unscaled}, scaled: {scaled}")
unscaled: -1, scaled: -2
Because the sign of the result of the weighted input function doesn't change, the output of the perceptron won't change given the standard activation function:
# Return the output of a perceptron for a given weighted input.
def activate(weighted_input):
if weighted_input <= 0:
return 0
else:
return 1
unscaled = z(6, 3, -4, 1, 0)
unscaled_output = activate(unscaled)
scaled = z(6, 3, -4, 1, 0, scaling_term)
scaled_output = activate(scaled)
print(f"unscaled output: {unscaled_output}, scaled output: {scaled_output}")
unscaled = z(6, 3, -4, 0, 1)
unscaled_output = activate(unscaled)
scaled = z(6, 3, -4, 0, 1, scaling_term)
scaled_output = activate(scaled)
print(f"unscaled output: {unscaled_output}, scaled output: {scaled_output}")
unscaled output: 1, scaled output: 1 unscaled output: 0, scaled output: 0
Ex2: Sigmoid neurons simulating perceptrons, part II¶
Exercise: Suppose we have the same setup as the last problem - a network of perceptrons. Suppose also that the overall input to the network of perceptrons has been chosen. We won't need the actual input value, we just need the input to have been fixed. Suppose the weights and biases are such that ${w \cdot x + b \neq 0}$ for the input x to any particular perceptron in the network. Now replace all the perceptrons in the network by sigmoid neurons, and multiply the weights and biases by a positive constant ${c>0}$ . Show that in the limit as ${c \rightarrow \infty}$ the behaviour of this network of sigmoid neurons is exactly the same as the network of perceptrons. How can this fail when ${w \cdot x + b = 0}$ for one of the perceptrons?
Consider the input to the sigmoid function:
$$\sigma(w \cdot x + b)$$
This outputs on the interval $(0, 1)$ no matter what. The more positive the input, the closer the output is to $1$; the more negative the input, the closer the output is to $0$.
$$0 < \sigma(w \cdot x + b) < 1$$
Now start scaling $w$ and $b$ by infinity:
$$\sigma(\infty \cdot w \cdot x + \infty \cdot b)$$
$$\sigma(\infty \cdot (w \cdot x + b))$$
Given the constraint that $w \cdot x + b \neq 0$ for any given $x$, we will have:
$$\sigma(\pm\infty)$$
Recall the definition of the sigmoid function:
$$ \sigma(z) \equiv \frac{1}{1+e^{-z}} $$
In the limit as $z$ approaches positive or negative infinity, this will output $0$ or $1$, just like a perceptron.
$$ \lim_{z \to \pm\infty} \frac{1}{1+e^{-z}} \longrightarrow \frac{1}{1+\{\infty, 0\}} = \{0, 1\} $$
Without the constraint, we could have some situations where $w \cdot x + b = 0$, leading to $\sigma(0) = 0.5$.
$$ \frac{1}{1+e^{-0}} \longrightarrow \frac{1}{1+1} = 0.5 $$
Since a perceptron ought to output one of $ \{ 0, 1 \} $ we cannot claim that a sigmoid neuron is functionally equivalent if it outputs $\{ 0, 0.5, 1 \} $.
Ex3: Determining the bitwise representation of a digit¶
Exercise: There is a way of determining the bitwise representation of a digit by adding an extra layer to the three-layer network above. The extra layer converts the output from the previous layer into a binary representation, as illustrated in the figure below. Find a set of weights and biases for the new output layer. Assume that the first 3 layers of neurons are such that the correct output in the third layer (i.e., the old output layer) has activation at least 0.99 , and incorrect outputs have activation less than 0.01 .
This is straightforwardly illustrated in code:
def dot_product(a, b):
result = 0
for i in range(len(a)):
result += a[i] * b[i]
return result
def unbiased_sigmoid_neuron(weights, inputs):
dp = dot_product(inputs, weights) # Pre-activation.
result = 1.0 / (1.0 + m.exp(-dp)) # Activation.
return result
import math as m
# Takes an output layer of digits and adds another layer to determine binary bits corresponding to that digit.
def digit_bits():
Y = 0.99
N = 0.01
digits = [
#0 1 2 3 4 5 6 7 8 9
[Y, N, N, N, N, N, N, N, N, N], #0
[N, Y, N, N, N, N, N, N, N, N], #1
[N, N, Y, N, N, N, N, N, N, N], #2
[N, N, N, Y, N, N, N, N, N, N], #3
[N, N, N, N, Y, N, N, N, N, N], #4
[N, N, N, N, N, Y, N, N, N, N], #5
[N, N, N, N, N, N, Y, N, N, N], #6
[N, N, N, N, N, N, N, Y, N, N], #7
[N, N, N, N, N, N, N, N, Y, N], #8
[N, N, N, N, N, N, N, N, N, Y], #9
]
W = 1
weights = [
# 0 1 2 3 4 5 6 7 8 9
[-W, W, -W, W, -W, W, -W, W, -W, W], #0001
[-W, -W, W, W, -W, -W, W, W, -W, -W], #0010
[-W, -W, -W, -W, W, W, W, W, -W, -W], #0100
[-W, -W, -W, -W, -W, -W, -W, -W, W, W], #1000
]
# No bias necessary, this alone is enough to do the job, we just take anything above 0.5 as indicating "this bit is active for this digit."
for i in range(10):
binary = ""
for j in range(4):
result = unbiased_sigmoid_neuron(digits[i], weights[j])
binary = str(int(result+0.5)) + binary
print(f"digit {i}: {binary}")
digit_bits()
digit 0: 0000 digit 1: 0001 digit 2: 0010 digit 3: 0011 digit 4: 0100 digit 5: 0101 digit 6: 0110 digit 7: 0111 digit 8: 1000 digit 9: 1001
Ex4: Proving that the gradient is the direction of steepest ascent¶
It can be proved that the choice of ${\Delta v}$ which minimizes ${\nabla C \cdot \Delta v}$ is ${\Delta v = - \eta \nabla C}$, where ${\eta = \epsilon / \|\nabla C\|}$ is determined by the size constraint ${\|\Delta v\| = \epsilon}$. So gradient descent can be viewed as a way of taking small steps in the direction which does the most to immediately decrease $C$.
Exercise: Prove the assertion of the last paragraph. Hint: If you're not already familiar with the Cauchy-Schwarz inequality, you may find it helpful to familiarize yourself with it.
By the Cauchy-Schwarz inequality, we know that:
$$ | \vec{u} \cdot \vec{v} | \leq \| \vec{u} \| \|\vec{v} \|$$
For non-zero vectors, it also holds that equality is attained if and only if there is some $ t $ such that ${ \vec{v} = t \vec{u} }$, meaning:
$$ | \vec{u} \cdot t\vec{u} | = \| \vec{u} \| \| t\vec{u} \|$$
Which can be restated as:
$$ \vec{u} \cdot t\vec{u} = \begin{cases} \| \vec{u} \| \| t \vec{u}\| (-1) & \longrightarrow t < 0 \\ \| \vec{u} \| \| t \vec{u}\| & \longrightarrow t \geq 0 \end{cases} $$
These represent the lower and upper bounds of ${ \vec{u} \cdot \vec{v} }$, respectively.
We're trying to minimize ${ \Delta C \approx \nabla C \cdot \Delta v }$, which tends to hold when $ \Delta v $ is very small. From the above it follows that:
$$ |\nabla C \cdot \Delta v | \leq \| \nabla C \| \| \Delta v \| $$
Given a small ${ \eta > 0 }$ we can state our lower bound as:
$$ \| \nabla C \| \| -\eta \nabla C \| (-1) = \nabla C \cdot (-\eta) \nabla C $$
So for any given $ \nabla C $, we expect to minimize $ \Delta C $ when ${ \Delta v = - \eta \nabla C }$.
To determine an appropriate $ \eta $, we first constrain the magnitude of $ \Delta v $ such that ${ \| \Delta v \| = \epsilon }$ for some small fixed ${ \epsilon > 0 }$. Then because ${ \| \Delta v \| = \| - \eta \nabla C \| }$, we can see that:
$$ \begin{align*} \| - \eta \nabla C \| &= \epsilon \\ \eta \| \nabla C \| &= \epsilon \\ \eta &= \frac{\epsilon}{\| \nabla C \|} \end{align*} $$
Ex5: Gradient descent of one variable¶
Exercise: I explained gradient descent when C is a function of two variables, and when it's a function of more than two variables. What happens when C is a function of just one variable? Can you provide a geometric interpretation of what gradient descent is doing in the one-dimensional case?
When $ C $ is a function of one variable, the gradient descent algorithm doesn't change, you're just finding the minimum in a two dimensional space. "Find the bottom of the parabola" is the basic idea.
Ex6: Online Learning¶
Exercise: An extreme version of gradient descent is to use a mini-batch size of just 1. That is, given a training input, $x$, we update our weights and biases according to the rules ${w_k \rightarrow w_k' = w_k - \eta \partial C_x / \partial w_k}$ and ${b_l \rightarrow b_l' = b_l - \eta \partial C_x / \partial b_l}$. Then we choose another training input, and update the weights and biases again. And so on, repeatedly. This procedure is known as online, on-line, or incremental learning. In online learning, a neural network learns from just one training input at a time (just as human beings do). Name one advantage and one disadvantage of online learning, compared to stochastic gradient descent with a mini-batch size of, say, 20.
Compared against stochastic gradient descent with a minibatch size of 20, online learning will better adjust to evolving trends in the data. On the other hand, it will handle outliers a lot worse.
One way in which I personally look at gradient descent is through the lens of a digital filter. The moving average low-pass filter is one of the simplest ways to "smooth out" a noisy signal. Generally speaking, the greater the number of samples in the signal you average together — i.e. the larger the window size — the smoother the signal gets. The smaller the window, the less smoothing/filtering is happening. With a window size of 1, well, there's no filtering happening at all. That means that spikes in the input get translated directly to the output.
From a machine learning perspective, the minibatch size dictates the amount of filtering/smoothing that's going on. The smaller the minibatch size, the greater the impact of any outliers ("noise") on the model. It makes intuitive sense: if you have a million samples that are mostly clustered within some small space, and then a few massive outliers, those outliers will get smoothed/filtered out when their contribution to the error is averaged in with everything else.
With a minibatch, this smoothing is reduced, but still present. With online learning, it isn't. Hence when the model encounters an outlier, it's likely to go wrong and stay wrong for a while — the number of good samples needed to get the model back on track will be directly proportional to the degree to which the outlier deviates from the rest.
Ex7: Equivalence between equations 22 and 4¶
Exercise: Write out Equation (22) in component form, and verify that it gives the same result as the rule (4) for computing the output of a sigmoid neuron.
$a' = \sigma(w \cdot a + b)$
$a'_j = \sigma(w_j \cdot a + b_j)$
$a'_j = \sigma(\sum_k w_{jk} a_k + b_j)$
$a'_j = {1 / (1 + \exp(-\sum_k w_{jk} a_k - b_j))}$
Ex8: A two-layer neural network¶
Exercise: Try creating a network with just two layers - an input and an output layer, no hidden layer - with 784 and 10 neurons, respectively. Train the network using stochastic gradient descent. What classification accuracy can you achieve?
The code below is adapted from Michael's text to work with Python 3. After several runs, the best accuracy I could achieve was around 91%, although the figure bounced around wildly, with one run finishing at around 60-something percent.
import numpy as np
rng = np.random.default_rng()
class Network(object):
def __init__(self, sizes):
self.num_layers = len(sizes)
self.sizes = sizes
self.biases = [rng.standard_normal((y, 1)) for y in sizes[1:]]
self.weights = [rng.standard_normal((y, x)) for x,y in zip(sizes[:-1], sizes[1:])]
network = Network([3, 5, 4])
# Raw input list of number of units in each layer
network.sizes
[3, 5, 4]
# Biases per layer, skipping the first layer which is input. Note that these are column vectors.
network.biases
[array([[-1.07198418],
[ 0.33563292],
[-1.45178819],
[-1.28336643],
[ 0.03031064]]),
array([[-0.08286307],
[ 0.14189407],
[ 0.25386069],
[ 1.13527978]])]
# Matrices which take D units from previous layer and output N units.
# So each layer is an NxD matrix.
# N = Number of units in *this* layer.
# D = Number of units in *previous* layer.
# The zip trick in the constructor does this for us.
network.weights
[array([[-0.60291218, 0.94769696, -0.29207766],
[-0.49815986, 1.45154906, 0.86846283],
[ 0.7248065 , -0.78578538, -0.19009134],
[-0.42983594, 0.41917942, 0.81053381],
[ 0.70665528, 0.42502245, 1.11496938]]),
array([[-0.28121247, -0.34703241, -1.56195391, -0.81001366, -1.28788254],
[-0.27383183, 0.06569628, 1.0284025 , -0.64158846, -0.92591406],
[-0.48960811, -0.12535807, 0.52961716, 0.94489982, -1.26546388],
[ 0.68333554, -0.3739202 , -0.38042004, 0.66598009, -0.01963056]])]
"""
mnist_loader
~~~~~~~~~~~~
A library to load the MNIST image data. For details of the data
structures that are returned, see the doc strings for ``load_data``
and ``load_data_wrapper``. In practice, ``load_data_wrapper`` is the
function usually called by our neural network code.
"""
import pickle
import gzip
def load_data():
"""Return the MNIST data as a tuple containing the training data,
the validation data, and the test data.
The ``training_data`` is returned as a tuple with two entries.
The first entry contains the actual training images. This is a
numpy ndarray with 50,000 entries. Each entry is, in turn, a
numpy ndarray with 784 values, representing the 28 * 28 = 784
pixels in a single MNIST image.
The second entry in the ``training_data`` tuple is a numpy ndarray
containing 50,000 entries. Those entries are just the digit
values (0...9) for the corresponding images contained in the first
entry of the tuple.
The ``validation_data`` and ``test_data`` are similar, except
each contains only 10,000 images.
This is a nice data format, but for use in neural networks it's
helpful to modify the format of the ``training_data`` a little.
That's done in the wrapper function ``load_data_wrapper()``, see
below.
"""
# mnist_modern.pkl.gz should work with modern Python, and is adapted from
# mnist.pkl.gz, which comes from:
# https://github.com/MichalDanielDobrzanski/DeepLearningPython
# and is distributed under the MIT license.
with gzip.open('mnist_modern.pkl.gz', 'rb') as f:
data = np.load(f, allow_pickle=True, encoding='latin1')
training_data, validation_data, test_data = data
return (training_data, validation_data, test_data)
def load_data_wrapper():
"""Return a tuple containing ``(training_data, validation_data,
test_data)``. Based on ``load_data``, but the format is more
convenient for use in our implementation of neural networks.
In particular, ``training_data`` is a list containing 50,000
2-tuples ``(x, y)``. ``x`` is a 784-dimensional numpy.ndarray
containing the input image. ``y`` is a 10-dimensional
numpy.ndarray representing the unit vector corresponding to the
correct digit for ``x``.
``validation_data`` and ``test_data`` are lists containing 10,000
2-tuples ``(x, y)``. In each case, ``x`` is a 784-dimensional
numpy.ndarry containing the input image, and ``y`` is the
corresponding classification, i.e., the digit values (integers)
corresponding to ``x``.
Obviously, this means we're using slightly different formats for
the training data and the validation / test data. These formats
turn out to be the most convenient for use in our neural network
code."""
tr_d, va_d, te_d = load_data()
training_inputs = [np.reshape(x, (784, 1)) for x in tr_d[0]]
training_results = [vectorized_result(y) for y in tr_d[1]]
training_data = list(zip(training_inputs, training_results)) # Convert to list
validation_inputs = [np.reshape(x, (784, 1)) for x in va_d[0]]
validation_data = list(zip(validation_inputs, va_d[1])) # Convert to list
test_inputs = [np.reshape(x, (784, 1)) for x in te_d[0]]
test_data = list(zip(test_inputs, te_d[1])) # Convert to list
return (training_data, validation_data, test_data)
def vectorized_result(j):
"""Return a 10-dimensional unit vector with a 1.0 in the jth
position and zeroes elsewhere. This is used to convert a digit
(0...9) into a corresponding desired output from the neural
network."""
e = np.zeros((10, 1))
e[j] = 1.0
return e
"""
network.py
~~~~~~~~~~
A module to implement the stochastic gradient descent learning
algorithm for a feedforward neural network. Gradients are calculated
using backpropagation. Note that I have focused on making the code
simple, easily readable, and easily modifiable. It is not optimized,
and omits many desirable features.
"""
#### Libraries
# Standard library
import random
class Network(object):
def __init__(self, sizes):
"""The list ``sizes`` contains the number of neurons in the
respective layers of the network. For example, if the list
was [2, 3, 1] then it would be a three-layer network, with the
first layer containing 2 neurons, the second layer 3 neurons,
and the third layer 1 neuron. The biases and weights for the
network are initialized randomly, using a Gaussian
distribution with mean 0, and variance 1. Note that the first
layer is assumed to be an input layer, and by convention we
won't set any biases for those neurons, since biases are only
ever used in computing the outputs from later layers."""
self.num_layers = len(sizes)
self.sizes = sizes
self.biases = [np.random.randn(y, 1) for y in sizes[1:]]
self.weights = [np.random.randn(y, x)
for x, y in zip(sizes[:-1], sizes[1:])]
def feedforward(self, a):
"""Return the output of the network if ``a`` is input."""
for b, w in zip(self.biases, self.weights):
a = sigmoid(np.dot(w, a)+b)
return a
def SGD(self, training_data, epochs, mini_batch_size, eta,
test_data=None):
"""Train the neural network using mini-batch stochastic
gradient descent. The ``training_data`` is a list of tuples
``(x, y)`` representing the training inputs and the desired
outputs. The other non-optional parameters are
self-explanatory. If ``test_data`` is provided then the
network will be evaluated against the test data after each
epoch, and partial progress printed out. This is useful for
tracking progress, but slows things down substantially."""
if test_data: n_test = len(test_data)
n = len(training_data)
for j in range(epochs):
random.shuffle(training_data)
mini_batches = [
training_data[k:k+mini_batch_size]
for k in range(0, n, mini_batch_size)]
for mini_batch in mini_batches:
self.update_mini_batch(mini_batch, eta)
if test_data:
print("Epoch {0}: {1} / {2}".format(
j, self.evaluate(test_data), n_test))
else:
print("Epoch {0} complete".format(j))
def update_mini_batch(self, mini_batch, eta):
"""Update the network's weights and biases by applying
gradient descent using backpropagation to a single mini batch.
The ``mini_batch`` is a list of tuples ``(x, y)``, and ``eta``
is the learning rate."""
nabla_b = [np.zeros(b.shape) for b in self.biases]
nabla_w = [np.zeros(w.shape) for w in self.weights]
for x, y in mini_batch:
delta_nabla_b, delta_nabla_w = self.backprop(x, y)
nabla_b = [nb+dnb for nb, dnb in zip(nabla_b, delta_nabla_b)]
nabla_w = [nw+dnw for nw, dnw in zip(nabla_w, delta_nabla_w)]
self.weights = [w-(eta/len(mini_batch))*nw
for w, nw in zip(self.weights, nabla_w)]
self.biases = [b-(eta/len(mini_batch))*nb
for b, nb in zip(self.biases, nabla_b)]
def backprop(self, x, y):
"""Return a tuple ``(nabla_b, nabla_w)`` representing the
gradient for the cost function C_x. ``nabla_b`` and
``nabla_w`` are layer-by-layer lists of numpy arrays, similar
to ``self.biases`` and ``self.weights``."""
nabla_b = [np.zeros(b.shape) for b in self.biases]
nabla_w = [np.zeros(w.shape) for w in self.weights]
# feedforward
activation = x
activations = [x] # list to store all the activations, layer by layer
zs = [] # list to store all the z vectors, layer by layer
for b, w in zip(self.biases, self.weights):
z = np.dot(w, activation)+b
zs.append(z)
activation = sigmoid(z)
activations.append(activation)
# backward pass
delta = self.cost_derivative(activations[-1], y) * \
sigmoid_prime(zs[-1])
nabla_b[-1] = delta
nabla_w[-1] = np.dot(delta, activations[-2].transpose())
# Note that the variable l in the loop below is used a little
# differently to the notation in Chapter 2 of the book. Here,
# l = 1 means the last layer of neurons, l = 2 is the
# second-last layer, and so on. It's a renumbering of the
# scheme in the book, used here to take advantage of the fact
# that Python can use negative indices in lists.
for l in range(2, self.num_layers):
z = zs[-l]
sp = sigmoid_prime(z)
delta = np.dot(self.weights[-l+1].transpose(), delta) * sp
nabla_b[-l] = delta
nabla_w[-l] = np.dot(delta, activations[-l-1].transpose())
return (nabla_b, nabla_w)
def evaluate(self, test_data):
"""Return the number of test inputs for which the neural
network outputs the correct result. Note that the neural
network's output is assumed to be the index of whichever
neuron in the final layer has the highest activation."""
test_results = [(np.argmax(self.feedforward(x)), y)
for (x, y) in test_data]
return sum(int(x == y) for (x, y) in test_results)
def cost_derivative(self, output_activations, y):
"""Return the vector of partial derivatives for the output activations."""
return (output_activations-y)
#### Miscellaneous functions
def sigmoid(z):
"""The sigmoid function."""
return 1.0/(1.0+np.exp(-z))
def sigmoid_prime(z):
"""Derivative of the sigmoid function."""
return sigmoid(z)*(1-sigmoid(z))
training_data, validation_data, test_data = load_data_wrapper()
net = Network([784, 10])
net.SGD(training_data, 30, 10, 3.0, test_data=test_data)
Epoch 0: 8411 / 10000 Epoch 1: 8405 / 10000 Epoch 2: 8421 / 10000 Epoch 3: 8396 / 10000 Epoch 4: 8398 / 10000 Epoch 5: 8400 / 10000 Epoch 6: 8427 / 10000 Epoch 7: 8400 / 10000 Epoch 8: 8418 / 10000 Epoch 9: 8428 / 10000 Epoch 10: 8419 / 10000 Epoch 11: 8426 / 10000 Epoch 12: 8418 / 10000 Epoch 13: 8415 / 10000 Epoch 14: 8429 / 10000 Epoch 15: 8429 / 10000 Epoch 16: 8400 / 10000 Epoch 17: 8431 / 10000 Epoch 18: 8411 / 10000 Epoch 19: 8422 / 10000 Epoch 20: 8419 / 10000 Epoch 21: 8445 / 10000 Epoch 22: 8421 / 10000 Epoch 23: 8429 / 10000 Epoch 24: 8422 / 10000 Epoch 25: 8442 / 10000 Epoch 26: 8429 / 10000 Epoch 27: 8482 / 10000 Epoch 28: 8463 / 10000 Epoch 29: 8468 / 10000