天天看點
傳回

提升方法：GBDT、XGBOOST、AdaBoost

提升 (boosting) 方法是一種常用的統計學習方法，應用廣泛且有效，在分類問題中，它通過改變訓練樣本的權重，學習多個分類器，并将這些分類器進行線性組合，提高分類器性能。

  • Table of Contents

    • GBDT
      • 提升的概念
      • 提升算法
      • 梯度提升決策樹 GBDT
    • XGBOOST
    • AdaBoost
      • 誤差分析
    • 參考文獻

GBDT

我們知道随機森林的決策樹分别采樣建立, 相對獨立。 那麼引來了如下思考 :

  • 假定目前一定得到了 
    提升方法：GBDT、XGBOOST、AdaBoost
     顆決策樹, 是否可以通過現有樣本和決策樹的資訊, 對第 
    提升方法：GBDT、XGBOOST、AdaBoost
     顆決策樹的建立産生有益的影響呢 ?
  • 各個決策樹組成随機森林後, 最後的投票過程可否在建立決策樹時即确定呢?

答案是肯定的，這也就是提升（boosting）的方法所解決的問題。

提升的概念

提升是一個機器學習技術, 可以用于回歸和分類問題, 它每一步産生一個弱預測模型(如決策樹), 并權重累加到總模型中，最終得帶一個強預測模型; 如果每一步的弱預測模型生成都是依據損失函數的梯度方向, 則稱之為梯度提升(Gradient boosting)。

提升的方法基于這樣一個思想：對于一個複雜任務來說，将多個專家的判斷進行适當的綜合所得出的判斷，要比其中任何一個專家單獨的判斷好。實際上，就是“三個臭皮匠頂個諸葛亮”的道理。

梯度提升算法首先給定一個目标損失函數, 它的定義域是所有可行的弱函數集合(基函數); 提升算法通過疊代的選擇一個負梯度方向上的基函數來逐漸逼近局部極小值。這種在函數域的梯度提升觀點對機器學習的很多領域有深刻影響。

梯度提升算法實際上和梯度下降算法是一樣的，隻不過看問題的角度不同，比如線上性回歸中，我們通過梯度下降來優化參數 

提升方法：GBDT、XGBOOST、AdaBoost

 ，使損失函數能達到（局部）最小值；如果我們換個角度，我們優化的不是 

提升方法：GBDT、XGBOOST、AdaBoost

，而是 

提升方法：GBDT、XGBOOST、AdaBoost

 這個函數，再通過沿梯度方向下降的方法達到損失函數（局部）最小值，就變成了梯度提升算法。

提升算法

給定輸入向量 

提升方法：GBDT、XGBOOST、AdaBoost

 和輸出變量 

提升方法：GBDT、XGBOOST、AdaBoost

 組成的若幹訓練樣本 

提升方法：GBDT、XGBOOST、AdaBoost

 , 目标是找到近似函數 

提升方法：GBDT、XGBOOST、AdaBoost

 , 使得損失函數 

提升方法：GBDT、XGBOOST、AdaBoost

 的損失值最小。

損失函數 

提升方法：GBDT、XGBOOST、AdaBoost

 的定義不唯一，典型定義有以下兩種：

  • 提升方法：GBDT、XGBOOST、AdaBoost
    ，這個定義其實預設誤差服從高斯分布
  • 提升方法：GBDT、XGBOOST、AdaBoost
    ，這個定義則認為誤差服從Laplace（雙指數）分布

假設最優解為 

提升方法：GBDT、XGBOOST、AdaBoost

，則：

提升方法：GBDT、XGBOOST、AdaBoost

該式的意思就是使損失函數期望風險最小化的參數 

提升方法：GBDT、XGBOOST、AdaBoost

 為最優解 

提升方法：GBDT、XGBOOST、AdaBoost

。

我們知道任何函數都可以被分解為一族基函數的線性組合，比如傅立葉分解可以把任何函數分解為三角函數的線性組合，是以這裡的 

提升方法：GBDT、XGBOOST、AdaBoost

 也不例外，我們假設它是一族基函數 

提升方法：GBDT、XGBOOST、AdaBoost

 的線性組合，即： 

提升方法：GBDT、XGBOOST、AdaBoost

算法推導

我們使用梯度提升方法尋找最優解 

提升方法：GBDT、XGBOOST、AdaBoost

, 使得損失函數在訓練集上的期望最小。方法如下:

  • 首先, 令 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，求常系數 
    提升方法：GBDT、XGBOOST、AdaBoost
     : 
    提升方法：GBDT、XGBOOST、AdaBoost
    • 若損失函數采用平方定義，上式可以解得：
      提升方法：GBDT、XGBOOST、AdaBoost
    • 若損失函數采用絕對值定義，則解 
      提升方法：GBDT、XGBOOST、AdaBoost
       為 
      提升方法：GBDT、XGBOOST、AdaBoost
       的中位數
  • 知道 
    提升方法：GBDT、XGBOOST、AdaBoost
     之後，接下來用遞推的思路來想，如果已知 
    提升方法：GBDT、XGBOOST、AdaBoost
     ，如何求 
    提升方法：GBDT、XGBOOST、AdaBoost
     ？于是得到下面的公式： 
    提升方法：GBDT、XGBOOST、AdaBoost
  • 我們可以用梯度下降的方法近似計算上式。若使 
    提升方法：GBDT、XGBOOST、AdaBoost
     取得最小值，我們可以對 
    提升方法：GBDT、XGBOOST、AdaBoost
     求偏導求出梯度，然後沿負梯度方向下降一個步長 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，由于這個步長可以通過線性搜尋求出最優值，是以該步長與負梯度的乘積可以近似為上式的最小值，于是得到如下的更新公式： 
    提升方法：GBDT、XGBOOST、AdaBoost

提升算法

  1. 初始給定模型為常數 
    提升方法：GBDT、XGBOOST、AdaBoost
  2. 對于 
    提升方法：GBDT、XGBOOST、AdaBoost
     到 
    提升方法：GBDT、XGBOOST、AdaBoost
    1. 計算僞殘差 (pseudo residuals) 
      提升方法：GBDT、XGBOOST、AdaBoost
      提升方法：GBDT、XGBOOST、AdaBoost
    2. 使用資料 
      提升方法：GBDT、XGBOOST、AdaBoost
       訓練拟合殘差的基函數 
      提升方法：GBDT、XGBOOST、AdaBoost
       （比如一棵決策樹）
    3. 計算步長 
      提升方法：GBDT、XGBOOST、AdaBoost
      • 一維優化問題
    4. 更新模型：
      提升方法：GBDT、XGBOOST、AdaBoost

梯度提升決策樹 GBDT

在提升算法中，如果基函數選擇的是決策樹，那麼算法又叫梯度提升決策樹，也就是GBDT。

GBDT

  • 在第 
    提升方法：GBDT、XGBOOST、AdaBoost
     步的梯度提升是根據僞殘差資料計算決策樹 
    提升方法：GBDT、XGBOOST、AdaBoost
    。
  • 令樹 
    提升方法：GBDT、XGBOOST、AdaBoost
     的葉節點數目為 
    提升方法：GBDT、XGBOOST、AdaBoost
    , 即樹 
    提升方法：GBDT、XGBOOST、AdaBoost
     将輸入空間劃分為 
    提升方法：GBDT、XGBOOST、AdaBoost
     個不相交區域
    提升方法：GBDT、XGBOOST、AdaBoost
     ,并且決策樹 
    提升方法：GBDT、XGBOOST、AdaBoost
     可以在每個區域中給出某個類型的确定性預測。使用訓示記号 
    提升方法：GBDT、XGBOOST、AdaBoost
    , 對于輸入 
    提升方法：GBDT、XGBOOST、AdaBoost
    , 
    提升方法：GBDT、XGBOOST、AdaBoost
     為: 
    提升方法：GBDT、XGBOOST、AdaBoost
  • 其中，
    提升方法：GBDT、XGBOOST、AdaBoost
     是樣本 
    提升方法：GBDT、XGBOOST、AdaBoost
     在區域 
    提升方法：GBDT、XGBOOST、AdaBoost
     的預測值，
    提升方法：GBDT、XGBOOST、AdaBoost
  • 使用線性搜尋計算學習率,最小化損失函樹
    • 提升方法：GBDT、XGBOOST、AdaBoost
    • 提升方法：GBDT、XGBOOST、AdaBoost
  • 進一步：對樹的每個區域分别計算步長，進而系數 
    提升方法：GBDT、XGBOOST、AdaBoost
     被合并到步長中，進而: 
    • 提升方法：GBDT、XGBOOST、AdaBoost
    • 提升方法：GBDT、XGBOOST、AdaBoost

參數設定和正則化

對訓練集拟合過高會降低模型的泛化能力, 需要使用正則化技術來降低過拟合。

  • 對複雜模型增加懲罰項, 如 : 模型複雜度正比于葉結點數目或者葉結點預測值的平方和等
  • 用決策樹剪枝
  • 葉結點數目控制了樹的層數, 一般選擇 
    提升方法：GBDT、XGBOOST、AdaBoost
  • 葉結點包含的最少樣本數目 
    • 防止出現過小的葉結點, 降低預測方差
  • 梯度提升疊代次數 
    提升方法：GBDT、XGBOOST、AdaBoost
     : 
    • 增加 
      提升方法：GBDT、XGBOOST、AdaBoost
       可降低訓練集的損失值, 但有過拟合風險
    • 交叉驗證

GBDT總結

  • 函數估計本來被認為是在函數空間而非參數空間的數值優化問題，而階段性的加性擴充和梯度下降手段将函數估計轉換成參數估計。
  • 損失函數是最小平方誤差、絕對值誤差等，則為回歸問題；而誤差函數換成多類别Logistic似然函數，則成為分類問題。
  • 對目标函數分解成若幹基函數的權重和，是常見的技術手段：神經網絡、徑向基函數、傅立葉/小波變換、SVM都可以看到它的影子。

XGBOOST

提升方法：GBDT、XGBOOST、AdaBoost

普通提升算法包括GBDT在計算上式實采用的是梯度提升，也就是隻用了一階導數資訊，如果常識二階導數的資訊呢？

目标函數：

提升方法：GBDT、XGBOOST、AdaBoost

其中，

提升方法：GBDT、XGBOOST、AdaBoost

 為正則項，

提升方法：GBDT、XGBOOST、AdaBoost

 為常數，目的是要求出使目标函數最小的 

提升方法：GBDT、XGBOOST、AdaBoost

。

二階Taylor展式： 
提升方法：GBDT、XGBOOST、AdaBoost

令： 

提升方法：GBDT、XGBOOST、AdaBoost

對 

提升方法：GBDT、XGBOOST、AdaBoost

 二階Taylor展開并省略高階無窮小得：

提升方法：GBDT、XGBOOST、AdaBoost
決策樹的描述
  • 使用決策樹對樣本做分類(回歸)，是從根結點到葉節點的細化過程；落在相同葉節點的樣本的預測值是相同的
  • 假定某決策樹的葉結點數目為 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，每個葉結點的權值為 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，決策樹的學習過程，就是構造如何使用特征得到劃分，進而得到這些權值的過程。葉權值就是這個葉節點的預測結果，若是分類問題，也就是這類樣本的标簽。
  • 樣本 
    提升方法：GBDT、XGBOOST、AdaBoost
     落在葉結點 
    提升方法：GBDT、XGBOOST、AdaBoost
     中，定義描述決策樹函數為: 
    提升方法：GBDT、XGBOOST、AdaBoost
    • 一個決策樹的核心即“樹結構”和“葉權值”

決策樹的複雜度可考慮葉結點數和葉權值，如使用葉結點總數和葉權值平方和的權重： 

提升方法：GBDT、XGBOOST、AdaBoost

其中，

提升方法：GBDT、XGBOOST、AdaBoost

 為葉子的個數。

我們繼續來推導目标函數 

提升方法：GBDT、XGBOOST、AdaBoost

：

提升方法：GBDT、XGBOOST、AdaBoost

令 

提升方法：GBDT、XGBOOST、AdaBoost

，

提升方法：GBDT、XGBOOST、AdaBoost

，進而： 

提升方法：GBDT、XGBOOST、AdaBoost

對 

提升方法：GBDT、XGBOOST、AdaBoost

 求偏導得： 

提升方法：GBDT、XGBOOST、AdaBoost

令 

提升方法：GBDT、XGBOOST、AdaBoost

，得： 

提升方法：GBDT、XGBOOST、AdaBoost

回代入目标函數得： 

提升方法：GBDT、XGBOOST、AdaBoost

這就是目标函數最後的結果，值越小代表決策樹的結構越好。

我們要建構一顆決策樹 

提升方法：GBDT、XGBOOST、AdaBoost

，使目标函數 

提升方法：GBDT、XGBOOST、AdaBoost

 達到最小，建構時可借鑒ID3/C4.5/CART的做法：

  • 如何進行子樹劃分？ 
    • 對于某可行劃分, 計算劃分後的 
      提升方法：GBDT、XGBOOST、AdaBoost
    • 對于所有可行劃分, 選擇 
      提升方法：GBDT、XGBOOST、AdaBoost
       降低最小的分割點
  • 枚舉可行的分割點, 選擇增益最大的劃分, 繼續同樣的操作, 直到滿足某門檻值或得到純節點 
    • 提升方法：GBDT、XGBOOST、AdaBoost
提升方法：GBDT、XGBOOST、AdaBoost

XGBOOST總結

  • XGBOOST 與 GBDT 的差別在于更新模型的方法不同，其餘都是一樣的
  • 相對于傳統的GBDT，XGBoost使用了二階資訊，可以更快的在訓練集上收斂
  • 由于“随機森林族”本身具備防止過拟合的優勢，是以XGBoost仍然一定程度的具有該特性
  • XGBoost的實作中使用了并行/多核計算, 是以訓練速度快; 同時它的原生語言為C/C++, 這是它速度快的實踐原因

AdaBoost

思考：如果對GBDT的基函數的學習中，不止考慮函數的參數和權值，而是對樣本本身也權重，會得到什麼結果呢？這其實就是Adaboost的思想。

AdaBoost算法

  • 設訓練資料集 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，初始化訓練資料的權值分布 
    提升方法：GBDT、XGBOOST、AdaBoost
    , 
    提升方法：GBDT、XGBOOST、AdaBoost
    , 
    提升方法：GBDT、XGBOOST、AdaBoost
    。
  • 對于 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，
    提升方法：GBDT、XGBOOST、AdaBoost
     為樹的棵數:
    • 使用具有權值分布 
      提升方法：GBDT、XGBOOST、AdaBoost
       的訓練資料集學習, 得到基本分類器 
      提升方法：GBDT、XGBOOST、AdaBoost
    • 計算 
      提升方法：GBDT、XGBOOST、AdaBoost
       在訓練資料集上的分類誤差率: 
      提升方法：GBDT、XGBOOST、AdaBoost
    • 計算 
      提升方法：GBDT、XGBOOST、AdaBoost
       的系數 
      提升方法：GBDT、XGBOOST、AdaBoost
    • 更新訓練資料集的權值分布 
      提升方法：GBDT、XGBOOST、AdaBoost
      提升方法：GBDT、XGBOOST、AdaBoost
    • 這裡，
      提升方法：GBDT、XGBOOST、AdaBoost
       是歸一化因子： 
      提升方法：GBDT、XGBOOST、AdaBoost
    • 它使 
      提升方法：GBDT、XGBOOST、AdaBoost
       成為一個機率分布（和為1）。
  • 建構基本分類器的線性組合 
    提升方法：GBDT、XGBOOST、AdaBoost
  • 得到最終分類器： 
    提升方法：GBDT、XGBOOST、AdaBoost

算法解釋

我們先分析 

提升方法：GBDT、XGBOOST、AdaBoost

 的系數：

提升方法：GBDT、XGBOOST、AdaBoost

，這裡的 

提升方法：GBDT、XGBOOST、AdaBoost

 是分類錯誤率。 

這個式子實作了這麼一個理論：如果一個分類器的分類錯誤率超過50%，那麼這個分類器還不如随機分類（預設均勻分布，随機分50%錯誤率）來得好，把這個分類器直接反轉效果反而會更好。

  • 如果 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，則 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，是以 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，可以得到 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，即：
    提升方法：GBDT、XGBOOST、AdaBoost
    ，說明如果這個分類器的錯誤率小于0.5則權值為正，表示可以參考這個分類器的結果，并且錯誤率越低分類器的權值越大；
  • 如果 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，則 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，是以 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，可以得到 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，即：
    提升方法：GBDT、XGBOOST、AdaBoost
    ，就相當于把分類器反轉。

再來看權值更新公式，

提升方法：GBDT、XGBOOST、AdaBoost
  • 先看指數上的一小部分 : 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，其中 
    提升方法：GBDT、XGBOOST、AdaBoost
     為該分類器的權值，
    提升方法：GBDT、XGBOOST、AdaBoost
     為第 
    提升方法：GBDT、XGBOOST、AdaBoost
     個樣本的實際類别且 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，
    提升方法：GBDT、XGBOOST、AdaBoost
     為預測類别。 
    • 若預測類别與實際類别一緻，則 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，反之則 
      提升方法：GBDT、XGBOOST、AdaBoost
    • 如果該分類器比較靠譜的話（
      提升方法：GBDT、XGBOOST、AdaBoost
      ），
      提升方法：GBDT、XGBOOST、AdaBoost
       是個正數，反之是個負數。
    • 綜合起來看：如果靠譜的分類器預測錯了（或者不靠譜的分類器預測對了），則 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，反之則 
      提升方法：GBDT、XGBOOST、AdaBoost
  • 提升方法：GBDT、XGBOOST、AdaBoost
     是用來歸一化的，不用看，把其他部分合起來：
    • 如果 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，則 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，進而得到 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，即權值增加。
    • 如果 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，則 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，進而得到 
      提升方法：GBDT、XGBOOST、AdaBoost
      ，即權值降低。
  • 結論：如果分類器預測錯了則增加該樣本的權值，在下次分類時重點關注該樣本；如果分類正确則降低該樣本的權值，在下次分類時弱化該樣本。也就是樣本的權值動态變化，如下圖所示：
提升方法：GBDT、XGBOOST、AdaBoost

誤差分析

AdaBoost算法最終的誤差界為：

提升方法：GBDT、XGBOOST、AdaBoost

證明

  • 前半部分：當 
    提升方法：GBDT、XGBOOST、AdaBoost
     時，
    提升方法：GBDT、XGBOOST、AdaBoost
    ，因而 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，而 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，是以 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，前半部分得證。 
  • 後半部分：
    • 由 
      提升方法：GBDT、XGBOOST、AdaBoost
       的定義式得：
      提升方法：GBDT、XGBOOST、AdaBoost
      提升方法：GBDT、XGBOOST、AdaBoost
    • 後半部分得證

這一結果說明，可以在每一輪選取适當的 

提升方法：GBDT、XGBOOST、AdaBoost

 使得 

提升方法：GBDT、XGBOOST、AdaBoost

 最小，進而使訓練誤差下降最快。

訓練誤差界

提升方法：GBDT、XGBOOST、AdaBoost

因為 

提升方法：GBDT、XGBOOST、AdaBoost

，

提升方法：GBDT、XGBOOST、AdaBoost

，

提升方法：GBDT、XGBOOST、AdaBoost

是以 

提升方法：GBDT、XGBOOST、AdaBoost

其中，

提升方法：GBDT、XGBOOST、AdaBoost

。

由此得到： 

提升方法：GBDT、XGBOOST、AdaBoost

取 

提升方法：GBDT、XGBOOST、AdaBoost

 的最小值，記為 

提升方法：GBDT、XGBOOST、AdaBoost

， 

則有： 

提升方法：GBDT、XGBOOST、AdaBoost

這表明AdaBoost訓練誤差是以指數速率下降的！

AdaBoost總結

  • AdaBoost算法可以看做是采用指數損失函數的提升方法，其每個基函數的學習算法為前向分步算法
  • AdaBoost的訓練誤差是以指數速率下降的
  • AdaBoost算法不需要事先知道下界 
    提升方法：GBDT、XGBOOST、AdaBoost
    ，具有自适應性(Adaptive)，它能自适應弱分類器的訓練誤差率

參考文獻

  • 李航，統計學習方法，清華大學出版社，2012
  • Jerome H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine. February 1999

轉載自：https://www.liuhe.website/index.php?/Articles/single/50

boost machine learning 機器學習
上一篇: vue路由$router.push傳遞Date對象
下一篇: vue + ElementUI實作表格的添加行、删除行

繼續閱讀