Confident Sinkhorn Allocation for Pseudo-Labeling

Thank you for your positive review and precisely highlighting all of our key contributions. We hope our responses to the minor concerns provide the necessary reassurance required.

Question: Connection between CSA and PAC-Bayes bound in the algorithm.

Answer: the key label assignment in pseudo-labeling (PL) is to train on labeled data and generalize this estimation to predict the unlabeled data. Most of the existing research in PL implicitly assumes the strong generalization that the model performance on the labeled (train set) and unlabeled (test set) are similar. However, this generalization assumption is not always true. For example, if we have limited samples in the labeled set, the model can not generalize to predict the unlabeled set well. Thus, it can lead to poor PL performance. Without the PAC-Bayes result, the CSA part may fail into the above generalization issue.

Therefore, we present the PAC-Bayes result to theoretically analyze the generalization performance of ensemble models trained on labeled data and tested on unlabeled data. In particular, Theorem 2 reveals that the more number of labels data $N_l$ makes the generalization error tighter (better). This generalization finding is consistently aligned with the result in Theorem 1 (analyzing from a different perspective). In addition, our generalization result in Theorem 2 considers the ensemble of multiple classifiers – the setting which has not been analyzed in Theorem 1. Thus, both theoretical results complement and strengthen each other in our paper.

Minor suggestion for legend: Thank you for mentioning this. We will improve the presentation of the legends in the final version.Particularly, we will make better word choices for the legend and have the corresponding caption to be more descriptive.

Thanks for the reponse. I have no further concerns to this work, so I prefer to maintain my score, while I'm not very familiar with the uncertainty estimation methonds, such that I suggest that Chairs mainly refer to the opinions of reviewers who are more professional in this field.

We thank the reviewer for insightful suggestions which are very helpful to improve the clarity of the paper. When reading this, it seems the reviewer believes our work makes a meaningful contribution. We hope we can clarify your issues.

Question: In Table 1, FlexMatch should be characterized as non-greedy

Answer: Using OT, each datapoint will be jointly assigned labels in the presence of other assignments. In contrast, using FlexMatch (and other PL approaches), each data point assignment will purely depend on the given threshold and does not necessarily depend on the other assignments. FlexMatch still falls into this greedy category. Nevertheless, in comparison to the other PL approaches, FlexMatch is less greedy in the sense that it defines the different thresholds for each class.

Question: Figure 4, the top red square on the left fails to adequately illustrate the distinctions in assignments.

Answer: We can improve this figure in the final version to make it clearer. In Figure 4, we use color (yellow is 1 and dark blue is 0) to indicate the numerical value of the assignment. The top red square actually has the value of 0.3 in brighter blue, although it is not visually clear enough to distinguish the dark blue (value =0), comparing to the other red squares in the bottom.

Question: In Algorithm 1, CSA (simplified), the derivation of $b_{-}$ and $b_{+}$ ...it is inferred that they are empirically estimated from the class label frequency in the training data or from prior knowledge.

Answer: Yes, they are empirically estimated from the class label frequency in the training data or from prior knowledge. We will mention them in the algorithm for clarity. Note that, $b_{-}$ and $b_{+}$ should be correctly written as $w_{-}$ and $w_{+}$.

Question: Are there alternative methods for statistical testing, more dependable methods for comparing the most probable class with the second most probable class?

Answer: Other alternatives for statistical testing include: Student-t test and Mann–Whitney U test. However, according to the literature [1,2,3], we should use Welch’s t-test by default, instead of Student’s t-test, because Welch's t-test performs better whenever sample sizes and variances are unequal between groups, and gives the same result when sample sizes and variances are equal. In addition, Ruxton (2006) [3] stated “...the unequal variance t-test (or Welch’s t-test should always be used in preference to the Student’s t-test or Mann–Whitney U test”

[1] Delacre, M. et al (2017). Why Psychologists Should by Default Use Welch’s t-test Instead of Student’s t-test. International Review of Social Psychology

[2] https://daniellakens.blogspot.com/2015/01/always-use-welchs-t-test-instead-of.html

[3] Ruxton, G. D. (2006). The unequal variance t-test is an underused alternative to Student's t-test and the Mann–Whitney U test. Behavioral Ecology.

We, therefore, opt for the proposed Welch’s t-test as the default choice in our framework. However, we can bring the above discussion in the paper to make it clearer for the readers. We thank the Reviewer for raising this useful question.

Question: the computational time of XGBoost increases with each iteration

Answer: First of all, most of the pseudo-labeling and SSL-based methods will suffer the same issue that the labeled dataset will grow over time after augmenting the unlabeled data. Such a growing dataset size will lead to more computational time. One potential solution is to consider online learning to incrementally update the model for XGB, without retraining from the scratch [1]. Note that this is beyond the scope of our paper, but we can mention it in the updated version of the paper.

[1] Montiel, et al. "Adaptive xgboost for evolving data streams. IJCNN 2020

Question: $\rho$ obviates the necessity to predefine a suitable threshold $\gamma$. But it introduces a new variable, $\rho$, necessitating a predefined value.

Answer: This is a very insightful comment. We follow the existing setting from SLA [44] to define the allocation schedule $\rho$ controlling the fraction of examples to be assigned labels in each iteration. The role of $\rho$ is to avoid assigning the entire 100% allocation in the first iteration for the OT approaches (both CSA and SLA). On the other hand, the threshold will stop this behavior from happening for other PL approaches.

A single assignment in PL can be sensitive to the value of $\gamma$ in being assigned or not. On the contrary with $\rho$ in OT, the assignment will be less sensitive to $\rho$ because we optimize the objective function to learn the assignment, i.e., minimizing the cost matrix to satisfy the row marginal distribution and column marginal distribution given the schedule allocation. There exist other factors (defined in the objective function) that influence the optimal assignment than the value of $\rho$ itself.

Thank you for the detailed review and a wide range of interesting comments. This review highlighted areas of our paper that absolutely needed to be clarified, so we appreciate the considerable time spent in finding them. We thank the reviewer in advance for reading our response, and hope that we have provided enough clarity that it is possible to provide us with a higher score as a consequence.

Question: It would enhance clarity to explicitly state the individual contributions of various sections within the methodology. The novelty of the optimal transport assignment in Section 2.3 appears somewhat limited. The primary concept seems to be derived from the original SLA [44].

Answer: The OT assignment plays an important role in our algorithm. However, we don't claim the novelty and contribution toward this OT part (we have clearly stated in the abstract, the last paragraph of the introduction, and Sec 2.3).

We summarize the novelty and significance as follows:

First, we are the first (to the best of our knowledge) to theoretically study the role of uncertainty in PL. The theoretical finding reveals that less uncertainty is more helpful. More unlabeled data is useful for a good estimation. Less number of classes and less number of input dimensions will make the estimation easier. The analysis takes a step further to show that both aleatoric uncertainty and epistemic uncertainty can reduce the probability of obtaining a good estimation. We note that the result presented in SLA [44] has only analyzed the first property (more number of unlabeled data is useful for a good estimation). The rest of the theoretical finding is novel and original.

Second, we propose to use Welch’s T-test to ascertain whether the most likely class holds statistically greater significance than the second-most likely class. This T-test (to be used with OT) eliminates the need to predefine the heuristic thresholds used in existing pseudo-labeling methods. Third, we extend PAC-Bayes bounds of ensemble models which provides a guarantee of generalization performance when trained on labeled data and tested on unlabeled data. Our bound strictly improves existing PAC-Bayes bounds for ensemble models and is of extended independent interest.

Note that both of our theoretical results contribute to subsequent research in this domain. These are identified and highlighted by Reviewer jWfa and Reviewer 33FF.

Question: There seems to be an inconsistency in the citation format used in the main text. The citation style in the introduction relies on numbers, but corresponding numbers in the reference list are missing. This inconsistency makes it challenging to match citations in the main text to the references.

Answer: We thank the reviewer for pointing out this citation format. In the current version, when clicking to the number citation in the main text using PDF, it will automatically link to the correct citation in the Reference. We will fix this formatting and update the paper.

Questions: The method is primarily evaluated within the context of semi-supervised learning tasks, where sample selection is a general aspect of the approach. It raises the question of whether this technique can be extended to other settings, such as active learning or learning with noisy labels. Exploring the adaptability of this method to these different scenarios and discussing potential challenges or advantages would provide valuable insights into its broader applicability and limitations.

Answer: we would like to thank the reviewer for the suggestion on the possible research extension from our proposed method, beyond semi-supervised learning tasks. Indeed, active learning or learning with noisy labels are the promising research directions that can leverage pseudo-labeling. Within the scope of our paper, we focus on the main task of SSL in which most of the pseudo-labeling methods have been evaluated. We will consider active learning and learning with noisy labels as the future work.

We thank the Reviewer for the overall positive comments and mentioning a few points to be clarified. We are glad that the Reviewer recognized our theoretical contribution for characterizing the role of uncertainty in PL and generalization bound.

Q: The optimization objectives for OT in Sec 2.3 lack clear explanations

A: Given the space constraints, we have presented additional details of the OT derivation and optimization in Appendix A.2 and A.3. There are three key components in the OT setting: the cost matrix, the marginal distributions for row and for column. We minimize the cost matrix to learn the optimal assignment, satisfying both marginal distributions. Specifically, the column marginal is a vector of one, i.e., each data point should not be assigned to more than one label, Eq. (6) and Eq. (11). In addition, each label should receive the amount of assignment ranging from lower bound and upper bound label frequency $[w_-, w_+]$, Eq. (7,8,12,13). We will highlight this interpretation in the final version.

Q: In Sec 2.1. the representation of the unlabeled data set as $\tilde{ X^k_i }$ seems non-standard. Given that $X^k_i$ denotes an individual data point, it would be more appropriate to use lowercase notation for clarity.

A: we follow the same notation in [Yang and Xu (2020), Sec 2.1] to denote the labeled vs unlabeled data set. The difference is that the original paper considers the binary setting with $X^+$ and $X^-$ while our setting considers multi-classification with k classes. In addition, we (also by Yang and Xu) use $X^k_i$ to define a data point which takes a class k. $X^k_i$ is equivalent to write $x_i \in X^k$ and $\tilde{X}^k_i$ is $x_i \in \tilde{X^k}$.

Q: the expression for the probabilistic classifiers $f_k(x_i)$ stated to produce a scalar value indicating the LLK of $x_i$ being labeled as $k$. However, the provided formulation $f_k(x_i) = N( x_i | \hat{ \theta_k} , \Lambda)$ suggests it's a function mapping to a normal distribution parameterized by $x_i | \hat{ \theta_k}$ and $\Lambda$.

A: $f_k(x_i)$ produces a scalar value indicating the LLK of $x_i$ being labeled as $k$. Then, we particularly consider the simple case of the Gaussian classifier, $f_k(x_i) := p(x_i | y_i = k) = N( x_i | \hat{ \theta_k} , \Lambda)$. This is the common notation used in [1].

[1] https://www.cs.ubc.ca/~murphyk/Teaching/CS340-Fall07/gaussClassif.pdf (see slide 7)

Q: In Theorem 1, $\mu_{\\k} = \mu_j | \exists j \in {1…K} \ k$ is ambiguous

A: Intuitively, k \ {1,...K} indicates the correct class index. We denote the incorrect class being \k = \mu_j \in {1…K} \ k. This refers to one of the remaining classes excluding k. $\exists j$ can be optionally dropped to make it concise. We hope it clear and will clarify them in the context of the theorem

Q: ablation study to discern the individual contributions of the ensemble effect and the proposed algorithm to the overall performance improvement?

A: Thanks for the great suggestion. We have made (below) the ablation study to learn the effect of ensembling. We show that the gain from the ensemble toward the final performance is not that significant to the overall performance improvement. In particular, ensembling XGBs will improve 2/5 datasets (Analcatdata, Digits) while degrade slightly for the other 3/5 datasets.

Q: the rationale behind selecting OT over the direct PL approach (Sec 2.2)

A: The Reviewer mentions pseudo-labeling approach presented from Sec 2.2. However, Sec 2.2. presents Welch's T-test for identifying high confidence samples while the PL approaches are described in the Related Work subsection of the Introduction. Please correct us if we miss anything.

OT is the non-greedy algorithm which can learn the best (non-trivial) label assignments. On the other hand, most of the existing PL methods are greedy which will rely on the predefined threshold to assign the labels. Specifically, using OT, each data point will be jointly assigned labels in the presence of others. In contrast, using the PL, each data point assignment will purely depend on the given threshold and does not necessarily depend on the other assignments.

We show in Sec 3.3 and Fig. 4 that OT assignment cannot be achieved simply by changing the threshold value (also mentioned by the Reviewer 33FF).

We feel we have addressed all of the concerns raised. As such, we are optimistic that you would be able to raise your score. If this is not possible, please let us know so we have an opportunity to address the remaining concerns.

Thank you for your response, which has resolved most of my concerns. However, regarding Weakness 4, you mentioned that $f_k(x_i) := p(x_i | y_i=k)$, but shouldn't it be defined as $f_k(x_i) := p(y_i=k | x_i)$? f_k produces a scalar value indicating the likelihood of being labeled as k. This definition somewhat affects the credibility of the conclusions drawn in the article, so I have decided to maintain the original score.

We are glad that we have resolved most of the concerns as acknowledged by the reviewer.

We thank the reviewer for mentioning the remaining concern left.

In our paper, we define $f_k$ produces a scalar value indicating the likelihood of being labelled as $k$. In particular, in Line 2, Page 4 in the paper, we have defined $f_k(x_i) := N( x_i | \hat{\theta}_k, \Lambda )$ which is correct.

However, during our response, we have written $f_k(x_i) := \textcolor{red}{p(x_i | y_i = k)} = N( x_i | \hat{\theta}_k, \Lambda )$ which is confusing as the reviewer pointed out. This should be corrected (by the reviewer) as $f_k(x_i) := \textcolor{blue}{p(y_i = k | x_i)} = N( x_i | \hat{\theta}_k, \Lambda )$.

Nevertheless, we want to call out that this typo $\textcolor{red}{p(x_i | y_i = k)}$ is from our rebuttal response while the equation presented in paper is still correct (Line 2, Page 4).

Given (1) the above correctness and (2) that we have addressed all other concerns, we would greatly appreciate if you can reconsider the score or please let us know what is your suggestion to fix this typo?

Thank you!

As per the Reviewer EorJ suggestion, we have updated the paper reflecting the changes to address the review feedbacks.

In the revised PDF, we use the orange color to indicate the new content (page 4, 10, 15, 16, 21,23). We aware that it is slightly over 9 pages, but we will fit the page limit later.

Please let us know so we have an opportunity to address the remaining concerns. Thank you very much!