一、FFM [2016]

《Field-aware Factorization Machines for CTR Prediction》

1. click-through rate: CTR 点击率预估在计算广告中起着重要作用。逻辑回归可能是该任务中使用最广泛的模型。给定一个具有 $N$$N$ 个样本的数据集 ${\{{\overrightarrow{\mathbf{x}}}_i,y_i\}}_{i=1}^N$$\left\{\mathbf{\vec x}_i,y_i\right\}_{i=1}^N$，其中 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^K$$\mathbf{\vec x }_i\in \mathbb R^K$ 为输入的 $K$$K$ 维特征向量，$y_i$$y_i$ 为 label 。我们通过求解以下最优化问题从而得到逻辑回归模型：

   $$\underset{\overrightarrow{\mathbf{w}}}{min}\frac{\lambda }{2}\parallel \overrightarrow{\mathbf{w}}{\parallel }_2^2+\sum _{i=1}^N\log (1+\exp (-y_i{\varphi }_{\text{LM}}(\overrightarrow{\mathbf{w}},{\overrightarrow{\mathbf{x}}}_i)))$$

   其中： $\lambda \ge 0$$\lambda\ge 0$ 为正则化参数，${\varphi }_{\text{LM}}(\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}})=\overrightarrow{\mathbf{w}}\cdot \overrightarrow{\mathbf{x}}$$\phi_\text{LM}\left(\mathbf{\vec w},\mathbf{\vec x}\right) =\mathbf{\vec w}\cdot \mathbf{\vec x}$ 。

   学习特征交互效应看起来对 CTR 预估至关重要。这里我们考虑下表中的人造数据集，以便更好地理解特征交互，其中 + 表示点击量、- 表示不点击量。Gucci 的广告在 Vogue 上的点击率特别高，然而这些信息对于线性模型来说很难学习，因为线性模型分别学习 Gucci 和 Vogue 的两个权重。

   

   为了解决这个问题，已经有两个模型来学习特征交互效应：

   • 第一个模型是二次多项式映射（ degree-2 polynomial mapping: Poly2），为每个特征交互学习专门的权重。

   • 第二个模型是分解机（factorization machine: FM），通过将特征交互分解为两个潜在向量的乘积来学习特征交互效应。

   FM 的一种变体，称作成对交互张量分解 （pairwise interaction tensor factorization: PITF），用于个性化的 tag 推荐。在 2012 年的 KDD Cup 中，Team Opera Solutions 提出了一种称作因子模型（factor model）作为 PITF 的泛化，称作 field-aware factorization machine: FFM。

   PITF 和 FFM 的区别在于：PITF 考虑了 user、item、tag 三个特殊的字段（field），而 FFM 更加通用。由于 FFM 是针对比赛的整体解决方案，因此对它的讨论是有限的，主要包含以下结论：

   • FFM 使用随机梯度 SG 来解决优化问题。为了避免过拟合，Team Opera Solutions 只训练了一个 epoch。

   • FFM 在Team Opera Solutions 尝试的六个模型中表现最好。

   在论文 《Field-aware Factorization Machines for CTR Prediction》 中，作者旨在具体建立 FFM 作为 CTR 预估的有效方法。论文的主要结果如下：

   • 尽管 FFM 被证明是有效的，但是本文可能是唯一发表的、将 FFM 应用于 CTR 预估问题的研究。为了进一步证明 FFM 在 CTR 预估方面的有效性，作者使用 FFM 作为主要模型，从而赢得由 Criteo 和 Avazu 主办的两场全球 CTR 比赛。

   • 论文将 FFM 和两个相关模型 Poly2 和 FM 进行比较。作者首先从概念上讨论为什么 FFM 可能比它们更好，并通过实验来查看准确性和训练时间方面的差异。

   • 论文提出了训练 FFM 的技术，包括用于 FFM 的有效并行优化算法、以及早停以避免过拟合。

   • 为了让 FFM 可以被大家使用，论文发布了一个开源软件。

1.1 模型

1. 为便于讨论，这里忽略了全局bias 项和一阶项。给定特征向量 $\overrightarrow{\mathbf{x}}=(x_1,\cdots ,x_K)\in {\mathbb{R}}^K$$\mathbf{\vec x}=(x_1,\cdots,x_K)\in \mathbb R^K$，

   • POLY2 模型为：

     $$\begin{array}{c}\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{POLY2}}(\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}})=\sum _{i=1}^K\sum _{j=i+1}^K{w}_{i,j}\times x_i\times x_j\end{array}$$

     参数个数为 $O(K^2)$$O(K^2)$，计算复杂度为 $O(K^2)$$O(K^2)$ 。

   • FM 模型为：

     $$\begin{array}{c}\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{FM}}(\mathbf{V},\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^K{w}_i\times x_i+\sum _{i=1}^K\sum _{j=i+1}^K{\hat{w}}_{i,j}\times x_i\times x_j\\ {\hat{w}}_{i,j}=<{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>=\sum _{l=1}^d{v}_{i,l}\times v_{j,l}\end{array}$$

     参数个数为 $O(K\times d)$$O(K\times d)$，计算复杂度为 $O(K^2\times d)$$O(K^2\times d)$ 。

     通过重写上式：

     $$\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{FM}}(\mathbf{V},\overrightarrow{\mathbf{x}})=\frac{1}{2}\sum _{l=1}^d({(\sum _{i=1}^K{v}_{i,l}\times x_i)}^2-\sum _{i=1}^K{v}_{i,l}^2\times x_i^2)$$

     计算复杂度降为 $O(K\times d)$$O(K\times d)$ 。

2. Rendle 解释了为什么当数据集稀疏时，FM 可以比 Poly2 更好。这里我们用上述人工数据集给出类似的说明。

   例如，对于 pair (ESPN, Adidas) 只有一个负样本：

   • 对于 Poly2 ，可能会为 $w_{\text{ESPN,Adidas}}$$w_\text{ESPN,Adidas}$ 学习一个非常负的权重。

   • 对于 FM，因为 (ESPN, Adidas) 的预估取决于 ${\overrightarrow{\mathbf{v}}}_{\text{ESPN}}\times {\overrightarrow{\mathbf{v}}}_{\text{Adidas}}$$\mathbf{\vec v}_\text{ESPN}\times \mathbf{\vec v}_\text{Adidas}$，并且 ${\overrightarrow{\mathbf{v}}}_{\text{ESPN}}$$\mathbf{\vec v}_\text{ESPN}$ 和 ${\overrightarrow{\mathbf{v}}}_{\text{Adidas}}$$\mathbf{\vec v}_\text{Adidas}$ 也可以从其它pair 中学习（如 (ESPN,Nike), (NBC, Adidas)），所以预测会更准确。

   另一个例子是没有针对 (NBC, Gucci) 的训练数据：

   • 对于 Poly2，对这个pair 的预测是无意义的（trivial）。

   • 但是对于 FM，因为 ${\overrightarrow{\mathbf{v}}}_{\text{NBC}}$$\mathbf{\vec v}_\text{NBC}$ 和 ${\overrightarrow{\mathbf{v}}}_{\text{Gucci}}$$\mathbf{\vec v}_\text{Gucci}$ 仍然可以从其它 pair 中学习，因此仍然可以做出有意义的预测。

3. 注意，Poly2 的一种朴素实现是将每一对特征视为一个新特征，这使得模型的参数规模为 $O(K^2)$$O(K^2)$ 。由于 CTR 预估任务中的特征数量通常很大，因此Poly2 不可行。 Vowpal Wabbit: VW 这个广泛使用的机器学习 package 通过哈希来解决这个问题。我们的实现方法也类似，具体而言：

   $$\begin{array}{c}\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{POLY2}}(\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}})=\sum _{i=1}^K\sum _{j=i+1}^K{w}_{h(i,j)}\times x_i\times x_j\\ h(i,j)=(\frac{1}{2}(i+j)(1+j+1)+j)\mathrm{mod}B\end{array}$$

   其中 $B$$B$ 是一个用户指定的超参数。

4. FFM 的思想来源于个性化tag 推荐的 PITF。PITF 假设有三个可用字段，包括 User、Item、Tag，并且在独立的潜在空间中分解 (User, Item)、(User, Tag)、(Item, Tag)。FFM 将 PITF 推广到更多字段（如 AdID、AdvertiserID、UserID、QueryID），并将其有效地应用于 CTR 预估。

   由于 PITF 仅针对三个特定字段（User, Item, Tag），而 FFM 原始论文缺乏对 FFM 的详细讨论，因此这里我们提供了对 CTR 预估的 FFM 的更全面的研究。

5. 对于大多数 CTR 数据集，特征 features 可以分组为 fields。在我们前面的示例中，ESPN, Vogue, NBC 三个特征属于 Publisher 字段，另外三个特征 Nike, Gucci, Adidas 属于 Advertiser 字段。FFM 是利用字段信息的 FM 变体。

   为了解释 FFM 的工作原理，我们考虑以下示例：

   Publisher (P): ESPN; Advertiser (A): Nike; Gender (G): Male; Clicked: Yes
   

   考虑对于 FM，有：

   $$\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{FM}}(\mathbf{V},\overrightarrow{\mathbf{x}})={\overrightarrow{\mathbf{v}}}_{\text{ESPN}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Nike}}+{\overrightarrow{\mathbf{v}}}_{\text{ESPN}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Male}}+{\overrightarrow{\mathbf{v}}}_{\text{Nike}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Male}}$$

   在 FM 中，每个特征只有一个潜在向量来学习和其它特征的潜在效应（latent effect）。以 ESPN 为例，${\overrightarrow{\mathbf{v}}}_{\text{ESPN}}$$\mathbf{\vec v}_\text{ESPN}$ 用于学习和 Nike 的潜在效应（${\overrightarrow{\mathbf{v}}}_{\text{ESPN}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Nike}}$$\mathbf{\vec v}_\text{ESPN}\cdot \mathbf{\vec v}_\text{Nike}$）、和 Male 的潜在效应 （${\overrightarrow{\mathbf{v}}}_{\text{ESPN}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Male}}$$\mathbf{\vec v}_\text{ESPN}\cdot \mathbf{\vec v}_\text{Male}$） 。然而，因为 Nike 和 Male 属于不同的字段，(EPSN, Nike) 和 (EPSN, Male) 的潜在效应可能不一样。

   在 FFM 中，每个特征有若干个潜在向量，这依赖于其它特征的字段数量。例如在这个例子中：

   $$\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{FFM}}(\mathbf{V},\overrightarrow{\mathbf{x}})={\overrightarrow{\mathbf{v}}}_{\text{ESPN,A}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Nike,P}}+{\overrightarrow{\mathbf{v}}}_{\text{ESPN,G}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Male,P}}+{\overrightarrow{\mathbf{v}}}_{\text{Nike,G}}\cdot {\overrightarrow{\mathbf{v}}}_{\text{Male,A}}$$

   其中：

   • (ESPN, NIKE) 的潜在效应由 ${\overrightarrow{\mathbf{v}}}_{\text{ESPN,A}}$$\mathbf{\vec v}_\text{ESPN,A}$ 和 ${\overrightarrow{\mathbf{v}}}_{\text{Nike,P}}$$\mathbf{\vec v}_\text{Nike,P}$ 学习，因为 Nike 属于 Advertiser 字段、ESPN 属于 Publisher 字段。

   • (ESPN, Male) 的潜在效应由 ${\overrightarrow{\mathbf{v}}}_{\text{ESPN,G}}$$\mathbf{\vec v}_\text{ESPN,G}$ 和 ${\overrightarrow{\mathbf{v}}}_{\text{Male,P}}$$\mathbf{\vec v}_\text{Male,P}$ 学习，因为 Male 属于 Gender 字段、 ESPN 属于 Publisher 字段。

   • (Mike, Male) 的潜在效应由 ${\overrightarrow{\mathbf{v}}}_{\text{Nike,G}}$$\mathbf{\vec v}_\text{Nike,G}$ 和 ${\overrightarrow{\mathbf{v}}}_{\text{Male,A}}$$\mathbf{\vec v}_\text{Male,A}$ 学习，因为 Male 属于 Gender 字段、 Nike 属于 Advertiser 字段。

6. FFM 模型用数学语言描述为：

   $$\begin{array}{c}\hat{y}(\overrightarrow{\mathbf{x}})={\varphi }_{\text{FFM}}(\mathbf{V},\overrightarrow{\mathbf{x}})=\sum _{i=1}^K\sum _{j=i+1}^K{\hat{w}}_{i,j}\times x_i\times x_j\\ {\hat{w}}_{i,j}=<{\overrightarrow{\mathbf{v}}}_{i,f_j},{\overrightarrow{\mathbf{v}}}_{j,f_i}>=\sum _{l=1}^d{v}_{i,f_{j}l}\times v_{j,f_i,l}\end{array}$$

   其中： $f_i$$f_i$ 表示第 $i$$i$ 个特征所属的 field ，一共有 $F$$F$ 个field （$1\le F\le K$$1\le F\le K$ ）。

   参数数量为 $O(K\times d\times F)$$O(K\times d\times F)$ ，计算复杂度为 $O({\overline{K}}^2\times d)$$O(\bar K^2\times d)$ ，其中 $\overline{K}$$\bar K$ 是样本中平均非零特征数。

7. 和 FM 相比，通常 FFM 中 representation 向量的维度要低的多。即：

   $$d_{\text{FFM}}\ll d_{\text{FM}}$$

   .

1.2 优化算法

1. FFM 模型采用随机梯度下降算法来求解，使用 AdaGrad 优化算法。

   在每个迭代步随机采样一个样本 $(\overrightarrow{\mathbf{x}},y)$$(\mathbf{\vec x},y)$ 来更新参数，则 $\mathcal{L}$$\mathcal L$ 退化为：

   $$\mathcal{L}=\log (1+\exp (-y{\varphi }_{\text{FFM}}(\mathbf{V},\overrightarrow{\mathbf{x}})))+\sum _{\theta \in \mathbf{\Theta }}{\lambda }_{\theta }\times \frac{1}{2}{\theta }^2$$

   考虑全局bias 以及一阶项，并统一所有的 ${\lambda }_{\theta }=\lambda$$\lambda_\theta=\lambda$ ，则有：

   $$\begin{array}{c}{g}_{w_0}=\frac{\partial \mathcal{L}}{\partial w_0}=\lambda w_0+\kappa \\ {\overrightarrow{\mathbf{g}}}_{\mathbf{w}}={\mathrm{\nabla }}_{\overrightarrow{\mathbf{w}}}\mathcal{L}=\lambda \overrightarrow{\mathbf{w}}+\kappa \times \overrightarrow{\mathbf{x}}\\ {\overrightarrow{\mathbf{g}}}_{{\mathbf{v}}_{i,f}}={\mathrm{\nabla }}_{{\overrightarrow{\mathbf{v}}}_{i,f}}\mathcal{L}=\lambda {\overrightarrow{\mathbf{v}}}_{i,f}+\sum _{f_j\ne f}\kappa \times {\overrightarrow{\mathbf{v}}}_{j,f_i}\times x_i\times x_j\\ i=1,\cdots ,K;f=1,\cdots ,F\end{array}$$

   其中： $\sum _{f_j\ne f}$$\sum_{f_j\ne f}$ 表示field f 内的所有其它特征； $\kappa$$\kappa$ 表示：

   $$\kappa =\frac{\partial \log (1+\exp (-y\varphi ))}{\partial {\varphi }_{\text{FFM}}}=-\frac{y}{1+\exp (y{\varphi }_{\text{FFM}}(\overrightarrow{\mathbf{x}}))}$$

   • 对梯度的每个维度，计算累积平方：

     $$\begin{array}{c}{G}_{w_0}\leftarrow G_{w_0}+g_{w_0}^2\\ G_{w_i}\leftarrow G_{w_i}+g_{w_i}^2\\ G_{v_{i,f,l}}\leftarrow G_{v_{i,f,l}}+g_{v_{i,f,l}}^2\\ i=1,\cdots ,K;f=1,\cdots ,F;l=1,\cdots ,d\end{array}$$

     其中 $g_{w_i}$$g_{w_i}$ 是 ${\overrightarrow{\mathbf{g}}}_{\mathbf{w}}$$\mathbf{\vec g}_{\mathbf w}$ 的第 $i$$i$ 个分量，$i=1,2,\cdots ,K$$i=1,2,\cdots,K$ ；$g_{v_{i,f,l}}$$g_{v_{i,f,l}}$ 是 ${\overrightarrow{\mathbf{g}}}_{{\mathbf{v}}_{i,f}}$$\mathbf{\vec g}_{\mathbf{ v}_{i,f}}$ 的第 $l$$l$ 个分量，$l=1,2,\cdots ,d$$l=1,2,\cdots,d$ 。

   • 更新参数：

     $$\theta \leftarrow \theta -\frac{\eta }{\sqrt{G_{\theta }}}{g}_{\theta }$$

     其中 $\eta$$\eta$ 是用户指定的学习率， $\theta \in \{w_0,\overrightarrow{\mathbf{w}},{\overrightarrow{\mathbf{v}}}_{i,f}\}$$\theta \in \{w_0,\mathbf {\vec w},\mathbf{\vec v}_{i,f}\}$ 。

2. 模型参数需要合适的初始化。论文推荐：

   • ${\overrightarrow{\mathbf{v}}}_{i,f}$$\mathbf{\vec v}_{i,f}$ 从均匀分布 $[0,1/\sqrt{d}]$$[0,1/\sqrt d]$ 中随机初始化。

   • $G_{\theta }$$G_\theta$ 初始值为1，这是为了防止在迭代开始时 $\frac{1}{\sqrt{G_{\theta }}}$$\frac {1}{\sqrt{G_\theta}}$ 太大，从而导致前进方向较大的偏离损失函数降低的方向。

   原始论文并没有 $w_0,\overrightarrow{\mathbf{w}}$$w_0,\mathbf {\vec w}$ 的项，因此个人推荐采用零均值、方差为 $\sigma$$\sigma$ 的正态分布来初始化它们。

3. 论文推荐采用样本级别的归一化，这可以提升模型泛化能力。

   注：如果采用 Batch normalization 效果可能会更好。论文未采用 BN，是因为论文发表时 BN 技术还没有诞生。

4. FFM 的 AdaGrad 优化算法：

   • 输入：

     • 训练集 $\mathbb{S}$$\mathbb S$

     • 学习率 $\eta$$\eta$

     • 最大迭代步 $T$$T$

     • 初始化 $w_0,\overrightarrow{\mathbf{w}}$$w_0,\mathbf{\vec w }$ 的参数 $\sigma$$\sigma$

   • 输出：极值点参数 ${\mathbf{\Theta }}^{\ast }$$\mathbf \Theta^*$

   • 算法步骤：

     • 初始化参数和 $G_{\theta }$$G_{\theta}$：

       $$\begin{array}{c}{G}_{\theta }=1\\ (w_0,\overrightarrow{\mathbf{w}})\leftarrow \mathcal{N}(0,\sigma )\\ {\overrightarrow{\mathbf{v}}}_{i,f}\leftarrow [0,1/\sqrt{d}]\end{array}$$

     • 迭代 $T$$T$ 步，每一步的过程为：

       • 随机从 $\mathbb{S}$$\mathbb S$ 中采样一个样本 $(\overrightarrow{\mathbf{x}},y)$$(\mathbf{\vec x},y)$

       • 计算 $\kappa$$\kappa$ ：

         $$\kappa =-\frac{y}{1+\exp (y{\varphi }_{\text{FFM}}(\overrightarrow{\mathbf{x}}))}$$

       • 计算 $g_{w_0},G_{w_0}$$g_{w_0},G_{w_0}$，更新 $w_0$$w_0$

       • 遍历所有的项：$i=1,\cdots ,K$$i=1,\cdots,K$：

         • 计算 $g_{w_i},G_{w_i}$$g_{w_i},G_{w_i}$ ，更新 $w_i$$w_i$

         • 遍历所有的项：$j=i+1,\cdots ,K$$j=i+1,\cdots,K$

           • 计算 ${\overrightarrow{\mathbf{g}}}_{v_{i,f}}$$\mathbf{\vec g}_{v_{i,f}}$

           • 遍历所有的维度：$l=1,\cdots ,d$$l=1,\cdots,d$：计算 $G_{i,f,l}$$G_{i,f,l}$ ，并更新 $v_{i,f,l}$$v_{i,f,l}$

1.3 field 分配

1. 大多数数据集的结构是 ：

   xxxxxxxxxx
   label  feat1:val1 feat2:val2 ...,
   

   其中 (feat:value) 表示特征索引及其取值。对于 FFM，我们扩展上述格式为：

   xxxxxxxxxx
   label field1:feat1:val1 field2:feat2:val2
   

   也就是我们必须为每个特征分配相应的字段。

   为某些类型的特征分配字段很容易，但是对于其他一些特征可能比较困难。接下来我们在三种典型类型的特征上讨论这个问题。

2. 离散型特征（ categorical ）：通常对离散型特征进行 one-hot 编码，编码后的所有二元特征都属于同一个 field 。例如，性别字段：G:G-Male:1、G:G-Male:0 。

3. 数值型特征（ numuerical）：数值型特征有两种处理方式：

   • 不做任何处理，简单的每个特征分配一个dummy field 。此时 $F=K$$F=K$ ， FFM 退化为 Poly2 模型。例如论文引用量 Cite:Cite:3，其中分配的字段和特征名相同。

   • 数值特征离散化之后，按照离散型特征分配 field 。例如，论文引用量 Cite:3:1，其中 3 表示特征名（桶的编号）。

     论文推荐采用这种方式，缺点是：

     • 难以确定合适的离散化方式。如：多少个分桶？桶的边界如何确定？

     • 离散化会丢失一些信息。

4. 离散集合特征（categorical set）（论文中也称作 single-field 特征）：所有特征都属于同一个field，此时 $F=1$$F=1$ ， FFM 退化为 FM 模型。

   如 NLP 情感分类任务中，特征就是单词序列。

   • 如果对整个sentence 赋一个field，则没有任何意义，因为此时可能的特征范围是天文数字。

   • 如果对每个word 赋一个 field，则 $F$$F$ 等于词典大小，计算复杂度 $O(FKd)$$O(FKd)$ 无法接受。

1.4 实验

1. 这里我们首先提供实验配置的细节，然后我们研究超参数的影响。我们发现，和逻辑回归以及 Poly2 不同，FFM 对 epoch 数量很敏感，因此我们提出了早停策略。最后我们将 FFM 和包括 Poly2, FM 在内的其它 baseline 进行对比，除了预估准确性之外我们还对比了训练时间。

2. 数据集：我们主要考虑来自 Kaggle 比赛的两个数据集 Criteo 和 Avazu。对于特征工程，我们主要应用了我们的成功方案，但是移除了复杂的部分。例如，我们在 Avazu 数据集的成功方案包含了 20 个模型的 ensemble，但是这里我们仅使用最简单的一个。另外，我们使用哈希技巧里生成 ${10}^6$$10^6$ 个特征。这两个数据集的统计信息如下：

   

   对于这两个数据集，测试集中的标签都是不可用的，所以我们将可用的数据分为训练集和验证集，拆分方式为：对于 Criteo，最后 6040618 行用于验证集；对于 Avazu，最后 4218938 行用于验证集。我们用以下术语来表示各个不同的数据集：

   • Va：上述拆分的验证集。

   • Tr：从原始训练集中剔除验证集之后，得到的新训练集。

   • TrVa：原始的训练集。

   • Te：原始的测试集，其 label 未公布，所以我们必须将我们的预测结果提交给评估系统从而获得 score 分。为了避免测试集过拟合，竞赛组织者将该数据集分为两个子集：public set （竞赛期间 score 可见）、private set（竞赛期间 score 不可见且只有竞赛结束后 score 才公布）。最终排名由 private set 决定。

3. 配置：所有实验都是在 Linux 工作站上运行，该工作站配置为两个 Intel Xeo E6-2620 2.0GHz 处理器、128GB 内存。

4. 评估指标：我们考虑 logloss 作为评估指标，其中：

   $$\text{logloss}=\frac{1}{m}\sum _{i=1}^m\log (1+\exp (-y_i\varphi (\mathrm{\Theta },{\overrightarrow{\mathbf{w}}}_i)))$$

   其中：

   • $m$$m$ 为测试样本数量，$y_i$$y_i$ 为测试样本 label 。

   • $\mathrm{\Theta }$$\Theta$ 为模型参数，$\varphi (\cdot )$$\phi(\cdot)$ 根据不同的模型可以为 ${\varphi }_{\text{LM}},{\varphi }_{\text{Poly2}},{\varphi }_{\text{FM}},{\varphi }_{\text{FFM}}$$\phi_\text{LM},\phi_\text{Poly2},\phi_\text{FM},\phi_\text{FFM}$ 。

5. 超参数影响：我们评估了超参数 $d$$d$ （representation 向量维度）、$\lambda$$\lambda$ （正则化项系数）、$\eta$$\eta$ （学习率）的影响。所有结果都是在验证集上得到。为了加快实验，我们从 Criteo新训练集中随机抽取 10% 样本作为训练集、从 Criteo验证集中随机选择 10% 样本作为测试集。

   • 超参数 $d$$d$ 的实验效果如下图所示。第一列为不同 $d$$d$ 的取值（论文中用 k 这个不同的符号），第二列为平均每个epoch 的计算时间，第三列为验证集的 logloss 。

     可以看到：不同的representation 向量维度，对模型的预测能力影响不大，但是对计算代价影响较大。所以在 FFM 中，通常选择一个较小的 $d$$d$ 值。

     注意，由于采用了 SSE 指令集，所以 $d=1,2,3$$d=1,2,3$ 时每个 epoch 计算时间几乎相同。

     

   • 超参数 $\lambda$$\lambda$ 的实验效果如下图所示。可以看到：

     • 如果正则化系数太小，则模型太复杂，容易陷入过拟合。

     • 如果正则化系数太大，则模型太简单，容易陷入欠拟合。

     一个合适的正则化系数不大不小，需要精心挑选。

     

   • 学习率 $\eta$$\eta$ 的实验效果如下图所示：可以看到：

     • 如果学习率较小，虽然模型可以获得一个较好的性能，但是收敛速度很慢。

     • 如果学习率较大，则目标函数很快下降，但是目标函数不会收敛到一个较低的水平。

     

6. 早停：FFM 对于训练 epoch 次数很敏感。为解决该问题，我们对 FFM 执行早停策略：

   • 首先将数据集拆分为训练集、验证集。

   • 在通过训练集训练的每个 epoch 结束时，计算验证集的 logloss 。

   • 如果验证集的 logloss 上升，则记录当前已训练的 epoch 次数 ${\text{epoch}}_{best}$$\text{epoch}_{best}$，并停止当前训练。

   • 最后用全量训练数据重新训练模型 ${\text{epoch}}_{best}$$\text{epoch}_{best}$ 个 epoch 。

   该方案存在一个潜在的缺点：logloss 对 epoch 次数高度敏感，以及验证集上的最佳 epoch 不一定是测试集上的最佳 epoch。因此早停得到的模型无法保证在测试集上取得最小的 logloss 。

   我们也尝试了其它的避免过拟合的方法，比如 lazy update 和 ALS-based 优化，但是这些方法效果都不如早停策略。

7. 我们在 Criteo 和 Avazu 数据集上比较了不同算法、不同优化方式、不同超参数的结果。

   我们选择了四种算法，包括LM 模型（线性模型）、POLY2 模型、FM 模型、FFM 模型。我们选择了三种优化算法，包括SG （随机梯度下降）、CD（坐标下降）、Newton（牛顿法）、ALS 。另外我们还选择了不同超参数。

   • LIBFM 支持SG,ALS,MCMC 三种优化算法，但是我们发现 ALS 效果最好。因此这里 LIBFM 使用 ALS 优化算法。

   • FM、FFM 都是基于 SG 优化算法来实现的，同时对于 SG 优化算法采取早停策略。

   • 对于非 SG 优化算法，停止条件由各算法给出合适的停止条件。

   从实验结果可以看到：

   • FFM 模型效果最好，但是其训练时间要比 LM 和 FM 更长。

   • LM 效果比其它模型都差，但是它的训练要快得多。

   • FM 是一种较好的平衡了预测效果和训练速度的模型，这就是效果和速度的平衡。

   • POLY2 比所有模型都慢，因为其计算代价太大。

   • 从两种 FM 的优化方法可见，SG 要比 ALS 优化算法训练得快得多。

   • 逻辑回归是凸优化问题，理论上 LM 和 POLY2 的不同优化算法应该收敛到同一个点，但实验表明并非如此。原因是：我们并没有设置合适的停止条件，这使得训练过程并没有到达目标函数极值点就提前终止了。

   

8. 我们比较了其它数据集上不同模型的表现。其中：

   • KDD2010-bridge,KDD2012,adult 数据集包含数值特征和离散特征，我们将数值特征执行了离散化。

   • cod-rna,ijcnn 数据集仅仅包含数值特征 ，我们将数值特征进行两种处理从而形成对比：将数值特征离散化、每个数值特征作为一个field （称作 dummy fields ）。

   • phishing 数据集仅仅包含离散特征。

   实验结果表明：

   • FFM 模型几乎在所有数据集上都占优。这些数据集的特点是：

     • 大多数特征都是离散的。

     • 经过 one-hot 编码之后大多数特征都是稀疏的。

   • 在 phishing,adult 数据集上 FFM 几乎没有优势。原因可能是：这两个数据集不是稀疏的，导致 FFM,FM,POLY2 这几个模型都具有几乎相同的表现。

   • 在 adult 数据集上LM 的表现和 FFM,FM,POLY2 几乎完全相同，这表明在该数据集上特征交互几乎没有起到什么作用。

   • 在 dummy fields 的两个数据集上 FFM 没有优势，说明 field 不包含任何有用的信息。

   • 在数值特征离散化之后，尽管 FFM 比 FM 更有优势，但还是不如使用原始数值特征的 FM 模型。

     这说明数值特征的离散化会丢失一些信息。

   

9. 从实验中总结的 FFM 应用场景：

   • 数据集包含离散特征，且这些离散特征经过one-hot 编码。

   • 经过编码后的数据集应该足够稀疏，否则 FFM 无法获取较大收益（相对于 FM ）。

   • 不应该在连续特征的数据集上应用 FFM，此时最好使用 FM 。