Ordered Boosting and Target Statistics

Encoding a categorical feature by its average target value (target encoding) is powerful but dangerous: if a category's own label is used to compute the very statistic used to predict that category's label, the model gets to peek at the answer during training. Ordered boosting, the technique behind CatBoost, closes this leak — not by avoiding target statistics, but by strictly controlling which rows are allowed to see which other rows' targets.

The analogy: grading essays only with feedback from essays graded earlier

Imagine a teaching assistant building a rubric average — "essays mentioning X score 85 on average" — and using that running average to grade every essay in the pile, including the essays that average was built from. Any one essay's grade would then be partly informed by itself, inflating consistency in a way that would not hold up on a brand-new essay. A fairer TA keeps a strict order: grade essay 5 using only the average computed from essays 1 through 4, never essay 5 itself or anything after it. That is what ordered boosting does with target statistics and with each tree's residuals — a row can only be informed by data that came "before" it in a randomly assigned order, never by itself or by data that comes after.

The mechanism

CatBoost picks one or more random permutations (orderings) of the training rows. For a target-based encoding of a category, the encoded value used for row $i$ is computed using only the target values of rows that appear before row $i$ in that permutation:

$$\text{enc}(x_i) = \frac{\sum_{j \prec i,\, x_j = x_i} y_j + a \cdot p}{\sum_{j \prec i,\, x_j = x_i} 1 + a}$$

where $j \prec i$ means "row $j$ comes before row $i$ in the permutation," $p$ is a prior (like the overall average target), and $a$ controls how strongly that prior pulls small-sample estimates toward it. In plain English: row $i$'s encoding only ever uses information available "in the past" relative to a random ordering, never its own label or anything "in the future," so the encoding cannot leak row $i$'s own answer back into itself.

The same ordering principle applies to fitting each new tree's residuals: rather than every tree's residual for row $i$ being computed from a model that was already trained (in part) on row $i$'s own label, ordered boosting maintains a separate running model for each prefix of the permutation, so the residual used for row $i$ comes from a model that never saw row $i$.

Worked example 1: target encoding with and without ordering

Suppose category "sector = tech" appears in rows 3, 7, and 12 with targets $y_3=1, y_7=0, y_{12}=1$. A naive (leaky) encoding computes the average over all three rows — $(1+0+1)/3=0.67$ — and uses that same 0.67 for all three rows, meaning row 3's encoding used row 3's own label. With ordered boosting and a permutation where the visiting order is 7, 3, 12: row 7 gets a prior-only encoding (no prior "tech" rows seen yet, so it falls back to $p$, say $0.5$); row 3 gets encoded using only row 7's target: $(0 + a \cdot 0.5)/(1+a)$; row 12 gets encoded using rows 7 and 3's targets: $(0+1+a \cdot 0.5)/(2+a)$. No row's encoding ever includes its own label.

Worked example 2: why this matters for tiny categories

A category appearing only once in the whole training set, say "sector = niche," has a naive target encoding that is exactly that one row's own label — perfect, leak-driven "predictive power" on training data and none whatsoever on new data (since at inference time there is no future label to encode with). Ordered boosting encodes that single occurrence with just the prior $p$ (since there are zero prior occurrences in any permutation position before it, most of the time), correctly reflecting that a single occurrence carries almost no real signal.

What this means in practice

CatBoost's default behavior handles high-cardinality categorical features (tickers, sectors, counterparties) without the manual leakage-avoidance work that target encoding normally requires with other libraries — no separate out-of-fold encoding scheme needed. It comes at some computational cost, since multiple orderings and running models must be maintained, which is why CatBoost is often slower per tree than XGBoost or LightGBM on the same data.