Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation

Experimental Settings Compared to SIMILAR

Our settings actually closely mirror the settings in SIMILAR. In SIMILAR, the rare class setup is very close to the long tail distribution setups in our paper. SIMILAR’s setting reduces the number of examples in some of the classes to form rare classes. Our long tailed setup also reduces the number of examples in different classes, but following a long tail distribution. In fact, the later half of the classes receive way less examples than the largest class, effectively making them the rare classes. We chose the long tail version for experiments since this setting has been much more widely adopted in deep learning literature than the construction in SIMILAR. Also, real world data often follow long-tailed distribution in practice. In our experiments, we included CIFAR-10LT and CIFAR-100LT in the original draft. Also, as suggested by Reviewer 7FVV, we also conducted extra experiment for ImageNet-LT (https://ibb.co/fVq3wsYJ) and iNaturalist datasets (https://ibb.co/F4fqyfdQ).

Our setup adopted from GALAXY, where we combined multiple classes into a single “other” or “out-of-distribution” class, which directly mirrors the out-of-distribution setting in SIMILAR. This is also known as the Open-Set classification setting, which is widely studied in deep learning literature.

Model Retraining Strategy

As mentioned in our paper, we use a reweighting strategy by weighting the loss of each example by the inverse class frequencies. Reweighting is usually preferred over resampling strategies (balanced dataloader suggested by the reviewer) for deep learning as we want to reduce the repetition of examples during neural network training to avoid overfitting.

Complete Time Complexity Analysis

First, as a reminder in our paper in Appendix C, the dominating computational cost has always been the neural network training and inference cost, which takes more than 90% of the total computational cost.

As for data selection algorithms, let $K$ be the number of classes, $N$ be the pool size and $B_{\text{train}}$ be the batch size, $D$ be the penultimate layer embedding dimension and $T$ be the number of batches. Below, we detail the computation cost of data selection of each algorithm we consider.

• DIRECT: $O(T(KN\log N + B_{train}N))$.
• GALAXY: $O(T(KN\log N + B_{train}KN))$
• BADGE: $O(TB_{train}N(K + D))$
• Margin sampling/most likely positive/confidence sampling: $O(TKN)$
• Coreset: $O(T^2B_{train}ND)$
• SIMILAR: $O(TB_{train}ND)$
• Cluster margin: $O(N^2\log N + TN(K + \log N))$
• BASE: $O(TN(D+B_{train}))$

Theoretical Guarantee

We are not sure about what you mean by “In practice, the effect of label noise and imbalance on such outputs might be more complex.” As the agnostic active learning algorithm specifically targets the label noise scenario and the optimal 1D threshold classifier is defined to address the imbalance issue, we think our theoretical argument can exactly be applied to this 1-D reduction setting. Concretely, the agnostic active learning procedure in Algorithm 2 is exactly trying to recover the empirical risk minimizer (ERM) when freezing all of the neural network weights and only looking at the sigmoid/softmax score space. The agnostic active learning algorithm has been proven to be noise robust and can identify the ERM efficiently.

To bridge the theoretical guarantee and the effect for deep learning, in deep active learning, almost all algorithms are trying to balance between querying uncertain examples and diverse examples. In our case, we utilize the margin scores as an uncertainty measure. For diversity, we want to provide better data coverage in our annotation. This has been traditionally done in the representation space using penultimate layer embeddings or gradient embeddings. However, as we show in our paper, these methods (such as BADGE and Coreset) underperform DIRECT in imbalance scenarios. DIRECT focuses on class diversity, combined with uncertainty sampling, labeling a more balanced dataset of uncertain examples (i.e. ones around the optimal separation threshold). Our theoretical guarantee directly translates into how well we are ensuring class-balancedness of the annotated examples. With an accurate threshold, our annotation around the threshold would result in higher class-diversity in annotated examples.

Thank you for providing the insightful review. We address your concerns below.

Using a different scoring in Eqn. 2 As you suggested, we could indeed subtract the mean instead of the max of the per-class softmax scores. The mean will simply be a constant for all examples, which makes the scoring equivalent to the confidence score. We totally agree that different scores can be used to rank the examples. For confidence scores, however, some of our initial experiments found it to be less effective than margin sampling. Notably, margin sampling has been shown to be a superior scoring function over confidence and entropy in several previous large scale benchmarking papers (e.g. [1] and [2]). We will nevertheless add a future work direction to test out different scoring methods beyond these scores.

Computation cost of all algorithms First, as a reminder in our paper in Appendix C, the dominating computational cost has always been the neural network training and inference cost, which takes more than 90% of the total computational cost.

As for data selection algorithms, let $K$ be the number of classes, $N$ be the pool size and $B_{\text{train}}$ be the batch size, $D$ be the penultimate layer embedding dimension and $T$ be the number of batches. Below, we detail the computation cost of data selection of each algorithm we consider.

• DIRECT: $O(T(KN\log N + B_{train}N))$.
• GALAXY: $O(T(KN\log N + B_{train}KN))$
• BADGE: $O(TB_{train}N(K + D))$
• Margin sampling/most likely positive/confidence sampling: $O(TKN)$
• Coreset: $O(T^2B_{train}ND)$
• SIMILAR: $O(TB_{train}ND)$
• Cluster margin: $O(N^2\log N + TN(K + \log N))$
• BASE: $O(TN(D+B_{train}))$

[1] Zhang, J., Chen, Y., Canal, G., Mussmann, S., Das, A. M., Bhatt, G., ... & Nowak, R. D. (2023). Labelbench: A comprehensive framework for benchmarking adaptive label-efficient learning. arXiv preprint arXiv:2306.09910.

[2] Bahri, D., Jiang, H., Schuster, T., & Rostamizadeh, A. (2022). Is margin all you need? An extensive empirical study of active learning on tabular data. arXiv preprint arXiv:2210.03822.

Sensitivity Analysis Thank you for the suggestion. We think our experiments already cover a wide range of imbalance ratios as shown in Table 1, even when fixing model training to be ResNet-18. As we have shown that our algorithm is superior across all of these ratios. Interestingly, when comparing the performance of random sampling, we see DIRECT saves an increasing amount of annotation costs as the dataset is more and more imbalanced. We will definitely add this observation to our paper.

More Detailed Analysis Thank you for the suggestion! We think this is indeed beneficial. We have to rerun some of the experiments for this. We will send over the analysis during the discussion period as soon as possible, once we get these numbers.

Thank you for the insightful and detailed review. We make the following clarifications to address your concerns.

Handling Label Noise by Agnostic Active Learning Algorithm The large body of classic literature of agnostic active learning studies exactly the active learning under label noise scenarios (please see [1-3] as examples). These papers study sample complexities in identifying the optimal hypothesis when annotations are noisy. DIRECT applies an instance of the agnostic active learning algorithm in finding the optimal separation threshold, which inherits the noise robustness with theoretical guarantees to be minimax and instance optimal (shown in [1] and [3]). We will include some of these discussions in our paper.

[1] Balcan, M. F., ... & Langford, J. (2006, June). Agnostic active learning. ICML.

[2] Dasgupta, S., ... & Monteleoni, C. (2007). A general agnostic active learning algorithm. NeurIPS.

[3] Katz-Samuels, ... & Jamieson, K. (2021). Improved algorithms for agnostic pool-based active classification. ICML.

Motivation and Justification behind DIRECT In active learning, almost all algorithms are trying to balance between querying uncertain examples and diverse examples. Uncertainty can come in many forms, such as entropy score, margin score, epistemic uncertainty, or even more recent methods such as local model smoothness and influence functions. In our paper, we choose to use margin sampling as it is computationally efficient, and has been shown to perform no worse than other more advanced methods in various benchmarking efforts [4-5]. We would also note that our method can use any of the scoring methods above in place of margin score.

The other beneficial philosophy is diversity in sampling. In other words, we want to provide better data coverage in our annotation. This has been traditionally done in the representation space using penultimate layer embeddings or gradient embeddings. However, as we show in our paper, these methods (such as BADGE and Coreset) underperform DIRECT in imbalance scenarios. DIRECT focuses on class diversity, combined with uncertainty sampling, labeling a more balanced dataset of uncertain examples (i.e. ones around the optimal separation threshold).

As we demonstrated in our experiments, we include plots for both accuracy and number of minority class labels, where the latter clearly shows DIRECT labels more class-diverse sets of examples.

Furthermore, to address your concerns, the optimal separation threshold is a novel proposal in our paper in the context of active learning.

[4] Zhang, J., Chen, Y., ... & Nowak, R. D. (2023). Labelbench: A comprehensive framework for benchmarking adaptive label-efficient learning. DMLR Journal.

[5] Bahri, D., ... & Rostamizadeh, A. (2022). Is margin all you need? An extensive empirical study of active learning on tabular data.

Different Learning Speed of Minority Class We think the different learning speed argument of minority class examples contributes to the motivation of DIRECT. Firstly, as DIRECT labels a more class-balanced set of examples, the learning speed of minority classes will be much faster when compared to other active learning algorithms. Furthermore, as we are adaptively labeling more examples when identifying the optimal separation threshold (Algorithm 2), we think these additional labels can significantly help in estimating the threshold. Without these additional labels, as you suggested, the decision boundary will be very inaccurate, which is exactly what the other active algorithms are experiencing. In other words, the slow learning speed of minority class results in bad estimation in uncertainty threshold (Figure 2a), and DIRECT mitigates this issue by adaptively labeling to find the optimal separation threshold, instead of relying only on the current decision boundary.

Additional Experiments Suggested by The Reviewer We actually do have the standard long-tail experiments in our paper, for CIFAR-10LT and CIFAR-100LT. In addition, we have conducted extra experiments under the LabelBench benchmark for ImageNet-LT (https://ibb.co/fVq3wsYJ) and iNaturalist datasets (https://ibb.co/F4fqyfdQ). In both cases, we are clearly seeding DIRECT dominating the other active learning algorithms.

Training Details Our pretrained ResNet-18 is the standard checkpoint in the PyTorch library. As pretrained models are much more widely available, we believe finetuning of neural networks can provide us better signal for practice.

Notation Issues In our paper the label space is defined as $[K] = 1, 2, …, K$. In the binary case, the label space is therefore {1, 2}. In section 4.1, as we mentioned right after the [0, 1], $\widehat{p}$ is mapping to sigmoid scores, which is different from the label space.

We just like the name DIRECT for our algorithm.

The margin score $\widehat{p}_i^k$ is indeed confusing as it is not a probability. We will change the notation to $\widehat{s}_i^k$ instead.