Backward-Compatible Prediction Updates: A Probabilistic Approach
Year: 2021

Abstract:
When machine learning systems meet real world applications, accuracy is only one of several requirements. In this paper, we assay a complementary perspective originating from the increasing availability of pre-trained and regularly improving state-of-the-art models. While new improved models develop at a fast pace, downstream tasks vary more slowly or stay constant. Assume that we have a large unlabelled data set for which we want to maintain accurate predictions. Whenever a new and presumably better ML models becomes available, we encounter two problems: (i) given a limited budget, which data points should be re-evaluated using the new model?; and (ii) if the new predictions differ from the current ones, should we update? Problem (i) is about compute cost, which matters for very large data sets and models. Problem (ii) is about maintaining consistency of the predictions, which can be highly relevant for downstream applications; our demand is to avoid negative flips, i.e., changing correct to incorrect predictions. In this paper, we formalize the Prediction Update Problem and present an efficient probabilistic approach as answer to the above questions. In extensive experiments on standard classification benchmark data sets, we show that our method outperforms alternative strategies along key metrics for backward-compatible prediction updates.

heading: 1 Introduction
text: The machine learning (ML) community develops new models at a fast pace: for example, just in the past year, the state-of-the-art on ImageNet has changed at least five times [9, 10, 31, 50, 51]. As reproducibility has increasingly been scrutinized [33, 34, 42], it is now common practice to release pre-trained models upon publication. In this work we take the perspective of an owner of an unlabelled data set who is interested in keeping the best possible predictions at all times. When a new pre-trained model is released, we face what we refer to as the Prediction Update Problem: (i) decide which points in the data set to re-evaluate with the new model, and (ii) integrate the new, possibly contradicting, predictions. For this task, we postulate the following three desiderata:
1. The prediction updates should improve overall accuracy. 2. The prediction updates should avoid introducing new errors. 3. The prediction updates should be as cheap as possible since the target data set could be huge.
∗Work done while FT and JvK were interning at Amazon. †Correspondence to: frederik.traeuble@tuebingen.mpg.de and pgehler@amazon.com
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We consider the setting in which the target data set for which we wish to maintain predictions is fully unlabelled (i.e., the ground-truth labels are unknown) and may come from a different distribution than the one on which models have been pre-trained, but with overlap in the label space. This is a transductive or semi-supervised problem, but, due to computational constraints, we avoid any model fitting or fine-tuning and rely solely on the predictions of the pre-trained models that are released over time. Typically, these models exhibit increased performance on their labelled training domain (e.g., the ImageNet validation or test set) as evidence for being good candidates for re-evaluation.
Clearly, one goal of updating the predictions stored for the target data set is to improve overall performance, e.g., top-k accuracy for classification. At the same time, the stored predictions may form an intermediate step in a larger ML pipeline or are accessible to users. This is the reason for our second desideratum: we would like to be backward-compatible, i.e., new predictions should not flip previously correct predictions (negative flips). Finally, we aim to reduce computational cost during inference and to avoid evaluating the entire data set which may be prohibitive in practice and unnecessary if we are already somewhat certain about a prediction.
In this paper, we motivate and formalize the Prediction Update Problem and describe its relation to various relevant research areas like ensemble learning, domain adaption, active learning, and others. We propose a probabilistic approach that maintains a posterior distribution over the unknown true labels by combining all previous model re-evaluations. Based on these uncertainty estimates, we devise an efficient selection strategy which only chooses those examples with highest posterior label entropy for re-evaluation in order to reduce computational cost. Furthermore, we consider different predictionupdate strategies to decide whether to change the stored predictions, taking asymmetric costs for negative and positive flips into account. Using the task of image classification as a case study, we perform extensive experiments on common benchmarks (ImageNet, CIFAR10, and ObjectNet) and demonstrate that our approach achieves competitive accuracy and introduces much fewer negative flips across a range of computational budgets, thus showing that our three desiderata are not necessarily at odds.
Contributions We highlight the following contributions:
• We introduce the Prediction Update Problem which addresses some common, but previously unaddressed challenges faced in real world ML systems (§ 2).
• We propose a probabilistic, model-agnostic approach for the Prediction Update Problem, based on Bayesian belief estimates of the true label combined with an efficient selection and different prediction-update strategies (§ 3).
• We contextualise this understudied problem setting as well as our method with related work (§ 4 & § 5) and discuss several extensions and limitations (§ 4).
• We demonstrate that our approach successfully outperforms alternative approaches and accomplishes all our desiderata in experiments across multiple common benchmark datasets (CIFAR-10, ImageNet, and ObjectNet) and practically relevant scenarios (§ 6).3

heading: 1.1 Backward-Compatible Prediction Systems
text: In real world ML applications, empirical performance is only one of several requirements. When humans interact with automatic predictions, they will start to build mental models of how these models operate and whether and when their predictions can be trusted. This is described as Human-AI teams by [1] who argue to “make the human factor a first-class consideration of AI updates”.
An example from [1] is autopilot functionality in cars for which drivers will build expectations in which driving situations the autopilot is safe to engage. It is important not to violate these assumptions when updating the models over the air. AI assisted medical decision processes are another example of a high stake application where medical professionals need to understand when systems can be trusted.
Consider the example of automatically tagging images in a user’s photo collection. Those tags are used for example in photo search. As models progress, the overall accuracy on all uploaded images may increase, but for any single user the experience can deteriorate if previously correct searches now show wrong results. Even worse, if errors fluctuate over the user’s photo collection as the result of prediction-updates, the user’s trust will be eroded. This “cost” is asymmetric and the negative experience may outweigh the benefit of better predictions on other images.
3All software and assets we use are open source and under MIT, Apache or Creative Commons Licenses.
In contrast to carefully curated and labelled ML benchmarks, many real-world data sets are magnitudes larger (up to billions of samples) and entirely unlabelled. Having no feedback which predictions are correct is a common scenario: consider any type of private data such as health data, photo collections, or personal information. Because the data is private, we can neither train on it, nor collect feedback, nor observe the effect of predictions. On the other hand, such data is valuable to an individual: she has an interest to keep it up to date with the best possible predictions. Since it is of little consolation to her if an update of the model improves predictions on average but on her data it gets worse, the update costs are asymmetric. Service providers often rely on models pre-trained on a different data set, and the desire to be backward-compatible arises naturally in this setting [1, 39, 43, 53].
This is an understudied problem where progress will have large impact. ML systems are becoming pervasive, and their accuracy will continue to increase. Being able to seamlessly transfer them to existing data will be crucial for real-world ML systems.

heading: 2 The Prediction Updates Problem Setting
text: Target Data Set We are given a large, unlabelled target data set Dtarg = {xn}Nn=1 comprising N independent and identically distributed (i.i.d.) observations xn ∈ X ⊆ Rd drawn from a target distribution PtargX . The ground-truth labels yn ∈ Y = {1, ...,K} distributed according to P targ Y |X are not observed. Note that we are particularly interested in a scenario where N may be extremely large.
Models Over time t = 0, 1, ..., T we successively gain access to classifiers C0, C1, . . . , CT : X → Y which have been trained on a labelled data set Dsrc from a potentially different source distribution PsrcX,Y over X × Y . For simplicity, we assume that the observation space X and label space Y are shared. We consider both the standard scenario where the models {Ct}Tt=0 are trained on a labelled set from the same domain (Psrc = Ptarg); and the transfer scenario where we deploy a model trained on a labelled ML benchmark to a different data set (Psrc 6= Ptarg). We assume that {Ct}Tt=0 are improving in performance on the training data set. Therefore, denoting by At the estimated accuracy of Ct on PsrcX,Y , we have A
t ≤ At+1 ∀t. As motivating example, consider an object recognition task in the wild and let Ct be the winning entry of the ImageNet competition in year t.
Labelling To relate the source and target distributions and to justify applying {Ct}Tt=0 to our target data set Dtarg, we make the commonly used covariate shift assumption PtargY |X = P src Y |X, i.e. the conditional label distribution is shared across source and target distributions [40, 45].4 We denote the predicted label by Ct for xn by ŷtn = C
t(xn) and the stored prediction for xn after time step t by ltn. The target data set is then initially fully labelled by C0, i.e., l0n := ŷ 0 n.
Objective As new classifiers {Ct}t≥1 become available, our main objective is to maintain the best estimates {ltn}Nn=1 on our target data set at all times and improve overall accuracy, while, at the same time, maintaining backward compatibility by minimising the number of negative flips, i.e., the number of previously correctly stored predictions that are incorrectly changed. The key challenge is that no ground truth labels for our target data set are available, so that we have no feedback on which predictions are correct and which are wrong. For each test sample xn and each time step t ≥ 1, we thus need to decide whether or not to update the previously stored prediction lt−1n based on the current and previous model predictions ŷtn and ŷ 0:t−1 n , respectively.
Limited Evaluation Budget Re-evaluating all samples (so-called backfilling) can be very costly and requires significant resources. Since we consider N to be very large, we also consider a limited budget of at most Bt ≤ N sample re-evaluations for step t. We thus additionally need to decide how to allocate this budget and select a subset of samples to be re-evaluated by Ct at every step.

heading: 3 Our Method
text: Having specified the setting, we next describe our proposed method for the Prediction Update Problem. We start by providing a Bayesian approach for maintaining and updating our beliefs about the unknown true labels as new predictions become available (§ 3.1), followed by describing strategies for selecting candidate samples for re-evaluation (§ 3.2) and for updating the stored predictions based on our changed beliefs (§ 3.3). Our framework is summarised in Figure 1.

heading: 3.1 Bayesian Approach
text: Since the true labels {yn}Nn=1 are unknown to us, we treat them as random quantities over which we maintain uncertainty estimates. We then perform Bayesian reasoning to update our beliefs as new evidence in the form of predictions ŷtn from newly-available classifiers C
t arrives over time t = 1, ..., T . In standard Bayesian notation, the true labels yn thus take the role of unknown parameters θ and the predictions ŷtn of data x. Since Dtarg is sampled i.i.d., we reason about each label yn independently of the others, i.e., the following is the same for all n.
Prior Lacking label information on the target data set, we choose a uniform prior over Y for all yn, i.e., p(yn = k) = 1/K, ∀k ∈ Y . If (estimates of) the class probabilities on Dtarg are available, we may instead use these as a more informative prior.
Likelihood Next, we need to specify a likelihood function p(ŷ0:Tn |yn = k) for the observed model predictions ŷ0:Tn given a value k of the true label yn. We make the following simplifying assumption. Assumption 1 (Conditionally independent classifiers). The different classifiers’ predictions ŷ0:Tn are conditionally independent given the true label yn, i.e., the likelihood factorises as
p(ŷ0:Tn |yn = k) = ∏T t=0 p(ŷ t n|yn = k). (1)
In a standard Bayesian setting, this corresponds to the assumption of conditionally independent observations given the parameters; we refer to § 4 for further discussion. The main advantage of Assumption 1 is that the factors p(ŷtn|yn = k) on the RHS of (1) have a natural interpretation: these are the (normalised) confusion matrices πt of the classifiers Ct, i.e., we denote by
πt(i, k) := p(ŷt = i|y = k),
the probability that Ct predicts class i given that the true label is k, which is the same for all n; see below and § 4 for more details on how we estimate πt in practice.
4In the context of image classification, this means that images of the same object under different environmental conditions (i.e., different PX) will always share the same label (i.e., same PY |X). Note that such covariate shift may also lead to changes in PY (label/target shift) and/or PX|Y (conditional shift) [44, 55].
Posterior At every time step t ≥ 0, we can then compute our posterior belief about the true label yn given model predictions ŷ0:tn according to Bayes rule,
p(yn = k|ŷ0:tn ) = πt(ŷtn,k)p(yn=k|ŷ
0:t−1 n )∑
i∈Y π t(ŷtn,i)p(yn=i|ŷ 0:t−1 n )
(2)
where we have used Assumption 1 to write p(ŷtn|yn = k, ŷ0:t−1n ) = p(ŷtn|yn = k) = πt(ŷtn, k). The posterior at step t− 1 acts as prior for step t, so we do not have to store all previous predictions. Estimating Confusion Matrices In practice, πt are generally not known and we instead use their (maximum likelihood) estimates π̂t from the source distribution. If the number of classes K is large compared to the amount of labelled source data,5 we only estimate the diagonal elements π̂tkk (i.e., the class-specific accuracies) and set the K(K − 1) off-diagonal elements to be constant,
π̂t(i, k) = 1−π̂ t(k,k)
K−1 ∀i 6= k,
so that ∑K i=1 π̂ t(i, k) = 1 ∀k ∈ Y . We refer to § 4 for further discussion on the estimation of πt.

heading: 3.2 Selecting Candidates for Re-evaluation
text: Given the label posteriors computed according to (2), we compute the Shannon entropies [38] Stn = − ∑ k∈Y p(yn = k|ŷ0:tn ) log p(yn = k|ŷ0:tn ),
which provide a simple measure of uncertainty in the true label yn after step t. We then select and re-evaluate the Bt samples with highest posterior label entropy Stn to update our beliefs.

heading: 3.3 Prediction-Update Strategies
text: Finally, we need a strategy for deciding whether and how to update the previously stored prediction lt−1n based on our new beliefs. We consider three such prediction-update strategies.
MaxBelief (MB) The simplest approach is to always update based on the maximum a posteriori belief, i.e., ltn := l̂ t n = argmaxk∈Y p(yn = k|ŷ0:tn ). We refer to this strategy as MaxBelief (MB).
MaxBeliefMinEntropy (MBME) A slightly more sophisticated approach is to also take the change in posterior entropy into account and only update when it has decreased:
ltn :=
{ l̂tn if S t n < S t−1 n ,
lt−1n otherwise.
We refer to this strategy as MaxBeliefMinEntropy (MBME).
CostRatio (CR) So far, we have not taken the assumed larger penalty for negative flips into account. We therefore now develop a third approach based on asymmetric flip costs. We denote the cost of a negative flip (NF) by cNF > 0 and that of a positive flip (PF) by cPF < 0.
We need to decide whether to update the previously stored prediction lt−1n based on our updated beliefs p(yn = k|ŷ0:tn ). Denote the MAP label estimate after step t by l̂tn = argmaxk∈Y p(yn = k|ŷ0:tn ). If l̂tn = l t−1 n there is no reason to change the stored prediction. Suppose that l̂ t n 6= lt−1n . We then need to reason about the (estimated) positive and negative flip probabilities when changing the stored prediction from lt−1n to l̂ t n. A positive flip (PF) occurs if l̂ t n is the correct label (and hence l t−1 n is not), and, vice versa, a negative flip occurs if lt−1n is correct (and hence l̂ t n is not):
p̂PFn (l t−1 n → l̂tn) = p(yn = l̂tn|ŷ0:tn ), p̂NFn (lt−1n → l̂tn) = p(yn = lt−1n |ŷ0:tn ).
If neither lt−1n nor l̂ t n are the correct label, the flip is inconsequential which we assume incurs zero cost. The estimated cost of changing the stored prediction from lt−1n to l̂ t n is thus:
ĉ(lt−1n → l̂tn) = cNFp̂NFn (lt−1n → l̂tn) + cPFp̂PFn (lt−1n → l̂tn). 5For example, on ImageNet we have K = 1000 which would require estimating 1 million parameters.
We only want to change the prediction if ĉ(lt−1n → l̂tn) < 0, i.e., p̂PFn (l t−1 n →l̂ t n)
p̂NFn (l t−1 n →l̂tn)
= p(yn=l̂
t n|ŷ 0:t n )
p(yn=l t−1 n |ŷ0:tn )
> − c NF
cPF (3)
leading to the following update rule:
ltn :=  l̂tn, if l̂ t n = l t−1 n , l̂tn, if l̂ t n 6= lt−1n ∧ ĉ(lt−1n → l̂tn) < 0,
lt−1n otherwise.
Note that (3) has an intuitive interpretation: we only want to update the currently stored prediction (thus potentially risking a negative flip) if our belief in a different label is larger than that in the current one by a factor exceeding |cNF/cPF|. We therefore refer to this strategy as CostRatio (CR).

heading: 4 Discussion: Extensions and Limitations
text: We discuss current limitations of our method and propose extensions to address them in future work.
Soft vs. Hard Labels Our approach presented in § 3 assumes deterministic classifiers which output hard labels, i.e., only the most likely class. This allows for maximum flexibility and a wide range of classifier models that can be used in conjunction with this method. However, our Bayesian framework can easily be adapted to also allow for probabilistic classifiers which output soft labels, i.e., vectors of class probabilities. We included some additional exploratory experiments utilizing softmax probabilities in Appendix A.11. Since deep neural networks are known to have unreliable uncertainty estimates [14, 25, 26, 47], we deliberately choose to work with hard labels. If, however, well-calibrated probabilistic classifiers are available (and can be scaled to huge data sets), taking this additional information into account will likely lead to more accurate posterior estimates and thus better performance.
Assumption of Conditionally-Independent Classifiers Since the models {Ct} are typically trained and developed on the same data and may even build on insights from prior architectures, our assumption of conditionally independent predictions on Dtarg does likely not hold exactly in practice. It should therefore rather be understood as an approximation that enables tractable posterior inference. Our experiments (§ 6) suggest that it is a useful approximation that yields competitive performance. Properly incorporating estimated model correlations may yield further improvements. We refer the interested reader to Appendix A.1 for a more detailed discussion.
Confusion Matrix Estimates Unless labelled data from Ptarg is available, the confusion matrices {πt} need to be estimated from Psrc. This is only an approximation because they may change as a result of PsrcX 6= P targ X , and taking such shifts into account could yield more accurate posterior estimates. For this, one may use ideas from the field of unsupervised domain adaptation [12, 28, 45]. One could use an importance-weighting approach [40] to give more weight to points which are representative of PtargX when estimating π
t from PsrcX,Y . As an example, in further experiments in Appendix A.4 we studied estimating the off-diagonal elements using Laplace smoothing [13, 35],
Other Selection Strategies Consider an ambiguous image that could be either a zucchini or a cucumber [4]. Such a sample would have large label entropy and could thus potentially be selected for re-evaluation again and again. To overcome this hurdle, one could decompose label uncertainty into epistemic (reducible) and aleatoric (irreducible) uncertainty [8, 19] and only re-evaluate samples with high aleatoric uncertainty, i.e., those with high expected information gain [24]. Such considerations also play a role in the field of active learning [37, 54]
Growing Data Set Size Our method is not constrained to fixed data set sizes and can accommodate for the addition of new data. New samples can be added at any time using an uniform prior over labels. Given their high initial entropy, they would then be naturally selected for (re-)evaluation first.
Adaptive Budgets Currently, we consider a fixed local budget of Bt re-evaluations at every time step. A possible extension would be to allow for a global budget of Btotal evaluations spread over all time-steps, i.e., to devise a strategy for deciding whether to (a) keep re-evaluating or (b) save budget for the next better model, potentially using techniques from reinforcement learning [46].
On the Cost of “Neutral” Flips For simplicity, we have assumed that “neutral” flips (i.e., changing a label estimate from an incorrect to a different incorrect one) bear no cost. However, as motivated
in § 1, it is well conceivable that even such neutral flips have a cost due to the potential to disrupt downstream robustness. If this is the case, it can easily be incorporated into our CR update strategy.

heading: 5 Related Work
text: Besides the aforementioned connections, our problem setting bears resemblance to several other areas of ML. In the following, we discuss the main differences and commonalities.
Backward Compatibility The term was first introduced by Bansal et al. [1] in the context of humans making decisions based on an AI’s prediction (e.g., medical expert systems or driver supervision in semi-autonomous vehicles). They contextualise that even though an AI’s predictive performance might increase overall, incompatible predictions in updated models severely hurt overall performance and trust, and propose to penalize negative flips w.r.t an older model when training a newer model. Yan et al. [53] show that with standard training, there can be a significant number of negative flips, even if the two models only differ in their random initializations. They then reduce the number of negative flips by giving more weight to training points that are correctly classified by the reference model, which they call ‘positive-congruent training’. Previous work on backward-compatible learning is concerned with training a new model. Here, we focus on updating the stored predictions rather than updating the stored models. This makes our approach more generally applicable and complements the use-cases of backward-compatible learning. Backward compatibility was further studied empirically by Srivastava et al. [43] who emphasize that this also causes problems for large multi-component AI systems. They propose two key metrics to characterize backward compatibility: (i) Backward Trust Compatibility (BTC), first mentioned in [1], measuring the fraction of predictions that are still predicted correctly after a model update; and (ii) Backward Error Compatibility (BEC), which corresponds to the probability that an incorrect prediction after an update is not new.
Ensemble Learning Ensemble methods aim to combine several ML models into a single model with higher performance than each of the individual models. Common techniques are boosting [11], bagging [6], or Bayesian model averaging [16]. Our approach falls into the latter category. We compute the posterior probability (2) in the same way as the well-known Naive Bayes combiner [23]. The classifier corresponding to our MB strategy goes back to at least Nitzan and Paroush [27] and has been thoroughly analyzed [3]. There are also Bayesian techniques that avoid Assumption 1, but these either make some parametric assumptions [20] or assume a very special form of dependence [5].

heading: 6 Experiments
text: We now evaluate our Bayesian approach to the Prediction Update Problem against different baselines using the task of image classification as a case study.

heading: 6.1 Experimental Setup
text: Data Sets We use the three widely accepted benchmark data sets ImageNet1K [7] (1K classes, 50k validation set), ObjectNet [2] (313 classes, 50k validation set) and CIFAR-10 [21] (10 classes, 10k validation set). To imitate our assumed setting of deploying pre-trained models to an unlabelled target data set, we only use the corresponding validation sets asDtarg. The ground truth labels are only used posthoc to compute performance metrics and are not seen during the T update steps. Of the 313 classes in ObjectNet, 113 are shared with ImageNet, corresponding to a subset of 18,547 images. ObjectNet images exhibit more realistic variations than those in ImageNet. It only has a test set and thus constitutes a challenging transfer scenario for object recognition models. We deploy ImageNet-pretrained models both on ImageNet and on the above subset of ObjectNet, thus simulating the cases that the source and target distributions are the same or different, respectively. For the former, we split the ImageNet validation set in half and use one half to estimate πt and the other as Dtarg. For the latter, we estimate πt from the full ImageNet validation set and evaluate on ObjectNet. We thus assume the covariate shift case, where the conditional label distribution is shared across source and target distributions.
Models & Architectures To emulate the setting of sequentially improving classifiers arriving over time, we use the following 17 models and architectures with many of them setting a new “state-of-the-art” on ImageNet at the time they were first introduced: AlexNet [22]; VGG-11, 13, 16, and 19 [41]; ResNet-18, 34, 50, 101, and 152 [15]; SqueezeNet [18]; GoogLeNet [48];
InceptionV3 [49]; MobileNetV2 [36]; DenseNet-121 and 169 [17], and ResNeXt-101 32x8d [52]. For ease of reproducibility, we use pre-trained models from the torchvision model zoo [29] and [32].
Performance Metrics Recall that our goal is to: (i) improve overall accuracy, (ii) avoid negative flips, and (iii) use as few re-evaluations as possible. To assess these different aspects, we report the following metrics: (i) final accuracy of the stored predictions (Acc) and accuracy improvement over the initial accuracy of C0 (∆Acc); (ii) the cumulative number of negative flips from time t = 0 to T (Σ NF), the average negative flip rate experienced per iteration, i.e., Σ NFN ·T (NFR), and the ratio of accumulated positive to negative flips (PF / NF); (iii) the evaluation budget available to each strategy as percentage of the data set size, i.e., a budget of 10 means that 10% of all samples can be re-evaluated at each time step: Bt = 0.1N, ∀t; finally, we measure the connective backward compatibility between (i) and (ii) via Backward Trust Compatibility (BTC) and Backward Error Compatibility (BEC) [43]. We refer to Appendix A.2 for a formal definition of these scores.
Baselines and Oracle We compare our method against two baselines: (i) Replace always updates the stored prediction with that predicted by the most recent classifier (a.k.a. backfilling); (ii) Majority Vote takes into account previous model predictions and updates the stored prediction according to the majority prediction. In case of a tie, the prediction of the most recent classifier is chosen. For reference, we also compare our method against an Oracle, which performs a prediction update if and only if this would lead to a positive flip; it thus incurs zero negative flips by definition (knowing the ground truth label). We emphasize that, in practice, we do not have that information in our setting.
Selection- and Prediction-Update Strategies For all methods, we select Bt ≤ N samples using the posterior label entropy selection strategy from § 3.2, but also compare with randomly selecting samples for re-evaluation. For all experiments involving the random selection strategies we run the same experiment for five different random seeds each and report the average. We use the predictionupdate strategies MB, MBME and CR from § 3.3 and consider cost ratios of |cNF/cPF| ∈ {2, 5, 10} for the latter (e.g., CR 2).

heading: 6.2 Results for ImageNet→ ImageNet
text: In Fig. 2 (left), we show the temporal evolution of backwards compatibility scores, negative flips and accuracy gains for prediction-updates on the ImageNet validation set for a subset of strategies and budgets. A complete account of final performances with additional metrics is shown in Tab. 1 (left).
For the evolution of ∆Acc in Fig. 2 (left), we observe that, unsurprisingly, strategies with 100% budget experience a more rapid gain in accuracy than those with 10%. Among the budget-constrained strategies, the CR strategy with large cost ratio shows the slowest increase, which makes sense as it requires a substantial change in posterior belief for updating a stored prediction and is thus more conservative. Interestingly, however, the final accuracies only differ marginally across both strategies and budgets which is also apparent from the minor differences in the ∆Acc column of Tab. 1. For the evolution of Σ NF in Fig. 2 (right), we observe a clear separation of strategies with a natural ordering from least conservative (Replace) to most conservative (CR 10). These relative differences stay mostly constant over time as NFs appear to accumulate approximately linearly (note the log-scale). We find roughly an order of magnitude difference in Σ NF between the best non-probabilistic baseline (Majority Vote) and the best Bayesian method (CR 10). Especially for small budgets of up to 30%,
our Bayesian strategies clearly dominate the non-probabilistic baselines both in terms of accuracy and flip metrics, as can be seen from Tab. 1 and Fig. 2 (right). Moreover, the CR strategy appears to provide control over the number of negative flips via its cost-ratio hyperparameter without adversely affecting final accuracy across a range of budgets, as already observed for a budget of 10% in Fig. 2. Interestingly, the update rules seem to be optimal when evaluating on less than 100% budget. We attribute this to posterior approximation errors on ImageNet, which is being supported by extensive ablations in the supplement. Regarding backward compatibility (our ultimate goal), we find that BTC and BEC scores reliably outperform the baselines across all budgets. In particular, the CR 10 strategy seems to be especially suitable with scores close to 100%, i.e., oracle performance.
Summary Our method appears to successfully fulfill the three desiderata for backward-compatible prediction-updates in an i.i.d. setting. In particular, our CR strategy seems like the most promising candidate to (i) maintain high accuracy gains and (ii) introduce very few negative flips, when (iii) given only a small compute budget for re-evaluations.

heading: 6.3 Results for ImageNet→ ObjectNet
text: Results for prediction-updates on ObjectNet are presented (similarly to § 6.2) in Fig. 3 and Tab. 1 (right). This transfer setting constitutes a much more challenging task. Nevertheless, we observe very similar behaviour to that discussed in § 6.2 and thus only point out the main differences. First, we note that - despite the smaller target data set - the difference in negative flips across different strategies and budgets is even larger on ObjectNet. For example, we observe a reduction in Σ NF of more than two orders of magnitude between Replace (100) and CR (10), and about one order when comparing the two for the same budget. At the same time, differences in accuracy across strategies are also slightly more pronounced, especially for the smallest budget of 10%. Here, the more conservative CR strategies yield lower accuracy gains while MB and MBME maintain competetive accuracy gains. Our strategies are again clearly dominating in terms of backward compatibility w.r.t. BTC and BEC. We remark that these results are agnostic to any potential differences in the label space: they are based on a posterior over all 1000 ImageNet classes whereas ObjectNet only contains a subset of 113 of these classes.

heading: 6.4 Further Experiments and Ablations
text: Results for CIFAR-10 In Fig. 4 (a) we show the corresponding results on the CIFAR-10 dataset. Here, pre-trained models exhibit a higher level of accuracy (≈ 93 − 95%) and we thus emulate an arguably more realistic scenario with models being released more frequently, thus with smaller accuracy differences. Our method shows very similar trends as we have worked out on ImageNet and ObjectNet. Interestingly, there is one novel characteristic: due to the presumably less steep increase in accuracy from one model to its successor and fewer class categories, we can form very accurate posterior beliefs which results in accuracy gains of all our methods that even outperform the accuracy-optimizing baselines concerning desideratum (i). A more comprehensive analysis of these experiments can be found in Appendix A.5.
Role of the Selection Strategy We also conduct a comparison between our entropy selection and the random baseline for all our methods across a range of budgets - see dashed lines in scatter plots. We find that random selection leads to substantially smaller accuracy gains, but also to fewer negative flips which is intuitive since random selection more often chooses “easy” samples for re-evaluation.
Robustness to Random & Adversary Model Sequences We have assumed that the models Ct are improving over time. We thus also consider the scenario where Ct arrive in a random or adversarial (i.e., strictly deteriorating) order. For the random order (see Fig. 4 (b)) we find that our methods - unlike, e.g., the replace strategy - achieve strict increases in accuracy while introducing much fewer negative flips. Even in the adversarial case, our methods improve accuracy during the initial steps with much fewer negative flips over the entire history. These findings suggest robustness of our approach to situations where an ordering by performance of Ct may not be available. We refer to Appendix A.3 for more details.
Reducing Re-Evaluations Matters at Scale The re-evaluations of a sample using deep neural network based models clearly dominate computational cost as compared to our method. As an example, the forward pass using the public ImageNet PyTorch models takes up to 550 (biggest VGG and ResNets) times longer than the unoptimized implementation of our method backbone. We analyze this in more detail in Appendix A.9. For very large data sets and with new models generally increasing in size, reducing the inference budget B is of crucial importance, emphasizing the relevance of desideratum 3.

heading: 7 Conclusion
text: The Prediction Update Problem appears frequently in practice and can take different forms. It relates to many different subfields of ML that we have discussed in § 4 and § 5, and there are interesting extensions (structured prediction, adaptive budgets) and improvements (modeling data set structure, across-dataset similarity, domain adaptation, calibration techniques) that need to be worked out. In this work, we have studied the classification case and proposed a Bayesian update rule based on simple assumptions. Empirically, we find improvements along the dimensions we set out to achieve, and we hope that progress on this problem will democratize ML usage even further as it lowers the bar for benefitting from the tremendous progress in model design seen over the last years.

heading: Acknowledgements
text: The authors would like to thank Matthias Bethge, Thomas Brox, Chris Russell, Karsten Roth, Nasim Rahaman, Alex Smola, Yuanjun Xiong and Stefano Soatto for helpful discussions and feedback.

Review summaries:
This paper proposes an approach for updating predictions on an unlabeled dataset as new, pretrained classifiers become available. Calling it the "Prediction Update problem", the authors seek to 1) make updates which improve accuracy, 2) avoid updates which introduce new errors, and 3) update predictions on data points using a limited budget (relevant in the massive dataset setting). The authors propose a Bayesian approach in which a posterior belief over true labels for each sample are updated as new classifier predictions become available for that sample. The authors assume (label-conditional) independence of the classifiers, allowing the likelihood to be computed easily using normalized confusion matrices of the classifiers. Samples are chosen for prediction on the basis of maximum posterior entropy, and different prediction update strategies are considered. These include naive baselines (e.g., newest classifier's prediction and majority vote) as well as MAP estimates and cost-aware strategies (which tradeoff large belief increases against the possibility of incorrectly flipping a prediction). The authors extensively discuss limitations and opportunities for future improvements. Detailed experiments using imaging benchmark datasets examine the properties of different strategies on standard (i.e., train and test data from same dataset/distribution) and transfer learning (i.e., train and test data from different datasets) tasks.

Paper proposes a new problem *Prediction Update Problem* with a complementary perspective originating from the increasing availability of pre-trained and regularly improving state-of-the-art models. In particular, they focus on (i) given a limited budget, deciding which data points should be re-evaluated using the new model; and (ii) if the new predictions differ from the current ones, deciding which predictions should be updated. The authors present an efficient probabilistic approach that answers both questions. Empirical evaluation shows the efficacy of their proposed approach over baselines.   

This paper formulates the “Prediction Update Problem”: as new (better) models are trained, you want to integrate them into your system, and improve accuracy. However, you want to do so without making too many previously correct predictions incorrect (negative flips), as this would reduce user trust. The authors provide a natural Bayesian procedure for doing this. Additionally, they consider the case where the dataset may be too large to evaluate each model on the full dataset, and propose an entropy-based subset selection procedure. Experimentally, they show that this method can beat simple baselines at keeping negative flips low without losing too much in accuracy.