微软开源GitHub最近邻搜索算法基于最近邻图的SPTAG

2019年5月15日，GitHub存储库中的开源社区成员可以访问微软的空间分区树和图（SPTAG）算法，该算法“允许用户来创建。”利用智能学习模型，在毫秒内智能搜索数十亿信息（也称为向量）。”

每个人都喜欢每天受益于各种在线服务（在线搜索、新闻推荐等）的各种便利。服务位于海量数据中，需要计算机实时处理 例如，在图像搜索领域，面对特定的问题图像，系统必须快速从庞大的数据库（例如包含数百万、数千万甚至数百个）中找到相同的图像数百万张图片）；而在新闻推荐中，计算机还必须从众多新闻中找到最相关的新闻，并根据用户的个人资料推荐给用户。最近邻搜索是计算机视觉等领域的一个基本且重要的问题、机器学习、多媒体搜索和计算几何。目前减少搜索时间的方法主要有两种：基于哈希的最近邻搜索方法，通过设计和优化哈希函数来减少计算次数，从而缩短搜索时间。基于量化的最近邻搜索方法通过聚类将向量分为若干类，每一类中的向量都用相应类的中心来近似。

图1：哈希和量化比较的二维情况。左：更丰富的量化距离；右：量化所需的位数较少。

今天，微软在 GitHub 上开源了基于最近邻图的最近邻搜索算法——空间分区树和图（SPTAG），这是 Bing 搜索底层的人工智能技术之一。您当前正在搜索“巴黎的塔楼有多高？”在 Bing 上，他们会告诉您埃菲尔铁塔高 324 米（1,063 英尺），大致相当于 81 层建筑。虽然搜索关键词中没有出现“埃菲尔”这个词，搜索结果中也没有出现“高”这个词。

在今天的公告中，该公司写道：“就在几年前，网络搜索还很简单。用户输入几个单词并浏览结果页面。现在，同一用户可以在手机上拍照并将其放在“在搜索框中，或使用智能助手在不触摸设备的情况下提问。他们还可以输入问题并期待真正的答复，而不是可能答案的页面列表。”

当然，矢量搜索本身并不是一个新想法。然而，微软所做的就是实现这个概念。深度学习模型。首先，团队采用经过训练的模型并将数据编码为向量，其中每个向量代表一个单词或像素。然后，它使用新的 SPTAG 库生成向量索引。当查询到来时，深度学习模型将文本或图像转换为向量，并且库在索引中找到最相关的向量。

“通过 Bing 搜索，矢量化工作已扩展到搜索引擎索引的超过 1500 亿条数据，从而比传统关键字匹配有所改进，”微软表示。 “这包括单个单词、字符、网页片段、完整查询和其他媒体。用户搜索后，Bing 可以扫描索引向量并提供最佳匹配。