# CatBoost regression

> Gradient boosting with symmetric trees and ordered boosting, which stops categorical encodings from leaking the target.

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

**CatBoost regression:** predicts a number as a constant plus a sum of small trees, $\hat y = F_0+\eta\sum_m f_m(x)$, like any gradient-boosted model. What is special is *what the trees see* and *how they are shaped*: every categorical feature is replaced by an **ordered target statistic** — the average target of the *earlier* rows with the same category in a random permutation — and every tree is **symmetric** (oblivious): one question per level, shared by all nodes on that level.

- **Task:** Regression: RMSE (squared error) by default; also MAE, Quantile, Huber, MAPE, Poisson, Tweedie, RMSEWithUncertainty
- **Input → output:** numeric **and raw categorical** features $x$ → real number $\hat y=F_0+\eta\sum_{m=1}^M f_m(x)$
- **Learns:** $M$ oblivious trees: $d$ (feature, border) pairs and $2^d$ leaf values each, plus per-category target statistics stored with the model
- **Training:** features quantized into $\le 254$ borders; per tree about $O(d\cdot n\cdot p)$ for $p$ features — slower per tree than LightGBM on numeric data, competitive once categories are involved
- **Prediction:** $O(M\cdot d)$: each tree is $d$ comparisons that form a $d$-bit leaf index — branch-free and very fast
- **Key hyperparameters:** `iterations`, `learning_rate` (η), `depth` (default 6), `l2_leaf_reg` (λ, default 3), `random_strength`, `bagging_temperature` / `subsample`, `one_hot_max_size`, `boosting_type` (Plain / Ordered)
- **Assumes:** a differentiable loss; no scaling; categories need no manual encoding; the fit is piecewise constant and axis-aligned, so no extrapolation beyond the training targets

## The problem

Tabular regression data is full of categories: district, product id, store, device, postcode. Trees need numbers. **One-hot encoding** works for a handful of levels but explodes for thousands, and each indicator column carries almost no signal on its own. The popular alternative is **target encoding**: replace each category by the mean target of its rows. For a rent model, "district = West" becomes "average West rent".

Target encoding computed on the training rows **leaks the target**. If row $i$'s own rent is part of the average that replaces its district, the encoded feature contains a piece of $y_i$. For a category with a single row the encoding *is* a rescaled $y_i$. The trees happily split on it, the training error drops, and the model fails on new data, where the encoding has no such piece. The CatBoost paper (Prokhorenkova et al., 2018) calls this **prediction shift**: the distribution of a feature at training time differs from its distribution at test time.

Boosting itself has the same flaw in a quieter form. The residuals that tree $m$ is fitted to are computed by a model that was trained *on those same rows*, so they are systematically smaller than the residuals the model will make on fresh rows. CatBoost's answer to both problems is the same trick: **order the data randomly and let each row use only the rows before it**.

A synthetic check (script-verified): 1000 training rows, $y=3x+\varepsilon$ with $\varepsilon\sim N(0,1)$, plus a 400-level category that carries **no signal**. Each scikit-learn GBM gets $x$ and one encoding of the category (200 trees, depth 3); test rows use full-training statistics. The irreducible error is 1.0.

| Model | Train RMSE | Test RMSE | corr(encoding, y) on train |
| --- | --- | --- | --- |
| GBM on $x$ only | 0.801 | 1.041 | — |
| GBM + greedy target encoding | **0.656** | **1.192** | 0.621 |
| GBM + ordered target statistic | 0.774 | 1.053 | 0.052 |
| CatBoost, Plain (raw category) | 0.919 | 1.012 | — |
| CatBoost, Ordered (raw category) | 0.927 | 1.008 | — |

The greedy encoding looks like the *best* model on the training set and is the *worst* on the test set: a pure-noise category correlates 0.621 with the target once each row's own target is inside its encoding. The ordered statistic is honest (0.052), and CatBoost's own pipeline does best of all.

## The idea

Imagine the training rows arriving one at a time, in a random order, like a stream. When row $i$ arrives, you may summarise only what you have already seen. Its district encoding is the average rent of the **earlier** rows from the same district, smoothed toward a prior. Row $i$'s own rent was never used, so the feature is exactly as informative as it will be for a brand-new flat. The first rows of each district get mostly the prior (noisy but unbiased); later rows get sharper estimates.

The trees are deliberately simple: a **symmetric tree** of depth $d$ asks the *same* question of every node on a level, so it is really a list of $d$ yes/no tests and a table of $2^d$ leaf values. That is a strong regularizer (one split must be good for every branch at once), and it turns prediction into computing a $d$-bit binary number.

**Vocabulary**

- **Target statistic (TS / CTR):** a number that replaces a category value, computed from the targets of rows with that value — e.g. a smoothed mean rent. CatBoost's docs call them CTRs.
- **Prior p, weight a:** the value a TS falls back to when a category has few rows, and how many "virtual rows" it is worth. Here $p$ is the mean target and $a=1$.
- **Greedy TS:** a TS computed from all training rows of the category, including the row being encoded — leaks the target
- **Leave-one-out TS:** all rows of the category except the row itself — still leaks, in reverse
- **Permutation σ:** a random ordering of the training rows; $\sigma(i)$ is row $i$'s position. CatBoost draws several.
- **Ordered TS:** the TS of row $i$ computed only from rows that come before it in $\sigma$
- **Prediction shift:** the gap between a feature's (or residual's) distribution on training rows and on new rows, caused by reusing a row's own target
- **Ordered boosting:** computing row $i$'s residual with a model that never saw row $i$ (only rows before it in $\sigma$) — `boosting_type="Ordered"`
- **Oblivious (symmetric) tree:** a tree in which every node at depth $k$ uses the same feature and border; $d$ tests, $2^d$ leaves
- **Border:** a candidate threshold. Features are quantized into at most 254 borders by default (`border_count`).
- **Feature combination:** a new categorical feature formed by joining categories (e.g. district × building type), encoded with its own TS

## The math

**Target statistics.** For a categorical feature with value $c_i$ in row $i$, the three candidate encodings differ only in which rows they average:

$$
\hat x_i^{\text{greedy}}=\frac{\sum_{j=1}^{n}[c_j=c_i]\,y_j+a\,p}{\sum_{j=1}^{n}[c_j=c_i]+a}\qquad \hat x_i^{\text{ordered}}=\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 row $i$'s category
- $[c_j=c_i]$: 1 if row $j$ has the same category as row $i$, else 0
- $y_j$: target (here: rent) of row j
- $p$: prior: the value an unseen category gets (here the mean target)
- $a>0$: prior weight: how many pseudo-rows the prior is worth
- $\sigma(j)<\sigma(i)$: row $j$ comes before row $i$ in the random permutation

**Why greedy leaks.** If category $c_i$ has $n_c$ rows, the greedy TS contains $y_i$ with weight $1/(n_c+a)$. For a category seen once, $\hat x_i=(y_i+ap)/(1+a)$ — a straight line in $y_i$, so a tree can recover the target exactly. On a new row of that category the encoding is a fixed number with no link to the new target. **Why leave-one-out leaks.** Removing the row gives $\hat x_i=(S_c-y_i+ap)/(n_c-1+a)$ with $S_c$ the category's target sum. Within one category this is a *decreasing* linear function of $y_i$: the row with the highest target always gets the lowest encoding, and one split on $\hat x$ separates them perfectly. **Why ordered does not leak.** $\hat x_i$ is a function of $y_j$ for rows *before* $i$ only, so $\mathbb E[\hat x_i\mid y_i]$ does not depend on $y_i$ — the same property a test row has.

> **Ordered TS is online learning in disguise:** It is exactly what an online system would know if the rows arrived in order $\sigma$: each encoding is computed from the past only. The price is variance — early rows in each category get poor estimates — which CatBoost reduces by drawing several permutations and using different ones for different trees.

**The boosting step for squared error.** Start from $F_0=\bar y$. At round $m$ the loss and its derivatives for row $i$ are

$$
\ell_i=\tfrac12\big(y_i-F_{m-1}(x_i)\big)^2,\qquad g_i=\frac{\partial \ell_i}{\partial F}=-(y_i-F_{m-1}(x_i))=-r_i,\qquad h_i=\frac{\partial^2 \ell_i}{\partial F^2}=1
$$

- $F_{m-1}(x_i)$: current prediction for row i
- $r_i$: residual: what the next tree should add
- $g_i,\ h_i$: gradient and hessian; for squared error the hessian is 1, so Newton and gradient leaf steps coincide

A tree assigns every row in leaf $j$ the same value $w_j$. Adding it to the predictions and penalising large values with $\tfrac{\lambda}{2}w_j^2$, the objective for leaf $j$ is

$$
\mathcal L_j(w)=\sum_{i\in j}\tfrac12(r_i-w)^2+\tfrac{\lambda}{2}w^2\;\Rightarrow\;\frac{d\mathcal L_j}{dw}=-\sum_{i\in j}r_i+(n_j+\lambda)w=0\;\Rightarrow\; w_j^*=\frac{G_j}{n_j+\lambda},\quad G_j=\sum_{i\in j}r_i
$$

- $n_j$: number of training rows in leaf j
- $G_j$: sum of residuals in leaf j (= minus the gradient sum)
- $\lambda$: `l2_leaf_reg` (default 3): shrinks small leaves toward 0

With $\lambda=0$ the leaf value is the mean residual; with $\lambda>0$ a leaf of 1 row is shrunk to a quarter of its residual (at $\lambda=3$), a leaf of 100 rows hardly at all. Plugging $w^*$ back in, the loss *saved* by leaf $j$ is $\tfrac12 G_j^2/(n_j+\lambda)$, so a tree structure is scored by

$$
\text{score}(\text{tree})=\sum_{j=1}^{2^d}\frac{G_j^2}{n_j+\lambda},\qquad \text{leaf}(x)=\sum_{k=1}^{d}2^{\,d-k}\,\big[x_{f_k}>b_k\big]
$$

- $(f_k,b_k)$: feature and border of level $k$ — one pair per level, shared by all $2^{k-1}$ nodes on it
- $[x_{f_k}>b_k]$: bit $k$ of the leaf index: 1 = "no, go right"
- $2^d$: number of leaves of a depth-d symmetric tree

**Growing a symmetric tree** is greedy over levels: at level $k$, try every (feature, border) pair, apply it to *all* current nodes at once, and keep the pair with the highest score. A normal tree picks the best split per node; the oblivious tree picks the split that is best *summed over every node of the level*, even if it is useless for some of them. This is also why $\lambda$ changes the structure, not just the leaf values: the denominator $n_j+\lambda$ makes splits that isolate one or two rows score less. (CatBoost's default CPU score is `Cosine`, a normalised variant of this L2 score; `score_function="L2"` gives exactly the formula above.)

**Ordered boosting.** For the residuals, the same no-peeking rule applies: $r_i=y_i-M_{\sigma(i)-1}(x_i)$, where $M_{k}$ is a model trained on the first $k$ rows of $\sigma$ only. Keeping $n$ models would be absurd, so CatBoost keeps supporting models for prefixes of exponentially growing length (1, 2, 4, 8, …) and shares the tree *structure* between them; only leaf values differ. The final model's leaf values are computed normally from all rows. In `Plain` mode — the default in current versions — residuals are ordinary, but **categorical features still get ordered target statistics**.

**How each hyperparameter enters the math**

- **learning_rate η:** scales every tree: $F_m=F_{m-1}+\eta f_m$. Smaller η needs more iterations but averages more trees, which generalises better. Chosen automatically from data size if not set.
- **depth d:** $2^d$ leaves and interactions of up to $d$ features per tree. Default 6 (64 leaves); 4–10 is the useful range.
- **l2_leaf_reg λ:** denominator $n_j+\lambda$ in both the leaf value and the split score; larger → smaller steps, fewer splits that isolate tiny groups.
- **random_strength:** adds random noise (scaled by this value and shrinking over iterations) to split scores, so near-tied splits are chosen randomly — a regularizer against greedy over-commitment.
- **a, p (CTR priors):** pull rare categories toward the prior; a larger $a$ means a category needs more rows before its TS departs from $p$.
- **one_hot_max_size:** categories with at most this many levels are one-hot encoded instead of target-encoded

## Worked example: rent by district and size

Twelve flats, one categorical feature (district) and one numeric feature (size in m²). Rent is in hundreds of euros per month. Assume the random permutation drawn is simply the row order shown. Mean rent $p=\bar y=168/12=14$, and the prior weight is $a=1$.

Training data, in permutation order. A new flat, South and 70 m², will be priced at the end.

| # | District | Size (m²) | Rent (×100 €) |
| --- | --- | --- | --- |
| 1 | North | 45 | 9 |
| 2 | South | 60 | 14 |
| 3 | North | 70 | 15 |
| 4 | East | 50 | 10 |
| 5 | South | 40 | 11 |
| 6 | West | 80 | 22 |
| 7 | North | 55 | 12 |
| 8 | East | 65 | 13 |
| 9 | South | 75 | 18 |
| 10 | West | 60 | 19 |
| 11 | East | 35 | 7 |
| 12 | North | 85 | 18 |

**Step 1 — ordered target statistics**

1. Row 1 (North) is the first North row: no history, so $\hat x_1=(0+1\cdot14)/(0+1)=14$. The same holds for the first South (row 2), East (row 4) and West (row 6) rows: all get the prior, 14.
2. Row 3 (North) has one earlier North row, rent 9: $\hat x_3=(9+14)/(1+1)=11.5$.
3. Row 7 (North) sees rows 1 and 3: $\hat x_7=(9+15+14)/(2+1)=12.667$. Row 12 sees rows 1, 3 and 7: $(9+15+12+14)/4=12.5$.
4. East: row 8 sees row 4 → $(10+14)/2=12$; row 11 sees rows 4 and 8 → $(10+13+14)/3=12.333$. South: row 5 → $(14+14)/2=14$; row 9 → $(14+11+14)/3=13$. West: row 10 → $(22+14)/2=18$.
5. For comparison, the greedy TS gives every North row $(54+14)/5=13.6$ and both West rows $(41+14)/3=18.333$ — each including its own rent.

The three encodings and the first residuals $r_i=y_i-14$. Correlation with rent over the 12 rows: greedy 0.769, leave-one-out 0.441, ordered 0.284. Inside North, leave-one-out orders the rows exactly backwards (rents 9, 15, 12, 18 → TS 14.75, 13.25, 14.00, 12.50).

| # | District | Earlier same-district rents | Ordered TS | Greedy TS | LOO TS | Residual r |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | North | — | 14.000 | 13.600 | 14.750 | −5 |
| 2 | South | — | 14.000 | 14.250 | 14.333 | 0 |
| 3 | North | 9 | 11.500 | 13.600 | 13.250 | +1 |
| 4 | East | — | 14.000 | 11.000 | 11.333 | −4 |
| 5 | South | 14 | 14.000 | 14.250 | 15.333 | −3 |
| 6 | West | — | 14.000 | 18.333 | 16.500 | +8 |
| 7 | North | 9, 15 | 12.667 | 13.600 | 14.000 | −2 |
| 8 | East | 10 | 12.000 | 11.000 | 10.333 | −1 |
| 9 | South | 14, 11 | 13.000 | 14.250 | 13.000 | +4 |
| 10 | West | 22 | 18.000 | 18.333 | 18.000 | +5 |
| 11 | East | 10, 13 | 12.333 | 11.000 | 12.333 | −7 |
| 12 | North | 9, 15, 12 | 12.500 | 13.600 | 12.500 | +4 |

**Step 2 — one symmetric tree of depth 2 on (size, ordered TS), λ = 3, η = 0.3**

1. **Start.** $F_0=14$; the residuals sum to 0, so the root's score is $0^2/(12+3)=0$. RMSE of $F_0$: 4.340.
2. **Level 1.** Try every border on both features. Best: **size ≤ 57.5** — left rows {1, 4, 5, 7, 11} with $G=-21$, $n=5$; right rows {2, 3, 6, 8, 9, 10, 12} with $G=+21$, $n=7$. Score $\tfrac{441}{5+3}+\tfrac{441}{7+3}=55.125+44.1=99.225$ (runner-up: size ≤ 52.5, 84.39).
3. **Level 2.** Now each candidate is applied to *both* halves. Best: **TS ≤ 12.17**. On the left half it separates nothing (all five left rows have TS above 12.17, leaf 00 is empty); on the right it isolates rows 3 and 8 ($G=+1-1=0$) from rows {2, 6, 9, 10, 12} ($G=21$). Score $0+55.125+0+\tfrac{441}{5+3}=110.25$. Next best: size ≤ 72.5 at 101.36.
4. **λ changed the choice.** TS ≤ 12.42 would also move row 11 (TS 12.333, $r=-7$) into its own leaf, which is what plain least squares wants ($\lambda=0$). With $\lambda=3$ that one-row leaf is worth only $49/4=12.25$, and the total falls to 95.375 — below 110.25.
5. **Leaf values** $w=G/(n+\lambda)$: leaf 00: empty → 0; leaf 01: $-21/8=-2.625$; leaf 10: $0/5=0$; leaf 11: $21/8=2.625$.
6. **Update** $F_1=F_0+0.3\,w$: rows {1, 4, 5, 7, 11} → 13.2125, rows {3, 8} → 14, rows {2, 6, 9, 10, 12} → 14.7875. Training RMSE 4.340 → 3.720.
7. **New flat (South, 70 m²).** At prediction time the TS uses *all* training rows of South: $(14+11+18+1\cdot14)/(3+1)=14.25$. Size 70 > 57.5 → bit 1; TS 14.25 > 12.17 → bit 1; leaf $11_2=3$. Prediction $14+0.3\cdot2.625=$ **14.7875**, i.e. about 1,479 € per month after one tree.

Running 100 such rounds (same TS, depth 2) drives the training RMSE to 0.337 and prices the new flat at 17.87 — that is badly overfitted with only 12 rows, which is why real CatBoost redraws permutations, adds score noise and is normally stopped early on a validation set.

> Figure: The worked example, live. Tab 1: each column is a flat in permutation order; the bar is its rent and the white tick the target statistic the trees will see. Press play to stream the rows: in ordered mode later rows of the same district are greyed out and unused. Switch to greedy or leave-one-out and watch the ticks jump and the correlation with rent rise from 0.284 to 0.769 or 0.441; reshuffle the permutation or change the prior weight a. Tab 2: the depth-2 symmetric tree on (size, TS) with λ = 3 — size ≤ 57.5, then TS ≤ 12.17 drawn across the whole plane, leaves −2.625 / 0 / 2.625, RMSE 4.340 → 3.720, new flat 14.7875. Drag λ to 0 and the second split moves to TS ≤ 12.42 to isolate row 11.

> **One split for the whole level:** In tab 2 the second line spans the full width even though it splits nothing on the left: that is the oblivious constraint. A normal tree would choose a different second question for each half. The constraint costs a little fit per tree, but it makes trees very hard to overfit, makes every tree a 2^d lookup table, and lets CatBoost evaluate a level with one pass over the data.

## The algorithm, step by step

**CatBoost regression (Plain mode, with ordered TS)**

1. **Quantize** every numeric feature into at most `border_count` (254) borders. Categories with at most `one_hot_max_size` levels are one-hot encoded; the rest are left for target statistics.
2. **Draw permutations** $\sigma_1,\dots,\sigma_s$ of the training rows. Set $F_0=\bar y$ (`boost_from_average`).
3. **For each round** $m=1\dots M$: pick a permutation; compute the ordered TS of every categorical feature (and of feature combinations built from splits already used) under it; compute residuals $r_i=y_i-F_{m-1}(x_i)$ — or, in `Ordered` mode, with the supporting model that has not seen row $i$.
4. **Grow a symmetric tree** level by level: for each (feature, border) compute $\sum_j G_j^2/(n_j+\lambda)$ over all $2^k$ nodes, perturb the scores with `random_strength` noise, keep the best pair.
5. **Leaf values** $w_j=G_j/(n_j+\lambda)$ (for losses other than RMSE: a Newton step with the hessians). Update $F_m=F_{m-1}+\eta f_m$.
6. **Stop** after `iterations`, or earlier when the validation metric (RMSE, MAE, R²) has not improved for `early_stopping_rounds`.
7. **Predict:** encode each category with statistics over *all* training rows, compute each tree's $d$-bit leaf index, sum the leaf values.

**Complexity**

- **Per level:** one histogram pass over $n$ rows for each of $p$ features, then $O(2^k\cdot p\cdot B)$ to score $B$ borders
- **Per tree:** about $O(d\cdot n\cdot p)$; ordered TS add $O(n)$ per categorical feature per permutation
- **Ordered boosting:** a constant-factor slowdown (supporting models on growing prefixes), worth it mainly for small and medium datasets
- **Prediction:** $O(M\cdot d)$ comparisons with no branching; vectorizes well on CPU and GPU

## Variants and tuning

Regression losses CatBoost supports out of the box, and when to choose them.

| loss_function | Leaf value aims at | Use when |
| --- | --- | --- |
| `RMSE` (default) | mean of the residuals, shrunk by λ | errors are roughly symmetric; you report RMSE or R² |
| `MAE`, `Quantile:alpha=q` | median / q-quantile of the residuals | outliers or prediction intervals (fit q = 0.1 and 0.9) |
| `Huber:delta=δ` | mean near zero, median for large residuals | mostly Gaussian noise with a few gross errors |
| `Poisson`, `Tweedie:variance_power=ρ` | log-mean of counts / non-negative amounts | counts, insurance claims, sales with many zeros |
| `MAPE` | relative error | targets of very different scales where % error matters |
| `RMSEWithUncertainty` | a mean and a variance per row | you need a predictive standard deviation |

**Practical tuning order**

- **1. Pass categories raw:** list them in `cat_features`; do not one-hot or target-encode yourself — that throws away the ordered statistics
- **2. Early stopping:** set a large `iterations`, an `eval_set`, and `early_stopping_rounds` (e.g. 100); the auto learning rate is usually a decent start
- **3. depth:** try 4, 6, 8. Each extra level doubles the leaves
- **4. l2_leaf_reg:** try 1, 3, 10, 30 — more for small or noisy data
- **5. Randomness:** `random_strength`, `bagging_temperature` (Bayesian bootstrap) or `subsample` (MVS / Bernoulli)
- **6. boosting_type:** `Ordered` for small data (thousands of rows), `Plain` for large; compare on validation

> **What the library actually encodes for regression:** The formulas above use the mean target, as in the paper. For RMSE the CPU library's default `simple_ctr` is `Borders` with `TargetBorderCount=1`: it binarizes the target at one border and encodes each category by the smoothed fraction of rows above it (with priors 0, 0.5 and 1), plus a `Counter` CTR (category frequency). The ordering logic is identical; only the statistic averaged differs. Its sibling articles **XGBoost regression** (G/H gain and λ, γ) and **LightGBM regression** (histograms, leaf-wise growth) cover the shared boosting machinery in more depth.

## In code

```python
import numpy as np

def ordered_ts(cat, y, perm, a=1.0, prior=None):
    """Ordered target statistic: each row sees only the rows before it in perm."""
    prior = y.mean() if prior is None else prior
    s, k, ts = {}, {}, np.empty(len(y))
    for i in perm:
        c = cat[i]
        ts[i] = (s.get(c, 0.0) + a * prior) / (k.get(c, 0) + a)
        s[c] = s.get(c, 0.0) + y[i]
        k[c] = k.get(c, 0) + 1
    return ts, s, k, prior

def full_ts(cat, s, k, prior, a=1.0):
    """For new rows: statistics over the whole training set."""
    return np.array([(s.get(c, 0.0) + a * prior) / (k.get(c, 0) + a) for c in cat])

def leaf_index(X, splits):
    """Oblivious tree: the leaf is a binary number, one bit per level."""
    idx = np.zeros(len(X), dtype=int)
    for j, t in splits:
        idx = 2 * idx + (X[:, j] > t)
    return idx

def fit_oblivious(X, r, depth, lam):
    splits = []
    for _ in range(depth):
        best = (-np.inf, None)
        for j in range(X.shape[1]):
            v = np.unique(X[:, j])
            for t in (v[:-1] + v[1:]) / 2:
                idx = leaf_index(X, splits + [(j, t)])
                G = np.bincount(idx, r, minlength=2 ** (len(splits) + 1))
                n = np.bincount(idx, minlength=2 ** (len(splits) + 1))
                score = (G ** 2 / np.maximum(n + lam, 1e-9)).sum()   # same split for every node
                if score > best[0]:
                    best = (score, (j, t))
        splits.append(best[1])
    idx = leaf_index(X, splits)
    G = np.bincount(idx, r, minlength=2 ** depth)
    n = np.bincount(idx, minlength=2 ** depth)
    return splits, G / np.maximum(n + lam, 1e-9)         # leaf values (0 if empty)

def fit(X, y, rounds=100, depth=2, eta=0.3, lam=3.0):
    F0 = y.mean()
    F = np.full(len(y), F0)
    trees = []
    for _ in range(rounds):
        splits, w = fit_oblivious(X, y - F, depth, lam)  # residual = -gradient of squared error
        F += eta * w[leaf_index(X, splits)]
        trees.append((splits, w))
    return F0, trees

def predict(model, X, eta=0.3):
    F0, trees = model
    return F0 + eta * sum(w[leaf_index(X, s)] for s, w in trees)

district = np.array("North South North East South West North East South West East North".split())
size = np.array([45, 60, 70, 50, 40, 80, 55, 65, 75, 60, 35, 85], float)
rent = np.array([9, 14, 15, 10, 11, 22, 12, 13, 18, 19, 7, 18], float)

ts, s, k, prior = ordered_ts(district, rent, perm=np.arange(12))
print("ordered TS:", np.round(ts, 3))
X = np.c_[size, ts]
Xq = np.c_[[70.0], full_ts(np.array(["South"]), s, k, prior)]

one = fit(X, rent, rounds=1)
print("tree 1 splits:", [(int(j), round(float(t), 3)) for j, t in one[1][0][0]])
print("tree 1 leaves:", np.round(one[1][0][1], 4))
print("after 1 tree, South 70 m2 ->", round(float(predict(one, Xq)[0]), 4))

model = fit(X, rent, rounds=100)
rmse = np.sqrt(np.mean((predict(model, X) - rent) ** 2))
print("100 trees: train RMSE", round(float(rmse), 3), "| South 70 m2 ->", round(float(predict(model, Xq)[0]), 3))
```

From scratch: ordered target statistics + symmetric trees fitted to squared-error residuals. Prints the hand-computed tree and prediction.

```text
ordered TS: [14.    14.    11.5   14.    14.    14.    12.667 12.    13.    18.
 12.333 12.5  ]
tree 1 splits: [(0, 57.5), (1, 12.167)]
tree 1 leaves: [ 0.    -2.625  0.     2.625]
after 1 tree, South 70 m2 -> 14.7875
100 trees: train RMSE 0.337 | South 70 m2 -> 17.87
```

Output of the script above.

```python
import numpy as np, pandas as pd
from catboost import CatBoostRegressor

df = pd.DataFrame({
    "district": "North South North East South West North East South West East North".split(),
    "size": [45, 60, 70, 50, 40, 80, 55, 65, 75, 60, 35, 85],
    "rent": [9, 14, 15, 10, 11, 22, 12, 13, 18, 19, 7, 18],
})
new = pd.DataFrame({"district": ["South"], "size": [70]})

# 1) Reproduce the hand-computed tree: feed the ordered TS as a number, one tree, L2 score.
ts = [14, 14, 11.5, 14, 14, 14, 38 / 3, 12, 13, 18, 37 / 3, 12.5]
X = pd.DataFrame({"size": df["size"], "ts": ts})
one = CatBoostRegressor(iterations=1, depth=2, learning_rate=0.3, l2_leaf_reg=3,
                        score_function="L2", random_strength=0, bootstrap_type="No", verbose=0)
one.fit(X, df.rent)
print("1 tree, train predictions:", np.round(one.predict(X), 4))
print("1 tree, South 70 m2:", round(float(one.predict(pd.DataFrame({"size": [70], "ts": [14.25]}))[0]), 4))

# 2) The normal way: hand CatBoost the raw category and let it build its own statistics.
for mode in ["Plain", "Ordered"]:
    m = CatBoostRegressor(iterations=300, depth=2, learning_rate=0.1, loss_function="RMSE",
                          boosting_type=mode, random_seed=0, verbose=0)
    m.fit(df[["district", "size"]], df.rent, cat_features=["district"])
    rmse = np.sqrt(np.mean((m.predict(df[["district", "size"]]) - df.rent) ** 2))
    print(mode, "| train RMSE", round(float(rmse), 3), "| South 70 m2 ->", round(float(m.predict(new)[0]), 2),
          "| importances", {k: round(float(v), 1) for k, v in zip(["district", "size"], m.get_feature_importance())})
print("default regression CTR:", m.get_all_params()["simple_ctr"][0].split(":")[0])
```

With the catboost library: first reproducing the hand-built tree exactly, then the normal workflow with the raw category.

```text
1 tree, train predictions: [13.2125 14.7875 14.     13.2125 13.2125 14.7875 13.2125 14.     14.7875
 14.7875 13.2125 14.7875]
1 tree, South 70 m2: 14.7875
Plain | train RMSE 0.411 | South 70 m2 -> 15.38 | importances {'district': 27.5, 'size': 72.5}
Ordered | train RMSE 0.641 | South 70 m2 -> 15.65 | importances {'district': 23.8, 'size': 76.2}
default regression CTR: Borders
```

Output (catboost 1.2.10). The library's own CTRs (target borders + counts) and random permutations give different numbers from our hand-built TS.

**Strengths**

- The data has categorical columns, especially high-cardinality ones (ids, postcodes, SKUs), and you want them used without leakage.
- You want strong results with default settings and little tuning — symmetric trees and ordered TS are robust regularizers.
- Prediction latency matters: oblivious trees evaluate as branch-free bit operations.
- The dataset is small or medium, where prediction shift hurts most and `Ordered` boosting helps.

**Limitations**

- All features are numeric and the data is huge: LightGBM is usually faster to train at similar accuracy.
- The target depends smoothly or linearly on the inputs, or you must extrapolate beyond the training range — tree sums are flat outside it.
- You need a single readable model: hundreds of trees plus stored category statistics are not interpretable rules.
- Rows are time-ordered and the future must not inform the past: a *random* permutation is the wrong order (use `has_time=True`).

- **Price and demand forecasting:** Retail and travel models with store, product, region and calendar categories; CatBoost was developed at Yandex for this kind of heterogeneous tabular data.
- **Real estate valuation:** Rent or sale price from district, building type and numeric size — the worked example at production scale.
- **Insurance and risk amounts:** Claim severity with `Tweedie` or `RMSE` loss on policy categories (vehicle make, region, occupation).
- **Delivery and arrival times:** ETA regression with courier, restaurant and zone ids, where high-cardinality ids carry most of the signal.

> **Target-encoding categories yourself before CatBoost:** If you replace a category by its mean target on the full training set and pass the result as a number, you reintroduce exactly the leak CatBoost was built to remove: training RMSE improves, test RMSE gets worse (1.192 vs 1.012 in the table above). Pass the raw column in `cat_features`.

> **Random permutations on time-ordered data:** For forecasting, a random permutation lets a row's statistic use rows from its future. Sort the data by time and set `has_time=True`, so the permutation *is* the time order, and validate on a later period, not a random split.

> **Why the training error is pessimistic:** With ordered statistics, rows early in the permutation see weak encodings, so CatBoost's training RMSE is often noticeably above what a leaky pipeline reports (0.919 vs 0.656 in the synthetic check) while its test RMSE is better. Judge it on held-out data only.

**Question:** In permutation order, a row from East is preceded by two East rows with rents 10 and 13. With prior p = 14 and a = 1, its ordered target statistic is…

- A. 11.5
- B. 12.333
- C. 11.0
- D. 14.0

**Answer:** B. 12.333 — $(10+13+1\cdot14)/(2+1)=37/3=12.333$. (11.0 is the greedy value, which also includes the row's own rent of 7.)

**Question:** A symmetric (oblivious) tree of depth 6 has how many leaves, and how many distinct split conditions?

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

**Answer:** B. 64 leaves, 6 conditions — Each level uses one (feature, border) pair for all its nodes, so there are $d=6$ conditions and $2^6=64$ leaves, indexed by a 6-bit number. A normal binary tree with 64 leaves has 63 separate conditions.

**Question:** A leaf holds 5 rows whose residuals sum to 21. With l2_leaf_reg = 3 and learning rate 0.3, how much does this tree add to those rows' predictions?

- A. 4.2
- B. 1.26
- C. 0.7875
- D. 2.625

**Answer:** C. 0.7875 — $w=G/(n+\lambda)=21/8=2.625$, and the update is $\eta w=0.3\cdot2.625=0.7875$. (4.2 is the unregularized mean residual; 1.26 is $0.3\cdot4.2$.)

**Question:** Why does leave-one-out target encoding still leak the target?

- A. It uses the test set
- B. Within a category, the encoding is a decreasing linear function of the row's own target, so a split can separate high and low targets perfectly
- C. It ignores the prior
- D. It only works for classification

**Answer:** B. Within a category, the encoding is a decreasing linear function of the row's own target, so a split can separate high and low targets perfectly — $\hat x_i=(S_c-y_i+ap)/(n_c-1+a)$: the higher $y_i$, the lower $\hat x_i$. In the worked example the North rents 9, 15, 12, 18 get LOO encodings 14.75, 13.25, 14.00, 12.50 — exactly reversed.

**Key points**

- Target encoding that includes a row's own target leaks it (prediction shift); leave-one-out leaks it in reverse.
- Ordered TS: encode row $i$ from the rows before it in a random permutation, smoothed by $(\,\sum y+ap)/(k+a)$; new rows use all training rows.
- Ordered boosting applies the same idea to residuals; Plain mode keeps ordered TS but ordinary residuals.
- Symmetric trees share one (feature, border) per level: $d$ tests, $2^d$ leaves, a $d$-bit index, chosen by $\sum_j G_j^2/(n_j+\lambda)$.
- For squared error, leaf value $w=G/(n+\lambda)$ and update $F\leftarrow F+\eta w$; λ shrinks small leaves and changes which splits win.
- Pass raw categories in `cat_features`, use early stopping, and tune depth and l2_leaf_reg first.

---

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