COIL: Contextualized Inverted List

語言: CN / TW / HK

Source: NAACL 2021: COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List

TL;DR: 本文提出了一種基於上下文倒排索引的資訊檢索模型: COIL(COntextualized Inverted List) ,COIL有效地結合了Lexical IR和Neural IR各自的優點,通過建立高效的上下文倒排索引緩解了傳統檢索模型中的詞彙不匹配和語義不匹配的問題,同時比起近幾天發展起來的稠密向量檢索模型,COIL引入了更多的細粒度語義資訊,在準確度和速度上均取得了更優秀的表現,是一個非常具有實用價值的檢索模型。

Introduction

Lexical Retriever

以BM25為代表的傳統資訊檢索系統通過query和document之間的詞彙重疊資訊來判斷query和document之間的相關度,得益於高效的倒排索引技術,這類基於詞彙的檢索方式(Lexical IR)依舊是當今檢索系統的主流方法。

眾所周知,基於BOW假設和統計語言模型和的Lexical IR主要面臨如下兩個難題:

  • 詞彙不匹配(vocabulary mismatch):catkitty 均表示“貓”
  • 語義不匹配(semantic mismatch):bank of riverbank in finance 中的 bank ,前者表示“河岸”,後者表示“銀行”

早期的研究主要通過詞形歸一,N-grams匹配,查詢擴充套件等技術來緩解上述兩個問題,然而這些改進方式本質上依舊是基於詞袋假設的,沒有從根本上解決上面的兩個問題,因此這類模型對自然語言的建模能力非常有限。

Neural Ranker

為了解決詞彙不匹配的問題,基於軟匹配(soft matching)的神經檢索模型(Neural IR)被提出來,早期的嘗試包括通過無監督地計算 預訓練詞向量 (如word2vec、GloVe)的相似度來獲取匹配分數,更有效的一種方式是以 DSSM孿生神經網路 為代表的有監督模型,即將query和document分別編碼成向量並計算向量相似度,後來人們意識到僅靠單個稠密向量很難編碼文字的細粒度資訊(fine-grained information),因此提出了不少以DRMM為代表的 全連線互動式模型 ,然而這些互動式模型的計算量非常巨大,僅僅適用於候選列表的最終精排階段,因此工業界常常把檢索系統形式化為 召回-排序(Retrieve-Rerank) 或者更復雜一點的召回-粗排-精排流水線。

Deep LM Based Ranker and Retriever

以BERT為代表的深度語言模型(deep LM)對Neural IR的發展產生了巨大的影響,如下圖所示,自BERT提出以來,語義匹配任務最通用的方法是將query,document拼接起來輸入到BERT中,然後利用BERT的 [CLS] 輸出匹配分數,雖然基於deep LM的排序方法通過 全連線交叉注意力 很好地解決了詞彙不匹配和語義不匹配的問題,但是交叉注意力的計算量實在過於龐大,因此基於BERT的reranker一般只會用於最終的精排階段。雖然後續也出現了以PreTTR為代表的更輕量的排序模型,但對於最頂層的全域性語料庫檢索(full-collection retrieval)的召回階段來說,交叉注意力的計算量依舊過於昂貴。因此人們通常會用簡單的BM25召回一批用於排序的候選文件,然後再用BERT reranker做精排。

deep LM大大改進了精排的準確度,那麼deep LM可以提升召回模型的效能嗎?當然可以,因此有人研究瞭如何通過deep LM來增強Classical IR,比如DocT5Query通過基於T5的問題生成模型來擴充文件內容,緩解詞彙不匹配的問題,又比如DeepCT利用BERT來修正詞權重以更好地匹配重點詞,然而這些方法依舊 沒有從根本上解決詞彙不匹配的問題

因此,更有價值的一條研究線路是延續以DSSM為代表的 稠密向量表示 的思想,如下圖所示,這類模型預先建立文件的稠密索引,然後通過最近鄰向量搜尋來檢索文件。以SentenceBERT和DPR為代表的基於deep LM的稠密檢索模型在多個檢索任務上取得了最優效能,後續也有很多研究探討了如何訓練出一個泛化效能更好的稠密檢索模型,比如語義殘差嵌入(semantic residual embeddings)和基於近似最近鄰的對比學習(ANN negative contrastive learning)。

之前提到,單個稠密向量實際上很難表示文字的細粒度語義資訊,因此 多向量表示系統(multi-vector representation) 也得到了探索,比如Poly-encoder將query編碼為一組向量,而將document編碼為單個向量,Me-BERT的編碼方式恰好和Poly-encoder相反,最近提出的ColBERT將query和document均編碼為一組向量,然後進行all-to-all的token級別的軟匹配,模型結構如下圖所示。這種方式依舊能像DPR那樣進行全域性語料庫級別的檢索,然而由於ColBERT將document的所有token都進行了稠密編碼,也就是需要將文件的所有token向量存到單個索引中,這導致ColBERT與DPR相比,索引的複雜度直接增加了一個數量級,並且在查詢過程中需要遍歷所有索引,因此ColBERT對硬體的要求很高,對大規模語料庫來說往往是不可承受的。

觀察DPR和ColBERT的模型結構,我們自然會思考是否存在介於這兩者之間的檢索模型,該模型的複雜度和檢索速度接近於DPR,而檢索準確度接近於ColBERT,而作者提出的COIL模型正好是DPR和ColBERT非常好的折中。

Methodologies

Preliminaries

由於COIL是基於Lexical IR的,因此先簡單介紹一下經典的Lexical IR系統,Lexical IR依賴於query和document之間的詞彙重疊資訊來為它們之間的相關性打分,相關性得分通常被定義為各個匹配詞彙的匹配分數之和,而具體的打分函式通常基於詞彙頻率(TF)和倒文件頻率(IDF),下面是一種通用的數學定義:

其中 表示查詢和文件的重疊詞彙, 用於抽取詞彙資訊, 為打分函式,根據這個定義,應用最為廣泛的BM25演算法可以表示為:

其中 表示詞彙 分別在文件 和查詢 中的頻率, 表示 的倒文件頻率, , 均為超引數。

Lexical IR最大的優點之一就是高效,如下圖所示,由於打分過程只依賴於包含了query詞彙的document,因此利用倒排索引技術,在實際的檢索過程中我們 並不需要一一訪問語料庫中的所有document,而僅僅需要訪問倒排索引列表的一個很小的子集 ,這也是Lexical IR依舊是當今通用搜索引擎的基本框架的原因。

Contextualized Exact Lexical Match

當前的Neural IR和傳統的Lexical IR基本上是兩套不同的體系,Neural IR雖然通過軟匹配打破了精確匹配的效能瓶頸,具有更高的檢索準確度,但檢索效率卻遠不如基於倒排索引的Lexical IR,難以承載 千億文件級別的檢索需求 ,另外,Lexical IR還具有很好的 可解釋性和可控性 ,人們可以很容易地修復bad case,而我們無法很好地理解Neural IR的匹配模式是怎樣的。

COIL的出發點在於,將上下文表示引入Lexical IR系統能夠帶來多大的效能提升?換句話說,我們可不可以建立一個Lexical IR模型,但這個模型的匹配訊號是由上下文詞向量提供的,而不是依靠啟發式的TF-IDF?再具體一點,就是我們是否可以 將簡單的基於TF-IDF的打分規則替換成基於上下文語義的打分模型 ,來提高精確匹配的準確性?

總體來說,我們的目標是將簡單的基於詞彙頻率(TF)的匹配演算法改進為基於上下文語義表示的匹配演算法,首先,我們分別將query和document的token編碼為上下文向量:

其中 是將語言模型輸出的 維向量對映到更低維的 維向量,後續實驗會說明token的上下文表示並不需要過高的維度,低維向量就可以很好地編碼token級別的資訊。

根據上文提到的Lexical IR的數學定義,我們可以將引入上下文詞向量的詞彙匹配的打分函式定義為

注意這裡的求和只針對query和document的重疊詞彙 ,具體來說,我們首先針對每個查詢詞 ,首先匹配document中所有的相同詞 ,然後利用上下文詞向量分別計算 的點積相似度,並取出所有 中相似度最高的那個token的相似度,這裡的 運算是為了捕捉document中最重要的語義訊號。

由於Lexical IR精確匹配的限制, 沒有考慮到不同詞彙的相似度,因此面臨著詞彙不匹配的問題,針對這個問題,我們可以利用 [CLS] 來整合句子級表示

之間的相似度可以提供高層次的語義匹配資訊,緩解詞彙不匹配的問題,最終,COIL模型的打分函式為

後文我們將具有 [CLS] 匹配的模型稱為COIL-full,否則稱為COIL-tok,COIL-full模型的整體結構如下圖所示。

COIL模型是完全可微的,因此可以優化負對數似然函式來訓練模型:

和DPR的訓練過程一樣,訓練過程採用的負樣本 為批內負樣本和BM25提供的困難負樣本。

Index and Retrieval with COIL

如上圖所示,COIL可以預先計算好document的所有向量表示並建立倒排索引,具體來說,針對詞表 中的詞彙 ,我們首先將 在語料庫 的所有上下文向量表示匯聚起來,為 建立上下文倒排索引:

其中 是上文提到的token編碼,最後我們得到了整個語料庫的倒排索引: ,另外針對COIL-full,我們還需要加入

在實際的實現過程中,我們可以將 轉化為一個矩陣 ,同樣地,所有的 也可以整合為一個矩陣 ,這樣就可以把相似度計算轉化為非常高效的矩陣向量積,我們甚至還可以利用近似最近鄰搜尋來進一步提速,建立索引的過程如下圖所示:

在檢索過程中,給定一個查詢 ,模型首先將 的所有token編碼為向量 ,然後利用預先建立好的上下文倒排索引獲取索引子集 ,注意 ,最後通過矩陣向量乘法獲取 與 的匹配度,具體的檢索過程如下圖所示:

Connection to Other Retrievers

  • Deep LM based Lexical Index: DeepCT和DocT5Query通過Deep LM修正document的詞頻 ,這其實類似於 的COIL-tok模型,然而單個自由度的標量只能衡量詞彙的重要性(importance),而無法衡量詞彙間的語義一致性(semantic agreement)。
  • Dense Retriever: 以DPR為代表的稠密檢索模型其實等價於COIL-full中的 [CLS] 匹配,而COIL通過token級的語義匹配訊號來彌補了稠密檢索模型丟失了token級別的互動資訊的缺陷。
  • ColBERT: ColBERT計算了query和document所有詞項之間的匹配度:

而COIL藉助於高效的倒排索引,只需計算精確匹配的詞項之間的語義相似度,因此COIL比ColBERT更加高效。

Experiment & Result

作者在MSMACRO passage(8M英文文章,平均長度60)和MSMACRO document(3M英文文件,平均長度900)測試了不同模型,實驗詳細設定可參考原文,下面直接給出實驗結果。

Main Results

實驗結果如上表所示,可以看到COIL-tok超越了所有基於詞彙匹配的檢索系統(Lexical Retriever),雖然DeepCT和DocT5Query改進了啟發式的基於詞頻的打分方法,但依舊受制於語義不匹配的問題。

COIL-tok也超越了所有稠密檢索模型(Dense Retriever),從指標上可以看出COIL-tok在 提升precision的同時也能夠保證recall不下降 ,進一步加上 [CLS] 匹配的COIL-full能夠很好地處理詞彙不匹配的問題,進一步提升了模型表現。

COIL-full的表現和ColBERT的差距非常小,注意ColBERT是所有檢索模型中計算量最大的一個,而 COIL-full能夠通過精確詞彙匹配來有效地捕捉到最重要的互動資訊,忽略沒必要的詞項互動,因此能夠在計算量很小的條件下取得和ColBERT非常接近的表現。

在Rerank任務中,COIL與BERT reranker的差距也非常小,不過這個差距可能是由於候選列表是由BM25召回的,但總體上來說,在相同的表現下,COIL的排序速度(10ms)比BERT(2700ms)快很多。

Analysis of Dimensionality

接下來我們測試上下文詞向量的維度 [CLS] 的向量維度對模型速度和效能的影響,如下表所示,將 [CLS] 從768維降到128維會導致表現輕微的下降,將 從32降到8所帶來的影響很小,甚至可以獲得更高的MRR,這表明降維有時候能夠起到一定的正則化作用。

降維之後的模型推理速度會得到提高,這使得COIL模型可以比DPR更快,甚至與傳統的BM25的推理速度處於同一級別,經過近似搜尋和量化壓縮之後,模型速度還有望進一步提升。

Case Study

COIL與DPR這類稠密向量檢索模型的一個不同之處是COIL沒有使用統一的語義表示空間,而是 針對不同的token分別為其學習一個詞級的表示空間來度量同一個token在不同上下文下的相似度 ,因此COIL可以有效區分同一個token在不同上下文中的語義差異。

如上表所示,第一個查詢中的查詢詞 cabinet 在第一個文件中是“內閣”的意思,而在第二個文件中是“櫥櫃”的意思,而查詢句中的 cabinet 是第一種含義,因此COIL賦予了第一個文件中的 cabinet 更高的匹配分數。

在第二個查詢中, pass 在這兩個文件中都是“許可”的意思,但經過上下文化之後,COIL能夠捕捉到 priority pass 這個整體概念,因此賦予了第一個文件更高的匹配分數。

在第三個查詢中, is 是一個停用詞(stopwords),在Lexical IR中,停用詞一般是會被丟棄的,然而在這個例子中我們可以觀察到COIL能夠區分解釋句中的 is 和被動語態中的 is 的區別,因為第一個文件中的 is 是解釋定義,查詢句中的 is 也是尋求解釋,因此COIL賦予了第一個文件更高的匹配分數,同時由於 is 過於常見,COIL也並沒有像前面兩個例子那樣為 is 賦予過高的權重。

上述例子均說明COIL的確引入了大量語義資訊,讓檢索系統超越了單純的字面匹配,有效地解決詞彙不匹配和語義不匹配的問題。

Discussion

COIL表明稠密檢索和詞彙匹配的確能夠起到互補的作用,而COIL正是這兩者的一個很好的平衡,在精度和召回率上均取得了很好的結果,且推理非常高效,具有很廣泛的應用價值。總體來說,COIL針對如何在Lexical IR和Neural IR的交匯處設計出更優質的匹配模型這個問題邁出了很好的一步,相信未來會出現比COIL更高效的檢索模型。