GBDT+LR论文翻译

0.摘要

在线广告允许广告客户仅针对可衡量的用户响应进行出价和付费，例如广告点击。因此，点击预测系统是大多数在线广告系统的核心。伴随每日活跃用户超过7.5亿，活跃广告客户超过100万的情况，预测Facebook广告点击是一项具有挑战性的机器学习任务。 在本文中，我们介绍了一个将决策树与逻辑回归相结合的模型，其性能比这两种方法中的任何一种都高出 3% 以上，这一改进对整体系统性能产生了重大影响。然后，我们将探讨一些基本参数如何影响我们系统的最终预测性能。最重要的是拥有正确的特征：那些捕获关于用户或广告的历史信息的特征主导其他类型的特征。一旦我们拥有了正确的特征和正确的模型(决策树加上逻辑回归)，其他因素就会起到很小的作用（尽管即使很小的改进在规模上也很重要）。选择最优的数据新鲜度处理，学习速率模式和数据采样稍微改进了模型，尽管比添加高价值的特性或选择正确的模型要少得多。

• Facebook日活跃度7.5亿，活跃广告主1百万
• 特征工程最重要：user和ad的历史信息胜过其他特征
• 轻微提升模型效果：数据新鲜度、学习率、数据采样
• 增加一个重要特征和选择正确的模型更关键

1.引言

   数字广告是一个数十亿美元规模的产业，并且逐年高速增长。大多数在线广告平台的广告投放是动态调整的，并基于观测用户反馈的兴趣进行定制的。机器学习在计算候选广告对用户的期望效用上起到主要作用，并以此提高市场效率。

   Varian和Edelman等人于2007年发表的有影响力的论文描述了由Google和Yahoo开创的按点击次数出价和付费的拍卖模型。同一年，微软也基于同样的拍卖模型(auction model)搭建了赞助搜索市场。广告拍卖的效率依赖于点击预测的精度和校准(calibration)。点击预测系统必须具有稳健性和适应性，并且能够胜任从海量数据中学习。本文的目标是分享从实验及真实应用中获得的见解。

  在赞助搜索广告中，用户查询(query)用于检索和查询匹配的候选广告。在Facebook，广告不是和查询关联，而是通过人口统计(specify demographic)和兴趣确定目标，因此用户访问Facebook时符合展示的广告量比赞助搜索更大。

  为了处理每个请求的大量候选广告，用户访问Facebook会触发广告请求，而每次广告请求需要处理大量的候选广告，所以我们构建了计算成本逐级升高的级联分类器。本文重点介绍最后一个阶段的点击预测模型，即为最终候选广告集生成预测的模型。

  我们发现，将决策树与逻辑回归相结合的混合模型本身就比这两种方法中的任何一种都好 3% 以上。 这种改进对整体系统性能有重大影响。 许多基本参数会影响我们系统的最终预测性能。 正如预期的那样，最重要的是拥有正确的特征：那些捕获有关用户或广告的历史信息的特征支配其他类型的特征。 一旦我们有了正确的特征和正确的模型（决策树加上逻辑回归），其他因素就会发挥很小的作用（尽管即使是小的改进在规模上也很重要）。 为数据新鲜度、学习率模式和数据采样选择最佳处理方式会稍微改进模型，尽管比添加高价值特征或选择正确的模型要少得多。

  我们首先在第 2 节中概述我们的实验设置。在第 3 节中，我们评估不同的概率线性分类器和不同的在线学习算法。 在线性分类的背景下，我们继续评估特征转换和数据新鲜度的影响。 受实际经验教训的启发，特别是围绕数据新鲜度和在线学习，我们提出了一个模型架构，该架构结合了在线学习层，同时生成了相当紧凑的模型。 第 4 节描述了在线学习层所需的关键组件，在线加入者，可以生成实时训练数据的实时流的实验性基础设施。

  最后，我们提出了用准确性换取内存和计算时间以及处理大量训练数据的方法。 在第 5 节中，我们描述了为大规模应用程序保留内存和延迟的实用方法，在第 6 节中，我们深入研究了训练数据量和准确性之间的权衡。

2.实验设置

2.1 构建training data和testing data

  为了实现严格可控的实验，我们选择2013年第四季度任意一周的数据作为离线训练数据。为了保持不同条件下训练数据和测试数据的一致性，准备的离线训练数据要和在线观测的数据相似。我们将存储的离线数据分割成训练数据和测试数据，并使用它们模拟用于在线训练和预测的流数据。

2.2 评估指标(Evaluation metrics)

  由于我们最关注最重要的因素对机器学习模型的影响，因此我们使用预测的准确性，而不是直接与利润和收入相关的指标。在这项工作中，我们使用归一化熵（NE）和校准作为我们的主要评估指标。

2.2.1 Normalized Entropy(NE)

  Normalized Entropy归一化熵的定义为每次展现时预测得到的log loss的平均值，除以对整个数据集的平均log loss值。之所以需要除以整个数据集的平均log loss值，是因为backgroud CTR(背景点击率是训练数据集的平均经验点击率)越接近于0或1，则越容易预测取得较好的log loss值，而做了normalization后，NE便会对backgroud CTR不敏感了。

  NE在计算相关的信息增益时是至关重要的。上面是逻辑回归的损失函数，也就是交叉熵。下面是个常数，所以这个Normalized Entropy值越低，则说明预测的效果越好。下面列出表达式：

给定一个N个样本的数据集，标签 y i ∈ { − 1 , + 1 } y_i \\in \\{-1, +1\\} yi​∈{−1,+1}, 预估点击概率为 p i p_i pi​, 其中$ i = 1,2,…N$。平均经验CTR为:

N E = − 1 N ∑ i = 1 n ( 1 + y i 2 l o g ( p i ) + 1 − y i 2 l o g ( 1 − p i ) ) − ( p ∗ l o g ( p ) + ( 1 − p ) ∗ l o g ( 1 − p ) ) ( 1 ) NE = \\frac{-\\frac{1}{N}\\sum^n_{i=1}\\big(\\frac{1+y_i}{2}log(p_i)+\\frac{1-y_i}{2}log(1-p_i)\\big)}{-\\big(p*log(p)+(1-p)*log(1-p)\\big)} \\qquad\\qquad(1) NE=−(p∗log(p)+(1−p)∗log(1−p))−N1​∑i=1n​(21+yi​​log(pi​)+21−yi​​log(1−pi​))​(1)

NE本质上是计算相对信息增益(RIG)的一个组成部分，$RIG=1-NE$  

2.2.2 Calibration校正

  Calibration定义为平均预估CTR(the average estimated CTR)和经验CTR(empirical CTR)的比率，即期望的点击数和实际观测的点击数的比率。Calibration 是一个很重要的指标，因为CTR的精确性和校准对在线出价和拍卖的成功至关重要。 该值越接近于1，模型效果越好。

注意，ROC下面积(AUC)也是衡量排序质量(不考虑校准)的一个很好的指标。在现实的环境中，我们希望该预测是准确的，而不是仅仅获得最佳排名，以避免潜在的广告投放不足或广告投放过多。 NE可以衡量预测的良好性，并直接反映校准。例如，如果一个模型高估了2倍，并且我们应用了一个全局乘数0.5来修改校准，那么即使AUC保持不变，相应的NE也将得到改善。

上面那句话的意思是NE衡量预测的良好性反应校准，AUC衡量排名质量而不考虑校准。

因为我们需要利用CTR计算精准的出价、ROI等重要的后续预估值，因此CTR模型的预估值需要是一个具有物理意义的精准的CTR，而不是仅仅输出广告排序的高低关系。所以文中不仅把CTR calibration作为重要的评价指标，更是在最后介绍了模型校正的相关方法。

3.预测模型结构

本节评估不同的概率线性分类器和不同的在线学习算法。

本节提出一种混合模型结构：提升决策树和概率稀疏线性分类器的串联。如下图所示。

3.1节说明了决策树是非常强大的输入特征转换器，能够显著提升概率线性模型的精确度。

3.2节说明了更新鲜的训练数据能够使预测更精确，从而激发了一个想法：使用在线学习方法训练学习器。

3.3节比较了两种线性分类器的几个变体。

  学习算法是用的是Stochastic Gradient Descent(SGD)随机梯度下降，或者Bayesian online learning scheme for probit regression(BOPR)贝叶斯概率回归在线学习方案都可以。本文评估的在线学习方案基于应用于稀疏线性分类器的SGD算法，原因是资源消耗要小一些。在特征变换后，曝光的广告是以结构化向量的形式给出的： x = ( e i 1 , . . . , e i n ) \\bold x = (e_{i1},...,e_{in}) x=(ei1​,...,ein​)，其中 e i e_i ei​ 是第 $i$ 个单元向量，而$ i_1 ,…,i_n$是 $n$ 个分类输入特征的值。在训练阶段，假设给定二元标签 y ∈ { + 1 , − 1 } y\\in \\{+1,-1\\} y∈{+1,−1} 来表示点击或未点击。

给定带标签的曝光广告$(\mathbf{x},y)$，定义有效权重的线性组合定义为公式2：
s ( y , x , w ) = y ⋅ w T x = y ∑ j = 1 n w j , i j ( 2 ) s(y, \\bold x, \\bold w) = y \\cdot \\bold w^T\\bold x = y\\sum^n_{j=1}w_{j,i_j} \\qquad\\qquad (2) s(y,x,w)=y⋅wTx=yj=1∑n​wj,ij​​(2)
其中$w$为线性点击分的权重向量。

在SOTA的BOPR（Bayesian online learning scheme for probit regression）算法中，似然度和概率如下定义：
p ( y ∣ x , w ) = Φ ( s ( y , x , w ) β ) p ( w ) = ∏ k = 1 N N ( w k ; μ k , σ k 2 ) \\begin{aligned} & p(y|\\bold x, \\bold w) = \\Phi\\Big(\\frac{s(y, \\bold x, \\bold w)}{\\beta}\\Big) \\\\ & p(\\bold w) = \\prod^N_{k=1}N(w_k;\\mu_k ,\\sigma^2_k) \\end{aligned} ​p(y∣x,w)=Φ(βs(y,x,w)​)p(w)=k=1∏N​N(wk​;μk​,σk2​)​
其中$ \\Phi(t)$ 为标准正态分布的累积密度函数,$N(t)$ 为标准正态分布的密度函数。通过期望传播和矩匹配来实现在线训练。结果模型由权重向量$\mathbf{w}$的近似后验分布的均值和方差组成。 BOPR算法是计算 $p(w|y,x)$ 并将其投影到 $p(w)$ 的最接近的分解高斯逼近。

因此，更新算法可以单独表示为所有非零分量$x$的均值和方差的更新方程：
μ i j ← μ i j + y i ⋅ σ i j 2 ∑ ⋅ v ( s ( y , x , μ ) ∑ ) ( 3 ) σ i j 2 ← σ i j 2 ⋅ [ 1 − σ i j 2 ∑ 2 ⋅ w ( s ( y , x , μ ) ∑ ) ] ( 4 ) ( ∑ ) 2 = β 2 + ∑ j = 1 n σ i j 2 ( 5 ) \\begin{aligned} & \\mu_{i_j} \\leftarrow \\mu_{i_j} + y_i\\cdot \\frac{\\sigma^2_{i_j}}{\\sum}\\cdot v\\Big(\\frac{s(y, \\bold x, \\bold \\mu)}{\\sum}\\Big) \\qquad\\qquad (3)\\\\[2ex] & \\sigma^2_{i_j} \\leftarrow \\sigma^2_{i_j} \\cdot \\Big[1-\\frac{\\sigma^2_{i_j}}{\\sum^2}\\cdot w \\big(\\frac{s(y, \\bold x, \\bold \\mu)}{\\sum}\\big)\\Big]\\qquad\\qquad(4)\\\\[2ex] & (\\sum)^2 = \\beta^2 + \\sum^n_{j=1}\\sigma^2_{i_j}\\qquad\\qquad(5) \\end{aligned} ​μij​​←μij​​+yi​⋅∑σij​2​​⋅v(∑s(y,x,μ)​)(3)σij​2​←σij​2​⋅[1−∑2σij​2​​⋅w(∑s(y,x,μ)​)](4)(∑)2=β2+j=1∑n​σij​2​(5)​
这里，校正函数 $v$ 和 $w$ 由 $v(t)=N(t)/\Phi (t)$ 给出，和 $w(t):=v(t)\cdot [(v(t)+t]$。这个推理可以视为在置信向量 $\mu$ 和 $\sigma$ 的SGD方案。

本文比较了BOPR与似然函数的SGD:
p ( y ∣ x , w ) = s i g m o i d ( s ( y , x , w ) ) \\begin{aligned} & p(y|\\bold x, \\bold w) = sigmoid(s(y, \\bold x, \\bold w)) \\end{aligned} ​p(y∣x,w)=sigmoid(s(y,x,w))​
其中$sigmoid(t)=exp(t)/(1+exp(t))$。 产生的算法通常称之为逻辑回归(LR)。 计算对数似然的导数，并在每个坐标上沿着这个梯度的方向移动步长：
w i j ← w i j + y ⋅ η i j ⋅ g ( s ( y , x , w ) ) ( 6 ) w_{i_j} \\leftarrow w_{i_j} + y\\cdot \\eta_{i_j} \\cdot g(s(y, \\bold x, \\bold w)) \\qquad\\qquad (6) wij​​←wij​​+y⋅ηij​​⋅g(s(y,x,w))(6)
其中g为所有非零分量的对数似然梯度，由$g(s)=[y(y+1)/2y\cdot sigmoid(s)]$ 给出。

SGD和BOPR都可以针对单个样本进行训练，所以他们可以做成流式的学习器(stream learner)。

3.1 决策树特征转换

   为了提高线性分类器的准确性， 有两种简单的特征变换方法。 对于连续特征，学习非线性变换的一个简单技巧是对特征进行分箱并将分箱索引视为分类特征。线性分类器能有效地学习特征的分段常数非线性映射。学习有用的bin边界是很重要的，有许多信息最大化的方法可以做到这一点。

  第二个简单但有效的转换在于构建元组输入特征。 对于分类特征，蛮力方法包括采用笛卡尔积，即创建一个新的分类特征，将原始特征的所有可能值作为值。 并不是所有的组合都是有用的，那些没有用的可以被删掉。 如果输入特征是连续的，则可以进行联合分箱，例如使用 k-d 树。

  本文发现boosted决策树是一种强大且方便的方法，可以实现上面描述的那种非线性变换和元组变换。 将每棵树视为一种分类特征，以样本最终落入的叶子索引作为值。使用1-of-k来编码这种类型的特征，那么把该叶子节点置为1，其他叶子节点置为0，所有叶子节点组成的向量即形成了该棵树的特征向量，把GBDT所有子树的特征向量concatenate起来，即形成了后续LR输入的特征向量。举个栗子，如图1所示有两棵子树，第一颗子树有3个叶子，第二颗有2个叶子。如果一个样本最终落在第一颗子树的第二个叶子上，第二颗子树的第一个叶子上，则整个输入变为二元向量 [0, 1, 0, 1, 0]。其中前3个节点对应第一颗子树的叶子节点，后两个对应第二颗子树。 本文使用GBM（Gradient Boosting Machine梯度提升机），经典的L2-TreeBoost算法。在每次学习迭代中，都会创建一棵树来对之前树的残差进行建模。我们可以将基于boosted决策树的变换理解为一种有监督的特征编码，它将实数型向量转换为紧凑的二元向量。从根节点到叶子节点的遍历，表示某些特征的规则。在二元向量上拟合线性分类器，本质上就是学习规则集的权重。boosted决策树以批处理的方式进行训练。

  我们进行了实验，以显示将树特征作为输入到线性模型中的效果。在这个实验中，我们比较了两种逻辑回归模型，一种是树状特征变换模型，另一种是普通(非变换)特征模型。我们还使用了一个改进的决策树模型，仅用于比较。

  与不进行树变换的模型相比，树特征变换使模型的归一化熵降低了3.4%以上。这是一个非常重要的相对改进。作为参考，一个典型的特征工程实验将削去相对NE的几十个百分点。有趣的是，孤立使用的LR和Tree模型具有相当的预测精度(LR 是更好的)， 但它们的结合带来了准确性的飞跃。预测精度有显著提高；可供参考的是，大部分的特征工程实验都只做到了减少归一化熵的百分比。

3.2 数据新鲜度

  模型会部署在实际的互联网环境中，每天会遇到很多新的数据，而这些新数据会不断的改变训练样本的数据分布，进而影响模型的性能。 为了探究新数据对模型性能的影响，论文利用某一天的数据进行训练，并观察模型在接下来连续几天的表现，其结果如图所示。

  在这个实验中，我们用一天的数据进行训练，连续六天进行评估，并计算每一天的归一化熵。 实验结果见图2。

  随着训练集和测试集之间的延迟的增加，这两个模型的预测精度明显下降。从这两个模型可以看出，从每周训练到每天训练，NE可以减少大约1%。

  这些发现表明，每天进行再训练是值得的。 一种选择是有一个重复的日常工作来重新训练模型，可能是批量的。 重新训练提升决策树所需的时间会有所不同，具体取决于训练样本的数量、树的数量、每棵树中的叶子数量、cpu、内存等因素。构建提升模型可能需要超过 24 小时 具有来自数亿个样本的数百棵树，具有单个核心 cpu。 在一个实际案例中，训练可以在几个小时内通过足够的并发在具有大量内存的多核机器上完成，以容纳整个训练集。 在下一节中，我们考虑一个替代方案。 增强的决策树可以每天或每两天训练一次，但线性分类器可以通过使用某种在线学习方式近乎实时地训练。

3.3 在线线性分类器

  为了最大化数据新鲜度，一种选择是在线训练线性分类器， 只要用户点击了广告，生成了新的样本，就进行增量训练。 在第 4 节中，我们将描述一个可以生成实时训练数据的基础框架。 在本节中，我们评估了几种为基于 SGD 的逻辑回归在线学习设置学习率的方法。 然后，我们将 BOPR 模型的最佳变体与在线学习进行比较。

为此，Facebook针对SGD-based online learning研究了5中学习速率的设置方式，如下：

1. Per-coordinate learning rate: The learning rate for feature $i$ at iteration $t$ is set to

η t , i = α β + ∑ j = 1 t ∇ j , i 2 α , β 是两个可调参数 \\begin{aligned} &\\eta_{t,i} = \\frac{\\alpha}{\\beta + \\sqrt{\\sum^t_{j=1}\\nabla^2_{j,i}}}\\\\[2ex] & \\alpha,\\beta是两个可调参数 \\end{aligned} ​ηt,i​=β+∑j=1t​∇j,i2​ ​α​α,β是两个可调参数​

2. Per-weight square root learning rate:

η t , i = α n j , i n j , i 是特征 i 直至迭代到 t 轮的总训练样本数 \\begin{aligned} &\\eta_{t,i} = \\frac{\\alpha}{\\sqrt{n_{j,i}}}\\\\[2ex] & n_{j,i}是特征i直至迭代到t轮的总训练样本数 \\end{aligned} ​ηt,i​=nj,i​ ​α​nj,i​是特征i直至迭代到t轮的总训练样本数​

3. Per-weight learning rate:
   η t , i = α n j , i \\begin{aligned} &\\eta_{t,i} = \\frac{\\alpha}{n_{j,i}}\\\\[2ex] \\end{aligned} ​ηt,i​=nj,i​α​​

4. Global learning rate:
   η t , i = α t \\begin{aligned} &\\eta_{t,i} = \\frac{\\alpha}{\\sqrt{t}}\\\\[2ex] \\end{aligned} ​ηt,i​=t ​α​​

5. Constant learning rate:
   η t , i = α \\begin{aligned} &\\eta_{t,i} = \\alpha \\end{aligned} ​ηt,i​=α​

  前三个方案分别设置每个特征的学习率。 最后两个对所有特征使用相同的学习速率。 所有可调参数均通过网格搜索进行优化（表 2 中详述了最优值。）

  我们将学习率下限为 0.00001 以进行持续学习。 我们使用上述学习率在相同数据上训练和测试 LR 模型。 实验结果如图 3 所示。

从上面的结果来看: Per-coordinate learning rate的SGD实现最佳预测精度, NE比使用er weight learning rate的SGD(表现最差)降低接近5% 该结果与文献[8]中的结论一致。

per-weight square root 与 constant learning rate的SGD实现相似且稍差的NE

剩下的方案比前面的三个方案差很多。

global rate的SGD失败的原因是因为训练数据集中每个特征的样本数量不一致

• 样本数量较少的特征学习率下降快,无法收敛获取全局最优权重

尽管per-weight learning rates的方案解决了特征样本数量不一致的情况, 但是依旧失败,原因是它太快降低了所有特征的学习率。

• 在模型收敛到次优点时训练过早终止。这解释了为什么该方案在所有选择中性能最差。

  有趣的是，均值的 BOPR 更新方程 (3) 与 LR 的 SGD 的per-coordinate learning rate 版本最相似。 BOPR 的有效学习率特定于每个坐标，并且取决于与每个单独坐标相关的权重的后验方差，以及给定模型预测的标签的“惊喜”[7]。

  我们进行了一个实验来比较 LR 与每坐标 SGD 和 BOPR 训练的预测性能。我们在相同的训练数据上训练 LR 和 BOPR 模型，并在第二天评估预测性能。 结果如表3所示。

  也许正如人们所期望的那样，考虑到更新方程的定性相似性，使用 Per-coordinate learning rate的SGD 训练 BOPR 和 LR 在 NE 和校准方面具有非常相似的预测性能（表中未显示）。

  LR 优于 BOPR 的一个优点是模型大小是一半，因为每个稀疏特征值只有一个权重，而不是均值和方差。较小的模型大小可能会导致更好的缓存局部性，从而更快地进行缓存查找。比较预测时的计算开销，LR 模型只需要特征向量和权重向量的一个内积，而 BOPR 模型需要方差向量和均值向量与特征向量的两个内积。

  BOPR 相对于 LR 的一个重要优势是，作为贝叶斯公式，它提供了对点击概率的完整预测分布。 这可用于计算预测分布的百分位数，可用于探索/利用学习方案 [3]。

4. online data joiner

  上一节确定了更新的训练数据可以提高预测准确性。 它还提出了一个简单的模型架构，其中线性分类器层是在线训练的。

  本节介绍一个实验系统，该系统通过在线学习生成用于训练线性分类器的实时训练数据。我们将此系统称为“在线加入者”， 这里最关键的步骤就是把labels(click/no-click)和训练输入(ad impressions(曝光))以一种在线的方式连起(join)起来。 类似的基础架构也用于流式学习，例如google的广告系统Photon。在线连接器将实时训练数据流输出到称为scribe的基础架构中。 类似的基础架构也用于流式学习，例如google的广告系统Photon。在线连接器将实时训练数据流输出到称为scribe的基础架构中。 出于这个原因，如果用户在看到广告后的固定和足够长的时间后没有点击广告，则认为展示具有否定的未点击标签。等待时间窗口的长度需要仔细调整。

4.1 label标注

首先设定一个足够长的阈值。一个广告展示给用户之后，如果用户在阈值的时间内没有点击广告就标记为 no-click，点击了的话就标记为 click。这个等待的时间窗口需要非常小心的调整。
如果太长了，会增加缓存 impression 的内存消耗，而且影响实时数据的产生；如果太短了则会导致丢失一部分的点击样本，会影响 click converage (点击覆盖)。

click converage (点击覆盖) 表示有多少个点击行为被记录了下来生成了样本。online data joiner 必须保证尽可能高的点击覆盖，也就是尽可能多的来记录下来所有的点击行为。但是如果等待太久就会增加缓存开销等影响。所以 online data joiner 必须在 click converage 和资源消耗之间做出平衡，又一个trade-off。

4.2 模型架构

  没有完整的点击覆盖率意味着实时训练集会出现偏差：经验 CTR 略低于基本事实。这是因为如果等待时间足够长，那么一小部分标记为未点击的展示会被标记为点击。然而，在实践中，我们发现很容易将这种偏差减少到百分比的小数点，等待窗口大小会根据内存调整。此外，可以测量和校正这种小的偏差。更多关于窗口大小和效率的研究可以在[6]中找到。在线连接器旨在使用请求 ID 作为连接的主要组成部分，对广告曝光和广告点击执行分布式流到流连接。每次用户在 Facebook 上执行触发刷新他们所看到的内容的操作时，都会生成一个请求 ID。在线加入者后续在线学习的示意性数据和模型流程如图 4 所示。当用户访问 Facebook 并向排名器发出候选广告请求时，会生成初始数据流。广告被传回用户的设备，同时每个广告和用于对该曝光排名的相关特征被添加到曝光流中。如果用户选择点击广告，该点击将被添加到点击流中。为了实现流到流的连接，系统使用了一个 HashQueue，该 HashQueue 由一个先进先出队列作为缓冲窗口和一个散列映射组成，用于快速随机访问标签印象。HashQueue 通常对键值对进行三种操作：入队、出队和查找。例如，为了使一个候选项入队，我们将候选项添加到队列的前面，并在哈希映射中创建一个键，其值指向队列中的候选项。只有在完全加入窗口期满后，标记的曝光才会发送到训练流。如果没有加入点击，它将作为负面标记的示例发出。

如果点击覆盖比较低，意味着很多用户的点击不但没有记录下来，而是变成了没有点击。造成数据分布发生偏差，结果就是：模型学习到的CTR值要比真实值低很多。不过实际情况中，问题比较好解决：增大等待时间窗口，只要内存消耗还可以接受就行。

  在此实验设置中，训练器从训练流中不断学习，并定期向 Ranker 发布新模型。 这最终为机器学习模型形成了一个紧密的闭环，可以在短时间内连续捕获、学习和纠正特征分布或模型性能的变化。

4.3 挑战

  系统异常是在线学习系统的一大挑战。这里的异常就是指系统异常，比如系统出现问题导致stream data是老数据。可能分类器就会学习到错的数据，针对所有的点击率都给出一个非常低甚至是0的概率。这显然不是我们想看到的。可以依靠一些保护机制来解决，比如：当发现实时的训练数据分布发生比较大变化的时候，就把onliner trainer和online joiner自动断开，防止Trainer学习到坏的数据分布。

5.内存和延迟

5.1 boosting tree个数

  模型中的树越多，进行预测所需的时间就越长。 在这一部分中，我们研究了提升树的数量对估计精度的影响。

  将树的数量从 1 到 2,000 不等，并在一整天的数据上训练模型，并在第二天测试预测性能。 我们限制每棵树不超过 12 片叶子。 与之前的实验类似，我们使用归一化熵作为评估指标。 实验结果如图 5 所示。

• 随着增加提升树的数量，归一化熵减少。
• 增加树木的收益会导致收益递减。
• 几乎所有的 NE 改进都来自前 500 棵树。最后 1,000 棵树的 NE 减少了不到 0.1%。
• 子模型 2 的归一化熵在 1,000 棵树之后开始回升(模型过拟合,由于子模型 2 的训练数据比子模型 0 和 1 的训练数据小 4 倍。)。

5.2 Boosting特征重要性

  特征计数是另一个模型特征，可以影响估计精度和计算性能之间的权衡。为了更好地理解特征计数的影响，我们首先将计算每个特征得特征重要性。为了衡量一个特征的重要性，使用 该特征进行分裂，所带来的loss减小的累积量( 因为一个特征可以在多颗树上进行使用，所以累积要在所有的树上进行)。 在每个树节点构造中，选择最佳切分特征以最大限度地减少平方误差。 因为一个特征可以在多颗树上进行使用，所以累积要在所有的树上进行。

  通常，少数特征贡献了绝大部分的解释力，而其余特征的贡献很小。如图6所示。在图 6 中绘制特征数量与其累积特征重要性的关系。

• 前 10 个特征贡献了大约一半的特征重要性，而后 300 个特征贡献了不到 1% 的特征重要性。

我们进一步试验只保留前 10、20、50、100 和 200 个特征，并评估性能如何受到影响。实验结果如图 7 所示, 从图中我们可以看出，随着我们包含更多特征，归一化熵具有相似的收益递减特性。

  下面，我们将对历史和上下文特征的有用性进行一些研究。 由于数据敏感性和公司政策，我们无法透露我们使用的实际特征的细节。 一些示例上下文特征可以是本地时间、星期几等。历史特征可以是广告的累计点击次数等。

5.3 历史特征

  Boosting 模型中使用的特征可以分为两类：上下文特征和历史特征。上下文特征的价值完全取决于与广告将在其中显示的上下文有关的当前信息，例如用户使用的设备或用户所在的当前页面。相反，历史特征取决于广告或用户之前的交互，例如上周广告的点击率，或者用户的平均点击率。

  在这一部分中，我们研究了系统的性能如何取决于这两种类型的特征。首先，我们检查这两种特征的相对重要性。通过按重要性对所有特征进行排序，然后计算历史特征在前 k 个重要特征中的百分比。结果如图 8 所示。

  从结果中，我们可以看到历史特征比上下文特征提供了更多的解释力。按重要性排序的前 10 个特征都是历史特征。 在前 20 个特征中，尽管历史特征占据了该数据集中大约 75% 的特征，但只有 2 个上下文特征。为了更好地理解每种类型特征的总体比较价值，我们训练了两个只有上下文特征和历史特征的 Boosting 模型，然后将这两个模型与具有所有特征的完整模型进行比较。结果如表4所示。

  从表中，我们可以再次验证总体历史特征比上下文特征发挥更大的作用。如果没有上下文特征，我们测得预测准确度损失了 4.5%。 相反，如果没有上下文特征，我们的预测准确性损失不到 1%。

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

  在下一步中，我们在连续几周内评估仅具有历史特征或上下文特征的训练模型，以测试特征对数据新鲜度的依赖性。 结果如图 9 所示。

  从图中我们可以看出，具有上下文特征的模型比历史特征的模型更依赖数据新鲜度。 这符合我们的直觉，因为历史特征描述的是长期积累的用户行为，这比上下文特征要稳定得多。

6.应对海量训练数据

  一天的 Facebook 广告曝光数据可能包含大量样本。请注意，我们无法透露实际数字，因为它是保密的。 但是一天的一小部分数据可能有数亿个样本。用于控制训练开销的常用技术是减少训练数据量。在本节中，我们评估了两种下采样数据的技术: 均匀二次采样(Uniform subsampling)和负样本下采样(Negative down sampling)。在每种情况下，我们都训练了一组具有 600 棵树的增强树模型
并使用校准和归一化熵来评估这些。

6.1 均匀二次抽样

  均匀采样非常的简单，易于实现。而且使用均匀采样没有改变训练数据的分布，所以模型不需要修改就可以直接应用于测试数据上。我们评估了一组大致呈指数增长的子采样率({0.001,0.01,0.1,0.5,1})。下图给出了不同采样率对模型性能的影响：

  可以看到更高的采样率使用了更多的训练数据，提升了模型的效果。从图中可以看到使用10%的数据，相比于使用100%的数据，仅仅造成了1%的性能降低。是非常小的。对于Calibration校准，均匀采样不会造成影响。

6.2 负样本下采样

  计算广告中大部分的训练样本都极度不平衡，这对模型会造成很大影响。一种解决办法就是对负样本进行下采样。实验结果如下：

可以看到采样率不同，对模型性能影响很大。采样率为0.025的时候取得最好结果。

6.3 模型重校正

  负样本下采样可以加快训练速度并提升模型性能。但是同样带来了问题：改变了训练数据分布。所以需要进行校准。 请注意，如果模型是在具有负下采样的数据集中训练的，它还会校准下采样空间中的预测。 举例来说，采样之前CTR均值为 $0.1$，使用 $0.01$ 采样之后，CTR均值近似变为 $10$。 我们需要对模型进行Calibration(校准)使得模型在实际预测的时候恢复成 $0.1$。调整公式如下：
q = p p + ( 1 − p ) / w \\begin{aligned} & q = \\frac{p}{p+(1-p)/ w} \\\\[2ex] \\end{aligned} ​q=p+(1−p)/wp​​

$w$ 是采样率， $p$ 是在采样后空间中给出的CTR预估值 ，计算得到的 $q$ 就是修正后的结果

7.结论

Facebook提出的LR + GBDT来提取非线性特征进行特征组合的方式非常经典，主要特性总结如下：

• Data Freshness很重要。模型至少一天重新训练一次是值得的，LR可以近乎实时的训练，但是数百颗树来构建boosting模型在多核机器也需要几个小时比较慢
• 使用Boosted Decision Tree转换实值输入特征很大程度上提高了线性分类器的预测准确率，这激发了将Boosted Decision Tree与稀疏的线性分类器（a sparse linear classifier）结合的混合模型架构。
• 最好的在线学习方法：LR + per-coordinate learning rate(基于SGD)，该方法最终在性能上与BOPR相当，并且比所有其他正在研究的LR SGD方案表现更好。

关于平衡计算开销和模型性能所采用的技巧：

• 提出了Boosted decision trees的数量和准确性之间的权衡。保持树的数量少以保持计算和内存的存储是有利的。
• Boosted decision trees提供了通过特征重要性进行特征选择的便捷方法。可以去掉部分重要性低的特征，而仅适度地损害预测准确性。
• 分析了组合历史特征和上下文特征的效果。对于具有历史记录的广告和用户，历史特征提供的预测性能要优于上下文功能。

最后，我们讨论了对训练数据进行下采样的方法，这些数据都可以用均匀降采样，但是对带有偏置(bias)的负样本降采样更感兴趣