  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 $\lambda$ affects the gen-error under both scenarios. As
$\lambda$ 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 $\lambda$ increases.
