Enhancing Semi-Supervised Learning via Representative and Diverse Sample Selection

Thank you very much for your careful review of our work. We hope our responses can address all your concerns.

W1. Some of the claims made by paper already appeared in previous art [1-3]. The proposed manuscript does not reference or compare to any of these works.

Response: Thank you for your comment. It is indeed correct that certain aspects of our methodology and initial hypotheses draw from established findings in the literature. The inclusion of these elements is essential for building upon a solid foundation of existing research. However, our work makes significant advancements beyond these foundational elements.

Specifically, even if our method is based on the perspective of representative and diverse sampling that previous studies have proposed, as we said to Reviewer Qb3b, multiple combinations of representativeness and diversity criteria are applicable to defining sample selection optimization objectives, but one should also provide an efficient algorithm and some theoretical guarantees derive an effective methodology that has better generalizability. In our paper, we artfully use kernel methods and the properties of RKHS to derive a simple but effective approach to model the sample selection problem that fulfils the aforementioned requirements for a generalizable method. In the experimental part, we have compared our method with more recent methods (e.g., USL [6] and ActiveFT [7]) and have achieved SOTA performance (refer to Table 1).

W2. Any low-budget strategy could be potentially applied to SSL as well, so those methods should be compared against as well. See for example [4,5].

Response: We follow your suggestions and compare our proposed RDSS with [4] and [5] by integrating them into FlexMatch and FreeMatch on CIFAR-10 with 40 labels. The experimental results show that RDSS outperforms the two methods.

W3. If AL methods can be applied in this case, this method can be used as a method for picking labeled examples for active learning purposes and should be tested as such.

Response: Thank you for your suggestions. In fact, we have already conducted comparisons with several SOTA AL methods, as demonstrated in Table 2 of the original manuscript. To ensure a more comprehensive evaluation, we have further supplemented our study with additional experiments comparing our approach against various AL methods. The results of these extended experiments can be found in our response to Reviewer Qb3b's Weakness 3.

W4. The framing of the paper is a bit unclear to me. I think the paper could benefit from explaining use cases in which one has the option to pick in advance the labeled set for SSL, which is not already covered by AL use cases.

Response: Thank you for your insightful feedback regarding the framing of the paper. We understand that the distinction between the use cases of SSL and AL may not have been sufficiently clear, and we appreciate the opportunity to clarify this aspect. In this work, we focus on scenarios where one can select a labelled set for SSL in advance, a situation that is distinct from traditional AL use cases. A particularly relevant example is in the context of medical trials. In such trials, labelling data (e.g., annotating medical images or patient records) often involves significant time and resources, typically requiring expert review. If the labelled data in later rounds of the trial must be determined based on the outcomes of previous rounds, as in a typical AL setup, the entire project timeline could be significantly extended due to the sequential nature of labelling and analysis. We will revise the manuscript to explicitly differentiate these use cases.

Q1. Can you please elaborate on how the proposed method differs from the idea suggested in [2]?

Response: Thank you for your question. Our standpoints are all from the idea of representative and diverse sampling, but each method has its own criterion for representativeness and diversity. This situation also happens when comparing our method to USL [6] and ActiveFT [7]. However, among all these works, our method exhibits not only a theoretical guarantee for generalization error but also a fast and effective optimization algorithm for practical sample selection tasks. Moreover, our method can be implemented in some research problems in the literature of statistical subsampling (e.g. [8]), which shows its potential in interdisciplinary scenarios or problems.

Q2. How is the problem of selecting the labeled set of SSL different from the problem setting of active learning?

Response: We understand that this is a critical issue. In SSL, the selection of the labelled set is typically predetermined or randomly sampled from an available pool of labelled data. In contrast, AL is an iterative process where the model actively queries an oracle (e.g., a human annotator) to label new samples that are expected to be the most informative for improving the model.

References:
[1] Parting with illusions about deep active learning. arXiv preprint, 2019.
[2] Active learning on a budget: Opposite strategies suit high and low budgets. ICML, 2022.
[3] Active learning through a covering lens. NeurIPS, 2022.
[4] Low budget active learning via wasserstein distance: An integer programming approach. ICLR, 2022.
[5] NTKCPL: Active Learning on Top of Self-Supervised Model by Estimating True Coverage. arXiv preprint, 2023.
[6] Unsupervised selective labeling for more effective semi-supervised learning. ECCV, 2022.
[7] Active Finetuning: Exploiting Annotation Budget in the Pretraining-Finetuning Paradigm. CVPR, 2023.
[8] Optimal Subsampling via Predictive Inference. Journal of the American Statistical Association, 2023.

Thank you very much for your insightful comments. Since Weakness 1 and Question 4, as well as Weakness 2 and Question 7, address the same issue, we have consolidated them accordingly.

Q1. The definition and usage of variable X in the article are inconsistent.

Response: Thank you for your careful review of our work. In this article, $\mathbf{X}$ is used for describing datasets, $\mathcal{X}$ denotes the feature space, and X is denoted as random variables. Could you please point out the inconsistent part?

Q2. Is Y in the section starting from line 141 representing the point as X? If so, I suggest using notations like Xi, Xj for clarity.

Response: We understand your concern. From line 141, y and Y are used rigorously to explain kernel tricks and the definition of MMD, which are commonly used in statistics literature. Nevertheless, we will consider your suggestion for the modification.

Q3. In Chapter 6, the determination of the kernel and parameters seems arbitrary.

Response: Here is the determination of the kernel and parameters.
Kernel: Our determination of kernel is based on the kernel choice in the study of two-sample test by [1]. In fact, according to Remark 1 (line 170), you can see that any positive-definite and characteristic kernel is applicable to our method. Among all kernels, Gaussian kernels are the most popular in the study of machine learning, so we take them as our suggestion.

Bandwidth parameters: The choice is also based on [1]. So far there is no theoretical guidance for us to determine the bandwidth parameters of Gaussian kernels in measuring similarity or representativeness. Some methods optimize this parameter in the learning process, but this idea is not applicable in RDSS.

$\alpha$: According to lines 246-250, we derived a finite-sample-error bound for MMD, which measures the representativeness, leading to our suggestion of the range of $\alpha$. In the experiments, the choice of $\alpha=1-1/\sqrt{m}$ significantly outperforms other choices.

Q4 & W1. The SOTA models selected by the author in the experiments are somewhat outdated.

Response: Thank you for your suggestion. Since the sampling process and the SSL process are relatively independent, comparing the sampling methods across different SSL models may have a limited impact. However, we have still compared different methods under two additional SOTA SSL approaches, i.e., ReFixMatch [2] and SequenceMatch [3]. The experimental results in the table below show that RDSS achieves the highest accuracy.

Q5. What are the limitations of stratified sampling. Why was this method excluded?

Response: Stratified sampling requires prior knowledge of sample categories, and then random sampling is performed within each category. However, in many real-world scenarios, we do not have prior knowledge of sample categories, making stratified sampling inapplicable. This is its limitation. We have a more comprehensive description in the manuscript (Line 25 and Line 81).

Q6. In Table 2, what sampling method did the other comparison methods adopt?

Response: We are sorry for overlooking this. The sampling methods employed by the AL approaches in Table 2 are as follows:
CoreSet uses a greedy algorithm known as $k$-Center-Greedy to select a subset from the unlabeled dataset;
VAAL consists of a VAE and an adversarial network. The VAE tries to trick the adversarial network into predicting that all data points are from the labelled pool, the adversarial network learns how to discriminate between dissimilarities in the latent space. The samples predicted as "unlabeled" by the adversarial network are selected for labelling;
LearnLoss designes a loss prediction module for a target network, which predicts target losses of unlabeled samples. The samples with the top-$K$ predicted losses are selected to be labelled;
MCDAL utilizes two auxiliary classification layers to select samples with the largest prediction discrepancy between them as those requiring labelling.

Q7 & W2. What dataset does Table 3 represent?

Response: Thank you for your reminder. The dataset used in Table 3 is CIFAR-10. We will refine these details in the next version of our manuscript.

Q8. The author should objectively evaluate their method, including its limitations.

Response: Thank you for your insightful suggestion. We have discussed the limitations of our method in Appendix E.

References:
[1] A kernel two-sample test. The Journal of Machine Learning Research, 2012.
[2] Boosting Semi-Supervised Learning by bridging high and low-confidence predictions. ICCV, 2023.
[3] SequenceMatch: Revisiting the design of weak-strong augmentations for Semi-supervised learning. WACV, 2024.

Thank you very much for your constructive comments, which have definitely helped us enhance the paper and highlight its contributions in a better way.

W1. Given the vast literature on submodular/supermodular functions, is it not possible to get an algorithm purely from that standpoint? If so, how different would it be from the proposed one?

Response: Thank you for your question. In our opinion, it is possible to derive a sample selection algorithm from submodular/supermodular functions. This idea is inspiring to us, and we will try to explore its realizability. However, in our paper, if we apply submodular/supermodular functions to deal with the optimization problem, the problem can be purely combinatorial and may lose its advantage in low computational complexity, which is achieved by exploring the convexity of the weighed MMD function (see Appendix A.1).

W2. Can one derive things such as leverage scores to detect the outlier-ness of a given point (or any other score)? If so, then couldn't one use something such as diversity - outlier score (or add a score that models likelihood), with diversity such as Facility location function, and optimize the final objective using greedy?

Response: Thank you for your question. Multiple combinations of representativeness and diversity criteria are applicable to define sample selection optimization objectives by representativeness and diversity. However, to derive an effective methodology, one should also provide an efficient algorithm and some theoretical guarantees, which require a detailed study on the definition of the optimization objectives.

From this perspective, your idea can be effective if your final objective can be modelled by a submodular framework. Intuitively, this can be achievable if we detaily study the properties of facility location function, diversity - outlier score and models likelihood. In our paper, we use kernel methods and RKHS to model the problem and derive GKHR as an efficient algorithm and generalization/finite-sample-error bound as the theoretical guarantee. The artful combination of representativeness (MMD) and diversity (kernel functions) criterions provide us a simple but effective approach to model the sample selection problem, so we don't have to use greedy algorithm to deal with it. Nevertheless, next time, we will try to start from your standpoint to study this problem if possible.

W3. Comparison with facility location function [1-4] and diversity based approaches [5] is missing.

Response: We follow your suggestions and compare two facility location-based methods from [2], namely the k-center and the conventional Facility Location (FL) method, as well as the GLISTER method [5]. Notably, the k-center method is equivalent to the Coreset method [6], which we have already benchmarked in our original manuscript (refer to line 309, Table 2).

The sampling process in GLISTER is tightly coupled with the downstream classification task, making it impossible to pre-determine all labelled samples, which renders it unsuitable for SSL. Therefore, we conduct comparisons under the AL framework, consistent with the experimental setup described in Appendix D.5 of the original manuscript. The results are presented in the table below, demonstrating that RDSS consistently outperforms the other methods, with particularly significant improvements observed on CIFAR-100 using 7,500 labels. We will incorporate these experimental results into a subsequent version of the manuscript.

W4. I'd appreciate one experiment on fine-tuning the CLIP models [3] using the proposed method.

Response: This is a good point. We fine-tune the CLIP model via a selection-via-proxy approach [3]. We compare the RDSS with random and k-center sampling methods on CIFAR-10/100 with 10,000 labelled instances when applied to FlexMatch and FreeMatch. The results are shown in the table below, from which we find that RDSS achieves the highest accuracy, outperforming the other two sampling methods. We will incorporate these experimental results into a subsequent version of the manuscript.

References:
[1] Submodularity in machine learning and artificial intelligence. arXiv preprint, 2022.
[2] An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Models. arXiv preprint, 2024.
[3] LabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning. Journal of Data-centric Machine Learning Research, 2024.
[4] Deep Submodular Peripteral networks. arXiv preprint, 2024.
[5] GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning. AAAI, 2021.
[6] Active learning for convolutional neural networks: A core-set approach. ICLR, 2018.

Thank you very much for your insightful comments, which have greatly contributed to improving the quality of our paper. We hope our responses can address all your concerns.

W1. I would like to see images of the actual selected samples and visualizations of the feature distribution to demonstrate that RDSS indeed balances the representativeness and diversity.

Response: We follow your suggestion and upload a PDF that contains the actual samples selected using different sampling methods in the "global" response. It can be observed that in the samples selected by our method, the variation in the number of samples across different categories is minimal. In contrast, certain methods fail to select representative samples for every category. For instance, $k$-means does not choose any samples from the horse category. Additionally, other methods tend to select an excessive number of similar samples within a single category, thereby neglecting diversity. For example, the ActiveFT approach selects too many samples from the airplane category.