ML17/homeworks-practice/homework-practice-02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Машинное обучение, ВМК МГУ\n",
    "\n",
    "## Практическое задание 2\n",
    "\n",
    "### Общая информация\n",
    "Дата выдачи: 4 ноября 2017\n",
    "\n",
    "Мягкий дедлайн: 23:59MSK 19 ноября (за каждый день просрочки снимается 1 балл)\n",
    "\n",
    "Жесткий дедлайн: 23:59MSK 26 ноября."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### О задании\n",
    "\n",
    "В этом задании вы:\n",
    "- обучите линейную регрессию, познакомитесь с метриками качества в задачах регресии\n",
    "- реализуете логистическую регрессию и её обучение градиентным спуском\n",
    "- настроите метод опорных векторов, визуализируете опорные вектора\n",
    "- познакомитесь с калибровочными кривыми и сравните вероятности, выдаваемые логистической регрессией и методом опорных векторов\n",
    "- изучите методы работы с категориальными переменными\n",
    "- в качестве бонуса попробуете библиотеку vowpal wabbit.\n",
    "\n",
    "\n",
    "### Оценивание и штрафы\n",
    "Каждая из задач имеет определенную «стоимость» (указана в скобках около задачи). Максимально допустимая оценка за работу — 10 баллов.\n",
    "\n",
    "Сдавать задание после указанного срока сдачи нельзя. При выставлении неполного балла за задание в связи с наличием ошибок на усмотрение проверяющего предусмотрена возможность исправить работу на указанных в ответном письме условиях.\n",
    "\n",
    "Задание выполняется самостоятельно. «Похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) не могут получить за него больше 0 баллов (подробнее о плагиате см. на странице курса). Если вы нашли решение какого-то из заданий (или его часть) в открытом источнике, необходимо указать ссылку на этот источник в отдельном блоке в конце вашей работы (скорее всего вы будете не единственным, кто это нашел, поэтому чтобы исключить подозрение в плагиате, необходима ссылка на источник).\n",
    "\n",
    "Неэффективная реализация кода может негативно отразиться на оценке.\n",
    "\n",
    "\n",
    "### Формат сдачи\n",
    "Для сдачи задания переименуйте получившийся файл *.ipynb в соответствии со следующим форматом: homework-practice-02-Username.ipynb, где Username — ваша фамилия и имя на латинице именно в таком порядке (например, homework-practice-02-IvanovIvan.ipynb). Приложите модули с кодом logreg.py и заархивируйте оба файла вместе в zip формат. Имя архива должно быть homework-practice-02-Username.zip)\n",
    "\n",
    "Далее отправьте этот файл на ml.cmc.msu@gmail.com\n",
    "\n",
    "\n",
    "Для удобства проверки самостоятельно посчитайте свою максимальную оценку (исходя из набора решенных задач) и укажите ниже."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Оценка:** ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%pylab inline\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn.base import BaseEstimator\n",
    "from sklearn.datasets import load_diabetes\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 1. Линейная регрессия"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части мы кратко познакомимся с линейной регрессией.\n",
    "\n",
    "Для начала загрузим данные и разделим их на обучающую и тестовую выборки в соотношении 7 к 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data = load_diabetes()\n",
    "X_train, X_test, y_train, y_test = train_test_split(data.data, data.target, train_size=0.7, random_state=241)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 1.__ Обучение линейной регрессии.\n",
    "\n",
    "**(1 балл)**\n",
    "\n",
    "Обучите линейную регрессию с $L_1$ (Lasso) и $L_2$ (Ridge) регуляризаторами (используйте параметры по умолчанию). Посмотрите, какое количество коэффициентов близко к 0 (степень близости к 0 определите сами из разумных пределов). Постройте график зависимости числа ненулевых коэффициентов от коэффицента регуляризации (перебирайте значения по логарифмической сетке от $10^{-3}$ до $10^3$). Согласуются ли результаты с вашими ожиданиями?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посчитайте для Ridge-регрессии следующие метрики: $RMSE$, $MAE$, $R^2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Подберите на обучающей выборке для Ridge-регрессии коэффициент регуляризации (перебирайте значения по логарифмической сетке от $10^{-3}$ до $10^3$) для каждой из метрик. Для этого воспользуйтесь GridSearchCV и KFold из sklearn. Постройте графики зависимости фукнции потерь от коэффициента регуляризации. Посчитайте те же метрики снова. Заметно ли изменилось качество?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "__Задание 2.__ Поиск объектов-выбросов\n",
    "\n",
    "**(0.5 балла)**\n",
    "\n",
    "Как известно, MSE сильно штрафует за большие ошибки на объектах-выбросах. С помощью cross_val_predict сделайте Out-of-Fold предсказания для обучающей выборки. Посчитайте ошибки и посмотрите на их распределение (plt.hist). Что вы видите?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попробуйте удалить объекты-выбросы из обучающей выборки (что считать или не считать выбросами на ваше усмотрение). Обучите модель заново и посмотрите на качество на отложенной выборке (учитывайте, что там тоже могут быть выбросы, с которыми вы ничего не можете сделать). Стало ли лучше? Чем вы можете объяснить это?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 2. Логистическая регрессия"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части мы будем реализовывать один из самых простых бинарных классификаторов — логистическую регрессию и её обучение с помощью обычного (полного) и стохастического градиентных спусков.\n",
    "\n",
    "Если кратко, то обучение логистической регрессии с $L_2$-регуляризацией можно записать следующим образом:\n",
    "\n",
    "$$\n",
    "Q(w, X) = \\frac{1}{l} \\sum_{i=1}^{l} \\log (1 + \\exp(- y_i \\langle w, x_i \\rangle )) + \\frac{\\lambda_2}{2} \\lVert w \\rVert _2^2 \\to \\min_w\n",
    "$$\n",
    "\n",
    "Считаем, что $y_i \\in \\{-1, +1\\}$, а нулевым признаком сделан единичный (то есть $w_0$ соответствует свободному члену). Искать $w$ будем с помощью градиентного спуска:\n",
    "\n",
    "$$\n",
    "w^{(k+1)} = w^{(k)} - \\alpha \\nabla_w Q(w, X)\n",
    "$$\n",
    "\n",
    "В случае полного градиентного спуска $\\nabla_w Q(w, X)$ считается напрямую (как есть, то есть, используя все объекты выборки). В случае стохастического градиентного спуска $\\nabla_w Q(w, X) \\approx \\nabla_w q_{i_k} (w)$, где $i_k$ — случайно выбранный номер слагаемого из функционала (регуляризатор можно внести в сумму, предварительно умножив и разделив на $l$). Длину шага $\\alpha > 0$ в рамках данного задания предлагается брать равной некоторой малой константе.\n",
    "\n",
    "Формулу для градиента функции потерь логистической регрессии вы должны были выводить в рамках одной из задач четвёртого теоретического домашнего задания. Но на всякий случай мы её повторим. Градиент по объекту $x_i$ считается по следующей формуле:\n",
    "\n",
    "$$\n",
    "\\nabla_w Q(w, x_i) = - \\frac{y_i x_i}{1 + \\exp(y_i \\langle w, x_i \\rangle)} + \\lambda_2 w\n",
    "$$\n",
    "\n",
    "На самом деле неправильно регуляризировать свободный член $w_0$ (то есть при добавлении градиента для $w_0$ не надо учитывать слагаемое с $\\lambda_2$). Но в рамках этого задания мы не обращаем на это внимания и работаем со всеми вектором весов одинаково. \n",
    "\n",
    "В качестве критерия останова необходимо использовать (одновременно):\n",
    "- проверку на евклидовую норму разности весов на двух соседних итерациях (например, меньше некоторого малого числа порядка $10^{-6}$) — параметр tolerance\n",
    "- достижение максимального числа итераций (например, 10000) — параметр max\\_iter.\n",
    "\n",
    "Инициализировать веса можно случайным образом или нулевым вектором.\n",
    "\n",
    "Вероятность принадлежности объекта $x$ классу $+1$ вычисляется следующим образом:\n",
    "\n",
    "$$\n",
    "P(y = +1 | x) = \\frac{1}{1 + \\exp(- \\langle w, x \\rangle )}\n",
    "$$\n",
    "\n",
    "Не забывайте, что матрицу объекты-признаки $X$ необходимо предварительно нормировать (то есть привести каждый признак к одному и тому же масштабу одним из 2 способов, разобранных на лекциях). Для этого можно воспользоваться StandardScaler или сделать это вручную.\n",
    "\n",
    "В логистической регрессии также можно использовать $L_1$-регуляризацию. Тогда в функцию потерь добавится слагаемое $\\lambda_1 \\lVert w \\rVert _1$. В формуле для вычисления градиента фукнции потерь по вектору коэффициентов это слагаемое будет соответствовать $\\lambda_1 sgn(w)$, где $sgn$ — вычисление знака числа, применяемое к вектору коэффициентов поэлементо."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 1.__ Реализация обучения и применения логистической регресии c $L_2$-регуляризацией. \n",
    "\n",
    "**(2.5 балла)**\n",
    "\n",
    "Используйте для этого указанные ниже прототипы. Для эффективности все вычисления производите в векторизованной форме без циклов (кроме самих итераций градиентного спуска). Сгенерируйте с помощью функции make\\_classification из модуля sklearn.datasets небольшую выборку для тестирования и исследования (выборка не должна быть слишком простой для классификации; также не забудьте проверить, что метки объектов из необходимого нам множества). Постройте следующие графики (для полного и стохастического градиентного спуска на одном графике):\n",
    "- функции потерь от номера итерации обучения\n",
    "- затраченного времени от номера итерации обучения\n",
    "\n",
    "Возьмите параметр регуляризации $\\lambda_2=1$, точность $tolerance=10^{-6}$, максимальное число итераций $max\\_iter=1000$. Подберите оптимальную на ваш взгляд величину шага градиентного спуска. \n",
    "\n",
    "Сделайте выводы о том, чем различается на практике обучение с помощью стохастического градиентного спуска по сравнению с полным градиентным спуском.\n",
    "\n",
    "В этом задании не обращайте внимания на $\\lambda_1$, соответствующий $L_1$-регуляризации.\n",
    "\n",
    "Для численной устойчивости вам могут быть полезны функции: scipy.special.expit и numpy.logaddexp.\n",
    "\n",
    "__Важно:__ код с реализацией логистической регрессии необходимо также отправить на проверку в Яндекс.контест (ссылка [раз](https://official.contest.yandex.ru/contest/5704/problems/) и [альтернативная](https://contest.yandex.ru/contest/5704/problems/)). Не забывайте про pep8. \n",
    "\n",
    "ID посылки: ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Бонусное задание.__ Реализация $L_1$-регуляризации и обучение с помощью субградиентного спуска.\n",
    "\n",
    "__(1.0 балла)__\n",
    "\n",
    "Модифицируйте реализацию так, чтобы можно было обучать логистическиую регрессию с $L_1$-регуляризацией (и даже одновременно с двумя видами). Проведите аналогичные эксперименты, считая $\\lambda_1 = 0.001, \\lambda_2 = 0$.\n",
    "\n",
    "Стоит помнить, что модуль — недифференцируемая в нуле функция, поэтому мы не можем применить обычный градиентный спуск. Вместо этого будем применить субградиентный спуск — аналогичный градиентному спуску метод, в котором используется субградиент функции. \n",
    "\n",
    "Вектор $g \\in \\mathbb{R}$ называется субградиентом выпуклой функции $f$ в точке $x$, если $\\forall z \\in \\mathbb{R}$ выполнено неравенство: $f(z) \\ge f(x) + g^T (z-x)$. Если функция $f$ дифференцируема в точке $x$, её субградиент в этой точке совпадает с градиентом. Субдифференциалом функции $f$ называют множество субградиентов в этой точке.\n",
    "\n",
    "Для $f(x) = |x|$ при $x = 0$ субдифференциал определяется неравенством $|z| \\ge gz$, поэтому $g \\in [-1, 1]$. \n",
    "\n",
    "На практике для стабильности процесса обучения для близких к нулю значений можно уменьшать градиент, умножая на небольшое число (например, 0.1-0.5) или делая его нулевым (только околонулевые координаты!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "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):\n",
    "        \"\"\"\n",
    "        lambda_1: L1 regularization param\n",
    "        lambda_2: L2 regularization param\n",
    "        gd_type: 'full' or 'stochastic'\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",
    "        \"\"\"\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": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here too\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Выводы:__ ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 2.__ Обучение логистической регрессии на реальных данных и оценка качества классификации.\n",
    "\n",
    "**(1 балл)**\n",
    "\n",
    "Полезные функции и классы из scikit-learn для этого задания: confusion_matrix, precision_recall_curve, average_precision_score, train_test_split, StandardScaler, roc-curve, roc_auc_score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Загрузим данные с актуального сейчас конкурса [Kaggle Porto Seguro’s Safe Driver Prediction](https://www.kaggle.com/c/porto-seguro-safe-driver-prediction) (вам нужна только обучающая выборка). Задача состоит в определении водителей, которые в ближайший год воспользуются своей автомобильной страховкой (бинарная классификация). Но для нас важна будет не сама задача, а только её данные. При этом под нужды задания мы немного модифицируем датасет."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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": "markdown",
   "metadata": {},
   "source": [
    "Пересемплируем выборку так, чтобы положительных и отрицательных объектов в выборке было одинаковое число. Разделим на обучающую и тестовую выборки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# some resampling\n",
    "np.random.seed(910)\n",
    "mask_plus = np.random.choice(np.where(target == 1)[0], 100000, replace=True)\n",
    "mask_zero = 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.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Не забудьте отнормировать признаки (можно воспользоваться StandardScaler или сделать это вручную). Пока не будем обращать внимание на то, что некоторые признаки категориальные (этим мы займёмся позже)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обучите логистическую регрессию с удобными для вас параметрами. Сделайте предсказание на тестовой части выборки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Постройку ROC-кривую и Precision-Recall-кривую, посчитайте ROC-AUC и PR-AUC. Какие наблюдения и выводы по ним можно сделать? (В свободной форме)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Предположим, что наш алгоритм должен обеспечивать полноту не менее 0.7. Какому порогу бинаризации вероятностей это будет соответствовать? Какую точность (precision) мы получим? Постройте матрицу ошибок для данного порога. Что вы можете сказать о таком алгоритме? (В свободной форме)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 3.__ Изучение влияния регуляризатора на процесс обучения\n",
    "\n",
    "__(0.5 балла)__\n",
    "\n",
    "Проверьте на практике, как влияет регуляризатор на процесс обучения (убывание функции потерь на обучающей и отложенной выборках). Чтобы считать функцию потерь на отложенной выборке после каждой итерации, запускайте процесс обучения логистической регрессии с параметром $max\\_iter=1$ и $w^{(0)}$, полученным на предыдущей итерации. Постройте два графика: на одном из них логистическая регрессия с коэффициентом регуляризации, равным 0, а на другом с некоторым разумным значением. На каждом графике одновременно должна быть и функция потерь для обучающей, и для тестовой выборки. Не забудьте сделать одинаковыми оси обоих графиков. Какие выводы вы можете сделать?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 3. Метод опорных векторов и калибровка вероятностней"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 1.__ Обучение и применение метода опорных векторов.\n",
    "\n",
    "__(1 балл)__\n",
    "\n",
    "Обучите метод опорных векторов (в этот раз воспользуйтесь готовой реализацией LinearSVC из sklearn). Используйте уже загруженные и обработанные в предыдущей части данные."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На той же тестовой части посчитайте все те же метрики. Что вы можете сказать о полученных результатах?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В названии метода присутствуют некоторые \"опорные векторы\". Сгенерируйте синтетический датасет с помощью make_classification с 2 признаками, обучите на нём метод опорных векторов с линейным ядром. Визуализируйте разделяющую прямую, все объекты и выделите опорные вектора (атрибут support\\_vectors\\_). В этот раз вместо LinearSVC воспользуйтесь SVC с линейным ядром, так как только в нём есть информация об опорных векторах."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задание 2.__ Калибровка вероятностей.\n",
    "\n",
    "__(1 балл)__\n",
    "\n",
    "Перейдём к оценке качества выдаваемых алгоритмами вероятностей. Начнём с калибровочных кривых. \n",
    "\n",
    "Допустим, алгоритм возвращает некоторые числа от нуля до единицы. Хорошо ли они оценивают вероятность? Для этого разобьем отрезок $[0, 1]$ на несколько маленьких отрезков одинаковой длины. Рассмотрим $i$-й отрезок с границами $[a_i, b_i]$ и предсказания $p_1, p_2, \\dots, p_k$, которые попали в него. Пусть им соответствуют истинные ответы $y_1, y_2, \\dots, y_k$. Если алгоритм выдает корректные вероятности, то среди этих истинных ответов должно быть примерно $(a_i + b_i) / 2$ единиц. Иными словами, если нарисовать кривую, у которой по оси X отложены центры отрезков, а по оси Y — доли единичных ответов этих в отрезках, то она должна оказаться диагональной. Ниже приведена функция, которая должна рисовать такие кривые. В ней допущено две ошибки — найдите и исправьте их."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def plot_calibration_curve(y_test, preds):\n",
    "    bin_middle_points = []\n",
    "    bin_real_ratios = []\n",
    "    n_bins = 20\n",
    "    for i in range(n_bins):\n",
    "        l = 1.0 / n_bins * i\n",
    "        r = 1.0 / n_bins * (i + 1)\n",
    "        bin_middle_points.append((l - r) / 2)\n",
    "        bin_real_ratios.append(np.min(y_test[(preds >= l) & (preds < r)] == 1))\n",
    "    plt.plot(bin_middle_points, bin_real_ratios)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотройте калибровочные кривые для логистической регрессии и метода опорных векторов (на той же самой выборке с тем же самым разбиением — можно использовать уже полученные ранее предсказания). Изучите распределение ответов классификаторов (постройте гистограммы с помощью plt.hist). Чем они различаются? Чем вы можете объяснить это?\n",
    "\n",
    "Заметим, что метод опорных векторов не умеет predict_proba, но имеет метод decision_function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Воспользуйтесь CalibratedClassifierCV из sklearn для калибровки вероятностей метода опорных векторов на обучении и постройте с его помощью предсказания для тестовой выборки. Нарисуйте для них калибровочную кривую. Улучшилась ли она?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Бонусное задание (1 балл).__ Реализуйте свою функцию для калибровки вероятностей. Опишите ваш подход и продемонстрируйте результаты."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 4. Работа с категориальными переменными"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части мы научимся обрабатывать категориальные переменные, так как закодировать их в виде чисел недостаточно (это задаёт некоторый порядок, которого на категориальных переменных может и не быть). Существует два основных способа обработки категориальных значений:\n",
    "- One-hot-кодирование\n",
    "- Счётчики (CTR, mean-target кодирование, ...) — каждый категориальный признак заменяется на среднее значение целевой переменной по всем объектам, имеющим одинаковое значение в этом признаке.\n",
    "\n",
    "Начнём с one-hot-кодирования. Допустим наш категориальный признак $f_j(x)$ принимает значения из множества $C=\\{c_1, \\dots, c_m\\}$. Заменим его на $m$ бинарных признаков $b_1(x), \\dots, b_m(x)$, каждый из которых является индикатором одного из возможных категориальных значений:\n",
    "$$\n",
    "b_i(x) = [f_j(x) = c_i]\n",
    "$$\n",
    "\n",
    "__Задание 1.__ Закодируйте все категориальные признаки с помощью one-hot-кодирования. Обучите логистическую регрессию и посмотрите, как изменилось качество модели (с тем, что было ранее). Измерьте время, потребовавшееся на обучение модели.\n",
    "\n",
    "__(0.5 балла)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как можно было заменить, one-hot-кодирование может сильно увеличивать количество признаков в датасете, что сказывается на памяти, особенно, если некоторый признак имеет большое количество значений. Эту проблему решает другой способ кодирование категориальных признаков — счётчики. Основная идея в том, что нам важны не сами категории, а значения целевой переменной, которые имеют объекты этой категории. Каждый категориальный признак мы заменим средним значением целевой переменной по всем объектам этой же категории:\n",
    "$$\n",
    "g_j(x, X) = \\frac{\\sum_{i=1}^{l} [f_j(x) = f_j(x_i)][y_i = +1]}{\\sum_{i=1}^{l} [f_j(x) = f_j(x_i)]}\n",
    "$$\n",
    "\n",
    "__Задание 2.__ Закодируйте категориальные переменные с помощью счётчиков (ровно так, как описано выше без каких-либо хитростей). Обучите логистическую регрессию и посмотрите на качество модели на тестовом множестве. Сравните время обучения с предыдущим экспериментов. Заметили ли вы что-то интересное?\n",
    "\n",
    "__(1 балл)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отметим, что такие признаки сами по себе являются классификаторами и, обучаясь на них, мы допускаем \"утечку\" целевой переменной в признаки. Это ведёт к переобучению, поэтому считать такие признаки необходимо таким образом, чтобы при вычислении для конкретного объекта его целевая метка не использовалась. Это можно делать следующими способами:\n",
    "- вычислять значение счётчика по всем объектам расположенным выше в датасете (например, если у нас выборка отсортирована по времени)\n",
    "- вычислять по фолдам, то есть делить выборку на некоторое количество частей и подсчитывать значение признаков по всем фолдам кроме текущего (как делается в кросс-валидации)\n",
    "- внесение некоторого шума в посчитанные признаки. \n",
    "\n",
    "__Задание 3.__ Реализуйте корректное вычисление счётчиков самым простым способом — добавление шума к значениям (необходимо соблюсти баланс между избавление от переобучения и полезностью признаков). Снова обучите логистическую регрессию, оцените качество. Сделайте выводы.\n",
    "\n",
    "__(0.25 балла)__\n",
    "\n",
    "__(Бонусная часть)__ Посчитайте корректные счётчики одним из двух способов описанных выше (не забудьте добавить и шум). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А теперь ответьте на следующий вопрос: что будет, если некоторая категория встречается в выборке всего несколько раз? По этой причине производится сглаживание счётчиков. Например, на практике хорошие результаты показывает использование сглаживания средним по всей выборке:\n",
    "$$\n",
    "g_j(x, X) = \\frac{\\sum_{i=1}^{l} [f_j(x) = f_j(x_i)][y_i = +1] + C * global\\_mean}{\\sum_{i=1}^{l} [f_j(x) = f_j(x_i)] + C}\n",
    "$$\n",
    "где $global\\_mean$ — среднее значение целевой переменной по всей выборке, $C$ — параметр, определяющий степень сглаживания (например, можно использовать 10 или подобрать для каждого признака свой). Основная идея в том, что мы \"разбавляем\" среднее значение по некоторой категории глобальным средним значении. И тем меньше, чем большее количество объектов этой категории встречается в выборке. \n",
    "\n",
    "Однако для сглаживания вместо среднего значения целевой переменной можно использовать любое другое значение от 0 до 1 (этот параметр иногда называют $prior$). Можно сделать несколько признаков с разными значениями параметра. На практике в задачах бинарной классификации полезными бывают даже отрицательные значения!\n",
    "\n",
    "__Задание 4.__ Добавьте сглаживание, описанное выше и повторите эксперименты.\n",
    "\n",
    "__(0.75 балла)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Замечание.__ Усложнение методов вычисления счётчиков не делают результаты модели гарантированно лучше. Особенно с учётом того, что логистическая регрессия не такая сложная модель, чтобы переобучаться. Поэтому вы необязательно должны были получать на каждом шаге всё лучшие и лучшие результаты (но необходимые результаты у вас должны были получиться).\n",
    "\n",
    "Как вы должны были заметить, счётчики являются хорошей альтернативой one-hot-кодированию. Напишите, какие плюсы и минусы использования счётчиков по сравнению с one-hot-кодированием, вы заметили.\n",
    "\n",
    "__Ответ:__ ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 5.** Какой лучший мем в 2k17?\n",
    "\n",
    "__Ответ:__ ...\n",
    "\n",
    "\n",
    "**Задание 6.** Поделитесь лучшим стикерпаком. Только там не должно быть преподавателей и ассистентов этого курса.\n",
    "\n",
    "__Ответ:__ ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 5 (бонус). Vowpal Wabbit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части мы научимся использовать библиотеку [vowpal wabbit](https://github.com/JohnLangford/vowpal_wabbit). У неё есть несколько особенностей:\n",
    "- можно обучать только линейные модели, но за счёт большого количества опций и возможностей по усложнению, можно построить и довольно сложные вещи\n",
    "- можно обучаться на выборках, которые не помещаются в оперативную память\n",
    "- можно обрабатывать большое количество признаков (например, мешки слов текстов) и \"на ходу\" строить на них комбинации (не переделывать датасет)\n",
    "- другие особенности, как например, активное обучение и возможность распараллеленного обучения.\n",
    "\n",
    "Основные особенности при использовании следующие:\n",
    "- Свой формат данных: \"label |A feature1:value1 |B feature2:value2\", позволяющий, во-первых, указывать не все признаки (не нужно хранить много нулей в разреженных данных), а во-вторых, группировать и иметь возможность отключать или взаимодействовать (\"отключать\", добавлять квадратичные признаки и т.д.) сразу со всей группой признаков. По этой причине вам понадобится реализовать конвертер датасета и загрузку своих предсказаний, чтобы посчитать качество предсказаний.\n",
    "- Запуск обучения из командной строки (однако можно запускать эти же команды из ноутбука).\n",
    "\n",
    "В этот раз мы будем использовать данные с конкурса [Kaggle Avazu Click-Through Rate Prediction](https://www.kaggle.com/c/avazu-ctr-prediction) по предсказанию кликов (бинарная классификация). В обучающей выборке 40kk строк, так что у вас не должно быть желания загружать их в оперативную память. Предлагается взять первые 30kk строк в качестве обучающей выборке и оставшуюся часть для тестирования.\n",
    "\n",
    "__Задание 1.__ Работа с vowpal wabbit. \n",
    "\n",
    "- Скачайте данные, разделите их на обучающую и тестовую выборки.\n",
    "- Подготовьте функции для конвертирования датасета в формат vowpal wabbit и для загрузки предсказаний в ноутбук для подсчёта функционала.\n",
    "- Сделайте простейшее решение на vowpal wabbit. Оцените качество.\n",
    "- Изучите возможности и параметры vowpal wabbit. Поэксперементируйте. \n",
    "- Расскажите, что интересного вы узнали (какие-нибудь особенности, режимы работы, фишки, параметры).\n",
    "- Удалось ли вам улучшить качество базовой модели? Насколько? Что ещё можно было бы попробовать?\n",
    "\n",
    "В этом задании предусмотрены баллы по двум критериям:\n",
    "- достижение ROC-AUC на отложенной выборки более 0.738 __(1 балл)__\n",
    "- несколько занимательных фактов и возможностей vowpal-wabbit __(0.5 балла)__."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "# ..."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py36",
   "language": "python",
   "name": "py36"
  },
  "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}