PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimized conformal classification using gradient descent approximation

Anthony Bellotti

arXiv:2105.11255v1cs.LG

TL;DR

Conventional conformal predictors inherit an underlying model’s objective, which may not align with prediction-set efficiency. This paper approximates inductive conformal classification with a differentiable objective optimized by gradient descent; preliminary experiments report improved efficiency in most cases.

  • Problem

    Conformal predictors built on underlying machine-learning models may be sub-optimal for prediction-set efficiency because those models are not trained to optimize that objective.

    Source: §1 · p. 4

  • Method

    The paper approximates inductive conformal classification with a differentiable objective and uses gradient descent to optimize its parameters before passing them to a proper conformal predictor.

    Source: §1 · pp. 4–5

  • Results

    Preliminary experiments on five real-world classification problems reduced prediction-set inefficiency relative to classical ICP in most cases.

    Source: §4 · p. 19

  • Takeaways & Limitations

    Different confidence levels generally require distinct parameter estimates, so one conformity measure may not work well at every level for a given problem.

    Source: §4 · p. 19

    The proof of concept uses a linear conformity measure, and extension to more complex structures such as neural networks requires further research.

    Source: §4 · p. 19

Abstract

from arXiv · show

Conformal predictors are an important class of algorithms that allow predictions to be made with a user-defined confidence level. They are able to do this by outputting prediction sets, rather than simple point predictions. The conformal predictor is valid in the sense that the accuracy of its predictions is guaranteed to meet the confidence level, only assuming exchangeability in the data. Since accuracy is guaranteed, the performance of a conformal predictor is measured through the efficiency of the prediction sets. Typically, a conformal predictor is built on an underlying machine learning algorithm and hence its predictive power is inherited from this algorithm. However, since the underlying machine learning algorithm is not trained with the objective of minimizing predictive efficiency it means that the resulting conformal predictor may be sub-optimal and not aligned sufficiently to this objective. Hence, in this study we consider an approach to train the conformal predictor directly with maximum predictive efficiency as the optimization objective, and we focus specifically on the inductive conformal predictor for classification. To do this, the conformal predictor is approximated by a differentiable objective function and gradient descent used to optimize it. The resulting parameter estimates are then passed to a proper inductive conformal predictor to give valid prediction sets. We test the method on several real world data sets and find that the method is promising and in most cases gives improved predictive efficiency against a baseline conformal predictor.

1 Introduction

Conformal predictors provide confidence-controlled prediction sets, so their efficiency depends on how informative those sets are. Because conventional predictors inherit an underlying model’s objective, this introduction motivates directly optimizing efficiency and presents SCPO for inductive conformal classification.

1 Introduction

  • Conformal predictors output sets rather than point predictions, with validity guaranteed at a user-defined confidence level under exchangeability.A medical prediction set can narrow the diagnoses a doctor explores further.Source: §1 · p. 2
  • Prediction-set size is used as an inefficiency measure because it is directly observable in practice; smaller sets are generally more informative.The study also considers log prediction-set size to demonstrate the method with another performance measure.Source: §1 · pp. 3–4
  • SCPO approximates the conformal-prediction objective with a differentiable function for gradient descent, targeting efficiency rather than the underlying model’s objective.The paper hypothesizes that this close approximation can yield more efficient solutions than a classical predictor built on a machine-learning model.Source: §1 · p. 4
  • SCPO is only an approximation and is not inherently valid, but its estimated parameters are passed to a valid conformal predictor.The approximation may still be sub-optimal.Source: §1 · p. 5
  • Because the N criterion depends on confidence level, the paper investigates whether different confidence levels require different optimized predictors.Higher confidence generally increases prediction-set size, and a separate optimization problem is needed for each chosen level.Source: §1 · p. 5
  • The study focuses on inductive conformal predictors for classification with finite labels, a distinct setting from conformal regression.The authors identify inductive predictors as the most popular form for batch machine learning.Source: §1 · p. 5
  • In most cases, SCPO improves ICP performance, while optimized predictors differ across confidence levels and inefficiency measures.The article evaluates a linear model structure across several classification problems.Source: §1 · p. 5

2 Methodology

The methodology directly optimizes a parameterized exchangeable conformity measure using an approximate loss for prediction-set inefficiency and validity. It demonstrates the approach with a linear multiclass measure and evaluates it against multinomial logistic regression ICP.

2 Methodology

  • SCPO minimizes a parametric, exchangeable conformity measure’s prediction-set inefficiency directly, without requiring an underlying classification algorithm.The parameterized conformity measure is computed from the training data through an exchangeable model structure.Source: §2 · pp. 6–7
  • Its training loss minimizes mean set-size inefficiency while approximately enforcing the target confidence-level coverage on training data.The quantile q may be optimized as an approximate ε-quantile, or fixed by rescaling the conformity measure when it can change scale.Source: §2 · pp. 8–9
  • Gradient descent uses sigmoid approximations for indicator terms, while λ balances objective components and larger λ and γ make SCPO closer to ICP but harder to optimize.The study also explores loss transformations because the raw objective can have extreme values and flat plateaus.Source: §2 · pp. 8–10

2.1 Multiclass Linear Conformity Measure

  • The proof-of-concept conformity measure is multiclass linear, with class-specific parameter vectors; rescaling all parameters permits q=1.In the two-variable illustration, class-specific threshold lines partition the plane into regions corresponding to different prediction sets.Source: §2.1 · pp. 10–11, Figure 1 · p. 11

2.2 Performance measures

  • Performance is measured by test accuracy and mean inefficiency, comparing identity and log set-size costs against multinomial-logistic-regression ICP.The identity cost reflects set size directly; the log cost represents applications where the cost of increasing set size may diminish as sets grow.Source: §2.2 · p. 12

3 Experiments

The experiments evaluate SCPO-ICP across classification data sets and settings. SCPO-ICP improves inefficiency over baseline ICP in most cases, while test accuracy remains close to the confidence level.

3.1 Data sets

  • The experiments use seven classification data sets, each with more than 1,000 observations; wine and polish are binary, while the others are multiclass.None of the data sets as used has extreme majority-class imbalance, which the authors identify as a consideration for conformal prediction.Source: §3.1 · pp. 13–14

3.2 Experimental set up

  • Hyperparameters are selected by grid search for each significance level, using training-data loss; final ICP uses independent calibration and test sets.The internal grid-search ICP is not valid because it reuses training data for calibration and testing, but the authors state that the final independent-data ICP is valid.Source: §3.2 · pp. 14–15

3.3 Results

  • Across seven data sets, L(θ) never gives the best performance; log L(θ) does so for two, −L(θ)−1 for four, and −L(θ)−2 for one.The transformations are evaluated with separate hyperparameter searches; Table 3 shows two example data sets at ε = 0.05 using f(w) = w.Source: §3.3 · p. 16, Table 3 · p. 17
  • SCPO-ICP improves inefficiency over baseline ICP in most cases, while test accuracy approximates the confidence level across all cases.The method is not universally successful: covtype performs up to 5.1% worse than baseline at 99% confidence, and mice has a 4.1% worse result at 80% confidence for f(w) = w.Source: §3.3 · p. 17
  • Large improvements are reported for avila, wine, and polish under both inefficiency measures, and for mice at high confidence levels.For covtype, the authors attribute missed improvement to an insufficient SCPO approximation and/or gradient descent not finding the available optimum, with gradient descent considered the likelier issue.Source: §3.3 · p. 18
  • Training the conformity measure at 80% confidence typically gives worse inefficiency at 95% than training at the target confidence; wine is the exception.This suggests that different confidence levels typically require different conformity-measure parameterizations.Source: §3.3 · p. 18

4 Conclusion

SCPO approximates the inductive conformal predictor with a differentiable objective and improves predictive efficiency in most tested cases. The study uses a linear conformity measure as proof of concept and identifies extensions to the model and optimization procedure as future work.

4 Conclusion

  • SCPO showed best results on 4 of 5 real-world classification datasets, while covtype showed no performance improvement over the classical ICP baseline.The authors attribute the covtype result to a possible limitation of the current optimization algorithm.Source: §4 · p. 19
  • The experiments used a simple grid search and constant-learning-rate gradient descent, motivating study of random starting positions and adaptive learning rates.Source: §4 · p. 19
  • Different confidence levels generally require distinct parameter estimates, so no single conformity measure works well at every level for a given problem.Source: §4 · p. 19
  • The study uses a linear conformity measure as proof of concept; extending SCPO to more complex gradient-estimable structures, such as neural networks, remains future work.Source: §4 · p. 19

A Matrix notation

The matrix notation organizes training observations, labels, conformity scores, and parameters, then expresses their derivatives for gradient computation.

A Matrix notation

  • The notation defines derivatives of α_i and s_i with respect to θ, then combines them into gradients for V, L(θ), and log L(θ).The observations indexed i ∈ 1,…,k are training data.Source: A Matrix notation · p. 20
  • Training data are represented by predictor matrix X, label vector Y, parameter vector θ, and a matrix A of conformity scores across candidate labels.A is computed from X and θ, with one column for each label; α_i selects the score for the observed label Y_i.Source: A Matrix notation · p. 20
  • For the multi-class linear NCM, the parameter count is p = Cm, with parameters arranged in an m × C matrix T.The notation also defines A′[i] as the derivative of candidate-label scores for observation i and specifies element-wise multiplication.Source: A Matrix notation · pp. 20–21
Loading 2105.11255v1…