fm算法go语言 fmm算法

推荐算法之—FM

FM即Factor Machine，因子分解机

1）、特征组合是许多机器学习建模过程中遇到的问题，如果对特征直接建模，很有可能忽略掉特征与特征之间的关联信息，一次可以通过构建新的交叉特征这一特征组合方式提高模型的效果。

2）、高维的稀疏矩阵是实际工程中常见的问题，并且直接导致计算量过大，特征权值更新缓慢。试想一个10000 100的表，每一列都有8中元素，经过one-hot编码之后，会产生一个10000 800的表。因此表中每一元素只有100个值为1,700个值为0

而FM的优势就在于对这两方面问题的处理。首先是特征组合，通过两两特征组合，引入交叉项特征（二阶特征），提高模型得分；其次是高维灾难，通过引入隐向量（对参数矩阵进行分解），完成特征参数的估计

我们已经知道FM可以解决特征组合以及高维稀疏矩阵问题，而实际业务场景中，电商、豆瓣等推荐系统的场景是使用最广泛的领域，打个比方，小王只在豆瓣上浏览过20部电影，而豆瓣上面有20000部电影，如果构建一个基于小王的电影矩阵，毫无疑问，里面讲有199980个元素全为0.而类似这样的问题就可以通过FM来解决

在展示FM算法之前，我们先回顾一下最常见的线性表达式：

其中[图片上传失败W0为初始权重值，或者理解为偏置项，Wi为每个特征 xi 对应的权重值，可以看到，这种线性表达式只描述了每个特征和输出的关系。

FM的表达式如下，可观察到，只是在线性表达式后面加入了新的交叉项特征及对应的权值。

1）寻找交叉项

FM表达式的求解核心在于对交叉项的求解。下面是很多人用来求解交叉项的展开式，对于第一次接触FM算法的人来说可能会有疑惑，不知道公式怎么展开的，接下来笔者会手动推导一遍。

设有3个变量（特征）x1,x2,x3,每个特征的隐变量分别为v1=(1,2,3)、v2=(4,5,6)、v3=(1,2,1)即：

设交叉项所组成的权矩阵W为对称矩阵，之所以设为对称矩阵是因为对称矩阵可以用向量乘以向量的转置代替的性质。

那么W=VVT ,即

所以：

2）交叉项权值转换

对交叉项有了基本了解后，下面将进行公式的分解，还是以n=3为例，

3）交叉项展开式

上面的例子是对3个特征做的交叉项推导，因此对具有n个特征，FM的交叉项公式就可推广为：

我们还可以进一步分解：

所以FM算法的交叉项最终展开为：

利用梯度下降法，通过求损失函数对特征（输入项）的导数计算出梯度，从而更新权值。设m为样本个数θ为权值。

如果是回归问题，损失函数一般是均方误差（MSE）即，最小二乘：

所以回归问题的损失函数对权值的梯度（导数）为：

其中，σ表示是阶跃函数sigmoid。

所以分类问题的损失函数对权值的梯度（导数）为：

相关问答

Q1: FM(Factorization Machine)公式推导

        网上关于FM算法的介绍很多fm算法go语言，我写这篇文章的目的是详细地推一遍FM算法中交叉组合项的简化计算（其是就是验证一下为什么公式中的每个等号是成立的，而不是探究这种思路是怎么得出的），方便自己以后查看，也可以帮助一下对这个算法有些许疑惑的朋友。本文主要参考fm算法go语言了 这篇文章，FM算法的原文出处则是在这里S. Rendle, "Factorization Machines,"  2010 IEEE International Conference on Data Mining , Sydney, NSW, 2010, pp. 995-1000, doi: 10.1109/ICDM.2010.127.

        FM即因式分解机。在传统的线性模型中，每个特征都是独立的，如果需要考虑特征与特征之间的交互作用，可能需要人工对特征进行交叉组合fm算法go语言；非线性SVM可以对特征进行Kernel映射，但是在特征高度稀疏的情况下，并不能很好地进行学习fm算法go语言；现在也有很多分解模型如矩阵分解MF、SVD++等，这些模型可以学习到特征之间的交互隐藏关系，但基本上每个模型都只适用于特定的输入和场景。为此，在高度稀疏的数据场景如推荐系统下，FM出现了。

        二元交叉的FM目标函数如下：

其中，

另外， 是 维向量，即矩阵 的某一行fm算法go语言； 运算符则表示两个 维向量的点积 ：

公式（1）中，前两项就是常规的线性模型，最后一项就是FM提出的交叉组合特征。

        交叉组合项乍一看复杂度是 ，但经过一定的化简后，可以将复杂度降低为 。下面我会将完整的公式先放出来，然后逐步分析。

上面这个公式用的是latex的split模块，打不了tag，就按照四个等号的顺序从上到下1-4好了。

        先是第1步的推导，这一步可以先不管 这一项，因此在推导过程中我就省略了。令 ， ， ， ，那么要验证的就是 。首先把 拆开，得到：

然后把 拆开，得到：

所以 ，而

进行简单的移项后，即可得到 。

        下面的2-4步如果仔细观察就会发现，只是把向量 拆开了而已，我写这篇文章之前是没想到这一点的...那这篇文章到这里就结束了，告辞。

        更新一波，在用梯度下降更新权值时，分别对三个权重的偏导是这样的：

Q2: 推荐系统排序算法--FM模型

在计算广告和推荐系统中，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。在进行CTR预估时，除了单特征外，往往要对特征进行组合。对于特征组合来说，业界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型。最近几年也出现了很多基于FM改进的方法，如deepFM，FNN，PNN，DCN，xDeepFM等。

FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：(本例来自美团技术团队分享的paper)

clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。

将上面的数据进行one-hot编码以后，就变成了下面这样 ：

因为是categorical特征，所以经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。举个非常简单的例子，假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见， 数据的稀疏性 ，是我们在实际应用场景中面临的一个非常常见的挑战与问题。

one-hot编码带来的另一个问题是 特征空间变大 。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的。

普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。

一般的线性模型为：

                     

从上面的式子很容易看出，一般的线性模型压根没有考虑特征间的关联。为了表述特征间的相关性，我们采用多项式模型。在多项式模型中，特征 与 的组合用 表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下：

为了简单起见，我们只考虑二阶交叉的情况，具体的模型如下：

                     

式中， 表示样本的特征数量, 表示第 个特征，与线性模型相比，FM的模型就多了后面特征组合的部分。

从FM公式可以看出，组合特征的参数一共有 n(n−1)/2个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，每个参数 的训练需要大量 和 都非零的样本；由于样本数据本来就比较稀疏，满足 和 都非零”的样本将会非常少。训练样本的不足，很容易导致参数  不准确，最终将严重影响模型的性能。

那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子中，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量的点积就是矩阵中user对item的打分。

类似地，所有二次项参数 可以组成一个对称阵 （为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 ， 的第 列便是第 维特征的隐向量。换句话说，每个参数 ，这就是FM模型的核心思想。因此，FM的模型方程为（本文不讨论FM的高阶形式）

                    

其中， 是第 维特征的隐向量， 代表向量点积。隐向量的长度为 ，二次项的参数数量减少为 个，远少于多项式模型的参数数量。另外，参数因子化使得 的参数和 的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说， 和 的系数分别为 和 ，它们之间有共同项 。也就是说，所有包含“ 的非零组合特征”（存在某个 ，使得 ）的样本都可以用来学习隐向量 vivi，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中， 和 是相互独立的。

显而易见，FM的模型公式是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是 。但是，通过下面的等式，FM的二次项可以化简，其复杂度可以优化到  。由此可见，FM可以在线性时间对新样本作出预测。        

                    

我们再来看一下FM的训练复杂度，利用SGD（Stochastic Gradient Descent）训练模型。模型各个参数的梯度如下：

其中， 是隐向量 的第 个元素。由于 只与 有关，而与 无关，在每次迭代过程中，只需计算一次所有 的 ，就能够方便地得到所有 的梯度。显然，计算所有 的 的复杂度是 ；已知 时，计算每个参数梯度的复杂度是 ；得到梯度后，更新每个参数的复杂度是 ；模型参数一共有 个。因此，FM参数训练的复杂度也是 。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。

libFM

论文： Factorization Machines

论文： Factorization Machines with Follow-The-Regularized-Leader for CTR prediction in Display Advertising

推荐系统遇上深度学习(一)--FM模型理论和实践

FM（Factorization Machines）的理论与实践

深入FFM原理与实践-美团

推荐好文：  深度学习在CTR预估中的应用

关于fm算法go语言和fmm算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。