Question

1. 在线广告是一个价值数十亿美金的行业，它是机器学习巨大成功的案例之一。赞助搜索广告sponsored search advertising 、上下文广告contextual advertising 、展示广告display advertising、实时竞价拍卖real-time bidding auction 都在很大程度上依赖于模型准确、快速、可靠地预估广告点击率的能力。这种问题设置problem setting 也推动该领域解决大规模问题，即使在十年前，这也是几乎不可想象的。典型的工业模型可以使用相应的大规模特征空间，每天提供数十亿次事件的预测，然后从产生的大量数据中学习。

   论文 《Ad Click Prediction: a View from the Trenches》 介绍了一系列案例研究，这些案例研究来自于最近在谷歌用于赞助搜索广告的 CTR 部署系统的实验setting 。这些改进包括基于 FTRL-Proximal 在线学习算法（具有极好的稀疏性sparsity和收敛性convergence ）的传统监督学习环境下的改进，以及per-coordinate 学习率的使用。

   因为 CTR 预估问题已经得到了很好的研究，所以作者选择关注一系列不太受关注、但是在工作系统中同样重要的主题。作者探索内存节省memory savings 、性能分析performance analysis、 预测置信度confidence in predictions 、calibration、特征管理feature management 等问题，其严谨性和传统上用于设计有效学习算法的问题相同。最后，作者还详细介绍了几个没有收益的方向，尽管这些方向在其他文献中取得了理想的效果。

   因此，论文的目的是让读者了解理论进步和实际工程之间的密切关系，并展示在复杂动态系统中应用传统机器学习方法时出现的深层挑战。同时，论文也分享可能适用于其它大规模问题领域的技巧和洞察。

6.1 系统概览

1. 当用户进行搜索 query $ q $ 时，基于广告主选择的竞价词，系统将候选广告集合与 query $ q $ 进行匹配。然后，拍卖机制决定是否向用户展示这些广告、广告展示的顺序、以及广告主在用户点击广告时支付的价格。除了广告主出价之外，拍卖的一个重要输入是：对于每个广告 $ a $ ，估计用户点击广告的概率 $ p(\text{click}\mid q,a) $ 。

   我们系统中使用的特征来自于各种来源，包括 query、广告创意文本、各种与广告相关的元数据。数据往往非常稀疏，每个样本通常只有一小部分非零特征。诸如正则化的逻辑回归之类的方法非常适合这类问题。每天需要进行数十亿次预测，并在观察到新的样本时快速更新模型。当然，这个数据生产速度意味着训练数据集是巨大的。数据是由一个基于 Photon system 的流式服务 streaming service 提供的。

   由于近年来大规模学习large-scale learning 得到了很好的研究，我们没有在本文中投入大量篇幅详述我们的系统架构。然而我们注意到，我们的训练方法和 Google Brain 团队描述的 Downpour SGD 方法相似，不同之处在于我们训练的是单层模型而不是多层神经网络。这使得我们能够处理更大的数据集和更大的模型（模型具有数十亿个参数）。因为训练好的模型被复制到很多数据中心进行serving，因此我们更关心 serving 时的稀疏化，而不是训练期间的稀疏化。

2. 我们系统的整体框架如图所示：

   • Probalistic Feature Inclusion：概率性特征纳入模块，主要用于降低特征数量来优化内存。
   • Parallelized Model Training：多模型并行训练模块，主要用于超参数选择中，提高多模型并行训练的效率。
   • Calibration：模型校准模块，主要用于校准模型的系统性预测 bias。
   • Progressive Validation Metrics：模型性能分析模块，主要用于分析模型在验证集上的性能。
   • Model Serving Replicas：模型部署模块，主要用于部署模型到线上。

   

6.2 在线学习和稀疏性

6.2.1 FTRL-Proximal

1. 对于大规模学习，广义线性模型（例如逻辑回归）的在线算法具有许多优势。尽管特征向量 $ \mathbf{\vec x} $ 可能有数十亿维，但是通常每个样本只有数百个非零值。这可以通过从磁盘或网络的流式样本 streaming examples 来对大型数据集进行有效的训练，因为每个训练样本只需要考虑一次。

   如果我们采用逻辑回归来建模，那么我们可以使用以下在线框架。

   在时刻 $ t $ ，假设样本特征为 $ \mathbf{\vec x}_t\in \mathbb R^d $ ，给定模型参数 $ \mathbf{\vec w}_t $ ，那么预估的点击率为 $ p_t = \sigma\left(\mathbf{\vec w}_t\cdot \mathbf{\vec x}_t\right) $ ，其中 $ \sigma(\cdot) $ 为 sigmoid 函数。假设我们观察到了 label $ y_t\in \{0,1\} $ ，那么 logloss 为：

   $ \mathcal l_t(\mathbf{\vec w}_t) = -y_t\log p_t - (1-y_t)\log (1-p_t) $

   显然有：

   $ \nabla_{\mathbf{\vec w}_t} \mathcal l_t = \left(\sigma\left(\mathbf{\vec w}_t\cdot \mathbf{\vec x}_t\right)-y_t\right)\mathbf{\vec x}_t = (p_t - y_t) \mathbf{\vec x}_t $

2. 在线梯度下降 online gradient descent: OGD 已经被证明对此类问题非常有效，能够以最少的计算资源产生出色的预测准确性。然而，在实践中另一个关键考虑因素是最终模型的大小。由于模型可以稀疏存储，因此 $ \mathbf{\vec w} $ 中非零权重的数量是内存占用的决定因素。

   不幸的是，OGD 在生成稀疏模型方面并不是特别有效。事实上，简单地将 L1 正则化添加到损失函数中，基本上永远不会产生完全为零的权重。更复杂的方法，如 FOBOS 和梯度截断，确实成功地引入了稀疏性。和 FOBOS 相比，Regularized Dual Averaging: RDA 算法产生了更好的准确性accuracy 和稀疏性sparsity 的tradeoff。

   然而，我们已经观察到梯度下降风格的方法可以在我们的数据集上产生比 RDA 更好的准确性。那么，我们能否同时获得 RDA 提供的稀疏性和 OGD 提供的准确性？答案是肯定的，使用 Follow The (Proximally) Regularized Leader: FTRL-Proximal 算法。在没有正则化的情况下，FTRL-Proximal 与标准的OGD相同，但因为它使用模型权重 $ \mathbf{\vec w} $ 的alternative lazy representation， L1 正则化可以更有效地实现。

3. FTRL-Proximal 算法在另一篇论文中（《Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization》）以便于理论分析的方式构建。这里我们专注于描述一个实际的实现。

   给定梯度序列 $ \mathbf{\vec g}_t\in \mathbb R^d $ ，OGD 的更新为：

   $ \mathbf{\vec w}_{t+1} = \mathbf{\vec w}_t - \eta_t\mathbf{\vec g}_t $

   其中： $ \eta_t $ 为 non-increasing 的学习率调度learning rate schedule ，例如 $ \eta_t = 1/\sqrt{t} $ 。

   定义 $ \mathbf{\vec g}_{1:t} = \sum_{s=1}^t \mathbf{\vec g}_s $ ，那么FTRL-Proximal 算法使用以下更新：

   $ \mathbf{\vec w}_{t+1} = \arg\min_{\mathbf{\vec w}} \left( \mathbf{\vec g}_{1:t} \cdot \mathbf{\vec w} + \frac 12\sum_{s=1}^t\sigma_s\left\|\mathbf{\vec w} - \mathbf{\vec w}_s\right\|_2^2 + \lambda_1\left\|\mathbf{\vec w}\right\|_1\right) $

   其中： $ \sigma_s $ 为学习率的函数，例如 $ \sum_{s=1}^t \sigma_s = 1/\eta_t $ 。

   从表面上来看，FTRL-Proximal 和 OGD 的更新方程非常不同。但是当我们取 $ \lambda_1=0 $ 时，二者会产生相同的权重向量序列。 然而，当 $ \lambda_1\gt 0 $ 的 FTRL-Proximal 更新在产生稀疏性方面做得更好（参考下面实验的结果）。

4. 乍一看，人们可能会认为 FTRL-Proximal 更新比梯度下降更难实现，或者需要存储所有历史的权重。然而，实际上只需要存储单个向量（每个 $ w_i $ 对应一个值），因为我们可以将 argmin 重写为：

   $ \left(\sum_{s=1}^t (\mathbf{\vec g}_s-\sigma_s\mathbf{\vec w}_s)\right)\cdot \mathbf{\vec w} + \frac {1}{\eta_t} \left\|\mathbf{\vec w} \right\|_2^2 + \lambda_1\left\|\mathbf{\vec w}\right\|_1 +\text{const} $

   因此，如果我们存储 $ \mathbf{\vec z}_{t-1} = \sum_{s=1}^{t-1} (\mathbf{\vec g}_s-\sigma_s\mathbf{\vec w}_s) $ ，则有：

   $ \mathbf{\vec z}_t = \mathbf{\vec z}_{t-1} + \mathbf{\vec g}_t -\left(\frac{1}{\eta_t} -\frac{1}{\eta_{t-1}} \right) \mathbf{\vec w}_t $

   则 $ \mathbf{\vec w}_{t+1} $ 的解可以 per-coordinate 来计算到：

   $ w_{t+1,i} = \begin{cases} 0,& \text{if}\quad |z_{t,i}|\lt \lambda_1\\ -\eta_t(z_{t,i}-\text{sgn}(z_{t,i})\lambda_1),&\text{else} \end{cases} $

   其中 $ i=1,2,\cdots,d $ 。

   因此，FTRL-Proximal 在内存中存储 $ \mathbf{\vec z}\in \mathbb R^d $ ，而 OGD 在内存中存储 $ \mathbf{\vec w}\in \mathbb R^d $ 。下面描述的算法采用这种方法（还添加了 per-coordinate 学习率调度，我们接下来要讨论的），并支持强度为 $ \lambda_2 $ 的 L2 正则化。

   或者我们可以直接存储 $ -\eta_t\mathbf{\vec z}_t $ 而不是 $ \mathbf{\vec z}_t $ ，然后当 $ \lambda_1=0 $ 时，我们刚好存储的就是标准的梯度下降之后的权重 $ \mathbf{\vec w}_{t+1} $ 。

   注意当 $ \eta_t=\eta $ 为常数、 $ \lambda_1=0 $ 时，很容易看出FTRL-Proximal 等于 OGD，因为我们有：

   $ \mathbf{\vec w}_{t+1} = -\eta\mathbf{\vec z}_t = -\eta\sum_{s=1}^t \mathbf{\vec g}_s\Longrightarrow \mathbf{\vec w}_{t+1} = \mathbf{\vec w}_{t} - \eta\mathbf{\vec g}_t $

   这正是梯度下降所起到的作用。

5. Per-Coordinate FTRL-Proximal 的逻辑回归算法（带 L1 正则化和 L2 正则化）：

   • 输入：

     • 超参数 $ \alpha,\beta,\lambda_1,\lambda_2 $
     • 数据集 $ \mathbb D=\left\{(\mathbf{\vec x}_t,y_t)\right\}_{t=1}^T $

   • 输出：训练好的模型权重 $ \mathbf{\vec w} $

   • 算法步骤：

     • 初始化： $ \mathbf{\vec z}_0=\mathbf{\vec 0}\in \mathbb R^d ,\mathbf{\vec n}=\mathbf{\vec 0}\in \mathbb R^d $ 。其中 $ \mathbf{\vec n} $ 存储累计梯度向量。

     • 迭代 $ t=1,\cdots,T $ ，迭代步骤为：

       • 读取特征向量 $ \mathbf{\vec x}_t $ ，令 $ \mathbb I=\{i\mid x_{t,i}\ne 0,1\le i\le d\} $ 为当前样本的非稀疏特征集合。

       • 更新非稀疏特征对应的权重：对 $ i\in \mathbb I $ 有

         $ w_{t,i} = \begin{cases} 0,& \text{if}\quad |z_{t-1,i}|\lt \lambda_1\\ -\left(\frac{\beta+\sqrt{n_i}}{\alpha}+\lambda_2\right)^{-1}(z_{t-1,i}-\text{sgn}(z_{t-1,i})\lambda_1),&\text{else} \end{cases} $

         其中 $ \eta_{i} = \left(\frac{\beta+\sqrt{n_i}}{\alpha}+\lambda_2\right)^{-1} $ 。注意： $ n_i $ 是和时刻 $ t $ 相关的。

       • 计算预估点击率 $ p_t = \sigma\left(\mathbf{\vec x}_t\cdot \mathbf{\vec w}_{t}\right) $ 。

       • 读取 labey $ y_t\in \{0,1\} $ 。

       • 更新非稀疏特征对应的梯度相关的信息：对 $ i\in \mathbb I $ 有

         $ g_{t,i} = (p_t - y_t) x_{t,i} \\ \sigma_{i}=\left(\frac{1}{\eta_{i}} - \frac{1}{\eta_{i-1}}\right) = \frac{1}{\alpha}\left(\sqrt{n_i + g_{t,i}^2}-\sqrt {n_i}\right)\\ z_i\leftarrow z_i + g_{t,i}-\sigma_i w_{t,i}\\ n_i=n_i+g_{t,i}^2 $

6. FTRL-Proximal 优化算法的实验结果如下表所示。评估指标为 AucLoss = 1- AUC。考虑到损失一般是越小越好，而 AUC 是越大越好，因此我们采用 1 - AUC 。

   OGD-Count 会维护它看到某个特征的次数。在计数超过阈值 $ k $ 之前，权重固定为零；在计数超过 $ k $ 之后，在线梯度下降照常进行。我们调整 $ k $ 值使得它与 FTRL-Proximal 相同的准确性。使用较大的 $ k $ 会导致更差的 AucLoss。

   可以看到：在模型大小和准确性 tradeoff 方面，带 L1 正则化的 FTRL-Proximal 显著优于 RDA 和 FOBOS。

   总体而言，这些结果表明 FTRL-Proximal 显著改善了稀疏性，同时具有相同或更好的预测准确性。

   

6.2.2 per-coordinate 学习率

1. OGD 的标准理论建议使用全局学习率调度 $ \eta_t = 1/\sqrt t $ ，该学习率对于所有 coordinates 都是相同的。我们在 FTRL-Proximal 中采用 per-coordinate 学习率：

   $ \eta_{t,i} = \frac{\alpha}{\beta+\sqrt{\sum_{s=1}^t g_{s,i}^2}} $

   该学习率在某种意义上几乎是最优的 near-optimal 。

   • 我们通过验证集仔细选择 $ \alpha $ 和 $ \beta $ 从而得到良好的性能。根据经验：

     • $ \alpha $ 的最佳值根据特征和数据集的不同而有很大差异。
     • $ \beta = 1 $ 通常就足够了，这只是确保早期的学习率不会太高。

   • 我们还尝试对于 $ \sum_{s=1}^t g_{s,i}^2 $ 使用 0.5 以外的幂次。

2. 如前所述，Per-Coordinate FTRL-Proximal 算法要求我们跟踪每个特征的累计梯度、以及累计平方梯度。后面会介绍另一种节省内存的公式，其中累计平方梯度在多个模型上均摊。

3. 我们通过测试两个相同的模型来评估 per-coordinate 学习率的影响：一个使用单个全局学习率，另一个使用 per-coordinate 学习率。超参数 $ \alpha $ 为每个模型单独调优。

   我们在一个有代表性的数据集上运行，并使用 AucLoss 作为我们的评估指标。结果表明：与全局学习率 baseline 相比，使用 per-coordinate 学习率将 AucLoss 降低了 11.2%。在我们的设置中，AucLoss 降低 1% 就被认为是很大的。

6.3 内存优化

1. 如前所述，我们使用 L1 正则化从而节省预测期间的内存。在这里，我们将描述在训练期间节省内存的其它技巧。

2. 特征优化：在很多具有高维数据的领域中，绝大多数特征都是极为稀疏的。事实上在我们的一些模型中，一半的 unique 特征在数十亿个样本的整个数据集中仅出现一次。

   跟踪这些稀疏特征的统计数据是昂贵的，这些特征永远不会有任何实际用途。不幸的是，我们事先不知道哪些特征将是稀疏的。预处理数据从而去除稀疏特征在 online setting 中是有问题的：

   • 额外读取然后写入数据的代价非常昂贵。
   • 并且如果删除某些特征（例如，如果特征出现的次数少于 $ k $ 次），则不再尝试使用这些特征建模，从而难以评估预处理在准确性方面的代价。

   一类方法通过 L1 正则化来实现训练中的稀疏性，不需要跟踪特征的任何统计。随着训练的进行，这允许删除信息较少的特征。然而我们发现，与在训练中跟踪更多特征、并仅为 serving 进行稀疏化的方法（如 FTRL-Proximal ）相比，这种稀疏化方式导致了不可接受的准确性损失。

   我们探索的另一类方法是概率性的特征纳入 probabilistic feature inclusion ，其中新特征在首次出现时以概率方式纳入模型中。这实现了预处理数据的效果，但是可以在 online setting 中执行。我们为该方法测试了两种实现方式：

   • Poisson Inclusion：当我们遇到模型中不存在的特征时，我们仅以概率 $ p $ 将其添加到模型中。一旦添加了一个特征，在随后的观察中，我们会像往常一样更新权重和相关统计数据。在将特征添加到模型之前，需要查看特征的次数遵循期望值为 $ 1/p $ 的几何分布。

   • Bloom Filter Inclusion：我们使用一组滚动的counting Bloom filters，从而检测训练中遇到了 $ n $ 次的特征。一旦某个特征出现超过 $ n $ 次（根据过滤器），我们将其添加到模型中，并将其用于后续观察中的训练。

     注意，该方法也是概率性的，因为 counting Bloom filters 可能会出现false positives（但是不会出现 false negatives）。也就是说，我们有时会纳入一个实际发生的次数少于 $ n $ 次的特征。

   这些方法的实验效果如下表所示。可以看到：这两种方法都运行良好，但是布隆过滤器方法为 RAM 节省和预测质量损失提供了更好的 tradeoff 。

   

3. 固定精度浮点数：通常我们用 32位或者64位浮点数来存储模型参数。实际中发现：几乎所有的参数取值都在 [-2, +2] 之间。同时，分析表明：对模型参数取如此高的精度完全没有必要。这促使我们探索使用 16 位固定精度的 q.23 编码，而不是浮点编码。在 q2.13 编码中：1个bit 表示正负、2个 bit 表示整数部分、13个 bit 表示小数部分。

   采用16位浮点数带来的精度下降会导致 OGD 过程中产生累积舍入误差。事实上在使用 32位浮点数（而不是 64 位浮点数）时，我们也能够观察到舍入误差。一个简单的随机舍入策略可以缓解该问题：

   $ \tilde w_i = 2^{-13}\lfloor 2^{13} w_i +R \rfloor $

   其中：

   • $ w_i $ 为原始的参数。
   • $ \tilde w_i $ 为引入随机舍入策略调整后的参数，它以 q2.13 格式存储。
   • $ R $ 为一个随机数，它从 0~1 均匀分布随机采样。

   最终在没有损失模型预测能力的情况下，相比于 64 位双精度浮点数，采用 q2.13 精度之后模型大小降低了 75%。

4. 多模型并行训练：有时候我们需要训练多个模型，这些模型采用相同的算法但是不同的超参数来训练，这些模型称作变种模型。最后选择最佳的超参数及对应的模型。

   一种简单的方式是：先用给定的算法训练好一个模型，然后用该模型作为变种模型的初始化点来训练变种模型。这种方式比较简单，容易实现。但是缺点是：无法处理特征裁剪、或者学习率调整等场景。

   实际上有一些数据可以在多个模型之间共享，如：训练样本。另一些数据无法在多个模型之间共享，如：每个模型的参数值。我们可以在同一张哈希表中存储每个模型的参数值，从而分摊存储 key（一个字符串或者哈希后的数值）的成本。

   任何不具有指定特征的变体都会将该特征的权重存储为零，从而浪费少量空间。此外，我们将这些特征的学习率设为零。这使得我们可以同时并行训练多个模型，所有 per-coordinate 元数据的平摊成本被降低。通过这种方式不仅节省了内存，还节省了网络带宽（因为每个样本只需要读取一次）、节省 CPU（只需要查找一个哈希表，并且从训练数据中只需要生成一次特征而不是每个模型一次）、以及节省磁盘。

5. 单值结构Single Value Structure ：有时我们希望一起评估非常多的模型变体的集合，这些变体仅通过添加或删除一小部分特征而不同。在这里，我们可以使用一种更为压缩的数据结构，这种结构既有损lossy又特别，但实际上却给出了非常有用的结果。

   这个 Single Value Structure 仅为 per-coordinate 存储一个权重值，该值由包含该特征的所有模型变体共享，而不是为每个模型变体存储单独的权重值。一个 bit-field 用于跟踪哪些模型变体包含给定的特征。注意，这在本质上 《Fast prediction of new feature utility》 的方法相似，但是也允许评估特征删除和特征添加。和多模型并行训练相比，增加模型变体的 RAM 成本增长要慢得多。

   假设使用 OGD 优化，则整个学习过程如下（设维度 $ i^* $ 由所有变种模型共享）：

   • 计算所有变种模型在该维度的参数更新值：

     $ w^{(m)}_{t+1,i^*} = w_{t,i^*} - \eta_{t,i^*} ^{(m)}\times g_{t,i^*}^{(m)},\quad m=1,2,\cdots,M $

     其中： $ M $ 为模型数量， $ w_{t,i^*} $ 为所有模型在特征 $ i^* $ 上共享的参数， $ w^{(m)}_{t,i^*} $ 表示模型 $ m $ 的具体参数。

   • 计算最新的共享参数值：

     $ w_{t+1,i^*} = \frac{\sum_{m=1}^M w^{(m)}_{t+1i^*} }{M} $

   我们对比了使用 Single Value Structure 训练的大量模型变体和使用多模型并行训练的相同变体。结果显示：不同变体的相对性能几乎相同，但是 Single Value Structure 在 RAM 占用方面中节省了一个数量级。

6. 学习率计算：如前所述，我们需要存储每个特征的累计梯度、以及累计平方梯度。虽然可以通过精确地计算梯度来得到学习率的准确值，但是可以对学习率计算进行粗略的近似。

   假设特征 $ i^* $ （比如说 “最近一年是否购买过广告主的产品”）出现时，点击事件和不点击事件是相互独立的（虽然实际上很难成立，但是不影响下面的推导过程）。设特征 $ i^* $ 出现时，有 $ P $ 次点击、 $ N $ 次未点击。则点击概率为： $ p = \frac{P}{N + P} $ 。设我们采用逻辑回归模型，则有梯度：

   $ g_{i^*} = (p-y)\times x_{i^*} $

   假设逻辑回归采用 one-hot 特征，当特征 $ i^* $ 出现时 $ x_{i^*} = 1 $ ，因此：点击时（此时 $ y=1 $ ）梯度 $ g_{i^*} = p-1 $ ，未点击时（此时 $ y=0 $ ）梯度 $ g_{i^*} = p $ 。则coordinate $ i^* $ 的累计平方梯度为：

   $ \sum_{s=1}^t g_{s,i^*}^2 = \sum_\text{click}(p_s-1)^2 + \sum_\text{noclick} p_s^2 \simeq P\times (1-p)^2 + N\times p^2\\ = P\times \left(1 - \frac{P}{N+P}\right)^2 + N\times\left(\frac{P}{N+P}\right)^2 = \frac{PN}{P+N} $

   这里我们假设每次点击的概率 $ p_t = p $ 是固定的。

   则coordinate $ i^* $ 的学习率为：

   $ \eta_{t,i^*} = \frac{\alpha}{\beta+\sqrt{\sum_{s=1}^t g_{s,i^*}^2}} = \frac{\alpha}{\beta+\sqrt{PN/(P+N)}} $

   因此可以基于每个特征上发生的点击/不点击计数来近似累计平方梯度，从而调整学习率。允许这样做的原因：学习率是模型的超参数，其取值不必非常精确。实验表明：这种方式得到的学习率，与采用累计平方梯度得到的学习率，二者表现相当。

   在多模型并行训练中，由于所有变种模型都具有相同的特征点击/不点击计数，因此存储 $ N,P $ 的成本被摊销，总的存储成本较低。

   另外，计数可以使用可变长度 bit 编码，并且绝大多数特征不需要很多 bit 。这可以进一步降低存储成本。

7. 训练数据降采样：在典型的推荐、搜索等场景中，点击率CTR 通常远低于 50%。这意味着正样本非常少，正样本在 CTR 预估任务的学习中更具有价值。因此我们可以通过负降采样来显著减少训练集大小，同时保证对模型预测能力的影响降到最低。负降采样方式为：所有正样本被保留、负样本保留 $ r $ 比例，其中 $ r\in (0,1] $ 。

   负降采样会导致模型产生预测偏差，这种偏差可以通过为每个样本赋予一个系数来解决：正样本系数为 1 、负样本系数为 $ 1/r $ 。这种系数放大了每个样本的损失，因此也同步地缩放了梯度。数学上，令 $ s_j $ 为样本 $ j $ 被降采样的概率（要么为 1 要么为 $ r $ ），而每个样本系数为 $ \beta_j $ （要么为 1 要么为 $ 1/r $ ） ，那么：

   $ \mathbb E[\mathcal l_j(\mathbf{\vec w})] = s_j\beta_j\mathcal l_j(\mathbf{\vec w}) = l_j(\mathbf{\vec w}) $

   这意味着：降采样训练数据上的期望加权损失函数等于原始数据集上的损失函数。

   实验表明：即使是非常大比例的负降采样（ $ r $ 值非常小），对最终模型准确性的影响也是微乎其微的，而且和具体的 $ r $ 值无关。

6.4 模型评估

1. 虽然可以直接利用实时流量来评估模型效果，但是这种评估的代价太大：在实时流量中上新模型可能会降低这些流量的收入，因为新模型的效果在评估之前是未知的，可能更好、但是大多数情况下是更坏。

   可以通过历史日志来评估模型效果。由于不同的评估指标衡量了模型在不同方面的能力，因此我们评估了一组指标：aucloss（即：1-auc）、logloss、平方误差。为了保持一致性，这些指标都是越小越好。

6.4.1 渐进式验证

1. 我们通常使用渐进式验证 progressive validation（有时称作在线损失），而不是交叉验证、也不是在 hold out 数据集上评估。因为学习过程中计算梯度无论如何都需要计算一个 prediction，所以我们可以低成本地将这些 prediction 以每小时汇总的方式输出，用于后续分析。我们还根据各种数据 sub-slices 计算这些指标，例如按照国家、query 主题、layout 等进行细分。

2. 假设当前待学习的样本为 $ (\mathbf{\vec x}_t,y_t) $ ， 为了学习该样本：oneline learning 模型会首先预测该样本，得到预测值 $ p_t $ ；然后基于预测值计算损失 $ l_t $ 和参数梯度 $ \mathbf{\vec g}_t $ ；最后根据参数梯度来更新参数。在这个过程中，我们可以很容易的将样本的预测值 $ p_t $ 记录下来供后续的模型评估。

   • 我们每个小时汇总一次，得到该小时内每个样本的真实值、预测值。基于这些数据得到小时级别的模型评估指标。因此可以得到随时间推进的模型能力变化趋势。

   • 这种方式中，每个样本都被用来训练，同时每个样本也被用来预测：训练完 $ (\mathbf{\vec x}_{t-1},y_{t-1}) $ 来预测 $ (\mathbf{\vec x}_t,y_t) $ 、训练完 $ (\mathbf{\vec x}_{t},y_{t}) $ 来预测 $ (\mathbf{\vec x}_{t+1},y_{t+1}) $ 、... 。这使得我们可以将 100% 的数据用于训练和验证。相比较于传统的交叉验证只有部分数据用于验证，这里的验证集更大，得到的验证结果也更具有统计意义。

     这很重要，因为某些性能的改进可能需要在大规模的验证集上评估才有意义（如：改进可能很小，比如千分之五），置信度才比较高。

3. 用绝对值来评估模型能力可能会产生误导。假如某个场景点击率是 50%，另一个场景点击率是 2% 。事实上前者的 logloss 的绝对值可能会超过后者，因为 logloss 及其它指标可能会根据问题的难度（即贝叶斯风险）而变化。

   这个问题非常重要。因为 CTR 会根据不同国家/地区、以及 query 而不同。query 在一天中的不同时段的分布不同，因此评估指标的均值会在一天之内发生变化。

   因此我们更关注相对变化：模型的评估指标相对于 baseline 的变化。根据我们的经验，随着时间的推进，相对变化会更加稳定。

4. 需要注意的是：我们必须在同一批数据上产生的同一个指标才有比较意义。如：A 模型在某个时间段上得到的模型指标，和 B 模型在另一个时间段上得到的模型指标之间不可比较。因为 A 模型和 B 模型的评估数据都不同。

6.4.2 通过可视化加深理解

1. 大规模机器学习的一个隐藏陷阱是：统计指标可能受到数据中某些属性分布的影响。如：给定一个验证集，模型 A 的准确率比模型 B 更高。很有可能该验证集中 “女性” 用户非常多，而模型 A 对于 “女性” 用户的预测比模型 B 更准。

   因此我们不仅要给出模型在整体验证集上的评估指标，还要在验证集数据的每个切片 slice 上给出评估指标。如：模型在每个国家上的评估指标、模型在每个性别上的评估指标、模型在每个主题上的评估指标 .... 。

2. 因为有数百种方法可以对数据进行有意义的切片，所以我们必须能够有效地检查数据的可视化 summary。为此，我们开发了一种称为 GridViz 的高维交互式可视化，可以全面了解模型性能。来自 GridViz 的一个视图的截图如下图所示，该图展示了baseline 模型相比，三个模型（不包括 baseline 模型）的一组根据 query 主题的切片。其中 AucLoss 和 LogLoss 的结果基于一系列 query 主题来计算。

   • 指标值由彩色单元格表示，行与模型名称相对应，列与数据的每个 unique 切片相对应。

   • 列的宽度表示切片的重要性，并且可以设置为反映诸如曝光次数、或点击次数之类的统计量。下图中，列宽反映了曝光次数。

   • 单元格的颜色反映了与 baseline 相比的指标值，这有助于快速扫描异常值和感兴趣的区域，从而直观地了解整体性能。

     • 当列足够宽时将显示所选指标的数值，否则所选指标数值不展示。
     • 可以选择多个指标，这些指标将一起显示。

   • 当用户将鼠标悬停在单元格上之时，会弹出给定单元格的详细报告。

   • 由于存在数百种可能的切片，我们设计了一个交互式界面，允许用户通过下拉菜单或切片名称正则化表达式选择不同的切片。

   • 可以对列进行排序并修改色标的动态范围从而适配手头的数据。

   总体而言，该工具使得我们能够显著提高我们对各种数据集的模型性能的理解深度，并确定需要改进的高影响区域。

   

6.5 置信度

1. 对很多application，重要的是不仅要预估广告的点击率，还要量化预估的置信度。置信度可以用于衡量和控制 explore-exploit tradeoffs。通常采用置信区间confidence intervals 来评估不确定性，但是在这里不适用：

   • 标准的方法用于评估完全收敛的 batch 学习模型，且没有正则化。

     而 FTRL 模型是在线学习，不再满足独立同分布 IID 的样本假设，因此甚至无法定义收敛性。并且模型是经过正则化的。

   • 标准的方法需要求解一个 n x n 矩阵的逆，这里 n 的规模达到数十亿甚至百亿，因此无法计算。

   • 此外，至关重要的是，任何置信度估计都需要在预测时以极低的成本进行计算。也就是说，置信度估计的耗时和预估本身的耗时差不多。

   为此，我们提出了一种称之为不确定性得分uncertainty score 的启发式方法，它在计算上易于处理，并且在衡量预估准确性的质量方面做得很好。

2. uncertainty score 的核心思想是：学习算法本身在用于控制学习率的 per-coordinate 计数器 $ n_{t,i}=\sum_{s=1}^t g_{s,i}^2 $ 中保存了不确定性的概念，其中 $ \eta_{t,i} = \frac{\alpha}{\beta+\sqrt{n_{t,i}}} $ 。 $ n_{t,i} $ 较大的特征获得了较小的学习率，正是因为我们相信当前的权重更有可能是准确的。

   假设我们对样本进行归一化，使得样本每个特征的取值都归一化到 1 以内，即： $ |x_i| \le 1 $ 。对于逻辑回归模型，损失函数的梯度为： $ g_i = (p_t - y_t)\times x_i $ 。 考虑到 $ y_t\in \{0,1\}, 0\le p_t \le 1 $ 因此有： $ |g_i| \le 1 \times 1 = 1 $ 。

   为简单起见我们令 $ \lambda_1=\lambda_2=0 $ ，因此 FTRL-Proximal 等价于 OGD。给定样本 $ \mathbf{\vec x} $ ，其预估的不确定性为：

   $ |\mathbf{\vec x}\cdot \mathbf{\vec w}_t - \mathbf{\vec x}\cdot \mathbf{\vec w}_{t+1} | \le \sum_{i:|x_i| \ne 0} \eta_{t,i} |g_{t,i}|\times x_i\le \sum_{i:|x_i| \ne 0} \eta_{t,i} \times x_i =\vec\eta_t \cdot \mathbf{\vec x} $

   因此对于样本 $ \mathbf{\vec x} $ ，定义模型预测的不确定性得分为： $ u(\mathbf{\vec x}) = \mathbf{\vec \eta}_t \cdot \mathbf{\vec x} $ 。这种方式定义的置信度指标计算非常方便。

   其物理意义是：由于学习的不充分导致预测结果的不确定性。因为一旦学习充分，则模型参数 $ \mathbf{\vec w} $ 非常稳定，在前后两次迭代之间的变化几乎为零。

3. 为验证这种置信度指标的有效性，我们执行以下实验：

   • 首先在真实数据集 $ \mathbb D $ 上训练模型 A ，但是使用稍微不同的特征。

   • 然后丢弃真实数据的标记 $ y $ ，用模型 A 的预测结果 $ p(\mathbf{\vec x}) $ 来代替 $ y $ ，从而产生了替代数据集 $ \mathbb D_p $ 。

   • 在数据集 $ \mathbb D_p $ 上用 FTRL 算法训练模型 B 。

   • 对于样本 $ \mathbf {\vec x} $ ，假设模型 A 的预测结果为 p，模型 B 的预测结果为 $ \tilde p $ 。则得分误差为：

     $ e(\mathbf{\vec x}) = |\sigma^{-1}(p) - \sigma^{-1}(\tilde p) | $

     其中 $ \sigma^{-1} $ 是 $ \sigma(z) = \frac{1}{1+\exp(-z)} $ 的反函数，它根据预测概率计算得分 $ \mathbf{\vec x} \times \mathbf{\vec w} $ 。

     $ e(\mathbf{\vec x}) $ 的物理意义为：由于标记噪声的引入，导致模型预测的波动范围。

   • 最后计算 $ u(\mathbf{\vec x}) $ ，观察该指标是否和得分误差 $ e(\mathbf{\vec x}) $ 相符。

   实验结果如下图所示。横坐标表示每一个样本的得分误差 $ e $ ，纵坐标表示每个样本的不确定性分 $ u $ ，x/y 轴归一化成 0~1 之间。曲线分别代表：相同得分误差的所有样本中，25%, 50%, 75% 百分位的不确定分连接而成的曲线。可以看到，得分误差 $ e $ 和不确定性得分 $ u $ 成正向关系：得分误差越大，不确定性得分越大。

   实验结果表明： $ u(\mathbf{\vec x}) $ 和得分误差 $ e(\mathbf{\vec x}) $ 比较匹配，而且置信度指标计算量非常小。

   

6.6 模型校正

1. 准确的、且经过良好校正 calibration 的 CTR 预估不仅对于竞价至关重要，还允许将竞价中的优化问题（如拍卖机制优化、出价优化）和机器学习问题解耦。

   很多因素可能会导致模型产生系统性偏差，如：模型的前提假设不成立、优化算法本身的缺陷、训练或预测期间无法获取某些重要特征。为解决该问题，我们提出 calibration layer 来校正预测的 CTR ，使得预测 CTR 和经验 CTR 适配。

2. 假设模型在数据集 $ \mathbb D $ 上的平均预测 CTR 为 $ p $ ，数据集 $ \mathbb D $ 的经验 CTR 为 $ q $ ，其中 $ p \simeq q $ 。预测偏差 bias 为 $ q-p $ 。

   模型校正是提供一个校正函数 $ \pi_{\mathbb D} (p) $ ，使得校正后的平均预测 CTR 尽可能接近 $ q $ 。

   一个简单方法是基于泊松回归来校正。定义： $ \pi_{\mathbb D}(p) = \gamma\times p^{\kappa} $ ，其中 $ \gamma,\kappa $ 都是待学习的参数，通过泊松回归在数据集 $ \mathbb D $ 上学习。

   一个通用的方法是利用分段线性函数来拟合 bias 曲线，其中必须满足 $ \pi(\cdot) $ 是单调递增函数。如：采用 isotonic 回归。这种方式的优点是通用性更强，无论平均预测 CTR 较高还是较低，它都能很好的校正。

3. 值得注意的是，如果没有很强的、额外的假设，系统中固有的反馈回路使得我们无法为校正的影响impact 提供理论上的保证。

4. 对于数据集，我们通常需要对不同数据区间对应的子集进行校正。因为很有可能模型对 “女性” 用户预测的平均 CTR 偏高，对“男性”用户预测的平均 CTR 偏低，但是整体预测的平均 CTR 较好。这时我们需要分别针对 “女性” 用户、“男性” 用户分别进行模型校正。

6.7 自动特征管理

1. 可扩展scalable 的机器学习的一个重要方面是管理 installation 的规模，包括构成机器学习系统的所有配置、开发人员、代码、计算资源。一个有趣的案例是机器学习特征空间的管理。

   我们可以将特征空间刻画为上下文和语义的一组信号，其中每个信号（例如“广告中的单词”、“原产国”等等）都可以转换为一组实值特征以供学习。在大多数系统中，许多开发人员可能会异步地进行信号开发。一个信号可能有许多版本，比如特征升级。工程团队可能会消费那些并不是他们直接开发的信号。信号可以在多个不同的学习平台上使用，并应用于不同的学习问题。

   为了处理 use cases 的组合增长，我们部署了元数据索引，用于管理数百个活跃模型对数千个输入信号的消费。

   • 索引会针对各种问题被手动或自动地注释，比如废弃、特定于某些平台、特定于某些领域。
   • 新模型和活跃模型消费的信号由自动告警系统审核。
   • 不同学习平台共享一个通用的接口，用于向中央索引报告信号消费。
   • 当一个信号被废弃时（例如，当有新版本可用时），我们可以快速识别信号的所有消费者并跟踪替换操作。当信号的改进版本可用时，可以提醒消费者尝试新版本。
   • 新信号可以通过自动测试进入审核，并列入白名单以供纳入。白名单既可用于确保生产系统的正确性，也可以用于使用自动特征选择的学习系统。
   • 没有任何消费者的信号自动标记，从而自动进行代码清理和相关数据的删除。

   有效的自动化信号消费管理可以确保在第一时间内正确地完成更多的学习。这减少了浪费和重复的工程工作，节省了很多工程时间。在运行学习算法之前验证配置的正确性，可以消除很多模型不可用的情况，从而节省大量潜在的资源浪费。

6.8 无效的探索

1. 这里我们简要报告几个（可能令人惊讶）没有产生显著收益的方向。

2. 积极的特征哈希 Aggressive Feature Hashing：近年来，出现了一系列工作围绕使用特征哈希来降低大规模机器学习的内存成本。我们测试了这种方法，但是发现：这种方式会带来模型预测能力的明显下降，因此无法应用。

3. dropout：基于 dropout 的正则化并不会带来任何好处，甚至会降低模型预测能力。其根本原因是：在 CTR预估任务中数据特征非常稀疏，经过 dropout 之后更为稀疏。

   在计算机视觉任务中，输入特征是非常密集的，且标签是比较干净的。此时 dropout 将高度相关的特征分离开，从而产生更健壮的分类器。

   而在 CTR 预估任务中，输入特征是非常稀疏的，且标签是带噪音的。此时 dropout 会显著降低学习的数据量，降低学习效果。

4. Feature Bagging：通过在特征空间上 $ k $ 个重叠子集来获取 $ k $ 个训练样本子集，然后基于这些样本子集训练 $ k $ 个模型。对于未知样本，最终这 $ k $ 个模型的预测均值为该样本的预测结果。这是一种管理 bias-variance tradeoff 的潜在有效方法。该方法略微降低模型预测能力，大约损失 AucLoss 的 0.1%到 0.6% 。

5. 特征向量归一化Feature Vector Normalization：由于每个样本的非稀疏特征不同，导致样本特征向量的长度不同。我们尝试将样本归一化 $ \frac{\mathbf{\vec x} }{ ||\mathbf{\vec x}||} $ ，最终效果不理想。我们猜测原因是：per-coordinate 的学习率和样本归一化相互作用，导致效果下降。