How Did the Model Change? Efficiently Assessing Machine Learning API Shifts 
Authors: Lingjiao Chen
Matei Zaharia
James Zou
Venue: ICLR 2022 Poster (2022)
Keywords: ML API performance shifts
ML as a service
ML monitoring
ML performance evaluation

Abstract: ML prediction APIs from providers like Amazon and Google have made it simple to use ML in applications. A challenge for users is that such APIs continuously change over time as the providers update models, and changes can happen silently without users knowing. It is thus important to monitor when and how much the MLAPIs’ performance shifts. To provide detailed change assessment, we model MLAPI shifts as confusion matrix differences, and propose a principled algorithmic framework, MASA, to provably assess these shifts efficiently given a sample budget constraint.MASAemploys an upper-confidence bound based approach to adaptively determine on which data point to query the ML API to estimate shifts. Empirically, we observe significant ML API shifts from 2020 to 2021 among 12 out of 36 applications using commercial APIs from Google, Microsoft, Amazon, and other providers. These real-world shifts include both improvements and reductions in accuracy. Extensive experiments show that MASA can estimate such API shifts more accurately than standard approaches given the same budget

Published as a conference paper at ICLR 2022
How DID THE MODEL CHANGE? EFFICIENTLY As- SESSING MACHINE LEARNING API SHIFTS
Lingjiao Chen, Matei Zaharia, James Y. Zou
Stanford University
(1 ingg ao, jamesz] @st.anooddd.... edu mateifBss.stanorrdccc edu
ABSTRACT
ML prediction APIS from providers like Amazon and Google have made simple to use ML in applications. A challenge for users is that such APIs continuously change over time as the providers update models, and changes can happen silently without users knowing. It is thus important to monitor when and how much the MI APIs' performance shifts. To provide detailed change assessment, we model ML API shifts as confusion matrix differences, and propose a principled algorithmic framework, MASA, to provably assess these shifts efficiently given a sample budget constraint. MASA employs upper-confidee confidence bound based approach to adaptively determine on which data point to query the ML API to estimate shifts. Empirically, we observe significant ML API shifts from 2020 2021 among 12 out of 36 applications using commercial APIs from Google, Microsoft, Amazon, and other providers. These real-world shifts include both improvements and reductions in accuracy. Extensive experiments show that MASA can estimate such API shifts more accurately than standard approaches given the same budget.
INTRODUCTION
Machine learning (ML) prediction APIs have made it dramatically easier build ML applications.
For example, one can use Microsoft text API MMic a to determine the polarity of a text review written by customer, or Google speech API (Goo b recognize users' spoken commands received
by smart home device. These APIs have been gaining in popularity (MLa Chen et al. 2020). as they eliminate the need for MI. users to train their own models.
Monitoring and assessing the performance of these third-party ML APIs over time, however, is under-explored. ML API providers continuously collect new data or change their model architectures (Qi et al. 2020) to update their services, which could silently help or harm downstream applications' performance. For example, as shown Tigure[(a) and (b), we observe a 7% overall accuracy drop of IBM speech API on the AUDIOMNST dataset in March 2021 compared March 2020. In systematic study of 36 API and dataset combinations, there are 12 cases where the API's performance changed by more than 1% the same dataset from 2020 to 2021 (sometimes for the worse). Such performance shifts are of serious concern not only because of potential disruptions to downstream tasks, but also because consistency often required for audits and oversight. Therefore, it is important to precisely assess shifts in an API's predictions over time. Moreover, in this assessment, it is often more informative quantify how the entire confusion matrix of the API has changed rather than just the overall accuracy. In the IBM case in Figure I it is interesting that a major culprit of the drop in performance the 2021 model mistaking "four" for "five". In other settings, changes in the confusion matrix could still cause issues even if the overall accuracy stays the same.
In this paper, we formalize the problem of assessing API shifts as estimating changes in the confusion matrix on the same dataset in sample-efficient manner (i.e., with few calls to the API itself to minimize dollar cost). The straightforward approach is to compare the API's prediction on randomly sampled data. However, this can require large number of API calls estimate the confusion matrix, which is expensive given that each call costs money. To help address this challenge, we propose MASA, a principled algorithm for ML API shift assessments. MASA efficiently estimates shifts in the API's confusion matrix by clustering the dataset and adaptively sampling data from different clusters query the API. M MASA automates its sampling rate from different data clusters based on

---

Published as a conference paper at ICLR 2022
2.9
0.0 0.0 0.0 0.0 0.0 0.0
Overall accuracy:98.3
0.1 0.0 0.0 0.0
- 8.8
0.0 0.0 0.2 0.3
Overall
accuracy:91.2
0.0
0.0
0.1
0.0
0.0 0.7
square 10rro10 norm error
10
MASA
0.0
0.0
0.0
0.0
0.0
0.0
0.4
0.0
0.0
00
0.0
Uniform
0.0
0.0
0.0
9.
0.
0.0
02
0.0
0.0
0.0
0.0
0.0
0.0
0.1
94
0.
0.0
02
0.0
0.1
0.0
0.1
10
0.0
0.0
0.
0.0
07
0.0
0.0
0.0
0.1
0.0
0.0
0.0
2.6
0.0
0.3
0.0
0.0
0.0
0.0
0.0
0.0
0.0
2
0.1
0.0
0.0
0.0
0.0
0.1
10-4
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
10-5
2 Predicted label
5
8
9
500 1000 1500 2000
Predicted label
Sample size
(a) Confusion matrix 2020 (%)
(b) Confusion matrix 2021 (%)
(c) Shift estimator performance
Figure I: ML API shift for IBM speech recognition API on AMNIST, a spoken digit dataset. (a) and (b) give its (normalized) confusion matrix in April 2020 and 2021, respectively. There is an overall 7% accuracy drop. One factor is the 2021 model incorrectly predicting more "four" as "five". (c) Given a sample budget, the proposed MASA can assess the API shift with much smaller error in Frobenius norm compared to standard uniform sampling.
the uncertainty in the confusion matrix estimation. For example, MASA may query the MI. API on more samples with the true label "four" than "one", if is less sure about the estimated performance copeer-cofideeccebbooee
change on the former. Employing MASA enjoys a low computation and space cost as well as fast estimation error rate guarantee.
approach estimate the uncertainties,
MASA's 's adaptive sampling substantially improves the quality of estimation for API shifts. In extensive experiments on real world ML APIs, MASA's assessment error is often an order of magnitude smaller than that of standard uniform sampling with same sample size (e.g.. Figure (c)). To reach the same tolerable target estimation error, MASA A can reduce the required sample size by more than 50%, sometimes up 90%.
Contributions. In short, our main contributions include:
1. We demonstrate that commercial MI APIS can experience significant performance shifts over time, and formulate ML API shift assessments via confusion matrix difference estimation as an important practical problem. We will release the dataset consisting of 1,224,278 samples annotated by ML APIs in different date to stimulate more research on ML API shifts.
2. We propose MASA, algorithm to assess the ML API performance shifts efficiently. MASA adaptively determines querying the ML API on which data points to minimize the shift estimation error under sample size constraint. We show that MASA enjoys a low computation cost and performance guarantees.
3. We evaluate MASA on real world APIs from Google, Microsoft, Amazon and other providers for tasks including speech recognition, sentiment analysis, and facial emotion recognition. MASA leads to estimation errors an order of magnitude smaller than standard uniform sampling using the same sample size, or over 90% fewer samples to reach the same tolerable estimation error. Our code and datasets are also released [
Related Work. Distribution shifts in MI. deployments: Performance shifts in MI systems have been observed in applications like discase diagnosis (Lipton et al. 2018). facial recognition (Wang) ctt al. 2020), and Inference of molecular structure (Koh et al.J 2020). Most of them are attributed to distribution shifts, i.e., the distribution of the test and training datasets are different. Distribution shifts are usually modeled as covariate shifts (Shimodaira) 2000 SSgiyama et al., 2007 Quiñionero Candela et al.] (209)) label shifts (Lipton et al.] 2018 Saerens et al. 2002 Azizzadenesheli et al. 2019:ZZho et al. 2021). API shifts are orthogonal to distribution shifts: instead of attributing the performance shifts to data distribution changes, API shifts concern with MI APIs changes which changes its predictions on the same dataset. The methods for detecting distribution drifts typically rely on changes in data feature statistics and can not detect changes in the API on the same data. To the best of our knowledge, MASA is the first work to systematically investigate MI. API shifts.
https://gi thwb. com http:/1chee0011111 /MASA
2

---

Published as a conference paper at ICLR 2022
ML API Google Amazon
+2.0
-1.1
+2.5
+1.5
MS
+3.0
0.0
0.0
0.0
IBM
+3.3
-7.1
0.0
0.0
ML API
Facer+ Google
ML. API
Google
0.0
0.0
0.0
0.0
-1.2
0.0
+24.1
+7.5
+5.0
+0.6
0.0
0.0
0.0
0.0
0.0
+0.7
0.0
0.0
MS
-1.6
+0.2
0.0
+0.3
YELP
IMDB
WAIMAI
SHOP
FER
RAFOB
EXPW
AFNET
DIGIT
AMNIST
CMD
FLUENT
Dataset
Dataset
Dataset
(a) Sentiment Analysis
(b) Facial Emotion Recognition
(c) Speech Recognition
Figure 2: Observed overall accuracy changes. Each corresponds to ML API, and each column represents a dataset. The entry is the overall accuracy difference between evaluation in spring 2020 and spring 2021. In 12 out of 36 cases, the API's overall accuracy changed by more than 1%; this includes several cases of substantial drops in performance.
Several issues in deployed ML APIs have been studied. For example. Buollamwni & Gebru (0118) showed that strong biases toward minority can exist in
Deploying and monitoring ML APIs:
commercial APIS and Ribeiro et al. (0200) revealed that several bugs in commercial APIs can be
detected using checklists. Kang et al. (2020) extend program assertions to monitor and improve
deployed ML models. Chen al. (2020) consider the trade-offs between accuracy performance and cost via exploiting multiple APIs. On the other hand, the proposed MASA focuses on estimating (silent) API performance changes cheaply and accurately, which has not been studied before.
Stratified sampling and multi-arm bandits: Stratified sampling has proved to be useful in various domains, such approximate query processing (Chaudhuri et al., (2007). population mean estimation (Carpentier et al. 2011 2015). and complex integration problems (Leprêtre et al. 2017). A common approach to model stratified sampling as multi-arm bandit (MAB) problem: view each data partition
and set the regret as the variance of the obtained estimator. Plenty of algorithms exist for solving standard MAB problems, such as the epsilon greedy algorithm (Slivkins) (2019). upper-confiddece-bouur approach (Auer et al., 2002), and Thompson sampling method (Russo et al.) 2018). While those algorithms aim at playing the best arm as often as possible, stratified sampling's goal is often to estimate the average of all arms, and thus needs allocate the number of calls for all arms aptly based on their variance. In contrast to estimating the population average in standard stratified sampling, our goal is to simultaneously estimate matrix whose entries can be correlated. Thus, we have an objective (uncertainty score) that is different from theirs (variance), which also leads an optimal allocation different from that of standard stratified sampling. This difference requires additional statistical bounds to prove convergence, which we provide in our paper. It also results in different upper-confidence-bonnt term and convergence rate compared to standard bandit. algorithms.
2 THE API SHIFT PROBLEM
Empirical assessment of ML API shifts. We start by making an interesting observation: Commer- cial ML APIs' performance can change substantial over time on the same datasets. We investigated twelve standard datasets across three different tasks, namely. YELP (Dal IMDB (Maas et a WAIMAI (Dat 6b. SHOP (Dat for sentiment analysis, FER+ (Goodfellow al., 2015). RAFDB eL a..). EXPW (Zhang et al.), AFNET MMolahosseini et al. (019) for facial emotion recognition, and DIGIT (Dai d). AMNIST (Becker et 2018). CMD (Wrdden] 2018), FLUENT (Lugosch et al.). for speech recognition. For each dataset, evaluated three commercial ML APIs' accuracy in April Figure2]summarize summarizes the overall accuracy changes.
2020 and April 2021. Figure?
There are several interesting empirical findings. First, API performance changes quite common. In fact, as shown in Figure - API performance changes exceeding 1% occurred in about 33% all (36) considered ML API-dataset combinations. Since the data distribution remains fixed, such a change is due to ML APIs' updates. Second, the API updates can either help or hurt the accuracy performance depending the datasets. For example, shown in Figure (a), the Amazon sentiment analysis

---

Published as a conference paper at ICLR 2022
DLM
Pick partition uncertainty score
Dr.
Get
An
Query ML API
[
Update uncertainty and other parameters
sample
Figure 3: How MASA works. MASA first partitions the dataset. Then it picks which partition to sample based on some uncertainty measurement, queries the ML API on the drawn sample, and uses the API' prediction to update uncertainty and estimated shifts on this partition. This is repeated until the MI API has been queried N times. Finally, the estimated shifts on different partitions aptly fused to obtain the desired API shifts.
API's accuracy increases on YELP, WAIMAI, and SHOP, but decreases on IMDB. In addition, the update of Microsoft facial emotion recognition API only affects performance on the FER+ dataset, as shown in Figure 2 (b). Another interesting finding is that the magnitude of the performance change can be quite different. In fact, most of the accuracy differences are between 1-3%, but on DIGIT dataset, Google's s accuracy change is more than 20%.
Fine-grained assessment of API shift as changes in the confusion matrix. Based on feedback from practitioners, accuracy change alone is insufficient, and attribution to per class change is often much more informative (Tipas et al. 22200) Hou et al. 2219:; Luque et al., 2019). Thus, natural idea is to quantify an ML API's performance by confusion matrix. We assess the change of the confusion matrix over time measure of API shift.
Formally, consider an MI. service for classification task with labels. For data point x from some domain X, let j(x) E [7.] denote its predicted label on and y(œ) be the true label. For example, for sentiment analysis, x is a text paragraph, and the task is to predict if the polarity of x is positive negative. Here L 2, and ツ(x) I implies positive predicted label while ((x) ) = 2 indicates negative true label. The confusion matrix is denoted by C E R where Ci, A Pr(y(#) = i, (<r) = .j]. Given a confusion matrix of the MI. API measured previously (say, a few months ago), C" the ML API shift is defined as AC C CO.
Using confusion matrix difference quantify the ML API shift is informative. E.g. the overall accuracy change is simply the trace of AC It also explains which label gets harder or easier for the updated API. Still consider, e-g., sentiment analysis. Given a 2% overall accuracy change, AC = 1% and 2C2,1 1 -3% implies that the change is due to predicting less (-3%) negative texts as positive, by sacrificing the accuracy on positive texts slightly (1%). This suggests that the API could have been updated with more negative training texts.
MASA: ML API SHIFT ASSESSMENT
Now we present MASA, an algorithmic framework efficiently to assess ML APT shifts. Suppose old confusion matrix Oo and large labeled dataset D are available. Given a query budget N, our goal is to generate Ač, estimation of the API shifts accurately possible by querying the ML API (() on N samples drawn from D.
MASA achieves its goal via adaptive sampling approach (Figure 3). It first divides the given dataset into several partitions (clusters). Then it adaptively decides which sample to query the ML API in an iterative manner: each iteration, selects one data partition based on some uncertainty measure (defined below), and queries the ML API on one sample randomly drawn from this partition. The API's prediction is obtained to update the uncertainty measure as well as the estimated shift AČ. This process repeated until the ML API has been queried N times or a stopping rule reached. We explain each step in detail next.
3.1 DATA PARTITIONING
A key intuition in MASA is that not all samples equally informative for estimating API shifts. Consider, for example, a vision API makes perfect predictions on "dog" images, and guesses randomly on "cat" pictures. The "dog" images are less informative, small sample of "dog" queries
4

---

Published as a conference paper at ICLR 2022
would tell that there is essentially no confusion for this class. Intuitively, within sample budget, an estimator with more samples from "cat" pictures should be more accurate overall than that from "dog". Generally, harder images tend to be more informative.
Thus, is a natural idea to partition all data points based on factors that may correlate with their informativeness, and sample from those partitions separately. In MASA, use partitions Da that each contain the points with true label i and difficulty level k. The difficulty level is an integer indicating how hard it is to predict the data point's label. needs not be perfect, and can be simply the discretized prediction confidence generated by some simple ML models. A total of L labels and K distinct difficulty labels lead to a total of LK partitions. If the uncertainty or variability of the ML API's prediction on each partition is different, then drawing different number of samples from each partition may improve the shift assessment performance compared standard uniform sampling. We verify this empirically in our evaluation (Section 4h.
3.2 BUDGET ALLOCCATION PROBLEM
Given the data partition, two questions arise: (i) how many samples should be drawn from each partition, and (ii) how estimate the MI. API shifts given available samples. The second question is relatively straightforward. Note that the API shifts satisfy
K
AC,,j = Pr(y((x) = i =] =| -
Σ
Prlu(s)= = j. - Ci.
-i,1--C
i=1 k=1
Pr(z E Dr.A) = 5| E Di.k] Ci Σ Pr(i(x)= = j, Di.k] 0i. = -EPi
k=1
where the first equation is by definition, the second due to total probability rule, the third uses the fact that Da. implies yxx) i, and the last equation applies conditional probability. Here, Pr(w E Dr,s] is simply ratio of size of partition Di.t and entire dataset D, known a prior. To assess ACig we only need to estimate Pr(ő(=) = j|ar Da,s). J. the predicted label distribution on partition Dr,K- It can be estimated simply via the frequency of predicting label j among all available samples drawn from D...-
Now we consider the sample allocation problem. For ease of notation, we denote Pr[æ;; E Diul by Pi,k, Pr(j(z) = j|æ E Da.s] and its estimation by Haas and P....j. respectively. Then for deterministic sample allocations, the squared Frobenius norm error can be written as
E
||A -
= >> E AOC.
AC:.)²==
=E E Σ Pi.eltann Ardis))
Σ B (IME, p1
k.j.k
Thus we use the loss C(A,N) 2 Σ C.
(1ar.,,) - 1)) to measure the performance of any sample budget allocation algorithm A using N samples. For any fixed N, our goal to find a sample budget allocation algorithm A to minimize the loss L(A,N) Notably, we can generalize it for other scenarios by replacing (AC ΔÒ) with W @ (AC AC), where @ is element-wise multiplication and W is an L x L weight matrix. Different choices of W can penalize the error of each entry in AČ differently and serve for different purposes. For example, if misclassifying label label 2 the only focus, then we can simply set W matrix as the weight W. then it becomes equivalent to estimating the overall accuracy by minimizing the variance. To minimize the loss for the general scenarios, Algorithm I (which is explained in the rest of this section) still applicable by simply multiplying the API selection formula (line 3 in Algorithm l with its corresponding weights.
P. L.
and W i, = O, (i. * (1, 2). If we use the identity
3.3 UNCERTAINTY SCORE AND OPTIMAL ALLOCATION
The optimal sample allocation is directly connected to how informative each data partition is. To see this, let us first introduce the notation of uncertainty score for each data partition.
5

---

Published as a conference paper at ICLR 2022
Algorithm 1 MASA's ML API shift assessment algorithm.
Input :ML API i(-), query budget N, partitions Di,,, E RLXX O E LLL and a > 0
Dutput:Estimant ML API Shift AČ E R
Set N
OLx K, OLXXXL = OLKK, H -OXXXL
Initialization
for n 1 to N do
ki,
iNN <2
(i*)*)
Determine data partition
Pitk arg k Ni.
0z,k +
o/w
Ni.
Sample din from Di- A= and query the MI API to obtain j(xx) N. + NN +1
>> Update sample size
Pu - Ma
i + 1ocmn)= and
Vj E
[
D Update predicted label distribution
N.
H ,n" H
ifN PNe. <2
Hi glend 2.
Update uncertainty score
07 0/.,u.+ +
o/w
Ne
H ((x))
t Hi M(an)
+1
b Update label frequency
end
Return AC E glxL where ACis Eken L Ci,,, Vi,
Confusion estimation
Definition 1. oi2 E/
E Di,l)) denotes the uncertainty score of Di.k-
The uncertainty score quantifies how informative each Di,e is by subtracting from the sum of the square of each label's probability mass. The uncertainty score is related to collision entropy (discussed in Appendix A). and determines the optimal allocation as follows.
Lemma 1. Let A be the sample allocation algorithm that achieves the smallest expected squared Frobenius norm error. Then the number of samples drawn from D by A is
Pi..Oik
N
Pr.
Lemma shows that the optimal budget allocation depends on the uncertainty score, but in practice, we do not know the uncertainty score before drawing samples and querying the ML API. Thus, natural question is how to estimate the uncertainty score o Suppose n samples, ... Zn. drawn from partition Di, Then
estimate o? by
o A
Σ
1((x))=((m))
(3.1)
n(n
3.4 AN UNCERTAINTY-AWAR ADAPTIVE SAMPLING ALGORITHM
Now we have a chicken-and problem: estimating the uncertainty scores is needed find the optimal sample allocation, but sampling from all partitions is needed to estimate their uncertainty scores. To overcome this issue, we adopt an iterative sampling approach, shown Algorithm
[ At each iteration, it alternates between (i) uncertainty score-based new sample selection (line
4) and (ii) uncertainty score and predicted label distribution update using the new sample (line
8). After querying the ML API N times, the API shifts are obtained by (iii) fusing the estimated predicted label distribution on each partition (line 10). We give the details as follows.
Uncertainty score and predicted label distribution update. After obtaining the predicted label for a sample from partition Dz . we need to update (i) the number of samples already drawn from this partition, denoted by Nr- Nr. kt. (ii) the estimated predicted label distribution, denoted by ( y Vjj and (ii) the estimated uncertainty score, o A... For N 5+ R and f (line 5-6), we use standard incremental update approach (Cotton) 1975), which requires constant space and computational cost per iteration. For o we additionally maintain the number of label j being predicted among all
samples drawn from D,- kt, denoted by He. (line 8). This enables fast incremental update of o? (line 7).

---

Published as a conference paper at ICLR 2022
Uncertainty score-based new sample selection. To determine which partition to select new sample, we use an copper-coffidenc-beee in line 3), after ensuring
approach on the weighted uncertainty score (second case samples have been drawn from each partition (first case in line 3). Two samples are needed for an initial estimation of each partition's 's uncertainty score. Here, we use a parameter > 0 to balance between exploiting knowledge of uncertainty score (0),)) and exploring
more partitions (V NER
We quantify the performance of MASA v.s. the optimal allocation algorithm A as follows. Theorem 2. If a > 2 L + log K + a log N and N 4LK, then have
L(MASA, N) L(A", N) & O(N log N)
Roughly speaking, Theorem shows that the loss gap between the API shift estimated by MASA and the (unreachable) optimal allocation algorithm ceases in the rate of N 5/44 Note that the loss of the optimal allocation decays in the rate of N Thus, as N gets larger and larger, the relative gap becomes more and more negligible.
EXPERIMENTS
We apply MASA to estimate the shifts of several real world ML services for various tasks. Our goal is three-fold: (i) understand if and why MASA assess the API shifts efficiently, (ii) examine how much sample cost MASA can reduce compared to standard sampling, and (iii) exploit the trade-offs between estimation accuracy and query cost achieved by MASA. We also study how the hyperparameters affect MASA's 's performance, left to Appendix
Tasks, ML APIs, and datasets. As shown in Section 2 we have observed 12 of 36 cases where there is a >1% overall accuracy performance change of an ML API. Thus, we focus on evaluating those 12 cases. Except for case study, all experiments were averaged over 1500 runs. In all tasks, we created partitions using difficulty levels induced by a cheap open source model from GitHub. More details in Appendix C
MASA's 's performance
Sentiment analysis: a case study on Amazon API. We start by a case study on Amazon API on sentiment analysis dataset, YELP to understand MASA's performance. We adopt MASA with sample budget 2000. The dataset is divided into 4 partitions ++.,, D+.,. D.. D_ .hs depending on whether the true label is positive (+) or negative (-), and quality score produced by the 2020 version is lower (I) or higher (h) than the median.
We first note that the API shift gives an interesting explanation to Amazon API's accuracy change. In fact, as shown in Figure (a-c), the accuracy increase is mostly because more texts (2.7%) with negative altitudes are correctly classified. One possible explanation that the API has been retrained on a dataset with more negative texts. Next, observe that MASA produces accurate estimation of the API shift by comparing Figure (c) and (d). This is primarily due to (i) that the data partitioning separates more uncertain data from less uncertain ones, and (ii) that adaptive sampling learns the uncertainty level effectively. Figure 4 (e-f) shows that while the partitions' size is similar, their uncertainty scores are different. For example, higher quality score implies a much smaller uncertainty for positive texts (D+.h and D+,1 in Figure (t). As shown in Figure 4 (g). MASA indeed learns to utilize such imbalanced uncertainty: optimal allocation (dark star point). Finally, it is worth noting that MASA outperforms standard uniform sampling notably, as shown in Figure 4h). This is because uniform sampling does not exploit the uncertainty of each partition.
sampling allocation for each partition is quite close the
Budget savings achieved by MASA. In many applications, it suffices to obtain an estimated API shift close to the true shift, e.g., within 1% Frobenius norm error. Thus, natural question arises: to reach the same tolerable estimation error, how much sampling cost can MASA reduce compared to standard sampling approaches?
To answer this question, we compare MASA with two natural approaches: (i) uniform sampling and (ii) stratified sampling by drawing same number of samples for each true label. For each approach,
7

---

Published as a conference paper at ICLR 2022
negative positive
negative positive
negative positive
negative positive
40
40
48.2
1.8
47.5
2.5
-0.6
0.6
-0.5
0.5
20
20
11.2
38.8
8.6
41.4
-2.7
2.7
-2.6
2.6
-2
positive
negative
positive
negative
positive
negative
positive
negative (d) Estimated Shift
(a) CM 2020
(b) CM 2021
(c) True API shift
Partition fraction
Uncertainty score
1000
10"
MASA
Number of quaries
De.n
#-x
Uniform
D..,
10"
0.2
0.2
+ D.,A
Frobenius
10
0.1
10
0.0
0.0
1000 Eeration
2008
1000
2000
D.,1
D+, D.,,
D.,,
D+,1
D+,h D.,1 D.,h
Iteration
(c) Partition Size
Uncertainty score
g Sample allocation
(h) Performance
Figure 4: Case study for Amazon API's performance shift on dataset YELP. (a) and (b) give its confusion matrix spring 2020 and spring 2021, respectively. (c) is their differences, i.e., the API shift. MASA's 's estimated shift using 2000 samples is in (d). The dataset is divided into partitions based on (i) positive (+) or negative (-) true labels, and (ii) low (I) or high (h) quality score. (c) and (f) give the size and uncertainty score of each partitions. (g) shows MASA's sampling decision per iteration, where the dark dot points represent the (unreachable) optimal sample allocation, (h) reveals its performance.
Table 1: Required sample size to reach 1% Frobnius norm error. Here we compare MASA with uniform (U) sampling and stratified (S) sampling. U and S required very similar sample sizes and are reported in the same column. The sample size is obtained when % Frobenius norm error is achieved with probability 95%.
Sample size
Sample size
APl;Dataset
Save
API;Dataset
Save
MASA
U/S
MASA
U/S
Amazon;YELP
4.5K
19.7K
77%
IBM:DIGIT
3.6K
17.0K
79%
Amazon:IMDB
10.3K
20.8K
51%
IBM;AMNIST
2.4K
18.5K
87%
Amazon:WAIMAl
7.8K
18.0K
57%
Google:DIGIT
4.2K
17.0K
75%
AHaZ
4.8K
20.8K
77%
Google:AMNIST
1.1K
18.5K
94%
MS; FER+
2.6K
19.9K
87%
Google;CMD
1.6K
15.2K
89%
Google; EXPW
4.2K
17.9K
77%
MS;DIGIT
3.3K
17.0K
81% 31%
we measure the number of samples needed reach 1% Frobenius norm error with probability 95%, via an upper bound on the estimated Frobenius error. The details are left to Appendix shown in Table I MASA usually requires more than 70% fewer samples to reach such tolerable Frobenius norm error than the uniform and stratified sampling, primarily due to its shift estimation more accurate. Uniform and stratified sampling required the similar number of samples because the upper bounds on their estimated Frobenius error are similar.
Trade-off's between estimation error and query budget. Next examine the trade-off's between API shift estimation error and sample size achieved by MASA, shown in Figure 3 We first note that, across all 12 observed API shifts, MASA consistently outperforms standard uniform sampling for any fixed sample size. In fact, the achieved estimation enror of MASA is usually an order of magnitude smaller than that of uniform sampling. This verifies that M MASA A provide more accurate
8

---

Published as a conference paper at ICLR 2022
Squared morm eree
10--
MASA
Uniform
10
10
10
10
10
10
1000
2000
3000
1000
2000 Sample size
3000
1000
2000
3000
1000
2000
3000
Sample size
Sample size
Sample size
(a) Amazon YELP
(b) Amazon IMDB
(c) Amazon WAIMAI
(d) Amazon SHOP
10
10
10
10
10
10
10-1
10-4
10
10-1
1000
2000
3000
1000
2000
3000
1000
2000
3000
1000
2000
3000
Sample size
Sample size
Sample size
Sample size
(c) Microsoft FER+
(f) Google EXPW
( Google DIGIT
(h) Google AMNIST
10
10
10
10
10 -
10-
10
10-4
10-4
1000 2000
3000
1000
2000
3000
1000
2000
3000
1000
2000
3000
Sample size
Sample size
Sample size
Sample size
(i) Google CMD
(i) IBM DIGIT
(k) IBM AMNIST
(l) Microsoft DIGIT
Figure 5: API shift estimation performance and sample size trade-offs. We compare the expected squared Frobenius norm emror of MASA with K = 3 partitions versus standard uniform sampling. For any sample size, MASA consistently leads to an estimation error much smaller than uniform sampling across different API and dataset combinations.
assessments of API shifts diverse applications. Second, some API shifts are easier to estimate than others. For example, for Google API shift on AMNIST, using 1000 samples already gives an expected squared Frobenius norm error lower than 10-4, while usually requires 2000 samples for other shifts. This is probably because the skew in its uncertainties among different partitions is more severe than other shifts.
5 CONCLUSION
In this paper, we identify and formulate the problem of characterizing ML API shifts. Our systematic empirical study has shown that API model updates frequent, and that some updates reduce performance substantially. Quantifying such shifts is an important but understudied problem that can greatly affect the reliability of applications using ML-as-a-service. To capture fine-grained change assessment, we model the ML API shifts as confusion matrix differences. Adaptive sampling methods are typically designed for estimating a single scalar (e.g., adaptive population mean) or training model (e.g., active learning), and thus not directly applicable for API shift estimation. Uniform sampling natural but requires a large number of samples. Thus, we propose an algorithmic framework, MASA, to adaptively assess the API shifts using as few samples possible. Our work focuses on estimating changes in the confusion matrix because the confusion matrix is often what is used by practitioners to assess API performance. We acknowledge that confusion matrices most applicable for classification tasks, and other measures need to be used for more complex APIs (e.g. OCR, NLP). While this is limitation, classification with small to moderate number of classes of interest is a common use case for ML APIs, and this is an important starting point since it has not been studied before. We also release dataset of 1, 1,224,278 samples annotated by commercial APIs in different dates as the first dataset and resource for studying ML. API performance shifts.

---

Published as a conference paper at ICLR 2022
REFERENCES
Amazon Comprehend API. 2020 and March-2021).
[Accessed March-
Baidu API. htttps:/aii.bnn
AAceesed March-2020 and March-2021J.
SHOP dataset.
WAIMAI dataset.
httpa////e..//aaaaca///a/aaaaaar hasterr/dtaasts//iill b.
YELP dataset.
DIGIT dataset. d.
Face++ Emotion API.
http:///tt/////./////////t/oooot [Accessed March-2020 and March-2021].
Google NLP API. http::///hhhoo..ooooccco/aaaaaaa [Accessed March-
2020 and March-20211.
Google Vision API. [ttpp://clloo..poolle..c//////// [Accessed March-2020 and March-2021).
Google Speech API. http:://bbouu.ooolllccc////eeeer March-2020 and March-2021].
[Accessed
IBM Speech API. http:///aaooaaa..occcco////oooep
inn. March-2020 and March-2021).
wow.
[Accessed
Machine
Learning
as
Service
Market
Report
https
g
Microsoft computer httpoonnnootttttt/ererrrrremommm
wwt.:///////eo.evviie.i. uun wersserrviiio / 2oo2111vee-srrr.cce//ooppr22222. a. [Accessed March-2020 Marc and March-2021].
Microsoft speech API.
https://azure.ntt www.:uee..iroooooooo aetssoot.commeenuueeee wtt.eeicssssseess/s//esee /ttes://rrrrrriirrrr.......
services b. [Accessed March-2020 and March-
2021].
K.B. Athreya and S.N. Lahiri. Measure Theory and Probability Theory. Springer, 2006.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem, 2002.
103
Kamyar Azizzadenesheli, et al. Regularized learning for domain adaptation under label shifts. In ICL. 2019.
Sören Becker, et al. Interpreting and explaining deep neural networks for classification of audio signals. CoRR, htw/1807.033 .03418, 2018.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In FAT 2018.
A. Carpentier et al. Finite time analysis of stratified sampling for monte carlo. In NIPS 2011.
Alexandra Carpentier, Rémi Munos, and András Antos. Adaptive strategy for stratified monte carlo sampling. Mach. Learn. Res., 16:2231-2271 2015.
Surajit Chaudhuri, Gautam Das, and Vivek R. Narasayya. Optimized stratified sampling for approxi- mate query processing. ACM Trans. Database Syst., 32(2):9, 2007.
10

---

Published as a conference paper at ICLR 2022
Lingjiao Chen, Matei Zaharia, and James Y. Zou. FrugalML: How to use ML prediction apis more accurately and cheaply. In NeurlPS 2020.
Ira W. Cotton. Remark on stably updating mean and standard deviation of data. Commun. ACM, 18 (8):458, 1975.
Goodfellow, et al. Challenges in representation learning: A report on three machine learning contests. Neural Networks, 64:59-63, 63, 2015.
Saihui Hou, et al. Learning a unified classifier incrementally via rehalancing. In CVPR 2019.
Daniel Kang, al. Model assertions for monitoring and improving ML models. In MLSys 2020.
Pang Wei Koh, et al. WILDS: A benchmark of in-the-wild distribution shifts. CoRR, abs/2012.07421, 2020.
Florian Leprêtre, Fabien Teytaud, and Julien Dehos. Multi-armed bandit for stratified sampling: Application to numerical integration. In TAAI 2017.
Shan Li, Weihong Deng, and JunPing Du. Reliable crowdsourcing and deep Docality-preseenee learning for expression recognition in the wild. In CVPR 2017.
Zachary C. Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In JCML 2018..
Loren Lugosch, et al. Speech model pre-training for end-to-end spoken language understanding. In Interppecch 2019.
Amalia Luque, et al. The impact of class imbalance in classification performance metrics based on the binary confusion matrix. Pattern Recognit., 91:216-231, 2019.
Andrew L. Maas, et al. Learning word vectors for sentiment analysis. In HLT 2011.
Ali Mollahosseini, Behzad Hasani, and Mohammad H. Mahoor. Affectnet: A database for facial expression, valence, and arousal computing the wild. IEEE Trans. Affect. Comput., 10(1):18-31, 2019.
Haode Qi, et al. Benchmarking intent detection for task-oriented dialog systems. abs/2012.03929, 2020.
CoRR,
Joaquin Quinonero-Candela, et al. Covariate Shift by Kernel Mean Matching, pp. 131-160. 2009.
M. Ribeiro, al. Beyond accuracy: Behavioral testing of NLP models with checklist. In ACL 2020.
Daniel Russo, et al. A tutorial on thompson sampling. Found. Trends Mach. Learn., 11(1):1-96. 2018.
Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of classifier new priori probabilities: A simple procedure. Neural Comput., 14(1):21 1-11,, 2002.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. In JSPI 2000.
Aleksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn. 2019.
Masashi Sugiyama, et Direct importance estimation with model selection and its application to covariate shift adaptation. In NIPS 2007.
Dimitris Tsipras, al. From imagenet to image classification: Contextualizing progress on bench- marks. In ICML 2020.
Zhongyuan Wang, et al. Masked face recognition dataset and application. In Arxiv 2020.
Pete Warden. Speech commands: A dataset for limited-vocabulary speech recognition. In Arxiv 2018.
Zhanpeng Zhang, et Learning social relation traits from face images. ICCV2015
Eric Zhao, et al. Active learning under label shift. In AISTATS 2021.
11

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This work was supported in part by a Google PhD Fellowship. NSF CCF 1763191, NSF CAREER 1651570 and 1942926, NIH P30AG059307, NIH U01MH098953, grants from the Chan-Zuckerberg Initiative, Sutherland, and affiliate members and other supporters of the Stanford DAWN project- Financial, Meta, Google, Infosys, NEC, and VMware as well as Cisco and SAP. We also thank anonymous reviewers for helpful discussion and feedback.
Appendix Outline The appendix is organized as follows. Section A provides additional technical details. All proofs are presented in Section B We give experimental setups, details of datasets and ML APIs, and further empirical results in Section
A TECHNICAL DETAILS
Computation and space cost of MASA. One attractive property of MASA is its low computation and space cost. In fact, it can be easily verified from Algorithm | that, the computation cost is only linear in the number of samples N. The occupied space is only constant. Therefore, MASA can be easily applied for large number of samples.
Choice of parameter The parameter a is used to balance between exploiting and exploration in the default value. While theoretically a should
Algorithm|l | Throughout this paper, we set depend the partition size and sample number, in practice we found that = 1 works well. An in-depth analysis for this remains an interesting open problem.
Stopping rule under loss requirements. For MASA, we establish the upper bound the loss by (i) computing the upper bound on the estimated uncertainty score for each partition, and (ii) summing up all those upper bounds weighted by the partition size to form the upper bound the loss. For Uniform sampling or stratified sampling. we directly use the upper bound on the Frobenius loss. Here, adopt the standard upper bound for Bernoulli variables. That is to say, for any estimator using n samples, we use V as its upper bound, where c a parameter to control the confidence. For both methods, choose ensure 1% error under 95% confidence level.
B PROOFS
We present all missing proofs here. For ease of expositions, let us first introduce a few notations. We let rr denote the rith sample drawn in Algorithm [ and use I, indicate from which partition the sample E, is drawn. For example, I, (i, k) indicates that F,, is drawn from the partition D
Let Ze, E [L] denote the ML API's predicted label for the tth sample drawn from the partition DE.E- Abusing the notation little bit, let Ne.k. denote the value of N after the n 1th iteration and before the nthh iteration in Algorithm []] Similarly,
z,k, be the value of ô e,k. Pe. be the value of p.,x.j. and H e.k.j.n be the value H Hekk.j all after the 1th iteration and before the nth iteration in Algorithm In addition, let Dr, 2 Pridee
Pe and Amin min Ar Similarly,
let us denote min min By assumption that Pi,t > 0 and or 0, we must have Amin and min 0.
B. USEFUL LEMMAS
Let us first give a few useful lemmas. The first gives a high probability bound on our estimated uncertainty score.
Lemma 3. Let the event be
log 2/8
A
N
OEA S
1lt
21
LSKSK, ISI5N
j=
Then for any 8 > have Pr(A] 2 ILKN8.
12

---

Published as a conference paper at ICLR 2022
Proof.
For any fixed t, let us first denote
2 ... #E,R,)) A
1(1 - 1)
iml f=1,f$
Its expectation is simply
FER ,ZE,,,)) =B[1
1
t(t 1) i=1 j=1
=1 1
E
Σ
1) j=1,jii
=1 E 111
where the second equation applies the linearity of expectation, and the third equation uses the fact that all k are identically independent. Note that
E| =
Prizen. = Ze,uoll
Prize,u Pr|eee =
2 Pr(ze Pr(zen, =r]
Σ
where the first equation uses the definition indicator function, the second uses the fact that two sample are independent and there are only I. many possible labels, and the last equation uses the fact that those samples' distribution identical. Applying this in the above equation, we get
(1,(2 ".. ,e,,,))) =1 - E 20,,
=1 Prizen, = r| 0
That is to say, its expectation is simply the uncertainty score o²2 On the other hand, we note that, for any we have
fZrr....
Ze,kii 2
Ze, =e.,,)) f(ze,,,1.' 22,,,, 2 2eM.411"" ,z,,,,))
Σ j=1
12 1/
I S t(t- (t (t-1)=
t(t - 1)
where the inequality is due to the fact that the indicator function can only take values in {0, 1). Similarly, have
f(zEk11"" ZE,k. 266,,,
Ze.k..) -" "4 PLA.11 (.,,,))
Σ
IZEA 2 t(t ((--)) - 11
f(t 1)
j=1j
By Mediarmid inequality, we have
262
Pr(] Zc..2, ... z....) (LL ,Z 2|] 2e
St 1-
= 2e 2tc² -202
Set 8 = 2e 2e-2 216²
This simply becomes, with probability most 6,
21..2. " oZA.
log 2/8
-If(zz,e,1 2",2.""" .2e,,,) El ". .ZE, 2
2t
13

---

Published as a conference paper at ICLR 2022
Note that f is positive, can take square root of both side, and obtain with probability most 6.
log log 2/6
V F(ZE,,11 2 2,,,2,"" ; Fe,kk 2
2t
Or alternatively, with probability least ò,
log 2/8
VV [ZEA,, BEA,,," ZeA.,)) TE S
21
which holds for fixed e, k. Taking union bound, we know that with probability KLN6,
log 2/8
(ZE,,)) 2C
21
which holds for all e, k. Plugging in the form of completes the proof.
The next one is more technical: it gives connection between stopping time and adaptive sampling. omit the proof and refer the interested readers to (Athreya & Lahiri 2006). Lemma 4 (Wald's second inequality). Let {Fi]==...... be filtration and {Xi)t=1...... be Fe adapted sequence of i...d. random variables with finite expectation μ and variance ar. Assume that Fi and ofX,, + 1}) are independent for any t n, and let T(S n) be stopping time with respect to Ft. Then
T Σ i=1
X; - TM)
= =E[T] Var.
B.2 PROOF LEMMA
Proof. Recall that the loss, defined the expected squared Frobenius norm error, is
E - A0II
= Σ E ACC. - AO..)
Σe
E Σ
Epreeleen - Prddos)
2,5
Σ
K.J.k
Here we basically apply the definition of each entry. Suppose s, samples are allocated to estimate Mi,k.j" Then we have
1 Pr(o(=) ر| e (L, - j|a Dz,,))
E (Maak AA.,,)))²
N since M.,.. is effectively Bernoulli variable. Then the loss becomes
E -
Σ i.j.k
Pi (IMi,k.s 1)
1 Pr(o(x) i|z DR Pr(j(x) j|x Ds,k)) Ni,
Σ
P
k.j.k
Pr((((>) f|z DI Pr(j(x)) 1/x E Da,e))
P
N.k
i
where the last equation is simply by rearranging the summation. Note that
Σ Pr(j(a) = j/æ e Dr.e] =
The last summation is simply
Σ Pr(ū(z) j|æ E Da,a(1 Pr(j(x)) =jlar E Dr,k)) =1
Σ Pr(((()) = -|0 E Dr,k))
?
14

---

Published as a conference paper at ICLR 2022
Thus, the loss becomes
E
-
Σ
oi
i.ke
Nik
2
By Cauchy Schwarz inequality, we have
2
P
Σ
Nist
2
Wik
6,
i,k
1,
where the equality holds if and only if
Pi N
p p N
P
for any i, K. That is to say, there exists some constant e, such that
Pi
PV.NOV
N i
N
And thus, N, i,c. Summing over i, k gives
N = Σ Ni.
1
i,k
Thus,
N
C
Li
and
Pi,kO
Ni = Pc i.
E.pPrror
Ei, PiR
which completes the proof.
B.3 PROOF OF THEOREM
2
Proof. To prove this theorem, we need a few more lemmas.
Lemma 5. Algorithm|] Is computational cost is O(LKN) and space cost K), Farthermore, for any > 2LK, after the 1th iteration and before the nihh iteration, we have
Ne. Ne,
(=
1=1
Peks = Pe.kja
1 (E (as)=
Nek
Ōz, =ūikkn
Σ 1=1 j=
I =L, ((n
N NeR
(Ne,k,
Haky H Hekjjn
(= (
Proof. The computational and space cost be easily verified: shown in Algorithm [ the variables o, f.. H. N take space LK, L2K, L2 LK. Therefore, the space is bounded by K).
For the first 2LK iterations (line 3-8) in Algorithm 1 the computation cost is clearly O(I.K).
15

---

Published as a conference paper at ICLR 2022
For the rest iterations (line 10- 16), the most expensive cost is computing In. which requires LK computations per iteration. Therefore, the total computational cost is O(LKN).
Next show that the above four equations hold for every 2LK. We prove this by induction.
n = 2LK + 1: One can easily verify this by plugging the initial values established in line 3-8 in Algorithm [
2) Suppose the four equations hold for the case when n = m.. Now consider n = m + Now let us consider two cases.
Any e, l such that Im+1 # ke) There is nothing update,
N Ne.mm+1
N em
1=(AA))
Σ
1 (=
+0= Σ 1 (=(()))) - (m
1=1
1=1
=E 1=1
1 (=
Similarly, one can show that
Σ 1 (=
Peniim
N Nr, i=l
m
O.Kmm+1 = O.k.mm
Σ Jo
1 1 (c,)) ((0)) f(x,)
Ne (Ne... 1)
im
m
He H He.k.. Σ =
(((=)))
For some E", h-' such that Im+1 = (l", (())
Let first consider N Ner, We increment N e x- by one, and thus
m-1
m-1
Ne m+1 Ne +1 Σ
(m +1= Σ
A=(0)") 1,, (8*
(+)
Next consider pac , . Using similar argument as above, we have
Per Ae s.+11 - j.m + 1 ()(m)= P
N tr m0
Ne -1
1l (10m))))
P Jmm + N Ner
Ne (erpmt Ne
fe Ne dom
Ne Ne
Net Km
[0(mm)=f
11, 1o) N Ke,t
Ne Ne N Ne*
1=1
Σ
1 Je) 1 Man
Ne (e.km. m++
iml
16

---

Published as a conference paper at ICLR 2022
where the first equation is due to the update rule of fag- &k the second equation is simply grouping by M A 4.m- the third equation is due to the fact that N & -* = Ne +1, the forth equation is due the induction assumption, and the forth equation simply algebraic rewriting.
Now us consider 0²- , m+1+ We can write
be k'' mm+1
H He.k-.
-6 ke m + Ne m++
(1
02 'k-
N Ne -1
Ne - 0r km +
2
H
(1
Ne
N
-2
(000)) )(,,))
Ne
Ne (Ne
1)
i=1 j=1,f
H (000m.)mmmm
(1
N r 10,0mm+1
Ne -2
Σ
1 1, x.) 3
(N -e 2) ,* mm,+ 1)
i=1 j=1,jşi
H ke alan).m
(1
Ne ktmm1
Ne k" m++1 -1
m-1
Σ (e=
=1 Ne (N &t
1=1 j=1iti
2H 1r k ((*m).m
We ma ee mn+
where the first equation is by the update rule in Algorithm| 1 the second equation is simply rearranging the terms, the third equation uses the induction assumption, the forth uses the update rule on Ne.. and thus N also rearranging the terms.
Ve Jet ,m Ne mm+1 - 1, and the fifth equation is
On the other hand, by induction assumption, we have
He ((em)))m
1=(t A-) I (()m))
And thus
m-1
m
- (00))))))) + 2H e t-, (m
J=
=
(1) ((.))))
j Lijii
Hence, the above equation becomes
fe m+1 =1
Σ Σ
N te.kmmme
(N (Ne. te m+1 km1
1)
1=1 j=1.
17

---

Published as a conference paper at ICLR 2022
Finally, let us consider He j + ((m)). ). it is clear that
H - i.m
11- ((a)== +0
m-1
1 1- xe (t) + 11 1==(0 An) ((m))=
m
f 1- (+=,))
where the first is due that there is no update for this j. the third equation due to the fact that (zm)) # j. and all the other equations are algebraic rewriting.
If j ((=m), clear that
m-11
He Hee j.m +
1 1= an) ((a))= +1
1 Amm(t xx)) (( + 1 1 (x=, (am))
(- i=1
where the first is due to that there is no update for this j. the third equation due to the fact that (zm) and all the other equations are algebraic rewriting.
That is to say, we have shown that,
m
N Nikmm11
(E,k)
t=1
Penjja11
L (ex)
N Nekimm1 i=1
m
m
Otkkm+1 Ne (Nekmm+1~ 1)
1 (1.1) ((x)
Light
He = Σ ((n))=j
Am
always hold. By induction, can say that for any 2LK, the original equations hold, which completes the proof.
Lemma 6. Suppose that the event A holds. Set 8 2e Then for each e, k, we have
1
4
log 2/0 N 1
4LKN-I
N
Ni,
min
Amin
for any 1 1565 L.SLIIksS
Proof. To show this, let us first establish the following useful lemma.
Lemma 7. Suppose that the event A holds. If Algorithm 7 draws least one sample from Dio Dio after the first 2LK iterations, we must have, for every E, K.
-1
log 2/8
N 2 (Nio. 1)
Pi.k
Oia + +
Di
2(N
-1]
18

---

Published as a conference paper at ICLR 2022
Proof. Since the event A holds, we have
- Σ
log 2/6
- - -ek S
21
j=lgii
for every É, k, t. Since this holds for every fixed t, it should also holds for any random variable t. Specifically, we must have
Na
N Naiiin
log 2/6
Σ
Oek S
(N - 1)
2N E,8.0
j=ljøi
Note that, by definition,
Nukkn Nidkon Σ j=1io
O,kk VI
N, (.k.,(Nekk. (Ne,k. 1)
We can then rewrite the above inequality as
log 2/8 2N E.k.n
Øekknn TEA.
That is to say,
2/8
log 2/6 2N e.k.a
oe,k
Gikkn 0t.k
2N E,k.n
Adding V
log 2N....
to both sides, this becomes
log 2/8 2N E,
log 2/8 2N r.k.n
Oe S Oekin
Oe, + 2,
Multiplying both sides by Naa
Pr.
we have
Pe. Nek Nek
OEK S
Pe,
@eekn +
V
log 2/5 2N 2Nekmn
I
Nek.
Pe,k
Te.k + 2
log 2/8 2N e.k.a
(B.1)
which holds for any E, k, n. Note that N > 2LK, there must exist some for ko. such that Algorithm I draws sample from the data partition Dio after the first 2LK iterations. Suppose the last
time sample is drawn from Diock, is > 2T.K. That is to say, N No. = Nig 1, Vn
no + 1,.., N. Since Algorithm chooses to. ko at iteration no. by line 11 in Algorithm we have
lo, arg max
Pe, N Ne
(ō +
log 2/5
2N E.N.no
By definition of arg max, we have
ko ko
log 2/5
Pr.k (ō
log 2/8 2N 2N e.k.no
N Ko.
2N ko.
N N,k.no
Setting no in the first half of inequality B.I
have
Pe.k N
log 2/8
Pe.k Ogk,mn
+
2N f,k,no
N N.k.no
Combining the above inequalities gives
Pio (ō toohoing +
log 2/8
Pe,
Or.k 2N
N to Rg.
tn.ko.ng
N Nr,k,ng
19

---

Published as a conference paper at ICLR 2022
Noting that by definition, N k, I Ne,.NN N e,ks lower bound 1/N E,k,no by 1/N e,ks and the above inequality becomes
Poo (o
log 2/6
Pek dt, Ne.
+
) )
N no
2N ko.
Now setting no. no, = Lo, k Ko in the second half of inequality B.1 have
Pio
log 2/ō
Aoo
log 2/8
tookko +2
N ko
2N 2N ka
N No
2N Ro.
Combining the above two inequalities, we have
Pio (o + + 2N to No.
log 2/5
Pek N Ot
N to no
Observe that ni is the last time sample is drawn from partition Dio we have N Lo Ap.
N Ko 1, Vn = no + 1, .... N. Specifically, ii ho.mo N No N Ni - 1. Replacing
N mo by N ko in the above inequality, get
kko
log 2/5
PE.k New
N Ko - to + 2
2(N to - TT)
oek
which holds for every k. Rearranging the terms completes the proof.
Now we are ready to prove the bound on E, N Let us first consider the lower bound. By definition, we have
K
N = N
11k=1
Subtracting 2 from each element, we have
L
K
N 2LK
NN - 2) = N 2LK-
N
N
Note that by definition, N equality, and obtain
Ei=1
Ek=1 No. We can now replace the second N in the above
K NE - 2)
N 2LK
N
N
2LK
L
K
K N
(N 2LK)
N
N
N
N
E.
N
t=1 k=1
k=k=
t=k==
Now let us consider two cases.
N (LLK))
(N-KK)
(i) Assume V. - >
That is to say, No.
+
Then we have
N
N
1
1
<
(N-(K-2LK)
E.
+
N
20

---

Published as a conference paper at ICLR 2022
subtracting N; from both sides, we get
1
I Ni, (N,(N-21.K3 -21K)
Nec Ni.
Ni E
+2
NE. (NA(N-2TR)
-2
N
(2LK)
N
+2)
N (N-(N-2LK)
NE.
N
Ni -22K))
N
2LKNZA
N
Ni 21K)
N
N
2LK
N IN 2LK)
where the last inequality is simply by removing the constant 2. Now by assumption, > 4LK, we have N 2LK < J.N. The above inequality can be further simplified
1
1
2LK (N
4LK Ni N
E.k
Ni.
21K)
By definition, we have b.k N DeN S N Amin Therefore, we have
1
1
2LK
S 4LK
Nek
N
Ni -2LK) N N
That is to say,
1
4LK
N 8.
N E,k
And thus, apparently,
1
4
log 2/6 N-
1 1+
minn V
New
N
Amin
No N (N-2LK) Then there must exists some tu. ko such that N No
(ii) Assume N Ne.
No (N- (N-2LK)
N > 0. That is to say, Algorithm draws at least one sample from Dio.ko after the first we must have
2LK iterations. By Lemmal) 7
De.
log 2/8
N 2 (Ni..a 1)0rkk
Oto,ho + +2 2(N to - $1)
Pto
N No 2 No. Winck,,--- (N-2LK)
implies
N
N ko (N 2LK)
N to
1 Nio.
N
Therefore, this lower bound N Ko in the above inequality and obtain
21

---

Published as a conference paper at ICLR 2022
N (N 2LK)
Pe.k koo
log2/8
N& 2
N
Oit
kookko +
No (N- -22KK
N
N (N- 2LK)
to.ko
OeR.Pe,k
2
1/6
1+
N
koo
to
N No. (N-2LK)
Ni, (N 2LK)
log 2/0
14
N
Ko
kr (N-2
where the first equality is by dividing dt at both denominator and numerator, and the second equality uses the fact that Ni,, is proportional to ee Taking inverse of the above inequality gives
N N N (N - 2LK)
log 2/6
1
Ne.
ko
2
No
fo 21.K)
Now let us simplify this inequality. Let us first expand all terms and obtain
1
N
2
log 2/6
S NN - 2LK)
1+
Nep
N to (N- -2LK)
2LK
N
2
log 2/8
Nw + Ni - - -2LK) +
N2 - -2LK)
d to.ko
2
N
io (N -LK)
2LK
N
5
log 2/8
N
NN - -LLK)
Tto.ko
N 2LK
2N 2,
N
to.ko
For the second term, by assumption, N > 4LK and thus N 2LK > 1/2N, we have
2LK
4LK
N 2LK
N
Thus the above equation becomes
4LK
2
N
log 2/8
+
N 8.6
N
N
to
N
2LK
2N*1 N
to.ko
For the third term, N
4LK also implies
N
2LK
2LK
+
<
4LK - 2LK 2
N
2LK
2
Thus the above inequality can be further simplified as
1
4LK
log 2/8 N
NEA
N
N
N
N E.k ko
E
4LK
log 2/5 ko.ko
1
+
N
N
N
E.
22

---

Published as a conference paper at ICLR 2022
Now by definition, to 2 0 mins and N above inequality
No Ao
N NAmins further simplify the
to.ko
1
1
4LK
4
log 2/8
F,6
N
L,k
N
ko
N to
4LK
4
log 2/8
1
+
N Ni.
N
Eo
N NAmin
1
4LK
4
log 2/8
S
1
N
N
mmin
NA min
That is say,
4
log 2/6
+ +LKN -1
N
N
i,k
min
min
(N-22221. or not, this inequality always holds, which N
That to say, no matter Ne, 2 completes the proof.
Now we are ready to prove Theorem
Let us first note that the loss can be written as
K
CN
P Blube - pe
4 K
No
P Bl
Σ
1
(B.2)
NEA
t= =1k=1
t=1
K
1 No.
(HEKS
1 1)) 1c
N
1= k=1j=1
t=1
Let us first consider the first term.
ΣΣΣ Bl - 11
8=1 1
N Σ
Pe Bleee
)
New
(B.3)
t=1
N
2
ΣΣΣ
PiAk
1
1
N E,k
k=
where we plug in the definition of j.. By Lemma 6 we have the upper bound on 1/N e.k
4
log 2/5 N
1 1+4LKN-1
Nr.
N
mmin
Amin
Therefore, we can use this inequality to obtain
Nr.
E
NE
Σ
A
N2
[=1
(B.4)
+
4LK
N 2
4
log 2/5
N
N Ne..eeR
N
1 1
1
N
Amin
Omin
A
1=1
23

---

Published as a conference paper at ICLR 2022
It is not hard that N f.& is stopping time. In fact, for any e, k. and any time n, new sample is drawn purely based on estimated uncertainty score a and observed sample number N up to the current iteration, which is part of the history. As N P.k N is bounded, N, is a stopping time. Hence, we can apply Lemma and obtain
N2.
2
Nuk
27
N NEAMees
Σ
14
SE
EE N E PrizeA11 5](1 - Pr(ze,,11 5])
where the first incquality uses the fact that square term must be non-negative, and the second inequality uses the fact that, for Bernoulli distribution with mean a, its variance is a(1 a). Applying this in inequality B.4 we have
N Σ
E
1
NENMeRS
1 1
1a
N
NEC Σ
4LK
N
2
+
log 2/5
N 2
Ne.HERR
1
N
E,k
A Amiu
min
A
min
1=1
4LK
N
+
4 mmin
log 2/5
N N F
Pa/ 5](1 - Pr(zen, =]]
N
A Amin
A
min
Now applying this in equality B.3
we get
L
K
L
p
El(pE, - (2, 1aAl
K
No.
Pi.k
2 E
N2
NENPERS
Σ
1
A
1=1
K
4LK
4
log 2/8
Pik Ni.
+
N
N 8 Prizex,1 = 1](1 Prize,,, = =])
Amin
m
5
min
L
K
Pi
N
Amin
4LK
N
Owin
4
A min
2/8
N [
k=1
(B.5)
where the last equation uses the fact that d = Σ 1= Pr Pr [e = E/ Pr(zen.11 =
j] Prize,k. -1)- Applying the inequality 1/(1 x)) < 1-x
1
4 m
log 2/5 Amin
1 144LKN-
N
N NE.
N
E.k
24

---

Published as a conference paper at ICLR 2022
Note that
log 2/8
oi L.k
+ 44KN
N
| r.
t,k
Mmin
min
P )a
4 min
log 2/6
+ 4LKN
N
E[N
Nº.
A
Amin
log 2/5
=N-
Σ
Pe F
1 4LKN- +
N- 1
IE (
O
Amin
P.K
where the last equation is by definition Nek- Now applying this in inequality B.5 we have
Eleee
k=
K
1
4LK
N
4 min
log 2/8
N (
F.k
N
Amin
A
min
8=1 k=1
2
K
log 2/6
Pe POE
1 1+4KKN-
N-1
E|N
t=1 k=1
min
Amin
(B.6)
=N
Pe (ORK)
4+4LKN
4
log 2/6
N 1
Σ N
min
Amin
+ 4LKK 4
log 2/8
=N Pr (
N
N
Omin
min
4
log 2/8
=N PELLTEN)
1+4LKN
N
o miin
Amin
where the second equation uses the fact that only E e. depends on E, k: the third equation uses the
fact that Ele E Ne = N and thus Ele E E[Nea] = Note that d = L --1 --1
we have
N-1 E
1 1+4LKN PI,LOEH)) 4 min
log 2/5
N
Amin
E,K
= =N
E 2
1 + 1+ log' .N]]
E
=N-1
P(
- log N)
f.k
Applying this back to inequality
B.6
we have
K
P...y) ( SLASSN' +P logt N)
(B.7)
A=1
t.k
Now consider the second term in equation
B.2
As l and is are within {0, 1}, we have
N
(pr,Rs N
E [0,
25

---

Published as a conference paper at ICLR 2022
Therefore,
NLE
ΣΣΣ
P Bl
Σ
1
- )
Ael
p
Pr[A
Ne.
By Lemma 3 the probability of A is at least 1 - KLN6. Hence, the probability of A is at most KLN6 Hence,
L
K
N NEK
D Pi
)=² 1Acc]
p
Pr[A9]
K
LKN6
L Σ LKN8= L'KN6
where the last inequality uses the fact that Ele Σx Ek=1PE S 1 since Et Ex= Pe. = 1 and
PE, 2 0. Since 5 T, - 7, we have
1 K ΣΣΣ
N
1
1
1c
Nek
t=1
<L2KN8 < N
Applying this as well as inequality B.7 to the equation B.2 we have
CN
Pikk Eleeas PENd
New
PêR Bl
21
New 1=1
K L
Ne.
p
E
Σ
1, 2c
Nek
t=1
SN-
+ O(N- logå N
2,6
Note that the loss of the optimal allocation is simply Cy = DeA inequality is simply
The above
LN Ey < SON log N)
which completes the proof.
C EXPERIMENTAL DETAILS
Experimental Setups. All experiments were run on machine with 2 ES-2690 v4 CPUs, 160 GB RAM and 500 GB disk with Ubuntu 18.04 LTS as the OS. Our code is implemented and tested in python 3.7. All experimental results were averaged over 1500 runs, except the case study. Overall the experiments took about two month, including debugging and evaluation on all datasets. Running MASA once to draw few thousand samples typically only takes few seconds. Our implementation is purely in Python for demonstration purposes, and more code optimization (c.g., using cython or multi-thread) generate much faster implementation.
26

---

Published as a conference paper at ICLR 2022
Table 2: Dataset statistics.
Dataset
Size
# Classes
Dataset
Size
# Classes
Tasks
FER+
6358
7
RAFDB (Li et al.)
15339
7
FER
EXPW
31510
AFFECTNET
87401
7
YELP
20000
SHOP
62774
2
SA
IMDB
25000
2
WAIMAI
11987
2
DIGIT 2000
10
AUDIOMNIST
30000
10
SIT
FLUENT
30043
31
COMMAND
64727
31
Table 3: ML services used for each task. Price unit: USD/10,000 queries. We consider three tasks, sentiment analysis (SA), facial emotion recognition (FER), and spoken command recognition (SCR)
Tasks
ML service
Price
ML service
Price
ML service
Price
SA
Google NLP GoN
2.5
AMZN Comp (Ama)
0.75
Baidu NLP Bai
3,5
FER
Google Vision Goo a)
15
MS Face (Mic
Face++ Fac
5
SCR
Google Speech (Goo
60
MS Speech (Mic
41
IBM Speech (BM
25
ML APIs and Dataset Statistics. We focus on three common classification tasks, namely, sentiment analysis, facial emotion recognition, and spoken command recognition. For each of the tasks, evaluated three APIs' performance in spring 2020 and spring 2021, respectively, for four datasets. The details of datasets and MI. APIs are summarized in Table and (ebble@reppectveeee Now give more context of the datasets.
For sentiment analysis, are both English text datasets. YELP (Dai C is generated by drawn twenty thousand samples from the large YELP review challenge dataset. Each original review is labeled by rating in (1,2,3,4.5) We generate the binary label by transforming rating 1 and 2 into negative, and rating 4 and 5 into positive. Ten thousand positive reviews and ten thousand negative reviews are then randomly drawn, respectively. IMDB (Maas et al.) is a polarized sentiment analysis dataset with provided training and testing partitions. We use its testing partition which has twenty-five thousand text paragraphs. SHOP (Dat a) and WAIMAI (Dat) (b) are two Chinese text datasets. SHOP contains polarized labels for reviews for various purchases including fruits, hotels, computers. WAIMAI is a dataset for polarized delivery reviews. Both SHOP and WAIMAI are publicly available without licence requirements. There is a dataset user agreement for YELP dataset, which disallows commercial usage of the datasets but encourages academic study. Same thing applies to the IMDB dataset.
four datasets, YELP, IMDB, SHOP, and WAIMAL YELP and IMDB
For facial emotion recognition, we use four datasets: FER+, RAFDB, EXPW, and AFNET. All the datasets annotated by the standard seven basic emotions, i.e., (anger, disgust, fear, happy, sad, surprise, neutral). ). The images FER+ (Goodfellow et al.) 2015) are from the ICMI. 2013 Workshop on Challenges in Representation. We use the provided testing portion in FER+. RAFDB (Li et a and AFFECTNET (Mollahosseini et al. (2019) were annotated with both basic emotions and fine-grained labels. In this paper, we only use basic emotions since commercial APIs cannot work for compound emotions. EXPW (Zhang et al.) contains raw images and bound boxes pointing out the face locations. Here we use the true bounding box associated with the dataset to create aligned faces first, and only pick the images that are faces with confidence larger than 0.6. We cotnacted the creators of RAFDB and AFNET to obtain the data access for academic purposes. FER+ and EXPW are both publicly available online without consent or licence requirements.
For spoken command recognition, we use DIGIT, AMNIST, CMD, and FLUENT. DIGIT DDa d) and AMNIST (Becker et al. 2018) are spoken digit datasets, where the label is is a spoken digit (i.e..
0-9). The sampling rate is kHz for DIGIT and 48 kHz for AMNIST. Each sample in CMD (Warden 2018) is spoken command such as "go", "left", "right", "up". and "down". with a sampling rate of 16 kHz. In total, there are 30 commands and few white noise utterances. FLUENT (Lugosch et al.)
another recently developed dataset for speech command. The commands in FLUENT are typically
27

---

Published as a conference paper at ICLR 2022
Overall accuracy:79.1
Overall accuracy:78.0
Overall change:-1.1
True label negative positive
True label. negative positive
True label negative positive
44.1
5.9
39.0
11.0
-5.1
+5.1
15.0
35.0
11.0
39.0
-4.0
+4.0
positive negative Predicted label
positive negative Predicted label
posítive negative Predicted label
(a) Amazon IMDB 2020
(b) Amazon IMDB 2021
(c) Amazon IMDB 2021
Overall 31,
Overall accuracy.
Overall change:+3.
ange
0.0
angal
-000
Sor
Trus 1200
0.0
04
Truslabel
hapay
0.0
0.0
0.0
24.9
00
02
-0.0
40.0
-0.0
+10
cod
0.2
3.0
3.1
03
6.0
0.1
4.8
500
0.1
0.0
0.1
0.1
65
0.0
4.5
-2.1
-0.0
+3.0
-02
-0.
0.0
02
0.1
0.0
0.2
04
0.0
10.5
0.1
0.0
0.2
0.5
0.0
10.7
17
-0.0
10.0
10.0
-0.
4.0
10.4
-02
norasl
0.2
0.0
0.0
0.8
0.6
53.7
noukul
0.1
0.0
0.0
0.8
0.5
0.9
34.5
resta
0.11
+0.0
0.0
0.4
0.0
0.3
+0.6
anger
degus
Fear
hapoy
suppees mwam
anger
seud
far
Fredided
hapzy
EM suppee naum
anger
degust
Tear
73377
lasel
end
suplle 18377
(d) Microsoft FER+ 2020
(e) Microsoft FER+ 2021
(l) Microsoft FER+ API shift
accuracy:30.1
Overall 242
change:+24.2
H0.0H0 4+0. 000
0.0
3.3
0.1
0.0
0.0
0.0
0.0
0.0
0.3
6.0
6.5
0.0
000
0.0
0.0
0.0
0.3
0.0
0.1
0.0
4.8
+00 -0.0-1.--0011-- +0.0+0.00000000000000000000000.0 www.:e.......000000 00000.00...0 0-..0-0---------11
0.0
3.
0.0
00
00
0.0
0.0
6.2
0.0
77
00
0.0
0.0
0.0
0.0
+.10,0+0 10000001110000000000000000 www.::00000000000.000.0 000.0000000000000000000001000000 0-0
0.0
31
0.0
0.1
6.9
0.0
04
0.0
0.0
0.0
-+000-00-004411-000000000
0.1
0.0
0.1
1.5
0.0
0.0
0.0
0.0
0.0
8.5
--
0.0
0.1
0.0
0.0
35
0.0
0.3
0.0
0.0
0.0
6.3
0-000000.0+00000111
0.1
0.0
12
0,0
82
0.0
0.0
0.0
0.0
3--0.0
0.1
0.0
04
0.0
61
_-
0.1
0.1
0.0
00
2e+0.1-0.0000-0011 0.00400000000.000000111110000000
0.0
0.0
0.1
0.0
0.0
0.0
02
19
0.0
0.0
7
0.1
0.0
0.1
0.0
0.0
0.1
0.1
4.5
0.0
0.0
51
0-0000000
0.
0.0
0.0
0.0
0.0 0.0 0.0
0.1
45
0.0
02
0.0
0.0
0.0 0.0
0.0
0.0
82
05
4.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0 0.0 0.0
0.0
0.0
0.0
Predkcied labe
0
Predsted label
Piedeted labit
(g) Google DIGIT 2020
(h) Google DIGIT 2021
(i) Google DIGIT 2021
Figure 6: Confusion matrices of few APIs in spring 2020/2021, along with their API shifts.
phrase (e.g., "turn on the light" or "turn down the music"). There are in total 248 possible phrases, which are mapped to 31 unique labels. The sampling rate is also 16 kHz. All those datasets are freely available online for academic purposes.
Some of the datasets may contain personal information. For example, the human faces contained in the facial emotion recognition dataset may be deemed as personal information. On the other hand, study focuses on whether there is a performance change on the dataset, and does not use or disclose any personal information.
For sentiment analysis, we use the Google NLP API (GoN), Amazon Comprehend API (Ama). and the Baidu NLP API (Bai). For facial emotion recognition, we use Google Vision API (Goo a). Microsoft Face API Mic a). and the Face++ API (Fac). For spoken command recognition, we adopt Google speech API Goo b). Microsoft Speech API (Mic b). and IBM speech API (IBM).
Details of observed ML API Shifts. Now we present a few more observed ML API shifts, as shown in Figure 6 One observation is that individual entry's 's change in the API shift can be larger than the overall accuracy's. s. For example, as shown Figure (c), the overall accuracy change is about - 1.1% for Amazon on IDMB, but the performance drop for positive texts is as large as 5%. This indicates the importance of using fine-grained confusion matrix difference to measure API shifts. In addition, when the overall accuracy increases, it is possible that the accuracy for each label has been improved. This can be easily verified by Figure 6 (d-f). On the other hand, as shown in Figure 6 (g-i), Google API's large accuracy improvement (24%) is mostly because it is able correctly predict many samples that were previously deemed as empty. One possible explanation is that Google API internally uses higher threshold to generate recognition. When the number of label increases,
28

---

Published as a conference paper at ICLR 2022
Squared narm errer
K=1
10-1
K+3
10
10-4
10-4
10
1000
2000
1000
2000
1000
2000
1000
2000
Sample
(a) Amazon YELP
(b) Amazon SHOP
Amazon IMDB
(d) Amazon WAIMAI
10-3
10
10-4
10
10-4
Sample
(e) Microsoft FER+
Google EXPW+
IBM DIGIT
(h) IBM AMNIST
10
10-2
1000
2000
1000
2000
1000
2000
1000
2000
Sample size
Sample size
Sample size
Sample size
(i) Google DIGIT
(i) Google AMINST
(k) Google CMD
(I) Microsoft DIGIT
Figure 7: Effects of partition parameter K. The total number of partitions is LK, and thus Larger K implics more partitions. Generally, across 12 cases where API shifts identified, larger number of partitions usually leads to smaller estimation error for large samples. practice, we observe that K 3 is enough reach good error rate.
might become hard to manually check the API shifts. For those cases, an anomaly detector can be applied to quickly identify the most surprising components the API shifts.
Now we study how the partition number affects the performance of MASA, shown in Figure Across all API shifts estimated, of partitions leads to a smaller overall Frobenious norm in general. This is expected, as larger K effectively introduces more parameters estimate and thus more powerful. The trade-off that the computational cost increases, and more samples are needed for initial estimation. Interestingly, as K becomes large, the relative error reduction improvement becomes small. This is probably because there is strong uncertainty difference within small partitions. In practice, we found that K = 3 already gives a small enough error reduction.
Partition size's effects on MASA.
that larger number
Comparison with baselines for case study on YELP. To further understand MASA's performance,
We compared the performance of MASA with two baselines: random sampling and standard stratified sampling (proportionate allocation). We drawed 2000 samples for all methods, and repeated the experiments 1000 times to obtain average of the Frobenius baselines significantly: the observed error is 0.015 for random sampling, 0.009 for stratified sampling, and 0.006 for MASA.
error. MASA outperforms both
Understanding uncertainty score. MASA developed based on the notion of uncertainty scores, and thus it is worthy understanding how uncertainty scores of different partitions for an ML API are computed. Here, we provide an illustrative example, as shown Figure The dataset contains three partitions and each partition includes six data points. We point, its interior color to denote its true label, and its edge color to denote the predicted label of an evaluated MI API. For example, on partition and partition 3, all edge colors match interior colors,
small ball to represent each data
29

---

Published as a conference paper at ICLR 2022
Partition
Partition 2
Partition 3
Accuracy: 1.0 Uncertainty: 0.50
Accuracy: 0.5 Uncertainty: 0.00
Accuracy: 1.0 Uncertainty: 0.67
Figure 8: Illustrative examples of uncertainty scores. The dataset contains three partitions, each of which includes six data points. Here we use a ball to represent a data point, its interior color to denote its true label, and its edge color to indicate an ML API's predicted label. For example, as shown in the left panel, three points are labeled as red and the other three are labeled as blue. All points are predicted correctly, and thus the accuracy 1.0. As MI. API predicts half of the points as red and half as blue, the uncertainty score is 1 0.5 x 0.5 0.5 x 0.5 0.5. Note that high accuracy does not necessarily imply low uncertainty. For example, accuracy on partition (1.0) is higher than that partition 200.5), but its uncertainty score actually larger than the latter. Yet, high diversity in the predicted labels does imply higher uncertainty. For example, while accuracy on partition 1 and partition 3 are both perfect, partition 3 incurs higher uncertainty. This is because while only two unique predicted labels exist in partition 1, three occur in partition 3.
and thus the accuracy is 1.0. On partition interior and edge colors match only on half of the points, and thus the accuracy is only 0.5.
To understand the caleulation of the uncertainty score, let us take partition MI. API predicts the label red for half of the partition and blue for the other half. Thus, the uncertainty score is 1 subtracting the sum of the square of likelihood of each predicted label, i.e., 0.5 x 0.5 0.5 x 0.5 = 0.5. Similarly, on partition 2, the ML API always predicts the label blue, and thus the uncertainty is simply 1 unique labels, and thus the uncertainty score becomes
example. The
0. On partition 3, the ML API evenly predicts three
x 3 3 x 3 x
~ 0.67.
Two observations worthy mentioning about uncertainty scores, in addition their non-negativity and upper bound of 1. First, higher accuracy on partition does not imply lower uncertainty. To see this, note that the accuracy on partition (1.0) higher than that on partition (0.5), but its uncertainty score is actually larger than that of partition 2. In fact, an API's accuracy orthogonal its uncertainty, as uncertainty score only depends on the predicted labels and is independent of the true labels. Second, diversity of the predicted labels is correlated to the uncertainty score. For example, the accuracy same on partition and 3, but the uncertainty score is higher on partition 3, mainly because there are three unique labels (red, blue, and green) in partition 3. This is expected, as uncertainty scores are designed to capture how diverse an ML API's prediction can be.
partition
30


Reviews:
[{"review_id": "qNsUWQ3Z4Ui", "reviewer": "Reviewer_Bj8e", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Originality and significance**: To the best of my knowledge, this is the first work to systematically investigate the shift in the performance of commercial ML APIs. With the popularity of these services on the rise, it is important to study various aspects of the models, including the variations of the performance over time. The proposed sampling method is also novel and can be used in similar settings where model queries are expensive. The paper aims to minimize the Frobenius norm of the error in estimating the confusion matrix of classifiers, while keeping the sample complexity close to the optimal allocation strategy (in hindsight). The proposed algorithm asymptotically approaches the optimal allocation decay rate of 1/N. The empirical studies suggest that the proposed method can be an order of magnitude more sample efficient compared to random sampling.\n\n**Quality and clarity**: The paper is well written and motivates the problem with case studies and examples. The algorithms and theorems are clearly stated. I did not check the proofs in the appendix.\n\nSome limitations of the work:\n- The method (as described in the paper) only applies to classification settings.\n- Although not a strict requirement, the experimental analysis of the sampling method benefits from a rough estimate of the “difficulty” of each example before it is evaluated by the ML API . This “difficulty” is calculated by using a separate (client-side) cheap model. This goes against one of the main appeals of ML APIs that try to minimize client-side evaluation setup (think installing TF runtime, etc). There are no ablation studies on the quantified role of using such client side models.\n- The experiments could be improved by comparison to baselines other than random sampling. Though this might not be possible with updated APIs.\n\nNote: I was a reviewer to an earlier version of this work. Compared to the previous version, (1) the writing of the paper is improved in parts, (2) there is a more clear discussion of related work, and (3) the dataset is being publicly released.", "summary_of_the_paper": "This paper considers the problem of estimating the change in the performance of commercial ML APIs (ML as a service) as the models are updated over time (experiments are for 2020 vs 2021). It formalizes the problem as estimating the change in the confusion matrix over time. The main theoretical contribution is an adaptive sampling method to more efficiently estimate this shift. Interesting empirical results on various ML APIs are provided in the paper, showing the relevance of the problem and the effectiveness of the proposed method.", "summary_of_the_review": "This work opens a discussion around the problem of estimating the performance shift in commercial ML APIs (for classification). The paper defines a metric for the performance shift of such APIs (via the confusion matrix), and presents a method to achieve near optimal sampling rates.\n\nThe theoretical contributions of the paper are small but non-trivial. The experimental analysis is detailed and interesting, but could benefit from further ablation studies on the effect of the client-side difficulty gauge model. The problem is of interest to the ML community and the release of the annotated dataset used in this work would be useful to the community. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pdOi6BPRkgR", "reviewer": "Reviewer_NY7g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 problem addressed is important and the method seems to yield good results in practise in comparison to random sampling. \n\nOnce concern is its unclear why this problem cannot leverage some of the existing work on stratified sampling (based on explanation at the end of section 1) with the aim to reduce the variance of the estimator? Could you please elaborate on this. After all, the goal is to estimate elements of the confusion matrix. \n\nBased on section 3.3, does MASA yield an optimal allocation of API calls?", "summary_of_the_paper": "API shifts are common in several deployed machine learning models. This work proposes an efficient way to measure shifts in the confusion matrices of ML models using limited number of API calls. ", "summary_of_the_review": "API shift is an important problem that needs to be addressed in order to operationalising AI. This work proposes a way to assess these shifts using limited number of API calls and has a lot of practical importance. Most deployed ML models are also priced in a manner wherein each API calls has an associated cost and thus performing API shift assessment using limited calls is quite important even from a pricing stand point. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "jfeKk7tekNk", "reviewer": "Reviewer_2mEB", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths\n- The use case is one that is not often studied, yet is important both from a business accountability perspective (assessing the trustworthiness of a commercial ML API) and ethics perspective (providing information to society about hidden dangers in commercial ML APIs, which are difficult to track because of the algorithmic intransparency that is a common problem in the tech industry)\n- Algorithm is uncomplicated to implement, and provides clear improvement over naive sampling methods\n- Collected dataset on API shifts is novel, and is a major contribution of the work if released to the public\n\nWeaknesses\n- The idea of difficulty levels (K) is not well-developed. There are a couple of places where I was expecting more details: (1) some experiments use K=2 while others use K=3, what is the justification for doing so?; (2) I was expecting an ablation study comparing MASA with K=1 vs MASA with K>1. As the paper stands, it is unclear just how much of MASA's performance improvement over uniform and stratified sampling is due to K, versus the uncertainty-based sample selection.\n\nOther suggestions for improvement\n- Being able to measure the uncertainty in each partition, and use that uncertainty to inform sample selection, is the key idea that makes MASA perform better than uniform or stratified sampling. Given the importance of this idea, it would be better to explain this via an intuitive figure. As a suggestion, the authors could visualize how a partition in which the ML API classifies all data points with the same class (whether right or wrong) will have low uncertainty, while the opposite gives high uncertainty.", "summary_of_the_paper": "A method to estimate the confusion matrix of a black-box classifier, using as few samples as possible. The paper is focused around one use case: tracking changes in ML APIs, considering that such changes may go unannounced.", "summary_of_the_review": "The paper makes atypical but important contributions to ML ethics. Although the proposed algorithm is not groundbreaking from a technical perspective, it does contribute significantly towards measuring and tracking changes in black-box APIs, and I think it is of high value to society. I am concerned that the idea of difficulty levels (K) is not fully developed, but I lean towards acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "12Wbc1A39M-", "reviewer": "Reviewer_Z5qk", "summary": "", "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": "Strengths:\n- Tackles important practical problem of the result differences from ML APIs\n- Presents accuracy change results from a number of actual ML APIs from leading providers\n- Authors created a novel algorithm (MASA) to efficiently detect and evaluate result differences for ML APIs. \n- Authors demonstrate that MASA significantly outperforms baseline algorithms.\n\nWeaknesses:\n- Accuracy changes from actual ML APIs is limited in scope. Only few systems were analyzed and only for two dates (spring 2020 and spring 2021). It would be interesting and important to track both more systems and more time points\n- Unclear how confusion matrixes were used for speech recognition task, which presumably has a very large number of \"classes\". I am guessing authors treated speech recognition problem as classification problem for evaluation. However, there are no details on this. It would be good if this was explained and info provided.\n- As authors noted, confusion matrix difference is a good measure as a result drift only for certain (classification-like) APIs. It would be good to see how to deal with non-classification APIs.\n- Authors suggest that the differences seen in confusion matrix provide useful insights into how API results changed and why they changed. There is little substantiation of usefulness of how the API results changed. I.e. is confusion matrix difference really the best we can do to show how the API results changed? Regarding \"why\" the results changed, the authors provide guesses, but it seems to me that we cannot really know based on the results. If we cannot determine the \"why\", this should be stated. If we can, then it would be good to see what can be determined and how. \n\nMinor typo:\nPage 7: diffident - should be different.", "summary_of_the_paper": "Authors show that ML models behind publicly available APIs change and these changes cause result changes for input datasets.\nAuthors track the changes through confusion matrix differences. They propose an efficient algorithm they call MASA to evaluate the changes in results with reduced number of queries. Their algorithm achieves better estimates given the same budget than uniform sampling.", "summary_of_the_review": "I think that the problem of ML API result shift is real and important. I believe authors made interesting and useful contribution in evaluating such shifts. Although the paper has some weaknesses, I would recommend accepting it. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies real world ML APIs' performance shifts due to API updates/retraining and proposes a framework to efficiently estimate those shifts.  The problem is very important and the presented approach definitely novel. My concern is about limited novelty of the theoretical analysis and weak experimental evaluation (just two dates, limited number of systems tested, small number of ablations). As of now the paper looks like an interesting but unfinished proposal. Looking forward to the discussion between the authors and the reviewers to address the concerns.

In the rebuttal, the authors have addressed reviewers' comments, in particular by adding additional experiments that strengthen the paper. All the reviewers recommend the paper to be accepted. It is suggested that in the camera-ready version the authors will add additional details regarding the experiments, as some of the reviewers mentioned.
Decision: Accept (Poster)