Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification

Marco Loog

TL;DR

Semi-supervised learning (SSL) often risks degrading classifier performance if model assumptions don't perfectly match the data. This paper introduces Maximum Contrastive Pessimistic Likelihood (MCPL) estimation, a framework that guarantees semi-supervised estimates will never be worse than their supervised counterparts on the training set, providing a "safe" way to leverage unlabeled data.

What Problem Does This Paper Address?

The promise of semi-supervised learning is simple: use cheap, unlabeled data to improve models trained on expensive, labeled data. However, in practice, SSL is a double-edged sword. If the model is "misspecified"—meaning the mathematical assumptions of the classifier (like Gaussian distributions in LDA) don't perfectly fit the real-world data—adding unlabeled data can actually deteriorate performance.

Most existing SSL methods, like Expectation-Maximization (EM) or self-learning, rely on the "cluster assumption" or other strict premises that are hard to verify. When these assumptions fail, the model drifts. The author, Marco Loog, tackles the fundamental challenge of creating an SSL estimation principle that is robust and provides theoretical guarantees of improvement without requiring restrictive data assumptions.

Methods

The author proposes MCPL, which rests on two core pillars:

  1. Contrastive: Instead of just maximizing the likelihood of the unlabeled data, the objective function looks at the difference (the contrast) between the semi-supervised estimate and the initial supervised solution. This allows the model to explicitly control and ensure improvement over the baseline.
  2. Pessimistic: Since we don't know the true labels of the unlabeled data, MCPL assumes the "worst-case" scenario. It searches for a parameter set that performs well even if the unlabeled data is assigned labels in the most adversarial way possible (the labeling that minimizes the gain in likelihood).

Mathematically, this results in a maximin problem: find the parameters $\theta$ that maximize the minimum possible improvement over the supervised baseline across all possible soft-labelings of the unlabeled data.

The paper specifically derives this for Linear Discriminant Analysis (LDA). Because the log-likelihood for LDA is concave in its canonical parameters, the author proves that the MCPL solution is unique and, for continuous data, is almost surely strictly better than the supervised version in terms of log-likelihood.

Datasets

The method was evaluated using 16 diverse datasets from the UCI Machine Learning Repository, including:

  • Physical/Sensor data: Gas sensor array drift, Magic gamma telescope, MiniBooNE particle identification.
  • Image/Pattern recognition: Landsat satellite, Optical/Pen-based recognition of handwritten digits, Letter recognition.
  • Biological/Medical: QSAR biodegradation, Skin segmentation, Spectf heart.
  • Others: Banknote authentication, Climate model simulation, Spambase.

The experiments used small labeled sets (typically $2 \times \text{dimensionality} + \text{classes}$) to simulate the low-data regime where SSL is most needed.

Key Insights and Ideas

  • The "Safety First" Approach: By being "pessimistic," the model becomes conservative. It only changes the supervised parameters if the unlabeled data provides a signal so strong that it improves the likelihood even under the worst-case labeling.
  • Breaking the "Deterioration" Cycle: Unlike EM, which can get stuck in feedback loops of misclassification, MCPL uses the supervised solution as an anchor. This prevents the "drifting" commonly seen in self-learning.
  • Likelihood vs. Error Rate: A key "aha" moment is the reminder that while we can guarantee improvements in log-likelihood, this doesn't always translate to a lower classification error (0-1 loss). However, the experiments show that in the vast majority of cases, the two are highly correlated.
  • Implicit Regularization: The pessimistic approach acts as a form of robust regularization, making the resulting covariance matrices in LDA much more stable than those estimated from tiny labeled samples alone.

Key Results

  • Training Guarantee: In 100% of the 16,000 experiments (1,000 runs per dataset), the MCPL estimate was better than or equal to the supervised estimate on the training set log-likelihood.
  • Test Performance: On unseen test data, MCPL-LDA outperformed supervised LDA in terms of log-likelihood in nearly every case (e.g., 99.8% of the time on the MiniBooNE dataset).
  • Error Rate Reduction: MCPL significantly reduced classification errors. For example, on the optical digits dataset, it achieved a relative error improvement of 42.6% compared to the supervised baseline.
  • Superiority over Ad-hoc Methods: MCPL generally outperformed previous "constrained" versions of LDA, providing a more principled and theoretically grounded framework.

Limitations and Future Work

  • Computational Complexity: Solving a maximinimization (saddle-point) problem is significantly more demanding than standard maximum likelihood. The author uses a heuristic alternating gradient descent/ascent method, but more efficient optimization could be explored.
  • Non-Concave Likelihoods: While the theory works beautifully for exponential families (like LDA or Gaussian mixtures), applying MCPL to models with non-concave likelihoods (like neural networks or complex mixture models) is much harder, as finding the global "pessimistic" labeling becomes difficult.
  • The Likelihood-Error Gap: As seen in the spectf dataset, there are rare cases where improving the likelihood actually increases the error rate. Understanding exactly when this "dipping" phenomenon occurs remains an open research question.

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},
}

Loading related content...

Figure