Kaggle Days TokyoでのGBDT実装の話

先日行われたKaggle Days Tokyoで発表した資料になります。

前半は主に外国の方向けのKaggle本の紹介、後半はGBDTをスクラッチ実装する話です。
拙い英語ですが、雰囲気で読んで下さい。ちょっと説明に優しさが足りない気もしますね。直前にKaggle Santaコンペをやっていたのが良くない。。

speakerdeck.com

コードはこちらです。Cython版でxgboostの1/4くらいの速度でまぁまぁな速さです。
sklearnやxgboostのコードを読むと、抽象化やいろいろなケースに対応するためのコードがあってアルゴリズムを理解するのに苦労するのですが、 シンプルにアルゴリズム部分が分かりやすいような書き方にしたつもりです。 www.kaggle.com www.kaggle.com

他にも、@nyker_gotoさんの実装を教えて頂いたのでご紹介します。

github.com


帰りにJackさんと少し話したのですが、私が気づいたxgboostの工夫は以下です。

  • ノードごとにデータを走査すると、計算量がO（ノード）になってしまう。
    深さごとにデータを走査し、データの属するノードに応じて処理を行うようにすると、計算量をO（深さ）にできる。
  • SortedCSCPageという構造を使い、データを疎に保持するようにしている。
    欠損値が多い場合などはその分スキップできるので速くなる。

xgboostのコードリーディング（その３）

前回（xgboostのコードリーディング（その２） - threecourse’s blog）の続きで、一旦これで完結のつもりです。 前回同様、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。

今回は、もはやxgboostではないのですが、lightgbmのEFB(Exclusive Feature Bundling)という機能でなぜ速くなるのかを説明します。 コードリーディングの発端の発端はここで、この機能でなぜ速くなる理由がわからず気持ち悪かったことにあります。 Kaggle本の執筆でも、途中まではEFBを説明に加えていたのですが、理由を説明できないにもかかわらず記載するのは良くないと思い、削りました。

EFB(Exclusive Feature Bundling）の概要

EFBとは、排他な特徴量をまとめて計算することにより計算量を削減する方法。
排他な特徴量とは、互いに（ほぼ）同時に0以外の値をとらない特徴量で、まとめ方も含めて以下の図のようなイメージとなる。

f:id:threecourse:20191031140356j:plain

ここで、例えばone-hot encodingによる特徴量があれば、それをlabel encodingのように一つの特徴量に戻して分岐の計算を行う・・・と思ってしまうがそうではなく、 あくまでhistogram-basedのヒストグラムの作成でEFBによりバンドルされた特徴量を利用することで計算量を削減し、分岐の計算においては、バンドルされたものでなく元の特徴量を使って計算する。

（参考）
LightGBM: A Highly Efficient Gradient Boosting Decision Tree
NIPS2017読み会 LightGBM: A Highly Efficient Gradient Boosting Decision T…
What makes LightGBM lightning fast? - Abhishek Sharma - Medium

EFBによる計算量の削減

lightgbmは、前回説明したhistogram-basedアルゴリズムにより計算が行われる。ここでは、分岐の作成の部分のみ説明する。
それぞれの葉における分岐の作成では、以下の2つの処理を行う。

  1. ヒストグラムを作成する
  2. 最も良く分割できる分岐の計算を行う

ここで、以下のような流れとなる。

  1. ヒストグラムを作成するときに、
    EFBによって計算量をO（データ数 x 特徴量の数）からO（データ数 x バンドルの数）に落とす
  2. 最も良く分割できる分岐の計算を行うときに、
    バンドルにした特徴量を元に戻して計算する。この計算量はO（ビンの数 x 特徴量の数）である

ヒストグラムを作成する部分は計算量の支配的な部分であり、その部分の計算量を落とすことができる。

コード（メモ）

lightgbmの計算の流れは以下のとおり：

1. python-package/lightgbm/engine.pyのtrainメソッド

学習において、決定木の作成ごとに、BoosterクラスのUpdateメソッドを通して、c++のメソッド_LIB.LGBM_BoosterUpdateOneIterを呼び出す

2. src/c_api.cppのLGBM_BoosterUpdateOneIterメソッド

GBDTクラス（＝Boosterクラスの派生クラス）のTrainOneIterを呼び出す。

3. src/boosting/gbdt.cppのGBDTクラスのTrainOneIterメソッド
  • （各データの勾配を求める処理は省略）
  • SerialTreeLearnerクラス（＝TreeLearnerクラスの派生クラス）のTrainメソッドを呼び出し、決定木を作成する
4. src/treelearner/serial_tree_learner.cppのSerialTreeLearnerクラスのTrainメソッド

作成する葉の数だけ、SerialTreeLearnerクラスのFindBestSplitsメソッドを繰り返す。
FindBestSplitsメソッドでは、以下の処理を行う。

  1. SerialTreeLearner::ConstructHistogramsメソッドにより、ヒストグラムを作成する
  2. SerialTreeLearner::FindBestSplitsFromHistogramsメソッドにより、最も良い分岐を作成する
5. src/treelearner/serial_tree_learner.cppのSerialTreeLearnerクラスのConstructHistogramsメソッド

DatasetクラスのConstructHistogramsメソッドを呼び出す。 DatasetクラスのConstructHistogramsメソッドでは、特徴量のバンドルごとに、DenseBinクラスのConstructHistogramメソッドを呼び出してヒストグラムのアップデートを行う

6. src/treelearner/serial_tree_learner.cppのSerialTreeLearnerクラスのFindBestSplitsFromHistogramsメソッド

特徴量のバンドルからそれぞれの特徴量に戻し、特徴量ごとにFeatureHistogramクラスのFindBestThresholdメソッドを実行する

"Data Analysis Techniques to Win Kaggle" table of contents /「Kaggleで勝つデータ分析の技術」の目次

This is table of contents of a book "Data Analysis Techniques to Win Kaggle (amazon.co.jp) written in Japanese and published on Oct. 2019. Authors are threecourse, Jack, hskksk, maxwell .

en ja
Data Analysis Techniques to Win Kaggle Kaggleで勝つデータ分析の技術
Chapter I: What is data analysis competition? 第1章 分析コンペとは?
1.1 what is data analysis competition? 1.1 分析コンペって何?
1.1.1 what do you do in competition? 1.1.1 何をするものか
1.1.2 submission and leaderboard 1.1.2 予測結果の提出と順位表(Leaderboard)
1.1.3 team 1.1.3 チームでの参加
1.1.4 prize 1.1.4 入賞賞金・特典
1.2 data analysis competition platform 1.2 分析コンペのプラットフォーム
1.2.1 Kaggle 1.2.1 Kaggle
1.2.2 Rankings 1.2.2 Rankings(ランキング・称号制度)
1.2.3 Kernel 1.2.3 Kernel
1.2.4 Discussion 1.2.4 Discussion
1.2.5 Datasets 1.2.5 Datasets
1.2.6 API 1.2.6 API
1.2.7 Newsfeed 1.2.7 Newsfeed
1.2.8 types of competitions and examples 1.2.8 開催された分析コンペの種類と具体例
1.2.9 formats of competitions 1.2.9 分析コンペのフォーマット
1.3 from start to finish in competition 1.3 分析コンペに参加してから終わるまで
1.3.1 participate in competition 1.3.1 分析コンペに参加
1.3.2 concent to terms 1.3.2 規約に同意
1.3.3 download data 1.3.3 データをダウンロード
1.3.4 prediction 1.3.4 予測値の作成
1.3.5 submission 1.3.5 予測値の提出
1.3.6 check Public Leaderboard 1.3.6 Public Leaderboardをチェック
1.3.7 select final submissions 1.3.7 最終予測値を選ぶ
1.3.8 check Private Leaderboard 1.3.8 Private Leaderboardをチェック
1.4 what do you participate for? 1.4 分析コンペに参加する意義
1.4.1 prize 1.4.1 賞金を得る
1.4.2 performance tiers and ranking 1.4.2 称号やランキングを得る
1.4.3 experience to analyze real data 1.4.3 実データを用いた分析の経験・技術を得る
1.4.4 connection to data scentists 1.4.4 データサイエンティストとのつながりを得る
1.4.5 job oppotunity 1.4.5 就業機会を得る
1.5 key points to win 1.5 上位を目指すためのポイント
1.5.1 tasks and metrics 1.5.1 タスクと評価指標
1.5.2 feature engineering 1.5.2 特徴量の作成
1.5.3 modelling 1.5.3 モデルの作成
1.5.4 validation 1.5.4 モデルの評価
1.5.5 model tuning 1.5.5 モデルのチューニング
1.5.6 ensemble 1.5.6 アンサンブル
1.5.7 workflow in competition 1.5.7 分析コンペの流れ
column - computational resources Column 計算リソース
Chapter II Tasks and Metrics 第2章 タスクと評価指標
2.1 types of tasks 2.1 分析コンペにおけるタスクの種類
2.1.1 regression 2.1.1 回帰タスク
2.1.2 classification 2.1.2 分類タスク
2.1.3 recommendation 2.1.3 レコメンデーション
2.1.4 other tasks 2.1.4 その他のタスク
2.2 datasets 2.2 分析コンペのデータセット
2.2.1 table data 2.2.1 テーブルデータ
2.2.2 external data 2.2.2 外部データ
2.2.3 time-series data 2.2.3 時系列データ
2.2.4 image and natural language 2.2.4 画像や自然言語などのデータ
2.3 evalution metrics 2.3 評価指標
2.3.1 what is evaluation metrics? 2.3.1 評価指標(evaluation metrics)とは
2.3.2 metrics for regression 2.3.2 回帰における評価指標
2.3.3 metrics for binary classification - when predict binary label 2.3.3 二値分類における評価指標〜正例か負例かを予測値とする場合
2.3.4 metrics for binary classification - when predict probability 2.3.4 二値分類における評価指標〜正例である確率を予測値とする場合
2.3.5 metrics for multi-class classification 2.3.5 多クラス分類における評価指標
2.3.6 metrics for recommendation 2.3.6 レコメンデーションにおける評価指標
2.4 evaluation metrics and objective function 2.4 評価指標と目的関数
2.4.1 difference between evaluation metrics and objective function 2.4.1 評価指標と目的関数の違い
2.4.2 custom metrics and custom objective function 2.4.2 カスタム評価指標とカスタム目的関数
2.5 metrics optimization 2.5 評価指標の最適化
2.5.1 approaches to metrics optimization 2.5.1 評価指標の最適化のアプローチ
2.5.2 optimize threshold 2.5.2 閾値の最適化
2.5.3 optimize threshold with out-of-fold 2.5.3 閾値の最適化をout-of-foldで行うべきか?
column - out-of-fold Column out-of-foldとは?
2.5.4 predicted probability and its adjustment 2.5.4 予測確率とその調整
2.6 cases of metrics optimization 2.6 評価指標の最適化の例
2.6.1 optimize balanced accuracy 2.6.1 balanced accuracyの最適化
2.6.2 optimize mean-F1 threshold 2.6.2 mean-F1における閾値の最適化
2.6.3 optimize quadratic weighted kappa threshold 2.6.3 quadratic weighted kappaにおける閾値の最適化
2.6.4 optimize MAE with custom objective function 2.6.4 カスタム目的関数での評価指標の近似によるMAEの最適化
2.6.5 approximate MCC with PR-AUC 2.6.5 MCCのPR-AUCによる近似とモデル選択
2.7 leakage 2.7 リーク(data leakage)
2.7.1 unexpected information leakage by host 2.7.1 予測に有用な情報が想定外に漏れている意味でのリーク
2.7.2 wrong validation scheme by participant 2.7.2 バリデーションの枠組みの誤りという意味でのリーク
Chapter III feature engineering 第3章 特徴量の作成
3.1 structure of this chapter 3.1 本章の構成
3.2 model and features 3.2 モデルと特徴量
3.2.1 model and features 3.2.1 モデルと特徴量
3.2.2 baseline feature engineering 3.2.2 ベースラインとなる特徴量
3.2.3 think as if I were a decision tree 3.2.3 決定木の気持ちになって考える
3.3 handle missing values 3.3 欠損値の扱い
3.3.1 use missing values as-is 3.3.1 欠損値のまま取り扱う
3.3.2 fill by statistic values 3.3.2 欠損値を代表値で埋める
3.3.3 predict missing values with other variables 3.3.3 欠損値を他の変数から予測する
3.3.4 create features from missing values 3.3.4 欠損値から新たな特徴量を作成する
3.3.5 recognize missing value in data 3.3.5 データ上の欠損の認識
3.4 transform numerical variable 3.4 数値変数の変換
3.4.1 standarization 3.4.1 標準化(standardization)
column - scaling using only train data or concatenating train and test data Column データ全体の数値を利用して変換を行うときに、
学習データのみを使うか、テストデータも使うか
3.4.2 min-max scaling 3.4.2 Min-Maxスケーリング
3.4.3 non-linear transformation 3.4.3 非線形変換
3.4.4 clipping 3.4.4 clipping
3.4.5 binning 3.4.5 binning
3.4.6 ranking 3.4.6 順位への変換
3.4.7 rankgauss 3.4.7 RankGauss
3.5 transform categorical variable 3.5 カテゴリ変数の変換
3.5.1 one-hot encoding 3.5.1 one-hot encoding
3.5.2 label encoding 3.5.2 label encoding
3.5.3 feature hashing 3.5.3 feature hashing
3.5.4 frequency encoding 3.5.4 frequency encoding
3.5.5 target encoding 3.5.5 target encoding
3.5.6 embedding 3.5.6 embedding
3.5.7 handle ordinal variable 3.5.7 順序変数の扱い
3.5.8 extract information from categorical variable 3.5.8 カテゴリ変数の値の意味を抽出する
3.6 transform datetime variable 3.6 日付・時刻を表す変数の変換
3.6.1 key points to transfrom datetime variable 3.6.1 日付・時刻を表す変数の変換のポイント
3.6.2 features from datetime variable 3.6.2 日付・時刻を表す変数の変換による特徴量
3.7 combine variables 3.7 変数の組み合わせ
3.8 merge other tables 3.8 他のテーブルの結合
3.9 aggregation and statistics 3.9 集約して統計量をとる
3.9.1 take simple statistics 3.9.1 単純な統計量をとる
3.9.2 take temporal statistics 3.9.2 時間的な統計量をとる
3.9.3 filter 3.9.3 条件を絞る
3.9.4 change aggregation units 3.9.4 集計する単位を変える
3.9.5 focus on item, not only user 3.9.5 ユーザ側でなく、アイテム側に注目する
3.10 time-series data 3.10 時系列データの扱い
3.10.1 time-series data 3.10.1 時系列データとは?
3.10.2 use only information prior to prediction point of time 3.10.2 予測する時点より過去の情報のみを使う
3.10.3 wide and long format 3.10.3 ワイドフォーマットとロングフォーマット
3.10.4 lag feature 3.10.4 ラグ特徴量
3.10.5 create feature correspoding to point of time 3.10.5 時点と紐付いた特徴量を作る
3.10.6 time range available for prediction 3.10.6 予測に使えるデータの期間
3.11 dimension reduction and unsupervised learning 3.11 次元削減・教師なし学習による特徴量
3.11.1 principal component analysis (PCA) 3.11.1 主成分分析(PCA)
3.11.2 non-negative matrix factorization (NMF) 3.11.2 非負値行列因子分解(NMF)
3.11.3 latent dirichlet allocation (LDA) 3.11.3 Latent Dirichlet Allocation(LDA)
3.11.4 linear discriminant analysis (LDA) 3.11.4 線形判別分析(LDA)
3.11.5 t-SNE, UMAP 3.11.5 t-SNE、UMAP
3.11.6 auto-encoder 3.11.6 オートエンコーダ
3.11.7 clustering 3.11.7 クラスタリング
3.12 other techniques 3.12 その他のテクニック
3.12.1 focus on mechanisms underlying 3.12.1 背景にあるメカニズムから考える
3.12.2 focus on relationship between records 3.12.2 レコード間の関係性に注目する
3.12.3 focus on relative values 3.12.3 相対値に注目する
3.12.4 focus on location 3.12.4 位置情報に注目する
3.12.5 NLP methods 3.12.5 自然言語処理の手法
3.12.6 apply NLP methods to data other than natural language 3.12.6 自然言語処理の手法の応用
3.12.7 apply topic model to transform categorical variables 3.12.7 トピックモデルの応用によるカテゴリ変数の変換
3.12.8 image features 3.12.8 画像特徴量を扱う手法
3.12.9 decision tree feature transformation 3.12.9 decision tree feature transformation
3.12.10 deanonymize anonymized data 3.12.10 匿名化されたデータの変換前の値を推測する
3.12.11 correct errors in data 3.12.11 データの誤りを修正する
3.13 cases of feature engineering in competition 3.13 分析コンペにおける特徴量の作成の例
3.13.1 Kaggle - Recruit Restaurant Visitor Forecasting 3.13.1 Kaggleの「Recruit Restaurant Visitor Forecasting」
3.13.2 Kaggle - Santander Product Recommendation 3.13.2 Kaggleの「Santander Product Recommendation」
3.13.3 Kaggle - Instacart Market Basket Analysis 3.13.3 Kaggleの「Instacart Market Basket Analysis」
3.13.4 KDD Cup 2015 3.13.4 KDD Cup 2015
3.13.5 other techniques in competition 3.13.5 分析コンペにおけるその他のテクニックの例
Chapter IV Modeling 第4章 モデルの作成
4.1 what is model? 4.1 モデルとは何か?
4.1.1 what is model? 4.1.1 モデルとは何か?
4.1.2 workflow of modeling 4.1.2 モデル作成の流れ
4.1.3 terms and points of modeling 4.1.3 モデルに関連する用語とポイント
4.2 models used in competition 4.2 分析コンペで使われるモデル
4.3 GBDT(gradient boosting decision tree) 4.3 GBDT(勾配ブースティング木)
4.3.1 overview of GBDT 4.3.1 GBDTの概要
4.3.2 characteristics of GBDT 4.3.2 GBDTの特徴
4.3.3 major libraries of GBDT 4.3.3 GBDTの主なライブラリ
4.3.4 how to use GBDT 4.3.4 GBDTの実装
4.3.5 points to use xgboost 4.3.5 xgboostの使い方のポイント
4.3.6 lightgbm 4.3.6 lightgbm
4.3.7 catboost 4.3.7 catboost
column - xgboost algorithm Column xgboostのアルゴリズムの解説
4.4. neural network 4.4 ニューラルネット
4.4.1 overview of neural network 4.4.1 ニューラルネットの概要
4.4.2 characteristics of neural network 4.4.2 ニューラルネットの特徴
4.4.3 major libraries of neural network 4.4.3 ニューラルネットの主なライブラリ
4.4.4 how to use neural network 4.4.4 ニューラルネットの実装
4.4.5 points to use keras 4.4.5 kerasの使い方のポイント
4.4.6 solution references - multi layer perceptron 4.4.6 参考になるソリューション - 多層パーセプトロン
4.4.7 solution references - recent neural network developments 4.4.7 参考になるソリューション - 最近のニューラルネットの発展
4.5 linear model 4.5 線形モデル
4.5.1 overview of linear model 4.5.1 線形モデルの概要
4.5.2 characteristics of linear model 4.5.2 線形モデルの特徴
4.5.3 major libraries of linear model 4.5.3 線形モデルの主なライブラリ
4.5.4 how to use linear model 4.5.4 線形モデルの実装
4.5.5 points to use linear model 4.5.5 線形モデルの使い方のポイント
4.6 other models 4.6 その他のモデル
4.6.1 k-nearest neighbor algorithm (kNN) 4.6.1 k近傍法(k-nearest neighbor algorithm、kNN)
4.6.2 random forest (RF) 4.6.2 ランダムフォレスト(Random Forest、RF)
4.6.3 extremely randomized trees (ERT) 4.6.3 Extremely Randomized Trees(ERT)
4.6.4 regularized greedy forest (RGF) 4.6.4 Regularized Greedy Forest(RGF)
4.6.5 field-aware factorization machines (FFM) 4.6.5 Field-aware Factorization Machines(FFM)
4.7 other points and techniques 4.7 モデルのその他のポイントとテクニック
4.7.1 when there are missing values 4.7.1 欠損値がある場合
4.7.2 when features are many 4.7.2 特徴量の数が多い場合
4.7.3 when target is not correspended to a record 4.7.3 目的変数に1対1で対応するテーブルでない場合
4.7.4 pseudo labeling 4.7.4 pseudo labeling
columns - structure of directories and classes for competition Column 分析コンペ用のクラスやフォルダの構成
Chapter V Validation 第5章 モデルの評価
5.1 what is validation? 5.1 モデルの評価とは?
5.2 validation methods 5.2 バリデーションの手法
5.2.1 hold-out 5.2.1 hold-out法
5.2.2 cross validation 5.2.2 クロスバリデーション
5.2.3 stratified k-fold 5.2.3 stratified k-fold
5.2.4 group k-fold 5.2.4 group k-fold
5.2.5 leave-one-out 5.2.5 leave-one-out
5.3 validation methods for time-series data 5.3 時系列データのバリデーション手法
5.3.1 temporal hold-out 5.3.1 時系列データのhold-out法
5.3.2 temporal cross validation(temporal order aware) 5.3.2 時系列データのクロスバリデーション(時系列に沿って行う方法)
5.3.3 temporal cross validation(temporal order ignorant) 5.3.3 時系列データのクロスバリデーション(単純に時間で分割する方法)
5.3.4 points of time-series data validation 5.3.4 時系列データのバリデーションの注意点
5.3.5 Kaggle - Recruit Restaurant Visitor Forecasting 5.3.5 Kaggleの「Recruit Restaurant Visitor Forecasting」
5.3.6 Kaggle - Santander Product Recommendation 5.3.6 Kaggleの「Santander Product Recommendation」
5.4 validation points and techniques 5.4 バリデーションのポイントとテクニック
5.4.1 purpose of validation 5.4.1 バリデーションを行う目的
5.4.2 mimic split of train and test data 5.4.2 学習データとテストデータの分割をまねる
5.4.3 when distribution between train and test data is different 5.4.3 学習データとテストデータの分布が違う場合
5.4.4 utilize leaderboard 5.4.4 Leaderboardの情報を利用する
5.4.5 "overfit" to validation data or Public Leaderboard 5.4.5 バリデーションデータやPublic Leaderboardへの過剰な適合
5.4.6 create feature for each cross validation split 5.4.6 クロスバリデーションのfoldごとに特徴量を作り直す
5.4.7 augment train data 5.4.7 使える学習データを増やす
Chapter VI Model Tuning 第6章 モデルのチューニング
6.1 hyper-parameter tuning 6.1 パラメータチューニング
6.1.1 hyper-parameter search methods 6.1.1 ハイパーパラメータの探索手法
6.1.2 things to set in parameter tuning 6.1.2 パラメータチューニングで設定すること
6.1.3 points in parameter tuning 6.1.3 パラメータチューニングのポイント
6.1.4 Bayesian optimization 6.1.4 ベイズ最適化でのパラメータ探索
6.1.5 GBDT parameters and tuning 6.1.5 GBDTのパラメータおよびそのチューニング
column - xgboost parameter tuning Column xgboostの具体的なパラメータチューニングの方法
6.1.6 neural net parameters and tuning 6.1.6 ニューラルネットのパラメータおよびそのチューニング
column - MLP parameter tuning Column 多層パーセプトロンの具体的なパラメータチューニングの方法
6.1.7 linear model parameter tuning 6.1.7 線形モデルのパラメータおよびそのチューニング
6.2 feature selection and feature importances 6.2 特徴選択および特徴量の重要度
6.2.1 univariate statistics 6.2.1 単変量統計を用いる方法
6.2.2 feature importances 6.2.2 特徴量の重要度を用いる方法
6.3.3 iterative selection 6.2.3 反復して探索する方法
6.3 imbalanced data 6.3 クラスの分布が偏っている場合
column - algorithms of Baysian Optimization and TPE Column ベイズ最適化およびTPEのアルゴリズム
Chapter VII Ensemble 第7章 アンサンブル
7.1 what is ensemble? 7.1 アンサンブルとは?
7.2 simple ensemble methods 7.2 シンプルなアンサンブル手法
7.2.1 average and weighted average 7.2.1 平均、加重平均
7.2.2 voting and weighted voting 7.2.2 多数決、重みづけ多数決
7.2.3 points and other techniques 7.2.3 注意点とその他のテクニック
7.3 stacking 7.3 スタッキング
7.3.1 overview of stacking 7.3.1 スタッキングの概要
7.3.2 stacking as a method to create feature 7.3.2 特徴量作成の方法としてのスタッキング
7.3.3 how to use stacking 7.3.3 スタッキングの実装
7.3.4 points of stacking 7.3.4 スタッキングのポイント
7.3.5 ensemble using hold-out prediction 7.3.5 hold-outデータへの予測値を用いたアンサンブル
7.4 what models should be included for ensemble? 7.4 どんなモデルをアンサンブルすると良いか?
7.4.1 diverse models 7.4.1 多様なモデルを使う
7.4.2 different hyper-paramters 7.4.2 ハイパーパラメータを変える
7.4.3 different features 7.4.3 特徴量を変える
7.4.4 differnet interpretation of task 7.4.4 問題のとらえ方を変える
7.5.4 model selection for ensemble 7.4.5 スタッキングに含めるモデルの選択
7.5 cases in competition 7.5 分析コンペにおけるアンサンブルの例
7.5.1 Kaggle - Otto Group Product Classification Challenge 7.5.1 Kaggleの「Otto Group Product Classification Challenge」
7.5.2 Kaggle - Home Depot Product Search Relevance 7.5.2 Kaggleの「Home Depot Product Search Relevance」
7.5.3 Kaggle - Home Credit Default Risk 7.5.3 Kaggleの「Home Credit Default Risk」

xgboostのコードリーディング（その２）

前回（xgboostのコードリーディング - threecourse’s blog）の続きです。
前回同様、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。

pre-sortedアルゴリズムとhistogram-basedアルゴリズム

決定木を作成するアルゴリズムとして、pre-sortedとhistogram-basedというアルゴリズムがある。
（参考） NIPS2017読み会 LightGBM: A Highly Efficient Gradient Boosting Decision T…

xgboostでは、

pre-sortedでは、以下のような計算の流れとなる。

  1. 予め、特徴量ごとに、特徴量の値でソートしたデータへの参照を作成しておく
  2. 深さごとに、特徴量ごとに、ソートされたデータを走査してそれぞれの葉の分割点を決める

（参考）XGBoost: A Scalable Tree Boosting System のAlgorithm 1: Exact Greedy Algorithm for Split Finding

histogram-basedでは、以下のような計算の流れとなる。

  1. 予め、特徴量ごとにヒストグラムを作り、各データがどのbinに属するかを求めておく。
  2. 深さごとに、

(参考） LightGBM: A Highly Efficient Gradient Boosting Decision Tree のAlgorithm 1: Histogram-based Algorithm

計算量を考えたときに、histogram-basedでは、以下のようなメリットがある。

  • 深さごとに、
    • ヒストグラム作成部分の計算量はO（特徴量 x データ数）
    • 分割点の計算部分の計算量はO（特徴量 x ビンの数）

    となり、ヒストグラム作成部分が支配的となり、O（特徴量 x データ数）となることに変わりはない。
    ただし、ヒストグラム作成の処理の方が分割点の計算の処理より軽いために速くなる。

  • 分岐を行い、左の葉のヒストグラムを求めたとする。すると、右の葉のヒストグラムは親から左の葉のヒストグラムを引き算して計算することができ、O（特徴量 x データ数）でなく、O(特徴量 x ビンの数）で計算できるため、その部分の計算量が無視できる。（データ数の方がビンの数より十分に多い前提で考えている）
  • 葉ごとにその葉に属するデータ（のインデックス）のリストを持たせることができるため、深さ単位でなく葉単位での木の成長が行えるようになる。pre-sortedでは、特徴量の値ごとにソートされている必要があるため、このように葉ごとにリストを持たせることは行いにくい。histogram-basedでは、属するビンが分かればソートされている必要はない。

結局、1本の決定木を作る計算量のオーダーは、O(データ数 x 特徴量の数 x 深さ)で変わらないものの、定数倍が効いてhistogram-basedの方が速くなる、と理解している。

xgboostのapproxとhistの違い

xgboostのtree_methodには、exactの他にapproxとhistのオプションがある。
approxとhistの違いについては、以下で説明されている。
[New Feature] Fast Histogram Optimized Grower, 8x to 10x Speedup · Issue #1950 · dmlc/xgboost · GitHub

このIssueによると、ヒストグラムを作る点は同じであるが、イテレーションごとにヒストグラムを作り直すapproxと、使いまわすhistの違いがあり、histの場合だと以下のような高速化が可能になるとのこと。

  • Cache of the bins: 連続変数をbinのインデックスとし、データの構造をキャッシュする
  • Histogram subtraction trick: ヒストグラムを作成するときに、親と兄弟のヒストグラムの差をとる

Histogram subtraction trickは理解できたが、Cache of the binsはどう利用されているのか良くわからなかった。また、イテレーションごとにヒストグラムを作り直す`approx'でも、Histogram subtraction trickは実行できる気がする。

tree_method=approxでの学習の流れ（メモ）

tree_method=approxでは、決定木ごとに同じヒストグラムを使用する"global"と分岐ごとにヒストグラムを作成し直す"local"の2つの手法があるが、デフォルトでは"global"となり、UpdaterとしてColMakerの代わりにGlobalProposalHistMakerが利用される。
（なおGlobalProposalHistMakerは、HistMakerの派生クラスのCQHistMakerの派生クラス）

学習の流れは以下のようになる：

  1. HistMakerのUpdateメソッド

    • HistMakerのUpdateメソッド(オーバーライドされたprivateの方) を呼び出す。
    • HistMakerのprivateのUpdateメソッドでは、
      各深さごとに、CreateHistメソッド、FindSplitメソッドを呼び出す。
      （初期化処理やその他のメソッドは省略）

  2. GlobalProposalHistMakerのCreateHistメソッド
    特徴量ごとに、CQHistMakerのUpdateHistColメソッドを呼び出す。
    UpdateHistColメソッドでは、各データについて、対応するビンの値をアップデートする。

  3. HistMakerのFindSplitメソッド
    特徴量ごとに、HistMakerのEnumerateSplitメソッドを呼び出す。
    EnumerateSplitメソッドでは、ヒストグラムの走査を行う。

tree_method=histでの学習の流れ（メモ）

tree_method=histの場合、QuantileHistMakerが利用される。深さ単位で成長するdepthwiseか葉ごとに成長するlossguideが選べるが、以下はデフォルトのdepthwiseの学習の流れとなる。

  1. QuantileHistMakerのUpdateメソッド
    GHistIndexMatrixのInitメソッドで前処理を行ったあと、QuantileHistMaker::BuilderのUpdateメソッドが呼び出される

  2. QuantileHistMaker::BuilderのUpdateメソッド
    depthwiseの場合は、ExpandWithDepthWiseメソッドが呼び出される

  3. QuantileHistMaker::BuilderのExpandWithDepthWiseメソッド

    深さごとに、以下のメソッドが順に呼び出される

    1. BuildHistsBatch
    2. BuildNodeStatBatch
    3. EvaluateSplitsBatch
    4. CreateNewNodesBatch

  4. QuantileHistMaker::BuilderのBuildHistsBatchメソッド
    ヒストグラムを作成する
    一定のデータ数ごとにtaskに分けて分散処理できるようにしている様子

  5. QuantileHistMaker::BuilderのBuildNodeStatBatchメソッド
    葉の情報を更新する
  6. QuantileHistMaker::BuilderのEvaluateSplitsBatchメソッド
    ヒストグラムから分割点を求める
  7. QuantileHistMaker::BuilderのCreateNewNodesBatchメソッド
    新しい葉を作成する
    一見複雑なことをやっているように見えるが、単に分岐に基づいてデータを葉に振り分けているだけのように思える

xgboostのコードリーディング

xgboostでどのような処理が行われているのかを、メモの意味でまとめてみました。
たぶん続きます。なお、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。

ソースコードは以下を参照しています。
https://github.com/dmlc/xgboost (release_0.90を参照)

前提

以下の前提とする:

  • ブースター(booster)はgbtree
  • 決定木のアルゴリズム（tree_method）はexact
  • カスタム目的関数を使わない
  • GPUの使用、マシン並列を行わない

xgboostでは、tree_methodオプションで決定木を作成するアルゴリズムを選択できる。
デフォルトではデータ数が一定未満の場合にはexact、それ以上であればapproxが適用される。
(4UL << 20UL = 4194304件が境目、GBTree::PerformTreeMethodHeuristicメソッド参照） また、histを設定することで、lightgbmのようなヒストグラムを用いた手法を利用できる。

学習の流れ

以下のようなPythonコードを呼び出すとする。

import xgboost as xgb
# param, dtrain, num_roundには適当な値が入っているとする
bst = xgb.train(param, dtrain, num_round)

このとき、xgb.trainでは、以下のように学習が実行される。

1. python-package/xgboost/training.pyのtrainメソッド

そこから_train_internalメソッドを呼びだして学習を行う。
学習において、決定木の作成ごとに、BoosterクラスのUpdateメソッドを通して、c++のメソッド_LIB.XGBoosterUpdateOneIterを呼び出す

2. src/c_api/c_api.ccのXGBoosterUpdateOneIterメソッド

LearnerImplクラスのUpdateOneIterを呼び出す。

3. src/learner.ccのLearnerImplクラスのUpdateOneIterメソッド
  • ObjFunctionクラスのGetGradientメソッドを呼び出し、各データの勾配を求める（この部分の説明は省略）
  • GBTreeクラスのDoBoostメソッドを呼び出し、決定木を作成する
4. src/gbm/gbtree.ccのGBTreeクラスのDoBoostメソッド

BoostNewTreesメソッドを呼び出す。
BoostNewTreesメソッドの中で、各updaterについてUpdateを行う。
今回の設定では、updaterはColMakerとTreePrunerの2つであり、ColMakerクラスのUpdateメソッドが木を作成する部分の本体と言える。（TreePrunerの説明は省略） なお、tree_methodによりupdaterが変わり、アルゴリズムの変更が反映される。今回はexactなのでColMakerが使われるがapproxであればHistMaker、histであればQuantileHistMakerが使われる。

5. src/tree/updater_colmaker.ccのColMakerクラスのUpdateメソッド

ColMaker::BuilderクラスのUpdateメソッドを呼び出す。

6. src/tree/updater_colmaker.ccのColMaker::BuilderクラスのUpdateメソッド

木の深さごとに以下を行う：

  1. FindSplitメソッドを呼び出す。

    • FindSplitメソッドでは、UpdateSolutionメソッドを呼び出す。
    • UpdateSolutionメソッドでは、特徴量ごとにEnumerateSplitメソッドを呼び出す。
    • EnumerateSplitメソッドは、ある特徴量で最適な分割点とロスを求めるメソッドである。
      特徴量の値でソート済のレコードのインデックスのリストがあるので、順次勾配の値を累積することで、分割後のロスが最も小さくなる特徴量の値を求めることができる。

  2. ResetPositionメソッドなどを呼び出し、データが属する葉を更新するなどの、葉を分岐させる処理を行う。

計算量

ソースコードを調べた発端はここの話で、計算量について正しく理解したかったため。

xgboostのexact(pre-sorted)アルゴリズム

xgboostのexactオプションでの計算量は以下のとおり（と思われる・・）：

  • 木の作成前に、特徴量ごとに特徴量の値でソートしたデータへの参照を作成しておく。これは一度だけO(データ数 x log(データ数）x 特徴量の数）が必要 。
  • 木を作成するごとに、各データの勾配/ヘシアンを求める必要があるが、これは最初にO(データ数)で計算できる。
  • 各深さごとに、各特徴量ごとに、最適な分割をデータを走査して求める。特徴量の値でソート済のデータへの参照があれば、密なデータの場合にはO(データ数)で計算できる。
    ここで、深さごとに計算しているのが一つのポイントで、同じ深さの各葉ごとに属するデータが排他なので、1度の走査で各葉に対して計算できる。もし葉ごとに全てのデータを走査すると無駄な走査が発生し、深さごとにO（データ数 x 葉の数）の計算が必要となってしまう。
  • 結局、支配的な部分は特徴量の走査の部分となり、計算量は、O(決定木の数 x データ数 x 特徴量の数 x 深さ)になる。

メモ

コードの理解に役立つクラスの説明：

  • HostDeviceVectorクラスは、GPUへの対応が考慮されているvectorクラスであり、コードの理解上はただのリストと考えておけば良い。
  • Entry構造体は、indexとvalueの2つの値を保持する。indexは使われ方によってデータの行のindexになることも、特徴量（列）のindexになることもある。
  • SparsePageクラスは、行列データを保持するクラス。行または列を参照するためのoffsetを表すvectorと、列または行を参照するindexと保持している値を表すvectorを持つことで、疎なデータを効率的に保持できる。
  • SortedCSCPageクラスは、SparsePageクラスの派生クラスで、列ごとに分割しやすい形式で疎なデータを保持することができる。ColMakerなどでの計算でこのクラスが使われている。

「Kaggleで勝つデータ分析の技術」について（執筆ツール編）

 「Kaggleで勝つデータ分析の技術」（amazon）の、執筆周りの知見の情報共有です。

今回は原稿をmarkdownで執筆しました。終盤まではGithubで管理を行い、その後出版社にPDFにしてもらい、PDFに修正依頼を入れることを数回繰り返し、完成となります。*1  

原稿

  markdownはバージョン管理ができるのがやはり楽です。ただ、Githubでmarkdownを見ようとしても数式が表示されないという致命的な問題がありました。
ここで、atomにmarkdown-preview-plusのプラグインを入れることで数式も含めてプレビューできる執筆環境ができます。（mathjax-wrapperも要るかもしれません）*2
それでも確認はしづらいので、pandocでhtmlに出力して適宜印刷して眺めるようにしました。なぜかpandocはwindowsではエラーが出たので、windows subsystem for linuxにインストールすることで解決しました。*3

数式・図・注釈といった要素に対応できるので、わりと満足な執筆環境ができます。   

図

  結局は安定と信頼のpowerpointになりました。draw.ioも試したけどしっくりこず。図はデザイナーさんが綺麗にしてくれるのですが、明確に書いておかないと結局修正することになるので、慣れないと時間はかかりますがちゃんと図を作らないとダメですね。
VBAがとくいなので各スライドを画像にして出力するマクロを作った*4のですが、めちゃくちゃ生産性が上がりました。  

Sub save_png()
 
Dim p As Variant
Set p = Application.ActivePresentation
 
For i = 1 To p.Slides.Count
   Debug.Print i
   Dim path As String
   path = ActivePresentation.path & "\images_ch3\スライド" & i & ".PNG"
   p.Slides(i).Export path, "PNG"
 
Next i
 
End Sub

 

ソースコード

  ちゃんとやるには、

  1. 書籍内に記述するためのコード
  2. 公開するためのコード
  3. aやbが正しく動くか検証するためのコード

を管理する必要があります。これらを綺麗に管理するのは難しく、bをベースにしながら、

# ----- START TEST -----
# ----- END TEST -----

を差し込んだりしてごにょごにょして頑張りました。.pyで記述したのですが、この目的であればJupyter Notebookの方が管理が楽だったかもしれません。

GCPで環境を作ってひととおり検証コードを流して、結果が概ねおかしくないことを確認しています。  

情報共有・修正依頼

  執筆者間および編集者との情報共有は、Github + Slack + google spreadsheetで行いました。 フロー情報はSlackで良いとして、入る情報の形が定まっていないストック情報の共有はgoogle spreadsheetが有力だと思います。タスクの粒度を変える必要があるときにGithubのIssueなどの他のツールだとなかなかつらい。

PDF化する前はgit管理なので楽なのですが、PDF化してからの修正依頼はなかなか苦労しました。google spreadsheetで修正対象と修正後の文章などを明確に記述して連携しましたが、ipad + apple pencilも良い選択肢かもしれません。   

*1:技術同人誌などではRe:Viewといった選択肢があるようですね。参考：『読みやすい技術書を書く技術』という本を技術書典7で頒布します #技術書典 - 憂鬱な世界にネコパンチ！

*2:参考：Atom をMarkdownエディタとして整備 - Qiita

*3:参考：数式・画像付きのmarkdownをhtmlに変換 - Qiita

*4:Option Explicitを書いてないのでガチ勢に怒られます

「Kaggleで勝つデータ分析の技術」について（内容編）

10/9に技術評論社から、「Kaggleで勝つデータ分析の技術」が出版されます（amazon）。
（ブログ主＝著者の一人の門脇です）
 
 
多くの予約を頂いているようで大変有難いです。もし評価がひどくて多方面から矢が飛んで来たらどうしようと怖くなることもありますが、何だかんだで自信を持って出せる本に仕上がったと思っています。以下で、見どころや意図を紹介します。
 
目指したところ
 
私が目指したのは、テーブルデータについて「Kaggler（＝Kaggleの参加者）の暗黙知を明らかにする」ことです。一度整理したかったですし、なかなか綺麗にまとまっている資料はないようです。
CourseraのHow to Win a Data Science Competitionが比較的近いテーマですが、英語なのはともかく、動画での講義なので情報を整理するコストがなかなか高いですし、またこの講座とも違うエッセンスを加えることができたかと思います。
 
Kaggleをあまりやったことのない方には、分析コンペという多数のタスクがあり、予測の良さに対して順位が明確につく環境でのノウハウには目新しいものが多いと思います。xgboostをはじめとする効果的な手法もありますし、また有名だけれど使えない手法が淘汰されていくところも面白いです。（SMOTEとか）
Kagglerの方には知っている情報も多いですが、特徴量のアイデアに迷ったときの事典となることや、手法やTIPSを整理して知識の穴を埋められることを目指しました。また、xgboostやTPEの仕組みの説明などでなかなか学ぶ時間がとれない理論的なところにも触れるようにしました。とはいえ、適当に期待は下げておきましょう笑
 
見どころ
 
 目次を見ると、大体何が書いてあるかわかるように構成しました。目次は技術評論社のページが見やすいかもしれません。
https://gihyo.jp/book/2019/978-4-297-10843-4/#toc 
 
私のオススメは3章と5章です。
 
3章：テーブルデータのコンペで最も重要な特徴量についての章です。目次だけでお腹いっぱいな感じがあります笑 
あまり綺麗な分け方ではないのですが、特徴量の作り方を大まかに以下に分けて説明しています。
  • モデルを意識した特徴量の作成
  • 欠損値の処理、数値変数の変換、カテゴリ変数の変換
  • 他のテーブルの結合、集約して統計量をとる
  • 時系列データ
  • 次元削減・教師なし学習
  • 特徴量を作るアイデア
前半の山場はtarget encodingで、後半の山場は集約と時系列データです。なかなか他では見られない視点や情報があると思います。
 
5章：モデルの評価を行うバリデーションの章です。前半はクロスバリデーション、group k-fold、時系列のバリデーションといった基本パターンの説明、後半は「何を目的としてバリデーションを行うのか」「学習データとテストデータの分割をまねる」といった、心構え・TIPS的な部分です。
特に後半の心構え的な部分について、明確に文章としてまとめたことに価値があると思っています。
 
その他の章については、以下のとおりです。
 
1章：Kaggleの概要を説明する章です。導入的な章ですが、それでもKagglerらしさや矜持のようなものが漏れ出ているようには思います。たとえば、タイタニックを例に説明をしていますが、理由があって特徴量の作成をあまりする気になれず、一方で手元のバリデーションとLeaderboardのスコアが合わずに焦っている様子を見ることができます。
 
2章：主に評価指標について説明する章で、評価指標の最適化が章のメインのテーマです。評価指標のハッキングなどと言われ、あまり本質的な意味がないと思われることもありますが、ゴールを常に意識することはタスクに取り組むときに普遍的に重要なポイントでしょう。
 
4章：モデルについて説明する章です。xgboostをはじめとするGBDT（勾配ブースティング木）の紹介に価値があり、他は頑張っていろいろ書きましたが蛇足ではないでしょうか。それくらい、GBDTの存在というのはテーブルデータの予測において圧倒的だと思っています。
 
6章：パラメータチューニングと特徴選択という、答えがあるのか良く分からないテーマを扱う章です。
パラメータチューニングについては、シンプルにやるにはグリッドサーチ、精度を求めるならベイズ最適化という考え方を中心に、パラメータの説明や動かし方などを記述しています。
特徴選択については、Kaggleで比較的良く使われている、GBDTの重要度を用いる手法を中心に説明しています。可視化は範囲から落としたのでSHAPやPartial Dependence Plotなどは入れていないのですが、入れても良かったですね。
 
7章：スタッキングをはじめとしたアンサンブルを説明する章です。
アンサンブルについてはKAGGLE ENSEMBLING GUIDEが有名ですが、前半が冗長に思うので、その辺りを考えながら構成を行いました。
「学習データとテストデータの分布が同じ」データについてスタッキングは強力な方法です。ただ、数百のモデルのスタッキング競争になるのを避けるためか、最近のコンペは学習データとテストデータの分布が違うものが多く、そういった場合にはスタッキングでなく加重平均など*1が使われるため、 重要性が薄れている印象はあります。
 
反省点
 
「現時点での最新のものを整理してまとめました」と「はじめに」で書いてしまったのですが、改めて見返すと以下は最新とは言い難いかなと思います。
 

・xgboostを使って説明している
    分析コンペでは速度面の利点などからlightgbmが使われるようになり、xgboostを使う人はもうあまりいません。ただ、Kaggleのような大きなデータでなければxgboostで十分ですし、xgboostを理解するとlightgbmでも十分通用するので、まぁ良いかなと・・

・ニューラルネットの最新の知見
    深層学習は世界中でかなりのリソースをかけて研究されており、技術の進展が速いです。画像データだけでなく、テーブルデータに使える概念や手法もあると思われます。たとえば、ネットワーク構造やパラメータチューニングのほか、domain adaptation*2の考え方を学習データとテストデータの分布が違う問題に適用するなどです。テーブルデータに適用する手法や知見がまだ確立していないように思うので、書くのは見送っています。
 
また、以下をもう少し強調して説明した方が良かったかもしれません。
  • Kaggleのコンペは、テーブルデータのコンペと、画像データなどを扱う深層学習の技術がメインとなるコンペの２つに大きく分かれます。本の記述だけだとKaggleにはテーブルデータしかないように見えてしまうかもしれないですが、そうでなく画像データなどのコンペも大きな位置を占めている、というか画像コンペの方が多いです。
  • 本で紹介したテクニックは実務に役立つものも沢山ありますが、分析コンペと実務には当然違う性質があります。分析コンペはデータが定まっている状況で精度を競うため、データを使いきることが重要です。また、メンテナンス性は多少無視して良いですし、Public Leaderboardでの確認がリークをしていないかの判断の助けになります。たとえば、分析コンペだとクロスバリデーションで評価を行い、hold-outデータを別途用意しておく余裕はないですが、実務ではデータを使いきる必要はなく、リークのリスクを減らすためにhold-outデータをとり置いて学習に一切使わないようにすることは有効でしょう。
 
オチ
 
原稿のドラフトを見せたときの編集者の感想
「実際に精緻な計算、戦略をとって取り組まれているように見えます。イキる*3というのがすべてを表しているとは思いませんが、そのイメージとはちょっと違う印象でした。」
🤔🤔🤔

*1:最近はあるモデルの予測値と目的変数の残差に対して違うモデルを適用するような手法もある

*2:Domain Adaptation — About ADDA, CyCADA and MCD が分かりやすかった

*3:twitterで自慢したり他人に噛みつくイキりDS（データサイエンティスト）と呼ばれる人が観測されていた