Hamming Compatible Quantization for Hashing

1 Introduction

Approximate Nearest Neighbour (ANN) search plays an important role in many applications such as computer vision and information retrieval. In recent years there has been growing interest in hashing techniques for efficient ANN search. The goal of hashing is to map data points into compact binary codes whose Hamming distance approximates the similarity. In hashing, data points are usually represented as short codes, such as 32 or 64 bits, which are cost effective in data storage. What's more, under Hamming distance metric, retrieval speed can be very fast (109 XOR and POPCOUNT operations per second in modern CPU [He et al., 2013]). Such properties make hashing an ideal method to handle the ANN search challenges in big data [Torralba et al., 2008].

Hashing methods typically involve two stages [Kong and L, 2012]: projection and quantization. Firstly, data points are transformed into low dimensional vectors with a linear or non-linear projection. Secondly, each projection dimension is quantized into binary code by a quantizer. Most of works focus on the improvement of the projection stage, with an aim to find good projection functions. Local Sensitive Hashing (LSH) [Andoni and Indyk, 2006] adopts a random Gaussian matrix as projection function. Principle Component Analysis Hashing (PCAH) [Wang et al., 2006] uses the projection matrix learnt by principal component analysis. Iterative Quantization (ITQ) [Gong and Lazebnik, 2011] figures out an orthogonal rotation matrix to refine the initial projection matrix. Weighted Component Hashing (WCH) [Duan et al., 2015] utilizes the dependency within each dimensionality to produce discriminative codes. Other typical projection methods include RBM [Hinton et al., 2006], SH [Weiss et al., 2008], KMH [He et al., 2013] and SSH [Wang et al., 2010].

Compared to projection, the quantization stage in hashing has attracted much less attention. Most existing hashing methods adopt single-bit quantization (SBQ) at the second stage [Kong and L, 2012], see figure 1. Specifically, given a projection dimension Y (i) in projected vector Y ∈ Rq (1 ≤ i ≤ q), b(Y (i) ) is 1 if Y (i) is larger than a threshold θ. Otherwise, b(Y (i) ) is 0. b denotes the quantizer in SBQ. SBQ may incur lots of quantization error [Kong and L, 2012], resulting in poor performance. We argue that quantization is equally important as projection. A good quantization mechanism may significantly improve the performance [Kong et al., 2012]. Unfortunately, relatively little efforts were devoted to better quantization. In this paper, we will perform in-depth analysis regarding the quantization stage and further improve the performance of Hashing techniques.

Recently, researchers have attempted to address the limitation of SBQ by proposing multiple bit quantization (MBQ) methods to reduce the quantization error. Representative MBQ methods include Hierarchical Quantization (HQ) in [Liu et al., 2011] and Double Bit Quantization (DBQ) in [Kong and L, 2012]. As shown in figure 1, HQ divides a projection dimension into four regions and encodes each region by a 2-bit code 01, 00, 10 and 11 respectively. However, the neighborhood structure would be destroyed. For instance, let's consider two elements, one in the first region and the other in the third region. Their Hamming distance equals d(01, 10) = 2, which is larger than the Hamming distance between the first region and the fourth region , as d(01, 11) = 1, which is unreasonable as two closer elements get a larger distance. Thus, Kong et al. proposed DBQ [Kong and L, 2012] to divide the projection dimension into three regions and encode them 01, 00 and 10 respectively. However, DBQ does not maximize the use of code space as two bits can represent four different values, leading to insufficient region division of the space.

In this work, we propose a novel multi-bit quantization method named Hamming Compatible Quantization (HCQ). The proposed method HCQ attempts to maximize the use of code space. In HQ and DBQ, each projection dimension is dealt with independently during quantization, ignoring the neighborhood structure of raw data in Euclidean space. Some data points may be actually far away although the distances in some individual projection dimensions are shorter. Hence, HCQ introduces a distance error function to describe the similarity preservation between Euclidean distance space and Hamming distance space, and maximize the similarity preservation. Moreover, a fast optimization algorithm is proposed to significantly reduce the computation complexity from O(n5 ) to O(n3 ), where n is the training data size. Experiments have shown HCQ significantly outperform HQ and DBQ. The main contributions are threefold:

(1) The proposed multi-bit quantization method with Hamming distance metric is essential for hashing techniques to solve the problem of fast ANN search. To the best of our knowledge, this is the first work to explicitly formulate and address the multi-bit quantization problem by incorporating practically important Hamming distance metric towards effective and efficient hashing techniques.

(2) We formulate the multi-bit quantization as an optimization problem by a minimizing distance error function, which elegantly preserves the capability of similarity metric between Euclidean space and Hamming space by utilizing the neighborhood structure of raw data. Moreover, a fast algorithm is proposed to solve the optimization problem.

(3) Extensive experiments on benchmark datasets have shown that our method significantly improves the performance of state-of-the-art multi-bit quantization methods and further advances the hashing technologies.

2 RelatedWork

Projection Methods. Most of existing hashing algorithms fall into this category and can be divided into two groups: (1) data-independent hashing, such as Locality Sensitive Hashing (LSH) [Andoni and Indyk, 2006] and Shift Invariant Kernel Hashing (SIKH) [Raginsky and Lazebnik, 2009], generates random projections independent of dataset. Dataindependent methods normally generate long binary codes for satisfactory performance. (2) data-dependent hashing, such as Spectral Hashing (SH) [Weiss et al., 2008], Principle Component Analysis Hashing (PCAH) [Wang et al., 2006], Semi-supervised Hashing (SSH) [Wang et al., 2010], Iterative Quantization (ITQ) [Gong and Lazebnik, 2011] and Restricted Boltzmann Machine (RBM) [Hinton et al., 2006], aims to learn the projection functions from training data. In general, data-dependent hashing outperforms dataindependent hashing. In this work, our focus is on the quantization stage, which is a valuable complement to the state-ofthe-art projection methods for hashing.

Quantization Methods. Besides the aforementioned multi-bit quantization methods HQ and DBQ, previous works have studied more sophisticated multi-bit strategies.

Kong et al. proposed a multi-bit quantization method called Manhattan Hashing [Kong et al., 2012] (MH). MH encodes each projection dimension into natural binary code (NBC) and adopts Manhattan distance to measure the similarity. For m-bits binary code, the range of Manhattan distance can be 0 to 2m - 1, which is more wider than the range of Hamming distance(0 to m), thereby yielding high retrieval performance. Moran et al. further improved MH by introducing an affinity matrix with F-measure criterion and proposing Neighborhood Preserving Quantization [Moran et al., 2013a] (NPQ). Likewise, Lee et al. present a QuadraEmbedding [Lee et al., 2012] (QE) quantization methods by adopting a specialized 'quadra' distance.

The above methods have achieved significant performance improvement over SBQ. However, those methods have fixed the bits assignment of each projection dimension, without allowing to vary the bit assignment across dimensions. Towards varying bit assignment, Moran et al. firstly proposed a variable-bit quantization [Moran et al., 2013b] named VBQ to allocate bits for different projection dimensions. Then, Xiong et al. proposed an adaptive quantization [Xiong et al., 2014] (AQ) strategy that assigns varying numbers of bits to different dimensions based on their information content.

However, all these methods need to adopt a special distance instead of the Hamming distance. Thus, retrieval speed would be much slower. Figure 2 compares the computing procedure of different distance. Given two codes A and B, only

2 atomic machine instructions are involved to compute their Hamming distance. However, Quadra distance and Manhattan distance involve 8 and 31 CPU operations respectively. At 64 bits code size, Hamming distance is at least 46 times faster than Manhattan distance and 10 times faster than Quadra distance. Readers are referred to Section 4 for more details on retrieval speed.

To the best of our knowledge, only two multi-bit quantization methods HQ and DBQ retain the Hamming distance. Distinct from HQ and DBQ, our work proposes a more efficient and effective quantization method by incorporating the distance information of the original data points.

3 Hamming Compatible Quantization

Assume a projected vector Y ∈ Rq is given. As our focus is the quantization stage, we don't consider how Y is generated. Given Y (u) (1 ≤ u ≤ q), we aim to figure out a mapping

to quantize Y (u) into binary code b(Y (u) ).

In our method, we set b = 2. That is, each element is quantized into 2 bits. The reason is that the computation complexity of threshold learning will be much heavier when b increases. Moreover, setting b to more than 2 cannot incur noticeable performance improvement. Sometimes it even causes performance drop, which was shown in MH [Kong et al., 2012]. Note that our related works, such as HQ [Liu et al., 2011], DBQ [Kong and L, 2012] and NPQ [Moran et al., 2013a], all assign b to 2.

Let T = {Ti|1 ≤ i ≤ n, Ti ∈ Rq } denote the training samples. The set of the u-th dimension projection of T is expressed as

where si = T (u) i , 1 ≤ i ≤ n. Without loss of generality, si (1 ≤ i ≤ n) are supposed to be in order and then we have s1 ≤ s2 ≤ ... ≤ sn (if not, we rank T by the value of T (u) ).

3.1 Formulation

Our goal is to find m- 1 boundaries c1, c2, ..., cm-1 to divide S into m = 2b = 4 groups, G1 = {s1, ..., sc1 }, G2 = {sc1+1, ..., sc2 }, ..., Gm = {scm-1+1, ..., sn} and assign an index Ii to each group Gi, where 1 ≤ i ≤ m. Then, any element x ∈ Gi will be quantized to Ii, i.e.

Here, Ii is a binary code, and {I1, I2, ..., Im} is a permutation of the integers {0, 1, ..., 2b - 1}. The left and right boundary of group Gi are denoted as GLi and GRi , where GLi =min{j|sj ∈ Gi} and GRi =max{j|sj ∈ Gi}.

Given any si, sj ∈ S, the Euclidean distance between their data points is

where d(.) denotes the Euclidean distance. After quantization, the distance between si and sj will be approximated as

where dh(.) denotes the Hamming distance.

Considering the similarity preservation between Euclidean distance space and Hamming distance space, a good hashing method should hash close data points to close binary codes. When two data points are faraway in Euclidean distance space, their corresponding hashing codes should get a large distance in Hamming space as well [Andoni and Indyk, 2006]. An optimal quantization function b(.) is to minimize the distance error introduced by the Hamming approximation:

Here, λ is a constant scalar factor to balance the ranges of E and H. The value of λ will be discussed in section 4. We call Eqn.6 as the distance error function.

There are two groups of variables in b(.), m-1 boundaries {ci|1 ≤ i ≤ m - 1} and m indices {Ii|1 ≤ i ≤ m}. Solving Eqn.6 consists of two steps: finding m- 1 boundaries {ci} to divide S into m groups, and assigning a binary code Ii to each groups Gi (1 ≤ i ≤ m). For simplicity, we firstly fix the indices {Ii} and then update {ci} to minimize the distance error function subject to the given assignment.

3.2 Optimization

A naive method to update {ci} would be: enumerate all possible values of c1, c2 and c3, and calculate the distance error in Eqn.6. Those values yielding minimum distance error are selected as the solution. However, this brute-force algorithm has a O(n5 ) time complexity including O(n3 ) for enumerating ci and O(n2 ) for calculating the distance error function, which is too heavy to solve a practical problem. The size of training data is usually a few thousands or more. When n = 10000, the order of magnitude of time complexity will increase up to 1020 . In practice, we even could not get the answer for this magnitude after nearly 4 days running on a Intel(R) Core(TM) i5 3470 CPU at 3.20GHz.

To update {ci} efficiently, we propose a very fast algorithm by reducing redundant operations. Let F(i, j) denote the sum of distance error between group Gi and Gj , where

Then, Eqn.6 can be rewritten as:

Optimizing Eqn.6 is equivalent to optimize Eqn.8.

Next, we discuss how to efficiently calculate F(i, j). We expand the square item in Eqn.7,

In Eqn.9, H(x, y) is a constant and H(x, y) = dh(Ii, Ij). Let A and B denote the sum of E2 (x, y) and E(x, y) respectively, where x ∈ Gi and y ∈ Gj . Then Eqn.9 is represented as

where σ denotes the constant term dh(Ii, Ij). In Eqn.10, we can efficiently solve F(i, j) by directly reading the values of A and B. As λ, σ, |Gi| and |Gj| are all constant items, once A and B are given, F(i, j) can be calculated in O(1) time. Then, we define two function

Let l1 = GLi - 1, r1 = GRi , l2 = GLj - 1 and r1 = GRj , and we have

Likewise, factor B can be modified as

By pre-computing J(.) and K(.), the results of A and B can be directly obtained from the look-up tables. F(i, j) can be efficiently calculated in O(1) time. Algorithm 1 shows the pseudo-code.

In our work, since {Ii} is a permutations of {00, 01, 10, 11} and there are only in total 4! = 24 instances, we just assign all permutations of {00, 01, 10, 11} to Ii and solve Eqn.8 for each assignment. The time complexity is O(24(n2 q + 16n3 )) = O(n2 q + n3 ), including O(n2 q) for computing J(.) and K(.), and O(16n3 ) for finding the minimal value. We just enumerate 24 instances. Since q is usually much smaller than n, the time complexity can be considered as O(n3 ). The space complexity is O(n2 ), due to n × n lookup tables J(.) and K(.).

Algorithm 1 The fast algorithm to solve the distance error function in Eqn.8.

Input: The training dataset S and T, index Ii(1 ≤ i ≤ m), factor λ.

Output: The solution c1, c2 and c3.

Initialize the variable of minimal distance error min = ∞. Define B1 = {(i, j, k)|1 ≤ i < j < k ≤ n, n = |s|} and B2 = {(i, j)|1 ≤ i, j ≤ 22 }.

Compute the results of J(i, j) and K(i, j), 0 ≤ i, j ≤ n. for each (c∗1 , c∗2 , c∗3 ) ∈ B1 do

Initialize value ← 0, G1 ← {sk|1 ≤ k ≤ c∗1 }, G2 ← {sk|c∗1 < k ≤ c∗2 }, G3 ← {sk|c∗2 < k ≤ c∗3 } and G4 ← {sk|c∗3 < k ≤ n}.

for each (i, j) ∈ B2 do

value ← value + F.

end for

if value < min then

min ← value.

end if end for

4 Experiment

4.1 Dataset and Evaluation Protocol

Extensive experiments were carried out over three widely used retrieval benchmark datasets, LabelMe22K [Torralba et al., 2008], CIFAR-10 [Krizhevsky, 2009] and NUSWIDE [Chua et al., 2009]. The CIFAR-10 dataset contains 60,000 images of size 32x32 and has been categorized into 10 classes. The LabelMe22K dataset contains 22,019 images. As setup in [Kong and L, 2012], [Kong et al., 2012] and [Moran et al., 2013a], we represent each image with a 512 dimensional gray-scale GIST descriptor [Aude and Torralba, 2001]. The NUS-WIDE dataset contains 269,648 images. We use the 225-D block-wise color feature to represent each image.

We report the ANN search results using Euclidean nearest neighbours as the ground-truth. Thresholding is applied to determine whether a returned database image is true positive or not. Following [Kong and L, 2012; Kong et al., 2012; Moranet al., 2013a; 2013b], a threshold is set as the average distance between each of randomly selected 100 data points and their returned the 50th nearest neighbours. We randomly select 1000 images as queries, and the remaining images as reference database images. We use mean Average Precision (mAP) to evaluate the search accuracy. We repeated the retrieval experiments by 10 times. In addition, we measure the search time on an Intel(R) Core(TM) i5 3470 CPU at 3.20GHz with a single thread.

4.2 Baselines

We choose five representative projection methods, ITQ [Gong and Lazebnik, 2011], SH [Weiss et al., 2008], PCAH [Wang et al., 2006], LSH [Andoni and Indyk, 2006] and SIKH [Raginsky and Lazebnik, 2009], and combine them with different quantization methods for hashing. Note that ITQ, SH and PCAH are data-dependent methods, while LSH and SIKH are data-independent methods.

By leveraging the aforementioned projection methods, we study the ANN search accuracy of our method versus stateof-the-art single/multiple bit quantization schemes:

• SBQ: single bit quantization.
• HQ [Liu et al., 2011]: hierarchical hashing uses k-means clustering to divide each dimension into 4 regions, and encodes the regions as 01, 00, 10, 11 from left to right.
• DBQ [Kong and L, 2012]: double-bit quantization with 01, 00, 10 from left to right.
• HCQ: the proposed Hamming Compatible Quantization.

To the best of our knowledge, only two multi-bit quantization methods HQ and DBQ retaining the Hamming distance were reported and we select both of them as baselines. We compare the search time cost of the proposed quantization method with Hamming distance and other typical quantization algorithms with Non-Hamming distance, i.e., MH [Kong et al., 2012] and NPQ [Moran et al., 2013a] with Manhattan distance, and QE [Lee et al., 2012] with Quadra distance. In our experiments, we also compare with Manhattan Hashing [Kong et al., 2012] which adopts Manhattan distance.

4.3 Impact of parameters

Training Sample n. Table 1 shows the impact of the training sample size n for our HCQ. Learning over a small training set (say 1000) has been sufficient for stable and promising performance. More training instances won't incur noticeable improvements while fewer instances may degrade the performance. In practice, we select 1000 images from the database to learn the quantization boundaries. The overall training stage is very efficient and can be finished in just five minutes.

Parameter λ. Figure 3 shows the effect of scalar constant factor λ in Eq. 6 at code size of 32 bits and 64 bits on LabelMe22K dataset. As one can see, for both 32 bits and 64 bits, there is significantly search performance drop (in mAP) when λ becomes smaller (close to 0) or larger (close to 1). Similar trends have been observed at code size 128 bits and 256 bits. It is observed that the optimal λ increases with the code size, e.g., the best mAP is achieved when λ = 0.6 at 32 bits and λ = 0.7 at 64 bits. This is reasonable since the range of Hamming distance increases with the code size, thereby we should enlarge λ to make sure that the Euclidean distance and the Hamming distance have comparable order of magnitude. In the following experiments, we set λ = 0.6, 0.7, 0.8, 0.9 at code size 32, 64, 128, 256, respectively.

4.4 Performance

Comparison with State-of-the-art. Figure 4, figure 5 and figure 6 list the search accuracy mAP when combining different quantization methods and different projection methods on dataset LabelMe22K, CIFAR-10 and NUS-WIDE respectively. When combining SBQ with different projection methods, we have the original baseline algorithms (i.e., ITQ, SH, PCA, LSH and SIKH). For multi-bit quantization HH, DBQ and HCQ, we use double bits to encode each projected dimension.

For fair comparison, HCQ firstly projects data points into c/2 dimension at code size c, which is also applied to other two multi-bit quantization methods HQ and DBQ. Experiment results show that HCQ significantly outperforms SBQ although only half of projection dimensions are used. This has validated the importance of the quantization stage to promote hashing performance.

As listed in figure 4, figure 5 and figure 6, the proposed HCQ consistently outperforms SBQ for all settings even at code size 32. At small code size, HQ and DBQ perform worse

(d) LabelMe-22K 256-bit

than SBQ in some cases (e.g., HQ+LSH and DBQ+LSH perform worse than SBQ+LSH at 32 bits on LabelMe22K and CIFAR-10), while HCQ outperforms SBQ expect just one point (i.e., HCQ+LSH at 32 bits on LabelMe22K dataset). At code size 32, data points are projected into 16 dimension and lots of information would be lost. But HCQ still outperforms SBQ. This demonstrates the effectiveness of HCQ.

Referring to the listed results, HCQ achieves much better performance than other two multi-bit quantization methods HQ and DBQ. The performance gap becomes larger as the code size increases. At 32 bits, HCQ is about +9% mAP better than HQ and +4% better than DBQ on LabelMe22K with ITQ projection. While, at 256 bits, HCQ is +21% mAP better than HQ and 14% mAP better than DBQ on LabelMe22K with ITQ projection. At 256 bits, HCQ is even +25% mAP better than SBQ on LabelMe22K with ITQ projection(i.e., 64.11% vs 38.46%). Considerable mAP improvements are yielded over CIFAR-10 and NUS-WIDE as well. The performance gain from quantization is significant to promote hashing techniques.

Retrieval Speed. Table 2 lists the search time on LabelMe22K dataset using different metrics including Manhattan distance in MH [Kong et al., 2012] and NPQ [Moran et al., 2013a] and Quadra distance in QE [Lee et al., 2012]. The Hamming distance computation is much faster than others at the same code size. For instance, at 32 bits, Hamming distance is about 40 times faster than Manhanttan distance and 10 times faster than Quadra distance. More importantly, the search speedup increases with the code size. This is consistent with the theoretical analysis in Section 2.

Comparison with Manhattan Hashing. We also compare HCQ with another multi-bit quantization method Manhattan Hashing (MH) which adopts Manhattan distance. Note that Manhattan distance has natural advantages over Hamming distance due to much wider distance range, but Manhattan distance incurs more computation complexity. In our experiments, MH firstly projects data points into c/2 dimension and then quantizes each of them into 2 bits at code size c. As listed in Table 3, HCQ achieves comparable retrieval performance with MH, and even better than MH at code size 128. However, the proposed HCQ is with more than 40 times faster retrieval speed than MH. At code size 128, HCQ even yields slightly better results than MH. The performance advantages have again shown that quantization is crucial for improving hashing techniques.

5 Conclusion

Quantization is crucial for performance, and Hamming distance metric contributes to fast retrieval speed. The proposed Hamming Compatibility Quantization not only benefits the

(b) NUS-WIDE 64-bit

(c) NUS-WIDE 96-bit

(d) NUS-WIDE 128-bit

Figure 6: The results of mAP on NUS-WIDE dataset at code size of 32 bits, 64 bits, 96 bits and 128 bits.

multi-bit quantization but also supports highly efficient Hamming distance metric. HCQ has significantly improved the performance of state-of-the-art hashing methods.

Acknowledgments

This work was supported by the Chinese Natural Science Foundation under Contracts No. 61271311, No. 61390515, No. 61421062 and by the National Hightech R&D Program of China (863 Program) under Grant No. 2015AA016302. Ling-Yu Duan is the correspondence author.