也來(lái)講講 Gradient Boosting，傳說(shuō)中天池移動(dòng)推薦算法比賽中應(yīng)用最多的算法。
基本思想：把分類問(wèn)題看作回歸問(wèn)題，弱分類器看作一個(gè)決策函數(shù) F(x)；每次迭代過(guò)程，對(duì)上一次分類的殘差進(jìn)行分類訓(xùn)練，即訓(xùn)練 $h(x) = y - F_m(x)$ ，作為前一次分類結(jié)果的補(bǔ)償。對(duì)于平方損失函數(shù) $\frac{1}{2} (\hat{y} - y)^2$ 而言，上述 $h(x)$ 則是其導(dǎo)數(shù)，因此，該方法作為一個(gè)梯度提升方法得名，可以根據(jù)需要推廣到不同的損失函數(shù)。
算法：
- 初始化基礎(chǔ)模型 $F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma)$
- 迭代 $m \in (1, M)$
- 計(jì)算偽梯度 $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$
- 以偽梯度為類標(biāo)，訓(xùn)練基礎(chǔ)模型 $h_m(x)$
- 計(jì)算模型權(quán)重 $\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)$
- 更新模型： $F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)$
- 得到最終模型 $F_m(x)$
其中 2.4 中計(jì)算模型權(quán)重采用的是一維模型，更恰當(dāng)?shù)?，?yīng)該采用區(qū)域模型（決策樹對(duì)特征向量的預(yù)測(cè)實(shí)際上是就是對(duì)特征空間進(jìn)行劃分）：
$$F_m(x) = F_{m-1}(x) + \sum_{j=1}^J \gamma_{jm} I(x \in R_{jm}), \quad
\gamma_{jm} = \underset{\gamma}{\operatorname{arg,min}} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma h_m(x_i))$$
但這樣做無(wú)疑增加了計(jì)算量。
為了簡(jiǎn)化操作，在 Spark MLlib 中的 GradientBoostTree 中，模型參數(shù) $\gamma_m$ 被規(guī)定為 1 ，不要與學(xué)習(xí)率（learning rate）混淆。
參數(shù)調(diào)優(yōu)：
- 學(xué)習(xí)率（Learning Rate） $F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x), \quad 0 < \nu \leq 1$ ，實(shí)踐中越小的學(xué)習(xí)率分類預(yù)測(cè)效果越好
- 隨機(jī)梯度提升（Stochastic Gradient Boosting），受 Bagging 思想啟發(fā)，每次訓(xùn)練時(shí)不直接用全局?jǐn)?shù)據(jù)，而是對(duì)數(shù)據(jù)進(jìn)行抽樣，每次只選擇一部分?jǐn)?shù)據(jù)進(jìn)行訓(xùn)練
- 限制葉子節(jié)點(diǎn)的實(shí)例個(gè)數(shù)，減小預(yù)測(cè)的方差
- 模型復(fù)雜度的懲罰，樹越復(fù)雜越可能過(guò)擬合
具體可以參考 <a >https://en.wikipedia.org/wiki/Gradient_boosting</a>
