Introduction to boosting trees

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Boosted trees
        Machine Learning
      

Introduction

AdaBoost works with weak-classifiers to sequentially build a more accurate ensemble. A similar strategy can be used to build an ensemble of strong models, for example, involving tree-based models for classification and regression.

Prerequisites

To understand the boosting approaches to trees, we recommend familiarity with the concepts in

Introduction to machine learning: An introduction to basic concepts in machine learning such as classification, training instances, features, and feature types.
Introduction to optimization
Decision tree classifier
Tree-based regression

Follow the above links to first get acquainted with the corresponding concepts.

Problem setting

Tree boosting can be used for both classification and regression tasks.

Consider an instance $ \vx \in \real^\ndim $, a vector consisting of $ \ndim $ features, $\vx = [x_1, x_2, \ldots, x_\ndim] $.

In classification, the goal of the predictive model is to identify the class that generated a particular instance. We need to assign it to one of the $ M $ classes $ C_1, C_2, \ldots, C_M $ depending on the values of the $ N $ features .

In regression, the goal of the predictive model is to predict a continuous valued output for a given multivariate instance. We need to predict a real-valued output $ \hat{y} \in \real $ that is as close as possible to the true target $ y \in \real $. The hat $ \hat{ } $ denotes that $ \hat{y} $ is an estimate, to distinguish it from the truth.

For both supervised learning settings, the model is inferred over a collection of labeled observations provided as tuples $ (\vx_i,y_i) $ containing the instance vector $ \vx_i $ and the true target variable $ y_i $. This collection of labeled observations is known as the training set $ \labeledset = \set{(\vx_1,y_1), \ldots (\vx_\nlabeled,y_\nlabeled)} $.

A quick refresher on trees

Remember from our comprehensive article on decision trees and tree-based regression that trees partition the feature space into regions. The prediction in each region is a constant. Suppose for a region $ r $, the constant prediction is $ \gamma_r $.

This means, the predictive model of the tree can be summarized as

$$ T(\vx;\Theta) = \sum_{r=1}^R \gamma_r \indicator{\vx \in r} $$

where, $ \Theta $ is the collection of all parameters of the tree — the regions $ \set{1, \ldots, R} $ and the corresponding constants $ \gamma_r,~~~\forall r \in \set{1,\ldots,R} $.

Intuitively, this means, the prediction for an instance $ \vx $ is the constant $ \gamma_r $ assigned to the region $ r $ that the instance belongs to.

Tree learning involves inferring $ \Theta $ — the regions and their constants.

Finding the regional constants $ \gamma_r $ is easy. Typically, in the case of regression, $ \gamma_r $ is the average of target variables of all training examples that belong to the region $ r $. In the case of classification, it is the modal class — the class that has the most representative examples belonging in the region $ r $.
Finding the regions is the harder problem. This is typically handled greedily, with a top-down recursive partitioning strategy.

Thus, the parameters, $ \Theta $, are fit to minimize the Gini index (in classification) or mean squared error (in regression) on the training set consisting of $ \nlabeled $ labeled examples.

$$ \hat{\Theta} = \argmin_{\Theta} \sum_{\nlabeledsmall=1}^{\nlabeled} \loss\left(y_\nlabeledsmall, T(\vx_\nlabeledsmall;\Theta)\right) $$

Predictive model

A boosted tree $ f_M $ is an ensemble of $ M $ such trees. It's predictive model is a sum of the predictions from each of the constituent trees.

\begin{align} \hat{y} &= f_M(\vx) \\\\ &= \sum_{m=1}^M T(\vx;\Theta_m) \label{eqn:class-pred} \end{align}

Training boosted trees

Note that the predictive model of the boosted tree is an additive model of the constituents. This means, to arrive at the optimal parameters $ \Theta_m $ of the $ m $-th tree, we must incorporate the predictions from the previous $ m - 1$ trees — the model $ f_{m-1} $. This ensures that the parameters $ \Theta_m $ are optimized for the residuals of the existing $ m - 1 $ tree. In other words, new trees added to the ensemble are optimized to minimize the errors of the previous trees in the ensemble.

This leads to the optimization criteria

$$ \hat{\Theta}_m = \argmin_{\Theta} \sum_{\nlabeledsmall=1}^{\nlabeled} \loss\left(y_\nlabeledsmall, f_{m-1}(\vx_\nlabeledsmall) + T(\vx_\nlabeledsmall;\Theta)\right) $$

The regions for the $ m$-th tree can then be found greedily as before.

With the knowledge of such regions, the regional constants $ \gamma_{rm} $ for the $ r$-th region of the $ m$-th tree can be found by optimizing the following

$$ \gamma_{rm} = \argmin_{\gamma} \sum_{\vx_\nlabeledsmall \in r} \loss(y_\nlabeledsmall, f_{m-1}(\vx_\nlabeledsmall) + \gamma) $$

Note that the regional constants of the newly learnt $ m $-th tree are modified from their usual values since we need to fix the errors of previous $ m - 1 $ trees in the ensemble.

Boosting regression trees

The above optimization strategy to sequentially create an ensemble of trees is straightforward for regression trees.

Discovering regions for boosted trees is no different from the strategy adopted for single tree learning. The only difference being, instead of optimizing to predict the target variable directly, we instead optimize the regions to predict the residual as explained earlier. Thus, the regions of the $ m $-th tree are inferred to optimize the residual $ y_\nlabeledsmall - f_{m-1}(\vx_\nlabeledsmall) $.
The calculation of regional constants, $ \gamma_{rm} $, is also straightforward for regression trees. Once the regions have been discovered for the $ m $-th tree in the sequence, the $ \gamma_{rm} $ is the mean of the residuals $ y_\nlabeledsmall - f_{m-1}(\vx_\nlabeledsmall) $ for training examples in that region; $ \vx_\nlabeledsmall \in r $.

Boosting classification trees

In the case of classification trees, if we restrict the output of each tree to be classes $ \set{-1,1} $, then we effectively end up with an AdaBoost-like solution, where we are fitting the new tree to weighted examples

$$ \Theta_m = \argmin_{\Theta} \sum_{\nlabeledsmall=1}^{\nlabeled} w_{\nlabeledsmall}^{(m)} \indicator{y_\nlabeledsmall \ne T(\vx_\nlabeledsmall;\Theta)} $$

with the weights

$$ w_{\nlabeledsmall}^{(m)} = \exp \left[-y_\nlabeledsmall f_{m-1}(\vx_\nlabeledsmall) \right] $$

If each tree is not restricted to the output $ \set{-1,1} $, then the optimization still simplifies to a weighted exponential criteria as

$$ \Theta_m = \argmin_{\Theta} \sum_{\nlabeledsmall=1}^{\nlabeled} w_\nlabeledsmall^{(m)} \exp \left[ -y_\nlabeledsmall T(\vx_\nlabeledsmall; \Theta) \right] $$

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Subscribe for article updates

Stay up to date with new material for free.