FFM

1.学习美团FM

1. Factorization Machine（因子分解）主要做特征的交叉，
   多项式模型是包含特征组合的最直观的模型。在多项式模型中，特征 xi 和 xj 的组合采用 xixj 表示，即 xi 和 xj 都非零时，组合特征 xixj 才有意义。从对比的角度，本文只讨论二阶多项式模型。模型的表达式如下：

   
   image.png

其中，n 代表样本的特征数量，xi 是第 i 个特征的值，w0、wi、wij 是模型参数。

• 矩阵分解提供了一种解决思路。在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子中，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量的点积就是矩阵中user对item的打分。

image.png

假设有n个user，m个item，则问题变成，nX2 X 2Xm=nXm。

2. 所有二次项参数wij可以写成对称矩阵W。

   
   image.png

image.png

那么这个矩阵就可以分解为 W=V 'V，V 的第 j 列便是第 j 维特征的隐向量
这个地方的v应该是kn的。
可能是对称矩阵分解可以得到特征。。

• n为特征数。k最大应该是n（n-1）/2,这里是不是V降维了。
  k应该是W的维度数。k<<n？
  也就是特征数小于样本数？
  参数变成，还是n*k个？
  k每一个n有k格参数。
  vi,vj的点积是相同的不区分顺序的。

1 -----------------------------

参数因子化使得 xh ，xi 的参数和 xi，xj 的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。 具体来说，xhxi 和 xixj 的系数分别为 ⟨vh,vi⟩ 和 ⟨vi,vj⟩，它们之间有共同项 vi。 也就是说，所有包含“xi 的非零组合特征”（存在某个 j≠i，使得 xixj≠0）的样本都可以用来学习隐向量 vi，这很大程度上避免了数据稀疏性造成的影响。 而在多项式模型中，whi 和 wij 是相互独立的

• 是不是说vi的来源包含了所有的特征。而不是单单的xi
  显而易见，公式(2)是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是 O(kn2)。但是，通过公式(3)的等式，FM的二次项可以化简，其复杂度可以优化到 O(kn)[7]。由此可见，FM可以在线性时间对新样本作出预测。
  

  image.png

• 这个公式如何化简？

  
  image.png

模型各个参数的梯度：

image.png

其中，vj,f 是隐向量 vj 的第 f 个元素。由于 ∑nj=1vj,fxj 只与 f 有关，而与 i 无关，在每次迭代过程中，只需计算一次所有 f 的 ∑nj=1vj,fxj，就能够方便地得到所有 vi,f 的梯度。显然，计算所有 f 的 ∑nj=1vj,fxj 的复杂度是 O(kn)；已知 ∑nj=1vj,fxj 时，计算每个参数梯度的复杂度是 O(1)；得到梯度后，更新每个参数的复杂度是 O(1)；模型参数一共有 nk+n+1 个。因此，FM参数训练的复杂度也是 O(kn)。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。

• vj,f 是隐向量 vj 的第 f 个元素

2. FFM

`

• 通过引入field的概念，FFM把相同性质的特征归于同一个field

• 在FFM中，每一维特征 xi，针对其它特征的每一种field fj，都会学习一个隐向量 vi,fj。因此，隐向量不仅与特征相关，也与field相关

• 假设样本的 n 个特征属于 f 个field，那么FFM的二次项有 nf个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看作FFM的特例，是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性，可以导出其模型方程。

`

image.png

• FFM实现

  
  image.png