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

GBDT

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

大意

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

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

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

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

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

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

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

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

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

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

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

xgboost 使用 level-wise 分割策略，而 lightGBM 使用 leaf-wise 策略。不同之處在于xgboost不加區(qū)別地分割每一層中的所有節(jié)點。有些節(jié)點的增益可能很小，對結(jié)果影響不大，但xgboost也被拆分了，帶來了必要的開銷。 leaf-wise的方法是在當前所有葉子節(jié)點中選擇分裂收益最大的節(jié)點進行分裂，并遞歸地進行。很明顯，leaf-wise的這種方法很容易過擬合，因為很容易陷入到比較高的深度，所以需要限制最大深度，以避免過擬合。

lightgbm使用基于直方圖的決策樹算法，與xgboost中的精確算法不同。直方圖算法在內(nèi)存和計算成本方面具有相當大的優(yōu)勢。

-.內(nèi)存優(yōu)勢：顯然，直方圖算法的內(nèi)存消耗是(#data* #features * 1Bytes)（因為對特征分桶后只保存了特征離散化后的值），而xgboost的exact算法的內(nèi)存消耗是：(2 * #data * #features* 4Bytes)，因為xgboost需要同時保存原始特征值和該值的順序索引。這些值需要32位浮點數(shù)來保存。

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

直方圖差異加速度

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

lightgbm支持直接輸入分類特征

-.在分割離散特征時，將每個值視為一個桶，分割時的增益計算為“是否屬于某個類別”的增益。類似于one-hot編碼。

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

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

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

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

-.特征并行

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

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

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