CTR预估专栏 | Facebook经典模型LR+GBDT理论与实践

2018 年 8 月 3 日 AI前线

作者｜李宁宁

来源｜机器学习荐货情报局（ID：ML_CIA）

编辑｜Debra

AI 前线导读：这是计算广告 CTR 预估系列的第七篇文章—Facebook 经典模型 LR+GBDT 理论与实践，主要介绍 Facebook 提出的 CTR 预估模型 LR(Logistic Regression)+GBDT。

更多干货内容请关注微信公众号“AI 前线”，（ID：ai-front）

一、介绍

本文主要介绍 Facebook 提出的 CTR 预估模型 LR(Logistic Regression)+GBDT。当时深度学习还没有应用到计算广告领域，Facebook 提出利用 GBDT 的叶节点编号作为非线性特征的表示，或者说是组合特征的一种方式。

LR+GBDT 相比于单纯的 LR 或者 GBDT 带来了较大的性能提升，论文中给出数据为 3%，这在 CTR 预估领域确实非常不错。除此之外，Facebook 还在在线学习、Data freshness、学习速率、树模型参数、特征重要度等方面进行了探索。

相比于搜索广告领域，根据用户 query 来给出候选广告，然后利用 Rank 模型对候选广告进行排序。这些广告要么显式要么隐式的和用户 query 相关联。但是在 Facebook 这样的社交场合中，广告并没有和用户 query 相关联，但是用户看到的广告一定程度上反映了用户的人口统计特性和兴趣特性。基于这个原因，在 Facebook 上展示的广告相比于搜索广告中的要多一些。

在实际的生产环境中，Facebook 做了多个分类器，并把他们级联起来。但是论文中分析的是最后的那一个 prediction 模型。它直接给出最后的 CTR 概率。

二、评估函数

论文目的是分析机器学习模型的影响因素，所以没有使用实际利益相关的评测函数。而是主要从以下两方面进行：

Normalized Cross-Entropy 或者叫做 Normalized Entropy，缩写 NE
Calibration 校准

2.1 Normalized Cross-Entropy(NE)

NE 的公式如下：

NE 等于预测的 log loss 除以 background CTR 的熵
NE 越小模型性能越好
除以了 background CTR 的熵，使得 NE 对 background CTR 不敏感
p 代表平均经验 CTR

2.2 Calibration

Calibration 校准是期待或预测的点击数除以实际的点击数。它是一个比例。
Calibration 越接近 1，模型性能越好

AUC 也是一个非常不错的评价指标，但是它有个问题。比如当我们的模型预测的 CTR 概率都偏高了 2 倍，我们可以通过 Calibration 校准，使用一个全局的 0.5 的系数来修正。修正之后 NE 也会提高，而 AUC 却保持不变。

在实际工作中，我们希望得到的是尽可能准确的预测每个广告被点击的概率，而不是仅仅得到相对的概率排序。所以 AUC 不如上面的 NE、Calibration 合适。

三、模型架构

经过多次实验，FB 得出结论：正确的模型 + 强特征 是提升模型性能的核心。相比于这两点，其他的因素的影响就小很多，比如学习速率、采样率等。当数据量足够大时，一个好的模型应该是稳定的，也就说参数的调整不会导致模型性能出现剧烈的震荡。

这里面，正确的模型就是指：Logistic Regression + Boosting Decision Tree。特征的话包含两方面的特征：用户或广告的历史信息特征、上下文特征。其中，用户或广告的历史信息特征取决定性作用。

学习算法是用的是 Stochastic Gradient Descent(SGD)，或者 Bayesian online learning scheme for probit regression(BOPR) 都可以。但是最终选择的是 SGD，原因是资源消耗要小一些。SGD 和 BOPR 都可以针对单个样本进行训练，所以他们可以做成流式的学习器 (stream learner)。

3.1 决策树 Feature Transforms

为了提升线性分类器的准确度，有两种方法进行特征变换：

对于连续特征。先进行离散化 bin，然后把 bin 的编号作为离散型特征。这样的话，线性模型可以分段的学习到一个非线性的映射，在每一段内的映射是不变的。另外，对于 bin 边界的学习非常重要
对于离散特征。做笛卡尔积，生成的是 tuple input features。笛卡尔积穷举了所有的特征组合，其中也包含部分没用的组合特征，不过可以筛选出来。

提升决策树 (boosted decision tree) 就可以很方便很好的实现上面我们说的这种非线性和 tuple 特征变换。对于一个样本，针对每一颗树得到一个类别型特征。该特征取值为样本在树中落入的叶节点的编号。举例来说：

上图中的提升决策树包含两棵子树，第一棵树包含 3 个叶节点，第二棵树包含 2 个叶节点。输入样本 x，在两棵树种分别落入叶子节点 2 和叶子节点 1。那么特征转换就得到特征向量 [0 1 0 1 0]。也就是说，把叶节点编号进行 one-hot 编码。

那么，怎么样直观的理解这种特征变化：

看做是一种有监督的特征编码。把实值的 vector 转换成紧凑的二值的 vector。
从根节点到叶节点的一条路径，表示的是在特征上的一个特定的规则。所以，叶节点的编号代表了这种规则。表征了样本中的信息，而且进行了非线性的组合变换。
最后再对叶节点编号组合，相当于学习这些规则的权重。

从最后的实验结果来看：将 LR 和 GBDT 进行组合模型的性能提升了很多。

3.2 Data freshness

论文里的数据取 2013 年某一周内的实际数据，并且尽可能的保证线上线下的数据分布是一致的。训练集、测试集的划分基本都是按照时间来的，比如选一天的数据作为训练集，其后的一天或者几天作为测试数据。

CTR 系统的环境经常变化，数据的分布也经常随着时间变化而变化。为了验证 data freshness 对模型的影响，实验中训练集固定为某一天的数据，然后分别测试在之后连续几天的模型的表现。

可以发现随着天数的增加，data freshness 也变得越来越差，模型的性能也越来越差。所以，针对每天的偏差进行重新训练就非常有必要。

一种做法是说每天都重新训练。即使是 mini-batch 来训练，也会非常耗时。提升树的训练时间受很多因素的影响，比如：样本数量、树深度、树数量、叶子节点个数等。为了加快速度，可以在多 CPU 上通过并行化来实现。

那么现在我们给出一种新的方法，可以做到：

提升树可以一天或者几天来训练一次
LR 可以实现在线学习 online learning，几乎是实现实时的训练

3.3 LR 线性分类器

为了最大化 data freshness，我们采取的措施是针对 Logistic Regression 进行在线增量训练。也就是说只要用户点击了广告，生成了新的样本，就进行增量训练。

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

前三种使得不同的参数有不同的学习速率
后两种对于所有的参数都是用相同的学习速率

最终的实验结果是：Per-coordinate learning rate 效果最好：

这个跟 Adagrad 的做法几乎一样，分母上使用梯度的平方进行累加，然后开根号。使得不同的参数具有不同的学习速率。顺便提一句，Adagrad 也有缺点：随着迭代不断进行，学习速率无限的减小，直到模型无法进行学习。

下图是实验中的参数设置，以及实验结果，供大家参考：

其他的学习速率的问题大多在于：由于模型收敛于一个局部最优解导致学习很快就停止了。另外，之前提到的 BOPR 和使用 per-coordinate 的 SGD 是非常相似的。他们的效果也非常接近，但是 BOPR 需要计算均值和方差，计算量更大。两者效果比较如下：

四. 线上模型架构

这部分主要是说明 online data joiner。前面我们研究过 data freshness对于模型的训练是非常重要的。那么新的训练数据是怎么产生的那，这就是 online data joiner 的作用。

这个名字主要是来自于，这里最关键的步骤就是把 labels(click/no-click) 和训练输入 (ad impressions) 以一种在线的方式连起 (join) 起来。所以系统被称为 online data joiner。

4.1 label 标注

首先设定一个足够长的阈值。一个广告展示给用户之后，如果用户在阈值的时间内没有点击广告就标记为 no-click，点击了的话就标记为 click。这个等待的时间窗口需要非常小心的调整。

如果太长了，会增加缓存 impression 的内存消耗，而且影响实时数据的产生；如果太短了则会导致丢失一部分的点击样本，会影响 click converage 点击覆盖。

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

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

4.2 模型架构

online data joiner 系统结构如下：

广告展示生成特征，用户给出反馈：点击或者未点击。Online Joiner 捕获反馈生成新的训练样本，训练样本经过 Trainer 的学习得到新的模型。模型反过来影响 Ranker 系统对展示的广告进行选择排序，用户又看到了新的广告，决定是否要点击。一直这样下去，形成一个 闭环系统。

4.3 挑战

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

五、处理大量训练数据

很多的计算广告领域的训练数据量都是非常巨大的，那么如何有效的控制训练带来的开销就非常重要。常用的办法是采样，分为：

Uniform Subsampling
Negative down sampling

5.1 Uniform subsampling

均匀采样非常的简单，易于实现。而且使用均匀采样没有改变训练数据的分布，所以模型不需要修改就可以直接应用于测试数据上。下图给出了不同采样率对模型性能的影响：

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

5.2 Negative down sampling

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

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

5.3 Model Re-Calibration

负样本欠采样可以加快训练速度并提升模型性能。但是同样带来了问题：改变了训练数据分布。所以需要进行校准。举例来说，采样之前 CTR 均值为 0.1%，使用 0.01 采样之后，CTR 均值变为 10%。我们需要对模型进行 Calibration(校准) 使得模型在实际预测的时候恢复成 0.1%。调整公式如下：

其中：

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

六、各种实验结果

所有的这些探索都是为了能够平衡模型性能 (accuracy) 和资源消耗 (内存、CPU)。只有当你充分了解模型和数据每个部分后，才能根据实际情况做出最佳的取舍。

6.1 Number of boosting trees

下图给出了，boosting trees 对模型的影响：

boosting tree 数量从 1 到 2000，叶节点个数被限制为最大 12 个。submodel 之间的区别在于训练数据大小的不同，比如 submodel 2 的训练数据只有前面两个的 1/4。

可以看到随着 boosting tree 数量的增加，模型的性能有所提升。但是几乎所有的提升都来自于前 500 个 trees，而后面的 1000 个 trees 的提升甚至都不到 0.1%。

submodel 2 在 1000 颗 trees 甚至模型效果在变差，原因是过拟合。

6.2 Boosting feature importance

为了在资源消耗和模型性能之间做到平衡，可以通过控制 Feature Count 来调节。如果想删掉一些特征的话，那么就需要研究这些特征的重要程度的分布，并研究删除部分特征后的效果。

下图给出了特征重要程度的分布情况：

上图首先对特征按照重要程度来进行排序，编号后再画图。特征重要程度按照 使用该特征进行分裂，所带来的 loss 减小的累积量。因为一个特征可以在多颗树上进行使用，所以累积要在所有的树上进行。

上图中，黄线表示对特征进行累加后的值，然后进行 log 变换。可以看到最终结果是 1，表示所有特征的重要度总和是 1. 最重要的是期初非常陡峭，上升的非常快，说明 特征重要度主要集中在 top10 这些特征中。前 10 个特征，贡献了 50% 的重要度，后面 300 个特征，贡献了 1% 的重要度。

那么能否全部去掉后面这些看起来不是那么重要的特征那？试一试：

显然，全部去掉是不行的。说明大量弱特征的累积也是很重要的，但是去掉部分不那么重要的特征，对模型的影响比较小，比如从 400 到 200。