9 - Boosting/Boosting.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc-sa/4.0/\"><img alt=\"Creative Commons License\" align=\"left\" src=\"https://i.creativecommons.org/l/by-nc-sa/4.0/80x15.png\" /></a>&nbsp;| [Emmanuel Rachelson](https://personnel.isae-supaero.fr/emmanuel-rachelson?lang=en) | <a href=\"https://supaerodatascience.github.io/machine-learning/\">https://supaerodatascience.github.io/machine-learning/</a>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"font-size:22pt; line-height:25pt; font-weight:bold; text-align:center;\">Boosting</div>\n",
    "\n",
    "Boosting is a procedure that combines several \"weak\" predictors into a powerful \"committee\". It belongs to the family of committee-based or ensemble methods in Machine Learning.\n",
    "\n",
    "The most popular Boosting algorithm is AdaBoost.M1 (Freund & Schapire, 1997).\n",
    "\n",
    "A motivation for Boosting:<br>\n",
    "*AdaBoost with trees is the best off-the-shelf classifier in the world.* (Breiman 1998)<br>\n",
    "It is not so true anymore today but still accurate enough in practice.\n",
    "\n",
    "For recent criticism on that statement, see:<br>\n",
    "**Random classification noise defeats all convex potential boosters.**<br>\n",
    "P.H. Long, R.A. Servedio, *Machine Learning*, **78**(3), 287-304, (2008).\n",
    "\n",
    "In this notebook we take a very practical approach. For a more thorough and rigorous presentation, see (for instance) the reference below.<br>\n",
    "**The boosting approach to machine learning: An overview.**<br>\n",
    "R. E. Schapire. *MSRI workshop on Nonlinear Estimation and Classification*, (2002).\n",
    "\n",
    "1. [Probably Approximately Correct learning](#sec1)\n",
    "2. [AdaBoost](#sec2)\n",
    "3. [Implementing AdaBoost with trees](#sec3)\n",
    "4. [AdaBoost in scikit-learn](#sec4)\n",
    "5. [Gradient Boosting](#sec5)\n",
    "6. [Examples](#sec6)\n",
    "    1. [Spam or Ham?](#sec6-1)\n",
    "    2. [NIST](#sec6-2)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Probably Approximately Correct learning\n",
    "\n",
    "Probably approximately correct (PAC) learning theory helps analyze whether and under what conditions a learning algorithm will probably output an approximately correct classifier.\n",
    "\n",
    "**\"Approximately correct\"**. A classifier $h(x)=y$ belonging to some family of fonctions $\\mathcal{H}$ and generated by the considered learning algorithm is approximately correct if its error over the distribution $p$ of inputs (its generalization error) is bounded by some $\\varepsilon$ (with $0\\leq \\varepsilon \\leq \\frac{1}{2}$), that is $\\mathbb{E}_{x\\sim p} \\left( h\\left(x\\right)\\neq\\left(x\\in c \\right) \\right) = \\int\\limits_X I_{h\\left(x\\right)\\neq\\left(x\\in c\\right)} \\textrm{d}p(x) \\leq \\varepsilon$.\n",
    "\n",
    "**\"Probably\"**. If, given enough data, the algorithm will output such an approximately correct classifier with probability $1-\\delta$ (with $0 \\leq \\delta \\leq \\frac{1}{2}$), we call that algorithm *Probably Approximately Correct* (PAC).\n",
    "\n",
    "In other words, an algorithm generating classifiers $h(x)=y$ is said to be a *Probably Approximately Correct* (PAC) learner (or *PAC-strong* learner) if,<br>\n",
    "for all $\\left\\{\\begin{array}{l}\n",
    "p\\textrm{ a distribution over } X\\\\\n",
    "\\varepsilon \\in ]0;0.5[\\\\\n",
    "\\delta \\in ]0;0.5[\\\\\n",
    "c \\in \\mathcal{P}(X) \\textrm{ a subset of X defining a classification task}\n",
    "\\end{array}\\right.$, given enough training data,\n",
    "$$\\mathbb{P}\\left(\\int\\limits_X I_{h\\left(x\\right)\\neq\\left(x\\in c\\right)} \\textrm{d}p(x)\\leq \\varepsilon\\right) \\geq 1-\\delta.$$\n",
    "\n",
    "Knowing that a target concept $h(x)=y$ is PAC-learnable allows one to lower bound the sample size $m$ necessary to probably learn an approximately correct classifier:\n",
    "$$m\\geq \\frac{1}{\\varepsilon} \\left( \\log|\\mathcal{H}| + \\log\\left(\\frac{1}{\\delta}\\right) \\right)$$\n",
    "\n",
    "This lower bound implies that:\n",
    "- As the precision requirement gets harder (as $\\varepsilon$ gets closer to zero) the necessary sample size increases.\n",
    "- Similarly, if the number of possible classifiers ($|\\mathcal{H}|$) increases, the sample size required to disambiguate between two classifiers with good probability increases.\n",
    "- Finally, as the desired probability of correctness increases (as $\\delta$ gets closer to zero), the required sample size increases as well.\n",
    "\n",
    "Want more details?<br>\n",
    "**A theory of the learnable.**<br>\n",
    "L.G. Valiant. *Communications of the ACM*, **27**(11):1134-1142, (1984).<br>\n",
    "**The strength of weak learnability.**<br>\n",
    "R.E. Schapire. *Machine Learning*, **5**(2), 197-227, (1990).<br>\n",
    "[Wikipedia page on sample complexity](https://en.wikipedia.org/wiki/Sample_complexity)\n",
    "\n",
    "An algorithm generating classifiers $h(x)=y$ is said to be a *weak* (or *PAC-weak*) learner if, for any training set, it performs better than a random guessing on the training data.\n",
    "This means that its generalization error is strictly below than 0.5 with high probability, formally:\n",
    "$$\\exists \\gamma > 0, \\mathbb{P}\\left(\\int\\limits_X I_{h\\left(x\\right)\\neq\\left(x\\in c\\right)} \\textrm{d}p(x)\\leq 0.5 - \\gamma \\right) \\geq 1-\\delta.$$\n",
    "This is almost the same property as PAC-strong, but restricted to the existence of an $\\epsilon$ smaller than 0.5 rather than for any value of $\\epsilon$."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"sec2\"></a> 2. AdaBoost\n",
    "\n",
    "AdaBoost constructs a PAC-strong classifier $f$ as a linear combination of weak classifiers $h_t(x)$:\n",
    "$$f(x) = \\sum\\limits_{t=1}^T \\alpha_t h_t(x)$$\n",
    "\n",
    "The algorithm:\n",
    "\n",
    "Given $\\left\\{\\left(x_i,y_i\\right)\\right\\}_{1 \\leq i \\leq q}, x_i \\in X, y_i \\in \\{-1;1\\}$.<br>\n",
    "Initialize weights $D_1(i) = \\frac{1}{q}$<br>\n",
    "For $t=1$ to $T$:\n",
    "\n",
    "* Find $h_t = \\arg\\min\\limits_{h\\in\\mathcal{H}} \\sum\\limits_{i=1}^q D_t(i) I(y_i\\neq h(x_i))$\n",
    "* If $\\epsilon_t = \\sum\\limits_{i=1}^q D_t(i) I(y_i\\neq h_t(x_i)) \\geq 1/2$ then stop\n",
    "* Set $\\alpha_t = \\frac{1}{2} \\log\\left(\\frac{1-\\epsilon_t}{\\epsilon_t}\\right)$\n",
    "* Update\n",
    "$$D_{t+1}(i) = \\frac{D_t(i) e^{-\\alpha_t y_i h_t(x_i)}}{Z_t}$$\n",
    "Where $Z_t$ is a normalisation factor.\n",
    "\n",
    "Return the classifier\n",
    "$$H(x) = sign\\left(\\sum\\limits_{t=1}^T \\alpha_t h_t(x) \\right)$$\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Consequently, AdaBoost learns a sequence of classifiers, by performing *iterative reweighting* over the training data.\n",
    "\n",
    "$$D_{t+1}(i) = \\frac{D_t(i) e^{-\\alpha_t y_i h_t(x_i)}}{Z_t}$$\n",
    "\n",
    "- Increase the weight of incorrectly classified samples\n",
    "- Decrease the weight of correctly classified samples\n",
    "- Memory effect: a sample misclassified several times has a large $D(i)$\n",
    "- $h_t$ focusses on samples that were misclassified by $h_0, \\ldots, h_{t-1}$\n",
    "\n",
    "Property of the training error:\n",
    "\n",
    "$$\\frac{1}{q} \\sum\\limits_{i=1}^q I\\left(H(x_i)\\neq y_i\\right) \\leq \\prod\\limits_{t=1}^T Z_t$$\n",
    "\n",
    "- To minimize training error at each step $t$, minimize this upper bound.<br>\n",
    "$\\rightarrow$ This is where $\\alpha_t = \\frac{1}{2} \\log\\left(\\frac{1-\\epsilon_t}{\\epsilon_t}\\right)$ comes from.\n",
    "- This is actually equivalent to maximizing a (geometrical) margin.\n",
    "\n",
    "Many variants of AdaBoost:\n",
    "- Binary classification AdaBoost.M1, AdaBoost.M2, ...\n",
    "- Multiclass AdaBoost.MH,\n",
    "- Regression AdaBoost.R,\n",
    "\n",
    "And other Boosting algorithms (BrownBoost, AnyBoost...).\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "AdaBoost is a meta-algorithm: it \"boosts\" a weak classification algorithm into a committee that is a strong classifier.\n",
    "<ul>\n",
    "<li> AdaBoost maximizes margin\n",
    "<li> Very simple to implement\n",
    "<li> Can be seen as a feature selection algorithm\n",
    "<li> In practice, AdaBoost often avoids overfitting.\n",
    "</ul>\n",
    "</div>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"sec3\"></a> 3. Implementing AdaBoost with trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn import datasets\n",
    "from sklearn.utils import shuffle\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "X1, y1 = datasets.make_gaussian_quantiles(cov=2.,\n",
    "                                 n_samples=300, n_features=2,\n",
    "                                 n_classes=2, random_state=1)\n",
    "X2, y2 = datasets.make_gaussian_quantiles(mean=(3, 3), cov=1.5,\n",
    "                                 n_samples=700, n_features=2,\n",
    "                                 n_classes=2, random_state=1)\n",
    "X = np.concatenate((X1, X2))\n",
    "y = np.concatenate((y1, - y2 + 1))\n",
    "y = 2*y-1\n",
    "\n",
    "X, y = shuffle(X, y)\n",
    "\n",
    "Xtest,X = np.split(X,[400])\n",
    "ytest,y = np.split(y,[400])\n",
    "\n",
    "Xblue = X[y==-1]\n",
    "Xred = X[y==1]\n",
    "plt.figure(figsize=(7,7))\n",
    "plt.scatter(Xblue[:,0],Xblue[:,1],c='b',s=20)\n",
    "_=plt.scatter(Xred[:,0],Xred[:,1],c='r',s=20)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's grow a first tree and display it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import tree\n",
    "from os import system\n",
    "from IPython.display import Image\n",
    "\n",
    "dt1 = tree.DecisionTreeClassifier(criterion='entropy',max_depth=3)\n",
    "dt1.fit(X,y)\n",
    "\n",
    "\n",
    "tree.plot_tree(dt1)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like to plot the tree's decision boundary. Let's take this occasion to plot the misclassified training points (in cyan and magenta)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_decision_boundary(t, X, y, fig_size=(7,7)):\n",
    "    plot_step = 0.02\n",
    "    x0_min, x0_max = X[:, 0].min() - 1, X[:, 0].max() + 1\n",
    "    x1_min, x1_max = X[:, 1].min() - 1, X[:, 1].max() + 1\n",
    "    xx0, xx1 = np.meshgrid(np.arange(x0_min, x0_max, plot_step), np.arange(x1_min, x1_max, plot_step))\n",
    "    yypred = t.predict(np.c_[xx0.ravel(),xx1.ravel()])\n",
    "    yypred = yypred.reshape(xx0.shape)\n",
    "    plt.figure(figsize=fig_size)\n",
    "    plt.contourf(xx0, xx1, yypred, cmap=plt.cm.Paired)\n",
    "    y_pred = t.predict(X)\n",
    "    Xblue_good = X[np.equal(y,-1)*np.equal(y,y_pred)]\n",
    "    Xblue_bad  = X[np.equal(y,-1)*np.not_equal(y,y_pred)]\n",
    "    Xred_good  = X[np.equal(y,1)*np.equal(y,y_pred)]\n",
    "    Xred_bad   = X[np.equal(y,1)*np.not_equal(y,y_pred)]\n",
    "    plt.scatter(Xblue_good[:,0],Xblue_good[:,1],c='b',s=20)\n",
    "    plt.scatter(Xblue_bad[:,0],Xblue_bad[:,1],c='c',marker='v',s=20)\n",
    "    plt.scatter(Xred_good[:,0],Xred_good[:,1],c='r',s=20)\n",
    "    plt.scatter(Xred_bad[:,0],Xred_bad[:,1],c='m',marker='v',s=20)\n",
    "    plt.show()\n",
    "\n",
    "plot_decision_boundary(dt1, X, y)\n",
    "print(\"Training error: %g\"%(1-dt1.score(X,y)))\n",
    "print(\"Testing error:  %g\"%(1-dt1.score(Xtest,ytest)))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To implement our AdaBoost algorithm, we will need a function that evaluates the majority vote of a given set of trees (a forest) and another function that plots the forest's decision boundary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forest_predict(f, weights, X):\n",
    "    N = len(f)\n",
    "    votes = np.zeros((X.shape[0],N))\n",
    "    for i in range(N):\n",
    "        votes[:,i] = weights[i]*f[i].predict(X)\n",
    "    pred = np.sum(votes,axis=1)\n",
    "    return np.sign(pred)\n",
    "\n",
    "def plot_decision_boundary_forest(f, weights, X, y, fig_size=(7,7)):\n",
    "    plot_step = 0.02\n",
    "    x0_min, x0_max = X[:, 0].min() - 1, X[:, 0].max() + 1\n",
    "    x1_min, x1_max = X[:, 1].min() - 1, X[:, 1].max() + 1\n",
    "    xx0, xx1 = np.meshgrid(np.arange(x0_min, x0_max, plot_step), np.arange(x1_min, x1_max, plot_step))\n",
    "    yypred = forest_predict(f, weights, np.c_[xx0.ravel(),xx1.ravel()])\n",
    "    yypred = yypred.reshape(xx0.shape)\n",
    "    plt.figure(figsize=fig_size)\n",
    "    plt.contourf(xx0, xx1, yypred, cmap=plt.cm.Paired)\n",
    "    y_pred = forest_predict(f, weights, X)\n",
    "    Xblue_good = X[np.equal(y,-1)*np.equal(y,y_pred)]\n",
    "    Xblue_bad  = X[np.equal(y,-1)*np.not_equal(y,y_pred)]\n",
    "    Xred_good  = X[np.equal(y,1)*np.equal(y,y_pred)]\n",
    "    Xred_bad   = X[np.equal(y,1)*np.not_equal(y,y_pred)]\n",
    "    plt.scatter(Xblue_good[:,0],Xblue_good[:,1],c='b',s=20)\n",
    "    plt.scatter(Xblue_bad[:,0],Xblue_bad[:,1],c='c',marker='v',s=20)\n",
    "    plt.scatter(Xred_good[:,0],Xred_good[:,1],c='r',s=20)\n",
    "    plt.scatter(Xred_bad[:,0],Xred_bad[:,1],c='m',marker='v',s=20)\n",
    "    plt.show()\n",
    "\n",
    "forest = [dt1]\n",
    "plot_decision_boundary_forest(forest,np.ones(1),X,y)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can implement an AdaBoost algorithm with trees and visualize its decision boundary.<br>\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Exercice**:<br>\n",
    "Using the elements introduced above, implement AdaBoost on a forest containing 100 trees, trained on the current dataset.<br>\n",
    "Display how the decision boundary evolves.<br>\n",
    "Plot on the same graph the evolution of the training and testing errors.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %load solutions/code1.py\n",
    "### WRITE YOUR CODE HERE\n",
    "# If you get stuck, uncomment the line above to load a correction in this cell (then you can execute this code).\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Question**:\n",
    "Is there a tendency to overfit?\n",
    "</div>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# <a id=\"sec4\"></a> 4. AdaBoost in scikit-learn\n",
    "\n",
    "Scikit-learn provides an [AdaBoost](http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html#sklearn.ensemble.AdaBoostClassifier) meta-algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.ensemble import AdaBoostClassifier\n",
    "\n",
    "boosted_forest = AdaBoostClassifier(tree.DecisionTreeClassifier(criterion='entropy',max_depth=3), n_estimators=100)\n",
    "boosted_forest.fit(X,y)\n",
    "\n",
    "plot_decision_boundary(boosted_forest,X,y)\n",
    "print(\"Training score:\", boosted_forest.score(X,y))\n",
    "print(\"Testing score: \", boosted_forest.score(Xtest,ytest))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# <a id=\"sec5\"></a> 5. Gradient Boosting\n",
    "\n",
    "AdaBoost incrementally builds a committee of classifiers (or regressors) where each one tries to compensate the weaknesses of all the previous ones. This description makes it sound a lot like gradient descent.\n",
    "\n",
    "Let's write $f_k = \\{h_0,\\ldots,h_k\\}$ the committee predictor obtained at step $k$. $f_k$ is a point in $\\mathcal{H}$ and our goal is to find the function (the point) in $\\mathcal{H}$ that minimizes a certain loss function $L(f), \\ f\\in\\mathcal{H}$. Therefore, $h_{k+1}$ should point in the opposite direction of the gradient of $L$ with respect to functions $f$.\n",
    "\n",
    "This is precisely the idea of Gradient Boosting, that extends traditionnal Boosting to any differentiable loss function. Let's write this formally.\n",
    "\n",
    "Suppose we have a loss function $L(f(x),y)$ that quantifies how bad a predictor $f$ is, given the true data pair $(x,y)$. This could be a squared error, a cross-entropy, or any other loss function that compares $f(x)$ to the true $(x,y)$ data.\n",
    "\n",
    "Our goal is to find $f_{k+1}$ so that it compensates the error of $f_k$ made at each input $x$. In other words, we would like to move the output of the predictor $f_k$ so that the loss reduces at each $x$. Thus, we will look at the variation of the loss with respect to the variation of the prediction of $f_k$. Formally, this is the derivative of the loss $L(f_k(x), y)$ with respect to the prediction $f_k(x)$.\n",
    "$$\\frac{\\partial L(f_k(x), y)}{\\partial f_k(x)}$$\n",
    "\n",
    "As in gradient descent, by adding the new weak learner $h_k$, we would like to move in the opposite direction (steepest descent reducing the loss) from a certain quantity $\\alpha_k$:\n",
    "$$f_{k+1} = f_{k} - \\alpha_{k} h_{k}$$\n",
    "\n",
    "Practically, we do not have an estimate of $\\frac{\\partial L(f_k(x), y)}{\\partial f_k(x)}$ for any $x$, but only on the data set $\\{(x_i, y_i)\\}_i$. This yields the following desired value of $h_{k}$ for all $(x_i, y_i)$: $\\frac{\\partial L(f_k(x_i), y_i)}{\\partial f_k(x_i)}$.\n",
    "Thus, we will seek to fit $h_k$ to the following training set:\n",
    "$$\\left\\{ \\left(x_i, \\frac{\\partial L(f(x_i), y_i)}{\\partial f(x_i)} \\right) \\right\\}_i$$\n",
    "\n",
    "This result is the essence of the gradient boosting method. The latter training set can be seen as the set of points that compensates the error (or reduces the loss) of $f_k$ at each $x_i$.\n",
    "\n",
    "Notice that for gradient boosting to be applied, the only requirement is for the loss function to be differentiable. The weak learners themselves could be any functions.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "The algorithm can be written as follows:\n",
    "\n",
    "$f_0 = \\arg\\min_\\gamma \\sum_i L(\\gamma, y_i)$<br>\n",
    "For $k=1$ to $K$\n",
    "* Compute the pseudo-residuals\n",
    "$$r_i = \\left[ \\frac{\\partial L(f(x_i), y)}{\\partial f(x_i)} \\right]_{f = f_{k-1}}$$\n",
    "* Train $h_k$ to fit the dataset $\\left(x_i, r_i\\right)$\n",
    "* Find $\\alpha_k$ though line search\n",
    "$$\\alpha_{k} = \\arg\\min_\\alpha \\left[ \\sum_i L\\left(f_{k-1}(x_i) + \\alpha h_{k}(x_i),y_i\\right) \\right]$$\n",
    "* Update the model\n",
    "$$f_k = f_{k-1} + \\alpha_k h_k$$\n",
    "Return $f_K$\n",
    "\n",
    "\n",
    "AdaBoost is actually a Gradient Boosting procedure.\n",
    "\n",
    "When $\\mathcal{H}$ is the set of regression or classification trees, Gradient Boosting is called **Gradient Tree Boosting**. Several extensions (regularization, local step-sizes, etc.) are possible in that case.\n",
    "\n",
    "The most well-known Gradient Boosting library is called [XGBoost](https://github.com/dmlc/xgboost). It is efficient and quite flexible. It has be used to win several Data Science competitions. But Scikit-Learn also provides a decent implementation that we will use below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.ensemble import GradientBoostingClassifier\n",
    "\n",
    "gtb = GradientBoostingClassifier(n_estimators=100)\n",
    "gtb.fit(X,y)\n",
    "\n",
    "plot_decision_boundary(gtb,X,y)\n",
    "print(\"Training score:\", gtb.score(X,y))\n",
    "print(\"Testing score: \", gtb.score(Xtest,ytest))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Forward stagewise boosting (Algorithm 10.2) is also a very greedy strategy.\n",
    "At each step the solution tree is the one that maximally reduces (10.29)# <a id=\"sec6\"></a> 6. Examples\n",
    "\n",
    "If you have done the previous notebooks, you are used to these two examples now.\n",
    "\n",
    "## <a id=\"sec6-1\"></a>6.1 Spam or ham?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import path\n",
    "path.append('../2 - Text data preprocessing')\n",
    "import load_spam\n",
    "spam_data = load_spam.spam_data_loader()\n",
    "spam_data.load_data()\n",
    "\n",
    "Xtrain, ytrain, Xtest, ytest = spam_data.split(2000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_ada = AdaBoostClassifier(tree.DecisionTreeClassifier(criterion='entropy',max_depth=3), n_estimators=100)\n",
    "spam_ada.fit(Xtrain,ytrain)\n",
    "print(\"score:\", spam_ada.score(Xtest,ytest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_gtb = GradientBoostingClassifier(n_estimators=100)\n",
    "spam_gtb.fit(Xtrain,ytrain)\n",
    "print(\"score:\", spam_gtb.score(Xtest,ytest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Xtrain, ytrain, Xtest, ytest = spam_data.split(2000, feat='wordcount')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_ada = AdaBoostClassifier(tree.DecisionTreeClassifier(criterion='entropy',max_depth=3), n_estimators=100)\n",
    "spam_ada.fit(Xtrain,ytrain)\n",
    "print(\"score:\", spam_ada.score(Xtest,ytest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_gtb = GradientBoostingClassifier(n_estimators=100)\n",
    "spam_gtb.fit(Xtrain,ytrain)\n",
    "print(\"score:\", spam_gtb.score(Xtest,ytest))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"sec6-2\"></a> 6.2 NIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import datasets\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "digits = datasets.load_digits()\n",
    "#print(digits.data.shape)\n",
    "#print(digits.images.shape)\n",
    "#print(digits.target.shape)\n",
    "#print(digits.target_names)\n",
    "\n",
    "X = digits.data\n",
    "y = digits.target\n",
    "Xtrain,Xtest = np.split(X,[1000])\n",
    "ytrain,ytest = np.split(y,[1000])\n",
    "\n",
    "#print(digits.DESCR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.utils import shuffle\n",
    "\n",
    "def shuffle_and_split(X,y,n):\n",
    "    X0,y0 = shuffle(X,y)\n",
    "    Xtrain,Xtest = np.split(X0,[n])\n",
    "    ytrain,ytest = np.split(y0,[n])\n",
    "    return Xtrain, ytrain, Xtest, ytest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(Xtrain.shape)\n",
    "print(ytrain.shape)\n",
    "digits_ada = AdaBoostClassifier(tree.DecisionTreeClassifier(criterion='entropy',max_depth=3), n_estimators=100)\n",
    "digits_ada.fit(Xtrain,ytrain)\n",
    "prediction = digits_ada.predict(Xtest)\n",
    "#print(\"Training error:\", np.sum(np.not_equal(prediction,ytest))/len(ytest))\n",
    "print(\"Generalization error:\", np.sum(np.not_equal(prediction,ytest))/len(ytest) )\n",
    "print(\"Generalization score:\", digits_ada.score(Xtest,ytest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "digits_gtb = GradientBoostingClassifier(n_estimators=100)\n",
    "digits_gtb.fit(Xtrain,ytrain)\n",
    "prediction = digits_ada.predict(Xtest)\n",
    "#print(\"Training error:\", np.sum(np.not_equal(prediction,ytest))/len(ytest))\n",
    "print(\"Generalization error:\", np.sum(np.not_equal(prediction,ytest))/len(ytest) )\n",
    "print(\"Generalization score:\", digits_gtb.score(Xtest,ytest))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"sec6\"></a> 6.3 Further Examples\n",
    "\n",
    "**Questions** :\n",
    "- Choose one of the dataset that you have used in a previous notebook - with a binary classification task. Compare both algorithm performances on this dataset.\n",
    "- Identify which parameter acts as a discrimination threshold on each algorithm and compare both of them using a ROC curve."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "232px",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}