# Data Pre-process（DP）
###### tags: `Product Quantizer`
[ToC]
### 动机
进行PQ量化前对特征进行量化的动机还是很容易理解的，主要是原始特征有两个问题会使得量化误差变大
* 特征维度间非独立。特征的维度之中可能是非独立的，这样同样的码数表达的信息就会变少，也就会造成更大的量化误差。
* 特征间非平衡。这个问题更严重，原本特征间的方差是不相等的，举个清晰的例子，假设为了让特征独立对特征进行了PCA变化，这样变换后的特征方差是沿着维度逐渐减小并且变化非常明显，那么根据PQ的原理，他会每$D/m$个chanel作为一个子量化器，进行聚类。这时候问题就很明显来了，每个子量化器的方差可以看作其包含的所有chanel的方差之和。因此前面的量化器每个chanel的方差都很大，后面量化器方差都很小，但是，每一个子量化器的聚类中心数目都一样多，这样就会造成前面子量化器表达能力不足，后面的有余，最终的量化效果差。
### 方法
既然问题出在了特征间非独立和不平衡，那么一些解决方案也就自然的沿着这两条线索进行,一般的，如果要解决非独立的问题，基本上会对特征进行一个PCA降维，各种方法主要解决的问题一般是维度之间非平衡问题。需要注意的是，用PCA会大大加剧维度不平衡问题，那么就一定要使用量化器均衡的策略。
#### 维度动态比特分配

相关论文：
* Transform Coding for Fast Approximate Nearest Neighbor Search in High Dimensions
* Spectral Hashing
为了解决前面的维度方差大，信息量大的问题，就动态的分配每个特征维度分配到的比特数，方差大的维度分配给的量化比特就多，小的就少。
#### 随机正交旋转变换
![image alt](https://imgpile.com/images/N67lIE.png "title" =300x400)
上图中，$xoy$可以看作PCA后的数据分布，$x_{r}oy_{r}$可以看作一组正交基，将原始的数据映射到新的正交基，可以看作对其做了旋转操作，在新的坐标系中，数据在两个轴上的分布均衡，量化误差相应的也会变小。
相关论文：
* Aggregating Local Descriptors into a Compact Image Representation
* Iterative Quantization: A Procrustean Approach to Learning Binary Codes
将PCA后的特征，随机映射到一组随机标准正交基组成的空间中，可以保持原始特征间的相对位置关系（旋转具有保距性），并且由于维度很多，可以在统计意义上实现每个维度的方差均衡。（没找到数学证明随机旋转矩阵可以实现方差均衡），用swav网络提取的object365特征，共取了10万个样本，每个样本2048维度，对原始特征，PCA后的特征以及旋转后的特征各个维度的方差进行比较，结果如下图

可以看到，PCA相对于原始特征，方差（能量）更加集中在少数的维度，三条曲线的平坦区，PCA的线是最低的，在旋转后，每个维度的能量变得非常均匀，同时，由于做的是正交变换，各个维度之间，仍然是独立的。
#### OPQ
随机旋转矩阵只是随机的选择一个正交矩阵进行映射，并不一定能保证数据在每一个维度的方差相等，或者说，没有结合真实的数据分布进行调整最优的旋转矩阵，那么是否可以根据一定的规则，找到最优的旋转矩阵呢？
相关论文：
Optimized Product Quantization
将旋转矩阵的优化放在PQ的训练中，以最小化量化误差为目标，交替优化聚类中心和旋转矩阵。
* 无参数模式：
步骤很简单，
* 初始化。首先初始化一个$R$,可以用随机正交矩阵作为初始化起点。然后初始化聚类中心$\{C^m\}^{M}_{m=1}$以及所有$x$的聚类index $\{i^{m}\}_{m=1}^{M}$，这一个可以通过对数据进行几个iter的聚类得到一个初步结果。
* 循环主体
1.优化codebook。所有数据乘以旋转矩阵，得到旋转后的数据$\hat{x}$.然后对于每一个sub quantizer，用属于每一个聚类中心的所有$\hat{x}$的均值来计算旋转后的聚类中心$\hat{x}^m(j)$,然后再反过来用这些更新的聚类中心算出所有$\hat{x}$的新的映射index.
2.优化旋转矩阵。将旋转矩阵求解看作一个优化问题，使得原始数据（如果前面有PCA步骤，那么则是PCA后的数据）经过旋转矩阵后得到的数据$X$，与$X$经过量化器encode-decode后的数据$Y$之间的误差最小，公式表达为：
$$\substack{min\\R}||RX-Y||_{F}^{2},...X^{\in D*n},Y^{\in D*n},R^{\in D*D}$$
$$s.t. R^{T}R=I$$
其中$||.||_{F}$是个矩阵范数，代表矩阵所有元素的和。这个优化问题有固定的解法，叫做 *Orthogonal Procrustes problem*，对$XY^T$进行奇异值分解，$XY^T=USV^T$,然后$R=VU^T$,详细证明见[正交普鲁克问题](https://blog.csdn.net/itnerd/article/details/104598742)

循环进行上述两个步骤进行一定的Iter数目，使得误差足够小。一般来说，作者给出的经验值是100个iter就够了。相对于直接使用一个随机初矩阵来说，这种结合数据特性进行迭代优化的方法更能贴合数据，求得更优的旋转矩阵。代价就是训练过程会穿插一个SVD分解，不过由于训练对于搜索来说一般不经常发生，所以是可以接受的。

### 补充一个我对SVD物理含义的理解
[从数据降维角度理解SVD](https://hackmd.io/g1t_9vMOTVWs_2bnQeKCEw)