[Pytorch]因子分解机原理推导及其实现

因子分解机(Factorization Machine, FM, 2010年)是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法。最大的特点是易于整合交叉特征、可以处理高度稀疏数据，主要应用在推荐系统及广告CTR预估等领域。

FM的模型方程为：

这个式子的前两项就是一个简单的线性函数，这没什么好说的。主要说一下最后这一项。

如果直接按照上面这个公式计算的话，复杂度就是。对其进行矩阵分解的优化，推导过程如下：

其中， 

这样一来，复杂度就下降到了。

现将上述式子改写成矩阵相乘的格式，方便代码书写，如下，设：

矩阵  是输入的样本数据，shape是 `batch size, num of features`，即 `b, n`，这里方便阅读，把上面的  的batch size设置成了1。

矩阵  是可学习参数，shape是 `num of features, k`，即 `n, k`，k 是个超参数。

这样一来，

其中，表示哈达玛积，即两个同阶矩阵对应元素相乘。

class FactorizationMachine(nn.Module):
    def __init__(self, n, k):
        super(FactorizationMachine, self).__init__()
        self.n = n
        self.k = k
        self.linear = nn.Linear(self.n, 1, bias=True)
        self.v = nn.Parameter(torch.Tensor(self.n, self.k))

    def forward(self, x):
        """
        :param x: Long tensor of size ``(b, n)``
        :return: Long tensor of size ``(b, 1)``
        """
        x1 = self.linear(x)
        x2 = torch.mm(x, self.v) * torch.mm(x, self.v) - torch.mm(x * x, self.v * self.v)
        x2 = 0.5 * torch.sum(x2, dim=-1, keepdim=True)
        x = x1 + x2
        return torch.sigmoid(x)