The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes

語言: CN / TW / HK

Source: The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes

TL;DR: 雖然以SentenceBERT為代表的語義向量檢索展現出了超越傳統的以BM25為代表的稀疏向量檢索的效能,但是還沒有人研究過索引量和向量維數對稠密向量檢索效能的影響,本文作者通過理論和實驗來證明了隨著索引量的增大,稠密向量檢索的表現比起稀疏向量檢索下降得更快,在極端情況下,稀疏向量檢索反而優於稠密向量檢索。

Introduction

傳統的資訊檢索技術通常使用TF-IDF、BM25這類稀疏表示來檢索文件,然而這些方法都建立在使用者查詢與相關文件存在詞彙重疊的基礎之上,然而現實世界並不會這麼理想,稀疏向量查詢通常會存在棘手的詞彙空缺或語義鴻溝問題(lexical/semantic gap),語義鴻溝可以理解為是自然語言詞彙的稀疏性和語法的多樣性,這些現象可以通過同義詞典、句式變換等方式來改善。而詞彙空缺是源自翻譯語言學的現象,我們可以將其簡單地理解為使用者查詢與文件的不對稱性,比如FAQ語料庫通常儲存的都是比較標準,正式的問句,然而真實場景下使用者的提問通常非常口語化,標準問句和真實查詢的字面匹配分數常常很低,這就不僅僅是單純的詞彙或句法差異了,而是更高層次的風格上的差異,甚至可以理解為兩種不同的語言,這實際上也是當前的搜尋引擎在正式檢索文件前必須對使用者查詢進行復雜的修正、解析、理解,而不是直接計算TF-IDF的原因。

將使用者查詢濃縮為關鍵詞的過程是非常複雜的,有沒有直接將使用者查詢與文件進行匹配的方式呢?這正是稠密向量查詢想要達到的效果,也就是將查詢和文件對映到同一個低維向量空間,通過計算餘弦相似度來檢索相關文件,關於稠密向量表示的探索可以追溯到經典的潛在語義分析(LSA),2013年的DSSM首次將深度學習方法引入了稠密向量檢索,目前,以SentenceBERT為代表的語義檢索模型在很多資料集上超越了基於稀疏向量的檢索方法。

然而,這些模型的實驗資料集的索引量大多都比較小,其中最大的MS Macro資料集也只有八百萬個文件,然而在實際的應用場景中,索引量常常能夠達到上億的量級。當索引量非常大的時候,稠密向量表示還優於稀疏向量表示嗎?接下來,我們分別從理論和實踐的角度來分析這個問題。

Theory

給定一個查詢向量 和文件向量 ,分別計算查詢和文件的餘弦相似度:

直觀上來看,查詢結果的假陽性率(false positives)會隨著索引量 的增大而增大,不妨假設文件向量相互獨立,如果要保證沒有檢索到假陽性文件,則需要滿足

其中 是與 相關的文件向量,如果該條件不滿足,則出現假陽性的概率為

可以發現隨著索引量 的增大,出現假陽性的概率的確也是增大的。

但假陽性率和向量維數的關係就沒這麼直觀了,對於隨機的 ,我們希望求出具體的假陽性率:

首先,不妨將 維文件向量標準化為單位向量,當 滿足 的時候,則 為假陽性,因此我們考慮用 維超平面從單位球面上切出會出現假陽性的區域,一個隨機生成的向量被判定為假陽性的概率為

其中 是切出來的區域的表面積, 則是單位球面的面積。以二維空間為例,如下圖所示,當 落入紅**域 時,則 為假陽性文件。

高維空間就很難直觀地理解了, 維空間中 的計算公式為

其中 為 和 形成的極角, 為正則不完全貝塔函式:

針對相同的夾角 , 是隨著維數 的遞增而單調遞減的,也就是說,向量維數越大,出現假陽性文件的概率就越小。因此,雖然稠密向量索引的優勢之一在於向量維數遠小於稀疏向量索引,非常節省記憶體,但過小的維數會導致假陽性率的提升,同時當索引量越來越大時,低維稠密表示比起高維稠密表示會有更高的假陽性率。

Empirical Investigation

上面的理論證明均假設了向量是獨立均勻分佈的,這實際上只為我們提供了一個假陽性率的下界,實際上,正如 BERT-flow 裡面提到的一樣,模型學習到的稠密向量分佈通常是各向異性的,這些向量在整個向量空間中只佔據了一個狹窄的錐形空間,這樣的性質將大幅度提升檢索結果的假陽性率,因此作者希望通過實驗來觀察這種現象到底有多嚴重。

Dataset

作者的實驗資料集為MS MACRO,該資料集包括了一百萬個來自Bing的真實使用者查詢和八百萬個候選文件,絕大部分查詢只對應著一個相關文件,檢索評價指標為MRR@10。為了更好地對比稠密向量檢索和稀疏向量檢索的相對效能差異,作者還定義了一個rank-aware error rate指標:

並在該指標的基礎上進一步定義了相對誤差率: ,舉個例子,50%的相對錯誤率就表示稠密向量表示的bad case只有BM25向量表示的一半。

Model

作者採用基於BM25的ElasticSearch實現了稀疏向量檢索,針對稠密向量檢索,作者訓練了基於DistilRoBERTa-base的孿生網路,損失函式採用的是對比學習常用的InfoNCE loss:

其中負樣本的取樣方式為批內負取樣,併為每個 加入了一個BM25檢索出的困難負樣本(hard-negative),為了對比輸出向量維數對模型效能的影響,作者在模型的平均池化層後面額外接了一個線性變換層。

Experiments

Increasing Index Size

如下表實驗結果所示,當我們將索引量從一萬增加到八百萬的時候,所有檢索模型的效能均出現了明顯的下降,稠密向量表示和稀疏向量表示的效能差距也逐漸縮小。當向量維數過小時(128 dim),模型效能會出現小幅下降,雖然增大向量維數可以一定程度上緩解索引量增大的影響,但在巨大的索引量面前,增大維數帶來的效能提升是微乎其微的。

下表展示了稠密向量與BM25向量比較的相對錯誤率,隨著索引量的增大,稠密向量檢索和BM25向量檢索的差距逐漸減小。

Index with Random Noise

如果我們將大量隨機字串加入文件庫,模型效能會受到影響嗎?由於MS MACRO資料集的標註是不充分的,也就是說每個查詢只標註了一個相關文件,但實際上可能有多個文件都是相關的,為了防止相關但未被標註的文件對實驗結果的影響,作者假定檢索的時候只存在一個相關索引向量和一堆隨機生成的向量,這些隨機向量是通過將長度為20~150的隨機字串輸入模型後得到的,在實驗中,作者統計有多少隨機字串與查詢的相似度高於相關文件與查詢的相似度。

實驗結果如下表所示,隨著加入的隨機字串數量的增多,稠密向量表示的效能出現了明顯的下降,具體來說,當我們加入了一億個隨機字串的時候,每十個查詢中就有一個查詢會返回隨機字串,這樣高的錯誤率在實際應用中是難以容忍的。值得注意的是,BM25卻完全沒有受到隨機字串的影響,這是因為生成和查詢詞彙匹配的字串的概率是非常低的。另外作者還認為實驗結果表明錯誤率比理論估計增長的速度更快,這說明稠密向量的分佈非常集中,只佔據了整個向量空間的一小部分,不過該結論僅僅是一個直觀感受。

為了直觀地感受稠密向量的分佈情況,我們可以將稠密表示的查詢向量,文件向量和隨機字串向量通過UMAP可視化出來,如下圖所示,可以發現隨機字串向量(紅色)和查詢、文件向量有較大部分的重合。

Discussion

這篇論文從理論和實驗的角度證明了稠密向量檢索的假陽性率會隨著索引量的增大和向量維數的減小而增大,雖然稠密向量檢索具有很好的發展前景,但需要知道目前的稠密檢索通常更適用於量級較小且乾淨的索引,當前的模型通常都是在小索引量的資料集上進行的實驗,得出的結論可能不適合大資料集。因此並不是在任何場景下稠密檢索都要優於稀疏檢索,SentenceBERT也並不能完全替代BM25,當索引量過大時,如何有效結合稀疏向量索引高精度和稠密向量索引高召回的優勢,移除噪聲的干擾,其實是一個值得關注的方向。