[[210003]]

Facebook 開源的 Faiss(Facebook AI Similarity Search) 的項目，提供了一個相似性搜索的類庫，能夠快速從多媒體文檔中搜索出相似的條目。Facebook 人工智能實驗室(FAIR)基于十億級別的數據集構建了最近鄰搜索算法的實現，這比已知的最快算法還快大約 8.5 倍，因此創造了新的記錄，包括第一個基于十億高維向量構建的 k 最近鄰圖。

Facebook 在今年 3 月份發布了 Facebook AI 相似性搜索(簡稱 Faiss)項目，該項目提供的類庫可以從多媒體文檔中快速搜索出相似的條目——這個場景下的挑戰是基于查詢的傳統搜索引擎無法解決的。Facebook 人工智能實驗室(FAIR)基于十億級別的數據集構建了最近鄰搜索算法的實現，這比之前介紹的已知文獻中在 GPU 上實現的最先進且最快的 k-selection 算法還要快大約 8.5 倍，因此創造了新的記錄，包括第一個基于十億高維向量構建的 k 最近鄰圖。

關于相似性搜索

傳統的數據庫是由包含符號信息的結構化數據表組成。比如，一個圖片集可以表示為一個數據表，每行代表一個被索引的圖片，包含圖片標識符和描述文字之類的信息;每一行也可以與其他數據表中的實體關聯起來，比如某個用戶的一張圖片可以與用戶姓名表建立關聯。

像文本嵌入(word2vec)或者卷積神經網絡(CNN)描述符這樣通過深度學習訓練出的 AI 工具，都可以生成高維向量。這種表示遠比一個固定的符號表示更加強大和靈活，正如后文將解釋的那樣。然而使用 SQL 查詢的傳統數據庫并不適用這些新的表示方式。首先，海量多媒體信息的涌入產生了數十億的向量;其次，且更重要的是，查找相似實體意味著查找相似的高維向量，如果只是使用標準查詢語言這將非常低效和困難。

如何使用向量表示?

假設有一張建筑物的圖片——比如某個你不記得名字的中等規模城市的市政大廳——然后你想在圖片集中查找所有該建筑物的圖片。由于不記得城市的名字，此時傳統 SQL 中常用的 key/value 查詢就幫不上忙了。

這就是相似性搜索的用武之地了。圖片的向量化表示旨在為相似的圖片生成相似向量，這里相似向量定義為歐氏距離最近的向量。

向量化表示的另一個應用是分類。假設需要一個分類器，來判定某個相冊中的哪些圖片屬于菊花。分類器的訓練過程眾所周知：給算法分別輸入菊花的圖片和非菊花的圖片(比如汽車、羊、玫瑰、矢車菊等);如果分類器是線性的，那么就輸出一個分類向量，其屬性值是它與圖片向量的點積，反映了該圖片包含菊花的可能性;然后分類器可以與相冊中所有圖片計算點積，并返回點積最大的圖片。這種查詢就是“最大內積”搜索。

所以，對于相似性搜索和分類，我們需要做下列處理：

• 給定一個查詢向量，返回與該向量的歐式距離最近的數據庫對象列表。
• 給定一個查詢向量，返回與該向量點積最大的數據庫對象列表。

一個額外的挑戰是，要在一個超大規模比如數十億向量上做這些運算。

軟件包

現有軟件工具都不足以完成上述數據庫檢索操作。傳統的 SQL 數據庫系統也不太適合，因為它們是為基于哈希的檢索或 1 維區間檢索而優化的;像 OpenCV 等軟件包中的相似性搜索功能在擴展性方面則嚴重受限;同時其他的相似性搜索類庫主要適用于小規模數據集(比如，1 百萬大小的向量);另外的軟件包基本是為發表論文而輸出的學術研究產物，旨在展示某些特定設置下的效果。

Faiss 類庫則解決了以上提到的種種局限，其優點如下：

• 提供了多種相似性搜索方法，支持各種各樣的不同用法和功能集。
• 特別優化了內存使用和速度。
• 為最相關索引方法提供了最先進的 GPU 實現。

相似性搜索評估

一旦從學習系統(從圖片、視頻、文本文件以及其他地方)抽取出向量，就能準備將其用于相似性搜索類庫。

我們有一個暴力算法作為參考對比，該算法計算出了所有的相似度——非常精確和齊全——然后返回最相似的元素列表。這就提供了一個黃金標準的參考結果列表。需要注意的是，暴力算法的高效實現并不簡單，一般依賴于其他組件的性能。

如果犧牲一些精度的話，比如允許與參考結果有一點點偏差，那么相似性搜索能快幾個數量級。舉個例子，如果一張圖片的相似性搜索結果中的第一個和第二個交換了，可能并沒有太大問題，因為對于一個給定的查詢，它們可能都是正確結果。加快搜索速度還涉及到數據集的預處理，我們通常把這個預處理操作稱作索引。

這樣一來我們就關注到下面三個指標：

速度。找到與查詢最相似的 10 個或更多個向量要耗時多久?期望比暴力算法耗時更少，不然索引的意義何在?

內存消耗。該方法需要消耗多少 RAM?比原始向量更多還是更少?Faiss 支持只在 RAM 上搜索，而磁盤數據庫就會慢幾個數量級，即便是 SSD 也是一樣。

精確度。返回的結果列表與暴力搜索結果匹配程度如何?精確度可以這樣評估，計算返回的真正最近鄰結果在查詢結果第一位(這個指標一般叫做 1-recall@1)的數量，或者衡量返回結果前 10 個(即指標 10-intersection)中包含 10 個最近鄰結果的平均占比。

通常我們都會在確定的內存資源下在速度和精準度之間權衡。Faiss 專注于壓縮原始向量的方法，因為這是擴展到數十億向量數據集的不二之選：當必須索引十億個向量的時候，每個向量 32 字節，就會消耗很大的內存。

許多索引類庫適用于百萬左右向量的小規模數據集，比如 nmslib 就包含了一些適于這種規模數據的非常高效的算法，這比 Faiss 快很多，但需要消耗更多的存儲。

基于 10 億向量的評估

由于工程界并沒有針對這種大小數據集的公認基準，所以我們就基于研究結果來評估。

評估精度基于 Deep1B，這是一個包含 10 億圖片的數據集。每張圖片已通過 CNN 處理，CNN 激活圖之一用于圖片描述。比較這些向量之間的歐氏距離，就能量化圖片的相似程度。

Deep1B 還帶有一個較小的查詢圖片集，以及由暴力算法產生的真實相似性搜索結果。因此，如果運行一個搜索算法，就能評估結果中的 1-recall@1。

選擇索引

為了評估，我們把內存限制在 30G 以內。這個內存約束是我們選擇索引方法和參數的依據。Faiss 中的索引方法表示為一個字符串，在本例中叫做 OPQ20_80,IMI2x14,PQ20。

該字符串包含的信息有，作用到向量上的預處理步驟(OPQ20_80)，一個選擇機制(IMI2x14)表明數據庫如何分區，以及一個編碼組件(PQ20)表示向量編碼時使用一個產品量化器(PQ)來生成一個 20 字節的編碼。所以在內存使用上，包括其他開銷，累計少于 30G。

這聽起來技術性較強，所以 Faiss 文檔提供了使用指南，來說明如何選擇滿足需求的最佳索引。

選好了索引類型，就可以開始執行索引過程了。Faiss 中的算法實現會處理 10 億向量并把它們置于一個索引庫中。索引會存在磁盤上或立即使用，檢索和增加 / 移除索引的操作可以穿插進行。

查詢索引

當索引準備好以后，一系列搜索時間參數就會被設置來調整算法。為方便評估，這里使用單線程搜索。由于內存消耗是受限并固定的，所以需要在精確度和搜索時間之間權衡優化。舉例說來，這表示為了獲取 40% 的 1-recall@1，可以設置參數以花費盡可能短的搜索時間。

幸運的是，Faiss 帶有一個自動調優機制，能掃描參數空間并收集提供最佳操作點的參數;也就是說，最可能的搜索時間對應某個精確度，反之亦然，最優的精確度對應某個搜索時間。Deep1B 中操作點被可視化為如下圖示：

本圖中我們可以看到，達到 40% 的 1-recall@1，要求每次查詢耗時必須小于 2ms，或者能優化到耗時 0.5ms 的話，就可以達到 30% 的 1-recall@1。一次查詢耗時 2ms 表示單核 500 QPS 的處理能力。

這個結果基本上能媲美目前業內最新研究成果了，即 Babenko 和 Lempitsky 在 CVPR 2016 發表的論文“Efficient Indexing of Billion-Scale Datasets of Deep Descriptors”，這篇論文介紹了 Deep1B 數據集，他們達到 45% 的 1-recall@1 需要耗時 20ms。

10 億級數據集的 GPU

計算GPU 實現方面也做了很大的投入，在原生多 GPU 的支持下能產出驚人的單機性能。GPU 實現已經可以作為對應 CPU 設備的替代，無需了解 CUDA API 就能挖掘出 GPU 的性能。Faiss 支持所有 Nvidia 2012 之后發布的 GPU(Kepler，計算能力 3.5+)。

我們把 roofline model 作為指南，它指出應當盡量讓內存帶寬或浮點運算單元滿載。Faiss 的 GPU 實現在單 GPU 上的性能要比對應的 CPU 實現快 5 到 10 倍，像英偉達 P100 這樣的新型 Pascal 架構硬件甚至會快 20 倍以上。

一些性能關鍵數字：

• 對于近似的索引，使用 YFCC100M 數據集中的 9500 萬張圖片，一個基于 128D CNN 描述符的暴力 k 近鄰圖(k=10)，只需 4 個 Maxwell Titan X GPU 就能在 35 分鐘內構建完成，包括索引構建時間。
• 十億級向量的 k 近鄰圖現在觸手可及?；?Deep1B 數據集，可以構建一個暴力 k-NN 圖(k=10)，達到 0.65 的 10-intersection，需要使用 4 個 Maxwell Titan X GPU 花費不到 12 小時，或者達到 0.8，使用 8 個 Pascal P100-PCIe GPU 消耗不到 12 小時。Titan X 配置可以在不到 5 小時生成低質量的圖。
• 其他組件也表現出了驕人的性能。比如，構建上述 Deep1B 索引需要使用 k 均值聚類 6701 萬個 120 維的向量到 262,144 個簇，對于 25 E-M 迭代需要在 4 個 Titan X GPU(12.6 tflop/s)上花 139 分鐘，或者在 8 個 P100 GPU(40 tflop/s)上花 43.8 分鐘。注意聚類的訓練數據集并不需要放在 GPU 內存中，因為數據可以在需要時流到 GPU 而沒有額外的性能影響。

底層實現

Facebook AI 研究團隊 2015 年就開始開發 Faiss，這建立在許多研究成果和大量工程實踐的基礎之上。對于 Faiss 類庫，我們選擇聚焦在一些基礎技術方面的優化，特別是在 CPU 方面，我們重度使用了：

• 采用多線程來利用多核資源，并在多個 GPU 上執行并行檢索。
• 使用 BLAS 類庫通過矩陣和矩陣乘法來高效精準地完成距離計算。一個不采用 BLAS 的暴力實現很難達到最優。BLAS/LAPACK 是 Faiss 唯一強制依賴的軟件。
• 采用機器 SIMD 向量化和 popcount 加速獨立向量的距離計算。

關于 GPU

對于前述相似性搜索的 GPU 實現，k-selection(查找 k 個最小或最大元素)有一個性能問題，因為傳統 CPU 算法(比如堆查找算法)對 GPU 并不友好。針對 Faiss GPU，我們設計了文獻中已知的最快輕量 k-selection 算法(k<=1024)。所有的中間狀態全部保存在寄存器，方便高速讀寫?？梢詫斎霐祿淮涡酝瓿?k-select，運行至高達 55% 的理論峰值性能，作為輸出的峰值 GPU 內存帶寬。因為其狀態單獨保存在寄存器文件中，所以與其他內核很容易集成，使它成為極速的精準和近似檢索算法。

大量的精力投在了為高效策略做鋪墊，以及近似搜索的內核實現。通過數據分片或數據副本可以提供對多核 GPU 支持，而不會受限于單 GPU 的可用顯存大小;還提供了對半精度浮點數的支持(float16)，可在支持的 GPU 上做完整 float16 運算，以及早期架構上提供的中間 float16 存儲。我們發現以 float16 編碼向量技術可以做到精度無損加速。

簡而言之，對關鍵因素的不斷突破在實踐中非常重要，Faiss 確實在工程細節方面下了很大的功夫。

開始使用 Faiss

Faiss 使用 C++ 實現，并支持 Python。只要從 Github 下載源碼并編譯，然后在 Python 中導入 Faiss 模塊即可開始使用。Faiss 還完整集成了 Numpy，并支持構造 numpy(使用 float32)數組的所有函數。

獲取 Faiss:

https://github.com/facebookresearch/faiss

索引對象Faiss(包括 C++ 和 Python)提供了索引 Index 的實例。每個 Index 子類實現一個索引結構，以說明哪些向量可被加入和搜索。比如，IndexFlatL2 是一個能使用 L2 距離搜索的暴力索引。

這樣會打印出索引向量的數量。增加到一個 IndexFlat 僅僅表示拷貝它們到索引的內部存儲，因為后面沒有其他操作會作用在該向量上。

執行一次搜索：

I 是一個整型矩陣，輸出后是這樣的：

對于 xq 的第一個向量，xb 中最相似向量的索引是 0(從 0 開始)，第二相似的是 #393，第三是 #363。對于 xq 的第二個向量，相似向量列表是 #1， #555 等等。本例中，xq 的前三個向量看起來與 xb 的前三個向量一樣。

矩陣 D 是一個平方距離矩陣，與 I 的大小一致，表示對于每個結果向量查詢的平方歐氏距離。

Faiss 實現了十多個由其他索引組合的索引類型?？蛇x的 GPU 版本有完全相同的接口，并有通道在 CPU 和 CPU 索引之間互通。Python 接口主要由 C++ 生成以凸顯 C++ 索引，所以可以很容易地將 Python 驗證代碼轉換為集成的 C++ 代碼。