来源商业新知网，原标题：机器学习算法系列：FM分解机
在线性回归中，是假设每个特征之间独立的，也即是线性回归模型是无法捕获特征之间的关系。 为了捕捉特征之间的关系，便有了FM分解机的出现了。 FM分解机是在线性回归的基础上加上了交叉特征，通过学习交叉特征的权重从而得到每个交叉特征的重要性。 这个模型也经常用于点击率预估。
因为线性回归中特征都是独立存在的，不存在特征组合项，除非事先人工添加。如果要在线性回归上加入二特征组合，可以如下：
其中， n 代表样本的特征数量， x_i 是第 i 个特征的值， w_0 ， w_i ， w_ij 是模型参数。
从上面公式可以看出组合特征一共有n(n-1)/2个，任意两个参数之间都是独立，这在数据稀疏的场景中，二次项参数的训练会很困难，因为训练w_ij需要大量非零的x_i和x_j，而样本稀疏的话很难满足x_i和x_j都非零。训练样本不足就很容易导致w_ij不准确，影响模型的性能。
为了解决这个问题，可以引进矩阵分解的技术，这也是为什么叫做分解机的原因。
根据矩阵分解的知识可以知道，一个实对称矩阵W，可以进行如下分解：
类似的，所有的二次项参数 w_ij 可以组成一个对称阵 W ，然后进行分解成以上形式，其中 V 的第 j 列便是第j 维特征的隐向量，也就是说每个 w_ij = ，这就是 FM 模型的核心思想，得到：
其中 <> 表示两个向量的点积。
为了降低参数训练的时间复杂度，我们将二次项进行化简，如下：
由上式可知， v_if 的训练只需要样本的 x_i 特征非 0 即可，适合于稀疏数据。
同时，我们可以看到对于每个 v_if 的梯度中求和公式中没有 i ，所以对 i=1,..,N 求和项都是一样的，只需要计算一次就可以了，所以要更新所有 v_if( 共有 nk 个 ) 的是时间复杂度为 O(nk) ，则 FM 可以在线性时间训练和预测，是一种非常高效的模型。
对于上述的式子，我们可以使用随机梯度下降的方法求解每个参数，即：
通过求解参数我们就可以得到最终的模型了。另外补充说明一点，对于隐向量 V ，每个 v_i 都是 x_i 特征的一个低维的稠密表示，在实际应用中，数据一般都是很稀疏的 Onehot 类别特征，通过 FM 就可以学习到特征的一种 Embedding 表示，把离散特征转化为 Dense Feature 。同时这种 Dense Feature 还可以后续和 DNN 来结合，作为 DNN 的输入，事实上用于 DNN 的 CTR 也是这个思路来做的。
