Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper gives a new empirical approach for learning schemes for compressing high-dimensional neural representations into binary codes over a small number of dimensions. Given labeled examples and a fixed neural architecture with d-dimensional output, they give a two-phase algorithm for learning weights for the network, a low-dimensional projector to a k-dimensional subspace of R^d, and a binary "codebook" matrix B(C) mapping the k-dimensional subspace to R^L, where L is the number of classes. The goal is to do this for k as close to log_2(L) as possible while mostly preserving test accuracy.

Concretely, the embedding g maps any input x to the Boolean vector given by the entrywise sign of the k-dimensional projection of the network's output under x, and B(C) maps any such g(x) to an L-dimensional vector corresponding to the scores of the different classes. In the first phase of the algorithm, they simply run ERM to simultaneously find some weights, projector, and codebook, using a standard heuristic to get around the fact that B(C) is discrete-valued. In the second phase, they train the weights and projector further by essentially encouraging the embedding to align with the codebook. 

The distinguishing feature of this approach is that the codebook and embedding are learning in conjunction rather than separately. Empirically over ImageNet-1K, they found that under two natural decoding schemes, the resulting classifiers beat a number of baseline approaches that separately constructed a codebook and then learned an embedding. Additionally, the accuracy is only ~3% less than the standard ResNet50 baseline.

As other applications, they showed that for image retrieval, the learnt embedding can be used as a hash function, outperforming HashNet and GreedyHash. They also gave an application to out-of-distribution detection which is comparable to certain baselines but notably does not need samples from the out-of-distribution domain.
main_review: The approach put forth in the submission seems quite effective, given that they are able to compress down to 20-bit representations while taking a hit of only 3% relative to the compression-free baseline of 77% for ImageNet-1K. It would be interesting to see how this sort of drop in performance manifests when there are even more classes, some of them potentially underrepresented, e.g. ImageNet-22K as mentioned on the last page.

That said, it seems a bit weird that just running ERM on the weights/projector/codebook already beats the other codebook baselines to which the authors were comparing, and I'm slightly worried that this is simply because the baselines weren't very compelling to begin with. If there aren't better baselines out there, then should I think of the particular instance and class code parametrization in (1) as already giving a nontrivial win over previous works? It does feel like (1) is a very natural thing to try.

Nevertheless, the applications to retrieval and OOD detection, as well as the discovered taxonomy findings, suggest that the usefulness of LLC extends beyond just classification, and for these reasons I would recommend acceptance.
limitations_and_societal_impact: Yes, the authors adequately address the limitations, and as they note in the checklist, their work inherits the upsides and downsides of other efficient ML research.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of learning binary vector representations of instances and classes. We pick a small dimension k (the paper uses k=20) and aim to learn a k-dimensional binary vector for each input and each label. Compressing the data into small-dimensional binary codes like this is challenging, but provides many benefits in terms of the space usage (the representations are very small) and the time to do lookups and find nearby neighbors.

The paper presents a new method called LLC which simultaneously finds codewords for both inputs and labels without using any side-information. They claim (and I have no reason to doubt this) that this is the first time a method for this has been designed. LLC consists of two phases:

In the first phase, the LLC method learns a codebook (low-dimensional bianry code for each label) by using the popular Straight-Through Estimator technique to do empirical risk minimization. 

In the second phase, the ECOC framework is used to classify the inputs according to this codebook. The algorithm treats each of the k bits of the code completely separately, and hence solves k disjoint binary classification problems instead of one multi-class (with L or 2^k classes) problem. This gives an additive 2% improvement to accuracy over just solving the optimization problem to classify all k bits together, since out of the box optimization finds fairly suboptimal solutions when trying to classify a length k vector all at once. (In other words, the second phase uses a heuristic where sepaartely learning each of the k bits works better than learning all k at once for the current optimization software which is well-suited to doing binary classification.)

The resulting classification accuracy seems quite good: 68.82% of inputs are assigned exactly the same binary code as their label, and 74.57% are assigned a binary code which is closer to the code of their label than any other label.

The result of this binary code classification can now be used in a number of applications, including:
- the binary codebook can be naturally used to make a taxonomy visualization for the labels. 
- the system can be used for efficient (in terms of representation size and running time of retrieval) multi-class classification.
- out-of-distribution detection can be done by seeing whether an input is mapped to the same codeword as any label. (I'm confused about how effective this can be when the original inputs are only correctly mapped to the codeword of their label 69% of the time.)
main_review: The paper is generally well-written, although it refers to a number of different techniques as "standard" instead of explaining them in more detail, and I wasn't familiar with some of them, which made it hard to understand some steps of the algoritm. There are some English grammatical issues (including many sentences with extra commas added, and many sentence fragments in more technical sections), and I recommend that the paper is carefully reread before it is published.

Overall, I think this paper is solving an interesting problem, and it seems to have good accuracy. The main new ideas seem to be (1) using a somewhat clever heuristic to pick the codebook instead of using random codewords, and (2) splitting the multi-class classification task into k disjoint binary classification tasks. Otherwise, standard tools from the area are used. I think these are fairly natural ideas for this problem (and not huge breakthroughs or anything), but they nonetheless perform quite well. It's surprising to me that such an approach hasn't been taken before.

I have some questions for the authors:

1. In Section 4.1.1, it says "we evaluate the hamming 205 distance with all the L class codes and output the class with the least hamming distance". What happens if there is a tie, and multiple class codes have the same Hamming distance? Since we are dealing with only 20-dimensional vectors, I imagine this must be common (is it?). (Also note: Hamming should be capitalized since it's someone's name.)

2. There isn't much discussion of the running times in practice/applications. How long did your code run for? How much time is saved by making phase 2 take time independent of L?

3. Phase 2 seems to only consider two extremes: classify all k bits at once, or just one at a time (which does better). What if an intermediate option were used (such as classifying pairs of bits at the same time, i.e., transform the problem into k/2 independent 4-class classification problems)?

4. One could imagine doing Phase 2 instead by just using a high accuracy classifier which totally ignores the codebook (and then afterwards looking up the codeword from the codebook for each label). How much more accurate would this be? How much slower would it be? Are there other downsides of this approach?
limitations_and_societal_impact: Not really discussed, though I'm not sure what there is to say about this.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Low-dimensional binary codes are important for a variety of large-scale ml tasks, especially retrieval. This paper proposed a method called LLC for learning semantially meaningful low-dimensional biary codes. Compare to the existing literature, LLC can learn both class and instance codes together without side-information:  (1) couple the learning process of both feature and class embedding and capture the sematic structure better (2) naturally benefits downstream tasks like OOD.    
main_review: General Comments

The paper proposes a neat algorithm for low-dimensional binary code learning. Although it is a (very) well-studied area, authors present the related work or literature clearly and at the same time show the novelty of their proposal. I understand the paper has already done a wide range of applications and extensive ablations (breath), but I think there's a potential to improve the depth of the work -- what's special/principled about LLC's learnt binary codes, not the algorithm of how to learn it but the learnt codes? Details are in pros and cons.   

Pros:

- Writing/Pitching: The problem is well-motivated. Literature review for learning binary class and instance codes is very clear. 
- Algorithm: It is a smart 2-stage algorith, which first learns binary codes for class and instance together and then using the learnt class binary codes as the better than random "pseudo" labels to "correct" binary codes for instance.   
- Utility: Evaluations on classification, retrieval and especially OOD provide good coverage of popular applications; ablations and visualizations are helpful.

Cons:

- Algorithm integrity: There are two stages for learning class and instance binary codes, the paper evaluates how much lift from stage 1 only to stage 1+stage 2. I'm curious how impactful is the quality of class binary codes learnt from stage1 to instance binary codes learnt at stage 2? How to fix the problem if stage1 learns suboptimal/bad representations in some other applications or datasets?
- Depth: Authors have analyzed class binary codes qualitatively and find they learnt semantic structure because there's hierarchy for hash codes. That's probably the reason why stage 2 is helpful. But I think it would be very interesting to dig further on what's special about instance binary codes? Are they more uniform, more compact? Why they are better than the ones the baseline generated on retrieval/classifcaiton and especially ood?
 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a two-phase method for learning low-dimensional binary codes via the standard classification task without side-information. Specifically, binary codes for classes are learned via a surrogate classification task in the first phase. On top of that, instance codes are learned using the Error-Correcting Output Codes approach.
main_review: -      Pros
* Well written paper with extensive experimental results.
* Improvements are found on three downstream tasks in terms of computational efficiency.
-      Cons: 
* According to Equ. (2) and (3), both class codes and inference codes are learnt by minimizing the classification-related loss. However, there are some other important criteria of binary codes, such as low-bit correlation, robustness against transformations, and neighboring relationships. The authors should explain how those criteria are ensured in the proposed work?
* According to Equ. (2), the codebook B(C) is learned by minimizing the multiclass prediction scores and the ground-truth one in Phase 1. However, since B(C) should be the only variable in Equ. (2), the authors should explain the initialization of g(x). And how does it ensure the training stability, especially in the first several epochs, when the instance embeddings are not discriminative?
*Some typo errors could be found in the paper. For example, in Line 257, the word “iff” should be corrected as “if”.
limitations_and_societal_impact: According to question 1(b) in the Checklist, the authors describe the limitations and give potential solutions.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work propose a method for learning low-dimensional binary codes for instance and classes. It is appealing in classification with large scale number of classes. The method is claimed super-efficient in learning and able to ensure nearly optimal classification accuracy. The learnt class code discovers some intuitive taxonomy over subset of classes selected from ImageNet. The method is applicable in image retrieval and out-of-distribution detection.
main_review: The paper need to be organized more seriously. The intuition for designing the loss in eq(2) is not well explained, why chose(P.F(x,theta)) over B(P.F(x,theta))? Is this kind of loss firstly proposed here, if not, then is it following existing works? What is the reason to choose this kind of loss? 

There are too many words and too less figures. Some figures/ flow-charts are suggested to clearly show how to use the class code and the instance code in classification, image retrieval, and out-of-distribution detection.

Figure 1 shows the discovered taxonomy using the learnt class code, but there is no illustration on the knowledge discovered by the learnt instance code, figures are suggested to show the relationship between the class code and instance code.

On the experiments part. Most of the compared methods are before 2018, is there any other recently developed methods? Is the proposed method comparable with SOTA methods? 
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The problem considered in this paper, namely, of learning compression schemes for high dimensional neural networks, is a very natural and important problem. The paper achieves new, state-of-the-art results with new techniques for this natural problem. While the proposed technique lacks theoretical grounding, the empirical results are quite impressive. In discussions the authors sufficiently clarified concerns the reviewers had about the lack of good baselines for this field. Overall I think this is an interesting paper on an interesting topic and worthy of inclusion.
Decision: Accept (Poster)