Sparse similarity-preserving hashing
Authors: Alex M. Bronstein, Guillermo Sapiro, Pablo Sprechmann, Jonathan Masci, Michael M. Bronstein
ICLR 2014

Abstract: In recent years, a lot of attention has been devoted to efficient nearest neighbor search by means of similarity-preserving hashing. One of the plights of existing hashing techniques is the intrinsic trade-off between performance and computational complexity: while longer hash codes allow for lower false positive rates, it is very difficult to increase the embedding dimensionality without incurring in very high false negatives rates or prohibiting computational costs. In this paper, we propose a way to overcome this limitation by enforcing the hash codes to be sparse. Sparse high-dimensional codes enjoy from the low false positive rates typical of long hashes, while keeping the false negative rates similar to those of a shorter dense hashing scheme with equal number of degrees of freedom. We use a tailored feed-forward neural network for the hashing function. Extensive experimental evaluation involving visual and multi-modal data shows the benefits of the proposed method.


Peer review:
[Review]:
This work presents a similarity-preserving hashing scheme to produce binary codes that work well for small-radius hamming search.  The approach restricts hash codes to be sparse, thereby limiting the number of possible codes for a given length of m bits.  A small-radius search within the set of valid codes will therefore have more hits, yet the total bit length can be lengthened to allow better representation of similarities.  According to the authors, this is the first application of sparsity constraints in the context of binary similarity hashes.

Overall I think this is a nice, well-motivated idea and corresponding implementation, with experiments on two datasets that demonstrate its effectiveness and mostly support the claims made in the motivation.  As a bonus, the authors describe a further adaptation to cross-modal data.

I still feel there are some links missing between the analysis, implementation and evaluation that could be made more explicit, and have quite a few questions (see below).


Pros:

- Well-argued idea for improving hashing by restricting the code set to enable targeting small search radii and large bit lengths

- Experiments show good system performance


Cons:

- Links between motivational analysis, implementation and evaluation could be made more explicit

- Related to that, some claims alluded to in the motivation don't appear fully supported, e.g. more efficient search for k-sparse codes doesn't seem realized beyond keeping r small


Questions:

- You mention comparing between k-sparse codes of length m and dense codes with the same degrees of freedom, i.e. of length log(m choose k).  This seems very appropriate, but the evaluation seems to compare same-length codes between methods.  Or, do the values of m reflect this comparison?  m=128 v. m=48 may work if k is around 10.  But I also don't see anything showing the distribution of nonzeros in the codes.

- pg. 4:  'retrieving partial collisions of sparse binary vectors is ... less complex ... compared to their dense counterparts':   Could this be explained in more detail?  It seems a regular exhaustive hamming search is used in the implemented system (especially since there appears to be no hard limit on k, so any small change can valid for most codes).

- The ISTA-net uses a sign-preserving shrink, and the outputs are binarized with tanh (also preserving sign) -- thus nonzeros of the ISTA-net can saturate to either +/- 1 depending on sign, while zeros are mapped to 0.  These are 3 values, not 2, so how are they converted to a binary vector, and how does this align with the xi(x) - xi(x') in the loss function (which seems to count a penalty for comparing +1 with 0 and a double-penalty for comparing +1 with -1)?

- Eqn. 4:  Distance loss between codes is L1 instead of L2, and there is no max(0, .) on the negatives (but still a margin M).  Are these errors or intended?

- I'm not sure how the PR curves were generated:  What ranking was used?

- Table 4 last line: Says alpha=0; it seems the sparsity term would be disabled if alpha=0, so not sure why results here are better than NN-hash instead of about the same?


Minor comments:

- Would have liked to see more comparing level of sparsity vs. precision/recall for different small r.  There is a bit of this in the tables, but it would be interesting to see more comprehensive measurements here.  It would be great if there was a 2d array with e.g. r on the x axis and avg number of nonzeros on the y axis, for one or more fixed m.

- How many layers/iterations were used in the ISTA-net?

- Fig 6 left, curves for m=128 appear missing for nnhash and agh2