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而沒有額外的性能影響。底層實現
采用多線程來利用多核資源，并在多個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距離搜索的暴力索引。
import faiss # 導入faissindex = faiss.IndexFlatL2(d) # 構建索引，d是向量大小# here we assume xb contains a n-by-d numpy matrix of type float32index.add(xb) # 把向量加入索引print index.ntotal這樣會打印出索引向量的數量。增加到一個IndexFlat僅僅表示拷貝它們到索引的內部存儲，因為后面沒有其他操作會作用在該向量上。
執行一次搜索：
# xq is a n2-by-d matrix with query vectorsk = 4 # 需要4個相似向量D, I = index.search(xq, k) # 實際搜索print II是一個整型矩陣，輸出后是這樣的：
[[ 0 393 363 78] [ 1 555 277 364] [ 2 304 101 13]]對于xq的第一個向量，xb中最相似向量的索引是0（從0開始），第二相似的是 #393，第三是 #363。對于xq的第二個向量，相似向量列表是 #1， #555 等等。本例中，xq的前三個向量看起來與xb的前三個向量一樣。
矩陣D是一個平方距離矩陣，與I的大小一致，表示對于每個結果向量查詢的平方歐氏距離。
Faiss實現了十多個由其他索引組合的索引類型。可選的GPU版本有完全相同的接口，并有通道在CPU和CPU索引之間互通。Python接口主要由C++生成以凸顯C++索引，所以可以很容易地將Python驗證代碼轉換為集成的C++代碼。
查看英文原文：https://code.facebook.com/posts/1373769912645926/faiss-a-library-for-efficient-similarity-search/
京公網安備 11010502049343號