Factorization Machine
因子分解机(Factorization Machine, FM)是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法。目前,被广泛的应用于广告预估模型中,相比LR而言,效果强了不少。我们可以认为,这个模型结合了SVM的优点与分解模型的优点。与SVM类似的是,FM是一个广泛的预测器,可以兼容任意实值的特征向量。而与FM不同的是,FM对于所有变量之间的联系使用了分解的参量去建模。
-
主要目标: 解决数据稀疏的情况下,特征怎样组合的问题。
-
FM优点:
主要考虑到,FM模型是SVM模型与factorization模型的结合。
- FM模型可以在非常稀疏的数据中进行合理的参数轨迹,而SVM做不到这点。(FMs allow parameter estimation under very sparse data wher SVMs fails.)
- FM模型的复杂度是线性的,优化效果很好,而且不需要像SVM一样依赖于支持向量。(FMs have linear complexity, can be optimized in the primal and do not rely on support vectors like SVM.)
- FM是一个通用模型,它可以用于任何特征值为实值的情况。而其他因式分解模型只能用于一些输入数据比较固定的情况。(FMs are a general predictor that can work with any real valued feature vector. In contrast to this, other state-of-the-art factorization models work only on very restricted input data)
关于FM, peghoty的博文比较清晰,大家可以点击链接先阅读一下,并与本文章进行对比。
1. FM模型简介
1.1 FM模型
本质上是SVM模型的拓展,主要考虑到多维特征之间的交叉关系,其中参数的训练使用的是矩阵分解的方法。
参数模型的表示如下:我们的预测任务是估计一个函数y:Rn→T表示从实值向量x∈Rn到目标域T中,(比如对回归问题T=R,分类问题T={+,−})。在监督模型中,我们假设存在一个训练数据集D={(x(1),y(1)),(x(2),y(2)),…}。另外,也调查了推荐任务的函数y,以及T=R可以被用来表示向量x。分数函数可以被用来训练成对训练集,这里特征元组(x(A),x(B))∈D表示x(A)应该比x(B)排名更高。
1.2 FM 模型的超平面分类公式
-
二阶FM的公式(2-order, 2-way FM):
y^FM(x):=⟨w,x⟩+j′>j∑⟨pj,pj′⟩xjxj
或者更为普遍的写法:
y^(x):=w0+i=1∑nwixi+i=1∑nj=i+1∑n⟨vi,vj⟩xixj
其中,各个参数的size为:
w0∈R,w∈Rn,V∈Rn×k
内积定义如下:
⟨vi,vj⟩:=f=1∑kvi,f⋅vj,f
其中k∈N0+表示的是决定分解机维度的超参。n表示的是模型参数的维度。2-way的FM捕捉了所有的单独的特征以及变量之间的特征,各参数的意义表示如下:
-
w0是全局偏置量
-
wi建模了第i个变量的强度
-
w^i,j:=⟨vi,vj⟩。建模了第i和第j个变量之间的联系。
-
高阶FM的公式:
y^HOFM(x):=⟨w,x⟩+j′>j∑⟨pj(2),pj′(2)⟩xjxj′+⋯+jm>⋯>j1∑⟨pj1(m),…,pjm(m)⟩xj1xj2…xjm
与二阶FM类似,但是其考虑了更多特征之间的关联性质。
1.3 关于FM三点优点的解释
首先,对于稀疏数据的计算,通常没有足够的数据来直接独立地估计变量之间的关联性。FM可以评估,则是因为FM通过分解的方式打破了数据参数的独立性。
具体可以参见图1:
![因子分解机(Factorization Machine)详解(一) 因子分解机(Factorization Machine)详解(一)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzIzNS80ZDczNDc0YmYwOWVhZDVjMjNiNGI0OTljN2M5OTZmYi5wbmc=)
在FM中,每个评分记录被放在一个矩阵的一行中,从列数看特征矩阵x的前面u列即为User矩阵,每个User对应一列,接下来的i列即为item特征矩阵,之后数列是多余的非显式的特征关系。后面一列表示时间关系,最后i列则表示同一个user在上一条记录中的结果,用于表示用户的历史行为。
例子,可以考虑用户A以及电影ST之间的关系。首先,二者没有直接的联系,也就是wA,ST=0,通过分解联系的变量⟨vA,vST⟩我们能够估计在这种情况下的联系。因此,对于稀疏数据而言,FM可以挖掘出更深层次的信息。
第二,假设n,k如前述定义,那么计算前驱过程的时间复杂度为O(kn2)。但是通过重组计算公式能够得到线性的时间复杂度O(kn)。证明如下:
==i=1∑nj=i+1∑n⟨vi,vj⟩xixj21i=1∑nj=1∑n⟨vi,vj⟩xixj−21i=1∑n⟨vi,vi⟩xixi21⎝⎛i=1∑nj=1∑nf=1∑kvi,fvj,fxixj−i=1∑nf=1∑kvi,fvi,fxixi⎠⎞=21f=1∑k((i=1∑nvi,fxi)(j=1∑nvj,fxj)−i=1∑nvi,f2xi2)=21f=1∑k⎝⎛(i=1∑nvi,fxi)2−i=1∑nvi,f2xi2⎠⎞
可以看到我们只需要计算vi,f以及xi相关的结果。另外,由上式可以看到,在稀疏的情况下,我们只需要计算非0的结果。假设x中非0的数量为m(x),时间复杂度为O(kmD)。另外,FM也具有多线性(multi-linearity)的性质,对任意参数θ,FM的预测模型如下:
y^(x)=gθ(x)+θhθ(x)∀θ∈Θ
可以轻易求得梯度:
hθ(x)=∂θ∂y^(x)=⎩⎨⎧1,xl,xl∑j̸=lvj,fxj, if θ is w0 if θ is wl if θ is vl,f
关于第三个优点,分别考虑FM与传统的线性分类器SVM与常见的分解方法MF, SVD++, PITF( factorizing pairwise interactions)以及FPMC( Factorized Personalized Markov Chains)等方法进行对比。具体的对比我会再写一篇文章进行详细分析。
2. FM的训练方法
对于FM而言,其可以被应用于很多预测任务,包括:
-
回归问题: 可以使用最小均方误差进行优化
-
二分类问题: 可以使用hinge loss或者logit loss进行优化
-
Ranking问题: 向量x以预测的分数函数y^(x)为基准进行排列,优化是使用实例向量(x(a),x(b))∈D成对的分类误差进行的。
具体的优化方法包括SGD, ALS以及MCMC。
2.1 优化问题介绍
对于特定的观测集S,我们得到目标函数为:
OPT(S):=Θargmin(x,y)∈S∑l(y^(x∣Θ),y)
loss function:
- 回归问题:lLS(y1,y2):=(y1−y2)2
- 二分类问题:lC(y1,y2):=−lnσ(y1y2)
对Stochastic的目标函数分布:
- 回归问题:p(y∣x,Θ)∼N(y^(x,Θ),1/α)
- 二分类问题:p(y∣x,Θ)∼Bernoulli(b(y^(x,Θ)))
其概率图模型可表示如下:
![因子分解机(Factorization Machine)详解(一) 因子分解机(Factorization Machine)详解(一)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzIyOS8xMGIzZDU2YWI0OGYwYzIxMTM4MjBhY2I2NGM3NmMzNS5wbmc=)
其中μ,λ等均为超参。
梯度计算公式如下:
∂θ∂lLS(y^(x∣Θ),y)=∂θ∂(y^(x∣Θ)−y)2=2(y^(x∣Θ)−y)∂θ∂y^(x∣Θ)
∂θ∂lC(y^(x∣Θ),y)=∂θ∂−lnσ(y^(x∣Θ)y)=(σ(y^(x∣Θ)y)−1)y∂θ∂y^(x∣Θ)
2.2 SGD方法
不多说,直接上算法:
![因子分解机(Factorization Machine)详解(一) 因子分解机(Factorization Machine)详解(一)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzk3Ny8xNDk0NjFlYTY1NzkyY2UwMDZiMDFhMDM5MzNkMzY2OS5wbmc=)
比较容易理解,缺点是必须确定学习率η。
2.3 ALS
ALS即为Alternating Least-Squares,也是Coordinate Descent,是对SGD方法的改进。具体是将参数Θ拆分成若干个部分,公式为:
θ∗=θargmin⎝⎛(x,y)∈S∑(y^(x∣Θ)−y)2+θ∈Θ∑λθθ2⎠⎞=θargmin⎝⎛(x,y)∈S∑(gθ(x∣Θ\{θ})+θhθ(x∣Θ\{θ})−y)2+θ∈Θ∑λθθ2⎠⎞=∑i=1nhθ(xi)2+λθ∑i=1nhθ2(xi∣Θ\{θ})hθ(xi∣Θ\{θ})=∑i=1nhθ(xi)2+λθθ∑i=1nhθ2(xi∣Θ\{θ})hθ(xi)ei
其中ei:=yi−y^(xi∣Θ),为残差项。算法如下:
![因子分解机(Factorization Machine)详解(一) 因子分解机(Factorization Machine)详解(一)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzIwNy9jM2E5ZDIzZmRkYzlhMWUzY2QxYjU0ZDdjNTU3Y2U5Zi5wbmc=)
对于更加详细的ALS算法,可以表现为下图:
![因子分解机(Factorization Machine)详解(一) 因子分解机(Factorization Machine)详解(一)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzEyMS84NzNmMzgzNWVmODg0YTQ5NDBjNzVlNmUwOWY2YjNmMS5wbmc=)
其中,ALS的主要改进为不需要学习率,但是仍然需要确定regularization的超参。
2.4 MCMC方法
使用概率图推断以及最大后验估计(MAP)的方法。概率图如下:
![因子分解机(Factorization Machine)详解(一) 因子分解机(Factorization Machine)详解(一)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzUxNC85MTdiODk1MzY4ZWExMGE1NjYxNThhNGE0YTVmNmEyYS5wbmc=)
其实就是针对原方法对各个超参进行MCMC采样操作。具体采用Gibbs采样器。通过确定各个超参的先验概率,使用贝叶斯推断方法,以及对各个参数的后验概率求导,即可对整个模型进行优化。参数集Θ为:
Θ0:={α0,β0,αλ,βλ,μ0,γ0}
后续将继续介绍FM与深度学习相结合的应用,以及解决高阶FM的方法。
3. Reference
[1] Rendle S. Factorization machines[C]//2010 IEEE International Conference on Data Mining. IEEE, 2010: 995-1000.
[2] Rendle S. Factorization machines with libfm[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2012, 3(3): 57.
[3] Blondel M, Fujino A, Ueda N, et al. Higher-order factorization machines[C]//Advances in Neural Information Processing Systems. 2016: 3351-3359.