(cache) 勾配ブースティング落穂拾い - 木の構築について

このシリーズについて

XGBoost芸人を自称してちょこちょこ活動をしてきたのですが、最近になって自分の理解の甘さを痛感するようになりました。

気になった箇所を散発的に復習しているのですが、その成果を備忘録として残しておこうと思います。今のところ体系的にまとめるつもりはないので、これを読んでも勾配ブースティングの全体像はつかめませんので悪しからず。

今回のテーマ以外にはマルチクラス分類の際の挙動等に関心を持っています。

木の構築について

勾配ブースティングでは M+1 回目のイテレーションで誤差

$\displaystyle \sum_{i=1}^N L \left( y_i - \sum_{j=1}^M \eta_j f_j \left( x_i \right) \right) = \sum_{i=1}^N L \left( y_i - f^M \left( x_i \right) \right)$

の勾配を上手く表現した木を構築します。

この部分の処理についてscikit-learnとXGBoostでの違いを確認します。

scikit-learn

カステラ本に準拠した処理になっています。勾配の計算は

$\displaystyle \frac{\partial}{\partial f^M \left( x_i \right)} L \left( y_i - f^M \left( x_i \right) \right)$

となり、これを各サンプルのラベル扱いにして DecisionTreeRegressor に投げます。

コード

このとき当然 DecisionTreeRegressor は2乗誤差*1を最小にするよう葉に属するサンプルにスコアを付けます。つまり平均値となっています。

ロス関数がRMSEのケースではそれで問題ないのですが、他の関数ではズレが生じます。そのため、木の分岐は DecisionTreeRegressor の結果を使うのですが、最終的なスコアには補正をかけて対応します。

例えば、ロス関数がMAEの場合は、葉に属するサンプルの中央値をスコアとして採用するのが、木の構造を所与としたときの最適となります。

コード

XGBoost

XGBoostでは正則化項が追加されているので最適化の目的関数が異なります。式の導出は別に譲りますが以下のようになります。

$\displaystyle \sum_{j=1}^M \left( G_j w_j + \alpha \left| w_j \right| + \frac{1}{2} \left( H_j + \lambda \right) w_j^2 \right) + \gamma T$

木の構造を所与としたとき最適な w_j^* は

$\displaystyle w_j^* = \frac{l \left( G_j , \alpha \right)}{H_j + \lambda} \\ \mathrm{where} \quad l(x, y) = \begin{array}{l} x - y \quad \mathrm{if} \ x \geq y \\ x + y \quad \mathrm{else} \end{array}$

となります。これは最適化の1階条件

$\displaystyle G_j + \alpha \mathrm{sign} \left( w_j^* \right) + \left( H_j + \lambda \right) w_j^* = 0 \\ \displaystyle w_j^* = -\frac{G_j + \alpha \mathrm{sign} \left( w_j^* \right)}{H_j + \lambda}$

によります。ここで $w_j^* \leq 0$ となるためには $G_j \geq \alpha$ でなければなりません。

これを代入すれば目的関数から w_j が消去できます。したがってXGBoostでは、ある分割についてはじめから最適なスコアを付ける前提で、最適な分岐を探索していることになります。

ポエム

XGBoostは通常の勾配ブースティングより精度が良いとされており、その原因は主としてL1/L2正則化にあるとされています。確かに通常の勾配ブースティングでもインサンプルの誤差を0にするのは簡単なので、汎化性能の高さは正則化によるものと考えるのが自然です。

しかしながら、今回見てきたようにXGBoostは通常のものより精度の高い近似計算をしています。個人的には正則化がそれほど効いていると思えないので、最適化の工夫によって高い汎化性能が実現しているのではないかと疑っています。 XGBoostの収束が速い分だけ、同水準のインサンプル誤差で比較したときに森の複雑性がより小さいと期待できるのではないでしょうか。

参考

The Elements of Statistical Learning（カステラ本）
Introduction to Boosted Trees
統計的学習の基礎読書会資料
Overview of tree algorithms

*1:オプションで絶対誤差も指定可能