一、前言

网上关于FM算法的介绍很多，我写这篇文章的目的是详细地推一遍FM算法中交叉组合项的简化计算（其是就是验证一下为什么公式中的每个等号是成立的，而不是探究这种思路是怎么得出的），方便自己以后查看，也可以帮助一下对这个算法有些许疑惑的朋友。本文主要参考了https://www.cnblogs.com/AndyJee/p/7879765.html这篇文章，FM算法的原文出处则是在这里S. Rendle, "Factorization Machines," 2010 IEEE International Conference on Data Mining, Sydney, NSW, 2010, pp. 995-1000, doi: 10.1109/ICDM.2010.127.

二、背景

FM即因式分解机。在传统的线性模型中，每个特征都是独立的，如果需要考虑特征与特征之间的交互作用，可能需要人工对特征进行交叉组合；非线性SVM可以对特征进行Kernel映射，但是在特征高度稀疏的情况下，并不能很好地进行学习；现在也有很多分解模型如矩阵分解MF、SVD++等，这些模型可以学习到特征之间的交互隐藏关系，但基本上每个模型都只适用于特定的输入和场景。为此，在高度稀疏的数据场景如推荐系统下，FM出现了。

三、FM算法模型

1、模型目标函数

二元交叉的FM目标函数如下： $\\\hat{y}(x):=\omega_0+\sum_{i=1}^n\omega_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n<V_i,V_j>x_ix_j\tag{1}$

其中， $\\\omega_i(i=0,1,\cdots,n)\in \mathbb{R},\quadV\in \mathbb{R}^{n\times k}$

另外， $V_i(i=1,2,\cdots,n)$ 是 $k$ 维向量，即矩阵 $V$ 的某一行； $<\cdot,\cdot>$ 运算符则表示两个 $k$ 维向量的点积 $V_i^TV_j$ ： $\\<V_i,V_j>:=\sum_{c=1}^kv_{i,c}\cdot v_{j,c}$

公式（1）中，前两项就是常规的线性模型，最后一项就是FM提出的交叉组合特征。

2、简化交叉组合特征项

交叉组合项乍一看复杂度是 $O(k*n^2)$ ，但经过一定的化简后，可以将复杂度降低为 $O(kn)$ 。下面我会将完整的公式先放出来，然后逐步分析。

$\\\begin{split}&\sum_{i=1}^{n-1}\sum_{j=i+1}^n(V_i^TV_j)x_ix_j\\=&\frac{1}{2}\left[\sum_{i=1}^n\sum_{j=1}^n(V_i^TV_j)x_ix_j-\sum_{i=1}^n(V_i^TV_j)x_ix_i \right]\\=&\frac{1}{2}\left[\sum_{i=1}^n\sum_{j=1}^n\sum_{c=1}^k(v_{i,c}v_{j,c})x_ix_j-\sum_{i=1}^n\sum_{c=1}^kv_{i,c}^2x_i^2 \right]\\=&\frac{1}{2}\sum_{c=1}^k\left(\sum_{i=1}^nv_{i,c}x_i\sum_{j=1}^nv_{j,c}x_j-\sum_{i=1}^nv_{i,c}^2x_i^2 \right)\\=&\frac{1}{2}\sum_{c=1}^k\left[ \left( \sum_{i=1}^nv_{i,c}x_i \right)^2-\sum_{i=1}^nv_{i,c}^2x_i^2 \right]\end{split}$

上面这个公式用的是latex的split模块，打不了tag，就按照四个等号的顺序从上到下1-4好了。

先是第1步的推导，这一步可以先不管 $V_i^TV_j$ 这一项，因此在推导过程中我就省略了。令 $M=\sum_{i=1}^{n-1}\sum_{j=i+1}^nx_ix_j$ ， $N=\sum_{i=1}^n\sum_{j=1}^nx_ix_j$ ， $S=\sum_{i=1}^nx_ix_i$ ， $S_n=\sum_{i=1}^nx_i$ ，那么要验证的就是 $M=\frac{1}{2}(N-S)$ 。首先把 $N$ 拆开，得到： $\\\begin{array}{1}N&=x_1\cdot(x_1+x_2+\cdots+x_n)+x_2\cdot(x_1+x_2+\cdots+x_n)+\cdots+x_n\cdot(x_1+x_2+\cdots+x_n)\\&=S_n\cdot S_n\end{array}$

然后把 $M$ 拆开，得到： $\\\begin{split}M&=x_1\cdot(S_n-S_1)+x_2\cdot(S_n-S_2)+\cdots+x_{n-1}\cdot(S_n-S_{n-1})\\&=(S_n-x_n)\cdot S_n-\sum_{i=1}^{n-1}(x_i\cdot S_i)\\&=S_n\cdot S_n-\sum_{i=1}^n(x_i\cdot S_i)\end{split}$

所以 $N-M=\sum_{i=1}^n(x_i\cdot S_i)$ ，而 $\begin{split}\sum_{i=1}^n(x_i\cdot S_i)&=x_1\cdot S_1+x_2\cdot S_2+x_3\cdot S_3+\cdots+x_n\cdot S_n\\&=x_1\cdot(x_1)+x_2\cdot(x_1+x_2)+x_3\cdot(x_1+x_2+x_3)+\cdots+x_n\cdot(x_1+x_2+\cdots+x_n)\\&=x_1^2+(x_1x_2+x_2^2)+(x_1x_3+x_2x_3+x_3^2)+\cdots+(x_1x_n+x_2x_n+\cdots+x_n^2)\\&=[(\underline{x_1x_2})+(\underline{x_1x_3}+x_2x_3)+\cdots+(\underline{x_1x_n}+x_2x_n+\cdots+x_{n-1}x_n)]+[x_1^2+x_2^2+\cdots+x_n^2]\\&=M+S\end{split}$

进行简单的移项后，即可得到 $M=\frac{1}{2}(N-S)$ 。

下面的2-4步如果仔细观察就会发现，只是把向量 $V_i(i=1,2,\cdots,n)$ 拆开了而已，我写这篇文章之前是没想到这一点的...那这篇文章到这里就结束了，告辞。

更新一波，在用梯度下降更新权值时，分别对三个权重的偏导是这样的： $\\\frac{\partial}{\partial\theta}\hat{y}=\left\{ \begin{split} &1,&{\rm if} \ \theta\ {\rm is}\ \omega_0 \\ &x_i,&{\rm if} \ \theta\ {\rm is}\ \omega_i\\ &x_i\sum_{j=1}^n(v_{j,c}\cdot x_j)-v_{i,c}\cdot x_i^2,\quad&{\rm if}\ \theta\ {\rm is}\ v_{i,c} \end{split}\right.$

FM(Factorization Machine)公式推导