PythonでXGBoostをちゃんと理解する(2) ライブラリ作者から学ぶ

XGBoostについて調べてたら、開発者本人から学ぶ的な動画があったので観てみた。

www.youtube.com

時間にして約1時間半、英語が苦手でなくて時間がある方は直接見て頂くと面白いかも。

目次はこんな感じ。
・Introduction
・Basic Walkthrough
・Real World Application
・Model Specification
・Parameter Introduction
・Advanced Features
・Gaggle Winning Solution

前半は「まぁみんな知ってるよね」ってことが多かったが、Model SpecificationとParameter Introductionの中のParameter Tuning、あとAdvanced Featuresが面白かったのでメモ。

Model Specification

よく見る勾配ブースティングの説明とは違うように見えたので、面白くて動画を見ながらスライドの内容をメモってみました。
所詮スライドなので、動画内での口頭での補足があるとよりわかりやすいですが、ざっと眺めてもそれなりにわかりやすいのでご参考にどうぞ。
日本語訳が雑でごめんなさい。

動画内スライド引用 (24:00〜)

$K$ 本の決定木があったとして、 $f_k$ がその木からの予測値とすると、モデルは $\sum_{k=1}^K f_k$ 。(P31)
$i$ 番目のデータ、 $x_i$ の予測値は、 $\hat{y_i} = \sum_{k=1}^K f_k (x_i)$ であり、同様に $t$ 番目のステップでの予測値は、 $\hat{y_i}^{(t)} = \sum_{k=1}^t f_k (x_i)$ となる(p32)。損失関数 $L$ は、最小二乗法、2値分類と多クラス分類のためなどそれぞれ目的に応じて使う。
また過学習を防ぐために正則化項を導入し、その式は
$\Omega　= \gamma {\bf T} +\frac{1}{2} \lambda\sum_{j=1}^T w_j^2$
ここで、 ${\bf T}$ は葉の数、 $w_j^2$ はj番目の葉における重みの値である(P34)。
損失関数と正則化項をまとめると下記のようになる。
$Obj　= L + \Omega$
XGboostでは、この $Obj$ を最適化するために、勾配降下法を用いる。
目的関数を下記のように置き直し、
${Obj}^{(t)}　= \sum_{i=1}^N L(y_i, \hat{y_i}^{(t)}) + \sum_{i=1}^t \Omega(f_i) = \sum_{i=1}^N L(y_i, \hat{y_i}^{(t-1)} + f_t(x_t)) + \sum_{i=1}^t \Omega(f_i)$

1次導関数、2次導関数それぞれをそれぞれ下記のように求めると(P37)、
${\partial_{\hat{y_i}^{(t)}} Obj^{(t)}}$
${\partial_{\hat{y_i}^{(t)}}^2 Obj^{(t)}}$
テイラー展開することで、
${Obj}^{(t)}　\simeq \sum_{i=1}^N [L(y_i, \hat{y_i}^{(t-1)}) + \frac{1}{2} h_i f_t^2(x_i)] + \sum_{i=1}^t \Omega(f_i)$
と近似できる。ここでは、
$g_i =\partial_{\hat{y_i}^{(t)}} l(y_i, \hat{y_i}^{(t-1)})$
$h_i =\partial_{\hat{y_i}^{(t)}}^2 l(y_i, \hat{y_i}^{(t-1)})$
である(P38)。で、この目的関数 ${Obj}^{(t)}$ を最適化させて $f_t$ を求めることがゴール。
じゃあこの $f_t$ を出力するために、①決定木の形をどうやって求める？＆②予測の値をどうやって出力させる？を考える(P43)。
①の問題が解決できてるとして、決定木は、 $f_t(x) = w_{q(x)}$ で表される。ここで $q(x)$ は、 $q(x)$ 番目の葉にデータを当てはめる関数である。この式は予測値を返す過程を、
・データ $x$ を葉 $q$ に割り当てる
・対応する重み $w_{q(x)}$ を割り当てる
j番目の葉に割り当てられたデータにインデックスを $I_j = \{i|q(x_i) = j\}$ に従って割り振る。
ここで、目的関数 $Obj$ を書き換えると、
$Obj^{(t)} = \sum_{i=1}^n [g_i f_i(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \gamma {\bf T} +\frac{1}{2} \lambda\sum_{j=1}^T w_j^2 =\sum_{j=1}^T [(\sum_{i \in I_j} g_i) w_i + \frac{1}{2} (\sum_{i \in I_j} h_i+\lambda )]{w_i}^2　+ \gamma {\bf T}$
同じ葉にいる全てのデータは同じ予測値を共有するので、この式は葉ごとの予測値の総和を返す。
ここで $w_j$ は2次方程式となるので、 $Obj$ を最適化する $w_j$ は簡単に求まり、
$w_j^{\ast} = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i+\lambda}$
となるから、それに応じた $Obj$ の値は下記となる(P48)。
$Obj^{(t)} = - \frac{1}{2} \sum_{j = 1}^T \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i+\lambda}+ \gamma {\bf T}$
これで重みの値が求まるので、次にどのように木の形を決めるかを考える。
通常は木の決め方をジニ係数などでGainを計算するが、勾配ブースティングでは、
$gain = \frac{1}{2} [\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} - \gamma ]$
として、gainを計算する(P53)。
この式に従って木をMax_depthに達するまで茂らせていき、gainが負になる枝を剪定する。
この作業を指定の回数繰り返す。

Parameter Tunin(55:20〜)&Advanced Features(1:00:00〜)

パラメーターをチューニングするにあたっては、以下の3つに気をつけなさいと。

①Control Overfitting
過学習を抑えるために、パラメーターについては二つに分けて考えているようです。
　・モデルの複雑さをコントロールするために
　　−max_depth, min_child_weight,gamma
　・ノイズに対する堅牢さを高めるために
　　−sub_sample, colsample_bytree
まぁこの辺りは何も特別な事考えず、etaを加えて6個のパラメーターを結果を見ながら調整するんでいいんじゃないかなと思います。

②Deal with Imbalanced data
データのバランスをコントロールするために以下3つを試してみなさいと。
・scale_pos_weight使ってデータのバランスを調整
・AUCを評価指標に使う
・max_delta_stepを"1"辺りに設定する

③Trust the cross validation
動画の中でも、CVを信じなさいと言ってました。
で、CVを行ってnroundを決める場合には、十分な回数を指定しつつearly.stop.roundを使って終わらせる方法が取り上げられてました。
さらに、Overfittingが見られたら、etaを少なくして、nroundを大きくすることを同時にする。
また、個別のオススメの機能としては、xgb.cv()で"prediction = TRUE"にすることで、予測値のベクトルを返してくれるようになります。

長くなったので、「じゃあパラメーターチューニングは具体的にどうやる？」については次回にします。