Finding Patterns

D

Our next model handles images. We will use it on the Fashion-MNIST dataset. The dataset contains 70,000 images, each showing one item: a T-shirt, a dress, a coat, etc.

D

We begin with a baby step, detecting signals in rank-1 tensors.
Here's a signal:
Tensor([0, 1.0, 0, 0, 0]).
Let's check if it contains the pattern
Tensor([0, 1.0, 0]).
We align the pattern with the left end of the signal, and slide the pattern all the way to the right. For each segment in the signal, we compute a score of how well it matches the pattern.

D

The score is the dot product between the pattern and the segment, which must have the same shape.

from pypie import op, Tensor

@op
def dot[n](s: Tensor[float][[n]], p: Tensor[float][[n]]) -> float:
    return (p * s).sum(0)

D

Next, we slide the pattern and compute dot on every segment. This function is called corr1d, short for rank-1 correlation.

from pypie import iota

@op
def corr1d[w, n](
    s: Tensor[float][[w]],
    p: Tensor[float][[n]]
) -> Tensor[float][[w - n + 1]]:
    return [
        dot(s[idx : idx + n], p)
        for idx in iota(w - n + 1)
    ]

It's a long function. Let's start with its type.

D

It does. [... for ... in ...] is a tensor comprehension.
Here's how corr1d slides across the signal:
iota gives us a Tensor[int][[w - n + 1]]: from 0 to w - n. We use these ints as the starting indices of the segments;
for each index, we take n elements from the signal to compute the dot product.
Let's run our example.

D

Now let's improve the coverage.

D

The coverage of the elements at the beginning and end of the signal.
Our corr1d underutilizes the first and last elements of the signal--each is used only once, while the middle element is used three times.
To use elements more evenly, we can pad the signal before computing corr1d.
pad1d builds zero tensors with replicate, then uses concat to put one on each side of xs.

@op
def pad1d[T, w](
    xs: Tensor[T][[w]],
    padding: int
) -> Tensor[T][[2 * padding + w]]:
    side_padding = replicate(padding, 0)
    return concat(concat(side_padding, xs), side_padding)

pad1d returns 2 * padding + w elements.
Extend corr1d with padding. How many elements does it return?

D

Next, let's make corr1d more flexible.
In our example, corr1d advances one element at a time.
In some cases, we might want to advance by two or three elements at a time.
To do that, we need a new function to generate indices.

@op
def seq(
    start: int,
    end: int,
    stride: int
) -> Tensor[int][[(end - start) / stride]]:
    size = (end - start) / stride
    return iota(size) * stride + start

For example, seq(0, 10, 2) gives Tensor([0, 2, 4, 6, 8]).
Create a new version of corr1d to use indices with flexible strides. How many elements does it return?

D

Excellent! We are ready to detect patterns in images.
Here's the template for corr2d, which handles padding, strides, and the sliding windows.

@op
def corr2d[h, w, m, n](
    s: Tensor[float][[h, w]],
    p: Tensor[float][[m, n]],
    stride0: int,
    stride1: int,
    padding0: int,
    padding1: int
) -> Tensor[float][
    [
        (h + 2 * padding0 - m + stride0) / stride0,
        (w + 2 * padding1 - n + stride1) / stride1
    ]
]:
    padded = pad2d(s, padding0, padding1)
    return [
        [
            ...
            for i in seq(0, w + 2 * padding1 - n + stride1, stride1)
        ]
        for j in seq(0, h + 2 * padding0 - m + stride0, stride0)
    ]

j is the index along h, sliding from top to bottom. i is the index along w, sliding from left to right.
We need functions for padding and dot products for rank-2 tensors. Define pad2d first by reusing pad1d on each row, then concatenating zero rows above and below.

D

Very well.
Here's the next helper: dot2d.

@op
def dot2d[m, n](s: Tensor[float][[m, n]], p: Tensor[float][[m, n]]) -> float:
    ...

dot2d takes two tensors with the same shape, so corr2d can pass the current slice of s directly.
Complete dot2d.

D

Exactly. Now we can finish corr2d, and make corr2d_with_bias the small bias wrapper.

@op
def corr2d[h, w, m, n](
    s: Tensor[float][[h, w]],
    p: Tensor[float][[m, n]],
    stride0: int,
    stride1: int,
    padding0: int,
    padding1: int
) -> Tensor[float][
    [
        (h + 2 * padding0 - m + stride0) / stride0,
        (w + 2 * padding1 - n + stride1) / stride1
    ]
]:
    padded = pad2d(s, padding0, padding1)
    return [
        [
            dot2d(padded[j : j + m, i : i + n], p)
            for i in seq(0, w + 2 * padding1 - n + stride1, stride1)
        ]
        for j in seq(0, h + 2 * padding0 - m + stride0, stride0)
    ]

@op
def corr2d_with_bias[h, w, m, n](
    s: Tensor[float][[h, w]],
    p: Tensor[float][[m, n]],
    bias: float,
    stride0: int,
    stride1: int,
    padding0: int,
    padding1: int
) -> Tensor[float][
    [
        (h + 2 * padding0 - m + stride0) / stride0,
        (w + 2 * padding1 - n + stride1) / stride1
    ]
]:
    return corr2d(s, p, stride0, stride1, padding0, padding1) + bias

D

It needs two more pieces:
input channels and output channels.

D

Sometimes our inputs have a rank higher than 2. For example, RGB images are Tensor[float][[3, h, w]], where each Tensor[float][[h, w]] stores the intensity of red, green, or blue.
Sometimes our outputs need a combination of patterns: rising edges, falling edges, and maybe curves.

D

corr2d_multi_in expects rank-3 tensors for s and p--one pattern for each input channel.

@op
def corr2d_multi_in[c, h, w, m, n](
    s: Tensor[float][[c, h, w]],
    p: Tensor[float][[c, m, n]],
    bias: float,
    stride0: int,
    stride1: int,
    padding0: int,
    padding1: int
) -> Tensor[float][
    [
        (h + 2 * padding0 - m + stride0) / stride0,
        (w + 2 * padding1 - n + stride1) / stride1
    ]
]:
    return corr2d(s, p, stride0, stride1, padding0, padding1).sum(0) + bias

In the returned value, what's the type of calling corr2d?

D

Yes. We can specify dimensions for sum. Here, sum collapses the first dimension, c, producing the expected rank-2 tensor.

D

Next, for multiple output channels, we pass the output-channel weights and biases separately.

@op
def corr2d_multi_in_out[o, i, h, width, m, n](
    s: Tensor[float][[i, h, width]],
    w: Tensor[float][[o, i, m, n]],
    b: Tensor[float][[o]],
    stride0: int,
    stride1: int,
    padding0: int,
    padding1: int
) -> Tensor[float][
    [
        o,
        (h + 2 * padding0 - m + stride0) / stride0,
        (width + 2 * padding1 - n + stride1) / stride1
    ]
]:
    return corr2d_multi_in(s, w, b, stride0, stride1, padding0, padding1)

D

corr2d_multi_in_out detects patterns at pixel-level granularity.
The same patterns, however, do not necessarily occur in the same position in all images. For example, although all T-shirt images should have a rising edge near the top-left area, one image might have the edge at (0, 1), and another may have it at (1, 2).

D

We shrink the image with pooling.

@op
def mean2d[m, n](
    x: Tensor[float][[m, n]],
    h: int,
    w: int,
    x_j: int,
    x_i: int
) -> float:
    return [
        [
            x[j + x_j][i + x_i]
            for i in iota(w)
        ]
        for j in iota(h)
    ].mean()

@op
def pool2d[m, n](
    x: Tensor[float][[m, n]],
    h: int,
    w: int,
    stride0: int,
    stride1: int,
    padding0: int,
    padding1: int
) -> Tensor[float][
    [
        (m + 2 * padding0 - h + stride0) / stride0,
        (n + 2 * padding1 - w + stride1) / stride1
    ]
]:
    padded = pad2d(x, padding0, padding1)
    return [
        [
            mean2d(padded, h, w, j, i)
            for i in seq(0, n + 2 * padding1 - w + stride1, stride1)
        ]
        for j in seq(0, m + 2 * padding0 - h + stride0, stride0)
    ]

Here, we reduce each h * w block to one value by taking the average of all elements in the block.

D

We now have most of the ingredients for the famous LeNet.
It takes images of size 28 * 28, with 1 input channel,
and generates likelihood scores for 10 items.

from pypie import larger

class LeNet(Model):
    def predict[h, w](
        x: Tensor[float][[1, h, w]],
        params: Tuple[
            Tensor[float][[6, 1, 5, 5]],
            Tensor[float][[6]],
            Tensor[float][[16, 6, 5, 5]],
            Tensor[float][[16]],
            ...
        ]
    ) -> Tensor[float][[10]]:
        (p1, b1, p2, b2, ...) = params
        layer1 = larger(corr2d_multi_in_out(x, p1, b1, 1, 1, 2, 2), 0)
        layer2 = pool2d(layer1, 2, 2, 2, 2, 0, 0)
        layer3 = larger(corr2d_multi_in_out(layer2, p2, b2, 1, 1, 0, 0), 0)
        layer4 = pool2d(layer3, 2, 2, 2, 2, 0, 0)
        ...

p1 is the pattern tensor for the first round of correlation: it has 1 input channel to match x, and 6 output channels. b1 has one bias per output channel.
p2 and b2 do the same for the second round: 6 input channels and 16 output channels.

D

larger is an activation function. Activation functions add non-linearity so each layer remains expressive. Otherwise, two consecutive linear layers would collapse into a single linear layer.
Here, we achieve non-linearity by simply replacing negative values with 0.

D

Right. Our model can only detect patterns--it does not reason about them yet.
We will complete LeNet in the next chapter, and run it on Fashion-MNIST!