盤點前深度學習時代阿里、谷歌、Facebook 的 CTR 預估模型
本文是王喆在 AI 前線 開設的原創技術專欄“深度學習 CTR 預估模型實踐”的第三篇文章（以下“深度學習 CTR 預估模型實踐”簡稱“深度 CTR 模型”）。回顧王喆老師過往精彩文章： 《重讀 Youtube 深度學習推薦系統論文，字字珠璣，驚為神文》 、 《YouTube 深度學習推薦系統的十大工程問題》 。
在上篇專欄文章 《前深度學習時代 CTR 預估模型的演化之路——從 LR 到 FFM》 中，我們沿著特徵交叉這條發展路線，回顧了從 LR 到 POLY2，FM，再到 FFM 的 CTR 模型演化過程。但任何問題的觀察角度都不是唯一的，CTR 模型更是如此，本文將繼續探索前深度學習時代的 CTR 模型，從特徵工程模型化的角度回顧 Facebook 的 CTR 模型——GBDT+LR，從時效性的角度學習 Google 是如何使用 FTRL 解決模型 online learning 問題的，最後從樣本聚類的動機出發介紹阿里的 LS-PLM CTR 模型。
在介紹細節之前，我們再次回到前深度學習時代的 CTR 模型關係圖，熟悉各個模型在演化過程中的位置，其中黃色的部分是上篇專欄文章介紹的模型，藍色部分將是這篇文章的主要內容。
GBDT+LR——特徵工程模型化的開端
上篇文章介紹的 FFM 模型採用引入特徵域的方式增強了模型的表達能力，但無論如何，FFM 只能夠做二階的特徵交叉，如果要繼續提高特徵交叉的維度，不可避免的會發生組合爆炸和計算複雜度過高的情況。那麼有沒有其他的方法可以有效的處理高維特徵組合和篩選的問題？2014 年，Facebook 提出了基於 GBDT+LR 組合模型的解決方案。
簡而言之，Facebook 提出了一種利用 GBDT 自動進行特徵篩選和組合，進而生成新的離散特徵向量，再把該特徵向量當作 LR 模型輸入，預估 CTR 的模型結構。
需要強調的是，用 GBDT 構建特徵工程，和利用 LR 預估 CTR 兩步是獨立訓練的。所以自然不存在如何將 LR 的梯度回傳到 GBDT 這類複雜的問題，而利用 LR 預估 CTR 的過程在上篇文章中已經有所介紹，在此不再贅述，下面著重講解如何利用 GBDT 構建新的特徵向量。
大家知道，GBDT 是由多棵迴歸樹組成的樹林，後一棵樹利用前面樹林的結果與真實結果的殘差做為擬合目標。每棵樹生成的過程是一棵標準的迴歸樹生成過程，因此每個節點的分裂是一個自然的特徵選擇的過程，而多層節點的結構自然進行了有效的特徵組合，也就非常高效的解決了過去非常棘手的特徵選擇和特徵組合的問題。
利用訓練集訓練好 GBDT 模型之後，就可以利用該模型完成從原始特徵向量到新的離散型特徵向量的轉化。具體過程是這樣的，一個訓練樣本在輸入 GBDT 的某一子樹後，會根據每個節點的規則最終落入某一葉子節點，那麼我們把該葉子節點置為 1，其他葉子節點置為 0，所有葉子節點組成的向量即形成了該棵樹的特徵向量，把 GBDT 所有子樹的特徵向量連線起來，即形成了後續 LR 輸入的特徵向量。
舉例來說，如上圖所示，GBDT 由三顆子樹構成，每個子樹有 4 個葉子節點，一個訓練樣本進來後，先後落入“子樹 1”的第 3 個葉節點中，那麼特徵向量就是 [0,0,1,0]，“子樹 2”的第 1 個葉節點，特徵向量為 [1,0,0,0]，“子樹 3”的第 4 個葉節點，特徵向量為 [0,0,0,1]，最後連線所有特徵向量，形成最終的特徵向量 [0,0,1,0,1,0,0,0,0,0,0,1]。
由於決策樹的結構特點，事實上，決策樹的深度就決定了特徵交叉的維度。如果決策樹的深度為 4，通過三次節點分裂，最終的葉節點實際上是進行了 3 階特徵組合後的結果，如此強的特徵組合能力顯然是 FM 系的模型不具備的。但由於 GBDT 容易產生過擬合，以及 GBDT 這種特徵轉換方式實際上丟失了大量特徵的數值資訊，因此我們不能簡單說 GBDT 由於特徵交叉的能力更強，效果就比 FFM 好，在模型的選擇和除錯上，永遠都是多種因素綜合作用的結果。
GBDT+LR 比 FM 重要的意義在於，它大大推進了特徵工程模型化這一重要趨勢，某種意義上來說，之後深度學習的各類網路結構，以及 embedding 技術的應用，都是這一趨勢的延續。
在之前所有的模型演化過程中，實際上是從特徵工程這一角度來推演的。接下來，我們從時效性這個角度出發，看一看模型的更新頻率是如何影響模型效果的。
在模型更新這個問題上，我們的直覺是模型的訓練時間和 serving 時間之間的間隔越短，模型的效果越好，為了證明這一點，facebook 的工程師還是做了一組實效性的實驗（如上圖），在結束模型的訓練之後，觀察了其後 6 天的模型 loss（這裡採用 normalized entropy 作為 loss）。可以看出，模型的 loss 在第 0 天之後就有所上升，特別是第 2 天過後顯著上升。因此 daily update 的模型相比 weekly update 的模型效果肯定是有大幅提升的。
如果說日更新的模型比周更新的模型的效果提升顯著，我們有沒有方法實時引入模型的效果反饋資料，做到模型的實時更新從而進一步提升 CTR 模型的效果呢？Google 2013 年應用的 FTRL 給了我們答案。
FTRL——天下武功，唯快不破
FTRL 的全稱是 Follow-the-regularized-Leader，是一種線上實時訓練模型的方法，Google 在 2010 年提出了 FTRL 的思路，2013 年實現了 FTRL 的工程化，之後快速成為 online learning 的主流方法。與模型演化圖中的其他模型不同，FTRL 本質上是模型的訓練方法。雖然 Google 的工程化方案是針對 LR 模型的，但理論上 FTRL 可以應用在 FM，NN 等任何通過梯度下降訓練的模型上。
為了更清楚的認識 FTRL，這裡對梯度下降方法做一個簡要的介紹。從訓練樣本的規模角度來說，梯度下降可以分為：batch，mini-batch，SGD（隨機梯度下降）三種，batch 方法每次都使用全量訓練樣本計算本次迭代的梯度方向，mini-batch 使用一小部分樣本進行迭代，而 SGD 每次只利用一個樣本計算梯度。對於 online learning 來說，為了進行實時得將最新產生的樣本反饋到模型中，SGD 無疑是最合適的訓練方式。
但 SGD 對於互利網廣告和推薦的場景來說，有比較大的缺陷，就是難以產生稀疏解。為什麼稀疏解對於 CTR 模型如此重要呢？
之前我們已經多次強調，由於 one hot 等 id 類特徵處理方法導致廣告和推薦場景下的樣本特徵向量極度稀疏，維度極高，動輒達到百萬、千萬量級。為了不割裂特徵選擇和模型訓練兩個步驟，如果能夠在保證精度的前提下儘可能多的讓模型的引數權重為 0，那麼我們就可以自動過濾掉這些權重為 0 的特徵，生成一個“輕量級”的模型。“輕量級”的模型不僅會使樣本部署的成本大大降低，而且可以極大降低模型 inference 的計算延遲。這就是模型稀疏性的重要之處。
而 SGD 由於每次迭代只選取一個樣本，梯度下降的方向雖然總體朝向全域性最優解，但微觀上的運動的過程呈現布朗運動的形式，這就導致 SGD 會使幾乎所有特徵的權重非零。即使加入 L1 正則化項，由於 CPU 浮點運算的結果很難精確的得到 0 的結果，也不會完全解決 SGD 稀疏性差的問題。就是在這樣的前提下，FTRL 幾乎完美地解決了模型精度和模型稀疏性兼顧的訓練問題。
但 FTRL 的提出也並不是一蹴而就的。如上圖所示，FTRL 的提出經歷了下面幾個關鍵的過程：
-
從最近簡單的 SGD 到 OGD（online gradient descent），OGD 通過引入 L1 正則化簡單解決稀疏性問題；
-
從 OGD 到截斷梯度法，通過暴力截斷小數值梯度的方法保證模型的稀疏性，但損失了梯度下降的效率和精度；
-
FOBOS（Forward-Backward Splitting），google 和伯克利對 OGD 做進一步改進，09 年提出了保證精度併兼顧稀疏性的 FOBOS 方法；
-
RDA：微軟拋棄了梯度下降這條路，獨闢蹊徑提出了正則對偶平均來進行 online learning 的方法，其特點是稀疏性極佳，但損失了部分精度。
-
Google 綜合 FOBOS 在精度上的優勢和 RDA 在稀疏性上的優勢，將二者的形式進行了進一步統一，提出並應用 FTRL，使 FOBOS 和 RDA 均成為了 FTRL 在特定條件下的特殊形式。
FTRL 的演算法細節對於初學者來說仍然是晦澀的，建議非專業的同學僅瞭解其特點和應用場景即可。對演算法的數學形式和實現細節感興趣的同學，我強烈推薦微博 馮揚 寫的“線上最優化求解”一文，希望能夠幫助大家進一步熟悉 FTRL 的技術細節。
LS-PLM——阿里曾經的主流 CTR 模型
本文的第三個模型，我們從樣本 pattern 本身來入手，介紹阿里的的 LS-PLM（Large Scale Piece-wise Linear Model），它的另一個更廣為人知的名字是 MLR（Mixed Logistic Regression）。MLR 模型雖然在 2017 年才公之於眾，但其早在 2012 年就是阿里主流的 CTR 模型，並且在深度學習模型提出之前長時間應用於阿里的各類廣告場景。
本質上，MLR 可以看做是對 LR 的自然推廣，它在 LR 的基礎上採用分而治之的思路，先對樣本進行分片，再在樣本分片中應用 LR 進行 CTR 預估。在 LR 的基礎上加入聚類的思想，其動機其實來源於對計算廣告領域樣本特點的觀察 。
舉例來說，如果 CTR 模型要預估的是女性受眾點選女裝廣告的 CTR，顯然我們並不希望把男性使用者點選數碼類產品的樣本資料也考慮進來，因為這樣的樣本不僅對於女性購買女裝這樣的廣告場景毫無相關性，甚至會在模型訓練過程中擾亂相關特徵的權重。為了讓 CTR 模型對不同使用者群體，不用使用者場景更有針對性，其實理想的方法是先對全量樣本進行聚類，再對每個分類施以 LR 模型進行 CTR 預估。MLR 的實現思路就是由該動機產生的。
MLR 目標函式的數學形式如上式，首先用聚類函式π對樣本進行分類（這裡的π採用了 softmax 函式，對樣本進行多分類），再用 LR 模型計算樣本在分片中具體的 CTR，然後將二者進行相乘後加和。
其中超引數分片數 m 可以較好地平衡模型的擬合與推廣能力。當 m=1 時 MLR 就退化為普通的 LR，m 越大模型的擬合能力越強，但是模型引數規模隨 m 線性增長，相應所需的訓練樣本也隨之增長。在實踐中，阿里給出了 m 的經驗值為 12。
下圖中 MLR 模型用 4 個分片可以完美地擬合出資料中的菱形分類面。
MLR 演算法適合於工業級的廣告、推薦等大規模稀疏資料場景問題。主要是由於表達能力強、稀疏性高等兩個優勢：
-
端到端的非線性學習：從模型端自動挖掘資料中蘊藏的非線性模式，省去了大量的人工特徵設計，這使得 MLR 演算法可以端到端地完成訓練，在不同場景中的遷移和應用非常輕鬆。
-
稀疏性：MLR 在建模時引入了 L1 和 L2,1 範數，可以使得最終訓練出來的模型具有較高的稀疏度，模型的學習和線上預測效能更好。
如果我們用深度學習的眼光來看待 MLR 這個模型，其在結構上已經很接近由輸入層、單隱層、輸出層組成的神經網路。所以某種意義上說，MLR 也在用自己的方式逐漸逼近深度學習的大門了。
深度學習 CTR 模型的前夜
2010 年 FM 被提出，特徵交叉的概念被引入 CTR 模型；2012 年 MLR 在阿里大規模應用，其結構十分接近三層神經網路；2014 年 Facebook 用 GBDT 處理特徵，揭開了特徵工程模型化的篇章。這些概念都將在深度學習 CTR 模型中繼續應用，持續發光。
另一邊，Alex Krizhevsky 2012 年提出了引爆整個深度學習浪潮的 AlexNet，深度學習的大幕正式拉開，其應用逐漸從影象擴充套件到語音，再到 NLP 領域，推薦和廣告也必然會緊隨其後，投入深度學習的大潮之中。
2016 年，隨著 FNN、Deep&Wide、Deep crossing 等一大批優秀的 CTR 模型框架的提出，深度學習 CTR 模型逐漸席捲了推薦和廣告領域，成為新一代 CTR 模型當之無愧的主流。下一篇文章，我們將繼續探討深度學習 CTR 模型，從模型演化的角度揭開所有主流深度學習 CTR 模型之間的關係和每個模型的特點，期待繼續與你一同學習討論。
《深度學習 CTR 預估模型實踐》專欄內容回顧：
作者介紹
王喆，畢業於清華大學計算機系，現在美國最大的 smartTV 公司 Roku 任 senior machine learning engineer，曾任 hulu senior research SDE，7 年計算廣告、推薦系統領域業界經驗，相關專利 3 項，論文 7 篇，《機器學習實踐指南》、《百面機器學習》作者之一。知乎專欄 / 微信公眾號：王喆的機器學習筆記。
更多內容，請關注 AI 前線
