Boosting Tree

　今回はシンプルなBoostingTreeについての解説です。アンサンブル学習の一つとしてBoostingです。Boostingは前段までのモデルの結果を受け取ってからさらに新しいモデルの訓練を開始します。前段までのモデルの結果とはモデルの予測と正解とのずれのことで、新しいモデルではこれをより少なくするように学習が実行されます。

アルゴリズム: Regression

　理論的な公式などをすべて省いて書いていきます。種類としては、Adaboost、Xgboostなどがありますが、今日はFreidmanのGradientBoostingのみについてです。先に回帰（Regression）について解説したいと思います。

　全サンプルの特徴量を$X$と対応する正解を$Y$とし、それぞれの$i$番目のサンプルを$x_i$、$y_i$、m番目のモデルの$x_i$に対する予測を$H_m(x_i)$、m番目のモデルまでの$x_i$に対する予測を$F_m(x_i)$とします。サンプル数はNで、M番目のモデルまで訓練を繰り返す場合を考えます。

　各段階でのモデルの出力は以下で与えられます。

F_m (x_i) = F_0 + \sum_{i=1}^m \gamma_i H_i(x_1)

ここで$F_0$は訓練データの平均です。

F_0 = \frac{1}{N} \sum_{i=1}^N Y_i

また、$\gamma_i$は学習率で各段階のモデルのごとに異なった値をとります。Line Searchで計算をするはずですが、FortLearnerでは固定のままです。Scikit-learnの目的関数の実装部分にあるかと思ったのですが、見つけることができませんでした。

　最後に各段階での$F_m$の計算方法です。最初に前段までのモデルの予測を受けとり正解とのずれを計算するといいましたが、具体的には目的関数の微分を計算します。全サンプル$X$の$i$番目のサンプルを$x_i$とし、対応する正解を$y_i$、$x_i$に対する予測を$F(x_i)$とします。目的関数（回帰であれば自乗誤差などで微分可能なものを設定します。）を$L(y_i, F(x_i))$とします。この時目的関数を$F(x_i)$で微分した値$\nabla L$は、例えば自乗誤差の場合は以下のように与えられます。

\nabla L =  \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} = \frac{\partial}{\partial F(x_i)} \left( \frac{1}{2} \left( y_i - F(x_i) \right)^2 \right) = y_i - F(x_i)

　自乗誤差では単純な正解と予測の差分で計算することができます。

　したがって、以下のような手順を指定の回数繰り返します。自乗誤差の場合と学習率固定($\gamma_i = \gamma$)の場合のみ記載するので、適宜読み替えてください。

F_0を計算する
１番目のモデルは各サンプルに対して$y_i^0 = y_i-F_0$を計算し、モデルに$X$とともに投入して学習を行う。
１番目のモデルの学習が終了したら全サンプルに対して$F_1(x_i) = F_0 + \gamma H_1(x_i)$を計算する。
２番目のモデルは各サンプルに対して$y_i^0 = y_i-F_1(x_i)$を計算し、モデルに$X$とともに投入して学習を行う。
２番目のモデルの学習が終了したら全サンプルに対して$F_2(x_i) = F_0 + \gamma H_1(x_i) + \gamma H_2(x_i)$を計算する。
...
M番目のモデルの学習が終了したら全サンプルに対して$F_2(x_i) = F_0 + \sum_{m=1}^M \gamma H_m(x_i)$を計算する。

アルゴリズム: Classification

　次に分類（Classification）についてみてみたいと思います。調べ始める前はRandomForestなどと同様に回帰の場合は複数のRegressorを、分類の場合は複数のClassifierをという風に思っていました。Classificationについても結局はRegressorを用いているようです。初期化($F_0$)の方法と最終的な予測の出力の仕方が少し異なるだけです。

　初期化の方法として、もう目的関数がLogLossの場合についてみてみましょう。$p_i$はサンプル$x_i$の予測確率です。

L = - y_i \log(p_i) - (1-y_i) \log(p_i) \hspace{10pt} \text{ここで} \hspace{10pt} p_i = \frac{1}{1+\exp(-F_m(x_i))}

シグモイド関数を適用しているのは、そのままでは範囲が[0,1]に収まらないためです。そして、回帰の時と同様に$F_m$で微分します。いろいろごにょごにょすると、

\nabla L = p_i - y_i

非常に簡単な形に変換できます。

その他

構成

　プログラムはboosting_trees以下に配置しています。

mod_gradient_boosting_adaboost.f90
- adaboostの実装です（明日の記事で解説します）
mod_gradient_boosting_clouds.f90
- CLOUDSをベースに使った実装です
mod_gradient_boosting_extra_tree.f90
- ExtraTreeをベースに使った実装です
mod_gradient_boosting_lawu.f90
- Lawuをベースに使った実装です（明後日のところで少しだけ触れます）
mod_gradient_boosting_tree.f90
- CARTをベースに使った実装です

計算時間

　基本的にBaggingより非常に時間がかかります。Baggingでは、各モデルを並列に学習することができました。CART, SLIQ, ObliviousTreeであれば特徴量ごとに、CLOUDSであればヒストグラム生成を並列実装することができると思います。

汎化性能

　訓練データのずれにフィットするように何度も学習が行われるため、過学習が起きやすいです。決定木一般でいうと

各葉ノードの数をあまり少なくしない。n_samples_leaf=10など
木の深さを抑える。max_depth=5など。max_leaf_nodesを抑えることもほぼ同じ

とくにBoostingでいうと学習率をあまり大きな値にしないことがあげられますが、同時に学習時間が大幅に伸びるので注意が必要です。

以上
　