作者 | Maple小七 整理 | NewBeeNLP
今天分享来自 NAACL 2021的一篇文章，一种基于上下文倒排索引的信息检索模型：「COIL(COntextualized Inverted List)」。
COIL有效地结合了Lexical IR和Neural IR各自的优点，通过建立高效的上下文倒排索引缓解了传统检索模型中的词汇不匹配和语义不匹配的问题，同时比起近几天发展起来的稠密向量检索模型，COIL引入了更多的细粒度语义信息，在准确度和速度上均取得了更优秀的表现，是一个非常具有实用价值的检索模型。
- 论文：COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List
- 地址：https://arxiv.org/abs/2104.07186
先验知识
基于词汇检索
以BM25为代表的传统信息检索系统通过query和document之间的词汇重叠信息来判断query和document之间的相关度，得益于高效的倒排索引技术，这类基于词汇的检索方式(Lexical IR)依旧是当今检索系统的主流方法。
众所周知，基于BOW假设和统计语言模型和的Lexical IR主要面临如下两个难题：
- 「词汇不匹配(vocabulary mismatch)：」 如
cat和kitty均表示“猫” - 「语义不匹配(semantic mismatch)：」 如
bank of river和bank in finance中的bank，前者表示“河岸”，后者表示“银行”
早期的研究主要通过词形归一，N-grams匹配，查询扩展等技术来缓解上述两个问题，然而这些改进方式本质上依旧是基于词袋假设的，没有从根本上解决上面的两个问题，因此这类模型对自然语言的建模能力非常有限。
基于神经网络检索
为了解决词汇不匹配的问题，基于软匹配(soft matching)的神经检索模型(Neural IR)被提出来，早期的尝试包括通过无监督地计算「预训练词向量」(如word2vec、GloVe)的相似度来获取匹配分数，更有效的一种方式是以「DSSM孪生神经网络」为代表的有监督模型，即将query和document分别编码成向量并计算向量相似度，后来人们意识到仅靠单个稠密向量很难编码文本的细粒度信息(fine-grained information)，因此提出了不少以DRMM为代表的「全连接交互式模型」，然而这些交互式模型的计算量非常巨大，仅仅适用于候选列表的最终精排阶段，因此工业界常常把检索系统形式化为「召回-排序(Retrieve-Rerank)」 或者更复杂一点的召回-粗排-精排流水线。
基于深度语言模型检索
以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
作者在MSMARCO passage(8M英文文章，平均长度60)和MSMARCO 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更高效的检索模型。
- END -
