Conformal Prediction and Testing under On-line Compression Models

Valentina Fedorova

Research output: ThesisDoctoral Thesis

665 Downloads (Pure)


This thesis addresses and expands research in conformal prediction -- a machine learning method for generating prediction sets that are guaranteed to have a prespecified coverage probability.

Introductory Chapter 1 places conformal prediction among other machine learning methods and describes fundamentals of the theory of conformal prediction.

Chapter 2 studies efficiency criteria for conformal prediction. It outlines four established criteria of efficiency and also introduces six new criteria. The conformity measures that optimise each of these ten criteria are described when the data-generating distribution is known. Lastly, the empirical behaviour of two of the outlined criteria is illustrated for standard conformal predictors on a benchmark data set.

Chapter 3 introduces conformal prediction under hypergraphical models. These models express assumptions about relationships between data features. Several conformal predictors under these models are constructed. Their performance is studied empirically using benchmark data sets. Also label conditional conformal predictors under hypergraphical models are described and studied empirically.

Chapter 4 addresses the problem of testing assumptions for complex data, with a particular focus on the exchangeability assumption. Testing is conducted in the on-line mode, which gives a valid measure of the degree to which this tested assumption has been falsified after observing each data example. Such measures are provided by martingales. Two new techniques for constructing martingales -- mixtures of stepped martingales and plug-in martingales -- are suggested. It is also proved that, under a stationarity assumption, plug-in martingales are competitive with commonly used power martingales. Results on testing two benchmark data sets are presented at the end of this chapter.

Chapter 5 discusses conformal prediction under the Gauss linear assumption and on-line testing is applied to this assumption. The performance of both prediction and testing is studied empirically for synthetic data sets and a benchmark data set.
Original languageEnglish
Awarding Institution
  • Royal Holloway, University of London
  • Gammerman, Alex, Supervisor
  • Vovk, Vladimir, Supervisor
  • Nouretdinov, Ilia, Supervisor
Thesis sponsors
Award date1 Jul 2014
Publication statusUnpublished - 2014


  • machine learning
  • conformal prediction
  • testing assumptions
  • hypergraphical model
  • exchangeability
  • Gauss linear model

Cite this