cs236756_tutorial_11_boosting_bagging.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# <img src=\"https://img.icons8.com/dusk/64/000000/mind-map.png\" style=\"height:50px;display:inline\"> CS 236756 - Technion - Intro to Machine Learning\n",
    "---\n",
    "#### Tal Daniel\n",
    "\n",
    "## Tutorial 11 - Boosting & Bagging\n",
    "---\n",
    "\n",
    "<img src=\"./assets/tut_11_adaboost_1.gif\" style=\"hright:250px\">\n",
    "\n",
    "<a href=\"https://web.eecs.umich.edu/~jabernet/eecs598course/fall2013/web/\">Image Source</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <img src=\"https://img.icons8.com/bubbles/50/000000/checklist.png\" style=\"height:50px;display:inline\"> Agenda\n",
    "---\n",
    "* [Ensemble Learning](#-Ensemble-Learning)\n",
    "    * [Voting Classifiers](#-Voting-Classifiers)\n",
    "* [Bagging (& Pasting)](#-Bagging-(&-Pasting))\n",
    "    * [Bootstrap](#Bootstrap)\n",
    "* [Boosting](#-Boosting)\n",
    "    * [AdaBoost](#-AdaBoost)\n",
    "* [Recommended Videos](#-Recommended-Videos)\n",
    "* [Credits](#-Credits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# imports for the tutorial\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib notebook\n",
    "\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.ensemble import VotingClassifier\n",
    "from sklearn.ensemble import BaggingClassifier\n",
    "from sklearn.ensemble import AdaBoostClassifier\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.svm import SVC\n",
    "from sklearn.preprocessing import StandardScaler\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\", category=DeprecationWarning) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <img src=\"https://img.icons8.com/dusk/64/000000/elections.png\" style=\"height:50px;display:inline\"> Ensemble Learning\n",
    "---\n",
    "* **Wisdom of the Crowd** - assembling the predictions of a group of predictors (such as classifiers or regressors) often results in a better prediction than with the best individual predictor.\n",
    "* **Ensemble** - a group of predictors. An *Ensemble Learning* algorithm is called an **Ensemble method**.\n",
    "    * For example: **Random Forest** -train a group of Decision Tree classifiers, each is trained on a random subset of the training set. To make predicitons, we obtain the predicitons of all individual trees, and then predict the class that gets the most votes. This is one of the most powerful ML algorithms available today."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <img src=\"https://img.icons8.com/flat_round/64/000000/vote-button.png\" style=\"height:50px;display:inline\"> Voting Classifiers\n",
    "---\n",
    "* **Hard Voting Classifier** - aggregate the predictions of each classifier and predict the class that gets the most votes.\n",
    "    * In fact, even if each classifier is a *weak learner* (it does only slightly better than random guessing), the ensemble can still be a *strong learner* (achieving high accuracy), provided there are a sufficient number of weak learners and they are sufficiently diverse.\n",
    "    * **The Law of Large Numbers** - how can the above fact be explained? building an ensemble containing 1,000 classifiers that are individually correct only 51% of the time (slighly better than random guessing) and predict the majority voted class, it is possible to reach 75% accuracy if all the classifiers are perfectly independent (which is not really the case since they are trained on the same data).\n",
    "    * One way to get diverse classifiers is to train them using very different algorithms (increases the chance that they will make very different types of erros and thus improving the ensemble's accuracy).\n",
    "* **Soft Voting Classifier** - if all the classifiers are able to estimate class probabilities, then the class probability can be averaged over all the individual classifiers.\n",
    "    * It often achieves higher performance than *hard voting* because it gives more weight to highly confident votes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total samples: 569\n",
      "total positive sampels (M): 212, total negative samples (B): 357\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>diagnosis</th>\n",
       "      <th>radius_mean</th>\n",
       "      <th>texture_mean</th>\n",
       "      <th>perimeter_mean</th>\n",
       "      <th>area_mean</th>\n",
       "      <th>smoothness_mean</th>\n",
       "      <th>compactness_mean</th>\n",
       "      <th>concavity_mean</th>\n",
       "      <th>concave points_mean</th>\n",
       "      <th>...</th>\n",
       "      <th>texture_worst</th>\n",
       "      <th>perimeter_worst</th>\n",
       "      <th>area_worst</th>\n",
       "      <th>smoothness_worst</th>\n",
       "      <th>compactness_worst</th>\n",
       "      <th>concavity_worst</th>\n",
       "      <th>concave points_worst</th>\n",
       "      <th>symmetry_worst</th>\n",
       "      <th>fractal_dimension_worst</th>\n",
       "      <th>Unnamed: 32</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>237</td>\n",
       "      <td>883263</td>\n",
       "      <td>M</td>\n",
       "      <td>20.48</td>\n",
       "      <td>21.46</td>\n",
       "      <td>132.50</td>\n",
       "      <td>1306.0</td>\n",
       "      <td>0.08355</td>\n",
       "      <td>0.08348</td>\n",
       "      <td>0.09042</td>\n",
       "      <td>0.060220</td>\n",
       "      <td>...</td>\n",
       "      <td>26.17</td>\n",
       "      <td>161.70</td>\n",
       "      <td>1750.0</td>\n",
       "      <td>0.12280</td>\n",
       "      <td>0.23110</td>\n",
       "      <td>0.31580</td>\n",
       "      <td>0.14450</td>\n",
       "      <td>0.2238</td>\n",
       "      <td>0.07127</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>159</td>\n",
       "      <td>871149</td>\n",
       "      <td>B</td>\n",
       "      <td>10.90</td>\n",
       "      <td>12.96</td>\n",
       "      <td>68.69</td>\n",
       "      <td>366.8</td>\n",
       "      <td>0.07515</td>\n",
       "      <td>0.03718</td>\n",
       "      <td>0.00309</td>\n",
       "      <td>0.006588</td>\n",
       "      <td>...</td>\n",
       "      <td>18.20</td>\n",
       "      <td>78.07</td>\n",
       "      <td>470.0</td>\n",
       "      <td>0.11710</td>\n",
       "      <td>0.08294</td>\n",
       "      <td>0.01854</td>\n",
       "      <td>0.03953</td>\n",
       "      <td>0.2738</td>\n",
       "      <td>0.07685</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>442</td>\n",
       "      <td>90944601</td>\n",
       "      <td>B</td>\n",
       "      <td>13.78</td>\n",
       "      <td>15.79</td>\n",
       "      <td>88.37</td>\n",
       "      <td>585.9</td>\n",
       "      <td>0.08817</td>\n",
       "      <td>0.06718</td>\n",
       "      <td>0.01055</td>\n",
       "      <td>0.009937</td>\n",
       "      <td>...</td>\n",
       "      <td>17.50</td>\n",
       "      <td>97.90</td>\n",
       "      <td>706.6</td>\n",
       "      <td>0.10720</td>\n",
       "      <td>0.10710</td>\n",
       "      <td>0.03517</td>\n",
       "      <td>0.03312</td>\n",
       "      <td>0.1859</td>\n",
       "      <td>0.06810</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>283</td>\n",
       "      <td>8912280</td>\n",
       "      <td>M</td>\n",
       "      <td>16.24</td>\n",
       "      <td>18.77</td>\n",
       "      <td>108.80</td>\n",
       "      <td>805.1</td>\n",
       "      <td>0.10660</td>\n",
       "      <td>0.18020</td>\n",
       "      <td>0.19480</td>\n",
       "      <td>0.090520</td>\n",
       "      <td>...</td>\n",
       "      <td>25.09</td>\n",
       "      <td>126.90</td>\n",
       "      <td>1031.0</td>\n",
       "      <td>0.13650</td>\n",
       "      <td>0.47060</td>\n",
       "      <td>0.50260</td>\n",
       "      <td>0.17320</td>\n",
       "      <td>0.2770</td>\n",
       "      <td>0.10630</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>477</td>\n",
       "      <td>911673</td>\n",
       "      <td>B</td>\n",
       "      <td>13.90</td>\n",
       "      <td>16.62</td>\n",
       "      <td>88.97</td>\n",
       "      <td>599.4</td>\n",
       "      <td>0.06828</td>\n",
       "      <td>0.05319</td>\n",
       "      <td>0.02224</td>\n",
       "      <td>0.013390</td>\n",
       "      <td>...</td>\n",
       "      <td>21.80</td>\n",
       "      <td>101.20</td>\n",
       "      <td>718.9</td>\n",
       "      <td>0.09384</td>\n",
       "      <td>0.20060</td>\n",
       "      <td>0.13840</td>\n",
       "      <td>0.06222</td>\n",
       "      <td>0.2679</td>\n",
       "      <td>0.07698</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>45</td>\n",
       "      <td>857010</td>\n",
       "      <td>M</td>\n",
       "      <td>18.65</td>\n",
       "      <td>17.60</td>\n",
       "      <td>123.70</td>\n",
       "      <td>1076.0</td>\n",
       "      <td>0.10990</td>\n",
       "      <td>0.16860</td>\n",
       "      <td>0.19740</td>\n",
       "      <td>0.100900</td>\n",
       "      <td>...</td>\n",
       "      <td>21.32</td>\n",
       "      <td>150.60</td>\n",
       "      <td>1567.0</td>\n",
       "      <td>0.16790</td>\n",
       "      <td>0.50900</td>\n",
       "      <td>0.73450</td>\n",
       "      <td>0.23780</td>\n",
       "      <td>0.3799</td>\n",
       "      <td>0.09185</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>127</td>\n",
       "      <td>866203</td>\n",
       "      <td>M</td>\n",
       "      <td>19.00</td>\n",
       "      <td>18.91</td>\n",
       "      <td>123.40</td>\n",
       "      <td>1138.0</td>\n",
       "      <td>0.08217</td>\n",
       "      <td>0.08028</td>\n",
       "      <td>0.09271</td>\n",
       "      <td>0.056270</td>\n",
       "      <td>...</td>\n",
       "      <td>25.73</td>\n",
       "      <td>148.20</td>\n",
       "      <td>1538.0</td>\n",
       "      <td>0.10210</td>\n",
       "      <td>0.22640</td>\n",
       "      <td>0.32070</td>\n",
       "      <td>0.12180</td>\n",
       "      <td>0.2841</td>\n",
       "      <td>0.06541</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>561</td>\n",
       "      <td>925311</td>\n",
       "      <td>B</td>\n",
       "      <td>11.20</td>\n",
       "      <td>29.37</td>\n",
       "      <td>70.67</td>\n",
       "      <td>386.0</td>\n",
       "      <td>0.07449</td>\n",
       "      <td>0.03558</td>\n",
       "      <td>0.00000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>...</td>\n",
       "      <td>38.30</td>\n",
       "      <td>75.19</td>\n",
       "      <td>439.6</td>\n",
       "      <td>0.09267</td>\n",
       "      <td>0.05494</td>\n",
       "      <td>0.00000</td>\n",
       "      <td>0.00000</td>\n",
       "      <td>0.1566</td>\n",
       "      <td>0.05905</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>120</td>\n",
       "      <td>865137</td>\n",
       "      <td>B</td>\n",
       "      <td>11.41</td>\n",
       "      <td>10.82</td>\n",
       "      <td>73.34</td>\n",
       "      <td>403.3</td>\n",
       "      <td>0.09373</td>\n",
       "      <td>0.06685</td>\n",
       "      <td>0.03512</td>\n",
       "      <td>0.026230</td>\n",
       "      <td>...</td>\n",
       "      <td>15.97</td>\n",
       "      <td>83.74</td>\n",
       "      <td>510.5</td>\n",
       "      <td>0.15480</td>\n",
       "      <td>0.23900</td>\n",
       "      <td>0.21020</td>\n",
       "      <td>0.08958</td>\n",
       "      <td>0.3016</td>\n",
       "      <td>0.08523</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>444</td>\n",
       "      <td>9110127</td>\n",
       "      <td>M</td>\n",
       "      <td>18.03</td>\n",
       "      <td>16.85</td>\n",
       "      <td>117.50</td>\n",
       "      <td>990.0</td>\n",
       "      <td>0.08947</td>\n",
       "      <td>0.12320</td>\n",
       "      <td>0.10900</td>\n",
       "      <td>0.062540</td>\n",
       "      <td>...</td>\n",
       "      <td>22.02</td>\n",
       "      <td>133.30</td>\n",
       "      <td>1292.0</td>\n",
       "      <td>0.12630</td>\n",
       "      <td>0.26660</td>\n",
       "      <td>0.42900</td>\n",
       "      <td>0.15350</td>\n",
       "      <td>0.2842</td>\n",
       "      <td>0.08225</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>10 rows × 33 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "           id diagnosis  radius_mean  texture_mean  perimeter_mean  area_mean  \\\n",
       "237    883263         M        20.48         21.46          132.50     1306.0   \n",
       "159    871149         B        10.90         12.96           68.69      366.8   \n",
       "442  90944601         B        13.78         15.79           88.37      585.9   \n",
       "283   8912280         M        16.24         18.77          108.80      805.1   \n",
       "477    911673         B        13.90         16.62           88.97      599.4   \n",
       "45     857010         M        18.65         17.60          123.70     1076.0   \n",
       "127    866203         M        19.00         18.91          123.40     1138.0   \n",
       "561    925311         B        11.20         29.37           70.67      386.0   \n",
       "120    865137         B        11.41         10.82           73.34      403.3   \n",
       "444   9110127         M        18.03         16.85          117.50      990.0   \n",
       "\n",
       "     smoothness_mean  compactness_mean  concavity_mean  concave points_mean  \\\n",
       "237          0.08355           0.08348         0.09042             0.060220   \n",
       "159          0.07515           0.03718         0.00309             0.006588   \n",
       "442          0.08817           0.06718         0.01055             0.009937   \n",
       "283          0.10660           0.18020         0.19480             0.090520   \n",
       "477          0.06828           0.05319         0.02224             0.013390   \n",
       "45           0.10990           0.16860         0.19740             0.100900   \n",
       "127          0.08217           0.08028         0.09271             0.056270   \n",
       "561          0.07449           0.03558         0.00000             0.000000   \n",
       "120          0.09373           0.06685         0.03512             0.026230   \n",
       "444          0.08947           0.12320         0.10900             0.062540   \n",
       "\n",
       "     ...  texture_worst  perimeter_worst  area_worst  smoothness_worst  \\\n",
       "237  ...          26.17           161.70      1750.0           0.12280   \n",
       "159  ...          18.20            78.07       470.0           0.11710   \n",
       "442  ...          17.50            97.90       706.6           0.10720   \n",
       "283  ...          25.09           126.90      1031.0           0.13650   \n",
       "477  ...          21.80           101.20       718.9           0.09384   \n",
       "45   ...          21.32           150.60      1567.0           0.16790   \n",
       "127  ...          25.73           148.20      1538.0           0.10210   \n",
       "561  ...          38.30            75.19       439.6           0.09267   \n",
       "120  ...          15.97            83.74       510.5           0.15480   \n",
       "444  ...          22.02           133.30      1292.0           0.12630   \n",
       "\n",
       "     compactness_worst  concavity_worst  concave points_worst  symmetry_worst  \\\n",
       "237            0.23110          0.31580               0.14450          0.2238   \n",
       "159            0.08294          0.01854               0.03953          0.2738   \n",
       "442            0.10710          0.03517               0.03312          0.1859   \n",
       "283            0.47060          0.50260               0.17320          0.2770   \n",
       "477            0.20060          0.13840               0.06222          0.2679   \n",
       "45             0.50900          0.73450               0.23780          0.3799   \n",
       "127            0.22640          0.32070               0.12180          0.2841   \n",
       "561            0.05494          0.00000               0.00000          0.1566   \n",
       "120            0.23900          0.21020               0.08958          0.3016   \n",
       "444            0.26660          0.42900               0.15350          0.2842   \n",
       "\n",
       "     fractal_dimension_worst  Unnamed: 32  \n",
       "237                  0.07127          NaN  \n",
       "159                  0.07685          NaN  \n",
       "442                  0.06810          NaN  \n",
       "283                  0.10630          NaN  \n",
       "477                  0.07698          NaN  \n",
       "45                   0.09185          NaN  \n",
       "127                  0.06541          NaN  \n",
       "561                  0.05905          NaN  \n",
       "120                  0.08523          NaN  \n",
       "444                  0.08225          NaN  \n",
       "\n",
       "[10 rows x 33 columns]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# let's load the cancer dataset, shuffle it and  speratre into train and test set\n",
    "dataset = pd.read_csv('./datasets/cancer_dataset.csv')\n",
    "# print the number of rows in the data set\n",
    "number_of_rows = len(dataset)\n",
    "print(\"total samples: {}\".format(number_of_rows))\n",
    "total_positive_samples = np.sum(dataset['diagnosis'].values == 'M')\n",
    "print(\"total positive sampels (M): {}, total negative samples (B): {}\".format(total_positive_samples, number_of_rows - total_positive_samples))\n",
    "num_train = int(0.8 * number_of_rows)\n",
    "# reminder, the data looks like this\n",
    "# dataset.head(10) # the dataset is ordered by the diagnosis\n",
    "dataset.sample(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# prepare the dataset\n",
    "# we will take the first 2 features as our data (X) and the diagnosis as labels (y)\n",
    "x = dataset[['radius_mean', 'texture_mean', 'concavity_mean']].values\n",
    "y = dataset['diagnosis'].values == 'M'  # 1 for Malignat, 0 for Benign\n",
    "# shuffle\n",
    "rand_gen = np.random.RandomState(0)\n",
    "shuffled_indices = rand_gen.permutation(np.arange(len(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "x_train = x[shuffled_indices[:num_train]]\n",
    "y_train = y[shuffled_indices[:num_train]]\n",
    "x_test = x[shuffled_indices[num_train:]]\n",
    "y_test = y[shuffled_indices[num_train:]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total training samples: 455, total test samples: 114\n"
     ]
    }
   ],
   "source": [
    "# pre-process - standartization\n",
    "scaler = StandardScaler()\n",
    "scaler.fit(x_train)\n",
    "x_train = scaler.transform(x_train)\n",
    "x_test = scaler.transform(x_test)\n",
    "\n",
    "print(\"total training samples: {}, total test samples: {}\".format(num_train, number_of_rows - num_train))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# hard voting\n",
    "random_state = 38\n",
    "# create different classifiers\n",
    "log_clf = LogisticRegression(random_state=random_state, solver='lbfgs')\n",
    "rnd_clf = RandomForestClassifier(random_state=random_state, n_estimators=100)\n",
    "svm_clf = SVC(random_state=random_state)\n",
    "# create a voting classifier\n",
    "voting_clf = VotingClassifier(estimators=[('lr', log_clf), ('rf', rnd_clf), ('svc', svm_clf)], voting='hard')\n",
    "# voting_clf.fit(x_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LogisticRegression 0.9385964912280702\n",
      "RandomForestClassifier 0.9298245614035088\n",
      "SVC 0.9473684210526315\n",
      "VotingClassifier 0.9473684210526315\n"
     ]
    }
   ],
   "source": [
    "# let's look at each classifier's accuracy on the test set\n",
    "for clf in (log_clf, rnd_clf, svm_clf, voting_clf):\n",
    "    clf.fit(x_train, y_train)\n",
    "    y_pred = clf.predict(x_test)\n",
    "    print(clf.__class__.__name__, accuracy_score(y_test, y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <img src=\"https://img.icons8.com/plasticine/100/000000/briefcase.png\" style=\"height:50px;display:inline\"> Bagging (& Pasting)\n",
    "---\n",
    "* Another approach to get a diverse set of classifiers is to use the **same training algorithm** for every predictor, but to train them on **different random subsets of the training set**.\n",
    "* When sampling is performed **with replacement** this method is called **bagging** (which is a short for *bootstrap aggregating*).\n",
    "    * In sampling **with replacement**, each sample unit of the population can occur one or more times in the sample.\n",
    "    * In statistics, resampling with replacement is called *bootstrapping*.\n",
    "* When sampling is performed **without replacement** this method is called **pasting**.\n",
    "* Thus, both bagging and pasting allow training instances to be sampled several times across multiple predictors, but only bagging allows training instances to be sampled several times for the same predictor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Illustartion: <img src=\"./assets/tut_11_bagging_pasting.png\" style=\"height:200px\">\n",
    "\n",
    "<a href=\"https://github.com/SoojungHong/MachineLearning/wiki/Random-Forest\">Image Source</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Once all predictors are trained, the ensemble can make a prediction for a new instance by collecting all the predictions of all the predictors. It usually decided by *hard voting* or average for regression.\n",
    "* Each individual predictor has a higher bias than if it were trained on the original training set, but the aggregation **reduces both bias and variance**.\n",
    "    * It is common to see that the ensemble has a **similar bias** but a **lower variance** than a single predictor trained on the original training set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Bootstrap\n",
    "---\n",
    "* **Bootstrap Algorithm**:\n",
    "    * Denote the original sample: $ L_N = (x_1, x_2, ..., x_N) $\n",
    "    * Repeat $M$ times:\n",
    "        * Generate a sample $L_k$ of size $k$ from $L_N$ by sampling *with replacement*.\n",
    "        * Compute $h$ from $L_k$ (that is, train a predictor $h$ using $L_k$).\n",
    "    * Denote the bootstrap values $H=(h^1, h^2, ..., h^M)$\n",
    "        * Use these values for calculating all the quantities of interest."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* **Bagging**:\n",
    "    * Train each model with a random training set (bootsrap).\n",
    "    * Each model in the ensemble has an **equal weight** in the voting.\n",
    "    * Finally: $$ H(x) = sign(h^1(x) +h^2(x) +... +h^M(x)) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* One classifier can be wrong as long as the others are correct (*hard voting*) <img src=\"./assets/tut_11_bagging_1.jpg\" style=\"height:200px\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Since given equal weight, this may cause problems when there is overlap. <img src=\"./assets/tut_11_bagging_2.jpg\" style=\"height:200px\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bagging accuracy: 0.939\n"
     ]
    }
   ],
   "source": [
    "# bagging\n",
    "# note: BaggingClassifiers will automatically perform 'soft voting' instead of 'hard voting'\n",
    "# if the base classifier can estimate class probabilities (i.e. if it has a \"predict_proba()\" method).\n",
    "\n",
    "bag_clf = BaggingClassifier(\n",
    "    DecisionTreeClassifier(),\n",
    "    n_estimators=500,\n",
    "    max_samples=100,\n",
    "    bootstrap=True,\n",
    "    n_jobs=1)\n",
    "bag_clf.fit(x_train, y_train)\n",
    "y_pred = bag_clf.predict(x_test)\n",
    "bag_acc = accuracy_score(y_test, y_pred)\n",
    "print(\"bagging accuracy: {:.3f}\".format(bag_acc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pasting accuracy: 0.930\n"
     ]
    }
   ],
   "source": [
    "# pasting\n",
    "pas_clf = BaggingClassifier(\n",
    "    DecisionTreeClassifier(),\n",
    "    n_estimators=500,\n",
    "    max_samples=100,\n",
    "    bootstrap=False,\n",
    "    n_jobs=1)\n",
    "pas_clf.fit(x_train, y_train)\n",
    "y_pred = pas_clf.predict(x_test)\n",
    "pas_acc = accuracy_score(y_test, y_pred)\n",
    "print(\"pasting accuracy: {:.3f}\".format(pas_acc))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <img src=\"https://img.icons8.com/bubbles/100/000000/rocket.png\" style=\"height:50px;display:inline\"> Boosting\n",
    "---\n",
    "* **Boosting** (also *hypothesis boosting*) - any Ensemble method that can combine several weak learners into a strong learner. In boosting methods, predictors are trained **sequentially**, each trying to correct its predecessor.\n",
    "    * Weak Learner - as before, the error rate is slighty better than flipping a coin\n",
    "    * We also define:\n",
    "        * $h$ is binary classifier such that $h \\in \\{-1, 1\\}$\n",
    "        * Error rate $Err \\in [0,1]$\n",
    "* The principal difference between boosting and the committe methods is that in boosting, the base classifiers are **trained in sequence**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Each base classifier is trained using a **weighted form of the dataset**, in which the weight coefficient associated with each data point depends on the performance of the previous classifiers.\n",
    "    * In particular, points that are misclassified by one of the base classifiers are given greater weight when used to train the next classifier in the sequence.\n",
    "* Once all the classifiers have been trained, their predictions are then combined through a **weighted majority voting** scheme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Visually: <img src=\"./assets/tut_11_boosting_1.jpg\" style=\"height:300px\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"./assets/tut_11_boosting_2.jpg\" style=\"height:400px\">\n",
    "\n",
    "* There are many boosting methods, but we will examine one of the most popular one called *AdaBoost*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <img src=\"https://img.icons8.com/dusk/64/000000/wired-network.png\" style=\"height:50px;display:inline\"> AdaBoost\n",
    "---\n",
    "* The idea of AdaBoost is to give more attention to training instances that the predecessor underfitted. This leads to a predictor that focuses more and more on the hard cases.\n",
    "* The sequential learning in Boosting seems similar to Gradient Descent, only in AdaBoost predictors are added to the ensemble in order to make it better where in GD, a single predictor's paramerters are optimized to minimize an objective function.\n",
    "* Once all predictors are trained, the ensemble makes predictions by assigning different weights to each predictor, depending on their **overall accuracy on the weighted training set**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Definitions\n",
    "---\n",
    "* Class labels are $\\{-1, 1\\}$\n",
    "* $m$ - number of samples in the training dataset\n",
    "* The weighted error rate of the $t^{th}$ predictor: $$ \\epsilon_t =\\sum _{i=1}^m w^{(i)} \\cdot \\mathbb{1}(\\hat{y}_t^{(i)} \\neq y^{(i)})$$ In the more general case where the weights are not normalized to 1: $$ \\epsilon_t =\\frac{\\sum _{i=1}^m w^{(i)} \\cdot \\mathbb{1}(\\hat{y}_t^{(i)} \\neq y^{(i)})}{\\sum _{i=1}^m w^{(i)}} $$\n",
    "    * $\\hat{y}_t^{(i)}$ is the $t^{th}$ predictor's prediction for the $i^{th}$ instance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* The predictors weight of the $t^{th}$ predictor: $$ \\alpha_t = \\eta \\ln \\frac{1 - \\epsilon_t}{\\epsilon_t} $$\n",
    "    * $\\eta$ it the learning rate hyperparameter, e.g. $\\frac{1}{2}$ or 1.\n",
    "    * The more accurate the predictor is, the more weight the predictor will be given.\n",
    "* The update rule: for $i = 1,2, ..., m $ $$ w^{(i)} \\leftarrow \\begin{cases} w^{(i)}e^{-\\alpha_t} & \\quad \\text{if } \\hat{y}_t^{(i)} = y^{(i)}  \\\\ w^{(i)}e^{\\alpha_t} & \\quad \\text{if } \\hat{y}_t^{(i)} \\neq y^{(i)} \\end{cases} = w^{(i)}e^{-\\alpha_t\\cdot y^{(i)} \\cdot \\hat{y}_t^{(i)}}$$\n",
    "    * Once all the weights were calculated, they are summed. The sum is denoted $Z_t$. Then, all the weights are normalized by dividing each weight by $Z_t$.\n",
    "* **Stopping criteria**:\n",
    "    * The desired number of predictors is reached.\n",
    "    * A perfert predictor is found."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"./assets/tut_11_adaboost.gif\" style=\"height:300px\">\n",
    "\n",
    "<a href=\"http://talimi.se/ml/adaboost/\">Image Source</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* **The AdaBoost Algorithm**:\n",
    "    * Initialize the data weights coefficients $\\{w^{(i)}\\}_{i=1}^m$: $$ w^{(i)} = \\frac{1}{m}, \\forall i= 1,2,...,m $$\n",
    "    * For $t = 1,...,T$:\n",
    "        * Fit a weak classifier $h_t(x)$ (which makes predictions $\\hat{y}_t$) to the weighted training data and calculate the weighted error rate: $$ \\epsilon_t =\\frac{\\sum _{i=1}^m w^{(i)} \\cdot \\mathbb{1}(\\hat{y}_t^{(i)} \\neq y^{(i)})}{\\sum _{i=1}^m w^{(i)}} $$\n",
    "        * Choose $\\alpha_t$ (default $\\eta=\\frac{1}{2}$): $$ \\alpha_t = \\frac{1}{2} \\ln \\frac{1 - \\epsilon_t}{\\epsilon_t} $$\n",
    "        * Update the weights: for $i = 1,2, ..., m $ $$ w^{(i)} \\leftarrow \\begin{cases} w^{(i)}e^{-\\alpha_t} & \\quad \\text{if } \\hat{y}_t^{(i)} = y^{(i)}  \\\\ w^{(i)}e^{\\alpha_t} & \\quad \\text{if } \\hat{y}_t^{(i)} \\neq y^{(i)} \\end{cases} = w^{(i)}e^{-\\alpha_t\\cdot y^{(i)} \\cdot \\hat{y}_t^{(i)}}$$\n",
    "        * Normalize the weights: for $i = 1,2, ..., m $ $$ w^{(i)} \\leftarrow \\frac{w^{(i)}}{Z_t} $$\n",
    "            * $Z_t = \\sum_{i=1}^m w^{(i)}$\n",
    "    * Use predictions using the final model, which is given by: $$ H(x) = sign(\\sum_{i=1}^T \\alpha_th_t(x)) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### <img src=\"https://img.icons8.com/nolan/64/000000/down2.png\" style=\"height:30px;display:inline\"> Exponential Loss\n",
    "---\n",
    "* So far, the loss functions we have seen:\n",
    "    * 0-1 loss\n",
    "    * Hinge loss\n",
    "    * Log loss\n",
    "* Unlike previously learnt classifiers, AdaBoost minimzes the exponential loss.\n",
    "* All lossess upper bound the 0-1 loss and act as differentiable surrogate loss functions.\n",
    "* <img src=\"./assets/tut_11_exp_loss.jpg\" style=\"height:200px\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Optimizing the exponential loss:\n",
    "    * As shown in class, the training error is upper bounded by $H$: $$ \\frac{1}{m} \\sum_i^m \\mathbb{1}(H(x_i) \\neq y_i) \\leq \\prod_{t=1}^T Z_t  $$\n",
    "        * $Z_t = \\sum_i w_t^{(i)} e^{-\\alpha_t y_i h_t(x_i)} $\n",
    "    * At each round we minimize $Z_t$ by:\n",
    "        * Choosing the optimal $h_t$\n",
    "        * Finding the optimal $\\alpha_t$\n",
    "        * $$ \\frac{dZ}{d\\alpha} = -\\sum_{i=1}^m w^{(i)} y_ih(x_i) e^{-\\alpha y_ih(x_i)} = 0 $$ $$ -\\sum_{i:y_i=h(x_i)}w^{(i)} e^{-\\alpha} + \\sum_{i: y_i \\neq h(x_i)} w^{(i)} e^{\\alpha} = 0 $$ $$ -e^{-\\alpha} (1-\\epsilon) +e^{\\alpha} \\epsilon = 0 $$ $$ \\rightarrow \\alpha_t = \\frac{1}{2} \\ln \\frac{1 - \\epsilon_t}{\\epsilon_t} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <img src=\"https://img.icons8.com/dusk/64/000000/classroom.png\" style=\"height:50px;display:inline\"> Boosting (AdaBoost) Example By Hand\n",
    "---\n",
    "Moses is a student who wants to avoid hard courses. \n",
    "\n",
    "In order to achieve this he wants to build a classifier that classifies courses as \"easy\" or \"hard\".\n",
    "\n",
    "He decides to classify courses' hardness by using AdaBoost with decision trees stumps (decision trees with max depth of 1) on the following data:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "| <center> Course ID</center>| <center> Hard </center> | <center> Final Exam </center> | <center>Theoretical </center>  | <center> Midterm </center>| <center> 236* </center> | <center> Number of HW </center>  \n",
    "| --- | --- | --- | --- | --- | --- | --- |\n",
    "|<center> 1</center> | <center> Y </center> | <center>Y </center>|<center> N </center> | <center> Y </center>| <center>N </center>| <center> 5</center>|\n",
    "|<center> 2</center> | <center> Y </center> | <center>N </center>|<center> Y </center> | <center> Y </center>| <center>N </center>| <center> 5</center>|\n",
    "|<center> 3</center> | <center> Y </center> | <center>N </center>|<center> Y </center> | <center> N </center>| <center>Y </center>| <center> 1</center>|\n",
    "|<center> 4</center> | <center> Y </center> | <center>N </center>|<center> Y </center> | <center> N </center>| <center>N </center>| <center> 3</center>|\n",
    "|<center> 5</center> | <center> Y </center> | <center>N </center>|<center> Y </center> | <center> N </center>| <center>N </center>| <center> 5</center>|\n",
    "|<center> 6</center> | <center> Y </center> | <center>Y </center>|<center> N </center> | <center> Y </center>| <center>N </center>| <center> 5</center>|\n",
    "|<center> 7</center> | <center> Y </center> | <center>Y </center>|<center> N </center> | <center> Y </center>| <center>N </center>| <center> 5</center>|\n",
    "|<center> 8</center> | <center> N </center> | <center>N </center>|<center> N </center> | <center> Y </center>| <center>Y </center>| <center> 1</center>|\n",
    "|<center> 9</center> | <center> N </center> | <center>N </center>|<center> Y </center> | <center> N </center>| <center>N </center>| <center> 1</center>|\n",
    "|<center> 10</center> | <center> Y </center> | <center>N </center>|<center> N </center> | <center> N </center>| <center>N </center>| <center> 5</center>|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As a first step, he first determined for each possible classifier (including the trivial constant classifier), which of the data points were misclassfied.\n",
    "\n",
    "For example, for the first classifier which classfies courses as hard if they have a final exam, the classifier is wrong on samples 2,3,4 and 5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "| <center> Classifier</center>| <center> Test </center> | <center> Value </center> | <center>Misclassified </center>  |\n",
    "| --- | --- | --- | --- |\n",
    "|<center> A</center> | <center> Final Exam </center> | <center>Y </center>|<center> 2,3,4,5 </center> |\n",
    "|<center> B</center> | <center> Theoretical </center> | <center>Y </center>|<center> 1,6,7,9 </center> |\n",
    "|<center> C</center> | <center> Midterm</center> | <center>Y </center>|<center> 3,4,5,8 </center> |\n",
    "|<center> D</center> | <center> Undergrduate </center> | <center>Y </center>|<center> 1,2,4,5,6,7,8 </center> |\n",
    "|<center> E</center> | <center> # HW > 2 </center> | <center>Y </center>|<center> 3,10 </center> |\n",
    "|<center> F</center> | <center> # HW > 4 </center> | <center>Y </center>|<center> 3,4,10 </center> |\n",
    "|<center> G</center> | <center> True (const) </center> | <center> </center>|<center> 8,9,10 </center> |\n",
    "|<center> H</center> | <center> Final Exam </center> | <center>N </center>|<center> 1,6,7,8,9,10 </center> |\n",
    "|<center> I</center> | <center> Theoretical </center> | <center>N </center>|<center> 2,3,4,5,8,10 </center> |\n",
    "|<center> J</center> | <center> Midterm</center> | <center>N </center>|<center> 1,2,6,7,9,10 </center> |\n",
    "|<center> K</center> | <center> Undergraduate </center> | <center>N </center>|<center> 3,9,10 </center> |\n",
    "|<center> L</center> | <center> # HW < 2 </center> | <center>Y </center>|<center> 1,2,4,5,6,7,8,9 </center> |\n",
    "|<center> M</center> | <center> # HW < 4 </center> | <center>Y </center>|<center> 1,2,5,6,7,8,9 </center> |\n",
    "|<center> N</center> | <center> False (const) </center> | <center> </center>|<center> 1,2,3,4,5,6,7 </center> |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Consider only useful classifiers\n",
    "Only 6 classifiers from the table above would ever be used because the other 8 make all the same error as one of the other classifiers and then make additional erros. For example, classifiers I and N do the same mistakes as A and add to that. The 6 useful classifiers are:\n",
    "\n",
    "\n",
    "| <center> Classifier</center>| <center> Test </center> | <center> Value </center> | <center>Misclassified </center>  |\n",
    "| --- | --- | --- | --- |\n",
    "|<center> A</center> | <center> Final Exam </center> | <center>Y </center>|<center> 2,3,4,5 </center> |\n",
    "|<center> B</center> | <center> Theoretical </center> | <center>Y </center>|<center> 1,6,7,9 </center> |\n",
    "|<center> C</center> | <center> Midterm</center> | <center>Y </center>|<center> 3,4,5,8 </center> |\n",
    "|<center> D</center> | <center> Undergrduate </center> | <center>Y </center>|<center> 1,2,4,5,6,7,8 </center> |\n",
    "|<center> E</center> | <center> # HW > 2 </center> | <center>Y </center>|<center> 3,10 </center> |\n",
    "|<center> G</center> | <center> True (const) </center> | <center> </center>|<center> 8,9,10 </center> |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### AdaBoost\n",
    "* We will now perform AdaBoost by calculating the weights at each iteration.\n",
    "* We will calculate the 10 weights, the classification $h$, the error and $\\alpha$.\n",
    "* If there is a tie, we break it by choosing the classifier that is higher on the list (lexicographical order)\n",
    "* Note: in this example we assume that the weights of the data points do not affect the clasification and are just meant to calculate the final weight of each classifier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Round 1\n",
    "* Each weight is given the same value: $\\frac{1}{m} = \\frac{1}{10}$\n",
    "* Since classifier $E$ is the most accurate, it will serve as the classifier.\n",
    "* The weight error rate of classifier $E$ is $\\epsilon_E = \\frac{2}{10}$\n",
    "* Thus: $\\alpha_E = \\frac{1}{2}\\ln \\frac{1 - \\epsilon_E}{\\epsilon_E} = \\frac{1}{2} \\ln (4)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "| <center> Parameters &nbsp; &nbsp; &nbsp; &nbsp;</center>| <center> Round 1 </center> | <center> Round 2 </center> | <center> Round 3 </center>  |\n",
    "| ----- | --- | --- | --- |\n",
    "|<center> w1</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w2</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w3</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w4</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w5</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w6</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w7</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w8</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w9</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> w10</center> | <center> $\\frac{1}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> $h$</center> | <center> $E$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> Err - $\\epsilon$</center> | <center> $\\frac{2}{10}$ </center> | <center> </center>|<center> </center> |\n",
    "|<center> $$\\alpha = \\frac{1}{2}\\ln \\frac{1 - \\epsilon}{\\epsilon} $$</center> | <center> $\\frac{1}{2} \\ln (4)$ </center> | <center> </center>|<center> </center> |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### AdaBoost - calculating the new weights\n",
    "* Recall that the un-normalized weights update: $$ \\tilde{w}_{t+1}^{(i)} = w_t^{(i)} e^{-\\alpha_ty_ih_t(x_i)} $$\n",
    "* For the correctly classified data points (8 points): $$ \\tilde{w}_{t+1}^{(i)} = \\frac{1}{10}e^{-\\frac{1}{2}\\ln (4)} = \\frac{1}{10} \\cdot \\frac{1}{2} = \\frac{1}{20} $$\n",
    "* For the incorrectly classified data points (2 points): $$ \\tilde{w}_{t+1}^{(i)} = \\frac{1}{10}e^{\\frac{1}{2}\\ln (4)} = \\frac{1}{10} \\cdot 2 = \\frac{1}{5} $$\n",
    "* Calculate the normalization factor: $$ Z_t = 8 \\cdot \\frac{1}{20} + 2 \\cdot \\frac{1}{5} = \\frac{4}{5}  $$\n",
    "* The final weights after normalization:\n",
    "    * Correct: $w_{t+1}^{(i)} = \\frac{1}{20} \\cdot \\frac{5}{4} = \\frac{1}{16}$\n",
    "    * Incorrect: $w_{t+1}^{(i)} = \\frac{1}{5} \\cdot \\frac{5}{4} = \\frac{1}{4}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Similarly, we fill in the rest of the table:\n",
    "\n",
    "\n",
    "| <center> Parameters &nbsp; &nbsp; &nbsp; &nbsp;</center>| <center> Round 1 </center> | <center> Round 2 </center> | <center> Round 3 </center>  |\n",
    "| ----- | --- | --- | --- |\n",
    "|<center> w1</center> | <center> $\\frac{1}{10}$ </center> | <center> $\\frac{1}{16}$</center>|<center>$\\frac{3}{24}$ </center> |\n",
    "|<center> w2</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{1}{16}$ </center>|<center> $\\frac{1}{24}$</center> |\n",
    "|<center> w3</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{4}{16}$ </center>|<center>$\\frac{4}{24}$ </center> |\n",
    "|<center> w4</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{1}{16}$ </center>|<center> $\\frac{1}{24}$</center> |\n",
    "|<center> w5</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{1}{16}$ </center>|<center>$\\frac{1}{24}$ </center> |\n",
    "|<center> w6</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{1}{16}$ </center>|<center>$\\frac{3}{24}$ </center> |\n",
    "|<center> w7</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{1}{16}$ </center>|<center>$\\frac{3}{24}$ </center> |\n",
    "|<center> w8</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{1}{16}$ </center>|<center>$\\frac{1}{24}$ </center> |\n",
    "|<center> w9</center> | <center> $\\frac{1}{10}$ </center> | <center> $\\frac{1}{16}$</center>|<center>$\\frac{3}{24}$ </center> |\n",
    "|<center> w10</center> | <center> $\\frac{1}{10}$ </center> | <center>$\\frac{4}{16}$ </center>|<center>$\\frac{4}{24}$ </center> |\n",
    "|<center> $h$</center> | <center> $E$ </center> | <center> $B$ </center>|<center> $A$ </center> |\n",
    "|<center> Err - $\\epsilon$</center> | <center> $\\frac{2}{10}$ </center> | <center> $\\frac{1}{4}$ </center>|<center> $\\frac{7}{24}$ </center> |\n",
    "|<center> $$\\alpha = \\frac{1}{2}\\ln \\frac{1 - \\epsilon}{\\epsilon} $$</center> | <center> $\\frac{1}{2} \\ln (4)$ </center> | <center>  $\\frac{1}{2} \\ln (3)$ </center>|<center> $\\frac{1}{2} \\ln \\frac{17}{7}$ </center> |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### AdaBoost - Putting the classifiers together\n",
    "* The final classifier for 3 rounds of Boosting: $$ H(x) = sign(\\frac{1}{2} \\ln (4) \\cdot h_E(x) + \\frac{1}{2} \\ln (3) \\cdot h_B(x) + \\frac{1}{2} \\ln \\frac{17}{7} \\cdot h_A(x)) $$\n",
    "    * $h_c(x)$ returns +1 or -1 for $c=E,B,A$\n",
    "* The data points that the final classifier is correct about them:\n",
    "    * Since $\\alpha_E, \\alpha_B > \\alpha_A$ - it is just a *majority vote*\n",
    "    * Only one example (3) is misclassified"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### AdaBoost in Scikit-Learn\n",
    "* Scikit-Learn uses a multiclass version of AdaBoost called *SAMME* (Stagewise Additive Modeling using a Multiclass Exponential loss function).\n",
    "    * When there are just 2 classes, SAMME is equivalent to AdaBoost.\n",
    "    * If the predictors can estimate class probabilities (i.e. they have a `predict_proba()` method), Scikit-Learn can use a variant of SAMME called *SAMMER* (R for \"Real\"), which relies on class probabilities rather than predictions and generally performs better.\n",
    "    \n",
    "* The following code trains an AdaBoost classifier on 600 Decision Stumps.\n",
    "* Note: if the AdaBoost classifier is **overfitting** the training set, a good regularization may be reducing the number of estimators or more strongly regularize the base classifier.\n",
    "* An important drawback to sequential learning is that **it cannot be parallelized**, since each predictor can only be trained after the previous predictor has been trained and evaluated. Thus, it does not scale as well as bagging or pasting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "adaboost accuracy: 0.930\n"
     ]
    }
   ],
   "source": [
    "# AdaBoost\n",
    "ada_clf = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=600, algorithm=\"SAMME.R\", learning_rate=0.5)\n",
    "ada_clf.fit(x_train, y_train)\n",
    "y_pred = ada_clf.predict(x_test)\n",
    "ada_acc = accuracy_score(y_test, y_pred)\n",
    "print(\"adaboost accuracy: {:.3f}\".format(ada_acc))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <img src=\"https://img.icons8.com/bubbles/50/000000/video-playlist.png\" style=\"height:50px;display:inline\"> Recommended Videos\n",
    "---\n",
    "#### <img src=\"https://img.icons8.com/cute-clipart/64/000000/warning-shield.png\" style=\"height:30px;display:inline\"> Warning!\n",
    "* These videos do not replace the lectures and tutorials.\n",
    "* Please use these to get a better understanding of the material, and not as an alternative to the written material.\n",
    "\n",
    "#### Video By Subject\n",
    "\n",
    "* Simple Ensemble, Mixture of Experts - <a href=\"https://www.youtube.com/watch?v=Yvn3--rIdZg\">Ensembles (1): Basics</a>\n",
    "* Bagging - <a href=\"https://www.youtube.com/watch?v=Rm6s6gmLTdg\">Ensembles (2): Bagging</a>\n",
    "* Boosting, AdaBoost - <a href=\"https://www.youtube.com/watch?v=toOAToTaGV4\">Machine Learning Lecture 34 \"Boosting / Adaboost\" -Cornell CS4780</a>\n",
    "    * <a href=\"https://www.youtube.com/watch?v=UHBmv7qCey4\">MIT - 6.034 Artificial Intelligence -  Learning: Boosting</a>\n",
    "    * <a href=\"https://www.youtube.com/watch?v=ix6IvwbVpw0\">Ensembles (4): AdaBoost</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## <img src=\"https://img.icons8.com/dusk/64/000000/prize.png\" style=\"height:50px;display:inline\"> Credits\n",
    "---\n",
    "* Icons from <a href=\"https://icons8.com/\">Icon8.com</a> - https://icons8.com\n",
    "* Datasets from <a href=\"https://www.kaggle.com/\">Kaggle</a> - https://www.kaggle.com/\n",
    "* Examples and code snippets were taken from <a href=\"http://shop.oreilly.com/product/0636920052289.do\">\"Hands-On Machine Learning with Scikit-Learn and TensorFlow\"</a>"
   ]
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}