XGBoost Objective Function & Missing Values

1. Model and Additive Training

Let ŷ_i be the prediction for instance i. The model is an ensemble of K trees:

ŷi = Σk=1K fk(xi)

where f_k is the k-th tree. Trees are added sequentially. At iteration t, we add a new tree f_t to improve upon the predictions from the previous t-1 trees:

ŷi(t) = ŷi(t-1) + ft(xi)

where ŷ_i^(t-1) is the prediction from the first t-1 trees.

2. Objective Function

The objective function at step t, Obj^(t), which we want to minimize to find the best f_t, consists of two parts: a loss function and a regularization term.

Obj(t) = Σi=1n l(yi, ŷi(t)) + Σk=1t Ω(fk)

where:

• l(y_i, ŷ_i^(t)) is a differentiable convex loss function that measures the difference between the true label y_i and the prediction ŷ_i^(t). (e.g., squared error for regression, logistic loss for binary classification).
• n is the number of training instances.
• Ω(f_k) is the regularization term for tree f_k, which penalizes complexity. For XGBoost, this is often:

  Ω(f) = γT + (1/2)λ Σj=1T wj2

  where T is the number of leaves in the tree, w_j is the score (output value) of the j-th leaf, and γ and λ are regularization parameters.

Substituting ŷ_i^(t) = ŷ_i^(t-1) + f_t(x_i) into the objective:

Obj(t) = Σi=1n l(yi, ŷi(t-1) + ft(xi)) + Ω(ft) + constant

(The regularization terms for trees 1 to t-1 are constant at step t and can be ignored for optimization).

3. Second-Order Taylor Approximation

To optimize this, XGBoost uses a second-order Taylor expansion of the loss function l(y_i, ŷ_i^(t-1) + f_t(x_i)) around the point ŷ_i^(t-1). Recall Taylor expansion: F(a+x) ≈ F(a) + F'(a)x + (1/2)F''(a)x².

Here, a = ŷ_i^(t-1) and x = f_t(x_i). Let g_i be the first-order derivative (gradient) and h_i be the second-order derivative (Hessian) of the loss function l with respect to its second argument (the prediction), evaluated at ŷ_i^(t-1):

gi = ∂l(yi, ŷi(t-1)) / ∂ŷi(t-1)
hi = ∂2l(yi, ŷi(t-1)) / (∂ŷi(t-1))2

The Taylor expansion of the loss for instance i is approximately:

l(yi, ŷi(t-1) + ft(xi)) ≈ l(yi, ŷi(t-1)) + gift(xi) + (1/2)hift(xi)2

Substituting this back into the objective function (and noting that l(y_i, ŷ_i^(t-1)) is constant at step t):

Obj(t) ≈ Σi=1n [gift(xi) + (1/2)hift(xi)2] + Ω(ft) + constant

We want to find the tree structure f_t and its leaf scores that minimize this approximated objective.

4. Deriving Optimal Leaf Weights and Structure Score

Let a tree f_t be defined by its structure (which assigns each instance x_i to a leaf) and the scores w_j for each leaf j. Let I_j = {i | q(x_i)=j} be the set of indices of data points assigned to leaf j. So, for any x_i in leaf j, f_t(x_i) = w_j.

Substitute f_t(x_i) = w_q(xi) and the regularization term Ω(f_t) = γT + (1/2)λ Σ_j=1^T w_j² into the approximated objective. We can rewrite the sum over instances as a sum over leaves:

Obj(t) ≈ Σj=1T [ (Σi∈Ij gi)wj + (1/2)(Σi∈Ij hi)wj2 ] + γT + (1/2)λ Σj=1T wj2

Rearranging terms related to w_j:

Obj(t) ≈ Σj=1T [ (Σi∈Ij gi)wj + (1/2)(Σi∈Ij hi + λ)wj2 ] + γT

Let G_j = Σ_i∈Ij g_i (sum of gradients in leaf j) and H_j = Σ_i∈Ij h_i (sum of Hessians in leaf j).

Obj(t) ≈ Σj=1T [ Gjwj + (1/2)(Hj + λ)wj2 ] + γT

For a fixed tree structure (fixed T and I_j), this is a quadratic function of w_j for each leaf. To find the optimal w_j^* that minimizes this, we take the derivative with respect to w_j and set it to 0:

∂Obj(t) / ∂wj = Gj + (Hj + λ)wj = 0
wj* = -Gj / (Hj + λ)

This is the optimal score for leaf j.

Now, substitute w_j^* back into the objective function to get the minimum objective value for a given tree structure:

Obj(t)opt = Σj=1T [ Gj(-Gj / (Hj + λ)) + (1/2)(Hj + λ)(-Gj / (Hj + λ))2 ] + γT
            = Σj=1T [ -Gj2 / (Hj + λ) + (1/2)Gj2 / (Hj + λ) ] + γT
            = -(1/2) Σj=1T [Gj2 / (Hj + λ)] + γT

This Obj^(t)_opt is often called the "structure score" or "quality score" of the tree. XGBoost tries to find tree structures (splits) that maximize the reduction in this score, or equivalently, maximize:

(1/2) Σj=1T [Gj2 / (Hj + λ)] - γT

Why Second-Order is More Efficient/Effective

Traditional Gradient Boosting often uses only first-order gradients (g_i) and fits trees to the negative gradients (residuals in squared error case). XGBoost's use of second-order derivatives (h_i, Hessians) offers advantages:

1. More Information about Loss Curvature: The Hessian h_i provides information about the curvature of the loss function. This allows XGBoost to make more informed steps. If the loss function is steep (large h_i), a smaller step (smaller w_j) might be appropriate, and vice-versa. The (H_j + λ) term in the denominator of w_j^* naturally handles this.
2. Faster Convergence: Using second-order information is akin to a Newton-Raphson step (for finding the minimum of a quadratic approximation), which can lead to faster convergence towards the minimum of the true objective function compared to first-order gradient descent.
3. Principled Regularization Handling: The λ regularization parameter is naturally incorporated into the optimal leaf weight calculation and the structure score.
4. Custom Loss Functions: The framework only requires the loss function to be twice differentiable. This makes it easy to use custom loss functions as long as you can provide their first and second derivatives (g_i and h_i). Traditional GBT often needs specific modifications for different loss functions.

While computing Hessians adds some computational cost per iteration, the benefits in terms of convergence speed and accuracy often outweigh this, especially for complex loss functions.

XGBoost's Handling of Missing Values

XGBoost has a built-in, quite sophisticated way of handling missing values, which differs significantly from traditional pre-imputation methods.

Traditional Imputation Methods:

• These methods are applied as a preprocessing step before training the model.
• Common techniques include:
  • Mean/median/mode imputation.
  • Regression imputation (predicting missing values using other features).
  • K-Nearest Neighbors (KNN) imputation.
  • Creating a separate category for "missing" or using an indicator variable.
• Drawbacks:
  • Can introduce bias if the imputation is not accurate.
  • May not capture the true underlying reason for missingness (e.g., if missingness itself is informative).
  • Can reduce variance in the imputed feature, potentially affecting model performance.

XGBoost's Approach (Sparsity-Aware Split Finding):

1. No Pre-Imputation Required (Generally): XGBoost doesn't require users to impute missing values beforehand. It can handle them directly during tree construction.
2. Learning Default Directions: When evaluating a potential split on a feature, XGBoost considers two scenarios for instances with missing values in that feature:
   • Assign all instances with missing values to the left child node.
   • Assign all instances with missing values to the right child node.
3. Calculating Gain for Each Scenario: For each of these two scenarios, XGBoost calculates the split gain (based on the structure score derived earlier, using G_j²/(H_j+λ)). It effectively tries placing all "missing" instances into the left child, calculates gain, then tries placing them all into the right child, and calculates gain again.
4. Choosing the Best Default Direction: The split point and the default direction (left or right for missings) that result in the maximum gain are chosen for that node. This "default direction" is learned from the data during training.
5. During Prediction: When a new instance with a missing value for a feature encounters a split on that feature, it follows the learned default direction.

Comparison and Advantages of XGBoost's Method:

• Data-Driven: The decision of how to handle missings is learned from the data to maximize split quality, rather than being a heuristic or a separate modeling step.
• Handles Informative Missingness: If the fact that a value is missing is itself predictive, XGBoost can learn to use this information by assigning missings to the branch that improves purity.
• No Bias from Imputation: Avoids introducing potential biases that can arise from inaccurate imputation.
• Efficiency: It's computationally efficient. During split finding, instances are typically sorted by feature value. Instances with missing values are often handled separately or at the end, and only two scenarios for their placement need to be evaluated for gain.
• Robustness: Generally more robust than ad-hoc imputation.

The main idea is that XGBoost learns the best way to partition data with missing values rather than making an upfront assumption or modification to the data via imputation.