Revisiting Locality-Sensitive Binary Codes from Random Fourier Features
Authors: Xiaoyun Li
Ping Li
Venue: ICLR 2022 Submitted (2022)

Abstract: The method of Random Fourier Feature (RFF) has been popular for large-scale learning, which generates non-linear random features of the data. It has also been used to construct binary codes via stochastic quantization for efficient information retrieval. In this paper, we revisit binary hashing from RFF, and propose SignRFF, a new and simple strategy to extract RFF-based binary codes. We show the locality-sensitivity of SignRFF, and propose a new measure, called ranking efficiency, to theoretically compare different Locality-Sensitive Hashing (LSH) methods with practical implications. Experiments are conducted to show that the proposed SignRFF is consistently better than the previous RFF-based method, and also outperforms other data-dependent and deep learning based hashing methods with sufficient number of hash bits. Moreover, we also validate that the proposed ranking efficiency aligns well with the empirical search performance.

Under review as a conference paper at ICLR 2022
REVISITING LOCALITY-SENSITVE BINARY CODES FROM RANDOM FOURIER FEATURES
Anonymous authors Paper under double-blind review
ABSTRACT
The method of Random Fourier Feature (RFF) has been popular for large-scale learning, which generates non-linear random features of the data. It has also been used to construct binary codes via stochastic quantization for efficient information retrieval. In this paper, we revisit binary hashing from RFF, and propose Sign- RFF, a new and simple strategy to extract RFF-based binary codes. We show the locality-sensitivity of SignRFF, and propose a new measure called ranking effi ciency to theoretically compare different Socality-Sensitii ods, which provides new systematic and unified framework for LSH comparison. It suggests that SignRFF should be preferred in the high similarity region. Experi- ments conducted to show that SignRFF is consistently better than the previous Raseb method, and also outperforms other data-dependent and deep learn- ing based hashing methods with sufficient number of hash bits. Moreover, the proposed ranking efficiency aligns well with the empirical search performance.
Hashing (LSH) meth-
INTRODUCTION
Developing efficient machine learning algorithms in large-scale problems has been an important research topic to deal with massive data. In this paper, focus on efficient retrieval/search methods, specifically, by designing similarity- preeeering binary representations of the data. That is, for each data vector RRd, we hash it into length-b binary 0/1 vector h(x)) {0, 13,, where the geometry of the data should be well preserved in the Hamming space. Searching with binary codes has been widely applied in many applications. such as large-scalt scale image retrieval (Weiss al., 2008: Gong & Lazebnik, 2011: I; Kulis & Darrell, 2009; He et al., 2013; Lin et al., 2015; Liu et al., 2016; 2017; Song al., 2018; Yu al., 2018; Yan al., 2021). The benefits are two-fold. Firstly, may largely reduce the memory cost for storing massive datasets, especially with nigh-dimensiioal data. Secondly, it can significantly speedup the retrieval process. For instance, the binary codes can be used build hash tables (e.g.. Indyk & Motwani (1998)) for sub-linear time approximate nearest neighbor (ANN) search. Moreover, the Hamming space, we can also apply exhaustive search, which much faster than computing the Euclidean distances, plus the technique of multi-inde hashing (Norouzi et al., 2012) can further accelerate the exact Hamming search by orders of magnitude.
In general, binary hashing methods can be categorized into supervised and unsupervised approaches. In this work, we focus on the unsupervised setting. Locality-Sensitive Hashing (LSH) (Indyk & Mot- wani, 1998) is one of the early hashing methods leading to binary embedding. The LSH targeting at cosine similarity (Charikar, 2002), also known as SimHash, generates binary hash codes using random hyperplanes by taking the sign of data-independent random Gaussian projections. For the cosine similarity, LSH has strict theoretical guarantee on the approximation error and search effi- ciency, but typically requires relatively long codes to achieve good performance. Hence, many works have focused on learning (lta-deepeneen short binary hash codes, through different objective func- tions. Examples include Iterative Quantization (ITQ) (Gong & Lazebnik, 20, Spectral Hashing (SpecH) (Weiss et al., 2008) and Binary Reconstruction Embedding (BRE) (Kulis & Darrell, 2009). Recently, some unsupervised deep learning based methods have been proposed in the computer vi- sion community, many of which are, to some extent, "task-specific" for moos-modal/vidde//mmgg retrieval, implemented based on some deep models like the autoencoder and VGG-16 (Liu et al., 2016; Do et al., 2017: Chen al., 2018; Li et al., 2019; Yang et al., 2019; Hansen et al., 2020: Liu et al., 2020; Qiu et al., 2021). By taking the advantage of the complicated model structures (c.g., CNN layers), these deep methods show promising performance in many image retrieval tasks.

---

Under review as a conference paper at ICLR 2022
Compared with the data-dependent methods (including deep methods), LSH has three advantages:
Although the data-dependent procedures can provide improved performance with fewer binary codes, known undesirable effect of many of these mechanisms is the performance degradation when we increase the code length b, as reported in prior literature (Raginsky & Lazebnik, 2009; Joly & Buisson, 201 I). In our experiments, we will show that this may also be an issue for deep learning based methods. On the other hand, the performance (i.e., search accuracy) of the iata-indepenndet LSH would keep boosting with larger b. In many scenarios, it is often the case that only using short codes (c.g., < 128 bits) cannot achieve a desirable level of search accuracy for practical purposes. In these cases, one may need to use longer codes anyway, where LSH could be more favorable.
LSH is very simple to implement (only with random projections), while data-dependent methods require additional optimization/training which might be costly. Moreover, large deep learning models would typically need longer inference time, which might be infeasible in practice where the query speed is important.
It is difficult to characterize the properties of the data-dependent methods theoretically, while LSH enjoys rigorous guarantees on the retrieval/approximation performance.
Therefore, LSH is still a popular hashing method with great research interest and many practical applications (Shrivastava & Li, 2014; Qi et al., 2017; Driemel & Silvestri, 2017; Chen et al., 2019; Zandieh et al., 2020; Lei et al., 2020; Daghaghi et al., 2021).
1.1 SENSITIVE HASHING FROM RANDOM FOURIER FEATURES
Kernel methods have gained great success in many machine learning tasks (Schölkopf & Smola, 2002; Zhu & Hastie, 2001; Avron et al., 2017; Sun et al., 2018). However, standard kernel methods require the n X n kernel matrix, which becomes computationally expensive on large-scale datasets with massive data points. To this end, Rahimi & Recht (2007) proposes the method of random Fourier feature (RFF), which defines a feature map that approximates shift-invariant kernels by the linear inner products. As such, the RFF preserves the "non-linear locality structure" of the data. This leads to numerous applications in large-scale learning where one trains linear models on RFF to approximate training non-linear kernel machines (Yang et al., 2012; Chwialkowski et al., 2015; Sutherland & Schneider, 2015; Avron et al., 2017; Sun et al., 2018; Tompkins & Ramos, 2018).
Given the popularity of RFF, one natural step apply it to search problems. Raginsky & Lazebnik (2009) proposes to construct binary codes from the RFF using stochastic binary quantization. We call this method "SQ-RFF". whose convergence (as + 00) and concentration can be theoretically characterized. The author showed that SQ-RFF can achieve competitive search accuracy with suffi- cient e.g., 2 512. Since RFF itself a widely used tool for large-scale kernel learning, SQ-RFF could be convenient/useful tool in practical scenarios where RFF has been generated for training kernel machines, and the data scientist wants to further use it for efficient near neighbor retrieval.
1.2 OUR CONTRIBUTIONS
Given the benefits of LSH and RFF, we revisit hashing methods for ninelineerr kernels, and improve the prior RFF based hashing method. Our approach is named as "SignRFF". Specifically.
We theoretically compare several linear and non-linear LSH methods in terms of novel measure called the ranking efficiency, which is defined based on the probability of retriev- ing wrong/reversed similarity ranking. Under this unified metric, the proposed SignRFF is uniformly better than SQ-RFF. Moreover, the ranking efficiency also indicates that typi- cally one should prefer SignRFF over linear LSH when the near neighbors are close each other, which is the first systematic comparison of linear vs. non-linear LSH in literature.
Empirically, we conduct near neighbor search experiments on benchmark image datasets to compare the proposed SignRFF with other popular hashing methods, which verifies the superiority of SignRFF over SQ-RFF. We validate that the ranking efficiency metric aligns well with the empirical results. Moreover, SignRFF outperforms various competing methods (including deep methods) with moderately large number of hash bits, indicating its ad advantage in applications achieve high search recall/precision.
2

---

Under review as a conference paper at ICLR 2022
2 PRELIMINARIES
2.1 LOCALITY- -EESIIVVE HASHING (LSH)
In large-scale information retrieval, exhaustive search of the exact nearest neighbors is usually too expensive. A common relaxation in this setting is the Approximate Nearest Neighbor (ANN) search, where return the "good" neighbors of query with high probability. In this paper, we will consider the search problem with data points R. X denotes the database consisting of n data points, and q is query point. æ. y are data points with p cos(ar, y).
Definition 2.1 (S-neighbor). For a similarity measure S IR x Rd + I, the S-neighbor set of q defined as (r E S(x, q) > $}.
Definition 2.2 ((c, SY-ANN), Assume > 0 is parameter. An algorithm A is a (c, SY-ANN method provided the following: with probability at least 1 - 6, for 0 < c < 1, if there exists an S-neighbor of in X, A returns cS-neighbor of q.
One popular method satisfying Definition 2.2 is the Socclltyy-ensitiieee Hashing (LSH).
Definition 2.3 (Indyk & Motwani (1998)). A family of hash functions H. is called 15,c5,p,, P2) locality-sensiiee sensitive for similarity measure and < uniformly chosen from H. it holds that: 1) If S(x, y) 2 S, then P(h(æ) h(y)) Z Pı 2) If S(x. y) S cS, then P(h(x) = h(y) S P2. with p2 < P1-
if for Ya, y Id and hash function
A key intuition of LSH is that, similar data points with have higher chance of hash collision in the Hamming space. In this paper, we will specifically consider the LSH for the cosine similar- ity (Charikar, 2002). For data vector Rd. the LSH binary code is given by
LSH:
hLSH(w sign(w' x))
where w T a standard Gaussian random vector. We use b i.i.d. WT, wr to generate b LSH binary codes. The collision probability between the codes of two data points æ, y is
P(hLS (x) = (L)HH())) =1 cos (p)
where o cos(æ, y) is their cosine similarity. Note that P(hLSH (x) hLSH(1)) is increasing in P, which, By Definition 2.3, is the key to ensure the locality sensitivity.
2.2 KERNELIZED LOCALITY-SENSTTIE HASHING (KLSH)
In this paper, we will consider the popular Gaussian kernel function defined for y E IRd as
- | -y1
k( y) = exp
where 7 is hyper-parameter. Let V Rdd F be the feature map with the kemnel induced feature space F. To incorporate non-linearity in LSH, Kulis & Grauman (2009) proposes Kernelized Locality-Sensitive Hashing (KLSH), by applying LSH (I) in the kernel induced feature space i.c., (xx) = sign(w (())))"(()))) However, as in many cases (c.g., for the Gaussian kernel) the map y cannot explicitly identified, constructing the random Gaussian projection vector w needs some careful design. KLSH approximates the random Gaussian distribution using sufficient number of data points, by the Central Limit Theorem (CLT) in the Reproducing Kernel Hilbert Space. One first samples m data points from X to form kernel matrix K, then uniformly picks / points from [1,..., m] at random to approximate the Gaussian distribution. The hash code has the form
KLSH:
hKLSH(#) = sign M w wi))(zz
where w = 1/2/ and e, E {0, 13mm has ones in the entries with indices of the selected points. We that the codes hi...., hy actually dependent, and the quality of using CLT to approximate Gaussian distribution is not guaranteed, especially in high-dimensional kernel feature space. Jiang et al. (2015) e-formulates KLSH as applying LSH the kernel principle components
3

---

Under review as a conference paper at ICLR 2022
in the kernel induced feature space, resolving theoretical concern of KLSH. Notably, since KLSH uses a pool of data samples to approximate the Gaussian distribution. the hash codes are in fact dependent in practical implementation. It is observed that the performance of KLSH also drops as b increases (Joly & Buisson, 201 1), similar to the behavior of many data-dependent methods. We provide more detailed explanation in Appendix C.
3 LOCALITY-SENSITIV BINARY CODES FROM RANDOM FEATURES
Rahimi & Recht (2007) proposes random Fourier feature (RFF) to alleviate the computational bottle- neck of standard kernel methods. For a data vector æ, the RFF for the Gaussian kernel is defined as
RFF:
F(x) = cos( w x: + T):
(4)
where w ~ Iaa) and T Uni f 2x) where I is the identity matrix. It holds that ((F()) A( 92/2.
That is, the non-linear kernel similarity can be preserved in expectation by the linear inner product of RFF. To obtain good approximation, we generate b independent RFFs for each data point using i..d. W1,.... we and T1..... Tb, which can be subsequently used for various learning tasks.
From now on, we will assume the data vectors are normalized to have unit l2 norm: 1) this is a standard pre- pee-processing step in practice; and 2) the theoretical guarantees of LSH (1) is only valid for the cosine similarity (i.e., normalized data). Nevertheless, our analysis can be easily extended to the general unnormalized case. With normalized data, the Gaussian kernel can be written function of cos( y): k()) k(x, = (1--))
To extend RFF efficient search problems, Raginsky & Lazebnik (2009) designs a mapping [0, 1] + 1) for each RFF. For x: E Rdd the code is produced by stochastic quantization (SQ):
hiq (z) sign (xx) + E) = sign(cos(w" + r) + E),
(5)
where & a random perturbation from fni 1), with two possible choices on the dependency. In Raginsky & Lazebnik (2009), the same & is used for all data points. Another option in litera- ture to use i.i.d. E for each data point, such that the binary codes admit ((h(())(())) = k(x,, y) For example, it is used in Zhang et al. (2019); Li & Li (2021) for large-scale low-precision train- ing. We also tested this strategy our experiments. The search performance however very poor, because more variation is introduced. On the other hand, actually do not need the exactly timation/recovery of the kernel values in search problems. Hence, in this paper we will consider the baseline using the same for all data samples in Raginsky & Lazebnik (2009). The collision probability of the so-called "SQ-RFF" is given as follows.
Theorem 3.1 (Raginsky & Lazebnik (2009)). For the SQ-RFF for. Vx, y R4, it holds that
PSQ(p) == (x) hsq(v)) =
8
Σ
20
1
1
(6)
π²
4s
This method is locality-sensitive w.r.t. P because of the fact that (6) is an increasing function of p- Hence, it is also Secaliy--eensitve w.r.t. the kernel k(p) by the monotonicity of k(p).
Proposition 3.2. The SQ-RFF (5) (Te, ck, Psq (P1). Psq
sensitive w.r.. similarity
measure k(-). where P1 = / + 1 and P2 = log( (g/cc)//> ) + 1.
In the kernel approximation problem, stochastic rounding introduces higher variance due to the noise S. which hurts the kernel estimation accuracy (Li & Li, 2021). Later, we will see that a similar effect also presents in search problems. To this end, we propose our simple strategy- diieectyy taking the sign of the RFF, i.e., applying deterministic quantization. Formally, the so-called "SignRFF" approach constructs the binary codes for by
SignRFF: hsign (m) = (eig((((a)) sign(cos(w" T)).
Operationally, SignRFF is extremely convenient. At the first glance, it may appear a bit surprising that this simple scheme has not been studied in literature. We believe one of the reasons is that the theoretical correctness of SignRFF is hard to justify. Indeed, with some recent progress on RFF, we can show that Fig is locality-sensitive.
4

---

Under review as a conference paper at ICLR 2022
Lemma 3.3 (Li & Li (2021)), For two normalized data points æ. y with cosine p. let F(.) be the
RFF defined as (4). The joint distribution of 2e = F)) and By = P F(y)
2 (a az + 2kT) a + a + 2k
[(Za, Zylp)
(8)
5/1 23
/ z2
where d cos -00000000))000))000000 (zn), ay cos (zy), and de (-) is the p.d.f. of N o²) with o 22(1- Furthermore, [lsign( ((z))ssgg(( (F())) is increasing function of p.
Proposition 3.4. The SignRFF (7) is (k, cki, Psign (p1), Psign (p2)) -localiyy sensitive w.r.. to k(.))
with P1 //² and P2 log(ck)//> 1, with collision probability
Psign (p) == Phasign (x) sign (1)) =2 f f Zylp)
where (Zay Zyl (p) the density function (8).
Proof. By Definition 2.3 and the monotonicity of k(p), it suffices to show that the collision probability, Psign (p), increasing in p. This immediately follows from Lemma 3.3 that E[sign( (z))ssign( F(y)]] = Psign (p) - -11 P(igg(()))) = Pesign (p) 1 is increasing in p.
4 THEORETICAL COMPARISON OF LSH METHODS: A NEW SCHEME
In our theoretical analysis, we assume for KLSH (Kulis Grauman, 2009) that the Gaussian pro- jection in the kernel induced feature space F is truly random. That is, KLSH "ideally" performs LSH the kernel space: IKL. (a) = sign(w" (x)) where is a random Gaussian vector with proper dimensionality. Since V(x) (yy) = k(x, y). applying (2) in F we obtain
PKLSH(P) = P(hKLSH (x) = LKLSS (y)) = cos (e (e->p(1))))
(10)
π
Proposition 4.1. KLSH is (k, ck, 1- cos 1(k) cos ((ck) llcallity sensitive w.r.t. k(-).
Recall Definition 2.3 of the (k,, P1, P2) LLSH. It is known (Indyk & Motwani. 1998) that one construct LSH data structure with the worst case query time (n where R == log is called the I.S efficiency, which has been used in literature theoretically compare different LSH methods, c.g. SimHash vs. MinHash (Shrivastava & Li, 2014). However, we should note that the LSH efficiency is only based on a worst case analytical bound. Therefore, it may not well explain or predict the practical search performance (See Appendix A. for related results).
log pz
We propose a novel measure for evaluating the search accuracy of LSH schemes, namely, the ranking efficiency, that can better compare LSHs in practice. The definition is motivated by the observation that regardless of the concrete approach (e.g.. building hash tables or exhaustive search), the nearest neighbor retrieval, to large extent, essentially boils down to estimating the Euclidean (cosine) similarity rankings in the Hamming space. Suppose æ and y are two points in the database, and q is query with Pa cos(q, æ), py cos(q, y). Assume is the true nearest neighbor of q, implying Pr > Py. By the property of LSH, we know that the hash collision probability Pa > Py- For an LSH hash function h, define the corresponding collision probability estimators
Pr Σ 1(h,(z)=hh(a)))
= h:(g)),
Py p== P== 1 1(h:(u))hh())))
(11)
Now the problem becomes comparing Pr and py to estimate the true ranking of and Py. We consider the event of obtaining a wrong similarity comparison from our estimation, i.e. Pz S py- Obviously, a higher probability implies worse search accuracy, we are more likely to retrieve the wrong nearest neighbor y. Denote
E. [[((h(x) = h(g)), E, E(((h(y) h(g)H1,
Vi Vay
Vay
(h(()( h(g)), ((h()) = h(g))) E
Vg
5

---

Under review as a conference paper at ICLR 2022
Pz
Ex B,y
E/b). This approximation would be good with a sufficiently large number of b, c.g., b 2 30. In this regime,
By the CLT, we know that as b + 0o,
N
Py
compute
VU(E. Eny VV2 + V. 2V
P(pa S Ppy P(p. - By 0) -1
(12)
where (-)) is the c.d.f. of standard normal distribution. For all the LSH methods studied in this paper, the Eg and Ey are simply the collision probabilities, and V2 (1 V E1 from the binomial distribution. Yet, the covariance Vay is difficult to be analytically computed. For simplicity, we assume that this term has same relative influence on the estimators of all approaches, thus dropping it in the formal definition of the ranking efficiency, which is given as below.
Definition 4.1 ((p c)- Ranking Efficiency). For LSH method, let the hash collision probability at cosine P and cp be E and E. respectively. Let V = (E(1-E) E), V. E E E2). The (p,c) (rankingg efficiency is defined as RE E-E,
VVVV.
Remark 4.1. The RE can also be defined in terms of the non-linear kernel k(.). We use cosine here address both linear and non-linear LSH for generality. In most retrieval applications, may concern more about high c (e.g., c 0.95) which corresponds to similar data points.
In general, higher RE implies smaller probability of the reversed estimated ranking in (12), which is more favorable. In Figure 1, we provide the comparison of ranking efficiency at different which covers the cases in our empirical study (Section 5). We observe some consistent patterns:
Non-linear LSH. Firstly, compared with the other RFF-based approach SQ-RFF, the pro- posed SignRFF uniformly more efficient at all p. In other words, in search tasks, the stochastic quantization of SQ-RFF introduces more "variation" that lowers the ranking ef- ficiency. Compared with KLSH, SignRFF is more efficient when y is large (e.g.. Y > 2) in all plots, while KLSH tends be more efficient with small In general, SignRFF is the best in terms of ranking efficiency.
When should prefer non-linear LSH? The ranking efficiency gives novel theoretical guidance on the appropriate choice between linear and non-linear LSH methods. We see that, when the target p high (e.g.. p > 0.8), with proper tuning, kernel methods (Sign- RFF and KLSH) can be more efficient than linear LSH. However, if the target is small (e.g., P < 0.7), linear LSH might be more favorable. In other words, SignRFF could be better than LSH on datasets where the near neighbors are close to each other with high similarity/short distance, which usually the case for, e.g., image data.
x10
x10
x10
ranking efficiency
ranking efficiency
0 0.95
LSH
ranking afficiency
p 0.3
0.95
SignRFF
SignRFF .LLSH SC-RFF
KLSH
SQ-RFF
LSH SignRFF KLSH
0.5
2
3
4
5
2
3
4
5
2
3
4
xx10
x110
x10
1.5
ranking efficiency
ranking efficiency
ranking efficiency
= 0.9 c 0.95
0.8 0.95
SignRFF KLSH
LSH
LSH
KLSH
SignRFF
0.5
p
0.95 c= 0.95
SignRFF
KLSH
SQ-RFF
SQ-RFF
8Q RFF
0
2
3
4
2
3
5
2 3
4
Figure Ranking efficiency (Definition 4.1) of different LSH methods with various p. c 0.95.

---

Under review as a conference paper at ICLR 2022
The ranking efficiency measures the search accuracy for given target p value. In practice, dataset contains many different pairs (with different p). Our experiments on real datasets in the next section show that the performance is largely consistent with the prediction based on the "average p" value.
5
EXPERIMENTS
In this section, we conduct image retrieval experiments on benchmark datasets to demonstrate the effectiveness of our approach and justify the theoretical comparison of ranking efficiency.
5.1 DATASETS, METHODS AND EVALUATION
Datasets. We use three popular benchmark datasets in image retrieval literature. The SIFTIM dataset (Jé- gou et al., 2011) contains 1M 128-dimensional SIFT image features, and 1000 query samples. The MNIST dataset (LeCun, 1998) contains 60000 hand-written dig-
CIFAR
0.9
SIFT
0.8
MNIST
its. We randomly choose 1000 samples from the test set as the query points. The CIFAR dataset (Krizhevsky, 2009) contains 50000 natural images. We use the gray-scale im-
0.7
CIFAR-VGG
ages in our experiments, and randomly select 1000 test
0.6
samples as the queries. In addition, when comparing our
100
10
10²
10
methods with VGG-16 (Simonyan Zisserman, 2015) based deep methods, following prior literature (c.g.. Yang et al. (2019); Qiu et al. (2021)), we use the 4096-d fea- tures from the last fully connected layer of the pre-trained VGG-16 network as the input data for shallow methods for fairness. This dataset is called "CIFAR- VGG". On all datasets, the data points are normalized to have unit norm. In Figure 2, we report the average cosine similarity between queries to their N-nearest neighbor, from N = 1 to 1000.
top similarity
Figure 2: Average P to N neighbor.
Methods. We compare the following unsupervised hashing methods: 1) LSH (Charikar, 2002); 2) Iterative Qauntization (ITQ) (Gong & Lazebnik, 201 I); 3) Spectral Hashing (SpecH) (Weiss et al., 2008); 4) Binary Reconstruction Embedding (BRE) with 1000 random samples for model training as suggested by Kulis & Darrell (2009); 5) KLSH with m = 500 random samples for formulating the kernel matrix and
50 samples for the CLT Gaussian approximation, which should be more accurate than (300, 30) as recommended in Kulis & Grauman (2009); 6) SQ-RFF (Raginsky & Lazebnik, 2009): 7) Our proposed SignRFF. For kernel LSH methods 5)-7), we tune the parameter over 0.1 ~ 5 and report the best with highest average recall over multiple b = 32 ~ 1024. For each tested method, we generate binary codes and perform exhaustive search in the Hamming space.
Evaluation. For each query point, the ground truth nearest neighbors are set by ranking the top N = 100 smallest Euclidean distance (top-100 largest cosine similarity). After running each algorithm, the Hamming ranking returns R estimated nearest neighbors to each query. We report the average recall over 1000 queries. Note that, recall equivalent to precision @N in our setting. See Appendix A.2 for more detailed explanation and additional results on the retrieval precision.
5.2 RESULTS
In Figure 3, we report the recall@N (precision @N) against the number of binary codes
On SIFT and MNIST, data-dependent methods (TTQ, SpecH, BRE) perform well with low bits, but the recall does not improve much after b > 100 ~ 200. Yet, this low bit region does not help much in practice, since the recall level is too low (e.g. 0.3 on SIFT and CIFAR) to be satisfactory for real-world tasks. As we mentioned, this is a known limitation of these methods. When b 2 256, LSH-type methods start to dominate, as expected. On CIFAR, SignRFF and KLSH outperform the data-dependent methods even with low bits.
On all three datasets, SignRFF is substantially better than SQ-RFF with all b. Due to dependence. KLSH has higher recall than SignRFF when b is small (e.g.. S 256), but is beaten by SignRFF with more bits. The gap is significant and consistent when b as large 512, where SignRFF achieves the highest recall on all three datasets.
7

---

Under review as a conference paper at ICLR 2022
0.6
0.6
0.8
SIFT
CIFAR
MNIST
recall 100
0.4
LSH
recall@ 100
LSH
recal 100
0.6
LSH
ITQ
SpecH
SpecH
SpecH
BRE
BRE
BRE
0.2
SQ-RFF
SQ-RFF
0.2
SQ-RFF
KLSH
SignRFF
SignRFF
SignAFF
0
500
1000
500
1000
500
1000
bits
bits
bits
Figure 3: Recall b. "recall @ 100" is the recall evaluated on the 10p-100 retrieved neighbors. Note
that in our case, recall 100 equivalent to precision @ 100.
SIFT
CIFAR
0.8
0.8
0.8
LSH
LSH
recall
0.6
++TO
recall
0.6
ITQ
recall
* ITQ
SpecH
SpecH
SpecH
0.4
BRE
0.4
BRE
SO-RFF
MNIST
0.2
KLSH
0.2
KLSH
SIgnRFF
SggRFFF
SignRFF
0.2
0
500
1000
0
500
1000
500
1000
If of retrieved neighbors
# of retrieved neighbors
# of retrieved neighbors
CIFAR
0.8
LSHH
LLHH
recall
0.6
ITO SpoaH BRE
recail
ITQ
(eca)
SpecH
0.6
S.SpocH
0.4
BRE
0.2
SQ RFF
KLSH
0.4
MNIST
-SQ-RFF
KLSH
SignAFF
SignRFF
SignAFF
500
1000
500
1000
500
1000
retrieved neighbors
# of retrieved neighbors
of retrieved neighbors
Figure 4: Recall vs. number of retrieved neighbors. 1st row: 512. 2nd row: b = 1024.
In Figure 4, we present the recall versus the number of retrieved neighbors, with b 512 and b = 1024. SignRFF performs the best among all competing methods on SIFT and CIFAR. On MNIST, SignRFF performs similarly to LSH and better than the other methods with sufficient b.
Ranking efficiency. In Figure 5, we additionally provide the recall against the Gaussian parameter y, to justify the effect ranking efficiency discussed Section 4. In Figure 1, the theoretical comparison suggests that KLSH would perform better with small while SignRFF is more efficient larger 7, which matches the empirical evidence (c.g., I vs. 2.5 on SIFT). Moreover, as shown in Figure 2, the average P between each query and its neighbors around 0.8, 0.9 and 0.95 for MNIST, SIFT and CIFAR, respectively. Figure predicts that compared with SQ-RFF (blue), LSH (green) would perform better on MNIST, similarly on SIFT, and worse CIFAR, which aligns with
1esalle 100
0.4
recall@ 100
recalle1 100
0.6
0.3
0.5
0.3
SIFT
SO-RFF KLSH
LSH
CIFAR
SQ-RFF
KLSH
LSH
0.4
LSH
SQ-RFF
KLSH
MNIST
SignRFF
SignRFF
7
7
Figure 5: Recall @ 100 (precision @ 100) vs. with b = 512.
8

---

Under review as a conference paper at ICLR 2022
Figure and Figure 4. Therefore, although the behavior of KLSH slightly deviates from the theory due to the dependence among hash codes, our experiments in general verify the effectiveness of the ranking efficiency informative measure to compare different LSH methods.
5.3 COMPARISON WITH DEEP HASHING
We provide additional experiments on the CIFAR-VGG dataset with recent unsupervised deep hashing method for image retrieval, the Contrastive Information Bottleneck (CIB) (Qiu al., 2021), which uses VGG-16 pre-trained model as the backbone. We apply the same training setting as in Qiu et al. (2021): I): 60 epochs, 64 mini-batch size and Adam optimizer with 0.001 learning rate. We note that, CIB (as well as many other deep methods) is not designed to find the most similar data points. Instead, by using techniques like cropping and rotation in training CNN, these methods aim robustly finding data points with same label the query, which does not necessarily imply high similarity with the query when represented by the fc7 layer of VGG-16. Hence, to favor CIB, in this experiment expand the range of true neighbors of query the top- 1p-1000 similar points in the database. See Appendix B for examples of the retrieved images and more discussion.
From Figure 6, we see that CIB performs the best with 32 and 64 bits than LSH methods, which illustrates the benefit of deep hashing with short codes. However, the recall only 0.3~0.4, and does not improve with more bits, since simply increasing the size of last layer in the deep net typically would not elevate the model performance significantly. When b 2 256, LSH, SignRFF and KLSH provide much higher recall than CIB.
Among LSHs, KLSH performs the best on this task. SignRFF again consistently improves SQ-RFF, and matches the recall KLSH with b 1024. In addition, linear LSH slightly outperforms SignRFF, which is consistent with the theoretical comparison in Figure 1 as expected (the target p is 00.7 for this task, where LSH is more efficient than SignRFF).
CIFAR-VGG
LSH
CIB
-S.LSH
CIB
recallo 1000
0.6
0.6
0.6
SQ-RFF
KLSH
KLSH
0.4
CIB
rocal
0.4
SignRFF
recall
0.4 SignRFF
LSH
SC-RFF KLSH SignRFF
CIFAR-VGG
CIFAR-VGG
1000
500
1000
500
1000
bits
# retrieved neighbors
# of retrieved neighbors
Figure 6: Left panel: Recall @ 1000 (precision @ 1000) vs. b. Mid & Right panel: Recall vs. # retrieved points, 512, 1024.
CONCLUSION
Random Fourier Feature (RFF) a popular method large-scale kernel learning, which has also been used for constructing binary codes for fast non-linear neighbor search (Raginsky & Lazebnik, 2009). In this work, we revisit RFF-based binary hashing, and propose a new strategy named Sign- RFF. We analyze its locality-sensitive property, and provide new unified theoretical framework to compare different LSH methods, based on a measure called ranking efficiency. The metric implies that, should prefer SignRFF over the linear LSH in the high similarity region when data points are close to each other. Empirically, we demonstrate that SignRFF significantly better than the previous RFFF-based approach, SQ-RFF, and outperforms data-dependent and deep hashing meth- ods when the number of hash bits moderately large. Moreover, the theoretical comparisons of the proposed ranking efficiency is consistent with the empirical results, suggesting that it could serve as a good thcoretical tool for comparing the search performance of different LSH methods in practice.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random fourier features for kernel ridge regression: Approximation bounds and sta- tistical guarantees. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 253-262, Sydney, Australia, 2017.
Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 380-388, Montreal, Canada, 2002.
Lin Chen, Hossein Esfandiari, Gang Fu, and Vahab S. Mirrokni. Docality-sensitive hashing for f- divergences: Mutual information loss and beyond. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 10044-10054, 2019.
Zhixiang Chen, Xin Yuan, Jiwen Lu, Qi Tian, and Jie Zhou. Deep hashing via discrepancy mini- mization. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 6838-6847. Computer Vision Foundation / IEEE Computer Society, 2018.
Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. In Advances in Neural Information Processing Systems (NIPS), pp. 1981, Montreal, Canada, 2015.
Shabnam Daghaghi, Tharun Medini, Nicholas Meisburger, Beidi Chen, Mengnan Zhao, and An- shumali Shrivastava. A tale of two efficient and informative negative sampling distributions. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2319-2329. PMLR, 2021.
Thanh-Toan Do, Dang-Khoa Le Tan, Trung T. Pham, and Ngai-Man Cheung. Simultaneous feature aggregating and hashing for large-scale image search. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 4217- 4226. IEEE Computer Society, 2017.
Anne Driemel and Francesco Silvestri. Locality-sensitive hashing of curves. arXiv preprint arXiv: 04040, 2017.
Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado Springs, CO, USA, 20-25 June 2011, pp. 817-824. IEEE Computer Society, 2011.
Casper Hansen, Christian Hansen, Jakob Grue Simonsen, Stephen Alstrup, and Christina Lioma. Unsupervised semantic hashing with pairwise reconstruction. In Proceedings of the 43rd Inter- national ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pp. 2009-2012. ACM, 2020.
Kaiming He, Fang Wen, and Jian Sun. K-means hashing: An Sefinity-preservve quantization method for learning binary compact codes. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23-28, 2013, pp. 2938-2945. IEEE Computer So- ciety, 2013.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pp. 604-613, Dallas, TX, 1998.
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1): (311):1 177-128, 2011.
Ke Jiang, Qichao Que, and Brian Kulis. Revisiting kernelized Docality-sensitive hashing for im- proved large-scale image retrieval. In IEEE Conference Computer Vision and Pattern Recog- nition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pp. 1933-4941 IEEE Computer Society, 2015.
10

---

Under review as a conference paper at ICLR 2022
Alexis Joly and Olivier Buisson. Random maximum margin hashing. In The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado Springs, CO, USA, 20-25 June 2011, pp. 873-880 IEEE Computer Society, 2011.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Depart- ment of Computer Science, University of Toronto, 2009.
Brian Kulis and Trevor Darrell. Learning to hash with binary reconstructive embeddings. In Ad- vances Neural Information Processing Systems 22: 23rd Annual Conference on Neural Infor- mation Processing Systems 2009. Proceedings of meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pp. 1042-1050. Curran Associates, Inc., 2009.
Brian Kulis and Kristen Grauman. Kernelized pocality-sensiiie hashing for scalable image search. In ICCV, pp. 2130-2137, 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmistt/ 1998.
Yifan Lei, Qiang Huang. Mohan S. Kankanhalli, and Anthony K. H. Tung, Locality-sensitive hash- ing scheme based on longest circular co-substring. In Proceedings of the 2020 International Conference on Management of Data (SIGMOD), pp. OR, USA], 2020.
Online conference [Portland,
Shuyan Li, Zhixiang Chen, Jiwen Lu, Xiu Li, and Jie Zhou. Neighborhood preserving hashing for scalable video retrieval. In 2019 IEEE/CVF International Conference on Computer Vision. ICCV 2019, Seoul, Korea (South), October 27 NNvember 2019, pp. 8211-8220. IEEE, 2019.
Xiaoyun Li and Ping Li. Quantization algorithms for random fourier features. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 6369-6380, PMLR, 2021.
Kevin Lin, Huei-Fang Yang, Jen-Hao Hsiao, and Chu-Song Chen. Deep learning of binary hash codes for fast image retrieval. In 2015 IEEE Conference Computer Vision and Pattern Recog- nition Workshops, CVPR Workshops 2015, Boston, MA, USA, June 7-12, 2015, pp. 27-35. IEEE Computer Society, 2015.
Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen. Deep supervised hashing for fast image retrieval. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 2064-2072. IEEE Computer Society, 2016.
Hong Liu, Rongrong Ji, Yongjian Wu, Feiyue Huang, and Baochang Zhang. Cross-modality binary code learning via fusion similarity hashing. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 6345-6353. IEEE Computer Society, 2017.
Song Liu, Shengsheng Qian, Yang Guan, Jiawei Zhan, and Long Ying. Joint-modal distribution- based similarity hashing for large-scale unsupervised deep cross-modal retrieval. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pp. 1379-1388. ACM, 2020.
Mohammad Norouzi, Ali Punjani, and David J. Fleet. Fast search in hamming space with multi- index hashing. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, Provi- dence, RI, USA, June 16-21, 2012, pp. 3108-3115. IEEE Computer Society, 2012.
Lianyong Qi, Xuyun Zhang, Wanchun Dou, and Qiang Ni. A distributed locality- sensitive hashing- based approach for cloud service recommendation from multi-source data. JEEE J. Sel. Areas Commun., 35(11):26116)) 11:11666662224, 2017.
Zexuan Qiu, Qinliang Su, Zijing Ou, Jianxing Yu, and Changyou Chen. Unsupervised hashing with contrastive information bottleneck. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 2021, pp. 959-965. org, 2021.
11

---

Under review as a conference paper at ICLR 2022
Maxim Raginsky and Svetlana Lazebnik. Locality-sensitive sensitive binary codes from shift-invariant ker- nels. In Advances in Neural Informaiion Processing Systems (NIPS), pp. 1509-1517, Vancouver, Canada, 2009.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NIPS), pp. 1177-1184, Vancouver, Canada, 2007.
Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels. The MIT Press, Cambridge, MA, 2002.
Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 886- 894, Reykjavik, Iceland, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale im- age recognition. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Jingkuan Song, Tao He, Lianli Gao, Xing Xu, Alan Hanjalic, and Heng Tao Shen. Binary generative adversarial networks for image retrieval. In Proceedings of the Thirly-Second AAAI Conference on Artificial Intelligence, (AAAI-18). the 30th innovative Applications of Artificial Intelligence (IAAI- 18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 394-401. AAAI Press, 2018.
Yitong Sun, Anna C. Gilbert, and Ambuj Tewari. But how does it work in theory? linear SVM with random features. In Advances in Neural Information Processing Systems (NeurIPS), pp- 3383-3392, Montréal, Canada, 2018.
Danica J. Sutherland and Jeff G. Schneider. On the error of random fourier features. In Proceed- ings of the Thirty-Firss First Conference on Uncertainty Artificial Intelligence (UAI), pp. 862-871, Amsterdam, The Netherlands, 2015.
Anthony Tompkins and Fabio Ramos. Fourier feature approximations for periodic kernels in time- series modelling. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI), pp. 41 4155-4162, New Orleans, LA, 2018.
Yair Weiss, Antonio Torralba, and Robert Fergus. Spectral hashing, In NIPS, 2008
Chenggang Yan, Biao Gong, Yuxuan Wei, and Yue Gao. Deep multi-view enhancement hashing for image retrieval. IEEE Trans. Pattern Anal. Mach. Intell., 4344): 1451, 2021.
Erkun Yang, Tongliang Liu, Cheng Deng, Wei Liu, and Dacheng Tao. Distillhash: Unsupervised deep hashing by distilling data pairs. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition (CVPR), pp. 2946-2955, Long Beach, CA, 2019.
Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. Nyström method vs random fourier features: A theoretical and empirical comparison. In Advances in Neural Information Processing Systems (NIPS), pp. 485-493, Lake Tahoe, NV, 2012.
Laihang Yu, Lin Feng, Huibing Wang, Li Li, Yang Liu, and Shenglan Liu. Multi-trend binary code descriptor: novel local texture feature descriptor for image retrieval. Signal Image Video Process., 12(2):2472254 2018
Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, and Ilya P. Razenshteyn. Scaling up kernel ridge regression via locality sensitive hashing. In Proceedings of 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 4088-4097, Online [Palermo, Sicily, Italy], 2020.
Jian Zhang, Avner May, Tri Dao, and Christopher Ré. Low-precision random fourier features for meeorry-constraing kernel approximation. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1264-1274, Naha, Okinawa, Japan, 2019.
Zhu and Trevor Hastie. Kernel logistic regression and the import vector machine. NIPS, pp- 1081-1088, Vancouver, BC, Canada, 2001.
12

---

Under review as a conference paper at ICLR 2022
A
MORE ANALYTICAL FIGURES AND EXPERIMENTS
A.1
COMPARISON OF LSH EFFICIENCY
LSH Efficiency
0.8
LSH Efficiency
0.8
0.6
LSHH
LSH
SignRFF -KLLSH
0.6
SignRFF
7 c 0.95
KLSH
7 c= 0.95
SQ-RFF
SQ-RFF
0.2
0.4
0.8
0.9
0.4
0.6
0.8
k
k
7 5 C 0.95
LSH Efficiency
0.9
LSH Efficiency
0.98
0.96
0.8
0.94
LSH
SignRFF
SignRFF
0.7
- 0.95
0.92
KLSH
SQ-RFF
0
0.5 K
0.2
0.4
0.6
0.8
k
Figure 7: LSH efficiency of different LSH methods with various 7, 0.95. The w-axis is the Gaussian kernel value in alignment with Definition 2.3, Proposition 3.2, 3.2 and 4.1.
Recall Definition 2.3 of the (ke, ck. Pr. P1.P2) P2)-LSH. It is known (Indyk & Motwani, 1998) that one can construct LSH data structure with the worst case query time (n) where
R = log P1/ log
called the LSH efficiency. which has been used in literature theoretically compare different LSH methods, e.g. SimHash vs. MinHash (Shrivastava & Li, 2014). However, we found that in our case, the LSH efficiency does not provide much informative comparison of different L.SH methods of interest. In Figure 7, we provide the LSH efficiency at multiple Firstly, we see that the differences among the curves are very small. Basically, the figures tells us that SignRFF is always better than KLSH and SQ-RFF, but do not provide the comparison of SignRFF and KLSH regarding as the ranking efficiency does. Also, the figures seem to suggest that SignRFF could (roughly) better than LSH with large y and large p. but it does not give good threshold at around p 0.7 (validated by the experiments) as suggested by the ranking efficiency. Thus, LSH efficiency insufficient to well predict the practical search performance.
A.2 MORE EXPERIMENTS ON SEARCH PRECISION
Define N as the number of ground truth neighbors. The search recall and precision are defined as recall @R # true neighbors in retrieved points
N
# true neighbors in R retrieved points
precision @R
R
Consequently, by definition, recall@) @ is equivalent to precision @ @N. Therefore, in our experiments, ie., Figure 3, Figure 5 and Figure 6, the curves are also "precision@N"" In Figure 8, we report see, SIFT, CIFAR and MNIST, the SignRFF
more results the search precision @R. As method again performs the best as long as > 256. The comparison is fairly consistent with the recall (precision) curves presented in Section 5.
13

---

Under review as a conference paper at ICLR 2022
SIFT
CIFAR
0.8
0.8
0.8
pregisoon@1
LSH
precis 1osloone11
@recision@h1
LSH
0.6
+TQQQ
0.6
ITO
0.6
ITQ
SpecH
SpecH
0.4
BRE
0.4
BRE
0.4
BRE
SQ-RFF
SQ-RFF
0.2
KLSH
0.2
KLSH
0.2
KLSH
SignRFF
SgnRFF
SignRFF
500
1000
0
500
1000
500
1000
bits
bits
bits
0.8
SIFT
TTQ
MNIST
precision
BRE
SpacH
precision
--- LSH
precision
LSH
0.6
SO-RFF
Spech
SpacH
KLSH
0.4
SignRFFF
0.2
SCHRFF
0.6
SQ RFF
SignRFF
SignAFF
0.2
0.4
50
100
50
100
100
# of retrieved neighbors
# of retrieved neighbors
# of retrieved neighbors
Figure 1st row: Precision @ 10 against b. 2nd row: Precision vs. retrieved points, b = 512.
A.3 DATA PROCESSING TIME
Another benefit of SignRFF its simplicity in implementation. This can reflected the data processing time. Note that, the query time consists of two parts: the processing time (to generate query binary codes), and the search time (to compare the query codes to the database). our experiments, since adopt the standard Hamming ranking method, the search time return fixed number of retrieved points are the same for all algorithms. Hence, we plot the comparison of processing time (for 1000 queries), shown Figure 9. We observe that SignRFF and LSH are the most efficient methods. KLSH is notably slower than SignRFF. The two data-dependent methods, SpecH and BRE, are significantly slower than Rign This reveals potential advantage of the simplicity of SignRFF in practical retrieval systems.
0.08
LSH
processing time
0.06
SpecH
BRE
SQ-RFF
0.04
KLSH
SignRFF
0.02
0
0
500
1000
bits
Figure 9; Data processing time (1000 queries).
14

---

Under review as a conference paper at ICLR 2022
B MORE IMAGE RETRIEVAL RESULTS ON CIFAR-VGG
In Section 5.3, compare the lecality-sensitive bashing methods with deep learning based method, the Contrastive Information Bottleneck (CIB) (Qiu et al., 2021). CIB built upon the pre-trained VGG-16 CNN model, whose objective is generate binary representations such that images from the same class are close. Thus, same as many other deep hashing methods, the objec- tive of CIB is slightly different from our setting (we find the most similar data points, without any label information). as being in the same class does not necessarily implies high similarity. In fact, the empirical evaluation of many of these papers (c.g., Yang et al. (2019): Qiu et al. (2021)), the true neighbors are simply set as those data points with same label as the query. In our setting, we strictly follow the ranking to find the true neighbors with highest similarities. To better illustrate the difference, we present top-10 retrieval result of two queries (automobile and cat) in Figure 10. For SignRFF and KLSH, the retrieved images mostly have high similarity with query, but may in- clude some data points from other classes (e.g., truck vs. automobile, dog vs. cat). On the contrary. the retrieved images of CIB clearly have lower similarity with the query, but contain fewer other classes. This is largely because the VGG-16 is pre- trained by classification. Hence, in this exper- iment we set the true neighbors as the top- 1000 similar data points, where CIB could be evaluated properly since most images from the same class would, least, have not too low similarity.
0.84346
0.83696
0.83491
0.83276
0.82833
0.82569
0,82006
0.8107
0.81866
0.81854
0.83605
0.78657
0.83401
0.75924
0.81588
0.84946
0.78874
0.78514
0.81006
0.79105
0.84345
0.62549
0.83276
0.81054
0.79838
0.53695
0,82006
0.7382
0.78659
0.81144
AIE
0.7116
0.78082
0.66964
0.67989
0.76262
0.68823
0.78574
0.75481
0.72452
0.708
0.8453
0.75363
0.72542
0.7122
0.71088
0.70822
0.70533
0.70361
0.69812
0.8453
0.70533
0.73863
0.69618
0.67699
0.56063
0.66057
0.68994
0.67611
0.8453
0.70533
0.6808
0.71096
0.65584
Figure 10: CIFAR Top- 10 retrieved images (right) for two query points (left) with 512: Auto- mobile and Cat. 1st row: true nearest neighbors in terms of cosine similarity of the features extract from the last layer of VGG- 16. 2nd row: SignRFR. 3rd row: KISHH. 4th row: CIB, The number on each retrieved image is the cosine similarity to the VGG-feature of the query.
15

---

Under review as a conference paper at ICLR 2022
C IMPACT OF THE DEPENDENCE IN KLSH
In practical implementation, the hash codes of KLSH are dependent. We give an intuitive explana- tion on how this dependence affect the search performance.
Firstly, let us review the reason why data-independent methods with independent codes (LSH, SQ- RFF, SignRFF) can boost search accuracy with increasing b. Essentially, same the intuition of the rank efficiency, comparing Hamming distance is equivalent to searching for the data points with highest estimated hash collision probability using b codes. Let æ, y be database points and q be the query, with Pr. > Py- This means the hash collision probability Pa. Py. We estimate the probability by averaging the collision indicators:
6 P= 6 Σ ((),())=)((a)) Pv b
b Σ
-
(13)
For data-dependent methods, with sufficient 6, (12) gives the probability of wrong raking (i.c., Pa < py). We see that it strictly decreases with larger b.
Recall the steps of KLSH. We first sample data points from database X, denoted X, to form kernel matrix K. Then we uniformly pick points, denoted X', from [1, ..,, ml at random to approximate the Gaussian distribution. After some algebra, the hash code has the form
T72
KLSH:
h(x=) sign( Σ
(i))(
(14)
where = K- and e, E {0, 1) has ones in the entries with indices of the t selected points. To generate multiple codes, we the same pool of points X, but with different choice of et, i.e., X' to approximate the Gaussian distribution.
Boosted performance with small b. For two hash codes hg and hę-1 of æ. the k(æ, x;)) terms in (14) are the same. The w's 's are dependent since the points used for Gaussian approximation (i.e. X') may overlap. Thus, the conditional hash collision probability is usually larger than the unconditional one,
((hx(x)) = h4 h (y)( = h hx-1(1)) > ((h)(z) = h& (v)),
and it may increase as get larger (intuitively, by dependence, more previous collisions implies higher chance of collision later on). Similarly.
((hx(a)) + ha (y)
+ hx-1 > ((h + he (y))-
Thus, at the beginning. the more similar (dissimilar) the data pair is, the more the estimator á is upward (downward) biased. In other words, similar points would have further increased hash col- lision probability, while dissimilar points would have even lower chance of collision. This is the main reason that the empirical performance of KLSH is higher than theoretical prediction (where we assume independence) with short binary codes.
Slow improvement with large b. However, this is not the whole story. As more bits used, there less and less marginal information left. That is, the later generated codes would be more and more dependent on the previous ones. an extreme case, at the point when all (?)) combinations of the I points in X have been used, the hash codes produced afterwards would all be the same as some previously generated ones, which would hardly improve the distance estimation anymore. This is why for KLSH, the recall curve becomes flat as b increases.
16


Reviews:
[{"review_id": "uEgsZYWA1gp", "reviewer": "Reviewer_Mduj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The proposed ranking efficiency measure gives an objective measure of different Locality-Sensitive Hashing method.\n2. The proposed hashing method was able to surpass other method. It is impressive given the simple modification based on SQ-RFF;\n\n", "summary_of_the_paper": "This paper proposed an improved version of Random Fourier Feature (RFF) based binary feature coding method as well as a new measure(ranking efficiency) to compare different Locality-Sensitive Hashing (LSH) methods. Under the new measure, the proposed method is better than previous methods. The authors also validated by visualization the consistency between theoretical comparisons based the proposed measure and the empirical results.", "summary_of_the_review": "The author does a great job explaining the idea, concepts, procedures and experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZjPjljwgh_r", "reviewer": "Reviewer_tti8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The authors develop a simpler hashing function for binary coding, which removes the random shifting $\\xi$ compared with SQ-RFF. They further demonstrate the new hashing function is also locality-sensitive. \n\n2. The new proposed ranking efficiency looks interesting. The authors provide some insights from the perspective of distortion or order-preserving (actual distance in original space vs. hamming distance after hashing) to illustrate the formula of ranking efficiency. They also use extensive results to justify the correctness of their formula. \n\n3. The authors conduct comprehensive experiments to validate the effectiveness of SignRFF. \n\n4. The paper is well organized and easy to follow.\n\nCons:\n1. The critical concern of this paper is its contribution. The new hashing scheme SignRFF and the ranking efficiency make me feel like two separate works but combine together. Both of them lack further investigation and analysis. More details can be found from Points 2 & 3 below.\n\n2. After introducing the new hashing function SignRFF and showing its locality-sensitive property, the authors did not further investigate its property. Based on Equation 9, we can compute the new $p_1$ and $p_2$ for $\\rho_1$ and $\\rho_2$. Can they be amplified compared with the $p_1$ and $p_2$ from SQ-RFF? They argue the stochastic rounding introduces extra variance caused by $\\xi$, so can SignRFF reduce the variance? Can it reduce a lot or a little, or depend on other factors? \n\n3. The authors claim the LSH efficiency ($R = \\log p_1 / \\log p_2$) is based on a worst-case analytical bound, but the LSH efficiency is still trendy. More investigations and comprehensive comparisons between the LSH efficiency and ranking efficiency can make it more convincing. Therefore, it is interesting to show the LSH efficiency of LSH, KLSH, SQ-RFF, and Sign-RFF with respective to $c$, $\\rho$, and $\\gamma$, and analyze whether the observed pattern from Figure 1 is consistent with that of the LSH efficiency. \n\n4. In the experiments, since different methods use different LSH functions, their computation time may be quite different. As the query response time is important, can the authors also show the recall vs query time with respect to different b values? \n\nMinor Comments or Typos:\n1. In Figure 5, the recall vs. $\\gamma$ for the data set Mnist is missing. Can the authors also show this curve in Figure 5?\n\n2. In Page 5, the paragraph before Equation 11, \"namely, the ranking accuracy, that can better compare LSHs in practice\", \"ranking accuracy\" should be \"ranking efficiency\".\n\n3. In Page 6, the $\\hat{S}_y$ and $\\hat{S}_x$ in Equation 12 should be $\\hat{p}_y$ and $\\hat{p}_x$, respectively. \n\n\n", "summary_of_the_paper": "The paper revisits the binary hashing from Random Fourier Feature (RFF) for approximate nearest neighbor search. The authors propose a simple and effective RFF-based hashing method SignRFF and demonstrate its locality-sensitive property. They also introduce a new measure called ranking efficiency to evaluate the performance of different LSH methods theoretically. Extensive experiments on three real-life image data sets validate the effectiveness of SignRFF and the consistency of the ranking efficiency from theoretical evaluation.", "summary_of_the_review": "In summary, this work looks interesting, but the concern about the contribution (details in Cons 1,2,3) justifies my current rating. I am glad to increase my rating if the authors can solve my questions. Thanks. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LsFt24Emwc7", "reviewer": "Reviewer_TrWv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The proposed SignRFF is simple. It is a simplified version of SQ-RFF by taking out the random perturbation. \n2. A new measure called the ranking efficiency is proposed to measure the practical performance rather than the worst case performance of LSH methods. This measure makes sense to consider the probability of retrieving a wrong/reversed similarity ranking.\n3. The paper is well written and easy to follow.\n\nWeaknesses:\n1. The technical contribution is the comparison of different LSH methods with the new defined ranking efficiency measurement. While the ranking efficiency measure is computed with theoretical analysis and some approximations, the comparison is conducted empirically. Thus, I am concerned about the author's claim of this contribution to be theoretically comparison between LSH methods.\n2. While the experimental results in Sec 5.2 look good, the results in Sec 5.3 (Figure 6) suggest the proposed method falls behind the KLSH. Any explanation for such performance gap or solution to remedy the problem would make the experiments and conclusion convincing.\n3. The authors argue that using short codes (less than 128 bits) cannot achieve a desirable level of search accuracy for practical purposes. The authors show the variation of recall w.r.t different bits in Figure 3, but fail to show whether the studied bit length is the desirable one in practical situations. Also, the precision is expected to be reported in this study.\n\nMinor:\nThe \\hat{S} is not defined in (12)\nThere are research papers that study deep learning based hashing methods before 2019, such as \nDeep Hashing via Discrepancy Minimization, 2018\nSimultaneous feature aggregating and hashing for large-scale image search, 2017\nDeep supervised hashing for fast image retrieval, 2016\nSimultaneous feature learning and hash coding with deep neural networks, 2015\nSupervised hashing for image retrieval via image representation learning, 2014\nit's better to mention these works when introducing hashing with deep models.\n\n\n", "summary_of_the_paper": "In this paper, the authors propose a simple strategy to extract random Fourier feature based binary codes. The authors also propose a new measure, ranking efficiency, to compare the search accuracy over two datapoints for locality-sensitive hashing methods. Experiments are conducted on several image retrieval datasets to validate the effectiveness of the proposed SignRFF.", "summary_of_the_review": "My research experience is on design hashing for computer vision tasks and I am familiar with work on LSH.\nThe paper is overall well organized. The technical contribution is the derivation of the ranking efficiency measurement, which is lower than the bar of ICLR. There are some flaws as identified in the weaknesses.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "IiyI29_TSP", "reviewer": "Reviewer_3RfW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have the following concerns of the paper:\n\n* limited method novelty: the proposed method SignRFF (eq. (7)) simply replaces the stochastic rounding into a deterministic form. In the whole section 3, only Proposition 3.4 is new, which proves that SignRFF is also locality-sensitive.\n\n* The empirical observation \"the results also reveals that LSH-type methods are better than data-dependent and deep hashing methods when the code length is moderately large\" is not new as well, [1] has the exactly same, and comprehensive study.\n\n* The empirical performance of SignRFF is not very competitive against other LSH methods.\n\n* The adopted hamming ranking retrieval method is not very efficient. It'd be better to use hashing table(s) for evaluating retrieval performance.\n\n\n[1] A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search, TKDE\n\n\n\n", "summary_of_the_paper": "The paper improves RFF-based hashing methods, and verfies it empirically.", "summary_of_the_review": "Given the limited method novelty and empirical findings, I'd recommend a reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your submission to ICLR.

This paper considers binary hashing schemes, and makes two related contributions.  First, it analyzes a simple extension to SQ-RFF; second, it introduces and analyzes a novel metric for ranking called ranking efficiency.  Some experiments are also performed on standard data sets.

This is very much a borderline paper, and could go either way.  I took a close look at the paper to offer my opinions in addition to the reviewers.  The paper itself is well written and seems to be correct.  I do like the simplicity of the proposed SignRFF method as well as the ranking efficiency measure.  However, the contributions are somewhat limited, and it's in an area that hasn't seen much work in the last several years (this paper mainly builds off of methods from 10+ years ago).  Further, it doesn't seem that methods such as KLSH and SignRFF are used much in practice, so I don't know if this will have substantial impact.  So while it's a reasonably interesting paper with some nice insights, I think it falls just below the acceptance threshold for me.
Decision: Reject