Embedding-based Retrieval in Facebook Search：解读Facebook搜索中的召回技术

许久不见甚是想念，自从工作后就没有更新过博客，难得今天抽空把前两天看的一篇 Facebook 发表在 KDD2020 的一篇关于社交网络搜索中的 embedding 检索问题的工作来分享一下，干货很多，尤其是负样本的选取真的是切中痛点，推荐一读。

参考文献：

1. https://arxiv.org/pdf/2006.11632.pdf

2.https://mp.weixin.qq.com/s/VJSDSHW3CsY3b5Xx90FO2A

3.https://mp.weixin.qq.com/s/VJSDSHW3CsY3b5Xx90FO2A

摘要

与传统的网络搜索相比，诸如Facebook之类的社交网络中的搜索面临着不同的挑战：除了查询文本外，重要的是要考虑搜索者的上下文以提供相关结果。他们的社交图谱是上下文的组成部分，也是Facebook搜索的独特方面。尽管基于嵌入的检索（EBR）已在Web搜索引擎中应用了很多年，但Facebook搜索仍主要基于布尔匹配模型。在本文中，我们讨论了将EBR应用到Facebook搜索系统的技术。文中共介绍了三方面的经验：

1. 提出了一套统一的 embedding 框架用于建模个性化搜索中的语义。

2. 提出了基于经典的倒排索引进行在线 embedding 检索的系统。

3. 讨论了整个个性化搜索系统中很多端对端的优化技巧，例如最近邻搜索调参经验、全链路优化等。

最后，在Facebook 垂直搜索场景下验证了本文方法的有效性，在线上 A/B 实验取得了显著的收益。

简介

从 query 中准确计算出用户的搜索意图以及准确表征文档的语义是非常困难的。之前的搜索算法主要还是通过关键词匹配的方式进行检索，但是对于字面不匹配但是语义相似的 case 基于关键词匹配的方法就不奏效了。而通过 embedding 可以建模句子之间的语义相似度，所以基于 embedding 的语义检索就应运而生了。

所谓 embedding 就是将高维稀疏的 id 映射成为一个低维稠密的向量，这样就可以在同一个向量空间中同时表示query 和候选集文档，从而进行譬如计算相似度等方面的操作。

一般来说，搜索主要包含检索和排序两个阶段。尽管 embedding 技术可以同时被应用在两个阶段，但相对来说应用在召回阶段可以发挥出更大的作用。简单来说，EBR 就是用 embedding 来表示 query 和 doc，然后将检索问题转化为一个在 Embedding 空间的最近邻搜索的问题。它要解决的问题是如何从千万个候选集中找到最相关的 topK 个，难点有如下的两个：一方面是如何构建千万级别的超大规模索引以及如何在线上进行服务；另一方面是如何在召回阶段同时考虑语义信息和关键词匹配信息。

一般而言，搜索引擎包括：召回层，旨在以低延迟和低计算量来检索一组相关文档（通常称为“检索(retrieval)”）；以及精排层，其目标是通过更复杂的算法或模型将最想要的文档排在最前面，通常称为"排序(ranking)"。尽管可以将emebdding应用于这两个层，但是但相对来说应用在召回阶段可以发挥出更大的作用，因为它位于系统的底部，通常是瓶颈所在。简单来说，EBR 就是用 embedding 来表示 query 和 doc，然后将检索问题转化为一个在 Embedding 空间的最近邻搜索的问题。它要解决的问题是如何从千万个候选集中找到最相关的 topK 个，难点有如下的两个：一方面是如何构建千万级别的超大规模索引以及如何在线上进行服务；其次，搜索引擎通常需要将基于嵌入的检索和基于关键词匹配的检索结合在一起，以对检索层中的文档进行评分。

本文从三个方面详细讲述了在 Facebook 搜索中应用 Embedding 检索技术遇到的挑战：

• modeling: 本文提出了一套统一的 Embedding 模型框架 ，也就是经典的双塔结构，一侧是抽取用户侧 query 特征；另一侧则是抽取 document 侧的特征。

• serving: 为了优化系统检索和排序的综合效果，Facebook 提出了将 EBR 的 embedding 和布尔匹配项集成在一起作为特征整合进 ranking 模型中以对文档进行评分以进行检索。为此，我们使用Faiss库嵌入矢量量化，并将其与基于倒排索引的检索相集成，以构建一个混合检索系统，以便更好地识别和利用 EBR 的召回结果。

• full-stack optimization: 针对实际的搜索效果优化提出了多个实用的 tricks。

模型

本文将搜索引擎中的检索任务建模为一个召回优化问题。从离线指标的角度，我们希望最大化 topK 返回结果的recall 指标。给定一个 query，以及期望被检索到的目标文档集合 T，T 中包含的文档可以来自用户的点击数据，也可以是经过人工筛选排序后的文档，我们的优化目标则是 [email protected]。

 

继而我们把召回优化问题建模成 query 和 doc 之间基于距离的排序问题，把 query 和 doc 同时表示成低维稠密的向量，通过计算向量空间中的距离衡量它们之间的相似度或相关度，本文中我们采用 cosine 距离。

但是在 Facebook 个性化检索场景下，仅仅计算 query 本身与候选文档的相似性是远远不够的，我们同时要考虑用户的上下文信息，比如他关注的人，他的关注话题等等，才能帮用户找到他真实的最想要的结果。为了实现这个目标，本文提出了统一嵌入模型，即Unified Embedding Model。

Unified Embedding Model的思路相对来说比较简单，沿用了经典的双塔结构，包括三个部分：query encoder，document encoder 以及 similarity function。两个encoder是互相独立的，也可以共享一部分网络参数，左边是 user 的塔；右边是 document 的塔，但是 Unified Embedding Model 的 encoder 的输入是和传统的输入不同的，user 塔的输入包括用户的检索 query，以及用户位置、用户社交关系等上下文特征，document 塔的输入包括文档本身，以及文档的 group 信息等上下文特征，模型结构详见下图所示。其中大部分的特征都是类别型特征，进行 one-hot 或者 multi-hot 的向量化；连续型特征则是直接输入到各自的塔中。

 

在模型训练的损失函数上，本文定义了一个三元组损失函数，使得负例比正例相对 query 的距离尽可能的远。在使用三元组损失函数的情况下，使用随机采样的负样本可以近似求解召回优化问题。

 

D(u,v)指两个向量间的距离衡量，m是正负对之间强制执行的边距值。该损失函数的直觉是将正对与负对分开一定距离，即同一个用户与“正文章”（点击过的文章）的匹配度<u,d+>，要比用户与“负文章”（怎么选择负文章就是召回的关键）的匹配度<u,d->高于一定的阈值。我们发现调整边距值很重要——最佳边距值在不同的训练任务中变化很大，并且不同的边距值会导致5-10％的KNN召回差异。

我们认为，使用随机样本为三元组损失形成负对可以近似于召回优化任务。 原因如下。 如果我们为训练数据中的每个阳性样本采样n个阴性样本，那么当候选库大小为n时，该模型将针对上一个位置的召回进行优化。 假设实际的服务候选池大小为N，我们大约在顶部K≈N / n处优化召回率。 在第2.4节中，我们将验证该假设，并提供不同正负标签定义的比较。

训练数据挖掘

这里是本文的关键知识所在，详细说明了推荐系统召回过程的一大痛点！本文最精彩的部分就是对样本的筛选。如果说排序是特征的艺术，那么召回就是样本的艺术，特别是负样本的艺术。样本选择错了，那么上述的模型设计、特征工程，只能是南辕北辙，做得越卖力，错得越离谱。本文在“样本筛选”上的贡献有三：

• 破除“召回照搬排序”的迷信，明确指出，不能（只）拿“曝光未点击”做负样本

• 提出了easy negative/hard negative的样本分级思路

• 提出了增强hard negative的思路（也不算首创了，和百度Mobius的思路几乎一模一样，也算英雄所见略同了）

本文的另外两个贡献也算是“样本筛选”的引申：

• 全链路优化中提出将召回结果交给人工审核，不过是增强hard negative的一个手段

• 多模型整合，也算是hard negative除了“增强样本”之外的另一种利用方式。而且不同模型也是按照negative samples的难度来分级的

本文中作者使用用户点击的样本作为正样本，分别拿随机采样的样本与曝光未点击的样本作为负样本训练，发现曝光未点击负样本训练的模型比随机采样负样本训练出来的模型差了“absolute 55% regression in recall for people embedding model”！那么为什么不能（只）拿"曝光未点击"做负样本，因为这违反了机器学习的一条基本原则，就是离线训练数据的分布，应该与线上实际应用的数据，保持一致。召回是“是将用户可能喜欢的，和海量对用户根本不靠谱的，分隔开”，所以召回在线上所面对的数据环境，就是鱼龙混杂、良莠不齐。所以，要求喂入召回模型的样本，既要让模型见过最匹配的<user,doc>，也要让模型见过最不靠谱的<user,doc>，才能让模型达到"开眼界、见世面"的目的，从而在“大是大非”上不犯错误。所以文章中描述的基本版本就是拿点击样本做正样本，拿随机采样做负样本。因为线上召回时，候选库里大多数的物料是与用户八杆子打不着的，随机抽样能够很好地模拟这一分布。

但是文章中没有说明随机抽样的概率，千万不要以为是在整个候选库里等概率抽样。

• 在任何一个推荐系统中，“八二定律”都是不可避免的，也就是少数热门物料占据了绝大多数的曝光与点击

• 这样一来，正样本被少数热门物料所绑架，导致所有人的召回结果都集中于少数热门物料，完全失去了个性化。

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

• • 

• 当热门物料做负样本时，要适当过采样，抵销热门物料对正样本集的绑架；同时，也要保证冷门物料在负样本集中有出现的机会。比如，某物料成为负样本的概率如下，其中n(w)是第i个物料的出现次数，而一般取0.75

• • 

NLP背景的同学看以上两个采样公式是不是有点眼熟？没错，它们就是word2vec中所采用的采样公式。没错，word2vec也可以看成一个召回问题，由center word在整个词典中召回context word。

但是，使用随机采样做负样本，也有其缺点，即与d+相比，d-与user太不匹配了。这样训练出来的模型，只能学到粗粒度上的差异，却无法感知到细微差别。就好比，一个推荐宠物的算法，能够正确做到向爱狗人士推荐狗，向爱猫人士推荐猫，但是在推荐狗的时候，无法精确感受到用户偏好上的细微差别，将各个犬种一视同仁地推出去。这样的推荐算法，用户也不会买账。

特征工程

Unified Embedding Model 架构的一个最明显的优势是可以任意加入各种各样的上下文特征。我们都知道 Facebook 推出的工业界实战论文都比较注重特征工程，Unified Embedding 大体上采用了如下三个方面的特征：

• Text features

Text Embedding 采用 char n-gram，相对于 word n-gram 有两方面的优势，一是有限的词典，char embedding table 会比较小，训练更高效；二是不会有 OOV 问题，subword 可以有效解决拼写错误以及单词的多种变体引入的 OOV 问题。

• Location features

位置特征对于搜索引擎的很多场景是非常重要的，因此本文在 query 和 document 侧的都加入了 location 的特征。

• Social Embedding features

为了有效利用 Facebook 社交网络中的丰富信息，本文额外地训练了一个社交网络的 Graph Embedding，然后将这个预训练的 Embedding 作为特征输入到模型当中。

在线Serving

前面的章节讲如何进行离线建模以及特征工程，这一节主要讲如何进行在线实时检索，Facebook 采用了自家的 Faiss 库进行线上近似最近邻搜索（approximate nearest neighbor search， ANN）。具体地，他们在实际系统中部署了一套基于倒排索引的 ANN 搜索算法，首先，利用自家的 Faiss 库创建向量索引，然后对索引表进行高效的最近邻检索。对 embedding 进行量化可以有效节省存储开销，同时可以方便地集成到现有的检索系统当中。

一个 query 可以表示为基于 term 的布尔表达式，譬如 john 和 smithe 住在 seattle 或者 menlo_park 可以用下面的布尔表达式来表示。在实际使用中，在 document 的布尔表示基础上，加上了 document embedding 的索引。

Embedding model 离线训练完成后通过 spark 构建候选文档集 document 的索引，当用户请求过来时，query 的 embedding 在线计算，进行 topK 召回。针对全量的候选文档集进行索引是非常耗存储和费时的，所以本文在构建索引的时候，只选择了月活用户，近期事件，热门的事件，以及热门 group。大部分公司在构建索引的时候也都会采取这样的策略，很多长时间不活跃的可以不构建索引。

Full-stack优化

Facebook 的搜索引擎可以看作是一个复杂的多阶段的排序系统，检索是排序之前的流程，检索得到的结果需要经过排序层的过滤和 ranking，我们可以将检索过程召回的分数（也就是向量的相似度）作为 ranking 阶段的一个特征，通过 ranking 模型进行统一排序。由于现有的排序算法是基于已有的检索算法的特点设计的，所以对于基于 embedding 召回的结果自然是被次优处理的，为了解决这个问题，作者提出了两个方法：

• Embedding as ranking feature: 将检索这一步骤得到的 embedding similarity 作为接下来排序的输入特征，实验证明余弦相似度的效果要优于其他相似度特征。

• Training data feedback loop: 基于 embedding 的语义召回的结果存在召回高但是精度低的问题，所以本文就采用了对召回结果进行人工标注的方法，对每个query召回的结果进行标注，区分相关结果和不相关结果，然后用标注后的数据重新训练模型，从而提升模型精度。（人工大法好）

基于 embedding 的语义召回模型需要更加深入的分析才能不断提升性能，Facebook 给出了其中可以提升的重要方向一个是 Hard Mining，另一个是 Embedding Ensemble。具体地有以下几个方法：

Hard Negative Mining(重要)

将的匹配度分成三个档次

• 匹配度最高的，是以用户点击为代表的，那是正样本。

• 匹配度最低的，那是随机抽取的。能被一眼看穿，没难度，所谓的easy negative，达不到锻炼模型的目的。

• 所以要选取一部分匹配度适中的，能够增加模型在训练时的难度，让模型能够关注细节，这就是所谓的hard negative。

本文与百度Mobius的作法，二者的作法极其相似，都是用上一版本的召回模型筛选出没那么相似的对，作为额外负样本，训练下一版本召回模型。怎么定义“没那么相似”？文章中是拿召回位置在101~500上的物料。排名太靠前那是正样本，不能用；太靠后，与随机无异，也不能用；只能取中段。

Online hard negative mining 模型是采用mini-batch的方式进行参数更新的，对batch中每个positive pair (q_i, d_i)，利用除 d_i 以外的其他正例文档组成一个文档集，从中选择最相近的文档作为困难负例 hard negative sample，通过这种方式构造的三元组数据 可以使模型效果提升非常明显，同时也注意到了每个 positive pair，最多只能有两个 hard negative sample，不然模型的效果会下降。

Offline hard negative mining 首先针对每个 query 召回 topK 个结果；然后选择一些 hard negative samples 进行重新训练，重复整个过程。需要拿上一版本的召回模型过一遍历史数据，候选集太大，需要用到基于FAISS的ANN。

不过需要特别强调的是，hard negative并非要替代easy negative，而是easy negative的补充。在数量上，负样本还是以easy negative为主，文章中经验是将比例维持在easy:hard=100:1。

Hard positive mining 模型采用了用户点击的样本为正样本，这一部分样本是现有系统已经可以召回的相对简单样本，但是还有一些用户未点击但是也能被认为是正样本的样本。作者从用户日志中挖掘出潜在的困难正样本（具体如何挖掘文章没有提及），发现训练数据量只有原来 4% 的情况下可以得到和原来相近的召回率，如果把这些困难正例和用户点击数据一起训练说不定有更好的效果。

Embedding Ensemble 简单样本和困难样本对训练 EBR 模型都很重要，简单样本可以让模型快速学习到数据分布特点，困难样本可以提升模型的 precision，所以采用不同难度的正负样本训练出来的模型各有优势，如何对这些模型进行融合以提升性能呢？第一种方案是 Weighted Concatenation，通过对不同模型计算的相似度 score 进行加权平均作为最终相似度值，采用加权融合的模型对于单模型而言有 4.39% 的提升。第二种方案是 Cascade Mode，模型以串行方式在第一阶段模型的输出上运行第二阶段模型。采用串行的方式，模型也有 3.4% 的提升。