召回综述与负样本构造

8/2/2021 召回综述召回负样本构造

# 假设物品库数量达到百万级别,如何设计方法从这个数量级别的物品中推荐给用户top10的物品,同时可以减少计算的压力?

在推荐系统的排序层,一般会使用复杂模型,利用多特征进行精准排序,而如果直接对百万量级的候选集进行逐一推断的话,则计算资源和延迟都是在线服务过程无法忍受的。

因此可以加入召回过程,利用少量的特征和简单的模型或规则进行候选集的快速筛选,减少精准排序阶段的时间开销。

# 推荐系统中为什么要有召回?在推荐系统中召回和排序有什么异同?

首先,在实际应用中,推荐算法往往是在线上使用,可用的设备资源和响应时间都是有限的。而整个物品集的规模往往十分庞大,在线上对大量物品进行排序是对性能的较大挑战,很难实现。召回可以视为一个粗排序的过程,这个过程的主要目的是在有限的资源条件下提供尽可能准确的一个小候选集,从而减轻排序阶段的计算负担和耗时。

其次,即使资源和时间足够对整个物品集进行扫描,先使用较为简单的方法进行召回往往也是比较有利的,先进行召回意味着可以排除大部分无关物品,从而允许在排序阶段对更小的候选集使用更多的特征和更复杂的模型,以提高排序的准确率。

召回层一般待计算的候选集合大、速度快、模型简单、特征较少,尽量让用户感兴趣的物品在这个阶段能够快速被召回,即保证相关物品的召回率。工业界主流的召回方式是采用多路召回策略,采用多个简单策略叠加的方式得到最终的召回结果。

排序层的首要目标是得到精准的排序结果,需处理的物品数量少,可利用多特征,使用比较复杂的模型。

# 排序为什么比召回更受关注?

排序

  • 排序,特别是精排,处于整个链条的最后一环,方便直接对业务指标发力。比如优化时长,只要排序模型里,样本加个权就可以了。
  • 排序由于候选集较小,所以有时间使用复杂模型,各种NN,各种Attention,能加的,都给它加上,逼格顿时高大上了许多。
  • 用于排序的基础设施更加完善,特征抽取、指标监控、线上服务都相对成熟。

召回

  • 一个系统中不可能只有一路召回,平日里相互竞争,召回结果重合度高,导致单路召回对大盘的影响有限;好处是,相互冗余,有几路出问题,也不至于让排序饿肚子。
  • 召回处于整体推荐链条的前端,其结果经过粗排、精排两次筛选,作用于最终业务指标时,影响力就大大减弱了。
  • 受限于巨大的候选集和实时性要求,召回模型的复杂度受限,不能上太复杂的模型。平日里,最简单的基于统计的策略,比如ItemCF/UserCF表现就很不错,改进的动力也不那么急迫。
  • 用于召回的基础设施不完善。比如,接下来,我们会提到,召回建模时,需要一些压根没有曝光过的样本。而线上很多数据流,设计时只考虑了排序的要求,线上的未曝光样本,线下不可能获取到。

# 召回模型有什么显著区别于排序模型的特点?

  • 特征选择上

召回面对的候选item是百万级、千万级,一般此类召回模型都是双塔型的,以便单独生成user embedding和item embedding,喂入的特征禁止含有user/item之间的交叉特征

  1. user特征喂入user tower得到user embedding,item特征喂入item tower得到item embedding。
  2. 离线时,先将item embedding喂入FAISS建立索引,
  3. 线上召回时,拿user embedding去FAISS里进行top-k近邻搜索,找到与其最接受的item embedding
  • 样本选择上
  1. 正样本没有太多的争议,以内容推荐为例,选“用户点击”的item为正样本。最多考虑一下用户停留时长,将“用户误点击”排除在外
  2. 负样本的选择比较有讲究。如果说排序是特征的艺术,那么召回就是(负)样本的艺术。
    • 原则之一就是不能(只)拿“曝光未点击”做负样本,负样本的绝大部分应该由“随机负采样”生成。
    • 原则之二就是要打压热门item
  • 损失函数上

因为绝大多数负样本是通过随机采样生成的,含有一定的噪声,因此召回不适合采用CTR预估常用的pointwise cross-entropy loss,而经常采用pairwise loss,比如margin-based bpr loss或hinge loss。

因此喂入模型的样本,区别于排序中常见的<user, item, label>,而是三元组<user, item+, item->,预测的目标是MatchScore(user, item+)要远高于MatchScore(user, item-)

# 推荐系统中有哪些场景是无法获得真负样本的?如何解决?

召回。召回的候选集一般是百万级、千万级,其中绝大多数item都从未给用户曝光过,虽然没有点击,但是你不能说用户就一定不喜欢。

个性化推送。App内部的推荐,我们可以根据埋点,比较容易获知用户滑过、忽略了某些推荐内容,所以比较有信心拿那些item作为负样本。但是在推送场景下,我们很难知道用户未点击的item是用户真的不喜欢,还是压根没看见(像我对于大多数推送,就是瞟了一眼桌面上的手机,这种“忽略”行为是无法埋点的)。所以,你也不能放心地将所有未点击的item都当负样本。

在这种无法获得“真负”样本的场景下,一般我们通过随机采样来获得负样本。但是,随机采样毕竟引入了噪声,这时,再用CTR预估这种要求“绝对准确性”的算法,就不合适了。所以,在召回或个性化推送场景下,我们一般采用Pairwise LearningToRank(LTR)建模排序的“相对准确性”。就好比,

  • 由于负样本中的噪声,让我预测user不喜欢item-的精确程度,我信心不足;

  • 但是由于item-是从库中几百万的item中抽样得到的,大概率和用户兴趣八杆子打不着,让我预测“user对item+,要比user对item-,喜欢得多一点”,信心更加充足一些。

# 为什么不能只拿"曝光未点击"做召回模型的负样本?

召回是将用户可能喜欢的item,和用户根本不感兴趣的海量item分离开来,他面临的数据环境相对于排序来说是鱼龙混杂的。

所以我们希望召回训练数据的正样本是user和item匹配度最高的那些样本,也即用户点击样本,负样本是user和item最不匹配的那些样本,但不能拿“曝光未点击”作为召回模型的负样本,因为我们从线上日志获得的训练样本,已经是上一版本的召回、粗排、精排替用户筛选过的,即已经是对用户“匹配度较高”的样本了,即推荐系统以为用户会喜欢他们,但用户的行为又表明的对他的嫌弃。拿这样的样本训练出来的模型做召回,并不能与线上环境的数据分布保持一致。也就是说曝光未点击既不能成为合格的正样本,也不能成为合格的负样本。

所以一般的做法是拿点击样本做正样本,拿随机采样做负样本,因为线上召回时,候选库里大多数的物料是与用户没有关系的,随机抽样能够很好地模拟这一分布。

# 召回模型是如何对负样本进行随机采样的?

首先,并非是在整个候选库进行等概率抽样,在任何一个推荐系统中,“八二定律”都是不可避免的,也就是少数热门物料占据了绝大多数的曝光与点击,这样一来,正样本被少数热门物料所绑架,导致所有人的召回结果都集中于少数热门物料,完全失去了个性化。

因此,当热门物料做正样本时,要降采样,减少对正样本集的绑架。 比如,某物料成为正样本的概率,其中是第i个物料的曝光或点击占比。

当热门物料做负样本时,要适当过采样,抵销热门物料对正样本集的绑架;同时,也要保证冷门物料在负样本集中有出现的机会。

比如,某物料成为负样本的概率。其中n(w)是第i个物料的出现次数,而一般取0.75

# 使用随机采样样本做负样本有什么缺陷?如何解决?

使用随机采样做负样本,也有其缺点,即与相比,与user太不匹配了。这样训练出来的模型,只能学到粗粒度上的差异,却无法感知到细微差别。所以需要挖掘Hard Negative增强样本。

一般我们把<user,item>的匹配度分成三个档次

  • 匹配度最高的,以用户点击样本为代表,此为正样本
  • 匹配度最低的,那是随机抽取的,可以被一眼就识别出来的,没什么难度,所谓的easy negative,达不到很好的锻炼模型的目的。
  • 匹配度适中的,能够增加模型在训练时的难度,让模型可以关注细节,就是所谓的hard negative.

如何选取hard negative,业界有不同的做法:

Airbnb在《Real-time Personalization using Embeddings for Search Ranking at Airbnb》一文中的做法,就是根据业务逻辑来选取hard negative

  • 增加与正样本同城的房间作为负样本,增强了正负样本在地域上的相似性,加大了模型的学习难度
  • 增加与正样本同城的房间作为负样本,增强了正负样本在地域上的相似性,加大了模型的学习难度

当业务逻辑没有那么明显的信号时,就只能依靠模型自己来挖掘。比如百度Mobius的作法,用上一版本的召回模型筛选出"没那么相似"的<user,doc>对,作为额外负样本,训练下一版本召回模型。

怎么定义“没那么相似”?文章中是拿召回位置在101~500上的物料。排名太靠前那是正样本,不能用;太靠后,与随机无异,也不能用;只能取中段。

上一个版本的召回模型作用于哪一个候选集上?分为online和offline两个版本。

online时就是一个batch中所有user与所有的cross join,这一点就与Mobius几乎一模一样了。

offline的时候,需要拿上一版本的召回模型过一遍历史数据,候选集太大,需要用到基于FAISS的ANN。

hard negative并非要替代easy negative,而是easy negative的补充。在数量上,负样本还是以easy negative为主,文章中经验是将比例维持在easy:hard=100:1。毕竟线上召回时,库里绝大多数的物料是与用户八杆子打不着的easy negative,保证easy negative的数量优势,才能hold住模型的及格线。

https://zhuanlan.zhihu.com/p/165064102

# 推荐系统召回是怎么实现热门item的打压?

任何一个推荐系统,都难逃“2-8”定律的影响,即20%的热门item占据了80%的曝光量或点击量。

因为三元组<user, item+, item->中item+来源于“用户点击过”的item,因此item+主要是热门item

  • 训练时,为了降低loss,算法会使每个user embedding尽可能接近少数热门item embedding
  • 预测时,每个user embedding从FAISS检索出来的邻居都是那少数几个热门item embedding,完全失去了个性化

由此可见,“打压热门item”的必要性。因为item出现的位置既可能是item+也可能是item-,因此打压热门item,也需要从这两方面入手,而采取截然不同的策略。

  • 生成item+时,打压高热item

目标是降低热门item成为item+的可能性。因此,item越热门,其成为item的概率就应该越低。

一个item""成为item+的概率

其中,

是一个超参,一般在之间

函数形状如下图所示 可见越高,item""成为item+的概率越低,从而实现了对热门item的打压 对于一些罕见item,按照以上公式计算出来的,说明罕见item只要被点击过,一定要当成正样本。

  • 生成item-时,打压高热item

目标是提升热门item成为item-的概率。可以从两个角度来理解

既然热门item已经绑架了item+,我们也需要提高热门item在item-中的比例,以抵消热门item对loss的影响

如果在采样生成item-时采取uniform sampling,因为有海量的候选item,而采样量有限,因此极有可能采样得到的item与user"八杆子打不着",即所谓的easy negative。而如果多采样一些热门item当item-,因为绝大多数用户都喜欢热门item,这样采集到的item-是所谓的hard negative,会极大地提升模型的分辨能力。

所以在随机采样负样本时,一方面需要采集到的item-能够尽可能地广泛覆盖所有候选item,另一方面又需要使采集到的item-尽量集中于高热item。

为了平衡这两方面的需求,我们定义负采样概率

是点击过第i个item的用户总数 b是一个调节因子 时,负采样完全按照item的热门程度进行,对热门item的打压最厉害,但是对所有候选item的覆盖度下降,导致训练数据环境与预测数据环境的gap增大,反而损害召回效果。

b=0时,负采样变成unform sampling,对所有候选item的覆盖度最高,减少了训练环境与预测数据环境的gap,但是对热门item的打压完全没有打压,采集到的tem-都是easy nagatve,召回效果会偏热门,个性化较差。

根据经验,b一般取0.75

https://www.zhihu.com/question/426543628/answer/1631702878

# 请简述基于embedding的召回方法,优势是什么?

在YouTube推荐系统中利用深度学习网络生成Embedding作为召回层的方法,再加上可使用局部敏感哈希进行快速的Embedding的召回方法在效果和速度上均不逊色于多路召回。

而且,多路召回中使用”兴趣标签“、”热门度“、”流行趋势“、”物品属性“等信息都可以作为Embedding召回方法中的附加信息(side information)融合进最终的Embedding向量中,就相当于在利用Embedding召回的过程中,考虑到了多路召回的多种策略。

Embedding召回的另一个优势在于评分的连续性,多路召回中不同召回策略产生的相似度、热度等分值并不具备可比性,无法据此决定每个召回策略放回候选集的大小,Embeddding召回可以把Embedding召回可以把Embedding间的相似度作为唯一的判断标准,因此可以随意限定召回的候选集大小。

# Airbnb召回算法中的listing embedding召回是如何选择正负样本的?

Airbnb召回算法源自于论文《Real-time Personalization using Embeddings for Search Ranking at Airbnb》,其中介绍了listing embedding和user/listing-type embedding两种召回算法。

  • listing embedding召回

listing就是Airbnb中的房源,所以基于listing embedding的召回,本质就是一个i2i召回。

对于正样本,本想照搬word2vec,将用户的点击序列看成一个句子,认为一个滑窗内的两个相邻listing是相似的,它们的embedding应该接近。

但是仔细想想,以上想法存在严重问题

  • word2vec建模的是语言模型的“共现性”,即哪些词语经常一起出现,因此需要一个滑动窗口限制距离
  • 而这里,我们建模的是listing之间的相似性,难道只有相邻listing之间存在相似性?一个点击序列首尾的两个listing就不相似了吗?

所以,理想情况下,一个序列中任意两个listing,它们的embedding都应该是相近的。但是在实践中发现,这样的组合太多,所以Airbnb还是退回到word2vec的老路,即还是只拿一个滑窗内的中心listing与邻居listing组成正样本对。但是由于“最终成功预订”的那个listing有最强的业务信号,所以我们拿它与点击序列中的每个listing组成正样本对。这也就是Airbnb论文中“增加final booked listing作为global context加入每个滑窗”的原因。

对于负样本,绝大部分的负样本是随机采样生成的,但是Airbnb发现,用户点击序列中的listing多是同城的,导致正样本多是同城listing组成,而随机采样的负样本多是异地的,这其中存在的bias容易让模型只关注“地域”这个粗粒度特征。

为此,Airbnb在全局随机采样生成的负样本之外,还在与中心listing同城的listing中随机采样一部分listing作为hard negative,以促使模型能够关注除“地域”外的更多其他细节。

# Airbnb召回算法中的user/listing-type embedding召回是如何选择正负样本的?

正样本构造:所谓的用user-type去召回listing-type,实际上就是u2i召回,Airbnb觉得预订行为太稀疏,所以将相似的user聚类成user-type,把相似的listing聚类成listing-type。与一般的u2i召回,别无二致。即,如果某user预订过某listing,那么该user所属的user-type,与该listing所属的listing-type就应该是相近的。

负样本构造:绝大部分负样本还是随机采样生成的。除此之外,增加“被owner拒绝”作为hard negative,表达一种非常强烈的“user~item不匹配”。

# Facebook的EBR算法是如何选择正负样本的?

来自于《Embedding-based Retrieval in Facebook Search》

正样本:使用的是u2i召回的典型思路,即user与其观看过的视频,在向量空间中是相近的。

负样本:绝大部分负样本依然是通过随机采样得到的。论文明确提出了,召回算法不应该拿“曝光未点击”做负样本。

本文最大的贡献是提供了两种挑选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
    • 拿增强后的负样本,训练下一版召回模型。

# 召回为什么要求具有隔离user与item特征的解耦性?具体怎么解耦?

召回需要面对的是百万、千万级别的海量候选item,如果让每个user与每个候选item都计算交叉统计特征,都过一遍DNN那样的复杂操作,是无法满足线上的实时性要求的。

在特征上,尽管交叉特征的信号很强,但是召回不允许使用“交叉统计特征”。

在模型上,禁止user feature与item feature出现DNN那样的多层交叉,二者必须独立发展,i.e., user子模型,利用user特征,生成user embedding;item子模型,利用item特征,生成item embedding。唯一一次user与item的交叉,只允许出现在最后拿user embedding与item embedding做点积计算匹配得分的时候。

只有这样,才能允许我们

  • 离线时,在user未知的情况下,独立生成item embedding灌入faiss;
  • 在线时,能独立生成user embedding,避免与每个候选item进行“计算交叉特征”和“通过DNN”这样复杂耗时的操作

# 在召回场景下,为什么往往采用Pairwise LearningToRank来构建排序的相对准确性?

排序阶段经常遵循"CTR预估"的方式

  • 样本上,是两条样本
  • loss上使用binary cross-entropy这样的pointwise loss

能够这么做的前提是,其中的是“曝光过但未点击”的“真负”样本,label的准确性允许我们使用pointwise loss追求“绝对准确性”。

但是在召回场景下,以上前提并不成立。以常见的u2i召回为例,绝大多数item从未给user曝光过,我们再从中随机采样一部分作为负样本,这个negative label是存在噪声的。在这种情况下,再照搬排序使用binary cross-entropy loss追求“预估值”与“label”之间的“绝对准确性”,就有点强人所难了。所以,召回算法往往采用Pairwise LearningToRank(LTR),建模“排序的相对准确性”:

# 优化召回Pairwise LearningToRank使用的损失函数可以有哪几种形式?

召回中的样本往往是的三元组形式

模型的优化目标是,针对同一个user,与他的匹配程度,要远远高于,与他的匹配程度。所以Loss中没有label,而存在的匹配分与的匹配分相互比较的形式。

为了实现Pairwise LTR,有几种Loss可供选择。

一种是sampled softmax loss。

这种loss将召回看成一个超大规模的多分类问题,优化的目标是使,user选中item+的概率最高。

user选中item+的概率=,其中是user embeddding,代表item embedding,代表item候选集。

为使以上概率达到最大,要求分子,即user与item+的匹配度尽可能大;而分母,即user与除了item+之外得的item的匹配度之和,尽可能小。体现出上文所说的“不与label比较,而是匹配得分相互比较”的特点。

但是,由于计算牵扯到整个候选item集合,计算量大到不现实。所以实际有花的是sampled softmax loss,即从中随机采样若干,近似替代计算完整的分母。

另一种loss是margin hinge loss,

优化目标是:user与正样本item的匹配程度,要比,user与负样本item的匹配程度,高出一定的阈值。

因为margin hinge loss多出一个超参margin需要调节,因此主要使用如下的BPR Loss。

其思想是计算"给user召回时,将item+排在item-前面的概率",

因为<user, item+, item->的ground-truth label永远是1,所以将喂入binary cross-entropy loss的公式,就有

# 如何评估召回的效果?

最好肯定是线上ab,但是ps资源和线上流量都有限,以下是一些离线评估召回方法:

  • 首先auc高并不代表召回的好,实际上好的召回可能auc低一些,但是会召回出更符合真实分布的内容,实际工作中auc当作参考就好。
  • 拿Top K召回结果与用户实际点击做交集并计算precision/recall,感觉现在大多都是用的这个方法,但是我总感觉极端条件下N路召回全都100%准确率召回率,那其实5路变成1路就好了,而且完全在拟合精排,又陷入了无探索的困境,因为召回的结果未被用户点击,未必说明用户不喜欢,而可能是由于该召回结果压根没有给用户曝光过。
  • 召回diff率。其实我现在还比较喜欢拿这个来预估要不要上线,因为diff高才有bagging一路召回的价值(当然还有是否保送,精排是否能排出来的问题)
  • 人肉debug:最近搞了一个模型,自己经常会拿组里同学的uid来打印召回结果,然后人肉评估一下靠不靠谱。虽然有点蠢,但是确实能帮我验证模型/机制做没做对,也能有个摸底的效果。

# 为什么Word2Vec训练中, 需要对负采样权重开3/4次幂?

https://zhuanlan.zhihu.com/p/144563199