Part2_KNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Nearest-neighbor image classification\n",
    "<a id=part2></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part, we'll familiarize ourselves with the `PyTorch` tensor API by implementing a very simple classifier,\n",
    "kNN, using tensor operations alone.\n",
    "We'll then implement cross-validation, an important ML technique used to find a suitable\n",
    "set values for a model's hyperparameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "import torchvision\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import unittest\n",
    "\n",
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "plt.rcParams.update({'font.size': 12})\n",
    "torch.random.manual_seed(1904)\n",
    "test = unittest.TestCase()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### kNN Classification\n",
    "<a id=part2_1></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arguably the most basic classification scheme in a supervised learning setting is the\n",
    "`k` nearest-neighbor (kNN) classifier.\n",
    "Given a training data set, kNN's \"training\" phase consists of simply memorizing it.\n",
    "When a classification of an unseen sample is required, it's distance (usually L1 or L2)\n",
    "is computed from all training samples.\n",
    "The unseen sample is then classified according to the majority label of it's `k` nearest-neighbors.\n",
    "\n",
    "Here we'll implement the most basic kNN, working directly on image pixel values and computing L2 distance\n",
    "between a test image and every known training image.\n",
    "We'll use data from the [MNIST](http://yann.lecun.com/exdb/mnist/) database of handwritten digits.\n",
    "This database contains single-channel images with a constant black background and the digits are\n",
    "roughly the same size, which makes it feasible to obtain bearable classification accuracy even with\n",
    "such a naïve model.\n",
    "\n",
    "Note however that real-world KNN model are often implemented with tree-based data structures to\n",
    "find nearest neighbors in logarithmic time, specialized distance functions and\n",
    "using image features instead of raw pixels.\n",
    "\n",
    "**TODO** Implement the `TensorView` transform in the `hw1/transforms` module, and run the following code to\n",
    "load the data we'll work with."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Prepare data for kNN Classifier\n",
    "import torchvision.transforms as tvtf\n",
    "import cs236605.dataloader_utils as dataloader_utils\n",
    "import hw1.datasets as hw1datasets\n",
    "import hw1.transforms as hw1tf\n",
    "\n",
    "# Define the transforms that should be applied to each CIFAR-10 image before returning it\n",
    "tf_ds = tvtf.Compose([\n",
    "    tvtf.ToTensor(), # Convert PIL image to pytorch Tensor\n",
    "    hw1tf.TensorView(-1), # Reshape to 1D Tensor\n",
    "])\n",
    "\n",
    "# Define how much data to load (only use a subset for speed)\n",
    "num_train = 10000\n",
    "num_test = 1000\n",
    "batch_size = 1024\n",
    "\n",
    "# Training dataset & loader\n",
    "ds_train = hw1datasets.SubsetDataset(\n",
    "    torchvision.datasets.MNIST(root='./data/mnist/', download=True, train=True, transform=tf_ds), num_train)\n",
    "dl_train = torch.utils.data.DataLoader(ds_train, batch_size)\n",
    "\n",
    "# Test dataset & loader\n",
    "ds_test = hw1datasets.SubsetDataset(\n",
    "    torchvision.datasets.MNIST(root='./data/mnist/', download=True, train=False, transform=tf_ds), num_test)\n",
    "dl_test = torch.utils.data.DataLoader(ds_test, batch_size)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**TODO** Complete the implementation of the kNN classifier in the module `hw1/knn_classifier.py`:\n",
    "1. Implement L2 distance calculation in `calc_distances()`.\n",
    "1. Implement label prediction in `predict()`.\n",
    "1. Implement accuracy calculation in the `accuracy()` function.\n",
    "\n",
    "Use the following code to test your implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hw1.knn_classifier as hw1knn\n",
    "\n",
    "# Get all test data to predict in one go\n",
    "x_test, y_test = dataloader_utils.flatten(dl_test)\n",
    "\n",
    "# Test kNN Classifier\n",
    "knn_classifier = hw1knn.KNNClassifier(k=10)\n",
    "knn_classifier.train(dl_train)\n",
    "y_pred = knn_classifier.predict(x_test)\n",
    "\n",
    "# Calculate accuracy\n",
    "accuracy = hw1knn.accuracy(y_test, y_pred)\n",
    "print(f'Accuracy: {accuracy*100:.2f}%')\n",
    "\n",
    "# Sanity check\n",
    "test.assertGreater(accuracy, 0.8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cross-validation\n",
    "<a id=part2_2></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A common way to  choose hyperparameters for a model or even the model itself is by applying\n",
    "**K-fold cross-validation**.\n",
    "For each candidate set of hyperparameters, the model is trained `K` times, each time with a different split of the training data to train and validation sets (called a fold). The set of hyperparameters which resulted in the the lowest average validation error rate is selected.\n",
    "\n",
    "More specifically:\n",
    "\n",
    "1. For all choices of a model and/or set of hyperparameters for the model:\n",
    "    1. Split training set into `K` non-overlapping parts. \n",
    "    1. For `k=0,...,K-1`:\n",
    "        1. Select the `k`-th part as the validation set and the remaining `k-1` parts as the training set.\n",
    "        1. Train the current model on the current training set.\n",
    "        1. Evaluate the model on the current validation set to obtain it's validation error.\n",
    "        1. Update the current model's average validation error.\n",
    "    1. Select the model with the lowest average validation error.\n",
    "1. Train the selected model with the entire training set.\n",
    "1. Evaluate the model with the test set.\n",
    "\n",
    "\n",
    "Now we would like to find the best value of K for applying our kNN model to CIFAR-10.\n",
    "In this case we already fixed the model and there is only one hyperparameter, the value of `k`\n",
    "(not to be confused with `K`, the number of folds for the cross validation).\n",
    "\n",
    "**TODO** Complete the implementation of the `find_best_k` function in the `knn_classifier.py` module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_folds = 5\n",
    "k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]\n",
    "\n",
    "# Run cross-validation\n",
    "best_k, accuracies = hw1knn.find_best_k(ds_train, k_choices, num_folds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot accuracies per k\n",
    "_, ax = plt.subplots(figsize=(12,6), subplot_kw=dict(xticks=k_choices))\n",
    "for i, k in enumerate(k_choices):\n",
    "    curr_accuracies = accuracies[i]\n",
    "    ax.scatter([k] * len(curr_accuracies), curr_accuracies)\n",
    "\n",
    "accuracies_mean = np.array([np.mean(accs) for accs in accuracies])\n",
    "accuracies_std = np.array([np.std(accs) for accs in accuracies])\n",
    "ax.errorbar(k_choices, accuracies_mean, yerr=accuracies_std)\n",
    "ax.set_title(f'{num_folds}-fold Cross-validation on k')\n",
    "ax.set_xlabel('k')\n",
    "ax.set_ylabel('Accuracy')\n",
    "ax.grid()\n",
    "\n",
    "print('best_k =', best_k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we found our `best_k`, we can train the model with that value of `k` on the full training set and evaluate the accuracy on the test set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier = hw1knn.KNNClassifier(k=best_k)\n",
    "knn_classifier.train(dl_train)\n",
    "y_pred = knn_classifier.predict(x_test)\n",
    "\n",
    "# Calculate accuracy\n",
    "accuracy_best_k = hw1knn.accuracy(y_test, y_pred)\n",
    "print(f'Accuracy: {accuracy_best_k*100:.2f}%')\n",
    "\n",
    "test.assertGreater(accuracy_best_k, accuracy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Questions\n",
    "\n",
    "**TODO** Answer the following questions. Write your answers in the appropriate variables in the module `hw1/answers.py`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from cs236605.answers import display_answer\n",
    "import hw1.answers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Question 1\n",
    "\n",
    "Does increasing `k` lead to improved generalization for unseen data? Why or why not? Up to what point? Think about the extremal values of `k`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display_answer(hw1.answers.part2_q1)"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}