Iterative Quantization，ITQ

article/2025/6/8 4:23:10

Abstract

针对大规模的图像检索问题，论文提出了一个高效的ITQ算法。该算法先将中心化后的数据映射到超立方体的顶点上，再通过优化过程寻找一个旋转矩阵，使得数据点经过旋转后，与超立方体的顶点数据具有最小的量化误差。ITQ算法涉及到了multi-class spectral clustering（不懂）以及Orthogonal Procrustes problem，且可以通过PCA（无监督）或CCA（监督）的方法事先对数据进行降维。该方法的实验结果优于大部分start-of-the-art方法。

1. Introduction

一个高效的二值编码学习方法应具有以下特点：（1）码长足够短，内存才不会占用过大；（2）应该具有局部敏感性，即原始空间相似的两个数据点在二值空间也应具有较近的汉明距离；（3）学习和查询过程效率也足够高。

在很多哈希方法中，初始的操作都是对数据进行PCA降维。但是每个特征维度所具备的方差是不同的，高方差的特征方向往往具有更多的信息，如果对所有方向都进行相同的编码（亦或要求向量间正交），那么算法有时会具有更差的表现。SSH算法通过放松对hash函数的正交限制得到了不错的表现，而在ITQ算法中并没有显式得对hash函数添加正交限制。算法初始也是进行PCA降维，然后随机初始化一个旋转矩阵，通过最小化量化误差的过程寻找到矩阵矩阵\(R^*\)，从而得到最终的映射函数。

2. Unsupervised Code Learning

接下来对文章用到的符号表示进行声明：

\(X∈R^{n*d}\)，为数据矩阵，并且对其进行中心化预处理0

\(B = sgn(XW)\)，W为映射函数，sgn为符号函数，B表示X经过映射后的数据，在二值超立方体上的映射的数据。

令\(V = XW\)，算法的目标是最小化量化误差\(||sgn(V) - V||\)，并令\(W^*\)表示最优解。假设R为旋转矩阵，因为旋转矩阵只改变方向不改变映射关系，因此\(W = W^* R\)依然为算法的最优解。据此可得到量化损失函数为：
\[ Q(B,R) = |B - VR|_F^{2}-------(1) \]
在实验中，发现对旋转矩阵R进行随机初始化，可以得到不错的效果。接下来，我们利用ITQ算法进行k（通常为50）次迭代，迭代过程分为两个步骤：

固定R，对B进行更新

通过对\(Q(B,R)\)公式的推导，我们得到最小化\(Q(B,R)\)的过程等同于最大化\(tr(BR^TV^T) = \sum_{i=1}^n \sum_{j=1}^cB_{ij}V^*_{ij}\)，其中\(V^* = VR\)。显然，因为B的取值只有-1和1，为使得该式最大，应使得V为正值时对应的B为1，V为负值时对应的B为-1。此外，对原始数据\(X\)的尺度进行改变不会影响到B或R的最优值，因此我们实现对数据进行中心化处理对实验结果没有影响。

固定B，对R进行更新

在此情况下，目标公式（1）就变成了典型的Orthogonal Procrustes problem，该问题的求解过程可以参考wiki百科。在本文中，利用SVD分解，使得\(B^TV = S\Omega S^T\)，再令\(R = SS^T\)，便可求解。

3. Evaluation of Unsupervised Code Learning

数据集

CIFAR：包括64800个数据，11类。
Tiny image dataset：包括580000个数据，分别对应388个Internet search key words。是以二进制文件形式存储的，每个数据文件包括图片本身、与图片相关的元数据（文件名，使用的搜索引擎，排名等）、每个图片的Gist描述符。

评估方案

第一个评估方法使用欧几里得近邻。在该方法中没有用到类标签的信息。对于每一个查询点，将其与其他数据点的距离进行升序排序，对于距离最近的前50个数据点，只要距离小于一个事先设定的阙值，便认为查询的结果是正确的，否则即为错误的查询结果。然后通过计算错误和正确的比例来得到精度和召回率。
第二个评估方法使用类标签。对每个查询点，得到对应top500的图像数据，然后通过计算top500中类标签和查询点相同所占的比例得到精度，再结合数据集中和查询点标签相同的所有数据点的数量得到召回率。

论文比较了PCA-RR、PCA-ITQ等与其他baseline方法在两种评估尺度下的表现：

屏幕快照 2018-10-06 下午10.43.41