We present a powerful new loss function and training scheme for learning binary hash codes with any differentiable model and similarity function. Our loss function improves over prior methods by using log likelihood loss on top of an accurate approximation for the probability that two inputs fall within a Hamming distance target. Our novel training scheme obtains a good estimate of the true gradient by better sampling inputs and evaluating loss terms between all pairs of inputs in each minibatch. To fully leverage the resulting hashes, we use multi-indexing. We demonstrate that these techniques provide large improvements to a similarity search tasks. We report the best results to date on competitive information retrieval tasks for ImageNet and SIFT 1M, improving MAP from 73% to 85% and reducing query cost by a factor of 2-8, respectively.
Summary: This paper contributes to the area of learning to hash. The goal is to take high-dimensional vectors in R^n resulting from an embedding and map them to binary codewords with the goal of similar vectors being mapped to close codewords (in Hamming distance). The authors introduce a loss function for this problem that's based on angles between points on the hypersphere, relying on the intuition that angles corresponds to the number of times needed to cross to the other side of the hypersphere in each coordinate. This is approximately the Hamming distance under a simple quantization scheme. The loss function itself forces similar points together and dissimilar points apart by matching the Hamming distance to the binomial CDF of the angle quantization. They also suggest a batching scheme that enforces the presence of both similar and dissimilar matches. To confirm the utility of this loss function, the authors empirically verify similarity on ImageNet and SIFT.
Strengths: The main idea, to match up angles between points on the hypersphere and Hamming distance is pretty clever. The loss function itself seems generally useful.
Weaknesses: First, I thought the paper was pretty difficult to understand without a lot of background from previous papers. For the most part the authors don't actually state what the input/output/goals are, leaving it implied from the context, which is tough for the reader. The overall organization isn't great. The paper doesn't contain any theory even for simplified or toy cases (which actually seems potentially tractable here); there is only simple intuition. I think that is fine, but then the empirical results should be extensive, and unfortunately they are not. 
Verdict: I think this work contains a great main idea and could become quite a good paper in the future, but the work required to illustrate and demonstrate the idea is not fully there yet. 
Comments and Questions:
- Why do you actually need the embedded points y to be on the unit hypersphere? You could compute distances between points at different radii. The results probably shouldn't change much.
- There's at least a few other papers that use a similar idea, for example 
Gong et al "Angular Quantization-based Binary Codes for Fast Similarity Search" at NIPS 2012. Would be good to discuss the differences.
- The experimental section seems very limited for an empirical paper. There's at least a few confusing details, noted below:
- The experimental results for ImageNet comparing against other models are directly taken from those reported by Lu et al. That's fine, but it does mean that it's hard to make comparisons against *any* other paper than the Lu paper. For example, if the selected ImageNet classes are different, then the results of the comparison may well be different. I checked the HashNet paper (Cao et al. 2017), and it papers that their own reported numbers for ImageNet are better than those of the Lu et al paper. That is, I see 0.5059 0.6306 0.6835 for 16/32/64 bit codewords vs Lu's result of 0.442 0.606 0.684, which is quoted in this paper. What's causing this difference? It would probably be a bit less convenient but ultimately better if the results for comparison were reproduced by the authors, and possibly on a different class split compared to the single Lu paper.
- The comparison against PQ should also consider more recent works of the same flavor as PQ, which themselves outperform PQ. For example, "Cartesian k-means" by Norouzi and Fleet, or "Approximate search with quantized sparse representations" by Jain et al. These papers also use the SIFT dataset for their experimental result, so it would be great to compare against them.