CatBoost

Gradient boosting built for categorical features: ordered target statistics and symmetric (oblivious) trees.

17 min read1921 wordsadvanced22 viewsupdated 2026-10-07

Definition

CatBoost (Yandex, 2017) is a gradient-boosted tree ensemble that outputs a log-odds score F(x)=F0+η∑mfm(x)F(x)=F_0+\eta\sum_m f_m(x) and a probability p=σ(F(x))p=\sigma(F(x)). Two ideas set it apart: every categorical feature is replaced by an ordered target statistic — the smoothed churn rate (or click rate, fraud rate…) of the earlier rows with the same category in a random permutation, never including the row itself — and every tree is symmetric (oblivious): one question per level, shared by all nodes on that level.

At a glance

Task
Classification: binary (Logloss, CrossEntropy) and multiclass (MultiClass, softmax); the same machinery also does regression and ranking
Input → output
numeric and raw categorical features xx → log-odds F(x)F(x) → probability σ(F(x))\sigma(F(x))
Learns
MM oblivious trees — dd (feature, border) pairs and 2d2^d leaf values each — plus the per-category counts needed to compute target statistics at prediction time
Training
features quantized into at most 254 borders; each level scores every (feature, border) pair over all 2ℓ2^{\ell} current leaves, roughly O(d⋅n⋅p)O(d\cdot n\cdot p) per tree, plus one pass per permutation to compute the statistics
Prediction
dd comparisons per tree, packed into a dd-bit leaf index — O(Md)O(Md) with no branching on tree shape
Hyperparameters
iterations, learning_rate, depth (default 6), l2_leaf_reg (default 3), one_hot_max_size, boosting_type (Plain / Ordered), random_strength, bootstrap_type, auto_class_weights
Assumes
rows are exchangeable, so a random order is a fair "time" (otherwise pass has_time=True); categories seen at prediction time behave like the ones seen in training

The problem

Boosted trees split on numbers. A column like plan, country, merchant id or device model has to be turned into numbers first, and the two textbook options both hurt. One-hot encoding makes one sparse column per level: with 10,000 merchants a tree needs thousands of splits to use the information, and rare levels are almost never chosen. Target encoding — replace each category by the average label of its rows — is a single, very informative column. But computed on the training set it leaks the label: a row's own yy is inside its own encoding.

The leak is worst exactly where categories are rare. A merchant that appears once gets encoding ≈yi\approx y_i — the answer itself. The trees happily split on it, training loss drops, and on new data (where the encoding is just the training average of other rows) the signal is gone. A script-verified example: 2,000 training rows with one informative numeric feature xx and a 500-level category that carries no signal at all:

Encoding of the noise categoryTrain AUCTrain log-lossTest AUCTest log-loss
none (x only)0.8920.4290.7960.545
greedy target statistic0.9430.3160.6680.926
ordered target statistic0.8900.4290.7810.566
CatBoost, raw category0.8330.5020.8000.542
scikit-learn GradientBoostingClassifier (200 trees, depth 3) given xx plus one encoding of the noise category (prior = training base rate, a=1a=1); test rows always use full-training statistics. Last row: CatBoost on the raw category (200 trees, depth 3). Greedy encoding correlates 0.508 with the training labels, the ordered one 0.023, and on test data it is −0.013.

The greedy encoding looks best on training data and is the worst on test data — test log-loss almost doubles. CatBoost's answer is to compute each row's statistic only from rows that come before it in a random order, so no row ever sees its own label. A second, subtler leak — prediction shift, where the gradients for row ii are computed by trees that were fit to row ii — gets the same "only look at the past" fix in ordered boosting. For the shared boosting machinery (residuals, Newton steps, shrinkage) see Gradient Boosting and XGBoost; for histogram tricks and leaf-wise growth see LightGBM.

The idea

Imagine the training rows arriving one at a time, like a stream. When a customer on the Basic plan arrives, all you could honestly know about Basic is the churn rate of the Basic customers you have already seen. That number — shrunk toward a prior so that the first few rows are not wild — is the ordered target statistic. It is exactly what you would know at prediction time about a new customer, so training and test features have the same meaning. Then build boosted trees on log-loss as usual, but make every tree symmetric: at depth 1 ask one question, at depth 2 ask one question in both halves, and so on. Such a tree is a weak, heavily regularized learner, and evaluating it is just building a dd-bit number.

Vocabulary

Permutation σ
a random order of the training rows. "Earlier" always means earlier in σ. CatBoost draws several (permutation_count, 4 by default) and uses different ones for different trees
Target statistic (TS / CTR)
a number replacing a category: smoothed positive rate positives+aPcount+a\frac{\text{positives}+aP}{\text{count}+a} of rows with that category. CatBoost calls these CTRs (from click-through rate)
Prior P, weight a
the value the statistic starts from before any rows are seen, and how many pseudo-rows it is worth. Default binary CTRs use P∈{0,0.5,1}P\in\{0, 0.5, 1\} with a=1a=1 — three statistics per categorical column
Borders / Counter CTR
Borders: positive rate (above a target border); Counter: how often the category occurs — a frequency, no target used
Greedy TS
the leaky version: statistic computed from all rows of the category, including the row itself
Oblivious (symmetric) tree
a depth-dd tree whose 2ℓ2^\ell nodes on level ℓ\ell all ask the same question xj>bx_j>b. It has dd questions and 2d2^d leaves
Leaf index
the dd answers read as a binary number k=∑ℓbℓ2d−ℓk=\sum_\ell b_\ell 2^{d-\ell}; the prediction is a table lookup wkw_k
Prediction shift
the bias from computing row ii's gradient with a model that already saw yiy_i
Ordered boosting
computing row ii's gradient with a model fit only to rows before ii in σ — boosting_type="Ordered"
Feature combination
a new categorical feature made by concatenating categories (e.g. plan × country), encoded with its own TS; CatBoost builds these greedily from categoricals already used in the tree

The math

Ordered target statistic. Let σ\sigma be a random permutation and cic_i the category of row ii. Using only rows earlier in σ\sigma:

x^i=∑j: σ(j)<σ(i)[cj=ci] yj  +  a P∑j: σ(j)<σ(i)[cj=ci]  +  a\hat x_i=\frac{\sum_{j:\,\sigma(j)<\sigma(i)}[c_j=c_i]\,y_j\;+\;a\,P}{\sum_{j:\,\sigma(j)<\sigma(i)}[c_j=c_i]\;+\;a}
x^i\hat x_i
the number that replaces category cic_i for row ii
σ(j)<σ(i)\sigma(j)<\sigma(i)
row jj comes before row ii in the permutation
[cj=ci][c_j=c_i]
1 if row j has the same category, else 0
yj∈{0,1}y_j\in\{0,1\}
label of row j (for multiclass: one statistic per class)
P, aP,\ a
prior value and its weight in pseudo-rows

The key property: x^i\hat x_i does not depend on yiy_i, so E[x^i∣yi]=E[x^i]\mathbb E[\hat x_i\mid y_i]=\mathbb E[\hat x_i] — exactly as for a test row. The greedy statistic replaces the sums by sums over all rows of the category; for a category with ncn_c rows it moves by 1/(nc+a)1/(n_c+a) toward yiy_i, a leak that is huge for rare categories. The prior controls the variance of early rows: the first row of every category gets exactly PP, and a row with kk earlier rows is pulled toward PP by weight a/(k+a)a/(k+a). At prediction time the statistic uses all training rows of the category (an unseen category gets PP).

Log-loss and its derivatives. With score FF and p=σ(F)=1/(1+e−F)p=\sigma(F)=1/(1+e^{-F}), the per-row loss and its first two derivatives with respect to FF are:

ℓ(y,F)=−ylog⁡p−(1−y)log⁡(1−p),g=∂ℓ∂F=p−y,h=∂2ℓ∂F2=p(1−p)\ell(y,F)=-y\log p-(1-y)\log(1-p),\qquad g=\frac{\partial\ell}{\partial F}=p-y,\qquad h=\frac{\partial^2\ell}{\partial F^2}=p(1-p)
gig_i
gradient: negative for a churner whose p is too low, positive for a stayer
hih_i
Hessian: largest (0.25) when p=0.5p=0.5, tiny when the model is already confident

The derivation of gg is short: ∂p/∂F=p(1−p)\partial p/\partial F=p(1-p), so ∂ℓ/∂F=−y(1−p)+(1−y)p=p−y\partial\ell/\partial F=-y(1-p)+(1-y)p=p-y, and differentiating again gives p(1−p)p(1-p). Now add a tree whose leaf kk adds wkw_k to every row it contains. A second-order Taylor expansion plus an L2 penalty gives, per leaf:

∑i∈kℓ(yi,Fi+wk)≈const+Gkwk+12Hkwk2+12λwk2  ⇒  wk∗=−GkHk+λ,score=∑kGk2Hk+λ\sum_{i\in k}\ell(y_i,F_i+w_k)\approx\text{const}+G_kw_k+\tfrac12H_kw_k^2+\tfrac12\lambda w_k^2\;\Rightarrow\;w_k^*=-\frac{G_k}{H_k+\lambda},\quad \text{score}=\sum_k\frac{G_k^2}{H_k+\lambda}
Gk, HkG_k,\ H_k
sums of g and h over the rows in leaf k
λ\lambda
l2_leaf_reg (default 3): shrinks every leaf toward 0, most strongly in leaves with little Hessian mass
wk∗w_k^*
the Newton step for leaf k; the model then adds η·w

Setting the derivative Gk+(Hk+λ)wkG_k+(H_k+\lambda)w_k to zero gives wk∗w_k^*; plugging it back gives a loss reduction of 12Gk2/(Hk+λ)\tfrac12 G_k^2/(H_k+\lambda), so the split that maximizes ∑kGk2/(Hk+λ)\sum_k G_k^2/(H_k+\lambda) reduces the approximate loss most. This is the same Newton machinery as XGBoost. Two CatBoost-specific details: (1) for an oblivious tree the sum runs over all 2ℓ2^\ell leaves of the level at once, because the candidate question is applied everywhere; (2) CatBoost's default score_function is Cosine (the cosine between the gradient vector and the leaf-value vector) rather than the L2 form above, and for Logloss it refines leaves with 10 Newton iterations by default. The worked example uses the L2 score and one Newton step, which the library reproduces exactly when asked.

fm(x)=wk(x),k(x)=∑ℓ=1d[xjℓ>bℓ] 2d−ℓf_m(x)=w_{k(x)},\qquad k(x)=\sum_{\ell=1}^{d}\big[x_{j_\ell}>b_\ell\big]\,2^{d-\ell}
(jℓ,bℓ)(j_\ell,b_\ell)
feature and border of level ℓ\ell — one pair per level, not per node
k(x)k(x)
leaf index built from the d yes/no answers

Ordered boosting. Plain boosting computes gi=pi−yig_i=p_i-y_i with a model F(m−1)F^{(m-1)} that was itself fit on row ii, so gig_i is systematically smaller in magnitude than it would be on an unseen row — the same leak as greedy TS, one level up. Ordered boosting keeps, conceptually, a model MiM_{i} for each prefix of σ\sigma and uses gi=σ(Mσ(i)−1(xi))−yig_i=\sigma\big(M_{\sigma(i)-1}(x_i)\big)-y_i: the gradient of row ii comes from a model trained only on rows before it. CatBoost implements this efficiently by keeping models on exponentially growing prefixes (lengths 1, 2, 4, 8, …), so the cost is a small constant factor rather than nn models. The learning rate η\eta scales every tree; depth dd is the number of shared questions and caps interaction order at dd; random_strength adds noise to split scores (shrinking as training proceeds) to decorrelate trees.

Worked example: who churns?

Twelve subscribers of a streaming service, already in a random permutation σ\sigma. Plan is categorical (Basic, Plus, Pro); tenure is months subscribed. 6 of 12 churned, so F0=log⁡66=0F_0=\log\frac{6}{6}=0 and every row starts at p=0.5p=0.5, g=±0.5g=\pm0.5, h=0.25h=0.25. Settings: prior P=0.5P=0.5, a=1a=1, depth 2, λ=3\lambda=3, η=0.5\eta=0.5. At the end we score a new customer: Basic, 14 months.

RowPlanTenureChurnEarlier same plan (churn / rows)Ordered TSGreedy TS
1Basic810 / 00.5000.900
2Pro1600 / 00.5000.100
3Plus210 / 00.5000.500
4Basic911 / 10.7500.900
5Pro600 / 10.2500.100
6Plus2301 / 10.7500.500
7Plus2901 / 20.5000.500
8Plus711 / 30.3750.500
9Basic112 / 20.8330.900
10Pro1000 / 20.1670.100
11Pro1900 / 30.1250.100
12Basic2013 / 30.8750.900
Training rows in permutation order, with the target statistic each row receives. The ordered TS uses only earlier rows of the same plan; the greedy TS uses all rows of the plan, including the row itself. Correlation with churn: ordered 0.530, greedy 0.816.

One CatBoost tree by hand (ordered TS)

  1. 1Target statistics. Row 4 is the second Basic row; the one before it churned, so x^4=(1+0.5)/(1+1)=0.750\hat x_4=(1+0.5)/(1+1)=0.750. Row 11 is the fourth Pro row; none of the three before it churned: (0+0.5)/(3+1)=0.125(0+0.5)/(3+1)=0.125. The first row of each plan gets the prior 0.5.
  2. 2Gradients. F0=0⇒p=0.5F_0=0\Rightarrow p=0.5: churners have g=0.5−1=−0.5g=0.5-1=-0.5, stayers g=+0.5g=+0.5, all h=0.25h=0.25. The root holds G=0G=0, H=3H=3, score 00.
  3. 3Level 1. Tenure >9.5>9.5 splits the rows into {1,3,4,5,8,9}\{1,3,4,5,8,9\} (G=−2, H=1.5G=-2,\ H=1.5) and {2,6,7,10,11,12}\{2,6,7,10,11,12\} (G=+2, H=1.5G=+2,\ H=1.5): score 44.5+44.5=1.778\tfrac{4}{4.5}+\tfrac{4}{4.5}=1.778. The best TS border, 0.31250.3125, scores only 1.523.75+1.525.25=1.029\tfrac{1.5^2}{3.75}+\tfrac{1.5^2}{5.25}=1.029. → tenure > 9.5.
  4. 4Level 2 (shared). Now each candidate is scored over all four leaves at once. TS >0.8542>0.8542 isolates row 12 (Basic, 20 months, churned — the only long-tenure churner) in the right half; in the left half no row exceeds it. Score (−2)21.5+3+2.521.25+3+(−0.5)20.25+3=0.889+1.471+0.077=2.436\tfrac{(-2)^2}{1.5+3}+\tfrac{2.5^2}{1.25+3}+\tfrac{(-0.5)^2}{0.25+3}=0.889+1.471+0.077=2.436, beating the best second tenure border (6.5 or 19.5, score 1.556). → TS > 0.8542 in both halves.
  5. 5Leaf values w=−G/(H+λ)w=-G/(H+\lambda): leaf 0 (short, low TS; 5 churners + row 5) =2/4.5=+0.444=2/4.5=+0.444; leaf 1 (short, high TS) is empty → 0; leaf 2 (long, low TS; 5 stayers) =−2.5/4.25=−0.588=-2.5/4.25=-0.588; leaf 3 (row 12) =0.5/3.25=+0.154=0.5/3.25=+0.154.
  6. 6Update F←F+0.5 wF\leftarrow F+0.5\,w: leaf-0 rows go to p=σ(0.222)=0.555p=\sigma(0.222)=0.555, leaf-2 rows to σ(−0.294)=0.427\sigma(-0.294)=0.427, row 12 to σ(0.077)=0.519\sigma(0.077)=0.519. Training log-loss 0.693→0.5990.693\to0.599.
  7. 7Predict Basic, 14 months. At prediction time its TS uses all four Basic rows: (4+0.5)/(4+1)=0.900(4+0.5)/(4+1)=0.900. Answers: tenure 14>9.514>9.5 → 1, TS 0.9>0.8540.9>0.854 → 1, so leaf k=1⋅2+1=3k=1\cdot2+1=3 and P(churn)=σ(0.5⋅0.154)=P(\text{churn})=\sigma(0.5\cdot0.154)= 0.519 after one tree (0.854 after 50 trees of the from-scratch code below).
StatisticLevel 1 (score)Level 2 (score)Leaf w (rows)Log-loss
Ordered TStenure > 9.5 (1.778)TS > 0.854 (2.436)+0.444 (6) · 0 (0) · −0.588 (5) · +0.154 (1)0.599
Greedy TSTS > 0.3 (1.800)tenure > 21.5 (3.286)−0.500 (4) · 0 (0) · +0.667 (6) · −0.286 (2)0.566
The same first tree with ordered vs greedy statistics (λ=3\lambda=3, η=0.5\eta=0.5). With the leaky statistic the root splits on TS, because 1.800 beats tenure's 1.778 — and the training loss looks better.
▸ CatBoost · ordered TS · λ = 3step 1/21
TS:λ:
permutation order σ · ● churned ● stayed · bar = TS fed to the treesrowplanmo.P011Basic82Pro163Plus24Basic95Pro66Plus237Plus298Plus79Basic110Pro1011Pro1912Basic20
corr(TS, churn) = 0.530log-loss 0.693
  1. 1shuffle rows → permutation σ
  2. 2for i in σ:
  3. 3 TS[i] = (pos + a·P) / (cnt + a)
  4. 4F = logit(ȳ); p = σ(F); g = p − y; h = p(1 − p)
  5. 5for level = 1..depth:
  6. 6 (j, b) = argmax Σ_leaves G² / (H + λ)
  7. 7 ask x_j > b in EVERY node of the level
  8. 8w_leaf = −G_leaf / (H_leaf + λ)
  9. 9F += η · w[leaf(x)]
  10. 10predict: leaf = bits(x) → p = σ(F)

12 customers in a random permutation σ. Each plan will be replaced by a target statistic with prior P = 0.5 and weight a = 1 (ordered mode).

fig.The worked example, live. First the 12 customers stream in permutation order: each bar is the target statistic the trees will see; the ringed dots are the rows it is computed from, and in ordered mode later rows of the same plan stay greyed out as "unseen". Then the dots fly into the (tenure, TS) plane, and one depth-2 symmetric tree grows on log-loss gradients: dashed lines are each feature's best border with its score, solid lines the chosen questions (level 1: tenure > 9.5, score 1.778; level 2: TS > 0.854 across both halves, score 2.436), shaded cells the Newton leaf values (+0.444, empty, −0.588, +0.154). Probabilities update (log-loss 0.693 → 0.599) and the new Basic, 14-month customer lands in leaf 3 with p = 0.519. Switch to greedy to watch row labels leak into the bars (correlation 0.530 → 0.816) and TS take the root; change λ to see leaf values shrink (λ = 0 takes full Newton steps −2, +2, −2, −1 and moves the second split to TS > 0.313; λ = 10 shrinks them to +0.174, 0, −0.222, +0.049).

The algorithm, step by step

CatBoostClassifier.fit

  1. 1Quantize every numeric feature into at most border_count (254) bins. Categorical columns with at most one_hot_max_size levels are one-hot encoded; the rest get target statistics.
  2. 2Permute. Draw ss random permutations of the rows (or keep the given order if has_time=True). For each permutation compute ordered TS for every categorical feature (and, as trees grow, for combinations of categoricals).
  3. 3Start from F0F_0 (0, or the log-odds of the base rate with boost_from_average).
  4. 4For each tree m=1…Mm=1\ldots M: pick a permutation; compute gi=pi−yig_i=p_i-y_i and hi=pi(1−pi)h_i=p_i(1-p_i) — in Ordered mode from the prefix model that has not seen row ii.
  5. 5Grow symmetrically. For level ℓ=1…d\ell=1\ldots d, score each (feature, border) pair over all 2ℓ−12^{\ell-1} current leaves, add random noise scaled by random_strength, and apply the best pair to every node.
  6. 6Leaves. Set wk=−Gk/(Hk+λ)w_k=-G_k/(H_k+\lambda) (refined by a few Newton iterations) and update F←F+η wk(x)F\leftarrow F+\eta\,w_{k(x)} on every permutation's model.
  7. 7Predict with full-data statistics for every category, dd comparisons per tree to form a bit index, sum the leaves, apply σ\sigma (or softmax for multiclass).

Complexity. Computing ordered statistics is one pass per permutation and categorical feature, O(sn)O(sn). A tree level costs about O(n⋅p)O(n\cdot p) histogram updates plus O(2ℓ⋅p⋅B)O(2^\ell\cdot p\cdot B) score evaluations for BB borders, so a tree is O(d n p)O(d\,n\,p); Ordered boosting multiplies the gradient work by a small constant (logarithmic number of prefix models). Prediction is O(Md)O(Md) comparisons and is very cache- and SIMD-friendly, which is why CatBoost models are fast to serve.

Variants, hyperparameters and tuning

ParameterDefaultEffect
learning_rate, iterationsauto, 1000η scales each tree. Lower η + more trees is smoother; use eval_set with early_stopping_rounds to pick the count
depth6number of shared questions → 2^d leaves and interactions up to order d. 4–10 is the useful range
l2_leaf_reg3λ in −G/(H+λ): larger shrinks leaves and lowers the score of splits that create low-Hessian (confident or small) leaves
boosting_typePlain (here)Ordered removes prediction shift; slower, most useful on small data
one_hot_max_size2categoricals with at most this many levels are one-hot encoded instead of target-encoded
simple_ctr / priorsBorders (P = 0, 0.5, 1) + Counterwhich statistics are built per categorical; more priors = more candidate columns
max_ctr_complexity—how many categoricals may be combined into one feature combination
random_strength1noise added to split scores; decorrelates trees, set 0 for reproducing hand calculations
bootstrap_typeMVSrow sampling per tree (Bayesian, Bernoulli, MVS, No)
auto_class_weightsNoneBalanced / SqrtBalanced reweight rare classes in g and h
grow_policySymmetricTreeDepthwise or Lossguide give ordinary (non-oblivious) trees, closer to XGBoost / LightGBM
The knobs that matter for classification, and what they do. Defaults are from catboost 1.2.10.

Practical tuning

Start
pass raw categoricals via cat_features — do not one-hot or target-encode them yourself; defaults are usually within a few percent of tuned
Then
fix a small learning_rate (0.03–0.1) with early stopping, tune depth (4–10) and l2_leaf_reg (1–10)
Small data
try boosting_type="Ordered" and more permutations; compare on a validation set
Imbalanced
use auto_class_weights or scale_pos_weight, and judge with log-loss / PR-AUC, not accuracy
Time-ordered rows
sort by time and set has_time=True so "earlier" means the real past

In code

python
1import numpy as np
2
3plan = np.array("Basic Pro Plus Basic Pro Plus Plus Plus Basic Pro Pro Basic".split())
4tenure = np.array([8, 16, 2, 9, 6, 23, 29, 7, 1, 10, 19, 20], float)
5y = np.array([1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1], float)
6PRIOR, A = 0.5, 1.0 # TS = (positives + A*PRIOR) / (count + A)
7
8def ordered_ts(cat, y):
9 """Rows are already in permutation order: each row sees only the rows before it."""
10 pos, cnt, out = {}, {}, np.empty(len(y))
11 for i, c in enumerate(cat):
12 out[i] = (pos.get(c, 0) + A * PRIOR) / (cnt.get(c, 0) + A)
13 pos[c] = pos.get(c, 0) + y[i]
14 cnt[c] = cnt.get(c, 0) + 1
15 return out
16
17def full_ts(cat, y, c): # used at prediction time: all training rows
18 m = cat == c
19 return (y[m].sum() + A * PRIOR) / (m.sum() + A)
20
21def oblivious_tree(X, g, h, depth, lam):
22 """One (feature, border) per level, shared by every node; Newton leaf values."""
23 idx, splits = np.zeros(len(g), int), []
24 for _ in range(depth):
25 best = (-np.inf, None, None)
26 for j in range(X.shape[1]):
27 v = np.unique(X[:, j])
28 for t in (v[:-1] + v[1:]) / 2:
29 if (j, t) in splits:
30 continue
31 leaf = 2 * idx + (X[:, j] > t)
32 score = sum(g[leaf == k].sum() ** 2 / (h[leaf == k].sum() + lam) for k in np.unique(leaf))
33 if score > best[0] + 1e-12:
34 best = (score, j, t)
35 _, j, t = best
36 splits.append((j, t))
37 idx = 2 * idx + (X[:, j] > t)
38 G = np.bincount(idx, g, 2 ** depth)
39 H = np.bincount(idx, h, 2 ** depth)
40 return splits, -G / (H + lam)
41
42def leaf_index(splits, x):
43 k = 0
44 for j, t in splits: # the same question on every level: just build a binary number
45 k = 2 * k + int(x[j] > t)
46 return k
47
48sigmoid = lambda f: 1 / (1 + np.exp(-f))
49logloss = lambda f: -np.mean(y * np.log(sigmoid(f)) + (1 - y) * np.log(1 - sigmoid(f)))
50
51def fit(X, y, rounds, depth=2, lr=0.5, lam=3.0):
52 F, trees = np.zeros(len(y)), [] # F0 = log-odds of the base rate (6/12 -> 0)
53 for _ in range(rounds):
54 p = sigmoid(F)
55 g, h = p - y, p * (1 - p) # log-loss gradient and Hessian
56 splits, w = oblivious_tree(X, g, h, depth, lam)
57 F += lr * w[[leaf_index(splits, x) for x in X]]
58 trees.append((splits, w))
59 return trees, F
60
61ts = ordered_ts(plan, y)
62X = np.c_[tenure, ts]
63print("ordered TS:", np.round(ts, 4))
64trees, F = fit(X, y, rounds=1)
65print("tree 1 splits:", [(int(j), round(float(t), 4)) for j, t in trees[0][0]])
66print("tree 1 leaves:", np.round(trees[0][1], 4) + 0.0)
67print("log-loss 0.6931 ->", round(logloss(F), 4))
68x_new = np.array([14, full_ts(plan, y, "Basic")]) # Basic plan, 14 months
69f = sum(0.5 * w[leaf_index(s, x_new)] for s, w in trees)
70print("new customer: TS", round(x_new[1], 4), "leaf", leaf_index(trees[0][0], x_new), "P(churn) =", round(sigmoid(f), 4))
71trees, F = fit(X, y, rounds=50)
72f = sum(0.5 * w[leaf_index(s, x_new)] for s, w in trees)
73print("50 trees: train log-loss", round(logloss(F), 4), "| new customer P(churn) =", round(sigmoid(f), 4))
From scratch: ordered target statistics + symmetric trees with Newton leaves on log-loss. Prints the hand-computed tree and prediction.
text
1ordered TS: [0.5 0.5 0.5 0.75 0.25 0.75 0.5 0.375 0.8333 0.1667
2 0.125 0.875 ]
3tree 1 splits: [(0, 9.5), (1, 0.8542)]
4tree 1 leaves: [ 0.4444 0. -0.5882 0.1538]
5log-loss 0.6931 -> 0.5993
6new customer: TS 0.9 leaf 3 P(churn) = 0.5192
750 trees: train log-loss 0.0776 | new customer P(churn) = 0.8541
Output of the script above.
python
1import numpy as np, pandas as pd
2from catboost import CatBoostClassifier
3from sklearn.metrics import log_loss
4
5df = pd.DataFrame({
6 "plan": "Basic Pro Plus Basic Pro Plus Plus Plus Basic Pro Pro Basic".split(),
7 "tenure": [8, 16, 2, 9, 6, 23, 29, 7, 1, 10, 19, 20],
8 "churn": [1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1],
9})
10new = pd.DataFrame({"plan": ["Basic"], "tenure": [14]})
11
12# 1) Reproduce the hand-built first tree: feed the ordered TS as a number, one Newton step.
13X = pd.DataFrame({"tenure": df.tenure, "ts": [0.5, 0.5, 0.5, 0.75, 0.25, 0.75, 0.5, 0.375, 5 / 6, 1 / 6, 0.125, 0.875]})
14one = CatBoostClassifier(iterations=1, depth=2, learning_rate=0.5, l2_leaf_reg=3, score_function="L2",
15 leaf_estimation_iterations=1, random_strength=0, bootstrap_type="No", verbose=0)
16one.fit(X, df.churn)
17print("1 tree, raw scores:", np.round(one.predict(X, prediction_type="RawFormulaVal"), 4))
18print("1 tree, Basic 14 months: P(churn) =", round(float(one.predict_proba(pd.DataFrame({"tenure": [14], "ts": [0.9]}))[0, 1]), 4))
19
20# 2) The normal way: give CatBoost the raw category.
21for mode in ["Plain", "Ordered"]:
22 m = CatBoostClassifier(iterations=200, depth=2, learning_rate=0.1, boosting_type=mode,
23 one_hot_max_size=1, random_seed=0, verbose=0)
24 m.fit(df[["plan", "tenure"]], df.churn, cat_features=["plan"])
25 p = m.predict_proba(df[["plan", "tenure"]])[:, 1]
26 print(mode, "| train log-loss", round(log_loss(df.churn, p), 3), "| Basic 14 months -> P(churn) =",
27 round(float(m.predict_proba(new)[0, 1]), 3),
28 "| importances", dict(zip(["plan", "tenure"], [round(float(v), 1) for v in m.get_feature_importance()])))
With the catboost library: first reproducing the hand-built tree exactly, then the normal workflow with the raw category.
text
11 tree, raw scores: [ 0.2222 -0.2941 0.2222 0.2222 0.2222 -0.2941 -0.2941 0.2222 0.2222
2 -0.2941 -0.2941 0.0769]
31 tree, Basic 14 months: P(churn) = 0.5192
4Plain | train log-loss 0.05 | Basic 14 months -> P(churn) = 0.8 | importances {'plan': 33.8, 'tenure': 66.2}
5Ordered | train log-loss 0.009 | Basic 14 months -> P(churn) = 0.991 | importances {'plan': 32.3, 'tenure': 67.7}
Output (catboost 1.2.10). The library's own CTRs (three priors + counts), several permutations and Cosine scoring give different numbers from our single hand-built statistic.

Use when

  • +The data has categorical columns, especially high-cardinality ones (merchant, SKU, postcode, user id), and you want them used without hand-made encodings or leakage.
  • +You want strong results from default settings — ordered statistics and symmetric trees are built-in regularizers.
  • +Serving latency matters: oblivious trees evaluate as branch-free bit lookups.
  • +You want calibrated-ish probabilities on tabular data with little tuning.

Avoid when

  • −All features are numeric and the dataset is huge: LightGBM is usually faster to train at similar accuracy.
  • −The signal is in raw text, images or sequences: use a neural model (or its embeddings as features).
  • −You need a readable model: hundreds of trees plus stored category statistics are not auditable rules.
  • −Category meanings drift over time: statistics stored at training time go stale silently.

Where it's used

Search & recommendation ranking

Yandex built it for web search and ads, where query, region and document ids are huge categoricals; it is used for click and conversion prediction.

Fraud & credit risk

Merchant, device, BIN and country columns are high-cardinality and rare levels matter most — the exact case where greedy encodings leak.

Churn & customer analytics

Plan, region, acquisition channel and product mix next to numeric usage features — like the worked example.

Tabular competitions & AutoML

A standard member of Kaggle and AutoML ensembles next to XGBoost and LightGBM, often the strongest out of the box when categoricals dominate.

Check yourself

A row is the third row of its category in the permutation. The two earlier rows have labels 1 and 0. With prior P = 0.5 and a = 1, its ordered target statistic is…

Check yourself

A leaf contains 3 churners and 1 stayer, all with p = 0.5. With λ = 1, the Newton leaf value w = −G/(H + λ) is…

Check yourself

A depth-6 CatBoost (symmetric) tree has how many distinct split questions and how many leaves?

Check yourself

Why does a greedy (full-data) target statistic hurt test performance most for rare categories?

Remember

  • ✓CatBoost replaces each category by an ordered target statistic: the prior-smoothed positive rate of earlier rows of that category in a random permutation, so no row sees its own label.
  • ✓Greedy target encoding leaks the label (train AUC 0.943 → test 0.668 on a pure-noise category); ordered statistics remove the leak; at prediction time the statistic uses all training rows.
  • ✓Each tree fits log-loss gradients g=p−yg=p-y, h=p(1−p)h=p(1-p) with Newton leaves w=−G/(H+λ)w=-G/(H+\lambda) — the same core as XGBoost.
  • ✓Trees are symmetric: one question per level, dd questions and 2d2^d leaves, prediction = bit index lookup. Strong regularization, fast inference, sometimes empty leaves.
  • ✓Ordered boosting applies the same "only the past" rule to gradients, removing prediction shift; it costs more and helps most on small data.
  • ✓Pass raw categoricals in cat_features, tune depth, l2_leaf_reg and learning rate with early stopping, and judge only on held-out data.
← back to ML Algorithms roadmap