酷应用

千亿级照片，毫秒间匹配最佳结果，微软开源Bing搜索背后的关键算法

百家作者：AI100 2019-05-16 12:00:37

作者 | Charlie Waldburger

译者 | 刘畅

责编 | 一一

出品 | AI科技大本营（id：rgznai100）

【导读】随着互联网的普及，搜索成为人们最常用的基本功能之一，但这背后的秘密是什么呢？近日，微软公司介绍了他们是其如何应对用户搜索习惯的改变，并开源了支撑 Bing 搜索背后的算法。

搜索需求的改变

以前的网页搜索功能十分简单，用户输入几个词，就会返回一系列相应的结果页面。如今，这些用户可能会用手机拍照并将其放入搜索框或使用智能助手来提问，并不需要亲自触摸设备。他们可能会直接输入一个问题，并期待一个对应的回复，而不仅仅是给出多个可能答案的网页列表。

搜索需求的改变对于以往基于索引系统，依赖关键字匹配给出搜索结果的传统搜索引擎是一个挑战。

“关键词搜索算法会在人们提出问题或拍照并询问搜索系统'这是什么？' 时失效”，微软 Bing 搜索和 AI 团队的项目经理 Rangan Majumder 说到。

当然，紧跟用户的搜索偏好并不是新鲜事，自从网络搜索功能出现以来，这一直是一场博弈。但现在，由于人工智能的发展，包括微软在人工智能方向取得进步，越来越容易满足这些不断变化的需求。

“人工智能正在使我们的产品更加符合人的思考习惯，”Majumder 说， “但在以前人们不得不思考，'当我使用计算机进行搜索时，如何输入才能得到自己想要的结果？'”

微软已经制作完成了最先进的人工智能工具之一，并已经在 GitHub 上开源，它还将通过微软的 AI 实验室发布这些工具的用户示例技术和介绍视频

链接
https://www.ailab.microsoft.com/vectorsearchexperiment）

这种被称为空间分治树与图（Space Partition Tree And Graph, SPTAG）的算法，允许用户利用深度学习模型来在毫秒内搜索数十亿条信息（或称矢量）。反过来，这意味着他们可以更快地向用户提供更匹配的结果。

矢量搜索相较于关键字搜索，可以更容易的按照内容得到搜索结果。例如，如果用户键入“巴黎铁塔有多高？”Bing 可以返回一个自然语言结果告诉用户艾菲尔铁塔是 1,063 英尺，即使“搜索查询”中没有出现“Eiffel”这个词，而“tall”这个词也不会出现在结果中。

微软将矢量搜索应用于 Bing 搜索引擎，该技术可以帮助 Bing 更好地理解数十亿网络搜索背后的意图，并在数十亿网页中找到最匹配的结果。

使用矢量进行更好的搜索

矢量的本质上是单词、图像像素或其他数据点的数字表示，它有助于捕获某条数据实际的意义。由于深度学习技术的进步，微软认为可以开始使用这些向量来理解和表示搜索意图。一旦将数据点分配给某条数据，就可以排列或映射这些向量，其中排列地靠前的数字表示相似性。这些近端结果会显示给用户，从而提升搜索结果。当公司工程师注意到用户搜索模式有异常趋势时，Bing 使用的矢量搜索背后的技术就会启动。

“在分析我们的日志时，团队发现搜索查询字符越来越长，”Majumder 说。这表明用户提出了更多问题，对于之前的搜索问题进行更多解释，对关键字搜索的体验不佳，或者在描述抽象事物时“试图像计算机一样思考”。这些对用户来说都是不自然和不方便的。

通过 Bing 搜索，矢量化工作已经扩展到搜索引擎中超过 1500 亿条数据，来提升传统关键字匹配算法的效果，主要包括单个单词、字符、网页代码段、完整查询和其他媒体信息。一旦用户进行搜索后，Bing 可以扫描索引向量并提供最佳的匹配结果。矢量分配使用深度学习技术进行训练，然后持续改进。模型会在搜索后考虑用户最终点击的输入，以便更好地理解搜索的含义。

微软专家表示，虽然矢量化媒体和搜索数据的想法并不新鲜，但最近才有可能在大规模搜索引擎（如 Bing）上使用它。“Bing 每天会处理数十亿个文档，现在的想法是我们可以将这些条目表示为向量，并在 1000 亿个以上的大规模索引中进行搜索，以便在 5 毫秒内找到最匹配结果。”微软 Bing 团队程序经理 Jeffrey Zhu 表示。

为了更直观的描述这一点，Majumder 详细解释道：一堆可以延伸到月球的 1500 亿张的名片中，眨眼之间，可在使用了 SPTAG 算法的 Bing 搜索里一个接一个地找到 10 张不同的名片。

搜索算法 SPTAG 及项目简介

该项目库假设使用向量来表示样本，并且可以使用 L2 距离或余弦距离来比较向量。为查询返回的向量是与查询向量具有最小 L2 距离或余弦距离的向量。

SPTAG 提供两种方法：kd-tree 和相关邻域图（SPTAG-KDT）与平衡 k-means 树和相关邻域图（SPTAG-BKT）。 SPTAG-KDT 在索引构建成本上更便宜，而 SPTAG-BKT 在高维数据中的搜索精度方面更好。

算法流程

SPTAG 的灵感来自 NGS 方法[WangL12]。它包含两个基本模块：索引构建器和搜索器。 RNG 建立在 k 近邻图[WangWZTG12，WangWJLZZH14]上，用于提高连接度。平衡的 k 均值树是用于替换 kd 树，以避免在高维向量中，kd 树对距离估计不准确带来的束缚。搜索首先在空间分治树中搜索，以找到可以在 RNG 中开始搜索的若干种子数，然后迭代地在树和图中进行搜索。

强调

最新更新：支持在线矢量删除和插入

分布式服务：在多台计算机上搜索

构建