推荐算法实战-5-召回（1）-召回中的loss设计

本文是推荐算法实战系列第五篇文章。

前面文章包括四个部分：

推荐系统简介
特征工程
embedding
精排

本文开始介绍召回。

1、传统召回算法

传统召回算法基于规则和统计，较少训练模型，尤其是深度模型。

这类算法虽然从技术上不如深度学习亮眼，但是由于可解释性好、简单，仍有用武之地。

例如，业务团队需要提升文章的转发分享率。如果用DNN模型实现这个需求，可以增加转发分享相关的特征，或者提升转发目标权重。

采用传统召回，可以新增一路召回策略，并在最终的流量机制策略上做一些调整，能起到立竿见影的效果。

1.1、基于物料属性的倒排索引

离线构造一个类似Map<Item Attribute， ItemSet>的集合。集合的key为物料属性，value为满足该属性的所有物料，按照后验消费指标（CTR）排序。

这种方式简单、直观。

1.2、协同过滤

CF是一类经典的数据驱动的召回算法。包括

UserCF：找到与用户A相似爱好的用户B，把B喜欢的东西推荐给A。
ItemCF：用户A喜欢物品C，找到与C相似的物料D，把D推荐给A。

传统的CF，无需训练模型，完全基于统计。以ItemCF为例：

定义用户反馈矩阵，${A\in R^{m \times n}}$。其中，m是用户数量，n是item数量。如果u与i交互过，则A[u,i] = v。v可以是显式打分，也可以是隐式反馈。A非常稀疏。

计算${S = A^TA \in R^{n \times n}}$，S[i,j]表示物料i与j之间的相似度。它的含义是：物品i所在的列（即i的用户向量）与物品j的用户向量的内积。。它与之前的文章中讲述的原理是一样的。即：

喜欢物品i的用户集合为Vi，即反馈矩阵的第i列，
喜欢物品j的用户集合为Vj，即反馈矩阵的第j列

则i与j的相似性可以定义为：${Sim_{i,j} = \frac{

V_i \cap V_j

}{\sqrt{

V_i

}\sqrt{

V_j

}}}$

相当于向量Vi、Vj的余弦相似度。

为用户u召回时，计算${r_u = A[u,:]S}$，表示u交互过的所有k个物品，计算它们与所有n个物品的相似性，得到n* k个相似性得分，再从中选取top-M。
综上，以交互矩阵A为基础，用矩阵运算的方式实现了ItemCF算法。ItemCF只使用数据，没有训练模型。
上述过程，可以基于MapReduce分布式实现。目前大厂通常有相应的组件。

1.3、矩阵分解

上述基于交互矩阵实现的ItemCF有一些问题：

交互矩阵A非常稀疏。大部分user-item对没有历史交互信息。
ItemCF先要拿到用户u交互过的i，再根据item相似性找到相关的item。
u没有交互过的i，无法参与召回，即交互矩阵中为0的u-i对既无法贡献相似性，也无法贡献召回候选集，被浪费了。
泛化性差。

为此，人们提出了矩阵分解算法（Matrix Facorization，MF）。

从数学上来讲，任意矩阵A（m * n），可以分解为两个小矩阵U（m * k）和V（n * k）的乘积： $A_{m \times n} = U_{m \times k} \times V^T_{k \times n}$

U：用户隐向量
V：物品隐向量

接下来的问题是如何求解U、V？

设预估交互矩阵${P = UV^T}$
可以通过反向传播算法，以A为目标（label），迭代训练，优化U、V，使得P逼近A。

MF既使用数据，也训练模型。由于U和V中每个元素都有值，它的泛化性大大优于ItemCF。它的隐向量初步具备了embedding无中生有的思想。

MF的缺点：

只使用userid、itemid当特征，只使用了交互矩阵，信息来源有限；
新用户、新item未在交互矩阵A中出现，无法预测。

目前业界MF使用较少。

2、向量召回

向量召回（Embedding-Based Retrieval，EBR），是指召回问题建模为向量空间内的近邻搜索问题。

其基本套路如下：

假设召回问题包含两类实体Q（例如用户）和T（例如物料）。
离线：训练模型M，将Q中的每个实例q和T中的每个实例t，都映射到同一个向量空间。
离线：将T中的每个实例喂入M，映射成向量，存入向量数据库，例如FAISS、Milvus等。
在线：对于每一个Q中的实例q，调用M，得到向量Emb-q。在向量数据库中通过ANN，查找最近的K个T类向量，作为召回结果。

向量化召回不是某个具体的算法，而是一个庞大的家族。其建模步骤可以归纳为：

如何定义正样本，即哪些q和t应该在向量空间中相近；
如何定义负样本，即哪些q和t应该较远；
如何将q和t映射成向量；
如何定义优化目标，即如何确定损失函数。

2.1、如何定义正样本

不同的召回场景定义不同：

I2I：q和t都是物料。比如同一个用户在同一个session交互过的物料，在向量空间相近。
U2I：q是用户，t是物料。一个用户与其交互过的物料，在向量空间中相近。
U2U：q、t都是用户。比如使用孪生网络。q是用户一半的交互历史，t是同一用户另一半交互历史，二者向量空间相似。
2.2、如何定义负样本

排序是特征的艺术，召回是（负）样本的艺术。

负样本是举反例告诉模型q与t-不匹配。其要义是让模型“开眼界、见世面”，即见识到形形色色、五花八门、不同角度的“q与t-之间的差异性”。

2.2.1、随机采样负样本

Youtube、DSSM等论文都是随机采样负样本。

召回为什么不用“曝光未点击”做负样本？

原因在于“离线训练的数据分布应该与线上服务时的数据分布一致”。

排序的目标是优中选优，它面对的候选物料是已经和用户兴趣比较match的优质物料。
召回的目标是将用户可能喜欢的与“八竿子打不着”的物料区分开。它面对的候选物料良莠不齐。

喂入召回模型的样本既要让模型见过最匹配的user、item组合，也要见过最不靠谱的组合，从而让模型不在大是大非上犯错误。

曝光未点击的样本，是经过精排、重排等层层筛选过的样本，已经是用户比较感兴趣的样本。

召回的样本如果只从曝光样本中选取，会引入样本选择偏差（SSB），即曝光样本与线上召回输入的待打分样本分布存在较大偏差。

解决方法是，随机采样生成负样本，不能只拿曝光未点击做负样本。

至于说曝光未点击能不能做补充负样本，业界尚无定论。有些（例如Facebook）认为它是鸡肋，有些认为它是hard negative。

（备注，如果随机采样到了用户非常感兴趣的样本，把它一股脑作为负样本会误导模型吗？）

2.2.2、随机负采样的技巧

随机采样的负样本被称为easy negative。它能帮助模型“开眼界”，但是不利于模型精度提升。

为了让模型关注正负样本细节差异，可以设计困难负样本，hard negative。

通常，模型以easy negative 为主，以hard negative为辅。Facebook的经验是Easy：hard=100:1。毕竟线上召回时，大部分是八杆子打不着的物料，保证easy的样本优势，能够hold住模型的及格线。

2.3、Embedding向量生成

排序模型鼓励交叉，召回模型要求解耦。

线上预测时，召回模型的候选集非常大，从预测性能考虑，需要解耦。

特征上，召回模型无法使用用户、item交叉特征
模型上，用户塔和物品塔相对独立。用户塔利用用户特征，物品塔利用物品特征。各自生成embeddign向量后才允许交叉。

这样的好处是：

离线时，不必知道哪个用户发起的请求，可以提前计算好所有物料的embedding。
在线时，根据用户侧特征，生成用户向量，通过查表得到候选item。既能保证个性化，也满足时延要求。

2.4、如何定义优化目标，设计损失函数

精排追求预测值的“绝对准确性”，通常使用交叉熵损失函数BCE，力图将每个样本的CTR/CVR预测准确。

召回主要考虑“相对准确性”：

召回的候选集非常庞大，通常只有正样本来自用户真实反馈，负样本往往未曾曝光，所以召回没必要对负样本预测绝对准确。召回常用的一类损失函数是多分类的softmax loss，只要求正样本的预估概率越高越好。
召回的作用是筛选候选集，只要能把用户喜欢的排在前面就好。另一类常用的损失函数遵循LTR思想，不求预估值的绝对准确，只求排序的相对准确。

以下以U2I为例，介绍几种常用loss。它们都被广泛使用，具体选择哪一种可以通过线上ab给出答案。

2.4.1、NCE loss

常见的softmax loss如下： $\begin{aligned} L_{softmax} &= -\frac{1}{|B|}\sum_i log\frac{exp(logit_i)}{\sum_j(logit_j)} \\ &= -\frac{1}{|B|}\sum_{(u_i, t_i) \in B} log \frac{exp(u_i \cdot t_i)}{\sum_{j \in T} exp(u_i \cdot t_j)} \end{aligned}$

B表示一个batch。其中第i条样本（ui，ti）由用户ui和他交互过的正例物料ti组成。（备注：样本中只有正例吗？随机采样的负例呢？）
ui、ti分别是用户塔和物品塔产出的用户embedding、物品embedding。
分子：正例对，越大越好，表示用户向量与正例物料向量越匹配。
分母：负例对，越小越好，表示用户向量与负例物料向量越不匹配。（备注：分母包含了分子的正例对吗？）
softmax loss将召回看成一个超大规模的多分类问题，每个候选物料一个类别，所有候选物料集合用T表示。
loss的含义：ui在T中选中正例ti的概率（log项）越高越好。
体现了不追求绝对准确性，只追求相对准确性的特点。

分母中的T表示所有（负）样本集合，非常大，因此计算量很大。

Noise Contrastive Estimation（NCE）是简化分母的一种思路。

NCE在NLP中（e.g. word2vec）比较常用。

如果T很大，难以归一化，我们可以从全集T中随机采样一批S（噪声），然后“预测样本是否来自于随机采样的噪声”，从而将多分类问题转化成了二分类问题。

例如，用户u点击的物料组成正例集合R，再采样一部分负例构成集合S，即“噪声”。u的候选物料集合不是物料库T，而是有限集合${C=R\cup S}$。NCE的二分类问题变成，如果候选物料t来自R则是正例，来自S则是负例。

用G(u,t)表示一条样本(u,t)属于正例的logit，表示如下（备注：为何可以如此定义？）： $G(u,t) = log \frac{P(t|u}{Q(t|u)} = logP(t|u) - log Q(t|u)$

P：u喜欢t的概率，召回模型建模的目标。
Q：u随机点击t的概率，是一个超参。
G(u,t)是二者的比值，这也是NCE中contrastive（对比）的含义。

在向量召回中，我们用向量点击来建模P，得到如下公式： $G(u,t) = u \cdot t - log Q(t|u)$

用u与t的点积代替logP。
在计算u与t的匹配度后，需要根据负采样概率Q修正。
负采样Q通常是物料热度的递增函数，以实现对热门物料的打压。
物料t热度越大，它被-logQ修正越厉害，被u点击的“个性化”成分越弱。
-logQ修正只发生在训练阶段，预测时还是那${u \cdot t}$计算u与t的匹配度。

根据G计算BCE，得到NCE loss，公式如下：

$\begin{aligned} L_{NCE} &= -\frac{1}{B}\sum_{(u_i,t_i) \in B}[log( \sigma(G(u_i,t_i))) + \sum_{j \in S_i} log(1 - \sigma(G(u_i, t_j))] \\ \end{aligned}$ 由于

$\begin{aligned} \sigma(x) &= (1 + exp(-x))^{-1} \\ log\sigma(x) &= -log(1 + exp(-x)) \\ -log\sigma(x) &= log(1 + exp(-x)) \\ 以及 \\ 1 - \sigma(x) &= (1 + exp(x)) ^{-1} \\ \frac{1}{1-\sigma(x)} &= 1+exp(x) \\ -log(1-\sigma(x)) &= log(1 + exp(x) ) \end{aligned}$ 进一步得到： $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))]$

B代表一个batch，第i条样本由用户ui和点击过的物品ti组成。
Si表示随机采样一些物料作为ui的负样本。（备注：batch内随机负采样吗？）

实际操作中，为了进一步简化，忽略公式中的-logQ修正项，拿原始的${u \cdot t}$表示用户与物品的匹配度，得到Negative Sampling Loss（NEG loss） $L_{NEG} = \frac{1}{B}\sum_{(u_i,t_i) \in B}[log(1 + exp(-u_i \cdot t_i)) + \sum_{j \in S_i} log(1 + exp(u_i \cdot t_j))]$

NEG的计算比NCE loss 更简单，但是它没有NCE loss那么强的理论保证。
可以证明，如果采样的负例足够多，NCE的梯度与原始超大规模softmax loss 的梯度趋于一致，NEG没有这种性质。
由于召回的目标不是为了将概率分布学习准确，而是为了学习高质量的用户向量和物品向量，实际召回场景中NEG仍然广泛应用。

2.4.2、sampled softmax loss

原始超大规模softmax需要估计整个物料库T中每个物料被u点击的概率。可以通过负采样缩小范围。

给定一个用户u和他点击的物料p（正样本），再给u按照Q（t｜u）的概率随机采样一批负样本S。

负采样后，变成了sampled softmax问题。即在候选集${C = {p} \cup S}$中，任意t被u点击的概率有多大，即建模P(t

u,C)。

通过推导，可得：

\[\begin{aligned} P(t|u,C) &= \frac{P(t|u)}{Q(t|u)} \times K(u,C) \\ logP(t|u,c) &= log(P(t|u)) - log(Q(t|u)) + logK(u,c) \end{aligned}\]

同样，用G（u，t）表示用户u在他的候选集C中点击物料t的logit，同时忽略常数项K，可得： $G(u,t) = logP(t|u,C) = u \cdot t - logQ(t|u)$

代入softmax公式中，得到：

\[\begin{aligned} L_{Sampledsoftmax} &= -\frac{1}{B}\sum_{(u_i,t_i)\in B}log\frac{exp(logit_i)}{\sum_j exp(logit_j)} \\ &= -\frac{1}{B}\sum_{(u_i,t_i)\in B}log\frac{exp(G(u_i,t_i))}{exp(G(u_i,t_i)) + \sum_{j \in S_i} exp(G(u_i,t_j))} \\ \end{aligned}\]

B: batch
ui：用户
ti：ui点击过的一个物料，正样本
Si：给ui采样生成的负样本集合
G(ui,ti)：ui点击ti的logit，注意其中的-logQ的修正项。
训练时有负采样概率的修正项，预测时直接计算 ${u_i \cdot ti}$

2.4.3、pairwise loss

pairwise loss是LTR的一种实现。仍以U2I为例：

一个样本是用户、正例、负例（可随机采样）组成的 三元组(${u_i, t_{i+}, t_{i-}}$)。
优化目标是，针对同一个用户u，正例t+与他的匹配度远远高于负例的匹配度。即 ${Sim(u, t+) » Sim(u,t-)}$。

一种表示远远高于的方法是marginal Hinge Loss： $L_{Hinge} = \frac{1}{|B|} \sum_{(u_i, t_{i+}, t_{i-}) \in B} max(0, m - u_i \cdot t_{i+} + u_i \cdot t_{i-})$

B：batch
ui、t+、t-分别是召回模型给u、t+、t-生成的向量表示。
m：阈值，margin，超参数。
loss函数要求，用户u与他点击过的t+的匹配度，要比一个随机采样的负例t-的匹配度，高出给定的阈值。

如果嫌调节参数m太麻烦，可以用Bayesian Personalized Ranking（BPR）loss。

BPR的思想是，给定一个用户u、正例t+、负例t-的三元组，针对用户ui的正确排序（将正例排在负例前面）的概率是(备注：logit为何是正例、负例之差？除法可以吗？)：

\[P_{CorrectOrder} = sigmoid(u_i \cdot t_{i+} - u_i \cdot t_{i-})\]

代入BCE交叉熵loss得到：

$\begin{aligned} L_{BPR} &= \frac{1}{|B|}\sum_{(u_i,t_{i+},t_{i-}) \in B} -log(P^{(i)}_{CorrectOrder}) \\ &= \frac{1}{|B|}\sum_{(u_i,t_{i+},t_{i-}) \in B} log(1 + exp(u_i \cdot t_{i-} - u_i \cdot t_{i+})) \end{aligned}$

B:batch。
样本：三元组。
label：正序对：1
BPRloss的优化目标：将正例排在负例前面的概率最大化。

本文总访问量次

上篇推荐算法实战-4-精排

下篇推荐算法实战-6-召回（2）-word2vec与双塔召回