論文Modeling Delayed Feedback in Display Advertising閱讀筆記
Abstract
- 評估廣告投放效果的重要名額：轉化率(conversion rate) —– 在廣告網站上采取行動的人占總浏覽人數的比例。使用機器學習預估 conversion rate，進而預估收益。
- 然而conversion很可能延時發生，比如看過一個商品廣告，當時有些心動但并沒有馬上去買，過了幾天按捺不住又去購買（Delayed Feedback），給模組化帶來困難。
- 這篇文章提出機率模型，對未采取行動的客戶進行判别：可能會買or不可能會買
Introduction
廣告計費模式：參考學習: 網絡廣告中，CPC、CPA、CPM 的定義各是怎樣的？
這篇文章集中在CPA(cost per action)模式，更确切的說，是post-click conversion（點選後轉化，轉化被歸因到之前的點選）。隻有産生了預先商定的行動才付費。支援CPA模式的平台，就需要将廣告标價，轉化為eCPM(期望CPM），取決于conversion rate。
轉化的延遲回報特性導緻構件訓練集，設定比對視窗長度的困難：過短則漏掉部分conversion；過長則導緻模型停滞。
本文生成訓練集時，将樣本标記為positive和unlabeled，需要從正例和未标記資料中進行學習，但都假定标記正例從正類中随機選擇，标簽缺失的機率恒定。但與本文所讨論的情形不同：點選剛發生時，标簽最易缺失。
本文引入模型II捕捉點選和轉化之間的期望延遲，這有點類似于survival time analysis(生存時間分析，指治療開始和患者死亡之間的時間)。有一些時間是截斷（conversion一直沒有發生）的， 這表明延遲（或者生存）時間至少是那個截斷時間。
然而病人終有一死，而客戶卻未必轉化。這就需要兩個模型：一個預測是否轉化；另一個預測相應的延遲時間。這兩個模型共同訓練，共同配置設定結果。
資料來源：Criteo流量日志；營利模式：收益（CPC/CPA，廣告商）- 成本（CPM，出版商）
Conversions
Post-Click Attribution
post-view attribution: 将轉化歸因于之前的一次或幾次浏覽
post-click attribution: 将轉化歸因于被點選的廣告
本文轉化時間視窗長度固定為：30天
比對除了時間窗要求，還要有相同的使用者id和廣告商。在多次點選導緻一次轉化時，按照行業标準歸因于最後一次點選。若有多次轉化比對一次點選，則隻保留第一個。也就是說，本文不考慮，單次點選導緻多次轉化的情形。
Conversion Rate Prediction
eCPM=CPA×Pr(conversion,click) e C P M = C P A × P r ( c o n v e r s i o n , c l i c k )
=CPA×Pr(click)×Pr(conversion|click) = C P A × P r ( c l i c k ) × P r ( c o n v e r s i o n | c l i c k )
條件機率分解能降低資料負載，并且在沒有conversion時仍能提供一定的click資訊。模組化Pr(click)需要可擴充的模型：單一平台每日廣告投放量可達數十億，而點選回報是即時的；模組化Pr(conversion | click)規模較小，但有回報延遲。
Analysis of the Conversion Delay
New Campaigns
廣告展示的各個因素都在持續變化，當新的活動被加入系統時，原來訓練好的模型效能将會降低：Keep the model fresh！
在圖2中，新活動的比例持續增長，這預示着30天的長時間窗模型将受到影響。
Model
- X X ：特征集
- Y∈{0,1}Y∈{0,1}：轉化是否已經發生
- C∈{0,1} C ∈ { 0 , 1 } ：使用者是否終會轉化
- D D ：點選和轉化之間的延遲
- EE：點選後已經流逝的時間
Y=0⟺C=0 or E<D Y = 0 ⟺ C = 0 o r E < D
Y=1⟹C=1 Y = 1 ⟹ C = 1
獨立性假設： Pr(C,D|X,E)=Pr(C,D|X) P r ( C , D | X , E ) = P r ( C , D | X )
也就是說，在這個模型中，不根據已經過了多久來判斷轉化最終是否發生和最終延遲時間。
給定資料集： (xi,yi,ei) ( x i , y i , e i ) ，如果 yi=1 y i = 1 ，還有相應的 di d i 值。
用兩個參數模型拟合資料： Pr(C|X),Pr(D|X,C=1) P r ( C | X ) , P r ( D | X , C = 1 )
訓練好以後，前者被用來預測轉換機率，後者被抛棄
這兩個模型都是廣義線性模型：前者是标準的邏輯回歸：
Pr(C=1|X=x)=p(x),p(x)=11+exp(−wc⋅x) P r ( C = 1 | X = x ) = p ( x ) , p ( x ) = 1 1 + exp ( − w c ⋅ x )
後者是延遲的指數分布：
Pr(D=d|X=x,C=1)=λ(x)exp(−λ(x)d) P r ( D = d | X = x , C = 1 ) = λ ( x ) exp ( − λ ( x ) d )
其中，為了保證 λ(x)>0 λ ( x ) > 0 ，令 λ(x)=exp(wd⋅x) λ ( x ) = exp ( w d ⋅ x )
則該模型的參數就是 wc,wd w c , w d
Pr(Y=1,D=di|X=xi,E=ei) P r ( Y = 1 , D = d i | X = x i , E = e i )
=Pr(C=1,D=di|X=xi,E=ei) = P r ( C = 1 , D = d i | X = x i , E = e i )
=Pr(C=1,D=di|X=xi) = P r ( C = 1 , D = d i | X = x i )
=Pr(D=di|X=xi,C=1)Pr(C=1|X=xi) = P r ( D = d i | X = x i , C = 1 ) P r ( C = 1 | X = x i )
=λ(xi)exp(−λ(xi)di)p(xi) = λ ( x i ) exp ( − λ ( x i ) d i ) p ( x i )
Pr(Y=0|X=xi,E=ei) P r ( Y = 0 | X = x i , E = e i )
=Pr(Y=0|C=0,X=xi,E=ei)Pr(C=0|X=xi) = P r ( Y = 0 | C = 0 , X = x i , E = e i ) P r ( C = 0 | X = x i )
+Pr(Y=0|C=1,X=xi,E=ei)Pr(C=1|X=xi) + P r ( Y = 0 | C = 1 , X = x i , E = e i ) P r ( C = 1 | X = x i )
=1−p(xi)+p(xi)exp(−λ(xi)ei) = 1 − p ( x i ) + p ( x i ) exp ( − λ ( x i ) e i )
⇑ ⇑
Pr(Y=0|C=1,X=xi,E=ei)=Pr(D>E|C=1,X=xi,E=ei) P r ( Y = 0 | C = 1 , X = x i , E = e i ) = P r ( D > E | C = 1 , X = x i , E = e i )
=∫∞eiλ(x)exp(−λ(x)t)dt=exp(−λ(x)ei) = ∫ e i ∞ λ ( x ) exp ( − λ ( x ) t ) d t = exp ( − λ ( x ) e i )
Optimization
Expectation-Maximization
EM算法學習參考:簡單易學的機器學習算法——EM算法
把 C C 看作隐藏變量
Joint Optimization
Loss Function:
argminwc,wdL(wc,wd)+μ2(||wc||22+||wd||22)argminwc,wdL(wc,wd)+μ2(||wc||22+||wd||22)
其中， μ μ 是正則化參數， L L 是負對數似然：
L(wc,wd)=−∑i,yi=1logp(xi)+logλ(xi)−λ(xi)diL(wc,wd)=−∑i,yi=1logp(xi)+logλ(xi)−λ(xi)di
−∑i,yi=0log[1−p(xi)+p(xi)exp(−λ(xi)ei)] − ∑ i , y i = 0 log [ 1 − p ( x i ) + p ( x i ) exp ( − λ ( x i ) e i ) ]
該優化問題是無限制且二次可微的，本文使用L-BFGS進行優化，可參考：優化算法——拟牛頓法之L-BFGS算法
Tips
這篇文章的主要貢獻：首次對延時回報進行模組化！
資料集：http://labs.criteo.com/tag/dataset
評價名額：平均負對數似然NLL
參數設定： μ:=1n||xi||22 μ := 1 n | | x i | | 2 2
![簡單文檔分類——樸素貝葉斯算法樸素貝葉斯算法簡單文檔分類執行個體步驟總結樸素貝葉斯分類調用(sklearn)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)