embedding亦福亦祸？XGBoost与LightGBM的新机遇
文 | 水哥
源 | 知乎
Saying
1. 小的性能差異在容易實現面前一文不值，這一點是XGBoost和LightGBM的最大優勢
2. 沒能與embedding很好地結合無疑是樹模型的災難，吃不下巨量的新數據，也打不過DNN，除了一些規模比較小的公司，樹模型在精排中已經滅絕了
3. 但沒能與embedding很好地結合卻帶給樹模型無限生機，在每一個需要模型但又不能上太重模型的場合，樹模型都可以靈活的存在。以這種方式，樹模型在推薦系統中獲得了永生
4. 想要成為精排模型的必要不充分條件是，新出現的特征/取值不會對訓練部署流程有任何中斷或者形式上的改變
這是【從零單排推薦系統】系列的第15講。樹模型在推薦中應用，算法上的發展比較簡單，從決策樹，到基于樹的Gradient Boosting Machine，包括上一講的GBDT都是抓小點和縫合為主。雖然XGBoost和LightGBM在GBDT的基礎上各自還做了一些改進，但都是屬于修補性質的。這兩個工作更加為人熟知的是工具上的發展越來越好，開源的實現是很多人打比賽刷榜的利器。在實踐中，好用的框架/工具就是算法長盛不衰的秘訣。
本講的重點是一個很有意思的，別的地方沒有討論過的問題：在kaggle等比賽中，樹模型非常強勢，但是在實際業務中，樹模型幾乎不會成為精排的選擇，為什么會出現這樣一頭熱一頭冷的情況？其本質原因是，要成為不斷接受新數據新特征的門神模型，必須擁有形式上的不變性。
XGBoost[1]：更加精致的GBM
我們先延續上一講的GBDT的推導來介紹XGBoost，正如上一講所說，GBM的核心是級聯很多模型，后面的模型學習的都是前面模型綜合后剩下的殘差：
這里的公式含義都和上一講完全保持一致。在這里，我們可以做一個二階的近似，也就是按照泰勒展開到二階項為止：
其中， ， 分別表示在上一步對于 的一階，二階偏導。由于的結果基本之前都已經算過了，設現在這步需要擬合的目標是 的話，就有
為了能讓這個式子繼續簡化，可以假設模型結構 是一個回歸樹，即樣本對所有樹都做一次預測，而每棵樹的葉子節點都有權重，最后樣本的概率是這些落入節點的權重的和（可以換個方式來理解：經過一些非線性操作，也就是決策樹決策的過程，最后得到的仍然是一個binary的向量。1的點就是落入的葉子節點，其他則是0，然后相當于用一個LR來做分類）。那么這個模型可以表示為，若 還是一個二范數的正則化，那么把這個代入到上面的式子中得到的就是一個二次項（其中的按照維度拆解，找對稱軸和 《水哥：推薦系統精排之鋒（2）：工業LR的稀疏要求（挑戰全網最好懂推導(https://zhuanlan.zhihu.com/p/408205665)）》都是一樣的），就可以直接求解了。
算法上，XGBoost對尋找切割點的貪心做了效率上的優化，不是遍歷每一個點，而是先通過特征分布尋找可能成為切割點的候選，在遍歷這些候選的點。在工程上，XGBoost事先把排序結果存在Compressed Sparse Columns Format中，并且用塊壓縮和塊分區來優化IO速度。但工程優化不是這個專欄的重點（主要是我也不會），就不展開講了。
總結來說，相對于GBDT，XGBoost的主要優點有：1.使用了二階項作為更細的近似，精度更高；2. 使用正則項并且把葉子結點個數加入到正則項中，可以控制模型的復雜度；3. 在特征排序上和尋找切割點的過程中都做了并行化處理。
LightGBM[1]：極大加速的GBDT
LightGBM是GBDT的另一種改進版本，它的出發點是從樣本角度和特征角度來簡化GBDT的運算過程：
樣本角度：GBDT對于每一個樣本都要參與運算，而在LightGBM中，給出了一個假設：只有梯度大的哪些樣本才會影響學習的過程，梯度小的樣本是一定程度上可以忽略的。基于這個假設，我們要做的就是把梯度大的放回去繼續優化，梯度小的丟棄。但是還不是這么簡單的，如果梯度小的全丟了，那么可能會引入bias，所以我們可以選擇梯度大的（也就是排序前top a%）全要，后面的部分中采樣出b%。采樣后的部分要乘以一個系數 ，為啥是這個系數呢？假如采樣后和采樣前均值 沒發生變化，乘完系數之后兩類樣本的比值沒變，這樣可以盡量不讓分布發生變化（有沒有注意到和之前說過的樣本負采樣很像，還記得是哪一講的嗎？）。
特征角度：特征中有很多特征是不會同時為1的，比如有一些one-hot特征，性別，年齡這樣的，一個用戶只會有其中一個值不為0.那么遍歷這樣的所有取值是不太合理的。LightGBM提出把這些不會同時取1的特征合并在一起，行成一個“束”，這樣尋找切割點的時候，遍歷起來會更快，這個就叫做互斥特征捆綁（Exclusive Feature Bundling）。不過在實現上，還有兩個小問題，第一個問題是選擇誰和誰拼成一個新的特征？第二個問題是具體怎么操作？對于第一個問題，lightGBM給出的做法是以特征為頂點，以沖突（同時為1）有多大為邊建圖。每個節點的度是與其他節點沖突的大小，由大到小挨個開始：如果加入一個“束”會導致總的沖突數超過既定閾值 ，就新開一個“束”，反之則加入。對于第二個問題，其實就是把值域合并一下，文章中舉得例子是 的值域是 ， 的值域是 ，那么給 加一個10的偏置，再合起來，新的特征值域就是。
上面雖然介紹了現在樹模型比較好用的兩種算法/工具，但是本講的重點其實不是他們的原理，而是在實踐中我們如何選擇是否使用樹模型？如果用的話，用在哪些場合是比較理想的？
因為沒有embedding，樹模型絕跡于精排
我們這兩講提到了很多樹模型的優點，比如它的非線性是非常非線性的。但是大家如果對業界有所了解，就會發現很少在實際業務的精排中看到樹模型的身影，這是為什么？
先拋出結論：因為樹模型不能很好的處理在線學習過程中，源源不斷的出現的ID類型的特征。雖然XGBoost和LightGBM都談了對于未訓練的值如何處理，但在實際場景中這個數字可能會非常夸張。從冷啟動這個角度來想，如果我們希望我們的平臺是富有活力的平臺，就理應會源源不斷的出現新的item，那么冷啟動的規模就更大。現在的大平臺上，新item的比例應該遠遠超過50%，在這么大的未出現樣本面前，樹模型就顯得捉襟見肘了。不能很好的解決這個問題，樹模型就不能負擔得起精排的重任。
當然，樹模型不是完全沒有想過應對方案。前一講的Facebook那篇文章其實就說了，他們的樹模型是一天一更新的（如果不更新，就會失去樹模型強化分桶的作用）。這個方案當然體現了他們對問題的深入思考，但你也能看得出來這中間的勉強。如果樹模型后面接的環節是一天重新訓練不能收斂的，這個方案還能用嗎？
那么，現在的精排模型怎么解決這個問題？答案就是embedding，每當新出現了ID，我可以開辟一段新的空間來存儲，讓這段embedding保留該特征的信息。一個新的embedding的加入，雖然會引發冷啟動問題，但是對于訓練，部署的流程沒有任何改動。因此，基于embedding的embedding+DNN無往不利。
有的同學可能會說那LR也沒有embedding呀，為什么它可以？我們可以認為LR是有embedding的，但是只有1維，就是之前所說的特征的權重 。在未來還可能有新的形式或者模型出現，但是我認為，不管哪種模型來做精排，新的特征出現時，都不能在訓練部署上出現中斷，或者形式的改變。
目前為止還沒有看到樹模型和embedding很好地結合的例子，或者準確地說是樹模型沒什么加embedding的必要和意義。embedding本質上是把低維的ID映射到一個更高的空間中，記錄更細致的信息（我個人也有一些相關的經驗，比如把所有特征的embedding長度都翻倍，基本上漲幅有大有小，但是從來不會掉點。這表明更大的embedding擁有更多的存儲空間），而決策樹是按照特征本身的信息劃分的。
因為沒有embedding，樹模型得以長生
上面明明說沒有embedding，樹模型都快滅絕了，這里怎么又說長生了，乍一看這和上面的說法不是反著的嗎？
可能這就是所謂的塞翁失馬，焉知非福了。embedding是很強很暴力，但是embedding需要大量的空間（Parameter Server）來存。想想看，如果一個特征的embedding維度是64，原來LR中一臺機器能存下的特征現在就需要64臺機器來存，這是非常可怕的空間消耗。而且推薦系統也不是除了召回粗排精排就沒東西了，還有許許多多小的環節需要模型來預估，難道各個都用embedding+DNN的模型結構嗎？除了占用空間太大，可能其中有的模型ROI也不太高，不如就找個簡單點的模型抗住唄？
這個時候，樹模型就可以大展身手了。既然它不需要embedding，那它就很省空間。一些邊邊角角的地方，需要模型時都可以考慮用它。不要小看這些邊邊角角的場合，有些是發揮很大作用的，舉兩個例子：
判斷一個item處于生命周期中的哪個階段（在后面會講講這個概念，現在可以簡單理解為，一個item有剛開始起量，穩定膨脹，流量下滑和死亡這么幾個階段，根據這個階段可以做不同的針對性決策），此時Item ID做特征顯然是沒有意義的，而是item現在總的曝光量，已經投放了多久，每個階段的曝光，轉化等等。
預測一個用戶第二天是不是還會來，有各種行為特征，比如在某個類別下觀看了多少視頻，用戶已經用了多長時間，今天的總播放時長是多少等等。
這兩個例子都是實踐中使用樹模型的典型場景，也是非常重要的應用場景。第一個場景關系到在線廣告系統中，怎樣為廣告主分配流量。而第二個例子與留存-DAU這個漏斗的優化有關聯。從這兩個例子中歸納一下，當觸發以下兩個條件時，樹模型自動進化為不二選擇：
特征中沒有不斷新增的ID類特征，categorical特征可以窮舉，比如年齡，城市等。
當輸入的特征混有各種各樣的categorical，numeric等等類型的特征時，尤其對于像counter（計數類特征，比如用戶在APP上的時間）類很有效果。
經過上面的分析，我們就能理解為什么在工業界，樹模型從精排模型中絕跡了，但在kaggle等比賽中，經常出現樹模型的身影。因為kaggle的比賽大部分是閉集，而且對特征設計要求較高，這種情況很適合樹模型發揮強大的非線性分類能力。
開集與閉集：以人臉識別為例，閉集的含義是，測試集的人你都見過，只是現在給你的圖片你沒見過。而開集則指的是，測試集中會出現新的人，要判斷這些沒見過的人的圖片之間是否相似。所以在公開數據集里面基本都是固定的人（閉集），而如果是產品則要面對開集場景。
下期預告
推薦系統精排之鋒（10）：DNN與兩大門派
往期回顧
1.召回 粗排 精排，如何各司其職？
2.拍不完的腦袋：推薦系統打壓保送重排策略
3.簡單復讀機LR如何成為推薦系統精排之鋒？
4.召回粗排精排-級聯漏斗（上）
5.召回粗排精排-級聯漏斗（下）
6.推薦系統精排：看阿里媽媽再試線性模型
7.推薦精排之鋒：FM的一小步，泛化的一大步
8.推薦中使用FNN/PNN/ONN/NFM優化特征交叉
9.聊聊推薦系統的高階特征交叉問題
10.真正的高階特征交叉：xDeepFM與DCN-V2
11.GBDT是如何成為推薦系統頂級工具人的？
后臺回復關鍵詞【入群】
加入賣萌屋NLP/IR/Rec與求職討論群
后臺回復關鍵詞【頂會】
獲取ACL、CIKM等各大頂會論文集！
?
[1] XGBoost: A Scalable Tree Boosting System，KDD，2016
(https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf)
[2] LightGBM: A Highly Efficient Gradient Boosting Decision Tree，NIPS，2017
(https://proceedings.neurips.cc/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf)
總結
以上是生活随笔為你收集整理的embedding亦福亦祸？XGBoost与LightGBM的新机遇的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 请不要吸开源的血
- 下一篇： 召回粗排精排-级联漏斗（下）