Conformal Thresholded Intervals for Efficient Regression

Basic Information

• Paper ID: 2407.14495
• Title: Conformal Thresholded Intervals for Efficient Regression
• Authors: Rui Luo (City University of Hong Kong), Zhixin Zhou (Alpha Benito Research)
• Classification: cs.LG, stat.ML
• Publication Time/Conference: AAAI 2025
• Paper Link: https://arxiv.org/abs/2407.14495
• Code Link: https://github.com/luo-lorry/CTI

Abstract

This paper proposes Conformal Thresholded Intervals (CTI), a novel conformal regression method designed to produce prediction sets as small as possible while guaranteeing coverage. Unlike existing methods that rely on nested conformal frameworks and complete conditional distribution estimation, CTI employs off-the-shelf multi-output quantile regression to estimate the conditional probability density that a new response falls into each inter-quantile interval. By leveraging the inverse relationship between interval length and probability density, CTI constructs prediction sets by thresholding inter-quantile intervals based on their estimated lengths. An optimal threshold is determined using a calibration set to ensure marginal coverage, effectively balancing the trade-off between prediction set size and coverage rate.

Research Background and Motivation

Problem Background

Conformal prediction is a powerful framework for constructing prediction sets with finite-sample coverage guarantees. Existing conformal regression methods fall into two main categories:

1. Directly using quantile regression models to predict the lower and upper endpoints of intervals
2. First estimating the complete conditional distribution, then inverting to obtain prediction sets

Limitations of Existing Methods

1. Quantile Regression Approaches: Typically produce equal-tailed intervals, but for skewed conditional distributions, the shortest valid intervals may be imbalanced
2. Density Estimation Methods: Can adapt to skewness but usually involve many tuning parameters, are difficult to interpret, and are complex for practitioners

Research Motivation

• Existing methods may produce suboptimal prediction sets when conditional distributions are skewed
• Need for a method that adapts to local data density while being computationally efficient
• Desire to avoid the complexity of estimating complete conditional distributions

Core Contributions

1. Proposes CTI Method: A novel conformal prediction regression method that leverages multi-output quantile regression to estimate inter-quantile intervals and constructs prediction sets by thresholding these intervals
2. Theoretical Analysis: Proves that CTI guarantees marginal coverage and can achieve desired conditional coverage and minimal expected prediction interval length under specific conditions
3. Experimental Validation: Extensive numerical experiments on simulated and real datasets demonstrate that CTI produces smaller prediction sets while maintaining effective coverage
4. Practical Utility: The method is simple to implement and interpret, making it attractive for practitioners seeking reliable uncertainty quantification

Methodology Details

Task Definition

Given a regression dataset $\{(x_i, y_i)\}_{i=1}^n$, where $x_i \in \mathcal{X} \subseteq \mathbb{R}^d$, $y_i \in \mathcal{Y} \subseteq \mathbb{R}$. The goal is to construct a conformal predictor that outputs a prediction set $C(x) \subseteq \mathcal{Y}$ for each test input $x$, satisfying: $P(Y \in C(X)) \geq 1-\alpha$ while minimizing the expected size of the prediction set.

Model Architecture

Core Insight

The key insight of CTI is to exploit the inverse relationship between interval length and probability density. For conditional probability density $f(y|x)$, if quantile regression is sufficiently accurate: $f(y|x) \approx \frac{1}{K \cdot \mu(I_k(x))}$ where $\mu(I_k(x))$ is the length of interval $I_k(x)$.

Algorithm Procedure

Step 1: Multi-output Quantile Regression Apply quantile regression on the training set to predict the $\tau$-th quantile of the conditional distribution $Y|X=x$: $\hat{q}_k(x) \text{ for } k = 0, 1, \ldots, K$ where $\tau = k/K$.

Step 2: Define Inter-quantile Intervals$I_k(x) = (\hat{q}_{k-1}(x), \hat{q}_k(x)] \text{ for } k = 1, \ldots, K$

Step 3: Construct Prediction Sets Based on interval length thresholding: $C(x) = \bigcup\{I_k(x) : \mu(I_k(x)) \leq t, k = 1, \ldots, K\}$

Step 4: Determine Threshold Use the calibration set to determine threshold $t$: $t = (1-\alpha)\text{-th quantile of } \frac{1}{1+|\mathcal{I}_{cal}|}\sum_{i \in \mathcal{I}_{cal}} \delta_{\mu(I_{k(y_i)}(x_i))} + \delta_\infty$

Technical Innovations

1. Direct Thresholding Strategy: Unlike CHR which requires explicit binning of the response space, CTI directly trains a multi-output quantile regression model
2. Global Thresholding: CTI adopts a global perspective to threshold inter-quantile intervals across all $x$ values, improving efficiency of marginal coverage
3. Theoretical Optimality: Based on the Neyman-Pearson lemma, CTI is theoretically close to optimal prediction sets

Experimental Setup

Datasets

Simulated Data:

• Generate $n = 10000$ samples, $X_i \sim \text{Uniform}[0,1]$
• Response variable: $y \sim \text{Triangular}(0, x, x)$
• Conditional density: $f(y|x) = \frac{2y}{x^2}\mathbf{1}\{y \in (0,x)\}$

Real Datasets (13 total): bike, bio, blog, community, concrete, facebook1, facebook2, homes, meps19, meps20, meps21, star, etc.

Evaluation Metrics

1. Coverage: Proportion of prediction sets containing true values
2. Prediction Set Size: Average length/measure of prediction sets

Baseline Methods

• Split Conformal: Basic split conformal method
• CQR (Conformal Quantile Regression): Conformal quantile regression
• CHR (Conformal Histogram Regression): Conformal histogram regression

Implementation Details

• Data split: 20% test, remaining split 70% training and 30% calibration
• Number of quantiles: $K = 100$
• Base models: Random Forest (RF) and Neural Networks (NN)
• Repeated experiments: 10 independent runs
• Significance level: $\alpha = 0.1$ (90% coverage)

Experimental Results

Main Results

Simulated Data Results:

• CTI theoretical expected set size: 0.317
• CHR theoretical expected set size: 0.342
• CQR theoretical expected set size: 0.376
• CTI actual performance: CTI(RF) 0.345±0.005, CTI(NN) 0.369±0.015
• All methods achieved approximately 90% coverage

Real Dataset Results: On 11 out of 13 datasets, CTI produced smaller prediction sets than other methods while maintaining desired coverage levels.

Key Findings

1. Consistent Advantages: CTI outperforms baseline methods on most datasets
2. Model Dependency: CTI's efficiency depends on the quality of the underlying quantile regression model
3. Small Dataset Challenges: On smaller datasets (e.g., star, n=2161), CQR may perform better

Ablation Studies

Interval Length Analysis: By comparing the distribution of response interval lengths with all interval lengths, CTI's performance depends on specific datasets and the underlying quantile regression model. Theoretically, the mean difference between the two distributions should be zero, but actual deviations exist, highlighting the method's dependence on data and models.

Related Work

Quantile Regression Methods

• Traditional Methods: Hunter & Lange (2000), Meinshausen (2006), etc.
• Multi-quantile Estimation: Cho et al. (2017) showed that simultaneous estimation of multiple quantiles is more effective than individual estimation
• Non-crossing Constraints: Moon et al. (2021), Brando et al. (2022), etc. address quantile crossing issues

Conformal Prediction Methods

• Nested Conformal Prediction: Romano et al. (2019), Sesia & Candès (2020), etc.
• Density Estimation Methods: Izbicki et al. (2020), Sesia & Romano (2021), etc.
• This Work's Innovation: Directly estimate conditional probability density rather than complete conditional distribution

Conclusions and Discussion

Main Conclusions

1. CTI provides a simple and effective conformal regression method
2. By thresholding inter-quantile intervals, CTI produces smaller prediction sets than existing methods
3. The method is theoretically supported by the Neyman-Pearson lemma, guaranteeing optimality
4. Experiments validate the method's effectiveness across multiple datasets

Limitations

1. Interval Constraint: Current implementation does not guarantee prediction sets are always interval-shaped
2. Model Dependency: Performance highly depends on the accuracy of the underlying quantile regression model
3. Small Sample Challenges: May underperform traditional methods on small datasets
4. Parameter Selection: Choice of quantile number K requires balancing expressiveness and computational efficiency

Future Directions

1. Develop CTI variants that produce interval-shaped prediction sets
2. Improve performance on small sample cases
3. Study adaptive methods for selecting quantile number K
4. Integration with other uncertainty quantification methods

In-Depth Evaluation

Strengths

1. Solid Theoretical Foundation: Theoretical optimality guarantees based on the Neyman-Pearson lemma
2. Simple Methodology: Avoids the complexity of complete conditional distribution estimation
3. Comprehensive Experiments: Extensive validation on simulated and real data
4. High Practical Value: Easy to implement and interpret, suitable for practitioners
5. Strong Innovation: Successfully applies thresholding ideas from classification to regression problems

Weaknesses

1. Limited Applicability: May perform poorly on small sample datasets
2. Prediction Set Shape: Cannot guarantee prediction sets are interval-shaped, may produce discontinuous sets
3. Hyperparameter Sensitivity: Relatively sensitive to the choice of quantile number K
4. Theoretical Analysis: Some theoretical results based on strong assumptions

Impact

1. Academic Contribution: Provides new perspectives and methods for the conformal prediction field
2. Practical Value: Simple and efficient characteristics offer good application prospects
3. Reproducibility: Open-source code provided for easy reproduction and extension

Applicable Scenarios

1. Medium to Large Datasets: Performs best when sample size is sufficient
2. Uncertainty Quantification: Regression tasks requiring reliable confidence intervals
3. Real-time Applications: Scenarios with high computational efficiency requirements
4. Skewed Distributions: Regression problems with skewed conditional distributions

References

1. Romano, Y., Patterson, E., and Candès, E. (2019). Conformalized quantile regression. NeurIPS.
2. Sesia, M., and Romano, Y. (2021). Conformal prediction using conditional histograms. NeurIPS.
3. Meinshausen, N. (2006). Quantile regression forests. JMLR.
4. Sadinle, M., Lei, J., and Wasserman, L. (2019). Least ambiguous set-valued classifiers with bounded error levels. JASA.