1. 符号定义
- 稀疏训练集D：
- 第i个数据点：
- ：数据点的不为0的feature数量
- ：D中的均值
2. 度为2的FM模型
度为2的预测函数 \begin{align} y = w_0 + \sum\limits_{i=1}^nw_ix_i + \sum\limits_{i=1}^n\sum\limits_{j=i+1}^n<v_i,v_j>x_ix_j \end{align}
式中的参数
\begin{align} w_0 \in R \quad w\in R \quad v_i,v_j \in R^K \end{align}
且表示两个向量的点积
3. 度为2的FM模型的计算简化
\begin{align} \sum\limits_{i=1}^n\sum\limits_{j=i+1}^n<v_i,v_j>x_ix_j = &\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n<v_i,v_j>x_ix_j-\frac{1}{2}\sum\limits_{i=1}^n<v_i,v_i>x_ix_i \\ = &\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^Kv_{i,k}v_{j,k}x_ix_j-\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{k=1}^Kv_{i,k}v_{i,k}x_ix_i \\ = &\frac{1}{2}\sum\limits_{k=1}^K\sum\limits_{i=1}^n\sum\limits_{j=1}^nv_{i,k}v_{j,k}x_ix_j-\frac{1}{2}\sum\limits_{k=1}^K\sum\limits_{i=1}^nv_{i,k}v_{i,k}x_ix_i \\ = &\frac{1}{2}\sum\limits_{k=1}^K \left( \left(\sum\limits_{i=1}^nv_{i,k}x_i\right)\left(\sum\limits_{j=1}^nv_{j,k}x_j\right)\right)-\frac{1}{2}\sum\limits_{k=1}^K\sum\limits_{i=1}^nv_{i,k}v_{i,k}x_ix_i \\ = &\frac{1}{2}\sum\limits_{k=1}^K \left(\sum\limits_{i=1}^nv_{i,k}x_i\right)^2-\frac{1}{2}\sum\limits_{k=1}^K\sum\limits_{i=1}^nv_{i,k}^2x_i^2 \end{align}
于是
\begin{align} y = w_0 + \sum\limits_{i=1}^nw_ix_i + \frac{1}{2}\sum\limits_{k=1}^K \left(\sum\limits_{i=1}^nv_{i,k}x_i\right)^2-\frac{1}{2}\sum\limits_{k=1}^K\sum\limits_{i=1}^nv_{i,k}^2x_i^2 \end{align}
上式的计算复杂度是O(Kn)
4. 梯度
\begin{align} \frac{\partial y}{\partial w_0} &= 1 \\ \frac{\partial y}{\partial w_{i\geq1}} &= x_i \\ \frac{\partial y}{\partial v_{i,k}}&= x_i\left(\sum\limits_{j=1}^nv_{j,k}x_j\right) - v_{i,k}x_i^2 \end{align}
5. 度为d的FM模型
\begin{align} y = w_0 + \sum\limits_{i=1}^nw_ix_i + \sum\limits_{l=2}^d\sum\limits_{i_1=1}^n…\sum\limits_{i_l=i_{l-1}+1}^n\left(\prod_{j=1}^lx_{i_j}\right)\left(\sum\limits_{k=1}^{K_l}\prod_{j=1}^lv^{(l)}_{i_j,k}\right) \end{align}