knn.ipynb

{
 "metadata": {
  "kernelspec": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "display_name": "IPython (Python 2)",
   "language": "python",
   "name": "python2"
  },
  "name": "",
  "signature": "sha256:797f7f42152aa4dad15017377ed2fed741551e92800ebdb81f48894f760f4479"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# k-Nearest Neighbor (kNN) exercise\n",
      "\n",
      "*Complete and hand in this completed worksheet (including its outputs and any supporting code outside of the worksheet) with your assignment submission. For more details see the [assignments page](http://vision.stanford.edu/teaching/cs231n/assignments.html) on the course website.*\n",
      "\n",
      "The kNN classifier consists of two stages:\n",
      "\n",
      "- During training, the classifier takes the training data and simply remembers it\n",
      "- During testing, kNN classifies every test image by comparing to all training images and transfering the labels of the k most similar training examples\n",
      "- The value of k is cross-validated\n",
      "\n",
      "In this exercise you will implement these steps and understand the basic Image Classification pipeline, cross-validation, and gain proficiency in writing efficient, vectorized code."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Run some setup code for this notebook.\n",
      "\n",
      "import random\n",
      "import numpy as np\n",
      "from cs231n.data_utils import load_CIFAR10\n",
      "import matplotlib.pyplot as plt\n",
      "\n",
      "# This is a bit of magic to make matplotlib figures appear inline in the notebook\n",
      "# rather than in a new window.\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",
      "# Some more magic so that the notebook will reload external python modules;\n",
      "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
      "%load_ext autoreload\n",
      "%autoreload 2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Load the raw CIFAR-10 data.\n",
      "cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'\n",
      "X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)\n",
      "\n",
      "# As a sanity check, we print out the size of the training and test data.\n",
      "print 'Training data shape: ', X_train.shape\n",
      "print 'Training labels shape: ', y_train.shape\n",
      "print 'Test data shape: ', X_test.shape\n",
      "print 'Test labels shape: ', y_test.shape"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "EOFError",
       "evalue": "",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mEOFError\u001b[0m                                  Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-2-76ab1121c87e>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m# Load the raw CIFAR-10 data.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[0mcifar10_dir\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'cs231n/datasets/cifar-10-batches-py'\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m \u001b[0mX_train\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0my_train\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mX_test\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0my_test\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mload_CIFAR10\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcifar10_dir\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      4\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[1;31m# As a sanity check, we print out the size of the training and test data.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32mE:\\workspace\\assignment1-master\\cs231n\\data_utils.pyc\u001b[0m in \u001b[0;36mload_CIFAR10\u001b[1;34m(ROOT)\u001b[0m\n\u001b[0;32m     19\u001b[0m   \u001b[1;32mfor\u001b[0m \u001b[0mb\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m6\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     20\u001b[0m     \u001b[0mf\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mos\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpath\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mROOT\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m'data_batch_%d'\u001b[0m \u001b[1;33m%\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 21\u001b[1;33m     \u001b[0mX\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mY\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mload_CIFAR_batch\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     22\u001b[0m     \u001b[0mxs\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[0mys\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mY\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32mE:\\workspace\\assignment1-master\\cs231n\\data_utils.pyc\u001b[0m in \u001b[0;36mload_CIFAR_batch\u001b[1;34m(filename)\u001b[0m\n\u001b[0;32m      6\u001b[0m   \u001b[1;34m\"\"\" load single batch of cifar \"\"\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      7\u001b[0m   \u001b[1;32mwith\u001b[0m \u001b[0mopen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfilename\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m'r'\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 8\u001b[1;33m     \u001b[0mdatadict\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mpickle\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mload\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      9\u001b[0m     \u001b[0mX\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mdatadict\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m'data'\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     10\u001b[0m     \u001b[0mY\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mdatadict\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m'labels'\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;31mEOFError\u001b[0m: "
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# 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(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(X_train[idx].astype('uint8'))\n",
      "        plt.axis('off')\n",
      "        if i == 0:\n",
      "            plt.title(cls)\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Subsample the data for more efficient code execution in this exercise\n",
      "num_training = 5000\n",
      "mask = range(num_training)\n",
      "X_train = X_train[mask]\n",
      "y_train = y_train[mask]\n",
      "\n",
      "num_test = 500\n",
      "mask = range(num_test)\n",
      "X_test = X_test[mask]\n",
      "y_test = y_test[mask]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# 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",
      "print X_train.shape, X_test.shape"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from cs231n.classifiers.k_nearest_neighbor import KNearestNeighbor\n",
      "\n",
      "# Create a kNN classifier instance. \n",
      "# Remember that training a kNN classifier is a noop: \n",
      "# the Classifier simply remembers the data and does no further processing \n",
      "classifier = KNearestNeighbor()\n",
      "classifier.train(X_train, y_train)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We would now like to classify the test data with the kNN classifier. Recall that we can break down this process into two steps: \n",
      "\n",
      "1. First we must compute the distances between all test examples and all train examples. \n",
      "2. Given these distances, for each test example we find the k nearest examples and have them vote for the label\n",
      "\n",
      "Lets begin with computing the distance matrix between all training and test examples. For example, if there are **Ntr** training examples and **Nte** test examples, this stage should result in a **Nte x Ntr** matrix where each element (i,j) is the distance between the i-th test and j-th train example.\n",
      "\n",
      "First, open `cs231n/classifiers/k_nearest_neighbor.py` and implement the function `compute_distances_two_loops` that uses a (very inefficient) double loop over all pairs of (test, train) examples and computes the distance matrix one element at a time."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Open cs231n/classifiers/k_nearest_neighbor.py and implement\n",
      "# compute_distances_two_loops.\n",
      "\n",
      "# Test your implementation:\n",
      "dists = classifier.compute_distances_two_loops(X_test)\n",
      "print dists.shape"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# We can visualize the distance matrix: each row is a single test example and\n",
      "# its distances to training examples\n",
      "plt.imshow(dists, interpolation='none')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Inline Question #1:** Notice the structured patterns in the distance matrix. \n",
      "\n",
      "- What is the cause behind the distinctly visible rows? \n",
      "- What causes the columns?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Your Answer**: *the white rows mean that the test case is different from the train cases.the black rows mean that the test case is similar to the train cases.*\n",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Now implement the function predict_labels and run the code below:\n",
      "# We use k = 1 (which is Nearest Neighbor).\n",
      "y_test_pred = classifier.predict_labels(dists, k=1)\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) / num_test\n",
      "print 'Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Now lets speed up distance matrix computation by using partial vectorization\n",
      "# with one loop. Implement the function compute_distances_one_loop and run the\n",
      "# code below:\n",
      "dists_one = classifier.compute_distances_one_loop(X_test)\n",
      "\n",
      "# To ensure that our vectorized implementation is correct, we make sure that it\n",
      "# agrees with the naive implementation. There are many ways to decide whether\n",
      "# two matrices are similar; one of the simplest is the Frobenius norm. In case\n",
      "# you haven't seen it before, the Frobenius norm of two matrices is the square\n",
      "# root of the squared sum of differences of all elements; in other words, reshape\n",
      "# the matrices into vectors and compute the Euclidean distance between them.\n",
      "difference = np.linalg.norm(dists - dists_one, ord='fro')\n",
      "print 'Difference was: %f' % (difference, )\n",
      "if difference < 0.001:\n",
      "  print 'Good! The distance matrices are the same'\n",
      "else:\n",
      "  print 'Uh-oh! The distance matrices are different'"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Now implement the fully vectorized version inside compute_distances_no_loops\n",
      "# and run the code\n",
      "dists_two = classifier.compute_distances_no_loops(X_test)\n",
      "\n",
      "# check that the distance matrix agrees with the one we computed before:\n",
      "difference = np.linalg.norm(dists - dists_two, ord='fro')\n",
      "print 'Difference was: %f' % (difference, )\n",
      "if difference < 0.001:\n",
      "  print 'Good! The distance matrices are the same'\n",
      "else:\n",
      "  print 'Uh-oh! The distance matrices are different'"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Let's compare how fast the implementations are\n",
      "def time_function(f, *args):\n",
      "  \"\"\"\n",
      "  Call a function f with args and return the time (in seconds) that it took to execute.\n",
      "  \"\"\"\n",
      "  import time\n",
      "  tic = time.time()\n",
      "  f(*args)\n",
      "  toc = time.time()\n",
      "  return toc - tic\n",
      "\n",
      "two_loop_time = time_function(classifier.compute_distances_two_loops, X_test)\n",
      "print 'Two loop version took %f seconds' % two_loop_time\n",
      "\n",
      "one_loop_time = time_function(classifier.compute_distances_one_loop, X_test)\n",
      "print 'One loop version took %f seconds' % one_loop_time\n",
      "\n",
      "no_loop_time = time_function(classifier.compute_distances_no_loops, X_test)\n",
      "print 'No loop version took %f seconds' % no_loop_time\n",
      "\n",
      "# you should see significantly faster performance with the fully vectorized implementation"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Cross-validation\n",
      "\n",
      "We have implemented the k-Nearest Neighbor classifier but we set the value k = 5 arbitrarily. We will now determine the best value of this hyperparameter with cross-validation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "num_folds = 5\n",
      "k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]\n",
      "\n",
      "X_train_folds = []\n",
      "y_train_folds = []\n",
      "################################################################################\n",
      "# TODO:                                                                        #\n",
      "# Split up the training data into folds. After splitting, X_train_folds and    #\n",
      "# y_train_folds should each be lists of length num_folds, where                #\n",
      "# y_train_folds[i] is the label vector for the points in X_train_folds[i].     #\n",
      "# Hint: Look up the numpy array_split function.                                #\n",
      "################################################################################\n",
      "idx=np.random.permutation(num_training)\n",
      "for i in range(num_folds):\n",
      "    start=i*num_training/5\n",
      "    end=start+num_training/5\n",
      "    X_train_folds.append(X_train[start:end])\n",
      "    y_train_folds.append(y_train[start:end])\n",
      "################################################################################\n",
      "#                                 END OF YOUR CODE                             #\n",
      "################################################################################\n",
      "\n",
      "# A dictionary holding the accuracies for different values of k that we find\n",
      "# when running cross-validation. After running cross-validation,\n",
      "# k_to_accuracies[k] should be a list of length num_folds giving the different\n",
      "# accuracy values that we found when using that value of k.\n",
      "k_to_accuracies = {}\n",
      "\n",
      "\n",
      "################################################################################\n",
      "# TODO:                                                                        #\n",
      "# Perform k-fold cross validation to find the best value of k. For each        #\n",
      "# possible value of k, run the k-nearest-neighbor algorithm num_folds times,   #\n",
      "# where in each case you use all but one of the folds as training data and the #\n",
      "# last fold as a validation set. Store the accuracies for all fold and all     #\n",
      "# values of k in the k_to_accuracies dictionary.                               #\n",
      "################################################################################\n",
      "for i in num_folds:\n",
      "    tr = \n",
      "    for kk in k_choices:\n",
      "    \n",
      "################################################################################\n",
      "#                                 END OF YOUR CODE                             #\n",
      "################################################################################\n",
      "\n",
      "# Print out the computed accuracies\n",
      "for k in sorted(k_to_accuracies):\n",
      "    for accuracy in k_to_accuracies[k]:\n",
      "        print 'k = %d, accuracy = %f' % (k, accuracy)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# plot the raw observations\n",
      "for k in k_choices:\n",
      "  accuracies = k_to_accuracies[k]\n",
      "  plt.scatter([k] * len(accuracies), accuracies)\n",
      "\n",
      "# plot the trend line with error bars that correspond to standard deviation\n",
      "accuracies_mean = np.array([np.mean(v) for k,v in k_to_accuracies.items()])\n",
      "accuracies_std = np.array([np.std(v) for k,v in k_to_accuracies.items()])\n",
      "plt.errorbar(k_choices, accuracies_mean, yerr=accuracies_std)\n",
      "plt.title('Cross-validation on k')\n",
      "plt.xlabel('k')\n",
      "plt.ylabel('Cross-validation accuracy')\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Based on the cross-validation results above, choose the best value for k,   \n",
      "# retrain the classifier using all the training data, and test it on the test\n",
      "# data.\n",
      "best_k = 1\n",
      "\n",
      "classifier = KNearestNeighbor()\n",
      "classifier.train(X_train, y_train)\n",
      "y_test_pred = classifier.predict(X_test, k=best_k)\n",
      "\n",
      "# Compute and display the accuracy\n",
      "num_correct = np.sum(y_test_pred == y_test)\n",
      "accuracy = float(num_correct) / num_test\n",
      "print 'Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}