hkshao 2018-08-20
1.引言
点击率(click-through rate, CTR)是互联网公司进行流量分配的核心依据之一。比如互联网广告平台,为了精细化权衡和保障用户、广告、平台三方的利益,准确的CTR预估是不可或缺的。CTR预估技术从传统的逻辑回归,到近两年大火的深度学习,新的算法层出不穷:DeepFM, NFM, DIN, AFM, DCN……
然而,相关的综述文章不少,但碎片罗列的居多,模型之间内在的联系和演化思路如何揭示?怎样才能迅速get到新模型的创新点和适用场景,快速提高新论文速度,节约理解、复现模型的成本?这些都是亟待解决的问题。
我们认为,从FM及其与神经网络的结合出发,能够迅速贯穿很多深度学习CTR预估网络的思路,从而更好地理解和应用模型。
2.本文的思路与方法
3.FM:降维版本的特征二阶组合
CTR预估本质是一个二分类问题,以移动端展示广告推荐为例,依据日志中的用户侧的信息(比如年龄,性别,国籍,手机上安装的app列表)、广告侧的信息(广告id,广告类别,广告标题等)、上下文侧信息(渠道id等),去建模预测用户是否会点击该广告。
FM出现之前的传统的处理方法是人工特征工程加上线性模型(如逻辑回归Logistic Regression)。为了提高模型效果,关键技术是找到到用户点击行为背后隐含的特征组合。如男性、大学生用户往往会点击游戏类广告,因此“男性且是大学生且是游戏类”的特征组合就是一个关键特征。但这本质仍是线性模型,其假设函数表示成内积形式一般为:ylinear=σ(⟨w→,x→⟩)
其中x→为特征向量,w→为权重向量,σ()为sigmoid函数。
但是人工进行特征组合通常会存在诸多困难,如特征爆炸、特征难以被识别、组合特征难以设计等。为了让模型自动地考虑特征之间的二阶组合信息,线性模型推广为二阶多项式(2d−Polynomial
2d−Polynomial)模型:ypoly=σ(⟨w→,x→⟩+∑i=1n∑j=1nwij⋅xi⋅xj)
其实就是对特征两两相乘(组合)构成新特征(离散化之后其实就是“且”操作),并对每个新特征分配独立的权重,通过机器学习来自动得到这些权重。将其写成矩阵形式为:ypoly=σ(w→T⋅x→+x→T⋅W(2)⋅x→)
其中W(2)为二阶特征组合的权重矩阵,是对称矩阵。而这个矩阵参数非常多,为O(n2)。为了降低该矩阵的维度,可以将其因子分解(Factorization)为两个低维(比如n∗k)矩阵的相乘。则此时W矩阵的参数就大幅降低,为O(nk)。公式如下W(2)=WT⋅W
这就是Rendle等在2010年提出因子分解机(Factorization Machines,FM)的名字的由来。FM的矩阵形式公式如下:yFM=σ(w→T⋅x→+x→T⋅WT⋅W⋅x→)
将其写成内积的形式:yFM=σ(⟨w→,x→⟩+⟨W⋅x→,W⋅x→⟩)利用⟨∑i=1nai→,∑i=1nai→⟩=∑i=1n∑j=1n⟨ai→,aj→⟩,可以将上式进一步改写成求和式的形式: yFM=σ(⟨w→,x→⟩+∑i=1n∑j=1n⟨xi⋅v→i,xj⋅v→j⟩)
其中vi→向量是矩阵W的第i列。为了去除重复项与特征平方项,上式可以进一步改写成更为常见的FM公式: yFM=σ(⟨w→,x→⟩+∑i=1n∑j=i+1n⟨v→i,v→j⟩xi⋅xj)
对比二阶多项式模型,FM模型中特征两两相乘(组合)的权重是相互不独立的,它是一种参数较少但表达力强的模型。此处附上FM的TensorFlow代码实现,完整数据和代码请参考网盘。注意FM通过内积进行无重复项与特征平方项的特征组合过程使用了一个小trick,就是: ∑i=1n∑j=i+1nxixj=1/2×[(∑i=1nxi)2−∑i=1nxi2]
4.用神经网络的视角看FM:嵌入后再进行内积
我们观察FM公式的矩阵内积形式:yFM=σ(⟨w→,x→⟩+⟨W⋅x→,W⋅x→⟩)
发现W·x→部分就是将离散系数特征通过矩阵乘法降维成一个低维稠密向量。这个过程对神经网络来说就叫做嵌入(embedding)。所以用神经网络视角来看:
5.FM的实际应用:考虑领域信息
广告点击率预估模型中的特征以分领域的离散特征为主,如:广告类别、用户职业、手机APP列表等。由于连续特征比较好处理,为了简化起见,本文只考虑同时存在不同领域的离散特征的情形。处理离散特征的常见方法是通过独热(one-hot)编码转换为一系列二值特征向量。然后将这些高维稀疏特征通过嵌入(embedding)转换为低维连续特征。前面已经说明FM中间的一个核心步骤就是嵌入,但这个嵌入过程没有考虑领域信息。这使得同领域内的特征也被当做不同领域特征进行两两组合了。
其实可以将特征具有领域关系的特点作为先验知识加入到神经网络的设计中去:同领域的特征嵌入后直接求和作为一个整体嵌入向量,进而与其他领域的整体嵌入向量进行两两组合。而这个先嵌入后求和的过程,就是一个单领域的小离散特征向量乘以矩阵的过程。此时FM的过程变为:对不同领域的离散特征分别进行嵌入,之后再进行二阶特征的向量内积。其计算图图如下所示:
这样考虑其实是给FM增加了一个正则:考虑了领域内的信息的相似性。而且还有一个附加的好处,这些嵌入后的同领域特征可以拼接起来作为更深的神经网络的输入,达到降维的目的。接下来我们将反复看到这种处理方式。
此处需要注意,这与“基于领域的因子分解机”(Field-aware Factorization Machines,FFM)有区别。FFM也是FM的另一种变体,也考虑了领域信息。但其不同点是同一个特征与不同领域进行特征组合时,其对应的嵌入向量是不同的。本文不考虑FFM的作用机制。
经过这些改进的FM终究还是浅层网络,它的表现力仍然有限。为了增加模型的表现力(model capacity),一个自然的想法就是将该浅层网络不断“深化”。6.embedding+MLP:深度学习CTR预估的通用框架
embedding+MLP是对于分领域离散特征进行深度学习CTR预估的通用框架。深度学习在特征组合挖掘(特征学习)方面具有很大的优势。比如以CNN为代表的深度网络主要用于图像、语音等稠密特征上的学习,以W2V、RNN为代表的深度网络主要用于文本的同质化、序列化高维稀疏特征的学习。CTR预估的主要场景是对离散且有具体领域的特征进行学习,所以其深度网络结构也不同于CNN与RNN。
具体来说, embedding+MLP的过程如下:
embedding+MLP的缺点是只学习高阶特征组合,对于低阶或者手动的特征组合不够兼容,而且参数较多,学习较困难。
7.FNN:FM与MLP的串联结合
Weinan Zhang等在2016年提出的因子分解机神经网络(Factorisation Machine supported Neural Network,FNN)将考FM与MLP进行了结合。它有着十分显著的特点:
通过观察FFN的计算图可以看出其与embedding+MLP确实非常像。不过此处省略了FNN的FM部分的线性模块。这种省略为了更好地进行两个模型的对比。接下来的计算图我们都会省略线性模块。
8.DeepFM: FM与MLP的并联结合
针对FNN需要预训练的问题,Huifeng Guo等提出了深度因子分解机模型(Deep Factorisation Machine, DeepFM, 2017)。该模型的特点是:
通过观察DeepFM的计算图可以看出红色虚线以上部分其实就是FM部分,虚线以下就是MLP部分。
9.NFM:通过逐元素乘法延迟FM的实现过程
我们再回到考虑领域信息的FM,它仍有改进的空间。因为以上这些网络的FM部分都是只进行嵌入向量的两两内积后直接求和,没有充分利用二阶特征组合的信息。Xiangnan He等在2017年提出了神经网络因子分解机(Neural Factorization Machines,NFM)对此作出了改进。其计算图如下所示:
NFM的基本特点是:
10.AFM: 对简化版NFM进行加权求和
NFM的主要创新点是在FM过程中添加了逐元素相乘的运算来增加模型的复杂度。但没有在此基础上添加更复杂的运算过程,比如对加权求和。Jun Xiao等在2017年提出了注意力因子分解模型(Attentional Factorization Machine,AFM)就是在这个方向上的改进。其计算图如下所示:
AFM的特点是:
11.PNN:通过改进向量乘法运算延迟FM的实现过程
再回到FM。既然AFM、NFM可以通过添加逐元素乘法的运算来增加模型的复杂度,那向量乘法有这么多,可否用其他的方法增加FM复杂度?答案是可以的。Huifeng Guo等在2016年提出了基于向量积的神经网络(Product-based Neural Networks,PNN)就是一个典型例子。其简化计算图如下所示:
12.DCN:高阶FM的降维实现
以上的FM推广形式,主要是对FM进行二阶特征组合。高阶特征组合是通过MLP实现的。但这两种实现方式是有很大不同的,FM更多是通过向量embedding之间的内积来实现,而MLP则是在向量embedding之后一层一层进行权重矩阵乘法实现。可否直接将FM的过程在高阶特征组合上进行推广?答案是可以的。Ruoxi Wang等在2017提出的深度与交叉神经网络(Deep & Cross Network,DCN)就是在这个方向进行改进的。DCN的计算图如下:
13.Wide&Deep: DeepFM与DCN的基础框架
开篇已经提到,本文思路有两条主线。到此为止已经将基于FM的主线介绍基本完毕。接下来将串讲从embedding+MLP自身的演进特点的CTR预估模型主线,而这条思路与我们之前的FM思路同样有千丝万缕的联系。
Google在2016年提出的宽度与深度模型(Wide&Deep)在深度学习CTR预估模型中占有非常重要的位置,它奠定了之后基于深度学习的广告点击率预估模型的框架。
Wide&Deep将深度模型与线性模型进行联合训练,二者的结果求和输出为最终点击率。其计算图如下:
14.Deep Cross: DCN由其残差网络思想进化
由K. He等提出的深度残差网络能够大大加深神经网络的深度,同时不会引起退化的问题,显著提高了模型的精度。Ying Shan等将该思路应用到广告点击率预估模型中,提出深度交叉模型(DeepCross,2016
DeepCross,2016)。Deep Cross的计算图如下:
15.DIN:对同领域历史信息引入注意力机制的MLP
以上神经网络对同领域离散特征的处理基本是将其嵌入后直接求和,这在一般情况下没太大问题。但其实可以做得更加精细。比如对于历史统计类特征。以用户历史浏览的商户id为例,假设用户历史浏览了10个商户,这些商户id的常规处理方法是作为同一个领域的特征嵌入后直接求和得到一个嵌入向量。但这10个商户只有一两个商户与当前被预测的广告所在的商户相似,其他商户关系不大。增加这两个商户在求和过程中的权重,应该能够更好地提高模型的表现力。而增加求和权重的思路就是典型的注意力机制思路。
由 Bahdanau et al. (2015) 引入的现代注意力机制,本质上是加权平均(权重是模型根据数据学习出来的),其在机器翻译上应用得非常成功。受注意力机制的启发,Guorui Zhou等在2017年提出了深度兴趣网络(Deep Interest Network,DIN)。DIN主要关注用户在同一领域的历史行为特征,如浏览了多个商家、多个商品等。DIN可以对这些特征分配不同的权重进行求和。其网络结构图如下:
16.多任务视角:信息的迁移与补充
对于数据驱动的解决方案而言,数据和模型同样重要,数据(特征)通常决定了效果的上限,各式各样的模型会以不同的方式去逼近这个上限。而所有算法应用的老司机都知道很多场景下,如果有更多的数据进行模型训练,效果一般都能显著得到提高。广告也是一样的场景,在很多电商的平台上会有很多不同场景的广告位,每个场景蕴含了用户的不同兴趣的表达,这些信息的汇总与融合可以带来最后效果的提升。但是将不同场景的数据直接进行合并用来训练(ctr/cvr)模型,结果很多时候并不是很乐观,仔细想想也是合理的,不同场景下的样本分布存在差异,直接对样本累加会影响分布导致效果负向。
而深度学习发展,使得信息的融合与应用有了更好的进展,用Multi−task
Multi−task learning(MTL)
learning(MTL)的方式可以很漂亮的解决上面提到的问题。我们不直接对样本进行累加和训练,而是像上图所示,把两个场景分为两个task,即分为两个子网络。对单个网络而言,底层的embedding层的表达受限于单场景的数据量,很可能学习不充分。而上图这样的网络结合,使得整个训练过程有了表示学习的共享(Shared Lookup Table),这种共享有助于大样本的子任务帮助小样本的子任务,使得底层的表达学习更加充分。 DeepFM和DCN也用到了这个思路!只是它们是对同一任务的不同模型进行结合,而多任务学习是对不同任务的不同模型进行结合。而且,我们可以玩得更加复杂。
Multi-task learning(MTL)整个结构的上层的不同的task的子网络是不一样的,这样每个子网络可以各自去拟合自己task对应的概念分布。并且,取决于问题与场景的相似性和复杂度,可以把底层的表达学习,从简单的共享embedding到共享一些层次的表达。极端的情况是我们可以直接共享所有的表达学习(representation learning)部分,而只接不同的网络head来完成不一样的任务。这样带来的另外一个好处是,不同的task可以共享一部分计算,从而实现计算的加速。
值得一提的另一篇paper是阿里妈妈团队提出的“完整空间多任务模型”(Entire Space Multi-Task Model,ESMM),也是很典型的多任务学习和信息补充思路,这篇paper解决的问题不是ctr(点击率)预估而是cvr(转化率)预估,传统CVR预估模型会有比较明显的样本选择偏差(sample selection bias)和训练数据过于稀疏(data sparsity )的问题,而ESMM模型利用用户行为序列数据,在完整的样本数据空间同时学习点击率和转化率(post-view clickthrough&conversion rate,CTCVR),在一定程度上解决了这个问题。
在电商的场景下,用户的决策过程很可能是这样的,在观察到系统展现的推荐商品列表后,点击自己感兴趣的商品,进而产生购买行为。所以用户行为遵循这样一个决策顺序:impression → click → conversion。CVR模型旨在预估用户在观察到曝光商品进而点击到商品详情页之后购买此商品的概率,即pCVR = p(conversion|click,impression)。
预估点击率pCTR,预估点击下单率pCVR和预估点击与下单率pCTCVR关系如下。
传统的CVR预估任务通常采用类似于CTR预估的技术进行建模。但是不同于CTR预估任务的是,这个场景面临一些特有的挑战:1) 样本选择偏差;2) 训练数据稀疏;3) 延迟反馈等。
ESMM模型提出了下述的网络结构进行问题建模
17.各种模型的对比和总结
前面介绍了各种基于深度学习的广告点击率预估算法模型,针对不同的问题、基于不同的思路,不同的模型有各自的特点。各个模型具体关系比较如下表1所示:
表 1. 各模型对比
Embedding+MLPFMAttentionResnetWide&Deep√××FNN√√×DeepFM√√×NFM√√×DIN√×√AFM×√√Deep Cross√××DCN√√×
本文从开篇就说明这些模型推演的核心思路是“通过设计网络结构进行组合特征的挖掘”,其在各个模型的实现方式如下:
当然,广告点击率预估深度学习模型还有很多,比如Jie Zhu提出的基于决策树的神经网络(Deep Embedding Forest)将深度学习与树型模型结合起来。如果数据特征存在图像或者大量文本相关特征,传统的卷积神经网络、循环神经网络均可以结合到广告点击率预估的场景中。各个深度模型都有相应的特点,限于篇幅,我们就不再赘述了。
18.后记
目前深度学习的算法层出不穷,看论文确实有些应接不暇。我们的经验有两点:要有充分的生产实践经验,同时要有扎实的算法理论基础。很多论文的亮点其实是来自于实际做工程的经验。也辛亏笔者一直都在生产一线并带领算法团队进行工程研发(当然也因此荒废了近2年的博客,T△T ),积淀了一些特征工程、模型训练的经验,才勉强跟得上新论文。比如DIN“对用户侧的某领域历史特征基于广告侧的同领域特征进行加权求和”的思想,其实与传统机器学习对强业务相关特征进行针对性特征组合的特征工程思路比较相似。另一方面,对深度学习的经典、前沿方法的熟悉也很重要。从前面我们的串讲也能够看出,CTR预估作为一个业务特点很强的场景,在应用深度学习的道路上,也充分借鉴了注意力机制、残差网络、联合训练、多任务学习等经典的深度学习方法。了解博主的朋友也知道我们一直推崇理论与实践相结合的思路,我们自身对这条经验也非常受用。当然,计算广告是一个很深的领域,自己研究尚浅,串讲难免存在纰漏。欢迎大家指出问题,共同交流学习。
参考文献