Birds of a Feather Trust Together: Knowing When to Trust a Classifier via Adaptive Neighborhood Aggregation
Authors: Miao Xiong
Shen Li
Wenjie Feng
Ailin Deng
Jihai Zhang
Bryan Hooi
Venue: Accepted by TMLR ()

Abstract: How do we know when the predictions made by a classifier can be trusted? This is a fundamental problem that also has immense practical applicability, especially in safety-critical areas such as medicine and autonomous driving. The de facto approach of using the classifier's softmax outputs as a proxy for trustworthiness suffers from the over-confidence issue; while the most recent works incur problems such as additional retraining cost and accuracy versus trustworthiness trade-off. In this work, we argue that the trustworthiness of a classifier's prediction for a sample is highly associated with two factors: the sample's neighborhood information and the classifier's output. To combine the best of both worlds, we design a model-agnostic post-hoc approach NeighborAGG to leverage the two essential information via an adaptive neighborhood aggregation. Theoretically, we show that NeighborAGG is a generalized version of a one-hop graph convolutional network, inheriting the powerful modeling ability to capture the varying similarity between samples within each class. We also extend our approach to the closely related task of mislabel detection and provide a theoretical coverage guarantee to bound the false negative. Empirically, extensive experiments on image and tabular benchmarks verify our theory and suggest that NeighborAGG outperforms other methods, achieving state-of-the-art trustworthiness performance.

Published in Transactions on Machine Learning Research (08/2022)
Birds of a Feather Trust Together: Knowing When to Trust a Classifier via Adaptive Neighborhood Aggregation
Miao Xiong', Shen Li", Wenjie Feng', Ailin Deng?, Jihai Zhang?, Bryan Hooi
(miao.riong shen. fu. edu, fengie.enn@@nus.c sea.gguuus.euuggg...... ailin nus. edu, {jihai, desbhk) kesbhkk-@comp..... @comp. nus. edu.sg Institute of Data Science, National University of Singapore
Deportment of Computer Science, National University of Singapore
Reviewed on OpenReview: https: openreview. net/ forum? id- p5V8P2J61u
Abstract
How do we know when the predictions made by classifier be trusted? This is fundamental problem that also has immense practical applicability, especially in safety-critical arcas such medicine and autonomous driving. The de facto approach of using the classifier's s softmax outputs as a proxy for trustworthiness suffers from the over-confidence issue; while the most recent works incur problems such as additional retraining cost and accuracy versus trustworthiness tradc-off. In this work, we argue that the trustworthiness of a classificr's prediction for a sample is highly associated with two factors: the sample's neighborhood information and the classifier's output. To combine the best of both worlds, design model-agnostic post-hoc approach NEIGHBORAGG to leverage the two essential information via an adaptive neighborhood aggregation. Theoretically, we show that NEIGHBORAGG is a generalized version of a one-hop graph convolutional network, inheriting the powerful modeling ability to capture the varying similarity between samples within each class. We also extend our approach to the closely related task of mislabel detection and provide a theoretical coverage guarantee to bound the false negative. Empirically, extensive experiments on image and tabular benchmarks verify theory and suggest. that NEIGHBORAGE outperforms other methods, achieving state-of-tho-ae tho-art trustworthiness performance.
1 Introduction
In recent years, interactions with Al systems have become increasingly pervasive in all walks of our daily lives. As machine learning models become more widely involved in our decision- beeision-making processes, the robustness and trustworthiness of their docisions need to be carefully scrutinized (Varshney Alemzadeh] (017]. This is of vital importance in many scenarios, especially in safety-critical areas, such as medical applications, where successful deployment is highly dependent
model's ability to detect
incorrect prediction, that
humans can intervene when necessary Shi & Jain 2019 Chang et al. 2020 Li et al., 2021). This leads to our central question: how can we know when the predictions made by classifier can be trusted?
In this paper, we investigate the trustworthiness of the prediction given by a classifier, which serves as a measure for the classifier's quality rather than the data. Concretely, given some i.i.d data and an pretrained classifier (referred to as 'base classifier' hereinafter), the goal trustworthiness score, such that higher scores indicate belief that the classifier's predicted class is more likely to be correct. In this way, the users the prediction output by machine learning models, or they should resort to domain experts for manual predictions. In the literature, this task is also referred to as "trustworthiness prediction", "failure prediction", or "misclassification detection" (Jian et al. 2018 Corbière et al. 2019
devise a discriminative and accurate
easily determine whether they should trust
Quur code publicly available

---

Published in Transactions on Machine Learning Research (08/2022)
(a) Max Softmax Score
(b) Ours
(e) Max Softmax Score
(d) Ours
Shallow Clussifier
Deep Classifier
Figure Comparison between max softmax scores and NEIGHBORAGG scores (ours), based on shallow base classifier (left) and a deep base classifier (right), respectively. The color of the points indicates its ground truth label while the color of the background shows the corresponding trustworthiness score. The dotted black line demonstrates the decision boundary of the base classifier. (a): The points marked by circles 'A' and 'B' overstep the decision boundary, being misclassified while some of them still get high max soft scores. On the contrary, (b): our algorithm can correctly assign these points the lowest trustworthiness scores. (c): Max softmax scores from base classifiers are potentially over-confident near the decision boundary whereas (d): our proposod score resolves this issue in modcl-agnostic manner by inspecting their neighbors.
The most common approach is to employ a classifier's softmax output (i.e. the maximal value of a softmax vector, referred to as confidence score hereinafter) as the proxy for trustworthiness (Hendryeks & Gimpel 2017). However, this approach has been found be over-confident (Guo et al.] 2017). Figure | illustrates this issue over 2D toy datasets: the points marked by circles 'A' and 'B' in Figure D are misclassified with high confidence scores. In Figure D while all samples have been correctly classified, the base classifier assigns excessively high confidence scores almost all the data points, even those near the classification boundary, making the decision boundary (full of bends and curves) prone to noise. On the contrary, our method addresses these issues by utilizing information from the neighbors of each point rather than just the point itself, thereby giving much lower worthwort scores to those misclassified points (Figure 1p) and better reflecting the uncertainty points near the decision boundary (Figure
Other related works include uncertainty-avee aware methods and post-hoc methods, The uncertainty-aware methods such as MC-dropout (Gal & Ghahramani 2016), Deep Ensemble [Lakshminarayanaar et al. 2017) and Dirichlet-based approaches (Charpentier et al. (2200) typically involve retraining the classifier due to the modification of network architecture, and can incur trade-offs between classifier accuracy and the performance of trustworthiness prediction. In contrast, the posl-hoc setting avoids such extrr-costt by focusing on a pretrained classifier. Among these algorithms, Corbière et al. (2019h builds on strong assumption that the base classifier is always over-confident, which fails in many cases (Wang et al. 2021 Trust Score (Jiang et al.) 2018) leverages the neighborhood information by hand-designed and non-trainable function, suffering from limited functional space and modeling capacity.
80
ProbOnty NeighOrly Trust Score
APM
Landsat
Figure 2: Sources of infor- mation for trustworthiness prediction. Our adaptive approach outperforms other methods that only use the classifier's prediction (ProbOnly) or neighborhood information (NeighOnly), and Trust Score.
Inspired by the comdonly-held Hodges 1989), we argue that the trustworthiness of a classifier's prediction for given sample is highly associated with the sample's 'ss neighborhood information, such as their labels and distances to the point itself. That is, if sample's 's predicted label is consistent with the majority of its neighbors' labels, this prediction is more likely to be reliable; otherwisc, we tend to assign it lower trustworthine score. To capture the various correlation between the sample and its neighborhood in a more flexible manner, we devise an adaptive approach to learn the scoring function, thereby ensuring superior capacity than Trust Score (Jiang al. 2018). Figure verifies the advantage by showing that the adaptive function (NeighOnly and Ours) outperforms Trust Score.
hoaabborhood-hooophie assumption Fix
2

---

Published in Transactions on Machine Learning Research (08/2022)
Furthermore, we believe that the classifier's predictive output is also an indispensable source of information for the trustworthiness prediction, if not more so than the sample's neighborhood information, particularly in cases where the classifier is sufficiently reliable or the hawhhbbooooooohoooohhho perfectly mect. This is further borne out by Figure 2 where using the classifier output (ProbOnly and Ours) outperforms using only neighborhood information (NeighOnly and Trust Score) for the Adult dataset.
assumption does not
In this paper, we propose model-agnostic algorithm, termed as NEIGHBORAGG, for the trustworthiness prediction by leveraging the neighborhood information and the classifier output via adaptive scoring function that combines the best of both worlds. Theoretically, we demonstrate that our method is essentially generalized onc-hop graph convolutional network, and hence inherits the powerful modeling capacity to capture the varying similarity within each class, making it insensitive to hyperparameters for neighbor selection. Owing to the adaptive design, these two factors are able to act in a complementary manner when determining the trustworthiness score. Our method is also effective by achieving 7.63% gain on APM and 2% gain on AUC on average for the tabular dataset.
Additionally, we apply approach to the closely related task of detecting mislabeled data samples, and propose the NEiCHBORAcG-CMA algorithm for mislabel detection. Furthermore, we obtain a theoretical coverage guarantee for this algorithm to bound the probability of false negative predictions. To the best of our knowledge, the present work is the first to adapt to real-world noisy data setting and achieves a promising result, which we believe is of independent interest.
In summary, our main contributions are as follows:
We propose model-agnostic post-hoc algorithm NEIGHRORAGG to measure the trustworthiness of classifier's predictions. Moreover, by demonstrating the theoretical equivalence with generalized graph convolutional network, we provide better understanding into how our approach works.
which adapts our method to mislabel detection and provide a noise-robust coverage guarantec to bound the false negative probability.
We propose NEIGHBORAGG-CMA
Experiments on multiple labular and image datasets showcase that the proposed NEIGHBORAGG consistently outperforms other state-of-the-art methods by clear margins. Additionally, we show that NEIGHBORAGG-CMI is able to identify mislabelled samples with promising results.
2 Preliminaries and Notations
We aim to measure classifier's trustworthiness in the context of multi-class classification with C 2 2 categories. Given a set of N data points X' = (x(1), (...,,(()) x(N),, }, with (()) E IR and their corresponding labels y (,.")...., M() with y( C 1,... C C,, 1), let bold y( RC denote the one-hot encoding of ( The dataset is split into training, validation and test set, denoted by (Ker. Vor), (Neat, Veat), (Rss: Vis,, respectively. Formally, we define the base classifier as a mapping F X' RC which takes data point x input and outputs its predicted probability vector or logits p E RC and predicted class g. Unless otherwise stated, vectors and matrices are denoted by boldface lowercase and uppercase letters, respectively, and sets are denoted by calligraphic letters. All vectors are treated as column vectors throughout the paper.
Yoat))Voat),
Problem (Trustworthiness Prediction). Given base classifier F X RC, the trustworthiness prediction problem is to give trustworthiness score t(x) T(;; Ntr, Ver) E R. for any E X where T is the designed function for trustuorthiness prediction, with the goal that in perfect condition:
(xx) = { 0
-
y y v
y y= g.
3 Proposed Method
In this section, we first introduce the training and inference algorithms of our proposed NEIGHBORAGG, Then, we theoretically show that NEIGHBORAGG is a generalized version of a one-hop graph convolutional
2 Viot and {X.Y} are i.idd datasets.
3

---

Published in Transactions on Machine Learning Research (08/2022)
Class-wise
Neighborhood Feature
3
Aggregation
1.7
1.6
1.3
1.8
1.4
1.2
2.7 2.4
2.0
h
80
RR
0.1
Wp
0.3
0.3
0.4
16 RRC
p
Classifier
Base Classifier
F
Output Feature
Compute Trustworthiness Score
Construct Feature
Figure 3: A conceptual illustration of the proposed NEIGHBORAGG with == and C =. Given a sample x in question, we first compute two features: (1) class-wise neighborhood feature h = [Sy, $1, that reflects the similarity
K neighbors across every class, and (2) the base classifier's probability vector p. Then, after two linear transforms Wh, Wp followed by concatenation, (3) NEIGHBORAGG aggregates the information and outputs the final trustworthiness score corresponding to the base classifier's predieted class. Compared to the confidence score 0.4, our approach assigns more trustworthiness to the predicted class by increasing the score to 0.6.
network. Lastly, we show a promising extension of NEIGHBORAGG applied in mislabel detection with a theoretical coverage guarantee.
3.1 Algorithm
As stated in the introduction, one of our key observations is that the trustworthiness of the classifier's prediction for sample highly associated with two information sources: the neighborhood of the sample and the predictive output of the classifier. These two components interact in variety of ways. How can we utilize the two information to determine more reliable trustworthiness score?
Next, we will introduce our proposed model termed NEIGHBORAGG and elaborate on how these two components are constructed and efficiently aggregated by our method. The overall framework is illustrated in Figure
Feature Construction. For given sample x E X, we utilize two input features: the neighborhood vector h and the classifier output vector p shown in Figure
For the classifier output feature, use the aforementioned vector from the classifier p= F(x).
The neighborhood vector consists of the similarity of a sample to its K nearest neighbors across all the C' classes in the training dataset. Specifically, for the sample x and each class c E C, we find its K ncarest. neighbors from class e the training dataset: No = (nel, nxk) and construct a similarity vector s, as
8, = [Sat, "........kkk 8ek = KC nck)
(1)
where Ky is the Laplacian kernel with a transform f. Le. KC, z) = exp (- - fz) can be used well; but we find that practice, Euclidean distance wrapped into Laplacian kernel performs better. For tabular dataset, the transform set the identity mapping of the original data, which we find empirically yields sufficiently good performance. For image dataset, more complex transform (e.g. the
Cosine similarity
4

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm 1: Training Algorithm of NEIGHBORAGG
Input: Training set (rr; Validation set (Xent, Poat); Base classifier F; Kernel K;; Ageregator Ace; Training epoches M; Number of neighbors K.
Output: Parameters of NEIGHRORAGG: Wa, W,, W (parameters ACG).
Initialize W, Wp. W;
for
to c=
Building class-wise KD-trees using the training set Split from Ne: X. {x|x N cti
4
Construct KD-tree KDT, using N. based the kernel Ky;; end
for epoch = to do
Training our NEIGHBORAGG using the volidation set for x in Neal do
for c= 1 to do
11
Find K nearest neighbors of x from KDT;; Compute similarity vector s. using Equation
12
end
14
Compute the neighborhood vector h = [s1 1......... ||cc];
Compute the predicted vector with F: p = F(x);
16
Compute the trustworthiness using Aggregator: t == Acc (Wah, WyP);
17
Compute the loss function using Equation
18
Update Wa, Wp. W via gradient descent;
end 19
20 end
return WA. Wp. W
backbone of the base classifier) are used for higher performance. Then, the final neighborhood vector h is constructed by concatenating all such class-wise similarity vectors:
[1 || s2ll. ... |[sc],
where || denotes the column concatenation operator. The procedure is shown in the Figure
3
Aggregation. Considering the potentially varying contribution of h and p the trustworthiness score, we introduce two separate linear transformations to them, which parameterized by W,, E CXCK and W E RCx,, respectively. We then aggregate the two resultant vectors using an operator AGG R R + RC which outputs C-dimensional trustworthiness vector of x (one element for one class),
= AGG (W,h, W
(3)
Here, the aggregation operator AGG can be instantiated by any neural network.
The optimization process is carried out by reducing the negative log-likelihood loss (NLL), i.e. (on. (Cx,) y)] where each sample's loss is calculated as
1 ((x,y) -
Ye log(te).
(4)
The overall training procedure is summarized in Algorithm !1
For simplicity, a single-layer feedforward neural network with a learnable weight matrix W e Rx20 and a nonlinear activation o--) used as the aggregator in this paper. Formally, the trustworthiness vector t (as shown in Figure can be expressod
softmax (W ([W, W,P))).
(5)
Underlying the learnable framework, how do these two pieces information cooperate during the aggregation? Curious about this question, also investigate the mechanism and show the empirical result. in section 4.1

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm 2: NetcHmoRAGo-CMM
Input: Dataset {(x, yr. 0.) 1=);: Mislabeling rate p; Confidence level a; Well-trained trustworthiness model NEIGHBOR
Output: Mislabeled sample set S.
T [t: t, NEIGHBORAGGG())) AiΣiAm n}
R {ri r; (2- I(: yi) y;) -) 1igh t1, T
R sort(R)
D Sort in non-increasing order
Ba = [(N + 1)(1 -a) +
= T(B.)
> r(B.) is the Ba-th largest element of R.
S = {(xi, Vi) In VISigN}
return
Inference. Given a test sample X, we construct its corresponding neighborhood vector h from the training dataset and fetch its classifier output vector P from the basc classificr F. Then we evaluate the trustworthiness vector i using equation and fitted model parameters W, Wa, and Wp- Finally, the trustworthiness score can be evaluated by indexing the trustworthiness vector using predicted class c², i.e., Tee.
3.2 Relation to Graph Neural Networks
In this section, we study the relations between our design and graph neural networks (GNNs) and show that our approach is inherently more flexible than GNNs in termss of aggregating neighborhood information to augment the classifier output for trustworthiness prediction. GNNs (Kipf & Welling) 2017 Xu et al. 2019) have been a topic of interest in recent times for their powerful modeling capacity aggregate neighbors, and this motivates to compare our method with GNNs. Among the several GNN variants, choose the widely used graph convolutional neural network (GCN) the subject for simplicity.
First, we show that our design of employing only one- neighbors for trustworthiness prediction is effective and efficient by comparing the performance of multi-hop GCNs with onc-hop GCNs. Empirically, we demonstrate that the use of multi-hop GNNs does not have significant improvement and even degrades the performance for some datasets (see Table D). We argue that multi-hop neighborhood aggregation may lead the over-smoothing issuc and the noise accumulation risk, at least for our task.
Second, prove that NEIGHBORAGG is essentially generalized version of a one-hop GCN: certain constraints on our NEIGHBORAGG (i.e., fixing the learned matrices Wa and W, p to be block diagonally- dominant), NEIGHBORAGG acts as a one-hop GCN. This equivalence is rigorously characterized as follows.
when imposing
Theorem (One-hop GCN Equivalence). Provided that Wa, exhibits a block diagonal structure:
1 W, K |1xx 11) with 1" 11111-...11
K1's
where & denotes the Kronecker product, and that W, =:= NEIGHBORAGe operates onc-hop Graph Convolutional Network with the node features ly 0] 22C-1 for y E Yer and (o || E 2 for p p= F(x) with x E Neat U Mes, and the adjacency matrix A induced by a predefined kernel K, (e.g. Laplacian kernel).
Proof. The proof is relegated to Appendix A
Remark. In fact, our approach is more flexible than one-hop GCN for feature aggregation, as Wa and Wp in our setting can exhibit more flexible forms than the simple block diagonal structure. This further verified by empirical studies (see Figure 6). which show that our model can exploit not only intra-class relations, but also inter-class relations, which one-hop GCN cannot. More detailed analyses be found in Section 4.1

---

Published in Transactions on Machine Learning Research (08/2022)
3.3 Conformal Mislabel Detection: An Extension of NeighborAgg
In this section, show that our trustworthiness score can also be used for another task, mislabel detection. In particular, we introduce the NEIGHBORAGO-CMM algorithm to assess the reliability of data labels in a mislaboled dataset. The detailed procodure is described in algorithm 2
To identify mislabeled data a noisy-labeled dataset, we compute reliability score for the label of each sample using NEIGHBORAGG and a well-trained base classifier. The reasoning behind this is that labels that contradict the classifier's 's prediction and have low trustworthiness scores are questionable, meaning that when the neighborhood supports the classifier's prediction rather than the label itself, it is more likely the label that makes a mistake. So we devise the reliability score based on the class label y's trustworthiness score by:
(2 I( v) 1)
(6)
where the indicator function II()) and the classifier's 's prediction á are used to detect whether the sample is misclassified. Samples with reliability scores lower than certain threshold are treated as mislabeled (i.e.
TTTo).
To bound the probability of false negative detections, we apply the conformal anomaly detection (Balasub- ramanian et al. 2014)) framework and exlend the existing work to the noisy setting for determining the threshold Ta- Given a dataset of size N with mislabeling rate p, and user-specified confidence level a, we compute reliability scores for cach sample in the validation dataset and sort them in non-increasing order (ra))...)")))) The threshold is set to the B, largest element, i.e.,
((B.) where Ba [[N 1)(1 - a) aNpl
Next, show the following theoretical guarantee which to the best of our knowledge is the first to consider the real-world noisy data setting.
Theorem 2 (Noisy-robust Coverage Guarantee). For any given confidence level a E ( (N4T, 1), with probability at least a over the random choice of any correctly labeled data point (x, D), we have
i > Tas
where is the predicted reliability score of x and Ta is defined in Equation
7
Proof. The detailed proof is relegated to Appendix B In contrast to existing work in conformal learning which requires an i.i.d. validation set, our algorithm uses a partitioning approach to allow for a more realistic setting involving a small percentage of mislabeled samples.
Remark. Theorem 2 suggests that the reliability score that our method outputs provide theoretical guarantee with high probability, a correctly labeled data point will be given score above the threshold fa- In other words, if we select the likely mislabeled samples by selecting those below the reliability threshold, we can bound the probability of a false positive (by a).
4 Experiments
Through extensive experiments, we aim to answer the following questions:
Mechanism Visualization: How does NEIGHBORAGG work?
Effectiveness: How well does NEIGHBORAGG perform different lypes of datasets?
Ablation Study: How does each component of NEiGHBORAGG contribute to the trustworthiness performance?
Sensitivity: How sensitive to hyperparameters is NEIGHBORAGG?
Computational Cost: How fast is NEIGHBORAGG?
Case Study: How is NEIGHBORAGG extended to mislabel detection?
Due to space limitation, we refer discussions about hyperparameter sensitivity, computational cost, and case study of mislabel detection to the Appendix D

---

Published in Transactions on Machine Learning Research (08/2022)
C === 8
Landsat
WA R
W, E R
SensorLesto LessDrive
C= 11, = 5
WA lIx(XXX))
W E Ril
Figure 4: Visualization of weight matrices Wo. for similarity vectors and W, for classifier output lcarned by NeighborAgg. Brighter colors indicate larger values. The dimmer diagonal blocks in W (e.g. in the red rectangle) are empirically associated with their corresponding brighter diagonal entries in W, suggesting that NEIGHBORAGG combines sample confidence with neighborhood information in a complementory manner. The different weights within each diagonal block in Wa (e.g. in the orange rectangle) suggests that NEiGHBORAGG can learn an appropriate K (i.e. how many neighbors are necessary to determine the trustworthhness) for every class based on local density, making byyerporancte--imensiii.
4.1 Mechanism Visualization and Verification
In this section, examine the mechanism of NEIGHBORAGG empirically, demonstrating that our method utilizes neighborhood and classifier information in complementary manner and captures intra-class and inter-class relations inside the neighborhood.
Complementary effect We show that NEiGHBORAGG integrates neighborhood information with classifier output in a complementary manner: it adaptively weighs the importance of the classificr's output against neighborhood information for each class. In other words, when the sample's neighborhood information not accurate or useful, it relies more the classifier output; and vice versa. To show this empirically, Figure ! suggests that the dimmer diagonal blocks in WA (e.g. in the red rectangle) their corresponding brighter diagonal entries in W,, and vice versa. To further confirm this quantitatively, we calculate the Pearson's 's correlation coefficient between the diagonal blocks in W, and the corresponding diagonal entries W, on Landsat. The result shows a strong negative correlation p == -0.90, which sheds light on the complcmentary mechanism NEIGHBORAGG.
empirically associated with
Intra-class and inter-class relations We have three observations on how NEIGHBORAGG leverages neighbors: firstly, aligning with motivation and Theorem I the learned weight matrices Wn, and Wp are significantly block-diagonally dominant as shown in Figure exhibiting the noighbor-homophil property and our method's similarity to graph neural networks. Secondly, the different weights within each diagonal block in WA reflect different importance among neighbors of the same class (i.e. intra-class proximity) as shown in the orange rectangle region of Figure 4 This suggests that NEIGHBORAGG can automatically learn how many neighbors are necessary to determine the trustworthiness for every class basod on neighborhood without luning the hyperparameler K. Thirdly, the ofT-diagonal blocks represent. the inter-class relations, such similar exclusive relations among classes, which makes more flexible in determining a robust. trustworthiness score. We leave the more detailed discussion in Appendix C
4.2 Experiment Setup
Datascts. We evaluate our method on image datasots including CIFAR10 Krizhevsky 2009). FashionM-
NIST [Xioo al. 2017) and MNIST (Deng) 2012), and UCI tabular datasets Dua Graff 2017). including CardDefault, Landsat and Recognieoo,,,,,nn,, etc. Statistics of each dataset summarized in Appendix G

---

Published in Transactions on Machine Learning Research (08/2022)
CIE
Method
Recogiinnnn
Landsot
CarDDdanlt APC %
AUC %
APC %
APM %
AUC %
APC %
APM %
AUC %
APM %
Confideace
85.28(0.18)
96.09;0.14)
61.25(0.51)
86. (5..0550.47)
97.77(0.07)
52.09/2.13) 13)
65.19(0.30)
86, 86.94/0.21)
33.44(0.32)
TempScaling
(1:67(0.22)
96.8300115)
59.72(0.64)
87 20000 (2)
07.63(0.08)
(8.85(1.73)
65. 22(0.3))
87.04:0.25)
33.50(0.36
TroetSoore
(5.75(0:23)
98.46(0.12)
86. 66.933(0.63)
55.5550000
98.39(0.12)
64.7600 70)
61.61(0-42)
85.35(0.28)
28.42(0.41
LR
TCP
30.78(0.21)
96.96(0.13)
74.85(0.43)
89.4700.0 19)
08.06(0.15)
51.25(1.78)
08.79(0.29)
(8.
31.110.557
TopLabel
78. (8.38(0.31)
92. (8)
(4.85(0.33)
84 05(005033 31)
96. 96.45(0.10)
41.55
64. 85(04)))))
86 08/0 30)
33.91
Ours
(9.05)
(9.72(0.01)
(0.47().17) (0.17)
72.54(1.400 (0.04
67 67.00(0.31)
87 87.46(0.22)
(0..3)
Confidencc
93:94(0.29)
90.48(0.03)
(1.49(1.97)
90:25(0.37)
98 (0.00)
48.77(1.78) (8)
(2))2)
10-43(0.11)
33.24(0.37)
TempScaling
94.58(0.19)
99.55(0.02)
66.41(1.86)
89 50.26(0.24
98. 08.56(0.05)
46.85(0.91)
08.691 (8.68(0.32)
89.31(0.16)
33.07(0.44)
RF
TCP
TometSoore
90.96(0.23)
86.83(0:22)
90.22(0.01)
98.71(0.06)
29. 00(0.0))
39. 19(1 (6)
85.0710.77 77)
88.52(0.30 34)
(0.04)
07.97(0.16)
34.330
43.36(2.70) 76)
07 12.
(0:29)
89.57 89.57:0.14)
84.89/0.29)
25.84(0.38)
30.08(0.24)
TopLabel
53.99(0.51)
(1(0.10)
26. (6.79(
64.40(0.30)
97.57
32,54(1-10)
67.80(0.36)
20)
(2.14
Ours
96.45(0.188
90.69(0.02)
91.23((0.20 71.16(
98.91 (0.06)
53.60(1.80)
69.27(0.30)
(9.61(0.09)
(0.45)
Confideace
90.71(0.18)
99.18(0.044
39.59(0.93))
$441f1.60 61)
96.96(0.71;
40.26((.0c)
99(0.32)
19.06/0.18)
36.17(0.49)
TempScaling
93. (3.83(0.15)
99. 19(0.01)
52 (0.58)
87. 10(0.53)
0.196
16.10(1.22 20)
68. 20(0.39)
88, 96/0 (0)
31,9900
MLP
TruetSoore
88.53(0.31)
90.06/0.06)
28(0660)
48)
08.32(0.09]
41 81,85(1145
20.00)))3
84.82/0.22 25)
26.60/0.35)
TCP
(0.91(0.58)
07.62(0.15)
25.61 (6)
(6.01(1101)
97.78(0.26)
30.70/2.677 67)
67. 67.77(0.19)
88 68.91(0.09)
31.17(0.27)
TopLabel
78.78(1.55)
98.09(0.20)
(6.65(0.79)
81 .2)2))())))
96.70(0.29) 29;
30.16/0.93)
67 07.84(0.37)
88, (8).8)(011)
(2,81(0.44)
Ours
(5.02(0.36)
(0.58(0.04)
65.81(1.19)
91.75(0.39)
98. (8.88(0.08)
69.69(0.29) (7.80(0.91)
89.51(0.19)
35.64(0.28)
Table 1: The performance of our proposed model NEIGHBORAGG and other models on three tabular datasets (mean We report. the results of all models based on different base classifiers (LR, RF, MLP) and best. results are emphasized in bold. We use TempSealing for Temperature Scaling due to space limitation.
Compared methods. We compare our proposed NEIGHBORAGG with the following methods:
Confidence Score (Hendrycks & Gimpel 2017 employs the maximum softmax output of a classifier as measure of trustworthiness.
Temperature Scaling (Guo et al. 2017 modifies the confidence score using a temperature parameter
T learned from the validation set.
TCP (Corbière et al. 2019) trains a ConfidNet using an intermediate output of any neural networks as the input for regression to the desired softmax output.
Trust Score (Jiang ct al. 2018)) defines the trustworthiness mcasure as the ratio between the distance from the test sample its nearest neighbor with labels excluding the predicted class, and the distance from the test sample to the nearest neighbor of the predicted class.
Top-label Calibration (Gupta & Ramdas (021] calibrates classifier's softmax output by using histogram bimning to reduce top-label multi-class calibration into binary calibration.
GCN-khop uses k-hop GCN to aggregate neighborhood information and classifier output for
trustworthiness prediction. Its detailed implementation can be found in Theorem 1 and Appendix
Evaluation Metrics. Following the existing pioneering work on trustworthiness (Hendrycks & Gimpel 2017 Corbière et al., 2019), we adopted the same metrics to evaluate the trustworthiness of a base classifier: AUC-ROC, APM and APC. More details regarding specific evaluation procedures can be found in Sec. of Hendryeks & Gimpel (2017). All reported results averaged over 5 trials under distinct random seeds the same splits of datasets.
Implementation Details. For tabular datasets, experiments are conducted based on three base classifiers, including logistic regression (LR) Peng ct al. 2002). random forest (RF) (Svetnik et al. 2003) and multi-layer perceptrons (MLPs) (Ruck el al. 1990); while for image datasets, shallow convolutional nelworks, Resnet18
and Resnet50 (He et al. 2016) are used. We leave details such as hyperparameters to Appendix G
4.3 Effectiveness of NeighborAgg
Performance results on tabular datascts and image datasets are summarized in Table Tand Table 2 reepectively from which we make the following observations:
Firstly, our proposed NEIGHBORAGG outperforms other models under almost all metrics across benchmarks. Specifically, Table [ shows that our model achieves the most significant improvement on APM, with the highest performance gain of 12.17%, and the average performance gain of 7.63%. This suggests that our model performs best. in identifying misclassified samples. Besides, N NEIGHBORAGG achieves more than 2%
9

---

Published in Transactions on Machine Learning Research (08/2022)
MNIST
FaelionMNIST
CIFARIO
Method
APC
Coulidence
90.48(0.39)
98.93(0.06)
(6.71(1888
(..3))
99.10/0.68)
1122(1.03)
83.72(1.1))
91.9710.00
54-42;1160
TempScaling
90.50(0.40)
98.93(0.00)
17.27(1.99)
(1.33
99.11(0.03)
(1.27(0.99)
53.73(1.25 29)
(1.6600.08)
51881(1.0)
TrustSorre
96.40(0.28)
90.61(
T8.53(1.25)
91.31(0:11)
99.100003)
47.27(0.86)
86.980.75)
96.0410.15
63 63.29(3.84)
TCP
92. (1..0)))33)
96.37(0.13)
69.91(7747 47)
(0.82
98.83(0.03)
50.52(1.33)
66.63(0992)
96.36,0 16)
61.06;3.10)
TopLabel
90.35(0.31)
98.89(0.05)
43.31(1.02)
89.54(0.41)
08.62(0.17)
45.76(1.53)
85.24(1.17)
94
60.90(5.59)
Mahala
75.88(0.23)
(0.0)
21.06(0.48)
(0.87)
04.26(0.06)
11.15(0.08)
66.73(5-92)
82.93(3.07)
23.47(3.10)
GONHhup
91.77(0.27)
98.07(0.05)
63.75(1.77)
90.44(0064)
98. 08.94(0008)
46 46.63(1 70)
82.68 32.68(1.4 44)
93. 93.78(0.38 31)
60 79.5.0))
GCN2hop
91.58(0.29)
99.05(0.05)
64.71(1.90)
(0.35
(8.92(0.07)
15.63(1.91)
83.75(1.66)
91.18(0.11)
62.37
CCN1hop
91.38(0.100
98.02(0.06)
63.77(1.89)
(0.31
98 (..08)
45.80(1.76) 76)
84.08
94.13(0.27)
62.63 02.63:5.33)
Ours
96.10(0.52)
99.53
99 99.04(0.02) 91.52(0.16) 81.02(1.91)
18.53(0.51)
87. 67.52(1.07)
96.05(0.51)
65.27(4.03)
Table 2: The performance of NEIGHBORAGG and other models on image datascts (mean + std). Best. results are emphasized in bold. We refer to Table for the full name of abbreviations.
ProbOsty
Weighonly
Trust Score
APM
60
40
20
CarcDafeult
BantMariseting
Landast
Letterlacognttinn
NagicGamma
SansorLauaDrrvve
(a) Comparison for LR base classifiers under the APM metric.
100
Oura
90
ProbOnly
NeighDely
Trust Score
AUC
80
70
60
BanikMarkwting
LatterRacognition MagicGamma
(b) Comparison for RF base classifiers under the AUC metric.
Figure 5: Performance results for ablation study. NEiGIBORAGG outperforms all the other model variants ProbOnly and NeighOnly across all datasets with LR and RF as the base classifiers, respectively. More results can be found in Appendix
improvement on AUC in most cases. Table 2 reveals that our model also achieves better or comparable performance on image datasets.
Secondly, the result suggests that the neighborhood information and classifier prediction are two essential and complementary sources information for trustworthiness prediction. This demonstrated by results shown in Table T that Trust Score achieves better results than Confidence Score on LetterRecogniee and Landsat when LR the base classifier, whereas Confidence Score performs better on CardDefault. Moreover, our method's outperformance of both information sources validates the complementary effect.
Thirdly, our method consistently beats the GCN-based method across all datascts, suggesting that our formulation is more effective and efficient. In addition, Table 2 also demonstrates that one-hop neighborhood aggregation is sufficient and that utilizing multi-hop neighbors may lead to the over sver-smoothing issue, by showing that multi-hop graph convolutional neural networks have limited improvement compared to the one-hop model, and sometimes become worse.
4.4 Ablation Study
To demonstrate the effoctiveness of each component and the adaptiveness of the learnable weights NGGG compare against its variants ProbOnly and NeighOnly.
10

---

Published in Transactions on Machine Learning Research (08/2022)
Detected mislabeled example questions
What the past Lense pasl lense?
What is the difference between fusion and a restaurant?
What are the new product for agent project?
Which protagonist from video game have you
related to?
Do I have to appear for IMU CET again even if 1 get good rank if appearing for improvement HSC board exam?
What are some important things/ hatngs/stpps when starting film production company in Netherlands!
What astrological combinations
needed to obtain scholarship for studies?
What advice would you give person intending buy a Nissan note, in terms performance
Le. traction, fuel economy, maintenance and resale?
Table 3:
Mislabeled samples detected in QuoralnsQ by our NEIGHBORAGG-CMD. These questions are labeled as insincere but are actually sincere.
NnighOnly: solely takes neighborhood vectors as input, ProbOnly: solely inputs classifier output vectors,
as well as the non-learnable baseline Trust Score.
Figure demonstrates the comparison results of the ablation study on seven tabular datascts. Results using other base classifiers and other metrics are listed in Appendix H
We note that NEIGHBORAGG consistently outperforms ProbOnly and NeighOnly across all datasets, especially on SensorLessDrive with 8.83% gain and on BankMarketing with 3% gain, which indicates that both vectors make non-negligible contributions to the final trustworthiness score, and that considering either of them alone is insufficient. It supports the claim that the neighborhood and the predictive output of the classifier complement one another in determining the trustworthiness score.
Moreover, the comparison between NeighOnly and Trust Score suggests that considering set of neighborhood rather than solely class-wise nearest neighbors contributes to the performance gain; by inspecting those neighborhoods, NEIGHBORAGG can utilize richer information and flexibly choose its receptive field, iee. how many neighbors are necessary to determine the trustworthiness score. It also empowers the model to adaptively capture intra-class relations (i.e. different proximity of a sample's neighbors) and inter-class relations, c.g, some classes may be more closely related as compared to other classes.
4.5 Mislabel Detection: Case Study
This section demonstrates the usefulness of our NEIGHBORAGG-CMM algorithm by presenting mislabeled samples in real-world datasets. We use dataset named Quoralns() from the Kaggle competition "Quora Insincere Questions Classification" that aims to improve online environment by detecting toxic questions. The datasel consists of 1,306, 122 questions which are manually categorized as sincere insincere. The definition of an insincere question is one that intends to make a statement instead of eliciting helpful responses. In order to estimate the mislabeling rate, we manually relabel 500 randomly selected questions and utilize the fraction of incorrectly labeled samples as the mislabeling rate.
Firstly, we use the model of the top-ranking team from the leaderboard as our base classifier and use NEIGHIBRAGG--MD to compute the reliability score for each sample. The mislabeling rate p is estimated 0.03. Then, we run NEIGHBORAGG- CMD with the confidence level 5% and obtain the detected mislabeled results. Then we showcase some of the detected example questions with the lowest reliability scores in Table 3) We find that all of them were labeled as 'insincere" in the original dataset, but none of them breach the four rules that signily a question as insincere. More experiments can be found in Appendix
5 Related Work
Trustworthiness Prediction. Trustworthiness prediction, also known as "failure prediction" and "mis- classification detection" in the literature, aims to assign a discriminative score every prediction given by base classifier, indicating whether trust this prediction or not. This has received increasing
11

---

Published in Transactions on Machine Learning Research (08/2022)
attention in recent times. Hendryckk & Gimpel (017
suggests using confidence score to tackle this problem.
Therefore, the confidence calibration method, designed to mitigate the over-confidence issue of the confidence score, can also be applied to trustworthiness prediction by giving a more accurate calibrated confidence score. Monte-Carlo dropout (Gal & Ghahramani 2016) and Decp-Ensemble (Lakshminarayanan et al. 2017) compute the output variance of multiple trials to detect incorrect predictions, while these ensemble- based methods are quite computationally expensive. Trust Score (Jiang et al. 2018) proposes a score which is a fixed, non-learnable function of the neighborhood of a sample, and hence suffers from limited functional space. Corbière et al. (2019) proposes regression method to fit the ground truth label's corresponding softmax score and uses it as a proxy for trustworthiness. However, this relies on the assumption that the base classifier is always over-confident, which is not always the case (e.g. graph neural networks were found to be under-confident in Wang el al. (2021)) Malinin & Gales] (0188;; ; Malinin et al. (2020); Sensoy et al. (2018); Charpentier et al. (2020) assume the classifier outputs are sampled from a latent Dirichlet distribution and treat low-likclihood samples as misclassificd samples. These methods typically involve modified architectures that need to be trained from scratch, and in some cases can involve the trade-off between classification accuracy and the performance of trustworthiness prediction. In contrast, our proposed NEIGHBORAGO keeps the base classifier intact and uses auxiliary information for simple estimation. In our work, we aim to measure trustworthiness by adaptively utilizing the classifie'ss predictive output and neighborhood information via a flexible mapping that combines the best of both worlds.
Relations to Out-of-distribution Detection. Oustof-distrbbution (OoD) detection (Hendrycks & Gimpel 2017 Sastry & Oore, 2020 Ming et al., 2022) are closely related to trustworthiness prediction but targeted at dilferent. goal. OoD detection aims to measure the sample quality by identifying input data whose ground truth label is not covered by the label set of the training dataset, whereas trustworthiness prediction aims to measure the classifier's quality by identifying input data whose predicted label does not match its ground truth label. However, since they both detect abnormal behaviors, the assumption used for one task can be applied to the other with some modification. For example, our neighbor-homophily assumption can also be extended to OoD detection by assuming that samples that are distant from neighbors in all classes are likely to be out-of-distribution data. On the other hand, methods for detecting OoD data, such as mahalanobis distance Lee et al. (2018), can also be adapted to our task.
Mislabel Detection The goal of mislabel detection is to identify data whose labelled class differs from the underlying ground truth class. A majority of research in this field leverages training dynamics for differentiating correctly labelled and mislabelled samples, such as the dynamics of logit in AUM Pleiss et al.] (2020) and the loss distribution in DY-Bootstrapd Arazo et al. (2019). Our approach falls into a different line of direction Northcutt et al. (2019) Zhang et al. (2021) that employs pre-trained classifiers. Confident Learning Northcutt
al. (2019). for example, estimates a noise transition matrix based on the softmax output. In addition to the softmax output, we also consider a sample's local neighborhood, which allows us to infer individual samples more accurately compared to confident learning.
6 Conclusions and Discussion
Conclusion Knowing when to trust a classifier is essential for safe deployment of present machine learning algorithms. To solve the problem, we devise a model-agnostic post-hoe trustworthiness prediction algorithm NEIGHBORAGe AGG which leverages information from the neighborhood and the classifier to predict the trust- worthiness of predictions given by classifier. By theoretically demonstrating that NEIGIBORAGG is a generalized one GCN aggregating information from the neighborhood and the sample itself, we provide better understanding of how our approach works. The working mechanism is also revealed by empirical studics, which show that our approach can utilize the classifier output and neighborhood information in a complementary manner, and caplure diverse similarities within different neighborhoods. On several tabular and image benchmarks, the effectiveness of NEIGHBORAGG is empirically validated via comparison with other state-of-tho-art methods and ablation studics. Of independent interest, an extension of NEIGHBOR AGG to mislabel detection is also introduced with a noise-robust coverage guarantee for bounding the false negative predictions.
12

---

Published in Transactions on Machine Learning Research (08/2022)
Discussion The current study assesses classifier's trustworthiness by utilizing each sample's neighborhood, comparing each sample's prediction to its neighbors' ground truth labels. Besides that, it would be interesting to explore alternative information associated with the trustworthiness of the classifier. The model explanation generated by explainable approaches, for example, can be used to determine trustworthiness. prodiction with implausible explaining logic likely wrong. Moreover, going beyond unstructured data, we believe NeiGhbORAGG is also promising for measuring trustworthiness of graph-structured data, which can be an interesting and nontrivial extension to this work.
Acknowledgments
This work was supported part by NUS ODPRT Grant 122220000A81--333
References
Alexandr Andoni and Piotr Indyk. Nearest neighbors in high-dimensional spaces, In Handbook of Discrete and Computational Geometry, pp. 1135-1155. Chapman and Hal//CRC, 2017.
Eric Arazo, Diego Ortego, Paul Albert, Noel O'Connor, and Kevin McGuinness. Unsupervised label noise modeling and loss correction. In International conference machine learning, pp. 312 321. PMLR, 2019.
Vineeth Balasubramanian, Shen-Shyang Ho, and Vladimir Vovk. Conformal prediction for reliable machine learning: theory, adaplations and applications. Newnes, 2014.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gačl Varoquaux. API design for machine lcarning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pp. 108- 122, 2013.
Jie Chang, Zhonghao Lan, Changmao Cheng, and Yichen Wei. Data uncertainty learning in face recognition. In Proceedings of the IEEE/CVP Conference on Computer Vision and Pattern Recognition, pp. 5719, 2020.
Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Posterior network: Uncertainty estimation without ood samples via density-based pscudo-counts. ArXiv, abs/2006.09933) 2020.
Bycongjun Choi, Byungjoon Chang, and Insung Ihm. Improving memory space efficiency of kd-tree for real-time ray tracing. In Compuler Graphics Forum, volume 32, pp. 335 344. Wiley Online Library, 2013.
Charles Corbière, Nicolas Thome, Avner Bar-Hen, Matthieu Cord, and Patrick Pérez. Addressing failure prediction by learning model confidence. arXiv preprint arXiv:1910.04851, 2019.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 142, 2012.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://arccivve.ccs.uii.
m1
Evelyn Fix and Joseph Lawson Hodges. Discriminatory analysis. nonparametric discrimination: Consistency
properties. International Statistical Review/Revue Internationale de Statistique, 57(3):238 247, 1989.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty
in deep learning. ArXiv, abs/1506.02111 2016.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pp. 1321-1330. PMLR, 2017.
Chirag Gupta and Aaditya K Ramdas. Distribution- free calibration guarantees for histogram binning without sample splitting. International Conference on Machine Learning, 2021.
13

---

Published in Transactions on Machine Learning Research (08/2022)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the TEEE conference on computer vision and pollern recognition, pp- 778, 2016.
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. Proceedings of International Conference on Learning Hepresentations, 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pp. 448-456 PMLR, 2015.
Heinrich Jiang, Been Kim, Melody Y Guan, and Maya Gupta. To trust or not to trust a classifier. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5544655551 2018.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. arXiv preprint arXiv: 10.117720787444 2017.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. Interna- lional Conference on Learning Representation (ICI.R, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Balaji Takshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NewrIPS, 2017.
Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of- distribution samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
Shen Li, Jianqing Xu, Xiaqing Xu, Pengeheng Shen, Shaoxin Li, and Bryan Hooi. Spherical confidence learning for face recognition. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 15629 15637, 2021.
Andrey Malinin and Mark John Francis Gales. Predictive uncertainty estimation via prior networks. In NewrIPS, 2018
Andrey Malinin, Bruno Mlodozeniee, and Mark John Francis Gales, Ensemble distribution distillation. abs.1195.00076, 2020.
ArXio,
Yifei Ming, Ying Fan, and Yixuan Li. Poem: Ont-of-distribution detection with posterior sampling. In International Conference on Machine Learning (ICML). PMLR, 2022.
Curtis G. Northcutt, Lu Jiang, and Isaac L. Chuang. Confident learning: Estimating uncertainty dataset. labels. 2019. doi: 10.48550/ ARXIV. 1911.00068. URL http:://aaxxxx..rg//a/////// 00068
Chao Ying Joanne Peng, Kuk Lida Lee, and Gary M Ingersoll. An introduction to logistic regression analysis and reporting. The journal of educational research, 96(1):3-14, 2002.
Geoff Pleiss, Tianyi Zhang, Ethan Elenborg, and Kilian Q Weinberger. Identifying mislabeled data using the area under the margin ranking. Advances in Neurul Information Processing Systems, 33:17044 17056, 2020.
Quora and Kaggle. Quora insincere questions classification competition, 2018. URL https: //www//wwww.. kaggle
M Rafiee and M Abbasi. Pruned kd-tree: a memory-efficiet algorithm for multi-field packet classification.
SN Applied Sciences, 1(12):1 19, 2019.
Dennis W Ruck, Steven K Rogers, Matthew Kabrisky, Mark E Oxley, and Bruce W Suter. The multilayer perceptron as an approxination to bayes optimal discriminant function. IEEE transactions on neural networks, 1 (44):296 298, 1990.
14

---

Published in Transactions on Machine Learning Research (08/2022)
Chandramouli Shama Sastry and Sageev Oore. Detecting nut-of-distribution examples with gram matrices. In International Conference on Machine Learning, pp. 14911-5011 PMLR, 2020.
Peter Scheuermann and Mohamed Ouksel. Multidimensionall b-trees for associative searching in database systems. Information systems, 7(2):123-133 137, 1982.
M. Sensoy, Melih Kandemir, and Lance M. Kaplan. Evidential deep learning to quantify classification uncertainty. In NewrIPS, 2018.
Yichun Shi and Anil K Jain. Probabilistic face embeddings. In Proceedings of the IEEE International Conference on Computer Vision, pp. 6902 6911, 2019.
Vladimir Svetnik, Andy Liaw, Christopher Tong, J Christopher Culberson, Robert P Sheridan, and Bradley P Feuston. Random forest: classification and regression tool for compound classification and qsar modeling. Journal of chemical information and compuler sciences, 43(6):1947-1955) 2003.
Varshney and Alemzadeh. On the safety of machine learning: Cyber-physical systems, decision sciences, and data products. Big data, 5 3:246 255, 2017.
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. NeurIPS, abs/2109. 14285, 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Mingyuan Zhang, Jane Lee, and Shivani Agarwal. Learning from noisy labels with no change to the training process. In International Conference on Machine Learning, pp. 12468 12478. PMLR, 2021.
15


Reviews:
[{"review_id": "BMhjBf3svF", "reviewer": "Reviewer_tWn7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n- The paper addresses an important problem, namely accessing the reliability of ML predictions.\n- The proposed method is intuitive and relatively clearly explained (see questions below though), and it seems to perform reasonably well in experiments.\n- Comparison to related work is nice.\n- The paper is relatively well-written.\n\nWeakness:\n\n- Some aspects about the algorithm are not very clear to me, see \"Requested changes\".\n- The method seems to incur a high computational and memory cost at inference time. This does not seem to be discussed in the paper.\n- Theorem 2 is fairly confusing to me, since it does not seem to depend on the underlying classifier $\\mathcal{F}$ at all. Is it purely a probabilistic statement related to the random sampling of the data and the properties of ordering?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a technique for estimating the trustworthiness of the predictions of an ML model. The proposed technique uses the logits of the model, together with neighborhood information. The method also extends to a technique for detecting mislabeled data instances. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I would suggest the following changes, which will hopefully make the contributions of the paper more clear and improve readability:\n\nMajor: \n- Please add a discussion on computational and memory aspects of the proposed methods and compare to prior work.\n- Please add a discussion on Theorem 2, in particular how does it depend on $\\mathcal{F}$.\n- Overall, it will be nice to make it more clear what sections/paragraphs/equations/part of the algorithm work with the training, validation and test data.\n\nSimple, but important fixes:\n- Page 3, Problem 1: Does the trustworthiness score depend on the test labels as well? This is currently imply by $t_c = \\Tau (\\mathcal{F}(x); \\mathcal{F}, \\{\\mathcal{X}, \\mathcal{Y}\\})$.\n- Page 3: $\\mathcal{X}$ is used both for the input space and for the set of inputs in the dataset.\n- Page 4: what is the function $f$ used for the similarity measure?\n- Page 5, before equation (4): do you mean expectation w.r.t. $\\mathcal{X}_{tr}$, not $\\mathcal{X}_{val}$\n- Page 5, Inference: how is the neighbourhood vector $\\tilde{h}$ computed? Is it with respect to the training data points? With respect to the other test points?\n- Algorithm 2 and Section 3.3 - please use indexes for the data points, otherwise the notation is very confusing.\n- Algorithm 2: what is $n$? Do you mean $N$?\n\nMinor:\n- Page 2: by focusing on a pretrained classifier, and among which ... --> by focusing on a pretrained classifier. Among these ...\n- Page 3 footnote: dataset --> datasetS\n- Page 4, Feature reconstruction: make it clear that this is about the training data - at test time you do not have access to the labels.", "broader_impact_concerns": "None that I can think of.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "H4Hyj2dWMy", "reviewer": "Reviewer_D4Gw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- This paper constructs reasonable features that represent the sample's neighborhood information.\n- This paper demonstrates that the sample's neighborhood and the classifier's output are complementary in failure prediction.\n- The proposed approach has good scalability: more information, such as model explanation scores, might be aggregated to obtain better performance.\n- The empirical performance of the proposed approach is good, especially on tabular datasets.\n\n**Weaknesses**\n- Previous work has shown that the neighborhood information can be leveraged to measure the trustworthiness of a classifier's predictions. This work aims to show that there is still some room for performance improvement with this information. Then, the authors replace the non-trainable function of the previous work with a trainable one. In this sense, the proposed approach is marginal.\n- Only two factors are leveraged to predict trustworthiness. More factors would be helpful.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to obtain a trustworthiness score that can detect incorrect predictions of a pre-trained classifier. To this end, the authors propose to train a failure predictor whose inputs are the sample's neighborhood information and the classifier's output. The failure predictor is flexible enough to utilize the patterns in the inputs, thus achieving state-of-the-art trustworthiness performance.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- (major) The statement of Problem 1 is not informative. The statement only tells the reader what information is required to calculate the trustworthiness score, while it does not define the goal of the score. What problem is the trustworthiness score proposed to solve? After reading the current statement of Problem 1, readers may not understand what Trustworthiness Prediction is.\n- (major) From Algorithm 1, the failure predictor NeighborAgg is trained using a training set. Is the base classifier 100% accurate on this training set? It is a common case for deep neural networks to achieve 100% accuracy on a training set. If it is the case, then there is no need to detect an incorrect prediction on the training set. How can the proposed approach really learn to predict failure in this case?\n- (minor) The inputs of Algorithm 1 include unused items, such as Validation set and Trustworthiness performance evaluation metric. These items do not appear in the the algorithm.\n- (minor) Random forests are used in experiments. It would be better to explain what is the classifier output feature of a random forest for feature construction.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "B2Wq5ggNVK", "reviewer": "Reviewer_QWSV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The paper is overall clearly written - it contains a clear motivation, a well-explained method, and detailed experimental setups (in Appendix).\n- The experiments are thorough especially in its ablation study: i.e., to verify that having both information of prediction probability and neighborhoods complementarily improves confidence calibration.\n- The proposed method is generally applicable for any pre-trained classifiers.\n\nWeaknesses\n\n- I think the paper could compare (or discuss) with more recent methods in the literature of confidence calibration or OOD detection in their experiments: in my understanding, the paper tackles the problem of “trustworthiness prediction” which is highly related to confidence calibration or OOD detection. The paper differentiates its position compared to those tasks in Section 5, but I generally feel that the differences are only weakly justified:\n    - (a) It first states that the usual confidence calibration techniques are not suitable for trustworthiness prediction because they do not alter the ranking of the prediction: but I do not think it is a crucial issue, e.g., one can still define the max-confidence as the trustworthiness score to address the task, and I am not fully convince that these two tasks are essentially different.\n    - (b) Compared to OOD detection, on the other hand, the paper states that the goal of OOD detection is not to evaluate on $p(y|x)$ but rather on $p(x)$: but this is also not clear to me as well - for example, one of state-of-the-art OOD detection method of Mahalanobis distance-based detection [Lee et al., 2019] does define $p(y|x)$ by means of a generative classifier based on a class-conditional Gaussian model, so one can still use this score to define a new trustworthiness score. Even for the method proposed in this paper, one may view that the method incorporates another generative classifier based on a kNN based model, so the method is related to Mahalanobis in this sense. The readers may also question whether other recent OOD based methods indeed only target modeling $p(x)$ rather than modeling a better $p(y|x)$ [2-6].\n- The empirical gains are often not clear given the standard deviations, especially for the results on image datasets (Table 2). For the tabular results in Table 1, on the other hand, I wonder if the gains would still remain significant if one considers a larger base classifier, e.g., beyond an MLP, so that the # parameters of the classifier can dominate those newly introduced in the proposed method.\n- The experiments are limited to only small-scale datasets, e.g., the 10-way CIFAR-10 classification at best, despite that one of the main claim of the proposed method is in its model-agnostic sense. There are many dimensions the paper did not cover to verify the scalability: e.g., with respect to the dataset size, model size, and # classes.\n\n[1] Lee et al., A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks, NeurIPS 2018.\n\n[2] Lee et al., Training Confidence-calibrated Classifiers for Detecting Out-of-Distribution Samples, ICLR 2018.\n\n[3] Hendrycks et al., Using Self-Supervised Learning Can Improve Model Robustness and Uncertainty, NeurIPS 2019.\n\n[4] Bergman and Hoshen, Classification-Based Anomaly Detection for General Data, ICLR 2020.\n\n[5] Tack et al., CSI: Novelty Detection via Contrastive Learning on Distributionally Shifted Instances, NeurIPS 2020.\n\n[6] Sastry et al., Detecting Out-of-Distribution Examples with Gram Matrices, ICML 2020.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the effect of incorporating class-wise k-nearest neighbor (kNN) models (in the input space) to calibrate the prediction confidences from a given classifier, to address the “trustworthiness prediction” task - a narrower variant of confidence calibration or out-of-distribution (OOD) detection tasks, where the focus is to define a score function capable to discriminate whether a given (test) input will be correctly/incorrectly classified. The paper next presents that the proposed method can be extended for detecting mislabeled samples. Experimental results on tabular (LetterRecognition, Landsat, CardDefault) and image (MNIST, FashionMNIST, CIFAR10) datasets show that the proposed method (score) achieves better AUC and Precisions on detecting misclassified samples over other baseline considered.  ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Major requests\n\n- More empirical investigation on the scalability of the proposed method, with respect to (a) the dataset size, (b) model size, and (c) # classes, as mentioned above. For example, I suppose that applying the method to pre-trained ImageNet classifiers would not that be technically hard given the model-agnostic sense of the method. If it is not the case, please add a respective discussion on why extending the method to larger-scale is practically difficult.\n- More discussions and comparisons considering recent literatures of confidence calibration or OOD detection in the experiments. The Mahalanobis [1] baseline seems crucial in this point, given that it defines a new confidence score $p(y|x)$, and is a post-hoc algorithm from a pre-trained model, as also claimed in the paper.\n- The definition of Trustworthiness prediction task (Problem 1) is quite unclear to me: Given that one gets trustworthiness scores $t_c$, what would be the goal of the task? - a more precise definition of the problem seems to be needed.\n\nMinor requests\n\n- Table 2: Missing indication in the main text for the details on how the GCN-based baselines (GCN*hop) are designed.\n- Section 3.2: I feel that the relationship between the method to GCN is somewhat vague, given that the proposed (MLP-like) architecture is quite general in practice - a more discussion needed on the actual implication of this relationship would be appreciated, e.g., does it mean that the method can leverage some useful properties of GCN? Or, does NeighborAgg can improve GCN?\n- There is also a literature on the mislabel detection task, e.g., [7], thus I think there should be also a respective discussion on it.\n\n[7] Pleiss et al., Identifying Mislabeled Data using the Area Under the Margin Ranking, NeurIPS 2020.", "broader_impact_concerns": "It seems the paper currently does not contain discussions that explicitly or implicitly states on Broader Impact. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the effect of incorporating class-wise k-nearest neighbor  models in the input space to calibrate the prediction confidences from a given classifier, to address the “trustworthiness prediction” task: a narrower variant of confidence calibration or out-of-distribution (OOD) detection tasks, where the focus is to define a score function capable to discriminate whether a given (test) input will be correctly/incorrectly classified. The sufficient experiments verify that the proposed method works better than existing sota methods sota experiments. In general, the main idea of this paper and the theory proposed in this paper are interesting. However, the authors should merge all rebuttal information before the full acceptance. Thus, I would like to recommend accepting the submission with minor revision.
Decision: Accept (poster)