Backward-Compatible Prediction Updates: A Probabilistic Approach
Authors: Frederik Träuble
Julius Von Kügelgen
Matthäus Kleindessner
Francesco Locatello
Bernhard Schölkopf
Peter Vincent Gehler
Venue: NeurIPS 2021 Poster (2021)
Keywords: Backward Compatibility
Algorithm Evaluation
Applications in Computer Vision
Probabilistic Methods

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.


Backward-Compatibe Prediction Updates: A Probabilistic Approach
Frederik Träuble
Julius von Kügelgen 1.3*
Matthäus Kleindessner
Francesco Locatello
Bernhard Schölkopf2
Peter Gehler
Max Planck Institute for Intelligent Systems, Tübingen, Germany
Amazon Tübingen, Germany
Department of Engineering, University of Cambridge, United Kingdom
Abstract
When machine learning systems meet real world applications, accuracy is only of several requirements. In this paper, assay a complementary perspective originating from the increasing availability of pre-trained and regularly improv- ing state-of-the-art models. While new improved models develop fast pace, downstream tasks vary more slowly or stay constant. Assume that we have a large unlabelled data set for which want maintain accurate predictions. Whenever new and presumably better ML models becomes available, we encounter two prob- lems: (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-compatbbl prediction updates.
Introduction
The machine learning (MI.) community develops new models 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 refer to 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, 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 cheap as possible since the target data set could be huge.
"Work done while FT and JvK were interning at Amazon. 'Corespondence to: frederik. traeuble@tuebinge mpg de and pgehlerd@mazzn.ccom
35th Conference on Neural Information Processing Systems (NcurIPS 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-truthe 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 transductive or semi-supervised problem, but, due to computational constraints, we avoid any model fitiing 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 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 the reason for our second desideratum: we would like to be backward- soccwaard-ompattble 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 la- bels 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 prediction- update strategies to decide whether to change the stored predictions, taking asymmetric costs for neg- ative and positive flips into account. Using the task of image classífication as a case study, we perform extensive experiments on common benchmarks (ImageNet, CIFAR10 10, and ObjectNet) and demon- strate that our approach achieves competitive accuracy and introduces much fewer negative flips across 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 (
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 ($ ().).
We contextualise this understudied problem setting as well as our method with related work ($ & 5 and discuss several extensions and limitations ($ 4
We demonstrate that our approach successfully outperforms alternative approaches and accomplishes all our desiderata experiments across multiple common benchmark datasets (CIFAR-10, ImageNet, and ObjectNet) and practically relevant scenarios ($ 6
1.1 Backward-Compatibb Prediction Systems
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 [I] who argue to "make the human factor first-class consideration of Al 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. Al assisted medical decision processes 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 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 experienee experience may outweigh the benefit of better predictions on other images.
All software and assets we are open source and under MIT, Apache Creative Commons Licenses.

---

Initial annotation
Ro Re-evaluation
evaiuation
Re-evaluation
t= 4
The frapg
Thick dheet"
ground
DE ToAdi
MI enskiCt?
Pandy
01
stored
Reploce:
Repiace:
frod
Repioce:
Replace:
truck
Majority
Majority Vote:
Majorit Vote:
truck
MB:
MB:
Frog
MB:
truck
MB:
truck
MD:
truck
MOME
frog
MBME
mrgg
MOME
truck
MAME:
trucs
MOME
truck
CR LO:
mrg
CR 10:
mmg
CR 10
Frgg
CR SC:
frgg
CR 10:
truck
Figure I: Overview of our proposed Bayesian approach to the Prediction Update Problem. Starting from a uniform prior, we maintain posterior distribution ply klg (middle) over the unknown true label of unlabelled sample which takes the predictions g from new ML models C (top) arriving over time t = 0, ..., T into account. Given a limited compute budget B¹, we re-evaluate those samples with highest posterior label entropy 5 at each time step, e.g., the example shown is first selected in time step t = after the initial annotation at t = O. We then consider different strategies for deciding whether to update the stored prediction (bottom) based our changed belief's. Note that the probbabbbblliticc baselines "Replace" (always update to last prediction) and "Majority Vote" (resolve ties by using the last prediction) incorrectly update the stored prediction from "truck" to "deer" in step f = 4. Our strategies (MB, MBMF, CR-10) which rely on the estimated label posterior, on the other hand, avoid such negative flip, which is one of our key goals.
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 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 update costs are asymmetric. Service providers often rely on models pre-trained on a diffcrent data set, and the desire to be backward-compe compatiie arises naturally in this setting 1 39 43 53
average but her data it gets worse, the
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.
2 The Prediction Updates Problem Setting
Target Data Set We are given a large, unlabelled target data set Diarg {xx))== comprising N independent and identically distributed (i.i.d.) observations x,, E X C Rd drawn from target distribution plars The ground-truth labels yn E y {1, ..., K) distributed according pfarg not observed. Note that we are particularly interested in a scenario where N may be extremely large.
Yix are
Models Over time t = 0, 1, ..... T we successively gain access to classifiers Co C'..... CT : X -> ) which have been trained on a labelled data set Detc from potentially different source distribution PXE over X' x y. For simplicity, we assume that the observation space X' and label space y are labelled
shared. We consider both the standard scenario where the models {C") Jezo trained set from the same domain (ipare = ptarg); and the transfer scenario where we deploy a model trained on labelled ML benchmark to a different data set (Parc * ptark). We assume that (C*)T.o improving in performance on the training data set. Therefore, denoting by A, the estimated accuracy of C* on peere x we have A' < A Vt. As motivating example, consider an object recognition task in the wild and let C₁ be the winning entry of the ImageNet competition in year t.
3

---

Labelling To relate the source and target distributions and to justify applying {C") data set Diarg, we make the commonly used covariate shift assumption p P
Jt=o to our target
Yix. i.e. the
conditional label distribution is shared across source and target distributions 440 We denote the predicted label by C for xn, by 8% C* (xx) and the stored prediction for x,, after time step t by ". The target data set is then initially fully labelled by C i.e., P == fh.
As new classifiers {C"}e2 become available, our main objective is to maintain the best estimates { ( on our target data set at all times and improve overall accuracy, while, at the same time, maintaining backward compatibility by minimising the number negative flips, i.e. the number of previously correctly stored predictions that are incorrectly changed. The key challenge 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 X,, and each time step t 2 I, we thus need to decide whether or not to update the previously stored prediction 1t-1 based on the current and previous model predictions in and 0u:t- respectively.
Objective
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 B S N sample re-evaluations for step We thus additionally need decide how to allocate this budget and select a subset of samples to be re-evaluated by C* at every step.
3 Our Method
Having specified the setting, we next describe our proposed method for the Prediction Update Problem. We start by providing Bayesian approach for maintaining and updating our beliefs about the unknown true labels as new predictions become available (.1)) followed by describing strategies for selecting candidate samples for re-evaluation (3.22) and for updating the stored predictions based on our changed beliefs ($ 3.3).
Our framework is summarised in Figure [
3.1 Bayesian Approach
Since the true labels (yn J we maintain uncertainty estimates. We then perform Bayesian reasoning to update our beliefs as new evidence in the form predictions if from newly-available classifiers C' arrives over time t = I. In standard Bayesian notation, the true labels Yn. thus take the role of unknown parameters and the predictions d data æ. Since Diarg is sampled i.i.d., we reason about each label yv independently of the others, i.e., the following is the same for all n.
n=1 are unknown to us, we treat them as random quantities over which
Prior Lacking label information on the target data set, we choose a uniform prior over Y for all yo- i... p(y, k) = 1/K, Vk E y. If (estimates of) the class probabilities on Diarg are available, we may instead use these as more informative prior.
Likelihood Next, we need to specify a likelihood function p(j":T (y. = k) for the observed model predictions 5h. given value is of the true label you We make the following simplifying assumption. Assumption (Conditionally independent classifiers). The different classifiers' predictions gor are conditionally independent given the true label ynu i.e., the likelihood factorises as
P 0:T Vn = k) = I P0O =k).
(1)
In a standard Bayesian setting, this corresponds to the assumption of conditionally independent observations given the parameters; we refer to F for further discussion. The main advantage of Assumption is that the factors p(i', yy. k:) on the RHS of (I) have natural interpretation: these are the (normalised) confusion matrices T' of the classifiers C i.e., we denote by
n' (i(,,)
p(ğ' = ily k).
the probability that C* predicts class i given that the true label is k. which is the same for all n; see below and for more details on how we estimate rf in practice.
*In 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 Prix). Note that such covariate shift may also lead to changes in Py (label/target shift) and/or IP x|y (conditional shift) 44 55

---

Posterior At every time step t 2 O, we can then compute our posterior belief about the true label given model predictions yh= according Bayes rule,
=k16 plun = klohht) = Eiey of (0% ()p( (at-1)
(2)
where we have used Assumption to write p(2 Un = ki 1 = p(i = =) x > A:). The posterior at step 1 acts prior for step t,
do not have to store all previous predictions.
Estimating Confusion Matrices In practice, n' 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 the amount of labelled source data we only estimate the diagonal elements म (i.e., the class- dlass-ppecffie accuracies) and set the K(K off- aff-diagonal elements to be constant,
# (i.k)
(k,A K-1
Vi + k:
Ak e V. We refer for further discussion on the estimation of n² so that Σ x (i,
3.2 Selecting Candidates for Re-evaluation
Given the label posteriors computed according to 1. we compute the Shannon entropies 38
S = Eiey P(Un. = k k( log p(v,. = k((0)))
which provide simple measure of uncertainty in the true label yn after step f. We then select and re-evaluate the B' samples with highest posterior label entropy S% to update our beliefs.
3.3 Prediction-Update Strategies
Finally, we need strategy for deciding whether and how to update the previously stored prediction 1, 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., 1 = 1 argmaxRey p(yn k) We refer to this strategy MaxBelief (MB). MaxBelieeMiinntene (MBME) A slightly more sophisticated approach is to also take the change in posterior entropy into account and only update when it has decreased:
i
if S < S
1
otherwise.
We refer to this strategy as MaxBeliefMinEnttopp (MBME).
CostRatio (CR) So far, 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 NF 0 and that of positive flip (PF) by c
We need to decide whether to update the previously stored prediction 1 based on our updated beliefs p(y, = kl Denote the MAP label estimate after step by īt = argmax P(yn = kl If it !t-1 there is reason to change the stored prediction. Suppose that 7,, 1.-1_ We then need to reason about the (estimated) positive and negative flip probabilities when changing the stored prediction from ! to it, A positive flip (PF) occurs if i"; is the correct label (and hence 1e-1 is not), and, vice versa, negative flip occurs if (t-1 is correct (and hence it is not):
pn (1----- + (.) ply, 0.
PN (1' -- - P.) = p(y. 1r 1
neither 1--1 nor ir are the correct label, the flip is inconsequential which we assume incurs zero cost. The estimated cost of changing the stored prediction from / to iz is thus:
60t Pr)) N pNF (1--1 (,)
For example, on ImageNet we have K 1000 which would require estimating I million parameters.
5

---

We only want to change the prediction if 6(1% + 11))== < 0, i...
Pe CC. xC, ( [
plun =L, 1 c
(3)
plyn=th 188)))
ct
leading to the following update rule:
if
i =
1
if 1 *
Aa(h ++) <0,
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 factor exceeding |c /c We therefore refer to this strategy as CostRatio (CR).
Discussion: Extensions and Limitations
We discuss current limitations of our method and propose extensions 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 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 prob- abilities in Appendix A.II Since deep neural networks are known have unreliable uncertainty es- timates [14 25 26 471. 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 infor- mation into account will likely lead to more accurate posterior estimates and thus better performance.
Assumption of trained and developed on the same data and may even build on insights from prior architectures, our assumption of conditionally independent predictions on Diarg does likely not hold exactly in practice. It should therefore rather be understood as an approximation that enables tractable posterior inference. Our experiments ($ () suggest that a useful approximation that yields competitive performance. Properly incorporating estimated model correlations may yield further improvements. We refer the interested reader to Appendix A for more detailed discussion.
Classifiers Since the models {C') are typically
Confusion Matrix Estimates Unless labelled data from ptarg is available, the confusion matrices (*') need to be estimated from pare_ This is only approximation because they may change as result of pere * ptarg 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 weaporttanc-weiihtiin
approach (40) to give more weight to points which are representative of ptarg when estimating n² from Pare As example, in further experiments in
Appendix A.4 we studied estimating the off-diagonal elements using Laplace smoothing [3] 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 role in the field of active learning (37 54
Growing Data Set Size Our method 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 (rea)evaluation first.
Adaptive Budgets Currently, we consider a fixed local budget of B' 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 label estimate from an incorrect to a different incorrect onc) bear no cost. However, motivated

---

in | 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.
Related Work
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. [ in the context of humans making decisions based on Al's prediction (e.g., medical expert systems driver supervision in aumimautonomous vehicles). They contextualise that even though an Al'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 al. [53] show that with standard training, there can be 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 correctly classified by the reference model, which they call 'positive-conrrentt training'. Previous work on backward-compatic 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 cackpard-comppaibll 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 characterize backward compatibility: (i) Backward Trust Compatibility (BTC), first mentioned in [.] 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 combine several ML models into single model with higher performance than each of the individual models. Common techniques are boosting [[],
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 | but these
either make some parametric assumptions
20 or assume a very special form of dependence [5]
6 Experiments
We now evaluate our Bayesian approach to the Prediction Update Problem against different baselines using the task of image classification as a case study.
6.1 Experimental Setup
Data Sets We use the three widely accepted benchmark data sets ImageNetIK IK 7 (IK classes, 50k validation set), ObjectNet (2 (313 classes, 50k validation set) and CIFAR-10 21 (10 classes, 10k vali- dation set). To imitate our assumed setting of deploying pre-trained models to an unlabelled target data set, we only use the corresponding validation sets as Diarg, The ground truth labels are only used post- hoc 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 im- ages 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-pree preetrrind models both 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 n² and the other as Diarg, For the latter, we estimate r 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 -tttee-f-thhe-at" on ImageNet at the time they were first introduced: AlexNet [22]: VGG-11,
13, 16, and 19 [1): ResNet-18, 34, 50, 101, and 152 [15; SqueezeNet [18]: GoogLeNet [48);
7

---

Rggaac 3000
(100
MB-1155
0030-200
ImageMet
Nagarty sinw (503)
MIME (100)
Orade (103)
7 55
SCC (M
Accurecy inporemenn Acc
BIC
Itant
Pain itan
CT.2 Joms
CK hone
5q seeecco of
11
Restec 38
VGG
200
Gemoolee 130
rnceptions
neSwor 131
ve0 18
Demuntie 17
Demolless lie
scceptiones
doant 112
Cengy
La Accumm lesed Negative Fliys INF
Figure 2: Left: Temporal evolution for ImageNet - ImageNet over T 16 prediction update steps for a
subset of strategies and budgets. Right: Comparison of prediction-updatt strategies across different budgets
after T = 16 prediction-update steps. Dashed lines correspond to the ablation using a random selection strategy.
Inception V3
49 MobileNetV2 36 DenseNet-121 and 169 117, and ResNeXt-101 32x&d 52
For ease of reproducibility, we use pre-trained models from the torchvision model zoo (2 and
Performance Metries 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 C (AAce): (ii) the cumulative number of negative flips from time = 0 to T (E NF), the average negative flip rate experienced per iteration, i.c., Σ NE (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.c. budget of 10 means that 10% of all samples can be re-evaluated at each time step: B' = 0. O. vt; 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.. for a formal definition of these scores.
N-T
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 tic, the prediction of the most recent classifier is chosen. For reference, also compare our method against 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 B' S 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 prediction- update strategies MB, MBME and CR from 3.3 and consider cost ratios of JeNt/e /cP"| E (2, 5, 10} for the latter (c.g., CR 2).
6.2 Results for ImageNet >> ImageNet
In Fig. [] we show the temporal evolution of backwards compatibility scores, negative flips and accuracy gains for grediction-update on the ImageNet validation set for subset of strategies and budgets. A complete account of final performances with additional metrics shown in Tab. (left).
For the evolution of AAc 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 requires a substantial change 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 AAce column of Tab. I For the evolution of Σ NF in Fig. (right), we observe a clear separation of strategies with 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 Σ NF between the best probaabiiiiisic baseline (Majority Vote) and the best Bayesian method (CR 10). Especially for small budgets of up to 30%,
8

---

Table 1: Results for ImageNet - ImageNet (left) and ImageNet - ObjectNet (right): all metrics refer to final performance for the improving model sequence from Fig. Ladd Fig respectively. The character E R in front of the strategy indicates that selection for re-evaluation is based on the entropy criterion or sampled randomly.
Ney
Bretog
Ang
Deglact
1569
Val
07:05
1319
73-1
1992
1.6
14
18:07
2/6
1.14
15
1539
216
$6.00
6313
363
1366
1321
26
187
33
CR Pv
95235
15.13
17
265
2012
655
34
CR
97.82
08.54
363
258
1864
0.5
46
17.0
6633
714
363
35464
130
15
13.39
08.33
39
31
6004
135
and
85.5
1361
13
1713
131
06.79
4114
145
13
00.0
212
2337
16.0
118
0355
15
98.55
44
90.4
1440
713
714
1917
6.36
44
668
15.9
710
K4
1033
1963
733
143
15564
0.9
12
5748
912
22.
362
1966
034
14
01:0
18.18
13.4
16.3
2013
86
413
016
233
881
24
1490
13:
98.53
95.9
1964
753
18.
115
605
95.07
19.90
113
18
064
15
Agp-ace 1.00
(.000
MS-185
0930-300
Chpectlltt
Nyganit viow (103)
Inted (100)
MBME 1100
Orade (133]
100
Majorty Sate
aurrng
seger cann
Accuncy
On tge
5q restth
30
Dorted satte 20
monoeei 100
Sqp seseaaa
Gangy skee
vor-11
vea i8
Demuntal 21 Denomtees 10
Ro Spaiis to
Enceptionis
Dellict--11 20
Accumuleted Negetive Flles INF
Figure 3: Left: Temporal evolution for ImageNet - ObjectNet over 1' 16 prediction-update steps for subset of strategies and budgets. Right: Comparison all strategies after 1' on ObjectNet.
our Bayesian strategies clearly dominate the probabbbbiii baselines both in terms of accuracy and flip metrics, as can be seen from Tab. annd Fig. (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 beckward-compatbble mediction--udatee in 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 small compute budget for re-evaluations.
6.3 Results for ImageNet - ObjectNet
Results for ceddiction-uddated ObjectNet presented (similarly $ 66.2) in Fig. 3 and Tab. T (right). This transfer setting constitutes a much more challenging task. Nevertheless, we observe very similar behaviour that discussed in $66.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 diffferent strategies and budgets is even larger on ObjectNet. For example, we observe 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 the label space: they are based on a posterior over all 1000 ImageNet classes whereas ObjectNet only contains subset of 1 113 of these classes.

---

HBNE 5000
MEME (1N
345 (10
V66-33
Google
VDD 18
vo0
V00-33
VD
Tecraa 152
oriscn 187
101
Fastee
VO6-3
Sereeoe 122
naatei sot.
200
(a) Experiments on CIFAR-10
(b) Random Model Sequence on ImageNet
Figure 4: Left: Temporal evolution for CIFAR- 10 over I'= = 11 prediction-upsle steps for a subset of strategies and budgets. Our approaches achieve competitive overall accuracy gains (even at 10% of the budget) while introducing only fraction of negative flips. Right: Experiment on ImageNet with random model sequence suggesting robustness our approach to situations where an ordering by performance of may not availahle.
6.4 Further Experiments and Ablations
Results for CIFAR-10 In Fig. f (a) we show the corresponding results on the CIFAR-10 dataset. Here, pre-trained models exhibit 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, 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.3
can form very
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 scatter plots. We find that random selection leads to substantially smaller accuracy gains, but also to fewer negative flips which intuitive since random selection more often chooses "easy" samples for re-evaluation.
Robustness to Random& & Adversary Model Sequences We have assumed that the models O' are improving over time. We thus also consider the scenario where C' arrive in a random adversarial (i.e., strictly deteriorating) order. For the random order (see Fig, (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 C* 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 compared to our method. As an example, the forward pass using the public ImageNet Py 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.
7 Conclusion
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 and $ 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 MI. usage even further as lowers the bar for benefitting from the tremendous progress in model design seen over the last years.
10

---

Acknowledgements
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.
References
[1] Gagan Bansal, Besmira Nushi, Ece Kamar, Daniel S Weld, Walter S Lasecki, and Eric Horvitz. Updates in human-AI teams: Understanding and addressing the perfomaace/compatiiily tradeoff. In Proceedings of the AAA! Conference on Artificial Intelligence, volume 33, 2019.
[2] Andrei Barbu, David Mayo, Julian Alverio, William Luo, Christopher Wang. Dan Gutfreund, Josh Tenenbaum, and Boris Katz. Objectnet: A large-scale bias-controlled dataset for pushing the limits of object recognition models. Advances in neural information processing systems, 32, 2019.
[3] Daniel Berend and Aryeh Kontorovich. A finite sample analysis of the naive bayes classifier. J. Mach. Learn. Res., 16(1), 2015.
[4] Lucas Beyer, Olivier Hénaff, Alexander Kolesnikov, Xiaohua Zhai and Aäron van den Oord. Are we done with imagenet? arXiv preprint arXiv:2006.07/54 2020.
[5] Philip Boland, Frank Proschan, and Yung Liang Tong. Modelling dependence in simple and indirect majority systems. Journal of Applied Probability, 1989.
[6] Leo Breiman. Bagging predictors. Machine learning. 24(2), 1996.
[7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition. Icee, 2009.
[8] Armen Der Kiureghian and Ove Ditlevsen. Alcatory or epistemic? does matter? Structural safety, 31(2), 2009.
[9] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbom, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition scale. 2021.
[10] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware mini- mization for efficiently improving generalization. 2021.
[11] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1), 1997.
[12] Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning. PMLR, 2015.
[13] Irving J Good. The population frequencies of species and the estimation of population parame- ters. Biometrika, 40(3-4), 1953.
[14] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. International Conference Learning Representations, 2015.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
[16] Jennifer A Hoeting, David Madigan, Adrian E Raftery, and Chris T Volinsky. Bayesian model averaging: tutorial. Statistical science, 1999.
[17] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2017.
11

---

[18] Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and < 0.5 mb model size. arXiv preprint arXiv: 1602.07360, 2016.
[19] Alex Kendall and Yarin Gal. What uncertainties do we need in Bayesian deep learning for computer vision? In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
[20] Hyun-Chul Kim and Zoubin Ghahramani. Bayesian classifier combination. In Artificial Intelligence and Statisties, 2012.
[21] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. 2009.
[22] Alex Krizhevsky, Ily Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 2012.
[23] Ludmila Kuncheva. Combining pattern classifiers: methods and algorithms. John Wiley Sons, 2014.
[24] Dennis V Lindley. On measure of the information provided by an experiment. The Annals of Mathematical Statistics, 1956.
[25] David JC MacKay. Bayesian neural networks and density networks. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 354(1), 1995.
[26] Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE conference computer vision and pattern recognition, 2015.
[27] Shmuel Nitzan and Jacob Paroush. Optimal decision rules in uncertain dichotomous choice situations. International Economic Review, 1982.
[28] Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on knowledge and data engineering. 22(10), 2009.
[29] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
[30] Niklas Pfister, Peter Bühlmann, Bernhard Schölkopf, and Jonas Peters. Kernel-based tests for joint independence. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(1):5-31, 2018.
[31] Hieu Pham, Qizhe Xie, Zihang Dai, and Quoc V Le. Meta pseudo labels. arXiv preprint arXiv:2003.1058: 2020.
[32] Huy Phan. hhyyaphan/pytorch.cfffrr.l jan 2021.
[33] Joelle Pineau, Genevieve Fried, Rosemary Nan Ke, and Hugo Larochelle. ICLR2018 repro- ducibility challenge. In ICLR workshop on Reproducibility in Machine Learning, 2018.
[34] Joelle Pineau, Koustuv Sinha, Genevieve Fried, Rosemary Nan Ke, and Hugo Larochelle. ICLR reproducibility challenge 2019. ReScience C, 5(),, 2019.
[35] Herbert Robbins. An empirical Bayes approach to statistics. In Proc. 3rd Berkeley Symp. Math. Statist. Probab. 1956, volume 1956.
[36] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mohilenetv2 inverted residuals and linear bottlenecks. Proceedings of the IEEE conference on computer vision and pattern recognition, 2018
12

---

[37] Burr Settles. Active learning literature survey. University of Wisconsin, Madison, Department of Computer Sciences, 2009.
[38] Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3), 1948.
[39] Yantao Shen, Yuanjun Xiong, Wei Xia, and Stefano Soatto. Towards backward-compatible representation learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, 2020.
[40] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of statistical planning and inference, 90(2), 2000.
[41] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference Learning Representations, 2015.
[42] Koustuv Sinha, Joelle Pineau, Jessica Forde, Rosemary Nan Ke, and Hugo Larochelle. Neurips 2019 reproducibility challenge. ReScience C, 6(2), 2020.
[43] Megha Srivastava, Besmira Nushi, Ece Kamar, Shital Shah, and Eric Horvitz. An empirical analysis of backward compatibility in machine learning systems. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
[44] Amos Storkey. When training and test sets are different: characterizing learning transfer. Dataset shift in machine learning, 30:3-28, 2009.
[45] Masashi Sugiyama and Motoaki Kawanabe. Machine learning in non-stationary environments: Introduction to covariate shift adaptation. MIT press, 2012.
[46] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[47] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Leurning Representations, 2014.
[48] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2015.
[49] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
[50] Hugo Touvron, Andrea Vedaldi, Matthijs Douze, and Hervé Jégou. Fixing the train-test resolution discrepancy: Fixefficientnet. Advances in Neural Information Processing Systems 32, 2019.
[51] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoe V Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
[52] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2017.
[53] Sijie Yan, Yuanjun Xiong. Kaustav Kundu, Shuo Yang, Siqi Deng. Meng Wang, Wei Xia, and Stefano Soatto. Positive-congruent training: Towards regression -fee model updates. Conference on Computer Vision and Pattern Recognition, 2021.
[54] Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active learning from imperfect labelers. Advances in Neural Information Processing Systems 29, 2016.
[55] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. International Conference on Machine Learning (ICML., pages 819-827. PMLR, 2013.
13


Reviews:
[{"review_id": "_0c9jDVX1g", "reviewer": "Reviewer_j1CS", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers an interesting and, to my knowledge, new problem. Existing work on backwards compatibility in ML has focused on training new models whose predictions are consistent with the old model (as discussed by the authors in Section 5). Instead, this work considers the perspective of an owner of, e.g., a proprietary unlabeled dataset for which they need labels to provide downstream services. It is increasingly common for large, state-of-the-art pretrained models (e.g., winners of benchmark challenges) to be publicly released. This work is aimed towards those who want to capitalize on the increasing availability of high quality pretrained models to perform labeling on their own data. It is a very interesting use case and I'm glad to see the authors begin a thorough investigation here.\n\nThe proposed approach is a very straightforward, but elegant, Bayesian approach for tracking and updating posterior belief about the true labels in a backwards compatible way. The proposed framework lends itself to a number of natural extensions (e.g., synthesizing probabilistic predictions instead of classification predictions, new selection strategies, adaptive budgets, etc.). I thought Section 4 on extensions and limitations was very well thought out and it addressed a number of the minor questions/concerns that I thought of while reading the paper. Finally, I thought the experiments were well executed and were a convincing demonstration of the proposed approach. The experiment studying the order of the classifiers is particularly interesting and important---I think the authors should draw more attention to it since I doubt new classifiers will truly be strictly better than older ones.\n\nI have a few suggestions for improvement:\n- When first reading the introduction I was a little confused by the setting, and had a hard time imagining possible use cases. The authors first discuss the problem in general and only then introduce the photo tagging example on Line 79. I think this should be reversed: first provide the concrete motivating example and then explain the general problem/principles that will drive the method and the rest of the paper.\n- Is there any way to test Assumption 1 or measure the magnitude of violations? In Section 4 the authors mention this assumption is a limitation, but could you provide suggestions or possible avenues for addressing it, measuring it, or performing sensitivity analysis?\n- Is my understanding correct that no adjustments to the method were made for the ImageNet --> ObjectNet experiment? That is, the updates were performed assuming no distribution shift? I think it would be beneficial for the authors to expand their discussion in Section 4 of how distribution shift affects the prediction update problem (and also discuss beyond just the covariate shift case), since this is a problem that is going to come up a lot in practice.\n\n\nUPDATE:\nThanks to the authors for their response. I remain very positive about this work and will be keeping my score the same. I think slightly more detailed discussion of Assumption 1 and distribution shifts in the main paper will help round it out nicely.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "Qe9OELgBN6u", "reviewer": "Reviewer_y17T", "summary": "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. \n ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper introduces a very important problem and, in general, is very clearly written and is very easy to follow. The proposed method is simple and intuitive. Limitation of the current work is also presented succinctly. \n\nComments: \n- Three desiderata are postulated in a very clear manner. Figure 1 illustrates the approach very clearly. \n- The proposed problem and solution are contrasted nicely with the related work. \n- Empirical results are strong in experiments across multiple common benchmark datasets. \n\nLimitations: \n- As mentioned by the authors, the assumption of conditionally independent classifiers is strong as usually the improvements are built on prior architectures. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "J5MaP8TYUMx", "reviewer": "Reviewer_BRHA", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-\tThis problem seems very interesting and well motivated, and the authors describe it well\n-\tThe proposed methods section provides a reasonable working-through of what a sensible, simple approach to this problem might be\n-\tThere are a few assumptions that seem limiting (e.g. independent predictions given label, reliable estimation of confusion matrix) but the authors mostly do a good job mentioning these\n-\tThe experiments tell a clear story although the presentation is quite cramped, it’s hard to really make out what is happening in the figures and charts. But the improvement over the baselines is clear\n-\tOne thing that would be helpful in the experiments is more discussion of the Pareto front between accuracy and negative flips\n-\tThe “limited evaluation budget” part of the story seems a little bit separate – in some sense I’m not sure you really need it as part of the proposed problem\n-\tBTC + BEC should definitely be defined in the main body!!!\n-\tThe experiment with the models ordered by when the broke SOTA is very cool\n-\tOne baseline I would find interesting would be using the oracle only for estimation of the confusion matrix – that seems like an important source of noise/uncertainty here\n-\tI’m not sure why the accuracies for the proposed methods decrease with higher budgets? There’s an explanation in the appendix but I don’t really understand it, would love more clarity here\n-\tWhy are the numbers in the \\sum NF column floats? Is this an average over seeds?\n-\tIn general, lots of experimental details are left out, there should be a section in the appendix  - I doubt I would be able to reproduce this result as is given the information in the paper currently\n-\tSec 6.4: when you discuss the ablations, should point to the appendix where you do the experiment\n-\tI have no idea what the “reducing re-evaluations matters at scale” section means – I thought you were using VGG/Resnets for your method??\n-\tOverall: the paper is a little sloppy but very interesting problem proposal and useful experimental evidence\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Good discussion of the limitations of a number of their assumptions – Section 4 is very nice. I think this work could be useful across industries, in particular high stakes situations and human trust in AI systems", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work introduces a Bayesian approach to the prediction update problem. In it they consider an interesting use case in which they want to label a large unlabelled dataset while taking advantage of new pertained classifiers as they become available. Overall, reviewers were positive about the paper, but had several good suggestions when it comes to improving the presentation. I encourage the authors to carefully incorporate reviewer feedback at the revision stage.
Decision: Accept (Poster)