概述：本文是對 WhalePaper 向量檢索領(lǐng)域第一次直播活動(dòng)內(nèi)容的文字版，會(huì)對向量檢索這個(gè) ChatGPT 和 new bing 都離不開的技術(shù)進(jìn)行介紹，結(jié)合了 ChatGPT 以及 new bing 的應(yīng)用場景進(jìn)行講解，相信被標(biāo)題騙進(jìn)來的你還真能有所收獲的（手動(dòng)狗頭）！本期內(nèi)容入門友好，對課件進(jìn)行了一些注解，圖文結(jié)合在一起全是干貨，長文預(yù)警！

脈絡(luò)

本次分享的主題是：基于圖索引的多向量檢索及其GPU加速。

主講人：浙江大學(xué)在讀博士王夢召。

將從以下幾個(gè)方面進(jìn)行:

• 背景介紹：包含 ChatGPT 的工作原理，向量檢索的發(fā)展現(xiàn)狀，什么是向量索引。

• 多向量檢索：會(huì)介紹什么是多向量，為什么需要多向量檢索，如何進(jìn)行多向量檢索。

• 如何通過GPU加速圖索引的多向量檢索：這部分內(nèi)容講解了如何基于圖索引進(jìn)行多向量檢索，如何用GPU來加速圖索引搜索。

• 對未來的思考：主要說明了一些王博士未來研究的一個(gè)方向。

• Q&A

背景介紹

我們每個(gè)人每天都會(huì)接觸大量的非結(jié)構(gòu)化數(shù)據(jù)，比如視頻、語音、文本等等，根據(jù)IDC（國際數(shù)據(jù)公司）的統(tǒng)計(jì)，當(dāng)前我們世界上所有的數(shù)據(jù)中有百分之八十是非結(jié)構(gòu)化數(shù)據(jù)。目前主流的處理非結(jié)構(gòu)化數(shù)據(jù)的方式是通過深度神經(jīng)網(wǎng)絡(luò)把非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)變?yōu)楦呔S的稠密向量，再對這些向量進(jìn)行分析處理。那么這些跟 ChatGPT 和 new bing 有什么關(guān)系呢？先來簡單介紹一下這兩者的工作方式。

ChatGPT 直接根據(jù)用戶提供的上文，直接生成回應(yīng)。那這個(gè)是怎么生成的呢？是靠用戶給出上文提示，它才能返回下文。但是自然語言的上下文，機(jī)器并不能看懂，所以要把自然語言編碼為向量的形式，回復(fù)時(shí)同樣是把向量解碼為一段文字。

new bing 是先用 bing 搜索找到一些參考，然后使用 GPT 模型進(jìn)行歸納總結(jié)。整體工作流程分為兩個(gè)部分。首先是檢索，就是根據(jù)用戶的搜索，先找到可靠的依賴信息。之后就是歸納總結(jié)，把搜索來的知識（網(wǎng)頁信息）歸納為一段精煉的文字。這個(gè)過程就類似向量檢索，根據(jù) query（查詢的向量）把相似向量檢索到，然后使用這些向量完成下游任務(wù)，例如：歸納總結(jié)，推薦。

從兩者的工作原理可以看出向量數(shù)據(jù)的重要性，AI應(yīng)用離不開向量數(shù)據(jù)，而只要在搜索過程中涉及到對向量的處理，便離不開向量檢索。那么什么是向量檢索？

什么是向量檢索?

還記得中學(xué)時(shí)期計(jì)算向量間的距離嗎？這其實(shí)就是向量檢索的本質(zhì)。還是舉個(gè)例子幫助我們更好的理解。

上圖為一個(gè)二維空間，里面存放著由非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)變成的向量，我們給定一個(gè)查詢（圖中小綠點(diǎn)），即我們要搜索的事物，然后把查詢也轉(zhuǎn)變成向量，通過計(jì)算向量間的距離，將距離最小的幾個(gè)向量（連線小紅點(diǎn)）作為結(jié)果返回，即召回離它最近的一些結(jié)果，這就是一個(gè)比較簡單的向量檢索的過程。

向量檢索的分類

向量檢索的索引技術(shù)可以分為四個(gè)流派，分別是Tree（樹索引）、Hashing（哈希索引）、Quantization（量化索引）和PG（圖索引），四種方法各有各的優(yōu)勢。其中基于圖的這種方式在效率和精度上有一個(gè)比較好的均衡，所以目前受到了大家更多的關(guān)注，也是我們這次分享的重點(diǎn)，后面會(huì)具體進(jìn)行說明。

對另外三種索引方式感興趣的朋友可以自行上網(wǎng)搜索，或者關(guān)注我們整理的相關(guān)論文：Unstructured-Data-Community/ANN-Papers，有已經(jīng)根據(jù)分類整理好的技術(shù)論文供大家閱讀，幫助大家節(jié)省搜尋的時(shí)間。

多向量檢索

什么是多向量

這個(gè)問題比較簡單，顧名思義，就是多個(gè)向量。我們以描述一個(gè)書本為例。

一本書里面每一章都包含數(shù)字、符號、文字、表格或圖片，其中的數(shù)字和符號就是標(biāo)量，文字、表格和圖片就是向量，每一章的內(nèi)容都由很多的向量及標(biāo)量構(gòu)成，而整本書由數(shù)個(gè)章節(jié)構(gòu)成，則是所有向量的集合。所以說我們利用多個(gè)向量來描述真實(shí)世界中的事物是比較靠譜的。

這一點(diǎn)在人臉中格外直觀。人臉是一個(gè)立體的圖形，一個(gè)人的臉就需要不同角度的照片進(jìn)行描述，將不同角度的照片中的信息編碼成向量之后就可以更好地描述這個(gè)人的臉部信息，也就是前面提到的更好地描述一個(gè)現(xiàn)實(shí)世界的事物。這些也點(diǎn)出了我們?yōu)槭裁葱枰嘞蛄繖z索。

為什么我們需要多向量檢索

又是一個(gè)例子（愛板栗星人狂喜）。

大家應(yīng)該都用過以圖搜圖的功能，假設(shè)現(xiàn)在有個(gè)用戶想要搜出一張?jiān)谝雇砬覉D中沒有人的埃菲爾鐵塔圖片，但是他手頭只有一張白天且人很多的埃菲爾鐵塔圖片作為原圖。如果他用傳統(tǒng)的搜索引擎以圖搜圖的方式去搜索，肯定會(huì)搜出與原圖相似的圖片，但是有可能沒法滿足他的要求。這個(gè)時(shí)候，多向量檢索就派上用場了。

所謂多向量檢索，就是可以用多個(gè)向量去檢索一個(gè)向量，其中，用于檢索的多個(gè)向量可以是不同形式的。在上述場景中，該用戶就可以用“無人且轉(zhuǎn)變成晚上”這句話來描述他所需要更改的信息，多向量檢索技術(shù)就將這句話編碼成文字向量，原圖編碼成圖片向量，結(jié)合兩個(gè)向量一起去檢索，得出和他描述的最近似的圖片。

從上述的例子可以看出，多向量檢索可以讓用戶更好地表達(dá)自己的意圖，從而提高搜索系統(tǒng)的可用性和準(zhǔn)確性。

下面所展示的電商檢索場景也是一個(gè)道理。

現(xiàn)在我們在搜索商品的時(shí)候，更多還是一個(gè)文字描述，并且最后算法推薦的結(jié)果還不一定可以滿足我們的需要。假如我們可以在搜索出來的結(jié)果上再進(jìn)行一次篩選，那么范圍就會(huì)進(jìn)一步縮小，不僅更接近我們的需要，而且還可以節(jié)約時(shí)間。

相信你已經(jīng)猜出來我要說什么了，沒錯(cuò)，我們可以在第一次檢索的基礎(chǔ)上再提供一些文字描述，利用多向量檢索進(jìn)行多次篩選，通過輸入的文字和召回的結(jié)果這兩個(gè)信息去迭代，不斷地優(yōu)化檢索的結(jié)果，最終獲取我們想要的商品。

怎么進(jìn)行多向量檢索

說了這么一串向量有好使，也該介紹一些怎么進(jìn)行多向量檢索了。

目前主要有兩個(gè)解決方案，一個(gè)是分離，另一個(gè)是聯(lián)合。

分離方案是指每種模態(tài)的信息都給獨(dú)立轉(zhuǎn)變成向量，然后獨(dú)立執(zhí)行向量搜索，最后將每種信息檢索結(jié)果進(jìn)行合并。

聯(lián)合方案是指把多種信息通過一個(gè)融合模型聯(lián)合成一個(gè)向量，然后通過當(dāng)前這個(gè)單獨(dú)的向量去檢索。

分離的方案在DB社區(qū)用的比較多一些，主要的挑戰(zhàn)在檢索過程中；聯(lián)合的方案在CV領(lǐng)域用的比較多，主要的挑戰(zhàn)在如何利用模型將不同模態(tài)的信息放進(jìn)一個(gè)向量中。但是不管那種方案，都是需要一個(gè)向量檢索的過程的。

基于圖索引的多向量檢索及其GPU加速

講了半天，終于到主菜了。在講GPU加速之前，我們要如何用我們前面提到的基于圖（PG）索引的方式來執(zhí)行多向量檢索呢？

基于圖索引進(jìn)行多向量檢索

首先，他需要根據(jù)向量之間的相似性對向量的集合建立一個(gè)圖索引，也就是將向量匯集在一個(gè)圖層中。之后在給定一個(gè)查詢時(shí)，會(huì)在這個(gè)圖層下隨機(jī)或固定生成一個(gè)入口點(diǎn)（圖中黑色點(diǎn)），去不斷地訪問點(diǎn)附近的鄰居（1234點(diǎn)），計(jì)算鄰居與這個(gè)查詢向量的距離，然后選擇離查詢點(diǎn)最近的鄰居向量（圖中4）的鄰居向量計(jì)算和查詢向量的距離，選取最近的點(diǎn)，不斷地重復(fù)以上的過程，迭代得到和查詢點(diǎn)最近的向量集合，最后獲取召回過程。

在這個(gè)過程中，有兩個(gè)比較關(guān)鍵的操作，一個(gè)是向量距離的計(jì)算，還有一個(gè)是計(jì)算機(jī)對向量搜索過程中數(shù)據(jù)結(jié)構(gòu)的維護(hù)。數(shù)據(jù)結(jié)構(gòu)包含三個(gè)，

• 結(jié)果集：用于放查詢召回的結(jié)果，也就是當(dāng)前搜索到的鄰居中距離目前最近的點(diǎn)；

• 候選集：用于存放檢索過程中當(dāng)前的一個(gè)鄰居搜索結(jié)果，也就是即將和查詢向量進(jìn)行距離計(jì)算的點(diǎn)的集合，是動(dòng)態(tài)變化的；

• 訪問記錄：用于存放已經(jīng)訪問過的點(diǎn)，以防重復(fù)地計(jì)算同一個(gè)向量。

這個(gè)過程比較復(fù)雜，具體展示一下加強(qiáng)理解。

上圖中我們要召回和黑點(diǎn) q 近似的結(jié)果，一共會(huì)召回四個(gè)結(jié)果，也就是離 q 最近的結(jié)果。我們將 v1 這個(gè)點(diǎn)作為入口進(jìn)入，首先把入口點(diǎn) v1 放入候選集 C 和訪問記錄 H 中，進(jìn)行初始化；然后我們到向量點(diǎn)的集合中找到和 v1 點(diǎn)連線的點(diǎn)，也就是 v1 的鄰居 v2、v3、v5、v7、v8 放入 C 和 H 中來和 q 進(jìn)行距離計(jì)算，并進(jìn)行距離長度的對比，將最近的點(diǎn) v8 從 C 中刪除并放進(jìn)結(jié)果集 N ，然后將 v8 的鄰居 v7、v10 放進(jìn) C 中，進(jìn)行新一輪的計(jì)算，因?yàn)槠渌c(diǎn)的距離在第一輪已經(jīng)計(jì)算過，所以此時(shí)只計(jì)算 q 與 v10 之間的距離，并與之前計(jì)算過的其他點(diǎn)的距離進(jìn)行比較，得出結(jié)果 v10 后，將 v10 從C中刪除放入 N ，如此循環(huán)，N 中有了4個(gè)點(diǎn)后有新的點(diǎn)要進(jìn)來還需要對比 N 中的點(diǎn)和新點(diǎn)的誰的距離更近，把最近的4個(gè)放進(jìn)去，遠(yuǎn)的拋棄，直到遍歷完所有點(diǎn)都沒法找出比 N 中的點(diǎn)更近的點(diǎn)了就結(jié)束這個(gè)迭代的過程。

這個(gè)過程總結(jié)起來就是三步，

• 候選定位：從 C 里面定位一個(gè)點(diǎn)；

• 距離計(jì)算：計(jì)算這個(gè)點(diǎn)的鄰居和查詢點(diǎn)的距離；

• 更新三個(gè)集：根據(jù)計(jì)算結(jié)果迭代三個(gè)集中的內(nèi)容。

其中距離計(jì)算是占用的時(shí)間最多，幾乎占了90%的查詢時(shí)間，所以我們就要考慮如何利用 GPU 這個(gè)并行能力去加速具體計(jì)算的過程。

GPU加速圖索引搜索

GPU 加速的核心就是并行運(yùn)算。

還是圖索引那個(gè)例子，現(xiàn)在我們在原有的基礎(chǔ)上進(jìn)行優(yōu)化，用一個(gè)線程來維護(hù)三個(gè)數(shù)據(jù)結(jié)構(gòu)。圖中左下角是GPU的內(nèi)存層次結(jié)構(gòu)，使用 GPU 進(jìn)行加速的搜索過程中，會(huì)把這三個(gè)結(jié)構(gòu)放到線程的局部內(nèi)存當(dāng)中，便于維護(hù)上述的候選定位以及更新三個(gè)集的操作。

圖中右下角就是圖索引的例子，在使用GPU加速之前，是直接計(jì)算一對向量的距離，但是在GPU加速的情況下，我們會(huì)將一個(gè)向量分成很多子向量，然后每個(gè)線程進(jìn)行單獨(dú)的距離計(jì)算，最后再合并起來。

這樣就可以實(shí)現(xiàn)并行計(jì)算，大大節(jié)省距離計(jì)算需要消耗的時(shí)間，在數(shù)據(jù)結(jié)構(gòu)維護(hù)的操作消耗時(shí)間不變的情況下，讓距離計(jì)算的時(shí)間從原先的占比90%降低到10%。

GPU 并行計(jì)算的這個(gè)特點(diǎn)除了加速距離計(jì)算過程之外，還可以加速數(shù)據(jù)結(jié)構(gòu)維護(hù)的操作。

這里補(bǔ)充兩個(gè)概念方便后續(xù)的理解，

• 訪問點(diǎn)：一個(gè)點(diǎn)如果已經(jīng)被訪問了，也就是這個(gè)點(diǎn)已經(jīng)和查詢的點(diǎn)進(jìn)行過距離計(jì)算了，稱為訪問點(diǎn)；

• 探索點(diǎn)：一個(gè)點(diǎn)如果已經(jīng)被探索了，也就是這個(gè)點(diǎn)的鄰居已經(jīng)和查詢的點(diǎn)進(jìn)行過距離計(jì)算了，稱為探索點(diǎn)。

GPU 加速過后的圖索引與傳統(tǒng)的圖索引最大的區(qū)別就在于數(shù)據(jù)結(jié)構(gòu)的不同，由于 GPU 并行計(jì)算的快速性，刪去歷史記錄結(jié)構(gòu)雖然會(huì)有一些少量的重復(fù)計(jì)算過程，但是反而為節(jié)約數(shù)據(jù)結(jié)構(gòu)維護(hù)上的時(shí)間開銷帶來很大的收益，但是如果不對探索點(diǎn)進(jìn)行一個(gè)記錄，可能會(huì)陷入到一個(gè)惡性循環(huán)，也就是會(huì)不停地訪問一個(gè)點(diǎn)相同的鄰居。所以 GPU 采用了一個(gè) Lazy Check 的策略，刪除了歷史記錄結(jié)構(gòu)，允許一些冗余計(jì)算的存在，但是又不會(huì)陷入惡性循環(huán)，后面會(huì)具體說明 Lazy Check 的原理。

我們來一起看一下 GPU 刪去歷史記錄結(jié)構(gòu)后的數(shù)據(jù)結(jié)構(gòu)維護(hù)過程。

GPU 的兩個(gè)數(shù)據(jù)結(jié)構(gòu)分別是合集 N 和合集 T。其中，合集 N 用于儲(chǔ)存當(dāng)前計(jì)算出最近的結(jié)果，集合 T 用于存放即將計(jì)算向量距離的鄰居，兩者都存放在 GPU 的線程當(dāng)中。

首先，在線程塊里面有很多線程，通過多線程并行的方式去探測當(dāng)前還沒有被探測過的點(diǎn)，比如下圖中，在集合 N 定位到第一個(gè)沒被探索過的頂點(diǎn) v 。

接著，在全局內(nèi)存把 v 的鄰居讀取到集合 T 當(dāng)中，集合 N 和集合 T 都在一個(gè)線程塊的共享內(nèi)存里。

現(xiàn)在我們要開始計(jì)算向量間的距離，需要去全局內(nèi)存將這個(gè)鄰居的原始向量讀取進(jìn)來，用和前面提到的一樣的方式，將一個(gè)向量拆解成多個(gè)子向量進(jìn)行距離計(jì)算后再合并。

計(jì)算完向量間的距離，我們進(jìn)行一個(gè)Lazy Check的操作，也就是利用并行二分搜索將集合 T 里面的每一個(gè)點(diǎn)和集合 N 里的點(diǎn)進(jìn)行對比，來看看有哪些點(diǎn)是已經(jīng)被探測過的，如果已經(jīng)被探測過了就會(huì)被做一個(gè)特殊的標(biāo)記，被標(biāo)記的點(diǎn)就不會(huì)再進(jìn)行計(jì)算了。也就是說 Lazy Check允許多次計(jì)算的存在，但是不允許計(jì)算陷入循環(huán)。

接下來，通過雙調(diào)排序的方法針對合集 T 中沒被標(biāo)記的點(diǎn)進(jìn)行一個(gè)并行排序。依舊是利用雙調(diào)排序，將合集 T 中的有序序列合并到合集 N 當(dāng)中。

對未來的思考

這個(gè)部分主要是王博士基于這個(gè)技術(shù)對于未來工作方向上的思考。

首先，目前 PG（圖索引）在向量搜索的時(shí)候還沒有理論保證，所以在這一方面做一個(gè)探索是比較值得的。

其次，剛才介紹到的多向量索引和搜索的策略分為分離和聯(lián)合兩種，但是我們可以針對多向量的這種特征去專門設(shè)計(jì)一個(gè)索引和搜索的策略。

再次，我們或許可以嘗試通過異構(gòu)硬件去存儲(chǔ)或者加速圖的搜索過程，因?yàn)閳D索引以及它對原始數(shù)據(jù)的依賴導(dǎo)致它的存儲(chǔ)開銷還是非常大的，這是個(gè)可以改進(jìn)的點(diǎn)。

最后，可以進(jìn)行一些優(yōu)化，探索如何將 PG 的維護(hù)操作做的更好，以及如何與 AI 或是向量數(shù)據(jù)庫集成。

Q&A

Q：不同模態(tài)的數(shù)據(jù)通過融合數(shù)據(jù)模型聯(lián)合投影到同一個(gè)向量空間，是否會(huì)存在不同模態(tài)轉(zhuǎn)變的向量之間距離較遠(yuǎn)從而影響到檢索速度的情況？例如通過融合數(shù)據(jù)模型同時(shí)將圖片、文字、視頻轉(zhuǎn)換成對應(yīng)向量然后存儲(chǔ)到同一個(gè)向量空間中，視頻向量在 A 區(qū)域，圖片向量在 B 區(qū)域，文字向量在 C 區(qū)域，且三個(gè)區(qū)域距離較遠(yuǎn)，從而導(dǎo)致檢索速度較慢。

A：會(huì)存在這種情況，不同模態(tài)的數(shù)據(jù)轉(zhuǎn)換成向量之后，向量的分布會(huì)存在很大的差異，存在聚類現(xiàn)象。但是現(xiàn)在 CV社區(qū) 更多地使用多模態(tài)融合的模型進(jìn)行訓(xùn)練，就會(huì)減少這種情況的存在。

Q：目前多模態(tài)搜索的技術(shù)壓力似乎都落在融合模型上，那對于向量搜索有什么技術(shù)挑戰(zhàn)嗎？

A：確實(shí)目前做了很多對模型的改進(jìn)，但是當(dāng)前融合模型還是將聯(lián)合與分離兩種方式結(jié)合在一起使用來進(jìn)行優(yōu)缺點(diǎn)的互補(bǔ)，還不存在一個(gè)特別完美的融合模型。如果單單依靠融合模型能將向量處理的非常好，那么向量搜索就不會(huì)有任何挑戰(zhàn)；但如果單單依靠融合模型并不能做的很好，那么我們可以考慮在檢索層面做一些搜索策略的優(yōu)化，來彌補(bǔ)融合模型的不足，這樣對于向量檢索層面就存在一個(gè)挑戰(zhàn)。

Q：如果遇到特別大的數(shù)據(jù)量，例如10億級，無法放入 GPU 的顯存中，只能放到 SSD 里，在處理的時(shí)候就會(huì)多一個(gè) PCIE 的通路進(jìn)行數(shù)據(jù)傳輸，有沒有可能數(shù)據(jù)傳輸帶來的時(shí)間開銷會(huì)導(dǎo)致 GPU 加速變得沒有意義？

A：目前已有的技術(shù)論文中對于這一塊的實(shí)驗(yàn)結(jié)果顯示，雖然面對特別大的數(shù)據(jù)量存在 PCIE 的過程，但是 GPU 加速可以抵消傳輸增加的時(shí)間開銷。

提示：目前有 GPU Direct 技術(shù)可以直接通過GPU訪問存儲(chǔ)

Q：基于圖索引的多向量搜索方式具有什么樣的優(yōu)勢？有哪些應(yīng)用？

A：基于圖索引的多向量搜索方式具有的優(yōu)勢主要在于多模態(tài)模型，在處理多向量上并沒有獨(dú)特的優(yōu)化，這也是未來可以研究的方向。目前應(yīng)用比較多的還是電商場景，以及 CV 社區(qū)目前在研究的視覺查詢、視覺問答等內(nèi)容，未來 ChatGPT 也會(huì)多模態(tài)化，可以看出應(yīng)用的方面還是比較多的。

好啦，本期分享內(nèi)容就全部結(jié)束啦，參考文獻(xiàn)放在最后，如果有任何疑問和建議都?xì)g迎在評論區(qū)提出，我們會(huì)盡量在第一時(shí)間進(jìn)行回應(yīng)。當(dāng)然，也可以掃碼添加負(fù)責(zé)人，加入我們的社區(qū)群進(jìn)行提問，大家都會(huì)耐心解答的。

參考文獻(xiàn)

[1] https://solutionsreview.com/data-management/80-percent-of-your-data-will-be-unstructured-in-five-years/?

[2] https://www.marqo.ai/blog/using-marqo-and-gpt3-for-topical-news-summarisaiton?

[3] https://www.marqo.ai/blog/what-is-tensor-search

看到這里的你不妨點(diǎn)亮點(diǎn)贊，留下你的足跡吧~