http://www.mqasem.net/vectorquantization/vq.html
VQ, 即Vector Quantization，矢量量化，在多个场景下使用，如图像压缩，声音压缩，语音识别等。
Github: https://github.com/lucidrains/vector-quantize-pytorch
矢量量化方法，即Vector Quantization，其具体定义为：将一个向量空间中的点用其中的一个有限子集来进行编码的过程。
什么是VQ?
作为示例，我们在不失一般性的情况下采用二维情况下的向量。 图 1 显示了空间中的一些向量。 与每个向量簇相关联的是一个代表性代码字。 每个代码字都位于其自己的 Voronoi 区域中。 为了说明，这些区域在图 1 中用假想线分隔。 给定一个输入向量，被选择来表示它的代码字是在同一个 Voronoi 区域中的码字。
相互欧几里德距离最近的点代表为码字
欧几里德距离定义为：
VQ如何在压缩中工作？
Vevtor quantizer由两个操作组成。 第一个是编码器，第二个是解码器。 编码器采用输入向量并输出提供最低失真的码字索引。 在这种情况下，通过评估输入向量与码本中每个码字之间的欧几里得距离，可以找到最低失真。 一旦找到最接近的码字，该码字的索引就会通过通道发送（该通道可以是计算机存储、通信通道等）。 当编码器接收到代码字的索引时，它用相关的代码字替换索引。
在矢量量化编码中，关键是码本的建立和码字搜索算法，如果想对矢量量化有个整体的概览，强烈推荐《Handbook of Image and Video Processing》一书中Fundamentals of Vector Quantization章节。下面对矢量量化中两类典型的方法多阶段矢量量化、乘积量化以及乘积量化的改进做简单介绍。
codebook如何设计？
到目前为止，我们已经讨论了 VQ 的工作方式，但我们还没有讨论如何生成码本。 什么码字最能代表一组给定的输入向量？ 应该选多少？
不幸的是，设计一个最能代表输入向量集的密码本是 NP 难的。 这意味着它需要在空间中穷尽搜索最佳可能的码字，并且随着码字数量的增加，搜索呈指数增长（如果你能在多项式时间内找到最佳解决方案，你的名字将永远载入史册）。 因此，我们求助于次优码本设计方案，第一个想到的是最简单的。 它以 Linde-Buzo-Gray 的名字命名为 LBG，Linde-Buzo-Gray 是这个想法的作者。 该算法类似于k-means算法。
算法如下，
- 确定码字数 N 或码本的大小。
2. 随机选择N个码字，将其作为初始码本。 可以从一组输入向量中随机选择初始码字。
3. 使用欧几里得距离度量将每个码字周围的向量聚类。 这是通过获取每个输入向量并找到它与每个码字之间的欧几里德距离来完成的。 输入向量属于产生最小距离的码字簇。
4. 计算新的码字集。 这是通过获取每个集群的平均值来完成的。 添加每个向量的分量并除以群集中的向量数。
重复2和3直到所有码字不再变化或者变化很小为止。
该算法是迄今为止最受欢迎的，这是由于它的简单性。 虽然它是局部最优的，但速度很慢。 它慢的原因是因为对于每次迭代，确定每个聚类需要将每个输入向量与码本中的所有码字进行比较。
典型的方法:
下面对矢量量化中两类典型的方法多阶段矢量量化、乘积量化以及乘积量化的改进做简单介绍。
1、多阶段矢量量化：
多阶段矢量量化（Multi-Stage Vector Quantization，MSVQ）也称为残差矢量量化（Residual Vector Quantization, RVQ），它是一种思想，即将编码任务分解为一系列级联过程。级联过程可以用下图直观的展示出来：
如上图所示，对于待量化的向量x，经过一级量化器quantizer1后，得到的量化残差为r1 = x – C1b1，其中C1为一级量化器的码本，b1为x经过一级量化器quantizer1后的表示结果，将一级量化误差r1作为二级量化器的输入，后面过程与此类似。通过这种级联量化的量化方式，当构建的量化器为无穷个时，x可以被这无穷个码本精确表示。上图右侧子图比较直观的描绘了x被多个码本逐步近似的过程。
上述 C1、C2、…、Ci、… 这些码本在构建的时候，可以采用KMeans等方式得到各个量化器的码本。以上面构建的4个级联的码本为例，当得到码本C1、C2、C3、C4后，x量化的结果即可用[b1, b2, b3, b4]表示。对于xq查询向量与x距离的计算，在计算xq与 C1、C2、…、Ci、… 之间的内积距离表后，可以通过查表的方式，获取到非对称距离。
这种多阶段级联的矢量量化方式，相比单阶段一次性量化，极大的降低了码本在训练过程中消耗的计算资源。举个例子，4个阶段的MSVQ，每阶段用KMeans只需构建构建256大小的码本，则对空间分割构建的cell数目为256256256256，效率是很高的，但是如果采用单阶段一次性量化构建4294967296大小的码本，这个码本根本没法用KMeans聚出来。此外在计算距离的时候，采用4阶段的MSVQ方式，只需计算4256次距离的计算构成距离表，然后采用查表方式计算距离，而单阶段一次性量化需要计算4294967296次的距离计算。MSVQ的进一步加速版本是倒排MSVQ，将一级码本视为倒排链，从而构建倒排结构，构建MSVQ倒排结构。
我们可以将MSVQ类比成“深度加深”的过程，下面介绍的非常经典的乘积量化方法，可以为“宽度加宽”的过程。
2、乘积量化：
乘积量化(Product Quantization，PQ)是Herve Jegou在2011年提出的一种非常经典实用的矢量量化索引方法，在工业界向量索引中已得到广泛的引用，并作为主要的向量索引方法，在Fasis有非常高效的实现。乘积量化的核心思想是分段（划分子空间）和聚类，或者说具体应用到ANN近似最近邻搜索上，KMeans是PQ乘积量化子空间数目为1的特例。PQ乘积量化生成码本和量化的过程可以用如下图示来说明：
在训练阶段，针对N个训练样本，假设样本维度为128维，我们将其切分为4个子空间，则每一个子空间的维度为32维，然后我们在每一个子空间中，对子向量采用K-Means对其进行聚类(图中示意聚成256类)，这样每一个子空间都能得到一个码本。这样训练样本的每个子段，都可以用子空间的聚类中心来近似，对应的编码即为类中心的ID。如图所示，通过这样一种编码方式，训练样本仅使用的很短的一个编码得以表示，从而达到量化的目的。对于待编码的样本，将它进行相同的切分，然后在各个子空间里逐一找到距离它们最近的类中心，然后用类中心的id来表示它们，即完成了待编码样本的编码。
正如前面所说的，在矢量量化编码中，关键是码本的建立和码字的搜索算法，在上面，我们得到了建立的码本以及量化编码的方式。剩下的重点就是查询样本与dataset中的样本距离如何计算的问题了。
在查询阶段，PQ同样在计算查询样本与dataset中各个样本的距离，只不过这种距离的计算转化为间接近似的方法而获得。PQ乘积量化方法在计算距离的时候，有两种距离计算方式，一种是对称距离，另外一种是非对称距离。非对称距离的损失小(也就是更接近真实距离)，实际中也经常采用这种距离计算方式。下面过程示意的是查询样本来到时，以非对称距离的方式(红框标识出来的部分)计算到dataset样本间的计算示意：
具体地，查询向量来到时，按训练样本生成码本的过程，将其同样分成相同的子段，然后在每个子空间中，计算子段到该子空间中所有聚类中心得距离，如图中所示，可以得到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、倒排乘积量化
倒排PQ乘积量化(IVFPQ)是PQ乘积量化的更进一步加速版。其加速的本质逃不开在最前面强调的是加速原理：brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。在上一小节可以看出，PQ乘积量化计算距离的时候，距离虽然已经预先算好了，但是对于每个样本到查询样本的距离，还是得老老实实挨个去求和相加计算距离。但是，实际上我们感兴趣的是那些跟查询样本相近的样本（姑且称这样的区域为感兴趣区域），也就是说老老实实挨个相加其实做了很多的无用功，如果能够通过某种手段快速将全局遍历锁定为感兴趣区域，则可以舍去不必要的全局计算以及排序。倒排PQ乘积量化的”倒排“，正是这样一种思想的体现，在具体实施手段上，采用的是通过聚类的方式实现感兴趣区域的快速定位，在倒排PQ乘积量化中，聚类可以说应用得淋漓尽致。
倒排PQ乘积量化整个过程如下图所示：
在PQ乘积量化之前，增加了一个粗量化过程。具体地，先对N个训练样本采用KMeans进行聚类，这里聚类的数目一般设置得不应过大，一般设置为1024差不多，这种可以以比较快的速度完成聚类过程。得到了聚类中心后，针对每一个样本x_i，找到其距离最近的类中心c_i后，两者相减得到样本x_i的残差向量(x_i-c_i)，后面剩下的过程，就是针对(x_i-c_i)的PQ乘积量化过程，此过程不再赘述。
在查询的时候，通过相同的粗量化，可以快速定位到查询向量属于哪个c_i（即在哪一个感兴趣区域），然后在该感兴趣区域按上面所述的PQ乘积量化距离计算方式计算距离。
4、最优乘积量化
最优乘积量化（Optimal Product Quantization, OPQ）是PQ的一种改进版本。其改进体现在，致力于在子空间分割时，对各子空间的方差进行均衡。在具体实现的时候，我们可以将Optimal的过程实现为一个组件。
通常，用于检索的原始特征维度较高，所以实际在使用PQ等方法构建索引的时候，常会对高维的特征使用PCA等降维方法对特征先做降维处理，这样降维预处理，可以达到两个目的：一是降低特征维度；二是在对向量进行子段切分的时候要求特征各个维度是不相关的，做完PCA之后，可以一定程度缓解这个问题。但是这么做了后，在切分子段的时候，采用顺序切分子段仍然存在一定的问题，这个问题可以借用ITQ中的一个二维平面的例子加以说明：
如上面a图所示，对于PCA降维后的二维空间，假设在做PQ的时候，将子段数目设置为2段，即切分成x和y两个子向量，然后分别在x和y上做聚类（假设聚类中心设置为2）。对a图和c图聚类的结果进行比较，可以明显的发现，a图在y方向上聚类的效果明显差于c图，而PQ又是采用聚类中心来近似原始向量（这里指降维后的向量），也就是c图是我们需要的结果。这个问题可以转化为数据方差来描述：在做PQ编码时，对于切分的各个子空间，我们应尽可能使得各个子空间的方差比较接近，最理想的情况是各个子空间的方差都相等。上图a图中，x和y各个方向的方差明显是差得比较大的，而对于c图，x和y方向各个方向的方差差不多是比较接近的。
为了在切分子段的时候，使得各个子空间的方差尽可能的一致，Herve Jegou在Aggregating local descriptors into a compact image representation中提出使用一个正交矩阵来对PCA降维后的数据再做一次变换，使得各个子空间的方差尽可能的一致。其对应的待优化目标函数见论文的第5页，由于优化该目标函数极其困难，Herve Jegou使用了Householder矩阵来得到该正交矩阵，但是得到的该正交矩阵并不能很好的均衡子空间的方差。
OPQ致力于解决的问题正是对各个子空间方差的均衡。具体到方法上，OPQ借鉴了ITQ的思想，在聚类的时候对聚类中心寻找对应的最优旋转矩阵，使得所有子空间中各个数据点到对应子空间的类中心的L2损失的求和最小。OPQ在具体求解的时候，分为非参求解方法和带参求解方法，具体为：
- 非参求解方法。跟ITQ的求解过程一样。
- 带参求解方法。带参求解方法假设数据服从高斯分布，在此条件下，最终可以将求解过程简化为数据经过PCA分解后，特征值如何分组的问题。在实际中，该解法更具备高实用性。
从上面可以看到，倒排乘积量化IVFPQ可以视为1阶段的MSVQ和PQ的结合版本，而OPQ是PQ对子空间方差均衡的改进。基于这样一种普适性的视角，可以构建一种矢量量化框架，MSVQ、PQ、OPQ中的O，都是该矢量量化框架中的基础组件，通过这些组件的组合，我们可以敏捷的得到上面介绍方法的各种实现。
