1. Introduction

PQ比二进制编码的距离计算精确程度要高得多；
PQ的原理是将原始向量解耦成若干正交的子空间，然后分别量化每个子空间。
对于一些类型的数据（比如基于直方图的SIFT），解耦的子空间本来就对应了自然的维度分割，表现趋近于最优（？）。
对于其他类型的数据，可以用OPQ的方法可以旋转空间，即PCA。
【编者：具体见https://www.jianshu.com/p/ecf37bbca6c1】
同时，PQ对于子空间的分解，暗含着各个子空间之间相互独立。当各个子空间的数据分布有较强的相关性时，PQ的表现会下降（？）。

针对于此，本文提出累积量化（Additive Quantization, AQ）方案，泛化PQ并进一步提升PQ准确性。

不同于PQ，AQ不再拆分子空间也没有子空间独立假设。所有codewords都和原始向量等长。

image.png

2. Additive quantization

2.1. Additive quantization representation

每个向量在被AQ压缩之后，只存一组id，id的范围是[1,K]，一共是M组。
如上图所示，M=K=4，量化后就是类似[3,2,1,4]这样一组id。
算距离的时候去对应的codebooks中取出codewords，把这写向量加起来用，因此称为累积量化。

2.2. Fast distance and scalar product computations

本节将查询时如何算压缩向量x和未压缩的查询向量q的距离。
【编者注：按照文中的意思，距离度量应为欧氏距离L2】
压缩向量x是从codebooks中取出codewords相加得来的。

下式首先根据欧式距离特征进行拆解：

image.png
其中 $||q||^2$ 在查询时算，剩下两项一项是向量内积，一项是模长。

向量内积：
可以在查询时，首先将q和所有codewords的内积预先算出来，代价为 $O(MKD)$ 。
向量模长：
x向量是一组codewords加起来构造出来的，它的模长也是一组向量加和的模长。可以转换为和的乘积，如下式：

image.png
这样就可以在构建索引时，预先算好codeword之间的两两乘积，共

K^2M^2

项，查询的时候需要

M^2/2

次取用和累加。
【编者注：原文作者还提出了对向量模长也进行量化的方法，但肯定有精度损失，编者觉得意义有限】

2.3. Codebook learning

接下来的问题就是codebooks如何获得，每个向量的编码（本质是一个分配向量）如何做。
这两者是一个互相依赖的关系，需要不断迭代。
需要首先初始化codebooks或者向量编码。作者的做法是初始化向量编码，每个位置[1,k]随机选一个数，然后根据这个分配向量，构建codebooks，构建好之后，再去调整分配向量；依次类推，循环迭代，直到收敛或达到收敛指标为止。
这个过程和一般的K-means算法也是很像的。

本节首先讲在给定分配向量之后，如何确定codebooks。

无论哪个过程，总的优化目标都是原始向量和量化后的向量的距离。
针对于每个维度，我们可以让当前编码后的向量（对应的维度），和原始向量（对应的维度）完全一致，此时代价最小。如下式：

image.png
但是要注意到，有MK个参数，即codeword的个数，却有N个方程，实际上是一个过度限制的方程。
【这组线性方程最终值具体是如何敲定的，编者也没有搞清楚，原文提到(10) deﬁnes n equations over KM variables, which are solved in the least-quadratic sense.】

2.4. Vector encoding

和找codebooks一样，纯粹按照精确的代价函数去找编码，代价太高，难以接受，仍然要想一些近似的办法。
本文给的方法是一个beam search的方法来寻找原始向量x的编码。
共迭代M次。

第一次迭代，在所有的codewords里面找到和x最近的N（超参数）个codeword。
第二次迭代，针对每个codeword，称c，算法从剩下的M-1个codebooks的所有codewords中找和(x-c)最近的N个codewords。在获得的 $N^2$ 个candidate中，选择和x最接近的N个保留下来。
第三次迭代，针对每对codewords，称<c1,c2>算法从剩下的M-2个codebooks的所有codewords中找和(x-c1-c2)最近的N个codewords。在获得的 $N^2$ 个candidate中，选择和x最接近的N个保留下来。
当进行到第M次时，我们就获得了x的N个最好的分配向量，我们选Top1赋予x即可。