FM介绍

Reading time ~1 minute

介绍

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下的预测

最常见的预测任务是:估计一个函数:

从一个实数值特征向量 ,到一个目标域T(比如:对于回归, T=R,对于分类,T={+, -})。在监督学习领域,假设存在一个训练数据集:,目标函数y给定的样本。我们也研究了排序任务,其中函数y的目标 T=R 可以被用于得分特征向量(score feature vectors)x,可以根据score进行排序。得分函数(score functions)可以通过pairwise的训练数据进行学习得到,其中特征tuple 意味着的排序比更高。由于pairwise的排序关系是斜对称(antisymmetric),只使用正例进行训练就足够了。

在本paper中,我们处理该问题,其中x是高度sparse的(比如:向量x中几乎大多数元素都是0)。假设m(x)是特征向量x中非零元素的数目,是所有向量 的m(x)的平均非零元素个数。现实世界中十分稀疏(huge sparsity )的情况很常见(),比如事件交互(推荐系统中的购买),或者文本分析(bag-of-word方法)。huge sparsity的一个原因是,需要处理海量的类别型变量域。

示例1:假设我们具有一个电影评论系统的交互数据。该系统记录了:用户对一部电影的评分,时间为,评分为。假设用户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)}

对于一个使用该数据的预测任务,目标是估计一个函数来预测:在某个时间点上,一个用户对一个item的评分行为。

图一:示例1的交互所创建的稀疏实数特征向量x。每一行表示了一个特征向量,以及它对应的目标,前4列(蓝色)表示用户的指示变量:接下来的5列(红色)表示item的指示变量。接下来的5列(黄色)持有着额外的隐式指示(比如:该用户评过分的其它电影)。一个特征(绿色)表示了月份时间。最后的5列(棕色)表示在该电影前评过分的最后一部电影。最右边的列是target:这是评分。

图1展示了特征向量是如何从S中被创建的。首先,是个二元变量(蓝色),它表示了一个交互的当前用户————通常对于一个交互只有一个用户,例如:在第一个( )的用户Alice。下一个二元变量(红色)持有着item(例如:)。图1的特征向量还包含了该用户评分过的其它电影(黄色)。对于每个用户,变量被归一化成总和为1. 例如:Alice评分了Titanic,Notting Hill和 Star Wars。另外,该样本包含了月份时间。最后,该向量包含了评分前最后一部电影的信息。例如,对于,Alice在对Notting Hill评分前,就对Titanic进行了评分。在第V节,我们展示了FM使用这样的特征向量作为输入数据,并与state-of-art算法进行比较。

我们将使用该样本数据进行本paper的演示。然而,注意FM是通用的预测器,任何实数型特征向量都可以使用,并不局限于推荐系统。

3.FM

在本节中,我们引入了因子分解机(FM)。我们详细讨论了模型等式,简短展示了如何应用FM到一些预测任务上。

A.FM模型

1)模型等式(Model Equation):阶(degree)为2,定义如下:

…(1)

其中,要估计的模型参数是:

…(2)

其中<.,.>是两个size=k的向量的点乘:

…(3)

在V中的一行描述了具有k个因子的第i个变量。是一个超参数,它定义了因子分解的维度。

一个2-way FM(degree d = 2)捕获了所有变量间的single和pairwise交叉:

  • 是全局bias
  • 建模了第i个变量的权重
  • 建模了第i个和第j个变量间的交叉(interaction)。FM模型不会为每个交叉使用单独的模型参数,作为替代,FM模型通过对它进行因子分解(factorizing)来对交叉进行建模。稍后我们可以看到,对于稀疏的高阶交叉(d>=2)允许高质量参数估计,这就是其关键点。

2) 表现力(Expressiveness):对于任意正定矩阵W(positive definite matrix),存在一个矩阵V,使得 ,k足够大(Cholesky decomposition)。这展示了一个FM可以表示任意交叉矩阵W,当k足够大时。然而在稀疏情况下,通常会选择一个小k,因为没有足够多的数据来估计复杂交叉W。限制k——即FM的表现力——可以导致更好的泛化,这样可以提升稀疏情况下的交叉矩阵。

3)稀疏条件下的参数估计:在sparse情况下,通常没有足够多的数据来直接地、独立地估计变量间的交叉(interactions)。FM可以在这样的情况下很好地估计交叉,因为他们通过对它们进行因子分解分离出交叉参数的独立性。总之,这意味着,对于一次交叉的数据可以帮助估计相关交叉的估计。以下的示例会利用来自图1的数据,使该思想更清晰。

假设:我们希望估计在Alice(A)和Star Trek(ST)间的交叉,来预测目标y(即rating)。很明显,在训练数据中,没有这样的样本x,同时满足都是非零的,因而一个直接的估计是没有交叉()。但是,这种情况下的因子分解的交叉参数是可以估计的。首先,Bob和Charlie具有相似的因子向量(factor vector),因为对于预测评分来说,两人与Star Wars()的交叉相似:必须相似。相比之下,Alice()和Charlie()之间会具有不同的因子向量(factor vector),因为在评分上,Alice与Titanic 和 Star Wars的因子也存在不同的交叉。另外,Star Trek的因子向量可能与Star Wars的相似,因为对于预测y来说,Bob与这两部电影具有相同的交叉。总之,这意味着,Alice和Star Trek的因子向量点乘(交叉) ,将与Alice和Star Wars的因子向量点乘相似——这在直观上是说得通的。

4)计算

接着,我们将展示如何从计算角度来让FM可用。等式(1)的计算复杂度是,因为所有pairwise交叉必须被计算。但是,用公式重新表示会下降到线性运行时(linear runtime)。

引理3.1:FM的模型等式(1)可以以线性时间O(kn)被计算。

证明:由于pairwise型交叉(interaction)的因子分解,不存在直接依赖这两个变量的模型参数(例如:一个带有索引(i,j)的参数)。因而,pairwise的交叉可以重新进行公式化:

该等式具有O(kn)的线性复杂度

再者,在sparsity情况下,x中的大多数元素为0(例如:m(x)很小),因而,该求和可以通过非零元素的计算来得到。在sparse应用中,FM的计算复杂度为,例如:,对于常见的推荐系统,比如MF方法。

B.FM作为预测器

FM可以应用到许多预测任务中。比如:

  • 回归:可以直接用于预测,最优化准则可以是在D上最小化square error。
  • 二元分类:,最优化准则可以使用hinge loss或者logit loss。
  • 排序(Ranking):向量x会通过的得分进行重新排序,最优化通过实例向量对,根据pairwise classification loss进行分类。

在所有的case中,正则项L2通常被添加到目标函数上来进行优化来阻止overfit。

C.FM的学习

FM具有一个封闭(closed)的模型等式,可以在线性时间上计算。这样,FM的模型参数(w0, w和 V)——可以有效地通过梯度下降法学到。——例如SGD,计算square, logit or hinge loss。FM模型的梯度如下:

…(4)

是与i独立的,可以预计算(例如:当计算 时)。总之,每个梯度都可以在常数时间内被计算。对于(x,y)的所有参数更新可以在O(kn)——或者稀疏情况下O(km(x))时间内完成。

我们提供了一个泛化实现,LibSVM,使用SGD,并支持element-wise和pairwise loss。

D.d-way FM

2-way FM可以很容易泛化到d-way Fm上:

…(5)

其中,l次交叉的交叉参数可以通过使用以下模型参数的PARAFAC模型进行因子分解:

…(6)

等式(5)的计算复杂度为 。但与引理3.1有相近的参数,可以看到在线性时间内被计算。

E.总结

FM模型在特征向量x中的值之间所有可能的交叉,使用因子分解交叉(factorized interactions),而非完全参数化交叉(full parametrized)。这主要有两个优点:

  • 1) 即使很稀疏,值之间的交叉可以被估计。尤其是,它可以泛化到未观察到的交叉
  • 2) 参数的数目对于预测和训练时间是线性的。这可以使用SGD直接进行最优化,并可以使用多种loss。

与其它模型的对比

详见paper,此处不介绍.

https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

xDeepFM介绍

前几天微软提出了一个xDeepFM算法:# 介绍传统交叉特征工程主要有三个缺点,以下部分来自paper:- 1.获取高质量特征代价高昂- 2.大规模预测系统(比如:推荐系统),存在大量原始特征(raw features),很难人工抽取所有交叉特征- 3.人工交叉特征不能泛化...… Continue reading

CRNN介绍

Published on March 04, 2018

CTPN介绍

Published on February 03, 2018