可扩展嵌入检索的渐进优化双粒度文档表示

286用于可扩展嵌入检索的渐进优化双粒度文档表示ShitaoXiaoXiao，ZhengLiuXiao， WeihaoHan，JianjinZhanggZhang，Yingg xiaShao，DefuLian，ChaochuoLi，HaoSunXiao，Denv yDenggXiao， LiangjieZhangG，QiZhangG，XingXieXiao中国北京邮电大学微软亚洲研究微软亚洲搜索技术中心，中国北京：中国科学技术大学{zhengliu,weihan,jianjzh,cli,hasun,dedeng,liazha,qizhang,xingx}@microsoft.com@liandefu@ustc.edu.cn摘要特设搜索要求从一个大规模的语料库中选择适当的答案。如今，基于嵌入的检索（EBR）成为一种很有前途的解决方案，其中基于深度学习的文档表示和ANN搜索技术相结合来处理这一任务。然而，一个主要的挑战是，人工神经网络索引可能太大，以适应内存，鉴于相当大的规模的answer语料库。在这项工作中，我们使用双粒度文档表示来解决这个问题，其中轻量级稀疏嵌入被索引并在内存中待机，用于粗粒度候选搜索，而重量级密集嵌入则托管在磁盘中，用于细粒度后验证。为了达到最佳的检索精度，设计了一个渐进式优化框架稀疏嵌入被提前学习以用于候选的高质量搜索以稀疏嵌入引起的候选分布为条件，连续学习密集嵌入以优化从入围候选中区分地面实况此外，两种技术：对比量化和局部中心采样被引入稀疏和密集嵌入的学习，这大大有助于他们的性能。 由于上述特点，我们的方法有效地处理了大规模的EBR具有强大的优势，准确性：高达+4。在百万级语料库上的召回率提高了3%，最高可达+17。在十亿级语料库上获得5%的召回率此外，我们的方法被应用到一个主要的赞助搜索平台的收入大幅增长（+1。95%），回忆（+1。01%）和CTR（+0. 49%）。我们的代码可在www.example.com上https://github.com/microsoft/BiDR。CCS概念• 计算方法→连续空间搜索。工作是肖世涛在微软实习期间完成的Yingxia Shao是通讯作者。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。 请求权限请发邮件至permissions@acm.org。WWW©2022版权归所有者/作者所有。授权给ACM的出版权ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3511957关键词双粒度文档表示，大规模密集检索ACM参考格式：ShitaoXiao ， Zheng Liu ， Weihao Han ， Jianjin Zhang ， YingxiaShao，Defu Lian，Chaozhuo Li，Hao Sun，Denvy Deng，LiangjieZhang，Qi Zhang，XingXie. 2022.渐进优化的双粒度文档表示，用于基于可扩展嵌入的检索。 在ACM Web Conference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚拟活动，法国里昂。ACM，美国纽约州纽约市，11页。https://doi.org/10.1145/3485447.35119571介绍特别检索对于当今的在线应用是重要的广告商和广告平台[11，18，28]。 对于每个输入的查询，系统需要从整个语料库中选择合适的答案，以满足用户的搜索需求。目前，基于嵌入的检索（EBR）已成为一种很有前途的解决方案，其中基于深度学习的文档表示和人工神经网络搜索技术联合使用来处理这个问题。EBR包括以下步骤。 在离线阶段，学习文本编码器以将输入文档表示为嵌入（例如，DPR [24]，ANCE [41]），其中查询及其相关答案可以在潜在空间中彼此靠近地投影然后，ANN索引（例如，HNSW [32]，IVFADC [21]）是为整个语料库的嵌入而构建的。 在在线阶段，ANN索引托管在存储器中。 一旦提出搜索请求，输入查询被编码到其嵌入，通过搜索ANN索引有效地选择相关的答案。1.1基于嵌入的大规模检索EBR是具有挑战性的，当一个大规模的语料库是给定的，因为人工神经网络索引可能太大，以适应内存;例如，10亿个dim- 768浮点嵌入将占用3 TB RAM空间，这比物理机的容量大几个数量级。对于今天的在线平台来说，这样的问题变得更加严重，其中内容提供商生成了数十亿个答案。扩展EBR的一种解决方案是将数据划分为多个分片，每个分片托管在不同的机器上。查询将被路由到所有分片，搜索结果将在最后阶段聚合[12]。然而，上述方法的成本很高。在这项工作中，我们使用双粒度文档表示（图1）解决了这个问题WWWXiao和Liu等人287候选人搜索（ANN）验证后（线性扫描）人工神经网络指数(in内存）数据存储(in磁盘）稀疏嵌入密集嵌入回答语料库图1：基于EBR的双粒度文档表示。答案被表示为双粒度嵌入：稀疏嵌入被索引并在内存中等待候选搜索;密集嵌入被托管在磁盘中并用于后验证。A.监督学习，然后是无监督量化（传统）B.渐进优化的双粒度表示（我们的）图2：双粒度文档表示的比较。（A）常规方法首先学习密集嵌入，并对稀疏嵌入运行无监督量化（B）我们的方法首先通过监督学习稀疏嵌入，在此基础上逐步优化密集嵌入。被表示为两组嵌入：轻量级稀疏嵌入，其在存储器中被索引并备用以用于粗粒度的候选搜索;重量级密集嵌入，其被维护在磁盘中以用于细粒度的后验证。对于每个查询q，通过内存中ANN搜索选择候选答案;然后，从磁盘加载入围候选的密集嵌入，生成细粒度的后验证结果Aq通过上述处理，EBR变得可扩展，其中数十亿个嵌入可以仅以数十千兆字节的RAM使用来托管。1.1.1表征学习的局限性尽管双粒度文档表示满足了存储空间约束，但其学习仍然是一个具有挑战性的问题。现有的EBR算法通常直接学习密集嵌入;当需要稀疏嵌入时，它们从良好学习的密集嵌入中无监督地量化[11，18，29]（图2A）。然而，我们认为，传统的方式产生的双粒度的文档表示是不适当的优化，使其与我们的候选人搜索和后验证连续执行的大规模EBR工作流程不兼容。特别是，传统的密集嵌入学习的全球歧视：从整个语料库中找到查询的相关答案的能力。然而，考虑到密集嵌入用于后验证，它需要强调局部判别：从入围候选人中选择地面实况的能力。因此，它应该在稀疏嵌入引起的候选分布之上进行优化，这与整个语料库上的答案分布不同。此外，还值得注意的是，无监督压缩是有损的[7，40]，这会阻止完全压缩候选人搜索中相关答案的覆盖范围1.2逐步优化的表示为了解决上述问题，我们提出了渐进优化的文档表示，并针对基于“候选搜索加验证后”的检索校正了学习目标首先监督学习稀疏嵌入：而不是对学习良好的密集嵌入运行无监督量化，稀疏嵌入是从对比学习中生成的，这优化了全局判别，并有助于在候选搜索中覆盖高质量的答案。 更重要的是，稀疏嵌入将制定候选分布，在此基础上，密集嵌入可以针对局部区分进行优化。在这里，一种新的采样策略，称为局部中心采样，以促进有效的优化局部歧视：一个bipartite接近图的基础上测量的稀疏嵌入的距离为基础的查询和答案建立第一，然后，在生成训练实例，随机查询被选为条目，从该查询和答案被采样在图上的局部区域 通过这种方式，同一批次内的阴性样本变得局部集中。 通过学习从大量的“批内共享负样本”中区分地面实况，表示模型将具有优越的局部区分能力，这大大有助于后验证的准确性。1.2.1突出优点。 由于上述特征，对于大规模EBR，可以显著提高检索精度。此外，我们惊讶地发现，我们的方法甚至在直接比较中优于SOTA EBR方法（即，SOTA基线直接将密集嵌入用于检索任务，其中不会产生量化损失）。 已知稀疏嵌入可以以极小的成本提供，这样的优势表明我们的双粒度文档表示也可以应用于通用EBR，其中给出了中等规模的语料库。全面的实验研究进行流行的基准上的网络搜索和十亿规模的数据集赞助搜索。根据实验结果，我们的方法取得了显着的改善，对SOTA基线在大规模和一般的EBR场景。同时，充分保持了系统的高可扩展性和运行效率。我们的方法也适用于商业搜索引擎，这带来了强大的收入，密集嵌入2.无监督量化稀疏嵌入1.监督学习用户单击2.备选销售稀疏嵌入密集嵌入1. 监督3监督量化学习用户单击用于可扩展嵌入检索的渐进优化双粒度文档表示WWW288··CTR的收益来自其广告服务。最后，本文的贡献突出如下。我们解决了渐进优化的双粒度文档表示的顶部上的大规模EBR问题。据我们所知，这是第一个系统的工作，它显着提高了检索的准确性。利用对比量化和局部中心采样，可以针对稀疏和密集嵌入有效地优化综合实验研究验证了我们所提出的方法的有效性，无论是在大规模和一般的EBR场景。全局判别从整个语料库问题洛杉矶市中心最好的披萨餐厅语料库酒店在旧金山Downtown，LA我附近的汉堡外卖…从入围候选人中甄别实况问题洛杉矶市中心最好的披萨餐厅候选人洛杉矶最佳披萨外送洛杉矶市中心最佳披萨餐厅洛杉矶阿纳海姆最佳披萨…2相关工作深度文档表示。文档表示是EBR的基础部分。最近，基于深度学习的方法由于生成语义丰富的嵌入而蓬勃发展[19，25，37]。最新的方法深入研究了预训练的语言模型，例如，BERT [10]，RoBERTa [30]，XLnet [43]. 这些模型利用大规模transformers作为主干，并通过大量语料库进行充分的预训练，实现了强大的表达能力，并有助于许多下游任务，例如文档检索[5，24，41]和问答[15，23，26]。此外，在训练方法上也取得了实质性进展。其中一个领域是负抽样。研究发现，表征学习受负样本规模的影响。因此，引入了批内负采样[6，13，24]，其中负样本可以以无成本的方式增加稍后，在[35，40]中使用跨设备负采样，其中负样本可以在所有分布式设备之间共享最近的研究也证明了“硬”阴性样本的有用性。在[24，31]中，通过BM 25评分收集硬阴性在[35，41，44]中，从ANN搜索中收集了更难的否定随着硬度的增加，显示质量有了显著的提高。也付出了一些努力应用知识蒸馏来训练检索模型[17]。索引算法。EBR的一个主要组成部分是ANN索引。简而言之，ANN索引组织具有某些数据结构的高维向量，使得可以以次线性时间复杂度执行邻近搜索[1，39]。人工神经网络指数的研究由来已久。 许多作品都是基于哈希[9，42]和树结构[3，33]开发的。最近，基于量化的方法由于有效性和紧凑性而受到广泛关注;例如， 在IVFADC [20，21]中，倒排索引与PQ（乘积量化）相结合，以促进ANN查询的快速检索。另一类重要的ANN索引是基于图的技术，其中为整个语料库构建邻近图 一种这样的方法是HNSW [32]：构建分层邻近图的多层结构，其实现了具有对数复杂度的最近邻的有效检索。基于图形的技术还与基于量化的 方法相结合，例如 ，IVFOADC+G+P [2]，其中邻近图被构造用于从大的倒排索引中快速检索前K个质心。图3：渐进式优化过程。左：首先学习稀疏嵌入，以优化全局判别，这使得高质量的候选被检索。右：学习密集嵌入以优化候选分布上的局部判别条件，这确保了地面实况（蓝色）的有效判别。人工神经网络的一个挑战性问题是，当面对一个大规模的语料库时，索引可能会超过内存。 尽管基于量化的方法可以提供帮助，但据报告，它们在召回方面受到限制[36，39]。最新的方法诉诸于混合存储。在MANN [38，39]中，为量化嵌入构建Vamana图，并将其保存在RAM中以进行成本粒度搜索;同时，原始嵌入保存在磁盘中以进行后期验证。 在HM-ANN [36]中，NSW图保存在慢 速 存 储 器 （ PMM ） 中， 枢 轴 点 托 管 在 快 速 存 储 器（DRAM）中。然而，在HM-ANN中需要大量的慢存储器是昂贵的，并且在许多情况下是不可用的到目前为止，由于其在精度和服务成本方面的相对竞争力，CANN仍然是大规模ANN的通用解决方案。3方法整个学习过程如图3所示。 在第一阶段，学习稀疏嵌入以优化全局判别：在整个语料库中区分正确答案和不相关答案，使得查询（green）及其相关答案可以被限制在同一个潜在区域。在第二阶段中，学习密集嵌入以优化局部判别：从稀疏嵌入提升的入围候选中识别地面实况。3.1稀疏嵌入学习我们将首先介绍稀疏嵌入的编码网络。然后，我们3.1.1ADC Siamese Network.请注意，只有答案需要内存高效表示，这需要索引和内存存储。因此，答案被量化用于稀疏表示，而查询保持密集表示。我们采用非对称距离计算（ADC）[21]调整连体网络，其中稀疏嵌入依赖于其选择的码字来计算与密集嵌入的距离。特别地，答案首先，每个答案a被投影到其稠密表示中。根据最近的文档表示工作[24，31]，我们使用BERT···WWWXiao和Liu等人289--ˆˆ. ..（·）·≪ | |（·）exp| || |{个文件夹{个文件夹ˆˆˆ（·）和（·）在最后处理中）。一个可重复使用的样品，S（·）qˆ||ˆ||l（q，a，a+、（五）–a−被稀疏嵌入所吸引。这种能力被称为作为编码骨干。生成的稠密向量表示为za。其次，将稠密向量量化为二进制码。这里，通过可微分PQ分量进行量化[7]。量化器用M个码本参数化，每个码字包含P个码字：Ci，j，M，P。给定密集表示za，从每个码本中选择码字C_i=arg_max{i_z_a，C_i，j_j}，（1）1121随机游走iji23其中za是za的第i段。argmax算子是基于直通估计[4]实现的，因此它是345端到端可微分。答案的稀疏嵌入由M个独热向量组成，对应于每个所选码字的ID。最后，稀疏嵌入连接所有选定的码字以进行距离计算：fs（a）=concat（[C1，. . ，C[M]）。（二更）二分邻近图2Snowball抽样查询直接由BERT编码，这与答案编码中的中间结果za相同3.1.2对比学习。 代替在密集嵌入上运行无监督量化，稀疏嵌入被监督学习以优化搜索精度。如所讨论的，稀疏嵌入用于从整个语料库中选择质量候选，这由以下操作来说明：Aq←Top-N（{（q），fs（a）|A}）。（三）在这里，Aq是候选集，其大小N远小于语料库规模，即，，NA.是查询我们使用内积来度量嵌入相似性。执行监督学习以最小化以下损失：arg minl（<$（q），fs（a+），fs（a−））， （4）图4：局部中心抽样。(1)二分邻近图构造：每个查询连接到其前N个候选答案;每个答案连接回其原始查询。(2)从输入查询开始，训练实例通过两种可选策略在局部补丁上采样：随机行走和雪球采样。复杂的负采样[22，27，35，41，44];然而，我们实验发现，在第一阶段进行这样的处理不会有助于后验证后的整体精度，因为局部区分将针对密集嵌入进行充分优化。因此，我们继续使用基于BM 25的阴性样本，因为它的有效性和简单性。3.2密集嵌入学习我们依靠具有BERT骨干的siamese编码器来生成密集嵌入。采用局部中心抽样（locality-centric sampling，LCS）方法实现强局部性Qa−a+其中a+和a−分别是查询的肯定和否定答案。在这里，我们使用InfoNCE[34]作为损失函数：统一在第一和第二阶段中学习的查询编码器3.2.1监督目标。 密集嵌入是学习的.+−. exp（q），fs（a+）<$）aAq有条件地w.r.t.由稀疏引起的候选分布其中，reA-q表示采样的集合w。r. t. q和a+。当地歧视，其中InfoNCE损失调整如下：3.1.3负采样。知道了负sam的规模-.+−（.exp（n（q），fd（a+））PLE基本上有助于表示质量[6，35]，l qaaa−）←−loga+<$A<$q−exp（q），fd.（七）（a）我们利用批量否定[24]，其中肯定的答案在一个训练实例中，用于增加其它实例的负样本。此外，我们还基于BM25为每个查询抽取了一个词汇相似的否定词，这被证明有助于文档表示[24，31]。词汇上相似的否定词也在训练实例中共享。 通过a bovet reatments，等式中的可验证样本集A−q。5be来了：A−q={a+}q′<$q<${a−}B，（6）其中a+q′<$q表示来自其他查询的肯定答案q′，而a-B表示同一个mini中的所有BM 25阴性一批批。也就是说，每个查询可以得到几乎2B个负样本（B是批量大小）。请注意，我们还可能收集比词汇相似的样本更这里，<$'（·）和fd（·）是查询编码器和密集答案编码器（我们将首先学习一个新的查询编码器<$'<$<$Aq选择用于该阶段，其不同于第一阶段中使用的那些，如Eq. 第六章特别地，A-q是从候选集合中随机采样的答案的子集：A−q←S（Aq）.（八）这里，A是如等式（1）所生成的前N个候选3，是随机选择的。我们根据经验发现，A-q应该足够大，以有效地优化局部歧视。然而，一个具有挑战性的问题是， 编码成本高。在许多情况下，保持一个大的12233451312345∑，fs歧视最后介绍了一种后处理方法）←−log嵌入：从候选人中识别地面真实情况，用于可扩展嵌入检索的渐进优化双粒度文档表示WWW290【详细】←ˆˆ·| |{ }个字符。 个文件夹. .ˆ（·）（·）（·）← （·）（·）（·）（·）·--（·）（·）（·）G（·）G（）（）（·）（·）q<$''（q）ˆ{（）下一页|个 文件夹嵌入相似性，如图4所示。特别是前N名候选人（）下一页在阿斯塔纳，为每个查询选择，如Eq.3例（N=200，+. .算法1：训练输入 ： q、a+ 得双曲正弦值.输出：fs，fd，<$，<$′，<$′1开始2%（学习稀疏嵌入）3fs，等式中的<$argmin InfoNCE5;4%（学习密集嵌入）5构造二部邻近图G;6而不收敛做算法2：ANN搜索1%（离线索引构建）2开始3推断稀疏&密集嵌入：{fs（a）|A}，{fd（a）|};4使用{fs（a）}构建HNSW|A}并将其托管在内存中;5维持{fd（a）|A}在磁盘中;6%（在线ANN服务）7开始8编码器查询为<$''（q）;7对G进行LCS得到小批量B;8通过最小化等式中的InfoNCE来更新f d，B组7例;9Aq←sea rchHNSWforTop-N（{fs（a），д′′（q）}|}）;9<$“←argmin InfoNCE in Eq.9;10load{fd（a）|一个简单的备忘录;样本大小，因为GPU容量有限，并且每个答案的编码成本可能很高。为了克服这个问题，以局部为中心的采样被用来以成本有效的方式扩展A-q。3.2.2局部中心抽样。 我们引入LCS来增广A-q。 首先，构造了二分概率图，它根据查询和答案的稀疏嵌入相似度来组织查询和答案。其次，在图的局部补丁上执行随机采样，其迭代地生成查询及其对应的硬否定。通过这样做，一个查询的否定样本也可以作为硬否定样本共享给同一小批量内的另一个查询。关于LCS的详细介绍如下。二分邻近图。我们首先构造二分邻近图的查询和答案的基础上，其稀疏图11Aq<$postr-秩，对于Top-K（{fd（a），<$''（q）<$ |}）;be：a+q′<$q（其他人3.2.3查询统一。 到目前为止，我们已经学习了分别与稀疏和密集答案嵌入配对的两个查询编码器<$'和<$'。 虽然这可能不会导致在线服务的额外延迟，因为两个编码器可以并行运行，但它仍然会导致两倍的编码成本。在计算能力有限的情况下，我们以一种简单但有效的方式统一了查询编码器，使得每个查询只需要编码一次。特别地，我们初始化<$''：<$''<$'，并固定答案编码器：fs。f ix，fd. f ix（固定的答案让我们保持一个巨大的负样本队列[16]，这有利于微调效果）。然后，我们微调查询编码器以最小化组合InfoNCE损失：Qa构建图形）。然后，添加一个前向边缘（实线），将que ryq连接到A中的anans wera。此外，q a+ l（д′′（q），fd（a+）. fix，fd（a−）.fix|A−q）。Q还添加了从a指向回q的边（虚线）。图上采样。从随机查询q作为入口点开始，执行以下策略之一：随机游走和雪球采样（图4），以生成一个小批量的训练实例。每一种策略在不同的情况下都有其优点和缺点，这将在我们的实验中讨论。随机游走：采样遵循Z字形路径。对于每个被访问的查询qi，从qi的连接候选中选择一个随机答案ai-（排除地面真值）;然后，从a i-的反向连接中采样另一个查询q i + 1。可以得出，为查询qi+1采样的下一个答案ai−+1与ai−相似;因此，它是qi的潜在候选者，这将有助于局部区分。Snowball Sampling：一个访问过的查询q将随机抽样一从它的邻居回答a-;然后在下一步中访问a的所有直接连接的 与随机游走算法相比，雪球抽样算法可以使训练样本集中在一个局部区域内，提高了批量样本的难度，但潜在地降低了样本的多样性。连续运行采样过程以生成q、a+、a−（当访问q时直接收集肯定答案a+当收集的实例填满小批量时，采样完成。最后，查询q的否定答案将上半部分是等式中的InfoNCE损失5.下半部分是方程式中的InfoNCE损失第七章通过优化上述组合损失，学习统一查询编码器<$''。我们发现，原来的精度可以很好地保持统一后3.3训练和搜索算法训练总结为Alg。1.一、首先，学习稀疏应答编码器fs和查询编码器д，以最小化等式2中的InfoNCE损失。五、其次，构造了二部邻近图。通过对执行LCS来对小批量B进行采样，利用该LCS来学习密集编码器fd和查询编码器<$’。公式中的InfoNCE损失第七章最后，查询编码器统一为<$''w.r.t.联合InfoNCE在Eq.第九章ANN搜索（Alg.2）包括两个部分：离线索引构造和在线人工神经网络请求服务。对于离线阶段：针对整个答案A推断稀疏嵌入fsa和密集嵌入fda。然后，为fsa构造HNSW [32]，它在内存中备用。同时，所有的密集嵌入fda A都存储在磁盘中。 对于在线ANN服务：每个输入查询被编码为，其用于搜索HNSW以获得前N个候选Aq。然后，将密集嵌入加载到候选者的存储器中。最后，细粒度的Top-K结果Aq通过基于{fd（a）|Aq}。argminl（д′′（q），fs（a+）. fix，fs（a−）. fix|A-q）+д′′（九）WWWXiao和Liu等人291（）（）请注意，当计算能力足够时，我们4实验研究4.1设置4.1.1数据集。 TREC 2019深度学习（DL）轨道是一个广泛使用的网络搜索基准，这是我们的主要实验对象。该基准测试包括两个任务：段落检索WebSearch（P），语料库为8，841，823个答案;文档检索WebSearch（D），语料库为3，213，835个答案。我们遵循[8]中的官方设置此外，我们利用赞助商搜索的工业数据集，其语料库包含来自商业搜索引擎的10亿个广告据我们所知，这可能是相关研究中使用的最大的语料库，这有助于我们更好地分析大规模EBR的性能。在这个数据集中，每个查询都需要匹配真实广告（由用户点击）。训练集有3 ， 000 ，000 个查询，有效/测试集有10 ，000/10，000个查询每个查询都有一个地面实况广告。请注意，数据集的答案长度高度多样化：WebSearch（D）的平均长度为448.5个令牌，比Web Search（P）（79.6）和Sponsored Search（8.1）长得多。这种差异给某些实验带来了实质性的影响，这将在我们的分析中显示出来。4.1.2基线方法。 我们与最新的文档表示方法进行了比较，这些方法在Web搜索和问答等任务上具有很强的性能。1）DPR[24]，其中批量阴性样本用于训练基于siamereBERT的文档编码器。2）DE-BERT [31] ，通过引入额外的硬负样本来适应DPR。3）ANCE[41]，它从整个语料库中迭代地全局挖掘硬否定. 它是MS MARCO基准上最强的密集检索基线之一。4）STAR[44]，通过引入批量底片以稳定和更准确的文档表示来改进ANCE我们在实验中使用以下ANN指标为了评估大规模EBR性能，利用SOTA可扩展ANN算法ERANN[39]。为了评估通用EBR性能，我们采用HNSW [32]，这是实践中最有效的ANN算法之一。4.2分析4.2.1EBR的评价 大规模EBR的评估在表1中示出，其中基线文档表示与PQANN（##+ DISK）组合：密集嵌入通过PQ压缩并通过Vamana图索引。我们的方法（BiDR：双粒度数据表示）有两种形式：BiDR （RD ），其中LCS 通过随机游走执行;和BiDR（SN），其中LCS通过雪球采样执行。基线和我们的方法都从候选人搜索中接收1000个答案，并将它们重新排名为细粒度的Top-K答案。 根据实验结果，BiDR（RD）和（SN）都优于基线，具有一致和显著的优势;例如，与最强基线相比，在Web搜索（P）和（D）上，Recall@10可以相对提高多达4.34%和2.66%。鉴于赞助搜索拥有十亿规模的语料库（比网络搜索大100倍以上），召回率方面的优势变得更大，例如，回忆@10可相对提高17.45%。现作更详细的分析如下。 在Web搜索（P）和Sponsored搜索上，BiDR（SN）的性能优于BiDR（RD），而在Web搜索（D）上，BiDR（SN）的性能不如BiDR（RD）。一个显著的区别是，网页搜索（P）和赞助商搜索的答案长度（79.6和8.1）比网页搜索（D）（448.5）小得多因此，每个训练实例（一个查询及其肯定和否定答案）的编码对于两个数据集都需要更小的内存消耗由于批量大小受GPU RAM容量的限制，因此在应用于WebSearch（P）和Sponsored Search时，将需要大量LCS采样步骤来填充小批量结果，随机游动可能发散，引入大量的相比之下，snowball有助于保持采样集中，从而解决了这个问题。然而，在Web Search（D）中，LCS步骤的数量变得非常有限，因为每个训练实例的内存消耗很大。在这种情况下，随机游走有助于引入更多的“多样化的硬负样本”，这比滚雪球抽样提供了更多信息的监督信号。至于基线：DE-BERT比DPR更强;同时，ANCE进一步优于DE-BERT。这表明硬否定，特别是ANN硬否定，是有益的。此外，STAR实现了最高的基线性能，其中批量和ANN阴性联合使用。我们在4.2.4中的实验将表明，人工神经网络和批内否定的效果是不同的：前者与局部区分度更相关，而后者与全局区分度更相关。两在某些情况下，目标可能相互矛盾4.2.2通用EBR的评价 在这一部分中，基线ANN索引被切换到HNSW，它比ANN更准确，但不再有内存效率。 鉴于赞助商搜索数据集具有十亿规模的语料库，这对于HNSW来说太大而无法放入内存，我们利用Web搜索（P）和（D）进行评估。实验结果如表2所示：利用HNSW，基线的性能与表1中的先前结果相比有所改善。 与此同时，BiDR（RD）和（SN）仍然保持其相对于最强基线的优势;例如，在不同的数据集上，Recall@10可以相对提高2.66%和2.52%。 这样的发现表明我们的双粒嵌入的竞争力对传统的EBR方法，它依赖于一个统一的密集嵌入集。关于我们的优势解释如下。 全球歧视与地方歧视是两个不同的目标，其效果是相互矛盾的：地方歧视过强不利于全球歧视，反之亦然。因此，与其强制执行一组统一的嵌入，不如利用两组协同工作的这一点将通过我们在4.2.4节中关于抽样策略的实验进一步阐明。此外，还应该注意的是，双粒度嵌入的维护并不昂贵：一方面，双粒度嵌入是离线推断的;另一方面，稀疏嵌入具有很高的内存和搜索效率，与仅使用密集嵌入的方法相比，很少引入额外的成本。用于可扩展嵌入检索的渐进优化双粒度文档表示WWW292×--网页搜索（P）网页搜寻（D）网页搜索（P）网页搜寻（D）赞助搜索方法R@10R@50R@100R@10R@50R@100R@10R@50R@100DPR +磁盘0.52970.76100.83170.59690.80830.86230.32050.50430.5545STAR + DISK0.58340.78070.83310.68070.85750.89250.34380.54800.6007ANCE+磁盘0.57450.78040.83310.66800.83360.86590.32580.52470.5757DE-BERT +磁盘0.55370.76820.82650.59980.80890.85630.32790.51740.5659BiDR（研发）0.60480.81560.87530.69880.88210.91760.39850.64670.7152BiDR（SN）0.60870.81690.87860.69590.88080.92250.40380.64890.7158表1：双级EBR的评价。BiDR（RD）和（SN）优于所有基线，具有显著优势。方法R@10R@20R@30R@50R@100R@10R@20R@30R@50R@100DPR + HNSW0.53280.64130.69840.76530.84050.59830.70590.75620.81100.8688STAR + HNSW0.59190.69170.74680.80380.86110.68160.77750.82360.86480.9044ANCE + HNSW0.58420.68580.74270.79910.85960.67280.76330.80600.84760.8840DE-BERT + HNSW0.55400.65800.71210.77090.83500.61120.71420.76600.81950.8707BiDR（研发）0.60480.70980.76040.81560.87530.69880.79640.83990.88210.9176BiDR（SN）0.60870.71160.76040.81690.87860.69590.79240.83570.88080.9225表2：通用EBR的评价。BiDR（RD）和（SN）在基线切换到HNSW后保持领先表现4.2.3效率和可扩展性。效率评估如图5所示：A1/B1为Web搜索（P）/（D），C1为赞助搜索。在实验中，我们测量了不同规模的候选人的时间潜伏期和回忆率一方面，扩展的候选大小将有助于更高的召回率，因为更有可能包括真实答案（当包括整个语料库时，ANN搜索将减少到线性扫描另一方面，扩展的候选项将增加搜索和后验证的成本，这导致更高的时间延迟。在我们的实验中，候选大小从100增加到10000，这导致召回率的增长以及时间延迟。 对于Web搜索（P）和（D）：我们观察到关于BiDR（RD）和（SN）的Recall@100很快达到了高度竞争的水平（小于0.1 ms，仅包含约300个候选人），这表明我们的方法的时间效率。 与A1和B1相比，BiDR在赞助搜索上达到稳定的竞争性Recall@100需要更多的延迟，如C1所示（约8ms，检索和重新排序5000个候选人）。 考虑到Sponsored Search拥有十亿级规模的语料库（比Web Search数据集大100多个），可以预期搜索成本的增加。此外，观察到的延迟在现实中确实具有竞争力，因为它是基于一台物理机器进行测量的（详细说明见附录）。相比之下，“STAR + CRANN”（最强基线）在候选尺寸较小时受到限制;这主要是由CRANN的有损无监督量化引起的。此外，BiDR和“STAR”之间的性能差距当包含大量候选项（10000）时，“+BNN”仍然存在;这是由于我们的渐进优化的双粒度嵌入的优越性，如4.2.2中所分析的。 可扩展性评估如图5A2、B2、C2所示. 稀疏嵌入的规模通过扩充码本逐渐增大，其存储开销从64位增加到1024当更多的比特被分配给稀疏嵌入时，数据量化的损失将更小，因此，召回率可以提高。对于所有数据集：BiDR很快增长到高召回率，内存成本低于256位（每个答案），这意味着只需32GBRAM成本就可以托管10亿个语料库进行高质量的ANN搜索。这反映了我们处理A1.网页搜索（P）A2.网页搜索（P）B2. 网页搜寻（D）C2.赞助搜索图5：效率（#1）和可扩展性（#2）的评估。BiDR以更少的延迟和内存成本达到更高的召回率。大规模EBR情景。 与效率分析中的观察结果类似：1）对于赞助搜索，所有方法在小比特率下的召回准确率都很低; 2）CRANN+STAR的召回率在小比特率下受到限制，并且性能差距仍然存在于高比特率下。我们将这些观察结果归因于我们在效率分析中解释的相同原因4.2.4消融研究。详细的影响进行了研究对比量化，局部中心抽样，统一查询。量化。我们的对比量化的评估显示在表3的上半部分，比较了三个代表性的基线：1）典型的无监督方法PQ [20]; 2）OPQ [14]，它迭代地学习嵌入的投影和码本以最小化重建损失;3）DPQ[7]，其中B1.网页搜寻（D）C1.赞助搜索WWWXiao和Liu等人293∼网页搜索（P）网页搜寻（D）赞助搜索量化R@50R@100R@1000R@50R@100R@1000R@50R@100R@1000PQ0.71270.78670.93490.40320.49000.74880.24130.31670.6000OPQ0.75980.82700.95190.78640.84900.94830.26290.33200.6140DPQ0.76960.83990.95580.79930.85710.95430.33590.42880.7218对比0.78010.84600.96050.81820.87020.96120.40670.50040.7659采样R@10R@50R@100R@10R@50R@100R@10R@50R@100安0.60210.81010.87280.69210.87090.91090.38350.63020.7041ANN+批内0.60140.80920.87270.68610.86980.91070.37550.62540.6999随机游走0.60480.81560.87530.69880.88210.91760.39850.64670.7152雪球0.60870.81690.87860.69590.88080.92250.40380.64890.7158统一查询R@10R@50R@100R@10R@50R@100R@10R@50R@100统一（RD）0.60270.81210.86630.70030.87850.91470.39620.63460.7046W.O.统一（RD）0.60480.81560.87530.69880.88210.91760.39850.64670.7152统一（SN）0.60030.80980.87040.69240.87750.91430.40020.63990.7064W.O.统一（SN）0.60870.81690.87860.69590.88080.92250.40380.64890.7158表3：消融研究：（1）对比量化、（2）局部中心采样（LCS）和（3）查询统一的影响。（考虑到在候选搜索中选择了前1000个答案，针对量化方法报告了Recall@1000。）在一个网络内共同最小化重构损耗和匹配损耗。候选搜索结果的召回率报告，其大小比最终检索结果大得多。我们可以发现直接使用PQ是有损的，其准确性是所有方法中最低的 由于有效减少了重建损失，其他基线得到了改善;然而，它们仍然不如我们的对比量化，其中InfoNCE损失（检索准确性的目