How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?

Let $S_{\mathrm{l}}=\{\mathbf{Z}_{i}\}_{i=1}^{n}=\{(\mathbf{X}_{i},Y_{i})\}_{i=1}^{n}$ be the labeled training dataset, where $\mathbf{X}_{i}\in\mathcal{X}=\mathbb{R}^{d}$ is the data feature, $Y_{i}\in\mathcal{Y}=[K]$ is the class label and each pair of $\mathbf{Z}_{i}=(\mathbf{X}_{i},Y_{i})\in\mathcal{X}\times\mathcal{Y}=\mathcal{Z}$ is independently and identically distributed (i.i.d.) from $P_{\mathbf{Z}}=P_{\mathbf{X},Y}\in\mathcal{P}(\mathcal{Z})$. Conditioned on $\mathbf{X}_{i}$, each label $Y_{i}$ is i.i.d. from $P_{Y|\mathbf{X}}$. Let $S_{\mathrm{u}}=\{\mathbf{X}_{i}\}_{i=n+1}^{n+m}$ be the unlabeled training dataset. For all $i\in[n+m]$, each $\mathbf{X}_{i}$ is i.i.d. from $P_{\mathbf{X}}\in\mathcal{P}(\mathcal{X})$. Based on the labeled dataset $S_{\mathrm{l}}$, a pseudo-labeling method assigns a pseudo-label $\hat{Y}_{i}$ to each $\mathbf{X}_{i}\in S_{\mathrm{u}}$ and $\hat{Y}_{i}$ is drawn conditionally i.i.d. from $P_{\hat{Y}|\mathbf{X},S_{\mathrm{l}}}$. Let the pseudo-labeled data point be $\hat{\mathbf{Z}}_{i}=(\mathbf{X}_{i},\hat{Y}_{i})$ and the pseudo-labeled dataset be $\hat{S}_{\mathrm{u}}=\{\hat{\mathbf{Z}}_{i}\}_{i=n+1}^{n+m}$. For any labeled and pseudo-label datasets, we use $P_{S_{\mathrm{l}}}$, $P_{\hat{S}_{\mathrm{u}}}$ and $P_{S_{\mathrm{l}},\hat{S}_{\mathrm{u}}}$ to denote the joint distributions of the data samples in $S_{\mathrm{l}}$, $\hat{S}_{\mathrm{u}}$, and $S_{\mathrm{l}}\cup\hat{S}_{\mathrm{u}}$, respectively. Note that $P_{S_{\mathrm{l}}}=P_{\mathbf{Z}}^{\otimes n}$.

Let $\mathbf{w}\in\mathcal{W}$ denote the output hypothesis. In semi-supervised learning, one considers the empirical risk based on both the labeled and unlabeled data. In this paper, by fixing a mixing weight $\eta\in\mathbb{R}_{+}$, for any loss function $l:\mathcal{W}\times\mathcal{Z}\to\mathbb{R}_{+}$, the total empirical risk is the $\eta$-weighted sum of the empirical risks of the labeled and pseudo-labeled data (McLachlan, 2005; Chapelle et al., 2006)

where $L_{\mathrm{E}}(\mathbf{w},S_{\mathrm{l}}):=\frac{1}{n}\sum_{i=1}^{n}l(\mathbf{w},\mathbf{Z}_{i})$ and $L_{\mathrm{E}}(\mathbf{w},\hat{S}_{\mathrm{u}}):=\frac{1}{m}\sum_{i=n+1}^{n+m}l(\mathbf{w},\hat{\mathbf{Z}}_{i})$. Note that, by normalizing the weight $\eta$, minimizing the empirical risk $L_{\mathrm{E}}(\mathbf{w},S_{\mathrm{l}},\hat{S}_{\mathrm{u}})$ is equivalent to minimizing

The population risk under the true data distribution is

Under the i.i.d. assumption, such a definition reduces to $\mathbb{E}_{S_{\mathrm{l}}\sim P_{S_{\mathrm{l}}}}\big{[}L_{\mathrm{E}}(\mathbf{w},S_{\mathrm{l}})\big{]}=\mathbb{E}_{\mathbf{Z}\sim P_{\mathbf{Z}}}\big{[}l(\mathbf{w},\mathbf{Z})\big{]}$.

Any SSL algorithm can be characterized by a conditional distribution $P_{\mathbf{W}|S_{\mathrm{l}},\hat{S}_{\mathrm{u}}}$, which is a stochastic map from the labeled dataset $S_{\mathrm{l}}$, the pseudo-labeled dataset $\hat{S}_{\mathrm{u}}$ to the output hypothesis $\mathbf{W}$. For any training datasets $S_{\mathrm{l}},\hat{S}_{\mathrm{u}}$ and any SSL algorithm $P_{\mathbf{W}|S_{\mathrm{l}},\hat{S}_{\mathrm{u}}}$, the expected gen-error is defined as the expected gap between the population risk and the empirical risk of the labeled data $S_{\mathrm{l}}$, i.e.,

which measures the extent to which the algorithm overfits to the labeled training data.

In particular, we consider the Gibbs algorithm (also known as the Gibbs posterior (Catoni, 2007)) to model a pseudo-labeling-based SSL algorithm. Given any $(S_{\mathrm{l}},\hat{S}_{\mathrm{u}})$, the $(\alpha,\pi(\mathbf{w}),\bar{L}_{\mathrm{E}}(\mathbf{w},S_{\mathrm{l}},\hat{S}_{\mathrm{u}}))$-Gibbs algorithm (Gibbs, 1902; Jaynes, 1957) is

where $\alpha\geq 0$ is the “inverse temperature”, $\Lambda_{\alpha,\eta}(S_{\mathrm{l}},\hat{S}_{\mathrm{u}})\!=\!\int\pi(\mathbf{w})\exp(-\alpha\bar{L}_{\mathrm{E}}(\mathbf{w},S_{\mathrm{l}},\hat{S}_{\mathrm{u}}))\,\mathrm{d}\mathbf{w}$ is the partition function and $\pi(\mathbf{w})$ is the prior of $\mathbf{w}$. We provide more motivations for the Gibbs algorithm model in Appendix A.

Our goal—relying on the characterization of $P_{\mathbf{W}|S_{\mathrm{l}},\hat{S}_{\mathrm{u}}}^{\alpha}$—is to precisely quantify the gen-error in (4) as a function of various information-theoretic quantities.

If $P$ is absolutely continuous with respect to $Q$ and vice versa, let the symmetrized KL-divergence (also known as Jeffrey’s divergence (Jeffreys, 1946)) be defined as $D_{\mathrm{SKL}}(P\|Q):=D(P\|Q)+D(Q\|P)$, where $D$ is the Kullback–Leibler (KL) divergence (Cover, 1999).

For random variables $X$ and $Y$ with joint distribution $P_{X,Y}$, the mutual information is $I(X;Y)=D(P_{X,Y}\|P_{X}\otimes P_{Y})$ and the Lautum information (Palomar and Verdú, 2008) is $L(X;Y)=D(P_{X}\otimes P_{Y}\|P_{X,Y})$. Similarly, the symmetrized KL information between $X$ and $Y$ (Aminian et al., 2015) is defined as $I_{\mathrm{SKL}}(X;Y):=D_{\mathrm{SKL}}(P_{X,Y}\|P_{X}\otimes P_{Y})=I(X;Y)+L(X;Y)$. We define the conditional symmetrized KL information as $I_{\mathrm{SKL}}(X;Y|Z):=I(X;Y|Z)+L(X;Y|Z)$.

One of our main results offers an exact closed-form information-theoretic expression for the gen-error of the $(\alpha,\pi(\mathbf{w}),\bar{L}_{\mathrm{E}}(\mathbf{w},S_{\mathrm{l}},\hat{S}_{\mathrm{u}}))$-Gibbs algorithm in terms of the symmetrized KL information defined above.

The proof of Theorem 1 is provided in Appendix B, where we also show that by letting $\eta\to 0$, the result reduces to that for supervised learning (SL). In addition, we can even extend Theorem 1 to SSL based on other methods, e.g., entropy minimization (Amini and Gallinari, 2002; Grandvalet et al., 2005). This corollary is provided in Section C.

Theorem 1 can also be applied to derive novel bounds on the expected gen-error of the Gibbs algorithm as follows.

The proof and more discussions are provided in Appendix D. In fact, we can further explore how the gen-error depends on the information that the output hypothesis contains about the labeled and unlabeled datasets by writing (see Appendix E)

From Theorem 1 and (3.2), we observe that for any $(\eta,\alpha)$, given $\hat{S}_{\mathrm{u}}$, as the dependency (or the information shared) between $\mathbf{W}$ and $S_{\mathrm{l}}$ decreases, the expected gen-error decreases, and the algorithm is less likely to overfit to the training data. This intuition dovetails with the results for supervised learning in Xu and Raginsky (2017), Russo and Zou (2019) and Aminian et al. (2021a). However, the difference here is that the quantities are conditioned on the pseudo-labeled data $\hat{S}_{\mathrm{u}}$, which reflects the impact of SSL.

Together with Proposition 1, we can observe that the gen-error is also dependent on the information shared between the input labeled and pseudo-labeled data. If the mutual information $I(\hat{S}_{\mathrm{u}};S_{\mathrm{l}})$ decreases, the expected gen-error is likely to decrease as well. This implies that pseudo-labels highly dependent on the labeled dataset may not be beneficial in terms of the generalization performance of an algorithm. In fact, in our subsequent example in Section 4, we exactly quantify the shared information using the cross-covariance between the labeled and pseudo-labeled data. This result sheds light on the future design of pseudo-labeling methods.

We can also build upon Theorem 1 and Xu and Raginsky (2017, Theorem 1) to provide distribution-free upper and lower bounds of the gen-error in (5). We next state an informal version of such bounds (the formal version and the proof are provided in Appendix G). Throughout this section, we let the mixing weight $\eta=\lambda=m/n$.

Recall that for SL with $n$ labeled data, the expected gen-error is of order $O(\frac{1}{n})$ Aminian et al. (2021a, Theorem 2). This can be naturally extended to SL with $n+m$ labeled data, leading to the expected gen-error behaving as $O(\frac{1}{n+m})$. Compared to the SL case, we see that using the pseudo-labeled data may degrade the convergence rate of the expected gen-error and the extent to which it degrades depends on $\gamma_{\alpha,\lambda}$, which captures the impact of the amount of information shared among the output hypothesis, the input labeled and unlabeled data as well as the ratio $\lambda$. If $\gamma_{\alpha,\lambda}$ is small, it implies $I(\hat{S}_{\mathrm{u}};S_{\mathrm{l}})$ is small and $I(\mathbf{W};S_{\mathrm{l}}|\hat{S}_{\mathrm{u}})$ is large, which leads to a tight upper bound.

If we fix $0<\lambda<\infty$ and assume $\hat{S}_{\mathrm{u}}$ is independent of $S_{\mathrm{l}}$, then $\gamma_{\alpha,\lambda}=0$ and

which coincides with the result of transfer learning in Bu et al. (2022, Remark 3) and corresponds to the analysis of (8). Although it appears that using independent pseudo-labeled data $\hat{S}_{\mathrm{u}}$ does not degrade the convergence rate of the expected gen-error, it may affect the excess risk or the test accuracy, which taken in unison, represents the performance of a learning algorithm. The definition and further analysis of the excess risk is provided in Section 5.1.1.

When $\lambda\to 0$, the gen-error converges to that of SL with $n$ labeled data and the distribution-free upper bound is of order $O(\frac{1}{n})$, given in Aminian et al. (2021a, Theorem 2).

For any $(\mathbf{X}_{i},Y_{i})\in S_{\mathrm{l}}$ and $i\in[n]$, we assume that $Y_{i}\in\{-1,+1\}$, $\mathbb{E}[\mathbf{X}_{i}|Y_{i}=1]=\bm{\mu}$, $\mathbb{E}[\mathbf{X}_{i}|Y_{i}=-1]=-\bm{\mu}$, $\|\bm{\mu}\|_{2}=1$ and $\operatorname{Cov}[Y_{i}\mathbf{X}_{i}]=\sigma^{2}\mathbf{I}_{d}$. Any $\mathbf{X}\in S_{\mathrm{u}}$ is drawn i.i.d. from the same distribution as $\mathbf{X}_{i}$. Consider the problem of learning $\bm{\mu}$ using $S_{\mathrm{l}}$ and $\hat{S}_{\mathrm{u}}$. We adopt the mean-squared loss $l(\mathbf{w},\mathbf{z})=\|\mathbf{w}-y\mathbf{x}\|_{2}^{2}$ and assume the prior $\pi(\mathbf{w})$ is uniform on $\mathcal{W}$. Based on $\mathbf{W}_{0}$ learned from the labeled dataset $S_{\mathrm{l}}$ (e.g., $\mathbf{W}_{0}=\frac{1}{n}\sum_{i=1}^{n}Y_{i}\mathbf{X}_{i}$), we assign a pseudo-label to each $X_{i}\in S_{\mathrm{u}}$ as $\hat{Y}_{i}$ (e.g. $\hat{Y}_{i}=\operatorname{sgn}(\mathbf{W}_{0}^{\top}\mathbf{X}_{i})$) and let $\bm{\mu}^{\prime}=\mathbb{E}[\hat{Y}_{i}\mathbf{X}_{i}]$. Let us construct $S_{\mathrm{l}}^{\prime}=\{Y_{i}\mathbf{X}_{i}\}_{i=1}^{n}$ and $\hat{S}_{\mathrm{u}}^{\prime}=\{\hat{Y}_{i}\mathbf{X}_{i}\}_{i=n+1}^{n+m}$. The empirical risk is given by (cf. (2) by replacing $S_{\mathrm{l}},\hat{S}_{\mathrm{u}}$ with $S_{\mathrm{l}}^{\prime},\hat{S}_{\mathrm{u}}^{\prime}$)

The expected gen-error is equal to the right-hand side of (5) by replacing $S_{\mathrm{l}},\hat{S}_{\mathrm{u}}$ with $S_{\mathrm{l}}^{\prime},\hat{S}^{\prime}_{\mathrm{u}}$.

The $(\alpha,\pi(\mathbf{W}),\bar{L}_{\mathrm{E}}(\mathbf{W},S_{\mathrm{l}}^{\prime},\hat{S}_{\mathrm{u}}^{\prime}))$-Gibbs algorithm is given by the following Gibbs posterior distribution

where $\sigma^{2}_{\mathrm{l},\mathrm{u}}=\frac{1}{2\alpha}$ and

Details are provided in Appendix H. With this posterior Gaussian distribution $P_{\mathbf{W}|S_{\mathrm{l}}^{\prime},\hat{S}_{\mathrm{u}}^{\prime}}^{\alpha}$, the expected gen-error in Theorem 1 can be exactly computed as follows

where $i\in[n]$ and $j\in[n+1:n+m]$ run over the labeled and unlabeled datasets respectively. From the definition of the expected gen-error in (4), we obtain the same result, which corroborates the characterization of the expected gen-error in Theorem 1. See Appendix H for details.

Note that the second term in (12) is the trace of the cross-covariance between the labeled and pseudo-labeled data sample, i.e., for any $i\in[n]$ and $j\in[n+1:n+m]$,

This result shows that for any fixed $(n,m)$, the expected gen-error decreases when the trace of the cross-covariance decreases, which corroborates our analyses in Section 3.2.

To futher study the effect of the pseudo-labeling method and the ratio $\lambda=m/n$, in this mean estimation example, we consider the class-conditional feature distribution of $\mathbf{X}_{i}|Y_{i}\sim\mathcal{N}(Y_{i}\bm{\mu},\sigma^{2}\mathbf{I}_{d})$ for any $i\in[n+m]$. Let $S_{\mathrm{l}}^{\prime(n+m)}$ be a dataset with $n+m$ independent copies of $Y\mathbf{X}\in S_{\mathrm{l}}^{\prime}$. Similarly to (12), for the supervised $(\alpha,\pi(\mathbf{w}_{\mathrm{SL}}^{(n)}),L_{\mathrm{E}}(\mathbf{w}_{\mathrm{SL}}^{(n)},S_{\mathrm{l}}^{\prime}))$-Gibbs algorithm and the supervised $(\alpha,\pi(\mathbf{w}_{\mathrm{SL}}^{(n+m)}),L_{\mathrm{E}}(\mathbf{w}_{\mathrm{SL}}^{(n+m)},S_{\mathrm{l}}^{\prime(n+m)}))$-Gibbs algorithm, the expected gen-errors are respectively given by (see details in Appendix H.1)

Let $\overline{\mathrm{gen}}_{\mathrm{SSL}}$ denote $\overline{\mathrm{gen}}(P_{\mathbf{W}|S_{\mathrm{l}},\hat{S}_{\mathrm{u}}}^{\alpha},P_{S_{\mathrm{l}},\hat{S}_{\mathrm{u}}})$ for brevity. By comparing $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n)}$ and $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}$, we observe that:

1. 1.

   If $\mathbb{E}\big{[}(Y_{i}\mathbf{X}_{i}-\bm{\mu})^{\top}(\hat{Y}_{j}\mathbf{X}_{j}-\bm{\mu}^{\prime})\big{]}<0$, then $\overline{\mathrm{gen}}_{\mathrm{SSL}}<\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}$, which means that SSL with such pseudo-labeling method even has better generalization performance than SL with $n+m$ labeled data. This is the most desirable case in terms of the generalization error;

2. 2.

   If $\mathbb{E}\big{[}(Y_{i}\mathbf{X}_{i}-\bm{\mu})^{\top}(\hat{Y}_{j}\mathbf{X}_{j}-\bm{\mu}^{\prime})\big{]}>\frac{\sigma^{2}d}{n}$, then $\overline{\mathrm{gen}}_{\mathrm{SSL}}>\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n)}$. This implies that if the cross-covariance between the labeled and pseudo-labeled data is larger than a certain threshold, the pseudo-labeling method does not help to improve the generalization performance;

3. 3.

   If $0\leq\mathbb{E}\big{[}(Y_{i}\mathbf{X}_{i}-\bm{\mu})^{\top}(\hat{Y}_{j}\mathbf{X}_{j}-\bm{\mu}^{\prime})\big{]}\leq\frac{\sigma^{2}d}{n}$, then $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}\leq\overline{\mathrm{gen}}_{\mathrm{SSL}}\leq\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n)}$. This implies that if the cross-covariance is sufficiently small, pseudo-labeling improves the generalization error.

The value of $\mathbb{E}\big{[}(Y_{i}\mathbf{X}_{i}-\bm{\mu})^{\top}(\hat{Y}_{j}\mathbf{X}_{j}-\bm{\mu}^{\prime})\big{]}$ also depends on the ratio $\lambda$. Next, to study the effect of $\lambda$, let the initial hypothesis learned from the labeled data $S_{\mathrm{l}}$ be $\mathbf{W}_{0}=\frac{1}{n}\sum_{i=1}^{n}Y_{i}\mathbf{X}_{i}\sim\mathcal{N}(\bm{\mu},\frac{\sigma^{2}}{n}\mathbf{I}_{d})$ and the pseudo-label for any $\mathbf{X}_{i}\in S_{\mathrm{u}}$ be $\hat{Y}_{i}=\operatorname{sgn}(\mathbf{W}_{0}^{\top}\mathbf{X}_{i})$.

Inspired by the derivation techniques in He et al. (2022), we can rewrite the expected gen-error in (12) as

where $E_{n}=\mathbb{E}[\tilde{g}J_{\sigma}(\gamma_{n}^{\prime})+\|\bm{\mu}^{\perp}\|_{2}K_{\sigma}(\gamma_{n}^{\prime})]$, $\tilde{g}\sim\mathcal{N}(0,1)$, $\bm{\mu}^{\perp}\sim\mathcal{N}(\textbf{0},\mathbf{I}_{d}-\bm{\mu}\bm{\mu}^{\top})$, $J_{\sigma}$ and $K_{\sigma}$ are functions with domain $[-1,1]$, and $\gamma_{n}^{\prime}\in[-1,1]$ is a sequence of correlation coefficients. Details are presented in Appendix H.2, where we also prove that $E_{n}=O(d)$ and $E_{n}\geq 0$, which means that we always have $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}\leq\overline{\mathrm{gen}}_{\mathrm{SSL}}$ here. Furthermore, we observe that $E_{n}$ does not depend on $m$ and thus, (13) converges to $2E_{n}$ when we fix $n$, and let $\lambda\to\infty$.

In Figure 1, we numerically plot $\overline{\mathrm{gen}}_{\mathrm{SSL}}$ by varying $\lambda$ and compare it with $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n)}$ and $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}$ for different values of noise level $\sigma$, and number of labeled data samples $n$. Under different choices of $\sigma$, we observe that $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}\leq\overline{\mathrm{gen}}_{\mathrm{SSL}}\leq\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n)}$. Moreover, the gen-error of SSL monotonically decreases as $\lambda$ increases, showing obvious improvement compared to $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n)}$. However, there exists a gap $\frac{2\lambda E_{n}}{1+\lambda}$ between $\overline{\mathrm{gen}}_{\mathrm{SSL}}$ and $\overline{\mathrm{gen}}_{\mathrm{SL}}^{(n+m)}$. For $n$ large enough (e.g., $n=100$) or noise level small enough (e.g., $\sigma=0.5$), this gap is almost negligible, which means pseudo-labeling yields comparable generalization performance as the SL when all the samples are labeled.

We have shown that the generalization error decreases as the information shared between the input labeled and pseudo-labeled data (represented by the mutual information $I(\hat{S}_{\mathrm{u}};S_{\mathrm{l}})$ or the cross-covariance term $\operatorname{tr}(\operatorname{Cov}[Y_{i}\mathbf{X}_{i},\hat{Y}_{j}\mathbf{X}_{j}])$ in the mean estimation example) decreases. This result serves as a guideline for choosing an appropriate pseudo-labeling method. For example, if we are given a set of pseudo-labeling functions $\{f_{i}\}_{i=1}^{C}$ with $f_{i}:\mathcal{X}\to\mathcal{Y}$, we can choose the best one $f_{i^{*}}$ that yields the minimum mutual information $I(\hat{S}_{\mathrm{u}};S_{\mathrm{l}})$. To make our ideas more concrete, for the mean estimation example that we have been discussing thus far, assume that the pseudo-labeling functions $\hat{Y}=\operatorname{sgn}(\mathbf{W}_{0}^{\top}\mathbf{X})\mathbf{1}_{\{|\mathbf{W}_{0}^{\top}\mathbf{X}|\geq T\}}$ (where $\mathbf{X}\in S_{\mathrm{u}}$) are indexed by various “confidence” thresholds $T\in\mathbb{R}_{+}$ ($T$ plays the role of the index $i$ in $\{f_{i}\}_{i=1}^{C}$). For instance, let us consider the case where $n=5$, $\sigma=1$ (cf. Figure 1(b)). As shown in Figure 2, one can choose the threshold $T$ that minimizes $\operatorname{tr}(\operatorname{Cov}[Y_{i}\mathbf{X}_{i},\hat{Y}_{j}\mathbf{X}_{j}])$ for $(\mathbf{X}_{i},Y_{i})\in S_{\mathrm{l}}$ and $\mathbf{X}_{j}\in S_{\mathrm{u}}$. From this figure, we observe that $T\geq 7$ approximately minimizes $\operatorname{tr}(\operatorname{Cov}[Y_{i}\mathbf{X}_{i},\hat{Y}_{j}\mathbf{X}_{j}])$ and hence, the generalization error. We have thus exhibited a concrete way to choose one pseudo-labeling method from a given family of methods via our characterization of generalization error.