ANN中乘积量化与多维倒排小结

2019/03/12 20:26
阅读数 308

  目前特征向量的比对加速优化能极大缩短比对耗时,改善用户体验。

       优化的途径主要有两种,一是使用指令集(SSE,AVX)加速运算。二是使用ANN替代暴力搜索。

       乘积量化和倒排索引组合是ANN中效果较好且实用的一种。总体框架分为线下训练字典,线上比对搜索两部分,如下图所示:

       相关论文如下:

      1.Hervé Jégou, Douze M , Schmid C . Product Quantization for Nearest Neighbor Search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010.

       2.Babenko A, Lempitsky V. The inverted multi-index[C]// Computer Vision & Pattern Recognition. 2012.

       具体基础知识如向量量化(vector quantization)、乘积量化(product quantization)、倒排(inverted index)等不详细阐述,总结下自己结合论文做实验的一些体会:

       1.向量量化是一种有损压缩。

       2.乘积量化中子空间不一定越多越好,要平衡计算复杂度和量化精度,论文推荐选2.

       3.类心越多,量化失真(distortion)越小,计算成本也会相应增强。类心数目(centroid)是实际中常调整的超参。

       4.乘积量化有个前提假设,两个子空间(subspace)独立。但实际上大多数不是这样,这里引出了OPQ的优化。

       OPQ(Ge T, He K, Ke Q, et al. Optimized Product Quantization[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2013, 36(4):744-755.),

是针对PQ中子空间存在相关性的优化。主要内容是添加旋转矩阵作用于字典(codebook),并依次迭代R和聚类,使得最终的量化损失最小。

      LOPQ(Kalantidis Y , Avrithis Y . Locally Optimized Product Quantization for Approximate Nearest Neighbor Search[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2014.)在OPQ的基础上,加入了每个子空间的各自旋转矩阵。下图展示了不同量化方法下的类心分布。

 

    

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部