利用CUR分解加速交互式相似度模型的检索

2022-11-10 06:11

©PaperWeekly 原创 · 作者 | 苏剑林

单位 | 追一科技

研究方向 | NLP、神经网络

文本相似度有“交互式”和“特征式”两种做法，想必很多读者对此已经不陌生，之前笔者也写过一篇文章《CoSENT：特征式匹配与交互式匹配有多大差距？》来对比两者的效果。总的来说，交互式相似度效果通常会好些，但直接用它来做大规模检索是不现实的，而特征式相似度则有着更快的检索速度，以及稍逊一筹的效果。

因此，如何在保证交互式相似度效果的前提下提高它的检索速度，是学术界一直都有在研究的课题。近日，论文《Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization》[1] 提出了一份新的答卷：CUR 分解。

问题分析

在检索场景下，我们一般有一个数量巨大的待检索集，不失一般性，我们可以假设是恒定不变的。检索的任务是对于任意的请求，找出中与最相关的若干个结果。交互式相似度模型是直接训练了一个相关性的打分函数，理论上我们可以对任意计算，然后进行降序排列。但这意味着每次检索的计算量都是，而且中间计算结果无法缓存，所以成本是难以接受的。

计算量可以接受的是具有矩阵分解形式的相似度，对于单个样本来说，就是基于内积的相似度及其变体，经典的实现是经过编码器编码为两个向量，然后算内积，这就是特征式相似度。这样的方案有几个特点：1、所有的可以实现算好并缓存；2、跟所有的算内积可以转化为矩阵乘法，可以充分并行快速计算；3、还可以通过 Faiss 等工具借助近似算法进一步检索速度。

所以，要加速交互式相似度的检索速度的思路，就是将它转化为矩阵分解的形式，比较经典的实现方案就是用一个特征式相似度模型去蒸馏学习交互式相似度的效果。Google 这篇论文的精巧之处在于，不引入任何新的模型，直接在原本交互式相似度模型的基础上利用 CUR 分解来实现加速，该方案被命名为 ANNCUR。

矩阵分解

CUR 分解是矩阵分解的一种，而说到矩阵分解，很多读者第一反应可能是 SVD，但事实上大家对 SVD 如此敏感的原因，不是 SVD 有多么通俗易懂，而是 SVD 被介绍得多。要说到直观易懂，CUR 分解明显更胜一筹。

其实，我们也可以用统一的视角去理解 SVD 和 CUR 分解：对于一个打分函数，我们希望构造如下近似

一般情况下有限制，使得它成为一个压缩分解。我们可以将看成是的一个“代表集”（或者“聚类中心”，反正都只是形象理解，可以随意），相应地看成是的一个“代表集”，那么上述分解就会变得很形象：

的打分，近似于先将与的“代表” 算打分，然后将与的“代表” 算打分，然后通过权重加权求和。

也就是说，与的直接交互，转化为它们分别与“代表”进行交互，然后再将结果进行加权。这样做的好处很明显，就是当都确定后，所有的都可以事先算好，作为一个矩阵缓存起来，然后每次检索，我们都只需要算次，然后再执行一次矩阵乘法（基于内积检索），所以检索的计算量从转化为（借助Faiss等工具，基于内积的检索可以近似优化到，因此可以忽略）。

假设请求集也是有限的，那么所有的就构成一个的矩阵，而相应地分别对应于的矩阵、的矩阵、的矩阵，式 (1) 就变成矩阵分解：

CUR分解

如果将限制为对角矩阵，而、不做特殊限制，那么对应的分解就是 SVD。SVD 相当于虚拟出了若干个“代表”出来，使得最终的拟合效果会比较好，但这样由算法自行构造出来的“代表”，我们很难理解它的具体含义，也就是可解释性差点。

CUR 分解则更直观一些，它认为“代表”应该是原来群体之一，也就是从的“代表”应该从它们自身集合挑出来的子集，即。这样一来，就是原来的之一，因此可以沿用的打分函数，即

于是，待定的函数就只有了。从矩阵分解的角度来看，此时式（2）中的就是的若干列组成的子矩阵，就是的若干行组成的子矩阵，要计算的就剩下矩阵。的计算也很直观，我们先考虑一个非常特殊的情形，且，此时 CUR 分解为，、都是方阵。由于此时已经取了全体作为代表，我们自然希望此时是而不是，取的话，可以直接解得。

然而，这意味着要是可逆的，但一般情况下未必成立。这时候要将矩阵的逆运算进行推广，我们称为“伪逆” [2]，记为。特别地，伪逆对于非方阵也有定义，因此当时，同样可以解得。最后，当或时，结果也类似的，只不过求伪逆的矩阵换成与的交集矩阵（即的若干行、若干列交集的元素拼成的矩阵）：

整个过程如下图所示：

▲ CUR分解示意图

加速检索

其实本文也不是第一次涉及 CUR 分解，去年初的文章《Nyströmformer：基于矩阵分解的线性化 Attention 方案》介绍的 Nyströmformer，其实也是基于 CUR 分解思想来设计的，原始论文还花了不少的篇幅来介绍 CUR 分解。ANNCUR 则是利用 CUR 分解来做检索加速，由此可见 CUR 的应用也很广泛。