CatBoost Splitting Algorithms vs XGBoost and LightGBM

While XGBoost and LightGBM rely on asymmetric depth-wise or leaf-wise splitting strategies, CatBoost introduces a fundamentally distinct architecture centered around symmetric oblivious trees and permutation-based categorical splits. This article explores the unique splitting algorithms that set CatBoost apart in Python, focusing on oblivious tree growth, ordered target encoding, dynamic feature combinations, and how these mechanisms compare directly to the splitting paradigms of XGBoost and LightGBM.

Oblivious Trees: Symmetric Splitting

The primary structural difference in CatBoost is its use of oblivious decision trees (also known as symmetric trees). In traditional gradient boosting frameworks, trees grow asymmetrically:

• XGBoost traditionally uses a level-wise (depth-wise) approach, splitting nodes level by level, where different nodes at the same depth can evaluate completely different features and thresholds.
• LightGBM uses a leaf-wise (best-first) approach, splitting the single node that yields the maximum loss reduction, which creates unbalanced, deeper trees rapidly.

In contrast, CatBoost applies the same splitting criterion (the identical feature and split threshold) across all nodes at the given depth level.

Key Characteristics of Symmetric Splits

1. Balanced Structure: A CatBoost tree of depth \(d\) always has exactly \(2^d\) leaves, maintaining strict structural symmetry.
2. Inference Speed: Evaluating a symmetric tree does not require pointer traversal down a graph. Instead, the tree evaluates \(d\) binary conditions sequentially, constructs a binary index via bitwise operations, and accesses leaf values directly via table lookup.
3. Regularization: Because the same rule must apply across all branches of that depth, oblivious trees enforce strong structural regularization, significantly reducing the risk of overfitting on noisy tabular data.

Categorical Feature Splitting with Ordered Target Statistics

XGBoost historically relies on one-hot encoding or experimental partition methods for categorical variables, while LightGBM sorts categorical levels by their target histogram values to find optimal subsets (\(O(K \log K)\) splits).

CatBoost replaces these methods with Ordered Target Statistics (OTS):

1. Random Permutations: CatBoost randomly permutes the dataset to introduce an artificial time sequence.
2. Online Encoding: For each sample, the target statistic for a category is computed using only the samples that precede it in that permutation: \[\hat{x}_{k} = \frac{\sum_{j < k} [x_j = x_k] \cdot y_j + a \cdot P}{\sum_{j < k} [x_j = x_k] + a}\] (where \(P\) is a prior value and \(a\) is a regularization parameter).
3. Target Leakage Prevention: Because a sample’s label is never used to compute its own feature value or the values of preceding samples, CatBoost eliminates target leakage (prediction shift) during tree node splitting.

In Python, passing categorical indices via the cat_features argument in CatBoostClassifier or CatBoostRegressor triggers this ordered splitting procedure automatically without manual pre-encoding.

Dynamic Feature Combinations on Tree Splits

Standard gradient boosting libraries evaluate single-feature splits independently, leaving feature interactions to be captured across successive tree depths.

CatBoost builds interaction splits dynamically:

• When considering a new split for an oblivious tree, CatBoost pairs the current candidate feature with categorical features already utilized in prior splits of that same tree.
• These combinations are generated on-the-fly during tree construction rather than in a preprocessing step, ensuring that only combinations that yield significant gain in the current tree context are evaluated.

Ordered Boosting: Unbiased Gradient Estimation

Traditional gradient boosting evaluates split candidates using gradients calculated on the entire training set, introducing a statistical bias because the gradients depend on the target values of the same instances used to train the current model.

CatBoost resolves this by maintaining several supporting models trained on distinct prefixes of the random permutations:

• The gradient step for a given instance is calculated using a model that has never observed that instance.
• Candidate splits are evaluated against unbiased gradient estimates, resulting in more accurate split selection than standard second-order Taylor approximations calculated globally.

Summary Comparison