2019-fall/homeworks-practice/homework-practice-06.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Машинное обучение, ФКН ВШЭ\n",
    "\n",
    "## Практическое задание 6. Разложение ошибки на смещение и разброс\n",
    "\n",
    "### Общая информация\n",
    "\n",
    "Дата выдачи: 23.11.2019\n",
    "\n",
    "Мягкий дедлайн: 8:00MSK 01.12.2019\n",
    "\n",
    "Жесткий дедлайн: 23:59MSK 02.12.2019\n",
    "\n",
    "### Оценивание и штрафы\n",
    "Каждая из задач имеет определенную «стоимость» (указана в скобках около задачи). Максимально допустимая оценка за работу — 10 баллов.\n",
    "\n",
    "Сдавать задание после указанного срока сдачи нельзя. При выставлении неполного балла за задание в связи с наличием ошибок на усмотрение проверяющего предусмотрена возможность исправить работу на указанных в ответном письме условиях.\n",
    "\n",
    "Задание выполняется самостоятельно. «Похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) не могут получить за него больше 0 баллов (подробнее о плагиате см. на странице курса). Если вы нашли решение какого-то из заданий (или его часть) в открытом источнике, необходимо указать ссылку на этот источник в отдельном блоке в конце вашей работы (скорее всего вы будете не единственным, кто это нашел, поэтому чтобы исключить подозрение в плагиате, необходима ссылка на источник).\n",
    "\n",
    "Неэффективная реализация кода может негативно отразиться на оценке.\n",
    "\n",
    "### Формат сдачи\n",
    "Задания сдаются через систему anytask. Посылка должна содержать:\n",
    "* Ноутбук homework-practice-06-Username.ipynb\n",
    "\n",
    "Username — ваша фамилия и имя на латинице именно в таком порядке\n",
    "\n",
    "### О задании\n",
    "\n",
    "В этом задании вам предстоит воспользоваться возможностями bootstraping для оценки смещения и разброса алгоритмов машинного обучения. Делать мы это будем на данных boston:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from matplotlib import pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_boston"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "boston = load_boston()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X = boston[\"data\"]\n",
    "y = boston[\"target\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((506, 13), (506,))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape, y.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Вычисление bias и variance с помощью бутстрапа\n",
    "На лекции была выведено следующая формула, показывающая, как можно представить ошибку алгоритма регрессии в виде суммы трех компонент:\n",
    "$$\n",
    "L(\\mu) = \n",
    "    \\mathbb{E}_{x, y}\\bigl[\\mathbb{E}_{X}\\bigl[ (y - \\mu(X)(x))^2 \\bigr]\\bigr] = \n",
    "$$\n",
    "$$\n",
    "    \\underbrace{\\mathbb{E}_{x, y}\\bigl[(y - \\mathbb{E}[y|x] )^2\\bigr]}_{\\text{шум}} + \\underbrace{\\mathbb{E}_{x}\\bigl[(\\mathbb{E}_{X}[\\mu(X)(x)] - \\mathbb{E}[y|x] )^2\\bigr]}_{\\text{смещение}} +\n",
    "    \\underbrace{\\mathbb{E}_{x}\\bigl[\\mathbb{E}_{X}\\bigl[(\\mu(X)(x) - \\mathbb{E}_{X}[\\mu(X)(x)] )^2\\bigr]\\bigr]}_{\\text{разброс}},\n",
    "$$\n",
    "* $\\mu(X)$ — алгоритм, обученный по выборке $X = \\{(x_1, y_1), \\dots (x_\\ell, y_\\ell)\\}$;\n",
    "* $\\mu(X)(x)$ — ответ алгоритма, обученного по выборке $X$, на объекте $x$;\n",
    "* $\\mathbb{E}_{X}$ — мат. ожидание по всем возможным выборкам;\n",
    "* $\\mathbb{E}_{X}[\\mu(X)(x)]$ — \"средний\" ответ алгоритма, обученного по всем возможным выборкам $X$, на объекте $x$.\n",
    "    \n",
    "С помощью этой формулы мы можем анализировать свойства алгоритма обучения модели $\\mu$, если зададим вероятностную модель порождения пар $p(x, y)$.\n",
    "\n",
    "В реальных задачах мы, конечно же, не знаем распределение на парах объект - правильный ответ. Однако у нас есть набор семплов из этого распределения (обучающую выборка), и мы можем использовать его, чтобы оценивать математические ожидания. Для оценки мат. ожиданий по выборкам мы будем пользоваться бутстрэпом - методом генерации \"новых\" выборок из одной с помощью выбора объектов с возвращением. Разберем несколько шагов на пути к оценке смещения и разброса.\n",
    "\n",
    "#### Приближенное вычисление интегралов\n",
    "На занятиях мы разбирали примеры аналитического вычисления смещения и разброса нескольких алгоритмов обучения. Для большинства моделей данных и алгоритмов обучения аналитически рассчитать математические ожидания в формулах не удастся. Однако мат. ожидания можно оценивать приближенно. Чтобы оценить математическое ожидание $\\mathbb{E}_{\\bar z} f(\\bar z)$ функции от многомерной случайной величины $\\bar z = (z_1, \\dots, z_d)$, $\\bar z \\sim p(\\bar z)$, можно сгенерировать выборку из распределения $p(\\bar z)$ и усреднить значение функции на элементах этой выборки:\n",
    "$$\\mathbb{E}_{\\bar z} f(z) = \\int f(\\bar z) p(\\bar z) d \\bar z \\approx \\frac 1 m \\sum_{i=1}^m f(\\bar z_i), \\, \\bar z_i \\sim p(\\bar z), i = 1, \\dots, m.$$\n",
    "\n",
    "Например, оценим $\\mathbb{E}_z z^2,$ $z \\sim \\mathcal{N}(\\mu=5, \\sigma=3)$ (из теории вероятностей мы знаем, что\n",
    "$\\mathbb{E}_z z^2 = \\sigma^2 + \\mu^2 = 34$):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "33.932175246772296"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = np.random.normal(loc=5, scale=3, size=1000)\n",
    "(z**2).mean()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Оценивание $\\mathbb{E}_{x, y}$\n",
    "Оценить мат. ожидания по $x$ и по $x, y$, встречающиеся во всех трех компонентах разложения, несложно, потому что у нас есть выборка объектов из распределения данных $p(x, y)$:\n",
    "$$ \\mathbb{E}_{x} f(x) \\approx \\frac 1 N \\sum_{i=1}^N f(x_i), \\quad\n",
    "\\mathbb{E}_{x, y} f(x, y) \\approx \\frac 1 N \\sum_{i=1}^N f(x_i, y_i),$$\n",
    "где $N$ - число объектов в выборке, $\\{(x_i, y_i)\\}_{i=1}^N$ - сама выборка. \n",
    "\n",
    "#### Оценивание $\\mathbb{E}_X$ с помощью бутстрапа\n",
    "Чтобы оценить мат. ожидание по $X$, нам понадобится выборка из выборок:\n",
    "$$\\mathbb{E}_X f(X) \\approx \\frac 1 s \\sum_{j=1}^s f(X_j),$$\n",
    "где $X_j$ - $j$-я выборка. Чтобы их получить, мы можем воспользоваться бутстрапом - методом генерации выборок на основе выбора объектов с возвращением. Чтобы составить одну выборку, будем $N$ раз выбирать индекс объекта $i \\sim \\text{Uniform}(1 \\dots N)$ и добавлять $i$-ю пару (объект, целевая переменная) в выборку. В результате в каждой выборке могут появиться повторяющиеся объекты, а какие-то объекты могут вовсе не войти в некоторые выборки.\n",
    "\n",
    "#### Итоговый алгоритм оценки смещения и разброса алгоритма $a$\n",
    "1. Сгенерировать $s$ выборок $X_j$ методом бутстрапа.\n",
    "1. На каждой выборке $X_j$ обучить алгоритм $a_j$.\n",
    "1. Для каждой выборки $X_j$ определить множество объектов $T_j$, не вошедших в нее (out-of-bag). Вычислить предсказания алгоритма $a_j$ на объектах $T_j$. \n",
    "\n",
    "Поскольку у нас есть только один ответ для каждого объекта, мы будем считать шум равным 0, а $\\mathbb{E}[y|x]$ равным имеющемуся правильному ответу для объекта $x$. \n",
    "\n",
    "Итоговые оценки:\n",
    "* Смещение: для одного объекта - квадрат разности среднего предсказания и правильного ответа. Среднее предсказание берется только по тем алгоритмам $a_j$, для которых этот объект входил в out-of-bag выборку $T_j$. Для получения общего смещения выполнить усреденение смещений по объектам.\n",
    "* Разброс: для одного объекта - выборочная дисперсия предсказаний алгоритмов $a_j$, для которых этот объект входил в out-of-bag выборку $T_j$. Для получения общего разброса выполнить усреденение разбросов по объектам.\n",
    "* Ошибка $L$: усреднить квадраты разностей предсказания и правильного ответа по всем выполненным предсказаниям для всех объектов.\n",
    "\n",
    "В результате должно получиться, что ошибка приблизительно равна сумме смещения и разброса!\n",
    "\n",
    "Алгоритм также вкратце описан по [ссылке](https://web.engr.oregonstate.edu/~tgd/classes/534/slides/part9.pdf) (слайды 19-21).\n",
    "\n",
    "__1. (3 балла)__\n",
    "\n",
    "Реализуйте описанный алгоритм. Обратите внимание, что если объект не вошел ни в одну из out-of-bag выборок, учитывать его в вычислении итоговых величин не нужно. Как обычно, разрешается использовать только один цикл - по выборкам (от 0 до num_runs-1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_biase_variance(regressor, X, y, num_runs=1000):\n",
    "    \"\"\"\n",
    "    :param regressor: sklearn estimator with fit(...) and predict(...) method\n",
    "    :param X: numpy-array representing training set ob objects, shape [n_obj, n_feat]\n",
    "    :param y: numpy-array representing target for training objects, shape [n_obj]\n",
    "    :param num_runs: int, number of samples (s in the description of the algorithm)\n",
    "    \n",
    "    :returns: bias (float), variance (float), error (float) \n",
    "    each value is computed using bootstrap\n",
    "    \"\"\"\n",
    "    ### your code here\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2. (0 баллов)__\n",
    "\n",
    "Оцените смещение, разброс и ошибку для трех алгоритмов с гиперпараметрами по умолчанию: линейная регрессия, решающее дерево, случайный лес."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__3. (1 балл)__\n",
    "Проанализируйте полученный результат. Согласуются ли полученные результаты с теми, что мы обсуждали на семинарах (с комментарием)?\n",
    "\n",
    "__Your answer here:__\n",
    "\n",
    "__3. (1 балл)__\n",
    "Вспомните обсуждение с лекции о том, во сколько раз в теории бутстрап уменьшает разброс базового алгоритма. Выполняется ли это в ваших экспериментах? Если нет, поясните, почему.\n",
    "\n",
    "__Your answer here:__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Визуализация предсказаний базовых алгоритмов бэггинга\n",
    "\n",
    "В материалах лекций можно найти изображение, похожее на мишень - визуализация алгоритмов с разным смещением и разным разбросом. В центре \"мишени\" - правильный ответ, а \"попадания\" - предсказания алгоритмов, обученных по разным выборкам. Построим похожее изображение на наших данных для трех алгоритмов. Наши \"мишени\" будут одномерными, потому что мы решаем задачу одномерной регрессии.\n",
    "\n",
    "__4. (2 балла)__\n",
    "\n",
    "Реализуйте фукнцию plot_predictions. Она должна выполнять следующие действия:\n",
    "1. Случайно выбрать num_test_objects пар объект-целевая переменная из выборки X, y. Получится две выборки: маленькая X_test, y_test (выбранные тестовые объекты) и X_train, y_train (остальные объекты).\n",
    "1. Сгенерировать num_runs выборок методом бутстарапа из X_train, y_train. На каждой выборке обучить алгоритм regressor и сделать предсказания для X_test.\n",
    "1. Нарисовать scatter-график. По оси абсцисс - объекты тестовой выборки (номера от 0 до num_test_objects-1), по оси ординат - предсказания. В итоге получится num_test_objects столбиков с точками. Для каждого тестового объекта надо отметить одним цветом все предсказания для него, а также черным цветом отметить правильный ответ.\n",
    "1. Подпишите оси и название графика (аргумент title)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def plot_predictions(regressor, X, y, num_runs=100, num_test_objects=10, title=\"\"):\n",
    "    \"\"\"\n",
    "    plot graphics described above\n",
    "    \"\"\"\n",
    "    ### your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__5. (0 баллов)__\n",
    "\n",
    "Нарисуйте графики для линейной регрессии, решающего дерева и случайного леса. Нарисуйте три графика в строчку (это можно сделать с помощью plt.subplot) с одинаковой осью ординат (это важно для понимания масштаба разброса у разных алгоритмов):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__6. (1 балл)__\n",
    "\n",
    "Для каждого графика прокомментируйте, как он характеризует смещение и разброс соответствующего алгоритма. \n",
    "\n",
    "__Your answer here:__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Изменение bias и variance при изменении гиперпараметров"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__7. (0 баллов)__\n",
    "\n",
    "Постройте графики зависимости смещения и разброса от гиперпараметров решающего дерева max_depth (от 1 до 10) и max_features (от 1 до X.shape[1]):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__8. (0 баллов)__\n",
    "\n",
    "Постройте графики зависимости смещения и разброса от n_estimators (по сетке 2**np.arange(1, 10)) для случайного леса и градиентного бустинга:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__3. (2 балла)__\n",
    "\n",
    "Прокомментируйте графики (всего 4 графика): почему они имеют такой вид.\n",
    "\n",
    "__Your answer here:__"
   ]
  }
 ],
 "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.6.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}