0
| 本文作者： 夏睿 | 2017-03-06 09:37 |
在用戶日常搜索過程中，一個經(jīng)常出現(xiàn)的問題即大多數(shù)返回的網(wǎng)站結(jié)果擁有完全相同或者幾乎一樣的信息。而應(yīng)用了相似性搜索的相似引擎即可為用戶返回最恰當(dāng)、最合適的結(jié)果，同時隱藏或者丟棄那些重復(fù)的數(shù)據(jù)。
但是，目前相似性搜索領(lǐng)域需要克服的難題即它的規(guī)模和運行速度。雷鋒網(wǎng)近日了解到，F(xiàn)acebook的人工智能研究團隊就稱已在該問題上取得了重要進展。Facebook在新發(fā)布的論文《Billion-scale similarity search with GPUs》中表示，可在GPU 上實現(xiàn)十億規(guī)模級的相似性搜索，并且已開源該方法。
在處理圖像或視頻等復(fù)雜數(shù)據(jù)時會涉及專用數(shù)據(jù)庫系統(tǒng)，而相似性搜索（similarity search）則可以在專用數(shù)據(jù)庫系統(tǒng)中找尋應(yīng)用。但問題是，這些復(fù)雜數(shù)據(jù)通常用高維特征表示，而且需要特定的索引結(jié)構(gòu)。
因此，F(xiàn)acebook的研究人員就通過更好地利用 GPU的優(yōu)勢解決了這個問題 。盡管 GPU 擅長數(shù)據(jù)并行任務(wù)，但之前的方法要么會在并行性不高的算法（如 k-min selection）上遭遇瓶頸，要么不能有效利用內(nèi)存的層次結(jié)構(gòu)。
為此雷鋒網(wǎng)了解到，他們提出一種可用于k-selection的新設(shè)計，使其能以高達性能理論峰值55% 的速度進行運算，并實現(xiàn)了比之前最佳的 GPU 方法快 8.5 倍的最近鄰搜索。他們?yōu)橐苑e量化（product quantization）為基礎(chǔ)的暴力計算、近似和壓縮域搜索提出優(yōu)化設(shè)計，從而將其應(yīng)用到不同的相似性搜索場景中。在所有這些場景中，該方法比之前的方法的最佳表現(xiàn)還要好，它可在 35 分鐘內(nèi)從 Yfcc100M 數(shù)據(jù)集的 9500 萬張圖像上構(gòu)建一個高準(zhǔn)確度的 k-NN 圖，也可以在 12 個小時內(nèi)在 4 個 Maxwell Titan X GPU 上構(gòu)建一個連接了 10 億個向量的圖。
現(xiàn)在Facebook已將該方法（Faiss）開源，使大家能進行比較和重復(fù)利用。
概括的說，該論文的主要突破有：
給出一個可在GPU上運行的k-selection算法。它可在快速寄存奇儲器中運行，并且其靈活性能使它能與其他內(nèi)核一起使用。對此我們給出了復(fù)雜性分析；
在GPU上實現(xiàn)的為精確和近似的k最近鄰搜索的近最優(yōu)算法布局;
通過一系列實驗表明，在單一或多GPU配置中運行的中到大規(guī)模的最近鄰搜索任務(wù)上，我們的方法大幅度優(yōu)于先前技術(shù)。
圖片選自論文（圖片6）：從 Yfcc100M 數(shù)據(jù)集的 9500 萬張圖像上構(gòu)建的高準(zhǔn)確度 k-NN 圖。第一張和最后一張圖片為給定圖片，算法通過計算得出兩張圖片之間最“和諧”的演變路徑。
開源庫Faiss簡介
Faiss 是用于有效的相似性搜索（similarity search）和稠密矢量聚類（clustering of dense vectors）的庫。它包含了可在任何大小向量集合里進行搜索的算法，向量集合的大小甚至可達到RAM容納不下的地步。另外，它還包含了用于評估和參數(shù)調(diào)優(yōu)的支持代碼。Faiss 用 C ++編寫，有 Python / numpy 的完整包裝。其中最有用的一些算法則在 GPU 上實現(xiàn)。
Faiss 包含幾種相似性搜索的方法。它假定示例可以被表示為向量，并可以通過整數(shù)識別。除此之外，這些向量可以與 L2 位距或點積進行比較。與一個查詢向量（query vector）相似的向量是具有最低 L2 位距或最高點積的查詢向量。Faiss 還支持余弦相似性（cosine similarity），因為它屬于標(biāo)準(zhǔn)化向量上的點積。
大多數(shù)方法，例如基于二元向量和緊湊量化代碼的方法，僅使用向量的壓縮表征，并不需要保留原始向量。這通常會降低搜索的準(zhǔn)確性，但這些方法可在單個服務(wù)器上的主存儲器中擴展到數(shù)十億個向量。
該 GPU 實現(xiàn)可接受來自 CPU 或 GPU 內(nèi)存的輸入。在一個帶有 GPU 的服務(wù)器上，其 GPU 索引可以被用作其 CPU 索引的插入替換（比如用 GpuIndexFlatL2 替代 IndexFlatL2），而且來自或發(fā)往 GPU 內(nèi)存的副本可以被自動處理。
Faiss的構(gòu)建
該庫基本上通過 C++ 實現(xiàn)。它帶有可選擇的 GPU （該GPU通過CUDA支持）以及一個可選的 Python 接口。編譯采用的是Makefile。詳細信息可參見INSTALL：
https://github.com/facebookresearch/faiss/blob/master/INSTALL
Faiss的工作原理
Faiss 是圍繞存儲一個向量集的索引類型（index type）構(gòu)建的，并且索引類型提供了一個利用 L2 和/或點積向量比較的函數(shù)，以使該函數(shù)能夠在向量集中進行搜索。有些索引類型是簡單的基線，如精確搜索。大多數(shù)可用的索引結(jié)構(gòu)都對應(yīng)以下幾點權(quán)衡：
搜索時間
搜索質(zhì)量
每個索引向量使用的內(nèi)存大小
訓(xùn)練時間
無監(jiān)督訓(xù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)本研究論文的結(jié)果，可以參考基準(zhǔn) README
https://github.com/facebookresearch/faiss/blob/master/benchs/README.md
相似性搜索延伸閱讀
對相似性搜索不甚了解的同學(xué)，可以參看以下由雷鋒網(wǎng)整理的相似性搜索的延伸閱讀。
相似性搜索的分類：
最鄰近搜索（nearest neighbor search）和范圍查詢（range queries）是相似搜索的重要子分類，研究人員已針對這兩種分類開發(fā)出多種解決方案。
相似性搜索中存在的問題也是搜索復(fù)雜對象時的固有問題。復(fù)雜對象會導(dǎo)致大多數(shù)技術(shù)對大范圍集合的抓取能力等問題。而在相似性搜索時，大部分情況下對象都是復(fù)雜的。
相似性搜索的工作原理：
相似性搜索工具可用于識別哪些候選要素與要匹配的一個或多個輸入要素最相似（或最相異）。相似性的基礎(chǔ)是數(shù)值屬性（感興趣屬性）的指定列表。如果指定了一個以上的要匹配的輸入要素，相似性將基于每個感興趣屬性的平均值。輸出要素類（輸出要素）將包含要匹配的輸入要素以及找到的所有匹配的候選要素，這些要素以相似程度排序（由最相似或最不相似參數(shù)指定）。返回的匹配數(shù)基于結(jié)果數(shù)參數(shù)的值。
相似性搜索的應(yīng)用
相似性搜索在很多場景下都可以發(fā)揮它的優(yōu)勢，比如：
人力資源經(jīng)理可能想要證明其公司薪資水平的合理性。找出在城市規(guī)模、生活成本和便利設(shè)施方面相似的城市后，她便可以查看這些城市的薪資水平，從而確定它們是否與本公司的薪資水平一致。
犯罪分析師希望搜索數(shù)據(jù)庫以查看某罪行是否屬于較重犯罪形式或有重罪趨勢。
課外健身計劃在 A 城極其成功。計劃提倡者期望找到與其計劃推廣的候選城市具有相似特征的其他城市。
執(zhí)法機構(gòu)用此方法揭露毒品種植地或生產(chǎn)地。標(biāo)識具有相似特征的地方可能有助于制定未來的搜索目標(biāo)。
大型零售商不僅擁有數(shù)個成功店鋪，也有少數(shù)業(yè)績不佳的店鋪。找到一些具有相似人口特征和環(huán)境特征（交通便利性、知名度以及商業(yè)互補性等等）的地方有助于標(biāo)識新店的最佳位置。
來源：Facebook 研究院，雷鋒網(wǎng)編譯。
