[[210003]]

Facebook 開(kāi)源的 Faiss(Facebook AI Similarity Search) 的項(xiàng)目，提供了一個(gè)相似性搜索的類庫(kù)，能夠快速?gòu)亩嗝襟w文檔中搜索出相似的條目。Facebook 人工智能實(shí)驗(yàn)室(FAIR)基于十億級(jí)別的數(shù)據(jù)集構(gòu)建了最近鄰搜索算法的實(shí)現(xiàn)，這比已知的最快算法還快大約 8.5 倍，因此創(chuàng)造了新的記錄，包括第一個(gè)基于十億高維向量構(gòu)建的 k 最近鄰圖。

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

關(guān)于相似性搜索

傳統(tǒng)的數(shù)據(jù)庫(kù)是由包含符號(hào)信息的結(jié)構(gòu)化數(shù)據(jù)表組成。比如，一個(gè)圖片集可以表示為一個(gè)數(shù)據(jù)表，每行代表一個(gè)被索引的圖片，包含圖片標(biāo)識(shí)符和描述文字之類的信息;每一行也可以與其他數(shù)據(jù)表中的實(shí)體關(guān)聯(lián)起來(lái)，比如某個(gè)用戶的一張圖片可以與用戶姓名表建立關(guān)聯(lián)。

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

如何使用向量表示?

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

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

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

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

• 給定一個(gè)查詢向量，返回與該向量的歐式距離最近的數(shù)據(jù)庫(kù)對(duì)象列表。
• 給定一個(gè)查詢向量，返回與該向量點(diǎn)積最大的數(shù)據(jù)庫(kù)對(duì)象列表。

一個(gè)額外的挑戰(zhàn)是，要在一個(gè)超大規(guī)模比如數(shù)十億向量上做這些運(yùn)算。

軟件包

現(xiàn)有軟件工具都不足以完成上述數(shù)據(jù)庫(kù)檢索操作。傳統(tǒng)的 SQL 數(shù)據(jù)庫(kù)系統(tǒng)也不太適合，因?yàn)樗鼈兪菫榛诠５臋z索或 1 維區(qū)間檢索而優(yōu)化的;像 OpenCV 等軟件包中的相似性搜索功能在擴(kuò)展性方面則嚴(yán)重受限;同時(shí)其他的相似性搜索類庫(kù)主要適用于小規(guī)模數(shù)據(jù)集(比如，1 百萬(wàn)大小的向量);另外的軟件包基本是為發(fā)表論文而輸出的學(xué)術(shù)研究產(chǎn)物，旨在展示某些特定設(shè)置下的效果。

Faiss 類庫(kù)則解決了以上提到的種種局限，其優(yōu)點(diǎn)如下：

• 提供了多種相似性搜索方法，支持各種各樣的不同用法和功能集。
• 特別優(yōu)化了內(nèi)存使用和速度。
• 為最相關(guān)索引方法提供了最先進(jìn)的 GPU 實(shí)現(xiàn)。

相似性搜索評(píng)估

一旦從學(xué)習(xí)系統(tǒng)(從圖片、視頻、文本文件以及其他地方)抽取出向量，就能準(zhǔn)備將其用于相似性搜索類庫(kù)。

我們有一個(gè)暴力算法作為參考對(duì)比，該算法計(jì)算出了所有的相似度——非常精確和齊全——然后返回最相似的元素列表。這就提供了一個(gè)黃金標(biāo)準(zhǔn)的參考結(jié)果列表。需要注意的是，暴力算法的高效實(shí)現(xiàn)并不簡(jiǎn)單，一般依賴于其他組件的性能。

如果犧牲一些精度的話，比如允許與參考結(jié)果有一點(diǎn)點(diǎn)偏差，那么相似性搜索能快幾個(gè)數(shù)量級(jí)。舉個(gè)例子，如果一張圖片的相似性搜索結(jié)果中的第一個(gè)和第二個(gè)交換了，可能并沒(méi)有太大問(wèn)題，因?yàn)閷?duì)于一個(gè)給定的查詢，它們可能都是正確結(jié)果。加快搜索速度還涉及到數(shù)據(jù)集的預(yù)處理，我們通常把這個(gè)預(yù)處理操作稱作索引。

這樣一來(lái)我們就關(guān)注到下面三個(gè)指標(biāo)：

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

內(nèi)存消耗。該方法需要消耗多少 RAM?比原始向量更多還是更少?Faiss 支持只在 RAM 上搜索，而磁盤數(shù)據(jù)庫(kù)就會(huì)慢幾個(gè)數(shù)量級(jí)，即便是 SSD 也是一樣。

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

通常我們都會(huì)在確定的內(nèi)存資源下在速度和精準(zhǔn)度之間權(quán)衡。Faiss 專注于壓縮原始向量的方法，因?yàn)檫@是擴(kuò)展到數(shù)十億向量數(shù)據(jù)集的不二之選：當(dāng)必須索引十億個(gè)向量的時(shí)候，每個(gè)向量 32 字節(jié)，就會(huì)消耗很大的內(nèi)存。

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

基于 10 億向量的評(píng)估

由于工程界并沒(méi)有針對(duì)這種大小數(shù)據(jù)集的公認(rèn)基準(zhǔn)，所以我們就基于研究結(jié)果來(lái)評(píng)估。

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

Deep1B 還帶有一個(gè)較小的查詢圖片集，以及由暴力算法產(chǎn)生的真實(shí)相似性搜索結(jié)果。因此，如果運(yùn)行一個(gè)搜索算法，就能評(píng)估結(jié)果中的 1-recall@1。

選擇索引

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

該字符串包含的信息有，作用到向量上的預(yù)處理步驟(OPQ20_80)，一個(gè)選擇機(jī)制(IMI2x14)表明數(shù)據(jù)庫(kù)如何分區(qū)，以及一個(gè)編碼組件(PQ20)表示向量編碼時(shí)使用一個(gè)產(chǎn)品量化器(PQ)來(lái)生成一個(gè) 20 字節(jié)的編碼。所以在內(nèi)存使用上，包括其他開(kāi)銷，累計(jì)少于 30G。

這聽(tīng)起來(lái)技術(shù)性較強(qiáng)，所以 Faiss 文檔提供了使用指南，來(lái)說(shuō)明如何選擇滿足需求的最佳索引。

選好了索引類型，就可以開(kāi)始執(zhí)行索引過(guò)程了。Faiss 中的算法實(shí)現(xiàn)會(huì)處理 10 億向量并把它們置于一個(gè)索引庫(kù)中。索引會(huì)存在磁盤上或立即使用，檢索和增加 / 移除索引的操作可以穿插進(jìn)行。

查詢索引

當(dāng)索引準(zhǔn)備好以后，一系列搜索時(shí)間參數(shù)就會(huì)被設(shè)置來(lái)調(diào)整算法。為方便評(píng)估，這里使用單線程搜索。由于內(nèi)存消耗是受限并固定的，所以需要在精確度和搜索時(shí)間之間權(quán)衡優(yōu)化。舉例說(shuō)來(lái)，這表示為了獲取 40% 的 1-recall@1，可以設(shè)置參數(shù)以花費(fèi)盡可能短的搜索時(shí)間。

幸運(yùn)的是，F(xiàn)aiss 帶有一個(gè)自動(dòng)調(diào)優(yōu)機(jī)制，能掃描參數(shù)空間并收集提供最佳操作點(diǎn)的參數(shù);也就是說(shuō)，最可能的搜索時(shí)間對(duì)應(yīng)某個(gè)精確度，反之亦然，最優(yōu)的精確度對(duì)應(yīng)某個(gè)搜索時(shí)間。Deep1B 中操作點(diǎn)被可視化為如下圖示：

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

這個(gè)結(jié)果基本上能媲美目前業(yè)內(nèi)最新研究成果了，即 Babenko 和 Lempitsky 在 CVPR 2016 發(fā)表的論文“Efficient Indexing of Billion-Scale Datasets of Deep Descriptors”，這篇論文介紹了 Deep1B 數(shù)據(jù)集，他們達(dá)到 45% 的 1-recall@1 需要耗時(shí) 20ms。

10 億級(jí)數(shù)據(jù)集的 GPU

計(jì)算GPU 實(shí)現(xiàn)方面也做了很大的投入，在原生多 GPU 的支持下能產(chǎn)出驚人的單機(jī)性能。GPU 實(shí)現(xiàn)已經(jīng)可以作為對(duì)應(yīng) CPU 設(shè)備的替代，無(wú)需了解 CUDA API 就能挖掘出 GPU 的性能。Faiss 支持所有 Nvidia 2012 之后發(fā)布的 GPU(Kepler，計(jì)算能力 3.5+)。

我們把 roofline model 作為指南，它指出應(yīng)當(dāng)盡量讓內(nèi)存帶寬或浮點(diǎn)運(yùn)算單元滿載。Faiss 的 GPU 實(shí)現(xiàn)在單 GPU 上的性能要比對(duì)應(yīng)的 CPU 實(shí)現(xiàn)快 5 到 10 倍，像英偉達(dá) P100 這樣的新型 Pascal 架構(gòu)硬件甚至?xí)?20 倍以上。

一些性能關(guān)鍵數(shù)字：

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

底層實(shí)現(xiàn)

Facebook AI 研究團(tuán)隊(duì) 2015 年就開(kāi)始開(kāi)發(fā) Faiss，這建立在許多研究成果和大量工程實(shí)踐的基礎(chǔ)之上。對(duì)于 Faiss 類庫(kù)，我們選擇聚焦在一些基礎(chǔ)技術(shù)方面的優(yōu)化，特別是在 CPU 方面，我們重度使用了：

• 采用多線程來(lái)利用多核資源，并在多個(gè) GPU 上執(zhí)行并行檢索。
• 使用 BLAS 類庫(kù)通過(guò)矩陣和矩陣乘法來(lái)高效精準(zhǔn)地完成距離計(jì)算。一個(gè)不采用 BLAS 的暴力實(shí)現(xiàn)很難達(dá)到最優(yōu)。BLAS/LAPACK 是 Faiss 唯一強(qiáng)制依賴的軟件。
• 采用機(jī)器 SIMD 向量化和 popcount 加速獨(dú)立向量的距離計(jì)算。

關(guān)于 GPU

對(duì)于前述相似性搜索的 GPU 實(shí)現(xiàn)，k-selection(查找 k 個(gè)最小或最大元素)有一個(gè)性能問(wèn)題，因?yàn)閭鹘y(tǒng) CPU 算法(比如堆查找算法)對(duì) GPU 并不友好。針對(duì) Faiss GPU，我們?cè)O(shè)計(jì)了文獻(xiàn)中已知的最快輕量 k-selection 算法(k<=1024)。所有的中間狀態(tài)全部保存在寄存器，方便高速讀寫(xiě)?？梢詫?duì)輸入數(shù)據(jù)一次性完成 k-select，運(yùn)行至高達(dá) 55% 的理論峰值性能，作為輸出的峰值 GPU 內(nèi)存帶寬。因?yàn)槠錉顟B(tài)單獨(dú)保存在寄存器文件中，所以與其他內(nèi)核很容易集成，使它成為極速的精準(zhǔn)和近似檢索算法。

大量的精力投在了為高效策略做鋪墊，以及近似搜索的內(nèi)核實(shí)現(xiàn)。通過(guò)數(shù)據(jù)分片或數(shù)據(jù)副本可以提供對(duì)多核 GPU 支持，而不會(huì)受限于單 GPU 的可用顯存大小;還提供了對(duì)半精度浮點(diǎn)數(shù)的支持(float16)，可在支持的 GPU 上做完整 float16 運(yùn)算，以及早期架構(gòu)上提供的中間 float16 存儲(chǔ)。我們發(fā)現(xiàn)以 float16 編碼向量技術(shù)可以做到精度無(wú)損加速。

簡(jiǎn)而言之，對(duì)關(guān)鍵因素的不斷突破在實(shí)踐中非常重要，F(xiàn)aiss 確實(shí)在工程細(xì)節(jié)方面下了很大的功夫。

開(kāi)始使用 Faiss

Faiss 使用 C++ 實(shí)現(xiàn)，并支持 Python。只要從 Github 下載源碼并編譯，然后在 Python 中導(dǎo)入 Faiss 模塊即可開(kāi)始使用。Faiss 還完整集成了 Numpy，并支持構(gòu)造 numpy(使用 float32)數(shù)組的所有函數(shù)。

獲取 Faiss:

https://github.com/facebookresearch/faiss

索引對(duì)象Faiss(包括 C++ 和 Python)提供了索引 Index 的實(shí)例。每個(gè) Index 子類實(shí)現(xiàn)一個(gè)索引結(jié)構(gòu)，以說(shuō)明哪些向量可被加入和搜索。比如，IndexFlatL2 是一個(gè)能使用 L2 距離搜索的暴力索引。

這樣會(huì)打印出索引向量的數(shù)量。增加到一個(gè) IndexFlat 僅僅表示拷貝它們到索引的內(nèi)部存儲(chǔ)，因?yàn)楹竺鏇](méi)有其他操作會(huì)作用在該向量上。

執(zhí)行一次搜索：

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

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

矩陣 D 是一個(gè)平方距離矩陣，與 I 的大小一致，表示對(duì)于每個(gè)結(jié)果向量查詢的平方歐氏距離。

Faiss 實(shí)現(xiàn)了十多個(gè)由其他索引組合的索引類型。可選的 GPU 版本有完全相同的接口，并有通道在 CPU 和 CPU 索引之間互通。Python 接口主要由 C++ 生成以凸顯 C++ 索引，所以可以很容易地將 Python 驗(yàn)證代碼轉(zhuǎn)換為集成的 C++ 代碼。