{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine Learning\n",
    "\n",
    "*Екатерина Лобачева / Илья Щуров / Сергей Сметанин *\n",
    "\n",
    "*Совместный бакалавриат НИУ ВШЭ и РЭШ, 2016-17 учебный год*\n",
    "\n",
    "[Страница курса](http://math-info.hse.ru/2016-17/Machine_Learning)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Домашнее задание №ML5\n",
    "\n",
    "Чтобы выполнить работу, скачайте настоящий ipynb-файл, откройте его в *Jupyter Notebook*, впишите решения в оставленные для этого ячейки (при необходимости можно добавлять новые ячейки), приводя полный работающий код, а также все необходимые пояснения и ответы (для этого нужно использовать markdown-ячейки). Вы можете вставлять формулы с помощью TeX-разметки в markdown-ячейки. После выполнения работы необходимо вытащить ipynb-файл из Jupyter (например, с помощью *File → Download as… → IPython Notebook*) и загрузить его на my.NES."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Setting\n",
    "\n",
    "Это ДЗ посвящено решающим деревьям (decision trees) и разложению ошибок на смещение (bias) и разброс (variance). Оно частично основано на [этой практической работе](https://github.com/esokolov/ml-course-hse/blob/master/2016-fall/homeworks-practice/homework-practice-03-ensembles.ipynb). См. также раздел 2 в [этом](https://github.com/esokolov/ml-course-hse/blob/master/2016-fall/lecture-notes/lecture08-ensembles.pdf) конспекте.\n",
    "\n",
    "Пусть имеется функция $y=f(x)$, задающая истинную связь между $x\\in \\mathbb X$ и $y\\in \\mathbb Y$. Очередной элемент данных $(x_i, y_i)$ генерируется следующим образом: сначала выбирается случайный элемент $x_i$ (в соответствии с некоторым распределением, заданным на $\\mathbb X$). Затем вычисляется $y_i = f(x_i)+\\varepsilon_i$, где $\\varepsilon_i$ — случайный шум, выбирающийся из ещё какого-то распределения. Повторяя эту операцию много раз, мы можем получить выборку любого заданного размера. Заметим, что свойства получающихся выборок зависят не только от функции $f$, но и от выбранных распределений.\n",
    "\n",
    "### Задача 1\n",
    "Пусть $\\mathbb X=\\mathbb R_+$, $f(x)=\\sin(x)$, распределение на $\\mathbb X$ — экспоненциальное с $\\lambda=1$ (`np.random.exponential`), случайный шум выбирается из равномерного распределения на отрезке $[-1, 1]$ (`np.random.uniform` — нужно указать правильно параметры).\n",
    "\n",
    "Написать функцию `make_sample(size)`, генерирующую выборку длины `size`. Она должна возвращать пару `(X, y)`, где `X` и `y` можно было бы использовать для обучения регрессоров `sklearn` (то есть `X` и `y` должны быть вектор-столбцами — можно использовать метод `.reshape(-1, 1)`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# вставьте решение сюда"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 2\n",
    "1. Сгенерируйте с помощью функции из предыдущей задачи выборку длины 100. \n",
    "2. Обучите `sklearn.tree.DecisionTreeRegressor` с параметрами по умолчанию на полученной выборке. Сделайте предсказание для объектов из `np.linspace(0, 7, 1000)`. \n",
    "3. Постройте на одном рисунке:\n",
    "    - Истинную зависимость $y=f(x)$ (линией).\n",
    "    - Выборку (в виде отдельных точек, можно использовать `'o'` в качестве третьего параметра для `plt.plot`).\n",
    "    - Зависимость, восстановленную решающим деревом (линией)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# вставьте решение сюда"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 3\n",
    "Повторите шаги 1 и 2 из предыдущей задачи 20 раз. На одном графике для каждого обученного решающего дерева визуализируйте восстановленную им зависимость (рекомендуется все такие линии рисовать полупрозрачными и серым цветом: `plt.plot(...... color=\"gray\", alpha=0.5)`). На этом же графике изобразите истинную зависимость `f(x)` (красным цветом: `color=\"red\"`) и усредненную по всем деревьям восстановленную зависимость (черным цветом: `color=\"black\"`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# вставьте решение сюда"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 4\n",
    "Повторите предыдущую задачу, установив максимальную глубину решающего дерева равной 2, а затем равной 4. Таким образом, у вас получится еще два графика."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# вставьте решение сюда"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 5\n",
    "Написать функцию `estimate_tree_bias(max_depth)`, оценивающую смещение решающего дерева глубины `max_depth`. Найти смещения для деревьев из задач 3 и 4. \n",
    "\n",
    "Напомним, что смещение задаётся формулой\n",
    "\n",
    "$$\\mathbb E_{x}\\left[\n",
    "(\\mathbb E_{\\mathcal X}[\\mu(\\mathcal X)(x)]-\\mathbb E[y|x])^2\\right].\n",
    "$$\n",
    "\n",
    "Здесь $\\mathcal X\\in (\\mathbb X\\times \\mathbb Y)^n$ — выборка размером $n$, $\\mu(\\mathcal X)$ — способ обучения алгоритма по выборке, $\\mu(\\mathcal X)(x)$ — предсказанное алгоритмом значение на объекте $x\\in \\mathbb X$, $\\mathbb E[y|x]$ — условное матожидание $y$ при условии $x$ (для нашего алгоритма генерирования данных), $\\mathbb E_{x}$ берётся в соответствии с вероятностным распределением, заданным на $\\mathbb X$, $\\mathbb E_{\\mathcal X}$ берётся в соответствии с вероятностным распределением, заданным на выборках (опять же, в соответствии с нашим способом генерировать данные).\n",
    "\n",
    "Таким образом, для оценки смещения вам необходимо:\n",
    "\n",
    "1. Сгенерировать случайный $x$ в соответствии с выбранным распределением.\n",
    "2. Сгенерировать много (например, 100) выборок $\\mathcal X$ одинаковой длины (например, 300). Обучить по каждой из них алгоритм. Найти среднее предсказанное значение в точке $x$. Найти разность между средним предсказанным значением и $\\mathbb E[y|x]$ (подсказка: в нашем случае это просто $f(x)$, т.к. матожидание шума равно нулю). Возвести в квадрат. Записать.\n",
    "3. Повторить шаги 1-2 много (например, 300) раз. Усреднить.\n",
    "\n",
    "Варить до готовности, посолить по вкусу.\n",
    "\n",
    "Смещение готово!\n",
    "\n",
    "(Хозяйке на заметку: чтобы программа работала быстрее, можно сразу сгенерировать много `x`'ов, а потом для каждой выборки генерировать сразу много предсказаний на всех `x`'ах сразу. Но можно обойтись и без этого.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# вставьте решение сюда"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 6\n",
    "\n",
    "Написать функцию `estimate_tree_variance(max_depth)`, оценивающую разброс решающего дерева глубины `max_depth`. Найти разброс для деревьев из задач 3 и 4.\n",
    "\n",
    "Напомним, что разброс задаётся формулой\n",
    "\n",
    "$$\\mathbb E_{x}\\left[\\mathbb E_{\\mathcal X}\n",
    "\\left[(\\mu(\\mathcal X)(x)-\\mathbb E_{\\mathcal X}[\\mu(\\mathcal X)(x)])^2\\right]\n",
    "\\right].$$\n",
    "\n",
    "Таким образом, для оценки разброса вам потребуется следующее:\n",
    "\n",
    "1. Сгенерировать случайный $x$ в соответствии с выбранным распределением.\n",
    "2. Сгенерировать много выборок $\\mathcal X$. Для каждой обучить алгоритм и найти его предсказание на $x$. Найти выборочную дисперсию полученных предсказаний. Записать её.\n",
    "3. Повторить шаги 1 и 2 много раз. Усреднить.\n",
    "\n",
    "Разброс готов!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# вставьте решение сюда"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 7 (необязательная)\n",
    "Исследовать, как изменятся смещение и разброс при изменении распределения, заданного на $\\mathbb X$. Что изменится, если вместо экспоненциального распределения использовать равномерное на отрезке от $0$ до $7$? "
   ]
  }
 ],
 "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.5.2"
  },
  "toc": {
   "toc_cell": false,
   "toc_number_sections": false,
   "toc_threshold": 6,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}