Bilinear random projections for locality-sensitive binary codes
Bilinear random projections for locality-sensitive binary codes
复制标题
DOI：
10.1109/cvpr.2015.7298739
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Saehoon Kim;Seungjin Choi
中科院分区：
文献类型：
--
作者：
Saehoon Kim;Seungjin Choi
局部敏感散列（LSH）是一种流行的与数据无关的近似相似性搜索索引方法，其中随机投影和量化对数据库中的点进行散列，以确保彼此靠近的对象的碰撞概率比相距较远的对象高得多。大多数图像的高维视觉描述符都表现出自然的矩阵结构。当视觉描述符由高维特征向量表示并分配长二进制代码时，随机投影矩阵在空间和时间上都需要昂贵的复杂性。在本文中，我们分析了双线性随机投影方法，其中通过两个较小的随机投影矩阵将特征矩阵转换为二进制代码。我们的理论分析基于扩展 Raginsky 和 Lazebnik 的结果，其中随机傅立叶特征与随机二进制量化器组合以形成局部敏感二进制代码。为此，我们回答以下两个问题：（1）双线性随机投影是否也能产生保留相似性的二进制代码； (2) 与大型线性投影相比，双线性随机投影是否会产生性能增益或损失。关于第一个问题，我们提出了双线性随机投影生成的二进制代码之间的预期汉明距离的上限和下限。针对第二个问题，我们分析了二进制码两位之间协方差的上下界，发现两位之间的相关性很小。 MNIST 和 Flickr45K 数据集上的数值实验证实了我们方法的有效性。
Locality-sensitive hashing (LSH) is a popular data-independent indexing method for approximate similarity search, where random projections followed by quantization hash the points from the database so as to ensure that the probability of collision is much higher for objects that are close to each other than for those that are far apart. Most of high-dimensional visual descriptors for images exhibit a natural matrix structure. When visual descriptors are represented by high-dimensional feature vectors and long binary codes are assigned, a random projection matrix requires expensive complexities in both space and time. In this paper we analyze a bilinear random projection method where feature matrices are transformed to binary codes by two smaller random projection matrices. We base our theoretical analysis on extending Raginsky and Lazebnik's result where random Fourier features are composed with random binary quantizers to form locality sensitive binary codes. To this end, we answer the following two questions: (1) whether a bilinear random projection also yields similarity-preserving binary codes; (2) whether a bilinear random projection yields performance gain or loss, compared to a large linear projection. Regarding the first question, we present upper and lower bounds on the expected Hamming distance between binary codes produced by bilinear random projections. In regards to the second question, we analyze the upper and lower bounds on covariance between two bits of binary codes, showing that the correlation between two bits is small. Numerical experiments on MNIST and Flickr45K datasets confirm the validity of our method.