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