【論文紹介】A speed-optimized and cache-friendly implementation of stochastic gradient-boosted decision trees for multivariate classification
論文のダウンロード先
論文の内容
Gradient Boosting Decision Treeの高速化を、特徴量の構造を工夫してCPUキャッシュヒットしやすくすることによって、より高速化したという論文。
XGBoostよりシングルコア比較で2.2倍速く，マルチコア比較で3.8倍速い。また他のライブラリ(e.g. xgboost)より推定精度も向上したとのこと。
内容
- 多クラス分類問題とか、線形問題においてGradient Boosting Decision Treeが最近よく使われている。
- 本論文では計算処理を最適化、キャッシュ処理の最適化をとくに考慮したFastBSD(の提案手法及び実装)を提案。
- 高速化手法の具体的な方法は以下の通り
- 特徴量の整数化、一様分布化
- CPUキャッシュの特徴を考慮した推定
- 従来の特徴量のメモリ内での持ち方はstruct of arrays。これをFASTBSDではarray of structs構造を採用。これをやることによってCPUのメモリキャッシュのヒット率を上げる。
評価
- gradient-boosted decision treesを実装したライブラリを評価
- scikit-learn
- XGBoost(シングルスレッド)
- TMVA
- XGBoost-i7(マルチコア)
- FastBSD(提案手法)
- 評価に利用したデータ・セット
- 100件のデータポイント、35次元の特徴量。人工データ(モンテカルロを利用)
- データ・セットを各ライブラリ向けのフォーマットに変換
- ハイパーパラメータは以下の通り
- depth of the trees = 3
- number of trees = 100
- number of features = 35
- number of training data-points = 500000 • sampling-rate = 0.5
- shrinkage = 0.1
結果
- 推定モデルの生成速度
XGBoostよりシングルコア比較で2.2倍速く，マルチコア比較で3.8倍速い
- 推定精度
基本的に他の手法を上回る。例外としてはtreeを深くしていった場合。
過学習がおきてしまって精度がxgboostに劣る。理由はxgboostの何らかの過学習対策が寄与している？
- ツールとして実装でできていないこと。
- Negative Weights
- 欠損値のサポート
- 特徴量重要度の表示
所感
- xgboostを利用してhyperparameterチューニングとかCVとかやると計算が膨大になるので、そういった意味で高速化手法が出てくるのは嬉しい。
- なぜ精度がよくなるかがいまいち不明。
- 論文では整数化&特徴量の一様分布化をすることによって、過学習がおきなくなっている、といっているけど確信がないので、追加調査が必要
