Deep learning: Gradients of a convolution

Compute what backpropagation needs from a convolution layer.

What to build

A program that computes the gradients of a valid, stride-1 convolution with respect to its kernel and its input.

Requirements

  • The forward pass is Y[i][j] = Σₐ Σ_b X[i + a][j + b] K[a][b]. Given dY, the gradient of the loss with respect to Y, compute dK and dX.
  • Print dK: and its rows, then dX: and its rows, values written with Python's g format.

Input

Line 1: X's height and width, then its rows. Then K's height and width, then its rows. Then dY's rows (its size follows from X and K).

Output

dK:, the dK rows, dX:, the dX rows.

Constraints

X up to 10 × 10; K up to 5 × 5.

Example

Input:

3 3
1 2 3
4 5 6
7 8 9
2 2
1 0
0 1
1 0
0 0

Output:

dK:
1 2
4 5
dX:
1 0 0
0 1 0
0 0 0

Why it works

Every kernel weight touched many input values, so its gradient collects one contribution from each output; every input value met several kernel weights, so its gradient collects those in return.

Examples

Example 1 · Input
3 3
1 2 3
4 5 6
7 8 9
2 2
1 0
0 1
1 0
0 0
Expected output
dK:
1 2
4 5
dX:
1 0 0
0 1 0
0 0 0
Example 2 · Input
2 2
1 2
3 4
1 1
3
1 1
1 1
Expected output
dK:
10
dX:
3 3
3 3

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

dK[a][b] = Σ over outputs (i, j) of dY[i][j] × X[i + a][j + b].

Hint 2

For every output (i, j), add dY[i][j] × K[a][b] to dX[i + a][j + b] for every kernel position (a, b).

Solution

Show one correct solution (try it yourself first)
h, w = map(int, input().split())
X = [list(map(float, input().split())) for _ in range(h)]
kh, kw = map(int, input().split())
K = [list(map(float, input().split())) for _ in range(kh)]
oh, ow = h - kh + 1, w - kw + 1
dY = [list(map(float, input().split())) for _ in range(oh)]
dK = [[sum(dY[i][j] * X[i + a][j + b] for i in range(oh) for j in range(ow)) for b in range(kw)] for a in range(kh)]
dX = [[0.0] * w for _ in range(h)]
for i in range(oh):
    for j in range(ow):
        for a in range(kh):
            for b in range(kw):
                dX[i + a][j + b] += dY[i][j] * K[a][b]
print("dK:")
for row in dK:
    print(" ".join(f"{v + 0.0:g}" for v in row))
print("dX:")
for row in dX:
    print(" ".join(f"{v + 0.0:g}" for v in row))

Lesson: Convolutions →