Distribution-Free Prediction Sets for Two-Layer Hierarchical Models

Robin Dunn, Larry Wasserman, Aaditya Ramdas

Abstract

We consider the problem of constructing distribution-free prediction sets for data from two-layer hierarchical distributions. For iid data, prediction sets can be constructed using the method of conformal prediction. The validity of conformal prediction hinges on the exchangeability of the data, which does not hold when groups of observations come from distinct distributions, such as multiple observations on each patient in a medical database. We extend conformal methods to this hierarchical setting. We develop CDF pooling, single subsampling, and repeated subsampling approaches to construct prediction sets in unsupervised and supervised settings. We compare these approaches in terms of coverage and average set size. If asymptotic coverage is acceptable, we recommend CDF pooling for its balance between empirical coverage and average set size. If we desire coverage guarantees, then we recommend the repeated subsampling approach.

Introduction

In high-stakes domains such as medicine and finance, point estimates are often insufficient for informed decision-making. Instead, practitioners require prediction sets: a range of values guaranteed to contain the true outcome with a specified probability (e.g., 90%). Conformal prediction has emerged as a leading framework for generating these sets because it is "distribution-free," requiring no parametric assumptions about the underlying data.

However, standard conformal prediction relies on the assumption of exchangeability, typically satisfied by independent and identically distributed (i.i.d.) data. In practice, data is frequently hierarchical. For example, a medical database may contain multiple visits per patient. Observations within a patient group are correlated, violating the exchangeability requirement. This paper addresses this gap by extending conformal prediction to two-layer hierarchical models, focusing on two primary objectives:

  1. Task 1: Predicting an outcome for a previously unseen subject.
  2. Task 2: Predicting a future outcome for a subject already present in the training data.

Methodology

The authors propose three distinct strategies to accommodate hierarchical structures while maintaining valid coverage.

1. CDF Pooling

This approach involves calculating an empirical Cumulative Distribution Function (CDF) for each group (subject) and then averaging these CDFs across all groups. Prediction intervals are then derived from the quantiles of this pooled distribution.

  • Pros: Computationally efficient and typically yields the narrowest (most precise) prediction sets.
  • Cons: Validity is asymptotic, meaning it requires a sufficiently large number of groups ($k$) to ensure coverage.

2. Single Subsampling

To restore exchangeability, this method randomly selects exactly one observation from each of the $k$ groups. This resulting subset of $k$ independent observations allows for the application of standard conformal prediction techniques.

  • Pros: Theoretically sound for any sample size.
  • Cons: Highly inefficient, as it discards the majority of the available data, leading to high variance in the resulting intervals.

3. Repeated Subsampling

This method stabilizes the single subsampling approach by repeating the process $B$ times and aggregating the resulting p-values.

  • Pros: Provides a robust finite-sample coverage guarantee (specifically $1-2\alpha$). It is significantly more stable and reproducible than single subsampling.
  • Cons: The theoretical bound is somewhat conservative compared to the desired $1-\alpha$.

4. James-Stein Shrinkage (Task 2)

For Task 2, where the goal is to predict for an existing subject, the authors incorporate James-Stein estimators. By "borrowing strength" from the global population, this method improves predictions for individuals with limited personal data, effectively balancing individual-specific noise against population-level trends.

Experimental Evaluation

Simulations

The methods were tested across various distributions (Normal, Beta, and Exponential) and varying group sizes. The simulations included "unbalanced" scenarios where some groups contained significantly more data than others (up to a 200x difference), testing the robustness of the pooling and subsampling techniques.

Sleep Deprivation Study

The framework was applied to the sleepstudy dataset (from the R package lme4), which tracks the reaction times of 18 drivers over 10 days of sleep restriction. This served as a supervised learning benchmark, where the model predicted reaction times based on the duration of sleep deprivation and the subject's baseline performance.

Key Results and Insights

  • The Subsampling Insight: The research demonstrates that exchangeability can be "engineered" back into hierarchical data through subsampling. This allows the existing conformal prediction ecosystem to be applied to complex data structures.
  • Coverage Performance: All proposed methods successfully achieved target coverage in simulations. While CDF pooling showed slight under-coverage when the number of groups was very small ($k < 35$), it stabilized as $k$ increased.
  • Efficiency Trade-offs: CDF pooling consistently produced the smallest prediction sets, making it the preferred choice for large-scale datasets where asymptotic validity is sufficient. For smaller datasets where mathematical guarantees are paramount, Repeated Subsampling proved more reliable.
  • Impact of Shrinkage: In Task 2 scenarios, shrinkage estimators significantly reduced the size of prediction sets when within-group variance was high, demonstrating the value of population-level data in refining individual predictions.

Conclusion

This work provides a practical roadmap for applying conformal prediction to hierarchical data. For practitioners, the choice of method depends on the specific requirements of the application: CDF Pooling is recommended for its efficiency and tight intervals in large-group settings, while Repeated Subsampling is recommended when finite-sample coverage guarantees are required. Future research may focus on tightening the $1-2\alpha$ bound for repeated subsampling and extending supervised methods for existing subjects.

Summary updated

Abstract

We consider the problem of constructing distribution-free prediction sets for data from two-layer hierarchical distributions. For iid data, prediction sets can be constructed using the method of conformal prediction. The validity of conformal prediction hinges on the exchangeability of the data, which does not hold when groups of observations come from distinct distributions, such as multiple observations on each patient in a medical database. We extend conformal methods to a hierarchical setting. We develop CDF pooling, single subsampling, and repeated subsampling approaches to construct prediction sets in unsupervised and supervised settings. We compare these approaches in terms of coverage and average set size. If asymptotic coverage is acceptable, we recommend CDF pooling for its balance between empirical coverage and average set size. If we desire coverage guarantees, then we recommend the repeated subsampling approach. Supplementary materials for this article are available online.
BibTeX
@article{dunn2018distribution,
  author = {Robin Dunn and Larry Wasserman and Aaditya Ramdas},
  title = {{Distribution-Free Prediction Sets for Two-Layer Hierarchical Models}},
  journal = {Journal of the American Statistical Association},
  year = {2018},
}
Figure