2018腾讯广告算法大赛

2018-08-14

× 文章目录

1. 比赛简介
2. 数据预处理
3. 特征工程
4. 模型选择
5. 总结

腾讯广告算法大赛 (CTR, Click-Through Rate) 总结

比赛简介

这个比赛是腾讯举办的一个推荐类型的比赛, 训练数据是种子人群及其中用户的脱敏特征, 每个用户的标签是是否属于该种子人群. 因此该问题是一个二分类问题, 采用 AUC 作为评价指标. 初赛阶段的数据量是1000万条数据 (4 GB), 复赛阶段是初赛阶段的5倍, 我们在初赛中的排名是 58/1600 (Top 3.6%), 复赛中由于特征工程较为复杂而数据量增大为5倍, 导致我们所采用的两个模型中的 LightGBM 模型因服务器资源紧张导致最终弃赛.

下面主要介绍本次比赛的一些相关知识点, 分为数据预处理、特征工程和模型选择三个方面.

数据预处理

预处理部分主要就是把训练数据处理成计算机模型能够使用的格式.

单、多取值离散特征进行 one-hot 稀疏编码

这一步主要就是把离散型单取值和多取值特征进行 one-hot 编码, 比如 age 这一特征是单取值特征, 对所有 age 中出现的数字进行 one-hot 稀疏编码; 而 interest 特征就是多取值特征, 同样也做 one-hot 稀疏编码处理.

部分连续值特征离散化后进行 one-hot 稀疏编码

我们注意到部分离散值特征的分布是满足长尾分布或者均匀分布的, 对于长尾分布的连续值特征, 我们将”尾部”统一按0处理, 其他部分则按数量比例划分切割点进行离散化后再 one-hot 编码. 而对于均匀分布的连续值特征则直接均匀的划分并进行 one-hot 编码处理.

hashtrick把数据保存为二进制数据流

这一部分主要是针对 FFM(Field-aware Factorization Machine) 模型(这个模型会在后文介绍)来设计的, 先把数据以字典的形式处理, 然后经过一个 hash 函数给特征划分 field 及每个 field 内的特征编号. 保存为二进制数据流的形式可以加速读写文件的速度并且占用更小的磁盘空间.

特征工程

首先, 在特征工程上我们吃了很大的亏, 这个比赛是有第一届的, 很多强特征挖掘都公布在 Github 上了, 但是我们很遗憾没有想过去挖掘这方面的信息. 另外, 在数据预处理部分中对离散值、连续值的处理也算是特征工程的一部分

特征交叉

特征交叉是指把明显具有关联度的特征进行组合以期获取一个更为好的新特征, 我们主要做了双、三特征交叉.
比如 age 这一特征和 consumptionAbility(消费能力) 具有明显关联, 一般认为年轻人较中老年人的消费力更强; 而前两者和 education 学历特征又具有明显的关联, 可以分别做双特征组合, 也可以把这三者组合作为一个新特征. 此外还有用户特征和广告特征之间的交叉. 特征交叉带来的问题是维度稀疏爆炸, 对此可以利用统计方法来压缩这些特征, 比如使用转换率来替代或者是统计出现的频次.

特征转化率

特征转化率是指统计满足某种属性的样本中正样本所占的比例, 例如, 我们可以统计 age=10 的正样本的比例, 但是注意直接这样统计之后作为新特征毫无疑问会暴露标签信息, 学习器会发现所有正样本的比例都符合一定规律. 因此, 我们需要用 k 折交叉来做这个特征. 具体地, 讲述数据分为5折, 前四折数据中统计 age=10 的正样本比例, 对于第5折数据我们使用前四折数据中的统计结果作为特征, 5次轮流对每折数据标记新特征.

tf-idf特征

对于 interest、topic 等多值特征, 我们考虑使用 tf-idf 来对这种特征做处理. tfidf(term frequency inverse document frequency)的主要思想是: 如果某个词或短语在一篇文章中出现的频率 tf 高, 并且在其他文章中很少出现, 则认为此词或者短语具有很好的类别区分能力, 适合用来分类. 在这里, 词或短语就是每个 interest 中出现的不同特征值, 文章就是不同样本对应的 interest、topic 多值特征.

特征筛选

经过特征工程处理后的特征维度是爆炸的, 为了加速训练同时防止过拟合, 我们对特征进行了压缩和筛选. 对于 tf-idf 特征我们原本想使用 SVD 进行降维分解, 发现数据量太大了时间复杂度无法接受, 后来就是限制 tf-idf 的生成维度, 然后用 scipy 的稀疏矩阵保存以节约内存. 对于最后所有的特征我们则是用 LightGBM 模型的特征重要性以及计算特征之间的 Pearson 相关系数来筛选不重要和冗余特征. Pearson 相关系数的定义是两个变量的协方差和标准差的商:

$\Large{\rho}_{X,Y} =\ \dfrac{cov(X, Y)}{\sigma_X \sigma_Y} =\ \dfrac{E[(X - \mu_X)(Y - \mu_Y)]}{\sigma_X \sigma_Y}$

模型选择

回顾 CTR 领域的模型, 大致发展方向是 LR $\rightarrow$ GBDT等树模型 $\rightarrow$ FM/FFM $\rightarrow$ DeepFM等深度模型.
LR 由于太简单, 我们主要尝试了后三个发展阶段的模型, 基于 Baseline 改进的 LightGBM、FFM 和 DeepFM. 最终的情况是 LightGBM 模型效果最好, FFM 模型其次, DeepFM 模型则效果一般对得分没什么贡献. 依靠前两个模型的融合得到了初赛58名的成绩.

LightGBM

LightGBM 模型是 Microsoft 提出的一个 state-of-art 提升树模型, 针对之前的 Xgboost 做出了改善包括速度和内存优化, LightGBM 采用 leaf-wise 分裂方法来分裂树, 而 Xgboost 则是 level-wise, 当叶子节点相同时前者可以减少更多的 loss 但是容易过拟合, 因此需要 max_depth 参数来限制树的深度.
Xgboost 的决策树增长方式:

LightGBM 的决策树增长方式:

传统 GBDT 算法对于每个特征, 都需要扫描整个数据集得到分割点, 这个过程是非常耗时的. LightGBM 主要通过 GOSS(Gradient-based One-Side Sampling) 和 EFB(Exclusive Feature Bundling) 两项技术使得模型在获取几乎同等精度的情况下速度提升 20倍 以上, 除了 GOSS 和 EFB, LightGBM 抛弃了 pre-sorting 算法进行特征选择和分裂, 转而使用基于直方图 (Histogram) 的方法, 其主要思想是将连续的浮点特征离散成 k 个离散值, 并构造宽度为 k 的 Histogram. 在遍历数据的时候, 根据离散化后的值作为索引在直方图中累积统计量. 当遍历一次数据后, 直方图累积了需要的统计量, 然后根据直方图的离散值, 遍历寻找最优的分割点. 其训练精度其实是比不上 pre-sorting 算法的, 但是实际使用差异不大甚至更好.
本次比赛的数据量也确实验证了 LightGBM 的速度优势, 我们尝试了 Xgboost 模型, 同样的训练数据 LightGBM 只用了一天跑完, Xgboost 则根本无法在可接受时间内完成, 此外 LightGBM 的内存占用也优于 Xgboost, 因此我们舍弃了 Xgboost.

GOSS: 基于不同样本的梯度在计算信息增益的过程中扮演不同的角色的假设, 作者认为拥有大梯度的样本贡献了更多的信息增益, 为了持结果的准确性, 应当尽可能保留大梯度的样本, 舍弃小梯度样本, 当数据量很大时这种方法不仅速度更快而且结果也更准确. 实际做法是按 a*100% 比例抽取大梯度样本, b*100% 比例抽取小梯度样本, 并放大小梯度样本的权重为 $\dfrac{1-a}{b}$ .
EFB: 在真实的应用中, 高维度特征具有稀疏性, 这样可以设计一个减少有效特征数量的几乎无损的方法, 特别是在稀疏特征中, 许多特征是互斥的, 出现大量 0，例如 one-hot 不会同时取 1. 我们可以捆绑互斥的特征. 最后还原捆绑互斥问题为图着色问题, 使用贪心算法近似求解.
上述是 LightGBM 的理论基础, 因为有 LightGBM 的 Baseline 实现, 针对该模型我们主要做的是参数调优争取在已有的特征基础上获取最好的结果, 查看 LightGBM 的文档, 我们队一些参数进行了调试, 首先影响最大的肯定是学习率参数, 这个参数太大的话速度回变快但是精度降低, 太小的话速度又太慢, num_leaves、max_depth 等参数可以控制过拟合, 我们还发现使用带 dropout 的树增长策略 dart 的结果是优于 gbdt 的, 推测是数据量较大加入了 dropout 可以减少过拟合现象. 为了获取较好的参数, 我们抽取了 10% 的训练数据来做参数优化, 利用这一小部分数据的表现来决定参数最终的配置.
FFM
FFM 是由 FM 演化而来的, 首先介绍一下 FM
FM(Factorization Machine): 降维版本的特征二阶组合
FM 之前用的方法是人工特征工程加上 LR, 为了更好地捕捉特征往往需要人为的判断组合一些特征, 例如 “男性大学生” 和 “点击游戏类广告” 两个特征就会是个很好的组合特征. 人工组合特征存在特征爆炸, 特征难以识别等问题. 因此, 提出了线性模型的二阶多项式(2d-polynomial): $y_{poly} = \sigma(<\overrightarrow{w}, \overrightarrow{x}> + \sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}\cdot x_i \cdot x_j)$ 括号内第一部分就是 LR 的模型, 后半部分就是 FM 中扩展的特征组合二次项, 其实就是特征两两相乘(组合)构成新特征, 并对新特征分配一个独立权重, 然后学习这些权重, 将上式改写为矩阵形式: $y_{poly} = \sigma(\overrightarrow{w}^T \cdot \overrightarrow{x} + \overrightarrow{x}^T \cdot W^{(2)} \cdot \overrightarrow{x})$ 其中 $W^{(2)}$ 就是组合特征的权重矩阵, 其参数个数是 $O(n^2)$ , 对其进行因子分解(Factorization)得到两个低维(如 n*k)矩阵 $W^T \cdot W$ 相乘, 至此权重矩阵的参数个数大幅降低为 $O(n*k)$ , 这也是 FM 名字的由来. 再对上式中 $W^{(2)}$ 替换成分解后的矩阵并写成向量内积形式: $y_{FM} = \sigma(<\overrightarrow{w}, \overrightarrow{x}> + <W \cdot \overrightarrow{x}, W \cdot \overrightarrow{x}>)$ 这个式子中后半部分可以看做是 Embedding, 先通过矩阵 $W$ 对稀疏特征 $\overrightarrow{x}$ 进行嵌入, 随后对嵌入后的稠密向量进行内积得到二阶组合特征. 根据矩阵知识, 上式可进一步写成和式并去除重复的特征平方项, 得到最终的 FM 公式: $y_{FM} = \sigma(<\overrightarrow{w}, \overrightarrow{x}> + \sum_{i=1}^{n}\sum_{j=i+1}^{n}<\overrightarrow{v_i}, \overrightarrow{v_j}> \cdot x_i \cdot x_j)$ 其中, $\overrightarrow{v_i}$ 表示第 $i$ 维特征的隐向量, 其长度为 $k$ . 对比线性模型的二次项推广模型可知, FM 的组合特征权重不是独立的, 因此 FM 是一个参数较少但表达能力较强的模型.
FFM(Field-aware Factorization Machine): 基于域的FM
通过引入 field 概念, Yu-Chin Juan 等提出了 FM 模型的升级版 FFM, FFM 将相同性质的特征归于同一个 field, 例如 interest 这个多值特征里的所有可能的取值都可以在 one-hot 编码之后归为一个 field. 在 FFM 中, 每一维特征 $\overrightarrow{x_i}$ 针对其他 field $f_j$ 都会学习一个隐向量 $\overrightarrow{v_{i,f_j}}$ , 因此隐向量不仅与特征有关, 还与 field 有关, 例如 interest 特征和 age、education 等特征组合时 interest 所使用的隐向量是不同的, 这也符合同一特征与不同的特征之间相关性不同的直觉, 这就是所谓 Field-aware 的由来.
那么假设样本有 $n$ 个特征属于 $f$ 个 field, 那么 FFM 有 $nf$ 个隐向量, 而 FM 中只有 $n$ 个, 因此 FM 可以看做是 FFM 的特例即 FM 把所有的特征都归到一个 field 内的 FFM 模型. 我们可以得到 FFM 模型的公式如下: $y_{FFM} = \sigma(<\overrightarrow{w}, \overrightarrow{x}> + \sum_{i=1}^{n}\sum_{j=i+1}^{n}<\overrightarrow{v_{i,f_j}}, \overrightarrow{v_{j,f_i}}> \cdot x_i \cdot x_j)$ 其中, $f_j$ 是第 $j$ 个特征所属的 field. 如果隐向量长度为 $k$ , 则 FFM 模型的参数个数为 $O(nfk)$ 远多于 FM 的 $O(nk)$ , 其复杂度也因为 field 的引入, 变为 $O(kn^2)$ .
FFM 模型是流式训练, 对内存占用极低, 不需要人为的挖取特征, 并且训练速度较 LightGBM 也快上许多, 但是精度较 LightGBM 还是差上一些, 初赛近凭 LightGBM 和 FFM 我们就获取了第58名的成绩, 现在看来还是遗憾很大的, 毕竟前50名还有单独的奖励和证书.
DeepFM
深度模型在这个比赛之前我们几乎没怎么接触过, 所以这个模型最终我们没能成功使用, 但是还是要提一下包括 DeepFM 在内的深度模型是如何解决 CTR 问题的. 首先看下深度模型在 CTR 领域的发展图, 具体参考这里:

一开始 CTR 中的深度模型主要采用 Embedding + MLP 结构, 即对 one-hot 编码后的特征进行 embedding 降维后拼接成一层隐藏层, 随后堆叠全连接层通过一个 sigmoid 得到最后的预测结果. 这种方法对低阶特征挖掘不够学习较为困难.
在前面我们提到 FM 模型实际上是通过参数矩阵 $W$ 对特征向量进行 embeddding 然后再通过内积组合特征, 这启发了后人在 DNN 中应用 FM. 下面介绍几个经典的 DNN 模型.

1、Weinan Zhang在2016年提出 FNN(Factorization Machine supported Neural Network), FNN 将 FM 与 MLP 结合, 采用 FM 预训练得到的隐含层及其权重作为神经网络第一层的初始值, 然后堆叠全连接层. 可以看出 FNN 和 Embedding + MLP 结构差距主要在 Embedding 方面, FNN 采用 FM 的预训练权重矩阵作为输入初始值.

缺陷: embedding 参数被 FM 影响; pre-training 阶段效率低; FNN 只捕获 high-order 特征组合 (low-order 特征对 CTR 很重要).

2、Huifeng Guo在 2016年提出了 PNN(Product-based Neural Networks), 与 FNN 直接使用 FM 预训练结果不同, PNN 将 FM 预训练得到的嵌入向量两两进行向量积, 得到的结果作为 MLP 的输入. 向量积分为内积和外积操作, 如用内积则将内积后的标量拼接为一个向量作为输入, 如用外积则将得到的矩阵求和作为输入.

缺陷: outer product 丢失太多信息, 不太可靠; inner product 更可信, 但 product 层输出全连接到第一隐含层的所有神经元, 计算复杂度还是太高 (DeepFM 直接把 Wide 部分连接到最后输出层的一个神经元); 且 PNN 和 FNN 一样忽视了 low-order 特征组合.

3、Google在2016年提出 Wide & Deep 深度模型, 前面的深度模型大多和 FM 有着很强的联系, 而 Wide & Deep 模型则是从 Embedding + MLP 出发, 它奠定了后面 CTR 深度模型(如 DCN、DeepFM)的框架. Wide & Deep 模型将深度模型和线性模型联合训练, 二者结果求和作为预测结果, 其 Deep 部分就是多层 MLP, Wide 部分则是 LR, 可以手动设计特征.

缺陷: 对于 Wide 部分需要人工特征工程

4、Ruoxi Wang在2017年提出了 DCN(Deep & Cross Network), 我们知道 FM 是通过向量内积来实现二阶特征组合, MLP 则是在 Embedding 之后通过一层层的矩阵乘法来组合高阶特征, DCN 的想法就是直接将 FM 过程在高阶特征组合上推广, 其 Deep 部分就是多层 MLP(矩阵操作), Cross 部分的每一层都会对特征不断进行交叉(向量操作), Cross 部分实际上是对 FM 的推广.

缺陷: Cross 部分的性能和交叉层的深度有关

5、Huifeng Guo在2017年提出了 DeepFM, DeepFM 的工作主要是基于 Wide & Deep 模型, 我们知道 W&D 模型输入向量维度很大, 且其 Wide 部分的输入包含了人工提取的特征, 因此复杂度较高且需要耗费人工精力. 而 DeepFM 的 Wide 和 Deep 部分共享相同的输入, 可以提高训练效率并且无需人为设计复杂的特征工程. DeepFM 使用 FM 来建模低阶特征, 用 DNN 结构来建模高阶特征.

如下图所示, DeepFM 包含两个部分 FM Component 和 Deep Component. FM Component 就是 FM 模型捕捉低阶特征, 其输出直接连接到最后的输出神经元; Deep Component 就是前馈神经网络捕捉高阶特征, 可以用 ResNet 实现, 考虑到 CTR 问题中的输入向量是高度稀疏的, 因此需要做一个 Embedding 处理获取神经网络的稠密低维输入否则难以收敛, Embedding 部分无论输入的 field 维度是多少都会得到同样的 k 维嵌入向量, FM 中的隐含向量 V 现在作为嵌入神经网络的权重, 经过学习来压缩输入 field 向量为 embedding 向量.

总结

本次比赛主要还是吃了不懂深度模型的亏, 传统的特征挖掘也不够精细, 另外对 LightGBM 也不算很熟, 复赛阶段由于数据量猛增导致 LightGBM 模型内存超出, 现在想想应该切片训练好歹也是有个结果的. 至于神经网络模型则是不够了解, 没有很好地发挥深度模型在大数量下的优势.

给出一些模型使用的建议:

1、FFM 在使用的时候要注意对连续特征做归一化或是离散化;

2、神经网络模型难以直接处理高维稀疏数据, 因此可以把 FM/FFM 模型当做是神经网络模型的 Embedding 向量, 同时可以引入 Attention 机制来进一步提升神经网络模型, 不过很可惜我们在做比赛的时候对神经网络模型不够了解, 也没有想到使用 Attention.

3、FM/FFM 模型和梯度提升树模型都可以进行特征组合, 但后者在数据高度稀疏时就很难有效的学习到复杂的组合特征, 所以应该使用 FM/FFM 的隐向量来作为神经网络的 Embedding 嵌入向量效果会好的多.

4、梯度提升树模型 (Xgboost/LightGBM) 可以更好地处理缺失特征和跨区间特征以及转化率特征, 并且对异常点不敏感 (决策树模型的特点), 可以更好地处理特征相关性, 与 RF 相比往往可以学习更加复杂的决策边界, 效果相对较好. 但是 RF 的优势则是不易过拟合和并行化; 而梯度提升树模型和神经网络模型相比的优势在于中小数据集上, 当网络结构合适时且数据量较大往往是神经网络的模型更好.