Bengxy

CTR预估模型发展历程

字数统计: 2.3k阅读时长: 9 min
2018/10/16 Share

CTR预估在搜索、推荐、广告等业务中一直是核心算法。而特征组合(Cross Feature)是CTR模型中的重头戏。本文主要梳理了自个性化技术广泛使用以来,CTR预估中带Cross Feature的若干经典模型。

CTR - Cross Feature模型发展史

LR 时期:

  • Logistic Regression & SVM
  • Degree-2 Polynomial Mapping(Poly2) 2010年1

FM 时期:

  • FM (Factorization Machine) 2010年 2
  • FFM(Field-aware Factorization Machine) 2016年 recsys 3

Deep时期:

  • FNN(Factorization machine supported Neural Network)2016年1月4
  • WDL(Wide&Deep)2016年6月5
  • PNN(Product-based Neural Network)2016年11月6
  • DeepFM(Factorization-Machine based Neural Network)2017年7

数据的结构

我们以movielens的评分数据为例,数据图用FM论文里的图。

image-20181016161203737

CTR预估模型里,目前主流的方法是对特征做离散化,变成1-hot的编码格式。 因为在工业应用中,存在很多离群点,利用boundary、hash等方法,将连续值映射到离散值上,会极大提高模型的鲁棒性。

Lv1阶段 - LR时期

浅层模型和特征组合

在初期的LR和SVM这里不多做介绍,优化目标大家都熟悉,比如简单的线性分类问题是:

其中d是样本x的特征总数,$x_i$表示第i个特征,w是权重。

早期特征组合靠人工。比如在电影评分问题里,我们有了用户u对上架t天的电影m的评分y。我们可以额外加一个特征,叫 “u+t”,表示用户和上架时间上的关联,如果有评分是1,没有评分是0, $x_{u+t} = x_u * x_t$。

像上面示例表中A的大部分样本都是上架时间T>10的,增加显式的“T+A”特征后,我们可以认为A比较喜欢看稍微老一点、可能大家都看过,有评论的电影。

这样的缺点是,需要人工做很多特征交叉的工作,无法面面俱到。

Poly2的特征两两组合

而Poly2的做法就是枚举了学习每一种特征的组合,公式里第三项是对每一个特征两两组合,这也是poly2(degree-2)名字的由来。

和上面的LR相比,多了第三项

第三项展开后,一共 $d(d-1)/2$ 个,这种特征交叉有几个问题:

  • 如果数据中大部分的特征对预测的贡献很小,那在特征组合后,很可能带来很多无用的特征,这些就会成为噪声影响模型准确度。
  • 随着特征数的增长将以$O(d^2)$的复杂度增长,在如今动辄上百上千特征的时候不可行。

Lv2 阶段 - FM时期

FM

Factorization Machine的提出解决了这一问题,它用一个巧妙的方法,让$d^2$的特征组合变成$d$个k长度的分解向量:用两个向量的乘积表示常数:

这样把原先需要的 $d(d-1)/2$ 个权重参数用d个维度为k的向量 $v_i$ 的乘积表达,从而把参数量从平方$O(d^2)$降到了线性$O(dk)$。

其实这也等效于对特征交叉产生的权重矩阵进行矩阵分解:

其中$W$是 $dd$ 特征关系的权重矩阵,$V$是k行d列的分解结果矩阵,分解后,把 $dd$ 的信息,压缩到了 $k*d$ 的编码空间上。

新的表达式写为(和上面的Poly2相比,第三项的发生变化):

重要的是,FM隐藏了一个思想。细心的人应该已经发现, $\vec v_i$ 和特征 $x_i$ 一一对应,$\vec v_i$可以看做特征列 $x_i$的一种表达 。进一步的讲,$\vec v_i$ 是 $x_i$ 的一个embedding。 这是后面2016年以来,Deep模型和FM能够纳入一套理论框架的基础。

更深一步的讲,抛开FM,很多模型已经表明 Embedding 和 矩阵分解两者本质上是相似的,神经网络是矩阵分解的高阶形式,这块我后面会写一个专门的博客进行分析。

FM允许了特征做复杂的交叉,同时参数空间线性增长,同时,由于特征之间有依赖,理论上我们只需要在closed pair上训练就可以学到所有的两两关系(closed pair: 在pair集合上,把pair看做边,元素看做节点,通过任意一个节点,都可以经过pair集到达所有其他节点)。 比如我们有fea1,fea2,fea3三个特征,对应的我们有v1,v2,v3三个向量,我们仅需(fea1,fea2)和(fea1, fea3)的两个组合,就可以额外学到(fea2,fea3)的组合信息。

FFM

FFM在FM的基础上,引入了域(Field)的概念。

假设我们对年龄和性别做one-hot编码:

age<=30 age>30 gender=M gender=F
1 0 1 0
0 1 0 1

上文提到的FM在做特征交叉的时候,是不区分交叉的两个元素关系的。所以 特征 (age<=30) 在和其他特征做cross的时候,共用了一个 $\vec v_i$ 。

而FFM把特征划分了几种域,不同域之间的交叉,用各个域的 $\vec v_{i, field}$。

比如我们把年龄和性别作为两个域,那当 (age<=30) 和(age>30)交叉,(age<=30)用它的 $\vec v{i,age}$ 作为交叉的特征向量。 当(age<=30)和(gender=M)以及(gender=F)交叉时,用它的 $\vec v{i,gender}$ 作为交叉的特征向量。

这两种交叉使用的特征向量不会直接干扰。对特征分域之后,增加了参数空间,另外避免了特征间噪声的影响。在几个比赛中,FFM比FM取得了更好的结果。

Lv3阶段 - Deep 时期

FNN & PNN

FNN和PNN是类似的工作,两者的上层都是神经网络。主要是底层的区别,这里一并介绍。

FNN

image-20181022160504801

神经网络最底层的输入定义为

$\vec z_i$ 表示上文FFM中提到的域(Field)。即输入向量$\vec z$是各个域产出向量的拼接。

而各个域的输入又是怎么定义的呢?FNN定义

$w_i, \vec v_i$ 是上文FM里分解后的一阶、二阶权重。

看到这里就很清楚了,FNN用预训练好的FM权重值作为神经网络的输入。

PNN

image-20181022160532040

PNN在FNN的基础上,在输入层加了域之间的特征组合。上图中,product layer的p部分就是跨域的特征组合。

所以他的输入写为:

另外,PNN发在2016年11月,当时涌现了大量Embedding技术,因此PNN把底层换成了Embedding,而不是

预训练的FM。

WDL

WDL框架是谷歌提出的一个框架,算是比较另类的,他从一开始没有从FM入手,而是直接把所有的特征都进行Embedding上。

image-20181022160724147

特征的离散化方法:

  • 连续值: 按照等频或等值的boundary分界离散
  • 离散值(如item_id、user_name):hash后按照id embedding
  • 小离散值(如性别): id embedding 或 不离散

模型分为Wide和Deep两个部分。Deep是三层神经网络,用于学习特征的深层关系,Wide是一层LR,同时Wide的主要输入是交叉特征, 用于记忆特征组合(共同出现)的频率。

所以WDL写作

DeepFM

上文提到的WDL,Wide部分是LR,非常简单。

DeepFM其实主要修改了WDL结构的Wide部分,把简单的LR换成了FM的(也就是下图中的红线部分)。

所以DeepFM写作

image-20181022160845856

总结

一路过来的CTR预估,其实真正可以玩出花样来的有几个:

  • Cross Feature(特征组合):包括在可行性和时间复杂度,比如从poly2到FM;噪声鲁棒性,比如增加field的概念;从线性到非线性等等。
  • Embedding思想的运用:很早的矩阵分解,包括2010年的FM就已经蕴含了Embedding思想,具体表现为特征index对应到的那条分解向量。而这在后期神经网络出现后加以改进。
  • 精度和泛化能力的结合:神经网络需要把算法做细,因此深度的模型让各种特征值变的很敏感,而宽模型部分把频繁共现的样本记录下来,这两部分的权重又是通过sigmoid自动学习的。

参考文献

1. Training and Testing Low-degree Polynomial Data Mappings via Linear SVM
2. Factorization Machines
3. Field-aware Factorization Machines for CTR Prediction
4. Deep Learning over Multi-field Categorical Data: A Case Study on User Response Prediction
5. Product-based Neural Networks for User Response Prediction
6. Wide & Deep Learning for Recommender Systems
7. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction
CATALOG
  1. 1. CTR - Cross Feature模型发展史
  2. 2. 数据的结构
  3. 3. Lv1阶段 - LR时期
    1. 3.1. 浅层模型和特征组合
    2. 3.2. Poly2的特征两两组合
  4. 4. Lv2 阶段 - FM时期
    1. 4.1. FM
    2. 4.2. FFM
  5. 5. Lv3阶段 - Deep 时期
    1. 5.1. FNN & PNN
      1. 5.1.1. FNN
      2. 5.1.2. PNN
    2. 5.2. WDL
    3. 5.3. DeepFM
  6. 6. 总结
  7. 7. 参考文献