编辑:Hao作者:Olli Huang编译:Geek AI、路

机器之心论文解读:可用于十亿级实时检索的循环二分嵌入模型(RBE)

今年 2 月,来自微软 Bing 的研究人员在今年的 KDD 会议上发表了论文《Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors》。该论文提出了能够生成紧凑语义表征的「循环二分嵌入」(RBE),这些表征可存储在 GPU 上,RBE 使得十亿级的检索能够实时进行。机器之心对这篇论文进行了解读。

论文链接:https://arxiv.org/pdf/1802.06466.pdf

1 简介

信息检索(IR)是根据用户查询从存储在计算机上的源数据集合中检索信息的活动。信息检索已有长达一个世纪的历史 [1],它是许多常见应用(如 web 搜索、产品推荐和社交网络上的个性化推送 feed 流服务)的核心。上世纪六七十年代,该领域的研究取得了重大突破 [2],研究人员开始将查询和文档作为高维向量进行编码。

然而,处理高维向量并非易事。在涉及高维数据的检索任务中,基于熵和 KL 散度的统计测量方法,过去被广泛使用。然而,这类方法通常面临维数灾难 [3,4]。

k 最近邻算法(k-NN)是一种广为人知的经典算法,用于化解维数灾难。k-NN 算法采用「暴力搜索」(或者「穷举搜索」)方法找到查询点在参考点集中的 k 个最近邻。但是,k-NN 算法的计算开销巨大。因此,研究人员们提出了诸如近似最近邻(ANN)等算法 [5,6],使用 kd 树对数据预先进行组织,从而减小计算量。

近十年,图形处理单元(GPU)在图像和视频处理任务中得到了广泛应用。然而,在开发基于 GPU 的信息检索(特别是穷举搜索)方面,却鲜有突出的成果。论文《Fast k nearest neighbor search using GPU》[7] 是对基于 GPU 的 k-NN 穷举搜索的早期尝试。

本文将解读微软 Bing 研究人员的一篇论文《Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors》,他们在这篇论文中提出了一个新模型「循环二分嵌入」(Recurrent Binary Embedding,RBE),它首次将基于 GPU 的穷举 k-NN 算法应用到十亿级的实时信息检索任务上。

这篇论文主要的贡献是设计了能够生成紧凑语义表征的「循环二分嵌入」(RBE),使十亿级的检索能够实时进行,这些表征可存储在 GPU 上。RBE 模型使用 CNTK 中的 BrainScript 实现(BrainScript 不久后将被开源,项目地址: https://docs.microsoft.com/en-us/cognitive-toolkit/),且在 GPU 集群上训练而成。此外,这篇论文在一个自定义多 GPU 服务器上实现了基于 GPU 的 RBE 信息检索模型(简称 rbeGIR),如图 1 所示。

图 1:具备 4 张英伟达 GeForce GTX 1080 GPU、两个 8 核 CPU、128GB DDR 内存的 rbeGIR 服务器。

论文的作者利用微软付费搜索引擎收集的数据,对 rbeGIR 系统进行评估。RBE 模型的训练数据包含 1.75 亿(175M)唯一点击对,这些数据是从两年的有效搜索日志中采样得到的。通过交叉抽样给每一个点击增加 10 个负样本,使训练样本的总数达到 19.25 亿(1925M)。为了避免重复,验证数据由一个月后采样得到的 1.2M 点击对组成。此外,测试数据包括人类标注的 0.8M 个点击对。

此外,rbeGIR 系统在召回和延迟方面取得了非常好的表现。在基于 12 亿个关键词和 1 万条查询的评估中,该系统的平均召回率达到了 99.99%,而平均延迟仅为 31.17 毫秒,这充分体现了 rbeGIR 系统的实时检索能力。

2. 要点

RBE 模型是在大型搜索引擎的搜索广告(sponsored search)背景下提出的。本质上,搜索广告机制是同时显示出广告与搜索结果。该生态系统中三个重要的相关利益方为「用户」、「广告商」和「搜索平台」。搜索平台的目标是显示出用户可能想要点击的广告。

用户将在搜索框中输入「查询」,而搜索引擎会查找到相关的信息。然后,搜索引擎将使用信息检索技术,提取出能够将用户和广告商意图相结合的「关键词」。最终,搜索引擎会根据这些关键词显示一些广告(或称「展现」)。如果用户点击了广告,则记录这个「点击」事件。

本节将介绍这篇论文的三个要点。第一个要点是 RBE 模型,它提供了一种为搜索广告语境中的查询和关键词生成紧凑向量表征的新方法。第二个要点是基于 RBE 的信息检索,这一部分关注的是将 RBE 模型应用在基于 GPU 信息检索系统中。最后一个要点,是使用基于 GPU 的穷举 k-NN 选择算法,这也是 rbeGIR 系统的重要组成部分,专门为十亿级检索而设计。

2.1 RBE 模型

如图 3 所示,RBE 模型旨在为搜索广告中的查询和关键词,生成紧凑的向量表征。RBE 模型是基于 CLSM 模型 [8] 构建而成(CLSM 模型架构如图 2 所示)。

RBE 模型与 CLSM 模型在「multi-layers」之前的部分是相同的前馈过程,multi-layers 以上的部分叫做 RBE 层。RBE 层由公式 8-11 形式化表示的。如图 3 和公示 9-11 所示,正是其中的循环结构使得 RBE 模型具备「循环」的性质。然而,RBE 模型与其他网络结构(如 RNN 或 LSTM)没有联系。这里「循环」仅仅指的是 RBE 模型中的循环模式。对于 RNN 或 LSTM 类模型,从时间步 t 到 t-1 的转换会共享同一组参数,以学习持续的记忆单元。而 RBE 模型在确定参数集是否固定或随着时间变化方面更加灵活。

图 2:CLSM 模型架构。

图 3:RBE 模型架构。

本质上,公式 8-11 背后的关键思想是通过最大化从实值向量 f_i 中提取出的信息来建立二值分解 b_i^t。为了重构这样的二值分解,训练过程中会生成多个中间向量。

2.2 基于 RBE 的信息检索

用于关键词检索的系统架构如图 4 所示。该系统被称为基于 GPU 的 RBE 信息检索系统,或 rbeGIR 系统。首先,该系统采用了多个 GPU 来存储和处理 RBE 嵌入。圆角矩形内展示了第 p 个 GPU 的组成部分。在图 4 底部我们可以看到,关键词首先被离线转换为 RBE 向量,然后从 CPU 存储单元(寄存器、cache 等)转移到 GPU 显存中。另一方面,查询会被即时转换为 RBE 向量。GPU 内的穷举匹配组件,则负责计算查询的 RBE 嵌入与每个关键词之间的相似度。为了找到最佳关键词,匹配结果将指导第 p 个 GPU 负责局部选择和全局选择过程。所有 GPU 的计算结果都将通过选择合并(Selection Merge)对生成的 top N 关键词作出贡献。

内存效率是 RBE 模型的关键优势。举例而言,存储十亿个关键词需要 14.90GB 的内存空间,而使用浮点类型进行存储只需要 238GB 的存储空间。这为在多 GPU 进行 内存检索(in-memory retrieval)铺平了道路。此外,RBE 还能够学习针对于特定应用的表征,因此它比通用的量化算法更加准确。

图 4:基于 GPU 的 RBE 信息检索(rbeGIR)系统图示。

rbeGIR 系统是基于论文作者开发的生产检索系统评估的。评估过程用到了两个对比基线:prod_1 指的是具有等量存储空间的生产环境;prod_2 指具备同等数量关键词的设置。此外,rbeGIR 系统中还存储了 12 亿个唯一关键词的嵌入。

如表 3 所示,在 2000 个查询中,每个查询返回的前 5 个关键词的平均质量为「差」、「一般」、「良」或「优」。表 3 中的每一列代表对应于每列标签的查询-关键词对数量的百分比差距。例如「良」的结果,rbeGIR 系统分别比 prod_1 和 prod_2 高出了 18.52% 和 11.19%。

为了评估 rbeGIR 系统的召回性能,论文作者首先使用精确的最近邻算法,将 1 万条查询和 12 亿个关键词,与 RBE 嵌入进行匹配。每个查询的 recall @1000 表示,rbeGIR 获得的 top 关键词,与相关关键词重叠的总数除以 1000 后的结果。实验结果显示,rbeGIR 系统的平均召回率(recall @1000)高达 99.99%。此外,rbeGIR 系统的平均延迟时间为 31.17 毫秒,这充分体现了该系统的实时检索能力。

2.3 基于 GPU 的穷举 k-NN 选择算法

rbeGIR 系统的一个重要组成部分是,可用于十亿级检索的穷举 k-NN 选择算法。该算法从局部的分段处理开始,它依赖于 k-NN 内核(如 Algorithm 1 所示)。该算法将查询和每个关键词的 RBE 嵌入作为输入,并输出一个具有最高相似度得分和索引的优先队列(priority queue)。输出的优先队列被传输给全局选择和合并选择过程,从而获得排序最靠前的关键词。全局选择和合并选择都采用了 Radix 排序方法 [9],这也是最快的排序算法之一。

3. 结论

这篇论文介绍了一种可为十亿级信息检索任务生成语义向量表征的 RBE 模型,它能在 GPU 上存储和运行。RBE 表征可以进一步与穷举 k-NN 搜索相结合。此外,文中实现的 rbeGIR 系统,是利用深度学习算法和强大 GPU 算力的一次早期尝试。

论文作者指出,RBE 表征不局限于 CLSM 模型。如图 5 所示,未来 RBE 的概念可进一步泛化到语义哈希 [10] 或 word2vec [11] 等网络中。

图 5:RBE 的概念可以推广到其他网络,如语义哈希(左图)和 word2vec(右图)。

参考文献:

[1] Sanderson, M., and Croft, W. B. The history of information retrieval research. Proceedings of the IEEE 100, Special Centennial Issue (2012), 1444-1451.

[2] Salton, G., Wong, A., and Yang, C.-S. A vector space model for automatic indexing. Communications of the ACM 18, 11 (1975), 613-620.

[3] Weber, R., Schek, H.-J., and Blott, S. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB (1998), vol. 98, pp. 194-205.

[4] Aggarwal, C. C., Hinneburg, A., and Keim, D. A. On the surprising behavior of distance metrics in high dimensional spaces. In ICDT (2001), vol. 1, Springer, pp. 420-434.

[5] Friedman, J. H., Bentley, J. L., and Finkel, R. A. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS) 3, 3 (1977), 209-226.

[6] Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry (2004), ACM, pp. 253-262.

[7] Garcia, V., Debreuve, E., and Barlaud, M. Fast k nearest neighbor search using GPU. arXiv preprint arXiv:0804.1448.

[8] Shen, Y., He, X., Gao, J., Deng, L., and Mesnil, G. A latent semantic model with convolutional-pooling structure for information retrieval. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management (2014), ACM, pp. 101-110.

[9] Merrill, D. G., and Grimshaw, A. S. Revisiting sorting for gpgpu stream architectures. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques (2010), ACM, pp. 545-546.

[10] Salakhutdinov, R., and Hinton, G. Semantic hashing. RBM 500, 3 (2007), 500.

[11] Mikolov, T., Chen, K., Corrado, G., and Dean, J. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013).

入门词嵌入自然语言处理信息检索
2
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

信息检索技术

信息检索(IR)是基于用于查询检索信息的任务。流行的信息检索模型包括布尔模型、向量空间模型、概率模型和语言模型。信息检索最典型和最常见的应用是搜索引擎。

维数灾难技术

维数灾难(英语:curse of dimensionality,又名维度的诅咒)是一个最早由理查德·贝尔曼(Richard E. Bellman)在考虑优化问题时首次提出来的术语,用来描述当(数学)空间维度增加时,分析和组织高维空间(通常有成百上千维),因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到,如物理空间通常只用三维来建模。

重构技术

代码重构(英语:Code refactoring)指对软件代码做任何更动以增加可读性或者简化结构而不影响输出结果。 软件重构需要借助工具完成,重构工具能够修改代码同时修改所有引用该代码的地方。在极限编程的方法学中,重构需要单元测试来支持。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

语义哈希技术

语义哈希(semanticHashing)是指将高维空间向量映射至低维汉明空间,并保持原空间向量相似性,使得新空间向量的汉明距离反映原空间向量相似度的哈希算法。语义哈希引入了近似的概念,认为在海量数据的搜索中,在大多数情况下,完全精确的查找并不是必须的,近似解己经足以满足用户绝大多数的要求,因而通过哈希算法迅速定位数据集中一定概率下与搜索关键词相关的数据,配合汉明空间相似度度量的快速性和索引结果容易进一步扩展的特点,可以大幅提高索引和检索的效率。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

word2vec技术

Word2vec,为一群用来产生词向量的相关模型。这些模型为浅而双层的神经网络,用来训练以重新建构语言学之词文本。网络以词表现,并且需猜测相邻位置的输入词,在word2vec中词袋模型假设下,词的顺序是不重要的。 训练完成之后,word2vec模型可用来映射每个词到一个向量,可用来表示词对词之间的关系。该向量为神经网络之隐藏层。 Word2vec依赖skip-grams或连续词袋(CBOW)来建立神经词嵌入。Word2vec为托马斯·米科洛夫(Tomas Mikolov)在Google带领的研究团队创造。该算法渐渐被其他人所分析和解释。

长短期记忆网络技术

长短期记忆(Long Short-Term Memory) 是具有长期记忆能力的一种时间递归神经网络(Recurrent Neural Network)。 其网络结构含有一个或多个具有可遗忘和记忆功能的单元组成。它在1997年被提出用于解决传统RNN(Recurrent Neural Network) 的随时间反向传播中权重消失的问题(vanishing gradient problem over backpropagation-through-time),重要组成部分包括Forget Gate, Input Gate, 和 Output Gate, 分别负责决定当前输入是否被采纳,是否被长期记忆以及决定在记忆中的输入是否在当前被输出。Gated Recurrent Unit 是 LSTM 众多版本中典型的一个。因为它具有记忆性的功能,LSTM经常被用在具有时间序列特性的数据和场景中。

推荐文章
暂无评论
暂无评论~