推荐系统-基于FM模型的召回

这篇文章我会介绍在推荐系统中如何基于FM模型来做召回。召回可以粗略地分为两大类，一种是统计类的，比如ItemCF, UserCF，都是基于对历史大数据的统计，找到相似矩阵，不涉及模型训练。另一种是模型类的，比如FM、YoutubeNet、DSSM之类的，有确定的模型以及损失函数。

召回阶段

一个最基本的推荐系统必定包含两个phase，召回和排序。很多文章都会提到一句: 召回阶段主要看样本，排序阶段主要靠特征。那这到底是什么意思呢？在推荐系统的召回训练中，负样本不能仅仅是曝光未点击。排序是从已经圈定的偏好item中再次排序，而召回更多的是侧重一定要排除用户压根不感兴趣的。点击的item用作正样本，这一点毫无争议。那么负样本应该如何构建呢？

在2020年Facebook最新的论文《Embedding-based Retrieval in Facebook Search》提到了不能只拿曝光未点击做负样本，负样本需要进行easy negative/hard negative分级。 hard negative就是说根据业务知识判断，来加入负样本。Airbnb在《Real-time Personalization using Embeddings for Search Ranking at Airbnb》一文中的做法，就是根据业务逻辑来选取hard negative

增加与正样本同城的房间作为负样本，增强了正负样本在地域上的相似性，加大了模型的学习难度
增加“被房主拒绝”作为负样本，增强了正负样本在“匹配用户兴趣爱好”上的相似性，加大了模型的学习难度

而easy negative就是用一种随机采样的方式来模拟负样本的产生。那么我们能和排序阶段一样使用<user, item, label>这样的格式吗？一般的我们会在排序时使用pointwise形式的样本，在召回阶段我们应该更倾向使用pairwise形式的样本。理由如下:

负样本大多是随机生成(easy nagative)，不应该严格的说user偏好或者不偏好这种二元信息，而是一种相对偏好，比如user点击了a，而b是随机生成，我们会说user相比较b更偏好a
召回样本区别于排序中常见的<user, item, label>，而是三元组<user, item+, item->，预测的目标是MatchScore(user, item+)要远高于MatchScore(user, item-)

FM模型

FM模型和一般的线性模型相比只是多考虑了特征交叉项，

\begin{equation} \hat{y}(x) = w_{0} + \sum_{i = 1}^n w_{i}x_{i} + \sum_{i = 1}^n\sum_{j = i+1}^nw_{i, j}x_{i}x_j \end{equation}

上述的交叉项满足不为0的条件非常少(需要 $x_i, x_j$ 均不为 0)，当样本训练不足时容易导致参数训练不充分，影响模型效果，所以交叉项参数的训练问题我们采用矩阵分解近似计算。

\begin{equation}\label{2}\begin{split} \hat{y}(x) &= w_{0} + \sum_{i = 1}^n w_{i}x_{i} + \sum_{i = 1}^n\sum_{j = i+1}^n<v_i, v_j>x_{i}x_j \\ <v_i, v_j> &= \sum_{f=1}^{k}v_{j, f}v_{j,f} \\ \end{split}\end{equation}

其中模型需要估计的参数是 $w_0 \in \mathbb{R}, \mathbf{w} \in \mathbb{R}^n, \mathbf{V} \in \mathbb{R}^{n \times k}$

如果直接计算公式 $\ref{2}$ ,其时间复杂度 $O(kn^2)$ ，通过公式变换可以减少到线性复杂度

\begin{equation}\begin{split} &\sum_{i=1}^{n}\sum_{j=i+1}^{n}<v_j, v_j>x_ix_j \\ &= \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}<v_j, v_j>x_ix_j - \frac{1}{2}\sum_{i=1}^n<v_j,v_j>x_ix_j \\ &= \frac{1}{2}( \sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^kv_{i, f}v_{j, f}x_ix_j - \sum_{i=1}^n\sum_{f=1}^kv_{i, f}v_{i,f}x_ix_i ) \\ &= \frac{1}{2}\sum_{f=1}^k( (\sum_{i=1}^nv_{i,f}x_i)(\sum_{j=1}^n)v_{j, f}x_j) - \sum_{i = 1}^{n}v_{i, f}^2x_i^2) \\ &= \frac{1}{2}\sum_{f=1}^k( (\sum_{i=1}^nv_{i,f}x_i)^2 - \sum_{i = 1}^n v_{i,f}^2x_i^2) \end{split}\end{equation}

怎么理解上述的公式呢? FM模型最终的模型结果不但有每个维度的权重还会有每个维度对应的一个向量。如下图所示(假设一共有n个维度, 隐藏维度是k)

\begin{equation} \begin{matrix} v_{0, 0} & v_{0, 1} & \cdots & v_{0, k-1} \\ v_{1, 0} & v_{1, 1} & \cdots & v_{1, k-1} \\ \vdots & \vdots & \ddots &\vdots \\ v_{n-1, 0} & v_{n-1, 1} & \cdots & v_{n-1, k-1}\\ \end{matrix}\end{equation}

FFM模型

FFM（Field-aware Factorization Machine）作为FM的升级版模型。通过引入field的概念，FFM把相同性质的特征归于同一个field。在FFM中，每一维特征 $X_{i}$ ，针对其它特征的每一种field $f_j$ ，都会学习一个隐向量 $v_{i,f_j}$ 。因此，隐向量不仅与特征相关，也与field相关。

\begin{equation} \hat{y}(x) = w_{0} + \sum_{i = 1}^n w_{i}x_{i} + \sum_{i = 1}^n\sum_{j = i+1}^n<v_{i, f_j}, v_{j,f_i}>x_{i}x_j \end{equation}

举个例子

现在有交叉项 $<v_{i, f_j}, v_{j,f_i}>x_\{i\}x_j$ ;
$f_j$ 是 $x_j$ 所属的field， $f_i$ 是 $x_i$ 所属的field
某个具体的特征x一定只会所属一个field
2个特征维度组合时，就会拿“对方”的所属field
FFM 当然也会包含属于同一个field下的维度两两组合

鉴于FFM的特性，我们没有办法对其进行线性计算优化，感兴趣的读者可以尝试使用libFFM, 另外，FFM的求解参数一共有nfk个(假设有n个维度，f个field，k维隐藏向量), 不能像FM一样优化，求解速度较慢。

样本选择

样本选择其实就一个注意点: 打压hot item。在之前的协同过滤中也提到打压方式，这里的打压思想也是一致的，我们要降低hot item被采样到的概率。

\begin{equation}\label{sampling} \begin{split} P_{pos}(w_i) &= (\sqrt{\frac{z(w_i)}{\alpha}} + 1) \frac{\alpha}{z(w_i)} \\ P_{neg}(w_i) &= \frac{f(w_i)^{\beta}}{\sum_wf(w)^{\beta}} \end{split} \end{equation}

在上述 $\ref{sampling}$ 公式中，如果希望对hot item在采样时打压更加厉害，可以减小 $\alpha$ 和 $\beta$ , $\alpha$ 的范围一般是 $1e^{-3}$ 到 $1e^{-5}$ , $\beta$ 一般取0.75。这两个采样公式正是来自word2vec中所用的公式。

在具体工程实践时，可以借助框架(比如spark)实现的分层采样(stratified sampling):

val df = sampleDF.stat.sampleBy("video_id", fractions, 1024L)

FM模型的求解

这边我会根据链式求导法则列出FM模型的求解过程，在实际应用中并不需要，目前的深度学习框架都提供了自动求导。

针对一个二分类问题，其损失函数如下图所示(假设用BGD, 一个Batch的size为N, 维度大小为n 隐藏维度大小是d)

\begin{equation}\label{FMderive}\begin{split} J &= - \frac{1}{N} \sum_{i=0}^{N-1}y^{(i)}\ln{\hat{y}^{(i)}} + (1 - y^{(i)})\ln{(1 - \hat{y}^{(i)})} \\ \hat{y}^{(i)} &= \phi{(z^{(i)})} = \frac{1}{1 + e^{(-z^{(i)})}} \\ z &= \omega_0 + \sum\omega_ix_i + \sum_{i = 1}^n\sum_{j = i+1}^n<v_{i, f_j}, v_{j,f_i}>x_{i}x_j \\ \end{split}\end{equation}

所以我们会得到求导公式

\begin{equation}\label{derivation}\begin{split} \frac{\partial J}{\partial \phi{(z)}} \frac{\phi{(z)} }{z} &= -\frac{1}{N}\sum_{i = 0}^{N-1} (y^{(i)} - \phi{(z^{i})}) \\ &= -\frac{1}{N}(\mathbf{Y} - \Phi{(\mathbf{Z})})^T \mathbf{I} \end{split} \end{equation}

\begin{equation} \frac{\partial z}{\partial \theta} = \begin{cases} 1, & \theta = \omega_0 \\ x_i, & \theta = \omega_i \\ x_i\sum_{j = 1}^n v_{j, f}x_j - v_{i, f}x_i^2, & \theta = v_{i, f} \\ \end{cases} \end{equation}

基于FM的召回模型

前面讲述的内容只能算铺垫，最关键的损失函数(目标函数)还没有展示给大家，直接抛出公式

\begin{equation}\label{FM} \begin{split} J &= -\frac{1}{N}\sum_iy^{(i)}ln\hat{y}^{(i)} + (1 - y^{(i)})ln(1-\hat{y}^{(i)}) \\ \hat{y}^{(i)} &= \phi(z^{(i)}) = \frac{1}{1 + e^{-z^{(i)}}} \\ z^{(i)} &= y_{fm}(x_{+}^{(i)}) - y_{fm}(x_{-}^{(i)}) \\ y_{fm}(x) &= w_0 + \sum_{i=1}^n w_ix_i + \sum_{i=1}^d\sum_{j=i+1}^d<v_i, v_j>x_ix_j \\ \end{split} \end{equation}

$y^{(i)}$ 表示真实样本label，例如对于三元样本<user, item+, item-> 它的label应该是1，同时我们还是使用交叉熵做为损失函数，这边交叉熵的概率描述的是pair样本之间的优先级关系。

下面是核心代码片段展示

    HIDDEN_NUM = 16

    inputsPos = tf.compat.v1.placeholder(tf.int32)

    inputsNeg = tf.compat.v1.placeholder(tf.int32)

    linearW = tf.Variable(tf.random_normal([FEATURE_NUM, 1], 0.0, 1.0))

    embedding = tf.Variable(tf.random_normal([FEATURE_NUM, HIDDEN_NUM], 0.0, 1.0))

    linear_op = tf.compat.v1.reduce_sum(tf.nn.embedding_lookup(linearW, inputsPos), axis=1) \
                - tf.compat.v1.reduce_sum(tf.nn.embedding_lookup(linearW, inputsNeg), axis=1)

    cross_op_a = tf.compat.v1.reduce_sum(
        tf.square(tf.compat.v1.reduce_sum(tf.nn.embedding_lookup(embedding, inputsPos), axis=1)), axis=1)
    cross_op_b = tf.compat.v1.reduce_sum(
        tf.compat.v1.reduce_sum(tf.square(tf.nn.embedding_lookup(embedding, inputsPos)), axis=1), axis=1)

    cross_op_inner = (tf.square(tf.compat.v1.reduce_sum(tf.nn.embedding_lookup(embedding, inputsPos), axis=1)) -
                      tf.compat.v1.reduce_sum(tf.square(tf.nn.embedding_lookup(embedding, inputsPos)), axis=1)) - \
                     (tf.square(tf.compat.v1.reduce_sum(tf.nn.embedding_lookup(embedding, inputsNeg), axis=1)) -
                      tf.compat.v1.reduce_sum(tf.square(tf.nn.embedding_lookup(embedding, inputsNeg)), axis=1))

    cross_op = 0.5 * tf.compat.v1.reduce_sum(cross_op_inner, axis=1)

    z = tf.clip_by_value(linear_op + cross_op, -4, 4)
    # 只有label = 1 所以只有一项
    cost_func = - tf.reduce_mean(tf.math.log(tf.nn.sigmoid(z)))

求解过程就交给tensorflow吧，在笔者的电脑配置(2018 Macbook)上，300W维度的以BSD方式进行的梯度训练。一共1.5W个batch 耗时30min。

向量检索

生产环境中，我们都需要借助向量检索引擎来完成召回。假设我们已经完成了FM的训练，我们召回的目标就是 $\hat{y}_{fm}(x)$ 的TopN个。但是这个表达式应该怎么算呢?

graph LR
    d1["item 向量"] --> d2["v0|v1|v2|...|vf_1|1|1|"]
    d3["user 向量"] --> d4["v0|v1|v2|...|vf_1|w_0|w_1|"]

如上图所示，在使用向量检索引擎时需要把item侧的向量都放入引擎内(比如milvus), 同时要在低位补充1，另一方方面，user侧的向量累加后，还需要在低位补足对应的weight。总之就是把FM的公式改写成向量内积的形式，这样就可以使用向量检索引擎了。

小结

在召回阶段，我们借助learning-to-rank的思想，计算item之间的偏序
借助FM模型，我们可以把所有的id类特征向量化，做成一个双塔模型
采样过程要注意对hot item的降采样
FM模型做为一个基础模型，还可以有很多变种，比如NFM模型，FFM模型

参考: