排序策略演进梳理

排序策略

Posted by weber on March 2, 2020

排序环节是推荐系统最关键,也是最具有技术含量的部分,目前大多数推荐技术其实都聚焦在这块。

在推荐、搜索、广告等领域,CTR(click-through rate)预估是一项非常核心的技术,这里引用阿里妈妈资深算法专家朱小强大佬的一句话:“它(CTR预估)是镶嵌在互联网技术上的明珠”。ctr预估的相关模型主要就是应用在排序中。本文就经典ctr预估模型进行梳理,说明排序模型的发展。

image-20200330125721611

1. LR(2010)

Logistic Regression是每一位算法工程师再也熟悉不过的基本算法之一了,毫不夸张地说,LR作为最经典的统计学习算法几乎统治了早期工业机器学习时代。

在早期的CTR预估中,算法工程师们通过手动设计交叉特征以及特征离散化等方式,赋予LR这样的线性模型对数据集的非线性学习能力,高维离散特征+手动交叉特征构成了CTR预估的基础特征。LR在工程上易于大规模并行化训练恰恰适应了这个时代的要求。

模型结构: 优势:

  • 模型简单,具备一定的可解释性;
  • 设计时间复杂度低;
  • 工程上可以大规模的并行化;

缺点:

  • 大量的人工特征工程;
  • 无法学习训练集中没有出现的交叉特征;

2. 自动化特征工程 - Facebook GBDT+LR(2014)

Facebook在2014年提出了GBDT+LR的组合模型来进行CTR预估,其本质上是通过Boosting Tree模型本身的特征组合能力来替代原先算法工程师们手动组合特征的过程。

GBDT等这类Boosting Tree模型本身具备了特征筛选能力(每次分裂选取增益最大的分裂特征与分裂点)以及高阶特征组合能力(树模型天然优势),因此通过GBDT来自动生成特征向量就成了一个非常自然的思路。注意这里虽然是两个模型的组合,但实际并非是端到端的模型,而是两阶段的、解耦的,即先通过GBDT训练得到特征向量后,再作为下游LR的输入,LR的在训练过程中并不会对GBDT进行更新。

img

模型结构:

通过GBDT训练模型,得到组合的特征向量。例如训练了两棵树,每棵树有5个叶子结点,对于某个特定样本来说,落在了第一棵树的第3个结点,此时我们可以得到向量 [0,0,1,0,0];落在第二棵树的第4个结点,此时的到向量[0,0,0,1,0] ;那么最终通过concat所有树的向量,得到这个样本的最终向量 [0,0,1,0,0,0,0,0,1,0]。将这个向量作为下游LR模型的inputs,进行训练。

优势:

  • 特征工程自动化;

缺点:

  • 两阶段的、非端到端的模型;
  • CTR预估场景涉及到大量高维稀疏特征,树模型并不适合处理(因此实际上会将dense特征或者低维的离散特征给GBDT,剩余高维稀疏特征在LR阶段进行训练);
  • GBDT模型本身比较复杂,无法做到online learning,模型对数据的感知相对较滞后(必须提高离线模型的更新频率)

3. FM及其变体

3.1 Factorization Machines (2010)

FM是在2010年提出的一种可以学习二阶特征交叉的模型,通过在原先线性模型的基础上,枚举了所有特征的二阶交叉信息后融入模型,提高了模型的表达能力。但不同的是,模型在二阶交叉信息的权重学习上,采用了隐向量内积(也可看做embedding)的方式进行学习。

模型结构: image-20200330131244592

FM与LR:

在LR中,一般是通过手动构造交叉特征后,喂给模型进行训练,例如我们构造性别与广告类别的交叉特征 xi: (gender=’女’ & ad_category=’美妆’),此时我们会针对这个交叉特征学习一个参数 wi 。但是在LR中,参数梯度更新公式与该特征xi的取值关系密切: 如果 xi 为0,即一旦两个特征只要有一个取0,参数 wi 不能得到有效更新;除此之外,对于训练集中没有出现过的交叉特征,也没办法学习这类权重,泛化性能不够好。

在FM中,通过将特征隐射到k维空间求内积的方式,打破了交叉特征权重间的隔离性,使得特征权重的学习不再互相独立。

优势:

  • 可以有效处理稀疏场景下的特征学习;
  • 具有线性时间复杂度(化简思路: ab=1/2[(a+b)^2-(a^2+b^2)])
  • 对训练集中未出现的交叉特征信息也可进行泛化;

缺点:

  • 仅枚举了所有特征的二阶交叉信息,没有考虑高阶特征的信息

3.2 Field-aware Factorization Machines(2015)

FFM(Field-aware Factorization Machine)是Yuchin Juan等人在2015年的比赛中提出的一种对FM改进算法,主要是引入了field概念,即认为每个feature对于不同field的交叉都有不同的特征表达。FFM相比于FM的计算时间复杂度更高,但同时也提高了本身模型的表达能力。

3.3 Attentional Factorization Machines(2017)

AFM全称 Attentional Factorization Machines,顾名思义就是引入Attention机制的FM模型。我们知道FM模型枚举了所有的二阶交叉特征(second-order interactions),实际上有一些交叉特征可能与我们的预估目标关联性不是很大;AFM就是通过Attention机制来学习不同二阶交叉特征的重要性。

举例来说,在预估用户是否会点击广告时,我们假设有用户性别、广告版位尺寸大小、广告类型三个特征,分别对应三个embedding: v1 ,v2 ,v3 ,对于用户“是否点击”这一目标 y 来说,显然性别与尺寸大小的交叉特征对于 y 的相关度不大,但性别与广告类型的交叉特征(如gender=女性&category=美妆)就会与 y 更加相关,重要性应该要高于性别与尺寸大小的交叉;

模型结构:

image-20200323092237492

其中,$\alpha_{ij}=\frac{\exp(e_{ij})}{\sum_{i,j}\exp(e_{ij})}$,$e_{ij}=h^TReLU(W(v_i \odot v_j )x_ix_j + b)$

优点:

  1. 引入attention机制赋予不同交叉特征不同的重要程度,增加了一定可解释性。

缺点:

  1. 仍然是浅层模型,没有学习到高阶的特征。

4. Embedding + MLP 浅层改造

4.1 FNN(2016)

FNN(Factorization Machine supported Neural Network)是2016年提出的方法。使用 FM 预训练的 embedding 作为 MLP 的输入。本质上也是二阶段模型,与 GBDT+LR 一脉相承。

FNN

FNN本身在结构上并不复杂,如上图所示,就是将FM预训练好的Embedding向量直接喂给下游的DNN模型,让DNN来进行更高阶交叉信息的学习。(如果不了解FM可以看上篇文章,给了FM及其实现)

优点:

  1. 离线FM预训练可以引入先验知识,同时加速训练;
  2. NN省去了学习feature embedding的步骤,计算开销低;

缺点:

  1. 非端到端,不利于online learning;
  2. FNN中只考虑了特征交叉,并没有保留低阶特征信息;

4.2 PNN(2016)

PNN是2016年提出的一种在NN中引入Product Layer的模型,其本质上和FNN类似,都属于Embedding+MLP结构。

PNN作者认为,在DNN中特征Embedding通过简单的concat或者add都不足以学习到特征之间复杂的依赖信息,因此PNN通过引入Product Layer来进行更复杂和充分的特征交叉关系的学习。PNN主要包含了IPNN和OPNN两种结构,分别对应特征之间Inner Product的交叉计算和Outer Product的交叉计算方式。

image-20200323100313143

PNN结构显示通过Embedding Lookup得到每个field的Embedding向量,接着将这些向量输入Product Layer,在Product Layer中包含了两部分,一部分是左边的 z ,就是将特征原始的Embedding向量直接保留;另一部分是右侧的 p ,即对应特征之间的product操作;可以看到PNN相比于FNN一个优势就是保留了原始的低阶embedding特征。

优势:

  1. 相较于FNN,保留了低阶embedding信息;
  2. 通过product引入了更加复杂的特征交互方式;

不足:

  1. 计算时间复杂度相对较高

4.3 NFM(2017)

NFM(Neural Factorization Machines)也是将FM与NN结合的结构,相较于FNN,NFM是端到端的模型。与PNN不同的是,将PNN中的Product Layer换成了Bi-interaction Pooling来进行特征交叉的学习。

image-20200323101510964

优点:

  1. 使用 Bi-interaction pooling 可以具备一定的特征交叉能力;

缺点:

  1. 直接进行sum pooling会损失一定的信息,可以考虑attention;

4.4 ONN(2019)

ONN(Operation-aware Neural Network)也称 NFFM,其实就是 FFM + MLP。ONN沿袭了Embedding+MLP结构。在Embedding层采用Operation-aware Embedding,可以看到对于一个feature,会得到多个embedding结果;在图中以红色虚线为分割,第一列的embedding是feature本身的embedding信息,从第二列开始往后是当前特征与第n个特征交叉所使用的embedding。这两部分concat之后接入MLP得到最后的预测结果。

优点:

  1. 引入Operation-aware,进一步增加了模型的表达能力。
  2. 同时包含了特征的一阶信息和高阶交叉信息。

不足:

  1. 复杂度相对较高

5. 双路并行的模型组合

5.1 WDL(2016)

Wide And Deep是2016年Google提出的用于Google Play app推荐业务的一种算法。其核心思想是通过结合Wide线性模型的记忆性(memorization)和Deep深度模型的泛化性(generalization)来对用户行为信息进行学习建模。

train model

优势:

  1. Wide层与Deep层互补互利,Deep层弥补Memorization层泛化性不足的问题
  2. wide和deep的joint training可以减小wide部分的model size(即只需要少数的交叉特征)
  3. 可以同时学习低阶特征交叉(wide部分)和高阶特征交叉(deep部分)

缺点:

  1. 仍需要手动设计交叉特征

5.2 DeepFM(2017)

WDL的提出算是一大革新,提出了一种双路并行的模型组合结构。WDL可以同时学习低阶和高阶特征,但缺点是无法发现交叉特征。DeepFM就应运而生。

模型结构:

DeepFM包含两部分:神经网络部分与因子分解机部分,分别负责低阶特征的提取和高阶特征的提取。这两部分共享同样的embedding输入。DeepFM的预测结果可以写为: image-20200323135157327

优点:

  1. 模型具备同时学习低阶和高阶特征的能力;
  2. 共享embedding层,共享了表达;

缺点:

  1. DNN对于高阶特征的学习仍然是隐式的;

6. 复杂的显式特征交叉网络

无论是以FNN、PNN、NFM、ONN为代表的Embedding+MLP,还是以Wide&Deep和DeepFM为代表的双路模型,基本都是通过DNN来学习高阶特征交叉信息。但DNN本身对于特征交叉是隐式的(Implicit)、bit- wise的,因此在这一阶段,以DCN、xDeepFM、AutoInt为代表的模型均把思路放在如何以Explicit的方式学习有限阶(bounded- degree)的特征交叉信息上。

6.1 DCN(2017)

image-20200323141158509

由图可以看到,分为嵌入层,Cross Net + Deep Net ,组合输出层 三部分,重点说明第二部分。

Cross Network:

交叉网络由交叉层组成,每个层具有以下公式:

优点:

  1. 显式的高阶特征交叉的能力;
  2. 结合了ResNet的思想,将原始信息再CrossNet中进行传递;

缺点:

  1. 交叉时候是bit-wise;
  2. CrossNet最终的输出有一定的局限性,CrossNet的每一层输出都是输入向量的标量倍,这种形式在一定程度上限制了模型的表达能力

6.2 xDeepFM(2018)

image-20200323144921094

如图所示,xDeepFM特别的设计之处在于:CIN模块,具体看看这一块的实现。

Compressed Interaction Network:

为了实现自动学习显式的高阶特征交互,同时使得交互发生在向量级上,文中首先提出了一种新的名为压缩交互网络(Compressed Interaction Network,简称CIN)的神经模型。

优点:

  1. xDeepFM可以同时学习到显式的高阶特征交叉(CIN)与隐式的高阶特征交叉;
  2. 在交叉特征的学习上,CIN采用了vector-wise的交叉(而不是DCN中的bit-wise交叉);

缺点:

  1. CIN在实际计算中时间复杂度过高;
  2. CIN的sum-pooling操作会损失一定的信息;

6.3 AutoInt(2019)

相比于DCN和xDeepFM采用交叉网络+DNN的双路结构,AutoInt直接采用了单路的模型结构,将原始特征Embedding之后,直接采用多层Interacting Layer进行学习(作者在论文的实验部分也列出了AutoInt+DNN的双路模型结构:AutoInt+)。

image-20200323154103237

Interacting Layer:

AutoInt中的Interacting Layer包含了两部分:Multi-head Self-Attention和ResNet部分。 作者使用了多个self-attention(multi-head self- attention)来计算不同subspaces中的特征交叉,其实就是进一步增加了模型的表达能力。采用h个multi-head之后,我们会得到h个 $\tilde e_m^{(h)}$ ,将这h个 concat起来,得到: 为了保留上一步学到的交叉信息,使用ResNet思想,使得之前学习到的信息也被更新到新的层中,:

对每个特征得到加权后的向量表示后,最终输出:

优点:

  1. AutoInt可以显示地、以vector-wise的方式地学习有限阶(bounded-degree)特征交叉信息
  2. 引入注意力机制,增加可解释性;

7. 考虑用户的行为序列

7.1 DIN(2018)

DIN的结构如图所示:EMbedding Layer -> Attention Network -> MLP

image-20200323162441625

DIN的思想:用户最终的行为只和历史行为中的部分有关,因此对历史序列中商品相关度应有区分,使用attention机制捕获ad和用户行为序列商品之间的关系。

优点:

  1. 和ad相似度搞得物品拥有更高的权重
  2. 不相关物品的相似度低

7.2 DIEN(2019)

DIEN是对DIN的改进:

DIN并没哟考虑用户的序列信息,即上一时刻的行为,往往会在一定程度下反应下一时刻的行为。

因此,DIEN使用了GRU来建模用户行为序列,在DIN基础上考虑序列信息,通过序列信息预测下一时刻的行为。

优点:

  1. 考虑了历史行为的序列信息;

7.3 DSIN(2019)

DSIN是对DIEN的进一步做出优化。

因为对用户来说,在每个会话中的行为是相近的,而在不同会话之间差别是很大的,如下图的例子:

img

模型架构:

img

1.会话分割层

将用户的点击行为按照时间排序,判断每两个行为之间的时间间隔,前后的时间间隔大于30min,就进行切分。

2.兴趣提取层

用Tansformer编码用户行为序列,简单来说就是输入一个序列,输出一个对应的embedding序列。同时引入了偏置编码(Bias encoding),实质上是对序列中位置信息的编码。

3.兴趣交互层

捕获序列的顺序关系,文中使用Bi-LSTM

4.兴趣激活层

和DIN中一样,使用attention捕捉商品相关性

总结

至此我们对于常见的CTR预估模型的演进过程与关系就讲解完毕,纵观整个过程,CTR预估模型从开始的LR,到利用树模型自动化组合特征,再发展到端到端的Embedding+MLP结构,再到如今越来越复杂的显式交叉网络,以及考虑历史行为序列等,每一次发展都是在不断提升模型对于用户行为的表达与学习能力。CTR预估不仅是一个数学优化问题,更是一个工程问题,因此如何能够以较低的计算成本,高效地提高模型表达能力将是未来需要努力的方向。

参考: https://zhuanlan.zhihu.com/p/100019681