How to Select Which Active Learning Strategy is Best Suited for Your Specific Problem and Budget

Summary

Some recent works have shown that typical examples are more beneficial than more uncertain ones under low budget setting in active learning. However, there has been no prior works that address how to distinguish whether a budget is in low or high budget regime, or how to determine which approach should be taken. The authors propose SelectAL, an algorithm that handles the tasks using derivative-based test, for the first time. The algorithm is theoretically and empirically supported in Section 2 and 4, respectively.

Strengths

1. This is the first paper that addresses how to automatically determine selection strategies based on the budget in active learning. 2. The authors provide some theoretical justification for the derivative-based test method.

Weaknesses

1. Although Strength 1 is a great contribution of this paper, there are several assumptions some of which may not be realistic. Intuitively, efficiency and realizability are reasonable assumptions but it would be hard to check if universality is generally true or not. Furthermore, the uniqueness of $B_{eq}$ (line 120-121) seems like a strong assumption. 2. It is somewhat hard to follow the flow of this paper. It is partially because of the complexity of theoretical work, but also because there are many assumptions to justify the theory. But upon the clarification of the questions below, I am willing to increase the score.

Questions

1. I am very confused with the definition of the generalization errors. If my understanding is correct, $E_{low}$ and $E_{high}$ are the generalization errors on the same unseen test set using $\mathcal{L}_{low}$ and $\mathcal{L}_{hight}$, each of which are trained on $\mathcal{D}_{low}$ and $\mathcal{D}_{high}$. How is it related to the equation in line 111? 2. What the equation in line 111 is saying is that the generalization error of $\mathcal{L}$ trained on $B$ examples can be expressed as the convex combination of $E(qB)$ and $E(\alpha(1-q)B)$. But, $E(qB)$ is from a learner trained only on $qB$ examples and $E(\alpha(1-q)B)$ is from the other learner trained only on $(1-q)B$ examples. Is it generally true or even close to the reality? If the generalization error is a function of the test examples given the same learner, I think the convex combination makes sense but since it is a function of training examples, I am not sure it is reasonably true. 3. Where are equalities for q coming from for $B_{low}$ and $B_{high}$ in Appendix A? 4. If the uniqueness of $B_{eq}$ does not hold, what happens to the Eq.(3), particularly, for the case $|A| \rightarrow 0$? 5. Could the authors provide more details about the experiment setting used to produce Figure 2 such as a linear $\mathcal{L}$, the dataset, and reasoning behind of choosing exponential error function? 6. For selectAL, did the authors observe some cases where {low, high, rand} are selected alternatively unlike the expected monotonic behavior? Can the authors provide the sequence of selections on CIFAR-10 and ImageNet-50?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Please refer to the weakness and questions above.

Summary

This paper considers the selection of active learning methods under different budgets. Previous studies have shown that different active learning methods perform differently under different labeling budgets, and incorrect selection can lead to model performance inferior to that of random sampling baselines. To address this issue, the authors conducted theoretical analysis and proposed the SelectAL method, and related experiments showed that this method can achieve consistent performance improvements under different budgets.

Strengths

1. The idea presented is interesting and it tackles an important issue in active learning. 2. The experimental results indicate that the proposal consistently improved performance, supporting the claims made in the paper.

Weaknesses

1. There is room for improvement in the technological representation. 2. The connection between theoretical results and practical methods seems to be weak. Miscellaneous: The text font in the figures should be kept the same as the main body.

Questions

1. What is the physical meaning of $E_{low}(x)=E_{high}(\alpha x)$ in the assumptions (Section 2.1)? Can you provide a more intuitive explanation? 2. The theoretical results (Section 2) assume that there is a unique and minimal solution for Eq.(1). What kind of E satisfies this assumption, and is this condition general enough to support practical applications? 3. The proposed method (Section 3) seems weakly connected to the theoretical analysis. The theoretical results show that under specific assumptions, there exist sampling boundaries B_low and B_high for the Low-Budget Method and High-Budget Method, which can be calculated through closed-form solutions. However, the SelectAL method used in the proposed method relies on a training-evaluating method to identify the type of samples that are currently lacking. Can you provide more connections between theoretical results and practical methods? 4. In the experiments (Figure 6), there are indeed performance differences between different AL methods, but the differences are small (≤2%). Have you observed more severe phenomena? In Tables 1 and 2, there are similar phenomena, and the performance differences between all methods are not significant. Specifically, in the low-budget scenario, the classification performance is so poor that the model cannot be deployed. Is it necessary to introduce complex methods to deal with this? Perhaps, random sampling followed by the consideration of high-budget methods is already sufficient. --- Thanks for the detailed clarifications, which have addressed my concerns. I would like to keep my score.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors do not provide a discussion about the limitations and potential negative societal impact.

Summary

The paper studies an algorithm selection problem for active learning under different labeling budgets. A theoretical analysis is conducted The proposed algorithm uses a derivative approach by removing small sets of labeled examples to approximate the effectiveness of different active learning algorithms. Empirical results are shown for different labeling budget that SelectAL chooses the best active learning algorithm. Experiments are conducted on CIFAR-10, CIFAR-100 and ImageNet-50.

Strengths

1. The paper studies an important problem of how to choose the best active learning algorithm for a labeling budget. 2. Experiments demonstrates the effectiveness of the method in specific settings. 3. It is interesting to empirically see that random sampling performs as good as other active learning algorithms when given a moderate number of labeling budget.

Weaknesses

I have major concerns with the writing and structure of the paper. 1. The theoretical analysis and the actual algorithm seem to be very loosely connected. Currently, section 3 contains very little motivation from section 2. Also, the analysis framework makes assumption on universality making it unlikely to reflect the performance in practice. 2. The data removal process from a labeled set is not immediate to the reader but is the key underlying tool for the derivate approximation. How does one remove labeled examples from a labeled set using an active learning algorithm? 3. Throughout the paper, the data removal algorithms are used as TypiClust and inverse-TypiClust. Instead of formulating the algorithm as using general active learning algorithms for removal, the authors may discuss more in-depth why these two algorithms are actually effective in predicting low and high budget scenarios. Furthermore, the experiments seem to be inconsistent. Specifically, even though CIFAR-10 and CIFAR-100 have the same pool size, the experiments are conducted with inconsistent budgets. For example, 7k+1k and 25k+5k are used for CIFAR-10 while 9k+1k and 30k+7k are used for CIFAR-100. Since the paper's focus is on different labeling budgets, I believe more budget settings are also needed beyond just three. Lastly, algorithm selection methods have been studied before, but not for different budgets. The paper could benefit from the following related work: 1. Baram, Y., Yaniv, R. E., & Luz, K. (2004). Online choice of active learning algorithms. Journal of Machine Learning Research, 5(Mar), 255-291. 2. Hsu, W. N., & Lin, H. T. (2015, February). Active learning by learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 29, No. 1). 3. Pang, K., Dong, M., Wu, Y., & Hospedales, T. M. (2018, August). Dynamic ensemble active learning: A non-stationary bandit with expert advice. In 2018 24th International Conference on Pattern Recognition (ICPR) (pp. 2269-2276). IEEE. 4. (Note the first version came out Feb 2023.) Zhang, J., Shao, S., Verma, S., & Nowak, R. (2023). Algorithm Selection for Deep Active Learning with Imbalanced Datasets. arXiv preprint arXiv:2302.07317.

Questions

1. What's the underlying intuition and reasoning of why TypiClust and inverse-TypiClust can correctly predict the budget scenarios. 2. Why are the particular initial seed set size and batch size selected for CIFAR-10 and CIFAR-100.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Sufficient.

Summary

The literature has shown that the optimal type of active learning (AL) strategy depends on the type of budget. Methods based on uncertainty sampling are most effective when the budget is large, and methods based on typicality work better in the low budget setting. However, what qualifies "large" or "low" depends on different criteria such as the data set and its size, the type of neural network architecture that is trained etc. The paper proposes a general approach that automatically determines whether a given setting is low or high budget by decoupling the data set in different parts. The method is divided in two parts. In the first part, a different active learning strategy is used depending on whether a labeled image belongs to the low or high budget setting. In the second part, unlabeled images are added to the labeled set.

Strengths

Quality and clarity: The general motivation of the approach (i.e. combining low and high budget settings and using different strategies for each) is clear and makes sense given the recent AL literature. The first part of the algorithm is clear and more or less described in Algorithm 1. The clarity of the second part could be improved by writing its pseudo-code (in the main paper or appendix). Originality: Similar ideas that consider different strategies for different parts of the data set were recently published in the literature (e.g. [A,B]). Jain et al. [A] show that low-budget settings follow a linear law whereas high-budget settings follow a power law in the standard classification setting. They also try to estimate whether a setting is low or high budget. Mahmood et al. [B] also consider to learn the optimal budget over multiple datasets (in the multi-variate case) to improve model performance while minimizing labeling cost. This is related to the case where each dataset corresponds to a type of budget. However, [A,B] do not consider active learning strategies. [A] Jain et al., A Meta-Learning Approach to Predicting Performance and Data Requirements, CVPR 2023 [B] Mahmood et al., Optimizing data collection for machine learning, NeurIPS 2022 Significance: The idea of the paper is interesting as it allows to automatically find the optimal AL strategy and type of budget. However, I wonder how much it would be useful in real-world applications since it seems much more expensive to run than standard AL approaches (by constantly checking how much samples improve the performance, and then to determine whether they have to be added to the low or high budget).

Weaknesses

- As mentioned above, the whole method should be clearly written in the main paper or appendix to improve clarity. - Is the method scalable to real-world applications? If so, isn't it cheaper to select a few uncertainty strategies (in large scale applications) to optimize the general labeling cost? - Due to its nature, the proposed method SelectAL returns the same scores as the best baselines (TypiClust and ProbCover, according to Table 1 and 2). Would there be a way to combine low and high budget strategies to obtain significantly better performance than a single baseline?

Questions

See above

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

Author-Reviewer Discussion

Thanks to the authors for submitting a detailed rebuttal. Can the reviewers please read the author response and let them know if they have any further comments / need any additional clarifications? Best regards, - Your AC.

Thank you for the clarifications.

Thank you for the clarifications.