text: Semi-supervised learning (SSL) uses unlabeled data for training and has been shown to greatly improve performances when compared to a supervised approach on the labeled data available. This claim depends both on the amount of labeled data available and on the algorithm used. In this paper, we compute analytically the gap between the best fully-supervised approach on labeled data and the best semi-supervised approach using both labeled and unlabeled data. We quantify the best possible increase in performance obtained thanks to the unlabeled data, i.e. we compute the accuracy increase due to the information contained in the unlabeled data. Our work deals with a simple high-dimensional Gaussian mixture model for the data in a Bayesian setting. Our rigorous analysis builds on recent theoretical breakthroughs in high-dimensional inference and a large body of mathematical tools from statistical physics initially developed for spin glasses.
  @cite_18: We observe a training set Q composed of l labeled samples (X sub 1 , spl theta sub 1 ),...,(X sub l , spl theta sub l ) and u unlabeled samples X sub 1 ',...,X sub u ' . The labels spl theta sub i are independent random variables satisfying Pr spl theta sub i =1 = spl eta , Pr spl theta sub i =2 =1- spl eta . The labeled observations X sub i are independently distributed with conditional density f sub spl theta i ( spl middot ) given spl theta sub i . Let (X sub 0 , spl theta sub 0 ) be a new sample, independently distributed as the samples in the training set. We observe X sub 0 and we wish to infer the classification spl theta sub 0 . In this paper we first assume that the distributions f sub 1 ( spl middot ) and f sub 2 ( spl middot ) are given and that the mixing parameter is unknown. We show that the relative value of labeled and unlabeled samples in reducing the risk of optimal classifiers is the ratio of the Fisher informations they carry about the parameter spl eta . We then assume that two densities g sub 1 ( spl middot ) and g sub 2 ( spl middot ) are given, but we do not know whether g sub 1 ( spl middot )=f sub 1 ( spl middot ) and g sub 2 ( spl middot )=f sub 2 ( spl middot ) or if the opposite holds, nor do we know spl eta . Thus the learning problem consists of both estimating the optimum partition of the observation space and assigning the classifications to the decision regions. Here, we show that labeled samples are necessary to construct a classification rule and that they are exponentially more valuable than unlabeled samples.
  @cite_20: 
  @cite_3: We provide the first information theoretical tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our work bridges recent theoretical breakthroughs in detection of latent community structure without nodes covariates and a large body of empirical work using diverse heuristics for combining node covariates with graphs for inference. The tightness of our analysis implies in particular, the information theoretic necessity of combining the different sources of information. Our analysis holds for networks of large degrees as well as for a Gaussian version of the model.
summary: To the best of our knowledge, there are much fewer theoretical works dealing with a semi-supervised setting. @cite_18 studies a mixture model where the estimation problem is essentially reduced to the one of estimating the mixing parameter and shows that the information content of unlabeled examples decreases as classes overlap. More closely related to our work, @cite_3 provides the first information theoretic tight analysis for inference of latent community structure given a dense graph along with high dimensional node covariates, correlated with the same latent communities. @cite_20 studies a class of graph-oriented semi-supervised learning algorithms in the limit of large and numerous data similar to our setting.