FM/FFM

FM

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

回归问题(MSE)

记样本的真实的标签为$\hat{y}$y^​，FM模型预测的标签为$y$y，训练集大小为$N$N，则
$\displaystyle loss(\hat{y},y)=\frac{1}{2}\sum\limits_{l=1}^{N}(\hat{y}^{(l)} - y^{(l)})^2=\frac{1}{2}\sum\limits_{l=1}^{N}\Big\{\hat{y}^{(l)}-\Big[w^{(l)}_0+\sum\limits_{i=1}^n w^{(l)}_i x_i+\frac{1}{2}\sum\limits_{k=1}^{K}\Big((\sum\limits_{i=1}^{n} v^{(l)}_{ik}x_i)^2-\sum\limits_{i=1}^n (v^{(l)}_{ik}x_i)^2\Big)\Big]\Big\}$loss(y^​,y)=21​l=1∑N​(y^​(l)−y(l))2=21​l=1∑N​{y^​(l)−[w0(l)​+i=1∑n​wi(l)​xi​+21​k=1∑K​((i=1∑n​vik(l)​xi​)2−i=1∑n​(vik(l)​xi​)2)]}

$求导：\displaystyle\frac{\partial loss(\hat{y},y)}{\partial\theta}=\sum\limits_{l=1}^{N}(\hat{y}^{(l)} - y^{(l)})\frac{\partial y^{(l)}}{\partial\theta}$求导：∂θ∂loss(y^​,y)​=l=1∑N​(y^​(l)−y(l))∂θ∂y(l)​

$利用SGD训练模型，各参数梯度：\displaystyle\frac{\partial y^{(l)}}{\partial\theta}=\begin{cases}1, &amp;\theta=w_0 \cr x_i, &amp; \theta=w_i \cr x_i\sum\limits_{j=1}^n v_{j,k}x_j-v_{i,k}x^2_i,&amp; \theta=v_{i,k}\end{cases}$利用SGD训练模型，各参数梯度：∂θ∂y(l)​=⎩⎪⎪⎪⎨⎪⎪⎪⎧​1,xi​,xi​j=1∑n​vj,k​xj​−vi,k​xi2​,​θ=w0​θ=wi​θ=vi,k​​

分类问题(logloss)

记样本的真实的标签为$\hat{y}$y^​，FM模型预测的标签为$y$y，训练集大小为$N$N；当正负样本的标签分别为$+1$+1和$-1$−1时，交叉熵损失可以表示为
$\displaystyle loss(\hat{y},y)=\sum\limits_{l=1}^{N}-ln\sigma(\hat{y}^{(l)}y^{(l)})=\sum\limits_{l=1}^{N}-ln\frac{1}{1+e^{-\hat{y}^{(l)}y^{(l)}}}=\sum\limits_{l=1}^{N}-ln\frac{1}{1+e^{-\hat{y}^{(l)}\Big[w^{(l)}_0+\sum\limits_{i=1}^n w^{(l)}_i x_i+\frac{1}{2}\sum\limits_{k=1}^{K}\Big((\sum\limits_{i=1}^{n} v^{(l)}_{ik}x_i)^2-\sum\limits_{i=1}^n (v^{(l)}_{ik}x_i)^2\Big)\Big]}}$loss(y^​,y)=l=1∑N​−lnσ(y^​(l)y(l))=l=1∑N​−ln1+e−y^​(l)y(l)1​=l=1∑N​−ln1+e−y^​(l)[w0(l)​+i=1∑n​wi(l)​xi​+21​k=1∑K​((i=1∑n​vik(l)​xi​)2−i=1∑n​(vik(l)​xi​)2)]1​

$求导：\displaystyle\frac{\partial loss(\hat{y},y)}{\partial\theta}=\sum\limits_{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}$求导：∂θ∂loss(y^​,y)​=l=1∑N​−σ(y^​(l)y(l))1​⋅∂y(l)∂σ(y^​(l)y(l))​⋅∂θ∂y(l)​

同样，$利用SGD训练模型，各参数梯度：\displaystyle\frac{\partial y^{(l)}}{\partial\theta}=\begin{cases}1, &amp;\theta=w_0 \cr x_i, &amp; \theta=w_i \cr x_i\sum\limits_{j=1}^n v_{j,k}x_j-v_{i,k}x^2_i,&amp; \theta=v_{i,k}\end{cases}$利用SGD训练模型，各参数梯度：∂θ∂y(l)​=⎩⎪⎪⎪⎨⎪⎪⎪⎧​1,xi​,xi​j=1∑n​vj,k​xj​−vi,k​xi2​,​θ=w0​θ=wi​θ=vi,k​​

FFM

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

$y=w_0+\sum\limits_{i=1}^n w_i x_i+\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n &lt;v_{i,f_j},v_{j,f_i}&gt;x_i x_j$y=w0​+i=1∑n​wi​xi​+i=1∑n−1​j=i+1∑n​<vi,fj​​,vj,fi​​>xi​xj​
注意，这里$i$i是特征，属于field$f_i$fi​；$v_{i,f_j}$vi,fj​​表示特征$f_i$fi​对field$f_j$fj​的隐向量。

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

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

FM背景及相关算法对比

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

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