Convolutions Theory.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The convolution layer has three parameters, the stride, the padding and the filter. We will explain the forward pass and the back propagation using a 2d image with a number of channels input as a minibatch as an example but the idea is valid for any number of dimensions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The input of a convolution layer is denoted as $l^0$ and output as $l^1$. With indices\n",
    "\n",
    "$$\n",
    "l^0_{I,i,j,k}\n",
    "$$\n",
    "\n",
    "where the indices are mini-batch, pixel row and column and channel. The notion of embedding and stride comes in by embedding this image in a (possibly) bigger 0-padded array thus\n",
    "\n",
    "$$\n",
    "\\tilde l^0_{I,P,P,k} = l^0_{I,i,j,k}\n",
    "$$\n",
    "\n",
    "where $P$ is the padding. \n",
    "\n",
    "\n",
    "The convolution part gives the output\n",
    "\n",
    "$$\n",
    "l^1_{I,i,j,m} = \\sum_{\\alpha,\\beta,k} \\tilde l^0_{I,si+\\alpha,sj+\\beta,k} W_{\\alpha,\\beta,k,m}\n",
    "$$\n",
    "\n",
    "where $s$ is the stride. Note that both the padding and the stride can be different for different directions but we take them the same for simplicity. The effect of padding is to increase the image size  additively and that of the stride is to decrease it multiplicaively.\n",
    "\n",
    "In fact if the size of the original image is $n$ then the size of the ouput is $\\tilde n=[\\frac{n+2P-K}{s}]+1$ where $[x]$ means the integral part of $x$.\n",
    "\n",
    "The back propagation is easy to workout. For the weights we get \n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial W_{\\alpha,\\beta,k,m}} = \\sum_{I,i,j} \\frac{\\partial L}{\\partial l^1_{I,i,j,m}} \\tilde l^0_{I,si+\\alpha,sj+\\beta,k}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And for the input layer it is\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial l^0_{I,p,q,l}} = \\sum_{\\alpha,\\beta,m} \\left(\\frac{\\partial L}{\\partial l^1} \\right)_{I,\\frac{p+P-\\alpha}{s} , \\frac{q+P-\\beta}{s},m} W_{\\alpha,\\beta,l,m} \\\\\n",
    "=  \\sum_{\\alpha,\\beta,m} \\left(\\frac{\\partial L}{\\partial l^1} \\right)_{I,\\frac{p+P-K+1+\\alpha}{s} , \\frac{q+P-K+1+\\beta}{s},m} \\tilde W_{\\alpha,\\beta,m,l}\n",
    "$$\n",
    "\n",
    "where\n",
    "\n",
    "$$\n",
    "\\tilde W_{\\alpha,\\beta,m,l} = W_{K-\\alpha, K-\\beta,l,m}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which is just a convolution with the filter flipped."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the intresting thing is that we can first embed the error wrt to the output in an array of size $s \\tilde n$\n",
    "\n",
    "$$\n",
    "z[I,si,sj,m]=\\left(\\frac{\\partial L}{\\partial l^1} \\right)_{I,i,j,m}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and then depending on the sign of $P-K+1$ we either embed $z$ on a left side zero padded array $y$ or embed part of the array $z$ from the starting of the array $y$ as below. The right side of the array $y$ is zero padded by $P$ in either case.\n",
    "\n",
    "Note that in case $P < (K-1)/2$ we need to zero bad z on the right so that its size is at least that out the input array."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "p1_left = P1 + 1 - K1\n",
    "#p1_right = P1\n",
    "\n",
    "p2_left = P2 + 1 - K2\n",
    "#p2_right = P2\n",
    "\n",
    "# extra size to allot to y compared to z\n",
    "# d1 = p1_right - p1_left \n",
    "# d2 = p2_right - p2_left\n",
    "\n",
    "\n",
    "# start position in z\n",
    "i1 = max(0, p1_left)\n",
    "i2 = max(0, p2_left)\n",
    "\n",
    "# start position in y\n",
    "iy1=i1-p1_left\n",
    "iy2=i2-p2_left\n",
    "\n",
    "# size of array taken from z\n",
    "f1 = z.shape[1] - s1\n",
    "f2 = z.shape[2] - s2\n",
    "y = np.zeros(shape=(z.shape[0], z.shape[1] + K1-1, z.shape[2] + K2-1, x.shape[3]))\n",
    "y[:,iy1:iy1 + f1,iy2:iy2 + f2] = z[:, i1:, i2:, :]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The we have\n",
    "\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial l^0_{I,p,q,l}}=\\sum_{\\alpha,\\beta,m} y_{I,p+\\alpha,q+\\beta,m} \\tilde W_{\\alpha,\\beta,m,l}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tensorflow 2",
   "language": "python",
   "name": "tensorflow2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}