A convolutional neural network (CNN or ConvNet) is a type of ANN that is usually discussed in the context of deep learning for analyzing visual imagery. It is actually good for identifying patterns between neighboring points in a sample, such as the spatial patterns in the image pixels close to each other. A modern CNN typically contains one or more of some basic elements such as convolution layers, activation functions like ReLU or its variant, pooling layers, and fully connected layers. In addition, Softmax or Sigmoid is additionally needed for classification tasks.
An understanding of the CNN, i.e., how it works, requires us to figure out how these different elements will be handled in backpropagation (including forward and backward passes as defined in the Chapter for NN) in both training and testing. Considering that training involves both passes while testing only involves the forward pass, we will show how the two passes will be made in a typical training process for convolution layers, ReLU, and pooling layers in the following subsection. The treatment for fully connected layers is the same as what is introduced for shallow NNs. The introduction thus will present explanations for understanding the working mechanisms of these elements as well as equations and procedures for implementing the training of a CNN consisting of these elements.
9.2.1. Convolution
The implementation of backpropagation including both forward and backward passes in a deep NN with exclusively convolution layers is outlined in Fig. 9.2. As illustrated, the forward pass starts from the first layer, where the input data for training, II, enters and moves along the blue arrows via the blue equations until the predicted output, OO, is generated as the output of the last layer (i.e., Layer NN ). The difference between the prediction, OO, and the labeled output, O_("true ")O_{\text {true }}, i.e., the loss LL, will be used to calculate the gradients (del L)/(delO^(N))\frac{\partial L}{\partial O^{N}}. Then, the gradients will propagate backward through the whole network until reaching the first layer.
The main operation in the forward pass, i.e., convolution, is I**F=OI * F=O. As a result, in the backward pass, the key steps are the calculation of (del L)/(del F)\frac{\partial L}{\partial F} and (del L)/(del I)\frac{\partial L}{\partial I} and the update on the convolution kernel FF. To move backward from one layer to the previous layer, the calculated value of (del L)/(del I)\frac{\partial L}{\partial I} for the current layer, i.e., (del L)/(delI^(n))\frac{\partial L}{\partial I^{n}}, will be used as (del L)/(del O)\frac{\partial L}{\partial O} of the previous layer, i.e., (del L)/(delO^(n-1))\frac{\partial L}{\partial O^{n-1}}, because the input of the current layer I^(n)I^{n} is the output of the previous layer O^(n-1)O^{n-1}.
The key in the implementation of the above two-way process is the convolution operation, i.e., equation with an *** operator, in the forward pass and the two equations for calculating (del L)/(del F)\frac{\partial L}{\partial F} and (del L)/(del I)\frac{\partial L}{\partial I} in the backward pass, which were given in Fig. 9.2 without explanation. In the following subsection, the deduction of these equations will be presented while we explain how convolution and backpropagation work through the convolution layers. It is noted that this figure only contains convolution layers. Therefore, more operations or other modifications will be needed if other CNN elements are needed. In addition, we must notice that operations with this set of equations for using and updating FF need to be performed for each convolution kernel. Usually, there is more than one kernel in each convolution layer. Therefore, such operations need to be carried out using the same equations but with different FF for different kernels.
Figure 9.2: Backpropagation through convolution layers
Forward Pass
Before being exposed to "convolution" in CNN, you possibly have heard about convolution in the context of general mathematics. It usually appears as a mathematical operation on two functions, e.g., yy and ff, generating a third function oo :
where tt is the axis (or independent variables) along which the three functions are defined. The operation can be understood as the area under the function i(tau)i(\tau) weighted by the function f(-tau)f(-\tau) shifted by tt.
The convolution in CNN is applied to data with a finite size, thus, the above equation can be slightly modified into
where tt is still the axis along which the three functions are defined, and the integration bounds denote the finite size of the data.
In addition, image data, such as a photo, is usually represented as an array of numbers, in which each element or entry corresponds to a pixel in the photo. Thus, the convolution operation needs to take a discrete form so that it can be applied to discrete image data.
The above equation states that the element nn in the generated convolution results OO is obtained as a weighted sum of the (image) data, II, and the convolution kernel as the weight. The above operation needs to be repeated NN times, where NN is the number of elements of the generated results along the direction of the operation (shifting direction).
The schematic in Fig. 9.3 shows what happens when a convolution kernel is applied to an image. As illustrated, each convolution kernel from a convolution layer, or called a learnable filter or a neuron, is slid over the image. This starts with the red box on the left upper corner, which has the same number of elements as the kernel and can be called a receptive field. The application of the kernel to his receptive field mathematically corresponds to the computation of a dot product between the entries/elements of the filter and the array of the receptive field. This sum of this regional operation generates the (1,1)(1,1) element of the output data, leading to a new element (1,1)(1,1) (" 4 " in the red cell )) in the result matrix. A stride like a step size is prescribed to move to the next receptive field. If a stride of 1 is used as illustrated in the figure, then the receptive area to the right of the red box region is the green box region. The same regional operation leads to the (1,2)(1,2) element (" 3 " in the green cell ) in the output. The same process will be repeated as the kernel moves over all the receptive fields.
To better show how different elements in the input and kernel are processed in the convolution operation, let us look at the example in Fig. 9.4, This example has a very simple 3xx33 \times 3 array II as input, i.e., data to which convolution is applied, and a 2xx22 \times 2 kernel. This example will also be employed in the following subsections for CNN to derive other equations for backpropagation.
Figure 9.3: Schematic of the application of a kernel to a 2D image (2D array)
Figure 9.4: An example for convolution operation
In the above example, the following equations can be used to get the output.
The above equations can be extended for images and kernels of any size to implement the forward pass.
Backward Pass
As illustrated in Fig. 9.2, both (del L)/(del F)\frac{\partial L}{\partial F} and (del L)/(del I)\frac{\partial L}{\partial I} need to be calculated for each layer while (del L)/(del O)\frac{\partial L}{\partial O} is from the next layer. That is, (del L)/(del O)\frac{\partial L}{\partial O} is calculated as the (del L)/(del I)\frac{\partial L}{\partial I} of the following layer. (del L)/(del F)\frac{\partial L}{\partial F} is obtained to update the filter, while (del L)/(del I)\frac{\partial L}{\partial I} of the current layer is obtained to work as the (del L)/(del O)\frac{\partial L}{\partial O} of the previous layer.
The following chain rule needs to be recalled first to start deriving (del L)/(del F)\frac{\partial L}{\partial F} and (del L)/(del I)\frac{\partial L}{\partial I} :
where (del L)/(del O)\frac{\partial L}{\partial O} can be obtained by passing the gradients layer by layer all the way back from the last layer. Thus, the above two types of gradients can be obtained as long as (del O)/(del F)\frac{\partial O}{\partial F} and (del O)/(del I)\frac{\partial O}{\partial I} can be obtained. Next, let us take a look at these two types of gradients.
As for Eq. 9.6a, in order to see what (del O)/(del F)\frac{\partial O}{\partial F} looks like, let us use O_(11)O_{11} first:
Then we will have (delO_(11))/(delF_(11))=X_(11),(delO_(11))/(delF_(12))=X_(12),(delO_(11))/(delF_(21))=X_(21)\frac{\partial O_{11}}{\partial F_{11}}=X_{11}, \frac{\partial O_{11}}{\partial F_{12}}=X_{12}, \frac{\partial O_{11}}{\partial F_{21}}=X_{21}, and (delO_(11))/(delF_(22))=X_(22)\frac{\partial O_{11}}{\partial F_{22}}=X_{22}. Similarly, we can get the local gradients for O_(12),O_(21),O_(22)O_{12}, O_{21}, O_{22}. Using these gradients, we can get the detailed equations for each element of (del L)/(del F)\frac{\partial L}{\partial F}. Let us check two typical elements:
We can get the equations for all the elements in a similar way. It is not difficult to find that the above equations can be summarized as operation in Fig. 9.5:
Figure 9.5: Operation for obtaining (del L)/(del F)\frac{\partial L}{\partial F}
As for Eq. 9.6 b, to get (del L)/(del I)\frac{\partial L}{\partial I}, let us see what (del O)/(del I)\frac{\partial O}{\partial I} looks like: (delO_(11))/(delI_(11))=F_(11),(delO_(11))/(delI_(12))=F_(12),(delO_(11))/(delI_(21))=F_(21)\frac{\partial O_{11}}{\partial I_{11}}=F_{11}, \frac{\partial O_{11}}{\partial I_{12}}=F_{12}, \frac{\partial O_{11}}{\partial I_{21}}=F_{21}, and (delO_(11))/(delI_(22))=F_(22)\frac{\partial O_{11}}{\partial I_{22}}=F_{22}. Similarly, we can get the local gradients for O_(12),O_(21),O_(22)O_{12}, O_{21}, O_{22}. Then, let us write out the detailed formulations of the elements of (del L)/(del I)\frac{\partial L}{\partial I} based on the above equations for the elements of (del O)/(del I)\frac{\partial O}{\partial I} :
The mathematical operation performed via the above equations can be summarized into the algebraic operation in Fig. 9.6:
In the above equation, F^(180^(@))F^{180^{\circ}} is obtained by rotating the array of FF by 180 degrees. Taking a 2D array as an example, if there are k_(h)k_{h} rows (height) and k_(w)k_{w} columns (width), then the element F_(ij)F_{i j} in the new array, F^(180^(@))F^{180^{\circ}}, will be F_((k_(h)+1-i)xx(k_(w)+1-j))F_{\left(k_{h}+1-i\right) \times\left(k_{w}+1-j\right)} in the original array, FF. The "full convolution" operator represented by ***\star in this book is different
Figure 9.6: Operation for obtaining (del L)/(del I)\frac{\partial L}{\partial I}
from the regular convolution, which is also called "valid convolution" in many places. The full convolution operation can be understood using the example given in Fig. 9.7. As can be seen, the array behind the operator (in yellow) is moved from the left upper corner of the array before the operator (blue), from left to right, upper to lower. The weighted sum of the overlapping area is where the local convolution occurs and generates a corresponding element in the operation result. For example, the lowest, rightmost element of the yellow array works as the weights for obtaining the sum of the highest, leftmost element (or a patch or region if a stride greater than 1 is used) of the blue array to generate the (1,1)(1,1) element of the generated array. Then, the yellow array is moved one element (or patch) to the right, and the weighted sum will be the (1,2)(1,2) element. The above process is repeated until all the elements (patches) of the new array are generated.
Figure 9.7: Example of full convolution operation
Padding and Stride
The above operations in backpropagation can be much more complicated in implementation. This is because the above illustrations were made with a very simple case: a padding of 0 and a stride of 1 . However, in modern CNN practice, the use of positive padding values and strides greater than 1 is very common. When working on the implementation, such as coding a CNN ourselves, we will need to pay close attention to the sizes of different matrices and the change of these sizes as we apply different operations including convolution with a padding and a stride. A padding is used to add extra space (or elements with 0's) so that an operation such as convolution can generate an array with desired sizes. Usually, positive paddings, either identical or different paddings, can be added to different directions, i.e., height and width, to increase the size of the generated images. In common situations, the same number of padding elements are added to both ends in each direction. A stride greater than 1 is used to reduce the overlap between the neighboring receptive fields.
Let us assume II has a size of n_(h)xxn_(w),Fn_{h} \times n_{w}, F has a size of k_(h)xxk_(w)k_{h} \times k_{w}. In the forward pass, if we apply a convolution operation between these two arrays with paddings of p_(h)xxp_(w)p_{h} \times p_{w} and strides of s_(h)xxs_(w)s_{h} \times s_{w}, then the size of the generated OO will be (n_(h)-k_(h)+p_(h)+s_(h))//s_(h)xx(n_(w)-k_(w)+p_(w)+s_(w))//s_(w)\left(n_{h}-k_{h}+p_{h}+s_{h}\right) / s_{h} \times\left(n_{w}-k_{w}+p_{w}+s_{w}\right) / s_{w}. Accordingly, in the backward pass, we will apply a full convolution between FF and (del L)/(del O)\frac{\partial L}{\partial O}. In this case, (del L)/(del O)\frac{\partial L}{\partial O} has a size of (n_(h)-k_(h)+p_(h)+s_(h))//s_(h)xx(n_(w)-k_(w)+p_(w)+s_(w))//s_(w),F\left(n_{h}-k_{h}+p_{h}+s_{h}\right) / s_{h} \times\left(n_{w}-k_{w}+p_{w}+s_{w}\right) / s_{w}, F has the same size, i.e., k_(h)xxk_(w)k_{h} \times k_{w}, and we will obtain (del L)/(del I)\frac{\partial L}{\partial I} with a size of n_(h)xxn_(w)n_{h} \times n_{w}, which is the same as that of II. Therefore, from a perspective of sizes, the above processes need to be "reversible". That is, the gradients returned in the backward pass should have the same size as the arrays where the gradients correspond to (or are applied to for update). For this purpose,
a general rule needs to be maintained: the same padding and stride values need to be used in both passes. Usually, we do not change padding and stride values in different backpropagation iterations, so these values should stay the same in the training processes. Even in testing, the training network will still stick to the same paddings and strides if being applied to data of the same size.
The use of paddings will not change the operations introduced in the previous subsection too much. We just want to make sure the same padding(s) is adopted and also pay attention to the sizes of different arrays according to the equations given above. The treatment of strides requires more care. This is because, in the forward pass, the input array, II, is "downsampled" when a stride greater than 1 is used. That is, the output array OO is smaller than that obtained with a stride of 1 . Due to this reason, we will need to upsample the gradients with respect to OO, i.e., (del L)/(del O)\frac{\partial L}{\partial O}, before using it for calculating (del L)/(del F)\frac{\partial L}{\partial F} and (del L)/(del I)\frac{\partial L}{\partial I}. This upsampling in the backward pass needs to be done with the same stride values as adopted in the forward pass for the same layer. For example, for a stride of ss, the upsampling needs to add s-10s-10 's between the neighboring elements in the array to be upsampled.
9.2.2. ReLU
In traditional ANNs, most elements are differentiable. That is why, in the ANN chapter, continuous functions can be obtained for the derivatives (gradients) in backpropagation. By contrast, CNN has added special elements, such as ReLU, which is not differentiable at some points, and pooling, which changes the sizes of the data. Special treatment needed for these two CNN elements will be introduced in this and the following subsections.
The mathematical function of ReLU can be written as
This function is not differentiable at x=0x=0. To deal with this issue, we can set the derivative at x=0x=0 as 0 or 1 . The choice will not affect the gradient to be used for updating the network. For example, the update on the weight in a typical example is w=w+alpha**( hat(y)-y)*delta_(ReLU)*(del(w*x-theta))/(del w)w=w+\alpha *(\hat{y}-y) \cdot \delta_{\operatorname{ReLU}} \cdot \frac{\partial(w \cdot x-\theta)}{\partial w}, where (del(w*x-theta))/(del w)=x\frac{\partial(w \cdot x-\theta)}{\partial w}=x. As can be seen, at x=0x=0, the increment (second part on the right-hand side of the equation) equals 0 no matter the gradient of ReLU(delta_("ReLU "))\operatorname{ReLU}\left(\delta_{\text {ReLU }}\right) is set as 0 or 1 .
Other activation functions such as Linear, Linear threshold, Maxout, and Softmax will not be discussed here. More information can be found in more specific deep learning literature.
9.2.3. Pooling
As mentioned above, pooling changes the size of the feature map. This prevents the gradients from being passed from the elements after pooling to their corresponding elements in the feature map before pooling. A general solution is to make sure the gradient of every element (or pixel) can be passed backward to the elements that generated this element in the previous forward pass. In this way, the total gradients will stay the same, which is needed to avoid gradient explosion or vanishing. Different pooling methods, e.g., average pooling and max pooling, have different treatments.
For the average pooling, as illustrated in Fig. 9.8, a straightforward way is to evenly divide the gradient of an element for all the elements that are pooled to generate that element. For example, the yellow element in the feature map after pooling is generated by the four elements in the feature map before pooling in the forward process. Therefore, in the backward process, the element 4 is divided by 4 . The obtained quotient, 1 , is then assigned to those four elements.
For the max pooling, a common way is to give the gradient to the element with the maximum value in the feature map before pooling. As shown in Fig. 9.9, the element with a gradient of 8 (orange) passes this gradient to the lower left element in the orange area, which has the maximum value in the forward pass. Therefore, in the implementation, the location of the element that has the highest value in each small region for pooling needs to be recorded in the forward pass, so that the gradient can be passed to it in the following backward pass.
It is worthwhile to mention that, in the above figures, the same feature map after pooling is used for the two passes (i.e., forward and backward) to help the readers better understand the operations. In reality, the feature map after pooling and the gradients that need to be passed backward are totally different, though they are the same size.
Figure 9.8: Forward and backward passes in backpropagation of average pooling layer
Figure 9.9: Forward and backward passes in backpropagation of max pooling layer
9.3. Recurrent Neural Network
RNN has many different variations with distinct structures. Shown in Fig. 9.10 is one of the most common architectures. On the left is the schematic of a unit. The one in the middle shows a more detailed flow of the data through the unit. The subplot on the right illustrates how the unit unfolds over time.
Figure 9.10: Structure and workflow of RNN
The symbols in Fig. 9.10 have the following meanings: x^(t)x^{t} is the output at step tt in the time series; h^(t)h^{t} is the state of the hidden layer at tt, which is determined by both x^(t)x^{t} and h^(t-1)h^{t-1} according to the above network architecture; o^(t)o^{t} is the output at tt, which is determined by the hidden state at the current step tt; L^(t)L^{t} is the loss function at tt; y^(t)y^{t} is the actual output (or label) at tt; tilde(y)^(t)\tilde{y}^{t} is the predicted output at tt; sigma_(1)\sigma_{1} and sigma_(2)\sigma_{2} are the hidden layer activation function and output activation function, respectively; U,WU, W, and VV are the arrays that include the network weights to be predicted.
