Active Learning for Deep Neural Networks on Edge Devices

To the best of our knowledge, most active learning studies consider data that is in some sense filtered, i.e., it is (implicitly) assumed that every candidate is a useful data sample for training. For example, when selecting data from an existing dataset, almost all samples are presumably relevant (except for mislabeling, etc.). 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. We show examples from real data in Appendix (Figure 4).

With regard to active learning on edge devices, we consider two main scenarios: cold-start 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.

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, regardless of the task, the computation of each sample’s informativeness can be done independently. Thus we define $f_{i}$ by using a function $g:\mathcal{X}\rightarrow\mathbb{R}^{+}$ and denote as

This is a form of linear modular function, and as $\forall x,g(x)\geq 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.

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.

As described in Section 2, expressing diversity is studied in various contexts. However, in most works, the proposed measure does not satisfy the constraints we consider, e.g., BADGE [3] requires a ground set for representing the diversity of one subset. Utilizing log-determinant [25, 24] allows for flexible design while satisfying constraints. Considering the similarity matrix $M=[k(x_{i},x_{j})]_{ij}$ for all $x\in V$ where $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ is a similarity function. Note that $M$ is always a $|V|\times|V|$ symmetric matrix, and all the diagonal values are equal to its largest value by construction. Considering the problem with combinatorial optimization perspective, let $M_{S}$ be the sub-matrix of $M$ indexed by $S$, i.e., $M_{S}=[k(x_{i},x_{j})]_{ij}$ for $x\in S$. Then, the diversity is described as

where $I$ is the identity matrix and $\alpha\in\mathbb{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\in\mathbb{R}^{n\times n}$ is symmetric and its smallest eigenvalue is larger than 1, the function $f(S)=\log\det(X_{S})$ is monotone submodular [38]. Thus if $k$ is positive semidefinite (i.e. $M$ is also positive semidifinite), $f_{d}$ in Eq. (3) is monotone submodular.

Constructing a positive semidefinite kernel is well studied, and we can do it very flexibly. For example, with any distance function $d:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}^{+}$, $k(x,x^{\prime})=\exp(-\beta\cdot d(x,x^{\prime}))$ where $\beta\in\mathbb{R}^{+}$ is a scaling constant can be a positive semidefinite kernel [12]. We show concrete examples and their interpretation in Appendix C.

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\cup\{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 (details in Appendix B). Also, there exists a $O(n)$ approximation algorithm for log determinants [7]. When we can tolerate approximation errors, this can be a reasonable choice.

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},\cdots K_{n}\}$ where $\sum_{i}K_{i}=K$. To simplify the problem, let $K_{1}=K_{2}=\cdots=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.

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(\cdot,\cdot)$. Although this is a standard technique, it is especially efficient when we use Sieve-Streaming++ because it often calculates the same $k(\cdot,\cdot)$ on different sieves.

As discussed in Section 3, we have to consider peculiarity of data. To simulate class-imbalance, we divide the number of samples by $10$ for half of the categories, similar to experiments in [1]. 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.

To solve the stream submodular optimization problem, we use the known approximation algorithms Sieve-Streaming++ [19] (which we denote as SSPP) with $\epsilon=0.1$. 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 pool-based 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.

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$,

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^{\prime}\in\mathcal{X}$, their similarity is evaluated as $k(x,x^{\prime})=\langle\hat{F}(x),\hat{F}(x^{\prime})\rangle$ where $\hat{F}(x)$ is a middle layer output.

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, several uncertainty functions designed for object detection are proposed [17]. 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 $\lambda$ 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 output $\hat{F}(x)$ used in this experiment is the concatenation of feature maps of the model, just before feeding the SSD extractor layers.