2019, Vol. 40
随着平板电脑和智能手机的广泛使用, 在APP中内置广告逐渐成为了移动数字营销的重要形式.现有的许多广告平台在推荐广告时其目标是最大化点击次数, 而移动APP广告期望用户进行的动作不仅仅是点击而是下载APP, 这时广告的转化率就成为广告投放平台制定投放策略时需考虑的重要指标.
实际上, 由于被转化的广告数据很少, 所以相比于对广告点击率的预估, 转化率的预估变得更加困难.现有的对广告点击率(click through rate, CTR)和转化率(conversion rate, CVR)的预估模型可以分为两类:一类是线性模型, 另一类是非线性模型.在线性模型中, 例如逻辑回归[1](logistic regression, LR), 具有简单、可解释性强和伸缩性好等优点, 已被Google, Facebook和Yahoo广泛使用.近年来, 因子分解机(factorization machine, FM)[2-3]、梯度增强决策树(gradient boosting decision tree, GBDT)、基于GBDT的扩展结构(XGBoost)和深度神经网络(DNN)[4]也被应用于工业上进行广告点击率和转化率预测.由Criteo举办的Kaggle广告点击率预估比赛, 获得优胜的模型FFM[5]是在FM基础上增加了域的概念.由于单一模型存在不同的优缺点, 不能达到最佳的预估效果, 所以通常将不同模型进行组合来提高预估的准确性.Google的推荐系统采用Wide & Deep模型[6], 这种混合模型结合了LR宽和DNN深的特性, 提高了预估准确性; Facebook上广告的点击率预估使用GBDT和LR混合模型, 通过GBDT进行非线性特征转换, 然后提供给LR进行最终预测, 混合之后的模型比单一模型的预估准确度提升了3%左右.模型FNN[7]则将通过FM学习的低阶组合特征嵌入到DNN中.这些混合模型偏向于分析高维组合特征, 有些虽然同时考虑了低阶特征间的相互关系, 但难以达到平衡.本文通过分析数据构造特征, 将LightGBM[8]模型提取的高阶组合特征与低阶离散型特征作为FFM的输入进行广告转化率预估, 使FFM在预估时不局限于二阶组合特征, 改善了FFM的预估性能.
1 解决方案本文针对现有广告转化率预测中的困难和模型的不足, 提出了新的解决方案, 其总体流程如图 1所示, 包括:数据筛选、数据划分、特征工程、建立模型.
|
图 1 解决方案的总流程 Fig.1 Overall flow chart of the solution scheme |
由于在广告系统中存在转化回流时间, 所以最后几天数据的转化标记可能不够准确, 但是直接删除这些数据可能会破坏数据的完整性.通过分析转化时间和应用程序(application, APP)之间的关系, 对数据进行筛选来保留数据的真实性和完整性.在划分训练和测试数据时, 本文通过实验确定了合适的数据窗口大小, 并且分析了数据新鲜度对预估结果的影响.
本文利用LightGBM模型天然的树型结构对特征进行组合来提取更高阶的组合特征, 并且同时将低阶和高阶特征作为FFM模型的输入, 得到了比较好的预估结果.
2 特征提取 2.1 低维特征提取本文使用的数据集来自腾讯(Tencent)在2017年4月举办的“社交广告算法大赛”中的广告日志信息, 出于对数据安全的考虑, 数据中一些原始字段被进行了加密处理.其中包括广告信息、用户信息和上下文信息.用户信息描述了用户的属性和行为, 例如用户ID、年龄、性别、学历、兴趣爱好、历史APP安装列表等; 广告信息描述了一条广告素材的信息, 包括广告ID、素材ID、APP分类、APP平台等; 上下文信息描述了广告所在环境的信息, 包括广告位ID、站点集合ID、广告位类型、联网方式、运营商等.本文将从原始数据信息中提取的低维特征分为以下几类, 其中ID类特征和交叉特征是离散型特征, 时间相关特征和统计特征是连续型特征.
1) ID类特征:用户ID、广告ID、广告位ID和APP的ID等.
2) 交叉特征:考虑到用户和广告、广告和APP、用户和APP之间存在密切的绑定关系, 所以增加了用户-广告、广告-APP和用户-APP交叉特征.
3) 时间相关的特征:分别统计用户、用户-广告特征和用户-APP特征在一段时间内的点击次数和安装次数.
4) 统计特征:分别统计ID类特征、交叉类特征的历史转化率和点击率.
2.2 高维特征提取本文利用LightGBM模型来提取高维组合特征.LightGBM是一种集成学习模型, 通过不断迭代训练多棵决策树以最小化损失函数.已知广告数据都是高度稀疏的, 也会出现数据缺失的情况, 而LightGBM模型不但可以处理稀疏和缺失数据, 同时还支持离散型数据的直接输入, 提高了数据处理的效率.提取高维特征的具体步骤如下:
步骤1 将低维特征作为LightGBM模型的输入, 并设置参数(迭代次数、损失函数、采样率a, b等), 初始化模型.
步骤2 将每个特征进行分桶并归一化.
步骤3 计算特征的直方图.
步骤4 从直方图中获得分裂增益, 在树的叶子节点中选择最佳的分裂特征和特征值.
步骤5 根据选择的最佳分裂特征和特征值将样本分割到左右子树中.
步骤6 重复步骤3~步骤5直到达到限制的叶子数或者限制深度.
步骤7 将新生成的树放入模型.
步骤8 根据生成模型预测每条样本, 并且计算梯度值.
步骤9 将数据按照梯度绝对值递增顺序排序.
步骤10 从数据中取前a×100%有较大增益值的样本, 并且在剩余的数据中随机采样b×100%个样本.
步骤11 在采样的具有较小增益的样本中, 将其增益值乘以常数(1-a)/b, 可以保证不改变数据分布.
步骤12 将步骤9, 步骤10得到的数据作为新的输入数据, 重复步骤2~步骤12, 直到迭代结束.
在步骤2~步骤4中采用直方图方法进行分裂特征和特征值的选择, 在步骤3中计算子节点的直方图时可以通过将父节点和兄弟节点的直方图做差快速得到.步骤8~步骤11具体实现可参照文献[8].
3 算法框架FFM能够处理高度稀疏的数据, 并且能够分析二阶特征的组合关系, 通过将特征分域, 使每个特征对应不同域中不同的隐向量, 在广告点击率和转化率的预估中有很高的准确率.本文通过将提取高阶特征的LightGBM模型与FFM集成, 弥补FFM在高阶组合特征分析上的不足, 从而提高模型对广告转化率预估的准确性.模型集成过程如图 2所示.
|
图 2 基于FFM的混合模型的框架 Fig.2 Framework of FFM-based hybrid model |
混合模型的算法框架如下:
1) 利用LightGBM提取高维组合特征(即图 2中的树型结构模型, 若某样本遍历LightGBM后到达叶节点为加粗的路径, 那么路径中的特征即为从该样本提取的组合特征, 组合特征用叶节点的索引值表示).
2) 模型初始化:将LightGBM提取高阶特征(每棵树叶节点的索引值)和低阶离散型特征同时作为输入数据, 并设置参数.
3) 将输入数据归一化, 防止溢出.
4) 对训练数据中每个样本做以下操作, 样本被形式化表示为(xi, yi).其中：xi=(xj1, xj2, …, xjm)表示样本, xj1, xj2, …, xjm表示样本的特征, 一个样本由m维特征组成；yi是二值变量, 取值为0或1, 表示真实的转化结果.计算每个样本的φ值, 公式为
|
(1) |
其中，wj, f是某个特征对某个域的一个隐向量.根据损失函数计算该样本的损失值, 损失函数的公式为
|
(2) |
计算该样本的梯度值, 梯度公式为
|
(3) |
用梯度值和初始的学习率更新FFM模型中的隐向量, 公式为
|
(4) |
其中：gφ是本次迭代所求的梯度值；gwj, ft是之前第t次迭代的梯度值.
5) 同理, 计算测试样本的损失值.
6) 重复步骤3)和4)直到迭代结束或者测试样本的损失值不再减少.
4 实验 4.1 实验准备腾讯提供的数据集是2015年9月17日至30日的日志信息, 为了模拟在线的训练和测试数据流, 实验选择17日~28日的数据作为训练数据, 30日的数据作为测试数据.数据信息可被形式化表示为D={(xi, yi)}(|D|=n, xi=Rm, yi=0或者1), 其中:xi表示一个样本, i是样本ID; n是样本数; m是特征维数; yi表示广告是否被转化, 假如用户对一条广告进行了转化操作, 则yi=1;否则广告未被转化, 则yi=0.实验选取在广告点击率和转化率预估中, 将逻辑损失(logistic loss, LL)作为评估指标, 其公式如下：
|
(5) |
其中:N是样本总数; yi是二值变量, 取值0或1, 表示第i个样本的真实结果; pi是第i个样本的预估结果.模型的LL值越低, 模型预估的准确性越高, 实验结果如表 1所示.从表中可以观察到, FFM作为单一模型使用时比LightGBM的LL值低一些, 而经过LightGBM提取高阶组合特征后的LL是最低的, 也就是预估准确率最高.
|
表 1 混合模型和单一模型的逻辑损失值比较 Table 1 Comparison of logistic loss values of the hybrid model and the single model |
在广告转化率预估系统中, 数据会随着时间的变化而变化, 那么数据的新鲜度就会影响模型对转化率预估的准确性.为了探索训练和测试天数的延迟对模型预估性能的影响, 实验将17日~28日的数据每相邻3 d作为1组, 一共分为5组训练数据, 均以30日数据作为测试数据, 分别在LightGBM+FFM和FFM上进行了实验, 实验结果如表 2所示.
|
|
表 2 延迟天数对模型逻辑损失值的影响 Table 2 Impact of the delay days on logistic loss values of the models |
从表中可以观察到, 两个模型的逻辑损失值都会随着延迟天数的增加而变大, 而一天的延迟会使逻辑损失增加0.1%左右, 所以在广告预估系统中, 需要新鲜的训练数据来保证模型的预估性能.
4.3 数据窗口在选择数据训练模型时还需要考虑数据的大小, 本文称之为数据窗口大小(data sizes).考虑到用户在下载APP之后可能过很长时间才会重新启动APP, 或者用户启动APP的行为需要广告商上报回广告系统的过程发生了延时.基于这两种情况, 如果将数据窗口设置得过小, 则本来已经被转化的广告很可能因为广告商没有及时将APP激活数据上报给广告系统, 也就是说这条广告的label本应被标注为1而实际却是0.所以数据窗口的负样本比真实要多, 造成了预估的不准确.
相反地, 数据窗口过大不仅会在等待数据过程时占用存储空间而造成浪费, 还会由于数据新鲜度的下降使模型的预测性能变低.因此, 需要在数据的新鲜度和窗口大小之间达到一个平衡.本文通过实验比较了不同数据窗口大小对预估性能的影响, 实验结果如图 3所示.
|
图 3 数据窗口大小对模型预估性能的影响 Fig.3 Impact of the data sizes on prediction accuracy |
从图 3中可以看出, 大体上数据窗口大小为78时, 两个模型的逻辑损失值最小.当数据窗口大小从8开始继续增大时, 两个模型的逻辑损失值开始变大.这是由于在数据窗口较大时, 继续增大窗口反而会使窗口中产生许多不必要的数据信息, 因此会影响预估模型的性能, 则逻辑损失值会变大.而在数据窗口较小时, 通过增大数据窗口使原本因延迟而导致窗口中负样本比实际多的情况得以解决, 所以逻辑损失值会减小.
5 优化参数当不做特殊说明时, 本节中所有实验的训练数据均选用7 d的数据量.
5.1 LightGBM模型中参数的讨论 5.1.1 迭代次数的选择通常模型训练时迭代次数越多预估的精度越高, 将模型迭代训练200次, 限制每棵树的叶子总数不超过64个, 观察逻辑损失值随迭代次数的变化.实验结果如图 4所示, 从图中可以看出, 当LightGBM模型的学习率为0.05和0.1时, 逻辑损失值随着迭代次数的增加而减小.并且迭代次数在60之前逻辑损失值下降比较明显, 在60之后下降缓慢.当学习率为0.2时, 逻辑损失值先随着迭代次数的增加而降低, 在迭代次数超过120后逻辑损失值逐渐上升, 说明出现了过拟合.
|
图 4 LightGBM模型取不同学习率时逻辑损失值随迭代次数的变化 Fig.4 Change of logistic loss values with iterations when LightGBM model takes differentlearning-rates |
LightGBM和XGBoost[9]的生长方式不同, LightGBM只要在限制的深度内达到设置的叶子总数就可以停止生长, 从而能够快速收敛.如表 3所示, 记录了XGBoost和LightGBM取不同迭代次数时训练模型所用的时间.
|
|
表 3 不同迭代次数时模型所用时间的对比 Table 3 Comparison of the time at different iteration |
从表 3中可以观察到, 相同的迭代次数, XGBoost所用的时间是LightGBM的几倍, 并且随着迭代次数的增加倍数也在增长.
5.2 FFM中参数的讨论 5.2.1 提前停止(early stopping)在很多机器学习问题中, 为了避免过拟合的出现, 会采用提前停止的方法(early stopping)[10].在FFM中用到类似early stopping的策略:将数据分成训练集和验证集, 在模型的每次迭代训练后用验证集计算损失函数值.如果损失函数值上升则记录迭代次数, 也可以按照记录的迭代次数用全部数据重新训练模型.如果损失函数值下降则继续迭代训练直到损失函数值上升.
从图 5可以观察到, FFM在经过5次迭代训练后逻辑损失达到最低值, 从第5次迭代之后随着迭代次数的增加逻辑损失值逐渐变大.随着训练次数的增加模型变得越来越复杂, 模型在训练数据集和验证集上的损失值也逐渐减小.但当模型达到一定的复杂度时, 模型在验证集上的误差反而会随之增大, 也就是出现了过拟合.所以FFM采用提早停止的方法来避免过拟合, 当然有些时候, 对于验证集最佳的迭代次数却不一定适合测试集, 这里不做过多讨论.
|
图 5 不同迭代次数对FFM模型预估性能的影响 Fig.5 Impact of different iterations on prediction performance of FFM model |
考虑到FFM模型在训练时选择多线程可能会出现不同的收敛情况.本文通过实验讨论了多线程时得到的收敛结果, 为了方便比较速度的提升情况, 将速度提升比定义为单线程所用时间和多线程所用时间的比.
从图 6中可以观察到, 最开始增加线程数能够使模型的收敛速度有明显的提升, 但当线程数增加到12之后收敛速度趋于平稳.在使用了22个线程后收敛速度稍有降低, 这是因为当多个线程同时访问内存空间时, 一个线程必须等待另一个线程访问结束后才可以继续执行, 当越来越多的线程同时执行时会加剧冲突的发生.
|
图 6 多个线程时的速度提升比 Fig.6 Speedup ratio of using multi-threading |
为了进一步验证本文提出的混合模型的有效性和泛化性, 将LightGBM+FFM在Criteo数据集和Tencent数据集上与更多模型进行了比较.实验结果如表 4所示, 可以观察到经过LightGBM提取高阶组合特征的FFM在两个数据集上都有最低的逻辑损失值.
|
|
表 4 更多模型预估结果(逻辑损失)的比较 Table 4 Comparison of more model predictions (logistic loss) |
本文提出了一种新的混合模型用于广告转化率的预估, 突破了FMM作为单一模型预估时只考虑二阶组合特征的局限性.在保留低阶特征的前提下, 通过LightGBM进行了高阶组合特征的研究, 改善了FFM的预估性能.并从数据和模型参数两个角度进行实验分析, 优化了模型.为了验证混合模型的有效性和泛化性, 在不同数据集上与其他模型进行了比较, 实验结果表明本文提出的混合模型的逻辑损失值最小, 预估结果更准确.
| [1] |
董书超.基于逻辑回归模型的广告点击率预估系统的设计与实现[D].哈尔滨: 哈尔滨工业大学, 2016.
( Dong Shu-chao.Design and implementation of click through rating system based on logistic regression model[D].Harbin: Harbin Institute of Technology, 2016. http://cdmd.cnki.com.cn/Article/CDMD-10213-1016915140.htm ) |
| [2] |
Juan Y, Zhuang Y, Chin W S, et al.Field-aware factorization machines for CTR prediction[C]//Proceedings of the 10th ACM Conference on Recommender Systems.Boston, 2016: 43-50.
|
| [3] |
Juan Y, Lefortier D, Chapelle O.Field-aware factorization machines in a real-world online advertising system[C]//Proceedings of the 26th International Conference on World Wide Web Companion.Perth, 2017: 680-688.
https://www.researchgate.net/publication/312462427_Field-aware_Factorization_Machines_in_a_Real-world_Online_Advertising_System |
| [4] |
Ling X L, Deng W W, Gu C, et al.Model ensemble for click prediction in bing search Ads[C]//Proceedings of the 26th International Conference on World Wide Web Companion.Perth, 2017: 689-698.
|
| [5] |
Pan J, Xu J, Ruiz A L, et al.Field-weighted factorization machines for click-through rate prediction in display advertising[C]//Proceedings of the 2018 World Wide Web Conference on World Wide Web.Lyon, 2018: 1349-1357.
https://arxiv.org/abs/1806.03514 |
| [6] |
Cheng H T, Koc L, Harmsen J, et al.Wide & deep learning for recommender systems[C]//Proceedings of the 1st Workshop on Deep Learning for Recommender Systems.Boston, 2016: 7-10.
https://www.researchgate.net/publication/316894922_Wide_Deep_Learning_for_Recommender_Systems |
| [7] |
Zhang W, Du T, Wang J.Deep learning over multi-field categorical data[C]//European Conference on Information Retrieval.Padua, 2016: 45-57.
https://link.springer.com/chapter/10.1007/978-3-319-30671-1_4 |
| [8] |
Ke G, Meng Q, Finley T, et al.LightGBM: a highly efficient gradient boosting decision tree[C]//Advances in Neural Information Processing Systems.Barcelona, 2017: 3149-3157.
|
| [9] |
Chen T, Guestrin C.XGBoost: a scalable tree boosting system[C]//Proceedings of the 22th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Francisco, 2016: 785-794.
https://arxiv.org/abs/1603.02754 |
| [10] |
Raskutti G, Wainwright M J, Yu B.
Early stopping and non-parametric regression:an optimal data-dependent stopping rule[J]. Journal of Machine Learning Research, 2014, 15(1): 335–366.
|