本文按這些方法出現(xiàn)的順序?qū)ζ溥M(jìn)行描述。

GBDT

梯度boosting樹(shù)是在boosting樹(shù)的基礎(chǔ)上發(fā)展起來(lái)的一種具有更廣泛應(yīng)用的方法。在處理回歸問(wèn)題時(shí)，Boosting Tree可以看作是梯度Boosting Tree的特例（是分類(lèi)問(wèn)題時(shí)的特例嗎？）。因?yàn)榻?shù)的每一步中的boosted tree都是為了在上一步得到的訓(xùn)練集上擬合模型的殘差。后面我們會(huì)介紹，這個(gè)殘差正是損失函數(shù)的梯度，對(duì)應(yīng)GBDT每一步要擬合的對(duì)象。

大意

梯度下降是在目標(biāo)函數(shù)所在的函數(shù)空間中進(jìn)行的，即以要得到的函數(shù)模型為參數(shù)。在每一步中，都會(huì)擬合目標(biāo)函數(shù)相對(duì)于上一步獲得的模型的梯度，從而使參數(shù)向最小化目標(biāo)函數(shù)的方向移動(dòng)。更新。

對(duì)于某些特征，每次迭代得到的決策樹(shù)模型必須乘以一個(gè)縮減系數(shù)，從而減少每棵樹(shù)的作用，增加可學(xué)習(xí)的空間。每次迭代都適合一階梯度。 XGBoost

XGBoost 是 GBDT 的變體。最大的區(qū)別在于xgboost對(duì)目標(biāo)函數(shù)進(jìn)行二階泰勒展開(kāi)，求出下一步要擬合的樹(shù)的葉子節(jié)點(diǎn)權(quán)重（需要先確定樹(shù)的結(jié)構(gòu)），然后計(jì)算基于損失函數(shù)的樹(shù)權(quán)重。找到每個(gè)分裂節(jié)點(diǎn)的損失減少的大小，以便可以根據(jù)分裂損失選擇合適的屬性進(jìn)行分裂。

這種使用二階展開(kāi)的損失函數(shù)公式與節(jié)點(diǎn)分裂的過(guò)程密切相關(guān)。首先遍歷所有節(jié)點(diǎn)的所有屬性進(jìn)行分裂。假設(shè)選擇a屬性的一個(gè)值作為分裂節(jié)點(diǎn)。根據(jù)泰勒展開(kāi)得到的公式，可以計(jì)算出樹(shù)結(jié)構(gòu)每個(gè)葉子節(jié)點(diǎn)的權(quán)重，從而計(jì)算損失減少的程度。因此，通過(guò)綜合各種屬性，選擇減少損失最多的特征作為當(dāng)前節(jié)點(diǎn)的分裂屬性。依此類(lèi)推，直至滿(mǎn)足終止條件。

除了類(lèi)似于GBDT的縮減系數(shù)之外，xgboost的一些特征還對(duì)每棵樹(shù)的葉子節(jié)點(diǎn)的數(shù)量和權(quán)重進(jìn)行懲罰，以避免過(guò)擬合。與隨機(jī)森林類(lèi)似，XGBoost 在構(gòu)建樹(shù)的過(guò)程中隨機(jī)對(duì)待每棵樹(shù)。選擇一些屬性作為分割屬性。

分裂算法有兩種pg娛樂(lè)電子游戲，一種是精確分裂，一種是近似分裂算法。精確分裂算法將每個(gè)屬性的每個(gè)值作為遍歷的閾值，使用的決策樹(shù)是CART。近似分裂算法將每個(gè)屬性的所有值劃分為多個(gè)桶，并以每個(gè)桶之間的值作為劃分閾值。 xgboost提出了一種特殊的分桶策略。一般的分桶策略是每個(gè)樣本的權(quán)重相同，但是xgboost讓每個(gè)樣本的權(quán)重為損失函數(shù)在該樣本點(diǎn)的二階導(dǎo)數(shù)（泰勒展開(kāi)式不應(yīng)該是損失函數(shù)的展開(kāi)式嗎關(guān)于模型（為什么有樣本點(diǎn)二階導(dǎo)數(shù)這樣的說(shuō)法？因?yàn)槟Ｐ蛯?duì)所有樣本點(diǎn)都是通用的，可以通過(guò)將樣本代入二階導(dǎo)數(shù)公式得到）。

xgboost 添加了對(duì)稀疏數(shù)據(jù)的支持。計(jì)算分割收入時(shí)，僅使用那些沒(méi)有缺失值的樣本。但是，在推理過(guò)程中pg賞金大對(duì)決試玩版，即樹(shù)的結(jié)構(gòu)確定后，需要將樣本映射到葉子節(jié)點(diǎn)時(shí)，需要對(duì)包含缺失值的樣本進(jìn)行劃分，xgboost假設(shè)該樣本屬于左子樹(shù)，并且分別右子樹(shù)，比較兩者的分裂增益，選擇增益較大的一側(cè)作為樣本的分裂方向。

xgboost 支持實(shí)現(xiàn)中的并行化。這里的并行并不是像rf這樣的樹(shù)之間的并行。和boosting方法一樣，xgboost在樹(shù)的粒度上是串行的，但是在構(gòu)建樹(shù)的過(guò)程中，即分裂節(jié)點(diǎn)時(shí)支持并行化，比如計(jì)算多個(gè)屬性的多個(gè)值作為分裂特征及其值??同時(shí)，再選擇收益最大的特征及其值來(lái)分裂節(jié)點(diǎn)。

xgboost在實(shí)現(xiàn)的時(shí)候，需要將所有的數(shù)據(jù)導(dǎo)入到內(nèi)存中pg棋牌，并做一次預(yù)排序（精確算法），這樣在選擇分裂節(jié)點(diǎn)的時(shí)候可以更快。

缺點(diǎn)：逐層樹(shù)構(gòu)造方法對(duì)當(dāng)前層的所有葉節(jié)點(diǎn)一視同仁。分裂一些葉子節(jié)點(diǎn)的好處很小，對(duì)結(jié)果沒(méi)有影響，但仍然需要分裂，增加了計(jì)算成本。預(yù)排序方法消耗大量空間。它不僅需要保存特征值，還需要保存特征的排序索引。同時(shí)，也消耗了大量的時(shí)間。遍歷每個(gè)分割點(diǎn)時(shí)必須計(jì)算分割增益（不過(guò)這個(gè)缺點(diǎn)可以通過(guò)近似算法克服。） lightGBM

關(guān)于lightGBM的論文還沒(méi)有發(fā)布。從網(wǎng)上的一些資料，我們可以得出與xgboost的以下區(qū)別：

xgboost 使用 level-wise 分割策略，而 lightGBM 使用 leaf-wise 策略。不同之處在于xgboost不加區(qū)別地分割每一層中的所有節(jié)點(diǎn)。有些節(jié)點(diǎn)的增益可能很小，對(duì)結(jié)果影響不大，但xgboost也被拆分了，帶來(lái)了必要的開(kāi)銷(xiāo)。 leaf-wise的方法是在當(dāng)前所有葉子節(jié)點(diǎn)中選擇分裂收益最大的節(jié)點(diǎn)進(jìn)行分裂，并遞歸地進(jìn)行。很明顯，leaf-wise的這種方法很容易過(guò)擬合，因?yàn)楹苋菀紫萑氲奖容^高的深度，所以需要限制最大深度，以避免過(guò)擬合。

lightgbm使用基于直方圖的決策樹(shù)算法，與xgboost中的精確算法不同。直方圖算法在內(nèi)存和計(jì)算成本方面具有相當(dāng)大的優(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需要同時(shí)保存原始特征值和該值的順序索引。這些值需要32位浮點(diǎn)數(shù)來(lái)保存。

-.計(jì)算優(yōu)勢(shì)。預(yù)排序算法在選擇分割特征時(shí)需要遍歷所有樣本的特征值來(lái)計(jì)算分割收益，時(shí)間為(#data)，而直方圖算法只需要遍歷桶，時(shí)間為( ＃垃圾桶 ）

直方圖差異加速度

-.父節(jié)點(diǎn)的直方圖減去兄弟節(jié)點(diǎn)的直方圖就可以得到子節(jié)點(diǎn)的直方圖，從而加快計(jì)算速度。

lightgbm支持直接輸入分類(lèi)特征

-.在分割離散特征時(shí)，將每個(gè)值視為一個(gè)桶，分割時(shí)的增益計(jì)算為“是否屬于某個(gè)類(lèi)別”的增益。類(lèi)似于one-hot編碼。

但實(shí)際上，xgboost的近似直方圖算法也和lightgbm的直方圖算法類(lèi)似。為什么xgboost的近似直方圖算法還是比lightgbm慢很多？

-. xgboost 在每一層動(dòng)態(tài)構(gòu)建直方圖。因?yàn)閤gboost的直方圖算法并不是針對(duì)特定的特征，而是所有的特征共享一個(gè)直方圖（每個(gè)樣本的權(quán)重是二階導(dǎo)數(shù)），所以每個(gè)層的直方圖都要重新構(gòu)建，而lightgbm對(duì)于每個(gè)特征都有一個(gè)直方圖，所以構(gòu)建一次直方圖就足夠了。

-. lightgbm做了緩存優(yōu)化嗎？

lightgbm 的哪些方面是并行化的？

-.特征并行

一般的特征并行就是對(duì)數(shù)據(jù)進(jìn)行垂直分區(qū)（垂直分區(qū)數(shù)據(jù)，即拆分屬性），然后將拆分后的數(shù)據(jù)分散到各個(gè)worker上。每個(gè)worker計(jì)算自己擁有的數(shù)據(jù)的最佳分割點(diǎn)，然后匯總得到全局結(jié)果。最佳分裂點(diǎn)。但lightgbm表示這種方式通信開(kāi)銷(xiāo)比較大。 lightgbm的做法是每個(gè)worker擁有所有數(shù)據(jù)，然后進(jìn)行劃分？ （我不明白，既然每個(gè)worker都有所有的數(shù)據(jù)，那么總結(jié)有什么意義呢？這個(gè)并行性體現(xiàn)在哪里？？）

-.數(shù)據(jù)并行

傳統(tǒng)的數(shù)據(jù)并行對(duì)數(shù)據(jù)集進(jìn)行劃分，也稱(chēng)為并行分區(qū)（水平分區(qū)數(shù)據(jù)）。分發(fā)到每個(gè)worker后，worker將獲得的數(shù)據(jù)制作直方圖，并對(duì)每個(gè)worker的直方圖進(jìn)行匯總，得到全局直方圖。 Lightgbm還聲稱(chēng)這個(gè)操作的通信開(kāi)銷(xiāo)比較大。 Lightgbm的做法是使用“Reduce Scatter”機(jī)制。它并沒(méi)有總結(jié)所有的直方圖，只是總結(jié)了不同worker的不同特征的直方圖（原理？）。在這個(gè)總結(jié)的直方圖上進(jìn)行分割并最終同步。