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

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

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

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

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

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

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

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

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

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

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

開源庫(kù)Faiss簡(jiǎn)介

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

Faiss 包含幾種相似性搜索的方法。它假定示例可以被表示為向量，并可以通過整數(shù)識(shí)別。除此之外，這些向量可以與 L2 位距或點(diǎn)積進(jìn)行比較。與一個(gè)查詢向量（query vector）相似的向量是具有最低 L2 位距或最高點(diǎn)積的查詢向量。Faiss 還支持余弦相似性（cosine similarity），因?yàn)樗鼘儆跇?biāo)準(zhǔn)化向量上的點(diǎn)積。

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

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

Faiss的構(gòu)建

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

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

Faiss的工作原理

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

• 搜索時(shí)間

• 搜索質(zhì)量

• 每個(gè)索引向量使用的內(nèi)存大小

• 訓(xùn)練時(shí)間

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

獲取Faiss 完整版文檔

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

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

• doxygen 文檔提供了每個(gè)類的信息：

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

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

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

相似性搜索延伸閱讀

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

相似性搜索的分類：

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

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

相似性搜索的工作原理：

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

相似性搜索的應(yīng)用

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

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

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

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

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

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

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

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