【向量检索研究系列】快速入门
1. 向量检索介绍
1.1 概念介绍
随着互联网的不断发展，产生了各种各样的海量数据，比如图片、文本、视频和语音等非结构化数据，这些数据可以通过人工智能技术提取出特征向量，然后通过对这些特征向量的计算和检索来实现对非结构化数据的分析和检索，如何对非结构化的向量数据进行高效检索即为向量检索技术的核心问题。
1.2. 应用场景
向量检索的应用场景非常丰富，比如：
- 推荐系统：广告推荐、猜你喜欢等；
- 图片识别：以图搜图，通过图片检索图片。具体应用如：车辆检索和商品图片检索等；
- 自然语言处理：基于语义的文本检索和推荐，通过文本检索近似文本；
- 声纹匹配，音频检索；
- 文件去重：通过文件指纹去除重复文件；
- 新药搜索；
举几个简单的例子
如APP的开屏广告推荐、淘宝的以图搜图、搜索引擎的联想词推荐，虽然这些场景可以用其它技术实现，但向量检索也是一个可行的方案。
2. 距离计算
向量检索的过程是计算向量之间的相似度，最后返回相似度较高的TopK向量返回，而向量相似度计算有多种方式，不同的计算方式也适用于不同的检索场景。
对于浮点型向量和二值型向量有着不同的距离计算方式。
浮点型向量计算方式
- 内积（IP）
- 欧式（L2）
- 余弦（Cosine）
二值型向量计算方式
- 汉明距离 (Hamming)
- 杰卡德距离 (Jaccard)
- 谷本距离 (Tanimoto)
介绍距离计算之前，简单了解一下向量归一化公式，归一化后，向量模长|X’|等于1。
2.1 内积距离
内积距离计算的是两个向量在方向上的差异，夹角越小越相似，因此内积值越大越相似。
两条向量内积距离的计算公式为：
内积更适合计算向量的方向而不是大小，通常用于推荐场景。
内积在几何意义上是计算一条向量在另一条向量上的垂直投影长度。
2.2 欧式距离
欧氏距离计算的是两点之间最短的直线距离，距离值越小越相似。
欧氏距离的计算公式为：
其中 a = (a1, a2,..., an) 和 b = (b1, b2,..., bn) 是 n 维欧氏空间中的两个点。
归一化后，欧式距离与余弦相似度呈单调关系。
欧氏距离是最常用的距离计算方式之一，应用广泛，适合数据完整，数据量纲统一的场景。
欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异。
2.3 余弦距离
余弦距离计算的是两个向量之间的夹角余弦值，夹角越小越相似，因此余弦相似度值越大越相似。
假设向量 A和B归一化后的向量分别是 A’和B’ ，则
归一化后，内积与余弦相似度计算公式等价。
余弦距离和内积距离更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题。
举例：统计两部剧的用户观看行为，用户A的观看向量为(0,1)，用户B为(1,0)；此时二者的余弦距很大，而欧氏距离相对较小；我们分析两个用户对于不同视频的偏好，更关注相对差异，显然应当使用余弦距离或内积距离。
2.4 汉明距离
汉明距离计算二进制字符串之间的距离。两个等长字符串之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。
比如，假设有两条字符串 1101 1001 和 1001 1101。比较时，如果字符相同用 0 表示，如果字符不同则用 1 表示。
11011001 ⊕ 10011101 = 01000100
所以以上两条字符串之间的汉明距离为 2。
2.5 杰卡德距离
杰卡德相似系数计算数据集之间的相似度，计算方式为：数据集交集的个数和并集个数的比值。计算公式可以表示为：
杰卡德距离是用来衡量两个数据集差异性的一种指标，被定义为 1 减去杰卡德相似系数。对于二值变量，杰卡德距离等价于谷本系数。
杰卡德距离适合字符串相似性度量。
2.6 谷本距离
对于二值变量，谷本距离公式可表示为：
值域从 0 到正无穷。
对于二值变量，谷本系数等价于杰卡德距离：
对于二值变量，谷本系数值域为 0 到 +1（+1 的相似度最高）
3. 基础算法
了解了向量检索的计算相似度方式，如何加快检索速度是研究的重点。向量检索的本质是近似近邻搜索（ANNS），尽可能减小查询向量的搜索范围，从而提高查询速度，目前业界的近邻搜索算法主要分为基于树、图、量化和哈希四类。本文主要是对这四类算法思想进行简要的介绍。
3.1 基于树
基于树的结构进行快速检索的主要思想是通过对K维空间进行多次划分，检索时只需对少数特定子空间进行检索即可，加快检索速度，其原理类似二叉树搜索。优点是简单易实现，缺点是不适合高维度向量场景。
基于树的搜索算法主要有KD树和Annoy算法，本文主要对KD树进行简要介绍，帮忙大家加深对K维空间划分和检索的理解。
- KD-树（K-Dimensional Tree）
- Annoy（Approximate Nearest Neighbors Oh Yeah）
KD树
KD树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x，y，z..）中划分的一种数据结构，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。
KD树构造算法：
- 选取方差值最大的数据维度为坐标轴，以训练集中的所有数据坐标中的中位数作为切分点，将超矩形区域切割成两个子区域。将该切分点作为根结点，由根结点生出深度为1的左右子结点，左节点对应坐标小于切分点，右结点对应坐标大于切分点。
- 对深度为i的结点，选择为切分坐标轴，以该结点区域中训练数据坐标的中位数作为切分点，将区域分为两个子区域，且生成深度为i+1的左、右子结点，左节点对应坐标小于切分点，右结点对应坐标大于切分点。重复以上操作，直到两个子区域没有数据时停止。
对于数据集{(6,5),(1,3),(-6-5),(-4-10),(-2,-1),(-5,12),(2,13),(17,-12),(8,-22),(15,-13),(10,-6),(7,15),(14,1)}
该数据集的第一个维度的方差值较大，因此选择第一个维度作为切分轴，其维度中位数为6，选择(6,5)作为切分点，如下左图。重复构造方法的步骤2，经过多次切分后得到的切分图如下右图。
每次切分点为树的节点，最终构造的树结构如下，右侧的X和Y分别表示基于第一个维度和第二个维度进行切分。
一般而言，在空间维度(d<=30)比较低的时候，KD树是比较高效的, 针对高维数据提出了优化的KD-tree with BBF（Best Bin First）算法。
KD树的检索算法：
假设在数据集S中搜索p节点的邻近topK节点。
- 根据目标p的坐标和kd树的结点向下进行搜索，如果树的结点root是以数据集的维度d以来切分的，那么如果p的维度d坐标值小于root，则走左子结点，否则走右子结点。
- 到达叶子结点时，将其标记为已访问。如果S中不足k个点，则将该结点加入到S中；否则如果S不空且当前结点与p点的距离小于S中最长的距离，则用当前结点替换S中离p最远的点。
- 如果当前结点不是根节点，执行（a）；否则，结束算法。
（a）回退到当前结点的父结点，此时的结点为当前结点（回退之后的结点）。将当前结点标记为已访问，执行（b）和（c）；如果当前结点已经被访过，再次执行（a）。
（b）如果此时S中不足k个点，则将当前结点加入到S中；如果S中已有k个点，且当前结点与p点的距离小于S中最长距离，则用当前结点替换S中距离最远的点。
（c）计算p点和当前结点切分线的距离。如果该距离大于等于S中距离p最远的距离并且S中已有k个点，执行步骤3；如果该距离小于S中最远的距离或S中没有k个点，从当前结点的另一子节点开始执行步骤1；如果当前结点没有另一子结点，执行步骤3。
假设p节点为(-1,-5)，在数据集中的位置如以下左图，检索邻近3个节点，经过上述搜索算法后，得到3个邻近节点（绿色节点），坐标为(-6,-5), (-1,-3), (-2,-1)。
在树中遍历的节点为左子树，如下图中的蓝色线条标识节点，在根节点处结束算法。
Annoy
Annoy（Approximate Nearest Neighbors Oh Yeah）是一种用超平面把高维空间分割成多个子空间，并把这些子空间以树型结构存储的索引方式。
在查询时，Annoy 会顺着树结构找到距离目标向量较近的一些子空间，然后比较这些子空间里的所有向量以获得最终结果。显然，当目标向量靠近某个子空间的边缘时，有时需要大大增加搜索的子空间数以获得高召回率。因此，Annoy 会使用 N 次不同的方法来划分全空间，并同时搜索所有划分方法以减少目标向量总是处于子空间边缘的概率。
Annoy 能够使用静态文件作为索引，意味着可以跨进程共享索引。它还创建了大量的基于只读文件的数据结构，这些数据结构被嵌入内存中，以便许多进程可以共享相同的数据。Annoy 的另一个好处是它试图最小化内存占用，因此索引非常小。
具体算法参考：Nearest neighbors and vector models – part 2 – algorithms and data structures
3.2 基于图
基于图的结构进行快速检索的主要思想是通过对图中邻居节点连线（高速公路）快速缩小搜索范围，加快检索速度，其原理类似Redis跳表。优点是查询速度快，缺点是构建索引耗时长，内存占用大。
基于图的搜索算法主要有NSW和HNSW算法，本文主要对HNSW图进行简要介绍，帮忙大家加深对图的构造和检索的理解。
- NSW（Navigating Small World）
- HNSW（Hierarchical Navigating Small World）
NSW
朴素的图搜索算法
如果要找到粉红色的点最近的点，我们从任一个点开始，比如A，从A的相邻的点中(B,C,D)找到离目标最近的点D，接下来从D相邻的点(F,J,E)中找到离目标最近的点E，而在E的相邻的点中(B,D,G,J)中，E是离目标最近，那搜索停止，E就是我们要找的点。
但是K点无法查询，E和L邻近点之间没有连线，邻居节点个数无法确定。
NSW（Navigable Small World）是一种基于图的基础搜索算法，基于朴素的图搜索算法，保证了所有的点都有相邻的点，相邻 的点有连线，邻近点的个数可以指定。
NSW构图算法：
向图中逐个插入点，插图一个全新点时，查找到与这个全新点最近的m个点（m由用户设置），连接全新点到m个点的连线。那么越先被插入的点，越有可能有高速公路，因为插入某一个点时，链接与它相近的点。但是在后面的构图过程中可能会有更近的点插入，那么这些原先的连线就成了高速公路。
NSW搜索机制：
在base node的近邻中找到与query最近的点，然后把这个点更新为新的base node，再重复以上过程，直到找到query。
NSW论文中配了如下这样一张图，黑色是近邻点的连线，红色线就是“高速公路机制”了。我们从enter point点进入查找，查找绿色点临近节点的时候，就可以用过红色连线“高速公路机制”快速查找到结果。
HNSW
HNSW（Hierarchical Navigating Small World）是一种基于图的索引算法，也是对NSW方法的改进，它由多层的邻近图组成，因此称为分层的NSW方法。它会为一张图按规则建成多层导航图，并让越上层的图越稀疏，结点间的距离越远；越下层的图越稠密，结点间的距离越近。
构图算法：
HNSW将空间中的向量按下图的形式组织，每一个节点插入时，首先将数据保存在第0层。然后随机一个层数，从该层开始逐层往下遍历，每层都将该节点以节点内部id代表插入，并按NSW的构图规则连接M个近邻节点，直至第0层，高层到低层之间的连线即为高速公路。
搜索算法：
搜索时从最上层开始，找到本层距离目标最近的结点后作为下一层的入口，进入下一层再查找。如此迭代，快速逼近目标位置。
- 0层以上，从enterpoint开始，寻找离目标最近的点。
- 0层，寻找最近的k个点。
HNSW采用类似跳表的思想，在高层跳过大量离目标点较远的点，从而快速定位到离目标较近的点，从而缩小搜索范围。在构图时采用启发式搜索选择连接邻居节点，从而防止出现不连通图的情况。搜索过程中维护动态list，从而减少遗漏的情况。
基于图的向量检索算法在向量检索的评测中性能都是比较优异的。如果比较在乎检索算法的效率，而且可以容忍一定的空间成本，多数场景下比较推荐基于图的检索算法。而HNSW是一种典型的，应用广泛的图算法，很多分布式检索引擎都对HNSW算法进行了分布式改造，以应用于高并发，大数据量的线上查询。
但是HNSW的缺点就是，除了保存数据之外，还需要一定的内存维护图的关系，而且每个节点分配固定的内存，其中有些没有使用而造成一定的浪费。
为了提高性能，HNSW 限定了每层图上结点的最大度数 M 。M的合理范围在[2,200]。M越高，对于本身具有高维特征的数据集来讲，recall可能越高，性能越好；M越低，对于本身具有低维特征的数据集来讲，性能越好。
此外，建索引时可以指定 efConstruction，efConstruction 越大，构造时间越长，index quality越好。有时，efConstruction 增加的过快并不能提升index quality。有一种方法可以检查efConstruction 的选择是否可以接受。计算recall，当ef=efConstruction ，在M值时，如果recall低于0.9，那么可以适当增加efConstruction 的数值。
查询时可以用 ef 来指定搜索范围，ef值越大，搜索范围越大，搜索时间也越长，一般和efConstruction值搭配调节。
3.3 基于量化
基于量化的结构进行快速检索的主要思想是将高精度的数值或向量，通过损失一定的精度，用近似的形式进行存储和计算，加快检索速度。优点是减少计算次数，加快检索速度，缺点是有一定的精度损失。
基于量化的方法
- SQ（ ScalarQuantization ）
- PQ（ Product Quantization ）
SQ是将每一个维度量化成指定位数的一个数，比如将32位的int量化成8位的int，通过损失一定的精度，缩减存储和计算成本，比较简单，本文主要对PQ进行简要介绍，帮忙大家加深对量化的过程和检索的理解。
PQ
乘积量化（PQ）算法是和VLAD算法是由法国INRIA实验室一同提出来的，为的是加快图像的检索速度。
量化算法
PQ先将D维空间切分成M份，现在考虑一个D=128维的原始向量，它被切分成了M=8个d=16维的短向量。
同时每个短向量都对应一个量化的索引值，索引值即该短向量距离最近的聚类中心的编号，每一个原始向量就可以压缩成M个索引值构成的压缩向量，只要设计好了数据结构，就可以获得所有1M数据的压缩向量。压缩向量其实就是M个索引值，每个索引值对应一个聚类中心，所以要同时保存压缩向量和聚类中心，下图中的矩阵为压缩后的向量。
搜索算法
有2种方法做相似搜索，一种是SDC(symmetric distance computation)，另一种是ADC(asymmetric distance computation)。SDC算法和ADC算法的区别在于是否要对查询向量（x）做量化。
- 对称距离计算：直接使用两个压缩向量x，y的索引值所对应的码字q(x),q(y)之间的距离代替之，而q(x),q(y)之间的距离可以离线计算，因此可以把q(x),q(y)之间的距离制作成查找表，只要按照压缩向量的索引值进行对应的查找就可以了，所以速度非常快；
- 非对称距离计算：使用x，q(y)之间的距离代替x，y之间的距离，其中x是测试向量。虽然y的个数可能有上百万个，但是q(y)的个数只有k个，对于每个x，我们只需要在输入x之后先计算一遍x和k个q(y)的距离，制成查找表（因为只有k个，所以速度是非常快的），然后按照y对应的压缩向量索引值进行取值操作就可以了。
查找过程先将查找向量x进行分段，在每个子段计算x子段到对应256个聚类中心的距离，可以使用对称距离计算或非对称距离计算，计算结果存为256*4码本。然后在每段通过查询码本计算x与每个y的距离（用到所属聚类中心的距离近似计算），然后将每段计算的对应向量的结果累加求和，最后取topK向量。
通过查询码本计算向量的距离，可以大大节省向量计算时间，提高检索速度，聚类的中心越多，检索的精度也越高。
PQ算法可以搭配IVF算法（kmeans聚类）组成IVF_PQ算法达到更快的检索速度。
3.4 基于哈希
基于哈希的结构进行快速检索的主要思想是利用相似度很高的数据以较高的概率映射成同一个hash值，相似度很低的数据以极低的概率映射成同一个hash值，将高维数据降维到低维数据，提高检索效率。优点是能高效处理海量高维数据的最近邻问题，缺点是会有一定的数据失真。
基于哈希的方法
- LSH（Locality-Sensitive Hashing）
LSH
LSH是一将原始数据空间中的两个相邻数据点通过相同的映射或投影变换后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。
LSH定义：将这样的一族hash函数 H={h:S→U} 称为是(r1,r2,p1,p2)敏感的，如果对于任意H中的函数h，满足以下2个条件：
- 如果d(O1,O2)<r1，那么Pr[h(O1)=h(O2)]≥p1
- 如果d(O1,O2)>r2，那么Pr[h(O1)=h(O2)]≤p2
其中，O1,O2∈S，表示两个具有多维属性的数据对象，d(O1,O2)为2个对象的相异程度，也就是相似度，当足够相似时，映射为同一hash值的概率足够大；而足够不相似时，映射为同一hash值的概率足够小。
如果我们对原始数据进行一些hash映射后，我们希望原先相邻的两个数据能够被hash到相同的桶内，具有相同的桶号。取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查询数据相邻的数据。
哈希函数是局部敏感的：相近的样本点对比相远的样本点对更容易发生碰撞。
LSH的设计能够通过相应的参数控制出现数据失真的概率，最关键的是构造合适的哈希函数族使得最近邻查找更为精确。
4. 总结
本文主要对向量检索的概念、应用场景、距离计算方式和基础算法进行了介绍，相信你已经对向量检索技术已经有了初步了解，对于算法部分的介绍，由于篇幅问题没有进行详尽的介绍，推荐自行查询进一步消化理解。后续还将进一步分享向量检索的技术调研、测试、应用和思考。
5. Reference
