tp2_convolution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolution naïve\n",
    "\n",
    "Jusqu'à présent, nous avons utilisé des réseaux multi-couches pleinement connectées.  Les opérations à chaque couche étaient de type *multiplication matrice-vecteur* suivies d'une non-linéarité. Dans ce deuxième travail pratique, nous aborderons un nouveau type de couche : la **couche convolutive**.  Mais avant de commencer à tester des réseaux de neurones à convolution, commençons à explorer la notion de \"convolution\".\n",
    "\n",
    "L'objectif de ce notebook est de vous amener à coder une **version naïve de la convolution**, version que vous pourrez récupérer par la suite.\n",
    "\n",
    "\n",
    "## NOTE IMPORTANTE!\n",
    "\n",
    "Dans ce notebook, nous utiliserons la **fonction d'activation identité** selon laquelle : \n",
    "\n",
    "$$\n",
    "f(x) = x\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "from utils.data_utils import load_CIFAR10\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots\n",
    "plt.rcParams['image.interpolation'] = 'nearest'\n",
    "plt.rcParams['image.cmap'] = 'gray'\n",
    "\n",
    "# Pour automatiquement recharger les modules externes\n",
    "# voir http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolution version 1.0\n",
    "\n",
    "On commence ici avec une opération très simple: convoluer une image de taille\n",
    "## **4x4**\n",
    "par un filtre de taille\n",
    "## **2x2**\n",
    "**Pas de padding et le stride = 1.**  Le résultat doit être de taille\n",
    "## **3x3**\n",
    "La fonction *convolution_naive* est dans le fichier *Conv.py*.  Puisque le tenseur de sortie doit avoir le contenu suivant :\n",
    "\n",
    "\n",
    "|   |   |   |\n",
    "|---|---|---|\n",
    "| 5 | 6 | 5 |\n",
    "| 6 | 7 | 8 |\n",
    "| 8 | 8 | 9 |\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from layers.ConvNaive import convolution_naive_npdl\n",
    "\n",
    "x_shape = (1, 1, 4, 4)  # (N=1 batch, C=1 channels, H=4 largeur du feature map, W=4 Hauteur du feature map)\n",
    "w_shape = (1, 1, 2, 2)  # (F=1 Nb feature maps en sortie, C=1 channels, HH=2 hauteur du filtre, WW=2 largeur du filtre)\n",
    "x = np.floor(10*np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape))\n",
    "w = np.floor(10*np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape))\n",
    "b = np.floor(10*np.linspace(-0.1, 0.2, num=w.shape[0]))\n",
    "\n",
    "correct_out = np.array([[[[5, 6, 5],\n",
    "                            [6, 7, 8],\n",
    "                            [8, 8, 9]]]])\n",
    "\n",
    "print('Input = \\n', x)\n",
    "print('Filter = \\n', w)\n",
    "print('Bias = ', b)\n",
    "conv_param = {'stride': 1, 'pad': 0}\n",
    "out, _ = convolution_naive_npdl(x, w, b, conv_param, True)\n",
    "print('Output = \\n', out)\n",
    "\n",
    "# La différence entre la sortie \"out\" et la sortie attendue \"correct_out\" devrait être proche de 0\n",
    "print('difference: ', np.sum(np.power(out-correct_out,2).flatten()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolution version 2.0\n",
    "\n",
    "Opération un peu plus compliquée : convoluer une image ayant 2 canaux de taille\n",
    "## **4x4x2**\n",
    "par un filtre de taille\n",
    "## **2x2x2**\n",
    "**Pas de padding et le stride = 1.**  Le résultat doit être de taille\n",
    "## **3x3**\n",
    "Le tenseur de sortie doit avoir le contenu suivant :\n",
    "\n",
    "\n",
    "|   |   |   |\n",
    "|---|---|---|\n",
    "| 19 | 21 | 20 |\n",
    "| 21 | 22 | 22 |\n",
    "| 21 | 22 | 23 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x_shape = (1, 2, 4, 4)  # (N=1 batch, C=2 channels, H=4 largeur du feature map, W=4 Hauteur du feature map)\n",
    "w_shape = (1, 2, 2, 2)  # (F=1 Nb feature maps en sortie, C=2 channels, HH=2 hauteur du filtre, WW=2 largeur du filtre)\n",
    "x = np.floor(10*np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape))\n",
    "w = np.floor(10*np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape))\n",
    "b = np.floor(10*np.linspace(-0.1, 0.2, num=w.shape[0]))\n",
    "\n",
    "correct_out = np.array([[[[19, 21, 20],\n",
    "                            [21, 22, 22],\n",
    "                            [21, 22, 23]]]])\n",
    "\n",
    "print('Input = \\n', x)\n",
    "print('Filter = \\n', w)\n",
    "print('Bias = ', b)\n",
    "conv_param = {'stride': 1, 'pad': 0}\n",
    "out, _ = convolution_naive_npdl(x, w, b, conv_param, True)\n",
    "print(out)\n",
    "\n",
    "# La différence entre la sortie \"out\" et la sortie attendue \"correct_out\" devrait être proche de 0\n",
    "print('difference: ', np.sum(np.power(out-correct_out,2).flatten()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolution version 3.0\n",
    "\n",
    "Ici on convolue une image ayant 2 canaux.  L'image est de taille\n",
    "## **2x4x4**\n",
    "et le filtre est de taille\n",
    "## **2x4x4**\n",
    "Puisque le filtre et l'image sont de même taille et que le padding = 0 et stride =1 alors résultat doit un tableau de taille\n",
    "## **1x1**\n",
    "Le tenseur de sortie doit avoir le contenu suivant : **86**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x_shape = (1, 2, 4, 4)  # (N=1 batch, C=2 channels, H=4 largeur du feature map, W=4 Hauteur du feature map)\n",
    "w_shape = (1, 2, 4, 4)  # (F=1 Nb feature maps en sortie, C=2 channels, HH=4 hauteur du filtre, WW=4 largeur du filtre)\n",
    "x = np.floor(10*np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape))\n",
    "w = np.floor(10*np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape))\n",
    "b = np.floor(10*np.linspace(-0.1, 0.2, num=w.shape[0]))\n",
    "\n",
    "correct_out = np.array([[[[86]]]])\n",
    "\n",
    "print('Input = \\n', x)\n",
    "print('Filter = \\n', w)\n",
    "print('Bias = ', b)\n",
    "conv_param = {'stride': 1, 'pad': 0}\n",
    "out, _ = convolution_naive_npdl(x, w, b, conv_param, True)\n",
    "print(out)\n",
    "\n",
    "# La différence entre la sortie \"out\" et la sortie attendue \"correct_out\" devrait être proche de 0\n",
    "print('difference: ', np.sum(np.power(out-correct_out,2).flatten()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolution version 4.0\n",
    "\n",
    "**ATTENTION! ici on va tester un padding et un stride différent** \n",
    "\n",
    "Pour ce faire, nous allons convoluer une image ayant 2 canaux.  L'image est de taille\n",
    "## **2x4x4**\n",
    "et le filtre est de taille\n",
    "## **2x4x4**\n",
    "Puisque le filtre et l'image sont de même taille et que le **padding = 1 et le stride = 2** alors résultat doit être un tableau de taille\n",
    "## **2x2**\n",
    "Le tenseur de sortie doit avoir le contenu suivant : \n",
    "\n",
    "| | |\n",
    "|-|-|\n",
    "|52|49|\n",
    "|37|29|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x_shape = (1, 2, 4, 4)  # (N=1 batch, C=2 channels, H=4 largeur du feature map, W=4 Hauteur du feature map)\n",
    "w_shape = (1, 2, 4, 4)  # (F=1 Nb feature maps en sortie, C=2 channels, HH=4 hauteur du filtre, WW=4 largeur du filtre)\n",
    "x = np.floor(10*np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape))\n",
    "w = np.floor(10*np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape))\n",
    "b = np.floor(10*np.linspace(-0.1, 0.2, num=w.shape[0]))\n",
    "\n",
    "correct_out = np.array([[[[52, 49],\n",
    "                            [37, 29]]]])\n",
    "\n",
    "print('Input = \\n', x)\n",
    "print('Filter = \\n', w)\n",
    "print('Bias = ', b)\n",
    "conv_param = {'stride': 2, 'pad': 1}\n",
    "out, _ = convolution_naive_npdl(x, w, b, conv_param, True)\n",
    "print(out)\n",
    "\n",
    "# La différence entre la sortie \"out\" et la sortie attendue \"correct_out\" devrait être proche de 0\n",
    "print('difference: ', np.sum(np.power(out-correct_out,2).flatten()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolution version 5.0\n",
    "\n",
    "Dernier test!  \n",
    "\n",
    "Nous allons ici convoluer **une batch de deux images** ayant chacune **3 canaux**.  La batch est un tenseur de taille\n",
    "## **2x3x4x4**\n",
    "De plus, nous appliquerons **3 filtres**.  Le tenseur de filtre est de taille\n",
    "## **3x3x4x4**\n",
    "Puisque le filtre et l'image ont tous deux 4 colonnes et 4 lignes et que le **padding = 1 et le stride = 2** alors résultat être une **batch de deux éléments ayant chacun trois feature maps**.  Le tenseur de sortie doit être de taille\n",
    "## **2x3x2x2**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x_shape = (2, 3, 4, 4)  # (N=2 batch, C=3 channels, H=4 largeur du feature map, W=4 Hauteur du feature map)\n",
    "w_shape = (3, 3, 4, 4)  # (F=3 nb feature maps en sortie, C=3 channels, HH=4 hauteur du filtre, WW=4 largeur du filtre)\n",
    "x = np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape)\n",
    "w = np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape)\n",
    "b = np.linspace(-0.1, 0.2, num=3)\n",
    "\n",
    "conv_param = {'stride': 2, 'pad': 1}\n",
    "out, _ = convolution_naive_npdl(x, w, b, conv_param, True)\n",
    "correct_out = np.array([[[[[-0.08759809, -0.10987781],\n",
    "                           [-0.18387192, -0.2109216 ]],\n",
    "                          [[ 0.21027089,  0.21661097],\n",
    "                           [ 0.22847626,  0.23004637]],\n",
    "                          [[ 0.50813986,  0.54309974],\n",
    "                           [ 0.64082444,  0.67101435]]],\n",
    "                         [[[-0.98053589, -1.03143541],\n",
    "                           [-1.19128892, -1.24695841]],\n",
    "                          [[ 0.69108355,  0.66880383],\n",
    "                           [ 0.59480972,  0.56776003]],\n",
    "                          [[ 2.36270298,  2.36904306],\n",
    "                           [ 2.38090835,  2.38247847]]]]])\n",
    "print(out)\n",
    "print(out.shape)\n",
    "\n",
    "# La différence entre la sortie \"out\" et la sortie attendue \"correct_out\" devrait être proche de 0\n",
    "print('difference: ', np.sum(np.power(out-correct_out,2).flatten()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sanity check\n",
    "\n",
    "Convoluons maintenant 2 *vraies* images couleurs.  Le premier filtre est un filtre faisant la **moyenne des canaux rouge-vert-bleu**; le résultat est une image en niveau de gris.  Le 2e filtre est un filtre qui détecte les contours horizontaux rouges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.pyplot import imread\n",
    "from skimage.transform import resize\n",
    "\n",
    "stripes = imread('datasets/stripes.jpg')\n",
    "wolf = imread('datasets/wolf.jpg')\n",
    "\n",
    "img_size = 200   # Make this smaller if it runs too slow\n",
    "stripes_resized = resize(stripes, (img_size, img_size))\n",
    "wolf_resized = resize(wolf, (img_size, img_size))\n",
    "\n",
    "x = np.zeros((2, 3, img_size, img_size))\n",
    "x[0, :, :, :] = stripes_resized.transpose((2, 0, 1))\n",
    "x[1, :, :, :] = wolf_resized.transpose((2, 0, 1))\n",
    "\n",
    "# Set up a convolutional weights holding 2 filters, each 3x3\n",
    "w = np.zeros((2, 3, 3, 3))\n",
    "\n",
    "# The first filter converts the image to grayscale.\n",
    "# Set up the red, green, and blue channels of the filter.\n",
    "w[0, 0, :, :] = [[0, 0, 0], [0, 0.333, 0], [0, 0, 0]]\n",
    "w[0, 1, :, :] = [[0, 0, 0], [0, 0.334, 0], [0, 0, 0]]\n",
    "w[0, 2, :, :] = [[0, 0, 0], [0, 0.333, 0], [0, 0, 0]]\n",
    "\n",
    "\n",
    "# Second filter detects horizontal edges in the blue channel.\n",
    "w[1, 0, :, :] = [[1, 0, -1], [2, 0, -1], [1, 0, -1]]\n",
    "\n",
    "# Vector of biases. We don't need any bias for the grayscale\n",
    "# filter, but for the edge detection filter we want to add 128\n",
    "# to each output so that nothing is negative.\n",
    "b = np.array([0, 128])\n",
    "\n",
    "# Compute the result of convolving each input in x with each filter in w,\n",
    "# offsetting by b, and storing the results in out.\n",
    "out, _ = convolution_naive_npdl(x, w, b, {'stride': 1, 'pad': 1})\n",
    "\n",
    "def imshow_noax(img, normalize=True):\n",
    "    \"\"\" Tiny helper to show images as uint8 and remove axis labels \"\"\"\n",
    "    if normalize:\n",
    "        img_max, img_min = np.max(img), np.min(img)\n",
    "        img = 255.0 * (img - img_min) / (img_max - img_min)\n",
    "    plt.imshow(img.astype('uint8'))\n",
    "    plt.gca().axis('off')\n",
    "\n",
    "# Show the original images and the results of the conv operation\n",
    "plt.subplot(2, 3, 1)\n",
    "imshow_noax(stripes_resized)\n",
    "plt.title('Image origine')\n",
    "plt.subplot(2, 3, 2)\n",
    "imshow_noax(out[0,0,:,:])\n",
    "plt.title('Image en niveaux de gris')\n",
    "plt.subplot(2, 3, 3)\n",
    "imshow_noax(out[0,1,:,:])\n",
    "plt.title('Contours horizontaux')\n",
    "plt.subplot(2, 3, 4)\n",
    "imshow_noax(wolf_resized)\n",
    "plt.subplot(2, 3, 5)\n",
    "imshow_noax(out[1, 0])\n",
    "plt.subplot(2, 3, 6)\n",
    "imshow_noax(out[1, 1])\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rétro-propagation\n",
    "\n",
    "Maintenant que la propagation avant de la convolution fonctionne, il faut coder la **rétro-propagation**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question :\n",
    "\n",
    "Avant de commencer à coder, expliquez mathématiquement en quoi consiste le gradient d'une convolution par rapport aux variables x, w et b, à savoir les variables dx, dw et db dans le code.  Pour vous aider, vous pouvez vous référez au document que voici:\n",
    "\n",
    "https://becominghuman.ai/back-propagation-in-convolutional-neural-networks-intuition-and-code-714ef1c38199\n",
    "\n",
    "## Votre réponse : ...\n",
    "Question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Commençons avec un cas facile, déjà testé auparavant : \n",
    "#    batch de 1 image 4x4 avec 1 channel, un filtre 2x2, pas de padding et un stride de 1 \n",
    "\n",
    "from layers.ConvNaive import convolution_naive_npdl, backward_convolution_naive_npdl\n",
    "\n",
    "x_shape = (1, 1, 4, 4)  # (N=1 batch, C=1 channels, H=4 largeur du feature map, W=4 Hauteur du feature map)\n",
    "w_shape = (1, 1, 2, 2)  # (F=1 Nb feature maps en sortie, C=1 channels, HH=2 hauteur du filtre, WW=2 largeur du filtre)\n",
    "x = np.floor(10*np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape))\n",
    "w = np.floor(10*np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape))\n",
    "b = np.floor(10*np.linspace(-0.1, 0.2, num=w.shape[0]))\n",
    "dOut = np.ones((1,1,3,3))\n",
    "correct_dx = np.array([[[[-2, -3, -3, -1],\n",
    "                         [-1,  1,  1,  2],\n",
    "                         [-1,  1,  1,  2],\n",
    "                         [ 1,  4,  4,  3]]]])\n",
    "correct_dw = np.array([[[[6, 9],\n",
    "                          [20,24]]]])\n",
    "correct_db = np.array([9])\n",
    "\n",
    "conv_param = {'stride': 1, 'pad': 0}\n",
    "out, cache = convolution_naive_npdl(x, w, b, conv_param, True)\n",
    "dx, dw, db = backward_convolution_naive_npdl(dOut, cache)\n",
    "\n",
    "# La différence entre la sortie \"out\" et la sortie attendue \"correct_out\" devrait être proche de 0\n",
    "print('difference dx: ', np.sum(np.power(dx-correct_dx,2).flatten()))\n",
    "print('difference dw: ', np.sum(np.power(dw-correct_dw,2).flatten()))\n",
    "print('difference db: ', np.sum(np.power(db-correct_db,2).flatten()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Allons-y maintenant avec un cas plus réaliste :\n",
    "#  batch de 4 images 7x7 ayant chacune 3 channels.  Il y a 2 filtres de taille 3x3x3\n",
    "# \n",
    "# Pour valider que votre convolution fonctionne bien, nous utiliserons le gradient numérique suivant \n",
    "\n",
    "\n",
    "def eval_numerical_gradient_array(f, x, df, h=1e-5):\n",
    "    \"\"\"\n",
    "    Evaluate a numeric gradient for a function that accepts a numpy\n",
    "    array and returns a numpy array.\n",
    "    \"\"\"\n",
    "    grad = np.zeros_like(x)\n",
    "    it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])\n",
    "    while not it.finished:\n",
    "        ix = it.multi_index\n",
    "\n",
    "        oldval = x[ix]\n",
    "        x[ix] = oldval + h\n",
    "        pos = f(x).copy()\n",
    "        x[ix] = oldval - h\n",
    "        neg = f(x).copy()\n",
    "        x[ix] = oldval\n",
    "\n",
    "        grad[ix] = np.sum((pos - neg) * df) / (2 * h)\n",
    "        it.iternext()\n",
    "    return grad\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.random.randn(4, 3, 7, 7)\n",
    "w = np.random.randn(2, 3, 3, 3)\n",
    "b = np.random.randn(2,)\n",
    "dout = np.random.randn(4, 2, 5, 5)\n",
    "conv_param = {'stride': 1, 'pad': 0}\n",
    "\n",
    "out, cache = convolution_naive_npdl(x, w, b, conv_param)\n",
    "dx, dw, db = backward_convolution_naive_npdl(dout, cache)\n",
    "\n",
    "# La différence entre un gradient numérique et votre gradient devrait être inférieure à 1e-9'\n",
    "dx_num = eval_numerical_gradient_array(lambda x: convolution_naive_npdl(x, w, b, conv_param)[0], x, dout)\n",
    "dw_num = eval_numerical_gradient_array(lambda w: convolution_naive_npdl(x, w, b, conv_param)[0], w, dout)\n",
    "db_num = eval_numerical_gradient_array(lambda b: convolution_naive_npdl(x, w, b, conv_param)[0], b, dout)\n",
    "print('difference dx: ', np.sum(np.power(dx-dx_num,2).flatten()))\n",
    "print('difference dw: ', np.sum(np.power(dw-dw_num,2).flatten()))\n",
    "print('difference db: ', np.sum(np.power(db-db_num,2).flatten()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}