集成學習需要理解的一些內容

• 2019 年 12 月 13 日
• 筆記

本系列為深入篇，儘可能完善專題知識，並不會所有的都會出現在面試中，更多內容，詳見：Reflection_Summary，歡迎交流。

另外，歡迎大家關注我的個人bolg，知乎，更多程式碼內容歡迎follow我的個人Github，如果有任何演算法、程式碼疑問都歡迎通過郵箱發消息給我。

介紹一下Boosting的思想？

• 初始化訓練一個弱學習器，初始化下的各條樣本的權重一致
• 根據上一個弱學習器的結果，調整權重，使得錯分的樣本的權重變得更高
• 基於調整後的樣本及樣本權重訓練下一個弱學習器
• 預測時直接串聯綜合各學習器的加權結果

最小二乘回歸樹的切分過程是怎麼樣的？

• 回歸樹在每個切分後的結點上都會有一個預測值，這個預測值就是結點上所有值的均值
• 分枝時遍歷所有的屬性進行二叉劃分，挑選使平方誤差最小的劃分屬性作為本節點的劃分屬性
• 屬性上有多個值，則需要遍歷所有可能的屬性值，挑選使平方誤差最小的劃分屬性值作為本屬性的劃分值
• 遞歸重複以上步驟，直到滿足葉子結點上值的要求

有哪些直接利用了Boosting思想的樹模型？

adaboost，gbdt等等

gbdt和boostingtree的boosting分別體現在哪裡？

• boostingtree利用基模型學習器，擬合的是當前模型與標籤值的殘差
• gbdt利用基模型學習器，擬合的是當前模型與標籤值的殘差的負梯度

gbdt的中的tree是什麼tree？有什麼特徵？

Cart tree，但是都是回歸樹

常用回歸問題的損失函數？

• mse:

image

• 負梯度：y-h(x)
• 初始模型F0由目標變數的平均值給出

• 絕對損失:

image

• 負梯度：sign(y-h(x))
• 初始模型F0由目標變數的中值給出

• Huber損失：mse和絕對損失的結合
  • 負梯度：y-h(x)和sign(y-h(x))分段函數
  • 它是MSE和絕對損失的組合形式，對於遠離中心的異常點，採用絕對損失，其他的點採用MSE，這個界限一般用分位數點度量

常用分類問題的損失函數？

• 對數似然損失函數
  • 二元且標籤y屬於{-1,+1}：?(?,?(?))=???(1+???(−??(?)))
    • 負梯度：y/(1+???(−??(?)))
  • 多元：

  

  image

• 指數損失函數:?(?,?(?))=???(−??(?))
  • 負梯度：y·???(−??(?)) 除了負梯度計算和葉子節點的最佳負梯度擬合的線性搜索，多元GBDT分類和二元GBDT分類以及GBDT回歸演算法過程相同

什麼是gbdt中的殘差的負梯度？

image

當loss函數為均方誤差

image

，gbdt中的殘差的負梯度的結果y-H(x)正好與boostingtree的擬合殘差一致

如何用損失函數的負梯度實現gbdt？

• 利用

image 可以計算得到x對應的損失函數的負梯度

image ,據此我們可以構造出第t棵回歸樹，其對應的葉子結點區域

image j為葉子結點位置

• 構建回歸樹的過程中，需要考慮找到特徵A中最合適的切分點，使得切分後的數據集D1和D2的均方誤差最小

image

• 針對每一個葉子節點裡的樣本，我們求出使損失函數最小，也就是擬合葉子節點最好的輸出值???,

image

• 首先，根據feature切分後的損失均方差大小，選取最優的特徵切分
• 其次，根據選定的feature切分後的葉子結點數據集，選取最使損失函數最小，也就是擬合葉子節點最好的輸出值
• 這樣就完整的構造出一棵樹：

image

• 本輪最終得到的強學習器的表達式如下：

image

擬合損失函數的負梯度為什麼是可行的？

• 泰勒展開的一階形式：

image

• m輪樹模型可以寫成：

image

• 對

image 進行泰勒展開：

image ,其中m-1輪對殘差梯度為

image

• 我們擬合了殘差的負梯度，

image ,所以

image 內會讓損失向下降對方向前進

即便擬合損失函數負梯度是可行的，為什麼不直接擬合殘差？ 擬合負梯度好在哪裡？

• 前者不用殘差的負梯度而是使用殘差，是全局最優值，後者使用的是 局部最優方向（負梯度）*步長（?）
• 依賴殘差進行優化，損失函數一般固定為反映殘差的均方差損失函數，因此 當均方差損失函數失效（該損失函數對異常值敏感）的時候，換了其他一般的損失函數，便很難得到優化的結果。同時，因為損失函數的問題，Boosting Tree也很難處理回歸之外問題。 而後者使用梯度下降的方法，對於任意可以求導的損失函數它都可以處理

Shrinkage收縮的作用？

每次走一小步逐漸逼近結果的效果，要比每次邁一大步很快逼近結果的方式更容易得到精確值，即它不完全信任每一棵殘差樹，認為每棵樹只學到了真理的一部分累加的時候只累加了一小部分多學幾棵樹來彌補不足。 這個技巧類似於梯度下降里的學習率

• 原始：

image

• Shrinkage：

image

feature屬性會被重複多次使用么？

會，同時因為特徵會進行多次使用，特徵用的越多，則該特徵的重要性越大

gbdt如何進行正則化的？

• 子取樣
  • 每一棵樹基於原始原本的一個子集進行訓練
  • rf是有放回取樣，gbdt是無放回取樣
  • 特徵子取樣可以來控制模型整體的方差
• 利用Shrinkage收縮，控制每一棵子樹的貢獻度
• 每棵Cart樹的枝剪

為什麼集成演算法大多使用樹類模型作為基學習器？或者說，為什麼集成學習可以在樹類模型上取得成功？

• 對數據的要求比較低，不需要強假設，不需要數據預處理，連續離散都可以，缺失值也能接受
• bagging，關注於提升分類器的泛化能力
• boosting，關注於提升分類器的精度

gbdt的優缺點？

優點：

• 數據要求比較低，不需要前提假設，能處理缺失值，連續值，離散值
• 使用一些健壯的損失函數，對異常值的魯棒性非常強
• 調參相對較簡單

缺點：

• 並行化能力差

gbdt和randomforest區別？

• 相同：
  • 都是多棵樹的組合
• 不同：
  • RF每次迭代的樣本是從全部訓練集中有放回抽樣形成的，而GBDT每次使用全部樣本
  • gbdt對異常值比rf更加敏感
  • gbdt是串列，rf是並行
  • gbdt是cart回歸樹，rf是cart分類回歸樹都可以
  • gbdt是提高降低偏差提高性能，rf是通過降低方差提高性能
  • gbdt對輸出值是進行加權求和，rf對輸出值是進行投票或者平均

GBDT和LR的差異？

• 從決策邊界來說，線性回歸的決策邊界是一條直線，邏輯回歸的決策邊界是一條曲線，而GBDT的決策邊界可能是很多條線
• 當在高維稀疏特徵的場景下，LR的效果一般會比GBDT好。因為LR有參數懲罰，GBDT容易造成過擬合

XGboost缺點

• 每輪迭代時，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進記憶體則會限制訓練數據的大小；如果不裝進記憶體，反覆地讀寫訓練數據又會消耗非常大的時間
• 預排序方法需要保存特徵值，及特徵排序後的索引結果，佔用空間
• level-wise，在訓練的時候哪怕新增的分裂點對loss增益沒有提升也會先達到預定的層數

LightGBM對Xgboost的優化

• 將連續的浮點特徵離散成k個離散值，具體過程是首先確定對於每一個特徵需要多少的桶bin，然後均分，將屬於該桶的樣本數據更新為bin的值，最後用直方圖表示。在進行特徵選擇時，只需要根據直方圖的離散值，遍歷尋找最優的分割點
  • 優點：時間開銷由O(features)降低到O(bins)
  • 缺點：很多數據精度被丟失，相當於用了正則
• 利用leaf-wise代替level-wise
  • 每次從當前所有葉子中找到分裂增益最大（一般也是數據量最大）的一個葉子，然後分裂，如此循環
• 直方圖做差加速

LightGBM亮點

• 單邊梯度取樣 Gradient-based One-Side Sampling (GOSS)：排除大部分小梯度的樣本，僅用剩下的樣本計算損失增益
• 互斥稀疏特徵綁定Exclusive Feature Bundling (EFB)：從減少特徵角度，把儘可能互斥的特徵進行合併，比如特徵A[0,10],特徵B[0,20],可以把B+10後與A合併，得到新特徵A+B[0,30]

xgboost對比gbdt/boosting Tree有了哪些方向上的優化？

• 顯示的把樹模型複雜度作為正則項加到優化目標中
• 優化目標計算中用到二階泰勒展開代替一階，更加準確
• 實現了分裂點尋找近似演算法
  • 暴力枚舉
  • 近似演算法（分桶）
• 更加高效和快速
  • 數據事先排序並且以block形式存儲，有利於並行計算
  • 基於分散式通訊框架rabit，可以運行在MPI和yarn上
  • 實現做了面向體系結構的優化，針對cache和記憶體做了性能優化

xgboost和gbdt的區別？

• 模型優化上：
  • 基模型的優化：
    • gbdt用的是cart回歸樹作為基模型，xgboost還可以用線性模型，加上天生的正則項，就是帶L1和L2邏輯回歸(分類)和線性回歸(回歸)
  • 損失函數上的優化：
    • gbdt對loss是泰勒一階展開，xgboost是泰勒二階展開
    • gbdt沒有在loss中帶入結點個數和預測值的正則項
  • 特徵選擇上的優化：
    • 實現了一種分裂節點尋找的近似演算法，用於加速和減小記憶體消耗，而不是gbdt的暴力搜索
    • 節點分裂演算法解決了缺失值方向的問題，gbdt則是沿用了cart的方法進行加權
  • 正則化的優化：
    • 特徵取樣
    • 樣本取樣
• 工程優化上：
  • xgboost在對特徵進行了分block預排序，使得在做特徵分裂的時候，最終選增益最大的那個特徵去做分裂，那麼各個特徵的增益計算就可以開多執行緒進行
  • cache-aware, out-of-core computation
  • 支援分散式計算可以運行在MPI，YARN上，得益於底層支援容錯的分散式通訊框架rabit

xgboost優化目標/損失函數改變成什麼樣？

• 原始：

image

image 為泰勒一階展開，

image

• 改變：

image

• J為葉子結點的個數，

image 為第j個葉子結點中的最優值

image 為泰勒二階展開，

image

xgboost如何使用MAE或MAPE作為目標函數？

MAE:

image

MAPE:

image

• 利用可導的函數逼近MAE或MAPE
  • mse
  • Huber loss
  • Pseudo-Huber loss

xgboost如何尋找分裂節點的候選集？

• 暴力枚舉
  • 法嘗試所有特徵和所有分裂位置，從而求得最優分裂點。當樣本太大且特徵為連續值時，這種暴力做法的計算量太大
• 近似演算法（approx）
  • 近似演算法尋找最優分裂點時不會枚舉所有的特徵值，而是對特徵值進行聚合統計，然後形成若干個桶。然後僅僅將桶邊界上的特徵的值作為分裂點的候選，從而獲取計算性能的提升
    • 離散值直接分桶
    • 連續值分位數分桶

xgboost如何處理缺失值？

• 訓練時：缺失值數據會被分到左子樹和右子樹分別計算損失，選擇較優的那一個
• 預測時：如果訓練中沒有數據缺失，預測時出現了數據缺失，那麼默認被分類到右子樹

xgboost在計算速度上有了哪些點上提升？

• 特徵預排序
  • 按特徵進行存儲，每一個block代表一個特徵的值，樣本在該block中按照它在該特徵的值排好序。這些block只需要在程式開始的時候計算一次，後續排序只需要線性掃描這些block即可
  • block可以僅存放樣本的索引，而不是樣本本身，這樣節省了大量的存儲空間

xgboost特徵重要性是如何得到的？

• 』weight『：代表著某個特徵被選作分裂結點的次數；
• 』gain『：使用該特徵作為分類結點的資訊增益；
• 』cover『：某特徵作為劃分結點，覆蓋樣本總數的平均值；

XGBoost中如何對樹進行剪枝？

• 在目標函數中增加了正則項：葉子結點樹+葉子結點權重的L2模的平方
• 在結點分裂時，定義了一個閾值，如果分裂後目標函數的增益小於該閾值，則不分裂
• 當引入一次分裂後，重新計算新生成的左、右兩個葉子結點的樣本權重和。如果任一個葉子結點的樣本權重低於某一個閾值（最小樣本權重和），也會放棄此次分裂
• XGBoost 先從頂到底建立樹直到最大深度，再從底到頂反向檢查是否有不滿足分裂條件的結點，進行剪枝

XGBoost模型如果過擬合了怎麼解決？

• 直接修改模型：
  • 降低樹的深度
  • 增大葉子結點的權重
  • 增大懲罰係數
• subsample的力度變大，降低異常點的影響
• 減小learning rate，提高estimator

xgboost如何調參數？

• 先確定learningrate和estimator
• 再確定每棵樹的基本資訊，max_depth和 min_child_weight
• 再確定全局資訊：比如最小分裂增益，子取樣參數，正則參數
• 重新降低learningrate，得到最優解