Gradient Boosting と XGBoost

2017年5月6日に個人のブログで公開した記事を移植してきたものです。内容は更新していないため古かったり不正確な部分があると思うのでご注意ください。

Gradient Boosting や XGBoostについて調べたことをまとめました。Gradient Descent や Newton 法と絡めて説明していきたいと思います。

Boosting

Boosting とは、ランダムより少し良い程度の"弱い"学習アルゴリズムを使って、そのアルゴリズムよりも"強い"学習アルゴリズムをつくることです。イメージとしては、弱い学習アルゴリズムを "boost" してあげる感じでしょうか。

そもそもそんなことって理論的に可能なの？という問いから Boosting の歴史が始まったわけですが、Boosting が可能であることは、1989年に Robert E. Schapire 大先生によって PAC Learning という枠組みで実際に Boosting を行うアルゴリズムを示す形で証明されました^[1]。

Boosting のアルゴリズムで大きな成功を収めたもののひとつが、^[2]で提案された AdaBoost で以降の Boosting アルゴリズムは AdaBoost に大きな影響を受けています。なんとなく Boosting と言えば逐次的に学習器を構築して、その和をとる、というようなイメージがありますが、それも AdaBoost 由来だと思います。たぶん。

$t$ 回目の反復で"弱い"学習アルゴリズムにより構築された学習器(弱学習器)を $f_t$とすると、よく使われている Boosting アルゴリズムのほとんどは次のような形で表されます。

$$F_T(x)=\sum_{t=1}^{T}\alpha_t f_t(x)$$

ここで $F_T(x)$ が Boosting アルゴリズムの出力で、$\alpha_t$ は適当に設定された係数です。

Gradient Descent (Steepest Descent)

Gradiet Boosting の説明をする前に Gradiet Boosting 非常に関連の強い Gradient descent (勾配降下法)に触れておきます。Steepest Descent (最急降下法) とも呼ばれているアレです。

Gradient Descent は関数 $\phi:\mathbb{R}^n \rightarrow \mathbb{R}$ を最小化するような $p\in\mathbb{R}^n$ を探すアルゴリズムで、繰り返し $\phi$ が小さくなる方向に解を更新し、最適解に近づけていきます。具体的には $t-1$ 回目の反復が終わった後の解を $p_{t-1}$ として、

$$p_t = p_{t-1} - \alpha_t \nabla \phi(p_{t-1})$$

と解の更新を行います。ここで $- \nabla \phi(p_{t-1})$ が減少する方向を表していて、$\alpha_t$ がこの更新でその方向にどれだけ動かすかを表しています。

$\alpha_t$ の決め方はいくつか提案されていますが、Line Search と呼ばれる手法では $\phi(p_{t-1} - \alpha \nabla \phi(p_{t-1}))$ を最小化する $\alpha$ を用います。

ニューラルネットの学習などの文脈で Gradient Descnet が使われる場合には、N個のデータ $(x_i, y_i)$ と損失関数$L$に対して、$p$ をパラメータ、$F(x; p)$ を $p$ の下での関数(学習器)の出力として、

$$\phi(p)=\sum_{i=1}^{N} L(y_i, F(x_i;p))$$

を最小化するパラメータ $p$ を求めるために使われることが多いです。この場合の Gradient Descent を、パラメータを変化させて目的関数を最小化するという意味で、パラメータ空間における Gradient Descent と言うことにしましょう。

パラメータ空間における Gradient Descent で、$T$回反復を終えた後の解は $p'_t = - \nabla \phi(p_{t-1})$ とおいて、初期値を $p_0$ とすると、次のように表すことができます。

$$p_T = p_0 + \sum_{t=1}^{T} \alpha_t p'_t$$

なんとなく Boosting の式と似てませんか？

Boosting では、すでに学習した弱学習器のパラメータを変化させるのではなく、新しい弱学習器を加えることにより全体の出力を変化させることができます。そこで、目的関数を $F_{t-1}$ で微分して降下方向を出し $f_t$ をそれにfitさせることで、関数の空間で Gradient Descent をしよう、というのがGradient Boosting になります。

Gradient Boosting^[3]

関数区間で Gradient Descent をする場合には目的関数は次のように書けます。

$$\phi(F) = \sum_{i=1}^{N}L(y_i, F(x_i))$$

しかし各データの損失の和を最小化する方向を求めるのは一般には難しいので、各データ $(x_i, y_i)$ についてそれぞれで損失 $L(y_i, F(x_i))$ を小さくすることを考えます。つまり各 $x_i$ について損失が小さくなる向きに関数の出力を変化させるわけです。

$t-1$ 回目の反復が終わった後の全体の出力を$F_{t-1}(x)$として、$F_t(x)$ が各 $(x_i, y_i)$ に対して次のようになってくれればうれしいです。(出力に1次元を想定しているので $\nabla$ はただの偏微分になります)

$$F_{t}(x_i) = F_{t-1}(x_i) - \alpha_t \frac{\partial L(y_i, F_{t-1}(x_i))}{\partial F_{t-1}(x_i)}$$

従って、

$$f_t(x_i) = - \frac{\partial L(y_i, F_{t-1}(x_i))}{\partial F_{t-1(x_i)}}$$

となるように弱学習器 $f_t$ の学習を行います。具体的には各 $x_i$ に対して次のような $\tilde{y_i}$ を考え、

$$\tilde{y_i} = - \frac{\partial L(y_i, F_{t-1}(x_i))}{\partial F_{t-1}(x_i)}$$

データ $(x_i, \tilde{y_i})$ に対して二乗誤差

$$\sum_{i=1}^N(\tilde{y_i} - f_t(x_i))^2$$

が最小になるように弱学習器 $f_t$ をfitさせます。その後、全体の損失 $\phi(F_{t-1} + \alpha_t f_t)$ が小さくなるように$\alpha_t$ を Line Search などで決定します。

$T$回反復を終えた後の解は、初期値を $f_0$ として、次のように表すことができます。

$$F_T(x) = f_0(x) + \sum_{t=1}^{T} \alpha_t f_t(x)$$

これが最もベーシックな Gradient Boosting になります。初期値については元論文^[3:1]では目的関数を最小化するような定数にしています (XGBBoost の実装は確認してない)。

疑似コードにすると次のようになります。

Regression Tree

これまでは弱学習器に何を用いるか特に決めずに解説しましたが、Gradient Boosting では回帰木 (Regression Trees) が使われることが多いため、回帰木のCART^[4]による構築について触れておきます。Gradient Boostingの話からは少しずれるので興味ない場合は飛ばしても大丈夫だと思います。

回帰木では葉に値が紐づいています (その値を葉の重みと呼びます)。葉が $T$ 個あるとして、適当に葉に1から$T$までの番号をふり、その葉の重みを $w_j (j=1,2,\dots,T)$ と表すことにします。また、木への入力 $x$ がたどり着く葉の番号を $q(x)$ としましょう。$x$ に対する木の出力 $f(x)$ は次のように書けます。

$$f(x) = w_{q(x)}$$

今回は Gradient Boosting に使う弱学習器という文脈なので、N個のデータ$(x_i, \tilde{y_i})$に対して、二乗誤差和を最小化する木の構築を考えてみます。

$$\sum_{i=1}^N (\tilde{y_i} - f(x_i))^2$$

この式は、木の構造が決まっているとき、すなわち関数 $q$ が決まっているとき、$j$ 番目の葉にたどり着くデータの集合 $I_j = \{ i~|~1\leq i\leq N, q(x_i) = j \}$を用いて

$$\sum_{j=1}^T \sum_{i\in I_j} (\tilde{y_i} - w_j)^2$$

と変形できます。さらにガチャガチャ変形すると

$$\sum_{j=1}^T |I_j|(w_j - \sum_{i=1}^N \frac{y_i}{|I_j|})^2 + constant$$

となり$w_j$ の値を $I_j$ に含まれる $y_i$ の平均にすることで最小値を取ることがわかります。このように、最小化したいものが二乗誤差和である場合には、ある木が実現できる最小値が解析的に求められます。(今回は二乗誤差でしたが他にも様々な損失関数に対して使えます)

この最小値をその木の評価値(一般的には不純度と呼ばれます)として扱い、この評価値が低くなるように木の構築を行います。木の構築では、ルートノード1つしかない状態から始めて、一定の深さになるか損失が下がらなくなるまでノードの分割を繰り返します。

分割対象になったノードに対して、そのノードに到達するデータの集合を $I$とし、ある特徴量のある値を閾値として $I$ が $I_L$ と $I_R$ に分割されたとします。その分割による木の評価値の変化(減少量)は次のように表されます。

Gain = ( $I$ の評価値) - ( $I_L$ の評価値 + $I_R$ の評価値)

これを$I$のすべてのデータのすべての特徴量で試し一番Gainが大きくなるものを選びます。

この厳密に全ての候補について試すという方法は XGBoost の論文では "Exact" Greedy Algorithm と呼ばれています。

Gradient Tree Boosting^[3:2]

回帰木を使う場合にはGradient Boostingをさらに効率的に行うことができます。Gradient Boosting で最小化したい目的関数は、木の構造が決まると、

$$\sum_{j=1}^T \sum_{i\in I_j} L(y_i, F_{t-1}(x_i) + w_j)$$

と変形することができます。この式が解析的に解ける場合には、$(x_i, \tilde{y_i})$ にfitするように木を構築した後、$w_j$ をこの式を最小化するように再び変更することで Line Search などで $\alpha_t$ を決める処理を行う必要がなくなるわけです。

でもその式が解析的に解けるのであれば、最初から $(x_i, \tilde{y_i})$ の二乗誤差和じゃなくて

$$\sum_{i=1}^N L(y_i, F_{t-1}(x_i) + f_t(x_i))$$

を最小化するように木を構築すればいいじゃないかと思うわけですが、二乗誤差和を損失に使うほうが断然早いので良いという感じらしいです。

Learning rate^[3:3]

Gradient Boosting の正則化として、更新を行う際に次のように Learning Rate (学習率) $\eta$ を使う方法が提案されています。

$$F_t(x) = F_{t-1}(x) + \eta \alpha_t f_t(x)$$

学習率を低くするとパフォーマンスが良くなるということが経験的に知られていて、学習率を低くするとその分最適な反復回数は大きくなることも言われています。(ここで言う最適は leave-out test sample で損失が最小になる回数)

(XGBoost を)実際に使ってみている感覚としては学習率は確かに小さいほうが良くて、0.01とか0.005くらいで十分に小さいという印象があります。それ以上は小さくしても遅くなるだけであまり精度に違いはでない感じがします。0.1とかだとやや大きいけどやや大きいけどデータによっては十分精度が出て、1.0だとかなり過学習しやすいような感じです(個人の感想です)。

Newton Boosting

さて、これまで説明した Gradient Boosting は関数空間で Gradient Descent を用いて目的関数を最小化しているのでした。

次はこの最小化を Gradient Descent でなく Newton 法で行う場合について考えてみます。(ここでいう Newton 法は根を見つける手法のことではありません)

Newton 法では目的関数をテイラー展開で二次の項まで近似して、高校数学で習った二次関数の最小化と同じノリで最小化を行います。

弱学習器 $f_t$ を加えるときの目的関数は次の式で表せます。

$$\sum_{i=1}^{N}L(y_i, F_{t-1}(x_i) + f_t(x_i))$$

この式を二次近似して次式を得ます。

$$\sum_{i=1}^{N}[~L(y_i, F_{t-1}(x)) + g_i f_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)~]$$

ここで $g_i = \frac{\partial L(y_i, F_{t-1}(x_i))}{\partial F_{t-1}(x_i)}$ で $h_i = \frac{\partial^2 L(y_i, F_{t-1}(x_i))}{\partial^2 F_{t-1}(x_i)}$です。
(ちなみに $-g_i$ は Gradient Boostingでの $\tilde{y_i}$ と一致します) この式を変形して $f_t$ に関係の無い項をconstantとすると次のようになります。

$$\sum_{i=1}^{N}[~\frac{h_i}{2} (f_t(x_i) + \frac{g_i}{h_i})^2 ~] + constant$$

$(x_i, - g_i / h_i)$ に対する二乗誤差が $h_i$ で重みづけされた形になりました。この式を最小化するように $f_t$ の構築を行う方法をNewton Boostingと呼びます^[5]。回帰木では先の二乗誤差和の例と同様に、この式を直接目的関数として扱うことができます。

Newton法では、目的関数が二次でない場合は適当に定めた $\alpha_t$ を使うのですが、これは Learning Rate を適当にスケールして吸収すればよいので、Newton Boosting の場合は $\alpha_t=1$ とします。

XGBoost^[6]

XGBoostではこのNewton Boostingが採用されています。さらに、木の正則化を行うための項を最小化する目的関数 $\phi$ に直接入れているのが特徴的です。(個人的には木はtrimとかで正則化するイメージですが直接目的関数にいれています)

具体的には次のような目的関数を設定しています。

$$\phi(F_t) = \sum_{i=1}^{N}L(y_i, F_t(x_i)) + \sum_{k=0}^t \Omega(f_k)$$

$$\Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^2$$

ここで、$T$ は回帰木 $f$ の葉の数、$w$ は葉の重みで、$\gamma, \lambda$はハイパーパラメータです。この形の正則化項であれば、普通の Newton Boosting と同じように二次近似して変形することで同じように回帰木を構築しやすい形にできます。

XGBoostを実際に使うときの指定としてはそのまま $\gamma$ は gamma、$\lambda$ は lambda というパラメータがあります。デフォルトの値はそれぞれ $0$ と $1$ です。論文には載っていませんが、doc/parameter.md を見る限り alpha というパラメータで葉の重みのL1ノルムでの正則化も行えるようです。

また、高速化のための工夫として、データの数や次元数が大きくなった場合、木の構築に Exact Greedy Algorithm を使うと時間がかかりすぎてしまうのを改善するため、分割に使う候補を絞る Weighted Quantile Sketch という手法も提案されています。

データが沢山あって、ここから分割の候補を $m$ 個選んでください、と言われたとき、素直な方法として、小さい順に並べて等間隔に $m$ 個取る、という方法が考えられます。この、同じ要素数の $m$ 個の部分集合に分割する点を $m$-Quantiles ($m$-分位点) と言い、Quantileを高速に求めるアルゴリズムとして Quantile Sketch^[7] があります。

Weighted Quantile Sketchはその名の通り、このQuantile Sketchを重み付きに拡張したものです。

Newton Boosting の項で説明した通り、XGBoostの目的関数は二乗誤差が $h_i$ で重みづけられた形になるため、$h_i$ が大きいほど $f_t$ でうまくfitできなかったとき目的関数に与える影響が大きくなります。そこで通常のQuantile Sketchのように各々1つとして扱ってQuantileを求めるのでなく、$h_i$ で重みづけしQuantile Sketchを行います。

既存研究では無かった理論保証付きのアルゴリズムを提案したそうで、論文でめっちゃ推されてます。詳しい内容については XGBoost 論文の Supplementary Material に載っています。

Sketching を使用するように明示的に指定するにはパラメータの tree_method を 'approx' にすれば良いです。また sketch_eps で候補点がどれくらい離れるかを指定できます。

この他にも、スパースなデータに対して高速に分割を見つけるアルゴリズムが実装されていたり、データをブロック化して効率的に扱う機能がついていたりなど、大規模な環境で高速に動作するために様々な工夫が行われています。

Generalization Error

理論的な汎化誤差についてはまだわかっていることは少ないようです(たぶん)。

ここが私が一番気になっているところで、Gradient Boostingでは加えた後の経験損失が小さくなるように弱学習器を足しているわけですが、なんで弱学習器をより複雑にして損失をさげるよりも、複雑でない弱学習器でこの手続きを繰り返すほうがうまくいくのでしょうか。また、なんで $\alpha_t$ を求めた上でさらに学習率をかける方法がうまくいくのでしょうか。不思議です。その辺について、汎化誤差から理論的に何か言えることはないのかなと思っています。

AdaBoost については元々統計的機械学習というより学習理論の分野で出てきたこともあって、古くから汎化誤差について研究が進められています。ここら辺は正直ちゃんと理解できておらずうまく説明できる気がしないので、詳しくは AdaBoost に関する survey 論文^[8]の章とか、margin の話の論文^[9]とかを読んでくださいという感じです。参照している論文が結構古いのでもしかしたらそこらへんの研究はもう少し進んでいるかもしません。

また、Gradient Boosting の汎化誤差については調べてみたものの見つからなかったので、これらについて何か情報があったら教えてもらえると非常に助かります。もしかしたら Gradient Descent のほうから調べていったほうが良いのかもしれません。よくわからんという感じです。強い人教えてください。

脚注

1. Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.

2. Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.

3. Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5), 2001.

4. Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and regression trees. The Wadsworth and Brooks-Cole statistics-probability series, Taylor & Francis.

5. Didrik Nielsen. Tree Boosting With XGBoost - Why Does XGBoost Win “Every" Machine Learning Competition? Master thesis, Norwegian University of Science and Technology, 2016.

6. Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 785-794, 2016.

7. Michael Greenwald and Sanjeev Khanna. Space-Efficient Online Computation of Quantile Summaries. Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 58-66, 2001

8. Robert E. Schapire. The boosting approach to machine learning: An overview. Nonlinear estimation and classification. 149-171, 2003.

9. Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651–1686, 1998.