Implementing a Convolution Layer

These are my notes from implementing Convolution Layer in CS231n Assignment 2. This post focuses on implementation rather than the underlying concepts.

Convolution Layer

The core of a CNN is convolution. Unlike a fully connected layer, a convolution layer preserves the input's spatial structure. Convolution extracts feature maps from that input.

 

The number of filters determines the output activation map's depth. How the filters slide over the input determines its spatial size. Given input size N, filter size F, and padding p, the equation below calculates the output size.

(N+2p−F)/Stride+1(N + 2p - F) / Stride + 1

So a convolution layer simply slides each filter across the input and calculates values. Sounds easy to implement, right?

That is true—but implementing it taught me a painful lesson.

Forward Pass

def conv_forward_naive(x, w, b, conv_param):
"""
Input:
- x: Input data of shape (N, C, H, W)
- w: Filter weights of shape (F, C, HH, WW)
- b: Biases, of shape (F,)
- conv_param: A dictionary with the following keys:
	- 'stride': The number of pixels between adjacent receptive fields in the horizontal and vertical directions.
	- 'pad': The number of pixels that will be used to zero-pad the input.

Returns a tuple of:
- out: Output data, of shape (N, F, H', W') where H' and W' are given by
	H' = 1 + (H + 2 * pad - HH) / stride
	W' = 1 + (W + 2 * pad - WW) / stride
- cache: (x, w, b, conv_param)
"""

out = None
cache = (x, w, b, conv_param)

return out, cache

Let us unpack the problem:

  1. The input x contains N images, each of size H × W × C, where C is the channel count, such as RGB.
  1. Slide F filters, each of size HH × WW × C, over the input.
  1. Add a bias vector of size F.
  1. Produce N outputs of size H′ × W′ × F.
  1. Calculate H′ and W′ using the equation above.

That is the task.

 

Now let us consider the computational graph.

 

It does not produce the output in one step. First, pad x, crop a region matching the filter size, take its dot product with the filter, and add the bias. This produces spatial_out of shape (N, F).

 

Imagine N copies of the container of balls in the middle of the picture. Each ball represents the value computed by one filter, with F balls in each container.

Repeat this process H′ × W′ times to obtain the desired output of shape (N, F, H′, W′)!

N, C, H, W = x.shape
F, C, HH, WW = w.shape

stride = conv_param['stride']
pad = conv_param['pad']

npad = ((0,0),  (0,0),  (pad,pad),  (pad,pad)) # padding 위한 값
filter_size = C*HH*WW # 내적의 용이성을 위해 미리 계산해두는 값

H_out = int(1 + (H + 2 * pad - HH) / stride) # H'
W_out = int(1 + (W + 2 * pad - WW) / stride) # W'

out = np.zeros((N, F, H_out, W_out)) # 최종적으로 구할 out 초기화 (N, F, H', W')
x_pad = np.pad(x, npad,  'constant', constant_values=(0)) # x에 pad 크기만큼 zero-padding

for height in  range(H_out):
	for width in  range(W_out):
		x_crop = x_pad[np.arange(N),  :, height*stride:height*stride+HH, width*stride:width*stride+WW]  # x에서 (N,C,HH,WW)크기만큼을 crop
		x_crop_stretch = x_crop.reshape(N, filter_size)  # (N, filter_size)
		w_stretch = w.reshape(F, filter_size)  # (F, filter_size)
		spatial_out = np.dot(x_crop_stretch, w_stretch.T) + b.reshape((1,F)) # (N,F)
		out[np.arange(N),  :, height, width] = spatial_out

Backward Pass

After all that work on the forward pass, it is time to implement the backward pass.

Do not panic. (I panicked.)

def conv_backward_naive(dout, cache):
    """
    Inputs:
    - dout: Upstream derivatives.
    - cache: A tuple of (x, w, b, conv_param) as in conv_forward_naive

    Returns a tuple of:
    - dx: Gradient with respect to x
    - dw: Gradient with respect to w
    - db: Gradient with respect to b
    """
    dx, dw, db = None, None, None
    return dx, dw, db

The task is quite simple.

Use the computational graph above to calculate dx, dw, and db.

x, w, b, conv_param = cache
N, C, H, W = x.shape
F, C, HH, WW = w.shape
N, F, H_out, W_out = dout.shape

stride = conv_param['stride']
pad = conv_param['pad']

npad = ((0,0), (0,0), (pad,pad), (pad,pad)) # x = (N, C, H+2*pad, W+2*pad)
filter_size = C*HH*WW # scalar, for stretch
x_pad = np.pad(x, npad, 'constant', constant_values=(0))

dx_pad = np.zeros((N,C,H+2*pad,W+2*pad))
dw = np.zeros((F,C,HH,WW))
db = np.zeros(F)

for height in range(H_out):
	for width in range(W_out):
		dspatial_out = dout[np.arange(N), :, height, width] # (N, F)
		db += np.sum(dspatial_out, axis=0) # (F, )

		x_tmp = x_pad[np.arange(N), :, height*stride:height*stride+HH, width*stride:width*stride+WW] # (N, C, HH, WW)
		dw_stretch = np.dot(dspatial_out.T, x_tmp.reshape(N, filter_size)) # (N,F).T @ (N,filter_size) = (F, filter_size)
		dw += dw_stretch.reshape(F,C,HH,WW)

		w_stretch = w.reshape(F, filter_size) # (F, filter_size)
		dx_tmp_stretch = np.dot(dspatial_out, w_stretch) # (N,F) @ (F,filter_size) = (N, filter_size)
		dx_tmp = dx_tmp_stretch.reshape(N,C,HH,WW)
		dx_pad[np.arange(N), :, height*stride:height*stride+HH, width*stride:width*stride+WW] += dx_tmp

dx = dx_pad[np.arange(N), :, pad:H+pad, pad:W+pad] # padding 제거한 값
 

Briefly:

Just as spatial_out was used to construct the full output, crop dspatial_out of shape (N, F) from dout and calculate the gradients. Remember that the output was computed from padded x: accumulate gradients in dx_pad, then remove the padding before assigning the result to dx.

I drew the backward graph too, but it was too messy to post. I want an iPad...

 

Reflections

I almost ended up with four nested for loops.

I was unsure which dimensions to slide over, so I initially looped over N, F, H, and W. After implementing it once, I saw how to vectorize N and F. I rewrote it, and it worked. What a satisfying moment. That is about it.

 

Read next