在google 发表的paper: 《Label Partitioning For Sublinear Ranking》中，有过介绍：

一、介绍

许多任务的目标是：对一个巨大的items、documents 或者labels进行排序，返回给其中少量的top K给用户。例如，推荐系统任务，比如：通过协同过滤，需要对产品（比如：电影或音乐）的一个大集合，根据给定的user profile进行排序。对于注解任务（annotation），比如：对图片进行关键词注解，需要通过给定的图片像素，给出的可能注解的一个大集合进行排序。最后，在信息检索中，文档的大集合（文本、图片or视频）会基于用户提供的query进行排序。该paper会涉及到实体(items, documents, 等)，被当作labels进行排序，所有上述的问题都看成是标签排序问题（label ranking problem）。在机器学习界中，提出了许多强大的算法应用于该领域。这些方法通常会通过对每个标签（label）依次进行打分（scoring）后根据可能性进行排序，可以使用比如SVM, 神经网络，决策树，其它流行方法等。我们将这些方法称为标签打分器（label scorers）。由于对标签打分是独立进行的，许多这些方法的开销与label的数量上是成线性关系的。因而，不幸的是，当标签数目为上百万或者更多时变得不实际，在serving time时会很慢。

本paper的目标是：当面临着在现实世界中具有海量的labels的情况时，让这些方法变得实用。这里并没有提出一种新方法来替换你喜欢的方法，我们提出了一个”wrapper”方法，当想继续维持（maintaining）或者提升(improve) accuracy时，这种算法能让这些方法更容易驾驭。(注意，我们的方法会改善测试时间，而非训练时间，作为一个wrapper方法，在训练时实际不会更快)

该算法首先会将输入空间进行划分，因而，任意给定的样本可以被映射到一个分区（partition）或者某分区集合(set of partitions)中。在每个分区中，只有标签的一个子集可以由给定的label scorer进行打分。我们提出该算法，用于优化输入分区，以及标签如何分配给分区。两种算法会考虑选择label scorer，来优化整体的precision @ k。我们展示了如何不需考虑这些因素，比如，label scorer的分区独立性，会导致更差的性能表现。这是因为当标签分区时（label partitioning），对于给定输入，最可能被纠正（根据ground truth）的是labels的子集，原始label scorer实际上表现也不错。我们的算法提供了一个优雅的方式来捕获这些期望。

本paper主要：

• 引入通过label partitioning，在一个base scorer上进行加速的概念
• 对于输入划分(input partitioning)，我们提供了一个算法来优化期望的预测（precision@K）
• 对于标签分配（label assignment），我们提供了一个算法来优化期望的预测（precision@K）
• 应用在现实世界中的海量数据集，来展示该方法

二、前置工作

有许多算法可以用于对标签进行打分和排序，它们与label set的size成线性时间关系。因为它们的打分操作会依次对每个label进行。例如，one-vs-rest方法，可以用于为每个label训练一个模型。这种模型本身可以是任何方法：线性SVM，kernel SVM，神经网络，决策树，或者其它方法。对于图片标注任务，也可以以这种方法进行。对于协同过滤，一个items的集合可以被排序，好多人提出了许多方法应用于该任务，也是通常依次为每个item进行打分，例如：item-based CF，latent ranking模型(Weimer et al.2007)，或SVD-based系统。最终，在IR领域，会对一个文档集合进行排序，SVM和神经网络，以及LambdaRank和RankNet是流行的选择。在这种情况下，不同于注解任务通常只会训练单个模型，它对输入特征和要排序的文档有一个联合表示，这样可以区别于one-vs-test训练法。然而，文档仍然会在线性时间上独立打分。本paper的目标是，提供一个wrapper方法来加速这些系统。

有许多算法用来加速，这些算法取决于对输入空间进行hashing，比如通过局部敏感哈希(LSH: locality-sensitive hashing)，或者通过构建一棵树来完成。本文则使用分区的方法来加速label scorer。对于该原因，该方法可以相当不同，因为我们不需要将样本存储在分区上（来找到最近邻），我们也不需要对样本进行划分，而是对label进行划分，这样，分区的数目会更小。

在sublinear classification schemes上，近期有许多方法。我们的方法主要关注点在ranking上，而非classification上。例如：label embedding trees（bengio et al.,2010）可以将label划分用来正确分类样本，(Deng et al.,2011)提出一种相似的改进版算法。其它方法如DAGs，filter tree, fast ECOC，也主要关注在快速分类上。尽管如此，我们的算法也可以运行图片标注任务。

3.Label Partitioning

给定一个数据集: pairs $(x_i, y_i), i=1, …, m $. 在每个pair中，$ x_i $是输入，$ y_i $是labels的集合（通常是可能的labels D的一个子集）。我们的目标是：给定一个新的样本 $ x^{*} $, 为整个labels集合D进行排序，并输出top k给用户，它们包含了最可能相关的结果。注意，我们提到的集合D是一个”labels”的集合，但我们可以很容易地将它们看成是一个关于文档的集合（例如：我们对文本文档进行ranking），或者是一个items的集合（比如：协同过滤里要推荐的items）。在所有情况下，我们感兴趣的问题是：D非常大，如果算法随label集合的size规模成线性比例，那么该算法在预测阶段并不合适使用。

假设用户已经训练了一个label scorer: $f(x,y)$， 对于一个给定的输入和单个label，它可以返回一个real-valued型的分值(score)。在D中对这些labels进行ranking，可以对所有$ y \in D$，通过简单计算f(x,y)进行排序来执行。这对于D很大的情况是不实际的。再者，在计算完所有的f(x,y)后，你仍会另外做sorting计算，或者做topK的计算（比如：使用一个heap）。

我们的目标是：给定一个线性时间(或更差)的label scorer: f(x,y)，能让它在预测时更快（并保持或提升accuracy）。我们提出的方法：label partitioning，有两部分构成：

• (i)输入分区（input partititoner）: 对于一个给定的样本，将它映射到输入空间的一或多个分区上
• (ii)标签分配（label assignment）: 它会为每个分区分配labels的一个子集

对于一个给定的样本，label scorer只会使用在相对应分区的labels子集，因此它的计算更快。

在预测时，对这些labels进行ranking的过程如下：

• 1.给定一个测试输入x，input partitioner会将x映射到partitions的某一个集合中： $ p=g(x) $

• 2.我们检索每个被分配到分区 $ p_j $上的标签集合(label sets)：$$ L = \bigcup_{j=1}^{

  p

  } \mathscr{L}{p_j} \(，其中\) \mathscr{L}{p_j} \subseteq D $$是分配给分区 $ p_j $的标签子集。

• 3.使用label scorer函数$ f(x,y) $对满足$ y \in L $的labels进行打分，并对它们进行排序来产生我们最终的结果

在预测阶段ranking的开销，已经被附加在将输入分配到对应分区（通过计算$ p=g(x) $来得到）上的开销；以及在相对应的分区上计算每个label（计算: $ f(x,y), y \in L $）。通过使用快速的input partitioner，就不用再取决于label set的size大小了（比如：使用hashing或者tree-based lookup）。提供给scorer的labels set的大小是确定的，相对小很多（例如：$ |L| « |D| $），我们可以确保整个预测过程在$ |D| $上是亚线性(sublinear)的。

3.1 输入分区（Input Partitioner）

我们将如何选择一个输入分区（input partitioner）的问题看成是：$ g(x) \rightarrow p \subseteq \mathcal{P} $，它将一个输入点x映射到一个分区p的集合中，其中P是可能的分区：$ \mathcal{P} = \lbrace 1,…,P \rbrace $。g总是映射到单个整数上，因而，每个输入只会映射到单个分区，但这不是必须的。

有许多文献适合我们的input partitioning任务。例如：可以使用最近邻算法作为input partitioner，比如，对输入x做hashing（Indyk & Motwani, 1998)，或者tree-based clustering和assignment (e.g. hierarchical k-means (Duda et al., 1995)，或者KD-trees (Bentley, 1975)，这些方法都可行，我们只需关注label assignment即可。然而，注意，这些方法可以对我们的数据有效地执行完全非监督式划分分区（fully unsupervised partitioning），但不会对我们的任务的唯一需求考虑进去：即我们希望在加速的同时还要保持accuracy。为了达到该目标，我们将输入空间进行分区：让具有相似相关标签（relevant labels：它们通过label scorer进行高度排序）的相应样本在同一个分区内。

我们提出了一种层次化分区（hierarchical partitioner）的方法，对于：

• 一个标签打分函数（label scorer）：$f(x,y)$
• 一个训练集：$(x_i,y_i), i=\lbrace 1,…,m \rbrace $，（注：x为input，y为label）
• 之前定义的label集合D

它尝试优化目标：precision@k。对于一个给定的训练样本$(x_i,y_i)$以及label scorer，我们定义了：

accuracy的measure（比如：precision@k）为：

以及最小化loss为：

注意，上述的f(x)是对所有labels的得分向量（f(x)与f(x,y)不同）：

其中$ D_i $是整个label set上的第i个label。然而，为了衡量label partitioner的loss，而非label scorer，我们需要考虑$l(f_{g(x_i)}(x_i), y_i)$，该值为ranking时$x_i$对应的分区上的label set的loss。比如：$ f_{g(x)}(x)=(f(x,L_1),…,f(x,L_{|L|)})) $

对于一个给定的分区，我们定义它的整个loss为：

不幸的是，当训练输入分区（input partitioner）时，L(label assignments)是未知的，它会让上述的目标函数不可解(infeasible)。然而，该模型发生的errors可以分解成一些成分（components）。对于任意给定的样本，如果发生以下情况，它的precision@k会收到一个较低值或是0:

• 在一个分区里，相关的标签不在该集合中
• 原始的label scorer在排第一位的分值就低

当我们不知道label assignment时，我们将会把每个分区上labels的数目限制在一个相对小的数（$ |L_j|«|D| $）。实际上，我们会将考虑两点来定义标签分区（label partitioner）：

• 对于共享着高度相关标签的样本，应被映射到相同的分区上
• 当学习一个partitioner时，对于label scorer表现好的样本，应被优先(prioritized)处理

基于此，我们提出了方法来进行输入分区（input partitioning）。让我们看下这种情况：假如定义了分区中心(partition centroids) $c_i, i=1,…,P$，某种划分，它使用最接近分配的分区：

这可以很容易地泛化到层次化的情况中（hierarchical case），通过递归选择子中心(child centroids)来完成，通常在hierarchical k-means和其它方法中使用。

加权层次化分区（Weighted Hierarchical Partitioner） ，这是一种来确保输入分区（input partitioner）对于那些使用给定label scorer表现较好的样本（根据precision）进行优先处理的简单方法。采用的作法是，对每个训练样本进行加权：

实际上，一个基于该目标函数的层次化分区（hierarchical partitioner），可以通过一个“加权(weighted)”版本的 hierarchical k-means来完成。在我们的实验中，我们简单地执行一个”hard”版本：我们只在训练样本集合 $ \lbrace (x_i,y_i): \hat{l}(f(x_i),y_i) \geq \rho \rbrace $上运行k-means，取ρ = 1。

注意，我们没有使用 $ l(f_{g(x_i)}(x_i), y_i) $, 而是使用$ l(f(x_i),y_i) $，但它是未知的。然而，如果$ y_i \in L_{g(x_i)}$，则：$ l(f_{g(x_i)}(x_i), y_i) \leq l(f_D(x_i),y_i) $，否则，$ l(f_{g(x_i)}(x_i), y_i)=1$。也就是说，我们使用的proxy loss，上界逼近真实值，因为比起完整的集合，我们只有很少的label，因而precision不能降低——除非真实label不在分区中。为了阻止后面的情况，我们必须确保具有相似label的样本在同一个分区中，我们可以通过学习一个合适的metrics来完成。

加权嵌入式分区（Weighted Embedded Partitioners）, 在上述构建加权层次式分区器（weighted hierarchical partitioner）时，我们可以更进一步，引入约束（constraint）：共享着高度相关labels的样本会被映射到同一个分区（partitioner）上。编码这些constraint可以通过一种metric learning阶段来完成(Weinberger et al., 2006).。

接着，你可以学习一个input partitioner，通过使用上面的weighted hierarchical partitioner目标函数，在要学的”embedding”空间上处理：

然而，一些label scorer已经学到了一个latent “embedding” space。例如，SVD和LSI等模型，以及一些神经网络模型（Bai et al., 2009). 在这样的case中，你可以在隐空间(latent space)上直接执行input partitioning，而非在输入空间上；例如：如果label scorer模型的形式是：$ f(x,y)= \Phi_{x}(x)^T \Phi_{y}(y) $，那么partitioning可以在空间 $ \Phi_x(x) $上执行。这同样可以节省计算两个embeddings（一个用于label partitioning，一个用于label scorer）的时间，在特征空间中的进一步分区则为label scorer调整。

3.2 Label Assignment

本节将来看下如何选择一个L（label assignment）。

• 训练集$ (x_i,y_i), i=1,…,m $，label set为：D
• input partitioner: g(x)，使用之前的方式构建
• 线性时间label scorer: f(x,y)

我们希望学到label assignment: $ L_j \subseteq D $，第j个分区对应的label set。我们提出的label assignment方法会应用到每个分区中。首先，来考虑下优化precision@1的情况，这种简化版的case中，每个样本只有一个相关的label。这里我们使用索引t来索引训练样本，相关的label为$ y_t $。我们定义：$ \alpha \in \lbrace 0,1 \rbrace^{|D|}$，其中$ \alpha_{i} $决定着一个label $ D_i $是否会被分配到该分区上（$ \alpha_{i}=1 $），或不分配（$ \alpha_{i}=0 $）。这里的$ \alpha_{i} $就是我们希望优化的变量。接下去，我们通过给定的label scorer对rankings进行编码：

• $ R_{t,i} $是对于样本t的label i的rank分值：

• $ R_{t,y_t} $是样本t的true label的rank分值

我们接着将需要优化的目标函数写出来：

…(1)

服从：

…(2)

…(3)

其中，C是分配给该分区的label数。对于一个给定的样本t，为了最大化precision@1,需满足两个条件：

• (1) true label必须被分配给该分区
• (2) true label必须是所有被分配labels上排序分值最高的

我们可以看到，等式1可以精确计算precision@1，因为项$ \alpha_{y_t} $和$ (1-max_{R_{t,i}<R_{t,y_t}} \alpha_{i}) $ 会对这两个条件各自进行measure。我们的目标函数会统计训练样本数precision@1。

有意思的是，注意，label partitioning的性质意味着：

• (i) 如果训练样本t在原始的label scorer上标记不正确，但由于高度不相关的label不会被分配到该分区上，会被label partitioner正确标注
• (ii) 原始的label scorer可以正确标注样本，但由于相关的label没有被分配到该分区上，会被label partitioner标注不正确

该优化问题，尽可能地将多个相关的label放在同一分区中，并且尽可能消除尽可能混淆的labels（高排序值但不正确），如果通过移除它们，更多的样本会被正确标注。如图1所示：

图1: 如何从D中选择2个labels的label assignment问题，只考虑它的precision@1。这里的$ R_i $是样本排序后的labels（粗体为true labels）。当选择为sky时，会正确预测样本1和2；而对于样本3-5，sky比true labels的排序还要高。最优的选择是car和house，它们在样本3-5中可以被正确预测，因为所有有更高排序但不相关labels（higher-ranked irrelevant labels）会被抛弃掉。这种选择问题就是我们在label assignment任务中要面临的挑战。

不幸的是，等式2的二元限制（binary constraint）致使等式(1)的最优化变得很难，但我们可以将约束放松些：

…(4)

$ \alpha $的值不再离散（discrete），我们不会使用等式（3)的约束，但在训练后会对连续值$ \alpha_{i}$做排序，会采用最大的C label作为分区的成员。

我们将上述泛化成pricision@k（k>1）的情况。如果至少一个“不相关(violating)”的label排在相关label之上，我们必须统计排在相关label之上的violations的数目。回到未放松约束的最优化问题上，我们有：

…(5)

服从：

…(6)

这里对于precision@k的优化，如果 r<k，我们可以简单地取$ \Phi(r) = 0 $，否则取1。

我们已经讨论了具有一个相关标签的情况，但在许多情况下，样本具有多个相关标签的情况是很常见的，它可以使得loss的计算变得稍微更具挑战性些。我们回到precision@1的情况。在这种情况下，原始的目标函数（等式（1））将返回为：

…(7)

服从：

…(8)

这里，$ y_t $包含着许多相关标签 $ y \in y_t $，如果它们中的所有都是排在前面的（top-ranked），那么会得到一个precision@1为1,这样我们可以取 $ max_{y \in y_t}$

我们可以结合等式(5)和等式(7)来形成一个关于precision@k的cost function，用于multi-label的训练样本上。为了更适合优化，我们使用一个sigmoid来将在等式(7)中的约束$max_{y \in y_t}$放松到一个均值和近似值 $ \Phi(r) $：

我们的目标接着变成：

…(9)

服从：

…(10)

对于单个样本，期等的目标是一个相关label出现在top k中。然而，当penalty不会影响真实排序位置的情况下不成立（例如：我们原始的cost等价于在位置k+1的排序，或者在位置$|D|$的位置）。早前我们希望那些label scorer的执行很差的样本降低其重要性。为了达到该目的，我们引入了一个带加权项（term weighting）的样本，通过使用原始label scorer得到的相关label排序的反序来实现，等式(4)和等式(9)变为：

这里我们作了简化：$w(R_{t,y}) = (R_{t,y})^{\lambda}, \lambda \geq 0 $，在我们的试验中，设置$\lambda=1$（该值越高会抑制具有更低排序的相关label的样本）。这些等式表示了label assignment objective的放宽条件版本的最终形式，可以使用SGA（随机梯度上升：A: ascent）进行优化。

最优化注意事项(Optimization Considerations) 我们考虑这样的情况，被选中的输入分区g(x)，表示每个输入x映射到单个分区上。每个分区的label assignment问题是独立的，这允许它们可以并行的求解（例如：使用MapReduce框架）。为了进一步减小训练时间，对于每个分区我们在完整label set上的一个子集上进行优化（例如：选择 $ \hat{D} \subseteq D, C < |\hat{D}| < |D| $）。对于每个分区，我们选择$ \hat{D} $：它是在该分区的训练样本中使用原始label scorer进行排序的最高排序的相关label。在所有的实验中，我们设置$ | \hat{D} | = 2C $。注意，在我们的实验中，我们发现设置成$ | \hat{D} | = 2C $后减少参数集的size，影响可忽略不计。原因是，任何分区中在任何训练样本中，在D中大部分labels不会作为相关labels出现。因为这样的labels不会接受任何正值的梯度更新。

统计Heuristic baseline 通过比较我们提出的label assignment的最优化，在我们的实验中，我们也考虑了一个更简单的Heuristic：只考虑等式(1)的第一项，例如：$ max_{\alpha} \sum_{t} \alpha_{t_t}$。这种情况下，最优化可以简化为：只需统计在分区中的每个true label的出现次数，并让C保持为最多的labels。这种基于统计的assignment提供了一个很好的baseline，来对比我们提出的优化。

4.实验

4.1 图像注解

首先使用ImageNet数据集来测试图片注解任务。ImageNet是一个很大的图片数据集，它将人口验证通过的图片与WordNet的概念相绑定。我们使用Spring 2010的版本，它具有9M的images，我们使用：10%用于validation, 10%用于test，80%用于training。该任务会对15589个可能的labels做rank，它们的范围从animals(“white admiral butterfly”)到objects(“refracting telescope”).

…【略】

4.2 视频推荐

从一个大型在线视频社区给用户推荐视频。上百万最流行的视频被认为是集合D，我们的目标是，对一个给定用户排序这些视频，并提供给该用户相关的视频。训练数据的格式中每个训练pair都基于一个匿名用户。对于每个用户，输入$x_i$是表示他的偏好的一个特征集合。这些特征通过聚合每个用户所感兴趣的所有视频的主题来生成。这些主题集合接着被聚类成各特征列。有2069个这样的聚类特征列（clusters）来表示用户，其中任何时候有10个聚类特征列是表示活跃的（意思：每个用户大致都有10个以上的特征）。label $y_i$是已知相关视频的一个集合。该数据集包含了1亿的样本，每个样本具有2069个输入特征，平均接近有10个相关视频。我们设置另外50w的样本用于validation，1M样本用于test。

我们的baseline label scorer $W_{SABIE}$在P@10上对比于Naive Bayes，它给出了108%的提升。因而，baseline已经足够强了。我们接着使用hierarchical k-means，它具有10000个分区，以及许多种label assignment set sizes，结果如表2所示。我们的方法可以提速990x倍，而在label scorer上的P@10提升13%。该结果和我们见到的一样重要：我们使用的label scorer是一个线性模型，其中label partitioner在某种程度上是“非线性”的：它可以在输入空间的不同分区上更改label sets——这可以纠正原始scorer的错误（在某种程度上，这有点像个re-ranker）。注意基于最优化的label partitioner比counting heuristic效果要好。

表2

我们的label partitioner被用于视频推荐系统中，用来尝试提升一个比较强的baseline ML系统。在我们的上述实验中使用的是precision，但precision只是一个online metrics，而在观看期视频的ctr作为衡量更好。当在实际系统中评估label partitioner时，它可以在ctr和观看时长（接近2%）上获得极大的提升。注意，我们不会将它与原始的label scorer做比较，那种情况下使用它是不可行的。

5.结论

我们提出了一种“wrapper”方法来加速label scoring rankers。它使用一种新的优化法：通过学习一个input partitioning和label assignment，来胜过其它baseline。该结果与原始的label scorer效果相似（或者效果更好），同时运行更快。这使得该技术被用于现实的视频推荐系统中。最终，我们我们觉得提出的label assignment是解决该问题的好方法，input partitioners间的巨大性能差距意味着，将来还有重大问题需要解决。

参考

Label Partitioning For Sublinear Ranking

机器学习中的许多模型中，对类别型变量，常作的处理是，将它们编码成one-hot。但是对于树模型来说，将类别型变量编码成one-hot，这样作是否有意义呢？像一些机器学习工具包（比如：spark gbm实现），你可以指定为类别型变量，内部自己去做one-hot实现。而像xgboost，则将输入全认为是数值型特征去处理。

一、要不要one-hot？

这在机器学习界也有争论。理论上，树模型如果够深，也能将关键的类别型特型切出来。

关于这个，xgboost的作者tqchen在某个issues有提到过：

I do not know what you mean by vector. xgboost treat every input feature as numerical, with support for missing values and sparsity. The decision is at the user

So if you want ordered variables, you can transform the variables into numerical levels(say age). Or if you prefer treat it as categorical variable, do one hot encoding.

在另一个issues上也提到过（tqchen commented on 8 May 2015）：

One-hot encoding could be helpful when the number of categories are small( in level of 10 to 100). In such case one-hot encoding can discover interesting interactions like (gender=male) AND (job = teacher).

While ordering them makes it harder to be discovered(need two split on job). However, indeed there is not a unified way handling categorical features in trees, and usually what tree was really good at was ordered continuous features anyway..

总结起来的结论，大至两条：

• 1.对于类别有序的类别型变量，比如age等，当成数值型变量处理可以的。对于非类别有序的类别型变量，推荐one-hot。但是one-hot会增加内存开销以及训练时间开销。
• 2.类别型变量在范围较小时（tqchen给出的是[10,100]范围内）推荐使用

二、one-hot的一致性问题

当你进行one-hot编码时，有些机器学习工具包内置的one-hot编码工具会帮你做这些事，但是真实的情况是，我们有数据集有如下分类：训练集、测试集、预测集（真实数据）等。

这些数据集并不会统一，比如：

训练集上A特征有: a,b,c,d，测试集上A特征有:a,b,d，预测集上可能有b,c,e,f

因此，你需要做的是，将它们统一使用one-hot编码，而非分开做不同的one-hot编码.

参考

• 1.https://github.com/szilard/benchm-ml/issues/1
• 2.https://github.com/dmlc/xgboost/issues/95

在广告系统中，一个重要的指标是CTR。ctr=点击(Click)/曝光(Impression)。

• 如果一个广告只有5次曝光，没有点击，是否表示它的ctr为0?
• 如果一个广告曝光了4次，却有3次点击，它的ctr是否就为75%?

直觉上肯定是不对的。

一个广告的每次展示，相当于概率试验里的投硬币。客户点击/不点击广告，是一个泊努利试验(Bernoulli Trial)。多个客户点击/不点击广告，可以看成是进行一串Bernoulli试验，即二项试验(Binomial Experiment)，服从二项分布。

假设我们尝试了n次试验（有n个客户），每个客户点击该广告的概率为p（平均ctr）。该试验服从二项分布：B(n,p)。在n次试验中，观察到有k次点击的概率为：

例如，如果有100个visitors，该广告的点击率为10%，点击次数的概率分布(PMF)为：

即上面公式中：n=100, 横轴为k，纵轴为p。

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import binom

n, p = 4, 0.1
x = np.arange(1,100)

fig, ax = plt.subplots(1, 1)
ax.plot(x, binom.pmf(x, n, p), 'bo', ms=8, label='binom pmf')
plt.show()

我们可得到类似这样的曲线：

当CTR接近10%时，有相当高的机会看到8次-12次左右的点击。如果观察的次数越少，噪声也会越多。当只有4次观测（observation）时，有65%的机会看到没有点击，30%的机会看到一次点击，5%的机会看到2次点击。

from scipy.misc import comb

n = 4
k = 0
r = 0.1
p0 = comb(n,k)* (r)**k * (1-r)**(n-k)
### p1接近0.65

k = 1
p1 = comb(n,k)* (r)**k * (1-r)**(n-k)
### p2接近0.30

k=2
p2 = comb(n,k)* (r)**k * (1-r)**(n-k)
### p3接近0.05

2.CTR的Beta分布

假如，我们只有少量观测，是否可以去估计CTR呢？是否可以设计一个算法去模仿相应的模型数据？

为了在一个广告上模仿点击，我们首先使用一些分布上的CTR的值，接着使用它们作为在二项分布上的点击概率。这意味着我们需要两个随机变量。首先，是一个在[0,1]范围内的CTR的连续分布。第二个，是使用该CTR作为参数的二项分布。

什么样的分布是合理的？我们首先想到的是：正态分布。但它有负数，负的CTR显然没意义。另外，它是对称的，没有理由将模型限制在对称分布上。最好的分布是：Beta分布。它在[0,1]区间内是连续的，并且有各种形状。它的两个参数为：α(alpha) 和 β(beta)。

有两种方式来从数据中估计α和β的值，其中有一种方法特别有用：“均值和样本量”参数化（“Mean and Sample Size” parametrization）。

假设我们从一个很大的样本中抽取的10次曝光和2次点击来估计它的分布。假设 ν为样本量。 ν=10，μ为CTR均值。我们有2次点击和10次曝光：μ=2/10=0.2。Beta分布的参数化为：

α=μν,β=(1–μ)ν

在该例中：

α=0.2⋅10=2, β=(1–0.2)⋅10=0.8⋅10=8

beta分布的概率计算公式：

其中的f(x;a,β)就是实际概率，而x就是这里我们的点击率。

绘制出对应的Beta曲线：

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import beta

a,b=2,8
x = np.arange(0,1,0.01)

fig, ax = plt.subplots(1, 1)
ax.plot(x, beta.pdf(x, a, b), 'r-', lw=5, alpha=0.6, label='beta pdf')
plt.show()

可以得到类似的图：

从10次观测中的不确定性，通过该分布的扩展可以很容易解释。同理，我们可以尝试计算参数化，如果我们具有1000个观测以及200次点击。你可以注意到它将高度集中围绕在20%的CTR中。

将Beta分布与Binomial分布结合在一起，称为Beta-Binomial分布。

3.贝叶斯推断（Bayesian inference）

3.1

在参考文献一中，提出的方法是直接使用先验CTR：

通常，我们实际展示多个广告。计算观测时，当存在不确定性时，我们会生成一个CTR的估计值。一些广告可能具有成千上万的曝光和点击，而另一些可能只有很少的点击。这时候，可以引入贝叶斯推断（Bayesian inference）。我们使用一个先验的CTR，当新观测被记录时，我们不断更新它。先验CTR有很多方式确定。如果时间足够，我们可以使用基于Mean和sample size的参数化方法。如果我们没有足够信息，我们可以使用事先分配的先验CTR(non-informative prior)，比如β(0.5,0.5):

一旦我们定义好先验CTR后，我们需要指定似然函数（likelihood function）。在我们的案例中，在结定参数集（CTR）下的观测的似然（likelihood）由二项分布给出。二项分布似然加上Beta先验，允许我们使用联合先验概率来获取一个后验分布。在我们的先验β(a,b)下，经过N次曝光观测到x次点击，得到的后验是这样一个Beta分布：β(a+x,b+N–x)。

还是使用之前的观测：4次曝光，1次点击，我们得到这样的后验：

贝叶斯模型可以后验的总结、或者通过随机抽样(均值、中位数、标准差等）进行分析。例如，在上面的贝叶斯推断步骤后，我们希望看到：一个广告在10000次曝光下，具有0.35的CPC（Cost-per－Click）

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import beta

cpc = 0.35

priorA = 0.5
priorB = 0.5

clicks = 1
impressions = 4

 #rvs：生成随机数
plt.hist(beta.rvs(priorA + clicks, priorB + impressions - clicks, size=10000) * 10000 * cpc, 20, facecolor='green')

plt.xlabel('Cost')
plt.ylabel('Frequency')
plt.grid(True)

plt.show()

3.2 数据连续性

在参考文献二中提到，在许多情况下，我们更关心CTR的趋势，而非某个绝对值快照。对于罕见的(page/ad) pair，任何时间点，CTR的估计都是很大噪声的。根据某种数据连续性，我们可以将impression/click看做是重复测量的离散集合，并在这些测量上采用了一种指数平滑（exponential smoothing），最后我们得到一个平滑的CTR。

对于一个(page/ad) pair，我们具有连续M天的测量：impressions(I1,I2,I3,…Im)和clicks(C1,C2,…,Cm)，然后我们希望估计在第M天的CTR。

$ \hat{I} $和 $ \hat{C} $各自表示平滑后的impressions和clicks。平滑后的CTR就等于$ \frac{\hat{C}}{\hat{I}} $。

其中γ为平滑因子，它0<γ<1，（γ控制着平滑中的历史影响：当γ接近0，表示与历史值接近；当γ接近1，表示与历史值关系越少）。换句话说，随着时间的流逝，平滑过的$ \hat{C_j}=C_j $相当于变成了对过去观察值的指数式降权平均。你可以直接在CTR上应用指数平滑，而非各自对impressions/clicks做平滑。

(未完待续)

参考

http://www.marketingdistillery.com/2014/09/24/bayesian-modeling-of-click-through-rate-for-small-data/

Click-Through Rate Estimation for Rare Events in Online Advertising

如何通俗理解beta分布？

部分是翻译，部分是个人的理解.

目录

• 0.统计推断
• 1.预处理
• 2.特征提取
• 3.特征选择
• 4.模型评估
• 5.学习曲线
• 6.参数学习
• 7.imbalanced类
• 8.ROC
• 9.降维
• 10.svd

线性模型

• 1.线性模型
• 2.随机梯度下降
• 3.logistic回归

非线性模型

• 1.svm

树模型

• 1.cart
• 2.随机森林
• 3.bagging
• 4.adaboost
• 5.gbm
• 6.gbm参数调优

1.介绍

Fackbook提出的gbdt+LR来预测广告点击，本文简单重温下相应的paper。

在付费搜索广告领域(sponsored search advertising)，用户query被用于检索候选广告（candidate ads），这些广告可以显式或隐式与query相匹配。在Facebook上，广告不与query相关联，但可以通过人口统计学(demographic)和兴趣（interest）来定向(targeting)。因而，当一个用户访问Facebook时，适合展示的广告容量（the volume of ads），比付费搜索中的要大。

为了应付每个请求上非常大量的候选广告，当用户访问Facobook时触发广告请求，我们会首先构建一连串的分类器，它们会增加计算开销。在本文中主要放在点击预测模型上，它会对最终的候选广告产生预测。

2.实验Setup

为了达到严谨受控的实验，我们会取2013年第4季度某一个周的数据作为离线训练数据。为了在不同条件下维护相同的训练／测试数据，我们准备了离线训练数据，它与线上观测到的数据相似。我们将这些保存下来的离线数据划分成：训练数据和测试数据，并使用它们来模拟在线训练和预测的streaming数据。

评估的metrics: 由于我们最关心的是机器学习模型的影响因子，我们使用prediction的accuracy作为metrics，而非利润和回报。在本文中，我们使用归一化熵（NE: Normalized Entropy）以及calibration作为主要的评测指标。

Nonmalized Entropy，或者更准确地被称为NCE：归一化的Cross-Entropy，等价于：【每次曝光（impression）的平均log loss】除以【如果一个模型为每个曝光预测了相应后台CTR(background CTR)，每个曝光的平均log loss】。换句话说，它是预测log loss，通过s通过background CTR进行归一化。background CTR是训练数据集的平均期望CTR(average empirical CTR)。它可能更多描述是指关于归一化log loss（Normalized Logarithmic Loss）。值越低，通过该模型预测的效果越好。使用该归一化的原因是，background CTR越接近0或1,也容易达到一个更好的log loss。除以background CTR的熵，使得NE对于background CTR不敏感。假设一个给定的数据集，具有N个样本，对应的labels为: $ yi \in {-1,+1} $，点击概率\(p_i\)，其中i=1,2,…,N。平均期望CTR为p：

……（1)

NE是用于计算相关的信息增益(RIG: Relative Information Gain)的一个必需单元. RIG=1-NE

Calibration(校准)是一个关于【平均估计CTR】和【期望CTR】的ratio。该比值相当于：【期望点击数】与【实际观察点击数】。Calibration是一个非常重要的指标，因为关于CTR的accurate、well-calibrated的预测，对于在线竞价和拍卖的成功很重要。Calibration与1的差异越小，模型越好。我们只会报告：在实验中的calibration，它是non-trivial的。

注意，对于评估ranking的质量，AUC也是一个相当好的指标，无需考虑Calibration。真实环境下，我们希望预测够准确，而非仅仅获取最优的rank顺序，以避免欠拟合（under-delivery）或过拟合（overdelivery）。NE可以measure预测的好坏，并隐式地影响calibration。例如，如果一个模型过度预测了2倍，我们可以使用一个全局的乘子0.5来修正calibration，对应的NE也会提升，尽管AUC仍相同。详见paper[12]

3.预测模型结构

本部分我们提出了一种混合模型结构：将GBDT与一个概率稀疏的线性分类器相串联，如图1所示。在3.1中，决策树对于输入特征的转换十分强大，可以极大增加概率线性分类器的accuracy。在3.2中，会展示训练数据的新鲜度是如何影响更准确的预测。这激发了我们使用一个在线学习方法来训练线性分类器。在3.3中，我们比较一些在线学习变种。

图1: 混合模型结构。输入特征通过boosted决策树的方式进行转换，每棵树的输出作为一个类别型输入特征，输入到一个稀疏的线性分类器上。Boosted决策树提供了非常强的特征转换.

我们评估的在线学习模式，是基于SGD算法的，应用于稀疏线性分类器。在特征转换后，给定一个ad的曝光，具有一个vector形式：$ x=(e_{i1},…,e_{in}) $，其中ei表示第i个unit vector，$i_1,…,i_n$是n种类别输入特征的值。在训练阶段，我们假设，给定一个二元标签 $y \in {-1,+1}$，用于表示点击or未点击。

给定一个加上label的广告曝光：(x,y)，我们将激活权重的线性组合表示成：

……(2)

其中w是线性点击分值的weight vector。

对于概率回归(BOPR)，目前最state-of-art的Bayesian在线学习scheme在[7]中有描述，似然和先验如下：

3.1 决策树特征转换

为了提升accuracy，有两种简单的方法，来对线性分类器的输入特征进行转换。对于连续型特征，用于学习非线性变换的一个简单的trick是，将特征二值化（bin），将将二值索引(bin index)看成是一个类别型特征。线性分类器可以有效地为该特征学到一个分段(piece-wise)常量的非线性映射。学到有用的二值边界很重要，有许多方法。

第二个简单但有效地转换包含在构建tuple型输入特征中。对于类别型特征，在笛卡尔积中采用的暴力搜索方法，比如，创建一个新的类别型特征，将它看成是原始特征的所有可能值。并不是所有的组合都有用，那些不管用的可以对其进行剪枝。如果输入特征是连续的，可以做联合二值化（joint binning），使用k-d tree。

我们发现boosted决策树很强大，非常便于实现非线性和上面这种tuple型转换。我们将每棵树看成是一个类别型特征，它把值看成是将叶子的索引。对于这种类型的特征，我们使用1-of-K的编码。例如，考虑图1中的boosted tree模型，有2棵子树，其中第1棵子树具有3个叶子，第2棵具有2个叶子。如果一个实例在第1棵子树的叶节点2上结束，在第2棵子树的叶节点1上结束，那么整体的输入到线性分类器上的二元向量为：[0,1,0,1,0]，其中前3个实体对应于第1棵子树的叶子，后2个对应于第2棵子树。我们使用的boosted决策树为：Gradient Boosting Machine(GBM)[5]，使用的是经典的L2-TreeBoost算法。在每个学习迭代中，会对前面树的残差进行建模创建一棵新树。我们可以将基于变换的boosted决策树理解成一个监督型特征编码（supervised feature encoding），它将一个实数值向量(real-valued vector)转换成一个压缩的二值向量(binary-valued vector)。从根节点到某一叶子节点的路径，表示在特定特征上的一个规则。在该二值向量上，再fit一个线性分类器，可以本质上学到这些规则的权重。Boosted决策树以batch方式进行训练。

我们开展实验来展示将tree features作为线性模型的效果。在该实验中，我们比较了两个logistic regression模型，一个使用tree feature转换，另一个使用普通的(未转换)特征。我们也加了一个单独的boosted决策树模型作为对比。所表1所示：

相对于没有树特征转换的模型，树特征变换可以帮助减小3.4%的NE。这是非常大的相对提升。作为参考，一个典型的特征工程实验，可减小20-30%左右的相对NE。LR和树模型以独立方式运行下的比较也很有意思（LR的预测accuracy更好一点点），但它们组合起来会有大幅提升。预测acuracy的增益是很大；作为参考，特征工程的好坏可以影响NE更多。

3.2 数据新鲜度

点击预测系统经常被部署在动态环境上，数据分布随时间变化。我们研究了训练数据的新鲜度对于预测效果的提升情况。我们在特定的某一天训练了一个模型，并在连续的数天对该模型进行测试。我们同时运行boosted决策树模型，以及一个使用树转换的LR模型。

在该实验中，我们训练了一天的数据，在后面的6天进行评估，计算每天的NE。结果如图2所示。

图2: 预测accuracy和时间关系

随着训练集与测试集间的时延的增长，预测accuracy明显下降。一周内两种模型的NE都下降大概1%左右。

该发现表明，需要以天为基础重新训练模型。一种选择是：使用一个周期天级任务，以batch方式重新训练模型。重新训练boosted决策树的时间各有不同，具体依赖于训练样本数，树的数目，每棵树的叶子，cpu，内存等。对于单核cpu，1亿左右的样本，有可能会超过24小时来构建一个上百棵树的boosting模型。实际情况中，训练过程可以在多核机器上，内存量足够存储整个训练集，通过足够的并发，使用几个小时来完成。下一部分，我们可以使用另一种方法。boosted决策树，可以每天或者每两天进行训练，但是线性分类器可以通过在线学习方式，接近实时进行训练。

3.3 在线线性分类器

为了最大化数据的新鲜度，一个选择是，当广告曝光数据到达标注后，直接在线训练线性分类器。在下面的第4部分，我们会描述一些基础，用来生成实时训练数据。在这部分，我们评估了许多方式，为基于SGD的LR在线学习设置不同的learning-rate。我们接着比较BOPR模型的在线学习最好变种。

在语术(6)中，我们可以有以下选择：

1.Per-coordinate学习率。该learning rate对于特征i在第t次迭代可设置成：

α, β 是两个可调的参数。

2.Per-weight均方根学习率。

3.Per-weight学习率：

4.全局学习率：

5.常数学习率：

前三种scheme可以为每个feature独立设置learning rate。后两种为所有feature使用相同的learning rate。所有可调的参数可以通过grid search进行优化。

对于连续学习（continuous learning），我们可以将learning rate设置为一个较低的边界0.00001. 我们使用上述的learning rate scheme来在相同的数据上训练和测试LR模型。相应的试验结果如图3所示。

图3: 不同learning rate schema的实验. X表示不同的learning rate。左侧为calibration，y轴右侧为NE.

从上面的结果可知，使用per-coordinate learning rate的SGD可以达到最好的预测accuracy，它可以降低5%的NE，比使用per weight learning rate要低（这种最差）。该结果的结论在[8]。per-weight square root学习率和常数学习率，几乎相同。另两种则比前面的都要差很多。global学习率失败的原因主要是因为训练实例的数目在每个特征上是不平衡的(imbalance)。由于每个训练实例可能包含不同的feature，一些流行的feature比起其它feature会具有更多的训练实例。在global学习率scheme下，具有更少训练实例的features的learning rate，会降得更快，以阻止最优weight（optimum weight）的收敛。尽管per-weight的learning rate的scheme也有相同的问题，它仍会失败，因为对于所有features，它会很快地减小learning rate。训练会过早终结，而模型会收敛到一个次优的点（sub-optimal point）。这解释了为什么该scheme在所有选择中具有最差的performance。

有意思的是，需要注意BOPR更新式(3)，意味着最接近LR SGD的per-coordinate learning rate版本。BOPR的有效学习率可以指定到每个coordinate上，取决于权重的后验variance，与每个单独的coordinate相关。

。。

4.Online data JOINER

前面的部分确定了训练数据中新鲜度会增加预测accuracy。同时也介绍了一个简单的模型架构，其中的线性分类器这一层是在线方式训练的。

本部分介绍一个实验系统，它生成实时训练数据，通过online learning来训练线性分类器。我们将该系统看成是”online joiner”，因为它的临界操作(critical operation)是将labels(click/no-click)和训练输入(ad impressions)以在线方式join起来。相同的基础设施可以用于流式学习（stream learning），例如Google Advertising System[1]。该online joiner会输出一个实时的训练数据流到一个称为“Scribe”的基础设施上[10]。而positive labels(clicks)是定义良好的，它没有提供给用户”no click”按钮。出于该原因，如果用户看到该广告后，在一个确定、足够长的时间周期上没有点击该广告，那么这次曝光(impression)可以认为是具有一个negative的no-click label。等待的时间窗口需要小心调节。

• 太长的时间窗口(time window)：实时训练数据会延迟，并增加额外内存分配开销来缓存要等待点击信号的impressions。
• 过短时间的时间窗口：会造成一些点击丢失，因为相应的impression可以会被冲掉，并当成no-clicked label来对待。这种负面影响称为”点击覆盖（click coverage）”，它是一个关于所有成功的clicks与impressions相join的一个分数。

作为结果，online joiner系统必须在最新性（recency）和点击覆盖(click coverage)间做出一个平衡。

不具有完整的点击覆盖，意味着实时训练集是有偏的(bias)：经验CTR(empirical CTR)会比ground truth要低。这是因为：一部分被标注为未点击（no-clicked）的曝光（impressions），如果等待时间足够长，会有可能会被标注成点击数据。实际上，我们会发现，在内存可控范围内，随着等待窗口的size的变大，很容易减小bias到小数范围内。另外，这种小的bias是可衡量和可纠正的。关于window size的研究可以见[6]。

online joiner被设计成执行一个在ad impressions和ad clicks之间的分布式stream-to-stream join，使用一个请求ID(request ID)作为join的主键。每一时刻当一个用户在Facebook上执行一个动作时，都会生成一个请求ID，会触发新鲜的内容曝光给他们。图4展示了online joiner和online learning的数据和模型流。当用户访问Facebook时，会生成初始的数据流，会发起一个请求给ranker对候选广告进行排序。广告会被传给用户设备，并行的，每个广告、以及和它相关的用于ranking的features，会并行地添加到曝光流（impression stream）中。如果用户选择点击该广告， 那么该点击(click)会被添加到点击流中（click stream）。为了完成stream-to-stream join，系统会使用一个HashQueue，它包含了一个先入先出的队列（FIFO queue）作为一个缓存窗口；以及一个hashmap用于快速随机访问label曝光。一个HashQueue通常在kv-pair上具有三种类型的操作：enqueue, dequeue和lookup。例如，为了enqueue一个item，我们添加该item到一个队列的前面，并在hashmap中创建一个key，对应的值指向队列中的item。只有在完整的join窗口超期后(expired)，会触发一个有标签的曝光(labeled impression)给训练流。如果没有点击join，它会触发一个negative的标注样本。

在该实验设置中，训练器(trainer)会从训练流中进行持续学习，并周期性发布新模型给排序器(Ranker)。这对于机器学习来说，最终会形成一个紧的闭环，特征分布的变更，或者模型表现的变更都能被捕获，学到，并在后续得到修正。

一个重要的考虑是，当使用实时训练数据生成系统进行试验时，需要构建保护机制来处理在线学习系统崩溃时引发的异常。例如：由于某些数据基础设施的原因，点击流（click stream）过期了，那么online joiner将产生这样的数据：它具有非常小或近乎0的经验CTR（empirical CTR）。作为结果，该实时训练器会开始以非常低、或近乎0的点击概率来进行错误的预测。一个广告的期望值会自然的决策于估计的点击概率，不正确预测成非常低的CTR的一个结果是，系统会降低广告曝光数。异常检测机制在这里就很有用。例如，如果实时训练数据分布突然发生变更，你可以从online joiner上自动断开online trainer。

5.内存与延迟

5.1 boosting trees的数目

模型中树越多，训练时间越长。这部分会研究树的数目在accuracy上的影响。

我们区分了树的数目，从1到2000棵，在一个完整天的数据上训练模型，并在下一天预测效果。我们限制了每棵树的叶子节点不超过12个。与之前的试验类似，我们使用NE作为评测的metric。试验结果如图5所示。NE会随着boosted trees的数目增加而增加。然而，通过添加树获得的增益，所获得的回归会减少。几乎所有的NE提升，都来自于前500棵树。最后的1000棵树减少的NE比0.1%还要少。另外，我们看到，NE对于子模型2(submodel 2), 会在1000棵树后开始倒退。这种现象的可能原因是overfitting。因为子模型2的训练数据比子模型0和1的要小。

图5: boosting tree的数目的实验。不同系统对应着不同的子模型。x轴表示boosting trees的数目。Y轴表示NE.

5.2 Boosting feature importance

特征数（feature count）是另一个模型特性，它可以影响估计的accuracy和计算性能。为了更好理解特征数的影响，我们首先为每个特征应用一个特征重要性（feature importance）。

为了衡量一个特征的重要性，我们使用statistic Boosting Feature Importance，它可以捕获一个feature的累积loss衰减属性（cumulative loss reduction）。在每个树节点构建中，会选择最好的feature，并将它进行split，来达到最大化平方误差衰减（squared error reduction）。由于一个feature可以被用在多棵树中，每个feature的（Boosting Feature Importance）可以通过在所有树上对一个指定feature做总的reduction的求和。

通常，只有少量的特征对可解释性(explanatory power)有主要贡献，对可解释性，而其余的特征则只有少量贡献。我们可以看到，当绘制特征数 vs. 累积特征重要性时（如图6所示），这种现象。

图6: Boosting feature importance。x轴表示特征数。在y轴左侧表示log scale中抽取了特征重要性，而y轴右侧表示累积特征重要性。

从上面的结果看来，top 10的特征占握着总的特征重要性的一半，而最后300个特征只贡献了少于1%的feature importance。基于该发现，我们进一步试验，只保留top 10,20,50,100,200个特征，并评估是如何影响表现的。试验的结果如图7所示。从图中可知，我们可以看到，当增加更多的特征时，NE的回报很少。

图7: 对于top features，Boosting模型的结果. 我们在y轴的左边，抽取了calibration，而在右边的y轴对应于NE.

下面，我们将研究，历史特征(historical feature)和上下文特征（contextual feature）是否有用。由于数据敏感性，我们不能展示实际使用的特征细节。一些上下文特征举例：一天里的local time，week里的天等。历史特征可以是：在一个广告上的点击累计，等。

5.3 历史型特征

Boosting模型中使用的特征可以归类为两类：上下文型特征（contextual features）和历史型特征（ historical features）。上下文特征的值仅仅取决于取决于一个广告所处的上下文当前信息，比如，用户使用的设备，或者用户停留的当前页面。相反的，历史特征则取决于广告(ad)或用户(user)之前的交互，例如，该广告在上周的点击通过率（click through rate），或者该用户的平均点击通过率。

图8: 历史型特征百分比的结果。X轴表示特征数。Y轴表示历史型特征在top-k个重要特征中的占比。

在这一部分，我们研究了该系的表现是如何受这两种特征影响的。首先，我们检查了两种类型的相对重要性。我们通过将所有特征按重要性进行排序，接着计算在top-k个重要的特征中，历史特征的占比。结果如图8所示，从该结果看，我们可以看到，比起上下文型特征，历史型特征更具可解释性。通过重要性排序的top 10个特征全部都是历史型特征。在top 20个特征间，只有2个上下文特征，尽管历史型特征在数据集上占据着75%的特征。为了更好地理解在aggregate中每种类型的比较值，我们训练了两种Boosting模型：一种只使用上下文型特征，另一种只使用历史型特征，接着将两个模型与带所有特征的完整模型相比较。结果如表4所示。

[表4]

从该表中，我们可以再次验证，历史型特征比上下文型特征更重要。如果只有上下文型特征，我们在预测accuracy上计算4.5%的loss。相反地，没有上下文型特征，我们在预测accuracy上有1%的loss。

需要注意到，上下文型特征对于处理冷启动问题很重要。对于新用户和新广告，上下文型特征对于合理的点击率预测是必不可少的。

在下一步，我们会评估在连续几周中，只使用历史型特征的训练模型，或者只使用上下文特征的训练模型，来测试在数据新鲜度上的特征依赖性。结果如图9所示。

图9: 不同类型特征对数据新鲜度的结果。X轴表示评估时期，Y表示NE.

从该图看到，比起历史型特征，使用上下文型特征的模型更依赖于数据新鲜度。这与我们的直觉相符合，因为历史型特征描述了长期累积的用户行为，它比起上下文型特征更稳定。

6.大规模训练数据

Facebook的一整天的广告曝光数据是海量的。注意，我们不会展示实际数量。但一天的一定比例的数据可以有几百万的实例。一个控制训练开销的常用技术是：减少训练数据的量。在本节中，我们评估了两种方法用于下采样：均匀子抽样（uniform subsampling）和负下采样(negative down sampling)。在每个case上，我们会训练一个使用600棵树的boosted tree模型的集合，然后使用calibration和NE进行评估。

6.1 均匀子抽样

训练行的均匀子抽样(uniform subsampling)是一种减少数据量的好方法，因为它可以很容易实现，生成的模型不需要修改，就可以在抽样的训练数据上以及未抽样的测试数据上直接使用。在本部门，我们会评估抽样率会指数式增加。对于每个在基础数据集上进行抽样的rate，我们分别训练了一个boosted tree模型。subsampling rate为{0.001, 0.01, 0.1, 0.5, 1}。

图10: 数据量的实验结果。X轴表示训练实例数。y左表示calibration。y右表示NE.

数据量及结果如图10. 它与我们的直觉相一致，越多的数据会导致更好的表现。再者，数据量展示了预测accuracy的回报会越来越少。通过使用10%的数据，NE只有在表现上，相较于整个训练数据集只有1%的减少。在该sampling rate上calibration几乎没有减少。

6.2 负下采样

类别不均衡（class imbalance）问题，许多研究者都有研究，它会对学到的模型具有重大的影响。在该部分，我们探索了使用负下采样（Negative down sampling）来解决类别不均衡的问题。经验上，我们使用不同负下采样率，来测试学到模型的accuracy。相应的rate为：{0.1, 0.01, 0.001, 0.0001}。结果如图11所示。

图11: 负下采样的实验结果。X轴对应于不同的负下采样率。y左表示calibration，y右表示NE.

从结果上看，我们可知，负下采样率在训练模型的表现上具有极大的提升。当负下采样率设置在0.025时具有最好的表现。

6.3 模型Re-Calibration

负下采样可以加速训练，提升模型表现。注意，如果在一个数据集上使用负下采样来训练一个模型，它可以校正(calibrate)在下采样空间上的预测。例如，如果平均CTR在采样之前只有0.1%，我们做一个0.01的负下采样，经验CTR（empirical）大约有10%的提升。对于真实的流量实验(hive traffic experiment)，我们需要重新校准模型，会获得0.1%的回报，$ q=\frac{p}{p+(1-p)/w} $。其中p是在下采样空间中的预测，w是负下采样率。

略.

参考：

1.Practical Lessons from Predicting Clicks on Ads at Facebook 2.kaggle:gbdt+libffm