notebooks/ensemble_hist_gradient_boosting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Speeding-up gradient-boosting\n",
    "In this notebook, we present a modified version of gradient boosting which\n",
    "uses a reduced number of splits when building the different trees. This\n",
    "algorithm is called \"histogram gradient boosting\" in scikit-learn.\n",
    "\n",
    "We previously mentioned that random-forest is an efficient algorithm since\n",
    "each tree of the ensemble can be fitted at the same time independently.\n",
    "Therefore, the algorithm scales efficiently with both the number of cores and\n",
    "the number of samples.\n",
    "\n",
    "In gradient-boosting, the algorithm is a sequential algorithm. It requires\n",
    "the `N-1` trees to have been fit to be able to fit the tree at stage `N`.\n",
    "Therefore, the algorithm is quite computationally expensive. The most\n",
    "expensive part in this algorithm is the search for the best split in the\n",
    "tree which is a brute-force approach: all possible split are evaluated and\n",
    "the best one is picked. We explained this process in the notebook \"tree in\n",
    "depth\", which you can refer to.\n",
    "\n",
    "To accelerate the gradient-boosting algorithm, one could reduce the number of\n",
    "splits to be evaluated. As a consequence, the generalization performance of such\n",
    "a tree would be reduced. However, since we are combining several trees in a\n",
    "gradient-boosting, we can add more estimators to overcome this issue.\n",
    "\n",
    "We will make a naive implementation of such algorithm using building blocks\n",
    "from scikit-learn. First, we will load the California housing dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import fetch_california_housing\n",
    "\n",
    "data, target = fetch_california_housing(return_X_y=True, as_frame=True)\n",
    "target *= 100  # rescale the target in k$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"admonition note alert alert-info\">\n",
    "<p class=\"first admonition-title\" style=\"font-weight: bold;\">Note</p>\n",
    "<p class=\"last\">If you want a deeper overview regarding this dataset, you can refer to the\n",
    "Appendix - Datasets description section at the end of this MOOC.</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will make a quick benchmark of the original gradient boosting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import cross_validate\n",
    "from sklearn.ensemble import GradientBoostingRegressor\n",
    "\n",
    "gradient_boosting = GradientBoostingRegressor(n_estimators=200)\n",
    "cv_results_gbdt = cross_validate(\n",
    "    gradient_boosting, data, target, scoring=\"neg_mean_absolute_error\",\n",
    "    n_jobs=2\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Gradient Boosting Decision Tree\")\n",
    "print(f\"Mean absolute error via cross-validation: \"\n",
    "      f\"{-cv_results_gbdt['test_score'].mean():.3f} +/- \"\n",
    "      f\"{cv_results_gbdt['test_score'].std():.3f} k$\")\n",
    "print(f\"Average fit time: \"\n",
    "      f\"{cv_results_gbdt['fit_time'].mean():.3f} seconds\")\n",
    "print(f\"Average score time: \"\n",
    "      f\"{cv_results_gbdt['score_time'].mean():.3f} seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We recall that a way of accelerating the gradient boosting is to reduce the\n",
    "number of split considered within the tree building. One way is to bin the\n",
    "data before to give them into the gradient boosting. A transformer called\n",
    "`KBinsDiscretizer` is doing such transformation. Thus, we can pipeline\n",
    "this preprocessing with the gradient boosting.\n",
    "\n",
    "We can first demonstrate the transformation done by the `KBinsDiscretizer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.preprocessing import KBinsDiscretizer\n",
    "\n",
    "discretizer = KBinsDiscretizer(\n",
    "    n_bins=256, encode=\"ordinal\", strategy=\"quantile\")\n",
    "data_trans = discretizer.fit_transform(data)\n",
    "data_trans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"admonition note alert alert-info\">\n",
    "<p class=\"first admonition-title\" style=\"font-weight: bold;\">Note</p>\n",
    "<p class=\"last\">The code cell above will generate a couple of warnings. Indeed, for some of\n",
    "the features, we requested too much bins in regard of the data dispersion\n",
    "for those features. The smallest bins will be removed.</p>\n",
    "</div>\n",
    "We see that the discretizer transforms the original data into integral\n",
    "values (even though they are encoded using a floating-point representation).\n",
    "Each value represents the bin index when the distribution by quantile is\n",
    "performed. We can check the number of bins per feature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[len(np.unique(col)) for col in data_trans.T]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After this transformation, we see that we have at most 256 unique values per\n",
    "features. Now, we will use this transformer to discretize data before\n",
    "training the gradient boosting regressor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.pipeline import make_pipeline\n",
    "\n",
    "gradient_boosting = make_pipeline(\n",
    "    discretizer, GradientBoostingRegressor(n_estimators=200))\n",
    "cv_results_gbdt = cross_validate(\n",
    "    gradient_boosting, data, target, scoring=\"neg_mean_absolute_error\",\n",
    "    n_jobs=2,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Gradient Boosting Decision Tree with KBinsDiscretizer\")\n",
    "print(f\"Mean absolute error via cross-validation: \"\n",
    "      f\"{-cv_results_gbdt['test_score'].mean():.3f} +/- \"\n",
    "      f\"{cv_results_gbdt['test_score'].std():.3f} k$\")\n",
    "print(f\"Average fit time: \"\n",
    "      f\"{cv_results_gbdt['fit_time'].mean():.3f} seconds\")\n",
    "print(f\"Average score time: \"\n",
    "      f\"{cv_results_gbdt['score_time'].mean():.3f} seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we see that the fit time has been reduced but that the\n",
    "generalization performance of the model is identical. Scikit-learn provides\n",
    "specific classes which are even more optimized for large dataset, called\n",
    "`HistGradientBoostingClassifier` and `HistGradientBoostingRegressor`. Each\n",
    "feature in the dataset `data` is first binned by computing histograms, which\n",
    "are later used to evaluate the potential splits. The number of splits to\n",
    "evaluate is then much smaller. This algorithm becomes much more efficient\n",
    "than gradient boosting when the dataset has over 10,000 samples.\n",
    "\n",
    "Below we will give an example for a large dataset and we will compare\n",
    "computation times with the experiment of the previous section."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.ensemble import HistGradientBoostingRegressor\n",
    "\n",
    "histogram_gradient_boosting = HistGradientBoostingRegressor(\n",
    "    max_iter=200, random_state=0)\n",
    "cv_results_hgbdt = cross_validate(\n",
    "    histogram_gradient_boosting, data, target,\n",
    "    scoring=\"neg_mean_absolute_error\", n_jobs=2,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Histogram Gradient Boosting Decision Tree\")\n",
    "print(f\"Mean absolute error via cross-validation: \"\n",
    "      f\"{-cv_results_hgbdt['test_score'].mean():.3f} +/- \"\n",
    "      f\"{cv_results_hgbdt['test_score'].std():.3f} k$\")\n",
    "print(f\"Average fit time: \"\n",
    "      f\"{cv_results_hgbdt['fit_time'].mean():.3f} seconds\")\n",
    "print(f\"Average score time: \"\n",
    "      f\"{cv_results_hgbdt['score_time'].mean():.3f} seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The histogram gradient-boosting is the best algorithm in terms of score.\n",
    "It will also scale when the number of samples increases, while the normal\n",
    "gradient-boosting will not."
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "main_language": "python"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}