Deep Hashing Network for Efficient Similarity Retrieval
Introduce
这是发表在AAAI-2016的一篇paper，下载地址
在本篇论文之前的监督Hash方法，第一步通过手动学习或者机器学习得到特征向量，第二步学习二进制的Hash Code。然而，这种方法存在明显的缺点，首先提取的特征并不一定完善，并且学习的二进制的Hash Code也有量化的误差。所以作者提出了Deep Hashing Network(DHN)。DHN模型主要从以下四个部分对之前的方法进行改进：
- 使用CNN来学习图像的特征。
- 使用CNN的全连接层来生成二进制码。
- 减少交叉熵损失，使原始空间相似的图片在海明空间也相似。
- 减少量化误差提高Hash Code的质量。
在下面详细介绍一下改进过程：
Deep Hashing Network
相似性检索中，给定训练集N个points
{xi}Ni=1
，每一个是一个D维的特征向量，
x∈RD
。每一对特征向量之间有一个相似性的label
sij
，如果
xi
和
xj
相似，
sij=1
；如果
xi
和
xj
不相似，
sij=0
。我们的目标就是学习到非线性的hashing function
f:x↦h∈{−1,1}Kh=f(x)
。
在本篇论文中，作者提出了如下图所示的网络结构，网络的输入是一组
{xi,xj,sij}
三元组。
figure1 显示的图片是AlexNet的修改，原始AlexNet网络结构con1-con5是5个卷积层，fc6-fc8是三个全连接层。对于每一个全连接层l总会学习到一个非线性的mapping。
zli=al(Wlzl−1i+bl)
这里
zli
是原始的数据
xi
在l层的表示，
Wl,bl
分别表示l-th 层网络的权重和偏置，
al
表示激活函数，这里采用了ReLU函数
al(x)=max(0,x)
。由于需要将原始的数据映射为K维的hash code，作者修改了网络的第8层，将AlexNet的fc8的softmax classifier变成了有K个隐节点的fch layer。
hi=zli,l=8
。为了保证fch layer的输出的范围在[-1,1]之间，作者将该层的激活函数修改为
al(x)=tanh(x)
。为了保证fch layer输出的hash code 性能良好，需要保持hash code 和原始的S中相似性一致，并且输出的二进制码量化误差最小。
一对二进制码
hi
和
hj
，海明距离和内积之间有以下的性质
distH(hi,hj)=12(K−⟨hi,hj⟩)
图像的label已知的，通过label可以得到相似性的矩阵
S={sij}
，那么最好的目标就是在相似性矩阵已知的情况下，根据贝叶斯公式可知，后验的概率与先验概率和似然函数的乘积正相关：
logp(H|S)∝logp(S|H)p(H)=∑si,j∈Slogp(sij|hi,hj)p(hi)p(hj)(1)
上式中，
p(S|H)
是似然函数，
p(H)
是先验。对于每一对输入的三元组，给定hash code
hi,hj
和图像相似性label，可以通过计算内积来表示
p(sij|hi,hj)
。
p(sij|hi,hj)={σ(⟨zli,zlj⟩),1−σ(⟨zli,zlj⟩),sij=1sij=0=σ(⟨zli,zlj⟩)sij(1−σ(⟨zli,zlj⟩))1−sij(2)
这里
σ(x)=11+e−x
是sigmod函数，
hi=zli
。分析上述函数，两种图片之间的海明距离
distH(hi,hj)
越小，内积
⟨hi,hj⟩
越大，
p(1|hi,hj)
越大，说明
hi
和
hj
应该分为相似的，同理
p(0|hi,hj)
越大，说明
hi
和
hj
应该分为不相似的。由于
hi∈{−1,1}K
是离散的，不可导，没办法找到梯度，所以要对
hi
进行放松，变为在[-1,1]区间的连续取值。但是这样做带来了两个问题：（1）存在量化误差（2）内积空间的近似误差变大。所以作者提出了如下所示的bimodal Laplacian prior：
p(hi)=12ϵexp(−|||hi|−1||1ϵ)(3)
函数的图像如下图所示：
把公（2）（3）带入到公式（1）可以得到最优化的目标：
minΘC=L+λQ(4)
上式中
λ=1/ϵ
，
Θ
是
{Wl,bl}
集合，L是交叉熵损失，Q是量化损失。
L=∑sij∈S(log(1+exp(⟨zli,zlj⟩))−sij⟨zli,zlj⟩)(5)
Q=∑sij∈S(|||zli−1||1+|||zli−1||1),(6)
公式（6）中的1为全是1的K维的单位向量。由于Q是不可导的，所以需要对Ｑ进行如下替换
|x|≈logcos(x)
,公式（6）变成了如下所示的可导形式，就可以根据梯度计算下降方向，可到最优解。
Q=∑si,j∈S∑k=1K(logcosh(|zlik|−1)+logcosh(|zljk|−1))(7)
最后通过sgn函数对
zl
进行二值化：
sgn(x){1,−1,x>0x<0
Learning Algorithm
作者定义一对图片之间的损失如下所示：
Cij≜Lij+λQij=log(1+exp(⟨zli,zlj⟩))−sij⟨zli,zlk⟩+λ∑k=1K(logcosh(|zlik|−1)+logcosh(|zljk|−1))(8)
单张图片关于网络第l-th层的k-th单元的参数
Wlk
进行求导可以得到损失函数的梯度：
∂Ci∂Wlk=2∑j:sij∈S(∂Lij∂Wlk+λ∂Qij∂Wlk)=2∑j:sij∈S(∂Lij∂z^lik+λ∂Qij∂z^lik)∂z^lik∂Wlk=2δlikzl−1l(9)
这里
z^lik=Wlzl−1i+bl
是第l层在激活函数之前的形式。
δlik≜∑j:sij∈S(∂Lij∂z^lik+λ∂Qij∂z^lik)
是
xi
在经过l层第k个节点与其他point产生的误差的和。
对于输出层的导数计算，可以利用直接的输出结果：
δlik=∑j:sij∈S([δ(⟨zli,zll⟩)−sij]zljk)a˙lz^lik+λ∑j:sij∈Stanh(|zlik|−1)sgn(zlik)a˙lz^lik,(10)
对于其他层的导数计算，直接利用中间的输出结果进行计算：
δl−1ik=(∑k′=1ulWlk′k)a˙l−1z^l−1ik(11)
与标准的BP算法相比，唯一的不同就是最后一层，采用公式(10)进行更新，其他的更新方式相同。
Experiments
作者主要在三个数据集进行测试：
- NUS-WIDE 21个类别，每一个类别有5000个图片，总共195384张图片，每个图片resize 256*256 500维视觉词典
- CIFAR-10 60000张，10个类别，32*32 gist512
- Flickr 25000张图片，38个语义label，256*256 3857维 sift+gist
对于NUS-WIDE和CLFAR-10每类图片选取500张作为训练集，100张作为测试集，Flickr 随机选择1000张作为测试集，4000张作为训练集。和其他方法做出了对比试验，结果如下图所示：
准确率和召回率图4所示：
Conclusion
个人觉得deep hash的主要是利用了深度学习的优点来学习非线性的hash function。首先要定义好目标函数，目标函数的选取有着很重要的意思，必须保证训练的过程能够BP，其次就是松弛以及松弛以后的求导，求导的过程还是需要一定的数学功底的。在膜拜学术的大牛的同时，也希望自己能不断学习，不断进步。
references
Deep Hashing Network for Efficient Similarity Retrieval Han Zhu, Mingsheng Long ,Jianmin Wang and Yue Cao AAAI -2016
