終於把微軟BING搜索-SPTAG演算法的原理搞清了

作者 | beyondma

轉載自 CSDN 博客

近日，微軟在GitHub上開源了其BING的搜索演算法SPTAG，github地址：https://github.com/microsoft/SPTAG。這個演算法筆者簡單看了一下，的確是很有價值可以看大家介紹下，這種稱為SPTAG （Space Partition Tree And Graph）目前的翻譯多稱為「空間分區式的樹和圖」，其實個人認為這種說法不太準確，其實這裡的圖與圖論中的圖意思一致，表示的是連接關係，並不是圖像的意思，，而且我們一會仔細也會發現其演算法中還帶有平衡（balance)的概念，感覺譯為」高維空間平衡樹「更為準確。

SPTAG能做什麼

微軟在github上的介紹中給出的官方解釋如下「This library assumes that the samples are represented as vectors and that the vectors can be compared by L2 distances or cosine distances. Vectors returned for a query vector are the vectors that have smallest L2 distance or cosine distances with the query vector. "

簡單解釋一下，就是微軟認為圖像、聲音文字都能被表示為向量，而且可以用L2距離及餘弦距離（cosine distances）表示其關係。這段我給讀者解釋一下，什麼叫可以用餘弦距離表示向量之間的關係。

那麼如果我把上述這四個圖都轉化為了向量，那麼會有

vec圖2-vec圖1=vec圖4-vec圖3

也就是說在圖片轉化為向量後，向量的位置關係保留了其圖片含義所代表的邏輯關係。這就是」L2距離及餘弦距離（cosine distances）表示其關係「的具體解釋。

那麼說到現在我們可以了解SPTAG演算法工作的前提就是將已經將用戶搜索的要素轉化為了正確位置上的向量，SPTAG就是要找到這個向量在空間上的最近鄰，說到這讀者是否對SPTAG的工作方式有了更進一步的認識了呢。

SPTAG工作原理簡述

對於搜索演算法有了解的同學可能都會了解，搜索演算法中一般有索引（index)和查尋(search)兩個重要部分組成。SPTAG的索引（index)演算法是基於kd-tree的。

kd-tree聽起來很高大上，其實他在於一維空間上的情況就是」平衡二叉樹「，在高維空間上kd-tree會用第k維的大小來決定一個元素應該插入左子樹還是右子樹，同時為保持tree的平衡，剩餘未進入tree的元素除第k維外方差最小。SPTAG正是以此來加速演算法的速度。

kmeans其實就是一種自動聚類的方法，演算法先隨機指定選取K個點做為初始聚集的簇心,分別計算每個樣本點到 K個簇核心的餘弦距離，找到距離最近的核心點，將它歸屬到對應的簇，所有點都歸屬到簇之後， M個點就分為了 K個簇。之後重新計算每個簇的重心，將其定為新的「核心」，重複上述步驟直到新核心不再改變為止或者改變距離達到一定值後中止。那麼最終的K個簇就是最終的聚類結果。

SPTAG 正是集合了kd-tree 和 kmeans 兩種演算法的精華，才允許用戶利用深度學習模型在幾毫秒內搜索數十億條信息。

（*本文為 AI科技大本營轉載文章，轉載請聯繫作者）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！