Question

1. 特征在很多预测系统predictive system 的成功中起着核心作用。因为使用原始特征很少能带来最佳结果，所以数据科学家通常会在原始特征的转换transformation 上花费大量工作，从而生成最佳预测系统或赢得数据挖掘data mining 游戏。

   特征转换的一种主要类型是对离散特征categorical feature 的叉积 cross-product 转换。这些特征称作交叉特征cross feature 或者多路特征multi-way feature ，用于衡量多个原始特征的交互interaction 。例如，如果用户在微软亚研院工作，并且在周一看到一篇关于深度学习的技术文章，那么 3-way 特征 AND(user_organization=msra, item_category=deeplearning, time=monday) 取值为 1 。

   传统的交叉特征的特征工程存在三个主要缺点：

   • 首先，获得高质量的特征需要付出高昂的代价。由于正确的特征通常是特定于任务的task-specific ，因此数据科学家需要花费大量时间从产品数据中探索潜在模式，然后才能成为领域专家domain expert 并提取有意义的交叉特征。
   • 其次，在 web-scale 推荐系统等大规模预测系统中，大量的原始特征使得手动提取所有交叉特征变得不可行。
   • 第三，手动制作的交叉特征无法推广到训练数据中未见 unseen 的交互。

   因此，在无需手动特征工程的情况下学习交叉特征是一项有意义的任务。

   因子分解机 Factorization Machine: FM 将每个特征 $ i $ 嵌入到一个潜在因子向量 $ \mathbf{\vec v}_i = (v_{i,1},\cdots,v_{i,D})^\top\in \mathbb R^D $ 中，pairwise 特征交互被建模为潜在向量的内积：

   $ f^{(2)}(i,j) = \left(\mathbf{\vec v_i}^\top \mathbf{\vec v}_j\right)x_ix_j $

   其中 $ x_i $ 为特征 $ i $ 的取值， $ x_j $ 为特征 $ j $ 的取值。在本文中，我们使用术语 bit 来表示潜在向量中的元素（例如 $ v_{i,1} $ ）。

   经典的 FM 可以扩展到任意的高阶特征交互（即 HOFM），但是一个主要缺点是：HOFM 提出对所有特征交互进行建模，包括有用的组合以及无用的组合。正如 AFM 所揭示的，跟无用特征的交互可能会引入噪声并降低性能。

   近年来深度神经网络 DNN 凭借强大的feature representation learning 能力，在计算机视觉、语音识别、自然语言处理方面取得了成功。 DNN 很有希望用于学习复杂的、有选择性的特征交互。

   • 《Deep learning over multi-field categorical data》 提出 Factorization-machine supported Neural Network: FNN 来学习高阶特征交互。在应用 DNN 之前，FNN 使用预训练的 FM 用于 field embedding 。

   • 《Product-based neural networks for user response prediction》 进一步提出了 Product-based Neural Network: PNN 。PNN 在 embedding layer 和 DNN layer 之间引入了一个 product layer，并且不依赖于预训练的 FM。

     FNN 和 PNN 的主要缺点是它们更关注于高阶特征交互，而很少捕获低阶特征交互。

   • Wide & Deep 和 DeepFM 模型通过引入混合架构克服了这个问题，其中包含一个浅层组件和一个深层组件，目的是同时学习 memorization 和 generalization 。因此，他们可以共同学习低阶特征交互和高阶特征交互。

   所有上述模型都利用 DNN 来学习高阶特征交互。然而，DNN 以隐式方式对高阶特征交互进行建模。DNN 学习到的最终函数可以是任意的，对于特征交互的最大阶次maximum degree 是什么，并没有理论上的结论。此外，DNN 在 bit-wise level 对特征交互进行建模，这与传统的 FM 框架在 vector-wise level 对特征交互进行建模不同。因此，在推荐系统领域，DNN 是否确实是表达高阶特征交互的最有效模型仍然是一个悬而未决的问题。

   在论文 《xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systems》 中，作者提出了一种基于神经网络的模型，以显式的、vector-wise 方式学习特征交互。论文的方法基于深度交叉网络 Deep & Cross Network: DCN，旨在有效地捕获有界阶次bounded degree 的特征交互。然而，作者将在论文中论证 DCN 将导致一种特殊的交互形式。因此，论文设计了一种新颖的压缩交互网络 compressed interaction network: CIN 来代替 DCN 中的交叉网络。CIN 显式地学习特征交互，交互的阶次degree 随着网络深度的增加而增长。

   遵循 Wide & Deep 和 DeepFM 模型的精神，论文将具有隐式交互模块的显式高阶交互模块与传统 FM 模块相结合，并将联合模型命名为 eXtreme Deep Factorization Machine: xDeepFM 。新模型不需要手动特征工程，并将数据科学家从繁琐的特征搜索工作中解放出来。总而言之，论文的贡献如下：

   • 提出了一种名为 eXtreme Deep Factorization Machine: xDeepFM 的新模型。xDeepFM 可以有效地联合学习显式高阶特征交互和隐式高阶特征交互，并且不需要手动特征工程。
   • 在 xDeepFM 中设计了一个压缩交互网络 compressed interaction network: CIN。CIN 可以显式地学习高阶特征交互。论文表明特征交互的阶次degree 在每一层都会增加，并且特征在 vector-wise level 而不是 bit-wise level 交互。
   • 对三个真实世界的数据集进行了大量实验，结果表明 xDeepFM 显著优于几个 state-of-the-art 的模型。

2. 相关工作：

   • 经典的推荐系统

     • non-factorization 模型：对于 web-scale 的推荐系统，输入特征通常是稀疏的、categorical-continuous 混合的、高维的。

       线性模型（例如具有 FTRL 的逻辑回归模型）因为易于管理、维护、部署而被广泛采用。由于线性模型缺乏学习特征交互的能力，数据科学家不得不在交叉特征的特征工程上花费大量的工作才能获得更好的性能。

       考虑到一些隐藏特征hidden feature 很难手动设计，一些研究人员利用提升决策树 boosting decision tree: BDT 来帮助构建特征变换。

     • factorization 模型：上述模型的一个主要缺点是它们无法推广到训练集中未见 unseen 的特征交互。

       分解机Factorization Machine: FM 通过将每个特征嵌入到一个低维潜在向量中从而克服这个问题。矩阵分解 Matrix Factorization: MF 仅仅将 ID 视为特征，可以看作是一种特殊的 FM。推荐是通过两个潜在向量的乘积而做出的，因此不需要用户和 item 在训练集中同时出现。MF 是推荐系统文献中最流行的 model-based 协同过滤collaborative filtering: CF方法。一些工作将 MF 扩展到利用辅助信息side information，其中包括线性模型和 MF 模型。

       另一方面，对于很多推荐系统只有隐式反馈数据集，如用户的观看历史和浏览活动可用。因此，研究人员将 factorization 模型扩展到Bayesian Personalized Ranking: BPR 框架从而用于隐式反馈。

   • 深度学习的推荐系统：深度学习技术在计算机视觉、语音识别、自然语言理解方面取得了巨大成功。因此，越来越多的研究人员对于DNN 用于推荐系统感兴趣。

     • 深度学习用于高阶交互：为了避免手动构建高阶交叉特征，研究人员将 DNN 应用于 field embedding，从而可以自动学习来自离散特征交互categorical feature interaction 的模式。代表性模型包括 FNN、PNN、DeepCross、NFM、DCN、Wide & Deep、DeepFM。这些模型与我们提出的 xDeepFM 高度相关。我们将在下文中对它们进行回顾。我们将证明，与这些模型相比，我们提出的 xDeepFM 具有两个特殊属性：xDeepFM 同时以显式方式和隐式方式学习高阶特征交互；xDeepFM 在 vector-wise level 而不是 bit-wise level 学习特征交互。

     • 深度学习用于精细的 Representation Learning：这里我们给出一些基于深度学习的推荐系统，它们不太关注于学习特征交互。

       • 一些早期的工作主要使用深度学习来对辅助信息进行建模，例如视觉数据和音频数据。
       • 最近，深度神经网络被用于对推荐系统中的协同过滤CF 进行建模。《Neural collaborative filtering》 提出了一种神经协同过滤 Neural Collaborative Filtering: NCF ，以便可以通过神经架构用任意函数替换 MF 中的内积。
       • 《Autorec: Autoencoders meet collaborative filtering》 和 《Collaborative denoising auto-encoders for top-n recommender systems》 基于自编码器范式建模 CF，他们通过实验证明了基于自编码器的 CF 优于几个经典的 MF 模型。自编码器可以进一步用于联合建模 CF 和辅助信息，从而生成更好的潜在因子。
       • 《A multi-view deep learning approach for cross domain user modeling in recommendation systems》 和 《CCCFNet: a content-boosted collaborative filtering neural network for cross domain recommender systems》 使用神经网络联合训练多个 domain 的潜在因子。
       • 《Attentive collaborative filtering: Multimedia recommendation with item-and component-level attention》 提出了注意力协同过滤 Attentive Collaborative Filtering: ACF，从而同时在 item-level 和 component-level 学习更精细的偏好。
       • 《Deep interest network for click-through rate prediction》 表明传统的推荐系统无法有效地捕获兴趣多样性interest diversity 和局部激活local activation ，因此他们引入了深度兴趣网络 Deep Interest Network: DIN 来通过注意力激活机制attentive activation mechanism 来表达用户的多样化兴趣。

10.1 基本概念

1. embedding 层Embedding Layer：在计算机视觉或自然语言理解中，输入数据通常是图像信号或文本信号，这些信号在空间或/和时间上是相关的，因此 DNN 可以直接应用于具有稠密结构dense structure 的原始特征。然而，在 web-scale 的推荐系统中，输入特征稀疏、维度巨大，并且没有明显的空间相关性或时间相关性。 因此，multi-field 的 categorical 形式被广泛采用。例如，一个样本的输入 [user_id=s02,gender=male, organization=msra,interests=comedy&rock] 通常通过 field-aware 的 one-hot 编码转换为高维稀疏特征：

   $ [\underbrace{0,1,0,\cdots,0}_{\text{ user id}}][\underbrace{1,0}_{\text{gender}}][\underbrace{0,1,0,0,\cdots,0}_{\text{organization}}][\underbrace{0,1,0,1,\cdots,0}_{\text{interests}}] $

   embedding layer 应用于原始特征输入从而将其压缩为低维、稠密的实值向量。

   • 如果field 是单值univalent 的，则使用 feature embedding 作为 field embedding。例如，将特征 male 的 embedding 作为 field gender 的 embedding。
   • 如果 field 的多值 multivalent的，则使用 feature embedding 的 sum 作为 field embedding。

   embedding layer 如下图所示，embedding size = 4 。

   

   embedding layer 的结果是一个宽的、拼接的向量：

   $ \mathbf{\vec e} = \left[\mathbf{\vec e}_1\|\mathbf{\vec e}_2\|\cdots\|\mathbf{\vec e}_m \right]\in \mathbb R^{mD} $

   其中： $ m $ 为 field 数量， $ \| $ 表示向量拼接， $ \mathbf{\vec e}_i\in \mathbb R^D $ 为 field $ i $ 的 embedding 。

   尽管样本的特征长度可能不同，但是它们的 embedding size 都是 $ mD $ ，其中 $ D $ 为 field embedding 维度。

2. 隐式高阶交互 Implicit High-order Interactions：FNN、Deep Crossing、Wide & Deep 中的 deep 组件利用 field embedding 向量 $ \mathbf{\vec e} $ 之上的前馈神经网络来学习高阶特征交互。前向传播过程为：

   $ \mathbf{\vec x}^{(1)} = \sigma\left(\mathbf W^{(1)}\mathbf{\vec e} + \mathbf{\vec b}^{(1)}\right)\\ \mathbf{\vec x}^{(k)} = \sigma\left(\mathbf W^{(k)}\mathbf{\vec x}^{(k-1)} + \mathbf{\vec b}^{(k)}\right) $

   其中 ： $ k $ 为第 $ k $ 层， $ \sigma(\cdot) $ 为激活函数， $ \mathbf{\vec x}^{(k)} $ 为第 $ k $ 层的输出， $ \mathbf W^{(k)},\mathbf{\vec b}^{(k)} $ 为第 $ k $ 层的参数。

   这个前向传播过程的视觉结构visual structure 和下图中所示的网络结构（PNN 和 DeepFM ）非常相似，只是这个前向传播过程不包含 FM Layer 或者 Product Layer。这个前向传播过程以 bit-wise 方式对交互进行建模。也就是说，即使是同一个 field embedding 内的元素也会相互影响。

   PNN 和 DeepFM 稍稍修改了上述架构。除了在 embedding 向量 $ \mathbf{\vec e} $ 上应用 DNN 之外，它们还在架构中添加了 2-way 的交互层 interaction layer （PNN 的 product layer、DeeFM 的 FM layer）。因此，它们的模型中同时包含了 bit-wise 交互和 vector-wise 交互。PNN 和 DeepFM 的主要区别在于：PNN 将 product layer 的输出连接到 DNN，而 DeepFM 将 FM layer 直接连接到输出单元，如下图所示。图中的红色连线代表 weight-1 的连接、灰色连线代表神经网络连接红色，另外 DeepFM 忽略了线性回归部分。

   

3. 显式高阶交互 Explicit High-order Interactions：DCN 提出了交叉网络 Cross Network: CrossNet，其架构如下图所示。DCN 旨在显式地对高阶特征交互进行建模。和经典的全连接前馈神经网络不同，DCN 的隐层通过以下交叉操作 cross operation 计算：

   $ \mathbf{\vec x}_{k} = \mathbf{\vec x}_0\mathbf{\vec x}_{k-1}^\top\mathbf{\vec w}_{k}+ \mathbf{\vec b}_k + \mathbf{\vec x}_{k-1} $

   其中： $ \mathbf{\vec w}_k,\mathbf{\vec b}_k,\mathbf{\vec x}_k\in \mathbb R^{mD} $ 分别为第 $ k $ 层的权重向量、bias 向量、输出向量。

   我们认为：CrossNet 学习了一种特殊类型的高阶特征交互，其中 CrossNet 中的每个隐层的输出都是 $ \mathbf{\vec x}_0 $ 的标量倍数。

   CrossNet 可以非常高效地学习特征交互。与 DNN 相比，CrossNet 的复杂度可以忽略不计。但是 CrossNet 的缺点是：

   • CrossNet 的输出受限于特征形式，即每个隐层的输出都是 $ \mathbf{\vec x}_0 $ 的标量倍数。
   • 特征交互是以 bit-wise 方式进行的。

   

4. 定理：考虑一个 $ k $ 层的交叉网络，其中第 $ i $ 层的输出定义为 $ \mathbf{\vec x}_{i} = \mathbf{\vec x}_0\mathbf{\vec x}_{i-1}^\top\mathbf{\vec w}_{i} + \mathbf{\vec x}_{i-1} $ 。那么交叉网络的输出 $ \mathbf{\vec x}_k $ 是 $ \mathbf{\vec x}_0 $ 的标量倍数。

   证明：当 $ k=1 $ 时，根据矩阵乘法的结合律和分配律，我们有：

   $ \mathbf{\vec x}_1 = \mathbf{\vec x}_0\mathbf{\vec x}_0^\top\mathbf{\vec w}_1 + \mathbf{\vec x}_0 \\ = \mathbf{\vec x}_0\left(\mathbf{\vec x}_0^\top\mathbf{\vec w}_1\right) + \mathbf{\vec x}_0 \\ = \mathbf{\vec x}_0\left(\mathbf{\vec x}_0^\top\mathbf{\vec w}_1 +1\right) = \alpha_1 \mathbf{\vec x}_0 $

   其中 $ \alpha_1 = \mathbf{\vec x}_0^\top\mathbf{\vec w}_1 +1 $ 为 $ \mathbf{\vec x}_0 $ 的一个线性回归。因此 $ k=1 $ 时命题成立。

   假设结论在 $ k=i $ 时命题成立。当 $ k=i+1 $ 时，

   $ \mathbf{\vec x}_{i+1} = \mathbf{\vec x}_0\mathbf{\vec x}_{i}^\top\mathbf{\vec w}_{i+1} + \mathbf{\vec x}_{i}\\ = \mathbf{\vec x}_0\left(\left(\alpha_i \mathbf{\vec x}_0\right)^\top \mathbf{\vec w}_{i+1}\right) + \alpha_i \mathbf{\vec x}_0 = \alpha_{i+1} \mathbf{\vec x}_0 $

   其中 $ \alpha_{i+1} = \alpha_i \left(\mathbf{\vec x}_0^\top \mathbf{\vec w}_{i+1} + 1\right) $ 为一个标量。因此 $ k=i+1 $ 时命题也成立。根据数学归纳法，则交叉网络的输出 $ \mathbf{\vec x}_k $ 是 $ \mathbf{\vec x}_0 $ 的标量倍数。

   注意：标量倍数并不意味着 $ \mathbf{\vec x}_k $ 与 $ \mathbf{\vec x}_0 $ 呈线性关系，因为标量系数 $ \alpha_{k} $ 是 $ \mathbf{\vec x}_0 $ 的函数。

10.2 模型

10.2.1 CIN

1. 我们设计了一个新的交叉网络，称作压缩交互网络 Compressed Interaction Network: CIN。CIN 具有以下考虑：交互应用在 vector-wise level 而不是 bit-wise level ；显式高阶交互；网络的复杂度不会随着交互的阶次呈指数型增长。

2. 由于 embedding 向量被视为 vector-wise 交互的基本单元，因此我们将 field embedding 的输出表示为矩阵 $ \mathbf X^{(0)} \in \mathbb R^{m\times D} $ 。 $ \mathbf X^{(0)} $ 的第 $ i $ 行是第 $ i $ 个 field 的 embedding 向量 $ \mathbf X^{(0)}_{i,*} = \mathbf{\vec e}_i\in \mathbb R^{D} $ ， $ D $ 为 field embedding 的维度。

   CIN 中第 $ k $ 层的输出也是一个矩阵 $ \mathbf X^{(k)}\in \mathbb R^{H_k\times D} $ ，其中 $ H_k $ 表示第 $ k $ 层输出的 embedding 向量（也称作 feature vector）的个数，并且 $ H_0=m $ 。对于 CIN， $ \mathbf X^{(k)} $ 计算为：

   $ \mathbf X_{h,*}^{(k)} = \sum_{i=1}^{H_{k-1}}\sum_{j=1}^m W_{i,j}^{(k,h)}\times \left(\mathbf X_{i,*}^{(k-1)}\odot \mathbf X_{j,*}^{(0)}\right) ,\quad 1\le h\le H_k $

   其中：

   • $ \mathbf W^{(k,h)}\in \mathbb R^{H_{k-1}\times m} $ 为第 $ k $ 层、第 $ h $ 个输出 feature vector的参数矩阵。它的第 $ (i,j) $ 个元素给出了第 $ k-1 $ 层第 $ i $ 个输出 feature vector和第 0 层第 $ j $ 个输出feature vector交互的权重。
   • $ \odot $ 为向量的逐元素乘积。

   注意： $ \mathbf X^{(k)} $ 是通过 $ \mathbf X^{(k-1)} $ 和 $ \mathbf X^{(0)} $ 之间的交互推导而来的，因此特征交互可以显式度量，并且交互的阶次degree 随着层的深度增加而增长。

3. CIN 的结构与循环神经网络 Recurrent Neural Network: RNN 非常相似，其中下一个隐层的输出取决于上一个隐层和一个额外的输入。我们在所有层都以 embedding 向量为单位参与计算，因此交互是在 vector-wise level 应用的。

   有趣的是，上述方程与计算机视觉中著名的卷积神经网络 Convolutional Neural Network: CNN 有着很强的联系。

   • 如下图所示，我们引入了一个中间张量 $ \mathbf Z^{(k+1)}\in \mathbb R^{D\times H_k\times m} $ ，它是隐层 $ \mathbf X^{(k)} $ 和原始特征矩阵 $ \mathbf X^{(0)} $ 的外积（沿着每个 embedding 维度）。那么 $ \mathbf Z^{(k+1)} $ 可以视为一种特殊类型的图像， $ \mathbf W^{(k+1,h)}\in \mathbb R^{H_k\times m} $ 为一个滤波器，一共有 $ H_{k+1} $ 个滤波器。

     

   • 如下图所示，我们沿着 embedding 维度 （D） 将滤波器在 $ \mathbf Z^{(k+1)} $ 上滑动，得到一个隐向量 $ \mathbf X^{(k+1)}_{i,*} $ ，在计算机视觉中通常称作 feature map 。因此， $ \mathbf X^{(k)} $ 是 $ H_k $ 个不同 feature map 的集合。

     如下图所示 $ \text{feature map 1} $ 为滤波器 $ \mathbf W^{(k+1,1)} $ 沿着 embedding 维度滑动， $ \text{feature map } H_{k+1} $ 为滤波器 $ \mathbf W^{(k+1,H_{k+1})} $ 沿着 embedding 维度滑动。

     

   CIN 名字中的 compressed 一词表示第 $ k $ 个隐层将 $ H_{k-1}\times m $ 个向量的潜在空间压缩为 $ H_k $ 个向量。

4. CIN 网络的整体结构如下图所示。令 $ T $ 表示网络的深度。每个隐层 $ \mathbf X^{(k)}\in \mathbb R^{H_k\times D}, 1\le k\le T $ 都与输出单元连接。

   • 我们首先在隐层的每个 feature map 上沿着 embedding 维度应用 sum 池化：

     $ p_i^{(k)} = \sum_{j=1}^D X^{(k)}_{i,j},\quad 1\le i\le H_k $

     因此我们得到一个池化向量 $ \mathbf {\vec p}^{(k)} = \left(p_1^{(k)},p_2^{(k)},\cdots,p_{H_k}^{(k)}\right)^\top $ 。

   • 来自隐层的所有池化向量在连接到输出单元之前进行拼接：

     $ \mathbf{\vec p}^{(+)} = \left[\mathbf{\vec p}^{(1)}\|\mathbf{\vec p}^{(2)}\|\cdots\|\mathbf{\vec p}^{(T)}\right]\in \mathbb R^{\sum_{k=1}^T H_k} $

     其中 || 表示向量拼接。

   • 如果我们直接使用 CIN 进行二分类，那么输出单元是位于 $ \mathbf{\vec p}^{(+)} $ 之上的一个 sigmoid 节点：

     $ \hat y =\frac{1}{1+\exp\left(\left(\mathbf{\vec p}^{(+)}\right)^\top\mathbf{\vec w}_o\right)} $

     其中 $ \mathbf{\vec w}_o\in \mathbb R^{\sum_{k=1}^T H_k} $ 为输出层参数。

   

10.2.2 CIN 分析

1. 我们分析了CIN 从而研究模型的复杂性和潜在的有效性。

2. 空间复杂度Space Complexity：第 $ k $ 层的第 $ h $ 个 feature map 包含 $ H_{k-1}\times m $ 个参数，正好是 $ \mathbf W^{(k,h)} $ 的size。第 $ k $ 层一共有 $ H_k $ 个 feature map，因此第 $ k $ 层共有 $ H_k\times H_{k-1}\times m $ 个参数。考虑到输出单元有 $ \sum_{k=1}^T H_k $ 个参数，因此CIN 的参数总量为 $ \sum_{k=1}^T H_k\times (1+H_{k-1}\times m) $ 。注意，CIN 与 embedding 维度 $ D $ 无关。

   • 相比之下，一个普通的 $ T $ 层 DNN 包含 $ m\times D\times H_1 +\sum_{k=2}^T H_k\times H_{k-1}+ H_T $ 个参数，并且参数总量会随着 embedding 维度 $ D $ 的增加而增加。

   • 通常 $ m $ 和 $ H_{k} $ 不会很大，所以 $ \mathbf W^{(k,h)} $ 的 size 是可以接受的。必要时，我们可以利用 $ L $ 阶分解并将 $ \mathbf W^{(k,h)} $ 替换为两个较小的矩阵 $ \mathbf U^{(k,h)}\in \mathbb R^{H_{k-1}\times L}, \mathbf V^{(k,h)}\in \mathbb R^{m\times L} $ ：

     $ \mathbf W^{(k,h)} = \mathbf U^{(k,h)}\left(\mathbf V^{(k,h)}\right)^\top $

     其中 $ L\ll H, L\ll m $ 。

   • 这里为了简单起见，我们假设每个隐层都具有相同数量（即 $ H_1=\cdots H_T=H $ ）的 feature map 。

     通过 $ L $ 阶分解，CIN 的空间复杂度从 $ O(mTH^2) $ 下降到 $ O(mTHL + TH^2L) $ 。相比之下，普通 DNN 的空间复杂度为 $ O(mDH+TH^2) $ ，对 field embedding 维度 $ D $ 敏感。

3. 时间复杂度Time Complexity ：计算张量 $ \mathbf Z^{(k+1)} $ 的时间成本是 $ O(mHD) $ 。因为我们在一个隐层中有 $ H $ 个 feature map，所以计算 $ T $ 层 CIN 需要 $ O(mH^2DT) $ 时间。相比之下，一个 $ T $ 层的普通 DNN 需要 $ O(mHD + H^2T) $ 时间。因此，CIN 的主要缺点在于时间复杂度。

4. 多项式近似 Polynomial Approximation：接下来我们检查 CIN 的高阶交互特性property 。为简单起见，我们假设隐层的 feature map 数量都等于 field 数量 $ m $ 。则第一层的第 $ h $ 个 feature map，记作 $ \mathbf{\vec x}^{(1)}_h\in \mathbb R^D $ ，计算为：

   $ \mathbf{\vec x}_h^{(1)} = \sum_{i=1}^m\sum_{j=1}^m W_{i,j}^{(1,h)} \left(\mathbf{\vec x}_i^{(0)}\odot \mathbf{\vec x}_j^{(0)}\right) $

   因此，第一层的每个 feature map 都使用 $ O(m^2) $ 个系数对 pair-wise 交互进行建模。同理，第二层的第 $ h $ 个 feature map 为：

   $ \mathbf{\vec x}_h^{(2)} = \sum_{i=1}^m\sum_{j=1}^m W_{i,j}^{(2,h)} \left(\mathbf{\vec x}_i^{(1)}\odot \mathbf{\vec x}_j^{(0)}\right)\\ = \sum_{i=1}^m\sum_{j=1}^m \sum_{s=1}^m\sum_{t=1}^mW_{i,j}^{(2,h)}W_{s,t}^{(1,i)}\left(\mathbf{\vec x}_j^{(0)}\odot \mathbf{\vec x}_s^{(0)}\odot \mathbf{\vec x}_t^{(0)}\right) $

   注意：所有与下标 $ s,t $ 有关的计算已经在前一个隐层完成。为了清晰起见，我们展开了 $ \mathbf{\vec x}_i^{(1)} $ 。可以看到，第二层的每个 feature map 都使用 $ O(m^2) $ 个新的参数对 3-way 交互进行建模。

   一个经典的 $ k $ 阶多项式有 $ O(m^k) $ 个系数。我们将表明 CIN 以 feature map 链的形式仅使用 $ O(km^3) $ 个参数来近似此类多项式。通过数学归纳法，我们可以证明第 $ k $ 层的第 $ h $ 个 feature map 为：

   $ \mathbf{\vec x}_h^{(k)} = \sum_{i=1}^m\sum_{j=1}^m W_{i,j}^{(k,h)} \left(\mathbf{\vec x}_i^{(k-1)}\odot \mathbf{\vec x}_j^{(0)}\right)\\ =\sum_{i=1}^m\sum_{j=1}^m\cdots \sum_{r=1}^m\sum_{t=1}^m\sum_{l=1}^m\sum_{s=1}^m W_{i,j}^{(k,h)}\cdots W_{l,s}^{(1,r)} \underbrace{\left(\mathbf{\vec x}_j^{(0)}\odot\cdots\odot \mathbf{\vec x}_s^{(0)}\odot \mathbf{\vec x}_l^{(0)}\right)}_{k \text{ vectors}} $

   为了更好地说明，我们令 $ \vec\alpha = (\alpha_1,\cdots,\alpha_m)\in \mathbb N^m $ 为一个 multi-index， $ \alpha_i $ 为非负整数。记 $ |\vec\alpha| = \sum_{i=1}^m \alpha_i $ 。我们忽略了 $ \mathbf{\vec x}_i^{(0)} $ 的原始上标，并使用 $ \mathbf{\vec x}_i $ 来代替，因为在最终展开的表达式中只有来自第 0 层的 feature map（它就是 field embedding ）。现在我们使用上标来表示向量运算，例如 $ \mathbf{\vec x}_i^3 = \mathbf{\vec x}_i\odot \mathbf{\vec x}_i\odot \mathbf{\vec x}_i $ 。

   令 $ VP_k(\mathbf X) $ 表示 $ k $ 阶的 multi-vector 多项式：

   $ VP_k(\mathbf X) = \left\{\sum_{\vec\alpha}w_{\vec\alpha} \mathbf{\vec x}_1^{\alpha_1}\odot\mathbf{\vec x}_2^{\alpha_2}\odot\cdots \odot \mathbf{\vec x}_m^{\alpha_m}\bigg| \;2\le |\vec\alpha| \le k \right\} $

   这一族的每个vector 多项式都有 $ O(m^k) $ 个系数。然后，我们的 CIN 逼近系数 $ w_{\vec\alpha} $ ：

   $ \hat w_{\vec\alpha} = \sum_{i=1}^m\sum_{j=1}^m\sum_{\vec B\in \mathbb P_{\vec \alpha}} \prod_{t=2}^{|\vec\alpha|} W_{i,B_t}^{(t,j)} $

   其中 $ \vec B=(B_1,\cdots,B_{|\vec\alpha|})^\top $ 为一个 multi-index， $ \mathbb P_{\vec\alpha} $ 为索引 $ (\underbrace{1,\cdots,1}_{\alpha_1 \text{ times}},\cdots,\underbrace{m,\cdots,m}_{\alpha_m \text{ times}}) $ 的所有排列组合构成的索引集合。

10.2.3 与隐式网络结合

1. 如前所述，普通 DNN 学习隐式高阶特征交互。由于CIN 和普通 DNN 可以互补，因此使模型更强大的一种直观方法是将这两种结构结合起来。最终得到的模型与 Wide & Deep 或 DeepFM 模型非常相似，架构如下图所示。我们将新模型命名为 eXtreme Deep Factorization Machine: xDeepFM 。一方面 xDeepFM 同时包含低阶特征交互和高阶特征交互，另一方面xDeepFM 同时包含隐式特征交互和显式特征交互。

   xDeepFM 的输出单元结果为：

   $ \hat y = \sigma\left(\mathbf{\vec w}^\top_\text{linear} \mathbf{\vec a} + \mathbf{\vec w}_\text{dnn}^\top \mathbf{\vec x}^{(k)}_\text{dnn} + \mathbf{\vec w}_\text{cin}^\top \mathbf{\vec p}^{(+)} + b\right) $

   其中： $ \sigma(\cdot) $ 为非线性激活函数； $ \mathbf{\vec a} $ 为原始特征； $ \mathbf{\vec x}^{(k)}_\text{dnn} $ 为普通 DNN 的输出； $ \mathbf{\vec p}^{(+)} $ 为 CIN 的输出； $ \mathbf{\vec w}_\text{linear},\mathbf{\vec w}_\text{dnn},\mathbf{\vec w}_\text{cin} $ 为权重向量， $ b $ 为 bias。

   对于二元分类问题，损失函数为 log loss：

   $ \mathcal L = -\frac{1}{N}\sum_{i=1}^N y_i \log \hat y_i + (1-y_i)\log \left(1-\hat y_i\right) $

   其中 $ N $ 为训练样本总数。

   优化过程最小化以下目标函数： $ \mathcal J = \mathcal L + \lambda_* \|\mathbf\Theta\| $ 。其中： $ \lambda_* $ 为正则化系数， $ \mathbf \Theta $ 为包括线性部分、CIN 部分、DNN 部分的训练参数集合。

   

2. 和 FM, DeepFM 的关系：假设所有字段都是单值univalent 的。从上图不难看出，当 CIN 部分的深度为 $ k=1 $ 、feature map 数量 $ H_k=1 $ 时，xDeepFM 是DeepFM 的推广，通过学习 FM 层的线性回归权重（注意，在 DeepFM 中，FM 层的单元直接连接到输出单元，没有任何系数）。

   当我们进一步移除 DNN 部分时，同时对 feature map 使用一个 constant 的 sum 滤波器（即它只是获取输入的 sum，没有任何待学习的参数，此时 $ W_{i,j}^{(1,1)}=1 $ ）时，那么 xDeepFM 就降级downgraded 为传统的 FM 模型。

10.3 实验

1. 这里我们进行了大量实验来回答以下问题：

   • Q1：我们提出的 CIN 在高阶特征交互学习中的表现如何？
   • Q2：推荐系统是否需要结合显式高阶特征交互和隐式高阶特征交互？
   • Q3：网络的超参数如何影响 xDeepFM 的性能？

   我们将在介绍一些基本的实验配置之后回答这些问题。

2. 数据集：我们将在以下三个数据集中评估我们提出的方法。

   • Criteo 数据集：它是一个可以公开访问的、著名的工业 benchmark 数据集，用于开发点击率预估模型。给定用户和他正在访问的网页，目标是预估用户点击给定广告的概率。

   • DianPing 数据集：大众点评网是中国最大的消费者评论网站。它提供多种特征，如评论、签到 check-in、以及商店的元信息（包括地理位置和商店属性）。我们为餐厅推荐实验收集了 6 个月的用户 check-in 记录。给定用户的用户画像、目标餐厅的属性、以及用户最近访问的三个point of interest: POI，我们希望预测他将访问目标餐厅的概率。

     对于用户 check-in 样本中的每家餐厅（postive 餐厅），我们根据 POI 热度popularity 对 postive 餐厅 3 公里范围内的四家餐厅进行采样作为负样本。

   • Bing News 数据集：Bing News 是微软 Bing 搜索引擎的一部分。为了评估我们模型在真实商业数据集中的性能，我们收集了新闻阅读服务上连续五天的曝光日志。我们使用前三天的数据进行训练和验证、用最后两天的数据进行测试。

   对于 Criteo 和 Dianping 数据集，我们按照 8:1:1 随机拆分样本用于训练、验证、测试。

   下表给出了这三个数据集的统计特性。

   

3. 评估指标：我们使用两个指标 AUC 和 Logloss 从不同角度来评估模型性能。

   • AUC 衡量一个正样本的排序高于随机选择的负样本的概率。它仅考虑预测样本的相对排序，对于类别不平衡问题class imbalance problem 不敏感。
   • 相反，Logloss 衡量每个样本的预测 score 和真实 label 之间的距离。

   有时我们更多地依赖 Logloss，因为我们需要使用预估点击率来估计排序策略的收益（通常使用 eCPM = pCTR x bid 来排序）。

4. baseline 方法：我们将 xDeepFM 和 logistic regression: LR、FM、DNN（普通深度神经网络）、PNN（从 IPNN 和 OPNN 中选择更好的那个）、Wide & Deep、DCN 、DeepFM 进行比较。如前所述，这些模型与我们的 xDeepFM 高度相关，其中一些是推荐系统的 state-of-the-art 模型。

   注意，本文的重点是自动学习特征交互，因此我们不包括任何手工制作的交叉特征。

5. 配置：

   • 我们使用 Tensorflow 实现我们的方法。
   • 每个模型的超参数通过在验证集上进行网格搜索来调优，每个模型的最佳 setting 将在相应部分显示。
   • 学习率设置为 0.001，优化器为 Adam ，batch size = 4096。
   • 对于 DNN, DCN, Wide & Deep, DeepFM, xDeepFM，采用 $ \lambda = 0.0001 $ 的 L2 正则化。对于 PNN，采用 dropout rate = 0.5 的 dropout 正则化。
   • 每层神经元数量的默认设置为：DNN 部分每层 400 个神经元；CIN 部分在 Criteo 数据集上每层 200 个神经元、在Dianping 数据集和 Bing News 数据集上每层 100 个神经元。
   • 由于本文关注的是神经网络结构，因此我们将所有模型的 field embedding 维度设为固定值 10。

   我们使用 5 个 Tesla K80 GPU 并行进行不同 setting 的实验。源代码可以在 github 上获取。

10.3.1 Q1: 单个神经网络组件的性能比较

1. 我们想知道单体 CIN 的效果。注意：FM 显式地建模二阶特征交互，DNN 隐式地建模高阶特征交互，CrossNet 尝试使用少量参数建模高阶特征交互（如前所述，这被证明无效），而CIN 显式地建模高阶特征交互。理论上无法保证某个单体individual 模型优于其它单体模型，因为这确实取决于数据集。例如，如果实际数据集不需要高阶特征交互，那么 FM 可能是最好的单体模型。因此，我们对哪个模型在这个实验中表现最好没有任何预期。

   下表显式了所有单体模型在三个实际数据集上的表现，Depth 列表示超参数调优找到的最佳网络深度。这里 CIN 是 xDeepFM 的 CIN 网络，不包含 xDeepFM 的 DNN 部分。CrossNet 是 DCN 的 cross network 部分，也不包含 DNN 部分。

   令人惊讶的是，我们的 CIN 始终优于其它模型。

   • 一方面，结果表明：对于实际数据集，稀疏特征上的高阶交互是必要的。这可以通过 DNN、CrossNet、CIN 在所有三个数据集上显著优于 FM 的事实来验证。
   • 另一方面，CIN 是最好的单体模型，这证明了 CIN 在显式建模高阶特征交互方面的有效性。

   注意， $ k $ 层 CIN 可以对 $ k $ 阶特征交互进行建模。同样有趣的是，CIN 需要 5 层才能在 Bing News 上产生最佳结果。

   

10.3.2 Q2: 整体模型的性能比较

1. xDeepFM 将 CIN 和 DNN 集成到端到端模型中。虽然 CIN 和 DNN 在学习特征交互方面涵盖了两个不同的属性，但是我们有兴趣知道它们结合在一起进行联合的显式学习和隐式学习是否确实有必要和有效。在这里，我们比较了几个强baseline，其中不限于单体模型individual model 。结果如下表所示，可以看到：

   • LR 远比所有其它模型差，这表明 factorization-based 的模型对预测稀疏特征至关重要。
   • Wide & Deep, DCN, DeepFM, xDeepFM 明显优于 DNN，这直接反映了虽然简单，但是融合了混合组件 hybrid components 对于提高预测系统的准确性很重要。
   • 我们提出的 xDeepFM 在所有数据集上都实现了最佳性能，这表明结合显式高阶特征交互和隐式高阶特征交互是必要的，并且 xDeepFM 在学习此类组合时是有效的。
   • 另一个有趣的观察是，所有基于神经网络的模型都不需要非常深的网络结构以获得最佳性能。depth 超参数的典型设置为 2 和 3，xDeepFM 的最佳深度为 3，这表明我们学习的交互最多为 4 阶。

   表中的 Depth 列给出整体模型通过超参数调优得到的各个组件的最佳深度，格式为 ” cross 层深度，DNN 层深度“。

   

10.3.3 Q3: 超参数研究

1. 这里我们研究超参数对 xDeepFM 的影响，包括：隐层数量、每层神经元数量、激活函数。我们通过保持 DNN 部分的最佳设置的同时改变 CIN 部分的setting 来进行实验。

2. 隐层深度：下图展示了隐层数量的影响。可以看到：

   • xDeepFM 的性能在开始时随着网络深度的增加而增加。
   • 然而，当网络深度大于 3 时，模型性能会下降。这是由于过拟合引起的，因为我们发现当添加更多隐层时，训练损失仍然在不断下降。

   

   

3. 每层神经元数量：增加每层神经元数量表示增加 CIN 中的 feature map 数量。如下图所示，当我们将每层神经元数量从 20 增加到 200 时，Bing News 数据集上的模型性能稳步提高。而在 Dianping 数据集上，100 是最佳的每层神经元数量。在这个实验中，我们将隐层深度固定为 3 。

   注：由于 field embedding 固定为 10，因此 CIN 每层神经元数量为 20 意味着 $ H_k = 2 $ 。

   

   

4. 激活函数：注意，我们在CIN 神经元上用恒等映射作为激活函数。深度学习文献中一种常见做法是在隐层神经元上使用非线性激活函数。因此，我们在 CIN 上比较不同激活函数的结果（对于 DNN 中的神经元，我们保持使用 relu 激活函数）。如下图所示，恒等映射确实是最适合 CIN 中神经元的激活函数。

   

   

5. 未来工作有两个方向：

   • 首先，目前我们仅使用 sum 池化来嵌入多元multivalent 的 field。我们可以探索使用 DIN 机制根据候选 item 来捕获相关的 activation 。
   • 其次，如前所述，CIN 模块的时间复杂度很高。我们有兴趣开发一个分布式版本的 xDeepFM，它可以在 GPU 集群上有效地训练。