FM 模型推导

论文地址：https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

在使用 LR 的时候，要进行大量的特征工程，如对离散值进行独热编码，在进行大量的独热编码之后，特征矩阵会变得非常稀疏。在特征创建的时候，两两特征进行组合，由于特征向量过于稀疏，无法学习到很多组合特征的权重，FM 模型在 LR 模型的基础上，多了特征两两组合的部分，需要比 LR 多学习对应参数的权重。

只讨论二阶特征组合的情况

• LR 多了两两特征组合的形式如下 ，$n$n 是特征向量的维度：

$\hat{y} = \omega_0 + \sum^n_{i=1}\omega_ix_i +\sum^n_{i=1}\sum^n_{j=i+1} \omega_{ij}x_ix_j$y^​=ω0​+i=1∑n​ωi​xi​+i=1∑n​j=i+1∑n​ωij​xi​xj​

• 假设每个特征有它对应的隐因子向量，那么 $\omega_{ij}$ωij​ 就可以用两个特征对应的 $k$k 纬隐因子向量 $v_i$vi​, $v_j$vj​ 的内积表示

$\hat{y} = \omega_0 + \sum^n_{i=1}\omega_ix_i +\sum^n_{i=1}\sum^n_{j=i+1} <v_i,v_j>x_ix_j$y^​=ω0​+i=1∑n​ωi​xi​+i=1∑n​j=i+1∑n​<vi​,vj​>xi​xj​

• 这里 $\sum^n_{i=1}\sum^n_{j=i+1} <v_i,v_j>x_ix_j$∑i=1n​∑j=i+1n​<vi​,vj​>xi​xj​ 的部分可以进行优化，先贴上论文里面的推导，step by step

Step 1

特征要两两进行组合，肯定是不考虑重复的情况，所以开始的时候 $\sum^n_{i=1}\sum^n_{j=i+1} <v_i,v_j>x_ix_j$∑i=1n​∑j=i+1n​<vi​,vj​>xi​xj​ 的 $j$j 从 $i+1$i+1 开始。现在 $j$j 的下标变为从 $1$1 开始，那么 $<v_i, v_j>$<vi​,vj​> 和 $<v_j, v_i>$<vj​,vi​> 都要算一遍，这俩计算结果是一样的，只算一遍即可，整体除以 $2$2 ，因为原来 $<v_i, v_i>$<vi​,vi​> 是不算的，现在算上了，所以要减去 $<v_i, v_i>$<vi​,vi​>

Step 2

这里就是把 $k$k 纬的隐因子向量展开

Step 3

• 提 $\sum^k_{f=1}$∑f=1k​

$=\frac{1}{2} \sum^k_{f=1} \Big( \sum^n_{i=1}\sum^n_{j=1} v_{i,f} v_{j,f} x_ix_j - \sum^n_{i=1}v_{i,f} v_{i,f}x_ix_i \Big)$=21​f=1∑k​(i=1∑n​j=1∑n​vi,f​vj,f​xi​xj​−i=1∑n​vi,f​vi,f​xi​xi​)

• 只看里面的 $\sum^n_{i=1}\sum^n_{j=1} v_{i,f} v_{j,f} x_ix_j$∑i=1n​∑j=1n​vi,f​vj,f​xi​xj​
  $\sum^n_{j=1} v_{i,f} v_{j,f} x_ix_j$∑j=1n​vi,f​vj,f​xi​xj​ 因为里面的 $v_{i,f} x_i$vi,f​xi​ 对于此处来说相当于常量，提到外面，变为 $v_{i,f}x_i \sum^n_{j=1} v_{j,f} x_j$vi,f​xi​∑j=1n​vj,f​xj​ ，所以变为：

$\sum^n_{i=1}\sum^n_{j=1} v_{i,f} v_{j,f} x_ix_j = \sum^n_{i=1}v_{i,f}x_i\sum^n_{j=1} v_{j,f} x_j$i=1∑n​j=1∑n​vi,f​vj,f​xi​xj​=i=1∑n​vi,f​xi​j=1∑n​vj,f​xj​

Step 4

这里 $\sum^n_{i=1}v_{i,f}x_i$∑i=1n​vi,f​xi​ 和 $\sum^n_{j=1} v_{j,f} x_j$∑j=1n​vj,f​xj​ 其实只是下标的名字不一样而已，对应的隐因子向量的每个元素是一样的，so $\sum^n_{i=1}v_{i,f}x_i$∑i=1n​vi,f​xi​ 和 $\sum^n_{j=1} v_{j,f} x_j$∑j=1n​vj,f​xj​ 是同一个东西，这样的话，只需要计算一次的 $\sum^n_{i=1}v_{i,f}x_i$∑i=1n​vi,f​xi​ 就可以了

到这样，计算 $\sum^n_{i=1}\sum^n_{j=i+1} <v_i,v_j>x_ix_j$∑i=1n​∑j=i+1n​<vi​,vj​>xi​xj​ 的复杂度，就从 $O(kn^2)$O(kn2) 变为了 $O(kn)$O(kn)

后面把这个 $\hat{y}$y^​ 代入 Sigmoid 函数，使用 logistic 损失函数，然后梯度下降求解 $\omega_i$ωi​ 和 $v_{i,f}$vi,f​ 即可。