Supervised Hashing for Image Retrieval via Image Representation Learning
Supervised Hashing for Image Retrieval via Image Representation Learning
背景
最邻近搜索，是给定一个query，返回空间中距离query最近的点。最直接暴力的方法就是计算查询与特征空间的距离，并按照从小到大的顺序进行排序，返回结果。但是采取这种方法，存储的空间消耗比较大，并且查询时间慢。拿互联网的图片为例，数据规模基本都是上亿级别。如果采取遍历上亿级别的图片，然后返回最小距离的结果，那么用户等的花都谢了。为了解决上述问题，近年来ANN搜索技术发展迅速，对空间和时间的需求也大大降低。其中Hash就是一种代表性的方法。
Hash的目标是相似的特征映射到相近的区域，不相近的特征尽可能映射到远的区域。如下图所示：
在Hash算法中，通常就是将样本表示为一串固定长度的二值编码，使得相似的样本具有相似的二值编码(编码之间的hamming距离小)。最起初的工作，主要工作是在特征空间中随机选择一些超平面对空间进行划分，根据样本在超平面的哪一侧决定每一个bit的值。虽然这种方法能够保证效果，但是有时需要很长的bit才能取到更好的效果。在后来的工作中，为了取得更短的编码长度，人们采用了各种尝试，比如构建不同的目标函数，采用不同的优化方法，使用非线性建模，放松离散的约束等方法。其中基于深度学习的Hash算法，最早是Hinton研究组提出的Semantic Hashing。14年的时候，CNN风生水起。中山大学的潘炎老师和颜水成老师合作在2014AAAI上发表了CNNH(Convolutional Neural Network Hashing)，将基于CNN的深度Hash搬上了舞台。
主要改进
本篇paper主要关注了有监督的Hash算法。一个关键的问题就是基于学习的Hash 算法需要将图片进行encode成有用的feature represention提高hash的性能。但是对于图像提出的Hash方法主要是使用了现有的视觉描述子，例如gist。然而，这种视觉特征描述子提取是一种无监督的形式，不能完全保证图像之间的语义相关性，比如奥巴马在不同场合的图片之间明显有着很强的语义相关，但是视觉特征向量之间的距离可能很大。于是作者提出了一种用于图片检索的有监督的Hash Method。方法主要分为两个阶段。
第一阶段 Learning approximate hash code
给定n个图片\{I_1,I_2,I_3,......I_n\}，首先根据图片之间的差异，构建一个相似度矩阵S，其中矩阵S_{i,j}=1表示相似的图片，S_{i,j}=-1表示不相似的图片，矩阵是n*n的矩阵，并且是对称矩阵。首先定义一个n*q大小的binary的H。矩阵的k^{th}行，H_k\in \{-1,1\}^q。H_k代表了图像I_k的q比特的hash code。将S进行如下分解：
分解以后的q-bit的 就作为label进行下一步的训练。
研究发现的 H_{i.}与 H_{j.}的内积 H_{i.}H_{j.}和 与 H_{j.}的Hamming distance有一一对应的关系。所以我们可以通过最小化重构误差来学习近似的Hash code。
其中 ||.||_F^2是Frobenius norm， H\in\{-1,1\}^{n*q}。H代表了相似性矩阵S的近似的Hash code。因为 H_{i.}H_{j.}\in[-q,q]，所以这里需要除以q和S保持同样的范围 \{-1,1\}。在公式(2)中，很难进行整数优化，所以，需要把约束 H\in\{1,-1\}^{n*q}放松为 H\in[1,-1]^{n*q}。公式(2)就转化为下述的形式：
在公式(3)中，由于 HH^T是非凸的，优化起来仍然困难。所以，这里采用了牛顿法进行求解。算法首先随机选择H中的一个entry进行更新，保持其他的entry固定。在每一次迭代中，只更新一项。假设 H=[H_{.1},H_{.2},H_{.3},......,H_{.n}]，这里 H_{.j}是矩阵H的第j-th列。目标函数(3)可以写成如下的形式：
这里 R=qS-\sum_{c \neq i}H_{.c}H_{.c}^H。因为S是对称的，所以R也是对称的矩阵。通过固定H中其他列，目标函数可以写成如下的形式：
下一步需要更新 H_{ij}到 H_{ij}+d，相应的最优化问题变为如下：
把公式进行Taylor展开如下：
上式中 \mathscr{G}^{'}(H_{ij}),\mathscr{G}^{''}(H_{ij})分别代表 \mathscr{G}在 的一阶导数和二阶导数：
把公式(4)关于d求一阶导：
令上式等于0。可以得到 d=-\frac{\mathscr{G}^{'}(H_{ij})}{\mathscr{G}^{''}(H_{ij})}
所以目标函数的(5)的最优解为公式(6)：
d得出以后，就可以按照 H_{ij} \gets H_{ij}+d进行更新。
如果直接计算 R=qS-\sum_{c\neq i}H_{.c}H_{.c}^T \in R^{n*n}需要 O(n^2)的时间复杂度。为了简化计算，保存矩阵 L=HH^T-qS来加速计算。有了Ｌ之后，可以按照如下的公式计算 \mathscr{G}^{'}(H_{ij})和 \mathscr{G}^{''}(H_{ij}):
L_{i.}是L的第i-th的行。这里只需要计算 (O(n))的时间复杂度。当 一旦更新过后，L的第i行和第j列数据将会发生改变。所以需要根据 H_{ij}\gets H_{ij}+d的值重新计算L：
更新的过程时间复杂度也是 O(n)。整个算法过程如下所示：
循环总共进行n*q次，所以总的时间复杂度为 O(Tqn^2)。
第二阶段 Learning image featrue representation and hash function
把原始的图片和第一步学习到的矩阵H作为网络的输入，通过卷积神经网络来学习Image representation和hash function。作者提出了两种网络结构：CNNH和CNNH+。
CNNH：
CNNH:
网络1，2，3层分别是用了32，64，128个filter。
总结
CNNH与传统的基于手工设计特征的方法的性能取得了显著的提升。但是这个方法学到的图像表示并不能反作用于二值编码的更新，并没有完全发挥出深度学习的潜力，以后的方法有不少的改机，相关内容在后面的博客进一步更新。