[KDD2017]Optimized Cost per Click in Taobao Display Advertising

最近工作中涉及到OCPC(Optimized Cost per Click)相关的部分，之前确实没仔细看过OCPC的细节，翻出论文来仔细阅读和记录一下。

Link：https://arxiv.org/abs/1703.02091

文章写作的时间点是2017年初，恰好经过了2016年的双十一，其实从近几年的展示广告的发展来看，基于PV的广告形式对广告主和平台来说越来越吃力。其中就涉及到展示广告的常见计价方式，CPM(Cost per Mile)和CPC(Cost per Click)的博弈问题。

整体思路

文中以手淘的首焦位置（Banner CPC Ads, 用于单品、店铺和品牌营销的广告展示）和推荐瀑布流（Item CPC Ads，3/200个推荐位用于展示广告）为例，指出了当前展示广告CPC模式的一个困境，广告系统是需要将广告主付费的，合适的广告展示给最合适(最可能点击)的到访客户，用来赚取被点击的广告的费用。在这个过程中，每一方的利益公式为：

$$ \begin{equation} \begin{aligned} Income_{广告系统} \approx eCPM & = pCTR * bid_{click}\\ Income_{广告主} \approx GMV_{total} & = pCTR * pCVR * price \end{aligned} \end{equation} $$

从中不难看出，平台是按照CPM计价的，也就是说，广告主预先设定好$bid_{click}$，广告系统对每一位到访的客户预估其相关广告的$pCTR$，然后按照$eCPM = pCTR * bid_{click}$ 进行排序，高者优先。但广告主的收益公式中的$pCVR$和$price$并没有体现在广告系统的排序中，那么此处产生了利益分歧，从广告系统侧来讲，只要尽可能的让广告主提高广告预算，即$bid_{click}$就可以获得更多收益。但这个过程是单方面收入增加的、简单粗暴、不可持续的，广告主的收入没有增加的情况下，付出更加沉重的成本将会成为压死骆驼的最后一根稻草——广告主掏不出更多的钱来继续提高竞价，会直接破坏掉广告主参与的积极性，导致最后整个平台生态破坏。

作为广告主，也会有一个评价指标来指导自己对$bid_{click}$的开价：

$$ROI_{click} = \frac{GMV_{click}}{bid_{click}} = \frac{pCTR * pCVR * price}{bid_{click}}$$

很明显，如果要保证$ROI_{click}$不变的话，$bid_{click}$与$pCVR$是线性相关的，换句话说，如果系统可以根据$pCVR$帮助广告主动态调整出价的话，那么就可以保证广告主的$ROI$稳定，甚至提升。

分步推导和实现细节

优化范围

ROI约束

假设用户$u$点击了广告$a$，产生交易的概率为：$p(c|u,a)$，并且定义$PPB$（pay-per-buy每次购买付款，也就是商家设定的商品价格—$price$）为：$v_{a}$。因为这次点击广告主需要付的费用为$b_{a}$（此处暂且不考虑由于广义二价GSP导致的费用偏差），那么可知：

$$ GMV_{click-and-buy} = p(c|u,a) * v_{a} $$ $$ roi_{(u,a)} = \frac{GMV_{click-and-buy}}{b_{a}} = \frac{p(c|u,a) * v_{a}}{b_{a}} $$

假设$n_{u}$是广告系统运行的一段时间内某个用户$u$对广告$a$的总点击数，我们认为$E_{u} \lbrack p(c|u,a) \rbrack$是$pCVR$的预估均值，那么：

$$ roi_{a} = \sum_{}roi_{(u,a)} = \frac{v_{a} \cdot \sum_{n}n_{u} \cdot p(c|u,a)}{b_{a} \cdot \sum_{u}{n_{u}}} = \frac{E_{u} \lbrack p(c|u,a) \rbrack \cdot v_{a}}{b_{a}} $$

上述式子$roi_{a}$就是oCPC优化问题中的约束条件，即$roi_{a}$不降低或者有上涨。在阿里的论文中，为了防止异常值和离群点，对$pCVR$进行了截断$E_{u} \lbrack p(c|u,a) \rbrack = Average(Trim(pCVR, \lbrack 10\%,90\% \rbrack))$。

Bid优化上下界

假设$b_{a}^*$是某一次广告出价$bid_{click}$，那么只要满足以下公式就可以保证$roi$不降低。

$$ \frac{b_{a}^*}{b_{a}} \le \frac{p(c|u,a)}{E_u \lbrack p(c|u,a) \rbrack} $$

但是很显然，商业竞价环境中并不能够保证每次的出价$b_{a}^*$都能保证$roi$不降低，那么文中给出了经验公式，并划定了可行域。其中$r_{a}$是一个调节系数，用来衡量广告位置差，流量质量低的情况下，对用户点击意愿的妥协程度系数。

\begin{equation} Lower Bound: l(b_{a}^*) = \left\{ \begin{array}{lr} {b_{a} \cdot (1-r_{a})}, & \frac{p(c|u,a)}{E_{u} \lbrack p(c|u,a) \rbrack} \lt 1 \\ b_{a}, & \frac{p(c|u,a)}{E_{u} \lbrack p(c|u,a) \rbrack} \ge 1 \end{array} \right. \\ Upper Bound: u(b_{a}^*) = \left\{ \begin{array}{lr} b_{a}, & \frac{p(c|u,a)}{E_{u} \lbrack p(c|u,a) \rbrack} \lt 1 \\ b_{a} \cdot min(1 + r_{a}, \frac{p(c|u,a)}{E_{u} \lbrack p(c|u,a) \rbrack}), & \frac{p(c|u,a)}{E_{u} \lbrack p(c|u,a) \rbrack} \ge 1 \end{array} \right. \end{equation}

从上述公式不难看出，可行域如图所示：

排序公式

在可行域中选取不同的$b_{a}^*$，会导致目前以$eCPM$作为排序机制的排序结果的改变，假设我们想要在$eCPM$的机制下展示一条广告$k$，并且希望$k$能够最大化我们的排序目标公式$f(\cdot)$：

$f(\cdot)$的最原始形式是只考虑$pctr$，故$f(k,b_{k}^*) = pctr_{k} * b_{k}^*$

\begin{equation} \begin{aligned} \underset{b_{1}^*, \cdots, b_{n}^*}{max} \quad & f(k, b_{k}^*) \\ s.t. \quad & k = \underset{i}{argmax} \quad pctr_{i} * b_{i}^* \\ \quad & l(b_{i}^*) \lt b_{i}^* \lt u(b_{i}^*), \forall i \in A \end{aligned} \end{equation}

接下来我们分别考虑两种排序公式：

\begin{equation} \begin{aligned} consider \: GMV: \: f_{1}(k,b_{k}^*) &= pctr_{k} * pcvr_{k} * v_{k} \\ consider \: GMV + eCPM: \: f_{2}(k,b_{k}^*) &= pctr_{k} * pcvr_{k} * v_{k} + \alpha * pctr_{k} * b_{k}^* \end{aligned} \end{equation}

假设

\begin{equation} s_{a}^* = pctr_{a}^* \cdot b_{a}^* \begin{aligned} \rightarrow \left\{ \begin{array}{lr} l(s_{a}^*) &= pctr_{a}^* \cdot l(b_{a}^*) \quad lower bound \\ u(s_{a}^*) &= pctr_{a}^* \cdot u(b_{a}^*) \quad upper bound \end{array} \right. \end{aligned} \end{equation}

天然的，$pctr$和$pcvr$等指标非负，并且在一般意义下，$b_{k}^*$高将会持续导致与其相关的$pctr$等指标提升（这里有个比较弱的假设，甚至可以认为广告系统近似等于一个增强学习环境，会导致样本整体出现受出价引导的$Bias$现象），会在一定程度上保证(原文中采用假设的方式)了$f(k,b_{k}^*)$函数对$b_{k}^*$单调不减。

由以上的假设可以认为，我们只要将所有的$f(k,u(b_{k}^*))$按照降序排列，并且按顺序找出来排位第一的广告$k$，就是我们要找的广告，并且满足以下的条件：

\begin{equation} \begin{aligned} u(s_{k}*) & \ge l(s_{i}^*) \qquad \forall i \ne k \\ b_{k}^* & = u(b_{k}^*) \end{aligned} \end{equation}

刚刚是在假设一次性只展示一条广告的情况下，若一次需要展示$N$条广告的话，那么作者给出了一个贪心策略来实现广告排序。假设一次展示$n$条广告$k_{1} \cdots k_{n}$。如何保证$Position_{i}$的广告恰好对应$k_{i}$。

\begin{equation} \begin{aligned} Step1: \qquad & 按照仅有1个广告被展示的情况先确定广告k_{1} \\ Step2: \qquad & 将其余的广告条目的上限改为k_{1},即 \\ & u(b_{i}^*) \le u(b_{k_{1}}) \qquad \forall i \ne k_{1} \\ Repeat: \qquad & Step1-2 \end{aligned} \end{equation}

算法细节

校正

从作者的历史经验来看，$oCPC$中的$pCVR$预估值存在偏低的现象，作者提出了一个经验校正公式：

\begin{equation} p(c|u,a) = \begin{aligned} \left\{ \begin{array}{lr} p(c|u,a), & p(c|u,a) \lt tc \\ p(c|u,a) * (1 + log(\frac{p(c|u,a)}{tc})), & p(c|u,a) \ge tc \end{array} \right. tc = 0.012 \end{aligned} \end{equation}

cCPC算法复杂度

整个oCPC算法包含两个部分：$Ranking和Calibration$，总起来的算法复杂度为$O(N * \vert\vert A\vert\vert * log\vert\vert A\vert\vert)$，是$N$的线性关系，通常$A和N$不是太大，那么足以提供online serving。

模型效果

文中提到用于验证的模型结构为MLR，其中包含有三类特征，用户特征，广告特征，上下文特征。在对oCPC指标的评估时，会涉及到pCTR、pCVR以及这两者相互影响的因素，很容易出现AUC虚高的情况，故作者提出GAUC(Group AUC)指标，对广告位置$p$和用户$u$进行组合后分组，并在计算AUC时进行加权 $w(u,p)$ ：

$$GAUC = \frac{\sum_{(u,p)}{}w_{(u,p)} * AUC_{u,p)}}{\sum_{(u,p)}{}w_{(u,p)}}$$

实验结果

在这个阶段作者给出了四种策略来证明oCPC的优越性，其中提到了一种实验中印证效果较高的 $f(k,b_{k}^*)$ 变种：

$$f(k,b_{k}^*) = pctr_{k} * b_{k}^* * (1 + \sigma (\frac{pcvr_{k} * v_{k} * \vert\vert A \vert\vert}{\sum_{i \in A}{}pcvr_{i} * v_{i}},w) * r_{a})$$ 其中$w = 6,r_{a} = 0.4$

最终在线效果看来，RPM、GPM、ROI三项指标均在提升，确实实现了广告主、广告系统、用户的共赢。

衍生和扩展

其实在文中作者也说，这个oCPC的思路其实可以扩展到更多的场景上，确实是动态定价这个方向上的一个通用框架型的工作，不妨来扩展一下思路，oCPM、oCPA及相应的变种oCPC(C->Cart)、oCPI(I->Install)、oCPS(S->Share)

电商网站常见的计价模式

模式	计价方式	含义	排序指标
CPM	$bid_{impression}$	千次展现计费	$eCPM = bid_{impression}$
CPC	$bid_{click}$	每次点击计费	$eCPM = pCTR * bid_{click}$
CPA/CPS/CPI	$bid_{action}$	每次行为计费(转化、销售、安装等)	$eCPM = pCTR * pCVR * bid_{action}$
OCPC	$bid_{click}$	带动态出价的点击后的转化计费	$eCPM = pCTR * pCVR * bid_{post-click-action}$
OCPA	$bid_{action}$	带动态出价的行为后的转化计费	$eCPM = pCTR * pCVR * bid_{post-action-action}$
OCPM	$bid_{impression}$	带动态出价的展现后的转化计费	$eCPM = pCTR * bid_{impression}$

其实Facebook早在2014年就已经实现了oCPM，相关的资料见[官网][https://developers.facebook.com/docs/marketing-api/cost-per-action-ads]