Почему xgboost намного быстрее, чем sklearn GradientBoostingClassifier?

Я пытаюсь обучить модели повышения градиента более чем на 50 тыс. Примеров с 100 числовыми функциями. XGBClassifierобрабатывает 500 деревьев в течение 43 секунд на моей машине, в то время как GradientBoostingClassifierобрабатывает только 10 деревьев (!) за 1 минуту и ​​2 секунды :( Я не стал пытаться вырастить 500 деревьев, так как это займет несколько часов. Я использую те же настройки learning_rateи max_depthнастройки , увидеть ниже.

Что делает XGBoost намного быстрее? Использует ли он какую-то новую реализацию для повышения градиента, которую не знают ребята из sklearn? Или это «срезание углов» и растущие более мелкие деревья?

PS Мне известно об этом обсуждении: https://www.kaggle.com/c/higgs-boson/forums/t/10335/xgboost-post-competition-survey, но я не смог получить ответ там ...

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)

Поскольку вы упоминаете «числовые» функции, я полагаю, что ваши функции не являются категориальными и имеют высокую степень достоверности (они могут принимать много разных значений, и, следовательно, существует много возможных точек разделения). В таком случае выращивание деревьев затруднено, так как есть [множество особенностей много точек разделения] для оценки.$\times$

Я предполагаю, что самый большой эффект связан с тем, что XGBoost использует приближение точек разделения. Если у вас есть непрерывная функция с 10000 возможными разбиениями, XGBoost по умолчанию рассматривает только «лучшие» 300 разбиений (это упрощение). Это поведение контролируется sketch_epsпараметром, и вы можете узнать больше об этом в документе . Вы можете попробовать опустить его и проверить разницу. Поскольку в документации по scikit-learn нет упоминания об этом , я думаю, что она недоступна. Вы можете узнать, что такое метод XGBoost в их статье (arxiv) .

XGBoost также использует приближение для оценки таких точек разделения. Я не знаю, по какому критерию учат скикиты, оценивает расщепления, но это может объяснить остальную разницу во времени.

Адресные комментарии

Что касается оценки точек разделения

Однако что вы имели в виду под «XGBoost также использует приближение для оценки таких точек разделения»? насколько я понимаю, для оценки они используют точное сокращение оптимальной целевой функции, как это показано в уравнении (7) в статье.

Чтобы оценить точку разделения, вам нужно будет вычислить где - это функция стоимости, цель, модель, построенная до сих пор, и текущее дополнение. Обратите внимание, что это не то, что делает XGBoost; они упрощают функцию стоимости с помощью расширения Тейлора, что приводит к очень простой для вычисления функции. Они должны вычислить Градиент и Гессиан относительно , и они могут повторно использовать это число для всех потенциальных расщеплений на этапе , делая быстрое вычисление наверху. Ты можешь проверить$L(y,H_{i-1}+h_i)$$L$$y$$H_{i-1}$$h_i$$L$$L$$H_{i-1}$$i$Функция потери Приближение с расширением Тейлора (CrossValidated Q / A) для получения более подробной информации, или вывод в их статье.

Дело в том, что они нашли способ аппроксимировать эффективно. Если бы вы оценивали полностью, без инсайдерских знаний, позволяющих оптимизировать, избегать или выполнять избыточные вычисления, на разделение потребовалось бы больше времени. В этом отношении это приблизительное значение. Тем не менее, другие реализации повышения градиента также используют функции стоимости прокси для оценки расщеплений, и я не знаю, является ли приближение XGBoost в этом отношении более быстрым, чем другие.$L(y,H_{i-1} + h_i)$$L$