Bengxy
Little steps lead to great distances.
CTR预估模型发展历程
2018-10-16 Leave a comment

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这里不多做介绍,优化目标大家都熟悉,比如简单的线性分类问题是:

$$ \hat y = w_0 + \sum_{i=1}^d w_i *x_i $$

其中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相比,多了第三项

$$ \hat y = w_0 + \sum_{i=1}^d w_i *x_i + \sum_{i=1}^d \sum_{j=i+1}^d w_{ij}x_ix_j$$

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

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

Lv2 阶段 - FM时期

FM

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

$$w_{ij} = \vec v_i * \vec v_j $$

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

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

$$ W = {w_{ij}} = V^TV$$

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

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

$$ \hat y = w_0 + \sum_{i=1}^d w_i *x_i + \sum_{i=1}^d \sum_{j=i+1}^d \vec v_i \vec v_j x_ix_j $$

重要的是,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 = (w_0, \vec z_1, \vec z_2, …, \vec z_n)$$

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

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

$$ \vec z_i = (w_i, v_i^1, v_i^2, …, v_i^k) = (w_i, \vec v_i) $$

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

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

PNN

image-20181022160532040

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

所以他的输入写为:

$$ \vec z = (w_0, \vec z_1, \vec z_2, …, \vec z_n, crossarray) $$

另外,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的主要输入是交叉特征, 用于记忆特征组合(共同出现)的频率。

$$cross : z_i = cross(x_p, x_q) $$

$$Wide: \hat y_{wide} = \phi_{LR} (\vec z_i)$$

$$Deep:\hat y_{deep} = \phi_{DNN}(\vec x)$$

所以WDL写作

$$ \hat y = sigmoid ( \phi_{LR} , \phi_{DNN}) $$

DeepFM

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

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

所以DeepFM写作

$$ \hat y = sigmoid ( \phi_{FM} , \phi_{DNN}) $$

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

本文作者:Bengxy

本文采用署名-非商业性使用 4.0 国际 (CC BY-NC 4.0)协议

本文链接:http://blog.bengxy.com/posts/d8c57fce/

CTR Machine Learning Rank