@TOC
论文名称：Factorization Machines
原文地址：FM
⚡本系列历史文章⚡
【推荐系统论文精读系列】(一)--Amazon.com Recommendations
【推荐系统论文精读系列】(二)--Factorization Machines
【推荐系统论文精读系列】(三)--Matrix Factorization Techniques For Recommender Systems
【推荐系统论文精读系列】(四)--Practical Lessons from Predicting Clicks on Ads at Facebook
【推荐系统论文精读系列】(五)--Neural Collaborative Filtering
【推荐系统论文精读系列】(六)--Field-aware Factorization Machines for CTR Prediction
【推荐系统论文精读系列】(七)--AutoRec Autoencoders Meet Collaborative Filtering
【推荐系统论文精读系列】(八)--Deep Crossing：Web-Scale Modeling without Manually Crafted Combinatorial Features
【推荐系统论文精读系列】(九)--Product-based Neural Networks for User Response Prediction
【推荐系统论文精读系列】(十)--Wide&Deep Learning for Recommender Systems
【推荐系统论文精读系列】(十一)--DeepFM A Factorization-Machine based Neural Network for CTR Prediction
【推荐系统论文精读系列】(十二)--Neural Factorization Machines for Sparse Predictive Analytics
一、摘要
本篇论文中，作者介绍了一个新的分解模型Fatorization Machines（FM），它结合了支持向量机的一些优点。与SVM一样，FM模型是一个通用的预测分类器适用于任何真实值的向量。但是与SVM不同的是，FM通过使用分解参数的方式在不同变量之间进行建模。因此即使是在巨大的稀疏情况（像推荐系统）也就是SVM失败的时候，FM同样也能够进行估计交互矩阵。我们将展示FM的模型方程，它能够在线性的时间进行计算，因此FM模型能够直接的进行优化。因此它不像一些非线性模型，一个对偶形式的转化是不必要的并且模型参数能够直接的被进行估计计算不需要任何支持向量。我们将在下文展示支持向量机和FM的关系和一些优缺点在稀疏情况下的参数估计。
另外一个方面就是现在有很多不同的分解模型，像矩阵分解模型、并行因子分析或者特定的一些模型，像SVD++，PITE，FPMC。这些模型的缺点就是它们不适用于一般的预测任务，特们只适用于特定的输入数据。而且它们的模型方程和优化算法都独立的源自不同的任务。我们展示了FM模型能够模型这些模型只需要指定数据数据，也就是说特征向量。这使得FM模型很容易使用，尽管是那些在矩阵分解领域没什么专业知识的人员。
二、介绍
支持向量机是最受欢迎的预测器之一在机器学习和数据挖掘领域。然而像在协同过滤这种情况下，SVM几乎不发挥任何作用，而且最好的模型要门是直接应用标准矩阵或者张量分解的模型像PARAFAC，要么就是一些特定的模型使用分解的参数。在本篇论文中，我会展示标准的支持向量机不成功的唯一原因，就是它不同够学习到可靠的参数（超平面）在非线性和空间中当数据稀疏性过大的时候。另外一方面就是张量分解模型和甚至那些特定的分解模型，它们不适用于一般的预测数据，并且它们都是源自特定的任务需求，它们需要独立的进行建模并且为它们设计专门的学习算法。
本篇论文中，我们会介绍一个新的预测器，Factorization Machine（FM），是一个和SVM很像的一个通用预测器，而且它也能够估计出可靠的参数子在矩阵极度稀疏下。FM模型对交互变量进行嵌套建模，使用一个分解的参数代替SVM中稠密的参数。FM的模型方程可以在线性时间被计算出来并且它仅仅依赖线性个数的参数。者使得它可以直接进行优化并且不需要存储任何训练数据（支持向量）的参数去进行预测。不同的是，非线性SVM通常被优化是以一种对偶的形式并且计算一个预测依靠支持向量。我们也验证了FM包含一些最成功的方法对于协同过滤任务，例如biased MF，SVD++，PITF，FPMC。
总的来说，我们建议FM的优点有以下几条：
- FMs允许在数据非常稀疏的情况下进行参数估计
- FMs有线性的复杂度，能够在原始的状态下被优化并且不依赖任何支持向量。而且他还适用于例如Netflix公司的1亿数据量
- FMs是一个通用的预测器能够适用于任何值的特征向量，相反，一些先进的分解模型仅仅适用于一些特定的数据，通过指定输入数据的特征向量，FMs就能够模仿先进的模型例如biased MF，SVD++，PITF，FPMC。
三、稀疏性下预测
最普遍的预测任务就是估计一个映射函数
本篇论文中，我们会处理的特征向量会非常稀疏的，几乎所有的元素
一个预测任务的例子就是使用上面那些数据，为了去估计出一个函数
示例1展示了一个例子就是特征向量是怎样从集合S中创建出来的。这里首先有
我们将会使用这些示例数据贯穿整篇论文进行阐述。然后请注意FMs是通用的预测器像SVMs一样，并且因此是适用于任何值的特征向量，而且不只限制于推荐系统。
四、分解机（FM）
在这个部分，我们会介绍分解机模型FMs。我们会详细的讨论模型方程并且简要的展示怎样应用FMs到几个预测任务。
A. Factorization Machine Model
1）模型方程：对于一个分解机模型度为2的模型方程被定义为：
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
2-way FM（d=2）捕捉了所有单一和成对的变量之间的交互：
-
：它是全局的偏置网络异常，图片无法展示|
-
：它是特征i的权重系数网络异常，图片无法展示|
-
：它描述的是两个不同特征之间的权重系数，在SVM中使用权重系数网络异常，图片无法展示|，而FMs通过分解它来描述交互情况，我们将会看到，这就是关键的地方允许高质量的参数估计即使是在高度系数的情况。网络异常，图片无法展示|
2）模型表达能力：任何被明确被定义的矩阵W都可以存在一个矩阵V，使得
3）稀疏情况下的参数估计：在稀疏的情况下，通常是没有足够的数据去直接估计变量之间的交互。但是FMs在这种情况下可以进行估计，因为它通过分解参数打破了参数之间的独立性。我们将会利用这个想法去解释示例1。假设我们想要估计Alice和Star Trek之间的交互然后去预测目标y（这里是评分）。很明显，在训练集中是没有这样的特征向量的二者都为非0值，因此直接进行估计可能会导致变量之间没有交互，也就是说权重为0。但是通过分解权重系数即使是在这种情况下我们也可以进行参数估计。首先，Bob和Charlie将会有相同的特征
4）计算：接下来，我们将会展示如何对FMs进行计算。模型方程（1）的复杂度为
定义3.1：模型方程可以在线性时间（
证明：由于是分解成对的参数，所以模型没有直接依赖的变量。所以成对交互能够重新被调整。
这个方程仅仅是线性复杂度，k和n（
而且，在稀疏情况下大多数的元素都是0，因此计算的都是非0的元素。因此在稀疏情况下，矩阵分解将被计算到
B. Factorization Machines as Predictors
FM能够被应用于不同的预测任务中：
- Regression：
能够直接的使用作为预测器，并且优化指标可以是最小平方误差。网络异常，图片无法展示|
- Binary classification：
可以被使用并且参数可以被优化使用 hinge loss或者logit loss。网络异常，图片无法展示|
- Ranking：向量 x被
的分数进行排序，然后被优化使用成对的分类loss。网络异常，图片无法展示|
在所有这些情况中，正则化术语L2通常会被加入到优化中为了防止过拟合。
C. Learning Factorization Machines
正如我们所展示，FMs有一个封闭的模型方程能够在线性时间被计算，因此模型参数能够被有效的学习通过使用梯度下降法，例如随机梯度下降（SGD），对于不同的损失，一般是平方误差，对数或者合页误差。梯度FM模型为：
总的来说，每个梯度能够在常数时间
我们提供了一个通用的实现，就是使用SGD和支持元素成对和损失成对。
D. d-way Factorization Machine
2-way FM能够很容易的被d-way FM所概括：
这个交互参数对于第l个特征交互被分解通过PARAFAC模型。
这个模型可以直接计算复杂度为
E. Summary
FMs通过使用分解交互参数替代使用全参数，来为特征向量之间的参数进行建模，这主要有两个主要的优势：
1）变量之间的交互甚至可以在极度稀疏的情况下进行评估参数，特别地，它很有可能产生未观察到的交互。
2）参数的数量对于学习和预测都是线性的，这使得可以直接使用SGD进行优化并且允许使用不同的损失函数。
在文章的剩余部分，我们将会展示FMs和SVMs、矩阵张量或者特定的分解模型之间的不同。
五、FMs vs. SVMs
A. SVM model
支持向量机的模型方程可以被输入数据特征之间的点积进行表达，
在下文，我们会讨论FMs和SVMs的关系通过分析SVMs的原始形式：
1）Linear kernel：
最简单的核函数就是线性核，
很明显线性核SVM是相同的和使用FMs对应degree=1。
2）Polynomial kernel：
多项式核允许SVM模型去对变量之间的交互进行更高的建模，它被定义为
所以，多项式核函数的模型方程能够重新定义为：
对比多项式核的SVM核FMs，能够看出模型对所有变量之间进行度为2的嵌套交互建模。主要的不同就是参数方式不同。SVMs中所有的参数
B. Parameter Estimation Under Sparsity
下面，我们将会展示为什么线性核和多项式核的SVM会失败在一些非常稀疏的问题上。我们将会展示这个一协同过滤的例子，用户核物品之间的指示变量。这里特征向量是非常稀疏的并且仅仅有两个元素是非0值（活跃用户u核活跃物品i）。
1）Linear SVM：
对于数据x，Linear SVM等价于：
因为
2）Polynomial SVM：
有了多项式核，SVM能够捕捉高阶的交互（用户和物品之间）。在我们的稀疏例子中，
首先，
对于SVMs，评估高阶的参数交互不仅是在CF中，在很多稀疏矩阵的情况都会出现这个问题，因为对于一个可靠的评估参数
C. Summary
1）SVMs的参数稠密需要直接的观测值，但是通常情况下这在稀疏情况下是很难达到的。FMs的参数能够被评估甚至是在很稀疏的情况下。
2）FMs能够直接在原始的情况下进行学习。非线性核的SVMs通常是以对偶形式进行学习。
3）FMs的模型方程式独立于训练集的，SVMs的预测是依赖于部分训练集的（支持向量）。
References
[1] R. A. Harshman, “Foundations of the parafac procedure: models and conditions for an ’exploratory’ multimodal factor analysis.” UCLA Working Papers in Phonetics, pp. 1–84, 1970.
[2] Y. Koren, “Factorization meets the neighborhood: a multifaceted collaborative filtering model,” in KDD ’08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2008, pp. 426–434.
[3] S. Rendle and L. Schmidt-Thieme, “Pairwise interaction tensor factorization for personalized tag recommendation,” in WSDM ’10: Proceedings of the third ACM international conference on Web search and data mining. New York, NY, USA: ACM, 2010, pp. 81–90.
[4] S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme, “Factorizing personalized markov chains for next-basket recommendation,” in WWW ’10: Proceedings of the 19th international conference on World wide web. New York, NY, USA: ACM, 2010, pp. 811–820.
[5] T. Joachims, “Optimizing search engines using clickthrough data,” in KDD ’02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2002, pp. 133–142.
[6] V. N. Vapnik, The nature of statistical learning theory. New York, NY, USA: Springer-Verlag New York, Inc., 1995.
[7] N. Srebro, J. D. M. Rennie, and T. S. Jaakola, “Maximum-margin matrix factorization,” in Advances in Neural Information Processing Systems 17. MIT Press, 2005, pp. 1329–1336.
[8] R. Salakhutdinov and A. Mnih, “Bayesian probabilistic matrix factorization using Markov chain Monte Carlo,” in Proceedings of the International Conference on Machine Learning, vol. 25, 2008
