GBDT是如何成为推荐系统顶级工具人的？
文 | 水哥
源 | 知乎
Saying
1. 集成學習的ensemble注意一定要讀作昂三姆包而不是印三姆包，一天一個算法工程師裝x小技巧
2. 區別bagging和boosting的準則是，先訓練的模型對于后訓練的模型是否有影響
3. GBDT中，B（boosting）組成頭部，這是該方法的核心，G（Gradient）組成軀干，決定大方向上的選型，DT（Decision Tree）組成腿部，想換就可以換掉
4. Facebook把GBDT用在推薦里的重點是為了自動地找出特征的歸類方式，并沒有說明樹模型在推薦中優于LR，但是說明樹模型是頂級工具人
這是 從零單排推薦系統 系列的第14講，這一講和下一講我們合起來把樹模型在推薦中的使用講清楚。在推薦領域里，樹模型屬于是來得快，去得也快。Facebook最開始發表Practical Lessons from Predicting Clicks on Ads at Facebook[1]的時候，大家都覺得很新奇很有意思，但是這個時間點DNN已經開始攻城略地了。到了embedding+DNN稱霸的現在，還沒有什么特別好的方案能把樹模型和DNN結合在一起。時至今日，GBDT還可以作為一個很好的分桶工具，而它的升級版XGBoost和LightGBM則是以另一個形式活在推薦系統中。
如果是一個沒有背景知識的同學，面對GBDT這四個字母可能有點懵，我們首先來拆解一下這四個字母都代表什么：
DT：Decision Tree
就是決策樹，具體來說，Facebook的論文里面使用CART作為決策樹。決策樹的內容比較基礎這里就不贅述了。但是它完成了兩件事：（1）非線性的分類，（2）分桶。分桶的這個性質非常重要，屬于是無心插柳式的點了。
B：Boosting
Boosting和樹模型總是一起出現的，本質原因是樹模型往往比較弱，而當我們不滿足一個模型的能力，想要用多個模型來融合達到最佳結果，這種方法就是集成學習，即ensemble learning。而ensemble learning又可以分為兩種：bagging和boosting，如下圖所示：
黃色的圓表示數據點，藍色立方體是模型，而問號則是目標。問號的深淺表示這步需要擬合的難度。
bagging：使用多個模型來共同完成目標。目標不會拆解，在訓練時，每一個模型的任務都是擬合目標，在部署時，可以簡單把決策加起來或者投票。數據上，有時候為了讓模型的側重點不同，每個模型用的特征或數據不一樣。前面講過的MoE可以算是bagging，而random forest就算是典型的bagging了。
boosting：使用多個模型來擬合目標，目標是循序漸進的，即后面的模型學習前面模型沒學到的部分。數據上可以做區分。這一族的算法比較著名的是AdaBoost，還有這一講要講的Gradient Boosting Machine（GBM）。
如果對于第個樣本，模型的輸出和真實label分別是 和 ，我們把損失函數表示為。最終的決策可以表示為：
一共有 個模型，模型用 來表示。從部署上來看，boosting和bagging沒有區別，都是一堆弱分類器決策加起來形成更強的結果。但是對于boosting，前面出錯的樣本在后面會增大權重，即前后是互相影響的，而bagging的各個模型幾乎是獨立的。
GB：Gradient Boosting （Machine）
對于Gradient Boosting來說，每一步中，都新訓練一個模型，而這個模型學習的是之前所有結果綜合后，仍然距離目標的誤差：
其中之前模型的結果合起來就是 ，所以其實等價于讓 學習 和 之間相差的部分，也可稱之為殘差。公式最后的 表示正則部分。
簡單起見（也符合這部分技術發展的歷史）我們用MSE loss來代入 ，那么忽略掉正則項之后，loss就變成了 ，前面括號里的計算結果就是殘差了，可見這個loss實際上就是希望 。另一方面，如果對 求導，則有：
所以這么看下來就要求 ，我們似乎可以得到結論：后面加的每一個函數，就是擬合在前一步的時候的負梯度。 但是要注意的是，上面的推導其實是省略了正則項的，如果加上正則項，希望的 的結果一定會變，不會再次嚴格等于負梯度。
那為什么后續的方法還是按照負梯度來呢？
GBM中Gradient的含義
這個問題在知乎上也有一些爭論：gbdt的殘差為什么用負梯度代替？(https://www.zhihu.com/question/63560633)
有一部分人認為負梯度是下降方向，所以一定是對的，另一部分人認為和泰勒展開有關系
其實《Gradient boosting machines, a tutorial》[2]這篇文章就明確說了：In practice, given some specific loss function and/or a custom base-learner , the solution to the parameter estimates can be difficult to obtain. To deal with this, it was proposed to choose a new function to be the most parallel to the negative gradient along the observed data.
所以說白了就一句話，也沒想那么多，就是負梯度簡單好用，而且也不差。
其實在XGBoost[3]這篇文章其實還給出了一個理由：每次計算新的結果的時候，上一步的結果和梯度是可以提前算好的，那豈不是不用白不用？
GBDT：組裝積木
所以知道了DT，B，GB分別是什么之后，GBDT就好理解了：就是在GBM中吧模型換成決策樹就好了。
但是這一講得重點是我們要理解，為什么Facebook使用了GBDT？
要理解這一點，我們要從特征的處理來講起。在一個推薦模型中，特征最方便的用法是給一個ID，或者用One-hot來表示，這樣可以很容易和前面講的邏輯回歸（LR）結合使用。但是對于連續值特征（比如這個用戶已經累計登陸了多少天），值是不可以窮舉的，要把它們加入到模型中去，比較常見的做法是分桶（bucketize）。例如對與用戶累計登錄的天數，劃分0-1天是一檔，1-7是一檔，7-30，30-180，180-365，365+各有一檔。這樣這個特征就一定可以表示為這六者之一。但是問題是這個桶的邊如何才能切的很好呢？可能有同學說，我可以做個統計，選擇最有信息量的切法。但是這個分布其實是動態變化的，又保證能夠跟得上呢？
不只是連續特征有問題，離散的特征也有問題。比如item ID，可能有很多商品長得都沒啥差距，僅僅是代理商換了一下，ID就不一樣。這些ID可能出現的次數還很稀疏，如果給這些ID都分配空間也是比較占空間且低效的，我可不可以做一些壓縮，一堆弟弟ID就放到一個ID的桶里面好了呢？
理解了上面的兩個問題，就可以理解GBDT用在這里的動機：對于item ID這個特征，就單獨對它用決策樹訓練一下點擊率，在決策樹分裂的過程中自動地就會決定一些ID是不是在同一個葉子節點中，做到某個深度之后就停止，然后這個葉子節點的序號就成為新的ID。也就是說，在這里使用GBDT，其實只是當做一個更高級一點的分桶的工具。
補充一下原論文的圖來舉一個例子：
item ID現在有5個，第一棵樹用來轉換這個特征，在做決策的過程中，3號落入第一個葉子節點，1，2落入第二個葉子節點，4，5在第三個里面。那么輸入3之后，壓縮后的item ID現在是1了，同理，1，2現在都是2，4，5變為3.
接下來每一棵樹處理一種特征，以此類推，剛好就有了boosting的過程。在這個算法中，分為兩個步驟，訓練好的GBDT僅僅用來轉換特征。轉換完成的特征仍然使用LR來進行分類，GBDT只是一個變換/壓縮特征的工具人罷了。文章中也給出了比較，直接使用GBDT來分類效果并不會更好。
其實我們也不用在GBDT上面扣得太細，歸納一下就是GBDT是學過的決策樹的升級版本，而更進一步的版本是XGBoost和LightGBM，如果我們在哪個環節需要一個樹模型，直接調用它們就好了。
延遲轉化初窺
Practical Lessons from Predicting Clicks on Ads at Facebook 還討論了一個問題，所有樣本一曝光的時候都只能默認是負樣本，只有點擊了發生，才能變成正樣本。我們就有一個難點：一方面，我們是一個online learning的系統，為了能做更好的預估，我們希望樣本馬上反饋到訓練環節上；但是另一方面，等待有可能的樣本變成正樣本是需要時間的，如果等的時間太短就發送，可能會把正樣本誤判成負樣本。
這個問題在轉化（CVR）預估的時候非常常見，比如游戲下載，下載完了才算轉化，但是下載的時間可能會非常長，你不能等到幾個小時之后才發送樣本吧？這就是延遲轉化的問題，具體我們留到難點篇來講。
在本文中是簡單的用一個時間窗來記錄，在這個窗口之內轉變的正樣本才記錄。所以這也是比較直接的一個做法。如果等待的窗口時間設的特別長，那么我們的online learning就會越來越向線下退化，極端情況下，可能第二天才能學習第一天完整的結果。但是根據我們的復讀機理論，沒有快速把能點擊的ID記下來，一定會在性能表現上吃虧。反之，如果時間窗口設定的太小，在模型看來，有些本來應該是正樣本的現在都是負樣本了，負樣本比例升高，模型輸出的CTR，CVR就會變低，造成低估。
下期預告
推薦系統精排之鋒（9）：embedding亦福亦禍，XGBoost與LightGBM的新機遇
往期回顧
1.召回 粗排 精排，如何各司其職？
2.拍不完的腦袋：推薦系統打壓保送重排策略
3.簡單復讀機LR如何成為推薦系統精排之鋒？
4.召回粗排精排-級聯漏斗（上）
5.召回粗排精排-級聯漏斗（下）
6.推薦系統精排：看阿里媽媽再試線性模型
7.推薦精排之鋒：FM的一小步，泛化的一大步
8.推薦中使用FNN/PNN/ONN/NFM優化特征交叉
9.聊聊推薦系統的高階特征交叉問題
10.真正的高階特征交叉：xDeepFM與DCN-V2
后臺回復關鍵詞【入群】
加入賣萌屋NLP/IR/Rec與求職討論群
后臺回復關鍵詞【頂會】
獲取ACL、CIKM等各大頂會論文集！
?
[1] Practical Lessons from Predicting Clicks on Ads at Facebook，ADKDD，2014
https://research.fb.com/wp-content/uploads/2016/11/practical-lessons-from-predicting-clicks-on-ads-at-facebook.pdf
[2] Gradient boosting machines, a tutorial
https://www.frontiersin.org/articles/10.3389/fnbot.2013.00021/full
[3] XGBoost: A Scalable Tree Boosting System，KDD，2016
https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf
總結
以上是生活随笔為你收集整理的GBDT是如何成为推荐系统顶级工具人的？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 可解释性：对神经网络中层特征复杂度的解释
- 下一篇： 卖萌屋新闻联播栏目，倾情上线~