MachineLearning
xgboost
randomForest
gradientTreeBoosting

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

More than 1 year has passed since last update.

はじめに

前回の記事では,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)を下げていき,その都度最適化を行う

最後の2つについては,下記の記事にパラメータのチューニング方法が紹介されています.
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 

上記の式より分岐を行うか決定し,最適なモデルを求めます.