XGBoostのアルゴリズムを論文を読んで解説 - 見習いデータサイエンティストの隠れ家

　
夕焼けと紅葉が同化するような季節になると、毎日の服選びに時間がかかるように、ほんの少し昔に遡ると、機械学習のアルゴリズムを何にするかは迷いの種でした。ところが、今や機械学習のご意見場的な立ち位置になったXGBoostが現れてかららは、XGBoostをとりあえず使ってみるというのが定番です。なので、XGBoostにすごいお世話になってるわけですが、中身をなんとなくしか知らいままずっと使っていました。そこで、XGBoostの論文を読んでアルゴリズムの解説を行おうと思います。

ザクッと理解する
数式で理解する
参考

ザクッと理解する

大仏に近づきすぎると膝小僧しか見えず、全体像がわからいために、目にしているのは大仏なのかもわからないかもしれません。つまり、物事を理解するためには、いきなり細部を深くほるというよりは、全体像を把握してから細部の話をすることが大事であり、全体の中でどの部分に関しての話をしているのかを意識することで理解度が上がります。

前置きはここまでにして、早速中身のアルゴリズムの話に入っていきます。すべてのアルゴリズムには型があるように、XGBoostにも核となるアルゴリズムの型があります。それがBoostingです。

Boosting

Boostingは、複数の学習器をまとめて一つのモデルとするアンサンブル学習の一つです。一つ一つは高い精度が出ない弱い学習器であっても、誤差を改善するように弱い学習器を追加していき、それらをまとめて一つのモデルにすることで精度を上げる手法です。

間違いに着目し、それを改善するようにモデルをどんどん追加していくので、誤差が徐々に小さくなっていき、追加されるモデルのウエイトも小さくなっていきます。アンサンブル学習にはこの他にも、個々の学習器を並列して学習させ、予測時に合わせるBaggingという手法もあります。Baggingの代表的なものがRandom Forestです。

武将の戦法で例えると、Boostingは侍が直列になって進み、前の人が倒れたらその倒れた人の後ろの人が次に戦い、Baggingは並列になって進み、全員が最前線になって戦うという感じでしょうか。

Gradient Boosting

Gradient Boostingは、Boostingにおいて、勾配情報を使って損失を減少させる方向を決める方法です。

XGBoostのアルゴリズム

XGBoostは、学習器として回帰木を使い、Boostingによってモデルの構築と学習を行い、学習時にはモデルの勾配情報でパラメータを更新するモデルです。ざくっとしたアルゴリズムは以下の流れになります。

① 回帰木を学習させる
② ①の予測値と目的地から計算される目的関数を改善するように、新たな回帰木を学習させ、モデルに追加する
③ ②を指定した回帰木の本数の分だけ繰り返す
④ モデルの予測値はデータが各回帰木に属する葉の重みの合計値

②について補足すると、追加される2本目以降の木は、目的変数とそれまでに作成した回帰木の予測値との誤差に対して学習が行われます。そのため、木を追加するたびにモデルの予測値が目的値に合致していきます。ただこれだと、深い木を作ったときに過学習してしまうかもしれません。そこで、モデルを学習する際に正則化項を追加し、パラメータが過大にならないように抑制しています。

数式で理解する

上記では、XGBoostのアルゴリズムの概形を触った感じだったので、数式を見ながらより深く理解していきたいと思います。

モデルの予測値

上記で触れたようにXGBoostでは、回帰木をどんどん追加してモデルを構築します。そのため、これからの説明においてモデルの中のどの回帰木を指しているかがわかるように、モデルの回帰木を追加した順番を\(k\)で表します。

最初に、回帰木を１つ学習します。そして、回帰木を追加して学習するということを繰り返し、モデル全体の精度を高めていきます。\(k\)番目の木の学習においては、\(k-1\)番目の木までの予測を補正するように行います。回帰木が順々に追加されてモデルが完成すると、その完成したモデルを使って予測したくなりますよね。そのモデルの予測値とは、データを各回帰木で分類したときに属する、各回帰木の葉の重みの合計値です。つまり、各回帰木の葉の重みが大事なのです。この重みをどのように求めるかは、後ほど出てきますので、詳細はしばしお待ち下さい。

それでは、モデルの予測値を数式で書いてみます。データ数が\(n\)、特徴量が\(m\)個のデータ群を\(D={(\textrm x_i, y_i)}\)とし、\(K\)個の回帰木で表すと、予測式は以下のようになります。と、型苦しく書いていますが、そんなに難しい式ではありません。要は、予測値は各回帰木を合計した値ですよといっているだけです。

\(\displaystyle \hat y_i=\phi (\mathrm x_i)=\sum_{k=i}^K f_k(\mathrm x_i), f_k \in \mathcal F\)

\(\displaystyle \mathrm where\ \mathcal F={f(\mathrm x)=w_{q(\mathrm x)}}\)

\(\displaystyle q:\mathbb R^m \rightarrow T, w \in \mathbb R^T\)

上記の式に出てきた各変数の説明は以下になります。何回も言いますが、大事なのは葉の重みです。この値によってデータの将来（分類先）が変わってしまうのですから。その説明まで近づいておりますが、もう少しのご辛抱を。

\(\mathcal F\)：回帰木の集合
\(f_k(\textrm x_i)\)：データ\(\textrm x_i\)の重み
\(\hat y_i\)：予測値（それぞれの回帰木の重みの合計）
\(w\)：葉の重み
\(T\)：歯の数

損失関数

上記の説明でモデルの予測式が出来上がったので、次に行うのはモデルの予測値と目的値があっているかの確認ですね。この一手間が大事で、常にテストの点数が満点の出来杉君みたいな人だとテストは解くだけでよく、答え合わせをしなくてもよいですよね。しかし、常に満点というのはありえず、次のテストで良い点を取るために、間違っているところをしっかり理解して、再度間違うことを防ぎますよね。機械学習でも同じように振り返りを行い、次に間違わないように正していきます。間違いをスコア化した損失関数を作り、そのスコアが小さくなるようにモデルのパラメータを修正します。これにより、予測モデルが賢くなっていきます。

XGBoostの損失関数は、予測値と目的値の誤差の合計に正則化項を足したものになります。これを式で表すと、損失関数\(\mathcal L(\phi)\)は以下の通りになります。

\(\displaystyle \mathcal L(\phi)=\sum_i l(\hat y_i,\ y_i)+\sum_k \Omega(f_k)\)

\(\displaystyle \mathrm where\ \Omega(f_k)=\gamma T+\frac 12\lambda\|w_k\|^2\)

上の２つ目の式は正則化項を表します。この式の肝は回帰木の重み\(w\)が入っていることです。これがあることで、損失関数の最小化時に回帰木の重みが抑制され、過学習になることを防ぎます。

各変数の説明は以下のとおりです。

\(l\)：\(y_i\)と\(\hat y_i\)の差分を測るための微分可能な損失関数
\(\Omega\)：正則化項
\(\gamma\), \(\lambda\)：パラメータ

損失関数の最適化〜Gradient Tree Boosting〜

損失関数が出来上がったので、あとは損失関数を最適化するだけです。

データ\(i\)が与えられ、\(t\)番目の回帰木\(f_t\)を最適化するとします。そのために、上記で作った損失関数を変形させます。\(t\)番目までの回帰木の予測値を\(t-1\)番目までの回帰木の予測値\(\hat y_i^{(t-1)}\)と\(t\)番目の回帰木の重み\(f_t\)を足した式で表し、損失関数を変形させます。

\(\displaystyle \mathcal L^{(t)}=\sum_i^n l(y_i,\ \hat y_i^{(t-1)}+f_t({\mathrm x_i}))+\Omega(f_t)\)

上記の式の\(f_t\)をTaylor展開の2階項まで求めます。この式を使うことで、最適化する際の収束が早くなります*1。その結果は以下のとおりです。

\(\displaystyle \mathcal L^{(t)} \simeq \sum_i^n [l(y_i,\ \hat y_i^{(t-1)})+g_if_t({\rm x_i})+\frac 1 2 h_if_i^2({\rm x_i})]+\Omega(f_t)\)

このとき、\(g_i=\partial _{\hat y^{(t-1)}}\ l(y_i,\hat y_i^{(t-1)})\), \(h_i=\partial _{\hat y^{(t-1)}}^2\ l(y_i,\hat y_i^{(t-1)})\)とします。更に、定数項は最小化に関係がないので、上記の式から省きます。そして、諸々を整理した下の式を最小化します。

\(\displaystyle \hat {\mathcal L}^{(t)} = \sum_i^n [g_i f_t({\mathrm x_i})+\frac 1 2 h_if_i^2({\mathrm x_i})]+\Omega(f_t)\)

ここで、上記の式を\(\Omega\)を展開します。\(\Omega\)は正則化項を表しており、葉の重みの二乗項と葉の数を足したものです。葉の重みが出てきたので、これまでのデータ単位の式を葉単位に変形します。回帰木において、データ\(\textrm x_i\)が属する葉の番号を\(j\)と表して、葉\(j\)に属するデータの集合を\(I_j\)とします。

\(\displaystyle \hat {\mathcal L}^{(t)} = \sum_i^n [g_i f_t({\mathrm x_i})+\frac 1 2 h_if_t^2({\mathrm x_i})]+\gamma T+\frac 1 2 \lambda \sum_{j=1}^T w_j^2\)

\(\displaystyle = \sum_{j=1}^T [(\sum_{i \in I_j} g_i)w_j + \frac 1 2 (\sum_{i \in I_j} h_i + \lambda ) w_j^2] + \gamma T\)

上記の式では、\(\Omega\)を展開したあとに、\(f_t(\textrm x_i)\)を葉の重みに変形しています。そのため、回帰木の葉を１からTまで順々に見ていく大かっこと、その大かっこの中で各葉に分類されたデータに関わる項（\(g_i, h_i\)）にその葉の重み\(w_j\)をかけています。これで葉の重みが出てきて、損失関数の変形は終了です。この損失関数を最小化する重みを見つけられば、最適なXGBoostを構築することができます。

上記の式を最小化する葉の重み\(w_j\)を求めるために、上記の式を葉の重み\(w_j\)で微分します。

\(\displaystyle {\hat {\mathcal L}^{(t)}}_j' = \sum_{i \in I_j} g_i + (\sum_{i \in I_j} h_i + \lambda ) w_j \)

すごいすっきりとした式になりましたね。この式を０としたときの葉の重み\(w_j\)がまさしく、近似した損失関数を最小化します。つまり、誰しも追い求める大秘宝にたどり着いたわけです。

\(\displaystyle w_j^*=-\frac {\sum_{i \in I_j} g_i} {\sum_{i \in I_j} h_i + \lambda}\)

損失関数を最小化する\(w_j^*\)が求まったので、これを近似した損失関数に代入すると最小の損失値が求まります。ここで、XGBoostの構造を\(q\)としています。

\(\displaystyle \hat {\mathcal L}^{(t)}(q) = - \frac 1 2 \sum_{j=1}^T \frac {(\sum_{i \in I_j})^2} {\sum_{i \in I_j} h_i + \lambda} + \gamma T\)

上記の式がXGBoostを評価する式になります。この式から求まる値を最小にする回帰木の分岐式の組み合わせを求めることで、最強なXGBoostを作ることができます。つまり、XGBoostってどうやって作るのかと尋ねられると、上記の式を最小にする分岐式の組み合わせを求めればいいんだよと答えればよいわけですね。

しかしながら、上記の式を最小化する分岐式の組み合わせを求めるのは、木の深さ・木の数が増えると現実的な時間では困難になります。そこで、現実的な時間で損失関数をそこそこ小さくする解を求めることを考えます。そのために、ヒューリスティックな貪欲的アルゴリズムによって分岐を行います。これは、目の前の最良な手を選択することで、全体としてそこそこ良い手の組み合わせになるという考え方です。XGBoostにおいては、最初の回帰木の葉一つから以下の式を最小にする分岐を選択していくことを繰り返して、全体の回帰木の組み合わせを構築します。

\(\displaystyle \hat {\mathcal L}_{split} = \frac 1 2 \Biggl[ \frac {(\sum_{i \in I_L} g_i)^2} {\sum_{i \in I_L} h_i + \lambda } + \frac {(\sum_{i \in I_R} g_i)^2} {\sum_{i \in I_R} h_i + \lambda } - \frac {(\sum_{i \in I} g_i)^2} {\sum_{i \in I} h_i + \lambda } \Biggr] - \gamma \)

上記の式では、葉\(I\)に属するデータの集合を分岐したとき、左の葉に属するようになったデータの集合を\(I_L\)、右の葉に属するようになったデータの集合を\(I_R\)としています。つまり、\(I=I_L \cup I_R\)です。分岐式の候補の中でこの式を最小化する分岐の候補を選択しては指定の深さになるまで分岐をするを繰り返します。