Fine-Grained Uncertainty Quantification via Collisions

1. Problem Statement

Machine learning classifiers are increasingly deployed in high-stakes domains (healthcare, finance, hiring) where aleatoric uncertainty (inherent noise in the data distribution) is significant. Existing Uncertainty Quantification (UQ) methods often suffer from limitations:

• Lack of Granularity: Metrics like the Bayes Error Rate (BER) provide a single scalar value representing the total uncertainty of a dataset but fail to identify which specific classes are difficult to distinguish.
• Classifier Dependence: Many methods (e.g., cross-validation accuracy, confusion matrices) measure the performance of a specific classifier rather than the inherent uncertainty of the data distribution itself.
• Posterior Estimation Difficulty: Estimating the true posterior class probability distribution $P(c|x)$ is challenging because training data is typically "one-hot" labeled (indicating only the observed class), lacking information about alternative probable classes.

The authors propose a new framework to quantify aleatoric uncertainty at a fine-grained, pairwise level and use this to estimate posterior distributions without requiring ground-truth posteriors during training.

2. Core Methodology

A. The Collision Matrix ($S$)

The central contribution is the definition of Class Collisions and the Collision Matrix.

• Definition: A class collision occurs when the same input feature vector $x$ is observed multiple times but belongs to different classes ($c \neq \tilde{c}$).
• The Matrix: For a $K$-class problem, the collision matrix $S$ is a $K \times K$ row-stochastic matrix where the entry $S_{i,j}$ represents the probability that an input drawn from class $i$'s distribution will be observed as class $j$.
  $$S_{i,j} = \mathbb{E}_{x \sim D_i} [P(c=j|x)]$$
• Interpretation:
  • $S_{i,j}$ measures the inherent difficulty of distinguishing class $i$ from class $j$.
  • The diagonal $S_{i,i}$ represents the probability of correct classification for class $i$.
  • The off-diagonal elements quantify the "similarity" or confusion between specific pairs of classes.
• Relation to BER: The collision matrix generalizes the Bayes Error Rate. The Probabilistic Bayes Error Rate (PBER) can be derived directly from $S$ and the class priors $\pi$: $PBER = 1 - \sum \pi_k S_{k,k}$.

B. Estimating the Collision Matrix (Two-Step Approach)

Since true posteriors $P(c|x)$ are unknown in standard one-hot labeled data, the authors propose a novel estimation method that avoids direct posterior estimation:

1. Step 1: Estimate the Row Gramian ($G$)

   • The authors define the row Gramian matrix $G = S S^T$.
   • They prove that under reasonable assumptions (non-negativity, symmetry for uniform priors, and strict diagonal dominance), $S$ is uniquely recoverable from $G$.
   • To estimate $G$, they introduce a Pair-Wise Contrastive Model ($V$). This model takes two inputs $(x, \tilde{x})$ and outputs the probability that they belong to the same class: $V(x, \tilde{x}) \approx P(c = \tilde{c} | x, \tilde{x})$.
   • The entries of $G$ are estimated by averaging the outputs of $V$ over pairs of data points from different classes:
     $$\hat{G}_{i,j} \approx \frac{1}{|T_i||T_j|} \sum_{x \in T_i} \sum_{\tilde{x} \in T_j} V(x, \tilde{x})$$

2. Step 2: Recover $S$ from $G$

   • Using the theoretical guarantee of uniqueness, the authors solve an optimization problem to find the matrix $\hat{S}$ that minimizes $\|\hat{S}\hat{S}^T - \hat{G}\|_F$ subject to constraints (stochasticity, non-negativity, diagonal dominance).

C. Estimating Posterior Distributions

Once $S$ is estimated, the authors show how to recover the posterior distribution $y(x)$ for any new input $x$:

1. Compute the Expected Similarity Score vector $q(x)$, where $q_i(x)$ is the expected similarity between $x$ and samples from class $i$ (estimated using the same contrastive model $V$).
2. Establish the linear relationship: $q(x) = S y(x)$.
3. Solve for the posterior: $y(x) = S^{-1} q(x)$.

This allows the conversion of similarity scores into calibrated probability distributions using only one-hot labeled training data.

3. Key Contributions

1. New Metric (Collision Matrix): Introduced a fine-grained, distribution-level metric that quantifies uncertainty between every pair of classes, offering more detail than scalar metrics like BER.
2. Theoretical Uniqueness: Proved that for strictly diagonally dominant, non-negative symmetric matrices, the collision matrix $S$ is uniquely determined by its row Gramian $G$. This is a novel result in matrix theory.
3. Novel Estimation Algorithm: Developed a two-step algorithm using a Pair-Wise Contrastive Model to estimate $S$ without needing ground-truth posteriors. This bypasses the "overconfidence" issues of standard classifiers.
4. Posterior Recovery: Demonstrated a method to estimate the full posterior class probability distribution $P(c|x)$ for individual inputs using the estimated collision matrix and similarity scores.
5. Practical Applications: Identified applications such as Class Consolidation (merging confusing classes), Adaptive Sampling, Data-Driven Label Smoothing, and Risk Assessment in high-stakes decisions.

4. Experimental Results

The authors validated their methods on both synthetic Gaussian mixture datasets and real-world datasets (MNIST, Adult Income, Law School Success, Diabetes Prediction, German Credit).

• Estimating $S$:
  • The proposed Gramian-based method (Algorithm 1) consistently outperformed baselines (Calibrated Classifiers, MC Dropout, Bayesian Neural Networks) in terms of Total Variation Distance (TVD) to the ground-truth collision matrix.
  • It was particularly robust in scenarios with varying class overlaps and numbers of classes.
  • MNIST Validation: The estimated collision matrix correctly identified high uncertainty between visually similar digits (e.g., 3 vs. 5, 4 vs. 9), matching human intuition.
• Estimating Posteriors:
  • On synthetic data, the proposed method produced posterior estimates with lower average TVD and significantly lower variance across runs compared to baselines.
  • On MNIST, the method successfully assigned probability mass to the most plausible alternative classes for ambiguous digits (e.g., splitting probability between '0' and '8' for a blurry image), whereas standard classifiers often remained overconfident in a single class.
• Real-World Insights:
  • Applied to tabular data, the collision matrix revealed specific, unavoidable limitations in datasets. For example, in the Diabetes dataset, the matrix showed that while recall could be high (identifying risk), precision would inherently be low due to data ambiguity, suggesting that better features are needed rather than better models.

5. Significance and Impact

• Shift in Perspective: Moves UQ from a "black box" scalar metric to a structured, interpretable matrix that reveals the specific geometry of class confusion.
• Data-Centric Uncertainty: By defining uncertainty as a property of the data distribution (independent of the classifier), it provides a "gold standard" for evaluating how much a dataset can theoretically support a classification task.
• Practical Utility: The ability to estimate posteriors from one-hot data without complex Bayesian ensembles or calibration techniques makes advanced uncertainty quantification more accessible and computationally efficient.
• Decision Support: The fine-grained nature of $S$ allows stakeholders to understand why a prediction is uncertain (e.g., "Class A is hard to distinguish from Class B, but not Class C"), enabling better risk management in critical fields like healthcare and finance.