Introduction aux réseaux de neurones.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction aux réseaux de neurones\n",
    "\n",
    "## Partie 1 - Classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "import numpy as np\n",
    "import math\n",
    "import random\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",
    "from dojo.dataset import Cifar10Dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chargement du dataset\n",
    "\n",
    "Durant ce dojo, nous utiliserons le dataset CIFAR10. Ce dataset comprend 60000 images RGB 32 par 32 de 10 classes différentes:\n",
    "\n",
    "0. airplane\n",
    "1. automobile\n",
    "2. bird\n",
    "3. cat\n",
    "4. deer\n",
    "5. dog\n",
    "6. frog\n",
    "7. horse\n",
    "8. ship\n",
    "9. truck\n",
    "\n",
    "Il existe également le dataset CIFAR100, qui a lui 100 classes distinctes. Pour plus de détails, voir le [site officiel](https://www.cs.toronto.edu/~kriz/cifar.html).\n",
    "\n",
    "Évaluez les cellules suivante pour télécharger le jeu de données. Normalement, vous devriez voir qu'il y a 50000 images dans les données d'entraînement et 10000 images dans les données de test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cifar10 = Cifar10Dataset()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(cifar10.x_train.shape)\n",
    "print(cifar10.y_train.shape)\n",
    "print(cifar10.x_test.shape)\n",
    "print(cifar10.y_test.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Visualize some examples from the dataset.\n",
    "# We show a few examples of training images from each class.\n",
    "classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']\n",
    "num_classes = len(classes)\n",
    "samples_per_class = 7\n",
    "for y, cls in enumerate(classes):\n",
    "    idxs = np.flatnonzero(cifar10.y_train == y)\n",
    "    idxs = np.random.choice(idxs, samples_per_class, replace=False)\n",
    "    for i, idx in enumerate(idxs):\n",
    "        plt_idx = i * num_classes + y + 1\n",
    "        plt.subplot(samples_per_class, num_classes, plt_idx)\n",
    "        plt.imshow(cifar10.x_train[idx].astype('uint8'))\n",
    "        plt.axis('off')\n",
    "        if i == 0:\n",
    "            plt.title(cls)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Le problème de classification\n",
    "\n",
    "Regardons la première image:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(cifar10.x_train[0])\n",
    "print(cifar10.y_train[0])\n",
    "plt.imshow(cifar10.x_train[0].astype('uint8'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Cette image est comprise par un humain comme étant une grenouille. Par contre, pour un ordinateur, cette image n'est rien de plus q'un tableau de 32 x 32 x 3 nombres à virgule flottante. Le problème de classification d'image est donc le suivant:\n",
    " \n",
    " \n",
    "> Étant donné des images $x_i$ et leurs étiquettes $y_i$, trouvez la fonction $f(X): x \\rightarrow y$ qui maximise le bon nombre d'associations entre les images et les étiquettes et qui se généralise à des images inconnues.\n",
    "\n",
    "\n",
    "### k-Nearest Neighbor\n",
    "\n",
    "Un des algorithmes les plus simple pour résoudre le problème de classification est k-Nearest Neighbor (kNN). k est un hyper-paramètre de l'algorithme, c'est-à-dire un paramètre qui est choisi par le programmeur de l'algorithme en fonction de l'application. L'algorithme fonctionne comme suit:\n",
    "\n",
    "Étant donné un point de test $x$, on regarde les $k$ voisins les plus proches et on procède à un vote de majorité sur la classe que devrait avoir $x$. Voici un exemple visuel où les données ont deux dimensions (x, y) et il y a trois classes possibles (bleu, rouge et vert).\n",
    "\n",
    "![kNN](http://cs231n.github.io/assets/knn.jpeg)\n",
    "\n",
    "Pour obtenir les voisins les plus proches, il faut d'abord se choisir une métrique de distance. Souvent, on utilise la distance L2 (ou distance euclidienne). Dans le cas 2D, on a:\n",
    "\n",
    "$$\n",
    "d = \\sqrt{x^2 + y^2}\n",
    "$$\n",
    "\n",
    "On peut utiliser la même métrique pour des images en comparant pixel par pixel chacune des valeurs de r, g et b.\n",
    "\n",
    "#### Exercice\n",
    "\n",
    "Complétez le fichier k_nearest_neighbor.py situé dans le dossier dojo. Dans un premier temps, complétez la fonction `compute_distances_two_loops`. Vous pouvez viusaliser le résultat avec le code suivant:\n",
    "\n",
    "> **NOTE** Nous utiliserons ici que le dixième du dataset. Les images rgb sont redimensionnées en vecteur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from dojo.k_nearest_neighbor import KNearestNeighbor\n",
    "\n",
    "n_of_train = 5000\n",
    "n_of_test = 500\n",
    "\n",
    "x_train, y_train = cifar10.x_train[:n_of_train], cifar10.y_train[:n_of_train]\n",
    "x_test, y_test = cifar10.x_test[:n_of_test], cifar10.y_test[:n_of_test]\n",
    "x_train = x_train.reshape((n_of_train, -1))\n",
    "x_test = x_test.reshape((n_of_test, -1))\n",
    "\n",
    "print(x_train.shape)\n",
    "\n",
    "classifier = KNearestNeighbor()\n",
    "classifier.train(x_train, y_train)\n",
    "\n",
    "dists = classifier.compute_distances_two_loops(x_test) # May take some time to compute\n",
    "print(dists.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.imshow(dists, interpolation='none')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Que représentent les colonnes claires? Les colonnes foncées?\n",
    "\n",
    "Maintenant, implémentez la fonction `predict_labels`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# We use k = 1 (which is Nearest Neighbor).\n",
    "y_test_pred = classifier.predict_labels(dists, k=3)\n",
    "\n",
    "# Compute and print the fraction of correctly predicted examples\n",
    "num_correct = np.sum(y_test_pred == y_test)\n",
    "accuracy = float(num_correct) / n_of_test\n",
    "print('Got %d / %d correct => accuracy: %f' % (num_correct, n_of_test, accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Votre algorithme devrait obtenir environ 27% d'accuracy. Vous pouvez jouer avec le paramètre $k$ pour regarder si les résultats s'améliorent ou non. Quelle est la meilleure valeur de k?\n",
    "\n",
    "#### Discussion\n",
    "- Peut-on utiliser kNN dans la forme présentée plus haut pour la classification de grands dataset?\n",
    "- Nommer une limitation de l'algorithme.\n",
    "- Comment avez-vous choisi la valeur de k? Avez-vous utilisé les données de test?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partie 2 - Backpropagation\n",
    "\n",
    "Dans la partie précédente, nous avons vu une manière assez limitée de faire de la classification. En effet, il faut précalculer une matrice de distances, puis itérer sur cette matrice pour faire un vote de majorité, ce qui est extrèmement coûteux. Idéalement, nous aimerions avoir un algorithme qui apprend itérativement en s'améliorant à chaque étape. L'algorithme aurait la forme suivante:\n",
    "\n",
    "1. On donne à l'algorithme une donnée ou une mini-batch de données (ex. 64 points) au hasard.\n",
    "2. L'algorithme utilise ses paramètre actuels pour prédire les étiquettes des données.\n",
    "3. L'algorithme évalue l'erreur produite sur cette évaluation\n",
    "4. L'algorithme évalue le rôle de chaque paramètre sur cette erreur.\n",
    "5. L'algorithme ajuste ces paramètres.\n",
    "6. goto 1.\n",
    "\n",
    "Les étapes 3. et 4. sont le nerf de la guerre. Ce qui est décrit en 3. est s'appelle la *loss function*. L'étape 4. est résolue par une technique qui s'appelle la *backpropagation*. \n",
    "\n",
    "Le but est de trouver un minimum local où la fonction de loss est la plus petite possible en se déplacant dans le sens du gradient.\n",
    "\n",
    "![gradient-descent](http://sebastianruder.com/content/images/2016/09/saddle_point_evaluation_optimizers.gif)\n",
    "\n",
    "\n",
    "Voyons ces étapes en détail à l'aide d'un exemple jouet avant de s'attaquer au problème de classification.\n",
    "\n",
    "### Fitting de courbe polynomiale\n",
    "\n",
    "Le dataset suivant est constitué de points $(x, y)$ où $y = ax^2 + bx + c + \\sigma$, où sigma représente du bruit dans la fonction.\n",
    "\n",
    "> **ATTENTION** En temps normal, on ne connais pas la distribution statistique des données d'entraînement, ce qui rend le problème extrêmement plus complexe.\n",
    "\n",
    "Notre algorithme tenteras d'estimer les paramètre a, b et c.\n",
    "Dans un premier temps, initialisons le dataset et les paramètres de la fonction à apprendre:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from dojo.dataset import PolynomialDataset\n",
    "\n",
    "min_param, max_param = (0, 100)\n",
    "poly_data = PolynomialDataset(min_param=min_param, max_param=max_param)\n",
    "n_of_train = poly_data.x_train.shape[0]\n",
    "n_of_test = poly_data.x_test.shape[0]\n",
    "print(n_of_train, n_of_test)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### *Loss function*\n",
    "Écrivez la *loss function*. Il s'agit de la différence entre le vrai $y$ et le $y$ prédit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def loss_function(y_predicted, y_ground_truth):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Backprop\n",
    "\n",
    "Maintenant, il faut regarder comment a, b et c affectent l'erreur sur la prédiction. Pour se faire, il faut calculer les dérivées partielles de la fonction. Cela fait du sens puisque ces dérivées partiellent indiquent comment chaque paramètre influence la sortie de la fonction.\n",
    "\n",
    "$$\n",
    "f(x) = ax^2 + bx + c\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial f}{\\partial a} = x^2\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial f}{\\partial b} = x\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial f}{\\partial c} = 1\n",
    "$$\n",
    "\n",
    "#### Exercice\n",
    "Écrivez la fonction qui retourne le gradient (vecteur des dérivées partielles). Ce vecteur de gradient doit être modulé (multiplié) par le loss."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gradient(x, loss):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Entraînement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "learning_rate = 1e-2\n",
    "\n",
    "a, b, c = 0.0, 0.0, 0.0\n",
    "\n",
    "print(a, b, c)\n",
    "\n",
    "for i in range(3000):\n",
    "    random_index = random.randint(0, n_of_train - 1)\n",
    "    x = poly_data.x_train[random_index]\n",
    "    y = poly_data.y_train[random_index]\n",
    "    y_predicted = a * x**2 + b * x + c\n",
    "    \n",
    "    # TODO\n",
    "    loss = 0\n",
    "    da, db, dc = [0, 0, 0]\n",
    "    \n",
    "    #TODO - update a, b, c with da, db, dc and learning_rate\n",
    "    \n",
    "    \n",
    "    if i % 20 == 0:\n",
    "        print(\"Step %d: a: %f b: %f c: %f\" % (i, round(a, 2), round(b, 2), round(c, 2)))\n",
    "        print(\"---loss: %f\" % loss)\n",
    "        \n",
    "print(\"TRAINING FINISHED\")\n",
    "print(\"ESTIMATED PARAMS a: %f b: %f c: %f\" % (round(a, 2), round(b, 2), round(c, 2)))\n",
    "print(\"ACTUAL PARAMS a: %d b: %d c: %d\" % (poly_data.a, poly_data.b, poly_data.c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Discussion:\n",
    "- Comment se comporte le loss au fil du temps?\n",
    "- Décrivez le comportement des paramètres a, b, c au fil du temps.\n",
    "- À quoi sert le learning rate? Modifiez la valeur et observez le comportement.\n",
    "- Modifier les valeurs initiales des paramètres et observez le comportement.\n",
    "- Comment peut-on vérifier que les paramètres a, b et c sont les bons?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partie 3 - Classification linéaire\n",
    "\n",
    "Dans cette partie, nous développerons un modèle de classification linéaire pour le dataset CIFAR10. Le but est d'avoir une approche itérative de descente de gradient comme à la partie 2. Si vous comprenez bien ce modèle, vous comprendrez aussi les réseaux de neurones, qui sont simplement la combinaison de plusieurs modèles linéaires.\n",
    "\n",
    "\n",
    "Revenons au problème de classification. Rappel:\n",
    "\n",
    "> Étant donné des images $x_i$ et leurs étiquettes $y_i$, trouvez la fonction $f(X): x \\rightarrow y$ qui maximise le bon nombre d'associations entre les images et les étiquettes et qui se généralise à des images inconnues.\n",
    "\n",
    "\n",
    "On peut décomposer la fonction $f$ en plusieurs fonctions. Au lieu d'avoir une fonction unique qui retourne directment l'étiquette $y$ de l'image, on peut avoir une fonction par classe du dataset et chaque fonction retourne le score associé à l'image en entrée qui indique à quel point il est probable que l'image est cette classe. Par exemple, si le dataset a seulement deux classes, 0 pour chien et 1 pour chat, nous aurions deux fonctions $f_0(X)$ et $f_1(X)$. Pour une image donnée $x_i$, si on a $f_0(x_i) = 0.6$ et $f_1(x_i) = 0.2$, on en déduit que l'image $x_i$  est un chien, car selon les fonctions, il est plus probable que l'image soit un chien. Voici une représentation visuelle des fonction $f_j(x)$. À noter, la figure est en 2D, mais dans le cas réel, les fonctions séparent les images dans un espace à $32 \\times 32 \\times 3 = 3072$ dimensions.\n",
    "\n",
    "![classification figure](http://cs231n.github.io/assets/pixelspace.jpeg)\n",
    "\n",
    "La classification linéaire est un modèle très simple pour représenter les fonctions $f_j(x)$. La formulation est la suivante:\n",
    "\n",
    "$$\n",
    "f_j(x) = w_j \\cdot x + b_j\n",
    "$$\n",
    "\n",
    "\n",
    "Dans la formule précédente, le vecteur $w_j$ représente les poids (ou *weights* en anglais) à associer à chaque pixel de l'image $x$ et $b_j$ est un scalaire qui représente le biais, c'est-à-dire si à priori il est plus probable d'observer la classe $j$.\n",
    "\n",
    "\n",
    "Pour que le calcul soit plus efficace, il est possible de calculer tous les scores $f_j(x)$ en même temps. Il suffit de mettre tous les vecteurs $w_j$ dans une matrice $W$ où chaque ligne $j$ est $w_j$ et de faire le produit matriciel $Wx$, puis additionner un vecteur $b$ qui contient les biais. Cela revient exactement au même que de faire les produit scalaires séparemment. Voici une représentation visuelle cette opération:\n",
    "\n",
    "\n",
    "> **NOTE** Pour simplifier les calculs, $x$ est redimensionné en un vecteur de 3072 éléments. Ainsi, il est très facile d'associer un point à chaque pixel et multiplier ces points à $x$, puisque cela se résume en un produit scalaire.\n",
    "\n",
    "> **NOTE** Pour simplifier encore plus les calculs, on peut ajouter un élément 1 dans $x$ et une colonne à $W$. Cela revient exactement au même que d'additionner séparemment $b$.\n",
    "\n",
    "![weight matrix](http://cs231n.github.io/assets/imagemap.jpg)\n",
    "\n",
    "\n",
    "### Généralisation\n",
    "\n",
    "La généralisation est un élément primordial en machine learning. C'est bien beau d'être capable de classifier correctement les données d'entraînement, mais il faut à tout prix éviter le phénomène d'*overfitting*. L'exemple classique est de trouver la courbe qui passe par une série de points. Si on a $n$ points, il est possible de trouver un polynôme de degré $n + 1$ qui passe parfaitement par tous les points. Par contre, cette courbe risque de moins bien performer qu'un modèle plus simple. pour passer à travers les autres points de la distribution que l'on n'as pas encore observé.\n",
    "\n",
    "![overfitting](https://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Overfitted_Data.png/300px-Overfitted_Data.png)\n",
    "\n",
    "\n",
    "Généralement, en machine learning, on sépare les données en deux groupes: *training* et *testing*. Ainsi, on peut évaluer la performance du modèle sur les données inconnues en utilisant des données qui n'ont pas servi à l'entraînement.\n",
    "\n",
    "### *Loss function* - Softmax\n",
    "\n",
    "Contrairement à la partie 2 où nous voulions faire de la *régression*, on ne peut pas directement calculé l'erreur sur l'estimé de la fonction. Pour la classification, nous untiliserons une *loss function* appelée **softmax**. \n",
    "\n",
    "Disons qu'on veut classifier un dataset qui a uniquement deux classes: chien et chat. Puisqu'il y a deux classes, la fonction retourne un vecteur de deux éléments. Si, étant donné une image de chien, la fonction retourne le vecteur suivant:\n",
    "\n",
    "$$\n",
    "f_j(x) = [-0.04, 0.12]\n",
    "$$\n",
    "\n",
    "On peut interpréter ces valeurs **comme le log de la probabilité (non normalisée)** que l'image appartienne à chaque classe. Ainsi, pour les classes 0 (chien) et 1 (chat), on a:\n",
    "\n",
    "$$\n",
    "P(0\\,|\\,x_i,W,b) = \\frac{e^{-0.04}}{e^{-0.04} + e^{0.12}} = 0.46\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(1\\,|\\,x_i,W,b) = \\frac{e^{0.12}}{e^{-0.04} + e^{0.12}} = 0.54\n",
    "$$\n",
    "\n",
    "La fonction estime donc qu'il est plus probable que l'image soit de classe 1 (chat), puisque la probabilité est de 54% pour cette classe. On remarque également que les probabilités sont maintenant normalisées (ont une somme de 1).\n",
    "\n",
    "La formule générale est la suivant:\n",
    "\n",
    "$$\n",
    "P(y_i\\,|\\,x_i,W,b) = \\frac{e^{f_{y_i} + \\log C}}{\\sum_j e^{f_{y_i} + \\log C}}\n",
    "$$\n",
    "\n",
    "où la constante $\\log C = -\\max_jf_j$ est ajoutée uniquement pour la stabilité numérique.\n",
    "\n",
    "\n",
    "Maintenant qu'on peut mettre une valeur sur la justesse de la prédiction de la classification, on peut facilement calculer le *loss*. Reprenons l'exemple précédent. On sait que l'image est une image de chien, avec une probabilité 1. On sait également que la probabilité que l'image soit un chat est 0. Donc, le vecteur de gradient est $[(1 - 0.46), (0 - 0.54)] = [0.54, -0.46]$. Autrement dit, **on veut que la fonction apprenne à, étant donné cet input, augmenter la probabilité de chien et diminuer la probabilité de chat**, proportionnellement à l'erreur observée. La valeur de *loss* est la norme euclidienne de ce vecteur de gradient.\n",
    "\n",
    "### Exercice\n",
    "Premièrement, préparons les données en suivant les étapes suivantes:\n",
    "1. Mettre tous les pixels de tous les canaux en un grand vecteur. On aura donc une matrice de taille (n_image, 3072)\n",
    "2. Calculer la valeur moyenne de chaque pixel **sur les données d'entraînement uniquement** et centrer les données. En général, on a des meilleurs résultats sur des distributions sans biais.\n",
    "3. Ajouter un élément à la fin de chaque ligne des $x$ pour ne pas avoir à calculer séparemment le biais $b$\n",
    "4. Extraire une petite batch x_dev pour nous aider au développement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x_train = cifar10.x_train\n",
    "x_test = cifar10.x_test\n",
    "y_train = cifar10.y_train\n",
    "y_test = cifar10.y_test\n",
    "\n",
    "# Preprocessing: reshape the image data into rows\n",
    "x_train = np.reshape(x_train, (x_train.shape[0], -1))\n",
    "x_test = np.reshape(x_test, (x_test.shape[0], -1))\n",
    "\n",
    "\n",
    "# Normalize the data: subtract the mean image\n",
    "mean_image = np.mean(x_train, axis=0)\n",
    "x_train -= mean_image\n",
    "x_test -= mean_image\n",
    "\n",
    "# add bias dimension and transform into columns\n",
    "x_train = np.hstack([x_train, np.ones((x_train.shape[0], 1))])\n",
    "x_test = np.hstack([x_test, np.ones((x_test.shape[0], 1))])\n",
    "\n",
    "mask = np.random.choice(x_train.shape[0], 500, replace=False)\n",
    "x_dev = x_train[mask]\n",
    "y_dev = y_train[mask]\n",
    "\n",
    "print(x_train.shape, x_test.shape, x_dev.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans le fichier `dojo/softmax.py`, complétez la fonction `softmax_loss_naive`, puis roulez le code suivant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from dojo.softmax import softmax_loss_naive\n",
    "import time\n",
    "\n",
    "# Generate a random softmax weight matrix and use it to compute the loss.\n",
    "W = np.random.randn(3073, 10) * 0.0001\n",
    "loss, grad = softmax_loss_naive(W, x_dev, y_dev, 0.0)\n",
    "\n",
    "# As a rough sanity check, our loss should be something close to -log(0.1).\n",
    "print('loss: %f' % loss)\n",
    "print('sanity check: %f' % (-np.log(0.1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Est-ce que votre fonction passe le sanity check? **Pourquoi s'attend-t-on à une valeur de $-\\log(0.1)$**?\n",
    "\n",
    "Maintenant, vérifiez que vous retournez le bon gradient en roulant le code suivant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Complete the implementation of softmax_loss_naive and implement a (naive)\n",
    "# version of the gradient that uses nested loops.\n",
    "loss, grad = softmax_loss_naive(W, x_dev, y_dev, 0.0)\n",
    "\n",
    "# As we did for the SVM, use numeric gradient checking as a debugging tool.\n",
    "# The numeric gradient should be close to the analytic gradient.\n",
    "from dojo.gradient_check import grad_check_sparse\n",
    "f = lambda w: softmax_loss_naive(w, x_dev, y_dev, 0.0)[0]\n",
    "grad_numerical = grad_check_sparse(f, W, grad, 10)\n",
    "\n",
    "# similar to SVM case, do another gradient check with regularization\n",
    "loss, grad = softmax_loss_naive(W, x_dev, y_dev, 1e2)\n",
    "f = lambda w: softmax_loss_naive(w, x_dev, y_dev, 1e2)[0]\n",
    "grad_numerical = grad_check_sparse(f, W, grad, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`grad_check_sparse` compare votre valeur de gradient avec un estimé numérique (versus un calcul analytique) calculé par une approche itérative (voir [wiki](https://en.wikipedia.org/wiki/Numerical_differentiation) pour plus de détails). Ce qu'il faut retenir, c'est que l'approximation numérique est trop lente à calculer pour les algos de machine learning mais peuvent nous permettre de vérifier notre travail.\n",
    "\n",
    "Si `relative error` est un petit nombre, c'est gagné.\n",
    "\n",
    "\n",
    "Maintenant, séparer votre ensemble d'entraînement en 2 partie: une parte de 49000 images pour l'entraînement (`x_train`) et une partie de 1000 images pour la validation (`x_val`). Itérez sur "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x_train = x_train[1000:]\n",
    "y_train = y_train[1000:]\n",
    "\n",
    "x_val = x_train[:1000]\n",
    "y_val = y_train[:1000]\n",
    "print(x_train.shape, x_val.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Use the validation set to tune hyperparameters (learning rate). \n",
    "# You should experiment with different ranges for the learning rates.\n",
    "from dojo.linear_classifier import Softmax\n",
    "\n",
    "results = {}\n",
    "best_val = -1\n",
    "best_softmax = None\n",
    "learning_rates = [1e-7, 1e-4] # [min, max]\n",
    "\n",
    "# Change num to change the number of learning_rates to try\n",
    "lrs = np.log10(np.logspace(learning_rates[0], learning_rates[1], num=5, dtype='Float64'))  \n",
    "num_iter = 2000\n",
    "\n",
    "\n",
    "for lr in lrs:\n",
    "    smc = Softmax()\n",
    "    smc.train(x_train, y_train, learning_rate=lr, num_iters=num_iter)\n",
    "    \n",
    "    y_train_pred = smc.predict(x_train)\n",
    "    y_val_pred = smc.predict(x_val)\n",
    "    \n",
    "    ##########################\n",
    "    #TODO\n",
    "    train_accuracy = 0.0\n",
    "    validation_accuracy = 0.0\n",
    "    ##########################\n",
    "    \n",
    "    results[lr] = (train_accuracy, validation_accuracy)\n",
    "    if validation_accuracy > best_val:\n",
    "        best_val = validation_accuracy\n",
    "        best_softmax = smc\n",
    "\n",
    "# Print out results.\n",
    "for lr in sorted(results):\n",
    "    train_accuracy, val_accuracy = results[lr]\n",
    "    print('lr %e train accuracy: %f val accuracy: %f' % (lr, train_accuracy, val_accuracy))\n",
    "    \n",
    "print('best validation accuracy achieved during cross-validation: %f' % best_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# evaluate on test set\n",
    "# Evaluate the best softmax on test set\n",
    "y_test_pred = best_softmax.predict(x_test)\n",
    "\n",
    "##########################\n",
    "#TODO\n",
    "test_accuracy = 0.0\n",
    "##########################\n",
    "\n",
    "print('softmax on raw pixels final test set accuracy: %f' % (test_accuracy, ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Visualisation\n",
    "\n",
    "La cellule suivante visualise les poids obtenus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Visualize the learned weights for each class\n",
    "w = best_softmax.W[:-1,:] # strip out the bias\n",
    "w = w.reshape(32, 32, 3, 10)\n",
    "\n",
    "w_min, w_max = np.min(w), np.max(w)\n",
    "print(w_min, w_max)\n",
    "\n",
    "classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']\n",
    "for i in range(10):\n",
    "    plt.subplot(2, 5, i + 1)\n",
    "\n",
    "    # Rescale the weights to be between 0 and 255\n",
    "    wimg = 255.0 * (w[:, :, :, i].squeeze() - w_min) / (w_max - w_min)\n",
    "    plt.imshow(wimg.astype('uint8'))\n",
    "    plt.axis('off')\n",
    "    plt.title(classes[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partie 4 - Réseaux de neurones\n",
    "\n",
    "Si vous avez bien compris la partie précédente, vous comprenez déjà les réseaux de neurones. Un réseaux de neurones est composé de:\n",
    "\n",
    "1. **Une couche d'input**. Comme pour la classification linéaire, c'est l'image sous forme de vecteur.\n",
    "2. **Couche(s) caché(s)**. Chaque neurone dans les couche cachées sont des classificateur linéaires, suivis de non-linéarités (plus de détails plus loin).\n",
    "3. **Couche de sortie**. Comme pour le classificateur linéaire, il y a une sortie par classe, et on utilise la fonction softmax pour calculer le *loss* et le gradient.\n",
    "\n",
    "![nn](http://cs231n.github.io/assets/nn1/neural_net2.jpeg)\n",
    "![nn-zoom](http://cs231n.github.io/assets/nn1/neuron_model.jpeg)\n",
    "\n",
    "L'idée générale d'un réseau de neurone est de combiner plusieur classificateurs linéaires pour avoir un pouvoir de représentation plus grand.\n",
    "\n",
    "![lin-nn](http://image.slidesharecdn.com/actionrecognition-12661691655651-phpapp01/95/action-recognition-thesis-presentation-29-728.jpg?cb=1266147980)\n",
    "\n",
    "On ajoute également une non linéarité (la fonction $f$ sur la deuxième image), ce qui augmente davantage le pouvoir de représentation du réseau. Trois fonctions d'activations sont populaires: tanh, sigmoid et ReLU (ReLU étant la plus fréquemment utilisée de nos jours).\n",
    "\n",
    "![non-lin](https://imiloainf.files.wordpress.com/2013/11/activation_funcs1.png)\n",
    "\n",
    "### Exercice\n",
    "\n",
    "Utilisez Tensorflow pour battre le précision du classificateur linéaire de la partie précédente. Utilisez les `placeholder` tensorflow puisque c'est la manière la plus simple de procéder pour des petits datasets. Quelques pistes d'explorations:\n",
    "\n",
    "- Jouez avec le nombre de couches et de neurones par couche\n",
    "- Modifiez la l'initialisation des poids W et des biais b\n",
    "- Changez de fonction d'activation (non-linéarité)\n",
    "\n",
    "Quelques liens:\n",
    "- https://www.tensorflow.org/how_tos/reading_data/#preloaded_data\n",
    "- https://www.tensorflow.org/how_tos/threading_and_queues/\n",
    "- http://playground.tensorflow.org/\n",
    "- https://www.tensorflow.org/tutorials/mnist/tf/\n",
    "- https://github.com/tensorflow/tensorflow/blob/master/tensorflow/examples/tutorials/mnist/mnist.py\n",
    "\n",
    "#### Sujets avancés\n",
    "\n",
    "Certains sujets avancés n'ont pas été abordés durant ce dojo pour que la matière reste accessible et entre dans une seule journée. Si vous avez complétés votre réseau avec Tensorflow, vous pouvez explorer ces sujets:\n",
    "\n",
    "- Réseaux de neurones convolutionnels (CNN)\n",
    "- Dropout\n",
    "- Batch-Normalization\n",
    "\n",
    "Bien sûr, n'hésitez pas à demander aux animateurs de l'aide personnalisée et des explications sur ces sujets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}