Jupyter Notebook Block 1 - Introduction to Image Classification.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "df630e55-57dd-470a-849b-f1bc90ac719e"
    }
   },
   "source": [
    "# 1. Importing and Visualization of CIFAR-10 Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "409a1ab7-fe1d-4430-b904-7694020a6223"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# function to import CIFAR-10 data set\n",
    "def unpickle(file):\n",
    "    import pickle\n",
    "    with open(file, 'rb') as fo:\n",
    "        dict = pickle.load(fo, encoding='bytes')\n",
    "    return dict\n",
    "data_batch_1 = unpickle(\"./data/data_batch_1\")\n",
    "data_batch_2 = unpickle(\"./data/data_batch_2\")\n",
    "data_batch_3 = unpickle(\"./data/data_batch_3\")\n",
    "data_batch_4 = unpickle(\"./data/data_batch_4\")\n",
    "data_batch_5 = unpickle(\"./data/data_batch_5\")\n",
    "test_batch = unpickle(\"./data/test_batch\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ce2be501-0be3-4750-8207-dfc00d7db01a"
    }
   },
   "source": [
    "What is the data structure of e.g. data_batch_1 ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "f77bd9ec-de3b-4c56-b08d-4a65f0780408"
    }
   },
   "outputs": [],
   "source": [
    "type(data_batch_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "09a5b60b-dcbb-4f97-ab57-e4611c253e2e"
    }
   },
   "source": [
    "What are the keys of e.g. data_batch_1 ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "c874a7c9-de0c-4ccd-a0f1-8f8a3265a0b6"
    }
   },
   "outputs": [],
   "source": [
    "data_batch_1.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "a7f910e7-0b11-453b-84d5-df6ac88ac6dd"
    }
   },
   "source": [
    "What is the data structure of data_batch_1[b'data'] ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "fe299a35-c930-4078-97b7-c9b67f42ec42"
    }
   },
   "outputs": [],
   "source": [
    "type(data_batch_1[b'data'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "3f978c4f-50d0-4f00-9f19-bf8744e505a3"
    }
   },
   "source": [
    "What is the data structure of data_batch_1[b'labels'] ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "46a97575-36c0-4920-a8dc-762e94239b7e"
    }
   },
   "outputs": [],
   "source": [
    "type(data_batch_1[b'labels'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2fd19982-c318-4303-8042-7a5a6998d175"
    }
   },
   "source": [
    "What is the shape of data_batch_1[b'data'] ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "b012720d-81f8-455d-8ce7-bfca64a842c8"
    }
   },
   "outputs": [],
   "source": [
    "data_batch_1[b'data'].shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "378aeda2-a547-435e-b28b-09ceb0074a53"
    }
   },
   "source": [
    "What is the size of data_batch_1[b'labels'] ?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "49c776cb-c8aa-461b-a0da-4f4d38342e2e"
    }
   },
   "outputs": [],
   "source": [
    "len(data_batch_1[b'labels'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "02ca495c-e6d2-48d4-9bc2-2295272d5f6f"
    }
   },
   "source": [
    "What are the first 10 elements of data_batch_1[b'labels'] ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "438920f4-774e-4e94-9b7c-30a2106d163c"
    }
   },
   "outputs": [],
   "source": [
    "data_batch_1[b'labels'][:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "1e599fcd-a46c-4750-94f8-1cf4ad8fb342"
    }
   },
   "source": [
    "What is the data type of data_batch_1[b'data'] ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "7617a699-c3d5-434f-97a5-3443489ac9db"
    }
   },
   "outputs": [],
   "source": [
    "data_batch_1[b'data'].dtype"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "067d850d-0411-4af6-8714-a79b310ca8c1"
    }
   },
   "source": [
    "Let us concatenate the batch training data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "942f351b-b771-4375-8df2-eec28391a576"
    }
   },
   "outputs": [],
   "source": [
    "X_train=np.concatenate([data_batch_1[b'data'], \n",
    "                         data_batch_2[b'data'], \n",
    "                         data_batch_3[b'data'], \n",
    "                         data_batch_4[b'data'], \n",
    "                         data_batch_5[b'data']], \n",
    "                         axis = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "b289f0b9-b3ab-480b-9ae6-76a893980efe"
    }
   },
   "source": [
    "Let us concatenate the training labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "9b85b9a0-5f2b-4c68-a74f-82f1ec212215"
    }
   },
   "outputs": [],
   "source": [
    "y_train=np.concatenate([data_batch_1[b'labels'] , \n",
    "                data_batch_2[b'labels'],\n",
    "                data_batch_3[b'labels'],\n",
    "                data_batch_4[b'labels'],\n",
    "                data_batch_5[b'labels']], \n",
    "                axis = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d9967582-1305-4b95-948b-e75c46fc49bb"
    }
   },
   "source": [
    "Let us define the test data as X_test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "5c85918c-f89e-4156-8cdd-ca38d14afbb9"
    }
   },
   "outputs": [],
   "source": [
    "X_test = test_batch[b'data']\n",
    "X_test.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "48754d72-9acd-49cf-b209-737c45047284"
    }
   },
   "source": [
    "Let us cast the test labels as ndarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "5f913d95-aa49-4727-8c6f-5630cbf59741"
    }
   },
   "outputs": [],
   "source": [
    "y_test=np.array(test_batch[b'labels']) \n",
    "y_test.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f4c3aa97-0d97-4e9c-a6b3-f2d2b1f08632"
    }
   },
   "source": [
    "What is the shape of X_train ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "a0eb7a33-19c9-46e4-b471-6f7904389177"
    }
   },
   "outputs": [],
   "source": [
    "X_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "81d3c33f-544e-44c8-8260-e89143cc6ef1"
    }
   },
   "source": [
    "What is the shape of Y_train ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "d699e7a7-efc0-421f-bd8d-2d2b34a09516"
    }
   },
   "outputs": [],
   "source": [
    "y_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d0a61e44-a2a9-4dff-9849-5f6a0e232290"
    }
   },
   "source": [
    "Let us visualize an image. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "d817d603-7d37-4ff2-b3d1-e95875b48f8f"
    },
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.imshow(X_train[20].reshape((3,32,32)).transpose((1,2,0)).astype('uint8'))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- By means of `reshape` we can convert an array from one shape to another without \n",
    "copying any data. To do this, we pass a tuple indicating the new shape to the `reshape` array instance method. \n",
    "\n",
    "- By default, `NumPy` arrays are created in _row major_ order. Spatially this means, that if we have a two-dimensional array of data, the items in each row of the array are stored in adjacent memory locations. In the case of a three-dimensional array of data, the items along `axis=2` are stored in adjacent order. Since the first 32 entries of the array `X_train[0]` are the red channel values of the first row of the image, etc., we need to pass the tuple $(3,32,32)$ to `reshape`. In conclusion, when __reshaping__ the array, higher order dimensions are traversed _first_ (e.g. axis $ 2 $ before advancing on axis $ 1 $.) \n",
    "\n",
    "- `plt.imshow` needs for each inner list the values representing a pixel. Here, with \n",
    "an RGB image, there are 3 values. We thus need to transpose the array : the RGB values need to be located along `axis=2`. \n",
    "\n",
    "- Using ndarray's `astype` method, we can cast an array from one `dtype` to another. `uint8` represents unsigned 8-bit integer types. Why 8 bits? Most displays can only render 8 bits per channel worth of color gradation. Why can they only render 8 bits/channel? Because that is about all the human eye can see."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "38cf20c0-9404-4f32-91ed-a00e910832f8"
    }
   },
   "source": [
    "We visualize some examples from the dataset.\n",
    "We show a few examples of training images from each class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "ba3743b9-ea50-4201-ad99-5fa47e8b82fb"
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']\n",
    "num_classes = len(classes)\n",
    "samples_per_class = 7\n",
    "\n",
    "\n",
    "\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].reshape((3,32,32)).transpose((1,2,0)).astype('uint8'))\n",
    "        plt.axis('off')\n",
    "        if i == 0:\n",
    "            plt.title(cls)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- When iterating over a sequence we often want to keep track of the index of the \n",
    "current item. Python's built-in function `enumerate` returns a sequence of $i$, value \n",
    "tuples.\n",
    "\n",
    "- `np.flatnonzero` returns indices that are non-zero in the (flattened version of) `y_train == y`, that is, it returns the indices for the elements that are `True`.\n",
    "\n",
    "- `np.random.choice(..., replace=False)` generates a random sample from a given 1-D array without replacement.\n",
    "\n",
    "\n",
    "- The `subplot()` command specifies `numrows`, `numcols`, `fignum` where `fignum` ranges from $ 1 $ to `numrows*numcols`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ab168c02-9867-455d-815d-c2de707e2f87"
    }
   },
   "source": [
    "# 2. K-Nearest-Neighbour Classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "36557d31-2ba4-416c-8ead-a92fb7446e85"
    }
   },
   "source": [
    " We subsample the data for more efficient code execution in this exercise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "26316896-3b01-455b-9a0a-87278f088d83"
    }
   },
   "outputs": [],
   "source": [
    "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]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "27db2b6f-c417-4d15-bff4-8c00d58cb808"
    }
   },
   "source": [
    "We define Class KNearestNeighbor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "497fbf77-9a17-4b35-a0d8-375972850902"
    }
   },
   "outputs": [],
   "source": [
    "class KNearestNeighbor():\n",
    "  \"\"\" a kNN classifier with L2 distance \"\"\"\n",
    "\n",
    "  def __init__(self):\n",
    "    pass\n",
    "\n",
    "  def train(self, X, y):\n",
    "    \"\"\"\n",
    "    Train the classifier. For k-nearest neighbors this is just \n",
    "    memorizing the training data.\n",
    "\n",
    "    Inputs:\n",
    "    - X: A numpy array of shape (num_train, D) containing the training data\n",
    "      consisting of num_train samples each of dimension D.\n",
    "    - y: A numpy array of shape (N,) containing the training labels, where\n",
    "         y[i] is the label for X[i].\n",
    "    \"\"\"\n",
    "    self.X_train = X.astype('float')\n",
    "    self.y_train = y\n",
    "    \n",
    "  def predict(self, X, k=1, num_loops=0):\n",
    "    \"\"\"\n",
    "    Predict labels for test data using this classifier.\n",
    "\n",
    "    Inputs:\n",
    "    - X: A numpy array of shape (num_test, D) containing test data consisting\n",
    "         of num_test samples each of dimension D.\n",
    "    - k: The number of nearest neighbors that vote for the predicted labels.\n",
    "    - num_loops: Determines which implementation to use to compute distances\n",
    "      between training points and testing points.\n",
    "\n",
    "    Returns:\n",
    "    - y: A numpy array of shape (num_test,) containing predicted labels for the\n",
    "      test data, where y[i] is the predicted label for the test point X[i].  \n",
    "    \"\"\"\n",
    "    if num_loops == 0:\n",
    "      dists = self.compute_distances_no_loops(X)\n",
    "    elif num_loops == 1:\n",
    "      dists = self.compute_distances_one_loop(X)\n",
    "    elif num_loops == 2:\n",
    "      dists = self.compute_distances_two_loops(X)\n",
    "    else:\n",
    "      raise ValueError('Invalid value %d for num_loops' % num_loops)\n",
    "\n",
    "    return self.predict_labels(dists, k=k)\n",
    "\n",
    "  def compute_distances_two_loops(self, X):\n",
    "    \"\"\"\n",
    "    Compute the distance between each test point in X and each \n",
    "    training point in self.X_train using a nested loop over both \n",
    "    the training data and the test data.\n",
    "\n",
    "    Inputs:\n",
    "    - X: A numpy array of shape (num_test, D) containing test data.\n",
    "\n",
    "    Returns:\n",
    "    - dists: A numpy array of shape (num_test, num_train) where \n",
    "      dists[i, j] is the Euclidean distance between the ith test \n",
    "      point and the jth training point.\n",
    "    \"\"\"\n",
    "    num_test = X.shape[0]\n",
    "    num_train = self.X_train.shape[0]\n",
    "    dists = np.zeros((num_test, num_train))\n",
    "    X = X.astype('float')\n",
    "    for i in range(num_test):\n",
    "      for j in range(num_train):\n",
    "          dists[i, j] = np.sqrt(np.sum(np.square(self.X_train[j,:] - X[i,:])))\n",
    "        \n",
    "    return dists\n",
    "\n",
    "  def compute_distances_one_loop(self, X):\n",
    "    \"\"\"\n",
    "    Compute the distance between each test point in X and each training point\n",
    "    in self.X_train using a single loop over the test data.\n",
    "\n",
    "    Input / Output: Same as compute_distances_two_loops\n",
    "    \"\"\"\n",
    "    num_test = X.shape[0]\n",
    "    num_train = self.X_train.shape[0]\n",
    "    dists = np.zeros((num_test, num_train))\n",
    "    X = X.astype('float')\n",
    "    for i in range(num_test):\n",
    "      dists[i, :] = np.sqrt(np.sum(np.square(self.X_train - X[i,:]), axis = 1))\n",
    "      \n",
    "     \n",
    "    return dists\n",
    "\n",
    "  def compute_distances_no_loops(self, X):\n",
    "    \"\"\"\n",
    "    Compute the distance between each test point in X and each training point\n",
    "    in self.X_train using no explicit loops.\n",
    "\n",
    "    Input / Output: Same as compute_distances_two_loops\n",
    "    \"\"\"\n",
    "    num_test = X.shape[0]\n",
    "    num_train = self.X_train.shape[0]\n",
    "    dists = np.zeros((num_test, num_train)) \n",
    "    X=X.astype('float')\n",
    "    \n",
    "    # Most \"elegant\" solution leads however to memory issues\n",
    "    # dists = np.sqrt(np.square((self.X_train[:, np.newaxis, :] - X)).sum(axis=2)).T\n",
    "    # split (p-q)^2 to p^2 + q^2 - 2pq\n",
    "    dists = np.sqrt((X**2).sum(axis=1)[:, np.newaxis] + (self.X_train**2).sum(axis=1) - 2 * X.dot(self.X_train.T))\n",
    "                     \n",
    "    \n",
    "    \n",
    "    return dists\n",
    "\n",
    "  def predict_labels(self, dists, k=1):\n",
    "    \"\"\"\n",
    "    Given a matrix of distances between test points and training points,\n",
    "    predict a label for each test point.\n",
    "\n",
    "    Inputs:\n",
    "    - dists: A numpy array of shape (num_test, num_train) where dists[i, j]\n",
    "      gives the distance betwen the ith test point and the jth training point.\n",
    "\n",
    "    Returns:\n",
    "    - y: A numpy array of shape (num_test,) containing predicted labels for the\n",
    "      test data, where y[i] is the predicted label for the test point X[i].  \n",
    "    \"\"\"\n",
    "    num_test = dists.shape[0]\n",
    "    y_pred = np.zeros(num_test, dtype='float64')\n",
    "    for i in range(num_test):\n",
    "        # A list of length k storing the labels of the k nearest neighbors to\n",
    "        # the ith test point.\n",
    "        closest_y = []\n",
    "        # get the k indices with smallest distances\n",
    "        min_indices = np.argsort(dists[i,:])[:k] \n",
    "        closest_y = np.bincount(self.y_train[min_indices])\n",
    "        # predict the label of the nearest example\n",
    "        y_pred[i] = np.argmax(closest_y)  \n",
    "\n",
    "    return y_pred"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Methods within a class are defined in much the same way as functions, that is, using `def`. Every defined class has a _special method_ called `__init__()`  `Python` runs automatically whenever we create a new _instance_ based on the `NearestNeighbor` \n",
    "class. The `self` parameter is required in the method definition, and it must come first \n",
    "before the other parameters. It must be included in the definition because when `Python` \n",
    "calls this `__init__` method later (to create an instance of `NearestNeighbor`), \n",
    "the method call will automatically pass the `self` argument. Every method call associated with a class automatically passes `self`, which is a reference to the instance itself; \n",
    "it gives the individual instance access to the attributes and methods in the class. In summary, when you invoke a class method on an object instance, `Python` \n",
    "arranges for the first argument to be the invoking object instance, which is always \n",
    "assigned to each method's `self` argument.\n",
    "\n",
    "- The two variables `self.X_train` and `self.y_train` each have the prefix `self`. Any variable prefixed with `self` is available to every method in the class, and we will also be able to access these variables through any instance created from the class. `self.X_train = X` takes the value stored in the parameter `X` and stores it in the variable `self.X_train`, which is then attached to the instance being created. The same process happens with `self.y_train = y`. \n",
    "\n",
    "- Variables that are accessible through instances like this are called _attributes_.\n",
    "`np.zeros` produces an array of $ 0 $'s, here the size is `num_test`.\n",
    "\n",
    "- `np.sum` returns the sum of all elements in the array or along an axis. Zero-length \n",
    "arrays have sum $ $ 0.\n",
    "\n",
    "- `np.argmin` returns the index of minimum element.\n",
    "\n",
    "- When Python reads the line `nn = NearestNeighbor()`, it calls the `__init__()` method in `NearestNeighbor()`. The `__init__()` method creates an instance representing this particular nearest neighbor classifier. The `__init__()` method has no explicit return statement, but Python automatically returns an instance representing this nearest neighbor classifier. We store that instance in the variable `nn`. The naming convention is helpful here: we can usually assume that a capitalized name like `NearestNeighbor()` refers to a class, and a lowercase name like `nn` refers to a single instance created from a class.\n",
    "\n",
    "\n",
    "- `np.argsort` returns the indices that would sort an array.\n",
    "\n",
    "- `np.bincount(x)` counts the number of occurrences of each value in an array of non-negative integers. The number of bins (of size 1) is one larger than the largest value in $ x $.\n",
    "\n",
    "- Instead of a loop that contains a _broadcasting_ process with a 2D array \n",
    "\n",
    "`for i in range(num_test):\n",
    "      dists[i, :] = np.sqrt(np.sum(np.square(self.X_train - X[i,:]), axis = 1))`\n",
    "\n",
    "we can speed up this process by broadcasting with a 3D array \n",
    "\n",
    "`dists = np.sqrt(np.square((self.X_train[:, np.newaxis, :] - X)).sum(axis=2))`\n",
    "\n",
    "- The _Broadcasting rule_ states: two arrays are compatible for broadcasting if for each \n",
    "_trailing dimension_ (that is, starting from the end of an array), the axis lengths match or if either of the lengths is 1. In the case of `self._train[:, np.newaxis, :]`, the trailing dimension is $2$ and the axis length $D$. The trailing dimension of `X` is 1 and has axis length $D$. Thus, they match. Broadcasting is then performed over the missing and / or length $ 1 $ dimensions. If we need to add a new axis with length $ 1 $ specifically for broadcasting purposes, `NumPy` arrays offer a special syntax for inserting new axes by indexing. We use the special `np.newaxis` attribute along with full slices to insert the new axis. We may imagine that `num_test` copies of `self.X_train` are tiled up along `axis=1` of `self.X_train[:, np.newaxis, :]`. On the other hand, `num_train` copies of `X` are tiled up on top of each other. First, the subtraction is performed along `axis=2`. Then, it is performed along `axis=1`, and finally over `axis=0`. The resulting shape of the subtraction then is (`num_train`, `num_test`, D). Since this runs into memory issues, we need to rewrite it as follows:\n",
    "\n",
    "`dists = np.sqrt((X**2).sum(axis=1)[:, np.newaxis] + (self.X_train**2).sum(axis=1) - 2 * X.dot(self.X_train.T))`\n",
    "\n",
    "which yields an array with shape (`num_test`, `num_train`, D)\n",
    "\n",
    "- It is important to cast the data files as `float`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "91c8998c-f531-4774-98ca-6c9631050fd3"
    }
   },
   "source": [
    "Create an instance nn from the class KNearestNeighbor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "215be79c-8fe0-4e10-9587-6bea172bb33a"
    }
   },
   "outputs": [],
   "source": [
    "classifier = KNearestNeighbor()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2f886096-8250-4739-8645-37950f408d41"
    }
   },
   "source": [
    "We call the method `train` of the `KNearestNeighbor` class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "de24c3a8-0860-446e-b974-3e0c334feced"
    }
   },
   "outputs": [],
   "source": [
    "classifier.train(X_train, y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d058a8de-3c50-4514-8405-5aff67b26398"
    }
   },
   "source": [
    "We test our implementation with two_loops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "d87bb3a8-6338-4957-ac73-4c81b87821eb"
    }
   },
   "outputs": [],
   "source": [
    "dists = classifier.compute_distances_two_loops(X_test)\n",
    "dists.shape  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "c1277b26-a267-4dec-ab9d-e44d31cdaa3e"
    }
   },
   "source": [
    "We can visualize the distance matrix: each row is a single test example and its distances to training examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "ae3a05a2-a3e6-4e65-a59f-0204411f57f9"
    }
   },
   "outputs": [],
   "source": [
    "plt.imshow(dists, interpolation='none')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7855beeb-d7e2-4ea7-994f-1adfa5a2c886"
    }
   },
   "source": [
    "Let us now predict labels and run the code below: We use $k = 1$ (which is Nearest Neighbor)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "219d7522-e633-4136-aa98-9abe80ca7bf3"
    }
   },
   "outputs": [],
   "source": [
    "y_test_pred = classifier.predict_labels(dists, k=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f083926f-4bd0-488f-8ba9-e77dc946fac8"
    }
   },
   "source": [
    "We compute and print the fraction of correctly predicted examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "f1ac90b4-5005-4940-9663-0bfd9574dc8c"
    }
   },
   "outputs": [],
   "source": [
    "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))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7a33b48c-c106-4903-ba68-769ce91ccb8b"
    }
   },
   "source": [
    " Let us now predict labels and run the code below: We use k = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "7a4433f3-d7d4-4b7c-bd21-6f6d5272c837"
    }
   },
   "outputs": [],
   "source": [
    "y_test_pred = classifier.predict_labels(dists, k=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "8cede653-c157-4396-a534-b4a8741251e2"
    }
   },
   "source": [
    "We compute and print the fraction of correctly predicted examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "445220c9-4974-41a0-a36c-a309d395490b"
    }
   },
   "outputs": [],
   "source": [
    "num_correct = np.sum(y_test_pred == y_test)\n",
    "accuracy = float(num_correct) / len(y_test_pred)\n",
    "print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Confusion Matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# utility function for plotting confusion matrix\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from sklearn.metrics import confusion_matrix\n",
    "\n",
    "def plot_confmat(y_true, y_pred):\n",
    "    \"\"\"\n",
    "    Plot the confusion matrix and save to user_files dir\n",
    "    \"\"\"\n",
    "    conf_matrix = confusion_matrix(y_true, y_pred)\n",
    "    fig = plt.figure(figsize=(9,9))\n",
    "    ax = fig.add_subplot(111)\n",
    "    sns.heatmap(conf_matrix,\n",
    "                annot=True,\n",
    "                fmt='.0f')\n",
    "    plt.title('Confusion matrix')\n",
    "    ax.set_xticklabels( classes)\n",
    "    ax.set_yticklabels( classes)\n",
    "    plt.ylabel('True')\n",
    "    plt.xlabel('Predicted')\n",
    "    \n",
    "plot_confmat(y_test, y_test_pred)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "df615e0b-aeeb-4074-abef-075af4118640"
    }
   },
   "source": [
    "## Algebra and Performance of Distance Matrix Computation\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "04f92811-3067-4a08-8227-ed55c42fed50"
    }
   },
   "source": [
    "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."
   ]