第11章：广告排序与机制设计
广告排序
工作方向
- 准入门槛：满足业务需求（平台方红线、各BU差异化出ad条件），保证用户体验。主要从距离、Item质量（星级）和pctr三个条件设定（优先级依次降低）；
- 机制排序：最大化三方收益。排序公式设计（考虑业务差异），超参数学习与优化，多目标优化，智能出价等；
技术方向
准入门槛优化
- 目标：通过门槛设计与优化，实现：既满足业务需要，保证用户体验的同时，最大化平台收益（RPS）；
- 主要手段：
- 距离：food、生活服务、酒店等对距离相对敏感；结婚对距离不敏感，可以不设置；
- item质量分：比如item星级，但要考虑新门店，该权重可以放宽；
- pCTR，pCVR等：静态门槛 $\rightarrow$ 动态门槛；$\color{red}{动态门槛如何实现？}$
排序公式
已有排序公式如下：
$$
\text{RankScore} = \text{Bid}^{\alpha} \cdot \text{Qualtiy}^{\beta}
$$
$$
\text{Qualtiy} = \underbrace{a_3 \cdot CTR}_{用户体验} + \underbrace{a_4 \cdot CTR^{a_6} \cdot CVR}_{访购率} + \underbrace{a_5 \cdot CTR \cdot CVR \cdot Price_{order}}_{GMV}
$$
公式设计的出发点：在质量分中考虑多目标优化。参数解读：
- $\alpha$：调控出价因子（默认为1）
- $\beta$: 调控质量分因子（默认为1）
- $a_3$: 点击率权重
- $a_4$: 访购率权重 (下单人数/浏览人数，$a_6$：不考虑CTR时，置为0)
- $a_5$: GMV权重(销售额，考虑商户利益)
以上排序公式的主要问题是，bid跟访购率、GMV存在乘积关系，不太合理，可能不一定能得到帕累托最优解。所以，考虑从多目标优化的角度，重新设计排序公式。
新公式设计如下：
$$
\text{RankScore} = a_1 \cdot Bid \cdot CTR^{a_{11}} + a_2 \cdot CTR \cdot CVR^{a_{21}} + a_3 \cdot CTR^{a_{31}} \cdot CVR \cdot Price^{a_{32}}
$$
公式解读：
- $a_1$：广告收入权重
- $a_{11}$: CPC广告，值为1；CPM广告，值为0;
- $a_2$：用户体验权重
- $a_{21}$：用户体验指标是访购率，值为1；用户体验指标是点击率；值为0;
- $a_3$：广告主收益权重
- $a_{31}$：考虑CTR，值为1；不考虑CTR，值为0;
- $a_{32}$：考虑订单价，值为1；不考虑订单价，值为0;
- 非0/1值：排序结果、计费价格都受影响
参数的设定基于人工经验、数据分析及线上实验效果。由于场景的复杂性，一套参数并不能实现利益最大化，不同场景上采用不同的参数，可以提高整体收益，因此就有了动态调参。
动态调参本质上是在人工选择排序公式中的一个参数基础上，进行一定范围的搜索，计算不同参数下的收益（奖励），选择出最优参数。因此，奖励设计是动态调参的关键。
奖励公式如下所示：
$$
Reward = bid \cdot ctr + b_1 \cdot ctr^{b_{11}} \cdot cvr^{b_{12}} + b_2 \cdot ctr^{b_{21}} \cdot cvr \cdot \frac{price_{order}}{bid}
$$
说明
出发点：多目标加权和，分别是广告收入、用户体验、广告主ROI；
- $b_1$：用户体验权重（如果不考虑CVR，可将$b_{12}$置为0）
- $b_2$：ROI权重
- $b_{21}$：如果不考虑CTR对ROI的影响，设置为0
上面的公式是广告位上的计算逻辑。通常，整个请求的Reward，会累加多个广告位的Reward，而且广告位存在位置偏倚。
存在的问题：整体ROI的计算，不能累加多个广告位的ROI，所以计算ROI有问题。
解决办法：计算各个广告位上的广告收入、用户体验指标、GMV，再算整体的广告收入、用户体验指标、ROI。$\color{red}{算整体时，不区分广告位?}$
不同流量上，动态参数和奖励设置不同。
静态与动态的关系
静态排序公式，考虑了多目标优化，动态的Reward也考虑了多目标优化，它们是什么关系？
- 还没有动态调参算法时，静态排序公式体现了我们多目标优化的权衡。根据rankScore排序插入，是一种贪婪算法。
- 有动态调参算法后，Reward体现了我们多目标优化的权衡。排序公式中的参数变成了决策变量。
不考虑计费，不同排序结果的数量是有限的。我们的目标是对比这些不同排序结果的优劣。不同的排序公式，决策变量与排序结果的对应关系不同，可能会影响找到最优解的效率。因此需要设计出更快更方便找到【帕累托最优】的决策变量。$\color{red}{帕累托最优是什么鬼？}$
注意：动态调参方法 通常是采用网格搜索的方式，在一定的区间以一定的步长进行。以关键词搜索为例，ctr权重系数区间：[0.007, 0.012]，步长：0.001
参数学习
智能出价
背景－流量的差异化
传统的出价是针对特定人群或广告产品（关键词／推荐列表页）设定一个固定的出价，是一种粗粒度的方式。如果能有更细粒度的方式来匹配出价和流量质量，根据流量质量动态地调整出价，那么可以有效地提升广告主ROI（预算花费更高效或带来更高的GMV），因此就有了智能出价策略。
不考虑广告主之间的博弈关系，可考虑如下方法：
- 线性出价算法
- 非线性出价算法
- 强化学习
$\color{red}{线性出价算法与OCPX的关系是什么？}$
线性出价会考虑广告主之间的博弈过程，OCPX没有。二者均是根据流量差异而进行出价。OCPC期望bid不大于真实bid；
智能出价统称为ocpx，可以是ocpc, ocpm, ocpa等。
以cpc与ocpc举例，比如1,2,3,4,5 有5个访客：
- cpc不考虑访客因素，出同样的bid，无论哪个访客转化好；
- ocpc的逻辑是：如果2，3转化了，ocpc会根据2，3人群的标签帮广告主找到类似人群（looalike挖掘），对该部分高转化访客提高出价，而对1，4，5低转化访客人群降低出价。
所以，智能出价是按照转化（或广告主ROI）出价，系统利用转化学习对不同人群（或访客）分别出价。
因此，智能出价通常需要两个阶段：
- 阶段1：数据收集阶段。按照cpc/cpm投放获取足够的转化数据；
- 阶段2：智能投放阶段。即根据对访客的转化率（或ROI）预估进行动态出价，大的原则是高CVR则出价高，低CVR则出价低。
_智能出价的优势_
- 广告系统自动为广告主寻找转化人群；
- 广告系统对不同的转化人群合理出价；
- 广告系统根据转化情况，展现最优质的物料（？？？创意）
_智能出价的劣势_
- 前期成本较高（需要收集转化数据，对电商类是否不存在该问题？）
- 对预算要求较高；
- 实验成本较高，需要不断测试智能出价模型；
OCPC算法
问题引导
- 排序公式的超参优化与智能出价的关系是什么？
- 论文的目标是保ROI的情况下，优化GMV和RPS。那么，ocpc框架怎么迁移至其它业务优化上？
- 如何选择最优bid？
- ocpc算法对平台收入增长的贡献点在哪里？
OCPC是Optimized Cost Per Click的缩写，即优化点击付费，本质还是按照cpc付费。采用更科学的转化率预估机制的准确性，可帮助广告主在获取更多优质流量的同时提高转化完成率。系统会在广告主出价（固定bid）基础上，基于多维度、实时反馈及历史积累的海量数据，并根据预估的转化率以及竞争环境，智能化的动态调整出价，进而优化广告排序，帮助广告主竞得最适合的流量，并降低转化成本。
因此ocpc是一种优化广告投放效果的智能出价技术，它能根据流量质量自动动态地调整广告的竞价bid，保证ROI的同时提高GMV。该算法出自阿里妈妈淘宝业务场景论文，并且在淘宝移动端猜你喜欢列表页和顶部banner两个广告场景落地。
从第一节中举cpc与ocpc的栗子可以看出，OCPC算法的工作原理是：
对每次广告请求都动态地设置与该流量质量相匹配的bid，同时综合优化用户体验、广告主和平台的三方诉求，并保持使用eCPM排序机制不变（因为优化目标的约束公式）。
这里有两点需要注意：
- 优化目标（即排序公式）与具体业务有关，不可照搬;
- 论文中排序公式为ecpm＋gmv，其中约束条件中是ecpm排序机制，个人绝的可以尝试将ecpm约束条件替换为业务需要的约束排序机制（是否必要替换需要想清楚？大概率不需要，因为排序公式已经体现了业务目标）
优化范围－ROI约束
假设用户u点击率广告a，产生交易的概率为$p(c|u,a)$，并且定义交易额（pay-per-buy，简称PPB，也就是商家设定的商品价格price）为$v_a$。因为一次点击广告主需要付的费用为$b_a$（此处暂不考虑GSP计费），那么可知：
$$
\text{GMV}_{click-and-buy} = p(c|u,a) \cdot v_a \\\
roi_{(u,a)} = \frac{\text{GMV}_{click-and-buy}}{b_a} = \frac{p(c|u,a) \cdot v_a}{b_a}
$$
假设$n_u$是某个用户$u$在过去一段时间对广告$a$的总点击数，$E_u[p(c|u,a)]$表示期望转化率，那么有：
$$
roi_a = \sum_u roi_{(u,a)} = \frac{v_a \cdot \left(\sum_u n_u \cdot p(c|u,a) \right)}{b_a \cdot \sum_u n_u} = v_a \cdot \frac{E_u[p(c|u,a)]}{b_a}
$$
上式$roi_a$就是ocpc优化问题中的约束条件（即$roi_a$不降低或者有上涨）。在阿里论文中，为了防止异常值和离群点，对pCVR进行了截断，即$E_u[p(c|u,a)] = Average(Trim(pCVR, [10\%,90\%]))$。
可以看到，广告主ROI主要受3个因素的影响：期望转化率、客单价和出价bid。
- ROI约束是广告系统 广告主诉求，ROI是与业务相关的指标。应用在其它场景，也可以是其他约束条件。
- 如果我们优化的不是bid出价，而是商品价格，那么目标也就发生了变化。
Bid优化上下界
假定$b_a^*$是某一次广告出价${bid}_{click}$，那么只需要满足以下公式就可以保证roi不降低。
$$
\frac{b_a^*}{b_a} \le \frac{p(c|u,a)}{E_u[p(c|u,a)]}
$$
但是，商业竞价环境中并不能保证每次的出价$b_a^＊$都能保证roi不降低。于是，论文给出了经验公式，并划定了可行域。其中$r_a$是一个调节系数，用来衡量广告位偏差，流量质量低的情况下，对用户点击意愿的妥协程度系数。
$$
\begin{align}
\text{LowerBound:} \quad l(b_a^*) &=
\begin{cases}
\displaystyle
b_a \cdot (1 - r_a) , &\quad \frac{p(c|u,a)}{E_u[p(c|u,a)]} < 1; \\\
b_a , &\quad \frac{p(c|u,a)}{E_u[p(c|u,a)]} \ge 1 \\
\end{cases}
\end{align}
$$
$$
\begin{align}
\text{UpperBound:} \quad u(b_a^*) &=
\begin{cases}
\displaystyle
b_a , &\quad \frac{p(c|u,a)}{E_u[p(c|u,a)]} < 1; \\\
b_a \cdot \min(1 + r_a, \frac{p(c|u,a)}{E_u[p(c|u,a)]}) , &\quad \frac{p(c|u,a)}{E_u[p(c|u,a)]} \ge 1
\end{cases}
\end{align}
$$
从上式可以看出，可行域如下图所示：
// TODO给出可行域空间图
可以看到bid优化的区间范围是$[(1-r_a) \cdot b_a, (1 + r_a) \cdot b_a]$。
问题：$r_a$通常取多少？
OCPC排序公式
在可行域中选取不同的$b_a^＊$，会导致目前以eCPM作为排序机制的排序结果的改变。假设我们想要在eCPM的机制下展示一条广告$k$，并且希望$k$能够最大化我们的排序目标公式$f(\cdot)$。
$f(\cdot)$最原始形式是指考虑$pctr$，故
$$
f(k, b_k^{＊}) = pctr_k \cdot b_k^＊
$$
那么排序公式等价于带约束的优化问题：
$$
\max_{b_1^＊, b_2^＊, \cdots, b_n^＊} f(k, b_k^＊) \\\
s.t. \quad k = \arg \max_{i} pctr_i \cdot b_i^＊ \\\
l(b_i^＊) < b_i^＊ < u(b_i^＊), \forall{i} \in A
$$
接下来，我们分别考虑两种排序公式：
$$
\begin{align}
\text{consider GMV:} \quad f_1(k, b_k^＊) &= pctr_k \cdot pcvr_k \cdot v_k \\\
\text{consider GMV + eCPM:} \quad f_2(k, b_k^＊) &= pctr_k \cdot pcvr_k \cdot v_k + \alpha \cdot pctr_k \cdot b_k^＊
\end{align}
$$
假设
$$
s_a^＊ = pctr_a \cdot b_a^＊ \rightarrow
\begin{cases}
l(s_a^＊) = pctr_a^＊ \cdot l(b_a^＊) \quad \text{LowerBound} \\\
u(s_a^＊) = pctr_a^＊ \cdot u(b_a^＊) \quad \text{UpperBound} \\\
\end{cases}
$$
由于pctr、pcvr等指标非负，并且一般意义下，$b_k^＊$高将会持续导致与其相关的pctr等指标提升，会在一定程度上保证了$f(k, b_k^＊)$函数对$b_k^＊$单调不减。
这里有个比较弱的假设：可以认为广告系统近似等于一个增强学习环境，会导致样本出现受出价引导的bias现象。
由以上假设可以认为，我们只需要将所有的$f(k, u(b_k^＊))$按照降序排列（那么如此是否可以说，使用ocpc优化后cpc一定会涨，从而带动了平台收入的增长？），并且按顺序找出来排在第一位的广告$k$，就是我们要找的广告（因为单调不减），并且满足以下条件：
$$
u(s_k^＊) \ge l(s_i^＊) \qquad \forall i \neq k \\\
b_k^＊ = u(b_k^＊)
$$
刚刚是在假设一次性只展示一条广告的情况，若一次需要展示$N$条广告的话，文中给出了一个贪心策略来实现广告排序。假设一次展示$n$条广告$k_1,k_2,\cdots,k_n$。如何保证$Position_i$的广告恰好对应$k_i$。
结合论文中的事例，解读ocpc算法排序过程：
- 算法第3-5步：按照排序公式对降序排序（$f_2$公式） ；选择lowerBound最大的广告（这里是a3）；从上到下选择第1个upperBound大于lowerBound的广告并输出（这里是a1）
- 算法第6-11步：剔除广告ad1，重新计算剩余广告的bid*(公式9-10)，同时更新其它指标的上下边界。第二轮（3-5步）：选择在lowerBound最大的广告（这里是a3），自顶向下选择第一条upperBound大于lowerBound的广告屏输出（这里是a3）。
- 直至完成所有排序或返回N个广告。
其它算法细节
_校准calibraction_
从历史经验看，oCPC中的pCVR预估值存在偏低的现象，作者提出了一个经验校正公式：
$$
p(c|u,a) =
\begin{align}
\begin{cases}
\displaystyle
p(c|u,a), &\quad p(c|u,a) < tc; \\\
p(c|u,a) \cdot (1 + \log(\frac{p(c|u,a)}{tc})), &\quad p(c|u,a) \ge tc
\end{cases}
\end{align}
\quad tc = 0.012 (与业务相关参数)
$$
_oCPC算法复杂度_
整个oCPC算法包含两部分：Ranking和Calibration，总起来算法复杂度为$O(N \times \Vert A \Vert \times \log \Vert A \Vert)$。与$N$成线性关系，通常A和N不是太大，可以提供online serving。
_模型评估指标－GAUC_
文中对广告位置p和用户u进行组合后分组，并在计算auc时进行加权$w(u,p)$
$$
GAUC = \frac{\sum_{(u,p)} w_{(u,p)} \times AUC_{(u,p)}} {\sum_{(u,p)} w_{(u,p)}}
$$
OCPC算法实现细节
- 客单价$v_a$：按照shopid粒度区分，计算过去一段时间（周or月）的消费均价来使用。若为空，使用门店均价来代替。实现方式：类似ctr统计特征，加载resource，每日推送新数据。
- 期望转化率$E[p(c|u,a)]$，按照slot＋广告launchid维度区分，计算过去一段时间（周or月）转化数据（如果转化数不超过100，则epcvr计为0，epcvr=0的shop不对其进行ocpc算法处理）。实现方式：统计点击转化率cvr，类似ctr统计特征，加载resource，每日推送。
- rank极端需要对所有的广告位进行一次处理。加入新的OcpcHandler：setup方法负责加载epcvr和客单价等数据以及docs；handle方法负责计算bound；cleanup方法负责rerank和回填数据。
- 排序公式f函数暂定论文中f2；
- 需要修改result，加入修改后的bid，透传给下游计费模块；
- cvr因为数据稀疏，可以考虑校准。
OCPM算法
什么是ocpm？
Optimized Cost per Mille的缩写，即优化千次展现出价，本质还是按照cpm付费。采用更精准的点击率和转化率预估机制，将广告展现给最容易产生转化的用户，在获取流量的同时，提高转化率、降低转化成本，跑量提速更快。
ocpm算法的逻辑是：广告主按点击竞价而按展现量计费。
今日头条的信息流广告在2018年已经用oCPM替换了之前的ocpc（目前仅在联盟穿山甲广告位上还保留ocpc），除了头条外，还有微信朋友圈广告、facebook使用ocpm出价算法。
社交网络SNS广告用户行为类型比较分散，比如有喜欢、点击、转发、分享、评论等。而电商类广告相对更集中，主要是各种点击，以及下单。
ocpm与ocpc在排序和转化出价上没有区别，区别在于opc中的初始化阶段以及按曝光计费。（为什么头条的信息流广告按照曝光计费而不是点击计费？）
ocpm与ocpc的区别主要在于：
ocpc只能以cpa（如下单、gmv等）作为优化目标；ocpm则多了一个空间，可以按照A（转化相关）作为优化目标，也可以按照C（点击）作为优化目标。对于那些只需要获取流量，不特别计较转化的广告主（如品牌类广告主），ocpm能够提供以点击或流量转化为目标的出价方式是非常有价值的。
今日头条广告计费模式
- cpm：按展示扣费，只要你的广告被刷出来，不论客户是否会点击都会扣费；
- cpc：按点击扣费，你的广告展现出来不扣费，只有客户点击了才会扣费；
- cpa：按转化扣费，你的广告展示出来、被人点击都不扣费，只有当用户产生转化了才会扣费，比如填写了手机号，成为了一个转化，系统才会扣费；
- ocpm：按展示扣费，ocpm相对cpm的不同是，ocpm可以自动优化人群，以达到广告越跑越精准的效果；
除了这四种常见，还有被头条取消，目前只存在穿山甲广告位的Ocpc：按点击扣费，ocpc相对cpc不同的是，ocpc可以自动优化人群，从而探索到更多优质用户。
那么，$\color{red}{今日头条为什么要取消ocpc，替换为ocpm呢}$？
原因如下（参考今日头条广告oCPM出价优势及广告资源！）：
- ocpm可以满足广告主在媒体类平台上多样化的转化目标需求，更适合粉丝营销的趋势，如关注、分享、点赞等；
- oCPM计划可以支持不同的转化类型组合，提高广告主的转化效果，能够更好的帮助实现计费逻辑。比如今日头条，可以帮助广告主实现多项不同的转化目标，提升广告营销效果；
- oCPM计划会支持更多互动性更强的样式，能够有效适配广告创意复杂的点击行为；
- oCPM计划支持视频播放后自动跳转到广告主的落地页页面，可以有效的帮助减少用户流失
CEM算法在OCPX中的应用
CEM（Cross-Entroy Method）算法迭代过程分为两个阶段：
- 重要性采样：根据指定的采样机制（可以是超参分布）、生成随机数据样本（或参数）；
- 根据生成的数据样本，更新采样机制中的超参数，实现在下一次迭代中生成更好（选择top精英）的样本；
因此CEM算法是一种基于参数扰动的进化算法，给参数空间一些合理的扰动，然后在这些扰动中搜索和选择较好的子集合，然后利用交叉熵来指导更新，让这些扰动方向趋近于我们想要的目标优化方向。
CEM优点：无需计算梯度，收敛快，可并行计算，工程实现轻量；
CEM不足：强依赖于随机探索、收敛于局部最优。（应对：多轮训练，择优）；
基于进化策略CEM的OCPM建模
业务背景：自动调bid，细粒度的流量匹配。
State: $feature = (bid, gmv, bid_{avg}, gmv_{avg}, gmv/gmv_{avg})$
Action: $\theta^T \cdot feature \\\ Optimized_{bid} = Clip(\theta^T \cdot feature + 1, lower, upper) \cdot bid$
Reward: $f(\Delta cpm, \Delta gmv) = \Delta cpm + \Delta gmv - |\Delta cpm - \Delta gmv|$
目标：采用CEM寻求最优参数$\theta^T$
问题：参数$\theta^T$是ad粒度还是请求粒度？ad之间的bid是否有影响。