{"id":2998,"date":"2025-04-10T07:02:46","date_gmt":"2025-04-10T07:02:46","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/04\/10\/catboost-inner-workings-and-optimizations\/"},"modified":"2025-04-10T07:02:46","modified_gmt":"2025-04-10T07:02:46","slug":"catboost-inner-workings-and-optimizations","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/04\/10\/catboost-inner-workings-and-optimizations\/","title":{"rendered":"Why CatBoost Works So Well: The Engineering Behind the Magic"},"content":{"rendered":"

Why CatBoost Works So Well: The Engineering Behind the Magic
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

\n

\n

Gradient boosting<\/mdspan> is a cornerstone technique for modeling tabular data due to its speed and simplicity. It delivers great results without any fuss. When you look around you\u2019ll see multiple options like LightGBM, XGBoost, etc. Catboost<\/a> is one such variant. In this post, we will take a detailed look at this model, explore its inner workings, and understand what makes it a great choice for real-world tasks.<\/p>\n

Target Statistic<\/h2>\n
\"Table
Target Encoding Example: the average value of the target variable for a category is used to replace each category. Image by author<\/figcaption><\/figure>\n

Target Encoding Example: the average value of the target variable for a category is used to replace each category<\/p>\n

One of the important contributions of the CatBoost paper is a new method of calculating the Target Statistic. What is a Target Statistic? If you have worked with categorical variables before, you\u2019d know that the most rudimentary way to deal with categorical variables is to use one-hot encoding. From experience, you\u2019d also know that this introduces a can of problems like sparsity, curse of dimensionality, memory issues, etc. Especially for categorical variables with high cardinality.<\/p>\n

Greedy Target Statistic<\/h3>\n

To avoid one-hot encoding, we calculate the Target Statistic instead for the categorical variables. This means we calculate the mean of the target variable at each unique value of the categorical variable. So if a categorical variable takes the values \u2014 A<\/code>, B<\/code>, C<\/code> then we will calculate the average value of (text{y}) over all these values and replace these values with the average of (text{y}) at each unique value.<\/p>\n

That sounds good, right? It does but this approach comes with its problems \u2014 namely Target Leakage. To understand this, let\u2019s take an extreme example. Extreme examples are often the easiest way to eke out issues in the approach. Consider the below dataset:<\/p>\n

\n\n\n\n\n\n\n\n\n\n
Categorical Column<\/th>\nTarget Column<\/th>\n<\/tr>\n<\/thead>\n
A<\/td>\n0<\/td>\n<\/tr>\n
B<\/td>\n1<\/td>\n<\/tr>\n
C<\/td>\n0<\/td>\n<\/tr>\n
D<\/td>\n1<\/td>\n<\/tr>\n
E<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Greedy Target Statistic: Compute the mean target value for each unique category<\/figcaption><\/figure>\n

Now let\u2019s write the equation for calculating the Target Statistic:
[hat{x}^i_k = frac{
sum_{j=1}^{n} 1_{{x^i_j = x^i_k}} cdot y_j + a p
}{
sum_{j=1}^{n} 1_{{x^i_j = x^i_k}} + a
}]<\/p>\n

Here (x^i_j) is the value of the i-th categorical feature<\/strong> for the j-th sample<\/strong>. So for the k-th sample, we iterate over all samples of (x^i), select the ones having the value (x^i_k), and take the average value of (y) over those samples. Instead of taking a direct average, we take a smoothened average which is what the (a) and (p) terms are for. The (a) parameter is the smoothening parameter and (p) is the global mean of (y).<\/p>\n

If we calculate the Target Statistic using the formula above, we get:<\/p>\n

\n\n\n\n\n\n\n\n\n\n
Categorical Column<\/th>\nTarget Column<\/th>\nTarget Statistic<\/th>\n<\/tr>\n<\/thead>\n
A<\/td>\n0<\/td>\n(frac{ap}{1+a})<\/td>\n<\/tr>\n
B<\/td>\n1<\/td>\n(frac{1+ap}{1+a})<\/td>\n<\/tr>\n
C<\/td>\n0<\/td>\n(frac{ap}{1+a})<\/td>\n<\/tr>\n
D<\/td>\n1<\/td>\n(frac{1+ap}{1+a})<\/td>\n<\/tr>\n
E<\/td>\n0<\/td>\n(frac{ap}{1+a})<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Calculation of Greedy Target Statistic with Smoothening<\/figcaption><\/figure>\n

Now if I use this Target Statistic<\/code> column as my training data, I will get a perfect split at ( threshold = frac{0.5+ap}{1+a}). Anything above this value will be classified as 1<\/code> and anything below will be classified as 0<\/code>. I have a perfect classification at this point, so I get 100% accuracy on my training data.<\/p>\n

Let\u2019s take a look at the test data. Here, since we are assuming that the feature has all unique values, the Target Statistic becomes\u2014
[TS = frac{0+ap}{0+a} = p]
If (threshold) is greater than (p), all test data predictions will be (0). Conversely, if (threshold) is less than (p), all test data predictions will be (1) leading to poor performance on the test set.<\/p>\n

Although we rarely see datasets where values of a categorical variable are all unique, we do see cases of high cardinality. This extreme example shows the pitfalls of using Greedy Target Statistic as an encoding approach.<\/p>\n

Leave One Out Target Statistic<\/h3>\n

So the Greedy TS didn\u2019t work out quite well for us. Let\u2019s try another method\u2014 the Leave One Out Target Statistic method. At first glance, this looks promising. But, as it turns out, this too has its problems. Let\u2019s see how with another extreme example. This time let\u2019s assume that our categorical variable (x^i) has only one unique value, i.e., all values are the same. Consider the below data:<\/p>\n

\n\n\n\n\n\n\n\n\n
Categorical Column<\/th>\nTarget Column<\/th>\n<\/tr>\n<\/thead>\n
A<\/td>\n0<\/td>\n<\/tr>\n
A<\/td>\n1<\/td>\n<\/tr>\n
A<\/td>\n0<\/td>\n<\/tr>\n
A<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Example data for an extreme case where a categorical feature has just one unique value<\/figcaption><\/figure>\n

If calculate the leave one out target statistic, we get:<\/p>\n

\n\n\n\n\n\n\n\n\n
Categorical Column<\/th>\nTarget Column<\/th>\nTarget Statistic<\/th>\n<\/tr>\n<\/thead>\n
A<\/td>\n0<\/td>\n(frac{n^+ -y_k + ap}{n+a})<\/td>\n<\/tr>\n
A<\/td>\n1<\/td>\n(frac{n^+ -y_k + ap}{n+a})<\/td>\n<\/tr>\n
A<\/td>\n0<\/td>\n(frac{n^+ -y_k + ap}{n+a})<\/td>\n<\/tr>\n
A<\/td>\n1<\/td>\n(frac{n^+ -y_k + ap}{n+a})<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Calculation of Leave One Out Target Statistic with Smoothening<\/figcaption><\/figure>\n

Here:
(n) is the total samples in the data (in our case this 4)
(n^+) is the number of positive samples in the data (in our case this 2)
(y_k) is the value of the target column in that row
Substituting the above, we get:<\/p>\n

\n\n\n\n\n\n\n\n\n
Categorical Column<\/th>\nTarget Column<\/th>\nTarget Statistic<\/th>\n<\/tr>\n<\/thead>\n
A<\/td>\n0<\/td>\n(frac{2 + ap}{4+a})<\/td>\n<\/tr>\n
A<\/td>\n1<\/td>\n(frac{1 + ap}{4+a})<\/td>\n<\/tr>\n
A<\/td>\n0<\/td>\n(frac{2 + ap}{4+a})<\/td>\n<\/tr>\n
A<\/td>\n1<\/td>\n(frac{1 + ap}{4+a})<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Substituing values of n<\/code> and n<sup>+<\/sup><\/code><\/figcaption><\/figure>\n

Now, if I use this Target Statistic<\/code> column as my training data, I will get a perfect split at ( threshold = frac{1.5+ap}{4+a}). Anything above this value will be classified as 0<\/code> and anything below will be classified as 1<\/code>. I have a perfect classification at this point, so I again get 100% accuracy on my training data.<\/p>\n

You see the problem, right? My categorical variable which doesn\u2019t have more than a unique value is producing different values for Target Statistic which will perform great on the training data but will fail miserably on the test data.<\/p>\n

Ordered Target Statistic<\/h3>\n
\"Illustration
Illustration of ordered learning: CatBoost processes data in a randomly permuted order and predicts each sample using only the earlier samples. Image by author<\/figcaption><\/figure>\n

CatBoost introduces a technique called Ordered Target Statistic to address the issues discussed above. This is the core principle of CatBoost\u2019s handling of categorical variables.<\/p>\n

This method, inspired by online learning, uses only past data to make predictions. CatBoost generates a random permutation (random ordering) of the training data((sigma)). To compute the Target Statistic for a sample at row (k), CatBoost uses samples from row (1) to (k-1). For the test data, it uses the entire train data to compute the statistic.<\/p>\n

Additionally, CatBoost generates a new permutation for each tree, rather than reusing the same permutation each time. This reduces the variance that can arise in the early samples.<\/p>\n

Ordered Boosting<\/h2>\n
\"Diagram
This visualization shows how CatBoost computes residuals and updates the model: for sample x\u1d62, the model predicts using only earlier data points. Source<\/a><\/figcaption><\/figure>\n

Another important innovation introduced by the CatBoost paper is its use of Ordered Boosting. It builds on similar principles as ordered target statistics, where CatBoost randomly permutes the training data at the start of each tree and makes predictions sequentially.<\/p>\n

In traditional boosting methods, when training tree (t), the model uses predictions from the previous tree (t\u22121) for all training samples, including the one it is currently predicting. This can lead to target leakage<\/strong>, as the model may indirectly use the label of the current sample during training.<\/p>\n

To address this issue, CatBoost uses Ordered Boosting where, for a given sample, it only uses predictions from previous rows in the training data to calculate gradients and build trees. For each row (i) in the permutation, CatBoost calculates the output value of a leaf using only the samples before (i). The model uses this value to get the prediction for row (i). Thus, the model predicts each row without looking at its label<\/strong>.<\/p>\n

CatBoost trains each tree using a new random permutation to average the variance in early samples in one permutation.
Let\u2019s say we have 5 data points: A, B, C, D, E<\/code>. CatBoost creates a random permutation<\/strong> of these points. Suppose the permutation is: \u03c3 = [C, A, E, B, D]<\/code><\/p>\n

\n\n\n\n\n\n\n\n\n\n
Step<\/th>\nData Used to Train<\/th>\nData Point Being Predicted<\/th>\nNotes<\/th>\n<\/tr>\n<\/thead>\n
1<\/td>\n\u2014<\/td>\nC<\/td>\nNo previous data \u2192 use prior<\/td>\n<\/tr>\n
2<\/td>\nC<\/td>\nA<\/td>\nModel trained on C only<\/td>\n<\/tr>\n
3<\/td>\nC, A<\/td>\nE<\/td>\nModel trained on C, A<\/td>\n<\/tr>\n
4<\/td>\nC, A, E<\/td>\nB<\/td>\nModel trained on C, A, E<\/td>\n<\/tr>\n
5<\/td>\nC, A, E, B<\/td>\nD<\/td>\nModel trained on C, A, E, B<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
Table highlighting how CatBoost uses random permutation to perform training<\/figcaption><\/figure>\n

This avoids using the actual label of the current row to get the prediction thus preventing leakage<\/strong>.<\/p>\n

Building a Tree<\/h2>\n

Each time CatBoost builds a tree, it creates a random permutation of the training data. It calculates the ordered target statistic for all the categorical variables with more than two unique values. For a binary categorical variable, it maps the values to zeros and ones.<\/p>\n

CatBoost processes data as if the data is arriving sequentially. It begins with an initial prediction of zero for all instances, meaning the residuals are initially equivalent to the target values.<\/p>\n

As training proceeds, CatBoost updates the leaf output for each sample using the residuals of the previous samples that fall into the same leaf. By not using the current sample\u2019s label for prediction, CatBoost effectively prevents data leakage.<\/p>\n

Split Candidates<\/h2>\n
\"Histogram
CatBoost bins continuous features to reduce the search space for optimal splits. Each bin edge and split point represents a potential decision threshold. Image by author<\/figcaption><\/figure>\n

At the core of a decision tree lies the task of selecting the optimal feature and threshold for splitting a node. This involves evaluating multiple feature-threshold combinations and selecting the one that gives the best reduction in loss. CatBoost does something similar. It discretizes the continuous variable into bins to simplify the search for the optimal combination. It evaluates each of these feature-bin combinations to determine the best split<\/p>\n

CatBoost uses Oblivious Trees, a key difference compared to other trees, where it uses the same split across all nodes at the same depth.<\/p>\n

Oblivious Trees<\/h2>\n
\"Comparison
Illustration of ordered learning: CatBoost processes data in a randomly permuted order and predicts each sample using only the earlier samples. Image by author<\/figcaption><\/figure>\n

Unlike standard decision trees, where different nodes can split on different conditions (feature-threshold), Oblivious Trees split across the same conditions across all nodes at the same depth of a tree. At a given depth, all samples are evaluated at the same feature-threshold combination. This symmetry has several implications:<\/p>\n