FullyConnectedNets.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-title"
    ]
   },
   "source": [
    "# Fully-Connected Neural Nets\n",
    "In the previous homework you implemented a fully-connected two-layer neural network on CIFAR-10. The implementation was simple but not very modular since the loss and gradient were computed in a single monolithic function. This is manageable for a simple two-layer network, but would become impractical as we move to bigger models. Ideally we want to build networks using a more modular design so that we can implement different layer types in isolation and then snap them together into models with different architectures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "source": [
    "In this exercise we will implement fully-connected networks using a more modular approach. For each layer we will implement a `forward` and a `backward` function. The `forward` function will receive inputs, weights, and other parameters and will return both an output and a `cache` object storing data needed for the backward pass, like this:\n",
    "\n",
    "```python\n",
    "def layer_forward(x, w):\n",
    "  \"\"\" Receive inputs x and weights w \"\"\"\n",
    "  # Do some computations ...\n",
    "  z = # ... some intermediate value\n",
    "  # Do some more computations ...\n",
    "  out = # the output\n",
    "   \n",
    "  cache = (x, w, z, out) # Values we need to compute gradients\n",
    "   \n",
    "  return out, cache\n",
    "```\n",
    "\n",
    "The backward pass will receive upstream derivatives and the `cache` object, and will return gradients with respect to the inputs and weights, like this:\n",
    "\n",
    "```python\n",
    "def layer_backward(dout, cache):\n",
    "  \"\"\"\n",
    "  Receive dout (derivative of loss with respect to outputs) and cache,\n",
    "  and compute derivative with respect to inputs.\n",
    "  \"\"\"\n",
    "  # Unpack cache values\n",
    "  x, w, z, out = cache\n",
    "  \n",
    "  # Use values in cache to compute derivatives\n",
    "  dx = # Derivative of loss with respect to x\n",
    "  dw = # Derivative of loss with respect to w\n",
    "  \n",
    "  return dx, dw\n",
    "```\n",
    "\n",
    "After implementing a bunch of layers this way, we will be able to easily combine them to build classifiers with different architectures.\n",
    "\n",
    "In addition to implementing fully-connected networks of arbitrary depth, we will also explore different update rules for optimization, and introduce Dropout as a regularizer and Batch/Layer Normalization as a tool to more efficiently optimize deep networks.\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "tags": [
     "pdf-ignore"
    ]
   },
   "outputs": [],
   "source": [
    "# As usual, a bit of setup\n",
    "from __future__ import print_function\n",
    "import time\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from cs231n.classifiers.fc_net import *\n",
    "from cs231n.data_utils import get_CIFAR10_data\n",
    "from cs231n.gradient_check import eval_numerical_gradient, eval_numerical_gradient_array\n",
    "from cs231n.solver import Solver\n",
    "\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",
    "# for auto-reloading external modules\n",
    "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "def rel_error(x, y):\n",
    "  \"\"\" returns relative error \"\"\"\n",
    "  return np.max(np.abs(x - y) / (np.maximum(1e-8, np.abs(x) + np.abs(y))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('X_train: ', (49000, 3, 32, 32))\n",
      "('y_train: ', (49000,))\n",
      "('X_val: ', (1000, 3, 32, 32))\n",
      "('y_val: ', (1000,))\n",
      "('X_test: ', (1000, 3, 32, 32))\n",
      "('y_test: ', (1000,))\n"
     ]
    }
   ],
   "source": [
    "# Load the (preprocessed) CIFAR10 data.\n",
    "\n",
    "data = get_CIFAR10_data()\n",
    "for k, v in list(data.items()):\n",
    "  print(('%s: ' % k, v.shape))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Affine layer: foward\n",
    "Open the file `cs231n/layers.py` and implement the `affine_forward` function.\n",
    "\n",
    "Once you are done you can test your implementaion by running the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing affine_forward function:\n",
      "difference:  9.769849468192957e-10\n"
     ]
    }
   ],
   "source": [
    "# Test the affine_forward function\n",
    "\n",
    "num_inputs = 2\n",
    "input_shape = (4, 5, 6)\n",
    "output_dim = 3\n",
    "\n",
    "input_size = num_inputs * np.prod(input_shape)\n",
    "weight_size = output_dim * np.prod(input_shape)\n",
    "\n",
    "x = np.linspace(-0.1, 0.5, num=input_size).reshape(num_inputs, *input_shape)\n",
    "w = np.linspace(-0.2, 0.3, num=weight_size).reshape(np.prod(input_shape), output_dim)\n",
    "b = np.linspace(-0.3, 0.1, num=output_dim)\n",
    "\n",
    "out, _ = affine_forward(x, w, b)\n",
    "correct_out = np.array([[ 1.49834967,  1.70660132,  1.91485297],\n",
    "                        [ 3.25553199,  3.5141327,   3.77273342]])\n",
    "\n",
    "# Compare your output with ours. The error should be around e-9 or less.\n",
    "print('Testing affine_forward function:')\n",
    "print('difference: ', rel_error(out, correct_out))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Affine layer: backward\n",
    "Now implement the `affine_backward` function and test your implementation using numeric gradient checking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing affine_backward function:\n",
      "dx error:  5.399100368651805e-11\n",
      "dw error:  9.904211865398145e-11\n",
      "db error:  2.4122867568119087e-11\n"
     ]
    }
   ],
   "source": [
    "# Test the affine_backward function\n",
    "np.random.seed(231)\n",
    "x = np.random.randn(10, 2, 3)\n",
    "w = np.random.randn(6, 5)\n",
    "b = np.random.randn(5)\n",
    "dout = np.random.randn(10, 5)\n",
    "\n",
    "dx_num = eval_numerical_gradient_array(lambda x: affine_forward(x, w, b)[0], x, dout)\n",
    "dw_num = eval_numerical_gradient_array(lambda w: affine_forward(x, w, b)[0], w, dout)\n",
    "db_num = eval_numerical_gradient_array(lambda b: affine_forward(x, w, b)[0], b, dout)\n",
    "\n",
    "_, cache = affine_forward(x, w, b)\n",
    "dx, dw, db = affine_backward(dout, cache)\n",
    "\n",
    "# The error should be around e-10 or less\n",
    "print('Testing affine_backward function:')\n",
    "print('dx error: ', rel_error(dx_num, dx))\n",
    "print('dw error: ', rel_error(dw_num, dw))\n",
    "print('db error: ', rel_error(db_num, db))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ReLU activation: forward\n",
    "Implement the forward pass for the ReLU activation function in the `relu_forward` function and test your implementation using the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing relu_forward function:\n",
      "difference:  4.999999798022158e-08\n"
     ]
    }
   ],
   "source": [
    "# Test the relu_forward function\n",
    "\n",
    "x = np.linspace(-0.5, 0.5, num=12).reshape(3, 4)\n",
    "\n",
    "out, _ = relu_forward(x)\n",
    "correct_out = np.array([[ 0.,          0.,          0.,          0.,        ],\n",
    "                        [ 0.,          0.,          0.04545455,  0.13636364,],\n",
    "                        [ 0.22727273,  0.31818182,  0.40909091,  0.5,       ]])\n",
    "\n",
    "# Compare your output with ours. The error should be on the order of e-8\n",
    "print('Testing relu_forward function:')\n",
    "print('difference: ', rel_error(out, correct_out))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ReLU activation: backward\n",
    "Now implement the backward pass for the ReLU activation function in the `relu_backward` function and test your implementation using numeric gradient checking:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing relu_backward function:\n",
      "dx error:  3.2756349136310288e-12\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(231)\n",
    "x = np.random.randn(10, 10)\n",
    "dout = np.random.randn(*x.shape)\n",
    "\n",
    "dx_num = eval_numerical_gradient_array(lambda x: relu_forward(x)[0], x, dout)\n",
    "\n",
    "_, cache = relu_forward(x)\n",
    "dx = relu_backward(dout, cache)\n",
    "\n",
    "# The error should be on the order of e-12\n",
    "print('Testing relu_backward function:')\n",
    "print('dx error: ', rel_error(dx_num, dx))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-inline"
    ]
   },
   "source": [
    "## Inline Question 1: \n",
    "\n",
    "We've only asked you to implement ReLU, but there are a number of different activation functions that one could use in neural networks, each with its pros and cons. In particular, an issue commonly seen with activation functions is getting zero (or close to zero) gradient flow during backpropagation. Which of the following activation functions have this problem? If you consider these functions in the one dimensional case, what types of input would lead to this behaviour?\n",
    "1. Sigmoid\n",
    "2. ReLU\n",
    "3. Leaky ReLU\n",
    "\n",
    "## Answer:\n",
    "[FILL THIS IN]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# \"Sandwich\" layers\n",
    "There are some common patterns of layers that are frequently used in neural nets. For example, affine layers are frequently followed by a ReLU nonlinearity. To make these common patterns easy, we define several convenience layers in the file `cs231n/layer_utils.py`.\n",
    "\n",
    "For now take a look at the `affine_relu_forward` and `affine_relu_backward` functions, and run the following to numerically gradient check the backward pass:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from cs231n.layer_utils import affine_relu_forward, affine_relu_backward\n",
    "np.random.seed(231)\n",
    "x = np.random.randn(2, 3, 4)\n",
    "w = np.random.randn(12, 10)\n",
    "b = np.random.randn(10)\n",
    "dout = np.random.randn(2, 10)\n",
    "\n",
    "out, cache = affine_relu_forward(x, w, b)\n",
    "dx, dw, db = affine_relu_backward(dout, cache)\n",
    "\n",
    "dx_num = eval_numerical_gradient_array(lambda x: affine_relu_forward(x, w, b)[0], x, dout)\n",
    "dw_num = eval_numerical_gradient_array(lambda w: affine_relu_forward(x, w, b)[0], w, dout)\n",
    "db_num = eval_numerical_gradient_array(lambda b: affine_relu_forward(x, w, b)[0], b, dout)\n",
    "\n",
    "# Relative error should be around e-10 or less\n",
    "print('Testing affine_relu_forward and affine_relu_backward:')\n",
    "print('dx error: ', rel_error(dx_num, dx))\n",
    "print('dw error: ', rel_error(dw_num, dw))\n",
    "print('db error: ', rel_error(db_num, db))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Loss layers: Softmax and SVM\n",
    "You implemented these loss functions in the last assignment, so we'll give them to you for free here. You should still make sure you understand how they work by looking at the implementations in `cs231n/layers.py`.\n",
    "\n",
    "You can make sure that the implementations are correct by running the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "np.random.seed(231)\n",
    "num_classes, num_inputs = 10, 50\n",
    "x = 0.001 * np.random.randn(num_inputs, num_classes)\n",
    "y = np.random.randint(num_classes, size=num_inputs)\n",
    "\n",
    "dx_num = eval_numerical_gradient(lambda x: svm_loss(x, y)[0], x, verbose=False)\n",
    "loss, dx = svm_loss(x, y)\n",
    "\n",
    "# Test svm_loss function. Loss should be around 9 and dx error should be around the order of e-9\n",
    "print('Testing svm_loss:')\n",
    "print('loss: ', loss)\n",
    "print('dx error: ', rel_error(dx_num, dx))\n",
    "\n",
    "dx_num = eval_numerical_gradient(lambda x: softmax_loss(x, y)[0], x, verbose=False)\n",
    "loss, dx = softmax_loss(x, y)\n",
    "\n",
    "# Test softmax_loss function. Loss should be close to 2.3 and dx error should be around e-8\n",
    "print('\\nTesting softmax_loss:')\n",
    "print('loss: ', loss)\n",
    "print('dx error: ', rel_error(dx_num, dx))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Two-layer network\n",
    "In the previous assignment you implemented a two-layer neural network in a single monolithic class. Now that you have implemented modular versions of the necessary layers, you will reimplement the two layer network using these modular implementations.\n",
    "\n",
    "Open the file `cs231n/classifiers/fc_net.py` and complete the implementation of the `TwoLayerNet` class. This class will serve as a model for the other networks you will implement in this assignment, so read through it to make sure you understand the API. You can run the cell below to test your implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "np.random.seed(231)\n",
    "N, D, H, C = 3, 5, 50, 7\n",
    "X = np.random.randn(N, D)\n",
    "y = np.random.randint(C, size=N)\n",
    "\n",
    "std = 1e-3\n",
    "model = TwoLayerNet(input_dim=D, hidden_dim=H, num_classes=C, weight_scale=std)\n",
    "\n",
    "print('Testing initialization ... ')\n",
    "W1_std = abs(model.params['W1'].std() - std)\n",
    "b1 = model.params['b1']\n",
    "W2_std = abs(model.params['W2'].std() - std)\n",
    "b2 = model.params['b2']\n",
    "assert W1_std < std / 10, 'First layer weights do not seem right'\n",
    "assert np.all(b1 == 0), 'First layer biases do not seem right'\n",
    "assert W2_std < std / 10, 'Second layer weights do not seem right'\n",
    "assert np.all(b2 == 0), 'Second layer biases do not seem right'\n",
    "\n",
    "print('Testing test-time forward pass ... ')\n",
    "model.params['W1'] = np.linspace(-0.7, 0.3, num=D*H).reshape(D, H)\n",
    "model.params['b1'] = np.linspace(-0.1, 0.9, num=H)\n",
    "model.params['W2'] = np.linspace(-0.3, 0.4, num=H*C).reshape(H, C)\n",
    "model.params['b2'] = np.linspace(-0.9, 0.1, num=C)\n",
    "X = np.linspace(-5.5, 4.5, num=N*D).reshape(D, N).T\n",
    "scores = model.loss(X)\n",
    "correct_scores = np.asarray(\n",
    "  [[11.53165108,  12.2917344,   13.05181771,  13.81190102,  14.57198434, 15.33206765,  16.09215096],\n",
    "   [12.05769098,  12.74614105,  13.43459113,  14.1230412,   14.81149128, 15.49994135,  16.18839143],\n",
    "   [12.58373087,  13.20054771,  13.81736455,  14.43418138,  15.05099822, 15.66781506,  16.2846319 ]])\n",
    "scores_diff = np.abs(scores - correct_scores).sum()\n",
    "assert scores_diff < 1e-6, 'Problem with test-time forward pass'\n",
    "\n",
    "print('Testing training loss (no regularization)')\n",
    "y = np.asarray([0, 5, 1])\n",
    "loss, grads = model.loss(X, y)\n",
    "correct_loss = 3.4702243556\n",
    "assert abs(loss - correct_loss) < 1e-10, 'Problem with training-time loss'\n",
    "\n",
    "model.reg = 1.0\n",
    "loss, grads = model.loss(X, y)\n",
    "correct_loss = 26.5948426952\n",
    "assert abs(loss - correct_loss) < 1e-10, 'Problem with regularization loss'\n",
    "\n",
    "# Errors should be around e-7 or less\n",
    "for reg in [0.0, 0.7]:\n",
    "  print('Running numeric gradient check with reg = ', reg)\n",
    "  model.reg = reg\n",
    "  loss, grads = model.loss(X, y)\n",
    "\n",
    "  for name in sorted(grads):\n",
    "    f = lambda _: model.loss(X, y)[0]\n",
    "    grad_num = eval_numerical_gradient(f, model.params[name], verbose=False)\n",
    "    print('%s relative error: %.2e' % (name, rel_error(grad_num, grads[name])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solver\n",
    "In the previous assignment, the logic for training models was coupled to the models themselves. Following a more modular design, for this assignment we have split the logic for training models into a separate class.\n",
    "\n",
    "Open the file `cs231n/solver.py` and read through it to familiarize yourself with the API. After doing so, use a `Solver` instance to train a `TwoLayerNet` that achieves at least `50%` accuracy on the validation set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model = TwoLayerNet()\n",
    "solver = None\n",
    "\n",
    "##############################################################################\n",
    "# TODO: Use a Solver instance to train a TwoLayerNet that achieves at least  #\n",
    "# 50% accuracy on the validation set.                                        #\n",
    "##############################################################################\n",
    "# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
    "\n",
    "pass\n",
    "\n",
    "# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
    "##############################################################################\n",
    "#                             END OF YOUR CODE                               #\n",
    "##############################################################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Run this cell to visualize training loss and train / val accuracy\n",
    "\n",
    "plt.subplot(2, 1, 1)\n",
    "plt.title('Training loss')\n",
    "plt.plot(solver.loss_history, 'o')\n",
    "plt.xlabel('Iteration')\n",
    "\n",
    "plt.subplot(2, 1, 2)\n",
    "plt.title('Accuracy')\n",
    "plt.plot(solver.train_acc_history, '-o', label='train')\n",
    "plt.plot(solver.val_acc_history, '-o', label='val')\n",
    "plt.plot([0.5] * len(solver.val_acc_history), 'k--')\n",
    "plt.xlabel('Epoch')\n",
    "plt.legend(loc='lower right')\n",
    "plt.gcf().set_size_inches(15, 12)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multilayer network\n",
    "Next you will implement a fully-connected network with an arbitrary number of hidden layers.\n",
    "\n",
    "Read through the `FullyConnectedNet` class in the file `cs231n/classifiers/fc_net.py`.\n",
    "\n",
    "Implement the initialization, the forward pass, and the backward pass. For the moment don't worry about implementing dropout or batch/layer normalization; we will add those features soon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initial loss and gradient check\n",
    "\n",
    "As a sanity check, run the following to check the initial loss and to gradient check the network both with and without regularization. Do the initial losses seem reasonable?\n",
    "\n",
    "For gradient checking, you should expect to see errors around 1e-7 or less."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "np.random.seed(231)\n",
    "N, D, H1, H2, C = 2, 15, 20, 30, 10\n",
    "X = np.random.randn(N, D)\n",
    "y = np.random.randint(C, size=(N,))\n",
    "\n",
    "for reg in [0, 3.14]:\n",
    "  print('Running check with reg = ', reg)\n",
    "  model = FullyConnectedNet([H1, H2], input_dim=D, num_classes=C,\n",
    "                            reg=reg, weight_scale=5e-2, dtype=np.float64)\n",
    "\n",
    "  loss, grads = model.loss(X, y)\n",
    "  print('Initial loss: ', loss)\n",
    "  \n",
    "  # Most of the errors should be on the order of e-7 or smaller.   \n",
    "  # NOTE: It is fine however to see an error for W2 on the order of e-5\n",
    "  # for the check when reg = 0.0\n",
    "  for name in sorted(grads):\n",
    "    f = lambda _: model.loss(X, y)[0]\n",
    "    grad_num = eval_numerical_gradient(f, model.params[name], verbose=False, h=1e-5)\n",
    "    print('%s relative error: %.2e' % (name, rel_error(grad_num, grads[name])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As another sanity check, make sure you can overfit a small dataset of 50 images. First we will try a three-layer network with 100 units in each hidden layer. In the following cell, tweak the **learning rate** and **weight initialization scale** to overfit and achieve 100% training accuracy within 20 epochs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# TODO: Use a three-layer Net to overfit 50 training examples by \n",
    "# tweaking just the learning rate and initialization scale.\n",
    "\n",
    "num_train = 50\n",
    "small_data = {\n",
    "  'X_train': data['X_train'][:num_train],\n",
    "  'y_train': data['y_train'][:num_train],\n",
    "  'X_val': data['X_val'],\n",
    "  'y_val': data['y_val'],\n",
    "}\n",
    "\n",
    "weight_scale = 1e-2   # Experiment with this!\n",
    "learning_rate = 1e-4  # Experiment with this!\n",
    "model = FullyConnectedNet([100, 100],\n",
    "              weight_scale=weight_scale, dtype=np.float64)\n",
    "solver = Solver(model, small_data,\n",
    "                print_every=10, num_epochs=20, batch_size=25,\n",
    "                update_rule='sgd',\n",
    "                optim_config={\n",
    "                  'learning_rate': learning_rate,\n",
    "                }\n",
    "         )\n",
    "solver.train()\n",
    "\n",
    "plt.plot(solver.loss_history, 'o')\n",
    "plt.title('Training loss history')\n",
    "plt.xlabel('Iteration')\n",
    "plt.ylabel('Training loss')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now try to use a five-layer network with 100 units on each layer to overfit 50 training examples. Again, you will have to adjust the learning rate and weight initialization scale, but you should be able to achieve 100% training accuracy within 20 epochs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: Use a five-layer Net to overfit 50 training examples by \n",
    "# tweaking just the learning rate and initialization scale.\n",
    "\n",
    "num_train = 50\n",
    "small_data = {\n",
    "  'X_train': data['X_train'][:num_train],\n",
    "  'y_train': data['y_train'][:num_train],\n",
    "  'X_val': data['X_val'],\n",
    "  'y_val': data['y_val'],\n",
    "}\n",
    "\n",
    "learning_rate = 2e-3  # Experiment with this!\n",
    "weight_scale = 1e-5   # Experiment with this!\n",
    "model = FullyConnectedNet([100, 100, 100, 100],\n",
    "                weight_scale=weight_scale, dtype=np.float64)\n",
    "solver = Solver(model, small_data,\n",
    "                print_every=10, num_epochs=20, batch_size=25,\n",
    "                update_rule='sgd',\n",
    "                optim_config={\n",
    "                  'learning_rate': learning_rate,\n",
    "                }\n",
    "         )\n",
    "solver.train()\n",
    "\n",
    "plt.plot(solver.loss_history, 'o')\n",
    "plt.title('Training loss history')\n",
    "plt.xlabel('Iteration')\n",
    "plt.ylabel('Training loss')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-inline"
    ]
   },
   "source": [
    "## Inline Question 2: \n",
    "Did you notice anything about the comparative difficulty of training the three-layer net vs training the five layer net? In particular, based on your experience, which network seemed more sensitive to the initialization scale? Why do you think that is the case?\n",
    "\n",
    "## Answer:\n",
    "[FILL THIS IN]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Update rules\n",
    "So far we have used vanilla stochastic gradient descent (SGD) as our update rule. More sophisticated update rules can make it easier to train deep networks. We will implement a few of the most commonly used update rules and compare them to vanilla SGD."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SGD+Momentum\n",
    "Stochastic gradient descent with momentum is a widely used update rule that tends to make deep networks converge faster than vanilla stochastic gradient descent. See the Momentum Update section at http://cs231n.github.io/neural-networks-3/#sgd for more information.\n",
    "\n",
    "Open the file `cs231n/optim.py` and read the documentation at the top of the file to make sure you understand the API. Implement the SGD+momentum update rule in the function `sgd_momentum` and run the following to check your implementation. You should see errors less than e-8."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from cs231n.optim import sgd_momentum\n",
    "\n",
    "N, D = 4, 5\n",
    "w = np.linspace(-0.4, 0.6, num=N*D).reshape(N, D)\n",
    "dw = np.linspace(-0.6, 0.4, num=N*D).reshape(N, D)\n",
    "v = np.linspace(0.6, 0.9, num=N*D).reshape(N, D)\n",
    "\n",
    "config = {'learning_rate': 1e-3, 'velocity': v}\n",
    "next_w, _ = sgd_momentum(w, dw, config=config)\n",
    "\n",
    "expected_next_w = np.asarray([\n",
    "  [ 0.1406,      0.20738947,  0.27417895,  0.34096842,  0.40775789],\n",
    "  [ 0.47454737,  0.54133684,  0.60812632,  0.67491579,  0.74170526],\n",
    "  [ 0.80849474,  0.87528421,  0.94207368,  1.00886316,  1.07565263],\n",
    "  [ 1.14244211,  1.20923158,  1.27602105,  1.34281053,  1.4096    ]])\n",
    "expected_velocity = np.asarray([\n",
    "  [ 0.5406,      0.55475789,  0.56891579, 0.58307368,  0.59723158],\n",
    "  [ 0.61138947,  0.62554737,  0.63970526,  0.65386316,  0.66802105],\n",
    "  [ 0.68217895,  0.69633684,  0.71049474,  0.72465263,  0.73881053],\n",
    "  [ 0.75296842,  0.76712632,  0.78128421,  0.79544211,  0.8096    ]])\n",
    "\n",
    "# Should see relative errors around e-8 or less\n",
    "print('next_w error: ', rel_error(next_w, expected_next_w))\n",
    "print('velocity error: ', rel_error(expected_velocity, config['velocity']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have done so, run the following to train a six-layer network with both SGD and SGD+momentum. You should see the SGD+momentum update rule converge faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "num_train = 4000\n",
    "small_data = {\n",
    "  'X_train': data['X_train'][:num_train],\n",
    "  'y_train': data['y_train'][:num_train],\n",
    "  'X_val': data['X_val'],\n",
    "  'y_val': data['y_val'],\n",
    "}\n",
    "\n",
    "solvers = {}\n",
    "\n",
    "for update_rule in ['sgd', 'sgd_momentum']:\n",
    "  print('running with ', update_rule)\n",
    "  model = FullyConnectedNet([100, 100, 100, 100, 100], weight_scale=5e-2)\n",
    "\n",
    "  solver = Solver(model, small_data,\n",
    "                  num_epochs=5, batch_size=100,\n",
    "                  update_rule=update_rule,\n",
    "                  optim_config={\n",
    "                    'learning_rate': 5e-3,\n",
    "                  },\n",
    "                  verbose=True)\n",
    "  solvers[update_rule] = solver\n",
    "  solver.train()\n",
    "  print()\n",
    "\n",
    "plt.subplot(3, 1, 1)\n",
    "plt.title('Training loss')\n",
    "plt.xlabel('Iteration')\n",
    "\n",
    "plt.subplot(3, 1, 2)\n",
    "plt.title('Training accuracy')\n",
    "plt.xlabel('Epoch')\n",
    "\n",
    "plt.subplot(3, 1, 3)\n",
    "plt.title('Validation accuracy')\n",
    "plt.xlabel('Epoch')\n",
    "\n",
    "for update_rule, solver in solvers.items():\n",
    "  plt.subplot(3, 1, 1)\n",
    "  plt.plot(solver.loss_history, 'o', label=\"loss_%s\" % update_rule)\n",
    "  \n",
    "  plt.subplot(3, 1, 2)\n",
    "  plt.plot(solver.train_acc_history, '-o', label=\"train_acc_%s\" % update_rule)\n",
    "\n",
    "  plt.subplot(3, 1, 3)\n",
    "  plt.plot(solver.val_acc_history, '-o', label=\"val_acc_%s\" % update_rule)\n",
    "  \n",
    "for i in [1, 2, 3]:\n",
    "  plt.subplot(3, 1, i)\n",
    "  plt.legend(loc='upper center', ncol=4)\n",
    "plt.gcf().set_size_inches(15, 15)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RMSProp and Adam\n",
    "RMSProp [1] and Adam [2] are update rules that set per-parameter learning rates by using a running average of the second moments of gradients.\n",
    "\n",
    "In the file `cs231n/optim.py`, implement the RMSProp update rule in the `rmsprop` function and implement the Adam update rule in the `adam` function, and check your implementations using the tests below.\n",
    "\n",
    "**NOTE:** Please implement the _complete_ Adam update rule (with the bias correction mechanism), not the first simplified version mentioned in the course notes. \n",
    "\n",
    "[1] Tijmen Tieleman and Geoffrey Hinton. \"Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude.\" COURSERA: Neural Networks for Machine Learning 4 (2012).\n",
    "\n",
    "[2] Diederik Kingma and Jimmy Ba, \"Adam: A Method for Stochastic Optimization\", ICLR 2015."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Test RMSProp implementation\n",
    "from cs231n.optim import rmsprop\n",
    "\n",
    "N, D = 4, 5\n",
    "w = np.linspace(-0.4, 0.6, num=N*D).reshape(N, D)\n",
    "dw = np.linspace(-0.6, 0.4, num=N*D).reshape(N, D)\n",
    "cache = np.linspace(0.6, 0.9, num=N*D).reshape(N, D)\n",
    "\n",
    "config = {'learning_rate': 1e-2, 'cache': cache}\n",
    "next_w, _ = rmsprop(w, dw, config=config)\n",
    "\n",
    "expected_next_w = np.asarray([\n",
    "  [-0.39223849, -0.34037513, -0.28849239, -0.23659121, -0.18467247],\n",
    "  [-0.132737,   -0.08078555, -0.02881884,  0.02316247,  0.07515774],\n",
    "  [ 0.12716641,  0.17918792,  0.23122175,  0.28326742,  0.33532447],\n",
    "  [ 0.38739248,  0.43947102,  0.49155973,  0.54365823,  0.59576619]])\n",
    "expected_cache = np.asarray([\n",
    "  [ 0.5976,      0.6126277,   0.6277108,   0.64284931,  0.65804321],\n",
    "  [ 0.67329252,  0.68859723,  0.70395734,  0.71937285,  0.73484377],\n",
    "  [ 0.75037008,  0.7659518,   0.78158892,  0.79728144,  0.81302936],\n",
    "  [ 0.82883269,  0.84469141,  0.86060554,  0.87657507,  0.8926    ]])\n",
    "\n",
    "# You should see relative errors around e-7 or less\n",
    "print('next_w error: ', rel_error(expected_next_w, next_w))\n",
    "print('cache error: ', rel_error(expected_cache, config['cache']))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Test Adam implementation\n",
    "from cs231n.optim import adam\n",
    "\n",
    "N, D = 4, 5\n",
    "w = np.linspace(-0.4, 0.6, num=N*D).reshape(N, D)\n",
    "dw = np.linspace(-0.6, 0.4, num=N*D).reshape(N, D)\n",
    "m = np.linspace(0.6, 0.9, num=N*D).reshape(N, D)\n",
    "v = np.linspace(0.7, 0.5, num=N*D).reshape(N, D)\n",
    "\n",
    "config = {'learning_rate': 1e-2, 'm': m, 'v': v, 't': 5}\n",
    "next_w, _ = adam(w, dw, config=config)\n",
    "\n",
    "expected_next_w = np.asarray([\n",
    "  [-0.40094747, -0.34836187, -0.29577703, -0.24319299, -0.19060977],\n",
    "  [-0.1380274,  -0.08544591, -0.03286534,  0.01971428,  0.0722929],\n",
    "  [ 0.1248705,   0.17744702,  0.23002243,  0.28259667,  0.33516969],\n",
    "  [ 0.38774145,  0.44031188,  0.49288093,  0.54544852,  0.59801459]])\n",
    "expected_v = np.asarray([\n",
    "  [ 0.69966,     0.68908382,  0.67851319,  0.66794809,  0.65738853,],\n",
    "  [ 0.64683452,  0.63628604,  0.6257431,   0.61520571,  0.60467385,],\n",
    "  [ 0.59414753,  0.58362676,  0.57311152,  0.56260183,  0.55209767,],\n",
    "  [ 0.54159906,  0.53110598,  0.52061845,  0.51013645,  0.49966,   ]])\n",
    "expected_m = np.asarray([\n",
    "  [ 0.48,        0.49947368,  0.51894737,  0.53842105,  0.55789474],\n",
    "  [ 0.57736842,  0.59684211,  0.61631579,  0.63578947,  0.65526316],\n",
    "  [ 0.67473684,  0.69421053,  0.71368421,  0.73315789,  0.75263158],\n",
    "  [ 0.77210526,  0.79157895,  0.81105263,  0.83052632,  0.85      ]])\n",
    "\n",
    "# You should see relative errors around e-7 or less\n",
    "print('next_w error: ', rel_error(expected_next_w, next_w))\n",
    "print('v error: ', rel_error(expected_v, config['v']))\n",
    "print('m error: ', rel_error(expected_m, config['m']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have debugged your RMSProp and Adam implementations, run the following to train a pair of deep networks using these new update rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "learning_rates = {'rmsprop': 1e-4, 'adam': 1e-3}\n",
    "for update_rule in ['adam', 'rmsprop']:\n",
    "  print('running with ', update_rule)\n",
    "  model = FullyConnectedNet([100, 100, 100, 100, 100], weight_scale=5e-2)\n",
    "\n",
    "  solver = Solver(model, small_data,\n",
    "                  num_epochs=5, batch_size=100,\n",
    "                  update_rule=update_rule,\n",
    "                  optim_config={\n",
    "                    'learning_rate': learning_rates[update_rule]\n",
    "                  },\n",
    "                  verbose=True)\n",
    "  solvers[update_rule] = solver\n",
    "  solver.train()\n",
    "  print()\n",
    "\n",
    "plt.subplot(3, 1, 1)\n",
    "plt.title('Training loss')\n",
    "plt.xlabel('Iteration')\n",
    "\n",
    "plt.subplot(3, 1, 2)\n",
    "plt.title('Training accuracy')\n",
    "plt.xlabel('Epoch')\n",
    "\n",
    "plt.subplot(3, 1, 3)\n",
    "plt.title('Validation accuracy')\n",
    "plt.xlabel('Epoch')\n",
    "\n",
    "for update_rule, solver in list(solvers.items()):\n",
    "  plt.subplot(3, 1, 1)\n",
    "  plt.plot(solver.loss_history, 'o', label=update_rule)\n",
    "  \n",
    "  plt.subplot(3, 1, 2)\n",
    "  plt.plot(solver.train_acc_history, '-o', label=update_rule)\n",
    "\n",
    "  plt.subplot(3, 1, 3)\n",
    "  plt.plot(solver.val_acc_history, '-o', label=update_rule)\n",
    "  \n",
    "for i in [1, 2, 3]:\n",
    "  plt.subplot(3, 1, i)\n",
    "  plt.legend(loc='upper center', ncol=4)\n",
    "plt.gcf().set_size_inches(15, 15)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-inline"
    ]
   },
   "source": [
    "## Inline Question 3:\n",
    "\n",
    "AdaGrad, like Adam, is a per-parameter optimization method that uses the following update rule:\n",
    "\n",
    "```\n",
    "cache += dw**2\n",
    "w += - learning_rate * dw / (np.sqrt(cache) + eps)\n",
    "```\n",
    "\n",
    "John notices that when he was training a network with AdaGrad that the updates became very small, and that his network was learning slowly. Using your knowledge of the AdaGrad update rule, why do you think the updates would become very small? Would Adam have the same issue?\n",
    "\n",
    "\n",
    "## Answer: \n",
    "[FILL THIS IN]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Train a good model!\n",
    "Train the best fully-connected model that you can on CIFAR-10, storing your best model in the `best_model` variable. We require you to get at least 50% accuracy on the validation set using a fully-connected net.\n",
    "\n",
    "If you are careful it should be possible to get accuracies above 55%, but we don't require it for this part and won't assign extra credit for doing so. Later in the assignment we will ask you to train the best convolutional network that you can on CIFAR-10, and we would prefer that you spend your effort working on convolutional nets rather than fully-connected nets.\n",
    "\n",
    "You might find it useful to complete the `BatchNormalization.ipynb` and `Dropout.ipynb` notebooks before completing this part, since those techniques can help you train powerful models."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "best_model = None\n",
    "################################################################################\n",
    "# TODO: Train the best FullyConnectedNet that you can on CIFAR-10. You might   #\n",
    "# find batch/layer normalization and dropout useful. Store your best model in  #\n",
    "# the best_model variable.                                                     #\n",
    "################################################################################\n",
    "# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
    "\n",
    "pass\n",
    "\n",
    "# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
    "################################################################################\n",
    "#                              END OF YOUR CODE                                #\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test your model!\n",
    "Run your best model on the validation and test sets. You should achieve above 50% accuracy on the validation set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y_test_pred = np.argmax(best_model.loss(data['X_test']), axis=1)\n",
    "y_val_pred = np.argmax(best_model.loss(data['X_val']), axis=1)\n",
    "print('Validation set accuracy: ', (y_val_pred == data['y_val']).mean())\n",
    "print('Test set accuracy: ', (y_test_pred == data['y_test']).mean())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}