Unleashing the Power of Annotation: Enhancing Semi-Supervised Learning through Unsupervised Sample Selection

9. What is the input space over which the method is used? Is it the actual data? For coreset is it the penultimate layer representation, what are you using?

The input of the sampling algorithm is the output of the image feature extractor. The specific process is as follows. First, we leverage the pre-trained image feature extraction capabilities of CLIP, which is a vision transformer architecture, to extract features. Subsequently, the [CLS] token features produced by the model’s final output are employed for sample selection.

10. Remark 1 is rather confusing, if you present Thm 3.1 and then claim that thm 3.1 doesn’t always work.

Thm 3.1. claims that if the model (or hypothesis class) belongs to a certain RKHS, then the expected risk of the trained model (or hypothesis) is controlled. If not, then the theory is not valid. Since the methodology is designed to be model-free, we think it would be better if claim that Thm 3.1 does not work for every model.

11. Figure 1 can not be deciphered with out a basic explanation\legend for the colors.

Thank you for your comment, we will supplement the legend of Figure 1 in the revised version.

12. Equation 6: is f_I_p(x_i) why is it defined only for x?

This is definitely a typo. We are really sorry for that. Substitute $x_i$ by $x$ would be right. We will correct that in the revised version. Thank you for your carefulness.

13. In equation (8) what is K in B=2K?

K is defined in Thm 3.2. It is the upper bound of k(x,x) over $\mathcal{X}$.

14. The computational complexity of O(mn) should be better explained? Wouldn’t the kernel construction cost more?

The result of computational complexity almost directly follows from the result of https://arxiv.org/pdf/2101.07564.pdf. Please refer to Section 3.1. However, after numerical experiments, we find that the kernel construction indeed cost more time in high-dimensional cases. Therefore, we may revise the computation complexity by O(mnd) where d is the dimension of feature space. Thanks.

15. Overall Im not convinced at all that the approach of diversification and representativeness is an optimal one. There are other important trade offs in active learning such as exploration-exploitation, which can outperform this UPA approach, in my view.

Diversity as a criteria of selecting samples in semi-supervised learning is theoretically studied by https://doi.org/10.1080/01621459.2023.2282644, and the simulation results in this paper shows that diversification indeed works. Representativeness is a straightforward idea to measure the sampling quality. Thus our criteria for the unsupervised sample selection task could be proper. As for optimality, we think that there does not exists optimal strategy for such unsupervised task. The exploration-exploitation framework in active learning is indeed effective and ingenious, but our unsupervised sample selection task does not require feedbacks from the model, which makes some active learning framework improper for semi-supervised learning.

16. Please explain what does the flexMatch method do , and why you chose it for your UPA approach.

FlexMatch and FreeMatch are state-of-the-art SSL algorithms that already achieve commendable results when implemented with baseline sampling methods, such as random sampling. Enhancing their performance further is a challenging task. Our method, however, manages to improve their performance further. Therefore, choosing them serves to more convincingly demonstrate the effectiveness of our approach.

17. Why do you think the diversification and representativeness is the best one for AL?

In this paper we mainly focus on the methodology of unsupervised sample selection and its application in semi-supervised learning tasks, nevertheless, we did not discuss its application in AL tasks. Maybe diversification and representativeness could be a good choice for AL, as a extension of core-set approach (only representativeness considered) proposed in https://arxiv.org/abs/1708.00489, which is a well-recognise work in the community.

Thank you very much for your comments. We hope our responses can address all your concerns.

1. Mostly the empirical validation is lacking additional datasets to support the advantage of the method.

Your point regarding the importance of additional datasets for validating the strengths of our method is very pertinent. In this paper, due to time and resource constraints, we selected CIFAR-10, CIFAR-100, and SVHN as our primary datasets for experiments. These datasets were chosen because of their wide acceptance and representativeness in the SSL domain. Our method demonstrated significant improvements on these datasets, especially in scenarios with a limited labeling budget. However, we acknowledge that applying our method to a broader and more diverse set of datasets is necessary for a more comprehensive validation of its strengths. To this end, we have initiated preliminary experiments on the STL-10 and ImageNet datasets, which is expected to take some time. We will provide a detailed response with the results upon the completion of this task.

2. Improvement over random baseline is too modest in my view, 0.5 precent improvement when the STD is at 0.5 is not convincing.

Current semi-supervised algorithms have already achieved relatively superior performance, making further enhancements a challenging and complex endeavor. Our methodology demonstrates limited improvements when the annotation budget is substantial. However, it shows considerable advancements in scenarios with constrained budgets. As shown in Table 1 of the manuscript, when employing UPA, Flexmatch achieves an accuracy improvement of 4.4% on the CIFAR-10 dataset with an annotation budget of 40, a 2.5% increase on the CIFAR-100 dataset with a budget of 400, and a 3.6% rise on the SVHN with a budget of 250. These findings align with intuitive conjecture: as the annotation budget increases, regardless of the sampling method employed, there is a greater likelihood of acquiring a more comprehensive set of samples. Consequently, the disparity between different sampling methods diminishes. Therefore, the superiority of a sampling method becomes more pronounced with a smaller annotation budget.

3. We are missing a simple ablation study: if you show results of flexMatch+UPA, you have to show also results of just flexMatch, otherwise it is not clear if the advantage is due to FlexMatch or the addition of UPA.

In the paradigm of Semi-Supervised Learning (SSL), a large amount of unlabeled data is initially provided, from which a subset is selected for labeling. The SSL algorithms, such as FlexMatch/FreeMatch used in our study, then leverage both the labeled and remaining unlabeled data for training. Therefore, any SSL algorithm cannot function independently without a sample selection method. The most widely used sample selection strategies currently are random sampling and stratified sampling. Stratified sampling necessitates prior knowledge of each sample's category for performing random sampling within each category, which is impractical in real-world scenarios. Consequently, random sampling serves as a feasible baseline method for comparison with our approach.

4. 3 independent runs is not enough.

Thank you for your comment. We will increase the number of experiments conducted to reduce the randomness in the experimental results.

5. Why are you selecting the particular m values for each data set? why is it different for each data set? I would much prefer seeing a graph over a range of values.

In the domain of SSL, most of the popular algorithms adopt such experimental settings, as referenced in [1]-[3].

[1] https://proceedings.neurips.cc/paper/2020/file/06964dce9addb1c5cb5d6e3d9838f733-Paper.pdf
[2] https://proceedings.neurips.cc/paper/2021/file/995693c15f439e3d189b06e89d145dd5-Paper.pdf
[3] https://openreview.net/pdf?id=PDrUPTXJI_A

6. Not enough method are used in the comparison, what about BADGE by Ash et al - it is a classical diversity and uncertainty approach that could also be compared to show that representativeness and diversity is better (if it is indeed so…).

Thanks for your suggestions, we are adding comparative experiments with BADGE.

7. The requirement that m/n <=0.2 is quite weak and unrealistic, sometimes 0.2 can be a huge data set to annotate! How does that work with Active learning setting in which the budget is limited.

We conducted comparative experiments under different labeling budgets, where m/n=0.2 represents the scenario with the maximum labeling budget. In most comparative experiments, the value of m/n is much less than 0.2. For instance, on the CIFAR-10 dataset with a budget of 40, the ratio is m/n=40/50000=0.0008; similarly, on the SVHN dataset with a budget of 250, it is m/n=250/73257=0.0034.

8. There is no pseudo code describing the method, or at least a set of steps.

Due to space limitations, we display the pseudocode in the appendix.

3. Performance under the supervised training paradigm.

Regarding the query you raised about 'at what subset size the accuracy would match the accuracy of a classifier trained on the whole training set', we consider this to be a highly valuable research direction. Such comparative experiments would significantly aid in a more comprehensive evaluation of the selection efficiency of our method. We trained classifiers in a supervised manner on CIFAR-10 with annotation budgets of 7,500 (15%), 12,500 (25%), 17500 (35%) and 50,000 (100%), respectively. The table below presents the experimental results. We observed that when the annotation budget is 7,500, our method is comparable to AL methods. Although AL methods also utilize only labeled data for supervised learning, it features a coupling of model training and sample selection, with the model's performance progressively improving during training, thereby tending to select samples more effective for enhancing model performance. Conversely, our approach is agnostic to the data prior to sample selection. With an annotation budget of 12,500, our method's accuracy reached 91.2%. At a budget of 17,500, our method's accuracy attained 93.8%, closely approaching the accuracy of a classifier trained on the whole dataset.

Thank you very much for your comments. We hope our responses can address all your concerns.

1. Introducing the parameter $\alpha$ doesn’t seem to have enough theoretical or experimental grounding. From the theoretical standpoint, the trivial case $\alpha=1$ makes all bounds tighter than for any other alpha. From the experimental part, the only ablation analysis of $\alpha$ is given in table 3, it doesn’t fully convince that using any other value except $\alpha=1$ is any better.

We will explain the necessity of introducing $\alpha$ from two aspects.

1.1 From a theoretical perspective

Theoretically $\alpha=1$ makes all bounds mentioned in this paper tighter, but this degenerates $\alpha$-MMD into MMD, which lead to the lack of diversity of samples selected by GKHR algorithm. Hence, even though setting $\alpha=1$ benefits the tightness of bounds, it violates the main goal of our idea. Actually, we prefer to regrad $\alpha$ as a predefined parameter which only depends on our preference for the diversity of selected samples. Nevertheless, the analysis on the bound helps us to derive a optimal choice of $\alpha$, which makes the selected samples as diverse as possible under the premise of their representativeness. The word "optimal" could be exaggerate here, but we still emphasize that it is recommended. We think substitute "optimal choice" by "recommended choice" to describe the setting $\alpha=1-1/\sqrt{m}$ in the revised version could be more proper.

1.2 From an experimental perspective

In fact, we have also conducted experiments with various values of $\alpha$ on CIFAR-10. However, due to the constraints of the initial submission deadline, these results were not included in the manuscript submitted. The experimental results on CIFAR-10 are reported below, and the setting of $\alpha=1-1/\sqrt{m}$ consistently achieved the highest Top-1 classification accuracy under three different annotation budget scenarios (i.e. $40$, $250$ and $4000$).

2. Specifically, the results for $\alpha=1$ and "optimal" $\alpha=1−1/\sqrt{m}$ are quite close, and measured only on 3 datapoints for one dataset. More experimental grounding for motivating the choice $\alpha=1−1/\sqrt{m}$ over $\alpha=1$ would help.

Although the "optimal choice" looks quite close to $1$ when $m$ is large, the following table, containing the result of $10$ rounds of experiments on a set of simulated data ($2000$ samples generated from uniform distribution 1 in Appendix A.4), shows that even slight changes on $\alpha$ could make the selected samples quite different. The elements in the table is the average cardinality of the set difference between the $m$ samples selected by GKHR with trade-off parameter $\alpha$ and $\alpha_0=1$.

Thank you very much for your comments. We hope our responses can address all your concerns.

1. Limited comparison to other sampling methods (only random sampling).

We are currently in the process of replicating some other methods, and we will provide a response with the results once this task is completed.

2. Marginal improvement over random sampling (Tab. 1 overlapping confidence intervals).

Current semi-supervised algorithms have already achieved relatively superior performance, making further enhancements a challenging and complex endeavor. Our methodology demonstrates limited improvements when the annotation budget is substantial. However, it shows considerable advancements in scenarios with constrained budgets. As shown in Table 1 of the manuscript, when employing UPA, Flexmatch achieves an accuracy improvement of 4.4% on the CIFAR-10 dataset with an annotation budget of 40, a 2.5% increase on the CIFAR-100 dataset with a budget of 400, and a 3.6% rise on the SVHN with a budget of 250. These findings align with intuitive conjecture: as the annotation budget increases, regardless of the sampling method employed, there is a greater likelihood of acquiring a more comprehensive set of samples. Consequently, the disparity between different sampling methods diminishes. Therefore, the superiority of a sampling method becomes more pronounced with a smaller annotation budget.

3. Not clearly and convincedly presented advantages of the method (e.g., Fig. 2, it's hard to see the claimed benefits).

We have introduced a parameter $\alpha$ to encourage diversity among the selected samples, ensuring that they are as dissimilar as possible. This approach prevents the over-concentration of selected samples and thereby avoids label redundancy. Figure 2 illustrates how our method achieves better space-filling property in sampling within different categories. In contrast to the other two methods, our approach does not result in sample clustering. We will given a more specified explanation in the revised version.

4. Focus on the selection step to approximate the distribution (estimated from the large dataset) with few examples. Compare the proposed approach to related work, discuss pros and cons. Finally sketch various applications (including SSL) briefly which will benefit.

The process of sample selection in AL is inherently coupled with model training. Thus, the selection procedure iterates in tandem with the model training, where a subset of samples is chosen in each iteration for labeling and training until the budget is exhausted. However, our approach entails a one-time selection of all samples for labeling. This results in our sample selection algorithm being inapplicable to the AL paradigm, thereby posing challenges in direct comparison with other AL methods.

In order to provide a more intuitive comparison between our sampling method and AL sampling methods in Related Work, while considering that AL sampling methods only utilize labeled data for supervised training, we devised a new comparative experiment under the same labeling budget constraint. First, we employed our method to select samples for annotation, followed by using these annotated samples for supervised classifier training. This step was undertaken to demonstrate the performance contrast between different sampling methods in supervised learning. The table below presents the experimental results.

It is worth noting that within AL framework, sample selection is tightly coupled with model training, where model training is dynamic, and subsequent sample selection becomes more precise as performance improves. This is an iterative process that continues until the labeling budget is exhausted. In contrast to our sampling method, all samples that require annotation are determined before training (i.e., in the absence of knowledge about the training data). The challenge with this approach is that all samples must be selected initially, and there is no flexibility to adjust sample selection based on intermediate training results. Although theoretically, this may lead to lower performance compared to dynamic sample selection in AL methods, experimental results demonstrate that even under a static selection framework, our method can achieve performance similar to AL. This indirectly reflects the advantages of our method.

5. How does the approach scope with low and high dimensions? How does the approach scope with different distributions (overlapping, clusters well separated, etc.)? What are limitations?

a) Using MMD to measure the representativeness is not influenced by the dimension of feature space theoretically, since MMD is actually the distance between kernel mean embeddings of full data and selected samples in a RKHS. Similarly, $\alpha$-MMD also enjoys such property. Therefore, the approach is not sensitive to the dimension of feature space.

b) The "optimal choice" is actually a recommended choice, and derived only from theoretical aspect. However, in practice, this choice seems to be effective. For well separated clusters, the algorithm is encouraged to select more data points lying on the boundaries of the clusters, which are more informative than the data points that lie aside the center of clusters. For overlapped distributions, since in the assumptions of SSL, few points are close to each other but in different classes, diversification is still a good idea for selecting informative samples. Consider that diversification prefer to select boundary points, low-density-region points and points from small clusters, the representativeness ensures that the proportion of selected points from each cluster is not too different from the proportion of full data. Nevertheless, if the cluster are sufficiently far from each other, we could encourage more diversity via decreasing the value of $\alpha$ so that more boundary points are selected.

c) A limitation of our method is that there is no certain criteria for choosing $\alpha$ that consider the distribution of full data. In b) we find that for overlapped distributions and clusters-well-separated distributions, choosing $\alpha$ could possibly follow different strategies. In other words, there could be a better choice (such as some distribution-dependent ones) for $\alpha$ than that we recommend.

3. Reg. table2. Since UPA is employed above SSL (flexmatch/freematch), it may be important to compare against baseline/SOTA AL criteria when employed with flexmatch/freematch. Then the advantage of the proposed criteria would be explicit. Now it is not clear whether the imporvement is because of flexmatch/freematch or because of the proposed criteria.

The improvement is related to both aspects. As shown in Table 1 of the manuscript, Flexmatch/Freematch already outperforms the AL/SSAL methods when our method is not used. Furthermore, with the adoption of our method, there is a further enhancement in performance.

In order to provide a more intuitive comparison between our sampling method and existing AL sampling methods, while considering that AL sampling methods only utilize labeled data for supervised training, we devised a new comparative experiment under the same labeling budget constraint. First, we employed our method to select samples for annotation, followed by using these annotated samples for supervised classifier training. This step was undertaken to demonstrate the performance contrast between different sampling methods in supervised learning. The table below presents the experimental results.

It is worth noting that within AL framework, sample selection is tightly coupled with model training, where model training is dynamic, and subsequent sample selection becomes more precise as performance improves. This is an iterative process that continues until the labeling budget is exhausted. In contrast to our sampling method, all samples that require annotation are determined before training (i.e., in the absence of knowledge about the training data). The challenge with this approach is that all samples must be selected initially, and there is no flexibility to adjust sample selection based on intermediate training results. Although theoretically, this may lead to lower performance compared to dynamic sample selection in AL methods, experimental results demonstrate that even under a static selection framework, our method can achieve performance similar to AL. This indirectly reflects the advantages of our method.

Furthermore, our research aims to enhance the performance of SSL algorithms. We acknowledge that in the SSL domain, the sample selection problem has been a long-neglected and under-researched area. Consequently, there are limited existing methods available for comparison. In our paper, particularly in Table 1, we have conducted a detailed comparison of two commonly used methods in SSL algorithms. The comparative results showcase the superiority of our method, indicating that our approach can improve SSL performance, especially when the annotation budget is limited.

Simultaneously, considering practical application scenarios, especially when dealing with a large amount of unlabeled data and constrained labeling budgets, both AL, SSAL and SSL are viable options. In our paper, Table 2 compares the performance of these different methods in practical applications, aiming to illustrate the variations in results brought about by different choices. We hope this comparison can provide valuable reference and guidance to future researchers facing similar situations.

We hope that our response above addresses your concerns. If you have any further questions, we are open to conducting additional experiments and analyses to provide further clarification.

4. In the proof of theorem3.2, "j" is defined as argmin over i=1to n\I_p for some objective. But in the proof the following is used: f_{I_p}(x_j_{p+1}) <= f_{I_p}(x_j). Is this correct?

Thank you very much, again, for pointing out our typo. The inequality is not correct for sure. Actually,

therefore, the following inequality would be valid (under the assumption in Theorem 3.2).

we will correct this typo (together with several other typos) in the revised edition of this paper.

Thank you very much for your comments. We hope our responses can address all your concerns.

1. None of such methods have been discussed nor have been empirically compared with. This makes it difficult to evaluate the significance of the proposal.

We appreciate your suggestion regarding the comparative methods. We are currently in the process of replicating these methods, which is expected to take some time. We will provide a response with the results once this task is completed.

2. The weighting idea and corresponding algorithm details are more or less straightforward (Mainly because it is a simple modification of MMD).

Firstly, in SSL tasks, especially the procedure of selecting unlabelled data, how to effectively utilize limited labeled data remains an unresolved challenge. Consider MMD is a powerful tool to measuring the distance between distributions, our idea is the first to apply the modification of MMD to resolve such problem via a unique approach. Secondly, the reason why we choose MMD is not only because MMD is a proper statistical divergence, but also due to the fact that the modified version of MMD $(\alpha-\operatorname{MMD})$ is capable of measuring both the representativeness and diversity. For other popular statistical divergence, including Wasserstein distance, total variation, etc., they cannot be applied in our task throught such a naturally and succinctly extension. Therefore, our idea is not a simple transplant, but an innovative development that combines the special property of MMD, which prefectly meets the demand of SSL. More importantly, the sample selection problem has being neglected for a long time in SSL. In our opinion, this problem is a considerable issue in applications of SSL, especially when labelling is expensive. Our idea provide a new perspective and solution to such problem, and validate the effectiveness of the methodology via sufficient experiments. Our innovative work not only generalizes the concept of MMD, but also contribute a new methodology with theoretical guarantees to the SSL community. We hope that this work attract more attention and interests to the problem of improving the efficiency of data utilization from the community.