csci677_assignment_1_1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "collapsed_sections": [
        "Sp9dU9BxtSsd"
      ],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/ERGOWHO/cs677/blob/main/csci677_assignment_1_1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Introduction\n",
        "\n",
        "In this assignment you will practice putting together a simple image classification pipeline based on the k-Nearest Neighbor or the SVM/Softmax classifier for [CIFAR-10](https://www.cs.toronto.edu/~kriz/cifar.html) dataset. The goals of this assignment are as follows:\n",
        "\n",
        "\n",
        "\n",
        "*   Understand the basic Image Classification pipeline and the data-driven approach (train/predict stages).\n",
        "*   Understand the train/val/test splits and the use of validation data for hyperparameter tuning.\n",
        "*   Implement and apply a k-Nearest Neighbor (kNN) classifier.\n",
        "*   Implement and apply a Multiclass Support Vector Machine (SVM) classifier.\n",
        "*   Implement and apply a Softmax classifier.\n",
        "*   Understand the differences and tradeoffs between these classifiers.\n",
        "\n",
        "Please fill in all the **TODO** code blocks. Once you are ready to submit:\n",
        "\n",
        "* Export the notebook `CSCI677_assignment_1.ipynb` as a PDF `[Your USC ID]_CSCI677_assignment_1.pdf`\n",
        "* Submit your PDF file through [Blackboard](https://blackboard.usc.edu/)\n",
        "\n",
        "Please make sure that the notebook have been run before exporting PDF, and your code and all cell outputs are visible in the your submitted PDF. Regrading request will not be accepted if your code/output is not visible in the original submission. Thank you!"
      ],
      "metadata": {
        "id": "u93YJyjNB9WK"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Data Preparation**\n",
        "\n",
        "[CIFAR-10](https://www.cs.toronto.edu/~kriz/cifar.html) is a well known dataset composed of 60,000 colored 32x32 images. The utility function `cifar10()` returns the entire CIFAR-10 dataset as a set of four Torch tensors:\n",
        "* `x_train` contains all training images (real numbers in the range  [0,1] )\n",
        "* `y_train` contains all training labels (integers in the range  [0,9] )\n",
        "* `x_test` contains all test images\n",
        "* `y_test` contains all test labels\n",
        "\n",
        "This function automatically downloads the CIFAR-10 dataset the first time you run it."
      ],
      "metadata": {
        "id": "5_7K_0sWz0OZ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import os\n",
        "import torch\n",
        "from torchvision.datasets import CIFAR10\n",
        "\n",
        "def _extract_tensors(dset, num=None):\n",
        "    x = torch.tensor(dset.data, dtype=torch.float32).permute(0, 3, 1, 2).div_(255)\n",
        "    y = torch.tensor(dset.targets, dtype=torch.int64)\n",
        "    if num is not None:\n",
        "        if num <= 0 or num > x.shape[0]:\n",
        "          raise ValueError('Invalid value num=%d; must be in the range [0, %d]'\n",
        "                          % (num, x.shape[0]))\n",
        "        x = x[:num].clone()\n",
        "        y = y[:num].clone()\n",
        "    return x, y\n",
        "\n",
        "def cifar10(num_train=None, num_test=None):\n",
        "    download = not os.path.isdir('cifar-10-batches-py')\n",
        "    dset_train = CIFAR10(root='.', download=download, train=True)\n",
        "    dset_test = CIFAR10(root='.', train=False)\n",
        "    x_train, y_train = _extract_tensors(dset_train, num_train)\n",
        "    x_test, y_test = _extract_tensors(dset_test, num_test)\n",
        "\n",
        "    return x_train, y_train, x_test, y_test"
      ],
      "metadata": {
        "id": "CVP8si9RpSdc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Our data is going to be stored simply in the four variables: `x_train`, `x_test`, `y_train`, and `y_test`.\n",
        "\n",
        "\n",
        "*   Training set: `x_train` is composed of 50,000 images where `y_train` references the corresponding labels.\n",
        "*   Testing set: `x_test` is composed of 10,000 images where `y_test` references the corresponding labels."
      ],
      "metadata": {
        "id": "Zz09FqISr0c8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "x_train, y_train, x_test, y_test = cifar10()\n",
        "\n",
        "classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']"
      ],
      "metadata": {
        "id": "cILqXrjWpFRa"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# k-Nearest Neighbor (kNN) (30 pts)\n"
      ],
      "metadata": {
        "id": "dr_Wv6Hi3Y_K"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **Subsampling**\n",
        "\n",
        "When implementing machine learning algorithms, it's usually a good idea to use a small sample of the full dataset. This way your code will run much faster, allowing for more interactive and efficient development. Once you are satisfied that you have correctly implemented the algorithm, you can then rerun with the entire dataset."
      ],
      "metadata": {
        "id": "Sp9dU9BxtSsd"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Subsample size\n",
        "num_train = 500\n",
        "num_test = 250\n",
        "\n",
        "# Redeclaring x_train...y_test with subsample\n",
        "x_train, y_train, x_test, y_test = cifar10(num_train, num_test)\n"
      ],
      "metadata": {
        "id": "2HnkODySthr0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Compute Distance (10 pts)\n",
        "\n",
        "Now that we have examined and prepared our data, it is time to implement the kNN classifier. We can break the process down into two steps:\n",
        "1. Compute the (squared Euclidean) distances between all training examples and all test examples\n",
        "2. Given these distances, for each test example find its k nearest neighbors and have them vote for the label to output\n",
        "\n",
        "**NOTE**: When implementing algorithms in PyTorch, it's best to avoid loops in Python if possible. Instead it is preferable to implement your computation so that all loops happen inside PyTorch functions. This will usually be much faster than writing your own loops in Python, since PyTorch functions can be internally optimized to iterate efficiently, possibly using multiple threads. This is especially important when using a GPU to accelerate your code."
      ],
      "metadata": {
        "id": "2hPrEvn9FSPf"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def compute_distances(x_train, x_test):\n",
        "    \"\"\"\n",
        "    Inputs:\n",
        "    x_train: shape (num_train, C, H, W) tensor.\n",
        "    x_test: shape (num_test, C, H, W) tensor.\n",
        "\n",
        "    Returns:\n",
        "    dists: shape (num_train, num_test) tensor where dists[j, i] is the\n",
        "        Euclidean distance between the ith training image and the jth test\n",
        "        image.\n",
        "    \"\"\"\n",
        "\n",
        "    # Get the number of training and testing images\n",
        "    num_train = x_train.shape[0]\n",
        "    num_test = x_test.shape[0]\n",
        "\n",
        "    # dists will be the tensor housing all distance measurements between testing and training\n",
        "    dists = x_train.new_zeros(num_train, num_test)\n",
        "\n",
        "    # Flatten tensors\n",
        "    train = x_train.flatten(1)\n",
        "    test = x_test.flatten(1)\n",
        "\n",
        "    #######################################################################\n",
        "    # TODO (10 pts):\n",
        "    # find the Euclidean distance between testing and training images,\n",
        "    # and save the computed distance in dists.\n",
        "    #######################################################################\n",
        "\n",
        "    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "    train_norms = (train * train).sum(dim=1).reshape(-1, 1)\n",
        "    test_norms = (test * test).sum(dim=1)\n",
        "    dists = train_norms + test_norms - 2 * train.mm(test.t())\n",
        "    dists = torch.sqrt(torch.clamp(dists, min=0.0))\n",
        "    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "    return dists"
      ],
      "metadata": {
        "id": "rxg2Aq1pt9fy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Implement kNN (10 pts)\n",
        "\n",
        "The kNN classifier consists of two stages:\n",
        "\n",
        "*   Training: the classifier takes the training data and simply remembers it\n",
        "*   Testing: kNN classifies every test image by comparing to all training images and transfering the labels of the k most similar training examples"
      ],
      "metadata": {
        "id": "v1i6QyD4j6bB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class KnnClassifier:\n",
        "    def __init__(self, x_train, y_train):\n",
        "        \"\"\"\n",
        "        x_train: shape (num_train, C, H, W) tensor where num_train is batch size,\n",
        "          C is channel size, H is height, and W is width.\n",
        "        y_train: shape (num_train) tensor where num_train is batch size providing labels\n",
        "        \"\"\"\n",
        "\n",
        "        self.x_train = x_train\n",
        "        self.y_train = y_train\n",
        "\n",
        "    def predict(self, x_test, k=1):\n",
        "        \"\"\"\n",
        "        x_test: shape (num_test, C, H, W) tensor where num_test is batch size,\n",
        "          C is channel size, H is height, and W is width.\n",
        "        k: The number of neighbors to use for prediction\n",
        "        \"\"\"\n",
        "\n",
        "        # Init output shape\n",
        "        y_test_pred = torch.zeros(x_test.shape[0], dtype=torch.int64)\n",
        "\n",
        "        # Find & store Euclidean distance between test & train\n",
        "        dists = compute_distances(self.x_train, x_test)\n",
        "\n",
        "        #######################################################################\n",
        "        # TODO (10 pts):\n",
        "        # The goal is to return a tensor y_test_pred where the ith index\n",
        "        # is the assigned label to ith test image by the kNN algorithm.\n",
        "        #######################################################################\n",
        "\n",
        "        # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "        for i in range(x_test.shape[0]):\n",
        "          k_nearest_neighbors = dists[:, i].argsort()[:k]\n",
        "          k_nearest_labels = self.y_train[k_nearest_neighbors]\n",
        "          y_test_pred[i] = k_nearest_labels.mode()[0]\n",
        "        # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "        return y_test_pred\n",
        "\n",
        "    def check_accuracy(self, x_test, y_test, k=1, quiet=False):\n",
        "        \"\"\"\n",
        "        x_test: shape (num_test, C, H, W) tensor where num_test is batch size,\n",
        "          C is channel size, H is height, and W is width.\n",
        "        y_test: shape (num_test) tensor where num_test is batch size providing labels\n",
        "        k: The number of neighbors to use for prediction\n",
        "        quiet: If True, don't print a message.\n",
        "\n",
        "        Returns:\n",
        "        accuracy: Accuracy of this classifier on the test data, as a percent.\n",
        "          Python float in the range [0, 100]\n",
        "        \"\"\"\n",
        "\n",
        "        y_test_pred = self.predict(x_test, k=k)\n",
        "        num_samples = x_test.shape[0]\n",
        "        num_correct = (y_test == y_test_pred).sum().item()\n",
        "        accuracy = 100.0 * num_correct / num_samples\n",
        "        msg = (f'Got {num_correct} / {num_samples} correct; '\n",
        "              f'accuracy is {accuracy:.2f}%')\n",
        "        if not quiet:\n",
        "          print(msg)\n",
        "        return accuracy"
      ],
      "metadata": {
        "id": "UrYRDVcuuL8m"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "We've finished implementing kNN and can begin testing the algorithm on larger portions of the dataset to see how well it performs."
      ],
      "metadata": {
        "id": "FpaBIPfczlo5"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "torch.manual_seed(0)\n",
        "num_train = 5000\n",
        "num_test = 500\n",
        "x_train, y_train, x_test, y_test = cifar10(num_train, num_test)\n",
        "\n",
        "classifier = KnnClassifier(x_train, y_train)\n",
        "classifier.check_accuracy(x_test, y_test, k=5)"
      ],
      "metadata": {
        "id": "eXqBT2ZnzDFq",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3618e9f9-accf-4e1d-93b7-3e768ecacb8d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Got 139 / 500 correct; accuracy is 27.80%\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "27.8"
            ]
          },
          "metadata": {},
          "execution_count": 490
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Cross-validation (10 pts)\n",
        "\n",
        "As our algorithm currently exists, we have to manually tune the hyperparameter $k$ to some integer value, which raises the question - is that the best value for $k$? Cross validation is a procedure to automate selecting an optimal value for $k$.\n",
        "\n"
      ],
      "metadata": {
        "id": "P7UIMKl94dGl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def knn_cross_validate(x_train, y_train, num_folds=5, k_choices=None):\n",
        "    \"\"\"\n",
        "    Inputs:\n",
        "    x_train: Tensor of shape (num_train, C, H, W) giving all training data\n",
        "    y_train: int64 tensor of shape (num_train,) giving labels for training data\n",
        "    num_folds: Integer giving the number of folds to use\n",
        "    k_choices: List of integers giving the values of k to try\n",
        "\n",
        "    Returns:\n",
        "    k_to_accuracies: Dictionary mapping values of k to lists, where\n",
        "        k_to_accuracies[k][i] is the accuracy on the ith fold of a KnnClassifier\n",
        "        that uses k nearest neighbors.\n",
        "    \"\"\"\n",
        "    # Create a list of k's for testing\n",
        "    if k_choices is None:\n",
        "        k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]\n",
        "\n",
        "    # Create empty lists to house the chunks for cross validation\n",
        "    x_train_folds = []\n",
        "    y_train_folds = []\n",
        "\n",
        "    # Flatten x_train from [5000, 3, 32, 32] to [5000, 3072]\n",
        "    x_train_flat = x_train.view(x_train.shape[0], -1)\n",
        "\n",
        "    # Partition our training set to 5 tensors of training images of shape [1000, 3072] and 5 labels of shape [1000]\n",
        "    x_train_folds = torch.chunk(x_train_flat, num_folds, dim=0)\n",
        "    y_train_folds = torch.chunk(y_train, num_folds, dim=0)\n",
        "\n",
        "    # Create object to house the combination of accuracies for different values k for different validation sets\n",
        "    k_to_accuracies = {}\n",
        "\n",
        "    #######################################################################\n",
        "    # TODO (10 pts):\n",
        "    # Iterate through every combination of k_choices and possible validation sets\n",
        "    # Return k_to_accuracies: Dictionary mapping values of k to lists\n",
        "    #######################################################################\n",
        "\n",
        "    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "    for k in k_choices:\n",
        "        k_to_accuracies[k] = []\n",
        "\n",
        "        for i in range(num_folds):\n",
        "            x_train_tmp = torch.cat([fold for j, fold in enumerate(x_train_folds) if j != i])\n",
        "            y_train_tmp = torch.cat([fold for j, fold in enumerate(y_train_folds) if j != i])\n",
        "\n",
        "            x_val_tmp = x_train_folds[i]\n",
        "            y_val_tmp = y_train_folds[i]\n",
        "\n",
        "\n",
        "            classifier = KnnClassifier(x_train_tmp.view(-1, 3, 32, 32), y_train_tmp)\n",
        "\n",
        "            accuracy = classifier.check_accuracy(x_val_tmp.view(-1, 3, 32, 32), y_val_tmp, k=k, quiet=True)\n",
        "            k_to_accuracies[k].append(accuracy)\n",
        "    return k_to_accuracies\n",
        "    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "\n",
        "def knn_get_best_k(k_to_accuracies):\n",
        "    \"\"\"\n",
        "    Inputs:\n",
        "    - k_to_accuracies: Dictionary mapping values of k to lists, where\n",
        "    k_to_accuracies[k][i] is the accuracy on the ith fold of a KnnClassifier\n",
        "    that uses k nearest neighbors.\n",
        "\n",
        "    Returns:\n",
        "    - best_k: best (and smallest if there is a conflict) k value based on\n",
        "    the k_to_accuracies info\n",
        "    \"\"\"\n",
        "    # Create best_k variable to return optimal k\n",
        "    best_k = 0\n",
        "\n",
        "    # Get keys and values from k_to_accuracies object\n",
        "    keys = [k for k in k_to_accuracies.keys()]\n",
        "    values = [v for v in k_to_accuracies.values()]\n",
        "\n",
        "    # Get largest average of all the values\n",
        "    max_avg = torch.argmax(torch.mean(torch.tensor(values), dim=1))\n",
        "    # Get corresponding k for max_avg\n",
        "    best_k = keys[max_avg]\n",
        "\n",
        "    return best_k\n"
      ],
      "metadata": {
        "id": "j5s666ygulBQ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now we can use the results of cross-validation to select the best value for $k$, and rerun the classifier on our full 5000 set of training examples."
      ],
      "metadata": {
        "id": "ZCVO-uUV4kU_"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "torch.manual_seed(0)\n",
        "\n",
        "k_to_accuracies = knn_cross_validate(x_train, y_train, num_folds=5)\n",
        "\n",
        "for k, accs in sorted(k_to_accuracies.items()):\n",
        "  print('k = %d got accuracies: %r' % (k, accs))\n",
        "\n",
        "best_k = knn_get_best_k(k_to_accuracies)\n",
        "print('Best k is ', best_k)\n",
        "\n",
        "classifier = KnnClassifier(x_train, y_train)\n",
        "classifier.check_accuracy(x_test, y_test, k=best_k)"
      ],
      "metadata": {
        "id": "mD5VXkEM5_ro",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "957f6597-a4ba-4fbe-8f82-1882b396045e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "k = 1 got accuracies: [26.3, 25.7, 26.4, 27.8, 26.6]\n",
            "k = 3 got accuracies: [23.9, 24.9, 24.0, 26.6, 25.4]\n",
            "k = 5 got accuracies: [24.8, 26.6, 28.0, 29.2, 28.0]\n",
            "k = 8 got accuracies: [26.2, 28.2, 27.3, 29.0, 27.3]\n",
            "k = 10 got accuracies: [26.5, 29.6, 27.6, 28.4, 28.0]\n",
            "k = 12 got accuracies: [26.0, 29.5, 27.9, 28.3, 28.0]\n",
            "k = 15 got accuracies: [25.2, 28.9, 27.8, 28.2, 27.4]\n",
            "k = 20 got accuracies: [27.0, 27.9, 27.9, 28.2, 28.5]\n",
            "k = 50 got accuracies: [27.1, 28.8, 27.8, 26.9, 26.6]\n",
            "k = 100 got accuracies: [25.6, 27.0, 26.3, 25.6, 26.3]\n",
            "Best k is  10\n",
            "Got 141 / 500 correct; accuracy is 28.20%\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "28.2"
            ]
          },
          "metadata": {},
          "execution_count": 492
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Define a General Classifier Class (20 pts)"
      ],
      "metadata": {
        "id": "B8Pr5Oh5rlUq"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Before implementing Support Vector Machine (SVM) and Softmax Classifier. We define a general classifier class that contains the following main functions:\n",
        "\n",
        "\n",
        "1.   `train`: train this linear classifier using stochastic gradient descent.\n",
        "2.   `predict`: use the trained weights of this linear classifier to predict labels for data points.\n",
        "3.   `loss`: compute the loss function and its derivative.\n",
        "\n",
        "We will define SVM and Softmax classifier as subclasses of this general linear classifier class. Subclasses will override the `loss` function.\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "7fZSgxj-s_jf"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "\n",
        "class LinearClassifier(object):\n",
        "    def __init__(self):\n",
        "        self.W = None\n",
        "\n",
        "    def train(\n",
        "        self,\n",
        "        X,\n",
        "        y,\n",
        "        learning_rate=1e-3,\n",
        "        reg=1e-5,\n",
        "        num_iters=100,\n",
        "        batch_size=200,\n",
        "        verbose=False,\n",
        "    ):\n",
        "        \"\"\"\n",
        "        Train this linear classifier using stochastic gradient descent.\n",
        "\n",
        "        Inputs:\n",
        "        - X: A numpy array of shape (N, D) containing training data; there are N\n",
        "          training samples each of dimension D.\n",
        "        - y: A numpy array of shape (N,) containing training labels; y[i] = c\n",
        "          means that X[i] has label 0 <= c < C for C classes.\n",
        "        - learning_rate: (float) learning rate for optimization.\n",
        "        - reg: (float) regularization strength.\n",
        "        - num_iters: (integer) number of steps to take when optimizing\n",
        "        - batch_size: (integer) number of training examples to use at each step.\n",
        "        - verbose: (boolean) If true, print progress during optimization.\n",
        "\n",
        "        Outputs:\n",
        "        A list containing the value of the loss function at each training iteration.\n",
        "        \"\"\"\n",
        "        num_train, dim = X.shape\n",
        "        num_classes = (\n",
        "            np.max(y) + 1\n",
        "        )  # assume y takes values 0...K-1 where K is number of classes\n",
        "        if self.W is None:\n",
        "            # lazily initialize W\n",
        "            self.W = 0.001 * np.random.randn(dim, num_classes)\n",
        "\n",
        "        # Run stochastic gradient descent to optimize W\n",
        "        loss_history = []\n",
        "        for it in range(num_iters):\n",
        "            X_batch = None\n",
        "            y_batch = None\n",
        "\n",
        "            #########################################################################\n",
        "            # TODO (10 pts):                                                        #\n",
        "            # Sample batch_size elements from the training data and their           #\n",
        "            # corresponding labels to use in this round of gradient descent.        #\n",
        "            # Store the data in X_batch and their corresponding labels in           #\n",
        "            # y_batch; after sampling X_batch should have shape (batch_size, dim)   #\n",
        "            # and y_batch should have shape (batch_size,)                           #\n",
        "            #                                                                       #\n",
        "            # Hint: Use np.random.choice to generate indices. Sampling with         #\n",
        "            # replacement is faster than sampling without replacement.              #\n",
        "            #########################################################################\n",
        "            # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "            indices = np.random.choice(num_train, batch_size, replace=True)\n",
        "            X_batch = X[indices]\n",
        "            y_batch = y[indices]\n",
        "\n",
        "            # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "            # evaluate loss and gradient\n",
        "            loss, grad = self.loss(X_batch, y_batch, reg)\n",
        "            loss_history.append(loss)\n",
        "\n",
        "            # perform parameter update\n",
        "            #########################################################################\n",
        "            # TODO (5 pts):                                                         #\n",
        "            # Update the weights using the gradient and the learning rate.          #\n",
        "            #########################################################################\n",
        "            # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "            self.W -= learning_rate * grad\n",
        "            # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "            if verbose and it % 100 == 0:\n",
        "                print(\"iteration %d / %d: loss %f\" % (it, num_iters, loss))\n",
        "\n",
        "        return loss_history\n",
        "\n",
        "    def predict(self, X):\n",
        "        \"\"\"\n",
        "        Use the trained weights of this linear classifier to predict labels for\n",
        "        data points.\n",
        "\n",
        "        Inputs:\n",
        "        - X: A numpy array of shape (N, D) containing training data; there are N\n",
        "          training samples each of dimension D.\n",
        "\n",
        "        Returns:\n",
        "        - y_pred: Predicted labels for the data in X. y_pred is a 1-dimensional\n",
        "          array of length N, and each element is an integer giving the predicted\n",
        "          class.\n",
        "        \"\"\"\n",
        "        y_pred = np.zeros(X.shape[0])\n",
        "        ###########################################################################\n",
        "        # TODO (5 pts):                                                           #\n",
        "        # Implement this method. Store the predicted labels in y_pred.            #\n",
        "        ###########################################################################\n",
        "        # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "        scores = X.dot(self.W)\n",
        "        y_pred = np.argmax(scores, axis=1)\n",
        "\n",
        "        # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "        return y_pred\n",
        "\n",
        "    def loss(self, X_batch, y_batch, reg):\n",
        "        \"\"\"\n",
        "        Compute the loss function and its derivative.\n",
        "        Subclasses will override this.\n",
        "\n",
        "        Inputs:\n",
        "        - X_batch: A numpy array of shape (N, D) containing a minibatch of N\n",
        "          data points; each point has dimension D.\n",
        "        - y_batch: A numpy array of shape (N,) containing labels for the minibatch.\n",
        "        - reg: (float) regularization strength.\n",
        "\n",
        "        Returns: A tuple containing:\n",
        "        - loss as a single float\n",
        "        - gradient with respect to self.W; an array of the same shape as W\n",
        "        \"\"\"\n",
        "        pass"
      ],
      "metadata": {
        "id": "O0Id2-q_QF02"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Multiclass Support Vector Machine (SVM) (30 pts)\n",
        "\n"
      ],
      "metadata": {
        "id": "JcO2mGt3NQ9n"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "[Support vector machines (SVMs)](https://scikit-learn.org/stable/modules/svm.html) are a set of supervised learning methods used for classification.\n",
        "\n",
        "The advantages of support vector machines are:\n",
        "\n",
        "* Effective in high dimensional spaces.\n",
        "* Still effective in cases where number of dimensions is greater than the number of samples.\n",
        "* Uses a subset of training points in the decision function (called support vectors), so it is also memory efficient.\n",
        "* Versatile: different Kernel functions can be specified for the decision function. Common kernels are provided, but it is also possible to specify custom kernels.\n",
        "\n",
        "The disadvantages of support vector machines include:\n",
        "\n",
        "* If the number of features is much greater than the number of samples, avoid over-fitting in choosing Kernel functions and regularization term is crucial.\n",
        "* SVMs do not directly provide probability estimates, these are calculated using an expensive five-fold cross-validation (see Scores and probabilities, below).\n",
        "\n",
        "In this section, we will first implement the loss function for SVM and use the validation set to tune hyperparameters.\n",
        "\n",
        "**NOTE:** please use [numpy](https://numpy.org/), please do not use [scikit-learn](https://scikit-learn.org/stable/), [PyTorch](https://pytorch.org/) or other libraries."
      ],
      "metadata": {
        "id": "c3_Z4W_ZH59m"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Loss Function (20 pts)\n",
        "\n",
        "We first structure the loss function for SVM. For detailed explanations of SVM loss, please check out [this reading material](https://cs231n.github.io/linear-classify/#loss-function)."
      ],
      "metadata": {
        "id": "l2ajMlXEIjWz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import time\n",
        "import numpy as np\n",
        "\n",
        "def svm_loss(W, X, y, reg):\n",
        "    \"\"\"\n",
        "    Structured SVM loss function implementation.\n",
        "\n",
        "    Inputs have dimension D, there are C classes, and we operate on minibatches\n",
        "    of N examples.\n",
        "\n",
        "    Inputs:\n",
        "    - W: A numpy array of shape (D, C) containing weights.\n",
        "    - X: A numpy array of shape (N, D) containing a minibatch of data.\n",
        "    - y: A numpy array of shape (N,) containing training labels; y[i] = c means\n",
        "      that X[i] has label c, where 0 <= c < C.\n",
        "    - reg: (float) regularization strength\n",
        "\n",
        "    Returns a tuple of:\n",
        "    - loss as single float\n",
        "    - gradient with respect to weights W; an array of same shape as W\n",
        "    \"\"\"\n",
        "    loss = 0.0\n",
        "    dW = np.zeros(W.shape)  # initialize the gradient as zero\n",
        "\n",
        "    #############################################################################\n",
        "    # TODO (10 pts):                                                            #\n",
        "    # Implement a vectorized version of the structured SVM loss, storing the    #\n",
        "    # result in loss.                                                           #\n",
        "    #############################################################################\n",
        "    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "    num_train = X.shape[0]\n",
        "\n",
        "    scores = X.dot(W)\n",
        "\n",
        "    correct_scores = scores[np.arange(num_train), y]\n",
        "    correct_scores = correct_scores[:, np.newaxis]\n",
        "\n",
        "    margins = np.maximum(0, scores - correct_scores + 1)\n",
        "\n",
        "    margins[np.arange(num_train), y] = 0\n",
        "\n",
        "    loss = np.sum(margins) / num_train\n",
        "    loss += 0.5 * reg * np.sum(W * W)\n",
        "    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "    #############################################################################\n",
        "    # TODO (10 pts):                                                            #\n",
        "    # Implement a vectorized version of the gradient for the structured SVM     #\n",
        "    # loss, storing the result in dW.                                           #\n",
        "    #                                                                           #\n",
        "    # Hint: Instead of computing the gradient from scratch, it may be easier    #\n",
        "    # to reuse some of the intermediate values that you used to compute the     #\n",
        "    # loss.                                                                     #\n",
        "    #############################################################################\n",
        "    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "    binary_margins = margins\n",
        "    binary_margins[margins > 0] = 1\n",
        "    row_sum = np.sum(binary_margins, axis=1)\n",
        "    binary_margins[np.arange(num_train), y] = -row_sum\n",
        "    dW = X.T.dot(binary_margins) / num_train + reg * W\n",
        "\n",
        "    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "    return loss, dW\n"
      ],
      "metadata": {
        "id": "edfvcABEN_np"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Before we test our implementation of SVM loss function, we need to first convert the previously loaded CIFAR-10 dataset from PyTorch tensors into NumPy array, split the data into train, val and test sets, and preprocess the images."
      ],
      "metadata": {
        "id": "eE7c15PrQdxx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "torch.manual_seed(0)\n",
        "num_train = 50000\n",
        "num_test = 5000\n",
        "x_train, y_train, x_test, y_test = cifar10(num_train, num_test)\n",
        "\n",
        "# Split the data into train, val, and test sets. In addition we will\n",
        "# create a small development set as a subset of the training data;\n",
        "# we can use this for development so our code runs faster.\n",
        "num_training = 49000\n",
        "num_validation = 1000\n",
        "num_test = 1000\n",
        "num_dev = 500\n",
        "\n",
        "x_train_np = x_train.numpy()\n",
        "y_train_np = y_train.numpy()\n",
        "x_test_np = x_test.numpy()\n",
        "y_test_np = y_test.numpy()\n",
        "\n",
        "# Our validation set will be num_validation points from the original\n",
        "# training set.\n",
        "mask = range(num_training, num_training + num_validation)\n",
        "X_val = x_train_np[mask]\n",
        "y_val = y_train_np[mask]\n",
        "\n",
        "# Our training set will be the first num_train points from the original\n",
        "# training set.\n",
        "mask = range(num_training)\n",
        "X_train = x_train_np[mask]\n",
        "y_train = y_train_np[mask]\n",
        "\n",
        "# We will also make a development set, which is a small subset of\n",
        "# the training set.\n",
        "mask = np.random.choice(num_training, num_dev, replace=False)\n",
        "X_dev = x_train_np[mask]\n",
        "y_dev = y_train_np[mask]\n",
        "\n",
        "# We use the first num_test points of the original test set as our\n",
        "# test set.\n",
        "mask = range(num_test)\n",
        "X_test = x_test_np[mask]\n",
        "y_test = y_test_np[mask]\n",
        "\n",
        "# Preprocessing: reshape the image data into rows\n",
        "X_train = np.reshape(X_train, (X_train.shape[0], -1))\n",
        "X_val = np.reshape(X_val, (X_val.shape[0], -1))\n",
        "X_test = np.reshape(X_test, (X_test.shape[0], -1))\n",
        "X_dev = np.reshape(X_dev, (X_dev.shape[0], -1))\n",
        "\n",
        "# As a sanity check, print out the shapes of the data\n",
        "print('Training data shape: ', X_train.shape)\n",
        "print('Validation data shape: ', X_val.shape)\n",
        "print('Test data shape: ', X_test.shape)\n",
        "print('dev data shape: ', X_dev.shape)\n",
        "\n",
        "# Preprocessing: subtract the mean image\n",
        "# first: compute the image mean based on the training data\n",
        "mean_image = np.mean(X_train, axis=0)\n",
        "\n",
        "# second: subtract the mean image from train and test data\n",
        "X_train -= mean_image\n",
        "X_val -= mean_image\n",
        "X_test -= mean_image\n",
        "X_dev -= mean_image\n",
        "\n",
        "# third: append the bias dimension of ones (i.e. bias trick) so that our SVM\n",
        "# only has to worry about optimizing a single weight matrix W.\n",
        "X_train = np.hstack([X_train, np.ones((X_train.shape[0], 1))])\n",
        "X_val = np.hstack([X_val, np.ones((X_val.shape[0], 1))])\n",
        "X_test = np.hstack([X_test, np.ones((X_test.shape[0], 1))])\n",
        "X_dev = np.hstack([X_dev, np.ones((X_dev.shape[0], 1))])\n",
        "\n",
        "print(X_train.shape, X_val.shape, X_test.shape, X_dev.shape)"
      ],
      "metadata": {
        "id": "lOdKZbllQSt-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7085f9d8-50a7-49db-edf7-a7465e54040a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Training data shape:  (49000, 3072)\n",
            "Validation data shape:  (1000, 3072)\n",
            "Test data shape:  (1000, 3072)\n",
            "dev data shape:  (500, 3072)\n",
            "(49000, 3073) (1000, 3073) (1000, 3073) (500, 3073)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now, we can test our implementation of SVM loss."
      ],
      "metadata": {
        "id": "nlw6rH_mQwAa"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# generate a random SVM weight matrix of small numbers\n",
        "W = np.random.randn(3073, 10) * 0.0001\n",
        "\n",
        "tic = time.time()\n",
        "loss, _ = svm_loss(W, X_dev, y_dev, 0.000005)\n",
        "toc = time.time()\n",
        "print('loss: %e computed in %fs' % (loss, toc - tic))"
      ],
      "metadata": {
        "id": "zu2PYRB2QbPC",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6789e24d-b508-41c7-e37a-52b201b65ba5"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "loss: 9.000802e+00 computed in 0.017666s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class LinearSVM(LinearClassifier):\n",
        "    \"\"\" A subclass that uses the Multiclass SVM loss function \"\"\"\n",
        "\n",
        "    def loss(self, X_batch, y_batch, reg):\n",
        "        return svm_loss(self.W, X_batch, y_batch, reg)"
      ],
      "metadata": {
        "id": "zWpju06hQIYX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "svm = LinearSVM()\n",
        "tic = time.time()\n",
        "loss_hist = svm.train(X_train, y_train, learning_rate=1e-7, reg=2.5e4,\n",
        "                      num_iters=1500, verbose=True)\n",
        "toc = time.time()\n",
        "print('That took %fs' % (toc - tic))\n"
      ],
      "metadata": {
        "id": "oFopfak1QPI6",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "efae9a3b-d9ee-4c85-ef8b-300680250798"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "iteration 0 / 1500: loss 390.063601\n",
            "iteration 100 / 1500: loss 239.977485\n",
            "iteration 200 / 1500: loss 149.006800\n",
            "iteration 300 / 1500: loss 93.863941\n",
            "iteration 400 / 1500: loss 60.443459\n",
            "iteration 500 / 1500: loss 40.181883\n",
            "iteration 600 / 1500: loss 27.902043\n",
            "iteration 700 / 1500: loss 20.456265\n",
            "iteration 800 / 1500: loss 15.940348\n",
            "iteration 900 / 1500: loss 13.207344\n",
            "iteration 1000 / 1500: loss 11.548549\n",
            "iteration 1100 / 1500: loss 10.542665\n",
            "iteration 1200 / 1500: loss 9.934569\n",
            "iteration 1300 / 1500: loss 9.564847\n",
            "iteration 1400 / 1500: loss 9.342052\n",
            "That took 8.360579s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "y_train_pred = svm.predict(X_train)\n",
        "print('training accuracy: %f' % (np.mean(y_train == y_train_pred), ))\n",
        "y_val_pred = svm.predict(X_val)\n",
        "print('validation accuracy: %f' % (np.mean(y_val == y_val_pred), ))"
      ],
      "metadata": {
        "id": "HwJY1JLmQeBQ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9a482712-5601-4d14-c707-6f2eadfa1be1"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "training accuracy: 0.231082\n",
            "validation accuracy: 0.248000\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Hyperparameter Tuning (10 pts)\n",
        "\n",
        "Now we use the validation set to tune hyperparameters (regularization strength and learning rate). You should experiment with different ranges for the learning rates and regularization strengths; if you are careful you should be able to get a classification accuracy of about 0.39 (> 0.385) on the validation set.\n",
        "\n",
        "**Note:** you may see runtime/overflow warnings during hyper-parameter search. This may be caused by extreme values, and is not a bug."
      ],
      "metadata": {
        "id": "JlA3kc3BIr2V"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# results is dictionary mapping tuples of the form\n",
        "# (learning_rate, regularization_strength) to tuples of the form\n",
        "# (training_accuracy, validation_accuracy). The accuracy is simply the fraction\n",
        "# of data points that are correctly classified.\n",
        "results = {}\n",
        "best_val = -1   # The highest validation accuracy that we have seen so far.\n",
        "best_svm = None # The LinearSVM object that achieved the highest validation rate.\n",
        "\n",
        "################################################################################\n",
        "# TODO (10 pts):                                                               #\n",
        "# Write code that chooses the best hyperparameters by tuning on the validation #\n",
        "# set. For each combination of hyperparameters, train a linear SVM on the      #\n",
        "# training set, compute its accuracy on the training and validation sets, and  #\n",
        "# store these numbers in the results dictionary. In addition, store the best   #\n",
        "# validation accuracy in best_val and the LinearSVM object that achieves this  #\n",
        "# accuracy in best_svm.                                                        #\n",
        "#                                                                              #\n",
        "# Hint: You should use a small value for num_iters as you develop your         #\n",
        "# validation code so that the SVMs don't take much time to train; once you are #\n",
        "# confident that your validation code works, you should rerun the validation   #\n",
        "# code with a larger value for num_iters.                                      #\n",
        "################################################################################\n",
        "\n",
        "# Provided as a reference. You may or may not want to change these hyperparameters\n",
        "learning_rates = [0.01]\n",
        "regularization_strengths = [0.1]\n",
        "\n",
        "\n",
        "# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "for lr in learning_rates:\n",
        "    for reg in regularization_strengths:\n",
        "        svm = LinearSVM()\n",
        "        svm.train(X_train, y_train, learning_rate=lr, reg=reg, num_iters=5000)\n",
        "\n",
        "        y_train_pred = svm.predict(X_train)\n",
        "        train_accuracy = np.mean(y_train == y_train_pred)\n",
        "\n",
        "        y_val_pred = svm.predict(X_val)\n",
        "        val_accuracy = np.mean(y_val == y_val_pred)\n",
        "\n",
        "        results[(lr, reg)] = (train_accuracy, val_accuracy)\n",
        "\n",
        "        if val_accuracy > best_val:\n",
        "            best_val = val_accuracy\n",
        "            best_svm = svm\n",
        "\n",
        "# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "\n",
        "# Print out results.\n",
        "for lr, reg in sorted(results):\n",
        "    train_accuracy, val_accuracy = results[(lr, reg)]\n",
        "    print('lr %e reg %e train accuracy: %f val accuracy: %f' % (\n",
        "                lr, reg, train_accuracy, val_accuracy))\n",
        "\n",
        "print('best validation accuracy achieved during cross-validation: %f' % best_val)"
      ],
      "metadata": {
        "id": "GII3_6w-QetA",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5cd56633-4126-4749-c931-ccd5c745b2f6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "lr 1.000000e-02 reg 1.000000e-01 train accuracy: 0.397245 val accuracy: 0.406000\n",
            "best validation accuracy achieved during cross-validation: 0.406000\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [],
      "metadata": {
        "id": "ocY1fBz4pRke"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Softmax Classifier (20 pts)\n",
        "\n",
        "In this section, we will first implement the loss function for softmax classifier, and then use the validation set to set the learning rate and regularization strength."
      ],
      "metadata": {
        "id": "oi-IrQTqNaGB"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Loss Function (10 pts)"
      ],
      "metadata": {
        "id": "QRoU4F1gW2Md"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def softmax_loss(W, X, y, reg):\n",
        "    \"\"\"\n",
        "    Softmax loss function\n",
        "\n",
        "    Inputs have dimension D, there are C classes, and we operate on minibatches\n",
        "    of N examples.\n",
        "\n",
        "    Inputs:\n",
        "    - W: A numpy array of shape (D, C) containing weights.\n",
        "    - X: A numpy array of shape (N, D) containing a minibatch of data.\n",
        "    - y: A numpy array of shape (N,) containing training labels; y[i] = c means\n",
        "      that X[i] has label c, where 0 <= c < C.\n",
        "    - reg: (float) regularization strength\n",
        "\n",
        "    Returns a tuple of:\n",
        "    - loss as single float\n",
        "    - gradient with respect to weights W; an array of same shape as W\n",
        "    \"\"\"\n",
        "    # Initialize the loss and gradient to zero.\n",
        "    loss = 0.0\n",
        "    dW = np.zeros_like(W)\n",
        "\n",
        "    #############################################################################\n",
        "    # TODO (10 pts):                                                            #\n",
        "    # Compute the softmax loss and its gradient using no explicit loops.        #\n",
        "    # Store the loss in loss and the gradient in dW. If you are not careful     #\n",
        "    # here, it is easy to run into numeric instability. Don't forget the        #\n",
        "    # regularization!                                                           #\n",
        "    #############################################################################\n",
        "    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "    scores = X.dot(W)\n",
        "    scores -= np.max(scores, axis=1, keepdims=True)\n",
        "\n",
        "    exp_scores = np.exp(scores)\n",
        "    probs = exp_scores / np.sum(exp_scores, axis=1, keepdims=True)\n",
        "\n",
        "    correct_log_probs = -np.log(probs[np.arange(X.shape[0]), y])\n",
        "    loss = np.sum(correct_log_probs) / X.shape[0]\n",
        "\n",
        "    loss += 0.5 * reg * np.sum(W * W)\n",
        "\n",
        "    dscores = probs\n",
        "    dscores[np.arange(X.shape[0]), y] -= 1\n",
        "    dscores /= X.shape[0]\n",
        "\n",
        "    dW = X.T.dot(dscores)\n",
        "    dW += reg * W\n",
        "\n",
        "    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "    return loss, dW"
      ],
      "metadata": {
        "id": "xs4TEI_jqEMo"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class Softmax(LinearClassifier):\n",
        "    \"\"\" A subclass that uses the Softmax + Cross-entropy loss function \"\"\"\n",
        "\n",
        "    def loss(self, X_batch, y_batch, reg):\n",
        "        return softmax_loss(self.W, X_batch, y_batch, reg)"
      ],
      "metadata": {
        "id": "oz33V9w9QuSA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Hyperparameter Tuning (10 pts)"
      ],
      "metadata": {
        "id": "iP0oB8rVYxmT"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "results = {}\n",
        "best_val = -1\n",
        "best_softmax = None\n",
        "\n",
        "################################################################################\n",
        "# TODO (10 pts):                                                               #\n",
        "# Use the validation set to set the learning rate and regularization strength. #\n",
        "# This should be identical to the validation that you did for the SVM; save    #\n",
        "# the best trained softmax classifer in best_softmax.                          #\n",
        "################################################################################\n",
        "\n",
        "# Provided as a reference. You may or may not want to change these hyperparameters\n",
        "learning_rates = [0.009]\n",
        "regularization_strengths = [0.09]\n",
        "# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "for lr in learning_rates:\n",
        "    for reg in regularization_strengths:\n",
        "        softmax_classifier = Softmax()\n",
        "\n",
        "        loss_hist = softmax_classifier.train(X_train, y_train, learning_rate=lr, reg=reg,\n",
        "                                             num_iters=1500, verbose=False)\n",
        "\n",
        "        y_train_pred = softmax_classifier.predict(X_train)\n",
        "        train_accuracy = np.mean(y_train == y_train_pred)\n",
        "\n",
        "        y_val_pred = softmax_classifier.predict(X_val)\n",
        "        val_accuracy = np.mean(y_val == y_val_pred)\n",
        "\n",
        "        results[(lr, reg)] = (train_accuracy, val_accuracy)\n",
        "\n",
        "        if val_accuracy > best_val:\n",
        "            best_val = val_accuracy\n",
        "            best_softmax = softmax_classifier\n",
        "# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****\n",
        "\n",
        "# Print out results.\n",
        "for lr, reg in sorted(results):\n",
        "    train_accuracy, val_accuracy = results[(lr, reg)]\n",
        "    print('lr %e reg %e train accuracy: %f val accuracy: %f' % (\n",
        "                lr, reg, train_accuracy, val_accuracy))\n",
        "\n",
        "print('best validation accuracy achieved during cross-validation: %f' % best_val)"
      ],
      "metadata": {
        "id": "v45_GEB0qcQD",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "728d7400-8f53-459f-f6d4-9a6cf3a75e4f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "lr 9.000000e-03 reg 9.000000e-02 train accuracy: 0.383980 val accuracy: 0.387000\n",
            "best validation accuracy achieved during cross-validation: 0.387000\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# evaluate on test set\n",
        "# Evaluate the best softmax on test set\n",
        "y_test_pred = best_softmax.predict(X_test)\n",
        "test_accuracy = np.mean(y_test == y_test_pred)\n",
        "print('softmax on raw pixels final test set accuracy: %f' % (test_accuracy, ))"
      ],
      "metadata": {
        "id": "dzpddP22qmL_",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "faab266e-1253-4526-822e-862663f1736b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "softmax on raw pixels final test set accuracy: 0.386000\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Acknowledgement\n",
        "\n",
        "Credits to [UMichigan's 498/598 Deep Learning for Computer Vision](https://web.eecs.umich.edu/~justincj/teaching/eecs498/FA2020/) and Stanfords's [CS231n: Convolutional Neural Networks for Visual Recognition](https://cs231n.github.io/), some code is adapted from their courses's assignments."
      ],
      "metadata": {
        "id": "hkodX4KYRcEA"
      }
    }
  ]
}