0
本月初雷鋒網報道，F(xiàn)acebook 開源了 AI 相似性搜索工具 Faiss。而在一個月之后的今天，F(xiàn)acebook 發(fā)布了對 Faiss 的官方原理介紹。
它是一個能使開發(fā)者快速搜索相似多媒體文件的算法庫。而該領域一直是傳統(tǒng)的搜索引擎的短板。借助Faiss，F(xiàn)acebook 在十億級數(shù)據(jù)集上創(chuàng)建的最鄰近搜索（nearest neighbor search），比此前的最前沿技術快 8.5 倍，并創(chuàng)造出迄今為止學術圈所見最快的、運行于 GPU 的 k-selection 算法。Facebook 人工智能實驗室（FAIR） 借此創(chuàng)造了數(shù)個世界紀錄，包括在十億高維矢量上的構建的、世界最快的 k-nearest-neighbor 圖。
傳統(tǒng)數(shù)據(jù)庫由包含符號信息的結構表組成。比方說，一個圖像集，會用每行放一張索引照片的列表來表示。每一行都包含諸如圖像標識和描述語句等信息。每一行也可與其他表格的條目關聯(lián)，比如照片與人名列表相關聯(lián)。
雷鋒網獲知，很多AI 工具都會產生高維矢量，比如像 word2vec 這樣的文本嵌入工具，以及用深度學習訓練的 CNN 描述符（descriptors）。這些表示比固定的符號表示更加強大靈活，至于原因，本文將為大家解釋。但是，用 SQL 來檢索的傳統(tǒng)數(shù)據(jù)庫并沒有適配這些新型表示。首先，海量的新多媒體流創(chuàng)造了數(shù)十億的矢量。其次，而且更重要的是，找到相似的相似的條目意味著找到相近的高維矢量。而對于當下的標準檢索語言，這是極度低效、甚至無法實現(xiàn)的。
讓我們假設你有一張某建筑的影像，比方說某城市的禮堂照片，但你忘記這是哪一個城市的了。然后，你希望找到圖片庫中該建筑的所有照片。該情況下，SQL 中常用的 key/value 檢索并沒有幫助——因為你已經忘了這是哪個城市。
這就輪到相似性搜索派上用場。由于設計，圖像的矢量表示會對相似圖像生成相近的矢量。在這里，相近矢量被定義為在歐幾里得空間相鄰的矢量。
另一項矢量表示的應用是分類。想象下你需要一個分類器，來判別圖片庫中哪一個圖片代表了菊花。分類器的訓練是一個開發(fā)者們都比較熟悉的過程：算法把菊花和非菊花的圖像作為輸入。若果分類器是線性的，它會輸出一個分類矢量，后者帶有一項重要屬性：它的向量點積（Dot Product）和圖像矢量在一起，能反映出該圖像包含菊花的概率。然后對向量點積和圖片庫中的所有條目進行計算。最后 return 有最高概率值的圖像。這種檢索是一種“最大內積”搜索。
所以，對于相似性搜索和分類，我們需要以下操作：
給定檢索矢量，return 在歐幾里得距離上最接近這個矢量的數(shù)據(jù)庫對象列表。
給定檢索矢量，return 有最高向量點積的數(shù)據(jù)庫對象列表。
一個額外的挑戰(zhàn)，是 Facebook 想要在一個大尺度上執(zhí)行這些操作。這里，“大尺度”指的是數(shù)十億的矢量。
現(xiàn)有的軟件工具，不足以完成上述數(shù)據(jù)庫搜索操作。傳統(tǒng)的 SQL 數(shù)據(jù)庫系統(tǒng)可用性不高，因為它們是為 hash-based searches 或 1D interval searches 而優(yōu)化。OpenCV 等工具包里包含的相似性搜索功能，在擴展性上的限制非常大。針對“小”數(shù)據(jù)集的相似性搜索算法庫也是這么個情況（比如，一百萬個矢量）。其他工具包大多是學術研究的產物，為發(fā)表的論文而開發(fā)，用來在特定設定下展示效果。
Faiss 是一個打破上述限制的算法庫。它的優(yōu)點有：
提供數(shù)個相似性搜索方法。這些方法針對不同使用情況，提供了跨度很大的功能取舍。
為內存的使用和速度而優(yōu)化。
為相關索引方法提供了最前沿的 GPU 執(zhí)行方案。
一旦這些矢量被學習機提取出來（從圖像、視頻、文本文件或其他渠道），它們就已經可以被輸入進相似性搜索庫。
Facebook 有一個作為參照的“暴力”算法——它會完整地照章計算所有的相似性，然后 return 最相似元素的列表。這提供了一個黃金結果參照列表。值得注意的是，高效得執(zhí)行該暴力算法不容易實現(xiàn)，而且經常影響系統(tǒng)其它部分的效果。
如果我們愿意犧牲一部分精確度，相似性搜索的速度可以有數(shù)個數(shù)量級的提升。當然，這會導致相對參照結果的一點偏移。舉個例子，對圖像相似性搜索的第一和第二個結果進行交換，或許不會有什么區(qū)別，因為它們很可能都是某個給定檢索的正確答案。加速搜索意味著要對數(shù)據(jù)集進行一些預處理，F(xiàn)acebook 把這成為索引。
這使 Facebook 確定了三大研究方向：
速度。找到十個最相似的矢量需要多久？希望花費的時間比暴力算法要少。不然的話，索引就沒有任何意義。
內存使用。該方法需要多少 RAM？比原始矢量多還是少？ Faiss 只支持在 RAM 上搜索，因為其他磁盤數(shù)據(jù)庫的速度要慢數(shù)個數(shù)量級。即便是 SSD 也太慢。
精確度。返回的結果列表與暴力搜索結果差多少？精確度能通過計算檢索數(shù)量，在結果列表中先返回最鄰近單位評估；或是衡量 10 個最先返回的最鄰近單位的平均 fraction （該方法被稱之為 10-intersection）。
Facebook 一般會衡量在給定內存使用情況下，速度和精確度之間的權衡。Faiss 專注于壓縮原始矢量的方法，因為它們是擴展到十億級矢量數(shù)據(jù)集的唯一途徑。當需要索引的矢量有十億個之多，每一個會占用 32 左右的字節(jié)，這些矢量會占用極大的內存空間。
許多索引算法庫針對的是百萬左右的矢量，F(xiàn)acebook 的工程師們把這成為小規(guī)模。舉個例子，nmslib 就包含這方面極其高效的算法，它比 Faiss 更快但是會占用遠遠更多的內存空間。
工程世界中，并沒有針對這個大小數(shù)據(jù)集的基準。因此，F(xiàn)acebook 基于研究結果進行評估。
精確度在 Deep1B 上進行評估，它是包含十億張圖片的圖像庫。每一個圖像都已經被 CNN 處理過，CNN 中的其中一個 activation map，會被作為圖像 描述符（descriptor）。這些矢量可以與歐幾里得距離進行比較，來量化這些圖像之間的相似度。
Deep1B 包含一個比較小的檢索圖像庫。真實的相似性搜索結果，由處理了這些圖像的暴力算法提供。因此，如果我們運行一個搜索算法，我們就可以評估結果中的 1-recall@1。
由于評估，我們把內存使用限制在 30 GB。該內存限制指導我們進行索引方法和參數(shù)的選擇。在 FAISS，索引方法用字符串來表示；在這個例子中是OPQ20_80,IMI2x14,PQ20。
該字符串代表了應用于矢量的預處理步驟 (OPQ20_80) 。一個 selection mechanism (IMI2x14) 來指示數(shù)據(jù)庫應該如何被分割，以及一個編碼部分（encoding component PQ20）來指示用 product quantizer (PQ) 編碼的矢量，生成 20 字節(jié)的代碼。因此，內存的占用（包括了 overheads）在 30GB 以下。
這聽起來太技術流，因此 Faiss 的文件會向開發(fā)者提供指導：如何根據(jù)需要選擇最恰當?shù)乃饕愋汀?/p>
索引類型確定之后，就可以開始索引。FAISS 算法庫對這十億個矢量進行處理，并把他們放入索引。索引能夠存在硬盤，或者立即使用，對索引的搜索、additions/removals 可被交錯插入。
當索引就緒后，一系列 search-time 的參數(shù)可設為針對此方法進行調整。由于評估需要，我們用單線程進行搜索。由于內存占用已經被限制住，我們需要在精確度和搜索時間之間進行權衡、優(yōu)化。舉個例子，這意味著能對 1-recall@1 40% 的最不可能搜索時間設置參數(shù)。
幸運的是，F(xiàn)aiss 配有自動調參機制，能掃描參數(shù)空間，并對提供了最佳操作點（operating points）的那些進行。這意味著給定精確度情況下的最優(yōu)潛在搜索時間，或者反過來，給定搜索時間的最優(yōu)精確度。在 Deep1B 上，操作點可用折線圖的形式進行可視化。
這幅圖上，我們可讀出，獲取 40% 的 1-recall@1，有少于每矢量 2 ms的檢索時間。如果把檢索時間放寬到 0.5 ms，我們可以達到 30%。2 ms 的檢索時間，意味著單核的 500 QPS（queries per second )。
若把該結果與圈內最先進的研究相比，即 Babenko 和 Lempitsky 在 CVPR 2016 上發(fā)表的論文：“Efficient Indexing of Billion-Scale Datasets of Deep Descriptors”。該論文介紹了 Deep1B 數(shù)據(jù)集。但他們需要 20 ms 來獲取 45% 的 1-recall@1。
當前，許多研究努力集中于 GPU 的執(zhí)行上。在原生多 GPU 支持下，這能夠產生相當不錯的單機性能。GPU 執(zhí)行可被看做是對應 CPU 的替代，你其實不需要理解 CUDA API 來挖掘 GPU 的性能。 Faiss 支持所有 2012 年之后發(fā)布的英偉達顯卡（開普勒，計算能力 3.5+）。
我們希望把 roofline model 作為指南，它指出開發(fā)者應盡量使內存帶寬或者浮點單位飽和。Faiss 單 GPU 的速度一般比 CPU 快五到十倍。新的帕斯卡架構 GPU 硬件，比如英偉達 P100，使之快了 20 倍有余。
一些展示性能的數(shù)字：
合適的索引，一個簡單暴力的 k-nearest-neighbor 圖（k = 10），基于 YFCC100M 數(shù)據(jù)集中 9500 萬圖像的128D CNN 描述符，0.8 的 10-intersection，用四路上代泰坦（Maxwell Titan X）只需要 35 分鐘即可建成，包含索引創(chuàng)建時間。
十億矢量的 k-nearest-neighbor 圖已經即將成為現(xiàn)實。開發(fā)者可以在 Deep1B 數(shù)據(jù)集上創(chuàng)建強力的 k-nearest-neighbor 圖（k = 10），0.65 的 10-intersection，在四路 Maxwell 泰坦支援下需要 12 個小時。若是 0.8 的 10-intersection，八路帕斯卡 P100-PCIe GPU，也是 12 個小時。更低質量的圖可在五小時內用泰坦創(chuàng)建完成。
其他部分也達到了驚人性能。比方說，創(chuàng)建上述 Deep1B 索引需要 6710 萬 120-dim 矢量，用 k-means 聚類生成 262,144 個幾何中心。這在 25 E-M 次迭代下，需要四路泰坦 (12.6 tflop/s of compute) 花 139 分鐘進行處理。注意聚類的訓練集不需要與 GPU 顯存匹配，因為數(shù)據(jù)是按需即時導入 GPU 的，而不會影響性能。
雷鋒網獲知，F(xiàn)AIR（Facebook 人工智能實驗室） 自 2015 年著手開發(fā) Faiss。這是建立在過去的許多研究結論和大量技術攻關的基礎上。對于 Faiss，F(xiàn)acebook 選擇專注于對幾項基礎技術進行優(yōu)化。尤其在 CPU 方面，F(xiàn)acebook 大量利用了：
多線程以充分利用多核性能并在多路 GPU 上進行并行搜索。
BLAS 算法庫通過 matrix/matrix 乘法進行高效、精確的距離計算。沒有 BLAS，高效的強力執(zhí)行很難達到最優(yōu)狀態(tài)。 BLAS/LAPACK 是唯一一個 Faiss 必須的前提軟件。
機器 SIMD 矢量化和 popcount 被用于加速孤立矢量的距離計算。
對于從前的相似性搜索 GPU 執(zhí)行，k-selection（尋找 k-minimum 或 maximum 因子）一直存在性能問題。這是因為普通的 CPU 算法（比如 heap selection）并不適用于 GPU。對于 Faiss GPU，F(xiàn)acebook 設計了學術圈迄今為止最快的小型 k-selection 算法（k <= 1024）。所有中間狀態(tài)都完全保存在寄存器中，進一步提升了速度。它能夠將輸入數(shù)據(jù)以 single pass 進行 k-select，運行于潛在峰值性能的 55%，取決于峰值 GPU 顯存帶寬。由于其狀態(tài)只存儲在注冊表中，并可與其他 kernels 融合，使它成為超級快的 exact 和 approximate 搜索引擎。
研究領域的許多注意力被放到了高效的 tiling 策略，和面向 approximate 搜索的 kernels 執(zhí)行。多 GPU 支持用過粉碎或復制數(shù)據(jù)來提供。開發(fā)者并不會受單 GPU 顯存大小的限制。半精度浮點支持 (float16) 也有提供，可在支持的 GPU 上進行完整 float16 運算，或者更早 GPU 架構所提供的的中級 float16 存儲。我們發(fā)現(xiàn) float16 這樣的編碼矢量能在幾乎不損失精度的前提下進行加速。
簡而言之，持續(xù)的 overhead 因素會在執(zhí)行中起到作用。Faiss 做了許多關注工程細節(jié)的痛苦工作。
Faiss 用 C++ 實現(xiàn)，支持 Python。想要上手的各位，請到 GitHub 獲取 Faiss，進行編譯，然后把 Faiss 模塊導入到 Python。Faiss 與 numpy 能做到完美的整合，包括需借助 numpy 陣列來實現(xiàn)的所有功能 (in float32)。
GitHub 地址：https://github.com/facebookresearch/faiss
詳情請訪問：https://code.facebook.com/posts/1373769912645926/faiss-a-library-for-efficient-similarity-search/
via facebook
相關文章：
Facebook AI實驗室開源相似性搜索庫Faiss：性能高于理論峰值55%，提速8.5倍
Facebook 開源 FAISS；MIT 開發(fā) SDV 系統(tǒng)，將合成數(shù)據(jù)用于機器學習等 | AI 開發(fā)者頭條
雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。
