Optimized Cost per Click in Taobao Display Advertising
解决问题
淘宝作为世界上最大的电商平台，每天为上百万的广告主提供十亿多在线广告曝光的机会。从商业目的上说，广告主为特定的场景和目标人群进行竞标以竞争商业流量。平台方在十毫秒内选择合适的广告进行展现曝光。常见的出价方法有cpm和cpc。
实现流量和广告的精准匹配，oCPC出价，实现高转化高出价，低转化低出价；同时优化版cpc能实现平台、广告主、用户的三方共赢。
传统广告系统以固定的出价来瞄准特定属性的人群和广告放置位置，本质上被视为出价和流量质量的粗粒度匹配。广告客户为争夺不同质量要求而设定的固定出价无法完全优化广告客户的关键要求。而且平台方需要为商业收入和用户体验做保证。本文提出一种出价优化策略，称为优化cpc（ocpc），该策略可以自动调整出价，以实现出价与网页浏览量（PV）请求粒度的更好匹配。这种方法可以优化广告客户的需求，平台业务收入和用户体验，并从整体上提高流量分配效率。在淘宝展示广告上进行方法验证，在线AB实验证明效果有提升。
本文关注于淘宝移动应用中必不可少的CPC展示广告的出价优化问题。
（高转化高出价，低转化低出价。满足一定条件；带约束优化问题）。
广告系统，包含三种角色：广告主、广告平台、用户；三方诉求不同，为了满足不同的诉求，需要采取不同的措施；同时在满足某方（某两方）诉求时，要关注其他方的价值，这是一个利益权衡的问题。动态博弈~
论文中提到的淘宝APP上的两种CPC广告格式分别是：
- Banner CPC Ads
- 猜你喜欢
淘宝作为连接用户和广告主的平台，其生态特点为：
- 不同于大部分RTB系统，淘宝有dsp和ssp两种角色，数据在平台上能形成闭环，能完整的获得到用户数据以及广告计划信息；
- 淘宝中大部分是中小广告主，其主要关注于提升收入而非提高品牌影响力。因此，提高gmv能有益于这些广告主。
- 不同的广告主可能追求不同的KPI，这里讨论在淘宝平台上以点击竞价的cpc方式。
- 最后，广告场景必须满足媒体要求，通过点击率、转换率、gmv等指标来衡量。
通过权衡利弊，在这两种广告格式中使用cpc竞价计费。原因：
- 相较于cpc，广告主采用cpa承担风险会更低，
- 淘宝中多为中小广告主，cpm相比于cpc风险更高，cpc允许广告主控制点击成本，同时平台承担曝光到点击的风险。
广告主总是期望出价能与流量质量相匹配。但是由于技术限制，传统方法只能为用户组和广告位设置固定出价，以实现粗粒度的流量差异化；但是，广告客户正在寻求对出价和流量质量进行更细粒度的匹配方法。基于固定出价的排序过程有两个不足：
- 广告主设定的一个固定出价去处理具有不同商业质量的持续互联网流量，这种方式是低效的；
- 传统方法会最大化eCPM来追求短期商业收入，但是无法优化和控制媒体需求（例如GMV），这不利于淘宝的长期利益。
为了解决这两个问题，从广告主角度出发，一些社交网络平台提出了从其他出价目标平等转换而来的oCPM，oCPM能最大化广告主利益；但是，不能保证广告平台的生态健康如gmv。另一方面，通过修改排名公式bid * pctr过度追求媒体需求（如GMV）无法为广告商和平台带来有效的商业利益。
为了解决上述问题，我们提出了具有以下特征的OCPC：对于每个PV请求，在优化广告客户需求的前提下，OCPC会根据流量质量的真实价值调整出价，同时将出价最大化 通过保持eCPM排序机制不变来反映用户体验，广告客户的兴趣和平台收入的整体生态的综合评分； 我们的设计使我们能够根据业务变化的需求，以较低的成本灵活地调整OCPC系统。
系统架构
描述淘宝展示广告系统中数据信息流，有利于理解出价优化如何生效。从PV请求开始到最终的展示曝光。
- Front Server：从用户侧接收page view请求，将请求传送给Merger Server
- Merger Server：中心调度器，在整个过程中与其他模块交流通信。Merger Server请求Matching Server分析用户，然后根据广告主的用户定向要求给出一个特征标签列表；
- Matching Server：
- Search Node(SN) Server：通过Merger Server，这些标签被传送给Search Node Server，用于依据出价来查找特定的候选广告。在’猜你喜欢‘广告中，候选广告从数千个减少为4百个。
- Real-time Prediction(RTP) Server：对SN中的候选广告预测点击率pctr、转换率pcvr。
- Strategy Server：负责ecpc逻辑处理，基于pctr、pcvr和出价在排序阶段优化流量分配。策略层还负责后续广告的重复删除，以及广义第二价拍卖下的最终曝光价计算。
- Data Node(DN) Server：根据广告排序结果，Data Node Server将广告的标题、图片地址抽取出来；
- Smart Creative Service（SCS）：对DNS处理得到的广告标题、图片地址进行创意优化。
最终，前端server将结果返回给app或者网站。之后的点击、转化将记录在log日志系统中。
OCPC
A：符合PV请求的广告计划集合。对于一个特定的PV请求来说，对于A中的每个广告计划a，存在一个广告主预先设定的出价ba。对每个ba来说，OCPC算法的作用是调整ba，找到一个优化后的ba*能满足预先设定好的各种优化要求。
优化可行域
ROI Constraint。ROI限制。考虑到淘宝大部分是中小广告主，其主要关注市场效益，我们选择以保持或提高ROI作为算法的主要应用的同时，对他们的收入GMV进行优化。这里先介绍相关概念，然后引出ROI的数学表达。
- p(c|u,a)：用户u点击广告a后发生转化c的概率；
- va：对于特定广告计划a，va表示预计顾客的购买价格（pa-per-buy），或者说卖家的商品定价
- p(c|u，a) * va: 单次点击的预计GMV
广告主的实际耗费依据广义二价机制来计算，这里我们假设广告主为点击点击的付费为ba。单词点击的期望ROI计算公式：
汇总不同用户和点击的广告计划a的总体ROI为：
nu表示一段时间内用户u的点击广告a的次数。
上述等式表明广告主的ROI由3个因素决定：期望转换率，va以及出价ba；其中va是由每个广告决定的，
在每个特定的商品（auction）上都是固定的。
实践中，当前的预测模型用于预测过去几天竞争广告的pCVR；消除了这些CVR中最大，最小的10％，计算剩余的平均值作为。出价优化的目标需要保证广告主的roi保持不变或者得到优化（称为ROI约束），此外，广告主可以获得更多高质量的流量。
出价优化边界。上面的等式保证了roia和之间的线性关系；为了满足ROI约束，出价优化保证
其中阈值ra是处于安全性和商业设置而定的。下限对于避免某些广告商在优化ROI时获得很少流量的情况至关重要。从上图可以看出，当流量质量较差时，横坐标小于1，的上限还能达到
本身，这显然不能保证ROI不降，做了妥协。
对于广告计划a的出价优化上下边界分别为和
。值得强调的是，出价优化的边界可以泛化到广告主设定的不同KPI上，并不局限于ROI指标。如果广告主没有设定出价优化，对应的上下边界均为
.
排序
在可行域内的优化出价可以帮助广告主获得更好流量质量以及更高的ROI。但是，在可行域内选择的不同的出价在eCPM排序机制下回导致不同的广告排序结果（pctr * bid），进而带来不同的收益以及其他指标的变化。本节的剩余内容主要介绍在保持eCPM排序机制不变的情况下综合考虑各方的利益的一种在可行域内选择
的方式。
假设在eCPM机制下要展示一个广告，我们期望广告能最大化目标函数：
n表示在一个PV中候选广告的数量。候选广告集合A中的n个广告需要在eCPM排序机制下竞争一个广告位；f(*)表示综合各方利益的一个综合指标。这里假设，是关于
的一个单调函数。
优化问题中，k是最终胜出的广告，依赖于的选择，f(⋅)是需要优化的目标函数，综合了需要关注的指标。比如：
f1只考虑淘宝平台的gmv（广告主的收入）；f2是gmv和广告收入的综合指标，是gmv和广告收入的权衡系数。
排序的剩余工作就是如何为每个广告a在最大化目标函数下选择。类比于优化出价的边界，我们设定
的边界为
和
，为优化排序分数
的上下边界（
）.
- 为了优化目标函数f，我们需要将广告依据
进行降序排序（因为设定
关于
的单调函数，所以这里使用出价的上边界
）；
- 按顺序选择第一个广告k（从上面的排序结果中顺序选择），满足k的ecpm排序分数上界
不小于其他所有广告的ecpm分数下界
[满足优化问题的不等式条件]
- 广告k是最重要展示的广告，同时出价
，取上边界作为最终出价。
- 最后，在可行域内更新其他候选广告的出价bid，保证广告k拥有最大的eCPM。
对实际场景中，在每个PV中可能有不止一个的广告展示（广告位），因此在上面的基础上提出一个贪心算法。
算法描述：先按照1个广告位的算法找到广告k放到广告位1，然后调整剩下广告的ecpm排序分数上界，保证, 这样可以保证k按照ecpm排序处于第一位；同时调整剩下广告的出价上边界
【根据ecpm排序分数计算，ecpm = bid * pctr】；接着在剩下的广告中按照1个广告位的算法找出剩余的广告位广告；最后将选出的广告出价设置为出价上界【依据ecpm排序分数计算】。
下面用例子来理解排序算法。假设候选广告A中有个4个广告，同时有2个广告位，我们需要在4个广告中使用提出的排序算法选择2个合适的广告。
首先，依据目标函数对4个候选广告进行降序排序；其中ecpm排序分数的最大下边界为
(表格中蓝色部分)。在依据
排序结果中从上到下选择第一个出价上边界大于所有广告出价最大下边界的广告，也就是
(蓝色标注)。因此，选出的第一个广告就是Ad 1，然后将其从候选广告A中删除，并加入到胜选广告集合
;剩余候选广告A更新成表格2，根据算法的6-11行，为了保证刚胜选的广告Ad 1的ecpm排序分数最大，需要更新剩余候选广告的ecpm排序上边界以及对应的出价上边界；更新部分如表格2中的红色部分。在表格2中依据算法继续进行选择，选择广告Ad 3；依据算法进行选择直到胜选广告数量等于N，即
.最后，设置胜选广告的出价为对应出价上边界；最终的所有候选广告的出价为表格3.
我们只修改了胜选的候选广告的出价[提高对高质量流量的竞争能力]，其余候选广告出价保持不变。
通过这样的排序算法，将最终的排序指标和广告流量的目标解耦。一方面，广告仍然可以通过pctr * bid进行排序，这部分用于最大化eCPM；另一方面，广告平台可以依据不同的目标函数f选择广告。另一个关键问题是广告主的预算约束。一旦广告计划花完了预算，这个广告将被移除接下来的auctions，这对出价优化过程没有影响。
模型校正Calibration
淘宝平台发现，从维护广告系统的历史经验来看，OCPC层中使用的预测值存在固有偏差，这可能会影响算法的有效性。（pcvr/pctr和实际cvr/ctr存在偏差，预估不准确）。这部分是在预测之后OCPC Layer之前进行的。
以pCVR为例，实时预测模块RTP当实际CVR很高时，给出的预测值pCVR也预测得越高。依据预测pCVR将所有广告分为20组，对应实际CVR与pCVR/CVR比例如下图所示。
pCVR校正公式为：
其中，tc为校正阈值，通常为0.012。当pCVR大于tc时，使用上述公式进行校正，减少pCVR和CVR的gap。校正之后，两者gap减少，减少了一个量级。
最终的OCPC算法为：
对于A中的候选广告，先进行pCVR校正、计算出价上下边界；然后进行算法1的排序；最后，返回候选广告的各个优化后出价。
模型评估
CTR模型中，正样本指那些曝光后发生点击的数据；负样本指曝光但用户没有点击的数据；CVR模型中，正样本指曝光后发生点击，之后又发生转化的数据；负样本指曝光后只发生点击，没有转化的数据。
新模型天级别更新，用于消除不同天的数据方差。
预估模型的提供精准的结果是非常重要的。像CTR预测中，AUC是一个评估模型有效性的指标。然后，存在研究显示测试阶段更好的AUC实际工作时反而带来更差的表现（线下AUC高，线上表现反而更差）。淘宝在实际工作中也遇到类似问题。
分析发现，AUC将不同的用户和广告位同等对待，一视同仁。但是，一些从不点击广告或者遮挡广告的用户会给AUC结果带来动荡，使其变得偏低。根据事实和分析，提出GAUC指标。将用户和广告位对测试数据进行分组；然后在每个小组内计算AUC（如果组内数据全是正样本or全是负样本；则从测试数据中移除这个组内的样本）；最后，依据每个小组的曝光or点击次数，对AUC进行加权平均。
实现验证
论文分别进行线下和线上实验，验证算法的有效性。
线下模拟
通过历史的log数据，将pCTR和pCVR当作真实的CTR和CVR，比如某次展示的广告计算出pCTR为4%，则认为贡献了0.04的点击。然后设计4种策略，统计指标。4种策略分别是：
- Strategy 0：对照组，保持原来线上的策略
-
Strategy 1：站在广告主角度，设计调价策略image-20200809122609524
-
Strategy 2：OCPC策略，优化的目标函数为image-20200809122642579
- Strategy 3：不调价直接修改rankscore公式，不再是eCPM排序，改成pctr * pcvr * bid，像提升gmv。
实验效果如下表，相对策略0，策略1和3的千次展示GMV和ROI都提高了；但RPM降了，只有策略2（OCPC）在3个指标上都获得了提升。
线上效果
Strategy 2上线效果和线下一致，在3个指标上均获得了提升。
此外，作者提出本文的机制具有普适性，并不局限于GMV。
Others
约束优化，保证ROI不降的情况下，对广告单元的cpc出价进行调整。然后设定了调整范围，可行域。之后，设计统筹多方利益（广告主、平台、用户）的指标；此外，保证eCPM排序机制不变，对候选列表中的广告单元出价进行上下调整。
总是想是实现：高质量流量高出价，低质量流量低出价。但是还要保证效果要好。
