在用戶日常搜索過程中，一個經(jīng)常出現(xiàn)的問題即大多數(shù)返回的網(wǎng)站結果擁有完全相同或者幾乎一樣的信息。而應用了相似性搜索的相似引擎即可為用戶返回最恰當、最合適的結果，同時隱藏或者丟棄那些重復的數(shù)據(jù)。

但是，目前相似性搜索領域需要克服的難題即它的規(guī)模和運行速度。雷鋒網(wǎng)近日了解到，F(xiàn)acebook的人工智能研究團隊就稱已在該問題上取得了重要進展。Facebook在新發(fā)布的論文《Billion-scale similarity search with GPUs》中表示，可在GPU 上實現(xiàn)十億規(guī)模級的相似性搜索，并且已開源該方法。

在處理圖像或視頻等復雜數(shù)據(jù)時會涉及專用數(shù)據(jù)庫系統(tǒng)，而相似性搜索（similarity search）則可以在專用數(shù)據(jù)庫系統(tǒng)中找尋應用。但問題是，這些復雜數(shù)據(jù)通常用高維特征表示，而且需要特定的索引結構。

因此，F(xiàn)acebook的研究人員就通過更好地利用 GPU的優(yōu)勢解決了這個問題 。盡管 GPU 擅長數(shù)據(jù)并行任務，但之前的方法要么會在并行性不高的算法（如 k-min selection）上遭遇瓶頸，要么不能有效利用內存的層次結構。

為此雷鋒網(wǎng)了解到，他們提出一種可用于k-selection的新設計，使其能以高達性能理論峰值55% 的速度進行運算，并實現(xiàn)了比之前最佳的 GPU 方法快 8.5 倍的最近鄰搜索。他們?yōu)橐苑e量化（product quantization）為基礎的暴力計算、近似和壓縮域搜索提出優(yōu)化設計，從而將其應用到不同的相似性搜索場景中。在所有這些場景中，該方法比之前的方法的最佳表現(xiàn)還要好，它可在 35 分鐘內從 Yfcc100M 數(shù)據(jù)集的 9500 萬張圖像上構建一個高準確度的 k-NN 圖，也可以在 12 個小時內在 4 個 Maxwell Titan X GPU 上構建一個連接了 10 億個向量的圖。

現(xiàn)在Facebook已將該方法（Faiss）開源，使大家能進行比較和重復利用。

概括的說，該論文的主要突破有：

• 給出一個可在GPU上運行的k-selection算法。它可在快速寄存奇儲器中運行，并且其靈活性能使它能與其他內核一起使用。對此我們給出了復雜性分析；

• 在GPU上實現(xiàn)的為精確和近似的k最近鄰搜索的近最優(yōu)算法布局;

• 通過一系列實驗表明，在單一或多GPU配置中運行的中到大規(guī)模的最近鄰搜索任務上，我們的方法大幅度優(yōu)于先前技術。

圖片選自論文（圖片6）：從 Yfcc100M 數(shù)據(jù)集的 9500 萬張圖像上構建的高準確度 k-NN 圖。第一張和最后一張圖片為給定圖片，算法通過計算得出兩張圖片之間最“和諧”的演變路徑。

開源庫Faiss簡介

Faiss 是用于有效的相似性搜索（similarity search）和稠密矢量聚類（clustering of dense vectors）的庫。它包含了可在任何大小向量集合里進行搜索的算法，向量集合的大小甚至可達到RAM容納不下的地步。另外，它還包含了用于評估和參數(shù)調優(yōu)的支持代碼。Faiss 用 C ++編寫，有 Python / numpy 的完整包裝。其中最有用的一些算法則在 GPU 上實現(xiàn)。

Faiss 包含幾種相似性搜索的方法。它假定示例可以被表示為向量，并可以通過整數(shù)識別。除此之外，這些向量可以與 L2 位距或點積進行比較。與一個查詢向量（query vector）相似的向量是具有最低 L2 位距或最高點積的查詢向量。Faiss 還支持余弦相似性（cosine similarity），因為它屬于標準化向量上的點積。

大多數(shù)方法，例如基于二元向量和緊湊量化代碼的方法，僅使用向量的壓縮表征，并不需要保留原始向量。這通常會降低搜索的準確性，但這些方法可在單個服務器上的主存儲器中擴展到數(shù)十億個向量。

該 GPU 實現(xiàn)可接受來自 CPU 或 GPU 內存的輸入。在一個帶有 GPU 的服務器上，其 GPU 索引可以被用作其 CPU 索引的插入替換（比如用 GpuIndexFlatL2 替代 IndexFlatL2），而且來自或發(fā)往 GPU 內存的副本可以被自動處理。

Faiss的構建

該庫基本上通過 C++ 實現(xiàn)。它帶有可選擇的 GPU （該GPU通過CUDA支持）以及一個可選的 Python 接口。編譯采用的是Makefile。詳細信息可參見INSTALL：

https://github.com/facebookresearch/faiss/blob/master/INSTALL

Faiss的工作原理

Faiss 是圍繞存儲一個向量集的索引類型（index type）構建的，并且索引類型提供了一個利用 L2 和/或點積向量比較的函數(shù)，以使該函數(shù)能夠在向量集中進行搜索。有些索引類型是簡單的基線，如精確搜索。大多數(shù)可用的索引結構都對應以下幾點權衡：

• 搜索時間

• 搜索質量

• 每個索引向量使用的內存大小

• 訓練時間

• 無監(jiān)督訓練對外部數(shù)據(jù)的需求

獲取Faiss 完整版文檔

• 完整文檔（包括一個指南）可以參閱 GitHub 的 wiki 頁：

  http://github.com/facebookresearch/faiss/wiki

• doxygen 文檔提供了每個類的信息：

       http://rawgithub.com/facebookresearch/faiss/master/docs/html/annotated.html

• 重現(xiàn)本研究論文的結果，可以參考基準 README

       https://github.com/facebookresearch/faiss/blob/master/benchs/README.md

相似性搜索延伸閱讀

對相似性搜索不甚了解的同學，可以參看以下由雷鋒網(wǎng)整理的相似性搜索的延伸閱讀。

相似性搜索的分類：

最鄰近搜索（nearest neighbor search）和范圍查詢（range queries）是相似搜索的重要子分類，研究人員已針對這兩種分類開發(fā)出多種解決方案。

相似性搜索中存在的問題也是搜索復雜對象時的固有問題。復雜對象會導致大多數(shù)技術對大范圍集合的抓取能力等問題。而在相似性搜索時，大部分情況下對象都是復雜的。

相似性搜索的工作原理：

相似性搜索工具可用于識別哪些候選要素與要匹配的一個或多個輸入要素最相似（或最相異）。相似性的基礎是數(shù)值屬性（感興趣屬性）的指定列表。如果指定了一個以上的要匹配的輸入要素，相似性將基于每個感興趣屬性的平均值。輸出要素類（輸出要素）將包含要匹配的輸入要素以及找到的所有匹配的候選要素，這些要素以相似程度排序（由最相似或最不相似參數(shù)指定）。返回的匹配數(shù)基于結果數(shù)參數(shù)的值。

相似性搜索的應用

相似性搜索在很多場景下都可以發(fā)揮它的優(yōu)勢，比如：

• 人力資源經(jīng)理可能想要證明其公司薪資水平的合理性。找出在城市規(guī)模、生活成本和便利設施方面相似的城市后，她便可以查看這些城市的薪資水平，從而確定它們是否與本公司的薪資水平一致。

• 犯罪分析師希望搜索數(shù)據(jù)庫以查看某罪行是否屬于較重犯罪形式或有重罪趨勢。

• 課外健身計劃在 A 城極其成功。計劃提倡者期望找到與其計劃推廣的候選城市具有相似特征的其他城市。

• 執(zhí)法機構用此方法揭露毒品種植地或生產(chǎn)地。標識具有相似特征的地方可能有助于制定未來的搜索目標。

• 大型零售商不僅擁有數(shù)個成功店鋪，也有少數(shù)業(yè)績不佳的店鋪。找到一些具有相似人口特征和環(huán)境特征（交通便利性、知名度以及商業(yè)互補性等等）的地方有助于標識新店的最佳位置。

來源：Facebook 研究院，雷鋒網(wǎng)編譯。

雷峰網(wǎng)版權文章，未經(jīng)授權禁止轉載。詳情見轉載須知。