{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "colab": {
   "provenance": []
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cell-0000",
   "metadata": {},
   "source": [
    "# How Convolutions Work\n",
    "\n",
    "Why dense layers fail on images, what a convolution actually computes, and the arithmetic of channels, stride, padding, and pooling.\n",
    "\n",
    "*Part of the free [Deep Learning with PyTorch](https://ramadnsyh.dev/courses/deep-learning) course by [Muhammad Ramadiansyah](https://ramadnsyh.dev). This notebook is generated from the interactive lesson — [read it online](https://ramadnsyh.dev/courses/deep-learning/convolutions).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "Every network so far flattened its input into a feature vector. For images\n",
    "that's a disaster: flattening throws away the very thing that makes an image\n",
    "an image — pixels near each other are related. Convolutional neural networks\n",
    "(CNNs) fix this with one elegant operation. In this lesson you'll see exactly\n",
    "what a convolution computes, slide kernels over an image yourself, master the\n",
    "output-size arithmetic, and implement a convolution from scratch in NumPy."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## Why dense layers fail on images\n",
    "\n",
    "Two fatal problems with feeding raw pixels into `nn.Linear`:\n",
    "\n",
    "1. **Parameter explosion.** A modest 224×224 RGB photo has 224 · 224 · 3 =\n",
    "   150,528 input values. One dense hidden layer of just 1,000 units already\n",
    "   needs about **150 million weights** — for a single layer, before the\n",
    "   network has done anything useful. More parameters means more memory, more\n",
    "   compute, and far more data needed to avoid memorizing noise.\n",
    "2. **No translation awareness.** To a dense layer, pixel 3,201 and pixel\n",
    "   14,878 are unrelated inputs. If it learns to spot a cat's ear in the top-left\n",
    "   corner, it has learned *nothing* about ears in the bottom-right — every\n",
    "   position needs its own separate weights for the same concept.\n",
    "\n",
    "The fix: learn one **small filter** that detects a pattern, and reuse it at\n",
    "*every* position in the image. That's a convolution."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "## Convolution: a small filter, slid everywhere\n",
    "\n",
    "A convolutional filter (or **kernel**) is a tiny grid of weights — typically\n",
    "3×3 or 5×5. It slides across the image, and at each position computes a\n",
    "weighted sum: multiply the kernel by the pixels underneath, element-wise, and\n",
    "add everything up. The result at each position becomes one pixel of the\n",
    "output, called a **feature map** — a map of *where* in the image the kernel's\n",
    "pattern appears.\n",
    "\n",
    "Try it yourself. Slide different kernels over the image and watch what each\n",
    "one extracts:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0004",
   "metadata": {},
   "source": [
    "> 🎛️ **Interactive demo** — this section has a hands-on visualization in the web version of this lesson: [open it here](https://ramadnsyh.dev/courses/deep-learning/convolutions)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0005",
   "metadata": {},
   "source": [
    "Notice the classic hand-crafted kernels:\n",
    "\n",
    "- an **edge-detection** kernel (positive center, negative surround) lights up\n",
    "  where brightness changes sharply and goes quiet on flat regions;\n",
    "- a **sharpen** kernel exaggerates those changes;\n",
    "- a **blur** kernel (all-positive, averaging) smooths them away.\n",
    "\n",
    "For decades, computer-vision engineers designed such kernels by hand. The CNN\n",
    "insight is to make the kernel weights **learnable parameters**: the network\n",
    "discovers whatever filters minimize the loss — edge detectors usually emerge\n",
    "in the first layer all by themselves. And because one kernel is reused at\n",
    "every position, a 3×3 filter costs **9 weights** instead of millions, and a\n",
    "pattern learned anywhere is recognized everywhere: built-in translation\n",
    "awareness."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0006",
   "metadata": {},
   "source": [
    "## Channels, stride, and padding\n",
    "\n",
    "Real images have **channels** (RGB = 3), and each convolution layer produces\n",
    "many feature maps. Vocabulary for a layer that maps 3 input channels to 8\n",
    "output channels with 3×3 kernels:\n",
    "\n",
    "- Each output channel has its own kernel of shape 3×3×**3** — it spans *all*\n",
    "  input channels and sums across them. So the layer holds 8 kernels,\n",
    "  8 · (3·3·3) = 216 weights (plus 8 biases).\n",
    "- **Stride** is the step size of the slide. Stride 1 visits every position;\n",
    "  stride 2 skips every other one, halving the output's width and height.\n",
    "- **Padding** adds a border of zeros around the input so the kernel can center\n",
    "  on edge pixels. Without padding, every 3×3 convolution shrinks the image by\n",
    "  2 pixels per side pair; with padding 1, the size is preserved.\n",
    "\n",
    "All of that folds into one formula for the output size along each dimension,\n",
    "with input size n, kernel size k, padding p, and stride s:\n",
    "\n",
    "**out = floor((n + 2p − k) / s) + 1**\n",
    "\n",
    "Worked example — a 28×28 image, 3×3 kernel, padding 1, stride 1:\n",
    "out = floor((28 + 2 − 3) / 1) + 1 = **28**. Same size, as promised. Now stride\n",
    "2: out = floor((28 + 2 − 3) / 2) + 1 = floor(13.5) + 1 = **14**. Halved.\n",
    "You'll use this formula constantly when designing architectures — the flatten\n",
    "layer at the end needs to know exactly what size arrives."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "## Pooling: cheap downsampling\n",
    "\n",
    "A **pooling** layer shrinks feature maps without any learnable weights.\n",
    "**Max pooling** with a 2×2 window and stride 2 splits the map into 2×2 tiles\n",
    "and keeps only the largest value in each — width and height halve, and the\n",
    "strongest activations survive. Why bother?\n",
    "\n",
    "- It cuts computation for every following layer by 4x.\n",
    "- It makes the representation slightly translation-tolerant: if the edge moves\n",
    "  one pixel, the max of its neighborhood often doesn't change.\n",
    "- Growing \"receptive fields\": after pooling, one pixel of a feature map\n",
    "  summarizes a larger region of the original image, letting later layers see\n",
    "  bigger patterns."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0008",
   "metadata": {},
   "source": [
    "## The feature hierarchy\n",
    "\n",
    "Stack the pattern — convolution, nonlinearity, pooling — a few times and\n",
    "something remarkable happens. The first layer, looking at raw pixels, learns\n",
    "**edges and color blobs**. The second layer, looking at edge maps, learns\n",
    "**textures and corners** — combinations of edges. Deeper layers combine those\n",
    "into **object parts** (eyes, wheels, feathers), and the final layers into\n",
    "whole objects. Nobody programs this hierarchy; it emerges from training,\n",
    "exactly like the learned features of the MLPs you trained — but now organized\n",
    "spatially."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0009",
   "metadata": {},
   "source": [
    "## Convolution from scratch\n",
    "\n",
    "Ten lines of NumPy make the operation concrete. Here's a vertical-edge kernel\n",
    "sliding over a tiny image that's dark on the left, bright on the right:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0010",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# 6x6 \"image\": dark left half (0), bright right half (9)\n",
    "img = np.zeros((6, 6))\n",
    "img[:, 3:] = 9.0\n",
    "\n",
    "# 3x3 vertical-edge kernel (Sobel-like)\n",
    "kernel = np.array([[ 1, 0, -1],\n",
    "                   [ 2, 0, -2],\n",
    "                   [ 1, 0, -1]])\n",
    "\n",
    "def conv2d(img, kernel, stride=1):\n",
    "    k = kernel.shape[0]\n",
    "    out_size = (img.shape[0] - k) // stride + 1     # the formula, p=0\n",
    "    out = np.zeros((out_size, out_size))\n",
    "    for i in range(out_size):\n",
    "        for j in range(out_size):\n",
    "            patch = img[i*stride:i*stride+k, j*stride:j*stride+k]\n",
    "            out[i, j] = np.sum(patch * kernel)      # element-wise mult, then sum\n",
    "    return out\n",
    "\n",
    "print(\"image:\")\n",
    "print(img)\n",
    "print()\n",
    "fmap = conv2d(img, kernel)\n",
    "print(\"feature map (4x4):\")\n",
    "print(fmap)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0011",
   "metadata": {},
   "source": [
    "Read the output: the feature map is zero on the flat regions and strongly\n",
    "negative exactly along the dark-to-bright boundary — the kernel found the\n",
    "vertical edge and nothing else. (Sign just encodes the edge's direction; a\n",
    "ReLU after the convolution would keep one polarity.) Note the size:\n",
    "(6 − 3)/1 + 1 = 4, matching the formula with no padding."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0012",
   "metadata": {},
   "source": [
    "## The PyTorch layers\n",
    "\n",
    "In PyTorch these operations are single layers:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0013",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch import nn\n",
    "\n",
    "conv = nn.Conv2d(in_channels=3, out_channels=8,\n",
    "                 kernel_size=3, stride=1, padding=1)\n",
    "pool = nn.MaxPool2d(kernel_size=2, stride=2)\n",
    "\n",
    "x = torch.randn(1, 3, 64, 64)     # [batch, channels, height, width]\n",
    "h = conv(x)\n",
    "print(h.shape)                    # [1, 8, 64, 64]  (padding=1 preserves size)\n",
    "h = pool(h)\n",
    "print(h.shape)                    # [1, 8, 32, 32]  (pooling halves H and W)\n",
    "\n",
    "n_weights = sum(p.numel() for p in conv.parameters())\n",
    "print(n_weights)                  # 8*(3*3*3) + 8 = 224 parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0014",
   "metadata": {},
   "source": [
    "224 parameters to process an image of any size — compare that to the 150\n",
    "million a dense layer needed. Convolution + ReLU + pooling is the block we'll\n",
    "stack into a full CNN in the next lesson."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0015",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — Stride, padding, and a horizontal edge\n",
    "\n",
    "horizontal edge\n",
    "\n",
    "kernel = np.array([[ 1,  2,  1],\n",
    "                   [ 0,  0,  0],\n",
    "                   [-1, -2, -1]])\n",
    "\n",
    "def conv2d(img, kernel, stride=1, padding=0):\n",
    "    if padding:\n",
    "        img = np.pad(img, padding)\n",
    "    k = kernel.shape[0]\n",
    "    out_size = (img.shape[0] - k) // stride + 1\n",
    "    out = np.zeros((out_size, out_size))\n",
    "    for i in range(out_size):\n",
    "        for j in range(out_size):\n",
    "            patch = img[i*stride:i*stride+k, j*stride:j*stride+k]\n",
    "            out[i, j] = np.sum(patch * kernel)\n",
    "    return out\n",
    "\n",
    "for s, p in [(1, 0), (2, 0), (1, 1)]:\n",
    "    fmap = conv2d(img, kernel, stride=s, padding=p)\n",
    "    predicted = (6 + 2*p - 3) // s + 1\n",
    "    print(f\"stride={s} padding={p} -> shape {fmap.shape} (formula: {predicted})\")\n",
    "    print(fmap, end=\"\\\\n\\\\n\")\n",
    "\n",
    "# The response is strongly negative along rows where dark meets bright,\n",
    "# zero elsewhere; stride 2 gives a 2x2 map, padding 1 gives 6x6.\n",
    "`}\n",
    ">\n",
    "Extend the from-scratch `conv2d` to support **padding** (hint: `np.pad`) and\n",
    "test it on a 6×6 image that is dark on **top** and bright on the **bottom**,\n",
    "using a **horizontal**-edge kernel. Run three configurations — stride 1 /\n",
    "padding 0, stride 2 / padding 0, and stride 1 / padding 1 — and verify each\n",
    "output shape against the size formula. Where does the feature map respond, and\n",
    "why?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0016",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0017",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "\n",
    "img = np.zeros((6, 6))\n",
    "img[3:, :] = 9.0          # dark top, bright bottom -> horizontal edge\n",
    "\n",
    "kernel = np.array([[ 1,  2,  1],\n",
    "                   [ 0,  0,  0],\n",
    "                   [-1, -2, -1]])\n",
    "\n",
    "def conv2d(img, kernel, stride=1, padding=0):\n",
    "    if padding:\n",
    "        img = np.pad(img, padding)\n",
    "    k = kernel.shape[0]\n",
    "    out_size = (img.shape[0] - k) // stride + 1\n",
    "    out = np.zeros((out_size, out_size))\n",
    "    for i in range(out_size):\n",
    "        for j in range(out_size):\n",
    "            patch = img[i*stride:i*stride+k, j*stride:j*stride+k]\n",
    "            out[i, j] = np.sum(patch * kernel)\n",
    "    return out\n",
    "\n",
    "for s, p in [(1, 0), (2, 0), (1, 1)]:\n",
    "    fmap = conv2d(img, kernel, stride=s, padding=p)\n",
    "    predicted = (6 + 2*p - 3) // s + 1\n",
    "    print(f\"stride={s} padding={p} -> shape {fmap.shape} (formula: {predicted})\")\n",
    "    print(fmap, end=\"\\\\n\\\\n\")\n",
    "\n",
    "# The response is strongly negative along rows where dark meets bright,\n",
    "# zero elsewhere; stride 2 gives a 2x2 map, padding 1 gives 6x6.\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0018",
   "metadata": {},
   "source": [
    "Next up: stacking conv-relu-pool blocks into a complete CNN and training it on\n",
    "a real image dataset in PyTorch."
   ]
  }
 ]
}