CVPR'16-(NO-IMI)Efficient Indexing of Billion-Scale Datasets of Deep Descriptors

十亿级深度学习向量数据集的高效索引

作者来自俄罗斯Yandex

编者的总结

  1. 核心思路是使用VQ而非PQ避免分段产生各分段之间的互信息损失。
  2. 技术手段是使用VQ中的RVQ做两层独立聚类，在控制聚类中心数量的基础上尽可能降低量化损失。
  3. 在二级残差中引入了一个Scale factor （GNO-IMI），但实际提升有限。
  4. 相比于IVF-RVQ变化不多。

1 Introduction

本文是针对分区量化索引结构IMI提出的改进版本，核心思想是如何更合理地对向量集进行高效聚类，使得聚类后产生的量化向量和原始向量更接近。

之前的算法IMI，是通过分段PQ进行聚类和空间分区，本文作者认为分段是一个不合理的假设，实际的向量表示不会是完全独立的两个子空间。因此IMI在SIFT上（一段数据表示图像一个区域）比在Deep上（DNN输出，无分段含义）表现更好。

因此，本文放弃了分段表示，采用了RVQ（Residual Vector Quantization）的技术进行向量量化，并在查询算法上做出了一些优化。

2 Algorithm

2.1 基本结构

  • RVQ有两个码本S和T，各自包含K个D维（原始维度）的codewords，两两组合也就产生了K^2个聚类中心，即K^2个cell，数据会被划分到这些cell里去；
  • 聚类划分分为两层，首先在第一层进行粗聚类出K个cell（S），然后根据向量到粗聚类中心的距离进行细划分，这些残差向量会细聚类出K个cell（T）

  • 如下图中间，绿色点为粗聚类中心，红色点为细聚类中心，注意到每个细聚类中心和粗聚类中心的偏差是固定的（即图中每个粗聚类中心引出来的4条线，方向和长度固定）


    image.png
  • 向量的最终量化表示为S_i+T_j。

2.2 码本训练

  • 基本结构：和K-means算法的原理类似，码本（聚类中心）的训练是迭代式完成的。即首先初始化一些聚类中心，再将数据集中点分配到最近的聚类中心上，然后根据分配情况（即，量化损失）重新调整聚类中心。

2.2.1 数据点分配

  • 分配过程是在K^2个聚类中心中选择离数据点最近的聚类中心。一种简单的方式是直接进行暴搜，这样复杂度太高。本文作者提出了一些优化方法：（数据点为p，当前探测的聚类中心是S_k, T_l，暂时忽略\alpha）
  1. 只针对最近的r个粗聚类下面的rK个cell进行评估，更远的直接放弃；
  2. 如下图，将距离计算公式展开，共4项：
    1. 第一项是到粗聚类的距离，第一步已经计算好；
    2. 第二项是fine codeword的模长，可以在分配前预先计算，所有数据点共享；
    3. 第三项是数据点与find codeword的内积，需要计算；
    4. 最后一项是course和fine codeword的内积，可以预计算，同第二项。
image.png
  • 因此，对于每个数据点，实际只要计算K次粗聚类，找出前r个最近的，然后计算rK次细聚类。(r+1)K相比于K^2缩小不少。

2.2.2 码本训练

  • 在给定数据点分配情况后，仅需要解析方法就可以得到新一轮的码本。解析目标是最小化所有Cell内的量化损失，粗细码本（S和T）分开训练。
  • 首先训练细码本T，此时粗码本S固定，仍然忽略\alpha
  • 如下图，T中每个Codeword训练独立，涉及该Codeword的量化总损失如下
image.png

  • 最小化此损失是一个二次函数，得到


    image.png

  • 训练粗码本S也是同理。

2.2.3 码本初始化

  • 粗码本S：数据集上直接K-means
  • 细码本T：残差K-means
  • 一般进行10轮迭代，粗cell选择个数r默认为8.

2.3 查询算法

  • 查询和数据点分配的结果类似，复杂度也相同。不同的是，查询最后会在rK个cell里面选出top-L个最近的Cell进行排序，最后对这L个cell里的向量进行精排。
  • 在精排阶段（rerank），仍然没有使用精确距离计算，而是将二级残差做了一次OPQ，通过OPQ的ADC进行精排排序。

2.4 优化：\alpha矩阵与GNO-IMI

  • 如下图，细聚类部分还可以再根据每个粗聚类的情况进行优化，即加入一个Scale factor调整细聚类Codeword的长度。


    image.png

  • 此时，每个聚类中心可以通过下式来进行表示：


    image.png
  • 训练过程中，\alpha矩阵仍然是单独训练，解析式如下：
    image.png

3. Experiments

  1. 下左图展示了两个codebook的互信息MI，IMI索引认为两个分段可以相互独立，但实际相关性很强。【编者：意义模糊，未完全理解】
  2. 下右图展示两个索引的空cell率，由于NO-IMI更自适应的分区方式，其空置率更低。
image.png

  1. 下表展示了三种索引的量化误差，有15%左右提升，但不确定是大是小。


    image.png

  2. 粗排阶段精度，代表空间分区质量，看起来提升不错，但\alpha矩阵的提升较小。

image.png
  1. 全阶段召回，相比IMI提升不少。
image.png
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容