Source-linked AI summary
To Trust Or Not To Trust A Classifier
Heinrich Jiang, Been Kim, Melody Y. Guan, Maya Gupta
TL;DR
The paper asks how to identify when a classifier’s prediction should be trusted, a question less studied than improving predictive accuracy. It proposes a trust score based on class-conditional data geometry and finds that it often outperforms model confidence, with theoretical guarantees under stated assumptions.
Problem
Determining whether an individual classifier prediction can be trusted remains less studied than improving overall classifier performance, despite its importance for consequential decisions.
Method
The trust score compares distances from a test example to high-density sets of the predicted class and the nearest different class using labeled examples.
Results
Trust scores consistently outperform classifier confidence in identifying trustworthy and suspicious examples across the reported empirical settings, while high or low scores predict likely agreement or disagreement with the Bayes-optimal classifier.
Takeaways & Limitations
Trust scores provide a separate signal for judging classifier predictions and can support user assessment, human review, and monitoring for distribution shifts.
Takeaways & Limitations
On high-dimensional datasets, trust scores may provide little or no improvement over model confidence, and the theoretical analysis requires regularity assumptions on density-level-set boundaries.
Abstract
from arXiv · showhide
Knowing when a classifier's prediction can be trusted is useful in many applications and critical for safely using AI. While the bulk of the effort in machine learning research has been towards improving classifier performance, understanding when a classifier's predictions should and should not be trusted has received far less attention. The standard approach is to use the classifier's discriminant or confidence score; however, we show there exists an alternative that is more effective in many situations. We propose a new score, called the trust score, which measures the agreement between the classifier and a modified nearest-neighbor classifier on the testing example. We show empirically that high (low) trust scores produce surprisingly high precision at identifying correctly (incorrectly) classified examples, consistently outperforming the classifier's confidence score as well as many other baselines. Further, under some mild distributional assumptions, we show that if the trust score for an example is high (low), the classifier will likely agree (disagree) with the Bayes-optimal classifier. Our guarantees consist of non-asymptotic rates of statistical consistency under various nonparametric settings and build on recent developments in topological data analysis.
1 Introduction
The paper addresses when classifier predictions can be trusted, arguing that accuracy alone is insufficient and proposing trust scores as an alternative to model confidence. Trust scores use labeled examples to assess predictions and outperform confidence-based signals in several settings.
- Classifier mistakes can have unequal costs, so understanding model strengths and limitations complements efforts to improve overall accuracy.
- Trust scores can help users assess AI decisions, route cases to human operators, and monitor classifiers for distribution shifts.
- The method uses labeled examples to compare a classifier’s prediction with distances to class-specific high-density sets.
- High or low trust scores theoretically correspond to likely agreement or disagreement with the Bayes-optimal classifier under several nonparametric settings.
- Trust scores better identify correctly classified points than the model itself in low- and medium-dimensional feature spaces, while high-dimensional spaces remain challenging.
2 Related Work
Related approaches estimate uncertainty from classifier outputs, abstention mechanisms, classifier sequences, or learned representations. The trust score instead evaluates an already trained classifier using data geometry and can operate on different representations.
- Calibration methods transform classifier scores into probability-like values but generally preserve the original score rankings.
- Bayesian neural-network approaches return output distributions, whereas the trust score leaves network structure unchanged and produces a single uncertainty score.
- Reject-option methods jointly learn prediction and rejection functions, while this paper evaluates an already trained, possibly black-box classifier without learning rejection thresholds.
- Sequential-classifier methods decide whether to stop evaluating models based on whether the current score will match the full sequence’s classification.
- Trust scores can use raw inputs, unsupervised embeddings, or intermediate activations, paralleling representation-based k-NN uncertainty and robustness methods.
- The density-filtering component builds on topological data analysis while estimating a suitable density level without knowing the level in advance.
3 Algorithm: The Trust Score
The trust-score algorithm first filters each class to retain high-density training examples, then compares a test point’s distances to the predicted and nearest alternative classes. The procedure supports multiple distance representations and has density and neighborhood parameters.
- The α-high-density-set retains class samples after filtering out the α-fraction with the lowest density, which may be outliers.
- Algorithm 1 approximates each class’s high-density set by filtering low empirical-density points using k-nearest-neighbor radii, independently of the classifier.
- The trust score is the distance to the nearest alternative class’s high-density set divided by the distance to the predicted class’s high-density set.
- A large distance to the predicted class relative to the closest alternative class warns that the classifier may be mistaken.
- Distances may be computed in raw inputs, unsupervised embeddings, or intermediate representations, and nearest-neighbor distance may be replaced by k-nearest-neighbor or centroid distances.
- The method uses k, the neighbor count, and α, the fraction of data filtered during empirical-density estimation.
4 Theoretical Analysis
The theoretical analysis establishes finite-sample guarantees for estimating high-density sets across full-dimensional, manifold, and noisy-manifold settings, then connects trust scores to Bayes-optimal decisions under regularity assumptions.
- 4.1 Analysis of Algorithm 1: Algorithm 1 consistently estimates α-high-density sets with finite-sample rates under full-dimensional, manifold, and noisy-manifold settings.The analysis uses Hausdorff distance, providing a uniform guarantee over the estimator.
- 4.1 Analysis of Algorithm 1: In full-dimensional data, estimation rates depend on ambient dimension D, reflecting the curse of dimensionality for density-based procedures.This dependence can be unattractive in high-dimensional settings.
- 4.4 Analysis of Algorithm 2: the Trust Score: Under well-behaved class margins, large trust scores indicate likely agreement with the Bayes-optimal classifier, while small scores indicate likely disagreement.The guarantee predicts unreasonable classifier decisions rather than guaranteeing prediction of misclassification when the Bayes-optimal classifier itself has high error.
- 4.2 Analysis of Algorithm 1 on Manifolds: For data supported on an unknown d-dimensional manifold, rates depend on intrinsic dimension d rather than ambient dimension D without changing the procedure or knowing d.The result assumes manifold regularity and a density bounded below on the manifold.
- 4.3 Analysis of Algorithm 1 on Manifolds with Full Dimensional Noise: With full-dimensional noise around a low-dimensional manifold, estimation rates still depend only on the manifold dimension, not the dimension of the entire data.The method requires neither knowledge of the manifold nor its dimension to attain these rates.
5 Experiments
The experiments evaluate trust scores for identifying trustworthy and suspicious predictions across datasets, classifiers, accuracies, and representations. Trust scores generally outperform model confidence, especially on low- to mid-dimensional data, while gains diminish with higher classifier accuracy and can disappear in high-dimensional settings.
- Evaluation setup: The evaluation measures precision at each score percentile for identifying correctly classified and incorrectly classified test examples.Experiments compare trust score, model confidence, and the 1-nn ratio using repeated train/evaluation splits.
- UCI benchmarks: The trust score consistently achieves higher precision-versus-percentile curves than comparison methods across UCI datasets and classifier families.The authors interpret this as improved identification of trustworthy and suspicious examples for low-dimensional data.
- Varying model accuracy: As classifier accuracy increases, the trust score still outperforms model confidence, but the improvement diminishes.This suggests that trust scores provide less additional information when model confidence already reflects a stronger classifier.
- Representations: The representation used for distance computations matters, with more-processed neural-network layers generally performing better.The tested representations include logits and intermediate fully connected layers, including PCA-reduced features.
- Image benchmarks: For convolutional networks, trust-score utility may be little or no better than model confidence on high-dimensional datasets.The experiments vary neural-network layers and include a negative CIFAR-100 result in the Appendix.
- Overall findings: The experiments support the paper’s conclusion that trust scores consistently outperform classifier confidence in low- to mid-dimensional settings.The reported practical scope excludes a general claim of equal benefit in high-dimensional feature spaces.
A Supporting results for Theorem 1 Proof
The supporting results introduce empirical-ball convergence and k-nearest-neighbor density-estimation tools used to analyze the high-density-set procedure. Their bounds hold uniformly with high probability under suitable sample-size and neighborhood-size conditions.
- Uniform convergence: Uniform convergence of empirical balls provides simultaneous high-probability control over empirical and population ball probabilities.The stated result assumes k is at least logarithmic in n, up to dimension-dependent factors.
- Density estimation: The analysis uses a k-NN density estimator based on the distance from x to its k-th nearest sample point.The estimator is normalized by the sample size and the volume of a unit ball in the ambient dimension.
- Local regularity: One-sided density-continuity moduli quantify how much the density can increase or decrease locally.These moduli support upper and lower bounds for the k-NN density estimator.
- Probabilistic bounds: The k-NN density bounds hold uniformly over x and positive error levels with probability at least 1 −δ.The supporting lemmas provide the probabilistic control needed for later high-density-set guarantees.
B Proof of Theorem 1
The proof establishes consistency of the estimated α-high-density set by controlling its density level and geometric deviation from the true set. Under continuity, compact support, regularity, and an admissible k range, the estimation error converges as sample size grows.
- Regularity argument: The density level corresponding to α is shown to vary smoothly enough for level-set estimation errors to transfer to geometric errors.The argument uses local regularity and controls changes in the density threshold as α-level perturbations change.
- Threshold estimation: The estimated density threshold is bracketed between empirical level sets separated by an error term involving K(n, k, δ).This converts k-NN density-estimation error into inclusions for the estimated high-density set.
- Parameter conditions: The proof selects k within explicit lower and upper bounds to obtain the stated finite-sample guarantee.The admissible range depends on sample size, confidence, dimension, and the smoothness parameter.
- Geometric control: The proof controls both directions of Hausdorff error: recovered points remain near the true region, and the recovered set covers the true region.These two inclusions are handled through density-level-set bounds and empirical-ball arguments.
C Supporting results for Theorem 2 Proof
The supporting results adapt uniform-convergence and k-NN density-estimation bounds to data lying on a lower-dimensional manifold. The resulting guarantees use intrinsic dimension in the relevant concentration and estimation terms.
- Manifold convergence: The manifold analysis replaces ambient-dimensional ball control with a uniform convergence result over a finite covering of the manifold.The bound applies to sample points and covering points with probability at least 1 −δ.
- Density bounds: The upper and lower manifold density lemmas control local density increases and decreases uniformly over admissible points and error levels.Both results hold under lower bounds on k and with high probability.
D Proof of Theorem 2
The manifold extension develops density-estimation lemmas and establishes a high-probability admissible range for k under continuity, support, and lower-density assumptions.
- The manifold proof follows the full-dimensional structure, with the primary change occurring in the density-estimation bounds.
- The manifold lemmas support the theorem by adapting the relevant k-NN density-estimation arguments to the manifold setting.
- Under continuity, manifold support, Assumptions 1–2, and a positive density lower bound, Theorem 6 provides a high-probability guarantee.
- Theorem 6 requires k to lie between logarithmic lower and polynomial upper bounds determined by δ, n, d, and β′.
- The proof is omitted where it is stated to repeat the full-dimensional argument using the contributed lemmas.
E Supporting Results for Theorem 3 Proof
This section supplies geometric and empirical-process results needed to control probability mass and uniform convergence for balls intersecting the manifold.
- A ball-volume lemma bounds the intersection of a Euclidean ball with the manifold using the unit-ball volume and manifold-volume measure.
- A uniform-convergence lemma provides a probability-at-least-1−δ bound simultaneously over all balls and γ≥0.
F Proof of Theorem 3
Theorem 3 extends the analysis to a manifold distribution contaminated by full-dimensional noise, showing that the algorithm can isolate high-density manifold regions and retain controlled k-NN estimation error.
- Supporting lemmas compare density estimators and empirical manifold mass using ball-volume and uniform-convergence arguments.
- Algorithm 1 does not select points outside Heα−ω(fM) with probability at least 1−δ for sufficiently large n.
- Theorem 7 analyzes a mixture of manifold data and full-dimensional noise under continuity, manifold regularity, positive density, and mixture-weight assumptions.
- Theorem 7 uses the same logarithmic lower and polynomial upper bounds on k as the manifold theorem, with constants depending on fM, fE, η, and M.
- The filtering step removes noise points, reducing the analysis to the eα-high-density set of the manifold density.
- The entire-sample k-NN density estimator can estimate fM without knowing which samples lie on the manifold.
H.3 High dimensional Datasets
Figure 6 reports trust-score results for convolutional neural networks across MNIST, SVHN, CIFAR-10, and CIFAR-100, separating trustworthy and suspicious-example detection.
- The left column detects trustworthy examples, while the right column detects suspicious examples across four image datasets.