机器学习算法系列：FM分解机

译者 | Ray

编辑 | 安可

在线性回归中，是假设每个特征之间独立的，也即是线性回归模型是无法捕获特征之间的关系。为了捕捉特征之间的关系，便有了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 = <v_i,v_j>，这就是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也是这个思路来做的。