一、NFM [2017]

《Neural Factorization Machines for Sparse Predictive Analytics》

1. 预测性的分析（predictive analytics）是很多信息检索（information retrieval: IR）和数据挖掘（data mining: DM）任务中最重要的技术之一，从推荐系统、定向广告（targeted advertising），到搜索排序、视觉分析（visual analysis）、事件检测（event detection）。通常，预测性任务（predictive task）被描述为估计将预测变量（predictor variables）映射到某个目标的函数，例如用于回归的实值目标（real valued target）和用于分类的离散目标（categorical target）。例如，在在线广告中，我们需要预测特定职业（第二个预测变量）的用户（第一个预测变量）点击广告（第三个预测变量）的可能性（目标）。

   与图像和音频中自然存在的连续预测变量（continuous predictor variables）（例如原始特征）不同，web application 的预测变量大多数是不连续（discrete）的和离散（categorical）的。要使用这些离散（categorical）的预测变量构建预测性的模型（predictive models），一种常见的解决方案是通过 one-hot encoding 将它们转换为一组二元特征（也称作特征向量）。然后，可以应用标准机器学习（machine learning: ML）技术，例如逻辑回归（LR）和支持向量机（SVM）。

   根据离散的预测变量的可能值（possible values），生成的特征向量可以具有非常高的维度但是很稀疏。要使用此类稀疏数据构建有效的机器学习模型，考虑特征之间的交互（interaction）至关重要。工业界和学术界的许多成功解决方案在很大程度上依赖于手动制作的组合特征（combinatorial features），即通过组合多个预测变量来构建新特征，也称作交叉特征（cross features）。例如，我们可以交叉变量 occupation = { banker, doctor}，gender = { M, F} ，从而得到一个新的特征 occupation_gender = { banker_M, banker_F, doctor_M, doctor_F } 。众所周知，顶级数据科学家通常是精心设计组合特征的大师，这在他们的获胜的公式中起着关键作用。然而，这些特征的强大是以高成本为代价的，因为这需要大量的工程努力（engineering efforts）和有用的领域知识（domain knowledge）来设计有效的特征。因此，这些解决方案很难推广到新问题或者新领域。

   另一种解决方案是设计一个机器学习模型来自动从原始数据中学习特征交互，而不是手动增加特征。一种流行的方法是分解机（factorization machine: FM），它将特征嵌入到潜在空间中，并通过 feature embedding 向量之间的内积来建模特征交互（feature interaction）。虽然 FM 在许多预测任务中取得了巨大的成功，但是NFM 的作者认为其性能可能受到它的线性、以及二阶特征交互建模的限制。具体而言，对于具有复杂的和非线性固有结构（inherent structure）的现实世界数据，FM 表达能力可能不够。尽管已经提出了高阶 FM，但是它们仍然属于线性模型家族，并且据称难以估计（estimate）。此外，这些高阶 FM 仅比 FM 略有改善，NFM 的作者怀疑这可能是由于高阶交互的线性建模带来的。虽然深度神经网络最近被应用于学习工业中的非线性特征交互，例如谷歌的 Wide & Deep、微软的 DeepCross，但是深度结构同时使它们难以训练。

   在论文 《Neural Factorization Machines for Sparse Predictive Analytics》中，作者提出了一种新的稀疏数据预测模型，称为神经分解机（Neural Factorization Machine: NFM），它通过建模高阶和非线性特征交互来强化 FM。通过在神经网络建模中设计一种新的操作（即，双线性交互池化 Bilinear Interaction pooling ），论文第一次将 FM 纳入神经网络框架之下。

   • 通过在 Bi-Interaction layer 之上堆叠非线性层，NFM能够加深（deepen）浅层线性 FM，有效地建模高阶和非线性特征交互以提高 FM 的表达能力。

   • 与传统的深度学习方法在底层（low level）简单地拼接、或平均 embedding 向量相比，NFM 使用 Bi-Interaction pooling 编码了更多有信息（informative）的特征交互，极大地促进了后续 deep layer 来学习有意义的信息。

   NFM 无缝地结合了 FM 在建模二阶特征交互中的线性、以及神经网络在建模高阶特征交互中的非线性。从概念上讲，NFM 比 FM 更具有表达能力，因为 FM 可以被视为没有隐层的 NFM 的特例。

   论文对上下文感知预测（context-aware prediction）和个性化标签推荐（personalized tag recommendation）的两个公共 benchmark 进行了广泛的实验。仅使用一个隐层， NFM 显著优于 FM（官方 LibFM 的实现），提高了 7.3%。与 SOTA 的深度学习方法（ 3 层 Wide & Deep 和 10 层的 DeepCross ）相比， 1 层 NFM 以更简单的结构、更少的模型参数显示出一致的提升。论文的实现可以在 github 上获得。

   这项工作的主要贡献如下：

   • 据作者所知，论文是第一个在神经网络建模中引入 Bi-Interaction pooling 操作的人，并为 FM 提出了一种新的神经网络视角。

   • 基于这种新视角，论文开发了一种新的 NFM 模型，从而在神经网络框架下 deepen FM ，最终学习高阶和非线性的特征交互。

   • 论文对两个真实世界的任务进行了广泛的实验，以研究 Bi-Interaction pooling 和 NFM 模型，证明了 NFM 的有效性以及在稀疏设置（sparse setting）下使用神经网络进行预测的巨大前景。

     与最近的深度学习方法 Wide & Deep、DeepCross 相比， NFM 使用更浅的结构但是提供了更好的性能，在实践中更容易训练和调优。

1.1 建模特征交互

1. 由于组合特征的空间很大，传统解决方案通常依靠手动特征工程（manual feature engineering） 或特征选择（ feature selection ）技术（如增强决策树boosted decision trees: BDT ）来选择重要的特征交互。这种解决方案的一个限制是它们不能泛化到未出现在训练数据中的组合特征。

   近年来，基于 embedding 的方法变得越来越流行，该方法试图从原始数据中学习特征交互。通过将高维稀疏特征嵌入到低维潜在空间中，该模型可以泛化到未见过（ unseen ）的特征组合。无论是哪个领域（ domain），我们都可以将这些方法分为两类：基于分解机（factorization machine: FM）的线性模型、基于神经网络的非线性模型。这里我们简要地概述这两种代表性的技术。

1.1.1 FM

1. FM 最初用于协同推荐（collaborative recommendation）。给定一个实值特征向量 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\mathbf{\vec x}\in \mathbb R^n$ ，FM 通过分解交互参数（interaction parameters），从而对每个对特征之间的所有交互进行建模，进而估计目标（target）：

   $${\hat{y}}_{\text{FM}}\left(\overrightarrow{\mathbf{x}}\right)=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^n\sum _{j=i+1}^n{\overrightarrow{\mathbf{v}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_j\times x_i{x}_j$$

   其中：

   • $w_0$$w_0$ 为全局 bias，$w_i$$w_i$ 建模第 $i$$i$ 个特征和 target 的交互。

   • ${\overrightarrow{\mathbf{v}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_i^\top \mathbf{\vec v}_j$ 表示分解的交互（factorized interaction），其中 ${\overrightarrow{\mathbf{v}}}_i\in {\mathbb{R}}^k$$\mathbf{\vec v}_i\in \mathbb R^k$ 为特征 $i$$i$ 的 embedding 向量，$k$$k$ 为 embedding 向量的维度。

     注意，由于存在系数 $x_i{x}_j$$x_ix_j$，因此只考虑非零特征的交互。

2. FM 的一个主要优势来自于它的通用性：与仅对两个实体关系进行建模的矩阵分解（matrix factorization: MF）相反，FM 是一个通用的预测器（predictor），可以与任何实值特征向量一起用于监督学习。

   显然，FM 使用特征之间的二阶分解交互（factorized interaction）增强了逻辑回归（logistic regression: LR）。通过指定 input 特征，论文 《Factorization machines》 表明FM 可以模拟很多特定的分解模型，例如标准的 MF、并行因子分析（parallel factor analysis）、SVD++。由于这种通用性，FM 被认为是稀疏数据预测的最有效的 embedding 方法之一。它已经成功应用于许多预测任务，从在线广告、微博检索，到开放关系抽取。

3. FM 的表达能力限制：尽管有效，我们指出 FM 仍然属于（多元）线性模型家族。换句话讲，预测目标 $\hat{y}\left(\overrightarrow{\mathbf{x}}\right)$$\hat y\left(\mathbf{\vec x}\right)$ 相对于每个模型参数是线性的。

   数学上，对于每个模型参数 $\theta \in \{w_0,\{w_i\},\{v_{i,f}\}\}$$\theta\in \left\{w_0,\{w_i\},\{v_{i,f}\}\right\}$，我们有 $\hat{y}\left(\overrightarrow{\mathbf{x}}\right)=g+h\theta$$\hat y\left(\mathbf{\vec x}\right) = g+h\theta$ ，其中 $g$$g$ 和 $h$$h$ 是独立于 $\theta$$\theta$ 的表达式。不幸的是，现实世界的底层结构通常是高度非线性的，无法被线性模型准确地近似。因此，FM 可能缺乏对具有复杂固有结构和规律的真实数据进行建模的表达能力（representation ability）。

   在方法论方面，已经开发了 FM 的很多变体。例如：

   • Co-FM 从多视图数据（multi-view data）中学习。

   • 《Predicting response in mobile advertising with hierarchical importance-aware factorization machine》 通过设计层级正则化器（hierarchical regularizer）将特征的先验知识编码到 FM。

   • field-aware FM: FFM 为每个特征学习多个 embedding 向量，从而区分与不同 field 的特征交互。

   • 最近，《Attentional factorization machines: Learning the weight of feature interactions via attention networks》 提出了 attentional FM ，使用注意力网络来学习每个特征交互的重要性。

   但是，这些变体都是 FM 的线性扩展，并且仅对二阶特征交互进行建模。因此，它们在建模真实世界数据时可能会遇到相同的表达能力不足的问题。

   在这项工作中，我们通过赋予 FM 非线性建模能力来改善 FM 的表达能力。核心思想是对二阶特征交互的潜在空间进行非线性变换，同时捕获高阶特征交互。

1.1.2 DNN

1. 近五年来，深度神经网络（deep neural network: DNN）取得了巨大的成功，并广泛应用于语音识别、计算机视觉、自然语言处理。然而，DNN 的使用在信息检索（information retrieval: IR）和数据挖掘（data mining: DM）社区中并不普遍。在我们看来，我们认为一个原因可能是 IR 和 DM 任务的大多数数据天然是稀疏的，例如用户行为、document/query 、以及从离散（categorical）变量转换而来的各种特征。尽管 DNN 表现出从稠密数据中学习模式的强大能力，但是在稀疏数据上使用 DNN 受到的审视（scrutiny）较少，并且不清楚如何在稀疏设置下使用 DNN 有效地学习特征交互。

   直到最近，一些工作开始在稀疏预测分析的某些场景中探索 DNN。

   • 论文 《Neural collaborative filtering》 提出了一个神经协同过滤 neural collaborative filtering: NCF 框架来学习用户和 item 之间的交互。

     后来NCF 框架被扩展为：针对属性感知协同过滤建模属性交互（attribute interaction）。然而，他们的方法仅适用于学习两个实体之间的交互，并不直接支持监督学习的一般设置（general setting）。

   • 《Deep learning over multi-field categorical data》 提出了 FNN，它使用 FM 预训练的feature embedding 来初始化 DNN。

   • 《Wide & deep learning for recommender systems》 提出了 Wide & Deep ，其中 deep 组件是位于特征 embedding 向量拼接之后的一个多层感知机（multi-layer perceptron: MLP），从而学习特征交互。

   • 《Deep crossing: Web-scale modeling without manually crafted combinatorial features》 提出了用于广告预测的 DeepCross，它与 Wide & Deep 共享一个类似的框架，但是通过 SOTA 的残差网络代替了 MLP 。

2. DNN 的优化困难：值得一提的是这些基于神经网络的方法的共同结构，即在 embedding 向量的拼接之后堆叠多层以学习特征交互。

   我们预期多层能够以隐式方式学习任意阶次的组合特征（combinatorial feature）。然而，我们发现这种架构的一个关键弱点是：简单地拼接特征 embedding 向量在底层（low level）上携带的关于特征交互的信息太少。一个经验证据来自于论文 《Neural collaborative filtering》，该论文表明：简单地拼接用户 embedding 向量和 item embedding 向量会导致协同过滤的结果非常差。为了解决这个问题，必须依靠后续的 deep 层来学习有意义的交互函数（interaction function）。虽然很多研究表明多个非线性层能够很好地学习特征交互，但是由于梯度消失（vanishing）/爆炸（exploding）、过拟合（overfitting）、退化（degradation）等臭名昭著的问题，这种深度架构在实践中可能难以优化。

   为了经验上证明 DNN 的优化困难，我们在 Frappe 数据及上绘制了 Wide & Deep 和 DeepCross 每个 epoch 的训练误差和测试误差，如下图所示。我们使用它们原始论文中报告的相同的架构和参数，其中 Wide & Deep 使用 3 层塔式结构， DeepCross 使用隐层维度逐渐降低的 10 层残差网络。

   从图 (a) 中可以看到：从头开始训练这两个模型导致的性能比浅层 FM 模型差很多。

   • 对于 Wide & Deep，训练误差相对较高，这很可能是因为模型退化（degradation）问题。

   • 对于 DeepCross，非常低的训练误差但很高的测试误差意味着模型过拟合。

   受到 FNN 的启发，我们进一步探索了使用 FM 学习的特征 embedding 来初始化 DNN，这可以看作是一个预训练步骤。从图 (b) 可以看到，这两个模型都实现了更好的性能（超过 11%）的提升。

   • 对于 Wide & Deep 而言，模型退化问题得到了很好的解决，训练误差要低得多，并且测试性能优于 LibFM。

   • 然而对于 10 层 DeepCross，它仍然存在严重的过拟合问题，并且表现不如 LibFM。

   

   这些相对负面的结果揭示了训练 DNN 的优化困难。

   在这项工作中，我们提出了一种新的、用于稀疏数据预测的神经网络范式。我们提出了一种新的双向交互Bi-Interaction 操作，而不是拼接特征 embedding 向量，该操作对二阶特征交互进行建模。这导致在底层（low level）上提供更多信息的 representation，极大地帮助后续的非线性层学习高阶交互。

1.2 模型

1. 我们首先提出 NFM 模型，该模型用于稀疏数据建模并结合了 FM 和神经网络的优势。然后我们讨论学习过程，以及如何在 NFM 中使用一些有用的技术，即 dropout、batch normalization 。

1.2.1 模型

1. 类似于 FM，NFM 是一个通用的机器学习器，可以处理任何实值特征向量。给定经过one-hot 编码之后的稀疏特征向量 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\mathbf{\vec x}\in \mathbb R^n$，其中特征 $x_i=0$$x_i=0$ 表示第 $i$$i$ 个特征不存在。则 NFM 的预测结果为：

   $${\hat{y}}_{\text{NFM}}(\overrightarrow{\mathbf{x}})=w_0+\overrightarrow{\mathbf{w}}\cdot \overrightarrow{\mathbf{x}}+f(\overrightarrow{\mathbf{x}})$$

   其中：

   • 第一项和第二项是类似于 FM 的线性回归（linear regression）部分，它对数据的全局 bias 和特征权重进行建模。

   • 第三项 $f(\overrightarrow{\mathbf{x}})$$f(\mathbf{\vec x})$ 是 NFM 用于建模特征交互的核心组件，它是一个多层前馈神经网络，包含 embedding层、Bi-Interaction 层、Hidden 层、输出层。如下图所示（仅仅包含 $f(\overrightarrow{\mathbf{x}})$$f(\mathbf{\vec x})$ ）。

     

2. Embedding 层：embedding 层是一个全连接层，将每个特征投影到一个稠密的向量 representation 。形式上，${\overrightarrow{\mathbf{v}}}_i\in {\mathbb{R}}^k$$\mathbf{\vec v}_i\in \mathbb R^k$ 是第 $i$$i$ 个特征的 embedding 向量。

   经过嵌入之后，则输入 $\overrightarrow{\mathbf{x}}=(x_1,x_2,\cdots ,x_n{)}^{\mathrm{\top }}$$\mathbf{\vec x}=(x_1,x_2,\cdots,x_n)^\top$ 就可以表示为：

   $${\mathcal{V}}_{\overrightarrow{\mathbf{x}}}=\{x_1{\overrightarrow{\mathbf{v}}}_1,x_2{\overrightarrow{\mathbf{v}}}_2,\cdots ,x_n{\overrightarrow{\mathbf{v}}}_n\}$$

   由于 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的稀疏性，${\mathcal{V}}_{\overrightarrow{\mathbf{x}}}$$\mathcal V_{\mathbf{\vec x}}$ 只需要保存非零的特征，即：

   $${\mathcal{V}}_{\overrightarrow{\mathbf{x}}}=\{x_i{\overrightarrow{\mathbf{v}}}_i\mid x_i\ne 0\}$$

   注意：这里使用输入特征 $x_i$$x_i$ 来调整 embedding 向量，而不是简单的从embedding table 中查找。这样做的好处是可以统一处理实值特（ real valued feature ）。

3. Bi-Interaction 层：然后我们将 embedding 集合馈入到 Bi-Interaction 层。Bi-Interaction 层是一个池化操作，将一组 embedding 向量转换为一个向量：

   $$f_{\text{BI}}\left({\mathcal{V}}_{\overrightarrow{\mathbf{x}}}\right)=\sum _{i=1}^n\sum _{j=i+1}^n{x}_i{\overrightarrow{\mathbf{v}}}_i\odot x_j{\overrightarrow{\mathbf{v}}}_j\in {\mathbb{R}}^k$$

   其中：

   • $\odot$$\odot$ 是逐元素乘法，即 ${({\overrightarrow{\mathbf{v}}}_i\odot {\overrightarrow{\mathbf{v}}}_j)}_k=v_{i,k}\times v_{j,k}$$\left(\mathbf{\vec v}_i\odot \mathbf{\vec v}_j\right)_k = v_{i,k}\times v_{j,k}$ 。

   • $f_{\text{BI}}\left({\mathcal{V}}_{\overrightarrow{\mathbf{x}}}\right)$$f_\text{BI}\left(\mathcal V_{\mathbf{\vec x}}\right)$ 是一个 $k$$k$ 维向量，它在 embedding 空间编码了二阶交叉特征。

   重要的是，Bi-Interaction 层可以在线性时间内高效计算。这个特性与平均池化/最大池化、拼接（concatenation）相同，它们相当简单且常用于神经网络方法。

   为了显示 Bi-Interaction 池化的线性时间复杂度，我们将上述方程重新表述为：

   $$f_{\text{BI}}({\mathcal{V}}_{\overrightarrow{\mathbf{x}}})=\frac{1}{2}[{\left(\sum _{i=1}^n{x}_i{\overrightarrow{\mathbf{v}}}_i\right)}^2-\sum _{i=1}^n{\left(x_i{\overrightarrow{\mathbf{v}}}_i\right)}^2]$$

   其中 ${\overrightarrow{\mathbf{v}}}^2$$\mathbf{\vec v}^2$ 表示 $\overrightarrow{\mathbf{v}}\odot \overrightarrow{\mathbf{v}}$$\mathbf{\vec v}\odot \mathbf{\vec v}$ 。

   由于输入 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的稀疏性，我们可以在 $O(k{n}_x)$$O(kn_x)$ 的时间内计算 Bi-Interaction 池化 ，其中 $n_x$$n_x$ 表示输入中非零项的数量。这是一个非常吸引人的特性，这意味着 Bi-Interaction 池化在建模 pairwise 特征交互时的优点是不涉及任何额外成本。

4. 隐层 （Hidden Layer）：在 Bi-Interaction 池化层之后堆叠了一组全连接层，这些全连接层能够学习特征之间的高阶交互。形式上，这些全连接层的定义为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_1={\sigma }_1({\mathbf{W}}_1{f}_{\text{BI}}({\mathcal{V}}_{\overrightarrow{\mathbf{x}}})+{\overrightarrow{\mathbf{b}}}_1)\\ {\overrightarrow{\mathbf{h}}}_2={\sigma }_2({\mathbf{W}}_2{\overrightarrow{\mathbf{h}}}_1+{\overrightarrow{\mathbf{b}}}_2)\\ ⋮\\ {\overrightarrow{\mathbf{h}}}_L={\sigma }_L({\mathbf{W}}_L{\overrightarrow{\mathbf{h}}}_{L-1}+{\overrightarrow{\mathbf{b}}}_L)\end{array}$$

   其中 $L$$L$ 表示隐层的数量，${\mathbf{W}}_l,{\overrightarrow{\mathbf{b}}}_l$$\mathbf W_l,\mathbf{\vec b}_l$ 表示第 $l$$l$ 层的待学习的权重矩阵、bias 向量，${\sigma }_l(\cdot )$$\sigma_l(\cdot)$ 表示第 $l$$l$ 层的激活函数。

   通过指定非线性激活函数，如 sigmoid、tanh、ReLU ，我们允许模型以非线性方式学习高阶特征交互。这优于现有的高阶交互学习方法，如高阶 FM 、Exponential Machine，它们仅支持以线性方式学习高阶交互。

   至于全连接层的结构（即每一层的 size ），可以自由选择塔式（tower） 、常数（constant） 、菱形（diamond）等等。

5. 预测层（Prediction Layer）：最后一个隐层的输出向量 ${\overrightarrow{\mathbf{h}}}_L$$\mathbf{\vec h}_L$ 被转换为 final prediction score：

   $$f(\overrightarrow{\mathbf{x}})={\overrightarrow{\mathbf{w}}}_f\cdot {\overrightarrow{\mathbf{h}}}_L$$

   其中 ${\overrightarrow{\mathbf{w}}}_f$$\mathbf{\vec w}_f$ 为预测层的权重。

6. 综上所述，NFM 的预测模型（predictive model）形式化为：

   $${\hat{y}}_{\text{NFM}}(\overrightarrow{\mathbf{x}})=w_0+\overrightarrow{\mathbf{w}}\cdot \overrightarrow{\mathbf{x}}+{\overrightarrow{\mathbf{w}}}_f\cdot {\sigma }_L({\mathbf{W}}_L(\cdots {\sigma }_1({\mathbf{W}}_1{f}_{\text{BI}}({\mathcal{V}}_{\overrightarrow{\mathbf{x}}})+{\overrightarrow{\mathbf{b}}}_1)\cdots )+{\overrightarrow{\mathbf{b}}}_L)$$

   模型的参数为：$\mathbf{\Theta }=\{w_0,\overrightarrow{\mathbf{w}},\{{\overrightarrow{\mathbf{v}}}_i\},{\overrightarrow{\mathbf{w}}}_f,\{{\mathbf{W}}_l,{\overrightarrow{\mathbf{b}}}_l\}\}$$\mathbf\Theta=\left\{w_0, \mathbf{\vec w},\{\mathbf{\vec v}_i\},\mathbf{\vec w}_f,\left\{\mathbf W_l,\mathbf{\vec b}_l\right\}\right\}$ 。和 FM 相比，NFM 的模型参数多了 $\{{\mathbf{W}}_l,{\overrightarrow{\mathbf{b}}}_l\}$$\left\{\mathbf W_l,\mathbf{\vec b}_l\right \}$ 的部分，这部分参数用于学习特征之间的高阶交互。

   接下来我们首先展示 NFM 如何推广 FM，并讨论 NFM 和现有深度学习方法之间的联系。然后我们分析评估了 NFM 模型的时间复杂度。

7. NFM 是 FM 的推广：FM 是一个浅层的线性模型，可以视为 NFM 没有隐层的一个特例。为了证明这一点，我们将 $L$$L$ 设为零，并直接将 Bi-Interaction 池化的输出投影到预测层。我们将这个简化模型称作 NFM-0，公式化为：

   $$\begin{array}{c}{\hat{y}}_{\text{NFM-0}}=w_0+\overrightarrow{\mathbf{w}}\cdot \overrightarrow{\mathbf{x}}+{\overrightarrow{\mathbf{w}}}_f\cdot (\sum _{i=1}^n\sum _{j=i+1}^n{x}_i{\overrightarrow{\mathbf{v}}}_i\odot x_j{\overrightarrow{\mathbf{v}}}_j)\\ =w_0+\overrightarrow{\mathbf{w}}\cdot \overrightarrow{\mathbf{x}}+\sum _{i=1}^n\sum _{j=i+1}^n\sum _{s=1}^k{w}_{f,s}{v}_{i,s}{v}_{j,s}\times x_i{x}_j\end{array}$$

   可以看到，当固定 ${\overrightarrow{\mathbf{w}}}_f=(1,1,\cdots ,1{)}^{\mathrm{\top }}$$\mathbf{\vec w}_f =(1,1,\cdots,1)^\top$ 时，我们可以准确恢复 FM 模型。

   值得指出的是，据我们所知，这是第一次在神经网络框架下表达 FM。而论文 《Polynomial networks and factorization machines: New insights and efficient training algorithms》 通过 kernelization 统一了 FM 和 Polynomial 网络，但是他们对 FM 的 kernel 视角仅提供了一种新的训练算法，并没有提供改进 FM 模型的见解。

   我们对 FM 的新观点具有很强的指导意义，并为改进 FM 提供了更多见解。特别是，我们允许在 FM 上使用各种神经网络技术来提高 FM 的学习能力和泛化能力。例如，我们可以在 Bi-Interaction 层使用 dropout （深度学习社区中一种众所周知的防止过拟合的技术）作为正则化 FM 的一种方式。在实验中我们发现，这比传统的 L2 正则化更有效。

8. NFM 和 Wide & Deep 以及 DeepCross 的关系：NFM 跟现有的几个深度学习解决方案具有类似的多层神经架构。主要区别在于 Bi-Interaction pooling 组件，这是 NFM 中特有的。

   具体而言，如果我们使用拼接操作来替代 Bi-Interaction 池化，并将塔式 MLP（或者残差单元）应用于隐层，那么我们可以恢复 Wide & Deep 模型（或 DeepCross 模型）。拼接操作的一个明显的缺点是它不考虑特征之间的任何交互。因此，这些深度学习方法必须完全依赖于后续的 deep layer 来学习有意义的特征交互。不幸的是，这在实践中很难训练。

   我们使用 Bi-Interaction 池化在底层 low level 捕获二阶特征交互，这比拼接操作提供更多信息。这极大地促进了 NFM 的后续隐层以更简单的方式学习有用的高阶特征交互。

9. 时间复杂度分析：可以在 $O(k{n}_x)$$O(kn_x)$ 时间内有效计算 Bi-Interaction 池化，这与 FM 相同。额外的计算成本是由隐层引起的。

   对于第 $l$$l$ 层隐层，计算复杂度为 $O(d_{l-1}\times d_l)$$O(d_{l-1}\times d_l)$，其中 $d_l$$d_l$ 表示第 $l$$l$ 层隐向量维度，$d_0=k$$d_0=k$ 。预测层仅涉及两个向量的内积，其复杂度为 $O(d_L)$$O(d_L)$ 。因此总的时间复杂度为：

   $$O(k\times n_x+\sum _{l=1}^L{d}_{l-1}\times d_l),d_0=k$$

   这与 Wide&Deep, DeepCrossing 的时间复杂度相同。

1.2.2 学习

1. NFM 可以应用于各种预测任务，包括回归、分类、排序（ranking）。为了估计 NFM 模型的参数，我们需要指定一个目标函数来优化。

   • 对于回归任务，一个常用的目标函数是平方损失：

     $$\mathcal{L}=\sum _{(\overrightarrow{\mathbf{x}},y)\in \mathbb{D}}{(\hat{y}(\overrightarrow{\mathbf{x}})-y)}^2$$

     其中：$\mathbb{D}$$\mathbb D$ 为训练集，$\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 为样本特征，$y$$y$ 为样本 label ，$\hat{y}(\overrightarrow{\mathbf{x}})$$\hat y(\mathbf{\vec x})$ 为样本的预测值。

     正则化项是可选的，这里省略了，因为我们发现神经网络建模中的一些技术，如 dropout 可以很好地防止 NFM 过拟合。

   • 对于分类任务，我们可以选择 hinge loss 或者 log loss。

   • 对于 ranking 任务，我们可以选择 pairwise personalized ranking loss 或者 contrastive max-margin loss 。

   在这项工作中，我们聚焦于回归任务并优化平方损失。ranking/classification 任务的优化可以用相同的方式完成。

2. 我们采用随机梯度下降 SGD 来优化神经网络模型。每轮迭代的模型参数更新为：

   $$\theta \leftarrow \theta -\eta \times 2(\hat{y}(\overrightarrow{\mathbf{x}})-y)\times {\mathrm{\nabla }}_{\theta }\hat{y}(\overrightarrow{\mathbf{x}})$$

   其中： $\theta \in \mathbf{\Theta }$$\theta\in \mathbf\Theta$ 为模型的可训练参数，$\eta >0$$\eta\gt 0$ 为学习率，${\mathrm{\nabla }}_{\theta }\hat{y}(\overrightarrow{\mathbf{x}})$$\nabla_\theta \hat y(\mathbf{\vec x} )$ 为模型输出相对于参数的梯度。

   例如 Bi-Interaction 池化层的参数梯度为：

   $$\frac{\partial f_{\text{BI}}({\mathcal{V}}_{\overrightarrow{\mathbf{x}}})}{\partial {\overrightarrow{\mathbf{v}}}_i}=\left(\sum _{j=1}^n{x}_j{\overrightarrow{\mathbf{v}}}_j\right)x_i-x_i^2{\overrightarrow{\mathbf{v}}}_i=\sum _{j=1,j\ne i}^n{x}_i{x}_j{\overrightarrow{\mathbf{v}}}_j$$

   其它层都是神经网络建模中的标准操作，已经在 TensorFlow 等机器学习工具包中广泛实现。

   因此，对于端到端的神经网络方法，在插入 Bi-Interaction 池化层之后，它们仍然可以端到端地学习。

3. Dropout：在 NFM 中，为了避免特征 embedding 相互协同适应（co-adapt）以及过拟合数据，我们建议在 Bi-Interaction 层之后采用 dropout 。具体而言，在获得一个 $k$$k$ 维的潜在因子向量 $f_{\text{BI}}\left({\mathcal{V}}_{\overrightarrow{\mathbf{x}}}\right)$$f_\text{BI}\left(\mathcal V_{\mathbf{\vec x}}\right)$ 之后，我们随机丢弃 $\rho$$\rho$ 比例的潜在因子，其中 $\rho$$\rho$ 称作 dropout rate 。

   由于没有隐层的 NFM 降级（degrade）为 FM 模型，因此可以将 dropout 视为正则化 FM 的一种新方法。

   此外，我们还在 NFM 的每个隐层上应用 dropout，从而防止从协同适应（co-adaptation）和过拟合（overfitting）中学习高阶特征交互。

4. Batch Normalization：在 NFM 中，为了避免特征 embedding 的更新改变了隐层或者预测层的输入，我们对 Bi-Interaction 的输出执行了 BN 。

1.3 实验

1. 在神经网络建模和用于稀疏数据预测的 NFM 设计中，我们进行了实验来回答以下研究问题：

   • RQ1：Bi-Interaction 池化能否有效捕获二阶特征交互？Bi-Interaction 的 dropout 和 batch normalization 如何工作？

   • RQ2：NFM 的隐层对于捕获特征之间的高阶交互和提高 FM 的表达能力（expressiveness）是否有用？

   • RQ3：与高阶 FM 和 SOTA 的深度学习方法 Wide & Deep 和 DeepCross 相比， NFM 表现如何？

   接下来我们将逐一回答上述问题。

2. 数据集：我们使用两个公开可用的数据集 Frappe 、MovieLens。

   • Frappe：给出了不同上下文时用户的 app 使用日志记录，一共包含 96203 个 app 。除了 userID, appID 之外，每条日志还包含 8个上下文特征：天气、城市、daytime（如：早晨、上午、下午） 等。

     采用 one-hot 编码之后，特征有 5382 维。label = 1 表示用户使用了 app 。

   • MovieLens：GroupLens 发布的最新 MovieLens 数据集的完整版，包含 17045 个用户在 23743 个 item 上的 49657 种不同的 tag 。这里我们研究个性化的 tag 推荐任务，而不是仅考虑二阶交互的协同过滤。

     将 userID,movieID,tag 进行 one-hot 编码之后，特征有 90445 维； label = 1 表示用户给 movie 贴了 tag 。

   由于两个原始数据集都只包含正样本（即所有样本的 label 都是 1 ），我们为每个正样本随机采样了两个负样本，从而确保预测模型的泛化。

   • 对于 Frappe 数据集，对每条记录，随机采样每个用户在上下文中未使用的其它两个 app 。

   • 对于 MovieLens 数据集，对每个用户每个电影的每个 tag，随机分配给该电影其它两个该用户尚未分配的 tag 。

   每个负样本的 label = -1。下表给出了最终评估数据集的统计数据。

   

3. 评估指标：我们将数据集随机划分为训练集（70%）、验证集（20%）、测试集（10%）。验证集用于调优超参数，并在测试集上进行最终的性能比较。为了评估性能，我们采用了均方根误差 RMSE，其中较低的 RMSE 得分表示更好的性能。

   • 对 NFM 属性的研究（即 RQ1 和 RQ2 的回答）是在验证集上进行的，这也可以反映我们如何选择最佳超参数。

   • 对于模型的预测结果，如果超出了 1 或者 -1 的范围，那么我们将结果截断为 1 或者 -1 。

   • 必要时我们进行 one-sample paired t-test 来判断统计显著性。

4. baseline 方法：我们使用 TensorFlow 实现了 NFM。我们和以下专为稀疏数据预测的、具有竞争力的、基于 embedding 的模型进行了比较：

   • LibFM：这是 Rendle 发布的 FM 的官方实现。它在个性化 tag 推荐和上下文感知预测方面具有强大的性能。我们使用 SGD learner 与其它所有使用 SGD （或者变体）优化的方法进行公平比较。

   • HOFM：这是高阶 FM 的 TensorFlow 实现，如论文 《Factorization machines》 所述。我们尝试了三阶，因为 MovieLens 数据涉及用户、电影、tag 之间的三元关系。

   • Wide & Deep：deep 部分首先拼接特征 embedding，然后是 MLP 对特征交互进行建模。由于 DNN 的结构难以完全调优（fully tuned），我们使用了与原始论文中报道的相同的结构：三层 MLP，隐层维度分别为 [1024, 512, 256]。

     虽然 wide 部分（这是一个线性回归模型）可以经过设计以包含交叉特征，但是我们使用原始特征，仅仅是为了和 FM, NFM 进行公平地比较。

   • DeepCross：它在特征 embedding 拼接之后应用多层残差网络来学习特征交互。我们使用了原始论文中报道的相同结构：五层残差单元（每层单元有两个子隐层），每个残差单元的维度为[512, 512, 256, 128, 64] 。

5. 超参数配置：

   • 为了公平地比较模型的能力，我们通过优化平方损失来学习所有模型。

   • 所有方法的学习率在 [0.005, 0.01, 0.02, 0.05] 之间搜索。

   • 为了防止过拟合，我们对线性模型 LibFM 和 HOFM 使用了 L2 正则化，正则化系数在 $[{10}^{-6},5\times {10}^{-6},\cdots ,{10}^{-1}]$$[10^{-6}, 5\times 10^{-6}, \cdots, 10^{-1}]$ 之间搜索。

   • 为了防止过拟合，我们对神经网络模型 Wide & Deep、DeepCross、NFM 使用了 dropout，dropout rate 在 [0, 0.1, 0.2, ..., 0.9] 之间搜索。

     注意，我们发现 dropout 可以很好地正则化 Wide & Deep 和 NFM 的隐层，但是对 DeepCross 的残差单元效果不佳。

   • 对于所有方法都执行了早停策略。如果验证集上的 RMSE 在 4 个连续的 epoch 中增加，我们就停止训练。

   • 除了使用平凡 SGD 优化 FM 的 LibFM 之外，所有其它方法都使用 mini-batch Adagrad 进行优化，其中：Frappe 的 batch size 设为 128，Movie-Lens 的 batch size 设为 4096 。

     注意，batch size 是通过考虑训练时间（training time）和收敛速度（convergence rate）来选择的，因为较大的 batch size 通常会导致每个 epoch 的训练速度更快，但是收敛速度较慢（需要更多的 epoch ）。

   • 如果没有特殊的说明，我们展示了 embedding size = 64 的结果。

1.3.1 RQ1: Bi-Interaction 池化的研究

1. 我们根据经验研究了 Bi-Interaction 池化操作。为了避免影响分析的其它组件（例如，隐层），我们研究了 NFM-0 模型，该模型直接将 Bi-Interaction 池化的输出投影到预估分而没有隐层。如前所述，NFM-0 和 FM 相同，因为可训练的 ${\overrightarrow{\mathbf{w}}}_f$$\mathbf{\vec w}_f$ 不影响模型的表达能力。我们首先将 dropout 和传统的 $L_2$$L_2$ 正则化进行比较以防止模型过拟合，然后探讨 batch normalization 的影响。

2. dropout 改进了泛化：下图显示了 NFM-0 验证误差相对于 Bi-Interaction 层 dropout rate 的关系，以及相对于 feature embedding 上 $L_2$$L_2$ 正则化的关系。我们使用线性回归（linear regression: LR）作为不考虑特征交互的 benchmark 性能。可以看到：

   • 首先，LR 导致了非常差的性能，这凸显了对稀疏特征之间的交互进行建模从而进行预测的重要性。

   • 其次，我们看到 $L_2$$L_2$ 正则化和 dropout 都可以很好地防止过拟合，并改善 NFM-0 对未见过（unseen）数据的泛化。在这两种策略之间，dropout 提供了更好的性能。

     具体而言，在 Frappe 上，使用 dropout rate = 0.3 导致最低的验证误差 0.3562，这明显优于 $L_2$$L_2$ 正则化的 0.3799 。一个原因可能是强制 $L_2$$L_2$ 正则化只会在数值上抑制每次更新中的参数值，而使用 dropout 可以被视为集成（ensembling）多个子模型，这可能更有效。

     考虑到很多因子分解模型都可以归为 FM模型，我们认为这是一个有趣的新发现，这意味着 dropout 也可以成为解决线性潜在因子模型过拟合的有效策略。

   

   为了更清楚地了解 dropout 的影响，我们在下图中展示了 NFM-0 有 dropout 和没有 dropout 在每个 epoch 的训练误差和验证误差。两个数据集都表明：采用了 dropout rate = 0.3 之后，虽然训练误差更高，但是验证误差更低。这证明了 dropout 在防止过拟合方面的能力，因此可以实现更好的泛化。

   

3. batch normalization 加速训练： 下图显示了在 Bi-Interaction 层上有 BN 和没有 BN 的 NFM-0 的每个 epoch 训练误差和验证误差。我们将 dropout rate 设为 0.3，并将学习率设为 0.02 。

   • 聚焦于训练误差，我们可以看到 BN 导致更快的收敛速度。在 Frappe 数据集上，应用 BN 时 epoch = 20 的训练误差甚至低于没有 BN 的 epoch = 60 ，并且验证误差表明更低的训练误差不是过拟合。

     事实上，《Batch normalization: Accelerating deep network training by reducing internal covariate shift》 表明：通过 BN 解决内部协变量偏移（shift），可以提高模型的泛化能力。我们的结果也验证了这一点，即，使用BN 会带来轻微的改进，尽管这个改进在统计上并不显著。

   • 此外，我们注意到 BN 使得学习不太稳定，蓝线的较大波动证明了这一点。这是由于我们同时使用 dropout 和 BN 造成的，因为随机 dropout 神经元可以改变 BN 的输入。如何有效地结合 BN 和 dropout 是一个有趣的方向。

1.3.2 RQ2: 隐层的影响

1. NFM 的隐层在捕获特征之间的高阶交互方面起着关键作用。为了探索影响，我们首先在 Bi-Interaction layer 之上添加一个隐层，并稍微过度使用 NFM 这个称呼来表示这个特定的模型。为了确保与 NFM-0 具有相同的模型容量（model capability）， 我们将隐层的维度设置为和 embedding 维度相同。

   下图显示了 NFM 验证误差相对于隐层的不同激活函数的关系，以及相对于隐层不同 dropout rate 的关系。我们将 LibFM 和 NFM-0 的性能作为 benchmark。可以看到：

   • 首先，我们观察到，通过使用非线性激活，NFM 的性能有很大的提高。和 NFM-0 相比，Frappe 和 MovieLens 上的相对提升分别为 11.3% 和 5.2% 。相对 LibFM 的提升也是类似的。这凸显了对高阶特征交互进行建模从而进行高质量预测的重要性。

     在不同的非线性激活函数中，没有明显的赢家。

   • 其次，当我们使用恒等映射作为激活函数时，即隐层执行线性变换，此时 NFM 表现不佳。这为采用非线性函数学习高阶特征交互的必要性提供了证据。

   

2. 为了了解更深的 NFM 是否进一步提高性能，我们在 Bi-Interaction layer 之上堆叠了更多的 ReLU 层。由于独立调整每个隐层的维度和 dropout rate 的计算成本很高，因此我们对所有层都使用相同的设置，并以与 NFM-1 相同的方式调整它们。

   从下表可以看出：当我们堆叠更多层时，性能并没有进一步提高，最佳性能是当我们仅使用一个隐层时。

   

   我们还探索了隐层的其它设计，例如塔式结构和残差单元，但是性能仍然没有提高。我们认为原因是因为 Bi-Interaction 层编码了信息丰富的二阶特征交互，基于此，一个简单的非线性函数就足以捕获高阶交互。

   为了验证这一点，我们使用拼接操作代替了 Bi-Interaction 层（这导致了与 Wide & Deep 相同的架构），并发现使用更多的隐层（最多三个）可以逐渐提高性能，然而可达到的最佳性能仍然不如 NFM-1。这证明了对底层（low-level layers）使用更有信息（informative）的操作的价值，这可以减轻高层学习有意义信息的负担。因此，不一定需要深层架构。

3. 预训练加速了训练过程：众所周知，参数初始化会极大地影响 DNN 的收敛性（convergence）和性能（performance），因为基于梯度的方法只能找到 DNN 的局部最优值。如前所述，使用 FM 预训练的feature embedding 进行初始化可以显著增强 Wide & Deep 和 DeepCross。

   

   那么，预训练如何影响 NFM？下图显示了有预训练和没有预训练的 NFM-1 在每个 epoch 的状态。可以看到：

   • 首先，通过使用预训练的 FM embedding ，NFM 表现出极快的收敛性。在两个数据集上，只有 5 个 epoch 的性能与从头开始（启用 BN ）训练的 NFM 的 40 个 epoch 性能相当。

   • 其次，预训练并没有提高 NFM 的最终性能，随机初始化可以获得比预训练初始化略好一些的结果。这证明了 NFM 的鲁棒性，它对参数初始化相对不敏感。

     和预训练对 Wide & Deep 和 DeepCross 的巨大影响（提高了模型的收敛性和最终性能）相比，我们得出的结论是 NFM 更容易训练和优化。这主要是由于Bi-Interaction 池化操作是有信息的（informative）以及有效的 （effective）。

   

1.3.3 RQ3: 性能比较

1. 我们现在与 SOTA 的方法进行比较。

   对于 NFM，我们使用一个带有 ReLU 激活函数的隐层，因为baseline 方法 DeepCross 和 Wide & Deep 在原始论文中也选择了 ReLU。

   注意，NFM 最重要的超参数是 dropout rate，我们对 Bi-Interaction layer 使用 dropout rate = 0.5，并调优隐层的 dropout rate。

   下图给出了测试 RMSE 和 embedding size 的关系，其中 Wide & Deep 和 DeepCross 使用 FM 预训练从而更好地探索这两种方法。LibFM, HOFM 是随机初始化。

   下表给出了在 embedding size = 128 和 256 上获得的具体得分，以及每种方法的模型参数数量。M 表示百万，** 表示相比较于最佳 baseline 具有统计显著性。在表中，我们还给出了没有采用预训练的 Wide & Deep 和 DeepCross 的分数。可以看到：

   • 首先，NFM 在两个数据集上一致地（consistently）实现了最佳性能，并且除了 FM 之外，模型参数最少。这证明了 NFM 在建模高阶特征交互和非线性特征交互从而进行稀疏数据预测方面的有效性和合理性。

     性能紧随其后的是 Wide & Deep，它使用 3 层 MLP 来学习特征交互。我们也为 Wide & Deep 尝试了更深的层，但是性能并没有得到改善。这进一步验证了在底层（low level）使用信息的（informative） Bi-Interaction 池化的效用。

   • 其次，我们观察到 HOFM 比 FM 略有改进，在 Frappe 和 MovieLens 上的平均改进分别为 1.45% 和 1.04%。这揭示了仅建模二阶特交互的 FM 的局限性，从而揭示了对高阶交互进行建模的有效性。

     同时，HOFM 和 NFM 之间的巨大性能差距反映了以非线性方式对高阶交互进行建模的价值，因为 HOFM 以线性方式建模高阶交互，并且使用的参数比 NFM 多得多。

   • 最后，DeepCross 相对较弱的性能表明，更深的学习并不总是更好，因为 DeepCross 是所有使用 baseline 中最深的模型，它使用 10 层网络。在 Frappe 上，DeepCross 仅实现了与浅层 FM 模型相当的性能；而在 Movielens 上，DeepCross 的性能明显低于 FM。我们认为原因在于优化困难和过拟合。