计算广告CTR预估系列(七)–Facebook经典模型LR+GBDT理论与实践

一、介绍

本文主要介绍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的公式如下：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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特征变换。对于一个样本，针对每一颗树得到一个类别型特征。该特征取值为样本在树中落入的叶节点的编号。举例来说：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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

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

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

从最后的实验结果来看：将LR和GBDT进行组合模型的性能提升了很多。
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

3.2 Data freshness

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

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

计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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

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

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

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

3.3 LR线性分类器

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

为此，Facebook针对SGD-based online learning研究了5中学习速率的设置方式，如下：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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

最终的实验结果是：Per-coordinate learning rate效果最好：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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

下图是实验中的参数设置，以及实验结果，供大家参考：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

其他的学习速率的问题大多在于：由于模型收敛于一个局部最优解导致学习很快就停止了。另外，之前提到的BOPR和使用per-coordinate的SGD是非常相似的。他们的效果也非常接近，但是BOPR需要计算均值和方差，计算量更大。两者效果比较如下：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

四. 线上模型架构

这部分主要是说明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系统结构如下：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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

4.3 挑战

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

五、处理大量训练数据

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

Uniform Subsampling
Negative down sampling

5.1 Uniform subsampling

均匀采样非常的简单，易于实现。而且使用均匀采样没有改变训练数据的分布，所以模型不需要修改就可以直接应用于测试数据上。
下图给出了不同采样率对模型性能的影响：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

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

5.2 Negative down sampling

计算广告中大部分的训练样本都极度不平衡，这对模型会造成很大影响。一种解决办法就是对负样本进行欠采样。实验结果如下：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践
可以看到采样率不同，对模型性能影响很大。采样率为0.025的时候取得最好结果。

5.3 Model Re-Calibration

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

其中：

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

六、各种实验结果

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

6.1 Number of boosting trees

下图给出了，boosting trees对模型的影响：
计算广告CTR预估系列(七)--Facebook经典模型LR+GBDT理论与实践

boosting tree数量从1到2000，叶节点个数被限制为最大12个。submodel之间的区别在于训练数据大小的不同，比如submodel 2的训练数据只有前面两个的1/4。
可以看到随着boosting tree数量的增加，模型的性能有所提升。但是几乎所有的提升都来自于前500个trees，而后面的1000个trees的提升甚至都不到0.1%。submodel 2在1000颗trees甚至模型效果在变差，原因是过拟合。