# AVBH: Asymmetric Learning to Hash with Variable Bit Encoding

Authors: Yanduo Ren; Jiangbo Qian; Yihong Dong; Yu Xin; Huahui Chen
Journal: Scientific Programming
 (2020)

---

## Abstract

Nearest neighbour search (NNS) is the core of large data retrieval. Learning to hash is an effective way to solve the problems by representing high-dimensional data into a compact binary code. However, existing learning to hash methods needs long bit encoding to ensure the accuracy of query, and long bit encoding brings large cost of storage, which severely restricts the long bit encoding in the application of big data. An asymmetric learning to hash with variable bit encoding algorithm (AVBH) is proposed to solve the problem. The AVBH hash algorithm uses two types of hash mapping functions to encode the dataset and the query set into different length bits. For datasets, the hash code frequencies of datasets after random Fourier feature encoding are statistically analysed. The hash code with high frequency is compressed into a longer coding representation, and the hash code with low frequency is compressed into a shorter coding representation. The query point is quantized to a long bit hash code and compared with the same length cascade concatenated data point. Experiments on public datasets show that the proposed algorithm effectively reduces the cost of storage and improves the accuracy of query.


---

## Body

## 1. Introduction

Given a query object/pointq and a dataset S, the nearest neighbour search (NNS) [1–3] is to return the nearest neighbours in S to q. Nowadays, the NNS is widely used in many applications such as image retrieval, text classification, and recommendation systems. However, with the exponential growth of data scale and the disaster of the high data dimensionality, the NNS problem is now much more difficult to solve than before. Therefore, new efficient index structures and query algorithms for similarity searches have increasingly become the focus of research for the problem.The hashing-based NNS methods [3–5] have attracted much attention. Generally, the hashing methods can project the original data with locality preserved to a low-dimensional Hamming space, i.e., binary codes [4–6]. The complexity of those methods is always in sublinear time. In addition, the hashing methods only need a simple bit operation to compute the similarity from Hamming encoding, which is very fast. As the high performance in large-scale data retrieval, hashing techniques have gained increasing interests in facilitating cross-view retrieval tasks [7, 8], on-line retrieval tasks [9], and metric learning tasks [10].For large-scale data retrievals, the time and space costs are the two important issues. As we know, the accuracy of existing hash methods is limited by the length of hash encoding and usually requires a longer coding to get better accuracy. However, a long coding will increase the space cost, network communication overhead, and response time.In order to solve this problem, a coding quantization mechanism [11] based on asymmetric hashing algorithm [12] was proposed. Different from the direct hash code comparison, by cascade concatenating the coding of the data point to the same encoding length of the query point, the coding storage cost of the dataset is reduced effectively and the accuracy of the result is ensured. However, this algorithm uses a unified compression method for all data, ignoring the effect of data distribution. Actually, the distribution of large-scale data is generally uneven. Hence, for most hashing algorithms, the frequency of quantization is also different. As we know, longer encoding can preserve most of the original information; however, it will bring high cost and vice versa. A careful trade-off among accuracy, computing overhead, and space-saving needs to be studied. Intuitively, high-density data require longer length encoding to ensure that the original information is preserved as much as possible, while low-density data can use shorter length encoding and still preserve most of the original information. That is the idea behind our algorithm.In this paper, an asymmetric learning to hash with variable bit encoding algorithm (AVBH) is proposed. The AVBH uses two types of hash mapping functions to quantify the dataset and the query set separately to encode the hash codes with different length bits. In particular, the frequency of dataset is calculated by random Fourier encoding, and then the random Fourier coding with high frequency is compressed into a longer hash code representation, and the random Fourier coding with low frequency is compressed into a shorter hash code representation.The main contributions of this paper are as follows: (1) a variable bit encoding mechanism (named AVBH) based on hash code frequency compression is proposed, which makes the encoding space effectively used, and (2) the experiment shows that the AVBH can effectively reduce the storage cost and improve the query accuracy.


## 2. Preliminaries and Description

In this section, we review some basic knowledge of LSH (locality-sensitive hashing) [13–15], vector quantization [16], and product quantization [17] that is essential to our proposed technique.


### 2.1. Vector Quantization

Vector quantization (VQ) is a classical data compression technique, which compresses the original data into discrete vectors. For a vectorx of n dimensions, formally, a VQ function f can specified as fx∈C=ci,i=1,2,…,k, where x (with n dimensions) is an original data/vector, C is a pretrained code set, and ci is a codeword in the codebook C. The objective of a VQ function is to quantify the original real number vector to the nearest codeword with the lowest VQ loss. Here, the VQ loss of vector x is given by(1)Evqx=minc∈Cx−c2.


### 2.2. Product Quantization

Product quantization (PQ) is an optimization of vector quantization. Firstly, the feature space is divided intom mutually exclusive subspaces, and each subspace is then quantized separately using VQ. That is, the coding of each subspace forms a small codebook C1,C2,…,Cm, and small codebooks form a large codebook C by the Cartesian product. In this method, a high-dimensional data can be decomposed into m low-dimensional spaces and can be processed in parallel. Suppose an object x is represented as a combination of m codewords c1,c2,…,cm, the loss of the product quantization of vector x is given by(2)Epq=minc∈Cx−c2=minc∈Cx−c1Tc2T⋮cmTT2.


### 2.3. Random Fourier Feature

Traditional dimensionality reduction methods, such as PCA, map the data to the independent feature space and compute the main independent features. This method ignores the nonlinear information of the sample distribution and cannot apply to the actual data well. Based on the feature mapping method of random Fourier feature (RFF), data are mapped to the characteristic space under the approximate kernel function, and the inner product of any two points under the feature space is approximated by their kernel function values. Compared with the PCA method, RFF can maximize the data distribution information and obtain the dimensional characteristic by reducing the dimension or raising the dimension. This kind of characteristic is suitable for the characteristic compression processing. SKLSH [18] is a kind of classical hashing algorithm based on RFF, which has a good experimental result under the long bit digit coding.The length coding hash learning algorithm firstly maps the sample points from the originaln dimension real space to the n dimension of the approximate kernel function feature space by RFF. Because of the convergence of RFF consistency, the kernel function similarity between any two sample points can be maintained.Specifically, for two pointsx,y, the translation invariant kernel function [12] Kx,y=EΦw,bx,Φw,by satisfies the following equation:(3)Kx,y=Kx+η,y+η=Kx−y,Kx,y≤Kx−x=K0=1,where Φw,b=2coswTx+b, b satisfies the uniform distribution between 0,2π, w obeys the probability distribution PK induced by the translation invariant kernel function, and η is a constant parameter.Thus, the mapping from then dimensional space to the feature space of the d dimensional approximation kernel function can be obtained by the following equation:(4)Φd⋅=1dΦw1b1⋅,Φw2b2⋅,…,Φwdbd⋅,where w1,w2,…,wd is for the same-sense sampling subject to the probability distribution PK and b1,b2,…,bd obeys the same-distribution sampling which is uniformly distributed between the obedience 0,2π. When the translation invariant kernel function is a Gaussian kernel function, Kx−y=e−y/2x−y2, PK is a Gaussian distribution, i.e., PK∼Normal0,γIn×n.


### 2.4. Orthogonal Procrustes Problem

An orthogonal Procrustes problem is to solve an orthogonal transforming matrixO, so that PO is as close to Q as possible, i.e.,(5)ΓO=minOPO−QF,where OTO=I. This formula is not easy to be solved directly, and it can be optimized by alternating optimization. Namely, the matrix P is first to be fixed, and the matrix Q is optimized to make the target function value reduced. Then the matrix Q is fixed, and the orthogonal transforming matrix O is optimized to make the target function value reduced.


## 2.1. Vector Quantization

Vector quantization (VQ) is a classical data compression technique, which compresses the original data into discrete vectors. For a vectorx of n dimensions, formally, a VQ function f can specified as fx∈C=ci,i=1,2,…,k, where x (with n dimensions) is an original data/vector, C is a pretrained code set, and ci is a codeword in the codebook C. The objective of a VQ function is to quantify the original real number vector to the nearest codeword with the lowest VQ loss. Here, the VQ loss of vector x is given by(1)Evqx=minc∈Cx−c2.


## 2.2. Product Quantization

Product quantization (PQ) is an optimization of vector quantization. Firstly, the feature space is divided intom mutually exclusive subspaces, and each subspace is then quantized separately using VQ. That is, the coding of each subspace forms a small codebook C1,C2,…,Cm, and small codebooks form a large codebook C by the Cartesian product. In this method, a high-dimensional data can be decomposed into m low-dimensional spaces and can be processed in parallel. Suppose an object x is represented as a combination of m codewords c1,c2,…,cm, the loss of the product quantization of vector x is given by(2)Epq=minc∈Cx−c2=minc∈Cx−c1Tc2T⋮cmTT2.


## 2.3. Random Fourier Feature

Traditional dimensionality reduction methods, such as PCA, map the data to the independent feature space and compute the main independent features. This method ignores the nonlinear information of the sample distribution and cannot apply to the actual data well. Based on the feature mapping method of random Fourier feature (RFF), data are mapped to the characteristic space under the approximate kernel function, and the inner product of any two points under the feature space is approximated by their kernel function values. Compared with the PCA method, RFF can maximize the data distribution information and obtain the dimensional characteristic by reducing the dimension or raising the dimension. This kind of characteristic is suitable for the characteristic compression processing. SKLSH [18] is a kind of classical hashing algorithm based on RFF, which has a good experimental result under the long bit digit coding.The length coding hash learning algorithm firstly maps the sample points from the originaln dimension real space to the n dimension of the approximate kernel function feature space by RFF. Because of the convergence of RFF consistency, the kernel function similarity between any two sample points can be maintained.Specifically, for two pointsx,y, the translation invariant kernel function [12] Kx,y=EΦw,bx,Φw,by satisfies the following equation:(3)Kx,y=Kx+η,y+η=Kx−y,Kx,y≤Kx−x=K0=1,where Φw,b=2coswTx+b, b satisfies the uniform distribution between 0,2π, w obeys the probability distribution PK induced by the translation invariant kernel function, and η is a constant parameter.Thus, the mapping from then dimensional space to the feature space of the d dimensional approximation kernel function can be obtained by the following equation:(4)Φd⋅=1dΦw1b1⋅,Φw2b2⋅,…,Φwdbd⋅,where w1,w2,…,wd is for the same-sense sampling subject to the probability distribution PK and b1,b2,…,bd obeys the same-distribution sampling which is uniformly distributed between the obedience 0,2π. When the translation invariant kernel function is a Gaussian kernel function, Kx−y=e−y/2x−y2, PK is a Gaussian distribution, i.e., PK∼Normal0,γIn×n.


## 2.4. Orthogonal Procrustes Problem

An orthogonal Procrustes problem is to solve an orthogonal transforming matrixO, so that PO is as close to Q as possible, i.e.,(5)ΓO=minOPO−QF,where OTO=I. This formula is not easy to be solved directly, and it can be optimized by alternating optimization. Namely, the matrix P is first to be fixed, and the matrix Q is optimized to make the target function value reduced. Then the matrix Q is fixed, and the orthogonal transforming matrix O is optimized to make the target function value reduced.


## 3. Asymmetric Learning to Hash with Variable Bit Encoding

### 3.1. Algorithm Framework

For a general hash learning algorithm, the length of the hash code by learning is always fixed. AVBH uses the idea of asymmetric hashing algorithm, that is, the hash code for the dataset is short and unfixed, and the query point of the code is long and fixed. The steps of the AVBH hashing algorithm are shown in Figure1, which mainly includes the dataset encoding steps ①–③ and the query point encoding step ④.Figure 1
Algorithm framework of AVBH.The dataset encoding section consists of two phases: random Fourier feature encoding (RFF encoding) and variable bit encoding (AVBH encoding). First, step ① uses the random Fourier feature (RFF) to map the dataset and get RFF encoding. After RFF coding, considering the difference of RFF coding frequency, the RFF coding frequency is sorted in step ②. According to the requirement, the original dataset can be divided into the subset by the RFF code as the length ofk1,k2,…,kL shown in the figure. As shown in step ③, the AVBH subset encoding of the length of k1,k2,…,kL can be reproduced by duplicating n/k1,n/k2,…,n/kL times sequentially and then the Hamming code of n dimension is formed.In the query point encoding section, the query point quantization is encoded into RFF encoding of lengthn by step ④.


### 3.2. Objective Function

The target of the AVBH method is to getL groups of hash encoding with the length of k1,k2,…,kL through the hash function Gx, namely,(6)Bl=b11b12⋯b1Nlb21b22⋯b2Nl⋮⋮⋱⋮bkl1bkl2⋯bklNl,bij∈+1,−1,i∈1,2,…,kl,j∈1,2,…,Nl,l∈1,2,…,L,where N=∑l=1LNl, n=∑l=1Lkl.This divides the datasetB1,B2,…,BL into subset according to the RFF encoding frequency. By cascading n/k1,n/k2,…,n/kL times, respectively, we can get L group n bit hash code. For example,(7)B∼l=BlT,BlT,…,BlTT,l∈1,2,…,L.Then combineB∼1,B∼2,…,B∼L to get a n bit long hash code of the entire dataset B∈+1,−1n×N. The AVBH method calculates the similarity by calculating the Hamming distance between the hash code of the query point and the concatenated dataset during the query process. Therefore, for the dataset, we need to construct the hash mapping function, so that the L group hash code obtained with the length of k1,k2,…,kL, respectively, can preserve the original information as much as possible. Therefore, the AVBH method obtains the hash mapping function by the reconstruction error (8) between the minimum cascading encoding B and n dimension sample vector Y:(8)LossB,R=minRB−YF2,where R is an orthogonal rotation n×n matrix, namely, RTR=RRT=I.Combining the properties of associative matrices and the definition ofF-norm of matrices, we can get the following equation:(9)LossB,R=minRB−YF2=mintrRB−YTRB−Y=mintrRBTRB+trYTY−2trRBYT.As the unknown variableB,R in formula (8) is the product relation, the expanded formula (9) contains two items of unknown variables, so it is difficult to solve. After further simplification, we can get the following formula:(10)LossB,R=minRB−YF2=mintrRBTRB+trYTY−2trRBYT=mintrBTRTRB+trYTY−2trRBYT=mintrBTB+trYTY−2trRBYT.AsB∈+1,−1n×N, it is easy to get trBTB=nN. As RTR=I, we can get that Y is unrelated to B and R. As a result, trYTY=c, where c is unrelated to B. So formula (10) is simplified as follows:(11)LossB,R=minRB−YF2=mintrBTB+trYTY−2trRBYT=mintrBTB+trYTRRTY−2trRBYT=minnN+c−2trBTRTY=mintrBTB+trRTYTRTY−2trBTRTY=mintrB−RTYTB−RTY=minB−RTYF2.Thus, minimizing the reconfiguration error (8) equals minimizing the quantization error (11).The objective function of AVBH to encode the dataset is to minimize the reconstruction error of the concatenated encoding of then bit by finding the orthogonal rotation matrix R. In extreme cases of the dataset which is uniformly distributed, there is no significant difference in the frequency of the hash encoding of the dataset, and the AVBH method then degenerates into the ACH algorithm [16]. Compared with the ACH hashing algorithm, the AVBH hashing algorithm is more adaptable to the real data because it can adapt to the data of various distributions and the generalization ability is stronger.


### 3.3. Optimization Algorithm

The objective function (11) can be optimized by alternating optimization. Namely, the rotation matrix R is first to be fixed, and the encoding matrix B is optimized to make the target function value reduced. Then the encoding matrix B is fixed and the rotation matrix R is optimized to make the target function value reduced. In this way, the value of the target function decreases until it converges. The following is a discussion of how to tune and optimize the value of the target function.(1)
Fix the rotation matrixR, and optimize the encoding matrix B.GivenV=RTY, Vlm is a matrix consisted of m−1×k+1 row to m×k row, l−1×k+1 column to l×k column of V. From formula (11), we can get the following equation:(12)Loss1B=minnN+c−2trBTRTY=minnN+c−2∑l=1LtrB∼lTVl=minnN+c−2∑l=1LtrBlT,BlT,…,BlTVl1Vl2⋮Vln/kl=minnN+c−2∑l=1LtrBlT∑m=1n/klVlm.Asn,N,c are unrelated to B, for a fixed R, the problem of minimizing (12) is equal to the problem of maximizing the following formula:(13)Loss1B=2max∑l=1LtrBlT∑m=1n/klVlm=max∑l=1L∑i=1n/kl∑j=1nlBijl∑m=1n/klVijlm,AsBijl∈+1,−1, optimal analytic solution of formula (13) is given by(14)Bijl=sign∑m=1n/klVijlm,i∈1,2,…,kl,j∈1,2,…,Nl,l∈1,L.(2)
Fix the encoding matrixB, and optimize the rotation matrix R.UnderRTR=RRT=I, the problem of minimizing formula (11) is equal to an Orthogonal Procrustes problem [9]. The optimal solution of such problems with R is as follows:(15)Loss2R=minnN+c−2trBTRTY=minnN+c−2trYBTRT.Hence, the problem of optmizingR to get the minimum value of formula (15) is equal to the problem of maximizing the following formula:(16)Loss2R=maxtrYBTRT.By calculating the SVD ofYBT, we can get the following formula:(17)YBT=UΩCT,where U is a matrix which consists of left singular value vector, C is a matrix which consists of right singular value vector, Ω is a diagonal matrix which consists of corresponding singular value vectors, and the diagonal elements of which is Ωii≥0,i∈1,n.By combining formulas (16) and (17), we can get the following equation:(18)Loss2R=maxtrUΩCTRT=maxtrUΩRCT=maxtrRCTUΩ.GivenA=RCTU, R∼=RC, Aii is the diagonal element of A, and R∼i,Ui, respectively, represent the i−th row of R∼, U. By Cauchy–Schwarz inequalities [11], the following equation is obtained:(19)Aii≤R∼iUi=1,whenR∼i=Ui.So formula (18) can be written as formula (20):(20)Loss2R=maxtrAΩ=max∑i=1nAiiΩii.Combining formula (19), when R∼i=Ui, formula (20) takes the maximum value. For R∼i=Ui, we can get the following formula:(21)R∼i=Ui⟺R∼=U⟺RC=U⟺RCCT=UCT⟺R=UCT,when R=UCT, formula (16) takes the maximum value, and formula (15) takes the minimum value. As a result, we can get the optimal result by formula (21).


### 3.4. Encoding Functions

#### 3.4.1. Dataset Encoding

When the objective function value converges, we can get the mapping functionGy1 of AVBH to the dataset according to formula (14), where y is the random Fourier feature (RFF) obtained by the mapping stage of the sample point x:(22)Gy=g1y,g2y,…,gkLy=sign∑m=1n/klRTlmy,l∈1,L.


#### 3.4.2. Query Point Encoding

The optimal rotation matrixR can be obtained from the training process of dataset coding. For the data q in the query set, the main goal of encoding is to keep as much accurate information as possible, so the query set encoding does not need to be compressed and mapped to the hash code of the length bit. Combining formula (14), we can get the mapping function of AVBH to the query set:(23)Fq=f1q,f2q,…,fnq=signRTq.


### 3.5. Convergence Analysis of AVBH

According to the objective function (8), we can get the following formula:(24)LossB,R=minB−RTYF2=minB−D−RTY−DF2≤minB−DF2+RTY−DF2=minB−DF2+minD−RTYF2=L1B+L2R,where D is a n×N constant matrix and satisfies the following two conditions: (1) signs of each element, i.e., positive or negative, in D are the same as that in RTY, and (2) each element in D is not greater than the corresponding position element in RTY.Therefore, the optimization goal forLossB,R is transformed into the two suboptimization problems, i.e., Loss1B and Loss2R. Specifically, for the subproblem Loss1B, formula (14) gives the optimal solution. Therefore, it can be guaranteed that the updated value of formula (14) is less than or equal to the value obtained before. For the subproblem Loss2R, formula (21) gives the optimal solution. Therefore, it also can be guaranteed that the updated value of formula (21) is less than or equal to the value obtained before.Combining the two parts, the combination of (14) and (21) can guarantee that the updated value is less than equal to the value obtained before the update. We can conclude the AVBH algorithm is convergence.


## 3.1. Algorithm Framework

For a general hash learning algorithm, the length of the hash code by learning is always fixed. AVBH uses the idea of asymmetric hashing algorithm, that is, the hash code for the dataset is short and unfixed, and the query point of the code is long and fixed. The steps of the AVBH hashing algorithm are shown in Figure1, which mainly includes the dataset encoding steps ①–③ and the query point encoding step ④.Figure 1
Algorithm framework of AVBH.The dataset encoding section consists of two phases: random Fourier feature encoding (RFF encoding) and variable bit encoding (AVBH encoding). First, step ① uses the random Fourier feature (RFF) to map the dataset and get RFF encoding. After RFF coding, considering the difference of RFF coding frequency, the RFF coding frequency is sorted in step ②. According to the requirement, the original dataset can be divided into the subset by the RFF code as the length ofk1,k2,…,kL shown in the figure. As shown in step ③, the AVBH subset encoding of the length of k1,k2,…,kL can be reproduced by duplicating n/k1,n/k2,…,n/kL times sequentially and then the Hamming code of n dimension is formed.In the query point encoding section, the query point quantization is encoded into RFF encoding of lengthn by step ④.


## 3.2. Objective Function

The target of the AVBH method is to getL groups of hash encoding with the length of k1,k2,…,kL through the hash function Gx, namely,(6)Bl=b11b12⋯b1Nlb21b22⋯b2Nl⋮⋮⋱⋮bkl1bkl2⋯bklNl,bij∈+1,−1,i∈1,2,…,kl,j∈1,2,…,Nl,l∈1,2,…,L,where N=∑l=1LNl, n=∑l=1Lkl.This divides the datasetB1,B2,…,BL into subset according to the RFF encoding frequency. By cascading n/k1,n/k2,…,n/kL times, respectively, we can get L group n bit hash code. For example,(7)B∼l=BlT,BlT,…,BlTT,l∈1,2,…,L.Then combineB∼1,B∼2,…,B∼L to get a n bit long hash code of the entire dataset B∈+1,−1n×N. The AVBH method calculates the similarity by calculating the Hamming distance between the hash code of the query point and the concatenated dataset during the query process. Therefore, for the dataset, we need to construct the hash mapping function, so that the L group hash code obtained with the length of k1,k2,…,kL, respectively, can preserve the original information as much as possible. Therefore, the AVBH method obtains the hash mapping function by the reconstruction error (8) between the minimum cascading encoding B and n dimension sample vector Y:(8)LossB,R=minRB−YF2,where R is an orthogonal rotation n×n matrix, namely, RTR=RRT=I.Combining the properties of associative matrices and the definition ofF-norm of matrices, we can get the following equation:(9)LossB,R=minRB−YF2=mintrRB−YTRB−Y=mintrRBTRB+trYTY−2trRBYT.As the unknown variableB,R in formula (8) is the product relation, the expanded formula (9) contains two items of unknown variables, so it is difficult to solve. After further simplification, we can get the following formula:(10)LossB,R=minRB−YF2=mintrRBTRB+trYTY−2trRBYT=mintrBTRTRB+trYTY−2trRBYT=mintrBTB+trYTY−2trRBYT.AsB∈+1,−1n×N, it is easy to get trBTB=nN. As RTR=I, we can get that Y is unrelated to B and R. As a result, trYTY=c, where c is unrelated to B. So formula (10) is simplified as follows:(11)LossB,R=minRB−YF2=mintrBTB+trYTY−2trRBYT=mintrBTB+trYTRRTY−2trRBYT=minnN+c−2trBTRTY=mintrBTB+trRTYTRTY−2trBTRTY=mintrB−RTYTB−RTY=minB−RTYF2.Thus, minimizing the reconfiguration error (8) equals minimizing the quantization error (11).The objective function of AVBH to encode the dataset is to minimize the reconstruction error of the concatenated encoding of then bit by finding the orthogonal rotation matrix R. In extreme cases of the dataset which is uniformly distributed, there is no significant difference in the frequency of the hash encoding of the dataset, and the AVBH method then degenerates into the ACH algorithm [16]. Compared with the ACH hashing algorithm, the AVBH hashing algorithm is more adaptable to the real data because it can adapt to the data of various distributions and the generalization ability is stronger.


## 3.3. Optimization Algorithm

The objective function (11) can be optimized by alternating optimization. Namely, the rotation matrix R is first to be fixed, and the encoding matrix B is optimized to make the target function value reduced. Then the encoding matrix B is fixed and the rotation matrix R is optimized to make the target function value reduced. In this way, the value of the target function decreases until it converges. The following is a discussion of how to tune and optimize the value of the target function.(1)
Fix the rotation matrixR, and optimize the encoding matrix B.GivenV=RTY, Vlm is a matrix consisted of m−1×k+1 row to m×k row, l−1×k+1 column to l×k column of V. From formula (11), we can get the following equation:(12)Loss1B=minnN+c−2trBTRTY=minnN+c−2∑l=1LtrB∼lTVl=minnN+c−2∑l=1LtrBlT,BlT,…,BlTVl1Vl2⋮Vln/kl=minnN+c−2∑l=1LtrBlT∑m=1n/klVlm.Asn,N,c are unrelated to B, for a fixed R, the problem of minimizing (12) is equal to the problem of maximizing the following formula:(13)Loss1B=2max∑l=1LtrBlT∑m=1n/klVlm=max∑l=1L∑i=1n/kl∑j=1nlBijl∑m=1n/klVijlm,AsBijl∈+1,−1, optimal analytic solution of formula (13) is given by(14)Bijl=sign∑m=1n/klVijlm,i∈1,2,…,kl,j∈1,2,…,Nl,l∈1,L.(2)
Fix the encoding matrixB, and optimize the rotation matrix R.UnderRTR=RRT=I, the problem of minimizing formula (11) is equal to an Orthogonal Procrustes problem [9]. The optimal solution of such problems with R is as follows:(15)Loss2R=minnN+c−2trBTRTY=minnN+c−2trYBTRT.Hence, the problem of optmizingR to get the minimum value of formula (15) is equal to the problem of maximizing the following formula:(16)Loss2R=maxtrYBTRT.By calculating the SVD ofYBT, we can get the following formula:(17)YBT=UΩCT,where U is a matrix which consists of left singular value vector, C is a matrix which consists of right singular value vector, Ω is a diagonal matrix which consists of corresponding singular value vectors, and the diagonal elements of which is Ωii≥0,i∈1,n.By combining formulas (16) and (17), we can get the following equation:(18)Loss2R=maxtrUΩCTRT=maxtrUΩRCT=maxtrRCTUΩ.GivenA=RCTU, R∼=RC, Aii is the diagonal element of A, and R∼i,Ui, respectively, represent the i−th row of R∼, U. By Cauchy–Schwarz inequalities [11], the following equation is obtained:(19)Aii≤R∼iUi=1,whenR∼i=Ui.So formula (18) can be written as formula (20):(20)Loss2R=maxtrAΩ=max∑i=1nAiiΩii.Combining formula (19), when R∼i=Ui, formula (20) takes the maximum value. For R∼i=Ui, we can get the following formula:(21)R∼i=Ui⟺R∼=U⟺RC=U⟺RCCT=UCT⟺R=UCT,when R=UCT, formula (16) takes the maximum value, and formula (15) takes the minimum value. As a result, we can get the optimal result by formula (21).


## 3.4. Encoding Functions

### 3.4.1. Dataset Encoding

When the objective function value converges, we can get the mapping functionGy1 of AVBH to the dataset according to formula (14), where y is the random Fourier feature (RFF) obtained by the mapping stage of the sample point x:(22)Gy=g1y,g2y,…,gkLy=sign∑m=1n/klRTlmy,l∈1,L.


### 3.4.2. Query Point Encoding

The optimal rotation matrixR can be obtained from the training process of dataset coding. For the data q in the query set, the main goal of encoding is to keep as much accurate information as possible, so the query set encoding does not need to be compressed and mapped to the hash code of the length bit. Combining formula (14), we can get the mapping function of AVBH to the query set:(23)Fq=f1q,f2q,…,fnq=signRTq.


## 3.4.1. Dataset Encoding

When the objective function value converges, we can get the mapping functionGy1 of AVBH to the dataset according to formula (14), where y is the random Fourier feature (RFF) obtained by the mapping stage of the sample point x:(22)Gy=g1y,g2y,…,gkLy=sign∑m=1n/klRTlmy,l∈1,L.


## 3.4.2. Query Point Encoding

The optimal rotation matrixR can be obtained from the training process of dataset coding. For the data q in the query set, the main goal of encoding is to keep as much accurate information as possible, so the query set encoding does not need to be compressed and mapped to the hash code of the length bit. Combining formula (14), we can get the mapping function of AVBH to the query set:(23)Fq=f1q,f2q,…,fnq=signRTq.


## 3.5. Convergence Analysis of AVBH

According to the objective function (8), we can get the following formula:(24)LossB,R=minB−RTYF2=minB−D−RTY−DF2≤minB−DF2+RTY−DF2=minB−DF2+minD−RTYF2=L1B+L2R,where D is a n×N constant matrix and satisfies the following two conditions: (1) signs of each element, i.e., positive or negative, in D are the same as that in RTY, and (2) each element in D is not greater than the corresponding position element in RTY.Therefore, the optimization goal forLossB,R is transformed into the two suboptimization problems, i.e., Loss1B and Loss2R. Specifically, for the subproblem Loss1B, formula (14) gives the optimal solution. Therefore, it can be guaranteed that the updated value of formula (14) is less than or equal to the value obtained before. For the subproblem Loss2R, formula (21) gives the optimal solution. Therefore, it also can be guaranteed that the updated value of formula (21) is less than or equal to the value obtained before.Combining the two parts, the combination of (14) and (21) can guarantee that the updated value is less than equal to the value obtained before the update. We can conclude the AVBH algorithm is convergence.


## 4. Experimental Results

The experimental computer has the Intel Core i5-2410M CPU and 8 GB DDR3 memory. We compared the performance of AVBH with that of several typical hashing methods: ACH [12], ITQ [19], KMH [20], PCAH [21], and LSH [13].


### 4.1. Experimental Datasets

#### 4.1.1. CIFAR-101

It is a set of 60,000-32 × 32 colour images in 10 categories with each category containing 6,000 images. In this experiment, 320-D gist features were extracted for each image in the dataset. We randomly selected 1,000 images as the test data and the remaining 59,000 as the training data. In the training data, the closest 50 data points (based on the Euclidean distance) from a test data point were regarded as its nearest neighbours.


#### 4.1.2. SIFT2

It is a local SIFT feature set containing 1,000,000 128-D images. 100,000 of these sample images were randomly selected as the training data and 10,000 of other sample images as the test data.


#### 4.1.3. GIST3

It is a global GIST feature set containing 1,000,000 960-D images. 500,000 of these sample images were randomly selected as the training data and 1,000 sample images as the test data.


### 4.2. Performance Evaluation

The performance of AVBH was evaluated mainly by the relationship between the accuracy of the query (precision) and the recall rate (recall). We define(25)precision=true positive resultstrue positive results+false positive results,recall=true positive resultstrue positive results+false negative results.For the sake of fairness, the average encoding length of AVBH was set to be the encoding length of other methods under a given dataset.Figures2–4 show precision-recall curves for Euclidean neighbour retrieval for several methods on CIFAR-10, SIFT, and GIST with Euclidean neighbour ground truth. Our method, AVBH, can get a better precision performance on the four datasets. As the AVBH algorithm uses the variable bit code, the total code length is less than other algorithms. As a result, our method effectively reduces the cost of storage and improves the accuracy of query.Figure 2
Comparison of the precision-recall experiment of different bits encoding under Cifar10: (a) Cifar10, 16 bit; (b) Cifar10, 32 bit; (c) Cifar10, 64 bit; (d) Cifar10, 128 bit.
(a)
(b)
(c)
(d)Figure 3
Comparison of the precision-recall experiment of different bits encoding under SIFT: (a) SIFT, 16 bit; (b) SIFT, 32 bit; (c) SIFT, 64 bit; (d) SIFT, 128 bit.
(a)
(b)
(c)
(d)Figure 4
Comparison of the precision-recall experiment of different bits encoding under GIST: (a) GIST, 16 bit; (b) GIST, 32 bit; (c) GIST, 64 bit; (d) GIST, 128 bit.
(a)
(b)
(c)
(d)


## 4.1. Experimental Datasets

### 4.1.1. CIFAR-101

It is a set of 60,000-32 × 32 colour images in 10 categories with each category containing 6,000 images. In this experiment, 320-D gist features were extracted for each image in the dataset. We randomly selected 1,000 images as the test data and the remaining 59,000 as the training data. In the training data, the closest 50 data points (based on the Euclidean distance) from a test data point were regarded as its nearest neighbours.


### 4.1.2. SIFT2

It is a local SIFT feature set containing 1,000,000 128-D images. 100,000 of these sample images were randomly selected as the training data and 10,000 of other sample images as the test data.


### 4.1.3. GIST3

It is a global GIST feature set containing 1,000,000 960-D images. 500,000 of these sample images were randomly selected as the training data and 1,000 sample images as the test data.


## 4.1.1. CIFAR-101

It is a set of 60,000-32 × 32 colour images in 10 categories with each category containing 6,000 images. In this experiment, 320-D gist features were extracted for each image in the dataset. We randomly selected 1,000 images as the test data and the remaining 59,000 as the training data. In the training data, the closest 50 data points (based on the Euclidean distance) from a test data point were regarded as its nearest neighbours.


## 4.1.2. SIFT2

It is a local SIFT feature set containing 1,000,000 128-D images. 100,000 of these sample images were randomly selected as the training data and 10,000 of other sample images as the test data.


## 4.1.3. GIST3

It is a global GIST feature set containing 1,000,000 960-D images. 500,000 of these sample images were randomly selected as the training data and 1,000 sample images as the test data.


## 4.2. Performance Evaluation

The performance of AVBH was evaluated mainly by the relationship between the accuracy of the query (precision) and the recall rate (recall). We define(25)precision=true positive resultstrue positive results+false positive results,recall=true positive resultstrue positive results+false negative results.For the sake of fairness, the average encoding length of AVBH was set to be the encoding length of other methods under a given dataset.Figures2–4 show precision-recall curves for Euclidean neighbour retrieval for several methods on CIFAR-10, SIFT, and GIST with Euclidean neighbour ground truth. Our method, AVBH, can get a better precision performance on the four datasets. As the AVBH algorithm uses the variable bit code, the total code length is less than other algorithms. As a result, our method effectively reduces the cost of storage and improves the accuracy of query.Figure 2
Comparison of the precision-recall experiment of different bits encoding under Cifar10: (a) Cifar10, 16 bit; (b) Cifar10, 32 bit; (c) Cifar10, 64 bit; (d) Cifar10, 128 bit.
(a)
(b)
(c)
(d)Figure 3
Comparison of the precision-recall experiment of different bits encoding under SIFT: (a) SIFT, 16 bit; (b) SIFT, 32 bit; (c) SIFT, 64 bit; (d) SIFT, 128 bit.
(a)
(b)
(c)
(d)Figure 4
Comparison of the precision-recall experiment of different bits encoding under GIST: (a) GIST, 16 bit; (b) GIST, 32 bit; (c) GIST, 64 bit; (d) GIST, 128 bit.
(a)
(b)
(c)
(d)


## 5. Conclusion

In this paper, an asymmetric learning to hash with variable bit encoding algorithm was proposed. By the frequency statistics of the random Fourier feature encoding for the dataset, we compress high-frequency hash codes into longer encoding representations and low-frequency hash codes into shorter encoding representations. For a query data, we quantize to a long bit hash code and compare with the same length cascade concatenated data point to retrieve the nearest neighbours. This ensures that the original data information can be preserved as much as possible while the data are compressed, which maximizes the balance between coding compression and query performance. Experiments on open datasets show that the proposed algorithm effectively reduces the cost of storage and improves the accuracy of the query. As we use a two-stage algorithm framework for the hash codes generating, the training stage costs a lot of time. In future work, we will work on simplifying the training process.



---

*Source: 2424381-2020-01-21.xml*