Visual Recognition with Deep Nearest Centroids
Authors: Wenguan Wang
Cheng Han
Tianfei Zhou
Dongfang Liu
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Nearest centroids classifier
Cased-base reasoning
Image classification
Image segmentation
Explainable neural networks

Abstract: We devise deep nearest centroids (DNC), a conceptually elegant yet surprisingly effective network for large-scale visual recognition, by revisiting Nearest Centroids, one of the most classic and simple classifiers. Current deep models learn the classifier in a fully parametric manner, ignoring the latent data structure and lacking simplicity and explainability. DNC instead conducts nonparametric, case-based reasoning; it utilizes sub-centroids of training samples to describe class distributions and clearly explains the classification as the proximity of test data and the class sub-centroids in the feature space. Due to the distance-based nature, the network output dimensionality is flexible, and all the learnable parameters are only for data embedding. That means all the knowledge learnt for ImageNet classification can be completely transferred for pixel recognition learning, under the ‘pre-training and fine-tuning’ paradigm. Apart from its nested simplicity and intuitive decision-making mechanism, DNC can even possess ad-hoc explainability when the sub-centroids are selected as actual training images that humans can view and inspect. Compared with parametric counterparts, DNC performs better on image classification (CIFAR-10, ImageNet) and greatly boots pixel recognition (ADE20K, Cityscapes), with improved transparency and fewer learnable parameters, using various network architectures (ResNet, Swin) and segmentation models (FCN, DeepLabV3, Swin). We feel this work brings fundamental insights into related fields. Our code is available at https://github.com/ChengHan111/DNC.

Published as a conference paper at ICLR 2023
VISUAL RECOGNITION WITH DEEP NEAREST CENTROIDS
Wenguan Wang Cheng H Zhou Dongfang Liu CCAI, Zhejiang University', Rochester Institute of Technology? & ETH Zurich
ABSTRACT
We devise deep nearest centroids (DNC), a conceptually elegant yet surprisingly ef- fective network for large-scale visual recognition, by revisiting Nearest Centroids, one of the most classic and simple classifiers. Current deep models learn the classi- fier in a filly parametric manner, ignoring the latent data structure and lacking explainability. DNC instead conducts nonparametric, case- base-based reasoning; it uti- lizes sub-centroids of training samples to describe class distributions and clearly ex- plains the classification as the proximity of test data to the class sub-cen centroids in the feature space. Due the distance- based nature, the network output dimensionality is flexible, and all the learnable parameters are only for data embedding. That means all the knowledge learnt for ImageNet classification can be completely transferred for pixel recognition learning, under the "pre-training and fine-tuning" paradigm. mechanism, DNC
Apart from its nested simplicity and intuitive decision-makee can even possess ad-hoc explainability when the sub-centroids are selected tual training images that humans can view and inspect. Compared with parametric counterparts, DNC performs better on image classification (CIFAR-10) CIFAR-I00. ImageNet) and greatly boosts pixel recognition (ADE20K, Cityscapes) with im- proved transparency, using various backbone network architectures (ResNet, Swin) and segmentationn models (FCN, DeepLaby3, Swin). Our code is available at DNC.
INTRODUCTION
Deep learning models, from convolutional networks (e.g.. VGG [1], [es Transformer-based architectures (e.g., Swin [3]), push forward the state-of-the-arr on visual recognition. With these ad- vancements, parametric softmax classifiers, which learn set of parameters, i.e., weight vector, and bias term, for each class, have become the de facto regime in the area (Fig. 1(b)). However, due to the parametric nature, they suffer from several limitations: First, they lack simplicity and explainability. The parameters the classification layer are abstract and detached from the physical nature of the problem being modelled [4]. Thus these classifiers are hard to naturally lend to an explanation that humans are able to process [5]. Second, linear classifiers are typically trained to optimize classification accuracy only, paying less attention to modeling the latent data structure. For each class, only one sin- gle weight vector is learned in a fully parametric manner. Thus they essentially assume unimodality for each class [6, 7], less tolerant of intra-class variation. Third, as each class has its own set of parame- ters, deep parametric classifiers require the output space with a fixed dimensionality (equal to the number of classes) [8]. As a result, their transferability is limited; when using ImageNet-trained clas- sifiers to initialize segmentation networks (i.e., pixel classifiers), the last classification layer, whose parameters are valuable knowledge learnt from the image classification task, has be thrown away.
In light of the foregoing discussions, we are motivated to present deep nearest centroids (DNC), a ppow erful, nonparametric classification network (Fig. (d)). Nearest Centroids, which has historical roots dating back to the dawn of artificial intelligence [9-14], is arguably the simplest classifier. Nearest Centroids operates on an intuitive principle: given data sample, it directly classified to the class training examples whose mean (centroid) is closest it. Apart from its internal transparency, Nearest Centroids is classical form of exemplar-based reasoning [5, 11], which is fundamental to our most effective strategies for tactical decision [15] (Fig. (c)).. Numerous past studies [16-18] have shown that humans learn to solve new problems by using past solutions of similar problems. Despite its conceptual simplicity, impiricalevidencee in cognitive science, and ever popularry 20-2e2,
"qqual contribution Corresponning author

---

Published as a conference paper at ICLR 2023
parametic dassifer class woight biss L.S. 0.3
Cat...t looks
Training datase
extraction
like I've
47, 54 05
ever seen, but
not like
Leal
2.1,
space
Dog? Pig? or Cat? (a)
Cat...it looks like
should be Cat, bec.use..umm...
I've ever seen, but not like
DNN
(b)
Human
(c)
DC
Figure I: (b) Prevalent visual recognition models cb. built upon parametric softmax classifiers, have few limitations, such as their transparnppentttt decision-making process. (c) Humans can use past cases as models when solving new problems| [16, 18] (e.g., comparing with a few familiar/exemplar animals for categorization) (d) DNC E makes classification based on the similarity of to class sub- centroids (representative training examples) in the feature space. The class sub-centroids are vital for capturing underlying data structure, enhancing interpretability, and boosting recognition.
Centroids and its utility in large datasets with nigh-dimensional input spaces are widely unknown or ignored by current community. Inheriting the intuitive power of Nearest Centroids, our DNC is able to serve as a strong yet interpretable backbone for large-scale visual recognition; is fully aware of the affremennionee limitations of parametric counterparts while shows even better performance.
Specifically, DNC summarizes each class into set of sub-centroids (sub-cluster centers) by clustering of training data inside the same class, and assigns each test sample the class with the nearest sub- centroid. DNC essentially an spprriecce/ddsstane wwddddiiiannbbeedddd classifier it merely relies on the proximity of test query to local means of training data ("quintessential" past observations) in the deep feature space. such, DNClearns visual recognition by directly optimizing the representation, instead of deep parametric models needing an extra softmax classification layer after feature extraction. For training. DNC alternates between two steps: i) class-wise clustering for automatically discovering class sub- centroids, and ii) classification prediction for supervised representation learning, through retrieving the nearest sub sub-centroids. However, since the feature space evolves continually during training, com- puting the sub-centroids is expensive - it requires a pass over the full training dataset after each batch update and limits DNC's scalability. To solve this, we use Sinkhorn Iteration [23] based clustering algorithm [24] for fast cluster assignment. We further adopt momentum update with an external me- mory for estimating online the sub-centroids (whose amount is more than IK on ImageNet [25]) with small- batl-bbtch size (e.g., 256). Consequently, DNC can be efficiently trained by simultaneously con- ducting clustering and stochastic optimization on large datasets with small batches, only slowing the training speed slightly (e.g., ~5% on ImageNet).
DNC enjoys few attractive qualities: First, improved simplicity and transparency. The intuitive working mechanism and statistical meaning of class sub- cenb-cetsoids make DNC elegant and easy to un- derstand. Second, automated discovery of underlying data structure. By within-class deterministic clustering, the latent distribution of each class is automatically mined and fully captured as a set of representative local means. In contrast, parametric classifiers learn one single weight vector per class, intolerant of rich intra-class variations. Third, direct supervision of representation learning. DNC achieves classification by comparing data samples and class sub-centroids on the feature space. With such distance-based nature, DNC blends unsupervised sub- sub-pattern mining (class-wise clustering) and supervised representation learning (nonparametric classification) in a synergy: local significant pat- terns are automatically mined to facilitate classification pecision-making the supervisory signal from classification directly optimizes the representation, which in turn boosts meaningful clustering. Forth, better transferability. DNC learns by only optimizing the feature representation, thus the output di- mensionality no longer needs to be as many as the classes. With this algorithmic merit, all the use- ful knowledge (parameters) learnt from source task (e.g., ImageNet [25] classification) are stored in the representation space, and can be completely transferred to target tasks (e.g., Cityscapes [26] segmentation). Fifth, ad-hhecexlaannabiiiy If further restricting the class sub-centroids to be samples (images) of the training set, DNC can explain its prediction based on IF-.. Then rules and allow users to intuitively view the class representatives, and appreciate the similarity of test data to the repre- sentative images (detailed in $38..3). Such ad-hoc explainability [27] is valuable in sensti-sessitive scenarios, and differs DNC from most existing network interpretation techniques [28-30] that only investigate post-hoc explanations and thus fail to elucidate precisely how a model works [31, 32].
DNC is an intuitive yet general classification framework; is compatible with different visual recog- nition network architectures and tasks. We experimentally show: In 1, with ResNet [2] and Swin [3]
2

---

Published as a conference paper at ICLR 2023
network architectrss,,, DNC outperforms parametric counterparts image classification, i.e., 0.23-
top- accuracy on (O and 0.24-0.32% on ImageNe((25]] by trainingfrrmm scratch.
In $4.2, when using our Image:Net-pretranne
nonparametric versions of ResNet and Swin as back- bones, our pixel-wise DNC classifier greatly improves the segmentation performance of FCN [34], DeepLabyy [35], and UperNet [36], on ADE20K [37] (1.6-2.5% m OU) and Cityscapes [26] (1.1- 1.9% (0%mIJ) OU). These results verify DNC's strong transferability and high versatility. In $4.3, after con- straining class sub-centroids as training images of ImageNet, DNC becomes more interpretable, with only 0.12% sacrifice in top-1 accuracy (but is still 0.17% better than the parametric counterpart).
These results are particularly impressive, considering the nonparametric and transparent nature of DNC. We feel this work brings fundamental insights into related fields.
2 RELATED WORK
Distance-PProootyp---ae Classifiers. Alosi the numerous classification algorithms (e.g., logis- tic regression [38], Naive Bayes [39], random forest [40], support vector machines [41], and deep neural networks (DNNs) [42]), distance-based methods are particularly remarkable, due to their intuitive working mechanism. Distance-based classifiers are nonparametric and exemplar-driven, relying on similarities between samples and internally stored exemplars/prototypes. Thus they con- duct case- based reasoning that humans use naturally in problem-solving making them appealing and interpretable [16, 43]. k-Nearest Neighbors (k-NN) [9, 10] is form of distance-based classi- fiers; it uses all training data as exemplars [44, 45J. Towards network implementation of k-NN [46- 48]. Wu et al. [49] made notable progress; their k-NN network outperforms parametric softmax based ResNet [2] and the learnt representation works well in few-shot settings. However, K-NN classifiers (including the deep learning analogues) cost huge storage space and pose heavy compu- tation burden (e.g., persistently retaining the training dataset and making full-dataset retrieval for each query) [50, 51], and the nearest neighbors may not be good class representatives [43]. Nearest Centroids [1 1-]4] is another famous distance-based classifier yet has neither of the deficiencies of (20, 43]. Nearest Centroids selects representative class centers, instead of all the training data, as exemplarss. Guerriero et al. [52] also investigate the idea of bringing Nearest Centroids into DNNs. However, they simply abstract each class into one single class mean, failing to capture complex class-wise distributions and showing weak results even in small datasets [33].
The idea of bistedce-based classification also stimulates the emergence of prototypical networks, which mainly focus on few-shot (53, 54] and zero-shot [55, 56] learning. However, they often asso- ciate to each class only one representation (prototype) [57] and their prototypes are usually flexible parameters [51, 53, 56] or defined prior to training [8. 55]. In DNC, a prototype (sub-centroid) is either generalization of number of observations or intuitively a typical training visual example. Via clustering based sub-class mining, DNC addresses two key properties of prototypical exemplars: sparsity and expressivity [58, 59]. In this way. the representation can be learnt to capture the under- lying class structure, hence facilitating large-scale visual recognition while preserving transparency.
Neural Network Interpretability.. As the black-box nature limits the adoption of DNNs in decision- critical tasks, there has been a recent surge of interest in DNNs' interpretabilityy However, most in- terpretation techniques only produce posteriori explanations for already-trained DNNs, typically by analysis of reverse- reverse-engineer importance values [28-30, 60-65] and sensitivities of inputs [66-69]. As many literature outlined, post-hoc explanations cannotexplain what actually makes a DNN arrive its decisions [72]. To pursue ad-hoc explainability, some attempts have been initiated to develop explainable DNNs, by deploying more interpretable machineries into black-box DNNs [73-75] or regularizing representation with certain properties (e.g., sparsity [76], decomposability [77]. monotonicity [78]) that can enhance interpretability.
problematic and misleading [32, 43, 70, 71]; they
DNC intrinsically relies on class sub-centroid retrieving. The theoretical simplicity makes it easy to understand; when anchoring the sub-centroids to available observations, DNC can derive intuitive explanations based on the similarities of test samples to representative observations. It simultane- ously conducts representation learning and case-based reasoning, making it self-explainable without post-hoc analysis [27]. DNC relates to concept-based based explainable networks [4, 5, 72-74, 79-81] 11] that refer to human-friendly concepts/prototypes during decision making. These methods, however, ne- cessitate nontrivial architectural modification and usually resort to pre-trained models, not to men- tion serving as backbone networks. In sharp contrast, DNC only brings minimal architectural change to parametric classifier based DNNs and yields remarkable performance training from scratch and ad-hoc explainability. It provides solid empirical evidence, for the first time as far as we know, for the power of case-based reasoning in large-scale visual recognition.
ImageNet [25] with
3

---

Published as a conference paper at ICLR 2023
napre sentation learning 2(7)
oub besed dissification
fecture
dalmingdaaast
feature spais
Spaee
unsuperissdl sub
dass wiseewirsr
pallem discwerry (5)
Figure 2:
With distannc--ccse-eaassee classification scheme, CNCcombines unsupervised sub- aub-pattern discovery and supervised representation learning in a synergy.
DEEP NEAREST CENTROIDS (DNC)
Problem Statement. Consider the standard visual recognition setting. Let X' be the visual space (e-g- image space for recognition, pixel space for segmentation), and y (I,...,C) the set of semantic classes. Given a training dataset { (In, Vn {n)))) the goal is to use the N ttraining examples to fit a model (or hypothesis) h:X' + that accurately predicts the semantic classes for new visual samples.
Parametric Softmax Classifier. Cormentcommon practice is to implement as DNNs and decompose it as h = fo Here f X' + Fis a feature extractor (e.g.. convolution based or Transformer-lik networks) that maps an input sample I E X into d-dimensional representation space F E R i.e., = f(x E F; and I: F ~ y is a parametric classifier (e-g-, the last fully-connected layer in recognition or last 1 1x1 convolution layer in segmentation) that takes æ as input and produces class prediction 9 = ((x) y, Concretely, assigns a query x E to the class ğ E y according to:
(1) where sf lR indicates the unnormalized prediction score (i.e., logit) for class c, w" E and e E are learnable parameters class weight and bias term for Parameters of l and f are learnt by mini- mizing the softmax cross-entropy loss:
a-arg max.gy s s² (w=
C= N Σ. -og p(yn(=)),, p(ul=) = (lof)x Eec exp(s")
exp(s")
Though highly successful, the use of the parametric classifier has drawbacks as well: i) The weight matrix W= (wt,... ) E RRdxC bias vector (b-,..., .,,,,,,)))) ..5) Rd in I are learnable parameters, which cannot provide any information about what makes the model h reach its decisions. ii) / makes the loss L only depend on the relative relativerllaaion among logits, i.e., {5 and cannot directly supervise on the representation x: [82, 83]. iii) W and b are learnt as flexible parameters, lacking explicit modeling of the underlying data structure. iv) The final output dimensionality is constrained to be the number of classes, i.e., C. During transfer learning. as different visual recognition tasks typically have distinct semantic label spaces (with different number of classes), the classifier from pretrained model has be abandoned, even though the learnt parameters Wnd b are valuable knowledge from the source task.
The question naturally arises: might there be simple way address these limitations of current de facto, parametric classifier based visual recognition regime? Here we show that this is indeed possi- ble, even with better performance.
DNC Classifier. Our DNC (Fig. 2) is built upon the intuitive idea of Nearest Centroids, i.e., assign a sample to the class ÿ y with the closest class center:
a-arg min (x, F²), T N Σ 2 =C= x
(3)
where (.,-) is a distance measure, given as: (u, v) = --==-uu uie ////llu ||| ||l./o/..Foorroo For simplicity, all the features defaulted to & ---ormallzzdd from now He is the mean vector of class x is training sample of i.e., uf = c, and No is the number of training samples in c. As such, the feature-to-class mapping FF F ) is achieved in nouparametric manner and understandable from user's view, in contrast the parametric classifier that learns "non- tton-transparent" parameters for each class. It makes more sense if multiple sub-centroids(loca means) per class are used, which is in particular true for challenging visual recognition where complex intra-class variations cannot be simply described by the simple assumption of unimodality of data of each class. When representing each class cas sub-centroids, k= the C-way classification for sample : takes place as a winner-takes-all rule:
denoted by {p] E B K
j=c", (c",k") arg min . y.ke (I.....k (z. pi)-
Clearly, estimating class sub-centroids needs clustering of training samples within each class, As class
4

---

Published as a conference paper at ICLR 2023
sub-centroids are sub-cluster centers in the latent feature space F, they are locally significant visual patterns and can comprehensively represent class-level characteristics. DNC can be intuitively un- derstood as selecting and storing prototypical exemplars for each class, and finding classification evidence for a previously unseen sample by retrieving the most similar exemplar. This also aligos with the prototype theory in psychology [17, 84, 85]: prototypes a typical form of cognitive organisa- tion of real world objects. DNC thus emulates the case-based reasoning process that we humans are accustomed [27]. For instance, when ornithologists classify a bird, they will compare with those typical exemplars from known bird species to decide which species the bird belongs to [43].
Sub-centroid Estimation. To find informative sub-centroids that best represent classes, we perform deterministic clustering within each class on the representation space F. More specifically, for each n= into K clusters whose centers are used as class e, we cluster all the representations {ar E Rd
the sub-centroids of c, i.e. {pf E ) x b ... F Ne] E RR and p [pf. . ..p.:" R denote the feature and sub-centroid matrixes, respectvely The tiatermiinstti i.e., the mapping from X to P can be denoted as Q [g.. ... x {0, 1 where n-th column qi E E 13. is an one-hot assignment vector of n-th sample xy, w.r. the K clusters. Q' desired to maximize the similarity between X and P leading to the following binary integer program (BIP):
max ==((') (P')) X*) e- = =Q''E KXN' F
(5)
where 1x is a K-dimensional all-ones vector. As in [24], we relax Q to be transportation poly- tope[23]: (Q R KxN (Q* Q'1N== x 1x) casting (5P into anoptimal trans- portproblem, Q besides the one-hot assignment constraint (i.e., (xx]_x=x=x an equipartition constraint (i.e., Q' = * 1k) is added to inspire No samples to be evenly assigned to K clusters. This can efficiently avoid degeneracy, i.e., mapping all the data to the same cluster. Then the solution can be given by fast version [23] of Sinkhorn- Knopp algorithm [86], in a form of a normalized exponential matrix:
(P')xx
X
Q diag(o) exp
diagg(9),
(6)
where the exponentiation is performed element-wise, a E R and B E R are two renormaliza- tion vectors, which can be computed using small number of matrix multiplications via Sinkhorn- Knopp Iteration [23], and & = 0.05 trades off convergence speed with closeness to the original transport problem. In short, by mapping data samples into few clusters under the constraints Q's, we pursue sparsity and expressivity (58, 59], making class sub-centroids representative of the dataset.
Training of = Representation
Sub-class Pattern Mining. Ideally, according to class-wise cluster assignments {Q) we can get totally CK sub-centroids C.K [pk i.e, mean feature vectors of the training data in the CK clusters. Then the training target becomes as: 1 E n= - log p(un/z.), p(ylx) = exp (- min( PEN)) Eeey ( (E)
Maariing+Autoann
(7)
Comparing (2) and (7), as class sub-centroids Jo. are derived solely from data representations, DNC learns visual recognition by directly optimizing the representation instead of the parametric classifier I. Moreover, with such nonparametric, distance- based scheme, DNC builds closer link to metric learning [87-93]: DNC can even be viewed as learning a metric function f to compare data samples (Ir)). under the guidance of the corresponding semantic labels {yn)a.
During training, DNC alternates two steps iteratively: class-wise clustering (5) for automatic sub- centroid discovery. and ii) sub-centroid based classification for supervised representation learning (7). Through clustering, DNC probes underlying data distribution of each class, and produces informative sub-centroids by aggregating statistics from data clusters. This automatic sub-class discovery process also enjoys a similar spirit recent clustering based unsupervised representation learning [24, 94- 101]. However, it works in class-win wise manner, since the class label is given. In this way, DNC opti- mizes the representation by adjusting the arrangement between sub-centroids and data samples. The enhanced representation in turn helps to find more informative sub-centroids, benefiting classification eventually, As such, DNC conducts unsupervised sub-class pattern discovery during supervised rep- resentation learning, distinguishing it from most (if not all) of current visual recognition models.
Since the latent representation f evolves continually during training, class sub-centroids should be synchronized, which requires performing class-wise clustering over all training data after each batch
5

---

Published as a conference paper at ICLR 2023
update. This is highly expensive on large datasets, even though Sinkhorn-Knopp iteration [23] based clustering (6) is highly efficient. To circumvent the expensive, offline sub-centroid estimation, we adopt momentum update and online clustering. Specifically, at each training iteration, we conduct class-wise clustering on the current batch and update each sub-centroid
Pi - up + (1 - p)af.
(8)
where μ [0, 1] is momentum coefficient, and æद. E is the mean feature vector of data assigned to (c, k)-cluster in current batch. As such, the meters. Though effective enough in most cases, batch-wit clustering could not extend to large num- e ber of classes, e-g-, when training on ImageNet [25] with 1K classes using batch size 256, not all the classes/clusters are present in batch. To solve this, we store features from several prior batches in a memory, and do clustering both the memory and current batch. DNC can be trained by gradient backpropagation in small-batch setting, with negligible lagging (~5% training delay on ImageNet).
can be up-to-date with the change of para-
Versatility. DNC is general framework; it can be effortless integrated into any parametric clas- sifier based DNNs, with minimal architecture change, i.e., removing the parametric softmax layer. However, DNC changes the classification decision-making mode, reforms the training regime, and makes the reasoning process more transparent, without slowing the inference speed. DNC can be ap- poiedto various visual recognition tasks, including image classification ($4.) 1) and segmentation ($4.2).
Transferability. As a nonparametric scheme, DNC can handle an arbitrary number of classes with fixed output dimensionality (d); all the knowledge learnt on a source task (e-g.. ImageNet classification with IK classes) are stored as a constant amount of parameters in and thus can be completely trans- ferred for a new task (e.g.. Cityscapes [26] segmentation with 19 classes), under the ppre-training and fine-tuning" paradigm. In similar setting, the parametric counterpart has to discard 2M parameters during transfer learning (d=2048 when using ResNet101 [2]). See $4.2 for related experiments.
Ad-hoe Explainability. DNC is a transparent classifier that has a built-in case-based reasoning pro- cess, as the sub-centroids are summarized from real observations and actually used during classifi- cation. So far we only discussed the case where the sub-centroids are considered as average mean feature vectors of a few training samples with similar patterns. When restricting the sub-centroids to be elements of the training set (i.e., representative training images), DNC naturally comes with numan-understandabll explanations for each prediction, and the explanations are loyal to the inter- nal decision mode and not created post-hoc. Studies regarding ad-hoc explainability are given in $4.3.
4
EXPERIMENT
4.1
EXPERIMENTS ON IMAGE CLASSIHICATION
Dataset. The evaluation for image classification is carried out on CIFAR-10[33] and [mageNet(25).
Network Architecture. For completeness, we craft DNC on popular CNN-based ResNet50/100 [2] and recent Transformer-basee
Swin-Small/-Base [3]. Note that, we only remove the last linear clas- sification layer, and the final output dimensionality of DNC is as many as the last layer feature of the parametric counterpart, i.e., 2,048 for ResNet50/100, 768 for Smill, and 1,024 for Swin-Base
Training, We use mmclass f icat ion' as codebase and follow the default training settings. For CIFAR-10, 10, we train ResNet for 200 epochs, with batch size 128. The memory size for DNC models setas batches.. For ImageNet, we train and epocss with batch size 16 for ResNet and Swin, respectively. The initial learning rates of ResNet and Swin are set as 0. and 0.0005, scheduled by a step policy and polynomial annealing policy, respectively. Limited by our GPU capacity, the memory sizes are set as 1,000 and 500 batches for versions of ResNet and Swin, respectively. Other hyper- parameters are empirically as: K=4 [ = 0.999.
Table 1: Classification top-1 accuracy on 10F3- ter.ttaaaatt...ss......aa. the of
Models are trained from scratch on eight V 11000000 GPUs
Results on 100. Table 1 compares DNC with the parametric counterpart, based on the most repre- sentative CNN network architecture, i.e., ResNet. As seen, DNC obtains better performance: DNC 0.23% higher on ResNet50, 0.24% higher on R0s,et101, using fewer learnable parameters. With the exact same
learnable parameters (same for other tables).
Method
Backhone
#Params
Lop-1
ResNet [2]
23.52M
93.55%
ResNet50
DNC-ResNet
23.50M
95.78%
ResNet [2]
42.51M
95.58%
DNC-ResNet ResNe1101
42.49M
95.82%
backbone architectures and training settings, one can safely attribute the performance gain to DNC.

---

Published as a conference paper at ICLR 2023
Results on ImageNet. Table illustrates again our compelling results over different vision net- work architectures. In terms of top-1 acc., DNC exceeds the parametric classifier by 0.29% and 0.28% on ResNet50 and ResNet101, respec- tively. DNC also obtains promising results with Transformer architecture: 83.26% 83.02% Swin-S, 83.68% vs 83.36% on Swin-B. These results are impressive, considering the transpa- rent, case-based reasoning nature of DNC. One may notice another nonparametric, k-NN classi- fier [49] reports 76.57% top-1 acc., based on Reseer55. [49] is trained with 130 epochs; in this setting, DNC gains 76.64%. Moreover, as mentioned in $2. [49] poses huge storage demand, Le., retaining the whole ImageNet training set (i.e. 1.2M images) to perform the k-NN decision rule, and suffers from very low efficiency, caused by extensive comparisons between each test image and all the training images. These limitations prevent the adoption of [49] in real application scenarios. In contrast, DNC only relies on a small set of class representatives (i.e., four sub-centroids per class) for classification decision decision-making and causes extra computation budget during network deployment.
Table Classification toppiiiaaaiiooo------- top-1 and top- accu- racy on ImageNet [25] val.
Method
Backhone
#Params top-1 top-5
ResNet [2]
25.56M
76.20% 93.01%
ResNet50
DNC-ResNN
23,51M
76.49% 93.08%
DNC-ResNet ResNet101
ResNet [2]
44,55M
77.52% 93.06%
42.50M
77.80% 93.85%
Swin [3]
49.61M
83.02% 96.29%
Swin-S
DNC-Swin
48.84M
83.26% 96.40%
Swin [3]
87.77M
83.36% 96.44%
DNC-Swin Swin-B
86.75M
83.68% 97.02%
4.2 EXPERIMENTS ON SEMANTIC SEGMENTATION
Dataset. Theeevuuuatinn for semantic segmenttion is carried out on ADE20K [37] and Cityscapes [26].
Segmentation Network Architecture. For comprehensive evaluation, we approach DNC on three famous segmentation models (i.e., FCN [34], DeepLabya [35], UperNet [36]), using two backbone ar- chitectures (i.e., ResNet101 [2] and Swin-B [3]) For the segmentation models, the only architec- tural modification is the removal of "segmentation head" (i.e., 1x1 conv based, pixel-wise classi- fication layer). For the backbone networks, werepecctvvlyy adopt parametric classifier based and our nonpara- metric, DNC based versions, which are both trained on ImageNet [25] and reported in Table 2, for initialization. Thus for each segmentation model, we derive four variants from the different combi- nations of parametric and DNC versions of the backbone and segmentation network architectures.
as the codebase, and follow the default training settings. We train FCN and DeepLabys with ResNet101 using SGD optimizer with initial learning rate 0.1, and UperNet with Swin-B using Adam with an initial learning rate 6e-5. For all the models, the learning rate is scheduled following a polynomial annealing policy. As common practices [102, 103], we train the models on ADE20K t train n with crop 51 12x5 12 and batch size 16; on Cityscapes tra in with crop size 769 x 769 and batch size 8. All the models are trained for 160K iterations on both datasets. Standard data augmentation techniques are used, including scale and color jittering, flipping, and cropping. The parree-as of DNC are by default set as: K = 10 and μ 1= 0.999.
Training. We adopt mmsegment
Performance on Segmentation. As summarized in Table 3, our DNC seg- mentation models, no matter whether using DNC based backbones, obtain better performance over parametric competitors, i.e,, FCN + 101, DeepLabys + R1s UperNet* Swin-B, across different segmentation and backbone network architectures. Taking as an example the famous FCN, the original version gains 39.91% 91% and 75.6% mIoU on ADE20K and City- scapes, respectively. By comparison, with the same backbone ResNer101,, DNC-FCN boosts the scores to 41%
Table 3: Segmentation mIoU score on ADE20K [37] and Cityscapes [26] val (top-1 acc. on ImageNet [25] val of backbones are also reported for reference).
Method
Backbone
ImageNet
#Params
ADE20K
Cityscapes
top acc.
mTo0
mToU
ResNet101 [2]
77.32%
68.6M
39.9%
75.6%
FCN [34]
Rese
77.80%
68.6M
40.4%;o4
76.3%
ResNet101 [2]
77.52%
68.5M
41.1%
76.7%
DNC-FCN
DNC-ResNett0l
77.80%
68.5M
42.3%
19.5%
Deeplabvs [35]
ResNett01 [2]
77.52%
62.7M
44.1%
78.1%
NettRe
77.80%
62.7M
44.6%
78.7%
ResNet101 [2]
77.52%
62.6M
45.0%
79.1% 10
DNC-DeopLabys
NNC-ResNed001
77.80%
62.6M
45.7%E-14
19.
UporNet [36]
Swin-B
83.36%
48.0%
79.8%
DNC-Swin-B
83.68%
90.6M
48.4%
80.1%
Swin-B [3]
83.36%
90.5M
48. 68
80.5%
DNC-UppeNee
DNC
83.68%
90.5M
50.5%;
1..
and 76.7%. When turning to DNC pre-trained backbone DNCCRessNe101,, our DNC-FCN outper- forms again its parametric counterpart - FCN, i.e., 42.3% vs 40.4% on ADE20K, 77.5% vs 76.3% on
Cityscapes. Similar trends can be also observed for DeepLabys and UperNet.
7

---

Published as a conference paper at ICLR 2023
Analysis on Transferability. One appealing feature of DNC is its strong transferabilityy DNC learns classification by directly comparing data samples in the feature space. The results in Table 3 also evidence this point. For example, DeepLaby; even parametric classifier based segmentation model - can achieve large performance gains, i.e., 44.6% vx 44.1% % on ADE20K, 78.7% vs 78.1 % on Cityscapes, after using DNC-ResNer for fine-tuning. When it comes to DNC-DeepL.aby better performance can be achieved, after replacing ResNet101 with DNC-ResNet101, i.e., 45.7% vs 45.0% on ADE20K, 79.8% vs 79.1% 1% on Cityscapes. We speculate this is because, when the segmentation and backbone networks are both built upon DNC, the model only needs to adapt the original repre- sentation space to the target task, without learning any extra new parameters. Also, these impressive results reflect the innovative opportunity of applying our DNC for more downstream visual recogni- tion tasks, either as a new classification network architecture or a strong and transferable backbone.
4.3 STUDY OF AD-HOC EXPLAINABILITY
So far, we have empirically showed that, by inheriting the intuitive power of Nearest Centroids and the strong representation learning ability of DNNs, DNC can serve as a transparent yet powerful tool for visual recognition tasks with improved transferability. When anchoring the class sub sub-centroids to real observations (i.e., actual images from the training dataset), instead of selecting them as cluster centers (i.e., mean features of set of training images), one may expect that DNC will gain enhanced ad-hoc explainability. Next we will show this is indeed possible, only at negligible performance cost.
Experimental Setup. We still train DNC version of ResNet50 on ImageNet train for 100 epochs. In the first 90 epochs, the model is trained in a standard manner, i.e., computing the class sub-centroids as cluster centers. Then we anchor each sub-centroid to its closest training image, based on the co- sine similarity of features. In the final 10 epochs, the sub-centroids only updated as the features of their anchored training images. Besides this, all the other training settings are as normal. In this way, we can get a more inter- pretable NeC-Res..
(LI OR (LL |> AND
|>[,,
AND
Interpretable Class Sub- centroids. The top of Fig.3 plots our discovered sub- centroid images for four ImageNet classes. These representative images are diverse in appearance, viewpoints, illuminations, scales, etc., characterizing their corresponding classes and allowing humans to view and understand.
AND
H
OR (LL,
H AND
AND
OR
AND
AND
IL
THEN (goose)
Figure 3: Top: sub-centroid images. Bottom: rule created for "goose".
Performance with Improved Interpretability, We then report the score of our DNC-ResNet50 based on the interpretable class representatives on Image- Net val. As shown in Table 4, enforcing the class sub-centroids as real training images only brings marginal performance degradation (e-g.. 76.49% 76.37% top-1 acc.), while coming with better in- terpretability. More impressively, our explainable DNC-ResNee50 even outperforms the vanilla black-box ResNet50, e.g., 76.37% vs 76.20%.
Table 4: Classification top-1 and top- 5 ac- curacy ImageNet [25] using cluster cen- ter vs resembling real observation as class sub- centroids, based DeNNC--ReNet500rchtteeeeee
Sub-centroid
Architecture
top-1 1 top 5
cluster center real observation
Res
76.49% 93.08%
76.37%
93.04%
ResNet50
76.20%
93.01%
Explain Inner Decision-Making Mode based on IF ... . -Then Rules. With the simple Nearest Cen- troids mechanism, we can use the representative images to form a set of IF Then rules [4], so as intuitively interpret the inner decision-making mode of DNC for human users. In particular, let f denote sub-centroid image for class IiT representative images for all the other classes, and I query image. One linguistic logical IF ... -hhen rule can be generated for î:
IF (IT, /) > [T, J.] AND T, f] [T, 12) AND AND [T, f [T, 12)) THEN (class c),
(9)
where | stands for similarity, given by DNC. The final rule for class e is created by combining all the rules of K sub-centroid images f of class c (see Fig. 3 bottom):
IF (II, f1] [T. f.] AND AND [T, f.) > [T, frl) OR (1, [ [1, Li] AND AND 11 fz) > [1, Ir))
(10)
OR (11 fx] [1, AND -.- AND 11 [, > U1 Frl) THEN (class c).
8

---

Published as a conference paper at ICLR 2023
With welt
lanae
Groat
i T
18.0%
48, 18.1%
00000%%
80.9%
50.7%
DNC's pediction toucan
DNC's s prodiction white wolf Gromdtrthh kuaazz
(a)
Groundmuth toucan
(b)
Figure 4: DNC can provide ressmiilarity-bssee interpretation. For the two test samples, we only plot the normalized similarities for their corresponding closest sub-centroids from top-4 scoring classes.
Table 5: A set of ablative experiments ImageNet [25] val and ADE20K [37] val.
ImageNet top-1 top-5
ADE20K
Memory (#batch)
ImageNet
ImageNet
ADE20K
mTo0
top-1 top-5
14
top-1
top-5
mToU
77.31%
93.01%
43.2%
0
77.49%
93.09%
U
73.82%
93.02%
42.7%
77.54%
93.32%
5
44.0%
700
77.58%
93.16%
0.9
76.41%
93.07%
43.6%
77.68%
93.63%
10
44.3%
800
77.64%
93.35%
0.99
77.33%
93.51%
44.0%
77.80%
93.85%
20
44.0%
900
77.75%
93.67%
0.999
77.80%
93.85%
44.3%
1000
77.80%
93.85%
0.9999
77.31%
93.48%
44.2%
(a) Number of sub-centroids
(h) Memory size
(c) Momentum coefficient (f))
(K) for each class
Based on (Dis)similaritt to Sub-centroid Images. Based on the interpretable class representatives, DNC can explain its predictions by letting users view and verify its computed (dis)similarity between query and class sub-centroid images. As shown in Fig. 4(a), an observation is correctly classified, DNC thinks it looks (more) like a particular exemplar of "toucan". However, in Fig. 4(b), DNC struggles to assign the observation to two ewemplar from "white wolf" and "kuvasz" respectively, and makes wrong decision finally. Though users are unclear how DNC an image feature, they can easily understand the decision-making mode [43] (e.g., why is one class predicted over another), and verify the calculated (dis)similarity the evidence for classification decision.
Interpret Prediction Prediictioorioo
4.4 DIAGNOSTIC EXPERIMENT
To perform extensive ablation experiments, we train ResNet101 classification and DeepLabys seg- mentation models for 100 epochs and 80K iterations, on ImageNet and ADE20K, respectively.
Class Sub-centroids. Table 5a studies the impact of the number of class sub-centroids (K) for each class. When K = 1, each class is represented by its centroid the average feature vector of all the training samples of the class (Eq, 3), without clustering. The corresponding bascline obtains 77.31% top-1 acc. and 43.2% mIoU for classification and segmentation, respectively. For classification, increasing K from 1 to 4 leads to better performance (i.e., 77.31% - 77.80%). This supports our hypothesis that one single class weight/center is far from enough to capture the underlying data distri- bution and proves the efficacy of our clustering based sub-class pattern mining. We stop using K > as the required memory exceeds the computational limit of our hardware. We find similar trends on segmentation; using more sub-cen sub-centroide ce-eetetroid (K: 1 + 10) brings noticeable performance boost: 43.2%-> 44.3%. However, increasing K above 10 provides marginal even negative gain. This may be because over-clustering finds some insignificant patterns, which are trivial or harmful for decision-makinn
External Memory, We next study the influence of the external memory, only used in image clas- sification. As shown Table 5b, DNC gradually improves the performance as the increase of the memory size. It reaches 77.80% top-1 acc. at size 1000. However, the results still not reaching the performance saturating point, but rather the upper limit of our hardware's 's computational budget. Momentum Update. Last, we ablate the effect of the momentum coefficient/ f (Eq. 8) that controls the speed of sub-centroid online updating. From Table Sc we find the behaviors of μu are consistent in both tasks. In particular, DNC performs well with larger coefficients (i.e., E [0.999, 0.9999), signifying the importance slow updating. The performance degrades when μ E (0.9, 0.99). and encounters a large drop when p= (i.e., only using batch sub-centroids as approximations).
CONCLUSION
We present deep nearest centroids (DNC), building upon the classic idea of classifying data samples according to nonparametric class representatives. Compared to classic parametric models, DNC has merits in: i) systemic simplicity by bringing the intuitive Nearest Centroids mechanism to DNNs; ii) automated discovery of latent data structure using within-clan clustering; iii) direct supervision of representation learning, boosted by unsupervised sub sub-pattern mining: iv) improved transferability that lossless transfers learnable knowledge across tasks; and v) ad-hoc explainability by anchoring class exemplars with real observations. Experiments confirm the efficacy and enhanced interpretability.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This research was supported by the National Science Foundation under Grant No. 2242243.
REFERENCES
Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recog-
nition. In: ICLR (2015)
[2] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: CVPR
(2016) I, 2, 3, 7, 8, 18, 19, 20, 21, 22, 23
[3] Liu, Z., Lin, Y., Cao, Y., Hu, H.. Wei, Y.. Zhang, Z., Lin, S., Guo, B.: Swin transformer: Hierarchical vision transformer using shifted windows. In: ICCV (2021) 1, 2, 6, 7, 18, 19, 20, 28, 29, 30
[4] Angelov, P., Soares, Towards explainable deep neural networks (xdnn). Neural Networks 130, 185-194 (2020) 3, 8
[5] Li, O., Liu, H., Chen, C., Rudin, C.: Deep learning for case-based reasoning through proto- types: A neural network that explains its predictions. In: AAAI (2018) 1,
[6] Hayashi, H., Uchida, S.: A discriminative gaussian mixture model with sparsity. In: ICLR (2021)
[7] Zhou, T., Wang, W., Konukoglu, E., Van Gool, L.: Rethinking semantic segmentation: A prototype view. In: CVPR (2022) 1
[8] Mettes, P., van der Pol, E., Snoek, C.: Hyperspherical prototype networks. In: NeurIPS (2019)
1,
[9] Fix, E., Hodges Jr, J.L.; Discriminatory analysis nonparametric discrimination: Small sam- ple performance. Tech. rep., California Univ Berkeley (1952) 1,
[10] Cover, T. Hart, P.: Nearest neighbor pattern classification. IEEE TIT 13(1), 21-27 (1967) 3
[11] Kolodner, J.L.: An introduction to case-based reasoning. Artificial Intelligence Review 6(1), 3-34 (1992) 3,
[12] Kohonen, T: Learning vector quantization. In: Self-Organizing Maps, pp. 175-189 (1995)
[13] Chaudhuri, B.: A new definition of neighborhood of a point in multi-dimensional space. Pattern Recognition Letters 17(1), 11-17 (1996)
[14] Webb, A.R.: Statistical pattern recognition. John Wiley & Sons (2003) 1,
[15] Kim, B., Rudin, C., Shah, J.A.: The bayesian model: A generative approach for case- based reasoning and prototype classification. In: NeurlPS (2014)
[16] Newell, A., Simon, H.A., et al.: Human problem solving, vol. 104 (1972) 2,
[17] Rosch, E.H.: Natural categories. Cognitive Psychology 4(3), 328-350 (1973) 5
[18] Aamodt, A., Plaza, E.: Case-based reasoning: Foundational issues, methodological varia- tions, and system approaches. AI Communications 7(1), 39-59 (1994) 1,2
[19] Slade, S.: Case-based reasoning: A research paradigm. AI magazine 12(1), 42-42 (1991)
[20] Sánchez, J.S., Pla, F., Ferri, F.J.: On the use of neighbourhood- based con-paraeetric classi-
fiers. Pattern Recognition Letters 18(11-13), 1179-1 186 (1997) 3
[21] Gou, J., Yi, Z., Du, L., Xiong, T.: A local mean- based k-nearest centroid neighbor classifier. The Computer Journal 55(9), 1058-1071 (2012)
[22] Mensink, T. Verbeek, J., Perronnin, F,, Csurka, G.: Distance-based image classification: Generalizing to new classes at near-zero cost. IEEE TPAMI 35(11), 2624-2637 (2013) 1
[23] Cuturi, M.: Sinkhom distances: Lightspeed computation of optimal transport. In: NeurIPS
(2013) 2, 5, 6, 22, 24, 28
[24] Asano, Y.M., Rupprecht, C., Vedaldi, A.: Self-labelling via simultancous clustering and rep-
resentation learning. In: ICLR (2020) 2, 5, 24, 28
10

---

Published as a conference paper at ICLR 2023
[25] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M.S., Berg, A.C., Li, F.: Imagenet large scale visual recognition challenge. IJC 115(3), 211-252 (2015) 2, 3, 6, 7, 8, 9, 18, 19, 20, 21, 23, 24, 25, 26
[26] Cordts, M., Omran, M., Ramos, S., Rehfeld, T., Enzweiler, M., Benenson, R., Franke, U., Roth, S.. Schiele, B.: The cityscapes dataset for semantic urban scene understanding. In: CVPR (2016) 2, 3, 6, 7, 20, 23, 24, 28, 30
[27] Biehl, M., Hammer, B., Villmann, Т.: Prototype- baseed models in machine learning. Wiley Interdisciplinary Reviews: Cognitive Science 7(2), 92-111 (2016) 2, 3,5
[28] Simonyan, K., Vedaldi, A., Zisserman, A.: Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 (2013) 2,
[29] Zeiler, M.D., Fergus, R.: Visualizing and understanding convolutional networks. In: ECCV (2014)
[30] Zhou, B., Khosla, A., Lapedriza, A., Oliva, A., Torralba, A.: Learning deep features for discriminative localization. In: CVPR (2016) 2,
[31] Lipton, Z.C.: The mythos of model interpretability; In machine learning, the concept of interpretability is both important and slippery. Queue 16(3), 31-57 (2018) 2
[32] Rudin, C.: Stop explaining black box machine learning models for high stakes decisions and
use interpretable models instead. Nature Machine Intelligence 1(5), 206-215 (2019) 2, 3
[33] Krizhevsky, A., Hinton, G.: Learning multiple layers of features from tiny images. Technical
report, University of Toronto (2009) 3, 6, 18, 19, 20, 21, 22, 23
[34] Long, J., Shelhamer, E., Darrell, T.: Fully convolutional networks for semantic segmentation. In: CVPR (2015) 3, 7, 19, 20
[35] Chen, L.C., Papandreou, G., Schroff, F., Adam, H.: Rethinking atrous convolution for seman-
tie image segmentation. arXiv preprint arXiv:1706.05588 (2017) 3, 7, 19, 20, 23
[36] Xiao, T. Liu, Y.. Zhou, B., Jiang, Y., Sun, J.: Unified perceptual parsing for scene under-
standing. In: ECCV (2018) 3, 7, 19, 20, 28, 29,
[37] Zhou, B., Zhao, H., Puig. X., Fidler, S., Barriuso, A., Torralba, A.: Scene parsing through
ade20k dataset. In: CVPR (2017) 3, 9, 20, 28, 29
[38] Friedman, J.H.: The elements of statistical learning: Data mining, inference, and prediction.
Springer (2009)
[39] Hand, D.J., Yu, K.; Idiot's bayes- not so stupid after all? International Statistical Review 69(3), 385-398 (2001) 3
[40] Breiman, L.: Random forests. Machine Learning 45(1), 5-32 (2001) 3
[41] Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20(3), 273-297 (1995)
[42] LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. nature 521(7553), 436-444 (2015)
[43] Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L., Zhong, C.: Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistics Surveys 16, 1-85 (2022)
3, 5,
[44] Boiman, O., Shechtman, E.,, Irani, M.: In defense of nearest-neighhor based image classifica- tion. In: CVPR (2008) 3
[45] Guillaumin, M., Mensink, T., Verbeek, J., Schmid, C.: Tagprop: Discriminative metric learn- ing in nearest neighbor models for image auto-annotation. In: ICCV (2009) 3
[46] Lippmann, R.P.: Pattern classification using neural networks. IEEE Communications Maga- zine 27(11), 47-50 (1989)3 3
[47] Salakhutdinov, R., Hinton, G.: Learning a nonlinear embedding by preserving class neigh- bourhood structure. In: Artificial Intelligence and Statistics. pp. 412-419 (2007)
[48] Papernot, N., McDaniel, P.: Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint
(2018) 3
[49] Wu, Z., Efros, A.A., Yu. S.X.: Improving generalization via scalable neighborhood compo-
nent analysis. In: ECCV (2018) 3, 23
11

---

Published as a conference paper at ICLR 2023
[50] Garcia, S., Derrac, J., Cano, J., Herrera, F. Prototype selection for nearest neighbor classifi- cation: Taxonomy and empirical study. IEEE TPAMI 34(3), 417-435 (2012)
[51] Yang, H.M., Zhang, X.Y., Yin, F., Liu, C.L.: Robust classification with convolutional proto- type learning. In: CVPR (2018) 3
[52] Guerriero, S., Caputo, B., Mensink, T:: Deepnem: Deep nearest class mean classifiers. In:
ICLR workshop (2018) 3, 23, 25
[53] Snell, J., Swersky, K., Zemel, R.S.: Prototypical networks for few-shot learning. In: NeurIPS (2017)3
[54] Dong, N., Xing, E.P.; Few-shot semantic segmentation with prototype learning, In: BMVC (2018) 3
[55] Jetley, S., Romera-Paredes, B., Jayasumana, S., Torr, P.: Prototypical priors: From improving
classification to zero-shot learning. arXiv preprint arXiv:1512.01 511.01 (2015)
[56] Xu, W., Xian, Y., Wang. J., Schiele, B., Akata, Z.: Attribute prototype network for zero-shot
learning. In: NeurlPS (2020) 3
[57] Rebuffi, S.A., Kolesnikov, A., Sperl, G., Lampert, C.H.: icarl: Incremental classifier and representation learning. In: CVPR (2017)
[58] Quattoni, A., Collins, M., Darrell, T.: Transfer learning for image classification with sparse prototype representations. In: CVPR (2008) 3, 5,
[59] Biehl, M., Hammer, B., Schneider, P., Villmann, T.: Metric learning for prototype- based classification. In: Innovations in Neural Information Paradigms and Applications, pp. 183- 199 (2009) 3, 5,
[60] Erhan, D., Bengio, Y., Courville, A., Vincent, P.: Visualizing higher-layer features of deep
network. University of Montreal 1341(3), I (2009) 3
[61] Mahendran, A., Vedaldi, A.: Understanding deep image representations by inverting them. In: CVPR (2015)
[62] Yosinski, J., Clune, J., Nguyen, A., Fuchs, T., Lipson, H.: Understanding neural networks through deep visualization. arXiv preprint arXiv:1506.0657 (2015)
[63] Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.R., Samek, W.: On pixel-wise
explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one
10(7), e0130140 (2015)
[64] Shrikumar, A., Greenside, P., Kundaje, A.: Learning important features through propagating
activation differences. In: ICML (2017)
[65] Selvaraju, R.R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., Batra, D.: Grad-cam: Visual explanations from deep networks via gradient-based localization. In: ICCV (2017) 3
[66] Ribeiro, M.T., Singh, S., Guestrin, C.: "why should i trust you?" explaining the predictions of any classifier. In: KDD (2016)
[67] Zintgraf, L.M., Cohen, T.S., Adel, T., Welling, M.: Visualizing deep neural network deci-
sions: Prediction difference analysis. In: ICLR (2017)
[68] Koh, P.W., Liang, P.: Understanding black-box predictions via influence functions. In: ICML (2017)
[69] Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. In: NeurIPS (2017)
[70] Laugel, T., Lesot, M.J., Marsala, C., Renard, X., Detyniecki. M.: The dangers of post-hoc interpretability; Unjustified counterfactual explanations. In: IJCA (2019)* 3
[71] Arrieta, A.B., Díaz-Rodríguez N., Del Ser. J., Bennetot, A., Tabik, S., Barbado, A., Gareía, S., Gil-López, S., Molina, D., Benjamins, R., et al.: Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai. Information Fu- sion 58, 82-115 (2020) 3
[72] Chen, C., Li, O., Tao, D.. Barnett, A., Rudin, C., Su, J.K.: This looks like that: deep learning for interpretable image recognition. In: NeurIPS (2019)
12

---

Published as a conference paper at ICLR 2023
[73] Alvarez Melis, D., Jaakkola, T.: Towards robust interpretability with self-explaining neural networks. In: NeurIPS (2018)
[74] Kim, B., Wattenberg, M., Gilmer, J., Cai, C., Wexler, J., Viegas, F., et al.: Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). In: ICML (2018)
[75] Wang, T.: Gaining free or low-cost interpretability with interpretable partial substitute (2019)
[76] Subramanian, A., Pruthi, D., Jhamtani, H., Kirgpairkpatrick, T., Hovy, E.: Spine: Sparse interpretable neural embeddings. In: AAAI (2018)= 3
[77] Chen, X., Duan, Y., Houthooft, R., Schulman, J., Sutskever, L, Abbeel, P.: Infogan: Inter- pretable representation learning by information maximizing generative adversarial nets. In: NeurlPS (2016)>
[78] You, S., Ding, D., Canini, K., Pfeifer, J., Gupta, M.: Deep lattice networks and partial mono- tonic functions. In: NeurlPS (2017) 3
[79] Ming, Y., Xu, P., Qu, H., Ren, L.: Interpretable and steerable sequence learning via proto- types. In: KDD (2019) 3
[80] Ank, Pfister, T.: Protoattend: Attention- based prototypical learningJJurraall Journal of Machine Learning Research 21, 1-35 (2020)
[81] Nauta, M., van Bree, R., Seifert, C.: Neural prototype trees for interpretable fine-grained image recognition. In: CVPR (2021) 3
[82] Pang, T., Xu, K., Dong, Y., Du, C., Chen, N., Zhu, J.: Rethinking softmax cross-entropy loss for adversarial robustness. In: ICLR (2020) 4
[83] Zhang, X., Zhao, R., Qiao, Y., Li, H.: Rbf-softmax: Learning deep representative prototypes with radial basis function softmax. In: ECCV (2020) 4
[84] Rosch, E.: Cognitive representations of semantic categories. Journal of Experimental Psy- chology: General 104(3), 192 (1975)
[85] Knowlton, B.J., Squire, L.R.: The learning of categories: Parallel brain systems for item
memory and category knowledge. Science 262( 40), 1747-1749 (1993) 5
[86] Knight, P.A.: The sinkhorn-knopp algorithm: convergence and applications. SIAM Journal Matrix Analysis and Applications 30(1), 261-275 (2008)
[87] Hadsell, R., Chopra, S., LeCun, Y.: Dimensionality reduction by learning invariant map-
ping. In: CVPR (2006) 5, 28
[88] Sohn, K.: Improved deep metric learning with multi-class n-pair loss objective. In: NeurlPS (2016) 28
[89] Kaya, M., Bilge, H.$.: Deep metric learning: A survey. Symmetry 11(9), 1066 (2019) 28
[90] Boudiaf, M., Rony. J., Ziko, L.M. Granger, E., Pedersoli, M., Piantanida. P., Ayed, I.B.: A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses. In: ECCV (2020)
[91] Sun, Y., Cheng, C., Zhang, Y., Zhang, C., Zheng, L., Wang, Z., Wei, Y.: Circle loss: A unified perspective of pair similarity optimization. In: CVPR (2020) 28
[92] Suzuki, R., Fujita, S., Sakai, T.: Are loss: Softmax with additive angular margin for answer retrieval. In: Asia Information Retrieval Symposium. pp. 34-40 (2019)
[93] Khosla, P., Teterwak, P., Wang, C., Samna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., Krishnan, D.: Supervised contrastive learning. In: NeurlPS (2020) 5. 28
[94] Bautista, M.A., Sanakoyeu, A., Tikhoncheva, E., Ommer, B.: Cliqueenn: Deep unsupervised
exemplar learning. In: NeurIPS (2016) 5, 28
[95] Xie, J., Girshick, R., Farhadi, A.: Unsupervised deep embedding for clustering analysis. In: ICML (2016) 28
[96] Caron, M., Bojanowski, P., Joulin, A., Douze, M.: Deep clustering for unsupervised learning of visual features. In: ECCV (2018) 28
13

---

Published as a conference paper at ICLR 2023
[97] Yan, X., Misra, I., Gupta, A., Ghadiyaram, D., Mahajan, D.: Clusterfit: Improving general-
ization of visual representations. In: CVPR (2020) 28
[98] Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P. Joulin, A.: Unsupervised learning of visual features by contrasting cluster assignments. In: NeurlPS (2020) 28
[99] Li, J., Zhou, P., Xiong, C., Hoi, S.C.: Prototypical contrastive learning of unsupervised rep- resentations. In: ICLR (2020) 28
[100] Van Gansbeke, W., Vandenhende, S., Georgoulis, S., Proesmans, M., Van Gool, L.: Scan: Learning to classify images without labels. In: ECCV (2020) 28
[101] Yaling Tao, Kentaro Takagi, K.N.:
representation learning via instance
discrimination and feature decorrelation. In: ICLR (2021) 5,28
[102] Xie, E.,, Wang. W., Yu, Z., Anandkumar, A., Alvarez, J.M., Luo, P:: Segformer: Simple and efficient design for semantic segmentation with transformers. In: NeurIPS (2021)
[103] Cheng, B., Schwing, A.G., Kirillov, A.; Per-pixel classification not all you need for seman-
tic segmentation. In: NeurIPS (2021) 7
[104) Caesar, H., Uijlings, J., Ferrari, V:: Coco-stuff: Thing and stuff classes in context. In: CVPR (2018) 16, 19
[105] Sandler, M., Howard, A., Zhu, M., Zhmoginov, A., Chen, L.C.: Mobilenetv2: Inverted resid- uals and linear bottlenecks. In: CVPR (2018) 18
[106] Huh, M., Agrawal, P., Efros, A.A.: What makes imagenet good for transfer learning? arXiv
preprint arXiv: ww8.68061..... (2016) 20, 21
[107] Wah, C., Branson, S., Welinder, P., Perona, P., Belongie, S.: The caltech-ucsd birds-200-2011
dataset (2011) 21
[108] Wang. X., Gao, J., Long, M., Wang, J.: Self-tuning for data-efficient deep learning. In: ICML. (2021) 21
[109] Oh Song, H., Xiang, Jegelka, S., Savarese, S.: Deep metric learning via lifted structured feature embedding. In: CVPR (2016)
[110] Plested, J., Gedeon, T.: Deep transfer learning for image classification: survey. arXiv preprint arXiv:2205. .09904 (2022)
[111] Recht, B., Roelofs, R., Schmidt, L., Shankar, V:: Do imagenet classifiers generalize ima- genet? (2019) 22
[112] Wang, W., Zhou, T., Yu, F., Dai, J., Konukoglu, E., Van Gool, L.: Exploring cross-image
pixel contrast for semantic segmentation. In: ICCV (2021) 23, 28
[113] Short, R., Fukunaga, K.: The optimal distance measure for nearest neighbor classification. IEEE Transactions on Information Theory 27(5) (1981) 28
[114] Hastie, T., Tibshirani, R.: Discriminant adaptive nearest neighbor classification and regres- sion. In: NeurIPS (1995) 28
[115] Bromley, J., Guyon, I., LeCun, Y., Säckinger, E., Shah, R.: Signature verification using a"
siamese" time delay neural network. NeurIPS (1993) 28
[116] Schroff, F., Kalenichenko, D., Philbin, J.: Facenet: A unified embedding for face recognition and clustering. In: CVPR (2015) 28
[117] Chen, W., Chen, X., Zhang, J., Huang, K.: Beyond triplet loss: deep quadruplet network for person re-identiification In: CVPR (2017) 28
[118] Wu, C.Y., Manmatha, R., Smola, A.J., Krahenbuhl, Sampling matters in deep embedding learning. In: ICCV (2017) 28
[119] Taigman, Y., Yang, M., Ranzato, M., Wolf, L.: Deepface: Closing the gap to human-level performance in face verification. In: CVPR (2014) 28
[120] Wang, H., Wang, Y., Zhou, Z., Ji, X., Gong, D., Zhou, J., Li, Z., Liu, W.: Cosface: Large margin cosine loss for deep face recognition. In: CVPR (2018)
[121] Cao, Z., Liu, D., Wang, Q., Chen, Y.: Towards unbiased label distribution learning for facial pose estimation using anisotropic spherical gaussian. In: ECCV (2022)
14

---

Published as a conference paper at ICLR 2023
[122] Cao, Z., Chu, Z., Liu, D., Chen, Y.: A vector-based representation to enhance head pose estimation. In: WACV (2021) 28
[123] Xiao, T., Li, S., Wang, B., Lin, L.,, Wang, X.: Joint detection and identification feature learn- ing for person search. In: CVPR (2017) 28
[124] Gutmann, M., Hyvärinen, A.: Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In: AISTATS (2010) 28
[125] Oord, A.v.d., Li, Y., Vinyals, O.: Representation learning with contrastive predictive coding.
arXiv preprint Xiv:
1 0001800077777 007.00778 (2018) 28
[126] Hjelm, R.D., Fedorov, A., Lavoie-Marchildon. S., Grewal, K., Bachman, P., Trischler, A.,
Bengio, Y.: Learning deep representations by mutual information estimation and maximiza- tion. In: ICLR (2019)
[127] Chen, X., Fan, H., Girshick, R., He, K.: Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003. 044997 (2020)
[128] Chen, T., Kormblith, S., Norouzi, M., Hinton, G.: A simple framework for contrastive learning of visual representations. In: ICML (2020)
[129] He, K., Fan, H., Wu, Y., Xie, S., Girshick, R.: Momentum contrast for unsupervised visual
representation learning. In: CVPR (2020) 28
[130] Biehl, M., Hammer, B., Villmann, T.: Distance measures for prototype based classification.
In: International Workshop Brain Inspired Computing (2013) 28
[131] Ji, X., Henriques, J.F., Vedaldi, A.: Invariant information clustering for unsupervised image
classification and segmentation. In: ICCV (2019) 28
[132] Zhan, X., Xie, J., Liu, Z., Ong, Y.S., Loy, C.C.: Online deep clustering for unsupervised
representation learning. In: CVPR (2020) 28
[133] Yang, B., Fu, X., Sidiropoulos, N.D., Hong, M.: Towards k-means frinndf spaces: Simulta-
neous deep learning and clustering (2017) 28
[134] J., K., Wang, F., Qian, C., Li, C., Lin, Z., Zha, H.: Deep comprehensive correlation mining for image clustering. In: ICCV (2019) 28
[135] Tschannen, M., Djolonga, J., Rubenstein, P.K., Gelly, S., Lucic, M.: On mutual information
maximization for representation learning. arXiv preprint arXiv: 13625 (2019) 28
[136] Wu, Z.., Xiong, Y., Yu, S.X., Lin, D.: Unsupervised feature learning via non-parametric in-
stance discrimination. In: CVPR (2018) 28
[137] Tao, Y., Takagi, K., Nakata, K.: Clustering-frieee representation learning via instance dis-
crimination and feature decorrelation. arXiv preprint arXiv:2106.00131 (2021)
[138] Tsai, T.W., Li, C., Zhu, Mice: Mixture of contrastive experts for unsupervised image clustering. In: ICLR (2020) 28
[139] Liu, D., Cui, Y.. Chen, Y., Zhang, J., Fan, B.: Video object detection for autonomous driving: Motion-aid feature calibration. Neurocomputing 409 (2020) 29
[140] Wang, Y., Liu, D., Jeon, H., Chu, Z., Matson, E.T.: End-to-end learning approach for
tonomous driving: A convolutional neural network model. In: ICAART (2019)
[141] Liu, D., Cui, Y., Guo, X., Ding, W., Yang, B., Chen, Y.: Visual localization for autonomous driving: Mapping the accurate location in the city maze. In: ICPR (2021) 29
[142] Ronen, M., Finder, S.F., Freifeld, O.: Deepdpm: Deep clustering with an unknown number
of clusters. In: CVPR (2022) 30
[143] Cheng. Z., Liang. J., Choi, H.. Tao, G., Cao. Z., Liu, D., Zhang, X.: Physical attack on
monocular depth estimation with optimal adversarial patches. In: ECCV (2022) 30
[144] Cheng, Z., Liang, J., Tao, G., Liu, D., Zhang, X.: Adversarial training of self-supervised monocular depth estimation against physical-worf wooldd attacks. In: ICLR (2023) 30
15

---

Published as a conference paper at ICLR 2023
SUMMARY OF THE APPENDIX
This appendix contains additional details for the ICLR 2023 submission, titled Visual Recognition with Deep Nearest Centroids" ". The appendix is organized follows:
S provides the pseudo code of DNC.
B introduces more quantitative results on image classification.
$C gathers additional semantic segmentation results on COCO-Stuff [104] dataset.
$D presents the corresponding error bars on Tables and 3.
SE investigates the potential of DNC in sub-categories discovery.
SF reports the transferability of DNC towards other image classification task.
$G evaluates the performance of DNC on ImageNetv2 test sets.
SH compares the performance of using k-means and Sinkhom-Knopp clustering algo-
rithms.
ŞI compares DNC with different distance (learning) based classifiers.
ŞJ reports additional diagnostic experiments for further investigations on K, update ratio external memory, ImageNet capacity, feature size, and temperature parameter (6).
SK offers more detailed discussions regarding the GPU memory cost.
SL depicts more visual examples regarding the ad-hoc explainability of DNC.
S plots qualitative semantic segmentation results.
ŞN gives additional review of representative literature on metric-ddistanc--eamiig and clustering- unsupervised representation learning.
$O discusses our limitations, socictal impact, and directions of our future work.
16

---

Published as a conference paper at ICLR 2023
A
PSEUDO CODE OF DNC AND CODE RELEASE
The pseudo-code of DNC is given in Algorithm 1. To guarantee reprodacibility, our code is available
https///gihuub.com///ennngg 11/D/annnIINNCCC 11/DNC.
Algorithm Pseudo-code of DNC in PyTorch-like style.
non-parametric sub-centroids X
# X: feature embeddings (N x D)
A C: number of classes
# K: number of ceb--eenrcids for each class
R: sinhorn-knopp iteration number
mu: momentum coefficient (Eq.8)
epsilon: hyper-parameter in the sinkhorn-Knopp algorithm (Bq.
aet (XC label)
1-- Model Prediction and Training Loss (Eq.7) =-
Lmage-to-centroid assignment (N K C, Eq.5)
I. - tarch.einsume (' I'n ckd->nke', K, P)
output = torch. amax (L, dim=l)
loss = CrossEnt (cutput, label)
rub-centroid Estimation
for in range
init_L LI...,
- anl conlinnnssttringgieee (init_
# assignments and embeddings for images in class c m_c I[label == c]
x.c labee == c, ....
find images that are assigned to each sub-centroid and correctly classified tile repeat (m_e, tile=K)
m_q Q m_c_tile
find images with label с that are correctly classified x_c_tile repeat (m_c, cile=x_c.shape(111] x x_c_q = x_c x x_c_tile
= torch, mm trrggsrasppoee x_c_g)
num assignments for each sub-centroid of class c
torch. sum (m_q, dim=0)
momentum update (Fq.8) is torch. (n) 0:
PLC = mu P(c, 1= 0, :] + (1-mu) f(n != 0, :] P !- 0, :] P_c
return loss
aef cnline ceciinee_lusttringgee (L, iters=3, epsilon=0.05)
torch.exp epsilen)
- torch. sum (Q)
for in range (R)
row normalization
0 /= torch.sum (C, dim=1, keepdin=True)
Q /= K
co column normalization
/= torch. sum (L, dim=0, keepdin=Truc)
/- N
make sure the sum of each column to be == N
return one hot (Q)
17

---

Published as a conference paper at ICLR 2023
B MORE EXPERIMENTS ON IMAGE CLASSIFICATION
Additional Results on CIFAR-10 [33]. CIFAR-10 dataset contains 60K (50K/10K for train/ test) 32 32 colored images of 10 classes. Table 6 reports additional comparison results on CIFAR-10, based on ResNet-18 [2] network architecture. As seen, in terms of top-1 1 accuracy, our DNC is 0.94% higher than the parametric counterpart, under the same training setting.
Table 6: Classification top-1 accuracy CIFAR-
10 [33] test. #Params: the number of learnable param- eters (same for other tables). See SB for more details.
Method
Backbone
#Params
top-1
ResNet [2] ResNet18
11.17M
93.55%
DNC-ResNet
11.16M 94.49%
Additional Results CIFAR-100 [33]. Table 7 reports comparison results on CIFAR-100, based on ResNet50 and ResNet101 network architectures [2]. CIFAR- 100 dataset has 100 classes with 500 training images and 100 testing images per class. We can find that, DNC obtains consistently better performance, compared to the classic parametric counterpart. Specifically, DNC is 0.10% higher on ResNet50, and 0.16% higher ResNet101, in terms of top-1 accuracy.
Table 7: Classification top-1 accuracy CIFAR- 100 [33] test, using lightweight backbone network ar- chitectures MobileNet-V2 [105], and Swin-T [3]. See $B for more details.
Method
Backbone
#Params
top-1
ResNet [2]
23.71M
79.81%
ResNet50
DNC-ResNet
23.50M
79.91%
ResNet [2]
42.70M
79.83%
DNC-ResNet ResNet101
42.49M
79.99%
Additional Results on ImageNet [25] using Lightweight Backbone Network Architectures. Ta- ble 8 reports performance ImageNet [25]. using two lightweight backbone architectures: MobileNet-V2 [105], and Swin-T [3]. As can be seen, DNC, again, attributes decent performance. In particular, our DNC is 0.28% and 0.30% higher is worth noticing that DNC can efficiently reduce the number of learnable parameters when the para- metric classifier occupies a massive proportion in the original lightweight classification networks. Taking MobileNet- V2 as an example: our DNC reduces the number of learnable parameters from 3.50M to 2.22M.
MobileNet-V V2 and Swin-Tiny, respectively. It
Table 8: Classification top accuracy on ImageNet [25]
val. See şB for more details.
Method
Backbone
#Params
top-1
MobileNet [105]
3.50M
71.76%
MobileNet-V2
DNC-MobileNet
2.22M
72.04%
Swin [3]
28.29M
81.08%
Swin-T
DNC-Swin
27.52M
81.38%
18

---

Published as a conference paper at ICLR 2023
C MORE EXPERIMENTS ON SEMANTIC SEGMENTATION
For through evaluation, we conduct extra experiments on COCO-Stuff [104], famous semantic seg- mentation dataset. COCO-Strt Croffff contains 9K/1K images for train/test of 80 object classes and 91 stuff classes. Similar to $4.2, we approach DNC FCN [34], DecppLabv and UperNet [36], using two backbone architectures, Lee, ResNet101 [2] and Swin-B [3]. All models are obtained by following the standard training settings of COCO-Stuff train, i.e,, crop size 612x512, batch size 16, and 40K iterations. From Table 9 we can draw similar conclusions: in comparison with the parametric counterpart, DNC produces
precise segments and yields improved transferability.
Table 9: Segmentation mloU score COCO-Stuff [104]. See $C for more details.
COCO-Stuff test
Method
Backbone
mToU]
ResNet101 [2]
32.63%
FCN [34]
DNC-ResNet101
f2.29%
ResNet101 [2]
33.04%
DNC-FCN
DNC-ResNet101
33.49%
ResNet101 [2]
36.01 %
DeepLabys [35]
DNC-ResNet101
36.28%to.27
ResNet101 [2]
36.51 10.50
DNC-DeepLabva
DNC-ResNet101
36.79%+0.7
Swin-B [3]
42, 77%
UperNet [36]
DNC-Swin-B
42.84%
Swin-B [3]
43. 43.13
DNC-UperNet
DNC-Swin-B
ro.55
D ERROR BARS
In this section, we report standard deviation error bars on Tables 10, 11, and 12 for our main ex- periments regarding image classification ($4.1) and semantic segmentation ($4.2). The results are obtained by training the algorithm three times, with different initialization seeds.
Table 10:
Classification top-1 accuracy on CIFAR-10 [33] test with error bars. See $1) for more details.
Method
Backbone
#Params
top-1 1
ResNet [2]
23.52M
95.55 (0.14)%
ResNet50
DNC-ResNet
23.50M
95.78
(0.12)%
ResNet [2]
42.51M
95.58 + (0.13)%
DNC-ResNet ResNet101
42.49M
95.82 + (0.13)%
Table 11:
Classification top-1 and top-5 accuracy on ImageNet [25] val with error bars. See şD for more details.
Method
Backhone
#Params
top-1
top-5 5
ResNet [2]
25.56M
76.20
(0.10)%
93.01 %
ResNet50
DNC-ResNet
23.51M
76.49 (0.09)%
93.08%
ResNet [2]
44.55M
77.52
(0.11)%
93.06%
ResNet101
DNC-ResNet
42.50M
77.80
(0.10)%
93.85%
Swin [3]
49.61M
83.02
(0.14)%
96.29%
Swin-S
DNC-Swin
48.84M
83.26 (0.13)%
96.40%
Swin [3]
87.77M
83.36 (0.12)%
96.44%
Swin-B
DNC-Swin
86.75M
83.68 + (0.12)%
97.02%
19

---

Published as a conference paper at ICLR 2023
Segmentation mloU score on ADE20K [37] val and Cityscapes [26] vall with error bars. See $D for more details.
Table 12:
ImageNet
ADE20K
Cityscapes
Method
Backbone
#Params
Lop-1 acc.
mIoU
mIoU
ResNet101 [2]
77.52%
68.6M
39,9 (0.11)%
75.6 (0.13)%
FCN [34]
DNC-ResNet101
77.80%
68.6M
40.4 = (0.11)%
76.3 + (0.12)%
ResNet101 [2]
77.52%
68.5M
41.1 - (0.10)%
76.7 + (0.11)%
DNC-FCN
DNC-ResNer101
77.80%
68.5M
42.3 (0.10)%
77.5 (0.11)%
ResNet101 [2]
77.52%
62.7M
44.1 + =0.13))%
78.1 + (0.12)%
DeepLabyy [35]
DNC-ResNet101
77.80%
62.7M
44.6 (0.13)%
78.7 - (0.13)%
ResNet101 [2]
77.52%
62.6M
45.0 (0.10)%
79.1 = (0.13)%
DNC-DeepLabya
DNC-ResNet101
77.80%
62.6M
45.7 = (0.09)%
79.8 (0.12)%
Swin-B [3]
83.36%
90.6M
=8.0
79.8 (0.13)%
UperNet [36]
DNC-Swin-B
83.68%
90.6M
3.4400.100)
80.1 - (0.12)%
Swin-B [3]
83.36%
90.5M
48.6 (0.09) %
80.5 (0.10)%
DNC-UperNet
DNC-Swin-B
83.68%
90.5M
50.5 - (0.09)%
80.9 + (0.10)%
E EXPERIMENTS ON SUB-CATEGORIES DISCOVERY
Through unsupervised, within-class clustering, our DNC represents each class as a set of auto- matically discovered class sub-centroids (i.e., cluster center). This allows DNC to better describe the underlying, multimodal data structure and robusty depict for rich intra-class variance. In other words, our DNC can effectively capture sub-class patterns, which is conducive algorithmic per- formance. Such a capacity of sub-patter mining is also considered crucial for good transferable features representations learnt on coarse classes are capable of fine- mne-grained recognition [106].
In order to quantify the ability of DNC for automatic sub-category discovery, we follow the exper- imental setup posed by [106] - learning the feature embedding using coarse-grained object labels, and evaluating the learned feature using fine-grained object labels. This evaluation strategy allows us to assess the feature learning performance regarding how well the deep model can discover vari- ations within each category. A conjecture is that deep networks that perform well on this test have an exceptional capacity to identify and mine sub-class patterns during training, which the proposed DNC seeks to rigorously establish.
In particular, the network is first trained on coarse-graing granine labels with the baseline parametric soft- max and with non-parametric DNC using the network architecture. After training on coarse classes, we use the top-1 nearest neighbor accuracy in the final feature space to measure the accuracy of identifying fine-grained classes. The classification performance evaluated in such setting is referred as induction accuracy as in [106]. Next we provide our experimental results on CIFAR 100 [33] and ImageNet [25], respectively.
Performance of Sub-category Discovery on CIFARI00. CIFAR100 includes both fine-grained annotations 100 classes and goasee-rraiedd annotations 20 classes. We examine sub-category discovery by transferring representation learned from 20 classes to 100 classes. As shown in Ta- ble 13, DNC consistently outperforms the parametric counterpart: DNC increases 0.12%, in terms of the standard top-1 accuracy, on both ResNet50 and ResNet101 architectures. Nevertheless, when transferred to CIFAR 100 (i.e., 100 classes) using k-NN, a significant loss occurs on the base- line: 53.22% and 54.31% 1% top-1 1 acc. ResNet50 and ResNet101, respectively. Our features, on the other hand, provide 14.24% and 13.82% improvement over the baseline, achieving 67. 67.46% and 68.13% top-1 acc. on 100 classes ResNet50 and R01 respectively. In addition, in com- parison the parametric model, our approach results in only a smaller drop in transfer performance, Le., -1887 -32.99 ResNet50, and -18447 vs -32.17 on ResNet101.
20

---

Published as a conference paper at ICLR 2023
Table 13: Top-1 induction aceuracy on CIFAR-100 [33] test using CIFAR-20 pre-trained models. Numbers reported with k- nearest neighbor classifiers. See $E for more details.
Method
Backbone
20 classes 100 classes
ResNet [2]
86.21%
53.22%
ResNet50
DNC-ResNet
86.33%
67.46%
ResNet [2]
86.48%
54.31%
DNC-ResNet ResNet101
86.60%
68.13%
Performance of Sub-category Discovery ImageNet. Table 14 provides experimental results of sub-category discovery on ImageNet val. As in [106]. 127 coarse ImageNet categories are obtained by top-down clustering of 1K ImageNet categories on WordNet tree. Training the 127 coarse classes, DNC improves the performance of baseline by 0.10% and 0.03%, achieving 84.39% and 85.91% % on ResNet50 and ResNet101, respectively. When transferring to the 1K ImageNet classes using k-NN, our features provide huge improvements, i.e., 8.98% and 9.29%, over the baseline.
Table 14: Top-1 induction accuracy on ImageNet [25] val using ImageNet-127 pre-trained models. Numbers reported with k-nearest neighbor classifiers. See ŠE for more details.
Method
Backbone
127 classes 1000 classes
ResNet [2]
84.29%
43.23%
ResNet50
DNC-ResNet
84.39%
22.21%
ResNet [2]
85.88%
45.31 %
ReC-ResNet ResNet101
85.91%
54.60%
The promising transfer results on CIFARIO0 and ImageNet serve as strong evidence to suggest that DNC is capable of automatically discovering meaningful sub-class patterns latent visual structures that are not explicitly presented in the supervisory signal, and hence handle intra-class variance and boost visual recognition.
F TRANSFERABILITY TOWARDS OTHER IMAGE CLASSIFICATION TASK
In addition to conducting the coarse-to-fin -oeeee transfer learning experiment ($E), further evaluate the transfer learning performance by applying ImageNet-trained weight to Caltech-UCSD Birds- 200-2011 (CUB-200-2011) dataset [107], following [108-110].
Specifically, CUB-200-2011 dataset comprises 11,788 bird photos arranged into 200 categories, with 5,994 for training and 5,794 for testing. All the models ResNet50 architecture [2], and are trained for 100 epochs. SGD optimizer is adopted, where the learning rate is initialized as 0.01 and organized following polynomial annealing policy. Standard data augmentation techniques used, including flipping, cropping and normalizing. Experimental results are reported in Table 15. As seen, DNC is +0.73% and +0.39% higher Top-1 and Top-5 acc., respectively. This clearly verifies that DNC owns better transferability.
Table 15: Classification top-1 and top-5 accuracy on CUB-200- 2011 test [107]. See &F for more details.
Model (IrageNet-trained)
Backbone
top-1
top-5
ResNet [2] DNC-ResNet
84.48%
96.31 %
ResNet50
85.21%
96.70%
21

---

Published as a conference paper at ICLR 2023
For parametric softmax classifier, both the feature network and softmax layer fully learnable parameters. That means, for a new task, the softmax classifier has to both finetune the feature network and train part. The class centers are not freely learnable parameters; they are directly computed from training data the feature space. For new task, DNC just needs fine-tune the only learnable part the feature network; the class centers are still directly computed from the training data according to the clustering assignments, without end-to-end training. Hence DNC owns better transferability during network fine-tuning.
softmax layer. However, for DNC, the feature network is the only learnable
G EVALUATION ON IMAGENETV2 TEST SETS
We evaluate DNC-ResNet50 ImageNetv2 [111] test sets, ie., "Matched Frequency", "Thresh- old0.7" and "Top Images". Each test set contains images for each ImageNet class, collected from MTurk. In particular, each MTurk worker is assigned with a certain classes. Then each worker is asked to select images belonging to his/her target class, from several candidate images sampled from large image pool well ImageNet validation set. The output is selection frequency for each image, ie., the fraction of MTurr workers selected the image in a task for its target class. Then three test sets developed according different principles defined the selection frequency, For "Matched Frequency", [111] first approximated the selection frequency distribution for each class using those "reaannta ImageNet validation images. According to these class class-specific distribu- tions, ten test images are sampled from the candidate pool for each class. For "Threshold0.7" [111] sampled ten images from each class with selection frequency least 0.7. For "Top Images", [111] selected the ten images with the highest selection frequency for each class. The results on these three test sets are shown Table 16. seen, our DNC exceeds the parametric softmax based ResNet50 by +0.52-0.89% top-1 1 and +0.26-0.47% top-5 acc..
Table 16: Classification top-1 and top-5 accuracy on ImageNetv2 test [111]. See $G for more details.
test set
Method
Backbone
top-1
top-5 5
ResNet [2]
63.30%
84.70%
MatchedFrequencc
ResNet50
NNC-ResNet
63.96%
85.17%
ResNet [2]
72.70%
92.00%
Threshold0.7
ResNet50
DNC-ResNet
73.59%
92.26%
ResNet [2]
78. 10%
94.70%
Toplmages
ResNet50
DNC-ResNet
78.62%
94.96%
H SINKHORN- Vs M-MEANS CLUSTERING
To further probe the impact of Sinkhorn-Knopp based clustering [23), we further report the perfor- mance of DNC by using the classic k-means clustering algorithm, CIFAR-10 and CIFAR100 datasets [33]. From Table 17 We can find that DNC with Bonkhorn-Knopp performs much better and much more training-efficientt
Table 17:
Classification top-1 and training time on CIFAR-10 and CIFAR 100 [33] test sets. See HH for more details.
Dataset
Method
Backbone
top-1
Training time (hours)
ANC-k-means
93.88%
4.5
CI [33]
ResNet50
DNC-Sinkhorn
95.78%
2.5
DNC-k-mennt
77.86%
16.3
CIFAR 100 [33]
ResNet50
DNC-Sinkhorn
79.91%
3.7
22

---

Published as a conference paper at ICLR 2023
I COMPARISON WITH DISTANCE (LEARNING) BASED CLASSIFIERS
We next compare our DNC with two metric based image classifiers [49, 52] and one distance learn- ing based segmentation model [112].
We first compare DNC with DeepNCM [52]. DeepNCM conducts limilarity-based classification using class means. As DeepNCM only describes its training procedures for CIFAR-10 and CIFAR- 100 [33], we make the comparison on these two datasets to ensure fairness. From Table 18 we can find that, DNC significantly outperforms DeepNCM by +2.11% CIFAR-10 and +7.16% on CIFAR-100, respectively.
DeepNCM simply abstracts each class into single class mean, failing capture complex within- class data distribution. contrast, DNC considers sub-centers per class. Note that this is not just increasing the number of class representatives. This requires accurately discovering the underlying data structure. DNC therefore jointly conducts automated online clustering (for mining sub-class patterns) and supervised representation learning (for cluster center based classification). Finding meaningful class representatives is extremely challenging and crucial for Nearest Centroids. As the experiment in $H and Table 17 revealed, simply adopting classic k-means causes huge performance drop and significant training speed delay. Moreover, DeepNCM computes class mean on each batch, which makes poor approximation of the real class center. contrast, DNC adopts the external memory for more accurate data densities modeling DNC makes clustering over the large memory of numerous training samples, instead of the relatively small batch. Thus DNC better captures complex within-class variants and addresses two key properties of prototypical exemplars: sparsity and expressivity [58, 59], and eventually gains much more promising results.
Table 18:
Classification top-1 on CIFAR-10 and CIFARI00 [33]
test. See ȘI for more details.
Dataset
Method
Backbone
top-1 1
DeepNCM [52]
93.67%
CIFAR-10
ResNet50
DNC
95.78%
DeepNCM [52]
72.75%
CIFAR-100
ResNet50
DNC
79.91%
We also compare DNC with DeepNCA [49]. DeepNCA a deep k-NN classifier, which conducts similarity- -baed classification based top-k nearest training samples. As [49] only reports results on ImageNet [25], we make the comparison on ImageNet to ensure fairness. Note that 130 training observe that, DNC outperforms DeepNCA. As we discussed in $2 and $4.1, DeepNCA poses huge storage demand, i.e., retaining the whole Ima- geNet training set (i.e., 1.2M images) to perform the k-NN decision rule, and suffers from very low efficiency, caused by extensive comparisons between each test sample and ALL the training images. These limitations prevent the adoption of [49] in real application scenarios. In contrast, DNC only relies on a small set of class representatives (i.e., four sub-centroids per class) for decision-making and causes no extra computation budget during network deployment.
epochs used, as in [49]. From Table 19
Table 19: Classification top-1 on ImageNet [25]
val. See II for more details.
Method
Backbone
top-1
DeepNCA [49] DNC
76.57%
ResNet50
76.64%
Finally, we compare DNC with ContrastiveSeg [112] on Cityscapes [26] val,, using ResNet101 [2] backbone and DeepLabV3 [35] segmentation architecture. ContrastiveSeg applies contrastive learn- ing to better shape the feature embedding space, so as to improve semantic segmentation perfor- mance. However, ContrastiveSeg still relies the softmax classifier; it is essentially a distance
23

---

Published as a conference paper at ICLR 2023
learning boosted parametric classifier. From Table 19 we can observe that, DNC greatly surpasses ContrastiveSeg by 0.6% mIoU.
Table 20: Segmentation mloU score on Cityscapes [26] val. See $1 for more details.
Method
Backbone
mIoU
ContrastiveSeg Sontrastvveog--Deeplayy DeepLabvv DNC-DeepLabvs
79.1%
ResNet101
79.8%
These three experiments solidly demonstrate our effectiveness on both image classification and seg- mentation tasks, even compared with other distance (learning) based counterparts.
J ADDITIONAL DIAGNOSTIC EXPERIMENT
Output Dimensionality. As stated in $4, the final output dimensionality of our DNC is set as many as the one the last layer the parametric counterpart, for the sake of fair comparison. However, owing the distance-fsimilarrty-bo sionality. Table 21, we further study the influence of the output dimensionality of DNC. As seen, when setting the final output dimensionality 1280, higher than the initial 2048 dimension configuration, i.e., 76.49%. We attribute the reason for the better balance between memory capacity and feature dimensionality with the limitation of hardware computational budget- when reducing the final output dimensionality, the expressibility of the final feature is weakened but more image features can be stored in the external memory for more accurate sub-centroid estimation.
nature, DNC has the flexibility to handle any output dimen-
achieve 76.61% % top-1 acc., which
Table 21: Ablative experiments regarding the final output di- mensionality on ImageNet [25] val. See SI for more details.
Output
ImageNet
dimensionality
top-1
top-5 5
640
76.23%
92.83%
1024
76.28%
92.90%
1280
76.61%
93.12%
2048
76.49%
93.08%
Temperature Parameter in (6). Parameter in (6) trades off convergence speed with close- ness to the original transport problem [23, 24]. Table 22, we further study the impact of e on ImageNet [25] val.
Table 22: Ablative experiments regarding temperature pa- rameter in (6) ImageNet [25] val. See for more details.
ImageNet
top-1
top-5
0.01
76.34%
92.97%
0.05
76.49%
93.08%
0.1
76.40%
93.02%
Number Centroids K. As shown in Table 23, we set with different values based on the number of training samples of each class. Specifically, ImageNet contains between 732 and 1300 training images (Himages) per class. Then, K 1 assigned to the class having between 732 and 874 training samples, K 2 to the class having between 875 and 1016 samples, K the class
24

---

Published as a conference paper at ICLR 2023
having between 1017 and 1158 samples, and K to the class having between 1159 and 1300 samples. We can find that we gain slightly better performance, +0.06% higher in top-1 acc. when compared with fixing K = 4 for all the classes.
Table 23:
Ablative experiments with varying K on different
classes on ImageNet [25] val. See ŞJ for more details.
K
ImageNet
range
top-1
top-5
unique value 4 varying between and
76.49%
93.08%
76.55%
93.10%
K MEMORY COST
In our experiment, we only adopt external memory for ImageNet classification. Below we pro- vide more discussion regarding this point. Semantic segmentation is pixel-wise classification task, where each training image provides numerous pixel samples for each class. For ImageNet classifica- tion, however, each training image is only assigned to single class. Moreover, ImageNet has IK classes, while in general semantic segmentation only has dozens of classes. Therefore, for a training mini-bated of, for example, 256 images, every class in segmentation usually has many training pixel samples in each banih, this allows us to use large K for clustering. However, under the same setting, for each mini-batch, there must have many ImageNet classes that do not have corresponding image samples- we have 1000 classes but each mini-batch only has 256 training images. This is why we need to build an external memory during ImageNet classification. This also why apply- ing Nearest Centroids for batch-wise ImageNet classification training is extremely challenging; [52] cannot handle ImageNet classification, as only computes class means in a batch-wise manner.
Table 24a and 24b provide statistics of GPU memory cost (per GPU usage) with respect to the number of class centroids K and external memory size respectively. The statisties are gathered during the training of DNC-ResNet50 on ImageNet, using eight V100 GPUs. In our experiment, we set the size of the external memory as 256,000 image samples (i.e., 1000 batches) and K for DNC-ResNet50 (i.e., total of 4000 class sub-centroids on ImageNet). More specifically, for a memory with #batch=1000, it stores 8 #gpu x 32 #batch size x 1000 #batch 256000 #image examples. In comparison, for segmentation, when set K = 10 (i.e., total of 1500 class sub- centroids for ADE20K), we have 65,536 pixel training samples in each mini-batch of 16 training images, without using memory.
Table 24: Statistics of GPU memory cost with respect to the number of class centroids K and external memory size, where 1000 batches = 256000 image samples. See SK for more details.
K (Fixed memory size: 1000 batches)
GPU memory
memory size
GPU memory cost (GB per GPU)
cost (GB per GPU)
(Fixed K = 4)
16.07
400 batches
11.88
2
19.04
600 batches
16.35
3
22.03
800 batches
21.65
26.31
1000 batches
26.35
(a) GPU memory cost w.rl number of centroids K
(b) GPU memory cost wand external memory size
L ADDITIONAL STUDY OF AD-HOC EXPLAINABILITY
Interpretable Class Sub-centroids. In Fig. show more examples of sub-centroid images for eight ImageNet classes. These representative images are automatically discovered by DNC, and can be intuitively viewed by users. As seen, the class sub-centroid images are able capture diverse characteristics of their classes, in the aspects of appearance, viewpoints, scales, illuminations, elc.
Interpret Prediction Based on (Dis)similarity Sub-centroid Images. Fig. 6 provides more re- sults regarding the (dis)similarity-basee based interpretation of DNC prediction. As seen, based on the similarity of test images to the class sub-centroid images, users can clearly understand the deci- sion making mode and make verification. DNC's compelling explainability enables it to establish trustworthiness with humans and empowers its potential in high stake applications.
25

---

Published as a conference paper at ICLR 2023
Labrador retriever
streefcur
airliner
bee
motor sconter
beacon
junco
Figure 5: Sub-centroid images for eight randomly chosen classes from ImageNet [25]. See $L for more details.
26

---

Published as a conference paper at ICLR 2023
stanteso cal
Persian cat
Eggypliinn
17.4%
00000S
81.9%
DNC's prediction: slamese cat Groundtruth: stamese cat
grille
6,8%
91.3%
DNC's prediction wagon Groundtruth station wagon
fat
red Fox
dhole
greey
13.0%
5.3%
81.2%
DNC's prediction: grey fox
Groundrruth: grey fox
flarringo
pelican
black stork
47.2%
1.3%
51.0%
DNC's prediction: flamingo
Groundruth: spoonbill
Treiirn atepphark.
OX
wetes
bison
48.2%
01.0%
51.3%
DNCs prediction:: Ox
Groundtruth: water buffalo
tape player
Oreeetiee player
Cassete
CD player
$19.8
6.9%
69.8%
DNC's prediction: tape player Groundtruth: cassette player
Figure 6: More examples on DNC interpreting its predictions based on its computed similarity to class sub-centroid images. For each test image, we plot the normalized similarities for the corre- sponding closest sub-centroids from the top-4 scoring classes. See $L for more details.
27

---

Published as a conference paper at ICLR 2023
M QUALITATIVE RESULTS ON SEMANTIC SEGMENTATION
Fig. 7 and Fig. 8 illustrate a few representative visual examples of semantic segmentation results on ADE20K [37] and Cityscapes [26], respectively. In comparison with the parametric counterpart, our approach produces more precise segments in different challenging scenes (for example, where objects with drastic photometric or geometric appearances). For instance, UperNet [36]-Swin-B [3] confuses on neighbouring objects with similar colors (e.g.. desk and chair) and leaves a large felse-ne regions (see the first image of Fig. 7); also has difficulties in segmenting small scale objects (e.g., motorbike semantic parsing). Among these examples, DNC consistently demonstrates supreme performance. Essentially, we argue that the proposed DNC has a stronger ability to super- vises the pixel embedding space via anchoring sub-centroids directly, leading to better predictions on segmenting such hard cases.
N ADDITIONAL LITERATURE REVIEW
This section gives additional review of representative literature on metric/dissance-llmming and clustering- based unsupervised representation learning.
Metric Learning. The goal of metric learning (also a.k.a distance learning) is to learn a distance metric/embedding which brings together similar samples and pushes away dissimilar ones. Metric learning has a long history, dating back to some early work for more than few decades ago [113, 1 114]. In particular, diverse metric learning objective functions, such as contrastive loss [87,93, 115], triplet loss [116], quadruplet loss [117], and n-pair loss [88], were proposed to measure similarity in the feature space for representation learning, and showed significant benefit in a wide range of applica- tions, such as image retrieval [118], face recognition [116, 119-122], and person re-identification [123], to name a few representative ones. Recently, metric learning gained astonishing success in learning transferable deep representations from massive unlabeled data [89]. A family of instance- based approaches used the contrastive loss [124, 125] to explicitly compare pairs of image repre- sentations [125-129]. Another group of methods adopted clustering-
strategy; they learn unsupervised representations by discriminating between groups of images without expensive pair- wise comparison between image instances [24, 94-101]. More recently, there are some efforts that revisit the idea of metric learning in supervised learning setting [91-93, 112].
As distance- paaninee/simiilrity-bassse tatives for classification, the fields of metric learning and distance- based classification are natu- rally related and the selection of proper distance measure impacts the success of distance-based classifiers [130]. Historically, metric learning and class center discovery are two critical research topics in the field of distance-based classification. As a nonparametric, distance-based classifier, DNC can be viewed as learnable metric function, which is trained to compare data samples un- der the guidance of the corresponding semantic labels. Although current distance learning based algorithms also optimize the feature space by comparing data samples, they need parametric soft- max for classification. Their trained models are still black-box parametric classifiers without any interpretability. In sharp contrast, DNC directly assigns an observation to the class of the closet centroids, without using parametric softmax. Moreover, its distance- classification decision- making mode allows DNC effortless adopt existing metric learning techniques (and the way of its current training can be already viewed as performing metric learning).
classifiers rely on the similarity between samples and class represen-
Clustering- based Self-supervised Representation Learning. There is a recent trend to bind self- supervised representation learning with clustering. Basically, clustering based self-supervised rep- resentation learning is more efficient for large-scale training data and more tolerant of the similar- ity (semantic structure) among data samples, compared with the instance-level counterpart. More specifically, early approaches [24, 94, 96, 97, 100, 131, 132] learn representations of image samples and cluster assignments in an alternative manner, i.e., group features into clusters derive pscudo supervisory signal and subsequently employ it for supervising representation learning. In very re- cent, numerous efforts have been devoted to simultaneous clustering and representation learning based on, e.g., data reconstruction [95, 133], mutual information maximization [131, 134, 135], or contrastive instance discrimination [98, 99, 101, 136-138].
Our work is also related to these clustering based unsupervised representation learning methods, especially the ones [24, 98] resorting to the fast Sinkhom-Knopp algorithm [23] for robust clus-
28

---

Published as a conference paper at ICLR 2023
Swin-B
Otas
Swirz
Olus
Figure Qualitative semantic segmentation results of UperNet [36]-Swin-B [3] and DNC on ADE20K [37] val. Red and green bounding boxes represent the same zoom-in area on UperNet [36]-Swin-B [3] and DNC, respectively. See SM for more details.
tering. They aim to learn transferable representation from massive unlabeled data. Although also involving similar clustering procedure for automatic sub-pattern mining. DNC targets build- ing a strong similarity-based classification network in the standard supervised learning setting. In DNC, the automatically discovered class sub-centroids are informative class representatives, which explicitly capture latent data structure of each class, and serve as classification evidence with clear physical meaning. The whole training procedure is hybrid of class-wise online clustering (for un- supervised sub-class discovery) and sub-centroid based classification (for supervised representation learning). This well addresses the nature of Nearest Centroids and brings novel insights into the visual recognition task itself.
O LIMITATION AND FUTURE WORK
Limitation. One limitation of our approach is that the Sinkhorn- Knopp algorithm runs in time Ō(g)) which would reduce the training efficiency. Though in practice, we find 3 sinkhorn loops per training iteration is sufficient enough for model representation, bringing a minor computational overhead (i.e., ~5% training delay on ImageNet). This also indicates possible directions for future research.
Social Impact. This work introduces DNC possessing the nature of nested simplicity, intuitive decision-makinn mechanism and even ad-hoc explainability. On positive side, the approach ad- vances model accuracy and is valuable in safety-sensitive applications by showing the advanced robustness on sub-categories discovery, e.g.. quality analytics, autonomous driving (139-141], etc. For potential negative social impact, DNC struggles in handling out-of-distribution data, which
29

---

Published as a conference paper at ICLR 2023
Swin-B B
Our
Swin-BB
Ous
Figure Qualitative semantic segmentation results of UperNet [36]-Swin-B [3] and DNC on Cityscapes [26] val. Red and green bounding boxes represent the same zoom-in area on UperNet [36]-Swin-B [3] and DNC, respectively. See SM for more details.
common limitation of all the discriminative classifiers. Hence its utility in open- world scenarios should be further examined.
Future Work. Despite DNC's systemic simplicity and efficacy, it also comes with challenges and unveils some intriguing questions. For example, incorporating more powerful, time-efficient online clustering algorithms into DNC might improve training speed and test accuracy. Also, the number of class centroids K currently is set to fixed value for all classes, which may not be opti- mal given that intra-class variability varies across classes. Our experiments in $J and Table 23 also suggest that simply varying K with the number of training samples of the class can boost perfor- mance. Thus adopting the clustering algorithms that do not require a predefined and fixed number of clusters [142] may allow DNC to automatically determine K for different classes, which eventually benefit performance. addition, instead of only considering first-order statistics, DNC could be enhanced by second-order statistics, which contain more useful information, but must contend with the computational overhead they impose. Another essential future direction deserving of further in- vestigation is the in-depth analysis of the intrinsic properties of DNC, such as its robustness against perturbation, adversarial attack [143, 144], and out-of- disttriiibttoonn data, with the comparison of the softmax based counterpart. This endeavor would help to better understand the nature of para- metric and nonparametric classifiers and reveals directions for further improvement. Furthermore, will explore the possibility of unifying close-set and open-world visual recognition within framework. Finally, considering the iinilarittyddistance -asen nature of DNC, the incorporation of metric learning based training objectives is also another promising direction for further boosting the performance. Given the vast number of technique breakthroughs in recent years, we expect flurry of innovation towards these promising directions. Overall, we believe the results presented this paper warrant further exploration.
30


Reviews:
[{"review_id": "wnxd2eDo-QK", "reviewer": "Reviewer_1ipB", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper proposes a method that learns deep prototype representations, by revisiting the nearest centroids clustering in the setting of deep network training. The authors construct a framework to combine the gradient descent kind of learning of neural networks with the distance-based learning of cluster centroids. In this paper, the clustering is done class-wise, defining a number of centroids K per class.", "summary_of_the_review": "The paper presents an interesting idea, well-constructed, and with a clear presentation of the devised methodology. The main concerns with the paper regard placement within the current literature, clarification of several statements made in the introduction and experimental analysis. \n\nThis work seems to relate with metric learning, e.g. contrastive learning, approaches but the authors do not cover this part. Indeed, equation 7 reminds very clearly the 'contrastive loss function' (with the difference that only the min distance is considered in (7)), see [3] equation 1.\n\nThe reported results are only marginally 'better' than baseline networks, but the authors do not compare with other related approaches (mentioned few above), making the evaluation of the contribution of deep prototype learning difficult to appreciate. Also in the discussio nabout explainability, methods based on classification by nearest sample (arcloss/arcface-like methods, contrastive approaches) should have been considered. \n\n[3] https://openaccess.thecvf.com/content/CVPR2021/papers/Wang_Understanding_the_Behaviour_of_Contrastive_Loss_CVPR_2021_paper.pdf", "strength_and_weaknesses": "__Strenghts__\n- the idea of learning deep centroids is relevant\n- interpretability of the classification with prototypes or a real sample closest to the prototype\n- experiments with different backbones\n\n\n__Weaknesses__\n- _statements about limitations of existing methods are too stretched_, e.g. \n\t1. lack of simplicity or explainability mentioned as weaknesses of existing approaches is not addressed clearly in the paper: the mention of lack of simplicity of existing methods makes one assume that the authors would propose a simpler method. Anyway, it is still absed on gradient descent optimization, with the addition of extra steps to ensure clustering after every update of the weights. Furthermore, the memory and algorithmic complexity of the proposed solution increased, making me wonder where the lack of simplicity is addressed. \n\t2. learning without considering underlying data structures (i.e. by similarity) and on fixed dimensional spaces: the authors miss the relation of this paper with a body of work on similarity-based and distance learning, e.g. contrastive learning or arcloss, is not covered. In these works, learning and optimization of parameters is done on the basis of similarity/metric learning, and subsequently decisions are taken by looking at the closest samples in the latent space. Other methods based on prototype learning are also ignored, e.g. [1][2]\n- _experiments should be extended_: methods based on latent similarity metric learning should be compared to, as the principle of classification/prediction for those methods is the same of closest-prototype picking.\n- _result improvements are marginal, with no statistical analysis of differences or details about replication of experiments_: the results are only very marginally above the baselines, and statistical margins are not reported. Are the results from the best runs of training or e.g. median over 5 runs, average over N runs, etc.? It is difficult to evaluate the contribution of the clutering approach.\n- _explainability/interpretability study needs extension and comparative analysis_: other approaches are used to do predictions based on distance/similarity in the latent space (e.g. supervised contrastive learning, circle loss, arcloss) that are not considered in the comparative analysis, also in terms of interpretability of the classifications. \n\n[1] nauta et al. Neural Prototype Trees for Interpretable Fine-grained Image Recognition\n[2] Chen et al. This looks like that: Deep learning for interpretable image recognition", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "qEfew5QisY", "reviewer": "Reviewer_GtUv", "summary": "", "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": "", "summary_of_the_paper": "This paper considers the use of nearest centroid classifiers in the context of deep neural networks, and in particular a setting where multiple centroids are used per class, obtained through clustering the feature vectors for each class.\nThe proposed method consists in concurrently learning the feature backbone network, and a per-class online clustering. For the clustering an optimal-transport based method is used to approximately equalise the amount of data assigned to each cluster.\nExperiments on image classification (ImageNet, CIFAR-10) and semantic segmentation (ADE20K, Cityscapes) are conducted using different network architectures.\nResults indicate improvements in prediction accuracy when comparing parametric linear classifier heads and nearest centroid classification heads. Moreover, networks pre-trained with the nearest centroid classifier, also transfer better to semantic segmentation tasks. \nIn addition, when using data points close to the cluster centres for classification, the method allows for interpretable results via visualisation of the exemplar used for classification. \n", "summary_of_the_review": "\nThis paper considers nearest centroid classifiers in combination with deep feature learning networks. The authors train the feature network, and cluster the data of each class in parallel using an optimal-transport based technique: a novel combination of existing techniques. \nExperiments on image classification and semantic segmentation compare the centroid-based classifier with a linear classification head, and conclude improved accuracy using centroid-based classifiers.\nExperiments also indicate that centroid-based pre-training for image classification yields better results when fine-tuning for semantic segmentation. \nReplacing centroids with the nearest datapoints (images) induces a small loss in predictive accuracy, but yields an interpretable exemplar-based classifier.\nMy ratings are based on a small perceived technical novelty, combined with some interesting experimental findings. The quality of the presentation can be substantially improved.\n\n### Post-rebuttal comments ###\nAfter reading author rebuttal and other reviews, I maintain my original recommendation of this paper as weak accept. \nThe authors have addressed most of the comments in my review: a number of clarifications have been made, and additional results are added, in particular evaluation on the ImageNetv2 evaluation sets, which confirm the results obtained earlier on the imageNet validation set.  I do not see any major reasons to reject the paper.\n", "strength_and_weaknesses": "\nStrengths:\n\n+ Two different tasks are considered to evaluate the effectiveness of deep nearest centroids classifiers: image classification and semantic segmentation (pixel classification). \n\n+ For each task two datasets are considered: ImageNet, CIFAR-10 for classification, and ADE20K, Cityscapes for semantic segmentation.\n\n+ Multiple network architectures are considered for each experiment.\n\n+ Exploration of the use of training samples rather than cluster centres as anchors for classification is interesting from an interpretability perspective.\n\n+ The use of nearest centroid classification is shown the be beneficial for semantic segmentation: (i) using it to fine-tune the segmentation model, and (ii) using it to pre-train the feature backbone network. Using it for both yields best performance. \n\n \nWeaknesses:\n\n- The claimed improved transferability is shown when pre-training on ImageNet classification, and then fine-tuning on ADE20K/Cityscapes semantic segmentation. There is no experimental evidence that transferability is improved towards other image classification tasks. Such results would be relatively easy to add, and would strengthen the support of the claim of improved transfer of features learned using the centroid-based classifier. \n\n- Experimental results do not include analysis of the stability of the results w.r.t. various sources of randomness in the experimental setup (initialisation of parameters, sampling of training batches). In particular for tables 1 and 2 this would help, as differences in accuracy are relatively small.  For ImageNet classification adding evaluation on the ImageNetv2 test set (https://github.com/modestyachts/ImageNetV2) would also strengthen the experimental results.\n\n- It is not clear where the normalised exponential for of the solution presented in Eq 6 comes from. In my understanding it is a consequence of the KL-regularization used in [25], but which is not adopted here in Eq 5. I guess it is an omission.  \n\n- The effect of the optimal-transport / Sinkhorn clustering approach as compared to a naive k-means approach is not ablated in the paper, while this is the main novelty of the paper over [52] besides using multiple centroids per class.\n\n- The setting of the temperature parameter epsilon in Eq 6 is not discussed, nor is its impact experimentally analysed. \n\n- Relations of the current work to [23,52] are not discussed in sufficient detail, it should be clear from the paper how this work is different from these earlier works. For example, the related work section states that [52] showed weak results even on small datasets, yet it is not clear why the current paper would work better for those cases: the ablations show only limited improvements over the case with K=1 cluster center per class as used in [52]. It is not clear from this why for the current paper experimental comparison to [52] is not included. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5UiGlxiaMYh", "reviewer": "Reviewer_k9FP", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper proposes deep nearest centroids, a new non-parametric classification layer. For each class, a number of sub-centroids are learned during the course of training. At test-time, the prediction is the class corresponding to the closest sub-centroid. The sub-centroids are learned in an iterative fashion: 1) Network parameters are updated to minimize the distance between each sample and the closest sub centroid of the ground truth class 2)  The subcentroids are updated using “momentum updates” using the centroid assignments of the current minibatch + a memory bank.\n\nImprovements are shown on CIFAR-10 (ResNet backbones) and ImageNet (ResNet + Swin backbones). Results on semantic segmentation are even stronger on 3 algo + backbone combinations. If the sub-centroids are restricted to training images, the algorithm shows out-of-the-box interpretability, in the sense that these sub-centroids can be leveraged to explain classification decisions by the model.\n", "summary_of_the_review": "I initally rate this paper below the border, even though the results are strong. See above for a list of my concrens.\nI am happy to adjust my rating if the authors can address my concerns with respect to the novelty and clarity of the paper and update the draft as a result.", "strength_and_weaknesses": "**Strengths**\n\n* The paper shows strong results on both classification and segmentation benchmarks. Ablations are shown to evaluate the impact of #subcentroids, showing that this design choice is important, i.e with no sub-centroid clustering, the algorithm performs worse than the classification layer.\n* While a number of architectural changes have been proposed to neural networks, this paper proposes to modify just the last layer with performance improvements, which is of interest to the ICLR audience.\n* The model provides out-of-the-box interpretability under some constraints. A few epochs before convergence, the authors propose to anchor each sub-centroid to the closest training image which can provide explainable predictions.\n\n**Weaknesses**\n\nSee below for detailed feedback.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4pYnJQpOqD", "reviewer": "Reviewer_3KaQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper proposes a deep nearest centroids (DNC) network for large-scale visual recognition. In contrast to the commonly employed parametric classifier (e.g., a parametric Softmax Classifier), the proposed DNC is claimed to be able to capture the underlying data distributions and is more interpretable. Experiments on a few benchmark visual recognition and semantic segmentation datasets demonstrate the superiority of DNC.\n", "summary_of_the_review": "To summarize, the paper investigates a classific non-parametric classifier and successfully integrates it into deep learning frameworks. Competitive performance have been achieved. The work can provide useful insights into representation learning and visual recognition for the community.\n", "strength_and_weaknesses": "Strength:\n++ Nearest centroids based classifiers have been used in many classification problems and exhibit strong performance compared with its parametric counterparts. This work applies the non-parametric classifier in the basic image classification task and achieves competitive performance by utilising sub-centroids of training samples to describe class distributions.\n++ Thorough experiments have been conducted to support the claims in the manuscript.\n\nWeaknesses:\n-- The number of centroids for each class K seems to be an important hyper-parameter. In the paper, K is set as a unique value for all classes; however, this may not be optimal since the intra-class variability can be very different across different classes. Is it possible to automatically determine the K value for different classes?\n-- The nearest centroids classifier only considers the 1st-order statistics. Would the 2nd-order statistics of clusters contribute to the classification performance?\n-- It would be interesting to compare the errors made by DNC and a parametric softmax classifier. Do they learn complementary knowledge?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%