Help us understand the problem. What is going on with this article?

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

More than 3 years have 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 

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

yh0sh
職業柄,機械学習や統計の記事を書くことが多いです.
http://yh0sh.hateblo.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした