FM算法解析

背景

FM算法全称因子分解机，具有以下特点：

1. 降低了参数量，参数从 $\frac{n(n+1)}{2}$ 降到 $kn$
2. 表达了特征之间的交叉
3. 模型复杂度可以从$O(kn^2)$ 优化到$O(kn)$
4. 提升了泛化能力，即使训练样本中不存在的$<a, b>$交叉项，也可以通过学习出的隐向量来预估

具体公式

$y = w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n} <v_i, v_j>x_ix_j$

其中$v_i​$ $v_j​$ 是对应$x_i​$ $x_j​$ 的隐向量，$<v_i, v_j>​$表示两个向量的内积(inner product)

优化过程：$ab + bc + ca = \frac{1}{2}\lgroup (a + b +c)^2 - a^2 - b^2 - c^2 \rgroup$

$\sum_{i=1}^{n}\sum_{j=i+1}^{n} <v_i, v_j>x_ix_j$

$=\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} <v_i, v_j>x_ix_j - \frac{1}{2}\sum_{i=1}^{n}<v_i, v_i>x_ix_i$

$= \frac{1}{2} (\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{f=1}^{k}v_{i,f}v_{j,f}x_ix_j - \sum_{i=1}^{n}\sum_{f =1}^{k}v_{i,f}v_{i,f}x_ix_i)$

$=\frac{1}{2} \sum_{f=1}^{k} \lgroup (\sum_{i=1}^{n}v_{i,f}x_i) (\sum_{j=1}^{n}v_{j,f}x_j) - \sum_{i=1}^{n} v_{i,f}^2x_i^2 \rgroup$

$=\frac{1}{2} \sum_{f=1}^{k} \lgroup (\sum_{i=1}^{n}v_{i,f}x_i)^2 - \sum_{i=1}^{n} v_{i,f}^2x_i^2 \rgroup$

梯度下降

$loss = \frac{1}{2}(y - \overline y) ^2$

$\frac {\partial loss} {\partial w_0} = 1$

$\frac {\partial loss} {\partial w_i} = x_i$

$\frac {\partial loss} { \partial v_{i,f}} = x_i\sum_{j=1}^{n}v_{j,f}x_j - v_{i,f}x_i^2$