Hedging predictions in machine learning

1 Introduction

• Conformal predictors complement machine-learning predictions with measures of accuracy and reliability that are automatically valid under the assumption of randomness.The assumption requires objects and labels to be generated independently from the same probability distribution.Source: §1 · p. 2
• Validity is established for finite data sequences rather than through asymptotic arguments.The paper formalizes validity in Sections 3 and 5 and examines both online and batch settings.Source: §1 · pp. 2–3
• Efficiency becomes the central design goal because virtually any classification or regression algorithm can be transformed into a conformal predictor.This allows methods such as support vector machines, nearest neighbours, and ridge regression to support hedged prediction.Source: §1 · pp. 2–3
• The paper develops computable approximations to an ideal universal predictor based on Kolmogorov’s algorithmic theory of randomness.The universal predictor gives the best possible hedged predictions but is noncomputable.Source: §1 · p. 2
• When the stochastic model is correct, an optimal conformal predictor is nearly as good as the Bayes-optimal confidence predictor; when it is wrong, conformal validity remains but efficiency suffers.The Bayes-optimal predictor can instead produce misleading results under model deviation.Source: §1 · p. 3
• Conformal predictors are transductive, while combining transduction with induction can improve computational efficiency.The paper also describes underlying machine-learning algorithms used to hedge predictions and aims to make the techniques practically applicable.Source: §1 · p. 3

2 Ideal hedged predictions

• Hedged prediction seeks the best possible trade-off between prediction accuracy and reliability for classification and regression.Classification complements a predicted label with reliability, whereas regression uses measures of accuracy and reliability.Source: §2 · p. 4

Prediction with Confidence and Credibility

• The ideal classification procedure tests every candidate label by appending it to the training sequence and retaining labels whose completions conform to randomness.The most random completion supplies the prediction, while confidence and credibility are derived from the largest and second-largest randomness levels.Source: §2 · p. 4, Prediction with Confidence and… · p. 5
• At a 99% confidence level, a wrong prediction can occur only when the data sequence lies in a preselected set with probability at most 1%.Low credibility indicates either a non-random training set or a test object that is not representative of the training data.Source: Prediction with Confidence and… · pp. 5–6

Confidence Predictors

• Regression uses nested prediction sets Γ_ε whose error probability is at most ε at each confidence level.Higher confidence generally requires larger sets, creating the paper’s accuracy–reliability trade-off.Source: Confidence Predictors · p. 6
• A randomness test yields a valid confidence predictor by including candidate labels whose detected randomness level exceeds ε.The resulting sets can be viewed at multiple confidence levels, such as 80%, 95%, and 99%.Source: Confidence Predictors · pp. 6–7
• The universal confidence predictor is theoretically useful but noncomputable, so practical methods must approximate it.This computational limitation motivates the later development of computable conformal predictors.Source: Confidence Predictors · p. 7

3 Conformal Prediction

• Support vector machines assign strangeness scores through their Lagrange multipliers, with positive values identifying support vectors and larger values indicating outliers.For a candidate test label, its p-value is the proportion of scores at least as large as the candidate's score.Source: §3 · p. 7
• High confidence excludes alternative labels, while low credibility flags a suspect test situation such as an unusual or out-of-distribution object.A prediction is described as trustworthy when confidence is close to 100% and credibility is not low; under the randomness assumption, credibility is low with probability at most ε for threshold ε.Source: §3 · pp. 8–9
• Nearest-neighbour nonconformity compares distances to same-label and different-label examples, so larger scores indicate greater strangeness.The construction can use distances in a feature space, including a Hilbert space for kernel nearest neighbours.Source: §3 · p. 9
• 99% confidence was achieved for more than 95% of USPS test examples using 1-nearest neighbours, whose underlying error rate was 2.2%.The result illustrates that hedged-prediction accuracy and reliability can track the underlying algorithm's error rate.Source: §3 · p. 9

General Definition

• Conformal predictors transform prediction algorithms into hedged predictions by converting nonconformity scores into p-values and prediction sets.The general construction applies to classification and regression, with prediction sets defined by candidate labels whose p-values exceed the chosen threshold.Source: §3 · p. 7, General Definition · pp. 9–10

Computationally Efficient Regression

• Regression cannot directly enumerate all candidate labels because the possible values are infinite, but residual-based scores can yield efficiently computable prediction sets.This idea underlies the ridge regression confidence machine and its kernel ridge regression variant.Source: Computationally Efficient Regression · p. 10

Ridge regression confidence machine

• The ridge regression confidence machine applies ridge regression under a Gaussian linear model and converts residuals into convex-hull prediction intervals.The model uses independent standard Gaussian noise and a Gaussian weight vector with covariance (1/a)I_p.Source: §4 · p. 11

Experimental design

• Experiments generated 10 weight vectors, 100 training objects, and 100 test objects per vector in R^5, with labels formed by a linear signal plus Gaussian noise.The ridge method used parameter a = 1, matching the data-generating mechanism in the validity experiment.Source: §4 · p. 11

Evaluation

• Efficiency was measured by the mean width of prediction intervals across test examples at each confidence level.Narrower prediction intervals indicate greater efficiency.Source: §4 · p. 11

Bayes-optimal predictor

• The Bayes-optimal predictor directly uses the conditional Gaussian label distribution to produce the shortest interval with probability 1 − ε.Its validity and efficiency are shown in Figures 4 and 5.Source: §4 · pp. 11, 13, Figure 4 · p. 13, Figure 5 · p. 14

Bayesian comparison

• With correct parameter a, the ridge regression confidence machine appears as good as the Bayes-optimal confidence predictor in efficiency.The comparison is based on the similarity of the solid lines in Figures 3 and 5.Source: Figure 3 · p. 12, §4 · p. 13, Figure 5 · p. 14

Robustness to misspecification

• When a is misspecified, the ridge regression confidence machine remains valid but its efficiency deteriorates, whereas the Bayes-optimal predictor becomes invalid.For a = 10000, only about 15% of labels fall within the Bayes-optimal predictor’s 90% prediction sets.Source: Figure 2 · p. 12, Figure 3 · p. 12, §4 · p. 13

5 On-line prediction

• In the on-line protocol, each prediction is a nested family of sets based on previous labeled examples, followed by immediate feedback of the true label.The protocol presents examples sequentially and updates predictions as more labeled examples accumulate.Source: §5 · pp. 14–15

Theoretical Analysis

• Ordinary conformal predictors are conservatively well calibrated, while cumulative error, multiple-set, and empty-set counts provide on-line validity and efficiency measures.The protocol records Err, Mult, and Emp at each confidence level; smoothed predictors are well calibrated and conformal predictors inherit a weaker guarantee.Source: §5 · p. 15, Theoretical Analysis · p. 18

5 On-line prediction

• At confidence levels 80%, 95%, and 99%, cumulative errors grow approximately linearly with slopes of 20%, 5%, and 1%, respectively.These slopes correspond to the tolerated error probability ǫ and are observed for a 1-nearest neighbour conformal predictor on USPS data.Source: §5 · p. 15, Figure 6 · p. 16
• At 97.5% confidence, approximately 250 of 10,000 predictions were errors and approximately 300 were multiple predictions.The multiple-prediction rate was approximately 3%, alongside the approximately 2.5% error rate.Source: §5 · p. 15, Figure 7 · p. 16
• Choosing ǫ controls errors but trades off multiple and empty prediction sets, with empty sets warning that an object is unusual.Changing the confidence level can remove labels from prediction sets; an empty set indicates credibility ǫ or less.Source: §5 · p. 17

Theoretical Analysis

• For smoothed conformal predictors, independent errors occur with probability ǫ at any confidence level 1 −ǫ when examples are independently generated from the same distribution.This is the strongest on-line validity property stated in the theoretical analysis.Source: Theoretical Analysis · p. 18

6 Slow teachers, lazy teachers, and the batch setting

• Immediate feedback gives the strongest validity guarantee, whereas weaker teachers require validity in the sense of convergence in probability.Slow and lazy teachers are modeled by feedback at selected later steps using previously seen objects.Source: §6 · p. 19
• Conformal predictors remain valid with delayed or sparse teacher feedback if and only if n_k/n_{k−1} → 1, equivalently when feedback growth is subexponential.This condition includes feedback provided for every tenth object.Source: §6 · p. 19
• The batch setting has a finite horizon with no labels returned after the training phase, and experiments show that approximate validity still holds.The batch protocol predicts labels for a fixed test set from a training set.Source: §6 · p. 19

7 Induction and transduction

• Induction constructs and stores a general prediction rule before applying it, whereas transduction moves directly from old examples to a prediction for the new object.The practical distinction for ordinary prediction concerns whether a general rule is explicitly extracted and stored.Source: §7 · pp. 20–21
• The paper’s approach is thoroughly transductive, which it identifies as enabling valid and efficient hedged prediction while still allowing an inductive component.Nearest-neighbours methods are given as examples of transductive prediction.Source: §7 · p. 20
• Hedged inductive results typically use accuracy ǫ and confidence δ, whereas transductive results use ǫ as the tolerated error probability.The two frameworks therefore attach different meanings and numbers of parameters to hedged prediction.Source: §7 · p. 21

8 Inductive conformal predictors

• Inductive conformal predictors split the data into proper training and calibration sets, construct a rule, score calibration examples, and form test prediction sets from those scores.For each test object and candidate label, the procedure computes a nonconformity score and compares it with calibration scores.Source: §8 · p. 21
• Their p-values can be packaged in classification as prediction sets or as a prediction with confidence and credibility.The construction applies the prediction-set definition after computing nonconformity rankings.Source: §8 · p. 22
• Inductive conformal predictors are valid because their probability of error never exceeds ǫ for test examples and confidence levels in the stated ranges.The corresponding on-line version has a stronger validity notion.Source: §8 · p. 22
• Their main computational advantage is that most computation is performed once, leaving only prediction, scoring, and calibration-rank operations for each test example.This avoids solving essentially independent optimization problems for every test object and potential label.Source: §8 · pp. 21–22
• The computational gain can reduce prediction efficiency because conformal predictors can use the whole training set for both proper training and calibration.Inductive conformal predictors reserve part of the data for calibration rather than fitting on all available examples.Source: §8 · p. 22

• Choosing an appropriate confidence level enables control of the number of errors made by hedged predictions.Source: §9 · p. 22