美文网首页
【阅读笔记】快手OCPX广告冷启动影子价格法

【阅读笔记】快手OCPX广告冷启动影子价格法

作者: 子游同学 | 来源:发表于2020-12-16 21:55 被阅读0次

本文为阅读张任宇老师论文《Cold Start on Online Advertising Platforms: Data-Driven Algorithms and Field Experiments》的读书笔记。据张老师分享，该方法目前被应用到快手广告线上冷启动，取得了不错的收益。

问题背景

信息流广告冷启动面临的核心技术问题:

  1. 新广告数据量不足，其价值难以准确预估
  2. 合理分配广告流量，平衡消耗与冷启动价值
优化目标

找到合适的广告推送策略，最大化消耗与冷启动收益之和

符号说明

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

转化出价b:\{b_1,b_2,...,b_k\}

y_{t,j}表示广告j是否被展现给用户t=1,2,3,...,T

x_t=i表示第t个用户的特征i

c_{i,j}=ctr 在特征i下广告j的实际点击率

\hat{c_{t,i,j}}=pctr 用户t特征i下广告j的预估点击率

cv_{i,j}=ctr*cvr

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

\beta_j 表示冷启动时单次转化的价值(设为2b_i)

\alpha T 冷启动成功的阈值(设为10)

问题建模

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) \}

其中第一项里面其实就是pctcvr*cpa*isShow，也就是ecpm。

第二项是取当前转化数\sum_{s\in t-1}\hat{cv_{t,i,j}}*y_{s,j}和冷启动阈值\alpha (t-1)的最小值，再乘以冷启动单个转化价值\beta_j得到冷启动总价值。

约束条件：
s.t. \{ y_{s,j}\geq 0, \sum_{j \in A} y_{s,j} \leq 1\}
第一个约束是说一个广告要么曝光要么没曝光。
第二个约束是说对于一个用户，假设所有广告中总是只有小于等于一个广告获得展现。

对偶问题推导

由于原问题维数为T*K，即用户数x广告数，维数太高不好求解，需要转化到对偶空间。

先做一次线性化：
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为广告离冷启动阈值还差多少个转化

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)

为简化问题，忽略其他约束，只考虑最后一个约束条件，写出其增广拉格朗日公式

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)\}
展开得
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]
化简得
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)分类讨论求sup_y L(y,\lambda)。

当(\lambda_j-\beta_j) \leq 0时候，在0处取得sup。又由一个队列只能有一个展现，可以约掉广告集合的求和项，得
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)为正无穷。
g(\lambda)=sup_yL(y,\lambda)
f(\lambda)=min. g(\lambda)
略去跟自变量\lambda无关的常数项，得
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]

这个对偶问题的第一项我们可以看成是调整后的新ecpm。

我们对广告主竞价b_j加了一个“影子出价”\lambda_j来增加新广告的曝光率以提升长期冷启动的价值。

冷启动价值系数\beta_j则是最优影子出价\lambda_j的上界。

求解对偶问题

主函数为凸函数，线上使用Sub-Gradient Descent Method（次梯度下降法）对其进行求解。

其次梯度为:
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是示性函数，当广告j的新ecpm排名最高时，I为1，否则I为0。
\lambda_j^{(k+1)}=\lambda_j^{(k)}-t_k * g^{(k)}
这里k为迭代次数，t_k为步长。
迭代终止条件为:
f(\lambda_j^{(k+1)})-f(\lambda_j^{(k)})<\epsilon
此次\lambda更新完成。

线上实现基本思路

MAB+Linear Programming

Shadow Bidding with Learning(SBI)算法

对于每个时刻：

  1. 观测用户特征x_t=i，以\epsilon_t=t^{-\frac{1}{3}}(Klogt)^{\frac{1}{3}}概率随机等可能展示一个广告;以1-\epsilon的概率展示广告argmax_j({\hat{cv_{t,i,j}}}*(b_j+\lambda_j))

  2. 到了需要更新的时刻，解empirical dual；更新冷启动广告的影子出价\lambda

  3. 更新DNN模型以及对应的pCTR,pCVR.

实验结论

SBI算法几乎能达到“上帝视角”的最优价值。

AB实验冷启动成功率+61.62%，冷启动价值+47.71%，CTR预测的AUC+7.84%，短期消耗和超成本情况几乎不变。

相关文章

网友评论

      本文标题：【阅读笔记】快手OCPX广告冷启动影子价格法

      本文链接：https://www.haomeiwen.com/subject/wcnogktx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|【阅读笔记】快手OCPX广告冷启动影子价格法|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！