A Rate Distortion Approach for Semi-Supervised Conditional Random Fields

Yang Wang, Gholamreza Haffari, Shaojun Wang, Greg MoriNeurIPS 2009 · OpenReview

In many machine learning domains—such as natural language processing and computer vision—unlabeled data is plentiful, but manual annotation remains prohibitively expensive. Semi-supervised learning aims to bridge this gap by leveraging both labeled and unlabeled datasets. While many techniques exist for simple multi-class classification, applying them to structured prediction tasks, like sequence labeling with Conditional Random Fields (CRFs), is notoriously difficult.

Previous attempts to solve this often relied on "minimum conditional entropy," a method that encourages the model to be highly confident on unlabeled data. However, this approach lacks a solid theoretical foundation and frequently leads to "degeneracy"—a scenario where the model simply places all its probability mass on a single label to artificially achieve zero entropy.

To address this, researchers have proposed a novel, principled information-theoretic framework for training CRFs that frames semi-supervised learning as a rate distortion problem.

A Rate Distortion Framework

In information theory, rate distortion theory deals with the minimum number of bits (the "rate") needed to represent a source given a maximum allowable "distortion." The authors adapt this concept to create a more robust, theoretically grounded way to incorporate unlabeled data into discriminative models.

  1. The Objective: The proposed training objective minimizes the mutual information (MI) between the empirical distribution of unlabeled data and the model’s predictions. This minimization is subject to a constraint on the model's performance (the "distortion") on the labeled data.
  2. Information-Theoretic Interpretation: This approach treats semi-supervised learning as a data compression or clustering problem. The goal is to find a compact representation of the data (low mutual information) that still preserves the essential "signal" found in the labeled examples.
  3. Variational Training: For structured prediction tasks like sequence labeling, calculating the exact gradient of mutual information is computationally intractable because it requires summing over an exponential number of possible label configurations. To overcome this, the authors developed a convergent variational training algorithm. By utilizing Jensen’s inequality, they create a tractable upper bound on the objective function, allowing for efficient model optimization without a combinatorial explosion of terms.

Experimental Setup

The authors evaluated their rate distortion approach on two primary tasks:

  • Text Categorization: Binary classification problems derived from the 20 Newsgroups dataset (e.g., distinguishing rec.autos from rec.motorcycles).
  • Hand-written Character Recognition: A structured sequence labeling task involving approximately 6,000 handwritten words, where each word is treated as a sequence of characters.

Results and Key Insights

The rate distortion framework effectively acts as semi-supervised clustering with guidance. The unlabeled data provides the underlying structure of the data space, while the labeled data "anchors" these clusters to specific semantic meanings.

Unlike minimum entropy—which merely forces the model to be "sure" of its predictions—minimum mutual information acts as a data-dependent prior. It encourages the model to find a simple, consistent mapping from inputs to outputs across the unlabeled data space.

Accuracy comparison of the Mutual Information (MI) approach versus baselines across different ratios of unlabeled to labeled data.

Key experimental findings include:

  • Superior Performance: In text categorization, the Rate Distortion (MI) approach consistently outperformed standard $l_2$ regularization, minimum conditional entropy (minCE), and maximum conditional entropy (maxCE) across various ratios of unlabeled to labeled data.
  • Sequence Labeling Gains: On the handwritten character task, the MI approach demonstrated significant gains over competing methods. Notably, the performance gap was much larger in the structured learning setting (sequence labeling) compared to a baseline "sanity check" where characters were treated as independent multi-class problems.
  • Robustness: The MI regularizer proved significantly more stable than minimum entropy, which has a tendency to degrade overall performance if the model becomes overconfident in incorrect predictions.

Limitations and Future Directions

While the variational approach successfully makes the problem tractable for linear-chain CRFs, extending this framework to more complex graph structures (like grids or general graphs) remains a challenge for future research. Additionally, despite the variational approximation, the method is still more computationally intensive than standard supervised training or simple entropy regularization.

Finally, the authors note that further theoretical work is needed to fully illuminate exactly how reducing the information rate directly translates to better generalization across different types of discriminative models.

Summary updated

Abstract

We propose a novel information theoretic approach for semi-supervised learning of conditional random fields. Our approach defines a training objective that combines the conditional likelihood on labeled data and the mutual information on unlabeled data. Different from previous minimum conditional entropy semi-supervised discriminative learning methods, our approach can be naturally cast into the rate distortion theory framework in information theory. We analyze the tractability of the framework for structured prediction and present a convergent variational training algorithm to defy the combinatorial explosion of terms in the sum over label configurations. Our experimental results show that the rate distortion approach outperforms standard $l_2$ regularization and minimum conditional entropy regularization on both multi-class classification and sequence labeling problems.
BibTeX
@inproceedings{wang2009rate,
  author = {Yang Wang and Gholamreza Haffari and Shaojun Wang and Greg Mori},
  title = {{A Rate Distortion Approach for Semi-Supervised Conditional Random Fields}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=SkWRedbd-B},
}
Figure