はじめに
前回の記事では，DMLCが提供するXGBoostパッケージを用いて，Boosted treesの実装をRを用いて行いました．
本記事ではXGBoostの主な特徴と，その理論であるGradient Tree Boostingについて簡単に纏めました．
XGBoostを導入する場合や，パラメータチューニングの際の参考になればと思います．
Boosted treesは，Gradient BoostingとRandom Forestのアルゴリズムを組み合わせたアンサンブル学習となります．
Boosted treesの予測精度はRandom Forestsよりも向上しますが，チューニングが必要なパラメータが複数存在します．
一方，Random Forestsはチューニングが不要なのですが，学習データに依存しやすく，過学習となりやすいです．
What is better: gradient-boosted trees, or a random forest? - FastML
XGBoostの主な特徴
XGBoostの主な特徴を以下に纏めました．時間のない方など，ここだけ見て頂ければと思います．
XGBoostとは，Gradient BoostingとRandom Forestsを組み合わせたアンサンブル学習である
高いスケーリング性を持つend-to-endなtree boostingシステムをもつ
sparseなデータ(値が欠損，0が多い，one-hot encodingなどの特殊な処理を施したなど)について，予め分岐の方向を決めるアルゴリズムを導入している
CPU外(out-of-core)での学習が可能であり，計算速度が高速化されている
複数のパラメータ調整によるチューニングが必要であり，最適化はグリッドサーチやCross Validationを複数行う
汎化能力を上げるために，学習率(XGBoostパッケージではパラメータeta)を下げていき，その都度最適化を行う
最後の２つについては，下記の記事にパラメータのチューニング方法が紹介されています．
Complete Guide to Parameter Tuning in XGBoost (with codes in Python) - Analytics Vidhya
Gradient Tree Boosting
次に，XGBoostの理論となるGradient Tree Boostingについて説明します．
この内容は，主にXGBoostの元論文を参考にしています．
Tree Ensemble Model
Tree Ensemble Modelの予測値$\hat{y}_i$は以下の式で表されます．
\hat{y}_i=\phi(\textbf{x}_\textbf{i})=\sum_{k = 1}^K f_k(\textbf{x}_\textbf{i}),\ f_k \in \mathcal{F}
where\ \mathcal{F} = \{f(\textbf{x}) = w_{q(\textbf{x})} \}
q:\mathbb{R}^m \rightarrow T,w \in \mathbb{R}^T
$\textbf{x}_\textbf{i}$:入力値
$\hat{y}_i$:予測値
$T$:葉の数
$w$:葉の重み
$\mathcal{F}$は回帰木空間(CART)と呼ばれ，$T$，$w$が定義されます．
作成する$K$個の木構造$q$にある，葉$i$の重み$w_i$をスコアとして，その総和($\sum f$)で得られる予測値$\hat{y}_i$と目的値$y_i$を比較します．
注意点として，作成する$K$個の木で共通する，$i$番目に位置する葉の($f$の)総和をとっている点です．
$K$個の木がもつ葉の数は一定で，その値をパラメータ(XGBoostパッケージではmax_depth)として与えます．
この説明は，WikipediaのGradient tree boostingの項目で記述されています．
Gradient boosting is typically used with decision trees (especially CART trees) of a fixed size as base learners.
$J$, the number of terminal nodes in trees, is the method's parameter which can be adjusted for a data set at hand.
(Wikipediaより)
モデル評価式
モデル評価には，正則項を加えた下記の式の最小化を行います．
L(\phi)=\sum_{i} l( \hat{y}_i, y_i)+ \sum_{k}\Omega(f_k)
where\ \Omega(f)=\gamma T+\frac{1}{2} \lambda \parallel w \parallel^2
$y_i$:目的値
$l$:$\hat{y}_i$と$y_i$の差分を測るための微分可能な凸損失関数
$\Omega$:正則化項
$\gamma$，$\lambda$:パラメータ
正則項$\Omega$は，モデルの複雑性に罰則を与えることで，過学習を抑える働きがあります．
$\Omega$には，パラメータ$\gamma$を乗じた葉の数$T$を加算します．
Gradient Tree Boosting
本題のGradient Tree Boostingです．
学習で得られたTree Ensemble Modelの$w$を更新して，$L$を最小化する最適なモデルを求めます．
更新の際，$L$に$\sum f_t$を新たに加えることで，評価式を変形します．
L^{(t)} =\sum_{i=1}^n (l( y_i, \hat{y}_i^{ (t-1) } ) + f_t ( \textbf{x}_i ) ) + \Omega(f_t)
上記の式の$f_t$をTaylor展開の2次項まで求め，定数項を除くことで，下記の式を得ます．
\tilde{L}^{(t)} =\sum_{i=1}^n [g_i f_t ( \textbf{x}_i ) + \frac{1}{2} h_i f_t^2 ( \textbf{x}_i ) ]+ \Omega(f_t)
where\ g_i=\partial_{\hat{y}_i^{ (t-1) } } l(y_i,\hat{y}_i^{(t-1)}),\ h_i=\partial_{\hat{y}_i^{ (t-1) } }^2 l(y_i,\hat{y}_i^{(t-1)})
木の構造$ q( \textbf{x} ) $が固定のとき，$L$の最適値は以下となります．
\tilde{L}^{(t)} (q) =-\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 T
where\ I_j := \{ i|q( \textbf{x}_i ) = j \}
上記の式をスコア関数と言います．$I_j$は葉$j$のインスタンス集合と言います．
$I$を左側および右側のノードのインスタンス集合$I_L$，$I_R$に分岐する場合，$I=I_L \bigcup I_R$の下で損失の減少量は以下で求められます．
L_{split} = \frac{1}{2} \left[ \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 } \right] - \gamma
上記の式より分岐を行うか決定し，最適なモデルを求めます．