Non-Local Contrastive Objectives

David Vickrey, Cliff Chiung-Yu Lin, Daphne KollerICML 2010

TL;DR

This paper introduces a framework for training probabilistic models using "non-local" contrastive objectives. Moving beyond traditional methods that only compare a correct label to its immediate neighbors, the authors propose Contrastive Constraint Generation (CCG). By iteratively identifying and contrasting against distant, high-probability assignments, CCG achieves a 12% error reduction over state-of-the-art methods in scene classification.

The Problem: The Intractable Partition Function

Training undirected graphical models, such as Markov Random Fields (MRFs) or Conditional Random Fields (CRFs), is notoriously difficult due to the partition function ($Z$). This normalization constant requires summing over an exponential number of possible labelings to convert raw "scores" into valid "probabilities." For complex tasks like image segmentation, calculating $Z$ exactly is mathematically intractable.

To bypass this, researchers often rely on contrastive methods. Popular examples include:

  • Pseudo-Likelihood (PL): Compares a pixel's true label only to other possible labels for that specific pixel.
  • Contrastive Divergence (CD): Looks at labels reachable by a few steps of local searching (e.g., Gibbs sampling).

The flaw: These "local" methods fail when the model's distribution is multi-modal. If there are "islands" of high probability far away from the correct label, local methods never "see" them during training and therefore cannot learn to suppress them. Consequently, the model becomes overconfident in completely wrong answers.

Methods: A Generalized Contrastive Framework

The authors propose a generalized framework for Contrastive Objectives. Instead of restricting comparisons to local neighbors, they define an objective that compares the correct label against an arbitrary set of "contrasting" assignments.

Theoretical Contribution

The paper proves that if the set of contrastive comparisons "spans" the space of possible labels—meaning you can "walk" from any labeling to any other through a chain of comparisons—the objective is consistent with Maximum Likelihood. Even with finite data, optimizing this contrastive objective can yield the same optimal parameters as the intractable full likelihood.

Contrastive Constraint Generation (CCG)

To operationalize this theory, the authors introduce the Contrastive Constraint Generation (CCG) algorithm. It works iteratively:

  1. Initialize: Start with a simple, tractable objective like Pseudo-Likelihood.
  2. Optimize: Find the best model parameters for the current objective.
  3. Inference: Use the current model to find "interesting" (high-probability) but incorrect labelings. They use Maximum A Posteriori (MAP) inference techniques, such as Iterated Conditional Modes (ICM) or Max-Product Belief Propagation, to locate these distant peaks.
  4. Update: Add these new "non-local" assignments to the contrastive objective.
  5. Repeat: Continue until the model no longer finds new high-probability incorrect assignments.

Key Insights

  • Probability Ratio Matching: Contrastive objectives work by enforcing correct probability ratios between pairs of assignments. Local comparisons only calibrate local ratios. To calibrate the entire model, you need a "path" of comparisons connecting distant regions of the label space.
  • Calibration vs. Margin: Unlike Max-Margin methods—which merely ensure the correct answer scores higher than the second-best—CCG attempts to produce accurate probability estimates. This makes it far more robust for downstream tasks requiring uncertainty quantification.
  • Static vs. Dynamic: Static methods use a fixed comparison set, while dynamic methods like CCG adapt the set over time. Although dynamic methods can introduce a small bias, their flexibility allows them to efficiently target the most problematic "modes" in the distribution.

Key Results

The authors evaluated their approach on a real-world machine vision task using the Street Scenes Dataset (715 images, 8 classes). To manage computational load, they operated on pre-segmented regions rather than individual pixels.

The CCG algorithm significantly outperformed traditional local methods and margin-based approaches.

Test error rates for various learning methods, showing CCG achieving the lowest error at 19.0%.

As shown in the results table:

  • Pseudo-Likelihood (PL): Performed poorly (46.1% error), relying too heavily on local correlations that vanished at test time.
  • Contrastive Divergence (CD): Achieved around 21.9% to 22.5% error.
  • Max-Margin (MM): Achieved 21.7% error.
  • CCG (The Winner): The best variant, CCG(MP-MV+PL), achieved 19.0% error, representing a 12% relative error reduction over the best baseline.

Furthermore, CCG proved to be highly sample-efficient compared to local sampling methods.

Convergence comparison showing CCG reaching lower test error than Contrastive Divergence (CD) methods over time.

The non-local constraints found via MAP inference are much more informative than the samples generated by local Gibbs sampling. As a result, CCG reaches high accuracy in far fewer iterations than Contrastive Divergence.

Limitations and Future Work

  • Computational Cost: While CCG requires fewer iterations than CD, each iteration involves a full optimization step and an inference step, which can be computationally heavy for very large models.
  • Optimization Strategy: The paper utilized batch optimization (BFGS). Implementing a Stochastic Gradient Descent (SGD) version of CCG could accelerate the process and make it applicable to massive datasets.
  • Inference Dependence: The success of CCG hinges on the quality of the MAP inference. If the inference algorithm fails to find the "interesting" distant modes, the contrastive objective loses its effectiveness.

Summary updated

BibTeX
@inproceedings{vickrey2010non,
  author = {David Vickrey and Cliff Chiung-Yu Lin and Daphne Koller},
  title = {{Non-Local Contrastive Objectives}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
}
Figure