XgboostがSklearn GradientBoostingClassifierよりもはるかに速いのはなぜですか？

Question

100の数値機能を備えた5万5万を超える例を勾配ブーストモデルをトレーニングしようとしています。 XGBClassifier マシンで43秒以内に500本の木を処理し、 GradientBoostingClassifier 1分2秒で10本の木（！）のみを処理します:(私は時間がかかるので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)

Answer 1

「数値」機能に言及しているので、あなたの機能はカテゴリではなく、高いアリティを持っていると思います（多くの異なる値をとることができます。したがって、可能な分割ポイントがたくさんあります）。そのような場合、評価するために[多くの機能$ times $ a Many Split Points]があるため、成長する木は困難です。

私の推測では、最大の効果は、Xgboostが分割点に近似を使用しているという事実に起因するということです。 10000の可能なスプリットを備えた連続機能がある場合、xgboostはデフォルトで「最高の」300スプリットのみを検討します（これは単純化です）。この動作は、によって制御されます sketch_eps パラメーター、そしてそれについてもっと読むことができます ドキュメントで. 。あなたはそれを下げて、それが生じる違いを確認することができます。それについて言及されていないので Scikit-Learnドキュメント, 、利用できないと思います。 xgboostメソッドが何であるかを学ぶことができます 彼らの論文（arxiv）.

Xgboostは、このような分割点の評価に近似も使用しています。 Scikit Learnがどの基準で分割を評価しているのかはわかりませんが、残りの時間差を説明できます。

---

アドレスコメント

スプリットポイントの評価に関して

しかし、「Xgboostは、そのような分割点の評価に近似も使用している」とはどういう意味ですか？私が理解している限り、評価のために、論文のeq（7）に表示されるように、最適な目的関数の正確な減少を使用しています。

分割点を評価するには、$ l（y、h_ {i-1}+h_i）$を計算する必要があります。ここで、$ l $はコスト関数、$ y $ターゲット、$ h_ {i-1}です。 $これまで構築されたモデル、および$ h_i $の現在の追加。これはXgboostが行っていることではないことに注意してください。彼らは、テイラー拡張によってコスト関数$ l $を簡素化しているため、非常に単純な関数が計算されます。彼らは$ h_ {i-1} $に対して$ l $の勾配とヘシアンを計算する必要があり、ステージ$ i $ですべての潜在的な分割に対してそれらの数値を再利用することができ、オーバーラル計算を速くすることができます。確認してもいい Taylor拡張による損失関数近似（交差検証Q/A） 詳細、または彼らの論文の派生。

ポイントは、彼らが$ l（y、h_ {i-1} + h_i）$を効率的に近似する方法を見つけたことです。最適化や回避、または冗長計算を可能にするインサイダーの知識なしで、$ l $を完全に評価する場合、分割あたりより多くの時間がかかります。これに関して、それは近似です。ただし、他のグラデーションブースト実装もプロキシコスト関数を使用して分割を評価します。これは、この点でXgboost近似が他の点よりも速いかどうかはわかりません。