Source-linked AI summary
Regression Conformal Prediction with Nearest Neighbours
Harris Papadopoulos, Vladimir Vovk, Alex Gammerman
TL;DR
Traditional regression methods provide point predictions without confidence information, while predictive-region usefulness depends on the nonconformity measure. This paper develops transductive and inductive k-NNR Conformal Predictors with six novel measures, which generally produce tighter regions, with definitions (31) and (32) strongest for ICP.
Problem
Traditional machine-learning predictions lack confidence information, and conformal predictive-region tightness depends on the chosen regression nonconformity measure.
Method
The paper develops transductive and inductive Conformal Predictors for k-NNR using six measures normalized by expected local prediction accuracy.
Results
The new measures produce tighter predictive regions in general, with definitions (31) and (32) appearing to give the overall tightest ICP regions.
Takeaways & Limitations
The methods produce reliable predictive intervals useful in practice, and their regions are almost as tight as GPR regions when the correct prior is known.
Takeaways & Limitations
Not all six new measures can be used with TCP, although all can be used with ICP.
Abstract
from arXiv · showhide
In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours Regression (k-NNR) algorithm and propose ways of extending the typical nonconformity measure used for regression so far. Unlike traditional regression methods which produce point predictions, Conformal Predictors output predictive regions that satisfy a given confidence level. The regions produced by any Conformal Predictor are automatically valid, however their tightness and therefore usefulness depends on the nonconformity measure used by each CP. In effect a nonconformity measure evaluates how strange a given example is compared to a set of other examples based on some traditional machine learning algorithm. We define six novel nonconformity measures based on the k-Nearest Neighbours Regression algorithm and develop the corresponding CPs following both the original (transductive) and the inductive CP approaches. A comparison of the predictive regions produced by our measures with those of the typical regression measure suggests that a major improvement in terms of predictive region tightness is achieved by the new measures.
1. Introduction
Traditional machine-learning predictions lack confidence information needed in risk-sensitive applications. The paper applies Conformal Prediction to k-NNR and introduces normalized nonconformity measures intended to produce tighter predictive regions through both transductive and inductive approaches.
- Traditional machine-learning algorithms output point predictions without confidence information, limiting their suitability for risk-sensitive applications such as medical diagnosis.
- Conformal Predictors add valid confidence measures to traditional algorithms under the i.i.d. assumption without requiring distributional assumptions beyond i.i.d.
- The original transductive approach is computationally inefficient because it recomputes all calculations for every test example.
- Inductive Conformal Prediction trains the underlying algorithm once, improving computational efficiency at a small loss in confidence-measure quality.
- Regression Conformal Predictors output predictive regions satisfying a given confidence level rather than conventional point predictions.
- The paper develops six k-NNR-based extensions to the absolute-error nonconformity measure and corresponding transductive and inductive predictors.
2. Conformal Prediction
Conformal Prediction evaluates candidate labels by comparing their nonconformity with that of examples in an augmented data set. Labels whose p-values exceed the chosen significance threshold form a predictive region with guaranteed validity, while the measure affects tightness.
- Conformal Prediction assumes i.i.d. labeled examples and evaluates confidence for candidate labels of a new unlabeled example.
- A nonconformity measure assigns each example a numerical score indicating its difference from the remaining examples.
- For each candidate label, the method augments the known data, computes nonconformity scores, and compares the candidate score with the others.
- The p-value p(ỹ) equals the fraction of scores at least as large as the candidate score and ranges from 1/(l+1) to 1.
- At confidence level 1−δ, a regression conformal predictor retains labels with p-values greater than δ as its predictive region.
- Validity holds for any algorithm or nonconformity measure, whereas their choice affects predictive-region tightness and usefulness.
3. k-Nearest Neighbours Regression TCP
The transductive k-NNR Conformal Predictor represents nonconformity scores as functions of a candidate label and computes the predictive region from their pairwise crossings. For weighted nearest-neighbour regression, this yields a finite interval-and-ray calculation rather than evaluating every real label.
- Weighted k-NNR predicts by averaging the labels of the k nearest training examples, using a distance measure such as Euclidean distance.
- The TCP expresses each example’s nonconformity score as a piecewise-linear function of the assumed test label ỹ.
- Because p(ỹ) changes only at score-crossing points, the TCP computes the retained labels as a union of finitely many intervals and rays.
- Algorithm 1 constructs and sorts crossing points, counts set coverage across resulting segments, and outputs the predictive region.
- For each example, the candidate labels producing at least as much nonconformity as the test example form a set S_i whose shape can be an interval, ray, two rays, the real line, or empty.
- The p-value of a candidate label is the number of sets S_i containing it divided by l+1.
4. k-Nearest Neighbours Regression ICP
The inductive k-NNR Conformal Predictor separates proper training from calibration, allowing the underlying algorithm to be trained once. Fixed calibration scores then determine each test example’s predictive region more efficiently, subject to the calibration-size trade-off.
- TCP retrains its underlying algorithm for every test example because the test example enters the training set, making it inefficient on large data sets.
- ICP splits the training data into a proper training set and a calibration set, then trains the underlying algorithm only once.
- ICP computes calibration-example nonconformity scores once and compares each candidate test-label score with them.
- For each test example, the k-NNR prediction and calibration scores remain fixed while only the assumed-label score changes.
- The ICP predictive region is bounded by the largest calibration score meeting the p-value threshold and is produced around the k-NNR prediction.
- The calibration size q should remain a small portion of the training set, with experiments using q=100n−1 for 99% and 95% confidence levels.
5. Normalized Nonconformity Measures
The paper normalizes the typical regression nonconformity measure using expected k-NNR accuracy, defining measures based on neighbour distances and label variability. These measures support ICP broadly, whereas TCP can use only two because some scores change with the candidate label.
- Motivation: The proposed measures normalize regression nonconformity using expected accuracy, producing larger predictive regions for examples that are more difficult to predict.The motivation is that equal absolute errors can indicate different degrees of strangeness when prediction accuracy differs.
- Distance-based measures: Expected accuracy is estimated from the distance between an example and its k nearest neighbours, because those neighbours generate the underlying k-NNR prediction.The distance is compared with the median distance across training examples for consistency across data sets.
- Parameterization: The parameter γ controls sensitivity to changes in the distance- or label-based accuracy measures, with its effect depending on the measure’s definition.For one measure, increasing γ reduces sensitivity; for another, it increases sensitivity, and the exponential form becomes more sensitive when neighbour distance is large.
- Label-variability measures: A second accuracy estimate uses the standard deviation of the labels of an example’s k nearest neighbours, with normalization by the median training-set standard deviation.Greater neighbour-label agreement is treated as indicating a more accurate k-NNR prediction.
- CP implementations: The paper develops normalized nonconformity measures for both transductive and inductive CP, but only measures (24) and (25) can be used with the k-NNR TCP.For ICP, calibration scores can be calculated using measures (24), (25), (29), (30), (31), or (32).
6. Theoretical Analysis of Nonconformity Measure (29)
The paper analyzes measure (29) for k-NNR ICP under specific distributional and asymptotic assumptions. Under those assumptions, its predictive regions are asymptotically optimal and closely match the standard normal-model prediction interval and the ICP region obtained from measure (35).
- Theoretical claim: Measure (29) produces asymptotically optimal predictive regions under specific assumptions, which are not required for the validity of the resulting regions.The authors deliberately do not formalize every condition needed for the asymptotic conclusions.
- Assumptions: The analysis assumes normally distributed labels with smooth mean and variance functions, covariates concentrated on a compact set, positive density, and k, m, q much larger than one another as specified.The stated regime requires k ≫1, m ≫k and q ≫k.
- Score distribution: The resulting nonconformity scores are approximately standard normal, yielding a high-probability bound based on their descending calibration-score order statistics.For a new example, the bound holds with probability close to 1 −δ.
- Predictive regions: The resulting region is close to the standard prediction interval for the normal model and almost identical to the k-NNR ICP region (35).This comparison is made with γ = 0 and the corresponding normalization setting.
7. Experimental Results
Experiments on six benchmark data sets evaluated predictive-region tightness and reliability for k-NNR conformal predictors. New nonconformity measures generally produced tighter regions while preserving empirical validity, with combined measures performing best overall for ICP.
- Experimental setup: Experiments used six UCI and DELVE benchmark data sets with normalized attributes and repeated cross-validation.Boston Housing and Abalone used 10 and 4 folds respectively; the other four data sets used 2 folds, across 10 random runs.
- Evaluation criteria: Predictive-region tightness was assessed using median and interdecile mean widths at 99%, 95%, and 90% confidence levels.These summaries were chosen to reduce the influence of extremely large or small regions.
- Reliability: The reported error percentages were close to the required significance levels and changed little across nonconformity measures.This provided an empirical check of predictive-region reliability in addition to width comparisons.
- Overall tightness: 17%-86% and 11%-47% were the median width percentages across measures and data sets at 99% and 95% confidence, respectively.For the best measure on each data set, the worst median width percentage was 61% at 99% confidence and 43% at 95% confidence.
- Comparison with the standard measure: New measures generally produced smaller median and interdecile mean widths than the standard regression measure, often substantially so.In many cases, new-measure median widths fell below the smallest widths obtained with the standard measure.
- Method comparisons: Measures (31) and (32) gave the tightest ICP regions overall, with one of them smallest in 11 of 18 median-width cases and all but one interdecile-mean case.TCP regions were tighter than ICP regions for the standard measure, while ICP offered a large processing-efficiency advantage despite extra computations for new measures.
8. Comparison with Gaussian Process Regression
The paper compares k-NNR conformal predictive regions with Gaussian Process Regression on artificial data generated from a GP and on three benchmark data sets. GPR regions are tighter in almost all cases, but on real-world data they frequently fail the required reliability levels, whereas CP regions remain valid.
- Experimental setup: The comparison evaluates k-NNR CPs and GPR on GP-generated artificial data and the Boston Housing, Abalone, and Computer Activity data sets.The artificial experiments used 100 data sets, each with 1000 training and 1000 test examples, generated from a Gaussian Process.
- Experimental setup: The GPR comparison includes covariance-function results for Boston Housing, Abalone, and Computer Activity, with hyperparameters adapted by maximizing marginal likelihood.The benchmark preprocessing standardized attributes and centered labels before GPR evaluation.
- Benchmark comparison: GPR regions are tighter in almost all cases on the three benchmark data sets.The comparison uses the GPR results in Tables 10–12 against the k-NNR CP results in Tables 2–4.
- Reliability: GPR regions frequently exclude the true label at rates higher than required for the 95% and 99% confidence levels.The paper therefore characterizes these regions as not valid on the benchmark data.
- Interpretation: CPs produce valid predictive regions even when their parameters or underlying algorithm are totally wrong, unlike GPR when the correct prior is unavailable.This contrast is central to interpreting the tighter GPR regions on real-world data.
9. Conclusions
The paper develops transductive and inductive k-NNR conformal predictors with six new nonconformity measures. Experiments report tight, reliable regions, with measures (31) and (32) strongest for ICP and ICP offering major efficiency advantages on relatively large data sets.
- Contributions: The paper develops six k-NNR nonconformity measures based on neighbour distances, label standard deviations, or combinations of both.The measures are used with Transductive and Inductive Conformal Predictors, although the paper notes that TCP supports only two of the six new measures.
- Results: The methods produce reliable predictive intervals that are tight enough to be useful in practice across the tested data sets.The conclusion also reports substantial improvement in predictive-region tightness for both transductive and inductive methods.
- Results: For relatively large data sets, ICP with measures (31) and (32) appears as tight as TCP while retaining a substantial computational-efficiency advantage.The conclusion frames this as a comparison of predictive-region tightness and computational efficiency.
- Future work: Future work includes normalized nonconformity measures for Ridge Regression and Support Vector Regression, plus evaluation in medical and other expert-reviewed applications.The paper identifies these as its main future directions rather than completed evaluations.