乘积量化（Product Quantization）算法原理

男娘i 2023-09-25 12:38 44阅读 0赞

## 一、简介 ##

乘积量化（PQ）算法是和VLAD算法是由法国INRIA实验室一同提出来的，为的是加快图像的检索速度，所以它是一种检索算法，在矢量量化（Vector Quantization，VQ）的基础上发展而来，虽然PQ不算是新算法，但是这种思想还是挺有用处的。

它原文中是接在VLAD算法后面，假设我们使用VLAD算法获得了1M（1024K）的图像表达向量，向量的维度为D=128，则对于一幅查询图像来说，我们需要计算1M（1024K）个余弦距离，这样实时性就比较差。

所以如何加快这种距离的计算速度就是PQ算法所要完成的任务。当然为了解决这个问题，已经有很多算法被提出了，如KDTree，LSH，ITQ等都是为解决这个问题而提出的，属于KNN或ANN范畴。

## 二、空间切分 ##

首先，PQ先将D维空间切分成M份：即将128维空间切分成M个D/M维的子空间，如下图所示M=8（在原文中，作者由于是在PCA之后进行的PQ检索，所以进行了一个随机旋转，因为PCA之后特征值的顺序是按照从大到小排列的）。

![d0086592966e1822e9963a1e64b80030.png][]

用代码表示就是把向量维度切分：

int ds= d / nsq; for ( int i = 0; i < nsq; i ++ )
    { for ( int j = 0; j < ds; j ++ )
        {
            vs.push_back( vtrain.row( i*ds + j ) );
        }
    } //vtrain的转置是原始128维向量，vs是其中的一个子向量

## 三、量化 ##

这样就可以在每个子空间内都会有1M个短向量，我们为每个子空间单独训练一本码书，图中码书规模为k=256，维度d=D/M=128/8=16，代码只要在上面的外循环中添加k-means聚类即可。

到这里我们就有M=8本子码书，下面我们依次量化每个子空间的数据，量化的过程就是计算每个短向量距离最近的聚类中心，距离就是L2距离。

[PQ(product quantization) 算法\_mydear\_11000的博客-CSDN博客\_pq量化算法][PQ_product quantization_ _mydear_11000_-CSDN_pq]

[实例理解product quantization算法 - 静夜录][product quantization_ -]

[乘积量化（Product Quantization）][Product Quantization]

[faiss(1)：简介 安装 与 原理\_沈子恒的博客-CSDN博客][faiss_1_ _ _ _-CSDN]

[faiss(2)：理解product quantization算法\_沈子恒的博客-CSDN博客\_product quantization][faiss_2_product quantization_-CSDN_product quantization]

[d0086592966e1822e9963a1e64b80030.png]: https://img-blog.csdnimg.cn/img_convert/d0086592966e1822e9963a1e64b80030.png
[PQ_product quantization_ _mydear_11000_-CSDN_pq]: https://blog.csdn.net/mydear_11000/article/details/83749059
[product quantization_ -]: http://www.fabwrite.com/productquantization
[Product Quantization]: https://www.jianshu.com/p/cf9f8dcc3c4d/
[faiss_1_ _ _ _-CSDN]: https://blog.csdn.net/shenziheng1/article/details/102881115
[faiss_2_product quantization_-CSDN_product quantization]: https://blog.csdn.net/shenziheng1/article/details/102881474