介绍
FM（Factorization Machines）是一个新模型：它会结合SVM和因子分解模型的优点。FM是一个通用预测器，可以很好地与实数值特征向量一起工作。对比SVM，FM模型会使用因子分解参数来对变量进行交叉。因而，我们可以估计推荐系统中海量稀疏性（huge sparsity）问题中的交叉（这种情况SVM会失败）。我们展示了FM的模型等式，它可以在线性时间内计算，因而FM可以直接进行最优化(optimize)。不同于非线性SVM需要以对偶式做转换，FM可以直接估计模型参数，无需求解任何支持向量（support vector）。本paper也展示了FM和SVM的关系，以及FM在稀疏（sparse）环境下的参数估计的优点。
另一方面，有许多不同的因子分解模型，比如：矩阵分解，并行因子分析模型（如：SVD++，PITF or FPMC）。这些模型的缺点是，不能应用于常见的预测任务（但对于一些特殊的输入数据管用）。这些模型等式和优化算法对于每个任务各不相同。我们展示了FM可以模仿这些模型，只需要指定输入数据（即：特征向量）即可。这让FM很容易使用，即使是对于那些在因子分解模型没有专家经验的用户。
1.介绍
SVM是最流行的预测器之一。然而，在协同过滤领域，SVM基本上毫无用武之地，该领域最好的模型是标准的矩阵/张量分解模型（matrix/tensor factorization model），比如：PARAFAC或者使用因子分解参数的特殊模型[2][3][4]。在本paper中，我们展示了为什么标准的SVM预测器在这些任务上不能成功的原因：在非常sparse的数据上，不能在复杂（非线性）kernel spaces上学到可靠的参数（超平面）。另一方面，张量分解模型的缺点是：
- (1) 它们不能应用于标准的预测数据（比如：在$R^n $ 空间中的实数值特征向量）
- (2) 对于特定的任务，需要在建模和算法设计时进行单独构建
在本paper中，我们引入了一个新的预测器，Factorization Machine(FM)，它是一个通用的预测器（类似于SVM），但也能在高度稀疏（sparsity）的数据下估计得到可靠参数。FM模型所有都嵌套着变量交叉（对比：在SVM中通过一个polynomial kernel），但它会使用一个因子分解参数（ factorized parametrization）的方法，而非SVM中的dense参数化（dense parametrization）。我们展示了FM的模型等式，它可以在线性时间内计算，只依赖于一个线性数量的参数。这允许直接优化和模型参数存储，无需存储任意训练中数据（比如：支持向量）来进行预测。对比于FM，非线性SVM通常以对偶形式（dual form）进行优化，依赖于训练中数据（支持向量）来计算预测。我们也展示了，FM把许多对于协同过滤任务的成功方法（biased MF, SVD++, PITF, FPMC）包含在内。
总之，我们提出的FM的优点有：
- 1) FM允许在非常sparse的数据（SVM会失败）上进行参数估计
- 2) FM具有线性复杂度，可以以原始形式优化，不需要依赖像SVM中的支持向量（SV）。我们展示了FM可以扩展到大数据集上（比如：Netflix 1000w训练实例）
- 3) FM是一个通用预测器，可以与任意实数型特征向量（real
valued feature vector）一起工作。对比于FM，其它state-of-art的因子分解模型非常受限于输入数据。我们将展示通过定义输入数据的特征向量，FM可以模仿state-of-the-art的模型（biased MF, SVD++, PITF, FPMC）。
2.sparsity下的预测
最常见的预测任务是：估计一个函数：
\[y : R^n \to T\]
从一个实数值特征向量 \(x \in R^n\)，到一个目标域T（比如：对于回归， T=R；对于分类，T={+, -}）。
在监督学习领域，假设存在一个训练样本数据集：\(D=\lbrace (x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), ... \rbrace\)，y为目标函数(target function)。我们也研究了排序任务，其中函数y的目标 T=R 可以被用于得分特征向量（score feature vectors）x，可以根据score进行排序。得分函数（score functions）可以通过pairwise的训练数据进行学习得到，其中特征tuple \((x^{(A)}, x^{(B)}) \in D\)意味着\(x^{(A)}\)的排序比\(x^{(B)}\)更高。由于pairwise的排序关系是不对称的（antisymmetric），只使用正例进行训练就足够了。
在本paper中，我们处理该问题，其中x是高度稀疏的（比如：向量x中几乎大多数元素\(x_i\)都是0)。假设m(x)是特征向量x中非零元素的数目，\(\bar{m}_{D}\)是所有向量 \(x\in D\)的m(x)的平均非零元素个数。现实世界中十分稀疏(huge sparsity )的情况很常见（\(\bar{m}_{D} \ll n\)），比如事件交互（推荐系统中的购买），或者文本分析（bag-of-word方法）。huge sparsity的一个原因是，需要处理海量的类别型变量域。
示例1：假设我们具有一个电影评论系统的交互数据。该系统记录了：用户\(u \in U\)对一部电影\(i \in I\)的评分，时间为\(t \in R\)，评分为\(r \in \lbrace 1,2,3,4,5 \rbrace\)。假设用户U和item I如下：
U = {Alice (A), Bob (B), Charlie (C), . . .}
I = {Titanic (TI), Notting Hill (NH), Star Wars (SW), Star Trek (ST), . . .}
观察到的数据S：
S = {(A, TI, 2010-1, 5),(A, NH, 2010-2, 3),(A, SW, 2010-4, 1),
(B, SW, 2009-5, 4),(B, ST, 2009-8, 5),
(C, TI, 2009-9, 1),(C, SW, 2009-12, 5)}
对于一个使用该数据的预测任务，目标是估计一个函数\(\hat{y}\)来预测：在某个时间点上，一个用户对一个item的评分行为。
图一：示例1的交互所创建的稀疏实数特征向量x。每一行表示了一个特征向量\(x^{(i)}\)，以及它对应的目标\(y^{(i)}\)，前4列（蓝色）表示用户的指示变量：接下来的5列（红色）表示item的指示变量。接下来的5列（黄色）持有着额外的隐式指示（比如：该用户评过分的其它电影）。一个特征（绿色）表示了月份时间。最后的5列（棕色）表示在该电影前评过分的最后一部电影。最右边的列是target：这是评分。
图1展示了特征向量是如何从S中被创建的。首先，\(|U|\)是个二元变量（蓝色），它表示了一个交互的当前用户————通常对于一个交互\((u,i,t,r) \in S\)只有一个用户，例如：在第一个（\(x_A^{(1)} =1\) ）的用户Alice。下一个\(|I|\)二元变量（红色）持有着item（例如：\(x_{T1}^{(1)}=1\)）。图1的特征向量还包含了该用户评分过的其它电影（黄色）。对于每个用户，变量被归一化成总和为1. 例如：Alice评分了Titanic，Notting Hill和 Star Wars。另外，该样本包含了月份时间。最后，该向量包含了评分前最后一部电影的信息。例如，对于\(x^{(2)}\)，Alice在对Notting
Hill评分前，就对Titanic进行了评分。在第V节，我们展示了FM使用这样的特征向量作为输入数据，并与state-of-art算法进行比较。
我们将使用该样本数据进行本paper的演示。然而，注意FM是通用的预测器，任何实数型特征向量都可以使用，并不局限于推荐系统。
3.FM
在本节中，我们引入了因子分解机（FM）。我们详细讨论了模型等式，简短展示了如何应用FM到一些预测任务上。
A.FM模型
1）模型等式（Model Equation）：阶(degree)为2，定义如下：
\[\hat{y}(x) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j\]
…(1)
其中，要估计的模型参数是：
\[w_0 \in R, w \in R^{n}, V \in R^{n * k}\]
…(2)
其中<.,.>是两个size=k的向量的点乘：
\[\langle v_i,v_j \rangle := \sum_{f=1}^{k} v_{i,f} \cdot v_{j,f}\]
…(3)
在V中的一行\(v_i\)描述了具有k个因子的第i个变量。\(k \in N_{0}^{+}\)是一个超参数，它定义了因子分解的维度。
一个2-way FM（degree d = 2）捕获了所有变量间的single和pairwise交叉：
- \(w_0\)是全局bias
- \(w_i\)建模了第i个变量的权重
- \(\hat{w}_{i,j} := \langle v_i, v_j \rangle\)建模了第i个和第j个变量间的交叉（interaction）。FM模型不会为每个交叉使用单独的模型参数\(w_{i,j} \in R\)，作为替代，FM模型通过对它进行因子分解（factorizing）来对交叉进行建模。稍后我们可以看到，对于稀疏的高阶交叉（d>=2）允许高质量参数估计，这就是其关键点。
2) 表现力（Expressiveness）：我们都知道：当k足够大时，对于任意正定矩阵W（positive definite matrix），存在一个矩阵V，使得 \(W=V \cdot V^t\)(Cholesky decomposition)。这表明：当k足够大时，一个FM可以表示任意交叉矩阵W。然而在稀疏情况下，通常会选择一个小k，因为没有足够多的数据来估计复杂交叉W。限制k（也就是限制FM的表现力)，可以产生更好的泛化，这样可以提升稀疏情况下的交叉矩阵。
3）稀疏条件下的参数估计：在sparse情况下，通常没有足够多的数据来直接地、独立地估计变量间的交叉（interactions）。FM可以在这样的情况下很好地估计交叉，因为他们通过对它们进行因子分解分离出交叉参数的独立性。总之，这意味着，对于一次交叉的数据可以帮助估计相关交叉的估计。以下的示例会利用来自图1的数据，使该思想更清晰。
假设：我们希望估计在Alice(A)和Star Trek（ST）间的交叉，来预测目标y（即rating）。很明显，在训练数据中，没有这样的样本x，同时满足\(x_A\)和\(x_{ST}\)都是非零的，因而一个直接的估计是没有交叉（\(W_{A,ST}=0\)）。但是，这种情况下的因子分解的交叉参数\(\langle v_A, v_{ST} \rangle\)是可以估计的。首先，Bob和Charlie具有相似的因子向量（factor vector）\(v_B\)和\(v_C\)，因为对于预测评分来说，两人与Star Wars（\(v_{SW}\)）的交叉相似：\(\langle v_B, v_{SW} \rangle\)和 \(\langle v_C, v_{SW} \rangle\)必须相似。相比之下，Alice（\(v_A\)）和Charlie(\(v_C\))之间会具有不同的因子向量（factor vector），因为在评分上，Alice与Titanic 和 Star Wars的因子也存在不同的交叉。另外，Star Trek的因子向量可能与Star Wars的相似，因为对于预测y来说，Bob与这两部电影具有相同的交叉。总之，这意味着，Alice和Star Trek的因子向量点积（交叉） ，将与Alice和Star Wars的因子向量点积相似——这在直观上是说得通的。
4）计算
接着，我们将展示如何从计算角度来让FM可用。等式(1)的计算复杂度是\(O(k n^2)\)，因为所有pairwise交叉必须被计算。但是，用公式重新表示会下降到线性运行时（linear runtime）。
引理3.1：FM的模型等式(1)可以以线性时间O(kn)被计算。
证明：由于pairwise型交叉（interaction）的因子分解，不存在直接依赖这两个变量的模型参数（例如：一个带有索引(i,j)的参数）。因而，pairwise的交叉可以重新进行公式化：
该等式具有O(kn)的线性复杂度
再者，在sparsity情况下，x中的大多数元素为0（例如：m(x)很小），因而，该求和可以通过非零元素的计算来得到。在sparse应用中，FM的计算复杂度为\(O(k \hat{m}_D)\)，例如：\(\hat{m}_D=2\)，对于常见的推荐系统，比如MF方法。
B.FM作为预测器
FM可以应用到许多预测任务中。比如：
- 回归：\(\hat{y}(x)\)可以直接用于预测，最优化准则可以是在D上最小化square error。
- 二元分类：\(sign(\hat{y}(x))\)，最优化准则可以使用hinge loss或者logit loss。
- 排序（Ranking）：向量x会通过\(\hat{y}(x)\)的得分进行重新排序，最优化通过实例向量对\((x^{(a)}, x^{(b)} \in D\)，根据pairwise classification loss进行分类。
在所有的case中，正则项L2通常被添加到目标函数上来进行优化来阻止overfit。
C.FM的学习
FM具有一个封闭(closed)的模型等式，可以在线性时间上计算。这样，FM的模型参数(w0, w和 V)——可以有效地通过梯度下降法学到。——例如SGD，计算square, logit or hinge loss。FM模型的梯度如下：
…(4)
\(\sum_{j=1}^{n} v_{j,f}x_j\)是与i独立的，可以预计算(例如：当计算 \(\hat{y}(x)\)时)。总之，每个梯度都可以在常数时间内被计算。对于(x,y)的所有参数更新可以在O(kn)——或者稀疏情况下O(km(x))时间内完成。
我们提供了一个泛化实现，LibSVM，使用SGD，并支持element-wise和pairwise loss。
D.d-way FM
2-way FM可以很容易泛化到d-way Fm上：
\(\hat{y}(x):=w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{l=2}^{d}\sum_{i_1=1}^{n}...\sum_{i_l=i_{l-1}+1}^{n} (\prod_{j=1}^{l} x_{i_j}) (\sum_{f=1}^{k_l}\prod_{j=1}^{l} v_{i_j,f}^{(l)})\) …(5)
其中，l次交叉的交叉参数可以通过使用以下模型参数的PARAFAC模型进行因子分解：
\(V^{(l)} \in R^{n * k_1}, k_l \in N_0^{+}\) …(6)
等式(5)的计算复杂度为 \(O(k_d n^d)\)。但与引理3.1有相近的参数，可以看到在线性时间内被计算。
E.总结
FM模型在特征向量x中的值之间所有可能的交叉，使用因子分解交叉（factorized interactions），而非完全参数化交叉（full parametrized）。这主要有两个优点：
- 1) 即使很稀疏，值之间的交叉可以被估计。尤其是，它可以泛化到未观察到的交叉
- 2) 参数的数目对于预测和训练时间是线性的。这可以使用SGD直接进行最优化，并可以使用多种loss。
与其它模型的对比
详见paper，此处不介绍.
https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf
