推荐算法：从FM到DeepFM

简介

本来在看离散型特征的编码方式，看到了推荐算法的一系列方法，综合转载于：

• 原创 | 万字长文，剖析经典论文GBDT+LR
• 小白都能懂的推荐算法入门（一），从上古时期的LR开始聊起
• 原创 | 想做推荐算法？先把FM模型搞懂再说
• 小白都能懂的推荐算法入门（二），FM为什么强大能代替LR？
• 小白都能懂的推荐算法入门（三），FM、类别特征以及Embedding
• FM算法详解（因子分解机）
• 推荐领域又一经典paper，分分钟搞清楚Attention机制
• 浅谈推荐，从FM到深度学习
• 吃透论文——推荐算法不可不看的DeepFM模型

GBDT+LR

来剖析一篇经典的论文：Practial Lessons from Predicting Clicks on Ads at Facebook。从这篇paper的名称当中我们可以看得出来，这篇paper的作者是Facebook的广告团队。这是一篇将GBDT与LR模型结合应用在广告点击率预测的方法，虽然距今已经有好几年了，但是文中的方法仍然没有完全过时，至今依然有一些小公司还在使用。

这篇paper非常非常经典，可以说是推荐、广告领域必读的文章，说是业内的常识也不为过。这篇文章的质量很高，内容也比较基础，非常适合作为大家的入门paper。

简介

paper开头的部分简单介绍了一下当时互联网行业当中广告的地位以及当时Facebook的规模，当时Facebook有着7.5亿的日活（日活跃用户daily active users)，超过一百万有效的广告商，因此对于Facebook来说选择合适有效的广告投放给用户的重要性是非常巨大的。在此基础上引出了Facebook的创新性做法，即将GBDT与逻辑回归模型进行组合，在真实的数据场景当中获得了超过3%的收益。

在2007年的时候Google和Yahoo就提出了在线竞价的广告收费机制，但是Facebook和搜索引擎的场景不一样，在搜索引擎的场景当中，用户会有明确的搜索意图。引擎会先根据用户的搜索意图去筛选广告，所以候选的广告集不会很大。但是Facebook不存在这样的强意图信息，所以Facebook候选的广告数量要大得多，因此对于系统的压力以及要求也要更高。

但是本文（paper）并不会讨论系统相关的内容，仅仅关注最后一部分排序模型的做法。虽然paper里没说，但是我们看得出来，Google和Yahoo这类搜索引擎当中的广告是搜索广告，而Facebook当中的这些广告是推荐广告。后者和前者最大的区别就是召回广告的逻辑不一样，有点类似于推荐系统和搜索系统的区别。

这其中的核心是用户意图，虽然用户登录Facebook的时候没有强意图，但是根据用户之前的浏览行为以及习惯，我们是可以提取出一些弱意图的。比如用户在哪类商品上停留的时间最长，点击什么样的内容的次数最多，还有类似协同过滤的把用户的行为抽象成向量的做法。其实这里面的内容很多，也非常有价值，可见Facebook在写论文的时候是留了一手的。

具体做法

终于到了重头戏了，虽然这篇paper当中讲了很多其他方面的内容，但是我们都知道GBDT+LR才是它的重点。GBDT和LR我们都很熟悉，但是它们两个怎么combine在一起呢？

其实这个问题本身就是错的，所谓GBDT+LR并不是两个模型的结合，而是一种特征的转化。也就是说这个问题我们需要从特征的角度去思考而不是从模型。

paper当中先讲了两种常用的处理特征的方法，第一种是叫做bin，也就是分桶的意思。比如说收入，这是一个连续性特征。如果我们把它放入模型，模型学到的就是它的一个权重，也就说它是线性起作用的。然而在实际的场景当中，可能这完全不是线性的。比如有钱人喜欢的品牌和穷人可能完全不同，我们希望模型能够学到非线性的效果。一种比较好的办法就是人为将这个特征进行分桶，比如根据收入分成年收入3万以下的，3万到10万的，10万到50万的，和50万以上的。落到哪个桶里，哪个桶的值标为1，否则标为0。

第二种方法叫做特征组合，这个也很好理解，比如性别是一个类别，是否是高收入群体是个类别。那我们排列组合一下，就可以得到男_低收入，男_高收入，女_低收入和女_高收入这四个类别。如果是连续性特征，可以使用像是kd-tree这类的数据结构进行离散化。我们把类别特征两两交叉就可以得到更多的特征，但这些特征并不一定都是有用的，有些可能没用，还有些可能有用但是数据很稀疏。所以虽然这样可以产生大量特征，但是需要一一手动筛选，很多是无效的。

由于手动筛选特征的工作量实在是太大，收益也不高，所以工程师就开始思考一个问题：有没有办法可以自动筛选特征呢？现在我们都知道可以让神经网络来做自动的特征交叉和筛选，但是当时神经网络还没有兴起，所以还是只能手动进行。为了解决这个问题，当时的工程师们想到了GBDT。

这才是会有GBDT+LR的原因，我们来看这张图：

我们来简单回顾一下GBDT的模型，首先GBDT是由多棵树组成的森林模型。对于每一个样本，它在预测的时候都会落到每一棵子树的其中一个叶子节点上。这样我们就可以使用GBDT来进行特征的映射，我们来看个例子：

在上图这个例子当中，GBDT一共有3棵子树，第一棵子树有3个叶子节点。我们的样本落到了第一个，所以第一棵子树对应的one-hot结果是[1, 0, 0]，第二棵子树也有3个节点，样本落到了第二个节点当中，所以one-hot的结果是[0, 1, 0]，同理可以得到第三棵子树的结果是[0, 0, 1, 0]。

这样我们最后把这些树的向量合并在一起，就得到了一个新的向量：[1, 0, 0, 0, 1, 0, 0, 0, 1, 0]，这个向量就是我们LR模型的输入。

我们来分析一下细节，首先明确一点，GBDT只是用来进行了特征转化和处理，它的预测结果并不重要。通过使用GBDT我们同时完成了刚才提到的两种操作，既把连续性特征转换成了离散型特征，也自动完成了特征的交叉。因为对于每一棵子树而言，其实本质上是一棵CART算法实现的决策树，也就是说从树根到叶子节点的链路代表了一种潜在的规则。所以我们可以近似看成使用了GBDT代替人工进行了规则的提取以及特征的处理。

为什么是LR

什么是LR大家已经知道了，但还有一个问题却没有回答。那就是为什么早年的时候LR模型如此受欢迎呢？难道就不能使用其他一些看起来高级一些的模型吗，比如决策树、随机森林、GBDT？不是说XGBoost在各种比赛的效果都非常好吗？为什么业内不用来做推荐呢？

尤其是当我读到2014年Facebook推出的GBDT+LR的paper的时候，这种困惑更是明显。

这篇论文非常经典，在业内地位很重，甚至可以说是推荐领域必读的paper之一。深度学习兴起之前很多公司和厂商都沿用了这个做法，论文当中的做法倒是不难，说是创新的做法，其实本质上就是将GBDT预测的时候样本落到的节点作为multi-hot编码，然后将这个编码之后的01的数组看成是新的特征，然后用这个转换过的特征来训练LR。可以说它的本质仍然是训练LR，所谓的GBDT只不过是一个编码器。

我当时看这篇paper的时候，里面的意思都已经理解了，但是有一个问题怎么也没想明白。既然都用GBDT了，结合其他模型不香吗，非得结合LR？

我估计这个问题很多在推荐领域的从业者可能也未必答得上来，我先卖个关子，把问题记在这里，等会晚点来回答。

推荐领域的特征有什么特点？

在算法领域，提及效果，特征和模型两者是一体两面，很难剥离。好的模型也需要好的特征支撑，好的特征需要好的模型才能充分表达。所以我们先把模型的问题放一放，来思考一下特征。

推荐领域主要的特征只有三块，以电商为例，分别是item，user和context。也就是商品，用户以及环境信息，比如时间，地点，展示位置等等。context特征比较少，来来回回就那么几样，我们也先放一放。剩下的就是用户和商品，围绕用户和商品我们形成的特征主要又可以分成两个部分，一个是基础特征，另外一个是统计特征。

以商品举例，基础特征就是品牌、价格、类目、评价，统计特征就是最近点击率、最近销售额、最近转化率等等。这些特征按照类别分又可以分为两种，一种是浮点型的连续型特征，一种是类别特征，比如商品的类目，品牌等等。到这里都很正常，没有什么难理解，或者是不可思议的部分。

我们接着往下，再来看看模型要预测的目标——点击率。我们结合一下模型预测的目标再来观察一下前面列举的特征，你会发现，除了历史点击率、历史转化率等少数几个指标和最终的结果是强正相关之外，其他的浮点型的特征没有特别明显的正相关或者是负相关。可以说商品的价格和点击率负相关吗？其实不太行，商品越便宜可能质量越差，反而不会有人点。用户的购买力呢？越有钱点的商品越多吗？也不成立。

正是因为上面说的这个原因，所以在推荐领域，效果很好的浮点型特征很少，大部分都是类别特征，也就是01特征。

所以你说GBDT、随机森林、XGboost这些模型的效果会很好吗？很难说，因为这些模型的长处往往都在浮点型特征，也就是连续型特征。这些树模型会设计规则对这些连续特征进行分段，如果大部分特征都是01特征，那还怎么分段呢？

所以，到这里也就回答了，为什么在深度学习模型兴起之前，推荐领域普遍都使用LR，而不是那些看着很牛的树模型。

LR模型的原理

LR模型也就是纯线性模型，它可以简单理解成若干个特征的加权和。每个特征的权重或大或小，最后累加在一起，得到一个预测的概率。这毫无毛病，也是学过的人都知道。

但我们往下一层，有没有想过这一点在推荐领域意味着什么呢？

意味着模型其实是”记住“了每个特征和最终结果的关系，我们把模型拟人化，把它看成一个机器人的话。机器人看到样本有特征A并且点击了，于是特征A的权重提升一点，样本有特征B但是没点击，于是把特征B的权重降低一些。模型就是在这样一个策略当中找到一个最佳的平衡。

这就意味着，一些容易被记忆的特征往往会发挥比较好的效果。比如男士通常会买烟，女士通常买口红，那么我们就可以设计男士_烟和女士_口红的组合特征。当模型看到大部分男士看到烟都点击了之后，它就能学到这个组合是一个强特征并给与一个比较高的权重。这样只要我们尽可能地找出这些特征的组合，那么模型就可以得到很好的效果。

所以到这里大家就明白了，LR模型在推荐领域发挥作用，本质上就是靠的“记性”。因为它可以记住那些类别特征以及类别特征的组合，所以它往往比 那些看起来更高端的树模型效果要好。这也是为什么到了LR时代的后期，算法工程师们的工作就是整天挖掘一些类别特征的组合，以期望模型达到很好的效果。

LR模型的优缺点

到这里，关于LR模型在推荐领域的应用就差不多说完了，我们做一个简单的总结，首先从它的优点开始说起。

LR模型的优点教科书上已经说了很多了，比如训练速度快，由于参数空间比较小，LR模型可以迅速收敛，它的训练速度要比那些树模型以及后面的深度学习模型快得多。其次是可解释性强，由于我们可以查阅得到所有特征的权重，所以我们很容易解释究竟是什么特征发挥了作用，或者是什么特征拖了后腿。

但是LR在推荐领域也有一个很大的缺点，是什么呢，就是脏活累活很多。

因为几乎所有的特征组合都需要人工挖取，需要人工遍历很多特征组合，甚至是一一尝试找到最佳的组合。这个过程当中需要花费大量的人力，几乎可以说是纯堆人工。所以对于LR时代的算法工程师来说可能螺丝钉的感觉比现在还要严重得多，什么优化模型基本上是不用想了，LR这么简单的模型也没什么优化的空间，剩下的事情基本上就只有做特征做实验了。

FM

介绍一个业内使用得更多的模型，它诞生于2010年，原作者是Steffen Rendle。虽然诞生得更早，但是它的活力更强，并且衍生出了多种版本。我们今天剖析的就是这篇2010年最经典的原版论文。

说到推荐、广告的算法模型，几乎很难绕开FM，它是一个非常强的模型。理论简单、推导严谨、实现容易，并且效果不俗。即使是目前仍然在各大厂商当中发挥用场，在一些小厂当中甚至是主力模型。我们初看之前也许还有疑惑，但是相信当大家看完之后，必然会有全新的认识。

简介

FM的全称是Factorization Machines，翻译过来就是因式分解机，这么翻译很拗口，不得其神也不得其形，所以我们一般都不翻译简称为FM模型。

论文开篇就讲了FM模型的种种好处，比如和SVM对比，它能够在稀疏的特征当中仍然拥有很好的表现，并且FM的效率非常高，可以在线性时间内获得结果。并且不像非线性的SVM（核函数），FM并不需要将特征转换成对偶形式，并且模型的参数可以直接训练，也不用借助支持向量或者是其他的方法。

除了SVM之外，FM模型和其他的因式分解模型比如SVD、PITF、FPMC比较起来都有非常明显的优势。这些模型往往只针对一个特定的场景或者是特定的数据集，并且它们的训练以及优化方案都是根据场景定制化的。FM模型不需要定制化就可以实现同样好的效果，可以非常简易地应用在各个预测问题当中。

这段摘要其实没什么太多的内涵，主要就是吹嘘了一通FM。不过作者所言不虚，和他列举的这些模型比较起来，FM的确更加出色。

总结一下，FM模型的优点有如下几点：

• FM模型的参数支持非常稀疏的特征，而SVM等模型不行
• FM的时间复杂度为$O(n)$，并且可以直接优化原问题的参数，而不需要依靠支持向量或者是转化成对偶问题解决
• FM是通用的模型，可以适用于任何实数特征的场景，其他的模型不行

paper在一开始的时候就表明了FM模型的优点，给足了好处，之后才是对FM模型的深入分析，让大家明白这些优点是如何得到的，以及它的工作原理。

稀疏场景

在有监督学习的场景当中，最常见的任务就是给定一个向量x，要求预测一个目标T。如果T是一个实数，那么这就是回归模型，如果T是一个类别的常量，就是一个分类模型。

这些都是机器学习的基础知识，相信大家都了解，然而对于线上排序的功能来说，我们重要的是给商品排序，而不是分类。常规来说我们可以将impression和click看成是两个类别进行分类预测，也可以直接用回归模型预测商品的点击率，根据点击率进行排序。这两种其实本质上是一样的，都是针对商品本身进行学习。还有一种方法是更加侧重商品之间的排序，我们的模型学习的是商品之间的优劣关系。

举个例子，比如我们用向量$x_i$表示i商品的特征向量，$x_j$表示j商品的特征向量，那么我们可以将这两个向量合并一起作为输入，进行分类预测。分类的结果表示的是i商品在j商品之前还是反之。这样我们可以通过多次预测，直接得到商品之间的排序关系，而不是根据一个分数进行排序。这样可以在只有正样本的情况下进行训练。这种方法直接训练的模型商品的优劣，业内叫做learning to rank。

然而不论是哪一种做法，都有一个问题绕不开就是特征的稀疏。举个很简单的例子，比如我们对商品的类目进行one-hot处理，在电商场景下商品的类目动辄上万个，那么one-hot之后的结果就是一个长度上万的数组，并且这个数组当中只有一位为1，其他均为0。当然这只是一个例子，除此之外还有许多许多的特征有可能是非常稀疏的。

我们用$m(x)$表示x向量当中非零的元素的个数，用$\hat{m}_D$表示所有x样本平均的非零元素的个数，在大多数真实数据场景下，我们都可以得到$\hat{m}_D \ll n$，这里的n是特征的维数。

当我们交叉特征做到后面，能够覆盖的样本的数量会非常非常少，尤其是一些本来就很小众的特征之间的交叉。举个例子，比如说高收入人群_房产这个交叉特征。对于电商平台来说，房产本来就是很小众的领域，只有极少数人才会闲着没事在电商网站看房子。同样高收入人群可能也很小众，毕竟大部分人都是普通打工人，收入有限。这么一来，这样得到的交叉特征能够覆盖的样本就会非常非常稀疏。

大家可以简单计算一下，假设房产在电商平台的商品当中的占比是1%，高收入群体在总用户占比是10%的话，那么两者交叉之后的占比就成了千分之一。那这样稀疏的样本在训练模型的时候，我们是很难保证这个特征对应的权重已经训练到了最佳程度。

如果说只是脏活累活多对于大公司来说倒也不是不可以忍受，大不了多雇一点人手就是了。但现在摆明了做出来的特征很有可能因为覆盖率的问题没有效果，那么这就不是很能接受了。

特征交叉的稀疏性以及大量的人力成本，这两个问题是LR模型绕不开的硬伤，也是它被FM代替的直接原因。

真实场景例子

paper当中举了一个真实场景的例子，我们的问题是预测用户对于一部电影的评分。我们先来观察一下下图，下图是样本矩阵。

很明显上图的左边一大块是特征，右边的Target y表示的预测结果，也就是用户可能对电影做出的评价。这里一共有[1, 2, 3, 4, 5]这5种可能，也就是说这是一个多分类的问题。

接着我们再来看特征，特征一共也有5个部分，其中蓝色的部分表示的用户的one-hot。那么这个数组的长度应该是用户的数量，只有代表当前用户的那一维为1，其他均为0。

红色部分表示电影，同样是电影的one-hot，和用户的one-hot是一样的逻辑。代表当前电影的那一维度为1，其他为0。

之后是黄色的部分，表示的之前用户对于电影的评分行为，维度同样是电影的数量。凡是用户评分过的电影分数大于0，没有评分的等于0。得分的计算逻辑是1除以用户评论过的电影数量。比如第一行当中，第一个用户评价过前三部电影，所以前三部电影每一部分到了的分数。

绿色的部分只有1维，表示的是用户评论电影的时间。计算方法是将记录当中最早的日期作为基数（这里是2009年1月），之后每过一个月，增加1。比如2009年5就可以折算成5。

最后棕色的部分表示的是用户最近一次评论的电影，这同样是一个one-hot的数组，它的维度和电影的数量是一致的。

我们假设用户的数量是U，电影的数量是M，那么最后得到的整个特征的维度数应该是U+3M+1。即使是小众一些的电影评分网站，用户数也至少是以上百万起的，再加上电影的数量，这显然是一个非常庞大的数字。而在这么庞大的维度当中只有少数的一些维度是有值的，其余均为0。

对于这样稀疏的特征矩阵而言，一般的模型是很难保证效果的。为什么FM模型可以置身其外呢？下面，我们就来看看FM模型的原理。

FM模型原理

在我们介绍FM模型的方程之前，我们先来回顾一下线性回归的表达式，其实非常简单，只有一行：

$$Y=W^T X=w_0+\sum_{i=1}^n w_i x_i$$

也就是说$W=\left(w_0, w_1, w_2, \cdots, w_n\right)$，W是这样一个n+1维的向量，X是一个n x m的特征矩阵。这里的n是特征的维数，m是样本的数量。所以我们也经常把它写成$Y=X W$，不管怎么写，形式都是一样的。

这个式子称为线性回归的原因也很简单，因为它就是一个简单的线性方程，只有一次项。但是一次项有时候效果不好，尤其是在特别稀疏的场景当中，刻画能力不够。我们做特征的时候经常会把两项特征组合起来做成新的组合特征，由于我们这样操作引入了新的特征，找到了新的特征组合，所以能够挖掘出之前无法得到的信息，因此模型也会有更好的效果。

当我们把特征进行二项组合之后，会得到这样的式子：

$$\hat{y}=w_0+\sum_{i=1}^n w_i x_i+\sum_{i=1}^{n-1} \sum_{j=i+1}^n w_{i j} x_i x_j$$

这里的$x_i$和$x_j$分别表示两个不同的特征取值，对于n维的特征来说，这样的组合应该一共有$C_n^2$种，这个值是$\frac{n(n-1)}{2}$，也就意味着我们需要同样数量的权重参数。但是有一个小问题，我们前面已经说过了，由于特征可能非常稀疏，导致n非常大，比如上百万，这里两两特征组合的特征量级大约是n的平方，那么因此带来的参数数量就是一个天文数字。想想看对于一个上百亿甚至更多参数空间的模型来说，我们需要多少训练样本才可以保证完全收敛？这是不可想象的。

既然如此，那么针对性的优化就是必不可少的。FM为人称道的也正是这一点，既引入了特征交叉，又解决了复杂度以及模型参数的问题，真的可以说是非常棒了。

FM解决这个问题的方法非常简单，它不再是简单地为交叉之后的特征对设置参数，而是设置了一种计算特征参数的方法。FM模型引入了新的矩阵V，矩阵V是一个n x k的二维矩阵。这里的k是我们设置的参数，一般不会很大，比如16、32之类。对于特征每一个维度i，我们都可以找到一个$v_i$，它表示一个长度为k的向量。

于是我们可以用$v_i$和$v_j$来计算得出上式当中的$w_{ij}$：

$$w_{i j}=v_i^T v_j$$

也就是说我们用向量的内积来计算得到了就交叉特征的系数，相比于原先$O\left(n^2\right)$量级的参数而言，我们将参数的量级降低到了n x k。由于k是一个常数值，所以可以看成我们的参数数量是$O(n)$。通过这种方式我们把参数的数量降低了一个数量级。

有了V矩阵之后，刚才的公式可以改写成：

$$\hat{y}=w_0+\sum_{i=1}^n w_i x_i+\sum_{i=1}^{n-1} \sum_{j=1}^n v_i^T v_j x_i, x_j$$

我们很容易可以知道，当k这个参数足够大的时候，我们可以保证$W=V \cdot V^T$成立。所以我们引入的参数矩阵V可以看成是对W矩阵做了一个因子分解，这也是FM得名的由来。当然在实际的应用场景当中，我们并不需要设置非常大的K，因为特征矩阵往往非常稀疏，我们可能没有足够多的样本来训练这么大量的参数，并且限制K也可以一定程度上提升FM模型的泛化能力。

此外这样做还有一个好处就是有利于模型训练，因为对于有些稀疏的特征组合来说，我们所有的样本当中可能都是空的。比如在刚才的例子当中用户A和电影B的组合，可能用户A在电影B上就没有过任何行为，那么这个数据就是空的，我们也不可能训练出任何参数来。但是引入了V之后，虽然这两项缺失，但是我们仍然可以得到一个参数。因为我们针对用户A和电影B训练出了一个向量参数，我们用这两个向量参数点乘，就得到了这个交叉特征的系数。

这种做法有两种理解方式，一种就是刚才说的，我们对于一些稀疏的组合也可以很好地计算出系数。另外一种理解方式是这其实也是一种embedding的方式，将某一个id映射成向量。所以业内也有使用FM来做embedding的。

复杂度优化

接下来我们来看另外一个很精髓的内容，就是关于FM模型的复杂度优化。我们观察一下刚才上面的式子，不难发现，目前对于预测一条样本的计算复杂度为$O\left(k n^2\right)$。

n我们前文说过了是一个比较大的数字，那么显然$n^2$级的计算也是我们不能接受的。所以对它进行优化也是必须的，并且这里的优化非常简单，可以直接通过数学公式的变形推导得到。

$$\hat{y}=w_0+\sum_{i=1}^n w_i x_i+\sum_{i=1}^{n-1} \sum_{j=1}^n v_i^T v_j x_i, x_j$$

这个是它的原式，对于这个式子来说，前面两项的复杂度是$O(n)$，我们可以先忽略，重点来看最后一项。我们要做的就是通过数学公式的变形来对这一项进行化简：

$$\begin{aligned} \sum_{i=1}^n \sum_{j=i+1}^n v_i^T v_j x_i x_j & =\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n v_i^T v_j x_i x_j-\frac{1}{2} \sum_{i=1}^n v_i^T v_i x_i x_i \\ & =\frac{1}{2}\left(\sum_{i=1}^n \sum_{j=1}^n \sum_{f=1}^k v_{i, f} v_{j, f} x_i x_j-\sum_{i=1}^n \sum_{f=1}^k v_{i, f} v_{i, f} x_i x_i\right) \\ & =\frac{1}{2} \sum_{f=1}^k\left(\left(\sum_{i=1}^n v_{i, f} x_i\right)\left(\sum_{j=1}^n v_{j, f} x_j\right)-\sum_{i=1}^n v_{i, f}^2 x_i^2\right) \\ & =\frac{1}{2} \sum_{f=1}^k\left(\left(\sum_{i=1}^n v_{i, f} x_i\right)^2-\sum_{i=1}^n v_{i, f}^2 x_i^2\right) \end{aligned}$$

简单来解释一下这个推导过程，第一行我想大家应该都能看懂，第二行也很好理解，其实就是把$v_i^T v_j$向量内积展开。第二行到第三行的转化也不难理解，这里有三个$\sum$，我们提取出的是最里面的$\sum$，因为是有限项求和，我们调换顺序并不会影响结果。提取出了公因式之后，得到的结果是两个平方项。我们观察一下可以发现，这两个平方项的计算复杂度都是$O(n)$，再加上外面一层$O(k)$的复杂度，整体的复杂度是$O(kn)$。

这样我们就完成了FM模型预测的优化。

模型训练

我们再来看下模型训练的过程，我们写出变形之后的原式：

$$\hat{y}=w_0+\sum_{i=1}^n w_i x_i+\frac{1}{2} \sum_{f=1}^k\left(\left(\sum_{i=1}^n v_{i, f} x_i\right)^2-\sum_{i=1}^n v_{i, f}^2 x_i^2\right)$$

针对FM模型我们一样可以使用梯度下降算法来进行优化，既然要使用梯度下降，那么我们就需要写出模型当中所有参数的偏导。

我们可以把参数分成三个部分，第一个部分自然是$w_0$，$\frac{\partial \hat{y}}{\partial w_0}=1$。第二个部分是$\sum_{i=1}^n w_i x_i$，对于其中每一个$w_i$来说它的系数是$x_i$。由于样本是固定的，我们要把样本的特征值看成是常数。所以$\frac{\partial \hat{y}}{\partial w_i}=x_i$。最后一个部分就是$\frac{1}{2} \sum_{f=1}^k\left(\left(\sum_{i=1}^n v_{i, f} x_i\right)^2-\sum_{i=1}^n v_{i, f}^2 x_i^2\right)$$\frac{1}{2} \sum_{f=1}^k\left(\left(\sum_{i=1}^n v_{i, f} x_i\right)^2-\sum_{i=1}^n v_{i, f}^2 x_i^2\right)$看起来复杂很多，但其实偏导也不难求，我们首先明确这里要优化的参数是$v_{i, f}$，所以我们可以忽略最外层的一层$\sum_{f=1}^k$，直接对括号内的进行求导，得出的结果是$\left.\frac{\partial \hat{y}}{\partial v_{i, f}}=x_i \sum_{j=1}^n v_{j, f} x_j-v_{i, f} x_i^2\right)$。

我们把这三种综合一下，就得到了：

$$\frac{\partial \hat{y}}{\partial \theta}=\left\{\begin{array}{lr} 1, & \text { if } \theta \text { is } w_0 \\ x_i, & \text { if } \theta \text { is } w_i \\ \left.x_i \sum_{j=1}^n v_{j, f} x_j-v_{i, f} x_i^2\right. & \text { if } \theta \text { is } v_{i, f} \end{array}\right.$$

其中$\sum_{j=1}^n v_{j, f} x_j$和i是独立的，所以它是可以提前算好的，这样一来对于所有参数项，我们都可以在$O(1)$的时间内计算出它们的梯度。由于我们所有参数的量级是$O(k n)$，意味着我们可以在$O(k n)$时间内对所有的参数完成梯度下降的更新。

拓展到d维

我们刚才介绍的FM模型专注的是二维特征交叉的情况，如果我们愿意也可以将它拓展到d维特征交叉的情况。这样的话我们的特征可以拟合任意$\tilde{d}(1 \leq \tilde{d} \leq d)$维特征交叉的相互关系。

我们仿照刚才的公式，可以写出FM模型推广到d维的方程：

$$\hat{y}=w_0+\sum_{i=1}^n w_i x_i+\sum_{l=2}^d \sum_{i=1}^n \ldots \sum_{i_l=i_{l-1}+1}^n\left(\Pi_{j=1}^l x_{i_j}\right)\left(\sum_{f=1}^{k_l} \Pi_{j=1}^l v_{i_j, f}^{(l)}\right)$$

前面两项都很好理解，我们着重来看第三项。第三项当中包含了从2维到d维交叉特征的情况，我们以d=3为例，那么这一项当中应该包含二维的交叉项以及三维的交叉项，应该是这样的：

$$\sum_{i=1}^{n-1} \sum_{j=i+1}^n x_i x_j\left(\sum_{t=1}^k v_{i, t} v_{j, t}\right)+\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{l=j+1}^n x_i x_j x_l\left(\sum_{t=1}^k v_{i, t} v_{j, t} v_{l, t}\right)$$ $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n x_i x_j\left(\sum_{t=1}^k v_{i, t} v_{j, t}\right)+\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{l=j+1}^n x_i x_j x_l\left(\sum_{t=1}^k v_{i, t} v_{j, t} v_{l, t}\right)$$

这个式子整体上和之前的形式是一样的，我们不难分析出它的复杂度是$O\left(k n^d\right)$。当d=2的时候，我们通过一系列变形将它的复杂度优化到了$O(k n)$，而当d>2的时候，没有很好的优化方法，而且三重特征的交叉往往没有意义，并且会过于稀疏，所以我们一般情况下只会使用d = 2的情况。

代码实现

上面这段大家了解一下知道有这么回事就可以了，实际上意义不大。最后的时候paper还比较了FM和其他一些经典的模型的效果，比如SVD、SVM等，也没太多价值，因为现在在推荐领域已经几乎没有人直接使用这些模型了。最后我贴一下我用pytorch和TensorFlow两个框架分别实现的FM模型，给大家做一个参考。

Pytorch

import torch
from torch import nn

ndim = len(feature_names)
k = 4

class FM(nn.Module):
    def __init__(self, dim, k):
        super(FM, self).__init__()
        self.dim = dim
        self.k = k
        self.w = nn.Linear(self.dim, 1, bias=True)
        # 初始化V矩阵
        self.v = nn.Parameter(torch.rand(self.dim, self.k) / 100)
        
    def forward(self, x):
        linear = self.w(x)
        # 二次项
        quadradic = 0.5 * torch.sum(torch.pow(torch.mm(x, self.v), 2) - torch.mm(torch.pow(x, 2), torch.pow(self.v, 2)))
        # 套一层sigmoid转成分类模型，也可以不加，就是回归模型
        return torch.sigmoid(linear + quadradic)
    
    
fm = FM(ndim, k)
loss_fn = nn.BCELoss()
optimizer = torch.optim.SGD(fm.parameters(), lr=0.005, weight_decay=0.001)
iteration = 0
epochs = 10

for epoch in range(epochs):
    fm.train()
    for X, y in data_iter:
        output = fm(X)
        l = loss_fn(output.squeeze(dim=1), y)
        optimizer.zero_grad()
        l.backward()
        optimizer.step()
        iteration += 1        
        if iteration % 200 == 199:
            with torch.no_grad():
                fm.eval()
                output = fm(X_eva_tensor)
                l = loss_fn(output.squeeze(dim=1), y_eva_tensor)
                acc = ((torch.round(output).long() == y_eva_tensor.view(-1, 1).long()).sum().float().item()) / 1024
                print('Epoch: {}, iteration: {}, loss: {}, acc: {}'.format(epoch, iteration, l.item(), acc))
            fm.train()

TensorFlow

import tensorflow as tf
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score, roc_auc_score
import numpy as np


class FactorizationMachine:

    def __init__(self, n_dim=1, k=4, learning_rate=0.05, epochs=8):
        self._learning_rate = learning_rate
        self._n_dim = n_dim
        self._k = k
        self._epochs = epochs
        self.sess = tf.Session()
        self.x_input = tf.placeholder(shape=[None, self._n_dim], dtype=tf.float32)
        self.y_input = tf.placeholder(shape=[None, 1], dtype=tf.float32)
        # 初始化W和V
        self.w = tf.Variable(tf.truncated_normal(shape=[self._n_dim, 1], dtype=tf.float32))
        self.V = tf.Variable(tf.truncated_normal(shape=[self._n_dim, self._k], dtype=tf.float32))
        self.b = tf.Variable(tf.truncated_normal(shape=[1, 1]))
        self.linear = tf.add(self.b, tf.matmul(self.x_input, self.w))
        self.quadratic = 1/2 * tf.reduce_sum(tf.square(tf.matmul(self.x_input, self.V)) - tf.matmul(tf.square(self.x_input), tf.square(self.V)), axis=1, keepdims=True)
        self.y_out = self.linear + self.quadratic
        self.y_pred = tf.round(tf.sigmoid(self.y_out))
        self.loss = tf.reduce_mean(tf.nn.sigmoid_cross_entropy_with_logits(logits=self.y_out, labels=self.y_input))
        self.train_op = tf.train.GradientDescentOptimizer(self._learning_rate).minimize(self.loss)
        self.accuracy = tf.reduce_mean(tf.cast(tf.equal(self.y_pred, self.y_input), tf.float32))
        init = tf.global_variables_initializer()
        self.sess.run(init)

    def train(self, X, Y, iterations=1000, batch_size=16, validation_size=0.1):
        x_train, x_test, y_train, y_test = train_test_split(X, Y, test_size=validation_size)
        for epoch in range(self._epochs):
            for i in range(iterations):
                rand_idx = np.random.choice(x_train.shape[0], size=batch_size)
                rand_x = x_train[rand_idx]
                rand_y = y_train[rand_idx]
                self.sess.run(self.train_op, feed_dict={self.x_input: rand_x, self.y_input: rand_y})
                if i % 100 == 99:
                    loss = self.sess.run(self.loss, feed_dict={self.x_input: x_test, self.y_input: y_test})
                    acc = self.sess.run(self.accuracy, feed_dict={self.x_input: x_test, self.y_input: y_test})
                    print('epoch = {}, iteration ={}, loss = {}, accuracy ={}'.format(epoch, i, loss, acc))

    def predict(self, x):
        return self.sess.run(self.y_pred, feed_dict={self.x_input: x})

注：TensorFlow代码使用的1.0版本

优缺点

对于FM模型来说，它最大的优点就是拟合能力很强，因为引入了二阶交叉的特征项，所以对于样本的表达能力大大提升。并且由于通过数学公式，我们将$O\left(n^2\right)$的复杂度降到了$O(n)$。它的训练以及预测速度都是非常快的，和LR旗鼓相当。

我们再来回顾一下LR的两个问题，一个是需要人工制作大量的特征，第二个是样本稀疏对于模型的训练会有影响。

第一个问题已经没有了，因为FM引入了自动交叉的机制，相当于默认帮助我们把所有的二阶交叉特征都做了一遍。但对于第二个问题我们还需要分析一下，为什么FM模型可以解决样本稀疏的问题呢？二阶交叉项不还是会面临样本很少的情况吗？

原因很简单，因为FM把特征映射成了向量，在进行特征交叉的时候是通过向量的点乘来计算的交叉项的权重。对于特征i来说，它和其他所有特征交叉时使用的都是同一个向量$V_i$。这样即使特征i和j的组合在样本当中非常稀疏，但是由于$V_i$和$V_j$是单独训练的，所以我们仍然可以得到一个相对比较准确的权重。甚至即使i和j的组合在样本当中没有出现过，但是由于有了$V_i$和$V_j$向量，我们一样可以表达i和j的组合特征，这也是正是FM强大的地方。

FM虽然强大但也不是没有缺点，我们随便想想也能找出来不少。比如说虽然模型自动做了二阶交叉，但是二阶交叉真的能表达所有的特征信息吗？会不会有一些三阶交叉的特征，甚至是四阶交叉的特征会更有效果呢？而且所有的特征交叉都进行了学习，会不会当中有很多无用信息被包含进来了呢？再比如FM当中设定了每个特征和其他所有特征交叉的时候使用的向量是同一个，这样一刀切真的效果最好吗？再比如FM模型很难对连续性特征进行交叉，基本上只能交叉01离散型的特征，这样真的不会丢失信息吗？

和SVM的区别

• SVM的二元特征交叉参数是独立的，而FM的二元特征交叉参数是两个k维的向量$v_i$、$v_j$，交叉参数就不是独立的，而是相互影响的。
• FM可以在原始形式下进行优化学习，而基于kernel的非线性SVM通常需要在对偶形式下进行。
• FM的模型预测是与训练样本独立，而SVM则与部分训练样本有关，即支持向量

为什么线性SVM在和多项式SVM在稀疏条件下效果会比较差呢？

• 线性svm只有一维特征，不能挖掘深层次的组合特征在实际预测中并没有很好的表现
• 多项式svn正如前面提到的，交叉的多个特征需要在训练集上共现才能被学习到，否则该对应的参数就为0，这样对于测试集上的case而言这样的特征就失去了意义，因此在稀疏条件下，SVM表现并不能让人满意。而FM不一样，通过向量化的交叉，可以学习到不同特征之间的交互，进行提取到更深层次的抽象意义。

延伸

Embedding

FM之所以效果很好，除了模型做了所有特征的二阶交叉之外，很重要的原因是它对类别特征做了embedding。

还没入门的同学不要觉得蒙，embedding其实很好理解，我们就当做是向量理解就可以了，它可以理解成把一个单个的标量转化成一个向量的形式。大家如果对NLP有所了解的话，会知道在NLP当中有一个基础算法叫做Word2vec，这个Word2vec讲的就是单词到向量的转化。我们可以通过算法模型通过学习文本单词的上下文关系，从而学习到每一个单词的向量表达。有了向量表达之后，我们就可以利用向量的性质做很多事。

我在网上找了一张示意图，当单词被表达成向量之后，意思相近的单词的向量也会非常接近。利用向量的性质我们可以做很多有意思的事情，比如近义词同义词分析，比如近义词召回，机器翻译等等。

在推荐领域当中的embedding和NLP差不太多，本质上也是把一个特征转化成向量。当然推荐领域一般不会直接用这个向量来表达，而是将它作为模型的输入。

到这里我们先暂停一下，先来思考一个问题：为什么把单个特征转化成向量效果会更好？

这个其实可以有很直观的解释，比如我们有一个特征是性别。如果性别作为一个单个特征，对于模型来说就只有0和1两个意思。但对于我们人类，其实是有很多层含义的。比如说女性大概率会喜欢美妆用品，女性在电商平台的表现也会比男性活跃，女性对于折扣更加敏感……只要我们愿意思考，可以想出很多的这样的特性来。显然这么多复杂的特性只用简单的0和1是无法表达的，所以这就是为什么我们要把它转化成向量的原因，因为向量的维度更高，表达能力更强。

第二个是当前的基于深度神经网络的模型有能力消化这些高维度的特征，神经网络当中有大量的神经元，神经元之间存在大量的信号传递，可以充分学习到高维度向量当中的含义。

你可能还会有问题，那从哪里可以搞到特征的向量表达呢，我们怎么知道怎么表达特征才是正确的呢？这个问题很简单，我们并不需要额外去准备特征的embedding，我们只需要将它作为模型的参数的一部分，让它通过梯度下降自己学习即可。也就是说embedding本身就是模型参数的一部分，模型收敛了，embedding也就有了，并不需要我们额外操心。

正是因为有了embedding，推荐、搜索等引擎的效果才有了大幅提升，而embedding的使用正是从FM模型开始的。FM模型用一个向量V来表示特征之间交叉权重的做法，其实就是一种embedding。

VIP类别特征

有了embedding之后，自然而然地带来了一个有趣的变化：推荐系统当中的类别特征逐渐都变成了VIP，而实数型特征则江河日下到了淘汰的边缘。

我们如果来分析一下电商场景下的推荐，你会发现当中有一个很重要的环节就是“打标签”。也就是给用户给商品打上各种各样的标签，然后通过推荐引擎来通过这些标签进行推荐。

比如说你喜欢电子产品，那你就是一个“电子达人”，她喜欢裙子，那她是“时尚女装”。这个商品很热销，那它是“当季爆款”，有个商品封面放了个大胸妹很吸引人，那它是“标题党”等等……

有了标签之后，模型就可以很容易理解到这些标签之间的作用关系。比如一个电子达人多半是直男，是不会对洛丽塔感兴趣的。同样爆款商品往往也只能吸引那些对于折扣、促销比较敏感的人群，对于钢铁直男同样没有效果……并且由于系统可以拿到用户在平台上活动的所有数据，我们还可以根据用户之前的行为来进行分析。

比如说用户在这一次登陆之前浏览的一直是女装商品，那即使他原本的标签是”钢铁直男“，那么系统也会因地制宜，实时了解到他兴趣的变化，给女装商品提升权重，增加曝光。

正是有了标签一样的特征，模型才能有很好的泛化能力。如果我们把商品的标签转化成商品最近的点击率、最近的转化率、最近的成交额、最近的好评数等特征，你想想看模型还能做出这样神奇的推荐吗？显然不行，因为实数型的特征没有办法做成embedding， 模型表达的能力也会受到影响。

除此之外一些实数型特征和推荐目标之间没有线性关系，比如年龄，你能说年龄越大越喜欢游戏机吗？显然不是，年龄太小或者年龄太大都不行，就只有某一个年龄段最喜欢。

所以最好的办法是对这些实数型的特征分桶，将它强行转化成类别特征。比如18岁以下一个桶，18到30岁一个桶，30岁到50一个桶，50以上一个桶。这样模型拿到的才不会是一个简单的年龄值，而是一个分段，而是一个可以转化成向量的标签。

正是因为以上一系列原因，在推荐系统当中类别特征成了VIP中的VIP，几乎统治一切，很多实数型特征也都会被强行转化成类别特征，沦落称为小弟。我们不仅要了解这些现象，更要透过现象看到本质，了解到变化产生的原因。

AFM和FFM

我们了解embedding和类别特征对于模型的意义之后，再回过头来看FM，会发现FM几乎都涉及到了。只不过FM毕竟还是机器学习时代提出的算法模型，对于神经网络超强的泛化和拟合能力没有很好地使用，所以在后来的深度学习时代有一点点落伍。这并不能说是FM模型设计得不好，相反，它已经是相当超前的设计，使得它横跨十几年即使到了神经网络时代依然能大展身手。

今天我们来简单聊聊关于FM模型的两个演化版本，可以理解成1.1版本。

FFM

FFM模型非常简单，它只是在FM的基础上做了一个很小的优化，即增加了field的概念。原本的FM在做特征交叉的时候，所有特征交叉的权重都一样，也都使用同一个参数向量V。

这样的好处是泛化能力比较强，但是缺点也是太单一了，x和所有的特征y交叉都用同一个向量，一刀切太过粗暴了。所以FFM提出了field的概念，即每个特征都会被映射成多个隐向量：$V_{i, 1}, V_{i, 2} \cdots V_{i, f}$。每个隐向量对应一个field，当两个特征$x_i, x_j$交叉组合的时候，用对方对应的场下对应的隐向量来做内积：

$$w_{i, j}=V_{i, f_j}^T V_{j, f_i}$$

引入了field之后，使得同一个特征x可以做到和不同的向量交叉时使用不同的向量$V$，从而提升了模型的的泛化能力。

AFM

AFM的模型结构和原理很简单，一点也不复杂，就是在FM两两特征交叉的地方加上了一个Attention网络。这个Attention网络用来学习两个向量的权重。

这里的Attention网络其实就是一个多层神经网络，它的表达式如下

$$\begin{aligned} & a_{i j}^{\prime}=h^T \operatorname{ReLU}\left(W\left(v_i \odot v_j\right) x_i x_j+b\right) \\ & a_{i j}=\frac{\exp \left(a_{i j}^{\prime}\right)}{\sum_{(i, j) \in R_x} \exp \left(a_{i j}^{\prime}\right)} \end{aligned}$$

本质上就是我们增加了一个模块专门用来学习交叉项的权重，进行加权求和而已。

AFM

论文是一篇FM的升级论文，叫做Attentional Factorization Machines: Learning the Weight of Feature Interactions via Attention Networks。翻译过来叫做注意力FM：通过Attention网络学习特征交互的权重。它是由浙大和新加坡国立大学的学生在2017年联合发表的，它是基于FM模型的一种优化。

摘要

FM是我们比较熟悉的模型，它引入所有特征的二阶交叉，通过向量内积的方式来计算所有二阶项的系数，来达到提升效果的目的。但是FM也有缺点，虽然我们通过一些数学的方式对它的效率进行了提升，但仍然有些问题没有解决。比如，对于一个固定的特征而言，它和其他特征交叉的向量都是一样的。再比如并不是所有特征的二阶交叉组合都是有用的，有些反而是干扰项。

在这篇paper当中我们通过消除不同特征组合之间的重要性来优化FM模型，我们把这种新的FM模型叫做AFM（Attentional Factorization Machine）。它最大的特性就是特征交叉的重要性是通过attention神经网络获得的。我们在两个实际的数据集上进行了完整的测试，测试结果显示AFM相比FM带来了8.6%的提升。和Wide & Deep以及Deep Cross相比，AFM的参数空间也更小，结构更加简单。

简介

众所周知，在机器学习以及数据挖掘当中，监督学习占据了很大的比重。监督学习某种程度上可以看成是学习一个函数，让它的output越来越接近我们实际想要的值。如果我们想要的值是浮点数，那么这个就是回归模型，如果是一个类别，那么则是分类模型。在推荐系统、在线广告以及图片识别等方面，监督模型起到了举足轻重的作用。

当我们的特征以类别特征为主的时候，让模型学习特征之间的交叉信息会变得非常关键。我们举一个简单的例子，比如我们有职业和层级这两个不同的特征。职业有银行职员以及工程师，层级有初级和高级。其中初级的银行职员的收入要低于初级工程师，而高级的职员收入则要高于高级工程师。如果模型无法学习到交叉信息，是很难预测准确的。

以LR模型举例，LR模型本质上是各个变量的加权求和的结果。无论是初级还是高级，工程师和银行职员这两个职业对应的权重都是一样的。显然，这个时候，模型很难预测准确。

为了考虑特征之间的交叉信息，一种常用的方法是引入新的参数向量，通过向量的内积来计算出交叉的权重。比如polynomial regression（PR）模型，它所有交叉特征的权重都是通过学习得到的。然而这样的设计有一个比较大的问题，就是对于那些稀疏的数据集会有一些交叉特征的权重没有办法学习到。比如说如果是商品的类目和用户的职业交叉，对于某一个冷门的类目以及冷门的职业，我们很难保证训练集当中包含了足够的样本来训练这个权重。

FM模型的提出正是为了解决这个问题，这个大家应该也都很熟悉了，我就不多说了。简而言之就是通过给每一个特征赋予一个向量的方式，当两个特征交叉的时候，通过计算它们向量的内积来代表它们交叉特征的权重。因为这种创新设计，FM取得了巨大的成功，在推荐系统以及NLP领域都有应用。但是FM模型仍然也有缺陷，比如在现实世界当中，不同的特征往往起到的效力不同，并不是所有特征都适合用来进行特征的交叉。所以一个改进思路是对于那些效力不高的交叉项进行降权，对不同的交叉特征进行自动升权或降权。

在这篇paper当中我们通过对特征交叉的组合进行区别对待的方式来提升FM的效果，区别对待的方式就是引入Attention神经网络的机制。

AFM

Model

下图展示的就是AFM模型的结构，为了方便观看，我们去除了线性回归的部分。

input层以及Embedding层都和FM模型一致，它的输入是一个sparse表示的特征，它会把非零项转化成float向量。接下来，我们会详细解释一下pair-wise interaction层也就是二维特征的交叉层以及Attention-based Pooling层，这些也是这篇paper的主要内容。

Pair-wise interaction Layer

受到FM当中二阶特征交叉做法的启发，我们在神经网络当中也做同样的处理。它通过element-wise-product（哈达玛积）的方式将两两向量组合在一起，对于m个向量，这样的组合一共有m(m-1)/2种。我们来举个例子，假设在向量x当中非零的特征为$\chi$，它embedding之后的结果是$\epsilon=\left\{v_i x_i\right\}_{i \in \chi}$。对于这些特征，我们两两组合之后得到的结果为：

$$f_{P I}(\epsilon)=\left\{\left(v_i \odot v_j\right) x_i x_j\right\}_{(i, j) \in R_x}$$

其中$\odot$表示两个向量的哈达玛积，$R_x$表示$\{(i, j)\}_{i \in \chi, j \in \chi, j>i}$，$f_{P I}$表示Pair-wise Interaction这一层的输出。通过定义pair-wise interaction层来提供权重，我们可以使用神经网络结构来表示FM。我们首先把$f_{P I}(\epsilon)$使用sum pooling（池化）来进行压缩，然后通过全连接层来预测分数：

$$\hat{y}=p^T \sum_{(i, j) \in R_x}\left(v_i \odot v_j\right) x_i x_j+b$$

这里的$P^T \in R^k$， $b \in R$分别表示权重和偏移量。如果我们固定p=1，b=0，那么上面这个式子和FM模型是完全一样的。pair-wise interaction layer可以简单地看成是权重层，用来给FM当中二阶交叉项提供权重。接下来我们来看Attention-based Pooling层。

Attention-based Pooling Layer

Attention机制在神经网络模型当中广泛使用，它的主要思想是当我们把多项累加在一起的时候，允许每一项的权重不同。可以简单理解成一种自动加权的机制，它的权重也是通过神经网络来学习自动赋予的，而不是我们事先固定的。和FM结合起来之后，也就是说FM当中每一个二阶交叉项的权重都是通过Attention网络学习得到的：

$$f_{A t t r}\left(f_{P I}(\epsilon)\right)=\sum_{(i, j) \in R_x} a_{i j}\left(v_i \odot v_j\right) x_i x_j$$

其中$a_{i j}$是attention网络提供给i和j交叉项的权重，求这些权重最简单的方法就是把它也作为模型的参数，让模型自己来学习。但有一个问题是很多交叉项在样本当中很少或者是没有共同出现过，这样会导致模型学习不到它正确的分布。这个问题和直接拟合二阶交叉项的问题是一样的。为了解决这个问题我们专门设计了一个多层神经网络来学习这个参数值。这个神经网络的输入就是$v_i \odot v_j$，输出是一个浮点数表示权重，它的表达式为：

$$\begin{aligned} & a_{i j}^{\prime}=h^T \operatorname{ReLU}\left(W\left(v_i \odot v_j\right) x_i x_j+b\right) \\ & a_{i j}=\frac{\exp \left(a_{i j}^{\prime}\right)}{\sum_{(i, j) \in R_x} \exp \left(a_{i j}^{\prime}\right)} \end{aligned}$$

其中$a_{i j}^{\prime}$的表达式是一个多层神经网络，$a_{i j}$是$a_{i j}^{\prime}$经过softmax函数运算之后的结果，这也是normalized的一种常规方法。attention网络的输出结果是一个k维度的向量，它最后会把所有的特征交叉的结果加权压缩到一起。最后，我们可以写出整个AFM的表达式：

$$\hat{y}_{A F M}(x)=w_0+\sum_{i=1}^n w_i x_i+p^T \sum_{i=1}^n \sum_{j=i+1}^n a_{i j}\left(v_i \odot v_j\right) x_i x_j$$

Learning

AFM相比FM直接在数据表达能力上进行了提升，因此它除了可以使用在一系列预测问题当中也可以使用在其他场景下。比如回归、分类和排序。问题的目标不同，使用的损失函数也不一样。比如对于回归问题，我们一般使用均方差，二分类问题我们则使用交叉熵。在这篇paper当中我们聚焦在回归问题上，并且使用均方差作为模型优化目标。

为了使得优化目标最优，我们使用随机梯度下降算法（SGD）来进行参数的训练。SGD是机器学习当中广泛使用的优化方法之一，也被像是TensorFlow、Pytorch等深度学习框架所支持，因此就不过多赘述了。

预防过拟合

过拟合是深度学习模型当中经常出现的问题，FM模型就经常遇到过拟合的问题，所以我们常常会引入$L_2$正则项来预防FM模型的过拟合。由于AFM对于数据的刻画能力比FM更强，因此AFM也比FM更容易陷入过拟合。这里我们引入dropout和$L_2$正则来解决过拟合问题。

dropout方法经常使用在图像相关的模型当中，在训练过程当中，每次会随机让神经网络当中的一部分节点失效。从而逼迫网络更加专注在一些泛化能力更强的信息上，而不是被少数特殊点影响了全局。对于AFM模型来说，如果所有交叉特征都被用上，神经元很容易学到这些交叉特征之间的关系，因此而陷入过拟合。另外当测试的时候，dropout是关闭的，所以测试的时候模型可以更好地发挥出它的性能。

虽然paper当中有这么一段，但是dropout一般在推荐领域很少使用，因为推荐领域的特征不像图像那么密集，很多都是空值。所以使用dropout不是一定可以带来提升或者是避免过拟合的，这里的说法有一点想当然。

除了dropout之外，我们同样在Attention网络当中引入了$L_2$正则，所以最终的Loss可以写成：

$$L=\sum_{x \in \tau}\left(\hat{y}_{A F M}-y(x)\right)^2+\lambda\|W\|^2$$

这里的$\tau$表示的训练集，$\lambda$表示$L_2$正则的参数。

FNN

首先我们来介绍一下FNN，FNN的全称是Factorisation-machi supported Neural Network，即FM支撑的神经网络。其实这个名字当中信息量很大，我们来做个简单的词法分析，这个短语的主语是神经网络，FM支撑的是一个修饰的定语。也就是说这个模型的本质是神经网络，FM只是这个神经网络的一个特性。

而如果回顾一下FFM以及AFM，你会发现这两个模型的主体还是FM，神经网络是FM的修饰。这里的一个潜在的主语的变化其实是有隐藏信息的，隐藏信息就是学界对于模型的认知正在逐渐变化，正从FM为主体悄然转化成神经网络为主体。这个悄然的变化说明了一个关键信息，以后推荐系统的相关模型，神经网络才是大头。

了解完了这个潜在台词之后，我们再来看看FNN的网络结构。其实FNN的网络结构非常简单，就是FM与神经网络的一个串联。通过FM部分将特征转化成Embedding，之后全部拼接到一起之后，放入MLP（多层感知机）当中做训练。大家参考一下下图很容易就能搞明白。

PNN

PNN和FNN类似它唯一的区别就是MLP的输入不仅仅是特征的Embedding，还加上了Embedding product的结果。它的模型结构是这样的：

我们关注一下中间的Product Layer，这一层分成了左右两个部分，左边的部分就是特征Embedding，右边的部分是Embedding的两两product的结果，也就是特征之间两两内积的结果。而向量之间product的操作也有好几种，既可以内积也可以外积。但不管是内积还是外积都有一个问题，就是它的数量太多了。对于N维特征的模型来说，它的两两交叉一共有$N(N-1)$种，这是一个非常庞大的数字。

DeepFM

DeepFM: A Factorization-Machine based Neural Network for CTR Prediction，翻译过来就是DeepFM：一个基于深度神经网络的FM模型。这篇paper的作者来自哈工大和华为，不得不说在人工智能领域的很多论文都是国产的，作为从业者还是非常欣喜能看到这点的。通过名字我们也能看得出来，今天的这篇paper本质上其实是FM模型的一个进阶或者说是优化版本。

摘要

对于CTR预估的模型来说，一个很重要的点就是学习用户行为对应的特征背后的潜在联系。虽然目前在这个领域已经取得了一些进展（截止2017年），但是目前的做法要么在低维或者高维的特征上存在很大的偏差，要么需要大量的专家级的特征工程。

在本篇paper当中，我们设计了一种新的模型DeepFM，从而找到了一种可能性，可以同时提升低维和高维的特征。它结合了FM和神经网络模型的长处，和Google最新的Wide & Deep模型的做法相比，取得了更大的进步，并且还免去了特征工程的部分。

摘要里面内容不多，主要是拉踩了一下同行。

简介

对推荐场景来说，CTR是最关键的指标，除了广告系统会按照CTR x bid来进行排序之外，推荐系统一般都会严格地按照预估的CTR进行排序。所以这其中的关键问题就是准确地预估CTR。

为了方便大家的理解，简单介绍一下目前常规的做法。一般来说常规的推荐系统当中的特征分为四个部分，第一个部分是用户特征，是关于用户的一些信息。比如是男是女，是否是高收入群体，是否是高消费群体，成为平台的用户多久了，偏好平台当中什么类目的商品等等。第二个部分是商品特征，就是关于item的一些信息，比如价格、类目、折扣、评价等等。第三个部分是上下文特征，比如当前的时间，是早上还是晚上，比如item展示的位置等等。最后一个部分是用户实时的行为，比如用户在浏览这个商品之前还看过哪些其他的商品，他登陆平台多久了，等等。

显然用户是否会点击某一个item是由以上这四个部分的信息共同作用的，比如给一个高富帅推兰博基尼或者是百达翡丽就是有吸引力的，给一个连听都没听说过的屌丝推同样的内容显然就屁用没有。也就是说商品的特征和用户的特征之间是存在逻辑上的关联的，我们一般称为特征的交叉。

这些交叉信息往往是隐式的，也就是我们不能直接描述和形容出来的。举个简单的例子，可能并不是所有富人都喜欢奢侈品，有些可能就喜欢电子消费品，还有些可能喜欢服装或者是旅行。人的喜好是很复杂的，我们很难用固定的规则去描述。所以这就需要模型能有这样的能力去学习这些特征之间的潜在联系，对这些潜在交叉信息把握越好的模型，一般也都拥有越好的效果。

比如我们分析了主流的app store市场之后发现，在饭点的时候，用户经常会下载外卖类的app，这说明了app的类别和时间之间存在交叉关系。再比如我们发现年轻的男生往往喜欢设计类游戏，这说明了app的类别与用户的性别之间也存在交叉关系。像是这样的交叉信息还有很多，从Wide & Deep模型的经验当中我们可以学到考虑低维和高维交叉特征之后，模型的效果会更好。

这里面的一个关键挑战是如何高效地对特征之间的交叉信息进行建模，其中的一些比较容易理解，也比较容易做出特征来，然而大部分的交叉信息是隐式的，难以直观理解的，比如啤酒和尿布的例子就是一个，只有大数据挖掘才能发现。即使是直观上容易理解的部分，由于涉及的数量太大，也不可能通过手工来全部处理。

之后paper当中拉踩了一下同行，首先说明了单纯的CNN以及RNN效果不好，这个比较容易想明白，RNN主要应用场景是序列场景，比如文本、音频等，用在CTR预估上并不合适。CNN也是一样，主要应用在图片等高维度的数据当中，也不太适合推荐场景。

然后还比较了一下同年发表的其他三篇论文，FNN、PNN以及Wide & Deep。也是一些常规套话，没有太多的分析，比如在低维高维特征的交叉上表现不足啦，比如需要过多的特征工程啦等等。其中Wide & Deep我们之前写文章剖析过了，FNN和PNN大家感兴趣可以去读一下paper，在业内用的不多，应该是效果不太理想。经过了一番比较之后提出了本文的观点，我们可以设计出一种效果更好并且会自动学习特征之间交叉信息的模型。

方案

我们假设训练集当中一共有n条样本，每一条样本可以写成$(\chi, y)$。其中的$\chi$是一个m个field组成的向量，包含了用户和item组成的特征。$y \in\{0,1\}$，y=0表示用户没有点击，相反，y=1表示用户点击。

我们再来看样本的特征，这m维特征可以看成两部分组成，第一部分是类别特征，比如性别、地理位置、收入情况等等。第二种是连续性特征，比如平均花费、平均停留时间等等。类别特征（categorical feature）一般被表示成一个one-hot之后的向量，而一个连续特征，一般就是表示它自己，当然也可以离散化成one-hot向量。

我们把这些特征全部处理完之后，整个向量会转化成$x=\left[x_{\text {field }_1}, x_{\text {field }_2}, \cdots, x_{\text {field }_m}\right]$，这里的每一个field和$\chi$向量一一对应。由于这当中做了一些离散化的处理，会使得x向量变得非常稀疏。所以我们要做的就是在这样特征比较稀疏的样本上建立一个CTR预测模型。

DeepFM

我们希望能够设计模型能够更好地学习低维和高维特征之间的交互，基于这点，我们在深度模型的基础上结合了FM，推出了DeepFM模型。它的整体结构如下图：

这张图看起来可能会有点乱，我们可以先忽略一些局部的细节，先从整体上把握。这个模型可以分成两个部分，分别是FM部分以及Deep部分。这两个部分的输入是一样的，并没有像Wide & Deep模型那样做区分。

其实这个模型还是比较好理解的，神经网络也就是Deep的部分用来训练这些特征的一维的关联以及联系，而FM模型会通过隐藏向量V的形式来计算特征之间的二维交叉的信息。最后一维和二维的信息汇总到一起，进入sigmoid层，获得最终的结果。

用公式来表达的话，大概是这样：

$$\hat{y}=\operatorname{sigmoid}\left(y_{F M}+y_{D N N}\right)$$

FM部分

FM部分其实就是因子分解机，我们在之前的文章当中曾经专门剖析过。FM会考虑所有特征之间两两交叉的情况，相当于人为对左右特征做了交叉。但是由于n个特征交叉的组合是$n^2$这个量级，所以FM设计了一种新的方案，对于每一个特征i训练一个向量$V_i$，当i和j两个特征交叉的时候，通过$V_i \cdot V_j$来计算两个特征交叉之后的权重。这样大大降低了计算的复杂度。

这当中涉及一些公式的推导和计算，我们在之前的文章当中已经详细推导过了，这里就不多赘述了。

最终我们可以得到这部分的公式：

$$y_{F M}=\langle w, x\rangle+\sum_{i=1}^d \sum_{j=i+1}^d<V_i, V_j> x_i \cdot x_j$$

Deep部分

Deep部分就是经典的前馈网络，用来学习特征之间的高维交叉。

图3展示的就是模型当中Deep这个部分，从图中我们可以看到，所有的特征都会被转化成embedding向量作为Deep部分的输入。CTR预估的模型和图片以及音频处理的模型有一个很大的不同，就是它的维度会更大，并且特征会非常稀疏，还伴有类别连续、混合、聚合的特点。在这种情况下，使用embedding向量来把原始特征当中的信息压缩到低维的向量就是一种比较好的做法了，这样模型的泛化能力会更强，要比全是01组成的multi-hot输入好得多。

这张图展示了这个部分局部的结构，我们可以看到所有特征转成的embedding向量拥有相同的维度k。并且和FM模型当中的维度也是一样的，并且这个embedding的初始化也是借用FM当中的二维矩阵V来实现的。我们都知道V是一个d x k的二维矩阵，而模型原始输入是一个d维的01向量，那么和V相乘了之后，自然就转化成了d x k的embedding了。

这里要注意的一点是，在一些其他DNN做CTR预估的论文当中，会使用预训练的FM模型来进行Deep部分的向量初始化。但这里的做法略有不同，它不是使用训练好的FM来进行初始化，而是和FM模型的部分共享同样的V。这样做会有两个非常重要的好处：

1. 它可以同时学习到低维以及高维的特征交叉信息，预训练的FM来进行向量初始化得到的embedding当中可能只包含了二维交叉的信息。
2. 这样可以避免像是Wide & Deep那样多余的特征工程。

从我了解到的实际情况来看，虽然DeepFM已经是4年前的提出的模型了，但是至今仍然还有非常多的公司还在使用它。所以如果有兴趣从事推荐领域的研究和工作的话，对这个模型的了解也是必不可少的。