This node before explained how it works, and now we need to understand how to write the operation mathematically and more importantly code it efficiently. So suppose we have the input I with the shape H x H x C, where B - the batch, H - is the height and width of the image( just taking square image for the example), C - the amount of channels. One kernel k has a size of K x K x C( also taking square kernel for the sake of the example). b is the bias for that kernel

$ ( I * K)_{i,j} = \sum_{m=0}^{k-1} \sum_{n=0}^{k-1} \sum_{c=0}^{C} K_{m,n,c} I_{i + m, j + n, c} + b$
-------------------------------------------------
$ ( I * K)$ - is the output matrix for the current kernel with size of H-K+1, H-K+1. This is the variation of the Convolution with no padding and stride one. Most of the libraries call it convolution but it is actually an operation called cross-correlation. In terms of coding the formula for convolution, there are several ways to implement it. One of them might be just straight brute force with nested loops, turning everything int a big matrix multiplication, and even using Fourier transforms. While brute force solution is straight forward, other two ways are not that easy to visualize and understand


Mathematical Implementation of Forward Propagation

Here is the visualization of the convolution operation were you can play with different hyperparameters of CNN:
https://ezyang.github.io/convolution-visualizer/index.html

Convolution Visualizer

On the left, we have a 6 x 6 grayscale image, so we represent it using a 6 x 6 x 1 matrix because there are no separate RGB channels. To detect vertical edges, we construct a 3 x 3 matrix, called filter or kernel, shown in the middle. We convolve the 6 x 6 matrix with the 3 x 3 filter. The output of this convolution operator will be a 4 x 4 matrix.

To compute the upper left element of this 4 x 4 matrix, we take the 3 x 3 filter and paste it on top of the 3 x 3 region of the original input image and sum up all the 9 the element-wise products. So, the result would be 3 x 1 + 1 x 1 + 2 x 1 + 0 x 0 + 5 x 0 + 7 x 0 + 1 x (-1) + 8 x (-1) + 2 x (-1) = -5. Next, to compute the second element, we shift the pasted filter matrix one step to the right on the 6 x 6 image, do the same element-wise products, and then add them up, which will give us -4, and so on.

To compute the next rows, we shift the pasted filter matrix one step down on the 6 x 6 image. Then, we repeat the same element-wise products, and additions for the second row, and so on.

Calculating Cross-Correlation (Convolution) Operation Example

Since kernels generally have width and height greater than 1, after convolving an image by the kernel, the image size will be reduced. By adding padding to the input image, we can have the output with the same size as input.

If we start with a 240×240-pixel image, 10 layers of 5×5 convolutions reduce the image to 200×200 pixels, slicing off 30% of the image and with it obliterating any interesting information on the boundaries of the original image. Padding is the most popular tool for handling this issue.

In the below example, we pad a 3×3 input, increasing its size to 5×5. The corresponding output then increases to a 4×4 matrix. The shaded portions are the first output element as well as the input and kernel tensor elements used for the output computation:  0×0+0×1+0×2+0×3=0.

Padding Convolution

When computing the cross-correlation, we start with the convolution window at the top-left corner of the input tensor, and then slide it over all locations both down and to the right. Usually, we default to slide one element at a time. However, sometimes, either for computational efficiency or because we wish to down-sample, we move our window more than one element at a time, skipping the intermediate locations.

We refer to the number of rows and columns traversed per slide as the stride.

Strided Convolution

Input size: $n_h * n_w$ 
Kernel size: $k_h * k_w$ 
Output size: $(n_h-k_h+1) * (n_w-k_w+1)$

Computation of Convolution Output Size

In the two-dimensional cross-correlation operation, we begin with the convolution window positioned at the top-left corner of the input tensor and slide it across the input tensor, both from left to right and top to bottom.
When the convolution window slides to a certain position, the input subtensor contained in that window and the kernel tensor are multiplied elementwise and the resulting tensor is summed up yielding a single scalar value. This result gives the value of the output tensor at the corresponding location.

Two-Dimensional Convolution Operation Procedure

A 2D convolution layer performs an entry per entry multiplication between the input and the filter, where the input and the filter are 2D matrices. 

In a 3D convolution layer, the same operation is performed on 3D inputs and the filters, such that:
- We multiply corresponding entries in the input and filter cubes and add up the results to determine the output entry.
- In addition to shifting (striding) the filter on two dimensions of the input matrix to perform the convolution operation, we also shift it in the third dimension.

For example, if we have a 4 x 4 x 4 input and a 3 x 3 x 3 filter, because we can shift the filter for only one entry per dimension, the output will be 2 x 2 x 2.

3D Convolution Layers

For example, if we have a 3 x 3 x 3 RGB filter, to perform the convolution operation, we start with placing the filter in the upper left most position of the image. We can consider this 3 x 3 x 3 filter as a cube with 27 parameters, where the first dimension is called "width," the second is called height, and the third indicates the number of channels. We multiply each of these 27 numbers with the corresponding numbers from the red, green, and blue channels of the image and sum up the results to calculate the corresponding output number. Then to compute the next output, we take this cube and slide it over by one, do the 27 multiplications, and add up the results to calculate the next output number, and so on. This way, convolving a 6 x 6 x 3 image with a 3 x 3 x 3 filter will give us a 4 x 4 output.

Convolutions Over Volumes

- The convolution operation, denoted by the asterisk (*), indicates mapping the filter matrix (kernel) to every possible position on the input matrix, multiplying each of the pairs of numbers, elementwise, and adding them up to calculate the corresponding element in the result matrix.


- In mathematics, the asterisk is the standard symbol for convolution but in Python, this is also used to denote multiplication or elementwise multiplication.


- Traditionally, the convolution operation before its application has a kernel mirroring step (left to right, and up to down). This allows associativity across convolutions to hold. In deep learning, this mirroring doesn't have a significant impact on the operations and thus is omitted. Also when the kernel is symmetric, the operations are identical. Hence, convolution in deep learning refers to cross-correlation. 

University of Michigan - Ann Arbor

A “filter”, sometimes called a “kernel”, is passed over the image, viewing a few pixels at a time (for example, 3X3 or 5X5). The convolution operation is a dot product of the original pixel values with weights defined in the filter. The results are summed up into one number that represents all the pixels the filter observed.

Convolution Filter (Kernel)

Good article for buliding an intuition on how to derive the backpropagation formula:https://medium.com/@pavisj/convolutions-and-backpropagations-46026a8f5d2c

Convolutions and Backpropagations

The back-propagation in CNN is done on the same principle of the chain rule, but the the the way it is actually done is not that easy. Of course if we have the gradient of the output we could do bunch of nested loops and calculate the gradients of the parameters and inputs, but this would be crazy inefficient. We need to search a way to vectorize this. We already implemented the forward propagation, and convolution operation is heavily involved in back propagation. The formulas for the gradients of the input are the following:(Suppose L is the cost function, F is the current filter, X is the current input)


Backpropagation in CNN

The Cross-Correlation (Convolution) Operation

The size of one dimension of the filter (kernel) matrix. Because it's usually a square matrix, we only consider the size of one dimension which is usually the same as the other dimension.

In machine vision, it is usually an **odd** number. So, we usually have a center cell in the filter (kernel) matrix.

Filter (Kernel) Size in Convolutional DNN

https://medium.com/@RosieCampbell/demystifying-deep-neural-nets-efb726eae941

Demystifying Deep Neural Nets

In a convolutional layer, instead of manually specifying numbers of cells of the filters (kernels), we define each of them as weights and we add a single bias number to each cell. Then, we train the model with these new parameters the same way as we optimize the weights and biases of neurons. So, the number of parameters in each filter (kernel) will be the number of its cells plus one bias.

The first ConvLayer is responsible for capturing the Low-Level features such as edges, color, gradient orientation, etc. With added layers, the architecture adapts to the high-level features as well, giving us a network which has the wholesome understanding of images in the dataset, similar to how we would.

Convolutional Layer (ConvLayer)

Three basic strategies for obtaining convolution kernels without supervised training:
- Initializing them randomly
- Setting each kernel to detect edges at a certain orientation or scale
- Item learning the kernels with an unsupervised criterion

Learn Before

Related

Learn After