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