542
CHAPTER 13. NEURAL NETS AND DEEP LEARNING
the ﬁlter F and the corresponding region in the input into vectors. Consider
the convolution of an m×m×1 tensor X (i.e., X is actually an m×m matrix)
with an f × f ﬁlter F and bias b, to produce as output the n × n matrix Z.
We now explain how to implement the convolution operation using a single
vector-matrix multiplication.
We ﬁrst ﬂatten the ﬁlter F into a f 2 × 1 vector g. We then create matrix
Y from X as follows: each square f × f region of X is ﬂattened into a f 2 × 1
vector, and all these vectors are lined up as columns to form a single f 2 × n2
matrix Y . Construct the n2 × 1 vector b so that all its entries are equal to the
bias b. Then
z = Y Tg + b
yields a n2 × 1 vector z. Moreover, each element of z is a single element in the
convolution. Therefore, we can rearrange the entries in z into an n × n matrix
Z that gives the output of the convolution.
Notice that the matrix Y is larger than the input X (approximately by a
factor of f 2), because each entry of X is repeated many times in Y . Thus,
this implementation uses a lot of memory. However, multiplying a matrix and
a vector is extremely fast on modern hardware such as Graphics Processing
Units (GPU’s), and so it is the method used in practice.
This approach to computing convolutions can easily be extended to the case
of inputs with more than one channel. Moreover, we can also handle the case
where we have k ﬁlters rather than just 1. We then need to replace the vector
g with a df 2 × k matrix G and use a larger matrix Y (df 2 × n2). We also need
to use an n2 × k bias matrix B, where each column repeats the bias term of
the corresponding ﬁlter. Finally, the output of the convolution is expressed by
an n2 × k matrix C, with a column for the output of each ﬁlter, where:
C = Y TF + B
We have explained how to perform the forward pass through the convolu-
tional layer. During training, we shall need to backpropagate through the layer.
Since each entry in the output of convolution is a dot product of vectors followed
by a sum, we can use the techniques from Section 13.3.3 to compute deriva-
tives. It turns out that the derivative of a convolution can also be expressed as
a convolution, but we shall not go into the details here.
13.4.6
Exercises for Section 13.4
Exercise 13.4.1: Suppose images are 512-by-512, and we use a ﬁlter that is
3-by-3.
(a) How many responses will be computed for this layer of a CNN?
(b) How much zero padding is necessary to produce an output of size equal
to the input?
