This paper presents a discussion on semi-supervised learning of probabilistic mixture model classifiers for face detection. We present a theoretical analysis of semi-supervised learning and show that there is an overlooked fundamental difference between the purely supervised and the semisupervised learning paradigms. While in the supervised case, increasing the amount of labeled training data is always seen as a way to improve the classifier’s performance, the converse might also be true as the number of unlabeled data is increased in the semi-supervised case. We also study the impact of this theoretical finding on Bayesian network classifiers, with the goal of avoiding the performance degradation with unlabeled data. We apply the semisupervised approach to face detection and we show that learning the structure of Bayesian network classifiers enables learning good classifiers for face detection with a small labeled set and a large unlabeled set.