assignments/assignment1/Linear classifier.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Задание 1.2 - Линейный классификатор (Linear classifier)\n",
    "\n",
    "В этом задании мы реализуем другую модель машинного обучения - линейный классификатор. Линейный классификатор подбирает для каждого класса веса, на которые нужно умножить значение каждого признака и потом сложить вместе.\n",
    "Тот класс, у которого эта сумма больше, и является предсказанием модели.\n",
    "\n",
    "В этом задании вы:\n",
    "- потренируетесь считать градиенты различных многомерных функций\n",
    "- реализуете подсчет градиентов через линейную модель и функцию потерь softmax\n",
    "- реализуете процесс тренировки линейного классификатора\n",
    "- подберете параметры тренировки на практике\n",
    "\n",
    "На всякий случай, еще раз ссылка на туториал по numpy:  \n",
    "http://cs231n.github.io/python-numpy-tutorial/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataset import load_svhn, random_split_train_val\n",
    "from gradient_check import check_gradient\n",
    "from metrics import multiclass_accuracy \n",
    "import linear_classifer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Как всегда, первым делом загружаем данные\n",
    "\n",
    "Мы будем использовать все тот же SVHN."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prepare_for_linear_classifier(train_X, test_X):\n",
    "    train_flat = train_X.reshape(train_X.shape[0], -1).astype(np.float) / 255.0\n",
    "    test_flat = test_X.reshape(test_X.shape[0], -1).astype(np.float) / 255.0\n",
    "    \n",
    "    # Subtract mean\n",
    "    mean_image = np.mean(train_flat, axis = 0)\n",
    "    train_flat -= mean_image\n",
    "    test_flat -= mean_image\n",
    "    \n",
    "    # Add another channel with ones as a bias term\n",
    "    train_flat_with_ones = np.hstack([train_flat, np.ones((train_X.shape[0], 1))])\n",
    "    test_flat_with_ones = np.hstack([test_flat, np.ones((test_X.shape[0], 1))])    \n",
    "    return train_flat_with_ones, test_flat_with_ones\n",
    "    \n",
    "train_X, train_y, test_X, test_y = load_svhn(\"data\", max_train=10000, max_test=1000)    \n",
    "train_X, test_X = prepare_for_linear_classifier(train_X, test_X)\n",
    "# Split train into train and val\n",
    "train_X, train_y, val_X, val_y = random_split_train_val(train_X, train_y, num_val = 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Играемся с градиентами!\n",
    "\n",
    "В этом курсе мы будем писать много функций, которые вычисляют градиенты аналитическим методом.\n",
    "\n",
    "Все функции, в которых мы будем вычислять градиенты, будут написаны по одной и той же схеме.  \n",
    "Они будут получать на вход точку, где нужно вычислить значение и градиент функции, а на выходе будут выдавать кортеж (tuple) из двух значений - собственно значения функции в этой точке (всегда одно число) и аналитического значения градиента в той же точке (той же размерности, что и вход).\n",
    "```\n",
    "def f(x):\n",
    "    \"\"\"\n",
    "    Computes function and analytic gradient at x\n",
    "    \n",
    "    x: np array of float, input to the function\n",
    "    \n",
    "    Returns:\n",
    "    value: float, value of the function \n",
    "    grad: np array of float, same shape as x\n",
    "    \"\"\"\n",
    "    ...\n",
    "    \n",
    "    return value, grad\n",
    "```\n",
    "\n",
    "Необходимым инструментом во время реализации кода, вычисляющего градиенты, является функция его проверки. Эта функция вычисляет градиент численным методом и сверяет результат с градиентом, вычисленным аналитическим методом.\n",
    "\n",
    "Мы начнем с того, чтобы реализовать вычисление численного градиента (numeric gradient) в функции `check_gradient` в `gradient_check.py`. Эта функция будет принимать на вход функции формата, заданного выше, использовать значение `value` для вычисления численного градиента и сравнит его с аналитическим - они должны сходиться.\n",
    "\n",
    "Напишите часть функции, которая вычисляет градиент с помощью численной производной для каждой координаты. Для вычисления производной используйте так называемую two-point formula (https://en.wikipedia.org/wiki/Numerical_differentiation):\n",
    "\n",
    "![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/22fc2c0a66c63560a349604f8b6b39221566236d)\n",
    "\n",
    "Все функции приведенные в следующей клетке должны проходить gradient check."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# TODO: Implement check_gradient function in gradient_check.py\n",
    "# All the functions below should pass the gradient check\n",
    "\n",
    "def square(x):\n",
    "    return float(x*x), 2*x\n",
    "\n",
    "check_gradient(square, np.array([3.0]))\n",
    "\n",
    "def array_sum(x):\n",
    "    assert x.shape == (2,), x.shape\n",
    "    return np.sum(x), np.ones_like(x)\n",
    "\n",
    "check_gradient(array_sum, np.array([3.0, 2.0]))\n",
    "\n",
    "def array_2d_sum(x):\n",
    "    assert x.shape == (2,2)\n",
    "    return np.sum(x), np.ones_like(x)\n",
    "\n",
    "check_gradient(array_2d_sum, np.array([[3.0, 2.0], [1.0, 0.0]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Начинаем писать свои функции, считающие аналитический градиент\n",
    "\n",
    "Теперь реализуем функцию softmax, которая получает на вход оценки для каждого класса и преобразует их в вероятности от 0 до 1:\n",
    "![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/e348290cf48ddbb6e9a6ef4e39363568b67c09d3)\n",
    "\n",
    "**Важно:** Практический аспект вычисления этой функции заключается в том, что в ней учавствует вычисление экспоненты от потенциально очень больших чисел - это может привести к очень большим значениям в числителе и знаменателе за пределами диапазона float.\n",
    "\n",
    "К счастью, у этой проблемы есть простое решение -- перед вычислением softmax вычесть из всех оценок максимальное значение среди всех оценок:\n",
    "```\n",
    "predictions -= np.max(predictions)\n",
    "```\n",
    "(подробнее здесь - http://cs231n.github.io/linear-classify/#softmax, секция `Practical issues: Numeric stability`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO Implement softmax and cross-entropy for single sample\n",
    "probs = linear_classifer.softmax(np.array([-10, 0, 10]))\n",
    "\n",
    "# Make sure it works for big numbers too!\n",
    "probs = linear_classifer.softmax(np.array([1000, 0, 0]))\n",
    "assert np.isclose(probs[0], 1.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Кроме этого, мы реализуем cross-entropy loss, которую мы будем использовать как функцию ошибки (error function).\n",
    "В общем виде cross-entropy определена следующим образом:\n",
    "![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cb6da032ab424eefdca0884cd4113fe578f4293)\n",
    "\n",
    "где x - все классы, p(x) - истинная вероятность принадлежности сэмпла классу x, а q(x) - вероятность принадлежности классу x, предсказанная моделью.  \n",
    "В нашем случае сэмпл принадлежит только одному классу, индекс которого передается функции. Для него p(x) равна 1, а для остальных классов - 0. \n",
    "\n",
    "Это позволяет реализовать функцию проще!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "probs = linear_classifer.softmax(np.array([-5, 0, 5]))\n",
    "linear_classifer.cross_entropy_loss(probs, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "После того как мы реализовали сами функции, мы можем реализовать градиент.\n",
    "\n",
    "Оказывается, что вычисление градиента становится гораздо проще, если объединить эти функции в одну, которая сначала вычисляет вероятности через softmax, а потом использует их для вычисления функции ошибки через cross-entropy loss.\n",
    "\n",
    "Эта функция `softmax_with_cross_entropy` будет возвращает и значение ошибки, и градиент по входным параметрам. Мы проверим корректность реализации с помощью `check_gradient`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO Implement combined function or softmax and cross entropy and produces gradient\n",
    "loss, grad = linear_classifer.softmax_with_cross_entropy(np.array([1, 0, 0]), 1)\n",
    "check_gradient(lambda x: linear_classifer.softmax_with_cross_entropy(x, 1), np.array([1, 0, 0], np.float))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В качестве метода тренировки мы будем использовать стохастический градиентный спуск (stochastic gradient descent или SGD), который работает с батчами сэмплов. \n",
    "\n",
    "Поэтому все наши фукнции будут получать не один пример, а батч, то есть входом будет не вектор из `num_classes` оценок, а матрица размерности `batch_size, num_classes`. Индекс примера в батче всегда будет первым измерением.\n",
    "\n",
    "Следующий шаг - переписать наши функции так, чтобы они поддерживали батчи.\n",
    "\n",
    "Финальное значение функции ошибки должно остаться числом, и оно равно среднему значению ошибки среди всех примеров в батче."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# TODO Extend combined function so it can receive a 2d array with batch of samples\n",
    "np.random.seed(42)\n",
    "# Test batch_size = 1\n",
    "num_classes = 4\n",
    "batch_size = 1\n",
    "predictions = np.random.randint(-1, 3, size=(batch_size, num_classes)).astype(np.float)\n",
    "target_index = np.random.randint(0, num_classes, size=(batch_size, 1)).astype(np.int)\n",
    "check_gradient(lambda x: linear_classifer.softmax_with_cross_entropy(x, target_index), predictions)\n",
    "\n",
    "# Test batch_size = 3\n",
    "num_classes = 4\n",
    "batch_size = 3\n",
    "predictions = np.random.randint(-1, 3, size=(batch_size, num_classes)).astype(np.float)\n",
    "target_index = np.random.randint(0, num_classes, size=(batch_size, 1)).astype(np.int)\n",
    "check_gradient(lambda x: linear_classifer.softmax_with_cross_entropy(x, target_index), predictions)\n",
    "\n",
    "# Make sure maximum subtraction for numberic stability is done separately for every sample in the batch\n",
    "probs = linear_classifer.softmax(np.array([[20,0,0], [1000, 0, 0]]))\n",
    "assert np.all(np.isclose(probs[:, 0], 1.0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Наконец, реализуем сам линейный классификатор!\n",
    "\n",
    "softmax и cross-entropy получают на вход оценки, которые выдает линейный классификатор.\n",
    "\n",
    "Он делает это очень просто: для каждого класса есть набор весов, на которые надо умножить пиксели картинки и сложить. Получившееся число и является оценкой класса, идущей на вход softmax.\n",
    "\n",
    "Таким образом, линейный классификатор можно представить как умножение вектора с пикселями на матрицу W размера `num_features, num_classes`. Такой подход легко расширяется на случай батча векторов с пикселями X размера `batch_size, num_features`:\n",
    "\n",
    "`predictions = X * W`, где `*` - матричное умножение.\n",
    "\n",
    "Реализуйте функцию подсчета линейного классификатора и градиентов по весам `linear_softmax` в файле `linear_classifer.py`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO Implement linear_softmax function that uses softmax with cross-entropy for linear classifier\n",
    "batch_size = 2\n",
    "num_classes = 2\n",
    "num_features = 3\n",
    "np.random.seed(42)\n",
    "W = np.random.randint(-1, 3, size=(num_features, num_classes)).astype(np.float)\n",
    "X = np.random.randint(-1, 3, size=(batch_size, num_features)).astype(np.float)\n",
    "target_index = np.ones(batch_size, dtype=np.int)\n",
    "\n",
    "loss, dW = linear_classifer.linear_softmax(X, W, target_index)\n",
    "check_gradient(lambda w: linear_classifer.linear_softmax(X, w, target_index), W)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### И теперь регуляризация\n",
    "\n",
    "Мы будем использовать L2 regularization для весов как часть общей функции ошибки.\n",
    "\n",
    "Напомним, L2 regularization определяется как\n",
    "\n",
    "l2_reg_loss = regularization_strength * sum<sub>ij</sub> W[i, j]<sup>2</sup>\n",
    "\n",
    "Реализуйте функцию для его вычисления и вычисления соотвествующих градиентов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO Implement l2_regularization function that implements loss for L2 regularization\n",
    "linear_classifer.l2_regularization(W, 0.01)\n",
    "check_gradient(lambda w: linear_classifer.l2_regularization(w, 0.01), W)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Тренировка!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Градиенты в порядке, реализуем процесс тренировки!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# TODO: Implement LinearSoftmaxClassifier.fit function\n",
    "classifier = linear_classifer.LinearSoftmaxClassifier()\n",
    "loss_history = classifier.fit(train_X, train_y, epochs=10, learning_rate=1e-3, batch_size=300, reg=1e1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's look at the loss history!\n",
    "plt.plot(loss_history)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's check how it performs on validation set\n",
    "pred = classifier.predict(val_X)\n",
    "accuracy = multiclass_accuracy(pred, val_y)\n",
    "print(\"Accuracy: \", accuracy)\n",
    "\n",
    "# Now, let's train more and see if it performs better\n",
    "classifier.fit(train_X, train_y, epochs=100, learning_rate=1e-3, batch_size=300, reg=1e1)\n",
    "pred = classifier.predict(val_X)\n",
    "accuracy = multiclass_accuracy(pred, val_y)\n",
    "print(\"Accuracy after training for 100 epochs: \", accuracy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Как и раньше, используем кросс-валидацию для подбора гиперпараметтов.\n",
    "\n",
    "В этот раз, чтобы тренировка занимала разумное время, мы будем использовать только одно разделение на тренировочные (training) и проверочные (validation) данные.\n",
    "\n",
    "Теперь нам нужно подобрать не один, а два гиперпараметра! Не ограничивайте себя изначальными значениями в коде.  \n",
    "Добейтесь точности более чем **20%** на проверочных данных (validation data)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_epochs = 200\n",
    "batch_size = 300\n",
    "\n",
    "learning_rates = [1e-3, 1e-4, 1e-5]\n",
    "reg_strengths = [1e-4, 1e-5, 1e-6]\n",
    "\n",
    "best_classifier = None\n",
    "best_val_accuracy = None\n",
    "\n",
    "# TODO use validation set to find the best hyperparameters\n",
    "# hint: for best results, you might need to try more values for learning rate and regularization strength \n",
    "# than provided initially\n",
    "\n",
    "print('best validation accuracy achieved: %f' % best_val_accuracy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Какой же точности мы добились на тестовых данных?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_pred = best_classifier.predict(test_X)\n",
    "test_accuracy = multiclass_accuracy(test_pred, test_y)\n",
    "print('Linear softmax classifier test set accuracy: %f' % (test_accuracy, ))"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}