FM公式推导

2020-08-26 本文已影响0人小幸运Q

我们只讨论二阶多项式

image.png

计算复杂度 $O(kn^2)$ ，不过没关系，可以用另外的方法降到 $O(kn)$ ，k是隐向量 $v_{i,f}$ 维度，原理如下：

image.png

$\sum_{i=1}^{n} {\sum_{j=i+1}^{n} <v_{i},v_{j}>x_{i}x_{j}} = \frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{<v_{i},v_{j}>x_{i}x_{j}}}-\frac{1}{2}\sum_{i=1}^{n}{<v_{i},v_{i}>x_{i}x_{i}}$

$=\frac{1}{2}(\sum_{i=1}^{n}{\sum_{j=1}^{n}{\sum_{f=1}^{k}{v_{i,f}v_{j,f}x_{i}x_{j}}}}-\sum_{i=1}^{n}{\sum_{f=1}^{k}{v_{i,f}v_{i,f}x_{i}x_{i}}})$
$=\frac{1}{2}\sum_{f=1}^{k}{((\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})}$

上式中的i跟j效果一样，将j用i替换

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

采用随机梯度下降法SGD求解参数，对v(i,f)的二阶导求导

观察上式可知，只要 $x_i \ne 0$ 即可训练，非常适合稀疏数据。

FM公式推导

猜你喜欢

热点阅读