Fine-Grained Uncertainty Quantification via Collisions

Technical Deep Dive: Fine-Grained Uncertainty Quantification via Collisions

Overview

The work proposes a novel approach for measuring aleatoric uncertainty in classification problems, called the collision matrix. The collision matrix provides a detailed, fine-grained description of the inherent difficulty in distinguishing between each pair of classes, going beyond coarser uncertainty metrics like the Bayes Error Rate (BER).

The key contributions are:

• Formal definition and analysis of the collision matrix, showing its relationship to the Probabilistic Bayes Classifier and the BER.
• A novel two-step method for estimating the collision matrix from one-hot labeled training data, leveraging the unique mathematical properties of the collision matrix.
• Demonstration that the collision matrix can be used to estimate the posterior class probability distributions for individual inputs, providing a way to quantify uncertainty at the instance level.
• Validation of the collision matrix estimation approach on both synthetic and real-world datasets, showing it outperforms baseline methods.

Problem & Context

• Machine learning classifiers are increasingly being applied in high-risk, high-uncertainty domains like healthcare, finance, and hiring.
• In these settings, it is important to not only identify the most likely class, but also understand the uncertainty involved in the prediction.
• This has led to growing interest in uncertainty quantification (UQ), which aims to describe the various types of uncertainty in a prediction task.

Methodology

Defining the Collision Matrix

• The class collision is defined as the event where the same input belongs to different classes when observed multiple times.
• The collision matrix $\mathbf{S}$ is a $K \times K$ row-stochastic matrix where $S_{i,j}$ represents the expected rate of class collisions between classes $i$ and $j$.
• The collision matrix can be interpreted as the expected confusion matrix of the Probabilistic Bayes Classifier, which samples its output from the true posterior class probabilities.
• The diagonal elements of $\mathbf{S}$ can be used to compute the Probabilistic Bayes Error Rate (PBER), a single-value uncertainty measure related to the Bayes Error Rate.

Estimating the Collision Matrix

• Baseline approaches for estimating $\mathbf{S}$ directly from one-hot labeled data are limited by the need to estimate the true posterior class probabilities.
• The authors propose a novel two-step method:
  1. Estimate the row Gramian matrix $\mathbf{G} = \mathbf{SS}^\top$ using a pair-wise contrastive model trained on the one-hot labeled data.
  2. Recover $\mathbf{S}$ from $\mathbf{G}$ by solving an optimization problem, leveraging the fact that $\mathbf{S}$ is strictly diagonally dominant under reasonable assumptions.

Estimating Posterior Distributions

• The authors show that the posterior class probability distribution $\mathbf{y}(\mathbf{x})$ can be expressed as a linear function of the collision matrix $\mathbf{S}$ and the expected similarity scores $\mathbf{q}(\mathbf{x})$ (also estimated using the pair-wise contrastive model).
• This allows them to provide a method for estimating $\mathbf{y}(\mathbf{x})$ from the estimated $\hat{\mathbf{S}}$ and $\hat{\mathbf{q}}(\mathbf{x})$.
• They also provide error bounds on the estimated posterior, showing the error is bounded by the errors in estimating $\mathbf{S}$ and $\mathbf{q}(\mathbf{x})$.

Data & Experimental Setup

Synthetic Data

• Gaussian mixture datasets with varying number of classes $K$ and class overlap (controlling the overall uncertainty).
• True collision matrices and posterior distributions can be computed exactly for these synthetic datasets.

Real-World Data

• MNIST dataset for image classification, where ambiguous digits can lead to class collisions.
• Four tabular datasets (Adult Income, Law School Success, Diabetes Prediction, German Credit) exhibiting potential for class collisions.

Results

Estimating the Collision Matrix

• On synthetic data, the authors' two-step Gramian-based method outperforms baseline approaches like calibrated classifiers, MC Dropout, and Bayesian neural networks.
• On MNIST, the estimated collision matrix aligns with intuitions about which digit pairs are most easily confused.
• On the real-world tabular datasets, the collision matrix provides insights into the inherent limitations of the data for classification, such as low precision but high recall for diabetes prediction.

Estimating Posterior Distributions

• On synthetic data, the authors' method exhibits lower average error and much lower variance in posterior estimates compared to baseline techniques.
• On MNIST, the estimated posteriors align with visual intuitions about ambiguous versus unambiguous digit images.

Interpretation

• The collision matrix provides a uniquely detailed description of the aleatoric uncertainty in a classification problem, going beyond coarse metrics like the BER.
• Estimating the collision matrix and using it to compute posterior distributions enables new applications:
  • Class Consolidation: Predicting how combining classes could affect classification difficulty.
  • Adaptive Sampling: Informing online changes to the training process to improve classifier performance.
  • Data-Driven Label Smoothing: Smoothing one-hot labels based on class similarities.

Limitations & Uncertainties

• The authors' estimation methods rely on the collision matrix having certain mathematical properties (strict diagonal dominance, symmetry with uniform priors), which may not hold for all real-world datasets.
• Validating the estimated posterior distributions is challenging, as the true posteriors are unknown for real-world datasets.
• The computational complexity of the collision matrix estimation is dominated by training the pair-wise contrastive model, which may be prohibitive for very large datasets.

What Comes Next

• Exploring relaxations of the assumptions required for the collision matrix estimation, to broaden the applicability to more diverse datasets.
• Investigating applications of the collision matrix beyond the ones presented, such as informing active learning strategies or guiding model architectures.
• Developing methods to efficiently estimate the collision matrix and posteriors for large-scale problems.