Backpropagation Neural Networks
Dear reader, the code in this chapter is old but I include it from a feeling of personal nostalgia. I used an early version of this simple code in the mid-1980s to prototype the C++ code that I wrote for a bomb detector my company built for the FAA. Hopefully my nostalgia is something interesting to you.
Let’s start with an overview of how these networks work and then fill in more detail later. Backpropagation networks are trained by applying training inputs to the network input layer, propagate values through the network to the output neurons, compare the errors (or differences) between these propagated output values and the training data output values. These output errors are backpropagated though the network and the magnitude of backpropagated errors are used to adjust the weights in the network.
The source code for the neural network example is the file src/code_snippets_for_book/backprop_neural_network.lisp. The screen shots below were produced by an earlier version of the program that used a plotlib package and this plotting code is not included in the listings here.
We will use the following diagram to make this process more clear. There are four weights in this very simple network:
- W1,1 is the floating point number representing the connection strength between input_neuron1 and output_neuron1
- W2,1 connects input_neuron2 to output_neuron1
- W1,2 connects input_neuron1 to output_neuron2
- W2,2 connects input_neuron2 to output_neuron2
Before any training the weight values are all small random numbers.
Consider a training data element where the input neurons have values [0.1, 0.9] and the desired output neuron values are [0.9 and 0.1], that is flipping the input values. If the propagated output values for the current weights are [0.85, 0.5] then the value of the first output neuron has a small error abs(0.85 - 0.9) which is 0.05. However the propagated error of the second output neuron is high: abs(0.5 - 0.1) which is 0.4. Informally we see that the weights feeding input output neuron 1 (W1,1 and W2,1) don’t need to be changed much but the neuron that feeding input neuron 2 (W1,2 and W2,2) needs modification (the value of W2,2 is too large).
Of course, we would never try to manually train a network like this but it is important to have at least an informal understanding of how weights connect the flow of value (we will call this activation value later) between neurons.
In this neural network see in the first figure we have four weights connecting the input and output neurons. Think of these four weights forming a four-dimensional space where the range in each dimension is constrained to small positive and negative floating point values. At any point in this “weight space”, the numeric values of the weights defines a model that maps the inputs to the outputs. The error seen at the output neurons is accumulated for each training example (applied to the input neurons). The training process is finding a point in this four-dimensional space that has low errors summed across the training data. We will use gradient descent to start with a random point in the four-dimensional space (i.e., an initial random set of weights) and move the point towards a local minimum that represents the weights in a model that is (hopefully) “good enough” at representing the training data.
This process is simple enough but there are a few practical considerations:
- Sometimes the accumulated error at a local minimum is too large even after many training cycles and it is best to just restart the training process with new random weights.
- If we don’t have enough training data then the network may have enough memory capacity to memorize the training examples. This is not what we want: we want a model with just enough memory capacity (as represented by the number of weights) to form a generalized predictive model, but not so specific that it just memorizes the training examples. The solution is to start with small networks (few hidden neurons) and increase the number of neurons until the training data can be learned. In general, having a lot of training data is good and it is also good to use as small a network as possible.
In practice using backpropagation networks is an iterative process of experimenting with the size of a network.
An earlier version of the example program (in the file backprop_neural_network.lisp) used the plotting library developed earlier to visualize neuron activation and connecting weight values while the network trains; the screen shots below show that visualization.
The following three screen shots illustrate the process of starting with random weights, getting random outputs during initial training, and as delta weights are used to adjust the weights in a network, then the training examples are learned:
In the last figure the initial weights are random so we get random mid-range values at the output neurons.
As we start to train the network, adjusting the weights, we start to see variation in the output neurons as a function of what the inputs are.
In the last figure the network is trained sufficiently well to map inputs [0, 0, 0, 1] to output values that are approximately [0.8, 0.2, 0.2, 0.3] which is close to the expected value [1, 0, 0, 0].
The activation values of individual neurons are limited to the range [0, 1] by first calculating their values based on the sum activation values of neurons in the previous layer times the values of the connecting weights and then using the Sigmoid function to map the sums to the desired range. The Sigmoid function and the derivative of the Sigmoid function (dSigmoid) look like:
Here are the definitions of these functions:
1 (defun Sigmoid (x)
2 (/ 1.0 (+ 1.0 (exp (- x)))))
3
4 (defun dSigmoid (x)
5 (let ((temp (Sigmoid x)))
6 (* temp (- 1.0 temp))))
The function NewDeltaNetwork creates a new neural network object. This code allocates storage for input, hidden, output layers (I sometimes refer to neuron layers as “slabs”), and the connection weights. Connection weights are initialized to small random values.
1 ; (NewDeltaNetwork sizeList)
2 ; Args: sizeList = list of sizes of slabs. This also defines
3 ; the number of slabs in the network.
4 ; (e.g., '(10 5 4) ==> a 3-slab network with 10
5 ; input neurons, 5 hidden neurons, and 4 output
6 ; neurons).
7 ;
8 ; Returned value = a list describing the network:
9 ; (nLayers sizeList
10 ; (activation-array[1] .. activation-array[nLayers])
11 ; (weight-array[2] .. weight-array[nLayers])
12 ; (sum-of-products[2] .. sum-of-products[nLayers[nLayers])
13 ; (back-prop-error[2] .. back-prop-error[nLayers]))
14 ; (old-delta-weights[2] .. for momentum term
15 ;
16 (defun NewDeltaNetwork (sizeList
17 &aux (numLayers (length sizeList))
18 (alpha 0.5)
19 (beta 0.25)
20 a-list s-list w-list dw-list d-list old-dw-list)
21
22 ;;
23 ; Allocate storage for activations, sum of products, back
24 ; propagation errors, and weights:
25 ;;
26 (dotimes (n numLayers)
27 (push (make-array (nth n sizeList)
28 :initial-element 0.0)
29 a-list))
30 (setq a-list (reverse a-list))
31
32 (dotimes (n (- numLayers 1))
33 (push (make-array (nth (+ n 1) sizeList)
34 :initial-element 0.0)
35 s-list))
36 (setq s-list (reverse s-list))
37
38 (dotimes (n (- numLayers 1))
39 (push (make-array (nth (+ n 1) sizeList)
40 :initial-element 0.0)
41 d-list))
42 (setq d-list (reverse d-list))
43
44 (dotimes (n (- numLayers 1))
45 (push (make-array (list (nth n sizeList) (nth (+ n 1) sizeList))
46 :initial-element 0.0)
47 w-list))
48 (setq w-list (reverse w-list))
49
50 (dotimes (n (- numLayers 1))
51 (push (make-array (list (nth n sizeList) (nth (+ n 1) sizeList))
52 :initial-element 0.0)
53 dw-list))
54 (setq dw-list (reverse dw-list))
55
56 (dotimes (n (- numLayers 1))
57 (push (make-array (list (nth n sizeList) (nth (+ n 1) sizeList))
58 :initial-element 0.0)
59 old-dw-list))
60 (setq old-dw-list (reverse old-dw-list))
61
62 ;;
63 ; Initialize values for all activations:
64 ;;
65 (mapc
66 (lambda (x)
67 (let ((num (array-dimension x 0)))
68 (dotimes (n num)
69 (setf (aref x n) (frandom 0.01 0.1)))))
70 a-list)
71
72 ;;
73 ; Initialize values for all weights:
74 ;;
75 (mapc
76 (lambda (x)
77 (let ((numI (array-dimension x 0))
78 (numJ (array-dimension x 1)))
79 (dotimes (j numJ)
80 (dotimes (i numI)
81 (setf (aref x i j) (frandom -0.5 0.5))))))
82 w-list)
83 (list numLayers sizeList a-list s-list w-list dw-list
84 d-list old-dw-list alpha beta))
In the following listing the function DeltaLearn processes one pass through all of the training data. Function DeltaLearn is called repeatedly until the return value is below a desired error threshold. The main loop over each training example is implemented in lines 177-272. Inside this outer loop there are two phases of training for each training example: a forward pass propagating activation from the input neurons to the output neurons via any hidden layers (lines 191-209) and then the backpropagation of output errors to accumulate the delta weights (lines 210-272). After all of the training examples have been processed, the weights are updated (lines 274-294):
1 ;;
2 ; Utility function for training a delta rule neural network.
3 ; The first argument is a network definition (as returned from
4 ; NewDeltaNetwork), the second argument is a list of training
5 ; data cases (see the example test functions at the end of this
6 ; file for examples.
7 ;;
8
9 (defun DeltaLearn (netList trainList)
10 (let ((nLayers (car netList))
11 (sizeList (cadr netList))
12 (activationList (caddr netList))
13 (sumOfProductsList (car (cdddr netList)))
14 (weightList (cadr (cdddr netList)))
15 (deltaWeightList (caddr (cdddr netList)))
16 (deltaList (cadddr (cdddr netList)))
17 (oldDeltaWeightList (cadddr (cdddr (cdr netList))))
18 (alpha (cadddr (cdddr (cddr netList))))
19 (beta (cadddr (cdddr (cdddr netList))))
20 (inputs nil)
21 (targetOutputs nil)
22 (iDimension nil)
23 (jDimension nil)
24 (iActivationVector nil)
25 (jActivationVector nil)
26 (n nil)
27 (weightArray nil)
28 (sumOfProductsArray nil)
29 (iDeltaVector nil)
30 (jDeltaVector nil)
31 (deltaWeightArray nil)
32 (oldDeltaWeightArray nil)
33 (sum nil)
34 (iSumOfProductsArray nil)
35 (error nil)
36 (outputError 0)
37 (delta nil)
38 (eida nil)
39 (eidaList nil)
40 (inputNoise 0))
41
42 ;;
43 ; Zero out deltas:
44 ;;
45 (dotimes (n (- nLayers 1))
46 (let* ((dw (nth n deltaList))
47 (len1 (array-dimension dw 0)))
48 (dotimes (i len1)
49 (setf (aref dw i) 0.0))))
50
51 ;;
52 ; Zero out delta weights:
53 ;;
54 (dotimes (n (- nLayers 1))
55 (let* ((dw (nth n deltaWeightList))
56 (len1 (array-dimension dw 0))
57 (len2 (array-dimension dw 1)))
58 (dotimes (i len1)
59 (dotimes (j len2)
60 (setf (aref dw i j) 0.0)))))
61
62 (setq inputNoise *delta-default-input-noise-value*)
63
64 ;;
65 ; Per-layer learning rates used when accumulating delta weights:
66 ;;
67 (setq eidaList (make-list (- nLayers 1) :initial-element alpha))
68
69 ;;
70 ; Main loop on training examples:
71 ;;
72 (dolist (tl trainList)
73
74 (setq inputs (car tl))
75 (setq targetOutputs (cadr tl))
76
77 (if *delta-rule-debug-flag*
78 (print (list "Current targets:" targetOutputs)))
79
80 (setq iDimension (car sizeList)) ; get the size of the input slab
81 (setq iActivationVector (car activationList)) ; input activations
82 (dotimes (i iDimension) ; copy training inputs to input slab
83 (setf
84 (aref iActivationVector i)
85 (+ (nth i inputs) (frandom (- inputNoise) inputNoise))))
86 ;;
87 ; Propagate activation through all of the slabs:
88 ;;
89 (dotimes (n-1 (- nLayers 1)) ; update layer i to layer flowing to layer j
90 (setq n (+ n-1 1))
91 (setq jDimension (nth n sizeList)) ; get the size of the j'th layer
92 (setq jActivationVector (nth n activationList)) ; activation for slab j
93 (setq weightArray (nth n-1 weightList))
94 (setq sumOfProductsArray (nth n-1 sumOfProductsList))
95 (dotimes (j jDimension) ; process each neuron in slab j
96 (setq sum 0.0) ; init sum of products to zero
97 (dotimes (i iDimension) ; activation from neurons in previous slab
98 (setq
99 sum
100 (+ sum (* (aref weightArray i j) (aref iActivationVector i)))))
101 (setf (aref sumOfProductsArray j) sum) ; save sum of products
102 (setf (aref jActivationVector j) (Sigmoid sum)))
103 (setq iDimension jDimension) ; reset index for next slab pair
104 (setq iActivationVector jActivationVector))
105 ;;
106 ; Activation is spread through the network and sum of products
107 ; calculated. Now modify the weights in the network using back
108 ; error propagation. Start by calculating the error signal for
109 ; each neuron in the output layer:
110 ;;
111 (setq jDimension (nth (- nLayers 1) sizeList)) ; size of last layer
112 (setq jActivationVector (nth (- nLayers 1) activationList))
113 (setq jDeltaVector (nth (- nLayers 2) deltaList))
114 (setq sumOfProductsArray (nth (- nLayers 2) sumOfProductsList))
115 (setq outputError 0)
116 (dotimes (j jDimension)
117 (setq delta (- (nth j targetOutputs) (aref jActivationVector j)))
118 (setq outputError (+ outputError (abs delta)))
119 (setf
120 (aref jDeltaVector j)
121 (+
122 (aref jDeltaVector j)
123 (* delta (dSigmoid (aref sumOfProductsArray j))))))
124 ;;
125 ; Now calculate the backpropagated error signal for all hidden slabs:
126 ;;
127 (dotimes (nn (- nLayers 2))
128 (setq n (- nLayers 3 nn))
129 (setq iDimension (nth (+ n 1) sizeList))
130 (setq iSumOfProductsArray (nth n sumOfProductsList))
131 (setq iDeltaVector (nth n deltaList))
132 (dotimes (i iDimension)
133 (setf (aref iDeltaVector i) 0.0))
134 (setq weightArray (nth (+ n 1) weightList))
135 (dotimes (i iDimension)
136 (setq error 0.0)
137 (dotimes (j jDimension)
138 (setq error
139 (+ error (* (aref jDeltaVector j) (aref weightArray i j)))))
140 (setf
141 (aref iDeltaVector i)
142 (+
143 (aref iDeltaVector i)
144 (* error (dSigmoid (aref iSumOfProductsArray i))))))
145 (setq jDimension iDimension)
146 (setq jDeltaVector iDeltaVector))
147
148 ;;
149 ; Update all delta weights in the network:
150 ;;
151 (setq iDimension (car sizeList))
152 (dotimes (n (- nLayers 1))
153 (setq iActivationVector (nth n activationList))
154 (setq jDimension (nth (+ n 1) sizeList))
155 (setq jDeltaVector (nth n deltaList))
156 (setq deltaWeightArray (nth n deltaWeightList))
157 (setq weightArray (nth n weightList))
158 (setq eida (nth n eidaList))
159
160 (dotimes (j jDimension)
161 (dotimes (i iDimension)
162 (setq delta (* eida (aref jDeltaVector j) (aref iActivationVector i)))
163 (setf
164 (aref DeltaWeightArray i j)
165 (+ (aref DeltaWeightArray i j) delta)))) ; delta weight changes
166
167 (setq iDimension jDimension)))
168
169 ;;
170 ; Update all weights in the network:
171 ;;
172 (setq iDimension (car sizeList))
173 (dotimes (n (- nLayers 1))
174 (setq iActivationVector (nth n activationList))
175 (setq jDimension (nth (+ n 1) sizeList))
176 (setq jDeltaVector (nth n deltaList))
177 (setq deltaWeightArray (nth n deltaWeightList))
178 (setq oldDeltaWeightArray (nth n oldDeltaWeightList))
179 (setq weightArray (nth n weightList))
180 (dotimes (j jDimension)
181 (dotimes (i iDimension)
182 (setf
183 (aref weightArray i j)
184 (+ (aref weightArray i j)
185 (* alpha (aref deltaWeightArray i j))
186 (* beta (aref oldDeltaWeightArray i j))))
187 (setf (aref oldDeltaWeightArray i j) ; save current delta weights
188 (aref deltaWeightArray i j)))) ; ...for next momentum term.
189 (setq iDimension jDimension))
190
191 (/ outputError jDimension)))
The function DeltaRecall in the next listing can be used with a trained network to calculate outputs for new input values:
1 ;;
2 ; Utility for using a trained neural network in the recall mode.
3 ; The first argument to this function is a network definition (as
4 ; returned from NewDeltaNetwork) and the second argument is a list
5 ; of input neuron activation values to drive through the network.
6 ; The output is a list of the calculated activation energy for
7 ; each output neuron.
8 ;;
9 (defun DeltaRecall (netList inputs)
10 (let ((nLayers (car netList))
11 (sizeList (cadr netList))
12 (activationList (caddr netList))
13 (weightList (cadr (cdddr netList)))
14 (iDimension nil)
15 (jDimension nil)
16 (iActivationVector nil)
17 (jActivationVector nil)
18 (n nil)
19 (weightArray nil)
20 (returnList nil)
21 (sum nil))
22 (setq iDimension (car sizeList)) ; get the size of the input slab
23 (setq iActivationVector (car activationList)) ; get input activations
24 (dotimes (i iDimension) ; copy training inputs to input slab
25 (setf (aref iActivationVector i) (nth i inputs)))
26 (dotimes (n-1 (- nLayers 1)) ; update layer j to layer i
27 (setq n (+ n-1 1))
28 (setq jDimension (nth n sizeList)) ; get the size of the j'th layer
29 (setq jActivationVector (nth n activationList)) ; activation for slab j
30 (setq weightArray (nth n-1 weightList))
31 (dotimes (j jDimension) ; process each neuron in slab j
32 (setq sum 0.0) ; init sum of products to zero
33 (dotimes (i iDimension) ; get activation from each neuron in last slab
34 (setq
35 sum
36 (+ sum (* (aref weightArray i j) (aref iActivationVector i)))))
37 (if *delta-rule-debug-flag*
38 (print (list "sum=" sum)))
39 (setf (aref jActivationVector j) (Sigmoid sum)))
40 (setq iDimension jDimension) ; get ready for next slab pair
41 (setq iActivationVector jActivationVector))
42 (dotimes (j jDimension)
43 (setq returnList (append returnList (list (aref jActivationVector j)))))
44 returnList))
We saw three output plots earlier that were produced during a training run using the following code:
1 (defun test3 (&optional (restart 'yes) &aux RMSerror (temp nil)) ; three layer network
2 (if
3 (equal restart 'yes)
4 (setq temp (newdeltanetwork '(5 4 5))))
5 (dotimes (ii 3000)
6 (setq
7 RMSerror
8 (deltalearn
9 temp
10 '(((1 0 0 0 0) (0 1 0 0 0))
11 ((0 1 0 0 0) (0 0 1 0 0))
12 ((0 0 1 0 0) (0 0 0 1 0))
13 ((0 0 0 1 0) (0 0 0 0 1))
14 ((0 0 0 0 1) (1 0 0 0 0)))))
15 (if (equal (mod ii 50) 0) ;; print error out every 50 cycles
16 (progn
17 (princ "....training cycle \#")
18 (princ ii)
19 (princ " RMS error = ")
20 (princ RMSerror)
21 (terpri)))))
Here the function test3 defines training data for a very small test network for a moderately difficult function to learn: to rotate the values in the input neurons to the right, wrapping around to the first neuron. The start of the main loop calls the training function 3000 times, printing the RMS error every 50 times through the main loop.
Backpropagation networks have been used sucessfully in production for about 25 years. In the next chapter we will look at a less practical type of network, Hopfield networks, that are still interesting because the in some sense Hopfield networks model how our brains work. In the final chapter we will look at deep learning neural networks.