{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Boosting\n", "\n", "Another effective ensemble method for classification and regression is gradient boosting, or **boosting**. Boosting was originally derived in the computational learning theory literature, where it was proved that one could boost the performance of any \"weak\" learner arbitrarily high, provided the weak learner could always perform slightly better than chance. The idea is that by sequentially applying very fast, simple models, we can get a total model error which is better than any of the individual pieces. Hastie and Tibshirani describe it as:\n", "\n", "> one of the most powerful learning ideas introduced in the last twenty years.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## AdaBoost\n", "\n", "One of the simplest and most prevalent boosting algorithms is the **AdaBoost.M1** method by [Freund and Schapire (1997)](http://www.sciencedirect.com/science/article/pii/S002200009791504X), which aims to improve the accuracy of *any* learning algorithm.\n", "\n", "If we consider a binary output, coded as $Y \\in \\{-1,1\\}$. We can define the error rate of some classifier $G(X)$ as:\n", "\n", "$$\\overline{err} = \\frac{1}{N} \\sum_{i=1}^N I[y_i \\ne G(x_i)]$$\n", "\n", "A classifier is called a *weak* classifier when its error rate is only marginally better than random selection of outcomes. Boosting takes a weak classifier and applies it sequentially to data which have been weighted by having been passed through previous iterations of the classifier. A final prediction is produced by a weighted majority vote from all the classifiers.\n", "\n", "![adaboost](http://d.pr/i/1bTsQ+)\n", "\n", "Thus, the $\\alpha_m$ values are calculated by the classifier, and are used to weight the estimates in generating a final prediction. Observations that are misclassified by a given classifier are weighted more heavily so that they are given more emphasis in subsequent classification steps. Hence, observations that are more troublesome are given increasing influence, until they are classified correctly.\n", "\n", "### AdaBoost.M1\n", "\n", "1. Initialize observation weights uniformly: $w_i = 1/N$\n", "2. Iterate $m=1,\\ldots,M$:\n", " + Fit classifier $G_m(x)$ to training data, weighted by $w_i$\n", " + Calculate weighted classification error:\n", " $$\\text{err}_m = \\frac{\\sum_i w_i I[y_i \\ne G_m(x_i)]}{\\sum_i w_i}$$\n", " + Compute $\\alpha_m = \\log[(1-\\text{err}_m)/\\text{err}_m]$\n", " + Recalculate weights: $w_i = w_i \\exp(a_m I[y_i \\ne G_m(x_i)])$\n", "3. Return $G(x) = \\text{sign}[\\sum_m \\alpha_m G_m(x)]$\n", "\n", "\n", "Boosting is simply a form of forward stagewise additive modeling. It is a particular type of basis function expansion, of the general form:\n", "\n", "$$f(x | \\{\\beta_m, \\theta_m\\}) = \\sum_{m=1}^M \\beta_m b(x | \\theta_m)$$\n", "\n", "where the $\\beta_m$ are expansion coefficients and $b$ some multivariate function parameterized by $\\theta_m$. We saw an example of such basis expansions in the previous section on decision trees, where the $b$ are internal nodes and the predictions are terminal nodes.\n", "\n", "These models are fit by minimizing some loss function:\n", "\n", "$$\\min_{\\{\\beta_m, \\theta_m\\}} \\sum_{i=1}^N L(y_i, f(x | \\{\\beta_m, \\theta_m\\})$$\n", "\n", "We can approximate the optimization by adding the next basis function to a set of existing functions, without adjusting the parameters of the functions already added.\n", "\n", "The algorithm is as follows:\n", "\n", "1. Initialize $f_0(x) = 0$\n", "2. Iterate $m=1,\\ldots,M$:\n", " + Optimize:\n", " $$(\\beta_m, \\theta_m) = \\text{argmin}_{\\beta, \\theta} \\sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \\beta_m b(x|\\theta_m))$$\n", " + Set $f_m(x) = f_{m-1}(x) + \\beta_m b(x|\\theta_m)$\n", " \n", "We can use a function such as squared-error loss.\n", "\n", "Returning to AdaBoost.M1, we can use an exponential loss function:\n", "\n", "$$L(y, f(x)) = \\exp(-y \\alpha G(x))$$\n", "\n", "which means we need to calculate:\n", "\n", "$$(\\alpha_m, G_m) = \\text{argmin}_{\\alpha, G} \\sum_{i=1}^N w_i^{(m)} \\exp[-y_i \\alpha G(x_i)]$$\n", "\n", "where the weights are:\n", "\n", "$$w_i^{(m)} = \\exp[-y_i f_{m-1}(x)]$$\n", "\n", "Let's implement this algorithm in Python, and run it on some artificial data, which consists of two predictors, simulated from a uniform random number generator, with the class label set to 1 where both values are greater than 0.4, and -1 otherwise." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import seaborn as sns\n", "sns.set(style='darkgrid')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ndata = 50\n", "np.random.seed(42)\n", "\n", "train_data = np.random.rand(2, ndata)\n", "train_classes = np.where(((train_data[0,:]>0.4) & (train_data[1,:]>0.4)),1,-1)\n", "\n", "test_data = np.random.rand(2,ndata)\n", "test_classes = np.where(((test_data[0,:]>0.4) & (test_data[1,:]>0.4)),1,-1)\n", "\n", "fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10,4))\n", "ax1.plot(train_data[0, np.where(train_classes==-1)], train_data[1, np.where(train_classes==-1)],'ro')\n", "ax1.plot(train_data[0, np.where(train_classes==1)], train_data[1, np.where(train_classes==1)],'bo')\n", "ax1.set_title('Training Data')\n", "\n", "ax2.plot(test_data[0, np.where(test_classes==-1)], test_data[1, np.where(test_classes==-1)],'ro')\n", "ax2.plot(test_data[0, np.where(test_classes==1)], test_data[1, np.where(test_classes==1)],'bo')\n", "ax2.set_title('Test Data');" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can specify a very simple weak classifier that generates a class label by fitting only one of the two predictor variables, based on a threshold value." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def classify(data, true_classes, value):\n", " \n", " # Classify\n", " classes = np.where(data0, 1, -1)\n", " pred_test_classes = np.where(pred_test[m]>0, 1, -1)\n", " \n", " train_errors[m] = sum(pred_train_classes!=y_train)\n", " test_errors[m] = sum(pred_test_classes!=y_test)\n", " \n", " if m and (weighted_error==0 or weighted_error>=0.5):\n", " M=m\n", " print('exiting at',m)\n", " break\n", " \n", " plt.plot(np.arange(M), train_errors[:M]/N,'k-', np.arange(M), test_errors[:M]/N,'k--')\n", " plt.legend(('Training error','Test error'))\n", " plt.xlabel('Iterations')\n", " plt.ylabel('Error')\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "np.random.seed(42)\n", "\n", "adaboost(train_data, train_classes, test_data, test_classes)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So, the algorithm takes what is a weak classifier and iteratively builds a strong ensemble classifier.\n", "\n", "A similar approach can be applied to decision trees, whereby the simplest possible tree (depth=1) is used as a weak classifier at each step. This is often *worse* than random chance for classification at the outset, but when boosting is applied, the resulting classifier can be powerful. This approach to ensemble decision tree learning is called **stumping**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Boosting Trees\n", "\n", "Recall that for decision trees, we partition the space of all predictor variables into disjoint regions $R_j$, where some constant value $\\gamma_j$ (e.g. a mean) is returned for any points in the parameter space located within $R_j$. Formally, we can express a tree as:\n", "\n", "$$T(x|\\{R_j, \\gamma_j\\}) = \\sum_{j=1}^J \\gamma_j I(x \\in R_j)$$\n", "\n", "The optimization required to find the best parameters is computationally difficult, and we typically fall back on growing and pruning strategies to obtain a competitive solution that is not guaranteed to be optimal.\n", "\n", "An alternative approach is to apply boosting to tree-building, which is just a sum of trees:\n", "\n", "$$f_M(x) = \\sum_{m=1}^M T(x| \\{ R_{j}, \\gamma_{j} \\}_m)$$\n", "\n", "induced in a stagewise manner. Specifically, at each step we solve:\n", "\n", "$$(R_m, \\gamma_m) = \\text{argmin}_{R, \\gamma} \\sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i| \\{R_j, \\gamma_j\\}_m))$$\n", "\n", "where $L$ is a chosen loss function.\n", "\n", "So, we can implement the AdaBoost method here. \n", "\n", "However, solving the optimization above is difficult, so we fall back on numerical optimization to approximate a solution.\n", "\n", "\n", "### Gradient Tree Boosting Algorithm\n", "\n", "1. Initialize $f_0(x) = \\text{argmin}_{\\gamma} \\sum_i L(y_i, \\gamma)$\n", "2. Iterate from m=1 to M:\n", " + For all $i=1,\\ldots,N$ calculate:\n", " $$r_{im} = - \\left[\\frac{\\partial L(y_i,f(x_i))}{\\partial f(x_i)}\\right]_{f=f_{m-1}}$$\n", " + Fit a tree to $r_{im}$ and determine regions $R_{jm}$\n", " + Compute: \n", " $$\\gamma_{jm} = \\text{argmin}_{\\gamma} \\sum_{x_i \\in R_{jm}} L(y_i, f_{m-1}(x_i)\\gamma)$$\n", " + Update: \n", " $$f_m(x) = f_{m-1}(x) + \\sum_j \\gamma_{jm} I(x\\in R_{jm})$$\n", "3. Return boosted model: $\\hat{f}(x) =f_m(x)$\n", "\n", "It turns out, for squared error loss the negative gradient is just the **residual**:\n", "\n", "$$r_{im} = y_i - f_{m-1}(x_i)$$\n", "\n", "Thus, successive trees are fit to the residuals from the current model. The new tree is added to the function, and the residuals are updated." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Thus, for regression problems, boosting is a form of **functional gradient descent**. Boosting is a numerical optimization technique for minimizing the loss function by adding, at each step, a new tree that best reduces (by stepping down the gradient) the cost function. For boosted regression trees, the first regression tree is the one that, for the selected tree size, maximally reduces the loss function. For subsequent steps, the focus is on the residuals: on variation in the response that is not so far explained by the model.\n", "\n", "The process is *stagewise*, meaning that existing trees are left unchanged as the model is enlarged. Only the fitted value for each observation is re-estimated at each step to reflect the contribution of the newly added tree. The final model is a linear combination of many trees (usually hundreds to thousands) that can be thought of as a regression model where each term itself is a tree.\n", "\n", "The example below presents a simple artificial problem, generated from a sinoid function with random Gaussian noise. There are 100 training points (blue) for fitting the model and 100 test data points (red) which for evaluating the approximation." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "np.random.seed(13)\n", "\n", "def true_model(x):\n", " return x * np.sin(x) + np.sin(2 * x)\n", "\n", "def gen_data(n_samples=200):\n", " x = np.random.uniform(0, 10, size=n_samples)\n", " x.sort()\n", " y = true_model(x) + 0.75 * np.random.normal(size=n_samples)\n", " train_mask = np.random.randint(0, 2, size=n_samples).astype(np.bool)\n", " x_train, y_train = x[train_mask, np.newaxis], y[train_mask]\n", " x_test, y_test = x[~train_mask, np.newaxis], y[~train_mask]\n", " \n", " return x_train, x_test, y_train, y_test\n", " \n", "\n", "X_train, X_test, y_train, y_test = gen_data(200)\n", "\n", "x_plot = np.linspace(0, 10, 500)\n", "\n", "def plot_data(alpha=0.6):\n", " \n", " plt.figure(figsize=(8, 5))\n", " gt = plt.plot(x_plot, true_model(x_plot), alpha=alpha, label='true function')\n", "\n", " # plot training and testing data\n", " plt.scatter(X_train, y_train, s=10, alpha=alpha, label='training data')\n", " plt.scatter(X_test, y_test, s=10, alpha=alpha, color='red', label='testing data')\n", " plt.xlim((0, 10))\n", " plt.ylabel('y')\n", " plt.xlabel('x')\n", " plt.legend(loc='upper left')\n", " \n", "plot_data()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If you fit an **individual** regression tree to the above data you get a piece-wise constant approximation. The deeper you grow the tree the more constant segments you can accomodate thus the more variance you can capture." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.tree import DecisionTreeRegressor\n", "\n", "plot_data()\n", "est = DecisionTreeRegressor(max_depth=1).fit(X_train, y_train)\n", "plt.plot(x_plot, est.predict(x_plot[:, np.newaxis]),\n", " label='RT max_depth=1', color='g', alpha=0.9, linewidth=2)\n", "plt.legend(loc='upper left');" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.tree import DecisionTreeRegressor\n", "\n", "plot_data()\n", "est = DecisionTreeRegressor(max_depth=1).fit(X_train, y_train)\n", "plt.plot(x_plot, est.predict(x_plot[:, np.newaxis]),\n", " label='RT max_depth=1', color='g', alpha=0.9, linewidth=2)\n", "\n", "est = DecisionTreeRegressor(max_depth=3).fit(X_train, y_train)\n", "plt.plot(x_plot, est.predict(x_plot[:, np.newaxis]),\n", " label='RT max_depth=3', color='g', alpha=0.7, linewidth=1)\n", "\n", "plt.legend(loc='upper left');" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now lets examine the effect on the approximation by adding more trees. Scikit-learn provides two estimators for gradient boosting: GradientBoostingClassifier and GradientBoostingRegressor, both are located in the sklearn.ensemble submodule. The relevant hyperparameters for these estimators include:\n", "\n", " * number of regression trees (n_estimators)\n", " * depth of each individual tree (max_depth)\n", " * loss function (loss)\n", " * learning rate (learning_rate)\n", "\n", "The gradient boosting estimators allow you to evaluate the prediction of a model as a function of the number of trees via the staged_predict and stages_predict_proba methods. The return a generator that iterates over the predictions as you add more and more trees." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.ensemble import GradientBoostingClassifier, GradientBoostingRegressor\n", "from itertools import islice\n", "\n", "plot_data()\n", "\n", "max_depth = 1\n", "\n", "est = GradientBoostingRegressor(n_estimators=1000, max_depth=max_depth, learning_rate=1.0)\n", "est.fit(X_train, y_train)\n", "\n", "ax = plt.gca()\n", "first = True\n", "\n", "# step over prediction as we added 20 more trees.\n", "for pred in islice(est.staged_predict(x_plot[:, np.newaxis]), 0, 1000, 20):\n", " \n", " plt.plot(x_plot, pred, color='r', alpha=0.2)\n", " \n", " if first:\n", " ax.annotate('High bias - low variance', xy=(x_plot[x_plot.shape[0] // 2],\n", " pred[x_plot.shape[0] // 2]),\n", " xycoords='data',\n", " xytext=(3, 4), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", color='k',\n", " connectionstyle=\"arc\"))\n", " first = False\n", "\n", "pred = est.predict(x_plot[:, np.newaxis])\n", "plt.plot(x_plot, pred, color='r', label='GBRT max_depth={}'.format(max_depth))\n", "ax.annotate('Low bias - high variance', xy=(x_plot[x_plot.shape[0] // 2],\n", " pred[x_plot.shape[0] // 2]),\n", " xycoords='data', \n", " xytext=(6.25, -6),\n", " textcoords='data', \n", " arrowprops=dict(arrowstyle=\"->\", color='k',\n", " connectionstyle=\"arc\"))\n", "plt.legend(loc='upper left');" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The above plot shows 50 red lines, each shows the response of the GBRT model after 20 trees have been added. It starts with a very crude approximation that can only fit more-or-less constant functions (ie. _High bias - low variance_) but as we add more trees the more variance our model can capture resulting in the solid red line.\n", "\n", "We can see that the more trees we add to our GBRT model and the deeper the individual trees are the more variance we can capture thus the higher the complexity of our model. But as usual in machine learning model complexity trades off variance and bias.\n", "\n", "A *deviance plot* shows the training/testing error (or deviance) as a function of the number of trees." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "colors = '#1b9e77','#d95f02','#7570b3','#e7298a','#66a61e','#e6ab02','#a6761d','#666666'\n", "\n", "n_estimators = len(est.estimators_)\n", "\n", "def deviance_plot(est, X_test, y_test, ax=None, label='', train_color=colors[0], \n", " test_color=colors[1], alpha=1.0):\n", "\n", " test_dev = np.array([est.loss_(y_test, pred) for pred in est.staged_predict(X_test)])\n", "\n", " if ax is None:\n", " fig = plt.figure(figsize=(8, 5))\n", " ax = plt.gca()\n", " \n", " ax.plot(np.arange(n_estimators) + 1, test_dev, color=test_color, label='Test %s' % label, \n", " linewidth=2, alpha=alpha)\n", " ax.plot(np.arange(n_estimators) + 1, est.train_score_, color=train_color, \n", " label='Train %s' % label, linewidth=2, alpha=alpha)\n", " ax.set_ylabel('Error')\n", " ax.set_xlabel('n_estimators')\n", " ax.set_ylim((0, 2))\n", " \n", " return test_dev, ax" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "test_dev, ax = deviance_plot(est, X_test, y_test)\n", "ax.legend(loc='upper right')\n", "\n", "# add some annotations\n", "ax.annotate('Lowest test error', xy=(test_dev.argmin() + 1, test_dev.min() + 0.02), xycoords='data',\n", " xytext=(150, 1.0), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "\n", "ann = ax.annotate('', xy=(800, test_dev[799]), xycoords='data',\n", " xytext=(800, est.train_score_[799]), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"<->\", color='k'))\n", "ax.text(810, 0.25, 'train-test gap');" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The green line above shows the training error: it rapidly decreases in the beginning and then gradually slows down but keeps decreasing as we add more and more trees. The testing error (upper line) too decreases rapidly in the beginning but then slows down and reaches its minimum fairly early (~50 trees) and then even starts increasing.\n", "\n", "An increasing train-test gap is usually a sign of *overfitting*.\n", "\n", "The great thing about gradient boosting is that it provides a number of ways to control overfitting." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Regularization\n", "\n", "There are three tuning parameters to consider:\n", "\n", "1. The depth and number of trees (boosting can overfit with very large numbers of deep trees)\n", "2. Shrinkage parameter $\\lambda$ (typically 0.01 or 0.001; smaller values require more trees to be effective)\n", "3. Randomization\n", "\n", "#### Tree Structure\n", "\n", "The depth of the individual trees is one aspect of model complexity. The depth of the trees basically control the degree of feature **interactions** that your model can fit. For example, if you want to capture the interaction between a feature latitude and a feature longitude your trees need a depth of at least two to capture this. Unfortunately, the degree of feature interactions is not known in advance but it is usually fine to assume that it is faily low; in practice, a depth of 4-6 usually gives the best results. In scikit-learn you can constrain the depth of the trees using the max_depth argument.\n", "\n", "Another way to control the depth of the trees is by enforcing a lower bound on the number of samples in a leaf. This will avoid inbalanced splits where a leaf is formed for just one extreme data point. In scikit-learn you can do this using the argument min_samples_leaf. This is effectively a means to introduce bias into your model with the hope to also reduce variance as shown in the example below:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "colors = '#2ca25f', '#99d8c9', '#e34a33', '#fdbb84', '#c51b8a', '#fa9fb5'\n", "\n", "def fmt_params(params):\n", " return \", \".join(\"{0}={1}\".format(key, val) for key, val in params.items())\n", "\n", "fig = plt.figure(figsize=(8, 5))\n", "ax = plt.gca()\n", "for params, (test_color, train_color) in [({}, (colors[0], colors[1])),\n", " ({'min_samples_leaf': 3},\n", " (colors[2], colors[3])),\n", " ({'min_samples_leaf': 10},\n", " (colors[4], colors[5]))]:\n", " est = GradientBoostingRegressor(n_estimators=n_estimators, max_depth=1, learning_rate=1.0)\n", " est.set_params(**params)\n", " est.fit(X_train, y_train)\n", " \n", " test_dev, ax = deviance_plot(est, X_test, y_test, ax=ax, label=fmt_params(params),\n", " train_color=train_color, test_color=test_color)\n", " \n", "ax.annotate('Higher bias', xy=(900, est.train_score_[899]), xycoords='data',\n", " xytext=(600, 0.3), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "ax.annotate('Lower variance', xy=(900, test_dev[899]), xycoords='data',\n", " xytext=(600, 0.4), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "plt.legend(loc='upper right')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Shrinkage\n", "\n", "The most important regularization technique for GBRT is shrinkage: the idea is basically to do slow learning by strongly shrinking the predictions of each individual tree by some small scalar, the learning_rate. By doing so the model has to re-enforce concepts. A lower learning_rate requires a higher number of n_estimators to get to the same level of training error -- so its trading runtime against accuracy." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n_estimators = 6000" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fig = plt.figure(figsize=(8, 5))\n", "ax = plt.gca()\n", "for params, (test_color, train_color) in [({}, (colors[0], colors[1])),\n", " ({'learning_rate': 0.1},\n", " (colors[2], colors[3])),\n", " ({'learning_rate': 0.01},\n", " (colors[4], colors[5]))]:\n", " est = GradientBoostingRegressor(n_estimators=n_estimators, max_depth=1, learning_rate=1.0)\n", " est.set_params(**params)\n", " est.fit(X_train, y_train)\n", " \n", " test_dev, ax = deviance_plot(est, X_test, y_test, ax=ax, label=fmt_params(params),\n", " train_color=train_color, test_color=test_color)\n", " \n", "ax.annotate('Requires more trees', xy=(200, est.train_score_[199]), xycoords='data',\n", " xytext=(300, 1.0), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "ax.annotate('Lower test error', xy=(900, test_dev[899]), xycoords='data',\n", " xytext=(600, 0.5), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "plt.legend(loc='upper right')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Stochastic Gradient Boosting\n", "\n", "Similar to random forests, introducing **randomization** into the tree building process can lead to higher accuracy. Scikit-learn provides two ways to introduce randomization: \n", "\n", "1. subsampling the training set before growing each tree (subsample) \n", "2. subsampling the features before finding the best split node (max_features).\n", "\n", "Subsampling features works better if there is a sufficiently large number of features (>30).\n", "\n", "Both options reduce runtime.\n", "\n", "Below we show the effect of using subsample=0.5, ie. growing each tree on 50% of the training data, on our toy example:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fig = plt.figure(figsize=(8, 5))\n", "ax = plt.gca()\n", "\n", "for params, (test_color, train_color) in [({}, (colors[0], colors[1])),\n", " ({'learning_rate': 0.1, 'subsample': 0.5},\n", " (colors[2], colors[3]))]:\n", " est = GradientBoostingRegressor(n_estimators=n_estimators, max_depth=1, learning_rate=1.0,\n", " random_state=1)\n", " est.set_params(**params)\n", " est.fit(X_train, y_train)\n", " test_dev, ax = deviance_plot(est, X_test, y_test, ax=ax, label=fmt_params(params),\n", " train_color=train_color, test_color=test_color)\n", " \n", "ax.annotate('Even lower test error', xy=(400, test_dev[399]), xycoords='data',\n", " xytext=(500, 0.5), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "\n", "est = GradientBoostingRegressor(n_estimators=n_estimators, max_depth=1, learning_rate=1.0,\n", " subsample=0.5)\n", "est.fit(X_train, y_train)\n", "test_dev, ax = deviance_plot(est, X_test, y_test, ax=ax, label=fmt_params({'subsample': 0.5}),\n", " train_color=colors[4], test_color=colors[5], alpha=0.5)\n", "ax.annotate('Subsample alone does poorly', xy=(300, test_dev[299]), xycoords='data',\n", " xytext=(250, 1.0), textcoords='data',\n", " arrowprops=dict(arrowstyle=\"->\", connectionstyle=\"arc\", color='k'),\n", " )\n", "plt.legend(loc='upper right', fontsize='small')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Hyperparameter tuning\n", "\n", "We now have introduced a number of hyperparameters, each of which require selection via optimization, and some of which interact with each other (learning_rate and n_estimators, learning_rate and subsample, max_depth and max_features).\n", "\n", "We usually follow this recipe to tune the hyperparameters for a gradient boosting model:\n", "\n", " 1. Choose loss based on your problem at hand (i.e. target metric)\n", " 2. Pick n_estimators as large as (computationally) possible (e.g. 3000).\n", " 3. Tune max_depth, learning_rate, min_samples_leaf, and max_features via grid search.\n", " 4. Increase n_estimators even more and tune learning_rate again holding the other parameters fixed.\n", " \n", "Scikit-learn provides a convenient API for hyperparameter tuning and grid search:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.model_selection import GridSearchCV\n", "\n", "param_grid = {'learning_rate': [0.1, 0.05, 0.02, 0.01],\n", " 'max_depth': [4, 6],\n", " 'min_samples_leaf': [3, 5, 9, 17],\n", " # 'max_features': [1.0, 0.3, 0.1] ## not possible in our example (only 1 fx)\n", " }\n", "\n", "est = GradientBoostingRegressor(n_estimators=3000)\n", "# this may take some minutes\n", "gs_cv = GridSearchCV(est, param_grid, n_jobs=4).fit(X_train, y_train)\n", "\n", "# best hyperparameter setting\n", "gs_cv.best_params_" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example: California Housing\n", "\n", "This example shows how to apply GBRT to a real-world dataset. The task is to predict the log median house value for census block groups in California. The dataset is based on the 1990 censues comprising roughly 20.000 groups. There are 8 features for each group including: median income, average house age, latitude, and longitude.\n", "\n", "We will use Mean Absolute Error as our target metric and evaluate the results on an 80-20 train-test split." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import pandas as pd\n", "\n", "from sklearn.datasets.california_housing import fetch_california_housing\n", "from sklearn.model_selection import train_test_split\n", "\n", "cal_housing = fetch_california_housing()\n", "\n", "names = cal_housing.feature_names\n", "\n", "# split 80/20 train-test\n", "X_train, X_test, y_train, y_test = train_test_split(pd.DataFrame(cal_housing.data, columns=names),\n", " np.log(cal_housing.target),\n", " test_size=0.2,\n", " random_state=1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cal_housing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Some of the aspects that make this dataset challenging are: \n", "\n", "- heterogenous features (different scales and distributions) \n", "- non-linear feature interactions (specifically latitude and longitude)\n", "\n", "Furthermore, the data contains some extreme values of the response (log median house value). Hence, analysis of this dataset will benefit from robust regression techniques.\n", "\n", "Below are histograms showing some of the features, along with the response. You can see that they are quite different: median income is left skewed, latitude and longitude are bi-modal, and log median house value is right skewed." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import pandas as pd\n", "\n", "X_df = pd.DataFrame(data=X_train, columns=names)\n", "X_df['LogMedHouseVal'] = y_train\n", "_ = X_df.hist(column=['Latitude', 'Longitude', 'MedInc', 'LogMedHouseVal'])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lets fit a gradient boosteed regression tree (GBRT) model to this dataset and inspect the model:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "est = GradientBoostingRegressor(n_estimators=3000, max_depth=6, learning_rate=0.04,\n", " loss='huber', random_state=0)\n", "est.fit(X_train, y_train)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Huber loss (huber) is a loss function used in robust regression, that is less sensitive to outliers in data than the squared error loss.\n", "\n", "$$L_{\\delta}(x) = \\left\\{ \\begin{array}{lr}\n", "\\frac{1}{2} x^2 & \\text{for } |x| \\le \\delta\\\\\n", "\\delta (|x| - \\frac{1}{2} \\delta) & \\text{otherwise}\n", "\\end{array} \\right.$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.metrics import mean_absolute_error\n", "\n", "mae = mean_absolute_error(y_test, est.predict(X_test))\n", "print('MAE: %.4f' % mae)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Feature importance\n", "\n", "Often features do not contribute equally to predict the target response. When interpreting a model, the first question usually is: what are those important features and how do they contributing in predicting the target response?\n", "\n", "Feature importance in regression trees can be measured by the amount RSS is decreased due to splits over a given predictor, averaged over all trees.\n", "\n", "A GBRT model derives this information from the fitted regression trees which intrinsically perform feature selection by choosing appropriate split points. You can access this information via the instance attribute est.feature_importances_." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# sort importances\n", "indices = np.argsort(est.feature_importances_)\n", "\n", "# plot as bar chart\n", "plt.barh(np.arange(len(names)), est.feature_importances_[indices])\n", "plt.yticks(np.arange(len(names)) + 0.25, np.array(names)[indices])\n", "_ = plt.xlabel('Relative importance')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise: Gradient boosting for classification\n", "\n", "Smith et al. (1988) used statistical learning to forecast the onset of diabetes mellitus. The diagnostic, binary-valued variable investigated is whether the patient shows signs of diabetes according to World Health Organization criteria. The variables include:\n", "\n", "1. Number of times pregnant\n", "2. Plasma glucose concentration a 2 hours in an oral glucose tolerance test\n", "3. Diastolic blood pressure (mm Hg)\n", "4. Triceps skin fold thickness (mm)\n", "5. 2-Hour serum insulin (mu U/ml)\n", "6. Body mass index (weight in kg/(height in m)^2)\n", "7. Diabetes pedigree function\n", "8. Age (years)\n", "9. Class variable (0 or 1)\n", "\n", "Use the GradientBoostingClassifier to forecast diabetes using the available features." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "diabetes = pd.read_csv('../data/pima-indians-diabetes.data.txt', header=None, \n", " names=['n_pregnant', 'plasma_glucose', 'diastolic_bp', 'triceps_skin', 'insulin_2h',\n", " 'bmi', 'pedigree_function', 'age', 'diabetes'])\n", "diabetes.head()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Write your answer here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Partial dependence\n", "\n", "Partial dependence plots show the dependence between the response and a set of features, marginalizing over the values of all other features. Intuitively, we can interpret the partial dependence as the expected response as a function of the features we conditioned on.\n", "\n", "The plot below contains 4 one-way partial depencence plots (PDP) each showing the effect of an individual feature on the repsonse. We can see that median income MedInc has a linear relationship with the log median house value.\n", "\n", "The contour plot shows a two-way PDP. Here we can see an interesting feature interaction. It seems that house age itself has hardly an effect on the response but when AveOccup is small it has an effect (the older the house the higher the price)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.ensemble.partial_dependence import plot_partial_dependence\n", "\n", "features = ['MedInc', 'AveOccup', 'HouseAge', 'AveRooms',\n", " ('AveOccup', 'HouseAge'), ('MedInc', 'HouseAge')]\n", "fig, axs = plot_partial_dependence(est, X_train, features,\n", " feature_names=names, figsize=(14, 10))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Scikit-learn provides a convenience function to create such plots: sklearn.ensemble.partial_dependence.plot_partial_dependence or a low-level function that you can use to create custom partial dependence plots (e.g. map overlays or 3d plots). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## XGBoost\n", "\n", "[XGBoost](https://arxiv.org/abs/1603.02754) is an open-source, high-performance implementation of gradient boosting methods for decision trees. It features natively-parallel tree construction, out-of-core computation, and cache optimization, and is readily deployable on clusters. It typically offers better speed and performance relative to scikit-learn and other comparable libraries.\n", "\n", "![](http://d.pr/i/pjkGym+)\n", "\n", "![](http://d.pr/i/mlQJj9+)\n", "\n", "While XGBoost is a C++ library, it includes several interfaces:\n", "\n", "- Command Line Interface (CLI).\n", "- Python \n", "- R \n", "- Julia.\n", "- Java and Scala\n", "\n", "Its Python interface has a syntax that is compatible with scikit-learn." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "XGBoost can be installed from conda or pip." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "!conda install -y xgboost" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import xgboost as xgb\n", "\n", "dtrain = xgb.DMatrix(X_train, label=y_train)\n", "dtest = xgb.DMatrix(X_test, label=y_test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can set a number of parameters using a Python dict. Here are a few notables:\n", "\n", "- max_depth: maximum tree depth of each tree\n", "- eta: learning rate\n", "- gamma: Minimum loss reduction required to make a further partition on a leaf node of the tree (regularization)\n", "- silent: verbosity of output written to log\n", "- objective: objective function for error evaluation\n", "- eval_metric: evaluation metrics for validation data\n", "- subsample: subsampling of training data\n", "- colsample_bytree: subsampling ratio of columns\n", "- reg_alpha: L1 regularization\n", "- reg_lambda: L2 regularization\n", "- base_score: global bias term\n", "\n", "Here we will use a linear regression objective, since we are estimating house values." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "xgb_params = {\n", " 'max_depth': 10, \n", " 'eta': 0.1, \n", " 'objective': 'reg:squarederror',\n", " 'eval_metric': 'rmse'} " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Rather than instantiating an object, the parameters and data are passed to the train function." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "boosted_regmod = xgb.train(xgb_params, dtrain, num_boost_round=30)\n", "boosted_regmod" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice that some model parameters are passed as an argument to the train function. num_boost_round is the number of boosting rounds (or trees) to build. The appropriate value depends on the other parameters, and therefore needs to be tuned for each parameter set. \n", "\n", "Recall that trees are built sequentially. This allows us to test our model at each step and see if adding a new tree improves performance. We can specify a value for early_stopping_round such that if validation error does not decrease over that interval, training stops. This aslo requires a test dataset with the evals argument. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "boosted_regmod = xgb.train(xgb_params, dtrain, num_boost_round=1000, \n", " evals=[(dtest, \"Test\")], early_stopping_rounds=3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "boosted_regmod.dump_model('model_dump.txt')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "house_preds = boosted_regmod.predict(dtest)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.metrics import explained_variance_score\n", "\n", "explained_variance_score(house_preds, y_test)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "xgb.plot_importance(boosted_regmod)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To optimize the other hyperparameters, we can use the cv function. Here again we can specify a maximum number of boosting rounds (num_boost_round) and an associated early_stopping_rounds in order to find the optimial number of boosting rounds." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "xgb.cv(xgb_params, dtrain, nfold=5, num_boost_round=500, early_stopping_rounds=5, verbose_eval=1000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We may want to tune other parameters, such as max_depth and min_child_weight. The latter is the minimum weight required in order to create a new node in the tree. Smaller min_child_weight values allow the algorithm to create children that correspond to fewer samples, thus allowing for more complex trees (with the associated risk of overfitting).\n", "\n", "These two parameters can be used to alter the complexity of the trees, hence they should be tuned together. We can make a grid of candidate values for both and use cv to select the best combination." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "param_grid = [(max_depth, min_child_weight) for max_depth in (5, 10, 15) for min_child_weight in (3, 5, 7)]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "min_rmse = np.inf\n", "best_params = None\n", "\n", "for max_depth, min_child_weight in param_grid:\n", " print(\"CV with max_depth={}, min_child_weight={}\".format(\n", " max_depth,\n", " min_child_weight))\n", "\n", " # Update our parameters\n", " xgb_params['max_depth'] = max_depth\n", " xgb_params['min_child_weight'] = min_child_weight\n", "\n", " # Run CV\n", " cv_results = xgb.cv(\n", " xgb_params,\n", " dtrain,\n", " num_boost_round=50,\n", " nfold=5,\n", " metrics={'rmse'},\n", " early_stopping_rounds=3\n", " )\n", "\n", " # Update best score\n", " mean_rmse = cv_results['test-rmse-mean'].min()\n", " boost_rounds = cv_results['test-rmse-mean'].argmin()\n", " print(\"\\tRMSE {} for {} rounds\".format(mean_rmse, boost_rounds))\n", " if mean_rmse < min_rmse:\n", " min_rmse = mean_rmse\n", " best_params = (max_depth, min_child_weight)\n", "\n", "print(\"Best params: {}, {}, MAE: {}\".format(best_params[0], best_params[1], min_rmse))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is also a scikit-learn-compatible interface that uses DataFrames and NumPy arrays rather than DMatrix objects. These can be used with all of scikit-learn's utilities." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "xgbr = xgb.XGBRegressor(colsample_bytree=0.5, n_estimators=1000)\n", "xgbr.fit(X_train, y_train)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "predictions = xgbr.predict(X_test)\n", "explained_variance_score(predictions,y_test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example: Pitch classification\n", "\n", "Using the Statcast pitch dataset from the previous notebook, use gradient boosted trees to predict pitch type, and compare the performance to that of random forests." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "pitches = pd.read_csv('../data/pitches.csv', index_col=0)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Write your answer here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## References \n", "\n", "T. Hastie, R. Tibshirani and J. Friedman. (2009) [Elements of Statistical Learning: Data Mining, Inference, and Prediction](http://statweb.stanford.edu/~tibs/ElemStatLearn/), second edition. Springer.\n", "\n", "S. Marsland. (2009) [Machine Learning: An Algorithmic Perspective](Machine Learning: An Algorithmic Perspectivehttp://seat.massey.ac.nz/personal/s.r.marsland/MLBook.html). CRC Press.\n", "\n", "Data Robot Blog: [Gradient Boosted Regression Trees](http://www.datarobot.com/blog/gradient-boosted-regression-trees/)" ] } ], "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.8.2" }, "latex_envs": { "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 0 } }, "nbformat": 4, "nbformat_minor": 4 }