背景：

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

明確概念：

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í)多個(gè)分類器,，并將這些分類器進(jìn)行線性組合，提高分類的性能,。下面要講的集成算法都屬于提升算法

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

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

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

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

1）計(jì)算基分類器的誤差

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

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

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

針對(duì)回歸任務(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ù)的原理

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

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

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

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

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

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

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

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

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

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

四、XGBoost（eXtreme Gradient Boosting）

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

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

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

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

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

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

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

3,、特征分裂點(diǎn)及特征選擇,。

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

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

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

4,、不同的樹對(duì)于殘差的擬合策略

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

五、LightGBM

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

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

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

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

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

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