DSP中的基础算法和模型的详细解析：核心算法
第2步（Audience Selection）和第5步(Bidding)是最核心的两步，其中audience selection是离线计算过程，因为可以在exchange发送请求前离线慢慢算好，而bidding的过程需要在100ms内在线快速算好。下面分开介绍这两步中的算法和模型，最后介绍如何对算法效果进行评估。
Audicence Selection:
m6d的Audience Selection算法需要对每个campaign都训练以下两个模型（对每个campaign独立训练模型是因为广告主隐私保护，从一个广告主网站上采集的数据不能用来优化另外一个广告主的模型，例如不能利用京东上访问过电视购买页面的用户数据，来给苏宁电器优化模型，被京东知道了，他们的生意你以后就没得做了。另外一个原因是分每个campaign单独训练模型在训练数据充足的时候可能有更优的效果。当然隐私的原因是主要原因）：
Low-level Model: 这个模型的作用是做初选。所有在该campaign对应的广告主网站上发生转化行为的用户作为正例，其他的用户作为负例(即利用action data)。该模型的特征只有一类，就是用户历史访问过的URL（即利用mapping data）。也就是说，所有可能的URL数就是特征空间的维数，如果用户访问过某个URL，那么这个URL对应的那一维特征的取值就是1，否则就是0. 显而易见，这样会导致特征空间维数太大，所以要做一个最基本的特征选择：去掉那些覆盖用户的转化总数小于某个固定的转化数阈值（比如5）的特征(具体做的时候可以用展现数过滤，阈值设为 转化数阈值/平均转化率)。这样会显著减少特征的数量。即使大幅减少了特征，但数目还是很多，所以这个模型m6d不意外地用了线性模型。
High-level Model: 这个模型的作用是细选。模型的样本和Low-level Model一样，特征就不限于用户访问过的URL了，可以是这个用户的各种挖掘出来的属性标签，包括可解释的分类标签，不可解释的聚类id, topic id，与广告主网站的关联特征等。这里也就是用户属性标签（user profile）起作用最重要的地方了，给用户打标签的技术是很多广告公司的基本功，这里就不着重介绍了。有意思的是，m6d还用了Low-level Model的输出值作为特征之一。这个模型m6d还是选择了线性模型，但因为这个模型要预测的样本数比较少了，可以做一些复杂的计算。m6d选择了一个非线性模型（Generalized additive model with smoothing splines）对结果进行修正。
之所以要分为两个模型，个人认为主要是性能考虑，如果把所有的用户都用high-level model来预测，那么在特征抽取和预测上都会消耗大量的计算量。而low-level模型因为特征只有URL，特征抽取逻辑简单，计算量小很多，另外对于一个campaign的Low-level Model来说，非0权重的特征数目有限，只需要把这些非0权重的url对应的用户拿出来计算预估值就可以了（相当于一个简单检索过程），不需要对所有的用户来计算预估值。
之后，每个campaign就会根据每个用户通过audience selection model预估的转化概率p(c|u)选出目标用户，m6d的经验数据是不超过百分之一的用户会成为某个campaign的目标用户。然后这些目标用户会根据不同的转化概率阈值划分到不同的segments中。例如p(c|u)>0.01放到一个segment中，0.01>= p(c|u) > 0.001放到另外一个segment中。论文中没有说到一个用户是否可以放到两个或以上的segment中，但我觉得应该是可以的。每个campaign有大约10到50个segments左右。划分segments的作用一是方便账户管理员对每个segment设置基础出价，另外在后面介绍的bidding算法中将属于同一个segment的用户做无差别对待，相当于同属一个类，可以缓解某些用户数据稀疏的问题，后面会详细介绍。
以上就是m6d的audience selection算法，值得注意的是，上述步骤是offline的，也即是预处理的，在exchange的请求到来前就已经对每个campaign都算好了。有的地方把根据广告主的一些少量已知转化用户找到更多潜在用户的模型叫做Look-alike Model, 我理解这里的audience selection model也应该算是look-alike model。
Bidding
当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的算法，以基础出价为基准，根据当前广告位计算出一个调整因子Φ，最后的出价就是baseprice∗Φ 。因此我们全部的工作就是要计算这个Φ。
如果上过刘鹏老师的计算广告学课的同学肯定会知道，在广义二阶竞价模型里，排序是应该按照 ecpm=转化概率*转化价值 来排序的。ecpm可以认为是一个展现的价值，它等于一个转化的价值*一个展现变为一个转化的概率。其实我想说的就是，对于同一个campaign来说，如果我们知道一个展现的转化率是另外一个展现的2倍，那么前面那个展现的出价应该是后面那个展现的出价的2倍。
按照上面的逻辑，既然我们为segments出了一个平均价格base price，当仅当一个展现的转化率是这个segments中用户的平均转化率的Φ倍，我们应该为这个展现出baseprice∗Φ的出价。所以
其中，u指的是用户，i是当前的广告位(inventory)，c指的是转化。分母计算的是在所有广告位（用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也对i的部分做了类似的trick，它把类似的广告位聚合到一起，给予一个相同的inventory id。目的和把u变为s是类似的。m6d的inventories的规模是5000个左右，每个campaign的segment的个数是10到50个左右。
以上就是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）和不考虑广告位对转化率的预估由有多大的影响呢？以下的图展示了区别：
考虑广告位信息后，AUC提升了0.0346，还是非常明显的。这个Lift也是一种评估指标，后面会详细解释。这里可以看到Lift指标也明显提升了。
具体看个例子。对于一个hotel广告主的一个campaign，不同的广告位预估出来的Φ值也很不相同，旅游类的预估值最高，社会媒体的最低。说明这个模型还是有一定区分度的。
评估
1. 模型评估
通常我们用AUC来评估模型的排序能力，但是AUC有一个问题是它无差别地考察了一个列表中所有位置的排序合理性，而对于我们的audience selection模型，转化率预估模型，我们更看重是否把最靠谱的拍在了前面，换句话说，是更看重这个列表中，前面的位置的排序合理性。因此m6d用了Lift指标。Lift@5% 指标衡量了在前5%的结果中，正例的比例比在随机情况下正例出现的比例高了多少。具体的Lift定义可以看：http:/ /en .wikipedia.org/wiki/Lift_(data_mining)
2. 业务目标评估
对于DSP的投放效果，m6d主要会看两个业务指标，一个是转化率（PVSVR）, 即转化数除以展现数（即CTR*CVR）；另外一个是CPA, 即获得每一个转化，平均花了多少钱。
m6d的广告主大多喜欢按CPM方式购买展现，找n家DSP来同时投放，给一样的CPM，然后看谁的转化率高。因此转化率是DSP赖以生存的指标之一。
转化率是和价格无关的，而如果一家DSP虽然转化率低10%，但是每个展现的价格（cpm）比别人低50%，那么对于广告主来说，还是会选择它的。因为它的CPA更低了，即获取一个转化，广告主需要付出的成本更低了。
所以，DSP的转化率是和利润挂钩的，要么把技术做得很好提高转化率，这样在保持CPA不变的情况下，向广告主收取更高的CPM，从而赚更多的钱。否则就只能比别人卖得更便宜了，甚至亏本了。当然，聪明的DSP会在早期先砸VC的钱亏本吸引广告主来投放，投放是可以累积数据的，有了数据下次就可以把转化率做得更好，从而再把钱赚回来。
也有广告主是按每个点击付费的（CPC），有的广告主是给一笔固定的投放预算，但其实最后都是类似的，广告主最终会去换算成CPA来进行比较。（只重视展现量的广告主除外） |
楼主
标题置顶
标题高亮
