一、Facebook EBR [2020]

《Embedding-based Retrieval in Facebook Search》

1. 搜索引擎已经成为帮助人们在线获取海量信息的重要工具。在过去的几十年里，已经开发了各种技术来提高搜索质量，特别是在包括 Bing 和 Google 在内的互联网搜索引擎中。由于很难从query 文本中准确地计算搜索意图（search intent），也很难表达文档（document）的语义（semantic meaning），因此搜索技术大多数基于各种term 匹配技术，这对于关键词（keyword）匹配可以解决的情况表现良好。

   语义匹配仍然是一个具有挑战性的问题：需要解决与query 文本不完全匹配、但是能够满足用户搜索意图的预期结果（desired result）。

   在过去几年中，深度学习在语音识别、计算机视觉、自然语言理解方面取得了重大进展。其中 embedding（也被称作representation learning）已被证明是有助于成功的技术。本质上，embedding 是将 id 的稀疏向量表示为稠密特征向量的一种方式，这种方式也被称作语义 embedding (semantic embedding )，因为它通常可以学习语义（semantics）。一旦学到了 embedding，就可以将其用作query 和文档的representation，从而应用于搜索引擎的各个阶段（stages）。由于该技术在包括计算机视觉和推荐系统在内的其它领域获得巨大成功，因此作为下一代搜索技术，它已经成为信息检索（information retrieval）社区和搜索引擎行业（search engine industry）的一个活跃研究课题。

   一般而言，搜索引擎包括：

   • 召回层（recall layer）：旨在以低延迟（low latency）和低计算量（low computational cost ）来检索一组相关（relevant）的文档。这也被称作检索（retrieval）。

   • 精确层（precision layer）：旨在以更复杂的算法或模型将最想要的文档排在最前面。这也被称作排序（ranking）。

   尽管可以将embedding 应用于检索和排序，但是通常更多地利用检索层中的 emebdding，因为检索层位于系统的底部，并且通常是系统的瓶颈。embedding 在检索中的应用称作基于 embedding 的检索（embedding-based retrieval: EBR）。简而言之，EBR 是一种使用 embedding 来表示query 和文档，然后将检索问题转换为 embedding 空间中的最近邻（nearest neighbor: NN）搜索问题的技术。

   • 由于要考虑的数据规模巨大，因此 EBR 在搜索引擎中是一个具有挑战性的问题。不同于通常每个session 仅考虑数百个文档的排序层，检索层需要在搜索引擎的索引中处理数十亿或者数万亿个文档。巨大的规模对于 embedding 的训练以及 embedding 的serving 提出了挑战。

   • 其次，与计算机视觉任务中基于embedding 的检索不同，搜索引擎通常需要将基于embedding 的检索和基于 term 匹配的检索（term matching based retrieval）结合起来，从而在检索层中对文档进行评分。

   Facebook 搜索作为一个社交搜索引擎，它与传统搜索引擎相比有着独特的挑战。在 Facebook 搜索中，搜索意图不仅取决于query 文本，而且还受到发出query 的用户、以及该用户所处上下文的严重影响。例如，searcher 的社交图（social graph）就是上下文的组成部分，并且是 Facebook 搜索的一个特有方面（unique aspect）。因此，正如信息检索社区（IR community）中积极研究的那样，在 Facebook 搜索中基于 embedding 的检索不是文本embedding 问题。相反，它是一个更复杂的问题，需要完全理解文本、用户、以及上下文。

   为了在 Facebook 搜索中部署EBR，论文 《Embedding-based Retrieval in Facebook Search》开发了一些方法来解决建模（modeling）、serving、和全栈（full-stack）优化方面的挑战。

   • 在建模中，我们提出了统一嵌入（unified embedding）的方法。该模型是一种two side 模型，其中一个side 是包含query 文本、搜索用户（searcher） 、上下文的搜索请求（search request），另一个side 是文档。

     为了有效地训练模型，我们开发了从搜索日志中挖掘训练数据，并从搜索用户、query、上下文和文档中抽取特征的方法。为了快速进行模型迭代，我们在离线评估集合中采用召回（recall）指标来比较模型。

     为搜索引擎构建检索模型有着独特的挑战，例如如何为模型构建具有代表性（representative）的训练任务，以使其有效（effectively）和高效（efficiently）地学习。我们研究了两个不同的方向：

     • hard mining 以解决有效地（effectively）表示（representing）和学习（learning）检索任务。

     • ensemble embedding 以将模型划分为多个阶段（stage），其中每个阶段都有不同的召回率（recall）和精度（precision）的 tradeoff 。

   • 在模型开发完成之后，我们需要开发一些方法来高效（efficiently）、有效（effectively）地 serve 检索stack 中的模型。虽然构建一个结合现有检索(即基于 term 匹配的检索)和embedding KNN 的系统很简单，但是由于以下几个原因，我们发现这是次优（suboptimal）的：

     • 从我们最初的实验来看，它具有巨大的性能代价（performance cost）（延迟方面）。

     • 双套索引（即一套为基于 term matching 、一套基于embedding ）导致维护成本较高。

     • 现有检索的候选 item 和 embedding kNN 的候选 item 可能有很大的重叠，这使得整体效率较低。

     因此，我们开发了一种混合检索框架（hybrid retrieval framework），将embedding KNN 和布尔匹配（Boolean Matching）集成（integrate）在一起，从而对文档打分以进行检索。为此，我们使用 Faiss 库来用于 embedding 向量的量化（quantization），并将其与基于倒排索引（inverted index based）的检索相集成，从而构建一个混合检索系统（hybrid retrieval system）。除了解决上述挑战之外，该系统还具有两个主要优点：

     • 它可以实现 embedding 和 term matching 的联合优化，从而解决搜索的检索问题。

     • 它支持受 term matching 约束的 embedding KNN ，这不仅有助于解决系统性能代价（system performance cost）问题，而且还提升了 embedding KNN 结果的 precision 。

   • 搜索是一个多阶段的排序系统（multi-stage ranking system），其中检索是第一阶段，然后是排序模型（ranking models）和过滤模型（ filtering models）等各阶段。为了全局优化系统以最终返回那些新的好结果（new good results）并抑制新的坏结果（new bad results），我们执行了后期优化（later-stage optimization）。具体而言，我们将 embedding 融合到排序层中，并建立了训练数据的反馈循环（feedback loop），从而主动学习识别 EBR 中好的结果和坏的结果。下图中给出了 EBR 系统的说明。

     

   我们使用在线 A/B test 对 Facebook Search 的垂直领域（verticals）评估了 EBR ，并观察到显著的指标增长。我们相信本文将提供有用的洞察和经验，从而帮助人们开发搜索引擎中基于embedding 的检索系统。

   注：搜索的垂直领域（verticals）指的是哪种类型的搜索，比如搜索某个人（people）、某个页面（page）、某个群组（group ）等。

1.1 模型

1. 我们将搜索的检索任务形式化为召回优化（recall optimization）问题。具体而言，给定一个搜索query 以及target 结果集合 $\mathbb{T}=\{t_1,\cdots ,t_{N_t}\}$$\mathbb T=\{t_1,\cdots,t_{N_t}\}$ ，我们的目标是模型返回的top-K 结果 $\{d_1,\cdots ,d_K\}$$\left\{d_1,\cdots,d_K\right\}$ 的 recall 召回率最大化：

   $$\text{recall@}K=\frac{\sum _{i=1}^K{d}_i\in \mathbb{T}}{N_t}$$

   其中：target 结果是基于某些准则（criteria）下的、与给定query 相关的文档（即label ）。例如，它可能是用户点击的结果，或者是基于人类评分得到的相关的文档。$N_t$$N_t$ 为 target 结果集合的规模。

2. 我们将召回优化问题形式化为：基于 query 和文档之间计算的距离的排序问题（ranking problem）。query 和文档被神经网络模型编码为稠密向量（dense vector），在此基础上我们使用余弦相似度作为距离度量。

   我们提出使用 triplet loss 来逼近召回目标函数（recall objective），从而学习神经网络编码器（也被称作embedding 模型）。

3. 尽管语义 embedding （ semantic embedding ）通常被表述为信息检索中的文本 embedding 问题，但是对于 Facebook 搜索而言这是不够的。Facebook 搜索是一种个性化的搜索引擎，它不仅考虑文本query，而且还考虑searcher 的信息以及搜索任务中的上下文，从而满足用户的个性化信息需求。以人物搜索（people search）为例，虽然Facebook 可能有成千上万个名为 John Smith 的用户资料，但是用户通过query "John Smith" 搜索的实际目标人物可能是他们的朋友或熟人。

   为了对这个问题进行建模，我们提出了unified embedding ，该embedding 不仅考虑了文本、还考虑用户和上下文信息。

1.1.1 评估指标

1. 虽然我们的最终目标是通过在线 A/B test 实现端到端的质量提升，但重要的是开发离线指标，以便在在线实验之前快速评估模型质量，并从复杂的在线实验配置中隔离（isolate）问题。

   我们提出在整个索引中运行 KNN 搜索，然后使用 $\text{recall@}K=\frac{\sum _{i=1}^K{d}_i\in \mathbb{T}}{N}$$\text{recall@}K = \frac{\sum_{i=1}^Kd_i\in \mathbb T}{N}$ 作为模型评估指标。具体而言，我们采样了 10000 个搜索session 从而收集评估集合的 query 和target result 的 pair 对。然后我们报告这 10000 个搜索 session 的平均 recall@K 指标。

1.1.2 损失函数

1. 给定一个三元组 $({\overrightarrow{\mathbf{q}}}^{(i)},{\overrightarrow{\mathbf{d}}}_{+}^{(i)},{\overrightarrow{\mathbf{d}}}_{-}^{(i)})$$\left(\mathbf{\vec q}^{(i)},\mathbf{\vec d}_+^{(i)},\mathbf{\vec d}_-^{(i)}\right)$ ，其中 ${\overrightarrow{\mathbf{q}}}^{(i)}$$\mathbf{\vec q} ^{(i)}$ 是一个query的 representation，${\overrightarrow{\mathbf{d}}}_{+}^{(i)}$$\mathbf{\vec d}_ +^{(i)}$ 为对应的positive 文档的 representation、${\overrightarrow{\mathbf{d}}}_{-}^{(-)}$$\mathbf{\vec d}_-^{(-)}$ 为对应的negative 文档的 representation。triplet loss 定义为：

   $$\mathcal{L}=\sum _{i=1}^{N}max(0,f_d({\overrightarrow{\mathbf{q}}}^{(i)},{\overrightarrow{\mathbf{d}}}_{+}^{(i)})-f_d({\overrightarrow{\mathbf{q}}}^{(i)},{\overrightarrow{\mathbf{d}}}_{-}^{(i)})+m)$$

   其中：

   • $f_d(\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}})$$f_d\left(\mathbf{\vec u},\mathbf{\vec v}\right)$ 为两个向量 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 和 $\overrightarrow{\mathbf{v}}$$\mathbf{\vec v}$ 之间的距离。

   • $m\ge 0$$m\ge 0$ 为margin 超参数，它是正pair 对和负 pair 对之间的边距（margin）。

   • $N$$N$ 为训练集中所有的 triplet 数量。

   这个损失函数的直觉是：将正pair 对和负 pair 对分开一段距离（由 $m$$m$ 超参数指定）。

2. 我们发现调整 margin 值 $m$$m$ 非常重要：最佳 $m$$m$ 值在不同训练任务中变化很大，不同的 $m$$m$ 值会导致 5 ~ 10% 的 KNN recall 方差。

3. 我们认为，使用随机样本形成负pair 对的 triplet loss 可以逼近召回优化任务。 理由如下：

   • 如果我们为训练数据中每个postive 样本随机采样 $n-1$$n-1$ 个 negative 样本，那么当候选池（candidate pool ）大小为 $n$$n$ 时，模型将优化最头部位置的 top-1 召回。

     候选池为 n，假设池子中每个样本都是随机选择的，则候选池中有 1 个 positive 样本。

   • 假设实际 serving 的候选池大小为 $N$$N$ ，我们将优化最前面的 $K\simeq \frac{N}{n}$$K\simeq \frac{N}{n}$ 位置的 top-K 召回。

     候选池为 N，假设池子中每个样本都是随机选择的，则候选池中有 $N/n$$N/n$ 个 postive 样本。

   在后续我们将验证该假设，并提供不同正、负标签定义的比较。

1.1.3 Unified Embedding Model

1. 为了从优化triples loss 中学习embedding，我们的模型包括三个主要组件：

   • 一个 query encoder $\overrightarrow{\mathbf{q}}=f(Q)$$\mathbf{\vec q}=f(Q)$ ， 它用于根据 query $Q$$Q$ 产生query embedding 。

   • 一个 document encoder $\overrightarrow{\mathbf{d}}=g(D)$$\mathbf{\vec d}=g(D)$ ，它用于根据文档 D 产生 文档 embedding 。

   • 一个相似度函数（similarity function） $S(\overrightarrow{\mathbf{q}},\overrightarrow{\mathbf{d}})$$S\left(\mathbf{\vec q},\mathbf{\vec d}\right)$，它用于产生 query $Q$$Q$ 和文档 $D$$D$ 之间的得分score 。

   下图给出了我们的unified embedding 模型架构，其中有关特征工程将在后续讨论。

   

2. 编码器（encoder）是一种神经网络，可以将输入转换为低维稠密向量，也称作 embedding 。在我们的模型中，这两个编码器 $f(\cdot ),g(\cdot )$$f(\cdot), g(\cdot)$ 默认是两个独立的网络，但是可以选择共享部分参数。

3. 对于相似度函数，我们选择余弦相似度，因为它是 embedding 学习中常用的方法之一：

   $$S(\overrightarrow{\mathbf{q}},\overrightarrow{\mathbf{d}})=\cos (\overrightarrow{\mathbf{q}},\overrightarrow{\mathbf{d}})=\frac{\overrightarrow{\mathbf{q}}\cdot \overrightarrow{\mathbf{d}}}{\Vert \overrightarrow{\mathbf{q}}\Vert \times \parallel \overrightarrow{\mathbf{d}}\parallel }$$

   因此在 triplet loss 函数中定义的距离函数为：

   $$f_d(\overrightarrow{\mathbf{q}},\overrightarrow{\mathbf{d}})=1-\cos (\overrightarrow{\mathbf{q}},\overrightarrow{\mathbf{d}})$$

   因此如果 $\overrightarrow{\mathbf{q}}$$\mathbf{\vec q}$ 和 $\overrightarrow{\mathbf{d}}$$\mathbf{\vec d}$ 相似，则它们的相似性得分较高（由余弦相似度刻画）、距离较近。可以看到 $0\le f_d(\cdot )<=2$$0\le f_d(\cdot) <=2$ 为一个 0~2 之间的正数。

4. 编码器的输入是unified embedding 模型区别于传统文本 embedding 模型的地方。unified embedding模型编码文本特征、社交特征、以及其他有意义的上下文特征来分别表征query 和文档 。例如：

   • 在 query side ，我们可以包括searcher location 以及他们的社交关系。

   • 在文档侧（document side），以 group 搜索为例，我们可以包含有关 Facebook group 的聚合location 以及社交群（social cluster）。

   大多数特征都是高基数（high cardinality）的离散特征，可以是 one-hot 或者 multi-hot 向量。

   • 对于每个离散特征，在输入编码器之前插入一个 embedding look-up layer 从而学习和输出其稠密向量的representation 。

   • 对于multi-hot 向量，将多个 embedding 的加权组合从而得到最终的feature-level embedding 。

1.1.4 Training Data Mining

1. 在搜索排序系统（search ranking system）中为检索任务定义 positive label 和 negative label 是一个非常重要的问题。这里我们根据模型召回率指标比较了几种选择。对于负样本，我们在初始研究中尝试了以下两种负样本选择，同时将click 作为正样本：

   • 随机选择：对于每个query，我们从文档库中随机采样文档作为负样本。

   • non-click 曝光：对于每个query，我们随机采样那些在同一个session 中曝光、但是未被点击的文档作为负样本。

   和使用随机负样本相比，使用 non-click 曝光的负样本训练的模型具有更差的模型召回率：对于 people 搜索的 embedding 模型，召回率下降了 55%（绝对值，而不是相对比例）。

   我们认为这是因为 non-click 曝光负样本倾向于 hard case（可能在一个或者多个因子factor 上匹配了query），而倒排索引中的大多数文档都是easy case（根本不可能匹配上query）。将所有负样本都设为hard case 会改变训练数据对于真实检索任务的表示性（representativeness），这可能会对学到的 embedding 施加不小的 bias 。

   所谓的 easy case 指的是文档和 query 压根无关，模型很容易学到是负样本；hard case 指的是文档和 query 有一定相关性，模型需要努力学习才知道是不是负样本。

2. 我们还尝试了多种挖掘正样本的不同方法，并有如下有趣的发现：

   • click：将点击的结果作为正样本是很直观的，因为点击表明用户对结果的反馈：可能与用户的搜索意图相匹配。

   • impression 曝光：我们的想法是将检索视为 ranker 的近似函数，但可以更快地执行。然后，我们希望设计检索模型来学习ranker 相同的结果集合以及结果排列顺序。从这个意义上讲，所有用户的曝光结果对于检索模型都是正样本。

     即用matching模型去逼近ranking 模型：认为曝光的 item 都是相关的 item 。

   我们的实验结果表明：两种定义均有效。在给定相同数据量的情况下，使用点击的模型和使用曝光的模型产生了相似的召回率。

   此外，我们还尝试了使用impression-based 的数据来扩充 click-based 的训练数据，但是我们并未观察到相比于 click-based 模型的更多增益。结果表明：增加曝光数据不能提供额外的价值，模型也不能从增加的训练数据中获益。

3. 我们的上述研究表明：使用点击作为正样本、以及使用随机采样的负样本可以提供合理的模型性能。此外，我们还进一步探索了 hard mining 策略，从而提高模型区分相似结果的能力。

1.2 特征工程

1. unified embedding 模型的优点之一是它可以融合文本之外的各种特征，从而提高模型性能。我们在不同的垂直领域（ vertical）观察到，unified embedding 比文本 embedding 更有效。例如，将文本 embedding 切换为 unified embedding 之后，事件搜索（events search）的召回率提高了 18% 、群组搜索（group search）的召回率提高了 16% 。

   unified embedding 的有效性很大程度上取决于识别和构建有信息量（informative）的特征的成功。下表展示了通过将每个新特征添加到 group embedding 模型（以文本特征为 baseline）而实现的增量提升。其中 Abs.Recall Gain 表示绝对的召回率增益。

   

   接下来，我们将讨论有助于提升模型效果的几个重要特征。

2. 文本特征：字符的 n-gram 是用于文本embedding 的表示文本的常用方法。和单词n-gram 相比，它有两个优势：

   • 首先，由于字符n-gram 的词典规模（ vocabulary size ）有限，因此 embedding lookup table 规模较小，在训练过程中可以更有效地学习。

   • 其次，subword representation 对于我们在query 侧（例如拼写变化或错误）和文档侧（由于Facebook 中的大量内容库存content inventory ）遇到的 out-of-vocabulary 问题是鲁棒（robust）的。

   我们比较了使用字符 n-gram 训练的模型以及使用单词n-gram 训练的模型，发现前者可以产生更好的模型。但是，在字符3-gram 模型的基础上，包含单词 n-gram representation 额外提供了较小、但是一致的模型提升（+1.5% 的召回率提升）。

   注意，由于单词 n-gram 的基数（cardinality）通常非常高（例如，352M 的 query 3-gram ），因此需要哈希（hashing）来减少 embedding lookup table 的规模。但是，即使有哈希冲突的缺点，添加单词n-gram 仍然提供了额外的增益。

   对于 Facebook 实体 entity，抽取文本特征的主要字段是人物实体（people entity）的名字、非人物实体（non-people entity）的标题。和布尔term 匹配技术相比，我们发现使用纯文本特征训练（即没有位置特征、社交特征等非文本特征）的 embedding 特别擅长处理以下两种情况：

   • 模糊文本匹配 （fuzzy text match）：例如，该模型能够学习在query "kacis creations" 和 "Kasie’s creations" 网页之间进行匹配，而基于 term 的匹配则无法实现。

   • 可选（optionalization）：在query "mini cooper nw" 的情况下，模型可以通过删除 "nw" 以获得可选的 term 匹配，从而学习检索预期的、 Mini cooper owner/drivers club 的 group 。

3. 位置特征（location feature）：位置匹配在很多搜索场景中是有利的，例如本地商业（local business）、本地群组（local groups）、本地事件（local events）。为了使得embedding 模型在生成输出 embedding 时考虑位置信息，我们在 query 侧和文档侧的特征中都添加了位置特征。

   • 在query 侧，我们抽取了 searcher 的城市（city）、地区（region）、国家（country）、以及语言（language）。

   • 在文档侧，我们添加了公开可用的信息，例如由管理员（admin）打标（tag）的、显示的群组位置（group location）。

   结合文本特征，该模型能够成功学习query 和结果之间的隐式位置匹配（location match）。

   下表比较了文本 embedding 模型和文本+位置embedding 模型返回的、用于 group 搜索的最相似的文档。可以看到：具有位置特征的模型可以学习将位置信号融合到 embedding 中，将与来自Louisville、Kentucky 的searcher 位置相同的文档排序到更高的position 。

   

4. 社交embedding 特征：为了利用丰富的 Facebook 社交图来改善unified embedding 模型，我们基于社交图训练了一个单独的 embedding 模型来嵌入用户和实体。这有助于将综合社交图（comprehensive social graph）融合到unified embedding 模型，否则该模型可能没有完整的社交图信息。

1.3 Serving

1.3.1 ANN

1. 我们在系统中部署了基于倒排索引的 ANN（近似近邻approximate near neighbor）搜索算法，因为它具有以下优点：

   • 首先，由于embedding 向量的量化（quantization），它具有较小的存储成本。

   • 其次，更容易集成（integrate）到现有的、基于倒排索引（inverted index）的检索系统中。

2. 我们使用 Faiss library 来量化向量，然后在我们现有的倒排表（inverted table）扫描系统（scanning system）中实现高效的最近邻搜索。

   embedding 量化有两个主要组成部分：

   • 一个是粗量化（coarse quantization），它通常使用 K-means 算法将 embedding 向量量化为粗粒度的簇cluster。

   • 一个是乘积量化（product quantization），它执行细粒度量化以实现embedding 距离的有效计算。

3. 我们需要调优几个重要参数：

   • 粗量化（coarse quantization）：粗量化有不同的算法，例如 IMI 和 IVF 算法。而且重要的是调整簇的数量（num_cluster），这会影响性能和召回率。

   • 乘积量化（product quantization）：乘积量化算法有多重变体，包括原始PQ、QPQ、带PCA变换的 PQ。 PQ 的字节数（ pq_bytes ）是要调优的重要参数。

     乘积量化的思想是将向量空间（假设为 $d$$d$ 维）划分为 $m$$m$ 个（即 pq_bytes 参数）子空间，每个子空间的维度为 $d/m$$d/m$ 。然后我们在每个子空间上聚类。假设每个子空间聚类的类别数都是 $k$$k$ ，则每个原始向量将由 $m$$m$ 个整数来表示（称作 codebook），每个整数代表某个子空间中的聚类类别。

   • nprobe：该参数用于确定每个 query embedding 需要召回多少个簇，它进一步决定将扫描多少个粗簇。该参数会影响性能和召回率。

   我们构建了一个离线 pipeline 来有效地调优这些超参数。此外，我们需要进行在线实验，根据离线调优结果从选定的候选配置中确定最终配置。下面我们将分享从 ANN 调优中获得的经验和技巧：

   • 基于扫描的文档数量调优召回率。最初，我们比较了相同 num_cluster 和相同 nprobe 下，不同粗量化算法的召回率。

     但是，通过更多的数据分析我们发现：簇（cluster）是不平衡的（imbalanced），特别是对于 IMI 算法而言大约一半的簇仅有几个样本。对于相同 num_cluster 和相同 nprobe 的配置下，这将导致扫描文档的数量不同。因此，我们将扫文档数量（而不是簇的数量）作为更好的指标来近似（approximate） ANN 调优中的性能影响，如下图所示。

     我们使用 1-recall@10 来度量 ANN 的准确率（accuracy），这是根据准确的 KNN 搜索的 top 结果在 ANN 搜索 top-10 结果中的召回率。

     即：KNN 搜索得到 top-1 结果，然后看这个 top-1 结果是否在 ANN 搜索的 top-10 列表中。

     

   • 当模型发生重大变化时，调优 ANN 的超参数。我们观察到，ANN 的性能和模型特性（characteristics）有关。例如，当我们将集成技术（ensemble technique）用于non-click 曝光训练的模型时，我们发现：虽然模型显示出比baseline 更好的召回率，但是在对两者应用量化之后，模型召回率比 baseline 更差。

     当模型训练任务发生重大变化时，例如增加更多的 hard 负样本，应该始终考虑调优 ANN 超参数。

   • 始终尝试 OPQ。在应用量化之前对数据进行转换通常很有用。我们用 PCA 和 OPQ 对数据进行了转换，发现 OPQ 通常更有效，如下表和下图所示，其中采用 128 维的 embedding 。

     OPQ 的一个警告是：由于 OPQ 应用了 embedding 的旋转，我们可能还需要重新调优 num_cluster 和 nprobe 才能有类似的文档扫描。

     

      

     

   • 选择 pq_bytes 为 d/4 。乘积量化器（product quantizer）将向量压缩为 $x$$x$ 个字节码。对于 $x$$x$ 的选择，它与embedding 向量的维度 $d$$d$ 有关：$x$$x$ 越大，搜索准确率（search accuracy）越高，但代价是内存和延迟的增加。从经验结果来看，我们发现 $x>d/4$$x\gt d/4$ 之后，准确率提升有限。

   • 在线调优 nprobe, num_clusters, py_bytes 以了解实际的性能影响。虽然离线调优 ANN 算法和参数以合理了解性能和召回率之间的 tradeoff 很重要，但是我们发现同样很重要的一点是：在线部署 ANN 算法和参数的若干个配置，从而更好地了解从embedding-based 检索、到实际系统的性能影响。这对于确定容量预算（capacity budget），并减少离线调优中的参数搜索范围非常重要。

1.3.2 系统实现

1. 为了将EBR 集成（integrate）到我们的serving stack 中，我们在 Unicorn 中实现了对最近邻搜索的first-class 支持。

   Unicorn 是为 Facebook 上大多数搜索产品提供支持的检索引擎（retrieval engine）。Unicorn 将每个文档表示为bag of terms，这些 term 是表示文档二元属性（binary property）的任意字符串，通常使用属性的语义来命名。例如：居住在西雅图的用户 John 的 term 为：text:john 和 location:seattle 。term 可以附加有效载荷（payload）。

   query 可以是term 的任何布尔表达式。例如，以下query 将返回名字中有 john 和 smithe 、并且居住在 Seattle （西雅图）或者 Menlo Park （门罗公园）的人：

   (and (or (term location:seattle)
            (term location:menlo_park))
        (and (term text:john)
             (term text:smithe))
    )
   

2. 为了支持最近邻，我们扩展了document representation 从而包括文档 embedding。每个文档 embedding 都有一个预先固定的字符串关键字，并在 query 侧添加了一个 nn<key>: radius <radius> 的 query operator。这个 query operator 匹配 <key> embedding 在 query embedding 指定半径内的所有文档。其中 <key> 就是预先固定的字符串关键字，如 model-141795009 （模型版本号）。

   • 在索引时，每个文档embedding 被量化并转换成一个 term（针对粗聚类）和一个有效载荷（针对量化的残差）。

   • 在查询时，(nn) 在内部被重写为 term之间的 (or) 的规则。这些 term 关联那些与 query embedding 最接近的 coarse clusters （即 (probes)）。然后对于匹配的文档， 检索 term 的 playload 以验证半径约束。

     probes 的数量可以用一个额外的属性来指定：: nprobe 。

3. 通过根据已经存在的原语（primitives）实现最近邻支持，而不是编写一个单独的系统，我们继承了现有系统的所有功能，例如实时更新、高效的查询计划 query planning 和执行、以及对multi-hop query 的支持。

   multi-hop query 使我们能够支持基于 top-K 的最近邻query ，其中我们只选择最接近query 的 K 个文档，而不是通过半径进行匹配。然后评估query 的剩余部分。

   然而，从我们的实验研究中我们发现：半径模式可以更好地权衡（tradeoff）系统性能和结果质量。一个可能的原因是：半径模式支持受约束的最近邻搜索（受匹配表达式的其它部分约束），但是 top K 模式提供了更宽松的操作（more relaxed operation），该操作需要扫描整个索引来获得 top K 的结果。因此，我们在当前产品中使用基于半径的匹配。

4. 混合检索（Hybrid Retrieval）：通过将 (nn) operator 作为布尔查询语言的一部分，我们现在可以支持混合检索表达式，将 embedding 和 term 任意组合。这可用于基于模型的模糊匹配（fuzzy matching），该模型可以改善拼写变体（spelling variation）、可选化（optionalization）等情况，并且重用和受益于检索表达式的其它部分。

   例如，假设一个拼写错误的query "john smithe" 意图寻找一个位于 Seattle 或者 Menlo Park的、名叫 john smith 的用户，那么检索表达式类似于上面的表达式。该表达式将无法检索目标用户，因为term text:smithe 和该文档不匹配。我们可以通过 (nn) operator 为该表达式添加模糊匹配：

   xxxxxxxxxx
   (and (or (term location:seattle)
            (term location:menlo_park))
        (or (and (term text:john)
                 (term text:smithe)))
            (nn model-141795009 :radius 0.24 :nprobe 16))
   )
   

   其中，model-141795009 是 embedding 的键。

   在这种情况下，如果query "john smithe" 的 embedding与文档"john smith" 的 embedding 之间余弦距离小于0.24，则目标用户将被检索。

5. Model Serving：我们通过以下方式来 serve embedding 模型。在训练好 two-sided embedding 模型之后，我们将该模型分解为 query embedding 模型和 document embedding 模型，然后分别独立地serve 这两个模型。

   • 对于 query embedding，我们将模型部署在 online embedding inference service 从而进行实时推断。

   • 对于 document embedding，我们使用 Spark 在离线状态下 batch 地进行模型推断，然后将生成的 embedding 内容与其它元数据（metadata）一起发布到正排索引（forward index）中。

   我们还进行了额外的 embedding 量化，包括粗量化和 PQ ，并将其发布到倒排索引（inverted index）中。

1.3.3 Query and Index Selection

1. 为了提高EBR 的效率和质量，我们执行了query 和索引选择（ query and index selection ）。

   • 在query 选择方面：我们应用 query 选择技术来克服诸如过度触发（over-triggering）、巨大的容量成本（capacity cost）、以及垃圾增加（junkiness increase）等问题。

     我们并未针对某些 query 触发 EBR，因为EBR 在这些 query 上的优势很弱，并且无法提供任何额外的价值。例如考虑以下两类场景：

     • searcher 正在搜索之前已经被搜索过的、或者点击过的特定目标。

     • query 意图和 embedding 模型训练的意图明显不同的情况。

   • 在索引选择方面：我们进行了索引选择，从而加快索引速度。例如，我们仅选择每月活跃用户、最近事件（event）、热门页面（page）、热门的（group）。

1.4 后期优化

1. Facebook 的搜索排序是一个复杂的多阶段排序系统（multi-stage ranking system），其中每个阶段逐步精细化（refine）前一阶段的结果。该stack 的最底部是检索层（retrieval layer），这里应用了EBR 。检索层的结果随后被一组 ranking layer 进行排序和过滤。

   每个阶段的模型都应该针对前一层返回的结果的分布进行优化。然而，由于当前的排序阶段是为现有检索场景设计的，这可能导致从EBR 返回的新结果被现有的 ranker 进行次优（sub-optimally）排序。为了解决这个问题，我们提出了两种方法：

   • embedding 作为 ranking 特征：沿着漏斗（funnel）进一步传播 embedding similarity 不仅有助于 ranker 从EBR 中识别新结果，还为所有结果提供了通用的语义相似性度量。

     我们探索了几种基于 embedding 的特征抽取选择，包括 query 和结果 embedding 之间的余弦相似度、Hadamard 积、原始 embedding 。从我们的实验研究来看，余弦相似度特征始终表现出比其他选择更好的性能。

   • 训练数据反馈环（feedback loop）：尽管EBR 可以改善检索的召回率，但是和 term matching 相比，其 precision 可能更低。

     为了解决 precision 问题，我们建立了一个基于人工评分pipeline 的闭环反馈（closed feedback loop）。具体而言，在启用EBR 之后，我们记录了结果，然后将这些结果发送给评估者以标记query 和检索结果之间是否相关。我们使用这些人工评估的数据来重新训练相关性模型（relevance model），以便模型可以学会过滤这些不相关的结果、保留相关的结果。

     事实证明，这是一种在 EBR 中提高召回率、并达到高 precision 的技术。

1.5 高级主题

1. EBR 需要广泛的研究来继续提高性能。我们研究了 embedding 建模的两个重要领域：hard mining 和 embedding ensemble，以继续推进EBR 方案的 SOTA 。

1.5.1 Hard Mining

1. 用于检索任务的数据空间在文本匹配程度、语义匹配程度、社交匹配程度上具有不同的数据分布，并且重要的是：为embedding 模型设计训练数据集，以便在这种空间上能够有效地学习。

   为了解决这个问题，hard mining 是一个主要的方向，也是 embedding learning 的活跃研究领域。但是，大多数研究来自于计算机视觉领域，并且用于分类任务。而搜索的检索任务没有 class 的概念，因此是一个现有技术不一定能解决的独特（unique）的问题。在这个方向上，我们将解决方案分为两部分： hard negative mining: HNM、hard positive mining: HPM 。

2. hard negative mining：在分析我们的 embedding 模型以进行 people search 时，我们发现：在给定query 的情况下，embedding 的 top K 个结果通常具有相同的名称name ，并且该模型并不总是将 target 结果排名高于其它结果，即使存在社交特征。这促使我们相信该模型尚不能正确利用社交特征，这可能是因为负的训练数据太容易了，因为它们是随机负样本，通常使用不同的名称name 。

   因为负样本通常都是和 target 结果name 不同的，因此模型简单地认为：和 target 结果同名的文档就是正样本。

   为了使得模型更好地区分相似结果，我们可以使用embedding 空间中更接近正样本的样本作为训练中的 hard 负样本。

   • 在线 hard negative mining：由于模型训练是基于 mini-batch 更新的，因此可以在每个batch 中以动态（dynamic）而有效（efficient）的方式选择hard 负样本。

     假设每个 batch 包含 $n$$n$ 个正positive 的 pair 对 ${\{q^{(i)},d_{+}^{(i)}\}}_{i=1}^n$$\left\{q^{(i)},d_+^{(i)}\right\}_{i=1}^n$ 。然后对于每个 query $q^{(i)}$$q^{(i)}$ ，我们使用所有其它的 positive document $\{d_{+}^{(1)},\cdots ,d_{+}^{(j)},\cdots ,d_{+}^{(n)}\mid j\ne i\}$$\left\{d_+^{(1)},\cdots,d_+^{(j)},\cdots,d_+^{(n)} \mid j\ne i\right \}$ 构成一个小的 document pool ，并选择相似度得分（similarity score）最高的文档作为 hardest 负样本，从而创建训练triplet 。

     使用在线hard negative mining 是我们改进模型的主要贡献之一。它在所有垂直领域 （verticals）都显著提高了embedding 模型的质量：对于 people search ，召回率 +8.38%；对于 groups search，召回率 +7%；对于 events search，召回率 +5.33% 。

     我们还观察到，最佳设置是每个正样本使用最多两个 hard 负样本。使用两个以上的 hard 负样本将开始降低模型质量。

     在线 hard negative mining的一个局限性在于：从随机样本中获得任何 hard 负样本的概率很低，因此无法产生足够 hard 的负样本。接下来，我们研究如何基于整个结果池来生成更 hard 的负样本，即离线 hard negative mining。

   • 离线 hard negative mining：离线 hard negative mining 的过程如下：

     • 首先为每个 query 生成 top K 个结果。

     • 然后根据 hard 选择策略（hard selection strategy）来选择 hard 负样本。

     • 接着使用新生成的 triplet 来重新训练 embedding 模型。

     • 上述过程可以反复迭代。

     我们进行了广泛的实验，从而比较离线 hard negative mining 和在线 hard negative mining。一个可能首先看起来违反直觉的发现是：简单地使用 hard 负样本训练的模型无法胜过使用随机负样本训练的模型。进一步的分析表明：相比较于easy 模型（即使用随机负样本训练的模型），hard 模型对非文本non-text 特征赋予了更多的权重，但是在文本匹配上表现更差。因此，我们调整了采样策略，最终产生了一个可以超越在线 hard negative mining 的模型。

     • 第一个洞察是关于 hard 选择策略。我们发现使用最hard 的样本不是最好的策略。我们比较了来自不同排序位置（rank position）的采样，发现排序 101~500 之间的采样实现了最佳的模型召回率。

     • 第二个洞察是关于检索任务优化。我们的假设是：仍然需要在训练数据中包含easy 负样本。因为检索模型要在整个输入空间中进行操作，而输入空间包含各种hard 级别（从最hard 到最 easy）的数据，并且输入空间中的大多数数据都是非常 easy 的负样本。

     因此，我们探索了将随机负样本和 hard 负样本结合在一起的方法，包括从 easy 模型中进行迁移学习（transfer learning）。根据我们的经验研究，以下两种技术显示出最高的有效性（effectiveness）：

     • 混合 easy/hard 训练：在训练中混合 easy 负样本和 hard 负样本是有利的。增加 easy 负样本的比例（相比较于 hard 负样本）会持续改善模型的召回率，并且在 easy : hard = 100 : 1 时达到饱和。

     • 从 hard 模型到 easy 模型的迁移学习：虽然从 easy 模型迁移到 hard 模型不能产生更好的模型，但是从 hard 模型迁移到 easy 模型却进一步改善了模型召回率。

     最后但同样重要的是，为训练数据中的每个数据点进行详尽地KNN 计算非常耗时，并且由于有限的计算资源，总的模型训练时间将变得不切实际。对于离线 hard negative mining 算法而言，有效的 top K 结果生成很重要。在这里，近似的近邻搜索是一种实用的解决方案，可以显著减少总的计算时间。另外，在一个随机分片shard 上执行近似的近邻搜索足以生成有效的hard 负样本，因为我们在训练期间仅依赖于 semi-hard 负样本（即排序 101~500 之间的）。

3. hard positive mining：我们的 baseline 模型使用点击或者曝光作为正样本，这是现有产品（product）已经能够获取的。为了通过 EBR 来最大化互补增益（complementary gain），一个方向是识别尚未被产品成功检索、但是仍然为postive 的结果。

   为此，我们从 searcher 的活动日志（activity log）中为失败的搜索session 挖掘潜在的 target 结果来作为正样本（怎么挖？）。我们发现以这种方式挖掘的正样本可以有效地帮助模型训练。单独使用 hard 正样本训练的模型就可以达到与点击训练数据相似的模型召回水平，而数据量仅为点击训练数据的 4% 。通过将 hard 正样本和曝光数据结合起来作为训练数据，可以进一步提高模型的召回率。

1.5.2 Embedding Ensemble

1. 我们从 hard negative mining 实验中了解到： easy 负样本和 hard 负样本对于 EBR 模型训练都很重要。我们需要 hard 负样本以提高模型的precision，但是 easy 负样本对于表征（represent）检索空间也很重要。

   • 使用随机负样本训练的模型模拟了检索数据的分布，并对于非常大的 K 是较优的，但是当 K 较小时，在 top K 处的 precision 较低。

   • 另一方面，被训练来优化 precision 的模型，例如使用 non-click 曝光作为负样本、或者使用离线 hard negative mining 来训练的模型，擅长为较小的候选集合进行排序，但是对于检索任务却失败了。

   因此，我们提出通过多阶段方法（multi-stage approach）将训练有不同hard 级别（levels of hardness）的模型组合起来，其中第一阶段模型侧重于 recall、第二阶段模型专门区分由第一阶段模型返回的、更相似的结果。

   我们使用《Hard-Aware Deeply Cascaded Embedding》 相同的级联embedding 训练（cascaded embedding training）的思想，它以级联（cascaded）的方式集成（ensemble）了一组以不同 hard 水平训练的模型。

   我们探索了不同形式的ensemble embedding，包括加权拼接（weighted concatenation）、级联模型（cascade model），并且发现两者都是有效的。

2. 加权拼接 （Weighted Concatenation）：由于不同的模型为 (query,document) 的 pair 对提供了不同的余弦相似度评分，因此我们使用加权的余弦相似度作为度量来定义pair 对的相似性。

   具体而言，对于任何query $Q$$Q$ 和文档 $D$$D$ ，给定一组模型 $\{{\mathcal{M}}_1,\cdots ,{\mathcal{M}}_n\}$$\left\{\mathcal M_1, \cdots,\mathcal M_n\right\}$ 以及模型相应的权重 $\{{\alpha }_1,\cdots ,{\alpha }_n\}$$\left\{\alpha_1,\cdots,\alpha_n\right\}$ ，我们定义 $Q$$Q$ 和 $D$$D$ 之间的加权集成相似度（weighted ensemble similarity） $S_w(Q,D)$$S_w(Q,D)$ 为：

   $$S_w(Q,D)=\sum _{i=1}^n{\alpha }_i\text{cos}({\overrightarrow{\mathbf{v}}}_{Q,i},{\overrightarrow{\mathbf{v}}}_{D,i})$$

   其中：

   • ${\overrightarrow{\mathbf{v}}}_{Q,i}$$\mathbf{\vec v}_{Q,i}$ 为模型 ${\mathcal{M}}_i$$\mathcal M_i$ 对 query $Q$$Q$ 学到的embedding 向量。

   • ${\overrightarrow{\mathbf{v}}}_{D,i}$$\mathbf{\vec v}_{D,i}$ 为模型 ${\mathcal{M}}_i$$\mathcal M_i$ 对文档 $D$$D$ 学到的embedding 向量。

   出于 serving 的目的，在query 侧和 document 侧，我们需要将多个 embedding 向量集成（ensemble）到单个representation 中。并且ensemble 之后的query embedding 向量和文档 embedding 之间的相似性要和 $S_w(Q,D)$$S_w(Q,D)$ 成正比。

   我们没有直接使用 $S_w(Q,D)$$S_w(Q,D)$ ，一是因为它的取值范围超出了 [0,1] 之间；二是它的计算在线比较复杂，需要计算 $n$$n$ 对 embedding 向量的相似性。

   我们可以证明：在query 侧（或者document 侧）应用加权的归一化可以满足需求。具体而言，我们通过以下方式构造了 query 向量和 document 向量：

   $$\begin{array}{c}{\overrightarrow{\mathbf{v}}}_Q=({\alpha }_1\frac{{\overrightarrow{\mathbf{v}}}_{Q,1}}{\Vert {\overrightarrow{\mathbf{v}}}_{Q,1}\Vert },\cdots ,{\alpha }_n\frac{{\overrightarrow{\mathbf{v}}}_{Q,n}}{\Vert {\overrightarrow{\mathbf{v}}}_{Q,n}\Vert })\\ {\overrightarrow{\mathbf{v}}}_D=(\frac{{\overrightarrow{\mathbf{v}}}_{D,1}}{\Vert {\overrightarrow{\mathbf{v}}}_{D,1}\Vert },\cdots ,\frac{{\overrightarrow{\mathbf{v}}}_{D,n}}{\Vert {\overrightarrow{\mathbf{v}}}_{D,n}\Vert })\end{array}$$

   可以看到 ${\overrightarrow{\mathbf{v}}}_Q$$\mathbf{\vec v}_Q$ 和 ${\overrightarrow{\mathbf{v}}}_D$$\mathbf{\vec v}_D$ 之间的余弦相似度正比于 $S_w(Q,D)$$S_w(Q,D)$：

   $$\cos ({\overrightarrow{\mathbf{v}}}_Q,{\overrightarrow{\mathbf{v}}}_D)=\frac{S_w(Q,D)}{\sqrt{\sum _{i=1}^n{\alpha }_i^2}\times \sqrt{n}}$$

   我们以1.3 节所描述的相同方式为 （ensemble embedding） 执行 serve。

   • 模型权重 $\{{\alpha }_1,\cdots ,{\alpha }_n\}$$\left\{\alpha_1,\cdots,\alpha_n\right\}$ 的选择是经验性的，可以基于验证集的性能进行选择。

   • 另外我们探索了第二阶段embedding 模型的几种选择。实验表明：使用 non-click 曝光训练的模型获得了最佳的 KNN 召回率（和 baseline 模型相比，召回率提升了 4.39%）。

     但是，当应用 embedding 量化时，和单个模型（single model）相比，ensemble model 遭受了更多的准确率（accuracy）损失。因此，当提供在线serving 时，其实际的收益会减少。

     我们发现，为了在embedding 量化后具有最佳召回率，最佳策略是：将相对 easier 的模型和离线 hard negative mining 模型集成（ensemble），其中这些模型修改和调优了训练负样本的 hard 级别。这个集成模型的离线提升略低，但是能够实现在线的显著的召回率提升。

3. 级联模型（Cascade Model）：和加权ensemble 中的并行组合（parallel combination）不同，级联模型以串行方式在第一阶段模型的输出上运行第二级模型。

   我们比较了不同的第二阶段的选择。我们发现：使用non-click 曝光训练的模型不是一个很好地选择。总体提升远小于加权ensemble 方法。此外，随着第二阶段模型要重新排序（rerank）的结果数量的增加，收益会降低。但是，在第二阶段使用离线hard 负样本模型可以比 baseline 召回率提高 3.4% 。这是一个更适合级联的候选模型，因为离线 hard negative mining 构建的训练数据完全基于第一阶段模型的输出。

   此外，我们探索了另一种级联模型的组成。我们观察到，尽管和文本 embedding 相比，unified embedding 总体上具有更大的模型召回率，但是由于它将焦点转移到了社交匹配（social match）和位置匹配（position match）上，因此产生了新的文本匹配（text match）失败。为了提高模型的文本匹配能力，进而提高模型precision，我们采用了级联策略：使用文本 embedding 来预选择 （pre-select）文本匹配的候选文档，然后使用 unified embedding 模型对结果进行重排（rerank）以返回最终的 top 候选文档。和仅使用 unified embedding 相比，它实现了显著的在线效果提升