Title: BIO-INSPIRED HASHING FOR UNSUPERVISED SIMI-LARITY SEARCH

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.

1. INTRODUCTION:

Sparse expansive representations are ubiquitous in neurobiology. Expansion means that a highdimensional input is mapped to an even higher dimensional secondary representation. Such expansion is often accompanied by a sparsification of the activations: dense input data is mapped into a sparse code, where only a small number of secondary neurons respond to a given stimulus.

A classical example of the sparse expansive motif is the Drosophila fruit fly olfactory system. In this case, approximately 50 projection neurons send their activities to 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 is 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 to a given stimulus (Mombaerts et al., 1996) . A 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 a 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, as well as local Hebbian learning, for designing a novel hashing algorithm BioHash that can be used in similarity search. Below we describe the task, the algorithm, and demonstrate that BioHash improves retrieval performance on common benchmark datasets.

Under review as a conference paper at ICLR 2020 Similarity search and LSH. In similarity search, given a query q ∈ R d , a similarity measure sim(q, x), and a database X ∈ R n×d 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 (LSH) 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 x (and query q) with a binary representation h(x) (h(q) respectively) and to retrieve R entries with smallest Hamming distances d H (h(x), h(q)). Intuitively, (see (Charikar, 2002) , for a formal definition), a hash function h : R d -→ {-1, 1} m is said to be locality sensitive, if similar (dissimilar) items x 1 and x 2 are close by (far apart) in Hamming distance d H (h(x 1 ), h(x 2 )). LSH algorithms are of fundamental importance in computer science, with applications in similarity search, data compression and machine learning (Andoni & Indyk, 2008) .

Drosophila olfactory circuit and FlyHash. 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 et al., 2017) where m d, but the secondary representation is highly sparse with only a small number k of m units being active, see Figure 1 . We call this algorithm FlyHash in this paper, since it 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 a random set of weights W (Dasgupta et al., 2017; Caron et al., 2013) . The resulting high dimensional representation is sparsified by k-Winner-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 FlyHash 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 to data, demonstrating improved performance over FlyHash. However, every learning update step in SOLHash invokes a 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 a 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 FlyHash and demonstrates improved performance compared to random weights used in FlyHash, but it is fast, online, scalable and, importantly, BioHash is neurologically plausible.

m ⌧ d < l a t e x i t s h a _ b a s e = " d z z Y I b V J b r T w J Q T o x t s k f u I = " > A A A B X i c b V D L S g N B E O y N r x h f U Y e B o P g K e y K o M e g F R z A O S J c z O z i Z j r H M z A p h y T a C I V / / H m / j J N m D J h Y F F X d d H d F K W f G + v V p b j c K m X d n b g + q h d t o z J N a I s o r n Q w o Z y J m n L M s t p N U U i j T T j S + n f m d J o N U / L B T l I a C j y U L G E E W y e R Z z F A + q N b / u z F W S V C Q G h R o D q p f / V i R T F B p C c f G A I / t W G O t W W E m l n x m a Y j L G Q p z V G J B T Z j P r i M f E K F H a l b R o r v e y L E w Z i I i y m w H Z l l b y b + / U y m y H O Z N p Z q k k i V J x p F V a P Y i p m m x P K J I h o m F Z I Q J t Y F V H E h B M s v r L R T w H Z a x U R R h h M h X M I A o a c A d N a A G B R i G V j z l P f i v X s f i a S V w c w x n z u / o b < / l a t e x i t > < l a t e x i t s h a _ b a s e = " d z z Y I b V J b r T w J Q T o x t s k f u I = " > A A A B X i c b V D L S g N B E O y N r x h f U Y e B o P g K e y K o M e g F R z A O S J c z O z i Z j r H M z A p h y T a C I V / / H m / j J N m D J h Y F F X d d H d F K W f G + v V p b j c K m X d n b g + q h d t o z J N a I s o r n Q w o Z y J m n L M s t p N U U i j T T j S + n f m d J o N U / L B T l I a C j y U L G E E W y e R Z z F A + q N b / u z F W S V C Q G h R o D q p f / V i R T F B p C c f G A I / t W G O t W W E m l n x m a Y j L G Q p z V G J B T Z j P r i M f E K F H a l b R o r v e y L E w Z i I i y m w H Z l l b y b + / U y m y H O Z N p Z q k k i V J x p F V a P Y i p m m x P K J I h o m F Z I Q J t Y F V H E h B M s v r L R T w H Z a x U R R h h M h X M I A o a c A d N a A G B R i G V j z l P f i v X s f i a S V w c w x n z u / o b < / l a t e x i t > < l a t e x i t s h a _ b a s e = " d z z Y I b V J b r T w J Q T o x t s k f u I = " > A A A B X i c b V D L S g N B E O y N r x h f U Y e B o P g K e y K o M e g F R z A O S J c z O z i Z j r H M z A p h y T a C I V / / H m / j J N m D J h Y F F X d d H d F K W f G + v V p b j c K m X d n b g + q h d t o z J N a I s o r n Q w o Z y J m n L M s t p N U U i j T T j S + n f m d J o N U / L B T l I a C j y U L G E E W y e R Z z F A + q N b / u z F W S V C Q G h R o D q p f / V i R T F B p C c f G A I / t W G O t W W E m l n x m a Y j L G Q p z V G J B T Z j P r i M f E K F H a l b R o r v e y L E w Z i I i y m w H Z l l b y b + / U y m y H O Z N p Z q k k i V J x p F V a P Y i p m m x P K J I h o m F Z I Q J t Y F V H E h B M s v r L R T w H Z a x U R R h h M h X M I A o a c A d N a A G B R i G V j z l P f i v X s f i a S V w c w x n z u / o b < / l a t e x i t > < l a t e x i t s h a _ b a s e = " d z z Y I b V J b r T w J Q T o x t s k f u I = " > A A A B X i c b V D L S g N B E O y N r x h f U Y e B o P g K e y K o M e g F R z A O S J c z O z i Z j r H M z A p h y T a C I V / / H m / j J N m D J h Y F F X d d H d F K W f G + v V p b j c K m X d n b g + q h d t o z J N a I s o r n Q w o Z y J m n L M s t p N U U i j T T j S + n f m d J o N U / L B T l I a C j y U L G E E W y e R Z z F A + q N b / u z F W S V C Q G h R o D q p f / V i R T F B p C c f G A I / t W G O t W W E m l n x m a Y j L G Q p z V G J B T Z j P r i M f E K F H a l b R o r v e y L E w Z i I i y m w H Z l l b y b + / U y m y H O Z N p Z q k k i V J x p F V a P Y i p m m x P K J I h o m F Z I Q J t Y F V H E h B M s v r L R T w H Z a x U R R h h M h X M I A o a c A d N a A G B R i G V j z l P f i v X s f i a S V w c w x n z u / o b < / l a t e x i t > m d < l a t e x i t s h a 1 _ b a s e 6 4 = " b Y p J e n e c L E T / B C Q O q + j a L s H K r e c = " > A A A B 7 X i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K o M e g F 4 8 R z A O S J c z O z m 7 G z G O Z m R V C y D 9 4 8 a C I V / / H m 3 / j J N m D J h Y 0 F F X d d H d F G W f G + v 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t o 3 J N a I s o r n Q 3 w o Z y J m n L M s t p N 9 M U i 4 j T T j S 6 n f m d J 6 o N U / L B j j M a C p x K l j C C r Z P a o p + m K B 5 U a 3 7 d n w O t k q A g N S j Q H F S / + r E i u a D S E o 6 N 6 Q V + Z s M J 1 p Y R T q e V f m 5 o h s k I p 7 T n q M S C m n A y v 3 a K z p w S o 0 R p V 9 K i u f p 7 Y o K F M W M R u U 6 B 7 d A s e z P x P 6 + X 2 + Q 6 n D C Z 5 Z Z K s l i U 5 B x Z h W a v o 5 h p S i w f O 4 K J Z u 5 W R I Z Y Y 2 J d Q B U X Q r D 8 8 i p p X 9 Q D v x 7 c X 9 Y a N 0 U c Z T i B U z i H A K 6 g A X f Q h B Y Q e I R n e I U 3 T 3 k v 3 r v 3 s W g t e c X M M f y B 9 / k D H 7 2 O 0 Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " b Y p J e n e c L E T / B C Q O q + j a L s H K r e c = " > A A A B 7 X i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K o M e g F 4 8 R z A O S J c z O z m 7 G z G O Z m R V C y D 9 4 8 a C I V / / H m 3 / j J N m D J h Y 0 F F X d d H d F G W f G + v 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t o 3 J N a I s o r n Q 3 w o Z y J m n L M s t p N 9 M U i 4 j T T j S 6 n f m d J 6 o N U / L B j j M a C p x K l j C C r Z P a o p + m K B 5 U a 3 7 d n w O t k q A g N S j Q H F S / + r E i u a D S E o 6 N 6 Q V + Z s M J 1 p Y R T q e V f m 5 o h s k I p 7 T n q M S C m n A y v 3 a K z p w S o 0 R p V 9 K i u f p 7 Y o K F M W M R u U 6 B 7 d A s e z P x P 6 + X 2 + Q 6 n D C Z 5 Z Z K s l i U 5 B x Z h W a v o 5 h p S i w f O 4 K J Z u 5 W R I Z Y Y 2 J d Q B U X Q r D 8 8 i p p X 9 Q D v x 7 c X 9 Y a N 0 U c Z T i B U z i H A K 6 g A X f Q h B Y Q e I R n e I U 3 T 3 k v 3 r v 3 s W g t e c X M M f y B 9 / k D H 7 2 O 0 Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " b Y p J e n e c L E T / B C Q O q + j a L s H K r e c = " > A A A B 7 X i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K o M e g F 4 8 R z A O S J c z O z m 7 G z G O Z m R V C y D 9 4 8 a C I V / / H m 3 / j J N m D J h Y 0 F F X d d H d F G W f G + v 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t o 3 J N a I s o r n Q 3 w o Z y J m n L M s t p N 9 M U i 4 j T T j S 6 n f m d J 6 o N U / L B j j M a C p x K l j C C r Z P a o p + m K B 5 U a 3 7 d n w O t k q A g N S j Q H F S / + r E i u a D S E o 6 N 6 Q V + Z s M J 1 p Y R T q e V f m 5 o h s k I p 7 T n q M S C m n A y v 3 a K z p w S o 0 R p V 9 K i u f p 7 Y o K F M W M R u U 6 B 7 d A s e z P x P 6 + X 2 + Q 6 n D C Z 5 Z Z K s l i U 5 B x Z h W a v o 5 h p S i w f O 4 K J Z u 5 W R I Z Y Y 2 J d Q B U X Q r D 8 8 i p p X 9 Q D v x 7 c X 9 Y a N 0 U c Z T i B U z i H A K 6 g A X f Q h B Y Q e I R n e I U 3 T 3 k v 3 r v 3 s W g t e c X M M f y B 9 / k D H 7 2 O 0 Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " b Y p J e n e c L E T / B C Q O q + j a L s H K r e c = " > A A A B 7 X i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K o M e g F 4 8 R z A O S J c z O z m 7 G z G O Z m R V C y D 9 4 8 a C I V / / H m 3 / j J N m D J h Y 0 F F X d d H d F G W f G + v 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t o 3 J N a I s o r n Q 3 w o Z y J m n L M s t p N 9 M U i 4 j T T j S 6 n f m d J 6 o N U / L B j j M a C p x K l j C C r Z P a o p + m K B 5 U a 3 7 d n w O t k q A g N S j Q H F S / + r E i u a D S E o 6 N 6 Q V + Z s M J 1 p Y R T q e V f m 5 o h s k I p 7 T n q M S C m n A y v 3 a K z p w S o 0 R p V 9 K i u f p 7 Y o K F M W M R u U 6 B 7 d A s e z P x P 6 + X 2 + Q 6 n D C Z 5 Z Z K s l i U 5 B x Z h W a v o 5 h p S i w f O 4 K J Z u 5 W R I Z Y Y 2 J d Q B U X Q r D 8 8 i p p X 9 Q D v x 7 c X 9 Y a N 0 U c Z T i B U z i H A K 6 g A X f Q h B Y Q e I R n e I U 3 T 3 k v 3 r v 3 s W g t e c X M M f y B 9 / k D H 7 2 O 0 Q = = < / l a t e x i t > W < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > W < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " G g o 3 W P Y Q V P 5 4 i v 8 X u l a k D l z R g T w = " > A A A B 8 X i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 6 L L o x m U F + 8 A 2 l M l 0 0 g 6 d T M L M j V B C / 8 K N C 0 X c + j f u / B s n b R b a e m D g c M 6 9 z L k n S K Q w 6 L r f T m l t f W N z q 7 x d 2 d n d 2 z + o H h 6 1 T Z x q x l s s l r H u B t R w K R R v o U D J u 4 n m N A o k 7 w S T 2 9 z v P H F t R K w e c J p w P 6 I j J U L B K F r p s R 9 R H A d h 1 p k N q j W 3 7 s 5 B V o l X k B o U a A 6 q X / 1 h z N K I K 2 S S G t P z 3 A T 9 j G o U T P J Z p Z 8 a n l A 2 o S P e s 1 T R i B s / m y e e k T O r D E k Y a / s U k r n 6 e y O j k T H T K L C T e U K z 7 O X i f 1 4 v x f D a z 4 R K U u S K L T 4 K U 0 k w J v n 5 Z C g 0 Z y i n l l C m h c 1 K 2 J h q y t C W V L E l e M s n r 5 L 2 R d 1 z 6 9 7 9 Z a 1 x U 9 R R h h M 4 h X P w 4 A o a c A d N a A E D B c / w C m + O c V 6 c d + d j M V p y i p 1 j + A P n 8 w f L F J D 7 < / l a t e x i t > k active neurons < l a t e x i t s h a 1 _ b a s e 6 4 = " Q t 2 J d h H D P A 1 C 0 n 4 4 b N Y m X 4 u + r / g = " > A A A C A X i c b V D L S g N B E J y N r x h f U S + C l 8 E g e A q 7 I u g x 6 M V j B P O A 7 B J m J 5 1 k y O z s M t M b D E u 8 + C t e P C j i 1 b / w 5 t 8 4 e R w 0 s a C h q O q m u y t M p D D o u t 9 O b m V 1 b X 0 j v 1 n Y 2 t 7 Z 3 S v u H 9 R N n G o O N R 7 L W D d D Z k A K B T U U K K G Z a G B R K K E R D m 4 m f m M I 2 o h Y 3 e M o g S B i P S W 6 g j O 0 U r t 4 N P A R H j D z K e M o h k A V p D p W Z t w u l t y y O w V d J t 6 c l M g c 1 X b x y + / E P I 1 A I Z f M m J b n J h h k T K P g E s Y F P z W Q M D 5 g P W h Z q l g E J s i m H 4 z p q V U 6 t B t r W w r p V P 0 9 k b H I m F E U 2 s 6 I Y d 8 s e h P x P 6 + V Y v c q y I R K U g T F Z 4 u 6 q a Q Y 0 0 k c t C M 0 c J Q j S x j X w t 5 K e Z 9 p G 4 Y N r W B D 8 B Z f X i b 1 8 7 L n l r 2 7 i 1 L l e h 5 H n h y T E 3 J G P H J J K u S W V E m N c P J I n s k r e X O e n B f n 3 f m Y t e a c + c w h + Q P n 8 w c J l p d B < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " Q t 2 J d h H D P A 1 C 0 n 4 4 b N Y m X 4 u + r / g = " > A A A C A X i c b V D L S g N B E J y N r x h f U S + C l 8 E g e A q 7 I u g x 6 M V j B P O A 7 B J m J 5 1 k y O z s M t M b D E u 8 + C t e P C j i 1 b / w 5 t 8 4 e R w 0 s a C h q O q m u y t M p D D o u t 9 O b m V 1 b X 0 j v 1 n Y 2 t 7 Z 3 S v u H 9 R N n G o O N R 7 L W D d D Z k A K B T U U K K G Z a G B R K K E R D m 4 m f m M I 2 o h Y 3 e M o g S B i P S W 6 g j O 0 U r t 4 N P A R H j D z K e M o h k A V p D p W Z t w u l t y y O w V d J t 6 c l M g c 1 X b x y + / E P I 1 A I Z f M m J b n J h h k T K P g E s Y F P z W Q M D 5 g P W h Z q l g E J s i m H 4 z p q V U 6 t B t r W w r p V P 0 9 k b H I m F E U 2 s 6 I Y d 8 s e h P x P 6 + V Y v c q y I R K U g T F Z 4 u 6 q a Q Y 0 0 k c t C M 0 c J Q j S x j X w t 5 K e Z 9 p G 4 Y N r W B D 8 B Z f X i b 1 8 7 L n l r 2 7 i 1 L l e h 5 H n h y T E 3 J G P H J J K u S W V E m N c P J I n s k r e X O e n B f n 3 f m Y t e a c + c w h + Q P n 8 w c J l p d B < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " Q t 2 J d h H D P A 1 C 0 n 4 4 b N Y m X 4 u + r / g = " > A A A C A X i c b V D L S g N B E J y N r x h f U S + C l 8 E g e A q 7 I u g x 6 M V j B P O A 7 B J m J 5 1 k y O z s M t M b D E u 8 + C t e P C j i 1 b / w 5 t 8 4 e R w 0 s a C h q O q m u y t M p D D o u t 9 O b m V 1 b X 0 j v 1 n Y 2 t 7 Z 3 S v u H 9 R N n G o O N R 7 L W D d D Z k A K B T U U K K G Z a G B R K K E R D m 4 m f m M I 2 o h Y 3 e M o g S B i P S W 6 g j O 0 U r t 4 N P A R H j D z K e M o h k A V p D p W Z t w u l t y y O w V d J t 6 c l M g c 1 X b x y + / E P I 1 A I Z f M m J b n J h h k T K P g E s Y F P z W Q M D 5 g P W h Z q l g E J s i m H 4 z p q V U 6 t B t r W w r p V P 0 9 k b H I m F E U 2 s 6 I Y d 8 s e h P x P 6 + V Y v c q y I R K U g T F Z 4 u 6 q a Q Y 0 0 k c t C M 0 c J Q j S x j X w t 5 K e Z 9 p G 4 Y N r W B D 8 B Z f X i b 1 8 7 L n l r 2 7 i 1 L l e h 5 H n h y T E 3 J G P H J J K u S W V E m N c P J I n s k r e X O e n B f n 3 f m Y t e a c + c w h + Q P n 8 w c J l p d B < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " Q t 2 J d h H D P A 1 C 0 n 4 4 b N Y m X 4 u + r / g = " > A A A C A X i c b V D L S g N B E J y N r x h f U S + C l 8 E g e A q 7 I u g x 6 M V j B P O A 7 B J m J 5 1 k y O z s M t M b D E u 8 + C t e P C j i 1 b / w 5 t 8 4 e R w 0 s a C h q O q m u y t M p D D o u t 9 O b m V 1 b X 0 j v 1 n Y 2 t 7 Z 3 S v u H 9 R N n G o O N R 7 L W D d D Z k A K B T U U K K G Z a G B R K K E R D m 4 m f m M I 2 o h Y 3 e M o g S B i P S W 6 g j O 0 U r t 4 N P A R H j D z K e M o h k A V p D p W Z t w u l t y y O w V d J t 6 c l M g c 1 X b x y + / E P I 1 A I Z f M m J b n J h h k T K P g E s Y F P z W Q M D 5 g P W h Z q l g E J s i m H 4 z p q V U 6 t B t r W w r p V P 0 9 k b H I m F E U 2 s 6 I Y d 8 s e h P x P 6 + V Y v c q y I R K U g T F Z 4 u 6 q a Q Y 0 0 k c t C M 0 c J Q j S x j X w t 5 K e Z 9 p G 4 Y N r W B D 8 B Z f X i b 1 8 7 L n l r 2 7 i 1 L l e h 5 H n h y T E 3 J G P H J J K u S W V E m N c P J I n s k r e X O e n B f n 3 f m Y t e a c + c w h + Q P n 8 w c J l p d B < / l a t e x i t >

Figure 1 : It is convenient to think about different hashing algorithms in terms of representational contraction (large dimension of input is mapped into a smaller dimensional latent space), or 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 a 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 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 utilized 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 on inspiration from FlyHash and more broadly the ubiquity of sparse, expansive representations in neurobiology, our work proposes a novel hashing algorithm BioHash, that in contrast with previous work (Dasgupta et 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 BioHash, resulting in a hashing with improved performance compared to previously published benchmarks. From the perspective of computer science, we show that BioHash is simple, scalable to 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 a data point as x ∈ R d , we seek a binary hash code y ∈ {-1, 1} m . We define the hash length of a binary code as k, if the exact Hamming distance computation is O(k). Below we present our 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 ∈ R m×d . The learning dynamics for the synapses of an individual neuron µ, denoted by W µi , is given by

EQUATION

where W µ = (W µ1 , W µ2 ...W µd ), and

EQUATION

and x, y µ = i,j η µ i,j x i y j , with η µ i,j = |W µi | p-2 δ ij , where δ ij 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

EQUATION

where A indexes the training example. Note that the training dynamics do not perform gradient descent, i.e Ẇµ = ∇ Wµ E. However, time derivative of the energy function under dynamics (1) is always negative (we show this for the case ∆ = 0 below),

EQUATION

where Cauchy-Schwartz inequality is used. For every training example A the index of the activated hidden unit is defined as Thus, the energy function decreases during learning. A similar result can be shown for ∆ = 0.

EQUATION

M T 4 2 d U G c 4 E T k u 9 V G N C 2 Z g O s W u p p B F q P 5 u f O i V n V h m Q M F a 2 p C F z 9 f d E R i O t J 1 F g O y N q R n r Z m 4 n / e d 3 U h F d + x m W S G p R s s S h M B T E x m f 1 N B l w h M 2 J i C W W K 2 1 s J G 1 F F m b H p l G w I 3 v L L q 6 R d q 3 r

After the learning-phase is complete, the hash code is generated, as in FlyHash, via WTA sparsification: for a given query x we generate a hash code y ∈ {-1, 1} m as

y µ = 1, W µ , x µ is in top k -1, otherwise. (6)

Thus, the hyperparameters of the method are p, r, m and ∆. Note that the synapses are updated based only on pre-and post-synaptic activations resulting in Hebbian or anti-Hebbian updates. Many "unsupervised" learning to hash approaches provide a sort of "weak supervision" in the form of similarities evaluated in the feature space of deep CNNs trained on ImageNet (Jin et 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 to think about the learning algorithm is to view the hidden units as particles that are attracted to local peaks of the density of the data, and that simultaneously repel each other.

To demonstrate this, it is convenient to think about input data as randomly sampled points from a continuous distribution. Consider the case when p = 2 and ∆ = 0. In this case, the energy function can be written as (since for p = 2 the inner product does not depend on the weights, we drop the subscript µ of the inner product)

EQUATION

)

where we introduced a continuous density of data ρ(v). Furthermore, consider the case of d = 2, and imagine that the data lies on a unit circle. In this case the density of data can be parametrized by a single angle ϕ. Thus, the energy function can be written as

EQUATION

It is instructive to solve a simple case when the data follows an exponential distribution concentrated around zero angle with the decay length σ (α is a normalization constant),

EQUATION

)

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 m. To further simplify the problem consider the case when the number of hidden units m is small. For m = 2 the energy is equal to

E = -α σ(1 + e -π σ ) 1 + σ 2 cos(ϕ 1 ) + σ sin(ϕ 1 ) + cos(ϕ 2 ) -σ sin(ϕ 2 ) (10)

Thus, in this simple case the energy is minimized when

EQUATION

In the limit when the density of data is concentrated around zero angle (σ → 0) the hidden units are attracted to the origin and |ϕ 1,2 | ≈ σ. In the opposite limit (σ → ∞) the data points are uniformly distributed on the circle. The resulting hidden units are then organized to be on the opposite sides of the circle |ϕ 1,2 | = π 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 ∆ϕ = 2π/m. 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 in the vicinity of local maxima of the probability density of the data. At the same time, repulsive 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 x "closest" to some new query q requires a definition of "distance". Since this measure is wanted only for nearby locations q and x, it need not be accurate for long distances. If we pick a set of m reference points in the space, then the location of point x can be specified by noting the few reference points it is closest to, producing a sparse and useful local representation. Uniformly tiling a high dimensional space is not a 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 1 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 is low. This is exactly what is needed for a 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 1 ) 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 x and y 2 , they produce hash codes that are slightly different (black and green circles, hamming distance is equal to 2 in this case). If the two data points are even farther, like x and y 3 , 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 d, entailing a storage cost of k bits per database entry and O(k) computational cost to compute Hamming distance. In BioHash (and in FlyHash), typically m k and m > d entailing storage cost of k log 2 m bits per database entry and O(k)1 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) , which stores a lookup table of distances between every pair of codewords for each product space. From a neurobiological perspective, a highly sparse representation such as the one produced by BioHash keeps the same metabolic cost (Levy & Baxter, 1996) 2 : mAP@1000 (%) on CIFAR-10 (higher is better). Best results (second best) for each hash length are in bold (underlined). BioHash demonstrates the best retrieval performance, especially at small k.

3. SIMILARITY SEARCH:

In this section, we 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: a) 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 is permissible. Features extracted from this pretraining are then used for hashing. In 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 et al., 2018) , we use Mean Average Precision (mAP) as the evaluation metric, a measure that averages precision over different recall. Specifically, given a query set Q, we evaluate mAP@R as

EQUATION

)

where R is number of retrievals, Rel(l) = 1(document l is relevant) and Precision(l) is the precision of the top l retrievals. Notation: when R is equal to size of the entire database, i.e a ranking of the entire database is desired, we use the notation mAP@All or simply mAP, dropping the reference to R.

3.2. DATASETS AND PROTOCOL:

To make our work comparable with recent related work, we used common benchmark datasets: a) MNIST (Lecun et al., 1998) , a dataset of 70k grey-scale images (size 28 x 28) of hand-written digits with 10 classes of digits ranging from "0" to "9", b) CIFAR-10 (Krizhevsky, 2009), a dataset containing 60k images (size 32x32x3) from 10 classes (e.g: car, bird). Following the protocol in Lu et al. (2017) ; Chen et al. (2018) , on 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 as 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 ∈ {16, 32, 64}. However, it was observed in Dasgupta et al. (2017) that the regime in which FlyHash outperformed LSH was in the regime of low hash lengths k ∈ {2, 4, 8, 16, 32}. Accordingly, we evaluate performance for k ∈ {2, 4, 8, 16, 32, 64}.

Under review as a conference paper at ICLR 2020 MNIST Activity (%) Activity (%)

Figure 4 : Effect of varying sparsity (activity): optimal activity % for MNIST and CIFAR-10 are 5% and 0.25%. Since the improvement in performance is small from 0.5 % to 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 FlyHash we set the sampling rating from PNs to KCs to be 0.1 and m = 10d. Additionally, where appropriate, we also compare performance of BioHash to deep hashing methods: DeepBit (Lin et al., 2015) , DH (Lu et al., 2017) , USDH (Jin et al., 2019) , UH-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 k entails a dense representation using k units.

In order to clearly demonstrate the utility of sparse expansion in BioHash, we include a baseline (termed "NaiveBioHash"), which uses the learning dynamics in 1 but without sparse expansion, i.e the input data is projected into a dense latent representation with k 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. Indeed, even at a very short hash length of k = 2, the performance of BioHash is comparable to or better than DH for k ∈ {16, 32}, while at k = 4, the performance of BioHash is better than the DH and UH-BNN for k ∈ {16, 32, 64}. The performance of BioHash saturates around k = 16, showing only a small improvement from k = 8 to k = 16 and an even smaller improvement from k = 16 to k = 32; accordingly, we do not evaluate performance 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 olfactory circuit, the ground truth in their experiment was top 100 nearest neighbors of a query in the database, based on Euclidean distance between pairs of images in pixel space and thus cannot be directly compared2 . Nevertheless, we adopt that protocol (Li et al., 2018) and show that BioHash substantially outperforms SOLHash in Sec 5. The performance of BioHash on 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 k. Even at k ∈ {2, 4}, the performance of BioHash is comparable to other methods with k ∈ {16, 32, 64}. 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 × a = k, where a is 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 25.25 27.18 27.69 25 20.30 22.73 24.73 26.20 100 17.84 18.82 20.51 23.57 Table 3 : Effect of Channel Inhibition. Left: mAP@All (%) on MNIST, Right: mAP@1000 (%) on CIFAR-10. The number active channels per spatial location is denoted by k CI . It 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-10 respectively.

(see appendix for details), see Figure 4 . There is an 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 tSNE embeddings for different settings of activity levels in Figure 5 . Interestingly, at lower sparsity levels, dissimilar images may become nearest neighbors though highly dissimilar images stay apart. This is reminiscent of an experimental finding (Lin et al., 2014) in Drosophila. Sparsification of Kenyon cells in Drosophila is controlled by feedback inhibition from the anterior paired lateral neuron. Disrupting this feedback inhibition leads to denser representations, resulting in fruit flies being able to discriminate between dissimilar odors but not similar odors.

Convolutional BioHash In 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 of kernel sizes K = 3, 4 and 10. The convolutional variant of BioHash, which we call BioConvHash shows further improvement over BioHash on MNIST as well as CIFAR-10, with even small hash lengths k ∈ {2, 4} substantially outperforming other methods at larger hash lengths. Channel Inhibition is critical for performance of BioConvHash across both datasets, see Table 3 . A 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.

Hashing using deep CNN features State-of-the-art hashing methods generally adapt deep CNNs trained on ImageNet (Su et al., 2018; Jin et al., 2019; Chen et al., 2018; Lin et 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 a fair comparison with our work, we trained 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 k ∈ {2, 4}, BioHash outperforms other methods at k ∈ {16, 32, 64}. For performance of other methods and performance at varying hash lengths see It is worth remembering that while exact Hamming distance computation is O(k) for all the methods under consideration, unlike classical hashing methods, BioHash (and also FlyHash) incurs a storage cost of k log 2 m instead of k per database entry. In the case of MNIST (CIFAR-10), BioHash at k = 2 corresponds to m = 40 (m = 400) entailing a storage cost of 12 (18) bits respectively. Even in scenarios where storage is a limiting factor, BioHash at k = 2 compares favorably to other methods at k = 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 a new hashing algorithm, BioHash. In contrast with previous work (Dasgupta et al., 2017; Li et al., 2018) , BioHash is both a data-driven algorithm and has a 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 a 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 expansive representations in biology (Ganguli & Sompolinsky, 2012) . These ideas, however, require that the input be reconstructable from the sparse latent code. This is a 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 to linear scan 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) .

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 in section 8.

5. APPENDIX A: RELATED WORK:

Sparse High-Dimensional 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 or aversive. They studied the case of random projections as well as learned/"structured" 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 to such information. To the best of our knowledge no previous work has systematically examined the proposal that LSH maybe a computational principle in the brain in the context of structured synapses learned in a biologically plausible manner.

Classical LSH. A classic LSH algorithm for angular similarity is SimHash (Charikar, 2002) , which produces hash codes by h(x) = sign(W x), where entries of W ∈ R m×d are i.i.d from a standard normal distribution and sign() is element-wise. While LSH is a property and consequently is 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, FlyHash (Dasgupta et al., 2017) and DenseFly (Sharma & Navlakha, 2018) are based on random projections and cannot learn from data. Sparse Optimal Lifting (SOLHash) (Li et al., 2018) 

Here, c is the # of synapses with weight 1; the rest are -1. To optimize this objective, Li et al. (2018) resorts to Franke-Wolfe optimization, wherein every learning update involves solving a constrained linear program involving all of the training data, which is biologically unrealistic. In contrast, BioHash is neurobiologically plausible involving only Hebbian/Anti-Hebbian updates and inhibition.

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 Y Y is recomputed at every step (Li et al., 2018) . Indeed, though Li et al. (2018) uses the SIFT1M 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-art 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) is to adopt a pretrained DCNN as a backbone, replace the last layer with a custom hash layer and objective

:

If we maintain sorted pointers to the locations of 1s, we have to compute the intersection between

ordered lists of length k, which is O(k).

Due to missing values of the hyperparameters we are unable to reproduce the performance of SOLHash to enable a direct comparison.

https://github.com/ssppp/GreedyHash

Figures and Tables:

t e x i t s h a 1 _ b a s e 6 4 = " h L + F a L t O T 9 l u w f L W 3 U t 0 8 x l 3 P c w = " > A A A B 6 H i c b V D L T g J B E O z F F + I L 9 e h l I j H x R H b R R I 9 E L x 4 h k U c C G z I 7 9 M L I 7 O x m Z t Z I C F / g x Y P G e P W T v P k 3 D r A H B S v p p F L V n e 6 u I B F c G 9 f 9 d n J r 6 x u b W / n t w s 7 u 3v 5 B 8 f C o q e N U M W y w W M S q H V C N g k t s G G 4 E t h O F N A o E t o L R 7 c x v P a L S P J b 3 Z p y g H 9 G B 5 C F n 1 F i p / t Q r l t y y O w d Z J V 5 G S p C h 1 i t + d f s x S y O U h g m q d c d z E + N P q D K c C Z w W u q n G h L I R H W D H U k k j 1 P 5 k f u i U n F m l T 8 J Y 2 Z K G z N X f E x M a a T 2 O A t s Z U T P U y 9 5 M / M / r p C a 8 9 i d c J q l B y R a L w l Q Q E 5 P Z 1 6 T P F T I j x p Z Q p r i 9 l b A h V Z Q Z m 0 3 B h u A t v 7 x K m p W y d 1 G u 1 C 9 L 1 Z s s j j y c w C m c g w d X U I U 7 q E E D G C A 8 w y u 8 O Q / O i / P u f C x a c 0 4 2 c w x / 4 H z + A O e H j Q A = < / l a t e x i t > y 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " g X L z r 9 l A 6 Q y E r Q r P k t 9 0 w K d v X M k = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 Q e 0 o W y 2 m 3 b p Z h N 2 J 0 I o / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k E h h 0 H W / n c L a + s b m V n G 7 t L O 7 t 3 9 Q P j x q m T j V j D d Z L G P d C a j h U i j e R I G S d x L N a R R I 3 g 7 G t z O / / c S 1 E b F 6 x C z h f k S H S o S C U b T S Q 9 b 3 + u W K W 3 X n I K v E y 0 k F c j T 6 5 a / e I G Z p x B U y S Y 3 p e m 6 C / o R q F E z y a a m X G p 5 Q N q Z D 3 r V U 0 Y g b f z I / d U r O r D I g Y a x t K S R z 9 f f E h E b G Z F Fg O y O K I 7 P s z c T / v G 6 K 4 b U / E S p J k S u 2 W B S m k m B M Z n + T g d C c o c w s o U w L e y t h I 6 o p Q 5 t O y Y b g L b + 8 S l q 1 q n d R r d 1 f V u o 3 e R x F O I F T O A c P r q A O d 9 C A J j A Y w j O 8 w p s j n R f n 3 f l Y t B a c f O Y Y / s D 5 / A E O h I 2 l < / l a t e x i t > y 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " U m Y 8 m i G J F s Y t I m g Q 4 U O S F c 3 r PP g = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 Q e 0 o W y 2 m 3 b p Z h N 2 J 0 I o / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k E h h 0 H W / n c L a + s b m V n G 7 t L O 7 t 3 9 Q P j x q m T j V j D d Z L G P d C a j h U i j e R I G S d x L N a R R I 3 g 7 G t z O / / c S 1 E b F 6 x C z h f k S H S o S C U b T S Q 9 a v 9 c s V t + r O Q V a J l 5 M K 5 G j 0 y 1 + 9 Q c z S i C t k k h r T 9 d w E / Q n V K J j k 0 1 I v N T y h b E y H v G u p o h E 3 / m R + 6 p S c W W V A w l j b U k j m 6 u + J C Y 2 M y a L A d k Y U R2 b Z m 4 n / e d 0 U w 2 t / I l S S I l d s s S h M J c G Y z P 4 m A 6 E 5 Q 5 l Z Q p k W 9 l b C R l R T h j a d k g 3 B W 3 5 5 l b R q V e + i W r u / r N R v 8 j i K c A K n c A 4 e X E E d 7 q A B T W A w h G d 4 h T d H O i / O u / O x a C 0 4 + c w x / I H z + Q M Q C I 2 m < / l a t e x i t > y 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " I 1 Y q f / d y f M g B Y E m m G x G u y v C m w Q 4 = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l a Q Y 9 F L x 4 r 2 l p o Q 9 l s J + 3 S z S b s b o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I B F c G 9 f 9 d g p r 6 x u b W 8 X t 0 s 7 u 3 v 5 B + f C o r e N U M W y x W M S q E 1 C N g k t s G W 4 E d h K F N A o E P g b j m 5 n / + I R K 8 1 g + m E m C f k S H k o e c U W O l + 0 m / 3 i 9 X 3 K o 7 B 1 k l X k 4 q k K P Z L 3 / 1 B j F L I 5 S G C a p 1 1 3

Figure 2: (Panel A) Distribution of the hidden units (red circles) for a given distribution of the data (in one dimension). (Panel B) Arrangement of hidden units for the case of homogeneous distribution of the training data ρ = 1/(2π). For hash length k = 2 only two hidden units are activated (filled circles). If two data points are close to each other (x and y 1 ) they elicit similar hash codes, if the two data points are far away from each other (x and y 3 ) -the hash codes are different.

Figure 5: tSNE embedding of MNIST as the activity is varied for a fixed m = 160 (the change of activity is accomplished by changing k 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.

is based on learned projections and results in improvements in hashing performance. SOLHash attempts to learn a sparse binary representation Y ∈ R n×m , by optimizing arg minY ∈[-1,1] n×m Y e d =(-m+2k)em ||XX -Y Y || 2 F + γ||Y || p ,(13)e m is an all 1's vector of size m. Note the relaxation from a binaryY ∈ {-1, 1} n×m to continuous Y ∈ [-1, 1] n×m .After obtaining a Y , queries are hashed by learning a linear map from X to Y by minimizing arg min W ∈[-1,1] d×m W e d =(-m+2c)em ||Y -XW || 2 F + β||W || p ,

as a dense low-dimensional (m d) representation, such as in classical LSH methods. At the same time, as we empirically show below, it better preserves similarity information.

Table content: <table><tr><td/><td/><td colspan="3">Hash Length (k)</td><td/><td/></tr><tr><td>Method</td><td>2</td><td>4</td><td>8</td><td>16</td><td>32</td><td>64</td></tr><tr><td>LSH</td><td colspan="6">11.73 12.49 13.44 16.12 18.07 19.41</td></tr><tr><td>PCAHash</td><td colspan="6">12.73 14.31 16.20 16.81 17.19 16.67</td></tr><tr><td>FlyHash</td><td colspan="6">14.62 16.48 18.01 19.32 21.40 23.35</td></tr><tr><td>SH</td><td colspan="6">12.77 14.29 16.12 16.79 16.88 16.44</td></tr><tr><td>ITQ</td><td colspan="6">12.64 14.51 17.05 18.67 20.55 21.60</td></tr><tr><td colspan="7">NaiveBioHash 11.79 12.43 14.54 16.62 17.75 18.65</td></tr><tr><td>BioHash</td><td colspan="5">20.47 21.61 22.61 23.35 24.02</td><td>-</td></tr><tr><td colspan="6">BioConvHash 26.94 27.82 29.34 29.74 30.10</td><td>-</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="3">Hash Length (k)</td><td/><td/></tr><tr><td>Method</td><td>2</td><td>4</td><td>8</td><td>16</td><td>32</td><td>64</td></tr><tr><td>LSH  *</td><td colspan="6">13.25 17.52 25.00 30.78 35.95 44.49</td></tr><tr><td>PCAHash  *</td><td colspan="6">21.89 31.03 36.23 37.91 36.19 35.06</td></tr><tr><td>FlyHash  *</td><td colspan="6">25.67 32.97 39.46 44.42 50.92 54.68</td></tr><tr><td>SH  *</td><td colspan="6">22.27 31.33 36.96 38.78 39.66 37.55</td></tr><tr><td>ITQ  *</td><td colspan="6">23.28 32.28 41.52 47.81 51.90 55.84</td></tr><tr><td>DeepBit</td><td>-</td><td>-</td><td>-</td><td>19.4</td><td>24.9</td><td>27.7</td></tr><tr><td>USDH</td><td>-</td><td>-</td><td>-</td><td colspan="3">26.13 36.56 39.27</td></tr><tr><td>SAH</td><td>-</td><td>-</td><td>-</td><td colspan="3">41.75 45.56 47.36</td></tr><tr><td>GreedyHash</td><td colspan="4">10.56 23.94 34.32 44.8</td><td>47.2</td><td>50.1</td></tr><tr><td colspan="7">NaiveBioHash  *  18.24 26.60 31.72 35.40 40.88 44.12</td></tr><tr><td>BioHash  *</td><td colspan="5">57.33 59.66 61.87 63.47 64.61</td><td>-</td></tr></table>

mAP@1000 (%) on CIFAR-10CNN. 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 GreedyHash, SAH, DeepBit and USDH, especially at small k. Performance for DeepBit,SAH and USDH is unavailable for some k, since it is not reported in the literature.

Table content: <table/>

Peer review (iclr2020):
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 -dimensional inputs to an -dimensional space such that . However, these mappings enforce sparsity on the hash maps such that only out of coordinates of the output of the hash map are non-zero. The 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. Using 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 . 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. Overall, 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. - What is in Eq. 1 and Eq. 3? - is not formally defined ( ?) - *figure*, *table*, *sec.* --> *Figure*, *Table*, *Sec.*. - Notation mAP@x is not formally defined in Section 3.1 and 3.2. Also, is there notation overloading. How are defining the sparsity in the map and in Section 3.1 related? - 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? ------------------------------------------ Post rebuttal phase ------------------------------------------ Thank 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.