Conformal prediction

Conformal prediction (CP) is a set of algorithms devised in order to assess the uncertainty of predictions produced by a machine learning model. CP algorithms do this by computing and comparing nonconformity scores (often referred to as α-values), of examples from the training set, and compare these with scores computed for test objects. There are several subtypes of conformal predictors, broadly they can be divisioned into inductive and transductive algorithms. These two variations mainly vary in their computational compexity and whether they can be applied to regression or classification tasks. The inductive algorithms rely on training one or several machine learning models which are re-used for all future test objects and is available for both classification and regression tasks, whereas the transductive approach requires the underlying model (singular) to be re-trained for every new test object and is only available for classification tasks.

Conformal prediction relies on the user to specify a significance level for which the algorithm should produce its predictions, this significance level restricts the frequency of errors that the algorithm is allowed to make. E.g. specifying a significance level of 0.1 forces the algorithm to at most produce 10% erronious predictions. To adhere to this requirement, the output of a conformal prediction algorithm is a set prediction instead of a point prediction which is what standard supervised machine learning models produce. For classification tasks that means that predictions are not a single class, say 'cat' or 'dog', but is instead sets like '{cat, dog}'. Depending on how good the underlying model is (how well it can discern between cats and dogs) and the specified significance level these sets can be smaller or wider, i.e. produce sets with only a single class or multi-sets. For regression tasks the output is prediction intervals, where a smaller significance level (less allowed errors) produces wider intervals which are less specific, and vise versa - more allowed errors produces tigher prediction intervals.[1][2][3][4]

Theory

Conformal Prediction was first proposed by Vovk et.al in 2005. [1]A tutorial by Vovk and Shafter was published in 2008.[5]The data has to confirm to some standards, such as data being exchangeable (a sightly weaker assumption than the standard IID imposed in standard machine learning). For conformal prediction a n% prediction region is said to be valid if the truth is part of the output n% of the time. [1]The efficiency is the size of the output. For classification this means the number of classes, whereas for regression model it refers to the span of the output. [5]

For the purest forms of conformal prediction is made for an online (transductive) section. This means that it is assumed that once a label has been predicted with a set confidence its true label will be known before the next prediction. The underlying model can therefore be re-trained using this new datapoint and the next prediction will be made on a calibration set containing n+1 data points, where the previous model had n data points. [5]

Classification algorithms

The purpose of standard classification algorithms is to classify a test object into one out of two (or several) discrete classes. Conformal classifiers instead computes and output the p-value for each available class by performing a ranking of the nonconformity score (α-value) of the test object against examples from the training data set. Similarly to standard hypothetis testing the p-value together with a threshold (referred to as significance level in the CP field) is used for determining whether the label should be part of the prediction set. E.g. when specifying a significance level of 0.1, all classes with a p-value of 0.1 or greater is added to the prediction set. Depending on the specific algorithm that is employed, the ranking of nonconformity scores can either be against a subset of the full training set (for inductive algorithms) or using all available training data (for the transductive algorithm).

Inductive conformal prediction (ICP)

Inductive Conformal Prediction was first known as Inductive Confidence Machines,[6] but was later re-introduced as ICP. It has gained in popularity in practical settings as the underlying model does not need to be retrained for every new test example. This makes it interesting for any model that is heavy to train, such as neural networks.[7]

Mondrian inductive conformal prediction (MICP)

In MICP the alpha values are class dependent (mondrian) and the underline model does not follow the original online setting introduced in 2005. [2]

The basic structure of conformal prediction being implemented in an Inductive Mondrian Conformal Predictor is:

  1. Train a Machine Learning Model (MLM)
  2. Run a calibration set through the MLM, save output from chosen stage
    1. In a deep learning setting the softmax values are often used
  3. Use a non-conformity function to generate α-values
    1. A data point in the calibration set will result in an α-values for its true class
  4. For a test data point generate a new α-values
  5. Find a p-value for each class of the data point
  6. If the p-value is bigger than the significance level, include the class in the output[2]

Regression algorithms

Conformal prediction was initially formulated for the task of classification, but was later modified to work for regression tasks. Contrary to the classification algorithms, which output p-values without supplying a significance level in advance, the regression algorithms require a fixed significance level at prediction time in order to produce prediction intervals for a new test object. For classic conformal regression, there exists no transductive algorithm, intuitively this can be explained due to the imposibility of postulating all possible labels for a new test object, as the label space is continuous. The available algorithms are all formulated in the inductive setting, which computes a prediction rule once and applies it to all future predictions.

Inductive Conformal Prediction (ICP)

All inductive algorithms require splitting the available training examples into two disjoint sets, one set of examples used for training the underlying machine learning model (commonly called proper training set) and one set of examples used for calibrating the prediction (commonly called calibration set). For the ICP algorithm this split is performed once, thus training a single ML model. Provided that the split is performed randomly and that data is exchangeable, the ICP model is proven to enjoy automatic validity (i.e. the error rate correspond to the required singificance level).

The algorithm for training the model is as follows:

  1. Split all training data into two disjoint sets, proper training and calibration
  2. Train the underlying ML model using the proper training set
  3. Predict the examples from the calibration set using the derived ML model → ŷ-values
  4. Optional - if using a normalized nonconformity function
    1. Train the normalization ML model
    2. Predict normalization scores → 𝜺 -values
  5. Compute the nonconformity scores (α-values) for all calibration examples, using ŷ- and 𝜺-values
  6. Sort the nonconformity scores
  7. Save underlying ML model, normalization ML model (if any) and nonconformity scores

The algorithm for predicting a test object is as follows:

Required input: significance level (s)

  1. Predict the test object using the ML model → ŷt
  2. Optional - if using a normalized nonconformity function
    1. Predict the test object using normalization model → 𝜺t
  3. Pick the nonconformity score from the list of scores produced by the calibration set in training, corresponding to the significance level s → αs
  4. Compute the prediction interval half width (d) from rearranging the nonconformity function and input αs (and optionally 𝜺) → d
  5. Output prediction interval (ŷ - d, ŷ + d) for the given significance level s

Split Conformal Prediction (SCP)

The SCP, also frequently referred to as Aggregated Conformal Predictor (ACP), can be thought of as an ensamble of several ICPs. SCP is often preferable over using a single ICP as it generally improve the efficiency of the predictions (i.e. create smaller prediction intervals), but loses the automatic validity in the generated predictions. A common subtype of SCPs is the Cross-Conformal Predictor (CCP), which splits the available training data into proper training and calibration sets using a folded splitting strategy similar to k-fold cross-validation. Regardles of the chosen splitting technique, the overall algorithm is to perform n splits into proper training and calibration sets and to train a single ICP for each of these splits. When predicting a new test object, the median ŷmedian and dmedian from the n ICPs are used to generate the final prediction interval (ŷmedian - dmedian, ŷmedian + dmedian).


Fields of application

Machine learning models

Several different machine learning models can be used in conjunction with Conformal Prediction. Studies have shown that it can be applied to for example convolutional neural networks,[8] support-vector machines, and more.

Data used

Conformal prediction is applied in av variety of fields and an active are of research. For example within biotechnology has been used to predict uncertainties in breast cancer,[9] stroke risks [10] and more. Within language technology, conformal prediction papers are routinely presented at COPA.[11]

Conferences

Conformal prediction is one of the main subjects discussed during the COPA-conference each year. Both theory and applications of conformal predictions are presented by leaders of the field. The conference has been held since 2012.[11] It has been hosted in several different European countries including Greece, Great Britain, Italy and Sweden.

References
  1. Vovk, Vladimir (2005). Algorithmic learning in a random world. A. Gammerman, Glenn Shafer. New York: Springer. ISBN 978-0-387-00152-4. OCLC 209818494.
  2. Toccaceli, Paolo; Gammerman, Alexander (2019-03-01). "Combination of inductive mondrian conformal predictors". Machine Learning. 108 (3): 489–510. doi:10.1007/s10994-018-5754-9. ISSN 1573-0565.
  3. Norinder, Ulf; Carlsson, Lars; Boyer, Scott; Eklund, Martin (2014-06-23). "Introducing Conformal Prediction in Predictive Modeling. A Transparent and Flexible Alternative to Applicability Domain Determination". Journal of Chemical Information and Modeling. 54 (6): 1596–1603. doi:10.1021/ci5001168. ISSN 1549-9596.
  4. Alvarsson, Jonathan; McShane, Staffan Arvidsson; Norinder, Ulf; Spjuth, Ola (2021-01-01). "Predicting With Confidence: Using Conformal Prediction in Drug Discovery". Journal of Pharmaceutical Sciences. 110 (1): 42–49. doi:10.1016/j.xphs.2020.09.055. ISSN 0022-3549. PMID 33075380.
  5. Vovk, Vladimir; Shafer, Glenn (2008-08-03). "A Tutorial on Conformal Prediction". Journal of Machine Learning Research. 9: 371–421.
  6. Papadopoulos, Harris; Proedrou, Kostas; Vovk, Volodya; Gammerman, Alex (2002). Elomaa, Tapio; Mannila, Heikki; Toivonen, Hannu (eds.). "Inductive Confidence Machines for Regression". Machine Learning: ECML 2002. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 345–356. doi:10.1007/3-540-36755-1_29. ISBN 978-3-540-36755-0.
  7. Papadopoulos, Harris; Haralambous, Haris (2010). Diamantaras, Konstantinos; Duch, Wlodek; Iliadis, Lazaros S. (eds.). "Neural Networks Regression Inductive Conformal Predictor and Its Application to Total Electron Content Prediction". Artificial Neural Networks – ICANN 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 32–41. doi:10.1007/978-3-642-15819-3_4. ISBN 978-3-642-15819-3.
  8. Papadopoulos, Harris; Vovk, Volodya; Gammerman, Alex (October 2007). "Conformal Prediction with Neural Networks". 19th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2007). 2: 388–395. doi:10.1109/ICTAI.2007.47.
  9. Lambrou, A.; Papadopoulos, H.; Gammerman, A. (November 2009). "Evolutionary Conformal Prediction for Breast Cancer Diagnosis". 2009 9th International Conference on Information Technology and Applications in Biomedicine: 1–4. doi:10.1109/ITAB.2009.5394447.
  10. Lambrou, Antonis; Papadopoulos, Harris; Kyriacou, Efthyvoulos; Pattichis, Constantinos S.; Pattichis, Marios S.; Gammerman, Alexander; Nicolaides, Andrew (2010), Papadopoulos, Harris; Andreou, Andreas S.; Bramer, Max (eds.), "Assessment of Stroke Risk Based on Morphological Ultrasound Image Analysis with Conformal Prediction", Artificial Intelligence Applications and Innovations, Berlin, Heidelberg: Springer Berlin Heidelberg, 339, pp. 146–153, doi:10.1007/978-3-642-16239-8_21, ISBN 978-3-642-16238-1, retrieved 2021-09-15
  11. "10th Symposium on Conformal and Probabilistic Prediction with Applications (COPA 2021)". cml.rhul.ac.uk. Retrieved 2021-09-15.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.