一文看懂推荐系统：排序模型08：Factorization Machines（FM）因子分解机，一个特殊的案例就是MF，矩阵分解为uv的乘积

提示：最近系统性地学习推荐系统的课程。我们以小红书的场景为例，讲工业界的推荐系统。
我只讲工业界实际有用的技术。说实话，工业界的技术远远领先学术界，在公开渠道看到的书、论文跟工业界的实践有很大的gap，
看书学不到推荐系统的关键技术。
看书学不到推荐系统的关键技术。
看书学不到推荐系统的关键技术。

王树森娓娓道来**《小红书的推荐系统》**
GitHub资料连接：http://wangshusen.github.io/
B站视频合集：https://space.bilibili.com/1369507485/channel/seriesdetail?sid=2249610

基础知识：
【1】一文看懂推荐系统：概要01：推荐系统的基本概念
【2】一文看懂推荐系统：概要02：推荐系统的链路，从召回粗排，到精排，到重排，最终推荐展示给用户
【3】一文看懂推荐系统：召回01：基于物品的协同过滤（ItemCF），item-based Collaboration Filter的核心思想与推荐过程
【4】一文看懂推荐系统：召回02：Swing 模型，和itemCF很相似，区别在于计算相似度的方法不一样
【5】一文看懂推荐系统：召回03：基于用户的协同过滤（UserCF）,要计算用户之间的相似度
【6】一文看懂推荐系统：召回04：离散特征处理，one-hot编码和embedding特征嵌入
【7】一文看懂推荐系统：召回05：矩阵补充、最近邻查找，工业界基本不用了，但是有助于理解双塔模型
【8】一文看懂推荐系统：召回06：双塔模型——模型结构、训练方法，召回模型是后期融合特征，排序模型是前期融合特征
【9】一文看懂推荐系统：召回07：双塔模型——正负样本的选择，召回的目的是区分感兴趣和不感兴趣的，精排是区分感兴趣和非常感兴趣的
【10】一文看懂推荐系统：召回08：双塔模型——线上服务需要离线存物品向量、模型更新分为全量更新和增量更新
【11】一文看懂推荐系统：召回09：地理位置召回、作者召回、缓存召回
【12】一文看懂推荐系统：排序01：多目标模型
【13】一文看懂推荐系统：排序02：Multi-gate Mixture-of-Experts (MMoE)
【14】一文看懂推荐系统：排序03：预估分数融合
【15】一文看懂推荐系统：排序04：视频播放建模
【16】一文看懂推荐系统：排序05：排序模型的特征
【17】一文看懂推荐系统：排序06：粗排三塔模型，性能介于双塔模型和精排模型之间
【18】一文看懂推荐系统：特征交叉01：Factorized Machine (FM) 因式分解机
【19】一文看懂推荐系统：物品冷启01：优化目标 & 评价指标
【20】一文看懂推荐系统：物品冷启02：简单的召回通道
【21】一文看懂推荐系统：物品冷启03：聚类召回
【22】一文看懂推荐系统：物品冷启04：Look-Alike 召回，Look-Alike人群扩散
【23】一文看懂推荐系统：物品冷启05：流量调控
【24】一文看懂推荐系统：物品冷启06：冷启的AB测试
【25】推荐系统最经典的 排序模型 有哪些？你了解多少？
【26】一文看懂推荐系统：排序07：GBDT+LR模型

提示：文章目录

Factorization Machines（FM）

按照发表年份，这篇博客应该在GBDT+LR之前写的，
但因为FM相比较GBDT+LR的内容稍微多些，所以就后写了这篇博客。

言归正传，FM是推荐系统领域大佬rendle于2010年发表在ICDM上的论文，
是一篇非常非常有影响力的论文，启发了此后10年学术界大量的工作，
直接的改进就有引入神经网络的NFM，引入attention的AFM等
（关于NFM和AFM这两个能不能像FM一样在工业界一样work，这个…，
不过话又说回来，学术界的价值就在于提供idea，大规模商用另说了）。

在详细介绍FM之前，先用一句话概括下FM：隐式向量特征交叉。

这么一看FM在那个时候已经孕育了embedding的思想。
接下来会介绍LR、SVM、MF，这三是FM的灵感源泉，这样看起来条理也比较清晰。

1. LR

先来回顾下LR：

那么，如果我们想做特征的二阶交叉，很自然的可以把LR改造为如下的函数：

2. SVM

我在很久很久以前的博客里写过一篇最基本最浅显的SVM
（现在回头来看着实有些浅显，没有讲解到核函数的本质），
参见：支持向量机SVM，

支持向量机干的事就是既然低维空间下找不到一个超平面来划分两类样本，
那么我映射下，把低维空间映射成高维空间来寻得一个超平面好了。

所以，假如我们用ϕ ( x ) 表示将x 映射后的特征向量，支持向量机模型为：

2.1 线性核函数

2.2 多项式核函数

我们看到二项式核函数的SVM和公式(2)中存在一样的问题，
就是交叉项的参数是独立的，
这会使得如果这个交叉特征值没有在样本里出现，这个参数是无法学到的。

所以，我们总结下，目前在模型层面做交叉特征的难点主要有以下两个方面：

**交叉特征的参数独立，**强依赖于在样本中的共现信息，如果交叉特征值没有出现，那么参数无法学习。
时间复杂度问题，直接做二阶交叉，时间复杂度为O(N^2)，复杂度过高。

3. FM

那么FM则解决了上面两个问题，直接上FM的模型公式：


那么问题来了，这种方法是FM独创的吗？

答案是：NO。

这种思想来源于一个古老且有效的方法矩阵分解MF（matrix factorization），

在推荐系统里，每个用户对每个物品的评分，可以构建出一个user-item矩阵，
而矩阵分解的核心思想是用一个用户embedding矩阵和一个物品embedding矩阵的乘积来近似这个大矩阵，
这两个embedding矩阵是可训练学习的。

上一张图来形象的表示矩阵分解

到这里，可以看到FM解决了我们前面抛出的两个问题中的第一个问题
（交叉特征参数独立，依赖于交叉特征的共现），

下面来看看FM如何解决第二个问题（时间复杂度问题），
再来看看公式（7）中的二阶部分，时间复杂度为O ( N 2 )
FM把这部分做了个公式推导，把时间复杂度降到了O ( K N )
下面来看看FM的推到过程：

4. FM实现

1.作者实现版本
rendle大佬用C++自己coding了个FM，并且开源了，地址：libFM，
大佬就是大佬，不仅学术能力了解，coding能力也不逞多让，不得不服。

下面来学习下大佬的代码，这里只列核心代码，讲解参见我的注释

double fm_model::predict(sparse_row<FM_FLOAT>& x, DVector<double> &sum, DVector<double> &sum_sqr) {
  double result = 0;
  // 公式(7)中的第一项，w0
  if (k0) {
    result += w0;
  }
  // 第二项，一阶部分w_i*x_i
  if (k1) {
    for (uint i = 0; i < x.size; i++) {
      assert(x.data[i].id < num_attribute); // num_attribute --> feature num
      result += w(x.data[i].id) * x.data[i].value;
    }
  }
  // 第三项，二阶部分
  for (int f = 0; f < num_factor; f++) {   // num_factor --> embedding size
    sum(f) = 0;
    sum_sqr(f) = 0;
    for (uint i = 0; i < x.size; i++) {
      double d = v(f,x.data[i].id) * x.data[i].value;
      sum(f) += d;
      sum_sqr(f) += d*d;
    }
    result += 0.5 * (sum(f)*sum(f) - sum_sqr(f));
  }
  return result;
}

// sgd，梯度部分
void fm_SGD(fm_model* fm, const double& learn_rate, sparse_row<DATA_FLOAT> &x, const double multiplier, DVector<double> &sum) {
  if (fm->k0) {
    double& w0 = fm->w0;
    w0 -= learn_rate * (multiplier + fm->reg0 * w0);
  }
  if (fm->k1) {
    for (uint i = 0; i < x.size; i++) {
      double& w = fm->w(x.data[i].id);
      w -= learn_rate * (multiplier * x.data[i].value + fm->regw * w);
    }
  }
  for (int f = 0; f < fm->num_factor; f++) {
    for (uint i = 0; i < x.size; i++) {
      double& v = fm->v(f,x.data[i].id);
      double grad = sum(f) * x.data[i].value - v * x.data[i].value * x.data[i].value;
      v -= learn_rate * (multiplier * grad + fm->regv * v);
    }
  }
}

2.paddlepaddle版本

百度官方开源了paddlepaddle版本的FM实现，文档介绍的相对详细点，参见：https://github.com/PaddlePaddle/PaddleRec/tree/release/2.1.0/models/rank/fm
因为使用的数据集包含离散特征和连续值特征两类，
一种办法是连续特征离散化，这样所有特征都当做离散特征处理，处理起来比较简单，代码比较统一。
另一种就是构建网络时离散值特征和连续值特征分开考虑，paddle版本FM采用了后者。

def forward(self, sparse_inputs, dense_inputs):
        # -------------------- first order term  --------------------
        sparse_inputs_concat = paddle.concat(sparse_inputs, axis=1)
        sparse_emb_one = self.embedding_one(sparse_inputs_concat)

        dense_emb_one = paddle.multiply(dense_inputs, self.dense_w_one)
        dense_emb_one = paddle.unsqueeze(dense_emb_one, axis=2)

        y_first_order = paddle.sum(sparse_emb_one, 1) + paddle.sum(
            dense_emb_one, 1)

        # -------------------- second order term  --------------------
        sparse_embeddings = self.embedding(sparse_inputs_concat)
        dense_inputs_re = paddle.unsqueeze(dense_inputs, axis=2)
        dense_embeddings = paddle.multiply(dense_inputs_re, self.dense_w)
        feat_embeddings = paddle.concat([sparse_embeddings, dense_embeddings],
                                        1)

        # sum_square part
        summed_features_emb = paddle.sum(feat_embeddings,
                                         1)  # None * embedding_size
        summed_features_emb_square = paddle.square(
            summed_features_emb)  # None * embedding_size

        # square_sum part
        squared_features_emb = paddle.square(
            feat_embeddings)  # None * num_field * embedding_size
        squared_sum_features_emb = paddle.sum(squared_features_emb,
                                              1)  # None * embedding_size

        y_second_order = 0.5 * paddle.sum(
            summed_features_emb_square - squared_sum_features_emb,
            1,
            keepdim=True)  # None * 1

        return y_first_order, y_second_order

总结

提示：如何系统地学习推荐系统，本系列文章可以帮到你

（1）找工作投简历的话，你要将招聘单位的岗位需求和你的研究方向和工作内容对应起来，这样才能契合公司招聘需求，否则它直接把简历给你挂了
（2）你到底是要进公司做推荐系统方向？还是纯cv方向？还是NLP方向？还是语音方向？还是深度学习机器学习技术中台？还是硬件？还是前端开发？后端开发？测试开发？产品？人力？行政？这些你不可能啥都会，你需要找准一个方向，自己有积累，才能去投递，否则面试官跟你聊什么呢？
（3）今日推荐系统学习经验：Factorization Machines（FM）因子分解机，一个特殊的案例就是MF，矩阵分解为uv的乘积