Factorization Machines笔记
FM预测公式:
其中,
二阶交叉部分可以通过数学转化,降低计算复杂度:
最终FM的预测公式为:
FM的训练复杂度,利用SGD(Stochastic Gradient Descent)训练模型。模型各个参数的梯度如下:
其中, $v_{j,f}$ 是隐向量 $v_j$ 的第 $f$ 个元素。 由于 $\sum_{j=1}^n v_{j,f} x_j$ 只与 $f$ 有关,而与 $i$ 无关,在每次迭代过程中,只需计算一次所有 $f$ 的 $\sum_{j=1}^n v_{j,f} x_j$, 就能够方便地得到所有 $v_{i,f}$ 的梯度。显然,计算所有 $f$ 的 $\sum_{j=1}^n v_{j,f} x_j$ 的复杂度是 $O(kn)$; 已知 $\sum_{j=1}^n v_{j,f} x_j$ 时,计算每个参数梯度的复杂度是 $O(1)$;得到梯度后,更新每个参数的复杂度是 $O(1)$; 模型参数一共有 $nk + n + 1$ 个。因此,FM参数训练的复杂度也是 $O(kn)$。综上可知,FM可以在线性时间训练和预测,是一种非常高效的模型。
MSE为:
其中p
为特征维度,k
为$v$的维度,label是one-hot
形式的
1 | """ |
论文及工程地址: