CatBoost

CatBoost is a gradient boosting algorithm designed mainly for tabular data, especially when you have many categorical features.

It was developed by Yandex and published in 2017.

CatBoost is a high-performance open-source library for gradient boosting on decision trees. Its name is a contraction of Categorical Boosting. While it shares the same foundational logic as XGBoost and LightGBM, it introduces several innovations that make it particularly effective for real-world datasets.

CatBoost = A Gradient Boosting Decision Tree algorithm

1. Handling Categorical Features

In most ML algorithms, you must manually convert text-based categories (like “City” or “Color”) into numbers using techniques like One-Hot Encoding. CatBoost handles this automatically using Ordered Target Statistics. It converts categories into numerical values based on the target variable while avoiding “data leakage” (where the model accidentally learns the answer from the training data).

2. Symmetric Trees (Oblivious Trees)

Unlike other boosting libraries that grow deep or asymmetrical branches, CatBoost builds Symmetric Trees. This means that at each level of the tree, the same splitting feature and threshold are used for all nodes.

• Benefit: This acts as a form of regularization, preventing the model from over-fitting.
• Speed: Symmetric trees are extremely fast to evaluate during deployment (inference).

3. Ordered Boosting

Standard gradient boosting suffers from “prediction shift.” Because the same data is used to calculate the gradient and train the model, the error estimates can be biased. CatBoost uses a technique called Ordered Boosting, which processes data points in a way that ensures the residual for a specific point is calculated using a model trained only on the points that came before it.

When CB used for classification (e.g., predicting “Spam” vs. “Not Spam”), CatBoost follows these steps:

1. Initialization: Starts with a simple initial prediction (like the average probability of the classes).
2. Iterative Refinement:

• Calculates the gradient (loss) for each observation.
• Fits a symmetric tree to these gradients.
• Updates the model by adding the new tree’s predictions, scaled by a learning rate.

1. Log-Loss Optimization: It typically minimizes Logarithmic Loss, which penalizes the model more heavily for being confidently wrong.

Why choose CatBoost?

• Minimal Tuning: It often performs exceptionally well with default hyperparameters.
• Robustness: It is less sensitive to outliers and handles missing values automatically.
• Performance: It is frequently the top performer in tabular data competitions (like Kaggle) where categorical data is prevalent.

Typical ML pipeline:

Data Collection → Data Cleaning → Feature Engineering → Train/Test Split → Model Training(CatBoost here) → Hyperparameter Tuning → Evaluation → Deployment.

CatBoost replaces models like:

• Logistic Regression
• Random Forest
• XGBoost
• Neural networks (sometimes)

The Math

CatBoost is based on Gradient Boosting which builds trees sequentially.

The core idea is to make predictions as close as possible to the real answer thus we want to minimize a loss function: the loss function measures how wrong the model is.:

L(y,F(x)) → {y = true value and F(x) = model prediction}

The model is built as:

Where:

• hm​(x) = decision tree
• γm​ = weight
• M = number of trees

Each new tree learns the residual errors.

Note: Residual error is simply the difference between the actual value and the model’s prediction.

Residual = y − y^ {y = actual value (truth) and y^ is the predicted value}

This nsure that each tree approximates the negative gradient.

That is why it is called gradient boosting.

A gradient tells you: Which direction increases the loss the fastest.

Think of it like a slope on a hill.

• Going uphill → loss increases
• Going downhill → loss decreases

The gradient points uphill.

The negative gradient points downhill.

And downhill is where we want to go because:

Downhill = smaller loss = better model

So:

Meaning: Move in the direction that reduces the loss the fastest.

Problem With Standard Gradient Boosting

Normal boosting (like XGBoost) has issues with categorical variables.

Get Mausam’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Typical solutions:

• One-Hot Encoding
• Label Encoding
• Target Encoding

But these cause:

• Overfitting
• Data leakage

CatBoost’s Solution: Ordered Target Encoding

CatBoost encodes categories using statistics computed from previous samples only.

This approach is the “secret sauce” that allows CatBoost to handle categorical data so effectively without the risk of target leakage.

In traditional Target Encoding, you replace a category (like “City: Florida”) with the average value of the target variable for all rows where “City” is “Florida.” The problem? The model “sees” the answer it’s trying to predict during the training phase, leading to overfitting.

How Ordered Target Encoding Works

CatBoost introduces a time-based or sequence-based logic to this calculation. Even if your data isn’t a time series, CatBoost creates a random permutation (a random ordering) of the data to simulate a sequence.

For any given row i, the numerical value for a categorical feature is calculated using only the rows that came before it in that random permutation:

Breaking down the formula:

• Numerator: The sum of target values (y_j) for all previous rows that have the same category.
• Denominator: The count of those previous rows.
• s (Prior Weight): A smoothing parameter to handle categories that haven’t appeared many times yet.
• p (Prior): A default value (usually the average target value of the entire dataset).

Why This Matters

1. Prevents Overfitting: By only looking “backward,” the model never uses the current row’s target to calculate its own feature value. This eliminates the “leakage” that often plagues XGBoost or LightGBM if they aren’t tuned carefully.
2. Handles Rare Categories: The “Prior” (p) ensures that if a category has only appeared once or twice, the encoded value stays close to the global average rather than an extreme outlier.
3. No Manual Pre-processing: You don’t need to perform Label Encoding or One-Hot Encoding yourself. You simply tell CatBoost which columns are categorical, and it handles the math under the hood.

The “Multiple Permutations” Trick

To make the model even more robust, CatBoost doesn’t just do this once. It creates multiple random permutations of the dataset and calculates these statistics differently for different trees. This adds a layer of variety (regularization) that makes the final ensemble incredibly stable.

Second Innovation: Ordered Boosting

The Problem: Prediction Shift

In standard gradient boosting (like XGBoost or LightGBM), the same data points are used to calculate the gradients (the errors) and then to train the next tree.

Imagine a model is trying to learn from a specific data point, x_i.

1. Tree 1 makes a prediction for x_i.
2. The Gradient (error) for x_i is calculated using its own target value y_i.
3. Tree 2 is then trained using that same gradient to “correct” the error.

Because x_i was used to calculate the very gradient it is now trying to predict, the estimate is biased. This leads to a discrepancy between the distribution of gradients during training and the distribution during testing, known as Prediction Shift. This is why other models often require heavy regularization to avoid overfitting.

The Solution: Ordered Boosting

CatBoost solves this by ensuring that the gradient used to train a tree for a specific data point is calculated without ever having seen that point’s target value.

It uses a “Permutation-based” approach:

1. Random Shuffle: CatBoost performs several random permutations of the training data.
2. Prefix-Based Learning: For a specific permutation, to calculate the gradient for the i-th element, CatBoost uses a model trained only on the preceding i-1 elements.
3. Independence: This ensures that the residual (error) for point x_i is truly “unseen” by the model being used to evaluate it.

Structure of the Trees

CatBoost uses Oblivious Trees (Symmetric Trees) : In CatBoost trees, every node at the same depth uses the same feature and threshold.

In an Oblivious Tree, the same splitting criterion (feature + threshold) is applied to all nodes at the same level of the tree. This means that for any given depth, every node is asking the exact same question.

How It Works (The “Rule” of Symmetry)

1. Level 1 Split: Is Income > 50k? (Applied to the root).
2. Level 2 Split: Is Age > 30? This question is applied to both resulting branches from the first split.
3. Level 3 Split: Is City == "Florida"? Again, this is applied across all four nodes created by Level 2.

Because the splits are identical across the level, the tree structure is balanced and “oblivious” to the specific path a data point took to get there.

Why Use This Structure?

The choice of symmetric trees provides three massive technical advantages:

1. Lightning-Fast Inference (Prediction): Since the tree is symmetric, the path a data point takes can be encoded as a Binary Index. Instead of following a complex “if-then-else” logic through a deep forest, CatBoost can evaluate the tree using bitwise operations. This makes it incredibly efficient for real-time applications where you need predictions in milliseconds.

2. Built-in Regularization: Symmetric trees are naturally more “constrained” than asymmetric ones. They cannot over-fit to tiny, specific sub-pockets of data as easily. This architectural choice acts as a form of regularization, helping the model generalize better to new, unseen data.

3. Efficient Feature Interaction: Because each level uses one feature for the entire breadth of the tree, CatBoost is excellent at finding global feature interactions. It forces the model to find the most impactful “questions” that apply to the broadest possible segments of the data at once.

Intuition in One Sentence

CatBoost = Gradient Boosting + Smart categorical encoding + Ordered training to prevent leakage.