今天分享一篇解決延遲回報問題最經典的文章：《Modeling Delayed Feedback in Display Advertising》，于2014年發表在KDD上。
CVR預估的延遲回報問題
廣告場景中的CVR預估
CVR預估對廣告平台而言非常重要，平台往往可以通過選擇曝光給使用者不同的廣告而增加收益，假設廣告主對獲得一個使用者的價位 b i d bid bid，将廣告曝光給使用者後的期望點選率為 p c t r pctr pctr，點選後的激活率為 p c v r pcvr pcvr，則每次曝光的期望收益 e c p m ecpm ecpm即為：
e c p m = p c t r ∗ p c v r ∗ b i d ecpm=pctr*pcvr*bid ecpm=pctr∗pcvr∗bid
在曝光之前需要預估曝光後的點選率 p c t r pctr pctr與點選轉化率 p c v r pcvr pcvr，預估曝光的期望收益，進而優化曝光收益，由此可見pcvr預估的重要性。
延遲回報造成的後果
延遲回報現象非常普遍，使用者在點選某個廣告後往往需要經過一段時間之後才會付費，進而帶來收益，而這一轉化結果又需要一段時間才能傳回，是以從使用者點選物品到獲知該次點選是否發生轉化存在一定的時間間隔，這便是延遲回報現象，文中給出了延遲回報情況統計，對于30天内的回報資料，延遲情況如下：
大概50%轉化發生在一天以後，13%轉化發生在2周以後，如果在一天後劃分正負樣本，則僅有一半的正樣本能夠被正确标注，其他一半則被誤标記為負樣本，基于偏差如此大的資料訓練的模型效果可想而知。
從圖中可以看出延遲的日期比較符合指數分布，是以後續模組化時會用指數分布模型來拟合。
需要指出的是圖中的資料僅僅包含30天内回報的資料，如果考慮30天以上的轉化，真實的延遲回報現象可能更加嚴重。
模組化的必要性
一個很自然的想法是，既然大部分轉化有延遲，那是否可以等待更長時間，資料回流完成之後再對樣本進行标記和使用，事實上這是因為線上模型對實時性具有很高的要求，為了證明這一點，作者給出了新流量占比圖：
圖中的橫坐标代表日期，縱坐标代表該日期所有流量中新流量的占比，該指穩定上升，并在30天時達到了11%，若使用30天前的資料進行訓練，則有至少11%的資料是模型從未遇見過的，這是無法接受的。
模組化過程
模型建立
為了對延遲回報現象進行模組化，我們需要建立兩個模型，第一個模組化轉化是否會發生（即cvr預估），第二個模型模組化轉化發生的延遲。
第二個模型僅僅用于輔助第一個模型的訓練，線上上僅使用第一個模型進行CVR預估。
X表示所有特征（包括使用者、物品及其他上下文特征），C為01變量，表示最終是否發生轉化，Y表示01變量，表示目前是否已發生轉化，D表示點選到轉化之間的延遲長度（僅對C=1有定義），E表示點選到目前時刻經曆的時間。C和Y的關系可由下圖表示，若Y=1則必然C=1，若Y=0則C均有可能，即目前未發生轉化，但未來有可能發生。
模型1：使用邏輯回歸模型預測最終轉化率C，其中 w c w_c wc為待解參數：
P r ( C = 1 ∣ X = x ) = p ( x ) Pr(C=1|X=x)=p(x) Pr(C=1∣X=x)=p(x)
p ( x ) = 1 1 + e x p ( − w c ⋅ x ) p(x)=\frac{1}{1+exp(-w_c\cdot x)} p(x)=1+exp(−wc⋅x)1
模型2：預測延遲時間
假設延遲時間服從參數為 λ ( x ) \lambda(x) λ(x)的指數分布，則：
P r ( D = d ∣ X = x , C = 1 ) = λ ( x ) e x p ( − λ ( x ) d ) ) Pr(D=d|X=x, C=1)=\lambda(x)exp(-\lambda(x)d)) Pr(D=d∣X=x,C=1)=λ(x)exp(−λ(x)d))
作者認為不同的特征的延遲時間是不同的，比如有些使用者會很快給出回報，有些業務場景需要較長的等待，是以指數分布的參數 λ ( x ) \lambda(x) λ(x)應該與x有關，另一方面為了保證其恒為正，将其模組化為指數：
λ ( x ) = e x p ( w d ⋅ x ) \lambda(x)=exp(w_d\cdot x) λ(x)=exp(wd⋅x)
機率計算
如果我們知道 C C C的資訊，那麼可以直接訓練模型1中的參數 w c w_c wc，而實際上我們不知道 C C C，隻知道 Y Y Y與 D D D，是以需要使用模型表示出 Y Y Y與 D D D的聯合機率分布，再基于已知的它們的值建立損失函數，進而訓練模型中的參數。
首先計算圖中藍色部分，即 Y = 1 Y=1 Y=1部分的機率：
Pr ( Y = 1 , D = d i ∣ X = x i , E = e i ) = Pr ( D = d i ∣ X = x i , C = 1 ) Pr ( C = 1 ∣ X = x i ) = λ ( x i ) exp ( − λ ( x i ) d i ) p ( x i ) \begin{array}{l} \operatorname{Pr}\left(Y=1, D=d_{i} \mid X=\mathbf{x}_{i}, E=e_{i}\right) \\ =\operatorname{Pr}\left(D=d_{i} \mid X=\mathbf{x}_{i}, C=1\right) \operatorname{Pr}\left(C=1 \mid X=\mathbf{x}_{i}\right) \\ =\lambda\left(\mathbf{x}_{i}\right) \exp \left(-\lambda\left(\mathbf{x}_{i}\right) d_{i}\right) p\left(\mathbf{x}_{i}\right) \end{array} Pr(Y=1,D=di∣X=xi,E=ei)=Pr(D=di∣X=xi,C=1)Pr(C=1∣X=xi)=λ(xi)exp(−λ(xi)di)p(xi)
接下來計算Y=0的機率，這部分包括黃色區域和橘黃色區域，利用條件機率公式可得：
Pr ( Y = 0 ∣ X = x i , E = e i ) = Pr ( Y = 0 ∣ C = 0 , X = x i , E = e i ) P ( C = 0 ∣ X = x i ) + Pr ( Y = 0 ∣ C = 1 , X = x i , E = e i ) P ( C = 1 ∣ X = x i ) \begin{array}{l} \quad \operatorname{Pr}\left(Y=0 \mid X=\mathbf{x}_{i}, E=e_{i}\right) \\ =\operatorname{Pr}\left(Y=0 \mid C=0, X=\mathbf{x}_{i}, E=e_{i}\right) P\left(C=0 \mid X=\mathbf{x}_{i}\right) \\ +\operatorname{Pr}\left(Y=0 \mid C=1, X=\mathbf{x}_{i}, E=e_{i}\right) P\left(C=1 \mid X=\mathbf{x}_{i}\right) \end{array} Pr(Y=0∣X=xi,E=ei)=Pr(Y=0∣C=0,X=xi,E=ei)P(C=0∣X=xi)+Pr(Y=0∣C=1,X=xi,E=ei)P(C=1∣X=xi)
C的機率可直接使用模型1得到，而 C = 0 C=0 C=0的條件下 Y = 0 Y=0 Y=0的機率為1，是以隻需要計算求 C = 1 C=1 C=1的情況下 Y = 0 Y=0 Y=0的機率，實際上就是 D > E D>E D>E的機率，借助指數分布來計算。
Pr ( Y = 0 ∣ C = 1 , X = x i , E = e i ) = Pr ( D > E ∣ C = 1 , X = x i , E = e i ) = ∫ e i ∞ λ ( x ) exp ( − λ ( x ) t ) d t = exp ( − λ ( x ) e i ) \begin{aligned} \operatorname{Pr}(Y=0&\left.\mid C=1, X=\mathbf{x}_{i}, E=e_{i}\right) \\ &=\operatorname{Pr}\left(D>E \mid C=1, X=\mathbf{x}_{i}, E=e_{i}\right) \\ &=\int_{e_{i}}^{\infty} \lambda(\mathbf{x}) \exp (-\lambda(\mathbf{x}) t) d t \\ &=\exp \left(-\lambda(\mathbf{x}) e_{i}\right) \end{aligned} Pr(Y=0∣C=1,X=xi,E=ei)=Pr(D>E∣C=1,X=xi,E=ei)=∫ei∞λ(x)exp(−λ(x)t)dt=exp(−λ(x)ei)
Pr ( Y = 0 ∣ X = x i , E = e i ) = 1 − p ( x i ) + p ( x i ) exp ( − λ ( x i ) e i ) \operatorname{Pr}\left(Y=0 \mid X=\mathbf{x}_{i}, E=e_{i}\right)=1-p\left(\mathbf{x}_{i}\right)+p\left(\mathbf{x}_{i}\right) \exp \left(-\lambda\left(\mathbf{x}_{i}\right) e_{i}\right) Pr(Y=0∣X=xi,E=ei)=1−p(xi)+p(xi)exp(−λ(xi)ei)
這裡我們就借助兩個模型得到了y和d的聯合機率，接下來就可以借助标簽來構造損失函數了。
模型求解
損失函數：
arg min w c , w d L ( w c , w d ) + μ 2 ( ∥ w c ∥ 2 2 + ∥ w d ∥ 2 2 ) \arg \min _{\mathbf{w}_{c}, \mathbf{w}_{d}} L\left(\mathbf{w}_{c}, \mathbf{w}_{d}\right)+\frac{\mu}{2}\left(\left\|\mathbf{w}_{c}\right\|_{2}^{2}+\left\|\mathbf{w}_{d}\right\|_{2}^{2}\right) argwc,wdminL(wc,wd)+2μ(∥wc∥22+∥wd∥22)
其中：
L ( w c , w d ) = − ∑ i , y i = 1 log p ( x i ) + log λ ( x i ) − λ ( x i ) d i − ∑ i , y i = 0 log [ 1 − p ( x i ) + p ( x i ) exp ( − λ ( x i ) e i ) ] \begin{aligned} L\left(\mathbf{w}_{c}, \mathbf{w}_{d}\right) &=-\sum_{i, y_{i}=1} \log p\left(\mathbf{x}_{i}\right)+\log \lambda\left(\mathbf{x}_{i}\right)-\lambda\left(\mathbf{x}_{i}\right) d_{i} \\ &-\sum_{i, y_{i}=0} \log \left[1-p\left(\mathbf{x}_{i}\right)+p\left(\mathbf{x}_{i}\right) \exp \left(-\lambda\left(\mathbf{x}_{i}\right) e_{i}\right)\right] \end{aligned} L(wc,wd)=−i,yi=1∑logp(xi)+logλ(xi)−λ(xi)di−i,yi=0∑log[1−p(xi)+p(xi)exp(−λ(xi)ei)]
可以使用梯度下降法對損失函數進行優化，進而得到參數。
∂ L ∂ w c = ∑ i , y i = 1 − 1 p ( x i ) ∂ p ( x i ) ∂ w c + ∑ i , y i = 0 1 − exp ( − λ ( x i ) e i ) 1 − p ( x i ) + p ( x i ) exp ( − λ ( x i ) e i ) ∂ p ( x i ) ∂ w c \begin{aligned} \frac{\partial L}{\partial \mathbf{w}_{c}} &=\sum_{i, y_{i}=1}-\frac{1}{p\left(\mathbf{x}_{i}\right)} \frac{\partial p\left(\mathbf{x}_{i}\right)}{\partial \mathbf{w}_{c}} \\ +& \sum_{i, y_{i}=0} \frac{1-\exp \left(-\lambda\left(\mathbf{x}_{i}\right) e_{i}\right)}{1-p\left(\mathbf{x}_{i}\right)+p\left(\mathbf{x}_{i}\right) \exp \left(-\lambda\left(\mathbf{x}_{i}\right) e_{i}\right)} \frac{\partial p\left(\mathbf{x}_{i}\right)}{\partial \mathbf{w}_{c}} \end{aligned} ∂wc∂L+=i,yi=1∑−p(xi)1∂wc∂p(xi)i,yi=0∑1−p(xi)+p(xi)exp(−λ(xi)ei)1−exp(−λ(xi)ei)∂wc∂p(xi)
∂ L ∂ w d = ∑ i , y i = 1 ( d i − 1 λ ( x i ) ) ∂ λ ( x i ) ∂ w d + ∑ i , y i = 0 p ( x i ) e i exp ( − λ ( x i ) e i ) 1 − p ( x i ) + p ( x i ) exp ( − λ ( x i ) e i ) ∂ λ ( x i ) ∂ w d \begin{aligned} \frac{\partial L}{\partial \mathbf{w}_{d}} &=\sum_{i, y_{i}=1}\left(d_{i}-\frac{1}{\lambda\left(\mathbf{x}_{i}\right)}\right) \frac{\partial \lambda\left(\mathbf{x}_{i}\right)}{\partial \mathbf{w}_{d}} \\ +& \sum_{i, y_{i}=0} \frac{p\left(\mathbf{x}_{i}\right) e_{i} \exp \left(-\lambda\left(\mathbf{x}_{i}\right) e_{i}\right)}{1-p\left(\mathbf{x}_{i}\right)+p\left(\mathbf{x}_{i}\right) \exp \left(-\lambda\left(\mathbf{x}_{i}\right) e_{i}\right)} \frac{\partial \lambda\left(\mathbf{x}_{i}\right)}{\partial \mathbf{w}_{d}} \end{aligned} ∂wd∂L+=i,yi=1∑(di−λ(xi)1)∂wd∂λ(xi)i,yi=0∑1−p(xi)+p(xi)exp(−λ(xi)ei)p(xi)eiexp(−λ(xi)ei)∂wd∂λ(xi)
根據指數分布的定義，期望延遲時間為 1 λ ( x i ) \frac{1}{\lambda(x_i)} λ(xi)1，若 e i e_i ei遠小于期望預估時間，則 ∂ L ∂ w c \frac{\partial L}{\partial \mathbf{w}_{c}} ∂wc∂L的第二部分的分子接近于0，該項的影響很小，可以了解為難以确定該樣本是否未來會發生轉化，而當 e i e_i ei遠大于 1 λ ( x i ) \frac{1}{\lambda(x_i)} λ(xi)1時，則有較大把握認為其實負樣本，故該梯度有較大參考價值。
歡迎關注我的公衆号，了解算法崗面經、深圳教師招聘備考指南、程式猿的技術之旅與浪漫生活~