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_2: We consider the high-dimensional inference problem where the signal is a low-rank matrix which is corrupted by an additive Gaussian noise. Given a probabilistic model for the low-rank matrix, we compute the limit in the large dimension setting for the mutual information between the signal and the observations, as well as the matrix minimum mean square error, while the rank of the signal remains constant. This allows to locate the information-theoretic threshold for this estimation problem, i.e. the critical value of the signal intensity below which it is impossible to recover the low-rank matrix.
  @cite_27: We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of m points in n dimensions, n,m → ∞ and α = m n stays finite. Using exact but non-rigorous methods from statistical physics, we determine the critical value of α and the distance between the clusters at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance. We also determine the accuracy achievable by the Bayes-optimal estimation algorithm. In particular, we find that when the number of clusters is sufficiently large, r > 4+2√α, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed.
  @cite_10: 
  @cite_17: Estimating the density of data generated by Gaussian mixtures, using the maximum-likelihood criterion, is investigated. Solving the statistical mechanics of this problem we evaluate the quality of the estimation as a function of the number of data points, P= N, N being the dimensionality of the points, in the limit of large N. Below a critical value of , the estimated density consists of Gaussian centers that have zero overlap with the structure of the true mixture. We show numerically that estimating the centers by slowly reducing the estimated Gaussian width yields a good agreement with the theory even in the presence of many local minima.
summary: Using exact but non-rigorous methods from statistical physics, @cite_17 @cite_27 determines the critical values for @math and @math at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance. Rigorous results on this model are given in @cite_10 where bounds on the critical values are obtained. The precises thresholds were then determined in @cite_2 . Our analysis builds on the techniques derived in this last reference with two main modifications: additional work is required to compute the classification accuracy (as opposed to the mean squared error) and to incorporate the side information.