隨著互聯(lián)網(wǎng)的普及，搜索成為人們最常用的基本功能之一，但這背后的秘密是什么呢？近日，微軟公司介紹了他們是其如何應(yīng)對(duì)用戶搜索習(xí)慣的改變，并開源了支撐 Bing 搜索背后的算法。

搜索需求的改變

以前的網(wǎng)頁搜索功能十分簡(jiǎn)單，用戶輸入幾個(gè)詞，就會(huì)返回一系列相應(yīng)的結(jié)果頁面。如今，這些用戶可能會(huì)用手機(jī)拍照并將其放入搜索框或使用智能助手來提問，并不需要親自觸摸設(shè)備。他們可能會(huì)直接輸入一個(gè)問題，并期待一個(gè)對(duì)應(yīng)的回復(fù)，而不僅僅是給出多個(gè)可能答案的網(wǎng)頁列表。

搜索需求的改變對(duì)于以往基于索引系統(tǒng)，依賴關(guān)鍵字匹配給出搜索結(jié)果的傳統(tǒng)搜索引擎是一個(gè)挑戰(zhàn)。

“關(guān)鍵詞搜索算法會(huì)在人們提出問題或拍照并詢問搜索系統(tǒng)'這是什么？' 時(shí)失效”，微軟 Bing 搜索和 AI 團(tuán)隊(duì)的項(xiàng)目經(jīng)理 Rangan Majumder 說到。

當(dāng)然，緊跟用戶的搜索偏好并不是新鮮事，自從網(wǎng)絡(luò)搜索功能出現(xiàn)以來，這一直是一場(chǎng)博弈。但現(xiàn)在，由于人工智能的發(fā)展，包括微軟在人工智能方向取得進(jìn)步，越來越容易滿足這些不斷變化的需求。

“人工智能正在使我們的產(chǎn)品更加符合人的思考習(xí)慣，”Majumder 說， “但在以前人們不得不思考，'當(dāng)我使用計(jì)算機(jī)進(jìn)行搜索時(shí)，如何輸入才能得到自己想要的結(jié)果？'”

微軟已經(jīng)制作完成了最先進(jìn)的人工智能工具之一，并已經(jīng)在 GitHub 上開源，它還將通過微軟的 AI 實(shí)驗(yàn)室發(fā)布這些工具的用戶示例技術(shù)和介紹視頻

這種被稱為空間分治樹與圖（Space Partition Tree And Graph, SPTAG）的算法，允許用戶利用深度學(xué)習(xí)模型來在毫秒內(nèi)搜索數(shù)十億條信息（或稱矢量）。反過來，這意味著他們可以更快地向用戶提供更匹配的結(jié)果。

矢量搜索相較于關(guān)鍵字搜索，可以更容易的按照內(nèi)容得到搜索結(jié)果。例如，如果用戶鍵入“巴黎鐵塔有多高？”Bing 可以返回一個(gè)自然語言結(jié)果告訴用戶艾菲爾鐵塔是 1,063 英尺，即使“搜索查詢”中沒有出現(xiàn)“Eiffel”這個(gè)詞，而“tall”這個(gè)詞也不會(huì)出現(xiàn)在結(jié)果中。

微軟將矢量搜索應(yīng)用于 Bing 搜索引擎，該技術(shù)可以幫助 Bing 更好地理解數(shù)十億網(wǎng)絡(luò)搜索背后的意圖，并在數(shù)十億網(wǎng)頁中找到最匹配的結(jié)果。

使用矢量進(jìn)行更好的搜索

矢量的本質(zhì)上是單詞、圖像像素或其他數(shù)據(jù)點(diǎn)的數(shù)字表示，它有助于捕獲某條數(shù)據(jù)實(shí)際的意義。由于深度學(xué)習(xí)技術(shù)的進(jìn)步，微軟認(rèn)為可以開始使用這些向量來理解和表示搜索意圖。一旦將數(shù)據(jù)點(diǎn)分配給某條數(shù)據(jù)，就可以排列或映射這些向量，其中排列地靠前的數(shù)字表示相似性。這些近端結(jié)果會(huì)顯示給用戶，從而提升搜索結(jié)果。當(dāng)公司工程師注意到用戶搜索模式有異常趨勢(shì)時(shí)，Bing 使用的矢量搜索背后的技術(shù)就會(huì)啟動(dòng)。

“在分析我們的日志時(shí)，團(tuán)隊(duì)發(fā)現(xiàn)搜索查詢字符越來越長(zhǎng)，”Majumder 說。這表明用戶提出了更多問題，對(duì)于之前的搜索問題進(jìn)行更多解釋，對(duì)關(guān)鍵字搜索的體驗(yàn)不佳，或者在描述抽象事物時(shí)“試圖像計(jì)算機(jī)一樣思考”。這些對(duì)用戶來說都是不自然和不方便的。

通過 Bing 搜索，矢量化工作已經(jīng)擴(kuò)展到搜索引擎中超過 1500 億條數(shù)據(jù)，來提升傳統(tǒng)關(guān)鍵字匹配算法的效果，主要包括單個(gè)單詞、字符、網(wǎng)頁代碼段、完整查詢和其他媒體信息。一旦用戶進(jìn)行搜索后，Bing 可以掃描索引向量并提供最佳的匹配結(jié)果。矢量分配使用深度學(xué)習(xí)技術(shù)進(jìn)行訓(xùn)練，然后持續(xù)改進(jìn)。模型會(huì)在搜索后考慮用戶最終點(diǎn)擊的輸入，以便更好地理解搜索的含義。

微軟專家表示，雖然矢量化媒體和搜索數(shù)據(jù)的想法并不新鮮，但最近才有可能在大規(guī)模搜索引擎（如 Bing）上使用它。“Bing 每天會(huì)處理數(shù)十億個(gè)文檔，現(xiàn)在的想法是我們可以將這些條目表示為向量，并在 1000 億個(gè)以上的大規(guī)模索引中進(jìn)行搜索，以便在 5 毫秒內(nèi)找到最匹配結(jié)果?！蔽④?Bing 團(tuán)隊(duì)程序經(jīng)理 Jeffrey Zhu 表示。

為了更直觀的描述這一點(diǎn)，Majumder 詳細(xì)解釋道：一堆可以延伸到月球的 1500 億張的名片中，眨眼之間，可在使用了 SPTAG 算法的 Bing 搜索里一個(gè)接一個(gè)地找到 10 張不同的名片。

搜索算法 SPTAG 及項(xiàng)目簡(jiǎn)介

該項(xiàng)目庫假設(shè)使用向量來表示樣本，并且可以使用 L2 距離或余弦距離來比較向量。為查詢返回的向量是與查詢向量具有最小 L2 距離或余弦距離的向量。

SPTAG 提供兩種方法：kd-tree 和相關(guān)鄰域圖（SPTAG-KDT）與平衡 k-means 樹和相關(guān)鄰域圖（SPTAG-BKT）。 SPTAG-KDT 在索引構(gòu)建成本上更便宜，而 SPTAG-BKT 在高維數(shù)據(jù)中的搜索精度方面更好。

算法流程

SPTAG 的靈感來自 NGS 方法[WangL12]。 它包含兩個(gè)基本模塊：索引構(gòu)建器和搜索器。 RNG 建立在 k 近鄰圖[WangWZTG12，WangWJLZZH14]上，用于提高連接度。平衡的 k 均值樹是用于替換 kd 樹，以避免在高維向量中，kd 樹對(duì)距離估計(jì)不準(zhǔn)確帶來的束縛。搜索首先在空間分治樹中搜索，以找到可以在 RNG 中開始搜索的若干種子數(shù)，然后迭代地在樹和圖中進(jìn)行搜索。

強(qiáng)調(diào)

最新更新：支持在線矢量刪除和插入

分布式服務(wù)：在多臺(tái)計(jì)算機(jī)上搜索

構(gòu)建

環(huán)境配置

安裝

它將在代碼目錄中生成一個(gè) Release 文件夾，其中包含所有構(gòu)建目標(biāo)。

它將在構(gòu)建目錄中生成 SPTAGLib.sln。 在 Visual Studio（至少 2015 年版本）中編譯ALL_BUILD 項(xiàng)目將生成一個(gè)包含所有構(gòu)建目標(biāo)的 Release 目錄。

驗(yàn)證

運(yùn)行 Release 文件夾中的 test（或 Test.exe）以驗(yàn)證所有測(cè)試。

未來

將矢量用于視覺、音頻搜索

Bing 團(tuán)隊(duì)表示，他們希望開源產(chǎn)品以用于企業(yè)或面向消費(fèi)者的應(yīng)用程序，從而識(shí)別基于音頻片段的語言或者用于圖像繁多的服務(wù)，例如讓人們拍攝鮮花等照片的應(yīng)用程序，然后確定它是什么類型的花。對(duì)于這類應(yīng)用，緩慢或不相關(guān)的搜索體驗(yàn)容易失去用戶。

“甚至需要幾秒鐘的搜索都會(huì)使應(yīng)用程序無法使用，”Majumder 指出。該團(tuán)隊(duì)還希望研究人員和學(xué)者能夠利用它來探索其他領(lǐng)域的搜索突破。“我們才開始在這個(gè)深度上探索矢量搜索的真正可能性”。