XGBoostを理解する Part 1

XGBoostについて調べたのでメモ．

Boostingは，弱学習器を順番に学習させていく手法であり，XGBoostもその一種である．入力を$\bm{x} \in \mathbb{R}^d$, 出力を$y \in \bm{R}$とし，以下のモデルを考える．

$\begin{aligned} \hat{y}(\bm{x}) = \sum_{k=1}^K f_{k} (\bm{x}) \end{aligned}$

$f_k$が弱学習器であり，$K$個の弱学習器を使って最終的な予測を行うようなモデルになっている．$f_k$にはよく決定木が用いられる．
$t$個目の弱学習器$f_t$を学習させるにあたり，次のような目的関数を考える．

$\begin{aligned} \mathcal{L}^{(t)} = \sum_{i=1}^n \ell(y_i, \hat{y}^{(t-1)}_i + f_t(\bm{x}_i)) + \Omega(f_t) \end{aligned}$

ここで，$\ell$は損失関数であり，$\Omega$は正則化項である．
$F(y') = \ell(y, y')$として，$F$を以下のように$\hat{y}^{(t-1)}$まわりで二次のテイラー展開する．

$\begin{aligned} F(y') = \ell(y, \hat{y}^{(t-1)}) + F'(\hat{y}^{(t-1)})(y' - \hat{y}^{(t-1)}) + \frac{1}{2} F''(\hat{y}^{t-1})(y' - \hat{y}^{(t-1)})^2 \end{aligned}$

これを用いると，$\mathcal{L}^{(t)}$は以下のように近似できる．

$\begin{aligned} \mathcal{L}^{(t)} \approx \sum_{i=1}^n \left[\ell(y, \hat{y}^{(t-1)}) + g_i f_t(\bm{x}_i) + \frac{1}{2} h_i f_t(\bm{x}_i)^2\right] \end{aligned}$

ただし，$g_i = \ell'(y_i, \hat{y}_i^{(t-1)}), h_i = \ell''(y_i, \hat{y}_i^{(t-1)})$とした．
定数項を除き，$\Omega(f_t) = + \gamma T + \frac{1}{2} \sum_{j=1}^T w_j^2$とすると，最終的には以下の目的関数の最小化を目指す．

$\begin{aligned} \tilde{\mathcal{L}}^{(t)} &= \sum_{i=1}^n \left[g_i f_t(\bm{x}_i) + \frac{1}{2} h_i f_t(\bm{x}_i)^2\right] + \gamma T + \frac{1}{2} \sum_{j=1}^T w_j^2\\ &= \sum_{j=1}^T \left[w_j G_j + \frac{1}{2}w_j^2 H_j\right] + \gamma T + \frac{1}{2} \sum_{j=1}^T w_j^2 \end{aligned}$

ここで，$G_j = \sum_{i:q(\bm{x}_i)=j} g_i, H_j = \sum_{i:q(\bm{x})=j} h_i$とした．この最適解は以下を満たす．

$\begin{aligned} w_j = - \frac{G_j}{H_j + \lambda} \end{aligned}$

これで，重みの学習は終わり．しかしながら，$G_j$や$H_j$を求めるには$q$（正確には$q_t$）を求めなければならない．この続きは次回．