SoftHash: High-dimensional Hashing with A Soft Winner-Take-All Mechanism

Thank you for your time and helpful comments. We address the questions and concerns below:

R-W1: Thanks for your detailed comments. In this paper, ConvHash is the classical LSH method, it generates the hash code of the input data sample $x$ according to $y = sgn(Mx)$, where $*M* \in \mathbb{R}^{m \times k}$ is a random matrix. $k$ is the hash length. We have changed 'ConvHash' to 'LSH' for simplicity. SoftHash-1 and SoftHash-2 have different weight initialization methods, uniform initialization for SoftHash-1, and Gaussian initialization for SoftHash-2. We have added a description of them in Table 2 of the paper.

R-W2: Thanks for your comments and recommendation. In this paper, we extend our comparison beyond conventional methods like SH and ITQ, as our proposed SoftHash is an unsupervised bio-inspired hashing method. Therefore, our experiment includes a comparison with other bio-inspired hashing methods. SGH, DGH and COSDISH are well-known hashing methods. We are conducting experiments to evaluate the performance of SGH on image retrieval. Other works have been concluded in the introduction and related works of the paper. Currently, experimental results are shown in the Table R-W2.

Table R-W2

R-Q1: The main differences are (1) the bio-inspired hashing methods project input data into high-dimensional representations, whereas conventional hashing methods map the data into low-dimensional representations; (2) the bio-inspired hashing methods sparsify the high-dimensional representation using a winner-take-all mechanism, whereas conventional hashing methods preserve a dense representation. In general, the high-dimensional sparse representations are always more robust to encoding noisy input data [1]. With the help of the bio-winner-take-all mechanism, the representations can also achieve a good performance in semantic clustering.

[1] How can we be so dense? The Benefits of Using Highly Sparse Representations

R-Q2: Most of the bio-inspired hashing codes are generated with the winner-take-all mechanism. The kernel assumption of the winner-take-all mechanism is that with an input vector $x$, if the semantic information of attribute $x_i$ is dominant over some other attribute, $x_i$ has stronger discriminative powers to represent $x$ and cluster $x$ [1]. This allows the most semantical features can be more utilized than other noisy features in the hash mapping. With different initialization of synaptic weights and different hash functions, capturing different dominant semantic information, can be learned with the bio-inspired learning rule. In this way, the data samples’ semantics are kept in the hash codes. We visualize the semantic capturing capabilities of bio-inspired hashing codes by comparing them to traditional hashing algorithms in Figure 3 in the paper. It is obvious that the cluster structure obtained by $*SoftHash*$ is more compact compared to traditional $*LSH*$ when using the same hash length. It indicates that the hash codes generated by $*SoftHash*$ effectively capture more semantic information of data samples than those of traditional LSH.

[1] Revisiting winner-take-all all (WTA) Hashing for Sparse Datasets

R-Q3: As the same as most traditional LSH methods, bio-inspired hashing methods construct only a binary hash index for the nearest neighbor search. No other additional storage is required, and the binary form of the hash codes is very friendly to storage and search, bringing about an economic memory for semantic similarity computing.
With respect to the index data structure, compared to traditional LSH methods with dense hash codes, bio-inspired methods use sparse hash codes to perform similarity search. In a hamming space, sparse vectors can be computed much faster than dense vectors. What's more, as introduced in the previous response, the winner-take-all mechanism ensures the output representations of bio-inspired hashing methods convey more semantic information. Therefore, with the above, bio-inspired hashing methods can implement fast retrieval/semantic computing.

R-Q2: We have changed "ConvHash" to "LSH" in the paper.

R-Q3: "Sokal and Michener similarity function" is the Hamming similarity. We agree with you. We have made the modifications to the relevant content.

R-Q4: In Table 2, we use mean average precision (MAP) for evaluation when the code length is larger. In the image retrieval task, we use MAP to measure the hamming ranking quality of various code lengths.

R-Q5: Your observation is keen, which enlightens us a lot. Next, we will try to explain Oja's rule from the view of gradient descent. First, let us look at the following equation

$

\frac{\partial|(x_i - w_{j}^iy_j)|^2}{\partial w_j^i } = -2y_j (x_i - w_{j}^iy_j)

$

It is interesting to find that the gradient of $\|(x_i - w_{j}^iy_j)\|^2$ is the same as the Oja rule (Eq (2)).

The $w_{j}^{i}$ in the numerator is just a regularization term that controls $w_{j}^{i}$ not to grow too big. If we ignore this term, the update rule of Oja can be rewritten to minimize the loss function as

$

\underset{w_j^i}{\text{minimize}} \sum_{i=1}^d |(x_i-y_j)|^2

$

where $y_j=\sum_i x_i w_{j}^i$. It is easy to see the loss function expects the output neuron ($y_j$) can act similarly as most of the input neurons ($x_i$s) as possible. Therefore, at the end of this unsupervised learning, $y_j$ will be determined by the most dominant correlated $x_i$s. In other words, the input samples with similar values on the dominant semantic features will have similar hashing values and be hashed into the same bucket.

This finding is very interesting.

We will add it to our final paper.

Thanks for your inspiration.

R-Q6: We have added SignRFF as an important reference in our section of related work. Next, we are going to do our best to implement SignRFF as a comparative baseline of our experiment in our final version.

Thank you again for your valuable feedback.

Thank you for your thoughtful comments.

R-W1&W2 Our algorithm design considers a lot about "winner-take-all" dilemma [1]. Many winner-take-all hashing methods like BioHash may fall into the dilemma, where the semantic representation of the learned hash codes may be dominated by the majority class, leading to the semantics loss of the minor classes, which greatly limits its ability to catch the semantic information of the input data.

In the energy function of BioHash (Eq.(10)), it is clear that each input sample belongs to only one neuron. It means only the output neuron with the largest value can be updated during the learning process, leading to the dilemma. For our hashing method, to alleviate this dilemma, we introduce a soft winner-take-all mechanism for learning the hash function. In contrast to the mentioned methods using a "hard" winner-take-all mechanism, our method makes non-winning classes not fully suppressed in the learning process. By assigning a credit score $\frac{e^{u_j+b_{j}}}{\sum_{l=1}^m e^{u_l+b_{l}}}$ in Eq (5) to each class, our method enables the minor classes to have a chance to influence the representative learning, making the learned hash codes improved with more semantic information. We have a detailed description of the connections and differences between SoftHash and BioHash in Appendix B.

$\frac{e^{u_j+b_{j}}}{\sum_{l=1}^m e^{u_l+b_{l}}}$ in Eq (5) is in the form of softmax function. The reason why we use softmax here is to assign each class with a normalized credit score. Compared to other normalization functions, softmax is more general and smooth. The biological plausibility of "softmax" sources from the lateral inhibition between neurons, is mentioned in [2,3,4].

[1] Domain Adaptive Semantic Segmentation without Source Data

[2] SoftHebb: Bayesian inference in unsupervised Hebbian soft winner-take-all networks

[3] Bayesian computation emerges in generic cortical microcircuits through spike-timing-dependent plasticity

[4] Optimality of short-term synaptic plasticity in modeling certain dynamic environments

R-W3: (1) SoftHash-1 and SoftHash-2 have different weight initialization methods, uniform initialization for SoftHash-1, and Gaussian initialization for SoftHash-2. The reason we believe that SoftHash-2 performs better is that Gaussian initialization is more effective in breaking symmetry compared to uniform initialization, leading to more representative feature combinations at the algorithm's beginning. In Gaussian initialization, weights are randomly sampled from a normal distribution, whereas in uniform initialization, weights are drawn from a uniform distribution. Gaussian initialization ensures that each neuron learns distinct features from the beginning, and improves the network's ability to capture input data characteristics during the learning process, enabling the learnable synaptic weights to generate more representative hash codes. We have added an ablation study in section 4.2 and descriptions of SoftHash-1 (SoftHash-2) in Table 2. We are sorry for the typo. In our study, the batch size is 1024 for all three datasets. It is determined by maximizing the usage of GPU memory. (2) For ease of comparison, we repeat the parameter setting of the previous work[1] for BioHash. For SoftHash, we have tuned the temperature parameter $T$ with {5,10, 15, 20} and set it to 10 according to its best performance.

[1] Unsupervised Learning by Competing Hidden Units

R-Q1: BioHash does not have the bias term. From the view of neuroscience, neuron activation occurs when the input signals reach a certain threshold, which is regarded as the neuron bias. Different neurons have different thresholds. Therefore, in order to precisely model the activities of neurons, the bias term should be seriously considered in the model. In practice, without the bias term, the learning algorithm may find it hard to fit the input samples, especially when the diversity of input features is large. As a result, the learned hash codes may lose effectiveness in finding similar data samples as shown in Table R-Q1.

Thank you for your kindly reply.

R-W3: We agree with your point. To fully study if symmetry is the key factor, we will add a result of the initialization method of the symmetric uniform distribution, which has the same scale range as the Gaussian distribution, in the final paper.

R-Q4: You are right. In our work, longer codes (k=256, 512) show better retrieval performance on three datasets (Appendix D.2). We will add k=1024 to make the results more complete in the final version.

Thanks for the reply. Some background and motivation are more clear to me now. I'm glad that my comments are helpful to improve your work.

W3: If symmetry might be the key factor here, why not using a symmstric uniform distribution as initialization? In practice Gaussian is more common, so proposing the (positive-only) uniform initialization may not offer much contribution or insights here.

Q4: What I meant is that I'm curious about the comparisons when the embedding dimension is larger. Now you only presented the results up to k=128. How about k=256, 512, 1024 etc? Longer codes are useful when high precision and recall are required. Please consider adding them to make the results more complete.

Thank you for your thoughtful comments, which prompt us to improve our manuscript. We would like to address your concerns and answer your questions in the following.

R-W1: We have added the description of the train/test set split in the $*Datasets*$ part of section 4.1 and rewritten the experiment settings of section 4.1 and section 5.1 in $\textcolor{blue}{BLUE}$ color.

R-Q1: To further illustrate the effectiveness of our algorithm, in Table R-Q1, we add the experimental results of "10,000 images with 10 classes". It shows that when the query size becomes large, SoftHash still outperforms other hashing methods with different hash lengths.

Table R-Q1

R-Q2: In this paper, we focus on designing a data-dependent hashing algorithm $*SoftHash*$ to encode dense continuous features into sparse binary codes for fast searching, meanwhile, adapting semantic knowledge from input data features to output hash codes for semantic clustering. Considering the above, we do not choose class-label-based evaluation, which is a bit coarse to reflect the effect of semantic clustering of our algorithm. On the other hand, Euclidean-distance-based evaluation is selected, which is more soft and refined to assess the semantic representativeness of output hash codes. Moreover, some datasets like Glove naturally have no class labels, which can not be conducted with class-label-based evaluation.

R-Q3: The reason we set the output dim as 2000 is motivated by the fact that in the factory circuit of Fruit Fly there are approximately 2000 Kenyon cells for information encoding [1]. Considering this biological basis, 2000 is used as the output dim in the experiments. "2000 is high" does not mean that the output dimension is higher compared to the input dimension. Here, we say "2000 is high" which means that compared to the traditional LSH methods like [2,3] hashing data into dense low-dimensional(d < 2000) space, our method's 2000 output dimension is a higher number. The main objective of the experiments is to show the superiority of our sparse high-dimensional hash representation over other dense low-dimensional hash representations.

[1] A neural algorithm for a fundamental computing problem; [2] Spectral hashing; [3] Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.

R-Q4: SoftHash-1 and SoftHash-2 have different weight initialization methods, uniform initialization for SoftHash-1, and Gaussian initialization for SoftHash-2. The reason we believe that SoftHash-2 performs better is that Gaussian initialization is more effective in breaking symmetry compared to uniform initialization, leading to more representative feature combinations at the algorithm's beginning. In Gaussian initialization, weights are randomly sampled from a normal distribution, whereas in uniform initialization, weights are drawn from a uniform distribution. Gaussian initialization ensures that each neuron learns distinct features from the beginning, and improves the network's ability to capture input data characteristics during the learning process, enabling the learnable synaptic weights to generate more representative hash codes. We have added an ablation study in section 4.2 and descriptions of SoftHash-1 (SoftHash-2) in Table 2.

R-Q5: Thank you for your comments. We have rewritten the description of the experiment settings in Section 4.1 and Section 5.1, including train/test split in the $*Datasets*$ part of Section 4.1. The output dimensions for the word search experiments were set to 2,000. It has been added in Appendix E.1.

R-Q6: Thank you for your correction. We have made the modifications in the references.

Thank you for your valuable comments!

R-W1: Thank you for pointing out this excellent reference. We are in the process of reimplementing MONGOOSE and testing it on the evaluation benchmarks we have used. We will add the experimental results to our paper once it is available.

R-W2 & Q1: Thank you for your comments. The key idea of SoftHash originates from Drosophila’s olfactory circuit [3], which utilizes sparse spike codes to convey the information of dense sensory signals. In particular, Hebbian-like rules are often used to learn such sparse codes. In this paper, our Hebbian-like learning rule is designed as $y_jx_i-y_ju_jw_j^i$, which works similarly to the Oja rule [4]. If the input and output are highly correlated, the first term will enhance the connection weight between the input and output neuron; The second term will give a punishment update when the weight is already large enough. The item $y_j$ is computed according to the Bayesian posterior probability, which allows every possible hash class to be able to influence the update at each iteration. In this way, our hash function can be trained in a soft manner.

Unlike randomized hash functions, the theoretical bounds for learning-based hashing methods are often lacking [5]. Although recently [2] proves a correctness bound for its tree-learning-based hashing method, its theoretical analysis cannot be easily applied to other learning-based methods, such as neural-network-based hashing methods. The reason is that [2] is a white-box algorithm, in which independence and randomness are introduced by the authors’ delicate design. With the well-designed randomness setting, the theoretical bound can be achieved as expected. However, neural-network-based hashing methods like ours are black-box algorithms, in which the function weight may converge to any saddle point with unknown probability. Therefore, it is challenging to provide a theoretical guarantee for our method. However, from the view of machine learning, our algorithm can be treated as an energy-based model as described in Equation (7) in the paper. We have proved that our learning rule can consistently reduce the energy value in Appendix A, which ensures the convergence of our method. Furthermore, we also provided an analysis on the time complexity of the algorithm.

[1] MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training [2] Learning to Hash Robustly, Guaranteed [3] A neural algorithm for a fundamental computing problem [4] A Simplified Neuron Model as a Principal Component Analyzer [5] Learning to Hash for Indexing Big Data—A Survey

R-Q2: Thank you for your comment. In our experiments, most of the algorithms can converge to a good result within 20 epochs.