想要飞速查找资源？谷歌新提出的向量相似性搜索算法也许能帮上忙！

原创让创新获得认可将门创投今天

收录于话题

#谷歌 1

#机器学习 1

#算法 2

#人工智能 4

关注并星标

从此不迷路

Jiangmen

From: Google 编译: T.R

近年来，机器学习极大地促进了计算机理解语言和语义的能力，同时也提高了抽象语言查询的能力。尽管如此，我们还是要面对计算资源的挑战，如何在数据库中尽可能快地找出与输入嵌入最为接近的嵌入表达呢？

为了解决这一问题，来自谷歌的研究人员通过压缩数据集向量的方法来加速向量间近似距离的计算，同时提出的新压缩技术大幅度提升了计算的精度。让我们来看看他们是如何做到的吧~

如果我们想要在庞大的文献数据库中利用特定的查询文本来精确地匹配标题、作者或者其他机器容易索引的指标，这类任务十分适合利用SQL语言在关系型数据库中进行检索。但我们如果想要查询一些例如“民国时期的诗词”这样更为抽象的概念，仅仅基于简单地度量两个短语间的相同单词数量来判断就变得难以实现了。

举个栗子🌰，在查询“sicence fiction”时会发现它与“future”的相似性高于“earth science”，尽管后一个短语有一个词语查询的短语相同，但“科幻小说”显然与“未来”的相关性更高一些，我们不能简单地看匹配词语的数量来确定抽象语义的相似性。

近年来机器学习极大地促进了计算机理解语言和语义的能力，同时也提高了抽象语言查询的能力。现代机器学习模型已经能够将文本、图像等输入转换为高维空间中的嵌入向量表示，使得相似的输入聚类地更为接近；可以为给定的查询计算出嵌入表示，同时在数据库中寻找与其最为相似的文献嵌入表示。通过这种方式，机器学家将先前抽象并难以细化的查询任务转换为了严格的数学问题。

尽管如此，我们还是要面对计算资源的挑战，如何在数据库中尽可能快地找出与输入嵌入最为接近的嵌入表达呢？庞大的数据库对于穷尽查找几乎是不可能，同时高维度的嵌入表示使得维度缩减也变得十分困难。为了解决这一问题，来自谷歌的研究人员通过压缩数据集向量的方法来加速向量间近似距离的计算，同时提出的新压缩技术大幅度提升了计算的精度！

向量相似性搜索的重要性

基于嵌入的检索技术更多的依赖于对于查询语句和数据库内容的语义理解，而不是简单的索引特征检索。在这一技术中，机器学习模型主要用来将查询字段和数据库项目映射到一个矢量嵌入空间中去，这使得嵌入间的距离具有了语义特性，更相似的项目间其距离也应该更接近。

用于将查询字段和数据库项目映射到嵌入空间中的模型(左)，右侧为嵌入空间，语义相似度越高的项目其在嵌入空间中就越接近。

为了得到查询结果，系统首先需要将查询语句映射到嵌入空间中去，随后需要遍历数据库中所有的嵌入结果计算出与查询嵌入最为接近的一个，这就是典型的最邻近搜索问题。度量嵌入向量相似性最为常用的标准是查询向量与数据库中向量的内积，基于这种方法的最邻近搜索则称为最大化内积最邻近搜索 (maximum inner-product search, MIPS)。

由于数据库动辄百万甚至几十亿量级，MIPS常常受到计算瓶颈的制约，穷尽搜索几乎是不现实的。所以我们必须找到一种MIPS的近似算法，在牺牲一定精度的情况下提高检索速度。

新型量化MIPS方法

很多先进的MIPS解决方案都利用了压缩数据库项目的方法，这使得近似的内积计算可以提升几倍的速度。通常人们使用学习量化的方法来进行压缩，利用数据库训练出一个表示向量的编码本，并利用它来近似表示数据库中的项目。

先前的向量量化机制对数据库中的元素进行量化的目标是最小化每一个向量与其量化后向量的平均距离。虽然这一度量方式很有用，但利用这一目标进行优化的过程并不等同于优化最邻近搜索的精度。本文工作的关键在于更高的平均距离编码也许能够在实际过程中带来更好的MIPS精度。

下面的例子具体阐述了这一思想。如下图所示有两个向量x1和x2需要量化到两个中心c1和c2上。我们的量化目标是最小化量化前后与q的内积。根据内积的几何关系，量化过程与将x投影到q上的过程类似，我们可以比较量化前后x在q上投影的幅度来比较相似性。

传统方法基于最小距离的方法会造成大小关系发生变化（左），而右侧方法则选择了较远的中心进行量化，虽然比起邻近的中心距离更远，但量化内积误差更小、量化的精度更高。

上面的例子说明，量化的方向与幅度一样重要！即使c1相较于c2距x1更远，但是c1相对于x1的偏移几乎与x1正交，而相对于c2的位移则几乎与x1平行。MIPS中平行方向上的误差将会造成更大的不良影响，因为这会对内积误差造成更大的影响。左图中使用传统的方法来选择距离每个x最近的中心点进行量化，这会使得两个x之间的大小关系在量化后发生错乱：x1在量化前与q的内积较小，而量化后则变大了！但如果我们将x1量化到c1，x2量化到c2，则这种大小关系则不会被改变。但显然x1量化到c1的距离比到c2的距离更远，那么该如何实现正确的量化呢？