Boosting In Ensemble Models

Roughly, a statistical learning algorithm is referred to as a weak learner if it does slightly better than random guessing and is called a strong learner if it can be made arbitrarikly close to the true relationship (given enough data).

Making a weak learner is much easier than producing a strong learner in general, however, it has been shown that if a problem is weak learnable (meaning that a weak learner exists) then it is strong learnable (meaning that a strong learner exists).

Boosting is a technique for taking a bunch of weak learners and creating a strong learner.

This is short for adaptive boosting. It’s an algorithm for building a strong learner with an iterative sequence of weak learners. While the ideas can be applied more generally we will address the case of binary classification. Let \(\mathcal D = \{(x_i, y_i)\}\) be the training data with \(N\) samples and with \(x_i \in \mathbb R^p\) and \(y_i \in \{-1, 1\}\). Let \(X = \{x_i\}\). Suppose we have a parameterized collection of classifiers \(C_\theta:\mathbb R^p\to \{-1.1\}\). A common choice in AdaBoost is for \(C_{j,t,\pm}\) to be a decision stump on feature \(j\) with threshold \(t\) (i.e. classify as \(1\) if \(\pm x_j > t\) and \(-1\) otherwise).

Goal is to build a function \(f:\mathbb R^p \to \mathbb R\) where \(f(x) \gg 0\) represents great confidence that \(y = 1\) and \(f(x) \ll 0\) represents great confidence that \(y = -1\) (we quantify this with a loss function soon). We will build this function as a linear combination of weak classifiers:

\begin{align*} f = \sum^{k}_{j=1} \beta_jC_j. \end{align*}

Our goal is to minimize the exponential loss function

\begin{align*} L(f,y) = \sum_{i=1}^N \exp(=y_if(x_i)). \end{align*}

We sum over all training data. Some notes about this loss function:

1. If \(f\) and \(y\) agree in sign, then \(\exp(-y_if(x_i))\) is really small. This means we want \(|f(x_i)|\) to be as large as possible while \(f(x_i)\) agrees in sign with \(y_i\). This function therefore rewards having \(f\) big with proper sign, and heavily penalizes having \(f\) big with incorrect sign.
2. For a given \(x\), assume that \((Y|x)\) is a Bernoulli random variable with probability \(p\) of \(Y=1\) and \((1-p)\) of \(Y = -1\). Then the value of \(f(x)\) which minimizes the expected value of \(\exp(-Yf(x))\) is \(\frac12 \log\left(\frac{p}{1-p}\right)\). So the population minimizer of \(f(x)\) is half the log-odds of \((Y|x)\). That is, we take a bunch of non-probabilistic classifiers and are trying to build a probabilistic classifier.

We build this greedily.

1. Select \(\beta_1\) and \(C_1\) to minimize \(L(C_1,y)\). Set \(f_1 = C_1\).
2. At stage \(j > 1\) select \(\beta_j\) and \(C_j\) to minimize \(L(f_j, y)\) where \(f_j = f_{j-1} + \beta_j C_j\).

Plugging stuff in demonstrates that

\begin{align*} L(f_j, y) = \sum^N_{i=1} w^j_i \exp(-\beta_jy_iC_j(x_i)) \end{align*}

where \(w^j_i = \exp(-y_i f_{j-1}(x_i))\) can be thought of as weighting on the samples at stage \(j\).