编者的总结：

1. 本文的精髓就是从理论上推导出来（正态分布下）减少失真唯一取决于维度的转换。失真度有下界，使得各子空间维度的特征值之积尽可能相等，不同子空间之间没有依赖，能使得真实失真度向下界逼近。这两个条件的满足是减少失真度的关键。

编者的思考

1. 子空间的分割只能是等量的维度数么？如果能分割成变长的，数据自适应的，是不是效果会更好一些？

Abstract

本文的优化主要在对向量的分段处理上，之前主要是均分，这不太合理。寻找一个最优的子空间分割（向量分段）可以有效降低量化失真，提高效果。

1 INTRODUCTION

向量量化方法用于KNN搜索，主要是两种手段

1. 构建翻转索引，搜索部分数据；
   • 用K-means或其变形做量化器，搜索时只搜相等的或者相似的码字。
2. 把向量编码成紧凑的码字，遍历搜索数据。

乘积量化虽然是目前最好的方法，但是如果不提前得知向量数据集的知识（信息），效果会大打折扣。也就是说，PQ在更general的数据集上的表现极大地受限于前置知识。

本文把PQ看做一个优化问题，目标是最小化量化失真，手段是找到最优codewords和空间分割。难点在于这两个参数（codewords和空间分割）是互相深度耦合的。

2 QUANTIZATION DISTORTION

2.1 Vector Quantization

量化值codeword称为c，量化值集合称为Codebook，Codebook基数是有限的。
优化的目标函数，即失真，就是均方差MSE

image.png

2.2 Codebook Generation

2.2.1 K-Means

如果对codebook没有额外限制的话，优化目标函数最终就会演变成K-means。

2.2.2 Product Quantization

乘积量化本质上就是如下目标函数。作者提供证明，如下目标函数的最小值，可以分段来求k-means，然后将M段的Centroids进行拼接，最终得到的结果也满足全局的最优。当然，这是在固定分段模式的情况下。

image.png

2.2.3 Iterative Quantization

【暂时没看过这篇文章】

2.3 Distortion as the Objective Function

为什么把失真（MSE）作为目标函数来处理呢？
如下图，失真度越高，mAP（准确率）越低，因此优化失真度可以有效提升效果。
另外，可以看出PQ分段越多时，失真越明显，不分段（纯K-means）失真度最低。

image.png

3 OPTIMIZED PRODUCT QUANTIZATION

本文的目标函数定义如下，考虑两点：

1. 向量数据值如何转换（标准化正交转换矩阵R）
   • 这一点从简单来讲可以是将各个维度重新排列，这样R只包含0和1；
   • 从更深的角度来讲，就是通过R来转换坐标系，构造出方差更大的维度和更均衡的维度组合。只要R是满秩标准化矩阵，就符合限制条件；
   • 实际上，本文构造出来的R，不仅满秩而且正交。R也被作者规定为正交矩阵。

2. 每段码字（centroid）如何确定。

   
   image.png

3.1 A Non-Parametric Solution

非参数化的解决方案分为两步：

1. 固定转换矩阵R，寻找每段的最优centroids；
   • 这个和PQ问题就一致了，直接分段K-means就可以解决。
2. 固定每段最优centroids，重新排列、转换向量各维顺序（调节R）。

   • 此时优化目标函数变为：

     
     image.png

   • 将累加放到范数公式里面去，就有：

     
     image.png
   • 其中X代表D×n的矩阵，每一列都是一个sample vector。F范数就是矩阵中每个元素绝对值的平方相加。然后这个问题就变成了一个正交普鲁克问题，有标准解法，复杂度。
     【正交普鲁克问题介绍：https://blog.csdn.net/itnerd/article/details/104598742】

这个算法就是对这两轮操作反复迭代，终止条件是指定迭代次数。
每次就先找K-means，找完K-means，固定下来centroids，再考虑怎么转换维度是最优的，转换好之后就再做新位置的K-means，反复迭代。

• 参数选择：迭代次数作者推荐100左右，每一次迭代中K-means可以只迭代一次。

• 结果分析：这个算法本质上也是一个locally optimal的算法，结果受初始顺序影响较大。在没有其他基本知识的情况下，下一节的参数化方案可以作为初始化。

  
  image.png

3.2 A Parametric Solution

参数化的解决方案假设数据集是正态分布的，如果真是正态分布的，这个solution将得到最优结果。
而且在正态分布的情况下，作者发现目标函数的下界仅仅取决于转换矩阵R，而和codewords无关。因此就可以直接去优化R而不考虑codewords取什么。

3.2.1 Distortion Bound of Quantization

不分段的量化失真是有界的，这个结论和公式来自于信息论。
其中k是codewords个数，D是维数，是协方差矩阵，||表示行列式。

image.png
实验来看，这个下界还是很紧的。
image.png

3.2.2 Distortion Bound of Product Quantization

乘积量化的下界由作者导出，形式上更复杂一些：
最需要注意的是，此时带有参数R（转换矩阵），在式中体现在^上，其等于。

image.png

3.2.3 Minimizing the Distortion Bound

转换过的协方差矩阵可以如下表示：

image.png

我们可以将这个协方差矩阵分成M×M个子矩阵，代表M段：

image.png

至少根据实验来看，下界还是比较紧的，这样可以考虑优化下界入手，也就是去调整R，目标函数如下：

image.png

接下来，对这个目标函数做一些变换：

• 根据均值不等式，提出指数M，相等条件是协方差矩阵对角线上每个值（行列式）都相等，也就是这M块中，每一块包含若干维度，这若干维度产生若干个特征值（每个维度的方差），而每一块的特征值之积是差不多的。
  

  image.png

• 根据费希尔不等式，有如下式子，相等条件是协方差矩阵非对角线位置全0，也就是说各个分段的子空间之间是基本独立的。只要将协方差矩阵做一次PCA，这个条件就能满足。
  

  image.png

• 由于：

  
  image.png

• 因此在考虑R是一个常量时：

  
  image.png

• 要满足不等式相等，需要满足两个不等式同时相等，总结下，有两个条件：

  1. 子空间是独立的，互不相干的，可以通过对协方差矩阵做PCA来完成。
  2. 各个子空间的差异（方差）是平衡的（方差相等），当我们对协方差矩阵做PCA之后，可以将各维度特征值做一个负载均衡，使得各个段（块）之间的特征值之积相差不大。至于段内各维度的顺序，则不重要，因为都是等价位置。

3.2.4 Algorithm: Eigenvalue Allocation

本文对于特征值的分配，就是我们刚才所说的负载均衡问题，用了一个贪心的算法来解决，不算新颖，但是实验中观测效果已经足够了。
准备M个bucket，每个bucket能装D/M个特征值。将特征值降序排序，每次选择头一个，往目前bucket内特征值之积最小的里投进去。
从实验的表里可以看到，右侧的贪心算法得到的值，和理论下界没差多少。

image.png

3.2.5 参数化方法的总结

推导了这么多公式，我们实质总结一下，这种方法具体应该如何使用：

1. 根据抽样样本，计算D×D的协方差矩阵；
2. 对协方差矩阵做PCA，得到特征值矩阵；
3. 分配特征值，得到分组，实际上就得到了转换矩阵R，此时这个R就不只是旋转的作用，而且将原数据集投影到了新的坐标系；
4. 然后根据转换后的数据集做PQ就可以了。

3.3 Non-Parametric versus Parametric—the Combinatorial Nature

根据特征值分配这一算法，和正交转换矩阵R，都可以揭示出本文讨论的问题有一些组合问题的特性。

• NP+RR：非参数方法+初始随机旋转
• NP+RO：非参数方法+初始乱序
• NP：非参数方法+特征值分配
• P：参数化方法
• E：目标函数（MSE）
• mAP：平均精准度

image.png

4 EXPERIMENTS

实验指标比较单一，主要比较效果。
参数化方法就已经很好了，基于参数化方法做初始值的非参数化方法更好一些，提升不算显著。

image.png