Convolutional Networks (CNN)

Code

Convolution — fill in two holes

In the last step you saw a convolution in tables. Now the same thing is written as a Python function — and you fill in the two missing pieces.

The algorithm

out ← table of zeros [H - kh + 1, W - kw + 1]
for each row i:
    for each column j:
        patch ← image[i .. i+kh, j .. j+kw]
        out[i, j] ← sum( patch * filter )     # cell by cell
return out

This is exactly what you did to get 27: a patch, the cell-by-cell product, the sum. Two loops just repeat it for every position.

Your job

Create two files in the project folder (see the right panel): conv_by_hand.py and test_cnn.py.

conv_by_hand.py is complete and runnable, but wrong: the loops are written, two places are missing. They are marked HOLE 1 and HOLE 2:

HOLE 1 — the patch. Right now image[:kh, :kw] always takes the same corner. Rewrite it so the corner is (i, j).
HOLE 2 — one line: multiply the patch by the filter cell by cell and add it up. Right now it holds 0.0.

Nothing else needs to change.

test_cnn.py is the verdict — you do not write it, you pass it. For now it only tests the convolution: the output shape, the very numbers you saw in step 2 (27, 36, −27 …), and a comparison with F.conv2d on random numbers.

Run it before filling anything in

Run it exactly as it is. From the project folder:

$ python -m unittest test_cnn
F.F
======================================================================
FAIL: test_matches_torch_on_random_input (test_cnn.ConvByHandTest.test_matches_torch_on_random_input)
----------------------------------------------------------------------
Traceback (most recent call last):
  ...
AssertionError: Tensor-likes are not close!

Mismatched elements: 63 / 63 (100.0%)
Greatest absolute difference: 10.376058578491211 at index (4, 3) (up to 1e-05 allowed)
Greatest relative difference: 1.0 at index (0, 0) (up to 1.3e-06 allowed)

======================================================================
FAIL: test_the_numbers_from_the_lesson (test_cnn.ConvByHandTest.test_the_numbers_from_the_lesson)
----------------------------------------------------------------------
Traceback (most recent call last):
  ...
AssertionError: False is not true : got
tensor([[0., 0., 0., 0.],
        [0., 0., 0., 0.],
        [0., 0., 0., 0.],
        [0., 0., 0., 0.]])

----------------------------------------------------------------------
Ran 3 tests in 0.590s

FAILED (failures=2)

(Shortened: the Traceback bodies are cut, and your timing and paths will differ.)

That is not an error — it is the starting point. F.F means: the shape is right (the middle test passed) and every number is zero. The skeleton never looks at the picture.

Fill in both holes and run again — you should see OK.

When it does not pass

Every number in the map is the same (27) — you left image[:kh, :kw]. The patch does not slide.
RuntimeError: The size of tensor a (2) must match the size of tensor b (3) — the patch is too small (e.g. i : i + kh - 1). It must be exactly kh × kw. You also get it when you swap i and j between rows and columns.
Numbers different but the right size — HOLE 2 forgot the filter (patch.sum()) or uses .mean() (the result is 9 times too small).
RuntimeError: expand(torch.FloatTensor{[3, 3]}, size=[]) — you wrote patch @ kernel. That is a matrix product, which returns another 3 × 3 table, and a single cell only holds one number. You need * and .sum().

conv_by_hand.py CREATE

Create this file in ./

"""conv_by_hand.py — a convolution written with plain loops."""

import torch


def conv2d_by_hand(image: torch.Tensor, kernel: torch.Tensor) -> torch.Tensor:
    """Slide kernel over image (no padding, stride 1) and return the feature map.

    image: [H, W]   kernel: [kh, kw]   result: [H - kh + 1, W - kw + 1]
    Every output number is the sum of (patch * kernel), where patch is the
    kh x kw piece of the image that lies under the kernel at that position.
    """
    h, w = image.shape
    kh, kw = kernel.shape
    out = torch.zeros(h - kh + 1, w - kw + 1)
    for i in range(out.shape[0]):
        for j in range(out.shape[1]):
            # HOLE 1: cut out the kh x kw patch whose top-left corner is (i, j).
            patch = image[:kh, :kw]
            # HOLE 2: multiply patch and kernel element by element, add it all up.
            out[i, j] = 0.0
    return out

test_cnn.py CREATE

Create this file in ./

"""test_cnn.py — the verdict. Run: python -m unittest -v"""

import unittest

import torch
import torch.nn.functional as F

from conv_by_hand import conv2d_by_hand

# The 6x6 picture from the lesson: a bright 3x3 square on a dark background.
SQUARE = torch.tensor(
    [
        [0, 0, 0, 0, 0, 0],
        [0, 9, 9, 9, 0, 0],
        [0, 9, 9, 9, 0, 0],
        [0, 9, 9, 9, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
    ],
    dtype=torch.float32,
)
# Responds where brightness grows from left to right (a vertical edge).
EDGE = torch.tensor([[-1.0, 0.0, 1.0], [-2.0, 0.0, 2.0], [-1.0, 0.0, 1.0]])


class ConvByHandTest(unittest.TestCase):
    def test_output_shape(self):
        out = conv2d_by_hand(torch.zeros(28, 28), EDGE)
        self.assertEqual(tuple(out.shape), (26, 26))

    def test_the_numbers_from_the_lesson(self):
        out = conv2d_by_hand(SQUARE, EDGE)
        expected = torch.tensor(
            [
                [27.0, 0.0, -27.0, -27.0],
                [36.0, 0.0, -36.0, -36.0],
                [27.0, 0.0, -27.0, -27.0],
                [9.0, 0.0, -9.0, -9.0],
            ]
        )
        self.assertTrue(torch.equal(out, expected), f"got\n{out}")

    def test_matches_torch_on_random_input(self):
        g = torch.Generator().manual_seed(0)
        image = torch.randn(9, 11, generator=g)
        kernel = torch.randn(3, 3, generator=g)
        want = F.conv2d(image.reshape(1, 1, 9, 11), kernel.reshape(1, 1, 3, 3))[0, 0]
        torch.testing.assert_close(conv2d_by_hand(image, kernel), want)


if __name__ == "__main__":
    unittest.main()