Patches of a picture
You will learn
Why networks read a picture in patches, and what a 2 x 2 window averaged over each patch gives.
A picture is a grid of numbers, and networks read it in small patches so that the same detector works anywhere in it. Here a 2 x 2 window steps by 2 over a 4 x 4 image whose cell i holds i, and each output is the average of its patch: 2.5, 4.5, 10.5 and 12.5. In the backward pass each output's gradient is split equally over its 4 cells. This is average pooling: a convolution would weight the 4 cells with a learned kernel, and its spec, t27#10612, is not merged yet. The spec avgpool2d_layer.t27 computes both passes.
Try it
Tap each patch and check its average by eye; then switch to the gradient and read what each cell of window 4 receives.
Tap a window on the 4 x 4 image: each output is the average of its 2 x 2 patch, two cells apart. Then switch to the gradient and see each output's blame shared out over its patch.
specs/ml/layers/avgpool2d_layer.t27
// SPDX-License-Identifier: Apache-2.0
// t27/specs/
// 2D average pooling formula | φ² + 1/φ² = 3 | TRINITY
// #8980: the kernel and stride were string constants typed `[]u32`, forward only
// asserted that its input was non-empty, and the tests asserted `true` or
// `result != undefined`. Average pooling now runs over one square H x H channel
// with the default 2 x 2 window and stride 2 and no padding, and each test checks
// numbers.
module Avgpool2d;
use base::types;
use math::constants;
// ═══════════════════════════════════════════════════════════
// 1. Constants
// ═══════════════════════════════════════════════════════════
const DEFAULT_KERNEL : u32 = 2;
const DEFAULT_STRIDE : u32 = 2;
// ═══════════════════════════════════════════════════════════
// 2. Types
// ═══════════════════════════════════════════════════════════
pub const PoolConfig = struct {
kernel_size : []u32,
stride : []u32,
padding : []u32,
};
pub const PoolShape = struct {
batch : u32,
channels : u32,
height_in : u32,
width_in : u32,
height_out : u32,
width_out : u32,
};
// ═══════════════════════════════════════════════════════════
// 3. Core Functions
// ═══════════════════════════════════════════════════════════
// Output side for an input side n: (n - k) / stride + 1, and 0 when no window fits
fn calc_output_size(height_in: u32) -> u32 {
if (height_in < DEFAULT_KERNEL) {
return 0;
}
return (height_in - DEFAULT_KERNEL) / DEFAULT_STRIDE + 1;
}
// output[oy][ox] = mean of the k x k window at (oy * stride, ox * stride) of a side x side
// input; returns the number of outputs written
fn forward(input: []const f32, side: u32, output: []f32) -> u32 {
const n = calc_output_size(side);
const area : f32 = @as(f32, @floatFromInt(DEFAULT_KERNEL * DEFAULT_KERNEL));
var oy : u32 = 0;
while (oy < n) {
var ox : u32 = 0;
while (ox < n) {
var sum : f32 = 0.0;
var ky : u32 = 0;
while (ky < DEFAULT_KERNEL) {
var kx : u32 = 0;
while (kx < DEFAULT_KERNEL) {
sum = sum + input[(oy * DEFAULT_STRIDE + ky) * side + ox * DEFAULT_STRIDE + kx];
kx = kx + 1;
}
ky = ky + 1;
}
output[oy * n + ox] = sum / area;
ox = ox + 1;
}
oy = oy + 1;
}
return n * n;
}
// backward: each window's gradient is shared equally by its k * k inputs
fn backward(grad_output: []const f32, side: u32, grad_input: []f32) -> void {
const n = calc_output_size(side);
const area : f32 = @as(f32, @floatFromInt(DEFAULT_KERNEL * DEFAULT_KERNEL));
var i : usize = 0;
while (i < grad_input.len) {
grad_input[i] = 0.0;
i = i + 1;
}
var oy : u32 = 0;
while (oy < n) {
var ox : u32 = 0;
while (ox < n) {
var ky : u32 = 0;
while (ky < DEFAULT_KERNEL) {
var kx : u32 = 0;
while (kx < DEFAULT_KERNEL) {
const idx = (oy * DEFAULT_STRIDE + ky) * side + ox * DEFAULT_STRIDE + kx;
grad_input[idx] = grad_input[idx] + grad_output[oy * n + ox] / area;
kx = kx + 1;
}
ky = ky + 1;
}
ox = ox + 1;
}
oy = oy + 1;
}
}
// 4 x 4 input 0..15, row-major: windows average to 2.5, 4.5, 10.5, 12.5
fn pool4_at(index: usize) -> f32 {
var input : [16]f32 = [0.0] ** 16;
var i : usize = 0;
while (i < 16) {
input[i] = @as(f32, @floatFromInt(i));
i = i + 1;
}
var output : [4]f32 = [0.0] ** 4;
_ = forward(&input, 4, &output);
return output[index];
}
// forward over a 2 x 2 input (1, 2, 3, 4) or a 1 x 1 input (5); returns the outputs written
fn pool_count(side: u32) -> u32 {
const four : [4]f32 = [1.0, 2.0, 3.0, 4.0];
const one : [1]f32 = [5.0];
var output : [1]f32 = [-1.0];
if (side == 2) {
return forward(&four, 2, &output);
}
return forward(&one, 1, &output);
}
fn pool2_value() -> f32 {
const four : [4]f32 = [1.0, 2.0, 3.0, 4.0];
var output : [1]f32 = [-1.0];
_ = forward(&four, 2, &output);
return output[0];
}
fn backward4_at(index: usize) -> f32 {
const grad_output : [4]f32 = [4.0, 8.0, 12.0, 16.0];
var grad_input : [16]f32 = [9.0] ** 16;
backward(&grad_output, 4, &grad_input);
return grad_input[index];
}
fn valid_input() -> u32 {
return calc_output_size(4);
}
// ═══════════════════════════════════════════════════════════
// TDD: Tests (from .tri behaviors)
// ═══════════════════════════════════════════════════════════
test calc_output_size_basic_case
given result = calc_output_size(4)
then result == 2
test calc_output_size_valid_input
given input = 10
when result = calc_output_size(input)
then result == 5
// A 1 x 1 input holds no 2 x 2 window
test calc_output_size_small_input
given input = 1
when result = calc_output_size(input)
then result == 0 and calc_output_size(2) == 1
test calc_output_size_large_input
given input = 1000
when result = calc_output_size(input)
then result == 500 and calc_output_size(1001) == 500
test forward_basic_case
given first = pool4_at(0)
when last = pool4_at(3)
then first == 2.5 and pool4_at(1) == 4.5 and pool4_at(2) == 10.5 and last == 12.5
// A 2 x 2 input is one window: the mean of 1, 2, 3, 4
test forward_non_empty_input
given count = pool_count(2)
when value = pool2_value()
then count == 1 and value == 2.5
test forward_single_element
given count = pool_count(1)
then count == 0
// Each of a window's 4 inputs gets a quarter of its gradient
test backward_spreads_the_gradient
given corner = backward4_at(0)
when last = backward4_at(15)
then corner == 1.0 and backward4_at(5) == 1.0 and backward4_at(2) == 2.0 and last == 4.0
// ═══════════════════════════════════════════════════════════
// TDD: Invariants (from .tri constraints)
// ═══════════════════════════════════════════════════════════
// kernel_size[i] >= 1
invariant avgpool2d_constraint_0
assert DEFAULT_KERNEL >= 1
// stride[i] >= 1
invariant avgpool2d_constraint_1
assert DEFAULT_STRIDE >= 1
// stride[i] <= kernel_size[i]: windows tile the input without gaps
invariant avgpool2d_constraint_2
assert DEFAULT_STRIDE <= DEFAULT_KERNEL
// name: avgpool_formula -- (n - k) / s + 1
invariant avgpool2d_constraint_3
assert valid_input() == 2
// "Zeiler & Fergus (2014) - Visualizing and Understanding Convolutional Networks": pooling halves each side
invariant avgpool2d_constraint_4
assert calc_output_size(8) == 4
// "He et al. (2016) - Deep Residual Learning for Image Recognition": a 7 x 7 map pools to 3 x 3
invariant avgpool2d_constraint_5
assert calc_output_size(7) == 3
All lessons
Module 1 · One neuron
A neuron sums its inputs and bends the sum: ReLU, the sigmoid and tanh, and where each one stops passing a gradient back.
Module 2 · New bends
The smooth curves of current models: GELU with its dip, Swish with its knob, and ELU with a floor instead of a cliff.
Module 3 · A layer
What sits around the neurons: softmax turns scores into a choice, an embedding turns a word into numbers, dropout switches units off.
Module 4 · Pictures
Reading a picture in patches: a window averaged over its patch, max pooling, and batch normalisation of features on different scales.
Module 5 · The error
How wrong a guess is, as one number: mean squared error, cross-entropy for probabilities, and the Huber loss for outliers.
Module 6 · Downhill
Walking down the loss: gradient descent with momentum, RMSProp that ignores the gradient's size, and Adam that combines them.
Module 7 · Learning
Where the gradients come from and what they achieve: backpropagation through a layer, a network that learns XOR, and LAMB for large batches.
Module 8 · Memory and attention
Networks that read a sequence: a recurrent cell and its fading echo, the gates of an LSTM, and attention over every position at once.
Module 9 · The transformer and the reward
The parts of a transformer and of an agent: positions as clocks, one encoder block, and PPO, which learns from reward without lurching.