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 paper builds upon Siamese neural networks [Hadsell et al, CVPR06] and (f)ISta networks [Gregor et al, ICML10] to learn to embed inputs into sparse code such that code distance reflect semantic similarity. The paper is clear and refers to related work appropriately. It is relevant to the conference. Extensive empirical comparisons over CIFAR-10 and NUS/Flickr are reported. I am mainly concerned by the computational efficiency motivation and the experimental methodology. I am also surprised that no attention to sparsity is given in the experiments given the paper title. 

The introduction states that your motivation for sparse code mainly comes from computational efficiency. It seems of marginal importance. The r-radius search in an m dimensional space is nchoosek(m,r). With k sparse vectors, the same search now amount to flipping r/2 bits in the 1 bits and r/2 bits in the 0 bits in the query, i.e. nchoose(k,r/2)+nchoose(m-k, r/2). Both are comparable combinatorial problems. I feel that your motivation for sparse coding could come from the type of work you allude to at the end of column 1 in page 4 (by the way could you add some references there?).  

I have concerns about the evaluation methodology. In particular, it is not clear to me why you compare different methods with a fixed code size and radius. It seems that, in an application setting, one might get some requirement in terms of mean average precision, recall at a given precision, precision at a fix recall, expected/worst search time, etc and would validate m and r to fit these performance requirement. Fixing m and r a priori and looking at the specific precision, recall point resulting from this arbitrary choice seems far from optimal for any methods. Moreover, I would also like to stress that m, r are also a poor predictor of a method running time given that different tree balance (number of points in each node and in particular the number of empty nodes) might yield very different search time at the same (m,r). In summary, I see little motivation for picking (m,r) a priori.  

I am also surprised that no attention to sparsity is given in the experiments given the paper title. How was alpha validated? What is the impact of alpha on validation performance, in particular how does the validation error surface look like wrt alpha, m and r? It might also be interesting to look at the same type of results replacing L1 with L2 regularization of the representations to further justify your work. Also reporting the impact of sparsity on search time would be a must.