Weighted Bayesian Conformal Prediction

1. Problem Statement

The paper addresses a critical gap in Conformal Prediction (CP), a framework for generating distribution-free prediction intervals with finite-sample coverage guarantees. While standard CP ensures that the true outcome falls within the predicted interval with probability $1-\alpha$, it suffers from two main limitations in real-world scenarios:

1. Distribution Shift: Standard CP assumes training (calibration) and test data are independent and identically distributed (i.i.d.). When this assumption fails (e.g., due to covariate shift, spatial heterogeneity, or domain adaptation), standard CP loses its validity. Weighted Conformal Prediction (WCP) solves this by using importance weights to maintain coverage, but it remains purely frequentist, outputting only a single deterministic threshold.
2. Meta-Uncertainty: Both standard CP and WCP produce a single point estimate for the prediction interval width (the threshold $\hat{q}$). They provide no information about the reliability of this threshold. For instance, a threshold derived from 200 highly relevant calibration points is far more reliable than one derived from 5 distant points, yet standard methods treat them identically.
3. Limitations of Existing Bayesian Approaches: Recent work by Snell & Griffiths reframed CP as Bayesian Quadrature (BQ-CP), providing a posterior distribution over the threshold (quantifying meta-uncertainty). However, BQ-CP relies strictly on the i.i.d. assumption and cannot handle importance-weighted settings.

The Core Problem: There is no existing method that simultaneously offers distribution-shift robustness (via weighting) and meta-uncertainty quantification (via a Bayesian posterior over the threshold).

2. Methodology: Weighted Bayesian Conformal Prediction (WBCP)

The authors propose WBCP, a framework that generalizes BQ-CP to arbitrary importance-weighted settings.

Key Insight

The method replaces the uniform Dirichlet prior used in BQ-CP with a weighted Dirichlet distribution.

• BQ-CP (i.i.d.): Models quantile spacings as $V \sim \text{Dir}(1, \dots, 1)$.
• WBCP (Weighted): Models quantile spacings as $V \sim \text{Dir}(n_{\text{eff}} \cdot \tilde{w}_1, \dots, n_{\text{eff}} \cdot \tilde{w}_n)$.

Here:

• $\tilde{w}_i$ are the normalized importance weights (e.g., likelihood ratios for covariate shift or kernel weights for spatial data).
• $n_{\text{eff}}$ is Kish's effective sample size, calculated as:
  $$n_{\text{eff}} = \frac{(\sum w_i)^2}{\sum w_i^2}$$
  This parameter acts as the concentration parameter for the Dirichlet distribution.

Theoretical Justification

1. Weighted Bayesian Bootstrap: The construction is justified via the weighted Bayesian bootstrap (Newton & Raftery, 1994). When weights are uniform, $n_{\text{eff}} = n$, and WBCP recovers the standard BQ-CP model.
2. Variance Matching: The authors prove that $n_{\text{eff}}$ is the unique concentration parameter that ensures the Bayesian posterior variance matches the frequentist sampling variance of the weighted estimator.
   • High $n_{\text{eff}}$ (many effective samples) $\rightarrow$ Concentrated posterior (low meta-uncertainty).
   • Low $n_{\text{eff}}$ (few effective samples) $\rightarrow$ Diffuse posterior (high meta-uncertainty).

Algorithm

1. Input: Calibration scores $\{\rho_i\}$ and weights $\{w_i\}$.
2. Compute: $n_{\text{eff}}$ and normalized weights.
3. Sampling: Sample $M$ vectors $u^{(m)}$ from $\text{Dir}(n_{\text{eff}} \cdot \tilde{w}_1, \dots, n_{\text{eff}} \cdot \tilde{w}_n)$.
4. Thresholding: For each sample, compute the threshold $\lambda^{(m)}$ corresponding to the $(1-\alpha)$-quantile of the weighted spacings.
5. Output:
   • $\lambda_{\text{HPD}}$: The Highest Posterior Density (HPD) threshold, providing a data-conditional guarantee.
   • $\sigma_{\text{post}}$: The posterior standard deviation, quantifying meta-uncertainty.
   • $n_{\text{eff}}$: The effective number of calibration samples supporting the estimate.

3. Key Contributions

The paper makes four primary theoretical contributions and one practical instantiation:

1. Generalization of BQ-CP: WBCP extends the Bayesian Quadrature framework to non-i.i.d. settings by mapping importance weights to Dirichlet concentration parameters.
2. Theoretical Proofs:
   • Calibration Consistency: Proves $n_{\text{eff}}$ is the unique scaling factor matching frequentist and Bayesian variances.
   • Posterior Concentration: Proves the posterior standard deviation decays as $O(1/\sqrt{n_{\text{eff}}})$. This establishes a direct link between data quality (effective sample size) and the reliability of the uncertainty estimate.
   • Weighted Stochastic Dominance: Extends BQ-CP's stochastic dominance guarantee to per-weight-profile settings, ensuring data-conditional guarantees hold for specific weight profiles.
   • Conditional Coverage Bound: Shows that the HPD threshold improves conditional coverage by $O(1/\sqrt{n_{\text{eff}}})$ over the marginal rate, with the improvement being most significant where $n_{\text{eff}}$ is low (i.e., where standard methods are least reliable).
3. Geographical BQ-CP (GeoBCP): The authors instantiate WBCP for spatial prediction. Using kernel-based spatial weights, GeoBCP generates:
   • $n_{\text{eff}}$ Maps: Visualizing where calibration data is dense vs. sparse.
   • $\sigma_{\text{post}}$ Maps: Visualizing where prediction intervals are "confidently narrow" vs. "uncertainly narrow."
4. Empirical Validation: Extensive experiments on synthetic and real-world spatial datasets (Seattle house prices) demonstrate that WBCP maintains coverage guarantees while providing significantly richer uncertainty information than standard CP, Weighted CP, or BQ-CP.

4. Results

• Synthetic Data: WBCP variants maintained coverage above the target (90%) while providing posterior diagnostics. The posterior standard deviation ($\sigma_{\text{post}}$) strongly correlated with known noise structures (Pearson $r < -0.9$), confirming it faithfully reflects data quality.
• Real-World Data (Seattle House Prices):
  • Coverage: GeoBCP achieved ~95% coverage (exceeding the 90% target) with a modest increase in interval width compared to standard GeoCP.
  • Diagnostics: The method successfully distinguished between urban centers (high $n_{\text{eff}}$, low $\sigma_{\text{post}}$) and peripheral areas (low $n_{\text{eff}}$, high $\sigma_{\text{post}}$).
  • Comparison: Unlike Standard CP or Weighted CP, WBCP provided a full posterior distribution, allowing users to see that a narrow interval in a data-sparse region is actually highly uncertain.

5. Significance

This work bridges a fundamental theoretical gap between frequentist robustness (handling distribution shift) and Bayesian uncertainty quantification (meta-uncertainty).

• Practical Impact: In high-stakes applications (e.g., medical diagnosis, autonomous driving, real estate), knowing how reliable a prediction interval is, is as important as the interval itself. WBCP allows practitioners to identify regions where predictions are statistically unsupported (low $n_{\text{eff}}$) and trigger targeted data collection or conservative decision-making.
• Theoretical Advancement: It resolves the limitation of BQ-CP by removing the i.i.d. constraint, making Bayesian conformal prediction applicable to the vast array of real-world problems involving covariate shift and spatial heterogeneity.
• Interpretability: The introduction of $n_{\text{eff}}$ and $\sigma_{\text{post}}$ as diagnostic tools transforms conformal prediction from a "black box" interval generator into an interpretable system that communicates the quality of its own calibration.