はじめに
XGBoost: A Scalable Tree Boosting System
を読んだので、分かったことをメモしておきます。機械学習の勉強を始めてまだ2ヶ月くらいなので理解不足な点が多々あると思います。間違いや見当違いな点がありましたらぜひぜひご指摘いただきたいです。
XGBoostとは何か
Gradient Boosting Decision Tree(勾配ブースティング決定木、GBDT)を利用した分類/回帰手法の一つです。単一のアルゴリズムというより、XGBoostというオープンソースのモジュールが利用している手法群の総称とイメージした方が分かりやすいと思います。
論文は以下の構成になっています
- Abstract
- 1.Introduction
- 2.Tree Boosting in a nutshell 決定木のブースティング全般について
- 3.Split Finding Algorithms 木が学習する際にどこで分割(split)するかの探し方 XGBoostの推しポイントの1つです
- 4. System Design XGBoostがGBDTの各段階でどう動くのかが書いてあります
- 5.Related Works
- 6.End to end evaluations
ここでは2〜4について書きます
2.1 正則化つきの目的関数
アンサンブル学習
$$\hat{y_i}=\phi(x_i)=\sum_{k=1}^kf_k(x_i) f_k\in F$$
目的関数
$$L(\phi)=\sum_il(\hat{y_i},y_i)+\sum_k\Omega(f_k)$$
$$where \Omega(f)=\sqrt{T}+\frac{1}{2}\lambda||w||^2$$
アンサンブル学習の式は「たくさんの予測を足し合わせると全体の予測になる」という意味です。
目的関数の式はlっていう予測の間違いを表す項と、Ωっていうモデルの複雑さへの罰を表す項を足し合わせたものを表しています。これが一番小さくなるようにl（具体的には葉につける重みw）を選んでいきます。
また正則化項のΩはこれじゃなきゃダメってわけじゃないですが(実際にXGBoostの実装時にl1正則化を指定したりもできる)これだと割とうまくいくらしいです。
2.2 勾配ブースティング決定木
決定木のアルゴリズムの中心にあるのは木の構造を決め方です。「どの特徴量について」「どの境界値で分割するか」が鍵になります。
それを決めるために、決定木では「もしこの特徴量、この値で分割したとしたら目的関数はいくつになるのか」を計算し、目的関数を一番小さくできるような場所で分割を行います。
その計算は以下のように行われます
1. 目的関数を最小化する際に、lがMSEみたいな簡単な関数なら計算できるけど、より複雑な場合は直接計算しにくい。
2. だからLはテイラー展開して2次の項まで残す。そうすると1次と2次の導関数だけ分かればlが複雑な関数でも計算できる。
3. するとそれぞれの葉の最適な重みwは1次と２次の導関数、それと正則化のためのハイパーパラメータのλだけの簡単な計算で求まる
4. 葉の重みが分かれば、その木全体の目的関数も計算できる。そして木同士の値を比較することで分割場所を決められる。
分割を決めるために、毎度毎度「勾配を出して、目的関数の値を出して、比べて」というのをたくさんの点で行うのは大変そうです。
3 分割値を決めるアルゴリズム
この分割の大変さを軽減するために、XGBoostではヒストグラムを使って特徴量の値をグループ分けし、分割を試す回数を少なくしています。これは論文ではapproximate algorithmと呼ばれています。どこでグループ分けをするかは特徴量の中でのパーセンタイルで決めるのが一般的だそうです。
それに対しsklearnやRのgbmではexact greedy algorithm(全部の場所で分割を試みる)を使っているため、より正確にはなるもののだいぶ処理が遅くなってしまうらしいです。
またそれに加えXGBoostはグループ分けする際に工夫することで、sparseな(ほとんど0な)データにもうまく対応できると書かれていました。
4 System Design
XGBoostが使っている工夫がいろいろ述べられています。箇条書きで述べます。
- ブロックわけを行うことで訓練で一番時間がかかる特徴量のソートを効率的に行えます。exact algorithmでは1つの、approximate algorithmでは複数のブロックを使うそうです。またこれにより並列処理ができるようになるらしいです。
- 勾配を持ってくる際に、exact algorithmの場合にはcache(コンピュータがデータを保存できる場所)を意識したアルゴリズムを使います。approximate algorithmの場合には適切なブロックサイズを決めておきます。これによって計算が速く行えます。
- Block Compression(圧縮)やBlock Sharding(分割)を行い、付加的な作業も効率的にできます。
このようにXGBoostには計算を効率的に行うための工夫がたくさんされています。
まとめ
こういった工夫により、XGBoostのフレームワークを使えばsklearnで普通にGBDTを行うよりより良い結果を出すことができます。今のKaggleではLightGBMが流行っていますが少し前はXGBoostが一強だったようです。