Convolution

Convolution is a mathematical operation on two functions that produces a third function expressing how the shape of one is modified by the other.

The term convolution comes from the latin com(with) + volutus(rolling).

Convolution filters, also called Kernels, can remove unwanted data. During the forward pass, each filter uses a convolution process across the filter input, computing the dot product between the entries of the filter and the input and producing an n-dimensional output of that filter. As a result, the network learns filters that activate when it detects some specific type of feature at some spatial position in the input.

Mathematically, Convolution is an integral that expresses the amount of overlap of one function g as it is shifted over another function f :

$\\c=\left ( f*g \right )\left ( t \right )= \int_{0}^{t}f\left ( \tau \right ) g\left ( t-\tau \right )d\tau \\\\\textup{where:} \\\\c\,\,\,\,\,\,\,\textup{convolution output function} \\f\,\,\,\,\,\,\textup{original input function} \\g\,\,\,\,\,\,\textup{function that is shifted over the input function} \\t\,\,\,\,\,\,\,\textup{variable representing range of shifting} \\\tau \,\,\,\,\,\,\textup{shifting against t}$

Examples Using Matrices

Convolution can be used successively across the cells of a matrix to create a new matrix, as illustrated below. There are three examples using different forms of padding in the form of zeros around a matrix:

No Padding - only the original matrix is used
Half Padding - padding around part of the matrix is used
Full Padding - padding around the full matrix is used

The purpose of padding is to allow the convolutional filter to pass across the matrix in different ways.

All three examples use a stride of 2, which means that the filter is moved by two cells for each convolutional operation.

No Padding

Using no padding is also called a ‘valid’ operation. However, this term is a bit misleading, as is this case where the stride of 2 doesn’t allow the 3x3 convolution filter to move all the way to the last column and row of the target matrix:

Half Padding

Using half padding, also called a ‘same’ operation, the convolution filter is allowed to move across all the rows and columns of the target matrix:

Full Padding

Using full padding, also called a ‘full’ operation, the convolution filter is allowed to move across all the rows and columns of the target matrix using an additional stride:

Examples Using Vectors

The examples below illustrates convolution using two vectors that produces three output variations. Note that:

the input vectors are used in various rolling configurations to compute vector z dot products and resulting scalars r
depending on the type of result desired (e.g., full, same, valid), selected configuration scalars are included in the convolution output

Python Example

The examples below reflects the illustration above.

To download the code, click here.

"""
convolution_with_numpy.py
defines and tests a convolution function
"""

# Import needed libraries.
import numpy as np
import matplotlib.pyplot as plt

# Initialize parameters.
vector_x = [1, 2, 3]
vector_y = [0, 1, 0.5]
type_full = 'full'
type_same = 'same'
type_valid = 'valid'


# Define a convolution function.
def convolution(vector_first, vector_second, convolution_type):
    result = np.convolve(vector_first, vector_second, convolution_type)
    print(convolution_type + ':')
    print(result)


# Execute the convolution function for each convolution type.
convolution(vector_x, vector_y, type_full)
convolution(vector_x, vector_y, type_same)
convolution(vector_x, vector_y, type_valid)

The output is below:

full:
[0.  1.  2.5 4.  1.5]
same:
[1.  2.5 4. ]
valid:
[2.5]