目录

1.FM算法产生背景

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

下面所有的假设都是建立在稀疏数据的基础上，举个例子，根据用户的评分历史预测用户对某部电影的打分，这里的每一行对应一个样本，Feature vector x表示特征，Targer y表示预测结果。从下图可以看出，这是一个稀疏特征的例子，后面的相关内容会以此为例子进行说明。

特征中的前四列表示用户u（one-hot编码，稀疏），接着五列表示电影i（ont-hot编码，稀疏），再接下去五列表示用户u对电影i的打分（归一化特征），紧接着一列表示时间（连续特征），最后五列表示用户u对电影i打分前评价过的最近一部电影（one-hot编码，稀疏）

2.FM算法模型

二、FM算法模型
1、模型目标函数
二元交叉的FM（2-way FM）目标函数如下：

其中，w是输入特征的参数，<vi,vj>是输入特征i,j间的交叉参数，v是k维向量。

前面两个就是我们熟知的线性模型，后面一个就是我们需要学习的交叉组合特征，正是FM区别与线性模型的地方。

为什么要通过向量v的学习方式而不是简单的wij参数呢？

这是因为在稀疏条件下，这样的表示方法打破了特征的独立性，能够更好地挖掘特征之间的相关性。以上述电影为例，我们要估计用户A和电影ST的关系w(A&ST)以更好地预测y，如果是简单地考虑特征之间的共现情况来估计w(A&ST)，从已有的训练样本来看，这两者并没有共现，因此学习出来的w(A&ST)=0。而实际上，A和ST应该是存在某种联系的，从用户角度来看，A和B都看过SW，而B还看过ST，说明A也可能喜欢ST，说明A很有可能也喜欢ST。而通过向量v来表示用户和电影，任意两两之间的交互都会影响v的更新，从前面举的例子就可以看过，A和B看过SW，这样的交互关系就会导致v(ST)的学习更新，因此通过向量v的学习方式能够更好的挖掘特征间的相互关系，尤其在稀疏条件下。

2、模型的计算复杂度
可能有人会问，这样两两交叉的复杂度应该O(k*n^2)吧，其实，通过数学公式的巧妙转化一下，就可以变成O(kn)了。转化公式如下所示，其实就是利用了$2xy=(x+y{)}^2-x^2-y^2$的思路。

3、模型的应用
FM可以应用于很多预测任务，比如回归、分类、排序等等。

1.回归Regression：y^(x)直接作为预测值，损失函数可以采用least square error；

2.二值分类Binary Classification：y^(x)需转化为二值标签，如0,1。损失函数可以采用hinge loss或logit loss；

3.排序Rank：x可能需要转化为pair-wise的形式如(X^a,X^b)，损失函数可以采用pairwise loss

4、模型的学习方法
前面提到FM目标函数可以在线性时间内完成，那么对于大多数的损失函数而言，FM里面的参数w和v更新通过随机梯度下降SGD的方法同样可以在线性时间内完成，比如logit loss，hinge loss，square loss，模型参数的梯度计算如下：

这部分求和跟样本i是独立的，因此可以预先计算好。

5、模型延伸：多元交叉
前面提到到都是二元交叉，其实可以延伸到多元交叉，目标函数如下：（看起来复杂度好像很高，其实也是可以在线性时间内完成的）

6、总结
前面简单地介绍了FM模型，总的来说，FM通过向量交叉学习的方式来挖掘特征之间的相关性，有以下两点好处：

1.在高度稀疏的条件下能够更好地挖掘数据特征间的相关性，尤其是对于在训练样本中没出现的交叉数据；

2.FM在计算目标函数和在随机梯度下降做优化学习时都可以在线性时间内完成。

3.FM算法VS其他算法

1、FM 对比 SVM
1）SVM
SVM是大家熟知的支持向量机模型，其模型原理在这里就不详述了。

SVM的线性模型函数表示为：

其非线性形式可以通过核映射kernel mapping的方式得到，如下所示：

其中多项式核表示为：

当d=2时为二次多项式，表示为：

多项式核映射后的模型函数表示为：

2）FM 对比 SVM
看到上面的式子，是不是觉得跟FM特别像？SVM和FM的主要区别在于，SVM的二元特征交叉参数是独立的，如wij，而FM的二元特征交叉参数是两个k维的向量vi、vj，这样子的话，<vi,vj>和<vi,vk>就不是独立的，而是相互影响的。

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

此外，FM和SVM的区别还体现在：1）FM可以在原始形式下进行优化学习，而基于kernel的非线性SVM通常需要在对偶形式下进行；2）FM的模型预测是与训练样本独立，而SVM则与部分训练样本有关，即支持向量。

2、FM 对比 其他分解模型Fac torization Model
这部分不详述，其他分解模型包括Matrix factorization (MF)、SVD++、PITF for Tag Recommendation、Factorized Personalized Markov Chains (FPMC)，这些模型都只在特定场景下使用，输入形式也比较单一（比如MF只适用于categorical variables），而FM通过对输入特征进行转换，同样可可以实现以上模型的功能，而且FM的输入可以是任意实数域的数据，因此FM是一个更为泛化和通用的模型。详细内容参考：https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

4.推荐算法总结

目前为止，我们常推荐算法有好多种，比较常见的有协同过滤（Collaborative Filtering Recommendations）这个在Mahout里的ItemCF和UserCF比较常用，还有一种比较新的运行在Spark上的交替性最小二乘ALS也是一种协同过滤的算法，但是其它的推荐算法也有很多，在日常中也用的比较多，就做个总结吧。

1、基于内容的推荐算法(Content Based Recommendation 简称CB)
这种推荐是从信息检索，和文本检索里来的，个人理解为是搜索引擎里的搜索排行。TD-IDF计算文章的词频和反文档频率计算出关键词在文档中的权值，最后构成某篇文章的特征向量。基于该文章的特征向量和其它文章的特征向量进行余弦相似度计算，从而返回最匹配相似的文章来给予推荐。

可以简单概括为: 抽取item的特征向量 -> 计算余弦相似度 -> 推荐

item可以是用户过去喜欢的电影，商品，问题等等。

基于内容的过滤创建了每个商品、用户的属性（或是组合）用来描述其本质。比如对于电影来说，可能包括演员、票房程度等。 用户属性信息可能包含地理信息、问卷调查的回答等。这些属性信息关联用户用户后即可达到匹配商品的目的。 当然基于内容的策略极有可能因为信息收集的不便而导致无法实施。

CB的优点：

1. 用户之间的独立性（User Independence）：既然每个用户的profile都是依据他本身对item的喜好获得的，自然就与他人的行为无关。而CF刚好相反，CF需要利用很多其他人的数据。CB的这种用户独立性带来的一个显著好处是别人不管对item如何作弊（比如利用多个账号把某个产品的排名刷上去）都不会影响到自己。

2. 好的可解释性（Transparency）：如果需要向用户解释为什么推荐了这些产品给他，你只要告诉他这些产品有某某属性，这些属性跟你的品味很匹配等等。

3. 新的item可以立刻得到推荐（New Item Problem）：只要一个新item加进item库，它就马上可以被推荐，被推荐的机会和老的item是一致的。而CF对于新item就很无奈，只有当此新item被某些用户喜欢过（或打过分），它才可能被推荐给其他用户。所以，如果一个纯CF的推荐系统，新加进来的item就永远不会被推荐:( 。

CB的缺点：

1. item的特征抽取一般很难（Limited Content Analysis）：如果系统中的item是文档（如个性化阅读中），那么我们现在可以比较容易地使用信息检索里的方法来“比较精确地”抽取出item的特征。但很多情况下我们很难从item中抽取出准确刻画item的特征，比如电影推荐中item是电影，社会化网络推荐中item是人，这些item属性都不好抽。其实，几乎在所有实际情况中我们抽取的item特征都仅能代表item的一些方面，不可能代表item的所有方面。这样带来的一个问题就是可能从两个item抽取出来的特征完全相同，这种情况下CB就完全无法区分这两个item了。比如如果只能从电影里抽取出演员、导演，那么两部有相同演员和导演的电影对于CB来说就完全不可区分了。

2. 无法挖掘出用户的潜在兴趣（Over-specialization）：既然CB的推荐只依赖于用户过去对某些item的喜好，它产生的推荐也都会和用户过去喜欢的item相似。如果一个人以前只看与推荐有关的文章，那CB只会给他推荐更多与推荐相关的文章，它不会知道用户可能还喜欢数码。

3. 无法为新用户产生推荐（New User Problem）：新用户没有喜好历史，自然无法获得他的profile，所以也就无法为他产生推荐了。当然，这个问题CF也有。

2、基于协同过滤的推荐算法（Collaborative Filtering Recommendations）
基于协同过滤的推荐，可以理解为基于用户行为的推荐。依赖于用户过去的行为的协同过滤，行为可以是过往的交易行为和商品评分，这种方式不需要显性的属性信息。协同过滤通过分析用户和商品的内在关系来识别新的 user-item 关系。

协同过滤领域主要的两种方式是最近邻（neighborhood）方法和潜在因子（latent factor）模型。最近邻方法主要集中在 item 的关系或者是 user 的关系，是比较基础的过滤引擎。而潜在因子模型并不是选取所有的关系，而是通过矩阵分解的技术将共现矩阵的分解，比如提取20-100个因子，来表示原始矩阵信息（可以对比上面提到的音乐基因，只不过潜在因子模型是通过计算机化的实现）。

最邻近：

基于用户的协同过滤算法: 基于一个这样的假设“跟你喜好相似的人喜欢的东西你也很有可能喜欢。”所以基于用户的协同过滤主要的任务就是找出用户的最近邻居，从而根据最近邻 居的喜好做出未知项的评分预测。

item based CF 基于物品相似的协同过滤。

user based CF 基于用户相似的协同过滤。

潜在引子模型：

SVD奇异值分解矩阵

ALS交替最小二乘

总结为： 用户评分 -> 计算最邻近 -> 推荐

3、算法对比

各种推荐方法都有其各自的优点和缺点，见表1。

4、 Mahout里的推荐算法

5、总结
没有最那一种算法能解决所有问题，混合算法有效结合每个算法的利弊才能达到最好的效果。

一个比较成功的内容过滤是 pandora.com 的音乐基因项目，一个训练有素的音乐分析师会对每首歌里几百个独立的特征进行打分。这些得分帮助pandora推荐歌曲。还有一种基于内容的过滤是基于用户人口统计特征的推荐，先根据人口统计学特征将用户分成若干个先验的类。对后来的任意一个用户，首先找到他的聚类，然后给他推荐这个聚类里的其他用户喜欢的物品。这种方法的虽然推荐的粒度太粗，但可以有效解决注册用户的冷启动(Cold Start)的问题。