FastBDTの計算時間が速いかを確認してみる
はじめに
最近、ブースティング系のアルゴリズムでXGboostより速いものが実装されているようです。
github.com
論文を見ると、Stochastic Gradient Boosted Decision Tree (SGBDT)という手法が用いられているようです*1。用途としては、信号（例えば、ラベル1）と背景事象（1以外）を分類する場合が想定されています。このアルゴリズムは、素粒子実験の一つである、Belle II実験の解析で使用されているとのことです。ばくっと探していたらカールスルーエの学生の修論があったので、載せておきます。
https://ekp-invenio.physik.uni-karlsruhe.de/record/48602/files/EKP-2015-00001.pdf
Belle II実験
Belle II実験に関しては、修士課程のときの自分の研究内容と深く関わっているので少し補足を。
Belle II実験とは、日本のKEKにある電子-陽電子加速器を用いた実験です。この実験の目的の一つ*2は、B中間子とよばれる、ボトムクォークを含む複合粒子をたくさん生成し、その「稀な」崩壊現象の精密測定から新しい理論の探索を行うことです*3。標準模型を超える物理があった場合、直接高エネルギー加速器で直接生成されるだけでなく、間接的に様々な物理量に寄与する可能性があります*4。その寄与は、標準模型の予測値からも「ずれ」という形で表れます。その「ずれ」を実験で精密に検証することで、新しい物理の姿を間接的に見ることができます。
間接的に新しい物理の効果を見るにあたって、「稀な」崩壊現象を見ることが非常に大事です。それは、比較的起こりやすい崩壊現象よりも、新しい物理の効果を捉えやすいためです。標準模型では、例えばGlashow‐Iliopoulos‐Maiani機構（GIM機構）といった、ある種類の崩壊を抑制する機構が備わっているため、素朴な次元解析での評価よりも崩壊率が小さいものがあります。これらは標準模型では「稀な」崩壊と予測されます。しかし、新しい物理は必ずしもGIM機構のようなものが備わっているわけではないため*5、大きな補正が「稀な」崩壊現象に加わる可能性があります。そのため、比較的起こりやすい崩壊現象とくらべて変化を捉えやすくなります。
B中間子に着目する理由は、その「稀さ」が絶妙だからです。B中間子の物理現象は、抑制されているカテゴリーの中では比較的大きな寄与を持っています*6。そのため、稀ではあるが、標準模型が正しいと仮定した場合の予測値が実験で検知できる程度には寄与がある、といった現象になり、「標準模型からのずれ」の検証が他の中間子よりも容易になっています。
インストールから使用可能になるまで
つい素粒子の話になると長くなってしまうので、話を戻します。Mac OSの場合、サイトから直接ダウンロードし、makeすれば使えるようになります。cmakeは予めインストールしておきます。
$ git clone https://github.com/thomaskeck/FastBDT $ cd FastBDT/ $ cmake . $ make $ make install
上記の操作をすれば、実行ファイルが生成されるので、FastBDTのディレクトリで
$ ./FastBDF [あといろいろ必要なオプション指定]
と唱えると実行できます。
Pythonから使用したい場合
Pythonで動かす方法もあります。ただし、まだ完全に設定などを理解していないので、現状を備忘録的にまとめておきます。
修正点
まず、インポートする元は ~/FastBDT/python/FastBDT.pyにあります。ただし、このスクリプトで指定しているライブラリの名前が自分の環境では異なっていたので、少し修正が必要です。修正方法は2通りあります。
- [19行目]で指定しているライブラリをlibFastBDT_CInterface.soからlibFastBDT_CInterface.dylibに書き換える
- [14行目-16行目]のコメントアウトを外し、[19行目]をコメントアウト
こうすれば、インポートしたときに正しく読み込みができるようになりました。
インポート
以下のようにパスを上手く指定してインポートします。
import sys sys.path.append('/Users/[ユーザ名]/FastBDT/python') import FastBDT
インポートまでの一連の流れですが、不慣れなこともあり、かなり洗練されていない感じになっています（というよりセオリーを知らない。）が、ご了承ください（汗）。
モデルはClassifierで作成することができます。モデルインスタンス作成後は、scikit-learnのようにfitやpredictといったメソッドが使えます。
計算時間の比較
学習にかかった時間を計測します。比較対象として、パーセプトロン、ランダムフォレスト、XGboostを選択します。
サンプルデータ
FastBDTは'1'とそれ以外を識別する問題にのみ対応しているようです*7。そのため、簡単のため、人工的に2値データを生成して、それで比較することにしました。クラス分類のテスト用の人工データは、scikit-learn.datasetのmake_classificationで作成することが可能です。参考にしたサイトは以下です。
overlap.hatenablog.jp
説明変数が5つ（n_features = 5）、サンプル数100万（n_samples = 1000000）の2値データ（n_classes = 2）を生成します。他のオプションは適当です。
from sklearn.datasets import make_classification # データ作成 dat = make_classification( n_samples=1000000, n_features=5, n_informative=2, n_redundant=2, n_repeated=0, n_classes=2, n_clusters_per_class=2, weights=None, flip_y=0.01, class_sep=1.0, hypercube=True, shift=0.0, scale=1.0, shuffle=True, random_state=None)
データマートを作成し、さらに学習用、検証用データを作成します。
# ライブラリ import pandas as pd from pandas import DataFrame # DataFrameに格納 df = DataFrame(dat[0], columns = ['Var1', 'Var2', 'Var3', 'Var4', 'Var5']) df['Class'] = dat[1] # 説明変数、目的変数 X = df.iloc[:, :-1].values y = df.loc[:, 'Class'].values # 学習用、検証用データ作成 from sklearn.cross_validation import train_test_split (X_train, X_test, y_train, y_test) = train_test_split(X, y, test_size = 0.3, random_state = 666)
計算時間、誤分類数、Accuracyを算出
ばくっと計算する関数を作っておきます。
def CalcTimes(mod, X_train, X_test, y_train, y_test): import numpy as np from sklearn.metrics import accuracy_score start = time.time() # モデルインスタンス作成、学習 mod = mod mod.fit(X_train, y_train) elapsed_time = time.time() - start print('elapsed_time: %.2f' %elapsed_time + ' [sec]') # 誤分類数、Accuracy y_train_pred = np.round(mod.predict(X_train)) y_test_pred = np.round(mod.predict(X_test)) print('Misclassified samples: %d' % (y_test != np.round(y_test_pred)).sum()) print('Accuracy: %.2f' % accuracy_score(y_test, y_test_pred))
FastBDT
from FastBDT import Classifier mod = Classifier() CalcTimes(mod, X_train, X_test, y_train, y_test) # 出力 elapsed_time: 6.50 [sec] Misclassified samples: 34948 Accuracy: 0.88
パーセプトロン
from sklearn.linear_model import Perceptron mod = Perceptron() CalcTimes(mod, X_train, X_test, y_train, y_test) # 出力 elapsed_time: 0.56 [sec] Misclassified samples: 66686 Accuracy: 0.78
ランダムフォレスト
from sklearn.ensemble import RandomForestClassifier mod = RandomForestClassifier() CalcTimes(mod, X_train, X_test, y_train, y_test) # 出力 elapsed_time: 44.74 [sec] Misclassified samples: 39241 Accuracy: 0.87
XGboost
from xgboost import XGBClassifier mod = XGBClassifier() CalcTimes(mod, X_train, X_test, y_train, y_test) # 出力 elapsed_time: 45.03 [sec] Misclassified samples: 34131 Accuracy: 0.89
比較結果
今回のデータセットに関しては、Macbook Air使用で、FastBDTはランダムフォレストやXGboostと比較して6倍以上速い結果になりました。しかも、Accuracyが大きく損なわれずにです。条件を変えると倍率は変わると思われますが、概ね似たカテゴリーのアルゴリズムよりは高速なんだと思います。もっと開発が進んで使いやすくなったら、非常に強力なアルゴリズムなのではないかと期待されます。
*1:細かい部分で工夫があるようですが、まだキャッチアップできていません。
*2:他にもK中間子の稀崩壊探索なども目的です。
*3:前身として、Belle実験というものが同じKEKで行われていました。Belle実験では、B中間子の崩壊現象を用いた標準模型の検証が主目的でした。
*4:量子効果（摂動論の高次効果）で寄与します。
*5:4次元以外の「余剰な」次元を持っている理論がその例です。超対称性を持った理論でSuper GIM機構というものがある場合は、余剰次元をもつ理論よりは寄与が抑制されます。
*6:色々省略しますが、これはトップクォークという素粒子がとてつもなく重いことが起源です。
*7:使ってみた結果、こう認識しています。間違いがあればご指摘ください。
