# Product Quantizer（PQ）
###### tags: `Product Quantizer`
[ToC]
PQ量化的基本思想是将原本较长的特征切分成$m$段，每一段各自聚类，形成$k$（一般为256）然后计算每个特征片段距离哪个聚类中心最近，就用该聚类中心的Index来表示特征片段。这样，原来一个$n$维的32位float特征，就变为了$m$个int8。暴力的计算query和所有gallery之间的距离相似度，也变成了建表和查找表操作，这样在占用内存和搜索速度上，都有较大提升。
## 流程
### step1: 特征切分
考虑到所有的聚类思想，若将整个特征看成基本量化单元去做，可以节省最大量内存，但是就对聚类中心数目要求很高，如果聚类中心较少，那么就会产生很大的量化误差，如果聚类中心很多，那么量化效率又很差。同样的，如果把特征的每一个维度都进行聚类，虽然精度可以很大程度保留，但是压缩后的码长没有变化，只是由float32变成了uint8，并且查找表的操作也会很多。效率也不高。
<img src="https://imgpile.com/images/NB45R4.png">
如图，为了平衡精度和效率，通常是将特征平均切分成$m$个片段，每个特征片段$\mu_{i}(x)$的维度为$d^{*}=d/m$，然后对每个片段用一个子量化器$q_{i}$进行量化，将这些量化片段的结果组合起来，表示原来的特征的量化结果
### step2: 特征聚类
对于每一个特征片段$\mu_{i}(x)$，指定$k^{*}$个聚类中心，然后对所有样本的改片段进行聚类,为了不浪费比特数，$k^{*}$一般可选2的整幂，如256，这样原始的特征空间就被表达为一系列子空间的笛卡尔乘积，这个也是"product"这个词的含义，整个量化器的容量可以表示为$(k^{*})^{m}$，用来表示这个量化空间的所有聚类中心，可以称之为PQ量化器的code book $CB$，其形状为$m * k^{*} * d^{*}$。
由于每个子量化器的维度不高，所以训练的时候所需要的特征数目也可以相应减少，通常整个大库都是上亿特征，不可能全都用来聚类，代价太高。faiss作者给出了一些推荐的聚类数据量,下面给出原文吧：
```
As a rule of thumb there is no consistent improvement of the
k-means quantizer beyond 20 iterations and 1000 * k training
points. And these number diminish when k increases (ie. when
training for larger k you can do fewer iterations on fewer
training points). This is why the k-means clustering
function samples vectors by default (see previous question).
As an example, the results you'd see from clustering 6.2B
vectors to 80K centroids would probably be about the same
quality-wise as sampling a random 20.48M subset to 80K
centroids, so it's just saving you work (of course sampling
should be unbiased, see next question).
```
也就是说呢，超过20个iteration和1000倍的聚类中心样本数之后，再增大iter也没什么用了，faiss默认的最大每个中心所需的样本数为256，所以才有了上面的20.48M for 80K
  作者这个统计规律，需要对样本进行无偏采样，作者这边给出了特征采样的建议
* 当所有特征可以装在RAM里面，那么直接对所有特征进行无放回抽样即可
```
rs = np.random.RandomState(123)
idx = rs.choice(nt_sample, size=nt, replace=False)
xt = xt[idx]
```
* 当所有特征并不能都放在RAM里面，或者本身就是一个流数据，那么需要保证遍历所有数据，保证每个数据都能被相等概率采样，这时候就需要对数据进行水塘采样(reservoir sampling)，原理介绍[水塘采样](https://www.cnblogs.com/strugglion/p/6424874.html),伪代码：
```
//stream代表数据流
//reservoir代表返回长度为k的池塘
//从stream中取前k个放入reservoir；
for ( int i = 1; i < k; i++)
reservoir[i] = stream[i];
for (i = k; stream != null; i++) {
p = random(0, i);
if (p < k) reservoir[p] = stream[i];
return reservoir;
```
### step3: 编码与解码
#### 编码
量化器作用就是尽量去掉原始码中的冗余信息，用尽量短的码来表示原始信息。经过前面的聚类操作，对于一个sub-quantizer $q_{i}$，我们得到$k^{*}$ 个聚类中心，那么对于一个gallery特征，我们计算它与这些聚类中心中最近的index，作为该gallery第i个位置的量化编码，最终，每个gallery编码为$m$个uint8整形数(以$k^{*}=256$为例)，整个gallery库会被编码为$n * m$的码库，用于后面的距离查找。
#### 解码
当在某些场景下(如搜到的特征要给后续步骤使用)需要将一个编码后的特征尽量恢复到原来空间，那么可以利用量化后的量化码和codebook操作，假设gallery量化特征的第$i$位的值是$v_{i}$，那么其解码特征$F^{'}$可以用codebook特征的组合得到，如下：
$F^{'} =cat([CB[0][v_{0}],CB[1][v_{1}],...CB[i][v_{i}],...,CB[m][v_{m}]])$
其中，$0<v_{i}<k^{*}$是每个子量化器的codebook索引
### step4: 距离计算
详细见[SDC与ADC](https://hackmd.io/fWvrkx-GSWak5-eyogAAdg)
### step4: 搜索
#### 非穷举搜索-IVFPQ（Inverted File PQ）
上面所描述的量化方法中大都是围绕压缩每个特征所占用的内存来，其中的加速部分来自于替换穷举的float欧式距离计算变为穷举的查找表，但是仍然需要对所有的特征都进行距离计算，事件复杂度上不够高效，因此采用了谷歌的一个倒排索引的技术，详细可见[倒排索引](https://www.zhihu.com/question/23202010)，在这里，做法就是先对特征进行一个粗聚类，将所有特征分为$k^{'}$组，在用query进行搜索时，首先把query和所有粗聚类中心进行比对，找到最匹配的$w$个聚类中心，然后再将这个$w$个聚类中心所对应的特征进行上述的距离计算，找出topk。
一个有意思的点是在进行上述PQ编码过程中，使用的特征不再是原始的特征，而是和每个聚类中心的差值，将这个残差进行PQ量化，作者在文章里面说这样的码能量更低，经过PQ编码取得更优的搜索性能。但是我感觉这个解释太不明显了，没有说明为啥差分的向量经过PQ编码性能更优。后面可以深入探究下。
#### gallery建立Index过程
```
1) quantize y to qc(y)
2) compute the residual r(y) = y − qc(y)
3) quantize r(y) to qp(r(y)), which, for the product
quantizer, amounts to assigning uj(y) to qj(uj(y)),
for j = 1 . . . m.
4) add a new entry to the inverted list corresponding
to qc(y). It contains the vector (or image) identifier and the binary code (the product quantizer’s
indexes).
```
其中，entry表示一个特征的在库里面的标识，其格式为：
identifier就是粗聚类中心的id，8-32位标识有$2^8$到$2^{32}$个聚类中心,code是用残差量化得到的PQ码，每一个sub quantizer需要$log_2k^*$个码，因此总共需要$mlog_2k^*$个bit去index一个特征。
但是我觉得通过分级建表应该不需要这么多，因为很多特征都属于同一个聚类中心，那么完全可以把他们放到一个表里面，然后记住这个表对应的索引就是对应粗聚类中心的索引，没必要把这个索引编码到每一个index里面。
#### 搜索过程
>
1) quantize x to its w nearest neighbors in the codebook qc;
For the sake of presentation, in the two next steps
we simply denote by r(x) the residuals associated
with these w assignments. The two steps are applied to all w assignments.
2) compute the squared distance $d(\mu_j(r(x)), cj,i)^2$
for each subquantizer j and each of its centroids
cj,i;
3) compute the squared distance between r(x) and
all the indexed vectors of the inverted list. Using
the subvector-to-centroid distances computed in
the previous step, this consists in summing up m
looked-up values, see Equation 31;
4) select the K nearest neighbors of x based on
the estimated distances. This is implemented efficiently by maintaining a Maxheap structure of
fixed capacity, that stores the K smallest values
seen so far. After each distance calculation, the
point identifier is added to the structure only if
its distance is below the largest distance in the
Maxheap
## 性能分析
### 搜索正确率
ANN问题旨在用量化距离代替原始距离，不关系最近的两个向量是否属于一类。
其中R@100代表排序前100中，最近邻在里面的比例。
### $m$和$k^{*}$的选择
编码后每个向量的码长为$m*log_{2}k^{*}$,当码长一定时，$m$和$log_{2}^{k}$是反比关系，作者在文中给出了一些实验结果
码长肯定越长，正确率越高，在码长固定的情况下m数目越少，性能越好，但是我们知道，整个量化器的codebook的大小为$k^{*}*d*32$,所以太小的$m$会对应较大的$k^{*}$，导致codebook会变的比较大。在实际用中m=8配合$k^{*}=256$是一个常用的组合
### $k^{'}$和$w$的选择
### 内存占用
内存占用的节省是非常明显的，原来一个1024维的特征需要$1024*32$位才能表示，现在用64位就能表示，压缩比512，很明显
Sign in with Wallet
Connect another wallet