{'fraction_non_alphanumeric': 0.034939847597579204, 'fraction_numerical': 0.008722710900938426, 'mean_word_length': 4.5794941900205055, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Active Learning for Deep Neural Networks on Edge Devices

When dealing with deep neural network (DNN) applications on edge devices, continuously updating the model is important. Although updating a model with real incoming data is ideal, using all of them is not always feasible due to limits, such as labeling and communication costs. Thus, it is necessary to filter and select the data to use for training (i.e., active learning) on the device. In this paper, we formalize a practical active learning problem for DNNs on edge devices and propose a general task-agnostic framework to tackle this problem, which reduces it to a stream submodular maximization. This framework is light enough to be run with low computational resources, yet provides solutions whose quality is theoretically guaranteed thanks to the submodular property. Through this framework, we can configure data selection criteria flexibly, including using methods proposed in previous active learning studies. We evaluate our approach on both classification and object detection tasks in a practical setting to simulate a real-life scenario. The results of our study show that the proposed framework outperforms all other methods in both tasks, while running at a practical speed on real devices.


Introduction
With advances in both hardware and software domains, running inference of deep neural networks (DNNs) on edge devices is now practical, even for relatively cheap devices [34,15,42]. Although these devices have lower computation resources and storage than servers, inference on these devices has many advantages over inference on servers; as it does not require sending input data (e.g., image) over the network, the latency becomes low, communication cost is decreased, and privacy is protected.
As DNNs are considerably large and require large computation for training [41], a model for the edge is usually trained on a server and subsequently deployed to the device. In this setting, it is unlikely that the model constructed in the beginning is "perfect" for two reasons. One is a problem of data. While deep learning is often very greedy for data [39], the gathering and labeling of data are time-consuming and expensive tasks. Moreover, the required amount and quality of data for acquiring the desired accuracy is unknown. Thus preparing data in sufficient amounts before training is challenging. Another reason is the problem known as domain shift. When the model is deployed after training on a server, depending on its deployment site, the distribution of input data may differ from that of training data due to several factors, such as temporal or environmental ones; Ultimately, constructing a model robust for these variations is ideal. For edge devices, however, this is unrealistic since such an adaptive model would require considerable memory or computational resources.
For these reasons, updating the model continuously rather than doing a one-shot training is preferable. In this scenario, the model also benefits from having real input data to train with (i.e., the training data distribution is the same as the target test data). Meanwhile, it is generally unrealistic to send all incoming data to a server. The amount of data will be rapidly too huge, especially when the processing is performed at a high frequency. In this scenario, the cost induced by the communication to the remote server is prohibitive, especially if the connection fee is on a pay-as-you-go basis. Furthermore, almost all data will contain a considerable number of similar samples, considering chronologically consequent data. For these reasons, we need to perform data selection on the device.
Selecting data and training with it is known as active learning, which is a well studied field [36]. Thus, in this paper we consider the problem we face as active learning on edge devices. Unfortunately, however, many approaches proposed in the literature are unable to trivially extend to the scenario we consider. Indeed, as most of them are pool-based approaches, they assume that the selector can access all candidate data at selection time. That is, to solve our problem via these methods, we need to store all the data or send it to the server. This is not possible for the above-mentioned practical reasons, so we have to consider the stream setting, where data arrive continuously, and only a part of them can be stored. In addition, as prior work mentioned [35,3], we should also consider batch-setting in the deep learning context. In this setting, multiple data samples are selected in one round, in contrast to the traditional method of selecting one per round. Along with this, we need to consider diversity inside a batch; if not, even though each sample is very informative, there is a risk the informativeness of a batch becomes small due to overlapping information content.
Our contributions In this paper, we first discuss the properties that reflect the real-world constraints and formalize the novel problem, active learning on edge devices. Moreover, we propose a taskagnostic framework for solving this problem. In this framework, we reduce the problem to a submodular maximization. As a result, we can solve the problem with theoretical guarantees on solution optimality by this framework. In the empirical evaluations, we show actual constructions for different tasks and demonstrate that our approach outperforms all other methods. In addition, we also show that our framework can be used practically through evaluations on a real device.
Potential negative impacts While this work has many positive environmental impacts such as promoting the use of low-energy consumption machine or reducing the communication traffic, one could use the proposed method to improve the performance of surveillance cameras or microphones that can harm the privacy of individuals. However, this work does not propose a new model in itself but a learning method, so such privacy violation threats mainly rely on existing models.

Related work
Active learning Active learning aims to train a model with few labeled samples by selecting data to label from a (large) pool of unlabeled data [36]. This field has been studied for a long time, and since larger amounts of data became available, its importance further increased. In a standard active learning setup, data is selected from a set of candidates and then fed to an oracle (e.g., a human annotator) that returns annotation. The model is trained with it, and this process is typically iterated multiple times (we call each iteration a round). It is assumed that labeling is costly; this is the primary motivation for reducing the amount of data to label.
While it is common to choose data from candidates, two settings exist depending on the accessibility of candidate data: pool-based and stream-based setting [36]. The former allows access to all candidate data, and it is the most popular setting. In the latter setting, we can only look at each sample once in a determined order and keep only a (small) subset of the data. At selection time, we can only access this subset. Therefore, in the pool-based setting, we can consider the relationship between arbitrary data in the ground set, while it is limited in stream-setting. Moreover, we distinguish two policies by the amount of data sent to an oracle at a time; one-by-one and batch-mode. For the one-by-one strategy, we only need to consider how to evaluate each sample solely, such as uncertainty [16,9], expected model output change [8,37] or expected error reduction [33]. While Amin et al. [2] showed that these methods can be simply extended to batch-mode, they still evaluate each sample independently (see Section 3 to further discussion about batch-mode). However, it is known that these kinds of approaches are ineffective for DNNs [35]. A batch-mode method, which has to take both informativeness and diversity into account, is thus required.
Various approaches are proposed to select a diversified batch of data. Sener and Savarese [35] formalizes the active learning problem as a core-set selection in the image space. Ash et al. [3] proposes to create diversity through probabilistic sampling with probability based on the distance between samples. Kirsch et al. [21] considers the mutual information between a batch and model parameters, although their target is Bayesian Neural Networks. Since submodular functions, which are described later, naturally model the diversity, some works reduce active learning to submodular optimization [14,44,18]. However, these methods are pool-based and cannot easily be applied to the stream setting. As described above, the stream setting compels us to consider relationship information, making the batch-mode active learning in this setting challenging.

Submodular maximization
If a set function f : 2 V → R has the following diminishing returns property, it is called submodular function: Since this property is similar to concavity, various problems can reduce to finding the set maximizing f , i.e., a submodular maximization problem [22]. There are many variations of this problem, depending on the constraints or the nature of f . One of the most popular settings is when f is a non-negative monotone submodular function, and the size of the set is bounded. Here, submodular function f is monotone if for all S ⊆ T we have f (S) ≤ f (T ). Although this problem is NP-hard, it is proven that simple greedy algorithm guarantees (1 − 1/e) approximation ratio, i.e., the worst-case solution is greater than (1 − 1/e) times the optimal solution [30]. This is a promising approach when we can access all samples; however, recent applications, including data mining and machine learning, require treating large amounts of data and/or sequentially obtained data. To solve the submodular maximization problem in this stream setting, several algorithms have been proposed. Badanidiyuru et al. [4] proposes SIEVE-STREAMING, which is the first one-pass streaming algorithm. This algorithm has a (1/2 − ) approximation ratio with O(K log(K)/ ) memory. After this work, the improved algorithms SIEVE-STREAMING++ [19] and ThreeSieves [5] were proposed. The former improves memory usage to O(K/ ) while keeping the same approximation ratio, and the latter decreases it to O(K) but makes the lower bound guarantee probabilistic. We provide an overview of the algorithms in Appendix A. Since SIEVE-STREAMING++ is an extension of SIEVE-STREAMING, we compare SIEVE-STREAMING++ and ThreeSieves in our experiments (Section 5).

Active learning for DNNs on edge devices
We first describe the context considered herein and discuss the settings we have to take into account with active learning for DNNs on edge devices; subsequently, we formally define the problem.

Setting
In this paper, we consider a situation where a DNN model is running on a device and continuously performing inference on input data (e.g., from a camera, a microphone, among others), i.e., the prediction of the current sample is completed before the next one is accessed. The model is trained on a server and deployed to the device. We aim to select a batch of data useful for training from the incoming data flow. When simultaneously running the prediction and selection, we assume the inference and the screening of one sample must be completed before processing the next sample. Consequently, we can regard the problem as stream-based batch-mode active learning. There are mainly two types of batch-mode method regarding the terminating condition: 1) greedily select and send to oracle as soon as the batch reaches a given size [2] or 2) send the batch of data to the oracle after seeing a given number of samples. While the former has the potential to reduce unnecessary selection, the amount of data selected per hour is unpredictable at a given sample frequency and it would not be preferable in many practical applications. Thus, we consider the latter setting. Under these assumptions, we need to consider the nature of data, which is different from the usual active learning setting. Moreover, we consider two scenarios that reflect problems faced in practical applications. These are closely related to the evaluation of the method in this problem.
Peculiarity of data In most active learning studies, the data considered for labeling is in some sense filtered, i.e., it is (implicitly) assumed that every candidate is an useful data sample for training. However, when we consider data selection on a device, it is natural to assume that the data will be in various conditions such as unclear, blurred, redundant, among others. We generally classify those into the three following statuses: "imbalanced", "duplicated", and "unuseful". The first one indicates class imbalance, i.e., some classes of data rarely appear, while instances of other classes often appear. The second condition is when almost identical samples exist in candidates. If the model runs at a high speed, the frequency of data capture is also high. Then, a data sample would be often similar to its surrounding samples. The last status describes the presence of data such as "non-object" or "background" samples. For example, in a face detection task, images without a face in it are not useful for increasing accuracy. We have to consider those peculiarities in the evaluation.
Scenarios With regard to active learning on edge devices, we consider two main scenarios: coldstart and domain adaptation. Although both scenarios predict and gather data in parallel, the former scenario considers training the model with a small initial dataset. This makes deployment earlier; consequently, the total operating time increases. The latter is a scenario where the model is initially trained with a dataset, which is usually not small, but its distribution is different from the target environment and is later updated with the collected data. This is intended to treat the domain shift, as mentioned above. There is a similar problem setting called unsupervised domain adaptation [10,29], but this is different in that no label of target domain data is available. In both scenarios, the goal is to adapt the model to its deployment environment.

Problem definition
Let X be the instance space, V ⊆ X whole incoming data set (i.e., ground set). Let V n , n ∈ {1, . . . , N }, V n ⊆ V be a partition of V by round n. We aim to select at each round n a subset S n ⊆ V n , |S n | ≤ K, of data to train a model, where K is a given constant. Since we consider the stream setting, we cannot access all x ∈ V n at the same time. Explicitly, at step t ∈ {1, . . . , |V n |} in round n, we have to decide whether store or discard a sample x t ∈ V n as soon as it arrives. At this time, we can evaluate only stored samples and x t . Moreover, we make no assumption on the independence between samples, i.e., samples are not independent and identically distributed (iid). In a typical stream (e.g., a video stream), there is indeed a temporal correlation between following samples, and therefore samples are not independent.
As an active learning problem, we assume we have an initial dataset D 0 at the beginning. For each round, after selecting S n , we label all samples in S n , add them to the dataset (i.e., D n = D n−1 ∪ S n ), and retrain the model with D n . Let a model parameter be θ and its loss function be l. Depending on the distribution where the samples in V and D 0 are drawn from, we define the following two scenarios. Note that in both scenarios, there is no constraint on the nature of the loss function l, i.e., we can consider any supervised tasks. Definition 1 (Cold-start Scenario). Given D 0 , whose samples are drawn from the same distribution as V . Let this distribution be P and |D 0 | |V |. In this scenario, the goal is minimizing E z∼P l(z; θ). Definition 2 (Domain Adaptation Scenario). Given D 0 , whose samples are drawn from a different distribution than V . Let these distributions be S and T respectively. In this scenario, the goal is minimizing E z∼T l(z; θ).

Active learning framework
Let f be a set function f : 2 V → R. We define f (S) representing a valueness of S. The goal is to select subset S ⊆ V, |S| ≤ K which maximize f . Here, we divide the valueness of S into the informativeness and diversity: the informativeness represents the total contribution of usefulness for each sample of the batch taken solely, each contribution being independent by construction. In contrast, the diversity measures the value of the batch as a whole considering relations between samples, e.g., representing how a batch contains little overlapping. Any valueness of a sample due to the presence of another sample in the batch, i.e. relationship between samples, is considered in the diversity criterion.
To consider these criteria simultaneously, we define the objective function f as the linear combination of these: are respectively the function for informativeness and diversity, and λ ∈ R + is a hyperparameter for balancing. To obtain solutions with worst-case guarantees, we aim to maximize f (S) in a submodular optimization manner. Then, this formalization is convenient: if both f i and f d are monotone submodular, f is also monotone submodular. Thus the policy is to construct each function as a monotone submodular function. In the following, we describe how we design each function.
Informativeness Quantifying how informative a sample is is a task-dependent problem. For example, softmax entropy [36] may be a good candidate for classification tasks, but is insufficient for object detection tasks [11,28] since it does not reflect the results of predicted bounding boxes. However, independence of each sample's informativeness is not related to the task. Consequently, the informativeness of a set can be described as the sum of samples' informativeness in the set. Thus we define f i by using a function g : X → R + and denote as This is a form of linear modular function, and as ∀x, g(x) ≥ 0 it is a monotone submodular function, thus fulfills the condition. The benefit of this formalization is that we can utilize various functions proposed in the previous active learning studies [36,17] as g, since many focus on the same problem, i.e., how to quantify the sample informativeness. This means there is room to choose the best function for the target task. We show concrete examples of constructed function in Section 5.
Diversity In contrast to the informativeness, we have to consider the relationships of samples in a batch, i.e., it cannot be represented as the sum of scores by sample. Usually, this relation is defined through similarity, i.e., high diversity means low similarity between samples. While there are many ways to represent the similarity in a set, designing it under the submodular constraint is not trivial. Therefore, constructing the diversity function of a set is summed up in two points: how we evaluate (dis)similarity between two samples and how we translate it into diversity.
Expressing diversity is studied in various contexts [25,24]. In those backgrounds, they consider the Note that M is always a |V | × |V | symmetric matrix, and all the diagonal values are equal to its largest value by construction. Considering the problem with combinatorial optimization perspective, where I is the identity matrix and α ∈ R + is a scaling parameter. Here, what we are interested in is what kind of functions we can use for k. Since similarity metrics have task-and context-dependent aspects (e.g., pictures of a bird and an airplane may be similar in image space but are not in terms of meaning), we want to allow various functions. Fortunately, we can use any positive semidefinite kernel [13] as a similarity function. It is known that if X ∈ R n×n is symmetric and its smallest eigenvalue is larger than 1, the function f (S) = log det(X S ) is monotone submodular [38]. Then, we can prove the following: Theorem 1. A sufficient condition for k to make f d in Eq. (3) monotone submodular is that k is a positive semidefinite kernel.
Its proof can be found in Appendix C. Constructing a positive semidefinite kernel is well studied, and we can do it very flexibly. For example, with any distance function d : where β ∈ R + is a scaling constant can be a positive semidefinite kernel [12]. We show concrete examples and their interpretation in Appendix C.

Computational cost reduction
Depending on the computational resource of the device we want to run our framework on, reducing the computation is necessary, even though the performance is sacrificed. We describe the possibilities for cost reduction below.
Determinant calculation One of the heaviest computation in our framework is the determinant evaluation in Eq. (3), which is usually O(n 3 ). However, if we focus on the fact that M is incrementally constructed, that is, M n+1 for the set S ∪ {x n+1 } always includes M n for the set S as the leading principal submatrix, we can make this calculation O(n 2 ) by elementary linear algebra (see the appendix for details). Also, there exists a O(n) approximation algorithm for log determinants [7]. When we can tolerate approximation errors, this can be a reasonable choice.
Dividing K As described above, one of the heaviest computation is the determinant calculation, and it depends on the maximum batch size K. Thus, one possible approach to decrease computation is to decompose K into {K 1 , K 2 , · · · K n } where i K i = K. To simplify the problem, let K 1 = K 2 = · · · = K n = K/n. Then, the computation cost for each K i is O((K/n) 3 ), and the total computation   becomes O(K 3 /n 2 ), compared to the initial O(K 3 ). To take advantage of this relaxation, we should make an assumption such as "no similar data appear in different divided substreams". Note that this is different from initially defining small K. If K is divided, the model is trained after multiple batch selection (i.e., after selection of n batches of size K/n), while it is done after a single batch selection of K samples in the default setting.
Memoization When we can use extra memory, memoization is a promising approach to decrease computation. The most effective element to use memoization on is the value of k(·, ·). Although this is a standard technique, it is especially efficient when we use SIEVE-STREAMING++ because it often calculates the same k(·, ·) on different sieves.

Experiments
In this section, we evaluate our framework's effectiveness and show the construction of concrete objective functions for specific tasks. To show how broadly our approach can be applied, we perform experiments with various datasets, tasks, and settings. At first, we evaluate an image classification task using some toy datasets. After that, we evaluate a more complex task, object detection, with a large practical dataset. We also evaluate our framework on a real device (Raspberry Pi 4B).

Image classification
For image classification task, we perform evaluations on both cold-start and domain adaptation scenarios, described in Section 3. The used datasets are described in respective sections.
Common settings As a classifier, we use a two-layer convolutional neural network. In the beginning, it is randomly initialized and trained with an initial dataset D 0 . Then, for each round, we are given 2048 images sequentially (i.e., as a stream) and select up to 128 from it. These images are appended to the current dataset (D n−1 at round n). As a simulation of manual annotation, the labels for each image are given after selection so that the labels are unknown during selection. Besides, all images are replicated four times, blurred by Gaussian noise with a standard deviation of 0.01 (i.e., 5 blurred similar images), and appear continuously on the stream to simulate high-frequency camera capture as discussed in Section 3. Also, to simulate the existence of many unuseful images, we fill each stream with many "non-object" images (1408 images for our experiments). Consequently, an additional class is added to the task, i.e., the former C-class classification becomes a (C + 1)-class classification, but instances of this added class are not included in the evaluation dataset.
Methods To solve the stream submodular optimization problem, we use and compare two known approximation algorithms SIEVE-STREAMING++ [19] (which we denote as SSPP) with = 0.1 and ThreeSieves [5] with = 0.1, T = 100. As a comparison to our method, we consider an extension of a classic active learning method: To the best of our knowledge, there are no existing methods for the problem we consider, but some standard active learning methods can be adapted with trivial modifications. For example, uncertainty sampling with entropy [36], which is a one-by-one poolbased method, can be extended such that it maximizes the sum of sample entropy in the batch (see detailed description in Appendix A). To evaluate the importance of considering the problem-specific properties discussed in Section 3, we compare this method with ours. Moreover, we also compare with random selection as a baseline. We denote these methods as Entropy and Random respectively.
Objective function As a measure of informativeness of each sample (i.e., g in Eq. (2)), we use the entropy of softmax output [36]: Let F (x) i be the i-th value of softmax output for the input x, This takes the highest value when outputs for all classes are equal and the lowest when the output is one-hot. To evaluate the diversity of a set with Eq. (3), we define k as polynomial kernel, which is positive definite [13]: For a given pair of images x, x ∈ X , their similarity is evaluated as is a middle layer output.
Cold-start scenario In this experiment, we use the popular datasets MNIST [26], Street View House Numbers (SVHN) [31], and CIFAR-10 [23], which consists of color images of objects from 10 classes. As discussed in Section 3, we often have to confront with class-imbalance in active learning on edge devices. To simulate this, we divide the number of samples by 10 for half of the categories, similar to experiments in Aljundi et al. [1]. As a cold-start setting, we set |D 0 | = 1000 and training from scratch in each round, i.e., after selecting a batch of up to 128 images from the stream. After the training, the model is evaluated on the test data in each dataset.
The results are shown in Figure 1a. At first, we can see that our proposed framework with SSPP achieves the best performance for all dataset. Only in MNIST experiments, the easiest task here, Entropy also seems to work well. These results suggest that more complex tasks need more consideration of diversity. Although the objective function is the same, ThreeSieves performs worse than SSPP by a large margin. The direct reason for this is because the number of selected images is small. It is observed that ThreeSieves tends to select fewer images than the allowed amount K in each round (the total number of selected images are described in Appendix E). This tendency is affected by the hyperparameter T , and the choice of its value will be important in practical application.
Domain adaptation scenario For the domain adaptation scenario, we perform our evaluation on two pairs of datasets, MNIST ↔ SVHN and STL-10 [6] → CIFAR-10 1 . We removed one class from both datasets in the latter setting since there are only 9 classes in common. As a domain adaptation scenario, the source dataset is available from the beginning. At each round, we train a model after appending the initial (source) dataset with images from the other dataset (i.e., target dataset). Like the cold-start scenario, we divide the number of samples by 10 for half of the categories. The evaluation is done on the test split of the target dataset.
The results are shown in Figure 1b. Similar to the cold-start experiments, we observe that our approach with SSPP outperforms all others. Moreover, we can see that ThreeSieves performs better than baselines in STL-10 → CIFAR-10 experiments. This means that it is possible to perform well in some types of data, and then we can benefit from the low computation and memory overhead.
Designing an objective function that helps to find good solutions is a fruitful future research direction.

Object detection
Detection of objects in an image is a complex task requiring relatively heavy computation. However, several models designed with a good balance between performance and latency exist, coping with an edge-computing setup [42,46,34]. In this domain-adaptation experiment, we use the approach Single-Shot Multibox Detector (SSD) [28] with the popular backbone Mobile Net v2 [34].
We use two datasets in the experiments, the popular COCO (2017) dataset [27] as the source dataset, which includes images with bounding box annotations of many categories, and BDD100K [45] as the target dataset, which is a large-scale dataset of driving videos. Most frames in the BDD100K dataset videos are not annotated with bounding box information, so we use the state-of-the-art detector EfficientDet [43] as an oracle for annotating selected image samples. The videos of BDD100K dataset are captured at 30 FPS, creating a stream with many redundant images. In this setting, selecting a diversified batch of samples is very challenging, and it is well suited for evaluating the performance of our method. We compare the same algorithms as in classification for solving the stream submodular optimization problem, with parameter = 0.01 set for SSPP and ThreeSieves, if not specified otherwise.
Objective function The detection task involves both regression of bounding box parameters and classification of object label, so ideally, we want a measure of the informativeness that copes with both aspects. In the context of active learning with detection tasks, Kao et al. [17] propose several uncertainty functions designed for object detection. We use a combination of localization stability and classification uncertainty as the objective function because those two do not rely on the architecture of the model. Keeping the notation of the paper, i.e., respectively S I (x) and U C (x): with λ a tradeoff parameter between classification uncertainty and localization stability (fixed to 0.5 in our experiments). For evaluating the diversity of a set, we use the same kernel function k as the image classification experiments, which is task-independent. The middle layer outputF (x) used in this experiment is the concatenation of feature maps of the model, just before feeding the SSD extractor layers. Domain adaptation scenario In this experiment, we initially train the detector on D 0 , the train part of COCO dataset. Then, for each round we select a batch of images from a stream composed of concatenated videos of BDD100k dataset (the stream used in each round starts at the end of the previous one), with each round's stream consisting of 10000 frames. Since the class of objects in the detection task must exist in both source and target datasets, we used the class bus; instances of it are not omnipresent in street footages, so selecting samples containing instances is non-trivial. The selected data S n is annotated by the oracle and appended to the previous dataset D n = D n−1 ∪S n . After training, the new model performance is evaluated on the validation split of BDD100K.
The results are shown in Figure 2. As for classification tasks, SSPP outperforms the other methods, showing the potential of this approach for complex tasks.
ThreeSieves and Entropy curves are however below the Random baseline. The streams are composed of videos with images taken at high frequency, it is then not surprising that Entropy approach performs poorly, as it lacks a mechanism taking the diversity into account. As we can see through error bars, the performance of ThreeSieves varies widely between experiments, showing a high dependence on the stream configuration. This is in accordance with this algorithm's functioning, as its reset component makes the result very reliant on the image order inside the same stream. We provide in the appendix both a comparison between SSPP with different values of , and examples of batch selected by each algorithm.

Real world evaluation
While our experiments above were conducted on a server for evaluation and reproducibility purposes, our framework is designed to run on edge devices. The two main issues for programs running on edge devices are the the memory footprint and the execution speed, so we perform a benchmark of the different methods we studied for both aspects. Execution speed We compare the execution speed of the methods used in the previous experiments. As the informativeness part of the objective function complexity depends on the model prediction, for a fair comparison, we assert that the input images are the same for all measurements. Thus, instead of capturing images from a camera, we load images stored beforehand on the device. The source code for our framework used on the device is the same as the one used in server experiments above running on CPU, but as the model inference is the bottleneck of computation, we optimized the inference computation using GPGPU 2 .
For each method, we measure the elapsed time between the processing of two successive inputs and average it on 1000 iterations. Results are compiled in Table 1. The first line is representing inference speed when no selection is performed, for reference. Firstly, we observe that the speed for all selection techniques are in the same order of magnitude, around 1 FPS. Entropy uses a greedy approach, so besides evaluating the objective function, there is close to no computation overhead. Thus, we observe that the computation induced by ThreeSieves is negligible compared to the objective function, as the reported speeds of ThreeSieves and Entropy are almost equal. The best performing SSPP is also the most computation-intensive, and because of the high number of sieves it uses, both reducing K or augmenting have a significant impact on the speed. The parameter directly influences the number of sieves considered during the computation in SSPP and is a tradeoff parameter between speed and accuracy. At fixed , each sieve's size depends on K, and so does the size of the matrix to compute the determinant of, for the evaluation diversity. This confirms the potential of Dividing K discussed in Section 4. Memory usage While Memory Swapping virtually increases the available memory, performing too much read/write on the storage device (e.g. SD cards) can harm its longevity and/or degrade execution speed. Among our studied methods, SSPP has the highest space complexity, so we measured its memory footprint during the experiments, with and without memoization discussed in Section 4. We report the average memory footprint and the peak use in Figure 3. While the version without memoization peaked above 100 MB, when enabled the memory use stayed below 10 MB, which can fit in the RAM of many edge-devices. The memoization allows to greatly reduce the memory footprint (around 10 times). The high consumption in the first rounds is due to the model uncertainty being very high, and the same sample is then cached for many sieves. While this phenomenon is masked in the memoization, we observe the interesting result that memory usage decreased as the learning progressed.

Conclusion
We formalized active learning for DNNs on edge devices. Based on the considerations about the nature of the problem, we proposed a general framework to solve this as a stream submodular maximization problem, which takes both the informativeness of sole data and the diverseness of a set of data into account. We evaluated our approach on classification and object detection tasks with several datasets. Empirical results showed that our approach outperforms other methods and can run even on low computational resources devices.

C.2 Construction Details
As discussed in Section 4, we have to define a kernel function k to evaluate the diversity of a set. There are many possible choices for k to measure the similarity between a pair of images x, x ∈ X . For example, whereF (x) is a middle layer output, β is a scaling parameter and JSD is short-hand for Jensen-Shannon divergence. Here, k 1 is known as polynomial kernel and k 2 , k 3 , k 4 are known as RBF kernel, both kernels are positive definite [13]. This selection can be interpreted as choosing which space we focus on, i.e., consider the similarity in the image space, feature vector space, etc.

D More Implementation Details
Our experiments on a server have been run on an Intel Xeon E5-2623 CPU with an Nvidia Tesla V100 GPU machine. Through all our experiments, we used the machine learning framework PyTorch [32].

D.1 Image Classification
For the classification task, we trained the model by Adam [20] optimizer with 12000 iterations, batch size 16. In each round, we trained the model from scratch. In domain adaptation experiments, we made the number of source domain images and target domain images in a batch the same since they are highly imbalanced, especially in early rounds. For the "non-object" image, we used a monochrome image obtained by taking the mean color (i.e., the means of each RGB channel) of the next real image in the stream. The elapsed time per round was a few minutes in each experiment.

D.2 Object Detection
For the detection task, we based our model on a PyTorch implementation of SSD 3 . The training setup for each round of our experiments is the following: input image size of 320, 120000 iterations with batch size 128, momentum SGD [40] optimizer with learning rate 1e −3 divided by 10 at iterations 80000 and 100000. For the oracle, we used the pretrained model EfficientDet D7 4 , with a score threshold of 0.6. For saving up computation, the round 0 (i.e., first training before selection) was skipped in all experiments and replaced by the loading of a model checkpoint trained with the same hyperparameters. The annotator has close to state-of-the-art precision but is not perfect, and we observed in experiments cases 5 of false positive (e.g., a cropped truck that was wrongly identified as a bus), that strongly impacted the trained model accuracy. Dealing with noisy labeled data is beyond the scope of this work, so we manually removed the experiments containing this kind of annotation.
As images with no bounding box annotation are ignored in our detector's loss function, we filtered out images from S n when the oracle detects no object. Also, if after filtering, no image remains (i.e., |S n | = 0), then D n = D n−1 , so we skipped the training of round n.
In this setting, the elapsed time during selection was negligible compared to the training time, and training a model took around 7 hours, so a single experiment of active learning took up to 70 hours.

E.1 Number of Selected Images
We report the number of selected images in Table 2, 3, respectively the results of cold-start and domain adaptation experiments. In both experiments, the images in a stream are duplicated, and the number of unique images is a good indicator to see how diverse were the batches selected. Moreover, we also show the total number of selected images, since SSPP and ThreeSieves may select fewer images than allowed (128 × 30 = 3840 in this experiments). While Random and Entropy always select the maximum number of images, we can see that SSPP and especially ThreeSieves select fewer. This would have a significant impact on performance.

E.2 Study of Parameter in SIEVE-STREAMING++
The parameter of SIEVE-STREAMING++ allows a tradeoff between the complexity of the algorithm and the optimality of the solution. We thus report in Figure 4 the performance of the method depending on the value of . Conform to our expectations, the higher the , the lower the performance. This is consistent with the approximation ratio of the algorithm (1/2 − ).

E.3 Examples of Selected Samples
We show the batches of images selected by different methods on the same round in Figure 5, 6, 7, 8. The batch selected by Entropy in Figure 8 contains a lot of informative samples, as we can see instances hard to detect (e.g., bus located far from the camera) or close to decision boundaries (e.g., trucks looking like buses). The redundance of samples in the batch is the consequence of the absence of a diversity component. Figure 6 shows the batch selected by ThreeSieves. As discussed in the experiments section, it exhibits the reset mechanism's weakness since there is a low probability for the samples of the first half of the stream to remain in the selected batch, resulting in a batch not very informative. Finally, the batch selected by SSPP in Figure 5 shows a good tradeoff between informative samples with diversity.