FM算法公式推导

设 x i x_{i} xi​ 为特征， y y y 为预测值，假设我们用最简单的线性拟合来预测 y y y 值： y = w 0 + ∑ i = 1 n w i x i {y}=w_{0}+\sum_{i=1}^{n} w_{i} x_{i} y=w0​+i=1∑n​wi​xi​实际中可能 x i x_{i} xi​， x j x_{j} xj​ 同时为1时可能是一个很有用的特征，这种组合特征是 x i x_{i} xi​ 和 x j x_{j} xj​ 的线性组合所无法表示的。这样一来乘积 x i x j x_{i}x_{j} xi​xj​ 就成一个新的特征。为了不错过任何一个这种可能有用的组合特征，我们穷举所有的 i i i， j j j组合: y = w 0 + ∑ i = 1 n w i x i + ∑ i n − 1 ∑ j = i + 1 n w i j x i x j {y}=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i}^{n-1} \sum_{j=i+1}^{n} w_{i j} x_{i} x_{j} y=w0​+i=1∑n​wi​xi​+i∑n−1​j=i+1∑n​wij​xi​xj​这只是组合了2个特征，同样道理我们可以组合任意三个特征、四个特征，随着阶数的提高，样本会显得非常稀疏，而且额外引入的参数呈指数增长。

FM总结： 1.二次回归 2.二次项系数矩阵分解 3.统一了各种矩阵分解模型

由于多了二次项系数 w i j w_{ij} wij​，我们额外引入 n 2 2 \frac{n^{2}}{2} 2n2​ 个参数需要训练。有没有什么办法可以减少参数？再来观察二次项系数矩阵 W n × n W_{n×n} Wn×n​，它是对称的方阵 w i j w_{ij} wij​ = w j i w_{ji} wji​，同时它是稀疏的，因为绝大部分的组合特征都是无用的，所以其系数应该为0。可以对 W n × n W_{n×n} Wn×n​ 进行矩阵分解 W n × n W_{n×n} Wn×n​ = V n × k V_{n×k} Vn×k​ V n × k T V_{n×k}^{T} Vn×kT​，即 w i , j = < V i , V j > w_{i,j} = wi,j​=。其中 k ≪ n k≪n k≪n，本来需要训练的 n × n n×n n×n 个参数，现在只需要训练 n × k n×k n×k 个： y = w 0 + ∑ i = 1 n w i x i + ∑ i n − 1 ∑ j = i + 1 n < V i , V j > x i x j {y}=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i}^{n-1} \sum_{j=i+1}^{n}x_{i} x_{j} y=w0​+