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

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

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

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

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

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

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

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