【閱讀筆記】快手OCPX廣告冷啟動(dòng)影子價(jià)格法

本文為閱讀張任宇老師論文《Cold Start on Online Advertising Platforms: Data-Driven Algorithms and Field Experiments》的讀書(shū)筆記。據(jù)張老師分享，該方法目前被應(yīng)用到快手廣告線(xiàn)上冷啟動(dòng)，取得了不錯(cuò)的收益。

問(wèn)題背景

信息流廣告冷啟動(dòng)面臨的核心技術(shù)問(wèn)題:

  1. 新廣告數(shù)據(jù)量不足，其價(jià)值難以準(zhǔn)確預(yù)估
  2. 合理分配廣告流量，平衡消耗與冷啟動(dòng)價(jià)值
優(yōu)化目標(biāo)

找到合適的廣告推送策略，最大化消耗與冷啟動(dòng)收益之和

符號(hào)說(shuō)明

廣告集合A:\{1,2,...,k\}

轉(zhuǎn)化出價(jià)b:\{b_1,b_2,...,b_k\}

y_{t,j}表示廣告j是否被展現(xiàn)給用戶(hù)t=1,2,3,...,T

x_t=i表示第t個(gè)用戶(hù)的特征i

c_{i,j}=ctr 在特征i下廣告j的實(shí)際點(diǎn)擊率

\hat{c_{t,i,j}}=pctr 用戶(hù)t特征i下廣告j的預(yù)估點(diǎn)擊率

cv_{i,j}=ctr*cvr

\hat{cv_{t,i,j}}=pctr*pcvr

\beta_j 表示冷啟動(dòng)時(shí)單次轉(zhuǎn)化的價(jià)值(設(shè)為2b_i)

\alpha T 冷啟動(dòng)成功的閾值(設(shè)為10)

問(wèn)題建模

maxV(y_{s,j})=\sum_{s\leq t-1}\sum_{j\in A}\hat{cv_{t,i,j}}*b_j*y_{s,j}+\sum_{j\in A}\beta_j * min\{(\sum_{s\in t-1}\hat{cv_{t,i,j}}*y_{s,j}),\alpha(t-1) \}

其中第一項(xiàng)里面其實(shí)就是pctcvr*cpa*isShow，也就是ecpm。

第二項(xiàng)是取當(dāng)前轉(zhuǎn)化數(shù)\sum_{s\in t-1}\hat{cv_{t,i,j}}*y_{s,j}和冷啟動(dòng)閾值\alpha (t-1)的最小值，再乘以冷啟動(dòng)單個(gè)轉(zhuǎn)化價(jià)值\beta_j得到冷啟動(dòng)總價(jià)值。

約束條件：
s.t. \{ y_{s,j}\geq 0, \sum_{j \in A} y_{s,j} \leq 1\}
第一個(gè)約束是說(shuō)一個(gè)廣告要么曝光要么沒(méi)曝光。
第二個(gè)約束是說(shuō)對(duì)于一個(gè)用戶(hù)，假設(shè)所有廣告中總是只有小于等于一個(gè)廣告獲得展現(xiàn)。

對(duì)偶問(wèn)題推導(dǎo)

由于原問(wèn)題維數(shù)為T(mén)*K，即用戶(hù)數(shù)x廣告數(shù)，維數(shù)太高不好求解，需要轉(zhuǎn)化到對(duì)偶空間。

先做一次線(xiàn)性化：
maxV(y_{s,j})=\sum_{s\leq t-1}\sum_{j\in A}\hat{cv_{t,i,j}}*b_j*y_{s,j} +\sum_{j\in A}\beta_j * [ \alpha(t-1)- \mu_j]

其中\mu_j為廣告離冷啟動(dòng)閾值還差多少個(gè)轉(zhuǎn)化

s.t.
y_{s,j}\geq 0, \sum_{j \in A} y_{s,j} \leq 1,\forall s \leq t-1 , \forall j \in A
\sum_{s \leq t-1}\hat{cv_{t,i,j}}*y_{s,j} + \mu_j \geq \alpha(t-1)

為簡(jiǎn)化問(wèn)題，忽略其他約束，只考慮最后一個(gè)約束條件，寫(xiě)出其增廣拉格朗日公式

L(y,\lambda)= \sum_{s\leq t-1}\sum_{j\in A}\hat{cv_{t,i,j}}*b_j*y_{s,j}+
\sum_{j\in A}\beta_j * [ \alpha(t-1)- \mu_j]+
\sum_{j \in A}\lambda_j\{\sum_{s \leq t-1}\hat{cv_{t,i,j}}*y_{s,j} + \mu_j - \alpha(t-1)\}
展開(kāi)得
L(y,\lambda)= \sum_{s\leq t-1}\sum_{j\in A}\hat{cv_{t,i,j}}*b_j*y_{s,j}
+\sum_{j \in A}\lambda_j \sum_{s \leq t-1}\hat{cv_{t,i,j}}*y_{s,j}
+\sum_{j \in A}\lambda_j( \mu_j - \alpha(t-1))
+\sum_{j\in A}\beta_j * [ \alpha(t-1)- \mu_j]
化簡(jiǎn)得
L(y,\lambda)= \sum_{s\leq t-1}\sum_{j\in A}\hat{cv_{t,i,j}}*(b_j+\lambda_j)*y_{s,j}
+\sum_{j \in A}\mu_j(\lambda_j-\beta_j)
+\sum_{j\in A}\beta_j * [ \alpha(t-1)]
-\alpha (t-1) \sum_{j \in A}\lambda_j

按(\lambda_j-\beta_j)分類(lèi)討論求sup_y L(y,\lambda)。

當(dāng)(\lambda_j-\beta_j) \leq 0時(shí)候，在0處取得sup。又由一個(gè)隊(duì)列只能有一個(gè)展現(xiàn)，可以約掉廣告集合的求和項(xiàng)，得
sup_yL(y,\lambda)= \sum_{s\leq t-1}\max\{\hat{cv_{t,i,j}}*(b_j+\lambda_j)\}
+\sum_{j\in A}\beta_j * [ \alpha(t-1)]
-\alpha (t-1) \sum_{j \in A}\lambda_j
否則，sup_y L(y,\lambda)為正無(wú)窮。
g(\lambda)=sup_yL(y,\lambda)
f(\lambda)=min. g(\lambda)
略去跟自變量\lambda無(wú)關(guān)的常數(shù)項(xiàng)，得
f(\lambda)=min\{ \sum_{s\leq t-1}\max\{\hat{cv_{t,i,j}}*(b_j+\lambda_j)\} - \alpha (t-1) \sum_{j \in A}\lambda_j \}
s.t.
\lambda_j \in [0,\beta_j]

這個(gè)對(duì)偶問(wèn)題的第一項(xiàng)我們可以看成是調(diào)整后的新ecpm。

我們對(duì)廣告主競(jìng)價(jià)b_j加了一個(gè)“影子出價(jià)”\lambda_j來(lái)增加新廣告的曝光率以提升長(zhǎng)期冷啟動(dòng)的價(jià)值。

冷啟動(dòng)價(jià)值系數(shù)\beta_j則是最優(yōu)影子出價(jià)\lambda_j的上界。

求解對(duì)偶問(wèn)題

主函數(shù)為凸函數(shù)，線(xiàn)上使用Sub-Gradient Descent Method（次梯度下降法）對(duì)其進(jìn)行求解。

其次梯度為:
g_j=\frac{\partial f(\lambda)}{\partial \lambda_j}= \sum_{s\leq t-1}\hat{cv_{t,i,j}}*I(\lambda_j)-\alpha(t-1)
其中，I是示性函數(shù)，當(dāng)廣告j的新ecpm排名最高時(shí)，I為1，否則I為0。
\lambda_j^{(k+1)}=\lambda_j^{(k)}-t_k * g^{(k)}
這里k為迭代次數(shù)，t_k為步長(zhǎng)。
迭代終止條件為:
f(\lambda_j^{(k+1)})-f(\lambda_j^{(k)})<\epsilon
此次\lambda更新完成。

線(xiàn)上實(shí)現(xiàn)基本思路

MAB+Linear Programming

Shadow Bidding with Learning(SBI)算法

對(duì)于每個(gè)時(shí)刻：

  1. 觀(guān)測(cè)用戶(hù)特征x_t=i，以\epsilon_t=t^{-\frac{1}{3}}(Klogt)^{\frac{1}{3}}概率隨機(jī)等可能展示一個(gè)廣告;以1-\epsilon的概率展示廣告argmax_j({\hat{cv_{t,i,j}}}*(b_j+\lambda_j))

  2. 到了需要更新的時(shí)刻，解empirical dual；更新冷啟動(dòng)廣告的影子出價(jià)\lambda

  3. 更新DNN模型以及對(duì)應(yīng)的pCTR,pCVR.

實(shí)驗(yàn)結(jié)論

SBI算法幾乎能達(dá)到“上帝視角”的最優(yōu)價(jià)值。

AB實(shí)驗(yàn)冷啟動(dòng)成功率+61.62%，冷啟動(dòng)價(jià)值+47.71%，CTR預(yù)測(cè)的AUC+7.84%，短期消耗和超成本情況幾乎不變。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容