勾配ブースティングは 、関数空間でのブースティング に基づく機械学習 手法であり、従来のブースティングのように残差 ではなく擬似残差をターゲットとします。これは、弱い予測モデルの アンサンブル の形で予測モデルを提供します。弱い予測モデルとは、データについてほとんど仮定を置かないモデルであり、通常は単純な決定木 です。[ 1 ] [ 2 ] ランダム フォレストよりも優れた性能を発揮します。[ 1 ] 他のブースティング 手法と同様に、勾配ブースティング木モデルは段階的に構築されますが、任意の微分可能な 損失関数 の最適化を可能にすることで、他の手法を一般化しています。
歴史 勾配ブースティングのアイデアは、ブースティングを適切なコスト関数上の最適化アルゴリズムとして解釈できるというレオ・ブレイマンの観察から生まれた。 [ 3 ] その後、ジェローム・H・フリードマン [ 4 ] [ 2 ] [ 5 ] [ 6 ] 後者の2つの論文は、ブースティングアルゴリズムを反復関数勾配降下 アルゴリズム として捉える見方を導入した。つまり、負の勾配方向を指す関数（弱い仮説）を反復的に選択することによって、関数空間上でコスト関数を最適化するアルゴリズムである。この関数勾配ブースティングの見方は、回帰や分類にとどまらず、機械学習や統計学の多くの分野でブースティングアルゴリズムの開発につながった。
アルゴリズム 多くの教師あり学習 問題では、出力変数y と入力変数のベクトルx が、何らかの確率分布で互いに関連しています。目標は、ある関数を見つけることです。F ^ （ x ） \displaystyle {\hat {F}}(x)} 損失関数を導入することによって形式化されます。 L （ y 、 F （ x ） ） {\displaystyle L(y,F(x))}
F ^ = アルグミン F E x 、 y [ L （ y 、 F （ x ） ） ] 。 {\displaystyle {\hat {F}}=\operatorname {argmin} \limits _{F}\mathbb {E} _{x,y}[L(y,F(x))].} 勾配ブースティング法は、y が実数値であることを前提としています。近似値を求めます。F ^ （ x ） \displaystyle {\hat {F}}(x)} M 個の関数の加重和の形でh m （ x ） {\displaystyle h_{m}(x)} H \displaystyle {\mathcal {H}}} 弱 学習器）と呼ばれるもの：
F ^ （ x ） = ∑ m = 1 M γ m h m （ x ） + const 、 {\displaystyle {\hat {F}}(x)=\sum _{m=1}^{M}\gamma _{m}h_{m}(x)+{\mbox{const}},} どこγ m \displaystyle \gamma _{m}} m {\displaystyle m} { （ x 1 、 y 1 ） 、 … 、 （ x n 、 y n ） } {\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}} xの値とそれに対応する y の値。経験的リスク最小化 原理に従って、この方法は近似値を見つけようとします。F ^ （ x ） \displaystyle {\hat {F}}(x)} F 0 （ x ） {\displaystyle F_{0}(x)} 貪欲な 方法で段階的に拡張します。
F 0 （ x ） = 引数 ミニ h 0 ∈ H ∑ 私 = 1 n L （ y 私 、 h 0 （ x 私 ） ） 、 {\displaystyle F_{0}(x)={\underset {h_{0}\in {\mathcal {H}}}{\arg \min }}\sum _{i=1}^{n}{L(y_{i},h_{0}(x_{i}))},} F m （ x ） = F m − 1 （ x ） + （ 1 r g m 私 n h m ∈ H [ ∑ 私 = 1 n L （ y 私 、 F m − 1 （ x 私 ） + h m （ x 私 ） ） ] ） （ x ） 、 {\displaystyle F_{m}(x)=F_{m-1}(x)+\left({\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]\right)(x),} のためにm ≥ 1 {\displaystyle m\geq 1} h m ∈ H {\displaystyle h_{m}\in {\mathcal {H}}}
残念ながら、最適な機能を選択するh m {\displaystyle h_{m}} Lに対して各ステップで を実行することは、一般に計算上実行不可能な最適化問題です。したがって、我々のアプローチは問題の簡略化されたバージョンに限定します。この最小化問題に 最急降下 法（関数勾配降下法）を適用するというアイデアです。基本的なアイデアは、 を反復して損失関数の局所最小値を見つけることです。F m − 1 （ x ） {\displaystyle F_{m-1}(x)} [ 8 ] γ {\displaystyle \gamma }
F m （ x ） = F m − 1 （ x ） − γ ∑ 私 = 1 n ∇ F m − 1 L （ y 私 、 F m − 1 （ 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}))} どこγ > 0 {\displaystyle \gamma >0} γ {\displaystyle \gamma } L （ y 私 、 F m （ x 私 ） ） ≤ L （ y 私 、 F m − 1 （ x 私 ） ） {\displaystyle L(y_{i},F_{m}(x_{i}))\leq L(y_{i},F_{m-1}(x_{i}))}
さらに、最適化することができますγ {\displaystyle \gamma } γ {\displaystyle \gamma }
γ m = アルグミン γ ∑ 私 = 1 n L （ y 私 、 F m （ x 私 ） ） = 引数 ミニ γ ∑ 私 = 1 n L （ y 私 、 F m − 1 （ x 私 ） − γ ∇ F m − 1 L （ y 私 、 F m − 1 （ x 私 ） ） ） 。 {\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {argmin} }}\sum _{i=1}^{n}L(y_{i},F_{m}(x_{i}))={\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)}.} 連続的な場合、つまり、H {\displaystyle {\mathcal {H}}} R {\displaystyle \mathbb {R} }
F m （ x ） = F m − 1 （ x ） − γ m ∑ 私 = 1 n ∇ F m − 1 L （ y 私 、 F m − 1 （ x 私 ） ） {\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}} どこγ m {\displaystyle \gamma _{m}} γ m = 引数 ミニ γ ∑ 私 = 1 n L （ y 私 、 F m − 1 （ x 私 ） − γ ∇ F m − 1 L （ y 私 、 F m − 1 （ x 私 ） ） ） 。 {\displaystyle \gamma _{m}={\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).} H {\displaystyle {\mathcal {H}}} L の勾配に最も近いh を 選択し、その係数γ を上記の方程式に対する線探索 によって計算します。このアプローチはヒューリスティックであるため、与えられた問題の正確な解ではなく、近似解が得られることに注意してください。擬似コードでは、一般的な勾配ブースティング法は次のようになります。[ 4 ] [ 1 ]
入力: トレーニングセット{ （ x 私 、 y 私 ） } 私 = 1 n 、 {\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n},} L （ y 、 F （ x ） ） 、 {\displaystyle L(y,F(x)),} M 。
アルゴリズム：
モデルを定数値で初期化します。 F 0 （ x ） = 引数 ミニ γ ∑ 私 = 1 n L （ y 私 、 γ ） 。 {\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).} m = 1 からM まで: いわゆる擬似残差 を計算する： r 私 m = − [ ∂ L （ y 私 、 F （ x 私 ） ） ∂ F （ x 私 ） ] F （ x ） = F m − 1 （ x ） のために 私 = 1 、 … 、 n 。 {\displaystyle r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\text{for }}i=1,\ldots ,n.} スケーリングに対して閉じたベース学習器（または弱学習器、例えばツリー）を適合させるh m （ x ） {\displaystyle h_{m}(x)} { （ x 私 、 r 私 m ） } 私 = 1 n {\displaystyle \{(x_{i},r_{im})\}_{i=1}^{n}} 乗数を計算するγ m {\displaystyle \gamma _{m}} γ m = アルグミン γ ∑ 私 = 1 n L （ y 私 、 F m − 1 （ x 私 ） + γ h m （ x 私 ） ） 。 {\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {argmin} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).} モデルを更新する： F m （ x ） = F m − 1 （ x ） + γ m h m （ x ） 。 {\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).} 出力F M （ x ） 。 {\displaystyle F_{M}(x).}
勾配木ブースティング 勾配ブースティングは通常、基本学習器として固定サイズの決定木 （特にCART ）とともに使用されます。この特殊なケースにおいて、フリードマンは各基本学習器の適合度を向上させる勾配ブースティング手法の改良を提案しています。
m 番目のステップでの一般的な勾配ブースティングは決定木に適合するだろうh m （ x ） {\displaystyle h_{m}(x)} J m {\displaystyle J_{m}} J m {\displaystyle J_{m}} R 1 m 、 … 、 R J m m {\displaystyle R_{1m},\ldots ,R_{J_{m}m}} 指示記号 表記を使用すると、h m （ x ） {\displaystyle h_{m}(x)} x は、次の和として表すことができます。
h m （ x ） = ∑ j = 1 J m b j m 1 R j m （ x ） 、 {\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),} どこb j m {\displaystyle b_{jm}} R j m {\displaystyle R_{jm}} 9 ]
次に係数b j m {\displaystyle b_{jm}} γ m {\displaystyle \gamma _{m}}
F m （ x ） = F m − 1 （ x ） + γ m h m （ x ） 、 γ m = 1 r g m 私 n γ ∑ 私 = 1 n L （ y 私 、 F m − 1 （ x 私 ） + γ h m （ x 私 ） ） 。 {\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})).} フリードマンはこのアルゴリズムを修正し、別の最適値を選択するようにすることを提案している。γ j m {\displaystyle \gamma _{jm}} γ m {\displaystyle \gamma _{m}} b j m {\displaystyle b_{jm}}
F m （ x ） = F m − 1 （ x ） + ∑ j = 1 J m γ j m 1 R j m （ x ） 、 γ j m = 1 r g m 私 n γ ∑ x 私 ∈ R j m L （ y 私 、 F m − 1 （ x 私 ） + γ ） 。 {\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 ).} 損失が発生した場合L （ ⋅ 、 ⋅ ） {\displaystyle L(\cdot ,\cdot )} γ j m {\displaystyle \gamma _{jm}} b j m {\displaystyle b_{jm}}
正則化 訓練データセットに過度に適合させると、モデルの汎化能力、つまり未知のデータに対する性能が低下する可能性があります。いわゆる正則化 手法のいくつかは、適合手順に制約を設けることで、この過学習の 影響を軽減します。
自然な正則化パラメータの一つとして、勾配ブースティングの反復回数M （すなわち、ベースモデルの数）が挙げられます。Mを増やすと訓練データセットにおける誤差は減少しますが、過学習のリスクが高まります 。M の最適な値は、多くの場合、別の検証データセットにおける予測誤差を監視することによって決定されます。
ツリーブースティングにおけるもう一つの正則化パラメータは、ツリーの深さです。この値が大きいほど、モデルが訓練データに過学習する可能性が高くなります。
収縮 勾配ブースティングの重要な要素の一つは、修正された更新ルールを用いる収縮による正則化である。
F m （ x ） = F m − 1 （ x ） + ν ⋅ γ m h m （ x ） 、 0 < ν ≤ 1 、 {\displaystyle F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,} パラメータ ν {\displaystyle \nu }
経験的に、小さな学習率 （例えば、ν < 0.1 {\displaystyle \nu <0.1} ν = 1 {\displaystyle \nu =1} [ 1 ] クエリ中の両方で 計算時間が 増加するという代償が伴います。つまり、学習率が低いほど、より多くの反復が必要になります。
確率的勾配ブースティング 勾配ブースティングが導入されて間もなく、フリードマンはブレイマン のブートストラップ集約 （「バギング」）法に触発され、アルゴリズムに若干の修正を提案した。[ 2 ] [ 10 ]
サブサンプルサイズは一定の割合ですf {\displaystyle f} f = 1 {\displaystyle f=1} f {\displaystyle f} 過学習を 防ぐのに役立ち、一種の正則化 として機能します。また、回帰木を各反復でより小さなデータセットに適合させる必要があるため、アルゴリズムは高速化されます。フリードマン[ 2 ] 0.5 ≤ f ≤ 0.8 {\displaystyle 0.5\leq f\leq 0.8} f {\displaystyle f} [ 11 ]
また、バギングと同様に、サブサンプリングでは、次のベース学習器の構築に使用されなかった観測値に対する予測を評価することにより、予測性能の向上に関するアウトオブバッグ誤差 を定義することができます。アウトオブバッグ推定は、独立した検証データセットの必要性を回避するのに役立ちますが、実際の性能向上と最適な反復回数を過小評価することがよくあります。[ 12 ] [ 13 ]
葉における観測数 勾配ツリーブースティングの実装では、ツリーの終端ノードにおける観測値の最小数を制限することで正則化を行うことがよくあります。これは、ツリー構築プロセスにおいて、この最小数よりも少ない訓練セットインスタンスを含むノードにつながる分割を無視することで実現されます。
この制限を設けることで、葉における予測値のばらつきを減らすことができる。
複雑性ペナルティ 勾配ブースティングモデルに対するもう1つの有用な正則化手法は、その複雑さにペナルティを課すことです。[ 14 ]
他の種類の正則化としては、ℓ 2 {\displaystyle \ell _{2}} 過学習を 回避するためにも使用できます。[ 15 ]
使用法 勾配ブースティングは、ランキング学習 の分野で使用できます。商用ウェブ検索エンジンのYahoo [ 16 ] Yandex [ 17 ] は 。 [ 18 ]勾配 [ 19 ]
名前 この手法はさまざまな名前で呼ばれています。フリードマンは回帰手法を「勾配ブースティングマシン」（GBM）として紹介しました。[ 4 ] [ 5 ] [ 6 ] [ 20 ] [ 21 ]
R の人気のあるオープンソース実装では「Generalized Boosting Model」と呼ばれていますが[ 12 ] [ 22 ] [ 23 ] 。
機能重要度ランキング 勾配ブースティングは特徴の重要度ランキングに使用できます。これは通常、基本学習器の重要度関数を集約することに基づいています。[ 24 ] 決定木 を使用して勾配ブースティングツリーアルゴリズムが開発されている場合、アンサンブルアルゴリズムは、すべての基本学習器で平均化されるという注意点付きで、エントロピーに基づいて特徴の重要度をランク付けします。[ 24 ] [ 1 ]
デメリット ブースティングは、決定木や線形回帰などの基本学習器の精度を向上させることができますが、理解しやすさと解釈しやすさを 犠牲にします。[ 24 ] [ 25 ] [ 26 ]
参考文献 1 2 3 4 5 6 Hastie, T.; Tibshirani, R.; Friedman, JH (2009). "10. ブースティングと加算ツリー" .統計的学習の要素 (第 2 版). ニューヨーク: Springer. pp. 337–384 . ISBN 978-0-387-84857-0 2009年11月10日にオリジナルからアーカイブされました。 1 2 3 4 Friedman, JH (1999 年 3 月)。 「確率的勾配ブースティング」 (PDF) 。2014 年 8 月 1 日に オリジナル (PDF)からアーカイブ済み。2013 年 11 月 13 日 に取得 。 ↑ Breiman, L. (1997年6月). 「Arcing The Edge」 (PDF) . 技術報告書486 . カリフォルニア大学バークレー校統計学部。 1 2 3 Friedman, JH (1999 年 2 月)。 「貪欲関数近似: 勾配ブースティングマシン」 (PDF) 。2019年 11 月 1 日に オリジナル (PDF) からアーカイブ済み。2018 年 8 月 27 日 に取得 。 1 2 Mason, L.; Baxter, J.; Bartlett, PL; Frean, Marcus (1999). "Boosting Algorithms as Gradient Descent" (PDF) . In SA Solla and TK Leen and K. Müller (ed.). Advances in Neural Information Processing Systems 12 . MIT Press. pp. 512–518 . 1 2 Mason, L.; Baxter, J.; Bartlett, PL; Frean, Marcus (1999 年 5 月)。 「関数空間における勾配降下法としてのブースティングアルゴリズム」 (PDF) 。2018 年 12 月 22 日に オリジナル (PDF) からアーカイブされました 。 ↑ Cheng Li. 「勾配ブースティング入門」 （PDF ） ↑ ランバース、ジム (2011–2012)。 「最も急な降下法」 (PDF) 。 ↑ 注：通常のCARTツリーの場合、ツリーは最小二乗損失を使用して適合されるため、係数はb j m {\displaystyle b_{jm}} R j m {\displaystyle R_{jm}} R j m {\displaystyle R_{jm}} ↑ これは、トレーニングセットと同じサイズのサンプルを使用するため、復元抽出を行うバギングとは異なることに注意してください。 ↑ Arrabi, Nooshin; Torabi, Mohhamadreza; Fassihi, Afshin; Ghasemi, Fahimeh. "ツリーベース学習モデリングと分子ドッキングシミュレーションによる潜在的な血管内皮増殖因子受容体阻害剤の同定". Chemometrics . 1 (1): 1. doi : 10.1002/cem.3545 . 1 2 Ridgeway, Greg (2007). Generalized Boosted Models: A guide to the gbm package. ↑ より良い予測のための勾配ブースティングアルゴリズムを学ぶ（R言語のコード付き） ↑ 陳天奇著『ブーステッドツリー入門』 ↑ Arrabi, Nooshin; Torabi, Mohhamadreza; Fassihi, Afshin; Ghasemi, Fahimeh. "ツリーベース学習モデリングと分子ドッキングシミュレーションによる潜在的な血管内皮増殖因子受容体阻害剤の同定". Chemometrics . 1 (1): 1. doi : 10.1002/cem.3545 . ↑ Cossock, David および Zhang, Tong (2008). Statistical Analysis of Bayes Optimal Subset Ranking ( Wayback Machine に 2010-08-07 に アーカイブ)、14 ページ。 ↑ Yandexの企業ブログ記事、新しいランキングモデル「Snezhinsk」について（ 2012年3月1日にWayback Machine に アーカイブ済み、ロシア語） ↑ Lalchand, Vidhi (2020). "ブーストされた決定木からより多くの情報を抽出する：高エネルギー物理学のケーススタディ". arXiv : 2001.06033 [ stat.ML ]. ↑ マー、ロンフェイ。シャオ、ハンミン。タオ、ジンウェイ。鄭、泰儀。張海琴（2022年1月1日）。 「勾配ブースティング決定木アルゴリズムを使用した、タイトな砂岩貯留層における貯留層品質評価のためのインテリジェントなアプローチ」 。 地球科学を開きます 。 14 (1): 629–645 。 Bibcode : 2022OGeo...14..354M 。 土井 ： 10.1515/geo-2022-0354 。 ISSN 2391-5447 。 ↑ Friedman, Jerome (2003). "多重加法回帰木とその疫学への応用". Statistics in Medicine . 22 (9): 1365– 1381. doi : 10.1002/sim.1501 . PMID 12704603 . S2CID 41965832 . ↑ Elith, Jane (2008). "ブースト回帰ツリーの実践ガイド" . Journal of Animal Ecology . 77 (4): 802– 813. Bibcode : 2008JAnEc..77..802E . doi : 10.1111/j.1365-2656.2008.01390.x . PMID 18397250 . ↑ Elith, Jane. "Boosted Regression Trees for ecological modeling" (PDF) . CRAN . 2020年7月25日に オリジナル (PDF)からアーカイブ済み。 2018年 8月31日 に取得 。 ↑ 「独占インタビュー：サルフォード・システムズ社長、データマイニングのパイオニア、ダン・スタインバーグ氏 」 。KDnuggets 。 1 2 3 Piryonesi, S. Madeh; El-Diraby, Tamer E. (2020-03-01). "資産管理におけるデータ分析: 舗装状態指数の費用対効果の高い予測" . Journal of Infrastructure Systems . 26 (1): 04019036. doi : 10.1061/(ASCE)IS.1943-555X.0000512 . ISSN 1943-555X . S2CID 213782055 . ↑ Wu, Xindong; Kumar, Vipin; Ross Quinlan, J.; Ghosh, Joydeep; Yang, Qiang; Motoda, Hiroshi; McLachlan, Geoffrey J.; Ng, Angus; Liu, Bing; Yu, Philip S.; Zhou, Zhi-Hua (2008-01-01). "データマイニングにおけるトップ10アルゴリズム". Knowledge and Information Systems . 14 (1): 1– 37. doi : 10.1007/s10115-007-0114-2 . hdl : 10983/15329 . ISSN 0219-3116 . S2CID 2367747 . ↑ Sagi, Omer; Rokach, Lior (2021). "解釈可能な決定木による XGBoost の近似". Information Sciences . 572 (2021): 522– 542. doi : 10.1016/j.ins.2021.05.055 .
さらに読む ベームケ、ブラッドリー； グリーンウェル、ブランドン（2019）。「勾配ブースティング」。『Rによる実践的機械学習』 。チャップマン＆ホール。pp. 221–245。ISBN 978-1-138-49568-5 。
外部リンク 勾配ブースティングを説明する方法 勾配ブースティング回帰木 ライトGBM 
![{\displaystyle {\hat {F}}=\operatorname {argmin} \limits _{F}\mathbb {E} _{x,y}[L(y,F(x))].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6d8872fd2462911debde63e8fbcc8ef479cf5ee)
![{\displaystyle F_{m}(x)=F_{m-1}(x)+\left({\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]\right)(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e54705fcbfa3bf430dcc7ba3255ab6816f6ba427)
![{\displaystyle r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\text{for }}i=1,\ldots ,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c29b5400e5f14eb8703722f691f872ac5e12c93)
