# Extending Conformal Prediction to Hidden Markov Models with Exact Validity via de Finetti's Theorem for Markov Chains

arXiv: https://arxiv.org/abs/2210.02271 · HTML: https://mlsanity.com/paper/2210.02271/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 5 Oct 2022.

## Builds on (most cited first, 9 of 9)

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Conformal Prediction: a Unified Review of Theory and New Challenges](https://mlsanity.com/paper/2005.07972/) (2020)
- [Robust Validation: Confident Predictions Even When Distributions Shift](https://mlsanity.com/paper/2008.04267/) (2020)
- [Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data](https://mlsanity.com/paper/1802.06300/) (2018)
- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [Human Intention Estimation based on Hidden Markov Model Motion Validation for Safe Flexible Robotized Warehouses](https://mlsanity.com/paper/1811.08269/) (2018)

## Built on by (most cited first, 8 of 8)

- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Conformal Load Prediction with Transductive Graph Autoencoders](https://mlsanity.com/paper/2406.08281/) (2024)
- [Weighted Aggregation of Conformity Scores for Classification](https://mlsanity.com/paper/2407.10230/) (2024)
- [Enhanced Route Planning with Calibrated Uncertainty Set](https://mlsanity.com/paper/2503.10088/) (2025)
- [Leave a Window Out: Modifying the Jackknife for Predictive Inference in Time Series](https://mlsanity.com/paper/2605.30292/) (2026)
- [Single Trajectory Conformal Prediction](https://mlsanity.com/paper/2406.01570/) (2024)
- [Interval POMDP Shielding for Imperfect-Perception Agents](https://mlsanity.com/paper/2604.20728/) (2026)
- [Conflict Forecasting via Conformal Prediction for Markov Processes](https://mlsanity.com/paper/2604.25139/) (2026)

## Abstract (arXiv)

Conformal prediction is a widely used method to quantify the uncertainty of a classifier under the assumption of exchangeability (e.g., IID data). We generalize conformal prediction to the Hidden Markov Model (HMM) framework where the assumption of exchangeability is not valid. The key idea of the proposed method is to partition the non-exchangeable Markovian data from the HMM into exchangeable blocks by exploiting the de Finetti's Theorem for Markov Chains discovered by Diaconis and Freedman (1980). The permutations of the exchangeable blocks are viewed as randomizations of the observed Markovian data from the HMM. The proposed method provably retains all desirable theoretical guarantees offered by the classical conformal prediction framework in both exchangeable and Markovian settings. In particular, while the lack of exchangeability introduced by Markovian samples constitutes a violation of a crucial assumption for classical conformal prediction, the proposed method views it as an advantage that can be exploited to improve the performance further. Detailed numerical and empirical results that complement the theoretical conclusions are provided to illustrate the practical feasibility of the proposed method.