{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-1 fw=all -->\n",
    "\n",
    "# Pooling\n",
    "\n",
    "In many cases our ultimate task asks some global question about the image,\n",
    "e.g., *does it contain a cat?* Consequently, the units of our final layer \n",
    "should be sensitive to the entire input.\n",
    "By gradually aggregating information, yielding coarser and coarser maps,\n",
    "we accomplish this goal of ultimately learning a global representation,\n",
    "while keeping all of the advantages of convolutional layers at the intermediate layers of processing.\n",
    "The deeper we go in the network,\n",
    "the larger the receptive field (relative to the input)\n",
    "to which each hidden node is sensitive. Reducing spatial resolution \n",
    "accelerates this process, \n",
    "since the convolution kernels cover a larger effective area. \n",
    "\n",
    "Moreover, when detecting lower-level features, such as edges\n",
    "(as discussed in that section),\n",
    "we often want our representations to be somewhat invariant to translation.\n",
    "For instance, if we take the image `X`\n",
    "with a sharp delineation between black and white\n",
    "and shift the whole image by one pixel to the right,\n",
    "i.e., `Z[i, j] = X[i, j - 1]`,\n",
    "then the output for the new image `Z` might be vastly different.\n",
    "The edge will have shifted by one pixel.\n",
    "In reality, objects hardly ever occur exactly at the same place.\n",
    "In fact, even with a tripod and a stationary object,\n",
    "vibration of the camera due to the movement of the shutter\n",
    "might shift everything by a pixel or so\n",
    "(high-end cameras are loaded with special features to address this problem).\n",
    "\n",
    "This section introduces *pooling layers*,\n",
    "which serve the dual purposes of\n",
    "mitigating the sensitivity of convolutional layers to location\n",
    "and of spatially downsampling representations."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling"
   },
   "source": [
    "from d2l import torch as d2l\n",
    "import torch\n",
    "from torch import nn"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-2 fw=all -->\n",
    "\n",
    "## Maximum Pooling and Average Pooling\n",
    "\n",
    "Like convolutional layers, *pooling* operators\n",
    "consist of a fixed-shape window that is slid over\n",
    "all regions in the input according to its stride,\n",
    "computing a single output for each location traversed\n",
    "by the fixed-shape window (sometimes known as the *pooling window*).\n",
    "However, unlike the cross-correlation computation\n",
    "of the inputs and kernels in the convolutional layer,\n",
    "the pooling layer contains no parameters (there is no *kernel*).\n",
    "Instead, pooling operators are deterministic,\n",
    "typically calculating either the maximum or the average value\n",
    "of the elements in the pooling window.\n",
    "These operations are called *maximum pooling* (*max-pooling* for short)\n",
    "and *average pooling*, respectively.\n",
    "\n",
    "*Average pooling* is essentially as old as CNNs. The idea is akin to \n",
    "downsampling an image. Rather than just taking the value of every second (or third) \n",
    "pixel for the lower resolution image, we can average over adjacent pixels to obtain \n",
    "an image with better signal-to-noise ratio since we are combining the information \n",
    "from multiple adjacent pixels. *Max-pooling* was introduced in \n",
    "@Riesenhuber.Poggio.1999 in the context of cognitive neuroscience to describe \n",
    "how information might be aggregated hierarchically for the purpose \n",
    "of object recognition; there already was an earlier version in speech recognition\n",
    "[@Yamaguchi.Sakamoto.Akabane.ea.1990]. Historically, max-pooling was\n",
    "often preferred inside convolutional bodies, while average pooling became the\n",
    "standard choice for global classifier heads. Neither dominates in every setting.\n",
    "\n",
    "In both cases, as with the cross-correlation operator,\n",
    "we can think of the pooling window\n",
    "as starting from the upper-left of the input tensor\n",
    "and sliding across it from left to right and top to bottom.\n",
    "At each location that the pooling window hits,\n",
    "it computes the maximum or average\n",
    "value of the input subtensor in the window,\n",
    "depending on whether max or average pooling is employed.\n",
    "\n",
    "\n",
    "![Max-pooling with a pooling window shape of $2\\times 2$. The shaded portions are the first output element as well as the input tensor elements used for the output computation: $\\max(0, 1, 3, 4)=4$.](../img/pooling.svg)\n",
    "\n",
    "The output tensor in the figure  has a height of 2 and a width of 2.\n",
    "The four elements are derived from the maximum value in each pooling window:\n",
    "\n",
    "$$\n",
    "\\max(0, 1, 3, 4)=4,\\\\\n",
    "\\max(1, 2, 4, 5)=5,\\\\\n",
    "\\max(3, 4, 6, 7)=7,\\\\\n",
    "\\max(4, 5, 7, 8)=8.\\\\\n",
    "$$\n",
    "\n",
    "More generally, we can define a $p \\times q$ pooling layer by aggregating over \n",
    "a region of said size. Returning to the problem of edge detection, \n",
    "we use the output of the convolutional layer\n",
    "as input for $2\\times 2$ max-pooling.\n",
    "Denote the edge-detector output by `X` and the pooling output by `Y`. If a\n",
    "single response of value 1 moves anywhere within the same $2\\times2$ pooling\n",
    "window while the other responses remain no larger, then `Y[i, j]` remains 1.\n",
    "Thus max-pooling can make a representation insensitive to some small movements\n",
    "that stay within a window. Crossing a window boundary can still change the\n",
    "pooled output abruptly, so this is local tolerance rather than exact translation\n",
    "invariance.\n",
    "\n",
    "In the code below, we implement the forward propagation\n",
    "of the pooling layer in the `pool2d` function.\n",
    "This function is similar to the `corr2d` function\n",
    "in that section.\n",
    "However, no kernel is needed, computing the output\n",
    "as either the maximum or the average of each region in the input."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-maximum-pooling-and-average-pooling-1"
   },
   "source": [
    "def pool2d(X, pool_size, mode='max'):\n",
    "    p_h, p_w = pool_size\n",
    "    Y = d2l.zeros((X.shape[0] - p_h + 1, X.shape[1] - p_w + 1))\n",
    "    for i in range(Y.shape[0]):\n",
    "        for j in range(Y.shape[1]):\n",
    "            if mode == 'max':\n",
    "                Y[i, j] = X[i: i + p_h, j: j + p_w].max()\n",
    "            elif mode == 'avg':\n",
    "                Y[i, j] = X[i: i + p_h, j: j + p_w].mean()\n",
    "    return Y"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-3 fw=all -->\n",
    "\n",
    "We can construct the input tensor `X` in the figure to validate the output of the two-dimensional max-pooling layer."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-maximum-pooling-and-average-pooling-2"
   },
   "source": [
    "X = d2l.tensor([[0.0, 1.0, 2.0], [3.0, 4.0, 5.0], [6.0, 7.0, 8.0]])\n",
    "pool2d(X, (2, 2))"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[4., 5.],\n        [7., 8.]])"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-4 fw=all -->\n",
    "\n",
    "Also, we can experiment with the average pooling layer."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-maximum-pooling-and-average-pooling-3"
   },
   "source": [
    "pool2d(X, (2, 2), 'avg')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[2., 3.],\n        [5., 6.]])"
     },
     "metadata": {},
     "execution_count": 4
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-5 fw=all -->\n",
    "\n",
    "## Padding and Stride\n",
    "\n",
    "As with convolutional layers, pooling layers\n",
    "change the output shape.\n",
    "And as before, we can adjust the operation to achieve a desired output shape\n",
    "by padding the input and adjusting the stride.\n",
    "We can demonstrate the use of padding and strides\n",
    "in pooling layers via the built-in two-dimensional max-pooling layer from the deep learning framework.\n",
    "We first construct an input tensor `X` whose shape has four dimensions,\n",
    "where the number of examples (batch size) and number of channels are both 1."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-padding-and-stride-1"
   },
   "source": [
    "X = d2l.reshape(d2l.arange(16, dtype=d2l.float32), (1, 1, 4, 4))\n",
    "X"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[[ 0.,  1.,  2.,  3.],\n          [ 4.,  5.,  6.,  7.],\n          [ 8.,  9., 10., 11.],\n          [12., 13., 14., 15.]]]])"
     },
     "metadata": {},
     "execution_count": 5
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-6 fw=all -->\n",
    "\n",
    "Since pooling aggregates information from an area, deep learning frameworks default to matching pooling window sizes and stride. For instance, if we use a pooling window of shape `(3, 3)`\n",
    "we get a stride shape of `(3, 3)` by default."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-padding-and-stride-2"
   },
   "source": [
    "pool2d = nn.MaxPool2d(3)\n",
    "# Pooling has no model parameters, hence it needs no initialization\n",
    "pool2d(X)"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[[10.]]]])"
     },
     "metadata": {},
     "execution_count": 6
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-7 fw=all -->\n",
    "\n",
    "Needless to say, the stride and padding can be manually specified to override framework defaults if required."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-padding-and-stride-3"
   },
   "source": [
    "pool2d = nn.MaxPool2d(3, padding=1, stride=2)\n",
    "pool2d(X)"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[[ 5.,  7.],\n          [13., 15.]]]])"
     },
     "metadata": {},
     "execution_count": 7
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-8 fw=all -->\n",
    "\n",
    "Of course, we can specify an arbitrary rectangular pooling window with arbitrary height and width respectively, as the example below shows."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-padding-and-stride-4"
   },
   "source": [
    "pool2d = nn.MaxPool2d((2, 3), stride=(2, 3), padding=(0, 1))\n",
    "pool2d(X)"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[[ 5.,  7.],\n          [13., 15.]]]])"
     },
     "metadata": {},
     "execution_count": 8
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-9 fw=all -->\n",
    "\n",
    "## Multiple Channels\n",
    "\n",
    "When processing multi-channel input data,\n",
    "the pooling layer pools each input channel separately,\n",
    "rather than summing the inputs up over channels\n",
    "as in a convolutional layer.\n",
    "This means that the number of output channels for the pooling layer\n",
    "is the same as the number of input channels.\n",
    "Below, we will concatenate tensors `X` and `X + 1`\n",
    "on the channel dimension to construct an input with two channels."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-multiple-channels-1"
   },
   "source": [
    "X = d2l.concat((X, X + 1), 1)\n",
    "X"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[[ 0.,  1.,  2.,  3.],\n          [ 4.,  5.,  6.,  7.],\n          [ 8.,  9., 10., 11.],\n          [12., 13., 14., 15.]],\n\n         [[ 1.,  2.,  3.,  4.],\n          [ 5.,  6.,  7.,  8.],\n          [ 9., 10., 11., 12.],\n          [13., 14., 15., 16.]]]])"
     },
     "metadata": {},
     "execution_count": 9
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-10 fw=all -->\n",
    "\n",
    "As we can see, the number of output channels is still two after pooling."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "pooling-multiple-channels-2"
   },
   "source": [
    "pool2d = nn.MaxPool2d(3, padding=1, stride=2)\n",
    "pool2d(X)"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[[ 5.,  7.],\n          [13., 15.]],\n\n         [[ 6.,  8.],\n          [14., 16.]]]])"
     },
     "metadata": {},
     "execution_count": 10
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-11 fw=all -->\n",
    "\n",
    "## Summary\n",
    "\n",
    "Pooling is a simple operation: it replaces each window of values with a single\n",
    "summary, the maximum or the mean. The stride and padding semantics of\n",
    "convolutions carry over unchanged, and pooling applies to each channel\n",
    "separately, so the number of channels is preserved. There are no parameters to\n",
    "learn. A $2 \\times 2$ window with stride 2, which quarters the number of\n",
    "spatial locations, is the classical local configuration; global average\n",
    "pooling is now the common classification head.\n",
    "\n",
    "Be aware, though, that pooling is no longer how most downsampling happens. Modern convolutional networks reduce resolution mainly with *strided convolutions*: a convolution with stride 2 halves the resolution just as a pooling layer would, but it learns its aggregation weights rather than fixing them to max or mean. ResNet (that section) and its successors follow this pattern. Pooling survives in two roles. *Global average pooling*, introduced with the network-in-network architecture (that section) [@Lin.Chen.Yan.2013], averages each channel over all spatial positions; it turns the final feature map into one number per channel and has replaced the large fully connected layers of early CNNs as the default classifier head. Max-pooling persists in some network stems (ResNet opens with one) and in detection models that merge feature maps across scales.\n",
    "\n",
    "One caveat applies to every stride-2 downsampler, pooled or convolutional:\n",
    "subsampling a signal without first removing its high spatial frequencies can\n",
    "*alias*, so that shifting the input by a single pixel changes the output\n",
    "noticeably; applying a small low-pass (blur) filter before subsampling can make\n",
    "the result substantially more shift-consistent, though not exactly invariant\n",
    "[@zhang2019making]. Beyond these mainstays there are randomized variants\n",
    "such as stochastic pooling [@Zeiler.Fergus.2013] and fractional\n",
    "max-pooling [@Graham.2014], and the attention mechanisms of\n",
    "that section aggregate by learned alignment\n",
    "between a query and representation vectors rather than by spatial location.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Implement average pooling through a convolution. \n",
    "1. Prove that max-pooling cannot be implemented through a convolution alone. \n",
    "1. Max-pooling can be accomplished using ReLU operations, i.e., $\\textrm{ReLU}(x) = \\max(0, x)$.\n",
    "    1. Express $\\max (a, b)$ by using only ReLU operations.\n",
    "    1. Use this to implement max-pooling by means of convolutions and ReLU layers. \n",
    "    1. How many channels and layers do you need for a $2 \\times 2$ convolution? How many for a $3 \\times 3$ convolution?\n",
    "1. What is the computational cost of the pooling layer? Assume that the input to the pooling layer is of size $c\\times h\\times w$, the pooling window has a shape of $p_\\textrm{h}\\times p_\\textrm{w}$ with a padding of $(p_\\textrm{h}, p_\\textrm{w})$ and a stride of $(s_\\textrm{h}, s_\\textrm{w})$.\n",
    "1. Why do you expect max-pooling and average pooling to work differently?\n",
    "1. Do we need a separate minimum pooling layer? Can you replace it with another operation?\n",
    "1. We could use the softmax operation for pooling. Why might it not be so popular?\n",
    "1. Naive stride-2 downsampling keeps every second entry of its input. Apply it to the one-dimensional signals $(1, 0, 1, 0, 1, 0)$ and $(0, 1, 0, 1, 0, 1)$, i.e., the same pattern shifted by one position. \n",
    "    1. Compare the two outputs. Why is this behavior called *aliasing*, and which input frequencies can a stride-2 subsampler represent faithfully?\n",
    "    1. Blur-pool counteracts aliasing by applying a small averaging filter before subsampling. Work out what blur-pool with a two-tap box filter $(\\tfrac{1}{2}, \\tfrac{1}{2})$ computes on the two signals above. Which pooling operation from this section does it coincide with?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=pooling-md-12 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/72)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
