31
$\begingroup$

There exist several implementations of the GBDT family of model such as:

  • GBM
  • XGBoost
  • LightGBM
  • Catboost.

What are the mathematical differences between these different implementations?

Catboost seems to outperform the other implementations even by using only its default parameters according to this bench mark, but it is still very slow.

My guess is that catboost doesn't use the dummified variables, so the weight given to each (categorical) variable is more balanced compared to the other implementations, so the high-cardinality variables don't have more weight than the others. It allows the weak categorical (with low cardinality) to enter to some trees, hence better performance. Other than that, I have no further explanation.

$\endgroup$
27
$\begingroup$
My guess is that catboost doesn't use the dummified variables, so the weight given to each (categorical) variable is more balanced compared to the other implementations, so the high-cardinality variables don't have more weight than the others.

https://arxiv.org/abs/1706.09516

You want to look at this English language paper from the Yandex team about CATBoost mathematical uniqueness.

I read it briefly, and among few things I could understand quickly was the fact that they do not use the residuals obtained on TRAIN to do TRAIN, since these residuals create optimistic bias of the learning quality. (Update: this novelty brings about a way to battle the overfitting, which is one of the reasons the algorithm worked better compared to its analogues, apart from a variety of ways to preprocess categorical variables).

I am sorry for not giving you a specific and full answer.

Mathematical differences between GBM, XGBoost

First I suggest you read a paper by Friedman about Gradient Boosting Machine applied to linear regressor models, classifiers, and decision trees in particular. https://statweb.stanford.edu/~jhf/ftp/trebst.pdf

I would not go in the details here. It is just a good read covering various types of loss (L) and besides variable importance concept. Of course this is a milestone paper of implementation of the method of a descent in the space of functions (low-level models) rather than parameters in pursuit of loss minimization.

If you look here: https://arxiv.org/pdf/1603.02754.pdf

You find a mathematical vignette for XGBoost model by Tianqi Chen et al. Now it becomes interesting. A couple of mathematical deviations of this model form the classic Friedman's GBM are:

  • Regularized (penalized) parameters (and we remember that parameters in the boossting are the function, trees, or linear models): L1 and L2 are available.

enter image description here

  • Using second derivatives to speed up the process (if it was used before please correct me).

To this point: look here to find an implementation of quantile loss in CATBoost, which comes in handy and provides both first and second derivatives: https://github.com/catboost/catboost/blob/master/catboost/libs/algo/error_functions.h

class TQuantileError : public IDerCalcer<TQuantileError, /*StoreExpApproxParam*/ false> { public:
    const double QUANTILE_DER2 = 0.0;

    double Alpha;
    SAVELOAD(Alpha);

    explicit TQuantileError(bool storeExpApprox)
        : Alpha(0.5)
    {
        CB_ENSURE(storeExpApprox == StoreExpApprox, "Approx format does not match");
    }

    TQuantileError(double alpha, bool storeExpApprox)
        : Alpha(alpha)
    {
        Y_ASSERT(Alpha > -1e-6 && Alpha < 1.0 + 1e-6);
        CB_ENSURE(storeExpApprox == StoreExpApprox, "Approx format does not match");
    }

    double CalcDer(double approx, float target) const {
        return (target - approx > 0) ? Alpha : -(1 - Alpha);
    }

    double CalcDer2(double = 0, float = 0) const {
        return QUANTILE_DER2;
    } };

While you cannot find this useful L1 loss function in XGBoost, you can try to compare Yandex's implementation with some of the custom loss functions written for XGB.

  • Besides, CATBoost works excelently with categorical features, while XGBoost only accepts numeric inputs.

Consider this link: https://tech.yandex.com/catboost/doc/dg/concepts/algorithm-main-stages_cat-to-numberic-docpage/#algorithm-main-stages_cat-to-numberic

They offer a variety of ways to feed categorical features to the model training on top of using old and well-known one-hot approach. Decreasing dimensions of an input space without loosing much information is one of possible reasons the fitted model are less overfitted.

I am done. I don't use LightGBM, so cannot shed any light on it.

$\endgroup$
  • 4
    $\begingroup$ I wonder why would someone downvote an answer without giving a better answer? Welcome on stage to give any input beyond doing anonymous downvoting, sir. $\endgroup$ – Alexey Burnakov Oct 16 '17 at 19:46
  • $\begingroup$ it responses exactly to my question for the catboost. Do you have any supplementary materials for LightGBM, XGBoost, and GBM? $\endgroup$ – Metariat Oct 18 '17 at 7:51
  • $\begingroup$ Yes, I will entich my answer. Do you cope well with hard math or rather prefer intuitive explanations? $\endgroup$ – Alexey Burnakov Oct 18 '17 at 9:06
  • $\begingroup$ Thank you, I can cope well with both, intuitive explanation is quicker to get, and mathematical details takes more time but is very benificial for further understanding / implementations. $\endgroup$ – Metariat Oct 18 '17 at 9:15
  • 1
    $\begingroup$ Answer enriched. $\endgroup$ – Alexey Burnakov Oct 18 '17 at 12:03
0
$\begingroup$

XGBoost uses Newton boosting whereas the other packages use gradient boosting. For some loss functions, the GBM package (and also scikit-learn) use hybrid gradient-Newton boosting as suggested in Friedman (2001) with gradient steps to find the tree structures and Newton's method to update the leave values. Concerning LightGBM, the companion article does not clearly declare whether pure gradient boosting is used or a hybrid variant. Mathematically speaking, this is the main difference between the packages. The other implementation differences include (i) the way they deal with large data, (ii) how they handle categorical features, and (iii) additional regularization and randomization options.

For more details, this article https://arxiv.org/abs/1808.03064 explains the difference between Newton and gradient booting.

Another package that uses Newton boosting is the KTBoost package. In addition to trees, you can also use kernel functions as base learners. See https://github.com/fabsig/KTBoost and https://arxiv.org/abs/1902.03999.

Disclaimer: I am the author of these articles.

$\endgroup$
  • $\begingroup$ Come on now. You can give a better answer than this. (Nice collection of papers) $\endgroup$ – usεr11852 Mar 31 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.