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

©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 的应用也很广泛。

加速的原理刚才已经稍微提及过了，现在再来总结一下。首先，我们分别挑若干个有代表的 和 ，算出它们两两打分构成矩阵 ，求伪逆后得到矩阵 ，然后提前算好 与 的打分矩阵 ，把 存起来。最后，对于每一个需要查询的 ，与每一个 都算打分，得到一个 维向量，然后将这个向量与缓存起来的矩阵 相乘，就得到了 与每一个 的打分向量了。

ANNCUR 的大致原理就是这样，具体的细节大家可以自行阅读原论文，比如交互式相似度模型换成论文说的 [EMB]-CE 版本效果会更好等。可能有读者想问“有代表的 要怎么选？”，事实上，大多数情况下都是随机选的，这就留下了一些提升空间，比如可以聚类后选最接近聚类中心的那个，这些就看大家自由发挥了。

另外要指出的是，CUR分解本身只是一种近似，它肯定有误差，所以该加速方案主要是为检索场景设计的，检索场景的特点是比较在乎 topk 的召回率，而不是特别要求 top1 的精确率，我们可以用 CUR 分解加速来召回若干个结果后，再用精确的 做一次重排序来提高准确度。

▲ ANNCUR的部分实验结果图

文章小结

本文回顾了矩阵分解中的 CUR 分解，并介绍了它在加速交互式相似度检索方面的应用。

参考文献

[1] https://arxiv.org/abs/2210.12579

[2] https://en.wikipedia.org/wiki/Moore–Penrose_inverse

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·