{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Машинное обучение \n",
    "\n",
    "### Факультет математики НИУ ВШЭ, 2020-21 учебный год\n",
    "\n",
    "_Илья Щуров, Соня Дымченко, Руслан Хайдуров, Павел Егоров, Максим Бекетов_\n",
    "\n",
    "[Страница курса](http://wiki.cs.hse.ru/Машинное_обучение_на_матфаке_2021)\n",
    "\n",
    "\n",
    "## Домашнее задание 5. Линейные модели и градиентный спуск."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В данном задании необходимо реализовать обучение логистической и линейной регрессий с помощью различных вариантов градиентного спуска.\n",
    "\n",
    "Правила оценивания найдите на странице курса."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 1: Реализация градиентного спуска.\n",
    "\n",
    "Реализуйте логистическую регрессию с лог-лоссом, обучаемую с помощью:\n",
    "\n",
    "**Задание 1 (1 балл)** Градиентного спуска;\n",
    "\n",
    "Подробнее о методах можно прочитать [тут](https://github.com/esokolov/ml-course-hse/blob/master/2019-fall/lecture-notes/lecture02-linregr.pdf). Напомним, что лог-лосс вычисляется по формуле\n",
    "$$\n",
    "    \\mathcal{L}(y, X, w) = -\\cfrac{1}{n} \\sum_{i=1}^{n} [y_i=1]\\log \\sigma(\\langle w, x_i\\rangle) + [y_i=0]\\log (1 - \\sigma(\\langle w, x_i\\rangle)) + \\lambda_2 ||w||_2^2 + \\lambda_1 ||w||_1\n",
    "$$\n",
    "где $\\sigma(x) = 1 / (1 + \\exp(-x))$, а $\\lambda_1, \\lambda_2 > 0$ -- параметры регуляризации. Считайте, что либо $\\lambda_1 = 0$, либо $\\lambda_2 = 0$. \n",
    "\n",
    "Необходимо соблюдать следующие условия:\n",
    "\n",
    "* Все вычисления должны быть векторизованы;\n",
    "* Циклы средствами python допускается использовать только для итераций градиентного спуска в методе fit; также разрешается использовать только стандартные средства языка Python и библиотеку numpy.\n",
    "* Обучение необходимо приостанавливать, если выполнено хотя бы одно из двух условий:\n",
    "\n",
    "    * проверку на евклидовую норму разности весов на двух соседних итерациях (например, меньше некоторого малого числа порядка $10^{-6}$, задаваемого параметром `tolerance`);\n",
    "    * достижение максимального числа итераций (например, 10000, задаваемого параметром `max_iter`).\n",
    "* Чтобы проследить, что оптимизационный процесс действительно сходится, будем использовать атрибут `loss_history` — в нём после вызова метода `fit` должны содержаться значения функции потерь для всех итераций, начиная с первой (до совершения первого шага по антиградиенту);\n",
    "* Инициализировать веса можно случайным образом или нулевым вектором. \n",
    "\n",
    "\n",
    "Ниже приведён шаблон класса, который должен содержать код реализации каждого из методов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.base import BaseEstimator\n",
    "\n",
    "\n",
    "class LogReg(BaseEstimator):\n",
    "    def __init__(self, lambda_1=0.0, lambda_2=1.0, gd_type='full', \n",
    "                 tolerance=1e-4, max_iter=1000, w0=None, alpha=1e-3, eta=0.0):\n",
    "        \"\"\"\n",
    "        lambda_1: L1 regularization param\n",
    "        lambda_2: L2 regularization param\n",
    "        gd_type: 'full', 'stochastic' or 'momentum'\n",
    "        tolerance: for stopping gradient descent\n",
    "        max_iter: maximum number of steps in gradient descent\n",
    "        w0: np.array of shape (d) - init weights\n",
    "        alpha: learning rate\n",
    "        eta: ignored\n",
    "        \"\"\"\n",
    "        self.lambda_1 = lambda_1\n",
    "        self.lambda_2 = lambda_2\n",
    "        self.gd_type = gd_type\n",
    "        self.tolerance = tolerance\n",
    "        self.max_iter = max_iter\n",
    "        self.w0 = w0\n",
    "        self.alpha = alpha\n",
    "        self.w = None\n",
    "        self.loss_history = None\n",
    "        self.eta = eta\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d)\n",
    "        y: np.array of shape (l)\n",
    "        ---\n",
    "        output: self\n",
    "        \"\"\"\n",
    "        self.loss_history = []\n",
    "        \n",
    "        pass\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    def predict_proba(self, X):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d)\n",
    "        ---\n",
    "        output: np.array of shape (l, 2) where\n",
    "        first column has probabilities of -1\n",
    "        second column has probabilities of +1\n",
    "        \"\"\"\n",
    "        if self.w is None:\n",
    "            raise Exception('Not trained yet')\n",
    "        \n",
    "        pass\n",
    "    \n",
    "    def calc_gradient(self, X, y):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d) (l can be equal to 1 if stochastic)\n",
    "        y: np.array of shape (l)\n",
    "        ---\n",
    "        output: np.array of shape (d)\n",
    "        \"\"\"\n",
    "        pass\n",
    "\n",
    "    def calc_loss(self, X, y):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d)\n",
    "        y: np.array of shape (l)\n",
    "        ---\n",
    "        output: float \n",
    "        \"\"\" \n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 2 (0 баллов)**. \n",
    "* Загрузите обучающие данные с соревнования [Porto Seguro](https://www.kaggle.com/c/porto-seguro-safe-driver-prediction);\n",
    "* Пересэмплируйте её так, чтобы объектов положительного и отрциательного классов было поровну;\n",
    "* Разбейте выборку на обучающую и тестовую в отношении 7:3.\n",
    "\n",
    "Ладно, мы сделали это за вас. =)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = pd.read_csv('train.csv', index_col=0)\n",
    "target = data.target.values\n",
    "data = data.drop('target', axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# some resampling\n",
    "np.random.seed(910)\n",
    "mask_plus = np.unique(np.random.choice(np.where(target == 1)[0], 100000, replace=True))\n",
    "mask_zero = np.unique(np.random.choice(np.where(target == 0)[0], 100000, replace=True))\n",
    "\n",
    "data = pd.concat((data.iloc[mask_plus], data.iloc[mask_zero]))\n",
    "target = np.hstack((target[mask_plus], target[mask_zero]))\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 3 (0.5 балла)**. Обучите и провалидируйте LogReg на данных из предыдущего пункта, посчитайте по тестовой выборке AUC-ROC и F-меру. Исследуйте влияние параметров `max_iter` и `alpha` на процесс оптимизации. Согласуется ли оно с вашими ожиданиями? (здесь подразумеваются графики, на которых отображаются значения метрик в зависимости от значения параметра)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 2: линейная регрессия и feature importance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте логистическую регрессию с лог-лоссом, обучаемую с помощью:\n",
    "\n",
    "**Задание 4 (1.5 балла)** Стохастического градиентного спуска;\n",
    "\n",
    "**Задание 5 (1.5 балла)** Стохастического градиентного спуска с Momentum.\n",
    "\n",
    "Подробнее о методах можно прочитать [тут](https://github.com/esokolov/ml-course-hse/blob/master/2019-fall/lecture-notes/lecture02-linregr.pdf). Напомним, что лог-лосс вычисляется по формуле\n",
    "$$\n",
    "    \\mathcal{L}(y, X, w) = -\\cfrac{1}{n} \\sum_{i=1}^{n} [y_i=1]\\log \\sigma(\\langle w, x_i\\rangle) + [y_i=0]\\log (1 - \\sigma(\\langle w, x_i\\rangle)) + \\lambda_2 ||w||_2^2 + \\lambda_1 ||w||_1\n",
    "$$\n",
    "где $\\sigma(x) = 1 / (1 + \\exp(-x))$, а $\\lambda_1, \\lambda_2 > 0$ -- параметры регуляризации. Считайте, что либо $\\lambda_1 = 0$, либо $\\lambda_2 = 0$. \n",
    "\n",
    "Во всех пунктах необходимо соблюдать следующие условия:\n",
    "\n",
    "* Все вычисления должны быть векторизованы;\n",
    "* Циклы средствами python допускается использовать только для итераций градиентного спуска в методе fit; также разрешается использовать только стандартные средства языка Python и библиотеку numpy.\n",
    "* Обучение необходимо приостанавливать, если выполнено хотя бы одно из двух условий:\n",
    "\n",
    "    * проверку на евклидовую норму разности весов на двух соседних итерациях (например, меньше некоторого малого числа порядка $10^{-6}$, задаваемого параметром `tolerance`);\n",
    "    * достижение максимального числа итераций (например, 10000, задаваемого параметром `max_iter`).\n",
    "* Чтобы проследить, что оптимизационный процесс действительно сходится, будем использовать атрибут `loss_history` — в нём после вызова метода `fit` должны содержаться значения функции потерь для всех итераций, начиная с первой (до совершения первого шага по антиградиенту);\n",
    "* Инициализировать веса можно случайным образом или нулевым вектором. \n",
    "\n",
    "\n",
    "Ниже приведён шаблон класса, который должен содержать код реализации каждого из методов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.base import BaseEstimator\n",
    "\n",
    "class LogReg(BaseEstimator):\n",
    "    def __init__(self, lambda_1=0.0, lambda_2=1.0, gd_type='stochastic', \n",
    "                 tolerance=1e-4, max_iter=1000, w0=None, alpha=1e-3, eta=0.0):\n",
    "        \"\"\"\n",
    "        lambda_1: L1 regularization param\n",
    "        lambda_2: L2 regularization param\n",
    "        gd_type: 'full', 'stochastic' or 'momentum'\n",
    "        tolerance: for stopping gradient descent\n",
    "        max_iter: maximum number of steps in gradient descent\n",
    "        w0: np.array of shape (d) - init weights\n",
    "        alpha: learning rate\n",
    "        eta: momentum parameter (weight of momentum vector)\n",
    "        \"\"\"\n",
    "        self.lambda_1 = lambda_1\n",
    "        self.lambda_2 = lambda_2\n",
    "        self.gd_type = gd_type\n",
    "        self.tolerance = tolerance\n",
    "        self.max_iter = max_iter\n",
    "        self.w0 = w0\n",
    "        self.alpha = alpha\n",
    "        self.w = None\n",
    "        self.loss_history = None\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d)\n",
    "        y: np.array of shape (l)\n",
    "        ---\n",
    "        output: self\n",
    "        \"\"\"\n",
    "        self.loss_history = []\n",
    "        \n",
    "        pass\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    def predict_proba(self, X):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d)\n",
    "        ---\n",
    "        output: np.array of shape (l, 2) where\n",
    "        first column has probabilities of -1\n",
    "        second column has probabilities of +1\n",
    "        \"\"\"\n",
    "        if self.w is None:\n",
    "            raise Exception('Not trained yet')\n",
    "        \n",
    "        pass\n",
    "    \n",
    "    def calc_gradient(self, X, y):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d) (l can be equal to 1 if stochastic)\n",
    "        y: np.array of shape (l)\n",
    "        ---\n",
    "        output: np.array of shape (d)\n",
    "        \"\"\"\n",
    "        pass\n",
    "\n",
    "    def calc_loss(self, X, y):\n",
    "        \"\"\"\n",
    "        X: np.array of shape (l, d)\n",
    "        y: np.array of shape (l)\n",
    "        ---\n",
    "        output: float \n",
    "        \"\"\" \n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 5.5 (1 балл)**. Обучите и провалидируйте оба метода на данных из пункта 2, посчитайте по тестовой выборке AUC-ROC и F-меру. Исследуйте влияние параметров `max_iter`, `alpha` и `eta` на процесс оптимизации. Согласуется ли оно с вашими ожиданиями? (здесь подразумеваются графики, на которых отображаются значения метрик в зависимости от значения параметра)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 6 (1.5 балла)**. Постройте графики (на одной и той же картинке) зависимости величины функции потерь от номера итерации для полного, стохастического градиентного спусков, а также для полного градиентного спуска с методом Momentum. Постройте аналогичные графики для зависимости от времени работы в секундах. Сделайте выводы о скорости сходимости различных модификаций градиентного спуска.\n",
    "\n",
    "Назовём график *красивым*, если он соответствует требованиям, предъявленным к графикам в первом дз. В этом задании от вас требуются красивые графики."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Далее мы проанализируем то, как работает линейная регрессия и регуляризация. Тут уже можно пользоваться sklearn'ом."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 7__ (0 баллов). Загрузите обучающие данные из соревнования [New York City Taxi Trip Duration](https://www.kaggle.com/c/nyc-taxi-trip-duration/data). Разделите выборку в отношении 7:3. Преобразуйте целевую переменную (trip_duration) как $\\widetilde{y} = \\log(1 + y)$. Удалите столбец id, а также столбцы, содержащие дату и время. Отнормируйте признаки при помощи MinMaxScaler'a. Как вы думаете, почему такое преобразование имеет смысл?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 8__ (1 балл). Обучите три вида линейной регрессии на получившихся данных: обычную, Ridge и Lasso. Оцените качество при помощи MSE и $R^2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 9__ (1 балл). Постройте графики зависимости значения метрик из предыдущего задания от значения коэффициента регуляризации для методов Lasso и Ridge. Какие выводы можно сделать?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хорошие ли получились результаты?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 10__ (0.5 баллов). При помощи кросс-валидации найдите оптимальные значения коэффициента регуляризации для методов Ridge и Lasso."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 11__ (0.5 баллов). Постройте bar plot весов признаков для каждой из трёх моделей (на одном рисунке). Какие выводы можно сделать?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Какие фичи оказались наиболее важными? Согласуется ли это с вашими ожиданиями?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 12__ (2 балла). Добавьте в датасет дополнительные признаки, основываясь на существующих, чтобы получить значение метрики MSE на тестовом куске данных не более 0.4. Что вы для этого сделали?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Бонус\n",
    "\n",
    "Бонусные задачи оцениваются особенно строго. Оценка может быть снижена за плохой код и даже за некрасивые названия переменных. Подсказок не даём.\n",
    "\n",
    "\n",
    "**Задание 13 (0.5 баллов)**. Правда ли, что лог-лосс является выпуклой функцией относительно $w$? Правда ли, что она является Липшицевой относительно $w$? Почему?\n",
    "\n",
    "**Задание 14 (3 балла)**. В этом задании на 2 балла засчитывается один из двух пунктов:\n",
    " * Реализуйте логистическую регрессию с лог-лоссом, обучаемую с помощью метода [Adam](https://arxiv.org/pdf/1412.6980.pdf)\n",
    " * Реализуйте логистическую регрессию с лог-лоссом, обучаемую с помощью [метода Ньютона](https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization)\n",
    "\n",
    "добавьте при необходимости параметры в класс модели, повторите пункты 2 и 3 и сравните результаты.\n",
    "\n",
    "На 3 балла засчитываются оба пункта со сравнением методов и выводами."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 15 (0.00 баллов)**.  Вставьте ниже самый смешной или самый грустный график, который получился у вас в этом дз."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}