本系列為深入篇，盡可能完善專(zhuān)題知識(shí)，并不會(huì)所有的都會(huì)出現(xiàn)在面試中，更多內(nèi)容，詳見(jiàn)：Reflection_Summary，歡迎交流。

另外，歡迎大家關(guān)注我的個(gè)人bolg，知乎，更多代碼內(nèi)容歡迎follow我的個(gè)人Github，如果有任何算法、代碼疑問(wèn)都?xì)g迎通過(guò)郵箱發(fā)消息給我。

介紹一下Boosting的思想？

• 初始化訓(xùn)練一個(gè)弱學(xué)習(xí)器，初始化下的各條樣本的權(quán)重一致
• 根據(jù)上一個(gè)弱學(xué)習(xí)器的結(jié)果，調(diào)整權(quán)重，使得錯(cuò)分的樣本的權(quán)重變得更高
• 基于調(diào)整后的樣本及樣本權(quán)重訓(xùn)練下一個(gè)弱學(xué)習(xí)器
• 預(yù)測(cè)時(shí)直接串聯(lián)綜合各學(xué)習(xí)器的加權(quán)結(jié)果

最小二乘回歸樹(shù)的切分過(guò)程是怎么樣的？

• 回歸樹(shù)在每個(gè)切分后的結(jié)點(diǎn)上都會(huì)有一個(gè)預(yù)測(cè)值，這個(gè)預(yù)測(cè)值就是結(jié)點(diǎn)上所有值的均值
• 分枝時(shí)遍歷所有的屬性進(jìn)行二叉劃分，挑選使平方誤差最小的劃分屬性作為本節(jié)點(diǎn)的劃分屬性
• 屬性上有多個(gè)值，則需要遍歷所有可能的屬性值，挑選使平方誤差最小的劃分屬性值作為本屬性的劃分值
• 遞歸重復(fù)以上步驟，直到滿足葉子結(jié)點(diǎn)上值的要求

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

adaboost，gbdt等等

gbdt和boostingtree的boosting分別體現(xiàn)在哪里？

• boostingtree利用基模型學(xué)習(xí)器，擬合的是當(dāng)前模型與標(biāo)簽值的殘差
• gbdt利用基模型學(xué)習(xí)器，擬合的是當(dāng)前模型與標(biāo)簽值的殘差的負(fù)梯度

gbdt的中的tree是什么tree？有什么特征？

Cart tree，但是都是回歸樹(shù)

常用回歸問(wèn)題的損失函數(shù)？

• mse:
  image
  • 負(fù)梯度：y-h(x)
  • 初始模型F0由目標(biāo)變量的平均值給出

• 絕對(duì)損失:
  image
  • 負(fù)梯度：sign(y-h(x))
  • 初始模型F0由目標(biāo)變量的中值給出
• Huber損失：mse和絕對(duì)損失的結(jié)合
  • 負(fù)梯度：y-h(x)和sign(y-h(x))分段函數(shù)
  • 它是MSE和絕對(duì)損失的組合形式，對(duì)于遠(yuǎn)離中心的異常點(diǎn)，采用絕對(duì)損失，其他的點(diǎn)采用MSE，這個(gè)界限一般用分位數(shù)點(diǎn)度量

常用分類(lèi)問(wèn)題的損失函數(shù)？

• 對(duì)數(shù)似然損失函數(shù)
  • 二元且標(biāo)簽y屬于{-1,+1}：??(??,??(??))=??????(1+??????(?????(??)))
    • 負(fù)梯度：y/(1+??????(?????(??)))

  • 多元：
    image
• 指數(shù)損失函數(shù):??(??,??(??))=??????(?????(??))
  • 負(fù)梯度：y·??????(?????(??))
    除了負(fù)梯度計(jì)算和葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合的線性搜索，多元GBDT分類(lèi)和二元GBDT分類(lèi)以及GBDT回歸算法過(guò)程相同

什么是gbdt中的殘差的負(fù)梯度？

image

image

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

如何用損失函數(shù)的負(fù)梯度實(shí)現(xiàn)gbdt？

• 利用
  image
  可以計(jì)算得到x對(duì)應(yīng)的損失函數(shù)的負(fù)梯度
  image
  ,據(jù)此我們可以構(gòu)造出第t棵回歸樹(shù)，其對(duì)應(yīng)的葉子結(jié)點(diǎn)區(qū)域
  image
  j為葉子結(jié)點(diǎn)位置

• 構(gòu)建回歸樹(shù)的過(guò)程中，需要考慮找到特征A中最合適的切分點(diǎn)，使得切分后的數(shù)據(jù)集D1和D2的均方誤差最小
  image

• 針對(duì)每一個(gè)葉子節(jié)點(diǎn)里的樣本，我們求出使損失函數(shù)最小，也就是擬合葉子節(jié)點(diǎn)最好的輸出值??????,
  image
  • 首先，根據(jù)feature切分后的損失均方差大小，選取最優(yōu)的特征切分
  • 其次，根據(jù)選定的feature切分后的葉子結(jié)點(diǎn)數(shù)據(jù)集，選取最使損失函數(shù)最小，也就是擬合葉子節(jié)點(diǎn)最好的輸出值

  • 這樣就完整的構(gòu)造出一棵樹(shù)：
    image

• 本輪最終得到的強(qiáng)學(xué)習(xí)器的表達(dá)式如下：
  image

擬合損失函數(shù)的負(fù)梯度為什么是可行的？

• 泰勒展開(kāi)的一階形式：
  image

• m輪樹(shù)模型可以寫(xiě)成：
  image

  • 對(duì)
    image
    進(jìn)行泰勒展開(kāi)：
    image
    ,其中m-1輪對(duì)殘差梯度為
    image

• 我們擬合了殘差的負(fù)梯度，
  image
  ,所以
  image
  內(nèi)會(huì)讓損失向下降對(duì)方向前進(jìn)

即便擬合損失函數(shù)負(fù)梯度是可行的，為什么不直接擬合殘差？ 擬合負(fù)梯度好在哪里？

• 前者不用殘差的負(fù)梯度而是使用殘差，是全局最優(yōu)值，后者使用的是 局部最優(yōu)方向（負(fù)梯度）*步長(zhǎng)（??）
• 依賴(lài)殘差進(jìn)行優(yōu)化，損失函數(shù)一般固定為反映殘差的均方差損失函數(shù)，因此 當(dāng)均方差損失函數(shù)失效（該損失函數(shù)對(duì)異常值敏感）的時(shí)候，換了其他一般的損失函數(shù)，便很難得到優(yōu)化的結(jié)果。同時(shí)，因?yàn)閾p失函數(shù)的問(wèn)題，Boosting Tree也很難處理回歸之外問(wèn)題。 而后者使用梯度下降的方法，對(duì)于任意可以求導(dǎo)的損失函數(shù)它都可以處理

Shrinkage收縮的作用？

每次走一小步逐漸逼近結(jié)果的效果，要比每次邁一大步很快逼近結(jié)果的方式更容易得到精確值，即它不完全信任每一棵殘差樹(shù)，認(rèn)為每棵樹(shù)只學(xué)到了真理的一部分累加的時(shí)候只累加了一小部分多學(xué)幾棵樹(shù)來(lái)彌補(bǔ)不足。 這個(gè)技巧類(lèi)似于梯度下降里的學(xué)習(xí)率

• 原始：
  image

• Shrinkage：
  image

feature屬性會(huì)被重復(fù)多次使用么？

會(huì)，同時(shí)因?yàn)樘卣鲿?huì)進(jìn)行多次使用，特征用的越多，則該特征的重要性越大

gbdt如何進(jìn)行正則化的？

• 子采樣
  • 每一棵樹(shù)基于原始原本的一個(gè)子集進(jìn)行訓(xùn)練
  • rf是有放回采樣，gbdt是無(wú)放回采樣
  • 特征子采樣可以來(lái)控制模型整體的方差
• 利用Shrinkage收縮，控制每一棵子樹(shù)的貢獻(xiàn)度
• 每棵Cart樹(shù)的枝剪

為什么集成算法大多使用樹(shù)類(lèi)模型作為基學(xué)習(xí)器？或者說(shuō)，為什么集成學(xué)習(xí)可以在樹(shù)類(lèi)模型上取得成功？

• 對(duì)數(shù)據(jù)的要求比較低，不需要強(qiáng)假設(shè)，不需要數(shù)據(jù)預(yù)處理，連續(xù)離散都可以，缺失值也能接受
• bagging，關(guān)注于提升分類(lèi)器的泛化能力
• boosting，關(guān)注于提升分類(lèi)器的精度

gbdt的優(yōu)缺點(diǎn)？

優(yōu)點(diǎn)：

• 數(shù)據(jù)要求比較低，不需要前提假設(shè)，能處理缺失值，連續(xù)值，離散值
• 使用一些健壯的損失函數(shù)，對(duì)異常值的魯棒性非常強(qiáng)
• 調(diào)參相對(duì)較簡(jiǎn)單

缺點(diǎn)：

• 并行化能力差

gbdt和randomforest區(qū)別？

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

GBDT和LR的差異？

• 從決策邊界來(lái)說(shuō)，線性回歸的決策邊界是一條直線，邏輯回歸的決策邊界是一條曲線，而GBDT的決策邊界可能是很多條線
• 當(dāng)在高維稀疏特征的場(chǎng)景下，LR的效果一般會(huì)比GBDT好。因?yàn)長(zhǎng)R有參數(shù)懲罰，GBDT容易造成過(guò)擬合

XGboost缺點(diǎn)

• 每輪迭代時(shí)，都需要遍歷整個(gè)訓(xùn)練數(shù)據(jù)多次。如果把整個(gè)訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會(huì)限制訓(xùn)練數(shù)據(jù)的大??；如果不裝進(jìn)內(nèi)存，反復(fù)地讀寫(xiě)訓(xùn)練數(shù)據(jù)又會(huì)消耗非常大的時(shí)間
• 預(yù)排序方法需要保存特征值，及特征排序后的索引結(jié)果，占用空間
• level-wise，在訓(xùn)練的時(shí)候哪怕新增的分裂點(diǎn)對(duì)loss增益沒(méi)有提升也會(huì)先達(dá)到預(yù)定的層數(shù)

LightGBM對(duì)Xgboost的優(yōu)化

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

LightGBM亮點(diǎn)

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

xgboost對(duì)比gbdt/boosting Tree有了哪些方向上的優(yōu)化？

• 顯示的把樹(shù)模型復(fù)雜度作為正則項(xiàng)加到優(yōu)化目標(biāo)中
• 優(yōu)化目標(biāo)計(jì)算中用到二階泰勒展開(kāi)代替一階，更加準(zhǔn)確
• 實(shí)現(xiàn)了分裂點(diǎn)尋找近似算法
  • 暴力枚舉
  • 近似算法（分桶）
• 更加高效和快速
  • 數(shù)據(jù)事先排序并且以block形式存儲(chǔ)，有利于并行計(jì)算
  • 基于分布式通信框架rabit，可以運(yùn)行在MPI和yarn上
  • 實(shí)現(xiàn)做了面向體系結(jié)構(gòu)的優(yōu)化，針對(duì)cache和內(nèi)存做了性能優(yōu)化

xgboost和gbdt的區(qū)別？

• 模型優(yōu)化上：
  • 基模型的優(yōu)化：
    • gbdt用的是cart回歸樹(shù)作為基模型，xgboost還可以用線性模型，加上天生的正則項(xiàng)，就是帶L1和L2邏輯回歸(分類(lèi))和線性回歸(回歸)
  • 損失函數(shù)上的優(yōu)化：
    • gbdt對(duì)loss是泰勒一階展開(kāi)，xgboost是泰勒二階展開(kāi)
    • gbdt沒(méi)有在loss中帶入結(jié)點(diǎn)個(gè)數(shù)和預(yù)測(cè)值的正則項(xiàng)
  • 特征選擇上的優(yōu)化：
    • 實(shí)現(xiàn)了一種分裂節(jié)點(diǎn)尋找的近似算法，用于加速和減小內(nèi)存消耗，而不是gbdt的暴力搜索
    • 節(jié)點(diǎn)分裂算法解決了缺失值方向的問(wèn)題，gbdt則是沿用了cart的方法進(jìn)行加權(quán)
  • 正則化的優(yōu)化：
    • 特征采樣
    • 樣本采樣
• 工程優(yōu)化上：
  • xgboost在對(duì)特征進(jìn)行了分block預(yù)排序，使得在做特征分裂的時(shí)候，最終選增益最大的那個(gè)特征去做分裂，那么各個(gè)特征的增益計(jì)算就可以開(kāi)多線程進(jìn)行
  • cache-aware, out-of-core computation
  • 支持分布式計(jì)算可以運(yùn)行在MPI，YARN上，得益于底層支持容錯(cuò)的分布式通信框架rabit

xgboost優(yōu)化目標(biāo)/損失函數(shù)改變成什么樣？

• 原始：
  image
  • image
    為泰勒一階展開(kāi)，
    image

• 改變：
  image

  • J為葉子結(jié)點(diǎn)的個(gè)數(shù)，
    image

    為第j個(gè)葉子結(jié)點(diǎn)中的最優(yōu)值

  • image
    為泰勒二階展開(kāi)，
    image

xgboost如何使用MAE或MAPE作為目標(biāo)函數(shù)？

image

image

• 利用可導(dǎo)的函數(shù)逼近MAE或MAPE
  • mse
  • Huber loss
  • Pseudo-Huber loss

xgboost如何尋找分裂節(jié)點(diǎn)的候選集？

• 暴力枚舉
  • 法嘗試所有特征和所有分裂位置，從而求得最優(yōu)分裂點(diǎn)。當(dāng)樣本太大且特征為連續(xù)值時(shí)，這種暴力做法的計(jì)算量太大
• 近似算法（approx）
  • 近似算法尋找最優(yōu)分裂點(diǎn)時(shí)不會(huì)枚舉所有的特征值，而是對(duì)特征值進(jìn)行聚合統(tǒng)計(jì)，然后形成若干個(gè)桶。然后僅僅將桶邊界上的特征的值作為分裂點(diǎn)的候選，從而獲取計(jì)算性能的提升
    • 離散值直接分桶
    • 連續(xù)值分位數(shù)分桶

xgboost如何處理缺失值？

• 訓(xùn)練時(shí)：缺失值數(shù)據(jù)會(huì)被分到左子樹(shù)和右子樹(shù)分別計(jì)算損失，選擇較優(yōu)的那一個(gè)
• 預(yù)測(cè)時(shí)：如果訓(xùn)練中沒(méi)有數(shù)據(jù)缺失，預(yù)測(cè)時(shí)出現(xiàn)了數(shù)據(jù)缺失，那么默認(rèn)被分類(lèi)到右子樹(shù)

xgboost在計(jì)算速度上有了哪些點(diǎn)上提升？

• 特征預(yù)排序
  • 按特征進(jìn)行存儲(chǔ)，每一個(gè)block代表一個(gè)特征的值，樣本在該block中按照它在該特征的值排好序。這些block只需要在程序開(kāi)始的時(shí)候計(jì)算一次，后續(xù)排序只需要線性掃描這些block即可
  • block可以僅存放樣本的索引，而不是樣本本身，這樣節(jié)省了大量的存儲(chǔ)空間

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

• ’weight‘：代表著某個(gè)特征被選作分裂結(jié)點(diǎn)的次數(shù)；
• ’gain‘：使用該特征作為分類(lèi)結(jié)點(diǎn)的信息增益；
• ’cover‘：某特征作為劃分結(jié)點(diǎn)，覆蓋樣本總數(shù)的平均值；

XGBoost中如何對(duì)樹(shù)進(jìn)行剪枝？

• 在目標(biāo)函數(shù)中增加了正則項(xiàng)：葉子結(jié)點(diǎn)樹(shù)+葉子結(jié)點(diǎn)權(quán)重的L2模的平方
• 在結(jié)點(diǎn)分裂時(shí)，定義了一個(gè)閾值，如果分裂后目標(biāo)函數(shù)的增益小于該閾值，則不分裂
• 當(dāng)引入一次分裂后，重新計(jì)算新生成的左、右兩個(gè)葉子結(jié)點(diǎn)的樣本權(quán)重和。如果任一個(gè)葉子結(jié)點(diǎn)的樣本權(quán)重低于某一個(gè)閾值（最小樣本權(quán)重和），也會(huì)放棄此次分裂
• XGBoost 先從頂?shù)降捉?shù)直到最大深度，再?gòu)牡椎巾敺聪驒z查是否有不滿足分裂條件的結(jié)點(diǎn)，進(jìn)行剪枝

XGBoost模型如果過(guò)擬合了怎么解決？

• 直接修改模型：
  • 降低樹(shù)的深度
  • 增大葉子結(jié)點(diǎn)的權(quán)重
  • 增大懲罰系數(shù)
• subsample的力度變大，降低異常點(diǎn)的影響
• 減小learning rate，提高estimator

xgboost如何調(diào)參數(shù)？

• 先確定learningrate和estimator
• 再確定每棵樹(shù)的基本信息，max_depth和 min_child_weight
• 再確定全局信息：比如最小分裂增益，子采樣參數(shù)，正則參數(shù)
• 重新降低learningrate，得到最優(yōu)解