CTR預測演算法之FTRL-Proximal

02-10

Google在2013年KDD上發表的論文Ad Click Prediction: a View from the Trenches，描述了FTRL-Proximal演算法的工程化的實踐。國內外公司紛紛進行了各自的實驗，比如亞馬遜，Yahoo，阿里，百度等也應用了該演算法在其搜索領域、推薦領域等的產品中，且都取得了明顯提升。另外在各大CTR競賽，Kaggle比賽上時常能看到它的身影。

基於現在信息更新速度很快且數據量爆炸，基於海量數據並進行快速更新迭代的需求導致online optimization特別當下的需要流式更新迭代的場景。Batch Gradient因為其需要offline的更新迭代且數據量的限制在CTR預測等領域使用較少。當然也可以做Batch learning和online learning的結合，效果也不錯。

Online optimization演算法的歷程大概可以描述為：SGD->TG-> FOBOS->RDA->FTRL-Proximal，FTRL可以看做RDA與FOBOS的結合體，兼顧了FOBOS的精確度與RDA的稀疏性。值得學習。

本文的思路大概分為以下幾個部分：

1. 演算法推導，及對應偽代碼;

2. Google工程化實踐的tricks;

下面分別進行展開：

一、演算法推導及對應偽代碼；

首先要感謝H. Brendan McMahan大大，創造並無私開放出來供我們學習；具體理論歷程大家可以參考如下幾篇paper：

1）Adaptive Bound Optimization for Online Convex Optimization.

2）A Unified View of Regularized Dual Averaging and Mirror Descent with Implicit Updates.

3）Ad Click Prediction: a View from the Trenches.

推導部分分成兩個大的部分，複習一下Logloss，接著進行FTRL推導：

1. LR的LogLoss導數推導：

$h(x)=g( heta ^{T}x )=frac{1}{1+e^{- heta ^{T}x} } , heta ^{T}x= heta_{0}+ heta_{1}x_{1}+ heta_{2}x_{2}+...++ heta_{n}x_{n}$ ) $P(y=1|x; heta)=h_{ heta} (x), P(y=0|x; heta)=1-h_{ heta} (x)$

可以改寫為：

$P(y|x; heta)=(h_{ heta} (x))^{y} (1-h_{ heta} (x))^{1-y}$

利用最大似然估計來求解最優的 $heta^{}$ ，一般分為四個步驟：

寫似然函數
取對數
求其偏導，並令其為0
求解

求解過程如下：

$L( heta)=prod_{i=1}^{m} P(y_{i}|x_{i}; heta)=prod_{i=1}^{m} (h_ heta{(x)} )^{y_{i} } (1-h_ heta{(x)} )^{1-y_{i} }$

$l( heta)=log(L( heta))=sum_{i=1}^{m}{(y_{i}log(h_{ heta}(x_{i} ) ) +(1-y_{i})log(1-h_{ heta}(x_{i} ) ))}$

乘以-1將其轉化為下凸函數，使用梯度下降來求得其最小值

令 $J( heta)=-frac{1}{m} l( heta)$ ,則： $heta_{j} := heta_{j}-alpha frac{delta }{delta heta_{j}} J( heta)$

其中： $frac{delta }{delta heta_{j}} J( heta)=-frac{1}{m} sum_{i=1}^{m}{y_{i} frac{1}{h_{ heta}(x_{i} ) } frac{delta }{delta heta_{j}}} h_{ heta}(x_{i})-{(1-y_{i}) frac{1}{1-h_{ heta}(x_{i} ) } frac{delta }{delta heta_{j}}} h_{ heta}(x_{i})$

$=-frac{1}{m} sum_{i=1}^{m}({y_{i}frac{1}{g( heta^{T} x_{i} )} } -{1-y_{i}frac{1}{1-g( heta^{T} x_{i} )} } )frac{delta }{delta heta_{j} } h_{ heta}(x_{i} )$

$=-frac{1}{m} sum_{i=1}^{m}({y_{i}frac{1}{g( heta^{T} x_{i} )} } -{1-y_{i}frac{1}{1-g( heta^{T} x_{i} )} } ) g( heta^{T} x_{i} )(1-g( heta^{T} x_{i} )) frac{delta }{delta heta_{j} } (x_{i} )$

$=-frac{1}{m} sum_{i=1}^{m}({y_{i}(1-g( heta^{T} x_{i} )) } -({1-y_{i})g( heta^{T} x_{i} ) } )x_{i}^{j}$

$=-frac{1}{m} sum_{i=1}^{m}({y_{i}-g( heta^{T} x_{i} ) } )x_{i}^{j}$

$=-frac{1}{m} sum_{i=1}^{m}({h_{ heta}(x_{i} ) -g( heta^{T} x_{i} ) } )x_{i}^{j}$

2. FTRL-Proximal推導過程：

define $sigma _{s}$ :learning rate

L1-FOBOS: $W^{t+1} =arg _{w}^{min} left{ G^{(t)}ast w +lambda left|left| w ight| ight|_{1} +frac{1}{2}sigma ^{1:t} left|left| w-w^{(t)} ight| ight|_{2}^{2} ight}$

L1-RDA: $W^{t+1} =arg _{w}^{min} left{ G^{(1:t)}ast w +tlambda left|left| w ight| ight|_{1} +frac{1}{2}sigma ^{1:t} left|left| w-0 ight| ight|_{2}^{2} ight}$

FTRL: $W^{t+1} =arg _{w}^{min} left{ G^{(1:t)}ast w +lambda _{1} left|left| w ight| ight|_{1} + lambda _{2} frac{1}{2}left|left| w ight| ight|^2+frac{1}{2}sigma ^{1:t} left|left| w-w^{(t)} ight| ight|_{2}^{2} ight}$

進行改寫：

$W^{t+1} =arg _{w}^{min} left{ (G^{(1:t)} - sum_{s=1}^{t}{ sigma^{(s)}w^{(s)} } )ast w +lambda _{1} left|left| w ight| ight|_{1} + frac{1}{2} (lambda _{2} + sum_{s=1}^{t}{ sigma^{(s)} } )left|left| w ight| ight|^2+frac{1}{2}sum_{s=1}^{t}sigma^{(s)} left|left| w^{(s)} ight| ight|_{2}^{2} ight}$

令 $Z^{(t)} =G^{(1:t)} -sum_{s=1}^{t}{sigma ^{(s)} w ^{(s)} }$

則有： $W^{t+1} =arg _{w}^{min} left{ Z^{(t)} ast w +lambda _{1} left|left| w ight| ight|_{1} + frac{1}{2} (lambda _{2} + sum_{s=1}^{t}{ sigma^{(s)} } )left|left| w ight| ight|^2 ight}$

針對各個特徵權重的各個維度將其拆解成N個獨立的標量最小化問題：

$_{w_{i} in R }^{minimize} left{ Z_{i}^{(t)}ast w_{i} + lambda _{1}left| w_{i} ight| + frac{1}{2}left( lambda _{2} + sum_{s=1}^{t}{sigma ^{(s)} } ight) w_{i}^{2} ight}$

由於 $lambda _{1}left| w_{i} ight|$ 在 $left| w_{i} ight|=0$ 處不可導，那我們假設 $left| w_{i}^{*} ight|$ 是最優解，並且定義 $xi in delta left| w_{i}^{*} ight|$ 在 $left| w_{i} ight|$ 在 $w_{i}^{*}$ 的次導數，則有：

$if w_{i}^{*} =0, delta left| w_{i}^{*} ight|=left{ -1<xi <1 ight}$

$if w_{i}^{*} >0, delta left| w_{i}^{*} ight|=left{1 ight}$

$if w_{i}^{*} <0, delta left| w_{i}^{*} ight|=left{ -1 ight}$

將 $Z$ 帶入並求導使其等於0，得：

$Z_{i}^{(t)} +lambda _{1}xi +(lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) w_{i} =0$

由於 $lambda _{1}>0,lambda _{2}>0,sigma ^{s} >0,$ 則分三種情況來討論 $|Z_{i}^{(t)} |<lambda _{1} ,Z_{i}^{(t)} >lambda _{1} ,Z_{i}^{(t)} <-lambda _{1}$ :

當 $|Z_{i}^{(t)} |<lambda _{1}$ 時，
1) $w_{i}^{*} =0,Z_{i}^{(t)} + lambda _{1}xi =0,$ 可得： $xi =-frac{Z_{i}^{(t)} }{lambda_{1} }$ ,滿足 $delta |0|$ 的要求；
2) $w_{i}^{*} >0,xi =1$ ,則 $Z_{i}^{(t)} + lambda _{1} + (lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) w_{i} >Z_{i}^{(t)} + lambda _{1}>0$ ,不滿足要求；
3) $w_{i}^{*} <0,xi =-1$ ,則 $Z_{i}^{(t)} - lambda _{1} + (lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) w_{i} <Z_{i}^{(t)} - lambda _{1}<0$ ,不滿足要求；
當 $Z_{i}^{(t)} >lambda _{1}$ 時，
1) $w_{i}^{*} =0,left{ -1<xi <1 ight} ,Z_{i}^{(t)} + lambda _{1}xi >0$ ,不滿足要求；
2) $w_{i}^{*} >0,xi =1,Z_{i}^{(t)} + lambda _{1} + (lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) w_{i} >Z_{i}^{(t)} + lambda _{1}>0$ ,不滿足要求；
3) $w_{i}^{*} <0,xi =-1,Z_{i}^{(t)} - lambda _{1} + (lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) w_{i}=0,$ 則 $w_{i} = -(Z_{i}^{(t)} - lambda _{1}) (lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) ^{-1}$ ,滿足要求；
同上，當 $w_{i}^{*} >0,xi =1$ 時，滿足要求；

綜上所述，可得：

$if |Z_{i}^{(t)} |<lambda_{1} ,w_{i}^{(t+1)}=0$

$otherwise,w_{i} = -(Z_{i}^{(t)} - lambda _{1}sgn(Z_{i}^{(t)})) (lambda _{2}+sum_{s=1}^{t}{sigma ^{(s)} } ) ^{-1}$

Google另一偉大的改進點在與per-coordinate設置。

對每個不同的特徵，根據該特徵在樣本中出現的次數來推算它的學習率。特徵如果出現很多次，那麼認為它對應的參數已經很可信了，那麼學習率應該比較小；如果出現次數很少，那麼它對應的參數可信度就很有限，學習率應該比較大，便於快速修正。

附上論文中的偽代碼：

二、下面對Google工程化實踐的trick進行說明：

save memory的策略：

predict時，節省內存是指使用L1使w稀疏，那麼自然而然節省了內存。具體見下圖理解：

training時，節省內存主要由以下6中方法：

1.概率特徵法：

在實踐中一半以上的特徵在全部訓練集中只出現一次，如果保留就會耗費大量內存且對於訓練來說效果很有限。常規去除掉這些特徵的方法是對全量數據進行預處理，對特徵進行count然後過濾掉頻次低於k的特徵，但是在online的情況下這樣做是不現實的。且由於扔掉是不可恢復的，也會帶來模型精確度的影響。Google提出的解決方法主要有兩種：

1）Poisson Inclusion:假設特徵是隨機到達的，也就是說應該符合Poisson分布。以p的概率隨機加入模型並進行訓練；

2）Bloom Filter Inclusion：使用布隆過濾器來進行計數，當特徵出現次數超過n時才加入模型。但布隆過濾器並非精確的，而是false positive的，因為產生衝突時，可能會加入還沒有滿n次的特徵來進行訓練。實際中我們並不要求完全精確的篩選。

在實驗中，Bloom Filter表現出更高的RAM節省及更少的AucLoss，更推薦。

2.用更少的位元組對浮點數進行編碼：

我們平常使用的都是32或64位浮點數編碼，但是在實際場景中，係數值普遍落在(-2,+2)之間，普通的編碼方式就顯得非常奢侈了。這裡提出了q2.13編碼方式：

1 bit表達正負號，2 bits表達整數位，13 bits表達小數點右邊的值，總計是16 bits。用更少的bit來表達就意味著信息損失。但是演算法中要運用到對每一小步的累計值，不做處理就會對模型產生影響。具體解決策略為：

加入一個隨機的regret項:R，R符合標準高斯分布，值介於0和1之間。對係數進行round，保證其整體離散誤差為0：

實驗表明，使用了q2.13相較於64位浮點編碼可以節省75%的參數存儲RAM。

3.訓練多個相似的模型：

我們在做特徵篩選或者設置優化時，基於已有的訓練數據，控制變數，生成多個不同的變體來進行對比實驗是一個不錯的方法。但這樣做比較耗費資源。之前有一個比較省資源的方法是基於一個先驗模型，使用其他模型來預測殘差。但是這樣不能進行特徵移除和特徵替換的效果。這裡Google提出了一個方法，由於每個模型變體的相似度是很高的，一部分特徵是變體之間共享的，一部分特徵是變體獨有的。如果採用一張hashtable來存儲所有變體的模型參數，就可以攤銷各個模型都進行獨立存儲key的內存消耗。而且也同時會降低看網路帶寬,CPU,磁碟的消耗。

4.A Single Value Structure：

這個是指不同模型變體之間共享一個特徵參數，而不是每一個模型變體存儲單獨的一個。用一個位欄位來標識這個特徵被哪些變體使用。

更新的方式如下：每一個模型變體去進行prediction並計算loss，然後對於每一個特徵給出一個迭代後的參數值。對所有的更新後的參數值進行平均並進行更新存儲。

5.使用正負樣本的數目來計算梯度之和：

前面提到學習率的計算per-coordinate learning rates，要對梯度的平方要進行累計。這裡給出了一個粗獷的梯度平方累計近似解決方案：

6.對訓練數據進行抽樣處理：

實際CTR問題中，點擊率遠遠低於50%，一般在1%左右，那就意味著負樣本數量遠超正樣本數量。做數據重採樣不僅能平衡正負樣本比例，還可以在不影響整體準確度的情況下降低訓練集大小。具體的篩選規則描述如下：

1）query對應至少一個ad點擊的全採樣；

2）query不對應任何ad點擊的按r比例採樣；

然後對樣本進行權重修正；

模型效果評估：

評測模型效果一般基於歷史數據，綜合很多指標來進行評估，比如AucLoss，LogLoss，SquaredError等。下面是Google進行模型評估時的嘗試：

1.Progressive Validation：

普通的話，一般是從訓練集里抽一部分出來做test，但Google認為都不如online test.online test可以反饋在最近的query數據上的效果，可以使用100%的數據做測試和訓練。

由於不同的國家，不同的時間點，不同的query下，指標的benchmark是不同的，而相對指標變化是穩定的，應該關注指標的相對值。同時也說明觀察模型效果要對數據進行切片觀察。

2.Deep Understanding through Visualization：

我們看到的模型整體提升是一個聚合結果，可能只發生在某一個slice上的效果提升了，其他slice並沒有或者發生下降。我們可以利用天生對圖像的敏感進行不同維度切分下指標的可視化來表達模型的表現。

於是，Google開發了一個web可視化工具GridViz，可以可視化不同變體在不同slice上的指標變化。通過不同的冷暖色，不同的透明程度來表達升高降低，以及對應的幅度信息。

置信度評估：

前面說了CTR預測是怎麼發生的，但在實際場景中只預測click發生的概率是不夠的，還要對這個預測進行一個置信度評估，來達到explore/exploit E&E問題的一個tradeoff。一方面做出精準的預測，把比較好的廣告符合用戶興趣的廣告展示出來，但是這類數據總歸是少的；公司總是要賺錢的，而且也廣告主的需求，將一些展示次數比較少的廣告也展示出來。

傳統標準的置信度評估方法不適合這個場景，原因在於：

1）標準方法需要完全收斂的沒有正則批處理模型。不符合；

2）標準方法需要NxN的矩陣，在Google場景下N的量級是billion，無奈放不下；不符合；

2）實際場景中，計算置信度的時間應該與做ctr判定在一個數量級上；

Google提出了一個uncertainty score來進行評估：核心思想在於對每一個特徵的頻次進行計數，該頻次決定這學習率，學習率越小則該特徵更可信。與我們的ituition是相符的。U(X)即對應的score，公式如下，