二十六、AutoInt[2018]

  1. 由于几个原因,CTR 预测问题非常具有挑战性:

    • 首先,输入特征是极其稀疏和高维的。

      在现实世界的应用中,相当比例的用户人口统计学和item 属性通常是离散的。为了应用监督学习,这些特征首先被转换为 one-hot embedding 向量,这很容易导致特征具有数百万的维度。面对如此稀疏的、高维的输入特征,机器学习模型很容易过拟合。

    • 其次,正如大量文献所示,高阶特征交互 feature interaction 对良好的性能至关重要。然而,寻找这种有意义的高阶组合特征在很大程度上依赖于领域专家。此外,几乎不可能手工制作出所有有意义的组合。

      有人可能会问,我们可以列举出所有可能的高阶特征,让机器学习模型选择有意义的特征。然而,枚举所有可能的高阶特征将指数级地增加输入特征的维度和稀疏度,导致更严重的模型过拟合问题。

    Factorization Machine: FM结合了多项式回归模型和因子分解技术从而建模特征交互,并在各种任务中证明了有效性。然而,受其多项式的限制,它只对低阶特征交互建模有效,而无法捕获高阶特征交互。

    最近,人们提出许多基于深度神经网络的工作从而建模高阶特征交互。具体而言,通常使用多层非线性神经网络来捕获高阶特征交互。然而,这类方法有两个局限性:

    • 首先,全连接的神经网络在学习乘性multiplicative 的特征交互方面效率低下。
    • 其次,由于这些模型是以隐式的方式学习特征交互,它们缺乏对哪些特征组合是有意义的良好解释。

    在论文 《AutoInt: Automatic Feature Interaction Learning via Self-Attentive Neural Networks》 中,作者提出了一种基于多头自注意力机制的方法。具体而言:

    • categorical 特征和 numerical 特征首先被嵌入到低维空间中,这降低了输入特征的维度,同时允许不同类型的特征通过向量运算(如求和和内积)来交互。

    • 然后,AutoInt 提出了一个新的交互层 interacting layer ,以促进不同特征之间的交互。在每个交互层内,允许每个特征与所有其他特征进行交互,并能够通过多头注意力机制自动识别相关特征以形成有意义的高阶特征。此外,多头机制将一个特征投射到多个子空间中,因此它可以在不同的子空间中捕获不同的特征交互。

      论文使用注意力机制来度量特征之间的相关性,这提供了良好的模型可解释性。

    论文贡献:

    • 论文提议研究显式学习高阶特征交互的问题,同时为该问题找到具有良好解释能力的模型。
    • 论文提出了一种基于自注意力神经网络的新方法,它可以自动学习高阶特征交互,并有效地处理大规模高维稀疏数据。
    • 论文在几个真实世界的数据集上进行了广泛的实验。在CTR 预测任务上的实验结果表明,所提出的方法不仅优于现有的 SOTA 的预测方法,而且还提供了良好的模型解释能力。
  2. 相关工作:

    • Learning Feature Interactions:学习特征交互是一个基本问题,因此在文献中得到了广泛的研究。

      • Factorization Machine: FM 用于捕获一阶特征交互和二阶特征交互,并被证明对推荐系统的许多任务是有效的。
      • Field-aware Factorization: FFM 建模不同 field 的特征之间的细粒度交互。
      • GBFMAFM 考虑了不同二阶特征交互的重要性。

      然而,所有这些方法都集中在建模低阶特征交互。最近有一些工作建模高阶特征交互:

      • NFM 将深度神经网络堆叠在二阶特征交互的输出之上,从而建模高阶特征交互。
      • PNN, FNN, DeepCrossing, Wide&Deep, DeepFM 也利用前馈神经网络来模拟高阶特征交互。

      然而,所有这些方法都是以隐式的方式学习高阶特征交互,因此缺乏良好的模型可解释性。相反,有三类工作是以显式方式学习特征交互:

      • 首先,Deep&CrossxDeepFM 分别在 bit-wise levelvector-wise level 上对特征进行外积outer product 。虽然它们进行了显式的特征交互,但要解释哪些组合是有用的并不简单。
      • 其次,一些基于树的方法结合了 embedding-based 模型和 tree-based 模型的力量,但不得不将训练过程分成多个阶段。
      • 第三,HOFM 提出了高效的高阶分解机的训练算法。然而,HOFM 需要太多的参数,只有它的低阶(通常小于 5 )形式可以实际使用。

      与现有工作不同的是,我们以端到端的方式显式地用注意力机制建模了特征交互,并通过可视化的方式探究学到的特征组合。

    • Attention and Residual Networks:我们的模型利用了深度学习文献中的最新技术:注意力机制和残差网络。

26.1 模型

  1. 定义 CTR Prediction:令 xRn 为用户 u 的特征和 item v 的特征的拼接,其中 categorical featuresone-hot encoding 来表示。点击率预测问题旨在根据特征向量 x 预测用户 u 点击item v 的概率。

  2. 针对 CTR 预测问题的一个直接的解决方案是:将 x 作为输入特征并馈入分类器,如逻辑回归。然而,由于原始特征向量 x 非常稀疏和高维,该模型将很容易过拟合。因此,最好能在低维连续空间中表示原始输入特征。

    此外,如现有文献所示,利用高阶组合特征来产生良好的预测性能是至关重要的。

  3. 定义 p 阶组合特征:给定输入特征向量 xRn ,一个 p 阶组合特征定义为 g(xi1,,xip) ,其中:每个特征来自于一个 distinct fieldp 为涉及的 feature fields 的数量,g() 是一个 non-additive 的组合函数,如乘法或外积。例如,xi1×xi2 为涉及field xi1,xi2 的二阶组合特征。

  4. 传统上,有意义的高阶组合特征是由领域专家手工制作的。然而,这非常耗费时间,而且很难推广到其他领域。此外,几乎不可能手工制作出所有有意义的高阶特征。因此,我们的目标是开发一种能够自动发现有意义的高阶组合特征的方法,同时将所有这些特征映射到低维的连续空间。

    问题定义:给定一个用于CTR 预测的输入特征向量 xRn ,我们的目标是学习 x 的低维representation ,它建模了高阶组合特征。

  5. 我们的方法的目标是:将原始稀疏的高维特征向量映射到低维空间,同时建模高阶特征交互。如下图所示:

    • 我们的方法将稀疏的特征向量 x 作为输入,然后是一个 embedding layer,将所有的特征(即 categorical 特征和数值特征)投影到同一个低维空间。

    • 接下来,我们将所有 fieldembedding 馈入一个新的交互层 interacting layer ,该层被实现为一个多头自注意力神经网络。

      对于每个交互层,高阶特征通过注意力机制进行组合,不同种类的组合可以通过多头机制进行评估,这些多头机制将特征映射到不同的子空间。

    • 最后一个交互层的输出是输入特征的低维 representation ,它建模了高阶组合特征,并进一步通过一个 sigmoid 函数来估计 CTR

    核心思想:将 Transformer Encoder Block 作用到 feature field embedding 上。

  6. Input Layer:我们首先将用户画像和 item 属性表示为一个稀疏向量,它是所有 field 的拼接:

    (1)x=[x1x2xM]

    其中:Mfeature fields 的总数;xi 为第 ifieldfeature 为向量拼接。

    如果第 ifieldcategorical 特征,则 xione-hot 向量。如果第 ifieldnumerical 特征,则 xi 为标量。如下图所示。

  7. Embedding Layer:我们用一个低维向量来表示每个 categorical 特征,即:

    (2)ei=Vixi

    其中:Vifield iembedding matrixxifield ione-hot 向量。

    很多时候,categorical 特征可以是多值的,即,xi 是一个 multi-hot 向量。因此,我们将 multi-valued feature field 表示为相应 feature embedding vectors的平均值:

    (3)ei=1qVixi

    其中:q 为样本在第 ifield 的取值的数量,xi 是它的 multi-hot 向量。

    可以用更复杂的、有效的操作来代替均值操作。

    为了允许 categorical 特征和 numerical 特征之间的交互,我们也在同一个低维特征空间中表示 numerical 特征。我们将 numerical 特征表示为:

    (4)em=vmxm

    其中: vmfield membedding 向量,xm 为一个标量。

    这里 vmfield m 的所有取值上共享。

    最终,embedding layer 的输出将是多个嵌入向量的拼接。

  8. Interacting Layer:我们采用注意力机制来确定哪些特征组合是有意义的。以特征 m 为例,我们首先定义在特定的注意头 h 下,特征 m 和特征 k 的相关性如下:

    (5)αm,k(h)=exp(ψ(h)(em,ek))l=1Mexp(ψ(h)(em,el)),ψ(h)(em,ek)=WQ(h)em,WK(h)ek

    其中:

    • ψ(h)(,) 为注意力函数,它定义了特征 mk 之间的相似性。可以通过神经网络或者简单的内积来定义注意力函数,这里我们使用内积的方式。
    • WQ(h),WK(h)Rd×d 为投影矩阵,它将原始的 embedding 空间投影到新的空间。d 为每个 field 的原始 embedding sized 为投影后的 embedding size

    然后,我们通过 αm,k(h) 所指导的所有相关特征来更新特征 m 在子空间 h 中的 representation

    (6)e~m(h)=k=1Mαm,k(h)WV(h)ek

    其中 WV(h)Rd×d 为投影矩阵。

    这其实就是标准的 Transformer Encoder Blocksoftmax(QK)V

    我们通过使用多个头来创建不同的子空间,分别学习不同的特征交互。我们收集在所有子空间学到的组合特征如下:

    (7)e~m=e~m(1)e~m(2)e~m(H)

    其中: 为拼接操作,H 为总的头数。

    为了保留先前学到的组合特征,包括原始特征(即,一阶特征),我们在网络中加入了标准的残差连接:

    (8)emRes=ReLU(e~m+WResem)

    其中 WResRdH×d 为投影矩阵。

    标准的 Transformer 中也包含残差连接。

    通过这样的交互层,每个特征的 representation em 将被更新为一个新的、高阶的 representation emRes 。我们可以将多个这样的层堆叠起来,将前一个交互层的输出作为下一个交互层的输入。通过这样做,我们可以建模任意阶次的组合特征。

    这就是标准的 Transformer Encoder Block ,将其应用到 feature field embedding 上。

  9. Output Layer:交互层的输出是一组特征向量 {emRes}m=1M 。对于最终的 CTR 预估,我们简单地将它们全部拼接起来,然后应用非线性投影:

    (9)y^=σ(w(e1Rese2ReseMRes)+b)

    其中:wRdHM 为投影向量,bbiasσ(x)=1/(1+exp(x))sigmoid 函数。

  10. 训练:损失函数为 log loss

    (10)L=1Nj=1N[yjlogy^j+(1yj)log(1y^j)]

    其中:yjground-truthy^j 为预估的 CTRN 为样本数量。

26.2 分析

  1. 建模任意阶次的组合特征:可以看到,AutoInt 是以 hierarchical 的方式学习特征交互,即从低阶交互到高阶交互,所有的低阶特征交互都由残差连接来承载。具体分析参考原始论文。

  2. 空间复杂度:O(LddH+nd) ,其中 L 为交互层的层数。

    • embedding 层的参数规模为 nd ,其中 dembedding sizen 为输入特征的维度。
    • 交互层的参数为 {WQ(h),WK(h),WV(h),WRes}L 层交互层的参数数量为 L×(3dd+dHd)
    • 输出层的参数数量为 dHM+1

    因此,总的空间复杂度为 O(LddH+nd) 。其中:L 为交互层的数量,d 为原始的 field embedding 维度,d 为投影后的 field embedding 维度,H 为投影子空间数量,n 为输入特征的维度(几乎等于所有 vocab size 的总和)。

    论文的结论是:空间复杂度几乎被交互层的参数所统治。结论不正确,实际上空间复杂度几乎是被 embedding table 所统治。

  3. 时间复杂度:O(MHd(M+d))

    • 一个 head 中,注意力权重的时间复杂度为 O(Mdd+M2d)
    • 然后,构建一个 head 中的组合特征的时间复杂度也是 O(Mdd+M2d)

    考虑有 H 个头,因此总的时间复杂度为 O(MHd(M+d)) 。其中:Mfield 数量。

26.3 实验

  1. 数据集:CriteoAvazuKDD12MovieLens-1M

    • 我们对 MovieLens-1M 进行了二元化:我们将评分小于 3 的样本视为负样本,将评分大于 3 的样本视为正样本,并删除中性样本(即评分等于 3 的样本)。

    • 我们删除不经常出现的特征(出现次数少于阈值),并将其作为一个单一的特征 "<unknown>" ,其中阈值对CriteoAvazuKDD12 数据集分别设置为 {10,5,10}

    • 由于数值特征可能有很大的方差,对机器学习算法造成伤害,我们采用 Criteo 竞赛的冠军提出的方案进行数值特征归一化:

      (11)z(x)={log2(x), if x>22, else
    • 我们随机选择 80% 的样本进行训练,并将剩下的样本随机分成大小相同的验证集和测试集。

    数据集的统计信息如下表所示。

  2. 评估指标:AUC, Logloss

  3. baseline 方法:

    • LR:仅建模原始特征的线性组合。
    • FM:使用因子化技术建模二阶特征交互。
    • AFM:通过注意力机制来区分二阶组合特征的重要性,从而扩展了 FM
    • DeepCrossing:采用带残差连接的深度全连接神经网络,以隐式的方式学习非线性的特征交互。
    • NFM:将深度神经网络堆叠在二阶特征交互层之上。通过神经网络隐式地捕获高阶特征。
    • CrossNetCrossNetDeep&Cross 的核心,它在 bit-wise level 上执行 concatenated 特征向量的外积,从而显式地建模特征交互。
    • CINCompressed Interaction Network: CINxDeepFM 模型的核心,在vector-wise level 上对堆叠的特征矩阵进行外积。
    • HOFM:提出了高效的 kernel-based 算法来训练高阶FM 。我们实现了一个三阶FM
  4. 实现细节:

    • 对于 AutoInt 和所有 baseline 方法,我们根据经验将 embedding 维度 d 设置为16batch size = 1024

    • AutoInt 有三个交互层,隐单元的数量 d=32 。在每个交互层中,注意力头的数量为 H=2

    • 为了防止过拟合,我们用网格搜索法在 {0.1 - 0.9} 范围内为 MovieLens-1M 数据集选择 dropout rate ,我们发现 dropout 对其他三个大数据集来说是没有必要的。

    • 对于 baseline 方法,我们按照他们的论文建议:

      • NFMBi-Interaction层上使用一个大小为 200 的隐藏层。
      • 对于 CNCIN ,和 AutoInt 一样,我们使用三个交互层。
      • DeepCrossing 有四个前馈层,隐单元的数量为 100 ,因为它在使用三个前馈层时表现很差。

      一旦所有的网络结构都固定下来,我们还对 baseline 方法应用网格搜索,以获得最佳的超参数。

    • 我们使用 Adam 来优化所有基于深度神经网络的模型。

  5. 模型效果:我们将 10 次不同运行的平均结果总结到下表,可以看到:

    • 探索二阶特征交互的 FMAFM 在所有的数据集上都以很大的幅度超过 LR,这表明单个特征在 CTR 预估中是不够的。

    • 一个有趣的观察是:一些捕捉高阶特征交互的模型的劣势。例如:DeepCrossingNFM 使用深度神经网络作为学习高阶特征交互的核心组件,但它们并不能保证比 FMAFM 有更大的改进。这可能是由于它们是以隐式的方式学习特征交互的。相反,CIN 显式地做到了这一点,并持续优于低阶模型。

      此外,尽管 HOFM 可以学习比 FM 更高阶的特征交互,但是 HOFMAvazu, KDD12 上的效果比 FM 更差。

    • AutoInt在四个真实世界的数据集中的三个上取得了最佳性能。在 Avazu 数据集上,CINAUC 评估中的表现比 AutoInt 好一点,但我们得到的 Logloss 更低。

      请注意,我们提出的 AutoIntDeepCrossing 共享相同的结构,除了特征交互层,这表明使用注意力机制来学习显式的组合特征是至关重要的。

  6. 模型效率:我们在下图中展示了不同算法在四个数据集上的运行时间。可以看到:

    • LR 由于其简单性而成为最高效的算法。
    • FMNFM 在运行时间方面表现相似,因为 NFM 只在二阶交互层之上堆叠了一个前馈隐藏层。
    • 在所有列出的方法中,CIN 在所有 baseline 中实现了最好的预测性能,但由于其复杂的交叉层,它要耗费更多的时间。
    • AutoInt有足够的效率,这与高效算法 DeepCrossingNFM 相当。

    我们还比较了不同模型的大小(即参数的数量),作为效率评估的另一个标准。如下表所示,与 baseline 模型中的最佳模型 CIN相比,AutoInt 的参数数量要小得多。

    综上所述,AutoInt 在所有 baseline 模型中取得了最好的性能。与最具竞争力的 baseline 模型 CIN相比,AutoInt 需要的参数要少得多,而且在在线推理过程中效率更高。

  7. 消融研究:

    • 残差结构的影响:为了证明残差单元的贡献,我们把它们从标准模型中分离出来,并保持其他结构不变。如下表所示,如果去除残差连接,所有数据集的性能都会下降。

    • 网络深度的影响:我们考虑不同交互层的数量的影响。注意,当交互层的数量为零时,意味着不考虑组合特征。结果如下图所示。

      • 如果使用一个交互层,即考虑到特征交互,在两个数据集上的性能都会大幅提高,这表明组合特征对于预测来说是非常有参考价值的。
      • 随着交互层数量的进一步增加,即高阶组合特征被考虑在内,模型的性能进一步提高。
      • 当层数达到三层时,性能变得稳定,表明增加更高阶特征对预测没有参考价值。

    • embedding 维度的影响:我们考虑不同 d 的影响。结果如下图所示。

  8. 可解释性:我们以 MovieLens-1M 数据集为例。

    • case-level:下图 (a) 展示了不同 field 的输入特征之间的相关性,这些相关性是由注意力得分得到的,其中该样本的 label = 1 。我们可以看到:AutoInt 能够识别出有意义的组合特征 <Gender=Male, Age=[18-24], MovieGenre=Action&Triller> (即红色的虚线矩形)。这是非常合理的,因为年轻男子很可能喜欢动作片和惊悚片。

      这种相关性是怎么计算的?如果是利用了 attention 矩阵,那么对于多个交互层,使用哪一层的结果?读者猜测是第一个交互层的 attention 矩阵。

    • global-level:下图 (b) 展示了不同 feature field 之间在整个数据中的平均注意力得分,从而衡量各 feature field 之间的相关性。可以看到:<Gender, Genre>, <Age, Genre>, <RequestTime, ReleaseTime>, <Gender, Age, Genre> 是强相关的(即,绿色的实心区域),这是推荐的可解释性规则。

      是考虑所有样本还是仅考虑正样本?读者猜测是仅考虑正样本。

  9. 集成隐式交互:前馈神经网络能够建模隐式的特征交互,并被广泛集成到现有的 CTR 预测方法中。为了研究集成隐式的特征交互是否能进一步提高性能,我们通将 AutoInt 与两层前馈神经网络相结合(并行集成,而不是堆叠)。我们将这个联合模型命名为 AutoInt+ ,并将其与以下算法进行比较:Wide&DeepDeepFMDeep&CrossxDeepFM

    结果如下表所示。可以看到:

    • 通过集成前馈神经网络,我们的方法在所有数据集上的性能都有所提高。这表明,集成隐式的特征交互确实提高了 AutoInt 的预测能力。

      然而,从最后两栏可以看出,与其他模型相比,性能提高的幅度相当小,表明我们的单个模型 AutoInt 是相当强大的。

    • 集成了隐式的特征交互之后,AutoInt+ 的性能超过了所有的 baseline 方法,并取得了新的 SOTA 的性能。

二十七、Fi-GNN[2019]

  1. 建模复杂的特征交互,对CTR 预测的成功起到了核心作用。FM 是一个著名的模型,它通过向量内积来建模二阶特征交互。FFM 进一步考虑了 field 信息并引入了 field-aware embedding 。然而,这些 FM-based模型只能建模二阶交互。

    最近,许多基于深度学习的模型被提出来从而学习高阶特征交互,这些模型遵循一个通用的范式:简单地拼接 field embedding 向量,并将其馈入 DNN 或其他专门设计的模型,从而学习交互。例如 FNN, NFM, Wide&Deep, DeepFM 等。然而,这些基于 DNN 的模型都是以 bit-wise 的、隐式的方式来学习高阶特征交互,这缺乏良好的模型解释。

    一些模型试图通过引入专门设计的网络来显式地学习高阶交互。例如,Deep&Cross ]引入了 Cross Network: CrossNetxDeepFM 引入了压缩交互网络 Compressed Interaction Network: CIN 。尽管如此,它们仍然不够有效和显式,因为它们仍然遵循将 feature field 组合在一起的通用范式来建模交互。简单的 unstructured combination 将不可避免地限制了灵活地、显式地建模不同 feature field 之间复杂交互的能力。

    在论文 《Fi-GNN: Modeling Feature Interactions via Graph Neural Networks for CTR Prediction》 中,作者考虑了 multi-field feature 的结构。具体来说,作者用一个名为 feature graph 的图结构来表示 multi-field feature 。直观而言,图中的每个节点对应于一个 feature field ,不同 field 可以通过边进行交互。因此,建模 feature field之间复杂交互的任务可以转化为建模 feature graph 上的节点交互的任务。为此,作者在 Graph Neural Network: GNN 的基础上设计了一个新的 Feature interaction Graph Neural Network: Fi-GNN ,它能够以灵活的、显式的方式建模复杂的节点交互(即,特征交互)。在 Fi-GNN 中,节点将通过与邻居节点交流 node state 来进行交互,并以 recurrent 的方式更新自己。

    AutoIntTransformer Encoder Block 建模 multi-field feature,而这里用 GNN 来建模 multi-field featureTransformer Encoder Block 可以视为一个简单的 GNN

    在每一个 time step 中,模型与邻居节点进行 one-hop 的交互。因此, interaction step 的数量等同于特征交互的阶次。此外,在 feature graph 中,边的权重反映了不同 feature interaction 对于 CTR 预测的重要性,而节点的权重反映了每个 feature field 对于 CTR 预测的重要性。这可以提供很好的解释。

    总的来说,论文提出的模型能够以显式的、灵活的方式建模复杂的特征交互,并提供良好的可解释性。论文贡献如下:

    • 论文指出了现有工作的局限性,即把 multi-field feature 视为 feature fieldunstructured combination 。为此,作者首次提出用图结构来表示 multi-field feature
    • 论文设计了一个新的模型 Feature interaction Graph Neural Network: Fi-GNN ,从而以更灵活的、显式的方式建模 graph-structured featurefeature field 之间的复杂交互。
    • 论文在两个真实世界的数据集上进行的广泛实验表明:所提出的方法不仅可以超越 SOTA 的方法,而且可以提供良好的模型解释。
  2. 相关工作:

    • Feature Interaction in CTR Predict:建模特征交互是 CTR 预测成功的关键,因此在文献中得到了广泛的研究。

      • LR 是一种线性方法,它只能对原始单个特征的线性组合建模一阶交互。

      • FM 通过向量内积来建模二阶特征交互。之后,FM 的不同变体也被提出:

        • Field-aware factorization machine: FFM 考虑了 field 信息并引入了 field-aware embedding
        • AFM 考虑了不同二阶特征交互的权重。

        然而,这些方法只能建模二阶交互,这是不够的。

      随着 DNN 在各个领域的成功,研究人员开始用它来学习高阶特征交互,因为它有更深的结构和非线性激活函数。一般的范式是将 field embedding 向量拼接在一起,并将其馈入 DNN 来学习高阶特征交互。

      • 《A convolutional click prediction model》 利用卷积网络建模特征交互。
      • FNN 在应用 DNN 之前,在 field embedding 上使用预训练的 FM
      • PNN 通过在 field embedding layerDNN layer 之间引入一个 product layer 来建模二阶交互和高阶交互。
      • 类似地,NFM 通过在 field embedding layerDNN layer 之间引入一个 Bi-Interaction Pooling layer 来建模二阶交互,但是随后的操作是 sum 操作,而不是像 PNN 中的拼接操作。

      另一个方向上的一些工作试图通过混合架构来联合建模二阶交互和高阶交互:Wide&DeepDeepFM 包含一个 wide 组件来建模低阶交互、一个 deep 组件来建模高阶交互。

      然而,所有这些利用 DNN 的方法都是以隐式的、 bit-wise 的方式学习高阶特征交互,因此缺乏良好的模型解释能力。 最近,一些工作试图通过专门设计的网络以显式的方式学习特征交互:

      • Deep&Cross 引入了一个在 bit-level 上对特征进行外积的 CrossNet
      • 相反,xDeepFM 引入了一个在 vector-level 对特征进行外积的 CIN

      然而,他们仍然没有解决最根本的问题,即把 field embedding 向量拼接起来。

      feature field 进行简单的 unstructured combination 将不可避免地限制了以灵活的、显式的方式建模不同 field 之间复杂交互的能力。为此,我们提出用图结构表示 multi-field feature ,每个节点代表一个 field ,不同的 feature field 可以通过边进行交互。因此,我们可以在图上建模不同 feature field 之间的灵活交互。

    • Graph Neural Network:图是一种数据结构,它对一组对象(节点)和它们的关系(边)进行建模。早期的工作通常将图结构的数据转换成序列结构的数据来处理。

      • 无监督的 DeepWalk 算法受 word2vec 的启发,用于学习基于 random walknode embedding
      • 之后,LINE 算法保留了图的一阶结构信息和二阶结构信息。
      • node2vec 引入了一个有偏的随机行走。

      然而,这些方法的计算成本很高,而且对于大型图而言也不是最优的。图形神经网络(graph neural network: GNN )就是为了解决这些问题而设计的,它是基于深度学习的方法,在 graph domain 上运行。现在已经有很多 GNN 的变种,这里我们只介绍一些有代表性的经典方法:

      • Gated Graph Neural Network: GGNN 使用 GRU 作为更新器。
      • Graph Convolutional Network: GCN 考虑了图的 spectral structure 并利用卷积聚合器。
      • GraphSAGE 考虑了空间信息,并引入了三种聚合器:mean aggregator, LSTM aggregator, Pooling aggregator
      • graph attention network: GAT 将注意力机制纳入消息传播步骤。

      由于 GNN 具有令人信服的性能和较高的可解释性,GNN 已经成为一种广泛应用的图分析方法。在这项工作中,我们提出了一个基于 GGNN 的模型 Fi-GNN 来为 CTR 预测建模特征交互。

27.1 模型

  1. 假设训练数据集由 mfieldcategorical feature 、以及表示用户点击行为的 label y{0,1} 组成。CTR 预测任务是对输入特征(包含 mfield )来预测用户点击的概率 y^

    下图是我们所提出方法的概览(m=4 ):

    • 输入的 sparse m-field feature vector 首先被映射成稀疏的 one-hot 向量,然后通过 embedding layermulti-head self-attention layer 嵌入到稠密的 field embedding 向量中。
    • 然后, field embedding 向量被表示为一个 feature graph ,其中每个节点对应于一个 feature field ,不同的 feature field 可以通过边进行交互。因此,建模交互的任务可以转换为建模 feature graph 上的节点交互。因此, feature graph 被馈入 Fi-GNN 从而建模节点交互。
    • 最后,在 Fi-GNN 的输出上应用一个 Attentional Scoring Layer来估计点击率 y^

    这里的 Multi-head Self-Attention Layer 就是单层的 AutoInt,因此,Fi-GNN 相当于是 AutoIntGNN 的堆叠。实验并没有表明 AutoInt 在这里的贡献,而且即使是 AutoInt + Fi-GNN,模型在所有数据集上的整体效果提升也不明显,因此论文价值不大。

  2. Embedding Layer:我们将每个 field 表示为一个 ont-hot encoding 向量,然后将其嵌入到一个稠密向量中,记做 field embedding 向量 。mfieldfield embedding 向量被拼接为(沿着 feature field 维度拼接):

    (12)E=[e1||e2||||em]Rm×d

    其中:eiRdfield iembedding 向量,dfield embedding 向量的维度,|| 为沿着 feature field 维度拼接。

  3. Multi-head Self-attention Layer:我们利用多头自注意力机制来捕获不同语义子空间中的 pairwise 特征交互。

    遵从 《AutoInt: Automatic Feature Interaction Learning via Self-Attentive Neural Networks》,给定 feature embedding 矩阵 E ,我们获取 feature representation ,它覆盖了 attention head i 中的 pairwise interaction

    (13)Hi=softmaxi(QKdk)VRm×diQ=EWi(Q),K=EWi(K),V=EWi(V)

    其中:Wi(Q),Wi(K),Wi(V)Rd×di 为针对 attention head i 的权重矩阵,dihead i 的维度。

    然后,我们将学到的每个 headfeature representation 结合起来,以保留每个语义子空间中的 pairwise feature interaction

    (14)H1=ReLU(H1H2Hh)Rm×d

    其中: 为拼接操作(沿着 embedding 维度),hattention head 数量,d=i=1hdi 为拼接后的 embedding 维度。

  4. Feature Graph:与以往简单地将 field embedding 向量拼接在一起并将其馈入模型中从而学习特征交互所不同的是,我们用图结构来表示 feature field 。具体而言,我们将每个输入的 multi-field feature 表示为一个 feature graph G=(N,E),其中每个节点 niN 对应一个 feature field i ,不同的 field 可以通过边进行交互,所以 |N|=m。因此,建模特征交互的任务可以转换为建模图上节点交互的任务。

    每个样本对应一张图,因此这是一个 graph-level 分类任务(二分类)。

  5. Feature Interaction Graph Neural NetworkFi-GNN 旨在以一种灵活的、显式的方式建模 feature graph 上的节点交互。在Fi-GNN 中,每个节点 ni 都关联一个 hidden state hit,图的状态由这些节点的状态组成:

    (15)Ht={h1t,h2t,,hmt}

    其中 t 表示 interaction step 。由多头自注意力层学到的 feature representation 作为图的初始状态 H1

    如下图所示,节点以循环方式进行交互并更新其状态。在每一个 interaction step 中,节点聚合邻居节点的状态信息(经过变换之后),然后根据聚合信息、以及节点历史状态通过 GRU 和残差连接来更新节点状态。

    • State Aggregation:在 interaction step t ,每个节点将聚合来自邻居节点的状态信息。具体而言,节点 ni 的聚合信息是其邻居节点的状态信息(转换之后)之和:

      (16)ait=(j,i)EAj,iWphjt1

      其中:Aj,i 为邻接矩阵 ARm×m ,它表示从 nj 指向 ni 的边 (j,i) 的权重,反映了这两个节点之间交互的重要性;Wp 是投影矩阵。

      显然,投影矩阵和邻接矩阵决定了节点之间的交互。由于每条边上的交互应该是不同的,我们的目标是建模边上的交互,这需要对每条边有一个 unique 的权重和投影矩阵。

      • 基于注意力的边权重:为了推断不同节点之间交互的重要性,我们建议通过注意力机制来学习边权重。具体而言,从节点 ninj 之间的边的权重通过它们的初始节点状态(即,field embedding 向量)来计算:

        (17)w(ni,nj)=exp(LeakyRelu(Ww[eiej]))kexp(LeakyRelu(Ww[eiek]))

        其中:WwR2d 为权重矩阵, 表示拼接操作(沿着 embedding 维度)。利用 softmax 函数进行归一化,使不同节点的权重容易比较。

        最终邻接矩阵为:

        (18)Ai,j={w(ni,nj), if ij0,else

        由于边的权重反映了不同交互的重要性,Fi-GNN 可以很好地解释输入样本的不同 feature field 之间的关系,这一点将在实验部分进一步讨论。

      • edge-wise 变换:如前所述,所有边上的固定的投影矩阵无法建模灵活的交互,对每个边进行 unique 的变换是必要的。然而,我们的图是完全图 complete graph (即,任意两个节点之间都存在边),因此包含大量的边。简单地给每条边分配一个 unique 的投影矩阵将消耗太多的参数空间和运行时间。为了减少时间和空间的复杂性,同时实现 edge-wise transformation ,我们为每个节点 ni 分配一个输出矩阵 Wouti 和一个输入矩阵 Wini 。如下图所示,当节点 ni 向节点 nj 发送其状态信息时,状态信息将首先被节点 ni 输出矩阵 Wouti 转换,然后在 nj 接收之前被节点 nj 的输入矩阵 Wini 转换。因此,从节点 ninj 的边 (i,j) 上的投影矩阵可以写作:

        (19)Wpij=WinjWouti

        因此聚合信息 ait 可以重写为:

        (20)ait=(j,i)EAj,iWiniWoutjhjt1

        这样一来,参数的数量与节点的数量成正比,而不是与边的数量成正比,这就大大降低了空间复杂性和时间复杂性,同时也实现了 edge-wise interaction

    • State Update :聚合状态信息之后,节点将通过 GRU 和残差连接来更新状态向量。

      • 通过 GRU 进行状态更新:根据传统的 GGNN ,节点 ni 的状态向量是根据节点 ni 的聚合状态信息、以及节点在上一个 step 的状态通过 GRU 更新的:

        (21)hit=GRU(hit1,ait)
      • 通过残差连接进行状态更新:我们引入了额外的残差连接(来自初始状态),与 GRU 一起更新节点状态,这可以促进低阶特征重用和梯度反向传播:

        (22)hit=GRU(hit1,ait)+hi1

        注意,这里是 hi1 的残差连接,而不是 hit1

  6. Attentional Scoring Layer:经过 Tpropagation step 之后,我们得到了 final node state

    (23)HT={h1T,h2T,,hmT}

    由于节点已经与它们的 T 阶邻居交互过,因此 Fi-GNN 建模了 T 阶特征交互。我们需要一个 graph-level output 来预测 CTR

    我们分别对每个 fieldfinal state 预测一个得分,并通过注意力机制将它们相加,这个注意力机制衡量它们对整体预测的影响。正式地,每个节点 ni 的预测得分、以及它的 attentional node weight 可以通过两个 MLP 分别得到:

    (24)y^i=MLP1(hiT),ai=MLP2(hiT)

    整体预测是所有节点的预测的加权和:

    (25)y^=i=1maiy^i
  7. 训练:损失函数为 logloss,即:

    (26)L=1Ni=1N(yilogy^i+(1yi)log(1y^i))

    其中:N 为总的训练样本数量;yi 为第 i 个训练样本的 labely^i 为第 i 个训练样本的预测 CTR

    我们采用 RMSProp 优化器。此外,为了平衡正负样本比例,在训练过程中,对于每个 batch 我们随机选择相同数量的正样本和负样本。

27.2 实验

  1. 数据集:Criteo, Avazu 。对于这两个数据集:

    • 我们移除了低频特征,并将低频特征替换为 "<unknown>" 。频次阈值分别为:Criteo 数据集为 10Avazu 数据集为 5 。即出现频次低于该阈值则移除。

    • 由于数值特征可能具有较大的方差,因此我们进行对数变换:

      (27)z={log2(x), if x>2x, else 

      这是由 Criteo 竞赛的获胜者提出的。

    • 数据集以 8:1:1 的比例随机拆分为训练集、验证集、测试集。

    数据集的统计信息如下表所示。

  2. 评估指标:AUC, LogLoss, Relative Improvement (RI)

    应该注意的是,对于真实世界的 CTR 任务来说,AUC 方面的微小改进被认为是显著的。为了估计我们的模型相对于 baseline 模型的相对改进,我们在此测量 RI-AUCRI-Logloss

    (28)RI-X=|X(model)X(base)|X(base)×100%

    其中 XAUCLogLoss

  3. baseline 方法:

    • LR:通过原始特征的线性组合来建模一阶特征交互。
    • FM:通过 field embedding 向量的内积来建模二阶特征交互。
    • AFM:是 FM 的一个扩展,利用注意力机制考虑不同二阶特征交互的权重。
    • DeepCrossing:利用具有残差连接的 DNN 以隐式的方式学习高阶特征交互。
    • NFM:利用 Bi-Interaction Pooling layer 来建模二阶特征交互,然后将拼接的二阶组合特征馈入 DNN 来建模高阶特征交互。
    • CrossNet(Deep&Cross):是 Deep&Cross 模型的核心,它通过采用拼接的 feature vector 的外积,从而显式地在 bit-wise level 上建模特征交互。
    • CIN(xDeepFM) :是 xDeepFM 模型的核心,它通过采用堆叠的 feature matrix 的外积,从而显式地在 vector-wise level 上建模特征交互。
  4. 实现细节:我们使用 Tensorflow 实现我们的方法。最优超参数由网格搜索策略确定。baseline 的实现遵循 《AutoInt: Automatic Feature Interaction Learning via Self-Attentive Neural Networks》

    • 对于所有方法, field embedding 向量的维度是 16batch size = 1024
    • DeepCrossing 有四个前馈层,每层有 100 个隐单元。
    • NFMBi-Interaction layer 之上有一个大小为 200 的隐层,如原始论文中所推荐的。
    • CrossNetCIN 都有三个交互层。
    • 所有实验都是在配备了 8NVIDIA Titan X GPU 的服务器上进行的。
  5. 不同模型的性能比较,如下表所示。可以看到:

    • LR 在这些 baseline 中效果最差,这证明了单个特征在 CTR 预测中是不够的。
    • 在所有数据集上,建模二阶特征交互的 FMAFM 优于 LR ,这表明建模 feature field 之间的 pairwise 交互是有效的。此外,AFMFM 具有更好的表现,证明了在不同交互上的注意力的有效性。
    • 建模高阶特征交互的方法大多优于建模二阶特征交互的方法。这表明二阶特征交互是不够的。
    • DeepCrossing 优于 NFM ,证明了残差连接在 CTR 预测中的有效性。
    • 在两个数据集上,Fi-GNN 在所有这些方法中取得了最好的性能,尤其是在 Criteo 数据集上。
    • Fi-GNNCriteo 数据集上取得的相对改进,高于在 Avazu 数据集上取得的相对改进。这可能是因为 Criteo 数据集中有更多的 feature field ,可以更好地利用图结构的表达能力。

  6. 消融研究:我们提出的 Fi-GNN 模型是基于 GGNN 的,在此基础上我们主要做了两个改进:

    • 通过 attentional edge weightedge-wise transformation 实现 edge-wise node interaction
    • 引入残差连接从而与 GRU 一起更新节点状态。

    为了评估两种改进的有效性,我们对比了三个变体:

    • Fi-GNN(-E/R):同时没有上述两个改进的变体。
    • Fi-GNN(-E):没有 edge-wise interaction: E 的变体。即,用二元邻接矩阵、以及所有边上共享的投影矩阵。
    • Fi-GNN(-R):没有 residual connection: R 的变体。

    对比结果如下图 (a) 所示。可以看到:

    • Fi-GNN(-E) 的性能相比完整的 Fi-GNN 大幅下降,这表明建模 edge-wise interaction 是至关重要的。
    • Fi-GNN(-E) 取得了比 Fi-GNN(-E/R) 更好的性能,证明了残差连接确实可以提供有用的信息。
    • 完整的 Fi-GNN 优于三种变体,表明我们所做的两种改进,即残差连接和 edge-wise interaction ,可以联合提高性能。

    Fi-GNN 中,我们采用两种方法来实现 edge-wise node interactionattentional edge weight: Wedge-wise transformation: T 。为了进一步研究巨大的改进来自哪,我们比较了另外三个变体:

    • Fi-GNN(-W/T):即 Fi-GNN-(E)
    • Fi-GNN(-W):没有 attentional edge weight
    • Fi-GNN(-T):没有 edge-wise transformation ,即所有边上共享投影矩阵。

    对比结果如下图 (b) 所示。可以看到:

    • Fi-GNN(-T)Fi-GNN(-W) 都优于 Fi-GNN(-W/T) ,这证明了它们的有效性。
    • Fi-GNN(-W)Fi-GNN(-T) 实现了更大的改进,这表明在建模 edge-wise interaction 方面, edge-wise transformationattentional edge weight 更有效。这是非常合理的,因为投影矩阵应该比标量的 attentional edge weightedge-wise interaction 有更强的影响。

  7. 超参数研究:

    • state 维度 d=i=1hdi 的影响:模型性能随着 d 的增加先升后降,在维度分别为 32Avazu 数据集)、64Criteo 数据集)时性能最佳。这是合理的,因为 Criteo 数据集更复杂,需要更大的维度来保持足够的信息。

      没有考虑 attention head 的影响?

    • interaction step T 的影响:interaction step等于特征交互的最高阶次。模型性能随着 T 的增加先升后降,在特征交互的最高阶次分别为 2Avazu 数据集)、3Criteo 数据集)时性能最佳。这是合理的,因为 Avazu 数据集有 23feature fieldCriteo 数据集有 39feature field 。因此,Criteo 数据集需要更多的 interaction step 来使 field nodefeature graph 中的其他节点完全交互。

  8. 模型可解释性:我们在 feature graph 的边上和节点上都应用了注意力机制,分别得到了 attentional edge weightattentional node weight ,可以从不同的角度给出解释。

    Multi-head Self-attention Layer 捕获的 pair-wise 交互是否也是可解释的?论文并没有说明这一点。

    • attentional edge weightattentional edge weight 反映了两个相连的 field node 之间交互的重要性,也反映了两个feature field 之间的关系。下图展示了 Avazu 数据集中所有样本的全局平均邻接矩阵的热力图,它可以在全局水平上反映不同 field 之间的关系。 由于有一些 field 是匿名的,我们只显示剩余的 13 个具有真实含义的 feature field

      可以看到:

      • 一些 feature field 倾向于与其他 field 有很强的关系,例如 site_categorysite_id 。这是有意义的,因为两个 feature field 都对应于投放广告的网站。
      • hour 是另一个与其他 field 有密切关系的特征。这是合理的,因为Avazu 专注于移动场景,用户可以在一天的任何时间在线冲浪。上网时间对其他的广告特征有很大的影响。
      • 另一方面,device_ipdevice_id 似乎与其他 feature field 的关系较弱。这可能是因为它们几乎等同于 user id ,相对固定,不易受其他特征的影响。

    • attentional node weightattentional node weight 反映了 feature field 对整体预测分数的影响的重要性。下图显示了 global-levelcase-levelattentional node weight 的热力图。左边的是 Avazu 数据集中所有样本的全局平均值,右边的是Avazu 数据集中随机选择的四个样本(预测分数分别为 [0.97, 0.12, 0.91, 0.99],标签分别为 [1, 0, 1, 1] )。

      • global level ,我们可以看到 featuer field app_category 对点击行为的影响最大。这是合理的,因为 Avazu 专注于移动场景,而 app 是最重要的因素。
      • case level ,我们观察到,在大多数情况下,最终的点击行为主要取决于一个关键的 feature field

二十八、FwFM[2018]

  1. CTR 预估所涉及的数据通常是 multi-field categorical data,这类数据具有以下特性:

    • 首先,所有的特征都是 categorical 的,并且是非常稀疏的,因为其中许多是 id 。因此,特征的总数很容易达到数百万或数千万。
    • 其次,每个特征都唯一地属于一个 field ,而且可能有几十到几百个 field

    下表是一个用于 CTR 预估的现实世界 multi-field categorical data set 的例子。

    multi-field categorical data 的特性对建立有效的机器学习模型进行 CTR 预测提出了几个独特的挑战:

    • 特征交互feature interaction 是普遍存在的,需要专门建模。在和标签关联方面,特征拼接 feature conjunction 与单个特征不同。例如,nba.com 上展示的耐克广告的点击率,通常比所有网站上耐克广告的平均点击率、或 nba.com 上展示的所有广告的平均点击率高很多。这种现象在文献中通常被称为特征交互。
    • 来自一个 field 的特征往往与来自其他不同 field 的特征有不同的交互。例如,我们观察到,来自 field GENDER 的特征通常与 field ADVERTISER 的特征有很强的交互,而它们与 field DEVICE_TYPE 的特征交互却相对较弱。这可能是由于具有特定性别的用户更偏向于他们正在观看的广告,而不是他们正在使用的设备类型。
    • 需要注意潜在的高模型复杂性。由于实践中通常有数以百万计的特征,模型的复杂性需要精心设计和调整,以适应模型到内存中。

    为了解决这些挑战的一部分,研究人员已经建立了几个解决方案,Factorization Machine: FMField-aware Factorization Machine: FFM 是其中最成功的:

    • FM 通过将 pairwise 特征交互的影响建模为两个 embedding 向量的内积来解决第一个挑战。然而, field 信息在 FM 中根本没有被利用。
    • 最近,FFM 已经成为 CTR 预估中表现最好的模型之一。FFM 为每个特征学习不同的 embedding 向量,从而用于当特征与其他不同 field 的特征进行交互。通过这种方式,第二个挑战被显式地解决了。然而,FFM 的参数数量是特征数量乘以 field 数量的数量级,很容易达到数千万甚至更多。这在现实世界的生产系统中是不可接受的。

    在论文 《Field-weighted Factorization Machines for Click-Through Rate Prediction in Display Advertising》 中,作者引入了 Field-weighted Factorization Machines: FwFM 来同时解决所有这些挑战。论文贡献:

    • 经验表明,不同的 field pairslabel 的关联程度明显不同。按照同样的惯例,论文称它为 field pair interaction
    • 基于上述观察,论文提出了 Field-weighted Factorization Machine: FwFM 。通过引入和学习 field pair weight matrixFwFM 可以有效地捕获 field pair interaction 的异质性。此外,FwFM 中的参数比 FFM 中的参数少几个数量级,这使得 FwFM 成为现实世界生产系统中的首选。
    • FwFM 通过用 embedding vector representation 取代线性项的 binary representation 而得到进一步的增强。这种新的处理方法可以有效地帮助避免过拟合,提高预测性能。
    • 论文在两个真实世界的 CTR 预估数据集上进行了综合实验,以评估 FwFM 与现有模型的性能。实验结果表明:FwFM 仅用FFM4% 的参数就能达到有竞争力的预测性能。当使用相同数量的参数时,FwFMFFMAUC 提升了 0.9%

28.1 模型

  1. 假设有 munique 特征 {f1,,fm},以及 n 个不同的 fields {F1,,Fn} 。每个特征 fi 仅属于一个 field,记做 F(i)

    给定数据集 S={y(s),x(s)}s=1N ,其中: y(s){1,1}label 表示是否点击; x(s){0,1}m 为二元特征向量,xi(s)=1 表示特征 fiactive 的。

    例如,假设有两个 field :性别、学历,那么 n=2 。假设有六个特征:f1=,f2=,f3=,f4=,f5=,f6= ,那么 f1,f2 属于性别这个 fieldf3f6 属于学历这个 field,它们的取值都是 01

    • LR 模型为: