CatBoost
Core Concept
CatBoost is gradient boosting on decision trees, engineered around one observation: the standard ways of handling categorical features leak the target into the features. Naive mean-target encoding computes a category's average label using rows that include the row you are about to predict — so the model memorises rather than learns. CatBoost's answer is ordering. It draws random permutations of the data and, for every row, computes both its categorical encodings and its boosting residuals using only the rows that came before it. That single discipline removes target leakage and the subtler prediction shift that biases classic boosting. Add symmetric (oblivious) trees for regularisation and blazing inference, and you get a model that is unusually strong out of the box on tabular data full of high-cardinality categories.
Key Components
Ordered Target Statistics
Each categorical value becomes a number derived only from prior rows in a random permutation, smoothed toward a prior P with weight a. No peeking at your own label — no leakage, and rare categories fall back gracefully to the prior.
Ordered Boosting
The residual for example i is scored by a model trained without example i. Classic boosting reuses the same data to both fit and evaluate gradients, so residuals are optimistically biased — that is prediction shift. Ordering removes it.
Oblivious / Symmetric Trees
Every node at the same depth uses the same feature and threshold. The tree becomes a lookup over a bit-vector: heavy regularisation against overfitting, and inference that vectorises into a handful of CPU instructions.
Feature Combinations
As trees grow, CatBoost greedily merges categoricals it has already split on into new combined categories (city×device). It discovers interaction terms you would otherwise hand-engineer.
How It Works
- Generate several random permutations of the training set. Different permutations are used for encodings and for gradient estimation, so no single ordering dominates.
- For every categorical value in a row, compute its ordered target statistic from preceding rows only, smoothed by prior
Pand weighta. - Estimate the gradient/residual for each example using supporting models built on prefixes of the permutation — models that have not seen that example.
- Grow one oblivious tree: at each depth, pick the single (feature, threshold) pair that best reduces loss across all nodes at that level.
- Optionally forge new combination features from categoricals already used in this tree, then re-scan candidate splits.
- Add the tree scaled by the learning rate, and repeat for the chosen number of iterations with early stopping on a validation fold.
Boosting Family, Side by Side
| Dimension | CatBoost | XGBoost | LightGBM |
|---|---|---|---|
| Categoricals | Native, ordered TS | Manual encode | Native, greedy split |
| Tree shape | Oblivious, symmetric | Depth-wise | Leaf-wise (best-first) |
| Growth bias | Ordered, low bias | Prediction shift | Prediction shift |
| Tuning effort | Low — strong defaults | Moderate | Higher (leaf count) |
| Inference speed | Very fast | Fast | Fast |
| Sweet spot | High-cardinality tabular | Dense numeric | Very large numeric |
Real-World Applications
cat_features. Pre-encoding throws away the ordered statistic — you re-introduce the exact leakage CatBoost exists to prevent, and usually lose accuracy while doing more work.
Checkpoint — answer before you move on
- Why does naive mean-target encoding leak, and how does the ordered target statistic close the leak without discarding the target signal? Hint: think about which rows contribute to the encoding of row i.
- What is prediction shift in classic gradient boosting, and what does ordered boosting change about how residuals are computed? Hint: which examples was the model that scores example i trained on?
- Oblivious trees are strictly less expressive than free-form trees at the same depth. Name one accuracy-side benefit and one systems-side benefit that make the trade worth it. Hint: one answer is about variance, the other about how inference maps onto hardware.