# CatBoost

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

Source: https://www.mlfoundry.in/learn/catboost  
Section: ML Algorithms › Supervised · Classification  
Level: advanced · 17 min read · updated 2026-10-07

**CatBoost:** (Yandex, 2017) is a gradient-boosted tree ensemble that outputs a log-odds score $F(x)=F_0+\eta\sum_m f_m(x)$ and a probability $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.

- **Task:** Classification: binary (`Logloss`, `CrossEntropy`) and multiclass (`MultiClass`, softmax); the same machinery also does regression and ranking
- **Input → output:** numeric **and raw categorical** features $x$ → log-odds $F(x)$ → probability $\sigma(F(x))$
- **Learns:** $M$ oblivious trees — $d$ (feature, border) pairs and $2^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^{\ell}$ current leaves, roughly $O(d\cdot n\cdot p)$ per tree, plus one pass per permutation to compute the statistics
- **Prediction:** $d$ comparisons per tree, packed into a $d$-bit leaf index — $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 $y$ is inside its own encoding.

The leak is worst exactly where categories are rare. A merchant that appears once gets encoding $\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 $x$ and a 500-level category that carries **no signal at all**:

scikit-learn GradientBoostingClassifier (200 trees, depth 3) given $x$ plus one encoding of the noise category (prior = training base rate, $a=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.

| 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 $i$ are computed by trees that were fit to row $i$ — 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 $d$-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 $\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\in\{0, 0.5, 1\}$ with $a=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-$d$ tree whose $2^\ell$ nodes on level $\ell$ all ask the same question $x_j>b$. It has $d$ questions and $2^d$ leaves
- **Leaf index:** the $d$ answers read as a binary number $k=\sum_\ell b_\ell 2^{d-\ell}$; the prediction is a table lookup $w_k$
- **Prediction shift:** the bias from computing row $i$'s gradient with a model that already saw $y_i$
- **Ordered boosting:** computing row $i$'s gradient with a model fit only to rows before $i$ 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 $c_i$ the category of row $i$. Using only rows earlier in $\sigma$:

$$
\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}
$$

- $\hat x_i$: the number that replaces category $c_i$ for row $i$
- $\sigma(j)<\sigma(i)$: row $j$ comes before row $i$ in the permutation
- $[c_j=c_i]$: 1 if row j has the same category, else 0
- $y_j\in\{0,1\}$: label of row j (for multiclass: one statistic per class)
- $P,\ a$: prior value and its weight in pseudo-rows

The key property: $\hat x_i$ does not depend on $y_i$, so $\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 $n_c$ rows it moves by $1/(n_c+a)$ toward $y_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 $P$, and a row with $k$ earlier rows is pulled toward $P$ by weight $a/(k+a)$. At prediction time the statistic uses **all** training rows of the category (an unseen category gets $P$).

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

$$
\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)
$$

- $g_i$: gradient: negative for a churner whose p is too low, positive for a stayer
- $h_i$: Hessian: largest (0.25) when $p=0.5$, tiny when the model is already confident

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

$$
\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}
$$

- $G_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
- $w_k^*$: the Newton step for leaf k; the model then adds η·w

Setting the derivative $G_k+(H_k+\lambda)w_k$ to zero gives $w_k^*$; plugging it back gives a loss reduction of $\tfrac12 G_k^2/(H_k+\lambda)$, so the split that maximizes $\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^\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.

$$
f_m(x)=w_{k(x)},\qquad k(x)=\sum_{\ell=1}^{d}\big[x_{j_\ell}>b_\ell\big]\,2^{d-\ell}
$$

- $(j_\ell,b_\ell)$: feature and border of level $\ell$ — one pair per level, not per node
- $k(x)$: leaf index built from the d yes/no answers

**Ordered boosting.** Plain boosting computes $g_i=p_i-y_i$ with a model $F^{(m-1)}$ that was itself fit on row $i$, so $g_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 $M_{i}$ for each prefix of $\sigma$ and uses $g_i=\sigma\big(M_{\sigma(i)-1}(x_i)\big)-y_i$: the gradient of row $i$ 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 $n$ models. The **learning rate** $\eta$ scales every tree; **depth** $d$ is the number of shared questions and caps interaction order at $d$; **random_strength** adds noise to split scores (shrinking as training proceeds) to decorrelate trees.

> **Why symmetric trees regularize:** A normal depth-$d$ tree can ask up to $2^d-1$ different questions; an oblivious tree asks only $d$. Each question must be useful *on average across every branch*, so the tree cannot carve out a tiny region to memorize a few rows. That makes each tree weaker but much less variable, and CatBoost compensates with more trees. It also makes the model a lookup table: in the worked example below, a single border on TS is forced into the left half where it changes nothing — leaving one leaf empty.

## 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 $F_0=\log\frac{6}{6}=0$ and every row starts at $p=0.5$, $g=\pm0.5$, $h=0.25$. Settings: prior $P=0.5$, $a=1$, depth 2, $\lambda=3$, $\eta=0.5$. At the end we score a new customer: **Basic, 14 months**.

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.

| 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)**

1. **Target statistics.** Row 4 is the second Basic row; the one before it churned, so $\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$. The first row of each plan gets the prior 0.5.
2. **Gradients.** $F_0=0\Rightarrow p=0.5$: churners have $g=0.5-1=-0.5$, stayers $g=+0.5$, all $h=0.25$. The root holds $G=0$, $H=3$, score $0$.
3. **Level 1.** Tenure $>9.5$ splits the rows into $\{1,3,4,5,8,9\}$ ($G=-2,\ H=1.5$) and $\{2,6,7,10,11,12\}$ ($G=+2,\ H=1.5$): score $\tfrac{4}{4.5}+\tfrac{4}{4.5}=1.778$. The best TS border, $0.3125$, scores only $\tfrac{1.5^2}{3.75}+\tfrac{1.5^2}{5.25}=1.029$. → **tenure > 9.5**.
4. **Level 2 (shared).** Now each candidate is scored over all four leaves at once. TS $>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 $\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. **Leaf values** $w=-G/(H+\lambda)$: leaf 0 (short, low TS; 5 churners + row 5) $=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$; leaf 3 (row 12) $=0.5/3.25=+0.154$.
6. **Update** $F\leftarrow F+0.5\,w$: leaf-0 rows go to $p=\sigma(0.222)=0.555$, leaf-2 rows to $\sigma(-0.294)=0.427$, row 12 to $\sigma(0.077)=0.519$. Training log-loss $0.693\to0.599$.
7. **Predict** Basic, 14 months. At prediction time its TS uses all four Basic rows: $(4+0.5)/(4+1)=0.900$. Answers: tenure $14>9.5$ → 1, TS $0.9>0.854$ → 1, so leaf $k=1\cdot2+1=3$ and $P(\text{churn})=\sigma(0.5\cdot0.154)=$ **0.519** after one tree (0.854 after 50 trees of the from-scratch code below).

The same first tree with ordered vs greedy statistics ($\lambda=3$, $\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.

| 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 |

> Figure: 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 ordered statistic is noisy — on purpose:** Row 8 is a Plus churner but gets TS 0.375, lower than row 6, a Plus stayer (0.750): early rows see few neighbours. That noise is the price of honesty, and it is why CatBoost averages over several permutations and why the prior matters. With 12 rows it is visible; with thousands per category it vanishes, while the greedy leak does not.

## The algorithm, step by step

**CatBoostClassifier.fit**

1. **Quantize** 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. **Permute.** Draw $s$ 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. **Start** from $F_0$ (0, or the log-odds of the base rate with `boost_from_average`).
4. **For each tree** $m=1\ldots M$: pick a permutation; compute $g_i=p_i-y_i$ and $h_i=p_i(1-p_i)$ — in `Ordered` mode from the prefix model that has not seen row $i$.
5. **Grow symmetrically.** For level $\ell=1\ldots d$, score each (feature, border) pair over all $2^{\ell-1}$ current leaves, add random noise scaled by `random_strength`, and apply the best pair to every node.
6. **Leaves.** Set $w_k=-G_k/(H_k+\lambda)$ (refined by a few Newton iterations) and update $F\leftarrow F+\eta\,w_{k(x)}$ on every permutation's model.
7. **Predict** with full-data statistics for every category, $d$ 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)$. A tree level costs about $O(n\cdot p)$ histogram updates plus $O(2^\ell\cdot p\cdot B)$ score evaluations for $B$ borders, so a tree is $O(d\,n\,p)$; `Ordered` boosting multiplies the gradient work by a small constant (logarithmic number of prefix models). Prediction is $O(Md)$ comparisons and is very cache- and SIMD-friendly, which is why CatBoost models are fast to serve.

## Variants, hyperparameters and tuning

The knobs that matter for classification, and what they do. Defaults are from catboost 1.2.10.

| 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, 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
import numpy as np

plan   = np.array("Basic Pro Plus Basic Pro Plus Plus Plus Basic Pro Pro Basic".split())
tenure = np.array([8, 16, 2, 9, 6, 23, 29, 7, 1, 10, 19, 20], float)
y      = np.array([1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1], float)
PRIOR, A = 0.5, 1.0                      # TS = (positives + A*PRIOR) / (count + A)

def ordered_ts(cat, y):
    """Rows are already in permutation order: each row sees only the rows before it."""
    pos, cnt, out = {}, {}, np.empty(len(y))
    for i, c in enumerate(cat):
        out[i] = (pos.get(c, 0) + A * PRIOR) / (cnt.get(c, 0) + A)
        pos[c] = pos.get(c, 0) + y[i]
        cnt[c] = cnt.get(c, 0) + 1
    return out

def full_ts(cat, y, c):                  # used at prediction time: all training rows
    m = cat == c
    return (y[m].sum() + A * PRIOR) / (m.sum() + A)

def oblivious_tree(X, g, h, depth, lam):
    """One (feature, border) per level, shared by every node; Newton leaf values."""
    idx, splits = np.zeros(len(g), int), []
    for _ in range(depth):
        best = (-np.inf, None, None)
        for j in range(X.shape[1]):
            v = np.unique(X[:, j])
            for t in (v[:-1] + v[1:]) / 2:
                if (j, t) in splits:
                    continue
                leaf = 2 * idx + (X[:, j] > t)
                score = sum(g[leaf == k].sum() ** 2 / (h[leaf == k].sum() + lam) for k in np.unique(leaf))
                if score > best[0] + 1e-12:
                    best = (score, j, t)
        _, j, t = best
        splits.append((j, t))
        idx = 2 * idx + (X[:, j] > t)
    G = np.bincount(idx, g, 2 ** depth)
    H = np.bincount(idx, h, 2 ** depth)
    return splits, -G / (H + lam)

def leaf_index(splits, x):
    k = 0
    for j, t in splits:                  # the same question on every level: just build a binary number
        k = 2 * k + int(x[j] > t)
    return k

sigmoid = lambda f: 1 / (1 + np.exp(-f))
logloss = lambda f: -np.mean(y * np.log(sigmoid(f)) + (1 - y) * np.log(1 - sigmoid(f)))

def fit(X, y, rounds, depth=2, lr=0.5, lam=3.0):
    F, trees = np.zeros(len(y)), []      # F0 = log-odds of the base rate (6/12 -> 0)
    for _ in range(rounds):
        p = sigmoid(F)
        g, h = p - y, p * (1 - p)        # log-loss gradient and Hessian
        splits, w = oblivious_tree(X, g, h, depth, lam)
        F += lr * w[[leaf_index(splits, x) for x in X]]
        trees.append((splits, w))
    return trees, F

ts = ordered_ts(plan, y)
X = np.c_[tenure, ts]
print("ordered TS:", np.round(ts, 4))
trees, F = fit(X, y, rounds=1)
print("tree 1 splits:", [(int(j), round(float(t), 4)) for j, t in trees[0][0]])
print("tree 1 leaves:", np.round(trees[0][1], 4) + 0.0)
print("log-loss 0.6931 ->", round(logloss(F), 4))
x_new = np.array([14, full_ts(plan, y, "Basic")])          # Basic plan, 14 months
f = sum(0.5 * w[leaf_index(s, x_new)] for s, w in trees)
print("new customer: TS", round(x_new[1], 4), "leaf", leaf_index(trees[0][0], x_new), "P(churn) =", round(sigmoid(f), 4))
trees, F = fit(X, y, rounds=50)
f = sum(0.5 * w[leaf_index(s, x_new)] for s, w in trees)
print("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
ordered TS: [0.5    0.5    0.5    0.75   0.25   0.75   0.5    0.375  0.8333 0.1667
 0.125  0.875 ]
tree 1 splits: [(0, 9.5), (1, 0.8542)]
tree 1 leaves: [ 0.4444  0.     -0.5882  0.1538]
log-loss 0.6931 -> 0.5993
new customer: TS 0.9 leaf 3 P(churn) = 0.5192
50 trees: train log-loss 0.0776 | new customer P(churn) = 0.8541
```

Output of the script above.

```python
import numpy as np, pandas as pd
from catboost import CatBoostClassifier
from sklearn.metrics import log_loss

df = pd.DataFrame({
    "plan": "Basic Pro Plus Basic Pro Plus Plus Plus Basic Pro Pro Basic".split(),
    "tenure": [8, 16, 2, 9, 6, 23, 29, 7, 1, 10, 19, 20],
    "churn": [1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1],
})
new = pd.DataFrame({"plan": ["Basic"], "tenure": [14]})

# 1) Reproduce the hand-built first tree: feed the ordered TS as a number, one Newton step.
X = 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]})
one = CatBoostClassifier(iterations=1, depth=2, learning_rate=0.5, l2_leaf_reg=3, score_function="L2",
                         leaf_estimation_iterations=1, random_strength=0, bootstrap_type="No", verbose=0)
one.fit(X, df.churn)
print("1 tree, raw scores:", np.round(one.predict(X, prediction_type="RawFormulaVal"), 4))
print("1 tree, Basic 14 months: P(churn) =", round(float(one.predict_proba(pd.DataFrame({"tenure": [14], "ts": [0.9]}))[0, 1]), 4))

# 2) The normal way: give CatBoost the raw category.
for mode in ["Plain", "Ordered"]:
    m = CatBoostClassifier(iterations=200, depth=2, learning_rate=0.1, boosting_type=mode,
                           one_hot_max_size=1, random_seed=0, verbose=0)
    m.fit(df[["plan", "tenure"]], df.churn, cat_features=["plan"])
    p = m.predict_proba(df[["plan", "tenure"]])[:, 1]
    print(mode, "| train log-loss", round(log_loss(df.churn, p), 3), "| Basic 14 months -> P(churn) =",
          round(float(m.predict_proba(new)[0, 1]), 3),
          "| 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
1 tree, raw scores: [ 0.2222 -0.2941  0.2222  0.2222  0.2222 -0.2941 -0.2941  0.2222  0.2222
 -0.2941 -0.2941  0.0769]
1 tree, Basic 14 months: P(churn) = 0.5192
Plain | train log-loss 0.05 | Basic 14 months -> P(churn) = 0.8 | importances {'plan': 33.8, 'tenure': 66.2}
Ordered | 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.

> **Why the library needed so many switches to match:** `score_function="L2"` uses the Newton score derived above (default is Cosine), `leaf_estimation_iterations=1` takes a single Newton step (default is 10 for Logloss), `random_strength=0` removes split noise and `bootstrap_type="No"` removes row sampling. Base score stays 0 because `boost_from_average` defaults to False for Logloss.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **Encoding categories yourself throws the advantage away:** If you target-encode with pandas before calling CatBoost, the leak is already baked in and ordered statistics cannot undo it. Pass raw string or integer columns and list them in `cat_features` (integers not listed there are treated as numbers with an order they do not have).

> **A random order is wrong for time series:** Ordered statistics assume rows are exchangeable. With time-stamped data, a random permutation lets the past see the future — sort by time and set `has_time=True`, and validate on a later time window.

> **Do not judge it by training loss:** Ordered statistics and ordered boosting deliberately make the training fit look *worse* (0.599 vs 0.566 in the example, AUC 0.833 vs 0.943 in the leak experiment). Compare models only on held-out data.

**Question:** 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…

- A. 0.333
- B. 0.500
- C. 0.625
- D. 0.667

**Answer:** B. 0.500 — $(1+0.5)/(2+1)=1.5/3=0.5$. The row's own label is not used, whatever it is.

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

- A. −0.5
- B. 0.25
- C. 0.5
- D. 1.0

**Answer:** C. 0.5 — $g=-0.5$ for each churner and $+0.5$ for the stayer, so $G=-1$; $h=0.25$ each, so $H=1$. $w=1/(1+1)=0.5$, pushing the log-odds toward churn.

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

- A. 63 questions, 64 leaves
- B. 6 questions, 64 leaves
- C. 6 questions, 12 leaves
- D. 64 questions, 6 leaves

**Answer:** B. 6 questions, 64 leaves — One (feature, border) per level, shared by all nodes: 6 questions. Each of the $2^6=64$ answer patterns is a leaf, indexed by the 6-bit number of answers.

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

- A. Rare categories are dropped by the encoder
- B. A row's own label makes up a large share of its category's average, so the feature nearly copies y
- C. Rare categories get the prior and lose all information
- D. Trees cannot split on rare values

**Answer:** B. A row's own label makes up a large share of its category's average, so the feature nearly copies y — With $n_c$ rows the row's own label has weight $1/(n_c+a)$ in its encoding; for $n_c=1$ the encoding is $(y_i+aP)/(1+a)$ — a function of the answer. On test data that information is absent.

**Key points**

- 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-y$, $h=p(1-p)$ with Newton leaves $w=-G/(H+\lambda)$ — the same core as XGBoost.
- Trees are symmetric: one question per level, $d$ questions and $2^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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
