Definition
CatBoost (Yandex, 2017) is a gradient-boosted tree ensemble that outputs a log-odds score and a probability . 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 → log-odds → probability
- Learns
- oblivious trees — (feature, border) pairs and 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 current leaves, roughly per tree, plus one pass per permutation to compute the statistics
- Prediction
- comparisons per tree, packed into a -bit leaf index — 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 is inside its own encoding.
The leak is worst exactly where categories are rare. A merchant that appears once gets encoding — 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 and a 500-level category that carries no signal at all:
| Encoding of the noise category | Train AUC | Train log-loss | Test AUC | Test log-loss |
|---|---|---|---|---|
| none (x only) | 0.892 | 0.429 | 0.796 | 0.545 |
| greedy target statistic | 0.943 | 0.316 | 0.668 | 0.926 |
| ordered target statistic | 0.890 | 0.429 | 0.781 | 0.566 |
| CatBoost, raw category | 0.833 | 0.502 | 0.800 | 0.542 |
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 are computed by trees that were fit to row — 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 -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 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 with — 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- tree whose nodes on level all ask the same question . It has questions and leaves
- Leaf index
- the answers read as a binary number ; the prediction is a table lookup
- Prediction shift
- the bias from computing row 's gradient with a model that already saw
- Ordered boosting
- computing row 's gradient with a model fit only to rows before 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 be a random permutation and the category of row . Using only rows earlier in :
- the number that replaces category for row
- row comes before row in the permutation
- 1 if row j has the same category, else 0
- label of row j (for multiclass: one statistic per class)
- prior value and its weight in pseudo-rows
The key property: does not depend on , so — exactly as for a test row. The greedy statistic replaces the sums by sums over all rows of the category; for a category with rows it moves by toward , a leak that is huge for rare categories. The prior controls the variance of early rows: the first row of every category gets exactly , and a row with earlier rows is pulled toward by weight . At prediction time the statistic uses all training rows of the category (an unseen category gets ).
Log-loss and its derivatives. With score and , the per-row loss and its first two derivatives with respect to are:
- gradient: negative for a churner whose p is too low, positive for a stayer
- Hessian: largest (0.25) when , tiny when the model is already confident
The derivation of is short: , so , and differentiating again gives . Now add a tree whose leaf adds to every row it contains. A second-order Taylor expansion plus an L2 penalty gives, per leaf:
- sums of g and h over the rows in leaf k
l2_leaf_reg(default 3): shrinks every leaf toward 0, most strongly in leaves with little Hessian mass- the Newton step for leaf k; the model then adds η·w
Setting the derivative to zero gives ; plugging it back gives a loss reduction of , so the split that maximizes 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 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.
- feature and border of level — one pair per level, not per node
- leaf index built from the d yes/no answers
Ordered boosting. Plain boosting computes with a model that was itself fit on row , so 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 for each prefix of and uses : the gradient of row 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 models. The learning rate scales every tree; depth is the number of shared questions and caps interaction order at ; 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 . Plan is categorical (Basic, Plus, Pro); tenure is months subscribed. 6 of 12 churned, so and every row starts at , , . Settings: prior , , depth 2, , . At the end we score a new customer: Basic, 14 months.
| Row | Plan | Tenure | Churn | Earlier same plan (churn / rows) | Ordered TS | Greedy TS |
|---|---|---|---|---|---|---|
| 1 | Basic | 8 | 1 | 0 / 0 | 0.500 | 0.900 |
| 2 | Pro | 16 | 0 | 0 / 0 | 0.500 | 0.100 |
| 3 | Plus | 2 | 1 | 0 / 0 | 0.500 | 0.500 |
| 4 | Basic | 9 | 1 | 1 / 1 | 0.750 | 0.900 |
| 5 | Pro | 6 | 0 | 0 / 1 | 0.250 | 0.100 |
| 6 | Plus | 23 | 0 | 1 / 1 | 0.750 | 0.500 |
| 7 | Plus | 29 | 0 | 1 / 2 | 0.500 | 0.500 |
| 8 | Plus | 7 | 1 | 1 / 3 | 0.375 | 0.500 |
| 9 | Basic | 1 | 1 | 2 / 2 | 0.833 | 0.900 |
| 10 | Pro | 10 | 0 | 0 / 2 | 0.167 | 0.100 |
| 11 | Pro | 19 | 0 | 0 / 3 | 0.125 | 0.100 |
| 12 | Basic | 20 | 1 | 3 / 3 | 0.875 | 0.900 |
One CatBoost tree by hand (ordered TS)
- 1Target statistics. Row 4 is the second Basic row; the one before it churned, so . Row 11 is the fourth Pro row; none of the three before it churned: . The first row of each plan gets the prior 0.5.
- 2Gradients. : churners have , stayers , all . The root holds , , score .
- 3Level 1. Tenure splits the rows into () and (): score . The best TS border, , scores only . → tenure > 9.5.
- 4Level 2 (shared). Now each candidate is scored over all four leaves at once. TS 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 , beating the best second tenure border (6.5 or 19.5, score 1.556). → TS > 0.8542 in both halves.
- 5Leaf values : leaf 0 (short, low TS; 5 churners + row 5) ; leaf 1 (short, high TS) is empty → 0; leaf 2 (long, low TS; 5 stayers) ; leaf 3 (row 12) .
- 6Update : leaf-0 rows go to , leaf-2 rows to , row 12 to . Training log-loss .
- 7Predict Basic, 14 months. At prediction time its TS uses all four Basic rows: . Answers: tenure → 1, TS → 1, so leaf and 0.519 after one tree (0.854 after 50 trees of the from-scratch code below).
| Statistic | Level 1 (score) | Level 2 (score) | Leaf w (rows) | Log-loss |
|---|---|---|---|---|
| Ordered TS | tenure > 9.5 (1.778) | TS > 0.854 (2.436) | +0.444 (6) · 0 (0) · −0.588 (5) · +0.154 (1) | 0.599 |
| Greedy TS | TS > 0.3 (1.800) | tenure > 21.5 (3.286) | −0.500 (4) · 0 (0) · +0.667 (6) · −0.286 (2) | 0.566 |
- 1shuffle rows → permutation σ
- 2for i in σ:
- 3 TS[i] = (pos + a·P) / (cnt + a)
- 4F = logit(ȳ); p = σ(F); g = p − y; h = p(1 − p)
- 5for level = 1..depth:
- 6 (j, b) = argmax Σ_leaves G² / (H + λ)
- 7 ask x_j > b in EVERY node of the level
- 8w_leaf = −G_leaf / (H_leaf + λ)
- 9F += η · w[leaf(x)]
- 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).
The algorithm, step by step
CatBoostClassifier.fit
- 1Quantize every numeric feature into at most
border_count(254) bins. Categorical columns with at mostone_hot_max_sizelevels are one-hot encoded; the rest get target statistics. - 2Permute. Draw 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). - 3Start from (0, or the log-odds of the base rate with
boost_from_average). - 4For each tree : pick a permutation; compute and — in
Orderedmode from the prefix model that has not seen row . - 5Grow symmetrically. For level , score each (feature, border) pair over all current leaves, add random noise scaled by
random_strength, and apply the best pair to every node. - 6Leaves. Set (refined by a few Newton iterations) and update on every permutation's model.
- 7Predict with full-data statistics for every category, comparisons per tree to form a bit index, sum the leaves, apply (or softmax for multiclass).
Complexity. Computing ordered statistics is one pass per permutation and categorical feature, . A tree level costs about histogram updates plus score evaluations for borders, so a tree is ; Ordered boosting multiplies the gradient work by a small constant (logarithmic number of prefix models). Prediction is comparisons and is very cache- and SIMD-friendly, which is why CatBoost models are fast to serve.
Variants, hyperparameters and tuning
| Parameter | Default | Effect |
|---|---|---|
learning_rate, iterations | auto, 1000 | η scales each tree. Lower η + more trees is smoother; use eval_set with early_stopping_rounds to pick the count |
depth | 6 | number of shared questions → 2^d leaves and interactions up to order d. 4–10 is the useful range |
l2_leaf_reg | 3 | λ in −G/(H+λ): larger shrinks leaves and lowers the score of splits that create low-Hessian (confident or small) leaves |
boosting_type | Plain (here) | Ordered removes prediction shift; slower, most useful on small data |
one_hot_max_size | 2 | categoricals with at most this many levels are one-hot encoded instead of target-encoded |
simple_ctr / priors | Borders (P = 0, 0.5, 1) + Counter | which statistics are built per categorical; more priors = more candidate columns |
max_ctr_complexity | — | how many categoricals may be combined into one feature combination |
random_strength | 1 | noise added to split scores; decorrelates trees, set 0 for reproducing hand calculations |
bootstrap_type | MVS | row sampling per tree (Bayesian, Bernoulli, MVS, No) |
auto_class_weights | None | Balanced / SqrtBalanced reweight rare classes in g and h |
grow_policy | SymmetricTree | Depthwise or Lossguide give ordinary (non-oblivious) trees, closer to XGBoost / LightGBM |
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, tunedepth(4–10) andl2_leaf_reg(1–10) - Small data
- try
boosting_type="Ordered"and more permutations; compare on a validation set - Imbalanced
- use
auto_class_weightsorscale_pos_weight, and judge with log-loss / PR-AUC, not accuracy - Time-ordered rows
- sort by time and set
has_time=Trueso "earlier" means the real past
In code
1import numpy as np23plan = 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)78def 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) + 115 return out1617def full_ts(cat, y, c): # used at prediction time: all training rows18 m = cat == c19 return (y[m].sum() + A * PRIOR) / (m.sum() + A)2021def 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 continue31 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 = best36 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)4142def leaf_index(splits, x):43 k = 044 for j, t in splits: # the same question on every level: just build a binary number45 k = 2 * k + int(x[j] > t)46 return k4748sigmoid = lambda f: 1 / (1 + np.exp(-f))49logloss = lambda f: -np.mean(y * np.log(sigmoid(f)) + (1 - y) * np.log(1 - sigmoid(f)))5051def 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 Hessian56 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, F6061ts = 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 months69f = 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))1ordered TS: [0.5 0.5 0.5 0.75 0.25 0.75 0.5 0.375 0.8333 0.16672 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.59936new customer: TS 0.9 leaf 3 P(churn) = 0.5192750 trees: train log-loss 0.0776 | new customer P(churn) = 0.85411import numpy as np, pandas as pd2from catboost import CatBoostClassifier3from sklearn.metrics import log_loss45df = 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]})1112# 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))1920# 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()])))11 tree, raw scores: [ 0.2222 -0.2941 0.2222 0.2222 0.2222 -0.2941 -0.2941 0.2222 0.22222 -0.2941 -0.2941 0.0769]31 tree, Basic 14 months: P(churn) = 0.51924Plain | 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}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 , with Newton leaves — the same core as XGBoost.
- ✓Trees are symmetric: one question per level, questions and 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_regand learning rate with early stopping, and judge only on held-out data.