勾配ブースティング
ブースティングは、決定木や線形回帰などの基本学習者の精度を高めることができるが、分かりやすさ intelligibility や解釈のしやすさ interpretability を犠牲にする 。また、計算量が多くなるため、実装が難しくなることもある。
勾配ブースティングは通常、固定サイズの決定木(特に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}} に分けて各地域の定数値を予測する。入力 x に対する出力 h m ( x ) {\displaystyle h_{m}(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}} における予測値を表す。
次に、係数 b j m {\displaystyle b_{jm}} に γ m {\displaystyle \gamma _{m}} (損失関数を最小化するように線型探索で選択する)を乗じ、モデルは次のように更新される。
F m ( x ) = F m − 1 ( x ) + γ m h m ( x ) , γ m = a r g m i n γ ∑ i = 1 n L ( y i , F m − 1 ( x i ) + γ h m ( x i ) ) . {\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})).}
ここで、関数 F i {\displaystyle F_{i}} , i ∈ { 1 , . . , m } {\displaystyle i\in \{1,..,m\}} を微分する。 γ m {\displaystyle \gamma _{m}} がステップ長である。離散的な場合、すなわち集合 H {\displaystyle {\mathcal {H}}} が有限の場合、L の勾配に最も近い h を選択する。この候補関数の係数 γ は、上記の方程式の線型探索を使用して計算できる。このアプローチはヒューリスティックであるため、特定の問題に対する正確な解決策ではなく、近似値が得られることに注意。擬似コードでは、一般的な勾配ブースティング方法は次のとおり。