本文介绍的是CIKM20上百度发表的一篇有关展示广告召回阶段样本优化的文章，论文名称是《Sample Optimization For Display Advertising》。文章提出了多种样本优化的方法，极大提升了线上广告收入，一起来学习一下。

1、背景

工业界广告排序系统大都至少包括两个阶段：候选生成阶段（召回阶段）和排序阶段，如下图所示：

本文我们主要关注召回阶段，在这一阶段，通常是多种策略并行，如协同过滤、基于上下文的召回等等。在百度的系统中，最广泛使用的召回的方式是双塔模型。从数据层面来看，训练一个合适的召回模型，面临如下几方面的挑战：

1）样本选择偏差：召回阶段模型训练的样本是经过排序阶段后最终展示给用户的，仅有一小部分的广告会展示给用户。但模型需要对整个广告队列进行预测，二者存在样本选择偏差。
2）真实的广告曝光分布通常是长尾的，一小部分广告占据了大部分的曝光，这些广告通常有更高的出价，具有更高的ecpm。但由于大部分曝光的广告没有被用户点击，这些高价值的广告通常多次被标记为负样本，其召回概率也降低，平台的收益也会随之下降。
3）曝光但未点击的广告，并不一定是真正的负样本。在广告系统中，一个广告未被点击通常出于多方面的原因，并不能直接认为这些广告与用户兴趣不匹配。
4）广告点击率低，导致样本中正分样本的数量差距较大，正样本比较稀疏。

对于以上几方面的问题，在召回阶段如何从数据层面进行优化呢？论文提出了多种策略，一起来看一下。

2、样本优化

本文提出的策略主要包括Weighted Random Negative Sampling、Real-Negative Subsampling、Sample refinement with PU Learning、Fuzzy Positive Sample Augmentation和Sampling with Noise Contrastive Estimation (NCE)。接下来分别进行简单的介绍。

2.1 Weighted Random Negative Sampling

第一种方法是使用负采样方式来丰富训练样本。由于广告曝光存在明显的长尾现象，因此论文提出了分片加权负采样的方式（ piece-wise weighted negative sampling method）。

具体的做法是：首先基于广告的曝光频次对广告进行分组，曝光次数大于一定阈值的计作Ah，曝光次数小于一定阈值的计作Al。随后，产生一个(0,1)之间的随机数p，如果随机数p<pl，则从Al使用均匀采样的方式采样得到一个广告，否则从Ah中基于一元模型分布(unigram distribution)采样一个负样本广告（这里可以参考word2vec里面的negative sampling方式，本文不进行详述）。其中pl定义如下：

上式中f(ai)为广告ai的曝光频次。而Ah中每个广告的被选择概率为：

由于||Al||远大于||Ah||，相比于原始的负采样方式，存储和时间复杂度上也是明显有降低的。

2.2 Real-Negative Subsampling

在百度的广告平台，广告点击率大约只有0.03%，由于长尾分布的存在，一小部分头部的广告占据了大部分的曝光，这些广告可能同时出现在正样本集合（曝光点击）和负样本集合（曝光未点击）中。这些头部广告往往具有更高的商业价值，因此不希望这些样本在负样本集合中出现太多次，因此会对这部分广告的负样本进行降采样。

具体的，具有高曝光的广告的负样本，基于以下的概率进行抛弃：

上式中第二项的分母是归一化后的曝光频次，分子β为设定好的阈值。广告的曝光频次越高，第二项越小，则抛弃概率更高。

这样的降采样方法，极大保证了线上的CPM指标（广告收入指标），在后文的实验结果中可以看到。

2.3 Sample refinement with PU Learning

这一种方法主要针对曝光未点击样本。曝光未点击可能是出于多种原因，并不一定代表用户真的不感兴趣，因此这里采用了一种PU learning的方式。将收集到的数据分为正样本和未标记样本。通过'spy technique'从未标记样本中找到比较置信的负样本。

1）首先从正样本集合P中随机选取一部分spy set，计作S，并将S加入到未标记样本集合U中；
2）使用去除S后的正样本集合P\S，作为正样本，U和S的交集作为负样本，训练biased SVM classifer（可参考论文《Building Text Classi ers Using Positive and Unlabeled Examples》）
3）使用得到的分类器计算U中每个样本的点击概率
4）计算spy set中所有样本的平均点击概率
5）U中预测点击率小于4）中得到的平均点击概率的样本，作为比较置信的负样本，计作RN。

最后，可以使用正样本集合P和RN来训练得到召回模型。

2.4 Fuzzy Positive Sample Augmentation

为了缓解正样本稀疏的问题，这里采用了一种较为启发式的方式来扩充正样本。在最终返回的广告列表中，只有头部的广告曝光给了用户，还有很多没有得到曝光，虽然这些样本没有得到曝光，但是是经过召回阶段和排序阶段的广告，有更高的概率与用户的兴趣相匹配。因此，从这部分未曝光的样本中，选择CPM高于预先设定阈值的样本作为模糊正样本，加入到模型训练中，但这些样本的label并非为1，而是小于1的数。

2.5 Sampling with Noise Contrastive Estimation (NCE)

最后一种方法是在采样时使用Noise Contrastive Estimation (NCE)的方式。关于NCE，可以参考论文《Noise-contrastive estimation: A new estimation principle for unnormalized statistical models》，这里不在详述。