FM: 推荐算法中的瑞士军刀
前言
自从我上次在知乎回答了问题《机器学习中较为简单的算法有哪些？》，很多同学私信我询问我FM算法在推荐系统中的应用细节，索性今天就专门写一篇文章，仔细聊一聊FM这把“推荐算法中的瑞士军刀”。正文开始之前，我说几句题外话。
第一，谈谈本文的标题。机器学习算法中的瑞士军刀，可不是随便起的。以前Xgboost因为方便易用、功能广泛、性能优异，被誉为Kaggle比赛中的瑞士军刀。因为同样的优点，我将FM称作“推荐算法中的瑞士军刀”，其中有两个含意：
如果你身处大厂，周围训练、上线的资源都很充裕，需要在已经很优秀的业务指标上锦上添花，那么你肯定看不上FM这样的老古董，而是追求DNN、GNN这样的大杀器，而且将Attetion、Transformer之类的花哨结构，能加的都给它加上。 但是，既然是瑞士军刀，那么拿它与屠龙刀比威力，就不太公平了。有一日，你脱离了大平台，单独出来行走江湖。这个时候，你才发现，即便屠龙宝刀白送给你，你自己一个人也很难扛起来。适合于业务草创阶段的算法兵器，应该具备：（1）快速训练+上线；（2）尽量白盒，以便定位问题；（3）一专多能，减少开发、维护成本；（4）性能上也不算差。此时，你会发现，FM几乎是你唯一的选择。
第二，本文主要介绍FM应用于推荐系统中的一些实战经验，需要读者对FM有一定的基础。对FM还不太了解的同学，我推荐以下参考资料：
掌握FM原理，推荐读美团的博客《深入FFM原理与实践》。FFM的部分可以忽略，在我看来，FFM损失了FM的很多优点（比如，通过公式简化，将时间复杂度由减少为），更像是为了Kaggle专门训练的比赛型选手。这就好比，奥运会上的射击冠军，未必能够胜任当狙击手一样。 FM用于召回，推荐读张老师的《推荐系统召回模型之：全能的FM模型》。但是，需要注意的是，FM虽然是能够覆盖召回+排序的全能选手，但是对于不同业务，FM在样本选择、模型设计、上线部署的细节上，都有较大差异。这一点，张的文章没有涉及，而本文将为读者梳理之。 如果想亲手实践，可以尝试alphaFM。该项目只不过是作者八小时之外的课外作品，却被很多公司拿来投入线上实际生产环境，足见该项目性能之优异和作者功力之深厚，令人佩服。强烈建议不满足只当“调参侠”的同学，通读一遍alphaFM的源代码，一定收获满满。
接下来的文字中，我首先梳理一下FM的特点，再按照精排、召回、解释模型的顺序，介绍FM在各个业务中的技术细节，比如：如何无偏地收集样本、如何设计模型、如何部署上线。细心的读者可能注意到，这里面没有“粗排”的内容。我们尝试过粗排模型（并非FM，而是双塔+蒸馏），线上收益并不明显，所以在就里就不详细叙述了，感兴趣的同学可以参考阿里的论文《Privileged Features Distillation at Taobao Recommendations》。
FM的特点
功能齐全
众所周知，推荐算法有三个应用领域：召回、粗排、精排。推荐算法千千万，但是有的算法只能用于召回，有的算法只能用于排序（吐槽一下，有本“著名”的书《Deep learning for matching in search and Recommendation》，其中的很多算法，比如DIEN之类的，其计算复杂度只能用于排序，但是很多人在翻译的时候将matching翻译成召回，简直是开玩笑）。像FM这样实现三个领域全覆盖的多面手，目前为止，孤陋寡闻的我尚不知道有第二个。
特别是FM用做召回时，表现更加优秀。FM召回的主流作法，是用生成的user embedding直接查找最相近的item embedding。除此之外，利用已经生成了的user/item embedding，还有更多的玩法，比如，查找相似item的“看了又看”功能、用户聚类推荐功能、根据item找潜在用户的Push功能。而且，FM对新用户、新物料也非常友好。实现一个FM召回，就能够完成u2i, i2i, i2u, u2u2i四种召回方式，还包括对新用户、新物料的冷启动。性价比如此之高，即使在很多大厂，FM也是主力召回模型，果然是很香了。
另外，虽然DNN这样的屠龙刀，威力强大，但是有一个缺点，就是模型黑盒化比较严重，可解释性非常差。这方面，FM的优势就非常明显了。FM能够将模型的最终打分拆解到每个特征和特征组合上，从而能够让我们分析出到底是哪些因素提高或拉低了模型的打分。最重要的是，区别于GBDT那种只能提供特征的全局重要性，FM提供的重要性是针对某一个、某一群样本的，使我们能够做更加精细化的特征分析。
性能优异
对于推荐系统的两大永恒主题，“记忆”与“扩展”，FM也能实现全覆盖。
FM存在一阶项，实际就是LR，能够记忆高频、常见模式 如我在《无中生有：论推荐算法中的Embedding思想》所说，Embedding是提升推荐算法“扩展性”的法宝。FM通过feature embedding，能够自动挖掘低频、长尾模式。在这一点上，基于embedding的二阶交叉，并不比DNN的高阶交叉，逊色多少。
便于上线
现在DNN是推荐领域的宠儿，LR/FM/GBDT这样的传统机器学习算法，被打入冷宫，不招人待见。
DNN这样的屠龙刀，虽然性能优异，但是它有一个致命缺点，就是上线困难。训练的时候，各位调参侠，把各种酷炫的结构，什么attention, transformer, capsule，能加上的都给它加上，看着离线指标一路上涨，心里和脸上都乐开了花，却全然无视旁边的后端工程师恨得咬紧了牙根。模型越复杂，离线和线上指标未必就更好，但是线上的时间开销肯定会增加，超时严重的时候，你那离线指标完美的模型压根没有上线的机会。虽说，目前已经有TF Serving这样的线上serving框架，但是它也不是开箱即用的，也需要一系列的性能调优，才能满足线上的实时性要求。
所以，如果你身处一个小团队，后端工程人员的技术能力不强，DNN的线上实时预测，就会成为一个难题，这个时候，FM这样的传统机器学习算法，就凸显出其优势。
FM排序，虽然理论上需要所有特征进行二阶交叉，但是通过公式化简，可以在 O(n)的时间复杂度下完成。n是样本中非零的特征数目，由于推荐系统中的特征非常稀疏，所以预测速度是非常快的。 召回，由于候选集巨大，对于实时性的要求更高。很多高级的召回算法（e.g., 基于GNN的召回算法），由于计算复杂，无法线上实时生成user embedding，只能退而离线生成user embedding，不仅降低了用户覆盖率，而且对于用户实时兴趣的捕捉大打折扣。FM召回，只需要把一系列的feature embedding相加，就可以对任何用户在线生成最新的user embedding，从而可以基于用户最新的兴趣，从千万量级候选item中完成实时召回。
FM精排
样本
如果只做CTR预估，不涉及CVR这样的级联目标，精排样本的选择是比较清晰的，拿“曝光点击做正样本，曝光未点击做负样本”是业界的共识。
正样本，一般再卡一个停留时长，去除用户误点击、自动播放之类的脏数据 负样本，讲究“真负”，一定是真正曝光给用户、然后被用户忽略的。为此，还有所谓above click的作法，拿用户点击的item以上的未点击item做负样本。
特征
精排能够利用的特征是最丰富的，需要分为三大类
user类：用户长短期画像、点击/收藏/购买历史、......等 item类：物料画像、物料的后验指标（e.g., CTR、时长）、......等 交叉类特征：有的同学或许有疑问，不是说FM能够自动实现特征之间的二阶交叉吗？怎么还需要输入交叉特征？FM所实现的特征交叉指的两个特征的共现，比如'用户喜欢军事，并且，物料带有坦克标签'。除此之外，我们可以计算一些统计意义上的交叉，比如“用户携带的tag与物料携带的tag之间的重合度”。 这种交叉特征，对于刻画用户与物料的匹配程度，非常重要，对排序模型的性能提升非常显著。 但是，由于需要让用户与每个候选物料进行交叉，所以只适用于候选物料较少的精排场合，无法用于召回和粗排。
正如我在《推荐算法的'五环之歌'》一文中所论述的，ID特征才是推荐系统中的一等公民，在离线训练、线上服务时都具备一系列优势，所以FM中所有特征都ID化。
类别型特征，比如UserId、ItemId、一二级分类、标签等，天然就是ID型特征。 而实数型特征，比如Item过去的点击率、用户过去24小时的点击数之类，需要通过分桶转化为ID类特征。
训练模型
由于我们使用的都是ID类特征，所以FM的预测公式可以简化为
b是bias项，大家都一样，不影响排序，下文会忽略 n是这条样本中所包含的非零特征的个数 代表第i个特征的一阶权重 分别是i-th/j-th特征的隐向量，是两向量的点积
以上公式又可以继续推导如下，其中代表两向量按位相乘，ReduceSum表示将一个向量所有位置上的元素相加
=
=
这个公式避免了原始公式中两两特征交叉，将时间复杂度由降低为O(n)，而且n还是样本中的非零特征数。虽然算法的整体特征空间是上亿级别，但是由于推荐场景中特征非常稀疏，每个样本的n都是非常有限的，因此训练与预测的速度都非常快 。
得到logit之后，我们就可以与样本的label（i.e., 是否点击）计算binary cross-entropy loss，并通过SGD优化，从而得到各特征的一阶权重和隐向量。
线上服务
精排打分时，也采用logit=的公式，时间复杂度只有O(n)，n是有限的非零特征的数目，能保证线上预测的实时性。
但是，我们还可以继续优化。由于线上打分时，是将某个用户与一批候选item，喂入ranker，因此那一个用户的特征只需要抽取、计算一遍，在给多个item打分时复用。
logit=
、、，是对所有user特征的处理，只需要计算一遍。 、、，是对所有item特征的处理，需要针对每个候选item计算一遍。但是给一批item打分时，这部分计算可能通过多线程并行完成。
FM召回
样本
我曾经提出一个观点，“排序是特征的意义，而召回是样本，特别是负样本的艺术”，足见样本选择对召回算法的重要性。
还是拿“曝光点击”的item做正样本，同时需要排除误点击、自动播放等脏数据。 对于负样本的选择，基本原则之一就是，不能只拿曝光未点击做负样本。 大多数负样本，应该通过在item库中随机采样的方式得到。这其中的原因，请参考我的另一篇文章《负样本为王：评Facebook的向量化召回算法》。 至于是否能够拿“曝光未点击”作为随机负样本的补充，这一点有争议。根据我和Facebook的经验，增加“曝光未点击”做负样本，不仅没有收益，性能还有所下降。但是有的同学私信给我，说他们团队拿“曝光未点击”做补充，还是有正向收益的。但是，无论如何，大部分负样本应该通过随机采样得到，只有这样，训练时的数据分布才最接近预测时的数据分布。
在遵循“随机采样负样本”这一基本原则之外，还需要注意两点。
打压热门item
任何一个推荐系统，都难逃“2-8”定律的影响，即20%的热门item占据了80%的曝光量或点击量，因此正样本中，绝大部分是热门item。如果不加以打压，将导致每个用户的召回结果，都集中于少数热门item，从而失去个性化。为了打压热门item，需要我们在生成正负样本时，针对热门item采取截然相反的采样策略
降低热门item成为正样本的可能性，因此，item越热门，其成为正样本的概率就应该越低。 一个item '' 成为正样本的概率=， 其中z()=， a是一个超参，一般在1e-3~1e-5之间。 提升热门item成为item-的概率。可以从两个角度来理解：（1）既然热门item已经“绑架”了正样本，我们也需要提高热门item在负样本中的比例，以抵销热门item对loss的影响；（2）如果随机负采样时采取uniform sampling，因为有海量的候选item，而采样量有限，因此极可能采样得到的item与user“八杆子打不着”，既所谓的easy negative。而如果多采集一些热门item当负样本，因为绝大多数用户都喜欢热门item，这样得到的是所谓的hard negative，会极大地提升模型精度。所以在随机采样负样本时，一方面需要尽可能广泛地覆盖所有候选item，另一方面又需要尽量集中于高热item。 为了平衡这两方面的需求，我们定义负采样概率= f()是点击过第i个item的用户总数 调节因子b=1时，负采样完全按照item的热门程度进行，对热门item的打压最厉害，但是对所有候选item的覆盖度下降，导致训练数据环境与预测数据环境的gap增大，反而损害召回效果 调节因子b=0时，负采样变成uniform sampling，对所有候选item的覆盖度最高，减少了训练数据环境与预测数据环境的gap，但是对热门item的打压完全没有打压，采集到的item-都是easy negative，召回效果会偏热门，个性化较差 调节因子b一般取0.75
以上对热门item成为正、负样本时的采样加权公式，是从word2vec中借鉴而来。因为，Language Model中根据“上下文”预测“缺失词”的问题，其实就可以看成一个召回问题。所以，word2vec中处理高频词的方式，也可以拿来为我们所用，在召回中打压高热item。具体细节，可以参考我的知乎回答《推荐系统传统召回是怎么实现热门item的打压》。
增强Hard Negative
<user,item>的匹配度可以分成三个档次
匹配度最高的item，是以用户点击为代表的，那是正样本。 匹配度最低的item，那是随机抽取的。能被一眼看穿，是所谓的easy negative，达不到锻炼模型的目的。 所以要选取一部分匹配度适中、但用户又未点击的item，增加模型在训练时的难度，让模型能够关注细节，这就是所谓的hard negative。
如何选取hard negative，业界有不同的做法。Airbnb是根据业务逻辑来选取hard negative
增加与正样本同城的房间作为负样本，增强了正负样本在地域上的相似性，加大了模型的学习难度 增加“被房主拒绝”作为负样本，增强了正负样本在“匹配用户兴趣爱好”上的相似性，加大了模型的学习难度
当业务逻辑没有那么明显的信号时，就只能依靠模型自己来挖掘。Facebook的EBR与百度Mobius的作法非常相似，都是用上一版本的召回模型筛选出'相似度没那么高'的<user,item>对，作为额外负样本，来增强训练下一版本召回模型。具体做法上，又分online和offline两个版本
在线筛选
假如一个batch有n个正样本对，<>，那么的hard negative是利用上一轮迭代得到的召回模型，评估与同一个batch的除之外的所有的匹配度，再选择一个与最相似的作为hard negative。
一个正样本最多配置2个这样的hard negative，配置多了反而会有负向效果。 缺点是仅仅采用一个batch中的item作为hard negative的候选集，规模太小，可能还不足够hard。
离线筛选
拿当前召回模型，为每个候选item生成item embedding，灌入FAISS 拿当前召回模型，为每个user生成user embedding，在FAISS中检索出top K条近邻item 这top K条近邻item中，排名靠前的是positive，排名靠后的是easy negative，只有中间区域（Facebook的经验是101-500）的item可以作为hard negative。 将hard negative与随机采样得到的easy negative混合。因为毕竟线上召回时，候选库里还是以easy negative为主，所以作者将比例维持在easy:hard=100:1 拿增强后的负样本，训练下一版召回模型。
特征
接下来会说到，线上部署FM召回模型时，需要周期地在线下计算好几百万候选item的embedding，然后灌入FAISS建立索引，等待user embedding来检索。因为user embedding是在线生成，而item embedding是离线生成，二者分离造成我们在训练、预测时，不能使用任何user与候选item之间的统计交叉特征。这一点与FM精排视“统计交叉特征”为最重要特征，有着显著不同。
训练模型
如前文所述，由于召回中的负样本大部分是通过随机采样得到的，它们的'negative label'是含有噪声的。在这种情况下，再照搬精排使用binary cross-entropy loss追求“预估值”与“label”之间的“绝对准确性”，就有点强人所难了。所以，召回算法往往采用Pairwise LearningToRank（LTR），建模排序的“相对准确性”。即模型优化的目的，不是为了拟合'user与负样本item的匹配程度越低越好'，而是追求“user与正样本item的匹配程度，要远远高于，user与负样本item的匹配程度”。
所以，与精排模型中的每个训练样本为<user, item, label>的形式不同，训练召回模型时的每个训练样本为一个三元组，即<user, item+, item->。而模型设计，又拆分成两个子问题：（1）如何定义user与item的匹配程度？（2）如何定义“远远高于”？
如何定义user与item的匹配度
对于第一个问题，FM召回当然是采用FM公式了。
MatchScore(user, item)=
、、，是对所有user特征的处理。因为每条样本中，user是共享的，所以只需要计算一遍。 、、，是对所有item特征的处理。每条样本中，需要分别代入item+和item-进行计算。
细心的同学会发现，常见的召回模型中采用“user embedding与item embedding做点积或cosine”来计算匹配度，以方便利用FAISS进行快速近邻检索，担心以上公式训练出来的模型无法与FAISS兼容。不用担心，接下来讲线上服务的时候，我们会发现以上完整的FM公式也可以转变成两个向量点积的形式，同样可以利用FAISS快速检索。
如何定义'远远高于'
一种是采用margin hinge loss，即user与正样本item的匹配程度，要比，user与负样本item的匹配程度，高出一定的阈值。写成公式，就是
=
但是，这个公式里面又多出一个超参margin需要调节，因此我主要使用如下的BPR Loss。
BPR Loss的思想是计算'给user召回时，将item+排在item-前面的概率'，。因为一个三元组<user, item+, item->的ground-truth label永远是1，所以将喂入binary cross-entropy loss的公式，则有
=
线上服务
传统u2i召回
上文已经提到，训练时，我们用完整的FM公式来描述User与Item之间的匹配度。但是，在线上服务时，我们必须将匹配度描述成点积或cosine的形式，才能利用FAISS完成在百万、千万级物料库中的快速召回。这个'FM→点积'的公式转化如下图所示。
这时还可以做两个简化：
当为一个用户召回时，这个用户的一阶权重和特征隐向量都是固定的，因此从公式中省略'所有User特征一阶权重之和'和“所有User特征隐向量两两点积之和”（图中绿色公式）也不影响排序 所有User特征与所有Item特征之间的两两点积之和（第一行红色公式），等价于，将所有User特征embedding相加得到user embedding，将所有Item特征embedding相加得到item embedding，再拿user embedding与item embedding做点积（第二行红色公式）
这时，有一种方案就是，忽略公式中的蓝色部分，线上服务时只保留user embedding与item embedding的点积。这样做，也不是不行，但是效果不是特别好。因为用户喜欢的，未必一定是与自身最匹配的，也包括一些自身性质极佳的item（e.g.,热门item），所以，非常有必要将'所有Item特征一阶权重之和'和“所有Item特征隐向量两两点积之和”考虑进去，但是也还必须写成点积的形式。
解决方法是将user/item embedding都增广一维，如下图公式所示。
离线 每小时筛选出一部分适合召回的候选item（e.g.,过去7天至少被点击过3次的）。 针对每个候选item，提取其所有特征的一阶权重w和隐向量v，计算 将所有item embedding灌入FAISS建立索引。 在线 用户请求到来时，提取其所有特征的隐向量v，计算 拿user embedding到离线建立好的FAISS库中检索距离最近的Top N item embedding，作为召回结果返回。
Embedding的其他玩法
除了以上最常用的u2i召回，在我们得到user embedding和item embedding之后，还有很多其他玩法
拿用户最近一次点击的item embedding，在item faiss库中检索相似item，推荐给用户，实现“看了又看”、“猜你喜欢”等功能 拿当前user embedding，在user faiss库中检索相似user，把这些相似user消费过的item推荐给当前user，类似User CF，效果也非常好 可以拿item embedding，在user faiss库中检索可能对它感兴趣的user，把item给这些用户Push出去，达到提高用户黏性、减少用户流失的目的。
冷启动新用户与新物料
需要特别指出的是，很多召回，比如基于ALS的矩阵分解、Item CF等，都有冷启动问题，尽管单路召回性能很好，但是由于能够覆盖的用户、物料有限，对大盘指标的影响也很有限。而FM召回的优势在于，它对新用户、新物料都非常友好。
对新用户，哪怕他是一个纯新用户，没有任何画像与交互历史，他至少有一个特征叫“IsNewUser=1”，也就能够生成user embedding，FM也能替他召回 对新物料，任何物料都能拿到其画像（e.g., 一二级 分类、标签等），自然能够得到item embedding。我们可以专门建立一个FAISS库，里面的item都是刚入库的新item。用户请求到来时，除了在常规的、由已经有一些点击量的item faiss库里召回之外，还在这个只由新item组成的faiss库里召回。这样既能够将新item分发出去，又保证分发是高度个性化的，提高流量的利用率。
FM解释模型
模型解释性：全局 vs. 局部
如果说，如果要追求模型的表达能力，还要靠DNN这样的大杀器，FM只能算“模型能力+工程复杂度”综合考虑下一个不错的折中方案。但是，如果论模型的可解释性，DNN模型就难望FM的项背了。不仅如此，FM在解释性上最大优点，是能够提供针对一个或一群样本上的“局部特征重要性”。
首先，先解释一下“全局特征重要性”与“局部特征重要性”两个概念。
GBDT能提供的特征重要性，就是“全局特征重要性”，它代表每个特征对整个模型的影响力。但是，如果我们想知道，对某一个具体样本的预测得分，哪些特征的影响力比较大，“全局特征重要性”是无能为力的。 这时就需要“局部特征重要性”，能够针对每一个样本，分析出该样本的每个特征对该样本预测得分的贡献。比如SHAP算法能提供如下图形化展示，模型给这条样本的最终打分是24.41，从图中我们可以看到是哪些特征做了贡献，又有哪些特征拖了后腿。
为什么“局部特征重要性”更重要？因为数据分析的精髓就在于指标的拆解、下钻。
我们可以按性别、年龄筛选出不同用户的消费样本，“局部特征重要性”能够告诉我们，影响某一类用户消费的正负向因素 我们可以专门筛选出那些false positive/false negative的bad case，看看哪些特征的表现不如预期，导致预测失败
FM得分拆解
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的维度上。以上算法可以在Spark中分布式运行。
单独看一个样本上的拆解结果，可能有很多噪声。我们可以选取一组样本进行得分拆解，然后将这组样本在各个field pair上的得分进行统计，比如绘制热力图，就能看出哪些field pair对这组样本至关重要。
FM解释模型适用于DNN吗？
现在线上主力排序模型一般都已经是DNN了，基于FM的特征重要性分析方法，还有用吗？
我们认为，特征重要性是客观存在的，不同模型对重要特征的发掘、利用，只有量上的不同，没有本质上的不同。如果通过FM得分拆解，发现一组field对某个样本非常重要，DNN大概率与会同意这一判断。
反之，如果一组我们认为非常重要的field，FM拆解结果却显示不重要，大概率应该是样本、特征的处理上出了问题，同样也会对DNN造成负面影响。我们就曾经遇到过这样的现象，发现一组field的得分不如预期，经查是特征分桶不太合适。修复之后，DNN的性能也得到提升。由此可见，FM解释模型，也同样适用于DNN。
总结
虽然如今不如DNN、GNN那般受人关注，但是FM凭借其功能齐全、性能优异、便于上线和解释的优点，可称得上是推荐算法界中的瑞士军刀。正如同，虽然核武器、航母、坦克、隐身飞机这样的大杀器才是各国武库中的明星，但是瑞士军刀仍然被很多国家的军队采购为制式装备。各位炼丹调参侠们，在苦练倚天剑、屠龙刀的同时，一把小巧的瑞士军刀，相信我，你值得拥有。