XGBoost › Formula

The mathematical foundation of XGBoost is rooted in the general gradient boosting framework, but XGBoost introduces several innovations that make it both more powerful and more efficient. To understand how XGBoost works under the hood, let's break down its formulation step by step, carefully explaining the meaning and purpose of each component.

At each boosting iteration $t$, XGBoost seeks to minimize an objective function that balances two goals:

• Fitting the data well (minimizing prediction error)
• Controlling model complexity (to avoid overfitting)

The general form of the objective function at iteration $t$ is:

$$\mathcal{L}^{(t)} = \sum_{i=1}^{n} l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t)$$

• $n$ is the number of training examples.
• $l(\cdot, \cdot)$ is a differentiable loss function (e.g., squared error for regression, log-loss for classification).
• $y_i$ is the true label for instance $i$.
• $\hat{y}_i^{(t-1)}$ is the prediction for $i$ after $t-1$ trees (i.e., the current ensemble's output).
• $f_t(x_i)$ is the output of the new tree being added at iteration $t$.
• $\Omega(f_t)$ is a regularization term that penalizes the complexity of the new tree.

At each step, XGBoost adds a new tree $f_t$ to the ensemble, aiming to improve predictions while keeping the model as simple as possible.

A key innovation in XGBoost is the use of a second-order Taylor expansion to approximate the loss function. This allows XGBoost to use both the gradient (first derivative) and the curvature (second derivative, or Hessian) of the loss, leading to more accurate and stable optimization compared to traditional gradient boosting, which uses only the first derivative.

Note: The second-order Taylor expansion is a mathematical technique that approximates a function near a point using both its slope (first derivative) and curvature (second derivative). This provides a more accurate approximation than using only the slope, especially when the function has significant curvature. In XGBoost, this translates to better optimization steps and faster convergence.

For each data point $i$, we expand the loss function around the current prediction $\hat{y}_i^{(t-1)}$:

$$l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) \approx l\left(y_i, \hat{y}_i^{(t-1)}\right) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)$$

where:

• $g_i = \frac{\partial l(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}$ is the first-order gradient (how much the loss would change with a small change in prediction).
• $h_i = \frac{\partial^2 l(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2}$ is the second-order gradient (how the gradient itself changes; i.e., the curvature).

This is important because:

• The first-order term ($g_i$) tells us the direction to move to reduce the loss.
• The second-order term ($h_i$) tells us how confident we are in that direction (steepness/curvature).
• Using both allows for more precise and stable updates, especially for complex loss functions.

To understand why second-order information is valuable, consider how gradient and Hessian guide optimization differently:

The visualization demonstrates a key advantage of using second-order information: the Hessian allows XGBoost to adapt step sizes based on local curvature. In the contour plot, notice how the loss surface has different curvature in different directions (the elliptical contours). The first-order method (blue) uses a fixed step size and overshoots in the steep direction, while the second-order method (green) uses curvature information to take a more appropriate step, achieving a lower loss value. This curvature-aware optimization is why XGBoost converges faster and more reliably than traditional gradient boosting.

Plugging the Taylor expansion into the original objective, and noting that $l(y_i, \hat{y}_i^{(t-1)})$ is constant with respect to $f_t$, we get:

$$\mathcal{L}^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t)$$

• The sum over $g_i f_t(x_i)$ encourages the new tree to correct the errors of the current model.
• The sum over $h_i f_t^2(x_i)$ penalizes large updates, especially where the loss curve is steep (high curvature).

XGBoost's regularization term $\Omega(f_t)$ is more sophisticated than in standard boosting. It penalizes both the complexity of the tree structure and the magnitude of the leaf weights:

Note: Regularization in XGBoost serves multiple purposes: it prevents overfitting by controlling model complexity, encourages sparsity in leaf weights (L1), and provides smooth shrinkage (L2). The structural regularization ($\gamma$) specifically controls tree complexity by penalizing the number of leaves, encouraging simpler trees that generalize better.

$$\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 + \alpha \sum_{j=1}^{T} |w_j|$$

• $T$ is the number of leaves in the tree $f_t$.
• $w_j$ is the score (weight) assigned to leaf $j$.
• $\gamma$ penalizes having too many leaves (encourages simpler trees).
• $\lambda$ is the L2 regularization parameter (shrinks large leaf weights).
• $\alpha$ is the L1 regularization parameter (encourages sparsity in leaf weights).

This regularization helps prevent overfitting by discouraging overly complex trees and large leaf values.

Let's break down how the objective function is rewritten in terms of the leaves of a tree, step by step.

Partitioning the Data by LeavesLink Copied

When we build a decision tree, each data point $x_i$ ends up in exactly one leaf. Suppose the tree has $T$ leaves. For each leaf $j$ (where $j = 1, 2, ..., T$), define:

• $I_j = \{i \mid q(x_i) = j\}$: the set of indices of data points that fall into leaf $j$. Here, $q(x_i)$ is a function that tells us which leaf $x_i$ belongs to.
• $w_j$: the score or weight assigned to leaf $j$. Every data point in leaf $j$ gets the same output $w_j$ from the tree.

Expanding the Objective FunctionLink Copied

Let's expand in detail how the objective function is rewritten in terms of the leaves of the tree.

Recall the approximated objective function after the second-order Taylor expansion:

$$\mathcal{L}^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t)$$

where:

• $g_i$ is the first derivative (gradient) of the loss with respect to the prediction for $x_i$,
• $h_i$ is the second derivative (Hessian) of the loss with respect to the prediction for $x_i$,
• $f_t(x_i)$ is the output of the new tree for $x_i$,
• $\Omega(f_t)$ is the regularization term for the tree.

Grouping by LeavesLink Copied

A decision tree partitions the data into $T$ leaves. Each data point $x_i$ falls into exactly one leaf, say leaf $j$. Let:

• $I_j = \{i \mid q(x_i) = j\}$ be the set of indices of data points assigned to leaf $j$,
• $w_j$ be the score (weight) assigned to leaf $j$.

By the definition of a tree, for all $i \in I_j$, the output of the tree is the same:

• $f_t(x_i) = w_j$ for all $i \in I_j$.

This allows us to rewrite the sums over all data points as sums over leaves, grouping together all points in the same leaf.

Expanding the First-Order Term (Step-by-Step)Link Copied

Let's break down how to rewrite the first-order term by grouping data points according to the leaves they fall into:

1. Start with the original first-order term:

   $$\sum_{i=1}^{n} g_i f_t(x_i)$$

2. Group data points by their assigned leaf: Each data point $x_i$ is assigned to a leaf $j$, so we can rewrite the sum over all data points as a sum over leaves and, within each leaf, a sum over the data points in that leaf:

   $$= \sum_{j=1}^{T} \sum_{i \in I_j} g_i f_t(x_i)$$

3. Substitute the leaf weight for the tree output: For all $i$ in leaf $j$, $f_t(x_i) = w_j$, so we can replace $f_t(x_i)$ with $w_j$:

   $$= \sum_{j=1}^{T} \sum_{i \in I_j} g_i w_j$$

4. Factor out terms that do not depend on $i$: $w_j$ is constant for all $i$ in $I_j$, so we can factor it out of the inner sum:

   $$= \sum_{j=1}^{T} w_j \sum_{i \in I_j} g_i$$

5. Write the final grouped form: This shows that the first-order term for the whole tree is the sum, over all leaves, of the sum of gradients in each leaf times the leaf's weight:

   $$= \sum_{j=1}^{T} \left( \sum_{i \in I_j} g_i \right) w_j$$

This step-by-step grouping is important because it allows us to efficiently compute the contribution of each leaf to the objective function.

Expanding the Second-Order TermLink Copied

Let's break down how to rewrite the second-order term by grouping data points according to the leaves they fall into:

1. Start with the original second-order term:

   $$\sum_{i=1}^{n} \frac{1}{2} h_i f_t^2(x_i)$$

2. Group data points by their assigned leaf: Each data point $x_i$ is assigned to a leaf $j$, so we can rewrite the sum over all data points as a sum over leaves and, within each leaf, a sum over the data points in that leaf:

   $$= \sum_{j=1}^{T} \sum_{i \in I_j} \frac{1}{2} h_i f_t^2(x_i)$$

3. Substitute the leaf weight for the tree output: For all $i$ in leaf $j$, $f_t(x_i) = w_j$, so we can replace $f_t(x_i)$ with $w_j$:

   $$= \sum_{j=1}^{T} \sum_{i \in I_j} \frac{1}{2} h_i w_j^2$$

4. Factor out terms that do not depend on $i$: $w_j^2$ is constant for all $i$ in $I_j$, so we can factor it out of the inner sum:

   $$= \sum_{j=1}^{T} \frac{1}{2} w_j^2 \sum_{i \in I_j} h_i$$

5. Write the final grouped form: This shows that the second-order term for the whole tree is the sum, over all leaves, of the sum of Hessians in each leaf times the square of the leaf's weight (with a factor of $1/2$):

   $$= \sum_{j=1}^{T} \frac{1}{2} \left( \sum_{i \in I_j} h_i \right) w_j^2$$

This step-by-step grouping is important because it allows us to efficiently compute the contribution of each leaf to the objective function.

Putting It TogetherLink Copied

So, the original sum over all data points can be rewritten as a sum over leaves, where each leaf's contribution depends on the sum of gradients and Hessians of the data points it contains, and the leaf's weight:

$$\sum_{i=1}^{n} g_i f_t(x_i) + \sum_{i=1}^{n} \frac{1}{2} h_i f_t^2(x_i) = \sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} h_i \right) w_j^2 \right]$$

This grouping allows XGBoost to efficiently compute the optimal weights for each leaf and to evaluate the quality of different tree structures.

Adding RegularizationLink Copied

The regularization term for the tree is:

$$\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 + \alpha \sum_{j=1}^{T} |w_j|$$

• $\gamma T$ penalizes the number of leaves (to discourage overly complex trees).
• $\lambda$ and $\alpha$ penalize large or non-sparse leaf weights.

Note: This is basically the L1 and L2 regularization covered in the Ridge and LASSO regularization chapters, but applied to the leaf weights.

Putting It All TogetherLink Copied

Let's carefully combine the grouped sums from the objective and the regularization terms, step by step.

Recall from above that, after grouping by leaves, the second-order Taylor-approximated objective (before regularization) is:

$$\sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} h_i \right) w_j^2 \right]$$

Now, let's add the regularization term for the tree:

$$\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 + \alpha \sum_{j=1}^{T} |w_j|$$

So, the total objective at step $t$ is:

$$\begin{aligned} \mathcal{L}^{(t)} &= \text{(grouped objective)} + \text{(regularization)} \\ &= \sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} h_i \right) w_j^2 \right] \\ &\quad + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 + \alpha \sum_{j=1}^{T} |w_j| \end{aligned}$$

Let's write all terms involving $w_j$ together, grouping by leaf $j$:

$$\begin{aligned} \mathcal{L}^{(t)} &= \sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j \right] \\ &\quad + \sum_{j=1}^{T} \left[ \frac{1}{2} \left( \sum_{i \in I_j} h_i \right) w_j^2 \right] \\ &\quad + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 \\ &\quad + \alpha \sum_{j=1}^{T} |w_j| \\ &\quad + \gamma T \end{aligned}$$

Now, notice that the two quadratic terms in $w_j$ can be combined for each leaf $j$:

$$\frac{1}{2} \left( \sum_{i \in I_j} h_i \right) w_j^2 + \frac{1}{2} \lambda w_j^2 = \frac{1}{2} \left( \sum_{i \in I_j} h_i + \lambda \right) w_j^2$$

So, the objective simplifies to:

$$\mathcal{L}^{(t)} = \sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} h_i + \lambda \right) w_j^2 + \alpha |w_j| \right] + \gamma T$$

Or, written out for clarity:

$$\mathcal{L}^{(t)} = \sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} h_i + \lambda \right) w_j^2 + \alpha |w_j| \right] + \gamma T$$

This is the final grouped and regularized form of the objective for a single boosting step in XGBoost.

What does this mean?

• For each leaf $j$, we sum up all the gradients ($g_i$) and Hessians ($h_i$) of the data points that fall into that leaf.
• The objective for the whole tree is now just a sum over the leaves, where each leaf's contribution depends on its weight $w_j$, the total gradient and Hessian in that leaf, and the regularization terms.
• This form makes it possible to analytically solve for the best $w_j$ for each leaf, and to efficiently evaluate how good a particular tree structure is.

By grouping the data by leaves, we turn a sum over all data points into a sum over leaves, where each leaf's effect on the objective depends only on the data points it contains. This is the key step that allows XGBoost to efficiently optimize tree structures and leaf values.

To determine the best value for each leaf weight $w_j$, we take the derivative of the objective with respect to $w_j$ and set it to zero (for simplicity, let's ignore the L1 term $\alpha$ for now):

Note: The L1 regularization term ($\alpha |w_j|$) is non-differentiable at zero, which complicates the analytical solution. In practice, XGBoost uses soft thresholding techniques to handle L1 regularization, but for this derivation, we focus on the L2 case to demonstrate the core mathematical principle.

Start with the grouped objective for a single leaf $j$:

$$\mathcal{L}_j = G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2$$

where

• $G_j = \sum_{i \in I_j} g_i$ (sum of gradients in leaf $j$)
• $H_j = \sum_{i \in I_j} h_i$ (sum of Hessians in leaf $j$)

Take the derivative with respect to $w_j$:

$$\frac{\partial \mathcal{L}_j}{\partial w_j} = G_j + (H_j + \lambda) w_j$$

Set the derivative to zero to find the minimum:

$$G_j + (H_j + \lambda) w_j = 0$$

Solve for $w_j$:

$$\begin{aligned} G_j + (H_j + \lambda) w_j &= 0 \\ (H_j + \lambda) w_j &= -G_j \\ w_j^* &= -\frac{G_j}{H_j + \lambda} \end{aligned}$$

Substituting back the definitions:

$$w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}$$

• The optimal weight for each leaf is determined by the sum of gradients (how much the model is under- or over-predicting) and the sum of Hessians (how "confident" we are in those gradients), regularized by $\lambda$.
• This formula is used to assign the value to each leaf during tree construction.

To visualize how this optimization works, consider how the objective function for a single leaf varies with the leaf weight $w_j$:

The visualization reveals how XGBoost finds optimal leaf weights through a simple quadratic optimization. The left plot shows how different gradient and Hessian values shift the location of the minimum.negative gradients push the optimum to positive weights (and vice versa), while larger Hessians create steeper curves that concentrate the optimum. The right plot demonstrates regularization's effect: as $\lambda$ increases, the optimal weight is pulled toward zero, preventing overfitting by penalizing large leaf values. This analytical solution is one of XGBoost's key advantages.rather than iteratively searching for good weights, it can compute the exact optimum for each leaf given the tree structure.

When building the tree, XGBoost evaluates possible splits by computing the "gain" or "quality score" for a given tree structure. This is the improvement in the objective function if we use a particular split:

$$\tilde{\mathcal{L}}^{(t)} = -\frac{1}{2} \sum_{j=1}^{T} \frac{\left( \sum_{i \in I_j} g_i \right)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T$$

• The numerator $(\sum_{i \in I_j} g_i)^2$ rewards splits that group together data points with similar gradients (i.e., similar errors).
• The denominator $(\sum_{i \in I_j} h_i + \lambda)$ penalizes splits where the model is less confident (low Hessian sum) or where regularization is strong.
• The $\gamma T$ term penalizes having too many leaves.

How is this used?

• During tree construction, XGBoost greedily chooses splits that maximize the reduction in this score (i.e., the largest gain).
• This process continues recursively, subject to constraints like maximum depth or minimum gain.

To understand how XGBoost evaluates and selects splits, consider a concrete example with multiple candidate splits:

The second-order approximation in XGBoost provides several important mathematical advantages. By incorporating the Hessian matrix (second derivatives), the algorithm can make more informed decisions about the direction and magnitude of updates, leading to faster convergence and better final performance. This is particularly beneficial when the loss function has significant curvature, as the second-order information captures this curvature more accurately than first-order methods alone.

Note: The mathematical presentation here focuses on the key concepts and simplified formulations. In practice, XGBoost's implementation includes additional optimizations such as approximate algorithms for split finding, handling of missing values, and various computational optimizations that are beyond the scope of this mathematical overview.

The regularization terms in XGBoost serve multiple purposes. The L2 regularization ($\lambda$) helps prevent overfitting by penalizing large leaf weights, while the L1 regularization ($\alpha$) can lead to sparsity in the leaf weights, effectively performing feature selection. The structural regularization ($\gamma$) controls the complexity of the tree by penalizing the number of leaves, encouraging simpler trees that are less likely to overfit.