Bio-Inspired Hashing for Unsupervised Similarity Search
Authors: Chaitanya K. Ryali
John J. Hopfield
Dmitry Krotov
Venue:  (2020)
Keywords: unsupervised learning
similarity search
neuroscience

Abstract: The fruit fly Drosophila's olfactory circuit has inspired a new locality sensitive hashing (LSH) algorithm, FlyHash. In contrast with classical LSH algorithms that produce low dimensional hash codes, FlyHash produces sparse high-dimensional hash codes and has also been shown to have superior empirical performance compared to classical LSH algorithms in similarity search. However, FlyHash uses random projections and cannot learn from data. Building on inspiration from FlyHash and the ubiquity of sparse expansive representations in neurobiology, our work proposes a novel hashing algorithm BioHash that produces sparse high dimensional hash codes in a data-driven manner. We show that  BioHash outperforms previously published benchmarks for various hashing methods. Since our learning algorithm is based on a local and biologically plausible synaptic plasticity rule, our work provides evidence for the proposal that LSH might be a computational reason for the abundance of sparse expansive motifs in a variety of biological systems. We also propose a convolutional variant BioConvHash that further improves performance.  From the perspective of computer science, BioHash and BioConvHash are fast, scalable and yield compressed binary representations that are useful for similarity search.

Under review as a conference paper at ICLR 2020
BIO-INSPIRED HASHING FOR UNSUPERVISED SIMI- LARITY SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
The fruit fly Drosophila's 's olfactory circuit has inspired new locality sensitive hash- ing (LSH) algorithm, Fl FlyHash. In contrast with classical LSH algorithms that produce low dimensional hash codes, FlyHash produces sparse high-dimennional hash codes and has also been shown to have superior empirical performance com- pared to classical LSH algorithms in similarity search. However, F FlyHash uses random projections and cannot learn from data. Building on inspiration from Fl "lyHast sh and the ubiquity of sparse expansive representations in neurobiology, our work proposes a novel hashing algorithm BioHash that produces sparse high dimensional hash codes data-driven manner. We show that Bi oHash outper- forms previously published benchmarks for various hashing methods. Since our learning algorithm based on a local and biologically plausible synaptic plasticity rule, our work provides evidence for the proposal that LSH might be computa- tional reason for the abundance sparse expansive motifs in a variety of biological systems. We also propose convolutional variant Bi Biooonvaal improves performance. From the perspective of computer science, BioHash and BicConviash are fast, scalable and yield compressed binary representations that are useful for similarity search.
that further
INTRODUCTION
Sparse expansive representations are ubiquitous in neurobiology. Expansion means that a high- dimensional input is mapped even higher dimensional secondary representation. Such expansion often accompanied by a sparsification of the activations: dense input data is mapped into a sparse code, where only small number of secondary neurons respond given stimulus.
classical example of the sparse expansive motif the Drosophila fruit fly olfactory system. In this case, approximately 50 projection neurons send their activities about 2500 Kenyon cells (Turner et al., 2008), thus accomplishing an approximately 50x expansion. An input stimulus typically activates approximately 50% of projection neurons, and less than 10% Kenyon cells (Turner et al., 2008), providing an example of significant sparsification of the expanded codes. Another example the rodent olfactory circuit. In this system, dense input from the olfactory bulb is projected into piriform cortex, which has 1000x more neurons than the number of glomeruli in the olfactory bulb. Only about 10% of those neurons respond given stimulus (Mombaerts et al., 1996). similar motif is found in rat's cerebellum and hippocampus (Dasgupta et al., 2017).
From the computational perspective, expansion is helpful for increasing the number of classification decision boundaries by simple perceptron (Cover, 1965) or increasing memory storage capacity in models of associative memory (Hopfield, 1982). Additionally, sparse expansive representations have been shown to reduce intrastimulus variability and the overlaps between representations induced by distinct stimuli (Sompolinsky, 2014). Sparseness has also been shown to increase the capacity of models of associative memory (Tsodyks & Feigelman, 1988).
The goal of the present work is to use this "biological" inspiration about sparse expansive motifs, well as local Hebbian learning, for designing novel hashing algorithm BioHash that can be used in similarity search. Below we describe the task, the algorithm, and demonstrate that Biollash improves retrieval performance common benchmark datasets.

---

Under review as a conference paper at ICLR 2020
Similarity search and LSH. In similarity search, given query q R similarity measure sim(g. 2), and a database E Raxd containing n items, the objective is to retrieve a ranked list of R items from the database most similar to q. When data is high-dimensional (e.g. images/documents) and the databases are large (millions or billions items), this is a computationally challenging problem. However, approximate solutions are generally acceptable, with Locality Sensitive Hashing (L.H)) being one such approach (Wang et al., 2014). Similarity search approaches maybe unsupervised or supervised. Since labelled information for extremely large datasets is infeasible to obtain, our work focuses on the unsupervised setting. In LSH (Indyk & Motwani, 1998; Charikar, 2002), the idea is to encode each database entry (and query 9) with a binary representation h(x) (h(q) respectively) and to retrieve R entries with smallest Hamming distances d (h(x). h(a)). Intuitively, (see (Charikar, 2002), for a formal definition), a hash function similar (dissimilar) items 21 and 22 are close by (far apart) in Hamming distance dæ (h(r1)) h((22)). LSH algorithms are of fundamental importance in computer science, with applications in similarity search, data compression and machine learning (Andoni & Indyk, 2008).
Rd - 1-1,1)m is said to be locality sensitive,
Drosophila olfactory circuit and Fly In classical LSH approaches, the data dimensionality d is much larger than the embedding space dimension m, resulting in low-dimensional hash codes (Wang et al., 2014; Indyk& & Motwani, 1998; Charikar, 2002). In contrast, a new family of hashing algorithms has been proposed (Dasgupta al., 2017) where m >> d. but the secondary representation is highly sparse with only a small number A of m units being active, see Figure 1. We call this algorithm F FlyHash in this paper, since is motivated by the computation carried out by the fly's olfactory circuit. The expansion from the d dimensional input space into an m dimensional secondary representation is carried out using random set of weights W (Dasgupta et al., 2017; Caron et al., 2013). The resulting high dimensional representation is sparsified by k- Winner--Takee Take-All (k- WTA) feedback inhibition in the hidden layer resulting in top 5% of units staying active (Lin et al., 2014; Stevens, 2016).
While 1 Flyassh uses random synaptic weights, sparse expansive representations are not necessarily random (Sompolinsky, 2014), perhaps not even in the case of Drosophila (Gruntman & Turner, 2013; Zheng et al., 2018). Moreover, using synaptic weights that are learned from data might help to further improve the locality sensitivity property of FlyHash. Thus, it is important to investigate the role of learned synapses on the hashing performance. A recent work SOLHash (Li et al., 2018), takes inspiration from FlyHash and attempts to adapt the synapses data, demonstrating improved performance over F FlyHash. However, every learning update step in SOLHash invokes constrained linear program and also requires computing pairwise inner-products between all training points, making it very time consuming and limiting its scalability to datasets of even modest size. These limitations restrict SOLHash to training only on small fraction of the data (Li et al., 2018). Additionally, SOLHash is biologically implausible (for an extended discussion, see Sec. 5). BioHash also takes inspiration from Fl FlyHash and demonstrates improved performance compared to random weights used in Fl Haahh, but it is fast, online, scalable and, importantly, Bi oHash is neurologically plausible.
m < d
m > d
k active ncurons
W
W
Figure 1: It is convenient to think about different hashing algorithms in terms of representational contraction (large dimension of input is mapped into smaller dimensional latent space), expansion (large dimensional input is mapped into an even larger dimensional latent space). The projections can be random or data driven.
Not only "biological" inspiration can lead to improving hashing techniques, but the opposite might also be true. One of the statements of the present paper is that BioHash satisfies locality sensitive property, and, at the same time, utilizes biologically plausible learning rule for synaptic weights (Krotov & Hopfield, 2019). This provides evidence toward the proposal that the reason why sparse expansive representations are so common in biological organisms is because they perform locality
2

---

Under review as a conference paper at ICLR 2020
sensitive hashing. In other words, they cluster similar stimuli together and push distinct stimuli far apart. Thus, our work provides evidence toward the proposal that LSH might be a fundamental computational principle utiliized by the sparse expansive circuits Fig. 1 (right). Importantly, learning of synapses must be neurobiologically plausible (the synaptic plasticity rule should be local).
Contributions. Building inspiration from FlyHash and more broadly the ubiquity of sparse, expansive representations in neurobiology, our work proposes a novel hashing algorithm Bi BioHash, sh, that in contrast with previous work (Dasgupta al., 2017: Li et al., 2018), produces sparse high dimensional hash codes in a data-driven manner and with learning of synapses in a neurobiologically plausible way. We provide an existence proof for the proposal that LSH maybe a fundamental computational principle in neural circuits (Dasgupta et al., 2017) in the context of learned synapses. We incorporated convolutional structure into oHash, resulting in a hashing with improved perfor- mance compared to previously published benchmarks. From the perspective of computer science, we show that BioHash is simple, scalable large datasets and demonstrates good performance for similarity search. Interestingly, BioHash outperforms a number of recent SOTA deep hashing methods trained via backpropogation.
2 APPROXIMATE SIMILARITY SEARCH VIA BIOHASHING
Formally, if we denote data point as I E Rd, we seek a binary hash code E (-1,1)" We define the hash length of binary code as k, if the exact Hamming distance computation is Ok)). Below we present our bio- bio-inspired hashing algorithm.
2.1 BIO-INSPIRED HASHING (BIOHASH)
We adopt a biologically plausible unsupervised algorithm for representation learning from Krotov & Hopfield (2019). Denote the synapses from the input layer to the hash layer as W E Rmdd The learning dynamics for the synapses of an individual neuron μ. denoted by Wyin is given by
dWpr μi
T
g Rank ( (W,r (z; - (W ()
(1)
dt
where W₁, = (Wud, ut, Ww2 W ma).. and
1,
glu|
/= r
(2)
0,
otherwise
and (z. (), =E,, The n.y,, with v/i, w where dg is Kronecker delta and is the time scale of the learning dynamics. The Rank operation in equation (1) sorts the inner products from the largest (μ = 1) to the smallest (μ = m². It can be shown that the synapses converge to a unit (p-norm) sphere (Krotov& & Hopfield, 2019). The training dynamics can be shown to minimize the following energy function
( xA M.
E E= ΣΣ
g Rank wr )n)]
(3)
(W p: W
where A indexes the training example. Note that the training dynamics do not perform gradient descent, i. Wr, + Ww, always negative (we show this for the case A = 0 below),
, E. However, time derivative of the energy function under dynamics (1) is
dE Σ dt
T(p 1)
dWR AA (W Wala - (Wa, (Wa,= x4) d
dWp dt
Wa)a
(Wa, W W
(4)
T(p 1)
= Σ
(0 )a Wa)a - (Wa, x 1/2 <0,
(Wa, Wp)
where Schwartz inequality used. For every training example A the index of the activated hidden unit is defined as
arg max [( (Wa, [))]
(5)
3

---

Under review as a conference paper at ICLR 2020
probability densily of the data
B
1/1
1/2
y/
* data point
O inactive unit (-1)
active unit (+1)
data
Figure 2: (Panel A) Distribution of the hidden units (red circles) for given distribution of the data (in one dimension). (Panel B) Arrangement of hidden units for the case of homogeneous distribution of the training data p = 1/(2x). For hash length & = 2 only two hidden units are activated (filled circles). If two data points close to each other (x: and y1) they elicit similar hash codes, if the two data points are far away from each other (æ: and y3) the hash codes are different.
Thus, the energy function decreases during learning. A similar result can shown for A o
After the learning-phase is complete, the hash code is generated. in F FlyHash, via WTA sparsifi- cation: for given query x we generate a hash code E { {-1, 1 as
( #) in top otherwise.
yy -1,
(6)
Thus, the hyperparameters of the method are m and A. Note that the synapses are updated based only on pre- and post-synaptic activations resulting in Hebbian or unti-Hebbian updates. Many "unsupervised" learning to hash approaches provide sort of "weak supervision" in the form of similarities evaluated in the feature space deep CNNs trained on ImageNet (Jin al., 2019) to achieve good performance. BioHash does not assume such information is provided and is completely unsupervised.
2.2 INTUITION BEHIND THE LEARNING ALGORITHM
An intuitive way think about the learning algorithm is to view the hidden units particles that are attracted to local peaks of the density of the data, and that simultancously repel each other. To demonstrate this, it is convenient to think about input data randomly sampled points from continuous distribution. Consider the case when p = 2 and A = O. In this case, the energy function can be written (since for p 2 the inner product does depend on the weights, we drop the subscript of the inner product)
E
(W (W ad
/
II dus Σ
8(:: x1²1
(Wa,
W
(Wa, Wa)
A
II dosp(v) (W v)
(W Way
where we introduced continuous density of data p(v). Furthermore, consider the case of 2, and imagine that the data lies unit circle. In this case the density of data can be parametrized by single angle sp Thus, the energy function can be written as
E= j dipp(s) cos(pp pa), where P arg max [cos((p ppp)
It is instructive to solve simple case when the data follows an exponential distribution concentrated around zero angle with the decay length (a a normalization constant),
lel
p(g) = ar
In this case, the energy (8) can be calculated exactly for any number of hidden units m. However, minimizing over the position of hidden units cannot be done analytically for general To further
4

---

Under review as a conference paper at ICLR 2020
simplify the problem consider the case when the number of hidden units m is small. For = 2 the energy is equal to
o (1 -(1+ 1
E
(o) + o sin((;)) + cos(pp2) - a sin
(10)
Thus, in this simple case the energy is minimized when
P1. = - arctan(())
(11)
In the limit when the density of data is concentrated around zero angle (a + 0) the hidden units are attracted to the origin and || R a. In the opposite limit (a - oo) the data points are uniformly distributed on the circle. The resulting hidden units are then organized be on the opposite sides of the circle | = 2. due to mutual repulsion.
Another limit when the problem can be solved analytically is the uniform density of the data 1/(2 for arbitrary number m of hidden units. In this case the hidden units span the entire circle homogeneously the angle between two consecutive hidden units is Ap- 2
These results are summarized in an intuitive cartoon in Figure 2, panel A. After learning is complete, the hidden units, denoted by circles, are localized the vicinity of local maxima of the probability density of the data. At the same time, repuisive force between the hidden units prevents them from collapsing onto the exact position of the local maximum. Thus the concentration of the hidden units near the local maxima becomes high, but, at the same time, they span the entire support (area where there is non-zero density) of the data distribution.
For hashing purposes, trying to find a data point "closest" to some new query q requires a definition of "distance". Since this measure is wanted only for nearby locations and x, it need not be accurate for long distances. If we pick set of reference points in the space, then the location of point can be specified by noting the few reference points it is closest to, producing a sparse and useful local representation. Uniformly tiling high dimensional space is not computationally useful approach. Reference points are needed only where there is data, and high resolution is needed only where there is high data density. The learning dynamics in I distributes m reference vectors by an iterative procedure such that their density is high where the data density is high, and low where the data density low. This exactly what needed for good hash code.
The case of uniform density on a circle is illustrated in Figure 2. panel B. After learning is complete the hidden units homogeneously span the entire circle. For hash length k: = 2, any given data point activates two closest hidden units. If two data points are located between two neighboring hidden units (like x and y/) they produce exactly identical hash codes with hamming distance zero between them (black and red active units). If two data points are slightly farther apart, like and 1/2 they produce hash codes that are slightly different (black and green circles, hamming distance is equal to in this case). If the two data points even farther, like and ya, their hash codes are not overlapping at all (black and magenta circles, hamming distance is equal to 4). Thus, intuitively similar data activate similar hidden units, resulting in similar representations, while dissimilar data result in very different hash codes.
2.3 COMPUTATIONAL COMPLEXITY AND METABOLIC COST.
In classical LSH algorithms (Charikar, 2002; Indyk & Motwani, 1998), typically, k == m and m < entailing a storage cost of & bits per database entry and O(k) computational cost to compute Hamming distance. In BioHash (and in F1 Haahh,, typically m >> l and m >> d entailing storage cost of k loga bits per database entry and ((k) computational cost to compute Hamming distance. Note that while there is additional storage/lookup overhead over classical LSH in maintaining pointers, this is not unlike the storage/lookup overhead incurred by quantization methods like Product Quantization (PQ) (Jégou et al., 2011), 1). which stores lookup table of distances between every pair of codewords for each product space. From neurobiological perspective, a highly sparse representation such as the one produced by BioHash keeps the same metabolic cost (Levy & Baxter, 1996) as a dense now-dimensional (m < d) representation, such as in classical LSH methods. At the same time, empirically show below, it better preserves similarity information.
IIf we maintain sorted pointers to the locations of 1s, we have to compute the intersection between 2 ordered lists of length k which is Ok))
5

---

Under review as a conference paper at ICLR 2020
Query
Top Retrievals
Figure 3: Examples of queries and top 15 retrievals using BioHash (A = 16) on VGG16 fc7 features of CIFAR-10. Retrievals have green (red) border if the image is in the same (different) semantic class as the query image. We show some success (top 4) and failure (bottom 2) cases. However, can be seen that even the fallure cases are reasonable.
Hash Length (k)
Method
8
16
32
64
LSH
12.45
13.77
18.07
20.30
26.20
32.30
PCAHash
19.59
23.02
29.62
26.88
24.35
21.04
FlyHash
18.94
20.02
24.24
26.29
32.30
38.41
SH
20.17
23.40
29.76
28.98
27.37
24.06
ITQ 21.94
28.45
38.44
41.23
43.55
44.92
DH
43.14
44.97
46.74
UH-BNN 25.85
45.38
47.21
NaiveBicHare
29.83
28.18
31.69
36.48
38.50
BioHash 44.38
49.32
53.42
54.92
55.48
BioConvHash 64.49
70.54
77.25
80.34
81.23
Table 1: mAP@ All (%) on MNIST (higher better). Best results (second best) for each hash length are in bold (underlined). BioHash demonstrates the best retrieval performance, substantially outperforming other methods including deep hashing methods DH and UH-BNN, especially at small Performance for DH and JH-BNN is unavailable for some k. since it is not reported in the literature.
2.4 CONVOLUTIONAL BIOHASH
In order to take advantage of the spatial statistical structure present in images, we use the dynamics in I to learn convolutional filters by training on image patches as Grinberg et al. (2019). Convolutions in this case unusual since the patches of the images are normalized to be unit vectors before calculating the inner product with the filters. Differently from Grinberg et al. (2019), we use cross channel inhibition suppress the activities of the hidden units that weakly activated. Specifically. there are convolutional filters, then only the top kc of activations are kept active per spatial location.
Patch normalization reminiscent of the canonical computation of divisive normalization (Carandini & Heeger, 2011) 1) and performs local intensity normalization. This is not unlike divisive normalization in the fruit fly's projection neurons. Divisive normalization has also been found to be beneficial (Ren et al., 2016) in CNNs trained end-to-end by the backpropogation algorithm task. We found that the cross channel inhibition is important for a good hashing performance. Post cross-channel inhibition, we use max- max-pooling layer, followed by Bi oHash layer as in Sec. 2.1.
supervised

---

Under review as a conference paper at ICLR 2020
Hash Length (k)
Method
2
4
8
16
32
64
LSH
11.73
12.49
13.44
16.12
18.07
19.41
PCAHash
12.73
14.31
16.20
16,81
17.19
16.67
FlyHash
14.62
16.48
18.01
19.32
21.40
23.35
SH
12.77
14.29
16.12
16.79
16.88
16.44
ITQ 12.64
14.51
17.05
18.67
20.55
21.60
NaiveBicHash
11.79
12.43
14.54
16.62
17.75
18.65
BioHash
20.47
21.61
22.61
23.35
24.02
oConvHash
26.94
27.82
29.34
29.74
30.10
Table 2: mAP@ 1000 (%) CIFAR-10 (higher is better). Best results (sccond best) for each hash length are in bold (underlined). BioHash demonstrates the best retrieval performance, especially at small k.
SIMILARITY SEARCH
In this section, empirically evaluate BioHash, investigate the role of sparsity in the latent space, and compare our results with previously published benchmarks. We consider two settings for evaluation: the training set contains unlabeled data, and the labels are only used for the evaluation of the performance of the hashing algorithm and b) where supervised pretraining on a different dataset permissible. Features extracted from this pretraining are then used for hashing. both settings BioHash outperforms previously published benchmarks for various hashing methods.
3.1 EVALUATION METRIC
Following previous work (Dasgupta et al., 2017; Li et al., 2018; Su al., 2018), Mean Average Precision (mAP) as the evaluation metric, a measure that averages precision over different recall. Specifically, given query set Q, evaluate mAP@ as
Q
mAP@R
Precision(!)Rel(().
(12)
Rel(()
where R number of retrievals, Rel(() (document is relevant) and Precision(I) is the precision of the top retrievals. Notation: when R is equal to size the entire database, i.e ranking of the entire database is desired, use the notation mAP@ All simply mAP, dropping the reference R.
3.2 DATASETS AND PROTOCOL
To make our work comparable with recent related work, used common benchmark datasets: a) MNIST (Lecun et al., 1998), dataset of 70k grey-scale images (size 28 x 28) hand-written digits with 10 classes of digits ranging from "0" to "9", b) CIFAR-10 (Krizhevsky, 2009), dataset containing 60k images (size 32x32x3) from 10 classes (e.g: car, bird).
Following the protocol in Lu al. (2017); Chen al. (2018), MNIST we randomly sample 100 images from each class to form a query set of 1000 images. We use the rest of the 69k images as the training set for BioHash
well as the database for retrieval post training. Similarly, on CIFAR-10. following previous work (Su et al., 2018; Chen et al., 2018; Jin, 2018), we randomly sampled 1000 images per class to create a query set containing 10k images. The remaining 50k images were used for both training as well as the database for retrieval as in the case of MNIST. Ground truth relevance for both dataset is based on class labels. Following previous work (Chen et al., 2018: Lin et al., 2015; Jin et al., 2019). we use mAP @ 1000 for CIFAR- 10 and mAP@ All for MNIST. It is common to benchmark the performance of hashing methods at hash lengths k E {16, 32, 64). However, observed in Dasgupta al. (2017) 7) that the regime in which F FlyHash outperformed LSH was in the regime of low hash lengths & E {2, 4, 16, 32}. Accordingly, we evaluate performance for (2, 4, 8, 16, 32, 64).

---

Under review as a conference paper at ICLR 2020
MNIST
CIFAR-10
55
24
MAP@AI (%)
22
MAP @Ap@1000
45
k=2
20
40
k=4
k=8
18
35
k=16
k-16
k=32
k-32
16
30
0.25
1.0
10.0
20.0
Activity (%)
Activity (%)
Figure 4: Effect of varying sparsity (activity): optimal activity % for MNIST and CIFAR-I0 are 5% and 0.25%. Since the improvement in performance is small from 0.5 % 0.25 %, we use 0.5% for CIFAR-10 experiments. The change of activity is accomplished by changing m at fixed k.
3.3 BASELINES
As baselines we include random hashing methods FlyHash (Dasgupta et al., 2017), classical LSH (LSH (Charikar, 2002)), and data-driven hashing methods PCAHash (Gong & Lazebnik, 2011),
Spectral Hashing (SH (Weiss et al., 2009)), Iterative Quantization (ITQ (Gong & Lazebnik, 2011)). As in Dasgupta et al. (2017), for F FlyHash we set the sampling rating from PNs KCs to be 0.1 and m = 10d. Additionally, where appropriate, we also compare performance of Bi Biohash to deep hashing methods: DeepBit t (Lin et al., 2015), DH (Lu al., 2017), USDH (Jin al., 2019), BNN (Do et al., 2016). SAH (Do et al., 2017) and GreedyHash (Su et al., 2018). As previously discussed, in nearly all similarity search methods, a hash length of l entails a dense representation using units. In order to clearly demonstrate the utility of sparse expansion in Bi oHa sh, we include a baseline (termed "Na veB i oHash"), which uses the learning dynamics in but without sparse expansion, i. the input data is projected into a dense latent representation with & hidden units. The activations of those hidden units are then binarized to generate a hash code of length k.
3.4 RESULTS AND DISCUSSION
The performance of BioHash on MNIST is shown in Table 1. BioHash demonstrates the best retrieval performance, substantially outperforming other methods, including deep hashing methods DH and UH-BNN, especially at small k. Indced, even at very short hash length of k = 2, the performance of BioHs is comparable to or better than DH for k E {16, 32), while at k = 4, the performance of RioHash sh is better than the DH and UH-BNN for 1 {16, 32, 64). The performance of Bi BioHash saturates around k = 16, showing only a small improvement from k = 8 to k = 16 and 32; accordingly, we do not evaluate performance
an even smaller improvement from k 16 at k = 64. We note that while SOLHash also evaluated retrieval performance on MNIST and is a data-driven hashing method inspired by Drosophila's 's olfactory circuit, the ground truth in their experiment was top 100 nearest neighbors of query in the database, based on Euclidean distance between pairs of images in pixel space and thus cannot be directly compared Nevertheless, we adopt that protocol (Li et al., 2018) 2018) and show that Bi BioHash substantially outperforms SOLHash in Sec 5.
The performance of BioHash CIFAR- 10 is shown in Table 2. Similar to the case of MNIST, BioHash demonstrates the best retrieval performance, substantially outperforming other methods, especially at small A. Even at l (2, 4), the performance of B oHash is comparable to other methods with & E {16, 32, 643. This suggests that BioHash is a particularly good choice when short hash lengths are required.
Effect of sparsity For a given hash length k, we parametrize the total number of neurons m in the hash layer as m = k. where the activity i.e the fraction of active neurons. For each hash length k we varied % of active neurons and evaluated the performance on a validation set
Due to missing values of the hyperparameters unable to reproduce the performance of S01.Hash to enable direct comparison.
8

---

Under review as a conference paper at ICLR 2020
Activity (%) 1.0
Activity (%).: 5.0
Activity (%) 20.0
Activity (%). 70.0
Figure 5: ISNE embedding of MNIST as the activity is varied for fixed 160 (the change of activity is accomplished by changing at fixed m). When the sparsity of activations decreases (activity increases), some clusters merge together, though highly dissimilar clusters (e.g. orange and blue in the lower left) stay separated.
Hash Length (k)
Hash Length (A)
kc1
2
4
8
16
kci
2
4
8
16
56.
66.23
71.20
73.41
1
26.94
27.82
29.34
29.74
5
58.13
70.88
75.92
79.33
5
24.92
25.94
27.76
28.90
10
64.49
70.54
77.25
80.34
10
23.06
25.25
27.18
27.69
25
56.52
64.65
68.95
74.52
25
20.30
22.73
24.73
26.20
100
23.83
32.28
39.14
46.12
100
17.84
18.82
20.51
23.57
Table 3: Effect of Channel Inhibition. Left: mAP@ All (%) MNIST, Right: mAP@ 1000 (%) on CIFAR-IO. The number active channels per spatial location is denoted by kcn- can seen that channel inhibition (high sparsity) is critical for good performance. Total number of available channels for each kernel size was 500 and 400 for MNIST and CIFAR- respectively.
(see appendix for details), Figure 4. There is optimal level of activity for each dataset. For MNIST and CIFAR-10, a was set to 0.05 and 0.005 respectively for all experiments. We visualize ISNE embeddings for different settings of activity levels in Figure Interestingly, lower sparsity levels, dissimilar images may become nearest neighbors though highly dissimilar images stay apart. This is reminiscent of an experimental finding (Lin al., 2014) Drosophila. Sparsification of Kenyon cells in Drosophila is controlled by feedback inhibition from the anterior paired lateral neuron. Disrupting this feedback inhibition leads denser representations, resulting in fruit flies being able to discriminate between dissimilar odors but not similar odors.
Convolutional BioHash the case of MNIST, we trained 500 convolutional filters (as described in Sec. 2.4) of kernel sizes K 3, 4. In the case of CIFAR-10, we trained 400 convolutional filters kernel sizes K = 3, and 10. The convolutional variant of Biahssh, which we call BioConvHash shows further improvement even small hash lengths e {2.4] 4} substantially outperforming other methods at larger hash lengths. Channel Inhibition is critical for performance of B BiooovHassh across both datasets, Table 3. high amount of sparsity is essential for good performance. As discussed previously discussed, convolutions in our network are atypical in yet another way, due to patch normalization. We show in Sec 6, that patch normalization results in robustness of BioConvHash to "shadows", a robustness also characteristic of biological vision.
BioHash on MNIST well CIFAR-10, with
Hashing using deep CNN features State-of-the-ar hashing methods generally adapt deep CNNs trained on ImageNet (Su al., 2018; Jin et al., 2019; Chen al., 2018; Lin al., 2017). These approaches derive large performance benefits from the semantic information learned in pursuit of the classification goal on ImageNet (Deng et al., 2009). To make fair comparison with our work, we trained Bi BioHash on features extracted from fc7 layer of VGG16 (Simonyan & Zisserman, 2014), since previous work (Su et al., 2018; Lin et al., 2015; Chen et al., 2018) has often adapted this pre-trained network. BioHash demonstrates substantially improved performance over recent deep unsupervised hashing methods with mAP 1000 of 63.47 for k = 16; example retrievals are shown in Figure 3. Even at very small hash lengths of lo E {2, 4). BioHash outperforms other methods at E { {16,35 32, 64). For performance of other methods and performance at varying hash lengths see Table 4.

---

Under review as a conference paper at ICLR 2020
Hash Length (k)
Method
8
16
32
64
LSH
13.25
17.52
25.00
30.78
35,95
44.49
PCAHash'
21.89
31.03
36.23
37.91
36.19
35.06
FlyHash'
25.67
32.97
39.46
44.42
50.92
54.68
SH"
22.27
31.33
36.96
38.78
39.66
37.55
ITQ"
23.28
32.28
41.52
47.81
51.90
53.84
DeepBit
19.4
24.9
27.7
USDH
26.13
36.56
39.27
SAH 10.56
41.75
45.56
47.36
GreedyHash
23,94
34.32
44.8
47.2
50.1
NaiveBioHash"
18.24
26.60
31.72
35.40
40.88
44.12
BioHaash'
57.33
59.66
61.87
63.47
64.61
Table 4: mAP@1000 (%) on CIFAR-IOCNN. Best results (second best) for each hash length in bold (underlined). BioHash demonstrates the best retrieval performance, substantially outperforming other methods including deep hashing methods GreedyHash, SAH, feepBit and USDH, especially small k. Performance for DeepBit.SAH and USDH unavailable for some k. since it is not reported in the literature. denotes the corresponding hashing method using representations from VGG16 fc7.
It is worth remembering that while exact Hamming distance computation is O(k) for all the methods under consideration, unlike classical hashing methods, Biollssh (and also FlyHash) incurs a storage cost of & log, m instead of & per database entry. In the case of MNIST (CIFAR-10), BioHlash at k = 2 corresponds to m = 40 (m = 400) entailing a storage cost of 12 (18) bits respectively. Even in scenarios where storage is limiting factor, B Biohash l: 2 compares favorably to other methods at = 16, yet Hamming distance computation remains cheaper for BioHash.
4 CONCLUSIONS, DISCUSSION, AND FUTURE WORK
Inspired by the recurring motif of sparse expansive representations in neural circuits, we introduced new hashing algorithm, BioHash.. In contrast with previous work (Dasgupta al., 2017; ; Li et al., 2018), BioHash both a data-driven algorithm and has reasonable degree of biological plausibility. BioHash demonstrates strong empirical results outperforming recent unsupervised deep hashing methods. The biological plausibility of our work provides support toward proposal that LSH might be general computational function (Valiant, 2014) of the neural circuits featuring sparse expansive representations. From the perspective of computer science BioHash is easy to train and scalable to large datasets.
Compressed sensing/sparse coding have also been suggested as computational roles of sparse expan- sive representations in biology (Ganguli Sompolinsky, 2012). These ideas, however, require that the input be reconstructable from the sparse latent code. This is much stronger assumption than LSH downstream tasks might not require such detailed information about the inputs, e.g. novelty detection (Dasgupta et al., 2018).
In this work, we limited ourselves linear sean using fast Hamming distance computation for image retrieval, like much of the relevant literature (Dasgupta et al., 2017; Su et al., 2018; Lin et al., 2015; Jin, 2018). Yet, there is potential for improvement. One line of future inquiry would be to speed up retrieval using multi-probe methods, perhaps via psuedo-hashes (Sharma & Navlakha, 2018). Another line of inquiry would be to adapt BioHash for Maximum Inner Product Search (Shrivastava & Li, 2014; Neyshabur & Srebro, 2015).
REFERENCES
Alexandr Andoni and Piotr Indyk. Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. Commun. ACM, 51()):11--122, January 2008. ISSN 0001-0782, doi: 10.1145/1327452. 1327494.
Matteo Carandini and David J. Heeger. Normalization canonical neural computation. Nature reviews. Neuroscience, 13(1):51-62, November 2011. ISSN 1471-003X. doi: 10. 1336
10

---

Under review as a conference paper at ICLR 2020
Sophie J. C. Caron, Vanessa Ruta, L. Abbott, and Richard Axel. Random convergence of olfactory inputs in the Drosophila mushroom body, Nature, 497(7447):1113 117, May 2013, ISSN 1476-4687. doi: 10.1038/ naturel 2063.
Moses Charikar. Similarity Estimation Techniques from Rounding Algorithms. Proceedings of Thiry- Phiry-Fourth Annual ACM Symposium on Theory of Compuring, STOC '02, pp. 380-388, New York, NY, USA, 2002. ACM. ISBN 978-1-581138 13--8197-
doi: 10.1 145/5099977 5509665.
Junjie Chen, William K. Cheung, and Anran Wang. Learning Deep Unsupervised Binary Codes Image Retrieval, In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pp. 613-619, Stockholm, Sweden, July 2018. International Joint Conferences on Artificial Intelligence Organization. ISBN 778-0-9992411-2-9 doi: 20111
Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions on electronic computers, (3):326-334, 1965.
Sanjoy Dasgupta, Charles F Stevens, and Saket Navlakha. A neural algorithm for fundamental computing problem. Science, pp. 2017.
Sanjoy Dasgupta, Timothy C. Sheehan, Charles F. Stevens, and Saket Navlakha. A neural data structure for novelty detection. Proceedings of the National Academy of Sciences, 115(51):13093 13098, December 2018. ISSN 0027-8424, 1091-6490. doi: 10.1073/pnas. 18tpppaas..8844811111 1814448115.
Jia Deng, Wei Dong, Richard Socher, Li-jia Li, Kai Li, and Li Fei-fei. Imagenet: A large-scale hicrarchical image database.
CVPR, 2009.
T. Do. D. L. Tan, T. T. Pham, and N. Cheung. Simultaneous Feature Aggregating and Hashing for Large- Scale Image Scarch. In 2017 JEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4217-4226, July 2017. doi: 10. 1099/CPR..007..444
Thanh- Do, Anh anh-Dzung Doan, and Ngai-Man Cheung. Learning to hash with binary deep neural network. In European Conference on Computer Vision, pp. 219-234. Springer, 2016.
Surya Ganguli and Haim Sompolinsky. Compressed sensing, sparsity, and dimensionality neuronal information processing and data analysis. Annual review of neuroscience, 35:485-508 508, 2012. doi: 10.1 466/anmuree-nnuooo06656 111-11111111000
Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR 20 pp. 817-824, Colorado Springs, CO, USA, June 2011. IEEE. ISBN 978-1-4577-0334-2 doi: 10.1109/CVPR.201 1,5995432.
Leopold Grinberg, John Hopfield, and Dmitry Krotov. Local Unsupervised Learning for Image Analysis.
arXiv: 08993 [cs, q-bio, stat], August 2019.
Eyal Gruntman and Glenn C. Turner. Integration of the olfactory code across dendritic claws of single mushroom body neurons. Nature Neuroscience, (6(12):1821-1 December 2013. ISSN 1546-1726. doi: 10. 1038/nn.3547.
J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceed- ings the National Academy of Sciences, (9(8):255422555 April 1982. ISSN 0027-8424, 1091-6490. doi: 10. 10.1073/pnas.77 7.2544..
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality, In Proceedings of Thirtieth Annual ACM Symposium on Theory of Computing - STOC '98. pp. 604-613, Dallas, Texas, United States, 1998. ACM Press. ISBN 978-0-897991-62-3.
doi: 10.1145/276688.276
Sergey loffe and Christian Szegedy. Batch Normaiizaiin: Accelerating Deep Network Training by Reducing Internal Covariate Shift. prXiv:1502. 502.03367 [cs], February 2015.
Jégou, M Douze, and C Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117-128, January 2011. ISSN 0162-8828. doi: 10. 10.1009/PAM..2000...7.
Sheng Jin, Unsupervised Semantic Deep Hashing. 0rX3v: [es], March 2018.
Sheng Jin, Hongxun Yao, Xiaoshuai Sun, Shangchen Zhou. Unsupervised semantic deep hashing. Newro- computing, 351:19-25, July 2019. ISSN 0925-2312. doi: n0.10166j.eeucmm.2011 wtt.co..m..9.00.002
Alex Krizhevsky. Leaming Multiple Layers of Features from Tiny Images. Technical report, 2009.

---

Under review as a conference paper at ICLR 2020
Alex Krizhevsky. Ilya Sutskever, and Geoffrey Hinton. ImageNet Classification with Deep Convolutional Neural Networks. In F. Pereira, C. J. C. Burges, Bottou, and K. Q. Weinberger (eds.), Advances Neural Information Processing Systems 25, pp. (097-1105. Curran Associates, Inc., 2012.
Dmitry Krotov John J. Hopfield. Unsupervised learning by competing hidden units. Proceedings of the National Academy of Sciences, 116(16))723--7731 April 2019. ISSN 0027-8424, 1091-6490, doi: 10. 10.1073/pna.. 1820458116.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, November 1998. ISSN 0018-9219 doi: 10. 109979997..6691.
W. B. Levy and R. A. Baxter. Energy efficient neural codes. Neural Computation, 8(3):531-54) April 1996. ISSN 0899-7667.
Wenye Li, Jingwei Mao, Yin Zhang, and Shuguang Cui. Fast Similarity Search via Optimal Sparse Lifting. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 776-184 Curran Associates, Inc., 2018
Andrew Lin, Alexei M Bygrave, Alix de Calignon. Tzumin Lee, and Gero Miesenböck. Sparse, decorrelated odor coding in the mushroom body enhances learned odor discrimination. Nature Neuroscience, 17(4): 459-568, April 2014. ISSN 1097-6256, 1726.176. doi: 10. 10.1038/mn.666.
Jie Lin, Zechao Li, and Jinhui Tang. Discriminative Deep Hashing for Scalable Face Image Retrieval. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pp. 2266-2272, Melbourne, Australia, August 2017. International Joint Conferences Artificial Intelligence Organization. ISBN 11--0-9999411---33 doi: 2,224666iccii22217/3355
Kevin Lin, Huci-Fang Yang, Jen-Hao Hsiao, and Chu-Song Chen. Deep learning of binary hash codes for fast image retrieval. In 2015 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 27-35, Boston, MA, USA, June 2015. IEEE, ISBN 978-1-4673-6759-22 doi: 10.1 N0.1109/CVP..2205.. 7301269.
Jiwen Lu, Venice Erin Liong, and Jie Zhou, Deep hashing for scalable image search. IEEE transactions on image processing, 26(5):2352-2366 2017.
Peter Mombaerts, Fan Wang. Catherine Dulac, Steve K Chao, Adriana Nemes, Monica Mendelsohn, James Edmondson, and Richard Axel. Visualizing an Olfactory Sensory Map. Cell, 8744)6675-666, November 1996.
ISSN 0092-8674. doi: 00.101650092-86744000 138722.
Behnam Neyshabur and Nathan Srebro. On Symmetric and Asymmetric LSHs for Inner Product Scarch. pp. 2015.
Mengye Ren, Renjie I Liao, Raquel Urtasun, Fabian Sinz, and Richard Zemel. Normalizing the Normal- izers: Comparing and Extending Network Normalization Schemes. International Conference on Learning Representations, 2016.
Jaiyam Sharma and Saket Navlakha. Improving Similarity Scarch with High- locality-sensitive Hashing, arXiv: 1812.01844 [cs, stat/, December 2018.
Aushumali Shrivastava and Ping Li. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances Neurul Information Processing Systems 27, pp. 2321-2329 Curran Associates, Inc., 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks large-scale image recognition. arXiv preprint arXiv:1409. /556, 2014.
Babadi Sompolinsky. Sparseness and Expansion in Sensory Representations. Neuron, 1315:11233 September 2014. ISSN 08966273. doi: n0.10166..euuro.2014.0000
Charles F. Stevens. A statistical property of fly odor responses is conserved across odors. Proceedings of the National Academy of Sciences, 133(2))6777-6772 June 2016. ISSN 0027-8424, 1091-6490, doi: 10. 10711003s.. 100333911.
Shupeng Su, Chao Zhang, Kai Han, and Yonghong Tian. Greedy hash: Towards fast optimization for accurate hash coding in CNN. In Advances in Neural Information Processing Systems, pp. 798 807, 2018
Mikhail V. Tsodyks and Mikhail V. Feigelman. The enhanced storage capacity in neural networks with low activity level. EPL. (Earophysics Letters), 6(2):101, 1988.
12

---

Under review as a conference paper at ICLR 2020
Glenn C. Turner, Maxim Bazhenov, and Gilles Laurent. Offactory representations Drosophila mushroom body neurons. Journal of neurophysiology, 99(2):334-746 2008.
Leslie G Valiant. What must global theory of cortex explain? Current Opinion in Neurobiology, 25:15-19.
April 2014. ISSN 09594388. doi: n..10166..comb.213111.0m
Jingdong Wang. Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for Similarity Search: A Survey. arXiv:1408. 2927 [es], August 2014.
Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral Hashing. In D. Koller, D. Schuurmans, Y. Bengio, and Bottou (eds.). Advances in Neural Information Processing Systems 21, pp. 1753-1760. Curran Associates, Inc., 2009.
Erkun Yang. Cheng Deng. Tongliang Liu, Wei Liu, and Dacheng Tao. Semantic Structure- based Unsupervised Deep Hashing. In Proceedings of the Twenty-Seventl International Joint Conference on Artificial Intelligence. Stockholm, Sweden, July 2018, International Joint Conferences on Artificial Intelligence doi: 10.24963/ijcai. 2018/1488
pp.
Organization, ISBN 978-0-999241 1 1-2-7,
Zhihao Zheng, J. Scott Lauritzen, Eric Perlman, Camenzind G. Robinson, Matthew Nichols, Daniel Milkie, Omar Torrens, John Price, Corey B. Fisher, Nadiya Sharifi, Steven A. Calle-Schuler, Lucia Kmecova, Iqbal J. Ali, Bill Karsh, Eric T. Trautman, John A. Bogovic, Philipp Hanslovsky, Gregory S.X.E. Jefferis, Michael Kazhdan, Khaled Khairy, Stephan Saalfeld, Richard Fetter, and Davi D. Bock. A Complete Electron Microscopy Volume of the Brain of Adult Drosophila melanogaster. Cell, 174(3) July 2018.
ISSN 00928674, doi: 10. 10.1016/f.cell. 2018..00000.060001.
13

---

Under review as a conference paper at ICLR 2020
SUPPLEMENTARY MATERIAL
We expand on the discussion of related work in section 5. We also include here some additional results. In section 6, we show that BioConvHash enjoys robustness to intensity variations. In section 7, we show that the strong empirical performance of BioHash is not specific to the choice of VGG16. Finally, we include technical details about implementation and architecture section 8.
5 APPENDIX A: RELATED WORK
Sparse High- Sigg--Dimeniin Representations in Neuroscience. Previous work has explored the nature of sparse high-dimensional representations through the lens of sparse coding and compressed sensing (Ganguli & Sompolinsky, 2012). Additionally, Sompolinsky (2014) has examined the computational role of sparse expansive representations in the context of categorization of stimuli as appetitive aversive. They studied the case of random projections as well as structur"" projections. However, structured synapses were formed by a Hebbian-like association between each cluster center and a corresponding fixed, randomly selected pattern from the cortical layer; knowledge of cluster centers provides a strong form a "supervision" "/additional information, while BioHash does not assume access such information. To the best of our knowledge no previous work has systematically examined the proposal that LSH maybe computational principle in the brain in the context of structured synapses learned biologically plausible manner.
Classical LSH. A classic LSH algorithm for angular similarity is SimHash (Charikar, 2002), which produces hash codes by h(x) sign(WTz>) where entries of W mmd are i.i.d from standard normal distribution and sign() is element-wise. While LSH is property and consequently sometimes used to refer to hashing methods in general, when the context is clear we refer to SimHash as LSH following previous literature.
Fruit Fly inspired LSH. The fruit fly's olfactory circuit has inspired research into new families (Dasgupta et al., 2018; Sharma & Navlakha, 2018: Li et al., 2018) of Locality Sensitive Hashing (LSH) algorithms. Of these, F FlyHash (Dasgupta et al., 2017) and DenseFly (Sharma & Navlakha, 2018) based random projections and cannot learn from data. Sparse Optimal Lifting (sOLHash) (Li et al., 2018) is based on learned projections and results in improvements in hashing performance.
SOLHash attempts to learn sparse binary representation Y Raxm by optimizing
arg min YE[-1,1juxm (=m=(-m-2k)em
-XXT-YYTI +1|lY1Ip
(13)
em is an all I's vector of size m. Note the relaxation from a binary Y E {-1,, 1) faxm continuous E [- nxxm After obtaining a Y. queries are hashed by learning linear map from X to Y by minimizing
arg min
| - XWI B|[
(14)
WeJ Wej=(-m-2oje...
Here, e is the # of synapses with weight 1; the rest are -1 To optimize this objective, Li et al. (2018) resorts to Franke-Woid optimization, wherein every learning update involves solving constrained linear program involving all of the training data, which biologically unrealistic. In contrast, Bi cHah is neurobiologically plausible involving only Hebbian/Ani inhibition.
updates and
From a computer science perspective, the scalability of SOLHash is highly limited; not only does every update step invoke a constrained linear program but the program involves pairwise similarity matrices, which can become intractably large for datasets of even modest size. This issue is further exacerbated by the fact that m >> d and YYT recomputed at every step (Li et al., 2018). Indeed, though Li et al. (2018) uses the SIFTIM IM dataset, the discussed limitations limit training to only 5% of the training data. Nevertheless. we make a comparison to SOLHash in Table 5 and see that BioHash results in substantially improved performance.
Deep LSH. A number of state-of-the-at approaches (Su et al., 2018; Jin, 2018; Do et al., 2017; Lin et al., 2015) to unsupervised hashing for image retrieval are perhaps unsurprisingly, based on deep CNNs trained on ImageNet Deng et al. (2009); A common approach (Su et al., 2018) to adopt pretrained DCNN backbone, replace the last layer with custom hash layer and objective
14

---

Under review as a conference paper at ICLR 2020
Hash Length (k)
Method
4
16
32
64
BioHash 39.57
54.40
65.53
73.07
77.70
80.75
SOLHash
11.59
20.03
30.44
41.50
51.30
Table 5: mAP@ 100 (%) on MNIST, using Euclidean distance in pixel space as the ground truth, following protocol in Li al. (2018). BioHash demonstrates the best retrieval performance, substantially outperforming SOLHash.
Figure 6: Examples of images with and without "shadow". We modified the intensities in the query set of CIFAR-10 10 by multiplying 80% of each image by a factor of 0.3; such images largely remain discriminable to human perception.
function and to train the network by backpropogation. Some other approaches (Yang al., 2018), use DCNNs as feature extractors or to compute measure of similarity in it's feature space, which then used as a training signal. While deep hashing methods are not the purpose of work, include them here for completeness.
APPENDIX B: ROBUSTNESS OF BIOCONVHASH TO VARIATIONS IN INTENSITY
Patch normalization is reminiscent the canonical neural computation of divisive normalization (Carandini & Heeger, 2011) and performs local intensity normalization. This makes BioConvHash robust to variations in light intensity. To test this idea, we modified the intensities the query set of CIFAR-10 10 by multiplying 80% of each image by factor of 0.3; such images largely remain discriminable human perception, see Figure 6. We evaluated the retrieval performance this query set with "shadows", while the database (and synapses) remain unmodified. We find that BioConvHash performs best at small hash lengths, while the performance of other methods except GreedyHash is almost at chance. These results suggest that maybe beneficial to incorporate divisive normalization into DCNNs architectures to increase robustness to intensity variations.
Hash Length (k)
Method
2
4
8
16
32
64
LSH
10.62
11.82
11.71
11.25
11.32
11.90
PCAHash
10.61
10.60
10.88
11.33
11.79
11.83
FlyHaash
11.44
11.09
11.86
11.89
11.45
11.44
SH
10.64
10.45
10.45
11.70
11.26
11.30
ITQ 10.54
10.68
11.65
11.00
10.95
10.94
BioHash
11.05
11.50
11.57
11.33
11.59
Bi oConvHash
26.84
27.60
29.31
29.57
29.95
GreedyHash 10.56
21.47
25.21
30.74
30.16
37.63
Table 6: Robustness to shadows. mAP@ @ 1000 (%) on CIFAR-10 (higher is better). when query set has "shadows". Performance of other hashing methods drops substantially, while the performance of BioConvHash remains largely unchanged due to patch normalization. For small k. Bi BioConvHase substantially outperforms all the other methods, while still being competitive at higher hash lengths. Best results (second best) for each hash length are in bold (underlined).
15

---

Under review as a conference paper at ICLR 2020
7 APPENDIX C: EVALUATION USING VGGI6BN AND ALEXNET
The strong empirical performance of BicHash using features extracted from VGG16 fc7 is not specific to choice of VGGI6. To demonstrate this, we evaluated the performance of BioHash using VGG16 with batch normalization (BN) (Ioffe & Szegedy, 2015) as well as AlexNet (Krizhevsky al., 2012). Consistent with the evaluation using VGG16 reported in the main paper, BioHash consistently demonstrates the best retrieval performance, especially at small k.
Hash Length (k)
Method
2
4
8
16
32
64
LSH
13.16
15,86
20.85
27.59
38.26
47.97
PCAHash
21.72
34.05
38.64
40.81
38.75
36.87
FlyHash
27.07
34.68
39.94
46.17
52.65
57.26
SH
21.76
34.19
38.85
41.80
42.44
39.69
ITQ
23.02
34.04
44.57
51.23
55.51
58.74
BioHash
60.56
62.76
65.08
66.75
67.53
Table mAP@ 1000 (%) on CIFAR-IOCNN, VGGI6BN, Best results (second best) for each hash length are in bold (underlined). BioHash demonstrates the best retrieval performance, especially at small
Hash Length (k)
Method
2
4
8
16
32
64
LSH
13.25
12.94
18.06
23.28
25.79
32.99
PCAHash
17.19
22.89
27.76
29.21
28.22
26.73
Flyffahh
18.52
23.48
27.70
30.58
35.54
38.41
SH
16.66
22.28
27.72
28.60
29.27
27.50
ITQ
17.56
23.94
31.30
36.25
39.34
42.56
BioHash
44.17
45.98
47.66
49.32
50.13
Table 8: mAP@ 1000 (%) on CIFAR-IOCNN, AlexNet. Best results (second best) for each hash length are in bold (underlined). BioHash demonstrates the best retrieval performance, especially at small k.
APPENDIX D: IMPLEMENTATION DETAILS
BioHash: The training /retrieval database centered. Queries were also centered using mean computed on the training set. Weights were initialized by sampling from the standard normal distribution. For simplicity
used p 2, A O. We set initial learning rate Gy = 2 x 10-2 which was decayed as < = 6o Tays ), where is epoch number and Tmax is maximum number of epochs. We used Tmax = 100 and a mini- mini-batch size of 100. The criterion for convergence
average norm of synapses < 1.06. Convergence usually
took < 20 epochs.
In order to set the activity level, we performed cross-validation. In the case of MNIST, we separated random samples (100 from each class) from the training set, to create a training set of size 68k and validation set of 1k images. Activity level with highest mAP@@ All on the validation set was determined to be 5%, see Figure 4. We then retrained oHa sh on the whole training data of size 69k and reported the performance on the query set. Similarly for CIFAR-10. 10, we separated 1k samples (100 images per class) to create a training set of size 49k and validation set of 1k. We set the activity level to be 0.5%, see Figure 4. We then retrained B sioHash on the whole training data of size 50k and reported the performance on the query set.
BicConvHash A convolutional filter of kernel size K is learned by dividing the training set into patches of sizes K K and applying the learning dynamics 1. In the case of MNIST, trained 500 filters of kernel sizes K = 3, 4. In the case of CIFAR- 10, used = 3, 4, 10. For both datasets, we used a stride of in the convolutional layers. We set
kc 10 for MNIST and Kcı 1 for CIFAR-10, by cross-validation in procedure similar
16

---

Under review as a conference paper at ICLR 2020
to how sparsity set. The effect of channel inhibition is shown in Table 3. kc means that only the largest activation across channels per spatial location was kept, while the rest are set to O. This followed by 2d max-pooling with stride of 2 and kernel size of 7. This was followed by a fully connected layer (the "hash" layer).
F Fl sh Following Dasgupta et al. (2017), we set m 10d for all hash lengths & and each neuron in the hashing layer ("Kenyon" cell) sampled from 0.1 dimensions of imput data (Projection neurons). Following Gong & Lazebmik 20.11, ITQ employed 50 iterations.
To extract representations from VGG16 fc7, CIFAR-10 images were resized to 224 224 and normalized using default values: [0.485. 0.456, 0.406]. [0.229, 0.224, 0.225]. To make a fair comparison we used the pre-trained VGG16 model (without BN), since this model frequently employed by deep hashing methods. We also evaluated the performance using VGG16 with BN and also using AlexNet (Krizhevsky et al., 2012), see Tables 7,8
GreedyHash replaces the softmax layer of VGG16 with a hash layer and trained end- to-end via backpropogation using custom objective function, see Su et al. (2018) for more details. We use the code provided by the authors to measure performance at k = 2, 4, 8, since these numbers were not reported in Su et al. (2018). We used the default parameters: mini-batch size of 32, learning rate of x 10 4 and trained for 60 epochs.
APPENDIX E: TRAINING TIME
Here we report the training times for the best performing (having the highest corresponding mAP@R) variant of our algorithm: BicHash, BicConviash,, or Bioflash top of VGG16 representations. For the case of MNIST, the best performing variant is Bi BioConvHash, and for CIFAR-10 it is BioHash top of VGG16 representations. We also report the training time of the next best method for each dataset. This is GreedyHash in the case of CIFAR-10, and BicHash in the case of MNIST. In the case of MNIST, the best method that not variant of BioHasi UH- BNN. Training time for UH-BNT BNN is unavailable, since it is not reported in literature. All experiments were run on single V100 GPU make fair comparison.
Hash Length (k)
Method
2
4
16
32
BioHash
~1.7 s
1.7s
~1.7 s
~3344 s
~ 5
BioConvllsh
~3. m
~3.
~3.5 m
~ m
5
Table 9: Training time for the best variant of Bi oHash, and the next best method for MNIST.
Hash Length (k)
CIFAR-10
2
8
16
32
Biolashh
~ 4.2
~7.6
~ 11.55
~2 s
35
GreedyHash
1.2 hrs
1=. hrs
111 hrs
~ 1.4 hrs
~ 1,45 hrs
Table 10: Training time for the best variant of BioHash and the next best method for CIFAR-10. Both models are based on VGG16.
17


Reviews:
[{"review_id": "rkxbczB-cS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a new model of locally sensitive hashing (LSH) that is inspired by the fruit fly Drosophila's olfactory circuit. Instead of mapping each input to a low-dimensional space, such LSH methods (FlyHash) map given $d$-dimensional inputs to an $m$-dimensional space such that $m \\gg d$. However, these mappings enforce sparsity on the hash maps such that only $k$ out of $m$ coordinates of the output of the hash map are non-zero.\n\nThe existing methods to realize these FlyHash maps rely on random projections and don't take the original dataset being mapped by the hash function into account. This paper proposes a data-driven approach to learn such sparsity inducing hash maps which are referred to as BioHash. The proposed approach is biologically feasible, which raises the interesting question if various biological organisms employ such a mechanism to realize some kind of LSH.\n\nUsing MNIST and CIFAR-10 datasets, the paper shows that BioHash achieves superior performance as a similarity search mechanism as compared to many existing LSH methods for small values of $k$. The paper also evaluates a convolutional variant of BioHash, namely BioConvHash, which leads to even better similarity search scores. This makes BioHash and BioConvHash an appealing candidate to realize fast and scalable similarity searches on large scale datasets.\n\nOverall, the paper makes some interesting contributions with experimental results clearly showing the utility of the proposed method. That said, there is some room for improvement in the presentation of the key ideas.\n\n- What is $Rank(\\cdot)$ in Eq. 1 and Eq. 3?\n\n- $W_{\\mu}$ is not formally defined ($W_{\\mu} = (W_{\\mu 1},\\ldots, W_{\\mu d})$?)\n\n- 'figure', 'table', 'sec.' --> 'Figure', 'Table', 'Sec.'.\n\n- Notation mAP@x is not formally defined in Section 3.1 and 3.2. Also, is there notation overloading. How are $k$ defining the sparsity in the map and $k$ in Section 3.1 related?\n\n- In Section 5 (appendix), the authors point out that data-driven Fly inspired LSH exists in the literature (SolHash by Li et al.) Even though SolHash is not a biological feasible approach, it somewhat contradicts one of the underlying claims in the main text that this paper is the first paper to propose data-driven Fly inspired hash maps. Shouldn't the authors mention SolHash in the main text itself and introduce their contributions in the proper context?\n\n------------------------------------------\nPost rebuttal phase\n------------------------------------------\n\nThank you for addressing my presentation related questions. With improved discussion of prior work, the paper places its contributions in the right context. Moreover, the empirical results in the paper demonstrate the utility of the proposed method on (small scale) real world data. This should inspire a thorough investigation on large scale data sets in the future. Overall, I think that this paper makes interesting and novel contributions. Accordingly, I have updated my score to Weak Accept.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1l6nBpQ9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a bio-inspired locally sensitive hashing method called BioHash, inspired by FlyHash. Unlike FlyHash and many other hashing algorithms, the BioHash algorithm is adaptive and uses synaptic plasticity to update the mapping from input to encoding. \nThe experimental section uses common datasets (CIFAR-10 & MNIST) to compare the performance of BioHash to a number of common locally sensitive hashing methods and BioHash is shown to significantly outperform existing method in similarity search tasks. \n\nCaveat: I'm not an expert in this field and did my best to understand the details. I'm not familiar with the the state-of-the-art of hashing methods.\n\nQuestions:\n- Novelty of the algorithm? As the authors point out (\"We adopt a biologically plausible unsupervised algorithm for representation learning from (17).\"), the algorithm comes from another recent paper (17, \"Unsupervised learning by competing hidden units\", PNAS 2019). What is the difference between the PNAS 2019 paper and this submission? It seems like the algorithm from [17] was directly applied to similarity search, without additional contributions.\n- Overall, I'm having a hard time understanding the equations in section 2.1. This is the main reason why I read [17]. In equation 1, you use square brackets for the input of a function g[...], but in equation 2, you use parenthesis (expected). I also had to refer to [17] to figure out what \"Rank\" meant in this context (hint: it's not the rank of a matrix). \n- Section 2.2 \"Intuition behind the learning algorithm\" doesn't clear things up. I think a visual representation of the learning method would better serve this purpose.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BklzYdcaYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a variant of FlyHash for similarity search in vector space. The basic idea is motivated by the intuition: the original FlyHash method is data-independent, so can we improve FlyHash's locality sensitivity by learning from data. It does so by learning the weights of the projection layer and uses winner-take-all sparsification to generate sparse binary hash code. This leads to the bio-inspired hashing algorithm (BioHash).  The paper argues that by taking into account the density of data, the learned projection helps to further push similar entities to have hash codes that point in similar direction while repelling dissimilar objects in opposite directions. Experiment results are reported on MNIST and CIFAR10, and the proposed approach demonstrates better retrieval precision results compared to several other hashing based methods. \n\nStrengths: \n+ A good example of intersection work that has interesting indications to both the biological and computational sides. \n+The unsupervised learning method for sparse representation expansion seems to be novel. \n\nWeaknesses:\n- Interesting exploration but still seems to have a large gap to a real-world solution (see comments below). \n- Sometimes the writing is a bit hard to follow, presumably because it introduces the work using concepts from both fields. \n\nOverall, I like the idea of this paper. In particular, I find the reverse indication that learned synapses must be neurobiologically plausible really interesting. It is also a sensible approach to learn from data to improve the locality sensitivity of FlyHash than doing just random projection. However, I feel there is still a gap between the current work and the real working system.  \n\nFirst, the paper only studies the accuracy impact of BioHash but completely ignores the evaluation of search time and memory, which are crucial dimensions for evaluating similarity search algorithms. Without those constraints, similarity search can just be done with brute force searches without any representation transformation.  By using accuracy as a single metric, it is tricky to get a sense of how good the proposed solution is.  It might outperform FlyHash and other hashing based approach, but a caveat is that hashing itself has not been identified as the most effective way for performing similarity search. \n\nSecond, the evaluation is mostly done on toy datasets in terms of scale. The state-of-the-art similarity search is often evaluated on millions and sometimes billion-scale datasets, such as BIGANN and DEEP1B. Given that the proposed approach is only evaluated on MNIST and CIFAR10, it is unclear how scalable the proposed solution is on larger datasets. Empirical studies have shown that hashing based approaches often incur a large accuracy loss for dense continuous vectors. On million-scale datasets, solutions such as similarity graph-based approaches (e.g., HNSW) outperform hashing and quantization based approaches by a large margin. It could be that through data-driven sparse expansion, bio-inspired hashing could help overcome the limitation of existing hashing based approaches, but without comparison, we do not know the answer. \n\nThird, I thought the paper neglects many practical aspects of doing a similarity search. For example, no indexing is applied to the generated binary hash code and the search is done through linear scanning. There is also no discussion on training time and how to handle incremental updates. \n\nAnother minor issue of this paper is that the citation format does not seem to comply with ICLR format. But I believe these issues could be easily fixed.\n\nThat being said, while the method does not seem to be readily applicable to real-world scenarios and only manages to demonstrate its effectiveness on small datasets compared to other hashing based approaches, I think this is a promising direction to look into, and I imagine it could serve as a starting point for other researchers to develop more extensions on top of it. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a biologically inspired locally sensitive hashing method, a variant of FlyHash. While the paper contains interesting ideas and its presentation has been substantially improved from its original form during the discussion period, the paper still does not meet the quality bar of ICLR due to its limitations in terms of experiments and applicability to real-world scenarios.
Decision: Reject