FM/FFM

大家好，又见面了，我是你们的朋友全栈君。

FM

FM算法的提出旨在解决稀疏数据下的特征组合问题。
$y=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n{w}_{ij}{x}_i{x}_j，(w_0,w_i,w_{ij}\in R)$
分解$w_{ij}=<v_i,v_j>=\sum _{k=1}^K{v}_{ik}{v}_{jk}$
$\sum _{i=1}^{n-1}\sum _{j=i+1}^n{w}_{ij}{x}_i{x}_j=\frac{1}{2}(\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}{x}_i{x}_j-\sum _{i=1}^n{w}_{ii}{x}_i^2)=\frac{1}{2}(\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^K{v}_{ik}{v}_{jk}{x}_i{x}_j-\sum _{i=1}^n\sum _{k=1}^K{v}_{ik}^2{x}_i^2)$
$=\frac{1}{2}\sum _{k=1}^K((\sum _{i=1}^n{v}_{ik}{x}_i)(\sum _{j=1}^n{v}_{jk}{x}_j)-\sum _{i=1}^n(v_{ik}{x}_i{)}^2)=\frac{1}{2}\sum _{k=1}^K((\sum _{i=1}^n{v}_{ik}{x}_i{)}^2-\sum _{i=1}^n(v_{ik}{x}_i{)}^2)$
其中$v_i=(v_{i1},v_{i2},\cdots ,v_{iK})$是第$i$维特征的隐向量。【1】隐向量的长度为$k（k<<n）$，包含$k$个描述特征的因子。由上可见，二次项的参数数量减少为$kn$个，远少于多项式模型的参数数量。即通过矩阵分解，二次项可以化简，复杂度可以从$O(k{n}^2)$优化到$O(kn)$。【2】参数因子化使得$x_h{x}_i$的参数和$x_i{x}_j$的参数不再是相互独立的，因此可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说，$x_h{x}_i$和$x_i{x}_j$的系数分别为$<v_h,v_i>$和$<v_i,v_j>$，它们之间有共同项$v_i$。也就是说，所有包含“$x_i$的非零组合特征”（存在某个$j̸=i$，使得$x_i{x}_j̸=0$）的样本都可以用来学习隐向量$v_i$，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中，$w_{hi}$和$w_{ij}$是相互独立的。【3】以上包含二阶项的拟合函数，可以采用不同的损失函数用于解决回归、二分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。

回归问题(MSE)

记样本的真实的标签为$\hat{y}$，FM模型预测的标签为$y$，训练集大小为$N$，则
$loss(\hat{y},y)=\frac{1}{2}\sum _{l=1}^N({\hat{y}}^{(l)}-y^{(l)}{)}^2=\frac{1}{2}\sum _{l=1}^N\{{\hat{y}}^{(l)}-[w_0^{(l)}+\sum _{i=1}^n{w}_i^{(l)}{x}_i+\frac{1}{2}\sum _{k=1}^K((\sum _{i=1}^n{v}_{ik}^{(l)}{x}_i{)}^2-\sum _{i=1}^n(v_{ik}^{(l)}{x}_i{)}^2\left)\right]\}$

$求导：\frac{\partial loss(\hat{y},y)}{\partial \theta }=\sum _{l=1}^N({\hat{y}}^{(l)}-y^{(l)})\frac{\partial y^{(l)}}{\partial \theta }$

$利用SGD训练模型，各参数梯度：\frac{\partial y^{(l)}}{\partial \theta }=\{\begin{array}{ll}1,& \theta =w_0\\ x_i,& \theta =w_i\\ x_i\sum _{j=1}^n{v}_{j,k}{x}_j-v_{i,k}{x}_i^2,& \theta =v_{i,k}\end{array}$

分类问题(logloss)

记样本的真实的标签为$\hat{y}$，FM模型预测的标签为$y$，训练集大小为$N$；当正负样本的标签分别为$+1$和$-1$时，交叉熵损失可以表示为
$loss(\hat{y},y)=\sum _{l=1}^N-ln\sigma ({\hat{y}}^{(l)}{y}^{(l)})=\sum _{l=1}^N-ln\frac{1}{1+e^{-{\hat{y}}^{(l)}{y}^{(l)}}}=\sum _{l=1}^N-ln\frac{1}{1+e^{-{\hat{y}}^{(l)}[w_0^{(l)}+\sum _{i=1}^n{w}_i^{(l)}{x}_i+\frac{1}{2}\sum _{k=1}^K((\sum _{i=1}^n{v}_{ik}^{(l)}{x}_i{)}^2-\sum _{i=1}^n(v_{ik}^{(l)}{x}_i{)}^2\left)\right]}}$

$求导：\frac{\partial loss(\hat{y},y)}{\partial \theta }=\sum _{l=1}^N-\frac{1}{\sigma ({\hat{y}}^{(l)}{y}^{(l)})}\cdot \frac{\partial \sigma ({\hat{y}}^{(l)}{y}^{(l)})}{\partial y^{(l)}}\cdot \frac{\partial y^{(l)}}{\partial \theta }$

同样，$利用SGD训练模型，各参数梯度：\frac{\partial y^{(l)}}{\partial \theta }=\{\begin{array}{ll}1,& \theta =w_0\\ x_i,& \theta =w_i\\ x_i\sum _{j=1}^n{v}_{j,k}{x}_j-v_{i,k}{x}_i^2,& \theta =v_{i,k}\end{array}$

FFM

通过引入field的概念，FFM把相同性质的特征/归于同一个field。FM可以看作FFM的特例，是把所有特征/都归属到一个field时的FFM模型。

$$y=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n<v_{i,f_j},v_{j,f_i}>x_i{x}_j$$
注意，这里$i$是特征，属于field$f_i$；$v_{i,f_j}$表示特征$f_i$对field$f_j$的隐向量。

基于field的FFM和FM的区别：（1）FM特征$x_i、x_j、x_k$交叉时，对应的隐向量$v_i、v_j、v_k$是可以无区别得互相交叉的，即“$x_i{x}_j$的系数为$v_i{v}_j$”，“$x_i{x}_k$的系数为$v_i{v}_k$”，很显然：$x_i$无论与特征$x_j$、还是特征$x_k$做交叉时，组合系数都是同一个$v_i$，并没有区别开。（2）FFM也是对特征进行交叉(5个feature两两交叉$C_5^2$)，但是FFM的特征$x_i、x_j、x_k$交叉时，对应的隐向量$v_i、v_j、v_k$不能不考虑field互相交叉；即$x_i$与特征$x_j$、$x_i$与特征$x_k$做交叉时，组合系数不能使用同一个$v_i$，应该根据field信息区别为$v_{i,f_j}$和$v_{i,f_k}$。只有feature $x_j$和$x_k$属于同一field时，有$v_{i,f_j}=v_{i,f_k}$。

结合上图表格：（1）feature1-User分别与feature2-Movie和feature5-Price做交叉时，由于feature2-Movies属于field2、feature5-Price属于field4，所以feature1-User和feature2-Movie组合的系数为$<v_{1,2},v_{2,1}>$，feature1-User和feature5-Price组合的系数为$<v_{1,4},v_{5,1}>$，即$v_{1,2}$和$v_{1,4}$是不同的两项。（2）feature1-User分别与feature3-Genre和feature4-Genre做交叉时，由于feature3-Genre和feature4-Genre都属于field3，所以feature1-User和feature3-Genre组合的系数为$<v_{1,3},v_{3,1}>$，feature1-User和feature4-Genre组合的系数为$<v_{1,3},v_{4,1}>$，即$v_{1,3}$和$v_{1,3}$是相同的项。

FM背景及相关算法对比

（1）FM(factorization machine)是在LR(logistic regression)基础上，加入了特征的二阶组合项；
（2）SVM和FM的主要区别在于，SVM的二元特征交叉参数是独立的，如$w_{ij}$，而FM的二元特征交叉参数是两个k维的向量$v_i、v_j$，即$<v_i，v_j>$和$<v_j，v_m>$是相互影响的。

Q：为什么线性SVM在和多项式SVM在稀疏条件下效果会比较差呢？A：线性SVM只有一维特征，不能挖掘深层次的组合特征在实际预测中并没有很好的表现；而多项式SVM正如前面提到的，交叉的多个特征需要在训练集上共现才能被学习到，否则该对应的参数就为0，对测试集上的case而言这样的特征就失去了意义，因此在稀疏条件下，SVM表现并不能让人满意。而FM不一样，通过向量化的交叉，可以学习到不同特征之间的交互，进行提取到更深层次的抽象意义。

参考文献
https://tech.meituan.com/2016/03/03/deep-understanding-of-ffm-principles-and-practices.html