Approximation to Object Conditional Validity with Inductive Conformal Predictors

Conformal predictors are machine learning algorithms that output prediction sets that have a guarantee of marginal validity for finite samples with minimal distributional assumptions. This is a property that makes conformal predictors useful for machine learning tasks where we require reliable predictions. It would also be desirable to achieve conditional validity in the same setting, in the sense that validity of the prediction intervals remains valid regardless of conditioning on any particular property of the object of the prediction. Unfortunately, it has been shown that such conditional validity is impossible to guarantee for non-trivial prediction problems for finite samples. In this article, instead of trying to achieve a strong conditional validity result, the weaker goal of achieving an approximation to conditional validity is considered. A new algorithm is introduced to do this by iteratively adjusting a conformity measure to deviations from object conditional validity measured in the training data. Along with some theoretical results, experimental results are provided for three data sets that demonstrate (1) in real world machine learning tasks, lack of conditional validity is a measurable problem and (2) that the proposed algorithm is effective at alleviating this problem.


Introduction
In some predictive analytic tasks it is useful to provide a prediction set of possible outcomes rather than a single point prediction. For example, a doctor diagnosing a patient's symptoms may find it more valuable if an automated decision support system suggested two or more possible causes instead of just one, if there is some ambiguity in diagnosis [Nouretdinov et al., 2014]. Or, given the uncertainty in property sale prices, it may be better if an automated valuation model provides a range of possible predicted sale prices, rather than a single point estimate. Indeed, for automated valuation, the delivery of a property price range is the norm; see e.g. [Bellotti, 2017] or www.zoopla.co.uk.
The conformal predictor (CP) is a machine learning algorithm that is able to generate prediction sets with a guarantee that its prediction sets are correct, i.e. the true label 1 will be a member of the prediction set, at a preset confidence level [Vovk et al., 2005]. We therefore say that the CP is a valid predictor. Other statistical methods based on frequentist and Bayesian approaches exist that promise the same guarantee, but only with some specific distributional assumptions. When those assumptions do not hold true, validity is no longer guaranteed. In contrast, CPs require only the assumption of exchangeability of data. Hence the CP is referred to as distribution-free [Lei and Wasserman, 2014]. Central to the CP is the use of a conformity measure (CM) that, given a new example, provides a measure of how typical it is of the population. Often the CM is based on some underlying machine learning algorithm, although this is not essential. The CP has been applied successfully in many problem domains including medical and financial, anomaly detection and network traffic applications, amongst others; see e.g. Balasubramanian et al. [2014].
Since the accuracy of CP is essentially fixed, the optimization task is to maximize the efficiency of the prediction sets which is some measure of the information given by the prediction set. There are multiple alternative measures of predictive efficiency, or conversely, predictive inefficiency [Vovk et al., 2016]. For example, Colombo and Vovk [2020] optimize on the object fuzziness of the predictions. Another approach is to build CPs that minimize the mean width of prediction intervals for regression [Bellotti, 2020] or mean prediction set size for classification. This is also the approach used for Prediction Interval Neural Networks [Khosravi et al., 2011, Pearce et al., 2018. For clarification, Examples 1 and 2 give two cases of what is meant by predictive efficiency.
The CP guarantees marginal validity: that is, across the whole population of observations, the accuracy of the CP will meet the confidence level preset by the user. However, even with marginal validity, there may be some sub-segments of the population for which accuracy is greater or less than the confidence level. Here are two examples demonstrating why this may be a problem.
• Medical example. If diagnosing a disease, we may have a CP that gives 95% accuracy guaranteed across all people. However, for a particular racial minority group, it gives only 85% accuracy, whilst for the majority racial group it gives 96% accuracy. This is clearly a problem for two reasons: (1) it makes clinical decisions less precise, especially for hospitals operating with a higher racial minority demographic, (2) it leads to medical decision support that is discriminatory.
• Business example. Suppose we have an automated valuation model (AVM) that gives good property price prediction intervals at 90% confidence levels across UK. However, for the particular county of Devon its accuracy is only 75%. This could adversely affect the business of any real estate company or mortgage provider operating in Devon who use the AVM. Worst still, the weakness of the AVM in their location may not even be known and so they will be operating under the misconception that the AVM is guaranteed to be 90% accurate: it is in general, but not for them.
For this reason, conditional validity has been identified as an important criterion, alongside marginal validity and predictive efficiency, for CP and indeed any algorithm generating prediction sets. That is, ideally, the validity should hold conditional on any underlying segmentation of the population. There are alternative forms of conditional validity depending on the type of information that accuracy is conditioned on. Vovk [2013] identifies (1) label conditional validity for conditioning on the label, (2) object conditional validity if conditioning on the features of each example (as opposed to the label) and (3) training conditional validity for conditioning on a property of the training set. We can also consider combinations of these types, so if we are interested in object and label conditional validity together, we call this example conditional validity. Lei and Wasserman [2014] construct a CP which has asymptotic object conditional validity and asymptotic efficiency in the number of examples used in development (more precisely: in the calibration set), basing their CM on a conditional kernel density estimator. However, for practical purposes and in this article we are interested in finite sample results. McCullagh et al. [2009] present provably conditionally valid prediction intervals, for the finite sample case, based specifically on linear regression, although other parametric models could be used, assuming some known probability distribution. However, it has been shown that it is impossible to meet the criterion of conditional validity in the finite sample case for non-trivial problems in the general case [Vovk, 2013, Lei andWasserman, 2014]. Both papers suggest label-conditioned CPs for classification as a way to address this problem. More generally, a conditional CP can be used that allows the user to specify a taxonomy of data into finite categories and then the CP is valid within those pre-defined categories [Vovk, 2014]. However, these approaches are problematic since (1) they limit the conditional validity to just some finite pre-defined categories and do not apply generally to any taxonomy, and (2) the effectiveness of the CP is reduced with the more categories included in the taxonomy, since the conditional CP essentially relies on a separate CP for each segment of data, limiting these approaches for practical use with large taxonomies.
These practical limitations with conditional validity have led Barber et al.
[2020] to proprose relaxing the requirement for conditional validity and to explore using an approximation to conditional validity. They set up a framework called distributionfree approximate conditional coverage meaning that conditional validity should be true for at least some pre-defined proportion of the population, which is similar to the PAC-type conditional validity given by Vovk [2014]. However, in the general case, they find that it is also impossible to meet this broad target. They make further progress proposing restricted conditional coverage to provide local conditional validity in the neighbourhood (ball) around some point. This is a promising approach and they show that CP satisfies this condition, but only for the case of CP for regression with the standard CM. Additionally, they identify computational difficulties with this method that require further research. The development of the normalized CM for regression [Papadopoulos et al., 2002] is an approach which can be seen as addressing this problem since the normalization factor allows more difficult prediction cases to be given wider prediction intervals, hence increasing their probability of being correct, and vice versa for easier prediction cases. However, it is a heuristic approach since it does not directly optimize for approximation to conditional validity and there has been little investigation of its effectiveness for approximation to conditional validity.
It may be supposed that pursuing the goal of maximizing predictive efficiency may align with conditional validity, in some sense. However, Example 3 gives a simple case demonstrating predictive efficiency is not consistent with conditional validity. In this paper, we focus on object conditional validity. The medical and business examples given above are both examples of this. We demonstrate that lack of object conditional validity is a genuine problem for CP through experiments with three data sets and alternative CPs; and, secondly, propose a new iterative feedbackadjusted conformity measure (IFACM) algorithm that can be used as part of an inductive conformal predictor (ICP) to achieve approximation to object conditional validity (AOCV), although in a different sense to Barber et al. [2020]. We provide some theory and experimental results. The methodology is based on ICP since ICP is a practical version of CP appropriate for batch machine learning. The proposed IFACM algorithm works from the proposition that (1) the AOCV of an ICP can be estimated using a meta-model, and (2) this meta-model can then be used to adjust the CM thus forming a new ICP which is able to achieve better AOCV on the same problem. This process can be repeated until no improvement in AOCV can be acheived. Finally, this algorithm will output a CM formed as layers of adjustments to some base CM. The algorithm is similar in approach to that of boosting algorithms that are used to reduce errors on point predictions through layers of simple predictive models [Freund and Schapire, 1999].
The remainder of this article is organized as follows. Section 2 introduces CP and the proposed IFACM algorithm, Section 3 presents some experimental results for both regression and classification, demonstrating the effectiveness of the proposed algorithm to achieve AOCV and conclusions are given in Section 4. The Appendix provides supporting theoretical results. Abbreviations used in this article are listed in Table 1  Example 1. Suppose a disease subtype needs to be diagnosed and it must be one of A, B or C. If the predictor outputs the prediction set {A, B, C} then it provides no new information at all, since the prediction set just states that the subtype is any of those available. The most informative prediction is the prediction singleton set, say {B}, since this isolates one single case. The prediction set {A, B} offers some information (by excluding C) but is not as informative as the singleton set. Hence this example suggests that cardinality of the prediction set is a good measure of predictive inefficiency.
Example 2. Suppose property price is predicted and a prediction interval [230,534] (in '000 GBP) is given. Then this range is rather broad and may not be particularly useful to a real estate agent. If the prediction algorithm is improved to give prediction interval [240,350] then this may prove an informatve and useful prediction. Hence, this example suggests that width of prediction interval would be a good measure of predictive inefficiency. For these particular examples, the predictive inefficiency would be 304 and 110 respectively.
Example 3. A simple example is constructed to demonstrate that finding the most efficient prediction intervals, on average, whilst maintaining marginal validity, leads to conditionally invalid prediction intervals.
By the law of total probability, Measure inefficiency as width of the prediction interval, then minimizing mean inefficiency is minimizing With the marginal validity constraint above, this is a simple linear programming problem with the solution, noticing that since ε < 1 2 , b > 0 (an alternative is to use the square of prediction interval width as an inefficiency measure, in which case 1 2 a 2 + 1 2 b 2 is minimized; however, this leads to the same solution). This then leads to the two conditional probabilities of accuracy: which both deviate from the confidence level 1 − ε, hence the solution does not exhibit conditional validity.
It is possible to enforce object conditional validity for this simple example by setting a = 1 − ε and b = 2(1 − ε) so that However, mean inefficiency then increases from 3 2 − 2ε to 3 2 (1 − ε), a difference of 1 2 ε more than optimal inefficiency. Therefore enforcing object conditional validity leads to a reduction in predictive efficiency.

Methodology
We first introduce ICP and marginal validity, then discuss AOCV before introducing the IFACM algorithm. Finally we show that IFACM for regression is consistent with the normalized CM.

Inductive Conformal Predictors
We set up the ICP framework following Vovk et al. [2005].
• Let z = (x, y) denote examples from the same unknown distribution P such that x is a vector of m predictor variables x ∈ R m and label y ∈ Y for some set of labels Y.
• Let z 1 , · · · , z l be a particular sequence of examples z j = (x j , y j ) from P .
• Let 1 to k index the training data set and k + 1 to l index the calibration set, for 1 < k < l.
• A conformity measure (CM) is any computable function for all permutations π of 1, · · · , k. For convenience, we will sometimes use A(x, y) to denote A(z).
• Let ε be a preset significance level, so 1−ε is the confidence level for predictions.
We typically consider a CM having the form A(z) = A p (θ, z) for some parameters θ = M (z 1 , · · · , z k ) where M is intended to be a model structure within which θ are estimated based on data z 1 , · · · , z k . For example, for regression, M could be ordinary least squares (OLS) linear regression and θ, the vector of coefficients in the OLS linear regression model; or M could be an artificial neural network with θ the vector of weights in the network. The ICP is defined as the prediction algorithm that gives the prediction set at significance level ε for a new example x, based on the calibration set of examples k + 1 to l as where I is the usual indicator function. This prediction set is dependent on the CM used so this is made explicit on the left-hand side of the expression. Assuming only that the calibration data set, z k+1 , · · · , z l , and any new test or operational data sets are exchangeable, ICP predictions on the new data are marginally valid: (2) for each new example (x, y) 2 . When the label set Y is finite, this is ICP for classification. When Y = R, this is ICP for regression. For these two cases, we can consider two particular CMs that are common in the literature.

Scoring CM
A scoring function f : R m × Y → R for which a higher output of f (x, y) means that label y is (in some sense) more likely to be associated with example x, then f itself can be used directly as a CM. An example of this is multinomial logistic regression for classification which estimates coefficient vectors β y for each possible label y ∈ Y such that f (x, y) = β y · x is the logodds of y conditional on x. We will use the multinomial logistic regression scoring function in the later experimental section.
Normalized CM In the case of regression, a typical choice is the normalized nonconformity measure: whereŷ is a point estimate based on a regression model of y andσ > 0 is some estimate of uncertainty in the prediction given by the model [Papadopoulos et al., 2002]. Both can be computed from models estimated from training data, z 1 , · · · , z k . For later experiments in this article, OLS linear regression of y is used for the numerator and a OLS linear regression of the log of absolute residual is used for σ following Papadopoulos et al. [2002]. For consistency, we use CM for this study and a normalized CM can be constructed as the reciprocal of the normalized nonconformity measure A N (x, y) = 1/N (x, y).
For the normalized nonconformity measure thus forming a prediction interval, where q is the ε-quantile of the empirical distribution of CM values within the calibration set. In the special case when σ = 1, this gives the standard CM. As can be seen from (4), the standard CM always gives the same fixed width 2q for prediction intervals. The introduction of the normalizing denominator allows for variation in the prediction interval width and hence form a CP that has varied prediction interval widths according to the difficulty of the observation, with observations that are more difficult to predict having wider prediction intervals.

Approximation to Object Conditional Validity
As discussed earlier, it would be valuable to achieve object conditional validity given by for all x ∈ R m , but, in the nontrivial case, this is impossible to achieve for CPs as shown byVovk [2013] and Lei and Wasserman [2014]. Instead we consider relaxing the constraint and allow for AOCV given broadly by This requirement can be made more precise by expressing it as minimizing the square difference across the population, This approach to AOCV is quite different to Barber et al. [2020] who, instead, consider proportions of the population that are exactly conditionally valid as an approximation method. After conformal predictions are made on a data set indexed by some index set S, (5) is estimated as is some probability estimator. The probability estimator can be logistic regression, k-nearest neighbours (k-NN) or any other probabilistic model taking training data indicates whether the prediction set for example j is correct. Therefore, this measure can be used to quantify AOCV. We take the square root of this estimate, so that the measure is on the same scale as the conditional probability. Hence the root mean square error gives deviation from conditional validity (DCV), If an ICP is conditionally valid then DCV(A) ≈ 0. The closer it is to zero, the better the AOCV exhibited by the ICP. Essentially p(z; A) ≈ 1 − ε indicating an uninformative model. For example, using logistic regression for p, the coefficient estimates will be close to zero and statistically insignificant. On the other hand, a low value of DCV does not guarantee conditional validity, since it only reflects the model structure that is used to construct the probability estimate, such as logistic regression, and not all possible conditionalities in the data. However, it will be a good indicator of AOCV for practical purposes.

Iterative Feedback-adjusted Conformity Measure
Consider constructing CMs that seek to minimize DCV(A). Our proposal is to extend an existing base CM A which may have a high DCV with another as follows: where γ > 0 is a control parameter, U is an update function based on the discrepency between estimated probability given A and confidence level, with the properties, where the underlying estimator p is exchangeable, i.e. the estimates are invariant to the order of the training examples. This ensures that A * γ is also a CM. This exchangeability condition is true of most probabilistic estimators and, in particular, is true of logistic regression and k-NN where the order of training examples is irrelevant. Hence, if the training data for p is independent of calibration and test data, then the use of A * γ in an ICP guarantees marginal validity (2).
The inituition for the update function is that if the conditional probability of being correct is too low, then we increase the CM so that the correct label has more chance of being in the prediction interval (1), hence increasing the conditional probability of being correct if ICP is rerun with the updated CM, and vice versa, for conditional probabilities that are too high, the CM value is lowered following the update, thus making it less likely that the prediction is correct.
A specific update function considered in this study is where δ ≥ 0 is a sensitivity parameter. Notice that U * is not dependent on y but this is not a problem, since A is expected to provide discrimatory power for the ICP, whilst U * just provides an adjustment to lead the ICP to achieve better AOCV. Ideally we would like to prove that adjusting by U * will improve AOCV in some way: perhaps showing that DCV is reduced. However, this seems difficult to achieve, at least in the general case, and remains an area for further research. However, it is possible to prove that applying U * adjustment to the CM does improve the average log-odds of being correct for those observations whose outcome (i.e. c j ) is switched by the adjustment, so that it is closer to the target confidence level, in the case when logistic regression is used as the probability estimator p. Technical details are provided in Appendix A.
The updated CM A * γ is optimized with respect to γ and δ using the training data set with the goal to minimize the DCV measure. There is no gradient that can be used for optimization but with only two parameters to minimize across, Nelder-Mead optimization [Nelder and Mead, 1965] is adequate for this task. Since both parameters are greater or equal to zero, the optimization is performed over the logarithm of the parameters.
The U * update function is rather simplistic and one application of an update may provide just a small improvement in DCV. However, since the update A * is itself a CM, the application of the update function can be applied iteratively, minimizing DCV at each iteration, until it cannot be minimized any further. Representing the CM recursively: for parameters γ i > 0 and δ i ≥ 0 that are computed at each iteration to minimize DCV. Importantly, the probability estimator (6) is re-estimated at each iteration based on the ICP with the current version of A * [i] . Then the output after n u iterations is the IFACM expressed as the weighted sum, This use of iterative modifications to the CM based on feedback from previous stages of the ICP performance mirrors the method of boosting that is used to reduce errors iteratively by giving greater weight to examples with errors from previous iterations in each model build at the next iteration. We would expect that the process of adjusting the CM by iterative updates will lead to reduced DCV, but on the other hand, that there will be a trade-off in an increase in predictive inefficiency. Hence, to mitigate against this the optimization task is modified to minimize at each iteration i, where I is an inefficiency measure for predictions made using the CM on index set S and C ≥ 0 is a control hyperparameter. There are several alternative measures of prediction inefficiency [Vovk et al., 2016]. In this study, the mean size of prediction sets is used, For classification, the size is the cardinality of the prediction set. For regression, using normalized CM, the size is the width of the prediction interval.
The method is introduced with the abstract set S. However, in practice, this would typically be the training data; i.e. S = {1, · · · , k}, in order to conserve data. The consequence of this is that the ICP constructed at each iteration of the algorithm is not marginally valid since the training, calibration and independent test sets all coincide, leading to overfitting. However, ultimately this is not a problem since the IFACM that is computed is subsequently an input to a proper ICP that does have an independent calibration set and independent testing (or operational) data. Algorithms 1 and 2 show how to compute the IFACM that can then be used within an external ICP with an independent calibration data set.
Algorithm 1: Run ICP on training data to measure DCV input : Train = training data set, CL = confidence level, A = conformity measure. Compute prediction intervals PI for all observations in Train using ICP with A, CL and Train as the calibration data set; Construct a probabilitic model M of the correctness of PI on Train ; Compute DCV of M predicting on Train, relative to CL ; W ← mean width of PI, using (9) ; output: DCV, W

IFACM and Normalized CM
The CM A * * is consistent with the normalized CM for regression. To see this, first observe that applying a monotonically increasing transform to a CM does not change the behaviour of the ICP since it is the rank ordering of CM that matters, as can be seen in (1). Therefore, taking base A(x, y) = log σ − log |y −ŷ| and applying the exponential function to (7) gives Algorithm 2: Iterative feedback-adjusted conformity measure (IFACM) input : Train = training data set, CL = confidence level, C = control parameter in equation (8), Run Algorithm 1 multiple times with input: Train, CL, A + γ i U * (.; A, δ i ) to minimize DCV + C(W − W 0 )I(W > W 0 ) with respect to γ i , δ i using the Nelder-Mead algorithm (i.e. minimize (8) with respect to γ i , δ i ) ; DCV 2 ← DCV from the minimization step above ; if DCV 2 < DCV 1 then Since the exponential function is monotonically increasing, this CM will give the same ICP as (7), except in the transformed version it can be seen that this is the normalized CM with an extra product update. Indeed, the update functions can be interpreted as a further normalizing factor in the CM. Therefore from (4), the prediction interval yielded by this CM for regression is whereσ =σ exp nu i=1 γ i U * (x, y; A, δ i ) .

Experimental settings and results
Experiments were conducted with three data sets listed in Table 2. Data set "covtype" has outcome identifying tree cover type for different forest locations. It is used in this study since it is a large multi-class classification problem. Data set "GPU" provides GPU performance data for different GPU settings, outcome is average performance time and it is a large regression data set [Nugteren and Codreanu, 2012] . Data set "KC" (King's County) contains US housing data and the outcome variable is property sale price. It is a smaller regression problem but is interesting for this study since the normalized CM gives improved performance over the standard CM, which was not the case with the GPU regression problem. Both "covtype" and  Parameter settings are as follows:- • Confidence level. For all experiments, confidence level is set to make the problem sufficiently hard that predictive efficiency becomes a challenge. For "covtype" this is 0.95 and for "GPU" and "KC" it is 0.9. Additionally a confidence level of 0.99 is also used for "GPU" to explore the consequences of high confidence levels. • Base CM. For classification, the multinomial scoring CM is used as base CM, whereas normalized CM is used for the regression problems. Additionally standard CM for regression is used for "KC" to explore if normalized CM improves on standard CM in terms of AOCV. Both use a base OLS linear regression model for point estimates ofŷ and normalized CM also uses OLS linear regression for estimates of logσ for (3). • Probability estimator. Logistic regression is used as the probability estimator (6). • C: penalty hyperparameter in (8). For "covtype", it was possible to achieve good results with C = 0. However, for the other data sets, C = 0 leads to huge predictive inefficiency, hence a value of C = 0.5 is used instead. For contrast, C = 5 is also used. • Nelder-Mead optimization. Low starting values log γ i = −5, log δ i = −5 were used when minimizing (8).
Results are shown in Table 3. The main points that we find are as follows.
• For all experiments, the IFACM algorithm successfully reduces DCV on both the training and test data sets, whilst maintaining marginal validity (i.e. Acc. ≈ CL). • As expected, the reduction in DCV comes at the cost of increase in predictive inefficiency and this is controlled by the hyperparameter C. However, the impact of this trade-off is different for each data set. For "covtype", inefficiency increases from 1.78 to 1.84 for the best improvement in DCV (when C = 0, lines 3-4), whereas taking C = 5 will yield better inefficiency (1.80) but the DCV more than doubles, so the impact of the trade-off between DCV and inefficiency is high for this data set. However, for "GPU", a low DCV is measured with minimal increase in inefficiency when C is low (lines 11-12). Surprisingly, when a high confidence level is used, IFACM yields lower inefficiency even with low DCV (lines 15-18). Whether this is a general result requires further investigation, but at the very least it demonstrates that for "GPU", the impact of applying IFACM on inefficiency is minimal.
• In many cases, DCV is much lower on the training data set compared to the test set. This is especially the case when low values of C are used (compare line 11 to 12 and 25 to 26). This suggests that in some situations, the IFACM algorithm gives rise to a large degree of overfit for the goal of minimizing DCV. For these data sets, it does not give rise to a significant problem with performance on the test data; however, it is worth some further investigation.
• Lines 19-22 demonstrate that for the "KC" regression problem, using NCM gives lower predictive inefficiency than the standard CM which confirms what we expect from previous work (e.g. [Papadopoulos et al., 2002]), but also interestingly the normalized CM is able to reduce DCV on training and test data (lines 21-22), which is expected by construction of the normalized CM. Nevertheless, we see that applying IFACM with the normalized CM as base CM allows for even further reduction in DCV. Using C = 5, IFACM is able to achieve this with only a small increase in inefficiency (lines 29-30). Interestingly, applying IFACM on the standard CM gives improvement over standard CM, but is not as good as IFACM applied to normalized CM in terms of either inefficiency or DCV measures (compare lines 27-28 to 29-30). This is important since it shows that IFACM cannot simply replace a good base CM (i.e. the normalized CM) but is a supplement to an existing base CM, for the purpose of achieving AOCV.
We can look in further detail at the behaviour of the IFACM algorithm.
• Figure 1 shows the coefficient estimates for each of the variables in "GPU" using the logistic regression probability estimator p in (6), before and after IFACM is applied, corresponding to lines 10 and 12 of Table 3 respectively. Since data has been standardized, the magnitude of the coefficients are comparable. The left graph shows the result on training data: in this case, the reduction in magnitude of coefficients is large, leading to an uninformative model after IFACM (i.e. coefficients ≈ 0) 3 . The right graph shows coefficients on test data: overall, there is a reduction in magnitude, but it is not as pronounced as with training data and some coefficients actually become larger in magnitude. This demonstrates there is overfitting with this algorithm, i.e. it does not perform so well on test data as training, in terms of AOCV, corroborating the results for DCV given in Table 3.
• Table 4 shows the sequence of values of parameters γ i and δ i estimated in several experiments. They show that the number of iterations of the IFACM algorithm is not large, with maximum 5 in our experiments. Also, the number of iterations goes down as C increases, showing that greater control of inefficiency means less precision with the feedback adjustment. The sequence of values of γ i decreases with each iteration, as the magnitude of the adjustment at each iteration is reduced. Finally, however, we notice no particular pattern with the sequences of δ i values. Figure 1: Change in coefficient estimates in probability estimator p before (dark grey) and after (light grey) applying the IFACM algorithm on "GPU" training data (left) and test data (right).
• Although DCV reported in Table 3 measures average deviation from conditional validity across the whole data set, to convince ourselves that the method is effective, it is also valuable to show accuracy for different sub-segments of the data. Therefore, as an illustration, Table 5 shows this for several segments in the test data sets. These segments are chosen as deviating greatly from the confidence level when the Base ICP is used. The results show that for each of these segments, using IFACM makes a considerable difference, giving accuracies much closer to the target confidence level, within each segment, as required for AOCV. So, e.g. in "covtype", for V43 we can see a bias in accuracy with better performance for V43=1 (accuracy=0.973). However, once IFACM is used, this bias is reduced and accuracy for V43=1 becomes closer to the target confidence level 0.95 (accuracy=0.955). Although improvements in AOCV are observed within all segments, some segments receive greater improvement than others. For example, in "GPU", the improved AOCV is much better for KWG than for the segment MWG=64.
• The code was written in R and was run on a PC with a processor running at 2.1 GHz with 16GB RAM. The Nelder-Mead optimizer was set to take no more than 100 steps each iteration of the IFACM algorithm. The computation times for training in Algorithm 2 on "covtype", "GPU" and "KC" data sets (corresponding to lines 3, 11 and 25 of Table 3, respectively) were 6125, 225 and 51 seconds respectively. The much longer running time for "covtype" was a consequence of a larger training data set size and larger number of iterations, n u .

Conclusion
The IFACM algorithm is introduced as a mechanism to iteratively update a base CM in order to adjust the conditional probability of a predictive interval being correct so that it is close to the target confidence level across the population and hence achieve AOCV. The experimental results provide good evidence that IFACM algorithm works well at this task, whilst maintaining marginal validity when the IFACM is used in the ICP. There is a cost in terms of increased predictive inefficiency, but the impact of that cost differs by data set and for all the data sets used in this study, the cost is not too onerous with the correct choice of hyperparameter C.
The results show that deviation from object conditional validity can be high and hence we recommend that developers using ICP should control for all three objectives: • Marginal validity: guaranteed by (2) for any ICP with independent and identically distributed training, calibration and test (or operational) data; • Predictive inefficiency: needs to be minimized; e.g. minimizing mean prediction interval width (9) for regression; • Deviation from conditional validity (DCV): needs to be minimized; this is the main objective of this study.
This article introduces the problem and proposes the novel IFACM algorithm with some initial experimental results that demonstrate that the algorithm is effective. There remain several avenues for further research.
1. Further benchmark studies on different data sets, different underlying machine learning algorithms for the base CM and alternative U update functions. 2. Exploring the effect of data set size and model complexity for the overfitting problem identified in the experimental results. 3. Testing alternative probability estimators p, such as nonparametric k-nearest neighbours, or estimators that could alleviate the overfitting problem, such as those using regularization. 4. The theoretical results given in the Appendix show that the behaviour of the update function is appropriate; however they are not complete and there is room for further theoretical work to help prove that improved AOCV can be achieved using IFACM. 5. As recommended above, CP should be built taking into account minimizing both predictive inefficiency and DCV. Colombo and Vovk [2020] and Bellotti [2020] propose methods specifically for minimizing predictive inefficiency, whilst this article focusses just on DCV. It would be interesting to develop a method that integrates both approaches. This is not straightforward since the optimization methods are quite different in each case. 6. This study only considers object conditional validity. It would be interesting to extend to other forms of conditional validity, such as label or example conditional validity.

A Theoretical Results
Some theoretical results for the update function U * with the logistic regression probability estimator p are given in Theorems 1 and 2 below. More generally, these results apply to any estimator using a binomial likelihood function (e.g. probit regression). Then, g(β) ≥ g(α).
Definition 1. The binomial log-likelihood for data set E of observations (x, c) ∈ E with c ∈ {0, 1}, for some parametric model with coefficients β, is Definition 2. The sample mean of conditional log-odds of c ∈ {0, 1} over data set , · · · , n}} for some n ≥ 1. Suppose S ⊆ {1, · · · , n}. Let Then since D T has the same observations as D S but only differs in outcome, Notice that the outer min is needed to deal with the case when two indexes both give the same minimum for the inner arg min.
• Base step, for γ < γ 1 : q(γ) remains the same value, i.e. i = q(γ) = q(0), so t(0) = A(z i ) and • Inductive step (1), for γ = γ k for some k ≥ 1: • Inductive step (2), for γ > γ k for some k ≥ 1 and γ < γ k+1 if k < K: There is no change in q(γ) from γ k to γ, hence i = q(γ) = q(γ k ). Therefore, Let the training data set and calibration data sets coincide so that observation i is the same as i + k for 1 ≤ i ≤ k and l = 2k for the ICP used in Algorithm 1.
Suppose A * γ (x, y) < t(γ), since t(γ) is the smallest value for which Definition 3 holds, then Since l = 2k and all observations i are the same as i + k, substituting A * γ for A, (1) gives Considering (11) and (12), it immediately follows that The prediction for observation i is correct if and only if Use an indicator variable to express this: . Definition 6. Suppose S is an index set of observations and let the data set of be the vector of coefficients using logistic regression as probability estimator for the correctness of the prediction intervals.
We use the notation for the probability estimator in (6) but since we use logistic regression, we supplement it with the coefficients β as an additional argument: p(z; A, β). For convenience, let p i = p(z i ; A,β(0)); i.e. the probability estimate from the base ICP using CM A.
We now have a framework in place to prove our result. Our idea is that, for a particular example z i , for any feedback-adjusted weight γ > 0 and sensitivity δ ≥ 0: 1. if c i (0) = 0 and p i < 1 − ε and c i (γ) = 1, then we expect p(z i ; A * γ ,β(γ)) > p i ; 2. if c i (0) = 0 and p i > (1 − ε) + δ, then c i (γ) = 0; 3. if c i (0) = 1 and p i < (1 − ε) − δ, then c i (γ) = 1; 4. if c i (0) = 1 and p i > 1 − ε and c i (γ) = 0, then we expect p(z i ; A * γ ,β(γ)) < p i . Line 1 states that if the conditional probability of being correct is biassed below confidence level then if the feedback-adjusted update by γ switches it to correct, this should increase the conditional probability of being correct. Line 4 states a similar objective but, vice versa, for bias above the confidence level. Both lines 1 and 4 will have the effect of shifting the conditional probability of being correct towards the confidence level. Line 2 states that if the conditional probability is biassed above confidence level but the outcome is already incorrect, then the feedback-adjusted update for any value γ will not change that outcome, since that will not help move the conditional probability towards the confidence level. Line 3 states a similar requirement, vice versa, for bias below confidence level. The following Theorem proves lines 2 and 3.
Proof. Take c i (0) as outcome variable c i , n = k, and S = {i ∈ {1, · · · , k}|c i (0) = c i (γ)}. Then since c i (γ) = 1 − c i (0) for i ∈ S, D S = S γ and DS = {(x i , c i (0))|i ∈ {1, · · · , k} and c i (0) = c i (γ)}.   (8) Table 4: Optimized values of γ i and δ i in (7) for each iteration i of Algorithm 2, for different experiments. CL=confidence level 1 − ε, C=penalty hyperparameter in (8) Table 5: Accuracies within some segments of the test data set using the Base ICP and ICP with IFACM. Each line shows accuracy measured within just the segment of observations given by the value of the variable. CL=confidence level 1 − ε, C=penalty hyperparameter in (8), # is the number of observations within the segment.