Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification

Marco Loog

Abstract

Improvement guarantees for semi-supervised classifiers can currently only be given under restrictive conditions on the data. We propose a general way to perform semi-supervised parameter estimation for likelihood-based classifiers for which, on the full training set, the estimates are never worse than the supervised solution in terms of the log-likelihood. We argue, moreover, that we may expect these solutions to really improve upon the supervised classifier in particular cases. In a worked-out example for LDA, we take it one step further and essentially prove that its semi-supervised version is strictly better than its supervised counterpart. The two new concepts that form the core of our estimation principle are contrast and pessimism. The former refers to the fact that our objective function takes the supervised estimates into account, enabling the semi-supervised solution to explicitly control the potential improvements over this estimate. The latter refers to the fact that our estimates are conservative and therefore resilient to whatever form the true labeling of the unlabeled data takes on. Experiments demonstrate the improvements in terms of both the log-likelihood and the classification error rate on independent test sets.

Introduction

The promise of semi-supervised learning (SSL) is to leverage abundant, inexpensive unlabeled data to augment models trained on scarce, expensive labeled data. However, in practice, SSL is often a double-edged sword. If the underlying model assumptions—such as the Gaussian distributions in Linear Discriminant Analysis (LDA)—do not perfectly align with the real-world data distribution, the inclusion of unlabeled data can lead to "model drift." In such cases of model misspecification, standard SSL techniques like Expectation-Maximization (EM) or self-learning can actually degrade the performance of the classifier compared to a purely supervised approach.

This paper introduces Maximum Contrastive Pessimistic Likelihood (MCPL) estimation, a framework designed to provide a "safe" way to utilize unlabeled data. MCPL guarantees that the resulting semi-supervised estimates will never be worse than their supervised counterparts on the training set log-likelihood, offering a robust alternative to traditional SSL methods.

The MCPL Framework: Contrast and Pessimism

The MCPL approach is built upon two fundamental pillars that distinguish it from standard likelihood maximization:

  1. Contrastive Estimation: Rather than maximizing the likelihood of the unlabeled data in isolation, the MCPL objective function focuses on the contrast—the difference—between the semi-supervised estimate and the initial supervised solution. This anchoring ensures that the model explicitly controls and monitors its improvement over the baseline.
  2. Pessimistic Labeling: Because the true labels of the unlabeled data are unknown, MCPL adopts a conservative, worst-case stance. It seeks a parameter set that performs well even if the unlabeled data were assigned labels in the most adversarial manner possible (i.e., the labeling that minimizes the gain in likelihood).

Mathematically, this results in a maximin optimization problem. The goal is to find the parameters $\theta$ that maximize the minimum possible improvement over the supervised baseline across all possible soft-labelings of the unlabeled data. By being "pessimistic," the model only deviates from the supervised parameters if the signal in the unlabeled data is strong enough to overcome the worst-case labeling scenario.

Theoretical Guarantees in LDA

The paper specifically applies this principle to Linear Discriminant Analysis (LDA). Because the log-likelihood for LDA is concave in its canonical parameters, the author demonstrates that the MCPL solution is unique. Furthermore, for continuous data, the author provides a proof that the semi-supervised version is almost surely strictly better than the supervised version in terms of log-likelihood. This provides a theoretical safety net that is largely absent from other SSL paradigms, which typically rely on hard-to-verify assumptions like the "cluster assumption."

Experimental Evaluation

The efficacy of MCPL was evaluated using 16 diverse datasets from the UCI Machine Learning Repository, spanning physical sensors, image recognition, and biological data. To simulate the low-data regimes where SSL is most critical, the experiments utilized small labeled sets (typically $2 \times \text{dimensionality} + \text{classes}$).

Key Findings

  • Training Reliability: Across 16,000 experimental runs (1,000 per dataset), the MCPL estimate was equal to or better than the supervised estimate in 100% of cases regarding training set log-likelihood.
  • Generalization: On unseen test data, MCPL-LDA outperformed supervised LDA in log-likelihood nearly every time (e.g., 99.8% of the time on the MiniBooNE dataset).
  • Error Rate Reduction: While the theory guarantees improvements in log-likelihood, the experiments showed these gains translated to significant reductions in classification error. For instance, on the optical digits dataset, MCPL achieved a relative error improvement of 42.6% over the supervised baseline.
  • Implicit Regularization: The pessimistic approach acts as a form of robust regularization. By considering the worst-case labeling, the resulting covariance matrices in LDA become more stable than those estimated from tiny labeled samples alone.

Discussion and Limitations

While MCPL offers a principled and safe framework for SSL, it introduces new challenges. Solving a maximin (saddle-point) problem is computationally more intensive than standard maximum likelihood estimation. The current implementation uses an alternating gradient descent/ascent method, but more efficient optimization strategies remain an area for future work.

Additionally, while the theory is robust for exponential families with concave likelihoods, extending MCPL to models with non-concave likelihoods—such as deep neural networks—is more complex. In those cases, finding the global "pessimistic" labeling becomes a significant hurdle. Finally, while log-likelihood and error rates are generally correlated, rare cases (like the spectf dataset) show that improving likelihood does not always guarantee a lower error rate, a phenomenon that warrants further investigation.

Conclusion

Maximum Contrastive Pessimistic Likelihood estimation provides a theoretically grounded solution to the problem of performance degradation in semi-supervised learning. By combining a contrastive objective with a pessimistic view of unlabeled data, MCPL ensures that the inclusion of additional data is a "safe" bet, consistently meeting or exceeding the performance of supervised baselines.

Summary updated

Abstract

Improvement guarantees for semi-supervised classifiers can currently only be given under restrictive conditions on the data. We propose a general way to perform semi-supervised parameter estimation for likelihood-based classifiers for which, on the full training set, the estimates are never worse than the supervised solution in terms of the log-likelihood. We argue, moreover, that we may expect these solutions to really improve upon the supervised classifier in particular cases. In a worked-out example for LDA, we take it one step further and essentially prove that its semi-supervised version is strictly better than its supervised counterpart. The two new concepts that form the core of our estimation principle are contrast and pessimism. The former refers to the fact that our objective function takes the supervised estimates into account, enabling the semi-supervised solution to explicitly control the potential improvements over this estimate. The latter refers to the fact that our estimates are conservative and therefore resilient to whatever form the true labeling of the unlabeled data takes on. Experiments demonstrate the improvements in terms of both the log-likelihood and the classification error rate on independent test sets.
BibTeX
@article{loog2016contrastive,
  author = {Marco Loog},
  title = {{Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2016},
  url = {https://openreview.net/forum?id=4lHsE6nmo9},
}
Figure