Histogram-based gradient boosting

As explained in Ensemble Methods for Machine Learning

Histogram-based gradient boosting is a gradient-boosting technique that discretizes feature values into bins to accelerate split finding and reduce memory use.

Gradient boosting can be effective but slow on large data sets because every regression tree must examine many possible split points. Histogram-based gradient boosting accelerates this step by replacing individual feature values with a smaller set of bins. section 5.2.3 section 5.2.4

The split-finding process works as follows:

• Collect feature values and assign them to a fixed number of ordered buckets. section 5.2.4
• Evaluate candidate tree splits only between successive buckets instead of between every pair of successive data points. section 5.2.4
• Use the best bucket boundary according to the tree’s split criterion, then continue gradient boosting with the resulting tree. section 5.2.4 section 5.0

Fifty points versus five bins

For 50 ordered data points, standard tree learning evaluates 49 possible splits. Binning those values into five buckets leaves only four bucket boundaries to evaluate, substantially reducing split-search work. On the breast cancer data set, HistGradientBoostingClassifier achieved a 4.2% test error, compared with 4.9% for GradientBoostingClassifier in the corresponding example. section 5.2.4 section 5.2.3

Figure 5.17 Left: A simple 1D regression problem with 50 data points. Center: Standard tree learning evaluates every possible split, which is illustrated by a line between each pair of data points. The best split is the one with the lowest split criterion (here, squared loss). Right: Histogram-based binning first puts the data into five buckets, and then evaluates the splits between each pair of data buckets. Again, the best split is the one with the lowest split criterion (also squared loss).

Use the figure to compare every-point split search with five-bucket histogram splitting and their squared-loss criteria. section 5.2.4

How Ensemble Methods for Machine Learning covers it

How deep it goes

Explains binning and candidate reduction with a 50-point example, but defers detailed implementation internals.

Examples

Uses a 50-point one-dimensional regression illustration and breast cancer classification with scikit-learn estimators.

What it assumes

Assumes gradient boosting and tree-learning basics while reinforcing residual-based sequential ensembles and loss-driven learning.

What you can do after

Apply it via scikit-learn’s HistGradientBoostingClassifier to train faster gradient-boosted classifiers.

How it connects

Connects gradient boosting to regression trees, split criteria, scikit-learn, and LightGBM.

liveBookmanning.com

Read Ensemble Methods for Machine Learning on liveBook Get the book at manning.com

Related concepts

• HistGradientBoostingClassifierimplemented by · HistGradientBoostingClassifier is a scikit-learn classifier that uses histogram-based gradient-boosted decision trees.
• gradient boostingkind of · Gradient boosting is an ensemble-learning technique that sequentially adds predictive models, typically weak learners, to reduce a loss by fitting its gradient.
• boostingkind of · Boosting is an ensemble-learning technique that builds predictive models sequentially and combines them, with later models improving on weaknesses of earlier ones.
• LightGBMimplemented by · LightGBM is an open-source gradient-boosting framework for efficiently training tree-based machine-learning models.
• XGBoostincludes · XGBoost is an open-source software library for efficient gradient-boosted decision-tree algorithms used in supervised machine learning.

This explainer was generated by Manning's knowledge graph from the text of Ensemble Methods for Machine Learning. The section links point to the parts of the book it draws on.