XGBoostの主な特徴と理論の概要

# はじめに
[前回の記事](http://qiita.com/yh0sh/items/276dce93cd1e48d372d1)では，[DMLC](http://dmlc.ml/)が提供する[XGBoost](https://github.com/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](http://fastml.com/what-is-better-gradient-boosted-trees-or-random-forest/)

# 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](http://www.analyticsvidhya.com/blog/2016/03/complete-guide-parameter-tuning-xgboost-with-codes-python/)

# Gradient Tree Boosting
次に，XGBoostの理論となるGradient Tree Boostingについて説明します．
この内容は，主にXGBoostの[元論文](http://arxiv.org/abs/1603.02754)を参考にしています．

## Tree Ensemble Model
*Tree Ensemble Model*の予測値$\hat{y}_i$は以下の式で表されます．

```math
\hat{y}_i=\phi(\textbf{x}_\textbf{i})=\sum_{k = 1}^K f_k(\textbf{x}_\textbf{i}),\ f_k \in \mathcal{F}
```
```math
where\ \mathcal{F} = \{f(\textbf{x}) = w_{q(\textbf{x})} \}
```
```math
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](https://en.wikipedia.org/wiki/Gradient_boosting#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より)

## モデル評価式
モデル評価には，正則項を加えた下記の式の最小化を行います．

```math
L(\phi)=\sum_{i} l( \hat{y}_i, y_i)+ \sum_{k}\Omega(f_k)
```
```math
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$を新たに加えることで，評価式を変形します．

```math
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次項まで求め，定数項を除くことで，下記の式を得ます．

```math
\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)
```
```math
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$の最適値は以下となります．

```math
\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
```
```math
where\ I_j := \{ i|q( \textbf{x}_i ) = j \}
```
上記の式を**スコア関数**と言います．$I_j$は葉$j$のインスタンス集合と言います．

$I$を左側および右側のノードのインスタンス集合$I_L$，$I_R$に分岐する場合，$I=I_L \bigcup I_R$の下で損失の減少量は以下で求められます．

```math
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 
```
上記の式より分岐を行うか決定し，最適なモデルを求めます．