Hard Primitives

Implement 1D Convolution

A 1D cross-correlation slides a short weight vector (the kernel) along an input vector. At each position, multiply matching entries, sum the products, and add a bias. Keep the kernel in its given order; do not flip it.

For x = [1, 2, 3, 4, 5], weight = [2, -1], bias = 0.5, and stride = 2, the windows start at indices 0 and 2:

[1, 2] gives 1*2 + 2*(-1) + 0.5 = 0.5.
[3, 4] gives 3*2 + 4*(-1) + 0.5 = 2.5.

The output is [0.5, 2.5]. A window starting at index 4 would extend past the input, so it is omitted. Stride sets the distance between window starts; it does not skip entries inside a window.

Your task

Implement conv1d(x, weight, bias, stride=1):

x has shape (L,) and weight has shape (K,), with 1 <= K <= L. They have matching floating-point dtypes and devices.
bias is a Python float added once to each output element.
stride is a positive integer. There is no padding or dilation.
Return a tensor of shape ((L - K) // stride + 1,).

For output index i, use the window beginning at i * stride. In formula form, output[i] = sum(x[i * stride + k] * weight[k] for k in range(K)) + bias. Use basic tensor operations rather than a built-in convolution operation.

The diagram shows one-dimensional window positions rather than numerical products. Keep padding at 0 and dilation at 1 to match this exercise.

Loading visualization…

Understand the ideas behind this exercise. The Problem tab contains the exact implementation requirements.

Apply the same filter at many locations

A convolutional layer slides a learned kernel over its input. At each location, it multiplies the covered values by the kernel weights and sums them. Deep-learning libraries usually implement cross-correlation under the name convolution: the kernel is not reversed.

For input [1, 2, 3] and kernel [1, -1], with no padding and stride one, the outputs are 1*1 + 2*(-1) = -1 and 2*1 + 3*(-1) = -1.

Work out the output shape

For one spatial axis, the output length is

$$\left\lfloor\frac{L+2P-D(K-1)-1}{S}\right\rfloor+1.$$

L is the input length, K the kernel size, P the padding on each end, S the stride between windows, and D the spacing between kernel elements (dilation). For a 2D input, apply the formula separately to height and width. Check the channel layout too: an ordinary convolution sums over both spatial positions in the window and input channels.

A depthwise convolution filters each input channel separately. A following pointwise convolution, using a 1-by-1 spatial kernel, mixes channels. This uses a different set of parameters from a full spatial convolution; the two constructions are not generally interchangeable.

Pool nearby features

Max pooling keeps the largest value in each window. Average pooling takes the window's mean. During backpropagation, max pooling sends the gradient to the selected position, while average pooling distributes it across the values that contributed to the mean. Overlapping windows can contribute more than once to the same input position, so add those gradients.

Follow the exercise's rules for tied maxima and whether padding counts in an average. For a small CNN, also save the forward-pass values needed for activation and pooling derivatives. Add each shared kernel's gradient contributions across all locations, then update weights after computing all gradients.

Detecting runtime…

Implement 1D Convolution

Your task

Apply the same filter at many locations

Work out the output shape

Pool nearby features

Your code, saved here

Stuck?

PyTorch reference solution