On the exponential value of labeled samples

Consider the problem of classifying a sample X0 into one of two classes, using a training set Q. Let Q be composed of l labeled samples {(X1, θ1), …, (Xl, θl)} and u unlabeled samples {X′1, …, X′u}, where the labels θi are i.i.d. Bernoulli(η) random variables over the set {1, 2}, the observations {Xi}i=1l are distributed according to fθi(·) and the unlabeled observations {X′j}j=1u are independently distributed according to the mixture density fX′(·) = ηf1(·) + (1−η)f2(·). We assume that f1(·),f2(·) and η are all unknown. Let f1(·) and f2(·) belong to a known family F, and assume that the mixtures of elements of F are identifiable. Even when the number of unlabeled samples is infinite and the decision regions can therefore be identified, one still needs labeled samples to label the decision regions with the correct classification. Letting R(l, u) denote the optimal probability of error for l labeled and u unlabeled samples, and assuming that the pairwise mixtures of F are identifiable, we obtain the obvious statements R(0, u) = R(0, ∞) = 12, R(1, 0) ⪕ 2ηη, R(∞, u) = R∗, and then prove R(1, ∞) = 2R∗(1−R∗), where R∗ is the Bayes probability of error, and R(l, ∞) = R∗ + exp{ −αl + o(l)}, where the exponent α is given by −log(2√ηη∫ √f1(x)f2(x) dx). Thus the first labeled sample reduces the risk from 12 to 2R∗(1−R∗) and subsequent labeled samples in the training set reduce the probability of error exponentially fast to the Bayes risk.