XGBoost in machine learning, explained in 5 lines

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

XGBoost, in more detail

XGBoost is gradient boosting rebuilt for speed and control.

The idea is the same, but the engineering is far better.

It folds regularization directly into how each tree is scored.

That makes it noticeably harder to overfit than plain boosting.

It deals with missing values on its own by learning which way to send them.

It finds splits using a summary of the data instead of checking every value.

It uses all your cores, and it can use a GPU.

Early stopping is built in, which makes tuning much less painful.

The settings that matter most are learning rate, depth and number of rounds.

Lower the learning rate and raise the rounds when you want more accuracy.

LightGBM grows trees leaf by leaf and is often faster on large data.

CatBoost handles categorical columns better with less preparation.

All three are close enough that the choice rarely decides a project.

It stays a very strong default for anything shaped like a spreadsheet.

Neural networks still have not clearly overtaken it on tabular problems.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath XGBoost

The objective it actually minimises

Gradient boosting fits each tree to a gradient. XGBoost writes the whole thing as one objective and includes the tree's own complexity in it.

\mathcal{O} = \sum_{i=1}^{n} \mathcal{L}\big(y_i, \hat{y}_i\big) + \sum_{m=1}^{M} \Omega(f_m)

\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2

$T$ : the number of leaves in the tree.
$w_j$ : the value that leaf $j$ outputs.
$\gamma$ : the cost charged per leaf.
$\lambda$ : L2 regularisation on the leaf values.

Regularisation is part of the objective rather than a stopping rule bolted on afterwards, which is the first real difference from plain boosting.

Second order, not first

\mathcal{O}^{(m)} \approx \sum_{i=1}^{n} \left[ g_i f_m(\mathbf{x}_i) + \frac{1}{2} h_i f_m(\mathbf{x}_i)^2 \right] + \Omega(f_m)

$g_i$ : the first derivative of the loss at sample $i$ .
$h_i$ : the second derivative at sample $i$ .

Expanding the loss to second order turns each round into a quadratic, and a quadratic can be solved exactly rather than approached by line search.

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

That is the optimal output for leaf $j$ , in closed form, where $I_j$ is the set of samples landing in it.

The gain a split must earn

\mathrm{Gain} = \frac{1}{2}\left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma

$G_L, G_R$ : the summed gradients on each side of the split.
$H_L, H_R$ : the summed second derivatives on each side.

Substituting the optimal leaf values back into the objective gives the score of a tree structure, and the difference before and after a split is that gain.

A split is kept only if the gain exceeds $\gamma$ , so the $-\gamma$ term prunes as the tree grows rather than after it.

One round, in order

Compute $g_i$ and $h_i$ for every training sample under the current prediction.
Sort each feature and sweep the split points, accumulating $G$ and $H$ on each side.
Take the split with the highest gain, and refuse the node entirely if no gain is positive.
Set each leaf to its closed-form optimal value.
Add the tree scaled by the learning rate, and move to the next round.

What makes it fast rather than just accurate

Gradient and second derivative for every sample are computed once per round and then only summed, so a split sweep is addition rather than model fitting.

Feature values are pre-sorted into compressed column blocks once, so the sort is not repeated at every node of every tree.

A missing value is not imputed. Each split learns a default direction by trying both and keeping whichever scored better, so sparsity is handled by the algorithm rather than before it.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What does XGBoost add on top of plain gradient boosting?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →