Cross-conformal e-prediction

2020·Arxiv

Abstract

Abstract

This note discusses a simple modification of cross-conformal prediction inspired by recent work on e-values. The precursor of conformal prediction developed in the 1990s by Gammerman, Vapnik, and Vovk was also based on e-values and is called conformal e-prediction in this note. Replacing e-values by p-values led to conformal prediction, which has important advantages over conformal e-prediction without obvious disadvantages. The situation with cross-conformal prediction is, however, different: whereas for cross-conformal prediction validity is only an empirical fact (and can be broken with excessive randomization), this note draws the reader’s attention to the obvious fact that cross-conformal e-prediction enjoys a guaranteed property of validity.

The version of this paper at http://alrw.net (Working Paper 26) is updated most often.

1 Introduction

Conformal prediction is based on the notion of a p-value. At this time p-values are widely discussed (see, e.g., [1]), and several alternatives to p-values have been proposed. Perhaps the most popular alternative is Bayes factors, which, when stripped of their Bayesian context, are referred to as e-values in [10]. In fact, e-values were used (under the name of i-values) when discussing precursors of conformal prediction in the 1990s. One early description is [3]. In this note, it will be convenient to distinguish between conformal e-prediction (using e-values) and conformal p-prediction (standard conformal prediction using p-values).

Conformal e-prediction was superseded by conformal (p-)prediction mainly for two reasons:

1. Conformal predictions can be packaged as prediction sets [9, Section 2.2], in which case the property of validity of conformal predictors is very easy to state: we just say that the probability of error is at most for a pre-specified significance level [9, Proposition 2.3].

2. In the on-line mode of prediction, smoothed conformal predictors make errors independently, and so small probabilities of errors manifest themselves, with high probability, as a low frequency of errors [9, Corollary 2.5].

These are important advantages of conformal p-prediction, which do not appear to be counterbalanced by any clear disadvantages.

Whereas the notion of a conformal e-predictor does not appear particularly useful, using e-values in place of p-values in cross-conformal prediction [8] has a clear advantage. Cross-conformal predictors are not provably valid [8, Appendix], and this sometimes even shows in experimental results [6]. The limits of violations of validity are given by R¨uschendorf’s result (see, e.g., [11]): when merging p-values coming from different folds by taking arithmetic mean (this is essentially what cross-conformal predictors do), the resulting arithmetic mean has to be multiplied by 2 in order to guarantee validity. In the recent method of jackknife+, introduced in [2] and closely related to cross-conformal prediction, there is a similar factor of 2 [2, Theorem 1], which cannot be removed in general [2, Theorem 2].

The situation with e-values is different: the arithmetic mean of e-values is always an e-value. This is an obvious fact, but it is shown in [10] that arithmetic mean is the only useful merging rule. Therefore, the version of cross-conformal prediction based on e-values, which we call cross-conformal e-prediction in this note, is always valid.

2 Conformal e-predictors

Suppose we are given a training set consisting of labelled objects = () and our goal is to predict the label of a new object x. In this note we consider predictors of the following type: for each potential label y for x we would like to have a number ) reflecting the plausibility of y being the true label of x. An example is conformal transducers [9, Section 2.5], which, in the terminology of this note, may be called conformal p-predictors. The output

of a conformal p-predictor is the full conformal prediction for the label of x; e.g., it determines the prediction set at each significance level. We will sometimes write ), where z := (x, y), instead of ).

We will use the notation X for the object space and Y for the label space (both assumed non-empty). These are measurable spaces from which the objects and labels, respectively, are drawn. Full observations z = (x, y) are drawn from Z := . For any non-empty set will be the set of all non-empty finite sequences of elements of X.

A conformal e-predictor is a function [0that maps any finite sequence (, to a finite sequence () of nonnegative numbers with average at most 1,

that satisfies the following property of equivariance: for any , any permutation of {1, . . . , m}, any (, and any ([0,

The conformal e-predictor proposed in [4] is

where SV is the set of indices of support vectors: SV if and only if is a support vector for the SVM constructed from as training set. When given a training set and a new object x, this conformal e-predictor goes through all potential labels y for x and for each constructs an SVM and outputs ). It makes it computationally inefficient.

The following obvious proposition asserts the validity of conformal e-predictors.

3 Split conformal e-predictors

Let us fix a measurable space Σ (a summary space). A Σ-valued split conformity measure is a measurable function Σ. Intuitively, ) encodes how well z conforms to . A normalizing transformation N : Σ[0is an equivariant measurable function that maps every non-empty finite sequence () of elements of Σ to a finite sequence () of the same length of nonnegative numbers whose average is at most 1 (i.e., satisfying (1)).

To apply split conformal e-prediction to a training set , we split it into two parts, the and the calibration set . For a new object x and a potential label y for it, we set

where is defined using the following steps:

For many choices of A and N, the split conformal e-predictor (2) will be computationally efficient; this is the case when:

1. Processing the training set proper only once, we can find an easily com- putable rule transforming z into ).

2. The normalizing transformation N is easily computable.

An example of an easily computable normalizing transformation is

where the summary space is supposed to be (0). Proposition 1, our statement of validity, continues to hold for split conformal e-predictors.

4 Cross-conformal e-predictors

A Σ-valued split conformity measure A is a Σ-valued cross-conformity measure if ) does not depend on the order of its first m arguments. Given such an A and a normalizing transformation N, the corresponding cross-conformal e-predictor (CCEP) is defined as follows. The training sequence is randomly split into K non-empty multisets (, k = 1, . . . , K, of equal (or as equal as possible) sizes , where is a parameter of the algorithm, () is a partition of the index set {1, . . ., n}, and consists of all . For each and each potential label of the new object x, find the output of the split conformal e-predictor on the new object x and its postulated label y with as training set proper and as calibration set, where := is the complement to the fold . The corresponding CCEP is defined by

(A slight modification, still provably valid, of this definition is where the arithmetic mean is replaced by the weighted mean with the weights proportional to the sizes of the folds.)

Proposition 1 still holds for cross-conformal e-predictors; this trivially follows from the arithmetic mean of e-values being an e-value.

Remark 2. To compare the outputs of cross-conformal p-predictors (CCPP) and CCEP, we can use the rough transformation discussed in [10]: a p-value of p roughly corresponds to an e-value of 1/p. Under this transformation, the arithmetic average of e-values corresponds to the harmonic average of p-values, and the harmonic average is always less than or equal to the arithmetic average [5, Theorem 16]. This suggests that CCEP produce better results than CCPP do. In the opposite direction, the arithmetic average of p-values corresponds to the harmonic average of e-values, which again suggests that CCEP produce a better result than CCPP do.

5 Validity in the time domain

Advantage 1 of conformal p-prediction given on p. 1 is that, when discussing validity, we can talk about probabilities instead of p-values. It mostly disappears when we move to conformal e-prediction: validity has to be defined in terms of e-values (however, it has been argued [7] that e-values are more intuitive than p-values). In this section we discuss advantage 2, which requires the online mode of prediction. We will see that it still holds, albeit in a weakened form.

The notion of validity asserted in Proposition 1 (applied to CCEP) is stated in the “space domain”: the output of the CCEP on the true label is an e-value, i.e., its mean value at a fixed time over the probability space does not exceed 1. Now we will complement the validity in the space domain by the validity in the time domain assuming that the CCEP is bounded.

In the online prediction protocol, we observe an object , apply the CCEP to compute the values ) for all possible labels , observe the true label , observe another object , apply the CCEP to compute the values ) for all possible labels , observe the true label , etc. Remark 3. Intuitively, using CCEP in the online mode defeats the purpose of cross-conformal prediction: once we process , we would like to apply the rules that we have found (see item 1 on p. 4) to a large number of new objects rather than just one. But more realistic settings are also more complicated.

Let the values for the true labels be := ). It follows from, e.g., [9, Lemma 3.15] that, if the observations () are IID,

We can see that the long-term time average of the values for the true labels is bounded above by 1. In this sense they are time-wise e-values.

Acknowledgments

This research was partially supported by Astra Zeneca and Stena Line.

References

[1] Special issue on p-values. American Statistician, 73(Supplement 1), 2019.

[2] Rina Foygel Barber, Emmanuel J. Cand`es, Aaditya Ramdas, and Ryan J. Tibshirani. Predictive inference with the jackknife+. Technical Report arXiv:1905.02928 [stat.ME], arXiv.org e-Print archive, December 2019.

[3] Alex Gammerman, Vladimir Vapnik, and Vladimir Vovk. Transduction in pattern recognition, 1997. Manuscript submitted to the Fifteenth International Joint Conference on Artificial Intelligence in January 1997. Extended version published as [4].

[4] Alex Gammerman, Vladimir Vovk, and Vladimir Vapnik. Learning by transduction. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pages 148–155, San Francisco, CA, 1998. Morgan Kaufmann.

[5] G. H. Hardy, John E. Littlewood, and George P´olya. Inequalities. Cambridge University Press, Cambridge, second edition, 1952.

[6] Henrik Linusson, Ulf Norinder, Henrik Bostr¨om, Ulf Johansson, and Tuve L¨ofstr¨om. On the calibration of aggregated conformal predictors. Proceedings of Machine Learning Research, 60:154–173, 2017.

[7] Glenn Shafer. The language of betting as a strategy for statistical and scien- tific communication. The Game-Theoretic Probability and Finance project, http://probabilityandfinance.com, Working Paper 54, October 2019 (first posted March 2019).

[8] Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74:9–28, 2015.

[9] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer, New York, 2005.

[10] Vladimir Vovk and Ruodu Wang. Combining e-values and p-values. Technical Report arXiv:1912.06116 [math.ST], arXiv.org e-Print archive, December 2019.

[11] Vladimir Vovk and Ruodu Wang. Combining p-values via averaging. Tech- nical Report arXiv:1212.4966 [math.ST], arXiv.org e-Print archive, October 2019. Journal version: Biometrika (to appear).