回顧Facebook經典CTR預估模型

雷鋒網 AI 科技評論按，本文作者是矽谷高級工程師王喆，原文發表在微信公眾號/知乎專欄 王喆的機器學習筆記上，雷鋒網獲授權轉載。

這裡是「王喆的機器學習筆記」的第九篇文章，今天我們重讀一篇經典的 CTR 預估領域的論文，Facebook 在 2014 發表的「Practical Lessons from Predicting Clicks on Ads at Facebook」。

在這篇文章中，Facebook 提出了經典的GBDT（Gradient Boosting Decision Trees）+LR(Logistics Regression)的 CTR 模型結構，可以說開啟了特徵工程模型化、自動化的新階段。此外其在五年前就採用的online learning，online data joiner，negative down sampling等技術時至今日也有極強的工程意義。下面我們就一起回顧一下這篇當時紅極一時，現在仍常看常新的論文吧。

用戶場景

文章的用戶場景是一個標準的點擊率預估的場景，需要強調的只有一點，因為我們需要利用 CTR 計算精準的出價、ROI 等重要的後續預估值，因此 CTR 模型的預估值需要是一個具有物理意義的精準的 CTR，而不是僅僅輸出廣告排序的高低關係。所以文中不僅把 CTR calibration 作為重要的評價指標，更是在最後介紹了模型校正的相關方法。

模型結構

計算廣告方向的同學應該都對 GBDT+LR 這個模型有所了解，這一點也無益是這篇文章最大的貢獻。雖然文章其他部分的價值絲毫不遜於該模型，但再次回顧該模型，清楚知道其技術細節還是必要的。

簡而言之，文章提出了一種利用 GBDT 自動進行特徵篩選和組合，進而生成新的 feature vector，再把該 feature vector 當作 logistic regression 的模型輸入，預測 CTR 的模型結構。

GBDT+LR 模型結構

這裡需要強調的是，用 GBDT 構建特徵工程，和利用 LR 預測 CTR 兩步是獨立訓練的。所以自然不存在如何將 LR 的梯度回傳到 GBDT 這類複雜的問題，而利用 LR 預測 CTR 的過程是顯然的，在此不再贅述，我們著重講一講如何利用 GBDT 構建新的特徵向量。

大家知道，GBDT 是由多棵回歸樹組成的樹林，後一棵樹利用前面樹林的結果與真實結果的殘差做為擬合目標。每棵樹生成的過程是一棵標準的回歸樹生成過程，因此每個節點的分裂是一個自然的特徵選擇的過程，而多層節點的結構自然進行了有效的特徵組合，也就非常高效的解決了過去非常棘手的特徵選擇和特徵組合的問題。

我們利用訓練集訓練好 GBDT 模型，之後就可以利用該模型構建特徵工程。具體過程是這樣的，一個樣本在輸入 GBDT 的某一子樹後，會根據每個節點的規則最終落入某一葉子節點，那麼我們把該葉子節點置為 1，其他葉子節點置為 0，所有葉子節點組成的向量即形成了該棵樹的特徵向量，把 GBDT 所有子樹的特徵向量 concatenate 起來，即形成了後續 LR 輸入的特徵向量。

舉例來說，比如 GBDT 由三顆子樹構成，每個子樹有 4 個葉子節點，一個訓練樣本進來後，先後落到了「子樹 1」的第 3 個葉節點中，那麼特徵向量就是 [0,0,1,0]，「子樹 2」的第 1 個葉節點，特徵向量為 [1,0,0,0]，「子樹 3」的第 4 個葉節點，特徵向量為 [0,0,0,1]，最後 concatenate 所有特徵向量，形成的最終的特徵向量為 [0,0,1,0,1,0,0,0,0,0,0,1]，我們再把該向量作為 LR 的輸入，預測 CTR。

引入了 GBDT+LR 的模型後，相比單純的 LR 和 GBDT，提升效果是非常顯著的。從下表中可以看到，混合模型比單純的 LR 或 Trees 模型在 loss 上減少了 3%。

LR+Trees 模型的 Loss 對比

為了確定最優的 GBDT 子樹規模，facebook 繪出了子樹規模和 loss 的關係曲線如下：

GBDT 子樹數量與 loss 的關係

可以看到，在規模超過 500 棵子樹後，增加子樹規模對於 loss 下降的貢獻就微乎其微了。特別是最後 1000 棵子樹僅貢獻了 0.1% 的 loss 下降，最終 facebook 選擇了 600 作為其子樹規模。

該模型的優勢我們上面已經提到，即可以自動進行特徵組合和特徵篩選，但在實踐過程中，模型的缺陷也比較明顯，相比 FTRL，FM，NN 等能夠通過梯度下降訓練的模型來說，GBDT 缺乏 online learning 的能力，因此我們往往只能相隔一天甚至幾天才能夠 update GBDT 模型，勢必影響模型的實效性，那麼 Facebook 是如何解決模型更新的問題的呢？

模型的實效性問題和更新策略

雖然我們的直覺是模型的訓練時間和 serving 時間之間的間隔越短，模型的效果越好，但為了證明這一點，facebook 的工程師還是做了一組實效性的實驗，在結束模型的訓練之後，觀察了其後 6 天的模型 loss（這裡採用 normalized entropy 作為 loss）

模型更新延遲與 loss 的關係

可以看出，模型的 loss 在第 0 天之後有所上升，特別是第 2 天過後顯著上升。因此 daily update 的模型相比 weekly update 的模型效果肯定是有大幅提升的。

但囿於 facebook 巨大的數據量以及 GBDT 較難實施並行化的原因，GBDT 的更新時間往往超過 24 小時，所以為了兼顧 data freshness 和客觀的工程要求，facebook 採取了下面的模型更新方法：

The boosted decision trees can be trained daily or every couple of days, but the linear classifier can be trained in near real-time by using some flavor of online learning.

就是說 GBDT 的部分幾天更新一次，而 LR 的部分進行准實時的更新，這無疑是很好的工程實踐經驗。時至今日，我們已經開始使用大量不同的 embedding 方法進行特徵編碼，facebook 當時的做法也對我們現在的工程實踐有重要的參考價值。因為大量深度學習 embedding 方法的更新計算開銷也非常大，但對實效性要求並不高，我們也完全可以低頻更新 embedding，高頻或實時更新基於 embedding 特徵的 LR，NN 等預測模型。

facebook 的實時數據流架構

為了實現模型的准實時訓練，facebook 專門介紹了其基於 Scribe 的數據流架構，文中稱其為 online data joiner。

該模塊最重要的作用是准實時的把來自不同數據流的數據整合起來形成 sample features，並最終與 click 數據進行 join，形成完整的 labeled sample。在整個過程中，我認為最應該注意的有三點：

1. waiting window 的設定：waiting window 指的是在 impression 發生後，我們要等待多久才能夠判定一個 impression 是否有 click。如果 waiting window 過大，數據實時性受影響，如果 waiting window 過小，會有一部分 click 來不及 join 到 impression，導致樣本 CTR 與真實值不符。這是一個工程調優的問題，需要有針對性的找到跟實際業務匹配的合適的 waiting window。除此之外，無論怎樣我們都會漏掉一部分 click，這就要求我們階段性的全量 retrain 我們的模型，避免 online learning 誤差的積累。

2. 分散式的架構與全局統一的 action id：為了實現分散式架構下 impression 記錄和 click 記錄的 join，facebook 除了為每個 action 建立全局統一的 request id 外，還建立了 HashQueue 緩存 impressions。hashQueue 緩存的 impression，如果在窗口過期時還沒有匹配到 click 就會當作 negative sample，這裡說的窗口與上面提到的 waiting window 相匹配。facebook 使用 scribe 實現了這一過程，更多公司使用 Kafka 完成大數據緩存和流處理。

3. 數據流保護機制：facebook 專門提到了 online data joiner 的保護機制，因為一旦 data joiner 失效，比如 click stream 無法 join impression stream，那麼所有的樣本都會成為負樣本，由於模型實時進行 online learning 和 serving，模型準確度將立刻受到錯誤樣本數據的影響，進而直接影響廣告投放和公司利潤，後果是非常嚴重的。為此，facebook 專門設立了異常檢測機制，一旦發現實時樣本數據流的分布發生變化，將立即切斷 online learning 的過程，防止預測模型受到影響。

降採樣和模型校正

對於巨型互聯網公司來說，為了控制數據規模，降低訓練開銷，降採樣幾乎是通用的手段，facebook 實踐了兩種降採樣的方法，uniform subsampling 和 negative down sampling

uniform subsampling是對所有樣本進行無差別的隨機抽樣，為選取最優的採樣頻率，facebook 試驗了 0.001，0.01，0.1，0.5 和 1 五個採樣頻率，loss 的比較如下：

可以看到當採樣率是 10% 時，相比全量數據訓練的模型，僅損失了不到 1% 的效果。

另一種方法 negative down sampling保留全量正樣本，對負樣本進行降採樣。除了提高訓練效率外，負採樣還直接解決了正負樣本不均衡的問題，facebook 經驗性的選擇了從 0.0001 到 0.1 的一組負採樣頻率，試驗效果如下：

大家可以看到，當負採樣頻率在 0.025 時，loss 不僅優於更低的採樣頻率訓練出來的模型，居然也優於負採樣頻率在 0.1 時訓練出的模型，雖然原文沒有作出進一步的解釋，但推測最可能的原因是解決了數據不均衡問題帶來的效果提升。

負採樣帶來的問題是 CTR 預估值的漂移，比如真實 CTR 是 0.1%，進行 0.01 的負採樣之後，CTR 將會攀升到 10% 左右。而為了進行準確的競價以及 ROI 預估等，CTR 預估模型是要提供準確的有物理意義的 CTR 值的，因此在進行負採樣後需要進行 CTR 的校正，使 CTR 模型的預估值的期望回到 0.1%。校正的公式如下：

其中 q 是校正後的 CTR，p 是模型的預估 CTR，w 是負採樣頻率。大家可以利用簡單的轉換關係就可以得出上述公式，有興趣的同學可以手動推導一下。

至此，我們介紹完了 facebook 這篇經典的 CTR 預估論文，可以看到雖然五年過去了，我們仍能從中汲取不少模型改造和工程實現的經驗，就我個人來言，最值得學習的有下面三點：

1. 特徵工程模型化。五年前在很多從業者還在通過調參經驗嘗試各種特徵組合的時候，利用模型進行特徵自動組合和篩選是相當創新的思路，也幾乎是從那時起，各種深度學習和 embedding 的思想開始爆發，一脈相承的發揚著特徵工程模型化的思路。

2. 模型複雜性和實效性的權衡。對 GBDT 和 LR 採用不同的更新頻率是非常工程化和有價值的實踐經驗，也是對組合模型各部分優點最大化的解決方案。

3. 有想法要用數據去驗證。這其實是我讀完這批文章最大的感觸，在做演算法工程師的過程中，我們其實是有很多直覺上的結論，比如 data freshness 的影響有多大，GBDT 應該設置多少顆子樹，到底是應該用負採樣還是 uniform 採樣，針對這些問題，facebook 告訴你的是，用數據說話，無論是多麼小的一個選擇，都應該用數據去支撐，這才是一位工程師嚴謹的工作態度。

最後慣例提出兩個問題供大家討論：

• 如果採用 random forest 替代 GBDT，有哪些優點和缺點？

• GBDT+LR 這個模型結構，是否能夠有效處理大量 ID 類特徵，為什麼？如果希望處理大量 ID 類特徵，我們應該如何改進這個模型？

歡迎大家關注我的微信公眾號 王喆的機器學習筆記（wangzhenotes）一起交流，水平有限，歡迎大家拍磚、吐槽、討論。感覺文章有價值的同學也歡迎點贊鼓勵，謝謝。

參考資料：

1. Practical Lessons from Predicting Clicks on Ads at Facebook

2. Computational Advertising Paper List

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！