典型场景：图像检索。高维检索。
本质： 很多稠密向量，要迅速找到某个点的临近点，并认为这是相似度最高的点。
原始数据的表达形式为，N维连续值的向量。如果针对一个query，进行暴力搜索，需要计算N次，并进行排序。而几乎所有的ANN方法都是对全空间的划分，可以迅速找到子空间，并与子空间内的数据进行计算。方法分为三大类：基于树的方法、哈希方法、矢量量化方法。
基于树的方法采用树这种数据结构的方法来表达对全空间的划分，其中又以KD树最为经典，下面分别对KD树和Annoy进行简单介绍。
1.1 KD树
KD树
构建树的过程，就是选择分裂节点，并分裂的过程。
节点选择：方差最大的那个维度。方差的大小可以反映数据的波动性。方差大表示数据波动性越大，选择方差最大的开始划分空间，可以使得所需的划分面数目最小，反映到树数据结构上，可以使得我们构建的KD树的树深度尽可能的小。(用方差进行选择，也就意味着特征值都在相同取值范围内)
分裂点：？
停止条件：？
在空间维度比较低的时候，KD树是比较高效的，当空间维度较高时，可以采用下面的哈希方法或者矢量量化方法。
1.2 Annoy
Annoy的核心是不断用选取的两个质心的法平面对空间进行分割，最终将每一个区分的子空间里面的样本数据限制在K以内。对于待插入的样本xi，从根节点依次使用法向量跟xi做内积运算，从而判断使用法平面的哪一边（左子树or右子树）。对于查询向量qi，采用同样的方式（在树结构上体现为从根节点向叶子节点递归遍历），即可定位到跟qi在同一个子空间或者邻近的子空间的样本，这些样本即为qi近邻。返回的结果无序，因为Annoy树不保存特征。保存原始的特征的坏处是造成占用内存过大，索引文件过大。
为了提高查询的召回，Annoy采用建立多棵树的方式。
2. 哈希方法（局部敏感哈希）
局部敏感：相近的样本点对比相远的样本点对更容易发生碰撞。
加速查找：首先找到查询样本落入在哪个cell(即所谓的桶)中，只需要在当前的cell中遍历比较，而不用在所有的数据集中进行遍历。
多表哈希：对于单表哈希，当我们的哈希函数数目K取得太大，查询样本与其对应的最近邻落入同一个桶中的可能性会变得很微弱，针对这个问题，我们可以重复这个过程L次，从而增加最近邻的召回率。这个重复L次的过程，可以转化为构建L个哈希表，这样在给定查询样本时，我们可以找到L个哈希桶（每个表找到一个哈希桶），然后我们在这L个哈希表中进行遍历。这个过程相当于构建了K*L个哈希函数(注意是“相当”，不要做“等价”理解)。
多表哈希中哈希函数数目K和哈希表数目L如何选取：哈希函数数目K过小，会导致每一个哈希桶中容纳了太多的数据点，从而增加了查询响应的时间；而当K过大时，会使得落入每个哈希桶中的数据点变小，而为了增加召回率，我们需要增加L以便构建更多的哈希表，但是哈希表数目的增加会导致更多的内存消耗，并且也使得我们需要计算更多的哈希函数，同样会增加查询相应时间。这听起来非常的不妙，但是在K过大或过小之间仍然可以找到一个比较合理的折中位置。通过选取合理的K和L，我们可以获得比线性扫描极大的性能提升。
Multiprobe：对于构建的L个哈希表，我们在每一个哈希表中找到查询样本落入的哈希桶，然后再在这个哈希桶中做遍历，而Multiprobe指的是我们不止在查询样本所在的哈希桶中遍历，还会找到其他的一些哈希桶，然后这些找到的T个哈希桶中进行遍历。这些其他哈希桶的选取准则是：跟查询样本所在的哈希桶邻近的哈希桶，“邻近”指的是汉明距离度量下的邻近。主要是为了提高查找准确率而引入的一种策略。通常，如果不使用Multiprobe，我们需要的哈希表数目L在100到1000之间，在处理大数据集的时候，其空间的消耗会非常的高，幸运地是，因为有了上面的Multiprobe的策略，LSH在任意一个哈希表中查找到最近邻的概率变得更高，从而使得我们能到减少哈希表的构建数目。
综上，对于LSH，涉及到的主要的参数有三个：
K，每一个哈希表的哈希函数（空间划分）数目
L，哈希表（每一个哈希表有K个哈希函数）的数目
T，近邻哈希桶的数目，即the number of probes
这三个设置参数可以按照如下顺序进行：首先，根据可使用的内存大小选取L，然后在K和T之间做出折中：哈希函数数目K越大，相应地，近邻哈希桶的数目的数目T也应该设置得比较大，反之K越小，L也可以相应的减小。获取K和L最优值的方式可以按照如下方式进行：对于每个固定的K，如果在查询样本集上获得了我们想要的精度，则此时T的值即为合理的值。在对T进行调参的时候，我们不需要重新构建哈希表，甚至我们还可以采用二分搜索的方式来加快T参数的选取过程。
3.1 矢量量化方法
其具体定义为：将一个向量空间中的点用其中的一个有限子集来进行编码的过程。在矢量量化编码中，关键是码本的建立和码字搜索算法。比如常见的聚类算法，就是一种矢量量化方法。
PQ乘积量化：
生成码本和量化
1）特征维度为128维，分为4个子段，4个子空间，每个子空间32维；
2）各个子段（子空间），用更少的特征，进行聚类。每一个子空间都能得到一个码本。则每个样本的每个子段，可以映射到一个ID，这个ID对应的是（子空间的聚类中心）。则 训练样本仅使用的很短的一个编码得以表示，从而达到量化的目的。对于待编码的样本，将它进行相同的切分，然后在各个子空间里逐一找到距离它们最近的类中心，要遍历的是每个类中心，然后用类中心的id来表示它们，即完成了待编码样本的编码。
3）查询样本与dataset（候选集）中的样本距离的计算。
有两种距离计算方式，一种是对称距离，另外一种是非对称距离。非对称距离的损失小(也就是更接近真实距离)，实际中也经常采用这种距离计算方式。
非对称距离计算
1) 查询向量来到时，按训练样本生成码本的过程，将其同样分成相同的子段，然后在每个子空间中，计算子段到该子空间中所有聚类中心得距离，如图中所示，可以得到4*256个距离，把这些算好的距离称作距离池。
在计算库中某个样本到查询向量的距离时，比如编码为(124, 56, 132, 222)这个样本到查询向量的距离时，我们分别到距离池中取各个子段对应的距离即可，比如编码为124这个子段，在第1个算出的256个距离里面把编号为124的那个距离取出来就可，所有子段对应的距离取出来后，将这些子段的距离求和相加，即得到该样本到查询样本间的非对称距离。所有距离算好后，排序后即得到我们最终想要的结果。
从上面这个过程可以很清楚地看出PQ乘积量化能够加速索引的原理：即将全样本的距离计算，转化为到子空间类中心的距离计算。比如上面所举的例子，原本brute-force search的方式计算距离的次数随样本数目N成线性增长，但是经过PQ编码后，对于耗时的距离计算，只要计算4*256次，几乎可以忽略此时间的消耗。另外，从上图也可以看出，对特征进行编码后，可以用一个相对比较短的编码来表示样本，自然对于内存的消耗要大大小于brute-force search的方式。
在某些特殊的场合，我们总是希望获得精确的距离，而不是近似的距离，并且我们总是喜欢获取向量间的余弦相似度（余弦相似度距离范围在[-1,1]之间，便于设置固定的阈值），针对这种场景，可以针对PQ乘积量化得到的前top@K做一个brute-force search的排序。
3.2 倒排乘积量化
倒排PQ乘积量化(IVFPQ)是PQ乘积量化的更进一步加速版。其加速的本质逃不开最前面强调的是加速原理：brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。在上一小节可以看出，PQ乘积量化计算距离的时候，距离虽然已经预先算好了，但是对于每个样本到查询样本的距离，还是得老老实实挨个去求和相加计算距离。但是，实际上我们感兴趣的是那些跟查询样本相近的样本（小白菜称这样的区域为感兴趣区域），也就是说老老实实挨个相加其实做了很多的无用功，如果能够通过某种手段快速将全局遍历锁定为感兴趣区域，则可以舍去不必要的全局计算以及排序。倒排PQ乘积量化的”倒排“，正是这样一种思想的体现，在具体实施手段上，采用的是通过聚类的方式实现感兴趣区域的快速定位，在倒排PQ乘积量化中，聚类可以说应用得淋漓尽致。
总结下来：
树方法：用一颗或多颗树，把样本划分到小区间。如果数据量大，特征多，则树就深。要从根节点走下去，效率就低。
Hash 方法：将不同样本划分在不同的桶中，桶相同，则为候选相似样本。
PQ方法：距离预先算好，编码长度较短。
参考：https://yongyuan.name/blog/ann-search.html
网友评论