经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 业界动态 » 查看文章
微软开源的Bing关键算法SPTAG成色几何?
来源:ATYUN订阅号  作者:老张  时间:2019/5/27 10:40:32  对本文有异议

几年前,网络搜索很简单,用户输入几个单词并浏览结果页面。

今天,用户可能会在手机上拍摄照片,并将其放入搜索框或使用智能助手提问而无需亲自接触设备。他们也可能会输入一个问题,并期待一个实际的回复,而不是一个有诸多可能的答案的页面。

这些任务挑战了传统的搜索引擎,传统的搜索引擎基于反向索引系统,而该系统依赖于关键字匹配来生成结果。

不断增加的媒体组合使微软转向另一种AI技术——空间分区树和图(SPTAG),从而更好地解析搜索。它现在已开源,还有示例技术和附带的视频。

该算法(用C ++编写并用Python包装)是许多Bing搜索服务的核心,能够在几毫秒内搜索数十亿条信息。反过来,这意味着它们可以更快地向用户提供更相关的结果。

1.jpg

向量搜索使按概念搜索比关键字搜索更容易,例如,如果用户输入“巴黎的塔有多高”,Bing可以返回一个自然语言结果,告诉用户艾菲尔铁塔1063英尺,即使搜索查询中没有出现“Eiffel”这个词,结果中也没有出现“tall”这个词。

微软将向量搜索用于自己的Bing搜索引擎,该技术正在帮助Bing更好地理解数十亿网络搜索背后的意图,并在数十亿网页中找到最相关的结果。

使用向量进行更好的搜索

向量本质上是一个单词、图像像素或其他数据点的数字表示,它帮助捕捉数据块的实际含义。主要通过深度学习理解和表示使用这些向量的搜索意图。

一旦将数值点分配给一段数据,就可以对向量进行排列或映射,将相邻的数字放在一起表示相似性。这些近似的结果显示给用户,改善了搜索结果。

当公司工程师开始注意到用户搜索模式的异常趋势时,Bing使用的向量搜索背后的技术得到了启动。

Majumder说,“在分析我们的日志时,团队发现搜索查询越来越长,这表明由于过去的经历、糟糕的关键词搜索体验,用户会问更多的问题、过度解释,或者在描述抽象事物时,试图像电脑一样,对用户来说既不自然又不方便。”

通过Bing搜索,向量化工作已经扩展到搜索引擎索引的超过1500亿条数据,从而改进了传统的关键字匹配。这些包括单个单词,字符,网页代码段,完整查询和其他媒体。用户搜索后,Bing可以扫描索引的向量并提供最佳匹配。

向量分配也使用深度学习技术进行训练,以进行持续改进。模型会在搜索后考虑最终用户点击之类的输入,以便更好地理解搜索的含义。

微软专家表示,虽然向量化媒体和搜索数据的想法并不新鲜,但最近才有可能在大规模搜索引擎(如Bing)上使用它。

微软Bing团队的项目经理Jeffrey Zhu表示,“Bing每天处理数十亿个文档,现在的想法是我们可以将这些条目表示为向量,并搜索这个1000亿以上向量的巨大索引,以便在5毫秒内找到最相关的结果,”Jeffrey Zhu,程序说。微软Bing团队的经理。

想象一下:1500亿张名片将从这里延伸到月球。在眨眼之间,Bing使用SPTAG进行的搜索可以在该堆卡片中一个接一个地找到10张不同的名片。

用于视觉、音频搜索

Bing团队表示,他们希望开源产品可以用于企业或面向消费者的应用程序,以识别基于音频片段的语言,或者用于图像繁重的服务,例如让人们拍摄鲜花和照片,确定它是什么类型的花。对于那些类型的应用程序,缓慢或不相关的搜索体验令人沮丧。

“甚至几秒钟的搜索都会降低应用程序体验,”Majumder指出。

该团队还希望研究人员和学者能够利用它来探索其他领域的搜索突破,“我们只是开始探索在这个深度上向量搜索的真正可能性。”

算法简介

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

2.jpeg

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

3.png

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

SPTAG提供了两种算法:kd树和相对邻域图(sptag-kdt)、平衡k均值树和相关邻域图(sptag-bkt)。sptag-kdt在索引构建成本上具有优势,sptag-bkt在高维数据的搜索精度上具有优势。

SPTAG的灵感来自于NGS方法。它包含两个基本模块:索引生成器和搜索器。RNG建立在K-最近邻图上,以提高连通性。利用平衡k均值树代替kd树,避免了kd树对高维向量的距离界估算不准确的缺陷。搜索过程从在空间分区树中搜索几个种子开始。树和图中的搜索是迭代进行的。

微软官方欢迎来自所有开发者的建议和意见,他们也会在GitHub上收集BUG信息。

GitHub地址是:

github.com/microsoft/SPTAG