不斷向開源社區添磚加瓦的微軟近日又有大動作– 將強大的最近鄰搜索算法開源。2019年5月15日，GitHub存儲庫上的開源社區成員都可以訪問微軟的空間分區樹和圖（SPTAG）算法，該算法“允許用戶充分利用學習模型在以毫秒為單位時間內智能搜索數十億條信息（也稱矢量）。”

我們每個人每天都在享受各種在線服務（在線搜索、新聞推薦等）所帶來的種種便利。這些服務的背後隱藏著龐大的、需要計算機實時處理的數據。例如，在圖像搜索領域，面對給定的一幅查詢圖像，系統要從龐大的數據庫裡（比如包含百萬、千萬甚至上億圖像）快速找出相似的圖像；而在新聞推薦中，計算機也需要根據用戶畫像，從大量的新聞中找到最相關的新聞推薦給用戶。

想要從海量數據中快速找到有效數據離不開最近鄰搜索算法。最近鄰搜索是計算機視覺、機器學習、多媒體搜索、計算幾何等領域裡非常基礎、也是非常重要的問題。目前主要有兩種減少搜索時間的方法：基於哈希的近似最近鄰搜索的方法通過設計和優化哈希函數，減少計算的次數，從而縮短搜索時間。基於量化的近似最近鄰搜索方法則通過聚類把向量集聚成若干類，每類裡面的向量用對應的類中心來近似。

圖1: 哈希和量化對比的二維案例。左：量化的距離更加豐富；右：量化需要的比特數目少。

而今天微軟在GitHub上開源了基於近鄰圖的最近鄰搜索算法–空間分區樹和圖（SPTAG），它是Bing搜索的底層人工智能技術之一。現在你在Bing上搜索“巴黎的塔樓有多高？”他們會告訴你艾菲爾鐵塔高324米（1,063英尺），與81層高的建築大致相同。儘管在搜索關鍵詞中並沒有出現“埃菲爾”（Eiffel）這個單詞，而且在搜索結果中也沒有“高”（tall）這個單詞。

該公司在今天的公告中寫道：“僅在幾年前，網絡搜索很簡單。用戶輸入幾個單詞並瀏覽結果頁面。今天，相同的用戶可能會在手機上拍照並將其放入搜索框中，或使用智能助手提問而無需親自觸摸設備。他們也可能會輸入一個問題並期待一個實際的答复，而不是一個可能答案的頁面列表。”

當然，矢量搜索本身並不是一個新想法。然而，微軟所做的是將這一概念應用於深度學習模型。首先，團隊採用預先訓練的模型並將數據編碼到矢量中，其中每個矢量代表一個字或像素。然後使用新的SPTAG庫生成向量索引。隨著查詢的進入，深度學習模型將該文本或圖像轉換為向量，並且庫在該索引中找到最相關的向量。

微軟表示，“通過Bing搜索，矢量化工作已經擴展到搜索引擎索引的超過1500億條數據，從而帶來了對傳統關鍵字匹配的改進。” “這些包括單個單詞，字符，網頁摘要，完整查詢和其他媒體。一旦用戶搜索，Bing就可以掃描索引的向量並提供最佳匹配。“