常見計算廣告點擊率預估演算法總結

01-24

前言

談到CTR，都多多少少有些了解，尤其在互聯網廣告這塊，簡而言之，就是給某個網路服務使用者推送一個廣告，該廣告被點擊的概率，這個問題難度簡單到街邊算命隨口告訴你今天適不適合娶親、適不適合搬遷一樣，也可以複雜到拿到各種諸如龜殼、銅錢等等傢伙事，在沐浴更衣、凈手熅香後，最後一通預測，發現完全扯淡，被人暴打一頓，更有甚者，在以前關係國家危亡、異或爭國本這種情況時，也通常會算上一卦，國家的興衰、。其實CTR和這個一樣，以前經常和小夥伴吐槽，其實做機器學習、無論是推薦還是計算廣告，都和以前的算命先生沒什麼差別，做的好的官至國師，不好的吃不了飽飯也是有的。要想把你CTR模型做的好好的，必須要先了解那些前輩們都是怎麼玩的。

CTR架構

一個典型的CTR流程如下圖所示：

如上圖，主要包括兩大部分：離線部分、在線部分，其中離線部分目標主要是訓練出可用模型，而在線部分則考慮模型上線後，性能可能隨時間而出現下降，弱出現這種情況，可選擇使用Online-Learning來在線更新模型：：

· 離線部分：

數據收集：主要收集和業務相關的數據，通常會有專門的同事在app位置進行埋點，拿到業務數據；
預處理：對埋點拿到的業務數據進行去臟去重；
構造數據集：經過預處理的業務數據，構造數據集，在切分訓練、測試、驗證集時應該合理根據業務邏輯來進行切分；
特徵工程：對原始數據進行基本的特徵處理，包括去除相關性大的特徵，離散變數one-hot，連續特徵離散化等等;
模型選擇：選擇合理的機器學習模型來完成相應工作，原則是先從簡入深，先找到baseline，然後逐步優化；
超參選擇：利用gridsearch、randomsearch或者hyperopt來進行超參選擇，選擇在離線數據集中性能最好的超參組合；
在線A/B Test：選擇優化過後的模型和原先模型（如baseline）進行A/B Test，若性能有提升則替換原先模型；

在線部分

Cache & Logic：設定簡單過濾規則，過濾異常數據；
模型更新：當Cache & Logic 收集到合適大小數據時，對模型進行pretrain+finetuning，若在測試集上比原始模型性能高，則更新model server的模型參數；

Model Server：接受數據請求，返回預測結果；

Logistic Regression

最簡單的模型也應該是工業界應用最廣的方法，Logistic

Regression演算法簡單易於調參，屬於線性模型，原理如下圖：

將CTR模型建模為一個分類問題，利用LR預測用戶點擊的概率；通常我們只需要離線收集好數據樣本構造數據集，選擇好合適的特徵空間，離線訓練好模型，測試在離線數據集上的性能之後，即可上線，也可以適應數據分布隨時間突變嚴重的情況，採用online-learning的策略來對模型進行相對頻繁的更新，模型的簡單能夠保證這部分的需求能夠得到保障。

PLOY2

LR優點是簡單高效，缺點也很明顯，它太簡單，視特徵空間內特徵之間彼此獨立，沒有任何交叉或者組合關係，這與實際不符合，比如在預測是否會點擊某件t恤是否會點擊，如果在夏天可能大部分地區的用戶都會點擊，但是綜合季節比如在秋天，北方城市可能完全不需要，所以這是從數據特徵維度不同特徵之間才能體現出來的。因此，必須複雜到能夠建模非線性關係才能夠比較準確地建模複雜的內在關係，而PLOY2就是通過特徵的二項式組合來建模這類特徵的複雜的內在關係,二項式部分如下圖公式：

然而理想是美好的，現實卻是殘酷的，PLOY2有一個明顯的問題，就是在實際場景中，大部分特徵都是稀疏的，即大部分特徵值為0，對這些稀疏的特徵做二項式組合，會發現最後大部分特徵值都是0，而在梯度更新時，當大部分feature為0時，其實梯度並不更新，所以PLOY2的方法在實際場景中並不能比較好地解決這類特徵組合來建模更複雜線性關係的問題。

Factorization Machine

上面PLOY2雖然理論上能夠建模二項式關係，但是在實際場景下稀疏數據時，無法使用，而FM就是為了解決這裡PLOY2的短板的，FM的基本原理是將這些二項式矩陣做矩陣分解，將高維稀疏的特徵向量映射到低維連續向量空間，然後根據內積表示二項式特徵關係：=

複雜度為$O(kn^2)$，作者提出了一種簡化的演算法：

將複雜度簡化為$O(kn)$ 然後就是SGD來更新模型參數，使模型收斂（這裡還有很多其他替代SGD的方法，在FFM中有提到）：

訓練時間複雜度也是$O(kn)$，也就是線性時間，FM通過對二項式稀疏進行低維連續空間的轉換，能夠有效地解決PLOY2中存在的二次項係數在大規模係數數據下不更新的問題，另外由於訓練預測複雜度均為線性，PLOY2+SVM這樣邏輯下由於要計算多項式核，複雜度是n^2，由於FM的這幾個特徵，在實際場景中，FM也大規模的應用在CTR中，尤其是在數據極其係數的場景下，FM效果相對於其他演算法有很明星的改善。

Field-aware FM

FMM全程是 Field-aware

FactorizationMachine，相對於FM增加了Field信息，每個特徵屬於一個field，舉個例子：

而相對於FM，只有Feature_index相同個數的低維連續表示，而FFM則不同，每一個feature對不同的field有不同的表示，所以有#Field_index*#Feature_index個不同的表示：

通常由於每個低維隱變數表示只學習特定field的表示，所以FFM的隱變數長度相對於FM的隱變數維度要小的多。FFM的優化問題相對其比較簡單，可以看看FFM這篇paper，裡面比較詳細地描述優化過程，還有相關的偽代碼 https://www.andrew.cmu.edu/user/yongzhua/conferences/ffm.pdf。

FNN

從12年在ImageNet上深度學習超過經典模型之後，在計算機視覺、語音、NLP都有很多相關的工作，而在CTR上，深度學習的建模能力也有一些應用，FNN和SNN就是其中的一些嘗試，來源於DeepLearning over Multi-field Categorical Data – A Case Study on User ResponsePrediction，這裡稍微描述下相關的做法：

網路底層由FM來進行參數初始化，W的元素由FM中的低維連續空間向量表示來做初始化：

而構成W的低維連續空間向量表示預先由FM在數據集上生成，模型在訓練過程中，會通過BP來更新FM層參數，其他步驟和常見的MLP沒有什麼區別，這裡重點就是底層如何介入FM層參數的問題；

CCPM

CCPM利用卷積網路來做點擊率預測，看了文章，沒有太明白其中的所以然，貼下網路結構的圖吧：

有弄清楚這篇文章的小夥伴可以討論下。

PNN

PNN主要是在深度學習網路中增加了一個inner/outer

product layer，用來建模特徵之前的關係，如下圖，Product layer部分Z是weight*feature，P部分weight*I(feature_i,feature_j)用來建模二項式關係：

PNN按product層的功能分為inner product

layer和outer product layer，區別如下：

和FM類似，構造好網路之後，對輸入數據做embedding處理之後得到低維的連續向量表示，經過任意兩個feature的進行inner product or

outer product（1也為feature的一部分，所以可以建模線性關係），這裡很容易發現，這部分特徵大小會變大很多（二次項數量級）,尤其是稀疏空間，和PLOY2遇到的問題類似，變得很難訓練，受FM啟發，可以把這個大矩陣轉換矩陣分解為小矩陣和它的轉置相乘，表徵到低維度連續向量空間，來減少模型複雜度：

DeepFM

DeepFM更有意思的地方是WDL和FM結合了，其實就是把PNN和WDL結合了，PNN即將FM用神經網路的方式構造了一遍，作為wide的補充，原始的Wide and Deep，Wide的部分只是LR，構造線性關係，Deep部分建模更高階的關係，所以在Wide and Deep中還需要做一些特徵的東西，如Cross Column的工作，而我們知道FM是可以建模二階關係達到Cross column的效果，DeepFM就是把FM和NN結合，無需再對特徵做諸如Cross Column的工作了，這個是我感覺最吸引人的地方，其實FM的部分感覺就是PNN的一次描述，這裡只描述下結構圖，PNN的部分前面都描述, FM部分：

Deep部分：

DeepFM相對於FNN、PNN，能夠利用其Deep部分建模更高階信息（二階以上），而相對於Wide and Deep能夠減少特徵工程的部分工作，wide部分類似FM建模一、二階特徵間關係，算是NN和FM的一個更完美的結合方向，另外不同的是如下圖，DeepFM的wide和deep部分共享embedding向量空間，wide和deep均可以更新embedding部分，雖說wide部分純是PNN的工作，但感覺還是蠻有意思的。

其他的一些方法

GBDT+LR：Facebook提出利用GBDT探索海量特徵空間的特徵組合，減少特徵工程工作量，性能很好；
MLR：阿里媽媽前端時間提出的一種增強LR模型，將region的劃分考慮進去來建模非線性關係，感覺類似於深度學習的Attention機制，據說在阿里媽媽相關業務提升很多；

總結

前面討論了一些CTR常見的方法，重點介紹了Factorization

Machine及其變種Field-Aware Factorization Machine，還有和深度學習的結合，個人感覺PNN的邏輯比較有意思，完全使用神經網路的思維模型重塑了FM，為後面DeepFM擴展wide and deep的工作打下基礎，減少了wide and deep中需要的一些基本的特徵工程工作（wide部分二次項工作），上面只是涉及到模型的演算法部分，在實際中可以去探討，並不能說明一定性能就好，另外由於架構的限制，綜合考慮其他方面的因素，如請求時間、模型複雜度，也是最終是否採用相關演算法的考慮因素，各位對此有興趣討論的小夥伴，歡迎回復討論。