本文主要包含以下内容：
1.背景
2.矩阵分解类算法
2.1 协同过滤 CF
2.2 矩阵分解 MF
2.3 逻辑回归 LR
2.4 因子分解机FM
2.5 组合模型
3.FM深入介绍
3.1 FM特点
3.2 FM用于召回
3.3 FM用于精排
4.Spark FM实现
5.TF FM 实现
6.参考
1.背景
在互联网的驱动下，推荐系统的发展可谓是一日千里，而矩阵分解算法在其中则扮演了一个重要的角色，本文主要介绍一下FM算法在召回和排序中的使用。
2.矩阵分解类算法
在介绍FM算法之前，大概介绍一下CF、MF、LR，因为这些都蕴含着隐藏的关系。
2.1 协同过滤 CF
协同过滤（Collaborative Filtering，CF）是推荐算法的鼻祖，至今，在各大互联网公司中，CF都扮演着不可或缺的角色。
协同过滤是根据大家的反馈、评论和意见一起对海量的信息进行过滤，从中筛选出目标用户可能感兴趣的信息的推荐过程。大致过程是，将用户与商品放入一个共现矩阵中，矩阵中的值为某用户对某件商品的点击、评价或者购买行为的度量。我们可以将用户感兴趣的所有商品向量化，记为代表该用户的向量，进而可以计算用户间的相似度。于是，可以将与某待推荐用户相似的用户所感兴趣的商品推荐给该用户。类似的，可以将对商品感兴趣的所有用户向量化，记为代表该商品的向量，进而计算物品之间的相似度。在实际的计算过程中，还应该对爆品、高销品与其他商品的相似度进行一定程度上的衰减。相似度的计算也应该进行归一化，排除数量级的影响。
协同过滤的优点是没有显式的学习过程、可解释性强、简单、速度快。其缺点也很明显：协同过滤只考虑了用户和物品的id信息，而无法将用户的属性、物品的属性、上下文考虑在内。并且没有挖掘用户和物品之间的隐含关系，对于一个没有购买过任何商品的新用户，协同过滤模型就不知道推荐什么商品了。协同过滤模型的泛化性差、推荐结果的头部效应明显、处理稀疏向量的能力弱（共现矩阵是非常稀疏的）。
2.2 矩阵分解 MF
针对协同过滤算法的头部效应较明显、泛化能力较弱的问题，矩阵分解算法被提出。矩阵分解在协同过滤算法中共现矩阵的基础上，加入了隐向量的概念，加强了模型处理稀疏矩阵的能力，针对性地解决了协同过滤存在的主要问题。大致过程是，将共现矩阵通过“特征值分解”、“奇异值分解”或“梯度下降”进行矩阵分解，得到用户矩阵和物品矩阵。共现矩阵的维度很高但很稀疏，而分解得到的用户矩阵和物品矩阵的维度会降低（取决于隐向量的维度）但很稠密。于是可以通过用户矩阵的隐向量之间的相似度来刻画用户之间的相似度，物品矩阵的隐向量之间的相似度来刻画物品之间的相似度，用户隐向量和物品隐向量之间的内积来刻画用户与物品之间的匹配程度。
矩阵分解的优点是，由于隐向量的存在，使任意的用户和物品之间都可以得到预测分数。隐向量的生成过程是对共现矩阵进行全局的拟合，有较强的泛化能力。空间复杂度降低，有更好的灵活性和拓展性。矩阵分解仍然不方便加入用户、物品和上下文相关的特征，使得矩阵分解不能利用很多有效信息的机会。
2.3 逻辑回归 LR
虽然CF、MF能够发挥不错的效果，但是其利用的特征还是比较少，因此可以借助线性模型进行捕获。线性模型分为：
其中在工业界应用比较成功的就是广义线性模型中的逻辑回归（Logistic Regression，LR）。
逻辑回归是我们很熟悉的一个分类模型。应用到推荐上，逻辑回归能够综合利用用户、物品、上下文等多种不同的特征，生成“较全面”的推荐结果。逻辑回归将推荐问题看成了分类问题，通过预测正样本的概率对物品进行排序。直观地讲，逻辑回归模型的数学形式是各特征的加权和，再施以 sigmoid 函数进行激活，映射到0-1之间。这是非常符合人类预估过程的直觉认知，使用各特征的加权和是为了综合不同特征对结果的影响，而不同特征的重要程度不一致，所以为不同特征指定不同的权重，代表不同特征的重要程度。最后通过 sigmoid 函数，映射为概率。逻辑回归易于并行化、模型简单、训练开销小。
逻辑回归的缺点是表达能力不强，无法进行特征交叉、特征筛选等一系列较为高级的操作，会不可避免地造成信息的损失。
其推导过程如下：
2.4 因子分解机FM
在利用单一特征而非交叉特征进行判断的情况下，有时不仅仅是信息损失的问题，甚至会得出错误的结论。FM 在 LR 的常数项、一阶项的基础上新增了特征之间交叉的二阶项，增加了利用交叉特征的能力。FM 所学习的参数除了偏置和各特征的权重之外，还有各特征对应的隐向量。本质上，FM 引入隐向量的做法，与矩阵分解用隐向量代表用户和物品的做法异曲同工。可以说，FM 是将矩阵分解隐向量的思想进行了进一步扩展，从单纯的用户、物品隐向量扩展到了所有特征上。通过用户特征的隐向量和物品特征的隐向量可以计算用户之间的相似度、物品之间的相似度和用户与物品的匹配度。这可以实现u2u, i2i, u2i, i2u等方式的召回。
FM算法利用了二阶的交叉特征，提升了模型的泛化能力。但无法进行更高阶数的特征交叉，因为组合爆炸问题的限制，三阶FM无论是权重数量还是训练复杂度都过高，难以在实际工程中实现。组合模型在一定程度上解决了高阶特征交叉的问题。
与FM相关联的另一个算法是FFM算法，FFM（Field-aware Factorization Machine）最初的概念来自Yu-Chin Juan（阮毓钦，毕业于中国台湾大学，现在美国Criteo工作）与其比赛队员，是他们借鉴了来自Michael Jahrer的论文中的field概念提出了FM的升级版模型。通过引入field的概念，FFM把相同性质的特征归于同一个field。以上面的广告分类为例，“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”这三个特征都是代表日期的，可以放到同一个field中。同理，商品的末级品类编码生成了550个特征，这550个特征都是说明商品所属的品类，因此它们也可以放到同一个field中。简单来说，同一个categorical特征经过One-Hot编码生成的数值特征都可以放到同一个field，包括用户性别、职业、品类偏好等。在FFM中，每一维特征，针对其它特征的每一种field ，都会学习一个隐向量 。因此，隐向量不仅与特征相关，也与field相关。也就是说，“Day=26/11/15”这个特征与“Country”特征和“Ad_type”特征进行关联的时候使用不同的隐向量，这与“Country”和“Ad_type”的内在差异相符，也是FFM中“field-aware”的由来。
关于FM、FFM原理的文章可以参考美团的这一篇，写的相当不错：深入FFM原理与实战
假设样本的 个特征属于 个field，那么FFM的二次项有 个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看作FFM的特例，是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性，可以导出其模型方程。
其中， 是第 个特征所属的field。如果隐向量的长度为 ，那么FFM的二次参数有 个，远多于FM模型的 个。此外，由于隐向量与field相关，FFM二次项并不能够化简，其预测复杂度是 。
2.5 组合模型
GBDT+LR是特征工程化的开端。其利用GBDT自动进行特征筛选和组合，进而形成新的离散特征向量，再把该特征向量当做LR模型的输入。GBDT每个树生成的过程是一棵标准的回归树生成过程，因此回归树中每个节点的分裂是一个自然的特征选择的过程，而多层节点的结构则是对特征进行了有效的自动组合。GBDT+LR的提出，意味着特征工程可以交由一个独立的模型来完成，实现了真正的端到端的训练。
LS-PLM（大规模分段线性模型）的思想是在逻辑回归的基础上加上了聚类的思想。首先对全量样本进行聚类，再对每个分类施以逻辑回归模型进行学习。这和我们项目中先对用户进行聚类，然后对每个聚类的用户群的购买特征进行学习的思想不谋而合。不同的是，我们的方法是采用硬聚类，每个用户仅属于其中一个用户群，k-means为非概率模型。而LS-PLM是多分类，是概率模型，每个用户均有一定的概率属于每个用户群。对某用户求各用户群的逻辑回归预测结果的加权平均，即为最后的预测结果。LS-PLM为阿里巴巴在传统推荐系统时代的主流推荐模型，再往后就是深度学习推荐模型的天下了。
3.FM深入介绍
由于本文主要介绍的是FM模型，所以这里对其进行深入的介绍，下面部分内容结合 【FM：推荐算法中的瑞士军刀】进行修改和理解。
3.1 FM特点
功能齐全
推荐算法有三个应用领域：召回、粗排、精排。FM 几乎是唯一一个能实现三个领域全覆盖的多面手。特别是FM用做召回时，表现更加优秀。FM召回的主流作法，是用生成的user embedding直接查找最相近的item embedding。除此之外，利用已经生成了的user/item embedding，还有更多的玩法，比如，查找相似item的“看了又看”功能、用户聚类推荐功能、根据item找潜在用户的Push功能。而且，FM对新用户、新物料也非常友好。实现一个FM召回，就能够完成u2i, i2i, i2u, u2u2i四种召回方式，还包括对新用户、新物料的冷启动。
FM能够将模型的最终打分拆解到每个特征和特征组合上，从而能够让我们分析出到底是哪些因素提高或拉低了模型的打分。最重要的是，区别于GBDT那种只能提供特征的全局重要性，FM提供的重要性是针对某一个、某一群样本的，使我们能够做更加精细化的特征分析。
性能优异
推荐系统的两大永恒主题，“记忆”和“拓展”，FM 也能实现全覆盖。
FM存在一阶项，实际就是LR，能够记忆高频、常见模式。Embedding是提升推荐算法“扩展性”的法宝。FM通过feature embedding，能够自动挖掘低频、长尾模式。在这一点上，基于embedding的二阶交叉，并不比DNN的高阶交叉，逊色多少。
便于上线
FM排序，虽然理论上需要所有特征进行二阶交叉，但是通过公式化简，可以在 O(n)的时间复杂度下完成。n是样本中非零的特征数目，由于推荐系统中的特征非常稀疏，所以预测速度是非常快的。
由于候选集巨大，召回对于实时性的要求更高。很多高级的召回算法（e.g., 基于GNN的召回算法），由于计算复杂，无法线上实时生成user embedding，只能退而离线生成user embedding，不仅降低了用户覆盖率，而且对于用户实时兴趣的捕捉大打折扣。FM召回，只需要把一系列的feature embedding相加，就可以对任何用户在线生成最新的user embedding，从而可以基于用户最新的兴趣，从千万量级候选item中完成实时召回。
3.2 FM用于召回
1. 样本
还是拿“曝光点击”的item做正样本，同时需要排除误点击、自动播放等脏数据。对于负样本的选择，基本原则之一就是，不能只拿曝光未点击做负样本。大多数负样本，应该通过在item库中随机采样的方式得到。只有这样，训练时的数据分布才最接近预测时的数据分布。
同时应给打压热门的item。降低热门item成为正样本的可能性，因此，item越热门，其成为正样本的概率就应该越低。在随机采样负样本时，一方面需要尽可能广泛地覆盖所有候选item，另一方面又需要尽量集中于高热item。
这个做法是模型训练的trick，具有普适性
2. 特征
接下来会说到，线上部署FM召回模型时，需要周期地在线下计算好几百万候选item的embedding，然后灌入FAISS建立索引，等待user embedding来检索。因为user embedding是在线生成，而item embedding是离线生成，二者分离造成我们在训练、预测时，不能使用任何user与候选item之间的统计交叉特征。这一点与FM精排视“统计交叉特征”为最重要特征，有着显著不同。
DSMM、Youtube DNN 等模型用于召回其实是一样的道理
3. 训练模型
由于召回中的负样本大部分是通过随机采样得到的，它们的'negative label'是含有噪声的。在这种情况下，再照搬精排使用binary cross-entropy loss追求“预估值”与“label”之间的“绝对准确性”，就有点强人所难了。所以，召回算法往往采用Pairwise LearningToRank（LTR），建模排序的“相对准确性”。即模型优化的目的，不是为了拟合'user与负样本item的匹配程度越低越好'，而是追求“user与正样本item的匹配程度，要远远高于，user与负样本item的匹配程度”。
4. 线上服务
传统u2i召回：将FM公式变形为user隐向量和item隐向量相乘的形式：对于某个用户
除了以上最常用的u2i召回，在我们得到user embedding和item embedding之后，还有很多其他玩法
FM对新用户、新物料都非常友好。
- 对新用户，哪怕他是一个纯新用户，没有任何画像与交互历史，他至少有一个特征叫“IsNewUser=1”，也就能够生成user embedding，FM也能替他召回
- 对新物料，任何物料都能拿到其画像（e.g., 一二级分类、标签等），自然能够得到item embedding。我们可以专门建立一个FAISS库，里面的item都是刚入库的新item。用户请求到来时，除了在常规的、由已经有一些点击量的item faiss库里召回之外，还在这个只由新item组成的faiss库里召回。这样既能够将新item分发出去，又保证分发是高度个性化的，提高流量的利用率。
- 拿用户最近一次点击的item embedding，在item faiss库中检索相似item，推荐给用户，实现“看了又看”、“猜你喜欢”等功能
- 拿当前user embedding，在user faiss库中检索相似user，把这些相似user消费过的item推荐给当前user，类似User CF，效果也非常好
- 可以拿item embedding，在user faiss库中检索可能对它感兴趣的user，把item给这些用户Push出去，达到提高用户黏性、减少用户流失的目的。
5. 得分
FM允许我们将最终预测得分，拆解到各 feature 和 feature 组合上，从而能够提供“局部特征重要性”。但是，推荐场景下，feature空间有上亿维，而且高度稀疏，拆解到feature与feature组合级别，计算量太大，而且即便能够拆解成功，拆解后的信息也太琐碎，让人无从分析。因此，更合理的解决方案是拆解到field级别，因为field最多几百个，算上field组合也不过几万个，无论是计算规模，还是分析规模，还是可以接受的。（有些同学对field的概念不太熟悉，这里做一下简单说明。比如“一级分类”算是field，而“军事”、“历史”这样的具体的分类值是这个field下的feature。）
拆解方法也很简单：针对每一个样本，将这个样本的feature embedding按所属field分组，同一field下所有feature embedding相加得到field embedding，然后两两field embedding做点积，这样就将样本得分拆解到了field和field pair的维度上。
3.3 FM用于精排
1. 样本
曝光点击做正样本，曝光未点击做负样本。正样本一般会卡一个停留时长，去除用户误点击、自动播放之类的数据。负样本是真正曝光给用户，然后被用户忽略的。
2. 特征
ID特征才是推荐系统中的一等公民，在离线训练、线上服务时都具备一系列优势，所以FM中所有特征都ID化。类别型特征，比如UserId、ItemId、一二级分类、标签等，天然就是ID型特征。而实数型特征，比如Item过去的点击率、用户过去24小时的点击数之类，需要通过分桶转化为ID类特征。
3. 训练模型
推导过程
4. 线上服务
采用fm公式进行打分。由于线上打分时，是将某个用户与一批候选item，喂入ranker，因此那一个用户的特征只需要抽取、计算一遍，在给多个item打分时复用。
4.Spark FM实现
github上有个大神实现了一个FM的代码：https://github.com/zhengruifeng/spark-libFM
代码主要是封装了一个FM的类，然后分别实现了基于SGD和LBFGS的的算法。该代码是基于Spark2.10进行实现的，有兴趣的可以将其改为更高的版本（不过目前很多企业使用的都是spark 2.x的版本），主要有三个代码段：
FactorizationMachine中定义了FMModel类和对象，也定义了FMGradient、FMUpdater在FMWithSGD、FMWithLBFGS。
其中TestFM为：
object TestFM extends App {
override def main(args: Array[String]): Unit = {
val sc = new SparkContext(new SparkConf().setAppName('TESTFM').setMaster('local'))
val training = MLUtils.loadLibSVMFile(sc, 'data/sample_libsvm_data.txt').cache()
println(training.take(3).foreach(println))
val fm1 = FMWithSGD.train(training, task = 1, numIterations = 100, stepSize = 0.15, miniBatchFraction = 1.0, dim = (true, true, 4), regParam = (0, 0, 0), initStd = 0.1)
val fm2 = FMWithLBFGS.train(training, task = 1, numIterations = 20, numCorrections = 5, dim = (true, true, 4), regParam = (0, 0, 0), initStd = 0.1)
}
}
运行输出为：
(0.0,(692,[127,128,129,130,131,154,155,156,157,158,159,181,182,183,184,185,186,187,188,189,207,208,209,210,211,212,213,214,215,216,217,235,236,237,238,239,240,241,242,243,244,245,262,263,264,265,266,267,268,269,270,271,272,273,289,290,291,292,293,294,295,296,297,300,301,302,316,317,318,319,320,321,328,329,330,343,344,345,346,347,348,349,356,357,358,371,372,373,374,384,385,386,399,400,401,412,413,414,426,427,428,429,440,441,442,454,455,456,457,466,467,468,469,470,482,483,484,493,494,495,496,497,510,511,512,520,521,522,523,538,539,540,547,548,549,550,566,567,568,569,570,571,572,573,574,575,576,577,578,594,595,596,597,598,599,600,601,602,603,604,622,623,624,625,626,627,628,629,630,651,652,653,654,655,656,657],[51.0,159.0,253.0,159.0,50.0,48.0,238.0,252.0,252.0,252.0,237.0,54.0,227.0,253.0,252.0,239.0,233.0,252.0,57.0,6.0,10.0,60.0,224.0,252.0,253.0,252.0,202.0,84.0,252.0,253.0,122.0,163.0,252.0,252.0,252.0,253.0,252.0,252.0,96.0,189.0,253.0,167.0,51.0,238.0,253.0,253.0,190.0,114.0,253.0,228.0,47.0,79.0,255.0,168.0,48.0,238.0,252.0,252.0,179.0,12.0,75.0,121.0,21.0,253.0,243.0,50.0,38.0,165.0,253.0,233.0,208.0,84.0,253.0,252.0,165.0,7.0,178.0,252.0,240.0,71.0,19.0,28.0,253.0,252.0,195.0,57.0,252.0,252.0,63.0,253.0,252.0,195.0,198.0,253.0,190.0,255.0,253.0,196.0,76.0,246.0,252.0,112.0,253.0,252.0,148.0,85.0,252.0,230.0,25.0,7.0,135.0,253.0,186.0,12.0,85.0,252.0,223.0,7.0,131.0,252.0,225.0,71.0,85.0,252.0,145.0,48.0,165.0,252.0,173.0,86.0,253.0,225.0,114.0,238.0,253.0,162.0,85.0,252.0,249.0,146.0,48.0,29.0,85.0,178.0,225.0,253.0,223.0,167.0,56.0,85.0,252.0,252.0,252.0,229.0,215.0,252.0,252.0,252.0,196.0,130.0,28.0,199.0,252.0,252.0,253.0,252.0,252.0,233.0,145.0,25.0,128.0,252.0,253.0,252.0,141.0,37.0]))
具体的代码可以进行阅读和交流。
5.TF FM 实现
主要的代码是：
def FM(feature_columns):
# 定义模型的输入特征
features = build_input_features(feature_columns)
# 定义离散特征、连续特征、多值特征列
sparse_feature_columns = list(
filter(lambda x: isinstance(x, SparseFeat), feature_columns)) if feature_columns else []
dense_feature_columns = list(
filter(lambda x: isinstance(x, DenseFeat), feature_columns)) if feature_columns else []
sparse_varlen_feature_columns = list(
filter(lambda x: isinstance(x, VarLenSparseFeat), feature_columns)) if feature_columns else []
inputs_list = list(features.values())
# 构建 linear embedding_dict
linear_embedding_dict = build_linear_embedding_dict(feature_columns)
linear_sparse_embedding_list, linear_dense_value_list = input_from_feature_columns(features, feature_columns,linear_embedding_dict)
# 线性模型部分
linear_logit = get_linear_logit(linear_sparse_embedding_list, linear_dense_value_list)
# 构建 embedding_dict
cross_columns = sparse_feature_columns + sparse_varlen_feature_columns
embedding_dict = build_embedding_dict(cross_columns)
sparse_embedding_list, _ = input_from_feature_columns(features, cross_columns, embedding_dict)
# 将所有sparse的k维embedding拼接起来，得到 (n, k)的矩阵，其中n为特征数
concat_sparse_kd_embed = Concatenate(axis=1)(sparse_embedding_list)
# 交叉部分
fm_cross_logit = FMLayer()(concat_sparse_kd_embed)
final_logit = Add()([fm_cross_logit, linear_logit])
output = tf.keras.layers.Activation('sigmoid', name='fm_out')(final_logit)
model = Model(inputs=inputs_list, outputs=output)
return model
6.参考
- 推荐算法中的倚天剑: FM (tensorflow2实现)
