Deep Learning · TEE · section

F23 Q1d

Final examination December 2023 fully solved

Question

Question (5 marks). Compute the convolution using the input A and kernel K shown below using padding 0 and stride 1.

Given matrices
Input A
10956
5767
3328
3267
Kernel K
111
121
111

Stride 1; P = 0 (no padding).

Answer — step by step

Given

Compute the convolution using the input A and kernel K shown below using padding 0 and stride 1.

To find

Find every convolution output cell.

Formula — which one and why

Convolution values. At each valid location, multiply corresponding window and kernel entries, add all products and add the filter bias once. Move by the stated stride and repeat.

X = input; K = kernel; S = stride; b = filter bias; u,v locate a kernel entry. Use the printed kernel without flipping under the stated deep-learning convention.

Y_{ij}=\sum_{u,v}X_{iS+u,jS+v}K_{uv}+bLaTeX: Y_{ij}=\sum_{u,v}X_{iS+u,jS+v}K_{uv}+b

Yaad rakhne ka cue: Matching cells multiply; sab products add; bias sirf ek baar.

Solution — step by step

Follow each selected input window below. Matching row colors connect its input cells, kernel coefficients and products; the outlined output cell shows where their sum belongs.

Step 1 shape: \left\lfloor\frac{4+2 \times 0-3}{1}\right\rfloor+1LaTeX: \left\lfloor\frac{4+2 \times 0-3}{1}\right\rfloor+1 = 2 along each axis. Use the deep-learning cross-correlation convention: do not flip the printed kernel.

Output position (1, 1)

Use this position's input window. Multiply corresponding entries row by row; then add all row totals.

Follow window (1, 1) into one output cell

Input rows 1–3, columns 1–3. The window moves 1 cell per output step.

1. Select the input window
10956
5767
3328
3267

Only the outlined cells belong to this output.

2. Match the kernel
111
121
111

Same row and column positions; no matrix multiplication.

3. Multiply cell by cell
1095
5146
332

Each cell is input × matching kernel coefficient.

4. Add the products row by row
Row 110 + 9 + 5 = 24
Row 25 + 14 + 6 = 25
Row 33 + 3 + 2 = 8

24 + 25 + 8 = 57

5. Place it in the output
5759
4050

Output row 1, column 1.

Window row 1.

R_1=(10)\times(1)+(9)\times(1)+(5)\times(1)=24LaTeX: R_1=(10)\times(1)+(9)\times(1)+(5)\times(1)=24

Window row 2.

R_2=(5)\times(1)+(7)\times(2)+(6)\times(1)=25LaTeX: R_2=(5)\times(1)+(7)\times(2)+(6)\times(1)=25

Window row 3.

R_3=(3)\times(1)+(3)\times(1)+(2)\times(1)=8LaTeX: R_3=(3)\times(1)+(3)\times(1)+(2)\times(1)=8

Add the rows to obtain one output cell.

Y_{1,1}=(24)+(25)+(8)=57LaTeX: Y_{1,1}=(24)+(25)+(8)=57

Output position (1, 2)

Use this position's input window. Multiply corresponding entries row by row; then add all row totals.

Follow window (1, 2) into one output cell

Input rows 1–3, columns 2–4. The window moves 1 cell per output step.

1. Select the input window
10956
5767
3328
3267

Only the outlined cells belong to this output.

2. Match the kernel
111
121
111

Same row and column positions; no matrix multiplication.

3. Multiply cell by cell
956
7127
328

Each cell is input × matching kernel coefficient.

4. Add the products row by row
Row 19 + 5 + 6 = 20
Row 27 + 12 + 7 = 26
Row 33 + 2 + 8 = 13

20 + 26 + 13 = 59

5. Place it in the output
5759
4050

Output row 1, column 2.

Window row 1.

R_1=(9)\times(1)+(5)\times(1)+(6)\times(1)=20LaTeX: R_1=(9)\times(1)+(5)\times(1)+(6)\times(1)=20

Window row 2.

R_2=(7)\times(1)+(6)\times(2)+(7)\times(1)=26LaTeX: R_2=(7)\times(1)+(6)\times(2)+(7)\times(1)=26

Window row 3.

R_3=(3)\times(1)+(2)\times(1)+(8)\times(1)=13LaTeX: R_3=(3)\times(1)+(2)\times(1)+(8)\times(1)=13

Add the rows to obtain one output cell.

Y_{1,2}=(20)+(26)+(13)=59LaTeX: Y_{1,2}=(20)+(26)+(13)=59

Output position (2, 1)

Use this position's input window. Multiply corresponding entries row by row; then add all row totals.

Follow window (2, 1) into one output cell

Input rows 2–4, columns 1–3. The window moves 1 cell per output step.

1. Select the input window
10956
5767
3328
3267

Only the outlined cells belong to this output.

2. Match the kernel
111
121
111

Same row and column positions; no matrix multiplication.

3. Multiply cell by cell
576
362
326

Each cell is input × matching kernel coefficient.

4. Add the products row by row
Row 15 + 7 + 6 = 18
Row 23 + 6 + 2 = 11
Row 33 + 2 + 6 = 11

18 + 11 + 11 = 40

5. Place it in the output
5759
4050

Output row 2, column 1.

Window row 1.

R_1=(5)\times(1)+(7)\times(1)+(6)\times(1)=18LaTeX: R_1=(5)\times(1)+(7)\times(1)+(6)\times(1)=18

Window row 2.

R_2=(3)\times(1)+(3)\times(2)+(2)\times(1)=11LaTeX: R_2=(3)\times(1)+(3)\times(2)+(2)\times(1)=11

Window row 3.

R_3=(3)\times(1)+(2)\times(1)+(6)\times(1)=11LaTeX: R_3=(3)\times(1)+(2)\times(1)+(6)\times(1)=11

Add the rows to obtain one output cell.

Y_{2,1}=(18)+(11)+(11)=40LaTeX: Y_{2,1}=(18)+(11)+(11)=40

Output position (2, 2)

Use this position's input window. Multiply corresponding entries row by row; then add all row totals.

Follow window (2, 2) into one output cell

Input rows 2–4, columns 2–4. The window moves 1 cell per output step.

1. Select the input window
10956
5767
3328
3267

Only the outlined cells belong to this output.

2. Match the kernel
111
121
111

Same row and column positions; no matrix multiplication.

3. Multiply cell by cell
767
348
267

Each cell is input × matching kernel coefficient.

4. Add the products row by row
Row 17 + 6 + 7 = 20
Row 23 + 4 + 8 = 15
Row 32 + 6 + 7 = 15

20 + 15 + 15 = 50

5. Place it in the output
5759
4050

Output row 2, column 2.

Window row 1.

R_1=(7)\times(1)+(6)\times(1)+(7)\times(1)=20LaTeX: R_1=(7)\times(1)+(6)\times(1)+(7)\times(1)=20

Window row 2.

R_2=(3)\times(1)+(2)\times(2)+(8)\times(1)=15LaTeX: R_2=(3)\times(1)+(2)\times(2)+(8)\times(1)=15

Window row 3.

R_3=(2)\times(1)+(6)\times(1)+(7)\times(1)=15LaTeX: R_3=(2)\times(1)+(6)\times(1)+(7)\times(1)=15

Add the rows to obtain one output cell.

Y_{2,2}=(20)+(15)+(15)=50LaTeX: Y_{2,2}=(20)+(15)+(15)=50

Final output: \begin{bmatrix}57 & 59\\40 & 50\end{bmatrix}LaTeX: \begin{bmatrix}57 & 59\\40 & 50\end{bmatrix}. Each output came from its own complete window; stride changes the next window position, not the multiplication rule.