LLC: Accurate, Multi-purpose Learnt Low-dimensional Binary Codes
Authors: Aditya Kusupati
Matthew Wallingford
Vivek Ramanujan
Raghav Somani
Jae Sung Park
Krishna Pillutla
Prateek Jain
Sham M. Kakade
Ali Farhadi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Classification
Efficient Classification
Error Correcting Output Codes
Binary Codes
Retrieval
Large-scale Classification

Abstract: Learning binary representations of instances and classes is a classical problem with several high potential applications. In modern settings, the compression of high-dimensional neural representations to low-dimensional binary codes is a challenging task and often require large bit-codes to be accurate. In this work, we propose a novel method for $\textbf{L}$earning $\textbf{L}$ow-dimensional binary $\textbf{C}$odes $(\textbf{LLC})$ for instances as well as classes. Our method does ${\textit{not}}$ require any side-information, like annotated attributes or label meta-data, and learns extremely low-dimensional binary codes ($\approx 20$ bits for ImageNet-1K). The learnt codes are super-efficient while still ensuring $\textit{nearly optimal}$ classification accuracy for ResNet50 on ImageNet-1K. We demonstrate that the learnt codes capture intrinsically important features in the data, by discovering an intuitive taxonomy over classes. We further quantitatively measure the quality of our codes by applying it to the efficient image retrieval as well as out-of-distribution (OOD) detection problems. For ImageNet-100 retrieval problem, our learnt binary codes outperform $16$ bit HashNet using only $10$ bits and also are as accurate as $10$ dimensional real representations. Finally, our learnt binary codes can perform OOD detection, out-of-the-box, as accurately as a baseline that needs $\approx3000$ samples to tune its threshold, while we require ${\textit{none}}$. Code is open-sourced at https://github.com/RAIVNLab/LLC.

LLC: Accurate, Multi-purpose Learnt Low-dimensional Binary Codes
Aditya Kusupati",
Matthew Wallingford", Vivek Ramanujan', Raghav Somani .ae Sung Parki, Krishna Pillutlal, Prateek Jain", Sham Kakadet and Ali Farhadi
UUniversity of Washington, 'Google Research India
(kusupati pecpuppti,cc2244,,11 raccx244,aaaa,,rreae raghavs,, aapark96,piiie pillutla, sham, ali) washington edu, prajainggoogle.com
Abstract
Learning binary representations of instances and classes is a classical problem with several high potential applications. In modern settings, the compression of high-dimensional neural representations to low-dimensional binary codes is chal- lenging task and often require large bit-codes to be accurate. In this work, we propose a novel method for Learning Low- -ww-dimensional binary Codes (LLC) for instances well as classes. Our method does not require any side-information, like annotated attributes or label meta-data, and learns extremely low-dimensional bi- nary codes (=z bits for ImageNet-1KK K). The learnt codes are super-efficient while still ensuring nearly optimal classification accuracy for ResNet50 on ImageNet- 1K. We demonstrate that the learnt codes capture intrinsically important features in the data, by discovering an intuitive taxonomy over classes. We further quantitatively measure the quality of our codes by applying to the efficient image retrieval as well -ittr---dittibttion (OOD) detection problems. For ImageNet- 100 retrieval problem, our learnt binary codes outperform 16 bit HashNet using only 10 bits and also are accurate 10 dimensional real representations. Finally, learnt bi- nary codes can perform OOD detection, out-of-the-box as accurately as a baseline that needs 3000 samples tune its threshold, while require none. Code is open-sourced at https: /ttp//gtttttt /gggttubbb.....g com/ www../oo.//..i.... RRAIVNLbbLLLC
Introduction
Embedding data in low-dimensional binary space is long-standing machine learning problem [56]. The problem has received a lot of interest in the computer vision (CV) domain, where the goal is to find binary codes that capture the key semantics of the image, like, objects present in the image or interpretable attributes. Section 2 covers the literature on learning binary codes and their applications.
In addition to learning semantically meaningful representations of the instances, low-dimensional binary codes allow efficiency variety of large-scale machine learning (MI.) applications. Low- dimensional codes crucial in extreme classification with millions of classes [8, 30, 15) and also critical in efficient large-scale retrieval settings [38, 16, 59].
Compressing information into binary codes is challenging due to its highly non-smooth nature while requiring the preservation of relevant information in an instance/class. This might explain the lack of good classification accuracy for existing classification based embedding techniques [28, 13]. To address that, traditional methods often relied on inde-information like attributes to construct class codes and then that to learn the instance codes [18, 1].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Learning binary embeddings can be posed in variety of formulations like pairwise optimization [34] or unsupervised learning [11, 50], in this work we focus on learning binary codes using given labeled multi-class dataset, e.g., ImageNet-IK, This allows us to couple the representation (code)
learning of both instances and classes thus enabling us to capture the underlying semantic structure efficiently to assist in downstream tasks like classification, retrieval etc.
We propose LLC, a method to learn both class and instance codes via the standard classification task and its setup without any inde-information. Our Learning Low-dimensional binary Codes (LLC) technique, formulates the embedding (code) learning problem as that of learning oow-dimensional binary embedding of a standard deep neural "backbone". Instead of directly training for the low- dimensional binary instance codes, we propose a two-phase approach. In the first phase, LLC learns now-dimessional (k-bit) binary codes for classes that capture semantic information through a surrogate classification task. Then in the second phase, LLC uses these learnt class codes as an efficient alternative to learning instance codes in sub-linear cost (in the number of classes, T.) using the Error- Corre-ccnnn Output Codes (ECOC) approach [19]. This two-phase pipeline helps in the effective distillation of required semantic similarity between instances through the learnt class codes. For example, on ImageNet-IK IK with ResNet50, LLC is able to learn tight 20-bit codes that can be used for efficient classification and achieve 74.5% accuracy compared to the standard baseline 77% on ImageNet- IK (Section 4.1). Furthermore, we observe that the learnt 20-bit class codes capture intuitive taxonomy over classes (Figure 1) while the instance codes retain the distilled class similarity information useful in efficient retrieval and OOD detection.
Retrieval. To further study, the effectiveness of our learnt binary codes, we apply them to hashing- based efficient retrieval, where the goal is to retrieve a large number of similar instances with the same class label in top retrieved samples. Deep supervised hashing is widely studied problem with several recent results [9, 53] which are designed specifically for the learnt hashing-bass retrieval. Interestingly, our learnt instance codes through the LLC routine provide strikingly better performance while not being learnt explicitly for hashing. For eg., using AlexNet, with just 32-bit codes we are can provide 5.4% more accurate retrieval than HashNet's 64-bit codes on ImageNet-100 (Section 4.2).
OOD Detection. We similarly apply LLC based learnt binary codes to detect OOD instances [26]. We adopt simple approach based on our binary codes: if an instance is not within Hamming distance of to any class codes, we classify it as OOD. That is, we do not fine-tune our OOD detector for the new domain, which is critical in practical settings. In contrast, baseline techniques for OOD detection require few samples (eg., 2s 3000 for ImageNet-750) from the OOD domain to fine-tune thresholds, while we require samples yet reaching similar OOD detection (Section 4.3).
In this work, we make the following key contributions:
LLC method to learn semantically-rich low-dimensional binary codes for both classes & instances. Show that the learnt codes enable accurate & efficient classification: ImageNet- 1K with 20-bits. Apply LLC image retrieval task, and demonstrate that it comfortably outperforms the instance code learning methods for hashing-based based retrieval on ImageNet-100)
Finally, use codes from LLC for strong & sample efficient OOD detection in practical settings.
2 Related Work
Binary class codes were originally aimed at sub-linear training and prediction for multi-class classifi- cation. The Prroe-Correcting Output Codes (ECOC) framework [19, 3, 20] reformulated multi-class classification as multi-label classification using k-bit codes per class (codebook). The learning of optimal codebook is NP-complete [14] which lead to use of random codebooks [28, 13] in traditional ML. However, there were a few codebook learning [5, 64, 58, 4] and construction schemes using side-information from other modalities [1]. The lack of a strong learnable feature extractor often de- terred the gains these codebooks provide for the classification and effective learning of instance codes. Attribute annotations can also help in constructing class codes [2]. These binary codes are either explicitly annotated [21] discovered [47, 22]. Attributed based learning also ties into leveraging the class codes for zero/few-sht learning [36, 37, 1, 44] expecting some form of interpretability.
Most methods that use class codes as supervision can produce instance codes [19]. However, the standalone literature of instance codes comes from requirements in large-scale application like retrieval (hashing). In the past, most hashing techniques that created instance codes were based on

---

random projections [16, 13, 12], semantics [51, 18] or learnt through metric learning [34, 33, 43, 32], clustering [57, 50] and quantization [23]. Deep learning further helped in learning more accurate hashing functions to generate instance codes either in an unsupervised [11, 52] or supervised [38, 9, 53, 62] fashion. We refer to [39, 63, 56] for a more thorough review on deep hashing methods.
Finally, umbedding-basee classification [13, 61, 8, 24] enables joint low-dimensional representation learning for both classes and instances with an eye on sub-linear training and prediction costs. After distilling the key ideas from the literature, we aim to a) learn semantically rich low-dimensional representations for both classes and instances together. b) have these representations in the binary space, and c) do this with minimal dependence on side-informe informmafonnnnnn or metadata.
LLC, to the best of our knowledge for the first jointly learns low- cow-dimensional binary codes for both classes and instances using a surrogate classification task, without any side-information (Section 3). The learnt class codes capture intrinsic information at the semantic level that helps in discovering an intuitive taxonomy over classes (Figure 1). The learnt class codes then anchor the instance code learning which results in tight and accurate low-dimensional instance codes further used in retrieval (Section 4.2). Finally, both the learnt class and instance codes power extremely efficient yet accurate classification (Section 4.1) and out-of-distribution detection (Section 4.3).
3 Learning Low-dimensional Binary Codes
The goal is to learn a binary embedding (code) function g: X' (-1, where X' is the input domain and is the dimensionality of the code. We focus on learning embeddings using a labelled multi-class data [28]. That is, suppose we are given a labelled dataset D (111,91),.... (arny yo where v; E X' is an input point and yı E [L] is the label of z; for all E [n]] Then, the goal is to learn an instance embedding function g: + -13* and class embeddings hy E [+1,-1}+ for all q E [L] such that g hy, and g(x;) g(rz) ) if and only if y: リソ-
Intuitively, for large-scale scale datasets, g(x) and h2 should capture key semantic information to provide accurate classification, thus allowing their use in application domains like retrieval or OOD detection. Note that while we present our technique for learning embeddings using multi-class datasets, applies more generally to multi-labeled datasets as well.
Instance and Class Code Parameterization. For learning such embedding function, we assume access a deep neural architecture 0f:: X' + Rd that maps the input x X to d-dimensional real-valued representation. By is a learnable parameterization of the network; we drop 0y from F wherever the meaning clear from the context. For example, ResNet50 is one such network that encodes 224 x 224 RGB images into d = 2048 dimensions.
Now, given network F and E X. we formulate embedding function of x and the corresponding multiclass prediction scores ÿ E 7,4 as:
gxx)
(PP-F(z;8p)) B(C) g(z)
where E kxd maps F(z) into k-dimensions and B(a) = sign(a) E f+1, -13 is the standard binarization/sign operator applied elementwise (with the assumption sign(0) +1). Finally, Ce e R4*k and ÿ B(C)- g(x) represents the scores of each class for an input x. Note that for class E [L], B(C,) (where C₁ represents the f-th row of C) is the learnt binary class embedding (code) of class l [L]. and g(x) B(P F(x; ())) is the learnt instance embedding (code) of instance Note that (1) is a general purpose formulation for the problem of learning class and instance codes.
3.1 The LLC Method
Phase 1: Codebook Learning B(C). Given labelled examples D, we standard empirical risk minimization to learn a multi-class classifier, i.e., we solve
Σ CBB(CC) (P (PF((x00)) vi)
min C.P.0F
(TDD
where L: RR x [7.] + R2 is the standard multi-class softmax cross-entropy loss function. This is a standard optimization problem that can be solved using standard gradient descent methods other
3

---

sub-gn gradient based optimizers. However. one challenge is that B(C) is binary matrix and B is binary function, so the gradients are almost everywhere. Instead, we use the
Estimator (STE) [6] technique popular in binary neural networks domain [48], to optimize for C through the binarization, Intuitively, STE uses binarization/sign function in the forward pass, but in the backpropagation phase, it allows the gradients to flow straight-throug as if it were real-valued. The codebook, (C)) refers to the collection of k-bit class codes learnt in this process.
For ImageNet-IK, we learnt unique binary codes, B(C;), for every class & E [L] of the 1000 classes using only 20-bits, only twice the information-theoreiicc limit. As with the class representations from a linear classifier, these class codes do capture intrinsically important features that help in discovering intuitive taxonomy over classes (Section 3.2) among various applications (Section 4).
Phase 2: Instance Code Learning B(P.. F(x; 0F)). Several existing techniques model and P in different ways to learn an embedding function similar to (I), However, these methods often try to only learn instance codes and have challenges of applications because optimization problem (2) is challenging and might lead to significantly sub-optimal classification error. For example, for ImageNet- IK classification with ResNet50, the accuracy for our trained model (20-bits) at this stage is 72.5% compared to the standard 77%.
maintaining high accuracy [9, 11] in a variety
To remedy this, we further optimize our embeddings using the ECOC framework [19] for multi-class classification, which essentially transforms the multi-class problem into multi-label problem, which in turn k independent binary classification problems. That is, we use the k-bit codes learnt for each class as the supervision to further train F( F(:8pp) and P:
min Pp.P
Σ (=
Σ BCE (o F(z;0f)); (B(C) (BCC
(3)
where a is the sigmoid/logistic function, BCE is the binary cross-entropy loss between the j-th bit of instance 2, embedding, and the j-th bit extracted from the class embedding of it's label y (the function 2 + (z + 1)/2 is used to map {+1,- -1} to {1, 0} to make it simple binary classification problem per each bit). We use gradient based optimization learn 0p and P. As mentioned earlier, ECOC framework allows us to correct errors in classification. For example, with just 20 bits on ImageNet- 1K dataset, the method now achieves 74.5% accuracy with ResNet50 backbone.
The advantage of this two-phase pipeline where we start with a codebook learning for classes is that the cost of learning instances codes reduces a bottleneck of k-dims (< L) instead of the usual L. Furthermore, these learnt low-dimensional binary codes for both classes and instances help in large-scale applications via efficient classification and retrieval (see Section 4). Note that, unlike attribute-base based methods [37], we do not require additional meta-data, but learn binary codes by only using the standard classification task. This also circumvents the potential instabilities of pairwise optimization in instance binary code learning which often leads to poor class codes due to codebook collapse. the end of LLC routine, we have learnt the instance codes, B(P F(x; 0r)), and class codes, B B(C) to be used for downstream applications. Algorithm 1 presents L.L. in full.
Algorithm 1 The LLC Method
Input: D, F and B
Output: C, P and OF
1: Codebook Learning - B(C): Solve (2) using ERM and STE to get C, P and Op-
C,P.0F t- arg min C,P,8
Σ C(B(C) (P F(x;0p)) w)) (RWA)ED
2: Instance Code Learning B(P F(:;6))) Further optimize P and Op by solving (3) using ECOC framework and ERM by fixing C-
0p, P. t- arg min
Σ
Σ
BCE (o F(x; (B(C + +1) /2)
Pr.P
(ELD)EDD==

---

Overall, we present simple yet scalable method to learn low- -iw-dmmessional (exact) binary codes for both classes and instances which in turn could power multi-class classification with sub-linear costs (in terms of I.) and efficient retrieval for large-scale applications. Using our method, we can consistently learn unique low-dimensional binary codes for all 1000 classes ImageNet- K using only 20-bits (which is twice the information-theoreee limit of [loga (1000)]). Next, we discuss the learnt codebook's intrinsic information about the classes and their structure.
3.2 Discovered Taxonomy and Visualizations
called frog
bulifro
tree frog
American chameleon
tench
friled Uizar
agama
African chameleon
common iguana
Africnn cracodit
Komado oragon
banded pocko
green Rzard
magple
lggatrr lard
common news
whiplal
great grey anl
bubbil
chickades
house finch
soldfinch
indigo bunting
bald
kite
vulture
ectricn
cit
spatted zalaranndr
European fire selamander
Giaa montter
mud turtee
terrapin
logger hebd
great white shark
cathcrback turt
hammerccd
stingey
goldfich
rebin
combligg
cock
turt
Figure 1: Discovered laxonomy over 50 classes of ImageNet-Ik IK using the learnt 20-bit class codes, Related species well clustered while pushing away unrelated ones. Figure 3 Appendix D contains the codebook.
After learning the 20-bit binary codebook for 1000 classes of ImageNet-IK, we used the class repre- sentation from (C) of the first 50 classes to discover intuitive taxonomy through agglomerative clustering [42]. Figure shows the discovered hierarchy. This hierarchy effectively separates birds from amphibians: frogs and chickens
extremes of the taxonomy and brings species with shared similarities closer (lizards crocodiles; marine life). While the taxonomy is not perfect, the 20-bits do capture enough important information that can be used downstream.
Figure 2 shows the pair-wise inner-product heat maps for all the 1000 classes using 20-bits and 2048-dimensional real representation; the comparison reveals that 20-bits indeed highlights the same substructures as the higher dimensional veal-valued embeddings. Appendix D has a more detailed discussion about quantitatively evaluating the discovered hierarchy and more visualizations.
0.75
0.8
0.6
0.25
0.00
0.2
0.25
-0.30
0.0
(a) 20-bit codes
(b) 2048-d real representations
Figure 2: The pair-wise inner product heat maps of class representations learnt 20-bit codes & b) learnt 2048 dimensional real representations for 1000 classes in ImageNet- Similar structures are highlighted both heatmaps and often correspond to local hierarchy present in the classes thus making a case that 20-bit codes distill enough information to capture hicrarchy of the classes.
4 Applications
In this section, we discuss three applications the learnt low-dimensional binary codes: 1) efficient multi-class classification (Section 4. 2) efficient retrieval (Section 4.2), and 3) out-of-the-box
5

---

out-of out-of-distribution (OOD) detection (Section 4.3). We also present ablation studies on codebook learning, feature separability and classification (Section 4.4).
4.1 Efficient Multi-class Classification
Recall that the proposed LLC algorithm outputs a) the learnt class codes (codebook), B(C) and b) an encoder that produces instance codes, B(P F(x:0)x) for æ. We define class codebook as a collection of L binary vectors, one for each class in the dataset, that can then be used for classification of a test instance x. We can use several "decoding" routines classify an instance x, given its encoding and the learnt codebook. Below we discuss two decoding schemes that are diametrically opposite in terms of the inference cost. Also, note that the standard linear classification with real-valued representation and classifiers scale as (L) in terms of computational complexity and model size.
4.1.1 Decoding Schemes
Exact Decoding (ED). Exact Decoding scheme expects the Hamming distance between the gen- erated instance code, B ((P f))). and the ground truth class code, B(C,) to be exactly 0. That is, we can hash the class codes in table, and then ED requires only (1)) hash-table lookup for given instance. Consequently, the inference time for ED is nearly independent of L. Naturally, the decoding scheme is highly stringent and would misclassify the ground truth code do not match in even a single bit. Surprisingly, this highly efficient decoding scheme still provides non-trivial accuracy (see Table and Section 4.1.2).
instance if the instance binary code and
Minimum Hamming Decoding (MHD). Minimum Hamming Decoding is akin to the Maximum Dot Product used by standard linear classifiers. For an instance code, we evaluate the Hamming distance with all the L class codes and output the class with the least Hamming distance. Note that the Hamming distance over binary codes can be computed using XOR operations that are implemented significantly more efficiently than the floating-point operations [48]. Even though, technically, computational complexity and model size of MHD scales OL)) but the real-world implementations should be an order of magnitude faster than standard classifiers. In fact, for large number of classes L, the efficiency of MHD can be further improved by using approximate nearest neighbour search [16, 7, 40). Appendix A has the mathematical presentation of the decoding schemes.
See Section 5 for more discussion on potential decoding schemes. Also see Section 4.4 for ablation studies about the two decoding schemes along with feature separability (linear vs Hamming).
4.1.2 Empirical Evaluation
ImageNet-IK [49] is widely used image classification dataset with 1000 hierarchical classes. Our classification experiments use ResNet50 [25] and are trained using the ~ ~1.3M training images. Images were transformed & augmented with standard procedures [35, 60]. All the implementations were in PyTorch [45] and experimented on a machine with NVIDIA Titan X (Pascal) GPUs.
When applied to ImageNet- IK, the first phase of LLC, learnt a 20-bit codebook with 1000 unique class codes, i.e., every class has its own distinct binary code. We warm start the second phase of LLC by the learnt ResNer50 backbone along with the 20 dimensional projection layer. See Appendix C for the hyperparameter values and other training details.
A key feature of L.L is that it jointly learns both the class codehook as well as instance codes. Several existing techniques decouple this learning process where the codebook is constructed separately and is then used to train the instance codes [28, 14, 3, 20, 1, 58]. We evaluate the advantage of the joint learning approach of LLC by comparing its performance against three strong baselines: i) Random codebook of 20-bits, ii) 20-bit CCA codebook [1, 58, 64] & iii) 20-bit SVD codebook. Previous works [28, 14, 3] argued that random codebooks are competitive using side-information. 20-bit CCA and SVD codebooks aim to capture the hierarchy that is amiss in the random codebook. The 20-bit SVD codebook is built using the SVD of 2048 dimensional linear classifiers (for each class) in the pre-trained ResNer50, and binarizing it. 20-bit CCA codebook is the binarized version of the transformed label embedding projected on to 20 components learnt using CCA between 2048 dimensional representations of 50K samples from the ImageNet train set and
the ones constructed

---

Table 1: Classification performance on ImageNet- with
Table 2: Classification accuracy on ImageNet- IK vs. bit length of the Icarnt class codebooks ($4.4).
ResNet50 using various class codebooks for training.
Codebook
Unique Codes
ED
MHD Accuracy (%)
LLC Length
Unique Codes
HD
MHD
Accuracy (%)
Accuracy (%)
Accuracy (%)
Random 20-bits
1000
64.07
66.91
15 bits
990
67.20
71.03
CCA 20-bits
813
55,17
57.03
20 bits
1000
68.82
74.57
SVD 20-bits
969
65,12
69.18
25 bits
1000
67.93
74.79
LLC 20-bits (Ours)
1000
68.82
74.57
30
1000
67.51
75.13
their one-hot label embeddings. Despite being able to capture the hierarchy information, both 20-bit CCA/SVD codebooks suffer from clashes reducing their overall effectiveness.
Next, using the baselines codebooks and the corresponding learnt instance codes, we compute class predictions for each test instance using the Exact Decoding (ED) & Minimum Hamming Decoding (MHD) schemes mentioned in the previous section. We evaluate all the methods using top-1 accuracy on the ImageNet-IK, KK validation set. Baseline ResNet50 architecture represents the maximum accuracy we can hope to achieve using binarized instance+-class codes. Note that this baseline classifier requires (T) computation over 16-bit real numbers, and achieves Top-1 accuracy of 77%.
Table 1 compares the accuracy of L.L. (with 20-bit codehook) against baseline codebooks mentioned above. Note that MHD with L.L.C codebook is 74.5% accurate, i.e., despite using only 20-dimensional binary representation it is only about 2.5% less accurate than standard ResNet50 that uses 2048 di- mensional real-valued representation. Furthermore, we observe that compared to standard codebooks like SVD, our jointly learnt codebook is 5% more accurate.
Interestingly, Exact Decoding (ED) which is ((1) inference scheme with LLC codebook is nearly accurate the SVD codebook with MHD scheme and is about 12% more accurate than the CCA codebook with ED scheme. Naturally, codebook tigth/dimensionality plays a critical role in classification accuracy; see Section 4.4 for detailed ablative study on this aspect. Finally, the gains in efficiency should be even more compelling for problems with millions of classes [54].
4.2 Efficient Retrieval
The goal in retrieval is to find instances from a database that are most similar to a given query. Traditional retrieval approaches, use a fixed metric to retrieve "similar points", with data structures like LSH for efficient retrieval. Recent progress in Deep Supervised Hashing (DSH) [38] offer significantly more compelling solutions by learning the hashing function itself. That is, DSH aims to learn binary codes for each instance s.t. pair of instances are embedded closely iff they belong to the same class, and then learns the hashing function end-to-end using a small train set.
As LLC also learns instance codes to reflect class membership, we can directly use our learnt encoder as a hashing function for given instances. For each query, the most relevant samples from the database are retrieved based on the minimum Hamming distance. Similar to the decoding schemes in classification, the retrieval can be optimized using approximate nearest neighbor search. Finally, the efficiency gains provided by using bits instead of real numbers should enable deployment of LLC based retrieval for efficient high recall portions of retrieval pipelines.
4.2.1 Empirical Evaluation
Following DSH literature, we evaluate besshngg-bssed image retrieval on ImageNet-100, a benchmark dataset created by Cao et al. [9]. ImageNet- 100 has 100 classes randomly sampled from ImageNet- - All the validation images of these classes are used as query images, all the training images (~ 1300 per class) of these 100 classes are used as database images. Finally, 130 samples per class from the database are used as the training set for learning binary codes or hashing functions.
We compare against HashNet [9] and Greedy Hash [53] for image retrieval using learnt instance codes. HashNet learns the bit representations of instances using a pairwise optimization with positive and negative instance pairs. HashNet is representative baseline for an alternative way of learning binary instance codes compared to L.I.C On the other hand, Greedy Hash learns only the instance codes using straightttrrough--simmat via the classification task. Note that LLC learns both class
7

---

Table 3: Efficient image retrieval on ImageNet- us- ing AlexNet compared using MAP@ 1000 (Appendix B)
Table 4: Comparison LLC based retrieval vs real-valued representations with ResNe150 on ImageNet- 100 using MAP@ 1000.
across 16- 64 bits.
Method
bits
16 bits
32 bits
48 bits
64 bits
Representation dims 10 dims
64 dims
HashiNtt [9]
0.1995
0,2815
0.4300
0.5270
0.5124
LLC (1 bit)
0.6458 0.6657
0.6773 0.7794
Greedy Hash [53]
0.2860
0.4247
0,5412
0,5720
0.5895
1..0 (Ours)
0.3086
0.4305
0.5565
0.5749
0.6000
Real (16 bits)
0.5041
codes as well as instance codes differentiating it from Greedy Hash style methods. Learnt instance codes are a byproduct of efficient classification as opposed to baselines that optimize for them.
We use the Mean Average Precision (MAP@ 1000) metric for evaluation. The MAP@ 1000 calculation code of HashNet [9] is erroneous and has propagated to several papers in the literature. We use the corrected version, hence the accuracy numbers are different from the original paper. Please see Appendix B for the corrected version, the changes required along with an example and brief discussion. We used the publicly available pre-trained HashNet models [10] and Greedy Hash [53] code to recompute the MAP@ 1000.
Following HashNet [9], we use AlexNet [31] as the backbone and warm-star start with pre-trained model on ImageNet-IK. IK. We add a projection layer to the backbone and learn the instance and class codes. We also report retrieval numbers with ResNet50 [25] and compare LLC based retrieval numbers to learnt real-values representations. Please see Appendix C for the training details and hyperparameters of efficient retrieval pipelines.
Table 3 shows the performance (evaluated using MAP@ 1000) for HashNet, Greedy Hash, and LLC across various code lengths. LLC outperforms HashNet across all code lengths (16 64) by least 4.79% on MAP@ 1000. LLC is also better than Greedy Hash across all the bit lengths. LLC also outperforms 16-bit HashNet by 2% & 15% using only 10 & 16 bits respectively. Finally, 32-bit LLC comfortably outperforms both 48 & 64-bit HashNet showcasing the effectiveness of our learnt tight bit codes. Note that LLC, learning both instance and class codes, is effective in retrieval even though it was designed for classification.
We repeat the retrieval experiments with ResNet50. Table 4 shows the MAP@ 1000 for LLC with 10 and 64 bits along with the same dimensional real-valued representations. The 10-bit LLC is only 2% lower than 10 dimensional real-valued representation even though theoretically, the cost associated with 10-bit LLC based retrieval is about 256 less than 10 dimensional real representations.
The 64 bit and 10 bit LLC outperforms 10 and 8 dimensional real-valued representations respectively at a much cheaper retrieval cost, at least by an order of magnitude. More discussion about the use of binary codes for retrieval at large scale can be found in Section 5. Finally, 10-bit LLC with ResNet50 outperforms the best performing AlexNet based models for the same task, suggesting ResNet50 is more appropriate architecture for benchmarking DSH literature.
4.3 Outtof-Distributiin (OOD) Detection
For a multi-class classifier, detecting an OOD sample is very important for robustness [26] and sequential learning [55]. Multi-class classifiers augmented with OOD detection capability by setting a threshold on heuristics like maximum logit which is tuned using a validation set.
We focus on the scenario where the ratio of in-distribution to out-of-distribun validation set is not representative of the deployment. This throws off the methods that try to maximize metrics, F1, using validation set. Our learnt class codebook from LLC comes with over-provisioning (for case of optimization) resulting in unassigned codes. These unassigned codes can be treated as OOD out-of-the-bol with no tuning whatsoever. That is, we classify an instance as OOD if its instance code does not match exactly with the code of a class in our learnt codebook.
samples in the
Appendix E discusses the OOD detection experiments on ImageNet-750 [55] & MIT Places [65]. At high level, LLC based out-of-the-bor- OOD detection (with a learnt 20-bit codebook on ImageNet-IK) achieves nearly the same OOD detection accuracy as baseline [26] that tries to maximize F1 using validation set. We would like to stress that while such method needs Rs 3000 points in the validation set, our method requires no samples, which is critical in several practical settings.
8

---

4.4 Ablation Studies
Classification Accuracy vs Number of Bits. Table shows the trade-off in classification accuracy with the variation in the length of the learnt codebook for ImageNet-1K IK. LLC learns 15-bit codebook with only 990 unique codes leading to a loss of accuracy due to code collapse in both ED and MHD schemes (1.62% & 3.54% compared to 20-bit codebook respectively). An interesting observation is that the ED accuracy gradually goes down after 20-bits while the MHD accuracy keeps on increasing. The phenomenon of increasing accuracy with MHD is probably due to the increase in the capacity of both instance and class codes. However, the decrease in ED accuracy after 20-bits can be explained through the hardness in exactly predicting every bit in the instance code to match the ground truth class code. Our classification model with 20-bits on average gets 19.2 bits correct but the model with 30-bits only gets 28.5 bits right. This increase in uncertainty coupled with the stringent ED scheme leads to a slight dip in accuracy as the code length increases. However, this also provides us with a path for more accurate decoding schemes while being efficient as discussed in Section 5.
Classification Accuracy Faster Codebook Learning. Codebook learning phase of LLC is expensive, this motivated us to speed up codebook learning at a minimal loss in accuracy. One way to warm-start the codebook using the ones built with SVD/CCA (see Section 4.1). While these codebooks suffer from code collapse, with further training, they start to learn 1000 unique codes quickly. Using these final codebooks gets to a comparable (1% drop) accuracy as the 20-bit learnt LLC codebook but at relatively cheaper training. Another option is to use only a portion of the data and a much smaller network learn the codebook. We sampled 50K training images and use a MobileNetVI 1 [27] (which has about 6x less parameters and compute than ResNet50) to learn a 20-bit codebook which gets ED and MHD accuracy of 66.62% & 72.55% which is only 2% lower than the end-to-end learnt codebook but at fraction of the training cost (3 hrs vs 2 days).
Linear vs Hamming Separability. Fitting a deep neural network to the learnt codebook for clas- sification results in warping of the feature space considerably. The final classification space is hypercube with the vertices being apart by Hamming distance of 1. To verify linear separability, we take the learnt, frozen ResNet50 trained for the 20-bit classification problem and fit linear classifier on top of the 2048 dimensional features. Linear classifier quickly reaches a top-1 accuracy of 75.51% %.
The opposite does not seem to be true. We extract and freeze the backbone of pre-trained ResNet50 and train a projection layer to fit the 20-bit learnt codebook. This gets to top-1 accuracy of only about 21% with the ED scheme. However, we also observed that unfreezing and finetuning the last 3 layers of the backbone recovers the top-1 ED accuracy to roughly 68%.
These experiments show 1) Hamming separability inherently enables linear separability, 2) Linear separability does not imply Hamming separability & 3) with enough overparameterization, linearly separable space can be warped to support Hamming separability. Hamming separability automatically provides linear separability with increased accuracy of ~ 1% over the MHD scheme which allows for option for using a more powerful yet simple classifier, in case of accuracy requirements.
Independent vs Nested Codebook Learning. Consider a scenario with varied computational budgets for classification. We could either train independent k-bit models (eg., k = 20, 25, 30) and use them according to the budget, or we could learn single nested codebook-based model that can be readily adapted to any of these settings. While training codebook of larger bit length like A = 30, we can ensure that the first m-bits, m < k. also form codebook at minimal additional cost. We were able to stably train a 30-bit codebook and also extract 20, 25-bit codebooks from it all of which are as accurate as independently trained codebooks. These nested codebooks have the potential to be used based on the computational resource availability for efficient classification without having to retrain.
5 Discussion and Conclusions
We designed LLC to learn low-dimensional binary codes for instances as well as classes, and utilized them in applications like efficient classification, retrieval, OOD detection. A key finding is that combining class code learning with ECOC framework to learn instance code leads to a stable training system that can accurately capture the semantics of the class data despite just 20-dimensional code. Traditionally, methods like HashNet, KLSH [33] attempt to learn hashing function using pairwise

---

loss functions by embedding instances such that points from the same class are embedded closely and points from different classes are far. But such formulations are hard to optimize, due to the risk of embedding collapse. We observe that LLC by using instance-wise formulation can train stably with significantly higher performance. Another fascinating observation is that while architectures like ResNer50 have large intermediate (2048 dimensional real) representations, they can be compressed to just 20 bits without significant loss in accuracy! Even though quantization [48] literature demonstrates strong compression of representations, we believe such stark compression has been elusive so far and is worth further exploration from the efficient inference viewpoint.
Limitations. Our visualization (see Figure 4 in Appendix D) indicates that each bit does not correspond to some easily interpretable attributes, unlike DBC [47]. We believe incorporating priors with weak supervision well as cross-modal learning could help LLC get past this limitation.
ED and MHD schemes are on two ends of the computation vs accuracy spectrum and do not transition smoothly. Designing decoding schemes that can compromise between these two extreme decoding schemes might be able to address this limitation.
Strong encoders are needed to warp the feature space to ensure Hamming separability. For example, using 20-bit learnt codebook with ED scheme, ResNer50 gets to 68.8% top-1 accuracy whereas MobileNetV] can only reach 53. 23.23% This also ties into the argument that classification is a trade- off between encoder and decoder costs. Making decoders efficient and cheap, puts the burden on encoding the information in the right way and higher expressivity often helps in that cause.
Future Work. There are several exciting directions that would like explore. In principle, LLC. can easily incorporate side-information when needed with simple additional losses during training. The additional regularization losses can also help in incorporating natural constraints on the codebook [14, 3] or can enable attribute-based class codes for interpretablity [21, 22, 37] making them exciting directions to explore. LLC algorithm can also be used to encode instances of multiple modalities like audio, visual, language to the same learnt low-dimensional binary space. This might help in effective cross-modal supervision along with retrieval among various other applications.
Potential in Large-Scale Applications. While our focus was on designing low-dimensional accu- rate binary codes, several studies [48, 29] have shown that efficiency afforded by bit-wise computation over floating-poin computation can lead to almost an order of magnitude speed-up. Furthermore, as the number of classes increases, the learning of class codebooks helps in training representations in sublinear costs [13] along with sublinear inference (in L). We expect LLC algorithm to have problems, like
its efficiency benefits outweigh the accuracy drop for large mualti-class/multillate objection recognition using ImageNet-22K [17], document tagging [54, 46] and instance classifica- tion [59]. The efficiency aspect of the binary codes has not been fully explored in this paper as the main computational bottleneck for ImageNet- IK classification is the deep neural network featurizer.
Lastly, LLC based efficient retrieval can be used for the initial high-recall shortlisting of search pipeline, which is followed by high precision models operating on more expressive yet expensive embeddings. We leave practical demonstration of such system at web-scale for future work.
Acknowledgments
We are grateful to Tapan Chugh, Kunal Dahiya, Max Horton, Sewoong Oh, Mohammad Rastegari, Ludwig Schmidt and members of RAIVN Lab for helpful discussions and feedback. AK would also like to thank Soumen Chakrabarti and Manik Varma for sowing the seeds of this idea in his initial research days. Sham Kakade acknowledges funding from NSF Awards CCF-1703574. Ali Farhadi acknowledges funding from the NSF awards IIS 1652052, IIS 1703166, DARPA 166001-19-2-4031, W911NF-15-1-0543 and gifts from Allen Institute for Artificial Intelligence.
References
[1] Z.. Akata, F. Perronnin, Z. Harchaoui, and C. Schmid. Label-embedding for image classification. IEEE transactions pattern analysis and machine intelligence, 1857):1455-1438 2015.
10

---

[2] Z. Akata, S. Reed, D. Walter, H. Lee, and B. Schiele. Evaluation of output embeddings for fine-grained image classification. In Proceedings the IEEE conference on computer vision and patlern recognition, pages 2927-2936, 2015.
[3] E. I.. Allwein, R. F. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of machine learning research, 1(Dec): 2000.
[4] M. A. Bautista Martín et al. Learning error-correcting representations for multi-class problems.
PhD thesis, Universitat de Barcelona, 2016.
[5] S. Bengio, J. Weston, and Grangier. Label embedding trees for large multi-class tasks. In Proceedings of the 23rd International Conference on Neural Information Processing Systems- Volume 1, pages 163-171, 2010.
[6] Y. Bengio, N. Léonard, and A. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprini arXiv: 1e0..108.33333 2013.
[7] J. L. Bentley. K-d trees for semidynamic point sets. In Proceedings of the sixth annual symposium on Computational geometry, pages 187-197, 1990.
[8] K. Bhatia, H. Jain, Kar, M. Varma, and Jain. Sparse local embeddings for extreme multi-label classification. In NIPS, volume 29, pages 730-738, 2015.
[9] Z. Cao, M. Long, J. Wang, and P. S. Yu. Hashnet: Deep learning to hash by continuation. In Proceedings of the IEEE international conference on computer vision, pages 5608-56001 5617,, 2017.
[10] Z. Cao, M. Long, Wang, and S. Yu. Hashnet: Deep learning to hash by continuation, 2017. URL https:
[11] M. A. Carreira-Perpinán and R. Raziperchikolaci. Hashing with binary autoencoders. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 557- 566, 2015.
[12] A. Choromanska, K. Choromanski, M. Bojarski, T. Jebara, S. Kumar, and Y. LeCun. Binary embeddings with structured hashed projections. In International Conference on Machine Learning, pages 344 353. PMLR, 2016.
[13] M. Cissé, N. Usunier, T. Artieres, and P. Gallinari. Robust bloom filters for large multilabel classification tasks. In Advances in Neural Information Processing Systems 26, pages 1851- 1859, 2013.
[14] K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 2(Dec):265-292, 2001.
[15] K. Dahiya, D. Saini, A. Mittal, A. Shaw, K. Dave, A. Soni, H. Jain, S. Agarwal, and M. Varma. Deepxml: A deep extreme multi-label learning framework applied to short text documents. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 31-39, 2021.
[16] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 253-262, 2004.
[17] Deng, W. Dong, R. Socher, L.JJ. K. Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pages 248-28 255. Ieee, 2009.
[18] Deng, A. C. Berg, and L. Fei-Fei. Hierarchical semantic indexing for large scale image retrieval. In CVPR 2011, pages 785-792. IEEE, 2011.
[19] T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correctngg output codes. Journal of artificial intelligence research, 2:263-286, 1994.
[20] S. Escalera, O. Pujol, and P. Radeva. Error-correcting ouput codes library. The Journal of Machine Learning Research, 11:661-664, 2010.
[21] A. Farhadi, I. Endres, D. Hoiem, and D. Forsyth. Describing objects by their attributes. In 2009 IEFE Conference on Computer Vision and Pattern Recognition, pages 1778-1785. IEEF, 2009.
[22] V. Ferrari and A. Zisserman. Learning visual attributes. Advances in neural information processing systems, 20:433-440, 2007.

---

[23] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE transactions on pattern analysis and machine intelligence, 35(12):2916-299) 2929, 2012.
[24] C. Guo, A. Mousavi, X. Wu, D. Holtmann-Rice S. Kale, S. J. Reddi, and S. Kumar. Breaking the glass ceiling for embedding- based classifiers for large output spaces. In NeurlPS, 2019.
[25] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-
778, 2016.
[26] D. Hendrycks and K. Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. arXiv preprint arXiv: 16100021,, 2016.
[27] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications.
arXiv preprint arXiv: 00..1044444488 2017.
[28] D. Hsu, S. M. Kakade, Langford, and T. Zhang. Multi-label prediction via compressed sensing. arXiv preprint arXiv:0902.1280 2009.
[29] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio. Binarized neural networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 41 14 4122, 2016.
[30] H. Jain, V. Balasubramanian, B. Chunduri, and M. Varma. Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 528-536, 2019.
[31] A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 15: 2012.
[32] B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In NIPS, volume 22, pages 1042- 1050. Citeseer, 2009.
[33] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In 2009 IEEE 12th international conference on computer vision, pages 2130-2137. IEEE, 2009.
[34] B. Kulis, P. Jain, and K. Grauman. Fast similarity search for learned metrics. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12):213322157 2009.
[35] A. Kusupati, V. Ramanujan, R. Somani, M. Wortsman, P. Jain, S. Kakade, and A. Farhadi. Soft threshold weight reparameterization for learnable sparsity. In International Conference on Machine Learning, pages 5544-5555. PMLR, 2020.
[36] C. H. Lampert, H. Nickisch, and S. Harmeling. Learning to detect unseen object classes by between-class attribute transfer. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 951-958. IEEE, 2009.
[37] C. H. Lampert, H. Nickisch, and S. Harmeling. Attribute-bseed classification for zero-shot visual object categorization. IEEE transactions on pallern analysis and machine intelligence, 36(3):453-465, 2013.
[38] H. Liu, R. Wang, S. Shan, and X. Chen. Deep supervised hashing for fast image retrieval. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2064 (072-2072,20 2016.
[39] X. Luo, C. Chen, H. Zhong, H. Zhang, M. Deng, J. Huang, and X. Hua. A survey on deep hashing methods. arXiv preprini arXiv:2003.. 03369, 2020.
[40] Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4))824-834 2018.
[41] G. A. Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(11) 1): 39-41, 1995.
[42] F. Murtagh and P. Contreras. Algorithms for hierarchical clustering: overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86-97, 2012.
[43] M. Norouzi, D. J. Fleet, and R. R. Salakhutdinov. Hamming distance metric learning. In Advances in neural information processing systems, pages 1061-1069, 2012.
12

---

[44] M. Norouzi, T. Mikolov, S. Bengio, Y. Singer, J. Shlens, A. Frome, G. S. Corrado, and J. Dean. Zero-shot learning by convex combination of semantic embeddings. arXiv preprint arXiv: 12....5600 2013.
[45] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, 7. Lin, N. Gimelshein, L.. Antiga, et al. Pytorch: An imperative style, perf-pper deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019.
[46] Y. Prabhu, A. Kusupati, N. Gupta, and M. Varma. Extreme regression for dynamic search advertising. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 456-464, 2020.
[47] M. Rastegari, A. Farhadi, and D. Forsyth. Attribute discovery via predictable discriminative binary codes. In European Conference on Computer Vision, pages 876-889, Springer, 2012.
[48] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In European conference computer vision, pages 525-542. Springer, 2016.
[49] O. Russakovsky. J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-255 2015.
[50] R. Salakhutdinov and G. Hinton. Learning a nonlinear embedding by preserving class neigh- bourhood structure. In Artificial Intelligence and Statistics, pages 412-419, PMLR, 2007.
[51] R. Salakhutdinov and G. Hinton. Semantic hashing. International Journal of Approximate Reasoning, 50(7):969-975 2009.
[52] F. Shen, Y. Xu, L. Liu, Y. Yang. Z. Huang, and H. T. Shen. Unsupervised deep hashing with similarity adaptive and discrete optimization. IEEE transactions on pattern analysis and machine intelligence, 40(12):3034-300 3044, 2018.
[53] S. Su, C. Zhang, K. Han, and Y. Tian. Greedy hash: Towards fast optimization for accurate hash coding enn. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 806-815, 2018.
[54] M. Varma. Extreme classification. Communications of the ACM, 62(11):44 2019.
[55] M. Wallingford, A. Kusupati, K. Sitzadeh-Vahid A. Walsman, A. Kembhavi, and A. Farhadi. Are we overfitting to experimental setups in recognition? arXiv preprint arXiv:2007002519 2020.
[56] J. Wang. W. Liu, S. Kumar, and S.FF. Chang. Learning to hash for indexing big data survey. Proceedings of the IEEE, 104(1):34-57, 2015.
[57] Y. Weiss, A. Torralba, R. Fergus, et al. Spectral hashing. In Advances in Neural Information Processing Systems, 2008
[58] J. Weston, S. Bengio, and N. Usunier. Wsabie: Scaling up large vocabulary image annotation.
In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
[59] T. Weyand, A. Araujo, B. Cao, and J. Sim. Google landmarks dataset v2-a large-scale benchmark for instance-level recognition and retrieval. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2575-2584, 2020.
[60] M. Wortsman, A. Farhadi, and M. Rastegari. Discovering neural wirings. arXiv preprint arXiv:1906.0055 00586, 2019.
[61] H.-F. Yu, P. Jain, Kar, and I. Dhillon. Large-scale multi-label learning with missing labels. In International conference on machine learning, pages 593-601 PMLR, 2014.
[62] X. Yuan, L. Ren, J. Lu, and J. Zhou. Relaxation-fre free deep hashing via policy gradient. In Proceedings of the European Conference on Computer Vision (ECCV), pages 134-150, 2018.
[63] X. Zhang. survey on deep hashing for image retrieval. arXiv preprint arXhv:2006.05627, 2020.
[64] Y. Zhang and J. Schneider. Multi-label output codes using canonical correlation analysis. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 873 882. JMLR Workshop and Conference Proceedings, 2011.
13

---

[65] B. Zhou, A. Lapedriza, J. Xiao, A. Torralba, and A. Oliva. Learning deep features for scene recognition using places database. In Advances in Neural Information Processing Systems, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] As with all the efficient machine learning work, this work has both pros and cons. We believe that making ML models affordably available will help in better feedback loop overall.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proof's of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen- tal material. All the code and models will be open sourced.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix C.
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [No] We evaluated computationally expensive to run (3 days per experiment).
method on ImageNet which is
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] All the datasets and code used public and are under MIT, BSD or CC licenses.
(c) Did you include any new assets either in the supplemental material or as URI.? [No]
(d) Did you discuss whether and how consent obtained from people whose data you'ne using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xZqa7SV1lu", "reviewer": "Reviewer_vExU", "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.    ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "General Comments\n\nThe 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.   \n\nPros:\n\n- Writing/Pitching: The problem is well-motivated. Literature review for learning binary class and instance codes is very clear. \n- 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.   \n- Utility: Evaluations on classification, retrieval and especially OOD provide good coverage of popular applications; ablations and visualizations are helpful.\n\nCons:\n\n- 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?\n- 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?\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ZhG7Rxmyy48", "reviewer": "Reviewer_BkS5", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-      Pros\n* Well written paper with extensive experimental results.\n* Improvements are found on three downstream tasks in terms of computational efficiency.\n-      Cons: \n* 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?\n* 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?\n*Some typo errors could be found in the paper. For example, in Line 257, the word “iff” should be corrected as “if”.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "According to question 1(b) in the Checklist, the authors describe the limitations and give potential solutions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "V4nDRm1_YTB", "reviewer": "Reviewer_z4qi", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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? \n\nThere 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.\n\nFigure 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.\n\nOn 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? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "four"}, "extra_text": {}}, {"review_id": "OFh5yzXRvWG", "reviewer": "Reviewer_Kaxs", "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.\n\nThe 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:\n\nIn 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. \n\nIn 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.)\n\nThe 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.\n\nThe result of this binary code classification can now be used in a number of applications, including:\n- the binary codebook can be naturally used to make a taxonomy visualization for the labels. \n- the system can be used for efficient (in terms of representation size and running time of retrieval) multi-class classification.\n- 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.)", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nOverall, 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.\n\nI have some questions for the authors:\n\n1. 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.)\n\n2. 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?\n\n3. 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)?\n\n4. 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not really discussed, though I'm not sure what there is to say about this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "2X5YSX1SiEM", "reviewer": "Reviewer_5Yju", "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.\n\nConcretely, 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. \n\nThe 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.\n\nAs 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThat 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.\n\nNevertheless, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)