# Nazar: Monitoring and Adapting ML Models on Mobile Devices

Wei Hao
Columbia University  Zixi Wang
Columbia University  Lauren Hong
Columbia University  Lingxiao Li
Columbia University  Nader Karayanni
Columbia University  Chengzhi Mao
Columbia University  Junfeng Yang
Columbia University  Asaf Cidon
Columbia University

###### Abstract

ML models are increasingly being pushed to mobile devices, for low-latency
inference and offline operation. However, once the models are deployed, it is
hard for ML operators to track their accuracy, which can degrade unpredictably
(e.g., due to data drift). We design Nazar, the first end-to-end system for
continuously monitoring and adapting models on mobile devices without
requiring feedback from users. Our key observation is that often model
degradation is due to a specific root cause, which may affect a large group of
devices. Therefore, once Nazar detects a consistent degradation across a large
number of devices, it employs a root cause analysis to determine the origin of
the problem, and applies a cause-specific adaptation. We evaluate Nazar on two
computer vision datasets, and show it consistently boosts accuracy compared to
existing approaches. On a dataset containing photos collected from driving
cars, Nazar improves the accuracy on average by 15%.

##  1 Introduction

Companies such as Google, Meta, Apple and LinkedIn, are increasingly running
their ML models _on users’ mobile devices_ , so they can run inference locally
at a low latency, even when the device is offline. Examples include text
suggestion [55, 18], ranking posts, object detection and tracking for virtual
reality [69], speech recognition [50] and targeted advertising [67]. As state-
of-the-art ML models are very large, they are typically trained in the
companies’ datacenters with fleets of GPUs [69, 53]. A team of _ML operators_
is usually responsible for retraining the models and pushing new model
versions to the users’ mobile devices.

However, in large-scale settings, ML operator teams lack sufficient visibility
into the performance of the ML models running on users devices [59]. Model
accuracy across devices is highly variable over time, and can change due to
unexpected shifts in the input data (termed _data drift_) or hardware issues
in specific devices (e.g., low-quality cameras, microphones) [19, 53].
Although the ML operators may fine-tune or retrain models to improve accuracy,
it is quite difficult today to detect data drift in the first place or verify
whether accuracy has been restored properly after fine-tuning [59, 53, 61,
60]. The crux is that after the models are deployed, the ML operators have no
“ground truth” on how accurate their models are because users do not manually
label data.

Although many algorithms from the ML literature can detect data drift [30, 44,
48, 28, 31, 42, 39, 32, 63, 38, 54, 64], and adapt to the drifts [41, 56, 62,
70, 45], they often operate with impractical assumptions (e.g., assume fully-
labeled data, or a single source of data drift, or require significant
computational resources or manual inspection), and have never been tested in a
real end-to-end system.

We present Nazar, the first end-to-end system for continuously monitoring and
addressing data drift in large-scale ML deployments on mobile devices. We
explicitly design Nazar to operate fully automatically without human
involvement so that it can practically support large-scale ML deployments. It
consists of three main functions: (a) automatically _detect_ when data drift
occurs on mobile devices, (b) _analyze_ the root cause of the data drift, and
(c) _adapt_ to the cause that triggered the data drift, all without requiring
any user input. Given that user-labeled data is not available and that
operators have little resources for manual diagnosis, Nazar employs _self-
supervised_ methods for detecting, analyzing, and adapting to data drift,
which we elaborate further below.

Detection. After considering a wide range of detection algorithms, we decided
to adopt a _confidence threshold_ method that detects data drift by comparing
the model’s confidence of the predictions against a threshold. This method
requires no user-labeled data or manually supplied surrogate models, and is
thus suitable for Nazar’s automation requirement while providing good
accuracy. Moreover, it is computationally lightweight and can easily work
locally on any mobile devices.

Root cause analysis. A classical approach [10, 13] for root cause analysis is
called _frequent itemset mining_ , which finds sets of attributes (in our
case, root causes) that are tied with specific data types (detected data
drift). While this approach is useful in uncovering causes of drift, it leads
to many duplicate root causes, which are subsets of or overlap with each
other, and therefore is often used in settings in which a human manually
inspects the results and acts upon them [10]. It is untenable in large-scale
settings that Nazar targets. Hence, we introduce novel _set reduction_ and
_counterfactual analysis_ algorithms, two heuristics that automatically
produce a small set of likely data drift root causes by eliminating root
causes that subsume each other and overlap.

By-cause adaptation. The vast majority of existing adaptation techniques
assume labeled data, and even those that do not, make completely impractical
assumptions. They assume a single source of data drift, and adapt the model on
each newly-arriving input [66, 71], which leads to poor accuracy when there
are multiple sources of drift. Instead, we propose a novel _by-cause_ model
adaptation method, which selectively adapts the model only to the specific
cause of accuracy degradation with the data that is suspected to have it.

The three Nazar components work harmoniously together, continuously
reinforcing each other in an end-to-end loop. As our experiments show, Nazar’s
analysis accurately identifies the root cause of the drift, so that by-cause
adaption is applied only to data drifted for the same cause. Otherwise, a
model adapted to one cause is unlikely to have high accuracy on data that
drifted due to completely different causes. Once an adapted model is deployed,
Nazar’s detection will leverage the new model’s confidence to detect drifts,
continuously improving accuracy. These components together enable Nazar to
effectively obtain a consistently and significantly higher accuracy than
existing approaches that adapt on all inputs, without requiring any manual
work.

We implement Nazar on Amazon AWS, and evaluate it on two streaming datasets:
cityscapes, a self-driving car dataset composed of images taken from driving
vehicles in various European cities [20], and an ImageNet-derived dataset that
emulates a species classification app. Nazar provides an average of 15% and up
to 22% of accuracy boost on all data and an average of 19% and up to 50% on
drifted data compared to the baselines on cityscapes. We will open source our
datasets and code upon publication.

Our main technical contributions are:

  1. 1.

First end-to-end online system for model monitoring and adaptation for mobile
devices.

  2. 2.

Fully-automated root cause analysis mechanism that introduces set reduction
and counterfactual analysis to effectively narrow down the root causes of
model degradation.

  3. 3.

New self-supervised adaptation technique that adapts by root cause, which
provides a significant accuracy boost over existing approaches when deployed
with Nazar’s effective root cause analysis, without any human input.

##  2 Background and Related Work

Companies are increasingly deploying models on user devices for faster
inference and to support low connectivity settings. On-device models support a
wide range of use cases, including object recognition [69], text auto-complete
[55, 18] and ranking posts and ads [69, 67].

##### Where to train the models?

These models can be trained either centrally in the cloud, or in a distributed
fashion across the devices themselves (termed _federated learning_). The
advantages of training the model in the cloud are: (a) the model training and
evaluation process is simpler, and (b) powerful datacenter-based AI compute
capabilities (e.g., a large number of GPUs/TPUs) are available for training.
An advantage of federated learning is that it does not require uploading
training data to the cloud, facilitating better privacy. While federated
learning has seen increased interest both in academia [37, 36, 23, 27] and in
industry [67, 55, 18], in this work, we primarily focus on the more common
scenario, where the models are trained in the cloud. Nazar’s principles and
ideas can also be applied to the federated learning case.

##### Model compression and quantization.

Conducting inference on devices introduces several significant challenges.
Since mobile devices are quite heterogeneous, and may impose significant
resource limitations, models need to be adapted to be run on those devices.
Several systems attempt to address this challenge, including TensorFlow Lite
[8], an extension to TensorFlow that adapts trained models to resource-limited
devices (e.g., using quantization). Another example is Mistify [24], which
automatically adapts the model’s architecture to fit the device’s constraints.

##### Accuracy degradation.

However, techniques like model compression can introduce subtle changes in the
models, which may degrade their accuracy. These discrepancies in accuracy
across devices can impact the applications’ quality of service [19, 53], and
lead to security vulnerabilities [26, 53]. For example, while quantization can
reduce the model size exponentially to fit on resource-constrained devices, it
can also lead to worse accuracy for specific classes [19]. This accuracy
degradation is hard to anticipate in advance.

##### Data drift.

Data drift is a classic problem that affects models that operate on streaming
data, where the distribution of the newly-arriving data diverges from training
data’s distribution [68, 46, 22]. Data drift can occur for many reasons:
temporal environmental changes or corruptions affecting the model input (e.g.,
weather, noise), changes in the input distribution itself (e.g., a self-
driving model trained in the US might not recognize street signs in India),
and sensor-related issues (e.g., problems with device microphone or camera
lense). To deal with this problem, models are often frequently retrained with
fresh data, even if some older data is retained, so their training data better
reflects the types of inputs they will encounter during inference [14, 49].
The data drift problem is exacerbated in on-device deployments, because: (a)
different devices may see divergent data distributions, and (b) when
retraining in large-scale deployments, it is not feasible to retrain on data
from _all devices_. Therefore, one needs to decide when to retrain and which
devices to sample from.

Ekya [14] is a recent system that tackles a variant of this problem, by
jointly scheduling retraining and inference on the same “edge” servers. In the
case of Ekya, an edge server is a server with multiple GPUs sitting at the
network’s edge (e.g., in a content distribution network), unlike our setting
where inference is done on resource-constrained mobile devices. A second key
difference is that, unlike Nazar, Ekya assumes labels are available for
adapting the models.

##### Lack of visibility and monitoring.

There are several efforts to provide more visibility and monitoring in ML
pipelines. ML-EXray [53] is a framework that helps “debug” models by allowing
ML operators to instrument logs and debugging assertions. It targets pre-
processing issues, quantization bugs, and suboptimal kernels. Another data
validation system for ML pipelines implemented at Meta [58] tries to identify
possible attributes that caused model performance drop, from the training
input. In contrast to these systems, Nazar focuses on post-deployment issues
caused by data drift, while these systems focus more on the pre-deployment
validation setting.

In summary, while there are existing systems that identify problems in models
pre-deployment, and existing ad-hoc detection and adaptation techniques, to
the best of our knowledge there is no automated end-to-end system for
monitoring and adapting models on mobile devices.

##  3 Design

###  3.1 Overview

Figure 1: Nazar’s design.

We present an overview of Nazar’s design (Figure 1). We design Nazar to be an
end-to-end system that can automatically monitor data drift, identify the main
root causes for the drift, and adapt models to them at scale, while
dynamically evolving with changing data distributions in the real world.

##### Usage modes.

The user of Nazar is the ML ops team, which maintains and retrains models. ML
ops can choose their level of interaction with Nazar: by default, Nazar runs
in an “autopilot” mode, where monitoring, analysis and adaptation are all done
automatically. The ML ops team can choose to more closely interact with the
system, receiving alerts when data drift occurs, and manually deciding when to
trigger the adaptation and on which root causes to apply them.

##### On-device detection.

App users (i.e., users of the apps that run the AI models) are completely
oblivious to Nazar. Nazar operates in the cloud, and interacts with the on-
device models using an API. The apps contribute two types of information to
Nazar. First, each time the models conduct inference, they also subsequently
run a very lightweight drift detection algorithm (described in §3.2). The
result of this algorithm, along with additional metadata about the device and
model (e.g., the device’s ID, current location, local time, model version) are
sent to Nazar in the cloud. We call this metadata collected from the devices a
_drift log entry_. Second, periodically, in the background, the device will
sample some percentage (by default 1%) of the inputs to the model, and send
them to the cloud for model adaptation purposes.

##### Root cause analysis.

The drift log entries are ingested into a database in the cloud, called the
_drift log_. Periodically, Nazar runs a _root cause analysis_ algorithm
(§3.3). The algorithm is composed of: (a) a series of database queries on the
data drift log to identify potential sets of causes of data drift, and (b)
_set reduction_ and _counterfactual analysis_ algorithms, which reduce
redundant causes and rank them to select the most important ones to adapt to.
When drift is indeed detected, Nazar generates an alert for the ML ops team.

##### By-cause adaptation.

After drift is detected, Nazar generates new _by-cause model adaptations_ that
adapt to the specific root causes of the drift (§3.4). These adaptations are
pushed to the app users’ devices and used for new inferences. Since model
updates can accumulate, Nazar consolidates the different versions to capture
the relevant root causes with a small number of model adaptations. For
inference, the device chooses which model version to use for each input, by
selecting the one with attributes that best match the input.

##### Evolving drift detection.

In the process of detecting, analyzing and adapting to drift, the concept of
what is non-drift and what is drift evolves over time. If Nazar adapts on a
certain source of drift, it should not continue to be detected as drift over
and over again. Therefore, ideally the detector and root cause analysis should
keep “adapting” to the new distribution of data, and only exhibit a high
detection rate if they see data that diverges from the data the original model
was trained on and that Nazar adapted its models to.

##### Design principles.

The main questions in designing Nazar is how to design its detection, root
cause analysis and adaptation mechanisms. Two primary principles guide our
design:

  1. 1.

As Nazar is transparent to app users, it requires _self-supervised_ methods
that cannot rely on labeled data.

  2. 2.

Nazar must support fully-automated operation, without relying on the ML ops
team instruction.

|  Threshold [30] |  KS-test [54] |  OE [31] |  Odin [42] |  MD [39] |  SSL [32] |  CSI [63] |  GOdin [34]
---|---|---|---|---|---|---|---|---
No secondary dataset | ✓ | ✓ | ✗ | ✗ | ✗ | ✓ | ✓ | ✓
No secondary model | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✓
No backpropagation | ✓ | ✓ | ✓ | ✗ | ✓ | ✓ | ✓ | ✗
No batching | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Table 1: Comparison of different data drift detection algorithms from the ML
literature. Nazar uses the threshold method, which simply applies a threshold
on the model’s softmax output, such as the max softmax score.

###  3.2 On-Device Data Drift Detection

We now describe Nazar’s data drift detector, which runs on the mobile devices.
The goal of the data drift detector is to detect when data drift has occurred
on a particular device in a lightweight fashion, without requiring any user
input.

####  3.2.1 Data Drift Detection Techniques

When designing Nazar’s drift detection mechanism, we considered different data
drift (also known as “concept drift” and “out-of-distribution drift”)
algorithms from the ML literature. However, most of these techniques were not
designed for an on-device inference setting. Table 1 summarizes the eight
primary techniques we evaluated. We introduce the classes of techniques, and
describe our rationale for focusing on methods that are derived from the
model’s inference output.

##### Detecting based on model output.

One class of data drift detection techniques assumes that data drift is
correlated with the model being “unsure” about the correct class to output.
Therefore, they apply various metrics on the model’s _logit_ vector (or un-
normalized log probabilities). As a refresher, in deep neural network (DNN)
models, the model outputs an array that assigns a probability for each class.
Typically the highest scoring class is chosen as the predicted class. The
distribution of this vector can indicate how “certain” a model is about its
prediction. For example, the MSP _threshold_ [30] checks if the maximum
softmax value of the logit vector is below a certain threshold. If it is, the
model is uncertain about the final prediction, which is correlated with data
drift. Prior work also proposes other types of thresholds or metrics, such as
the entropy of the softmax values [64] and other similar scores [44]. In our
experiments, we found these thresholds to perform almost identically to MSP.
MSP has the small advantage that it is normalized between 0 and 1, making it a
simpler knob to tune, and hence we adopt it. The advantage of this class of
algorithms is that they can simply be applied to the model’s inference output
with negligible computational overhead (since the logit scores are anyways
computed by the inference), and do not require any outside information.

##### Statistical test on batch of outputs.

Orthogonal to the aforementioned methods that use a simple threshold for data
drift detection, statistical tests can be combined with any of these scores to
determine whether the inference data diverges from the training data
distribution [64]. For example, Kolmogorov-Smirnov (KS) test (KS-test in Table
1) compares the empirical cumulative distribution functions (CDFs) of the two
datasets and calculates their maximum difference. Prior work [54] conducts
empirical studies on using different combinations of statistic test and finds
that applying KS-test on softmax outputs yields the best detection accuracy.
Hence, this is the main statistical test we evaluate.

##### External datasets.

Another class of methods assumes training-time access to a dataset that
contains drifted data samples. The intuition is that such a “drift dataset”
will help train a model to be more sensitive to all drifts. Examples include
Outlier-Exposer [31] (OE in Table 1), Odin [42] and Mahalanobis Distance [39]
(MD). We deem these approaches impractical for our setting, because our data
is unlabeled, and we cannot assume that users will prepare drift datasets
which is a meaningless concept for a user.

##### Secondary model.

Some techniques employ auxiliary models to detect data drift. SSL [32] and CSI
[63] co-train an auxiliary model for self-supervised tasks on a transformed
version of the dataset (e.g., they rotate images in the original dataset and
perform rotation angle classification). The assumption is that if there was no
drift, after training, both models would have high confidence on the same
input. We rule out this class of methods, given that some mobile devices are
resource constrained, and we cannot rely on them to invoke an additional model
purely for data drift detection.

##### Methods that require backpropagation.

Generalized Odin [34] (GOdin) is an expanded version of Odin that does not
require the use of a secondary dataset but requires adding small adversarial
perturbations to make the model more confident when data is in distribution,
and less confident when data has drifted. However, to add these perturbations,
it requires an extra step of _backpropagation_ after the softmax values are
read, i.e., the neural network needs to be traversed in reverse. Unfortunately
backpropagation cannot be used in certain compressed models, which means this
technique would not be usable for many types of adapted models pushed to user
devices.

Figure 2: Comparison of F1 scores using KS-test with different batch sizes.
For batch size is 1, we use threshold on MSP with default value 0.9.

####  3.2.2 Chosen Detection Technique: Threshold on MSP

After ruling out most of the techniques due to their lack of fit with on-
device inference, we finalize a shortlist of two detection methods: the simple
MSP threshold method that operates on one model-outputted logit vector at a
time, and the KS-test statistical method, which operates on a batch of MSP
scores. To evaluate these methods we measure their _F1 score_ to compare their
effectiveness on an equal split of clean and drifted images (described in
§5.3) and a ResNet50 model (see §5.2) is used to generate the logit vectors.
The F1 score is defined as:

$F1=2\cdot\frac{Precision\cdot
Recall}{Precision+Recall}=2\cdot\frac{TP}{2TP+FP+FN}$ (1)

where a high score indicates that the detector has a good balance between
precision and recall. In other words, the model is able to correctly identify
true positives (the image is “drifted”, i.e., it belongs to a different
distribution than the training set, and the detector thinks it is drifted)
while minimizing false positives (the image is not drifted and the detector
thinks it is drifted) and false negatives (the inverse). For the KS-test
method, we test it with different batch sizes and assign the detection result
(i.e., a boolean value for drift or non-drift) _on the whole batch_. For the
threshold method, we set its default value to 0.9 (we evaluate this choice in
§5.3).

Figure 2 displays the results, showing that when the batch size is higher than
4, KS-test slightly outperforms the threshold method, but is worse when the
batch size is lower. However, batching results from device inference raises
various tricky questions: should one batch inference results from a specific
device over time? How long should we allow that time window to be? How do we
batch results when we do not have sufficient samples from a single device to
fit in one batch?

Since the threshold method performs very similarly to KS-test with large
batches, and since using a batched detection method raises these thorny
issues, we choose the threshold method with MSP as the default detection
module in Nazar.

###  3.3 Root Cause Drift Analysis

As we will show later (§5), since the drift detection algorithm operates
without any user input or labeled data, and it is simply a function of the
model’s uncertainty, the detection algorithm is somewhat noisy for each
individual detection. Therefore, we need a more accurate mechanism at a system
level to determine whether drift has actually occurred, and why. This
subsection explores the design of this mechanism, which we call the _root
cause drift analysis_.

Time | Device ID | Weather | Location | Drift
---|---|---|---|---
06:02:01 | android_42 | clear-day | Helsinki | False
06:02:23 | android_21 | clear-day | New York | False
06:04:55 | android_21 | clear-day | New York | True
08:03:32 | android_21 | snow | New York | True
11:05:01 | android_42 | snow | Helsinki | True
Table 2: Example of drift log.

In Nazar, for each inference, the device sends to the cloud the data drift
detection results, as well as metadata about the device and its environment
(e.g., weather and geolocation, as depicted by the example in Table 2). Each
entry is called the _drift log entry_ , and the entries are assembled in a
single large database in the cloud, called the _drift log_. Hence, the drift
log is a live global view of data drift across all devices.

We walk through the algorithm using a toy example of two devices (one in New
York, one in Helsinki) running an application for classifying animals in their
natural settings. This application produces a drift log (Table 2). Each device
generates a few drift entries, which contain metadata on the current location
of the device and the weather it is operating in. This metadata can be either
gleaned by the device itself (e.g., its location) or generated by Nazar in the
cloud via an external source (e.g., for weather metadata, Nazar looks up the
weather in a third-party weather API using the device’s location). In this
example, the root cause of the drift is the snowy weather, which transforms
the image sufficiently so that it diverges from the original training data –
imaged taken in clear days – used to train the model. The example includes a
false positive drift detection, i.e., the third entry in the log, where the
detection threshold algorithm marked the image as “drifted” (due to low
confidence logit scores), even though the image was not.

##### Frequent itemset mining (FIM).

To identify whether drifts exist and discover its root causes in the face of
potential false positives and negatives, Nazar focuses only on clusters of
drifts that are statistically significant. One possible approach is to
directly apply an ML-based clustering algorithm on the entries flagged as
drifts. We did not adopt this approach because clustering algorithms often
require specifying how many clusters to divide the data into (e.g., the $K$
parameter in K-means), and can be expensive, especially at scale [57].

An alternative, classical data mining approach [12, 11] is to explore whether
sets of attributes in the drift log entries, e.g., {snow, New York} in Table
2, frequently appear with the drift attribute. These attributes are termed in
the data mining literature as _frequent itemsets_ and there exist many
algorithms [12, 52, 51, 16, 25, 17] for frequent itemsets mining (FIM).

Rank | Occurrence | Support | Risk Ratio | Confidence | Weather | Location | Location
---|---|---|---|---|---|---|---
0 | 0.4 | 0.67 | 3 | 1 | snow | - | -
1 | 0.2 | 0.3 | 2 | 1 | snow | - | android_21
2 | 0.2 | 0.3 | 2 | 1 | snow | - | android_42
3 | 0.2 | 0.3 | 2 | 1 | snow | New York | -
4 | 0.2 | 0.3 | 2 | 1 | snow | Helsinki | -
5 | 0.4 | 0.7 | 1.3 | 0.67 | - | - | android_21
6 | 0.4 | 0.7 | 1.3 | 0.67 | - | New York | -
7 | 0.4 | 0.7 | 1.3 | 0.67 | - | New York | android_21
8 | 0.2 | 0.33 | 0.75 | 0.5 | - | - | android_21
9 | 0.2 | 0.33 | 0.75 | 0.5 | - | - | android_42
10 | 0.2 | 0.33 | 0.75 | 0.5 | - | Helsinki | -
11 | 0.2 | 0.33 | 0.75 | 0.5 | clear-day | - | android_21
12 | 0.2 | 0.33 | 0.75 | 0.5 | - | Helsinki | android_42
13 | 0.2 | 0.33 | 0.75 | 0.5 | clear-day | New York | -
14 | 0.2 | 0.33 | 0.75 | 0.5 | - | Helsinki | -
15 | 0.2 | 0.33 | 0.33 | 0.33 | clear-day | - | -

Table 3: Example of frequent itemset mining results.

In the first stage of root cause analysis, shown in Figure 3(a), Nazar
implements an FIM mechanism that employs the _apriori algorithm_ [13]. The
apriori algorithm is a common method for FIM, which first identifies frequent
individual attributes in the entry and then uses them to generate larger sets
of attributes associated with the drift attribute. The algorithm calculates
several metrics starting from sets containing each single attribute, and then
the sets containing combinations of attributes which form subsets of the
single ones, e.g., {snow, New York} is a subset of {snow}. It filters the sets
by checking if statistics from the metrics pass certain thresholds to consider
a certain set as a cause of drift, since the drift detection is noisy.
Finally, it ranks which sets of attributes are the leading causes of drift.
The metrics and ranking for the example drift log in Table 2 are shown in
Table 3.

The _occurrence_ of a set of attributes measures how often it appears in the
drift log. The _support_ of a set of attributes measures how often it is
marked as “drift” as a proportion of all log entries that are marked as
drifted. E.g., {snow} has a support of 0.67, because $\frac{2}{3}$ of the
drift entries have the attribute “snow”. The _confidence_ of an attribute set
is how often it is marked as drift as a proportion of all its appearances in
the table. Finally, the _risk ratio_ of a set measures how much likelier
entries that are marked as drifted contain the set of attributes versus not
containing it. E.g., for {snow, Helsinki}, the risk ratio is 2, because the
probability of an entry being drift given it contains {snow, Helsinki} is 1
and the probability of an entry being drift given it does not contain {snow,
Helsinki} is $\frac{1}{2}$.

By default, Nazar uses the risk ratio to rank the results, because it measures
the importance of a specific root cause. Following prior work [10], Nazar sets
the maximum number of attributes that can belong to a single root cause to 3,
and uses values of 0.01, 0.01, 0.51 and 1.1 for minimum occurrence, support,
confidence and risk ratio respectively, by default.

##### Practical limitations of FIM.

While FIM is a useful technique to rank root causes and set some thresholds on
which root causes are important, systems that rely on it typically assume that
a human will then inspect the results and manually choose the appropriate root
causes [10]. In our example in Table 3, the top seven rows are all possible
root causes, since they pass the four thresholds. However, it would not be a
good idea to simply adapt models to each one of these root causes, since they
are overlapping and even contain subsets of each other (e.g., {snow, New York}
is a subset of {snow}). Therefore, Nazar needs a way to narrow down this set
of possible root causes so it can apply model adaptations sparingly, covering
as many relevant root causes as possible without requiring operator
instruction.

Figure 3: Flow of root cause analysis.

##### Set reduction.

There are two types of possibly redundant root causes that may have already
been addressed in other root causes, and thus can be _reduced_. First, a root
cause which is a subset of other root causes that have broader coverage. For
example, {snow, New York} is a subset of both {snow} and {New York}, so if one
of these two is selected as root causes for model adaptations, there is no
reason to select their intersection,e.g., {snow, New York}. Nazar’s set
reduction algorithm merges the subset root cause into one of its super-sets
that has higher ranking, e.g., {snow, New York} is merged into {snow} instead
of {New York}, because {snow} is ranked higher (rank 0). This stage is termed
as _set reduction_ and is depicted in Figure 3(b).

##### Counterfactual analysis.

The second cause of redundancy is overlapping causes, when the entries with
drift are already “covered” by some other root causes. In our example,
$\frac{2}{3}$ entries from New York contain drift signals though $\frac{1}{3}$
are false positives. However, this subset of images is already addressed by a
higher-ranked root cause, e.g., {snow}. Nazar filters out this type of root
cause by applying counterfactual analysis [40], which iteratively modifies the
drift attribute from the log entries associated with a higher-ranked root
cause to be “false”, and tests whether the lower-ranked root cause is still
statistically significant by checking the four metrics after these drift
attributes have been modified. If it is still statistically significant, Nazar
add this lower-ranked root cause into the final result. Note that the first
top-ranked root cause is directly added to the final result. This iterative
process is shown in Figure 3(c) and it runs until all root causes from the set
reduction output are exhausted. Eventually, Nazar groups images associated
with each filtered root cause, e.g., images that have “snow” in their meta-
data. Note that Nazar also filters a set of images that are “clean” when they
are not associated with previously discovered root causes. Algorithm 1
summarizes the root cause analysis mechanism.

##### Limitations.

The primary limitation of our root cause analysis is that the drift log
attributes may not capture all possible root causes of drifts. For example,
certain devices may have camera lenses from a particular manufacturer that are
causing image corruption, but the drift log might not contain an attribute of
the lens manufacturer for each device. In such cases, Nazar may group devices
by their models, their location, or even by device ID, even though the “real”
root cause is the lens. In such cases, Nazar should still automatically
produce by-cause adaptations, which would capture these data drifts, but the
ML operator team would have to manually investigate the issue in order to
understand the real root cause. To combat this issue, in large-scale settings,
the list of attributes should be exhaustive, to capture unforeseen causes of
drift.

Algorithm 1 Root cause analysis algorithms

$FIM():$
Output: Extracts frequent sets of attributes associated with drift.

$Set\\_Reduction(FIM\\_table):$
Input: Sorted list of attribute sets.
Output: Mapping between the most coarse-grained attribute sets and their
subsets. Ties between coarse-grained sets are broken by ranking.

$Passes\\_Drift\\_Threshold(items):$
Input: Attribute set potentially causing drift.
Output: True if the set passes thresholds (occurrence, support, confidence,
and risk). False otherwise.

Drift Analysis:

1:$FIM\\_list\leftarrow FIM()$

2:$coarse\\_associations~{}\leftarrow~{}Set\\_Reduction(FIM\\_list)$

3:$root\\_causes\leftarrow[\ ]$

4:while $coarse\\_associations$ do

5: $curr\\_coarse\\_cause\leftarrow coarse\\_associations.pop()$

6: if $Passes\\_Drift\\_Threshold(curr\\_coarse\\_cause)$ then

7: $root\\_causes.append(curr\\_coarse\\_cause.key)$

8: $Mark\\_No\\_Drift(curr\\_coarse\\_cause.key)$

9: else

10: for each $subset$ in $curr\\_coarse\\_cause.value$ do

11: if $Passes\\_Drift\\_Threshold(subset)$ then

12: $root\\_causes.append(subset)$

13:return $root\\_causes$

###  3.4 By-Cause Adaptation

Most model adaptation techniques [41, 56, 62, 70, 45] and end-to-end ML
systems that incorporate adaptation (e.g., SageMaker [43], TFX [47]) require
labeled data, which are unsuitable for our design.

We focus on two main self-supervised methods for adapting models to data
drift, motivate the idea of adapting a model to a _specific cause of drift_ ,
and introduce how Nazar chooses different adapted model versions for
inference.

##### Self-supervised adaptation.

Nazar’s model adaptation builds on prior work on self-supervised adaptation.
The intuition is to select a self-supervised objective (e.g., minimize the
entropy of the model output) that captures some invariant of the data itself
without requiring any labels. Upon data drift, this objective is no longer
optimal, therefore we can optimize the model weights to minimize this
objective again, effectively adapting the model to the drift.

We consider two methods: TENT [66] and MEMO [71]. TENT adapts any pre-trained
probabilistic model by minimizing the entropy on the logits output by the
model, on a batch of images. MEMO adapts on marginal entropy, which is the
entropy of the averaged output logits, over different augmented copies of a
single image, e.g., by rotating and posterizing the image. The idea is that
the model should be (a) invariant across augmented versions of the image, and
(b) confident in its predictions even for heavily-augmented versions of the
image.

We make three modifications to these methods to make them practical for the
setting of large ML deployments on mobile devices that Nazar targets. First,
both methods tightly couple adaptation and inference: they adapt the models
based on the current inference inputs, and then immediately run inference on
the inputs. However, as discussed in §2, many mobile devices are too wimpy for
on-device adaption, so we decouple adaption and inference in Nazar. Second,
MEMO adapts a whole model including all its layers, significantly increasing
network consumption and model storage costs because each adaptation leads to a
whole new version of the model weights. We thus modify MEMO to adapt only the
_batch normalization (BN) layer_ [35], similar to TENT. As an example, in
ResNet50 the BN layer is $217\times$ smaller than the full model (0.4MB vs.
92MB). Our experiments show that adapting only the BN layer in MEMO has the
same accuracy boost as adapting all layers. Third, we modify MEMO to adapt
based on a small batch of inputs instead of on every input because the latter
would be impractical in our setting, incurring too frequent adaptations even
for one-off or falsely-detected drifts.

##### Benefit of adapting by cause over adapting blindly.

Prior adaption methods unrealistically assume a single cause behind the data
drift and adapt on all inputs, but in practice data drift can originate from
different sources: for example, a traveler may bring her device from location
to location over a short period of time, experiencing very different input
distributions each corresponding to a different cause (location). We show in
our experiments below that adapting by cause improves model performance
significantly over adapting blindly on all inputs. Moreover, to illustrate the
need for accurate root cause analysis, we show that a model adapted to one
cause of data drift has poor performance when applied to data that is drifted
due to a different cause or non-drifted (i.e., clean) data.

Methods | Average Accuracy (%)
---|---
No-adapt | 38.7
By-cause (TENT) | 61.5
By-cause (MEMO) | 42.3
Adapt-all (TENT) | 42.4
Adapt-all (MEMO) | 30.3
Table 4: TENT and MEMO when adapting them by-cause, and using a single model
to adapt to all sources.

We adapt a pre-trained ResNet50 on a dataset that contains 16 different types
of data drifts, such as weather-based corruptions and image blur (§5 describes
the evaluation setup), and a portion of clean data. We run TENT and MEMO in
two settings: (a) adapt and test a model for each cause of drift and clean
data (17 total models), termed _by-cause_ , and (b) adapt one model on a mix
of all 16 sources of drifts and clean data, and test them on the same test set
as in (a), termed _adapt-all_. We also evaluate non-adapted ResNet50 on the
same test set.

The average test accuracy is shown in Table 4. Adapting on data by-cause using
both methods improves accuracy over the original model, by 22.8% for TENT and
3.6% for MEMO; whereas adapting on all the data degrades accuracy with MEMO
and leads to small gains with TENT. The reason is that adapting models to
multiple divergent distributions without supervision can cause models to
underfit and leads to low performance. To further demonstrate this, we run an
experiment where we adapt a model by-cause (foggy weather), and test it on
images with other sources of drift. On average, the model obtains an average
accuracy of only 16.4% when run on images with other sources of drift, and an
accuracy of 66.7% on its own test set. Its accuracy on clean data is also very
low: 26.8%, while the model adapted on clean data has an accuracy of 74.6% on
the same clean test set.

Therefore, we conclude that Nazar has to adapt its models sparingly and apply
them carefully; it should apply adapted models only when there is a true
prevalent source of data drift that affects some portion of user devices, and
ideally run the resulting adapted model on data that experiences the same
source of drift. These observations motivate Nazar to adapt different models
by distinct root cause, so that the distribution of inference data will be as
close as possible to the one of the training data. Ideally, each by-cause
adapted model should run inference on data that belongs to the same
distribution it was adapted on, while a continuously adapted “clean” model
should be run on clean data. Since no ground truth exists, Nazar has to rely
on its root cause analysis to determine which devices are experiencing data
drift and from which source. In addition, this motivates us to use TENT as the
default method to adapt the models in Nazar, since TENT largely outperforms
MEMO in the both strategies in our experiment, as shown in Table 4. However,
ML operators are free to use any self-supervised adaptation method with Nazar.

##### Consolidating model versions.

Adapting by-cause generates multiple model versions. We cannot allow the
number of models to grow unbounded, especially on resource-constrained
devices. Nazar constrains the number of models that can be stored on each user
device, by periodically consolidating them. To consolidate different versions,
Nazar keeps a global view of the model pool, in a least recently updated (LRU)
list, which contains the sets of models to be deployed. The oldest models make
room for the newer ones. Orthogonally to the LRU algorithm, if a new model
version belongs to the exact same set of attributes as an existing one, the
older one is evicted without having to evict the tail of the LRU. In addition,
if an incoming model version has a root cause that is a superset of an older
model version, the older version gets evicted (similar to the set reduction
algorithm in §3.3).

##### Picking which model to use for inference.

During inference on the device, Nazar will use the most-recently updated model
that has the highest number of matching attributes for inference, e.g., {rain,
New York} has more attributes matching than {rain} if the input image is
associated with {rain, New York}. It uses the risk ratio ranking of a root
cause, described in §3.3, to break ties between model versions. If no matching
model is found, it uses its “clean” model for inference. Note that model
selection for inference is run on the device without any involvement from the
cloud.

##  4 Implementation

We now describe our prototype implementation of Nazar on Amazon AWS. To
support a large number of devices and models, our implementation uses highly-
scalable AWS services. Such services exist on all cloud providers, and our
implementation could be easily ported to other clouds.

##### Drift log.

We run the drift log on Amazon Aurora [65], a relational database that
supports over 120,000 writes per second and can be scaled to 128 tebibytes.
The drift log is stored as a table, where each row contains the metadata and
whether the inference was detected as a data drift.

##### Root cause analysis and adaptations.

The root cause analysis is run periodically as an Amazon Lambda function,
which is triggered either automatically based on a configurable time window or
manually by the ML operator. The FIM algorithm is run as a set of SQL queries
on the drift log. The initial phase of the algorithm requires extracting the
attributes frequently associated with drift. This can be implemented using a
simple SQL Count aggregation, with appropriate conditions. The function then
calculates the FIM metrics, which are used to filter and rank the root causes.
The function then runs the set reduction and counterfactual analysis. Finally,
each narrowed-down root cause is sent to a GPU-equipped instance, which
conducts the adaptation by-cause.

##  5 Evaluation

This section answers the following questions:

  * Q1:

How well does Nazar’s detection algorithm detect different types of data
drift? (§5.3)

  * Q2:

How effective is Nazar’s root cause analysis in identifying the root cause of
drift? (§5.4)

  * Q3:

How does by-cause adaptation perform compared to prior approaches? (§5.5)

  * Q4:

Does the detector evolve with model adaptation? (§5.6)

  * Q5:

What is the accuracy gain in end-to-end workloads? (§5.7)

  * Q6:

How quickly does Nazar adapt to data drift and how well does the root cause
analysis scale? (§5.8)

We first describe our datasets (§5.1) and our experimental setup (§5.2), and
then answer the evaluation questions.

###  5.1 Datasets

(a) Wildlife animal example.

(b) Cityscapes example.

Figure 4: Examples of clean image and images with rain, snow and fog
(corruption severity of 3) from the two datasets.

Our evaluation uses two configurable datasets: cityscapes and animal wildlife,
which represent the datasets of two typical applications of Nazar. Both
datasets are emulated over a period between January 1st 2020 and April 21st,
2020, following a Kaggle dataset of historical weather [5], which exhibits
dynamic weather patterns. We apply synthetic weather-based data drifts (rain,
snow and fog) based on the historic weather for different locations using data
from a weather website [9]. By default, we evenly divide the time for both
datasets by 8, and run Nazar after each interval. The drifts are applied as
different types of random corruptions to the images. We parameterize the
severity of different data drifts and the probability of an image experiencing
them under the corresponding weather condition. By default, we set this
probability to 1. For example, if an image from Hamburg is tagged to have been
generated on January 18th, 2020, and the historical weather for that day
indicated there was rain at some point during that day, by default, we apply a
drift function for rain (e.g., see Figure 4) on that image.

##### Cityscapes.

A potential application of Nazar is in driver automation and self-driving car
models, which conduct on-device object classification and image segmentation
[15]. Similar to prior work (Ekya [14]), we prepare an object detection
dataset for a self-driving car application, built on top of the cityscapes
dataset, which contains photos of traffic-related objects collected from
driving cars from 50 cities in Europe [20]. Following Ekya’s methodology, we
pre-process cityscapes for object classification, resulting in 27,604 images,
and use 14% of the dataset for the initial training, 6% for validation and 80%
for streaming new inferences. Since photos in each city are associated with
sequence numbers, we assume users submit them based on their original order.
We assume the dataset at each location starts at January 1st, 2020 and ends at
April 21st, 2020, and that the images are submitted for inference in equal
intervals across these dates.

##### Animals.

In addition to cityscapes, which is a temporally-tagged dataset, we also
generate a parameterized synthetic dataset that would allow us to
methodologically configure our system. For this dataset we are inspired by
iNaturist [6], an application for nature lovers to tag animals in the wild,
which uses object classification to help users identify animal species in
seconds. We emulate a geodistributed deployment of iNaturalist, where
subscribers from different locations are taking photos and attempting to
identify different animal species in the wild. We build this dataset on top of
a subset of the classes from ImageNet [4], which contains 201 classes of
animals excluding pets. Each one of these classes contains on average 793
images for model training, 50 images for validation, and 500 images for
streaming. We did not use the established iNaturist [33] because both the
distribution shift functions and adaptation methods were designed and tested
for ImageNet [29, 66, 71] and we want to conduct a fair comparison between
Nazar and prior adaptation approaches.

We emulate 7 locations from different continents: New York, Tibet, Beijing,
New South Wales, United Kingdom and Quebec, where each location contains a
different distribution of animal species. Each location contains a
configurable number of user devices with a configurable arrival pattern of
inference requests. By default, we set the number of devices to 16 for each
location and the request pattern to be a Poisson distribution with a mean of
two images per day per device.

##### Class skew.

We introduce another source of data drift, _class skew_. We observe that a
model’s accuracy of images from different classes varies (Figure 5(b)), even
though the number of training images for each class is similar. Therefore, if
a certain location exhibits a higher proportion of images from lower-accuracy
classes, the model’s accuracy may suffer. To emulate this effect, we generate
the distribution of classes for each location by randomly assigning
probabilities for each class under the Zipf distribution, where the higher the
Zipf parameter $\alpha$ is, the more skewed the class distribution. By
default, we set $\alpha$ to be 0 (uniform) but also evaluate under a high skew
($\alpha=1$).

(a) F1 score by MSP threshold.

(b) Accuracy across classes.

(c) Rate of detection and accuracy vs skew.

Figure 5: 5(a) shows F1 scores of MSP detector are fairly stable on different
threshold values. 5(b) shows average accuracy on different animal classes is
highly variable. 5(c) shows the accuracy decreases and detection rate
increases when skew is high.

Analysis Methods / Ground Truth Drifts | None | Rain | Snow | Fog | Fog & Snow | Fog & Rain | Snow & Rain | Snow & Rain & Fog
---|---|---|---|---|---|---|---|---
FIM | 1 | 0.919 | 0.773 | 1 | 0.891 | 0.921 | 0.926 | 0.917
FIM with Set Reduction | 1 | 0.919 | 0.773 | 1 | 0.891 | 0.921 | 0.934 | 0.919
FIM with Set Reduction and CF Analysis | 1 | 1 | 0.874 | 1 | 1 | 1 | 1 | 1

Table 5: Evaluation of root cause analysis algorithms with Fowlkes-Mallows
Score (1 is optimal).

###  5.2 Evaluation Setup

##### AWS setup.

Our AWS implementation uses the following configurations. The drift log is run
on Amazon Aurora [65] with a 5.7.mysql_aurora.2.11.1 engine on a
db.r6g.2xlarge instance [2]. The drift analysis is run as an AWS Lambda [3]
serverless function with 256MB of memory. The adaptation is run on a
p3.2xlarge EC2 instance, which is equipped with an NVIDIA Tesla V100 GPU [1].

##### Models.

We use three image classification models in all experiments, ResNet18,
ResNet34 and ResNet50, which are commonly-used model architectures for mobile
devices [7]. Each model is trained from scratch until convergence. The
accuracy of each model on clean (non-drifted) validation dataset with
cityscapes is 83.6%, 83.9% and 83.7%, respectively, while the accuracy of the
base model on the animal dataset is 72.1%, 75.4% and 76.1%.

##### Data drifts.

Prior work on drifts apply 16 types of different data drift on ImageNet [29].
In microbenchmarks in §5.3, §5.5 and §5.6 we show how Nazar handles all 16
types of drifts. Our end-to-end evaluation (§5.7) contains only the three
weather-related drifts (snow, rain, fog), as the distribution of weather is
dynamic and driven by real historical weather records. 29% and 36% of days in
the cityscape and animal datasets, respectively, experience weather-related
drifts. All 16 drifts use a severity level of 3 (out of 5) by default.

##### Baselines.

We compare Nazar with two other settings: adapt-all, which is the baseline
approach (e.g., employed by Ekya, TENT, MEMO), where one model is continuously
adapted on all input during each adaptation window, and no-adapt, which is a
pre-trained model that is never adapted. Note that besides adapt-all, we also
conducted experiments on TENT to adapt on only the images whose drift
attribute is “True” but this method always yields worse performance than
adapt-all and thus we do not present its results here.

###  5.3 Detection (Q1)

To show how well the MSP threshold detects drifts, we measure the F1 scores
calculated with different MSP thresholds on the logit outputs from Resnet50.
We evenly applied 16 types of drifts on half of the streaming images in the
animal dataset, as the positive set, and leave another half non-drifted, as
the negative set. We show the result in Figure 5(a), where the F1 score of MSP
detector steadily increases until it reaches 0.73 and then decreases. The
detector’s sensitivity to threshold changes is small around a threshold of
0.9, which we adopt as a default value.

Further illustrating this point, in Figure 5(c), we vary the class skew, i.e.,
we vary the distribution we sample from different classes, where under high
skews we are much likelier to sample specific animal classes than others. The
result shows that the detector rate significantly increases and the total
accuracy degrades under high class skew.

These results indicate that the MSP threshold is a good indicator of different
sources of drifts.

###  5.4 Root Cause Analysis (Q2)

We evaluate Nazar’s root cause analysis using the Fowlkes-Mallows Score (FMS)
[21], which measures the similarity between two sets of clustering results. In
our case, the two sets are ground truth root causes of drift, and ones that
are identified by our root cause analysis. The FMS score is:

$FMS=\sqrt{\frac{TP}{TP+FP}\cdot\frac{TP}{TP+FN}}$ (2)

where TP (true positive) is the number of pairs of data points that are
clustered together in both sets, FP (false positive) is the number of pairs
that are clustered together in the second set but not in the first, and FN
(false negative) is the inverse of FP. The score ranges from 0 to 1, with
higher values indicating more similarity between the clusters. We use 8 drift
scenarios, depicted in Table 5, whose ground truth root causes of drifts are
different combinations of three weather corruptions on the animal dataset for
14 days starting on January 1st, 2020, on a ResNet50. As an example, if the
ground truth root causes are “fog” and “snow” then we apply only these two
types of drifts on the dates that have foggy and snowy weather for each
location but ignore “rain” drift on the rainy days.

The combination of FIM, set reduction, and counterfactual analysis always
yields the highest score under each scenario. In fact, it obtained the optimal
FMS score under all drift scenarios except “snow”.

###  5.5 Adaptation (Q3)

To evaluate whether by-cause adaptation performs better than the naive
approach, i.e., adapting on all coming images, we evenly split the images in
the animal dataset in 17 partitions, 16 of which are transformed with
different drifts, and one is left as clean, and run them on ResNet50. To
isolate the performance of the adaptation mechanism, we assume perfect
knowledge of the underlying root cause of the data drift, and that we adapt
only to images with that root cause (i.e., we assume Nazar’s detector and root
cause analysis are perfect). We treat the clean data as its own data source,
and run an adaptation model for it as well.

Figure 6 breaks down the average accuracy by drift type. By-cause adaptation
significantly and consistently outperforms the adapt-all. In addition, it
provides a significant improvement compared to the baseline non-adapted model,
while adapt-all sometimes degrades the accuracy of the non-adapted model. The
total average accuracy increase of by-cause adaptation in this experiment is
very significant: it achieves a 61.5% accuracy, compared to only 42.4% for
adapt-all and 38.7% for the non-adapted model.

We conclude that by-cause adaptation shows promise in overcoming the
limitations of traditional supervised adaptation approaches, paving the way
for more scalable and efficient adaptation in real-world applications.

Figure 6: Experiments of by-cause, adapt-all, and no-adapt on 16 different
drifted data and clean data Figure 7: Detection rate before and after
adaptation.

(a) Average accuracy.

(b) Average accuracy of drifted data.

(c) ResNet18 accuracy over time.

(d) Number of model versions over time.

Figure 8: Results of experiments on cityscapes dataset. 8(a) and 8(b) show the
average accuracy on all data and drifted data under three strategies. 8(c)
shows the trace of accumulated accuracy per time window. 8(d) shows the number
of model versions on user devices when set reduction and counterfactual
analysis are removed from Nazar.

(a) Average accuracy (S = 3).

(b) Average accuracy (S = 5).

(c) Average accuracy ($\alpha$ = 1).

(d) Root cause analysis scalability.

Figure 9: Results of experiments on Animals dataset. 9(a) and 9(b) show the
average accuracy with different drift severities under three strategies. 9(c)
shows the average accuracy with class skew of $\alpha$=1. 9(d) shows the
scalability of Nazar’s root analysis function.

###  5.6 Evolving Drift Detection (Q4)

We test how the by-cause adaptation influences the drift detector. Using the
same experimental setup as the previous subsection, Figure 7 displays the
detection rate for each one of the drift types before adaptation and after
adaptation. The after adaptation detection rate is measured for the adapted
model that matches the drift type of the input image. The results show two
interesting insights. First, before adaptation the detector is rather accurate
in catching most of the sources of drift, but has some noise. Second, when it
uses the appropriately adapted model, it is less likely to detect the data as
drift, and exhibits the same detection probability for drifted data and clean
data. Therefore, Nazar is not expected to frequently detect root causes again
once it has adapted to them.

###  5.7 End-to-End Workloads (Q5)

We now evaluate all components of Nazar end-to-end on our streaming workloads.
We first evaluate the general performance on the cityscapes dataset and then
test them on the more synthetic animal dataset under more severe drift
conditions, i.e., higher severity for weather drifts and class skew.

##### Average accuracy.

We measure the average accuracy on all data averaged across the last 7 time
windows on the cityscapes dataset in Figure 8(a). For all model architectures,
Nazar yields the highest average accuracies and the smallest standard
deviations. The improvements in average accuracy compared with adapt-all are
very significant: 10.1–19.4%.

We also measure the average accuracy of only the drifted data averaged across
three types of data drift in Figure 8(b), which shows even more significant
accuracy improvements compared to adapt-all (49.5% on ResNet18 and 37.6% on
ResNet34), which is because smaller models have a weaker ability to generalize
on a mixed source of distributions.

Figure 8(c) shows the cumulative average accuracy over time for all data and
only for drifted images. The cumulative accuracy of Nazar continuously
improves over time with each adaptation, while the one for adapt-all increases
for one adaptation window, as the drift level is mild even in the no-adapt
case, and then decreases in the following 3 adaptation windows, after which
they slightly increase. This demonstrates the utility of adapt by-cause, which
provides much more stable accuracy over time, both for clean and drifted data.

##### Benefit of set reduction and counterfactual analysis.

To find out if the set reduction and counterfactual analysis are effective in
the end-to-end setting, we only run the FIM algorithm for root cause analysis,
and find the average accuracy drops 1.3–9.7%. Meanwhile, the number of stored
BN versions (recall we only adapt the BN layer, so each BN layer represents a
different adapted model) is much higher than Nazar, due to the redundant root
causes. We show an example of the numbers of BN versions, from ResNet18,
stored on user devices during each time window for FIM and Nazar in Figure
8(d), where the number of BN versions with Nazar is steady at 3 from the
second time window. Note in this experiment we do not cap the number of model
versions for Nazar.

##### Adaptation frequency.

We evaluate if the number of adaptation cycles affects adaptation performance.
We ran the end-to-end workloads by splitting them into 4 intervals instead of
8, and found the results stayed very consistent. The average accuracy across
the three models improved by 1.2-3.8%.

##### Drift severity.

We vary the severity of the corruptions on the animal dataset (Figure 9(a) and
9(b)), where a higher severity represents a higher level of drift, and
severity is denoted by “S”. When severity is higher, all three methods degrade
on both accuracy metrics but Nazar still outperforms among them. Nazar’s
improvements compared to adapt-all is larger when the severity is higher
(3.8–10.4% better).

##### Class skew.

We evaluate the effect of class skew on Nazar with ResNet50, by setting the
Zipfian parameter $\alpha=1$. The results are presented in Figure 9(c). Nazar
fails to outperform adapt-all on average accuracy when severity is set to 3 on
the animal dataset, because Nazar has a narrower view of diverse image
features than adapt-all, when the variability of classes in each location is
largely constrained by class skew, and thus tends to overfit the model during
adaptation. When we increase the variety of images during each adaptation by
splitting the workload into 4 intervals instead of 8, Nazar outperforms both
baselines and improves the average accuracy of 0.9% compared with adapt-all.
In addition, when the severity is higher, Nazar yields better average accuracy
even when the number of time windows is 8, also shown in Figure 9(c) which
offsets the impact from class skew.

###  5.8 Runtime and Scalability (Q6)

##### Runtime.

Once a sufficient number of entries contain data drift, Nazar should be able
to generate adaptations in a reasonably timely manner to respond to the drift.
We measure the latency of Nazar from the invocation of the root cause analysis
function, through the model adaptations and up until the adapted models are
written S3, and repeat the experiment four times. The average end-to-end
latency is 49.5 minutes. The average root cause analysis runtime is only 46
seconds, while the rest of the time is consumed by the model adaptation. Note
that this time can be shortened by adding additional or larger adaptation
instances.

##### Scalability.

Nazar’s three components are designed to be highly scalable. The drift log
relies on a scalable database (Aurora), and model adaptation can be easily
parallelized on a large number of instances. Thus, the only component that
could potentially become a scalability bottleneck is the root cause analysis
function, since a single function needs to operate on a relatively large
number of Aurora rows via a series of SQL queries. Figure 9(d) presents the
runtime of the root cause analysis running on a single instance, as a function
of the drift log size. We can see the relationship between the runtime and the
number of rows in the drift log is completely linear. The reason is that the
FIM algorithm is linear [13] and the number of candidate sets of attributes is
greatly reduced for counterfactual analysis after the set reduction.

##  6 Conclusions

Nazar is the first end-to-end monitoring and adaptation system for mobile-
based ML deployments. We conclude that chaining together drift detection run
on the device, with root cause analysis and by-cause adaptation run in the
cloud, provides high accuracy, even without user input. Interesting avenues
for future work are adapting Nazar to distributed federated learning, and
developing techniques for better protecting user privacy.

## References

  * [1] Amazon EC2 P3 instances.  https://aws.amazon.com/ec2/instance-types/p3/.  Accessed: April 27, 2023.
  * [2] Amazon RDS instance types.  https://aws.amazon.com/rds/instance-types/.  Accessed: April 27, 2023.
  * [3] AWS Lambda.  https://aws.amazon.com/lambda/.  Accessed: April 27, 2023.
  * [4] ImageNet Object Localization Challenge.  https://www.kaggle.com/c/imagenet-object-localization-challenge, 2017.
  * [5] Historical daily weather data 2020.  https://www.kaggle.com/datasets/vishalvjoseph/weather-dataset-for-covid19-predictions, 2020\.  Accessed: Apr 12, 2021.
  * [6] iNaturalist.  https://www.inaturalist.org/, 2023.
  * [7] Pytorch android examples.  https://github.com/pytorch/android-demo-app, 2023.  Accessed: May 3, 2023.
  * [8] TensorFlow Lite.  https://www.tensorflow.org/lite, 2023.
  * [9] Weather underground.  https://www.wunderground.com/, 2023.  Accessed: Mar 8, 2023.
  * [10] Abuzaid, F., Kraft, P., Suri, S., Gan, E., Xu, E., Shenoy, A., Ananthanarayan, A., Sheu, J., Meijer, E., Wu, X., Naughton, J., Bailis, P., and Zaharia, M. DIFF: A relational interface for large-scale data explanation.  Proc. VLDB Endow. 12, 4 (dec 2018), 419–432.
  * [11] Agrawal, R., Imieliński, T., and Swami, A. Mining association rules between sets of items in large databases.  In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (New York, NY, USA, 1993), SIGMOD ’93, Association for Computing Machinery, p. 207–216.
  * [12] Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A. I., et al. Fast discovery of association rules.  Advances in knowledge discovery and data mining 12, 1 (1996), 307–328.
  * [13] Agrawal, R., Srikant, R., et al. Fast algorithms for mining association rules.  In Proc. 20th int. conf. very large data bases, VLDB (1994), vol. 1215, Santiago, Chile, pp. 487–499.
  * [14] Bhardwaj, R., Xia, Z., Ananthanarayanan, G., Jiang, J., Karianakis, N., Shu, Y., Hsieh, K., Bahl, V., and Stoica, I. Ekya: Continuous learning of video analytics models on edge compute servers.  CoRR abs/2012.10557 (2020).
  * [15] Bojarski, M., Testa, D. D., Dworakowski, D., Firner, B., Flepp, B., Goyal, P., Jackel, L. D., Monfort, M., Muller, U., Zhang, J., Zhang, X., Zhao, J., and Zieba, K. End to end learning for self-driving cars.  CoRR abs/1604.07316 (2016).
  * [16] Borgelt, C. Efficient implementations of apriori and eclat.  In FIMI’03: Proceedings of the IEEE ICDM workshop on frequent itemset mining implementations (2003), Citeseer, p. 90.
  * [17] Borgelt, C. An implementation of the fp-growth algorithm.  In Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations (2005), pp. 1–5.
  * [18] Chen, M., Mathews, R., Ouyang, T., and Beaufays, F. Federated learning of out-of-vocabulary words.  arXiv preprint arXiv:1903.10635 (2019).
  * [19] Cidon, E., Pergament, E., Asgar, Z., Cidon, A., and Katti, S. Characterizing and taming model instability across edge devices.  Proceedings of Machine Learning and Systems 3 (2021).
  * [20] Cordts, M., Omran, M., Ramos, S., Rehfeld, T., Enzweiler, M., Benenson, R., Franke, U., Roth, S., and Schiele, B. The cityscapes dataset for semantic urban scene understanding.  CoRR abs/1604.01685 (2016).
  * [21] Fowlkes, E. B., and Mallows, C. L. A method for comparing two hierarchical clusterings.  Journal of the American statistical association 78, 383 (1983), 553–569.
  * [22] French, R. M. Catastrophic forgetting in connectionist networks.  Trends in cognitive sciences 3, 4 (1999), 128–135.
  * [23] Ghosh, A., Chung, J., Yin, D., and Ramchandran, K. An efficient framework for clustered federated learning.  Advances in Neural Information Processing Systems 33 (2020), 19586–19597.
  * [24] Guo, P., Hu, B., and Hu, W. Mistify: Automating DNN model porting for on-device inference at the edge.  In NSDI (2021), pp. 705–719.
  * [25] Han, J., Pei, J., and Yin, Y. Mining frequent patterns without candidate generation.  ACM sigmod record 29, 2 (2000), 1–12.
  * [26] Hao, W., Awatramani, A., Hu, J., Mao, C., Chen, P.-C., Cidon, E., Cidon, A., and Yang, J. A tale of two models: Constructing evasive attacks on edge models.  Proceedings of Machine Learning and Systems 4 (2022), 414–429.
  * [27] He, C., Li, S., So, J., Zeng, X., Zhang, M., Wang, H., Wang, X., Vepakomma, P., Singh, A., Qiu, H., et al. FedML: A research library and benchmark for federated machine learning.  arXiv preprint arXiv:2007.13518 (2020).
  * [28] Hein, M., Andriushchenko, M., and Bitterwolf, J. Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem.  CoRR abs/1812.05720 (2018).
  * [29] Hendrycks, D., and Dietterich, T. G. Benchmarking neural network robustness to common corruptions and perturbations.  CoRR abs/1903.12261 (2019).
  * [30] Hendrycks, D., and Gimpel, K. A baseline for detecting misclassified and out-of-distribution examples in neural networks.  CoRR abs/1610.02136 (2016).
  * [31] Hendrycks, D., Mazeika, M., and Dietterich, T. G. Deep anomaly detection with outlier exposure.  CoRR abs/1812.04606 (2018).
  * [32] Hendrycks, D., Mazeika, M., Kadavath, S., and Song, D. Using self-supervised learning can improve model robustness and uncertainty.  CoRR abs/1906.12340 (2019).
  * [33] Horn, G. V., Aodha, O. M., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., and Belongie, S. The inaturalist species classification and detection dataset.  In CVPR (2018).
  * [34] Hsu, Y., Shen, Y., Jin, H., and Kira, Z. Generalized ODIN: detecting out-of-distribution image without learning from out-of-distribution data.  CoRR abs/2002.11297 (2020).
  * [35] Ioffe, S., and Szegedy, C. Batch normalization: Accelerating deep network training by reducing internal covariate shift.  CoRR abs/1502.03167 (2015).
  * [36] Lai, F., Dai, Y., Singapuram, S., Liu, J., Zhu, X., Madhyastha, H., and Chowdhury, M. Fedscale: Benchmarking model and system performance of federated learning at scale.  In International Conference on Machine Learning (2022), PMLR, pp. 11814–11827.
  * [37] Lai, F., Zhu, X., Madhyastha, H. V., and Chowdhury, M. Oort: Efficient federated learning via guided participant selection.  In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21) (July 2021), USENIX Association, pp. 19–35.
  * [38] Lee, K., Lee, H., Lee, K., and Shin, J. Training confidence-calibrated classifiers for detecting out-of-distribution samples.  arXiv preprint arXiv:1711.09325 (2017).
  * [39] Lee, K., Lee, K., Lee, H., and Shin, J. A simple unified framework for detecting out-of-distribution samples and adversarial attacks.  In NeurIPS (2018).
  * [40] Lewis, D. Counterfactuals.  John Wiley & Sons, 2013.
  * [41] Li, Z., and Hoiem, D. Learning without forgetting.  IEEE transactions on pattern analysis and machine intelligence 40, 12 (2017), 2935–2947.
  * [42] Liang, S., Li, Y., and Srikant, R. Principled detection of out-of-distribution examples in neural networks.  CoRR abs/1706.02690 (2017).
  * [43] Liberty, E., Karnin, Z., Xiang, B., Rouesnel, L., Coskun, B., Nallapati, R., Delgado, J., Sadoughi, A., Astashonok, Y., Das, P., et al. Elastic machine learning algorithms in amazon sagemaker.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (2020), pp. 731–737.
  * [44] Liu, W., Wang, X., Owens, J. D., and Li, Y. Energy-based out-of-distribution detection.  CoRR abs/2010.03759 (2020).
  * [45] Maltoni, D., and Lomonaco, V. Continuous learning in single-incremental-task scenarios.  Neural Networks 116 (2019), 56–73.
  * [46] McCloskey, M., and Cohen, N. J. Catastrophic interference in connectionist networks: The sequential learning problem.  In Psychology of learning and motivation, vol. 24. Elsevier, 1989, pp. 109–165.
  * [47] Modi, A. N., Koo, C. Y., Foo, C. Y., Mewald, C., Baylor, D. M., Breck, E., Cheng, H.-T., Wilkiewicz, J., Koc, L., Lew, L., Zinkevich, M. A., Wicke, M., Ispir, M., Polyzotis, N., Fiedel, N., Haykal, S. E., Whang, S., Roy, S., Ramesh, S., Jain, V., Zhang, X., and Haque, Z. Tfx: A tensorflow-based production-scale machine learning platform.  In KDD 2017 (2017).
  * [48] Nguyen, A. M., Yosinski, J., and Clune, J. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.  CoRR abs/1412.1897 (2014).
  * [49] Parisi, G. I., Kemker, R., Part, J. L., Kanan, C., and Wermter, S. Continual lifelong learning with neural networks: A review.  Neural networks 113 (2019), 54–71.
  * [50] Paulik, M., Seigel, M., Mason, H., Telaar, D., Kluivers, J., van Dalen, R., Lau, C. W., Carlson, L., Granqvist, F., Vandevelde, C., et al. Federated evaluation and tuning for on-device personalization: System design & applications.  arXiv preprint arXiv:2102.08503 (2021).
  * [51] Pei, J., Han, J., Mao, R., et al. Closet: An efficient algorithm for mining frequent closed itemsets.  In ACM SIGMOD workshop on research issues in data mining and knowledge discovery (2000), vol. 4, pp. 21–30.
  * [52] Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C. Prefixspan,: mining sequential patterns efficiently by prefix-projected pattern growth.  In Proceedings 17th International Conference on Data Engineering (2001), pp. 215–224.
  * [53] Qiu, H., Vavelidou, I., Li, J., Pergament, E., Warden, P., Chinchali, S., Asgar, Z., and Katti, S. ML-EXray: Visibility into ML deployment on the edge.  Proceedings of Machine Learning and Systems 4 (2022), 337–351.
  * [54] Rabanser, S., Günnemann, S., and Lipton, Z. Failing loudly: An empirical study of methods for detecting dataset shift.  Advances in Neural Information Processing Systems 32 (2019).
  * [55] Ramaswamy, S., Mathews, R., Rao, K., and Beaufays, F. Federated learning for emoji prediction in a mobile keyboard.  arXiv preprint arXiv:1906.04329 (2019).
  * [56] Rebuffi, S.-A., Kolesnikov, A., Sperl, G., and Lampert, C. H. icarl: Incremental classifier and representation learning.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (2017), pp. 2001–2010.
  * [57] Sculley, D. Web-scale K-means clustering.  In Proceedings of the 19th international conference on World wide web (2010), pp. 1177–1178.
  * [58] Shankar, S., Fawaz, L., Gyllstrom, K., and Parameswaran, A. G. Moving fast with broken data.  arXiv preprint arXiv:2303.06094 (2023).
  * [59] Shankar, S., Garcia, R., Hellerstein, J. M., and Parameswaran, A. G. Operationalizing machine learning: An interview study, 2022.
  * [60] Shankar, S., Herman, B., and Parameswaran, A. G. Rethinking streaming machine learning evaluation.  arXiv preprint arXiv:2205.11473 (2022).
  * [61] Shankar, S., and Parameswaran, A. G. Towards observability for machine learning pipelines.  CoRR abs/2108.13557 (2021).
  * [62] Shmelkov, K., Schmid, C., and Alahari, K. Incremental learning of object detectors without catastrophic forgetting.  In Proceedings of the IEEE international conference on computer vision (2017), pp. 3400–3409.
  * [63] Tack, J., Mo, S., Jeong, J., and Shin, J. CSI: novelty detection via contrastive learning on distributionally shifted instances.  CoRR abs/2007.08176 (2020).
  * [64] Van Looveren, A., Klaise, J., Vacanti, G., Cobb, O., Scillitoe, A., and Samoilescu, R. Alibi detect: Algorithms for outlier, adversarial and drift detection, 2019.
  * [65] Verbitski, A., Gupta, A., Saha, D., Brahmadesam, M., Gupta, K., Mittal, R., Krishnamurthy, S., Maurice, S., Kharatishvili, T., and Bao, X. Amazon Aurora: Design considerations for high throughput cloud-native relational databases.  In Proceedings of the 2017 ACM International Conference on Management of Data (2017), pp. 1041–1052.
  * [66] Wang, D., Shelhamer, E., Liu, S., Olshausen, B. A., and Darrell, T. Fully test-time adaptation by entropy minimization.  CoRR abs/2006.10726 (2020).
  * [67] Wang, E., Kannan, A., Liang, Y., Chen, B., and Chowdhury, M. FLINT: A platform for federated learning integration.  arXiv preprint arXiv:2302.12862 (2023).
  * [68] Widmer, G., and Kubat, M. Learning in the presence of concept drift and hidden contexts.  Machine learning 23 (1996), 69–101.
  * [69] Wu, C.-J., Brooks, D., Chen, K., Chen, D., Choudhury, S., Dukhan, M., Hazelwood, K., Isaac, E., Jia, Y., Jia, B., et al. Machine learning at Facebook: Understanding inference at the edge.  In 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA) (2019), IEEE, pp. 331–344.
  * [70] Yin, X., Yu, X., Sohn, K., Liu, X., and Chandraker, M. Feature transfer learning for deep face recognition with under-represented data.  arXiv preprint arXiv:1803.09014 (2018).
  * [71] Zhang, M., Levine, S., and Finn, C. MEMO: test time robustness via adaptation and augmentation.  CoRR abs/2110.09506 (2021).