How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?
This work offers theoretical insights for researchers in machine learning to better understand and choose pseudo-labeling methods, though it is incremental as it builds on existing SSL and information theory frameworks.
The paper tackles the problem of characterizing the generalization error in semi-supervised learning with pseudo-labeling using the Gibbs algorithm, providing exact expressions and bounds that reveal the error depends on shared information between labeled and pseudo-labeled data, with examples showing how the ratio of unlabeled to labeled data affects error in mean estimation and logistic regression.
We provide an exact characterization of the expected generalization error (gen-error) for semi-supervised learning (SSL) with pseudo-labeling via the Gibbs algorithm. The gen-error is expressed in terms of the symmetrized KL information between the output hypothesis, the pseudo-labeled dataset, and the labeled dataset. Distribution-free upper and lower bounds on the gen-error can also be obtained. Our findings offer new insights that the generalization performance of SSL with pseudo-labeling is affected not only by the information between the output hypothesis and input training data but also by the information {\em shared} between the {\em labeled} and {\em pseudo-labeled} data samples. This serves as a guideline to choose an appropriate pseudo-labeling method from a given family of methods. To deepen our understanding, we further explore two examples -- mean estimation and logistic regression. In particular, we analyze how the ratio of the number of unlabeled to labeled data $λ$ affects the gen-error under both scenarios. As $λ$ increases, the gen-error for mean estimation decreases and then saturates at a value larger than when all the samples are labeled, and the gap can be quantified {\em exactly} with our analysis, and is dependent on the \emph{cross-covariance} between the labeled and pseudo-labeled data samples. For logistic regression, the gen-error and the variance component of the excess risk also decrease as $λ$ increases.