GBDT

梯度提升樹實(shí)在提升樹的基礎(chǔ)上發(fā)展而來(lái)的一種使用范圍更廣的方法，當(dāng)處理回歸問(wèn)題時(shí)，提升樹可以看作是梯度提升樹的特例(分類問(wèn)題時(shí)是不是特例？)。 因?yàn)樘嵘龢湓跇?gòu)建樹每一步的過(guò)程中都是去擬合上一步獲得模型在訓(xùn)練集上的殘差。后面我們將會(huì)介紹，這個(gè)殘存正好是損失函數(shù)的梯度，對(duì)應(yīng)于GBDT每一步要擬合的對(duì)象。

主要思想

在目標(biāo)函數(shù)所在的函數(shù)空間中做梯度下降，即把待求的函數(shù)模型當(dāng)作參數(shù)，每一步要擬合目標(biāo)函數(shù)關(guān)于上一步獲得的模型的梯度，從而使得參數(shù)朝著最小化目標(biāo)函數(shù)的方向更新。

一些特性

1. 每次迭代獲得的決策樹模型都要乘以一個(gè)縮減系數(shù)，從而降低每棵樹的作用，提升可學(xué)習(xí)空間。
2. 每次迭代擬合的是一階梯度。

XGBoost

XGBoost 是GBDT的一個(gè)變種，最大的區(qū)別是xgboost通過(guò)對(duì)目標(biāo)函數(shù)做二階泰勒展開，從而求出下一步要擬合的樹的葉子節(jié)點(diǎn)權(quán)重（需要先確定樹的結(jié)構(gòu)），從而根據(jù)損失函數(shù)求出每一次分裂節(jié)點(diǎn)的損失減小的大小，從而根據(jù)分裂損失選擇合適的屬性進(jìn)行分裂。

這個(gè)利用二階展開的到的損失函數(shù)公式與分裂節(jié)點(diǎn)的過(guò)程是息息相關(guān)的。先遍歷所有節(jié)點(diǎn)的所有屬性進(jìn)行分裂，假設(shè)選擇了這個(gè)a屬性的一個(gè)取值作為分裂節(jié)點(diǎn)，根據(jù)泰勒展開求得的公式可計(jì)算該樹結(jié)構(gòu)各個(gè)葉子節(jié)點(diǎn)的權(quán)重，從而計(jì)算損失減小的程度，從而綜合各個(gè)屬性選擇使得損失減小最大的那個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂屬性。依次類推，直到滿足終止條件。

一些特性

1. 除了類似于GBDT的縮減系數(shù)外，xgboost對(duì)每棵樹的葉子節(jié)點(diǎn)個(gè)數(shù)和權(quán)重都做了懲罰，避免過(guò)擬合

2. 類似于隨機(jī)森林，XGBoost在構(gòu)建樹的過(guò)程中，對(duì)每棵樹隨機(jī)選擇一些屬性作為分裂屬性。

3. 分裂算法有兩種，一種是精確的分裂，一種是近似分裂算法，精確分裂算法就是把每個(gè)屬性的每個(gè)取值都當(dāng)作一次閾值進(jìn)行遍歷，采用的決策樹是CART。近似分裂算法是對(duì)每個(gè)屬性的所有取值進(jìn)行分桶，按照各個(gè)桶之間的值作為劃分閾值，xgboost提出了一個(gè)特殊的分桶策略，一般的分桶策略是每個(gè)樣本的權(quán)重都是相同 的，但是xgboost使每個(gè)樣本的權(quán)重為損失函數(shù)在該樣本點(diǎn)的二階導(dǎo)(泰勒展開不應(yīng)該是損失函數(shù)關(guān)于模型的展開嗎？為什么會(huì)有在該樣本點(diǎn)的二階導(dǎo)這種說(shuō)法？ 因?yàn)槟Ｐ褪菍?duì)所有樣本點(diǎn)都通用的，把該樣本輸入到二階導(dǎo)公式中就可以得到了)。

4. xgboost添加了對(duì)稀疏數(shù)據(jù)的支持，在計(jì)算分裂收益的時(shí)候只利用沒有missing值的那些樣本，但是在推理的時(shí)候，也就是在確定了樹的結(jié)構(gòu)，需要將樣本映射到葉子節(jié)點(diǎn)的時(shí)候，需要對(duì)含有缺失值的樣本進(jìn)行劃分，xgboost分別假設(shè)該樣本屬于左子樹和右子樹，比較兩者分裂增益，選擇增益較大的那一邊作為該樣本的分裂方向。

5. xgboost在實(shí)現(xiàn)上支持并行化，這里的并行化并不是類似于rf那樣樹與樹之間的并行化，xgboost同boosting方法一樣，在樹的粒度上是串行的，但是在構(gòu)建樹的過(guò)程中，也就是在分裂節(jié)點(diǎn)的時(shí)候支持并行化，比如同時(shí)計(jì)算多個(gè)屬性的多個(gè)取值作為分裂特征及其值，然后選擇收益最大的特征及其取值對(duì)節(jié)點(diǎn)分裂。

6. xgboost 在實(shí)現(xiàn)時(shí)，需要將所有數(shù)據(jù)導(dǎo)入內(nèi)存，做一次pre-sort（exact algorithm），這樣在選擇分裂節(jié)點(diǎn)時(shí)比較迅速。

缺點(diǎn)

1. level-wise 建樹方式對(duì)當(dāng)前層的所有葉子節(jié)點(diǎn)一視同仁，有些葉子節(jié)點(diǎn)分裂收益非常小，對(duì)結(jié)果沒影響，但還是要分裂，加重了計(jì)算代價(jià)。
2. 預(yù)排序方法空間消耗比較大，不僅要保存特征值，也要保存特征的排序索引，同時(shí)時(shí)間消耗也大，在遍歷每個(gè)分裂點(diǎn)時(shí)都要計(jì)算分裂增益(不過(guò)這個(gè)缺點(diǎn)可以被近似算法所克服)

lightGBM

1. xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，區(qū)別是xgboost對(duì)每一層所有節(jié)點(diǎn)做無(wú)差別分裂，可能有些節(jié)點(diǎn)的增益非常小，對(duì)結(jié)果影響不大，但是xgboost也進(jìn)行了分裂，帶來(lái)了務(wù)必要的開銷。 leaft-wise的做法是在當(dāng)前所有葉子節(jié)點(diǎn)中選擇分裂收益最大的節(jié)點(diǎn)進(jìn)行分裂，如此遞歸進(jìn)行，很明顯leaf-wise這種做法容易過(guò)擬合，因?yàn)槿菀紫萑氡容^高的深度中，因此需要對(duì)最大深度做限制，從而避免過(guò)擬合。

2. lightgbm使用了基于histogram的決策樹算法，這一點(diǎn)不同與xgboost中的 exact 算法，histogram算法在內(nèi)存和計(jì)算代價(jià)上都有不小優(yōu)勢(shì)。
   -. 內(nèi)存上優(yōu)勢(shì)：很明顯，直方圖算法的內(nèi)存消耗為(#data* #features * 1Bytes)(因?yàn)閷?duì)特征分桶后只需保存特征離散化之后的值)，而xgboost的exact算法內(nèi)存消耗為：(2 * #data * #features* 4Bytes)，因?yàn)閤gboost既要保存原始feature的值，也要保存這個(gè)值的順序索引，這些值需要32位的浮點(diǎn)數(shù)來(lái)保存。
   -. 計(jì)算上的優(yōu)勢(shì)，預(yù)排序算法在選擇好分裂特征計(jì)算分裂收益時(shí)需要遍歷所有樣本的特征值，時(shí)間為(#data),而直方圖算法只需要遍歷桶就行了，時(shí)間為(#bin)

3. 直方圖做差加速
   -. 一個(gè)子節(jié)點(diǎn)的直方圖可以通過(guò)父節(jié)點(diǎn)的直方圖減去兄弟節(jié)點(diǎn)的直方圖得到，從而加速計(jì)算。

4. lightgbm支持直接輸入categorical 的feature
   -. 在對(duì)離散特征分裂時(shí)，每個(gè)取值都當(dāng)作一個(gè)桶，分裂時(shí)的增益算的是”是否屬于某個(gè)category“的gain。類似于one-hot編碼。

5. 但實(shí)際上xgboost的近似直方圖算法也類似于lightgbm這里的直方圖算法，為什么xgboost的近似算法比lightgbm還是慢很多呢？
   -. xgboost在每一層都動(dòng)態(tài)構(gòu)建直方圖， 因?yàn)閤gboost的直方圖算法不是針對(duì)某個(gè)特定的feature，而是所有feature共享一個(gè)直方圖(每個(gè)樣本的權(quán)重是二階導(dǎo)),所以每一層都要重新構(gòu)建直方圖，而lightgbm中對(duì)每個(gè)特征都有一個(gè)直方圖，所以構(gòu)建一次直方圖就夠了。
   -. lightgbm做了cache優(yōu)化？

6. lightgbm哪些方面做了并行？
   -. feature parallel
   一般的feature parallel就是對(duì)數(shù)據(jù)做垂直分割（partiion data vertically，就是對(duì)屬性分割），然后將分割后的數(shù)據(jù)分散到各個(gè)workder上，各個(gè)workers計(jì)算其擁有的數(shù)據(jù)的best splits point, 之后再匯總得到全局最優(yōu)分割點(diǎn)。但是lightgbm說(shuō)這種方法通訊開銷比較大，lightgbm的做法是每個(gè)worker都擁有所有數(shù)據(jù)，再分割？（沒懂，既然每個(gè)worker都有所有數(shù)據(jù)了，再匯總有什么意義？這個(gè)并行體現(xiàn)在哪里？？）
   -. data parallel
   傳統(tǒng)的data parallel是將對(duì)數(shù)據(jù)集進(jìn)行劃分，也叫 平行分割(partion data horizontally)， 分散到各個(gè)workers上之后，workers對(duì)得到的數(shù)據(jù)做直方圖，匯總各個(gè)workers的直方圖得到全局的直方圖。 lightgbm也claim這個(gè)操作的通訊開銷較大，lightgbm的做法是使用”Reduce Scatter“機(jī)制，不匯總所有直方圖，只匯總不同worker的不同feature的直方圖(原理？)，在這個(gè)匯總的直方圖上做split，最后同步。

參考：https://github.com/Microsoft/LightGBM/wiki/Features