勾配ブースティング

勾配ブースティング（こうばいブースティング、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]。

勾配ブースティングは通常、固定サイズの決定木（特に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
• 決定木

• Boehmke, Bradley; Greenwell, Brandon (2019). “Gradient Boosting”. Hands-On Machine Learning with R. Chapman & Hall. pp. 221–245. ISBN 978-1-138-49568-5 

• 勾配ブースティングを説明する方法
• 勾配ブースト回帰ツリー
• LightGBM

表 話 編 歴 統計学
標本調査	標本 母集団 無作為抽出 層化抽出法
記述統計学	連続データ 位置 平均 算術 幾何 調和 中央値 分位数 順序統計量 最頻値 階級値 分散 範囲 偏差 偏差値 標準偏差 標準誤差 変動係数 決定係数 相関係数 自己相関 共分散 自己共分散 分散共分散行列 百分率 統計的ばらつき モーメント 分散 歪度 尖度 カテゴリデータ 頻度 分割表
推計統計学	仮説検定 パラメトリック t検定 ウェルチのt検定 F検定 Z検定 二項検定 ジャック–ベラ検定 シャピロ–ウィルク検定 分散分析 共分散分析 ノンパラメトリック ウィルコクソンの符号順位検定 マン・ホイットニーのU検定 カイ二乗検定 イェイツのカイ二乗検定 累積カイ二乗検定 フィッシャーの正確確率検定 尤度比検定 G検定 アンダーソン–ダーリング検定 コルモゴロフ–スミルノフ検定 カイパー検定 マンテル検定 コクラン・マンテル・ヘンツェルの統計量 その他 帰無仮説 対立仮説 有意 棄却 区間推定 信頼区間 予測区間 モデル選択基準 AIC BIC WAIC MDL その他 偏り 偏りと分散 過剰適合 推定量 点推定 最尤推定 尤度関数 尤度方程式 最小距離推定 メタアナリシス ブートストラップ法
ベイズ統計学	確率 主観確率 ベイズ確率 事前確率 事後確率 最大事後確率 その他 ベイズ推定 ベイズ因子
相関	相関係数 ピアソンの積率相関係数 スピアマンの順位相関係数 ケンドールの順位相関係数 偏相関係数 その他 自己相関 空間的自己相関 相互相関 交絡変数 相関関係と因果関係 擬似相関 錯誤相関
モデル	一般線形モデル 一般化線形モデル 混合モデル 一般化線形混合モデル
回帰	線形 リッジ回帰 ラッソ回帰 エラスティックネット 非線形 k近傍法 回帰木 ランダムフォレスト ニューラルネットワーク サポートベクター回帰 射影追跡回帰 時系列 自己回帰モデル 自己回帰移動平均モデル ARCHモデル 対移動平均比率法 トレンド定常 傾向推定 共和分 構造変化
分類	線形 線形判別分析 ロジスティック回帰 単純ベイズ分類器 単純パーセプトロン 線形サポートベクターマシン 二次 二次判別分析 非線形 k近傍法 決定木 ランダムフォレスト ニューラルネットワーク サポートベクターマシン ベイジアンネットワーク 隠れマルコフモデル その他 二項分類 多クラス分類 第一種過誤と第二種過誤
教師なし学習	クラスタリング k平均法（k-means++法） DBSCAN 密度推定（英語版） カーネル密度推定（カーネル） その他 主成分分析 独立成分分析 自己組織化写像
統計図表	棒グラフ バイプロット（英語版） 箱ひげ図 管理図 フォレストプロット ヒストグラム 円グラフ Q-Qプロット ランチャート 散布図 幹葉図 バイオリン図 ドットプロット ヒートマップ 階級区分図
生存時間分析	生存時間関数 カプラン＝マイヤー推定量 ログランク検定 故障率 比例ハザードモデル
歴史	統計学の創始者 確率論と統計学の歩み
応用	社会統計学 疫学 生物統計学 系統学 統計力学 計量経済学 機械学習 実験計画法
出版物	統計学に関する学術誌一覧 重要な出版物
全般	統計 頻度主義統計学 統計学および機械学習の評価指標
その他	方向統計学 S言語 R言語 統計検定 社会調査士 JDLA Deep Learning For GENERAL JDLA Deep Learning for ENGINEER 実用数学技能検定 品質管理検定
カテゴリ