InstanT: Semi-supervised Learning with Instance-dependent Thresholds

We consider the general setting from SSL, namely, we have a small group of labeled instances $X_{l}:=\{\bm{x_{1}},...,\bm{x_{n}}\}$ with their corresponding labels $Y_{l}:=\{y_{1},...,y_{n}\}$. And there is an unlabeled instance group $X_{u}:=\{\bm{x_{n+1}},...,\bm{x_{n+m}}\}$ with their latent labels $Y_{u}:=\{y_{n+1},...,y_{n+m}\}$, usually, we have $m>>n$. Furthermore, we assume that the labeled instances and unlabeled instances are independent and identically distributed (i.i.d), i.e. $X:=\{X_{l},X_{u}\}\in\mathcal{X}$, $Y:=\{Y_{l},Y_{u}\}\in\mathcal{Y}$.

We term the model trained with clean and pseudo-labels as $\hat{f}$, parameterized by $\theta$. Since $\hat{f}_{\theta}$ is bound to make mistakes, its generated pseudo-label $\hat{Y}_{u}$ will contain label errors. Hence the softmax predictions of $\hat{f}_{\theta}$ are actually approximating the noisy class posterior. We fix the notation for the real noisy class posterior as $P(\hat{Y}|X)_{t}$ at $t$-th iteration, whereas our approximated noise class posterior is $\hat{P}(\hat{Y}|X)_{t}$, which can be obtained from the softmax predictions of the model $\hat{f}_{\theta}$ at $t$-th iteration.

As the clean label for the unlabeled set is unknown, we instead wish to recover the Bayes optimal label for all the unlabeled instances, which is the label class that maximizes the clean class posterior [50, 56]. The Bayes optimal label is generated by the hypothesis that minimizes the risk within the hypothesis space, i.e. the Bayes optimal classifier, which we denote as $h^{*}$. And we can denote the Bayes optimal label for $\bm{x}$ as $h^{*}(\bm{x})$.

As mentioned in the previous section, label noise is an inevitable challenge in SSL. Moreover, since $P(\hat{Y}|X)$ is dependent on $X$, we say the label noise is instance-dependent [12, 45]. Concretely, we have $P(\hat{Y}|X=\bm{x})=T(\bm{x})P(Y|X=\bm{x})$ [32, 35], where $T(\bm{x_{u}})$ is the instance-dependent transition matrix, which models the generation of label noise. $P(Y|X=\bm{x})$ represents the latent clean class posterior for unlabeled samples. We can define the $ij$-th entry of $T(\bm{x})$ as:

which means the $ij$-th entry of $T(\bm{x})$ models the probability that $\bm{x}$ with clean label $y=i$ will be predicted as $\hat{y}=j$.

We assume our learned classifier satisfies Tsybakov Margin Condition [38], which essentially restrained the level of complexities of the classification problem by assuming the data are separable enough. It is a commonly used assumption for various Machine Learning problems [2, 6, 56] including SSL [48]. Without the loss of generality, we will directly present the multi-class Tsybakov Margin Condition [2, 56], whereas the binary case will be provided in the Appendix B.

Where $P(Y=\gamma|X=\bm{x})$ and $P(Y=s|X=\bm{x})$ are the largest and second-largest clean class posterior probability for $\bm{x}$.

To understand the choice of pseudo-label thresholds in SSL, it is essential to consider the trade-off between the quality and the quantity of the pseudo-labels [10, 41]. Typically, a higher threshold is presumed to yield superior label quality, as it assigns pseudo-labels solely to instances where the classifier exhibits a high level of confidence. Conversely, elevating the threshold diminishes the quantity of pseudo-labels, as it leads to the exclusion of instances where the classifier lacks sufficient confidence. Hence causing the dilemma of quality-quantity trade-off.

One possible approach to address the quantity-quality trade-off in SSL is to apply a dynamic threshold, which is dependent on the training progress. This is because the evaluation metric for confident samples is usually not stationary throughout the training process of neural networks. As the model’s predicted probability is subject to the level of over-fitting [16, 30], designing a thresholding function that is dependent on the training process is crucial to the success of SSL algorithms[9, 41]. Intuitively, in the early stage of the training process, where the model has just started to fitting, the threshold should not be set too high to filter out too many samples, and as the model has already well-fitted to the training data, the threshold should be elevated to combat falsely confident instances caused by confirmation bias [4].

For a classifier trained with sufficient accurately labeled data, its prediction $\gamma$ will be made if $P(Y=\gamma|X=\bm{x})>P(Y=s|X=\bm{x})$. However, under the existence of label errors, the fidelity of the classifier can no longer be guaranteed. Recently, Zheng et al. [56] showed that the classifier influenced by the label noise can still have a bounded error rate. We show that in SSL tasks, where the label noise is instance-dependent, we can establish a lower-bound probability for the predictions to be correct through similar derivations.

Recall Assumption 1, we have $\gamma:=\operatorname*{arg\,max}_{i}P(Y=i|X=\bm{x_{u}})$, $s:=\operatorname*{arg\,max}_{i\neq k}P(Y=i|X=\bm{x_{u}})$, $k:=\operatorname*{arg\,max}_{i}\hat{P}(\hat{Y}=i|X=\bm{x_{u}})=\hat{y}_{u}$. And let $\epsilon_{\theta}$ be the estimation error between our estimated noisy class posterior $\hat{P}(\hat{Y}|X)$ and true noisy class posterior $P(\hat{Y}|X)$. We can then formulate our main theorem:

The proof of Theorem 1 is provided in Appendix C. Theorem 1 substantiates that, as our model over-fits to the label error (as $\epsilon_{\theta}$ decreases), and the transition matrix can be successfully estimated, the probability lower-bound of the assigned pseudo-labels are correct will increase asymptotically. This guarantees the quality of the pseudo-labels $\tau(\bm{x_{u}})$ assigned. Note that, $\tau(\bm{x_{u}})$ requires the clean class posterior of unlabeled instances, which can be provably inferred upon the successful estimation of $T(\bm{x})$ and the noisy class posterior [26, 32].

To gain a deeper understanding of Theorems 1, we will try to intuitively understands the outputs of $\tau(\bm{x_{u}})$. Our aim is to examine the behavior of $\tau(\bm{x_{u}})$ in relation to the unlabeled sample $\bm{x_{u}}$, which has a predetermined clean class posterior. If we observe an increase in the sum of column $k$ in the transition matrix, it will result in a corresponding increase in the threshold $\tau(\bm{x_{u}})$. This implies that when $\bm{x_{u}}$ is highly likely to be assigned with an incorrect pseudo-label, $\tau(\bm{x_{u}})$ will assign a higher threshold in order to prevent its premature inclusion of $\{\bm{x_{u}},\hat{y}_{u}\}$ in the training set. Conversely, when $\bm{x_{u}}$ is less likely to be assigned with a incorrect pseudo-label, $\tau(\bm{x_{u}})$ will assign a lower threshold to encourage adding $\{\bm{x_{u}},\hat{y}_{u}\}$ to the training set.

Theorem 1 builds upon the assumption that $T(\bm{x})$ can be successfully identified. Yet, the identification of $T(\bm{x})$ has been a long-standing issue in the field of label noise learning. Fortunately, in SSL, we argue that $T(\bm{x})$ can be provably identified under mild conditions. We will first justify our argument from a theoretical perspective based on the Theorems from Liu et al. [27]. Subsequently, we will also propose the empirical methods for estimating $T(\bm{x})$ from an intuitively understandable aspect in the following section.

We will start by defining the identifiability, we use $\Omega$ to represent an observation space and use $\Theta$ to represent a general parametric space. Then, for a distribution with parameter $\theta^{{}^{\prime}}$, such that $\theta^{{}^{\prime}}\in\Theta$, a model $P_{\theta^{{}^{\prime}}}$ on $\Omega$ can be defined [3, 50]. We further define its identifiability as:

In our case, $\theta^{{}^{\prime}}(\bm{x}):=\{T(\bm{x}),P(Y|X=\bm{x})\}$, i.e., $P_{\theta^{{}^{\prime}}}$ is a distribution defined by the transition probability and clean class posterior. To determine the identifiability of $T(\bm{x})$, we also need to define the term informative noisy labels. Specifically, we have:

Then, we can make the following theorem:

The Theorem 2 is based on Kruskal’s Identifiability Theorem, the proof is provided in the Appendix D. From Theorem 2 and Definition 2, we can conclude that, in SSL, if we have more than three labeled samples per class, transition matrix $T(\bm{x})$ is identifiable, more discussions on this can also be found in Appendix D.

While Theorem 1 provides a theoretical guarantee for the correctness of $\tau(\bm{x_{u}})$, as discussed in section 2.4, SSL algorithms can benefit from non-constant thresholds [9, 41]. Here we define the dynamic threshold $\kappa_{t}$ at iteration $t$ from the relative confidence threshold (RT) in AdaMatch [9]:

where $n$ is the number of labeled samples, and $\beta$ is a fixed discount factor. Subsequently, we present the instance-dependent threshold function at iteration $t$:

Note that this estimation process requires the clean class posterior, which can be estimated or approximated using a transition matrix via importance re-weighting [26, 46] or loss correction [32, 45], details will be introduced in the following section. We also remark here that a less strict instance-dependent version of the threshold function can be used with the class-dependent transition matrix [32, 46, 52], which can lead to better empirical results under certain cases, it is also important to note that even under class-dependent transition matrix, the threshold function is still instance-dependent, as the noise class posterior are instance-dependent.

Now we will introduce a piratical method for estimating $T(\bm{x})$ in SSL. Our approach involves approximating the label noise transition pattern using a Deep Neural Network. As we recall from Equation 1, $T(\bm{x})$ can be described as a mapping function $T:X\rightarrow\mathbb{R}^{|Y|\times|Y|}$, since we already know that, in general cases, $T(\bm{x})$ is identifiable in SSL, we only need to find the correct mapping function. In addition, since we have clean label $Y_{l}$ for $X_{l}$, and we also have the noisy pseudo-labels $\hat{Y}_{l}$ for $X_{l}$, this enables us to directly fit a model to approximate $T(\bm{x})$. Therefore, we want our transition matrix estimator, parameterized by $\theta^{{}^{\prime}}$, to approximate the label noise transition process at every iteration $t$:

The above approximation holds since label noise is assumed to be i.i.d, therefore both labeled and unlabeled samples share the same noise transition process. As we can estimate the noisy class posterior for labeled samples, we can therefore collect distribution $D:=\{X_{l},Y_{l},\hat{P}(\hat{Y}|X=\bm{x_{l}})\}$. Observing Equation 6, we can design following objective for $\theta^{{}^{\prime}}$ to minimize:

Where $\bm{y_{l}}$ is the one-hot vector for the label of labeled samples, thus $\bm{y_{l}}\cdot\hat{T}(\bm{x_{l}})$ is equivalent to finding the class-conditional noise class posterior $\hat{P}(\hat{Y_{l}}=j|Y_{l}=i,X_{l}=\bm{x_{l}};\theta^{{}^{\prime}})$. $\bm{\hat{y}_{l}}$ is the one-hot noisy pseudo-label of $\bm{x_{l}}$, minimizing $L_{D}(\theta^{{}^{\prime}})$ will result $\hat{T}(\bm{x_{l}};\theta^{{}^{\prime}})$ approximate $T(\bm{x})$. As shown in Figure 2, $\hat{f}_{\theta^{{}^{\prime}}}$ will be trained in parallel to the main classifier and updated in every epoch.

Notably, the estimator for the transition matrix in InstanT is not constrained to one specific method, there has been a wide versatile of $T$ estimator in the field of label noise learning [25, 45, 51], we have incorporated some of them into the implementation of InstanT, indicating the good extensibility of InstanT.

When the prediction of the classifier becomes imbalanced, Distribution Alignment (DA) is used to modulate the prediction so that the poorly predicted class will not be overlooked completely [7, 9, 20, 42]. This is achieved by estimating the prior of the pseudo-label $P(\hat{Y})$ during training, and setting a clean class prior $\hat{P}(Y)$, which is usually assumed to be uniformly distributed. The distribution alignment process can be described as $\hat{P}(\hat{Y}=j|X=\bm{x_{u}})=\mathrm{Norm}(\hat{P}(\hat{Y}=j|X=\bm{x_{u}})P(Y=j)/P(\hat{Y}=j))$, where $\mathrm{Norm}$ is a total-sum scaling. Therefore, if the distribution of $\hat{Y}$ is severely imbalanced, DA will force the prediction for the minority class to be scaled up, and the prediction for the over-populated class to be scaled down.

While the classifier trained with incorrect pseudo-labels is subject to the influence of noisy supervision, in order to satisfy Theorem 1, the estimated softmax predictions from $\hat{f}_{\theta}$ must approximate the clean class posterior [56]. As we have already demonstrated that the transition matrix can be identified in standard SSL setting, in this part, we will show how to infer clean class posterior from noisy predictions and transition matrix, by utilizing forward correction [32]. Specifically, let $\ell_{\psi}$ be a proper composite loss [33] (e.g. softmax cross-entropy loss), forward correction is defined as:

where $\psi$ is an invertible link function. It has been proven that minimizing the forward loss with an accurately estimated transition matrix is equivalent to minimizing the loss defined over clean latent pseudo-labels [32]. Therefore, minimizing $\ell^{\rightarrow}_{\psi}$ will let the softmax prediction of classifier $\hat{f}_{\theta}$ approximate the clean class posterior.

Lastly, we provide an overview of the training objective of InstanT. We employ the widely adopted consistency regularization loss [36, 47], which assumes a well-learned and robust model should generate consistent predictions for random perturbations of a given instance. Previous methods have commonly employed augmentation techniques to introduce perturbations. The training loss of classifier $\hat{f}_{\theta}$ consists of two parts: supervised loss $L_{D_{s}}(\theta)$ and unsupervised loss $L_{D_{u}}(\theta)$. $L_{D_{s}}(\theta)$ is calculated by the labeled samples, specifically, we have:

where $n$ is the number of labeled samples, $\bm{y_{l}}$ is the one-hot label for $\bm{x_{l}}$, and $\mathbb{W}$ is a weak augmentation function [36, 47], and $\ell$ is the cross-entropy loss function. Unsupervised loss $L_{D_{u}}(\theta)$ is calculated by the unlabeled samples $X_{u}$ and their predicted pseudo-labels $\hat{Y}_{u}$, which can be defined as:

where $m$ is the number of unlabeled instances, $\bm{\hat{y}_{u}}$ is the one-hot pseudo-label for $\bm{x_{u}}$, and $\mathbb{S}$ is a strong augmentation function [7, 14, 15]. $\mathbbm{1}$ is an indicator function that filters unlabeled instances using $\tau(\bm{x_{u}})_{t}$. Combining the supervised and unsupervised loss, we then have the overall training objective:

where $\lambda$ is used to control the influence of the unsupervised loss.

We use three benchmark datasets for evaluating the performances of InstanT, they are: CIFAR-10, CIFAR-100 [21], and STL-10 [13]. CIFAR-10 has 10 classes and 6,000 samples per class. CIFAR-100 has 100 classes and 600 samples per class. STL-10 has 10 classes and 500 labeled samples per class, 100,000 unlabeled instances in total. For each dataset, we set varying numbers of labeled samples to create different levels of difficulty. Following recently more challenging settings [10, 41], where the labeled samples could be extremely limited, we set the number of labeled samples per class on CIFAR-10 as $\{1,4,25\}$, for CIFAR-100, we set as $\{2,4,25\}$, for STL-10, we set as $\{1,4,10\}$.

To ensure fair comparison between our method and all baselines, and to allow simple reproduction of our experimental results, we implemented InstanT and conducted all experiments within USB (Unified SSL Benchmark) framework [40]. To improve the training efficiency, e.g. faster convergence, we use pre-trained ViT as the backbone model for all baselines with the same hyper-parameters in part \@slowromancapi@. We use AdamW [28] as the default optimizer, where the learning rate is set as $5e-4$ for CIFAR-10/100, $1e-4$ for STL-10 [40]. The total training iterations $K$ are set as 204,800 for all datasets. The training batch size is set as 8 for all datasets. For a more comprehensive evaluation of our proposed method, we also conduct experiments with Wide ResNet [53] trained from scratch, the detailed settings are aligned with existing works [7, 9, 36, 47, 48, 54], these results are summarized in part \@slowromancapii@. We select a range of popular baseline methods to evaluate against InstanT, which includes Pseudo-Label (PL) [23], MeanTeacher (MT) [37], VAT [29], MixMatch [8], UDA [47], FixMatch [36], Dash [48], FlexMatch [54] and AdaMatch [9]. More comprehensive setting details, including full details of hyper-parameters, can be found in Appendix A.

In this section, we will be verifying the effects of each component of InstanT, specifically, we will focus on evaluating the parts that we adapted from existing works, and determine how many performance improvements are attributed to our instance-dependent thresholds. Results of this ablation study are summarized in Table 4, where all experiments are averaged over three random seeds and ran on STL-10(40) using the setting of part \@slowromancapi@. First, we observe that InstanT-\@slowromancapi@ removed both Distribution Alignment (DA) and relative thresholds (RT), which makes it equivalent to adding $\tau(\bm{x_{u}})$ on top of the fixed threshold of FixMatch. Notably, this also brings a significant improvement over FixMatch for over 2%, which further verifies the effectiveness of our proposed instance-dependent thresholds. Simply removing RT or DA will also cause a performance drop, which is aligned with the results from AdaMatch [9].