P02-C05-regularization-scratch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overfitting and regularization\n",
    "\n",
    "In [the last tutorial](./P02-C03-softmax-regression-scratch.ipynb), we introduced the task of multiclass classification. We showed how you can tackly this problem with a linear model called logistic regression. Owing to some amount of randomness, you might get slightly different results, but when I ran the notebook, the model achieved 88.1% accuracy on the training data and actually did slightly (but not significantly) better on the test data than on the data the model has actually seen. \n",
    " \n",
    "Not every algorithm that performs well on training data will also perform test data. Take, for example, a trivial algorithm that memorizes its inputs and stores the associated labels. This model would have 100% accuracy on training data but would have no way of making any prediction at all on previously unseen data. \n",
    "\n",
    "The goal of machine learning is to produce models that *generalize* to previously unseen data. When a model achieves low error on training data but not test data, we sau that the model has *overfit*. This means that the model has caught on to idiosyncratic features of the training data (e.g. one \"2\" happened to have a white pixel in top-right corner), but hasn't really picked up on general patterns. \n",
    "\n",
    "Lots of factors govern whether a model will generalize well. And there's actually a large body of mathematical analysis that guarantees the generalization error for simple classes of models. *We won't get into this theory but may delve deeper in a future chapter*.\n",
    "\n",
    "On an intuitive level, a few factors tend to influence the generalizability of a model class:\n",
    "1. **The number of degrees of freedom.** When the number of tunable parameters is large, models tend to be more susceptible to overfitting.\n",
    "2. **The number of training examples.** It's trivially easy to overfit a dataset containing only one or two examples even if your model is simple. But overfitting a dataset with millions of examples requires an extremely flexible model.\n",
    "\n",
    "When classified handwritten digits before, we didn't overfit because our 60,000 training examples far out numbered the  $784 \\times 10 = 7,840$ weights plus $10$ bias terms gave us far fewer parameters than training examples. To  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "import mxnet as mx\n",
    "from mxnet import nd, autograd\n",
    "import numpy as np\n",
    "ctx = mx.cpu()\n",
    "mx.random.seed(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load the MNIST dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "mnist = mx.test_utils.get_mnist()\n",
    "num_examples = 1000\n",
    "batch_size = 64\n",
    "train_data = mx.io.NDArrayIter(\n",
    "    mnist[\"train_data\"][:num_examples], \n",
    "    mnist[\"train_label\"][:num_examples], \n",
    "    batch_size, shuffle=True)\n",
    "test_data = mx.io.NDArrayIter(\n",
    "    mnist[\"test_data\"][:num_examples], \n",
    "    mnist[\"test_label\"][:num_examples], \n",
    "    batch_size, shuffle=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Allocate model parameters and define model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "W = nd.random_normal(shape=(784,10))\n",
    "b = nd.random_normal(shape=10)\n",
    "\n",
    "params = [W, b]\n",
    "\n",
    "for param in params:\n",
    "    param.attach_grad()\n",
    "    \n",
    "def net(X):\n",
    "    y_linear = nd.dot(X, W) + b\n",
    "    yhat = nd.softmax(y_linear, axis=1)\n",
    "    return yhat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define loss function and optimizer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cross_entropy(yhat, y):\n",
    "    return - nd.sum(y * nd.log(yhat), axis=0, exclude=True)\n",
    "\n",
    "def SGD(params, lr):    \n",
    "    for param in params:\n",
    "        param[:] = param - lr * param.grad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Write evaluation loop to calculate accuracy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def evaluate_accuracy(data_iterator, net):\n",
    "    numerator = 0.\n",
    "    denominator = 0.\n",
    "    data_iterator.reset()\n",
    "    for i, batch in enumerate(data_iterator):\n",
    "        data = batch.data[0].as_in_context(ctx).reshape((-1,784))\n",
    "        label = batch.label[0].as_in_context(ctx)\n",
    "        label_one_hot = nd.one_hot(label, 10)\n",
    "        output = net(data)\n",
    "        predictions = nd.argmax(output, axis=1)\n",
    "        numerator += nd.sum(predictions == label)\n",
    "        denominator += data.shape[0]\n",
    "    return (numerator / denominator).asscalar()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Execute training loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Completed epoch 100. Loss: 0.699882578467, Train_acc 0.883789, Test_acc 0.694336\n",
      "Completed epoch 200. Loss: 0.383530223087, Train_acc 0.94043, Test_acc 0.726562\n",
      "Completed epoch 300. Loss: 0.296192424847, Train_acc 0.974609, Test_acc 0.726562\n",
      "Completed epoch 400. Loss: 0.219277466178, Train_acc 0.987305, Test_acc 0.734375\n",
      "Completed epoch 500. Loss: 0.167076686896, Train_acc 0.996094, Test_acc 0.735352\n",
      "Completed epoch 600. Loss: 0.129148652002, Train_acc 0.999023, Test_acc 0.738281\n",
      "Completed epoch 700. Loss: 0.0998192830617, Train_acc 1.0, Test_acc 0.742188\n",
      "Completed epoch 800. Loss: 0.0805371355478, Train_acc 1.0, Test_acc 0.743164\n",
      "Completed epoch 900. Loss: 0.0675567659364, Train_acc 1.0, Test_acc 0.74707\n",
      "Completed epoch 1000. Loss: 0.0582670229406, Train_acc 1.0, Test_acc 0.75\n"
     ]
    }
   ],
   "source": [
    "epochs = 1000\n",
    "moving_loss = 0.\n",
    "\n",
    "for e in range(epochs):\n",
    "    train_data.reset()\n",
    "    for i, batch in enumerate(train_data):\n",
    "        data = batch.data[0].as_in_context(ctx).reshape((-1,784))\n",
    "        label = batch.label[0].as_in_context(ctx)\n",
    "        label_one_hot = nd.one_hot(label, 10)\n",
    "        with autograd.record():\n",
    "            output = net(data)\n",
    "            loss = cross_entropy(output, label_one_hot)\n",
    "        loss.backward()\n",
    "        SGD(params, .001)\n",
    "\n",
    "        ##########################\n",
    "        #  Keep a moving average of the losses\n",
    "        ##########################\n",
    "        if i == 0:\n",
    "            moving_loss = np.mean(loss.asscalar())\n",
    "        else:\n",
    "            moving_loss = .99 * moving_loss + .01 * np.mean(loss.asscalar())\n",
    "            \n",
    "    test_accuracy = evaluate_accuracy(test_data, net)\n",
    "    train_accuracy = evaluate_accuracy(train_data, net)\n",
    "    if e % 100 == 99:\n",
    "        print(\"Completed epoch %s. Loss: %s, Train_acc %s, Test_acc %s\" % \n",
    "              (e+1, moving_loss, train_accuracy, test_accuracy))       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "\n",
    "By the 700th epoch, our model achieves 100% accuracy on the training data. However, it only classifies 75% of the test examples accurately. \n",
    "\n",
    "[PLACEHOLDER]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regularization\n",
    "[PLACEHOLDER]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def l2_penalty(params):\n",
    "    penalty = nd.zeros(shape=1)\n",
    "    for param in params:\n",
    "        penalty = penalty + nd.sum(param ** 2)\n",
    "    return penalty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Re-initializing the parameters\n",
    "\n",
    "[PLACEHOLDER]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for param in params:\n",
    "    param[:] = nd.random_normal(shape=param.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Training L2-regularized logistic regression\n",
    "\n",
    "[PLACEHOLDER]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Completed epoch 100. Loss: 417.827958109, Train_acc 0.904297, Test_acc 0.714844\n",
      "Completed epoch 200. Loss: 222.459426625, Train_acc 0.962891, Test_acc 0.758789\n",
      "Completed epoch 300. Loss: 123.724861786, Train_acc 0.984375, Test_acc 0.78125\n",
      "Completed epoch 400. Loss: 72.6283419307, Train_acc 0.990234, Test_acc 0.806641\n",
      "Completed epoch 500. Loss: 46.1087759935, Train_acc 0.991211, Test_acc 0.816406\n",
      "Completed epoch 600. Loss: 32.333768166, Train_acc 0.992188, Test_acc 0.824219\n",
      "Completed epoch 700. Loss: 25.1729688411, Train_acc 0.993164, Test_acc 0.827148\n",
      "Completed epoch 800. Loss: 21.4474974968, Train_acc 0.992188, Test_acc 0.824219\n",
      "Completed epoch 900. Loss: 19.5080785639, Train_acc 0.992188, Test_acc 0.824219\n",
      "Completed epoch 1000. Loss: 18.4982315813, Train_acc 0.992188, Test_acc 0.829102\n"
     ]
    }
   ],
   "source": [
    "epochs = 1000\n",
    "moving_loss = 0.\n",
    "l2_strength = .1\n",
    "\n",
    "for e in range(epochs):\n",
    "    train_data.reset()\n",
    "    for i, batch in enumerate(train_data):\n",
    "        data = batch.data[0].as_in_context(ctx).reshape((-1,784))\n",
    "        label = batch.label[0].as_in_context(ctx)\n",
    "        label_one_hot = nd.one_hot(label, 10)\n",
    "        with autograd.record():\n",
    "            output = net(data)\n",
    "            loss = nd.sum(cross_entropy(output, label_one_hot)) + l2_strength * l2_penalty(params)\n",
    "        loss.backward()\n",
    "        SGD(params, .001)\n",
    "\n",
    "        ##########################\n",
    "        #  Keep a moving average of the losses\n",
    "        ##########################\n",
    "        if i == 0:\n",
    "            moving_loss = np.mean(loss.asscalar())\n",
    "        else:\n",
    "            moving_loss = .99 * moving_loss + .01 * np.mean(loss.asscalar())\n",
    "            \n",
    "    test_accuracy = evaluate_accuracy(test_data, net)\n",
    "    train_accuracy = evaluate_accuracy(train_data, net)\n",
    "    if e % 100 == 99:\n",
    "        print(\"Completed epoch %s. Loss: %s, Train_acc %s, Test_acc %s\" % \n",
    "              (e+1, moving_loss, train_accuracy, test_accuracy))       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "\n",
    "By adding L2 regularization we were able to increase the performance on test data from 75% accuracy to 83% accuracy. That's a 32% reduction in error. In a lot of applications, this big an improvement can make the difference between a viable product and useless system.\n",
    "\n",
    "[PLACEHOLDER FOR DISCUSSION]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For whinges or inquiries, [open an issue on  GitHub.](https://github.com/zackchase/mxnet-the-straight-dope)"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}