背景：

當(dāng)前的熱門算法中，除了神經(jīng)網(wǎng)絡(luò)在圖像和文字、音頻等領(lǐng)域大放異彩之外，集成學(xué)習(xí)中的xgboost,lightGBM,CatBoost也在kaggle等機(jī)器學(xué)習(xí)平臺上成為了炙手可熱的工具。

明確概念：

1、Boosting（提升）

2、Adaptive Boosting（自適應(yīng)增強(qiáng)）

3、Gradient Boosting（梯度提升）

4、Decision Tree（決策樹）

一、Boosting

關(guān)于boosting（提升算法）的概念，上文有簡單介紹過，提升算法（這是一類算法族的稱呼，不是指某種具體算法）是通過改變訓(xùn)練樣本的權(quán)重（如果基分類器不支持則通過調(diào)整采樣的方式改變基分類器的訓(xùn)練樣本分布），學(xué)習(xí)多個分類器，并將這些分類器進(jìn)行線性組合，提高分類的性能。下面要講的集成算法都屬于提升算法

二、Adaboost（Adaptive Boosting自適應(yīng)增強(qiáng)算法）

 針對分類任務(wù)，李航的《統(tǒng)計學(xué)習(xí)方法》中有詳細(xì)介紹

總結(jié)一下流程如下圖所示

經(jīng)過上述學(xué)習(xí)，我們已經(jīng)可以明確adaboost的核心是

1）計算基分類器的誤差

2）計算基分類器的權(quán)重

3）更新樣本的權(quán)重

4）最后的結(jié)合策略

針對回歸任務(wù)，adaboost有以下步驟

三、GBDT（GBDT泛指所有梯度提升樹算法，包括XGBoost，它也是GBDT的一種變種，為了區(qū)分它們，GBDT一般特指“Greedy Function Approximation：A Gradient Boosting Machine”里提出的算法，只用了一階導(dǎo)數(shù)信息。）

參考自：https://zhuanlan.zhihu.com/p/46445201

GBDT是以CART樹（回歸樹）作為基分類器的boosting算法。與Adaboost通過每次調(diào)整樣本的權(quán)值來訓(xùn)練不同的基分類器不同，GBDT是通過將殘差作為擬合目標(biāo)訓(xùn)練心得基分類器。

先看一下GBDT應(yīng)用于回歸任務(wù)的原理

其實，我一直對GBDT中的“梯度提升”很不理解，因為最優(yōu)化理論中，梯度下降優(yōu)化算法已經(jīng)很熟悉了，拿兩者進(jìn)行比較，我總是覺得GBDT依然是“梯度下降”而非“梯度提升”，如下圖是某個博客上的對比

 ，這分明都是使用的“梯度下降”。

在參考了很多資料之后，我終于明白了GBDT為什么使用“梯度提升”的叫法了。這里的“梯度提升”并不是和“梯度下降”對立的概念，相反，應(yīng)該把它拆解開來

 “梯度提升”=“梯度” “提升”

“梯度”是指GBDT算法中使用梯度近似擬合殘差的做法

“提升”是指boosting方法中將弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的做法

再附一個GBDT實際應(yīng)用于回歸任務(wù)的例子

GBDT應(yīng)用于分類任務(wù)

 針對二分類任務(wù)，

 以上，最重要的一點就是，針對分類任務(wù)每個基分類器擬合的是真實標(biāo)簽與和對應(yīng)類別預(yù)測概率的殘差。

四、XGBoost（eXtreme Gradient Boosting）

從名字就可以看出，xgboost是GBDT的增強(qiáng)版本。

如果把xgboost對gbdt的所有改進(jìn)細(xì)節(jié)列出來，那牽扯的point有點多，所以選擇幾個點進(jìn)行闡述。

為了用最容易理解的思路，我們就假設(shè)不知道xgboost算法，先去思考GBDT的過程中有哪些點可以改進(jìn)：

1、基學(xué)習(xí)器的選擇。

GBDT使用CART（回歸樹）作為基學(xué)習(xí)器，我們還可以考慮支持其他的基學(xué)習(xí)器，所以xgboost也支持線性學(xué)習(xí)器

2、損失函數(shù)的選擇。

GBDT大多數(shù)情況下采用平方誤差和作為損失函數(shù)，我們還可以考慮更優(yōu)秀的損失函數(shù)，所以xgboost實現(xiàn)了自己的損失函數(shù)。

3、特征分裂點及特征選擇。

GBDT采用CART樹的特征分裂點及特征選擇方式，具體為串行遍歷所有的特征分裂點和特征，選擇平方誤差和最小的特征及特征分裂點；

這個過程中，我們注意到各特征及分割點的損失函數(shù)的計算可以并行執(zhí)行，而且如果對樣本按照特征排序的結(jié)果在全局可以復(fù)用，可大大提高計算效率，而xgboost也是這樣做的。

另外，GBDT的每棵樹的特征選擇策略都是相同的，方差較小，多樣性不足，我們可以借鑒隨機(jī)森林中列抽樣（隨機(jī)變量選擇）的思想，xgboost也實現(xiàn)了這一點。

4、不同的樹對于殘差的擬合策略

GBDT采用殘差的一階導(dǎo)數(shù)代替殘差進(jìn)行擬合（這里需要說明，許多資料說用一階導(dǎo)代替殘差的原因是殘差難以獲得，這好扯淡啊，擬合一階導(dǎo)的優(yōu)點明明是為了更快地進(jìn)行擬合，而且當(dāng)損失函數(shù)為平方誤差和時，一階導(dǎo)就等于殘差），發(fā)散一下我們就想到了梯度下降和牛頓法，那我們能不能使用二階導(dǎo)來擬合殘差呢，答案是肯定的，且xgboost也是這樣做的，而且通過二階導(dǎo)擬合策略計算出了xgboost的損失函數(shù)（見步驟2）。損失函數(shù)不僅考慮到了經(jīng)驗風(fēng)險，也考慮到了結(jié)構(gòu)風(fēng)險，通過結(jié)構(gòu)風(fēng)險正則化，使得xgboost泛化性能更佳，更不容易過擬合。

五、LightGBM

該算法在精度，運行效率和內(nèi)存消耗等方面在絕大多數(shù)數(shù)據(jù)集上的表現(xiàn)都優(yōu)于xgboost。

我們沿用上面的思路，繼續(xù)思考在xgboost的優(yōu)化基礎(chǔ)上，怎樣進(jìn)一步優(yōu)化GB類的算法。

1、boosting過程中，最耗時的就是特征選擇及連續(xù)特征分裂點選取的問題，xgboost已經(jīng)通過pre-sorted預(yù)排序的方法進(jìn)行了優(yōu)化，但是如果樣本對應(yīng)的特征枚舉值過多，還是會導(dǎo)致耗時過長的問題。所以我們可以考慮HistoGram（直方圖）算法，通過預(yù)先對樣本的特征進(jìn)行分桶（bin）的方式，在選擇分裂點的時候遍歷各個桶，就可以有效地提高運行效率，雖然會稍微損失一點精度，但是可以通過其它的優(yōu)化進(jìn)行彌補。

2、結(jié)點的分裂策略。GBDT和xgboost在樹的分裂過程中，都采用level-wise（類似層序遍歷）的分裂方式，這種方式平等地對待了分裂貢獻(xiàn)可能相差很大的同一層的不同子結(jié)點。lightGBM采用leaf-wise（類似深度優(yōu)先遍歷）分裂策略，每一步都選擇最深的貢獻(xiàn)最大的子結(jié)點進(jìn)行分裂。

3、采樣方法。無論是GBDT還是xgboost，我們都是在不停地訓(xùn)練基學(xué)習(xí)器去擬合殘差，當(dāng)殘差小于某個閾值時停止訓(xùn)練，可能存在這樣一種情況，對于大多數(shù)樣本來講，其梯度已經(jīng)較小，而小部分樣本的梯度仍較大，所以我們想到可以在每次訓(xùn)練新的基學(xué)習(xí)器時，保留梯度較大的樣本，減少梯度較小的樣本數(shù)量（隨機(jī)采樣），這便是GOSS方法(Gradient-based One-Side Sampling)。

ok,,,寫得自己很不滿意，先出第一版，后面迭代優(yōu)化吧。。。還想補一下catboost。。。