FastBDTでの高速化

機械学習

はじめに

勾配ブースティング木の高速化はどうすればいいだろうと調べていたら、arxivで流れているのを見かけたのでメモ。

Stochastic Gradient Boosted Decision Tree(SGBDT)

  • 勾配ブースティングの各イテレーションで、学習データから非復元抽出でサンプリングしたデータを用いる

高速化

メモリアクセス、CPUキャッシュ、前処理、並列化を考慮。

メモリアクセスパターン
  • 学習データのメモリ配置について最適化
  • 一般的に以下の2つのレイアウト方式が考えられる
    • array of structs(構造体の配列) : x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3, x_4, y_4, z_4
    • struct of arrays(配列の構造体) : x_1, x_2, x_3, x_4, y_1, y_2, y_3, y_4, z_1, z_2, z_3, z_4
  • FastBDTは「array of structs」を利用
    • CPUキャッシュの空間的局所性(例：linear memory access pattern)、時間的局所性(小さなCPHのキャッシュ)、CPUの分岐局所性(conditional jumpをできるだけ避ける)を考慮

【正例と負例のメモリマップ】

  • array of structsを利用する場合、そのまま並べてしまうと、正例と負例の判定で条件分岐が必要になってしまう
  • そこで、正例と負例のデータを分けて、保存や処理を行う

【レイヤー毎の複数ノードの処理】

  • ノード単位で別々にノードを処理していく方法だと、使用する学習データへのアクセスがとびとびになってしまい、メモリレイアウト方式によらずランダムにジャンプしてアクセスしてしまう
    • (DFS的な感じでのノードの処理？)
  • 木のレイヤー単位で、そのレイヤーすべてのノードを並列処理することができると、連続的なメモリアクセスにできる

【確率的サブサンプリング】

  • SGBDTだと、学習データからサンプリングしたデータを使用するため、使うデータと使わないデータを選ぶ必要がある
  • array of structsだと、各データポイントの範囲内であれば、条件分岐なしでデータへ連続的にアクセスできる
前処理
  • 決定木では、「値それ自身」というより「値同士の大小関係」しか使わない
  • そこで、入力素性についてequal-frequency binningをして整数値(インデクス)にマッピング
    • equal-frequency binning : 入力の値をbinningするとき、各ビンが同じデータ数になるようにbinningする(ソートしてm個ずつビンにいれる)
    • 速度面だけでなく、ピークやヘビーテイルを含む入力の分布を一様分布にマッピングすることで分離性能も改善しうる
  • また、木の学習が終わったら、整数値から小数値へ逆に変換すれば、実行時に変換のオーバーヘッドなく利用できる
並列化
  • タスクレベル(マルチプロセッサ、マルチコア、マルチスレッドなど)の並列化を適用できる
    • 学習時、適用時
  • 命令レベル(命令パイプライン化、multiple execution unit、vectorizationなど)の並列化の適用は難しい
    • アルゴリズム固有の条件分岐が大量にあるため
    • ただ、メモリレイアウトと前処理から、条件分岐をインデクス操作に置き換えることで高速化はできる(branch locality)
      • 「if(X) a++; else b++;」ではなく、「arr[X]++;」のような書き方

参考