CTR点击率预估之经典模型回顾

SIGAI特约作者

张凌寒

中国科学院研究生院

研究方向：机器学习, 推荐系统

摘要

CTR(Click-through rate, 点击率)预估在工业级推荐系统、广告系统中是非常重要的一个环节, 其预估效果会直接影响推荐系统的性能. CTR预估常伴有训练数据量大、特征高度稀疏、推断性能要求高等特点, 使得算法的设计多围绕这些特点来进行. 本文旨在梳理经典CTR预估模型的演化历程, 分为如下几个小节:

1.CTR预估的典型应用场景

2.LR(Logistic Regression, 逻辑斯蒂回归)在CTR预估中的应用

3.使用FM(Factorization Machines, 因子分解机)自动进行特征组合

4.使用FFM(Field-aware Factorization Machines, 域感知因子分解机)做进一步特征组合

5.使用GBDT(Gradient Boosting Decision Tree, 梯度提升决策树)进行高阶特征组合

6.总结

关键词: 点击率预估, 推荐系统, 机器学习

CTR预估的典型应用场景

现阶段, 工业级的推荐系统常因为候选集数据量、系统响应时效等因素的影响, 需要分多个阶段完成整个推荐的流程, 具体地, 常将其分为召回与排序两大阶段. 对于具有一定规模的互联网业务而言, 其所面对的待推荐物料库(商品、视频、音乐等)通常能达到百万量级, 更大规模的业务甚至能达到千万及亿量级. 若针对某一特定的用户我们都需要对全体物料进行打分排序以给出最终推荐结果的话, 在有限的计算资源和响应时间下显然是不现实的事情. 所以, 在工业实践中, 我们通常先采用多路召回策略(协同过滤、热点、用户画像标签等)从待推荐物料库中先召回一批数据, 使数据量下降到千量级. 由于召回阶段的数据量较大, 所以要求该阶段所使用的策略和模型要足够的简单. 通过召回阶段, 我们顺利地将待排序数据量降至千量级, 此时, 我们便可以通过用户画像、物料画像、用户行为记录等数据来进行排序, 从而得到用户对每个物料的CTR预估值. 下图为Youtube在2016年的一篇文章中所展示的推荐系统架构图, 其很好地描述了召回与排序的流程[2].

Youtube视频推荐系统架构

那么, 为什么CTR预估的性能对推荐系统的总体性能起到至关重要的作用呢? 假设我们现在面对的是一个电子商城的场景, 此时, 推荐系统的结果就是用户看到的商品列表. 电子商城能获得的期望收益为

在(1)中,

为用户在曝光数据集中的CTR预估,

为用户在点击后被转化的预估, 二者再与期望价格进行相乘, 便可以得到期望收益. 由此可见, 对CTR的精确预估(CVR同理), 直接能使得期望收益进行增长, 所以CTR预估的性能直接影响了推荐系统的整体性能, 对提高营收、社区活跃度等指标起到至关重要的作用.

LR在CTR预估中的应用

在CTR预估中, 我们通常使用one-hot编码来对数据进行处理. 这种编码承袭于NLP(Natural language processing, 自然语言处理)中对词典中的词汇进行编码的方式, 其使用一个维度为词汇个数的向量来表示每一个词汇, 在该向量中, 除了对应词汇所在位置取值为1, 其余位置均取值为0. 具体地, 假设数据集

yi∈{0,1}中每个样本都由若干个不同的field(域)组成, 如uid、gender、city、weekday、brand等, 若我们共有3个样本

我们可以使用one-hot编码为

由(3)我们便得到了样本的向量化表示. 有了数据集

yi∈{0,1}的向量化表示, 对于向量

, i=1,...n我们需要使用一个CTR模型来判断其是否会被用户点击. 一个很自然的思路是, 假设数据集

,yi∈{0,1}是线性可分的, 那么我们可以使用一个线性超平面

来将yi∈{0,1}，i=1，...，n的点进行分离. 具体地, 假设我们已经得到最优的超平面参数

, 则

由(4), 我们便可以预测样本

,i=1,...,n是否会被点击了. 由(1), 我们最后希望得到的是模型对后验概率

的估计值, 所以, 我们还需要对(4)做进一步的处理. 具体地, 我们使用sigmoid函数

来将(4)的预测结果映射为一个概率分布, 即

sigmoid函数示意图

(5)即为LR模型, 其直接对后验概率分布

进行建模, 避免引入先验假设时因为假设不准确所带来的误差, 同时,sigmoid函数是任意阶可导的凸函数, 此优秀的数学性质使得大部分的数值优化方法都可以用来对其进行参数的估计. 由(5)我们可得模型的CTR预估为

虽然LR模型使用sigmoid函数来获得一个合法的后验概率分布, 但其本质上还是一个线性模型, 通过对(5)稍作调整就可以看出端倪

由(7)可以看出, 我们是使用线性模型

对样本的

进行回归和预测, 所以本质上LR模型还是一个线性模型, 我们称之为广义线性模型. 那么, 应该如何来对其参数进行求解呢? 我们使用MLE(maximum likelihood estimation, 极大似然估计)[3]来指导模型的训练, 构造似然函数

我们只需令(8)取最大值即可得最优解

不过由于数值稳定性等原因, 实践中我们会由(8)进一步整理出

我们称(9)为NLL(negative log likelihood, 负对数似然)函数, 其使用cross entropy(交叉熵)[4]来度量模型预测的后验分布与真实分布之间的差距, 通过最小化

即可获得最优解

. 得益于LR模型优秀的数学性质, 我们可以采用常用的梯度下降法、牛顿法[5]等优化算法对该问题进行求解.

使用FM自动进行特征组合

由上一节的阐述我们很容易发现使用one-hot编码与LR模型来进行CTR预估有着明显的缺陷: 1. one-hot编码带来非常稀疏的样本特征; 2. 样本集可线性分离的假设是个非常强的假设, 而事实上样本集不一定是可线性分离的; 3. 没有考虑特征之间的相关性, 这通常需要算法工程师在特征工程阶段结合业务进行手动挖掘, 非常地费时费力而不一定有好的效果. 为了解决这几个问题, 我们需要一种方案, 其能在非常稀疏的样本特征中很好地进行特征组合以挖掘特征之间的相关性并给模型引入非线性.

FM模型的提出很好的解决了这些问题. FM[6]模型通过给one-hot稀疏特征的每一维特征都学习一个稠密的k维隐向量, 再使用该隐向量来进行特征之间的两两交叉, 从而给模型引入了自动化的特征组合和非线性机制. 具体地

(10)中,x=[x1,...xn]T∈Rn为n维稀疏特征向量,v∈Rk为k维稠密隐向量,<vi,vj>=

为两个向量之间的內积. 由(10)我们可看出, FM模型的输出结果是由线性模型与特征的二阶交叉组合而成的, 所以FM模型可以看成是LR模型的一个延伸扩展. 由于采用了为每个特征都学习一个稠密隐向量的机制, 使得FM模型能很好地从稀疏的特征向量中学习那些隐含于其中的特征关联关系. 如何理解这一过程呢? 假如我们不采用这种隐向量的机制, 而是使用标量参数对特征的交叉进行直接建模, 即特征交叉部分为

, 则我们有可能会因为特征的稀疏性而没能学到某些特征之间的关联, 如特征xi,xj 从未在训练集的样本中同时出现, 那我们将无法学习到其标量参数. 而使用隐向量的机制则能很好的克服这一点, 如虽然特征xi,xj 从未在训练集的样本中同时出现, 但经常会有特征xi,xk和特征xj,xk同时出现, 那么我们就能正常地学习到特征xi的隐向量vi和特征xj的隐向量vj, 则在模型进行预测时, 我们便可以通过<vi,vj>得到其关联性, 从而克服了稀疏特征所带来的弊端.

FM模型示意图

由于我们对原始的样本进行了one-hot编码, 所以属于同一个域的多个特征在同一时刻只会有一个取值为1, 其余的均取值为0. 我们在构造属于同一个域的多个特征的隐向量时, 在数学上可以理解为使用隐向量组成的矩阵V与one-hot特征

进行乘法运算, 其中下标i表示非零位的索引, 其结果为非零位i所对应的矩阵V的列, 即

(11)中

即为k维隐向量. 隐向量的构造过程在FM模型示意图中有清晰的呈现, 这个过程本质上是将one-hot编码特征向量中的每一维都映射成Rk空间中的一个低维向量, 而后再通过向量之间的內积来获得特征之间的关联性, 从而完成特征的组合. 这种做法与通过word2vec[7]获得词语的embedding表示是一脉相承的, 所以我们也将特征的隐向量表示称为embedding.

熟悉推荐系统的同学对MF[8](Matrix factorization, 矩阵分解)类的协同过滤算法都不会感到陌生, 其典型代表有Funk SVD、SVD++等, 而核心思想都是通过对user-item评分矩阵进行分解, 分别得到user和item的隐向量所组成的矩阵, 再使用对应的隐向量进行內积运算, 来获得user对item的评分, 从而给出推荐结果. 以Funk SVD为例, 具体地

其中,

是user-item标注评分矩阵,

是user-item预测评分矩阵,

是user隐向量矩阵,

是item隐向量矩阵. 当我们想获得user u对item i的评分时, 只要将对应的隐向量进行內积运算即可

如果我们在训练FM模型时, 训练数据只由user的id和item的id组成, 则通过训练我们分别得到了user与item的隐向量, 而后FM模型在预测时就会使用对应的user与item的隐向量进行內积获得预测结果, 这个过程与MF进行预测的过程是一致的, 所以我们可以认为MF模型是训练数据只有user id和item id的FM模型, 即MF模型是FM模型的一种特殊情况.

由(10)可知, FM模型的时间复杂度为O(kn2), 事实上, 这个复杂度可经过对FM模型进行化简进一步降为O(kn, 具体地

由(14)我们将FM模型的时间复杂度降为线性时间复杂度. 由(10)(14)可进一步整理出

训练FM模型时可采用SGD(Stochastic Gradient Descent, 梯度下降法)进行参数的求解, 由(15)可得函数对参数的梯度为

使用FFM做进一步特征组合

FFM模型在FM模型的基础上引入了field(域)的概念, 其把拥有共同性质的特征都组织到一个field中, 与FM模型不同的是, FFM模型的每一维特征xi会针对不同的field fj分别训练一个隐向量vifj, 而在预测阶段, 也会根据所组合的特征所在的field不同而使用不用的隐向量来参与计算, 具体地

因此, 在FFM模型中, 隐向量的使用不仅与特征相关, 还与特征所在的field相关. 若特征向量x的维度为n, 且划分为f个field, 则FFM模型总共需要学习nf个隐向量. FM模型可以看成是所有特征都在同一个field中的FFM模型, 所以FM模型是FFM模型的一种特殊情况. 由于FFM模型的表达式无法进行化简, 所以时间复杂度还是O(kn2), 在特征维度较大且数据量较多时, FFM模型的运算性能将远不如FM模型.

使用GBDT进行高阶特征组合

由前述章节我们发现, FM、FFM模型只利用了二阶特征组合, 并没有使用更高阶的特征组合. 当然, 我们也可以将它们的特征组合扩展到更高阶, 但模型的时间复杂度就会呈指数增长了. 那有什么方案能高效地进行高阶特征组合呢? 答案就是利用GBDT. GBDT是典型的集成学习代表, 我们就从集成学习开始, 简要地介绍其模型原理. 集成学习是机器学习算法中地位非常重要的一类算法, 其拥有理论基础扎实、易扩展、可解释性强等特点, 其核心思想是, 使用弱学习器(如线性模型、决策树等)进行加权求和, 从而产生性能较为强大的强学习器.具体的, 假设我们有数据集D={(xi,yi)}, i=1,...n, 集成学习希望使用如下的模型对数据集D进行拟合

其中, 系数αm为各个弱学习器的权重,

, m=1,...M为弱学习器. 由(18)来进行如下的拟合过程

即可得到强学习器

. 而GBDT是集成学习的一个典型代表, 其以boosting为理论基础, 使用C&RT决策树作为训练弱学习器hm的模型. 具体地, 其算法流程如下

算法(20)提供了一个GBDT的框架, 其可以拥有多种不同变体且细节相异的实现方式.

Facebook[9]提出了一种使用GBDT解决LR模型特征发现和高阶特征组合的方案. 使用GBDT的决策路径作为LR模型的特征输入本身就是一种天然的特征发现与特征组合的过程. 使用GBDT进行特征发现和特征组合的核心思想是: 样本xi,i=1...n经过GBDT每棵树的路径都作为LR的一维特征, 以期达到路径上所有特征进行组合的效果. 使用已有的特征训练GBDT模型, 然后利用GBDT模型来构造新的特征向量. 新特征向量由0/1组成, 其每个特征对应GBDT模型树的一个叶子节点, 当样本落在某个叶子节点上时, 该位特征取值为1, 否则取值为0. 新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和.

使用GBDT+LR进行CTR预估示意图

如上图所示, 图中的GBDT模型由两棵树组成, 共5个叶子节点, 故x经由GBDT模型处理后将生成5维的新特征向量. 假设其分别落在第一棵树的2号叶子节点和第二棵树的1号叶子节点, 则生成的新特征向量为[0,1,0,1,0]T, 而后再使用LR模型进行后续操作. 论文[9]中树的数量达到500棵, 每棵树的叶子节点数不超过12.

使用GBDT代替人工的特征发现和特征组合在工业级的推荐系统中已经得到广泛的应用, 其表现出了卓越的性能. 另外, 除了与LR进行糅合, 还有一些工作尝试了GBDT+FM, GBDT+FFM等, 总的来说都不逊色于人工的特征.

有关GBDT更加详细的论述请参考:

Linghan Zhang：Gradient Boosting梯度提升-GBDT与XGBoost解析及应用zhuanlan.zhihu.com

总结

本文对CTR点击率预估的经典模型进行了梳理和回顾, 着重分析了不同模型的原理与异同. 许多现代的深度学习点击率预估模型都是以上述的经典模型为基础演变而来, 厘清经典模型的发展脉络, 对掌握和使用深度学习点击率预估模型将有很大的益处.

引用

[1] Zhang, J. (2019). 推荐系统召回四模型之：全能的FM模型.Retrieved from https://zhuanlan.zhihu.com/p/58160982

[2] Covington, P., Adams, J., & Sargin, E. (2016). Deep Neural Networks for YouTube Recommendations.Retrieved from https://ai.google/research/pubs/pub45530

[3] Wikipedia contributors. (2019, May 1). Maximum likelihood estimation. InWikipedia, The Free Encyclopedia. Retrieved 04:00, May 17,2019,from https://en.wikipedia.org/w/index.php?title=Maximum_likelihood_estimation&oldid=895026573

[4] Wikipedia contributors. (2019, May 15). Cross entropy. InWikipedia, The Free Encyclopedia. Retrieved 06:45, May 17, 2019, fromhttps://en.wikipedia.org/w/index.php?title=Cross_entropy&oldid=897193273

[5] Wikipedia contributors. (2019, April 18). Newton's method. InWikipedia, The Free Encyclopedia. Retrieved 03:42, April 21, 2019, fromhttps://en.wikipedia.org/w/index.php?title=Newton%27s_method&oldid=892955071

[6] Rendle, S. (2010). Factorization Machines. [online] Csie.ntu.edu.tw.Available at: https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf [Accessed 17 May 2019].

[7] Wikipedia contributors. (2019, April 8). Word2vec. InWikipedia,The Free Encyclopedia. Retrieved 13:08,May 18, 2019, fromhttps://en.wikipedia.org/w/index.php?title=Word2vec&oldid=891480412

[8] Wikipedia contributors. (2019, February 18). Matrix factorization (recommender systems). InWikipedia, The Free Encyclopedia. Retrieved 13:59, May 18, 2019, fromhttps://en.wikipedia.org/w/index.php?title=Matrix_factorization_(recommender_systems)&oldid=883976625

[9] He, X. and Pan, J. (2014).Practical Lessons from Predicting Clicks on Ads at Facebook. [online] Facebook Research. Available at:https://research.fb.com/publications/practical-lessons-from-predicting-clicks-on-ads-at-facebook/[Accessed 22 Apr. 2019].

本文为SIGAI原创