點擊率預估的幾個經典模型簡介

2016-02-22 00:32

點擊率預估是大數據技術應用的最經典問題之一，在計算廣告，推薦系統，金融征信等等很多領域擁有廣泛的應用。本文不打算對這個話題做個全面敘述，一方面這過于龐大，另一方面也已經有很多文章和演講材料相當不錯。本文只打算對已有的一些文字作個補充，從貼近實際的角度列舉一些經過商業檢驗的點擊率模型。

最經典的模型當然是邏輯回歸，這是絕大多數商業公司的選擇，簡單的邏輯回歸有實現容易，訓練快速等優點。自從邏輯回歸出現后，針對它的改進主要圍繞兩方面：如何正則化；如何最優化。正則化是機器學習的重要技術，它的主要目的是讓防止模型過擬合，目前比較常用的正則化有L1和L2。通常L2在減少預測錯誤上表現更好，這是因為當兩個特征相關時，L1會只選擇一個，而讓另外一個系數為0，因此可以產生稀疏解；而L2則會同時保留2個特征然后另它們的權重系數收縮。因此在數據維度有限時，L2會既有防止過擬合的優點，還不會導致模型預測損失。然而對于大規模機器學習框架，L1的稀疏解會更有吸引力，加入L1正則化的損失函數在優化后，絕大多數特征的權重都是0。這個特性可以大大減少點擊率預估時的內存占用，并提高預測的速度。關于最優化，因為邏輯回歸的損失函數是一個可以求導的凸函數，所以通常可以采用梯度下降或者擬牛頓進行最優化。不論是梯度下降，還是擬牛頓，都是頻率派的最優化手段，貝葉斯學派也有自己的手段，這就是微軟的AdPredictor提出的Bayesian Probit Regression[3]。AdPredictor有一些比較好的特性：它只需要一次迭代就可以收斂到最優解，而不是像梯度法或者擬牛頓法那樣需要反復迭代；它不僅能預測出一個樣本是正樣本的概率，而且還可以給出對于這個概率預測值的置信度，因此很多在線廣告公司都采用AdPredictor作為其點擊率預估的方法。由于AdPredictor假設特征權重的先驗分布遵循高斯分布，因此它相當于是L2正則化，這在許多大規模場景下難以接受，因此Google在13年發表的FTRL-Proximal提供了既是L1正則化，又具備AdPredictor優點的方案，FTRL-Proximal公式較多，讀者可以從[7]獲得更完整的敘述。

另一方面，回到模型本身，采用簡單的線性模型會導致其他一些問題，比如高維場景下，究竟應當如何選擇特征，大部分公司以來人工特征工程，隨著過程深入，這種方式的收益會逐步達到上限。此外，簡單線性模型無法捕捉特征之間的關聯，這對于提升長尾用戶行為的點擊率尤其關鍵。有一些公司在這些方面也做了不少工作。首先比較重要的是Facebook的工作[4]，它的主要貢獻在于通過利用非線性模型GBDT來進行特征選擇，GBDT的輸出作為線性模型邏輯回歸的輸入，通過這樣的級聯產生了明顯的提升。這種手段應當可以作為新一代點擊率預估系統的標準配置。

關于特征關聯發現，先來看看排名第一的重定向廣告公司Criteo的工作，在其點擊率方案中[5]直接利用x_u*M*x_a來修正sigmoid函數，其中M為一個矩陣，x_u和x_a分別代表用戶和廣告特征，因此矩陣的大小取決于用戶和廣告特征的基數。通常，這兩個數字都會很大，因此矩陣就會變得非常很大和稀疏，Criteo主要是借助于特征Hashing來減少矩陣尺寸，但這會導致沖突情況下無法判斷是哪些特征組合信號強的問題。

再來看看Linkedin的LASER系統，由于LASER的作者源自Yahoo內容優化和推薦引擎團隊，因此我們可以認為LASER跟Yahoo的工作如出一轍。

LASER點擊率預估系統建模跟Criteo類似，都很簡單直接，但是引入了上下文信息和更多特征。Y_ijt表示用戶i對于廣告j在上下文t下是否會點擊。相比傳統的邏輯回歸只用簡單的單一種類特征，LASER同時引入了用戶特征x_i，廣告特征c_j，以及上下文特征z_t，并且還要考慮這些特征之間的相互關聯信息。這種建模的思路是解決冷啟動問題的有效方式，因為這意味著即便沒有很多的用戶行為數據，也可以根據特征之間的關聯信息作出不算太離譜的預測，當然，如果能夠有用戶行為數據，則可以錦上添花，為此，LASER把傳統邏輯回歸的Logit對數差異函數s_ijt分成圖中所示的三個組成部分：第一個部分表達了概率密度跟所有一階特征的關系；第二部分表達了概率密度跟所有特征之間關聯程度的關系，包括用戶特征和廣告特征之間，廣告特征和上下文特征之間，以及用戶特征和上下文特征之間三種關聯，因此稱為二階特征。整個模型如果光有這部分數據，也能夠做出比較靠譜的預測，因此把這兩部份加起來稱作冷啟動。相比之下，第三部分稱作為熱啟動，用來表示用戶當前對于冷啟動選擇出的Top K廣告的偏好轉移，為便于快速實時計算，這部分只包含廣告和上下文的一階特征。

可以看到，冷啟動部分是LASER的主要工作，為訓練這部分模型，LASER采用了交替方向乘子ADMM算法和L2正則化。ADMM是一種求解優化問題的計算框架，適用于求解分布式凸優化問題，ADMM 通過將大的全局問題分解為多個較小、較容易求解的局部子問題，并通過協調子問題的解而得到大的全局問題的解。在高精度要求下，ADMM 的收斂很慢；但在中等精度要求下，ADMM 的收斂速度可以接受（幾十次迭代），因此ADMM非常適合大規模機器學習使用。在LASER里，又采用了一些額外優化，比如在不同分區同時進行計算，然后拿各分區的均值作為ADMM初始化參數，并且動態調節各分區計算的步長，這樣在實際中把ADMM的迭代次數可以降到更低（如十多次迭代），因此一方面提升了訓練性能，另一方面，也讓整個冷啟動部分的訓練可以在一些不適合機器學習的框架如Hadoop上運行良好。在Spark還不穩定的2013年，這樣做的價值是顯而易見的。在稀疏方面，LASER沒有考慮太多，因此大規模特征，比如百萬維以上，是不能采用的。

再來看看阿里的[2]CGL，意思是Coupled Group Lasso，就是在損失函數中分別用Group Lasso去正則化用戶特征和廣告特征。在文章前邊我們提到邏輯回歸正則化主要有L1和L2，其中L1也可叫Lasso，L2也可叫Ridge，除了L1和L2之外，還有一些其他的手段，比如結合L1和L2優點的Elastic Net，而Group Lasso是對Lasso的推廣，通過預先定義分組，以組為單位進行變量選擇。為了建模特征之間的關聯，CGL把普通邏輯回歸的sigmoid函數修改為如下：

其中x_u和x_a分別代表用戶和廣告特征，因此x_u*M*x_a就可以表征特征之間的關聯，而把矩陣M分解W*V'后就可以轉化成圖中的形式。采用這種方法改寫的原因是避免引入過于龐大的M矩陣，因此模型的參數可以少很多。

在解決特征組合的手段中，除了上面提到的針對邏輯回歸的工作之外，還有FM(Factorization Machine)，FM的建模跟LASER其實有一些類似，看下邊公式就知道了，都是把線性關系和特征笛卡爾積共同列出做統一優化，因此也具備特征關聯發現功能。

在以FM為核心的幾個方案贏得一些點擊率預估大賽之后，FM已經為更多的公司所接受，從競賽和學術方案走向商業成熟。

前邊列舉的主要是機器學習手段，而我們知道深度學習系統也能夠給點擊率預估帶來很大收益，百度是這方面的先行者之一，由于相關資料少我們就不單獨列舉了。由于LASER是筆者團隊曾經實現的系統，因此篇幅有些不合時宜得多。關于如何設計一個現代的點擊率系統，請諸位參考德川同學撰寫的“關于點擊率模型，你知道這三點就夠了”一文，德川同學采用的GBDT+FM，是經過商業檢驗的優秀方案，也是非基于深度學習的點擊率預估系統的最佳實踐之一。

參考文獻：

[1] LASER: A Scalable Response Prediction Platform For Online Advertising, Deepak Agarwal, WSDM 2014

[2] Coupled group lasso for web-scale ctr prediction in display advertising, Yan, Ling and Li, Wu-jun and Xue, Gui-Rong and Han, Dingyi, ICML 2014

[3] Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine, Graepel, Thore and Candela, Joaquin Q and Borchert, Thomas and Herbrich, Ralf, ICML 2010

[4] Practical lessons from predicting clicks on ads at facebook, He, Xinran and Pan, ADKDD 2014

[5] Simple and scalable response prediction for display advertising, Chapelle, Olivier, ACM Transactions on Intelligent Systems and Technology 2014

[6] Click-through prediction for advertising in twitter timeline, Li, Cheng and Lu, Yue and Mei, Qiaozhu, SIGKDD 2015

[7] 馮揚, 在線最優化求解

總結

以上是生活随笔為你收集整理的点击率预估的几个经典模型简介的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。