【fm球员评分低】一文读懂FM算法优势，并用python实现！（附代码）

作者：ANKIT CHOUDHARY翻译：状元术语校对：冯友文校对：谭家尧这篇文章建议共用3933个字读9分钟。

本文带大家了解因子分解机算法并解析其优势所在，教你在python中实现。

介绍

我仍然记得第一次遇到点击率预测问题时的情形，在那之前，我一直在学习数据科学，对自己取得的进展很满意，在机器学习黑客马拉松活动中也开始建立了自信，并决定好好迎接不同的挑战。

为了做得更好，我购买了一台内存16GB，i7处理器的机器，但是当我看到数据集的时候却感到非常不安，解压缩之后的数据大概有50GB - 我不知道基于这样的数据集要怎样进行点击率预测。幸运地是，Factorization Machines(FM)算法拯救了我。

任何从事点击率预测问题或者推荐系统相关工作的人都会遇到类似的情况。由于数据量巨大，利用有限的计算资源对这些数据集进行预测是很有挑战性的。

然而在大多数情况下，由于很多特征对预测并不重要，所以这些数据集是稀疏的（每个训练样本只有几个变量是非零的）。在数据稀疏的场景下，因子分解有助于从原始数据中提取到重要的潜式或隐式的特征。

因子分解有助于使用低维稠密矩阵来表示目标和预测变量之间的近似关系。在本文中我将讨论算法Factorization Machines(FM) 和Field-Aware Factorization Machines(FFM)，然后在回归/分类问题中讨论因子分解的优势，并通过python编程实现。

1. 因式分解的直观介绍

2. FM算法如何优于多项式和线性模型

3. FFM算法介绍

4. 在python中使用xLearn库进行算法实现

因式分解的直观介绍

为了直观地理解矩阵分解，我们来看一个例子：假设有一个用户-电影评分（1-5）矩阵，矩阵中的每一个值表示用户给电影的评分（1-5）。

从上述表格中我们可以看出，一些评分是缺失的，我们想设计一种方法来预测这些缺失的评分。直观上来讲，利用矩阵分解来解决这个问题的关键是应该有一些潜在的特征决定用户如何评价一部电影。举例来说 - 用户A和B都是演员阿尔·帕西诺的粉丝，那么他们就会对阿尔·帕西诺的电影评分较高。在上述例子中，对特定演员的偏好是一个隐藏的特性，因为我们没有明确地将其包含在评分矩阵中。

假设我们要计算K个隐藏或潜在的特征，我们的任务是找出矩阵P (U x K)和Q (D x K) (U – 用户, D – 电影)，使得 P x QT 近似等于评分矩阵R。

P矩阵的每一行表示用户与不同特征的相关性，Q矩阵的每一行表示该特征与电影同样的相关性。为了得到用户ui对电影dj的评分，我们可以计算对应于ui和dj两个向量的点积。

接下来要做的就是求出矩阵P和矩阵Q。我们使用梯度下降算法来计算，目标函数是使用户的实际评分与通过矩阵P和Q估计的评分之间的平方误差最小，这里的平方误差由以下方程求出。

现在我们要给pik和qkj定义一个更新规则，梯度下降法中的更新规则是由最小化误差值的梯度来定义的。

获得梯度值后，接下来可以定义pik和qkj的更新规则。

这里α是控制更新步长的学习速率，使用上述更新规则，我们可以迭代地执行操作，直到误差收敛到最小，同时使用下面的公式计算总的误差，以此来确定什么情况下应该停止迭代。

上述解决方案很简单并且经常会导致过拟合，即现有的评分都被准确预测到，但是不能很好地推广到未知的数据上。为了解决这个问题，我们可以引入一个正则化参数 β，它将分别控制矩阵P和Q中向量“用户-特征”和“电影-特征”，并给出一个更好的评分的近似值。

如果对利用python实现上述功能和相关细节感兴趣，请参考这个链接。一旦我们用上述方法计算出了矩阵P和Q，得到的近似评分矩阵如下：

现在，我们既能够重新生成现有评分，也能对未知的评分进行一个合理的近似。

FM算法如何优于多项式和线性模型

首先考虑一组点击率预测数据的训练示例。以下数据来自相关体育新闻网站（发布商）和体育用品公司（广告商）。

当我们讨论FM或者FFM的时候，数据集中的每一列（比如上述表格中的出版商、广告商等）将被称为一个字段，每一个值（ ESPN、Nike 等）都被称为一个特征。

线性或逻辑回归模型在很多问题上表现很好，但缺点是这种模型只能学习所有变量或者特征各自的影响，无法学习变量之间的相互作用

。

在上述等式中，w0、wESPN等代表参数，xESPN、xNike等代表数据集中的各个特征，通过最小化上述函数的对数损失，得到逻辑回归模型。捕获特征之间相互作用的一种方法是使用多项式函数，将每个特征对的乘积作为单独的参数来学习，并且把每一个乘积作为一个独立的变量。

这也可以称为 Poly2模型，因为每一项都只考虑了两个特征之间的相互影响。

问题在于，即使面对一个中等大小的数据集，也需要一个庞大的模型，这对存储模型所需要的内存空间和训练模型所花费的时间都有很大的影响；
其次，对于一个稀疏数据集，这种技术不能很好地学习所有的权重或参数，因为没有有足够的训练样本使每一个特征对的权重是可靠的。

救星FM

FM算法解决了成对特征交互的问题。它使我们能够根据每一对特征组合中的可靠信息（隐藏特征）来训练模型，同时在时间和空间复杂度上更有效地实现上述目标。具体来讲，它将成对交互特征作为低维向量的点积（长度为K）进行建模，以下包含了一个二阶因子分解的方程。

FM（K=3）项中每个参数的表示方法如下：

上述等式中，我们分别计算了与2个特征对应的2个长度为3的潜因子的点积。

从建模的角度来看，这是非常强大的，因为每一个特征最后都会转换到一个相似特征被互相嵌套的空间，简而言之，点积基本上表示了潜在特征的相似程度，特征越相近，点积越大。

对于余弦函数，当 θ是0时，得到最大值1；当 θ是180度，得到-1，所以当 θ接近于0时，相似性最大。

FM算法的另一个巨大优势是能够在线性时间复杂度下使用简单的数学方法计算模型中成对特征的相互作用。如果你想进一步了解具体的实现步骤，请参考链接中关于FM算法的原始研究论文。

示例：FM算法性能优于 POLY2算法的演示

考虑以下一组虚构的点击率数据：

这个数据集由作为发布者的体育网站和体育用品广告商构成。广告是以弹出的方式来显示的，用户可以选择点击广告或者关闭广告。

特征对(ESPN，Adidas)只有一个负的训练数据，那么在Poly2算法中，这个特征对可能会学到一个负的权重值wESPN，Adidas；而在FM算法中，由于特征对(ESPN，Adidas)是由wESPN·wAdidas决定的，而其中的wESPN和wAdidas分别是从其他特征对中学到的（比如(ESPN，Nike)，(NBC，Adidas)等），所以预测可能更加精确。
另一个例子是特征对(NBC，Gucci)没有任何训练数据，对于Poly2算法，这个特征对的预测值为0；但是在FM算法中，因为wNBC和wGucci可以从其他特征对中学到，所以仍然有可能得到有意义的预测值。

FFM算法介绍

为了理解FFM算法，我们需要认识field的概念。field通常是指包含一个特定特征的更广泛的类别。在上述训练示例中，field分别指发布者（P）、广告商（A）和性别（G）。

在FM算法中，每一个特征只有一个隐向量v，来学习其他特征带来的潜在影响。以ESPN为例，wESPN被用来学习特征Nike(wESPN·wNike)和Male)之间的潜在作用。
但是，由于ESPN和Male属于不同的field,所以对特征对(ESPN，Nike)和(ESPN，Male)的起作用的潜在作用可能不同。FM算法无法捕捉这个差异，因为它不区分field的概念，在这两种情况中，它会使用相同参数的点积来计算。
在FFM算法中，每个特征有若干个隐向量。例如，当考虑特征ESPN和Nike之间的交互作用时，用符号wESPN，A来表示ESPN的隐藏特征，其中A（广告商）表示特征Nike的field。类似的，关于性别的field的一个重要的参数wESPN,G也会被学习到。