XGBoost Explained: From Gradient Boosting to Weighted Quantile Sketch

XGBoost

Introduction: XGBoost

XGBoost is a tree-based algorithm. It is a variant of Gradient Boosting which is one of the highest-scaled versions of it. It performs calculations 10x faster than Gradient Boosting. Its success is also witnessed in Kaggle's competitions wherein out of 29, 17 solutions used XGBoost. Its capability also shines in handling sparse data and null values.

Before understanding XGBoost let's understand boosting first.

Boosting

In simple words, boosting is: take the mistakes/errors of the first model and send it to another model to correct it. Then again predict the actual target, identify the errors, and again send them further for correction.

It is the working principle for both normal GB and XGBoost. However, XGBoost is far better than the normal one in scaling.

Objective Function

L(φ) = Σᵢ l(ŷᵢ, yᵢ) + Σₖ Ω(fₖ)

where:

Ω(f) = γT + ½λ Σⱼ wⱼ²

Above is an objective function which XGBoost has to minimize.

where:

T → Number of leaves

w → Weight of leaf

But the main drawback is that the above equation is non-optimizable in Euclidean space as each fₖ is a decision tree. It can't be optimized simply as Linear Regression because each tree structure is different.

Hence, some more modifications are done. The 2nd-order Taylor series is used.

L⁽ᵗ⁾ = Σᵢ l(yᵢ, ŷᵢ⁽ᵗ⁻¹⁾ + fₜ(xᵢ)) + Ω(fₜ)

Using the second-order Taylor expansion:

L⁽ᵗ⁾ ≈ Σᵢ [l(yᵢ, ŷᵢ⁽ᵗ⁻¹⁾) + gᵢfₜ(xᵢ) + ½hᵢfₜ(xᵢ)²] + Ω(fₜ)

Removing the constant term:

L⁽ᵗ⁾ ≈ Σᵢ [gᵢfₜ(xᵢ) + ½hᵢfₜ(xᵢ)²] + Ω(fₜ)

Gradient tells which direction to move.

Hessian tells the shape/curvature of the curve.

Therefore:

L⁽ᵗ⁾ = Σᵢ [gᵢfₜ(xᵢ) + ½hᵢfₜ(xᵢ)²] + γT + ½λΣⱼwⱼ²

On solving the above equation and differentiating with respect to w, it gives the optimal w value:

wⱼ* = − [Σᵢ∈Iⱼ gᵢ] / [Σᵢ∈Iⱼ hᵢ + λ]

where Iⱼ represents the instances that fall into leaf j.

---

Split Finding

The objective function can be written as:

L⁽ᵗ⁾ = Σⱼ [ (Σᵢ∈Iⱼ gᵢ)wⱼ + ½(Σᵢ∈Iⱼ hᵢ + λ)wⱼ² ] + γT

Putting the optimal wⱼ back into the equation:

L⁽ᵗ⁾(q) = −½ Σⱼ [ (Σᵢ∈Iⱼ gᵢ)² / (Σᵢ∈Iⱼ hᵢ + λ) ] + γT

This is a scoring function to measure the quality of a tree, like Gini impurity for a Decision Tree.

Since a tree has too many possible structures which are impossible to enumerate, we use a greedy approach.

Assume Iᴸ and Iᴿ are the left and right instances of a tree.

The split gain can be calculated as:

Gain = ½ [ Gᴸ²/(Hᴸ+λ) + Gᴿ²/(Hᴿ+λ) − G²/(H+λ) ] − γ

where:

Gᴸ = Σᵢ∈Iᴸ gᵢ

Hᴸ = Σᵢ∈Iᴸ hᵢ

Gᴿ = Σᵢ∈Iᴿ gᵢ

Hᴿ = Σᵢ∈Iᴿ hᵢ

G = Gᴸ + Gᴿ

H = Hᴸ + Hᴿ

It is used in practice for evaluating split candidates.

---

Greedy Algorithm

Input: I, instance set of current node

Input: d, feature dimension

First calculate:

G = Σᵢ∈I gᵢ

H = Σᵢ∈I hᵢ

Then sort the instances according to the feature value.

For every possible split:

Gᴸ ← Gᴸ + gⱼ

Hᴸ ← Hᴸ + hⱼ

The right-side statistics can then be obtained as:

Gᴿ ← G − Gᴸ

Hᴿ ← H − Hᴸ

Then calculate the gain for the split and keep the maximum:

Score = max(Score, Gain)

Output: Split with maximum score.

The above approach is greedy, which is good only for small datasets as it has to try all possible split points.

The approximate approach comes into the picture here.

---

Approximate Split Finding

The second-order objective can be rewritten as:

L⁽ᵗ⁾ = Σᵢ ½hᵢ [ fₜ(xᵢ) − gᵢ/hᵢ ]² + Ω(fₜ) + constant

This has the form of a weighted squared-loss problem.

Here:

gᵢ/hᵢ → acts like the target

hᵢ → acts as the weight

Therefore, XGBoost uses hᵢ as the weight when constructing weighted quantiles.

---

Weighted Quantile Sketch

For a particular feature k, we can represent the feature values and their corresponding Hessians as:

Dₖ = {(x₁ₖ,h₁), (x₂ₖ,h₂), ..., (xₙₖ,hₙ)}

Here:

xᵢₖ = value of feature k for instance i

hᵢ = second-order gradient/Hessian of instance i

XGBoost defines a weighted rank function:

rₖ(z) = [Σ₍ₓ,ₕ₎∈Dₖ, x<z h] / [Σ₍ₓ,ₕ₎∈Dₖ h]

In simple words, this tells us:

"What fraction of the total weight lies below a certain feature value z?"

Since XGBoost wants consecutive candidate split points to be reasonably close, ε is used as an approximation factor.

The candidate split points satisfy:

|rₖ(sₖ,ⱼ) − rₖ(sₖ,ⱼ₊₁)| < ε

Here, ε controls how finely the weighted distribution is approximated.

Approximately:

1/ε → number of candidate regions

For example:

ε = 0.1

1/ε = 10

So there are roughly 10 candidate regions.

Similarly:

ε = 0.01

1/ε = 100

So there are roughly 100 candidate regions.

A smaller ε gives a finer approximation and therefore more candidate split points.

The weighted quantile sketch allows XGBoost to generate a manageable number of candidate split points instead of checking every possible feature value.

---

Handling Missing Values

XGBoost also handles null/missing values by assigning a default direction to each branch.

During training, XGBoost considers where missing values should go and chooses the default direction that gives the better split score.

Therefore, when a feature value is missing during prediction, the instance is sent in the learned default direction.

---

Example: XGBoost with Numerical and Categorical Features

Let's understand the above concepts with a small example.

Suppose we want to predict whether a customer will buy a product.

1 → Customer buys

0 → Customer does not buy

Our dataset contains one numerical feature, Age, and one categorical feature, Device.

Customer	Age	Device	Actual y
A	28	Mobile	0
B	25	Mobile	0
C	30	Laptop	1
D	35	Laptop	1
E	40	Mobile	1
F	45	Laptop	1

Step 1: Initial Prediction

For simplicity, assume XGBoost starts with:

ŷᵢ = 0.5

for every customer.

Using squared error:

l(ŷ,y) = ½(ŷ − y)²

The gradient is:

gᵢ = ∂l / ∂ŷᵢ = ŷᵢ − yᵢ

and the Hessian is:

hᵢ = ∂²l / ∂ŷᵢ² = 1

Therefore:

Customer	y	Prediction	Gradient gᵢ	Hessian hᵢ
A	0	0.5	0.5	1
B	0	0.5	0.5	1
C	1	0.5	-0.5	1
D	1	0.5	-0.5	1
E	1	0.5	-0.5	1
F	1	0.5	-0.5	1

The positive gradient for A and B tells us that their predictions need to move down, while the negative gradient for C, D, E and F tells us that their predictions need to move up.

---

Step 2: Try a Numerical Split

For the numerical feature Age, XGBoost can consider different split points.

For example:

Age < 27.5

This creates two groups.

Left:

A, B

Right:

C, D, E, F

For the left side:

Gᴸ = 0.5 + 0.5 = 1

Hᴸ = 1 + 1 = 2

For the right side:

Gᴿ = -0.5 - 0.5 - 0.5 - 0.5 = -2

Hᴿ = 4

The optimal leaf weight is:

wⱼ* = −Gⱼ / (Hⱼ + λ)

Assuming:

λ = 0

For the left leaf:

wᴸ = −1/2 = -0.5

For the right leaf:

wᴿ = −(-2)/4 = 0.5

So the tree can be represented as:

text
              Age < 27.5?
              /          \
           Yes            No
            |              |
          -0.5            +0.5