计算广告中主要模块策略及其场景下

　　本文是我最近学习的一个总结，之前的文章多是和功能特别是广告主界面有关，而本篇文章则是和策略有关。在文章会讲述计算广告（主要是DSP）中的主要模块、用到的策略及其场景。希望大家能和我一样，在了解广告业务的同时，还能对策略的设计有一定了解，总结出一些通用的方法。
　　本文分三个部分，功能和策略，主讲功能型产品和策略型产品的区别；架构综述，主讲广告系统的流程、模块和技术架构；算法和场景，主讲各个模块和场景中用到的算法。功能和策略、架构综述在上篇已经讲了，在此下篇中将接着讲算法和场景。
　　GBDT模型
　　GBDT的全称是（GradienBoostingDecisionTrees），是一种决策树，属于Boosting族，能将弱学习器提升为强学习器。GBDT中文叫梯度提升决策树，由多棵决策树构成，最终的预测结果是将所有决策树的结果累加得到。
　　提升即迭代，是不断缩小残差（真实值预测值）的过程，建立M个决策树模型，每个模型都是弱分类器，每次分类后对分错的数据的权重增加后再分类，一直到训练和测试数据获得较好结果。
　　训练一个提升树模型来预测年龄：训练集是4个人，A，B，C，D年龄分别是14，16，24，26。样本中有购物金额、上网时长、经常到百度知道提问等特征。
　　提升树的过程如下：
　　该例子很直观的能看到，预测值等于所有树值得累加（GBDT是加权累加），如A的预测值树1左节点值15树2左节点114。可以看到第二颗树是对第一颗树的补充，学术的描述就是每一次建立模型是在之前建立模型的损失函数的梯度下降方向，这就是梯度提升的过程，也用到了损失函数。
　　F0在这里是初始值，Ti是一棵棵的决策树，不同的问题选择不同的损失函数和初始值。损失函数可以用平方损失函数或者指数损失函数等。
　　此外，在使用特征或属性进行分支时，分支规则采用最小均方差的方式，即预测误差的残差的平方和去除以N，误差越多错的越多，通过这种方式找到最好的分支依据。
　　GBDT的损失函数和逻辑回归中的概念类似，描述的是当前模型偏差的程度，损失函数越大，偏差越大，模型出错程度越高。
　　训练目的就是让损失函数的值不断下降，每次修正的过程中按梯度下降的方向作为修正方向，步长选择不能过大，过大的逼近可能会导致过拟合，每次走一小步可以避免这种情况，但步长范围设置过小也会导致计算和预测时间大大增加。步长等超参数的如何设置的问题，几乎在绝大部分模型中都会遇到。
　　在《在线广告DSP平台实时竞价算法的研究与实现》中，运用GBDT来预估CTR预估，是用开源的xgboost实现，设置树深度为4，训练了300棵数，学习速率设为0。1。
　　决策树的个数越多学习越充分，但也会导致过拟合。学习速率可以稍微设快，可以减少树的数量。
　　实验中特征变量选取的都是连续值变量，如不同地区的特征变量则计算出它的发生频率和点击率，并将其作为梯度提升决策树的两个特征。广告的底价由于是连续值，可直接用于梯度提升决策树的变量值。
　　并非所有变量都能对模型产生很大影响，因此在特征选取时不会像逻辑回归那样需要选择很多特征，GBDT会放弃大多数特征而保留一小部分，学习过程中选用了72个特征作为训练和预测的变量。而逻辑回归在实验中共选取了61万余个特征。
　　GBDTLR模型
　　由于GBDT所需特征量远小于逻辑回归的特征数量，自然想到利用GBDT来选择特征。Facebook基于GBDT提出了GBDTLR模型，这是一种利用GBDT自动进行特征筛选和组合，进而生成新的离散特征向量，再把该特征向量当作LR模型输入，预估CTR的模型结构。
　　模型结构
　　其中用GBDT实现特征工程和用LR预估CTR两步是独立训练的，因此不存在如何将LR梯度会传到GBDT这类复杂问题。
　　GBDT中每棵树生成的过程是一棵标准的回归树生成过程，因此每个节点的分裂是一个自然的特征选择的过程，而多层节点的结构自然进行了有效的特征组合，也就非常高效的解决了过去非常棘手的特征选择和特征组合的问题。
　　利用训练集训练好GBDT模型之后，就可以利用该模型完成从原始特征向量到新的离散型特征向量的转化。
　　具体过程是这样的，一个训练样本在输入GBDT的某一子树后，会根据每个节点的规则最终落入某一叶子节点，那么我们把该叶子节点置为1，其他叶子节点置为0，所有叶子节点组成的向量即形成了该棵树的特征向量，把GBDT所有子树的特征向量连接起来，即形成了后续LR输入的特征向量。
　　GBDT生成特征向量的过程
　　举例来说，如上图所示，GBDT由三颗子树构成，每个子树有4个叶子节点，一个训练样本进来后，先后落入子树1的第3个叶节点中，那么特征向量就是〔0，0，1，0〕，子树2的第1个叶节点，特征向量为〔1，0，0，0〕，子树3的第4个叶节点，特征向量为〔0，0，0，1〕，最后连接所有特征向量，形成最终的特征向量〔0，0，1，0，1，0，0，0，0，0，0，1〕。
　　由于决策树的结构特点，决策树的深度就决定了特征交叉的维度。如果决策树的深度为4，通过三次节点分裂，最终的叶节点实际上是进行了3阶特征组合后的结果，如此强的特征组合能力显然是FM系的模型不具备的。
　　但由于GBDT容易产生过拟合，以及GBDT这种特征转换方式实际上丢失了大量特征的信息，因此我们不能简单说GBDT由于特征交叉的能力更强，效果就比FFM好，在模型的选择和调试上，永远都是多种因素综合作用的结果。GBDTLR比FM重要的意义在于，它大大推进了特征工程模型化这一重要趋势。
　　POLY2、FM、FFM模型
　　由于LR模型的表达能力非常初级，只能使用单一特征，无法利用高维信息。而针对这个问题，工程师通常需要人工组合特征，但是人力毕竟有限，因此就有了POLY2模型。并从POLY2进化到FM再到FFM，这其中体现出的方向、思维和方法论，比模型本身更值得我们学习。
　　POLY2
　　在上面POLY2二阶部分的目标函数中（上式省略一阶部分和sigmoid函数的部分），可以看到POLY2对所有特征进行了两两交叉，并对所有的特征组合赋予了权重。POLY2通过暴力组合特征的方式一定程度上解决了特征组合的问题。并且由于本质上仍是线性模型，其训练方法与LR并无区别，便于工程上的兼容。
　　而POLY2的缺陷在于是对特征组合赋予权重，特征组合会让原本就很稀疏的特征向量更加稀疏，如果样本中没有出现这个组合特征就学习不到权重；同时权重参数的数量由n上升到n2，极大增加了训练复杂度和收敛难度。
　　FM
　　相比POLY2，主要区别是用两个向量的内积（wj1wj2）取代了单一的权重。FM为每个特征都学习一个隐向量（latentvector），在特征交叉时，使用两个特征隐向量的内积作为交叉特征的权重。每一个隐向量都包含k个latentfactors，k是人为设定的超参数，例如上述的k就是2。
　　训练数据
　　以此训练数据为例，在ESPN广告中，Adidas的样本只有一个，预测结果是1，那么Poly2对于这个组合特征会学到一个非常大的负的权重。但是，FM对于样本（ESPN，Adidas）的预测，是由两个向量决定的：WespnWadidas。而这两个向量，可以单独的去从其他的样本中学习，比如：（ESPN，Nike），（BBC，Adidas）。所以FM这样学习的更加准确。
　　通过引入特征隐向量的方式，直接把原先n2级别的权重数量减低到了nk（k为隐向量维度，namp；gt；amp；gt；k）。也许FM相比POLY2丢失了某些信息的记忆能力，但是泛化能力大大提高，这对于互联网的数据特点是非常重要的。
　　FFM
　　FFM模型学习每个特征在f个域上的k维隐向量，交叉特征的权重由特征在对方特征域上的隐向量内积得到，权重数量共nkf个。总之，FFM引入了域的概念，为模型引入了更多的信息，模型建模更加准确，但是计算复杂度较高达到kn2。
　　损失函数
　　损失函数可以用logisticloss，加上L2惩罚项，因此只能用于二分类。其中，yi是1，1表示label，L是样本数量，lambda是惩罚项系数。
　　CTR预估平台
　　在实际业务中CTR预估的场景有很多，例如点评猜你喜欢、点评商品详情页推荐、美团猜你喜欢等等多款应用多个业务，而CTR预估中模块等都是一致的，这就涉及到造轮子的问题。
　　广告排序架构图
　　广告架构图中最重要的就是精排，前文也有讲，离线要为在线提供模型等等，离线训练和在线预估统称为CTR预估。
　　从多套流程到统一框架
　　而一开始美团使用的是【多套流程】方案，一方面是不同位置之间区别较大，点评和美团是差异很大的两个应用，猜你喜欢和详情页推荐差异也很大；另一方面也是有很多隐藏的历史原因，因此不能简单的把轮子组合到一起。
　　多套流程
　　如上图所示，为了快速支持业务，在不同位置上有不同的团队和人员负责，但是存在以下几个问题：
　　分位置优化成本高，对某个链路的优化不能迅速的扩大到其他位置；
　　对人员要求高，要求掌握全链路所有模块，整个流程复杂；
　　在线还要做很多工作，很容易出错，离线效果不等于在线效果。
　　要调整到【统一框架】方案，其中有三个问题：
　　双平台多业务，代码如何统一合并；
　　如何保证线下线上效果一致；
　　复杂的离线回溯中涉及到半年的数据数百个任务如何调度。
　　市面上有在线到离线和离线到在线两个流派，前者重在线，在线做特征速度很快，而且能保证线上线下一致，但是对特征工程和海量数据不友好；后者重离线，离线做历史数据的拼接、样本、模型训练等，更适合海量数据量，例如百度要用最近半年的数据。美团用的是离线到在线。
　　统一框架
　　Match是个基本的打分单元，在不同场景下打分单元不同，由业务定义，例如：在广告推荐场景就是遇到某个广告并对其打分。
　　Cube则是CTR预估流程的抽象，所有的CTR预估都是这个流程，与业务无关。
　　Tesla是业务插件，用来定义Match是什么、特征是什么等。
　　Solar则是离线复杂逻辑调度以及基本算子，包括多天数据、usercontextad如何构建、怎么match等多天任务流，以及整个离线过程中的功能因子，例如：数据库常见操作join，在千亿样本和千亿特征中，join会倾斜，而抽象出来后只要用Solar中的算子即可无需考虑倾斜的情况。
　　解决离线在线一致的情况，要从数据一致和代码一致两个角度去考虑。由于离线在线用的Cube是同一套，代码自然一致。此外，离线ETL加工数据并同步到线上，对于一个请求UserContextAd三元组，拼成一样的Match，以此实现数据的一致。
　　统一框架中的分工
　　统一框架就是每个平台虚线框就有某个人负责，大大提高开发和部署效率。但是仍然存在几个问题，业务代码接口较多，实现较难，美团推荐接入要2周；仍旧要掌握全链路，离线在线都要做，容易出错；数据、代码共享复杂，管理也较为复杂。
　　从统一框架到框架平台化
　　框架平台化
　　上图中不存在Cube和Tesla，可总结为一句话：一份数据三个流程。
　　数据就是offlineentity，之前的UserContextAd都是entity，是排序中的实体，实际用的时候可以选择是在线entity还是离线回溯的entity。
　　第一个流程就是matchjoiner，指要把哪些entityjoin成match。
　　第二个流程是特征提取。
　　第三个流程是模型训练和预估。
　　全部都可以抽象出来，通过配置实现，在除了特征处理以外的流程，不同业务不一样的参数较少，所以比较好做，但是特征处理有点麻烦。
　　特征抽取
　　element中是基本算子，operator、generator等都是定义好的，只需要配置即可使用。
　　框架平台化的分工
　　根据上图中的分工，可以很明显看到，专人负责专模块，数据、特征、模型、业务等都有人负责，业务则是把数据定义好、把各个流程组装好，无需写代码直接配置即可。新业务通过复用已有entity只需要1天时间，模块化流水线化效率大大提升，模块专人优化降低门槛做深做精。
　　总结美团CTR预估平台的特点，能力强劲，支持千亿样本百亿特征的海量数据处理，支持LR、XGB、DNN等多模型；使用简便，全流程可配置，拖拽可视化即可实现。
　　效果优化
　　优化目标有两点，让CTR预估更准确或者是广告样式更吸引人点击。优化方向则有数据、特征、模型、策略和样式。
　　优化方向
　　从美团上来说，模型经过XGBoostLRFFMDNN能力越来越强，样本量从亿级十亿级百亿级More越来越大，特征维度从百级亿级千亿级越来越高。样本量、特征维度与模型之间并不是孤立的，模型并非简单的使用，而是要与合适量级的样本量和特征维度相配合，才能发挥模型的能力。
　　从XBGoost到大规模稀疏模型LR，模型描述能力更强，复杂低维特征到简单高维特征，从百万样本到亿级别样本，CTR大约提升10；从亿级别样本到百亿样本，从百万特征到亿特征，CTR大约提升5。
　　从LR到FFM，FFM能够自动学习特征交叉似的表达能力更强，适用于未知场景的预估能力更强，CTR大约提升3。
　　总体来看，随着样本来那个增加，效果整体提升并趋于收敛；随着特征规模增加，效果先变好后变差，前期特征变多模型表达能力变强，稀疏特征变多，过拟合严重，泛化能力变弱。
　　样本量特征维度和AUC
　　从提升CTR效果上来说，特征样式模型策略数据，模型要与合适量级的样本量和特征维度相配合才能真正发挥能力，而非简单的更换模型。
　　数据和策略上的调整很多时候还不如一个标红的样式，但是不可否认数据和策略等的价值，要根据不同优化方向的效果和当前场景和瓶颈，排出不同优先级，选择不同的资源投入。
　　Yamp；gt；Namp；gt；Zamp；gt；Mamp；gt；X
　　出价
　　下图中的BiddingEngine就是竞价模块，其中包括实时的出价计算（BidCalculation）、曝光价值评估（ImpressionEvaluation）和离线的竞价函数优化（BiddingFunctionOptimisation）、CTRCVR预估、胜出模型。出价计算和竞价函数优化是核心，其他功能并非所有公司都会用到的。
　　竞价引擎
　　核心问题
　　竞价的目的就是约束下最大化DSP利润，考虑因素包括预算约束、曝光价值、竞价胜出率等。不同的竞价策略考虑的因素不同，并非每种策略都要考虑所有因素。
　　约束下最大化DSP利润模型
　　把流量、广告分为供给节点、需求节点，约束一是某个供给节点提供给某个需求节点的占比1，某个供给节点的总供给量就是1，约束二是某个需求节点购买某个供给节点的总花费需求节点预算，DSP利润则是所有供给节点与需求节点之间的每次分配的（收益r成本m）之和。
　　流量节点往小了看，可以是每个曝光就是一个流量节点。收益r则是此次曝光的曝光价值，曝光价值点击率点击价值点击率转化率转化价值，成本m则是此次曝光的曝光成本，即此次曝光最后结算费用，对于历史曝光来说，成本是已知的，而对于此次曝光，成本是未知的，且不一定是出价，胜率也是未知的。
　　曝光价值预估（收益r）
　　曝光价值点击率点击价值点击率转化率转化价值，如果广告主是对每次曝光出价，那么曝光价值直接用广告主的出价价格即可；如果广告主是对每次点击出价，那么点击价值直接用广告主的出价价格即可，点击率仍然需要预估；如果广告主是对每次安装购物等转化行为出价，那么转化价值直接用广告主的出价价格即可，转化率仍然需要预估。
　　其实除了转化率之外，还有到达率也会影响点击价值，点击价值（a，u，c）到达率（a，c）转化率（a，u）转化价值（a），a是广告主，c是媒体，u是用户，但是达到率dsp控制不了，不在讨论范围内。
　　点击率预估方式上文已经讲过了，而转化率的预估则大有不同。目标、转化行为、广告主等多种多样，不同目标甚至用的模型都不同，而且转化样本少，数据很稀疏，同时广告投放次数对转化率影响很大。一定要注意广告投放次数和转化率冷启动两个点。
　　同一个广告针对同一个人群进行连续投放，越到后面效果肯定越差，所以要把广告投放次数放入模型中。以特定广告与人群的历史投放数据为基础，采用时间序列分析方法，训练出转化率随投放重复次数变化的曲线模型参数。该模型可以用来预测特定特定广告、人群、重复投放次数下的转化率。
　　转化率预测时，要特别注意是否有足够的历史数据，此外预测不可贸然交给机器完成，要把统计、经验等结合起来估算转化率。当然，如果是DSP广告主类型和转化流程基本一致，例如专注于游戏客户的DSP或者是专注于阿里体系内电商的阿里妈妈，那么在转化数据充分情况下可采用机器学习建模方法预测。
　　若没有足够历史数据，则要引入基于规则的简单方法，核心思想就是以最相似广告最近一次对该人群进行投放的转化率作为参考。
　　对应的广告与人群在最近1周内有投放记录时，取最近一天投放时的转化率；对应的广告与人群在历史上有投放记录时，取历史中选定的最近一段时间内投放转化率放入率平均值；若对应的广告与人群在历史上没投放记录，但同类广告与该人群有投放记录时，取历史中选定的最近一段时间内投放转化率放入平均值；若对应的广告或同类广告与该人群在历史上都没投放记录，取平台平均的投放转化率值。
　　成本m和胜率函数
　　可直接把出价当做成本m，但是多是采用第二高价竞价，出价比成本要低，最好建立一个专门的市价预测模型来估计m，但远没有曝光价值的预估可靠，不宜使用过于复杂的模型和算法，主要使用时间、地域、媒体属性等影响明确的因素来进行预估。
　　有些竞价策略还考虑了胜率函数，胜率函数可根据历史样本得到，但是要注意针对每个广告主进行订制，且ADX发来的竞价请求一般是有低价的，低于底价的竞价都是不成功，而高于一定价格，竞价一般都会成功，因此胜率函数两端的曲率要高。此外，点击率低于某个值，还可直接不出价。
　　在这个过程中，还存在幸存者偏差和删失两个问题。幸存者偏差是指，作为DSP赢下了所有bidding请求，并可以观察到所有bidding的市场价格。然而，在实际RTB中，各家DSP的策略不断调整，导致每家DSP都无法得到竞标失败的数据的反馈，且这种数据缺失是非随机的。
　　这会导致非常严重的后果：从ADX得到的反馈用于训练的数据和测试的数据分布不同。
　　竞价动态数据过滤器
　　竞价过程等同于一个动态的数据过滤器，随bidvalue而不同。由于竞价失败的请求无法得到曝光，不能出现在模型依赖的训练数据中，整个训练数据相对于fullvolumedata是有偏的。
　　训练数据与测试数据的总体分布相同是监督学习（supervisedlearning）的理论基石。在常见的业务场景如推荐中，训练样本与测试样本存在采样偏差，但总体分布是相同的；而在DSP中，样本的总体分布都不相同。
　　在有偏分布下，任何监督学习方法都是低效且过拟合的；需要的一种解决思路是将有偏的训练数据分布试图重构到整体分布上。例如用KaplanMeierProductLimit可针对存在非随机数据缺失的情况进行分布估计。
　　在实时竞价广告系统中普遍存在一个软地板价的机制，若最高价低于软地板价则采用第一高价，此时无关DSP赢标与否都只能观测到第一高价（即支付价格）。也就是说，会出现赢标后只得到自己出价的情况，只能作出估计第二高价最高不超过自己实际支付价格，因此这种得到的估价是估值过高的。这种就叫删失。可以引入竞价失败价格因素。
　　竞价策略
　　前文虽然说了很多因素，但是竞价策略有很多种，并非每种都会考虑上面所有因素。例如下图中就是一些竞价策略考虑到的因素，当然除了这些以外还有其他竞价策略。
　　几种竞价策略
　　出价逻辑
　　定值出价：对所有展示请求都出同一个价格，模型的唯一参数就是其价格。简单粗暴，但很多DSP在用。
　　随机出价：在一个给定价格区间中随机出价，唯一参数是竞价的区间上限，一般也给定，下限一般是0。
　　真实出价：就是按照计算的曝光价值出价，计算多少就出价多少，当然转化率预估的问题之前也有提到。
　　受限点击成本出价：在CPC模式下，广告主一般会设定可接受的最高点击成本（mCPC），这时就可以通过计算mCPCCTR来出价。如果点击率预估准确，该策略可以保证其支出小于收入。
　　线性出价：出价与估计的点击率成正比，但要设置基准出价，即：
　　b0是基准出价，0、分别是该广告的平均点击率以及该请求下预测的点击率。此外，还可以引入其他逻辑，例如0低于0。8不出价，高于1。2出价翻倍等。
　　非线性出价：出价模型在有预算限制的情况下最大化收益（点击数或转化数）。假设某个广告推广在一定时期T内总共符合其定向的广告请求共NT个，每个广告请求特征向量为x，满足定向条件的x先验为px（x）。给定收益函数（x），竞价函数b（（x）），竞价成功率函数w（b（（x））），假设该广告的预算为B，则优化目标可以写成：
　　由于x和（x）的关系是确定的
　　进而可以把优化目标写成：
　　利用拉格朗日乘子法，目标函数变为：
　　其中为拉格朗日乘子。通过对b（）求偏导并令其等于零，可以得到：
　　竞价成功率与出价的函数可以表示为：
　　其中c是一个常量。将此函数代入上式，得到：
　　可以看出，最优的出价是收益的一个非线性函数。
　　该策略的出价函数中有两个参数，分别是c和。其中c可以通过一段时间的盲投（比如利用随机出价策略），得到多个出价与成功率的离散点，再利用最小二乘法拟合曲线得到；可以通过网格遍历的方法，利用历史日志计算不同取值时的收益，从中选取最高的那个。
　　预算
　　预算也是另一个重要的策略点，广告主在投放广告时，会为每个广告活动（campaign或者adset）设置一个时间范围内的预算，预算就是上文提及的最大化DSP利润中的约束。
　　如果不对预算进行合理管控，会出现三种情况：
　　预算迅速消耗完毕，但是赢得了很多价值不高的请求，更失去了赢得后续收益更高请求的机会，导致最终广告效果较差；
　　时间范围结束后，预算仍有大量剩余，导致输了很多高价值的请求；
　　由于市场竞争变化及其他因素变化，导致市场波动，似的预算消耗速度忽高忽低，无法管控和预测预算消耗。这三种情况都会导致预算利用率下降，从而使得广告整体的量级和ROI均下滑，可尝试利用动态规划算法来求解。
　　因此，控制预算消耗的主要目标是：
　　同时得到广告的投放和性能目标，效果类广告是根据广告主所给出的优化目标，提升活动整体的ROI，品牌类广告则需要触达更多人群，提高广告回想度；
　　满足广告主设定的预算使用速率，匀速的预算使用速率能让广告在时间范围内匀速消耗预算，保证在更长时间内有曝光效果，每个时间段内花费相对平稳。而加速的预算使用速率用于时效性更强的推广，例如双十一电商广告投放等；
　　降低数据咨询花费，DSP通常要用自有第一方数据和来自DMP第三方用户数据来做出理想决策，除了性能以外，DMP还要收取额外费用，降低数据咨询次数能降低这方面的开销。
　　（a）预算过早耗尽（b）预算波动剧烈
　　主要目标1可由效果预估和出价算法做较大提升，主要目标2和3则极大依赖于预算步进算法。所谓预算步进算法（BudgetPacing）是指通过对历史行为数据的分析，得出一个符合近期趋势的广告预算分配计划，具体计划是预算花费与时间的变化趋势，且通过控制实际的花销进度去接近这个分配计划，最终保证预算的按计划分配。
　　结合实时竞价实际场景，给定一个广告活动（设置预算广告级别）一天的预算限制（总预算则换算成每日预算），在设计一个依照时间变化的分配策略，保证实际花销与理想进度尽可能接近。
　　业界一开始用简易的预算步进算法，用于保证单位时间内的花销大约均等。但一天中广告流量等都在变化，这种方案难以顾及这些问题。Joaquin等人利用动态规划和变分法证明了理想的预算花费并非线性也并非单位时间均等，而是正比于广告交易量。
　　ipinyou数据集中03月11日的竞标和曝光次数趋势图
　　分配计划正比于广告流量的变化趋势，广告投放到一天内任意一个用户的几率均等，从而保证广告均匀的分配到受众群体上，重点是分配机会的均等而非时间段均等。此外，广告关键指标（优化目标）和广告市场的竞争程度也是需要考虑的点。不同时间段内的点击率、转化率等关键指标并非恒定，因此对于广告主来说价值不同。
　　关于广告市场竞争程度，根据YuanShuai等人研究RTB基本问题时，统计的数据图（下图）所示，0到5时由于激烈市场竞争加上较少的用户数会导致非常高的市场成交价，此时广告主投入较多预算得不偿失，竞标的广告主数量的变化趋势与广告流量变化有很大出入。
　　竞标广告主、展示量与时间的变化趋势
　　预算步进算法示意图
　　因此，要基于广告流量、广告质量、市场竞争程度确定分配计划。步骤1用来计算分配计划，对广告请求进行过滤，控制参与竞标的广告请求数量满足预算等限制条件。当赢得交易后扣除预算，步骤2根据实际花销与预计花销之间的差异来实时调整下一个时刻的分配计划。
　　预算步进定义
　　本文提出的预算步进方案采用了概率过滤机制，概率过滤值成为步进率（PacingRate），是一个随时间t的函数：
　　表示某个广告主发起的广告活动adc（campaign或者adset，看预算设置层级）在时段t参与投标的概率。限定广告活动adc是因为不同广告活动设置不同行业、不同目标、不同受众群体等，导致不同广告活动之间差异极大，必须为不同类广告活动设置不同的广告分配计划，可用目标一致，受众群体相似的广告活动作为冷启动时的历史数据。
　　实际操作中难以将p（t）当做连续函数处理，一般将一天时间分段。若一天时间分为T段，则在时段的预计预算花销为：
　　一天总预算：
　　在时间段t内从ADX到来的共n个广告请求为：
　　定义时间段t的请求数函数为req（t），p（t）需要对广告请求进行第一次筛选，初步决定参与投标的广告请求为：
　　0表示未投标，1表示通过初次筛选。那么步进率可表示为：
　　而若投标后赢得竞标的广告请求序列为：
　　1表示赢得，则赢标概率为：
　　这些广告请求最终的花销序列为：
　　未投标和投标失败的花销为0。时段t的实际花费与预计花费的差距越小越好，即：
　　在时段t中平均展示价格为：
　　此处的平均展示价格并非千次，且可根据经验及历史记录统计，线性回归是一个业界常用解决方案。每个指标函数都被指定到一个广告活动adc中，因为不同广告活动在个指标函数中可能存在差异。
　　广告质量度
　　广告展示质量可通过不同时段的关键指标变化体系，点击、转化等等均可作为变化趋势。在质量高的时段投入更多预算能够提高广告效果，应当照顾质量较高的时段。本文定义广告展示质量度量应该能够反映当前时段展示质量与平均展示质量的差距，为：
　　取值范围再0到1之间，可利用一个映射函数：
　　将其控制在所需要的范围内，如logistic函数。定义某广告活动adc的广告展示质量系数函数为：
　　控制其变化速度，建议取值范围：当某时段展示质量接近平均水平是其取值在1附近。
　　市场竞争程度
　　作为DSP本身是拿不到每次请求其他买家的数量，这个数量只有ADX掌握，且广告流量与参与投标的买家数量的变化趋势不相同。然后思考赢标价格或赢标概率能否评价市场竞争程度，是由市场交易机制、参与投标卖家策略、自身出价策略变化而决定，总结出赢标价的高低受广告质量与竞争程度影响。刨除赢标价中对广告展示质量的提现，剩下能够影响到赢标价的因素即竞争程度。
　　定义某时段成交价（记作cpm，注意此时是每次展示）与一天的平均成交价的差距为：
　　为了规范（t）和（t）量级，以便能求差值，需要先求得两数的平方平均数：
　　能够反映时段t的竞争程度，当kpi恒定情况下，cpm越高，这个值越大，同等质量的曝光却又更高的成交价，说明竞争程度高；而另一方面，当cpm稳定而kpi更高时，即用较低的花销买到更好质量的展示，竞争程度低于正常水平。
　　同理经过以平滑映射函数，定义广告活动adc在时段t内的竞争程度系数为：
　　注意两个系数函数的参数和控制函数变化速度，且当竞争程度较高时，步进算法应当降低出价时机，即降低该因子系数从而最终降低该时刻出价概率，而映射函数
　　定义为单调递增的平滑函数，所以应取负号。
　　预算分配计划
　　根据Joaquin等人证明不考虑其他因素时，最佳的分配计划应该完全正比于广告流量，再加上本文提出的广告质量与竞争程度度量，则定义广告活动adc在其t时段的分发概率为：
　　广告活动adc在一天的总预算为：
　　则与之前的个指标有如下关系：
　　利用以上公式可轻易计算出分发概率基准值：
　　并由此得到广告活动adc在各时段的理论下分发概率：
　　应注意算法适用于目标广告库存量远大于购买量的广告活动，对于本身存在欠交付风险买家的广告活动，例如平均分发概率：
　　大于某阈值时，表示可能出现欠交付（UnderDelivery）的可能，可能由于设置受众定向目标过于严苛，或是竞价算法出价太低导致竞标成功率过低。这种情况极其常见，强制使用可能由于数据量稀疏而导致较大的算法误差。
　　预算步进措施
　　实际情况中由于市场波动或是预测精度等原因，实际花费进度可能与预定分配计划有所偏差。为了对这种情况进行调整，本文提出两种措施。
　　第一种措施，是概率过滤方式，利用计算的理论分发概率，结合实际的花费情况不断地调整实际分发概率。定义在时段t实际花费的预算为：
　　那么下一个时段应该将fe分发比率调整为：
　　可见，除t1时，系统在t1时段使用校准过的分发概率，并以此类推保证预算分发进度。而且，实际情况RTB出售的大多是媒体的剩余流量，用户好感度不高，用户点击行为具有很大随机性。这种方法保证每次曝光都有机会参与竞标，尽可能降低系统性能导致的分发风险，是很实用的一种方案。
　　第二种措施，KPI阈值过滤方式，利用公式求出KPI阈值，根据所处KPI阈值范围确定以何种预算策略参与此次投标。
　　KPI阈值过滤广告流量
　　如上图所示，利用历史数据得到时段长度内广告流量在不同KPI的分布函数：
　　找到KPI阈值：
　　使得：
　　同时注意到广告点击性能在某时段t的分布与在一整天的分布趋势是相近的，只是绝对数量不同，从而可降低系统的统计复杂程度，只需在求出此时段的点击次数clks（t）和一天中的点击分布：
　　那么有：
　　运用品友数据集测试后发现，时间迭代模型的去进行广告流量这类预测表现出了较好稳定性，能够反映出历史数据的时效性因素。概率过滤模型在实验中表现出良好的稳定性，受预测精度影响较小；而性能指标阈值过滤在某些时候可以获得更佳的收益，但会略微增加计算难度。
　　本文终于结束了，希望读者对计算广告中主要模块、策略及其场景有个较好的认识和理解，本篇文章仅适合入门了解，不适合深度分析。想要深度分析的话，建议去看国外论文，分享两个GitHub上的论文集：
　　https：github。comwzhe06Adpapers
　　https：github。comwnzhangrtbpapers
　　此外，阅读也有局限性，还是得结合实践，特别是我在复盘本篇文章中的一些思路时，是发现了一些漏洞的，而作者好像故意忽略了这些漏洞。阅读实践思考，才是学习的良好方法，与君共勉。
　　参考文献
　　https：blog。csdn。nettaoqickarticledetails72822727GBDT：梯度提升决策树
　　https：zhuanlan。zhihu。comp61154299前深度学习时代CTR预估模型的演化之路
　　https：daxue。qq。comcontentcontentid3682美团点评柳明海：O2O推荐广告CTR预估实践
　　http：www。huxmarket。comdetail2966DSP的bidding算法
　　计算广告刘鹏、王超
　　http：tech。youmi。net201606158883267。html浅析RTB中的竞价策略
　　https：dolantinlist。github。ioRTB广告竞价系统的算法介绍
　　韩静。在线广告DSP平台实时竞价算法的研究与实现〔D〕。上海交通大学，2015。
　　李佩伦。实时竞价系统中出价算法的研究与实现〔D〕。电子科技大学，2017。
　　郭威。针对在线广告实时竞价系统的相关算法研究〔D〕。电子科技大学，2013。
　　相关阅读
　　计算广告中主要模块、策略及其场景（上篇）