Source-linked AI summary
CatBoost: gradient boosting with categorical features support
Anna Veronika Dorogush, Vasily Ershov, Andrey Gulin
TL;DR
Gradient boosting performs well on heterogeneous and complex data, but categorical features are commonly converted to numbers before training. CatBoost addresses this by handling categorical features during training and introducing strategies intended to reduce overfitting and gradient bias. It outperforms established gradient boosting implementations across diverse tasks and reports faster comparable-ensemble GPU training and CPU scoring, subject to limitations in speed comparisons.
Problem
Gradient boosting must handle important categorical features, yet common implementations typically convert them to numerical values before training.
Method
CatBoost handles categorical features during training using ordered statistics and uses new schemes for leaf values and gradient estimation to reduce overfitting and gradient bias.
Results
CatBoost outperforms XGBoost, LightGBM, and H2O across diverse popular tasks, while comparable-ensemble training and scoring experiments report faster GPU training and CPU scoring.
Takeaways & Limitations
CatBoost provides an open-source gradient boosting library that combines categorical-feature support with CPU and GPU implementations for quality and speed comparisons.
Takeaways & Limitations
Training-speed comparisons are rough because libraries have different parameterized quality, speed, and model-size trade-offs, and tree-construction time depends on features and ensemble size.
Abstract
from arXiv · showhide
In this paper we present CatBoost, a new open-sourced gradient boosting library that successfully handles categorical features and outperforms existing publicly available implementations of gradient boosting in terms of quality on a set of popular publicly available datasets. The library has a GPU implementation of learning algorithm and a CPU implementation of scoring algorithm, which are significantly faster than other gradient boosting libraries on ensembles of similar sizes.
1 Introduction
CatBoost is a gradient boosting algorithm designed to handle categorical features during training rather than preprocessing. It improves predictive quality across diverse tasks and provides faster GPU training and CPU scoring on similarly sized ensembles.
- Gradient boosting combines weaker base predictors iteratively through a greedy procedure corresponding to gradient descent in function space.
- Categorical features are important in many datasets, but common gradient boosting implementations typically convert them to numbers before training.Categorical features contain discrete, non-comparable values such as user IDs or city names.
- CatBoost handles categorical features during training and uses a new leaf-value calculation scheme that helps reduce overfitting.
- CatBoost outperforms XGBoost, LightGBM, and H2O on a diverse set of popular tasks.The algorithm is released as open source.
- CatBoost provides GPU and CPU implementations, with faster GPU training and CPU scoring than comparable open-source gradient boosting implementations on similarly sized ensembles.
2 Categorical features
CatBoost transforms categorical features using training-aware statistics and combinations while addressing overfitting from label-based encodings. Its ordered strategy uses preceding examples and priors, and its feature combinations capture interactions between categorical variables.
- Categorical features have discrete, non-comparable values and therefore cannot be used directly in binary decision trees.
- One-hot encoding replaces a categorical feature with binary variables for its categories and can be performed during training in CatBoost.
- Label-based category statistics can overfit, while partitioning data reduces overfitting at the cost of using less data for training and statistic calculation.
- CatBoost computes category averages from same-category examples preceding each example in a random permutation, enabling use of the whole dataset for training while reducing overfitting.
- A prior P weighted by a > 0 reduces noise from low-frequency categories, and several permutations can be used with CatBoost’s leaf-value scheme without overfitting.
- Feature combinations represent interactions such as user ID with musical genre, but the number of combinations grows exponentially with the number of categorical features.
- CatBoost also implements category-appearance counts and computes this statistic for feature combinations.
- CatBoost considers several priors and constructs a feature for each to fit the optimal prior at each algorithm step.
3 Fighting Gradient Bias
CatBoost addresses gradient bias by estimating each example’s gradient with a model that excludes that example, while sharing tree structures for efficiency. Random permutations and a compressed implementation make this strategy practical.
- Classical boosting can overfit because gradients are estimated on the same data used to build the current model.
- CatBoost estimates each example’s gradient with a separate model trained without that example, producing gradients unbiased with respect to its model.
- The training procedure updates models and calculates model values for gradient estimation while constructing successive trees.
- CatBoost relaxes the separate-model construction by having all example-specific models share the same tree structures.
- Several random dataset permutations improve robustness, while maintaining O(s n) rather than O(n^2) values reduces the complexity of constructing one tree.
4 Fast scorer
CatBoost uses oblivious trees and compact binary representations to accelerate model evaluation. Data-parallel construction of these vectors provides up to 3x speedup and a faster scorer.
- CatBoost uses oblivious trees, applying the same splitting criterion across each tree level and encoding each leaf index as a depth-length binary vector.
- Leaf values are stored in vectors of size 2^d, where d is the tree depth, and binary feature values are stored in a continuous vector B.
- The leaf index for an example is computed from the binary feature values selected at each depth of a tree.
- Data-parallel vector construction gives up to 3x speedup and produces a scorer faster than existing alternatives in the reported experiments.
5 Fast training on GPU
CatBoost accelerates GPU training through discretized, grouped feature representations and histogram computation designed to avoid slow atomic operations. Its categorical-feature support includes permutation-based statistics and feature combinations, with GPU-specific memory handling.
- Dense numerical features: CatBoost discretizes dense numerical features into fixed bins and uses a histogram-based approach to search for decision-tree splits.
- Dense numerical features: Feature values are bit-packed into 32-bit integers, using 1, 4, or 8 bits according to the number of bins.
- GPU histogram computation: CatBoost avoids the atomic operations used by XGBoost and LightGBM by computing partial histograms per GPU warp.
- GPU histogram computation: Histogram construction uses shared memory and loop unrolling to maintain high performance despite less than 100% GPU occupancy.
- Categorical features: Categorical-feature processing supports one-hot encoding, single-feature statistics, and feature-combination statistics, with combinations described as the slowest and most memory-consuming component.
- Categorical features: GPU categorical processing stores bit-compressed perfect hashes in CPU RAM and streams required data while overlapping computation and memory operations.
- Multiple GPU support: Multi-GPU learning uses feature-parallel computation because categorical statistics are computed during training across several dataset permutations.
6 Experiments
Experiments evaluate CatBoost against established gradient-boosting implementations for classification quality, GPU training speed, and CPU scoring speed. CatBoost outperforms the compared methods on classification datasets and shows substantial speed advantages, although cross-library training-time comparisons are constrained.
- GPU vs CPU training performance: GPU training significantly outperforms CPU training on the Criteo categorical-feature benchmark, reaching an x15 speedup on NVIDIA V100.The benchmark uses 36 *10^6 samples, 26 categorical features, and 13 numerical features.
- GPU training performance: comparison with baselines: Training-speed comparisons across boosting libraries cannot establish the time required to reach a given quality level because parameter and quality–speed trade-offs differ.The experiment therefore compares fixed-size ensembles rather than time to achieve a target quality.
- GPU training performance: comparison with baselines: 17.9ms mean tree construction time for CatBoost compares with 488ms for XGBoost and 40ms for LightGBM on 8000-tree Epsilon ensembles.The authors characterize these as rough comparisons because tree-construction time depends on feature distribution and ensemble size.
- Scorer performance: CatBoost scoring is around 25 times faster than XGBoost and around 60 times faster than LightGBM on similarly sized Epsilon ensembles.All models use 8000 trees, and prediction wall time is measured on an Intel Xeon E5-2660 CPU after loading and converting the test data.