各大廠商CTR預估模型的優缺點對比

作者：TonyZhou

導語

筆者對各大廠商CTR預估模型的優缺點進行對比，並結合自身的使用和理解，梳理出一條CTR預估模型的發展脈絡，希望幫助到有需要的同學。

0. 提綱

1. 背景

2. LR 海量高緯離散特徵 (廣點通精排)

3. GBDT 少量低緯連續特徵 (Yahoo & Bing)

4. GBDT+LR (FaceBook)

5. FM+DNN (百度鳳巢)

6. MLR (阿里媽媽)

7. FTRL_Proximal (Google)

1. 背景

眾所周知，廣告平台的最終目標是追求收益最大化，以 CPC 廣告為例，平台收益既與 CPC 單價有關，又與預測 CTR 有關。在排序的時候，CPC 可以認為是一個確定的值，所以這裡的關鍵是預測用戶的點擊率 pCTR。

( 指數項 w 是一個調節因子，用於平衡用戶體驗和收入。扶持力度用於調節各個廣告渠道 )

互聯網公司根據各自業務的特點，研發出了各種各樣的 CTR 預估模型及其變種，本文嘗試在眾多流派和分支中梳理出一條 CTR 預估模型的發展脈絡。

2. LR 海量高緯離散特徵 (廣點通精排)

LR（邏輯回歸）1可以稱之上是 CTR 預估模型的開山鼻祖，也是工業界使用最為廣泛的 CTR 預估模型。LR 是廣義線性模型，與傳統線性模型相比，LR 使用了 Logit 變換將函數值映射到 0~1 區間，映射後的函數值就是 CTR 的預估值。

LR 利用了 Logistic 函數，函數形式為：

對於線性邊界，邊界形式如下：

Logistic 函數在有個很漂亮的"S"形，如下圖所示：

構造 log 損失函數，用梯度下降法求最小值，得到參數向量θ：

2.1 正則化

為了防止過擬合，通常會在損失函數後面增加懲罰項 L1 正則或者 L2 正則：

L1 正則化是指權值向量 w 中各個元素的絕對值之和，通常表示為||w||1；

L2 正則化是指權值向量 w 中各個元素的平方和然後再求平方根，通常表示為||w||2。

其中，L1 正則可以產生稀疏性，即讓模型部分特徵的係數為 0。這樣做有幾個好處：首先可以讓模型簡單，防止過擬合；還能選擇有效特徵，提高性能。

如上圖：最優解出現在損失函數的等值線和約束函數 L1 相切的地方，即凸點，而菱形的凸點往往出現在坐標軸上（係數 w1 或 w2 為 0），最終產生了稀疏性。

L2 正則通過構造一個所有參數都比較小的模型，防止過擬合。但 L2 正則不具有稀疏性，原因如下圖，約束函數 L2 在二維平面下為一個圓，與等值線相切在坐標軸的可能性就小了很多。

2.2 離散化

LR 處理離散特徵可以得心應手，但處理連續特徵的時候需要進行離散化。通常連續特徵會包含：大量的反饋 CTR 特徵、表示語義相似的值特徵、年齡價格等屬性特徵。

以年齡為例，可以用業務知識分桶：用小學、初中、高中、大學、工作的平均年齡區間做分桶；也可以通過統計量分桶，使各個分桶內的數據均勻分布。

反饋 CTR 特徵的離散化，一般通過統計量分桶，但在桶的邊界往往會出現突變的問題，比如兩個桶分別為 0.013~0.015、0.015~0.018，在邊界左右的值 0.01499 和 0.01501 會帶來完全不同的效果。（這裡給 GBDT LR 埋下一個伏筆）。

2.3 特徵組合

LR 由於是線性模型，不能自動進行非線性變換，需要大量的人工特徵組合。以 id 類特徵為例，用戶 id 往往有上億維(one-hot)，廣告 id 往往有上百萬維，特徵組合會產生維度爆炸。

廣告特徵里往往有三類維度(a,u,c)，分別是廣告類特徵、用戶類特徵、上下文類特徵。這三類特徵內部兩兩組合、三三組合，外部再兩兩組合、三三組合就產生了無限多種可能性。所以在 CTR 預估模型的早期，主要工作就是在做人工特徵工程。人工特徵工程不但極為繁瑣，還需要大量的領域知識和試錯。

2.4 優缺點

優點：由於 LR 模型簡單，訓練時便於並行化，在預測時只需要對特徵進行線性加權，所以性能比較好，往往適合處理海量 id 類特徵，用 id 類特徵有一個很重要的好處，就是防止信息損失（相對於范化的 CTR 特徵），對於頭部資源會有更細緻的描述。

缺點：LR 的缺點也很明顯，首先對連續特徵的處理需要先進行離散化，如上文所說，人工分桶的方式會引入多種問題。另外 LR 需要進行人工特徵組合，這就需要開發者有非常豐富的領域經驗，才能不走彎路。這樣的模型遷移起來比較困難，換一個領域又需要重新進行大量的特徵工程。

3. GBDT 少量低緯連續特徵 (Yahoo & Bing)

GBDT（Gradient Boosting Decision Tree）2是一種典型的基於回歸樹的 boosting 演算法。學習 GBDT，只需要理解兩方面：

a. 梯度提升（Gradient Boosting）：每次建樹是在之前建樹損失函數的梯度下降方向上進行優化，因為梯度方向(求導) 是函數變化最陡的方向。不斷優化之前的弱分類器，得到更強的分類器。每一棵樹學的是之前所有樹結論和的殘差。

b. 回歸樹（Regression Tree）：注意，這裡使用的是回歸樹而非決策樹，通過最小化 log 損失函數找到最靠譜的分支，直到葉子節點上所有值唯一 (殘差為 0)，或者達到預設條件(樹的深度)。若葉子節點上的值不唯一，則以該節點上的平均值作為預測值。

核心問題 1：回歸樹怎麼才能越來越好？

最直觀的想法，如果前一輪有分錯的樣本，那邊在後面新的分支只需提高這些分錯樣本的權重，讓沒學好的地方多學一學。這種方法在數學上可以用殘差來很好的解決，比如上圖中，第一輪訓練後殘差向量為(-1, 1, -1, 1)，第二輪訓練就是為了消除殘差，即這些分錯的樣本，當殘差為 0 或者達到停止條件才停止。

那麼哪裡體現了Gradient呢？其實回到第一棵樹結束時想一想，無論此時的 cost function 是什麼，是均方差還是均差，只要它以誤差作為衡量標準，殘差向量(-1, 1, -1, 1) 都是它的全局最優方向，這就是 Gradient。

核心問題 2：如何將多個弱分類器組合成一個強分類器？

通過加大分類誤差率較小的弱分類器的權重，通過多棵權重不同的樹（能者多勞）進行打分，最終輸出回歸預測值。

3.1 特徵工程

由於 GBDT 不善於處理大量 id 類離散特徵（後文會講到），但是卻善於處理連續的特徵，一般的做法是用各種 CTR 反饋特徵來做交叉，來范化的表達信息。在這種情況下，信息會大量存在於動態特徵中，而少量存在於模型中（對比 LR，信息幾乎都存在於模型中）。下圖是作者為搜索廣告的 GBDT 模型設計的特徵，讀者可供參考。

3.2 優缺點

優點：我們可以把樹的生成過程理解成自動進行多維度的特徵組合的過程，從根結點到葉子節點上的整個路徑(多個特徵值判斷)，才能最終決定一棵樹的預測值。另外，對於連續型特徵的處理，GBDT 可以拆分出一個臨界閾值，比如大於 0.027 走左子樹，小於等於 0.027（或者 default 值）走右子樹，這樣很好的規避了人工離散化的問題。

缺點：對於海量的 id 類特徵，GBDT 由於樹的深度和棵樹限制（防止過擬合），不能有效的存儲；另外海量特徵在也會存在性能瓶頸，經筆者測試，當 GBDT 的 one hot 特徵大於 10 萬維時，就必須做分散式的訓練才能保證不爆內存。所以 GBDT 通常配合少量的反饋 CTR 特徵來表達，這樣雖然具有一定的范化能力，但是同時會有信息損失，對於頭部資源不能有效的表達。

4. GBDT LR (FaceBook)

Facebook 在 2014 年發表文章介紹了通過 GBDT 解決 LR 的特徵組合問題3，其主要實現原理是：

訓練時，GBDT 建樹的過程相當於自動進行的特徵組合和離散化，然後從根結點到葉子節點的這條路徑就可以看成是不同特徵進行的特徵組合，用葉子節點可以唯一的表示這條路徑，並作為一個離散特徵傳入 LR 進行二次訓練。

預測時，會先走 GBDT 的每棵樹，得到某個葉子節點對應的一個離散特徵(即一組特徵組合)，然後把該特徵以 one-hot 形式傳入 LR 進行線性加權預測。

4.1 改進

Facebook 的方案在實際使用中，發現並不可行，因為廣告系統往往存在上億維的 id 類特徵(用戶 guid10 億維，廣告 aid 上百萬維)，而 GBDT 由於樹的深度和棵樹的限制，無法存儲這麼多 id 類特徵，導致信息的損失。有如下改進方案供讀者參考：

方案一：GBDT 訓練除 id 類特徵以外的所有特徵，其他 id 類特徵在 LR 階段再加入。這樣的好處很明顯，既利用了 GBDT 對連續特徵的自動離散化和特徵組合，同時 LR 又有效利用了 id 類離散特徵，防止信息損失。

方案二：GBDT 分別訓練 id 類樹和非 id 類樹，並把組合特徵傳入 LR 進行二次訓練。對於 id 類樹可以有效保留頭部資源的信息不受損失；對於非 id 類樹，長尾資源可以利用其范化信息（反饋 CTR 等）。但這樣做有一個缺點是，介於頭部資源和長尾資源中間的一部分資源，其有效信息即包含在范化信息(反饋 CTR) 中，又包含在 id 類特徵中，而 GBDT 的非 id 類樹只存的下頭部的資源信息，所以還是會有部分信息損失。

4.2 優缺點

優點：GBDT 可以自動進行特徵組合和離散化，LR 可以有效利用海量 id 類離散特徵，保持信息的完整性。

缺點：LR 預測的時候需要等待 GBDT 的輸出，一方面 GBDT在線預測慢於單 LR，另一方面 GBDT 目前不支持在線演算法，只能以離線方式進行更新。

5. FM DNN (百度鳳巢)

隨著深度學習的逐漸成熟，越來越多的人希望把深度學習引入 CTR 預估領域，然而由於廣告系統包含海量 id 類離散特徵，如果全用 one-hot 表示，會產生維度爆炸，DNN 不支持這麼多維的特徵。目前工業界方案是 FNN4，即用 FM 做 Embedding，DNN 做訓練。

FM（factorization machines）5的目標函數如下：

可以看到 FM 的前半部分可以理解成是 LR，後半部分可以理解成是特徵交叉(2 階 FM 只支持 2 維特徵交叉)。

DNN(Deep Neural Networks) 6模型往往具有多個隱層，通過 Relu、tanh 等激活函數做非線性變換，殘差會反向傳播，並通過隨機梯度下降來更新權值向量，最終預測時通過 sigmoid 函數做歸一化輸出（二分類用 sigmoid 做歸一化；多分類用 softmax 做歸一化）

FM DNN 的具體做法是：

對於離散特徵，先找到其對應的 category field，並用 FM 做 embedding，把該 category field 下的所有特徵分別投影到這個低維空間中。以用戶 query 為例，如果用 one-hot 可能有數十億維，但是如果我們用 FM 編碼，就可以把所有的 query 都映射到一個 200 維的向量連續空間里，這就大大縮小了 DNN 模型的輸入。

而對於連續特徵，由於其特徵維度本來就不多，可以和 FM 的輸出一同輸入到 DNN 模型里進行訓練。

6.1 優缺點

優點：FM 可以自動進行特徵組合，並能把同一 category field 下的海量離散特徵投影到一個低緯的向量空間里，大大減少了 DNN 的輸入。而 DNN 不但可以做非線性變換，還可以做特徵提取。

缺點：由於 2 階FM 只支持 2 維的特徵交叉（考慮性能的因素常用 2 階 FM），所以不能像 GBDT 那樣做到 10 維的特徵組合。另外 DNN 模型出於調參複雜和性能不高的原因，並不適用於中小型業務。所以在工業界使用的不多。

6. MLR (阿里媽媽)

前一陣子阿里巴巴的廣告部阿里媽媽公布了其 MLR(mixed logistic regression) 模型 7，MLR 是 LR 的一個改進， 它採用分而治之的思想，用分片線性的模式來擬合高維空間的非線性分類面。

簡單來說，MLR 就是聚類 LR，先對樣本空間進行分割，這裡有一個超參數 m，用來代表分片的個數，當 m=1 時自動淪為普通的 LR；當 m 越大，擬合能力越強；當然隨著 m 增大，其所需要的訓練樣本數也不斷增大，性能損耗也不斷增加。阿里的實驗表明，當 m=12 時，表現最好。

上圖公式可以看到，左邊聚類部分用 softmax 做分區函數並決定樣本空間的劃分，右預測部分用 sigmoid 做擬合函數，並決定空間內的預測。

上圖可以看到，對於這種高緯空間的非線性分類面，用 MLR 的效果比 LR 好。

6.1 優缺點

優點：MLR 通過先驗知識對樣本空間的劃分可以有效提升 LR 對非線性的擬合能力，比較適合於電商場景，如 3C 類和服裝類不需要分別訓練各自不同的 LR 模型，學生人群和上班族也不需要單獨訓練各自的 LR，在一個 LR 模型中可以搞定。模型的遷移能力比較強。

缺點：MLR 中超參數 m需要人工去調，另外還是有 LR 共性的缺點，如需要人工特徵組合和人工離散化分桶等。

7. FTRL_Proximal (Google)

對於 LR 靜態特徵這種模型，信息主要存儲在模型中（相比 GBDT 動態特徵，信息既存儲在模型中又存儲在動態特徵里），所以為了讓模型更加快速的適應線上數據的變化，google 率先把在線演算法 FTRL 引入 CTR 預估模型 8。

online 演算法其實並不複雜，batch 演算法需要遍歷所有樣本才能進行一輪參數的迭代求解(如隨機梯度下降)，而 online 演算法可以每取一個訓練樣本，就對參數進行一次更新，大大提升了效率。但這樣做也引入了一個問題，模型迭代不是沿著全局的梯度下降，而是沿著某個樣本的梯度進行下降，這樣即使用 L1 正則也不一定能達到稀疏解。

FTRL 是在傳統的在線演算法如 FOBOS 和 RDA 的基礎上做了優化，它採用和 RDA 一樣的 L1 正則，同時和 FOBOS 一樣會限制每次更新的距離不能太遠。所以它在稀疏性和精確度上要優於 RDA 和 FOBOS9。

另外 FTRL 採用Per-Coordinate Learning Rates，意思是對於某個特徵的完整性比較低的時候，會動態加大學習率，而對於特徵完整性高的，會減小學習率，讓特徵權重慢慢學。學習率的計算公式如下，即步長等於歷次梯度的平方和的開方的倒數：

7.1 優缺點

優點：FTRL 可以在線訓練，這樣使 LR 存儲於模型中的信息可以得到快速的更新。另外 FTRL 也具有不錯的稀疏性和精確度，可以減少內存佔用防止過擬合。最後 FTRL_Proximal 還支持動態的學習率，可以對不同完整性的特徵採用不同的步長進行梯度下降。

缺點：FTRL 同樣具有 LR 的缺點，需要人工特徵工程和人工離散化分桶。

引用

1. Chapelle O, Manavoglu E, Rosales R. Simple and scalable response prediction for display advertising

2. J. H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics 29, 1189–1232. 2001.

3. Practical lessons from predicting clicks on ads at facebook. He X, Pan J, Jin O, et al.

4. Deep Learning over Multi-field Categorical Data – A Case Study on User Response Prediction. Weinan Zhang.

5. Factorization Machines. Steffen Rendle.

6. Deep Neural Networks for Acoustic Modeling in Speech Recognition: The shared views of four research group. G. E. Hinton et al

7. Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction

8. McMahan H B, Holt G, Sculley D, et al. Ad click prediction: a view from the trenchesC//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 1222-1230.

9. H. B. McMahan. Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In AISTATS, 2011

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