{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-1 fw=all -->\n",
    "\n",
    "# Convolutions for Images\n",
    "\n",
    "Now that we understand how convolutional layers work in theory,\n",
    "we are ready to see how they work in practice.\n",
    "Building on our motivation of convolutional neural networks\n",
    "as efficient architectures for exploring structure in image data,\n",
    "we stick with images as our running example."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-convolutions-for-images"
   },
   "source": [
    "from d2l import torch as d2l\n",
    "import torch\n",
    "from torch import nn\n",
    "from torch.nn import functional as F"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-2 fw=all -->\n",
    "\n",
    "## The Cross-Correlation Operation\n",
    "\n",
    "Recall that strictly speaking, convolutional layers\n",
    "are a  misnomer, since the operations they express\n",
    "are more accurately described as cross-correlations.\n",
    "Based on our descriptions of convolutional layers in that section,\n",
    "in such a layer, an input tensor\n",
    "and a kernel tensor are combined\n",
    "to produce an output tensor through a cross-correlation operation.\n",
    "\n",
    "Let's ignore channels for now and see how this works\n",
    "with two-dimensional data and hidden representations.\n",
    "In the figure,\n",
    "the input is a two-dimensional tensor\n",
    "with a height of 3 and width of 3.\n",
    "We mark the shape of the tensor as $3 \\times 3$ or ($3$, $3$).\n",
    "The height and width of the kernel are both 2.\n",
    "The shape of the *kernel window* (or *convolution window*)\n",
    "is given by the height and width of the kernel\n",
    "(here it is $2 \\times 2$).\n",
    "\n",
    "![Two-dimensional cross-correlation operation. The shaded portions are the first output element as well as the input and kernel tensor elements used for the output computation: $0\\times0+1\\times1+3\\times2+4\\times3=19$.](../img/correlation.svg)\n",
    "\n",
    "In the two-dimensional cross-correlation operation,\n",
    "we begin with the convolution window positioned\n",
    "at the upper-left corner of the input tensor\n",
    "and slide it across the input tensor,\n",
    "both from left to right and top to bottom.\n",
    "When the convolution window slides to a certain position,\n",
    "the input subtensor contained in that window\n",
    "and the kernel tensor are multiplied elementwise\n",
    "and the resulting tensor is summed up\n",
    "yielding a single scalar value.\n",
    "This result gives the value of the output tensor\n",
    "at the corresponding location.\n",
    "Here, the output tensor has a height of 2 and width of 2\n",
    "and the four elements are derived from\n",
    "the two-dimensional cross-correlation operation:\n",
    "\n",
    "$$\n",
    "0\\times0+1\\times1+3\\times2+4\\times3=19,\\\\\n",
    "1\\times0+2\\times1+4\\times2+5\\times3=25,\\\\\n",
    "3\\times0+4\\times1+6\\times2+7\\times3=37,\\\\\n",
    "4\\times0+5\\times1+7\\times2+8\\times3=43.\n",
    "$$\n",
    "\n",
    "Note that along each axis, the output size\n",
    "is slightly smaller than the input size.\n",
    "Because the kernel has width and height greater than $1$,\n",
    "we can only properly compute the cross-correlation\n",
    "for locations where the kernel fits wholly within the image,\n",
    "the output size is given by the input size $n_\\textrm{h} \\times n_\\textrm{w}$\n",
    "minus the size of the convolution kernel $k_\\textrm{h} \\times k_\\textrm{w}$\n",
    "via\n",
    "\n",
    "$$(n_\\textrm{h}-k_\\textrm{h}+1) \\times (n_\\textrm{w}-k_\\textrm{w}+1).$$\n",
    "\n",
    "This is the case since we need enough space\n",
    "to \"shift\" the convolution kernel across the image.\n",
    "Later we will see how to keep the size unchanged\n",
    "by padding the image with zeros around its boundary\n",
    "so that there is enough space to shift the kernel.\n",
    "Next, we implement this process in the `corr2d` function,\n",
    "which accepts an input tensor `X` and a kernel tensor `K`\n",
    "and returns an output tensor `Y`."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-the-cross-correlation-operation-1"
   },
   "source": [
    "def corr2d(X, K):\n",
    "    \"\"\"Compute 2D cross-correlation.\"\"\"\n",
    "    h, w = K.shape\n",
    "    Y = d2l.zeros((X.shape[0] - h + 1, X.shape[1] - w + 1))\n",
    "    for i in range(Y.shape[0]):\n",
    "        for j in range(Y.shape[1]):\n",
    "            Y[i, j] = d2l.reduce_sum((X[i: i + h, j: j + w] * K))\n",
    "    return Y"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-3 fw=all -->\n",
    "\n",
    "We can construct the input tensor `X` and the kernel tensor `K`\n",
    "from the figure\n",
    "to validate the output of the above implementation\n",
    "of the two-dimensional cross-correlation operation."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-the-cross-correlation-operation-2"
   },
   "source": [
    "X = d2l.tensor([[0.0, 1.0, 2.0], [3.0, 4.0, 5.0], [6.0, 7.0, 8.0]])\n",
    "K = d2l.tensor([[0.0, 1.0], [2.0, 3.0]])\n",
    "corr2d(X, K)"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[19., 25.],\n        [37., 43.]])"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-4 fw=all -->\n",
    "\n",
    "## Convolutional Layers\n",
    "\n",
    "A convolutional layer cross-correlates the input and kernel\n",
    "and adds a scalar bias to produce an output.\n",
    "The two parameters of a convolutional layer\n",
    "are the kernel and the scalar bias.\n",
    "When training models based on convolutional layers,\n",
    "we typically initialize the kernels randomly,\n",
    "just as we would with a fully connected layer.\n",
    "\n",
    "We are now ready to implement a two-dimensional convolutional layer\n",
    "based on the `corr2d` function defined above.\n",
    "In the `__init__` constructor method,\n",
    "we declare `weight` and `bias` as the two model parameters.\n",
    "The forward propagation method\n",
    "calls the `corr2d` function and adds the bias."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-convolutional-layers"
   },
   "source": [
    "class Conv2D(nn.Module):\n",
    "    def __init__(self, kernel_size):\n",
    "        super().__init__()\n",
    "        self.weight = nn.Parameter(torch.rand(kernel_size))\n",
    "        self.bias = nn.Parameter(torch.zeros(1))\n",
    "\n",
    "    def forward(self, x):\n",
    "        return corr2d(x, self.weight) + self.bias"
   ],
   "execution_count": 4,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-5 fw=all -->\n",
    "\n",
    "In\n",
    "$h \\times w$ convolution\n",
    "or an $h \\times w$ convolution kernel,\n",
    "the height and width of the convolution kernel are $h$ and $w$, respectively.\n",
    "We also refer to\n",
    "a convolutional layer with an $h \\times w$\n",
    "convolution kernel simply as an $h \\times w$ convolutional layer.\n",
    "\n",
    "\n",
    "## Object Edge Detection in Images\n",
    "\n",
    "Let's take a moment to parse a simple application of a convolutional layer:\n",
    "detecting the edge of an object in an image\n",
    "by finding the location of the pixel change.\n",
    "First, we construct an \"image\" of $6\\times 8$ pixels.\n",
    "The middle four columns are black ($0$) and the rest are white ($1$)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-object-edge-detection-in-images-1"
   },
   "source": [
    "X = d2l.ones((6, 8))\n",
    "X[:, 2:6] = 0\n",
    "X"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[1., 1., 0., 0., 0., 0., 1., 1.],\n        [1., 1., 0., 0., 0., 0., 1., 1.],\n        [1., 1., 0., 0., 0., 0., 1., 1.],\n        [1., 1., 0., 0., 0., 0., 1., 1.],\n        [1., 1., 0., 0., 0., 0., 1., 1.],\n        [1., 1., 0., 0., 0., 0., 1., 1.]])"
     },
     "metadata": {},
     "execution_count": 5
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-6 fw=all -->\n",
    "\n",
    "Next, we construct a kernel `K` with a height of 1 and a width of 2.\n",
    "When we perform the cross-correlation operation with the input,\n",
    "if the horizontally adjacent elements are the same,\n",
    "the output is 0. Otherwise, the output is nonzero.\n",
    "Note that this kernel is a special case of a finite difference operator. At location $(i,j)$ it computes $x_{i,j} - x_{i,j+1}$, i.e., it computes the difference between the values of horizontally adjacent pixels. This is a discrete approximation of the first derivative in the horizontal direction (up to a sign). After all, for a function $f(i,j)$ its derivative is $\\partial_j f(i,j) = \\lim_{\\epsilon \\to 0} \\frac{f(i,j+\\epsilon) - f(i,j)}{\\epsilon}$, so the kernel output $x_{i,j} - x_{i,j+1}$ approximates $-\\partial_j f(i,j)$. Let's see how this works in practice."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-object-edge-detection-in-images-2"
   },
   "source": [
    "K = d2l.tensor([[1.0, -1.0]])"
   ],
   "execution_count": 6,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-7 fw=all -->\n",
    "\n",
    "We are ready to perform the cross-correlation operation\n",
    "with arguments `X` (our input) and `K` (our kernel).\n",
    "As you can see, we detect $1$ for the edge from white to black\n",
    "and $-1$ for the edge from black to white.\n",
    "All other outputs take value $0$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-object-edge-detection-in-images-3"
   },
   "source": [
    "Y = corr2d(X, K)\n",
    "Y"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n        [ 0.,  1.,  0.,  0.,  0., -1.,  0.]])"
     },
     "metadata": {},
     "execution_count": 7
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-8 fw=all -->\n",
    "\n",
    "We can now apply the kernel to the transposed image.\n",
    "As expected, it vanishes. The kernel `K` only detects vertical edges."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-object-edge-detection-in-images-4"
   },
   "source": [
    "corr2d(d2l.transpose(X), K)"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.],\n        [0., 0., 0., 0., 0.]])"
     },
     "metadata": {},
     "execution_count": 8
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-9 fw=all -->\n",
    "\n",
    "## Learning a Kernel\n",
    "\n",
    "Designing an edge detector by finite differences `[1, -1]` is neat\n",
    "if we know this is precisely what we are looking for.\n",
    "However, as we look at larger kernels,\n",
    "and consider successive layers of convolutions,\n",
    "it might be impossible to specify\n",
    "precisely what each filter should be doing manually.\n",
    "\n",
    "Now let's see whether we can learn the kernel that generated `Y` from `X`\n",
    "by looking at the input--output pairs only.\n",
    "We first construct a convolutional layer\n",
    "and initialize its kernel as a random tensor.\n",
    "Next, in each iteration, we will use the squared error\n",
    "to compare `Y` with the output of the convolutional layer.\n",
    "We can then calculate the gradient to update the kernel.\n",
    "For the sake of simplicity,\n",
    "in the following\n",
    "we use the built-in class\n",
    "for two-dimensional convolutional layers\n",
    "and ignore the bias."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-learning-a-kernel-1"
   },
   "source": [
    "# Construct a two-dimensional convolutional layer with 1 output channel and a\n",
    "# kernel of shape (1, 2). For the sake of simplicity, we ignore the bias here\n",
    "conv2d = nn.LazyConv2d(1, kernel_size=(1, 2), bias=False)\n",
    "\n",
    "# The two-dimensional convolutional layer uses four-dimensional input and\n",
    "# output in the format of (example, channel, height, width), where the batch\n",
    "# size (number of examples in the batch) and the number of channels are both 1\n",
    "X = X.reshape((1, 1, 6, 8))\n",
    "Y = Y.reshape((1, 1, 6, 7))\n",
    "lr = 3e-2  # Learning rate\n",
    "\n",
    "for i in range(10):\n",
    "    Y_hat = conv2d(X)\n",
    "    l = (Y_hat - Y) ** 2\n",
    "    conv2d.zero_grad()\n",
    "    l.sum().backward()\n",
    "    # Update the kernel\n",
    "    with torch.no_grad():\n",
    "        conv2d.weight[:] -= lr * conv2d.weight.grad\n",
    "    if (i + 1) % 2 == 0:\n",
    "        print(f'epoch {i + 1}, loss {l.sum():.3f}')"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "epoch 2, loss 10.235\nepoch 4, loss 3.103\nepoch 6, loss 1.088\nepoch 8, loss 0.415\nepoch 10, loss 0.165\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-10 fw=all -->\n",
    "\n",
    "Note that the error has dropped to a small value after 10 iterations. Now we will take a look at the kernel tensor we learned."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-learning-a-kernel-2"
   },
   "source": [
    "d2l.reshape(conv2d.weight.data, (1, 2))"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[ 0.9475, -1.0304]])"
     },
     "metadata": {},
     "execution_count": 10
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-11 fw=all -->\n",
    "\n",
    "Indeed, the learned kernel tensor is close\n",
    "to the kernel tensor `K` we defined earlier.\n",
    "\n",
    "## Cross-Correlation and Convolution\n",
    "\n",
    "Recall our observation from that section of the correspondence\n",
    "between the cross-correlation and convolution operations.\n",
    "Here let's continue to consider two-dimensional convolutional layers.\n",
    "What if such layers\n",
    "perform strict convolution operations\n",
    "as defined in the equation\n",
    "instead of cross-correlations?\n",
    "In order to obtain the output of the strict *convolution* operation, we only need to flip the two-dimensional kernel tensor both horizontally and vertically, and then perform the *cross-correlation* operation with the input tensor.\n",
    "\n",
    "Since kernels are learned from data in deep learning,\n",
    "the outputs of convolutional layers remain unaffected\n",
    "no matter such layers\n",
    "perform\n",
    "either the strict convolution operations\n",
    "or the cross-correlation operations.\n",
    "\n",
    "To illustrate this, suppose that a convolutional layer performs *cross-correlation* and learns the kernel in the figure, which is here denoted as the matrix $\\mathbf{K}$.\n",
    "Assuming that other conditions remain unchanged,\n",
    "when this layer instead performs strict *convolution*,\n",
    "the learned kernel $\\mathbf{K}'$ will be the same as $\\mathbf{K}$\n",
    "after $\\mathbf{K}'$ is\n",
    "flipped both horizontally and vertically.\n",
    "That is to say,\n",
    "when the convolutional layer\n",
    "performs strict *convolution*\n",
    "for the input in the figure\n",
    "and $\\mathbf{K}'$,\n",
    "the same output in the figure\n",
    "(cross-correlation of the input and $\\mathbf{K}$)\n",
    "will be obtained.\n",
    "\n",
    "In keeping with standard terminology in deep learning literature,\n",
    "we will continue to refer to the cross-correlation operation\n",
    "as a convolution even though, strictly-speaking, it is slightly different.\n",
    "Furthermore,\n",
    "we use the term *element* to refer to\n",
    "an entry (or component) of any tensor representing a layer representation or a convolution kernel.\n",
    "\n",
    "\n",
    "## Convolution as Matrix Multiplication\n",
    "\n",
    "Every output element in the figure is a dot product:\n",
    "the kernel, flattened into a vector of length $k_\\textrm{h} k_\\textrm{w}$,\n",
    "multiplied with the input patch under the window, flattened the same way.\n",
    "If we extract each patch the sliding window visits,\n",
    "flatten it into a row, and stack the rows,\n",
    "we obtain a matrix with one row per output position.\n",
    "The entire cross-correlation then collapses into a single product\n",
    "of this patch matrix with the flattened kernel.\n",
    "The rearrangement is called *im2col*\n",
    "(it turns image patches into the columns, here rows, of a matrix).\n",
    "\n",
    "This rewriting motivates one important family of convolution implementations.\n",
    "GPUs and other accelerators are built around fast dense matrix multiplication,\n",
    "and libraries often lower convolutions to explicit or implicit matrix products.\n",
    "Depending on the shapes and hardware, they may instead select direct,\n",
    "Winograd, FFT-based, or other specialized kernels.\n",
    "The explicit form costs memory:\n",
    "each input element is duplicated in up to $k_\\textrm{h} k_\\textrm{w}$ rows.\n",
    "Let's build the patch matrix for the input and kernel\n",
    "of the figure\n",
    "and check that the matrix product reproduces `corr2d`."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-convolution-as-matrix-multiplication-1"
   },
   "source": [
    "X = d2l.tensor([[0.0, 1.0, 2.0], [3.0, 4.0, 5.0], [6.0, 7.0, 8.0]])\n",
    "K = d2l.tensor([[0.0, 1.0], [2.0, 3.0]])\n",
    "h, w = K.shape\n",
    "p_h, p_w = X.shape[0] - h + 1, X.shape[1] - w + 1\n",
    "patches = d2l.stack([d2l.reshape(X[i:i + h, j:j + w], (-1,))\n",
    "                     for i in range(p_h) for j in range(p_w)])\n",
    "Y_mat = d2l.reshape(d2l.matmul(patches, d2l.reshape(K, (-1, 1))), (p_h, p_w))\n",
    "Y_mat, d2l.reduce_sum(d2l.abs(Y_mat - corr2d(X, K)))"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([[19., 25.],\n         [37., 43.]]),\n tensor(0.))"
     },
     "metadata": {},
     "execution_count": 11
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-12 fw=all -->\n",
    "\n",
    "The sum of absolute differences is zero:\n",
    "the one matrix product and the sliding-window loop\n",
    "compute the same output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-13 fw=pytorch -->\n",
    "\n",
    "PyTorch exposes this rearrangement directly:\n",
    "`F.unfold` extracts the patch matrix\n",
    "(transposed, and with batch and channel dimensions),\n",
    "so any convolution can be written as unfold,\n",
    "matrix multiplication, and reshape."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "conv-layer-convolution-as-matrix-multiplication-2"
   },
   "source": [
    "X_batch = d2l.reshape(X, (1, 1, 3, 3))\n",
    "patches_unfold = F.unfold(X_batch, kernel_size=(2, 2))[0].T\n",
    "torch.allclose(patches_unfold, patches)"
   ],
   "execution_count": 12,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "True"
     },
     "metadata": {},
     "execution_count": 12
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-14 fw=all -->\n",
    "\n",
    "The same idea also works in the opposite direction:\n",
    "instead of unfolding the input,\n",
    "we can unroll the kernel into a sparse, banded matrix\n",
    "that multiplies the flattened image.\n",
    "The exercises explore this view.\n",
    "\n",
    "## Feature Map and Receptive Field\n",
    "\n",
    "As described in that section,\n",
    "the convolutional layer output in\n",
    "the figure\n",
    "is sometimes called a *feature map*,\n",
    "as it can be regarded as\n",
    "the learned representations (features)\n",
    "in the spatial dimensions (e.g., width and height)\n",
    "to the subsequent layer.\n",
    "In CNNs,\n",
    "for any element $x$ of some layer,\n",
    "its *receptive field* refers to\n",
    "all the elements (from all the previous layers)\n",
    "that may affect the calculation of $x$\n",
    "during the forward propagation.\n",
    "Note that the receptive field\n",
    "may be larger than the actual size of the input.\n",
    "\n",
    "Let's continue to use the figure to explain the receptive field.\n",
    "Given the $2 \\times 2$ convolution kernel,\n",
    "the receptive field of the shaded output element (of value $19$)\n",
    "is\n",
    "the four elements in the shaded portion of the input.\n",
    "Now let's denote the $2 \\times 2$\n",
    "output as $\\mathbf{Y}$\n",
    "and consider a deeper CNN\n",
    "with an additional $2 \\times 2$ convolutional layer that takes $\\mathbf{Y}$\n",
    "as its input, outputting\n",
    "a single element $z$.\n",
    "In this case,\n",
    "the receptive field of $z$\n",
    "on $\\mathbf{Y}$ includes all the four elements of $\\mathbf{Y}$,\n",
    "while\n",
    "the receptive field\n",
    "on the input includes all the nine input elements.\n",
    "Thus,\n",
    "when any element in a feature map\n",
    "needs a larger receptive field\n",
    "to detect input features over a broader area,\n",
    "we can build a deeper network.\n",
    "\n",
    "This layer-by-layer counting has a closed form.\n",
    "Consider a stack of $L$ convolutional layers\n",
    "in which layer $i$ has a $k_i \\times k_i$ kernel and stride $s_i$\n",
    "(padding affects only which outputs exist,\n",
    "not how far each one sees).\n",
    "One step at the input of layer $i$\n",
    "corresponds to $\\prod_{j=1}^{i-1} s_j$ steps at the original input,\n",
    "since every earlier layer with stride $s_j$\n",
    "multiplies the step size by $s_j$.\n",
    "Layer $i$'s kernel spans $k_i - 1$ steps of its own input,\n",
    "so it widens the receptive field by\n",
    "$(k_i - 1) \\prod_{j=1}^{i-1} s_j$ input pixels.\n",
    "Starting from a single pixel and summing over layers,\n",
    "an element at the top of the stack\n",
    "has a receptive field of side length\n",
    "\n",
    "$$\n",
    "r = 1 + \\sum_{i=1}^{L} \\left( k_i - 1 \\right) \\prod_{j=1}^{i-1} s_j,\n",
    "$$\n",
    "\n",
    "where the empty product for $i = 1$ equals $1$.\n",
    "\n",
    "The most common case is $L$ stacked $3 \\times 3$ layers with stride $1$:\n",
    "each layer adds $2$,\n",
    "so the stack sees $(2L + 1) \\times (2L + 1)$ input pixels.\n",
    "Two such layers cover $5 \\times 5$, three cover $7 \\times 7$.\n",
    "This is why deep stacks of small kernels can replace single large ones:\n",
    "three $3 \\times 3$ layers match the receptive field\n",
    "of one $7 \\times 7$ layer with fewer parameters\n",
    "($27$ weights instead of $49$ per input--output channel pair)\n",
    "and three nonlinearities instead of one.\n",
    "Strides enter through the product:\n",
    "after a stride-$2$ layer (or a pooling step, that section),\n",
    "every later kernel counts double,\n",
    "so downsampling makes the receptive field grow geometrically with depth.\n",
    "We will use the equation repeatedly\n",
    "when we analyze modern architectures in that section.\n",
    "\n",
    "Equation the equation gives the *theoretical* receptive field:\n",
    "the set of inputs that can affect an activation at all. Their influence is not\n",
    "uniform. @Luo.Li.Urtasun.ea.2016 measured the *effective* receptive\n",
    "field through gradients and found that it concentrates near the center of the\n",
    "theoretical region, with a roughly Gaussian profile in common randomly\n",
    "initialized and trained networks. Depth, dilation, and larger kernels enlarge\n",
    "the set of possible inputs; they do not guarantee that optimization will use\n",
    "all of it equally.\n",
    "\n",
    "Receptive fields derive their name from neurophysiology.\n",
    "Experiments recording from the visual cortex of several animal species\n",
    "[@Hubel.Wiesel.1959; @Hubel.Wiesel.1962; @Hubel.Wiesel.1968]\n",
    "found that its lower levels respond to edges and related shapes.\n",
    "Later, @Field.1987 modeled these responses on natural images\n",
    "with what are, in effect, convolutional kernels.\n",
    "We reprint a key figure in the figure.\n",
    "\n",
    "![Figure and caption taken from @Field.1987: An example of coding with six different channels. (Left) Examples of the six types of sensor associated with each channel. (Right) Convolution of the image in (Middle) with the six sensors shown in (Left). The response of the individual sensors is determined by sampling these filtered images at a distance proportional to the size of the sensor (shown with dots). This diagram shows the response of only the even symmetric sensors.](../img/field-visual.png)\n",
    "\n",
    "The correspondence extends to features computed by deeper layers of networks trained on image classification [@Kuzovkin.Vicente.Petton.ea.2018].\n",
    "\n",
    "## Summary\n",
    "\n",
    "The core computation in a convolutional layer is cross-correlation. A nested\n",
    "loop states the operation directly; practical libraries select among implicit\n",
    "matrix multiplication, direct, Winograd, FFT-based, and specialized kernels.\n",
    "Locality creates extensive reuse of weights and overlapping input patches, but\n",
    "real performance depends on both arithmetic throughput and memory movement.\n",
    "\n",
    "Convolutions can detect edges and lines, blur images, or sharpen them. In a\n",
    "neural network, the filters are learned from data rather than specified by\n",
    "hand. The language of receptive fields has a historical connection to visual\n",
    "neurophysiology, but that analogy is motivation rather than evidence that a\n",
    "particular network mirrors the brain.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Construct an image `X` with diagonal edges.\n",
    "    1. What happens if you apply the kernel `K` in this section to it?\n",
    "    1. What happens if you transpose `X`?\n",
    "    1. What happens if you transpose `K`?\n",
    "1. Design some kernels manually.\n",
    "    1. Given a directional vector $\\mathbf{v} = (v_1, v_2)$, derive an edge-detection kernel that detects\n",
    "       edges orthogonal to $\\mathbf{v}$, i.e., edges in the direction $(v_2, -v_1)$.\n",
    "    1. Derive a finite difference operator for the second derivative. What is the minimum\n",
    "       size of the convolutional kernel associated with it? Which structures in images respond most strongly to it?\n",
    "    1. How would you design a blur kernel? Why might you want to use such a kernel?\n",
    "    1. What is the minimum size of a kernel to obtain a derivative of order $d$?\n",
    "1. When you try to automatically find the gradient for the `Conv2D` class we created, what kind of error message do you see?\n",
    "1. How do you represent a cross-correlation operation as a matrix multiplication by changing the input and kernel tensors?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=conv-layer-md-15 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/66)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
