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

不断向开源社区添砖加瓦的微软近日又有大动作– 将强大的最近邻搜索算法开源。2019年5月15日，GitHub存储库上的开源社区成员都可以访问微软的空间分区树和图（SPTAG）算法，该算法“允许用户充分利用学习模型在以毫秒为单位时间内智能搜索数十亿条信息（也称矢量）。”

我们每个人每天都在享受各种在线服务（在线搜索、新闻推荐等）所带来的种种便利。这些服务的背后隐藏着庞大的、需要计算机实时处理的数据。例如，在图像搜索领域，面对给定的一幅查询图像，系统要从庞大的数据库里（比如包含百万、千万甚至上亿图像）快速找出相似的图像；而在新闻推荐中，计算机也需要根据用户画像，从大量的新闻中找到最相关的新闻推荐给用户。

想要从海量数据中快速找到有效数据离不开最近邻搜索算法。最近邻搜索是计算机视觉、机器学习、多媒体搜索、计算几何等领域里非常基础、也是非常重要的问题。目前主要有两种减少搜索时间的方法：基于哈希的近似最近邻搜索的方法通过设计和优化哈希函数，减少计算的次数，从而缩短搜索时间。基于量化的近似最近邻搜索方法则通过聚类把向量集聚成若干类，每类里面的向量用对应的类中心来近似。

图1: 哈希和量化对比的二维案例。左：量化的距离更加丰富；右：量化需要的比特数目少。

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

该公司在今天的公告中写道：“仅在几年前，网络搜索很简单。用户输入几个单词并浏览结果页面。今天，相同的用户可能会在手机上拍照并将其放入搜索框中，或使用智能助手提问而无需亲自触摸设备。他们也可能会输入一个问题并期待一个实际的答复，而不是一个可能答案的页面列表。”

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

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