Boosted Trees › Formula

The mathematical foundation of boosted trees involves understanding how the algorithm sequentially builds an ensemble by minimizing a loss function through gradient descent. Let's break this down step by step, starting with the basic structure and progressing to the complete algorithm formulation.

The final boosted tree model is an ensemble of $M$ decision trees, where each tree is trained sequentially to correct the errors of the previous trees. The prediction for a given input $\mathbf{x}$ is:

$$\hat{y} = \sum_{m=1}^{M} \gamma_m h_m(\mathbf{x})$$

where:

• $\hat{y}$ is the final prediction
• $M$ is the total number of trees in the ensemble
• $\gamma_m$ is the learning rate (step size) for tree $m$
• $h_m(\mathbf{x})$ is the prediction from the $m$-th tree for input $\mathbf{x}$

Boosted trees minimize a loss function $L(y, \hat{y})$ that measures how well the model's predictions match the true values. Common loss functions include:

For Regression (Mean Squared Error):

We've already covered these loss functions in the regression chapters, so we are keeping the explanation brief.

The most common loss function for regression tasks in gradient boosting is the Mean Squared Error (MSE). It measures the average squared difference between the actual target value $y$ and the predicted value $\hat{y}$:

$$L(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$$

The factor of $\frac{1}{2}$ is included for mathematical convenience because when you take the derivative of $\frac{1}{2}(y - \hat{y})^2$ with respect to $\hat{y}$, the 2 from the exponent cancels with the $\frac{1}{2}$, leaving just $(\hat{y} - y)$; this makes the gradient expression simpler and avoids carrying an extra constant through the calculations.

During training, the algorithm tries to minimize this loss by adjusting the model so that predictions $\hat{y}$ get as close as possible to the true values $y$. The gradient of this loss with respect to $\hat{y}$ is simply $(\hat{y} - y)$, which means each new tree in the ensemble is trained to predict the residuals (errors) of the current model.

For Classification (Logistic Loss):

For binary classification problems, gradient boosting typically uses the logistic loss (also called log-loss or binary cross-entropy). This loss is specifically designed for situations where the target $y$ is 0 or 1, and the model's output $\hat{y}$ is a real number (not a probability, but a "logit" or "log-odds" score).

The logistic loss for a single data point is:

$$L(y, \hat{y}) = y \log(1 + e^{-\hat{y}}) + (1-y) \log(1 + e^{\hat{y}})$$

In gradient boosting, the logistic loss is central to the entire training process. At each boosting iteration (i.e., for each new tree that is added to the ensemble), the algorithm evaluates the logistic loss for every training example using the current prediction $\hat{y}$ (which is the sum of the outputs from all previous trees).

The gradients of this loss with respect to $\hat{y}$ are then computed for each example, and the next tree is trained to predict these gradients (also called "pseudo-residuals"). This means that the logistic loss is used repeatedly, at every boosting step and for every data point, to guide the model's updates and help it focus on the examples that are currently hardest to classify.

Let's look at how this loss function connects to log-odds and probabilities, step by step.

1. Model Output ($\hat{y}$): In gradient boosting for classification, the model does not directly output a probability. Instead, it outputs a real number $\hat{y}$ for each example. This number is called the logit or log-odds.

2. From Log-Odds to Probability: To get a probability $p$ from $\hat{y}$, we use the sigmoid (logistic) function:

   $$p = \frac{1}{1 + e^{-\hat{y}}}$$

   This maps any real value to a number between 0 and 1.

3. From Probability to Log-Odds: If you start with a probability $p$, you can get back to the log-odds (the value the model outputs) by inverting the sigmoid:

   $$\hat{y} = \log\left(\frac{p}{1-p}\right)$$

   So, the model is really building up an estimate of the log-odds for each example.

1. Why does the loss use $\hat{y}$ and not $p$?
   You might notice that the loss function is expressed in terms of $\hat{y}$ (the log-odds), while the sigmoid function uses $p$ (the probability). This is intentional: the model predicts and updates values in the log-odds space, not directly in probability space.

   This is because the logistic loss is derived from the negative log-likelihood of the Bernoulli distribution. Let's walk through the full derivation:

2. Start with the Bernoulli likelihood: First, we write down the likelihood function for a single data point, which gives the probability of observing $y \in \{0, 1\}$ given the predicted probability $p$.

   $$P(y|p) = p^y (1-p)^{1-y}$$

3. Take the negative log-likelihood: Next, we take the negative logarithm of the likelihood to obtain the loss function that we want to minimize.

   $$-\log P(y|p) = -\log\left(p^y (1-p)^{1-y}\right) = -y \log p - (1-y) \log (1-p)$$

4. Express $p$ in terms of the model output $\hat{y}$: Then, we rewrite the probability $p$ in terms of the model's output $\hat{y}$ (the log-odds), since this is what the model predicts.

   $$p = \frac{1}{1 + e^{-\hat{y}}}$$

   and

   $$1 - p = \frac{e^{-\hat{y}}}{1 + e^{-\hat{y}}}$$

5. Substitute $p$ and $1-p$ into the loss: Now, we substitute the expressions for $p$ and $1-p$ in terms of $\hat{y}$ back into the loss function.

   $$-y \log p - (1-y) \log (1-p) = -y \log\left(\frac{1}{1 + e^{-\hat{y}}}\right) - (1-y) \log\left(\frac{e^{-\hat{y}}}{1 + e^{-\hat{y}}}\right)$$

6. Simplify the expression: Finally, we simplify the resulting expression to obtain the standard form of the logistic loss in terms of $\hat{y}$.

   $$= -y \left[ -\log(1 + e^{-\hat{y}}) \right] - (1-y) \left[ -\hat{y} - \log(1 + e^{-\hat{y}}) \right]$$ $$= y \log(1 + e^{-\hat{y}}) + (1-y) \left[ \hat{y} + \log(1 + e^{-\hat{y}}) \right]$$ $$= y \log(1 + e^{-\hat{y}}) + (1-y)\hat{y} + (1-y)\log(1 + e^{-\hat{y}})$$ $$= \log(1 + e^{-\hat{y}}) + (1-y)\hat{y}$$

   Alternatively, you may see the loss written as:

   $$L(y, \hat{y}) = y \log(1 + e^{-\hat{y}}) + (1-y) \log(1 + e^{\hat{y}})$$

   which is algebraically equivalent.

This full derivation shows how the logistic loss arises naturally from the probabilistic model, and why it is expressed in terms of $\hat{y}$. This formulation is preferred because it simplifies the optimization process and makes the gradients easy to compute, which is essential for efficient training.

To recap, the logistic loss is derived from the negative log-likelihood of the Bernoulli distribution, and is expressed in terms of $\hat{y}$ (the log-odds) because the model predicts and updates that value at each boosting step.

Gradients and Pseudo-ResidualsLink Copied

The boosting algorithm computes the gradient of the loss with respect to $\hat{y}$ (where $\hat{y}$ is the log-odds score for the model's prediction, or the raw score output by the model for a given input $\mathbf{x}$) for each training example. For logistic loss, this gradient is:

$$\frac{\partial L}{\partial \hat{y}} = - (y - p)$$

This means that the "pseudo-residuals" (the targets for the next tree) are simply the difference between the true label and the current predicted probability.

• If the model predicts $p$ close to $y$ (e.g., $p=0.9$ and $y=1$), the gradient is small, so the next tree makes only a small correction.
• If the model predicts $p$ far from $y$ (e.g., $p=0.1$ and $y=1$), the gradient is large, so the next tree tries to make a bigger correction.

This process is repeated, with each new tree focusing on the mistakes of the current model, gradually improving the fit.

Log-loss has several properties that make it well-suited for classification tasks in gradient boosting. First, it is a strictly proper scoring rule, which means it encourages the model to produce well-calibrated probability estimates. It is also differentiable, so gradient-based optimization methods can be applied directly. Another useful property is that log-loss imposes a strong penalty on predictions that are both confident and incorrect, discouraging the model from making overconfident mistakes.

In gradient boosting for classification, the logistic loss provides a principled way to measure prediction error and guide the model's updates. At each step, the model fits a new tree to the difference between the true label and the current predicted probability, steadily reducing the overall loss and improving classification accuracy.

The key insight of gradient boosting is to use the gradient of the loss function to guide the training of each new tree. Here's how it works:

Step 1: Initialize the model
Start with a simple model, typically the mean of the target variable for regression or the log-odds for classification:

$$F_0(\mathbf{x}) = \arg\min_{\gamma} \sum_{i=1}^{n} L(y_i, \gamma)$$

• Here, $F_0(\mathbf{x})$ is the initial prediction for all inputs $\mathbf{x}$.
• $L(y_i, \gamma)$ is the loss function, measuring the error between the true value $y_i$ and a constant prediction $\gamma$.
• $n$ is the number of training examples.
• $\arg\min_{\gamma}$ means we choose the value of $\gamma$ that minimizes the total loss over all training examples.

For regression with mean squared error (MSE) loss, this simplifies to:

$$F_0(\mathbf{x}) = \frac{1}{n} \sum_{i=1}^{n} y_i$$

That is, the initial prediction is just the average of the target values.

Step 2: For each iteration $m = 1, 2, \ldots, M$:

• $m$ is the index of the current boosting iteration (tree), and $M$ is the total number of boosting rounds (trees).

2a. Calculate the negative gradient (pseudo-residuals)
For each training example $i$, calculate the negative gradient of the loss function with respect to the current model's prediction:

$$r_{im} = -\frac{\partial L(y_i, F_{m-1}(\mathbf{x}_i))}{\partial F_{m-1}(\mathbf{x}_i)}$$

• $r_{im}$ is the pseudo-residual for example $i$ at iteration $m$.
• $F_{m-1}(\mathbf{x}_i)$ is the prediction for example $i$ from the previous iteration.
• The negative gradient tells us how to adjust our prediction to reduce the loss.

This gives us the "pseudo-residuals" that tell us in which direction and by how much we need to adjust our predictions.

2b. Train a new tree on the pseudo-residuals
Train a decision tree $h_m(\mathbf{x})$ to predict the pseudo-residuals:

$$h_m = \arg\min_{h} \sum_{i=1}^{n} (r_{im} - h(\mathbf{x}_i))^2$$

• $h_m(\mathbf{x})$ is the new tree fitted at iteration $m$.
• The tree is trained to predict $r_{im}$ from the input features $\mathbf{x}_i$.
• The sum of squared differences means we fit the tree to the pseudo-residuals using least squares.

2c. Find the optimal step size
For each leaf $j$ in the new tree, find the optimal step size that minimizes the loss:

$$\gamma_{jm} = \arg\min_{\gamma} \sum_{\mathbf{x}_i \in R_{jm}} L(y_i, F_{m-1}(\mathbf{x}_i) + \gamma)$$

• $\gamma_{jm}$ is the optimal value to add to the prediction for all examples in leaf $j$ of tree $m$.
• $R_{jm}$ is the set of training examples that fall into leaf $j$ of tree $m$.
• This step ensures that each leaf's output is chosen to minimize the loss for the examples it contains.

2d. Update the model
Add the new tree to the ensemble:

$$F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \gamma_m h_m(\mathbf{x})$$

• $F_m(\mathbf{x})$ is the updated prediction after adding the $m$-th tree.
• $\gamma_m$ is the step size (sometimes called the learning rate or shrinkage parameter) for this iteration. In some implementations, each leaf has its own $\gamma_{jm}$, and the update is performed leaf-wise.
• $h_m(\mathbf{x})$ is the prediction of the new tree.

Boosted trees possess several key mathematical properties that help explain their effectiveness. One of the most important is the connection to gradient descent optimization. The algorithm can be viewed as performing gradient descent in function space, where each tree represents a step in the direction of steepest descent of the loss function.

The bias-variance decomposition also applies to boosted trees, but in a different way than Random Forest. Early in the training process, the model has high bias (underfitting) but low variance. As more trees are added, the bias decreases but variance increases. The optimal number of trees balances this trade-off to minimize the total error.

Another important property is the concept of shrinkage, controlled by the learning rate $\gamma$. A smaller learning rate means smaller steps in the optimization process, which can lead to better generalization but requires more trees to achieve the same level of performance. This is often expressed as:

$$\hat{y} = \sum_{m=1}^{M} \nu h_m(\mathbf{x})$$

where $\nu$ is the shrinkage parameter (typically between 0.01 and 0.1) that controls the learning rate.