勾配ブースティング

勾配ブースティング（こうばいブースティング、Gradient Boosting）は、回帰や分類などのタスクのための機械学習手法であり、弱い予測モデル weak prediction model（通常は決定木）のアンサンブルの形で予測モデルを生成する^[1][2]。決定木が弱い学習者 weak learner である場合、結果として得られる予測器は勾配ブースト木と呼ばれ、通常はランダムフォレストよりも優れている^[3]。他のブースティング手法と同様に段階的にモデルを構築するが、任意の微分可能な損失関数の最適化を可能にすることで一般化している。

歴史

勾配ブースティングのアイデアは、ブースティングが適切なコスト関数に対する最適化アルゴリズムとして解釈できるというレオ・ブライマンの観察に端を発している^[4]。その後、ジェローム・H・フリードマンが回帰勾配ブースティングアルゴリズムを開発し^[5][6]、Llew Mason、Jonathan Baxter、Peter Bartlett、MarcusFreanがより一般的な関数型勾配ブースティングの観点から発表した^{[7] [8]}。後者の2つの論文では、ブースティング・アルゴリズムを反復的な関数型勾配降下アルゴリズムとして捉えることが紹介された。すなわち、負の勾配方向を向く関数（弱い仮説 weak hypothesis）を繰り返し選択することにより、関数空間上のコスト関数を最適化するアルゴリズムである。このブースティングの関数型勾配としての見方により、回帰や分類にとどまらず、機械学習や統計学の多くの分野でブースティング・アルゴリズムが開発されている。

簡単な紹介

本節では、Li による勾配ブースティングの説明を紹介する^[9]。

他のブースティング方法と同様に、勾配ブースティングは、弱い学習器を反復的に結合し1つの強い学習器を構成する。最小二乗回帰の設定で説明するのが簡単で、

• ${\displaystyle {\hat {y}}_{i}}$ は ${\displaystyle F(x_{i})}$ の予測値
• ${\displaystyle y_{i}}$ は ${\displaystyle F(x_{i})}$ の観測値

とする。ここで、${\displaystyle i}$ は訓練集合におけるインデックスであり${\displaystyle n}$ は 訓練集合のの標本数である。目標は、平均二乗誤差${\displaystyle {\tfrac {1}{n}}\sum \nolimits _{i}(F(x_{i})-y_{i})^{2}}$ を最小化することにより未知の ${\displaystyle x}$に対する予測値を${\displaystyle {\hat {y}}=F(x)}$ によって得るようなモデル ${\displaystyle F}$ を訓練することである。

ここで、${\displaystyle M}$ 個のステージがからなる勾配ブースティング・アルゴリズムについて考える。勾配ブースティングの ${\displaystyle m}$（${\displaystyle 1\leq m\leq M}$）ステージ目において、いくつかの不完全なモデル ${\displaystyle F_{m}}$ を想定する。${\displaystyle m}$ が小さいうちは、このモデルは単にy の平均値を返すだけかもしれない（${\displaystyle {\hat {y}}_{i}={\bar {y}}}$）。${\displaystyle F_{m}}$ を改善するために新しい推定量 ${\displaystyle h_{m}(x)}$ を追加すると、

${\displaystyle F_{m+1}(x)=F_{m}(x)+h_{m}(x)=y}$

または、同等に、

${\displaystyle h_{m}(x)=y-F_{m}(x)}$

したがって、勾配ブースティングは、h を残差 ${\displaystyle y-F_{m}(x)}$ に適合させる。他のブースティング手法と同様、${\displaystyle F_{m+1}}$ は前任者${\displaystyle F_{m}}$のエラーを修正しようとする。二乗誤差以外の損失関数や分類・ランク付け問題に一般化すると、モデルの残差 ${\displaystyle h_{m}(x)}$ は ${\displaystyle F(x)}$ に関する平均二乗誤差損失関数の負の勾配に比例する。

${\displaystyle L_{\rm {MSE}}={\frac {1}{2}}\left(y-F(x)\right)^{2}}$

${\displaystyle h_{m}(x)=-{\frac {\partial L_{\rm {MSE}}}{\partial F}}=y-F(x)}$ 。

したがって、勾配ブースティングは勾配降下アルゴリズムに特化したものであり、これを一般化するには、異なる損失とその勾配を「プラグイン」する必要がある。

アルゴリズム

多くの教師あり学習問題では、出力変数 y と入力変数のベクトル x があり、相互に何らかの確率分布で関連している。目標は、入力変数の値から出力変数を最もよく近似する関数 ${\displaystyle {\hat {F}}(x)}$ を見つけることである。これは、損失関数 ${\displaystyle L(y,F(x))}$ の最小化として形式化することができる。

${\displaystyle {\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]}$ 。

勾配ブースティング法では、実数 y を仮定し、クラス${\displaystyle {\mathcal {H}}}$ の関数 ${\displaystyle h_{i}(x)}$ （基本学習者 base learners ないし弱い学習者 weak learners）の加重和の形で近似 ${\displaystyle {\hat {F}}(x)}$ を求める。

${\displaystyle {\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+{\mbox{const.}}}$

通常、既知の標本 x に対応する y の値からなるトレーニングセット ${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ が提供される。経験的リスク最小化の原則に基づき、トレーニングセットにおける損失関数の平均値を最小化する（経験的リスクを最小化する）近似${\displaystyle {\hat {F}}(x)}$ を探索する。これは定数関数 ${\displaystyle F_{0}(x)}$ に基づくモデルから開始し、貪欲法で段階的に拡張する。

${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}}$

${\displaystyle F_{m}(x)=F_{m-1}(x)+{\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right]}$ 、

ここで、${\displaystyle h_{m}\in {\mathcal {H}}}$ は基本学習関数。

残念ながら、任意損失関数Lに対して各ステップで最適な関数 h を選択することは、一般に計算上実行不可能な最適化問題である。そのため、単純化されたバージョンにアプローチを限定する。

この最小化問題に最急降下法のステップを適用する。

最急降下法の基本的な考え方は、${\displaystyle F_{m}(x)}$ を反復することによって損失関数の極小値を見つけることである。

${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma \sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$

ここで ${\displaystyle \gamma >0}$ 。これは、次のことを意味する。 ${\displaystyle L(y_{i},F_{m}(x_{i}))\leq L(y_{i},F_{m-1}(x_{i}))}$ 。

損失関数が最小値を取る ${\displaystyle \gamma }$ をみつけることで、${\displaystyle \gamma }$ を最適化することができる。

${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m})\right)}}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},}$

連続的な場合、つまり、 ${\displaystyle {\mathcal {H}}}$ を ${\displaystyle \mathbb {R} }$ 上の任意の微分可能な関数の集合と考えるト、次の式に従ってモデルを更新する

${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).}$

ここで、関数 ${\displaystyle F_{i}}$, ${\displaystyle i\in \{1,..,m\}}$ を微分する。${\displaystyle \gamma _{m}}$がステップ長である。離散的な場合、すなわち集合 ${\displaystyle {\mathcal {H}}}$ が有限の場合、L の勾配に最も近い h を選択する。この候補関数の係数 γ は、上記の方程式の線型探索を使用して計算できる。このアプローチはヒューリスティックであるため、特定の問題に対する正確な解決策ではなく、近似値が得られることに注意。擬似コードでは、一般的な勾配ブースティング方法は次のとおり^[5][2]。

Input: training set ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n},}$ a differentiable loss function ${\displaystyle L(y,F(x)),}$ number of iterations M.

Algorithm:

1. Initialize model with a constant value:

   ${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).}$

2. For m = 1 to M:
   1. Compute so-called pseudo-residuals:

      ${\displaystyle r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.}$

   2. Fit a base learner (or weak learner, e.g. tree) ${\displaystyle h_{m}(x)}$ to pseudo-residuals, i.e. train it using the training set ${\displaystyle \{(x_{i},r_{im})\}_{i=1}^{n}}$.
   3. Compute multiplier ${\displaystyle \gamma _{m}}$ by solving the following one-dimensional optimization problem:

      ${\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).}$

   4. Update the model:

      ${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).}$

3. Output ${\displaystyle F_{M}(x).}$

勾配ツリーブースティング

勾配ブースティングは通常、固定サイズの決定木（特にCART木）を基本学習者として使用する。フリードマンは、この特殊なケースに対して、各基本学習者の適合性を向上させる勾配ブースティング法の修正を提案している。

一般的な勾配ブースティングでは、m 番目のステップにおいて、決定木 ${\displaystyle h_{m}(x)}$ を疑似残差に適合させる。${\displaystyle J_{m}}$ をその葉の数とする。ツリーは入力空間を ${\displaystyle J_{m}}$ 個の互いに素な領域 ${\displaystyle R_{1m},\ldots ,R_{J_{m}m}}$に分けて各地域の定数値を予測する。入力 x に対する出力 ${\displaystyle h_{m}(x)}$ を指示関数を使って記述すると

${\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x)}$

ここで、${\displaystyle b_{jm}}$は領域 ${\displaystyle R_{jm}}$ における予測値を表す^[10]。

次に、係数 ${\displaystyle b_{jm}}$ に ${\displaystyle \gamma _{m}}$（損失関数を最小化するように線型探索で選択する）を乗じ、モデルは次のように更新される。

${\displaystyle F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).}$

フリードマンは、木全体に対する ${\displaystyle \gamma _{m}}$ ではなく、領域毎に異なる別の最適値 ${\displaystyle \gamma _{jm}}$ を選択するようにこのアルゴリズムを修正することを提案している。彼は修正されたアルゴリズムを「TreeBoost」と呼んでいる。係数 ${\displaystyle b_{jm}}$ を破棄して、モデルの更新規則は次のようになる。

${\displaystyle F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,}$

木のサイズ

${\displaystyle J}$ は木の末端ノードの数であり、本手法のパラメータで、手元のデータセットに合わせて調整できる。これは、モデル内の変数間の交互作用の最大許容レベルを制御する。${\displaystyle J=2}$ （決定株）では、変数間の交互作用は許可されていない。また、${\displaystyle J=3}$ では、最大2つの変数の間の交互作用の影響をモデルに含めることができる。

Hastie らは、典型的には ${\displaystyle 4\leq J\leq 8}$ でブースティングが上手くいき、結果は ${\displaystyle J}$ の選択にあまり影響を受けないが、${\displaystyle J=2}$ では不十分であり、${\displaystyle J>10}$ が必要になることはあまりないと述べている^[2]。

正則化

トレーニングセットをフィットさせすぎると、モデルの汎化能力が低下してしまう。正則化と呼ばれるいくつかの手法は、フィッティング手順を制約することで、このオーバーフィッティングを軽減する。

自然な正則化パラメータの一つに、勾配ブースティングの反復回数 M （すなわち、基本学習者が決定木である場合、モデルに含まれる木の数）がある。 M を増加させると、トレーニングセットのエラーが減少するが、M が大きすぎると、オーバーフィッティングにつながる可能性がある。M の最適な値は、別の検証データセットで予測誤差を監視することによって選択されることが多い。 Mの制御以外にも、いくつかの正則化手法が使用される。

もう1つの正則化パラメータは、木の深さである。この値が大きいほど、モデルがトレーニングデータに過剰適合する可能性が高くなる。

収縮

勾配ブースティング方法の重要な部分は、収縮による正則化であり、更新規則を次のように変更することである。

${\displaystyle F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,}$

ここでパラメータ${\displaystyle \nu }$ は「学習率」と呼ばれる。

経験的には、小さな学習率（例えば ${\displaystyle \nu <0.1}$ など）を用いると、学習率を下げずに勾配ブースティングを行った場合（${\displaystyle \nu =1}$）に比べて、モデルの汎化能力が劇的に向上することが分かっている^[2]。 ただし、学習率が低いと反復回数が多くなり、学習時と検索時の計算時間が長くなる。

確率的勾配ブースティング

勾配ブースティングが導入後されて間もない頃、フリードマンは、ブレイマンのブートストラップ・アグリゲーション（バギング）法を参考にして、アルゴリズムのマイナーチェンジを提案した^[6]。具体的には、アルゴリズムの各反復において、置換なしでランダムに抽出されたトレーニングセットのサブサンプルにベース学習器を適合させることを提案した。^[11]。フリードマンは、この変更により、勾配ブースティングの精度が大幅に向上することを確認しました。

サブサンプルはトレーニングセットから一定の割合${\displaystyle f}$で選ばれる。${\displaystyle f=1}$ のとき、アルゴリズムは決定論的であり、上記のものと同じになる。${\displaystyle f}$ の値が小さいと、アルゴリズムにランダム性を導入し、オーバーフィッティングの防止に役立つ。回帰木は各反復でより小さなデータセットに適合させるため、アルゴリズムも高速になる。フリードマンは小規模および中規模のトレーニングセットのいて ${\displaystyle 0.5\leq f\leq 0.8}$ で良好な結果が得られることを突き止めた^[6]。そのため、${\displaystyle f}$ は通常は0.5に設定される。これは、トレーニングセットの半分が各基本学習者の構築に使用されることを意味する。

また、バギングの場合と同様に、サブサンプリングでは、次の基本学習者の構築に使用されなかった観測値の予測を評価することで、予測性能の向上のアウトオブバッグエラーを定義できる。アウトオブバッグの推定値は、独立した検証データセットの必要性を回避するのに役立つが、実際の性能向上や最適な反復回数を過小評価することがよくある^{[12] [13]}。

葉の観察数

勾配ツリーブースティングの実装では、木の末端ノードでの観測の最小数を制限する正則化もよく使用される。この正則化は、木の構築プロセスにおいて、この数より少ないトレーニングセットインスタンスを含むノードにつながる分割を無視する。

この制限を設けることで、葉での予測のばらつきを抑えることができる。

ツリーの複雑さにペナルティを課す

勾配ブーストツリーのもう1つの有用な正則化手法は、学習したモデルのモデルの複雑さにペナルティを課すことである^[14]。モデルの複雑さは、学習したツリーの葉の数に比例するものとして定義できる。損失とモデルの複雑さの共同最適化は、損失をしきい値で減らすことができない枝を取り除くポストプルーニング・アルゴリズムに対応する。他の正則化の種類としては、${\displaystyle \ell _{2}}$正則化を行うことで、オーバーフィッティングを防ぐことができる。

使用法

勾配ブースティングは、ランク付けの学習の分野でも利用されている。商用ウェブ検索エンジンであるYahoo! ^[15]や Yandex ^[16]は、機械学習型のランキングエンジンに勾配ブースティングの変法を使用している。また、高エネルギー物理学の分野でも、データ解析に勾配ブースティングが利用されている。大型ハドロン衝突型加速器（LHC）では、ヒッグス粒子の発見に使用されたデータセットにおいて、勾配ブースティングを用いたディープニューラルネットワーク（DNN）が、機械学習ではない解析方法の結果を再現することに成功した^[17]。

名前

この方法にはさまざまな名前が付けられている。 フリードマンは、自分の回帰手法を「Gradient Boosting Machine」（GBM）として紹介した^[5]。 メイソン、バクスターらは、一般化された抽象的なクラスのアルゴリズムを「関数的勾配ブースティング」と表現している^{[7] [8]}。フリードマンらは、勾配ブーストモデルを発展させたものを Multiple Additive Regression Trees（MART）と表現し^[18]、Elithらは、そのアプローチを「Boosting Regression Trees」（BRT）として説明する^[19]。

R言語のオープンソースの実装では「Generalized Boosting Model」と呼んでいるが^[12] 、「BRT」を使用している^[20]。また、木ベースの方手法を開発した研究者の1人であるSalford System社のDan Steinbergによる初期の商用実装にちなんで、TreeNet とも呼ばれている^[21]。XGBoostは、2次最適化などの拡張機能を備えた最新の実装として人気がある。

短所

ブースティングは、決定木や線形回帰などの基本学習者の精度を高めることができるが、分かりやすさ intelligibility や解釈のしやすさ interpretability を犠牲にする^{[1] [22]}。また、計算量が多くなるため、実装が難しくなることもある。

関連項目

• AdaBoost
• ランダムフォレスト
• CatBoost
• LightGBM
• XGBoost
• 決定木