{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Майнор по Анализу Данных, Группа ИАД-4\n", "## 05/10/2017 Бустинг" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Table of Contents\n", "

1  Майнор по Анализу Данных, Группа ИАД-4
1.1  05/10/2017 Бустинг
2  Алгоритм Ada-boost
2.1  Повторяем теорию
2.2  Игрушечная практика
3  Градиентный бустинг
3.1  Повторяем теорию
3.2  Игрушечная практика
4  Настоящая практика
" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import os\n", "import numpy as np\n", "import pandas as pd\n", "import matplotlib.pyplot as plt\n", "\n", "%matplotlib inline\n", "\n", "plt.style.use('ggplot')\n", "plt.rcParams['figure.figsize'] = (8, 8)\n", "\n", "# Для кириллицы на графиках\n", "font = {'family': 'Verdana',\n", " 'weight': 'normal'}\n", "plt.rc('font', **font)\n", "\n", "try:\n", " from ipywidgets import interact, IntSlider, fixed, FloatSlider\n", "except ImportError:\n", " print u'Так надо'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Алгоритм Ada-boost" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Повторяем теорию" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Boosting, в отличие от bagging'а - это последовательный способ построения композиции базовых моделей.\n", "\n", "Мы постоянно работаем с одним и тем же набором данных, **но** на каждом шаге строим новую базовую модель, которая учитывает ошибки предыдущей модели.По большому счету, бустинг-алгоритмы отличаются лишь тем, как в них заложен учет этих самых ошибок.\n", "\n", "Например в методе AdaBoost каждому объекту присваивается вес, который изменяется в зависимости от того, ошиблась ли на нем очередная композиция базовых алгоритмов или нет. Так же веса имеются и у самих базовых моделей, которые штрафуют их за плохие предсказания. Для задачи классификации этот процесс можно проиллюстрировать следующим образом:\n", "\n", "\n", "\n", "Введем следующие обозначения:\n", "* $t_k$ - базовый классификатор, полученный на шаге $k$\n", "* $\\alpha_k$ - вес базового классификатора, полученного на шаге $k$\n", "* $w_k(i)$ - веса объектов на шаге $k$\n", "* $x_i$ - $i$-й объект, $i = 1, \\dots, N$\n", "* $y_i=\\{-1, 1\\}$ - метки класса для $i$-го объекта \n", "\n", "Конечное предсказание получается из взвешенной комбинации предсказания базовых моделей:\n", "$$ T(x^*) = sign(\\sum\\limits^{K}_{k=1}\\alpha_kt_k(x^*)) $$\n", "\n", "Наша цель - минимизировать количество ошибок на всей выборке ..\n", "\n", "$$ E_T = \\frac{1}{N}\\sum\\limits_{i=1}^N [T(x_i) \\neq y_i] $$\n", "\n", ".. которые мы мажорируем экспонентой =)\n", "\n", "$$ E_T = \\frac{1}{N}\\sum\\limits_{i=1}^N [T(x_i) \\neq y_i] \\leq \\frac{1}{N}\\sum\\limits_{i=1}^N e^{(-y_i\\sum_k\\alpha_kt_k(x_i))} $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Если мы посчитаем ошибки $E_1, E_2, E_3,...$ на каждом шаге, то это даст нам правило для обновления весов объектов. (Упражнение)\n", "А если мы посчитаем ошибки производную $E_t$ по $\\alpha_t$, то это даст нам правило для обновления весов базовых моделей. (Упражнение)\n", "\n", "Алгоритм обучения **Discrete AdaBoost**:\n", "\n", "* Инициализируем веса объектов $w(i)_1 = \\frac{1}{N}$ \n", "* Для $k = 1..K$\n", " * Обучить классификатор $t_k(x) \\in \\{-1, 1\\}$ используя веса объектов $w(i)_k$\n", " * Вычислить ошибку взвешенную ошибку $\\epsilon = \\frac{\\sum_i w_{k}(i)[y_i \\neq t_k(x_i) ]}{\\sum_i w_{k}(i)}$\n", " * Вычислить вес базовой модели $\\alpha_k = \\ln\\frac{1-\\epsilon}{\\epsilon}$\n", " * Пересчитать веса объектов $w_{k+1}(i) = \\frac{w_{k}(i) e^{-\\alpha_k y_i t_k(x_i)}}{W}$, $i = 1, \\dots, N$,где $W = \\sum_i w_k(i) e^{-\\alpha_k y_i t_k(x_i)}$ - нормировочная константа.\n", "* $T(x) = sign(\\sum_k \\alpha_k t_k(x))$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Можно вывести аналогичный алгоритм для задачи регрессии." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Обратите внимание* что базовые модели как правило явлюятся слабыми (weak learners), т.е. их качество должно едва ли превышать бросание монетки. На рисунке выше - это логические правила на одном из признаков, что равносильно дереву решений с глубиной 1." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Раз все понятно, то перейдем к игрушечной практике" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Игрушечная практика" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from sklearn import datasets\n", "from sklearn.ensemble import AdaBoostClassifier\n", "from sklearn.tree import DecisionTreeClassifier" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Рассмотрим такой набор данных" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X = np.array([[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]])\n", "y = np.array([-1,-1,-1,-1,1,1,1,1])\n", "\n", "plt.scatter(X[:, 0], X[:, 1], c=y, s=500)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Вопрос:** Cколько базовых классификаторов достаточно, чтобы правильно классифицировать эти данные?\n", "\n", "Запомнили ответ, а теперь посмотрим" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ada = AdaBoostClassifier(n_estimators=3, algorithm='SAMME', \n", " base_estimator=DecisionTreeClassifier(max_depth=1))\n", "ada.fit(X, y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def plot_decision(model, rows=1, columns=3):\n", " fig, ax = plt.subplots(nrows=rows, ncols=columns, figsize=(15,4))\n", " ax = ax.ravel()\n", "\n", " xx1, xx2 = np.meshgrid(np.arange(X[:,0].min()-1, X[:,0].max()+1, 0.1),\n", " np.arange(X[:,1].min()-1, X[:,1].max()+1, 0.1))\n", "\n", " yy = model.staged_predict(np.c_[xx1.ravel(), xx2.ravel()])\n", "\n", " for i, y_hat in enumerate(yy):\n", " y_hat = y_hat.reshape(xx1.shape)\n", "\n", " ax[i].set_title('iteration %d' % (i+1))\n", " ax[i].contourf(xx1, xx2, y_hat, cmap=plt.cm.Paired)\n", " ax[i].scatter(X[:, 0], X[:, 1], c=y, s=300)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plot_decision(ada)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ответ: 3! (для дискретного алгоритма) Почему?! Для вещественного и правда достаточно двух" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "ada_real = AdaBoostClassifier(n_estimators=3, algorithm='SAMME.R', \n", " base_estimator=DecisionTreeClassifier(max_depth=1))\n", "ada_real.fit(X, y)\n", "plot_decision(ada_real)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Еще игрушки" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "notes" } }, "outputs": [], "source": [ "from sklearn.datasets import make_moons\n", "def ada_demo(n_est=1):\n", "\n", " ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1,), n_estimators=n_est, learning_rate=0.1)\n", " ada.fit(X, y)\n", " \n", "\n", " plt.figure(figsize=(7,5))\n", "\n", " xx1, xx2 = np.meshgrid(np.arange(-1.5, 2.5, 0.1),\n", " np.arange(-1, 1.5, 0.1))\n", "\n", " y_hat = ada.predict(np.c_[xx1.ravel(), xx2.ravel()])\n", " \n", " y_hat = y_hat.reshape(xx1.shape)\n", "\n", " plt.title('iteration = %d' % n_est )\n", " plt.contourf(xx1, xx2, y_hat, cmap=plt.cm.Paired)\n", " plt.scatter(X[:, 0], X[:, 1], c=y)\n", " \n", " plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "X, y = make_moons(noise=0.1)\n", "plt.figure(figsize=(7,5))\n", "plt.scatter(X[:, 0], X[:, 1], c=y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "interact(ada_demo, n_est=IntSlider(min=1, max=150, value=1, step=1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Градиентный бустинг" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Повторяем теорию" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Основная идея градиентного бустинга заключается в том, что каждая следующая базовая модель настраивается на \"остатки\" предыдущих базовых моделей.\n", "По своей структуре метод похож на алгоритм градиентного спуска - отсюда и такое название.\n", "\n", "По своей структуре метод похож на алгоритм градиентного спуска - отсюда и такое название.\n", "\n", "Пусть дана дифференцируемая функция потерь $L(T_k(x), y)$ (для любой задачи - регрессии или классификации) \n", "Функционал качества - $Q(T, y) = \\sum_iL(T_k(x_i), y_i) = \\sum_iL(T_{k-1}(x_i) + \\alpha t_{k}(x_i), y_i)$\n", "\n", "На секунду представим, что $t_{k}(x)$ - это просто вектор значений. Тогда задачу оптимизации $Q(T, y)$ можно решать простым градиентным методом:\n", "\n", "* $T_0$ - начальное приближение\n", "* $T_k = T_{k-1} - \\alpha g$ - делаем градиентный шаг\n", "* где $g_i = \\frac{\\partial L(T_{k-1}(x_i), y_i)}{\\partial t_{k-1}(x_i)}$, $i = 1, \\dots, N$ - градиент функции потерь\n", "\n", "Тогда $t_{k}(x) = \\arg\\min\\limits_{t} \\sum\\limits_i(t_{k}(x_i) - g_i)^2$, $\\alpha$ определяется в одномерное задаче оптимизации $ \\sum_iL(T_{k-1}(x_i) + \\alpha t_{k}(x_i), y_i) \\rightarrow \\min\\limits_\\alpha$\n", "\n", "Наибольший успех, а потому и популярность, получил градиентный бустинг на деревьях решений. Именно с этой его реализацией мы сейчас поработаем" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Игрушечная практика" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from sklearn.ensemble import GradientBoostingRegressor\n", "\n", "def grad_demo(n_est=1):\n", "\n", " X = np.random.uniform(1, 100, 500)\n", "\n", " y = np.log(X) + np.random.normal(0, .3, 500)\n", " plt.scatter(X, y)\n", " \n", "\n", " gbr = GradientBoostingRegressor(n_estimators=n_est, learning_rate=0.15)\n", " gbr_full = GradientBoostingRegressor(n_estimators=200, learning_rate=0.15)\n", " gbr.fit(X.reshape(-1,1), y)\n", " gbr_full.fit(X.reshape(-1,1), y)\n", " \n", " x_range = np.linspace(X.min(), X.max(), 100).reshape((-1,1))\n", "\n", " for y_hat in gbr.staged_predict(x_range):\n", " plt.plot(x_range, y_hat, alpha=0.4, c='g')\n", "\n", " y_hat = gbr_full.predict(x_range)\n", " \n", " plt.title('Estimators %d' % n_est)\n", " plt.plot(x_range, y_hat, c='r')\n", " \n", " plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X = np.random.uniform(1, 100, 500)\n", "\n", "y = np.log(X) + np.random.normal(0, .3, 500)\n", "plt.scatter(X, y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from sklearn.ensemble import GradientBoostingRegressor" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Обучите модель и изобразите предсказания на каждом шаге\n", "# Посмотрите, как влияет скорость обучения learning_rate на предсказания" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Настоящая практика" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Один из самых важных параметров алгоритма бустинга является количество базовых моделей.\n", "Слишком большое количество моделей может привести к переобучению, а слишком малое - к недообучению.\n", "Как бы вы определяли оптимальное количество базовых моделей?\n", "\n", "Рассмотрите следующий [набор данных](https://www.dropbox.com/s/zmz41plcrmss26f/california.dat?dl=0). По этой таблице предлагается построить модель, предсказывающую стоимоть дома в калифорнии по остальным прихнакам.\n", "\n", "* Загрузите данные и разбейте их на обучающую и контрольную выбору\n", "* Определите оптимальное количество базовых моделей в градиентном бустинге\n", "* Посмотрите, как ваш ответ меняется при изменении скорости обучения\n", "* Посмотрите, как ваш ответ меняется при обучении на случайных подвыборках\n", "* В качестве ошибки используйте MAE" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "!head california.dat" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [conda root]", "language": "python", "name": "conda-root-py" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.13" }, "nav_menu": {}, "toc": { "colors": { "hover_highlight": "#DAA520", "navigate_num": "#000000", "navigate_text": "#333333", "running_highlight": "#FF0000", "selected_highlight": "#FFD700", "sidebar_border": "#EEEEEE", "wrapper_background": "#FFFFFF" }, "moveMenuLeft": true, "nav_menu": { "height": "142px", "width": "253px" }, "navigate_menu": true, "number_sections": false, "sideBar": true, "threshold": 4, "toc_cell": false, "toc_section_display": "block", "toc_window_display": true, "widenNotebook": false } }, "nbformat": 4, "nbformat_minor": 1 }