五、GBDT-LR 模型

1. 论文 Practical Lessons from Predicting Clicks on Ads at Facebook 提出了 GBDT-LR 模型，该模型利用 GBDT 作为特征抽取器来抽取特征、利用 LR 作为分类器来执行分类预测。

   实验结果表明：GBDT-LR 比单独的 GBDT 模型，或者单独的 LR 模型都要好。

   

2. 传统的搜索广告根据用户query 来检索候选广告，检索依据是：广告是否显式的或隐式的匹配用户 query 。

   而 Facebook 中的广告不是和用户 query 关联，而是和广告主指定的人群定向（如：年龄、性别、城市等统计特性，体育、财经、游戏等兴趣特性）相关联。这使得每个用户能够匹配大量的候选广告。

   如果每次用户的广告请求都对这些候选广告做预测，则时间成本太高（广告检索有时间约束，时间太长则不可接受）。因此 Facebook 构建了一组分类器：

   • 前期的分类器比较简单，处理候选广告多，计算成本低，同时预测准确率较差。
   • 后期的分类器比较复杂，处理候选广告少，计算成本高，同时预测准确率较好。
   • 每个分类器都将它们预测的低 pCTR 广告截断，从而降低下游分类器的处理数据量

   通过这种分类器级联的方式层层过滤，最终每个用户只需要对少量广告的点击率进行预测。

   本论文关注的是最后一个分类器，它为最终候选广告集合生成点击率预估。

5.1 评估指标

1. 论文提出归一化熵 Normalized Entropy:NE 来评估模型。

2. 假设样本集合有 个样本，样本集合的经验CTR 为 （它等于所有正类样本数量除以总样本数量）。

   假设第 个样本预测为正类的概率为 ，其真实标签为 。

   • 定义背景点击率 background CTR 为样本集合经验 CTR ，它的熵定义为背景熵：

     

     背景熵衡量了样本集合的类别不平衡程度，也间接的衡量了样本集合的预测难度。

     类别越不均衡预测难度越简单，因为只需要将所有样本预测为最大的类别即可取得非常高的准确率。

   • 定义模型在样本集合熵的损失函数为：

     

     每个样本的损失为交叉熵。

   • 定义归一化熵 NE 为：模型在所有样本的平均损失函数除以背景熵。

     

     • 分子需要除以 是为了剔除样本集合大小的影响。

     • NE 相对损失函数的优势在于：NE 考虑了样本集预测的难易程度。

       在平均损失相同的情况下，样本集越不均衡则越容易预测，此时 NE 越低。

3. AUC 也是评估模型能力的一个很好的指标，但是 AUC 反应的模型对样本的排序能力：auc=0.8 表示 80% 的情况下，模型将正样本预测为正类的概率大于模型将负样本预测为正类的概率。

   假设我们预估的 pCTR 是有偏的（相比较经验 CTR），此时我们需要乘以一个系数 来校准 calibration 。

   • 在校准前后，模型的 AUC 保持不变。因为对所有正负样本的 pCTR 乘以一个系数不改变它们的排序 rank 。
   • 在校准前后，模型的 NE 得到改善。因为校准后的 pCTR 分布与样本的标签分布距离更近。

5.2 GBDT 特征抽取

1. 有两种最简单的特征转换方式：

   • 连续特征离散化：将连续特征的取值映射到一个个分散的分桶里，从而离散化。

     这里桶的数量和边界难以确定，通常有两种方法：

     • 通过人工根据经验来设定分桶规则
     • 利用后续的分类器来显式的学习这个非线性映射，从而学习出有意义的分桶数量和边界。

   • 离散特征交叉：类似 FM 模型采用二路特征交叉（或者更高阶）来学习高阶非线性特征。

     对于连续特征可以先离散化之后再执行特征交叉，如 kd 树就是典型的代表。

   Boosted decisition tree:BDT 就是结合了上述两种方式的一个强大的特征提取器。

2. 对于 BDT，我们将每棵子树视为一个离散特征，其叶结点的编号为特征的取值并执行 one-hot 编码。

   假设 BDT 有两棵子树，第一棵有 3 个叶结点，第二棵有2 个叶结点。则样本提取后有两个特征：第一个特征取值为 {1,2,3}，第二个特征取值为 {1,2} 。

   假设某个样本被划分到第一棵子树的叶结点 2，被划分到第二棵子树的叶结点 1，则它被转换后的特征为：[0,1,0,1,0]。其中：前三项对应于第一个离散特征的 one-hot，后两项对应于第二个离散特征的 one-hot 。

3. 论文采用梯度提升树 Gradient Boosting Machine:GBM 来训练每棵子树，因此这种特征提取方式可以视为基于决策树的有监督特征编码：

   • 它将一组实值向量 real-valued vector 转换为一组二元向量 binary-valued vector 。
   • 每棵子树从根节点到叶节点的遍历表示某些特征转换规则。
   • 在转换后的二元向量上拟合线性分类器本质上是学习每个规则的权重。

4. 实验结果表明：采用 GBDT-LR 的模型相比于单独的 GBDT 提升了 3.4%。

   

5.3 数据新鲜度freshness

1. CTR 预估模型通常部署在数据分布随时间变化的动态环境中。训练数据和测试数据的时间距离越近，二者的数据分布差距越小，效果也越好。

   论文用某一天的样本数据训练一个模型，然后用该模型评估当天、一天后、两天后、… 六天后的测试数据。

   结果表明：模型需要每天根据最新的样本进行重新训练。与每周训练一个模型相比，每天训练一个模型可以提升模型效果大约 1%（以 NE 为指标）。

   

2. 考虑数据新鲜度，我们需要用最新的样本更新模型。有两种更新策略：

   • 每天用最新的数据重新训练模型。当模型比较大时，可能要花费几个小时甚至24个小时以上来训练。
   • 每天或者每隔几天来训练特征提取器 BDT ，但是用最新的数据在线训练 LR 线性分类器。

5.4 学习率

1. 当通过mini-batch 梯度下降法来训练在线 LR 分类器时，学习率的设定非常关键。有几种学习率设定方式：

   • per-coordinate 基于特征的学习率：在第 次迭代特征 的学习率为：

     

     其中： 为模型的超参数； 为第 次迭代的梯度在特征 的分量。

     • 特征 的梯度越大，说明该特征方向波动较大，则学习率越小，学习速度放慢。
     • 特征 的梯度越小，说明该特征方向波动较小，则学习率越大，学习速度加快。

   • per-weight 维度加权学习率：在第 次迭代特征 的学习率为：

     

     其中： 为模型的超参数， 为截至到第 次迭代特征 上有取值的所有样本数量。在特征上有取值表示：one-hot 之后的取值为 1 。

     设样本为 ，模型参数为 。 其中：

     

     对于广义线性模型：

     

     设损失函数为 。则有：

     

     因此可以看到，对于罕见特征由于大多数情况下特征取值 ，因此特征权重 几乎很难有更新的机会。

     • 特征 上有取值的样本越多，则可供学习的样本也多，则学习率越小，学习速度放慢。
     • 特征 上有取值的样本越少，则可用学习的样本也少，则学习率越大，学习速度加快。

   • per-weight square root 基于权重开方的学习率：在第 次迭代特征 的学习率为：

     

• global 全局学习率：在第 次迭代所有特征的学习率都为：

  

• constant 常量学习率：在第 次迭代所有特征的学习率都为：

  

1. 论文验证了这几种学习率的效果，其中超参数 通过grid search 来得到。

   

   实验结果如下表所示。结果表明：per-coordinate 方法获得最好的表现，而 per-weight 效果最差。

   • 全局学习率表现不佳，其主要原因是：每个特征上训练样本数量不平衡。

     一些常见特征上（如：“是否男性” 特征）的样本数量较多，而另一些罕见特征（如：“是否明星” ）上的样本数量较少。在全局学习率策略下，罕见特征学习率太快降低到很小的值，使得最优化难以收敛到最优点。

   • 虽然 per-weight 策略解决了该问题，但是它仍然表现不佳。主要原因是：虽然它对罕见特征的学习率控制较好，但是它对常见特征的学习率控制较差。它太快的降低了常见特征的学习率到一个很小的值，在算法收敛到最优点之前训练就过早终止了。

   

5.5 在线训练框架

1. 在线训练框架最重要的是为模型提供在线学习的标注样本。

   点击行为比较好标记，但是“不点击”行为难以标记。因为广告并没有一个“不点击”按钮来获取不点击的信息。

   因此，如果一个曝光在一个时间窗内未发生点击行为，则我们标记该次曝光是未点击的。

   之所以要设定一个时间窗，是因为广告曝光和用户点击之间存在时间差。这里有两个原因：

   • 给用户曝光一个广告后，用户不会立即点击。如：用户会简单浏览广告的内容再决定是否点击。对于视频类广告，用户甚至会观看完整视频之后再决定是否点击。

     因此曝光事件和点击事件这两个事件存在时间差。

   • 广告系统的曝光日志和点击日志通常都是分开的、独立的实时数据流。这两个数据流回传到在线训练系统可能并不是同步的，存在数据回传时间差。

2. 给定一个曝光，我们需要等待一段时间来确认它是否被用户点击。

   • 如果等待时间内收到了曝光的点击信息，则该曝光标记为正样本。
   • 如果等待时间内未收到曝光的点击信息，则该曝光标记为负样本。

   等待的时长需要精心选择：

   • 如果时间太长则实时训练数据延迟较大，数据 freshness 较差。

     同时，为了存储更长时间的曝光数据内存代价也较高。

   • 如果时间太短则因为没有等到点击信息回传，部分正样本被误判为负样本。这会导致实时样本集的经验 CTR 比真实 CTR 偏低。

     这种经验CTR 的偏差也可以检测并矫正。

   因此，需要在数据的 freshness 和点击覆盖率（能匹配上曝光的点击的数量占总点击数量之比） 之间平衡。

   通过挑选合适的时长，可以降低经验的 CTR 偏差到百分之1以下，同时内存代价也可以接受。

3. Facebook 在线训练框架如下图所示：

   • 用户浏览 Facebook 时向 Ranker 模块发送一个广告请求，请求中包含 request ID 。
   • Ranker 模块根据在线模型的预测结果，向用户返回一个广告，同时在曝光实时数据流中增加一条曝光日志。
   • 如果用户点击广告，则前端打点系统上报点击事件，在后台点击实时数据流中增加一条点击日志。
   • 通过 Oneline Joiner 模块实时获取最近一个时间窗的曝光、点击日志，并拼接样本特征来构造训练集。
   • Trainer 模块根据构造的训练集执行在线训练，训练好的模型部署到线上供 Ranker 模块使用。

   这会形成一个数据闭环，使得模型能够捕捉到最新的数据分布。

   

4. 在线训练需要增加对实时训练数据的异常保护。

   假设实时训练数据出现问题（如：前端打点上报出现异常、Online Joiner 工作异常等），导致大量的点击数据丢失。那么这批实时训练样本存在缺陷，它们的经验 CTR 非常低甚至为 0 。

   如果模型去学习这样一批样本，则模型会被带偏：对任何测试样本，模型都会预测出非常低、甚至为零的点击率。

   根据广告点击价值 eCPM = BID x pCTR，一旦预估点击率 pCTR 为零则广告的 eCPM 为零。那么这些广告几乎没有竞争力，竞争失败也就得不到曝光机会。

   因此需要增加实时训练数据的异常检测机制。如：一旦检测到实时训练数据的分布突然改变，则自动断开在线训练流程。

5.6 优化技巧

1. 论文提出了一些优化技巧来降低数据规模，从而节省训练代价，加快训练速度。

5.6.1 子树规模

1. 在 GBDT-LR 模型中，子树的数量越大模型表现越好，但是计算代价、内存代价越高。

   但是随着子树的增多，每增加一棵子树获得的效益是递减的。这就存在平衡：新增子树的代价和效益的平衡。

   如下图所示，可以看到：NE 随着子树数量的增加而下降，但是最后增加的1000棵子树获得的效益很低。

   • NE submodel0, NE submodel1 使用全量训练数据，不同的超参数来训练
   • NE submodel2 使用 1/4 的训练数据，模型在 1000 棵子树之后出现过拟合（损失函数增加）。

   

5.6.2 特征数量

1. 在 GBDT-LR 模型中，样本特征越大模型表现越好，但是计算代价、内存代价越高。

   但是随着特征的增多，尤其是无效特征的增多，每增加一个特征获得的效益是递减的。这就存在平衡：新增特征的代价和效益的平衡。

2. 为衡量特征数量的影响，我们首先对特征重要性进行排序，然后考察 topK 重要性特征的效果。

   可以通过 Boosting Feature Importance 来衡量特征重要性。有三种度量方法（如 XGBoolst/LightGBM ）：

   • weight：特征在所有子树中作为分裂点的总次数
   • gain：特征在所有子树中作为分裂点带来的损失函数降低总数
   • cover：特征在所有子树中作为分裂点包含的总样本数

   通常少数特征贡献了较多的重要性，大多数特征贡献了较少的重要性。如下图所示，top 10 特征贡献了大于一半的重要性，最后 300 个特征贡献了不到 1% 的重要性。

   

3. 论文考察了 top10,top20,top50,top100,top200 重要性的特征，结果如下图。

   可以看到，随着特征增加模型的 NE 在降低。

   

5.6.3 降采样

1. Facebook 每天的广告曝光量非常大。即使是每个小时，数据样本也可能上亿。在线学习需要对样本进行采样来降低数据量，从而提升训练速度。

2. 有两种降采样技术：

   • 均匀降采样：所有样本都以同一个概率 来随机采样。

     该方法容易实现，且采样后的样本分布和采样前保持不变。这样使得训练数据集的分布基本和线上保持一致。

     论文考察了几种采样率 ： 0.001,0.01,0.1,0.5,1 。结果表明：更多的数据带来更好的模型。但是采用 10% 的训练样本相对于全量样本仅仅损失了 1% 的预测能力（经过模型校准之后甚至没有降低），而训练代价降低一个量级。

     

   • 负降采样：保留所有的正样本，仅负样本以概率 来随机采样。

     该方法可以缓解类别不平衡问题。但是，采样后的样本分布和采样前不再相同，导致训练集的分布和线上不再保持一致。因此需要对模型进行校准。

     论文考察了几种采样率 ： 0.1,0.01,0.001,0.0001,... 。结果表明：最佳负采样率在 0.025 。

     

5.7 历史统计特征

1. 模型中用到的特征分类两类：上下文特征和历史统计特征。

   • 上下文特征：曝光广告的当前上下文信息。如：用户设备、用户所在页面的信息等等。
   • 历史统计特征：广告的历史统计行为，或者用户的历史统计行为。如：广告的上周平均点击率，用户的历史平均点击率。

2. 取 top K 重要性的特征，通过查看历史统计特征的占比来评估这两类特征的重要程度。

   结果表明：历史统计特征比上下文特征更重要。

   

3. 训练三种模型：仅仅包含上下文特征、仅仅包含历史统计特征、包含完整的特征。

   这三种模型的表现如下。

   

4. 虽然实验结果表明：历史统计特征要重要得多。但是，上下文特征对于解决冷启动问题非常重要。

   对新广告和新用户，上下文特征对于点击率预测是必不可少的。

5. 训练两种模型来评估模型对数据的freshness 依赖性：仅仅包含上下文特征、仅仅包含历史统计特征。

   实验结果表明：上下文特征比历史统计特征更为依赖数据 freshness 。这比较符合直觉：上下文特征刻画了事件发生的瞬间用户的行为，历史统计特征刻画了更长期的用户累积行为，因此历史统计特征更稳定。

   

5.8 模型校准 calibration

1. 模型校准分为两类：

   • 模型预测能力不足导致的校准
   • 训练数据分布和线上数据分布不一致导致的校准

   相比较第一类情况，第二类情况的校准系数偏离 1.0 更为严重，因此也更需要执行校准。

2. 给定样本集 ，假设模型预估的 pCTR 分别为： 。则样本集的经验 CTR 为：

   

   样本集的预估平均 CTR 为：

   

   定义校准系数为：预估平均 CTR 和经验 CTR 之比：

   

   它衡量了模型预期点击次数和实际观察到的点击次数之比，它的值与 1 的差异越小，则模型的表现越好。

   假设模型预估的结果为 ，则校准后的预估结果为：

   

3. 负降采样可以加快训练速度，改善模型能力。但是负采样中的训练数据分布和线上数据分布不一致，因此必须对模型进行校准。

   假设采样之前样本集的平均 CTR 为 0.1% 。当执行采样率为 0.01 的负降采样之后，由于正样本数量不变、负样本数量降低到之前的 0.01 ，因此采样后的样本集的平均 CTR 为 10% 。

   此时需要校准模型，使得模型的预估平均 CTR 尽可能与线上的平均 CTR 一致。假设模型预估的结果为 ，则校准后的预估结果为：

   

   其中 为负采样比例。