Querying Easily Flip-flopped Samples for Deep Active Learning

Thank you for your constructive feedback that helped us further improve our paper and for a positive outlook. We are grateful to the reviewer for advocating our paper, and we will ensure that all the feedback and comments are incorporated into our final manuscript.

We thank the reviewer for an overall positive outlook of our paper as well as insightful questions. Let us clarify the points raised in the review:

The proposed approach provides somewhat mild benefits compared to already existing approaches (although it is consistently the best or the second best approach in each scenario, and the best according to metrics that consider the average performance among all datasets.)

We first emphasize that, as shown by our extensive experiments, our algorithm consistently outperforms or is at least at par with, prior state-of-the-art algorithms over various scenarios (varying datasets, networks, etc). This characteristic is very important as it shows how strong and safe our algorithm is, i.e., how robust our algorithm is to the scenario considered.

We also note that our algorithm appears to provide mild benefits compared to existing approaches because it is compared with the best-performing algorithm for each dataset. Our algorithm provides significantly improved performance when comparing each algorithm across all datasets, which is arguably a fairer comparison. For example, our algorithm significantly outperforms OML#6, OML#44135, CIFAR10, SVHN, TinyImageNet, and FOOD101 compared to BADGE on all datasets. In particular, there is a large performance difference of about 2% between the two algorithms on OML#6 and OML#44135.

The datasets considered in this paper are somewhat small-scale, and so it's not clear to me whether the proposed approach is suitable for large-scale applications. For example, in Table 2 where the authors present the running time per dataset, Imagenet — which is the largest dataset considered in this paper, is missing.

Could the authors provide the mean running time of each algorithm considered for the Imagenet dataset?

For ImageNet, we have used different hardware (CPU/GPU) for each algorithm due to time and resource constraints, so a fair comparison between the algorithms is impossible. Still, to answer your pointed-out weakness, one step of acquisition time (min) is reported. The results are as follows.

If we only compare the acquisition time of a single step, our algorithm seems to take longer than Entropy or Margin. Still, the difference is insignificant if we consider the training time of the model, which was three days. In the case of BADGE, the runtime is proportional to the square of the number of features and classes, so the runtime increases significantly on ImageNet compared to other datasets, which is in contrast to our algorithm, which is comparable to other algorithms. ENS has a short acquisition time, but this is because only the time for calculating the variation ratio is measured. If the whole training time of ensemble networks is considered, the runtime is about 15 days.

Careful discussion of limitations is lacking in the paper. There are many deep active learning algorithms coming out each year, each with its own pros and cons. A careful discussion of advantages and limitations will be very helpful to the community. One possible drawback is the need to use ensembles which takes more cost compared to methods that only use one model like BADGE and CoreSet.

Again, we would like to emphasize that in our paper, “ensemble size” is the number of sampled hypotheses in the LDM estimation. In our paper, we do not perform the usual ensembling where multiple models must be trained with multiple (random) initializations; instead, we replace this with sampling near a single trained model.

Thus, the drawback regarding the cost, as suggested by the reviewer, is not accurate, as we only train one model as well, similar to BADGE and CoreSet; this is clear when we compare the runtime of the algorithms in Table 2 in the main text.

Still, we agree with the reviewer that a careful discussion of the limitations of our framework is indeed lacking in our paper, and we would like to thank the reviewer for pointing this out. We have included another paragraph in the Conclusion section that discusses the potential limitations of our work. One limitation that is also an important future direction is to obtain a rigorous sample complexity guarantee for our LDM-S algorithm in the context of active learning; we have included this in our revised Conclusion section.

The seeding strategy seems detached from the novel estimator. Many strategies, e.g., [1], [2], and [4], have been published to extend to batches. It is better to compare these strategies based on LDM and show if the performance improvement is consistent.

Thank you for pointing out these recent works. First, [1] uses k-means++ seeding to introduce diversity to the acquisition, similar to our approach, along with a novel acquisition function; replacing that with LDM is precisely our current algorithm.

At first glance, Cluster Margin [2] is a viable option for LDM to be incorporated into, with LDM replacing margin score. However, this introduces an additional hyperparameter, margin batch size $k_m$, and the number of clusters $r$ among others, which requires an intricate tuning. This goes against our goal of keeping our proposed algorithm simple and intuitive. Also, during the preliminary phase of our research, we tried a similar approach in which we first sampled samples with high LDM (more uncertain) and then performed k-means clustering. Here, we observed that the tuning of the additional parameters relied heavily on the particular problem instance, and the overall performance was sensitive to such hyperparameters.

[4], which is a very recent work, proposes several alternate batch acquisition strategies, such as score-based and rank-based strategies. Indeed, it would be interesting to see how our LDM-based approach would combine with the alternate strategies, and we will definitely look into this in our future work. We would like to emphasize that our main novelty lies in proposing LDM, a new uncertainty measure, which provides very good performance in the active learning context.

I am very interested to see the performance of active learning models with MC-dropout. MC-dropout is more efficient compared ensemble method.

Again, we would like to emphasize that in our paper, “ensemble size” is the number of sampled hypotheses in the LDM estimation. In our paper, we do not perform the usual ensembling where multiple models must be trained; rather, we replace this with sampling near a single trained model.

In Table 2, we compare our approach to the MC-dropout-based approach (DBAL [9]) has about the same runtime as ours, yet the number of hypotheses for MC-dropout is 100 while our approach uses much more (for instance, for MNIST + SCNN, with stop condition $s = 10$, our approach uses roughly $10^4$ hypotheses). It should also be noted that with similar time, our approach consistently outperforms, or is at least at par with, DBAL over all tasks. In this respect, although somewhat similar, MC-dropout requires a bit more computation time than ours, as it requires going through all the neuron connections in the given network for dropout for each forward pass, in contrast to ours, which only involves sampling. In other words, given the same computation cost, our approach could yield more hypotheses than MC dropout; of course, the precise comparison would be different depending on the network.

We would like to thank the reviewer for providing several constructive comments. Let us clarify the points raised in the review:

Many baseline models are not considered in the paper's experiment, e.g., SAAL, Cluster-Margin, Similar, and [4].

We focused on uncertainty and diversity-baed baselines, which have been receiving lots of attention in recent years and which are much more related (and thus comparable) to our work. We emphasize that we have already considered quite a lot of standard baseline models to the best of our knowledge at the time of submission.

We thank the reviewer for pointing out additional baselines compared to which we could further show the effectiveness of our approach. Out of the suggested algorithms, we have added BatchBALD (Figure 13) and Cluster-Margin (Figure 14) results in Appendix F.3, showing that, indeed, our LDM-S outperforms both algorithms. We will add the results for the other suggested algorithms in the final draft (we are currently implementing those algorithms).

Computational cost analysis is lacking, including LDM estimation cost and LDM-S. What is the relationship to batch size, ensemble size, M, etc? The computational cost seems to be comparable to BADGE which has squared complexity to batch size.

First, we would like to emphasize that in our paper, “ensemble size” is the number of sampled hypotheses in the LDM estimation. In our paper, we do not perform the usual ensembling where multiple models must be trained with new initializations; instead, we replace this with sampling near a single trained model.

We have already included the computational cost analysis for LDM evaluation in Figure 10 of Appendix F.1; this cost is directly related to the number of Monte-Carlo samples $M$ and the number of sampled hypotheses $N$. The runtime for LDM evaluation is almost linearly proportional to the stop condition $s$ and is linearly proportional to $M$ and $N$.

Let us now clarify the dependency of the computational cost on the batch size. Our LDM-S has two stages: evaluating the LDM of each sample for the entire pool dataset (which only requires a single pass at the beginning) via Algorithm 1 and selecting samples for querying. The first stage is not affected by the batch size, but the runtime for the second stage increases linearly with the batch size since it requires selecting a batch size of samples. BADGE uses a similar seeding method; thus, its runtime increases linearly with the batch size. We would also like to clarify that BADGE has squared complexity to the number of features and classes, not the batch size.

The authors provide no analysis of the relatedness of LDM to active learner performance in the paper setting.

Could the authors provide numerical or illustrative examples to show that LDM-based algorithm can be more effective in deep active learning? The authors provided the asymptotical analysis of the estimator but no analysis is provided for the relatedness of LDM to the final performance. In this case, it is better to provide some illustrative examples to show the effectiveness of LDM-based algorithms.

To show the effectiveness of LDM, in Appendix F.1, we provide an ablation study by replacing LDM with other uncertainty measures, such as Entropy, Margin…etc, combined with our seeding algorithm. There, it is clear that out of all the considered uncertainty measures, LDM is the most effective in the context of active learning. Please also refer to Fig. 2 in the main text for illustrative examples of the effectiveness of LDM.

Dear reviewer ixMJ, please review and respond the the authors' responses to your initial review.

Thank you for your critical contribution to this conference.

The effect of each hyperparameter is studied independently. Nothing is said about how they affect each other. Does the choice of one hyperparameter (number of MC samples, batch size, LDM stop condition and σ interval) affect each other?

Thank you for asking this question. The number of MC samples, $M$, affects runtime and the estimation quality of the LDM, but it has little effect on other hyperparameters or performance, i.e., $M$ is independent of other hyperparameters. Batch size is also irrelevant as it is given by the task rather than being tuned individually in the algorithm by the learner.

The stop condition, $s$, and the $\sigma$ interval can indirectly affect each other. If the $\sigma$ interval is narrow, the estimation quality of LDM would be high with smaller $s$, although the number of intervals to be considered would also have to increase. If the $\sigma$ interval is wide, then to retain the estimation quality, $s$ also needs to be increased, but the number of intervals wouldn’t be as high as before. In our setting, we set the $\sigma$ interval sufficiently narrow for using a small $s$ to reduce runtime, which we have verified empirically to be the case when we grid-searched for the correct hyperparameters.

Which metric/score is used to quantify performance in section 4.2? Accuracy is mentioned in the appendix, but it is not entirely clear to me.

In Section 4.3 (Main Experiments), we use two performance metrics. We use test accuracy (%) for Table 1 and AUC for the Dolan-More curve (Fig. 3). We have included the exact expressions for the metrics for Fig. 3 in Appendix E. We have clarified this further in our revised manuscript.

x should be present in the input in algorithm 1, right?

Thank you for pointing this out. Yes, it should be part of the input. We have fixed this in our revised manuscript.

Perhaps, Assumption 3 is over-complicated: $\sup_{\epsilon \in (0, 1)} \lim_{N} \alpha(N, \epsilon) = 0$ amounts to saying that $\lim_{N} \alpha(N, \epsilon)$ exists and is 0 when $\epsilon \in (0, 1)$.

That is true. We wanted to state that $\lim_N \alpha(N, \varepsilon) = 0$ for any $\epsilon \in (0, 1)$ in a compact way. But we are happy to rephrase the assumption to be in a simpler term, as the reviewer has suggested.

I think $f$ in Theorem 1 should be $\alpha$?

Indeed, $f$ should be $\alpha$. Thank you for pointing out this typo. We have fixed it.

We would like to thank the reviewer for providing several insightful and constructive comments and pointing out several typos we have missed. Let us clarify the points raised in the review:

I think there exists an important gap between the theoretical description of LDM (its definition in Section 2.1 and its estimator in Section 2.2) and how it is empirically evaluated (Section 2.3). In Section 2.3, the "motivation" paragraph includes several sentences to justify the procedure that the authors are going to follow to empirically evaluate LDM, but these sentences are just somewhat "generic"/"loose", and there is no guarantee that hypothesis in Section 2.2 are satisfied. Taking this into account, I wonder whether Section 2.2 is a core component of the contribution, or could be moved to the appendix, leaving room in the main text for other information that may be more central to the contribution (e.g. a more detailed description of the experiments or further empirical evaluations, which are currently in the appendix).

Related to the first point above, some aspects of theory are disconnected from the implementation:

• To implement $L_{N, M}$ the authors propose to sample near the learned hypothesis using standard parameter perturbation techniques. As authors state, this sampling scheme would need to satisfy Assumption 3. However, it is not explained why this specific form of sampling assures that the hypothesis spaces $\mathcal{H}_n$ satisfy Assumption 3.
• In the 2D binary classification experiment, the performance of LDM-S, entropy, and random based sampling procedures are investigated. As authors state, true LDM is measurable in the 2D binary classification scenario. Thus, a study could be carried out on the error made when approximating L using $L_{N, M}$. Verification of bounds and rates of convergence could be carried out.

First, we would like to thank the reviewer for providing very insightful and constructive comments and questions that would help us improve our paper significantly. Indeed, as the reviewer has correctly stated, in the original draft, we did not theoretically justify our Algorithm 1 for evaluating LDM, thus seemingly creating a gap between Section 2.2 and 2.3.

However, we would like to emphasize that the current Algorithm 1 is inspired by our theoretical guarantees, and thus, we believe that Section 2.2 is a core contribution of our work. While proving the asymptotic consistency of the LDM estimator, we realized that Assumption 3 (coverage assumption) was required. Naturally, we thought that by sampling a sufficiently large, finite collection of $N$ hypotheses $\mathcal{H}_N$ with a distribution whose support spans the entire space, e.g., Gaussian distribution over $\mathbb{R}^d$ and is centered around $g$, we could “cover” the hypothesis that yields the true LDM with high probability, as $N \rightarrow \infty$. Conversely, if such a true hypothesis cannot be covered, we cannot hope to obtain a consistent estimator of LDM.

We agree with the reviewer that this still does not give a solid reason why the proposed sampling scheme should satisfy Assumption 3. But, we would like to remark that, as briefly mentioned in Section 2.3, directly verifying Assumption 3 for a very general scenario (e.g., deep neural network + multiclass classification + complex data distribution) is often impossible, as it is challenging to compute the true LDM nor identify the hypothesis that (approximately) attains the true LDM. On a slightly different note, we have shown in Appendix F.1 that for realistic deep AL scenarios, our algorithm shows a solid trend of convergence in the estimated LDM, which suggests that Assumption 3 is being satisfied.

We have also empirically shown that for the toy binary classification with linear classifiers in which the true LDM and the optimal hypothesis attaining the optimal LDM are known (see Section 2.1), the empirical LDM output from our algorithm converges to the true LDM. As the reviewer has suggested, we could prove that Assumption 3 can be attained in the same setting. We have included this in Appendix B.3. This shows that Assumption 3 is not unrealistic and is not an assumption for the considered toy example. Again, we thank the reviewer for this helpful suggestion.

Lastly, we agree with the reviewer that some of the experiments in the appendix should be moved to the main text. We have done so in the revised manuscript; see the general response for the changes that we have made.

Thanks to the authors for their detailed response, which has addressed a good amount of my concerns. Thus, I am raising my score to 8.

We would like to thank the reviewer for highlighting the strengths of our paper and providing several constructive comments. Let us clarify the points raised in the review:

Minor typo: Page 1, last paragraph: flips-flopped --> flip-flopped

Thank you for pointing out this typo. We have fixed this in our revised manuscript.

Section 2.2 is rather rushed in its presentation, and details are not expanded on. For example, it is unclear why $\mathcal{H}$ needs to be a Polish space (i.e., why second countability is necessary, for instance). In Theorem 1, $f$ is undefined. In Assumption 3, it seems that the phrase, "that is monotone decreasing in the first argument" refers to $\alpha$ but that is not fully clear.

Why does $\mathcal{H}$ need to be a Polish space as opposed to a more general metric space?

We thank the reviewer for pointing this out. We have revised Section 2.2 to be more well-motivated and have expanded on the missing details.

Thank you for pointing out the typos. Indeed, $f$ should be $\alpha$, and with a closer look, we realized that the “monotone …” part of the assumption isn’t required. We have removed that part, and we would like to thank the reviewer for helping us discover this.

The reason for assuming that $\mathcal{H}$ is a Polish space is to avoid any complications that may arise from the space being not countable, especially as we consider a probability measure over $\mathcal{H}$; see Chapter 1.1 of [1], where it states that the usual measurability and other related properties may not hold for non-separable spaces (e.g., Skorohod space). The Euclidean space, which comes up naturally by parametrizing $\mathcal{H}$ (e.g., neural networks), is Polish.

[1] Aad W. van der Vaart and Jon A. Wellner. “Weak Convergence and Empirical Processes: With Applications to Statistics,” Springer. 1996.

Similarly, some other details are presented with no clear rationale. For example, in (6), why is p(x) squared?

Our paper incorporates diversity by using the $k$-means++ seeding algorithm, which has been proposed in an influential prior work [1] for initializing the centers of clustering. Their seeding algorithm uses squared $p(x)$, i.e., squared distance, to minimize the potential function defined as $\phi = \sum_{x \in \mathcal{X}} \min_{c \in C} \Vert x - c \Vert^2$. Note that we only modified the distance measure from L2 to cosine distance between the features of the data points. In Appendix F.2, we have provided further ablation studies showing that the cosine distance outperforms L2 distance in active learning.

Please let us know of any other confusing details; we will be happy to elaborate.

[1] David Arthur and Sergei Vassilvitskii. K-Means++: The advantages of Careful Seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, 2007.

In Figure 2a, LDM sometimes samples on or very close to the decision boundary. Please change the color of the LDM crosses so they are more apparent.

Thank you for your suggestion. We have revised the figure accordingly.

In Algorithm 2, when you compute $L_x$ via Algorithm 1, could you clarify the parameters passed? My understanding is that you pass it a hypothesis parameterized by $v$, number of samples $m$, and a "small" $s$ (as said in Sec. 2.3), but I'm unclear what $\sigma_k^2$ you pass.

As described in Section 4.2, we set $s=10$, $M$ to be the same size as the pool size, and $\sigma_k = 10^{0.1k - 5}$ for k \in {1, 2, \cdot, 51\}. Figure 7 of Appendix C.2 shows the relationship between the disagree metric and $\sigma$. The $\sigma$ controls the $\rho$. To properly approximate LDM, we need to sample hypotheses with a wide range of $\rho$, and thus we need a wide range of $\sigma$. To efficiently cover a wide range of $\sigma$, we consider equal spacing in the log scale, where the spacing was chosen via a grid search.