6000 IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.27.NO.12,DECEMBER 2018 the kth bit of all points in B is given by: Algorithm 1 The Learning Algorithm for DDSH min [b ]TQ b+[b p Input: b Training set X; s.t.b∈{-1，+1}I (4) Code length c; Supervised information S. where b denotes the kth column of B,and Output: k- -29-∑ Parameter of the deep neural network. Initialization m=1 Initialize neural network parameter mini-batch size M Q=0 and iteration number Tout,Tin Initialize B=bii=1,2,...,n} p晴=-2∑晴es-∑， for iter =1,2,...,Tout do l=1 Randomly sample and set r= Here,bm denotes the mth bit of bi and p denotes the ith Split training set X into X and xr. element of p. Split B into B and Br. Following COSDISH,we can easily solve problem (4) for epoch =1,2,....Tin do by transforming the BQP problem into an equally clustering for k =1,2,...,c do problem [48]. Construct the BOP problem for the kth bit using (4). 2)Learn h(F(x:))With B Fixed:Because the derivative Construct the clustering problem to solve the BQP of the hash function h(x)=sign(F(x:))is 0 everywhere problem for the kth bit. end for except at 0,we cannot use back-propagation(BP)methods to for t 1,2,...,T/M do update the neural network parameters.So we relax sign()as h(x)=tanh(F(x;)inspired by Song et al.[24].Then we Randomly sample M data points from XI to con- struct a mini-batch. optimize the following problem: Calculate h(xj)for each data point x;in the mini- minc)=∑∑Ld,AsS) batch by forward propagation. i∈2 XIEXI Calculate the gradient according to(7). s.t.h(xj)=tanh(F(xj;) (5) Update the parameter by using back propagation. Update b;=sign(h(x))for each data point xj in To learn the CNN parameter we utilize a the mini-batch. back-propagation algorithm.That is,each time we sample a end for mini-batch of data points,and then use BP algorithm based end for on the sampled data. end for We define the output of CNN as zj=F(xj:and aj= tanh(zj).Then we can compute the gradient of aj and zj as follows: ac =>0Lb,:S) More specifically,given any point xX,we use the dai following formula to predict its binary code: ien dai =∑2abi-sb, (6) ba=h(x)=sign(F(x;)) ieΩ where is the deep neural network parameter learned by and DDSH model. ac ac ●(1-a) IV.COMPARISON TO RELATED WORK =∑2(ab-S)b,·1-a》 (7) Existing feature learning based deep hashing methods with iEQ pairwise labels either use relaxation strategy without discrete Then,wecan use chain rule to computebased on coding or do not use the supervised information to directly and号 guide the discrete coding procedure.For example,CNNH [36] We summarize the whole learning algorithm for DDSH in is a two-step method which adopts relaxation strategy to learn Algorithm 1. continuous code in the first stage and performs feature learning in the second stage.The feature learning procedure in CNNH is not directly guided by supervised information.NINH [37], C.Out-of-Sample Extension for Unseen Data Points DHN [41]and DSH [40]adopt relaxation strategy to learn After training our DDSH model,we can adopt the learned continuous code.DPSH [42]and DQN [41]can learn binary deep hashing framework to predict the binary code for any code in the training procedure.However,DSPH and DQN do unseen data point during training. not utilize the supervised information to directly guide the6000 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 27, NO. 12, DECEMBER 2018 the kth bit of all points in B is given by: min bk [bk ] T Qkbk + [bk ] T pk s.t. bk ∈ {−1, +1} || (4) where bk denotes the kth column of B, and Qk ij i=j = −2(cS ij − k−1 m=1 bm i bm j ) Qk ii = 0 pk i = −2 || l=1 B lk (cS li − k−1 m=1 B lmbm i ). Here, bm i denotes the mth bit of bi and pk i denotes the ith element of pk . Following COSDISH, we can easily solve problem (4) by transforming the BQP problem into an equally clustering problem [48]. 2) Learn h(F(x; )) With B Fixed: Because the derivative of the hash function h(x) = sign(F(x; )) is 0 everywhere except at 0, we cannot use back-propagation (BP) methods to update the neural network parameters. So we relax sign(·) as h(x) = tanh(F(x; )) inspired by Song et al. [24]. Then we optimize the following problem: min h L(h) = i∈ x j∈X L(bi, h(x j); Sij) s.t. h(x j) = tanh(F(x j; )) (5) To learn the CNN parameter , we utilize a back-propagation algorithm. That is, each time we sample a mini-batch of data points, and then use BP algorithm based on the sampled data. We define the output of CNN as z j = F(x j; ) and a j = tanh(z j). Then we can compute the gradient of a j and z j as follows: ∂L ∂a j = i∈ ∂ L(bi, a j; Sij) ∂a j = i∈ 2(aT j bi − Sij)bi (6) and ∂L ∂z j = ∂L ∂a j • (1 − a2 j) = i∈ 2(aT j bi − Sij)bi • (1 − a2 j) (7) Then, we can use chain rule to compute ∂L ∂ based on ∂L ∂a j and ∂L ∂z j . We summarize the whole learning algorithm for DDSH in Algorithm 1. C. Out-of-Sample Extension for Unseen Data Points After training our DDSH model, we can adopt the learned deep hashing framework to predict the binary code for any unseen data point during training. Algorithm 1 The Learning Algorithm for DDSH More specifically, given any point xq ∈/ X, we use the following formula to predict its binary code: bq = h(xq ) = sign(F(xq ; )), where is the deep neural network parameter learned by DDSH model. IV. COMPARISON TO RELATED WORK Existing feature learning based deep hashing methods with pairwise labels either use relaxation strategy without discrete coding or do not use the supervised information to directly guide the discrete coding procedure. For example, CNNH [36] is a two-step method which adopts relaxation strategy to learn continuous code in the first stage and performs feature learning in the second stage. The feature learning procedure in CNNH is not directly guided by supervised information. NINH [37], DHN [41] and DSH [40] adopt relaxation strategy to learn continuous code. DPSH [42] and DQN [41] can learn binary code in the training procedure. However, DSPH and DQN do not utilize the supervised information to directly guide the