Knowing what you know: valid confidence sets in multiclass and multilabel prediction

Maxime Cauchois, Suyash Gupta, John C. DuchiarXiv 2020 · OpenReview

TL;DR

This paper introduces novel methods for creating "confidence sets" in machine learning predictions, ensuring that the true outcome is included with a guaranteed probability. Unlike previous approaches that might be unreliable on difficult examples, their methods provide more robust and (asymptotically) conditional coverage, crucial for high-stakes applications. They also tackle the computational challenge of multilabel prediction by using efficient tree-structured models.

What Problem Does This Paper Address?

In machine learning, simply predicting the most likely outcome isn't enough for critical applications like autonomous driving or medical diagnosis. We need to know how confident the model is in its prediction. This is where "confidence sets" come in: they are a range of possible outcomes that the true outcome is guaranteed to fall within with a certain probability (e.g., 90%). The challenge is that existing methods, particularly "conformal prediction," often provide marginal coverage, meaning the guarantee holds on average but can fail significantly on specific, harder examples. This paper addresses the need for more reliable, conditional coverage, especially in complex scenarios like multiclass (one label out of many) and multilabel (multiple labels possible) prediction, where existing methods struggle with uneven performance and computational complexity.

Methods

The core contribution is the development of Conformalized Quantile Classification (CQC) for multiclass problems and its extension to Conformalized Inner/Outer Classification (CQioC) for multilabel problems.

  • CQC (Multiclass): This method builds upon conformal prediction by fitting a quantile function to the model's prediction scores. This allows it to adapt to data heterogeneity and provide better conditional coverage than standard methods, while still guaranteeing marginal validity. It's designed to be a "bolt-on" solution that can be applied to any existing classification model.
  • CQioC (Multilabel): This extends CQC to the multilabel setting, where an example can have multiple labels. The challenge here is the exponential growth of possible label combinations. The authors propose using "inner" and "outer" sets to efficiently represent confidence sets. They introduce two main strategies:
  • A generic split-conformal method that directly fits inner and outer sets.
  • Methods that leverage tree-structured graphical models to efficiently model label correlations and compute scores. This includes constructing scores from arbitrary predictors or from individual task scores.

A key innovation is the use of randomization to achieve nearly perfectly calibrated coverage and the development of new validation methodologies (e.g., worst-slab coverage) to better assess conditional coverage.

Datasets

  • Simulated Datasets: Used to demonstrate the theoretical properties of the methods, including a Gaussian mixture model for multiclass and a logistic model with hidden confounders for multilabel.
  • Real Datasets:
    • CIFAR-10: A standard benchmark for image classification.
  • ImageNet: A large-scale hierarchical image database.
  • PASCAL VOC 2007 and VOC 2012: Datasets for multilabel image recognition.

Key Insights and Ideas

  • Quantile Regression is Key for Conditional Coverage: By fitting a quantile function to prediction scores, we can adapt to local data characteristics and achieve better conditional coverage, not just average coverage.
  • Multilabel Complexity Demands Structure: The exponential number of label combinations in multilabel problems necessitates efficient representations like inner/outer sets and leveraging label correlations via tree-structured models.
  • "Bolt-on" Conformalization is Powerful: The proposed methods can be applied to any pre-trained classifier, offering a way to add guaranteed validity without retraining from scratch.
  • New Validation Metrics are Necessary: Standard marginal coverage isn't sufficient. Metrics like "worst-slab coverage" are crucial for evaluating how well methods perform across different subsets of the data.
  • Randomization Improves Calibration: Introducing controlled noise can lead to nearly perfect conditional coverage, a significant step beyond traditional conformal methods.

Key Results

  • Improved Conditional Coverage: Experiments show that CQC and its tree-based extensions provide significantly more robust conditional coverage than standard marginal conformal methods, especially on minority classes or challenging data regions.
  • Competitive Confidence Set Sizes: Despite offering better coverage, the proposed methods generally produce confidence sets comparable in size to simpler methods, particularly when using tree-structured scores.
  • Effective Multilabel Handling: Tree-based methods for multilabel prediction (PGM-CQC) demonstrate superior worst-slab coverage compared to direct methods, effectively leveraging label dependencies.
  • Theoretical Guarantees: The paper provides theoretical guarantees for marginal validity and asymptotic conditional coverage under appropriate assumptions.

Limitations and Future Work

  • Asymptotic Optimality: While the methods are asymptotically optimal for conditional coverage, finite-sample performance can still be conservative or exhibit some variability.
  • Assumption of Exchangeability: The theoretical guarantees rely on exchangeability of data, which might not always hold in practice.
  • Computational Cost: While tree-structured methods improve efficiency, complex models or large numbers of labels can still pose computational challenges.
  • Future Work: The authors suggest exploring distributionally robust optimization and uniform convergence arguments for more uniform notions of validity. They also highlight the potential for further improvements by developing more sophisticated tree-structured score functions and exploring new ways to construct confidence sets.

Summary updated

Abstract

We develop conformal prediction methods for constructing valid predictive confidence sets in multiclass and multilabel problems without assumptions on the data generating distribution. A challenge here is that typical conformal prediction methods---which give marginal validity (coverage) guarantees---provide uneven coverage, in that they address easy examples at the expense of essentially ignoring difficult examples. By leveraging ideas from quantile regression, we build methods that always guarantee correct coverage but additionally provide (asymptotically optimal) conditional coverage for both multiclass and multilabel prediction problems. To address the potential challenge of exponentially large confidence sets in multilabel prediction, we build tree-structured classifiers that efficiently account for interactions between labels. Our methods can be bolted on top of any classification model---neural network, random forest, boosted tree---to guarantee its validity. We also provide an empirical evaluation, simultaneously providing new validation methods, that suggests the more robust coverage of our confidence sets.
BibTeX
@misc{cauchois2020knowing,
  author = {Maxime Cauchois and Suyash Gupta and John C. Duchi},
  title = {{Knowing what you know: valid confidence sets in multiclass and multilabel prediction}},
  year = {2020},
  eprint = {2004.10181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.10181},
}
Figure