Pourquoi xgboost est-il tellement plus rapide que sklearn GradientBoostingClassifier?

29

J'essaie de former un modèle d'augmentation de gradient sur plus de 50k exemples avec 100 fonctionnalités numériques. XGBClassifiergère 500 arbres en 43 secondes sur ma machine, alors qu'il GradientBoostingClassifierne gère que 10 arbres (!) en 1 minute et 2 secondes :( Je n'ai pas pris la peine d'essayer de faire pousser 500 arbres car cela prendra des heures. J'utilise les mêmes paramètres learning_rateet max_depth, voir ci-dessous.

Qu'est-ce qui rend XGBoost beaucoup plus rapide? Utilise-t-il une nouvelle implémentation pour augmenter le gradient que les gars de Sklearn ne connaissent pas? Ou s'agit-il de "couper les coins" et de faire pousser des arbres moins profonds?

ps Je suis au courant de cette discussion: https://www.kaggle.com/c/higgs-boson/forums/t/10335/xgboost-post-competition-survey mais je n'ai pas pu y trouver la réponse ...

XGBClassifier(base_score=0.5, colsample_bylevel=1, colsample_bytree=1,
gamma=0, learning_rate=0.05, max_delta_step=0, max_depth=10,
min_child_weight=1, missing=None, n_estimators=500, nthread=-1,
objective='binary:logistic', reg_alpha=0, reg_lambda=1,
scale_pos_weight=1, seed=0, silent=True, subsample=1)

GradientBoostingClassifier(init=None, learning_rate=0.05, loss='deviance',
max_depth=10, max_features=None, max_leaf_nodes=None,
min_samples_leaf=1, min_samples_split=2,
min_weight_fraction_leaf=0.0, n_estimators=10,
presort='auto', random_state=None, subsample=1.0, verbose=0,
warm_start=False)
ihadanny
la source
2
Je suppose que je vais bientôt devoir le reformuler comme "pourquoi LightGBM est-il tellement plus rapide que XGBoost?" :)
ihadanny

Réponses:

25

×

Je suppose que le plus grand effet vient du fait que XGBoost utilise une approximation sur les points de partage. Si vous avez une fonctionnalité continue avec 10000 divisions possibles, XGBoost ne considère que "les meilleures" 300 divisions par défaut (c'est une simplification). Ce comportement est contrôlé par le sketch_epsparamètre, et vous pouvez en savoir plus à ce sujet dans la doc . Vous pouvez essayer de l'abaisser et vérifier la différence que cela fait. Puisqu'il n'en est pas fait mention dans la documentation de scikit-learn , je suppose que ce n'est pas disponible. Vous pouvez apprendre quelle est la méthode XGBoost dans leur article (arxiv) .

XGBoost utilise également une approximation sur l'évaluation de ces points de partage. Je ne sais pas par quel critère scikit learn évalue les divisions, mais cela pourrait expliquer le reste de la différence de temps.


Adressage des commentaires

Concernant l'évaluation des points de partage

Cependant, que vouliez-vous dire par "XGBoost utilise également une approximation sur l'évaluation de ces points de partage"? pour autant que je sache, pour l'évaluation, ils utilisent la réduction exacte de la fonction objective optimale, telle qu'elle apparaît dans l'équation (7) de l'article.

L(y,Hi1+hi)LyHi1hiLLHi1i

L(y,Hi1+hi)L

Clins d'oeil
la source
Merci @Winks, j'ai lu le document et vois ce que vous vouliez dire par l'algorithme d'approximation pour choisir les candidats divisés. Cependant, que vouliez-vous dire par "XGBoost utilise également une approximation sur l'évaluation de ces points de partage"? pour autant que je sache, pour l'évaluation, ils utilisent la réduction exacte de la fonction objective optimale, telle qu'elle apparaît dans l'équation (7) de l'article.
ihadanny
J'ai modifié ma réponse pour répondre à votre commentaire. Consultez ce Q / R pour plus de détails sur l'évaluation des points de partage.
Clin d'
Merci beaucoup, @Winks! serait formidable si vous pouviez également répondre à ma question plus élaborée ici: datascience.stackexchange.com/q/10997/16050
ihadanny
C'est une excellente réponse. Tour de chapeau !
eliasah