2011TPAMI-（乘积量化KNN算法）Product Qua
标题：近似搜索的乘积量化算法。
乘积量化也是在向量空间数据的KNN搜索中比较特色的一类算法，本篇是开山之作。
编者的总结
- 量化实际上就是找k-means做聚类，乘积量化就是分段找k-means，整体上减少聚类中心，也就是码字的占用的空间大小，使得置于内存成为可能。
- 本文方法中的“乘积”二字，通常指的是平均分段，然而数据集向量中的值的特征不一定均分，相邻两段之间的值如果有关联也会被打破。本文实验中，分段越少，MSE越低，质量越好，也从侧面说明了这一点。在实验中，作者更改了SIFI,GIFT数据的分段模式，构造了向量的顺序，获得了较大的性能提升（尤其在GIFT）上。
编者的思考
- 这个估计距离，无论是SDC还是ADC，都只是近似估计，既不是上界也不是下界，因此无法搜索精确KNN，无法做Range query，也没法做branch-and-bound式的树形剪枝。而最后基于估计距离的KNN，效果也是随缘的。
- 本文假设的是数据随粗量化器的分布是基本均匀的，这实际上依赖于使用了K-means算法，如果均匀性出了问题，性能和效果都可能大打折扣。
- 和AI领域的算法有类似的通病，参数比较难调，实际用起来有些不便。实验中也能看到，效果受参数影响太大。
- inverted file的构建速度和实际占用内存实验没有看到。
1 INTRODUCTION
本文使用欧氏距离，解决高维向量近似KNN问题。
- 在高维空间上，LSH方法已经被启发式方法打败，包括在FLANN选择算法中实现的随机KD-Tree，层次化k-means。
- AKNN算法通常只去比效率和效果，除此之外，很重要的一点其实是空间占用，尤其是内存占用。一些纯内存的算法缺乏实用性。
本文方法的优势有两点：
- 近似距离的值域扩大了不少，提高了精确性；（相对于汉明码距离）
- 可以有预测距离。
2 BACKGROUND: QUANTIZATION, PRODUCT QUANTIZER
这一节主要讲量化和乘积量化的背景知识，是后面算法的基础。
2.1 Vector Quantization
-
向量量化器q是什么？其实就是一个映射/函数，可以把一大组向量（数据集），映射到一小组向量中（codebook，共k个）。对于数据集中每一个向量，都可以映射到codebook中的一个向量。
- 换个方式理解，其实就是将高维空间，分成k个以codebook向量为中心的cell，每个高维向量都将属于其中某一个Cell。
-
这样的量化器，我们随便取几个向量就可以构造一个，因此需要一个评价指标来评价量化器q的优劣。我们希望数据集中原向量和量化值向量的距离尽量近一些，因此用它们的期望做指标，即MSE（均方差）：
-
当然，在进行计算时，就数据集的所有点的MSE取平均即可。
image.png
-
-
在相似性搜索中，我们当然希望近似的量化值和真实向量越接近越好，因此希望找到一个最优的量化器。要想是最优的，理论上已经有人给出了证明，必须要满足两个最优条件：
-
向量x的量化值必须是codebook中所有量化值中和x最近的那一个。
image.png
-
某一个Cell的量化值必须是该Cell内所有向量的重心。
image.png
- 两个条件相互制约，读者应该可以想象得到，可以利用k-means做一个近似最优的量化器。
-
-
作者额外给出了一个量化器q在第i个Voronoi Cell失真度的一个定义：
image.png
-
量化器q在各个Cell的失真度期望，实际上就是MSE(q)
image.png
2.2 Product Quantizers
上面是说对于一个向量的量化器的构造和评价。
- 量化器的缺陷：让我们考虑一个128维向量，用64位的码来做codebook，也就是
。注意，如果分段来看，每一位码（二进制），就要分割两维空间，也就是二分两维空间，可以说效果已经比较低了。但是空间占用上呢，每一个Voronoi Cell都要一个D维向量来做centroid，也就是需要
个浮点数维护空间分割，这个内存里无论如何也放不下，
，连外存也是放不下的。
- 分段设计：为解决这个问题，可以将高维向量，平均等分成m段，在每一段上，单独构造量化器，称为子量化器。子量化器就有子Codebook，子codebook之间的笛卡尔积，就是整个量化器的codebook。
- 不妨设
就是每一段子codebook值的数量，那么整个codebook值的数量就是
。
- 算法的复杂度：就是m次
算法，其中数据维度是
。
- 内存占用：m段，每段
维的，总内存占用为
个浮点数，这样就在可接受范围内了。
image.png
作者提到，高维向量的连续几个维度通常在构造上是相关的，因此最好将它们由同一个子量化器来量化。
- 不妨设
-
这种乘积量化器q，其MSE(q)定义为各分段的均值：
image.png
- 固定了码字长度，即固定k，就要在m和
image.png
- 从图中得到一个经验：8段，每段256个centroid比较合适。
3 SEARCHING WITH QUANTIZATION
3.1 Computing Distances Using Quantized Codes
这里在量化码上进行距离计算有两种方式，就是如下图中两根黑色实线。其中红色实线是真实距离，黑色实线是估计距离。注意这里的估计距离就只是估计，没有任何上下界的性质。不过大抵可以想象得到，第二种比第一种逼近的要强一点，毕竟要真实一些。
image.png
设query为x，数据集中的向量数据点为y。
-
Symmetric distance computation (SDC)：首先计算x归属于k个centroid中的哪个，称为q(x)，然后用q(x)和q(y)的距离用作估计。因为距离公式两个元素都是量化码，因此称为对称的。
image.png
- Asymmetric distance computation (ADC)：直接计算x和k个centroid的距离作为估计距离。x是真实值，centroid是量化码，因此它们的距离称为不对称的。
image.png
注意无论是哪种距离计算公式来进行knn搜索，第一步，都要在每一段（共m段）和。
距离准备好之后，全部存入查找表，之后query和数据集每个点算估量距离，其复杂度只有O(m)，因为每一段查找一次表，大小为n的数据集总复杂度为O(mn)。
image.png
基于表中的信息，我们后文主要就采用ADC作为估量距离计算。
3.2 Analysis of the Distance Error
首先说，本节的分析适用于满足第2节提到的两个最优化条件的所有量化手段，不局限于特定的量化器。
对于一个量化器q，定义了MSDE(q)，就是利用这个量化器，估量距离和真实距离差值平方的期望是多少。
根据下图简单的三角不等式证明，这个期望MSDE(q)是不会超过量化器q的MSE(q)的。
image.png
同样，对于SDC距离，这个上界是2MSE(q)，就要差一些。
不过注意，说到底，这也只是一个期望的上界，是统计学意义上的。
image.png
4 NONEXHAUSTIVE SEARCH
思考一下，即使我们用了刚才的估计距离，但是如果要找KNN，还是要彻底扫一遍数据集，复杂度至少和数据集大小成正比，这在大数据集上是不可能的。为了解决这个问题，作者提出了IVFADC。其基本策略就是粗细粒度结合。
4.1 Coarse Quantizer, Locally Defined Product Quantizer
我们刚才所说的基于K均值分段做量化器，在这里被称之为粗量化器，根据文中来看，在这一部中，可以分成的Voronoi Cell的个数k'（注意在这里更名为k'）在1000-1000000左右，这个个数是偏少的。因此粗量化器可以仅用来首先将数据先分布到各个Voronoi Cell中，然后在query中定位query所在的Cell，仅搜索当前Cell，和周边的个cell。
现在问题就是定位好Cell了，如何在cell中搜索得到KNN呢？
作者在这里定义了残存向量：
image.png
残存向量，实际上就是相对于粗量化器centroid的偏移向量。进一步，细量化器可以对残存量再次做一次量化，分m段。
- 这里其实有一个权衡，一种方法是在每一个Voronoi Cell中都去找一个特定的量化器，这种方法虽然效果好，但是要找k'个细量化器，不仅计算代价大，而且存储起来也很占空间。因此，我们在全体数据集的残存向量上，只找一个通用的细量化器。
4.2 Indexing Structure
索引结构是一个翻转链表。
注意在IVFADC中，k'是粗量化器每段的Centroid数，k*是细量化器（残存向量量化器）每段的Centroid数。由于是翻转链表结构，数据项除了id以外，只需要细量化器的量化码即可。
- key就是粗量化器的量化值，也就是所谓粗量化器的Codebook，key的个数共有k'个。
- value是一个列表，所有在该Voronoi Cell的向量，全部在该列表中有一个entry。
-
这个entry包含向量的原始值（压缩过的），还包含细量化器的量化值。
image.png
-
4.3 Search Algorithm
搜索主要指近似KNN算法。这个搜索算法就不再扫描所有向量数据，只扫描一部分相关数据。这部分相关数据就是将query定位到粗量化器的量化值所指定的Voronoi Cell，然后得到list。对于list中所有entry，都算一次近似距离，这个近似距离的公式如下：
。
其中x是query向量,y是数据库里的向量数据。
当然，r(x)将在搜索之前，提前和所有的细量化器的codebook中所有量化值算距离，这样每次计算距离，就是查表。
基于这个近似距离，去排一个KNN作为近似结果。
5 EVALUATION OF NN SEARCH
一个常用的度量是Recall@R，表示召回R个结果，其中存在1NN的概率是多少。注意这个和精度不太一样，当R=1的时候才表示精度。
5.2 Memory versus Search Accuracy: Trade-Offs
- 下图反映的还是之前的老结论：少分段，每个分段的格子密一些，效果才会更好。另外，ADC比SDC好不少。
【编者注：一般乘积量化的centroid数，即k*，维持在数据集向量数1%左右的数目是工业界比较常用的参数。在这张图里，m=8，k*=1024】
image.png
【编者注：这幅图是编者加上来的，来源于腾讯AI lab的技术分享，技术方案就是IVFPQ，采用的参数，不太清楚聚类中心数说的是k*，还是】
35b3291ded4a07383426fa320c7a13f.jpg
下图固定了细量化器每段的Centroid数k*，因此横轴只需要依次增加段数m，就线性增加了code length。（IVFADC只需要存残存向量量化码）
- 搜索量(w)多一些，效果越好。
- 但是请注意中间两条线，仅增加k'不增加w，会导致实际搜索量降低，效果反而降低一大截。作者也提到，算法效果和参数强相关。
- 乍一看IVFADC似乎还不如ADC，其实原因是ADC要扫描整个量化后的数据集（至少要扫描所有量化码），然后找出近似距离的KNN。而IVFADC首先找到query所在的（粗）量化码，然后找出周边的几个（粗）量化码，然后进一步搜索。效率上要高得多，所以精度差一点可以理解。
-
具体来说，搜索的比例近似于w/k'，那么在搜索比例不变的条件下，k'是越大精确率越高，因为分割就越细。
image.png
-
5.3 Impact of the Component Grouping
-
将有关联的特征数据放在同一段，可以有效提升效果。
image.png
5.4 Comparison with the State of the Art
- 和汉明码相关的方法比较，有明显的优势。
-
其中IVFADC会在一些位置停下来的原因其实是搜索量就没那么大。
image.png
和FLANN的比较，在这个实验里面，IVFADC首先通过刚才的近似搜索方式找到一个returen list（长度为R），然后计算真实距离，返回最近的一个。注意所有向量其实都存在内存里，在这种条件下，速度仍不容乐观，都在秒级别了。
此时的分段数m固定为8，细量化器的centroid个数k*为256，图中所示为w-k'，即选择的centroid数和粗量化器的Centroid数（每段）。
image.png
5.5 Complexity and Speed
-
两个参数k'和w的选择，一般要根据数据集来衡量了。
image.png
