CatBoost: unbiased boosting with categorical features
This paper presents the key algorithmic techniques behind CatBoost, a new gradient boosting toolkit. Their combination leads to CatBoost outperforming other publicly available boosting implementations in terms of quality on a variety of datasets. Two critical algorithmic advances introduced in CatBoost are the implementation of ordered boosting, a permutation-driven alternative to the classic algorithm, and an innovative algorithm for processing categorical features. Both techniques were created to fight a prediction shift caused by a special kind of target leakage present in all currently existing implementations of gradient boosting algorithms. In this paper, we provide a detailed analysis of this problem and demonstrate that proposed algorithms solve it effectively, leading to excellent empirical results.
UPDATE AFTER AUTHORS' RESPONSE  Regarding "using one tree structure", I think I understand now, and I think the current wording is confusing.  Both the manuscript and the response made me think that the *same* tree splits (internal nodes) are used for all of the boosting iterations.  But looking at the argmin line in Algorithm 2, I think the intent is to say "the same feature is used to split all internal nodes at a given level of a tree" (aka, oblivious tree).  If that is not right, then I am still confused.  Regarding one random permutation, please update text to be more clear.   SUMMARY  The paper identifies two potential sources of overfitting, one related to how high cardinality categorical features are encoded, and the other due to reuse of labeled examples across gradient boosting iterations.  A new boosting variation, CatBoost, addresses both problems by treating the examples as an ordered sequence that is accessed in an online or prequential fashion (ala A.P. Dawid's work). The algorithm builds a nested sequence of models that are indexed against the sequence of labeled examples.  Model i is allowed to use all the labeled examples seen before the i'th point in the example sequence, but none afterwards.  This helps avoid estimation bias from reusing target labels (supported by theoretical analysis). Empirically, CatBoost is more accurate than popular boosting implementations (LightGBM and XGBoost) with comparable or faster training time.  The impact from different components of the algorithm are measured empirically.  REVIEW  This is a very good paper.  It makes several valuable contributions:  * Help clarify a source of overfitting in boosting.  This should help   others continue research into the problem. * Propose a new, interesting way to avoid target leakage when   representing categorical features with target statistics.  The risk   of target leakage is well-known, and the paper shows that the new   approach leads to better accuracy than the simple approaches people   are currently using. * Propose ordered boosting to solve the overfitting problem, and   describe an efficient implementation of it. * Solid empirical study of the new algorithm.  The main weakness is not including baselines that address the overfitting in boosting with heuristics.  Ordered boosting is non-trivial, and it would be good to know how far simpler (heuristic) fixes go towards mitigating the problem.  Overall, I think this paper will spur new research.  As I read it, I easily came up with variations and alternatives that I wanted to see tried and compared.   DETAILED COMMENTS  The paper is already full of content, so the ideas for additional comparisons are really suggestions to consider.  * For both model estimations, why start at example 1?  Why not start   at an example that is 1% of the way into the training data, to help   reduce the risk of high variance estimates for early examples?  * The best alternative I've seen for fixing TS leakage, while reusing   the data sample, uses tools from differential privacy [1, 2].  How   does this compare to Ordered TS?  * Does importance-sampled voting [3] have the same target leakage   problem as gradient boosting?  This algorithm has a similar property   of only using part of the sequence of examples for a given model.   (I was very impressed by this algorithm when I used it; beat random   forests hands down for our situation.)  * How does ordered boosting compare to the subsampling trick mentioned   in l. 150?  * Yes, fixes that involve bagging (e.g., BagBoo [4]) add computational   time, but so does having multiple permuted sequences.  Seems worth a   (future?) comparison.  * Why not consider multiple permutations, and for each, split into   required data subsets to avoid or mitigate leakage?  Seems like it   would have the same computational cost as ordered boosting.  * Recommend checking out the Wilcoxon signed rank test for testing if   two algorithms are significantly different over a range of data   sets.  See [6].  * l. 61: "A categorical feature..."  * l. 73: "for each categorical *value*" ?  * l. 97: For clarity, consider explaining a bit more how novel values   in the test set are handled.  * The approach here reminds me a bit of Dawid's prequential analysis,   e.g., [5].  Could be worth checking those old papers to see if there   is a useful connection.  * l. 129: "we reveal" => "we describe" ?  * l. 131: "called ordered boosting"  * l. 135-137: The "shift" terminology seems less understandable than   talking about biased estimates.  * l. 174: "remind" => "recall" ?  * l. 203-204: "using one tree structure"; do you mean shared \sigma?  * Algorithm 1: only one random permutation?  * l. 237: Don't really understand what is meant by right hand side of   equality.  What is 2^j subscript denoting?  * l. 257: "tunning" => "tuning"  * l. 268: ", what is expected."  This reads awkwardly.  * l. 311: This reference is incomplete.   REFERENCES  [1] https://www.slideshare.net/SessionsEvents/misha-bilenko-principal-researcher-microsoft  [2] https://www.youtube.com/watch?v=7sZeTxIrnxs  [3] Breiman (1999).  Pasting small votes for classification in large databases and on-line.  Machine Learning 36(1):85--103.  [4] Pavlov et al. (2010).  BagBoo: A scalable hybrid bagging-the-boosting model.  In CIKM.  [5] Dawid (1984).  Present position and potential developments: Some personal views: Statistical Theory: The Prequential Approach.  Journal of the Royal Stastical Society, Series A, 147(2).  [6] Demsar (2006).  Statistical comparisons of classifiers over multiple data sets.  Journal of Machine Learning Research, 7:1--30.