20211224

【機(jī)器學(xué)習(xí)算法總結(jié)】XGBoost_yyy430的博客-CSDN博客_xgboost

xgboost參數(shù)

默認(rèn)：auto。XGBoost中使用的樹構(gòu)造算法。可選項(xiàng)：auto，exact，approx，hist，gpu_exact，gpu_hist。分布式和外部存儲(chǔ)器版本僅支持tree_method = approx。auto：使用啟發(fā)式方法選擇最快的方法。（1）對(duì)于中小型數(shù)據(jù)集，將使用精確的貪婪（exact）。（2）對(duì)于非常大的數(shù)據(jù)集，將選擇近似算法（approx）。（3）因?yàn)榕f行為總是在單個(gè)機(jī)器中使用精確貪婪，所以當(dāng)選擇近似算法來通知該選擇時(shí)，用戶將得到消息。
exact：精確貪心算法。
approx：使用分位數(shù)草圖和梯度直方圖的近似貪婪算法。
hist：快速直方圖優(yōu)化近似貪心算法。 它使用了一些性能改進(jìn)，例如垃圾箱緩存。
gpu_exact：精確算法的GPU實(shí)現(xiàn)。
gpu_hist：hist算法的GPU實(shí)現(xiàn)。

文章不全? ?缺少公式和圖

一、提升樹

1. 提升樹boostring tree是以決策樹為基本學(xué)習(xí)器的提升方法。它被認(rèn)為是統(tǒng)計(jì)學(xué)習(xí)中性能最好的方法之一。

2. 對(duì)分類問題，提升樹中的決策樹是二叉決策樹；對(duì)回歸問題，提升樹中的決策樹是二叉回歸樹。

3. 提升樹模型可以表示為決策樹為基本學(xué)習(xí)器的加法模型：??。

   其中 ：

   • 表示第 個(gè)決策樹。
   • 為第 個(gè)決策樹的參數(shù)。
   • 為決策樹的數(shù)量。

4. 提升樹算法采用前向分步算法。

   • 首先確定初始提升樹??。

   • 第??步模型為：?。其中??為待求的第??個(gè)決策樹。

   • 通過經(jīng)驗(yàn)風(fēng)險(xiǎn)極小化確定第??個(gè)決策樹的參數(shù)?：?。

     這里沒有引入正則化，而在xgboost?中會(huì)引入正則化。

5. 不同問題的提升樹學(xué)習(xí)算法主要區(qū)別在于使用的損失函數(shù)不同（設(shè)預(yù)測值為?，真實(shí)值為?)：

   • 回歸問題：通常使用平方誤差損失函數(shù)： 。
   • 分類問題：通常使用指數(shù)損失函數(shù)： 。

1.1 算法

1. 給定訓(xùn)練數(shù)據(jù)集?，其中??為輸入空間，??為輸出空間。

   如果將輸入空間??劃分為??個(gè)互不相交的區(qū)域?，并且在每個(gè)區(qū)域上確定輸出的常量?， 則決策樹可以表示為：?

   其中：

   • 參數(shù) 表示決策樹的劃分區(qū)域和各區(qū)域上的輸出。
   • 是決策樹的復(fù)雜度，即葉結(jié)點(diǎn)個(gè)數(shù)。

2. 回歸問題中，提升樹采用平方誤差損失函數(shù)。此時(shí)：

   其中??為當(dāng)前模型擬合數(shù)據(jù)的殘差。

   所以對(duì)回歸問題的提升樹算法，第??個(gè)決策樹??只需要簡單擬合當(dāng)前模型的殘差。

3. 不僅是回歸提升樹算法，其它的boosting?回歸算法也是擬合當(dāng)前模型的殘差。

4. 回歸提升樹算法：

   • 輸入：訓(xùn)練數(shù)據(jù)集?

   • 輸出：提升樹?

   • 算法步驟：

     • 初始化?

     • 對(duì)于?

       • 計(jì)算殘差： 。構(gòu)建訓(xùn)練殘差 ： 。
       • 通過學(xué)習(xí)一個(gè)回歸樹來擬合殘差 ，得到 。
       • 更新

     • 得到回歸問題提升樹：?。

1.2 GBT

1. 提升樹中，當(dāng)損失函數(shù)是平方損失函數(shù)和指數(shù)損失函數(shù)時(shí)，每一步優(yōu)化都很簡單。因?yàn)槠椒綋p失函數(shù)和指數(shù)損失函數(shù)的求導(dǎo)非常簡單。

   當(dāng)損失函數(shù)是一般函數(shù)時(shí)，往往每一步優(yōu)化不是很容易。針對(duì)這個(gè)問題，Freidman提出了梯度提升算法。

2. 梯度提升樹GBT?是利用最速下降法的近似方法。其關(guān)鍵是利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值作為殘差的近似值，從而擬合一個(gè)回歸樹。

   根據(jù)：

   則有：

   要使得損失函數(shù)降低，一個(gè)可選的方案是：?。

   • 對(duì)于平方損失函數(shù)，它就是通常意義上的殘差。? ? ? ?看原文更好? ?有些圖沒粘貼過來
   • 對(duì)于一般損失函數(shù)，它就是殘差的近似 。

3. 梯度提升樹用于分類模型時(shí)，是梯度提升決策樹GBDT；用于回歸模型時(shí)，是梯度提升回歸樹GBRT。

4. 梯度提升回歸樹算法GBRT：

   • 輸入：

     • 訓(xùn)練數(shù)據(jù)集
     • 損失函數(shù)

   • 輸出：回歸樹?

   • 算法步驟：

     • 初始化：??。

       它是一顆只有根結(jié)點(diǎn)的樹，根結(jié)點(diǎn)的輸出值為：使得損失函數(shù)最小的值。

     • 對(duì)于?

       • 對(duì)于, 計(jì)算：

       • 對(duì)??擬合一棵回歸樹，得到第??棵樹的葉結(jié)點(diǎn)區(qū)域?

       • 對(duì)??計(jì)算每個(gè)區(qū)域??上的輸出值：

       • 更新?

     • 最終得到回歸樹：??。

5. 梯度提升決策樹算法GBDT與GBRT類似，主要區(qū)別是GBDT的損失函數(shù)與GBRT的損失函數(shù)不同。

1.3 正則化

1. 在工程應(yīng)用中，通常利用下列公式來更新模型：?。

   其中??稱作學(xué)習(xí)率。

   學(xué)習(xí)率是正則化的一部分，它可以降低模型更新的速度（需要更多的迭代）。

   • 經(jīng)驗(yàn)表明：一個(gè)小的學(xué)習(xí)率 () 可以顯著提高模型的泛化能力（相比較于 ) 。
   • 如果學(xué)習(xí)率較大會(huì)導(dǎo)致預(yù)測性能出現(xiàn)較大波動(dòng)。

2. Freidman?從bagging?策略受到啟發(fā)，采用隨機(jī)梯度提升來修改了原始的梯度提升樹算法。

   • 每一輪迭代中，新的決策樹擬合的是原始訓(xùn)練集的一個(gè)子集（而并不是原始訓(xùn)練集）的殘差。

     這個(gè)子集是通過對(duì)原始訓(xùn)練集的無放回隨機(jī)采樣而來。

   • 子集的占比??是一個(gè)超參數(shù)，并且在每輪迭代中保持不變。

     • 如果 ，則與原始的梯度提升樹算法相同。
     • 較小的 會(huì)引入隨機(jī)性，有助于改善過擬合，因此可以視作一定程度上的正則化。
     • 工程經(jīng)驗(yàn)表明， 會(huì)帶來一個(gè)較好的結(jié)果。

   • 這種方法除了改善過擬合之外，另一個(gè)好處是：未被采樣的另一部分子集可以用來計(jì)算包外估計(jì)誤差。

     因此可以避免額外給出一個(gè)獨(dú)立的驗(yàn)證集。

3. 梯度提升樹會(huì)限制每棵樹的葉子結(jié)點(diǎn)包含的樣本數(shù)量至少包含??個(gè)樣本，其中??為超參數(shù)。在訓(xùn)練過程中，一旦劃分結(jié)點(diǎn)會(huì)導(dǎo)致子結(jié)點(diǎn)的樣本數(shù)少于??，則終止劃分。

   這也是一種正則化策略，它會(huì)改善葉結(jié)點(diǎn)的預(yù)測方差。

1.4 RF vs GBT

1. 從模型框架的角度來看：

   • 梯度提升樹GBT 為boosting 模型。
   • 隨機(jī)森林RF 為bagging 模型。

2. 從偏差分解的角度來看：

   • 梯度提升樹GBT 采用弱分類器（高偏差，低方差）。梯度提升樹綜合了這些弱分類器，在每一步的過程中降低了偏差，但是保持低方差。
   • 隨機(jī)森林RF 采用完全成長的子決策樹（低偏差，高方差）。隨機(jī)森林要求這些子樹之間盡可能無關(guān)，從而綜合之后能降低方差，但是保持低偏差。

3. 如果在梯度提升樹和隨機(jī)森林之間二選一，幾乎總是建議選擇梯度提升樹。

   • 隨機(jī)森林的優(yōu)點(diǎn)：天然的支持并行計(jì)算，因?yàn)槊總€(gè)子樹都是獨(dú)立的計(jì)算。

   • 梯度提升樹的優(yōu)點(diǎn)：

     • 梯度提升樹采用更少的子樹來獲得更好的精度。

       因?yàn)樵诿枯喌?#xff0c;梯度提升樹會(huì)完全接受現(xiàn)有樹（投票權(quán)為1）。而隨機(jī)森林中每棵樹都是同等重要的（無論它們表現(xiàn)的好壞），它們的投票權(quán)都是?，因此不是完全接受的。

     • 梯度提升樹也可以修改從而實(shí)現(xiàn)并行化。

     • 梯度提升樹有一個(gè)明確的數(shù)學(xué)模型。因此任何能寫出梯度的任務(wù)，都可以應(yīng)用梯度提升樹（比如?ranking?任務(wù)）。而隨機(jī)森林并沒有一個(gè)明確的數(shù)學(xué)模型。

二、xgboost

1. xgboost?也是使用與提升樹相同的前向分步算法。其區(qū)別在于：xgboost?通過結(jié)構(gòu)風(fēng)險(xiǎn)極小化來確定下一個(gè)決策樹的參數(shù)?：

   其中：

   • 為第 個(gè)決策樹的正則化項(xiàng)。這是xgboost 和GBT的一個(gè)重要區(qū)別。
   • 為目標(biāo)函數(shù)。

2. 定義：

   即：

   • 為 在 的一階導(dǎo)數(shù)。
   • 為 在 的二階導(dǎo)數(shù)。

   對(duì)目標(biāo)函數(shù)??執(zhí)行二階泰勒展開：

   提升樹模型只采用一階泰勒展開。這也是xgboost?和GBT的另一個(gè)重要區(qū)別。

3. 對(duì)一個(gè)決策樹??，假設(shè)不考慮復(fù)雜的推導(dǎo)過程，僅考慮決策樹的效果：

   • 給定輸入 ，該決策樹將該輸入經(jīng)過不斷的劃分，最終劃分到某個(gè)葉結(jié)點(diǎn)上去。
   • 給定一個(gè)葉結(jié)點(diǎn)，該葉結(jié)點(diǎn)有一個(gè)輸出值。

   因此將決策樹拆分成結(jié)構(gòu)部分?，和葉結(jié)點(diǎn)權(quán)重部分??，其中??為葉結(jié)點(diǎn)的數(shù)量。

   • 結(jié)構(gòu)部分 的輸出是葉結(jié)點(diǎn)編號(hào) 。它的作用是將輸入 映射到編號(hào)為 的葉結(jié)點(diǎn)。
   • 葉結(jié)點(diǎn)權(quán)重部分就是每個(gè)葉結(jié)點(diǎn)的值。它的作用是輸出編號(hào)為 的葉結(jié)點(diǎn)的值 。

   因此決策樹改寫為：??。

2.1 結(jié)構(gòu)分

1. 定義一個(gè)決策樹的復(fù)雜度為：?。

   其中：?為葉結(jié)點(diǎn)的個(gè)數(shù)；?為每個(gè)葉結(jié)點(diǎn)的輸出值；?為系數(shù)，控制這兩個(gè)部分的比重。

   • 葉結(jié)點(diǎn)越多，則決策樹越復(fù)雜。
   • 每個(gè)葉結(jié)點(diǎn)輸出值的絕對(duì)值越大，則決策樹越復(fù)雜。

   該復(fù)雜度是一個(gè)經(jīng)驗(yàn)公式。事實(shí)上還有很多其他的定義復(fù)雜度的方式，只是這個(gè)公式效果還不錯(cuò)。

2. 將樹的拆分、樹的復(fù)雜度代入??的二階泰勒展開，有：

   對(duì)于每個(gè)樣本?，它必然被劃分到樹??的某個(gè)葉結(jié)點(diǎn)。定義劃分到葉結(jié)點(diǎn)??的樣本的集合為：?。則有：

3. 定義 ：?。

   • 刻畫了隸屬于葉結(jié)點(diǎn) 的那些樣本的一階偏導(dǎo)數(shù)之和。
   • 刻畫了隸屬于葉結(jié)點(diǎn) 的那些樣本的二階偏導(dǎo)數(shù)之和。

   偏導(dǎo)數(shù)是損失函數(shù)??關(guān)于當(dāng)前模型的輸出??的偏導(dǎo)數(shù)。

   則上式化簡為：?。

   假設(shè)??與 與??無關(guān)，對(duì)??求導(dǎo)等于0，則得到：?。

   忽略常數(shù)項(xiàng)，于是定義目標(biāo)函數(shù)為：

4. 在推導(dǎo)過程中假設(shè)??與 與??無關(guān)，這其實(shí)假設(shè)已知樹的結(jié)構(gòu)。

   事實(shí)上??是與??相關(guān)的，甚至與樹的結(jié)構(gòu)相關(guān)，因此定義??為結(jié)構(gòu)分。

   結(jié)構(gòu)分刻畫了：當(dāng)已知樹的結(jié)構(gòu)時(shí)目標(biāo)函數(shù)的最小值。

2.2 分解結(jié)點(diǎn)

1. 現(xiàn)在的問題是：如何得到最佳的樹的結(jié)構(gòu)，從而使得目標(biāo)函數(shù)全局最小。

2.2.1 貪心算法

1. 第一種方法是對(duì)現(xiàn)有的葉結(jié)點(diǎn)加入一個(gè)分裂，然后考慮分裂之后目標(biāo)函數(shù)降低多少。

   • 如果目標(biāo)函數(shù)下降，則說明可以分裂。
   • 如果目標(biāo)函數(shù)不下降，則說明該葉結(jié)點(diǎn)不宜分裂。

2. 對(duì)于一個(gè)葉結(jié)點(diǎn)，假如給定其分裂點(diǎn)，定義劃分到左子結(jié)點(diǎn)的樣本的集合為：?；定義劃分到右子結(jié)點(diǎn)的樣本的集合為：?。則有：

3. 定義葉結(jié)點(diǎn)的分裂增益為：

   其中：

   • 表示：該葉結(jié)點(diǎn)的左子樹的結(jié)構(gòu)分。
   • 表示：該葉結(jié)點(diǎn)的右子樹的結(jié)構(gòu)分。
   • 表示：如果不分裂，則該葉結(jié)點(diǎn)本身的結(jié)構(gòu)分。
   • 表示：因?yàn)榉至褜?dǎo)致葉結(jié)點(diǎn)數(shù)量增大1，從而導(dǎo)致增益的下降。

   每次分裂只一個(gè)葉結(jié)點(diǎn)，因此其它葉結(jié)點(diǎn)不會(huì)發(fā)生變化。因此：

   • 若 ，則該葉結(jié)點(diǎn)應(yīng)該分裂。
   • 若 ，則該葉結(jié)點(diǎn)不宜分裂。

4. 現(xiàn)在的問題是：不知道分裂點(diǎn)。對(duì)于每個(gè)葉結(jié)點(diǎn)，存在很多個(gè)分裂點(diǎn)，且可能很多分裂點(diǎn)都能帶來增益。

   解決的辦法是：對(duì)于葉結(jié)點(diǎn)中的所有可能的分裂點(diǎn)進(jìn)行一次掃描。然后計(jì)算每個(gè)分裂點(diǎn)的增益，選取增益最大的分裂點(diǎn)作為本葉結(jié)點(diǎn)的最優(yōu)分裂點(diǎn)。

5. 最優(yōu)分裂點(diǎn)貪心算法：

   • 輸入：

     • 數(shù)據(jù)集 ，其中樣本 。
     • 屬于當(dāng)前葉結(jié)點(diǎn)的樣本集的下標(biāo)集合 。

   • 輸出：當(dāng)前葉結(jié)點(diǎn)最佳分裂點(diǎn)。

   • 算法：

     • 初始化：?。

     • 遍歷各維度：

       • 初始化：?

       • 遍歷各拆分點(diǎn)：沿著第??維 ：

         • 如果第??維特征為連續(xù)值，則將當(dāng)前葉結(jié)點(diǎn)中的樣本從小到大排序。然后用??順序遍歷排序后的樣本下標(biāo)：

         • 如果第??維特征為離散值??，設(shè)當(dāng)前葉結(jié)點(diǎn)中第??維取值??樣本的下標(biāo)集合為??，則遍歷??：

     • 選取最大的??對(duì)應(yīng)的維度和拆分點(diǎn)作為最優(yōu)拆分點(diǎn)。

6. 分裂點(diǎn)貪心算法嘗試所有特征和所有分裂位置，從而求得最優(yōu)分裂點(diǎn)。

   當(dāng)樣本太大且特征為連續(xù)值時(shí)，這種暴力做法的計(jì)算量太大。

2.2.2 近似算法

1. 近似算法尋找最優(yōu)分裂點(diǎn)時(shí)不會(huì)枚舉所有的特征值，而是對(duì)特征值進(jìn)行聚合統(tǒng)計(jì)，然后形成若干個(gè)桶。

   然后僅僅將桶邊界上的特征的值作為分裂點(diǎn)的候選，從而獲取計(jì)算性能的提升。

2. 假設(shè)數(shù)據(jù)集??，樣本??。

   對(duì)第??個(gè)特征進(jìn)行分桶：

   • 如果第??個(gè)特征為連續(xù)特征，則執(zhí)行百分位分桶，得到分桶的區(qū)間為：?，其中??。

     分桶的數(shù)量、分桶的區(qū)間都是超參數(shù)，需要仔細(xì)挑選。

   • 如果第??個(gè)特征為離散特征，則執(zhí)行按離散值分桶，得到的分桶為：?，其中??為第??個(gè)特征的所有可能的離散值。

     分桶的數(shù)量??就是所有樣本在第??個(gè)特征上的取值的數(shù)量。

3. 最優(yōu)分裂點(diǎn)近似算法：

   • 輸入：

     • 數(shù)據(jù)集 ，其中樣本 。
     • 屬于當(dāng)前葉結(jié)點(diǎn)的樣本集的下標(biāo)集合 。

   • 輸出：當(dāng)前葉結(jié)點(diǎn)最佳分裂點(diǎn)。

   • 算法：

     • 對(duì)每個(gè)特征進(jìn)行分桶。 假設(shè)對(duì)第??個(gè)特征上的值進(jìn)行分桶為：?。

       如果第??個(gè)特征為連續(xù)特征，則要求滿足??。

     • 初始化：?。

     • 遍歷各維度：

       • 初始化：?

       • 遍歷各拆分點(diǎn)，即遍歷??：

         • 如果是連續(xù)特征，則設(shè)葉結(jié)點(diǎn)的樣本中，第??個(gè)特征取值在區(qū)間??的樣本的下標(biāo)集合為?，則：

         • 如果是離散特征，則設(shè)葉結(jié)點(diǎn)的樣本中，第??個(gè)特征取值等于??的樣本的下標(biāo)集合為?，則：

       • 選取最大的??對(duì)應(yīng)的維度和拆分點(diǎn)作為最優(yōu)拆分點(diǎn)。

4. 分桶有兩種模式：

   • 全局模式：在算法開始時(shí)，對(duì)每個(gè)維度分桶一次，后續(xù)的分裂都依賴于該分桶并不再更新。

     • 優(yōu)點(diǎn)是：只需要計(jì)算一次，不需要重復(fù)計(jì)算。
     • 缺點(diǎn)是：在經(jīng)過多次分裂之后，葉結(jié)點(diǎn)的樣本有可能在很多全局桶中是空的。

   • 局部模式：除了在算法開始時(shí)進(jìn)行分桶，每次拆分之后再重新分桶。

     • 優(yōu)點(diǎn)是：每次分桶都能保證各桶中的樣本數(shù)量都是均勻的。
     • 缺點(diǎn)是：計(jì)算量較大。

   全局模式會(huì)構(gòu)造更多的候選拆分點(diǎn)。而局部模式會(huì)更適合構(gòu)建更深的樹。

5. 分桶時(shí)的桶區(qū)間間隔大小是個(gè)重要的參數(shù)。

   區(qū)間間隔越小，則桶越多，則劃分的越精細(xì)，候選的拆分點(diǎn)就越多。

2.3 加權(quán)分桶

1. 假設(shè)候選樣本的第??維特征，及候選樣本的損失函數(shù)的二階偏導(dǎo)數(shù)為：

   定義排序函數(shù)：

   它刻畫的是：第??維小于??的樣本的??之和，占總的??之和的比例。

2. xgboost?的作者提出了一種帶權(quán)重的桶劃分算法。定義候選樣本的下標(biāo)集合為??，拆分點(diǎn)??定義為：

   其中??表示樣本??的第??個(gè)特征。即：

   • 最小的拆分點(diǎn)是所有樣本第??維的最小值。

   • 最大的拆分點(diǎn)是所有樣本第??維的最大值。

   • 中間的拆分點(diǎn)：選取拆分點(diǎn)，使得相鄰拆分點(diǎn)的排序函數(shù)值小于??（分桶的桶寬）。

     • 其意義為：第 維大于等于 ，小于 的樣本的 之和，占總的 之和的比例小于 。
     • 這種拆分點(diǎn)使得每個(gè)桶內(nèi)的以 為權(quán)重的樣本數(shù)量比較均勻，而不是樣本個(gè)數(shù)比較均勻。

3. 上述拆分的一個(gè)理由是：根據(jù)損失函數(shù)的二階泰勒展開有：

   對(duì)于第??個(gè)決策樹，它等價(jià)于樣本??的真實(shí)標(biāo)記為?、權(quán)重為?、損失函數(shù)為平方損失函數(shù)。因此分桶時(shí)每個(gè)桶的權(quán)重為??。

2.4 缺失值

1. 真實(shí)場景中，有很多可能導(dǎo)致產(chǎn)生稀疏。如：數(shù)據(jù)缺失、某個(gè)特征上出現(xiàn)很多 0 項(xiàng)、人工進(jìn)行?one-hot?編碼導(dǎo)致的大量的 0。

   • 理論上，數(shù)據(jù)缺失和數(shù)值0的含義是不同的，數(shù)值 0 是有效的。

   • 實(shí)際上，數(shù)值0的處理方式類似缺失值的處理方式，都視為稀疏特征。

     在xgboost?中，數(shù)值0的處理方式和缺失值的處理方式是統(tǒng)一的。這只是一個(gè)計(jì)算上的優(yōu)化，用于加速對(duì)稀疏特征的處理速度。

   • 對(duì)于稀疏特征，只需要對(duì)有效值進(jìn)行處理，無效值則采用默認(rèn)的分裂方向。

     注意：每個(gè)結(jié)點(diǎn)的默認(rèn)分裂方向可能不同。

2. 在xgboost?算法的實(shí)現(xiàn)中，允許對(duì)數(shù)值0進(jìn)行不同的處理。可以將數(shù)值0視作缺失值，也可以將其視作有效值。

   如果數(shù)值0是有真實(shí)意義的，則建議將其視作有效值。

3. 缺失值處理算法：

   • 輸入：

     • 數(shù)據(jù)集 ，其中樣本 。
     • 屬于當(dāng)前葉結(jié)點(diǎn)的樣本的下標(biāo)集合 。
     • 屬于當(dāng)前葉結(jié)點(diǎn)，且第 維特征有效的樣本的下標(biāo)集合 。

   • 輸出：當(dāng)前葉結(jié)點(diǎn)最佳分裂點(diǎn)。

   • 算法：

     • 初始化：?。

     • 遍歷各維度：

       • 先從左邊開始遍歷：

         • 初始化：?

         • 遍歷各拆分點(diǎn)：沿著第??維，將當(dāng)前有效的葉結(jié)點(diǎn)的樣本從小到大排序。

           這相當(dāng)于所有無效特征值的樣本放在最右側(cè)，因此可以保證無效的特征值都在右子樹。

           然后用??順序遍歷排序后的樣本下標(biāo)：

       • 再從右邊開始遍歷：

         • 初始化：?

         • 遍歷各拆分點(diǎn)：沿著??維，將當(dāng)前葉結(jié)點(diǎn)的樣本從大到小排序。

           這相當(dāng)于所有無效特征值的樣本放在最左側(cè)，因此可以保證無效的特征值都在左子樹。

           然后用??逆序遍歷排序后的樣本下標(biāo)：

     • 選取最大的??對(duì)應(yīng)的維度和拆分點(diǎn)作為最優(yōu)拆分點(diǎn)。

4. 缺失值處理算法中，通過兩輪遍歷可以確保稀疏值位于左子樹和右子樹的情形。

2.5 其他優(yōu)化

2.5.1 正則化

1. xgboost?在學(xué)習(xí)過程中使用了如下的正則化策略來緩解過擬合：

   • 通過學(xué)習(xí)率 來更新模型： 。
   • 類似于隨機(jī)森林，采取隨機(jī)屬性選擇。

2.5.2 計(jì)算速度提升

1. xgboost?在以下方面提出改進(jìn)來提升計(jì)算速度：

   • 預(yù)排序pre-sorted 。
   • cache-aware 預(yù)取。
   • Out-of-Core 大數(shù)據(jù)集。

2.5.2.1 預(yù)排序

1. xgboost?提出column block?數(shù)據(jù)結(jié)構(gòu)來降低排序時(shí)間。

   • 每一個(gè)block 代表一個(gè)屬性，樣本在該block 中按照它在該屬性的值排好序。
   • 這些block 只需要在程序開始的時(shí)候計(jì)算一次，后續(xù)排序只需要線性掃描這些block 即可。
   • 由于屬性之間是獨(dú)立的，因此在每個(gè)維度尋找劃分點(diǎn)可以并行計(jì)算。

2. block?可以僅存放樣本的索引，而不是樣本本身，這樣節(jié)省了大量的存儲(chǔ)空間。

   如：block_1?代表所有樣本在feature_1?上的從小到大排序：sample_no1,sample_no2,....?。

   其中樣本編號(hào)出現(xiàn)的位置代表了該樣本的排序。

2.5.2.2 預(yù)取

1. 由于在column block?中，樣本的順序會(huì)被打亂，這會(huì)使得從導(dǎo)數(shù)數(shù)組中獲取??時(shí)的緩存命中率較低。

   因此xgboost?提出了cache-aware?預(yù)取算法，用于提升緩存命中率。

2. xgboost?會(huì)以minibatch?的方式累加數(shù)據(jù)，然后在后臺(tái)開啟一個(gè)線程來加載需要用到的導(dǎo)數(shù)??。

   這里有個(gè)折中：minibatch?太大，則會(huì)引起cache miss?；太小，則并行程度較低。

2.5.2.3 Out-of-Core

1. xgboost?利用硬盤來處理超過內(nèi)存容量的大數(shù)據(jù)集。其中使用了下列技術(shù)：

   • 使用block 壓縮技術(shù)來緩解內(nèi)存和硬盤的數(shù)據(jù)交換IO ： 數(shù)據(jù)按列壓縮，并且在硬盤到內(nèi)存的傳輸過程中被自動(dòng)解壓縮。
   • 數(shù)據(jù)隨機(jī)分片到多個(gè)硬盤，每個(gè)硬盤對(duì)應(yīng)一個(gè)預(yù)取線程，從而加大"內(nèi)存-硬盤"交換數(shù)據(jù)的吞吐量。

三、LightGBM

1. GBT?的缺點(diǎn)：在構(gòu)建子決策樹時(shí)為了獲取分裂點(diǎn)，需要在所有特征上掃描所有的樣本，從而獲得最大的信息增益。

   • 當(dāng)樣本的數(shù)量很大，或者樣本的特征很多時(shí)，效率非常低。
   • 同時(shí)GBT 也無法使用類似mini batch 方式進(jìn)行訓(xùn)練。

2. xgboost?缺點(diǎn)：

   • 每輪迭代都需要遍歷整個(gè)數(shù)據(jù)集多次。

     • 如果把整個(gè)訓(xùn)練集裝載進(jìn)內(nèi)存，則限制了訓(xùn)練數(shù)據(jù)的大小。
     • 如果不把整個(gè)訓(xùn)練集裝載進(jìn)內(nèi)存，則反復(fù)讀寫訓(xùn)練數(shù)據(jù)會(huì)消耗非常大的IO 時(shí)間。

   • 空間消耗大。預(yù)排序（pre-sorted）需要保存數(shù)據(jù)的feature?值，還需要保存feature?排序的結(jié)果（如排序后的索引，為了后續(xù)的快速計(jì)算分割點(diǎn)）。因此需要消耗訓(xùn)練數(shù)據(jù)兩倍的內(nèi)存。

   • 時(shí)間消耗大。為了獲取分裂點(diǎn)，需要在所有特征上掃描所有的樣本，從而獲得最大的信息增益，時(shí)間消耗大。

   • 對(duì)cache?優(yōu)化不友好，造成cache miss?。

     • 預(yù)排序后，feature 對(duì)于梯度的訪問是一種隨機(jī)訪問，并且不同feature 訪問的順序不同，無法對(duì)cache 進(jìn)行優(yōu)化。
     • 在每一層的樹生長時(shí)，需要隨機(jī)訪問一個(gè)行索引到葉子索引的數(shù)組，并且不同feature 訪問的順序也不同。

3. LightGBM?的優(yōu)點(diǎn)：

   • 更快的訓(xùn)練效率：在達(dá)到同樣的準(zhǔn)確率的情況下，可以達(dá)到比GBT 約20倍的訓(xùn)練速度。
   • 低內(nèi)存使用。
   • 更高的準(zhǔn)確率。
   • 支持并行化學(xué)習(xí)。
   • 可處理大規(guī)模數(shù)據(jù)。

3.1 原理

1. LightGBM?的思想：若減少訓(xùn)練樣本的數(shù)量，或者減少樣本的訓(xùn)練特征數(shù)量，則可以大幅度提高訓(xùn)練速度。

2. LightGBM?提出了兩個(gè)策略：

   • Gradient-based One-Side Sampling(GOSS)： 基于梯度的采樣。該方法用于減少訓(xùn)練樣本的數(shù)量。
   • Exclusive Feature Bundling(EFB)： 基于互斥特征的特征捆綁。該方法用于減少樣本的特征。

3.1.1 GOSS

3.1.1.1 算法

1. 減少樣本的數(shù)量的難點(diǎn)在于：不知道哪些樣本應(yīng)該被保留，哪些樣本被丟棄。

   • 傳統(tǒng)方法：采用隨機(jī)丟棄的策略。
   • GOSS 方法：保留梯度較大的樣本，梯度較小的樣本則隨機(jī)丟棄。

2. 在AdaBoost?中每個(gè)樣本都有一個(gè)權(quán)重，該權(quán)重指示了樣本在接下來的訓(xùn)練過程中的重要性。

   在GBDT?中并沒有這樣的權(quán)重。如果能知道每個(gè)樣本的重要性（即：權(quán)重），那么可以保留比較重要的樣本，丟棄不那么重要的樣本。

   由于GBDT?中，負(fù)的梯度作為當(dāng)前的殘差，接下來的訓(xùn)練就是擬合這個(gè)殘差。因此GOSS?采用樣本的梯度作為樣本的權(quán)重：

   • 如果權(quán)重較小，則說明樣本的梯度較小，說明該樣本已經(jīng)得到了很好的訓(xùn)練。因此對(duì)于權(quán)重較小的樣本，則可以隨機(jī)丟棄。
   • 如果權(quán)重較大，則說明樣本的梯度較大，說明該樣本未能充分訓(xùn)練。因此對(duì)于權(quán)重較大的樣本，則需要保留。

3. GOSS?丟棄了部分樣本，因此它改變了訓(xùn)練樣本的分布。這會(huì)影響到模型的預(yù)測準(zhǔn)確性。

   為了解決這個(gè)問題，GOSS?對(duì)小梯度的樣本進(jìn)行了修正：對(duì)每個(gè)保留下來的、小梯度的樣本，其梯度乘以系數(shù)??（即放大一個(gè)倍數(shù)）。

   其中（假設(shè)樣本總數(shù)為??）：

   • ?是一個(gè)0.0~1.0?之間的數(shù)，表示大梯度采樣比。

     其意義為：保留梯度的絕對(duì)值在?top??的樣本作為重要的樣本。

   • ?是一個(gè)0.0~1.0?之間的數(shù)，表示小梯度采樣比。

     其意義為：從不重要的樣本中隨機(jī)保留??的樣本。

   • ?是一個(gè)0.0~1.0?之間的數(shù)，表示不重要的樣本的比例。

   • ?刻畫了：從不重要的樣本中，隨機(jī)保留的樣本的比例的倒數(shù)。

4. GOSS?算法：

   • 輸入：

     • 訓(xùn)練集 ，其樣本數(shù)量為
     • 大梯度采樣比
     • 小梯度采樣比
     • 當(dāng)前的模型

   • 輸出：下一個(gè)子樹?

   • 算法：

     • 計(jì)算：

       • 修正因子
       • 重要的樣本數(shù)為
       • 隨機(jī)丟棄的樣本數(shù)為
       • 每個(gè)樣本的損失函數(shù)的梯度

     • 根據(jù)梯度的絕對(duì)值大小，將樣本按照從大到小排列。

       • 取其中取 的樣本作為重要性樣本。
       • 在 之外的樣本中，隨機(jī)選取 的樣本作為保留樣本，剩下的樣本被丟棄。

     • 構(gòu)建新的訓(xùn)練集：重要性樣本+隨機(jī)保留的樣本，其中：

       • 個(gè)重要性樣本，每個(gè)樣本的權(quán)重都為 1。
       • 個(gè)隨機(jī)保留的樣本，每個(gè)樣本的權(quán)重都為 。

     • 根據(jù)新的訓(xùn)練集及其權(quán)重，訓(xùn)練決策樹模型??來擬合殘差（即：負(fù)梯度?）。返回訓(xùn)練好的??。

5. 由于需要在所有的樣本上計(jì)算梯度，因此?丟棄樣本的比例 ～ 加速比?并不是線性的關(guān)系。

3.1.1.2 理論

1. 在GBDT?生成新的子決策樹??時(shí)，對(duì)于當(dāng)前結(jié)點(diǎn)??，考慮是否對(duì)它進(jìn)行分裂。

   假設(shè)結(jié)點(diǎn)??包含的樣本集合為?， 樣本維數(shù)為??。對(duì)于第??維，假設(shè)其拆分點(diǎn)為?。

   • 對(duì)于分類問題，其拆分增益為信息增益。它刻畫的是劃分之后混亂程度的降低，也就是純凈程度的提升：

     其中：

     • 表示樣本屬于結(jié)點(diǎn) 的概率， 為結(jié)點(diǎn) 上的樣本標(biāo)記的條件熵。
     • 表示左子結(jié)點(diǎn)的樣本集合； 表示右子結(jié)點(diǎn)的樣本集合。
     • 表示樣本屬于結(jié)點(diǎn) 的左子結(jié)點(diǎn)概率， 為左子結(jié)點(diǎn)的樣本標(biāo)記的條件熵。
     • 表示樣本屬于結(jié)點(diǎn) 的右子結(jié)點(diǎn)概率， 為右子結(jié)點(diǎn)的樣本標(biāo)記的條件熵。

     對(duì)于結(jié)點(diǎn)??的任意拆分點(diǎn)，由于??都相同，所以：

   • 對(duì)于回歸問題，其拆分增益為方差增益(variance gain:VG)。它刻畫的是劃分之后方差的下降；也就是純凈程度的提升：

     其中：

     • 表示屬于結(jié)點(diǎn) 的樣本的標(biāo)記的方差。
     • 表示左子結(jié)點(diǎn)的樣本集合； 表示右子結(jié)點(diǎn)的樣本集合。
     • 表示屬于結(jié)點(diǎn) 的左子結(jié)點(diǎn)的樣本的標(biāo)記的方差。
     • 表示屬于結(jié)點(diǎn) 的右子結(jié)點(diǎn)的樣本的標(biāo)記的方差。

     對(duì)于結(jié)點(diǎn)??的任意拆分點(diǎn)，由于??都相同，所以：

2. 對(duì)于樣本??，設(shè)其標(biāo)記為??（它是殘差，也是負(fù)梯度）。

   對(duì)于結(jié)點(diǎn)??中的樣本，設(shè)其樣本數(shù)量為?，樣本的標(biāo)記均值為??，其方差為：

   設(shè)總樣本數(shù)量為?， 則??，則有：

3. 現(xiàn)在考慮回歸問題。

   對(duì)于拆分維度??和拆分點(diǎn)?， 令左子結(jié)點(diǎn)的樣本下標(biāo)為?，樣本數(shù)量為??右子結(jié)點(diǎn)的樣本下標(biāo)為?， 樣本數(shù)量為??。則方差增益：

   考慮到?，因此有：?。因此則方差增益：

   考慮到總樣本大小?是個(gè)恒定值，因此可以去掉??。考慮到??并不隨著結(jié)點(diǎn)??的不同劃分而變化因此定義：對(duì)于拆分維度??和拆分點(diǎn)?，方差增益為：

4. 考慮在?GOSS?中，在劃分結(jié)點(diǎn)??的過程中，可能會(huì)隨機(jī)丟棄一部分樣本，從而??的樣本總數(shù)下降。因此重新定義方差增益：

5. 在GOSS?中：

   • 首先根據(jù)樣本的梯度的絕對(duì)值大小降序排列。
   • 然后選取其中的 top a 的樣本作為重要樣本，設(shè)其集合為 。則剩下的樣本集合 保留了 1-a 比例的樣本。
   • 在剩下的樣本集合 中，隨機(jī)選取總樣本的 比例的樣本保留，設(shè)其集合為 。
   • 最后將樣本 劃分到子結(jié)點(diǎn)中。

   重新定義方差增益為：

   其中：

   • ?表示所有保留的樣本的數(shù)量。??分別表示左子結(jié)點(diǎn)、右子結(jié)點(diǎn)保留的樣本的數(shù)量。

   • ?分別表示左子結(jié)點(diǎn)、右子結(jié)點(diǎn)的被保留的重要樣本的集合。

     ?分別表示左子結(jié)點(diǎn)、右子結(jié)點(diǎn)的被保留的不重要樣本的集合。

   • ?用于補(bǔ)償由于對(duì)??的采樣帶來的梯度之和的偏離。

   由于??的大小可能遠(yuǎn)遠(yuǎn)小于?，因此估計(jì)??需要的計(jì)算量可能遠(yuǎn)遠(yuǎn)小于估計(jì)?。

6. 定義近似誤差為：， 定義標(biāo)準(zhǔn)的梯度均值：

   則可以證明：至少以概率??滿足：

   其中：

   • ，刻畫的是剩余樣本集合 中最大梯度的加權(quán)值。
   • ， 刻畫的是未采取GOSS 時(shí)，劃分的左子結(jié)點(diǎn)的梯度均值、右子結(jié)點(diǎn)的梯度均值中，較大的那個(gè)。

   結(jié)論：

   • 當(dāng)劃分比較均衡（即：?） 時(shí)，近似誤差由不等式的第二項(xiàng)決定。

     此時(shí)，隨著樣本數(shù)量的增長，使用GOSS?和原始的算法的誤差逼近于 0 。

   • 當(dāng)??時(shí)，GOSS?退化為隨機(jī)采樣。

7. GOSS?的采樣增加了基學(xué)習(xí)器的多樣性，有助于提升集成模型的泛化能力。

3.1.2 EFB

1. 減少樣本特征的傳統(tǒng)方法是：使用特征篩選。

   該方式通常是通過?PCA?來實(shí)現(xiàn)的，其中使用了一個(gè)關(guān)鍵的假設(shè)：不同的特征可能包含了重復(fù)的信息。這個(gè)假設(shè)很有可能在實(shí)踐中無法滿足。

2. LightBGM?的思路是：很多特征都是互斥的，即：這些特征不會(huì)同時(shí)取得非零的值。如果能將這些互斥的特征捆綁打包成一個(gè)特征，那么可以將特征數(shù)量大幅度降低。

   現(xiàn)在有兩個(gè)問題：

   • 如何找到互斥的特征。
   • 如何將互斥的特征捆綁成一個(gè)特征。

3.1.2.1 互斥特征發(fā)現(xiàn)

1. 定義打包特征集為這樣的特征的集合：集合中的特征兩兩互斥。

   給定數(shù)據(jù)集??，其中樣本??。

   如果對(duì)每個(gè)??，都不會(huì)出現(xiàn)??，則特征??和特征??互斥。

2. 可以證明：將每個(gè)特征劃分到每個(gè)打包特征集中使得打包特征集?的數(shù)量最小，這個(gè)問題是NP?難的。

   為了解決這個(gè)問題，LightGBM?采用了一個(gè)貪心算法來求解一個(gè)近似的最優(yōu)解。

3. 將每個(gè)特征視為圖中的一個(gè)頂點(diǎn)。

   遍歷每個(gè)樣本?， 如果特征??之間不互斥（即??），則：

   • 如果頂點(diǎn) 之間不存在邊，則在頂點(diǎn) 之間連接一條邊，權(quán)重為 1 。
   • 如果頂點(diǎn) 之間存在邊，則頂點(diǎn) 之間的邊的權(quán)重加 1 。

   最終，如果一組頂點(diǎn)之間都不存在邊，則它們是相互互斥的，則可以放入到同一個(gè)打包特征集?中。

4. 事實(shí)上有些特征之間并不是完全互斥的，而是存在非常少量的沖突。即：存在少量的樣本，在這些樣本上，這些特征之間同時(shí)取得非零的值。

   如果允許這種少量的沖突，則可以將更多的特征放入打包特征集中，這樣就可以減少更多的特征。

5. 理論上可以證明：如果隨機(jī)污染小部分的樣本的特征的值，則對(duì)于訓(xùn)練accuracy?的影響是：最多影響??。其中??為污染樣本的比例，??為樣本數(shù)量 。

6. 互斥特征發(fā)現(xiàn)算法：

   • 輸入：

     • 數(shù)據(jù)集 ，其中樣本 。
     • 沖突閾值 。

   • 輸出：打包特征集?的集合?

   • 算法：

     • 構(gòu)建圖?：

       • 每個(gè)特征作為一個(gè)頂點(diǎn)。

       • 遍歷每個(gè)樣本??：

         • 遍歷所有的特征對(duì)??，如果特征??之間不互斥 （即?）則：

           • 如果頂點(diǎn) 之間不存在邊，則在頂點(diǎn) 之間連接一條邊，權(quán)重為 1 。
           • 如果頂點(diǎn) 之間存在邊，則頂點(diǎn) 之間的邊的權(quán)重加 1 。

     • 對(duì)每個(gè)頂點(diǎn)，根據(jù)?degree?（與頂點(diǎn)相連的邊的數(shù)量）來降序排列。

     • 初始化：

     • 根據(jù)頂點(diǎn)的排序遍歷頂點(diǎn)：

       設(shè)當(dāng)前頂點(diǎn)為??。

       • 遍歷?打包特征集??，計(jì)算頂點(diǎn)??與?打包特征集??的沖突值??。如果?， 則說明頂點(diǎn)??與?打包特征集??不沖突。此時(shí)將頂點(diǎn)??添加到?打包特征集??中，退出循環(huán)并考慮下一個(gè)頂點(diǎn)。

         頂點(diǎn)??與?bundle?特征集??的沖突值有兩種計(jì)算方法：

         • 計(jì)算最大沖突值：即最大的邊的權(quán)重：
         • 計(jì)算所有的沖突值：即所有的邊的權(quán)重：

       • 如果頂點(diǎn)??未加入到任何一個(gè)?打包特征集?中 ，則：創(chuàng)建一個(gè)新的?打包特征集?加入到??中，并將頂點(diǎn)??添加到這個(gè)新的?打包特征集?中。

     • 返回?

7. 互斥特征發(fā)現(xiàn)算法的算法復(fù)雜度為：?，其中??為樣本總數(shù)，?為樣本維數(shù)。

   • 復(fù)雜度主要集中在構(gòu)建圖 。
   • 該算法只需要在訓(xùn)練之前執(zhí)行一次。
   • 當(dāng)特征數(shù)量較小時(shí)，該算法的復(fù)雜度還可以接受。當(dāng)特征數(shù)量非常龐大時(shí)，該算法的復(fù)雜度太高。
   • 優(yōu)化的互斥特征發(fā)現(xiàn)算法不再構(gòu)建圖 ，而是僅僅計(jì)算每個(gè)特征的非零值。

8. 優(yōu)化的互斥特征發(fā)現(xiàn)算法：

   • 輸入：

     • 數(shù)據(jù)集 ，其中樣本 。
     • 沖突閾值 。

   • 輸出：打包特征集?的集合?

   • 算法：

     • 初始化：所有特征的非零值數(shù)量組成的數(shù)組?

     • 計(jì)算每個(gè)特征的非零值 (復(fù)雜度?) ：遍歷所有的特征??、遍歷所有所有的樣本??，獲取特征??的非零值??。

     • 根據(jù)??對(duì)頂點(diǎn)降序排列。

     • 初始化：

     • 根據(jù)頂點(diǎn)的排序遍歷頂點(diǎn)：

       設(shè)當(dāng)前頂點(diǎn)為??。

       • 遍歷?打包特征集?，計(jì)算頂點(diǎn)??與?打包特征集??的沖突值??。如果?， 則說明頂點(diǎn)??與?打包特征集??不沖突。此時(shí)將頂點(diǎn)??添加到?打包特征集??中，退出循環(huán)并考慮下一個(gè)頂點(diǎn)。

         頂點(diǎn)??與?bundle?特征集??的沖突值有兩種計(jì)算方法：

         • 計(jì)算最大沖突值：即最大的非零值：
         • 計(jì)算所有的沖突值：即所有的非零值：

         這里簡單的將兩個(gè)特征的非零值之和認(rèn)為是它們的沖突值。它是實(shí)際的沖突值的上界。

       • 如果頂點(diǎn)??未加入到任何一個(gè)?打包特征集?中 ，則：創(chuàng)建一個(gè)新的?打包特征集?加入到??中，并將頂點(diǎn)??添加到這個(gè)新的?打包特征集?中。

     • 返回?

3.1.2.2 互斥特征打包

1. 互斥特征打包的思想：可以從打包的特征中分離出原始的特征。

   假設(shè)特征?a?的取值范圍為?[0,10)， 特征?b?的取值范圍為?[0,20)?。如果a,b?是互斥特征，那么打包的時(shí)候：對(duì)于特征?b的值，給它一個(gè)偏移量，比如 20。

   最終打包特征的取值范圍為：[0,40)。

   • 如果打包特征的取值在 [0,10)， 說明該值來自于特征 a 。
   • 如果打包特征的取值在[20,40)，說明該值來自于特征 b 。

2. 基于histogram?的算法需要考慮分桶，但是原理也是類似：將?[0,x]?之間的桶分給特征?a， 將?[x+offset,y]?之間的桶分給特征?b。 其中?offset > 0?。

3. 互斥特征打包算法：

   • 輸入：

     • 數(shù)據(jù)集 ，其中樣本 。
     • 待打包的特征集合 。

   • 輸出：打包之后的分桶

   • 算法：

     • 令??記錄總的分桶數(shù)量，??記錄不同的特征的邊界。初始化：?。

     • 計(jì)算特征邊界：遍歷所有的特征?：

       • 獲取特征 的分桶數(shù)量 ，增加到 ：
       • 獲取特征 的分桶邊界：

     • 創(chuàng)建新特征，它有??個(gè)桶。

     • 計(jì)算分桶點(diǎn)：遍歷每個(gè)樣本??：

       • 計(jì)算每個(gè)特征??：

         • 如果 ，則：如果 在特征 的第 個(gè)分桶中， 那么在打包后的特征中，它位于桶 中。
         • 如果 ，則不考慮。

4. 互斥特征打包算法的算法復(fù)雜度為?，其中??為樣本總數(shù)，?為樣本維數(shù)。

5. 也可以首先掃描所有的樣本，然后建立一張掃描表，該表中存放所有樣本所有特征的非零值。

   這樣互斥特征打包算法在每個(gè)特征上僅僅需要掃描非零的樣本即可。這樣每個(gè)特征的掃描時(shí)間從??降低為?， 其中??為該特征上非零的樣本數(shù)。

   該方法的缺陷是：消耗更多的內(nèi)存，因?yàn)樾枰谡麄€(gè)訓(xùn)練期間保留這樣的一張表。

3.2 優(yōu)化

1. LightGBM?優(yōu)化思路：

   • 單個(gè)機(jī)器在不犧牲速度的情況下，盡可能多地用上更多的數(shù)據(jù)。
   • 多機(jī)并行時(shí)通信的代價(jià)盡可能地低，并且在計(jì)算上可以做到線性加速。

2. LightGBM?的優(yōu)化：

   • 基于histogram 的決策樹算法。
   • 帶深度限制的leaf-wise 的葉子生長策略。
   • 直方圖做差加速。
   • 直接支持類別（categorical） 特征。
   • 并行優(yōu)化。

3.2.1 histogram 算法

1. 基本思想：先把連續(xù)的浮點(diǎn)特征值離散化成??個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為??的直方圖。

   在遍歷數(shù)據(jù)時(shí)：

   • 根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量。
   • 當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量。
   • 然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。

2. 優(yōu)點(diǎn)：節(jié)省空間。假設(shè)有??個(gè)樣本，每個(gè)樣本有??個(gè)特征，每個(gè)特征的值都是 32 位浮點(diǎn)數(shù)。

   • 對(duì)于每一列特征，都需要一個(gè)額外的排好序的索引（32位的存儲(chǔ)空間）。則pre-sorted 算法需要消耗 字節(jié)內(nèi)存。
   • 如果基于 histogram 算法，僅需要存儲(chǔ)feature bin value（離散化后的數(shù)值），不需要原始的feature value，也不用排序。而bin value 用unit8_t 即可，因此histogram 算法消耗 字節(jié)內(nèi)存，是預(yù)排序算法的 。

3. 缺點(diǎn)：不能找到很精確的分割點(diǎn)，訓(xùn)練誤差沒有pre-sorted?好。但從實(shí)驗(yàn)結(jié)果來看，?histogram?算法在測試集的誤差和?pre-sorted?算法差異并不是很大，甚至有時(shí)候效果更好。

   實(shí)際上可能決策樹對(duì)于分割點(diǎn)的精確程度并不太敏感，而且較“粗”的分割點(diǎn)也自帶正則化的效果。

4. 采用histogram?算法之后，尋找拆分點(diǎn)的算法復(fù)雜度為：

   • 構(gòu)建histogram： 。
   • 尋找拆分點(diǎn)： ，其中 為分桶的數(shù)量。

5. 與其他算法相比：

   • scikit-learn GBDT、gbm in R 使用的是基于pre-sorted 的算法。
   • pGBRT 使用的是基于histogram 的算法。
   • xgboost 既提供了基于pre-sorted 的算法，又提供了基于histogram 的算法。
   • lightgbm 使用的是基于histogram 的算法。

3.2.2 leaf-wise 生長策略

1. 大部分梯度提升樹算法采用level-wise?的葉子生長策略：

而lightgbm?采用leaf-wise?的葉子生長策略：

1. level-wise?：

   • 優(yōu)點(diǎn)：過一遍數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過擬合。
   • 缺點(diǎn)：實(shí)際上level-wise是一種低效算法 。它不加區(qū)分的對(duì)待同一層的葉子，帶來了很多沒必要的開銷：實(shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。

2. leaf-wise：是一種更為高效的策略。每次從當(dāng)前所有葉子中，找到分裂增益最大的一個(gè)葉子來分裂。

   • 優(yōu)點(diǎn)：同level-wise?相比，在分裂次數(shù)相同的情況下，leaf-wise?可以降低更多的誤差，得到更好的精度。

   • 缺點(diǎn)：可能會(huì)長出比較深的決策樹，產(chǎn)生過擬合。

     因此?lightgbm?在?leaf-wise?之上增加了一個(gè)最大深度限制，在保證高效率的同時(shí)防止過擬合。

3.2.3 直方圖做差加速

1. 通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)。但是事實(shí)上一個(gè)葉子的直方圖可以由它的父親結(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。

   LightGBM?在構(gòu)造一個(gè)葉子的直方圖后，可以用非常微小的代價(jià)得到它兄弟葉子的直方圖，在速度上可以提升一倍。

3.2.4 直接支持 categorical 特征

1. 通常對(duì)categorical?特征進(jìn)行one-hot?編碼，但是這個(gè)做法在決策樹學(xué)習(xí)中并不好：對(duì)于取值集合較多的categorical feature，學(xué)習(xí)到的樹模型會(huì)非常不平衡；樹的深度需要很深才能達(dá)到較高的準(zhǔn)確率。

   LightGBM?直接支持categorical?特征。（因?yàn)榛谥狈綀D 所有天然的 每個(gè)值就是一個(gè)分桶）

3.2.5 并行優(yōu)化

3.2.5.1 特征并行

1. 傳統(tǒng)的特征并行算法主要體現(xiàn)在決策樹中的最優(yōu)拆分過程中的并行化處理：

   • 沿特征維度垂直劃分?jǐn)?shù)據(jù)集，使得不同機(jī)器具有不同的特征集合。（多機(jī)子）
   • 在本地?cái)?shù)據(jù)集中尋找最佳劃分點(diǎn)：(劃分特征，劃分閾值) 。
   • 將所有機(jī)器上的最佳劃分點(diǎn)整合，得到全局的最佳劃分點(diǎn)。
   • 利用全局最佳劃分點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行劃分，完成本次最優(yōu)拆分過程。

2. LightGBM?在特征并行上進(jìn)行了優(yōu)化，流程如下：

   • 每個(gè)機(jī)器都有全部樣本的全部特征集合。

   • 每個(gè)機(jī)器在本地?cái)?shù)據(jù)集中尋找最佳劃分點(diǎn)：(劃分特征，劃分閾值)?。

     但是不同的機(jī)器在不同的特征集上運(yùn)行。

   • 將所有機(jī)器上的最佳劃分點(diǎn)整合，得到全局的最佳劃分點(diǎn)。

   • 利用全局最佳劃分點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行劃分，完成本次最優(yōu)拆分過程。

3. LightGBM?不再沿特征維度垂直劃分?jǐn)?shù)據(jù)集，而是每個(gè)機(jī)器都有全部樣本的全部特征集合。這樣就節(jié)省了數(shù)據(jù)劃分的通信開銷。

   • 傳統(tǒng)的特征并行算法需要在每次最優(yōu)拆分中，對(duì)數(shù)據(jù)劃分并分配到每臺(tái)機(jī)器上。
   • LightGBM 特征并行算法只需要在程序開始時(shí)，將全量樣本拷貝到每個(gè)機(jī)器上。

   二者交換的數(shù)據(jù)相差不大，但是后者花費(fèi)的時(shí)間更少。

4. LightGBM?的特征并行算法在數(shù)據(jù)量很大時(shí)，仍然存在計(jì)算上的局限。因此建議在數(shù)據(jù)量很大時(shí)采用數(shù)據(jù)并行。

3.2.5.2 數(shù)據(jù)并行

1. 傳統(tǒng)的數(shù)據(jù)并行算法主要體現(xiàn)在決策樹的學(xué)習(xí)過程中的并行化處理：

   • 水平劃分?jǐn)?shù)據(jù)集，使得不同機(jī)器具有不同的樣本集合。
   • 以本地?cái)?shù)據(jù)集構(gòu)建本地直方圖
   • 將本地直方圖整合為全局直方圖
   • 在全局直方圖中尋找最佳劃分點(diǎn)。

2. LightGBM?在數(shù)據(jù)并行上進(jìn)行了優(yōu)化，流程如下：

   • LightGBM 使用Reduce scatter 的方式對(duì)不同機(jī)器上的不同特征進(jìn)行整合。每個(gè)機(jī)器從本地整合直方圖中尋找最佳劃分點(diǎn)，并同步到全局最佳劃分點(diǎn)中。
   • LightGBM 通過直方圖做差分加速。

20210113

案例

GBDT算法原理以及實(shí)例理解_Freemanzxp-CSDN博客_gbdt算法

gbdt詳解_kyle1314608的博客-CSDN博客_gbdt

重點(diǎn)

gbdt 的算法的流程？
gbdt 如何選擇特征 ？
gbdt 如何構(gòu)建特征 ？
gbdt 如何用于分類？
gbdt 通過什么方式減少誤差 ？
gbdt的效果相比于傳統(tǒng)的LR，SVM效果為什么好一些 ？
gbdt 如何加速訓(xùn)練？
gbdt的參數(shù)有哪些，如何調(diào)參 ？
gbdt 實(shí)戰(zhàn)當(dāng)中遇到的一些問題 ？
gbdt的優(yōu)缺點(diǎn) ？

機(jī)器學(xué)習(xí)算法GBDT - Alexander - 博客園

今天是周末，之前給自己定了一個(gè)小目標(biāo)：每周都要寫一篇博客，不管是關(guān)于什么內(nèi)容的都行，關(guān)鍵在于總結(jié)和思考，今天我選的主題是梯度提升樹的一些方法，主要從這些方法的原理以及實(shí)現(xiàn)過程入手講解這個(gè)問題。

本文按照這些方法出現(xiàn)的先后順序敘述。

GBDT

梯度提升樹實(shí)在提升樹的基礎(chǔ)上發(fā)展而來的一種使用范圍更廣的方法，當(dāng)處理回歸問題時(shí)，提升樹可以看作是梯度提升樹的特例(分類問題時(shí)是不是特例？)。 因?yàn)樘嵘龢湓跇?gòu)建樹每一步的過程中都是去擬合上一步獲得模型在訓(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通過對(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ā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)重都做了懲罰，避免過擬合
2. 類似于隨機(jī)森林，XGBoost在構(gòu)建樹的過程中，對(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)這種說法？ 因?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)建樹的過程中，也就是在分裂節(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ì)算分裂增益(不過這個(gè)缺點(diǎn)可以被近似算法所克服)

lightGBM

Features · microsoft/LightGBM Wiki · GitHub
關(guān)于lightGBM的論文目前并沒有放出來，只是從網(wǎng)上一些信息得出以下的一些與xgboost不同的地方：

• 3、max_depth[默認(rèn)6]

  表示樹的最大深度。也是用來避免過擬合的。當(dāng)它的值越大時(shí)，模型會(huì)學(xué)到更具體更局部的樣本，可能會(huì)導(dǎo)致過擬合。需要使用CV函數(shù)來進(jìn)行調(diào)優(yōu)。 典型值：3-10

  4、max_leaf_nodes

  表示樹上最大的節(jié)點(diǎn)或葉子的數(shù)量。可以替代max_depth的作用。因?yàn)槿绻傻氖嵌鏄?#xff0c;一個(gè)深度為n的樹最多生成n2個(gè)葉子。??

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

  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ù)來保存。
     -. 計(jì)算上的優(yōu)勢(shì)，預(yù)排序算法在選擇好分裂特征計(jì)算分裂收益時(shí)需要遍歷所有樣本的特征值，時(shí)間為(#data),而直方圖算法只需要遍歷桶就行了，時(shí)間為(#bin)

  3. 直方圖做差加速
     -. 一個(gè)子節(jié)點(diǎn)的直方圖可以通過父節(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說這種方法通訊開銷比較大，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，最后同步。??

  7. ??GBDT算法原理以及實(shí)例理解_Freemanzxp-CSDN博客_gbdt算法? gbdt原理和案例

  8. xgboost重要參數(shù)1_kyle1314608的博客-CSDN博客?xgboost 參數(shù)1

  9. ??xgboost重要參數(shù)2為主但不全要參照1_kyle1314608的博客-CSDN博客? ?xgboost 參數(shù)2

  • 3、max_depth[默認(rèn)6]

    表示樹的最大深度。也是用來避免過擬合的。當(dāng)它的值越大時(shí)，模型會(huì)學(xué)到更具體更局部的樣本，可能會(huì)導(dǎo)致過擬合。需要使用CV函數(shù)來進(jìn)行調(diào)優(yōu)。 典型值：3-10

    4、max_leaf_nodes

    表示樹上最大的節(jié)點(diǎn)或葉子的數(shù)量。可以替代max_depth的作用。因?yàn)槿绻傻氖嵌鏄?#xff0c;一個(gè)深度為n的樹最多生成n2個(gè)葉子。

  • 二者可以任選其一

總結(jié)

以上是生活随笔為你收集整理的梯度提升决策树（GBDT）与XGBoost、LightGBM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。