assignment1/knn.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from google.colab import drive\n",
    "\n",
    "drive.mount('/content/drive', force_remount=True)\n",
    "\n",
    "# enter the foldername in your Drive where you have saved the unzipped\n",
    "# 'cs231n' folder containing the '.py', 'classifiers' and 'datasets'\n",
    "# folders.\n",
    "# e.g. 'cs231n/assignments/assignment1/cs231n/'\n",
    "FOLDERNAME = None\n",
    "\n",
    "assert FOLDERNAME is not None, \"[!] Enter the foldername.\"\n",
    "\n",
    "%cd drive/My\\ Drive\n",
    "%cp -r $FOLDERNAME ../../\n",
    "%cd ../../\n",
    "%cd cs231n/datasets/\n",
    "!bash get_datasets.sh\n",
    "%cd ../../"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-title"
    ]
   },
   "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",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "outputs": [],
   "source": [
    "# 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "outputs": [],
   "source": [
    "# Load the raw CIFAR-10 data.\n",
    "cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'\n",
    "\n",
    "# Cleaning up variables to prevent loading data multiple times (which may cause memory issue)\n",
    "try:\n",
    "   del X_train, y_train\n",
    "   del X_test, y_test\n",
    "   print('Clear previously loaded data.')\n",
    "except:\n",
    "   pass\n",
    "\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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "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(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()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "outputs": [],
   "source": [
    "# Subsample the data for more efficient code execution in this exercise\n",
    "num_training = 5000\n",
    "mask = list(range(num_training))\n",
    "X_train = X_train[mask]\n",
    "y_train = y_train[mask]\n",
    "\n",
    "num_test = 500\n",
    "mask = list(range(num_test))\n",
    "X_test = X_test[mask]\n",
    "y_test = y_test[mask]\n",
    "\n",
    "# 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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore"
    ]
   },
   "outputs": [],
   "source": [
    "from cs231n.classifiers 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)"
   ]
  },
  {
   "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",
    "**Note: For the three distance computations that we require you to implement in this notebook, you may not use the np.linalg.norm() function that numpy provides.**\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",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 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')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-inline"
    ]
   },
   "source": [
    "**Inline Question 1** \n",
    "\n",
    "Notice the structured patterns in the distance matrix, where some rows or columns are visible brighter. (Note that with the default color scheme black indicates low distances while white indicates high distances.)\n",
    "\n",
    "- What in the data is the cause behind the distinctly bright rows?\n",
    "- What causes the columns?\n",
    "\n",
    "$\\color{blue}{\\textit Your Answer:}$ *fill this in.*\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should expect to see approximately `27%` accuracy. Now lets try out a larger `k`, say `k = 5`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_test_pred = classifier.predict_labels(dists, k=5)\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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should expect to see a slightly better performance than with `k = 1`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-inline"
    ]
   },
   "source": [
    "**Inline Question 2**\n",
    "\n",
    "We can also use other distance metrics such as L1 distance.\n",
    "For pixel values $p_{ij}^{(k)}$ at location $(i,j)$ of some image $I_k$, \n",
    "\n",
    "the mean $\\mu$ across all pixels over all images is $$\\mu=\\frac{1}{nhw}\\sum_{k=1}^n\\sum_{i=1}^{h}\\sum_{j=1}^{w}p_{ij}^{(k)}$$\n",
    "And the pixel-wise mean $\\mu_{ij}$ across all images is \n",
    "$$\\mu_{ij}=\\frac{1}{n}\\sum_{k=1}^np_{ij}^{(k)}.$$\n",
    "The general standard deviation $\\sigma$ and pixel-wise standard deviation $\\sigma_{ij}$ is defined similarly.\n",
    "\n",
    "Which of the following preprocessing steps will not change the performance of a Nearest Neighbor classifier that uses L1 distance? Select all that apply.\n",
    "1. Subtracting the mean $\\mu$ ($\\tilde{p}_{ij}^{(k)}=p_{ij}^{(k)}-\\mu$.)\n",
    "2. Subtracting the per pixel mean $\\mu_{ij}$  ($\\tilde{p}_{ij}^{(k)}=p_{ij}^{(k)}-\\mu_{ij}$.)\n",
    "3. Subtracting the mean $\\mu$ and dividing by the standard deviation $\\sigma$.\n",
    "4. Subtracting the pixel-wise mean $\\mu_{ij}$ and dividing by the pixel-wise standard deviation $\\sigma_{ij}$.\n",
    "5. Rotating the coordinate axes of the data.\n",
    "\n",
    "$\\color{blue}{\\textit Your Answer:}$\n",
    "\n",
    "\n",
    "$\\color{blue}{\\textit Your Explanation:}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore-input"
    ]
   },
   "outputs": [],
   "source": [
    "# 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('One loop 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')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "tags": [
     "pdf-ignore-input"
    ]
   },
   "outputs": [],
   "source": [
    "# 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('No loop 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')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "no_loop",
    "tags": [
     "pdf-ignore-input"
    ]
   },
   "outputs": [],
   "source": [
    "# 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!\n",
    "\n",
    "# NOTE: depending on what machine you're using, \n",
    "# you might not see a speedup when you go from two loops to one loop, \n",
    "# and might even see a slow-down."
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "tags": [
     "code"
    ]
   },
   "outputs": [],
   "source": [
    "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",
    "# *****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",
    "# 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",
    "# *****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",
    "# 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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "pdf-ignore-input"
    ]
   },
   "outputs": [],
   "source": [
    "# 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 sorted(k_to_accuracies.items())])\n",
    "accuracies_std = np.array([np.std(v) for k,v in sorted(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()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "cross_validation"
   },
   "outputs": [],
   "source": [
    "# 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. You should be able to get above 28% accuracy on the test 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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "pdf-inline"
    ]
   },
   "source": [
    "**Inline Question 3**\n",
    "\n",
    "Which of the following statements about $k$-Nearest Neighbor ($k$-NN) are true in a classification setting, and for all $k$? Select all that apply.\n",
    "1. The decision boundary of the k-NN classifier is linear.\n",
    "2. The training error of a 1-NN will always be lower than that of 5-NN.\n",
    "3. The test error of a 1-NN will always be lower than that of a 5-NN.\n",
    "4. The time needed to classify a test example with the k-NN classifier grows with the size of the training set.\n",
    "5. None of the above.\n",
    "\n",
    "$\\color{blue}{\\textit Your Answer:}$\n",
    "\n",
    "\n",
    "$\\color{blue}{\\textit Your Explanation:}$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# IMPORTANT\n",
    "\n",
    "This is the end of this question. Please do the following:\n",
    "\n",
    "1. Click `File -> Save` to make sure the latest checkpoint of this notebook is saved to your Drive.\n",
    "2. Execute the cell below to download the modified `.py` files back to your drive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "FOLDER_TO_SAVE = os.path.join('drive/My Drive/', FOLDERNAME)\n",
    "FILES_TO_SAVE = ['cs231n/classifiers/k_nearest_neighbor.py']\n",
    "\n",
    "for files in FILES_TO_SAVE:\n",
    "  with open(os.path.join(FOLDER_TO_SAVE, '/'.join(files.split('/')[1:])), 'w') as f:\n",
    "    f.write(''.join(open(files).readlines()))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 4
}