Toward Faithful Case-based Reasoning through Learning Prototypes in a Nearest Neighbor-friendly Space.
Authors: Seyed Omid Davoudi
Majid Komeili
Venue: ICLR 2022 Poster (2022)
Keywords: case-based reasoning
interpretable machine learning
explainable artificial intelligence
xai
prototype learning

Abstract: Recent advances in machine learning have brought opportunities for the ever-increasing use of AI in the real world. This has created concerns about the black-box nature of many of the most recent machine learning approaches. In this work, we propose an interpretable neural network that leverages metric and prototype learning for classification tasks. It encodes its own explanations and provides an improved case-based reasoning through learning prototypes in an embedding space learned by a probabilistic nearest neighbor rule. Through experiments, we demonstrated the effectiveness of the proposed method in both performance and the accuracy of the explanations provided.

Published conference paper at ICLR 2022
TOWARD FAITHFUL CASE-BASED REASONING THROUGH LEARNING PROTOTYPES IN A NEAREST NEIGHBOR- FRIENDLY SPACE.
Omid Davoodi
Majid Komeili
School of Computer Science
School Computer Science
Carleton University
Carleton University
Ottawa, ON, Canada
Ottawa, ON, Canada
omi d. da voud @earrlaaaoon
ma jajid komei 1 1@carleton.cc.
ABSTRACT
Recent advances machine learning have brought opportunities for ever-increasing use of AI in the real world. This has created concerns about the black-box nature of many of the most recent machine learning approaches. this work, we propose an interpretable neural network that leverages metric and prototype learning for classification tasks. It encodes its own explanations and provides an improved case-based reasoning through learning pro- totypes in embedding space learned by probabilistic nearest neighbor rule. Through experiments, we demonstrated the effectiveness of the proposed method both perfor- mance and the accuracy of the explanations provided.
INTRODUCTION
With the ever-increasing usage of deep learning in real-world situations, interpretable and explainable chine learning has become more and more important. This is because the deeply complex nature and large number of parameters in deep learning models raise concerns about reliability, fairness, transparency, and trust. While some research has been focused explaining the current "black-box" models by offering extra insight about their decisions (Ribeiro al., 2016 Lundberg & Lee [017]] [eelaraju et al.) (017). another approach is to create models that are inherently interpretable (Rudin) 2019).
Some classes of machine learning models are deemed to be inherently more interpreaabeeDoshi-Veeee & Kim. 2017). These include linear models like logistic regression, decision trees, rules-based models, naive bayes, and nearest neighbor models. These models are usually simple or abstract enough that a human can get an understanding of how they make specific decisions. Decisions made by nearest neighbor methods, in particular, can be easily understood by human. But an important disadvantage of nearest neighbor models is that their inference computational cost scales with the amount of training data. This can make them impractical when the dataset is too large.
One of the main ways suggested to combat the cost of nearest neighbor models is to prototypes. Pro- totypes are points in the dataset that represent group of points around them. If the number of prototypes is smaller than the number of data points, using them a proxy of real data for nearest neighbor methods could significantly speed up the inference process, Depending on the number and the position of prototypes, performance differences compared using the whole dataset can be minimal.
Using prototypes for classification is not a new concept. Research was done on nearest prototype classifiers (Bezdek Castelaz, 1977 Kohonen 1990; Seo et al. 2003) and their validity (Kuncheva Bezdek 1998]
Graf et al. (2009). One important domain where these types of classifiers are used is in interpretable classifi
cation (Bien & Tibshirani
2011 Kim al. 2014 Chen et al. 2018 Li 2018), Recently [i et al. 2018

---

Published conference paper at ICLR 2022
presented an explainable neural network structure that represents samples by their distance to some proto- types learned in an embedding space. A fully connected layer gets these distances input and outputs the final class. It learns the prototypes along with the network weights. However, the drawback of that method is that it learns the prototypes in poorly constructed embedding space. Because the structural similarities in the embedding space are not preserved, prototypes are less likely to be surrounded by a group of similar sam- ples. Since these prototypes should represent unknown homogenous clusters that might exist within classes (i.e. subclasses). For example different breeds of dogs within the class dog. We empirically show that [i et al. (2018) fails to preserve such subclasses and even destroys them. We argue that this is due to the lack of a mechanism for learning proper embedding space in conjugation with learning the prototype positions.
the explanations for the model, naturally one may expect that the prototypes
In this paper, we offer an interpretable prototype classification method called Deep Embedded Prototype Network (DEPN). This method is a neural network architecture that finds a good embedding space and number of suitable prototypes for classification. The emhedding space and the prototypes in DEPN are constructed in such a way that high classification performance is achieved. In addition, the decisions of the classifier can be explained by showing the nearest prototypes as a comparative example. We show that the combination of our embedding space and prototype selection method leads to cohesive prototype explanations compared to the state-of-tee of-the-art Li et al. (2018).
The embedding space of DEPN is formed such that samples that are closer to each other in terms of Euclidean distance more similar to each other than samples that further away. It is because the embedding space is learned based on the nearest-neighhor rule. In particular, following (Chauhan et al. (021) an upper bound of the classification error using nearest-neighhour classifier is minimized. While it is very hard to find annotated datasets containing similarity measures between each pair of samples, it is possible to create datasets that contain superclasses each consisting of multiple subclasses. Subclass similarity is, therefore, good proxy for overall sample similarity. The advantage of (Chauban et al., [202]) is that it has been shown to be able to create embedding spaces where even unlabeled subclasses of the data distribution are preserved in the embedding space. This happens despite the model not having any direct knowledge about subclass data. This means that for example, if one of the classes in the data consists of two subclasses, less likely to mix these two subclasses together in the resulting embedding space.
For example, suppose that the problem is the classification between cats and dogs using only a picture of the animal. If the dataset consists of multiple dog and cat breeds, we can assume that it contains multiple subclasses of cats and dogs. the nearest neighbors of a dog sample in the embedding space are other dog samples that belong to the same breed (subclass), the closest samples to a prototype might also belong to the same subclass. We believe that if the subclasses of the closest prototype used to classify a new sample is the same that of that sample, the prototype is a better explanation for the decision taken by the model compared to when the overall class label is correct, but the subclass shows a different breed of the animal. It is important note that the method we provide does not have access to the subelass data. In fact, it doesn't t need the subclass labels to be present at all.
The final result is a neural network that classifies the input using a number of prototypes. can explain its decisions by offering the closest prototype of that class to the human user. Due to the way our embedding space preserves subclass information, the offered explanation is much more likely to be suitable compared to the previous state-of-fet of-the-art method Li et al.) (2018). In particular, our measurements show that our work preserves the subclass neighhorhoods in the embedding space while [i et al. (2018) actively degrades them. This is while DEPN has the same overall performance when measured in superclass accuracy while showing, on average, 125% improvement in subclass accuracy.
There are previous works that might seem similar to our own. Deep k-Nearest-Neighhorr (DKNN) by Pa- method for deep neural networks. This method uses nearest-neighbor labels in the intermediate layers of neural network to assess the validity of a decision. The main idea behind DkNN is that when the network makes a decision, the nearest neighbors in the intermediate layers should also share the same label. If this is not the case for most of the layers, then maybe this decision
pernot & McDaniel (2018) is an interpretability-bas

---

Published conference paper at ICLR 2022
something that came up due to the quirks the final layers of the network. While this focus on nearest neighbors might seem similar to our work, DkNN ultimately offers confidence score for the decisions of the network. In contrast, our method offers examples (prototypes) as explanations for the decisions it takes. In fact, DKNN can be used alongside DEPN to offer confidence scores for its decisions.
The work done by Li et al. (2018) is another method that is quite similar to our work. While the network architecture in both works is mostly the same (especially if MsDNN-AE is used for the encoder), the way they utilize the architecture is quite different. This work is trained end-to-end, but DEPN uses a more gentle two-stage training procedure. The ri loss used in this work does not consider the prototype labels while the one in DEPN does. This work uses the decoder outputs as the representations of its prototypes while the decoder in DEPN is an optional regularization system for MsDNN, the decoder is not able output good representations, this work will not be able to offer proper explanations for its decisions. The explanations in DEPN in contrast, are the nearest same class prototype, which will be represented by training sample. Another difference is that the explanations offered by this method are much less likely to be of the same subclass as that of DEPN.
The work done by Chen et al. (018)) offers prototype explanations-baset on parts of an image. These explanations are inherently different from the sample based explanations DEPN offers. This method is also limited to data that can be split into parts and will not be feasible for other types of data (like tabular data).
2
METHODOLOGY
Our method a neural network with an uncommon structure suited for prototype training. It consists backbone encoder network that transforms the input to a metric space learned based nearest-neighhor rule. There is an optional decoder that will be used in an autoencoder which will get its inputs from the embedding space and reconstruct the original input. Then, special layer on top of the encoder. The value n is a hyperparameter. The larger the n, the more detailed and specific explanations will become the expense of more computational cost. Finally, we have normal fully connected neural network layer that gets the output of the prototype layer and outputs the class likelihoods. This output layer can have softmax activation function.
have prototypes which will be modeled
The special prototype layer in our method gets the transformed samples from the embedding space as input and outputs vector for each sample denoting the distance between that sample and each prototype in the embedding space. This arrangement was first proposed by Li et al. (2018) and lets position the prototypes during the training process of the neural network itself. a schema our network architecture is illustrated in Figure
Encoder/Backbone Network
Prototype Layer
Fully Connected Layer
Embedded input
Distance prototypes
Input data
Figure 1: A schema of our network architecture
2.1 TRAINING PROCEDURE
The training happens in two steps: The first step is to train the embedding space so that a good embedding space is formed at the output of the encoder. This done by using the special MsDNN loss (Chauhan et al.

---

Published conference paper at ICLR 2022
2021) on the embedding space. MsDNN loss is a variation of triplet loss WWeinberger & Saul 2009) that uses Gaussian estimations of the overall positive and negative samples substitute of the positive and negative samples themselves. It has been shown to be effective in preserving the unseen subclasses of the data and consequently is good pick for our purpose. Optionally, decoder that gets the transformed embeddings inputs and reconstructs the original samples can also be used this stage of the training, similar to MsDNN- AE (Chauhan et al. 2021).
First stage of training
Second stage training
Train the backbone network using MsDNN loss
Move the prototypes to their nearest sample
Optional: Fine tune the output layer
No
Satistied?
Satisfied?
Yes
No
Freeze the backbone network's weights
Train the network end-to- end using CEL, ft,
Figure 2: A schema of the training procedures for DEPN
Training stops when accuracy using nearest-neighhor classification validation set is maximized. Our experiments show that unseen subclass accuracy, when measured by nearest-neighbor classification accuracy, generally follows the coarse- coarse-grained classification. This lets us optimize embedding space using only the coass-grriindd class data and still get within the general vicinity of the best settings for fine- fine-grained subclass accuracy in the embedding space without having any subclass labels.
The choice of hyperparameter a in MsDNN is important to the viability of the created embedding space. This hyperparameters determines the size of the effective area for weighting the samples. Higher values would result in further samples being considered close neighbors for creating the positive and negative data point for MsDNN's contrastive loss. We found that starting from small values and doubling the value of until the peak of coarse-grained validation accuracy to be good procedure. Extremely large values of a encourage subclasses to merge. We found out that fine ane-grained and coarse- coarse-grained accuracy follow the same pattern with respect to the value of a. This means that coarse-rrained validation accuracy is generally good indicator of fine-grained accuracy as well.
The second step of the training procedure trains the whole network in an end-to-end manner for classification but with the weights of the encoder network frozen. In essence, what this stage does is to train the prototype and the output layers of the network. The input samples are fed to the encoder and the output of the output layer is used for the final classification. The loss function used in this stage can be seen in equation I
L A,CFL(( + Aeri (e,p(e + A3r2(e,p)
Where L is the loss value, CEL is the cross-entropy loss, ÿ represents the true coarse-grained labels of the input samples, y is the predicted output of the network, rı and r2 are special losses defined on the prototype layer, represents the transformed training samples in the embedding space, p represents the of learned prototypes in the embedding space, and λι, X2, Aa E IR+ are weights of each individual loss function. rı and r2 are defined as:
Σ min (llp - eell)) =Pp p| yn Vi, 1ppk exll2 = -minn mmll2) Cg
(2)
PsEPe
T2- = Σ (1pp - e,l13)
(3)
EfEe
P.Ep

---

Published conference paper at ICLR 2022
Table 1: Results of experiments on MNIST and FashionMNIST datasets.
MNIST
Methods
Coarse
Fine
C-NN
F-NN
PDL
98.39% % +0.51
33.82%
+1.38%
98.59%
+0.1 11%
88.45%
=0.54%
DEPN-A
97.81%
#0.95%
88.36%
#1.13%
98.74%
+0.07 %
96.65% #0.31 %
DEPN
92.79%
+0.99%
83.64%
+1.52%
98.53%
+0.09%
94.89%
+0.42%
DEPN-I
79.8%
+0.57%
76.13%
+1.89%
97.94%
+0.00%
96.63% +0.00%
Fashion MNIST Fine 41.53%
Methods
Coarse
C-NN
F-NN
PDL
94.03%
+2.71%
92.74%
#0.09%
69.75% =0.57%
DEPN-A
92.38%
+0.51%
67.14%
#1.43%
92.68%
#0.09%
82.02%
+0.32%
DEPN
92.01% #0.35%
57.83%
#1.57%
92.79%
#0.12%
78.57%
+0.23%
DEPN-I
86.11% +0.36%
59.68% +1.22%
91.86%
+0.00%
81.48% +0.00%
Where e; is an element in e with index i, Pe; is the set of all prototypes that have the same class label es (determined by the the label of the closest sample in the current batch to that prototype) and P5 is an element of Pe.- 21 is loss function that sums up the distance between each input sample in the current batch and its nearest same class prototype. The class label of a prototype in this case is the class label of its nearest sample in the current batch. On the other hand, r2 sums up the distance between each prototype and its closest input sample in the current batch. Minimizing 72 will make sure that each prototype is close to at least one input sample, Minimizing 71 on the other hand makes sure that each sample is close to at least one prototype of the same class. Minimizing these two losses combined makes sure that the prototypes are well-positioned inside the distribution of the data. To increase the speed of the process, the initial position of the prototypes will be chosen the position of a number of randomly selected training samples.
Minimizing the overall loss function will position the prototypes in key positions of the data distribution and will train the output layer to the distance of samples each prototype to classify them. It is important to note that the freezing of the weights of the encoder ensures that these loss functions do not determine the embedding space itself and only use it to classify the samples using the prototypes. We found that not freezing the encoder will result in the destruction of the subclass neighborhoods in the embedding space.
The stopping criteria in this stage of training are the plateauing of the loss function and the validation accu- racy. In our experience, the latter happens sooner than the former. At this stage, the prototypes should be manually moved to the nearest sample the training set. This sample is called the prototype sample and its class label is used as the class label of that prototype. At this point, the network is ready for inference. An optional procedure after this is to fine-tune the output layer using only cross-entropy loss due to the men- tioned moving of the prototypes, but saw noticeable change in the output of the network even without this fine-tuning. A schema of the training procedures can be found in Figure 2.1
2.2 INFERENCE AND EXPLANATIONS
The inference phase of DEPN is relatively simple. First, the data points fed to the network and are classified using the output layer. Then, the closest prototype to the embedding of that data point that shares the same class label the one predicted by the network is selected. The prototype sample of that prototype is then offered as an explanation to the end-user.
3 EXPERIMENTS
To assess the validity of our method, we performed a series of experiments. Our first experiments were done on the MNIST (Deng 2012) and FashionMNIST (iiao et al., 2017) datasets. To evaluate the ability
5

---

Published conference paper at ICLR 2022
of the networks to deal with unlabeled subclasses, we combined the first 5 classes of these datasets into one superclass. The same was done for the last 5 classes. This created a 2-way classification problem where also have subclass labels to be used for evaluation purposes (not training). We compare our work with the one by[Li [i et al. (2118) which is the state of the art in prototype-basee explainable networks and from now on will be referred to as PDL. (Prototype Deep Learning). In all experiments, the number of prototypes was 30. They were trained on 90% of the training set and validated the remaining 10%. Adam optimizer (Kingma & Ba 2014) was used in all instances. The results mentioned here are from evaluating on the test set. The results contain the coarse-grained (superelass) network accuracy indicated as Coarse, fine-grained (real classes) network accuracy by using the tine-graieed label of the closest same-class prototype as the prediction of the network. It is indicated as Fine. We also calculated both coarse and fine- -griigd nearest-neighhor accuracy in the embedding spaces of both methods (C-NN and F-NN respectively) as additional measures of how good each embedding space is. Note that F-NN represents a classic nearest-neighbor classification result while Fine represents a nearest-prototype classification accuracy. All experiments were repeated 8 times and their results were averaged.
PDL was trained for 50 epochs on backbone network that consisted of 4 convolutional layers. All layers except the last one had 32 feature maps. The last layer had 10 feature maps instead. The activation function for all of the backbone layers was ReLU. The decoder network the mirror image of the encoder, using deconvolution layers instead. The weight for cross-entropy loss was set to 20 and the weights of MSE in the auto-encoder, r1 and 12 were set during training.
DEPN was trained for 50 epochs on the same backhone network at the first stage and then for another 30 epochs the second stage. Experiments were done using both MsDNN and MsDNN-AE (DEPN and DEPN- A respectively). When MsDNN-AE was used, the decoder was also the same as the previous experiments. Best a for MsDNN-AE was found to be O. 128 and the weights of the second stage of training were 10 for cross-entropy loss and 11 and 1 for r2. An experiment was also done in which MsDNN was not used at all and the prototypes were instead placed in the input space itself with no backbone network (DEPN-I). Only the second stage of training was performed in this experiment. This was done as an ablation study on the use of MsDNN itself. The results for these experiments can be seen in Table
Another set of experiments were done on the CIFAR-10 10 dataset. Similar to MNIST, we created two super- classes, one containing planes, cars, cats, birds, and deer subclasses and another one containing dogs, frogs, horses, ships, and trucks. For this experiment, we used pre-trained Resnet-18 18 (He et al. 2016) network as our backbone. As Resnet-18 18 uses input sizes of 224x244 pixels while CIFAR-10 images are only 32x32, scaled the inputs to x24x224 using linear interpolation method. The number of distinct dimensions in our input data was 32x32x wanted our embedding space to be smaller as force the network compress the image data even more, so we added a new fully-connected layer with 120 neurons to the end of the resnet network. This layer had LeakyReLU activation with a 0.2 scaling factor. The decoder used in this configuration had 6 initial de- convolutional layers with 64 feature maps and a LeakyReLU activation function with a 0.2 scaling factor. These layers fed into a final layer with feature maps that represented the RGB values of the original image, recreating the input at its output. All of these layers had a kernel size of 4 and a stride of 2. All of them except the third layer had a padding of 1. The third layer used padding of 2. This configuration made sure that our output size matched the 224x224 pixel image that was used as input. All of these experiments used a prototype count of 40.
and the output of the resnet- 18 has 2x2x 128=512 dimensions. We
For PDI., we used weight distribution of 20 for cross-entropy loss and 1 for all of the remaining loss functions. This is similar to the original values used in Li et al. (2018). The network was trained for 150 epochs and evaluated the same way as the previous experiments. For DEPN, the best value for a was found to be 4 and the weights of the loss functions were set as 10 for both cross-entropy loss and ra and 1 for r2. The reason r2 had a lower weight was because the batch-size used was 200 and this would adversely affect r2 itself. More explanations on T T2, and the value of a are provided in the appendix. The network trained for the first stage for 130 epochs and 50 for the second stage. These values ensured that all of validation losses in all of the experiments plateau long enough for us to be sure about the fact that the training is done.
6

---

Published conference paper at ICLR 2022
Table 2: Results of experiments on CIFAR-10.
Methods
Coarse
Fine
C-NN
F-NN
PDL
91.05%
+0.36%
19.50%
#1.14%
91.88%
+0.22%
40.11%
+0.68%
DEPN-A
91.12%
+0.76%
58.29%
+2.59%
92.45%
+0.65% %
74.70%
#0.21% %
DEPN
90.50%
=0.41%
56.88%
=1.54%
92.00%
+0.36%
72.01%
+1.34%
DEPN-I
59.41%
=0.24%
36.38%
+3.60%
80.27%
+0.00%
70.07%
+0.00%
Table 3: Results of experiments on ImageNet.
Methods
Coarse
Fine
C-NN
F-NN
PDL
96.61% #0.22%
33.37% #1 =1.46%
96.28%
#0.31%
42.81%
11.18%
DEPN-A
97.02% #0.24%
54.17%
#3.64%
97.14%
+0.34%
80.68%
+0.63%
DEPN
96.19%
=0.10%
60.45%
#7.90%
97.00%
+0.47%
82.63% +1.72%
DEPN-I
95.28% +0.31%
61.31 % +4.45%
95.66%
+0.00%
85.75% #0.00%
The evaluation scheme was the same as the previous experiments. The only exception was that in DEPN-I, the prototypes were placed in the Resnet-18 18 embedding space (and not in the space of the additional fully connected layer we added to the network). This was because Resnet's embedding space is pre-trained and could be used to determine how much the performance was due to Resnet itself. The results can be seen in Table
The last set of experiments was done on a subset of the ImageNet dataset (Deng et al. 2009). The previous experiments combined unrelated classes of existing datasets into superclasses. With ImageNet, we have hierarchy of classes and we can combine a number of related classes together. This can lead to a more reasonable experimental setup. This experiment was up canine feline classification problem with each class consisting of a number of subclasses. These subclasses were "foxes", "wolves", "collies", and "swiss mountain dogs" (sennenhunde) for the canine superclass and "domestic cats", "wild cats" and "big cats" for the feline superclass. We cropped the regions consisting of these classes and split the data when there was more than one animal in the picture. The details of the dataset can be found in the appendix.
We used very similar networks as the ones in the experiment with the CIFAR-10 dataset. We still had to resize the data into 224 pixel images because the dataset did not contain images of uniform size. The only difference with the networks used in the CIFAR-10 dataset was that we did not add the fully connected layer to the end of resnet. This is because in this case, even the smallest image in the dataset was large enough that compressing it into 512-dimensional space could be considered a good compression. We found that the same set of hyperparameters as the ones in CIFAR- 10 works the best in this experiment too. The only difference
that the first stage of DEPN training was done in only 10 epochs instead of the previous 130. This is because resnet-18 is trained on ImageNet itself and already works very well on this dataset. The results of these experiments can be seen in Table 3
4 DISCUSSION
The results from MNIST and FashionMNIST show that DEPN, in comparison to PDL, achieves comparable accuracy for classification of the superclasses while achieving significantly better accuracy for fine-grained nearest prototype labels (Fine). In this particular example, embedded spaces created by MsDNN-AE outper- form the ones by plain MsDNN. Also, comparisons with not using MsDNN and only applying the second stage of training (prototype training) show that M&DNN is responsible for a significant portion of the perfor- mance in both coarse and fine- fine-graine -eeiigr accuracy. It also shows that PDL degrades the subclass neighborhoods as shown by the fine- fine-graine grained nearest neighbor accuracy (F-NN) and especially fine mee-grained prototype label accuracy (Fine). Note that fine- finennrained nearest neighbor accuracy can be seen as some form of soft upper

---

Published conference paper at ICLR 2022
bound for fine-grie greingraied accuracy in general (which can be achieved by having as many prototypes as training samples, turnngg the model into nearest-neighbor model).
The results for CIFAR-10 10 continue to show a large improvement in the fine-grained performance of DEPN compared to PDL. One thing note is that the decoder of PDL in this experiment was extremely blurry, only showing a very vague shape of the original input image and performing even worse for the prototypes themselves. We used the closest sample to the prototype a proxy of the prototype itself.
The results for the ImageNet dataset are interesting because the Resnet embedding space is trained on Im- ageNet itself. This means that the embedding space starts very well separated in terms of subclasses. We found that in this case, using MsDNN-AE will actually slightly degrade the embedding space because the decoder is not pre-trained and the backpropagated loss of the decoder will be detrimental to the fine-grained neighborhoods of the embedding space. But plain MsDNN loss will start the first stage already near the local minimum, so it will not perform any drastic change the embedding space and will keep largely intact. Our observation of the training procedure aligned with these theories. Also, as the embedding space itself was already well separated, not using MsDNN at all yielded similar results to the plain MsDNN (no autoencoder). PDL, like before, was detrimental to the fine-grained class neighborhoods of the embedding space.
In conclusion, we have offered DEPN, an interpretable prototype-based neural network that achieves good accuracy and offers demonstrably better explanations compared to the state of the art. It works so by offering the prototype that is most responsible for the decision the network as an explanation. As the prototype and its associated input were selected in nearest-neighhor- -iigho--rreenly embedding space, the offered explanation is likely to be similar to the sample being classified as opposed to just being from the same class.
We have demonstrated the validity of our method by performing number of experiments in which used datasets with coarse-gras gaasse-rraineddd and fine- tme-ggrined class labels to assess the similarity of the offered explanation to the input sample. This has let achieve compared to the state-of-the-arr We believe this work has also shown that, when developing an interpretable method, we should mind the quality of offered explanations especially in where direct information is limited.
average of 125% improvement
fine- tineggranedd accuracy
5 ACKNOWLEDGEMENTS
This research was enabled in part by support provided by Compute Ontario (www. wwwputoontattiiioooooooo ca). Compute Canada (www. wowputccandaa ca) and Natural Sciences and Engineering Research Council of Canada (www mussrrc-rssng ge.ca..
REFERENCES
James Bezdek and Patrick F Castelaz. Prototype classification and feature selection with fuzzy sets. IEEE Transactions on Systems, Man, and Cybernetics, 7(2):87-92, 1977.
Jacob Bien and Robert Tibshirani. Prototype selection for interpretable classification. The Annals of Applied Statistics, 5(4):2403-2424, 2011.
Abhijeet Chauhan, Omid Davoudi, and Majid Komeili. Multi-scale deep nearest neighbors. In 2021 Interna- tional Joint Conference Neural Networks (IJCN), pp. 1-8. IEEF, 2021.
Chaofan Chen, Oscar Li, Chaofan Tao, Alina Jade Barnett, Jonathan Su, and Cynthia Rudin. This looks like that: deep learning for interpretable image recognition. arXiv preprint arXiv: 10574, 2018.
Jia Deng, Wei Dong, Richard Socher. Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, Iece, 2009.

---

Published conference paper ICLR 2022
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): (966):141142, 2012.
Finale Deshi-Velez and Been Kim. Towards a rigorous science of interpretable machine learning, arXiv preprint arXiv:1702.08000 2017.
Arnulf BA Graf, Olivier Bousquet, Gunnar Rätsch, and Bernhard Schölkopf. Prototype classification: In- sights from machine learning. Neural computation, 21(1):272-300, 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Been Kim, Cynthia Rudin, and Julie A Shah. The bayesian case model: generative approach for case- based reasoning and prototype classification. In Advances in neural information processing systems, pp. 1952-1960, 2014.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 1rXiv:1412.69800 2014.
arXiv preprint
Teuvo Kohonen. Improved versions of learning vector quantization. In 1990 ijenn international joint confer- ence on Neural networks, pp. 545-550. IEEE, 1990.
Ludmila I Kuncheva and James C Bezdek. Nearest prototype classification: Clustering, genetic algorithms, or random search? IEEE Transactions on Systems, Man, and Cybernetcss, Part C (Applications and Reviews), 28(1):160-164 1998.
Oscar Li, Hao Liu, Chaofan Chen, and Cynthia Rudin. Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. In Proceedings of the 31st international conference on neural information processing systems, pp. 1768-777, 2017.
Nicolas Papernot and Patrick McDaniel. Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint 1.33::1803307666 2018.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin." why should trust you?" explaining the predic- tions any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 135-1114, 2016.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use inter- pretable models instead. Nature Machine Intelligence, 1(5):206-215 2019.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017.
Sambu Sco, Mathias Bode, and Klaus Obermayer. Soft nearest prototype classification. IEEE Transactions on Neural Networks, 14(2):390-398, 2003.
Kilian Q. Weinberger and Lawrence K. Saul. Distance metric learning for large margin nearest neighbor classification. ournal of Machine Learning Research 10, no. 25, 2009.
Han Xiao, Kashif Rasul, and Roland Vollgraf. mashion-mnise novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: I 1704.77747 2017.

---

Published conference paper ICLR 2022
A APPENDIX
A.I DETAILS OF THE IMAGENET DATASET
We used used 7 subclasses and 2 superclasses in our curated dataset. ImageNet samples might contain multiple objects. These objects have boundaries which used to crop and split them if necessary.
Each of our subclasses consisted of smaller subclasses. The actual ImageNet labels for those were:
Canines:
1. Foxes: 2315 total in02119789 'n02119022', 'n02120505', 'n02120079'
2. Wolves: 2199 total 'n021 14712', "10112,,'2211888111" 'n02114855', 'n02114548', 'n021 143677
3. Collies: 2258 total 'n02106030", 'n02106166', 'n02105855"
4. Swiss mountain dogs: 2251 total 'n02108000", 'n02107683', 'n02107574", 'n02107908'
Felines:
1. Big Cats: 3542 total 'n02128925', 'n02129604', 'n02128385', 'n02128757', 'n02129165', "n02130308'
2. Domestic Cats: 2906 total - 'n02124075', 'n02123394', 'n02123159', 'n02123597', 'n02123045'
Wildcats: 1108 total "n2112311'', 'n02127052'
We used the validation set ImageNet to create the test set for this experiment. The validation set of this experiment 10% random subset of the training set.
A.2 SELECTING THE BEST
To select the best we started from small amount and doubled the value each time until we hit the best possible coarse-grained nearest-neighbor validation result. (g2sre/A.[|hhows the results of those experiments. We chose based on the best coarse-grained nearest-neighbor accuracy but fine-grained results rose and fell generally in line with those.
Experements
Coarse grained network accuracy
Hise indd necerck acourocy
Figure 3: Coarse and fine grained network classification accuracy for different values of CIFAR-10.
10

---

Published conference paper ICLR 2022
Hearso nalptto accense of undeuling dinggiceeaaiiii
19d glanec acouuty
Doanco modiinoa wwt.egooooeooooooo...oooo acueracy
Figure 4: Coarse and fine grained nearest neighbor classification validation accuracy during the first stage of training on CIFAR-10.
A.3 STOPPING CRITERIA FOR MsDNN AND FINE-GRAINED ACCURACY TRENDS
We stopped training the first stage when the coarse- graiined classification accuracy of the network plateaued. Our data shows that fine -en-iir accuracy followed the same trends as coarse coarse-grained accuracy during the training. Figure A.3 shows one of the training results on CIFAR-10.
A.4 VARIETY OF THE PROTOTYPES
We found that our method able to find varied prototypes. Figure A.4 shows an example of them on the ImageNet dataset. Note that the method able to find prototypes that not only from the 7 subclasses that we created but also the smaller subclasses that were merged to create them. For example, you can see different types of "big cats" here, including tigers, lions, panthers, etc. An interesting example is that there are two prototypes for lions. One for male and one for female (a distinction that does not exist even in the original ImageNet).
A.5 SECOND STAGE OF TRAINING
In the second stage of DEPN training, the weights of each individual loss function can have important effects on the final distribution the prototypes. We found that the weight of the cross-entropy loss should be about the same the weight of v1. If it is too low, the coarse-grained accuracy of the model might suffer. If it is too high, it will prevent the other loss functions to effectively spread the prototypes.
We found to be more important than r2. If the weight of r1 is too low, prototype diversity and result, fine-grained network accuracy suffers. 72 on the other hand, should probably have lower weights than the others. In ideal situation, it should force the prototypes basically sample. But our training done batches, and while the distance between a prototype and its nearest sample might be 0 in one batch, the same prototype might be even close any sample in another. We found that this dependency on batch can be somewhat mitigated by using a larger batch size, but unless the whole dataset each batch, this problem remains. We found that if the batch size is too large, the prototypes will be pushed to the densest areas of data distribution. That makes sense as those areas are the ones more likely be represented by at least one sample each batch. This a bad effect on
the location of their nearest
small the weight of
11

---

Published conference paper ICLR 2022
200
400
600
800
1000
250
500
1000
1250
1500
1750
Figure 5: The 40 prototype samples for one of our ImageNet experiments.
prototype diversity, making many prototype samples to be identical. r2 should not too low though, as that could let the prototypes move outside the distribution if the data distribution is not convex region.
A.6 NUMBER OF PROTOTYPES
There are some important aspects to keep in mind for choosing the number of prototypes. the number is small, the network will suffer in terms of expressibility and the nearest prototypes will be too far for some samples. If it is too large, it might make it hard for human user to take all of them in mind if they want to ex- plore all of the distances these prototypes (potential loss of a global view interpretability). If the number is absurdly large (in the scale of thousands), we might encounter memory and computational problems. The general trend, however, is that the higher the number of prototypes, the closer the performance of the model will get to nearest neighbor classification. Some examples of experiments with different prototype counts (each are the average of experiments with MsDNN's s sigma=2. Note that for CIFAR- 10, 40 prototypes were used in the experiments mentioned in the paper) can be for fine- line-grained accuracy as the number of prototypes increases. Note that coarse- coarse-grained network accuracy is still quite similar for all of the experiments.
Table 4 These show general upward trend
12

---

Published conference paper ICLR 2022
Table 4: Results of experiments on different
number of prototypes for CIFAR-10.
Number of prototypes
Coarse
Fine
5
91.50%
31.02%
30
91.14%
54.85%
40
91.12%
58.29%
50
91.65%
61.00%
100
91.83%
64.16%
13


Reviews:
[{"review_id": "qy5nsIUqTDv", "reviewer": "Reviewer_NPUz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am not expert in deep learning, but I know that prototype method was very\npopular in statistical learning. Many commonly used algorithms, such as KNN and\nK-means, are exploiting this idea.\n\nThe proposed method adapts the idea of prototype-based classification to deep\nneural networks, and uses the automatically extracted prototypes to increase the\nexplainability of neural nets. The proposed algorithm seems work well on MNIST\nand ImageNet benchmarks.\n\nMy main concern is the novelty of this work, and its lack of comparison to\nprevious work in similar direction. For example, the DkNN method mentioned in\nrelated works persues a very similar idea like this work, so I think the authors\nshould compare this work to it. Moreover, the main contribution of this work is\nit extends MsDNN with a prototype layer. Again, I'm not familiar with this area,\nso I'm not sure whether this improvement is significant or just incremental.\n\nOther than the above problem, I wonder how difficult it is to apply the proposed\nnetwork on real problems. The authors have state that it should be applied on\nclassification problems that each class consists of many subclasses. In order\nto show this idea, the authors manually create superclasses in MNIST and\nImageNet dataset. I understand that using this method can verify if the neural\nnet preserves the subclass structure in its embedding layer. Nevertheless, in\nreal problem we usually do not have such type of information, so I wonder how\nwill the proposed method perform on the original MNIST and ImageNet tasks\ncomparing to more related works.", "summary_of_the_paper": "This paper presents a method to learn neural nets that preserves the subclass\nsimilarity in the embedding space. The proposed method adds a prototype layer,\nwhich stores the representative prototypes of some subclasses, then a fully\nconnected MLP is used to output the class label based on examples' distance to\nthe prototypes.", "summary_of_the_review": "The novelty of this work could be limited, and the experiments seem not enough\nfor validating the effectiveness of the proposed approach, so I recommend to reject.\n=======================\nAfter reading other reviews and the authors' clarification, I have increased my rating.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "f5hE7hxeEu", "reviewer": "Reviewer_MCMJ", "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": "The paper addresses an interesting problems which is interpretability of the classification methods that can have various use cases and can demystify the neural net black box for technical and non-technical individuals. It is written well and is easy to follow. The method is positioned well in the existing body of works and the contributions of the work is clear. Experimental settings and results are throughly and very well discussed which makes the work repeatable. Authors have also done a good job discussing the experimental results and sharing the interesting observations.\n\nA couple of recommendations:\n- One of the main contributions of the paper that should get credit for it's superior fine-grained performance is the loss function introduced in equation 1. However, it's not clear to what extent r1 and r2 are contributing to the overall performance of the method and which one is more important. From the explanations at page 6, it looks like that the weight of the cross entropy component of the loss function is significantly higher than r1 and r2 weights which alludes to the fact that r1/2 play a less significant role in the method. It would have been good if the authors could have added one or more ablated versions to the experiments to check this.\n- Based on the experimental results, C-NN and F-NN mostly outperform Coarse and Fine which makes the reader wonder if instead of classification nearest neighbor search in the embedding space should have been suggested. If the concern is computational costs, it would have been interesting to see the performance of C-NN and F-NN by using approximate nearest neighbor search (e.g. using LSH or k-d trees).\n\n- Minor comments:\n-- P3: \"Training stops when accuracy using nearest-neighbor classification on a validation set is minimized\"\nIf I understand correctly, training stops when classification error is minimized not the accuracy. Please check.\n-- Some hyper parameters seem to be set arbitrarily (e.g. # prototypes = 30) and it's not clear how assigning a different value could have affected the accuracy of the proposed method or how authors have come up with the used values.", "summary_of_the_paper": "The paper introduces a novel an interpretable neural network for classification tasks that works by assigning input cases to prototypical cases based on their euclidean distance in an embedding space learned by the network. This is achieved by minimizing a loss function consisting of three components: cross entropy loss; distance between each case and the prototype with the same class, distance between each prototype and the closest case to it. The proposed method is specially useful when classification at fine-grained level is performed where in addition to the class to which an instance belongs, predicting the subclass is desirable as well. Experimental results are provided in the paper that validates the merits of the method compared to a set of variations of the proposed method and a state of the art approach as well.", "summary_of_the_review": "Overall an interesting read and a well written paper. My recommendation is to accept the paper.", "strength_and_weaknesses": "", "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": "0VGIiXlt_o", "reviewer": "Reviewer_s8S9", "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": "The paper's main strengths are:\n* The combination of nearest-neighbor learning and prototype learning is very natural and appears to work well, empirically. The combination is also well-motivated from a pretty comprehensive literature review. I particularly appreciate the acknowledgment of early prototype work (e.g. Kohonen) which is typically omitted in the recent literature.\n* A particularly nice result is that a learned model can also be used as a one-nearest prototype classifier for finer-grained subclasses of the actual classes it was trained on. In other words: the proposed approach learns hierarchical structure that was not explicitly provided in the training labels. As far as I know, this result is a novelty in the literature and motivates the use of prototype/nearest neighbor approaches.\n* The paper provides reasonable ablation studies and close baselines, which enables the reader to tease apart the effect of most architectural choices. Similarly, the discussion of results is detailed and illuminating.\n* I found the paper easy to follow and clear, with each claim being justified both conceptually as well as empirically.\n\nThe paper's main weaknesses are:\n* It seems to me that the architecture of the last 2 layers is needlessly complicated. While this architecture is in Line with Li et al. (2018), a more common option (starting from Kohonen, 1995) is to assign a fixed label to each prototype and classifying data by assigning the label of the closest prototype (as the paper does for the fine-grained classification). Typical loss functions include the GLVQ loss from [Sato and Yamada (1995)](https://proceedings.neurips.cc/paper/1113-generalized-learning-vector-quantization.pdf) or variants of the [LMNN loss (2009)](https://www.jmlr.org/papers/volume10/weinberger09a/weinberger09a.pdf). Such an architecture would also be more in line with MsDNN.\nInstead, the present paper selects a pseudo-label for each prototype based on the closest data point and proposes new loss components. Why is that? Does it perform better? If so, I would appreciate another ablation baseline that drops the final, fully connected layer and, instead, uses only the distances to the prototypes for classification. \n* While the combination of MsDNN and prototype learning is very natural and makes a lot of sense, intuitively, it would have been nice to see a more formal, theoretical justification why this combination improves performance.\n* The experimental evaluation includes very reasonable baselines. However, more baselines would have been possible, taking more recent work into account, such as Chen et al. (2019) or [Hase et al. (2019)](https://ojs.aaai.org/index.php/HCOMP/article/view/5265).\n* The experimental hyper-parameter settings on page 6 appear ad hoc and are not justified.\n\nOverall, my impression is that the paper is not quite ready, yet. I believe that more experiments and theoretical analysis are needed to fully develop the proposed idea. I do appreciate the core idea, though, and believe that a future iteration of the paper may well be a good contribution to the field.\n\nBeyond the major points mentioned above, there are a few minor recommendations:\n\n* on page 4, the meaning of the hyperparameter $\\sigma$ should be quickly explained.\n* Please provide standard deviation (or another measure of variance) in Tables 1-3.", "summary_of_the_paper": "The paper proposes a novel combination of prototype learning and deep nearest neighbor learning in order to achieve an embedding of the input data that is more friendly for prototype learning while maintaining the computational efficiency and intepretability of a prototype approach. In more detail, the approach first trains a Multi-scale deep nearest neighbor network to embed the input data. Then, it jointly learns a prototype layer and a fully connected layer which outputs class logits based on distances to prototypes. Finally, the learned prototypes are replaced by the closest sample from the actual training data to enhance interpretability. In experiments on MNIST, FashionMNIST, CIFAR-10, and ImageNet, the paper shows that the proposed approach outperforms state-of-the-art prototype learning.", "summary_of_the_review": "Overall, my impression is that the paper is not quite ready, yet. I believe that more experiments and theoretical analysis are needed to fully develop the proposed idea. I do appreciate the core idea, though, and believe that a future iteration of the paper may well be a good contribution to the field.\n\n/edit The authors have resolved the most crucial points in their response. Provided that these crucial arguments are amended to the paper, I believe that it can be published.", "strength_and_weaknesses": "", "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": "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": {}}]

Author rebuttal:

Meta-review: The authors propose a neural network model to preserve the sub-class similarity. The key of the model is to add a prototype layer to a multi-scale deep nearest neighbor network. The prototype layer stores the representative prototypes of some fine-grained sub-classes. The use of the prototype layer preserves intepretability and computational efficiency. Experimental results demonstrate that the proposed approach reaches state-of-the-art prototype learning performance.

The reviewers generally find the paper clear and with sufficient contributions. The empirical validation is sufficiently thorough to back the claims in the paper. The main concern prior to the rebuttal among some of the reviewers was about the novelty of the paper (e.g. with respect to DkNN), but the authors convinced most of the reviewers in the rebuttal about the key differences. The authors are encouraged to highlight the novelty aspect more clearly in the revision. Another suggestion was to add an ablation study to justify the importance of the r1/r2 parameters, and the authors have done a successful job addressing the suggestion. Several other comments, such as explanations of the hyperparameters, have been taken into account in the revision. The reviewers thus reach the consensus to recommend acceptance.
Decision: Accept (Poster)