Datawhale

作者：小雨姑娘，Datawhale成員

事情的源頭是這樣的，某日我分享了一篇阿里機器學習工程師面試失敗經歷，其中提到了我回答關于Xgboost的部分，評論區的老哥就開始了靈魂拷問：“你真正看過Xgboost的原文嗎？”哈哈哈，真讓你猜中了，我這個菜逼還真沒看過，所以當時答得自己像個憨比。

沒關系，沒看過不要緊，現在著手看就行了哈哈，就像知乎上常說的一句話，種一棵樹最好的時間是十年前，其次是現在。

未看過原文 VS 看過原文

先復盤一下七個月前我沒看過原文面試的情況：

Q

那像你提到有用到Xgboost，你有測試過Xgboost和GBDT的效果區別嗎？你認為在你的項目上是什么原因導致了這個區別?

答：我們有試過，具體的效果是LightGBM大于Xgboost大于GBDT，但是具體為什么Xgboost效果比GBDT好我不知道，但是我知道LightGBM為什么好。據我所知，因為在Xgboost里面自帶了對離散值的處理，所以效果會好一些

Q

對離散值是怎么處理的？

答：類似于Onehot之類的叭

Q

那你知道在什么情況下應該使用Onehot呢？

答：嗯……應該是在特征的類別比較少的時候叭，如果太多了會導致維度爆炸，就應該使用概率方法，把他轉化為標簽的條件概率。

Q

你能講一下Xgboost和GBDT的區別嗎？

答：Xgboost實際上是一種對GBDT的實現叭，Xgboost在建基模型樹的時候，加入了正則項，相對于GBDT會控制基模型的…大小。然后Xgboost在建樹的時候好像是采用了并行策略，多線程在跑。還有一點據我所知……GBDT在選擇特征的時候使用的是基尼指數或者熵增之類的，而Xgboost是有優化過的。

那么如果是現在我會怎么回答呢？

Q

那像你提到有用到Xgboost，你有測試過Xgboost和GBDT的效果區別嗎？你認為在你的項目上是什么原因導致了這個區別？

答：是的，我們有試過，Xgboost的精度要比GBDT高而且效率也要更高。我認為精度高的最大原因是大部分的CTR特征中，我們會將一些高基類別的離散值轉化為連續值，會產生很多含有缺失值的稀疏特征，而Xgboost會對缺失值做一個特殊的處理。效率高是因為建樹時采用了更好的分割點估計算法。

Q

對缺失值是怎么處理的？

答：在普通的GBDT策略中，對于缺失值的方法是先手動對缺失值進行填充，然后當做有值的特征進行處理，但是這樣人工填充不一定準確，而且沒有什么理論依據。而Xgboost采取的策略是先不處理那些值缺失的樣本，采用那些有值的樣本搞出分裂點，然后在遍歷每個分裂點的時候，嘗試將缺失樣本劃入左子樹和右子樹，選擇使損失最優的情況。

Q

那你知道在什么情況下應該使用Onehot呢？

答：對于non-ordered特征來說需要做一個onehot，實踐中我發現在線性模型中將連續值特征離散化成0/1型特征效果會更好(線性模型擬合連續特征能力弱，需要將連續特征離散化 成one hot形式提升模型的擬合能力)。所以對于稠密的類別型特征，可以對離散特征做一個OneHot變化，對于高基類別特征我們最好還是采用bin count或者embedding的方法去處理。

Q

你能講一下Xgboost和GBDT的區別嗎？

答：Xgboost是GBDT算法的一種很好的工程實現，并且在算法上做了一些優化，主要的優化在一下幾點。首先Xgboost加了一個衰減因子，相當于一個學習率，可以減少加進來的樹對于原模型的影響，讓樹的數量變得更多；其次是在原GBDT模型上加了個正則項，對于樹的葉子節點的權重做了一個約束；還有增加了在隨機森林上常用的col subsample的策略；然后使用二階泰勒展開去擬合損失函數，加快優化的效率；然后最大的地方在于不需要遍歷所有可能的分裂點了，它提出了一種估計分裂點的算法。在工程上做了一個算法的并發實現，具體我并不了解如何實現的。

哈哈，看過原文后對于Xgboost的理解是不是好了一些

原文理解

先看第一章introduction，不需要聲嘶力竭地爭辯啥，只需要輕描淡寫地說，沒有Xgboost你們做不了數據挖掘比賽啦~

In this paper, we describe XGBoost, a scalable machine learning system for tree boosting. The system is available as an open source package. The impact of the system has been widely recognized in a number of machine learning and data mining challenges. Take the challenges hosted by the machine learning competition site Kaggle for example. Among the 29 challenge winning solutions 3 published at Kaggle’s blog during 2015, 17 solutions used XGBoost. Among these solutions, eight solely used XGBoost to train the model, while most others combined XGBoost with neural nets in ensembles. For comparison, the second most popular method, deep neural nets, was used in 11 solutions. The success of the system was also witnessed in KDDCup 2015, where XGBoost was used by every winning team in the top10. Moreover, the winning teams reported that ensemble methods outperform a well-configured XGBoost by only a small amount.

你看看人家的introduction，靚仔；你看看你的introduction，憨比。

有一說一，模型和算法里面用到的符號比較多，就不手打公式了，這里我就直接復制論文圖片貼上去，請大家理解。之前GBDT的已經推過了，就直接從原文第2.2章開始了。

目標函數，后面那一項就是加進來的規整項。注意這是一個遞歸的式子，規整項僅僅是第t顆樹的，具體起來就是這棵樹所有葉子節點權重向量的二范數。

然后我們對目標函數做了上面這么一個泰勒展開，這里其實是假設殘差接近于零的，所以和高數課本上的麥克勞林展開是一樣的。注意前面那個損失L(y,y^t-1)是個常數，所以可以不用管它。

麥克勞林展開

最后一步，把樣本 i 歸類到所在的葉子節點 j 上，改寫目標函數的形式如上圖。其中Ij指的是那些歸類到葉子節點 j 上的樣本的集合。其中Wj 指的是葉子節點 j 的權重。

然后對w求導為0，求得w的解析解：

再把w代入到目標函數里面，得到：

注意，之前已經提到了，這是個遞歸的式子，由于yt - yt-1是個常數可以不管他，剩下的部分都是關于yt的，也就是第t顆樹的。按照此公式優化完第t顆樹之后，還要繼續優化第t+1顆樹。

后面就是具體優化這棵樹的算法了，我們看看就知道找到一顆恰好能夠使上面公式最小的樹的結構肯定是個NP問題。GBDT優化的策略是什么呢？貪心，找到每一步最優的分裂結果，即二重循環遍歷所有特征以及所有分割點，每次選最好的那個。這算法的確不錯，只是每次遍歷每個可能的分割點代價有點大。但陳天奇采用了一種近似分割的算法，這種算法首先通過加權分位數的算法選出了一些可能的分裂點，然后再遍歷這些較少的分裂點來找到最佳分裂點。

具體產生可能分裂點的方式就是加權分位數，加權是用二階導數加權的：

第一眼看蒙了，用二階導加權，雖然給出了解釋，但感覺還是離譜。問了老師，老師也懵逼，后來看了一篇文章給了很好的解釋。

看這個公式是和損失函數等價的，前面hi就是某個樣本的二階導，后面gi/hi是個常數，所以hi可以看做計算殘差時某個樣本的重要性。

因為我們每個節點，要均分的是loss，而不是樣本的數量，而每個樣本對loss的貢獻可能是不一樣的，按樣本均分會導致loss分布不均勻，取到的分位點會有偏差。加上權重，不要讓某些結點重要的樣本多而且還大，類似于下圖：

這樣的話最右邊的子樹，只要一個權重特別大的樣本就夠了，左邊的子樹，權重太低，多給點樣本。這樣loss在樹結構中才均勻。

原文下載：https://arxiv.org/pdf/1603.02754

備注：公眾號菜單包含了整理了一本AI小抄，非常適合在通勤路上用學習。

往期精彩回顧2019年公眾號文章精選適合初學者入門人工智能的路線及資料下載機器學習在線手冊深度學習在線手冊AI基礎下載（第一部分）備注：加入本站微信群或者qq群，請回復“加群”加入知識星球（4500+用戶，ID：92416895），請回復“知識星球”

喜歡文章，點個在看

總結

以上是生活随笔為你收集整理的你看过Xgboost原文吗？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。