Bid Optimizing and Inventory Scoring in Targeted Online Advertising
这篇文章来自美国一家很优秀的DSP公司——M6D,介绍了DSP的工作流程和其中的一个核心技术：real-time bidding(实时竞价技术)
实时竞价：找准正确的广告信息和广告位信息，以一个能够反映真实价格的竞拍价格参与广告展示机会的竞价
M6D竞价流程
- 追踪用户行为：DSP公司通常会在广告主的网站上埋点（即放上一个1x1的不可见像素），这样当互联网用户第一次访问广告主的网站时，就会得到DSP公司的一个cookie，这样DSP公司就可以追踪到这个网民的在广告主网站上的行为了(这些数据也叫action data)。DSP公司还会和第三方的网站合作（例如：新浪，腾讯），在他们的网站上也埋点，或者向DMP购买网民行为数据，这样就可以追踪到网民在这些网站上的行为了(这些数据也叫mapping data)。这里值得一提的是，DSP公司对某一个用户记录的cookie和第三方网站或DMP或exchange记录的cookie是不一样的，这里需要一个叫Cookie Mapping的过程，这不是本文重点，以下假设DSP已经做好了Cookie Mapping，每个用户有一个唯一的id标识。
- 受众选择（audience selection）: m6d对每一个campaign(即每一个广告主的每个推广活动), 训练一个audience selection model, 该模型以在广告主的网站上发生转化行为（转化行为可以是注册成为用户，点击某个特定页面，购买产品。每个广告主对转化的定义不一样）的用户为正例，没有发生转化行为的用户为负例（是的，正负例很不均匀，通常要做采样和结果修正）。得到模型后，对所有的用户预估对这个campaign的转化概率p(c | u),即该用户u有多大的概率会在广告主的网站上发生转化行为（c表示conversion），去掉大多数转化概率非常小的用户，将目标用户根据转化概率高低分到不同的segments中。这样我们对每个campaign就找到了很多的目标用户，而且这些用户根据他们的质量高低，被分别放在不同的segments中。
- 通知exchange: DSP将这些目标用户的cookie告诉exchange，这样当有这些cookie的请求来的时候，exchange才会来向DSP的服务器发送请求。
- Segment管理： 通常DSP公司会有账户管理员（运营人员），他们人工来对每个campaign的做一些设定。他们根据每个campaign所属的行业特点，经济状况，决定开启哪些segments，关掉哪些segments。例如：对没钱的小公司的campaign, 那些用户转化概率小一些的segment就不要投广告了。他们还需要对每个segment设定一个基础出价（base price）。账户管理员可以拿到每个segment的平均预估转化概率，来辅助他们设定基础出价。这一步也是人工影响投放策略最主要的地方。
- 进行实时竞价：当exchange把请求发过来的时候，DSP会拿到以下信息：当前广告位的信息，当前用户的cookie和基本信息。DSP需要在100ms内，根据对当前用户的理解，并且考虑当前广告位，根据自己的bidding算法，来要决定是否要买这次展现，投放哪个campaign的广告，出价是多少（bidding），并向exchange返回出价信息？如果超过时间DSP没有响应，则exchange默认DSP放弃这次竞价。
- 展现广告：如果赢得了展现机会，则DSP返回创意，用户就会在该广告位看到该创意。
- 追踪转化：因为DSP在广告主的网站上埋了点，就能知道用户是否在这次展现之后进行了转化行为。根据这些数据统计转化率，每个转化平均成本等指标，汇总成报告给广告主。
核心算法
当exchange发送请求时，DSP会接受到当前用户的cookie和一些最基本的用户信息，以及当前广告位的信息。DSP则需要找到这个用户所属的所有segments，而这些segments可能会对应多个campaign。那么应该出哪个campaign的广告呢？这里有一个内部竞价的过程。
m6d是这么做的，首先要把一些不合适出广告的campaign根据规则过去掉。主要的规则有，如果一个用户之前已经被展现了这个campaign的广告数达到一定的个数了，那么就不要再浪费广告费了（这个次数限制通常叫frequency cap）。另外一个主要规则是，如果一个campaign已经达到了它的每日，或者每周，或者每月预算限制了，那么也不再为它投放广告了。对于剩下的campaign候选，DSP会对他们都根据算法计算出最合适的出价，然后简单地选取出价最高的那个（出价反映了当前用户对该campaign的价值）。
下面介绍下对于某一个campaign, 如何计算对当前展现机会的出价。
前面的audience selection部分，我们已经对每个用户划分了segments，然后账户管理员又对每个segment给出了基础出价（base price），当时这个出价考虑的是这个用户和这个campaign的适合程度，并没有考虑当前广告位是否适合这个campaign投广告，是否适合这个用户。因此m6d的算法，以基础出价为基准，根据当前广告位计算出一个调整因子$\phi$，最后的出价就是$baseprice * \phi$ 。因此我们全部的工作就是要计算这个$\phi$。
计算调整因子$\phi$的依据
在实时竞价中，一次展示机会的价值可以由其带来的真正效益来衡量，我们用转化率*转化价值来表示
由于转化价值不好估计，我们就在转化率上面做文章。
对于同一个campaign来说，如果我们知道一个展现的转化率是另外一个展现的2倍，那么前面那个展现的出价应该是后面那个展现的出价的2倍。这就是M6D设计的竞价函数的依据。
调整因子$\phi$计算
按照上面的逻辑，既然我们为segments出了一个平均价格baseprice，当一个展现机会的的转化率是这个segments中用户的平均转化率的$\phi$倍，我们应该为这个展现出$baseprice * \phi$的出价。因此有：
其中，u指的是用户，i是当前的广告位(inventory)，c指的是转化，a指某一具体的广告。分母计算的是在所有广告位（用j指代）上的平均转化率。这个分母要计算起来很复杂，我们要遍历所有的广告位(inventory)。但我们知道：
因此最终调整因子的计算化简为：
所以m6d的bidding算法的最核心部分，就是为每个campaign都建立两个模型来分别预估p(c|u,i)和p(c|u)。考虑到每个campaign的转化数据很少，这2个模型的训练数据很少，要训练这两个模型太难了。因此m6d将同一个segment中的用户不做区分，从而可以把上式变为
其中，s是segment。这样就只需要训练p(c|s,i)和p(c|s)。因为s的个数远小于u的个数，这2个模型的特征空间显著变小了，模型更容易得到更好的结果。
模型训练
以上就是m6d对bidding的建模过程了，剩下的工作就是如何训练得到这两个模型。
p(c|s,i)模型: 要得到这个模型的训练数据，还有一个冷启动的过程。必须事先对这些segments在这些inventories上投放，然后把那些最终带来转化的展现标记为正例，没有最终带来转化的展现标记为负例。m6d认为一次转化是由之前7天内该用户见到的最后一次展现带来的。这个模型的特征只有两类，一类就是segment id, 另外一类就是inventory id。也就是说，每一个样本只有两个非0的特征，一个是segment id对应的那个特征，另外一个是inventory id对应的那个特征。m6d没有组合segment和inventory特征，这样做的结果是：不管对于哪个segment，某个特定的inventory对最后预估值的贡献都是一样的。这个假设可以认为在大多数情况下是合理的。而且如果真要把这些组合特征加入模型，特征空间一下子又大了不少，对于少得可怜的训练数据来说，很容易就过拟合了。
p(c|s)模型：和p(c|s,i)模型基本一样，区别就是特征只有segment id。
这两个模型的正例比例都非常低，因此训练过程中进行了采样（sampling）和修正（recalibration）。
结果分析
考虑了广告位（inventory）和不考虑广告位对转化率的预估由有多大的影响呢？以下的图展示了区别：
具体看个例子。对于一个hotel广告主的一个campaign，不同的广告位预估出来的$\phi$值也很不相同，旅游类的预估值最高，社会媒体的最低。说明这个模型还是有一定区分度的。
