1 of 17

Improving Uncertainty Quantification of Deep Classifiers via Neighborhood Conformal Prediction: ​�Novel Algorithm and Theoretical Analysis​

Subhankar Ghosh*, Taha Belkhouja*, Yan Yan, Janardhan Rao Doppa​

​

School of EECS, Washington State University

2 of 17

Safety of deep model deployments

  • The need to capture the deviation of the prediction from the ground-truth output is important for critical decision-making

2

Example: Medical differential diagnosis

VS

Standard prediction:

Food allergy

Confident prediction set:

Good: {Food allergy, Food poisoning, Viral infection}

Better: {Food allergy, Food poisoning}

3 of 17

Uncertainty quantification

  •  

3

4 of 17

Conformal prediction for uncertainty quantification

  •  

4

 

 

 

5 of 17

Split Conformal Prediction

  •  

5

6 of 17

Motivation

  • Can we improve CP in terms of the trade-off between coverage and efficiency?

​

  • What are the necessary conditions for a reduced prediction set while achieving the target coverage?

6

7 of 17

Neighborhood Conformal Prediction

  •  

7

&

  • Key Idea:
      • Calibration examples in the local neighborhood of a given testing input have higher importance in the CP algorithm.

Test samples

Calibration samples

Importance

8 of 17

Neighborhood Conformal Prediction

  •  

8

Test samples

Calibration samples 1..n

 

VS

Standard CP

Neighborhood CP

9 of 17

Localizer and weighting function

  •  

9

Original distribution

 

Ball-based localizer over the learned representation

10 of 17

Localizer and weighting function

  • We employ k-nearest-neighbors and exponential weighting function

10

 

11 of 17

Importance of k-nearest-neighborhood

  • NCP produces significantly smaller predicted set sizes using a neighborhood based on k-nearest examples then NCP-All that uses all calibration examples.

11

Table 1: Algorithm performance according to the mean prediction set size

12 of 17

NCP theoretical guarantees

  •  

12

 

Theorem: As the assumptions are a key characterizations of the properties

of the learned representation, NCP gives smaller expected quantile (i.e., more efficient) to achieve the same target coverage as standard CP.

13 of 17

NCP theoretical guarantees

13

Theorem: As the assumption are a key characterizations of the properties of the learned representation, NCP gives smaller expected quantile (i.e., more efficient) to achieve the same target coverage as standard CP.

 

14 of 17

Empirical evaluation

  • NCP is a wrapper approach that can be used with any conformity scoring function
  • NCP is evaluated over prior CP methods for classification to demonstrate the increase in efficiency for achieving a target coverage of 90%
  • Metrics:
    • Empirical coverage
    • Efficiency (cardinality of prediction set for classification)

14

15 of 17

Empirical results

15

  • NCP significantly reduces the prediction set size (i.e., improves efficiency)
  • NCP as a wrapper algorithm further improves efficiency by using a better conformity scoring function such as RAPS

Table 2: Algorithm performance according to the mean prediction set size

16 of 17

Empirical results

16

  • NCP improves efficiency by further tightening the gap between actual coverage and the desired coverage (90%)

Table 3: Algorithm performance according to the empirical marginal coverage achieved

17 of 17

Summary

  • Improve uncertainty quantification of pre-trained deep classifiers using theoretical guarantees
  • Using the local neighborhood information to assign importance weights for conformal prediction calibration examples
  • Theoretical and empirical analysis to demonstrate the effectiveness of Neighborhood Conformal Prediction algorithm in enhancing the trade-off between coverage and efficiency
  • NCP is used as a wrapper over existing conformity scores to improve efficiency

17