Factorization Machines
参考
1. 刘建平的博客: https://www.cnblogs.com/pinard/p/6370127.html
2. Tracholar的博客: https://tracholar.github.io/machine-learning/2017/03/10/factorization-machine.html
3. 知乎小孩不笨的文章: https://zhuanlan.zhihu.com/p/50426292
1 准备
通常,我们的机器学习模型是学习一个映射函数
f(⋅)→T
该函数使我们输入的n维实值特征向量 x∈Rn 映射到一个目标域T,例如对与回归问题,这个目标域T=R,而对于分类问题,T={C1,C2,...,Cn}。在常见的有监督学习任务中,我们的训练样本数据通常还带有一个标签y,数据格式如:
D={(x(1),y(1)),(x(2),y(2)),...,(x(m),y(m))}
其中x(i)∈Rn为输入数据,对应样本的特征向量,y(i)对应该样本的标签,m为样本的数目。
在现实世界中,许多应用问题(如文本分析、推荐系统等)会产生高度稀疏的(特征)数据,即特征向量x(i)中几乎所有的分量都为0
这里,我们以电影评分系统为例,给出一个关于高度稀疏数据的实例:
![推荐算法-因式分解机FM 推荐算法-因式分解机FM](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzE1Ny9mNjA0MzI4NGQ4YTQwNjg4ZjM5Y2FiZjFmNDljMDM2ZC5wbmc=)
关于这个数据各部分含义这里不再解释。
在上面的例子中,特征向量x的实际维度为∣U∣+∣I∣+∣I∣+1+∣I∣=∣U∣+3∣I∣+1,真实场景中,用户数目∣U∣与电影数目∣I∣都非常大,而每个用户对电影的评分数目非常有限。以此可知我们的特征向量x将会多么的稀疏,用Nz(X)来表示一条样本数据/特征向量x的非0分量个数,并记:
Nz(X)=N1i∑mNz(x(i))
Nz(X)表示训练集D中所有特征向量中非零分量数的平均数,显然,对于稀疏数据Nz(X)<<m
2 FM二阶模型方程
对于上面提到的样本数据D,我们先回顾一下线性回归的做法:
y^=w0+w1x1+...+wnxn
=w0+i=1∑nwixi
如果我们采用单一的线性模型来学习用户的点击,打分习惯,各特征分量是相互独立的,没有考虑特征分量之间的相互关系,我们很容易忽略特征中潜在的组合关系,比方说“男性用户”喜欢看“漫威电影”,买“奶粉”的用户也常常买“尿不湿”等等。
为了学习特征间的交叉,SVM通过多项式核函数来实现特征的交叉,实际上和多项式模型是一样的,问题在于二阶项的参数过多,设特征维数为n,那么二阶项的参数数目为2n(n+1),对于广告点击率预估问题,由于存在大量id特征,导致 n 可能为 107维,这样一来,模型参数的量级为1014,这导致只有极少数的二阶组合模式才能在样本中找到, 而绝大多数模式在样本中找不到,因而模型无法学出对应的权重。例如,对于某个wij,样本中找不到xi=1,xj=1 (这里假定所有的特征都是离散的特征,只取0和1两个值)这种样本,那么wij的梯度恒为0,从而导致参数学习失败!
很容易想到,可以对二阶项参数施加某种限制,减少模型参数的*度。FM 施加的限制是要求二阶项系数矩阵是低秩的,能够分解为低秩矩阵的乘积。
下面我们做改进:
y^=w0+i=1∑nwixi+i=1∑n−1j=i+1∑nwijxixj
上式将任意两个互异的分量之间的关系也考虑进来了。接下来对二阶项参数wij进行改进。针对每个维度的特征xi,引入辅助向量(相当于给每个特征一个隐向量)vi,(注意是对每一个特征,xi是一个特征分量,引入一个向量),从而将wij表示为vi与vj内积的形式。其中:
vi=(vi1,vi2,...,vik)∈Rk,i=1,2,..,n
这里的n对应一条样本数据中的特征数目n,k对应每个特征要表示为k维的辅助向量(隐向量),是一个可调节的超参数。则wij应表示为:
w^ij=viTvj:=l∑kvilvjl
这样就将参数个数减少到 kn,可以设置较少的k值(一般设置在100以内,k << n),极大地减少模型参数,增强模型泛化能力,这跟矩阵分解的方法是一样的。但是这样为什么说可以提高模型的泛化能力呢?
以上述电影评分系统为例,假设我们要计算用户A与电影ST的交叉项,很显然,训练数据里没有这种情况,这样会导致 wA,ST=0 ,但是我们可以近似计算出 <VA,VST> 。首先,用户 B 和 B 有相似的向量 VB 和 VC ,因为他们对 SW 的预测评分比较相似, 所以<VB,VSW> 和 <VC,VSW> 是相似的。用户 A 和 C 有不同的向量,因为对 TI 和 SW 的预测评分完全不同。接下来, ST 和 SW 的向量可能相似,因为用户 B 对这两部电影的评分也相似。最后可以看出, <VA,VST> 与 <VA,VSW> 是相似的。
于是,函数y^可以进一步改写为:
y^(x)=w0+i=1∑nwixi+i=1∑n−1j=i+1∑n<viT,vj>xixj
这就是FM的模型方程。
3 复杂度分析与化简
FM模型的方程中,参数包括:
w0∈R,W∈Rn,V∈Rn×k
共有1+n+n×k个参数,其中w0为整体的偏置,W为各特征分量xi的参数向量,V为交叉特征的参数向量矩阵,函数的计算复杂度为:
{n+(n−1)}+{2n(n−1)[k+(k−1)+2]+2n(n−1)−1}+2=O(kn2)
第一个花括号内对应∑i=1nwixi的加法和乘法操作,第二个花括号内对应∑i=1n−1∑j=i+1n<viT,vj>xixj的加法和乘法操作。
我们对方程进行改写约简,即可将计算复杂度降到O(kn),推导过程如下:
i=1∑nj=i+1∑n<vi,vj>xixj
=21i=1∑nj=1∑n<vi,vj>xixj−21i=1∑n<vi,vi>xixi
=21⎝⎛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⎠⎞
可以计算出,上式的计算复杂度为
k{[n+(n−1)+1]+[3n+(n−1)]+1}+(k−1)+1=O(kn)
需要注意的是:在高度稀疏的数据集中,特征向量X中绝大部分分量为0,即文章开始我们引入的Nz(X)会很小,于是计算复杂度为O(kNz(X)),对整个数据集D而言,平均计算复杂度为:O(kNz(X))
4 推广高阶
y^(x)=w0+i=1∑nwixi+l=2∑di1=1∑n−(l−1)i2=i1+1∑n−(l−2)…il=il−1+1∑n(j=1∏lxij)⎝⎛f=1∑klj=1∑lvij,f(l)⎠⎞
详细理解见最上方参考文献。
5 回归与分类任务的损失函数
5.1 回归问题
回归问题常用的衡量损失的函数有最小平方误差(LSE)、均方差(MSE),均方根误差(RMSE)、平均绝对误差(MAE),这里以最小平方误差为例:
loss(y^,y)=(y^−y)2
5.2 二分类
01损失,交叉熵损失函数等
6 优化方法
6.1 梯度下降
![推荐算法-因式分解机FM 推荐算法-因式分解机FM](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzU4NC9iZmZjMmY3OTBlYTk2NDFkMDRmMmI5ZjIxYWE4MWRjOC5wbmc=)
对SGD超参数的讨论:
- 学习率η: SGD的收敛依赖于η的取值,η太大,则可能不收敛;太小,则收敛会很慢,因此这个参数要取得合适
- 正则化系数λ: FM模型的泛化能力(相应的预测质量)很大程度上依赖于这些正则化系数的选取。它们通常是在单独的 holdout set上通过 grid search方法来获取,由于它们个数多,取值区间大,因此,通过 grid search方法来选取会非常费时。一种提高效率的做法是减少它们的个数。例如,可以考虑让矩阵V中行号经π映射后为同一个值的那些行使用同一个正则化系数。此时,正则化系数集λ变为λ0,λπ(i)w,λπ(i)v,i∈{1,2,⋯,n}
- 正态分布方差参数σ: 矩阵V的初始化采用符合正态分布N(0,σ)的随机初始化,方差参数σ通常取得很小
7 FM与MF的关系
FM包含矩阵分解的模型,矩阵分解的模型是FM的一个特例,当特征只剩下userID和itemID时,FM就退化成了MF。
以user对item评分预测问题为例,基于矩阵分解的协同过滤可以看做FM的一个特殊例子,对于每一个样本,FM可以看做特征只有userid和itemid的onehot编码后的向量连接而成的向量。从FM和MFCF公式来看,MFCF的用户embedding和item embedding可以看做FM中的隐向量,用户和item的bias向量就是FM中的一次项系数,常数μ也和FM中的常数w0相对应,可以看到,MFCF就是FM的一个特例!另外,FM可以采用更多的特征,学习更多的组合模式,这是单个矩阵分解的模型所做不到的!因此,FM比矩阵分解的方法更具普遍性!事实上,现在能用矩阵分解的方法做的方案都直接上FM了!
![推荐算法-因式分解机FM 推荐算法-因式分解机FM](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzc5NC9kMTI3MDlhNmRhYzI4YjEwYjQ1M2NkNzYwZWY2NjE5Mi5KUEVH)
另外,FM与决策树,FM与神经网络的关系请参考参考文献2