An Ensemble Diversity Approach to Supervised Binary Hashing
Binary hashing is a well-known approach for fast approximate nearest-neighbor search in information retrieval. Much work has focused on affinity-based objective functions involving the hash functions or binary codes. These objective functions encode neighborhood information between data points and are often inspired by manifold learning algorithms. They ensure that the hash functions differ from each other through constraints or penalty terms that encourage codes to be orthogonal or dissimilar across bits, but this couples the binary variables and complicates the already difficult optimization. We propose a much simpler approach: we train each hash function (or bit) independently from each other, but introduce diversity among them using techniques from classifier ensembles. Surprisingly, we find that not only is this faster and trivially parallelizable, but it also improves over the more complex, coupled objective function, and achieves state-of-the-art precision and recall in experiments with image retrieval.
Information retrieval tasks such as searching for a query image or document in a database are essentially a nearest-neighbor search [33]. When the dimensionality of the query and the size of the database is large, approximate search is necessary. We focus on binary hashing [17], where the query and database are mapped onto low-dimensional binary vectors, where the search is performed. This has two speedups: computing Hamming distances (with hardware support) is much faster than computing distances between high-dimensional floating-point vectors; and the entire database becomes much smaller, so it may reside in fast memory rather than disk (for example, a database of 1 billion real vectors of dimension 500 takes 2 TB in floating point but 8 GB as 64-bit codes).
Constructing hash functions that do well in retrieval measures such as precision and recall is usually done by optimizing an affinity-based objective function that relates Hamming distances to supervised neighborhood information in a training set. Many such objective functions have the form of a sum of pairwise terms that indicate whether the training points x n and x m are neighbors:
Here, X = (x 1 , . . . , x N ) is the dataset of high-dimensional feature vectors (e.g., SIFT features of an image), h: R D → {−1, +1} b are b binary hash functions and z = h(x) is the b-bit code vector for input x ∈ R D , min h means minimizing over the parameters of the hash function h (e.g. over the weights of a linear SVM), and L(·) is a loss function that compares the codes for two images (often through their Hamming distance z n − z m ) with the ground-truth value y nm that measures the affinity in the original space between the two images x n and x m (distance, similarity or other measure of neighborhood). The sum is often restricted to a subset of image pairs (n, m) (for example, within the k nearest neighbors of each other in the original space), to keep the runtime low. The output of the algorithm is the hash function h and the binary codes Z = (z 1 , . . . , z N ) for the training points, where z n = h(x n ) for n = 1, . . . , N . Examples of these objective functions are Supervised Hashing with Kernels (KSH) [28] 
(1) where for KSH y nm is 1 if x n , x m are similar and −1 if they are dissimilar; for BRE y nm = 1 2 x n − x m 2 (where the dataset X is normalized so the Euclidean distances are in [0, 1]); and for the Laplacian loss y nm > 0 if x n , x m are similar and < 0 if they are dissimilar ("positive" and "negative" neighbors). Other examples of these objectives include models developed for dimension reduction, be they spectral such as Locally Linear Embedding [32] or Anchor Graphs [27], or nonlinear such as the Elastic Embedding [7] or t-SNE; as well as objectives designed specifically for binary hashing, such as Semi-supervised sequential Projection Learning Hashing (SPLH) [34]. They all can produce good hash functions. We will focus on the Laplacian loss in this paper.
In designing these objective functions, one needs to eliminate two types of trivial solutions. 1) In the Laplacian loss, mapping all points to the same code, i.e., z 1 = · · · = z N , is the global optimum of the positive neighbors term (this also arises if the codes z n are real-valued, as in Laplacian eigenmaps). This can be avoided by having negative neighbors. 2) Having all hash functions (all b bits of each vector) being identical to each other, i.e., z n1 = · · · = z nb for each n = 1, . . . , N . This can be avoided by introducing constraints, penalty terms or other mathematical devices that couple the b bits. For example, in the Laplacian loss (1) we can encourage codes to be orthogonal through a constraint Z T Z = N I [35] or a penalty term Z T Z − N I 2 (with a hyperparameter that controls the weight of the penalty) [14], although this generates dense matrices of N × N . In the KSH or BRE (1), squaring the dot product or Hamming distance between the codes couples the b bits.
An important downside of these approaches is the difficulty of their optimization. This is due to the fact that the objective function is nonsmooth (implicitly discrete) because of the binary output of the hash function. There is a large number of such binary variables (bN ), a larger number of pairwise interactions (O(N 2 ), less if using sparse neighborhoods) and the variables are coupled by the said constraints or penalty terms. The optimization is approximated in different ways. Most papers ignore the binary nature of the Z codes and optimize over them as real values, then binarize them by truncation (possibly with an optimal rotation; [16]), and finally fit a classifier (e.g. linear SVM) to each of the b bits separately. For example, for the Laplacian loss with constraints this involves solving an eigenproblem on Z as in Laplacian eigenmaps [2,35,36], or approximated using landmarks [27]. This is fast, but relaxing the codes in the optimization is generally far from optimal. Some recent papers try to respect the binary nature of the codes during their optimization, using techniques such as alternating optimization, min-cut and GraphCut [4,14,26] or others [25], and then fit the classifiers, or use alternating optimization directly on the hash function parameters [28]. Even more recently, one can optimize jointly over the binary codes and hash functions [8,14,31]. Most of these approaches are slow and limited to small datasets (a few thousand points) because of the quadratic number of pairwise terms in the objective.
We propose a different, much simpler approach. Rather than coupling the b hash functions into a single objective function, we train each hash function independently from each other and using a single-bit objective function of the same form. We show that we can avoid trivial solutions by injecting diversity into each hash function's training using techniques inspired from classifier ensemble learning. Section 1 discusses relevant ideas from the ensemble learning literature, section 2 describes our independent Laplacian hashing algorithm, section 3 gives evidence with image retrieval datasets that this simple approach indeed works very well, and section 4 further discusses the connection between hashing and ensembles.
Binary hashing can improve information retrieval efficiency from both time and space perspectives. Most existing methods learn hashing codes and function by a composite joint optimization, which makes the optimization a hard problem. Inspired by the diversity requirement in classifier ensemble, this paper proposes to learn hash function for each hashing code independently. Three types of diversity strategies are used, namely on different initializations, different training sets and different feature subsets. The new approach benefits from its computational efficiency and nesting property. Diverse experiments validate the effectiveness of the proposed ILH strategy.
Inspired by diversity requirement to train a good classifier in an ensemble scenario, this paper proposes to train binary hashing codes independently. This Independent Laplacian Hashing (ILH) approach optimizes in a two-step way: first learns hash codes and then trains the hashing function. Three types of diversity are proposed, and from the experiment results the one learned with different training sets can achieve better performance.  This paper investigates ILH approach from different perspectives, and explains the results in detail. Some discussions about orthogonal codes are interesting.  Here are some suggestions/questions about the experiments: 1. Statement in line 186-188 is not very clear. 2. In most experiments, only precision is reported. For example, in Fig.1, its better to show the change of recall at the same time. 3. In Fig.1, different methods are plotted in different graphs. Ploting different approaches with the same b value in a single graph may be better to find their differences. 4. Since ILH method is based on the random initialization, training subset and feature subset, different trials will get various results. How to control experiments w.r.t. this randomness is important. Will different random trails all output good last results or the results are based on a specific randomize strategy? 5. Performance of ILHf relies on the property of features. It discards useful features when training on CIFAR dataset, will it perform better when there are irrelevant or redundant features? 6. Time comparison on different datasets (about different versions of ILH and other compared methods) may be necessary to show the property of the proposed method.