推荐算法实战-五-召回（上）

一、传统召回算法

（一）基于物料属性的倒排索引

在离线时，将具有相同属性的物料集合起来，根据一些后验统计指标将物料排序。

当一个用户在线交互发出请求后，提取用户的兴趣标签，根据标签检索相应物料集合返回。

（二）基于统计的协同过滤算法

1、协同过滤的两个类型

传统的协同过滤是不是基于深度学习的，而是基于统计的。

①基于用户的协同过滤User CF

给用户a推荐与其相似的用户b喜欢的物料。

②基于物料的协同过滤Item CF

给用户a推荐与其喜欢的物料相似的物料。

2、基于Item的协同过滤

（1）机制描述

首先建立用户反馈矩阵 $A\in R^{m \times n}$ ，m是用户个数，n是物料个数。如果用户u和物料t交互过，那么A[u][t]=v，v可以来自于显式交互，比如打分，也可以来自于隐式交互，比如点击次数等指标。

由于大部分用户交互过的物料没那么多，因此A是比较稀疏的。

再计算物料相似矩阵 $S=AA^T$ ，其中S[i][j]表示第i个物料和第j个物料的相似程度。

在为用户u召回时，可以通过计算 $r_u=A[u,:]S$ ，其中r_u表示用户u对所有物料的喜好程度，根据数值大小排序后向用户推荐。

（2）优点

比起数据量庞大的用户数量，物料相对稳定且数量相对较小，S可以离线计算好。
可以使用MapReduce分布式算法进行S的计算。
可以采用cosine、欧几里得距离等来进行相似度的计算。

（三）矩阵分解MF算法

1、MF机制

MF定义一个反馈矩阵A，同Item CF中定义相同。A中空的位置用MF预测填充，有数值的则代表用户u与物料t的显式\隐式交互指标。

定义一个预测矩阵 $P \in R^{m \times n}$ ，用户隐向量矩阵 $U \in R^{m \times k}$ ，物料隐向量矩阵 $V \in R^{n \times k}$ 。有公式 $P=UV^T$ 。在MF中要学习优化的便是U和V，根据A中非空值进行训练模型，使P中相应位置的值靠近A中值。训练好U和V后，P[u,:]中筛选出得分最高且未被用户u消费过的前k个物料进行推荐（未被消费过的物料在A[u,:]中以空值形式存在）。

2、MF缺点

只能将user id和item id当做feature，信息来源受限。
对于没有参与训练的新用户和新物料，无法进行预测。

（四）如何合并多路召回

1、多路召回的作用和细节

多路召回有冗余防错和互相补充的作用。

将多路召回的结果合并成一个结果集，去重后再传递给下游模块。若超过了下游模块接收处理能力，那么实施截断。

2、多路召回合并

①错误的合并思路：将不同路的召回先人工评估重要性，重要性高的召回子序列先加入结果集，直到达到一定限度为止，剩下路的召回被截断。

②正确的合并思路：实施多轮多路召回合并，每次每路选取一小部分精华加入结果集，直到达到一定的限度。

二、向量化召回统一建模框架

（一）向量化召回简述

1、定义

向量化召回Embedding-based Retrieval，是将召回问题建模成向量空间内最近邻搜索问题。

2、类型

U2I：为用户找到其可能喜欢的物料。
I2I：推荐与用户喜欢的物料相似的物料。
U2U2I：推荐与用户相似的用户喜欢的物料。

3、机制描述

（1）机制：用户和物料都被映射到同一个向量空间

每个物料实例喂给模型后都被映射成向量，然后这些向量被存入faiss等向量数据库中，建立索引。
在线交互时，针对用户实例q，将其喂给模型映射成向量，然后在向量数据库中通过ANN算法查找与用户向量最为邻近的K个物料向量，将对应的物料返回。

（2）关注的问题

如何定义正样本，即哪些用户向量和物料向量应该邻近。
如何定义负样本，即哪些用户向量和物料向量应该远离。
如何映射成向量。
如何优化目标。

（二）如何定义正样本

1、关注的问题

哪些q向量（表示用户向量）和t向量（表示物料向量）在向量空间中的距离应该相近。

2、三种类型

I2I：同一个用户在同一个会话session（较短的用户行为序列）中交互过的物料向量应该相近，体现两个物料之间的相似性。
U2I：一个用户与其交互过的物料在向量空间中应该是相近的。
U2U

（三）如何定义负样本

1、负样本主要依靠随机采样

喂入召回模型中的负样本主要依靠随机采样。负样本在召回中地位非常重要。

2、怎么随机采样

随机采样一些样本作为负样本，与正样本相差过大的负样本被称为easy negative，与正样本优点相似的负样本被称为hard negative（比如对于一只狗而言，狐狸是hard negative，猫是easy negative）。

在召回模型中以easy negative为主，辅以hard negative。这是因为召回是从海量候选集中选出用户比较感兴趣的物料、筛去用户无感的物料，因此easy negative的数量优势能保证召回的基本精度。

（四）解耦生成embedding

1、排序鼓励交叉

特征策略：通过将特征交叉挖掘新模式。
模型结构：通常将用户特征、物料特征、交叉特征拼接成一个大向量共同喂给DNN，一般在第一个FC（全连接层）以后就分不清哪一位属于哪个特征了。

2、召回要求解耦

召回要求解耦的原因：因为召回面对的候选集太大了，交叉以后代价过大。
召回解耦的实现：（1）在离线时，计算好每个物料的embedding，存入faiss等向量数据库，建立检索。（2）用户在线交互时，计算用户的embedding向量，利用ANN算法等在faiss中检索相应物料并返回。

（五）如何优化目标

1、召回中用户物料匹配程度衡量方法

采用用户embedding和物料embedding的点积或者cosine来衡量两者的匹配程度，值越大越匹配。

2、召回与排序的精度要求

召回面对的候选集很大，不追求预测值的绝对准确，而是要求排序的相对准确，只要能够筛选出用户可能感兴趣的物料即可。因此常用的一些的loss遵循learning-to-rank（LTR）思想。
由于召回面对的数据中正样本是来自于真实数据，而负样本是随机采样得到的，因此在召回的过程中要求对正样本预测地较好即可，常采用多分类的softmax loss。

3、召回Loss

（1）NCE Loss

①Softmax Loss

优化目标是用户u和其交互过的物料t的向量越邻近越好，可以表示为以下公式：

$L_{softmax}=-\frac{1}{|B|}\sum_{(u_i,t_i)\in B}log\frac{exp(u_i,t_i)}{\sum_{j\in T}exp(u_i,t_j)}$

其中B表示一个batch，|B|是B中样本的数量，T是包含所有物料的集合，其中(u_i,t_i)被看做B中一个样本。Softmax loss将召回看成一个多分类问题，每个物料看为一类。由于量级过大，因此采用NCE Loss来简化分母。

②NCE Loss（Noise Contrastive Estimation)

NCE loss将softmax loss的超大多分类问题简化成了一个二分类问题（正样本和负样本）。其中正样本是与用户交互过的物料组成的，负样本是随机采样得到的。用G(u,t)来表示一个样本是正样本的logit如下式所示：

$G(u,t)=log\frac{P(t|u)}{Q(t|u)}=logP(t|u)-logQ(t|u)$

其中P表示用户u确实喜欢物料t的概率，而Q表示物料t是噪声的概率，比如说用户不喜欢物料t但是因为它太过热门被误点。

我们可以用u_i和t_i的点积来表示用户u确实喜欢物料t的概率，则可简化上式如下：

$G(u,t)=log\frac{P(t|u)}{Q(t|u)}=u\cdot t-logQ(t|u)$

-logQ(t|u)项的作用是为了防止热门物料被过度惩罚，因为大部分的噪声都来自于热门物料。这个修正项可以使用户u适当靠近热门物料，是一种补偿。-logQ(t|u)修正只发生在训练阶段，预测阶段不使用。

因此可以采用G(u,t)计算Binary Cross-Entropy Loss，就得到NCE Loss，公式如下：

$L_{NCE}=-\frac{1}{|B|}\sum_{(u_i,t_i)\in B}[log(1+exp(-G(u_i,t_i)))+\sum_{j \in S_i}log(1+exp(G(u_i,t_j)))]$

进一步简化计算，忽略修正项得到NEG（negative sampling loss）如下：

$L_{NEG}=-\frac{1}{|B|}\sum_{(u_i,t_i)\in B}[log(1+exp(-u_i,t_i))+\sum_{j \in S_i}log(1+exp(u_i,t_j))]$

NEGloss的优点在于：计算简便。而NCE的优点在于当负样本物料足够充足的时候，NCE梯度与softmax loss的梯度趋于一致。

（2）Sampled Softmax Loss

假设有一个推荐系统，其中需要从 1000 万个候选项中推荐商品给用户。如果使用标准的 Softmax Loss，你需要计算每个候选项的概率并归一化。而使用 Sampled Softmax Loss，你可以随机选择一小部分候选项（如1000个）进行计算，其中包括正样本（用户实际点击的商品）和若干负样本。这大大减少了计算负担，并使得模型能够在大规模数据集上有效训练。

（3）Pairwise Loss

Pairwise Loss是Learning-to-rank的一种实现。每个样本都是由用户、正样本（用户消费过的样本）、随机取样的负样本的embedding向量组成的三元组。优化目标是，用户与正样本的匹配程度要远远高于和负样本的匹配程度，因此可以采用一种Marginal Hinge Loss，表示如下：