  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.
